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

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

< Участник:Ruzik(Различия между версиями)

Текущая версия

Содержание

1 Основная идея
2 Алгоритм Stochastic Gradient (SG)
3 Преимущества SG
4 Недостатки SG и способы борьбы с ними
5 Сходимость алгоритма
6 Литература

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

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

Тело:

Инициализировать веса $w_j \; j = 0, \dots, n$ ;
Инициализировать текущую оценку функционала:
$Q \, {:=} \, \sum_{i=1}^l L(a(x_i, w), \, y_i)$ ;
Повторять:
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$ ;
Пока значение $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$ и алгоритмов классификации:

Адаптивный линейный элемент (Adalines);
Правило Хэбба;
Алгоритм k-средних (K-Means);
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-х условий:

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

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

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Ruzik/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 1: / Строка 1: @@
-<tex>y^*: \: X \to Y</tex> <br />
+==Основная идея==
-<tex>X^l \, = \, (x_i,y_i)_{i=1}^l, \; y_i \, = \, y^*(x_i)</tex> <br />
-<tex>Q(w) \, = \, \sum_{i=1}^l L(a(x_i, w), \, y_i) \to \min_w</tex> <br />
-<tex>w \, {:=} \, w \, - \, \eta \nabla Q(w)</tex> <br />
-<tex>w \, {:=} \, w \, - \, \eta \sum_{i=1}^l L_a^\prime (a(x_i, w), \, y_i) \varphi^\prime (<w, x_i>)x_i</tex> <br />
-<tex>w_j \, {:=} \, \frac{<y, f_i>}{<f_i, f_j>}</tex> <br />
-<tex>x^j \, {:=} \, \frac{x^j \, - \, x_{\min}^j}{x_{\max}^j \, - \, x_{\min}^j}</tex> <br />
-<tex>w</tex>
-==Метод стохастического градиента (Stochastic Gradient)==
 ''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.
-Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов <tex>w</tex> в линейном классификаторе (ссылка).
+Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов <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>.
@@ Строка 19: / Строка 10: @@
 где <tex>L(a,y)</tex> - заданная функция потерь.
-Для минимизации применим метод градиентного спуска. Это пошаговый алгоритм, на каждой итерации которого вектор <tex>w</tex> изменяется в направлении наибольшего убывания функционала <tex>Q</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>. Это требует больших вычислительных затрат.
+*''Пакетный (batch)'', когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется <tex>w</tex>. Это требует больших вычислительных затрат.
-* ''Стохастический (stochastic/online)'', когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
+*''Стохастический (stochastic/online)'', когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
 ==Алгоритм 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>;
@@ Строка 39: / Строка 30: @@
 #:: <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> не перестанут изменяться.
 ===Порядок выбора объектов===
 Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
-* ''Перемешивание (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> - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. "Недостатки 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]