T-61.5020 Luonnollisten kielten tilastollinen käsittely
Vastaukset 6, to 28.2.2007, 12:15-14:00 -- Samankaltaisuusmitat
Versio 1.1

1.

Euklidinen etäisyys (eli $ L_2$-normi)

Euklidinen etäisyys vektorin $ \mathbf x =[x_1 ~x_2 \dots x_n]$ ja $ \mathbf y =[y_1 ~y_2 \dots y_n]$ välillä määritellään

$\displaystyle Euc(\mathbf x, \mathbf y)= \sqrt{\sum_{i=1}^n (x_i-y_i)^2}$ (1)

Lasketaan euklidinen etäisyys esimerkin vuoksi Tintuksen ja Korvalääkkeen välillä:
$\displaystyle Euc(Ti,Ko)$ $\displaystyle =$ $\displaystyle \sqrt{(0-10)^2+(0-6)^2+(5-2)^2+(1-1)^2 +(4-0)^2}$  
  $\displaystyle =$ $\displaystyle 12.7$  
$\displaystyle Euc(Ko,Te)$ $\displaystyle =$ $\displaystyle 9.9$  
$\displaystyle Euc(Ti,Te)$ $\displaystyle =$ $\displaystyle 5.1$  

$ L_1$-normi

$ L_1$-normin mukainen etäisyys määritellään

$\displaystyle L_1(\mathbf x, \mathbf y)= \sum_{i=1}^n \vert x_i-y_i \vert$ (2)

Lasketaan etäisyydet:
$\displaystyle L_1(Ti,Ko)$ $\displaystyle =$ $\displaystyle \vert-10\vert+\vert-6\vert+\vert 5-2\vert+\vert 1-1\vert +\vert 4-0\vert$  
  $\displaystyle =$ $\displaystyle 23.0$  
$\displaystyle L_1(Ko,Te)$ $\displaystyle =$ $\displaystyle 17.0$  
$\displaystyle L_1(Ti,Te)$ $\displaystyle =$ $\displaystyle 10.0$  

Kosini

Kosini onkin sitten hieman erilainen tapaus, se on samankaltaisuusmitta. Se määritellään vaikkapa

$\displaystyle \cos(\mathbf x, \mathbf y) = \frac{\sum_{i=1}^n x_iy_i}{\sqrt{\sum_{i=1}^n x_i^2}\sqrt{\sum_{i=1}^n y_i^2}}$ (3)

Lasketaan etäisyydet:
$\displaystyle cos(Ti,Ko)$ $\displaystyle =$ $\displaystyle \frac{0\cdot10+0\cdot6+5\cdot2+1\cdot1 +4\cdot0} {\sqrt{5^2+1+4^2}\sqrt{10^2+6^2+2^2+1^2}}$  
  $\displaystyle =$ $\displaystyle 0.14$  
$\displaystyle cos(Ko,Te)$ $\displaystyle =$ $\displaystyle 0.55$  
$\displaystyle cos(Ti,Te)$ $\displaystyle =$ $\displaystyle 0.70$  

Tässä siis suurempi luku vastaa suurempaa samankaltaisuutta ja etäisyydet / samankaltaisuudet ovat samassa järjestyksessä kuin edelläkin.

Informaatiosäde

Informaatiosäteen laskemista varten muodostetaan suurimman uskottavuuden estimaatit sille, että seuraava lähteen $ l_i$ (Tintus, Korvalääke, Termiitti) tuottama tunnettu sana on $ w_i$. Tämä voidaan laskea jakamalla jokainen annetun matriisin rivin alkio rivin alkioiden summalla (Taulukko 1).

Taulukko 1: ML-estimaatti sanatodennäköisyyksille
  raikas hapokas makea hedelmäinen pehmeä
Tintus 0 0 0.50 0.10 0.40
Korvalääke 0.53 0.32 0.11 0.05 0
Termiitti 0.07 0.29 0.21 0.21 0.21


Määritellään vielä, että

$\displaystyle 0 \log\frac0x = 0, ~ \forall x \in \Re$    

Informaatiosäde voidaan laskea kaavasta
$\displaystyle Irad(p,q)$ $\displaystyle =$ $\displaystyle D(p\vert\vert\frac{p+q}2) + D(q\vert\vert\frac{p+q}2)$  
  $\displaystyle =$ $\displaystyle \sum_i p_i \log\frac{p_i}{\frac{p_i+q_i}2} + \sum_i q_i \log\frac{q_i}{\frac{p_i+q_i}2}$  

Lasketaan informaatiosäde annetuille lähteillä:
$\displaystyle Irad(Ti,Ko)$ $\displaystyle =$ $\displaystyle 0\cdot\log\frac{2\cdot0}{0.53} + 0\cdot\log\frac{2\cdot0}{0.32} + 0.50\cdot\log\frac{2\cdot0.50}{0.61} + 0.10\cdot\log\frac{2\cdot0.10}{0.15}$  
    $\displaystyle +0.40\cdot\log\frac{2\cdot0.40}{0.40} + 0.53\cdot\log\frac{2\cdot0.53}{0.53} + 0.32\cdot\log\frac{2\cdot0.32}{0.32}$  
    $\displaystyle + 0.11\cdot\log\frac{2\cdot0.11}{0.61} + 0.05\cdot\log\frac{2\cdot0.05}{0.15} + 0\cdot\log\frac{2\cdot0}{0.40}$  
  $\displaystyle =$ $\displaystyle 1.5$  
$\displaystyle Irad(Ko,Te)$ $\displaystyle =$ $\displaystyle 0.6$  
$\displaystyle Irad(Ti,Te)$ $\displaystyle =$ $\displaystyle 0.5$  

Huomataan, että kaikki mitat asettavat lääkeet asettavat lääkkeet samankaltaisuuksin mukaan samaan järjestykseen: Tintus ja Termiitti ovat samankaltaisimmat, Tintus ja Korvalääke erilaisimmat.

KL-divergenssi

KL-divergenssin määritelmästä voimme suoraan nähdä muutaman siihen liittyvän ongelman:

$\displaystyle D(p\vert\vert q)=\displaystyle \sum_i p_i \log \frac{p_i}{q_i}$    

KL-divergenssi ei ole symmetrinen, vaan pitäisi aina päättää kumpi lääke on referenssilääke, mihin toista verrataan. Toinen ongelma on siinä, että jos vertailtavalla jakaumalla $ q$ on nollatodennäköisyys jossain, missä referenssijakauma $ p$ ei ole nolla, niin KL-divergenssi menee äärettömyyksiin.

[2.]

Kullback-Leibler -divergenssi

KL-divergenssin määritelmä on

$\displaystyle D(p\vert\vert q)=\displaystyle \sum_i p_i \log \frac{p_i}{q_i}$    

Etsitään jakauma, joka minimoi KL-divergenssin. Lisätään Lagrange-kerroin $ \lambda_1$ pitämään huolta siitä, että $ p$ pysyy todennäköisyysjakaumana (eli $ \sum_i p_i=1$) ja $ \lambda_2$ $ q$:lle.

$\displaystyle E=D(p\vert\vert q)+\lambda_1(1-\sum_ip_i)+\lambda_2(1-\sum_iq_i) ... ...um_i p_i \log \frac{p_i}{q_i} + \lambda_1(1-\sum_ip_i) + \lambda_2(1-\sum_iq_i)$    

Merkitään osittaisderivaatta $ p_i$:n suhteen nollaksi:
$\displaystyle \frac{\partial E}{\partial p_i}$ $\displaystyle =$ $\displaystyle p_i\cdot \frac{1}{\frac{p_i}{q_i}} \cdot \frac{1}{q_i} + \log \frac{p_i}{q_i} - \lambda_1$  
  $\displaystyle =$ $\displaystyle \log p_i - \log q_i + 1 - \lambda_1 = 0$  

Ratkaistaan $ p_i$:
$\displaystyle p_i$ $\displaystyle =$ $\displaystyle q_i \cdot e^{\lambda_1-1}$  

Lasketaan osittaisderivaatta $ \lambda_1$ suhteen:
$\displaystyle \frac{\partial E}{\partial \lambda_1}$ $\displaystyle =$ $\displaystyle 1-\sum_i p_i=0$  
$\displaystyle \Rightarrow \sum_i p_i$ $\displaystyle =$ $\displaystyle 1$  

Vastaava ehto $ q_i$:lle saadaan $ \lambda_2$ suhteen derivoimalla, mikä oli tarkoituskin. Lasketaan vielä nollakohta $ q_i$:n suhteen:
$\displaystyle \frac{\partial E}{\partial q_i}$ $\displaystyle =$ $\displaystyle p_i \cdot \frac{1}{\frac{p_i}{q_i}} \cdot p_i \cdot (-\frac{1}{q_i^2})-\lambda_2 = - \frac{p_i}{q_i} - \lambda_2 = 0$  
$\displaystyle \Leftrightarrow p_i$ $\displaystyle =$ $\displaystyle - \lambda_2 q_i$  

Koska sekä $ q$:n että $ p$:n tulee siis summatua yhteen, saamme:
$\displaystyle 1$ $\displaystyle =$ $\displaystyle \sum_i p_i = \sum_i (-\lambda_2 q_i) = -\lambda_2 \sum_i q_i = -\lambda_2$  
$\displaystyle \Rightarrow p_i$ $\displaystyle =$ $\displaystyle -\lambda_2 q_i = q_i$  

Toisen asteen derivaattoja tarkastelemalla voimme vielä varmistua siitä että tämä todellakin on minimi eikä maksimi:
$\displaystyle \frac{\partial^2 E}{\partial p_i \partial p_i}$ $\displaystyle =$ $\displaystyle \frac1{p_i}>0$  
$\displaystyle \frac{\partial^2 E}{\partial q_i \partial q_i}$ $\displaystyle =$ $\displaystyle \frac{p_i}{q_i^2}>0$  
$\displaystyle \frac{\partial^2 E}{\partial p_i \partial p_j} = \frac{\partial^2 E}{\partial q_i \partial q_j}$ $\displaystyle =$ 0  

Jos sijoitamme KL-divergenssin kaavaan $ q_i = p_i$ saamme divergenssiksi nolla. Eli KL-divergenssi on nolla jos ja vain jos jakaumat $ q$ ja $ p$ ovat samoja, muuten nollaa suurempi.

Informaatiosäde

Informaatiosäteen määritelmä on

$\displaystyle IRad(p,q)=D(p\vert\vert\frac{p+q}2) + D(q\vert\vert\frac{p+q}2)$    

Laskimme juuri, että KL-divergenssi on nolla, kun jakaumat ovat samat ja muuten tätä enemmän. Informaatiosäteen tapauksessa nolladivergenssiin siis päästään myös vain kun $ q_i = p_i$:

$\displaystyle IRad(p,q)=\sum_i p_i \log\frac{p_i}{\frac{p_i+p_i}2} + \sum_i p_i \log\frac{p_i}{\frac{p_i+p_i}2} = 0$    

Ehto on siis sama kuin KL-divergenssillä.

$ L_1$-normi

$ L_1$-normin määritelmä on

$\displaystyle L_1(p,q)=\sum_i \vert p_i - q_i \vert$    

Tämähän on selvästi pienimmillään nolla. Se tapahtuu kun $ q_i = p_i$.

Huomataan siis, että kaikki mitat antavat pienimmän etäisyyden samalla ehdolla -- jakaumien on oltava samat -- ja tämä pienin arvo on nolla.

[3.]

Kullback-Leibler -divergenssi

Katsotaan vielä KL-divergenssin määritelmää:

$\displaystyle D(p\vert\vert q)=\displaystyle \sum_i p_i \log \frac{p_i}{q_i}$    

Huomataan, että jos $ q_i=0$ kun $ p_i \ne 0$, saadaan etäisyydeksi $ \infty$.

Informaatiosäde

Kirjoitetaan informaatiosäteen määritelmä auki:

$\displaystyle IRad(p,q)=D(p\vert\vert\frac{p+q}2) + D(q\vert\vert\frac{p+q}2) = \sum_i p_i \log \frac{2p_i}{p_i+q_i} +\sum_i q_i \log \frac{2q_i}{p_i+q_i}$    

Intuition avulla arvataan sopivaksi jakaumaksi sellainen, missä jakaumat sijaitsevat täysin eri alueilla:
$\displaystyle \textrm{jos } p_i > 0 \Rightarrow q_i=0$      
$\displaystyle \textrm{jos } q_i > 0 \Rightarrow p_i=0$      

Sijoitetaan tällaiset jakaumat informaatiosäteen lausekkeeseen:
$\displaystyle IRad(p,q)$ $\displaystyle =$ $\displaystyle \sum_i p_i \log \frac{2p_i}{p_i} +\sum_i q_i \log \frac{2q_i}{q_i}$  
  $\displaystyle =$ $\displaystyle \log 2 \sum_i p_i + \log2 \sum_i q_i = 2 \log 2$  

Huomataan, että ehdot täyttävä jakauma antaa suurimman etäisyyden. Todistus siitä, että $ 2 \log 2$ on suurin mahdollinen informaatiosäde ja että ylläarvatut ehdot vaaditaan tämän etäisyyden saavuttamiseksi olisi sitten jonkin verran hankalampi.

$ L_1$-normi

$ L_1$-normin määritelmähän oli

$\displaystyle L_1(p,q)=\sum_i \vert p_i - q_i \vert$    

Intuitiollahan voisi jo päätellä, että vastaus on sama kuin informaatiosäteen tapauksessa, mutta yritetään perustella asiaa vielä matemaattisesti. Jaetaan alkeistapaukset $ I$ kahteen osaan. Osassa $ j \in I$ on tapaukset, joissa $ p_j > q_j$ ja osassa $ k \in I$ tapaukset, joissa $ q_k >p_k$. Kirjoitetaan itseisarvot auki:
$\displaystyle L_1(p,q)$ $\displaystyle =$ $\displaystyle \sum_j (p_j - q_j ) + \sum_k (q_k-p_k)$  
  $\displaystyle =$ $\displaystyle \sum_j p_j - \sum_k p_k + \sum_k q_k - \sum_j q_j$  

Koska todennäköisyydet ovat positiivisia ja summautuvat 1:een, suurin etäisyys saadaan kun
$\displaystyle \textrm{jos } p_i > 0 \Rightarrow q_i=0$      
$\displaystyle \textrm{jos } q_i > 0 \Rightarrow p_i=0$      

eli etäisyys on
$\displaystyle L_1(p,q)$ $\displaystyle =$ $\displaystyle \sum_i p_i + \sum_i q_i =2$  

Yhteenveto

Informaatiosäteen ja $ L_1$-normin tapauksessa kahden todennäköisyysjakauman välisen suurimman etäisyyden saavuttamiseen vaaditaan samat ehdot. Sen sijaan KL-divergenssi menee äärettömyyksiin jo, kun vertailujakauma $ q$ on nolla jossain missä $ p$ ei ole nolla.


svirpioj@cis.hut.fi