Главная > Интеллектуальные системы > Введение в статистическую теорию распознавания образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.1.2. Доказательство сходимости для случая линейной разделимости классов.

Доказательство сходимости описанного выша алгоритма проводится следующим образом [Нильсон, 1967].

Введем новый вектор

Тогда классификатор (7.2) принимает вид

а правила модификации текущего вектора параметров в (7.5):

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

Кроме того, предположим, что Это предположение не уменьшает общности доказательства по следующим причинам:

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

2. Правило полной коррекции и градиентное правило коррекции становятся эквивалентными правилу фиксированного приращения, если во всех случаях, когда дополнять обучающую последовательность последовательностью искусственных объектов Значение и определяется условиями (7.9) и (7.10).

Сокращенная обучающая последовательность создает соответствующую последовательность векторов

где

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

Выбирая

можно выбрать масштаб так, чтобы

Изменение масштаба не изменяет решающего правила (7.13) дли (7.2).

Расстояние между векторами параметров равно

Следовательно, используя (7.15), получим

Вспоминая, что и учитывая неравенства (7.18) и (7.19), имеем

Неравенство (7.22) показывает, что при каждом предъявлении нового объекта расстояние уменьшается на некоторую фиксированную величину, большую чем Поэтому после конечного числа предъявлений вектор должен стать равным вектору

<< Предыдущий параграф Следующий параграф >>
Оглавление