Багатовимірні простори

Вступ

Ми живемо в 3-вимірному просторі. Воно для нас настільки звичне, що властивості просторів більшого числа вимірів часто виявляються дуже несподіваними. Тим не менш, саме з такими просторами мають справу в машинному навчанні, де об'єкти зазвичай характеризуються n речовими ознаками. Розглянемо деякі математичні аспекти багатовимірності.

Гіперкуб

Нормуванням завжди можна зробити так, щоб значення кожної ознаки належали інтервалу від 0 до 1. Тоді всі об'єкти представимі точками всередині n-вимірного одиничного гіперкуба в просторі ознак.

Одиничний 2-вимірний куб (квадрат на площині) має 4 вершини з координатами (0,0), (0,1), (1,0), (1,1). У 3-вимірного куба їх 8.

У просторі n вимірів: x = {x¹,...,xⁿ}. Нехай одна вершина куба знаходиться на початку координат: {0,0,...,0} (n нулів). Інші вершини нумеруються всіма можливими послідовностями n нулів і одиниць: {0,0,...,0}, {1,0,...,0}, ..., {1,1,...,1}, тому:

Гіперкуб у n вимірах має 2ⁿ вершин

При великих n гіперкуб дуже "колючий" об'єкт. Наприклад, при n=32 у нього 4'294'967'296 вершин.

З кожної $2^n$ вершин гіперкуба виходить $n$ ребер (для вершини (0,0,...,0) це $n$ координатних осей). Тому всього у гіперкуба $n\,2^n/2=n\,2^{n-1}$ ребер.

Діагональ, що з'єднує точки {0,0,...,0} і {1,1,...,1}, має довжину $\sqrt{n}$ (таких довгих діагоналей $n$ штук). "Сторона" гіперкуба - це $(n-1)$-вимірний куб з $2^{n-1}$ вершинами (у 3-куба 6 сторін-квадратів). Таких сторін у гіперкуба $2\,n$ штук. Крім цього, гіперкуб можна отримати з'єднанням ребрами вершин двох $(n-1)$-вимірних кубів (для "звичайного" куба це два квадрати). При цьому знову виходить:

Гіпотеза компактності

Припустимо, що ми хочемо рівномірно заповнити простір ознак всередині гіперкуба точками (навчальними об'єктами). Для цього кожну ознаку (вісь) розіб'ємо на k рівних частин. У результаті вийде kⁿ кубиків, у кожен з яких можна помістити точку. Зрозуміло, що навіть при k = 2 і n = 32 це зробити практично неможливо. Таким чином, багатовимірний простір дуже великий.

Необхідно прагнути до такого відбору ознак об'єктів, при якому відповідні їх класам образи не були б занадто складними. Іноді це формулюють у вигляді гіпотези компактності:

Кожен клас повинен займати відносно компактну область у n-вимірному просторі, таким чином щоб і різні класи виявлялися віддільними одне від одного порівняно простими поверхнями (в ідеалі гіперплощинами).

Куля

Множина рівновіддалених точок від даної (центра) називається сферою. Простір всередині сфери називається кулею. Куля, вписана в гіперкуб, це дуже "маленький" об'єкт. У $n$-вимірному просторі куля радіуса $R$ має такі об'єм $V_n$ і площу поверхні $S_n$: $$ V_n = C_n\cdot R^n,~~~~~~~~~~~~S_n = C_n\cdot n\,R^{n-1},~~~~~~~де~~~~~~C_n = \frac{ \pi^{n/2} }{\Gamma({n\over 2}+1)},~~~~~C_{2k} = \frac{\pi^k}{k!} $$ де $\Gamma(x)$ - гамма-функція: $\Gamma(1)=1,~~~$ $\Gamma(1/2)=\sqrt{\pi}$, $~~\Gamma(z+1) = z\,\Gamma(z)~~$ і $~~\Gamma(z+\alpha)=z^\alpha\,\Gamma(z)$ при $z \gg 1$.

В одиничний гіперкуб можна вписати кулю з радіусом R=1/2. Її об'єм при n=10 дорівнює V₁₀=0.0025, а при n=32 він зникаюче малий: V₃₂=10^-15. Хоча куля "притискається" до граней гіперкуба, її оточує дуже багато (2ⁿ) кутів.

Ще одна особливість n-вимірної кулі полягає в тому, що майже весь її об'єм зосереджений біля поверхні. Дійсно, розглянемо дві вкладені одна в одну кулі з радіусами $R$ і $R-\Delta R$. Різниця їх об'ємів дорівнює об'єму сферичного шару між ними. $$ \frac{\Delta V}{V} = \frac{R^n - (R-\Delta R)^n}{R^n} = 1 - \left(1-\frac{\Delta R}{R}\right)^n. $$ Відношення об'єму шару до об'єму кулі радіуса $R$ наведено на рисунку справа для різних розмірностей простору $n$.

Нехай куля рівномірно (з постійною щільністю) заповнена об'єктами. Випадково вибраний об'єкт (при великих $n$) майже напевно виявиться біля поверхні кулі.

Нехай об'єкти даного класу характеризуються деякими типовими (середніми) значеннями ознак з невеликим розкидом навколо цих середніх значень. Тоді образ цього класу є центром кулі в n-вимірному просторі. Чим менший розкид навколо середнього, тим менший радіус такої кулі-образу. Якщо у різних ознак розкид має різну амплітуду, то куля стає еліпсоїдом. Лінійним перетворенням еліпсоїд завжди можна перетворити на кулю. Однак, якщо в просторі ознак існує кілька різних еліпсоїдів, то лінійним перетворенням перетворити на кулю можна тільки один з них.

Простори ембединга

При обробці текстів або зображень отримують вектори ознак, для яких як близькість використовується косинусна відстань. У цьому випадку основним об'єктом зручніше розглядати сферу одиничного радіуса. Для парних $n$ її об'єм дорівнює: $$ V_2=3.14,~~~~~~~V_{16}=0.23,~~~~~~~V_{32}=4\cdot 10^{-6},~~~~~~~V_{64}=3\cdot 10^{-20},~~~~~~~~V_n=C_n=\frac{\pi^{n/2}}{(n/2)!}. $$

$$ D(\mathbf{x},\mathbf{y}) = (\mathbf{x}-\mathbf{y})^2 = \mathbf{x}^2 + \mathbf{y}^2 - 2\,\mathbf{x}\cdot \mathbf{y} $$ $$ D(\mathbf{x},\mathbf{y}) = 2\,\bigr(1-\cos(\mathbf{x},\mathbf{y})\bigr). $$

Якщо на "поверхні" $(n-1)$-вимірної гіперсфери, провести $(n-2)$-вимірну сферу радіуса $r$, то відношення площі гіперсфери і об'єму сфери буде порядку: $$ \frac{S_n(R)}{V_{n-1}(r)} \approx \sqrt{2\pi n}\, \left(\frac{R}{r}\right)^{n-1} $$ Так, на одиничній $n$-гіперсфері $R=1$ проведемо ($n-1$)-сферу радіуса $r=1/2$ (пів радіана або 28°). Тоді в 100-вимірному просторі, таких непересічних сфер може бути порядку $2^{100}$. Отже в них можуть розміститися кластери об'єктів різних класів. Багатовимірний простір суттєво більш "місткий".

Якщо компоненти вектора є випадковими гаусовими числами $\varepsilon$ з нульовим середнім і одиничною дисперсією, то середнє значення квадрата його довжини дорівнює розмірності простору: $$ \langle \mathbf{x}^2\rangle = \langle \varepsilon^2_1+...+\varepsilon^2_1\rangle = n. $$ При цьому ймовірність розподілу квадрата довжини $D=\mathbf{x}^2$ при великих $n$ в околі $n-2$ має вузький пік (усі точки "збираються" в околі сфери): $$ \frac{e^{-(\varepsilon^2_1+...+\varepsilon^2_n)/2}} {(2\pi)^{n/2}}\, d\varepsilon_1...d\varepsilon_n = \frac{\Omega_n}{(2\pi)^{n/2}}\, e^{-r^2/2}\, r^{n-1}\,dr = \frac{\Omega_n}{2(2\pi)^{n/2}}\, e^{-D/2}\, D^{n/2-1}\,dD $$ Змоделюємо це за допомогою бібліотеки numpy:

X = np.random.normal(0.0, 1, (10000, dim))/dim**0.5        
R2 = (X*X).sum(axis=1)

m-вимірні площини

Нехай $\mathbf{x}=\{x^1,...,x^n\}$ - точка в $n$-вимірному просторі (верхній індекс - номер координати). Поверхню розмірності $m$ можна описати параметричним чином $$ \mathbf{x} = \mathbf{f}(t_1,...,t_m), $$ де $t_k$ - набір скалярних параметрів (їхня кількість дорівнює розмірності поверхні). Наприклад, одинична сфера в 3-вимірному просторі описується двома (2-вимірний об'єкт) кутами $\{t_1,t_2\}=\{\theta,\phi\}$: $$ x = \sin \theta \cos\phi, ~~~~~y = \sin \theta \sin\phi,~~~~~z = \cos \theta. $$ Найпростішою $m$-вимірною поверхнею є площина. Нехай $\mathbf{e}_k=\{\mathbf{e}_1,...,\mathbf{e}_m\}$ - набір $m$ одиничних, попарно ортогональних векторів ($\mathbf{e}_k\mathbf{e}_p=\delta_{pk}$, де $\delta_{pk}$ - символ Кронекера). Тоді рівняння площини має вигляд: \begin{equation}\label{plane_eq} \mathbf{x}= \mathbf{x}_0 + \sum^m_{k=1} t_k\mathbf{e}_k. \end{equation} Параметри $\{t_1,...,t_m\}$ виступають декартовими координатами в $m$-вимірному просторі з базисом $\{\mathbf{e}_1,...,\mathbf{e}_m\}$. Вектор $\mathbf{x}_0$ задає положення початку координат (точка $n$-простору, в якій на площині всі координати $t_k$ рівні нулю). Рівняння (\ref{plane_eq}) є першим наближенням розкладу в ряд Тейлора довільної поверхні $\mathbf{x} = \mathbf{f}(t_1,...,t_m)$ в околі точки $t_1=...=t_m=0$. Якщо $m=1$, то (\ref{plane_eq}) буде рівнянням прямої (одновимірний об'єкт). При $m=2$ ми маємо двовимірну площину і т.д.

Відстань до $m$-площини

Отримаємо вираз для найкоротшої евклідової відстані $(\mathbf{x}-\mathbf{X})^2$ від довільної точки $\mathbf{X}$ до $m$-площини (\ref{plane_eq}). Для цього необхідно знайти параметри $t_k$ для яких ця відстань мінімальна: $$ d^2 = \bigr(\mathbf{x}_0-\mathbf{X} + \sum^m_{k=1} t_k\mathbf{e}_k\bigr)^2 = \min. $$ Візьмемо похідну за $t_p$, прирівняємо її нулю і врахуємо ортонормованість векторів $\mathbf{e}_k$: $$ \bigr(\mathbf{x}_0-\mathbf{X} + \sum^m_{k=1} t_k\mathbf{e}_k\bigr)\,\mathbf{e}_p = (\mathbf{x}_0-\mathbf{X})\,\mathbf{e}_p + t_p = 0 ~~~~~~~~\Rightarrow~~~~~~~t_p = -(\mathbf{x}_0-\mathbf{X})\,\mathbf{e}_p. $$ Підставимо ці $t_p$ у квадрат відстані $d^2$: $$ d^2 = \bigr(\mathbf{x}_0-\mathbf{X} - \sum^m_{k=1} \bigr[(\mathbf{x}_0-\mathbf{X})\,\mathbf{e}_k \bigr]\,\mathbf{e}_k\bigr)^2. $$ Підносячи до квадрата (знову з урахуванням ортогональності), цей вираз можна переписати в такому вигляді: \begin{equation}\label{d2_to_plane} d^2 = \bigr(\mathbf{x}_0-\mathbf{X}\bigr)^2 - \sum^m_{k=1} \bigr[(\mathbf{x}_0-\mathbf{X})\,\mathbf{e}_k \bigr]^2. \end{equation} Проекція точки $\mathbf{X}$ на площину отримується підстановкою знайдених параметрів $t_k$ в рівняння площини (\ref{plane_eq}): \begin{equation}\label{projec_coord} \mathbf{X} ~\mapsto~\mathbf{x}=\mathbf{x}_0 + \sum^m_{k=1} \bigr[(\mathbf{X}-\mathbf{x}_0)\,\mathbf{e}_k\bigr]\mathbf{e}_k. \end{equation}

Гіперплощина

Гіперплощиною в $n$-вимірному просторі називають $m=(n-1)$-вимірну площину. (у 2-вимірності це лінія, а в 3-вимірності "звичайна" площина). Гіперплощину завжди можна провести через $n$ точок. Відповідно, вона задається за допомогою $n$ чисел (наприклад, одиничним ($\boldsymbol{\omega}^2=1$) вектором нормалі (перпендикуляра) до площини $\boldsymbol{\omega} = \{\omega^1,....,\omega^n\}$ і параметром зсуву $\omega_0$.

Нехай гіперплощина проходить через точку $\mathbf{x}_0$ і має вектор нормалі $\boldsymbol{\omega}$. Тоді відстань d від гіперплощини до деякої точки $\mathbf{X}=\{X^1,...,X^n\}$ обчислюється за формулою

При цьому $d > 0$, якщо точка $\mathbf{X}$ лежить з того боку площини, куди вказує вектор $\boldsymbol{\omega}$ і $d < 0$, якщо з протилежного. Коли $d=0$ - точка $\mathbf{X}$ лежить у площині. Зміна параметра $\omega_0$ зсуває площину паралельним чином у просторі. Якщо $\omega_0$ зменшується, то площина зміщується в напрямку вектора $\boldsymbol{\omega}$ (відстань менша), а якщо $\omega_0$ збільшується - площина зміщується проти вектора $\boldsymbol{\omega}$. Це безпосередньо випливає з наведеної вище формули.

◄ Запишемо вектор $\mathbf{X}-\mathbf{x}_0$, що починається в точці $\mathbf{x}_0$ (що лежить у площині) і спрямований у точку $\mathbf{X}$ (вектори складаються за правилом трикутника). Точка $\mathbf{x}_0$ вибрана в основі вектора $\boldsymbol{\omega}$, тому $\boldsymbol{\omega}$ і $\mathbf{X}-\mathbf{x}_0$ колінеарні (лежать на одній прямій). Якщо вектор $\boldsymbol{\omega}$ одиничний ($\boldsymbol{\omega}^2=1$), то скалярний добуток векторів $d=\boldsymbol{\omega}\,(\mathbf{X}-\mathbf{x}_0)$ дорівнює відстані $d$ точки $\mathbf{X}$ до площини.

Якщо довжина $\omega=|\boldsymbol{\omega}|$ вектора $\boldsymbol{\omega}$ відмінна від одиниці, то $d$ в $\omega$ разів більша ($\omega > 1$) або менша ($\omega < 1$) евклідової відстані в $n$-вимірному просторі. Коли вектори $\boldsymbol{\omega}$ і $\mathbf{X}-\mathbf{x}_0$ спрямовані в протилежні сторони: $d < 0$. ►

Якщо простір має n вимірів, то гіперплощина це (n-1)-вимірний об'єкт.
Вона ділить весь простір на дві частини. Для наочності розглянемо 2-вимірний простір. Гіперплощиною в ньому буде пряма лінія (одновимірний об'єкт). Праворуч на малюнку кружечок зображує одну точку простору, а хрестик - іншу. Вони розташовані по різні боки від лінії (гіперплощини). Якщо довжина вектора ω набагато більша за одиницю, то і відстані d від точок до площини за модулем будуть суттєво більшими за одиницю.

Рівняння гіперплощини, аналогічно $m$-площині, можна записати в параметричному вигляді за допомогою $n-1$ векторів базису $\{\mathbf{e}_1,...,\mathbf{e}_{n-1}\}$. Усі ці вектори ортогональні вектору нормалі: $\boldsymbol{\omega}\mathbf{e}_k=0$.

Симплекс

Симплексом називають n вимірне узагальнення трикутника 2-вимірного простору. В 3-вимірності це тетраедр (рисунок праворуч). Через n точок в n-вимірному просторі можна провести гіперплощину. Відповідно n+1 точок у загальному випадку не лежать на одній гіперплощині і утворюють симплекс з n+1 вершинами. Якщо всі ребра (відстані між парами вершин) однакові - симплекс називають правильним. Навпроти кожної з n+1 вершин лежить гіперплощина (в яку ця вершина не потрапила).

Кожна з $n+1$ вершин симплекса з'єднана з усіма іншими вершинами ребрами. Відповідно, число ребер дорівнює $n\,(n+1)/2$.

Об'єм правильного симплекса з одиничними ребрами дорівнює: $$ V_n = \frac{\sqrt{n+1}}{n!\,2^{n/2}}. $$ Як і куля, це дуже "маленький" об'єкт.

Нехай всередині сфери знаходяться об'єкти одного класу, а поза нею - об'єкти іншого класу. Для їх розділення потрібна нейронна мережа з одним прихованим шаром, що має принаймні n+1 нейронів у прихованому шарі. Вони утворюють n+1 гіперплощин симплекса (можливо зі згладженими кутами, якщо довжини векторів нормалі невеликі).

Трохи математики