Теорема сходимости перцептрона

Теорема сходимости перцептрона — это теорема, описанная и доказанная Ф. Розенблаттом (с участием Блока, Джозефа, Кестена и других исследователей, работавших вместе с ним). Она показывает, что элементарный перцептрон, обучаемый по методу коррекции ошибки (с квантованием или без него), независимо от начального состояния весовых коэффициентов и последовательности появления стимулов всегда приведёт к достижению решения за конечный промежуток времени. Ф. Розенблаттом также были представлены доказательства ряда сопутствующих теорем, следствия из которых позволяли сделать вывод о том, каким условиям должны соответствовать архитектура искусственных нейронных сетей и методы их обучения.

Теоремы существования решения для универсальных перцептронов

Логическая схема элементарного перцептрона. Веса S—A связей могут иметь значения −1, +1 или 0 (то есть отсутствие связи). Веса A—R связей W могут быть любыми.

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

Теорема 1.
Дана сетчатка с двумя состояниями входных сигналов (Да и Нет). Тогда класс элементарных перцептронов, для которых существует решение для любой классификации C(W) возможных сред W, не является пустым.

Далее Ф. Розенблатт показал и доказал в теореме 2, что необходимыми, но ещё не достаточными условиями существования решения, являются следующие:

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

Второе условие нуждается в пояснении. Коэффициентом смещения для А-элемента Ф. Розенблатт называл отношение $n_{i}^{+}/n_{i}^{-}$ числа стимулов в обучающей выборке, которые относятся к одному классу, и возбуждают данный А — элемент, к числу стимулов, относящихся к другому классу, но также возбуждающие этот же А-элемент. Нарушение второго условия делает отношение $n_{i}^{+}/n_{i}^{-}$ постоянным для А-элементов, реагирующих на стимулы из такой определённой подпоследовательности появления стимулов на входах перцептрона. И из-за этого, как доказывается в теореме 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 будут классифицированы неправильно. Это и называется отсутствие схождения при решении классификации.

В чистом виде достаточные условия Розенблатт описывает только позже в следующей теореме, предложенной Джозефом:

Теорема 9.
Даны элементарный перцептрон и классификация C(W). Необходимое и достаточное условие того, что методом коррекции ошибок за конечное время и из произвольного начального состояния может быть достигнуто решение, сводится к тому, что не должно существовать ненулевого вектора

X^{**}

, такого, что для всех і показатель смещения

b_{i}(X^{**})=0

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

Теорема 3.
Даны элементарный перцептрон, пространство стимулов W и какая-то классификация C(W). Тогда для существования решения для C(W) необходимо и достаточно, чтобы существовал некоторый вектор u, лежащий в том же ортанте, что и C(W), и некоторый вектор x, такой, что Gx=u.

Но практически значимыми являются три следствия из этой теоремы:

Если G - матрица перцептрона особенная, то есть матрица, не имеющая обратной (это происходит когда её детерминант равен нулю), то может существовать некоторая классификация, которая не имеет решения. В этом случае сходимости при обучении перцептрона не будет.
Если число стимулов в обучающей выборке больше числа А-элементов в элементарном перцептроне, то также существует некоторая классификация, которая не имеет решения. Таким образом, определяется верхняя граница числа формальных нейронов в скрытом слое. Однако практически достаточно иметь 60-80 % (и не менее 50 %) от этого числа в зависимости от числа классов на которые нужно классифицировать стимулы.
Вероятность существования решения для случайно выбранной классификации при увеличении числа стимулов (что непосредственно, согласно второму следствию, ведёт к увеличению числа А-элементов) стремится к нулю. Практически это означает, что при наличии у перцептрона порядка 1000 А-элементов, вероятность того, что его G-матрица будет особенной близка к нулю, а при увеличении числа А-элементов такая вероятность стремится к нулю.

Основная теорема сходимости

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

Теорема 4.
Даны элементарный перцептрон, пространство стимулов W и некоторая классификация C(W), для которой известно, что решение существует. Предположим, что все стимулы из W появляются в любой последовательности, но при условии, что каждый стимул появляется повторно через некоторый конечный интервал времени. Тогда процесс обучения с коррекцией ошибок (с квантованием или без квантования подкрепления), начинающийся с произвольного исходного состояния, всегда приведёт к достижению решения для C(W) в течение конечного промежутка времени. При этом все входные сигналы к R - элементам достигнут значения, по крайней мере равного некоторой произвольной величине d >= 0.

Дополнительные теоремы сходимости

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

В теореме 5 он показывает, что метод коррекции ошибок со случайным знаком подкрепления, хотя и уступает методу с коррекцией ошибок по скорости, но, тем не менее, может достичь решения.
В теореме 6 доказано, что при S-управляемом обучении может быть получено решение, но оно может оказаться неустойчивым. А при R-управляемом обучении вообще не имеет смысла говорить о вероятности сходимости процесса обучения.
В теореме 7 показано, что метод коррекции случайными возмущениями (по сути, метод коррекции без учителя), также уступая по скорости методу с коррекцией ошибок, позволяет получить решение за конечное время.
В теореме 8 показывается, что для гамма-перцептрона (перцептрон в котором веса всех активных связей сначала изменяются на равную величину, а затем из весов всех связей вычитается другая величина, равная полному изменению весов всех активных связей, деленному на число всех связей) может существовать решение, которого он достичь не сможет.

Теорема Минского

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

Критика Минского

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

Для оценки ёмкости памяти требуемой для хранения весовых коэффициентов, при решении обучении предикату «четность», Минский исходил из нижеследующих соображений. Для любого единообразного представления коэффициентов необходимо по $|R|-1$ бит на каждый, где $|R|$ — число точек на сетчатке перцептрона. Это следует из того, что таким должен быть вес самого большого коэффициента, чтобы выполнялись условия существования решения. А необходимое число коэффициентов (максимально необходимое) $2^{|R|}$ . Следовательно, потребуется $(|R|-1)*2^{|R|}$ бит. Если сравнивать это число с тем, что получится в случае, если запомнить все возможные изображения, которые могут быть нанесены на сетчатку перцептрона, то понадобится ёмкость = $|R|*2^{|R|-1}$ . При таких предположениях получается, что перцептрону для весовых коэффициентов ёмкости требуется практически столько же, как для запоминания всех возможных изображений.

Для оценки числа итераций, требующихся элементарному перцептрону чтобы определить весовые коэффициенты, Минский проанализировал обучение предикату «четность», которая есть одна из наиболее теоретически сложных для перцептрона. При этом он взял перцептрон с наименьшим возможным числом А-элементов, а следовательно и с наименьшим числом весовых коэффициентов, и для этого случая определил нижнюю и верхнюю границу числа коррекций: $5^{|R|}<n<10^{|R|}$ , где $|R|$ — число точек на сетчатке перцептрона.

Поэтому критика Минского в отношении сходимости перцептрона указывает на то, что:

если требуется работать с довольно большим разрешением изображений, например 800х600 пикселей,
и требуется решить некую математическую функцию, которая зависит целиком от всех точек (например, предикат чётность, о котором нельзя сказать, чётен он или нет пока не будут проанализированы все точки пространства последовательно)

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

Здесь следует добавить только то, что для большинства задач распознавания реальных изображений не требуется находить такие математические функции, а отличительные черты изображений разного класса могут быть найдены учитывая лишь маленькую область, например, состоящую из 20 точек из 8000 возможных. Построив такие предикаты от 20 элементов (предикаты соответствуют А-элементам), можно классифицировать изображения, не учитывая все их особенности (как правило число таких предикатов, как было сказано выше, находится в пределах 60-80 % от числа всех изображений). Это указывает на тот факт, что число осмысленных изображений в определённой размерности на несколько порядков меньше, чем число всевозможных изображений. Если не требовать выполнения некоторой математической функции (сдвиг, поворот) над такими осмысленными изображениями, становится ясным, что перцептрон может не только оптимально запоминать для классифицирования ряд изображений, но и работать в некотором смысле алгоритмом сжатия изображений с потерями, точно относящим их к требуемому классу.

Литература

Фрэнк Розенблатт. Принципы нейродинамики: перцептроны и теория механизмов мозга = Principles of Neurodynamic: perceptrons and the theory of brain mechanisms. — М.: «Мир», 1965.

М. Минский, С. Пейперт. Персептроны = Perceptrons. — М.: «Мир», 1971.

См. также

Перцептрон