Univerzita Karlova v Praze Matematicko-fyzikální fakulta

Univerzita Karlova v Praze Matematicko-fyzikáln´ı fakulta

´ RSK ˇ ´ PRACE ´ BAKALA A

Jan Vyˇsohl´ıd Prostˇ red´ı pro testov´ an´ı algoritm˚ u pro uˇ cen´ı automat˚ u Kabinet software a v´ yuky informatiky

Vedouc´ı bakaláˇrské práce: RNDr. Petr Hoffmann Studijn´ı program: Informatika, programován´ı

2008

Dˇekuji pˇredevˇs´ım svému vedouc´ımu RNDr. Petru Hoffmannovi za ochotu a trpˇelivost, s jakou mi odpov´ıdal na mé dotazy, za pˇripom´ınky, rady a námˇety vedouc´ı ke zlepˇsen´ı kvality práce, za ˇcas stráven´ y konzultacemi se mnou a celkovou pomoc pˇri psan´ı této práce. Dále dˇekuji vˇsem citovan´ ym autor˚ um za jejich d´ıla, z nichˇz jsem mohl ˇcerpat. Bez vˇsech tˇechto lid´ı by práce nedostala svou nynˇejˇs´ı podobu.

Prohlaˇsuji, ˇze jsem svou bakaláˇrskou práci napsal samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. Souhlas´ım se zap˚ ujˇcován´ım práce a jej´ım zveˇrejˇ nován´ım.

V Praze dne 28.7.2008

Jan Vyˇsohl´ıd

2

Obsah ´ 1 Uvod 1.1 Charakteristika práce . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Struˇcn´ y popis kapitol . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 7

2 Z´ akladn´ı teorie 2.1 Koneˇcné automaty . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Regulárn´ı inference . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 10

3 Testov´ an´ı algoritm˚ u 3.1 Testovac´ı metody . . . . . 3.2 Abbadingo formáty . . . . 3.3 Trénovac´ı a testovac´ı data 3.4 Pr˚ ubˇeh testován´ı . . . . .

12 12 14 15 16

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

4 Z´ avˇ er 18 4.1 Zhodnocen´ı práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Moˇzná vylepˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A Uˇ zivatelsk´ a dokumentace 20 A.1 Popis práce s aplikac´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 A.2 Pˇr´ıklad testován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 B Program´ atorsk´ a dokumentace

26

Literatura

29

3

Název práce: Prostˇred´ı pro testován´ı algoritm˚ u pro uˇcen´ı automat˚ u Autor: Jan Vyˇsohl´ıd Katedra (´ ustav): Kabinet software a v´ yuky informatiky Vedouc´ı bakaláˇrské práce: RNDr. Petr Hoffmann E-mail vedouc´ıho: [email protected] Abstrakt: V pˇredloˇzené práci studujeme metody pro testován´ı algoritm˚ u regulárn´ı inference. Nejprve jsou uvedeny nˇekteré teoretické poznatky z oblasti koneˇcn´ ych automat˚ u a regulárn´ı inference. Dále jsou pˇredstaveny nˇekteré algoritmy pro uˇcen´ı koneˇcn´ ych automat˚ u, jejich principy a pouˇzité testovac´ı metody, jeˇz zjiˇst’uj´ı kvalitu algoritm˚ u testován´ım v´ ysledn´ ych automat˚ u. V dalˇs´ım textu je pak vysvˇetlen zp˚ usob generován´ı trénovac´ıch a testovac´ıch dat, popsán formát pro uloˇzen´ı tˇechto dat a pro uloˇzen´ı koneˇcn´ ych automat˚ u a nakonec také samotn´ y pr˚ ubˇeh testován´ı algoritm˚ u. Souˇcást´ı práce je rovnˇeˇz aplikace, která uvedené testovac´ı metody implementuje a v´ ysledné statistiky ukládá ve zvoleném formátu. V dodatc´ıch pˇrikládáme uˇzivatelskou a programátorskou dokumentaci k této aplikaci. Kl´ıˇcová slova: koneˇcn´ y automat, regulárn´ı inference, uˇc´ıc´ı algoritmus, testovac´ı metoda, aplikace

Title: An application for testing automata learning algorithms Author: Jan Vyˇsohl´ıd Department: Department of Software and Computer Science Education Supervisor: RNDr. Petr Hoffmann Supervisor’s e-mail address: [email protected] Abstract: In the present work we study methods for testing regular inference algorithms. First there are introduced some theoretical basics for finite state automata and regular inference. Next we present some finite state automata learning algorithms, their principles and used testing methods, which find out algorithms quality via testing resulting automata. Following text makes the training and testing data generating process clear, describes format for saving this data and for saving finite state automata and finally the algorithms testing run alone, too. The application implementing present testing methods is a part of this work as well. It saves result statistics in chosen format. In appendices we append user and programmer documentation for this application. Keywords: finite state automaton, regular inference, learning algorithm, testing method, application

4

Kapitola 1 ´ Uvod 1.1

Charakteristika pr´ ace

C´ılem práce je studovat a navrhnout metody pro testován´ı algoritm˚ u pro uˇcen´ı koneˇcn´ ych automat˚ u a navrˇzené postupy implementovat. Problém uˇcen´ı koneˇcn´ ych automat˚ u nen´ı jednoduch´ y a existuj´ı pro nˇej r˚ uzné zp˚ usoby zadán´ı i postupy ˇreˇsen´ı. Tato práce se bude zab´ yvat uˇcen´ım z trénovac´ıch dat. Algoritmy pro uˇcen´ı koneˇcn´ ych automat˚ u z trénovac´ıch dat se také naz´ yvaj´ı algoritmy regulárn´ı inference. Problém regulárn´ı inference je velmi zaj´ımav´ y a uˇziteˇcn´ y. Má nemal´ y teoretick´ y v´ yznam, ale také ˇsiroké spektrum aplikac´ı jako je napˇr. identifikace sekvenˇcn´ıch proces˚ u, rozpoznáván´ı vzor˚ u, zpracován´ı ˇreˇci a pˇrirozeného jazyka, exploratorn´ı sekvenˇcn´ı anal´ yza, umˇelá inteligence nebo data mining. Máme dána nˇejaká data z jazyka, kter´ y neznáme. Z nich chceme z´ıskat automat, kter´ y pozitivn´ı pˇr´ıklady pˇrij´ımá a negativn´ı pˇr´ıklady zam´ıtá. Jin´ ymi slovy hledáme automat konzistentn´ı s tˇemito daty. ˇ sen´ı tohoto problému ale nen´ı jednoznaˇcné, jak je vidˇet na následuj´ıc´ım pˇr´ıkladu. Reˇ Pˇr´ıklad dvou automat˚ u konzistentn´ıch se stejn´ ymi trénovac´ımi daty, které m˚ uˇzeme oba povaˇzovat za ˇreˇsen´ı problému regulárn´ı inference, rozpoznávaj´ıc´ıch r˚ uzné jazyky: Trénovac´ı data: pozitivn´ı pˇr´ıklady: {10, 101010} negativn´ı pˇr´ıklady: {100}

Automat 1:

5

Automat 2:

V ideáln´ım pˇr´ıpadˇe by v´ ysledn´ y automat mˇel rozpoznávat jazyk, z nˇehoˇz byla trénovac´ı data nagenerována. Automat m˚ uˇze ale pˇrij´ımat napˇr. nadmnoˇzinu tohoto jazyka a pˇresto bude odpov´ıdat trénovac´ım dat˚ um. To znamená, ˇze existuje velké mnoˇzstv´ı automat˚ u, které rozpoznávaj´ı slova z tohoto jazyka a nev´ı se tedy, kter´ y konkrétn´ı automat je nejlepˇs´ı a mˇel by b´ yt vybrán jako v´ ysledn´ y. Moˇzn´ ym pˇr´ıstupem k ˇreˇsen´ı tohoto problému je Occamova bˇritva [9]. Podle n´ı je ˇreˇsen´ı t´ım lepˇs´ı, ˇc´ım je jednoduˇsˇs´ı. V naˇsem pˇr´ıpadˇe napˇr. automat maj´ıc´ı ménˇe stav˚ u m˚ uˇzeme povaˇzovat za lepˇs´ı neˇz automat s v´ıce stavy. Automat s minimáln´ım poˇctem stav˚ u mezi vˇsemi automaty rozpoznávaj´ıc´ımi dan´ y jazyk je oznaˇcován jako mDFA a bude definován v pˇr´ıˇst´ı kapitole. Ovˇsem jak je uvedeno v [8], problém hledán´ı mDFA konzistentn´ıho s trénovac´ımi daty je NP-´ upln´ y, proto se v praxi dle [5] hledá tzv. optimáln´ı automat, kter´ y se mDFA snaˇz´ı nˇejak´ ym zp˚ usobem pˇribl´ıˇzit. Protoˇze algoritm˚ u regulárn´ı inference bylo vymyˇsleno pomˇernˇe hodnˇe a vznikaj´ı stále nové, bylo by uˇziteˇcné porovnat existuj´ıc´ı algoritmy i algoritmy novˇe navrˇzené a právˇe to by mˇela umoˇznit pˇriloˇzená aplikace (dále jen aplikace). Tato aplikace implementuje zm´ınˇené testován´ı kvality algoritm˚ u regulárn´ı inference pomoc´ı vybran´ ych statistick´ ych metod, které se zamˇeˇruj´ı na r˚ uzná hlediska pˇribl´ıˇzen´ı uvedenému c´ılovému automatu, podle nˇehoˇz byla generována trénovac´ı a testovac´ı data. Testovan´ y algoritmus je dodán v podobˇe extern´ıho programu, kterému aplikace pˇredá nagenerovaná trénovac´ı data v pevném formátu a obdrˇz´ı od nˇej (deterministick´ y) koneˇcn´ y automat v pevném formátu. Tyto formáty budeme dále naz´ yvat Abbadingo formát dat a Abbadingo formát automatu, protoˇze byly pouˇzity v [1] a odtud jsou také pˇrevzaty. Automat pak aplikace otestuje zvolenou statistickou metodou a vypoˇc´ıtá statistické u ´daje, které je moˇzné uloˇzit do souboru ve formátu vhodném pro vloˇzen´ı do publikac´ı (napˇr. obrázek ˇci LaTeXov´ y kód). Souˇcást´ı aplikace je také nˇekolik program˚ u s algoritmy regulárn´ı inference staˇzen´ ych z [2], aby bylo moˇzné porovnat nové algoritmy regulárn´ı inference se schopn´ ymi a vyzkouˇsen´ ymi. Protoˇze tyto algoritmy byly k dispozici pouze pro UNIXové systémy, jsou v rámci práce upraveny také pro MS Windows. Práce je urˇcena pˇredevˇs´ım vˇedeck´ ym pracovn´ık˚ um vyv´ıjej´ıc´ım algoritmy regulárn´ı inference, kteˇr´ı potˇrebuj´ı otestovat své postupy r˚ uzn´ ymi statistick´ ymi metodami nebo je prezentovat v publikac´ıch. Dále jistˇe bude uˇziteˇcná tˇem, kteˇr´ı vyuˇz´ıvaj´ı algoritmy regulárn´ı inference, aby si pro své u ´ˇcely mohli vybrat vhodn´ y algoritmus na základˇe srovnán´ı pomoc´ı pˇriloˇzené aplikace. Byla ale napsána pro vˇsechny, kteˇr´ı 6

se o zpracovanou problematiku zaj´ımaj´ı nebo si chtˇej´ı jen zkusit otestovat kvalitu nˇekterého z algoritm˚ u. Jak je popsáno v kapitole 4, aplikaci lze snadno rozˇs´ıˇrit napˇr. o dalˇs´ı testovac´ı metody, zp˚ usoby generován´ı dat nebo ji upravit pro vlastn´ı specifické u ´ˇcely pouˇzit´ı.

1.2

Struˇ cn´ y popis kapitol

Kapitola 2 seznamuje se základn´ımi definicemi a vˇetami z oblasti koneˇcn´ ych automat˚ u a regulárn´ı inference a s principy algoritm˚ u regulárn´ı inference. V kapitole 3 jsou popsány zvolené statistické metody pro testován´ı jejich kvality, Abbadingo formáty trénovac´ıch a testovac´ıch dat a automatu a nakonec samotn´ y pr˚ ubˇeh testován´ı. Kapitola 4 shrnuje a hodnot´ı z´ıskané poznatky. Dodatky A a B obsahuj´ı uˇzivatelskou a programátorskou dokumentaci k nástroji, kter´ y implementuje popsané testovac´ı metody. Na závˇer práce je pˇriloˇzen seznam pouˇzité literatury.

7

Kapitola 2 Z´ akladn´ı teorie Tato kapitola seznamuje se základn´ımi definicemi a vˇetami z oblasti koneˇcn´ ych automat˚ u a regulárn´ı inference a s principy algoritm˚ u regulárn´ı inference.

2.1

Koneˇ cn´ e automaty

Tato podkapitola podává základn´ı definice a vˇety z oblasti koneˇcn´ ych automat˚ u. N´ıˇze definujeme ˇretˇezce [4], prefix ˇretˇezce [6] a jazyk [4]. Definice 2.1.1 Necht’ Σ je libovoln´ a koneˇcn´ a mnoˇzina (nazýv´ ame ji abeceda), pak + Σ oznaˇcuje mnoˇzinu vˇsech koneˇcných nepr´ azdných posloupnost´ı utvoˇrených z prvk˚ u ∗ + mnoˇziny Σ, λ oznaˇcuje prázdnou posloupnost a definujeme Σ = Σ ∪ {λ}. Prvky Σ∗ se nazývaj´ı ˇretˇezce. Definice 2.1.2 Necht’ Σ je koneˇcn´ a abeceda. Necht’ u, v jsou prvky z mnoˇziny Σ∗ ˇ (tedy ˇretˇezce nad abecedou Σ). Rekneme, ˇze u je prefixem v, pokud existuje w ∈ Σ∗ tak, ˇze uw = v. Definice 2.1.3 Je-li Σ koneˇcn´ a abeceda a L ⊆ Σ∗ , pak L nazýv´ ame jazykem nad abecedou Σ. K popisu jazyk˚ u pouˇz´ıváme automaty. Ty m˚ uˇzeme uspoˇrádat podle jejich vyjadˇrovac´ı s´ıly. Toto uspoˇrádán´ı se naz´ yvá Chomského hierarchie. Koneˇcné automaty jsou v tomto uspoˇrádán´ı nejn´ıˇze a maj´ı tedy nejmenˇs´ı vyjadˇrovac´ı s´ılu. V následuj´ıc´ım textu definujeme koneˇcn´ y automat, jazyk rozpoznávan´ y koneˇcn´ ym automatem [4] a prefix tree acceptor [10]. Definice 2.1.4 Koneˇcným automatem nazýv´ ame kaˇzdou pˇetici A = (Q, Σ, δ, q0 , F ), kde Q je koneˇcná neprázdná mnoˇzina stav˚ u (stavový prostor), Σ je koneˇcn´ a neprázdn´ a mnoˇzina vstupn´ıch symbol˚ u (vstupn´ı abeceda), δ: Q×Σ → Q je pˇrechodov´ a funkce, q0 ∈ Q je poˇcáteˇcn´ı stav a F ⊆ Q je mnoˇzina koncových stav˚ u. Definice 2.1.5 Pro koneˇcný automat A = (Q, Σ, δ, q0 , F ) rozˇs´ıˇr´ıme pˇrechodovou funkci δ: Q × Σ → Q na zobecnˇenou pˇrechodovou funkci δ ∗ : Q × Σ∗ → Q takto: 8

1. δ ∗ (q, λ) = q pro kaˇzdé q ∈ Q, 2. δ ∗ (q, wa) = δ(δ ∗ (q, w), a) pro kaˇzdé q ∈ Q, w ∈ Σ∗ , a ∈ Σ. Jazykem rozpoznávaným koneˇcným automatem A pak nazveme jazyk L(A) = {w | w ∈ Σ∗ & δ ∗ (q0 , w) ∈ F }. ˇ ıkáme, ˇze slovo w ∈ Σ∗ je pˇrij´ım´ R´ ano automatem A, pr´ avˇe kdyˇz w ∈ L(A). Definice 2.1.6 Prefix tree acceptor vzhledem k I+ (⊂ Σ∗ ) nepr´ azdné mnoˇzinˇe ˇretˇezc˚ u je koneˇcný automat PTA(I+ ) = (Q, Σ, δ, q0 , F ), kde Q = Pr(I+ ) je mnoˇzina vˇsech prefix˚ u slov z I+ , q0 = λ a δ(u, a) = ua, pˇriˇcemˇz u, ua ∈ Q, u ∈ Σ∗ , a ∈ Σ. Prefix tree acceptor m˚ uˇzeme vn´ımat jako strom, v nˇemˇz kaˇzdá cesta z koˇrene do pˇrij´ımac´ıho stavu odpov´ıdá ˇretˇezci z dané mnoˇziny I+ . Dále definujeme mDFA [5] a jazyk rozpoznateln´ y koneˇcn´ ym automatem [4]. Definice 2.1.7 Necht’ mDFA(L) oznaˇcuje poˇctem stav˚ u minim´ aln´ı deterministický koneˇcný automat pˇrij´ımaj´ıc´ı jazyk L. ˇ Definice 2.1.8 Rekneme, ˇze jazyk L je rozpoznatelný koneˇcným automatem, jestliˇze existuje koneˇcný automat A takový, ˇze L = L(A). Existuj´ı r˚ uzné zp˚ usoby, kter´ ymi m˚ uˇzeme jazyky rozpoznávané koneˇcn´ ymi automaty charakterizovat. Jedn´ım z nich jsou regulárn´ı jazyky [4]. Definice 2.1.9 Tˇr´ıda RJ(Σ) regul´ arn´ıch jazyk˚ u nad abecedou Σ je nejmenˇs´ı tˇr´ıda jazyk˚ u nad abecedou Σ splˇ nuj´ıc´ı tyto podm´ınky: 1. Ø ∈ RJ(Σ) a {a} ∈ RJ(Σ) ∀a ∈ Σ. 2. L1 , L2 ∈ RJ(Σ) ⇒ L1 ∪ L2 ∈ RJ(Σ), kde operace ∪ je sjednocen´ı jazyk˚ u. 3. L1 , L2 ∈ RJ(Σ) ⇒ L1 . L2 ∈ RJ(Σ), kde operace . je souˇcin (zˇretˇezen´ı) jazyk˚ u. 4. L ∈ RJ(Σ) ⇒ L∗ ∈ RJ(Σ), kde operace

∗

je iterace jazyka.

Vztah mezi regulárn´ımi jazyky a koneˇcn´ ymi automaty je dán vˇetou n´ıˇze [4]. Vˇ eta 2.1.10 (Kleene) Libovolný jazyk je regul´ arn´ı, pr´ avˇe kdyˇz je rozpoznatelný koneˇcným automatem. Dalˇs´ım zp˚ usobem charakterizace jazyk˚ u rozpoznávan´ ych koneˇcn´ ymi automaty jsou regulárn´ı v´ yrazy [4]. Definice 2.1.11 Mnoˇzinu RV(Σ) regul´ arn´ıch výraz˚ u nad abecedou Σ = {a1 , ..., an } definujeme jako nejmenˇs´ı mnoˇzinu slov v abecedˇe {a1 , ..., an , ø, λ, +, ., ∗, (, )} splˇ nuj´ıc´ı tyto podm´ınky [kde ø, λ, +, ., ∗, (, ) jsou symboly nepatˇr´ıc´ı do Σ]: 9

1. ø ∈ RV(Σ), λ ∈ RV(Σ), a ∈ RV(Σ) pro kaˇzdé a ∈ Σ. 2. α, β ∈ RV(Σ) ⇒ (α + β) ∈ RV(Σ), (α . β) ∈ RV(Σ), (α)∗ ∈ RV(Σ). Vztah mezi regulárn´ımi jazyky a regulárn´ımi v´ yrazy vyjadˇruje definice n´ıˇze [4]. Definice 2.1.12 Kaˇzdý z regul´ arn´ıch výraz˚ u oznaˇcuje jistý regul´ arn´ı jazyk. Výraz ø oznaˇcuje prázdný jazyk, výraz λ oznaˇcuje jazyk {λ}, pro a ∈ Σ oznaˇcuje výraz a jazyk {a}. Jestliˇze α, β jsou výrazy oznaˇcuj´ıc´ı po ˇradˇe jazyky L1 , L2 , potom (α + β) oznaˇcuje L1 ∪ L2 , (α . β) oznaˇcuje L1 . L2 a (α)∗ oznaˇcuje (L1 )∗ .

2.2

Regul´ arn´ı inference

Tato podkapitola obsahuje základn´ı definice z oblasti regulárn´ı inference a seznamuje s principy algoritm˚ u regulárn´ı inference. Nejprve je potˇreba vˇedˇet, jak vypadaj´ı trénovac´ı data, z nichˇz bude uˇcen´ı automat˚ u prob´ıhat a co je vlastnˇe uˇcen´ı a regulárn´ı inference [6]. Definice 2.2.1 Trénovac´ımi daty pro jazyk L nazveme I = I+ ∪I− mnoˇzinu pˇr´ıklad˚ u sestávaj´ıc´ı z pozitivn´ıho vzorku I+ , tzn. koneˇcné podmnoˇziny z jazyka L, a negativn´ıho vzorku I− , tzn. koneˇcné mnoˇziny slov nen´ aleˇzej´ıc´ıch do jazyka L (neboli koneˇcné podmnoˇziny doplˇ nku jazyka L). Mnoˇzina I− m˚ uˇze být v nˇekterých pˇr´ıpadech pr´ azdná. Definice 2.2.2 Necht’ I+ a I− jsou disjunktn´ı podmnoˇziny mnoˇziny Σ∗ , které oznaˇcuj´ı pozitivn´ı a negativn´ı uˇc´ıc´ı vzorky inferenˇcn´ıho algoritmu a I = I+ ∪ I− . Uˇcen´ım nazýváme proces hledán´ı koneˇcného automatu A takového, ˇze vzorky z mnoˇziny I+ jsou pˇrij´ımány automatem A a vzorky z mnoˇziny I− jsou automatem A zam´ıtány. Regulárn´ı inferenc´ı nazýváme proces uˇcen´ı z trénovac´ıch dat I. Nˇekteré algoritmy regulárn´ı inference poˇzaduj´ı, aby mnoˇzina I+ byla tzv. strukturálnˇe kompletn´ı [6]. Definice 2.2.3 Mnoˇzina pozitivn´ıch vzork˚ u I+ je nazýv´ ana struktur´ alnˇe kompletn´ı vzhledem ke koneˇcnému automatu A, pokud existuj´ı pˇrij´ımaj´ıc´ı výpoˇcty pro slova z mnoˇziny I+ takové, ˇze plat´ı: 1. Kaˇzdý pˇrechod A je pouˇzit nejménˇe jednou pˇri pˇrij´ım´ an´ı ˇretˇezc˚ u z I+ . 2. Kaˇzdý prvek F (koncový stav) je pˇrij´ımac´ı alespoˇ n pro jeden ˇretˇezec z I+ . Pro problém regulárn´ı inference definované v´ yˇse existuje hodnˇe ˇreˇsen´ı. My z nich chceme vybrat pouze jedno, které by nám nejv´ıce vyhovovalo. Jednou z moˇznost´ı, která byla jiˇz okomentována v u ´vodu práce, je hledat co nejmenˇs´ı v´ ysledn´ y automat co do poˇctu stav˚ u. Následuje formalizace této moˇznosti ˇreˇsen´ı [5]. 10

Definice 2.2.4 Mˇejme mnoˇziny pozitivn´ıch a negativn´ıch vzork˚ u I+ a I− . Potom koneˇcný automat A je ˇreˇsen´ım problému regul´ arn´ı inference, pokud jsou splnˇeny n´ asleduj´ıc´ı podm´ınky: 1. I+ je strukturálnˇe kompletn´ı vzhledem k A. 2. I− ⊆ Σ∗ − L(A). 3. A je automat s nejmenˇs´ım poˇctem stav˚ u, který splˇ nuje pˇredchoz´ı dvˇe podm´ınky. ˇ sen´ı m˚ Reˇ uˇzeme omezit na mDFA definovan´ y v pˇredchoz´ı podkapitole konzistentn´ı s I+ a I− . Ovˇsem jak je uvedeno v [8], problém hledán´ı mDFA konzistentn´ıho s trénovac´ımi daty je NP-´ upln´ y, proto se v praxi dle [5] hledá tzv. optimáln´ı automat, kter´ y se mDFA snaˇz´ı nˇejak´ ym zp˚ usobem pˇribl´ıˇzit. Právˇe testován´ım tohoto optimáln´ıho automatu zjiˇst’ujeme kvalitu uˇc´ıc´ıho algoritmu podle r˚ uzn´ ych kritéri´ı volbou vhodné testovac´ı metody. Tato kritéria jsou popsána spolu s testovac´ımi metodami v dalˇs´ı kapitole. Dalˇs´ı text popisuje dˇelen´ı a principy algoritm˚ u regulárn´ı inference s jejich konkrétn´ımi pˇr´ıklady a je zpracován podle [9]. Algoritmy regulárn´ı inference m˚ uˇzeme rozdˇelit do nˇekolika skupin. Prvn´ı velkou skupinou jsou algoritmy, které zaˇc´ınaj´ı s PTA pro zadané I+ a sluˇcuj´ı stavy za u ´ˇcelem z´ıskán´ı v´ ystupn´ıho automatu (state merging method [13]). Mohou pracovat s pozitivn´ımi i negativn´ımi vzorky, napˇr. RPNI (regular positive and negative inference [12]), Traxbar [13] a EDSM (evidence driven state merging [11]), nebo pouze s pozitivn´ımi vzorky, napˇr. Alergia [3]. Pokud nejsou k dispozici negativn´ı vzorky, algoritmus mus´ı umˇet rozpoznat jin´ ym zp˚ usobem, kdy ukonˇcit sluˇcován´ı stav˚ u (u algoritmu Alergia je to test podobnosti funkce stav˚ u, dalˇs´ı moˇznost´ı je pouˇz´ıt Occamovu bˇritvu [9]), v opaˇcném pˇr´ıpadˇe k tomu pouˇz´ıvá právˇe negativn´ı vzorky. Do druhé velké skupiny patˇr´ı genetické algoritmy nebo jiné algoritmy zaloˇzené na evoluci, napˇr. GARI (genetic algorithm for regular inference [9]). Dalˇs´ı algoritmy jsou vˇetˇsinou modifikac´ı princip˚ u zm´ınˇen´ ych skupin nebo je vylepˇsuj´ı pˇridan´ ymi prvky, napˇr. r˚ uzn´ ymi heuristikami. Jednou z nich je napˇr. minimal message length (MML [9]).

11

Kapitola 3 Testov´ an´ı algoritm˚ u V této kapitole jsou popsány zvolené statistické metody pro testován´ı jejich kvality, Abbadingo formáty trénovac´ıch a testovac´ıch dat a automatu a nakonec samotn´ y pr˚ ubˇeh testován´ı.

3.1

Testovac´ı metody

V této podkapitole jsou uvedeny testovac´ı metody, které provˇeˇruj´ı kvality algoritm˚ u regulárn´ı inference podle r˚ uzn´ ych hledisek, pouˇzité v aplikaci. Vˇsechny metody maj´ı nˇekolik spoleˇcn´ ych rys˚ u, které je vhodné u ´vodem popsat. Do v´ ystupn´ıho souboru se statistikami je do tabulky vypisována pr˚ umˇerná respektive minimáln´ı/pr˚ umˇerná/maximáln´ı procentuáln´ı u ´spˇeˇsnost testován´ı pro danou metodu a zadan´ y poˇcet pokus˚ u nebo je jako v´ ystup vykreslen graf. Tyto v´ ystupy lze také vzájemnˇe kombinovat. D´ıky opakován´ı testován´ı na r˚ uzn´ ych datech je z tabulky nebo grafu pˇresnˇeji vidˇet kvalita automatu od programu s algoritmem, neˇz kdyby testován´ı probˇehlo pouze jednou. Genetické (evoluˇcn´ı) algoritmy jsou obecnˇe nedeterministické, proto se pˇri testován´ı pouˇzije vˇzdy pr˚ umˇer z 10 bˇeh˚ u algoritmu. Tento poˇcet bˇeh˚ u byl pro testován´ı zvolen podle [5]. V následuj´ıc´ım seznamu budou jednotlivé metody popsány spolu s vysvˇetlen´ım jejich vyuˇzit´ı: 1. Metoda ovˇ eˇ ren´ı konzistence automatu s tr´ enovac´ımi daty. Pouˇz´ıvá k tomu stejná trénovac´ı data, jaká byla pˇredána programu s algoritmem. I kdyˇz se toto testován´ı m˚ uˇze na prvn´ı pohled zdát nesmyslné, protoˇze by napˇr. staˇcilo, aby automat pˇrij´ımal jazyk sestávaj´ıc´ı právˇe z pozitivn´ıch vzork˚ u, poslouˇz´ı hlavnˇe v prvn´ıch fáz´ıch v´ yvoje programu, kdy si autor nen´ı jist jeho správnost´ı. M˚ uˇze se tedy stát, ˇze program dostane trénovac´ı data a na v´ ystup vydá automat, kter´ y s nimi nen´ı konzistentn´ı. 2. Metoda testov´ an´ı schopnosti automatu klasifikovat testovac´ı data. Ta jsou disjunktn´ı s trénovac´ımi daty a lze tedy pomoc´ı nich odhadnout, jak dobˇre automat zobecˇ nuje na nová data, která pˇredt´ım jeˇstˇe nevidˇel, protoˇze nebyla obsaˇzena v trénovac´ıch datech.

12

3. Metoda Abbadingo podobná pˇredchoz´ı metodˇe je pˇrevzata z [11]. Pˇredchoz´ı metoda z n´ı dokonce vycház´ı a je jej´ı obecnˇejˇs´ı variantou. Aˇckoli je metoda Abbadingo speciáln´ım pˇr´ıpadem pˇredchoz´ı metody, je pˇresto velmi uˇziteˇcná a to proto, ˇze umoˇzn ˇuje jednoduˇse provést test pˇresnˇe podle soutˇeˇze Abbadingo [11]. Tato metoda také testuje schopnost automatu klasifikovat testovac´ı data jako pˇredchoz´ı metoda, ale dˇelá to pouze pro automaty s poˇcty stav˚ u 64, 128, 256 a 512, které pracuj´ı s binárn´ımi vzorky. V aplikaci je nav´ıc upravena tak, ˇze m˚ uˇze generovat 1 aˇz 4 z tˇechto automat˚ u. V ˇclánku [11] se povaˇzuje problém za vyˇreˇsen´ y (automat od programu s algoritmem je dostateˇcnˇe kvalitn´ı), pokud je automatem správnˇe klasifikováno v´ıce neˇz 99% testovac´ıch vzork˚ u. V aplikaci dostáváme m´ısto toho v´ ystup, kter´ y je popsán v u ´vodu této podkapitoly. Pouˇzité poˇcty trénovac´ıch dat v metodˇe Abbadingo pro vˇsechny kombinace poˇctu stav˚ u a sloˇzitosti jsou uvedeny v Tabulce 1, která je pˇrevzata podle Tabulky 1 z ˇclánku [11]. Jak pˇresnˇe metoda pracuje je popsáno v uˇzivatelské dokumentaci v dodatku a ukázáno na pˇr´ıkladˇe.

64 velikost 128 automatu 256 512

sloˇ zitost tr´ enovac´ıch dat IV III II I 4456 3478 2499 1521 13894 10723 7553 4382 36992 28413 19834 11255 115000 87500 60000 32500

Tabulka 1. Poˇcty trénovac´ıch dat v Abbadingu. 4. Metoda porovn´ an´ı poˇ ctu stav˚ u zadan´ eho nebo vygenerovan´ eho automatu s poˇ ctem stav˚ u automatu od programu s algoritmem. Právˇe tato metoda testuje pˇribl´ıˇzen´ı mDFA z hlediska poˇctu stav˚ u. Procentuáln´ı u ´spˇeˇsnost této metody ale m˚ uˇze b´ yt i vˇetˇs´ı neˇz 100%, protoˇze jednak automat, z nˇehoˇz byla generována trénovac´ı data nemusel b´ yt mDFA pro dan´ y jazyk a nav´ıc z˚ ustává pˇri testován´ı touto metodou otázkou, zda automat od programu pˇrij´ımá stejn´ y jazyk jako zadan´ y ˇci vygenerovan´ y automat. Je tedy dobré tuto metodu kombinovat s metodou testován´ı schopnosti automatu klasifikovat testovac´ı data. 5. Metoda porovn´ an´ı MML (minimal message length) pro automat z aplikace a automat od algoritmu regul´ arn´ı inference. MML je spoˇc´ıtána podle vzorce M log2 (N )−log2 ((N −1)!)+

N X

(log2 ((tj +V −1)!)−log2 ((V −1)!)−

j=1

V X

log2 (nij !))

i=1

uvedeného v [9], kde M je poˇcet vˇsech pˇrechod˚ u, N poˇcet stav˚ u, V velikost abecedy zv´ yˇsená o 1, tj poˇcet odchod˚ u ze stavu j pˇri procházen´ı trénovac´ıch dat a nij poˇcet odchod˚ u ze stavu j symbolem i pˇri procházen´ı trénovac´ıch dat. Vypoˇc´ıtané MML jsou porovnány a urˇc´ı se z nich kvalita automatu od 13

programu s algoritmem. Tato metoda je po pˇredchoz´ı metodˇe dalˇs´ım zp˚ usobem mˇeˇren´ı jednoduchosti v´ ysledného automatu. MML zjednoduˇsenˇe ˇreˇceno urˇcuje, jak dlouhá zpráva by byla potˇreba, aby byla co nejkratˇs´ı a zároveˇ n dokázala pˇr´ıjemci popsat automat i trénovac´ı data zakódovaná pomoc´ı automatu tak, aby je podle n´ı umˇel zrekonstruovat.

3.2

Abbadingo form´ aty

V této podkapitole jsou popsány Abbadingo formáty trénovac´ıch a testovac´ıch dat a automatu i s konkrétn´ımi pˇr´ıklady podle [1]. Abbadingo formát trénovac´ıch a testovac´ıch dat má v hlaviˇcce uveden poˇcet ˇretˇezc˚ u, z nichˇz se data skládaj´ı a poˇcet symbol˚ u abecedy (v [1] jsou pouˇzity symboly 0 a 1, tedy poˇcet symbol˚ u je 2). Kaˇzd´ y z dalˇs´ıch ˇrádk˚ u pˇredstavuje jeden pˇr´ıklad. Skládá se z informace o tom, zda je pozitivn´ı (1), negativn´ı (0) nebo nen´ı známo, zda jej automat pˇrij´ımá, tedy jedná se o testovac´ı data (-1). Následuj´ı délky ˇretˇezce a symboly ˇretˇezce oddˇelené b´ıl´ ymi znaky. Délka ˇretˇezce je rovna poˇctu symbol˚ u. Pˇr´ıklad Abbadingo formátu trénovac´ıch dat pro I+ = {1000, 0100, 0010, 10111, 111101, 010000, 100000, 0001101, 0000101} a I− = {101, 0000, 1101, 00000, 00101, 010111, 1000111}: 16 2 141 140 140 151 161 160 161 170 170 031 040 041 050 050 060 071

0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 0

0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0

0 0 0 1 1 0 0 1 0

1 0 0 0 1 1

0 1 0 0 1 0

0 1 11 111

1 0 0 01 01

Pˇr´ıklad Abbadingo formátu testovac´ıch dat: 20 2 -1 7 0 0 1 1 0 0 0 -1 7 1 0 0 1 1 0 1 14

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

7 7 7 7 6 7 7 7 5 6 6 5 7 7 7 7 7 7

1 0 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 1

0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1

1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1

0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0

1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1

0 1 0 0 1 0 1 1

1 0 1 0 1 0 0

1 1 1 1 0 1 1 1

1 0 1 1 1 0

Abbadingo formát automatu obsahuje v hlaviˇcce u ´daje o poˇctu stav˚ u a velikosti abecedy (poˇctu symbol˚ u). Kaˇzd´ y dalˇs´ı ˇrádek reprezentuje jeden stav. Postupnˇe obsahuje nezáporné celé ˇc´ıslo stavu, informaci o tom, zda je stav koncov´ y a pro kaˇzd´ y symbol z abecedy (nezáporné celé ˇc´ıslo) ˇc´ıslo stavu, do nˇehoˇz se dostaneme, pokud je symbol na vstupu. Symboly se ˇrad´ı podle abecedy vzestupnˇe a berou se za sebou jdouc´ı ˇc´ısla zaˇc´ınaj´ıc´ı od 0 (napˇr. ve vzorc´ıch se dvˇema symboly to budou 0 a 1). Pˇr´ıklad Abbadingo formátu automatu: 5 0 1 2 3 4

2 0 1 1 0 0

1 3 4 2 0

3.3

2 4 1 0 3

Tr´ enovac´ı a testovac´ı data

V této podkapitole je podrobnˇe vysvˇetlen zp˚ usob generován´ı trénovac´ıch a testovac´ıch dat. Aplikace generuje zadan´ y poˇcet trénovac´ıch dat obsahuj´ıc´ıch pozitivn´ı i negativn´ı vzorky, které se mohou opakovat. Pokud bychom tedy chtˇeli testovat algoritmus, kter´ y negativn´ı vzorky nepotˇrebuje, mus´ı se umˇet vypoˇrádat s negativn´ımi vzorky na vstupu (napˇr´ıklad je ignorovat). Testovac´ı data jsou omezena pouze podm´ınkou, 15

ˇze vzorek nesm´ı b´ yt obsaˇzen v trénovac´ıch datech, tedy mnoˇziny trénovac´ıch a testovac´ıch dat mus´ı b´ yt disjunktn´ı. Jejich poˇcet také zadává uˇzivatel. Pˇri generován´ı trénovac´ıch a testovac´ıch dat lze zvolit, zda trénovac´ı data obsahuj´ı pozitivn´ı a negativn´ı vzorky náhodnˇe nebo je polovina trénovac´ıch dat pozitivn´ı a polovina negativn´ı. Poloviny se uplatn´ı hlavnˇe v pˇr´ıpadˇe, ˇze dan´ y jazyk je hust´ y, tedy c´ılov´ y automat pˇrij´ımá témˇeˇr vˇsechna slova nad pouˇzitou abecedou a skoro vˇsechny vzorky by bez pouˇzit´ı dˇelen´ı vzork˚ u na poloviny byly pozitivn´ı. Potom napˇr. jednostavov´ y automat od programu s algoritmem regulárn´ı inference pˇrij´ımaj´ıc´ı vˇsechny vzorky by z hlediska klasifikace testovac´ıch dat dopadl velmi dobˇre (´ uspˇeˇsnost klasifikace by se bl´ıˇzila 100%). C´ılov´ y automat také m˚ uˇze pˇrij´ımat u ´plnˇe vˇsechna slova nad danou abecedou, potom by neexistoval ˇzádn´ y negativn´ı vzorek. V aplikaci se proto po nalezen´ı dostateˇcného poˇctu pozitivn´ıch vzork˚ u pˇri generován´ı dat na poloviny omezuje poˇcet pokus˚ u hledán´ı negativn´ıch vzork˚ u na 1000, po dosaˇzen´ı tohoto limitu je vypsána chyba a ukonˇcen bˇeh aplikace. Stejn´ y limit je nastaven pro hledán´ı pozitivn´ıch vzork˚ u po nalezen´ı dostateˇcného poˇctu negativn´ıch vzork˚ u, kdyby automat nepˇrij´ımal ˇzádná nebo témˇeˇr ˇzádná slova. Dále se liˇs´ı zp˚ usob generován´ı dat: • Pokud se jedná o binárn´ı vzorky, m˚ uˇze uˇzivatel vybrat metodu, která bere data náhodnˇe z mnoˇziny 16n2 − 1 vzork˚ u stejnˇe jako v [11], kde n je poˇcet stav˚ u c´ılového automatu. Jejich délky leˇz´ı mezi 0 a 2 log2 n + 3, jak je uvedeno v [11]. Tato metoda ale generuje delˇs´ı vzorky s vˇetˇs´ı pravdˇepodobnost´ı, protoˇze ˇc´ım delˇs´ı vzorek vezme, t´ım v´ıce existuje moˇznost´ı, jak bude vzorek vypadat a delˇs´ıch vzork˚ u je tedy vˇetˇs´ı mnoˇzstv´ı. • Abychom se vyhnuli problému zm´ınˇeném na konci pˇredchoz´ıho bodu, dalˇs´ı metoda nejprve vybere délku vzorku a pak generuje symboly, dokud nedostane vzorek této délky. Vˇsechny délky tedy maj´ı stejnou pravdˇepodobnost a nav´ıc lze pouˇz´ıt i jiné neˇz binárn´ı vzorky a tud´ıˇz otestovat automaty pracuj´ıc´ı s v´ıce neˇz dvˇema symboly, coˇz pˇredchoz´ı metoda neum´ı. Jako poˇcet generovan´ ych vzork˚ u se vol´ı pro trénovac´ı i testovac´ı data druhá mocnina poˇctu stav˚ u automatu normalizovaná poˇzadovanou sloˇzitost´ı dat. Pokud aplikace testuje algoritmy tˇret´ı metodou popsanou v pˇredchoz´ı kapitole, jsou speciálnˇe definovány poˇzadované poˇcty trénovac´ıch a testovac´ıch dat dle [11] (viz Tabulka 1).

3.4

Pr˚ ubˇ eh testov´ an´ı

Tato podkapitola popisuje postupy pˇriloˇzené aplikace implementuj´ıc´ı testován´ı algoritm˚ u regulárn´ı inference. Aplikace umoˇzn ˇuje zadat na vstup automaty, na nichˇz má prob´ıhat testován´ı, tˇremi zp˚ usoby: 1. vygenerovat náhodné automaty, z nichˇz prvn´ı má n stav˚ u a kaˇzd´ y dalˇs´ı má o 4 stavy v´ıce (kde n je dˇelitelné 4 a urˇcuje jej uˇzivatel stejnˇe jako poˇcet automat˚ u) nebo náhodné automaty pro testován´ı metodou Abbadingo z podkapitoly 3.1, 16

které maj´ı na rozd´ıl od pˇredchoz´ıch pˇredem dané poˇcty stav˚ u na 64, 128, 256 a 512 a mohou tedy b´ yt maximálnˇe 4 (viz Tabulka 1), 2. naˇc´ıst automaty ze vstupn´ıho souboru pevného formátu od uˇzivatele, 3. naˇc´ıst automaty pro Tomitovy jazyky, které jsou vypsány v Tabulce 2 zpracované podle [9] (poˇcty stav˚ u jsou upraveny kv˚ uli pouˇzit´ı Abbadingo formátu automatu pro binárn´ı vzorky). Jazyk L1 L2 L3 L4 L5 L6 L7

Popis (regul´ arn´ı v´ yraz)

Poˇ cet stav˚ u 0* 2 (01)* 3 Nemá lich´ y poˇcet 1 a potom lich´ y poˇcet 0 5 Maximálnˇe dvˇe po sobˇe následuj´ıc´ı 0 4 Sud´ y poˇcet 0 a sud´ y poˇcet 1 4 Poˇcet 0 a poˇcet 1 kongruentn´ı modulo 3 3 0*1*0*1* 5

Tabulka 2. Tomitovy jazyky. Generován´ı automat˚ u je pˇrevzato z [11], tedy aplikace nejprve vytvoˇr´ı orientovan´ y graf na 54 n vrchol˚ u stupnˇe 2, náhodnˇe vybere vrchol jako poˇcáteˇcn´ı stav a vezme podgraf obsahuj´ıc´ı vrcholy dosaˇzitelné z koˇrene. Pro kaˇzd´ y vrchol náhodnˇe urˇc´ı, zda se bude nebo nebude jednat o pˇrij´ımac´ı stav. Generován´ı se provád´ı tak dlouho, dokud maximáln´ı hloubka v´ ysledného grafu nen´ı právˇe 2 log2 n − 2. V´ ysledkem popsaného postupu je automat pracuj´ıc´ı s binárn´ımi vzorky. Po vytvoˇren´ı automat˚ u si aplikace naˇcte informace o programech s algoritmy, které má testovat. Poté si vezme jeden automat a opakovanˇe se nageneruj´ı trénovac´ı a testovac´ı data, na nichˇz se otestuj´ı vˇsechny algoritmy. Protoˇze testován´ı prob´ıhá pro vˇsechny algoritmy na stejn´ ych datech, kontroluje se strukturáln´ı kompletnost trénovac´ıch dat, pokud to poˇzaduje alespoˇ n jeden z testovan´ ych algoritm˚ u. Pokud skonˇc´ı testován´ı pro jeden automat, uloˇz´ı se v´ ysledky pro zvolenou testovac´ı metodu a opakuje se stejn´ y postup na ostatn´ıch automatech. Nakonec vyp´ıˇse nebo vykresl´ı v´ ysledky se statistikami ve formátu, jenˇz si uˇzivatel vybere.

17

Kapitola 4 Z´ avˇ er 4.1

Zhodnocen´ı pr´ ace

Problém regulárn´ı inference je velmi zaj´ımav´ y a uˇziteˇcn´ y. Má nemal´ y teoretick´ y v´ yznam, ale také ˇsiroké spektrum aplikac´ı jako je napˇr. identifikace sekvenˇcn´ıch proces˚ u, rozpoznáván´ı vzor˚ u, zpracován´ı ˇreˇci a pˇrirozeného jazyka, exploratorn´ı sekvenˇcn´ı anal´ yza, umˇelá inteligence nebo data mining. V aplikaci se podaˇrilo implementovat nˇekolik metod pro testován´ı algoritm˚ u regulárn´ı inference a poskytnout tak vˇedeck´ ym pracovn´ık˚ um nástroj k usnadnˇen´ı v´ yvoje tˇechto algoritm˚ u. Souˇcást´ı aplikace je také nˇekolik program˚ u s algoritmy regulárn´ı inference staˇzen´ ych z [2], aby bylo moˇzné porovnat nové algoritmy regulárn´ı inference se schopn´ ymi a vyzkouˇsen´ ymi. Protoˇze tyto algoritmy byly k dispozici pouze pro UNIXové systémy, jsou v rámci práce upraveny také pro MS Windows. Jako teoretick´ y podklad aplikace slouˇz´ı samotn´ y text této práce, jehoˇz souˇcást´ı je v pˇr´ıloze i dokumentace k aplikaci. Nejd˚ uleˇzitˇejˇs´ı a nejv´ıce pouˇz´ıvanou se pravdˇepodobnˇe stane metoda testuj´ıc´ı schopnost algoritmu klasifikovat testovac´ı data. V´ yznam této metody spoˇc´ıvá v prezentaci schopnost´ı algoritmu zobecˇ novat na nová data. Zde vˇsak dále uˇzivatel m˚ uˇze zvolit zp˚ usob generován´ı trénovac´ıch a testovac´ıch dat. Zp˚ usob pouˇzit´ y v [11], kter´ ym je vybrán jeden vzorek z univerza je prvn´ı moˇznost´ı. Ta oˇcividnˇe upˇrednostˇ nuje delˇs´ı vzorky pˇred kratˇs´ımi. Proto je druhou z moˇznost´ı nejdˇr´ıve náhodnˇe vybrána délka vzorku a pak je teprve vygenerován samotn´ y vzorek této délky. Celkov´ yu ´spˇech práce ukáˇze aˇz jej´ı uˇzit´ı v praxi pˇri v´ yvoji algoritm˚ u pro uˇcen´ı koneˇcn´ ych automat˚ u.

4.2

Moˇ zn´ a vylepˇ sen´ı

Na kaˇzdé práci je stále co zlepˇsovat. Proto vznikla tato kapitola, aby dala prostor k publikaci nápad˚ u, které nebyly zrealizovány. Urˇcitˇe existuje v´ıce zp˚ usob˚ u generován´ı trénovac´ıch a testovac´ıch dat. Bylo by moˇzno napˇr´ıklad nahlédnout na tuto problematiku z hlediska toho, s jakou pravdˇepodobnost´ı se automat vydá po jedné nebo druhé vˇetvi m´ısto pravdˇepodobnosti délky 18

vzorku nebo v´ ybˇeru vzorku z jejich dané mnoˇziny. Tyto metody totiˇz zp˚ usob´ı, ˇze pokud jsou délky libovoln´ ych vˇetv´ı automatu vycházej´ıc´ıch ze stejného stavu nerovnomˇerné (na jedné z nich lze vygenerovat v´ıce vzork˚ u), pak má jedna vˇetev vˇetˇs´ı pravdˇepodobnost neˇz druhá, ˇze se pˇri generován´ı dat automat vydá právˇe po n´ı. To by ˇreˇsila metoda, která by brala stejné pravdˇepodobnosti, ˇze se automat vydá po jedné vˇetvi (pokud je stav koncov´ y, mus´ıme to zapoˇc´ıtat jako dalˇs´ı vˇetev). Jistˇe by se také daly zkoumat dalˇs´ı metody testován´ı algoritm˚ u regulárn´ı inference a vymyslet t´ım dalˇs´ı hlediska pohledu na kvalitu automat˚ u, které tyto algoritmy vydávaj´ı na v´ ystupu.

19

Dodatek A Uˇ zivatelsk´ a dokumentace A.1

Popis pr´ ace s aplikac´ı

Aplikace slouˇz´ı k testován´ı algoritm˚ u regulárn´ı inference vybran´ ymi testovac´ımi metodami. Bliˇzˇs´ı popis najdeme v hlavn´ı ˇcásti textu této práce. Aplikace se spouˇst´ı z pˇr´ıkazové ˇrádky pˇr´ıkazem TestAlgDFA a komunikace s n´ı prob´ıhá prostˇrednictv´ım textov´ ych konfiguraˇcn´ıch soubor˚ u (vzorové soubory najdeme na pˇriloˇzeném CD). V´ ystupy se pak ukládaj´ı rovnˇeˇz do soubor˚ u. Nejprve si pop´ıˇseme vstupn´ı konfiguraˇcn´ı soubory, které je potˇreba um´ıstit do pracovn´ıho adresáˇre aplikace. V´ ystupn´ı soubory najdeme rovnˇeˇz v pracovn´ım adresáˇri aplikace. Hlavn´ım konfiguraˇcn´ım souborem params.tadfa ˇr´ıd´ıme cel´ y pr˚ ubˇeh testován´ı. Jeho obsahem jsou hodnoty potˇrebn´ ych parametr˚ u napsané pod sebou. Pokud nˇejakou hodnotu nepotˇrebujeme, v˚ ubec se do souboru neuvád´ı. Následuj´ıc´ı seznam popisuje vˇsechny parametry, které tento soubor obsahuje a jejich vzájemné závislosti (v´ yrazem Px znaˇc´ıme parametr x, kde x je ˇc´ıslo parametru v seznamu): 1. Inicializovat random generátor ruˇcnˇe (1 = ano, 0 = ne). Aplikace pouˇz´ıvá generátor náhodn´ ych ˇc´ısel. Jeho ruˇcn´ı nastaven´ı na urˇcitou hodnotu m˚ uˇze b´ yt uˇziteˇcné napˇr. pokud hledáme v programu s algoritmem regulárn´ı inference nˇejakou chybu a potˇrebujeme jej nastavit opakovanˇe na stejnou hodnotu. 2. Druh automatu (1 = Tomitovy jazyky (v pracovn´ım adresáˇri mus´ı b´ yt soubor tomita.tadfa), 2 = ze souboru od uˇzivatele, 3 = Abbadingo, n = z generátoru (n je poˇcet stav˚ u automatu dˇeliteln´ y 4)). 3. Poˇcet automat˚ u (pokud P2 = 1, 3, 4). Jméno souboru (pokud P2 = 2). 4. Poˇcet trénovac´ıch dat (uvád´ı se jen pro P2 = 1, 2, 4). Je potˇreba zadat rozumné mnoˇzstv´ı, protoˇze pokud zadáme mnoho (v´ıce neˇz lze pro dan´ y automat vygenerovat), mohla by aplikace spotˇrebovat vˇsechny vzorky na generován´ı trénovac´ıch dat a v generován´ı testovac´ıch dat by nastala chyba (testovac´ı data obsahuj´ı pouze vzorky, které nejsou v trénovac´ıch datech). Pokud naopak zadáme pˇr´ıliˇs málo, m˚ uˇze b´ yt uˇcen´ı ménˇe u ´spˇeˇsné. 5. Poˇcet testovac´ıch dat (uvád´ı se jen pro P2 = 1, 2, 4). 20

6. Stejné pravdˇepodobnosti délek vzork˚ u (1 = ano, 0 = ne, uvád´ı se jen pro P2 = 1, 2, 4). Pokud 1 z automat˚ u nepracuje se 2 symboly, nelze zvolit 0. 7. Testovac´ı metoda (1 = konzistence automatu s trénovac´ımi daty, 2 = schopnost automatu klasifikovat testovac´ı data, 3 = metoda Abbadingo, 4 = porovnán´ı poˇctu stav˚ u, 5 = porovnán´ı MML; uvád´ı se jen pro P2 = 1, 2, 4). 8. Generovat trénovac´ı data náhodnˇe (1 = ano, 0 = ne). Pokud je zvoleno 0, bude vygenerována polovina pozitivn´ıch a polovina negativn´ıch vzork˚ u. 9. Poˇcet opakován´ı generován´ı dat pro automat. Jako v´ ysledek se pak bere pr˚ umˇer z tohoto poˇctu opakován´ı. 10. Jméno souboru pro uloˇzen´ı trénovac´ıch dat (pro P13 = 1 najdeme soubory pod názvy jméno automat opakován´ı sloˇzitost, kde vˇse kromˇe jména jsou ˇc´ısla pˇr´ısluˇsné poloˇzky). 11. Jméno souboru pro uloˇzen´ı testovac´ıch dat (pro P13 = 1 najdeme soubory pod názvy jméno automat opakován´ı sloˇzitost, kde vˇse kromˇe jména jsou ˇc´ısla pˇr´ısluˇsné poloˇzky). 12. Jméno souboru pro uloˇzen´ı automatu od programu s algoritmem (pro P14 = 1 najdeme soubory pod názvy jméno automat opakován´ı sloˇzitost algoritmus nedeterminismus, kde nedeterminismus je ˇc´ıslo od 1 do 10 pro nedeterministické algoritmy, jinak je vˇzdy rovno 1, vˇse ostatn´ı kromˇe jména jsou ˇc´ısla pˇr´ısluˇsné poloˇzky). 13. Ukládat trénovac´ı a testovac´ı data (1 = ano, 0 = ne). 14. Ukládat automaty z generátoru (pokud se automaty generuj´ı) a od programu s algoritmem (1 = ano, 0 = ne). 15. Vypisovat v´ ystup do formátu csv (1 = ano, 0 = ne). 16. Vypisovat v´ ystup jako tabulku do formátu tex (1 = ano, 0 = ne). 17. Vypisovat pro kaˇzd´ y automat graf pro srovnán´ı algoritm˚ u (1 = ano, 0 = ne). 18. Vypisovat pro kaˇzd´ y algoritmus graf pro srovnán´ı automat˚ u (1 = ano, 0 = ne). 19. Poˇcet desetinn´ ych m´ıst pro v´ ypis procentuáln´ıch u ´spˇeˇsnost´ı ve v´ ystupech. 20. Vypisovat na v´ ystup také minima a maxima (1 = ano, 0 = ne). Pokud je P16 = 1, je maximáln´ı poˇcet automat˚ u 18 pro hodnotu 1 a 54 pro hodnotu 0. Pro P9 = 1 je pr˚ umˇer roven v´ ysledku a minima i maxima se mu rovnaj´ı. ˇ ıslo pro ruˇcn´ı inicializaci random generátoru (uvád´ı se jen pro P1 = 1). 21. C´ 22. Jméno souboru pro v´ ystup do formátu csv (uvád´ı se jen pro P15 = 1). 23. Jméno souboru pro v´ ystup do formátu tex (uvád´ı se jen pro P16 = 1). 21

24. Jméno souboru pro graf s porovnán´ım algoritm˚ u (uvád´ı se jen pro P17 = 1). 25. Jméno souboru pro graf s porovnán´ım automat˚ u (uvád´ı se jen pro P18 = 1). 26. Formát grafu (1 = png, 2 = gif, 3 = jpg; uvád´ı se jen pro P17 = 1 nebo P18 = 1). 27. Násobek základn´ı velikosti grafu 100 x 75 (uvád´ı se jen pro P17 = 1 nebo P18 = 1). 28. Cesta k souboru s gnuplotem (absolutn´ı ˇci relativn´ı; gnuplot\bin\pgnuplot znamená, ˇze v pracovn´ım adresáˇri aplikace se nacház´ı adresáˇr gnuplot, v nˇem adresáˇr bin a v nˇem soubor pgnuplot.exe pro spuˇstˇen´ı gnuplotu; uvád´ı se jen pro P17 = 1 nebo P18 = 1). Gnuplot je freeware (ke staˇzen´ı napˇr. na [7]). 29. Jméno souboru pro uloˇzen´ı automatu z generátoru (uvád´ı se jen pro P14 = 1, soubory najdeme pod názvy jméno automat opakován´ı sloˇzitost algoritmus nedeterminismus, kde nedeterminismus je ˇc´ıslo od 1 do 10 pro nedeterministické algoritmy, jinak je vˇzdy rovno 1, vˇse ostatn´ı kromˇe jména jsou ˇc´ısla pˇr´ısluˇsné poloˇzky). Dále je potˇreba do souboru algors.tadfa napsat informace o algoritmech, které chceme testovat. Kaˇzd´ y ˇrádek reprezentuje 1 algoritmus a obsahuje jméno programu s algoritmem (v MS Windows nen´ı potˇreba udávat pˇr´ıponu .exe), informaci o tom, zda je algoritmus deterministick´ y (1 = ano, 0 = ne), informaci o tom, zda algoritmus poˇzaduje strukturáln´ı kompletnost trénovac´ıch dat (1 = ano, 0 = ne) a dalˇs´ı parametry pro program s algoritmem (napˇr. pˇriloˇzen´ y algoritmus rlb potˇrebuje znát velikost okénka). Pokud chceme testovat automaty zadané uˇzivatelem, je tˇreba vytvoˇrit soubor, jenˇz obsahuje na prvn´ım ˇrádku poˇcet automat˚ u, dále následuj´ı jednotlivé automaty v Abbadingo formátu automatu. Jméno tohoto souboru sdˇel´ıme aplikaci v konfiguraˇcn´ım souboru params.tadfa popsaném v´ yˇse. K aplikaci jsou pˇriloˇzeny algoritmy red-blue, rlb a traxbar (podrobnˇeji je popisuje posledn´ı odstavec programátorské dokumentace). Kaˇzd´ y testovan´ y program s algoritmem uveden´ y v souboru algors.tadfa mus´ı b´ yt uloˇzen v pracovn´ım adresáˇri s aplikac´ı v podobˇe spustitelného souboru. V´ ystup do formátu tex je reprezentován tabulkou, kde pro kaˇzd´ y algoritmus najdeme v´ ysledky ke vˇsem automat˚ um. Poˇcet ˇrádk˚ u tabulky pro algoritmus se tedy rovná poˇctu automat˚ u a vypisovány jsou pr˚ umˇerné hodnoty. Pokud ale nav´ıc vypisujeme minima a maxima, u kaˇzdého automatu pˇribyde nad ˇrádkem s pr˚ umˇery ˇrádek s minimy a pod ˇrádkem s pr˚ umˇery ˇrádek s maximy. U v´ ystupu v podobˇe grafu lze zvolit, zda se bude vykreslovat soubor pro kaˇzd´ y automat a bude vˇzdy obsahovat srovnán´ı vˇsech algoritm˚ u nebo se bude vykreslovat soubor pro kaˇzd´ y algoritmus a bude vˇzdy obsahovat srovnán´ı vˇsech automat˚ u. Srovnán´ı je vyjádˇreno procentuáln´ı u ´spˇeˇsnost´ı pro 4 sloˇzitosti trénovac´ıch dat, kde horn´ı hranice grafu je volena podle nejvyˇsˇs´ı u ´spˇeˇsnosti, aby se dosáhlo co moˇzná nejlepˇs´ı ˇcitelnosti. Je samozˇrejmˇe moˇzné grafy vykreslovat i pro minima a maxima a ne jen pro pr˚ umˇery, potom jméno souboru s grafem konˇc´ı min“ resp. max“. ” ” 22

A.2

Pˇ r´ıklad testov´ an´ı

Následuj´ıc´ı grafy (4 pro porovnán´ı klasifikaˇcn´ıch schopnost´ı algoritm˚ u na automatech maj´ıc´ıch 64, 128, 256 a 512 stav˚ u, 2 pro znázornˇen´ı zmˇen klasifikaˇcn´ıch schopnost´ı algoritm˚ u s rostouc´ı velikost´ı automatu) a Tabulka 3 ukazuj´ı v´ ysledky reálného pˇr´ıkladu testován´ı metodou Abbadingo pro P1 = 0, P2 = 1, P8 = 1, P19 = 3, P20 = 0, P26 = 3 a P27 = 4. V tomto testován´ı byly pouˇzity programy s algoritmy red-blue a rlb. Pro rlb bylo zvoleno okénko velikosti 10. Toto testován´ı prob´ıhá pˇresnˇe podle soutˇeˇze Abbadingo [11], ale d´ıky náhodnému generován´ı automat˚ u i dat a d´ıky jinému vyhodnocen´ı (v soutˇeˇzi Abbadingo se bere jako v´ ysledek procentuáln´ı u ´spˇeˇsnost, kde se pokus povaˇzuje za u ´spˇeˇsn´ y, pokud je správnˇe klasifikováno v´ıce neˇz 99% testovac´ıch vzork˚ u, my bereme za v´ ysledek pr˚ umˇer klasifikace testovac´ıch dat ze vˇsech opakován´ı, coˇz pro 1 opakován´ı dává právˇe v´ ysledek tohoto pokusu) se mohou v´ ysledky liˇsit. Z graf˚ u je vidˇet, ˇze pˇri zadaném nastaven´ı algoritmus red-blue pˇrekonává algoritmus rlb, kter´ y nedopadl moc dobˇre.

23

24

target size IV III II 64 54.111 55.944 52.889 128 50.500 55.444 55.000 256 49.833 49.056 49.778 512 45.278 49.056 52.611 64 99.833 100.000 100.000 128 100.000 99.944 99.833 256 99.889 99.944 99.889 512 99.500 99.500 99.833

I algorithm 52.444 52.389 rlb 49.389 50.889 99.500 99.722 red-blue 99.944 99.389

Tabulka 3. V´ ysledek vzorového testován´ı metodou Abbadingo.

25

Dodatek B Program´ atorsk´ a dokumentace Aplikace TestAlgDFA slouˇz´ıc´ı k testován´ı kvality algoritm˚ u regulárn´ı inference je napsána v jazyce C++ pro systémy MS Windows (32-bit) a systémy na bázi UNIXu. Zkompilována a testována byla v MS Windows XP Professional SP3 (EN) pod MS Visual Studio .NET 2005 Professional (EN) s nejnovˇejˇs´ımi aktualizacemi k 13.7.2008 a v Linuxu Fedora 7 s jádrem 2.6.22.9-91.fc7 pod g++ (GCC) 4.1.2. Nˇekteré konstrukce (napˇr. názvy funkc´ı) se mezi systémy MS Windows a systémy na bázi UNIXu liˇs´ı, v hlaviˇckovém souboru TestAlgDFA.h jsou proto definována makra rozliˇsuj´ıc´ı mezi tˇemito systémy a podle nich je vˇzdy zvolena konstrukce podporovaná v daném operaˇcn´ım systému. Pˇri kompilaci jsou potˇreba kromˇe zdrojov´ ych soubor˚ u aplikace (TestAlgDFA.h, TestAlgDFA.cpp a MainProc.cpp) také hlaviˇckové soubory iostream, fstream, map, vector, deque, string, cstdlib, ctime, cmath, iomanip, stdexcept a fcntl.h. Kromˇe toho potˇrebujeme pod systémy MS Windows hlaviˇckové soubory io.h, sys/stat.h a process.h a pod systémy na bázi UNIXu hlaviˇckové soubory unistd.h a sys/wait.h. Pokud je nˇekter´ y z uveden´ ych soubor˚ u v jiném um´ıstˇen´ı, neˇz kompilátor oˇcekává, mus´ıme jej nahrát do adresáˇre se zdrojov´ ymi soubory aplikace nebo k nˇemu nˇejak´ ym zp˚ usobem zadat cestu. Hlavn´ı funkˇcnost aplikace obstarává funkce main“, která pouˇz´ıvá dalˇs´ı po” mocné fukce definované v souboru MainProc.cpp a tˇr´ıdu testovani“ deklarovanou ” v souboru TestAlgDFA.h a definovanou v souboru TestAlgDFA.cpp. Tato tˇr´ıda vyuˇz´ıvá dalˇs´ı pomocné struktury a funkce deklarované a definované ve stejn´ ych souborech jako ona sama. Funkce main“, tˇr´ıda testovani“ a dalˇs´ı zm´ınˇené funkce ” ” a struktury budou v následuj´ıc´ım textu podrobnˇe popsány. Funkce main“ nejprve pomoc´ı funkce nacti parametry“ naˇcte parametry ” ” zadané uˇzivatelem v souboru params.tadfa (tento soubor je popsán v uˇzivatelské dokumentaci) a inicializuje generátor náhodn´ ych ˇc´ısel bud’ náhodnˇe (podle ˇcasu funkc´ı time“) nebo ˇc´ıslem typu unsigned, které zadal uˇzivatel v souboru params.tadfa. ” Dále vytvoˇr´ı instanci tˇr´ıdy testovani“ a do n´ı uloˇz´ı poˇzadované automaty. Pokud ” jsou automaty náhodnˇe generovány, mohou b´ yt uloˇzeny do soubor˚ u. Pak jsou jeˇstˇe naˇcteny algoritmy ze souboru algors.tadfa (tento soubor je popsán v uˇzivatelské dokumentaci), alokuje se pamˇet’ pro parametry spuˇstˇen´ı tˇechto algoritm˚ u a m˚ uˇze zaˇc´ıt vlastn´ı testován´ı. 26

Testován´ı prob´ıhá pro kaˇzd´ y automat ve 4 sloˇzitostech trénovac´ıch dat a opakuje se vˇzdy tolikrát, kolikrát urˇcil uˇzivatel. Pro 1 automat v 1 opakován´ı jsou vˇzdy pro 1 sloˇzitost otestovány vˇsechny algoritmy na stejn´ ych trénovac´ıch datech, která jsou pro ten u ´ˇcel vygenerována ve vytvoˇrené instanci tˇr´ıdy testovani“, zvolenou tes” tovac´ı metodou. V´ ysledky jsou ukládány také ve vytvoˇrené instanci tˇr´ıdy testovani“, ” potom jsou normalizovány poˇctem opakován´ı a pˇrevedeny na procenta. Nakonec jsou vypsány v´ ystupy v uˇzivatelem zvolen´ ych formátech a je uvolnˇena pamˇet’ alokovaná pro parametry algoritm˚ u. Funkce main“ vyuˇz´ıvá tyto pomocné funkce: ” • nacti parametry“ ” Naˇc´ıtá parametry zadané do souboru params.tadfa uˇzivatelem a vrac´ı je ve sv´ ych parametrech. • nacti algoritmy“ ” Naˇc´ıtá algoritmy zadané do souboru algors.tadfa uˇzivatelem a vrac´ı je ve svém parametru. • preved na argv“ ” Pˇrevede zadané parametry algoritm˚ u na char** pro spuˇstˇen´ı algoritm˚ u. • nazev data“ ” Vytvoˇr´ı název souboru pro trénovac´ı nebo testovac´ı data. • uloz data“ ” Uloˇz´ı trénovac´ı a testovac´ı data do zadan´ ych soubor˚ u. • nazev aut“ ” Vytvoˇr´ı název souboru pro automat od algoritmu regulárn´ı inference. • nazev gen“ ” Vytvoˇr´ı název souboru pro automat z generátoru. • vystup“ ” Obstarává u ´pravu jmen soubor˚ u s grafy a volán´ı vykreslen´ı graf˚ u. Grafy se vykresluj´ı pro kaˇzd´ y algoritmus (srovnán´ı automat˚ u) nebo pro kaˇzd´ y automat (srovnán´ı algoritm˚ u). Tˇr´ıda testovani“ uchovává c´ılové automaty, automaty od algoritmu, trénovac´ı ” i testovac´ı data a v´ ysledky testován´ı. Pouˇz´ıvá k tomu struktury stav“ pro uloˇzen´ı ” stavu automatu, DFA“ pro uloˇzen´ı automatu, vzorek“ pro uloˇzen´ı vzorku dat, ” ” TTD“ pro uloˇzen´ı trénovac´ıch nebo testovac´ıch dat a algoritmy“ pro uloˇzen´ı tes” ” tovan´ ych algoritm˚ u a jejich parametr˚ u. Zároveˇ n poskytuje funkce pro práci s tˇemito daty. Nejd˚ uleˇzitˇejˇs´ı z nich si pop´ıˇseme (v´ yznam ostatn´ıch je zˇrejm´ y z komentáˇr˚ u): • gen data“ ” Generuje trénovac´ı a testovac´ı data. Vyuˇz´ıvá k tomu funkce generuj nahod” ne“, generuj napul“, vzorek rovnomerne“, vzorek nahodne“, vrat label“, ” ” ” ” zkontroluj“, je napul“ a kompletni“. Kontrola strukturáln´ı kompletnosti je ” ” ” 27

omezena na 1000 opakován´ı, protoˇze jinak by tato operace také nemusela nikdy skonˇcit napˇr. v pˇr´ıpadˇe, kdy pozitivn´ıch trénovac´ıch vzork˚ u je velmi málo. • run“ ” Spust´ı program s algoritmem regulárn´ı inference a pˇredá mu zadané parametry. • shoda trenovaci“ ” Metoda ovˇeˇren´ı konzistence automatu s trénovac´ımi daty. • shoda testovaci“ ” Metoda testován´ı schopnosti automatu klasifikovat testovac´ı data. • pocet stavu“ ” Metoda porovnán´ı poˇctu stav˚ u. • shoda mml“ ” Metoda porovnán´ı minimal message length. • vypis csv“ ” Vypisuje v´ ystup do formátu csv. • vypis tex“ ” Vypisuje v´ ystup jako tabulku do formátu tex. • vypis graf“ ” Vypisuje graf (png, gif nebo jpg). Vyuˇz´ıvá k tomu funkce dat gen“, dat alg“, ” ” dat aut“, graf“, horni mez“ a spust graf“. ” ” ” ” • generuj DFA“ ” Vygeneruje koneˇcn´ y automat se zadan´ ym poˇctem stav˚ u. Vyuˇz´ıvá k tomu funkce vytvor graf“, najdi podgraf“, prejmenuj stavy“, hloubka“ a vytvor au” ” ” ” ” tomat“. • mml“ ” Spoˇc´ıtá minimal message length pro zadan´ y automat. Vyuˇz´ıvá k tomu funkce pocet odchodu“ a log2fakt“. ” ” Souˇcást´ı aplikace je rovnˇeˇz nˇekolik algoritm˚ u regulárn´ı inference, které byly staˇzeny z [2]. Protoˇze algoritmy z tohoto odkazu chod´ı jen pod systémy na bázi UNIXu, byly v rámci práce upraveny také pro systémy MS Windows. Potˇrebné u ´pravy vˇzdy popisuje soubor readme.txt um´ıstˇen´ y v adresáˇri s dan´ ym algoritmem. Jednou z nejd˚ uleˇzitˇejˇs´ıch u ´prav je nahrazen´ı hlaviˇckového souboru sys/time.h souborem timeval.h, kter´ y byl staˇzen z [14]. Algoritmy se jmenuj´ı red-blue, rlb a traxbar. Algoritmus traxbar v nˇekter´ ych pˇr´ıpadech vrac´ı m´ısto ˇc´ısla stavu znak ’ ?’. Pˇri naˇc´ıtán´ı automatu pak nastane chyba vstupu, protoˇze pˇri vstupn´ıch operac´ıch prob´ıhá kontrola datov´ ych typ˚ u (nebo obecnˇe korektnosti vstupn´ıho proudu) pomoc´ı funkce kontrola“. Chybové hláˇsky jsou vypisovány funkc´ı chyba“ a zároveˇ n je pro” ” gram ukonˇcen s kódem 1. Touto funkc´ı jsou tedy oˇsetˇrovány chyby, které zamezuj´ı dalˇs´ımu korektn´ımu bˇehu aplikace. 28

Literatura [1] Abbadingo One: DFA Learning Competition - DFAs: Languages and Learning [online], citováno 24.06.2008, url: http://abbadingo.cs.unm.edu/dfa.html. [2] Abbadingo One: DFA Learning Competition - 4 DFA learning algorithms download [on-line], citováno 24.06.2008, url: http://abbadingo.cs.may.ie/~lang/dfaalgorithms.tar.gz. [3] Carrasco R. C., Oncina J.: Learning stochastic regular grammar by means of a state merging method, Grammatical Inference and Applications (ICGI’94), Springer, Berlin, Heidelberg, 1994, 139–152. [4] Chytil M.: Automaty a gramatiky, SNTL, Praha, 1984, 18–96. [5] Dupont P.: Regular grammatical inference from positive and negative samples by genetic search: the GIG method, Grammatical Inference and Applications (ICGI’94), Springer, Berlin, Heidelberg, 1994, 236–245. [6] Dupont P., Miclet L., Vidal E.: What is the search space of the regular inference?, Grammatical Inference and Applications (ICGI’94), Springer, Berlin, Heidelberg, 1994, 25–37. [7] Gnuplot download - stránka pro staˇzen´ı gnuplotu [on-line], citováno 13.07.2008, url: http://www.gnuplot.info/download.html. [8] Gold E. M.: Complexity of Automaton Identification from Given Data, Information and Control 37, 1978, 302–320. [9] Hingston P.: A genetic algorithm for regular inference, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), Morgan Kaufmann, San Francisco, 2001, 1299–1306. [10] Hoffmann P.: Improving RPNI Algorithm Using Minimal Message Length, Artificial Intelligence and Applications, Innsbruck, 2007, 378–383. [11] Lang K. J., Pearlmutter B. A., Price R. A.: Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm, Lecture Notes in Computer Science 1433, 1998, 1–12. [12] Oncina J., Garcia P.: Inferring regular languages in polynomial update time, Pattern Recognition and Image Analysis, World Scientific, 1992, 49–61. 29

[13] Trakhtenbrot B., Barzdin Y.: Finite Automata: Behavior and Synthesis, North Holland Publication Company, Amsterdam, 1973. [14] Yongwei, Wu: Hlaviˇckový soubor timeval.h [on-line], citováno 13.07.2008, url: http://www.geocities.com/yongweiwu/timeval.h.txt.

30

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

Recommend Documents