Úvod Štyri simulácie Evolučná indukcia gramatiky Evolučné modelovanie ontogenézy rečových kategóriı́ 4 simulácie Daniel Devatman Hromada12 daniel@udk-berlin.de 1 Slovak University of Technology Faculty of Electronic Engeneering and Informatics Department of Robotics and Cybernetics 2 Université Paris 8 École Doctoralle Cognition, Langage, Interaction Laboratoire Cognition Humaine et Artificielle 3.6.2016 Úvod Štyri simulácie Table of Contents 1 Úvod Cotutelle Conceptual Foundations Teória Intramentálnej Evolúcie 2 Štyri simulácie 3 Evolučná indukcia gramatiky Evolučná indukcia gramatiky Úvod Štyri simulácie Cotutelle PhD. pod dvojitým vedenı́m Evolučná indukcia gramatiky Úvod Štyri simulácie Evolučná indukcia gramatiky Conceptual Foundations Konceptuálne Základy Takmer 300-stranový elaborát usilujúci sa o syntézu troch vedeckých paradigiem: 1 univerzálny darwinizmus (36 strán) 2 vývojová psycholingvistika (50 strán) 3 komputačná lingvistika (63 strán) Obsahuje taktiež 38 stranový súhrn kvalitatı́vnych pozorovanı́ jedného ľudského toddlera (0-30 mesiacov) a 27 strán kvantitatı́vnych analýz vyextrahovaných z korpusu Child Language Data Exchange System (CHILDES). Úvod Štyri simulácie Evolučná indukcia gramatiky Conceptual Foundations Základné Tézy 1 ”Myseľ sa vyvı́ja” (mind evolves) 2 ”Učenie je formou evolúcie” 3 ”Učenie možno úspešne simulovať pomocou evolučných výpočtov” 4 ”Učenie prirodzených jazykov možno úspešne simulovať pomocou E.V.” 5 ”Ontogenézu detskej reči možno úspešne simulovať pomocou E.V.” Úvod Štyri simulácie Evolučná indukcia gramatiky Teória Intramentálnej Evolúcie Teória Intramentálnej Evolúcie Základný postulát Vývoj individuálnej mysle možno interpretovať - resp. dokonca simulovať - ako proces replikácie, variácie a selekcie v mysli obsiahnutých a informáciu nesúcich kognitı́vnych štruktúr. O niečo podobné usilovala už aj Piagetova genetická epistemológia, T.I.E. však hovorı́ aj o simulácii či dokonca emulácii... Simulácie mojej dizertácie sú snahou o poskytnutie určitého dôkazu ex computatione platnosti tejto teórie. Úvod Štyri simulácie Table of Contents 1 Úvod 2 Štyri simulácie Nultá simulácia Simulácie 1-3 Simulácia 1: Učenie sémantického klasifikátora Simulácia 2: Učenie tvaroslovného triediča Učenie slovných druhov Indukcia Gramatiky 3 Evolučná indukcia gramatiky Evolučná indukcia gramatiky Úvod Štyri simulácie Evolučná indukcia gramatiky Nultá simulácia Voyničov rukopis Enigma 240 strán textu napı́saných v neznámom pı́sme (a možno aj v neznámom jazyku) sprevádzaných ilustráciami s motı́vami botaniky, zdravovedy, astrológie atď. Nultá simulácia 1 môj prvý vlastný evolučný algoritmus 2 genóm každého jedinca má dĺžku 19 znakov a udáva možný prepis jedného symbolu v rukopise na jednu z možných foném výsledného jazyka (napr. slovanské jazyky 38 znakov) 3 sústreďuje sa na prepis jednej časti rukopisu, tzv. ”kalendár” na zoznamy krstných mien 4 prepisy sú najúspešnejšie keď slovnı́ky obsahujú ženské mená pı́sané zprava doľava 5 hebrejské a slovanské zdrobnelé ženské mená... Úvod Štyri simulácie Evolučná indukcia gramatiky Simulácie 1-3 Spoločné črty simuláciı́ 1-3 Všetky tri simulácie 1 sa usilujú o riešenie problémov strojového učenia 2 použı́vajú texty pı́sané v hovorovej angličtine ako vstupné dáta 3 charakterizujú slová v týchto textoch pomocou ich určitých čŕt: tieto črty sú následne využité v premietnutı́ textu do vektorových priestorov 4 principiálne operujú v relatı́vne nı́zkorozmerných binárnych (Hammingových) priestoroch 5 uskutočňujú evolučné vyhladávanie optimálnych riešenı́ 6 v najvnútornejšom cykle vyhodnocovania účelovej funkcie vždy dochádza k meraniu Hammingových vzdialenostı́ Úvod Štyri simulácie Evolučná indukcia gramatiky Simulácia 1: Učenie sémantického klasifikátora Viactriedna sémantická klasifikácia textov Elitech 2015, aplikovaná informatika (ocenenie) Korpus: 20 newsgroups (18845 textov z 20tich usenetových kategóriı́) 11314 textov: trénovacie dáta; 7543 textov: testovacie dáta frekvencie výskytov jednotlivých slov v jednotlivých textoch udávajú črty pomocou ktorých text geometrizujeme Základná idea Vo vektorovom priestore vyhľadávame také body ktoré sú čo najbližšie k vek.rep. objektov určitej kategórie a čo najďalej od vek.rep. objektov iných kategóriı́. Úvod Evolučná indukcia gramatiky Štyri simulácie Simulácia 1: Učenie sémantického klasifikátora Teória Prototypov Items rated more prototypical of the category were more closely related to other members of the category and less closely related to members of other categories than were items rated less prototypical of a category (Rosch a Mervis, 1975) Fitness funkcia: FCP (PK ) = X t∈CK Fhd (ht , PK ) − X Fhd (hf , PK ) (1) f 6⊂CK (PK kandidát na prototyp K -tej triedy; ht vektorová reprezentácia objektu tiež náležiaceho do K ; hf vektorová reprezentácia objektu ktorý do K nepatrı́; Fhd Hammingová vzdialenosť) Úvod Štyri simulácie Evolučná indukcia gramatiky Simulácia 1: Učenie sémantického klasifikátora Problém lineárnej oddeliteľnosti... ...možno nieje pre klasifikačné modely založené na Teórii Prototypov až takým pálčivým problémom ! Úvod Štyri simulácie Evolučná indukcia gramatiky Učenie slovných druhov Učenie slovných druhov Problémy ako part-of-speech (POS) induction a POS tagging sú jedny z najlepšie rozpracovaných problémov výpočtovej lingvistiky. O užitočnosti slovných druhov 1 Ak človek dokáže rozpoznať že neznáme slovo WX patrı́ do kategórie K , dokáže mu ľahšie priradiť význam. 2 Bez slovných druhov nieto gramatı́k. Druhá simulácia: 1 sekcia Brown / Eve korpusu CHILDES 2 prepisy POS tagy manuálne opravené ľudskými anotátormi 3 trénovacı́ korpus (972 slovných typov) : Eve pred dosiahnutı́m dvoch rokov veku; testovacı́ korpus (934 slovných typov): Eve vo veku 2 - 2. 12 roka 4 449 slovných typov sa vyskytuje iba v testovacom korpuse Úvod Štyri simulácie Evolučná indukcia gramatiky Učenie slovných druhov Metóda Iba tri jednoduché črty sú použité na priemet slovo X do vektorového priestoru: prı́pona slova X , prı́pona slova napravo od X a prı́pona slova naľavo od X . Operačný princı́p A Pay attention to the ends of words. (Slobin, 1973) Po geometrizácii všetkých tokenov následne vyhľadávame prototypy jednotlivých tvaroslovných tried pomocou účelovej funkcie Fobject (~i, o~ ) = |PF | px 6=pT ∧ Hd(~ o ,p~x )<=Hd(~ o ,p~T ) =⇒ px ,→PF t.j. penalizujeme za každý nesprávny prototyp pX ktorý je k objektu o~ bližšie ako správny (pT ). To čo vyhľadávame sú optimálne konštelácie prototypov. (2) Úvod Učenie slovných druhov Zopár výsledkov Štyri simulácie Evolučná indukcia gramatiky Úvod Štyri simulácie Evolučná indukcia gramatiky Učenie slovných druhov Výsledky čo prekvapili... A subsequent inspection of false positives turns out to be quite instructive. Hence, the token ”building”, present in the utterance ”what are you building here?” on line 5417 of eve05.cha transcript is clearly not a noun, as CHILDES annotators and correctors supposed, but rather a participle - and hence an instance belonging to ACTION class, as correctly predicted by FITTEST (GAMERGE 1 ). Idem for ”hit” present in the utterance ”did you hit your head?” present on line 4145 of eve01.cha transcript: the token is clearly not a noun, as postulated by CHILDES annotators, but, as predicted, a verb and hence member of ACTION class. And one can continue: the token ”matter” annotated on lines 2152 and 5688 of CHILDES corpus as a verb is clearly not a verb but a noun - and hence a member of a class SUBSTANCE - because it twice occurs in the utterance ”what’s the matter?. And in spite of the fact that CHILDES labels the token ”numbers” as a verb, it is definitely not a verb when it occurs in the utterance ”the numbers are going around too” (eve15.cha, line 6276). Et caetera et caetera. Úvod Štyri simulácie Evolučná indukcia gramatiky Indukcia Gramatiky Indukcia | Inferencia Gramatiky Definı́cia problému Máme množinu M viet jazyka J. Cieľom IG je vydestilovať z M poznatky (resp. model, pravidlá, schémy, vzory atď.) ktoré nám následne umožnia vygenerovať aj také vety jazyka J ktoré neboli v M. Kameň úrazu Prı́lišné zovšeobecnenie (over-generalisation resp. over-regularisation): napr. keď dvojročné dieťa začne hovoriť goed namiesto went. Cieľom IG je nájsť také systémy pravidiel ktoré niesú ani prı́liš špecifické: (1 →< corpus >), ale ani prı́liš všeobecné: 1 → 2∗ 2 → a|b|c. . . Z Úvod Evolučná indukcia gramatiky Štyri simulácie Evolučná indukcia gramatiky Klenbový svornı́k Problém prı́lišného zovšeobecnenia možno vyriešiť tak, že nastavı́me evolučný proces spôsobom ktorý bude penalizovať prı́liš všeobecné riešenia. Schopnosť evolúcie zbaviť sa toho čo je nepotrebné sa postará o zvyšok. YX ∗ YX EX kde YX je počet viet korpusu matchnutých fenotypickým prejavom N−schémy X a EX je teoreticky maximálna možná daná extenzia Fitness1 (NX ) = EX = N Y IHk k=1 zı́skaná ako multiplikatı́vny produkt extenziı́ kategóriı́ ktoré su v NX kódované. Úvod Evolučná indukcia gramatiky Štyri simulácie Evolučná indukcia gramatiky Od teórie k praxi Theoria ∆−rozmerné vektorové priestory, G-kategórie, Hammingové sféry, H-kategórie, Syntagmatické a paradigmatické kategórie, N-schémy... Praxis Prepis vektorov ktoré popisujú konštelácie oblastı́ v hammingových priestorov na staré dobré PERLovské regulárne výrazy. Syntagma H1 Center BABC Radius 17 H2 Center 0F20 R 5 H3 Center 5FF0 R 7 ˆ(this |that|it )(is )(not )(a |the )(dog |duck)$ H4 Center C124 R 3 H Cente 7723 Úvod Štyri simulácie Evolučná indukcia gramatiky Prvé výsledky c.f. Appendix 1 Evolučná indukcia gramatiky Úvod Štyri simulácie Evolučná indukcia gramatiky Diskusia Pár otázok Možno pomocou evolučných algoritmov realizovať strojové učenie ? ÁNO: V prı́pade že ústrednou črtou strojového učenia je schopnosť zovšeobecniť poznatky obsiahnuté v trénovacı́ch dátach. Môžu byť evolučné algoritmy užitočné na riešenie problémov výpočtovej lingvistiky ? ÁNO: Ale len za predpokladu vhodne zvolenej účelovej funkcie a reprezentácie jednotlivých riešenı́. Odporučenie: kombinácia subsymbolických (napr. geometrických) a symbolických úrovnı́ reprezentácie sa ukazuje ako užitočná. Výhody evolučného prı́stupu v porovnanı́ s konekcionistickými riešeniami? Konekcionisti modelujú štrukturálne vlastnosti kognitı́vnych systémov. Ale možnosť definovať fitness funkciu umožňuje Úvod Štyri simulácie Diskusia Ďakujem za pozornosť. Evolučná indukcia gramatiky