Русская Википедия:Мажорирование стресса
Мажорирование стресса — это стратегия оптимизации, используемая в многомерном шкалировании, где для набора из n элементов размерности m ищется конфигурация X n точек в r(<<m)-мерном пространстве, которая минимизирует так называемую функцию мажорирования <math>\sigma(X)</math>. Обычно r равно 2 или 3, то есть (n x r) матрица X перечисляет точки в 2- или 3-мерном евклидовом пространстве, так что результат может быть отражён визуально. Функция <math>\sigma</math> является ценой или функцией потерь, которая измеряет квадрат разницы между идеальным (<math>m</math>-мерным) расстоянием и актуальным расстоянием в r-мерном пространстве. Она определяется как:
- <math>\sigma(X)=\sum_{i<j\leqslant n}w_{ij}(d_{ij}(X)-\delta_{ij})^2</math>,
где <math>w_{ij}\geqslant 0</math> является весом для мер между парами точек <math>(i,j)</math>, <math>d_{ij}(X)</math> является евклидовым расстоянием между <math>i</math> и <math>j</math>, а <math>\delta_{ij}</math> является идеальным расстоянием между точками в <math>m</math>-мерном пространстве. Заметим, что <math>w_{ij}</math> может быть использовано для спецификации степени доверия в похожести точек (например, можно указать 0, если нет никакой информации для конкретной пары).
Конфигурация <math>X</math>, которая минимизирует <math>\sigma(X)</math>, даёт график, в котором близкие точки соответствуют близким точкам в исходном <math>m</math>-мерном пространстве.
Существует много путей минимизации <math> \sigma(X)</math>. Например, КрускалШаблон:Sfn рекомендует итеративный подход кратчайшего спуска. Однако существенно лучший (в терминах гарантированности и скорости сходимости) метод минимизации стресса был предложен Яном де Лейвом[1]Шаблон:Sfn. Метод итеративной мажоризации де Лейва на каждом шаге минимизирует простую выпуклую функцию, которая ограничивает <math>\sigma</math> сверху и касается поверхности <math>\sigma</math> в точке <math>Z</math>, которая называется опорной точкой. В выпуклом анализе такая функция называется мажорирующей функцией. Этот итеративный процесс мажоризации также упоминается как алгоритм SMACOF (Шаблон:Lang-en).
Алгоритм SMACOF
Функцию стресса <math>\sigma</math> можно разложить следующим образом:
- <math>
\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) </math>
Заметим, что первый член является константой <math>C</math>, а второй зависит квадратично от X (то есть для матрицы Гессе V второй член эквивалентен tr<math>X'VX</math>), а потому относительно прост в вычислениях. Третий же член ограничен величиной
- <math>
\sum_{i<j}w_{ij}\delta_{ij}d_{ij}(X)=\,\operatorname{tr}\, X'B(X)X \geqslant \,\operatorname{tr}\, X'B(Z)Z </math>,
где <math>B(Z)</math> имеет элементы
- <math>b_{ij}=-\frac{w_{ij}\delta_{ij}}{d_{ij}(Z)}</math> для <math>d_{ij}(Z)\ne 0, i \ne j</math>
<math>b_{ij}=0</math> для <math>d_{ij}(Z)=0, i\ne j</math>
<math>b_{ii}=-\sum_{j=1,j\ne i}^n b_{ij}</math>.
Данное неравенство доказывается через неравенство Коши — Буняковского, см. статью БоргаШаблон:Sfn.
Таким образом, мы имеем простую квадратичную функцию <math>\tau(X,Z)</math>, которая мажорирует стресс:
- <math>\sigma(X)=C+\,\operatorname{tr}\, X'VX - 2 \,\operatorname{tr}\, X'B(X)X
</math>
- <math>\leqslant C+\,\operatorname{tr}\, X' V X - 2 \,\operatorname{tr}\, X'B(Z)Z = \tau(X,Z)
</math>
Тогда итеративная процедура мажоризации делает следующее:
- на шаге k мы принимаем <math>Z\leftarrow X^{k-1}</math>
- <math>X^k\leftarrow \min_X \tau(X,Z)</math>
- останавливаемся, если <math>\sigma(X^{k-1})-\sigma(X^{k})<\epsilon</math>, в противном случае возвращаемся в начало.
Было показано, что этот алгоритм уменьшает стресс монотонно (см. статью де ЛейваШаблон:Sfn).
Использование в визуализации графов
Мажорирование стресса и алгоритмы, подобные SMACOF, имеют также приложение в области визуализации графовШаблон:SfnШаблон:Sfn. То есть можно найти более или менее эстетичное расположение вершин для сети или графа путём минимизации функции стресса. В этом случае <math>\delta_{ij}</math> обычно берётся как расстояние в смысле теории графов между узлами (вершинами) i и j, а веса <math>w_{ij}</math> берутся равными <math>\delta_{ij}^{-\alpha}</math>. Здесь <math>\alpha</math> выбирается как компромисс между сохранением длинных и коротких идеальных расстояний. Хорошие результаты были показаны для <math>\alpha=2</math>Шаблон:Sfn.
Примечания
Литература
- ↑ Имя нидерландское и родился он в Вубурге (Нидерланды), см. с таким же именем статью «Портрет Яна де Лейва».
