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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 6: Строка 6:
<tex>w_j \, {:=} \, \frac{<y, f_i>}{<f_i, f_j>}</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>x^j \, {:=} \, \frac{x^j \, - \, x_{\min}^j}{x_{\max}^j \, - \, x_{\min}^j}</tex> <br />
 +
<tex>w</tex>
 +
==Метод стохастического градиента (Stochastic Gradient)==
==Метод стохастического градиента (Stochastic Gradient)==
''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.
''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.
Строка 36: Строка 38:
#Инициализировать текущую оценку функционала:
#Инициализировать текущую оценку функционала:
#:: <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> и ошибку:
Строка 44: Строка 46:
## Оценить значение функционала:
## Оценить значение функционала:
##:: <tex>Q \, {:=} \, (1 \, - \, \lambda)Q \, + \, \lambda\varepsilon_i</tex>;
##:: <tex>Q \, {:=} \, (1 \, - \, \lambda)Q \, + \, \lambda\varepsilon_i</tex>;
-
#Пока
+
#Пока значение <tex>Q</tex> не стабилизируется и/или веса <tex>w</tex> не перестанут изменяться.

Версия 12:46, 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 не перестанут изменяться.
Источник — «http://www.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»
Личные инструменты