Участник:Ruzik/Песочница
Материал из MachineLearning.
Содержание |
Основная идея
Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе (ссылка). Пусть - целевая зависимость, известная только на объектах обучающей выборки: .
Найдём алгоритм , аппроксимирующий зависимость . Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу: , где - заданная функция потерь.
Для минимизации применим метод градиентного спуска (gradient descent). Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):
- ,
где - положительный параметр, называемый темпом обучения (learning rate).
Возможно 2 основных подхода к реализации градиентного спуска:
- Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется . Это требует больших вычислительных затрат.
- Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
Алгоритм Stochastic Gradient (SG)
Вход:
- - обучающая выборка
- - темп обучения
- - параметр сглаживания функционала
Выход:
- Вектор весов
Тело:
- Инициализировать веса ;
- Инициализировать текущую оценку функционала:
- ;
- Повторять:
- Выбрать объект из (например, случайным образом);
- Вычислить выходное значение алгоритма и ошибку:
- ;
- Сделать шаг градиентного спуска:
- ;
- Оценить значение функционала:
- ;
- Пока значение не стабилизируется и/или веса не перестанут изменяться.
Порядок выбора объектов
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
- Перемешивание (shuffling). Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор будет каждый раз сильнее изменяться.
- Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
Способы инициализации весов
- Инициализировать вектор нулями. Этот способ используется очень во многих системах, но совсем не всегда является удачным.
- , где - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. ниже.)
- Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации () и квадратичной функции потерь (). Тогда решение имеет вид:
- .
Параметр сглаживания
В алгоритме для оценки функционала на каждой итерации используется его приближённое значение по методу экспоненциального сглаживания, откуда лучше брать порядка . Если длина выборки избыточно большая, то следует увеличивать.
Известные частные случаи алгоритма
Метод SG (при соответствующем выборе функций активации и потерь) является обобщением следующих широко распространённых эвристик подбора и алгоритмов классификации:
- Адаптивный линейный элемент (Adalines);
- Правило Хэбба;
- Алгоритм k-средних (K-Means);
- Learning Vector Quantization (LVQ).
Преимущества SG
- Метод приспособлен для динамического (online) обучения, когда обучающие объекты поступают потоком, и надо быстро обновлять вектор .
- Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
- Возможны различные стратегии обучения. Если выборка избыточно большая, или обучение происходит динамически, то допустимо не сохранять обучающие объекты. Если выборка маленькая, то можно повторно предявлять для обучения одни и те же объекты.
Недостатки SG и способы борьбы с ними
- Алгоритм может не сходиться или сходиться слишком медленно (см. ниже.)
- Как правило, функционал многоэкстремален и процесс градиентного спуска может "застрять" в одном из локальных минимумов. Для борьбы с этим используют технику встряхивания коэффициентов (jog of weights). Она заключается в том, чтобы при каждой стабилизации функционала производить случайные модификации вектора в довольно большой окрестности текущего значения и запускать процесс градиентного спуска из новых точек.
- При большой размерности пространства признаков и/или малой длине выборки возможно переобучение, то есть классификация становится неустойчивой, и вероятность ошибки увеличивается. При этом сильно возрастает норма вектора весов. Для борьбы с данным недостатком используют метод сокращения весов (weights decay). Он заключается в том, чтобы ограничить возможный рост нормы , добавив к штрафное слагаемое: . В результате правило обновления весов принимает вид:
- .
- Если функция активации имеет горизонтальные асимптоты, то процесс может попасть в состояние "паралича". При больших значениях скалярного произведения значение становится близким к нулю и вектор перестаёт существенно изменяться. Поэтому общей практикой является предварительная нормализация признаков:
- , где - соответственно минимальное и максимальное отклонения j-го признака. Если при этом , то
Сходимость алгоритма
Как уже было сказано, сходимость в общем случае не гарантируется, однако установлено, что в случае выпуклой функции и при выполненении следующих 3-х условий:
- ;
- ;
процесс градиентного спуска будет сходиться. Например, можно положить: . Однако, как показывает практика, это не очень удачный способ.