SZIMBÓLUMSOROZATOK ELEMZÉSE STATISZTIKAI MÓDSZEREKKEL Tudományos diákköri dolgozat, 1997

0

´ SZIMBOLUMSOROZATOK ´ ELEMZESE STATISZTIKAI ´ MODSZEREKKEL Tudom´ anyos di´ akk¨ ori dolgozat, 1997.

Kész´ıtette: B´ ır´ o Tam´ as V. éves fizikushallgat´ o ELTE TTK

Témavezet˝ o: Vicsek Tam´ as egyetemi tan´ ar ELTE TTK Atomfizikai Tanszék

Budapest, 1997.

¨ Osszefoglal´ o Dolgozatom célja az, hogy o ¨sszefoglalja azokat a statisztikus fizikai és sztochasztikus m´ odszereket, amelyek szimb´ olumsorozatok (sz¨ ovegek természetes nyelveken, DNS-k´ od,...) elemzésénél hatékonyan haszn´ alhat´ oak. Beketintést adok az ezen a téren a kilencvenes években végzett kutat´ asokba (pl. hossz´ ut´ av´ u korrel´ aci´ ok, Zipf-t¨ orvény). Majd megvizsg´ alom, milyen k¨ ovetkezményekkel j´ arnak ezen eredmények a szimb´ olumsorozatot létrehoz´ o folyamatok modellezhet˝ oségére nézve, ha a form´ alis nyelvek elméletét kib˝ ov´ıtj¨ uk sztochasztikus eszk¨ oz¨ okkel. Azt kapom, hogy a folyamatot két szakaszra kell bontanunk, az els˝ o, amely egy nemline´ aris ”k´ odoland´ ob´ ol” kész´ıt egy line´ aris k´ odot, hossz´ ut´ av´ u korrel´ aci´ okat eredményez; viszont a m´ asodik szakasz elemezhet˝ o Markov-folyamatként. Bevezetek egy elj´ ar´ ast, amely szekvenci´ akat hasonl´ıt o ¨ssze, a r¨ ovidt´ av´ u korrel´ aci´ okb´ ol ad´ od´ o jellegzetességeik alapj´ an, és felhaszn´ alom ezt a m´ odszert a fonotaktik´ aban, valamint k´ odol´ o és nem-k´ odol´ o DNSszakaszok o ¨sszehasonl´ıt´ as´ ara.

2

Tartalomjegyz´ ek

1. Bevezet´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Hossz´ utav´ u korrel´ aci´ ok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3. Alapfogalmak a form´ alis nyelvek elm´ elet´ eb˝ ol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4. A genetikai k´ od ´ es a term´ eszetes nyelvek k¨ oz¨ otti anal´ ogi´ ak . . . . . . . . . . . . . . .13 5. Sztochasztikus form´ alis nyelvek ´ es Markov-modellek . . . . . . . . . . . . . . . . . . . . . . 16 5.1. Sztochasztikus k¨ ornyezetf¨ uggetlen grammatik´ ak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2. Sztochasztikus regul´ aris nyelvtanok és a Markov-modell . . . . . . . . . . . . . . . . . . . . . . . . . 19 6. n-grammok ´ es fonotaktika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 7. K´ odol´ o´ es nem-k´ odol´ o DNS-szakaszok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 8. Befejez´ es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 K¨ osz¨ onetnyilv´ an´ıt´ as . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Irodalomjegyz´ ek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32

3

1. Bevezet´ es M´ıg a hagyom´ anyos fizika az egyes t¨ omegpontok, részecskék viselkedésével foglalkozik, a modern statisztikus fizika a nagysz´ am´ u k¨ olcs¨ onhat´ o részecske a ´ltal létrehozott strukt´ ur´ akat is képes le´ırni. Ezek a strukt´ ur´ ak gyakran f¨ uggetlenek az o ˝ket létrehoz´ o részecskék legt¨ obb speci´ alis tulajdons´ ag´ at´ ol, ezt nevezz¨ uk univerzalit´ asnak. K¨ olcs¨ onhat´ o ”részecskékb˝ ol” a ´ll´ o rendszerekkel a fizik´ an k´ıv¨ ul is tal´ alkozunk. Az elm´ ult években sikerrel alkalmazt´ ak a statisztikus fizik´ aban kifejlesztett m´ odszereket a molekul´ aris biol´ ogi´ aban 1 , az evoluci´ obiol´ ogi´ aban 2 , vagy éppen a k¨ ozdazdas´ agtanban, 3 ahol a piacon verseng˝ o v´ allalatok vagy a t˝ ozsdén ”k¨ olcs¨ onhat´ o” u ¨gyn¨ ok¨ ok a statisztikus fizik´ ab´ ol ismert viszonyokat hoznak létre. Az egyens´ ulyt´ ol t´ avoli rendszerekre jellemz˝ o sk´ al´ az´ asi (ill. frakt´ alis) tulajdons´ agokkal (Vicsek [1992], Family & Vicsek [1991]) tal´ alkozunk péld´ aul a v´ allalatok méret szerinti eloszl´ as´ an´ al ,4 de el˝ obukkannak statisztikus fizikai m´ odszerek az opci´ ok a ´raz´ as´ an´ al és a t˝ ozsdei a ´rfolyamok alakul´ as´ an´ al is 5 . Az emberi beszéd vizsg´ alat´ an´ al szintén tal´ alkozunk ”k¨ olcs¨ onhat´ o rendszerekkel”, méghozz´ a két szinten is. Az a ´llati kommunik´ aci´ ot´ ol ugyanis éppen az u ń. ”kett˝ os tagolts´ ag” (”kett˝ os szerkezet”) k¨ ul¨ onb¨ ozteti meg az emberi beszédet (Kenesei [1995], p. 31.): a jelentés nélk¨ uli elemi hangok (”foném´ ak”, a klasszikus nyelvészeti iskol´ ak szerint) ép´ıtik fel a szavakat (”morfém´ akat”), melyekb˝ ol pedig a mondatok (”megnyilatkoz´ asok”) ép¨ ulnek fel. Mind a két szinten k¨ olcs¨ onhatnak a magasabb egységet alkot´ o ép´ıt˝ o elemek. A hangok rendszerét és k¨ olcs¨ onhat´ asait ´ırja le a fonol´ ogia 6 , m´ıg a morfém´ ak k¨ olcs¨ onhat´ asait a szintaxis (azaz ”mondattan”). Joggal mer¨ ulhet fel a kérdés, hogy vajon a nyelvi rendszer(ek) is rendelkezik (rendelkeznek)-e az eml´ıtett univerz´ alis tulajdons´ agokkal. Az elm´ ult évek vizsg´ alatai azt mutatj´ ak, mint azt a II. fejezetben ismertetni fogom, hogy igen. 1

Ld. pl. Derényi & Vicsek [1996]. Ld. pl. Geritz et al. [1997] 3 T¨ obb cikk is tal´ alhat´ o a komplex rendszerek és a k¨ ozgazdas´ agtan kapcsolat´ ar´ ol Martin´ as & Moreau [1995]-ben: pl. J. A. Holyst et al.: Control of Microeconomical Chaos. 4 M. H. R. Stanley et al. [1996a,b], Amaral et al. [1997] 5 Bouchaud & Potters [1997], Potters et al. [1997], Ghashghaie et al. [1996], Mantegna & Stanley [1996], Liu et al. [1997], Mantegna & Stanley [1995b, 1996] 6 A fonol´ ogia nem keverend˝ oo ¨ssze a fonetik´ aval, a hagyom´ anyos értelemben vett hangtannal, mely a beszédhangok fizikai tulajdons´ agaival, valamint képzés¨ uk és érzékelés¨ uk fiziol´ ogi´ aj´ aval foglalkozik. 2

4

A természetes nyelvi sz¨ ovegeken, pontosabban fogalmazva ´ırott sz¨ ovegeken végzett vizsg´ alatokkal anal´ og vizsg´ alatokat lehet végezni DNS-szekvenci´ akon. A vizsg´ alati m´ odszer szempontj´ ab´ ol a k¨ ul¨ onbség csup´ an abban az alap´ abécében van, melyb˝ ol felép¨ ul a szimb´ olumsorozat. T¨ obb, fizikusok a ´ltal ´ırt cikk jelent meg az elm´ ult években, melyek e két szekvenciat´ıpus hasonl´ os´ agaira mutatnak r´ a 7 . Viszont a DNS ”nyelve” vagy ”nyelvei” (amennyiben beszélhet¨ unk egy´ altal´ an ilyenr˝ ol, ld. Mantegna et al. [1994, 1995a] megjegyzései) sokkal kevésbé ismert, j´ oval nehezebben megismerhet˝ o, mint a természetes nyelvek rendszerei. Ugyanis sokat seg´ıt az ut´ obbi megismerésében a természetes nyelvek grammatik´ aj´ ar´ ol mindannyiunkban lév˝ o intu´ıci´ o. Teh´ at amennyiben siker¨ ul a nyelvi intu´ıci´ onk seg´ıtségével fel´ all´ıtott nyelvészeti elméleteket a statisztikus fizika eszk¨ ozeivel is megvizsg´ alni, a DNS statisztikai tulajdons´ agai elvezethetnek a genetikai k´ od grammatik´ aj´ anak jobb megismeréséhez. Tal´ an néh´ any, jelenleg még megmagyar´ azatlan tény és jelenség értelmezéséhez is k¨ ozelebb ker¨ ulhet¨ unk. Az egyik legnagyobb ilyen kérdés a DNS nem k´ odol´ o szakaszainak, péld´ aul az intronoknak, a szerepére vonatkozik. Lehet, hogy ezek a szakaszok is fontos inform´ aci´ okat tartalmaznak, m´ asok szerint ”biztons´ agi” jelent˝ oség¨ uk van (n¨ ovelik a genetikai k´ od redundanci´ aj´ at), de létezik olyan vélemény is, mely szerint semmi jelent˝ oség¨ uk sincs, csup´ an ”evol´ uci´ os szemetek”, a m´ ult emlékei. Az alkalmazott elj´ ar´ asok lényege az, hogy − a fizika jellegének megfelel˝ oen − a jelenségeket kvantitat´ıv ”s´ıkra terelj¨ uk”. De a felhaszn´ alt m´ odszerek j´ oval o ¨sszetettebbek, mint a hagyom´ anyos kvantitat´ıv nyelvészet 8 statisztikai m´ odszerei. A kapott eredményeket, a természettudom´ anyos megismerés szab´ alyai szerint, modellekkel igyeksz¨ unk o ¨sszevetni. A jelen esetben sztochasztikus eszk¨ oz¨ ok j¨ ohetnek sz´ oba, u ´gy mint a Markov-l´ ancok és a form´ alis nyelvek elméletének sztochasztikus formalizmussal t¨ ortén˝ o kiterjesztései. Ehhez kapcsolhat´ o majd a kés˝ obbiekben a szintén fizikai fogalmak anal´ ogi´ aj´ ara sz¨ uletett, Shanonféle inform´ aci´ oelmélet. A 2. fejezetben o ¨sszefoglalom az 1990-es évek els˝ o felében DNS-szekvenci´ akon és ´ırott nyelvi sz¨ ovegeken végzett, a szimb´ olumszekvenci´ ak hossz´ ut´ av´ u korrel´ aci´ oinak felt´ ar´ as´ ara ir´ anyul´ o kutat´ asok eredményeit. A tov´ abbiakban arra leszek k´ıv´ ancsi, hogy ezek az eredmények milyen k¨ ovetkezményekkel j´ arnak a k´ odol´ o mechanizmusra nézve. Feltételezem, hogy a szimb´ olumsorozat le´ırhat´ o a form´ alis nyelvek eszk¨ ozeivel, amely elméletnek az alapjait a 3. fejezetben ismertetem. A 4. fejezetben anal´ ogi´ akra mutatok r´ a a DNS- és a természetes nyelvi jelsorozatok k¨ oz¨ ott. Az 5. fejezetben kib˝ ov´ıtem a form´ alis nyelvek elméletét sztochasztikus eszk¨ oz¨ okkel, hogy az a ´ltalam javasolt anal´ ogi´ ak seg´ıtségével megmagyar´ azhassuk a két t´ıpus´ u szekvencia hasonl´ o tulajdons´ agait. A 6. fejezetben bevezetek egy olyan m´ odszert, amely, az ´ırott sz¨ ovegek r¨ ovidt´ av´ u korrel´ aci´ okb´ ol ad´ od´ o jellegzetességei alapj´ an, a sz¨ ovegek nyelvi és tartalmi hasonl´ os´ ag´ ara ad egy ”mértéket”. Ezt a m´ odszert a 7. fejezetben DNS-szekvenci´ akra is alkalmazom, és r´ amutatok a k´ odol´ o és nem-k´ odol´ o szakaszok u ´jabb eltér˝ o viselkedésére. Végezet¨ ul, a 8. fejezetben o ¨sszefoglalom eredményeimet.

7 8

Dietler & Zhang [1994], Mantegna et al. [1994, 1995a]. Példaként ld. Nagy F. [1986]-ot. 5

2. Hossz´ ut´ av´ u korrel´ aci´ ok A kilencvenes években egyre nagyobb mennyiségben kész¨ ulnek el vir´ alis, bakteri´ alis, n¨ ovényi, a ´llati és emberi kromosz´ om´ ak fizikai térképei. Ezen adatok meglehet˝ osen ”unalmas” adatb´ azisokban tal´ alhat´ ok meg: a négy b´ azisnak (A: adenin, C: citozin, G: guanin és T: timin) megfelel˝ oen, négy bet˝ u véget nem ér˝ o sorozat´ at alkotj´ ak. Id˝ onként v´ altozatoss´ agot jelent egy-egy egzotikus b´ azis felbukkan´ asa. Miféle érdekes inform´ aci´ o nyerhet˝ o ezen sz´ azezres nagys´ agrend˝ u b´ azisp´ ar-szekvenci´ ab´ ol? 1992-ben C.-K. Peng és t´ arsai, t¨ obbség¨ uk a Bostoni Egyetem munkat´ arsa, érdekes 1 megfigyeléseiket hozt´ ak nyilv´ anoss´ agra a Nature has´ abjain. Egydimenzi´ os bolyong´ ass´ a a ´talak´ıtva a DNS-szekvenci´ at (”DNA walk”), hossz´ ut´ av´ u korrel´ aci´ okat fedeztek fel az intronokat tartalmaz´ o szekvenci´ akban, melyek hi´ anyoztak az exonokban, valamint a c-DNS2 ekben, és az intront nem tartalmaz´ o génekben. A m´ odszert m´ as fizikusok felhaszn´ alt´ ak ´ırott sz¨ ovegek elemzésére is. 3 Az elj´ ar´ as lényege a k¨ ovetkez˝ o: képzelj¨ unk el egy bolh´ at, melyet egy sz´ amegyenes orig´ oj´ aba helyez¨ unk. Felolvassuk neki a szekvenci´ at, és amennyiben pirimidinv´ azas b´ azist hall (C vagy T), u ´gy el˝ ore lép egyet, m´ıg purinv´ azas b´ azis esetén (A vagy G) h´ atra lép. Amennyiben ui -vel jel¨ olj¨ uk az i-ik lépést (ui = ±1), u ´gy a bolha helyzete az i-ik lépés ut´ an nyilv´ an y(l) =

l X

ui .

(2.1)

i=1

A mozg´ ast jellemz˝ o statisztikus fizikai mennyiség az y(l)-nek az elmozdul´ as a ´tlaga k¨ or¨ ul vett F (l) a ´tlagos fluktu´ aci´ oja (root mean square fluctuation):

ahol

2 F 2 (l) = (∆y(l)− < ∆y(l) >)2 = ∆y(l)2 − h∆y(l)i , ∆y(l) = y(l0 + l) − y(l0 ),

(2.2)

(2.3)

és az o ¨sszes lehetséges l0 poz´ıci´ ora kell az a ´tlagol´ ast képezni. 2 Az F (l) szoros o ¨sszef¨ uggésben a ´ll az C(l) =< u(l0 )u(l0 + l) > − < u(l0 ) >2

(2.4)

autokorrel´ aci´ os f¨ uggvénnyel: 1

Peng et al. [1992], Stanley et al. [1992, 1993a,b], Peng et al. [1993] . A c-DNS a fehérjeszintézis sor´ an haszn´ alt RNS egy m´ asolata, melyet megford´ıtott transkripci´ oval kaphatunk meg. 3 Schenkel et al. [1993], Amit et al. [1994], Dietler & Zhang [1994], Ebeling & Neiman [1995]. 2

6

F 2 (l) =

l X l X i=1 j=1

C(j − i).

(2.5)

Ebb˝ ol k¨ ovetkezik, hogy − C(l) viselkedését˝ ol f¨ ugg˝ oen − F (l) h´ aromféle viselkedést mutathat: • Amennyiben véletlen sorozattal a ´llunk szemben, azaz C(l) = 0 a ´tlagban (kivéve az l = 0 esetet, hiszen C(0) = 1), akkkor klasszikus, korrel´ alatlan bolyong´ asr´ ol van sz´ o: α = 0, 5 kitev˝ oj˝ u hatv´ anyf¨ uggvényként cseng le az F (l). • R¨ ovidt´ av´ u korrel´ aci´ ok esetén adott a korrel´ aci´ ok R karakterisztikus hossza, azaz az autokorrel´ aci´ os f¨ uggvény C(l) ∼ exp(−l/R) viselkedést mutat. Az F (l) aszimpt´ otikus viselkedése ebben az esetben is α = 0, 5 kitev˝ oj˝ u hatv´ anyf¨ uggvény lesz. • Hossz´ ut´ av´ u korrel´ aci´ ok esetén viszont, C(l) nem jellemezhet˝ o R karakterisztikus hosszal, hanem − exponenci´ alis helyett − hatv´ anyf¨ uggvényszer˝ u viselkedést tapasztalunk. Ennek k¨ ovetkezménye F (l)-re nézve az lesz, hogy az α-kitev˝ o értéke eltér a 0, 5 értékt˝ ol. Az eltérés mértéke jellemzi a hossz´ ut´ av´ u korrel´ aci´ ok er˝ osségét. Az α = 1 eset felel meg a sk´ alainvari´ ans 1/f zajnak (”maximal complexity limit”) (Amit et al. [1993]). Az al´ abbi esetekben 0, 5 és 1 k¨ oz¨ otti értékeket fogunk tal´ alni. Az elj´ ar´ as a ´tvihet˝ o természetes nyelvi ´ırott sz¨ ovegekre is. Ebben az esetben egyaz-egyhez k´ odol´ ast alkalmaztak, azaz a ´t´ırt´ ak a sz¨ oveget egy bin´ aris a ´bécé seg´ıtségével (szemben a ”DNA-walk”-kal, ahol is két-két b´ azist ugyan´ ugy k´ odoltak). Péld´ aul o ¨t biten kit˝ un˝ oen lehet k´ odolni az angol a ´bécé 26 bet˝ ujét, a sz´ ok¨ ozt, és a legfontosabb ´ır´ asjeleket. Az eredmények nagyon érdekesek. A vizsg´ alt DNS-szekvenci´ ak nagyon j´ ol szétv´ alaszthat´ ok két csoportba: a tiszt´ an k´ odol´ o szakaszokb´ ol a ´ll´ o szekvenci´ ak α = 0, 50 ± 0, 01 exponenssel jellemezhet˝ ok, azaz nem mutatnak hossz´ ut´ av´ u korrel´ aci´ okat, szemben az intront is tartalmaz´ o szekvenci´ akkal, melyek esetében α = 0, 61 ± 0, 03. (Peng et al. [1992]) Írott sz¨ ovegek esetében, a vizsg´ alathoz haszn´ alt sz¨ ovegek k¨ oz¨ ott megtal´ aljuk a Biblia eredeti, héber nyelv˝ u sz¨ ovegét, valamint modern ford´ıt´ asait, tov´ abb´ a Shakespearedr´ am´ akat, regényeket, s˝ ot egy sz´ ot´ arat is. Néh´ any érdekesebb eredmény: • A sz¨ ovegek sok nagys´ agrenden kereszt¨ ul a ´lland´ o α-exponenssel jellemezhet˝ oek, melynek értéke a ´ltal´ aban 0, 6 − 0, 7 k¨ ozé esik (Schenkel et al. [1993]). • A kitev˝ o értéke nem jellemz˝ o a szerz˝ ore, hiszen péld´ aul a Hamlet exponense 0, 56, m´ıg a R´ ome´ o és J´ uli´ aé 0, 6 (Schenkel et al. [1993]). • A ford´ıt´ asok sor´ an, u ´gy t˝ unik, a korrel´ aci´ o mértéke cs¨ okken. Hab´ ar a Biblia exponense kimagasl´ oan magas (∼ 0, 75), a ford´ıt´ asai sor´ an ezen érték szisztematikusan cs¨ okken. 4 (Amit et al. [1994]) • A sz´ ot´ ar a sz´ ocikkek hossz´ an´ al j´ oval hosszabb korrel´ aci´ okat mutat, amely jelenség nem magyar´ azhat´ o puszt´ an a tartalom korrel´ alts´ ag´ aval (Schenkel et al. [1993]). • A sz¨ ovegeket kisebb részletekre, péld´ aul szavakra, mondatokra vagy l = 10 − 10000 karakter hossz´ us´ ag´ u, azonos darabokra szabdalva, a szabdal´ as hossz´ anak nagys´ agrendjéig 4

Nem tal´ altam a szakirodalomban vil´ agos v´ alaszt arra a kérdésre, hogy a magas hatv´ anykitev˝ o miért nem lehet a héber nyelvnek vagy ortogr´ afi´ anak jellegzetes tulajdons´ aga. 7

megmaradnak a korrel´ aci´ ok, azon t´ ul pedig elt¨ unnek. Ezek szerint a sz´ ot´ ar sz´ ocikkeinek elrendezése ”nem véletlenszer˝ u”, el˝ ozetes sejtés¨ unkkel ellentétben, ´ırja (Schenkel et al. [1993]). Leford´ıtott sz´ am´ıt´ ogépprogramokat (.exe-file-okat) is megvizsg´ altak, ezek esetében ´ 0, 9-et is meghalad´ o kitev˝ ot tal´ altak (Schenkel et al. [1993]). Erdekes még a ”hum´ an véletlensz´ amgener´ ator” vizsg´ alata: az egyik szerz˝ o 0 és 9 k¨ oz¨ ott ´ırt le sz´ amokat, ”véletlenszer˝ uen”. A véletlenszer˝ u eloszl´ asra val´ o t¨ orekvés eredményeképpen, r¨ ovid t´ avon (l ∼ 10) antikorrel´ aci´ ot fedezhet¨ unk fel, de ennél hosszabb t´ avon − a sz´ amokat gener´ al´ o személy minden igyekezete ellenére − megjelentek a korrel´ aci´ ok. R´ aad´ asul, a hatv´ anykitev˝ o értéke nem is a ´lland´ o, tart az 1-hez! A szerz˝ ok ezt u ´gy magyar´ azz´ ak, hogy − ellentétben a sz¨ ovegekkel és a sz´ am´ıt´ ogépes programokkal −, a véletlensz´ am gener´ al´ as nem rendelkezik értelmes céllal, vagyis a tudattalan tényez˝ ok, melyeket felel˝ ossé tesznek a hossz´ ut´ av´ u korrel´ aci´ okért, nagyobb szerepet j´ atszhatnak (Schenkel et al. [1993]). Az al´ abbiakban azt vizsg´ alom meg, milyen k¨ ovetkezményekkel j´ arnak ezek a megfigyelések a jelsorozatot létrehoz´ o folyamatok alkalmas modelljének természetére vonatkoz´ oan. Mindenek el˝ ott, be kell vezetn¨ unk a form´ alis nyelv fogalm´ at (Révész [1979] alapj´ an), melyet széles k¨ orben haszn´ alnak a természetes és sz´ am´ıt´ ogépes nyelvek le´ır´ as´ ara. Amellett is felhozok majd érveket, miért tartom hasznosnak ezen matematikai konstrukci´ o alkalmaz´ as´ anak kipr´ ob´ al´ as´ at a genetik´ aban. A form´ alis nyelvek elmélete az algebra bevett a ´gai k¨ ozé tartozik, de hasznosnak tartom az alapfogalmak o ¨sszefoglal´ as´ at, hiszen ez a témak¨ or nem része a fizikus szak tananyag´ anak.

3. Alapfogalmak a form´ alis nyelvek elm´ elet´ eb˝ ol A form´ alis nyelvek elméletének a célja a természetes és sz´ am´ıt´ ogépes nyelvek le´ır´ asa. Az alapgondolat az, hogy a nyelvet, mint a ”j´ olform´ alt mondatok”− azaz a nyelvhez tartoz´ o, a ´bécébeli sztringek − halmaz´ at, nem csak a halmaz elemeinek a felsorol´ as´ aval, vagy a halmazok megad´ as´ an´ al megszokott, egyszer˝ u szab´ alyok seg´ıtségével defini´ alhatjuk. Megadhatunk egy nyelvet a ”szerkezetének” le´ır´ as´ aval is, generat´ıv grammatika seg´ıtségével, valamint olyan automata révén, mely a nyelv ”mondatait”, ”formul´ ait”, és csak azokat fogadja el. Mindkét fogalom egy véges vagy végtelen halmazt ad meg, véges eszk¨ oz¨ okkel. Ezen gondolat m¨ og¨ ott az a ´ll, hogy a gyermek az anyanyelvét nyilv´ an nem a hallott mondatok egyszer˝ u reproduk´ al´ as´ aval saj´ at´ıtja el: egyrészt, nem hallhatja a nyelv o ¨sszes, potenci´ alisan végtelen sz´ am´ u mondat´ at, és képes olyan mondatot is reproduk´ alni, amelyet el˝ oz˝ oleg nem hallott. ; tov´ abb´ a, egyszer˝ u ismétlés esetén, nem hib´ azna, hiszen feltehet˝ oleg csak helyes mondatot hall. Teh´ at − legal´ abbis Chomsky és k¨ ovet˝ oi szerint − a gyermek a nyelv szab´ alyait saj´ at´ıtja el. A form´ alis nyelvek elméletében, valamilyen L nyelv egy nem¨ ures, véges Σ halmaz, az u ń. a ´bécé f¨ ol¨ ott, defin´ıci´ o szerint nem m´ as, mint a Σ elemeib˝ ol képzett, véges hossz´ us´ ag´ u sztringek egy halmaza. (Az n hossz´ us´ ag´ u sztring egy rendezett n-est jelent matematikailag.) Jel¨ olje Σ+ a Σ elemeib˝ ol képezett, pozit´ıv (véges) hossz´ us´ ag´ u sztringek halmaz´ at, Σ ∗ pedig 8

ennek kib˝ ov´ıtését az e (”empty”) u ¨res, azaz nulla hossz´ us´ ag´ u sztringgel. Ekkor egy L nyelv Σ f¨ ol¨ ott nem m´ as, mint Σ∗ egy részhalmaza:

.

L ⊆ Σ∗

Az al´ abbiakban ”sz´ o”, ”mondat”, ”jelsorozat”, ”formula” kifejezéseket a ”sztring” szinon´ım´ ajaként fogom haszn´ alni, a ”jel”, ”bet˝ u”, ”szimb´ olum” szavak pedig az a ´bécé elemeire fognak utalni. A sz´ ohaszn´ alat a konkrét implement´ aci´ ot´ ol f¨ ugg: szintaxis (mondattan) esetén péld´ aul Σ szavakat tartalmaz. Két formula, X és Y konkaten´ aci´ oj´ an azt a Z formul´ at értj¨ uk, amelyet u ´gy kapunk, hogy X-et és Y -t ”egym´ as mellé ´ırjuk”, o ¨sszef˝ uzz¨ uk: Z = XY . Nyilv´ anval´ o, hogy Σ ∗ a konkaten´ aci´ o m˝ uveletével egy¨ utt egységelemes félcsoportot alkot, ahol az e u ¨res sz´ o j´ atssza az egységelem szerepét. A generat´ıv grammatika fogalm´ anak defin´ıci´ oja Révész [1979.] alapj´ an az al´ abbi: 1. Defin´ıci´ o: Egy G generat´ıv grammatik´ an az al´ abbi rendezett négyest értj¨ uk: G = (VN , VT , S, F ), ahol VN és VT diszjunkt véges a ´bécék, S ∈ VN , az F pedig olyan rendezett (P, Q) p´ aroknak egy véges halmaza, melyekre P, Q ∈ V ∗ (V := VT ∪ VN ), és P legal´ abb egy VN -beli jelet tartalmaz. A VN elemeit nemtermin´ alisok elemeknek, VT elemeit pedig termin´ alis jeleknek fogjuk nevezni, az al´ abbiakban ismertetend˝ o okokb´ ol. Az F elemeit helyettes´ıtési szab´ alyoknak (rewriting rules) h´ıvjuk, és P → Q alakban ´ırjuk. Az S kit¨ untetett nemtermin´ alis elem neve: mondatszimb´ olum. Az al´ abbi m´ odon defini´ aljuk a levezetés fogalm´ at: 2. Defin´ıci´ o: Adott G = (VN , VT , S, F ) grammatika esetén, X, Y ∈ V ∗ -ra azt mondjuk, hogy Y levezethet˝ o X-b˝ ol, azaz X ⇒ Y , ha létezik olyan P1 , P2 , P, Q ∈ V ∗ , hogy X = P1 P P2 , Y = P1 QP2 , valamint (P → Q) ∈ F .

Ez azt jelenti, hogy ha X-ben P -t u ´jra´ırjuk Q-val az egyik F -beli helyettes´ıtési szab´ aly ∗ alkalmaz´ as´ aval, u ´gy Y -t kapjuk. Jel¨ olj¨ uk a ⇒ rel´ aci´ o tranzit´ıv lez´ artj´ at ⇒ -val, azaz ∗ X ⇒ Y csakkor a ´ll fenn, ha X-b˝ ol kiindulva, F -beli u ´jra´ırøszab´ alyok nulla vagy véges sz´ am´ u alkalmaz´ as´ aval, eljuthatunk Y -ba. Egy G grammatika a ´ltal gener´ alt L(G) nyelv az S mondatszimb´ olumb´ ol levezethet˝ o, termin´ alis elemekb˝ ol a ´ll´ o mondatok halmaz´ at jelenti: L(G) := {P ∈ VT∗ |S ⇒∗ P }

Azt mondjuk, hogy az L nyelvet a G grammatika gener´ alja, ha L = L(G). A termin´ alisok VT halmaz´ anak szerepét a Σ a ´bécé t¨ olti be, amikor egy nyelvhez grammatik´ at gy´ artunk. Két grammatik´ at gener´ al´ as szempontj´ ab´ ol ekvivalensnek nevez¨ unk, ha ugyan azt a nyelvet gener´ alj´ ak. A form´ alis nyelvek elméletének alapvet˝ o kérdése az, hogy milyen t´ıpus´ u nyelvekhez milyen grammatik´ akat adhatunk meg. Azaz milyen k¨ ovetkezményekkel j´ ar, ha megk¨ otéseket tesz¨ unk a helyettes´ıtési szab´ alyok alakj´ ara. Noam Chomsky az al´ abbi nyelvoszt´ alyokat vezette be (Révész [1979.]): 3. Defin´ıci´ o: A G = (VN , VT , S, F ) grammatik´ at i-t´ıpus´ unak nevezz¨ uk, ha az al´ abbiak k¨ oz¨ ul az i-ik teljes¨ ul: 9

i = 0: Nincs semmilyen kik¨ otés. i = 1: Az F minden eleme Q1 XQ2 → Q1 P Q2 alak´ u, ahol Q1 , Q2 , P ∈ V ∗ , X ∈ VN és P 6= e, kivéve esetleg az S → e szab´ alyt, amely viszont csak u ´gy szerepelhet az F -ben, ha az S nem fordul el˝ o semelyik szab´ alynak sem a jobb oldal´ an. i = 2: Az F minden eleme X → P alak´ u, ahol X ∈ VN , és P ∈ V ∗ . i = 3: Az F minden eleme X → P Y vagy X → P alak´ u, ahol X, Y ∈ VN , és P ∈ VT∗ . Valamely L nyelvet i-t´ıpus´ unak mondunk, ha létezik hozz´ a i-t´ıpus´ u grammatika. Az i-t´ıpus´ u grammatik´ ak oszt´ aly´ at Gi -vel, m´ıg az i-t´ıpus´ u nyelvek csal´ adj´ at Li -vel szok´ as jel¨ olni. Bel´ athat´ o, hogy ezen nyelvoszt´ alyok egym´ as val´ odi részhalmazai: L3 ⊂ L 2 ⊂ L 1 ⊂ L 0 Az i = 0 nyelvoszt´ alyt mondatszerkezet˝ u nyelveknek nevezz¨ uk. Az i = 1 t´ıpus´ u grammatik´ ak helyettes´ıtési szab´ alyai u ´gy néznek ki, hogy az X nemtermin´ alist ´ırjuk u ´jra, a Q1 Q2 k¨ ornyezetben, ahol jelzi X helyét. Ezért az i = 1 grammatika-, ill. nyelvoszt´ alyt k¨ ornyezetf¨ ugg˝ onek (context-sensitive, CS) nevezz¨ uk, szemben az i = 2 k¨ ornyezetf¨ uggetlen (context-free, CF) oszt´ allyal. Az i = 3 esetben pedig regul´ aris oszt´ alyokr´ ol beszél¨ unk. A form´ alis nyelvekkel szoros kapcsolatban a ´llnak az automata-elméletb˝ ol ismert gépek. Egy nyelvet elfogad valamely automata, ha a nyelv mondatait, és csak azokat fogadja el. Az egyes nyelvoszt´ alyok ilyen alapon megfeleltethet˝ oek az egyes automata-t´ıpusoknak. Erre a kérdésre − hely hi´ any´ aban − nem fogok részletesen kitérni. Egyed¨ ul a véges a ´llapot´ u automat´ ak alapgondolat´ at ismertetem, mivel a kés˝ obbiekben még visszatérek ezek kapcsolat´ ara a Markov-l´ ancokkal. A regul´ aris grammatik´ ak csak lok´ alis jelenségeket tudnak le´ırni. Az al´ abbiakban l´ atni fogjuk kapcsolatukat a Markov-l´ ancokkal, vagyis az ilyen nyelvek esetén nem v´ arunk hossz´ ut´ av´ u korrel´ aci´ okat (lesz´ am´ıtva természetesen a determinisztikus esetet). Bel´ athat´ o, hogy regul´ aris nyelvekhez, és csak azokhoz szerkeszthet˝ o elfogad´ o véges a ´llapot´ u automata (Révész [1979.]): 4. Defin´ıci´ o: Egy véges automat´ an az A = (K, T, M, q0, H) rendezett o ¨t¨ ost értj¨ uk, ahol K egy véges, nem u ¨res halmaz, az a ´llapothalmaz, T egy véges a ´bécé, a bemen˝ oa ´bécé, M a K × T halmaznak egy leképezése a K-ra, az a ´tmenetf¨ uggvény, q0 ∈ K a a kezd˝ oa ´llapot, H ⊆ K a vég´ allapotok halmaza. A véges a ´llapot´ u automata m˝ uk¨ odése a k¨ ovetkez˝ o: elindul a kezd˝ oa ´llapotb´ ol, az els˝ o lépésben beolvassa a bemen˝ o szalagra ´ırt mondat els˝ o jelét (∈ T ), és a beolvasott jel, valamint az éppen aktu´ alis a ´llapot f¨ uggvényében, az M a ´ltal meghat´ arozott a ´llapotba megy a ´t. A k¨ ovetkez˝ o lépésben u ´jabb jelet olvas be a szalagr´ ol, és ez alapj´ an u ´jabb a ´llapotba ”ugrik” − feltéve, hogy az aktu´ alis a ´llapot és a beolvasott jel a ´ltal alkotott rendezett p´ ar ´ eleme az M a ´tmenetf¨ uggvény értelmezési tartom´ any´ anak. Es ´ıgy tov´ abb, egészen addig, am´ıg el nem akad az automata m˝ uk¨ odése, vagy el nem olvasta az egész mondatot. Azt mondjuk, hogy az automata elfogadott egy mondatot, ha végigolvasta azt, és az utols´ o 10

a ´llapot eleme H-nak. (Ez a folyamat formaliz´ alhat´ o ”´ allapotsorozatok” defini´ al´ as´ aval, de ett˝ ol most tekints¨ unk el.) A véges a ´llapot´ u automata jellemz˝ oje, hogy nem rendelkezik ”mem´ ori´ aval” (végtelen veremmel), és ebb˝ ol k¨ ovetkezik majd a hossz´ ut´ av´ u korrel´ aci´ ok hi´ anya a regul´ aris nyelveknél. Péld´ aul az La := {an bn |n > 0} nyelv (ahol an n darab ’a’ konkaten´ aci´ oj´ at jelenti) azért nem lehet regul´ aris, mert a ’b’-k beolvas´ asakor ”tudnunk kell” azt, hogy mennyi ’a’-t olvastunk be el˝ oz˝ oleg. M´ arpedig, az ’a’-k sz´ ama tetsz˝ olegesen nagy lehet, ´ıgy ezt a végtelen sok lehet˝ oséget nem tudjuk véges sok a ´llapot seg´ıtségével ”megjegyezni”. Ezzel szemben, a nem-regul´ aris k¨ ornyezetf¨ uggetlen nyelvek tetsz˝ olegesen sok ”be´ agyaz´ ast” tesznek lehet˝ ové. Tipikus péld´ at szolg´ altatnak erre − a fentebb megadott L a halmazon k´ıv¨ ul − a sz´ am´ıt´ ogépes nyelvek, ahol a ciklusszervezés jelenti az egym´ asba a ´gyazott strukt´ ur´ akat, valamint a z´ ar´ ojelezett matematikai kifejezések. Chomsky [1957] amellett érvel, hogy az angol nyelv − és a ´ltal´ aban a természetes nyelvek − szintaxisa is k¨ ornyezetf¨ uggetlen grammatik´ aval adhat´ o meg, melyet a transzform´ aci´ ok a ´talak´ıthatnak. (Ellenpéldaként szok´ as felhozni egyes holland szerkezeteket, melyeket k¨ ornyezetf¨ ugg˝ o szab´ alyokkal érdemes csak le´ırni. Ezekt˝ ol azonban tekints¨ unk el, mint ahogy azt a legt¨ obb nyelvész is teszi.) A k¨ ornyezetf¨ uggetlen nyelvek mondatainak jellemz˝ oje a l´ atv´ anyos hierarchikus szerkezet. Egy formula levezetését egy gr´ affal (ir´ any´ıtott f´ aval) a ´br´ azolhatjuk, melynek ”gy¨ okere” a mondatszimb´ olum, végpontjai (”levelei”) a levezetett mondat szavai. A k¨ oztes csom´ opontok pedig a levezetés sor´ an megjelen˝ o nemtermin´ alisoknak felelnek meg, amelyb˝ ol indul´ o élek végpontjait ”¨ osszeolvasva”, azon helyettes´ıtési szab´ aly jobb oldal´ at kapjuk meg, ´ amellyel u ´jra´ırtuk a nemtermin´ alist. Igy péld´ aul azt mondhatjuk (nagyon leegyszer˝ us´ıtve a kérdés nyelvészeti oldal´ at), hogy az S mondatszimb´ olumb´ ol levezethet˝ o magyar mondat a ´ll egy f˝ onévi csoportb´ ol (NP), amely az alany szerepét t¨ olti be, és egy igei csoportb´ ol (VP). Azaz fel´ırhat´ o a k¨ ovetkez˝ o szab´ aly: S → NP VP. Maga az igei csoport is felép¨ ulhet igéb˝ ol (V), t´ argyb´ ol és hat´ aroz´ okb´ ol (ut´ obbiak szintén NP-k, azaz f˝ onévi csoportok): VP → VP NP, illetve: VP → V. A f˝ onévi csoport pedig a ´llhat f˝ onevekb˝ ol (N) és melléknevekb˝ ol (A): NP → A NP, és NP → N. Majd a V, N és A nemtermin´ alisokat helyettes´ıthetj¨ uk a megfelel˝ o kateg´ ori´ aj´ u (”sz´ ofaj´ u”) magyar szavakkal (termin´ alisokkal). A fenti szab´ alyok péld´ at mutatnak a rekurzi´ ot lehet˝ ové tev˝ o szab´ alyokra is, melyek seg´ıtségével lehet egy végtelen sok mondatb´ ol a ´ll´ o nyelvet le´ırni a generat´ıv grammatik´ ak véges eszk¨ ozével. A k¨ ornyezetf¨ uggetlen nyelvekhez kész´ıtett elfogad´ o automat´ ak oszt´ alya az u ń. veremautomat´ ak. Adott k¨ ornyezetf¨ uggetlen grammatik´ ahoz kész´ıthet˝ o olyan automata is (´ un. parser), amely a termin´ alisok line´ aris szekvenci´ aj´ ab´ ol el˝ oa ´ll´ıtja az azt létrehoz´ o levezetés(ek) sor´ an alkalmazott szab´ alyok sorozat´ at. K¨ ornyezetf¨ ugg˝ o nyelvre példa az Lb := {an bn cn |n > 0} nyelv. (A k¨ ornyezetf¨ uggetlen nyelvekre sz¨ ukséges feltételt kir´ ov´ o Bar Hillel lemma seg´ıtségével l´ athat´ o be, hogy L b -hez nem adhat´ o meg k¨ ornyezetf¨ uggetlen grammatika.) A k¨ ornyezetf¨ uggetlenséget kiz´ arja, ha a ”korrel´ aci´ ok” egym´ ast keresztezik, nincsennek egym´ asba a ´gyazva, mintha megengednénk a k¨ ovetkez˝ o ”z´ ar´ ojelezést”: (...[...)...] . 11

Az L1 nyelvoszt´ aly a line´ arisan korl´ atolt automat´ ak a ´ltal elfogadott nyelvek oszt´ aly´ aval egyezik meg, m´ıg a mondatszerkezet˝ u nyelveket elfogad´ o automat´ ak éppen a h´ıres Turinggépek. K¨ ornyezetf¨ ugg˝ o grammatik´ at haszn´ alnak a fonol´ ogusok, a nyelvekben lej´ atsz´ od´ o hangtani folyamatok jellemzésére. Viszont Kaplan és Kay [1994] bebizony´ıtja, hogy a fonol´ ogiai modellek a ´ltal´ aban olyan feltételeket r´ onak ki a szab´ alyok alkalmaz´ as´ ara, amelyek regul´ ariss´ a reduk´ alj´ ak a folyamatokat. Erre hivatkozva, az al´ abbiakban feltételezem, hogy a fonol´ ogia − elvileg − fel´ırhat´ o regul´ aris szab´ alyok seg´ıtségével is. L´ attuk, hogy a form´ alis nyelvek elmélete éppannyira hasznos a nyelvészetben, mint ´ a sz´ am´ıt´ astechnik´ aban. Ugy vélem, a genetik´ aban is eredményesen lehetne felhaszn´ alni ezt a modellt. Hiszen a fehérjék hasonl´ o hierarchikus szerkezettel rendelkeznek, mint a k¨ ornyezetf¨ uggetlen nyelvek. Az els˝ odleges, m´ asodlagos és harmadlagos szerkezet egym´ asra ép¨ ulése, a funkci´ os csoportok elhelyezkedése, val´ osz´ın˝ uleg le´ırhat´ o ilyen eszk¨ oz¨ okkel, de saj´ at magam − hi´ anyos biokémiai ismereteim miatt − nem merek ezen a téren nyilatkozni. De u ´gy ”érzem”, hogy a fehérjeszerkezet-kutat´ asok alapj´ an fel´ırhat´ oak olyan k¨ ornyezetf¨ uggetlen u ´jra´ır´ o szab´ alyok, melyeket molekulafizikai sz´ am´ıt´ asokkal lehetne igazolni. A gondolatmenetet folytatva, a k¨ ovetkez˝ o kih´ıv´ ast azt jelentheti, hogy megérts¨ uk, ezek a k¨ ornyezetf¨ uggetlen szab´ alyok miként reduk´ al´ odnak regul´ ariss´ a, hiszen a c-DNSekb˝ ol hi´ anyz´ o korrel´ aci´ ok arra engednek k¨ ovetkeztetni, hogy a fehérjék ”szintaxisa” nem csak k¨ ornyezetf¨ uggetlen, hanem tal´ an regul´ aris is egyben. De térj¨ unk vissza az ”´ almodoz´ asaimb´ ol”, és tekints¨ uk a ´t, mi lehet a k¨ oz¨ os a vizsg´ alt jelenségekben? Milyen anal´ ogi´ ak vonhat´ ok a DNS-szekvenci´ ak és a természetes nyelvi sz¨ ovegek k¨ oz¨ ott, ami miatt hasonl´ o jelenségeket fedezt¨ unk fel benn¨ uk az el˝ oz˝ o fejezetben, valamint hasonl´ o modellek alkalmaz´ as´ at javasoltam r´ ajuk.

4. A genetikai k´ od ´ es a term´ eszetes nyelvek k¨ oz¨ otti anal´ ogi´ ak Milyen alapon lehet egy kalap al´ a venni a DNS-szekvenci´ akat, a természetes nyelvi sz¨ ovegeket, ´ valamint − hozz´ a vehetj¨ uk még − a sz´ amit´ ogépes programokat? Mindh´ arom ”jelenséget” az a szerkezet jellemzi, amit az a ´ltalam ”kett˝ os k´ odol´ asnak” (”double coding”, a ”kett˝ os tagolts´ ag” mint´ aj´ ara, ld. 1. fej.) nevezett folyamat hoz létre. Vélem´ nyem szerint, a ”kett˝ os k´ odol´ as” lényege abb´ ol a ´ll, hogy egy megval´ osítand´ ot ´ ´ u ´gy kell a ´talakitani a megval´ osit´ ov´ a, hogy egy line´ aris k´ od form´ aj´ aban t´ aroljuk az ”inform´ aci´ ot”. Linearit´ as alatt itt és a tov´ abbiakban a k´ odot alkot´ o szimb´ olumok line´ aris sorrendjét ertem, péld´ aul azt, hogy a karaktereket az ´ır´ as sor´ an egym´ as mellett helyezhetj¨ uk el. (Az ´ır´ as t¨ orténetének korai szakaszai mutatj´ ak, hogy ez a tény nem trivi´ alis.) A természetes nyelvi sz¨ ovegek esetén a ”megval´ os´ıtand´ o” a k¨ oz¨ olt inform´ aci´ o (a mondat vagy a sz¨ oveg jelentése), m´ıg a ”megval´ os´ıt´ o” a kiejtett hangsor. A DNS-szekvenci´ ak esetén a ”megval´ os´ıtand´ o”-t az enzim a ´ltal ell´ atand´ o funkci´ o jelenti, m´ıg a ”megval´ os´ıt´ o” maga az enzim. Sz´ am´ıt´ ogépes program esetében pedig, a programozand´ o feladat a ”megval´ os´ıtand´ o”, m´ıg a programk´ od a ”megval´ os´ıt´ o”. 12

A ”megval´ os´ıtand´ o” k¨ oz¨ os jellemz˝ oje mindh´ arom esetben a nem-linearit´ as. Egy mondat jelentése épp annyira komplex szerkezet˝ u lehet, mint egy biol´ ogiai vagy sz´ am´ıt´ ogépes feladat. A ”megval´ os´ıt´ o” kv´ azi-line´ aris. Ez azt jelenti, hogy a megval´ os´ıt´ ot majdnem teljes mértékben le´ırhatjuk line´ arisan. A ”kv´ azi” jelz˝ ovel a fehérjék m´ asodlagos és harmadlagos szerkezetére utalok, ill. arra, hogy a kiejtett hangkontinuumot igaz´ ab´ ol csak multiline´ arisan lehet le´ırni, a k¨ ul¨ onb¨ oz˝ o hangképz˝ o szervek helyzete vagy egy hang fizikai tulajdons´ agai egym´ ast´ ol t¨ obbé-kevésbé f¨ uggetlenek. A ”megval´ os´ıtand´ ot” a ”megval´ os´ıt´ oval” egy t¨ okéletesen line´ aris k´ od k¨ oti o ¨ssze. A kérdés az, hogy miként lehetséges a nem-line´ aris inform´ aci´ ot line´ ariss´ aa ´talak´ıtani oly m´ odon, hogy ne vesszen el semmi, azaz a megval´ os´ıt´ ot 1 a megval´ os´ıtand´ ohoz rendel˝ o leképezés invert´ alhat´ o legyen. Ez a ”kett˝ os k´ odol´ as” legtiszt´ abban a nyelvészet esetében figyelhet˝ o meg, ott o ¨sszef¨ uggésben van az emberi nyelv bevezet˝ oben eml´ıtett ”kett˝ os tagolts´ ag´ aval”. A szemantika a nemline´ aris jelentésb˝ ol megalkotja a szintaxis nem-line´ aris bemenetét, amit k´ odoland´ onak fogok nevezni. A k´ odoland´ ob´ ol a szintaxis létrehozza a line´ aris k´ odot. Ezt u ´gy teszi meg, hogy egy generat´ıv grammatik´ at haszn´ al, mely szab´ alyainak ismeretében, a k´ odb´ ol (a legener´ alt termin´ alis-sztringb˝ ol) visszafejthet˝ o a levezetési l´ anc (parsing), azaz a ”mondat” nemline´ aris szintaktikus strukt´ ur´ aja, ami viszont m´ ar a jelentés komplex szerkezetével f¨ ugg o ¨ssze. Péld´ aul a Béla fia szép fizikus l´ anyt l´ at. mondatb´ ol, a magyar nyelv szintaktikai szab´ alyainak az ismeretében, rekonstru´ alhat´ o a mondatot alkot´ o elemek egym´ ashoz val´ o viszonya. Ut´ obbit, z´ ar´ ojelek seg´ıtségével, az al´ abbi m´ odon a ´br´ azolhatjuk: (Béla fia) ((szép (fizikus l´ anyt)) l´ at). Visszatérve ”megval´ os´ıtand´ o” leképezésére ”megval´ os´ıt´ ov´ a”, a szintaxis kimenete a szavak (morfém´ ak) line´ aris sorrendje. Ez leképez˝ odik hangalakokk´ a, majd a morfol´ ogiaifonol´ ogiai szab´ alyok kisebb, lok´ alis v´ altoztat´ asokat eszk¨ oz¨ olnek ezen a line´ aris szekvenci´ an (´ un. igaz´ıt´ o szab´ alyok). A v´ altoztat´ asok egy részének oka legink´ abb az emberi hangképz˝ o szervek tehetetlensége, péld´ aul hasonul´ asok esetén, vagy a percepci´ o (megértés, rekonstru´ al´ as) el˝ oseg´ıtése, péld´ aul disszimilat´ıv folyamatokn´ al. (A természetes fonol´ ogia termi2 nusaival: szintagmatikai és paradigmatikai folyamatok .) A hangs´ uly és a hanglejtés, és esetleg m´ as artikul´ aci´ os jegyek is (péld´ aul az autoszegment´ alis fonol´ ogia megk¨ ozel´ıtésében), megt¨ orik a linearit´ ast, egy helyett néh´ any ”tengelyre” lesz sz¨ ukség¨ unk. Ezért a fonol´ ogia kimenete, a k´ odolt, k¨ ul¨ on¨ osen pedig a fonetika imm´ ar nem is diszkrét elemekb˝ ol a ´ll´ o, hanem folytonos kimenete, a megval´ os´ıt´ o, multi- vagy kv´ azi-line´ arisnak nevezhet˝ o. A 4.1 a ´bra foglalja o ¨ssze ezt a folyamatot. 1

Pontosabban sz´ olva: a leképezés inverze lehet˝ oleg ne legyen t¨ obb érték˝ u, és ha az esetek egy részében még t¨ obb érték˝ u is, akkor se legyen ”sok” érték˝ u. Hiszen a természetes nyelvekben el˝ ofordul a szerkezeti t¨ obbértelm˝ uség. A ”Péter és J´ anos kuty´ ai” esetében nem tudjuk, hogy a ”Péter + (J´ anos kuty´ ai)” vagy a ”(Péter és J´ anos) kuty´ ai” jelentésre gondolt az, aki kimondta a szerkezetet. Hasonl´ oképpen, ”Az oroszl´ an simogat´ asa veszélyes” jelentheti egyszerre azt, ha az oroszl´ an simogat, és azt is, ha az oroszl´ ant simogatj´ ak. 2 Ld. Kiefer [1994], p. 39. 13

megval´ os´ıtand´ o (jelentés) szemantika k´ odoland´ o szintaxis line´ aris k´ od morfofonol´ ogia k´ odolt fonetika megval´ os´ıt´ o (hang-kontinuum) 4.1 a ´bra: A kett˝ os k´ odol´ as szintjei

Fontos megjegyezni, hogy a fenti a ´bra mindkét ir´ anyba j´ arhat´ o, hiszen a beszédértés éppen a beszédprodukci´ oval ellentétes folyamat. A genetik´ aban még nem ismerj¨ uk kell˝ oképpen a részleteket. A ”line´ aris k´ od” szerepét nyilv´ anval´ oan a DNS-szekvencia t¨ olti be, ez k´ odolja a genetikai inform´ aci´ ot, hogy az a létrej¨ ov˝ o fehérjék els˝ odleges, m´ asodlagos és harmadlagos szerkezete révén val´ osuljanak meg. A genetikai inform´ aci´ o, mint ”megval´ os´ıtand´ o”, nyilv´ an meglehet˝ osen komplex. Ebben a képben a sejtbiol´ ogia felel meg a szemantik´ anak, hiszen a sejtben lezajl´ o folyamatok, a ”k´ odoland´ ok”, jelentik az els˝ o (utols´ o) lépést az inform´ aci´ o form´ aba o ¨ntése felé. A genetika (a biol´ ogiai rendszerek szintaxisa) a ´tk´ odolja a ”folyamatokat” DNS- szekvenci´ av´ a. A fehérje-szintézis el˝ obb lok´ alis v´ altoztat´ asokat hajt végre (”fonol´ ogia”), péld´ aul kihagyja az intronokat 3 , az m-RNS tekinthet˝ o ”k´ odoltnak”, majd a ribosz´ om´ akon ”materializ´ al´ odik” az inform´ aci´ o, ez az utols´ o szakasz (”fonetika”) hozza létre a megval´ os´ıtand´ o genetikai inform´ aci´ ot megval´ os´ıt´ o enzimet. Az enzimol´ ogia bez´ arja a k¨ ort, mivel megadja azt, hogy hogyan val´ os´ıtja meg a megval´ os´ıt´ o a megval´ os´ıtand´ ot. Ez a f´ azis a természetes nyelvek esetén hi´ anyzik, egyed¨ ul a kett˝ os tagol´ ast nem tartalmaz´ o kommunik´ aci´ o (pl. indulatszavak, a ´llati kommunik´ aci´ o, gesztusnyelv,...) létezik szoros kapcsolat a hang és a jelentés k¨ oz¨ ott. (A fenti gondolatmenetben meglep˝ o lehetett, hogy a genetik´ at mint a DNS-k´ od tudom´ any´ at eml´ıtettem, és péld´ aul a fehérjeszintézis kutat´ as´ at kiz´ artam a genetik´ ab´ ol. Lehet, hogy ez nagyon merész lépés, és jobb terminusokat kellett volna tal´ alnom, mint péld´ aul ”genetikai szintaxis”. De a d¨ ontésem oka a nyelvészeti anal´ ogia volt, ahol chomsky´ anus felfog´ as a szintaxist tekinti a nyelvészet magj´ anak. A m´ asik oka az volt, hogy feltételezem az egész dolgozatom sor´ an azt, hogy a DNS ”nem-k´ odol´ o” részei val´ oj´ aban nem ”evol´ uci´ os 3

Lehet, hogy ezen transzform´ aci´ ok a transzform´ aci´ os grammatik´ ak analogonjai? A felvetés val´ osz´ın˝ uleg t´ uls´ agosan messze vezetne, és a mai genetikai ismereteink nem teszik lehet˝ ové, hogy megalapozott v´ alaszt adjunk erre a kérdésre. 14

szemét”, hanem van szerepe, és olyan inform´ aci´ ot k´ odol, ami t´ ulmegy a fehérjék els˝ odleges szerkezetét k´ odol´ o, ismert mechanizmusokon. Amennyiben tényleg ´ıgy lenne, u ´gy a j¨ ov˝ o genetikai kutat´ asai a DNS-k´ od a jelenleginél mélyebb megértéseit fogj´ ak eredményezni.) Sz´ am´ıt´ ogépes programok esetén, a gondolatmenet hasonl´ o a fentiekhez. A feladat (a megval´ os´ıtand´ o) megfogalmaz´ asa (k´ odoland´ o) ut´ an, a programoz´ as folyamata nem m´ as, mint egy line´ aris k´ od létrehozatala, a sz´ am´ıt´ ogépes nyelv szintaxisa seg´ıtségével. A fonol´ ogi´ anak tal´ an az algoritmus le´ır´ o nyelv elvont utas´ıt´ asainak k´ odol´ asa jelenti, a programoz´ asi nyelv konkrét karaktersorozataként. Lok´ alis v´ altoztat´ asokat jelent péld´ aul megjegyzések besz´ ur´ asa. Ha az algoritmus le´ır´ o nyelv felel meg a Chomsky-féle univerz´ alis grammatik´ anak, akkor megfigyelhet˝ o, hogy a szintaxis kisebb, és a ”fonol´ ogia” nagyobb része nyelvspecifikus, mind a természetes, mind a sz´ am´ıt´ ogépes nyelvek esetén. Ez a meglehet˝ osen a ´ltal´ anos´ıt´ o meg´ allap´ıt´ as érthet˝ o, ha arra gondolunk, hogy a ”megval´ os´ıtand´ o” még teljesen f¨ uggetlen az alkalmazand´ o nyelvt˝ ol, m´ıg a ”megval´ os´ıt´ ot” a nyelv hozza létre. Minél k¨ ozelebb vagyunk a ”megval´ os´ıt´ ohoz”, ann´ al t¨ obb nyelvspecifikus jelenségre sz´ am´ıthatunk, mivel a ”megval´ os´ıt´ as” részeredménye az adott szinten maga is ann´ al ink´ abb nyelvspecifikus. Hogyan lehet a fenti gondolatmenetet igazolni, honnan tudjuk, hogy ilyen m´ odon magyar´ azhat´ oak a DNS-szekvenci´ ak és ´ırott nyelvi sz¨ ovegek elemzésénél tal´ alt hasonl´ o jelenségek? (Programoz´ asi nyelvekkel a tov´ abbiakban nem foglalkozom.) A megval´ os´ıtand´ o a ´tfogalmaz´ asa k´ odoland´ ov´ a egy logikai strukt´ ura létrehoz´ as´ at jelenti. Ez feleltethet˝ o meg a szintaxis a ´ltal haszn´ alt k¨ ornyezetf¨ uggetlen generat´ıv grammatika levezetési f´ ainak, gondoljunk csak a fenti, z´ ar´ ojelezett példamondatra. (A levezetési f´ ak ekvivalensek a z´ ar´ ojelezéssel.) Ezzel a megfeleltetéssel a dolgozatomban nem foglalkozom részletesen. Teh´ at az elemi o ¨sszetev˝ ok k¨ oz¨ otti komplex strukt´ ur´ ahoz egy-az-egyben rendelhet˝ o levezetési fa (parse-tree), melyhez pedig egy-az-egyben (esetleg ”néh´ any-azegyben”) rendelhet˝ o egy line´ aris sorrend, adott (r¨ ogz´ıtett) grammatika mellett. Vagyis a generat´ıv grammatika teszi lehet˝ ové a nem-line´ aris szerkezet k´ odol´ as´ at line´ aris k´ od form´ aj´ aban. Ez a generat´ıv grammatika viszont nem lehet regul´ aris, hiszen a komplex szerkezet t´ avoli o ¨sszetev˝ ok k¨ oz¨ otti kapcsolatot is lehet˝ ové tesz, amelyet véges sok a ´llapottal nem lehet elemezni. A gondolatmenetet folytatva, ennek a k¨ ovetkezménye az, hogy a szintaxist nem lehet regul´ aris grammatik´ aval le´ırni, legal´ abb k¨ ornyezetf¨ uggetlen nyelvtan kell hozz´ a. és az irregularit´ as, azaz a mem´ oria-igény felbukkan´ as´ anak k¨ ovetkezménye a hossz´ ut´ av´ u korrel´ aci´ ok megjelenése a sz¨ ovegben. (A fenti gondolatmenet matematikai megfogalmaz´ asa hi´ anyzik, de remélem, hogy megtehet˝ o.) E ponton kapcsolhat´ o a dolgozatom a statisztikus fizik´ ahoz, hiszen a fizika nyelvén sz´ olva, komplex strukt´ ur´ ak hossz´ ut´ av´ u korrel´ aci´ ot létrehoz´ o mechanizmus´ at vizsg´ alom. A line´ aris k´ od k´ odoltt´ a és megval´ os´ıt´ ov´ a t¨ ortén˝ o transzpon´ al´ asa sor´ an viszont csak r¨ ovidt´ av´ u, lok´ alis (”kényelmi”) v´ altoz´ asokat hajtunk végre nyelvek esetén. A genetika nem tud még v´ alaszt adni arra a kérdésre, hogy miért van sz¨ ukség ezekre a v´ altoztat´ asokra (nem-k´ odol´ o részek kihagy´ asa,...). A programoz´ asi nyelvek esetén nincs is sz¨ ukség ilyen v´ altoztat´ asokra, hiszen − mesterségesen létrehozott nyelvr˝ ol lévén sz´ o − a nyelvet létrehoz´ o személy a ´ltal´ aban nem defini´ alt ilyet. Ezek a lok´ alis v´ altoztat´ asok le´ırhat´ ok regul´ aris nyelvvel. Igaz, hogy a szok´ asos fonol´ ogiai formalizmus l´ atsz´ olag nemcsak, hogy nem regul´ aris, hanem nem is k¨ ornyezetf¨ uggetlen, hanem k¨ ornyezetf¨ ugg˝ o, hiszen egy tipikus klasszikus generat´ıv fonol´ ogiai szab´ aly alakja: 15

A → B \ C D, amely a form´ alis nyelveknél megszokott alakban fel´ırt CAD → CBD, k¨ ornyezetf¨ ugg˝ o szab´ alynak felel meg. Mégis, a fonol´ ogiai szab´ alyokra, ill. azok m˝ uk¨ odésére a ´ltal´ aban olyan megszor´ıt´ asokat szoktak alkalmazni, amelyek regul´ ariss´ a teszik az a ´ltaluk le´ırt nyelvet (Kaplan & Kay [1994]). A k¨ ovetkez˝ o fejezetben bel´ atjuk, hogy a regul´ aris grammatik´ ak ekvivalensek a Markovmodellekkel, vagyis nem eredményezhetnek hossz´ ut´ av´ u korrel´ aci´ okat. Ezek ut´ an érthet˝ ové v´ alik, hogy miért vesz´ıtett¨ uk el a hossz´ ut´ av´ u korrel´ aci´ okat a sz¨ ovegek megpermut´ al´ a- sakor: a permut´ aci´ o t¨ onkreteszi szintaxis a nem regul´ aris nyelvét, és csak a sz´ o szint˝ u, r¨ ovid t´ av´ u fonol´ ogiai korrel´ aci´ ok maradtak meg. Mi t¨ orténik, amikor c-DNS-t kész´ıt¨ unk? Szintén a ”genetikai fonol´ ogia”, azaz a transkripci´ o eredményét vizsg´ aljuk, és az ezen a szinten m˝ uk¨ od˝ o szab´ alyok m´ ar nem hoznak létre hossz´ ut´ av´ u korrel´ aci´ okat. Arra viszont nem tudok v´ alaszt adni, hogy vajon miért sz˝ unnek meg itt a kor´ abban létrej¨ ott hossz´ ut´ av´ u korrel´ aci´ ok, holott azok megmaradnak a permut´ alatlan hangsorban. Val´ osz´ın˝ uleg a v´ alaszt csak a DNS-k´ od jobb megértése, a ”nem-k´ odol´ o” részek szerepének tiszt´ az´ asa adja meg.

5. Sztochasztikus form´ alis nyelvek ´ es Markov-modellek A generat´ıv nyelvészet a ´ltal haszn´ alt form´ alis nyelvek elméletének fentebb ismertetett form´ aja nem teszi lehet˝ ové, hogy a korrel´ aci´ ok statisztikus jelenségének nyelvészeti vonatkoz´ asait megvizsg´ alhassuk, vagy a korrel´ aci´ ok létére nyelvészeti magyar´ azatot tal´ aljunk. Ehhez az sz¨ ukséges, hogy a form´ alis nyelvek elméletét kiegész´ıts¨ uk sztochasztikus eszk¨ oz¨ okkel. El˝ osz¨ or a sztochasztikus k¨ ornyezetf¨ uggetlen grammatik´ ak néven ismert modellt ismertetem, Krenn & Samuelsson [1996] alapj´ an. Majd ennek speci´ alis esetét, a sztochasztikus regul´ aris grammatik´ akat vizsg´ alom meg, és megmutatom kapcsolatukat a Markov-modellekhez.

5.1 Sztochasztikus k¨ ornyezetf¨ uggetlen grammatik´ ak Ha a generat´ıv grammatik´ ak négyesét egy val´ osz´ın˝ uségi f¨ uggvénnyel egész´ıtj¨ uk ki, sztochasztikus grammatik´ akat kapunk. Ilyen m´ odon nem csak azt mondhatjuk meg, hogy egy adott mondat vajon eleme-e a grammatika a ´ltal gener´ alt nyelvnek, hanem azt is, hogy milyen val´ osz´ın˝ uséggel vezethetj¨ uk le az S mondatszimb´ olumb´ ol az adott szekvenci´ at. Ezt a val´ osz´ın˝ uséget u ´gy értem, hogy amennyiben o ¨sszef˝ uzz¨ uk a ”végtelen” sok mondat´ at, azaz képez¨ unk egy ide´ alis sz¨ ovegkorpuszt, akkor az adott mondat milyen gyakoris´ aggal fordul el˝ o a korpuszban. Az ide´ alis korpusz j´ o k¨ ozel´ıtését adhatja természetes nyelvek esetén egy k¨ onyv (pl. egy regény), a ”DNS-nyelv” esetén pedig a DNS-szekvenci´ akat tartalmaz´ o adatb´ azisokat fogom ilyen korpusznak tekinteni. (Természetes, hogy a v´ alasztott korpusz befoly´ asolhatja a val´ osz´ın˝ uségeket. Péld´ aul az ”A Maxwell-egyenletek nem invari´ ansak a Galilei-transzform´ aci´ ora.” mondat val´ osz´ın˝ usége 16

nyilv´ anval´ oan m´ as a Fizikus Tanszékcsoport k¨ onyvt´ ari anyag´ ab´ ol képezett korpuszban, mint a Csepeli Fémm˝ uvek dolgoz´ oi a ´ltal 1996. sor´ an kiejtett mondatok, mint korpusz esetében. De ez nem zavar benn¨ unket, hiszen a nyelvészek gyakran kényszer¨ ulnek le´ır´ asaikat egy sz˝ ukebb k¨ orre, péld´ aul a magyar nyelv esetében a ”budapesti k¨ oznyelvre”, lesz˝ uk´ıteni. A val´ osz´ın˝ uségek egy részének korpusz-v´ alaszt´ ast´ ol val´ o f¨ uggését ezért szociolingvisztikai kérdésnek tekinthetj¨ uk. Ennél nehezebb kérdés az, hogy miként defini´ alhatunk egy k¨ ozel ide´ alis korpuszt. Nyilv´ an ilyen lenne a budapesti k¨ oznyelv esetén a k¨ ovetkez˝ o meghat´ aroz´ as: ”az 1996. december 31-én 18. életév¨ uket bet¨ olt¨ ott, érettségizett, magyar anyanyelv˝ u budapesti lakosok a ´ltal 1997. sor´ an kiejtett mondatok.” Viszont ezen korpusz k´ısérletileg nem vizsg´ alhat´ o. Amennyiben viszont az 1980-as években megjelent sajt´ otermékek korpusz´ at tekintj¨ uk, az anyag ink´ abb az irodalmi, mintsem a k¨ oznyelvi a ´llapotokat fogj´ ak t¨ ukr¨ ozni. Természetesen, ennek a vizsg´ alata is érdekes lehet.) 5. Defin´ıci´ o: Sztochasztikus k¨ ornyezetf¨ uggetlen grammatik´ anak (Stochastic Contextfree Grammar, SCFG) nevezz¨ uk az (VN , VT , S, R, P ) o ¨t¨ ost, ahol: VN a nemtermin´ alisok véges halmaza, VT a termin´ alisok véges halmaza (legyen u ´jb´ ol V := VN ∪ VT ), S ∈ VN a nemtermin´ alisok k¨ oz¨ ul a kit¨ untetett mondatszimb´ olum, R az X → Q alak´ u levezetési szab´ alyok egy véges halmaza, ahol X ∈ V N és Q ∈ V ∗ , P pedig egy R → [0, 1] f¨ uggvény oly m´ odon, hogy ∀X ∈ VN :

X

Q∈V ∗

P (X → Q) = 1.

A P (X → Q) val´ osz´ın˝ uség azt jelenti, hogy ha egy levezetési l´ ancban megjelenik egy X nemtermin´ alis, azt milyen val´ osz´ın˝ uséggel fogjuk Q-ként u ´jra´ırni. Ezek ut´ an, egy levezetési l´ anc, ill. levezetési fa val´ osz´ın˝ uségét u ´gy defini´ alhatjuk, mint az alkalmazott helyettes´ıtési (´ ujra´ır´ o) szab´ alyokhoz rendelt val´ osz´ın˝ uségek szorzat´ at. Valamely mondat val´ osz´ın˝ usége pedig a hozz´ atartoz´ o levezetési f´ ak (parse trees) val´ osz´ın˝ uségeinek az o ¨sszege lesz. A m´ odszer a sz´ am´ıt´ ogépes nyelvészetben hasznos elemz˝ o automat´ ak (parser-ek) fut´ asi idejének optimaliz´ al´ as´ ara. Ha a korpuszt u ´gy tekintj¨ uk, mint nagy sz´ am´ u, egym´ as mellé ´ırt mondatszimb´ olumb´ ol (”poli-S l´ ancb´ ol”) levezetett sztring, u ´gy l´ athat´ o a kapcsolat a korpuszb´ ol sz´ am´ıtott emp´ırikus gyakoris´ ag és a fentebb bevezetett elméleti val´ osz´ın˝ uség k¨ oz¨ ott. Mivel a DNS-szekvenci´ akkal és természetes nyelveken ´ırt sz¨ ovegekkel foglalkoz´ o fizikusok egyik régi érdekl˝ odési ter¨ ulete a Zipf-t¨ orvény: Zipf-t¨ orvény: Ha o ¨sszesz´ amoljuk egy adott sz¨ ovegben a k¨ ul¨ onb¨ oz˝ o szavak el˝ ofordul´ asi gyakoris´ ag´ at, majd a cs¨ okken˝ o gyakoris´ ag szerint sorba rendezz¨ uk o ˝ket, akkor a sorrendben elfoglalt R hely f¨ uggvényében a ´br´ azolva az ω(R) gyakoris´ agot (frekvenci´ at), egy, k¨ ozel´ıt˝ oleg −1 exponenssel jellemezhet˝ o hatv´ anyf¨ uggvényt kapunk. (Zipf, [1935, 1949], Czir´ ok[1995, 1996], Kanter & Kessler [1994]) én az egyes termin´ alisok el˝ ofordul´ asi val´ osz´ın˝ uségére voltam k´ıv´ ancsi egy korpuszban, azaz mondatok l´ anc´ aban. Ezért végeztem el a k¨ ovetkez˝ o sz´ amol´ ast: v S (a)-val jel¨ ol¨ om azt, hogy 17

az a ∈ VT termin´ alis v´ arhat´ oan h´ anyszor fordul el˝ o egy S-b˝ ol levezethet˝ o mondatban 1 : X σ vS (a) := , pS (σ) a ∗ σ∈VT

ahol pS (σ) jel¨ oli a σ ∈ VT∗ mondat fentebb bevezetett val´ osz´ın˝ uségét, σa pedig az a termin´ alisok sz´ am´ at a σ mondatban. (Megjegyzem, hogy hab´ ar form´ alisan nem l´ atom be, de ezen végtelen szumm´ anak konvergensnek kell lennie. Hiszen fel¨ ulr˝ ol becs¨ ulhet˝ o a mondatok hossz´ anak v´ arhat´ o értékével, amely viszont véges, hiszen enélk¨ ul a kommunik´ aci´ o nem lenne elképzelhet˝ o.) A benn¨ unket érdekl˝ o vS (a) v´ arhat´ o értéknél t¨ obbet fogunk kisz´ am´ıtani a SCFG paramétereib˝ ol, azaz a P val´ osz´ın˝ uségf¨ uggvényb˝ ol. Jel¨ olje pA (σ) b´ armely A ∈ VN nemtermin´ alisra annak a val´ osz´ın˝ uségét, hogy A-b´ ol a σ ∈ VT∗ sztringet vezetj¨ uk le: az A gy¨ oker˝ u, σ-t eredményez˝ o 2 levezetési f´ ak val´ osz´ın˝ uségeinek footnote Az ilyen f´ ak val´ osz´ın˝ uségét szintén az alkalmazott levezetési szab´ alyok val´ osz´ın˝ uségeinek a szorzataként sz´ am´ıthatjuk ki, ak´ arcsak az S gy¨ oker˝ u f´ ak esetén. az o ¨sszegét. és jel¨ olje vA (a) annak a v´ arhat´ o értékét, hogy az A-b´ ol sztringekben h´ anyszor szerepel az a termin´ alis: X σ vA (a) := . (5.1) pA (σ) a ∗ σ∈VT

Ezek a vA (a)-k egy v(a) vektornak a komponensei, amely egy, a VN elemeinek a sz´ am´ aval megegyez˝ o dimenzi´ oj´ u térben van. A pa (σ) a ´t´ır´ as´ ahoz be kell vezetni a Chomsky-féle norm´ alalak fogalm´ at. Bel´ athat´ o (pl. ld. Révész [1979], SCFG-re Krenn & Samuelsson [1996]), hogy b´ armely k¨ ornyezetf¨ uggetlen grammatik´ ahoz létezik olyan Chomsky-féle norm´ alalakban megadott grammatika (Chomsky Normal Form, CNF), amely ugyanazt a nyelvet gener´ alja, és amelynek a szab´ alyai A → BC vagy A→a alak´ uak, ahol A, B, C ∈ VN és a ∈ VT . Tetsz˝ oleges SCFG-hez is adhat´ o meg olyan SCFG, amelynek R-je CNF-alak´ u levezetési szab´ alyokat tartalmaz, és amely minden sztringet ugyanolyan val´ osz´ın˝ uséggel gener´ al, mint az eredeti SCFG. Defini´ aljuk még a π(a) vektort és a µ m´ atrixot:

µAB

πA (a) := P (A → a) i X h := P (A → BC) + P (A → CB) C∈VN

1

Az al´ abbiakban a kisbet˝ uk mindig termin´ alisra, a nagybet˝ uk nemtermin´ alisra, m´ıg a g¨ or¨ og bet˝ uk termin´ alisokb´ ol a ´ll´ o sztringre fognak utalni. 18

Amikor az A-b´ ol akarom levezetni a σ-t egy CNF alak´ u grammatik´ aban, két lehet˝ oségem van az elindul´ asra: amennyiben a σ egyetlen a termin´ alisb´ ol a ´ll, u ´gy az A → a szab´ alyt kell alkalmaznom, egyébként pedig az A-t egy A → BC szab´ allyal ´ırom u ´jra, és B-b˝ ol levezetem σ1 -et, C-b˝ ol σ2 -t, ahol σ = σ1 σ2 alak´ u (e kett˝ o konkaten´ aci´ oja). Ennek megfelel˝ oen:

pA (σ) =

X

b∈VT

P (A → a)δσ,b +

X

X

B,C∈VN σ1 ,σ2 ∈VT∗ σ=σ1 σ2

P (A → BC)pB (σ1 )pC (σ2 )

(5.2)

(A δσ,b szimb´ olum a megszokott Kronecker-delt´ at jel¨ oli.) Ha be´ırjuk a (5.2) egyenletet (5.1)-be, u ´gy bizonyos egyszer˝ us´ıtésekre lesz lehet˝ oség¨ unk, a k¨ ovetkez˝ o h´ arom o ¨sszef¨ uggés felhaszn´ al´ as´ aval: b = δb,a a X pC (σ) = 1

σ∈VT∗

σ σ1 σ2 = + a a a Az eredmény a k¨ ovetkez˝ o lesz: vA (a) = πA (a) +

X

B,C∈VN

P (A → BC)(vB (a) + vC (a)),

amelyb˝ ol: vA (a) = πA (a) +

X

vB (a)µAB ,

B∈VN

vagyis: v(a) = π(a) + µv(a).

(5.3)

A (5.3) o ¨sszef¨ uggés a ´trendezésével a SCFG paramétereib˝ ol ki tudjuk sz´ am´ıtani a Zipft¨ orvényben szerepl˝ o frekvenci´ akat. Ehhez az sz¨ ukséges, hogy az 1 − µ m´ atrix invert´ alhat´ o legyen, de ezzel azért nincs baj, mert a µ elemeire nincsen semmiféle megk¨ otés (π(a) kis megv´ altoztat´ as´ ara µ is megv´ altozik), vagyis kis perturb´ aci´ oval megsz¨ untethet˝ o egy esetleges szingularit´ as.

5.2 Sztochasztikus regul´ aris nyelvtanok ´ es a Markov-modell Az el˝ oz˝ o részben bevezetett SCFG speci´ alis esete az, ha nem csup´ an a k¨ ornyezetf¨ uggetlenséget, hanem a regularit´ ast is kik¨ otj¨ uk. Jelen fejezetben az 5. defin´ıci´ o szerinti P val´ osz´ın˝ uséggel kib˝ ov´ıtett sztochasztikus regul´ aris nyelvtanokra (SRG) fogom bel´ atni, hogy helyettes´ıthet˝ ok 19

Markov-modellekkel. (A Markov-folyamat fogalm´ at nem defini´ alom, mivel a fizikusok ”m˝ uveltségébe” beletartozik. J´ o és t¨ om¨ or le´ır´ asa megtal´ alhat´ o Krenn & Samuelsson [1996]ban.) El˝ olj´ ar´ oban megjegyzem, hogy egy regul´ aris korpusz, pontosabban sz´ olva: egy regul´ aris nyelv mondataib´ ol o ¨sszef˝ uz¨ ott sz¨ oveg maga is tekinthet˝ o egyetlen regul´ aris mondatnak. 2 Elegend˝ o, ha az eredeti generat´ıv grammatika minden A → a alak´ u, mondatgener´ al´ ast lez´ ar´ o szab´ alya mellé felvesz¨ unk egy A → aS szab´ alyt is, mely az el˝ oz˝ o mondatot lez´ arja, és egy u ´jat kezd el, a sz¨ oveg k¨ ovetkez˝ o mondat´ at. Teh´ at, ha egy mondat-l´ anc regularit´ as´ at vizsg´ aljuk, nyugodtan tekinthetj¨ uk az egészet egyetlen mondatnak. (Olyan ez, mintha pontok helyére pontosvessz˝ oket tennénk.) El˝ osz¨ or, érts¨ uk meg, miben k¨ ul¨ onb¨ ozik egy Markov-modell egy SRG-t´ ol, illetve az azzal ekvivalens véges a ´llapot´ u automat´ at´ ol, amennyiben az ut´ obbit szintén felruh´ azzuk a ´tmeneti val´ osz´ın˝ uségekkel. Mindkett˝ o egy véges a ´llapothalmazb´ ol vett a ´llapotok sorozat´ an halad kereszt¨ ul, két a ´llapot k¨ oz¨ otti a ´tmenet sor´ an kibocs´ at egy-egy jelet, és az a ´tmenetek, ill. a jelkibocs´ at´ as bizonyos val´ osz´ın˝ uséggel k¨ ovetkezik be. Viszont, m´ıg a Markov-modell esetén f¨ uggetlen a jelkibocs´ at´ as az a ´tmenett˝ ol, addig a SRG esetében a kett˝ o egy¨ utt k¨ ovetkezik be: P (A → aB) annak a val´ osz´ın˝ usége, hogy az automata az A a ´llapotb´ ol a B a ´llapotba megy a ´t, mik¨ ozben az a jelet bocs´ atja ki. M´ as szavakkal: az SRG ”élcimkézett” (arc-labeled), m´ıg a Markov-modell ”´ allapotcimkézett” (state-labeled), vagyis a SRG-n´ al (azaz a véges a ´llapot´ u automat´ an´ al, finite state automaton, FSA) a kibocs´ atott jel (a ”cimke”) az a ´llapotok k¨ oz¨ otti élhez kapcsol´ odik, m´ıg a Markov-modelleknél mag´ ahoz az a ´llapotokhoz. Viszont tudjuk, hogy a ”state-labeled” és az ”arc-labeled” automat´ ak ekvivalensek (ld. pl. Bird & Ellison [1994]). Ennek felel meg a k¨ ovetkez˝ oa ´ll´ıt´ as a sztochasztikus automat´ akra (nyelvekre, modellekre) 3 : ´ ıt´ All´ as: Minden sztochasztikus regul´ aris nyelv megval´ os´ıthat´ o Markov-modellel. A bizony´ıt´ as sor´ an megkonstru´ aljuk a megfelel˝ o Markov-modellt. A Markov-modell a ´llapotai k¨ oz¨ ott egyrészt megtal´ aljuk a SRG nemtermin´ alisainak (a véges a ´llapot´ u automata a ´llapotainak) megfelel˝ oa ´llapotokat, m´ asrészt a SRG minden helyettes´ıtési szab´ aly´ anak is megfelel egy a ´llapot. El˝ obbieket nevezz¨ uk primer, ut´ obbiakat pedig szekunder a ´llapotnak. A Markov-modell kimen˝ oa ´bécéje természetes m´ odon megegyezik az SRG termin´ alisaival (a le´ırand´ o nyelv a ´bécéjével), illetve tartalmaz még egy λ elemet is, melynek jel¨ olésére nem véletlen¨ ul v´ alasztottam a lambd´ at, hiszen sokan ezt haszn´ alj´ ak az u ¨res sz´ o jel¨ olésére (amire mi az e-t v´ alasztottuk): a λ szerepe az lesz, hogy ignor´ aljuk o ˝t. Meg kell még adnunk a Markov-modell a ´tmeneti val´ osz´ın˝ uségeit és a jel-kibocs´ at´ asi val´ osz´ın˝ uségeit. Primer a ´llapotb´ ol csak szekunder a ´llapotba, szekunder a ´llapotb´ ol csak primerbe mehet¨ unk a ´t nem-zérus val´ osz´ın˝ uséggel. Az A nemtermin´ alisnak megfelel˝ oa ´llapotb´ ol a B → aC a ´llapotba val´ oa ´tmenet val´ osz´ın˝ usége δA,B P (B → aC). A B → aC a ´llapotb´ ol az Aa ´llapotba pedig: δC,A . Primer a ´llapotban 1 val´ osz´ın˝ uséggel bocs´ atja ki a Markov-modell a λ jelet (m´ as olvasat szerint: nem bocs´ at ki jelet), m´ıg minden m´ ast zérus val´ osz´ın˝ uséggel. Amikor a Markov-modell a ´ltal gener´ alt jelsorozatot vizsg´ aljuk, egyszer˝ uen figyelmen k´ıv¨ ul Azaz, ha L regul´ aris nyelv, akkor L∗ is regul´ aris, ld. Révész [1979], 2.2 tétel. 3 A Markov-modell lényegében egy visszafele m˝ uk¨ od˝ o, sztochasztikus eszk¨ oz¨ okkel kib˝ ov´ıtett state-labeled automaton. 2

20

hagyjuk a p´ aratlan helyeken megjelen˝ o λ-kat. Az igazi jelet a szekunder a ´llapotokban bocs´ atja ki, a B → aC szab´ alynak megfelel˝ o a ´llapotban egyed¨ ul az a jelet bocs´ atja ki nem-zérus val´ osz´ın˝ uséggel (1 val´ osz´ın˝ uséggel). K¨ onnyen l´ athat´ o, hogy az ´ıgy v´ azolt Markov-modell ekvivalens az eredeti SRG-val, ha eltekint¨ unk a λ-k gener´ al´ as´ at´ ol, valamint a SRG-t a ´talak´ıtjuk a fejezet elején eml´ıtett m´ odon mondatsorozat (sz¨ oveg) gener´ al´ as´ ara, és ”végtelen´ıtj¨ uk” a m˝ uk¨ odését. (Nem haszn´ aljuk az A → a alak´ u szab´ alyokat; ill. a haszn´ alatuk a Markov-modellt egy vég´ allapotba viszi, ahol meg´ all a m˝ uk¨ odése.) A Markov-modell két lépésben teszi meg ugyan azt, és ugyan olyan val´ osz´ın˝ uséggel, mint amit a SRG egy gener´ al´ asi lépés alatt, illetve az SRG-vel ekvivalens véges a ´llapot´ u automata egy lépés alatt. Ezek ut´ an o ¨sszefoglalhatjuk eddigi eredményeinket: a form´ alis nyelvek elmélete alkalmas egy sor jelenségk¨ or le´ır´ as´ ara (természetes nyelvek, programoz´ asi nyelvek, val´ osz´ın˝ uleg a DNS és a fehérjék szerkezetének le´ır´ as´ ara is). A form´ alis nyelvek elméletét kib˝ ov´ıtve sztochasztikus m´ odszerekkel, azt kaptuk, hogy a regul´ aris grammatik´ ak ekvivalensek a Markov-modellekkel. Mivel a Markov-l´ ancok, és ´ıgy a Markov-modellek sem, képesek hossz´ ut´ av´ u korrel´ aci´ ok produk´ al´ as´ ara, bizony´ıtottnak vehetj¨ uk, hogy azok a jelenségek, amelyeknél hossz´ ut´ av´ u korrel´ aci´ okat észleltek (intront tartalmaz´ o DNS-ek, természetes nyelvi sz¨ ovegek a sz´ o szintje f¨ ol¨ ott,...) nem elemzhet˝ oek regul´ aris grammatik´ akkal. Ez a szintaxis esetén nem u ´jdons´ ag, hiszen m´ ar Chomsky [1957] is emellett érvel. A genetik´ aban b´ armely elméletnek, mely az intronok szerepére vonatkozik, o ¨sszhangban kell lennie ezzel az elmélettel (Mantegna et al. [1995a]). Azok a szintek, amelyek nem mutattak hossz´ ut´ av´ u korrel´ aci´ okat (fonol´ ogia, c-DNS-ek,...) viszont esetleg le´ırhat´ ok regul´ aris eszk¨ oz¨ okkel, mint ahogy a fonol´ ogia esetében t¨ orténtek is erre m´ ar k´ısérletek. A k¨ ovetkez˝ o két fejezetben bemutatand´ o ”vektortér-technika” − M. Damashek [1995], az alap¨ otlet kidolgoz´ oja nevezte −, a szimb´ olumsorozatok regul´ aris viselkedését veszi k¨ ozelebbr˝ ol szem¨ ugyre.

6. n-grammok ´ es fonotaktika Az elm´ ult években egyre t¨ obb algoritmus sz¨ uletik sz¨ ovegek automatikus szelekt´ al´ as´ ara: péld´ aul egy h´ır¨ ugyn¨ okség sz´ am´ ara nagyon hasznos lenne, ha a befut´ o h´ıreket emberi beavatkoz´ as nélk¨ ul lehetne nyelv és témak¨ or szerint csoportos´ıtani. Damashek [1995] éppen egy ilyen algoritmusra tesz javaslatot, melyet o ˝ Acquaintancenek nevez. Ennek az algoritmusnak a lényege az, hogy a sz¨ ovegekb˝ ol vektort kész´ıt, majd a vektorok skal´ aris szorzata jellemz˝ o a vektorok, azaz a sz¨ ovegek hasonl´ os´ ag´ ara. Képzelj¨ uk el, hogy egy n hossz´ us´ ag´ u ablakot (n = 3..6) mozgatunk végig a sz¨ ovegen, karakterr˝ ol karakterre. A k¨ ul¨ onb¨ oz˝ o lehetséges karakter-n-eseket indexelj¨ uk i = 1..J -vel. Jel¨ olj¨ uk mi -vel az i-ik karakter-n-es el˝ ofordul´ asainak a sz´ am´ at. A sz¨ ovegb˝ ol képezett x vektor i-ik komponensét éppen az mi lenorm´ al´ as´ ab´ ol kapott frekvenciaként képezz¨ uk: mi xi := PJ

j=1 mj

21

(6.1)

Damashek praktikus tan´ acsot is ad ezen vektor gyors és mem´ oriatakarékos kisz´ am´ıt´ as´ ara: elégséges csup´ an a zérust´ ol k¨ ul¨ onb¨ oz˝ o vektorkomponenseket t´ arolni; a vektort pedig u ´gy a ´ll´ıthatjuk el˝ o, hogy a karakterszekvenci´ ab´ ol képezz¨ uk az n-esek szekvenci´ aj´ at, majd egy hatékony rendezési algoritmussal rendezz¨ uk ezt a szekvenci´ at, és ezt k¨ ovet˝ oen elég o ¨sszesz´ amolni, mely n-esb˝ ol mennyi van a sz¨ ovegben. A két sz¨ ovegb˝ ol ilyen m´ odon képezhet˝ o vektorok, x és y, skal´ aris szorzata jellemzi a sz¨ ovegek hasonl´ os´ ag´ at: PJ

xj y j 1/2 = cos θ PJ 2 2 j=1 yj j=1 xj

S= PJ

j=1

(6.2)

K¨ onnyen bel´ athat´ o, hogy a d(x, y) := 1 − S t´ avols´ ag egy metrik´ at defini´ al a vektorok terében, azaz j´ o t´ avols´ agfogalom a sz¨ ovegek k¨ oz¨ ott. (Att´ ol a val´ osz´ın˝ utlen esett˝ ol eltekintve, amikor két k¨ ul¨ onb¨ oz˝ o sz¨ oveg ugyanarra a vektorra képezhet˝ o le.) Ez a szorzat els˝ osorban a sz¨ ovegek nyelv szerinti szétv´ alaszt´ as´ ara alkalmas, de szerencsés esetben az azonos nyelv˝ u sz¨ ovegek téma szerinti szétv´ alaszt´ asa is lehetséges szerencsés esetben. Saj´ at magam péld´ aul o ¨t, fizikai tém´ aja angol e-mailb˝ ol (Ph1-Ph5), h´ arom szintén angol nyelv˝ u, de m´ as tém´ aj´ u e-mailb˝ ol (E1-E3), két francia levélb˝ ol (Fr1-Fr2) és h´ arom magyar nyelv˝ u, mag´ anjelleg˝ u e-mailb˝ ol (H1-H3) a ´ll´ o korpuszt vizsg´ altam. Azt egyes sz¨ ovegek hossza 3400 és 6000 karakter k¨ oz¨ ott van, kivéve a két francia levelet, amelynek hossza csup´ an 1000 - 1200 karakter. Az angol a ´bécé 26 bet˝ ujét, a pontot, a vessz˝ ot, valamint az u ¨res helyet vettem figyelembe. A t¨ obbi karaktert ignor´ altam, kis- és nagybet˝ u k¨ oz¨ ott, ill. ékezetes és ékezet nélk¨ uli bet˝ u k¨ oz¨ ott pedig nem tettem k¨ ul¨ onbséget. A t¨ obb u ¨res helyb˝ ol a ´ll´ o szekvenci´ akat el˝ oz˝ oleg t¨ or¨ olni kell. Eredményeimet n = 3-ra és n = 4-re az 6.1, ill. a 6.2 t´ abl´ azat tartalmazza. (Damashek a m´ odszert tov´ abbfejleszti. Bevezet u ń. centroid vektorokt, amely egy sz¨ ovegcsokor (péld´ aul az angol nyelv˝ u sz¨ ovegek, vagy az angol nyelv˝ u, sz´ am´ıt´ astechnikai tém´ aj´ u sz¨ ovegek) vektorainak az a ´tlaga. Ezt a vektort levonva a sz¨ ovegek vektoraib´ ol, kitranszform´ alhat´ oak a sz¨ ovegcsokor k¨ oz¨ os jellemz˝ oi, péld´ aul az adott nyelv funkcion´ alisgrammatikai szavaib´ ol ad´ od´ o jellegzetességek (a magyar esetén pl. az ” a ” h´ armas vagy az ” az ” négyes). Ilyen m´ odon, a sz¨ ovegek finomabb csoportos´ıt´ asa is lehetséges. Damashek javasol praktikus o ¨tleteket a statisztikus hib´ ak kiker¨ ulésére is.) A két t´ abl´ azat adatai k¨ oz¨ ott szignifik´ ansan magasabbak az azonos nyelv˝ u sz¨ ovegek vektoraib´ ol képezett vektorok szorzatai, mint a k¨ ul¨ onb¨ oz˝ o nyelv˝ uek szorzatai. A két, k¨ ul¨ onb¨ oz˝ o tém´ aj´ u angol sz¨ ovegcsokor is elk¨ ul¨ on¨ ul egym´ ast´ ol: a Ph-sz¨ ovegek (pl. n = 3-ra a Ph-sz¨ ovegek egym´ as k¨ oz¨ otti szorzata: 0, 79 ± 0, 024) ill. az E-sz¨ ovegek szorzata (0, 80 ± 0, 015) magasabb, mint egy E- és egy Ph-sz¨ oveg szorzata(0, 68 ± 0, 03). Ezt k¨ ovet˝ oen, o ¨sszef˝ uztem mind a négy sz¨ ovegt´ıpusb´ ol néh´ any sz¨ oveget, egyetlen 1 f˝ uzérré. Egy m = 100 hossz´ us´ ag´ u dobozt mozgattam végig ezen a f˝ uzéren, és a doboz 1

A file szerkezete: 0-6775. karakter: Ph-t´ıpus; 6776-13551. karakter: E-t´ıpus; 1355223219. karakter: Ph-t´ıpus; 23220-25862. karakter: H-t´ıpus; 25863-32319. karakter: Pht´ıpus; 32320-35178. karakter: Fr-t´ıpus. 22

éppen aktu´ alis tartalm´ ab´ ol képezett vektort (n = 3) o ¨sszeszoroztam a f˝ uzér elejéb˝ ol (06775. karakterek k¨ oz¨ otti Ph-sz¨ ovegekb˝ ol) képezett vektorral. Az eredmények az 6.1. a ´br´ an l´ athat´ oak: a f˝ uzér angol és nem angol nyelv˝ u részei élesen k¨ ul¨ onv´ alnak. Az eredmény magyar´ azata ott keresend˝ o, hogy k¨ ul¨ onb¨ oz˝ o nyelvekre k¨ ul¨ onb¨ oz˝ o karakterszekvenci´ ak jellemz˝ oek. Péld´ aul az angol nyelv˝ u sz¨ ovegekben, az n = 3 esetben kiugrik a ”the” karakterh´ armas: gondoljunk a hat´ arozott nével˝ on k´ıv¨ ul a névm´ asokra (”they”, ”their”, ”them”, ”these”, ”there”, stb.). Véleményem szerint, ez a jelenség részben ortogr´ afiai okora megy vissza (pl. az ”sz” p´ ar csak azért jellemz˝ o a magyar sz¨ ovegekre, mert a magyar helyes´ır´ as ´ıgy jel¨ oli a fonetikai [s] hangot). M´ asrészt, igazi nyelvészeti okokat is tal´ alhatunk, hiszen az ´ırott sz¨ oveg részben t¨ ukr¨ ozi a kiejtett sz¨ oveg fonol´ ogiai jellemz˝ oit. A Damashek-féle vektorok jellegzetességei részben a nyelv fonotaktik´ aj´ ara mennek vissza. A fonotaktika a fonol´ ogia azon a ´ga, amely a foném´ ak lehetséges kapcsolatait vizsg´ alja a célnyelvben (Kiefer, [1994], 4. fejezet). Péld´ aul az ∗ b´ ard´ as sz´ o nem létezik a magyar nyelvben, de nem érezz¨ uk idegennek, ”ak´ ar létezhetne is”, hiszen megfelel a magyar nyelv fonotaktikai szab´ alyainak. Szemben az el˝ odordul´ o, de nem j´ olform´ alt g¨ orl (pl. show-girlo ¨k) sz´ oval. A fonotaktika jellegzetesen ”regul´ aris” vizsg´ al´ od´ asi ter¨ ulet. A fonotaktikai megszor´ıt´ asok fel´ırhat´ ok regul´ aris grammatik´ ak form´ aj´ aban, melyek megengedik a j´ olform´ alt alakokat, és kiz´ arj´ ak a nem j´ olform´ altakat. 23

A fonotaktikai elemzések sor´ an gyakran alkalmaznak a nyelvészek kisebb ”csal´ asokat”. El˝ ofordul´ o alakokat néha nem-j´ olform´ altnak tekintenek: ritk´ an el˝ ofordul´ o, idegen hangz´ as´ u szavak (pl. nganasz´ an [szamojéd nyelv neve], scs´ı, f´ ajl) esetén még ki lehet magyar´ azni azzal, hogy felejts¨ uk el o ˝ket. De a barack, recept, teremt szavak esetén m´ ar nincs ilyen egyszer˝ u dolgunk. A ”csal´ asok” m´ asik része az, amikor nemlétez˝ o hangkapcsolatokat j´ olform´ altnak tekint¨ unk az elemzés egyszer˝ us´ıtése miatt, és csup´ an ”véletlen hi´ anynak” tekintj¨ uk azt, hogy péld´ aul y a magyarban nincsen [t a]-val kezd˝ od˝ o sz´ o. Ezen hi´ anyokat ”érzés” alapj´ an tekintj¨ uk helyesnek, de mit jelent az, hogy ”véletlen hi´ any”? Ezért javaslom a fonotaktika sztochasztikus megk¨ ozel´ıtését: egész´ıts¨ uk ki a fonotaktika regul´ aris grammatik´ aj´ at sztochasztikus eszk¨ oz¨ okkel, azaz térj¨ unk a ´t Markov-modellre. Ilyen megk¨ ozel´ıtésben, j´ olform´ alt az az alak, amelynek nagy val´ osz´ın˝ uséget j´ osol a modell, a nem-j´ olform´ alt alakokhoz pedig elhanyagolhat´ o (zérus) val´ osz´ın˝ uséget rendel¨ unk. A ”csal´ asok” magyar´ azhat´ oak az elméleti val´ osz´ın˝ uség k¨ or¨ uli statisztikus sz´ or´ assal. Az agrammatikus, el˝ ofordul´ o alak olyan szekvenci´ anak felel meg, amely az elmélet a ´ltal j´ osolt val´ osz´ın˝ uségnél nagyobb gyakoris´ aggal fordul el˝ o, m´ıg a véletlen hi´ anyok a sz´ am´ıtottn´ al alacsonyabb gyakoris´ agot jelent. A fonotaktika sztochasztikus megk¨ ozel´ıtése j´ olform´ alts´ agi fokozatok megk¨ ul¨ onb¨ oztetését teszi lehet˝ ové. Péld´ aul a [ck#] sz´ ovéget kevésbé érezz¨ uk nem-j´ olform´ altnak, mint a [#ng] sz´ okezdetet. Az el˝ obbi t¨ obb, és gyakoribb szavakban fordul el˝ o (barack, palack, tarack,...), 24

mint az ut´ obbi (nganasz´ an). A sztochasztikus modellek ezen fokozatok le´ır´ as´ at lehet˝ ové teszik. Egy megjegyzés a gyakoris´ agok meghat´ aroz´ as´ ar´ ol. A nyelvészek a ´ltal´ aban ”lexiconbased” statisztik´ akat haszn´ alnak, mivel o ˝ket csak az érdekli, vajon egy alak el˝ ofordul-e vagy sem (ld. pl. a Kiefer [1994] 4. fejezetében haszn´ alt 80 000 tételb˝ ol a ´ll´ o adatb´ azist). Ezzel szemben, a Damashek-féle m´ odszer u ń. ”corpus-based” elj´ ar´ as, hiszen a sz¨ ovegben gyakrabban el˝ ofordul´ o szavak, hangkapcsolatok nagyobb s´ ullyal szerepelnek. Ennek el˝ onye az, hogy k¨ ul¨ onbséget tud tenni péld´ aul a [#ng] sz´ okezdet és a [mt#] sz´ ovég k¨ oz¨ ott: hab´ ar mindkett˝ ot agrammatikusnak tartj´ ak az elemzések, mivel mindkett˝ o csup´ an egyetlen mag25

yar sz´ oban fordul el˝ o (nganasz´ an, ill. teremt), de az ut´ obbi sokkal gyakrabban fordul el˝ oa korpuszokban, és az anyanyelvi beszél˝ o és érzi a két alak k¨ oz¨ otti j´ olform´ alts´ agi fokozatot. Tegy¨ uk fel, hogy a nyelv¨ unk fonotaktik´ aj´ at le tudjuk ´ırni egy olyan Markov-modellel, amely N a ´llapotot (s1 , s2 , ..., sN ) és M darab jelet (σ1 , σ2 , ..., σM ) tartalmaz. Az i-ikb˝ ol a jik a ´llapotba t¨ ortén˝ oa ´tmenet val´ osz´ın˝ uségét jel¨ olj¨ uk p ij -vel, m´ıg ai j annak a val´ osz´ın˝ usége, hogy az i-ik a ´llapotban a modell a j-ik jelet bocs´ atja ki. Tegy¨ uk fel, hogy ergodikus a Markov-modell¨ unk; és mivel hossz´ u l´ ancokr´ ol, regul´ aris nyelv hossz´ u modatair´ ol van sz´ o ∗ (ne felejts¨ uk el, hogy a regul´ aris nyelvek oszt´ alya z´ art a m˝ uveletre, ld. 5.2 fejezet elején), feltehetj¨ uk azt is, hogy a modell m´ ar ”egyens´ ulyiv´ a v´ alt”, azaz annak a v i val´ osz´ın˝ usége, hogy a szekvencia valamely poz´ıci´ oj´ aban a rendszer az i-ik a ´llapotban lesz, f¨ uggetlen a poz´ıci´ ot´ ol. Ekkor a σk1 σk2 ...σkn szimb´ olum n-es elméletileg j´ osolt val´ osz´ın˝ usége: P (σk1 σk2 ...σkn ) =

N X

v i 1 a i 1 k1

N X

pi1 i2 ai2 k2 ...

i2 =1

i1 =1

N X

pin−1 in ain kn

i1 =1

Mivel a pij és aij paramétereket nem ismerj¨ uk, a j¨ ov˝ obeni kutat´ asok érdekes feladata lehet valamely adott korpusz esetén ezen ”rejtett Markov-modell” (hidden Markov Model, Krenn & Samuelsson [1996]) paramétereinek a becslése. A becsléshez rendelkezésre a ´llnak a P (σk1 σk2 ...σkn )-k emp´ırikus k¨ ozel´ıtései, valamint felhaszn´ alhatjuk a jelek emp´ırikus gyakoris´ agait. Az i-ik jel νi frekvenci´ aj´ ara adhat´ o elméleti becslés: νi =

N X

vj aji ,

j=1

hiszen vj val´ osz´ın˝ uséggel van a rendszer az sj a ´llapotban, és ekkor aji val´ osz´ın˝ uséggel bocs´ atja ki a σi jelet. Izgalmas kérdés, vajon mennyire sz¨ oveg-, téma- és nyelvspecifikusak a rejtett paraméterek, milyen mérték˝ u eltérések engedélyezettek, milyen mérték˝ u eltérések sz¨ ukségesek a Damashekm´ odszer sikeréhez. Befejezés¨ ul, még arr´ ol a kérdésr˝ ol, hogy miért nem egyszer˝ us´ıtettem le a gondolatmenetemet Markov-l´ ancokra. Val´ osz´ın˝ uleg egyszer˝ ubbek lennének a sz´ am´ıt´ asok, ha Markov-l´ ancot, és nem Markov-modellt tekint¨ unk. Két okb´ ol ragaszkodtam a Markovmodellhez. Egyrészt, a regul´ aris grammatik´ akat Markov-modellekre, és nem Markovl´ ancokra vezett¨ uk vissza. A m´ asodik ok nyelvészeti: a fonotaktikai szab´ alyok sok esetben felhaszn´ alnak metrikus fonol´ ogiai inform´ aci´ okat is (sz´ otagszerkezet, sz´ oszerkezet, stb.). Ezt u ´gy val´ os´ıthatjuk meg, ha a metrikus szerkezet elemeit (pl. sz´ otagkezdet, mag, sz´ otagz´ arlat) az a ´llapotokkal reprezent´ aljuk, m´ıg a szegmentumoknak (foném´ aknak) felelnek meg a Markov-modell jelei. De ennek a kérdésnek a b˝ ovebb kidolgoz´ asa m´ ar egy nyelvészeti, és nem egy fizikai dolgozat t´ argya lehetne.

7. K´ odol´ o´ es nem-k´ odol´ o DNS-szakaszok 26

Marc Damashek cikke adta az o ¨tletet, hogy a cikkben kidolgozott m´ odszert DNS-szekvenci´ akra 1 is alkalmazzam. A DNS-szekvenci´ ak statisztikai m´ odszerekkel t¨ ortén˝ o kutat´ as´ anak jelenleg legizgalmasabb kérdése a k´ odol´ o és a nem-k´ odol´ o szakaszok eltér˝ o viselkedése, ennek a magyar´ azat´ anak a megtal´ al´ asa, valamint olyan algoritmus kész´ıtése, amely automatikusan és nagy pontoss´ aggal v´ alasztja szét a két t´ıpus´ u szekvenci´ akat. 2 Mantegna et al. [1994, 1995a], Czir´ ok et al. [1995, 1996] b´ azisp´ arokb´ ol képezett n-esekre végeztek Zipf-anal´ızist (n-tupple Zipf analysis)(n = 3...8), és azt kapt´ ak, hogy az el˝ ofordul´ asi frekvencia a gyakoris´ agi sorrendben elfoglalt hely f¨ uggvényében a k´ odol´ o szakaszok esetén exponenci´ alisként, m´ıg a nem-k´ odol´ o szakaszok esetén hatv´ anyf¨ uggvényként cseng le (v. o ¨. az 5.1 fejezetben eml´ıtett Zipf-t¨ orvénnyel). Jogosan mer¨ ul fel a kérdés, vajon megk¨ ul¨ onb¨ oztethet˝ ok-e a k´ odol´ o és a nem-k´ odol´ o szakaszok a Damashek-féle szorzat seg´ıtségével. A 7.1 t´ abl´ azat a HUMHBB szekvencia (hum´ an hemoglobin) o ¨t, a ´t´ır´ asra ker¨ ul˝ o szakasz´ ab´ ol (”primary transcript”) kész´ıtett vektorokat tartalmaz. Egy ilyen szakasz a ´ll egy ”bevezet˝ o” részb˝ ol, h´ arom exonb´ ol (k´ odol´ o szekvencia), a k¨ ozt¨ uk lév˝ o két intronb´ ol, valamint egy ”z´ ar´ o” részb˝ ol. Az E-vel jel¨ olt vektorokat az exonok konkaten´ aci´ oib´ ol képeztem, m´ıg az I-vel jel¨ olteket a fennmarad´ o (nem k´ odol´ o) részekb˝ ol. (A t´ abl´ azatban felt¨ untetett adatok esetében, a vektorok képzésénél n = 3 hossz´ us´ ag´ u ablakot haszn´ altam, de m´ as n-re is hasonl´ o jelenségek figyelhet˝ oek meg.) 1

DNS-szekvenci´ ak Markov-l´ ancokkal t¨ ortén˝ o elemzésére az 1980-as években is tettek m´ ar k´ısérletet, ld. Weir [1990] (pp. 237. skk.), ahol tov´ abbi irodalom is tal´ alhat´ o. 2 Ld. pl. Herzel & Große [1997], Große et al. [1997] 27

A t´ abl´ azatban l´ atv´ anyosan elk¨ ul¨ on¨ ulnek a k´ odol´ o és a nem-k´ odol´ o szekvenci´ ak. Az exonok egym´ as k¨ oz¨ otti szorzatai a ´tlagosan 0, 94 ± 0, 016 értéket eredményeznek. A magas a ´tlag és a kis sz´ or´ as ann´ al ink´ abb meglep˝ o, mert nagyon r¨ ovid szekvenci´ akr´ ol van sz´ o. (Gondoljunk a 6.1 és 6.2 t´ abl´ azatokra, ahol a t¨ obbi sz¨ ovegnél j´ oval r¨ ovidebb francia sz¨ ovegek szorz´ asa rosszabb eredményt adott, mint a hosszabb sz¨ ovegeké.) A nem-k´ odol´ o szakaszok szintén magas a ´tlagot eredményeznek: 0, 92 ± 0, 03. Ezzel szemben, k´ odol´ o és nem-k´ odol´ o szakaszb´ ol kész´ıtett vektor szorzata szignifik´ ansan alacsonyabb, és nagy sz´ or´ ast mutat: 0, 75 ± 0, 08. Hasonl´ o eredményeket figyelhet¨ unk meg m´ as n-ekre, valamint a RATCRYG-szekvenci´ ara (norvég patk´ any) is. Ezt k¨ ovet˝ oen, az egyes szekvenci´ akb´ ol képeztem egy ”na´ıv-vektort” is, amelynek i-ik komponensét az i-ik b´ azisp´ ar-n-es egyes b´ azisp´ arjai el˝ ofordul´ asi frekvenci´ aja szorzataként sz´ am´ıtottam ki (”korrel´ aci´ omentes vektor”). Azaz, ha az i-ik n-gramm (b´ azis-n-es) alakja σk1 σk2 ...σkn , és νj jel¨ oli a σj b´ azisp´ ar megfigyelt el˝ ofordul´ asi frekvenci´ aj´ at, akkor az x (naiv) vektor i-ik komponense:

(naiv)

xi

:= P (naiv) (σk1 σk2 ...σkn ) :=

n Y

ν kj .

j=1

A 7.2 t´ abl´ azatban j´ ol l´ atsz´ odik, hogy a vizsg´ alt eml˝ os szekvenci´ ak esetében (a szekvenci´ akat ugyan u ´gy kész´ıtettem el, mint a 7.1 t´ abl´ azat esetében) a k´ odol´ o szakaszok j´ oval t´ avolabb esnek a korrel´ alatlan vektort´ ol, mint a nem-k´ odol´ ok: a szorzat értéke az el˝ obbi esetben 0, 66 ± 0, 05, m´ıg az ut´ obbiban 0, 83 ± 0, 03. Ez az eredmény nem mond ellent annak, hogy hossz´ ut´ av´ u korrel´ aci´ ok az intront tartalmaz´ o szekvenci´ akban fordulnak el˝ o, m´ıg a tiszt´ an k´ odol´ o szakaszokban nem. Ugyanis, mint azt a 4. fejezetben kifejtettem, elképzelésem szerint az intront is tartalmaz´ o szekvenci´ akat nem-regul´ aris folyamatok hozz´ ak létre, és ´ıgy sz¨ uletnek a hossz´ ut´ av´ u korrel´ aci´ ok, m´ıg az exonok most felfedezett r¨ ovidt´ av´ u korrel´ aci´ oit Markov-folyamattal is magyar´ azhatjuk. A 7.2 t´ abl´ azat eredményein felbuzdulva, a 6. fejezetben ismertett ”mozg´ o doboz”-os m´ odszert alkalmaztam a DNAS-szekvenci´ akra is. A HUMHBB a ´t´ır´ asra ker¨ ul˝ o részei (az exonok k¨ ornyékei) nagyon jellegzetes strukt´ ur´ at mutatnak (7.1 a ´bra). A h´ arom exon k¨ oz¨ ul, az els˝ o kett˝ o nagyon k¨ ozel van egym´ ashoz, ´ıgy van olyan helyzet, hogy a doboz belel´ og mindkett˝ obe. Ennek ellenére felfedezhet˝ o az a jellegzetes v¨ olgy, amely u ´gy keletkezik, hogy minél jobban ny´ ulik bele a doboz az exonba, ann´ al alacsonyabb lesz a naiv-vektorral t¨ ortén˝ o szorz´ as eredménye. A primary transcript els˝ o két exonja k¨ or¨ uli v¨ olgy teh´ at a ´tlapol, viszont a harmadik exon v¨ olgye szépen kivehet˝ o. Meglep˝ o felfedezés ugyanakkor a harmadik exont megel˝ oz˝ o v¨ olgy felt˝ unése, mind az o ¨t a ´t´ır´ asra ker¨ ul˝ o szakasz esetén ugyan ott. Ezen ”´ alexon” létére még nem tal´ altam magyar´ azatot. Vég¨ ul, a 7.2 a ´br´ an az éleszt˝ o III. kromosz´ om´ aj´ anak (SCCHRIII) egy részlete l´ athat´ o. Ugyan ezt a részletet mutatja be Stanley et al. [1993b] 3. a ´br´ aja (a DNA-walk α-exponense egy m = 800bp széles mozg´ o dobozban) Mindkét a ´br´ aban lok´ alis minimumok jelzik az exonok helyét, ennek ellenére a két a ´bra kevés hasonl´ os´ agot mutat. 28

8. Befejez´ es DNS-szekvenci´ ak és természetes nyelvi sz¨ ovegek esetén egyar´ ant felfedeztek az 1990-es évek elején hossz´ ut´ av´ u korrel´ aci´ okat. Ezt k¨ ovet˝ oen, az 1990-es évek k¨ ozepén kider¨ ult, hogy a DNS nemk´ odol´ o szakaszai és az ´ırott sz¨ ovegek tov´ abbi k¨ oz¨ os tulajdons´ agokkal rendelkeznek: péld´ aul a karakter n-esekre kész´ıtett Zipf-féle frekvencia−gyakoris´ ag f¨ uggvény a nem-k´ odol´ o DNS-szekvenci´ akra, ak´ ar csak a szintaxisra (szavak eloszl´ as´ ara egy sz¨ ovegben) hatv´ anyf¨ uggvényt k¨ ovet, szemben a k´ odol´ o DNS-szakaszokkal és a bet˝ uk eloszl´ as´ aval valamely sz¨ ovegben (a fonol´ ogia leképez˝ odése a helyes´ır´ asra), amelyek esetén a Zipf-f¨ uggvény exponenci´ alisan cseng le (Mantegna et al. [1994, 1995a]). Ugyan ezek a vizsg´ alatok emp´ırikusan hozt´ ak ki azt az eredményt, amit én a korrel´ aci´ ok meglétéb˝ ol k¨ ovetkeztettem ki: a nemk´ odol´ o DNS-szekvenci´ akat nem lehet helyesen modellezni Markov-folyamatokkal (ellentétben az 1980-as évek pr´ ob´ alkoz´ asaival, Weir [1990]). Magasabb rend˝ u Markov-l´ ancok jav´ıthatnak a le´ır´ as pontoss´ ag´ an, de végleges megold´ ast szintén nem adhatnak (Mantegna et al. [1995a]). Tal´ an azért n˝ o a pontoss´ ag a rend n¨ ovelésével, mert az adekv´ altabb le´ır´ ast ad´ o sztochasztikus k¨ ornyezetf¨ uggetlen grammatik´ akat k¨ ozel´ıtik meg? Dolgozatomban ezen jelenségek m¨ ogé k´ıv´ antam tekinteni. A két szimb´ olumsorozat egyar´ ant o ¨sszetett strukt´ ur´ akat k´ odol line´ aris form´ aban, ezért a hossz´ ut´ av´ u korrel´ aci´ ok − véleményem szerint − a k´ odoland´ o nemlinearit´ as´ anak a megnyilv´ anul´ asai. A m´ asodlagos folyamatok (fonol´ ogia, fehérje szintézis) viszont regul´ aris szab´ alyokat alkalmaznak. Nem vil´ agos egyel˝ ore, hogy miért t˝ unnek el a korrel´ aci´ ok a fehérje-szintézis sor´ an a k´ odol´ o sza29

kaszokban, holott a beszédprodukci´ oban megtal´ alhat´ oak egyar´ ant a szintaxis hossz´ ut´ av´ u, és a fonol´ ogia r¨ ovidt´ av´ u korrel´ aci´ oi. Megjegyzem, hogy a Zipf-f¨ uggvény viselkedése ugyanezt a kett˝ osséget k¨ oveti: a regul´ aris (korrel´ aci´ omentes) szinten exponenci´ alisként cseng le, m´ıg a korrel´ aci´ okat produk´ al´ o szinten hatv´ anyf¨ uggvénnyel k¨ ozel´ıthet˝ o. Dolgozatom végén a Damashek-féle vektortér/technika alkalmaz´ as´ at mutattam be − mint a regul´ aris folyamatok a ´ltal létrehozott r¨ ovidt´ av´ u korreal´ aci´ okon alapul´ o m´ odszert − sz¨ ovegeken, és − u ´jdons´ agként − és DNS-en. DNS-ek esetében, a k´ odol´ o és a nemk´ odol´ o szakaszok szorzatai szignifik´ ansan eltérnek egym´ ast´ ol, ´ıgy egy u ´jabb jelenséggel b˝ ov¨ ult a k´ odol´ o és nem-k´ odol´ o szakaszok statisztikai tulajdons´ agait magyar´ azni k´ıv´ an´ o kutat´ ok feladata. A felfedezés egyel˝ ore nem alkalmas még a kétféle szekvencia automatikus 30

elv´ alaszt´ as´ ara, mivel tal´ altam olyan szakaszokat is, amelyek exonként viselkednek, hab´ ar nem azok. A természetes nyelvi sz¨ ovegek kapcs´ an a m´ odszer sikerességét helyes´ır´ asi és fonotaktikai okokkal (nyelvek szerinti szort´ıroz´ as), illetve a sz¨ oveg tartalm´ ara jellemz˝ o szavak gyakoris´ ag´ aval (téma szerinti szétv´ alogat´ as) magyar´ aztam. Ennek al´ at´ amaszt´ as´ ara, javaslatot tettem a fonotaktika Markov-modellekkel t¨ ortén˝ o megk¨ ozel´ıtésére.

K¨ osz¨ onetnyilv´ an´ıt´ as K¨ osz¨ onetemet fejezem ki Vicsek Tam´ as egyetemi tan´ arnak, aki felh´ıvta a figyelmemet a statisztikus fizika nyelvészeti és genetikai vonatkoz´ as´ u fejezeteire, és minden téren t´ amogatta a munk´ amat. H´ al´ as vagyok Czir´ ok Andr´ asnak, az ELTE TTK Atomfizikai Tanszék doktorandusz´ anak, aki cikkekkel és praktikus tan´ acsokkal seg´ıtett, valamint Rebrus Péternek, az MTA Nyelvtudom´ anyi Intézet PhD-¨ oszt¨ ond´ıjas´ anak, aki a nyelvészeti vonatkoz´ asokban volt a seg´ıtségemre.

31

Irodalomjegyz´ ek L. A. N. Amaral, S. V. Buldyrev, S. Havlin, M. A. Salinger, H. E. Stanley [1997]: Power law scaling in a system of interacting units with complex internal structure (preprint). M. Amit, Y. Shmerler, E. Eisenberg, M. Abraham, N. Shnerb [1994]: Language and Codification Dependence of Long-Range Correlations in Texts, Fractals, 2, 1, pp. 7-13. S. Bird, T. M. Ellison [1994]: One-level Phonology: Autosegmental Representations and Rules as Finite Automata, Computational Linguistics, 20, 1, pp. 55-90. J-Ph. Bouchaud, M. Potters [1997]: Théorie des Risques Financiers. Portefeuilles, options et risques majeurs, Collection Aléa Saclay. N. Chomsky [1957]: Syntactic Structres, The Hague: Mouton. Magyarul megjelent: Mondattani szerkezetek, Osiris-Sz´ azadvég, Budapest, 1995. A. Czir´ ok, R. N. Mantegna, S. Havlin, H. E. Stanley [1995]: Correlations in binary sequences and a generalized Zipf analysis, Physical Review E, 52, 1 , pp. 446-452. A. Czir´ ok, H. E. Stanley, T. Vicsek [1996]: Possible origin of power-law behavior in n-tuple Zipf analysis, Physical Review E 53, 6371. M. Damashek [1995]: Gauging Similarity with n-Grams: Language-Independent Categorization of Text, Science, 267, pp. 843-848. I. Derényi, T. Vicsek [1996]: The kinesin walk: A dynamic model with elastically coupled heads, Proc. Natl. Acad. Sci. USA, 93, pp. 6775-6779. G. Dietler, Y.-C. Zhang [1994]: Crossover from White Noise to Long Range Correlated Noise in DNA Sequences and Writings, Fractals, 2, 4, pp. 473-479. W. Ebeling, A. Neiman [1995]: Long-range correlations between letters and sentences in texts, Physica A 215, pp. 233-241. F. Family, T. Vicsek [1991] (szerk.): Dynamics of Fractal Surfaces, World Scientific. ´ Kisdi, G. Meszéna [1997]: Dynamics of Adaptation S. A. H. Geritz, J. A. J. Metz, E. and Evolutionary Branching, Physical Review Letters, 78, 10, pp. 2024-2027. S. Ghashghaie, W. Breymann, J. Peinke, P. Talkner, Y. Dodge [1996]: Turbulent cascades in foreign exchange markets, Nature, 381, 27 June 1996, pp. 767-770. I. Große, H. Herzel, S. V. Buldyrev, H. E. Stanley [1997]: Mutual information of coding and noncoding DNA (preprint). 32

H. Herzel, I. Große [1997]: Correlations in DNA sequences: The role of protein coding segments, Physical Review E, 55, 1, pp. 800-810. I. Kanter, D. A. Kessler [1994]: Markov Process: Linguistics, Zipf’s Law and LongRange Correlations. (Submitted to PRL, Oct. 20, 1994). R. M. Kaplan, M. Kay [1994]: Regular Models of Phonological Rule Systems, Computational Linguistics, 20, 3, pp. 331-378. Kenesei I. [1995] (szerk.): A Nyelv és nyelvek, Akadémiai Kiad´ o, Budapest. Kiefer F. [1994] (szerk.): Struktur´ alis magyar nyelvtan, 2. k¨ otet: Fonol´ ogia, Akadémiai Kiad´ o, Budapest. B. Krenn, Ch. Samuelsson [1996]: The Linguist’s Guide to Statistics, forr´ as: http://coli.uni-sb.de/ christer. Y. Liu, P. Cizeau, M. Meyer, C.-K. Peng, H. E. Stanley [1997]: Correlations in Economic Time Series (preprint submitted to Elsevier Science). K. Martin´ as, M. Moreau [1995] (szerk.): Complex Systems in Natural and Economic Sciences, Proceedings of the Workshop Methods of Non-Equilibrium Processes... R. N. Mantegna, S. V. Buldyrev, A. L. Goldberger, S. Havlin, C.-K. Peng, M. Simons, H. E. Stanley [1994]: Linguistic Features of Noncoding Sequences, Physical Review Letters, 73, 23, pp. 3169-3172. R. N. Mantegna, S. V. Buldyrev, A. L. Goldberger, S. Havlin, C.-K. Peng, M. Simons, H. E. Stanley [1995a]: Systematic analysis of coding and noncoding DNA sequences using methods of statistical linguistics, Phys. Rev. E, 52, 3, pp. 2939-2950. R. N. Mantegna, H. E. Stanley [1995b]: Scaling behaviour in the dynamics of an economic index, Nature, 376, 6 July 1995, pp. 46-49. R. N. Mantegna, H. E. Stanley [1996]: Turbulence and financial markets, Nature, 383, 17. October 1996, pp. 587-588. R. N. Mantegna, H. E. Stanley: Stock market dynamics and turbulence, Parallel analysis of fluctuation phenomena, Physica A, 3357 (1997.). Nagy Ferenc [1986]: Kvantitat´ıv Nyelvészet, Tank¨ onyvkiad´ o, Budapest. C.-K. Peng, S. V. Buldyrev, A. L. Goldberger, S. Havlin, F. Sciortino, M. Simons, H. E. Stanley [1992]: Long-range correlations in nucleotide sequences, Nature, 356, pp. 168-170. C.-K. Peng, S. V. Buldyrev, A. L. Goldberger, S. Havlin, M. Simons, H. E. Stanley [1993]: Finite-size effects on long-range correlations: Implications for analyzing DNA sequences, Physical Review E, 47, 5, pp. 3730-3733. M. Potters, R. Cont, J-Ph. Bouchaud [1997]: Financial markets as adaptive systems (preprint). Révész Gy. [1979]: Bevezetés a form´ alis nyelvek elméletébe, Akadémiai Kiad´ o, Budapest. A. Schenkel, J. Zhang, Y.-C. Zhang [1993]: Long Range Correlation in Human Writings, Fractals, 1, 1, pp. 47-57. 33

M. H. R. Stanley, L. A. N. Amaral, S. V. Buldyrev, S. Havlin, H. Leschhorn, Ph. Maass, M. A. Salinger, H. E. Stanley [1996a]: Scaling behaviour in the growth of companies, Nature, 379, 29 Febr. 1996, pp. 804-806. M. H. R. Stanley, L. A. N. Amaral, S. V. Buldyrev, S. Havlin, H. Leschhorn, Ph. Maass, M. A. Salinger, H. E. Stanley [1996b]: Can Statistical Physics Contribute to the Science of Economics?, Fractals, 4, 3 (1996), pp. 415-425. H. E. Stanley, S. V. Buldyrev, A. L. Goldberger, J. M. Hausdorff, S. Havlin, J. Mietus, C.-K. Peng, F. Sciortino, M. Simons [1992]:Fractal landscapes in biological systems: Longrange correlations in DNA and interbeat heart intervals, Physica A, 191, 1-12. H. E. Stanley, S. V. Buldyrev, A. L. Goldberger, S. Havlin, C.-K. Peng, M. Simons [1993a]: Long-range power-law correlations in condensed matter physics and biophysics, Physica A 200, 4-24. H. E. Stanley, S. V. Buldyrev, A. L. Goldberger, S. Havlin, S. M. Ossadnik, C.-K. Peng, M. Simons [1993b]: Fractal Landscapes in Biological Systems, Fractals, 1, 3, pp. 283-301. T. Vicsek [1992]: Fractal Growth Phenomena (second edition), World Scientific. B. S. Weir [1990]: Genetic Data Analysis, Methods for Discrete Population Genetic Data, Sinauer Associates, Inc. Publishers, Sunderland, Mass. G. K. Zipf [1935]: The Psychobiology of Language, Houghton Mifflin, Boston. G. K. Zipf [1949]: Human Behavior and the Principle of Least Effort, Addison-Wesley Press.

34

SZIMBÓLUMSOROZATOK ELEMZÉSE STATISZTIKAI MÓDSZEREKKEL Tudományos diákköri dolgozat, 1997

Recommend Documents