!!§!! Вспомогательная страница к разделу
☞
((:linear_space ЛИНЕЙНЫЕ ПРОСТРАНСТВА)).
==Линейные многообразия в R^n==
~~TOC~~
!!П!! **Пример.** Найти прямую, проходящую через точку $ 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 $ ((:euclid_space#opredelenija скалярное произведение)) векторов $ 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 $ или же, что она является для этих множеств **разделяющей гиперплоскостью**[[separating hyperplane]].
!!П!! **Пример.** Для множеств $ \mathbb S_1 $ (фиолетового, состоящего из двух областей) и $ \mathbb S_2 $
(зеленого, точечного)
{{ :linear_space:separ1.png?600 |}}
прямая $ 2x_1+x_2=2 $ является разделяющей:
{{ :linear_space:separ3.png?600 |}}
♦
Не для любой пары множеств существует разделяющая гиперплоскость. Но, по крайней мере, для выпуклых множеств существует:
!!Т!! **Теорема [Минковского о разделяющей гиперплоскости]**[[Hyperplane separation theorem.]]. //Для непересекающихся непустых выпуклых множеств// $ \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 $ максимально возможно. Такая гиперплоскость называется **оптимальной разделяющей гиперплоскостью**[[Maximum-margin hyperplane.]]. Геометрически очевидно, что в случае существования такой гиперплоскости, она должна быть равноудаленной от обоих множеств, т.е. должны существовать точки $ X_1 \in \mathbb S_1 $ и
$ X_2 \in \mathbb S_2 $, находящиеся на одинаковом расстоянии от гиперплоскости. Также очевидно, что не на всякой равноудаленной от $ \mathbb S_1 $ и $ \mathbb S_2 $ гиперплоскости достигается максимум расстояния до этих множеств.
{{ :linear_space:separ4.png?600 |}}
!!Т!! **Теорема.** //Для различных точек// $ 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 $ до этой гиперплоскости ((:algebra2/optimiz/distance#rasstojanie_ot_tochki_do_linejnogo_mnogoobrazija_ploskosti равно))
$$
| \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 $ можно варьировать как изображено на рисунках
{{ :linear_space:separ5.png?600 |}}
Пока точка $ X_3 $ лежит вне желтой полосы, серединной линией которой является прямая, оптимально разделяющая точки $ X_1 $ и
$ X_2 $, эта же прямая остается оптимальной разделяющей и для множеств $ \mathbb S_1 $ и $ \mathbb S_2 $. Ситуация изменится когда $ X_3 $, двигаясь влево, войдет внутрь полосы: расстояние от разделяющей прямой до $ X_3 $ становится меньше расстояния до $ X_2 $.
{{ :linear_space:separ6.png?400 |}}
Что же теперь будет решением задачи? --- Средняя линия треугольника $ X_1X_2X_3$, а именно та, что проходит через середины сторон $ [X_1,X_2] $ и $[X_1X_3]$.
{{ :linear_space:separ7.png?400 |}}
Что произойдет при дальнейшем дрейфе точки $ 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 $ лежит в определяющей полупространство гиперплоскости. Сама **гиперплоскость** также называется **опорной**[[supporting hyperplane]]. Если точки множества $ \mathbb S $ лежат по обе стороны гиперплоскости, то говорят, что она **рассекает**
$ \mathbb S $.
==Конусы==