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

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

[math]\displaystyle{ \sigma(X)=\sum_{i\lt j\leqslant n}w_{ij}(d_{ij}(X)-\delta_{ij})^2 }[/math],

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

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

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

Алгоритм SMACOF

Функцию стресса [math]\displaystyle{ \sigma }[/math] можно разложить следующим образом:

[math]\displaystyle{ \sigma(X)=\sum_{i\lt j\leqslant n}w_{ij}(d_{ij}(X)-\delta_{ij})^2 =\sum_{i\lt j}w_{ij}\delta_{ij}^2 + \sum_{i\lt j}w_{ij}d_{ij}^2(X)-2\sum_{i\lt j}w_{ij}\delta_{ij}d_{ij}(X) }[/math]

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

[math]\displaystyle{ \sum_{i\lt j}w_{ij}\delta_{ij}d_{ij}(X)=\,\operatorname{tr}\, X'B(X)X \geqslant \,\operatorname{tr}\, X'B(Z)Z }[/math],

где [math]\displaystyle{ B(Z) }[/math] имеет элементы

[math]\displaystyle{ b_{ij}=-\frac{w_{ij}\delta_{ij}}{d_{ij}(Z)} }[/math] для [math]\displaystyle{ d_{ij}(Z)\ne 0, i \ne j }[/math]

[math]\displaystyle{ b_{ij}=0 }[/math] для [math]\displaystyle{ d_{ij}(Z)=0, i\ne j }[/math]

[math]\displaystyle{ b_{ii}=-\sum_{j=1,j\ne i}^n b_{ij} }[/math].

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

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

[math]\displaystyle{ \sigma(X)=C+\,\operatorname{tr}\, X'VX - 2 \,\operatorname{tr}\, X'B(X)X }[/math]

[math]\displaystyle{ \leqslant C+\,\operatorname{tr}\, X' V X - 2 \,\operatorname{tr}\, X'B(Z)Z = \tau(X,Z) }[/math]

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

• на шаге k мы принимаем [math]\displaystyle{ Z\leftarrow X^{k-1} }[/math]
• [math]\displaystyle{ X^k\leftarrow \min_X \tau(X,Z) }[/math]
• останавливаемся, если [math]\displaystyle{ \sigma(X^{k-1})-\sigma(X^{k})\lt \epsilon }[/math], в противном случае возвращаемся в начало.

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

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

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