§ 3. Описание алгоритмов непосредственной аппроксимации степени достоверности.

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

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

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

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

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

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

а аппроксимируется функция являющаяся математическим ожиданием случайной функции по В такой постановке задача аппроксимации степени достоверности не требует применения формулы Байеса и сводится к рассмотренной в § 2 главы VI задаче об аппроксимации детерминированной функции по ее

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

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

В частности, минимизируемый функционал в этом случае имеет вид (см. формулу (20) гл. VI)

Теорема I главы VI, устанавливающая условия сходимости процедуры (16) § 2 главы VI, применима и в данном случае, причем условие которое в главе VI являлось дополнительным ограничением, теперь всегда выполняется, так как

Второй алгоритм. В предлагаемом алгоритме фигурирует оператор «черта сверху», определенный следующим образом:

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

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

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

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

Подставляя в (24) выражение для из (20) и вспоминая, что в рассматриваемой задаче как раз и является аппроксимируемой функцией убеждаемся, что алгоритм (24) имеет специальный вид, выделенный формулами (10), (11) главы II, причем

Это позволит нам далее, в § 4 настоящей главы, применить к этому алгоритму все результаты главы IV, касающиеся алгоритмов вида (10), (11) главы II.

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

Рассматриваемую процедуру можно представить в виде рекуррентного соотношения

где величина определяется в зависимости от того, какой из случаев или реализовался на шаге:

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

Процедура (26), (27) может быть рассмотрена как частный случай процедуры (10), (11) главы II, так как случайную последовательность можно представить в виде

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

Используя теперь формулу (27), получаем

Обозначая через разность

математическое ожидание которой, разумеется, равно нулю, приходим к формуле (28), в которой

Таким образом, показано, что процедура (26), (27), несмотря на наличие в ней случайного акта «бросания монеты», может быть представлена в форме (10), главы II, причем

где

Более того, вид функции в рассматриваемом третьем алгоритме оказался точно таким же, как и во втором алгоритме (см. формулу (25)). С этой точки зрения второй и третий алгоритмы отличаются лишь видом помехи ?: в отличие от второго алгоритма, в третьем алгоритме помеха зависит также и от случайного акта. Одинаковый вид функции определяет тот факт, что второй и третий алгоритмы минимизируют один и тот же функционал, вид которого устанавливается в следующем параграфе.

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