Участник:Asenin/Многомерное шкалирование

Автор: Сенин Александр Николаевич, студент ММП ВМК МГУ (417)

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

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

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

Постановка получилась сильно общей, вполне естественно существование более узких постановок и разных подходов к решению. Резюмируем общую задачу: по вещественной матрице попарных различий найти для каждого объекта такое положение в пространстве размерности [math]p[/math] (чаще всего [math]p=2,3[/math]), что попарные различия будут лучше всего сохранены. Тогда общее описание алгоритма: получаем на вход квадратную вещественную матрицу [math]D[/math] размера [math]N x N[/math], возвращаем [math]N[/math] векторов размерности [math]p[/math] - координаты точек, которые лучше всего описывают наши объекты.

1.2 Математическое описание алгоритма

Конкретизируем подход к решению задачи многомерного шкалирования. Будем рассматривать задачу классического многомерного шкалирования (Classical Multidimensional Scaling, cMDS).

Пусть входная матрица различий - матрица попарных расстояний для евклидовой метрики [math]D = (d_{ij})[/math]. Здесь предполагаем, что данные нам различия во входной матрице - расстояния, с точки зрения математики, причем посчитанные евклидовой метрикой. Это допущение позволит найти конфигурацию, которая идеально точно воспроизводит расстояния на парах, но про размерность полученных координат мы не сможем ничего сказать. Однако, даже если метрика была не евклидовой, или даже не была формально математическим расстоянием, а также в случае, если требуются координаты фиксированной небольшой размерности, мы все равно получим результат.

Задача классического MDS (cMDS) - найти [math]X = (x_1, ..., x_N)^T[/math], т.ч. [math]d_{ij} = ||x_i - x_j||_2[/math].

Решение не единственно: [math]X^* = X + c^T[/math] тоже решение, т.к. [math]d_{ij} = ||x_i - x_j|| = ||(x_i + c) - (x_j + c)||[/math]. Ищем центрированную конфигурацию [math]\overline{x} = 0[/math]. Матрица [math]D[/math] евклидова, т.е. [math]\exists \{x_i\}_{i=1}^{N} \in \ R^p[/math], т.ч. [math]d_{ij}^2 = (x_i - x_j)^T(x_i - x_j)[/math]

Идея: восстановить [math]\{x_i\}_{i=1}^{N} \in R^p[/math], при условии [math]\overline{x} = 0[/math]. Решение: восстановим матрицу Грама [math]B = (b_{ij}),[/math] где [math]b_{ij} = x_i^T x_j[/math]

Обозначим [math]X = (x_1, ..., x_N)^T \Rightarrow B = XX^T[/math]

Таким образом, если получим матрицу Грама, то сможем по ее спектральному разложению получить [math]X[/math].

Восстановление матрицы Грама в cMDS:

[math]d_{ij}^2 = (x_i - x_j)^T(x_i - x_j) = x_i^Tx_i + x_j^Tx_j - 2x_i^Tx_j = b_{ii} + b_{jj} - 2b_{ij} \\ \overline{x} = 0 \Rightarrow \sum_{i=1}^N b_{ij} = 0 \\ \dfrac{1}{N} \sum\limits_{i=1}^{N} d_{ij}^2 = \dfrac{1}{N} \sum\limits_{i=1}^{N} b_{ii} + b_{jj} \\ \dfrac{1}{N} \sum\limits_{j=1}^{N} d_{ij}^2 = b_{ii} + \dfrac{1}{N} \sum\limits_{j=1}^{N} b_{jj} \\ \dfrac{1}{N^2} \sum\limits_{i, j=1}^{N} d_{ij}^2 = \dfrac{2}{N} \sum\limits_{i=1}^{N} b_{ii} \\ b_{ij} = -\dfrac{1}{2}(d_{ij}^2 - d_{i \bullet}^2 - d_{\bullet j}^2 + d_{\bullet \bullet}^2)[/math]

Строим по [math]D[/math] матрицу Грама [math]B[/math]:

[math]b_{ij} = -\dfrac{1}{2}(d_{ij}^2 - d_{i \bullet}^2 - d_{\bullet j}^2 + d_{\bullet \bullet}^2)[/math]

[math]B = C_N A C_N[/math], где [math]A = -\dfrac{1}{2} D^2[/math] поэлементно, [math]C_n = E - \dfrac{1}{n} \textbf{1} \textbf{1}^T[/math]

Выше получено, что [math]B = XX^T,[/math] [math]X \in R^{N \times p} \Rightarrow B[/math] симметричная, неотрицательно определенная, ранга [math]rg{B} = rg{XX^T} = rg{X} = p[/math]

[math]B[/math] имеет [math]p[/math] положительных собственных значений и [math]n-p[/math] нулевых собственных значений.

[math]B = \Gamma \Lambda \Gamma^T[/math], где [math]\Lambda = diag(\lambda_1, ..., \lambda_p)[/math] и [math]\Gamma = (\gamma_1, ..., \gamma_p)[/math] матрица собственных векторов.

Итоговый результат:

[math]X = \Gamma \Lambda^{\frac{1}{2}}[/math]

3 Литература

[1] Wikipedia contributors. (2020, April 13). Multidimensional scaling. In Wikipedia, The Free Encyclopedia. Retrieved 20:33, June 1, 2020, from https://en.wikipedia.org/w/index.php?title=Multidimensional_scaling&oldid=950612463