Мажорирование стресса

Мажорирование стресса — это стратегия оптимизации, используемая в многомерном шкалировании, где для набора из n элементов размерности m ищется конфигурация X n точек в r(<<m)-мерном пространстве, которая минимизирует так называемую функцию мажорирования $\sigma (X)$. Обычно r равно 2 или 3, то есть (n x r) матрица X перечисляет точки в 2- или 3-мерном евклидовом пространстве, так что результат может быть отражён визуально. Функция $\sigma$ является ценой или функцией потерь, которая измеряет квадрат разницы между идеальным ($m$-мерным) расстоянием и актуальным расстоянием в r-мерном пространстве. Она определяется как:

$\sigma (X)=\sum _{i<j⩽n}{w}_{ij}(d_{ij}(X)-{\delta }_{ij}{)}^2$,

где $w_{ij}⩾0$ является весом для мер между парами точек $(i,j)$, $d_{ij}(X)$ является евклидовым расстоянием между $i$ и $j$, а ${\delta }_{ij}$ является идеальным расстоянием между точками в $m$-мерном пространстве. Заметим, что $w_{ij}$ может быть использовано для спецификации степени доверия в похожести точек (например, можно указать 0, если нет никакой информации для конкретной пары).

Конфигурация $X$, которая минимизирует $\sigma (X)$, даёт график, в котором близкие точки соответствуют близким точкам в исходном $m$-мерном пространстве.

Существует много путей минимизации $\sigma (X)$. Например, КрускалШаблон:Sfn рекомендует итеративный подход кратчайшего спуска. Однако существенно лучший (в терминах гарантированности и скорости сходимости) метод минимизации стресса был предложен Яном де ЛейвомШаблон:Sfn. Метод итеративной мажоризации де Лейва на каждом шаге минимизирует простую выпуклую функцию, которая ограничивает $\sigma$ сверху и касается поверхности $\sigma$ в точке $Z$, которая называется опорной точкой. В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажоризации также упоминается как алгоритм SMACOF (Шаблон:Lang-en).

Алгоритм SMACOF

Функцию стресса $\sigma$ можно разложить следующим образом:

$\sigma (X)=\sum _{i<j⩽n}{w}_{ij}(d_{ij}(X)-{\delta }_{ij}{)}^2=\sum _{i<j}{w}_{ij}{\delta }_{ij}^2+\sum _{i<j}{w}_{ij}{d}_{ij}^2(X)-2\sum _{i<j}{w}_{ij}{\delta }_{ij}{d}_{ij}(X)$

Заметим, что первый член является константой $C$, а второй зависит квадратично от X (то есть для матрицы Гессе V второй член эквивалентен tr$X^{\prime }VX$), а потому относительно прост в вычислениях. Третий же член ограничен величиной

$\sum _{i<j}{w}_{ij}{\delta }_{ij}{d}_{ij}(X)=\mathrm{tr}{X}^{\prime }B(X)X⩾\mathrm{tr}{X}^{\prime }B(Z)Z$,

где $B(Z)$ имеет элементы

$b_{ij}=-\frac{w_{ij}{\delta }_{ij}}{d_{ij}(Z)}$ для $d_{ij}(Z)\ne 0,i\ne j$

$b_{ij}=0$ для $d_{ij}(Z)=0,i\ne j$

$b_{ii}=-\sum _{j=1,j\ne i}^n{b}_{ij}$.

Данное неравенство доказывается через неравенство Коши — Буняковского, см. статью БоргаШаблон:Sfn.

Таким образом, мы имеем простую квадратичную функцию $\tau (X,Z)$, которая мажорирует стресс:

$\sigma (X)=C+\mathrm{tr}{X}^{\prime }VX-2\mathrm{tr}{X}^{\prime }B(X)X$

$⩽C+\mathrm{tr}{X}^{\prime }VX-2\mathrm{tr}{X}^{\prime }B(Z)Z=\tau (X,Z)$

Тогда итеративная процедура мажоризации делает следующее:

• на шаге k мы принимаем $Z\leftarrow X^{k-1}$
• $X^k\leftarrow \underset{X}{\min }\tau (X,Z)$
• останавливаемся, если $\sigma (X^{k-1})-\sigma (X^k)<ϵ$, в противном случае возвращаемся в начало.

Было показано, что этот алгоритм уменьшает стресс монотонно (см. статью де ЛейваШаблон:Sfn).

Использование в визуализации графов

Мажорирование стресса и алгоритмы, подобные SMACOF, имеют также приложение в области визуализации графовШаблон:SfnШаблон:Sfn. То есть можно найти более или менее эстетичное расположение вершин для сети или графа путём минимизации функции стресса. В этом случае ${\delta }_{ij}$ обычно берётся как расстояние в смысле теории графов между узлами (вершинами) i и j, а веса $w_{ij}$ берутся равными ${\delta }_{ij}^{-\alpha }$. Здесь $\alpha$ выбирается как компромисс между сохранением длинных и коротких идеальных расстояний. Хорошие результаты были показаны для $\alpha =2$Шаблон:Sfn.

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья