5.9.3. ПОВЕДЕНИЕ В СЛУЧАЕ НЕРАЗДЕЛЯЕМЫХ МНОЖЕСТВ

Если ТОЛЬКО что приведенное доказательство сходимости рассмотреть с целью выяснения использования предположения о раз- деляемости, то окажется, что данное предположение было использовано дважды. Во-первых, было использовано соотношение efeb=0, чтобы показать, что либо еь=0 при некотором конечном k, либо е* никогда не станет нулевым и коррекции не прекратятся. Во-вторых, такое же условие было использовано с целью показать, что если сходится к нулю, то тоже должно сходиться к нулю.

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

Что получается, если образы неразделяемы, а е^ никогда не обращается в нуль? В данном случае все же выполняются

Таким образом, последовательность Цвіір, ЦегЦ^, ... все еще сходится, хотя предельное значение ||е||® может не быть равным нулю. Поскольку условие сходимости требует, чтобы вектор е| сходился к нулю, можно сделать заключение, что либо 6^=0 при некотором конечном к, либо сходится к нулю, тогда как значение | е^Н отличается от нулевого. Таким образом, алгоритм Хо — Кашьяпа дает разделяющий вектор для случая разделяемых множеств и явно обнаруживает неразделяемость для случая неразделяемых множеств. Однако не существует ограничения числа шагов, необходимых для обнаружения неразделяемости.