Участник:Ruzik/Песочница
Материал из MachineLearning.
м (декатегоризация) |
|||
(37 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
- | + | ==Основная идея== | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | + | ||
''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. | ''Градиентные методы'' - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. | ||
- | Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов <tex>w</tex> в линейном классификаторе | + | Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов <tex>w</tex> в [[Линейный классификатор | линейном классификаторе]]. |
Пусть <tex>y^*: \: X \to Y</tex> - целевая зависимость, известная только на объектах обучающей выборки: | Пусть <tex>y^*: \: X \to Y</tex> - целевая зависимость, известная только на объектах обучающей выборки: | ||
<tex>X^l \, = \, (x_i,y_i)_{i=1}^l, \; y_i \, = \, y^*(x_i)</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>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>w \, {:=} \, w \, - \, \eta \nabla Q(w)</tex>, | ||
где <tex>\eta</tex> - положительный параметр, называемый ''темпом обучения (learning rate)''. | где <tex>\eta</tex> - положительный параметр, называемый ''темпом обучения (learning rate)''. | ||
Возможно 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: | Строка 30: | ||
#:: <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> - размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. "Недостатки SG и способы борьбы с ними".) |
- | * Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (<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>. | ||
===Параметр сглаживания=== | ===Параметр сглаживания=== | ||
- | В алгоритме для оценки функционала <tex>Q</tex> на каждой итерации используется его приближённое значение по методу экспоненциального сглаживания, откуда <tex>\lambda</tex> лучше брать <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] |
Текущая версия
Содержание |
Основная идея
Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.
Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе.
Пусть
- целевая зависимость, известная только на объектах обучающей выборки:
.
Найдём алгоритм , аппроксимирующий зависимость
.
Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу:
,
где
- заданная функция потерь.
Для минимизации применим метод градиентного спуска (gradient descent). Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала
(то есть в направлении антиградиента):
,
где - положительный параметр, называемый темпом обучения (learning rate).
Возможно 2 основных подхода к реализации градиентного спуска:
- Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется
. Это требует больших вычислительных затрат.
- Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
Алгоритм Stochastic Gradient (SG)
Вход:
- обучающая выборка
- темп обучения
- параметр сглаживания функционала
Выход:
- Вектор весов
Тело:
- Инициализировать веса
;
- Инициализировать текущую оценку функционала:
-
;
-
- Повторять:
- Выбрать объект
из
(например, случайным образом);
- Вычислить выходное значение алгоритма
и ошибку:
;
- Сделать шаг градиентного спуска:
;
- Оценить значение функционала:
;
- Выбрать объект
- Пока значение
не стабилизируется и/или веса
не перестанут изменяться.
Порядок выбора объектов
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
- Перемешивание (shuffling). Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор
будет каждый раз сильнее изменяться.
- Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
Способы инициализации весов
- Инициализировать вектор
нулями. Этот способ используется во многих системах, но совсем не всегда является лучшим.
, где
- размерность пространства признаков. Этот подход существенно более удачен, чем предыдущий, если соответствующим образом нормализовать признаковое описание (см. "Недостатки SG и способы борьбы с ними".)
- Ещё один подход заключается в том, чтобы решить исходную оптимизационную задачу в случае статистически независимых признаков, линейной функции активации (
) и квадратичной функции потерь (
). Тогда решение имеет вид:
-
.
-
Параметр сглаживания
В алгоритме для оценки функционала на каждой итерации используется его приближённое значение по методу экспоненциального сглаживания, откуда
лучше брать порядка
. Если длина выборки избыточно большая, то
следует увеличивать.
Известные частные случаи алгоритма
Метод SG (при соответствующем выборе функций активации и потерь) является обобщением следующих широко распространённых эвристик подбора и алгоритмов классификации:
- Адаптивный линейный элемент (Adalines);
- Правило Хэбба;
- Алгоритм k-средних (K-Means);
- Learning Vector Quantization (LVQ).
Преимущества SG
- Метод приспособлен для динамического (online) обучения, когда обучающие объекты поступают потоком, и надо быстро обновлять вектор
.
- Алгоритм способен обучаться на избыточно больших выборках за счёт того, что случайной подвыборки может хватить для обучения.
- Возможны различные стратегии обучения. Если выборка избыточно большая, или обучение происходит динамически, то допустимо не сохранять обучающие объекты. Если выборка маленькая, то можно повторно предявлять для обучения одни и те же объекты.
Недостатки SG и способы борьбы с ними
- Алгоритм может не сходиться или сходиться слишком медленно (см. "Сходимость алгоритма".)
- Как правило, функционал
многоэкстремален и процесс градиентного спуска может "застрять" в одном из локальных минимумов. Для борьбы с этим используют технику встряхивания коэффициентов (jog of weights). Она заключается в том, чтобы при каждой стабилизации функционала производить случайные модификации вектора
в довольно большой окрестности текущего значения и запускать процесс градиентного спуска из новых точек.
- При большой размерности пространства признаков
и/или малой длине выборки
возможно переобучение, то есть классификация становится неустойчивой, и вероятность ошибки увеличивается. При этом сильно возрастает норма вектора весов. Для борьбы с данным недостатком используют метод сокращения весов (weights decay). Он заключается в том, чтобы ограничить возможный рост нормы
, добавив к
штрафное слагаемое:
. В результате правило обновления весов принимает вид:
.
- Если функция активации имеет горизонтальные асимптоты, то процесс может попасть в состояние "паралича". При больших значениях скалярного произведения
значение
становится близким к нулю и вектор
перестаёт существенно изменяться. Поэтому общей практикой является предварительная нормализация признаков:
, где
- соответственно минимальное и максимальное отклонения j-го признака. Если при этом
, то
Сходимость алгоритма
Как уже было сказано, сходимость в общем случае не гарантируется, однако установлено, что в случае выпуклой функции и при выполненении следующих 3-х условий:
;
;
процесс градиентного спуска будет сходиться. Например, можно положить: . Однако, как показывает практика, это не очень удачный способ.