Пример. Найти прямую, проходящую через точку $ X_0=[6,5,1,-1]^{^{\top}} $ и пересекающую плоскости

$$ \mathbb M_1 = \left\{ X\in \mathbb R^4 \left| \begin{array}{rrrrl} -x_1&+2\,x_2&+x_3&&= 1, \\ x_1&&&+x_4 &=1 \end{array} \right. \right\} $$ и $$ \mathbb M_2 = \left\{ X=[4+t,4+2\,t, 5+3\,t,4+4\, t]^{^{\top}} \bigg| t\in \mathbb R \right\} \ . $$

Решение. Ищем прямую в виде $$ \mathbb M=\left\{ X=X_0 + \alpha Z \big| \alpha \in \mathbb R \right\} \ , $$ где $ Z=[z_1,z_2,z_3,z_4]^{^{\top}} $ — направляющий вектор искомой прямой, а $ \alpha_{} $ — скаляр (параметр). Условие пересечения $ \mathbb M $ и $ \mathbb M_1 $ состоит в том, что при некотором значении $ \alpha=\alpha_1 $ совпадают координаты на плоскости $ \mathbb M_1 $ и вдоль прямой $ \mathbb M $. $$ \left\{ \begin{array}{rrrrr} -(6+\alpha_1z_1)&+2\,(5+\alpha_1z_2)&+(1+\alpha_1z_3)& &=1 , \\ (6+\alpha_1z_1)&&&+(-1+\alpha_1z_4) &=1 \end{array} \right. \ \iff $$ $$ \iff \ \left\{ \begin{array}{lr} \alpha_1(-z_1+2\,z_2+z_3)&=-4,\\ \alpha_1(z_1+z_4)&=-4. \end{array} \right. $$ Рассмотрев эти уравнения как систему относительно $ \alpha_1 $, выпишем необходимое и достаточное условие ее совместности: $$ \operatorname{rank} \left( \begin{array}{c} -z_1+2\,z_2+z_3 \\ z_1+z_4 \end{array} \right) = \operatorname{rank} \left( \begin{array}{cr} -z_1+2\,z_2+z_3, & -4 \\ z_1+z_4, & -4 \end{array} \right) \ . $$ Последнее удовлетворяется тогда и только тогда, когда $$ \left| \begin{array}{cr} -z_1+2\,z_2+z_3, & -4 \\ z_1+z_4, & -4 \end{array} \right| = 0 \ \iff \ 2\, z_1 -2\, z_2 - z_3 +z_4 =0 \ . $$ Условие пересечения прямых $ \mathbb M $ и $ \mathbb M_2 $ выписывается аналогично: система $$ \left\{ \begin{array}{rl} 6+\alpha_2 z_1 &=4+t, \\ 5+\alpha_2 z_2 &=4+2\,t, \\ 1+\alpha_2 z_3&=5+3\,t, \\ -1+\alpha_2 z_4&=4+4\,t, \end{array} \right. \quad \iff \quad \left\{ \begin{array}{rr} \alpha_2 z_1-\ \, t =&-2, \\ \alpha_2 z_2-2\,t =&-1, \\ \alpha_2 z_3-3\,t=&4, \\ \alpha_2 z_4-4\,t=&5 \end{array} \right. $$ должна быть совместна относительно $ \alpha_2 $ и $ t_{} $. Необходимое и достаточное условие: $$ \operatorname{rank} \left( \begin{array}{rr} z_1 & -1 \\ z_2 & -2 \\ z_3 & -3 \\ z_4 & -4 \end{array} \right) = \operatorname{rank} \left( \begin{array}{rrr} z_1 & -1 & -2\\ z_2 & -2 & -1 \\ z_3 & -3 & 4 \\ z_4 & -4 & 5 \end{array} \right) \ . $$ Поскольку число слева $ \le 2 $, а справа $ \ge 2 $, то имеет смысл выяснить при каких условиях на $ z_1,z_2,z_3,z_4 $ расширенная матрица имеет ранг в точности равный $ 2_{} $. $$ \left( \begin{array}{rrrr} z_1 & z_2 & z_3 & z_4 \\ -1 & -2 &-3 &-4 \\ -2 & -1 & 4 & 5 \end{array} \right) \rightarrow \ \left( \begin{array}{rrrr} -1 & -2 &-3 &-4 \\ -2 & -1 & 4 & 5 \\ z_1 & z_2 & z_3 & z_4 \end{array} \right) \rightarrow $$ $$ \rightarrow \left( \begin{array}{rccc} 1 & 2 &3 &4 \\ 0 & 3 &10 & 13 \\ 0 & z_2-2\,z_1 & z_3-3\,z_1 & z_4-4\,z_1 \end{array} \right) \rightarrow $$ $$ \rightarrow \left( \begin{array}{rrcc} 1 & 2 &3 &4 \\ 0 & 3 &10 & 13 \\ 0 & 0 & 11/3\,z_1 -10/3\,z_2+z_3 & 14/3\,z_1 - 13/3\,z_2+z_4 \end{array} \right) \ . $$ Ранг этой матрицы будет равен $ 2_{} $ тогда и только тогда, когда $$ \left\{ \begin{array}{rrrrl} 11/3z_1 &- 10/3z_2&+z_3& &=0, \\ 14/3z_1 & - 13/3z_2& &+z_4&=0. \end{array} \right. $$ Объединив эти условия с полученным выше, составим систему для определения координат направляющего вектора прямой: $$ \left\{ \begin{array}{rrrrl} 2\, z_1 &-2\, z_2& - z_3& +z_4& =0, \\ 11\,z_1 &-10\,z_2&+3\,z_3& &=0, \\ 14\,z_1 & -13\,z_2& &+3\,z_4&=0 \end{array} \right. \iff \ \left\{ \begin{array}{rrrrl} 2\, z_1 &-2\, z_2& - z_3& +z_4& =0, \\ z_1 &&+8\,z_3&-5\,z_4 &=0, \\ & z_2&+7\,z_3 &-4\,z_4&=0 \end{array} \right. $$ $$ \iff \ \left\{ \begin{array}{rrrrl} z_1 && +8\, z_3& -5\,z_4& =0, \\ &z_2 &+7\,z_3&-4\,z_4 &=0, \\ & &-3\,z_3 &+3\,z_4&=0 \end{array} \right. \Rightarrow \ \ \begin{array}{ccc|c} z_1 & z_2 & z_3 & z_4 \\ \hline -3 & -3 & 1 & 1 \end{array} $$

Ответ. $ \mathbb M=\left\{ [6-3\, \alpha,\ 5-3\, \alpha,\ 1+ \alpha,\ -1+ \alpha ]^{^{\top}} \ \bigg| \ \alpha \in \mathbb R \right\} $.

Пусть заданы вещественные числа $ a_1,\dots, a_n, b $, причем не все $ \{a_j\}_{j=1}^n $ равны нулю. Уравнение $$ a_1x_1+a_2x_2+\dots+a_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, A \rangle = b \quad \mbox{при} \quad A:=(a_1,\dots,a_n) \, . $$ В этом случае вектор $ A $ интерпретируется как вектор нормали к гиперплоскости. Действительно, если $ X_1 $ и $ X_2 $ — две точки, лежащие на гиперплоскости, то вектор $ A $ перпендикулярен вектору $ \vec{X_1X_2} $: $$ \langle X_1, A \rangle = b, \ \langle X_2, A \rangle = b \quad \Rightarrow \quad \langle X_2-X_1, A \rangle = 0 \, . $$

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

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

Доказательство. $$ \langle X_0,A \rangle = b \quad \Rightarrow \quad \langle X_0+tA,A \rangle = \langle X_0,A \rangle + t \langle A,A \rangle = b + t \langle A,A \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,A \rangle = b $. Если оба множества замкнуты и хотя бы одно из них компактно, то разделение может быть произведено в виде строгих неравенств

$$ \langle X,A \rangle > b \quad \mbox{и} \quad \langle X,A \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 $$ при некотором векторе $ A $ единичной длины: $ |A|:=\sqrt{a_1^2+\dots+a_n^2}=1 $. Расстояние от точки $ X_1 $ до этой гиперплоскости равно $$ | \langle X_1- X_c, A \rangle | = | \langle X_2- X_c, A \rangle | \, , $$ причем числа под модулями имеют разные знаки. Пусть, для определенности, $ \langle X_1- X_c, A \rangle>0 $. Мы хотим вычислить $$ \max \, \langle X_1- X_c, A \rangle>0 \quad \mbox{при} \ A \in \mathbb R^n, |A|=1 \, . $$ Решаем эту задачу условной оптимизации методом множителей Лагранжа. Вводим множитель Лагранжа $ \lambda $ и разыскиваем стационарные точки полинома $$ L(a_1,\dots,a_n; \lambda):= \langle X_1- X_c, A \rangle - \lambda \langle A, A \rangle = \langle X_1- X_c, A \rangle - \lambda (a_1^2+\dots+a_n^2-1) \, . $$ Они определяются из системы уравнений $$ \frac{\partial L}{\partial a_1}=0,\dots, \frac{\partial L}{\partial a_n}=0, \frac{\partial L}{\partial \lambda}=0 $$ которую можно переписать в векторном виде $$ X_1-X_c = 2\lambda A, \ \langle A, A \rangle=1 \, . $$ Первое из этих уравнений означает, что вектор нормали $ A $ к искомой плоскости должен быть коллинеарен вектору $ 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_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 $ анализ возможных сценариев для расположения оптимальной разделяющей прямой усложняется. Но кое-какие гипотезы можно уже сформулировать. Прямая, оптимально разделяющая точечные множества на плоскости, задает серединную линию «контрольно-следовой полосы» между этими множествами: полосы максимально возможной ширины, внутри которой нет точек обоих множеств, а на каждой границе (прямой, параллельной серединной) лежит хотя бы одна точка одного из разделяемых множеств.

Анализ задачи теряет подкрепление геометрическими соображениями при переходе к случаю многомерного пространства.

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