5.6.4. Сходимость алгоритмов обучения

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

Теорема 1. (О свойствах сходимости алгоритма.) Пусть векторы образов х удовлетворяют в пространстве образов следующим условиям.

1. Потенциальная функция

ограничена для .

2. Существует решающая функция, представимая в виде

такая, что

где .

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

Тогда с вероятностью 1 можно определить конечное число шагов таких, что кумулятивный потенциал

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

Теорема 2. (О скорости сходимости алгоритма.) Пусть

— бесконечная последовательность обучающих образов, выбранных из обучающего множества причем Допустим, что потенциальная функция ограничена при и существует решающая функция, представимая разложением (5.6.57) и удовлетворяющая условиям (5.6.58). Тогда существует целое число

не зависящее от выбора обучающей последовательности и такое, что при использовании алгоритмов из пп. 5.6.1 и 5.6.2 число коррекций не превышает величины R.

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

Доказательство. Прежде всего с помощью уравнения (5.6.28) преобразуем область X в Z. Обучающее множество отразится симметрично относительно начала координат, образовав множество Пусть, наконец,

и

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

Из условия (5.6.63) следует, что

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

вектор весов принимает вид

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

Из соотношений (5.6.64) и (5.6.67) получаем, что

Применение неравенства Коши — Шварца дает

Согласно (5.6.68) и (5.6.69),

Принимая во внимание неравенство (5.6.64), приходим к соотношению

Так как и существует вектор удовлетворяющий условию формулу (5.6.71) можно записать

Приняв, что при помощи итерации получим

Объединив (5.6.70) и (5.6.73), имеем

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

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

Известно, что этот ряд сходится, если при все коэффициенты равны пулю.

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

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

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

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