[ЗАСТАВКА] Продолжим
изучение линейных методов классификации регрессии,
основанных на стохастическом градиенте.
Как мы уже увидели, этот метод имеет много преимуществ,
он легко реализуется, может быть обобщён на нелинейной модели.
Он может быть использован с самыми разными функциями потерь,
может быть использован для больших данных, но,
тем не менее, этот метод имеет и некоторое количество недостатков.
Во-первых, как правило, функционалы, которые получаются в задачах машинного
обучения, являются многоэкстремальными, а какие-то обоснования сходимости для метода
стохастического градиента известны главным образом только для выпуклых функций.
А мы пытаемся его применять для невыпуклых функций,
поэтому сходимость есть, но она только локальная,
к локальному экстремуму, и как найти хорошее начальное приближение,
которое приведёт нас к удачному локальному экстремуму, это важный вопрос.
Дальше, возможна также расходимость или очень медленная сходимость,
поэтому нужно знать, какими способами можно ускорить сходимость этого метода.
Наконец, в линейных моделях возможно переобучение из-за неприятного эффекта,
который называется мультиколлинеарностью.
И вот эти все мелкие проблемы порождают отношение к методу стохастического
градиента как к некому искусству, потому что требуется комплекс эвристик,
каждый раз при решении каждой задачи он подбирается индивидуально.
Давайте рассмотрим эти эвристики и начнём с инициализации весов.
Очень часто в учебниках и популярных руководствах по линейным методам
и даже по методам построения неровных сетей, которые являются их обобщениями,
даётся рекомендация брать в качестве начального приближения либо нулевой
вектор, либо какой-то близкий к нулю случайный вектор.
Это не всегда хорошо работает и не всегда ведёт к хорошим локальным решениям.
Неплохие эвристики для инициализации можно получить,
если воспользоваться очень простыми методами регрессии или классификации,
которые основаны на, ну можно так сказать, драконовских предположениях.
Это предположение о некоррелированности или независимости признаков.
Две такие формулы приведены на слайде.
Первая — для задачи регрессии, очень простая формула,
которая заключается в том, что вы считаете скалярное произведение между векторами
признаков и векторами правильных ответов на всех объектах обучающей выборки.
И примерно столь же простой способ инициализации для задач классификации,
когда вы должны для каждого признака посчитать его среднее значение в
каждом классе, и логарифмы этих средних значений как раз и являются
неплохой инициализацией для вектора весов.
Но если признаки действительно по счастливой случайности окажутся
независимыми, то эти формулы уже практически дают хорошее решение.
Ещё одна эвристика заключается в том,
что эти оценки можно считать по небольшим случайным подвыборкам.
Это работает в том случае, когда выборка у вас избыточна,
вы видите перед собой десять миллионов объектов, но понятно,
что эту инициализацию можно сделать, скажем, по случайной тысяче объектов.
И ещё одна хорошая рекомендация — это метод мультистарта, который заключается в
том, что вы подобного рода инициализацию, например, по случайным подвыборкам
делаете многократно и получаете много исходных точек, из каждой из которой
вы запускаете дальше итерационный процесс стохастического градиента, и может быть,
какие-то из этих запусков приведут вас к более удачным локальным решениям.
Вот это вот способы решения проблемы многоэкстремальности,
выбор начального приближения.
Следующий важный момент, который тоже порождает
несколько хороших эвристик — это в каком же порядке предъявлять объекты.
В методе стохастического градиента считается,
что объекты надо брать в случайном порядке.
Однако если сделать так, чтобы объекты брались не просто случайными, а чтобы они
были существенно отличными друг от друга, то процесс сходимости пойдёт быстрее.
Ну действительно, если вы возьмёте друг за другом два объекта,
которые случайно лежали рядом,
то вы практически никакого эффекта не получите от такого градиентного шага.
Очень простая и эффективная эвристика — так называемая перетасовка объектов.
Давайте брать объекты попеременно из разных классов, это, можно сказать,
эвристика, основанная на гипотезе компактности, потому что считается,
что объекты одного класса, они, как правило, как-то компактно расположены.
А если вы берёте объекты из разных классов,
то они у вас получаются существенно различными.
Можно чаще брать те объекты, на которых была большая ошибка допущена,
то есть вероятность взять объект в следующий раз можно поставить
зависимость от значения отступа на этом объекте.
Можно поставить ограничение объекта,
который имеет большой положительный отступ, вообще перестать брать.
Можно также перестать брать объекты,
которые получили настолько большой отрицательный отступ, что стало ясно,
что это объект-«выброс», и настраиваться на нём уже бесполезно.
Ну в таких эвристиках обычно появляются какие-то дополнительные параметры,
которые приходится перебирать вручную и делать эксперименты многократно
при разных значениях этих параметров.
Следующая важная вещь, которая возникает в градиентных методах
— это варианты выбора градиентного шага.
Если вы посмотрите на учебники по методам оптимизации, то найдёте там такой факт,
что сходимость градиентного метода гарантируется для выпуклых функций,
если мы градиентный шаг устремляем к нулю с итерациями, но не слишком быстро.
И, в частности, можно, например, брать градиентный шаг,
как величину градиентного шага обратно пропорционально номеру итерации.
На практике эта стратегия далеко не всегда работает, и потому что функции
могут иметь очень непростой характер и из-за многоэкстремальности.
Более продвинутая стратегия — это метод скорейшего градиентного спуска,
когда вы шаг h выбираете так, чтобы достичь локального
минимума вот такой вот одномерной функции, которая получается,
если мы будем варьировать градиентный шаг в направлении фиксированного градиента.
Иногда эту задачу удаётся решать аналитически, в частности,
для регрессии при квадратичной функции потерь можно эту задачу
решить и получить величину шага оптимального, и это очень простая формула.
Чтобы выбивать процесс из неудачных локальных экстремумов,
рекомендуется периодически делать пробные большие случайные шаги в разных
направлениях, получать тем самым очередное приближение,
из которого дальше стартует градиентный процесс.
Ну и если он не уходит в какую-то более удачную область, то можно вернуться в ту
точку, из которой мы сделали такой большой прыжок, чем-то похоже на мультистарт.
Ну и наконец, ещё одна интересная стратегия повышения скорости
сходимости — это использование метода второго порядка.
Однако метод второго порядка, в частности, метод Ньютона-Рафсона,
плох тем, что он заставляет нас посчитать матрицу Гессе,
это матрица частных производных,
которая… Её не только долго посчитать, но и её ещё надо обращать,
это операция, которая очень трудоёмкая и далеко не
всегда её удаётся встроить в итерационный процесс.
Можно сделать следующее эвристическое предположение.
Допустим, что в этой матрице Гессе есть диагональное преобладание.
Это действительно часто бывает так, но мы сделаем ещё более грубое предположение,
будем считать все недиагональные элементы равными нулю.
В таком случае матрицу очень легко обратить.
Обратная диагональная матрица — это матрица, у которой на диагонали стоят
обратные элементы, и получается очень простая формула,
в которой практически выписана величина градиентного шага,
причём этот градиентный шаг по каждой размерности свой.
Можно в этой формуле легко полагать градиентный шаг h равным единице.
Вот и ещё приходится вводить дополнительный параметр для того,
чтобы предотвратить обнуление элемента, который оказывается в знаменателе.
Получается, что у нас,
когда градиент большой, но вторая производная близка к нулю,
это означает, что мы находимся где-то в районе точек перегибов функции,
то есть это, скорее всего, далеко от локальных экстремумов,
но в этой области мы можем делать нормальный, настоящий градиентный спуск.
А вот когда мы заходим в область, локально близкую к экстремуму,
то здесь уже надо пользоваться методами, близкими к методам второго порядка.
Вот этот метод называется диагональным методом Левенберга-Марквардта,
и отличается тем, что он очень быстро может быть реализован,
он очень простой как для реализации,
так и в смысле скорости вычислений, он быстрый.
И, тем не менее, он сохраняет свойство метода второго порядка в окрестности
локальных экстремумов.
[ЗАСТАВКА]
