r - 如何最小化 R 中的线性最小二乘函数？

Question

我正在阅读 Goodfellow 等人的深度学习。并且正在尝试实现梯度下降，如第 4.5 节示例:线性最小二乘法所示。这是本书纸质版的第 92 页。

详细算法可以查看https://www.deeplearningbook.org/contents/numerical.html第 94 页的线性最小二乘法的 R 实现。

我试过在 R 中实现，实现的算法收敛于一个向量，但这个向量似乎没有按要求最小化最小二乘函数。将 epsilon 添加到有问题的向量中经常会产生小于我程序输出的最小值的“最小值”。

options(digits = 15)
dim_square = 2 ### set dimension of square matrix
# Generate random vector, random matrix, and 
set.seed(1234) 
A = matrix(nrow = dim_square, ncol = dim_square, byrow = T, rlnorm(dim_square ^ 2)/10)
b = rep(rnorm(1), dim_square)

# having fixed A & B, select X randomly 
x = rnorm(dim_square) # vector length of dim_square--supposed to be arbitrary

f = function(x, A, b){
  total_vector = A %*% x + b # this is the function that we want to minimize
  total = 0.5 * sum(abs(total_vector) ^ 2) # L2 norm squared
  return(total)
}
f(x,A,b)

# how close do we want to get?
epsilon = 0.1
delta = 0.01

value = (t(A) %*% A) %*% x - t(A) %*% b
L2_norm = (sum(abs(value) ^ 2)) ^ 0.5

steps = vector()
while(L2_norm > delta){
  x = x - epsilon * value
  value = (t(A) %*% A) %*% x - t(A) %*% b
  L2_norm = (sum(abs(value) ^ 2)) ^ 0.5
  print(L2_norm)
}

minimum = f(x, A, b)
minimum

minimum_minus = f(x - 0.5*epsilon, A, b)
minimum_minus # less than the minimum found by gradient descent! Why?

出现在 https://www.deeplearningbook.org/contents/numerical.html 的 pdf 第 94 页上

我正在尝试找到使 f(x) 最小化的向量 x 的值。但是，正如我的代码中的最小值和 minimum_minus 所示，最小值不是实际的最小值，因为它超过了最小值减去。

知道问题出在哪里吗？

Answer 1

Original Problem

找到使数量 Ax - b 最小化的 x 值等同于找到使 Ax - b = 0 或 x = (A^-1)*b 的 x 值。这是因为 L2 范数是欧氏范数，通​​常称为距离公式。根据定义，距离不能为负，使其最小值相同为零。

该算法的实现实际上非常接近于估计 x。但是，由于递归减法和舍入，很快就会遇到下溢的问题，导致大量振荡，如下:

Value of L2 Norm as a function of step size

Above algorithm vs. solve function in R

上面我们有 A %% x 后跟 A %% min_x 的结果，其中 x 由已实现的算法估计，min_x 由 R 中的 solve 函数估计.

熟悉数值分析的人都知道下溢问题，最好由最有能力解决它的低级库的程序员来解决。

总而言之，该算法似乎与实现时一样有效。然而，需要注意的重要一点是，并非每个函数都有最小值(想想一条直线)，并且还要注意该算法应该只能找到局部最小值，而不是全局最小值。