Általános tudnivalók

A természetes nyelvfeldolgozás matematikai alapjai (Mathematical Foundations of Natural Language Processing)

Az elõadások helye, ideje ?, szerda 12:15-14:00

Tantárgy kód BMETE959308 (NYELVMAT)

Kornai András fogadóórája Kedd 12-1:30, H/5/5

Kredit 3 -- év közben projekt vagy év végén szóbeli vizsga

Ajánlott/kötelezõ elõtanulmányi rend

• lineáris algebra, formális nyelvek, diszkrét matematika
• algebra, analízis
• valszám

Kapcsolódó kurzusok

A 2-4 elõadásokban matematikai nyelvészeti szemszögbõl tárgyalt anyag jóval részletesebb és gépközpontúbb kifejtését adja Naszódi Mátyás: Bevezetés a nyelvmérnökségbe c. kurzusa.

A 8. és 12 elõadásokhoz hasonlóan illeszkedik Tikk Domonkos Szövegbányászat kurzusa illetve

Szakadát István Digitális archívumok és szemantikus technikák kurzusa.

Jegyzet, tankönyv, felhasználható irodalom

Tematika

1. Nyelvészet, grammatika, axiomatikus módszer
2. Véges automaták és Turing gépek közötti nyelvosztályok. Generálás
3. Hangtan: fonémák, jegyek, hangsúly, intonáció, szupraszegmentális és autoszegmentális elemek, nyelvi ellenõrzés (spell checking)
4. Alaktan: prozódia, szóképzés, optimalitás, Zipf-törvénye
5. Mondattan: kombinatorikus grammatikai és szemantikai elméletek. Súlyozott nyelvek, súlyozott véges automaták, rejtett Markov modellek
6. Jelentéstan: paradoxonok, Montague nyelvtan. Igazságértékek, változó kötés, típus algebra
7. Bonyolultság: információ, Kolmogorov bonyolultság
8. Nyelvi alakfelismerés: kvantizáció, magasszintû jelfeldolgozás, a jel információtartalma, dokumentum osztályozás
9. Beszédfelismerés: alacsony szintõ jelfeldolgozás. A fonémák mint rejtett elemek. Fonológiai és fonetikai kategóriák. Beszédszintézis
10. Kézi és nyomtatott írás felismerése: lap dekompozíció, jegy számítás.
11. Tanuló algoritmusok: neurális hálók, rejtett Markov modellek, szabály indukció.
12. Egyéb alkalmazások: keresõ motorok, gépi fordítás.

Vizsgatételek

1. A generálás mint nem-determinisztikus algoritmus, a nyelvtan mint axiómarendszer, a nyelvtechnológia alapfeladatai (2.1, 2.2)
2. Ábécé, láncok, formális nyelvek, Chomsky-hierarchia (2.3). A klasszikus bevezetés Salomaa (1973) Formal Languages (csak az elsõ rész, pp 1-122). Magyar nyelven használható Alberti Gábor (2006) Matematika a természetes nyelvek leírásában (Tinta Kiadó), illetve Bach Iván formális nyelvek jegyzete.
3. Determinisztikus, nem-determinisztikus véges (fél)automaták. Véges automaták, reguláris kifejezések, és félcsoportok kapcsolata (5.1.1) Alapszinten Salomaa, Alberti, Bach, középhaladó szinten Ginzburg (1968), haladóknak Eilenberg (1974). Jó mégJ. Horton Conway (1971) Regular algebra and finite machines (Chapman and Hill). Itt is és máshol is hasznos Jurafsky és Martin (1999) (új kiadás 2009), ehhez a tételhez a harmadik fejezet kapcsolódik. Kiraktam Kleene és Moore klasszikus cikkeit, érdekes olvasmány mindakettõ, de nem vizsgatétel.
4. *Kaszkád- és koszorú-szorzat, Krohn-Rhodes tétel. (5.6). Ginzburg, Eilenberg, Maler és Pnueli (1994)
5. Fonológiai ábécé, természetes osztályok, környezetfüggõ szabályrendszerek, szótagok (3.1, 3.2, 4.1.1)
6. Szupraszegmentálisok, autoszegmensek (3.3)
7. Transzducerek és fonológiai alkalmazásuk. (3.4). Normál esetben ez egy teljes kurzus -- a vizsgakérdés csak az, hogy hogyan csinálunk környezetfüggõ szabályból véges transzducert. A klasszikus bevezetõ Kaplan és Kay (1994). Jó cikkek vannak a Roche és Schabes (1997), Kornai (1999), illetve az ezeket követõ FSMNLP kötetekben.
8. Szóképzés (4.2)
9. Szógyakoriság. Zipf törvényei és Herdan törvénye, ezek kapcsolata (4.4)
10. Súlyozott automaták és transzducerek (5.4, 5.5)
11. Kombinatorikus szintaxis (5.1)
12. Információ, entrópia, Shannon kódolási tétel, Hincsin-tétel (7.1)
13. Kolmogorov-bonyolultság (7.2)
14. *Tanuláselmélet (7.3)
15. Markov láncok, HMM, Shannon állapottétel (8.2)
16. Téma szerinti osztályozás (8.4) Reuters korpusz
17. Jelfeldolgozás, LPC, mintavételi tétel (9.1)
18. Írásfelismerés (9.3)

Szorgalmi feladatok

1. Prímszámok környezetfüggõ nyelvtannal. Megoldás
2. Nyelvmodellezés. Adva van (természetes nyelvi) szavak egy w_1, w_2, ... w_n sorozata, beszéljük meg a P(w_{n+1}|w_1,...,w_n) feltételes eloszlást: ez a nyelvmodellezési probléma. Ennek a gyakorlatban kitüntetett jelentõsége van, de a feladat nem ez, hanem az alábbi: ha Q_1 és Q_2 a nyelvmodellezési probléma két javasolt megoldása, és P az empirikus eloszlás, adjunk olyan jóságmértéket (figure of merit) ami megmondja Q_1 és Q_2 közül melyik közelíti P-t jobban.
3. Gépi fordítás. Adott egy forrásnyelvi S szöveg, ennek kézi fordítása K és gépi fordításai G_1 és G_2. Adjunk olyan jóságmértéket ami G_1 és G_2 közti választást tesz lehetõvé. Kell-e S-re támaszkodnunk, és ha igen miért nem?
4. Milyen szabályos nyelvekhez tartozik csoportmentes szintaktikai monoid? Hogyan jellemezzük ezeket a nyelveket félautomatával ill. szabályos kifejezéssel?

Kötelezõ feladatok

1. Adott tövek egy T_1, T_2, .... végtelen sorozata amely Zipf eloszlást követ P(T_i) ~ 1/i^B (B>1), és adott egy paradigma melyben a k paradigmatikus alak valószinûsége rögzített p_k (k=1,...,N). Milyen eloszlást követnek a w szavak amelyeket az összes T_i tõbõl az N-féle paradigmatikus alak bármelyikével nyerünk, feltéve hogy P(T_i.k) = P(T_i)p_k.