Как минимизировать линейную функцию наименьших квадратов в R?

Question

Я читаю Deep Learning от Goodfellow et al. и я пытаюсь реализовать градиентный спуск, как показано в разделе 4.5 Пример: линейные наименьшие квадраты. Это страница 92 на бумажном носителе книги.

Алгоритм может быть рассмотрен подробно в https://www.deeplearningbook.org/contents/numerical.html с R реализацией линейных наименьших квадратов на странице 94.

Я пытался реализовать в R, и реализованный алгоритм сходится к вектору, но этот вектор, по-видимому, не минимизирует функцию наименьших квадратов, как требуется. Добавление эпсилона к рассматриваемому вектору часто дает «минимум», меньший, чем минимум, выдаваемый моей программой.

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?

На странице 94 PDF-файла, который появляется по адресу https://www.deeplearningbook.org/contents/numerical.html

Я пытаюсь найти значения вектора x, чтобы f (x) было минимизировано. Тем не менее, как показывает минимум в моем коде иimum_minus, минимум составляет , а не фактический минимум, так как он превышает минимальный минус.

Есть идеи, в чем может быть проблема?

Answer 1

Исходная задача

Нахождение значения x, при котором величина Ax - b минимизируется, эквивалентно нахождению значения x, при котором Ax - b = 0 или x =(а ^ -1) * б.Это потому, что норма L2 является евклидовой нормой, более известной как формула расстояния.По определению, расстояние не может быть отрицательным, поэтому его минимум равен нулю.

Этот алгоритм, как он реализован, на самом деле очень близок к оценке x.Однако из-за рекурсивного вычитания и округления быстро возникает проблема недостаточного потока, что приводит к массивным колебаниям ниже:

Значение нормы L2 как функции размера шага

Выше алгоритм против решить функция в R

Выше мы имеем результаты A% % x, а затем A% % min_xс x, оцененным по реализованному алгоритму, и min_x, оцененным с помощью функции решить в R.

Проблема недостаточного значения, хорошо известная специалистам по численному анализу, вероятно, лучше всего решаетсяпрограммисты библиотек более низкого уровня, лучше всего подготовленные для его решения.

Подводя итог, можно сказать, что алгоритм работает так, как реализован.Важно отметить, однако, что не каждая функция будет иметь минимум (представьте, что это прямая линия), а также имейте в виду, что этот алгоритм должен быть в состоянии найти только локальный, в отличие от глобального минимума.