Loading [MathJax]/extensions/TeX/boldsymbol.js

Многомерные пространства


Введение

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


Гиперкуб

Нормировкой всегда можно сделать так, чтобы значения каждого признака принадлежали интервалу от 0 до 1. Тогда все объекты представимы точками внутри n-мерного единичного гиперкуба в пространстве признаков.

Единичный 2-мерный куб (квадрат на плоскости) имеет 4 вершины с координатами (0,0), (0,1), (1,0), (1,1). У 3-мерного куба их 8.

В пространстве n измерений: x = {x1,...,xn}. Пусть одна вершина куба находится в начале координат: {0,0,...,0} (n нулей). Остальные вершины нумеруются всеми возможными последовательностями n нулей и единиц: {0,0,...,0}, {1,0,...,0}, ..., {1,1,...,1}, поэтому:

Гиперкуб в n измерениях имеет 2n вершин

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

Из каждой 2n вершин гиперкуба выходит n рёбер (для вершины (0,0,...,0) это n координатных осей). Поэтому всего у гиперкуба n2n/2=n2n1 рёбер.

Диагональ, соединяющая точки {0,0,...,0} и {1,1,...,1}, имеет длину n (таких длинных диагоналей n штук). "Сторона" гиперкуба - это (n1)-мерный куб с 2n1 вершинами (у 3-куба 6 сторон-квадратов). Таких сторон у гиперкуба 2n штук. Кроме этого, гиперкуб можно получить соединением рёбрами вершин двух (n1)-мерных кубов (для "обычного" куба это два квадрата). При этом снова получается:

число вершин: 2n1+2n1=2n,       число рёбер: (n1)2n2+(n1)2n2+2n1=n2n1.


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

Предположим, что мы хотим равномерно заполнить пространство признаков внутри гиперкуба точками (обучающими объектами). Для этого каждый признак (ось) разобьём на k равных частей. В результате получится kn кубиков, в каждый из которых можно поместить точку. Понятно, что даже при k = 2 и n = 32 это сделать практически невозможно. Таким образом, многомерное пространство очень большое.

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

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


Шар

Множество равноудалённых точек от данной (центра) называется сферой. Пространство внутри сферы называется шаром. Шар, вписанный в гиперкуб, это очень "маленький" объект. В n-мерном пространстве шар радиуса R имеет следующие объём Vn и площадь поверхности Sn: Vn=CnRn,            Sn=CnnRn1,       где      Cn=πn/2Γ(n2+1),     C2k=πkk! где Γ(x) - гамма-функция: Γ(1)=1,    Γ(1/2)=π,   Γ(z+1)=zΓ(z)   и   Γ(z+α)=zαΓ(z) при z1.

В единичный гиперкуб можно вписать шар радиуса R=1/2. Его объём при n=10 равен V10=0.0025, а при n=32 он исчезающе мал: V32=10-15. Хотя шар "прижимается" к граням гриперкуба, его окружает очень много (2n) углов.

Ещё одна особенность n-мерного шара состоит в том, что почти весь его объём сосредоточен возле поверхности. Действительно, рассмотрим два вложенных друг в друга шара с радиусами R и RΔR. Разность их объёмов равна объёму сферического слоя между ними. ΔVV=Rn(RΔR)nRn=1(1ΔRR)n. Отношение объёма слоя к объёму шара радиуса R приведено на рисунке справа для различных размерностей пространства n.

Пусть шар равномерно (с постоянной плотностью) заполнен объектами. Случайно выбранный объект (при больших n) почти наверняка окажется возле поверхности шара.

Пусть объекты данного класса характеризуются некоторыми типичными (средними) значениями признаков с небольшим разбросом вокруг этих средних значений. Тогда образ этого класса является центром шара в n-мерном пространстве. Чем меньше разброс вокруг среднего, тем меньше радиус такого шара-образа. Если у разных признаков разброс имеет различную амплитуду, то шар становится эллипсоидом. Линейным преобразованием эллипсоид всегда можно превратить в шар. Однако, если в пространстве признаков существует несколько различных эллипсоидов, то линейным преобразованием превратить в шар можно только один из них.


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

При обработке текстов или изображений получают векторы признаков, для которых в качестве близости используется косинусное расстояние. В этом случае основным объектом удобнее рассматривать сферу единичного радиуса. Для чётных n её объём равен: V2=3.14,       V16=0.23,       V32=4106,       V64=31020,        Vn=Cn=πn/2(n/2)!.

Для единичных векторов находящихся на сфере, квадрат евклидовго расстояния между ними пропорционален их косинусному расстоянию:

D(x,y)=(xy)2=x2+y22xy D(x,y)=2(1cos(x,y)).

Если на "поверхности" (n1)-мерной гиперсферы, провести (n2)-мерную сферу радиуса r, то отношение площади гиперсферы и объёма сферы будет порядка: Sn(R)Vn1(r)2πn(Rr)n1 Так, на единичной n-гиперсфере R=1 проведём (n1)-сферу радиуса r=1/2 (пол радиана или 28°). Тогда в 100-мерном пространстве, таких непересекающихся сфер может быть порядка 2100. Следовательно в них могут разместиться кластеры объектов различных классов. Многомерное пространство сущесвенно более "вместительно".

Если компоненты вектора являются случайными гауссовыми числами ε с нулевым средним и единичной дисперсией, то среднее значение квадрата его длины равно размерности пространства: x2=ε21+...+ε21=n. При этом вероятность распределения квадрата длины D=x2 при больших n в окрестности n2 имеет узкий пик (все точки "собираются" в окрестности сферы): e(ε21+...+ε2n)/2(2π)n/2dε1...dεn=Ωn(2π)n/2er2/2rn1dr=Ωn2(2π)n/2eD/2Dn/21dD Смоделируем это при помощи библиотеки numpy:

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

m-мерные плоскости

Пусть x={x1,...,xn} - точка в n-мерном пространстве (верхний индекс - номер координаты). Поверхность размерности m можно описать параметрическим образом x=f(t1,...,tm), где tk - набор скалярных параметров (их количество равно размерности поверхности). Например, единичная сфера в 3-мерном пространстве описывается двумя (2-мерный объект) углами {t1,t2}={θ,ϕ}: x=sinθcosϕ,     y=sinθsinϕ,     z=cosθ. Самой простой m-мерной поверхностью является плоскость. Пусть ek={e1,...,em} - набор m единичных, попарно ортогональных векторов (ekep=δpk, где δpk - символ Кронекера). Тогда уравнение плоскости имеет вид: x=x0+mk=1tkek. Параметры {t1,...,tm} выступают декартовыми координатами в m-мерном пространстве с базисом {e1,...,em}. Вектор x0 задаёт положение начала координат (точка n-пространства, в которой на плоскости все координаты tk равны нулю). Уравнение (1) является первым приближением разложения в ряд Тейлора произвольной поверхности x=f(t1,...,tm) в окрестности точки t1=...=tm=0. Если m=1, то (1) будет уравнением прямой (одномерный объект). При m=2 мы имеем двумерную плоскость и т.д.


Расстояние до m-плоскости

Получим выражение для кратчайшего евклидового расстояния (xX)2 от произвольной точки X до m-плоскости (1). Для этого необходимо найти параметры tk для которых это расстояние минимально: d2=(x0X+mk=1tkek)2=min. Возьмём производную по tp, приравняем её нулю и учтём ортонормированность векторов ek: (x0X+mk=1tkek)ep=(x0X)ep+tp=0               tp=(x0X)ep. Подставим эти tp в квадрат расстояния d2: d2=(x0Xmk=1[(x0X)ek]ek)2. Возводя в квадрат (снова с учётом ортогональности), это выражение можно переписать в следующем виде: d2=(x0X)2mk=1[(x0X)ek]2. Проекция точки X на плоскость получается подстановкой найденных параметров tk в уравнение плоскости (1): X  x=x0+mk=1[(Xx0)ek]ek.


Гиперплоскость

Гиперплоскостью в n-мерном пространстве называют m=(n1)-мерную плоскость. (в 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 = \omega_0 + \boldsymbol{\omega}\mathbf{X},~~~~~~~~~~~~\omega_0 = -\boldsymbol{\omega}\mathbf{x}_0.

При этом 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 гиперплоскостей симплекса (возможно со сглаженными углами, если длины векторов нормали невелики).


Немного математики

► Интегральное определение гамма функции (второй интеграл - замена t=x^2): \Gamma(z) = \int\limits^\infty_{0} t^{z-1}\, e^{-t}\, dt = 2\int\limits^\infty_0 x^{2z-1}\, e^{-x^2}\, dx. Интегрированием по частям и в частных случаях z=1,2, несложно получить свойства гамма-функции: \Gamma(z+1) = z\, \Gamma(z),~~~~~~~~~~~~\Gamma(1) = 1,~~~~~~~~~~~\Gamma(1/2) = \sqrt{\pi}.

► Докажем формулу для объёма n-мерного шара. В 2-мерном случае (плоскость) элемент объёма (площади) в полярных координатах равен d^2x=rdr\,d\phi = rdr\,d\Omega. Поэтому объём 2-мерной сферы радиуса R (площадь круга) равен V_2=\pi R^2, а полный телесный угол \Omega_2=2\pi. Аналогично для трёхмерного пространства d^3x = r^2 dr\,d\Omega, поэтому V_3=(4/3)\pi R^3 и \Omega_3=4\pi.

Аналогично для трёхмерного пространства d^3x = r^2 dr\,d\Omega, поэтому V_3=(4/3)\pi R^3 и \Omega_3=4\pi.

Для n-мерного случая вычислим произведение n гауссовых интегралов (r^2=x^2_1+...+x^2_n): \int\limits^\infty_{-\infty} e^{-(x^2_1+...+x^2_n)}\, d^n x = \int\limits^\infty_{0} e^{-r^2}\, r^{n-1}\,d r \int d\Omega = \frac{1}{2}\,\Gamma(n/2) \int d\Omega = \pi^{n/2}, где последнее равенство получено возведением в n-ю степень (первый интеграл) гауссова интеграла. Теперь несложно записать n-мерный телесный угол и объём n-мерной сферы радиуса R: \Omega_n = \int d\Omega= \frac{2\,\pi^{n/2}}{\Gamma(n/2)},~~~~~~~~~~~~~V_n = \frac{\Omega_n R^n}{n}.