Optimimarginaaliluokittelija

Wikipedia

Optimimarginaaliluokittelija on hahmontunnistuksen käsite, joka tarkoittaa luokittelijaa joka erottaa kaksi avaruuden osajoukkoa (luokkaa) mahdollisimman tasapuolisesti toisistaan.

[muokkaa] Määritelmä

Optimimarginaaliluokittelija on piirreavaruuden pinta muotoa $\bold{w}^T\bold{x} + b = 0$ , joka erottaa kaksi luokkaa toisistaan niin että luokkien pisteet jäävät eri puolille pintaa. Lisäksi vaaditaan että lyhin etäisyys kummankin luokan pisteistä pintaan nähden on mahdollisimman suuri. Tämä tarkoittaa sitä että kummankin luokan lyhin etäisyys pintaan nähden on sama, koska kokonaisuuden kannalta lyhin etäisyys määrittyy lähempänä olevan luokan perusteella.

Luokalla tarkoitetaan avaruuden osajoukkoa jolla on tietty semanttinen ominaisuus, joka riippuu sovelluskohteesta. Silloin kun kahden eri luokan erottelu on mahdollista, sanotaan että luokat ovat lineaarisesti erotettavia.

Oletamme että piirreavaruus on $R n$ , ja yritämme etsiä tasoa $(\bold{w},b)$ siten että pisteelle $\bold{x}$ pätee:

$\bold{w}^T\bold{x} + b > 0$ ,

kun $\bold{x}$ kuuluu ensimmäiseen luokkaan, ja

$\bold{w}^T\bold{x} + b < 0$ ,

kun $\bold{x}$ kuuluu toiseen luokkaan. Jos sovimme että ensimmäisen luokan pisteitä vastaa $y$ :n arvo $+ 1$ ja toisen luokan pisteitä $- 1$ , niin saamme yhden yhtälön

$y (\bold{w}^T\bold{x} + b) > 0$ ,

joka pätee kummankin luokan pisteille. Jos opetustieto koostuu $l$ eri pisteestä, jotka ovat $\bold{x}_i$ , kun $i = 1, \dots, l$ , ja $y i$ ovat niiden vastaavat luokat (joko $+ 1$ tai $- 1$ ), niin vaadimme että luokat erottava taso $(\bold{w},b)$ toteuttaa ehdon

$y_i (\bold{w}^T\bold{x}_i + b) > 0 \quad \forall i = 1, \dots, l$ .

Tietylle pinnalle $(\bold{w},b)$ geometrinen etäisyys opetustietoon voidaan laskea seuraavasti:

$\min_{i=1}^l \frac{|\bold{w}^T \bold{x}_i + b|}{\|\bold{w}\|}$ .

Optimimarginaaliluokittelijan löytämiseksi on olemassa useita eri ratkaisutapoja. Tukivektorikone-kirjallisuudessa esitetään monesti ratkaisutapaa joka perustuu neliölliseen optimointiin, koska se tapa johtaa luontevasti myös vaativampien ongelmien ratkaisuun. Toinen mahdollinen tapa on etsiä kummallekin luokalle erillinen konveksipeite, ja sen jälkeen etsiä konveksipeitteiden välille lyhin mahdollinen viiva. Tämän jälkeen vektori $\bold{w}$ on viivan suunta, ja $b$ määrittyy siitä että piste viivan puolivälissä kuuluu tasoon.

[muokkaa] Neliöllinen optimointi

Optimimarginaaliluokittelija voidaan määrittää ratkaisemalla seuraava erikoistapaus neliöllisen ohjelmoinnin ongelmasta. Lausekkeen $\frac{1}{2}\|\bold{w}\|^2$ optimointi muuttujien $\bold{w}$ ja $b$ suhteen johtaa haluttuun tulokseen, kun reunaehdot ovat

$y_i (\bold{w}^T\bold{x}_i + b) \ge 1 \quad \forall i = 1, \dots, l$ .

Muuttuja $b$ ei esiinny kohdefunktiossa vaan se määrittyy implisiittisesti reunaehdoista.

Optimointitehtävän asettelu perustuu siihen että tarkastellaan kahta tasoon nähden lähintä pistettä $\bold{x}_n$ ja $\bold{x}_m$ . Näiden pisteiden geometriset etäisyydet mielivaltaiseen tasoon ovat $δ n$ ja $δ m$ kun

$\delta_i = \frac{|\bold{w}^T \bold{x}_i + b|}{\|\bold{w}\|}$ .

Taso $(\bold{w},b)$ on täsmälleen sama kuin mikä tahansa taso $(c \bold{w}, c b)$ , kun $c > 0$ , josta seuraa että $c$ voidaan valita siten että $|c \bold{w}^T \bold{x}_i + c b| = 1$ pisteille $\bold{x}_n$ ja $\bold{x}_m$ . Tällöin saadaan geometristen etäisyyksien summaksi

$\delta_n + \delta_m = \frac{|c \bold{w}^T \bold{x}_n + c b|}{\|c \bold{w}\|} + \frac{|c \bold{w}^T \bold{x}_m + c b|}{\|c \bold{w}\|} = \frac{2}{\|c \bold{w}\|}$ .

Tämän seurauksena rajoittamalla reunaehdot annetun tehtävän mukaisesti ja minimoimalla $\|\bold{w}\|$ etäisyys tasoon maksimoituu.

Haettu osoitteesta http://fi.wikipedia.org../../../o/p/t/Optimimarginaaliluokittelija.html

Luokat: Hahmontunnistus | Matemaattinen optimointi

Optimimarginaaliluokittelija

Wikipedia

[muokkaa] Määritelmä

[muokkaa] Neliöllinen optimointi

Views

Valikko

Haku