Теорема Новикова

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Ссылки)
 
(10 промежуточных версий не показаны.)
Строка 1: Строка 1:
 +
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
 +
'''Теорема Новикова''' — теорема сходимости персептрона.
'''Теорема Новикова''' — теорема сходимости персептрона.
-
+
 
-
Рассматривается случай, в котором изменение "весов" в методе стохастического градиента производится по правилу Хэбба. Теорема гарантирует, что в случае линейно разделимой обучающей выборки вектор "весов" находится за конечное число итераций алгоритма.
+
Рассмотрим [[Метод стохастического градиента|метод стохастического градиента]] как способ подбора вектора синаптических весов <tex>w</tex> в [[линейный классификатор|линейном классификаторе]]. На каждой итерации алгоритма случайным образом выбирается объект обучающей выборки (то есть во время работы алгоритма объекты обучающей выборки перебираются в случайном порядке, возможно, неоднократно), и вектор «весов» изменяется в направлении наибольшего убывания функционала потерь <tex>Q</tex>.
 +
 
 +
Рассматривается случай, в котором это изменение производится по правилу Хэбба. Теорема гарантирует, что в случае линейно разделимой обучающей выборки вектор «весов» находится за конечное число итераций алгоритма.
== Историческая справка ==
== Историческая справка ==
-
В 1957 г. Ф. Розенблатт предложил эвристику обучения нейрона, основанную на принципах нейрофизиологии: при ошибках алгоритма на обучающей выборке «веса» соответствующих обучающих объектов изменяются определенным образом, чтобы «связь» не ослабевала, подобно связи между двуми нейронами. Обучение происходит до тех пор, пока веса не перестанут изменяться. В этом состоит суть [[Однослойный персептрон (пример)|однослойного персептрона Розенблатта]].
+
В 1957 г. Ф. Розенблатт предложил эвристику обучения нейрона, основанную на принципах нейрофизиологии: при ошибках алгоритма на обучающей выборке «веса» соответствующих обучающих объектов изменяются определенным образом, чтобы «связь» не ослабевала, подобно связи между двуми нейронами. Обучение происходит до тех пор, пока веса не перестанут изменяться. В этом состоит суть [[Однослойный персептрон (пример)|однослойного персептрона Розенблатта]]— частного случая градиентного метода.
== Правило Хэбба ==
== Правило Хэбба ==
Строка 22: Строка 26:
Тогда алгоритм, основанный на [[Метод стохастического градиента|методе стохастического градиента]], с правилом Хэбба находит вектор весов, разделяющий обучающую выборку безошибочно за конечное число итераций при любом начальном приближении <tex>$w^{0}$</tex> и при любом <tex>$\eta>0$</tex>, независимо от порядка предъявления объектов обучающей выборки.
Тогда алгоритм, основанный на [[Метод стохастического градиента|методе стохастического градиента]], с правилом Хэбба находит вектор весов, разделяющий обучающую выборку безошибочно за конечное число итераций при любом начальном приближении <tex>$w^{0}$</tex> и при любом <tex>$\eta>0$</tex>, независимо от порядка предъявления объектов обучающей выборки.
 +
 +
'''Замечания'''
-
В частности, при нулевом начальном приближении <tex>$w^{0}=0$</tex> число итераций алгоритма не превосходит
+
*При нулевом начальном приближении <tex>$w^{0}=0$</tex> число итераций алгоритма не превосходит
<tex>$n_{max}=$</tex>
<tex>$n_{max}=$</tex>
<tex>$ (\frac D \delta) ^{2}$ </tex>, где <tex>$D=max||x||$</tex>, где <tex>$x\in X^{l}$ </tex>.
<tex>$ (\frac D \delta) ^{2}$ </tex>, где <tex>$D=max||x||$</tex>, где <tex>$x\in X^{l}$ </tex>.
-
На практике выборки редко обладают свойством линейной разделимости.
+
*На практике выборки редко обладают свойством линейной разделимости.
 +
 
 +
*Если условия теоремы Новикова не выполнены, то процесс обучения может оказаться расходящимся.
-
Если условия теоремы Новикова не выполнены, то процесс обучения может оказаться расходящимся.
 
==Литература==
==Литература==
* Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
* Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
Строка 36: Строка 43:
* [[Машинное обучение (курс лекций, К.В.Воронцов)]].
* [[Машинное обучение (курс лекций, К.В.Воронцов)]].
-
[[Категория:Метрические алгоритмы классификации]]
+
[[Категория:Линейные классификаторы]]
-
[[Категория:Классификация]]
+
[[Категория:Нейронные сети]]
-
[[Категория:Машинное обучение]]
+
-
[[Категория:Энциклопедия анализа данных]]
+
-
+
-
{{Задание|Allegra|Константин Воронцов|8 января 2010}}
+

Текущая версия

Данная статья является непроверенным учебным заданием.
Студент: Участник:Allegra
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Теорема Новикова — теорема сходимости персептрона.

Рассмотрим метод стохастического градиента как способ подбора вектора синаптических весов w в линейном классификаторе. На каждой итерации алгоритма случайным образом выбирается объект обучающей выборки (то есть во время работы алгоритма объекты обучающей выборки перебираются в случайном порядке, возможно, неоднократно), и вектор «весов» изменяется в направлении наибольшего убывания функционала потерь Q.

Рассматривается случай, в котором это изменение производится по правилу Хэбба. Теорема гарантирует, что в случае линейно разделимой обучающей выборки вектор «весов» находится за конечное число итераций алгоритма.

Содержание

Историческая справка

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

Правило Хэбба

Рассматривается некоторая модификация метода стохастического градиента. Пусть множество ответов алгоритма $ Y=\{-1,+1\}$, $x$ — некоторый объект обучающей выборки $X^l=\{x_i, y_i\}_{i=1}^l$, $ y_i=y_{i}^*(x_i)\in Y $ — классы, которым принадлежат эти объекты.

И пусть алгоритм классификации имеет вид $a(x, w)=sign(\<x,w\>)$, где $\<x,w\>$ — скалярное произведение объекта и его «веса». Таким образом, алгоритм классификации ошибается, если знак этого скалярного произведения не совпал со знаком класса, которому принадлежит объект $x$, то есть если $\<x,w\>y<0$.

Тогда правило модификации весов примет вид:

если $\<x,w\>y<0$, то:
$w:=w+\eta x y$.

Это правило носит название правила Хэбба.

Для правила Хэбба справедлива теорема Новикова о сходимости.

Теорема сходимости (теорема Новикова)

Пусть $X=R^{n+1}, Y=\{-1,+1\}$ и выборка $X^l$ линейно разделима, то есть существует вектор $w*$ и число $\delta >0$ такие, что $\<x_i,w*\>y_i>\delta$ $\forall i=1\dots l$.

Тогда алгоритм, основанный на методе стохастического градиента, с правилом Хэбба находит вектор весов, разделяющий обучающую выборку безошибочно за конечное число итераций при любом начальном приближении $w^{0}$ и при любом $\eta>0$, независимо от порядка предъявления объектов обучающей выборки.

Замечания

  • При нулевом начальном приближении $w^{0}=0$ число итераций алгоритма не превосходит

$n_{max}=$ $ (\frac D \delta) ^{2}$ , где $D=max||x||$, где $x\in X^{l}$ .

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

Литература

  • Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9D%D0%BE%D0%B2%D0%B8%D0%BA%D0%BE%D0%B2%D0%B0»
Личные инструменты