Реализация градиентного (крутого) спуска

Question

Я ищу несколько советов о том, как реализовать Градиентный (самый крутой) спуск в C. Я нахожу минимум f (x) = || Ax-y || ^ 2, с заданными A (n, n) и y (n).

Это сложно в C (я думаю), потому что вычисление градиента, Δf (x) = [df / dx (1), ..., df / dx (n)] требует вычисления производных.

Я просто хотел бросить это в SO, чтобы получить некоторое руководство по программированию, например:

1) Какая размерность будетлучше всего начинать с (1,2, ...)

2) Советы о том, как делать частичные производные

3) Должен ли я реализовать на более простом языке, напримерсначала на python - затем переведите на C

4) И т.д.

Дайте мне знать ваши мысли!Заранее спасибо

Answer 1

1) Начните в 2D, таким образом, вы можете построить траекторию спуска и увидеть, как работает ваш алгоритм.

2) df / dx = (f (x + h) -f (xh)) / (2 * h), если оценка f дешевая, (f (x + h) -f (x)) / h, если это дорого. Выбор h должен сбалансировать ошибку усечения (в основном с большим h) и ошибку округления (маленький h). Типичные значения h: ~ pow (DBL_EPSILON, 1./3), но фактический показатель степени зависит от формулы для производной, и в идеале должен существовать коэффициент, который зависит от f. Вы можете построить числовую производную как функцию h в логарифмическом масштабе для некоторых заданных точек выборки в пространстве параметров. Затем вы четко увидите диапазон h, оптимальный для точек, которые вы отбираете.

3) Да, все, что вы найдете проще.

4) Трудно найти оптимальный размер шага. Вы можете использовать внутренний цикл для поиска оптимального шага.

Answer 2

Я нахожу минимум f (x) = || Ax-y || ^ 2, с заданными A (n, n) и y (n).

Эта проблема известна как метод наименьших квадратов, и вы выполняете оптимизацию без ограничений.Написание конечно-разностного решателя градиентного спуска на C не совсем правильный подход.Прежде всего, вы можете легко рассчитать производную аналитически, поэтому нет никаких причин делать конечную разницу.Кроме того, проблема является выпуклой, так что она становится еще проще.

(Пусть A 'обозначает транспонирование A)

d/dx ||Ax - y||^2 = 2*A'*(Ax - y)

, поскольку это проблема, которая, как мы знаем, будетпроисходят, когда производная равна 0

0 = 2*A'(Ax - y)
A'y = A'Ax
inverse(A'A)*A'y = x

A'A гарантированно обратимо, потому что оно положительно определено, поэтому проблема сводится к вычислению этого обратного значения, которое равно O (N ^ 3).Тем не менее, есть библиотеки для наименьших квадратов как в C, так и в Python, поэтому вам, вероятно, следует просто использовать их вместо написания собственного кода.

Answer 3

1) Я бы начал с простого 1D примера, а затем перешел бы к 2D, как только я уверен, что это работает.

2) Как вы знаете целевую функцию заранее, возможно, вы можете также предоставить аналитический градиент. Если возможно, это (почти) всегда лучше, чем прибегать к числовым производным.

3) Во что бы то ни стало.

4) Предположительно, самый крутой спуск - это только первый шаг, затем, возможно, рассмотрим что-то вроде CG или BFGS.