Метод стохастического градиента

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
==Основная идея==
 +
''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.
 +
Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов <tex>w</tex> в [[Линейный классификатор | линейном классификаторе]].
 +
Пусть <tex>y^*: \: X \to Y</tex> - целевая зависимость, известная только на объектах обучающей выборки:
 +
<tex>X^l \, = \, (x_i,y_i)_{i=1}^l, \; y_i \, = \, y^*(x_i)</tex>.
 +
 +
Найдём алгоритм <tex>a(x, w)</tex>, аппроксимирующий зависимость <tex>y^*</tex>.
 +
Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу:
 +
<tex>Q(w) \, = \, \sum_{i=1}^l L(a(x_i, w), \, y_i) \to \min_w</tex>,
 +
где <tex>L(a,y)</tex> - заданная функция потерь.
 +
 +
Для минимизации применим метод ''градиентного спуска (gradient descent)''. Это пошаговый алгоритм, на каждой итерации которого вектор <tex>w</tex> изменяется в направлении наибольшего убывания функционала <tex>Q</tex> (то есть в направлении антиградиента):
 +
::<tex>w \, {:=} \, w \, - \, \eta \nabla Q(w)</tex>,
 +
где <tex>\eta</tex> - положительный параметр, называемый ''темпом обучения (learning rate)''.
 +
 +
Возможно 2 основных подхода к реализации градиентного спуска:
 +
*''Пакетный (batch)'', когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется <tex>w</tex>. Это требует больших вычислительных затрат.
 +
*''Стохастический (stochastic/online)'', когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
 +
 +
==Алгоритм Stochastic Gradient (SG)==
 +
'''Вход:'''
 +
*<tex>X^l</tex> - обучающая выборка <br />
 +
*<tex>\eta</tex> - темп обучения <br />
 +
*<tex>\lambda</tex> - параметр сглаживания функционала <tex>Q</tex> <br />
 +
'''Выход:'''
 +
*Вектор весов <tex>w</tex> <br />
 +
'''Тело:'''
 +
#Инициализировать веса <tex>w_j \; j = 0, \dots, n</tex>;
 +
#Инициализировать текущую оценку функционала:
 +
#:: <tex>Q \, {:=} \, \sum_{i=1}^l L(a(x_i, w), \, y_i)</tex>;
 +
#Повторять:
 +
##Выбрать объект <tex>x_i</tex> из <tex>X^l</tex> (например, случайным образом);
 +
##Вычислить выходное значение алгоритма <tex>a(x_i, w)</tex> и ошибку:
 +
##::<tex>\varepsilon_i \, {:=} \, L(a(x_i, w), \, y_i)</tex>;
 +
##Сделать шаг градиентного спуска:
 +
##::<tex>w \, {:=} \, w \, - \, \eta L_a^\prime (a(x_i, w), \, y_i) \varphi^\prime (<w, x_i>)x_i</tex>;
 +
## Оценить значение функционала:
 +
##::<tex>Q \, {:=} \, (1 \, - \, \lambda)Q \, + \, \lambda\varepsilon_i</tex>;
 +
#Пока значение <tex>Q</tex> не стабилизируется и/или веса <tex>w</tex> не перестанут изменяться.
 +
 +
===Порядок выбора объектов===
 +
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
 +
*''Перемешивание (shuffling).'' Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор <tex>w</tex> будет каждый раз сильнее изменяться.
 +
*Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
 +
 +
===Способы инициализации весов===
 +
*Инициализировать вектор <tex>w</tex> нулями. Этот способ используется во многих системах, но совсем не всегда является лучшим.
 +
*<tex>w_j {:=} rand(-\frac{1}{n}, \frac{1}{n})</tex>, где <tex>n</tex> - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. "Недостатки SG и способы борьбы с ними".)
 +
*Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (<tex>\varphi</tex>) и квадратичной функции потерь (<tex>L</tex>). Тогда решение имеет вид:
 +
:: <tex>w_j \, {:=} \, \frac{<y, f_j>}{<f_j, f_j>}</tex>.
 +
 +
===Параметр сглаживания===
 +
В алгоритме для оценки функционала <tex>Q</tex> на каждой итерации используется его приближённое значение по методу экспоненциального сглаживания, откуда <tex>\lambda</tex> лучше брать порядка <tex>\frac{1}{l}</tex>. Если длина выборки избыточно большая, то <tex>\lambda</tex> следует увеличивать.
 +
 +
===Известные частные случаи алгоритма===
 +
Метод SG (при соответствующем выборе функций активации и потерь) является обобщением следующих широко распространённых эвристик подбора <tex>w</tex> и алгоритмов классификации:
 +
#Адаптивный линейный элемент (Adalines);
 +
#Правило Хэбба;
 +
#Алгоритм k-средних (K-Means);
 +
#Learning Vector Quantization (LVQ).
 +
 +
==Преимущества SG==
 +
*Метод приспособлен для динамического (online) обучения, когда обучающие объекты поступают потоком, и надо быстро обновлять вектор <tex>w</tex>.
 +
*Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
 +
*Возможны различные стратегии обучения. Если выборка избыточно большая, или обучение происходит динамически, то допустимо не сохранять обучающие объекты. Если выборка маленькая, то можно повторно предявлять для обучения одни и те же объекты.
 +
 +
==Недостатки SG и способы борьбы с ними==
 +
*Алгоритм может не сходиться или сходиться слишком медленно (см. "Сходимость алгоритма".)
 +
*Как правило, функционал <tex>Q</tex> многоэкстремален и процесс градиентного спуска может "застрять" в одном из локальных минимумов. Для борьбы с этим используют технику ''встряхивания коэффициентов (jog of weights)''. Она заключается в том, чтобы при каждой стабилизации функционала производить случайные модификации вектора <tex>w</tex> в довольно большой окрестности текущего значения и запускать процесс градиентного спуска из новых точек.
 +
*При большой размерности пространства признаков <tex>n</tex> и/или малой длине выборки <tex>l</tex> возможно переобучение, то есть классификация становится неустойчивой, и вероятность ошибки увеличивается. При этом сильно возрастает норма вектора весов. Для борьбы с данным недостатком используют метод ''сокращения весов (weights decay)''. Он заключается в том, чтобы ограничить возможный рост нормы <tex>w</tex>, добавив к <tex>Q(w)</tex> штрафное слагаемое: <tex>Q_{\tau}(w) \, = \, Q(w) \, + \, \frac{\tau}{2}||w||^2</tex>. В результате правило обновления весов принимает вид:
 +
::<tex>w \, {:=} \, w(1 \, - \, \eta \tau) \, - \, \eta \nabla Q(w)</tex>.
 +
*Если функция активации имеет горизонтальные асимптоты, то процесс может попасть в состояние "паралича". При больших значениях скалярного произведения <tex><w, x_i></tex> значение <tex>\varphi^\prime</tex> становится близким к нулю и вектор <tex>w</tex> перестаёт существенно изменяться. Поэтому общей практикой является предварительная нормализация признаков:
 +
::<tex>x^j \, {:=} \, \frac{x^j \, - \, x_{\min}^j}{x_{\max}^j \, - \, x_{\min}^j}, \; j = 1, \dots, n</tex>, где <tex>x_{\min}^j, \, x_{\max}^j</tex> - соответственно минимальное и максимальное отклонения j-го признака. Если при этом <tex>w_j = rand(-\frac{1}{n}, \frac{1}{n})</tex>, то <tex><w, x> \in [-1,1].</tex>
 +
 +
==Сходимость алгоритма==
 +
Как уже было сказано, сходимость в общем случае не гарантируется, однако установлено, что в случае выпуклой функции <tex>Q(w)</tex> и при выполненении следующих 3-х условий:
 +
#<tex>\eta_t \to^{t \to \infty} 0</tex>;
 +
#<tex>\sum_{t=1}^{\infty} \eta_t \, = \, \infty</tex>;
 +
#<tex>\sum_{t=1}^{\infty} \eta_t^2 \, < \, \infty</tex>
 +
процесс градиентного спуска будет сходиться. Например, можно положить: <tex>\eta_t \, = \, \frac{\eta_0}{t}</tex>. Однако, как показывает практика, это не очень удачный способ.
 +
 +
==Литература==
 +
#[[Машинное обучение (курс лекций, К.В.Воронцов)]]
 +
#[http://leon.bottou.org/papers/bottou-mlss-2004 Stochastic Learning]
 +
 +
 +
[[Категория:Классификация]]
 +
[[Категория:Машинное обучение]]
 +
{{Задание|Ruzik|Константин Воронцов|8 января 2009}}
{{Задание|Ruzik|Константин Воронцов|8 января 2009}}

Версия 17:09, 3 января 2010

Содержание

Основная идея

Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов w в линейном классификаторе. Пусть y^*: \: X \to Y - целевая зависимость, известная только на объектах обучающей выборки: X^l \, = \, (x_i,y_i)_{i=1}^l, \; y_i \, = \, y^*(x_i).

Найдём алгоритм a(x, w), аппроксимирующий зависимость y^*. Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу: Q(w) \, = \, \sum_{i=1}^l L(a(x_i, w), \, y_i) \to \min_w, где L(a,y) - заданная функция потерь.

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

w \, {:=} \, w \, - \, \eta \nabla Q(w),

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

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

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

Алгоритм Stochastic Gradient (SG)

Вход:

  • X^l - обучающая выборка
  • \eta - темп обучения
  • \lambda - параметр сглаживания функционала Q

Выход:

  • Вектор весов w

Тело:

  1. Инициализировать веса w_j \; j = 0, \dots, n;
  2. Инициализировать текущую оценку функционала:
    Q \, {:=} \, \sum_{i=1}^l L(a(x_i, w), \, y_i);
  3. Повторять:
    1. Выбрать объект x_i из X^l (например, случайным образом);
    2. Вычислить выходное значение алгоритма a(x_i, w) и ошибку:
      \varepsilon_i \, {:=} \, L(a(x_i, w), \, y_i);
    3. Сделать шаг градиентного спуска:
      w \, {:=} \, w \, - \, \eta L_a^\prime (a(x_i, w), \, y_i) \varphi^\prime (<w, x_i>)x_i;
    4. Оценить значение функционала:
      Q \, {:=} \, (1 \, - \, \lambda)Q \, + \, \lambda\varepsilon_i;
  4. Пока значение Q не стабилизируется и/или веса w не перестанут изменяться.

Порядок выбора объектов

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

  • Перемешивание (shuffling). Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор w будет каждый раз сильнее изменяться.
  • Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.

Способы инициализации весов

  • Инициализировать вектор w нулями. Этот способ используется во многих системах, но совсем не всегда является лучшим.
  • w_j {:=} rand(-\frac{1}{n}, \frac{1}{n}), где n - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. "Недостатки SG и способы борьбы с ними".)
  • Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (\varphi) и квадратичной функции потерь (L). Тогда решение имеет вид:
w_j \, {:=} \, \frac{<y, f_j>}{<f_j, f_j>}.

Параметр сглаживания

В алгоритме для оценки функционала Q на каждой итерации используется его приближённое значение по методу экспоненциального сглаживания, откуда \lambda лучше брать порядка \frac{1}{l}. Если длина выборки избыточно большая, то \lambda следует увеличивать.

Известные частные случаи алгоритма

Метод SG (при соответствующем выборе функций активации и потерь) является обобщением следующих широко распространённых эвристик подбора w и алгоритмов классификации:

  1. Адаптивный линейный элемент (Adalines);
  2. Правило Хэбба;
  3. Алгоритм k-средних (K-Means);
  4. Learning Vector Quantization (LVQ).

Преимущества SG

  • Метод приспособлен для динамического (online) обучения, когда обучающие объекты поступают потоком, и надо быстро обновлять вектор w.
  • Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
  • Возможны различные стратегии обучения. Если выборка избыточно большая, или обучение происходит динамически, то допустимо не сохранять обучающие объекты. Если выборка маленькая, то можно повторно предявлять для обучения одни и те же объекты.

Недостатки SG и способы борьбы с ними

  • Алгоритм может не сходиться или сходиться слишком медленно (см. "Сходимость алгоритма".)
  • Как правило, функционал Q многоэкстремален и процесс градиентного спуска может "застрять" в одном из локальных минимумов. Для борьбы с этим используют технику встряхивания коэффициентов (jog of weights). Она заключается в том, чтобы при каждой стабилизации функционала производить случайные модификации вектора w в довольно большой окрестности текущего значения и запускать процесс градиентного спуска из новых точек.
  • При большой размерности пространства признаков n и/или малой длине выборки l возможно переобучение, то есть классификация становится неустойчивой, и вероятность ошибки увеличивается. При этом сильно возрастает норма вектора весов. Для борьбы с данным недостатком используют метод сокращения весов (weights decay). Он заключается в том, чтобы ограничить возможный рост нормы w, добавив к Q(w) штрафное слагаемое: Q_{\tau}(w) \, = \, Q(w) \, + \, \frac{\tau}{2}||w||^2. В результате правило обновления весов принимает вид:
w \, {:=} \, w(1 \, - \, \eta \tau) \, - \, \eta \nabla Q(w).
  • Если функция активации имеет горизонтальные асимптоты, то процесс может попасть в состояние "паралича". При больших значениях скалярного произведения <w, x_i> значение \varphi^\prime становится близким к нулю и вектор w перестаёт существенно изменяться. Поэтому общей практикой является предварительная нормализация признаков:
x^j \, {:=} \, \frac{x^j \, - \, x_{\min}^j}{x_{\max}^j \, - \, x_{\min}^j}, \; j = 1, \dots, n, где x_{\min}^j, \, x_{\max}^j - соответственно минимальное и максимальное отклонения j-го признака. Если при этом w_j = rand(-\frac{1}{n}, \frac{1}{n}), то <w, x> \in [-1,1].

Сходимость алгоритма

Как уже было сказано, сходимость в общем случае не гарантируется, однако установлено, что в случае выпуклой функции Q(w) и при выполненении следующих 3-х условий:

  1. \eta_t \to^{t \to \infty} 0;
  2. \sum_{t=1}^{\infty} \eta_t \, = \, \infty;
  3. \sum_{t=1}^{\infty} \eta_t^2 \, < \, \infty

процесс градиентного спуска будет сходиться. Например, можно положить: \eta_t \, = \, \frac{\eta_0}{t}. Однако, как показывает практика, это не очень удачный способ.

Литература

  1. Машинное обучение (курс лекций, К.В.Воронцов)
  2. Stochastic Learning


Данная статья является непроверенным учебным заданием.
Студент: Участник:Ruzik
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%81%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B3%D0%BE_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%B0»
Личные инструменты