Теорема Перцептрона

Если есть множество точек на плоскости, как построить разделяющее множество?

Можно выделить две выпуклые оболочки, найти ближайшие точки и между ними по центру провести прямую. Под каким углом? Ну ок, в двумерном клёво, а в n-мерном - огромные вычислительные сложности на построение выпуклой оболочки. Алгоритм общего перебора. x₁..x_k - промежуточный класс

y₁..y_k - правильный класс. Надо найти вектор (w₁..w_n) и порог, тогда g(x) = ∑ w_i * x_i

Решающее правило: f(x)= sign(g(x))

Алгоритм:

1. Пробегаем 1..k

   σ(x_k) = y_k ???

   • Да - ничего
   • Нет - w := w + y_k * x_k

   θ := θ + y_k

2. На шаг 1
3. Нашли конец - хорошо. Были ошибки - плохо.

Формулировка теоремы.

Если классы -1,1 линейноразделимы, т.е. алгоритм сходится за конечное время.