5.3. Другие теоремы для персептронов ограниченного порядка

5.3.0. Считающие предикаты

Пусть будет группой всех перестановок элементов сетчатки так что содержит все отображения из в Пусть — число точек сетчатки которые для изображения X находятся в „возбужденном" состоянии т. е. число переменных без черточек сверху в представлении X). Единственными предикатами первого порядка, инвариантными относительно являются считающие предикаты

и их отрицания.

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

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

или, что эквивалентно,

где Заметим, что здесь 0 может считаться коэффициентом маски нулевого размера (константы) линейного предиката. Поскольку — целое число, порог 0 можно уточнять.

Замечание. Персептрон порядка 1 представляет собой в некотором смысле „наиболее общую" обучающуюся машину. Ее конструктор не встроил в нее никаких предубеждений, описав Ф, поскольку он просто предъявляет персептрону картинки, воспринимаемые сетчаткой вместе с указанием их класса и дает возможность процедуре сходимости определить, что же в них существенно. В теореме утверждается, что только тогда, когда это сделано (классификация при этом должна быть инвариантна относительно

любого преобразования), персептрон может сформировать правило классификации, которое отделит изображения друг от друга, исходя из их площадей. Является этот результат ободряющим или удручающим, удивительным или неудивительным, зависит от вашей точки зрения. В одном из ранних исследований персептронов было обнаружено, что персептроны первого порядка способны обучаться достаточно точному и интересному разделению объектов. Для иллюстрации способностей персептронов часто использовались рукописные буквы или цифры. Фактически персептрон классифицировал вариант картинки, закодированный цифрами. Тонкие различия в размерах букв и цифр приводили к разным числам возбужденных элементов в сетчатке, и, значит, можно было применить считающий предикат. Теорема о сходимости (гл. 4) гарантирует, что такой предикат можно найти.

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

5.3.1. Четность

Сформулируем соответствующую теорему без доказательства. Предикат

нельзя найти персептроном порядка, меньшего чем размер сетчатки. И если сетчатку можно увеличить неограниченно, то необходимый персептрон не будет конечного порядка. (Напомним, что в предикате „четность", рассматриваемом для иллюстрации теоремы о положительной нормальной форме, одна из масок имела размер 3, равный размеру сетчатки.)

Четность — интересное математическое понятие, поэтому факт, что персептрон не может классифицировать по четности, наводит на мысль, что персептроны не обладают некоторыми свойствами, которыми должна была бы обладать мыслящая машина. Можно построить очень простое устройство последовательного распознавания образов, которое будет классифицировать по четности. Этой машине требуются две компоненты: точечное устройство считывания и однобитовая память. Машина начинает работать с записи в память нуля (четное число). Затем она считывает сетчатку и меняет состояние памяти всякий раз, когда встречает элемент сетчатки в „возбужденном" состоянии. В конце считывания состояние памяти и будет соответствовать классификации изображения.