Участник: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
Метод стохастического градиента (Stochastic Gradient)
Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе (ссылка). Пусть - целевая зависимость, известная только на объектах обучающей выборки: .
Найдём алгоритм , аппроксимирующий зависимость . Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу: , где - заданная функция потерь.
Для минимизации применим метод градиентного спуска. Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):
- ,
где - положительный параметр, называемый темпом обучения (learning rate).
Возможно 2 основных подхода к реализации градиентного спуска:
- Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется . Это требует больших вычислительных затрат.
- Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
Алгоритм Stochastic Gradient (SG)
Вход:
- - обучающая выборка
- - темп обучения
- - параметр сглаживания функционала
Выход:
- Вектор весов
Тело:
- Инициализировать веса ;
- Инициализировать текущую оценку функционала:
- ;
- Повторять:
- Выбрать объект из (например, случайным образом);
- Вычислить выходное значение алгоритма и ошибку:
- ;
- Сделать шаг градиентного спуска:
- ;
- Оценить значение функционала:
- ;
- Пока значение не стабилизируется и/или веса не перестанут изменяться.