Квазиньютоновские методы, или когда вторых производных для Атоса слишком много

в 12:26, , рубрики: BFGS, DFP, Алгоритмы, квазиньютоновские методы, математика, машинное обучение, методы оптимизации

При первом знакомстве с квазиньютоновскими методами можно удивиться дважды. Во-первых, после беглого взгляда на формулы охватывают сомнения, что это вообще может работать. Однако же они работают. Дальше кажется сомнительным, что они будут работать хорошо. И тем удивительнее видеть то, насколько они превосходят по скорости разнообразные вариации градиентного спуска, причем не на специально построенных задачах, а на самых настоящих, взятых из практики. И если после этого еще остаются сомнения вперемешку с интересом — то нужно разбираться в том, почему вообще работает это нечто.

Ранее уже рассматривалось происхождение и основные идеи, которые приводят в движение градиентные методы, включая метод Ньютона. А именно, мы опирались на ту информацию о поведении функции в окрестности текущего положения, которую дает нам незамысловатый математический анализ. Как минимум предполагалось, что информация о первых производных нам доступна. Что делать, если это все, что нам доступно? Градиентный спуск — наш приговор? Конечно да, если только вдруг не вспомнить, что мы имеем дело с процессом, в ходе которого целевая функция как следует прошаривается. И раз так, что почему бы нам не использовать накопленную информацию о поведении функции для того, чтобы сделать наше блуждание по ее поверхности чуть менее слепым?

Идея использования информации о пройденном пути лежит в основе большинства способов ускорения методов спуска. В этой статье рассматривается один из самых эффективных, хотя и не самый дешевый, способ учета такого рода информации, приводящий к идее квазиньютоновских методов.

Для того, чтобы понять откуда растут ноги у квазиньютоновских методов и откуда вообще пошло такое название, нам снова придется вернуться к методу минимизации, основанному на непосредственном решении уравнения стационарной точки Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 1. Ровно также, как рассмотрение метода Ньютона, примененного к решению данного уравнения, привело нас к одноименному методу оптимизации (который, в отличие от своего прародителя, имеет глобальную область сходимости), мы можем рассчитывать, что рассмотрение иных методов решения систем нелинейных уравнений будет плодотворным в плане идей для построения других методов оптимизации.

Методы секущих

Напомню, что метод Ньютона для решения системы уравнений Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 2, основан на замене в окрестности некоторой близкой к решению точки Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 3 функции Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 4 ее линейной аппроксимацией Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 5, где Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 6 – линейный оператор, который в случае, когда Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 7 является вектором и Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 8 имеет частные производные по каждой переменной, совпадает с матрицей Якоби Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 9. Далее решается уравнение Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 10 и точка Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 11 принимается в качестве нового приближения к искомому решению. Это просто и это работает.

Но что делать, если матрицу Якоби мы по каким-либо причинам вычислить не можем? Первое, что в данном случае приходит в голову — если мы не можем вычислить частные производные аналитически, то вполне можем получить для них численное приближение. Самым простым (хотя и далеко не единственным) вариантом такого приближения может служить формула правых конечных разностей: Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 12, где Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 13 – j-й базисный вектор. Матрицу, составленную из таких приближений, будем обозначать Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 14. Анализу того, насколько замена Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 15 на Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 16 в методе Ньютона влияет его сходимость, посвящено достаточно большое количество работ, но нас в данном случае интересует другой аспект. А именно, такое приближение требует вычисления функции в N дополнительных точках, и, кроме того, функция Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 17 в этих точках интерполирует функцию Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 18, т.е.

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 19

Не каждая аппроксимация матрицы Якоби обладает таким свойством, но каждая матрица аффинной функции, обладающей таким свойством, является аппроксимацией матрицы Якоби. Действительно, если Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 20 и Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 21, то при Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 22. Данное свойство, а именно — свойство интерполирования, дает нам конструктивный способ обобщить метода Ньютона.

Пусть Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 23 – функция, удовлетворяющая требованию Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 24 для некоторой системы линейно независимых векторов Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 25. Тогда такая функция называется секущей функции Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 26, а определяющее ее уравнение — уравнением секущей. Если при этом система векторов Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 27 полна (то есть их ровно N и они все еще линейно независимы), и, кроме того, система векторов Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 28 линейно независима, то Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 29 определяется однозначно.

Любой метод, построенный на основе локальной замены уравнения Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 30 уравнением вида Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 31, где Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 32 удовлетворяет уравнению секущих, называют методом секущих.

Возникает справедливый вопрос о том, как наиболее рациональным способом построить секущую для функции Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 33. Кажется очевидным следующий ход рассуждений: пусть в точке x уже построена аффинная модель, которая интерполирует заданную функцию в точках Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 34. Решение уравнения Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 35 дает нам новую точку Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 36. Тогда для построения аффинной модели в точке Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 37 разумнее всего выбрать точки интерполяции так, что в них значение Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 38 уже известно – то есть взять их из множества Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 39. Возможны разные варианты того, какие именно точки выбирать из множества ранее использованных. Например, можно взять в качестве точек интерполяции такие, в которых Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 40 имеет наименьшее значение, либо просто первые Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 41 точек. В любом случае, кажется очевидным, что Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 42 следует включать в множество точек интерполяции для новой аффинной модели. Таким образом, за Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 43 шагов итерационного процесса в нашем множестве может оказаться до Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 44 смещений, построенных по ранее пройденным точкам. Если процесс построен таким образом, что новая аффинная модель использует не более Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 45 предыдущих значений, то такой процесс называют p-точечным методом секущих.

На первый взгляд может показаться, что наилучшим кандидатом на роль замены метода Ньютона выступает N-точечный метод секущих, поскольку в нем максимально используется информация, которую мы получаем в процессе решения, и при этом минимизируется количество дополнительных вычислений — ведь мы используем значение функции в последних N пройденных точках. К сожалению, это не так. Все дело в том, что система векторов Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 46 упорно отказывается быть линейно независимой при достаточно большом N. Кроме того, даже если это условие оказывается выполненным и соответствующая аффинная модель все-таки существует, то вот шанс, что направления Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 47 также окажутся линейно независимы, оказывается еще меньше. А это влечет за собой то, что аффинная модель хоть и существует, но является вырожденной и практически непригодной.

Вообще, самым устойчивым оказывается 2-х точечный метод секущих. То есть метод, в котором на каждой итерации нам придется вычислять дополнительно N-1 значений функции. Это явно не подходит для наших практических целей.

Тогда вопрос — а к чему все это было?

Квазиньютоновские методы решения уравнений

Выход из положения прост, хотя и не очевиден. Если у нас нет технической возможности на основании уже вычисленных значений однозначно определить аффинную модель, удовлетворяющую уравнению секущих — то и не надо. Возьмем уравнение секущих за основу, но будем требовать, чтобы оно выполнялось только для некоторой неполной системы векторов Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 48. Иными словами, мы будем требовать выполнение условия интерполяции только для достаточно малого количества известных значений. Разумеется, в этом случае мы уже не можем гарантировать, что используемая в такой модели матрица будет стремиться к матрице Якоби, однако это нам и не потребуется. Добавив к этому, что аффинная модель должна интерполировать функцию в текущей точке, то есть Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 49, мы получаем следующую формулировку метода секущих:

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 50

Бройден был первым, кто рассмотрел методы такого вида при m=1, назвав их квазиньютоновскими. Понятно, что условие секущих в данном случае позволяет однозначно идентифицировать матрицу Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 51 только если наложить на нее дополнительные условия, и каждое такое дополнительное условие порождает отдельный метод. Сам Бройден рассуждал следующим образом:

поскольку движение в направлении Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 52 от точки Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 53 к точке Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 54 не дает нам никакой дополнительной информации о том, как изменяется функция в отличных от Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 55 направлениях, то воздействие новой аффинной функции на вектор Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 56 должно отличаться от воздействия старой функции на тот же вектор тем меньше, чем больше отличается Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 57 от Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 58. В крайнем случае, когда Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 59 ортогонален Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 60, поведение новой функции вообще не должно отличаться от поведения старой.

Идея Бройдена гениальна в своей простоте. Действительно, если мы не имеем новой информации о поведении функции, то лучшее, что мы можем сделать — постараться не профукать старую. Тогда дополнительное условие

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 61 для всех Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 62, таких, что Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 63

позволяет однозначно определить матрицу нового преобразования — она получается добавлением к старой матрице поправки ранга 1.

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 64

Однако, не смотря на простоту и логичность сделанных Бройденом умозаключений, они не дают той точки опоры, которая могла бы послужить основой для построения других аналогичных методов. К счастью, существует более формальное выражение его идеи. А именно, построенная таким образом матрица Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 65 оказывается решением следующей задачи:

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 66

Ограничение задачи представляет собой ни что иное, как уравнение секущей, а условие минимизации отражает наше желание сохранить как можно больше информации, содержащейся в матрице Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 67. Мерой расхождения между матрицами в данном случае выступает норма Фробениуса, в которой поставленная задача имеет однозначное решение. Эта формулировка уже вполне может послужить отправной точкой для построения других методов. А именно, мы можем изменить как меру, посредством которой оцениваем вносимые изменения, так и ужесточить условия, накладываемые на матрицу. В общем, с такой формулировкой метода уже можно работать.

Квазиньютоновские методы оптимизации

Поняв основную идею, мы наконец можем вернуться к задачам оптимизации и заметить, что применение формулы Бройдена для пересчета аффинной модели, не слишком удачно ложится на нашу задачу. В самом деле, первая производная от функции-градиента Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 68 есть ни что иное, как матрица Гессе, которая по построению является симметричной. В то же время, обновление по правилу Бройдена приводит к несимметричной матрице Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 69 даже если Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 70 была симметричной. Это не значит, что метод Бройдена не может быть применен для решения уравнения стационарной точки, но на основании такого правила обновления мы вряд ли сможем построить хорошие методы оптимизации. Вообще достаточно очевидно, что квазиньютоновский метод должен работать тем лучше, чем точнее система условий задачи описывает специфику конкретной матрицы Якоби.

Для исправления указанного недостатка добавим дополнительное ограничение к бройденовской задаче минимизации, явно потребовав, чтобы новая матрица была симметричной наряду со старой:

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 71

Решением данной задачи является

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 72

Здесь Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 73, а формула пересчета матрицы носит имя своих создателей — Пауэлла, Шанно и Бройдена (PSB). Получаемая в результате матрица симметрична, но явно не является положительно определенной, если только вдруг Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 74 не окажется коллинеарным Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 75. А мы видели, что положительная определенность является крайне желательной в методах оптимизации.

Опять скорректируем условие задачи, использовав на этот раз в качестве меры расхождения матриц масштабированную норму Фробениуса.

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 76

Происхождение такой постановки вопроса — отдельная большая тема, однако интересно, что если матрица T такова, что Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 77 (то есть G также является матрицей аффинного преобразования, удовлетворяющего уравнению секущих для направления p), то решение данной задачи оказывается независимым от выбора T и приводит к формуле обновления

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 78

известной как формула Давидона-Флетчера-Пауэлла. Данный способ обновления неплохо зарекомендовал себя на практике, поскольку обладает следующим свойством:

если Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 79 и Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 80 положительно определена, то Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 81 также положительно определена.

Отмечу вдогонку, что если первое условие не выполнено, то вообще не существует аффинной функции с положительно определенной матрицей, которая удовлетворяет уравнению секущей.

Если в задаче, приводящей к DFP-методу, взять в качестве меры расхождения аффинных моделей расстояние не между самими матрицами, а между обратными к ним, то получим задачу вида

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 82

Ее решение — широко известная формула, открытая почти одновременно Бройденом, Флетчером, Гольдфарбом и Шанно (BFGS).

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 83

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

Все описанные методы обновления матрицы предполагают внесение поправки ранга 2. Это позволяет легко и непринужденно обратить матрицу Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 84, используя формулу Шермана-Моррисона и значение Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 85.

Квазиньютоновские методы, или когда вторых производных для Атоса слишком много - 86

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

Осталось рассмотреть вопрос о том, как должна выглядеть самая первая матрица в квазиньютоновском процессе. Здесь все очевидно — чем она ближе к матрице Гессе или к ее скорректированному варианту, если гессиан вдруг не окажется положительно определенным, тем будет лучше с точки зрения сходимости. Однако в принципе нам может подойти любая положительно определенная матрица. Самый простой вариант такой матрицы — единичная, и тогда первая итерация совпадает с итерацией градиентного спуска. Флетчером и Пауэллом было показано (естественно, для DFP-метода), что в случае минимизации квадратичной функции в независимости от того, какая (положительно определенная) матрица будет использована в качестве начальной DFP-итерации приведут к решению ровно за N итераций, где N – размерность задачи, причем квазиньютоновская матрица совпадет с матрицей Гессе в точке минимума. В общем нелинейном случае такого счастья мы, само собой, не дождемся, однако это по крайней мере дает повод не слишком переживать на счет неудачного выбора начальной матрицы.

Заключение

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

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

Теоретически определить, какой из огромного количества возможных квазиньютоновских методов окажется наиболее эффективным по отношению к некоторому классу задач практически невозможно. Обычно при формулировании метода ограничиваются тем, что показывают его эффективность при минимизации квадратичной функции (к слову, метод считается эффективным, если приводит к точному решению за N итераций, то есть не медленнее, чем прямые методы решения СЛАУ). В более редких случаях можно найти исследования порядка сходимости метода (который обычно сверхлинейный, то есть существенно лучше того, что нам дает градиентный спуск), устойчивости и других представляющих интерес характеристик. Но в целом, единственный разумный критерий, позволяющий судить об эффективности того или иного метода для конкретного класса задач — практика. Так что лопаты в руки — и успехов в применении.

Автор: alexkolzov

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js