5.2.2. Теорема об инвариантности относительно группы

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

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

Определения

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

2. Множество Ф предикатов на замкнуто относительно Это означает, что для каждого предиката каждого преобразования существует такой предикат о что

Для интерпретации (16) полезно заметить, что, если значение задано (истина или ложь), то найдется такой предикат в, что если для перестройки сетчатки применялось преобразование то значение совпадает с заданным значением а (X).

3. Классом эквивалентности предиката относительно группы называется множество удовлетворяющее (16) при Формально предикат о принадлежит классу эквивалентности предиката о тогда и только тогда, когда

В этом случае мы будем писать

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

Пример. На рис. 5.3 изображена сетчатка в виде (-матрицы. Предположим, что Ф — множество детекторов вертикальных полос длины два. В матричных обозначениях будет

множеством а любой предикат из Ф — это логическое произведение

Пусть — множество преобразований, отображающих столбцы в столбцы. Любое преобразование сдвинет поле для вправо или влево (см. рис. 5.3 для детекторов вертикальных полос в строках 3 и 4). Классом эквивалентности заданного предиката будет множество предикатов с одинаковым номером строки так как каждое допускаемое преобразование сдвигает носитель детектора вправо или влево, а не вверх или вниз.

Рис. 5.3. Пример класса эквивалентности. Предикат „Существует вертикальная полоса длины два в столбце 1 и строках 3 и имеет класс эквивалентности (обозначенный прямоугольниками) относительно множества преобразований, переставлиющих столбцы.

Теорема об инвариантности относительно группы. Если предикат 4“ принадлежит и инвариантен относительно для всех то его можно представить в виде

где если

Доказательство. Так как — линейный предикат, то его можно представить в виде

где некоторое множество вещественных чисел.

Поскольку множество Ф замкнуто относительно любое преобразование определяет соответствие Для всех X и

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

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

Применим (21) к

Подставим (24) в (23):

Это справедливо для всех Суммирование (25) по всем дает положительное число

Меняя порядок суммирования, получаем

Теперь положим

Если и номера предикатов одного и того же класса эквивалентности, то для некоторых и . В более общем виде,

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

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

Следствие 1. Предикат порядка инвариантный относительно группы, можно представить линейным предикатом на множестве Ф масок размера в котором маски (одного и того же размера), отображаемые друг в друга некоторым преобразованием имеют одинаковые коэффициенты.

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

Следствие 2. Пусть множество Ф разбито на классы эквивалентности относительно Линейный предикатф, инвариантный относительно группы можно представить в виде

где — число предикатов в для которых

Для доказательства достаточно рассмотреть конструктивное определение Для любого X точно предикатов будут „возбуждены".

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