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

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

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

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

Градиенты среднеквадратичной ошибки по коэффициентам W и Г, представляют собой выражения

Для того чтобы выполнялось условие вычислительная процедура должна быть организована следующим образом.

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

а вместо С использовать

Таким образом, компоненты вектора А Г будут положительны или равны нулю в зависимости от того, положительны или отрицательны соответствующие компоненты вектора С. Следовательно,

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

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

2) Не накладывается ограничений на коэффициенты Поэтому при данном, векторе Г можно выбрать коэффициенты из условия где градиент имеет вид (4.80);

или

При заданном оценка минимизирует на этом итеративном шаге среднеквадратичную ошибку

Для доказательства сходимости процедуры оптимизации (4.84) и (4.86) исследуем норму вектора С, который используется при коррекции векторов Г и Из выражений (4.83) и (4.79) следует, что

При увеличении номера шага I приращение величины можно вычислить путем подстановки выражений (4.84) и (4.86) в (4.83). В результате получим

С другой стороны, из выражений (4.83), (4.85) и (4.78) имеем

и

Поэтому выражение (4.88) можно упростить следующим образом:

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

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

означает, что

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

Поэтому можно найти некоторую константу а 1 такую, что

Это противоречит тому, что при данном векторе Г коэффициенты выбраны из условия минимума среднеквадратичной ошибки вида (4.79). Таким образом, равенство (4.91) выполняется только при условии, что на каждом шаге I монотонно уменьшается до тех пор, пока не станет равным нулю. Это завершает доказательство сходимости рекуррентной процедуры для случая линейной разделимости классов.

В случае линейной неразделимости классов условие (4.93) и, следовательно, (4.94) не выполняется. Поэтому нельзя распространить доказательство сходимости на этот случай. Можно только утверждать, что процедура оптимизации сойдется, если на некотором шаге будет выполнено или