§ 5. Сходимость процедуры

Далее, при решении иных задач (гл. VI и VII) исследование сходимости соответствующей процедуры метода потенциальных функций опирается на теорему XV главы IV. Применение этой теоремы к исследованию сходимости процедуры этой главы затруднено в связи с двумя обстоятельствами: во-первых, с необходимостью дополнительно выяснить, не возникает ли «ложное» решение, о котором шла речь в конце предыдущего параграфа, а во-вторых, с отсутствием в алгоритме этой главы «сжимающего» множителя В связи с этим в этом параграфе мы не будем опираться на теорему XV, а будем использовать иные соображения, исходящие из особенностей задачи, рассматриваемой в этой главе.

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

Условие (18) в) исключает случай, когда «спектральный состав» потенциальной функции «уже» спектрального состава восстанавливаемой функции, так как в противном случае некоторые из членов ряда (18) в) были бы бесконечно велики из-за того, что при Для персептронной реализации это означает присутствие в схеме персептрона гармоник, для которых в (18) а) К вопросу о том, как ведет себя процедура, если это условие не выполнено, мы более в этом параграфе возвращаться не будем.

Введем в рассмотрение величину

которая отличается от величины (17) лишь отсутствием множителя Если теперь показать, что величина (19) в силу процедуры (4), (5) в каком-либо смысле стремится к нулю с ростом то это может быть только, если в пределе при знаки совпадают, т. е. если реализуется правильное разделение. Для этой величины, рассматриваемой как функционал от процедура (4), (5) не является градиентной, однако имеет место следующая

Теорема I. Пусть множества в пространстве X и система функций таковы, что:

1) выполнены условия (18), и функция удовлетворяет условию

2) появление точек обучающей последовательности — независимые события, определяемые плотностью вероятности

Тогда в силу алгоритма, определяемого соотношениями (4), (5),

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

Введем обозначение

В силу условия (5) выбора последовательности

С другой стороны, в силу (22), если только

Таким образом, всегда

Имея в виду применить далее теорему VI главы IV, введем в качестве последовательности функций последовательность

Вспоминая теперь, что

получаем

Воспользовавшись соотношением (23), получаем

Здесь учтено, что принимает лишь значения О или 1, и, следовательно,

Переходя в (26) к условным математическим ожиданиям, находим

Применим теперь в качестве последовательности фигурирующей в теореме VI главы IV, выражение

совпадающее в силу (5) с (19), а в качестве константы а, фигурирующей в тексте этой теоремы, — величину

Тогда все условия теоремы VI главы IV выполнены, и в силу этой теоремы последовательность а значит, и величина (19) стремится к нулю почти наверное. Теорема I доказана.

Интересной особенностью процедуры (4), (5) является то, что она обеспечивает разделение множеств за конечное число шагов. Этот факт устанавливают следующие теоремы II и III.

Теорема II (А. Новиков [11]). Пусть М — произвольная бесконечная последовательность точек пространства X, принадлежащих множествам А или В. Пусть, далее, существует функция удовлетворяющая условиям (18) и (20). Тогда существует целое число не зависящее от выбора последовательности М, такое, что при использовании процедуры (4), (5) число исправлений ошибок не превосходит числа равного

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

Доказательство теоремы II будет проведено на этом «геометрическом языке» применительно к спрямляющему пространству.

Доказательство теоремы II. Введем обозначения

Из (20) и (28) следует, что

Поскольку

то так как — ограниченная функция. На геометрическом языке величина а равна минимальному расстоянию от плоскости до объединенной области расстояние от начала координат до наиболее удаленной от него точки этой области (рис. 16).

Из (28) и (29) следует, что при

Рис. 16.

Обозначим, кроме того, через

направляющий вектор плоскости, построенной рассматриваемой процедурой после исправлений ошибок (последовательность М определена выше, в § 2 этой главы, — см. текст перед формулой Тогда, если

Проследим за изменением направляющего вектора плоскости, выстраиваемой в силу алгоритма. Просуммируем неравенство (31) по I от единицы до учитывая затем обозначение (33):

Для оценки левой части (35) используем неравенство Коши — Буняковского

Отсюда и из (35) после сокращения на получаем

Далее, в соответствии с геометрической интерпретацией алгоритма

Поэтому

Используя теперь неравенства (32) и (34), получаем

Из этого рекуррентного соотношения, учитывая, что находим

Объединяя неравенства (36) и (37)

получаем окончательно оценку

Оценка (38) выписана в терминах спрямляющего пространства. Она может быть переписана в терминах пространства X, если переписать в этих терминах формулы (28) и (29):

Поэтому

и число конечно, если ряд сходится. Этот ряд сходится заведомо, если выполнено основное предположение (18). Теорема II доказана.

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

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

Теорема III. Пусть множества в пространстве X таковы, что существует разделяющая функция, удовлетворяющая условиям (18) и (20), а статистика показа удовлетворяет следующим условиям:

а) точки обучающей последовательности появляются независимо с одним и тем же распределением вероятностей.

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

Тогда с вероятностью единица для каждой реализации процедуры найдется такое конечное число I (быть может, свое для каждой реализации), что

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

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

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

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

Доказательство теоремы III. Рассмотрим множество всех реализаций процедуры (соответствующих множеству всех обучающих последовательностей). В каждой реализации существует последнее исправление ошибки (так как в соответствии с теоремой II их может быть лишь конечное число). Рассмотрим вероятность того, что после последнего исправления ошибки вероятность появления ошибки на следующем шаге больше чем Но событие «после последнего исправления ошибки и событие «при во всех последующих показах ошибки не происходит» тождественны. Вероятность же последнего события равна нулю для каждого так как вероятность ненаступления ошибки в последующие шагов в силу независимости появления точек (условие теоремы) меньше чем а последнее выражение стремится к нулю при Следовательно, при любом а отсюда следует, что и Но в соответствии с условием теоремы и есть вероятность того, что разделение не происходит. Поэтому вероятность того, что разделение произойдет, равна что и требовалось доказать.