T-61.281 Luonnollisten kielten tilastollinen käsittely
Vastaukset 9, ti 25.3.2003, 16:15-18: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: 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 referenssilääkkeellä on nollatodennäköisyys jossain, missä vertailtava lääke 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-\sum_ip_i)=\displaystyle \sum_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$  

Samanlainen tulos saadaan $ \lambda_2$:lle ja $ q_i$:lle. Osittaisderivaattojen nollakohdista voimme päätellä että
$\displaystyle p_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 p_i \partial p_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.

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 nollaetäisyyden samalla ehdolla: jakaumien on oltava samat.

[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 positiivissa 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 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.


vsiivola@cis.hut.fi