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

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

Версия от 12:43, 3 января 2010; Ruzik (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

$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}$

Метод стохастического градиента (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$

Тело:

Инициализировать веса $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$ ;
Пока