Comments 30
К сожалению, мне не известно хоть сколь-нибудь строгого обоснования данного выбора, но в качестве эмпирической рекомендации он упоминается довольно часто.
Не настоящий сварщик, но есть версия, что это для того, чтобы скомпенсировать разный масштаб переменных, который не учитывается в дефолтной регуляризации с единичной матрицей. В этом случае, как раз, доверительный регион будет "эллипсом", а не "сферой"
Пока мы не регуляризируем — да, но добавление lambda*I начинает приводить нашу параболу к сферической форме.
И это не строгое обоснование, а умозрительное.
По идее так же работает диагональный прекондишенер в методе сопряженных градиентов
Пока мы не регуляризируем — да, но добавление lambda*I начинает приводить нашу параболу к сферической форме.
Тогда уж приводить параболу к плоскости, форма региона не меняется. Этот аргумент справедлив если матрица Гессе близка к диагональной — тогда переменные правильно масштабируются, а направление оказывается очень близко к ньютоновскому. Тот же аргумент с большим правом может быть применен к исправленному гессиану или квазиньютоновской метрике.
По идее так же работает диагональный прекондишенер в методе сопряженных градиентов
Это экстраполяция геометрических представлений с плоского случая на многомерный. Идею прочувствовать помогает, но в общем и целом — эмпирика. По идее вы правы, но я говорил о том, что не знаю строгого обоснования.
Тогда уж приводить параболу к плоскости, форма региона не меняется.
Не очень правильно выразился — парабола остается параболой, просто если оригинальная аппроксимация могла иметь довольно вытянутую форму (эллипс), то добавление регуляризации сделает ее менее вытянутой (сфера)
По идее вы правы, но я говорил о том, что не знаю строгого обоснования.
Так-то и метод Гаусса-Ньютона тоже во многом эмпиричен :) Если не ошибаюсь, то его сходимость не гарантируется, в отличие от метода Ньютона. Более того, что Левенберг-Марквардт, что Dog leg опираются на эвристики при подборе размера trust region.
В каком месте Гаусс-Ньютон эмпиричен? По поводу сходимости Ньютона я говорил в прошлом посте и вот он как раз может расходиться, а вот Гаусс-Ньютон сходится глобально. В приведённом изложении без явного использования размера региона Левенберг-Марквардт ни на какие эвристики не опирается, а трастрегионы общего вида опираются на них только плане угадывания размера региона. Ну ещё иногда при поиске квазиоптимального решения, но эти правила эвристичны в меньшей степени.
Насчет сходимости Гаусса-Ньютона — https://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm#Convergence_properties. Пишут что "However, convergence is not guaranteed, not even local convergence as in Newton's method, or convergence under the usual Wolfe conditions"
а трастрегионы общего вида опираются на них только плане угадывания размера региона.
Вот их я и имел ввиду.
Потому что Википедия брешет. Проблема не в том, что направление, которое метод даёт плохое, проблема в методах линейного поиска — Вульфа, Гольдштейна и их модификаций. Для выдаваемых ими последовательности шагов действительно возможно построить контрпримеры, при которых поиск не сходится даже к локальному минимуму. Это уже сделано для Ньютона, Гаусса-Ньютона, некоторых квазиньютоновских, возможно ещё для каких-то мне неизвестных. Но это никак не отменяет их теоретических свойств сходимости. Просто на практике предполагают без проверки наличие свойств, которые у задачи могут отсутствовать.
Почти любой метод второго порядка быстрее чем градиентный спуск, причем намного (как минимум для большинства практических задач).
Локально аппроксимируем нашу функцию ошибки в точке при помощи квадратичной функции, после чего делаем шаг в точку минимума нашей аппроксимации. Повторить до сходимости.
Можете представить себе участок функции ошибки, который выглядит как "узкий желоб" с небольшим наклоном (например что-то похожее на https://www.wolframalpha.com/input/?i=f%28x%2C+y%29+%3D+100*x%5E2+%2B+0.1*y%5E2+-+x*y). Предположим, что мы стоим на стенке. Метод наискорейшего спуска укажет в сторону противоположной стенки. Дальше, если у нас есть эффективный line search, то градиентному спуску надо сделать сначала шаг в пространство между стенками, а потом шаг в направлении наклона желоба. Если у нас нет эффективного line search, то градиентный спуск будет осцилировать между стенками, медленно смещаясь в сторону глобального минимума.
Метод Ньютона сразу будет делать эффективный шаг в минимум, т.к. помимо направления наискорейшего спуска им известна локальная форма функции.
В теории, методы третьего порядка должны давать еще более эффективные шаги, но на практике такую аппроксимацию очень сложно и дорого использовать.
Сложность сильно зависит от деталей.
Для каких-нибудь блочно-диагональных или ленточных якобианов это перемножение будет очень дёшево.
А число итераций может снижаться на порядки. Или робастность метода радикально улучшаться при добавлении второго порядка.
Хотя, конечно, есть случаи, когда овчинка не стоит выделки. В этом засада вообще всех численных методов — "лучше в теории" совсем не означает "лучше на практике в 100% случаев". Почти всегда метод надо подстраивать под задачу.
Хитрость в длине шага.
Если шаг длинный — то в конечной точке он далёк от настоящего градиента, и там будет резкий поворот. Если шаг короткий — надо много итераций.
Классическая картинка:
Методы второго порядка умеют "осреднять" градиент и делать шаги "прямо к минимуму".
Ну поправьте, как верно.
Я, может быть, плохо сформулировал (и невольно поспособствовал росту каких-то заблуждений, да).
У меня лично такая цепочка. Реальное время сходимости метода определяется именно количеством шагов. А меньше шагов можно сделать, только если шаг будет длинным. А у чисто градиентного метода, если не учитывать историю (а если учитывать — это будет уже другой метод с другой сходимостью), вообще нет информации, как выбрать длину шага. Поэтому линейный поиск, зигзаги в одном случае и избыточное количество шагов в другом и т.д. А у квадратичного метода есть матрица, которая говорит и куда двигаться, и насколько — и для квадратичной формы гарантированно приводит в стационарную точку с первой же итерации.
Меньше шагов можно сделать, только если шаг будет длинным
Нет, меньше шагов можно сделать если правильно выбрано направление шага.
У чисто градиентного метода вообще нет информации как выбрать длину шага
Ни у какого метода нет такой информации. У вас есть только гарантия, что если выбранное направление является направлением спуска, то существует такой шаг в этом направлении, что значение целевой функции уменьшится.
У квадратичного метода есть матрица, которая говорит и куда двигаться, и насколько
Не для «квадратичного метода», а для метода Ньютона при решении уравнения, которому удовлетворяет стационарная точка. Вы имеете ввиду именно его — будьте точны в терминах. Его сходимость — локальна. Глобально сходящаяся версия метода требует, во-первых, положительную определенность гессиана в каждой проходимой точке, и во-вторых — также линейного поиска. То есть куда двигаться — да, насколько — нет.
А зигзаги возникают не от недостатка информации о длине шага, а от недостатка информации о разности масштаба (грубо) переменных, который может быть учтён посредством изменения формы доверительного региона. Что и приводит к методу Ньютона, квазиньютонам и т.д.
Абсолютно верные замечания.
Но что-то это уходит от исходного вопроса, который был "Интересно, может ли что-то сойтись быстрее чем в градиентном спуске, ведь мы идем всегда в направлении максимального спуска".
Я всего лишь написал, что градиентный спуск, если делать не бесконечно короткие, а длинные шаги, не тождественен максимальному спуску, что поправки следующего порядка и призваны исправить.
И то, что серебряной пули в численных методах нет, — это тоже в другом комментарии написал.
alexkolzov а нет желания подробно разобрать BFGS? Что метод Ньютона, что Гаусса-Ньютона довольно хорошо разобраны в разных источниках, а для BFGS все обычно ограничиваются общей формулировкой (накапливаем значение матрицы обратной матрице Гессе), и выражением для шага. А метод ведь очень красивый, и использует только градиент ф-ии + line search
А еще лучше K-FAC (https://arxiv.org/abs/1503.05671). Там вообще все хорошо — идеи из метода Гаусса-Ньютона адаптируются для эффективного обучения нейронок. Правда его все еще никто особо не использует на практике :)
Плюсую за BFGS.
Попробовал недавно — просто, красиво, эффективно.
А ещё там можно обновлять не матрицу, а сразу разложение Холецкого, и будет численно устойчиво.
А ещё есть трюки, чтобы сразу взять "хорошее" приближение для матрицы, и тогда линейный поиск оказывается почти не нужен.
А ещё там можно обновлять не матрицу, а сразу разложение Холецкого
Про такое не слышал, а можно подробней?
А ещё есть трюки, чтобы сразу взять "хорошее" приближение для матрицы
А не поделитесь тем, что зашло?)
Линейный поиск стал для меня причиной отказа от BFGS в продакшене — слишком сложно тюнить для некоторых случаев. Гаусс-Ньютон не всегда хорош, но довольно робастен, на практике. К сожалению, расчет якобиана не очень хорошо ложится на автодифф, поэтому приходиться страдать.
Можно посмотреть Gill, Murray and Wright, Practical Optimization.
Там почти в начале приводятся формулы для rank-one update разложения Холецкого.
Там же предлагается модифицированное разложение Холецкого — по сути, берём матрицу, пытаемся делать обычное разложение, если где-то вылез слишком маленький элемент на диагонали — заменяем его на положительный нужной величины. И такое разложение гессиана можно брать как начальное приближение для BFGS.
Реально такую вещь не пробовал, у меня системы довольно маленькие и простые, обхожусь линейным поиском. Вот тут пишут, что с мод. разложением для аналогичной моей задачи линейный поиск даже не понадобился.
Как работает метод Левенберга-Марквардта