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

Мажорування стресу — це стратегія оптимізації, використовувана в багатовимірному шкалюванні, де для набору з n елементів розмірності m шукається конфігурація X n точок у r(<<m)-вимірному просторі, яка мінімізує так звану функцію мажорування ${\displaystyle \sigma (X)}$. Зазвичай r дорівнює 2 або 3, тобто (n x r) матриця X перераховує точки в 2- або 3-вимірному евклідовому просторі, так що результат можна відобразити візуально. Функція ${\displaystyle \sigma }$ є ціною або функцією втрат, яка вимірює квадрат різниці між ідеальною (${\displaystyle m}$-вимірною) відстанню і актуальною відстанню в r-вимірному просторі. Вона визначається як:

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

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

Конфігурація ${\displaystyle X}$, яка мінімізує ${\displaystyle \sigma (X)}$, дає графік, на якому близькі точки відповідають близьким точкам у початковому ${\displaystyle m}$-вимірному просторі.

Існує багато шляхів мінімізації ${\displaystyle \sigma (X)}$. Наприклад, Крускал^[1] рекомендує ітеративний підхід найшвидшого спуску. Однак істотно кращий (у термінах гарантованості і швидкості збіжності) метод мінімізації стресу запропонував Ян де Лейв^[2]. Метод ітеративного мажорування де Лейва на кожному кроці мінімізує просту опуклу функцію, яка обмежує ${\displaystyle \sigma }$ зверху і дотикається до поверхні ${\displaystyle \sigma }$ в точці ${\displaystyle Z}$, яку називають опорною точкою. В опуклому аналізі таку функцію називають мажорувальною функцією. Цей ітеративний процес мажорування також відомий як алгоритм SMACOF (англ. Scaling by MAjorizing a COmplicated Function).

Алгоритм SMACOF[ред. | ред. код]

Функцію стресу ${\displaystyle \sigma }$ можна розкласти так:

${\displaystyle \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)}$

Зауважимо, що перший член є константою ${\displaystyle C}$, а другий залежить квадратично від X (тобто для матриці Гесе V другий член еквівалентний tr${\displaystyle X'VX}$), а тому відносно просто обчислюється. Третій член обмежений величиною

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

де ${\displaystyle B(Z)}$ має елементи

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

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

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

Ця нерівність доводиться через нерівність Коші — Буняковського (див. статтю Борга^[3]).

Таким чином, ми маємо просту квадратичну функцію ${\displaystyle \tau (X,Z)}$, яка мажорує стрес:

${\displaystyle \sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X}$

${\displaystyle \leqslant C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(Z)Z=\tau (X,Z)}$

Тоді ітеративна процедура мажорування робить таке:

• на кроці k ми приймаємо ${\displaystyle Z\leftarrow X^{k-1}}$
• ${\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}$
• зупиняємося, якщо ${\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }$, в іншому випадку повертаємося на початок.

Показано, що цей алгоритм зменшує стрес монотонно (див. статтю де Лейва^[2]).

Використання у візуалізації графів[ред. | ред. код]

Мажорування стресу і алгоритми, подібні SMACOF, застосовуються також у галузі візуалізації графів^[4][5]. Тобто, завдякимінімізації функції стресу, можна знайти більш-менш естетичне розташування вершин для мережі або графа. В цьому випадку ${\displaystyle \delta _{ij}}$ зазвичай береться як відстань (у сенсі теорії графів) між вузлами (вершинами) i і j, а ваги ${\displaystyle w_{ij}}$ беруться рівними ${\displaystyle \delta _{ij}^{-\alpha }}$. Тут ${\displaystyle \alpha }$ вибирається як компроміс між збереженням великих і малих ідеальних відстаней. Хороші результати отримано для ${\displaystyle \alpha =2}$^[6].

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Нормативний контроль Freebase: /m/02q73yd