Теорема сходимости Перцептрона - это теорема описанная и доказанная Ф. Розенблаттом (с участием Блока, Джозефа, Кестена и других исследователей, работавших вместе с ним). Она показывает, что элементарный перцептрон, обучаемый по методу коррекции ошибки (независимо от того с квантованием или без него), а также независимо от начального состояния весовых коэффициентов, последовательности появления стимулов - всегда приведет к достижению решения за конечный промежуток времени. Ф. Розенблаттом также были представлены доказательства ряда сопутствующих теорем, следствия из которых позволяли сделать вывод о том каким условиям должна обладать архитектура искусственных нейронных сетей и методы их обучения.
Теоремы существования решения для универсальных перцептронов[]
Прежде, чем доказать основную теорему сходимости перцептрона, Ф. Розенблатт показал, что архитектура перцептрона достаточна для того, чтобы получить решение любой мыслимой задачи на классификацию, т.е. тем самым перцептрон представляет собой "универсальную систему".
| Файл:Logo arte.jpg | Теорема 1. Дана сетчатка с двумя состояниями входных сигналов (Да и Нет). Тогда класс элементарных перцептронов, для которых существует решение для любой классификации C(W) возможных сред W, не является пустым. |
Далее Ф. Розенблатт показал и доказал в теореме 2, что необходимыми, но еще не достаточными условиями существования решения, являются следующие:
- каждый стимул должен возбуждать по крайней мере один А-элемент;
- не должно существовать никакой подпоследовательности стимулов, содержащей по меньшей мере по одному стимулу каждого класса, которая приводила бы к одинаковому коэффициенту смещения для каждого А-элемента в множестве А-элементов, реагирующих на эту подпоследовательность.
Второе условие нуждается в пояснении. Коэффициентом смещения для А-элемента Ф. Розенблатт называл отношение числа стимулов в обучающей выборке, которые относятся к одному классу, и возбуждают данный А - элемент, к числу стимулов, относящихся к другому классу, но также возбуждающие этот же А-элемент. Нарушение второго условия делает отношение постоянным для А-элементов, реагирующих на стимулы из такой определенной подпоследовательности появления стимулов на входах перцептрона. И из-за этого, как доказывается в теореме 2, по крайней мере один из стимулов будет классифицирован неправильно.
Розенблатт также показал, что этих условий будет недостаточно, на следующем примере
| Стимул | Возбуждает А-элементы | Принадлежит к классу |
|---|---|---|
| №1 | №1 | №1 (положительному) |
| №2 | №2 | №1 (положительному) |
| №3 | №3 и №4 | №1 (положительному) |
| №4 | №1, №2 и №3 | №2 (отрицательному) |
| №5 | №1, №2 и №4 | №2 (отрицательному) |
| А - элемент | Коэффициент смещения |
|---|---|
| №1 | 1/2 |
| №2 | 1/2 |
| №3 | 1/1 |
| №4 | 1/1 |
Данный пример удовлетворяет двум необходимым условиям, но тем ни менее не имеет решения. Чтобы получить нужную классификацию для первого класса, требуется:
- Для правильной классификации стимула №1, чтобы вес А-элемента №1 был бы положительным;
- Для правильной классификации стимула №2, чтобы вес А-элемента №2 был бы положительным;
- Для правильной классификации стимула №3, чтобы сумма весовых коэффициетнов А-элементов №3 и №4 была бы положительной.
Чтобы получить нужную классификацию для второго класса, требуется:
- Для правильной классификации стимула №4, сумма весовых коэффициетнов А-элементов №1, №2 и №3 была бы отрицательной
- Для правильной классификации стимула №5, сумма весовых коэффициетнов А-элементов №1, №2 и №4 была бы отрицательной
Отсюда видно, что если у нас весовые коэффициенты для А-элементов №1 и №2 положительные, и хотя бы один из весовых коэффициентов для А-элементов №3 и №4 положителен, то тем самым мы можем добится, чтобы сумма весов №1(+), №2(+) и №3(-) была бы отрицательной, но вынуждены в таком случае вес №4 оставить положительным, и тогда сумма №1(+), №2(+) и №4(+) никак не может быть отрицательной. Таким образом, либо стимул №4, либо стимул №5 будут классифицированы неправильно. Это и называется отсутствие схождения при решении классификации.
В чистом виде достаточные условия Розенблатт описывает только позже в следующей теореме, предложенной Джозефом:
| Файл:Logo arte.jpg | Теорема 9. Даны элементарный перцептрон и классификация C(W). Необходимое и достаточное условие того, что методом коррекции ошибок за конечное время и из произвольного начального состояния может быть достигнуто решение, сводится к тому, что не должно существовать ненулевого вектора , такого, что для всех i показатель смещения |
но так как это математическое представление, хотя и более элегантное, но тем ни менее мало говорящие о том какие нужно выполнить условия в терминах архитектуры перцептрона, Розенблатт прежде доказывает следующую теорему:
| Файл:Logo arte.jpg | Теорема 3. Даны элементарный перцептрон, пространство стимулов W и какая-то классификация C(W). Тогда для существования решения для C(W) необходимо и достаточно, чтобы существовал некоторый вектор u, лежащий в том же ортанте, что и C(W), и некоторый вектор x, такой, что Gx=u. |
Но практически значимыми являются три следствия из этой теоремы:
- Если G - матрица перцептрона особенная, т.е. матрица, не имеющая обратной (это происходит когда ее детерминант равен нулю), то может существовать некоторая классификация, которая не имеет решения. В этом случае сходимости при обучении перцептрона не будет.
- Если число стимулов в обучающей выюорке больше числа А-элементов в элементарном перцептроне, то также существует некоторая классификация, которая не имеет решения. Таким образом, определяется верхняя граница числа формальных нейронов в скрытом слое. Однако практически достаточно иметь 60-80% (и не менее 50%) от этого числа в зависимости от числа классов на которые нужно классифицировать стимулы.
- Вероятность существования решения для случайно выбранной классификации при увеличении числа стимулов (что непосредственно, согласно второму следствию, ведет к увеличению числа А-элементов) стремится к нулю. Практически это означает, что при наличии у перцептрона порядка 1000 А-элементов, вероятность того, что его G-матрица будет особенной близка к нулю, а при увеличении числа А-элементов такая вероятность стремится к нулю.
Основная теорема сходимости[]
В основной теореме сходимости Ф. Розенблатт показывает, что существующие возможные решения могут быть достигнуты именно при применении алгоритма обучения с коррекцией ошибки:
| Файл:Logo arte.jpg | Теорема 4. Даны элементарный перцептрон, пространство стимулов W и некоторая классификация C(W), для которой известно, что решение существует. Предположим, что все стимулы из W появляются в любой последовательности, но при условии, что каждый стимул появляется повторно через некоторый конечный интервал времени. Тогда процесс обучения с коррекцией ошибок (с квантованием или без квантования подкрепления), начинающийся с произвольного исходного состояния, всегда приведет к достижению решения для C(W) в течении конечного промежутка времени. При этом все входные сигналы к R - элементам достигнут значения, по крайней мере равного некоторой произвольной величине d >= 0. |
Дополнительные теоремы сходимости[]
В ряде следующих теорем Ф. Розенблатт показывает какими характеристиками должен обладать алгоритм обучения, чтобы он мог достич решения.
- В теореме 5 он показывает, что метод коррекции ошибок со случайным знаком подкрепления, хоть и уступает методу с коррекцией ошибок по скорости, но тем ни менее может достич решения.
- В теореме 6 доказано, что при S-управляемом обучении может быть полученно решение, но оно может оказаться нейстойчивым. А при R-управляемом обучении вообще не имеет смысла говорить об вероятности сходимости процесса обучения.
- В теореме 7 показано, что метод коррекции случайными возмущениями (по сути метод коррекции без учителя) так-же уступая по скорости методу с коррекцией ошибок, позволяет получить решение за конечное время.
- В теореме 8 Показывается, что для Гамма-перцептрона (перцептрон в котором веса всех активных связей сначала изменяются на равную величину, а затем из весов всех связей вычитается другая величина, равная полному изменению весов всех активных связей, деленному на число всех связей) может существовать решение которого он достич не сможет.
Критика Минского[]
Минский привел ряд своих доказательств теоремы о схождении Перцептрона. Но его доказательства позволили судить о величине весовых коэффициентов, что существенно для хранения их в памяти компьютера, а также о числе необходимых коррекций весовых коэффициентов, что важно при оценке скорости обучения перцептрона.
Для оценки емкости памяти требуемой для хранения весовых коэффициентов, при решении обучении предикату "четность", Минский исходил из следующих соображений. Для любого единообразного представления коэффициентов необходимо по бит на каждый, где - число точек на сетчатке перцептрона. Это следует из того, что таким должен быть вес самого большого коэффициента, чтобы выполнялись условия существования решения. А необходимое число коэффициентов (максимально необходимое) . Следовательно, потребуется бит. Если сравнивать это число с тем, если запомнить все возможные изображения, которые могут быть нанесены на сетчатку перцептрона - то емкость, которая для этого понадобится равна . При таких предположениях, получается, что перцептрону для весовых коэффициентов емкости требуется практически столько же, как для запоминания всех возможных изображений.
Для оценки числа иттераций требующихся элементарному перцептрону, чтобы определить весовые коэффициенты, Минский проанализировал обучение предикату "четность", которая есть одна из наиболее теоритически сложных для перцептрона. При этом он взял перцептрон с наименьшем возможным числом А-элементов, а следовательно, и с наименьшим числом весовых коэффициентов. И для этого случая он определил нижнию и верхнию границу числа коррекций: , где - число точек на сетчатке перцептрона.
Поэтому критика Минского в отношении сходимости перцептрона указывает на то, что:
- если требуется работать с довольно большим разрешением изображений, например 800х600 пикселей,
- и требуется решить некую математическую функцию, которая зависит целиком от всех точек (например, предикат четность, о котором нельзя сказать четен он или нет пока не будут проанализированы все точки пространства последовательно)
то перцептрон потребует нереальной большой памяти компьютера и длительного времени обучения, даже не смотря на то, что теорема сходимости говорит о конечном числе иттераций.
Здесь, следует добавить только то, что для большинства задач распознавания реальных изображений не требуется находить такие математические функции, а отличительные черты изображений разного класса могут быть найдены учитывая лишь маленькую область, например, состоящую из 20 точек из 8000 возможных. А построив такие предикаты от 20 элементов (предикаты соответствуют А-элементам) можно не учитывая все особенности изображения, классифицировать их по классам учитывая лишь некоторые из них (как правило число таких предикатов, как было сказанно выше находятся в пределах 60-80% от числа всех изображений). Это указывает на тот факт, что число осмысленных изображений в определенной размерности на несколько порядков меньше, чем число всевозможных изображений. И если не требовать выполнения некоторой математической функции (сдвиг, поворот) над такими осмысленными изображениями, становится ясным, что перцептрон может не только оптимально запоминать для классифицирования ряд изображений, но и работать в некотором смысле алгоритмом сжатия изображений с потерями, но точно относя их к требуемому классу.
Литература[]
- Фрэнк Розенблатт Принципы нейродинамики: перцептроны и теория механизмов мозга = Principles of Neurodynamic: perceptrons and the theory of brain mechanisms. — М.: «Мир», 1965.
- М. Минский, С. Пейперт Персептроны = Perceptrons. — М.: «Мир», 1971.
См. также[]
Это основополагающая версия, написанная участниками этого проекта. Но содержимое этой страницы очень близкое по содержанию предоставлено для раздела Википедии на русском языке. Так же, как и в этом проекте, текст этой статьи, размещённый в Википедии, доступен на условиях GNU FDL. Статью, размещенную в Википедии можно найти по адресу: Теорема сходимости перцептрона.