Мажорування стресу

Мажорування стресу — це стратегія оптимізації, використовувана в багатовимірному шкалюванні, де для набору з 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.

Література

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