§ 5. Метод циклического повторения обучающей последовательности

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

Какова же достаточная длина последовательности примеров для персептрона Розенблатта?

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

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

Казалось бы, в данной ситуации обучение на реальном числе примеров (несколько сотен) возможно лишь в исключительных случаях. Вспомним, однако, что выше нас всюду интересовало только число исправлений, независимо от того, на каком материале они происходили. При этом оказывалось, что если только нужное число исправлений проведено, то можно гарантировать, что искомое решающее правило найдено. А раз так, возникает мысль использовать одну и ту же обучающую последовательность несколько раз: предъявлять ее обучающемуся устройству до тех пор, пока при очередном предъявлении не будет ни одного исправления коэффициентов. Прекращение исправлений решающего правила как раз и будет означать, что обучающая последовательность разделена правильно. Но это-то и означает также, что реализуется метод минимизации эмпирического риска.

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

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

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

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

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

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