Участник:Ruzik/Песочница
Материал из MachineLearning.
Строка 51: | Строка 51: | ||
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор: | Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор: | ||
* ''Перемешивание (shuffling).'' Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор <tex>w</tex> будет каждый раз сильнее изменяться. | * ''Перемешивание (shuffling).'' Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор <tex>w</tex> будет каждый раз сильнее изменяться. | ||
- | * Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой | + | * Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам. |
+ | |||
+ | ===Способы инициализации весов=== | ||
+ | * Инициализировать вектор <tex>w</tex> нулями. Этот способ используется очень во многих системах, но совсем не всегда является удачным. | ||
+ | * <tex>w_j {:=} rand(-\frac{1}{n}, \frac{1}{n})</tex>, где <tex>n</tex> - размерность пространства признаков. |
Версия 13:35, 3 января 2010
Содержание |
Метод стохастического градиента (Stochastic Gradient)
Градиентные методы - это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении. Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе (ссылка). Пусть - целевая зависимость, известная только на объектах обучающей выборки: .
Найдём алгоритм , аппроксимирующий зависимость . Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу: , где - заданная функция потерь.
Для минимизации применим метод градиентного спуска. Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):
- ,
где - положительный параметр, называемый темпом обучения (learning rate).
Возможно 2 основных подхода к реализации градиентного спуска:
- Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется . Это требует больших вычислительных затрат.
- Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор w настраивается на каждый вновь выбираемый объект.
Алгоритм Stochastic Gradient (SG)
Вход:
- - обучающая выборка
- - темп обучения
- - параметр сглаживания функционала
Выход:
- Вектор весов
Тело:
- Инициализировать веса ;
- Инициализировать текущую оценку функционала:
- ;
- Повторять:
- Выбрать объект из (например, случайным образом);
- Вычислить выходное значение алгоритма и ошибку:
- ;
- Сделать шаг градиентного спуска:
- ;
- Оценить значение функционала:
- ;
- Пока значение не стабилизируется и/или веса не перестанут изменяться.
Порядок выбора объектов
Выше сказано, что в случае стохастического градиентного спуска объекты следует выбирать случайным образом. Однако существуют эвристики, направленные на улучшение сходимости, которые слегка модифицируют обычный случайный выбор:
- Перемешивание (shuffling). Предлагается случайно выбирать объекты, но попеременно из разных классов. Идея в том, что объекты из разных классов скорее всего менее "похожи", чем объекты из одного класса, поэтому вектор будет каждый раз сильнее изменяться.
- Возможен вариант алгоритма, когда выбор каждого объекта неравновероятен, причём вероятность выпадения объекта обратно пропорциональна величине ошибки на объекте. Следует заметить, что при такой эвристике метод становится очень чувствителен к шумам.
Способы инициализации весов
- Инициализировать вектор нулями. Этот способ используется очень во многих системах, но совсем не всегда является удачным.
- , где - размерность пространства признаков.