Участник:Ruzik/Песочница

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 24: Строка 24:
Возможно 2 основных подхода к реализации градиентного спуска:
Возможно 2 основных подхода к реализации градиентного спуска:
-
* ''Пакетный (batch)'', когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется <tex>w</tex>. Это требует больших вычислительных затрат.
+
*''Пакетный (batch)'', когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется <tex>w</tex>. Это требует больших вычислительных затрат.
-
* ''Стохастический (stochastic/online)'', когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
+
*''Стохастический (stochastic/online)'', когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
==Алгоритм Stochastic Gradient (SG)==
==Алгоритм Stochastic Gradient (SG)==
'''Вход:'''
'''Вход:'''
-
* <tex>X^l</tex> - обучающая выборка <br />
+
*<tex>X^l</tex> - обучающая выборка <br />
-
* <tex>\eta</tex> - темп обучения <br />
+
*<tex>\eta</tex> - темп обучения <br />
-
* <tex>\lambda</tex> - параметр сглаживания функционала <tex>Q</tex> <br />
+
*<tex>\lambda</tex> - параметр сглаживания функционала <tex>Q</tex> <br />
'''Выход:'''
'''Выход:'''
-
* Вектор весов <tex>w</tex> <br />
+
*Вектор весов <tex>w</tex> <br />
'''Тело:'''
'''Тело:'''
#Инициализировать веса <tex>w_j \; j = 0, \dots, n</tex>;
#Инициализировать веса <tex>w_j \; j = 0, \dots, n</tex>;
Строка 39: Строка 39:
#:: <tex>Q \, {:=} \, \sum_{i=1}^l L(a(x_i, w), \, y_i)</tex>;
#:: <tex>Q \, {:=} \, \sum_{i=1}^l L(a(x_i, w), \, y_i)</tex>;
#Повторять:
#Повторять:
-
## Выбрать объект <tex>x_i</tex> из <tex>X^l</tex> (например, случайным образом);
+
##Выбрать объект <tex>x_i</tex> из <tex>X^l</tex> (например, случайным образом);
-
## Вычислить выходное значение алгоритма <tex>a(x_i, w)</tex> и ошибку:
+
##Вычислить выходное значение алгоритма <tex>a(x_i, w)</tex> и ошибку:
-
##:: <tex>\varepsilon_i \, {:=} \, L(a(x_i, w), \, y_i)</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>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 \, {:=} \, (1 \, - \, \lambda)Q \, + \, \lambda\varepsilon_i</tex>;
#Пока значение <tex>Q</tex> не стабилизируется и/или веса <tex>w</tex> не перестанут изменяться.
#Пока значение <tex>Q</tex> не стабилизируется и/или веса <tex>w</tex> не перестанут изменяться.
===Порядок выбора объектов===
===Порядок выбора объектов===
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
-
* ''Перемешивание (shuffling).'' Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор <tex>w</tex> будет каждый раз сильнее изменяться.
+
*''Перемешивание (shuffling).'' Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор <tex>w</tex> будет каждый раз сильнее изменяться.
-
* Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
+
*Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
===Способы инициализации весов===
===Способы инициализации весов===
-
* Инициализировать вектор <tex>w</tex> нулями. Этот способ используется очень во многих системах, но совсем не всегда является удачным.
+
*Инициализировать вектор <tex>w</tex> нулями. Этот способ используется очень во многих системах, но совсем не всегда является удачным.
-
* <tex>w_j {:=} rand(-\frac{1}{n}, \frac{1}{n})</tex>, где <tex>n</tex> - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. ниже.)
+
*<tex>w_j {:=} rand(-\frac{1}{n}, \frac{1}{n})</tex>, где <tex>n</tex> - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. ниже.)
-
* Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (<tex>\varphi</tex>) и квадратичной функции потерь (<tex>L</tex>). Тогда решение имеет вид:
+
*Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (<tex>\varphi</tex>) и квадратичной функции потерь (<tex>L</tex>). Тогда решение имеет вид:
:: <tex>w_j \, {:=} \, \frac{<y, f_j>}{<f_j, f_j>}</tex>.
:: <tex>w_j \, {:=} \, \frac{<y, f_j>}{<f_j, f_j>}</tex>.
Строка 68: Строка 68:
#Алгоритм k-средних (K-Means);
#Алгоритм k-средних (K-Means);
#Learning Vector Quantization (LVQ).
#Learning Vector Quantization (LVQ).
 +
 +
==Преимущества SG==
 +
* Метод приспособлен для динамического (online)обучения, когда обучающие объекты поступают потоком, и надо постоянно быстро обновлять вектор <tex>w</tex>.
 +
* Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
 +
*

Версия 14:27, 3 января 2010

y^*: \: X \to Y
X^l \, = \, (x_i,y_i)_{i=1}^l, \; y_i \, = \, y^*(x_i)
Q(w) \, = \, \sum_{i=1}^l L(a(x_i, w), \, y_i) \to \min_w
w \, {:=} \, w \, - \, \eta \nabla Q(w)
w \, {:=} \, w \, - \, \eta \sum_{i=1}^l L_a^\prime (a(x_i, w), \, y_i) \varphi^\prime (<w, x_i>)x_i
w_j \, {:=} \, \frac{<y, f_i>}{<f_i, f_j>}
x^j \, {:=} \, \frac{x^j \, - \, x_{\min}^j}{x_{\max}^j \, - \, x_{\min}^j}
w

Содержание

Метод стохастического градиента (Stochastic Gradient)

Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов 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) - заданная функция потерь.

Для минимизации применим метод градиентного спуска. Это пошаговый алгоритм, на каждой итерации которого вектор 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 - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. ниже.)
  • Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (\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.
  • Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
Личные инструменты