Метод градиентного спуска

Метод градиентного спуска

Рассмотрим СЛАУ (1). Пусть матрица является симметричной и положительно определенной. Поставим в соответствие СЛАУ (1) многочлен:

 

, (11)

 

который называется функционалом энергии.

Утверждение 1. Если матрица является симметричной и положительно определенной, то многочлен (11) имеет единственный минимум.

Существует определенная связь между двумя задачами: задачей решения СЛАУ (1) и задачей минимизации функционала (11).

Теорема 4. Если в некоторой точке n-мерного векторного пространства многочлен (11) имеет минимум, то координаты этой точки являются решением СЛАУ (1).

Теорема 5. Если — решение СЛАУ (1), то многочлен (11) принимает в этой точке свой абсолютный минимум по всему n-мерному пространству.

Из теорем 4,5 вытекает, что задача решения СЛАУ (1) для симметричной и положительно определенной матрицы эквивалентна задаче минимизации функционала (11).

Метод градиентного (или наискорейшего) спуска является достаточно общим и применяется для минимизации любой функции, для которой имеет смысл понятие градиента.

Пусть в некоторой области n-мерного пространства векторов задана произвольная функция . Предположим, что задано начальное приближение к минимуму этой функции. Отправляясь из точки , мы хотим двигаться к точке минимума как можно быстрее. В силу этого нам нужно двигаться из точки в направлении, противоположном направлению вектора-градиента функции в этой точке (вспомним, что — это вектор, по численному значению и по направлению характеризует наибольшую скорость возрастания функции в точке ). Определив направление движения, необходимо также определить расстояние, на которое нам нужно продвинуться за один шаг.

Путь, по которому мы будем перемещаться из точки , задается уравнением:

 

, (12)

 

при этом . Нам нужно следить за изменением значения при движении в направлении , т.е. нужно следить за некоторой функцией

 

. (13)

 

Остановиться нужно при таком , в котором функция достигает своего минимума. Это произойдет там, где (см.матем.анализ – условия локального экстремума функции одной переменной). Пусть определяется по формуле (11). В этом случае

 

. (14)

 

Формула (14) получается путем непосредственного вычисления координат вектора и сравненя их значений с соответствующими элементами вектора :

 

Первая компонента вектора получается как удвоенная разность между произведением первой строки матрицы на вектор и , т.е. равна , что полностью сопадает со значение, полученным выше для . Аналогично проверяются равенства и последующих компонент векторов.

Тогда функция (13) может быть записана в виде:

 

,

 

где

. (15)

 

Вычислим :

.

 

;

 

.

&n
bsp;

Тогда

.

 

Приравнивая , получаем стационарную точку функции:

 

. (16)

 

Алгоритм метода наискорейшего (градиентного) спуска

Пусть — заданная точность (погрешность), с которой нужно получить решение поставленной задачи.

Шаг 1. Задается начальное приближение .

Шаг 2. По формуле (16) вычисляется коэффициент .

Шаг 3. По формуле (15) вычисляет очередное приближение к решению : .

Шаг 4 (проверка). Если , то требуемая точность достигнута, итерационный процесс завершен, в качестве приближенного значения решения СЛАУ (1) берется , полученный на шаге 3; иначе полагается равным , переход на шаг 2.

Замечание 4 (вычислительная сложность метода градиентного спуска). Основные расчетные формулы метода градиентного спуска – это формулы (16) и (15), которые определяет действия данного алгоритма на каждой итерации. Проверьте, что каждая итерация метода градиентного спуска требует операций, тогда в целом количество арифметических операций, необходимых для решения СЛАУ методом градиентного спуска, определиться как

 

,

 

где — это количество итераций, затраченных в методе градиентного спуска для достижения заданной точности решения .

 

Вопросы

  1. Сравнение итерационных и прямых методов решения СЛАУ, их принципиальные отличия.
  2. Особенности и преимущества итерационных методов решения систем линейных алгебраических уравнений. Основная идея итерационных методов.
  3. Критерий сходимости МПИ для любого начального приближения.
  4. Вычислительная сложность МПИ.
  5. Возможности увеличения скорости сходимости МПИ.
  6. Стационарный метод Зейделя как ускорение МПИ.
  7. Условия сходимости стационарного метода Зейделя.
  8. Вычислительная сложность стационарного метода Зейделя.
  9. Основная идея метода наискорейшего спуска. Понятие функционала энергии. Для каких СЛАУ можно использовать метод наискорейшего спуска? Почему?
  10. Вычислительная сложность метода наискорейшего спуска.

 

12345


Дата добавления: 2015-03-20; просмотров: 952;


ПОСМОТРЕТЬ ЕЩЕ:

Стохастический Градиентный Спуск

Градиентные методы — это широкий класс оптимизационных алгоритмов, используемых не только в машинном обучении.

1.2. Градиентные методы.

Здесь градиентный подход будет рассмотрен в качестве способа подбора вектора синаптических весов в линейном классификаторе. Пусть — целевая зависимость, известная только на объектах обучающей выборки:

Найдём алгоритм , аппроксимирующий зависимость . В случае линейного классификатора искомый алгоритм имеет вид:

где играет роль функции активации (в простейшем случае можно положить ).

Согласно принципу минимизации эмпирического риска для этого достаточно решить оптимизационную задачу:

Где — заданная функция потерь.

Для минимизации применим метод градиентного спуска (gradient descent).

Это пошаговый алгоритм, на каждой итерации которого вектор изменяется в направлении наибольшего убывания функционала (то есть в направлении антиградиента):

Где — положительный параметр, называемый темпом обучения (learning rate).

Возможны 2 основных подхода к реализации градиентного спуска:

1. Пакетный (batch), когда на каждой итерации обучающая выборка просматривается целиком, и только после этого изменяется . Это требует больших вычислительных затрат.

2. Стохастический (stochastic/online), когда на каждой итерации алгоритма из обучающей выборки каким-то (случайным) образом выбирается только один объект. Таким образом вектор настраивается на каждый вновь выбираемый объект.

Можно представить алгоритм стохастического градиентного спуска в виде псевдокода следующим образом:

Вход:

· — обучающая выборка

· — темп обучения

· — параметр сглаживания функционала

Выход:

1. Вектор весов

Тело:

1) Инициализировать веса

2) Инициализировать текущую оценку функционала:

3) Повторять:

1. Выбрать объект из случайным образом

2. Вычислить выходное значение алгоритма и ошибку:

3. Сделать шаг градиентного спуска

4. Оценить значение функционала:

4) Пока значение не стабилизируется и/или веса не перестанут изменяться.

 

Главным достоинством SGD можно назвать его скорость обучения на избыточно больших данных. Именно это интересно для нас в рамках поставленной перед нами задачи ибо объем входных данных будет весьма велик. В то же время, алгоритм SGD в отличие от классического пакетного градиентного спуска дает несколько меньшую точность классификации. Также алгоритм SGD неприменим при обучении машины опорных векторов с нелинейным ядром.

Выводы

В рамках решаемой задачи нам потребуется воспользоваться алгоритмом преобразования исходных данных TF-IDF, который позволит нам повысить весомость редких событий и снизить вес частых событий. Полученные после преобразования данные мы будем передавать классификаторам, которые подходят для решения стоящей перед нами задачи, а именно: Наивный Байесовский Классификатор или Машина Опорных Векторов с Линейным ядром, обученная по методу стохастического градиентного спуска. Также мы осуществим проверку эффективности Машины Опорных Векторов с нелинейными ядрами, обученной по методу пакетного градиентного спуска. Однако, данный тип классификатора не кажется подходящим для поставленной задачи в силу слишком сложного ядра и склонности к переобучаемости, при которой классификатор плохо справляется с данными, которые не использовались для обучения классификатора.


Дата добавления: 2015-11-16; просмотров: 369 | Нарушение авторских прав


Постановка задачи | Задача классификации | Стратегия One-vs.-rest | Multi-label классификация | Методы и алгоритмы, реализованные в программной системе | Инструкция пользователя | Рабочий режим | Тестовый режим | Рабочий режим | Машинный эксперимент |


mybiblioteka.su — 2015-2018 год. (0.008 сек.)

Задача кластеризации

Только что мы изучили задачу классификации, относящуюся к стратегии "обучение с учителем".

В этой части лекции мы введем понятия кластеризации, кластера, кратко рассмотрим классы методов, с помощью которых решается задача кластеризации, некоторые моменты процесса кластеризации, а также разберем примеры применения кластерного анализа.

Задача кластеризации сходна с задачей классификации, является ее логическим продолжением, но ее отличие в том, что классы изучаемого набора данных заранее не предопределены.

Синонимами термина "кластеризация" являются "автоматическая классификация", "обучение без учителя" и "таксономия".

Кластеризация предназначена для разбиения совокупности объектов на однородные группы (кластеры или классы). Если данные выборки представить как точки в признаковом пространстве, то задача кластеризации сводится к определению "сгущений точек".

Цель кластеризации — поиск существующих структур.

Кластеризация является описательной процедурой, она не делает никаких статистических выводов, но дает возможность провести разведочный анализ и изучить "структуру данных".

Само понятие "кластер" определено неоднозначно: в каждом исследовании свои "кластеры". Переводится понятие кластер (cluster) как "скопление", "гроздь".

Кластер можно охарактеризовать как группу объектов, имеющих общие свойства.

Характеристиками кластера можно назвать два признака:

· внутренняя однородность;

· внешняя изолированность.

Вопрос, задаваемый аналитиками при решении многих задач, состоит в том, как организовать данные в наглядные структуры, т.е.

развернуть таксономии.

Наибольшее применение кластеризация первоначально получила в таких науках как биология, антропология, психология. Для решения экономических задач кластеризация длительное время мало использовалась из-за специфики экономических данных и явлений.

В таблице 5.2 приведено сравнение некоторых параметров задач классификации и кластеризации.

 

Таблица 5.2. Сравнение классификации и кластерзации

Характеристика Классификация Кластеризация
Контролируемость обучения Контролируемое обучение Неконтролируемое обучение
Стратегия Обучение с учителем Обучение без учителя
Наличие метки класса Обучающее множество сопровождается меткой, указывающей класс, к которому относится наблюдение Метки класса обучающего множества неизвестны
Основание для классификации Новые данные классифицируются на основании обучающего множества Дано множество данных с целью установления существования классов или кластеров данных

На рисунке 5.7 схематически представлены задачи классификации и кластеризации.

Рисунок 5.7 — Сравнение задач классификации и кластеризации

 

Кластеры могут быть непересекающимися, или эксклюзивными (non-overlapping, exclusive), и пересекающимися (overlapping).

6.1. Метод градиентного спуска

Схематическое изображение непересекающихся и пересекающихся кластеров дано на рисунке 5.8

Рисунок 5.8 — Непересекающиеся и пересекающиеся кластеры

 

Следует отметить, что в результате применения различных методов кластерного анализа могут быть получены кластеры различной формы. Например, возможны кластеры "цепочного" типа, когда кластеры представлены длинными "цепочками", кластеры удлиненной формы и т.д., а некоторые методы могут создавать кластеры произвольной формы.

Различные методы могут стремиться создавать кластеры определенных размеров (например, малых или крупных) либо предполагать в наборе данных наличие кластеров различного размера.

Некоторые методы кластерного анализа особенно чувствительны к шумам или выбросам, другие — менее.

В результате применения различных методов кластеризации могут быть получены неодинаковые результаты, это нормально и является особенностью работы того или иного алгоритма.

Данные особенности следует учитывать при выборе метода кластеризации.

Подробнее обо всех свойствах кластерного анализа будет рассказано в лекции, посвященной его методам.

На сегодняшний день разработано более сотни различных алгоритмов кластеризации. Некоторые, наиболее часто используемые, будут подробно описаны во втором разделе курса лекций.

Приведем краткую характеристику подходов к кластеризации [21].

· Алгоритмы, основанные на разделении данных (Partitioning algorithms), в т.ч. итеративные:

o разделение объектов на k кластеров;

o итеративное перераспределение объектов для улучшения кластеризации.

· Иерархические алгоритмы (Hierarchy algorithms):

o агломерация: каждый объект первоначально является кластером, кластеры, соединяясь друг с другом, формируют больший кластер и т.д.

· Методы, основанные на концентрации объектов (Density-based methods):

o основаны на возможности соединения объектов;

o игнорируют шумы, нахождение кластеров произвольной формы.

· Грид-методы (Grid-based methods):

o квантование объектов в грид-структуры.

· Модельные методы (Model-based):

o использование модели для нахождения кластеров, наиболее соответствующих данным.

Предыдущая23242526272829303132333435363738Следующая


Дата добавления: 2015-09-28; просмотров: 871;


ПОСМОТРЕТЬ ЕЩЕ:

Лекция 3
Методы многомерной безусловной оптимизации. Методы первого порядка

К методам первого порядка относятся алгоритмы, в которых в процессе поиска кроме информации о самой функции используется информация о производных первого порядка. К группе таких методов относятся различные градиентные методы.

Алгоритм наискорейшего спуска

Градиент функции в любой точке показывает направление наибольшего локального увеличения . Поэтому при поиске минимума , следует двигаться в направлении противоположном направлению градиента в данной точке, то есть в направлении наискорейшего спуска.

Итерационная формула процесса наискорейшего спуска имеет вид

, или .

Оптимизация без ограничений. Градиентный спуск

Очевидно, что в зависимости от выбора параметра λ траектории спуска будут существенно различаться. При большом значении λ траектория спуска будет представлять собой колебательный процесс, а при слишком больших λ процесс может расходиться. При выборе малых λ траектория спуска будет плавной, но и процесс будет сходиться очень медленно. Обычно λ выбирают из условия , решая одномерную задачу минимизации с использованием некоторого одномерного метода. В этом случае получаем алгоритм наискорейшего спуска.

Если λ определяется в результате одномерной минимизации, то градиент в точке очередного приближения будет ортогонален направлению предыдущего спуска .

Вообще говоря, процедура наискорейшего спуска может закончиться в стационарной точке любого типа, в которой . Поэтому следует проверять, не завершился ли алгоритм в седловой точке.

Эффективность алгоритма зависит от вида минимизируемой функции. Алгоритм наискорейшего спуска сойдется за одну итерацию при любом начальном приближении для функции , но сходимость будет очень медленной, например, в случае функции вида . В тех ситуациях, когда линии уровня минимизируемой функции представляет собой прямолинейный или, хуже того, криволинейный «овраг» эффективность алгоритма оказывается очень низкой. Очевидно, что хорошие результаты может давать предварительное масштабирование функций.

Процесс наискорейшего спуска обычно быстро сходится вдали от точки экстремума и медленно в районе экстремума. Поэтому метод наискорейшего спуска нередко используют в комбинации с другими алгоритмами.

Метод сопряженных градиентов

В алгоритме наискорейшего спуска на каждом этапе поиска используется только текущая информация о функции и градиенте . В алгоритмах сопряженных градиентов используется информация о поиске на предыдущих этапах спуска.

Направление поиска на текущем шаге строится как линейная комбинация наискорейшего спуска на данном шаге и направлений спуска на предыдущих шагах . Веса в линейной комбинации выбираются таким образом, чтобы сделать эти направления сопряженными. В этом случае квадратичная функция будет минимизироваться за шаг алгоритма.

При выборе весов используется только текущий градиент и градиент в предыдущей точке.

В начальной точке направление спуска : , где λ0 выбирается из соображений минимальности целевой функции в данном направлении . Новое направление поиска , где ω1 выбирается так, чтобы сделать направления и сопряженными по отношению к матрице H: . (*)

Для квадратичной функции справедливы соотношения: , где , .

Если положить , тогда и .

Воспользуемся последним выражением, чтобы исключить из уравнения (*). Для квадратичной функции H = HT, поэтому .

Следовательно, для сопряженности и : .

Вследствие изложенных ранее свойств сопряженности все перекрестные члены исчезают. Учитывая, что , получим для ω1 следующее соотношение: .

Направление поиска строится в виде линейной комбинации векторов , , , причем так, чтобы оно было сопряженным с . Если распространить сделанные выкладки на , опуская их содержание и учитывая, что приводит к , можно получить общее выражение для ωk:

(**).

Все весовые коэффициенты, предшествующие ωk, что особенно интересно, оказываются нулевыми.

Полностью алгоритм описывается следующей последовательностью действий:

Если исходная функция является квадратичной, то (n+1)-е приближение даст точку экстремума данной функции. Описанный алгоритм с построением ωk по формулам (**) соответствует методу сопряженных градиентов Флетчера-Ривса.

В модификации Полака-Рибьера (Пшеничного) метод сопряженных градиентов отличается только вычислением .

В случае квадратичных функций обе модификации примерно эквивалентны, однако в модификации Полака-Рибьера алгоритм обычно оказывается несколько эффективнее.

Многопараметрический поиск

Милем и Кентреллом предложен метод поиска, основанный на использовании двух подбираемых параметров для минимизации в каждом направлении поиска. В этом алгоритме последовательность действий определяется формулой: , где .

На каждом шаге решается задача минимизации по двум параметрам: .

После чего находится очередное приближение. При этом можно показать, что , и .

На первом шаге , а должно быть задано. На k-м шаге:

Процесс заканчивается, когда .

На квадратичных функциях алгоритм по эффективности близок к методу сопряженных градиентов.

Крэгг и Леви распространили данный метод на случай большего числа параметров. На каждом шаге при минимизации в заданном направлении решается задача вида , а очередное приближение при m ≤ n — 1.

Достоинства и недостатки такого подхода очевидны.



Метод градиентного спуска

Рассмотрим СЛАУ (1).

Пусть матрица является симметричной и положительно определенной. Поставим в соответствие СЛАУ (1) многочлен:

 

, (11)

 

который называется функционалом энергии.

Утверждение 1. Если матрица является симметричной и положительно определенной, то многочлен (11) имеет единственный минимум.

Существует определенная связь между двумя задачами: задачей решения СЛАУ (1) и задачей минимизации функционала (11).

Теорема 4. Если в некоторой точке n-мерного векторного пространства многочлен (11) имеет минимум, то координаты этой точки являются решением СЛАУ (1).

Теорема 5. Если — решение СЛАУ (1), то многочлен (11) принимает в этой точке свой абсолютный минимум по всему n-мерному пространству.

Из теорем 4,5 вытекает, что задача решения СЛАУ (1) для симметричной и положительно определенной матрицы эквивалентна задаче минимизации функционала (11).

Метод градиентного (или наискорейшего) спуска является достаточно общим и применяется для минимизации любой функции, для которой имеет смысл понятие градиента.

Пусть в некоторой области n-мерного пространства векторов задана произвольная функция . Предположим, что задано начальное приближение к минимуму этой функции. Отправляясь из точки , мы хотим двигаться к точке минимума как можно быстрее. В силу этого нам нужно двигаться из точки в направлении, противоположном направлению вектора-градиента функции в этой точке (вспомним, что — это вектор, по численному значению и по направлению характеризует наибольшую скорость возрастания функции в точке ). Определив направление движения, необходимо также определить расстояние, на которое нам нужно продвинуться за один шаг.

Путь, по которому мы будем перемещаться из точки , задается уравнением:

 

, (12)

 

при этом . Нам нужно следить за изменением значения при движении в направлении , т.е. нужно следить за некоторой функцией

 

. (13)

 

Остановиться нужно при таком , в котором функция достигает своего минимума. Это произойдет там, где (см.матем.анализ – условия локального экстремума функции одной переменной). Пусть определяется по формуле (11). В этом случае

 

. (14)

 

Формула (14) получается путем непосредственного вычисления координат вектора и сравненя их значений с соответствующими элементами вектора :

 

Первая компонента вектора получается как удвоенная разность между произведением первой строки матрицы на вектор и , т.е.

Градиентный спуск

равна , что полностью сопадает со значение, полученным выше для .

Аналогично проверяются равенства и последующих компонент векторов.

Тогда функция (13) может быть записана в виде:

 

,

 

где

. (15)

 

Вычислим :

.

 

;

 

.

 

Тогда

.

 

Приравнивая , получаем стационарную точку функции:

 

. (16)

 

Алгоритм метода наискорейшего (градиентного) спуска

Пусть — заданная точность (погрешность), с которой нужно получить решение поставленной задачи.

Шаг 1. Задается начальное приближение .

Шаг 2. По формуле (16) вычисляется коэффициент .

Шаг 3. По формуле (15) вычисляет очередное приближение к решению : .

Шаг 4 (проверка). Если , то требуемая точность достигнута, итерационный процесс завершен, в качестве приближенного значения решения СЛАУ (1) берется , полученный на шаге 3; иначе полагается равным , переход на шаг 2.

Замечание 4 (вычислительная сложность метода градиентного спуска). Основные расчетные формулы метода градиентного спуска – это формулы (16) и (15), которые определяет действия данного алгоритма на каждой итерации. Проверьте, что каждая итерация метода градиентного спуска требует операций, тогда в целом количество арифметических операций, необходимых для решения СЛАУ методом градиентного спуска, определиться как

 

,

 

где — это количество итераций, затраченных в методе градиентного спуска для достижения заданной точности решения .

 

Вопросы

  1. Сравнение итерационных и прямых методов решения СЛАУ, их принципиальные отличия.
  2. Особенности и преимущества итерационных методов решения систем линейных алгебраических уравнений. Основная идея итерационных методов.
  3. Критерий сходимости МПИ для любого начального приближения.
  4. Вычислительная сложность МПИ.
  5. Возможности увеличения скорости сходимости МПИ.
  6. Стационарный метод Зейделя как ускорение МПИ.
  7. Условия сходимости стационарного метода Зейделя.
  8. Вычислительная сложность стационарного метода Зейделя.
  9. Основная идея метода наискорейшего спуска. Понятие функционала энергии. Для каких СЛАУ можно использовать метод наискорейшего спуска? Почему?
  10. Вычислительная сложность метода наискорейшего спуска.

 

12345


Дата добавления: 2015-03-20; просмотров: 951;


ПОСМОТРЕТЬ ЕЩЕ:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *