2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 13:46 


07/10/15

2400
Имеется следующий алгоритм многомерной оптимизации:
$$\bold x_{n+1}=\bold x_{n+1}-\mu (\bold J^T\bold J^T+\alpha \bold E)^{-1} \bold J^T \bold \delta, $$
где $\bold J$ - матрица Якоби, $\bold \delta$ - вектор невязок, $\mu \in (0, 1] $ - меняющийся шаг, $\alpha $ - параметр регуляризации, $\bold E$ - единичная диагональная матрица.
Оптимизируемый функционал имеет вид:
$$\xi=\bold \delta^T \bold \delta+\alpha \bold x^T\bold x.$$
С уменьшением $\alpha$, как и следовало ожидать, остаточная невязка $\xi_{min}$ уменьшается. Но это наблюдается лишь до некоторого $\alpha_{min}$. При дальнейшем уменьшении $\alpha$ остаточная невязка увеличивается, и при $\alpha=0$ она существенно больше, чем при $\alpha_{min}$.

В общем, до конца алгоритм сходиться не хочет. До eps ещё очень далеко. В чём может быть дело?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 15:23 


16/04/19
161
При $\alpha = 0$ получится метод Ньютона, в котором вместо $\bold J$ почему-то взята $\bold J^T$. Что это за метод такой?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 16:04 
Заслуженный участник
Аватара пользователя


11/03/08
10189
Москва
Там точно как приведено? Транспонированная на транспонированную?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 17:06 


07/10/15

2400
Понятно, что опечатка. Правильно так:
$$\bold x_{n+1}=\bold x_{n+1}-\mu (\bold J^T\bold J+\alpha \bold E)^{-1} \bold J^T \bold \delta. $$
Строго говоря, методом Ньютона это является только в случае нулевой остаточной невязки. Т.е. при точном решении СНАУ. Если невязка не нулевая, например, когда $\bold J$ прямоугольная (а у меня как раз так и есть), то направление оптимизации отличается от ньютоновского, так как не учитываются вторые производные. Поэтому он и называется метод Ньютона-Гаусса.

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 17:07 
Заслуженный участник
Аватара пользователя


11/03/08
10189
Москва
В качестве простейшего объяснения - матрица $\bold J$ неполного ранга или близка к матрице неполного ранга, производные, они часто оказываются сильно скоррелированными (просто по формуле производной сложной функции - общие сомножители появляются), "мультиколлинеарность", как это зовут применительно к регрессии. Матрица $\bold J^T\bold J^T+\alpha \bold E $ при обнулении альфы получается вырожденной или близкой к вырожденной. В силу конечной точности вычислений при попытке ея обращения

(Оффтоп)

в истинную веру
вместо честного деления на ноль и "авоста" получаем игру ошибок округления (и рост элементов обращённой до бесконечности, но при умножении на $\bold J^T$ большие сомножители гасятся маленькими, и результат выглядит правдоподобным, но никакого отношения к оптимизации уже не имеет, это именно шуточки округления. Прибавка единичной матрицы это предотвращает. Здесь хорошо проясняет сделать сингулярное разложение для $\bold J$, сократить и увидеть, что происходит с сингулярными числами в решении и как работает

(Оффтоп)

спецподразделение
альфа.

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 17:44 


07/10/15

2400
Насколько я понимаю, обусловленность $\bold J $ влияет только на ошибки $\bold x$, которые определяются так:
$$|\delta \bold x|=cond(\bold J)\cdot\xi,$$
но сама невязка $\xi$ не должна зависеть от $cond(\bold J)$. Она всё равно должна уменьшаться до некоторого минимального значения, а этого не происходит. Я специально использовал точную модель, для которой $\xi\approx 0$ (порядка $10^{-34}$), но невязка уменьшается только до $10^{-8}$-$10^{-10}$. Непонятно, почему она не уменьшается дальше?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 18:34 
Заслуженный участник
Аватара пользователя


11/03/08
10189
Москва
Величина, достигнутая при оптимизации, вообще от альфы не зависит. Она влияет только на скорость движения к оптимуму. При очень большой альфе получается движение по градиенту мелкими шагами. То есть медленнее, но надёжнее.
Двойная точность это погрешность порядка $10^{-15}$, по числу разрядов мантиссы, а если брать не единичную операцию, а сложное вычисление - $10^{-10}$, откуда $10^{-34}$?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 18:43 


07/10/15

2400
это абсолютная невязка, она может быть и $10^{-300}$

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 18:49 
Заслуженный участник
Аватара пользователя


11/03/08
10189
Москва
Без знания вида задачи не могу говорить более определённо, но у меня впечатление, что просто вышли на максимум точности. Во всяком случае, значение альфы тут не столь важно. Нулевая альфа - пытаемся одним прыжком напрыгнуть на оптимум, но есть шанс из-за численной неустойчивости быть заброшенными далеко от него. Большая альфа - получается почти в точности градиентный поиск помаленьку. А оптимум тот же самый. Просто быстрее или медленнее приближаемся.

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 19:11 


07/10/15

2400
Евгений Машеров в сообщении #1394619 писал(а):
но у меня впечатление, что просто вышли на максимум точности

В этом и весь вопрос. Если взять начальное приближение, равное точному решению, то невязка получается $10^{-34}$. Если взять очень близко к истинному решению - получается уже $10^{-34}$. Если начальное приближение достаточно далеко, то получается примерно $10^{-8}$. Создаётся впечатление, что при достижении некоторой невязки, например $10^{-8}$, процесс оптимизации останавливается, ну или очень сильно замедляется.

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 20:05 


16/04/19
161
Если минимизируется $\xi=\bold \delta^T \bold \delta+(\bold {\sqrt{\alpha} x})^T(\bold {\sqrt{\alpha} x})$, то почему прибавляется $\alpha \bold E$. Эта альфа по идее должна просто попасть в матрицу $\bold J$ и никуда не вылазить из неё, или это другая альфа? При $\alpha=\infty$ должно получаться $\bold x = 0$. Не понятно.

-- 22.05.2019, 21:07 --

а невязка, если это сумма квадратов, совсем плохая (

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 20:39 


07/10/15

2400
feedinglight в сообщении #1394627 писал(а):
та альфа по идее должна просто попасть в матрицу $\bold J$ и никуда не вылазить из неё,

это почему же?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 21:32 
Заслуженный участник
Аватара пользователя


11/03/08
10189
Москва
И можно прояснить
Andrey_Kireew в сообщении #1394542 писал(а):
Оптимизируемый функционал имеет вид:
$$\xi=\bold \delta^T \bold \delta+\alpha \bold x^T\bold x.$$
?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение22.05.2019, 22:09 


07/10/15

2400
что конкретно прояснить?

 Профиль  
                  
 
 Re: Остаточная ошибка метода Гаусса-Ньютона
Сообщение23.05.2019, 01:00 


07/10/15

2400
Благодаря намёку Евгений Машеров я нашел ошибку в алгоритме. Правильно должно быть так:
$$\bold x_{n+1}=\bold x_{n}-\mu (\bold J^T\bold J+\alpha \bold E)^{-1} (\bold J^T \bold \delta+\alpha \bold x_{n}). $$
дело, видимо, было в последнем слагаемом.

Теперь, кажется, всё сходится до предела ошибок вычислений:
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: B@R5uk


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group