• Градиентный спуск: всё, что нужно знать. Градиентные спуски: batch и stochastic gradient descents

    где f i – функция, подсчитанная на i-м батче, i выбирается случайным образом;

    Шаг обучения является гиперпараметром; при слишком больших значениях алгоритм обучения будет расходиться, при слишком маленьких – будет сходиться медленно.

    Стохастический градиентный спуск с инерцией

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

    (14)
    (15)

    Как несложно догадаться, гиперпараметр инерции μ имеет такое название из-за того, что, подобно так называемой ньютоновой силе инерции, т.е. силе противодействия, «сопротивляется» изменениям градиента и смягчает изменения весовых коэффициентов на протяжении обучения. Такой алгоритм обучения называется стохастическим градиентным спуском с инерцией или SGDМ (stochastic gradient descent with momentum).

    Метод адаптивного градиента

    Метод адаптивного градиента (Adagrad – от англ. «adaptive gradient algorithm») основан на идее масштабирования. Он перемасштабирует скорость обучения для каждого настраиваемого параметра в отдельности, при этом учитывая историю всех прошлых градиентов для этого параметра. Для этого каждый элемент градиента делится на квадратный корень от суммы квадратов предыдущих соответствующих элементов градиента. Такой подход эффективно уменьшает скорость обучения для тех весовых коэффициентов, которые имеют большое значение градиента, а также со временем снижает скорость обучения для всех параметров, так как сумма квадратов неуклонно увеличивается для всех параметров при каждой итерации. При задании нулевого начального масштабирующего параметра g = 0 формула для пересчета весовых коэффициентов имеет вид (деление выполняется поэлементно).

    Цель - минимизировать функцию F в пространстве все возможных точек. График F представляет собой параболическую поверхность, и у неё должен быть один-единственный минимум. А вопрос о том, как исправлять точки так, чтобы двигаться в сторону этого минимума, давным-давно решён в математическом анализе. Для этого нужно двигаться в направлении, противоположном градиенту - вектору, вдоль которого производная максимальна. Градиент вычисляется следующим образом:

    Т.е. для вычисления градиента мы должны использовать производную от заданной функции при соответствующих точках (переменных).

    Таким образом, чтобы определить, как правильно исправлять координаты точек, мы должны вычислить градиент и отнять вектор какой-нибудь наперёд заданной длины (в нашем случае этой длинной выступает заданный шаг а) от имеющегося вектора точек:

    Чтобы реализовать это программно, нужно научиться дифференцировать функцию F:

    Пример 1 - алгоритм градиентного спуска для одной точки.

    GradientDescent()

    • 1. Инициализировать маленькими случайными значениями.
    • 2. Повторить Number_of_Steps раз:
      • а) Для всех i от 1 до n
      • б) Для всех j от 1 до m :
        • (i) Для всех i от 1 до n
    • 3. выдать значения.

    Это значит, что нам нужно подправлять координаты точек после каждого тестового примера так:

    Новый, изменённый алгоритм показан в примере 1. Правда, нужно внести и другие изменения. Во-первых, мы больше не можем рассчитывать на то, что в какой-то момент достигнем идеальной гармонии с исходными данными, и нам нужно научиться останавливаться в какой-то момент. В качестве условия для остановки здесь принято то, что алгоритм выполняется пока разности значений функции меньше ранее заданной точности. Другое изменение - в том, что если оставлять а постоянным, то на каком-то этапе точка перестанет приближаться к искомому минимуму, а начнёт его «перепрыгивать» на каждой итерации, то в одну сторону, то в другую. Поэтому a нужно уменьшать со временем. В данной программе мы уменьшаем шаг на два.

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

    SVM

    Метод опорных векторов (англ. SVM, support vector machine) -- набор схожих алгоритмов обучения с учителем, использующихся для задач классификации и регрессионного анализа. Принадлежит к семейству линейных классификаторов, может также рассматриваться как специальный случай регуляризации по Тихонову. Особым свойством метода опорных векторов является непрерывное уменьшение эмпирической ошибки классификации и увеличение зазора, поэтому метод также известен как метод классификатора с максимальным зазором.

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

    Часто в алгоритмах машинного обучения возникает необходимость классифицировать данные. Каждый объект данных представлен как вектор (точка) в -мерном пространстве (последовательность p чисел). Каждая из этих точек принадлежит только одному из двух классов. Нас интересует, можем ли мы разделить точки гиперплоскостью размерностью Это типичный случай линейной разделимости. Таких гиперплоскостей может быть много. Поэтому вполне естественно полагать, что максимизация зазора между классами способствует более уверенной классификации. То есть можем ли мы найти такую гиперплоскость, чтобы расстояние от неё до ближайшей точки было максимальным. Это бы означало, что расстояние между двумя ближайшими точками, лежащими по разные стороны гиперплоскости, максимально. Если такая гиперплоскость существует, то она нас будет интересовать больше всего; она называется оптимальной разделяющей гиперплоскостью, а соответствующий ей линейный классификатор называется оптимально разделяющим классификатором.

    Формально можно описать задачу следующим образом.

    Полагаем, что точки имеют вид: , где принимает значение 1 или?1, в зависимости от того, какому классу принадлежит точка. Каждое -- это -мерный вещественный вектор, обычно нормализованный значениями или. Если точки не будут нормализованы, то точка с большими отклонениями от средних значений координат точек слишком сильно повлияет на классификатор. Мы можем рассматривать это как учебную коллекцию, в которой для каждого элемента уже задан класс, к которому он принадлежит. Мы хотим, чтобы алгоритм метода опорных векторов классифицировал их таким же образом. Для этого мы строим разделяющую гиперплоскость, которая имеет вид:

    Вектор -- перпендикуляр к разделяющей гиперплоскости. Параметр равен по модулю расстоянию от гиперплоскости до начала координат. Если параметр равен нулю, гиперплоскость проходит через начало координат, что ограничивает решение.

    Так как нас интересует оптимальное разделение, нас интересуют опорные вектора и гиперплоскости, параллельные оптимальной и ближайшие к опорным векторам двух классов. Можно показать, что эти параллельные гиперплоскости могут быть описаны следующими уравнениям (с точностью до нормировки).

    Если обучающая выборка линейно разделима, то мы можем выбрать гиперплоскости таким образом, чтобы между ними не лежала ни одна точка обучающей выборки и затем максимизировать расстояние между гиперплоскостями. Ширину полосы между ними легко найти из соображений геометрии, она равна, таким образом наша задача минимизировать. Чтобы исключить все точки из полосы, мы должны убедиться для всех, что

    Это может быть также записано в виде:

    В случае линейной разделимости классов, проблема построения оптимальной разделяющей гиперплоскости сводится к минимизации при условии (1). Это задача квадратичной оптимизации, которая имеет вид:

    По теореме Куна -- Таккера эта задача эквивалентна двойственной задаче поиска седловой точки функции Лагранжа.


    Где -- вектор двойственных переменных

    Сведем эту задачу к эквивалентной задаче квадратичного программирования, содержащую только двойственные переменные:


    Допустим мы решили данную задачу, тогда и можно найти по формулам:

    В итоге алгоритм классификации может быть записан в виде:

    При этом суммирование идет не по всей выборке, а только по опорным векторам, для которых

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

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

    Аналогично, по теореме Куна-Таккера сводим задачу к поиску седловой точки функции Лагранжа:


    По аналогии сведем эту задачу к эквивалентной:


    На практике для построения машины опорных векторов решают именно эту задачу, а не (3), так как гарантировать линейную разделимость точек на два класса в общем случае не представляется возможным. Этот вариант алгоритма называют алгоритмом с мягким зазором (soft-margin SVM), тогда как в линейно разделимом случае говорят о жёстком зазоре (hard-margin SVM).

    Для алгоритма классификации сохраняется формула (4), с той лишь разницей, что теперь ненулевыми обладают не только опорные объекты, но и объекты-нарушители. В определённом смысле это недостаток, поскольку нарушителями часто оказываются шумовые выбросы, и построенное на них решающее правило, по сути дела, опирается на шум.

    Константу обычно выбирают по критерию скользящего контроля. Это трудоёмкий способ, так как задачу приходится решать заново при каждом значении.

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

    Алгоритм построения оптимальной разделяющей гиперплоскости, предложенный в 1963 году Владимиром Вапником и Алексеем Червоненкисом -- алгоритм линейной классификации. Однако в 1992 году Бернхард Босер, Изабелл Гийон и Вапник предложили способ создания нелинейного классификатора, в основе которого лежит переход от скалярных произведений к произвольным ядрам, так называемый kernel trick (предложенный впервые М.А. Айзерманом, Э.М. Браверманном и Л.В. Розоноэром для метода потенциальных функций), позволяющий строить нелинейные разделители. Результирующий алгоритм крайне похож на алгоритм линейной классификации, с той лишь разницей, что каждое скалярное произведение в приведённых выше формулах заменяется нелинейной функцией ядра (скалярным произведением в пространстве с большей размерностью). В этом пространстве уже может существовать оптимальная разделяющая гиперплоскость. Так как размерность получаемого пространства может быть больше размерности исходного, то преобразование, сопоставляющее скалярные произведения, будет нелинейным, а значит функция, соответствующая в исходном пространстве оптимальной разделяющей гиперплоскости, будет также нелинейной.

    Стоит отметить, что если исходное пространство имеет достаточно высокую размерность, то можно надеяться, что в нём выборка окажется линейно разделимой.

    Наиболее распространённые ядра:

    1. Линейное ядро:

    2. Полиномиальное (однородное):

    3. RBF функция:

    4. Сигмоид:

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

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

    Стохастический Градиентный Спуск

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

    Найдём алгоритм, аппроксимирующий зависимость. В случае линейного классификатора искомый алгоритм имеет вид:

    где играет роль функции активации (в простейшем случае можно положить).

    Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу:

    Где - заданная функция потерь.

    Для минимизации применим метод градиентного спуска (gradient descent). Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):

    Где - положительный параметр, называемый темпом обучения (learning rate).

    Возможны 2 основных подхода к реализации градиентного спуска:

    1. Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется. Это требует больших вычислительных затрат.

    2. Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор настраивается на каждый вновь выбираемый объект.

    Можно представить алгоритм стохастического градиентного спуска в виде псевдокода следующим образом:

    · - обучающая выборка

    · - темп обучения

    · - параметр сглаживания функционала

    1. Вектор весов

    1) Инициализировать веса

    2) Инициализировать текущую оценку функционала:

    3) Повторять:

    1. Выбрать объект из случайным образом

    2. Вычислить выходное значение алгоритма и ошибку:

    3. Сделать шаг градиентного спуска

    4. Оценить значение функционала:

    4) Пока значение не стабилизируется и/или веса не перестанут изменяться.

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

    Выводы

    В рамках решаемой задачи нам потребуется воспользоваться алгоритмом преобразования исходных данных TF-IDF, который позволит нам повысить весомость редких событий и снизить вес частых событий. Полученные после преобразования данные мы будем передавать классификаторам, которые подходят для решения стоящей перед нами задачи, а именно: Наивный Байесовский Классификатор или Машина Опорных Векторов с Линейным ядром, обученная по методу стохастического градиентного спуска. Также мы осуществим проверку эффективности Машины Опорных Векторов с нелинейными ядрами, обученной по методу пакетного градиентного спуска. Однако, данный тип классификатора не кажется подходящим для поставленной задачи в силу слишком сложного ядра и склонности к переобучаемости, при которой классификатор плохо справляется с данными, которые не использовались для обучения классификатора.

    программный машинный предобработка данный

    Итак, у вас есть задача предсказать какое-то значение вроде стоимости дома по его размеру. Или время обработки какого-то запроса вашей системой. Да мало ли что.

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

    1. Batch Gradient Descent (общий градиентный спуск)
    2. Stochastic Gradient Descent (стохастический градиентный спуск)
    3. Normal Equations (нормальные уравнения)
    4. Newton’s Method (метод Ньютона)

    Сегодня мы поговорим о двух видах градиентного спуска.

    Gradient Descent

    Что вообще такое градиентный спуск?

    Представьте себе какую-то сложную функцию от одной переменной. У нее есть какие-то максимумы и минимумы. В каждой точке этой функции мы можем взять производную:

    Зеленая линия показывает, что в этой точке производная будет положительной, красная – отрицательной.

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

    Если же в вашей точке производная отрицательная (красная линия), это значит, что минимум находится «перед» вами, и чтобы прийти к нему, вам надо, снова-таки, отнять от координаты x значение вашей производной. Значение ее отрицательное, и потому, отнимая отрицательное значение, вы будете увеличивать координату x .

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

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

    Вы можете представить эту функцию как «чашку» в трехмерном пространстве:

    Производная функций от нескольких переменных называется градиентом. Градиент – это вектор размерностью в количество переменных, в котором каждый элемент вектора – производная от какой-то одной переменной.

    Наша функция стоимости имеет вид:

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

    В каждой частной производной мы считаем ее от какой-то одной переменной. Все прочие переменные считаем константами, следовательно, их производные будут равны нулю:

    После этого мы обновляем каждое значение по формуле:

    Параметр называется learning rate и определяет, насколько быстро мы будем двигаться к минимальному значению функции. С каждым обновлением параметров мы делаем маленький шаг в сторону минимума. После этого повторяем процедуру. Параллельно с этим смотрим, насколько изменилось значение функции стоимости сравнительно с предыдущим шагом. Когда это изменение становится очень маленьким (мы топчемся на месте), мы можем останавливаться и считать, что пришли в точку минимума.

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

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


    Здесь в скобках надо заметить, что вышеописанное касается градиентного спуска в общем виде, но не касается градиентного спуска конкретно для линейной регрессии. Функция стоимости линейной регрессии выпуклая и имеет только один минимум (вспомните трехмерную чашку), потому градиентный спуск всегда найдет его.

    Чем ближе вы подбираетесь к минимуму функции стоимости (чем меньше разница между предсказанной ценой и реальной), тем лучше ваша прямая описывает ваши исторические данные:

    Когда исторических примеров не много, все в порядке, но когда их миллионы, для каждого маленького шага к минимуму мы должны проделать миллионы вычислений, и это может занимать долгое время.

    Альтернативой этому может быть stochastic gradient descent – метод, при котором мы берем какой-то один пример и обновляем значения , ориентируясь только на него. Потом берем следующий пример и обновляем параметры, ориентируясь уже на него. И так далее. Это приводит к тому, что мы не всегда «спускаемся» с холма, иногда мы делаем и шаг вверх или в сторону, но рано или поздно мы достигаем того самого минимума и начинаем кружить вокруг него. Когда значения начинают нас устраивать (достигают нужной нам точности), мы останавливаем спуск.

    В псевдокоде stochastic gradient descent выглядит так:

    Until Cost Function change is small: {

    For j:= 1 to m {

    Напоследок, особенности схождения алгоритма: batch gradient descent всегда сходится к минимуму при условии, что используется достаточно маленькое значение . Stochastic gradient descent в общем виде не сходится к минимуму, но есть его модификации, которые позволяют добиться сходимости.

    Стохастический градиент оценивается по формуле :

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

    Если в качестве взять орты, т. то эта оценка при как легко заметить из (3.3.22), дает точное значение градиента.

    Обе описанные оценки градиента могут эффективно применяться при любых значениях в том числе и при что существенно отличает их от детерминированного способа оценивания (3.3.22), для которого строго Это же обстоятельство подтверждает, что детерминированные методы обобщаются случайными (см. конец подраздела 3.3.1). Приведем еще пример такого обобщения.

    Градиентный поиск (3.3.21) является частным случаем по крайней мере двух алгоритмов случайного поиска. Первый алгоритм:

    где - по-прежнему единичный случайный -мерный вектор. Это известный градиентный алгоритм случайного поиска . Второй алгоритм имеет вид (3.3.23), но оценка градиента вычисляется по формуле

    При как легко заметить, оба алгоритма вырождаются, в градиентный алгоритм поиска (3.3.21).

    Таким образом, случайный поиск является естественным расширением, продолжением и обобщением известных регулярных методов поиска.

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

    Так, алгоритм случайного поиска с линейной тактикой (3.3.12) является стохастической моделью алгоритма наискорейшего спуска:

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

    оператор случайного шага заменяет громоздкий оператор оценки градиента, например, по формуле (3.3.22).

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

    Следовательно, глобальность алгоритмов случайного поиска является как бы «премией» за использование случайности и чем-то вроде «бесплатного приложения» к алгоритму. Это обстоятельство особенно важно при оптимизации объектов с неизвестной структурой, когда нет полной уверенности в одноэкстремальности задачи и возможно (хотя и не ожидается) наличие нескольких экстремумов. Использование в таком случае методов глобального поиска было бы неразумной расточительностью. Методы локального случайного поиска здесь наиболее приемлемы, так как они эффективно решают локальную задачу и могут в принципе решить глобальную, если таковая будет иметь место. Это обеспечивает случайному поиску своеобразную психологическую надежность, которую очень ценят пользователи.

    Алгоритмическая простота случайного поиска делает его привлекательным в первую очередь для потребителей . Опыт показывает, что известные алгоритмы случайного поиска являются лишь «канвой», на которой пользователь в каждом конкретном случае «вышивает узоры» новых алгоритмов, отражающих не только его вкусы и наклонности (что нельзя не учитывать), но и специфику оптимизируемого объекта. Последнее создает благоприятную основу для реализации известного принципа, что алгоритм должен конструироваться «под объект». Наконец, алгоритмическая простота случайного поиска обусловливает простоту его аппаратурной реализации. Это не только дает возможность строить простые, компактные и надежные оптимизаторы с неограниченным числом оптимизируемых параметров , но и позволяет довольно просто организовать их оптимальный синтез на ЭВМ .

    Читать еще: