§ 2. Связь между видом экстремизирующей разделяющей функции и видом функционала

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

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

Будем считать в дальнейшем, что граница, разделяющая области и определяемая уравнением

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

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

где такова, что

Для определения вариации функционалов, рассмотренных в предыдущем параграфе, нам понадобится формула для вариации функционалов вида

Эта формула устанавливается следующей леммой.

Лемма. Пусть функция непрерывна в ограниченной области Тогда вариация функционала (9) определяется следующим интегралом по поверхности

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

Рис. 24.

Аналогично, точки х, принадлежащие лежат на нормалях, восстановленных из тех точек поверхности в которых отрицательно. В силу соглашения о знаках функции имеем

или

Разобьем область поверхности на куски о,- так, чтобы:

1) в каждом куске а функция сохраняла свой знак;

2) диаметр каждой из областей с не превышал Для каждого из кусков построим область так, что точки, принадлежащие лежат на нормалях, восстановленных из точек поверхности принадлежащих Очевидно, что области Г осуществляют разбиение области Г т. е. если в соответствующем куске функция если в функция Легко видеть, что диаметр с? (Г каждой из областей Г, удовлетворяет неравенству

где

Введение областей Г позволяет записать выражение (11) в виде

где любая точка, принадлежащая

Используя теорему о среднем, интегралы в (13) можно представить в виде

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

где снова произвольная точка куска Таким образом, имеем

Подставляя (14) в (13), получаем

Представим (15) в виде

Первая сумма в (16) равна интегралу по поверхности

а вторая сумма может быть оценена следующим образом:

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

причем при

Поскольку же диаметр области Г, не превосходит формулу (12)),

Поэтому из (18) имеем

Сопоставляя (16), (17) и (19) и учитывая, что получаем

так что

что и составляет утверждение леммы. Лемма доказана.

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

Теорема Пусть функционал имеет вид

где Ф — дифференцируемая функция от ненормированных моментов (1) до степени включительно, а плотность вероятности является непрерывной функцией, обращающейся в нуль вне некоторого ограниченного множества Тогда:

1) если экстремум (минимум или максимум) функционала достигается на некоторой разделяющей

функции, этот же экстремум достигается на разделяющей функции, являющейся полиномом степени:

где

2) на разделяющей функции заданной соотношениями (20) и (21), функционал принимает стационарное значение.

В тексте теоремы I символы означают при четном числа, а при нечетном векторы с координатами где компонента вектора означает при четном произведения чисел а при нечетном скалярное произведение векторов

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

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

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

формул (20), (21) в предположении, что Тогда проблема сводится к выбору процедуры, решающей эту систему уравнений. Пример такой процедуры, предложенный М. И. Шлезингером [13], будет рассмотрен далее в конце этого параграфа. Такой подход к задаче обучения без учителя не является рекуррентным, так как при показе каждой новой точки приходится заново составлять и решать новую систему уравнений, не используя значений уже выписанных на предыдущем шаге. Нас в этой книге интересуют главным образом рекуррентные процедуры, которые и будут рассмотрены далее в этой главе.

Доказательство теоремы Рассмотрим вариацию функционала

где вариации ненормированных моментов, а скобки означают попрежнему произведение чисел или скалярное произведение векторов в зависимости от того, четно или нечетно Применяя формулу (10) к функционалам (1), имеем

Подставляя (23) в (22), получаем

Если имеет вид (20), (21), то интеграл в (24) обращается в нуль. Таким образом, доказано, что функция удовлетворяющая (20) и (21), доставляет функционалу стационарное значение.

Пусть теперь рассматриваемый функционал принимает экстремальное значение на некоторой функции Рассмотрим вначале случай, когда всюду

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

в точках, принадлежащих поверхности Определяя функцию в остальных точках области равенством (25), получаем доказательство теоремы в случае, когда всюду на множестве

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

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

выбрать сходящиеся подпоследовательности, имеющие своими пределами соответственно. Нетрудно установить теперь, переходя к пределу в (26) и используя непрерывность функционала и правых частей (21) по и (в норме С), что

причем предельные значения и удовлетворяют соотношениям (21). Но соотношение (27) означает, что функции доставляют соответственно минимум и максимум функционалу Теорема I доказана.

Рассмотрим теперь, что утверждает теорема I применительно к функционалам (2а), (4а), (5а).

Обратимся сначала к функционалу (формула В силу соотношения (21)

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

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

Обратимся теперь к функционалу (формула Этот функционал зависит лишь от моментов первого и нулевого порядков, и поэтому в силу теоремы I сразу видно, что функция, доставляющая ему экстремум, линейна с коэффициентами

Что касается функционала (формула (4а)), то он существенно зависит от моментов второго порядка, так что экстремизирующая функция в этом случае является гиперповерхностью второго порядка. Соответствующие формулы для коэффициентов функции (20) могут быть легко получены в силу теоремы I и не выписываются здесь, так как эти формулы не будут нам далее нужны.

Соотношениям (28) и (30) можно дать удобную геометрическую интерпретацию.

Рассмотрим, например, функционал (2а) и соотношения (28). Направляющий вектор экстремизирующей плоскости коллинеарен отрезку, соединяющему «центры тяжести» (средние векторы) множеств точек, лежащих по одну и по другую сторону от этой плоскости, а значит, сама экстремизирующая плоскость ортогональна этому отрезку и, кроме того, делит его попалам (рис. 25). Последнее замечание следует из того факта, что точка лежащая посредине отрезка,

соединяющего центры тяжести областей удовлетворяет уравнению

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

Рис. 25.

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

Алгоритм М. И. Шлезингера [13] предлагает как раз способ нахождения такой плоскости и заключается в следующем. Процесс начинается с произвольно

проведенной плоскости, лишь бы по каждую сторону от нее лежало некоторое число точек. Затем определяются «центры тяжести» точек, лежащих по каждую сторону от плоскости, и проводится новая плоскость, перпендикулярно к отрезку, соединяющему эти центры тяжести, через его середину; вновь вычисляются центры тяжести обеих групп точек и т. д. М. И. Шлезингером доказано, что эта плоскость сходится к той плоскости, которая разбивает выборку наилучшим образом в указанном выше смысле.

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

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

который достигает минимума при

Процедура Роббинса—Монро для минимизации функционала имеет вид

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

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

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

Поэтому процедура восстановления Р принимает вид

Пусть к некоторому моменту времени построена разделяющая функция вида (20)

и тем самым все пространство разбито на множества Обозначим через характеристическую функцию множества А:

Выразим правые части формулы (21) через нормированные моменты и вероятности и Тогда формула (21) принимает вид

Для получения процедуры, о которой идет речь, введем переменные потребовав, чтобы

они изменялись в силу соотношений

Коэффициенты же входящие в определение (34) характеристической функции определяются формулой

Совокупность соотношений (34), (36), (37) определяет рекуррентную процедуру вычисления последовательностей разделяющих поверхностей.

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

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

Отсюда следует, что формула (37) в пределе при переходит в формулу (35), которая лишь обозначениями отличается от формулы (21).

Таким образом, вопрос о том, можно ли использовать рекуррентную процедуру (34), (36) и (37) для решения интересующей нас задачи, сводится к установлению факта сходимости этой процедуры. В настоящее время достаточно широкие условия сходимости этой процедуры еще не установлены, и поэтому в каждом частном случае выбора исходного функционала пришлось бы устанавливать сходимость отдельно, используя теоремы и методы, изложенные в главе IV. Для частного случая функционала (2а) процедура (34), (36), (37) с учетом (28) сводится к виду

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