5.2. Основные теоремы для персептронов ограниченного порядка

5.2.0. Замечания

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

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

5.2.1. Теорема о масках (теорема о положительной нормальной форме)

Каждый предикат линеен относительно множества всех масок.

Замечание. Это очень сильное утверждение. Если где Ф — какое-то множество масок, то порядок предиката определяется размером наибольшей маски из Ф. В теореме также утверждается, что любую классификацию можно реализовать линейным

предикатом, если в Ф содержатся все маски и нет других предикатов.

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

где логические произведения членов. Так как все эти произведения различны, то

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

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

Любое логическое произведение можно записать как произведение переменных и их отрицаний, скажем:

Пусть — первое отрицание, тогда (9) можно представить в виде

где

Заметим, что в входят только сами переменные, а может содержать как переменные, так и их отрицания. Очевидные алгебраические преобразования дают

Мы получили в виде линейной комбинации двух логических произведений, одно из которых содержит а другое нет. Каждое преобразование типа (13) устраняет одно отрицание. Если проделать это со всеми С] и всеми выведенными из них логическими произведениями, а затем со всеми последующими произведениями и т. д., то в итоге будет линейной комбинацией логических произведений, содержащих только переменные (а не их отрицания).

Такие логические произведения как раз и являются масками. Теорема доказана.

Иллюстрация. Пусть состоит из трех точек — предикат содержит нечетное число точек из Этот предикат принимает значение „истина", если все точки из или только одна принадлежат X. Следовательно, можно записать как

Последовательно применим (13) к (14):

Это линейный предикат на множестве масок.

Представление предиката в виде линейной комбинации масок называется его положительной нормальной формой. Можно показать, что положительная нормальная форма единственна; кроме того, предикат имеет порядок тогда и только тогда, когда наибольшая маска с ненулевым коэффициентом в положительной нормальной форме имеет размер (Минский и Пейперт, 1969, теоремы 1.5.2 и 1.5.3). Если эта маска не зависит от размера сетчатки то предикат имеет конечный порядок.