Теорема Новикова
Материал из MachineLearning.
(→Правило Хэбба) |
(→Правило Хэбба) |
||
| Строка 6: | Строка 6: | ||
== Правило Хэбба == | == Правило Хэбба == | ||
Рассматривается некоторая модификация [[Метод стохастического градиента|метода стохастического градиента]]. | Рассматривается некоторая модификация [[Метод стохастического градиента|метода стохастического градиента]]. | ||
| - | Пусть множество ответов алгоритма <tex>$ Y=\{-1,+1\}$</tex>, <tex>$x$</tex> | + | Пусть множество ответов алгоритма <tex>$ Y=\{-1,+1\}$</tex>, <tex>$x$</tex> — некоторый объект обучающей выборки <tex>$X^l=\{x_i, y_i\}_{i=1}^l$</tex>, <tex>$ y_i=y_{i}^*(x_i)\in Y $</tex> — классы, которым принадлежат эти объекты. |
| - | И пусть алгоритм классификации имеет вид <tex>$a(x, w)=sign(\<x,w\>)$</tex>, где <tex>$\<x,w\>$</tex> | + | И пусть алгоритм классификации имеет вид <tex>$a(x, w)=sign(\<x,w\>)$</tex>, где <tex>$\<x,w\>$</tex> — скалярное произведение объекта и его «веса». Таким образом, алгоритм классификации ошибается, если знак этого скалярного произведения не совпал со знаком класса, которому принадлежит объект <tex>$x$</tex>, то есть если <tex>$\<x,w\>y<0$</tex>. |
Тогда правило модификации весов примет вид: | Тогда правило модификации весов примет вид: | ||
Версия 18:49, 2 января 2010
Теорема Новикова-теорема сходимости персептрона.
Содержание |
Историческая справка
В 1957 г. Ф. Розенблатт предложил эвристику обучения нейрона, основанную на принципах нейрофизиологии: при ошибках алгоритма на обучающей выборке «веса» соответствующих обучающих объектов изменяются определенным образом, чтобы «связь» не ослабевала, подобно связи между двуми нейронами. Обучение происходит до тех пор, пока веса не перестанут изменяться. В этом состоит суть однослойного персептрона Розенблатта.
Правило Хэбба
Рассматривается некоторая модификация метода стохастического градиента.
Пусть множество ответов алгоритма ,
— некоторый объект обучающей выборки
,
— классы, которым принадлежат эти объекты.
И пусть алгоритм классификации имеет вид , где
— скалярное произведение объекта и его «веса». Таким образом, алгоритм классификации ошибается, если знак этого скалярного произведения не совпал со знаком класса, которому принадлежит объект
, то есть если
.
Тогда правило модификации весов примет вид:
- если
, то:
-
.
-
Это правило носит название правила Хэбба.
Для правила Хэбба справедлива теорема Новикова о сходимости.
Теорема сходимости (теорема Новикова)
Пусть и выборка
линейно разделима, то есть существует вектор
и число
такие, что
.
Тогда алгоритм, основанный на методе стохастического градиента, с правилом Хэбба находит вектор весов, разделяющий обучающую выборку безошибочно за конечное число итераций при любом начальном приближении и при любом
, независимо от порядка предъявления объектов обучающей выборки.
В частности, при нулевом начальном приближении число итераций алгоритма не превосходит
, где
, где
.
На практике выборки редко обладают свойством линейной разделимости.
Если условия теоремы Новикова не выполнены, то процесс обучения может оказаться расходящимся.
Литература
- Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
Ссылки
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
