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

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

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

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

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

Существует много путей минимизации $\mathrm{\sigma <!--\; \sigma \; -->}(X)$$\sigma (X)$. Например, Крускал рекомендует итеративный подход кратчайшего спуска. Однако существенно лучший (в терминах гарантированности и скорости сходимости) метод минимизации стресса был предложен Яном де Лейвом. Метод итеративной мажоризации де Лейва на каждом шаге минимизирует простую выпуклую функцию, которая ограничивает $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ сверху и касается поверхности $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$ в точке $Z$$Z$, которая называется опорной точкой. В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажоризации также упоминается как алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function).

Алгоритм SMACOFПравить

Функцию стресса $\mathrm{\sigma <!--\; \sigma \; -->}$$\sigma$  можно разложить следующим образом:

$\sigma (X)=\sum _{i<j\leqslant 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$$C$ , а второй зависит квадратично от X (то есть для матрицы Гессе V второй член эквивалентен tr$X^{\prime }VX$$X'VX$ ), а потому относительно прост в вычислениях. Третий же член ограничен величиной

$\sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)=\,\operatorname {tr} \,X'B(X)X\geqslant \,\operatorname {tr} \,X'B(Z)Z$ ,

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

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

$b_{ij}=0$$b_{ij}=0$  для $d_{ij}(Z)=0,i\ne <!--\; \ne \; -->j$$d_{ij}(Z)=0,i\neq j$ 

$b_{ii}=-<!--\; -\; -->\underset{j=1,j\ne <!--\; \ne \; -->i}{\overset{n}{\sum <!--\; \sum \; -->}}{b}_{ij}$$b_{ii}=-\sum _{j=1,j\neq i}^{n}b_{ij}$ .

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

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

$\mathrm{\sigma <!--\; \sigma \; -->}(X)=C+\mathrm{tr}{X}^{\prime }VX-<!--\; -\; -->2\mathrm{tr}{X}^{\prime }B(X)X$$\sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X$ 

$⩽<!--\; ⩽\; -->C+\mathrm{tr}{X}^{\prime }VX-<!--\; -\; -->2\mathrm{tr}{X}^{\prime }B(Z)Z=\mathrm{\tau <!--\; \tau \; -->}(X,Z)$$\leqslant C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(Z)Z=\tau (X,Z)$ 

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

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

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

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

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