Пусть заданы вещественные числа $ a_1,\dots, a_n, b $, причем не все $ \{a_j\}_{j=1}^n $ равны нулю. Уравнение $$ w_1x_1+w_2x_2+\dots+w_nx_n= b $$ относительно переменных $ x_1,x_2,\dots,x_n $ задает в $ \mathbb R^n $ множество, называемое гиперплоскостью (в частном случае гиперплоскости в $ \mathbb R^2 $ она, очевидно, является с прямой). Если в пространстве $ \mathbb R^n $ скалярное произведение векторов $ X:=(x_1,\dots,x_n) $ и $ Y:=(y_1,\dots,y_n) $ задается стандартным способом $$ \langle X,Y \rangle = x_1y_1+\dots+x_n y_n \, , $$ то уравнение гиперплоскости можно переписать в виде $$ \langle X, W \rangle = b \quad \mbox{при} \quad W:=(w_1,\dots,w_n) \, . $$ В этом случае вектор $ W $ интерпретируется как вектор нормали к гиперплоскости. Действительно, если $ X_1 $ и $ X_2 $ — две точки, лежащие на гиперплоскости, то вектор $ W $ перпендикулярен вектору $ \vec{X_1X_2} $: $$ \langle X_1, W \rangle = b, \ \langle X_2, W \rangle = b \quad \Rightarrow \quad \langle X_2-X_1, W \rangle = 0 \, . $$

Каждая гиперплоскость делит $ \mathbb R^n $ на два подмножества. Для точек одного из них выполняется неравенство $$ w_1x_1+w_2x_2+\dots+w_nx_n > b \ ,$$ а для точек другого — $$ w_1x_1+w_2x_2+\dots+w_nx_n < b \ .$$ Каждое из этих множеств называется (открытым) полупространством, определяемым данной гиперплоскостью. Если к полупространству присоединяются точки гиперплоскости¹⁾, то получившееся множество называется замкнутым полупространством.

Теорема. Если точка $ X_0 $ лежит в гиперплоскости $ \langle X,W \rangle = b $, то точка $ X_0+t W $ при любом положительном значении параметра $ t $ лежит в полупространстве $ \langle X,W \rangle > b $.

Доказательство. $$ \langle X_0,W \rangle = b \quad \Rightarrow \quad \langle X_0+tW,W \rangle = \langle X_0,W \rangle + t \langle W,W \rangle = b + t \langle W,W \rangle > b \quad \mbox{при} \ t>0 \, . $$ ♦

Если некоторое непустое множество $ \mathbb S_1 \subset \mathbb R^n $ принадлежит замкнутому полупространству, а другое множество $ \mathbb S_2 $ не принадлежит этому полупространству (т.е. лежит в другом, открытом, полупространстве), то говорят, что гиперплоскость отделяет множество $ \mathbb S_1 $ от множества $ \mathbb S_2 $ или же, что она является для этих множеств разделяющей гиперплоскостью²⁾.

Пример. Для множеств $ \mathbb S_1 $ (фиолетового, состоящего из двух областей) и $ \mathbb S_2 $ (зеленого, точечного)

прямая $ 2x_1+x_2=2 $ является разделяющей:

♦

Не для любой пары множеств существует разделяющая гиперплоскость. Но, по крайней мере, для выпуклых множеств существует:

Теорема [Минковского о разделяющей гиперплоскости]³⁾. Для непересекающихся непустых выпуклых множеств $ \mathbb S_1 $ и $ \mathbb S_2 $ существует разделяющая их гиперплоскость $ \langle X, W \rangle = b $. Если оба множества замкнуты и хотя бы одно из них компактно, то разделение может быть произведено в виде строгих неравенств

$$ \langle X,W \rangle > b \quad \mbox{и} \quad \langle X,W \rangle < b \, . $$

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

Задача. Для точечных множеств $ \mathbb S_1 $ и $ \mathbb S_2 $ построить разделяющую их гиперплоскость.

Поставленная задача не всегда разрешима, а если и разрешима, то, как правило, разрешима не единственным способом. Из всего множества разделяющих гиперплоскостей выделяют наиболее удаленную от обоих множеств, т.е. такую, расстояние от которой до ближайшей точки $ \mathbb S_1 \cup \mathbb S_2 $ максимально возможно. Такая гиперплоскость называется оптимальной разделяющей гиперплоскостью⁴⁾. Геометрически очевидно, что в случае существования такой гиперплоскости, она должна быть равноудаленной от обоих множеств, т.е. должны существовать точки $ X_1 \in \mathbb S_1 $ и $ X_2 \in \mathbb S_2 $, находящиеся на одинаковом расстоянии от гиперплоскости — в противном случае оптимальную гиперплоскость можно было бы «подвинуть».

Также очевидно, что не на всякой равноудаленной от $ \mathbb S_1 $ и $ \mathbb S_2 $ гиперплоскости достигается максимум расстояния до этих множеств.

Теорема. Для различных точек $ X_1 $ и $ X_2 $ оптимальная разделяющая гиперплоскость задается уравнением

$$ \langle X- X_c, X_1-X_2 \rangle = 0 \quad \mbox{где} \ X_c:= \frac{1}{2} (X_1+X_2) \, . $$ Расстояние от нее до любой из точек $ X_1 $ и $ X_2 $ равно $$ \frac{1}{2} |X_1-X_2| \, . $$

Доказательство. Точка $ X_c $ определяет середину отрезка $[X_1,X_2]$. Все разделяющие точки $ X_1, X_2 $ и равноудаленные от них гиперплоскости должны содержать точку $ X_c $. Уравнение любой такой гиперплоскости можно представить в виде $$ \langle X- X_c, A \rangle = 0 $$ при некотором векторе $ W $ единичной длины: $ |W|:=\sqrt{w_1^2+\dots+w_n^2}=1 $. Расстояние от точки $ X_1 $ до этой гиперплоскости равно $$ | \langle X_1- X_c, W \rangle | = | \langle X_2- X_c, W \rangle | \, , $$ причем числа под модулями имеют разные знаки. Пусть, для определенности, $ \langle X_1- X_c, W \rangle>0 $. Мы хотим вычислить $$ \max \, \langle X_1- X_c, W \rangle>0 \quad \mbox{при} \ W \in \mathbb R^n, |W|=1 \, . $$ Решаем эту задачу условной оптимизации методом множителей Лагранжа. Вводим множитель Лагранжа $ \lambda $ и разыскиваем стационарные точки полинома $$ L(w_1,\dots,w_n; \lambda):= \langle X_1- X_c, W \rangle - \lambda \langle W, W \rangle = \langle X_1- X_c, W \rangle - \lambda (w_1^2+\dots+w_n^2-1) \, . $$ Они определяются из системы уравнений $$ \frac{\partial L}{\partial w_1}=0,\dots, \frac{\partial L}{\partial w_n}=0, \frac{\partial L}{\partial \lambda}=0 $$ которую можно переписать в векторном виде $$ X_1-X_c = 2\lambda W, \ \langle W, W \rangle=1 \, . $$ Первое из этих уравнений означает, что вектор нормали $ W $ к искомой плоскости должен быть коллинеарен вектору $ X_1-X_c $, а, фактически, вектору $ X_1-X_2=\vec{X_2X_1} $. Таким образом, мы знаем точку на гиперплоскости и ее вектор нормали. Отдельно надо бы доказать, что на этой гиперплоскости достигается именно максимум расстояния до точек $ X_1 $ и $ X_2 $. Когда-нибудь доделаю… ♦

Пример. Построить оптимальную разделяющую гиперплоскость для точек

$$ X_1=(1,-1,2,3) \quad \mbox{ и } \quad X_2= (-5, 1, 2, 5) \, . $$

Решение. Имеем $$ X_с:=\frac{1}{2} (X_1+X_2) = (-2,0,2,4) \ , \ X_1-X_2=(6,-2,0,-2) \, . $$ Уравнение оптимальной разделяющей гиперплоскости $$ 6\, (x_1+2)-2\,x_2-2\,(x_4-4)=0 \quad \iff \quad 3\, x_1-x_2-x_4+10=0 \, . $$ Расстояние от нее до любой из точек $ X_1, X_2 $ равно $ \sqrt{11}/2 $. ♦

Пусть теперь множество $ \mathbb S_2 $ состоит из двух точек $ X_2,X_3 $, в то время как $ \mathbb S_1 $ — из одной $ X_1 $. Кажется осмысленным построить оптимальную разделяющую гиперплоскость сведением к предыдущему случаю: выбрать ближайшую к $ X_1 $ точку среди $ X_2 $ и $ X_3 $ и построить для этой пары оптимальную разделяющую прямую. К сожалению, такой подход не всегда сработает должным образом. Рассмотрим случай $ \mathbb R^2 $ и задачу будем решать в постановке об оптимальной разделяющей прямой. Пусть точки $ X_1 $ и $ X_2 $ фиксированы, а расположение $ X_3 $ можно варьировать как изображено на рисунках (с соблюдением условия $ |X_1X_2|<|X_1X_3| $) Пока точка $ X_3 $ лежит вне желтой полосы, серединной линией которой является прямая, оптимально разделяющая точки $ X_1 $ и $ X_2 $, эта же прямая остается оптимальной разделяющей и для множеств $ \mathbb S_1 $ и $ \mathbb S_2 $. Ситуация изменится когда $ X_3 $, двигаясь влево, войдет внутрь полосы: расстояние от разделяющей прямой до $ X_3 $ становится меньше расстояния до $ X_2 $. Что же теперь будет решением задачи? — Средняя линия треугольника $ X_1X_2X_3$, а именно та, что проходит через середины сторон $ [X_1,X_2] $ и $[X_1X_3]$. Что произойдет при дальнейшем дрейфе точки $ X_3 $ влево? — Эта прямая вращается вокруг середины отрезка $[X_1X_2]$ по часовой стрелке и остается решением задачи до тех пор пока будет существовать треугольник $ X_1X_2X_3$.

С увеличением количества точек во множествах $ \mathbb S_1 $ и $ \mathbb S_2 $ анализ возможных сценариев для расположения оптимальной разделяющей прямой усложняется. Но кое-какие гипотезы можно уже сформулировать.

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

2. При построении этой полосы анализируются расстояния между парами точек разделяемых множеств. Однако, как показывают примеры, рассмотрению подлежат не всякие такие пары. На нижнем рисунке точки $ X_1 $ и $ X_2 $ явно не влияют на выбор разделяющей полосы. Почему? — Да потому, что каждая из них лежит «внутри» многоугольника, образованного другими точками соответствующего множества. Фактически мы пытаемся свести задачу от точечных множеств к фигурам — выпуклым многоугольникам. Расстояние между подобными объектами всегда достигается на их границах: либо в вершинах (точках из рассматриваемых множеств) либо же на сторонах (соединяющих две такие вершины).

Теперь переносим эти наводящие геометрические соображения в многомерное пространство.

Замкнутое полупространство называется опорным для непустого множества $ \mathbb S\subset \mathbb R^n $ если оно содержит $ \mathbb S $ и, кроме того, хотя бы одна точка $ \mathbb S $ лежит в определяющей полупространство гиперплоскости. Сама гиперплоскость также называется опорной⁵⁾. Если точки множества $ \mathbb S $ лежат по обе стороны гиперплоскости, то говорят, что она рассекает $ \mathbb S $.

Пусть объекты некоторого конечного множества описываются числовыми значениями $ n $ конкретных признаков (параметров). Каждый объект может быть однозначно отнесен к одному из двух классов («враг-друг», «плюс-минус», «спуск-подъем» и т.п.). Имеется подозрение, что признаки и классы как-то коррелируют. Возможно, что близким (в смысле какого-то расстояния) наборам значений признаков соответствуют одинаковые классы.

Задача. Найти аналитический критерий, позволяющий по значениям вектора признаков $X:=(x_1,\dots,x_n) $ определять класс соответствующего объекта.

Этот аналитический критерий может быть представлен, например, в форме неравенств $$ h(X) > 0 \quad \mbox{ и } \quad h(X)<0 $$ относительно векторов пространства $ \mathbb R^n $ и некоторой (скалярной) функции $ h $ от $ n $ переменных, специально подобранной из особенностей задачи. Если бы, вдобавок, функция $ h(X) $ была непрерывной, то уравнение $ h(X)=0 $ задавало бы в $n$-мерном пространстве гиперповерхность, разделяющую два класса — по типу разделяющей прямой для множеств на плоскости из примеров предыдущего пункта.

Теоретически проблема может быть конструктивно решена — ну, хотя бы, для конечных множеств. На практике же, рассматриваемое множество может оказаться очень большим, содержащим миллионы объектов. И поставленную задачу приходится решать в другой постановке. Предполагается, что из двух исходных подмножеств (классов) $ \mathbb S_1 $ и $ \mathbb S_2 $ осуществляются случайные выборки сравнительно небольших подмножеств — $ \widehat{\mathbb S}_1 $ и $ \widehat{\mathbb S}_2 $ соответственно. Множество $ \widehat{\mathbb S}_1 \cup \widehat{\mathbb S}_2 $ называется обучающим⁶⁾. Разделяющая гиперповерхность строится уже только для этих «подподмножеств». Если такую гиперповерхность удается построить, то задающую ее функцию $ h(X) $ тестируют на случайной выборке векторов из $ \mathbb S_1 \setminus \widehat{\mathbb S}_1 $ и из $ \mathbb S_2 \setminus \widehat{\mathbb S}_2 $. Если тестирование проходит успешно, то принимают функцию $ h(X) $ за истинный классификатор.

Решать задачу построения классификатора начинают с подбора кандидата из самого простого класса функций — линейных от значений признаков: $$ h(X):=\langle X, W \rangle - b =w_1x_1+\dots+w_nx_n-b \quad \mbox{при} \ W \ne \mathbb O \, . $$ Иными словами, пытаются строить разделяющую множества $ \mathbb S_1 $ и $ \mathbb S_2 $ гиперплоскость. Причем начинают процесс с разделения обучающих подмножеств $ \widehat{\mathbb S}_1 $ и $ \widehat{\mathbb S}_2 $.