Màquina de vectors de suport estructura

La màquina de vectors de suport estructurat és un algorisme d'aprenentatge automàtic que generalitza el classificador de la màquina de vectors de suport (SVM). Mentre que el classificador SVM admet classificació binària, classificació multiclasse i regressió, l'SVM estructurat permet l'entrenament d'un classificador per a etiquetes de sortida estructurades generals.

Com a exemple, una instància de mostra pot ser una frase en llenguatge natural i l'etiqueta de sortida és un arbre d'anàlisi anotat. L'entrenament d'un classificador consisteix a mostrar parells de mostres correctes i parells d'etiquetes de sortida. Després de l'entrenament, el model SVM estructurat permet predir per a noves instàncies de mostra l'etiqueta de sortida corresponent; és a dir, donada una oració en llenguatge natural, el classificador pot produir l'arbre d'anàlisi més probable.

Per a un conjunt de $n$ instàncies de formació $({\boldsymbol {x}}_{i},y_{i})\in {\mathcal {X}}\times {\mathcal {Y}}$, $i=1,\dots ,n$ d'un espai mostral ${\mathcal {X}}$ i l'espai d'etiquetes ${\mathcal {Y}}$, l'SVM estructurat minimitza la següent funció de risc regularitzada.

${\underset {\boldsymbol {w}}{\min }}\quad \|{\boldsymbol {w}}\|^{2}+C\sum _{i=1}^{n}{\underset {y\in {\mathcal {Y}}}{\max }}\left(0,\Delta (y_{i},y)+\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y)\rangle -\langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}}_{i},y_{i})\rangle \right)$

La funció és convexa ${\boldsymbol {w}}$ perquè el màxim d'un conjunt de funcions afins és convex. La funció $\Delta :{\mathcal {Y}}\times {\mathcal {Y}}\to \mathbb {R} _{+}$ mesura una distància a l'espai de l'etiqueta i és una funció arbitrària (no necessàriament una mètrica) satisfactòria $\Delta (y,z)\geq 0$ i $\Delta (y,y)=0\;\;\forall y,z\in {\mathcal {Y}}$. La funció $\Psi :{\mathcal {X}}\times {\mathcal {Y}}\to \mathbb {R} ^{d}$ és una funció característica, que extreu algun vector de característica d'una mostra i etiqueta donades. El disseny d'aquesta funció depèn molt de l'aplicació.

Com que la funció de risc regularitzada anterior no és diferenciable, sovint es reformula en termes d'un programa quadràtic introduint una variable slack. $\xi _{i}$ per a cada mostra, cadascuna representa el valor del màxim.

En el moment de la prova, només una mostra ${\boldsymbol {x}}\in {\mathcal {X}}$ es coneix, i una funció de predicció $f:{\mathcal {X}}\to {\mathcal {Y}}$ l'assigna a una etiqueta prevista des de l'espai d'etiquetes ${\mathcal {Y}}$ . Per a SVM estructurats, donat el vector ${\boldsymbol {w}}$ obtinguda de l'entrenament, la funció de predicció és la següent.

$f({\boldsymbol {x}})={\underset {y\in {\mathcal {Y}}}{\textrm {argmax}}}\quad \langle {\boldsymbol {w}},\Psi ({\boldsymbol {x}},y)\rangle$

Per tant, el maximitzador de l'espai de l'etiqueta és l'etiqueta prevista. La resolució d'aquest maximitzador és l'anomenat problema d'inferència i similar a fer una predicció a posterior màxima (MAP) en models probabilístics. En funció de l'estructura de la funció $\Psi$, resoldre el maximitzador pot ser un problema difícil.