Выполнение градиента (крутого) спуска

Question

Я ищу несколько советов о том, как реализовать реализацию Gradient (steepest) Descent в 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) должен ли я реализовать более простым языком, как питон, первый - затем транслируют к 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

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

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

3) В любом случае.

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

Answer 3

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

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

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

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

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

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

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