§ 4.5. Сходимость алгоритмов

При рассмотрении алгоритмов обучения (4.9) будем различать два случая:

1)  значения функции  для каждого фиксированного  измеряются с помехой , имеющей конечную дисперсию и математическое ожидание, равное нулю;

2)  значения функции  для каждого фиксированного  известны точно.

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

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

.      (4.16)

В этом случае

.                                   (4.17)

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

.                         (4.18)

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

Если «гипотеза представимости» не выполнена, равенство (4.18) записать нельзя, так как  будет зависеть от показов. Однако и в этом случае алгоритм (4.6) при постоянном , удовлетворяющем определенным условиям, будет сходиться. Так, например, для квадратичного критерия сходимость алгоритма с вероятностью единица имеет место при

.                   (4.19)