Învățarea distanței pentru clasificarea cu marjă ridicată. Algoritmul LMNN

Metrici

O distanță peste un set \mathcal{X} este o funcție între două puncte d:\mathcal{X}\times \mathcal{X} \rightarrow \mathbb{R} care satisface următoarele condiții, \forall x, x', x'' \in \mathcal{X}:

  • d(x,x') \geq 0 (nonnegativitatea)
  • d(x,x') = 0 \Leftrightarrow x=x'(idempotența)
  • d(x,x') = d(x',x)(simetria)
  • d(x,x'') \leq d(x,x') + d(x', x'')(inegalitatea triunghiului)

Aceste proprietăți sunt considerate a fi axiomele distanței și reflectă proprietăți intuitive despre conceptul de distanță. O pseudo distanță trebuie să respecte aceste proprietăți cu excepția condiției 2, unde doar d(x,x)=0 este necesar.

Similaritatea este totuși un concept mai general, distanțele putând fi considerate un caz mai special al similarității. În aceeași manieră, similaritatea poate fi o funcție între două puncte \mathcal{S} : \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}. Dacă funcția \mathcal{S}respectă axioma 3, spunem că este o funcție de similaritate simetrică. Convențional, cu cât este mai mare valoarea unei funcții de similaritate, cu atât sunt mai similare și cele două obiecte. Din acest motiv, distanțele sunt o măsură a diferenețierii (dissimilarity din engleză).

O funcție de similaritate simetrică K este un kernel dacă există o funcție \phi : \mathcal{X} \rightarrow \mathbb{H} din spațiul cu instanțe \mathcal{X} la un spațiu vectorial \mathbb{H}, echipat cu un produs scalar \langle\cdot, \cdot\rangle, astfel încât K(x,x')=\langle \phi(x),\phi(x')\rangle. Echivalent, K este un kernel dacă este pozitiv semi-definit, adică \sum_i^n\sum_j^n c_i c_j K(x_i,x_j) \geq 0, pentru toate secvențele finite x_1,…,x_n \in \mathcal{X} și c_1,…,c_n\in \mathbb{R} . Altfel spus, un kernel este o funcție care ia forma unui produs scalar în \mathbb{H} și care poate fi interpretată ca o măsură a similarității ​[3]​.

Metrici uzuale pentru date numerice

Presupunem că punctele din \mathcal{X} \subseteq \mathbb{R}^d.

Distanțele Minkowski sunt o familie de distanțe induse de normele L_p. Formal, pentru p\geq 1:

 \begin{align}d_p(x,x')=\|{x-x'}\|_p = \left(\sum_{i=1}^d (x_i-x_i')^p\right)^{1/p} \end{align}
Distanțe Minkowski: cercuri unitate pentru diferite valori ale lui $p$ ​[1]​

Figura arată „cercurile” unitate corespunzătoare pentru câteva valori ale lui p. Din formula de mai sus putem extrage 3 metrici frecvent utilizate:

  • Când p=1 se obține distanța Manhattan:
\begin{align}d_{\text{man}}(x,x') = \|x-x'\|_1=\sum_{i=1}^d \mid x - x' \mid\end{align}
  • Pentru p=2 obținem distanța euclideană uzuală:
\begin{align}d_{\text{euc}}(x,x') = \|{x-x'}\|_2=\left[\sum_{i=1}^d (x_i - x_{i}')^2 \right]^{1/2} = \sqrt{(x-x')^T(x-x')}\end{align}
  • Pentru p=\infty se obține distanța Chebyshev:
\begin{align}d_{\text{che}}(x,x')=\|{x-x'}\|_\infty = \max_i \mid x_i - x_i' \mid \end{align}

Distanța Mahalanobis

În mod tradițional se referă la o distanță care încorporează corelația trăsăturilor:

\begin{align}d_\mathcal{M}(x,x') = \sqrt{(x-x')^T\Sigma^{-1}(x-x')}\end{align}

unde x, x' sunt vectori aleatori extrași din distribuția cu matricea de covarianță \Sigma.

Totuși, în literatura de specialitate dedicată metodelor de învățare a distanței, distanța Mahalanobis se mai confundă cu distanța cuadratică generalizată, definită ca:

\begin{align}d_\mathcal{M}(x,x') = \sqrt{(x-x')^TM(x-x')}\end{align}

\textbf M trebuie să fie o matrice pozitiv semi-definită, condiție care asigură că d_\mathcal{M} este o pseudo-metrică.

Învățarea distanței Mahalanobis

Este important de remarcat că există două abordări pentru învățarea distanței Mahalanobis, ce sunt matematic echivalente, dar care semantic exprimă două lucruri diferite. Prima metodă se bazează pe învățarea matricii pozitiv semi-definite \textbf{M} care descrie metrica. A doua metodă constă în a găsi acea transformare liniară \textbf{L} care, odată aplicată setului de date, va induce o schimbare a relației de vecinătate între elemente, atunci când se utiliează distanța euclideană în spațiul transformat, echivalentă cu relația de vecinătate indusă de o distanță Mahalanobis. Acest lucru este posibil, deoarece prin factorizarea Cholesky, \textbf{M}=\textbf{L}^T\textbf{L}.

Diferența semantică a celor două abordări constă că, spre deosebire de prima abordare, care nu modifică obiectele în sine ci doar scala cu care acestea se măsoară, a doua abordare modifică obiectele, deoarece transformarea \textbf{L} se aplică asupra datelor și nu asupra vectorilor ce formează o bază.

Odată cu dezvoltarea metodelor bazate pe învățarea adâncă, prima abordare și-a pierdut din popularitate deoarece este conduce la aceleași rezultate, dar este mai puțin interpretabilă decât distanța euclidiană.


Clasificarea cu marjă ridicată. Algoritmul LMNN.

Lucrarea „Distance Metric Learning for Large Margin Nearest Neighbor Classification” de K. Weinberger et al. ​[4]​, prezintă o metodă prin care se poate învăța distanța Mahalanobis în problema celor mai apropiați k vecini. Metrica este optimizată în așa fel încât cei mai apropiați k vecini aparțin aceleași clase în timp ce exemplele din clase diferite sunt separate de distanțe mai mari.

În articol nu se învață direct matricea Mahalanobis, ci transformarea spațiului care conduce la aceeași relație de vecinătate atunci când se utilizează distanța Mahalanobis. Acest lucru este posibil fiindcă orice matrice pozitiv definită poate fi descompusă, prin intermediul factorizării Cholesky, în produsul unei matrici inferior triangulare cu conjugatul ei. Mai precis, se poate obține o familie de metrici peste un spațiu vectorial \chi calculând distanța euclideană după ce s-a aplicat o transformare liniară x'=\mathbf{L}x, x\in\chi .

\begin{aligned}D_{\mathbf L}(x_i,x_j)& =\|\mathbf L(x_i-x_j)\|_2^2 = (\mathbf{L}(x_i-x_j))^T(\mathbf L (x_i-x_j)) \\
& = (x_i-x_j)^T(\mathbf{L}^T\mathbf{L})(x_i-x_j) \\
& = (x_i-x_j)^T\mathbf M(x_i-x_j) \tag{7} \end{aligned}

Modelul se bazează pe două intuiții: \forall x_i \in \chi ar trebui să aibă y_i ca și cei mai apropiați k vecini; instanțele de antrenare cu etichete diferite ar trebui să fie cât mai distanțate.

Pentru învățare este necesară identificarea explicită a unor vecini pentru fiecare x_i. Acești vecini a lui x_i sunt cei pe care îi dorim a fi cei mai apropiați de x_i, iar transformarea liniară ideală va trebui să surprindă acest aspect. S-a folosit notația j\leadsto i pentru a indica că intrarea x_j este un vecin explicit a lui x_i.

Pentru a crește robustețea clasificării kNN, se adoptă un obiectiv mai restrictiv – de a menține o distanță cât mai mare între exemplele cu etichete diferite, numite „impostori”, și vecinii specificați în mod explicit. Prin această constrângere, modelul devine robust la zgomotul redus care ar putea fi prezent în datele de antrenare. Matematic, impostorii sunt definiți printr-o inegalitate. Pentru un exemplu x_i cu etichetă y_i și vecin explicit x_j, un impostor este o intrare x_l cu y_l \ne y_i astfel încât:

\begin{aligned}\|{\textbf{L}(x_i-x_l)}\|^2\leq \|\textbf{L}(x_i-x_j)\|^2 + 1\tag{8}\end{aligned}

Cu alte cuvinte, un impostor este orice element cu o etichetă diferită de y_i care invadează perimetrul vecinului x_j al intrării x_i. Figura 1 ilustrează ideea principală a învățării cu margine mare. Prin învățare, impostorii sunt împinși în afara perimetrului stabilit de către vecinii obiectiv. După învățare, va exista o margine între acest perimetru și impostori. Figura arată un caz idealizat, în care există o transformare liniară ce poate să corecteze erorile de clasificare.

Ilustrare a vecinătății unei intrări înainte de antrenare (stânga), respectiv după (dreapta)  [1]
Ilustrare a vecinătății unei intrări înainte de antrenare (stânga), respectiv după (dreapta) [1]

Funcția de cost constă în doi termeni:

  • Primul termen penalizează distanțele mari dintre exemplele ce aparțin aceleiași clase
\begin{aligned}\varepsilon_{\text{pull}}(\textbf{L}) = \sum_{j\leadsto i} \|{\textbf{L}(x_i-x_j)}\|^2\tag{9}\end{aligned}
  • Al doilea termen penalizează distanțele mici dintre exemplele ce au etichete diferite – violări ale inegalității \ref{eq1}. Pentru a simplifica notația s-a introdus o variabilă indicator y_{il}=1 dacă și numai dacă y_i=y_l, respectiv y_{il}=0 în rest.
\begin{aligned}\varepsilon_{\text{push}}(\textbf{L}) = \sum_{i,j\leadsto i}\sum_l(1-y_{il})\max(1 + \|{\textbf{L}(x_i-x_j)}\|^2 - \|{\textbf{L}(x_i-x_l)}\|^2, 0) \tag{10}\end{aligned}

Funcția de cost penalizează impostorii deoarece termenul din sumă este pozitiv atunci când elementul cu o etichetă diferită se află în perimetrul definit de x_j. Odată ce impostorul iese din perimetrul extins (perimetru + 1), prima expresie din funcția \max va fi negativă, iar acel element nu va mai contribui la \varepsilon_{\text{push}}.

Minimizarea acestor termeni conduce la o transformare liniară a spațiului de intrare care crește numărul de exemple de antrenare pentru care cei mai apropiați k vecini au aceeași etichetă. Funcția finală de cost va combina cei doi termeni \varepsilon_{\text{pull}}(\textbf{L}) și \varepsilon_{\text{push}}(\textbf{L}). Cei doi termeni au efecte concurente – să atragă vecinii target pe de-o parte și să respingă impostorii, pe de altă parte. De aceea, se introduce un termen \mu \in [0,1] care balansează aceste obiective:

\begin{aligned}\varepsilon (\textbf{L}) = (1-\mu)\varepsilon_{\text{pull}}(\textbf{L}) + \mu\varepsilon_{\text{push}}(\textbf{L}) \tag{11}\end{aligned}

\mu poate fi obținut prin validare încrucișată, dar autorii remarcă că 1/2 este o valoare rezonabilă.

Totuși, funcția de cost din (11) nu este convexă în elementele matricii \textbf{L}. Pentru a depăși această problemă, autorii au reformulat funcția de cost ca o optimizare peste matrici pozitiv semidefinite. Concret, se utilizează matricea \textbf{M}=\textbf{L}^T\textbf{L}, funcția de cost devenind [\cdot]+ este \max(0,\cdot):

\begin{aligned} \varepsilon(\textbf{M}) = (1-\mu)\sum_{i,j\leadsto i} \mathcal{D}_{\textbf M}(x_i, x_j) + \mu \sum_{i,j\leadsto i} \sum_l(1-y_{il})[1 + \mathcal{D}_{\textbf M}(x_i, x_j) - \mathcal{D}_{\textbf M}(x_i, x_l)]_+\tag{12}\end{aligned}

Cu această substituție, funcția de cost este exprimată pe matrici pozitiv semidefinite \textbf{M}\succeq0. Pentru a evita colapsarea într-o soluție trivială, trebuie ca optimizarea să țină cont de \textbf{M}\succeq0.

Prin reformularea obiectivului (11) de mai sus se poate obține o instanță a unei probleme de programare semidefinită ​[2]​. Este necesar să fie introdusă o variabilă liberă nenegativă, \xi pentru toate tripletele vecinilor obiectiv j\leadsto i și impostorilor x_l. Variabila liberă \xi \geq 0 este folosită pentru a măsura gradul în care inegalitatea (8) este violată. Folosind variabila liberă pentru a monitoriza violările marginii de separație, se obține instanța de problemă de programare semidefinită:

\begin{aligned} \min_{\textbf{M}} \;\; & (1-\mu)\sum_{i,j\leadsto i} \mathcal{D}_{\textbf M}(x_i, x_j) + \mu \sum_{i,j\leadsto i,l} (1-y_{il})\xi_{ijl} \\ \quad & \mathcal{D}_{\textbf M}(x_i, x_l) - \mathcal{D}_{\textbf M}(x_i, x_j) \geq 1-\xi_{ijl} \\ \quad & \xi_{ijl} \geq 0 \\ \quad & M\succeq0 \tag{13}\end{aligned}
  1. A. Bellet, A. Habrard, and M. Sebban. 2015. Metric Learning. Morgan & Claypool Publishers.
  2. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, USA.
  3. B. Schölkopf and AJ. Smola. 2002. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press.
  4. Kilian Q Weinberger, John Blitzer, and Lawrence K. Saul. 2006. Distance Metric Learning for Large Margin Nearest Neighbor Classification. In Advances in Neural Information Processing Systems 18, Y. Weiss, B. Schölkopf and J. C. Platt (eds.). MIT Press, 1473–1480.

Lasă un comentariu