1. IBM modell másképp

Az 1. IBM modellt bevezető cikkben [1] másfajta tárgyalást használnak, minél elemibb matematikai eszközökkel szeretnék levezetni a paraméterbecslés formuláját, és sokat támaszkodnak a szemléletre. Ezért matematikai szempontból a szerzők nem elég pontosan járnak el. Mégis tanulságos megnézni ezt a levezetést, mert lényegében ugyanazt az eredményt kapják, amit fent levezettem, és algoritmikus szempontból ugyanazt kell csinálni a számítógéppel való számoláskor. Elemibb eszközöket használnak a formulák kiszámításához, de mégis kerülőúton jutnak arra az eredményre, amire én a tétel közvetlen alkalmazásával. Tehát láthatjuk, hogy sok esetben a hiányos adatrendszer likelihood függvénye közvetlenül is maximalizálható, de ekkor semmi sem garantálja a felírt iteratív eljárás konvergenciáját. Illetve ekkor a konvergencia külön megfontolás tárgya, vagy ha könnyen kipróbálható az algoritmus a valóságban, számítógépen, akkor lehet vele kísérletezni. Ez a szokásos mérnöki megközelítés. Tehát szerzők jelöléseikkel élve egy $\bf f$ francia, egy $\bf a$ alignment és egy $\bf e$ angol mondat valószínűségét a következő alakban írják fel:

$$\boldsymbol P({\bf f},{\bf a}\vert{\bf e}) = \boldsymbol P(m\vert... ...{j-1},f_1^{j-1},m,{\bf e}) \boldsymbol P(f_j\vert a_1^{j},f_1^{j-1},m,{\bf e}).$$

Itt $m$ a francia mondat hossza, $P(m\vert{\bf e})$ pedig a hossz feltételes valószínűsége, egyenletesnek feltételezzük egy bizonyos $M$ határon belül. Az $a_j$ az alignment egy tagja, azaz, az a szám, ami megmutatja, hogy a $j$ -edik francia szó melyik angol szóból származik, $a_1^{j-1}$ pedig az alignment tagja $1$ -től $j-1$ -ig. Az $f_j$ a $j$ -edik francia szó, és $f_1^{j-1}$ pedig a francia szavak összessége $1$ -től $j-1$ -ig. A $P(a_j\vert a_1^{j-1},f_1^{j-1},m,{\bf e})$ valószínűségekről feltételezzük, hogy csak $l$ -től, az angol mondat hosszától függ, és ezért konstans $(l+1)^{-1}$ . $e_{a_j}$ -vel jelöljük azt az angol szót, melyből $f_j$ származik. Felteszik, hogy $\boldsymbol P(f_j\vert a_1^{j},f_1^{j-1},m,{\bf e})$ csak $f_j$ -től, és $e_{a_j}$ -től függ. Ezek után az $\epsilon=P(m\vert{\bf e})$ , $t(f_j\vert e_{a_j})=P(f_j\vert a_1^{j},f_1^{j-1},m,{\bf e})$ számokat tekintik paraméternek. Ezt a $t(f_j\vert e_{a_j})$ paramétert tekinthetjük úgy, mint az $f_j$ -nek a fordítási valószínűségét adott $e_{a_j}$ mellett. Figyeljük meg, hogy végig csak egyetlen mondatpárról beszélnek a cikkben és aztán majd csak később, amikor egy várható érték előjön, akkor összegzik a kapott értékeket az összes mintabeli mondatpárra. Ezt egyébként megtehetik, mert az eloszlás paraméterektől függő része polinomiális, és ezért a log likelihood már összeg lesz, aminek a várható értéke tagonként vehető, ám mondhatni, hogy ez csak merő véletlen, általános esetben ez nem tehető meg. Ha $n$ független mintát veszek, akkor azok log likelihood függvénye ugyan összeg lesz, de ha ezek a független tényezők nem szorzat alakúak, mint esetünkben, akkor már nehezebb lehet a várható érték kiszámolása. Esetünkben a kitevők egyszerűen indikátor változók voltak, amiknek a várható értéke ráadásul a feltételes valószínűség. Látható, hogy a legegyszerűbb esettel van dolgunk. A nehézségeket inkább a részletek adhatják. A fenti jelölésekkel a cikkben tehát a

$$\boldsymbol P({\bf f},{\bf a}\vert{\bf e})={\epsilon\over{(l+1)^m}}\prod_{j=1}^m t(f_j\vert e_{a_j})$$

formulát kapják. Egy mondatpár fordítási valószínűségét a lehetséges alignmentekre összegezve kapjuk. Ezért

$$\boldsymbol P({\bf f}\vert{\bf e})={\epsilon\over{(l+1)^m}}\sum_{a_1=0}^l\cdots\sum_{a_m=0}^l \prod_{j=1}^m t(f_j\vert e_{a_j}).$$

Tehát a feladatunk az, hogy a $t$ fordítási valószínűségek függvényeként maximáljuk a $\boldsymbol P({\bf f}\vert{\bf e})$ hiányos adatokhoz tartozó likelihoodot úgy, hogy közben a paraméterek minden $e$ angol szóra kielégítsék a $\sum_f t(f\vert e)=1$ feltételt.

A probléma direkt megoldásához bevezetve a $\lambda_e$ Lagrange multiplikátorokat a feltételes szélsőérték keresésére a

$$\boldsymbol P({\bf f}\vert{\bf e})={\epsilon\over{(l+1)^m}}\sum_{... ...=0}^l \prod_{j=1}^m t(f_j\vert e_{a_j})-\sum_e \lambda_e (\sum_f t(f\vert e)-1)$$

kifejezést kell maximalizálnunk, most már a paraméterekben és a $\lambda_e$ változókban egyaránt. A parciális deriváltakat kell kiszámolni. A $\lambda_e$ szerinti deriváltak a feltételeket adják vissza. A $t(f\vert e)$ változó szerinti derivált

$${\epsilon\over{(l+1)^m}}\sum_{a_1=0}^l \cdots \sum_{a_m=0}^l \sum... ...)\delta(e,e_{a_j})t(f\vert e)^{-1} \prod_{k=1}^m t(f_k\vert e_{a_k})-\lambda_e.$$

Ahol $\delta$ a már bevezetett Kronecker delta függvény. Ez a kifejezés akkor nulla, ha

$$t(f\vert e)=\lambda^{-1}{\epsilon\over{(l+1)^m}}\sum_{a_1=0}^l \c... ...elta(f,f_j)\delta(e,e_{a_j})t(f\vert e)^{-1} \prod_{k=1}^m t(f_k\vert e_{a_k}).$$

Ez a felírás azt sugallja, hogy érdemes egy iteratív eljárást alkalmazni az egyenlet megoldására. A cikk irói azt állítják, hogy ez egy EM algoritmusra vezet, ám nem bizonyítják. A korábbi formulák segítségével és az egymásba ágyazott összegeket a teljes alignmenteken való egyetlen összegnek írva a

$$t(f\vert e)=\lambda^{-1}\sum_{\bf a}\boldsymbol P({\bf f},{\bf a}\vert{\bf e}) \sum_{j=1}^m \delta(f,f_j)\delta(e,e_{a_j}).$$

Ebben az egyenletben a Kronecker delta függvények szorzatát tartalmazó összeg megadja, hogy $e$ hányszor kapcsolódik $f$ -hez egy alignmentben. Ez a formula másképp is írható, ha bevezetjük $e$ és $f$ összekapcsolódásának várható értékére a $c(f\vert e;{\bf f},{\bf e})$ jelölést. Erre definíció szerint teljesül, hogy

$$c(f\vert e;{\bf f},{\bf e})=\sum_{\bf a}\boldsymbol P({\bf a}\vert{\bf e},{\bf f}) \sum_{j=1}^m \delta(f,f_j)\delta(e,e_{a_j})$$

Mivel a $\lambda_e$ számok csak normalizációs célokat szolgálnak, vagyis elméleti és gyakorlati szempontból sem kell őket meghatározni, hiszen a paraméterek ismeretében kiszámolhatók, mert azok összege, ezért a $\lambda_e \boldsymbol P({\bf f}\vert{\bf e})$ számot is jelölhetjük $\lambda_e$ -vel. Ezzel a jelöléssel nagyon röviden így írható a az egyenlet:

$$t(f\vert e)=\lambda_e^{-1}c(f\vert e;{\bf f},{\bf e}).$$

A gyakorlatban azonban több mondatpár is rendelkezésünkre áll, ezért

$$({\bf f}^{(1)}\vert{\bf e}^{(1)}),({\bf f}^{(2)}\vert{\bf e}^{(2)}),\ldots,({\bf f}^{(S)}\vert{\bf e}^{(S)})$$

$S$ elemű minta esetén a paraméter becslése

$$t(f\vert e)=\lambda_e^{-1}\sum_{s=1}^S c(f\vert e;{\bf f}^{(s)},{\bf e}^{(s)}).$$

Ez az egyenlet megfelel az M lépésnek. Ugyanis, ha a bal oldalon álló paramétert a jobboldalon állók függvényeként akarjuk kiszámolni, vagyis veszünk kiindulási paramétereket, majd ezeket a jobb oldalba helyettesítjük, és a bal oldalon megjelenő értékeket tekintjük az új paramétereknek, akkor láthatjuk, hogy a régi paraméterekkel vett $c$ feltételes várható érték pont az, amit számolnunk kell. Ezek a feltételes várható értékek szerepelnek a polinomiális eloszlás kitevőiben, illetve ez nem is polinomiális eloszlás, hiszen a kitevőkben nem csak egész számok lehetnek. Számunkra ebből csak az az érdekes, hogy az ezt maximalizáló paramétereket úgy kell kiszámolni, hogy vesszük az azonos alapú kitevők összegét, amint az egyenletben is, és ezt elosztjuk az összegükkel, vagyis normáljuk őket. A normálást biztosítja a Lagrange multiplikátor, illetve $\lambda_e \boldsymbol P({\bf f}\vert{\bf e}).$

Most térjünk rá a feltételes várható érték paraméterek szerinti kiszámolására, hiszen eddig csak felírtuk azt a feltételes valószínűségekkel. Tulajdonképpen elvileg ebben a fázisban is ki tudnánk számolni a $\boldsymbol P({\bf a}\vert{\bf e},{\bf f})$ valószínűségeket, hiszen ez

$${\boldsymbol P({\bf f},{\bf a}\vert{\bf e})}\over{\boldsymbol P({\bf f}\vert{\bf e})}$$

és ezeknek pedig ismerjük a paraméterekkel való felírását. Az egyetlen probléma, hogy a nevezőben az összes lehetséges alignmentre összegezni kell, ami a gyakorlatban kivitelezhetetlen. Ezért az abban szereplő összegzésre tekintsük a következő azonosságot:

$$\sum_{a_1=0}^l\cdots\sum_{a_m=0}^l \prod_{j=1}^m t(f_j\vert e_{a_j})=\prod_{j=1}^m\sum_{i=0}^lt(f_j\vert e_i).$$

Ennek a kifejezésnek a segítségével a nevező a következő alakban írható:

$$\boldsymbol P({\bf f}\vert{\bf e})={\epsilon\over{(l+1)^m}}\prod_{j=1}^m\sum_{i=0}^lt(f_j\vert e_i)$$

Így a $c$ feltételes várható értékre kapjuk, hogy

$$c(f\vert e;{\bf f},{\bf e})={t(f\vert e)\over{t(f\vert e_0)+\cdots +t(f\vert e_l)}} \sum_{j=1}^m \delta(f,f_j)\sum_{i=0}^l \delta(e,e_i).$$

Lényegében tehát a Bayes-tételt alkalmazzuk, ami előzőleg is kijött. Ezzel a kis trükkel megoldottuk, hogy az $(l+1)^m$ lehetséges alignmentre való összegzés helyett csak $l+m$ összeget kell venni.