Univerzita Karlova v Praze Matematicko-fyzik´aln´ı 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´aˇrsk´e pr´ace: RNDr. Petr Hoffmann Studijn´ı program: Informatika, programov´an´ı
2008
Dˇekuji pˇredevˇs´ım sv´emu vedouc´ımu RNDr. Petru Hoffmannovi za ochotu a trpˇelivost, s jakou mi odpov´ıdal na m´e dotazy, za pˇripom´ınky, rady a n´amˇety vedouc´ı ke zlepˇsen´ı kvality pr´ace, za ˇcas str´aven´ y konzultacemi se mnou a celkovou pomoc pˇri psan´ı t´eto pr´ace. D´ale 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´ace nedostala svou nynˇejˇs´ı podobu.
Prohlaˇsuji, ˇze jsem svou bakal´aˇrskou pr´aci napsal samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. Souhlas´ım se zap˚ ujˇcov´an´ım pr´ace a jej´ım zveˇrejˇ nov´an´ım.
V Praze dne 28.7.2008
Jan Vyˇsohl´ıd
2
Obsah ´ 1 Uvod 1.1 Charakteristika pr´ace . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Struˇcn´ y popis kapitol . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 5 7
2 Z´ akladn´ı teorie 2.1 Koneˇcn´e automaty . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Regul´arn´ı inference . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 10
3 Testov´ an´ı algoritm˚ u 3.1 Testovac´ı metody . . . . . 3.2 Abbadingo form´aty . . . . 3.3 Tr´enovac´ı a testovac´ı data 3.4 Pr˚ ubˇeh testov´an´ı . . . . .
12 12 14 15 16
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4 Z´ avˇ er 18 4.1 Zhodnocen´ı pr´ace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Moˇzn´a vylepˇsen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 A Uˇ zivatelsk´ a dokumentace 20 A.1 Popis pr´ace s aplikac´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 A.2 Pˇr´ıklad testov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 B Program´ atorsk´ a dokumentace
26
Literatura
29
3
N´azev pr´ace: Prostˇred´ı pro testov´an´ı algoritm˚ u pro uˇcen´ı automat˚ u Autor: Jan Vyˇsohl´ıd Katedra (´ ustav): Kabinet software a v´ yuky informatiky Vedouc´ı bakal´aˇrsk´e pr´ace: RNDr. Petr Hoffmann E-mail vedouc´ıho:
[email protected] Abstrakt: V pˇredloˇzen´e pr´aci studujeme metody pro testov´an´ı algoritm˚ u regul´arn´ı inference. Nejprve jsou uvedeny nˇekter´e teoretick´e poznatky z oblasti koneˇcn´ ych automat˚ u a regul´arn´ı inference. D´ale jsou pˇredstaveny nˇekter´e algoritmy pro uˇcen´ı koneˇcn´ ych automat˚ u, jejich principy a pouˇzit´e testovac´ı metody, jeˇz zjiˇst’uj´ı kvalitu algoritm˚ u testov´an´ım v´ ysledn´ ych automat˚ u. V dalˇs´ım textu je pak vysvˇetlen zp˚ usob generov´an´ı tr´enovac´ıch a testovac´ıch dat, pops´an form´at pro uloˇzen´ı tˇechto dat a pro uloˇzen´ı koneˇcn´ ych automat˚ u a nakonec tak´e samotn´ y pr˚ ubˇeh testov´an´ı algoritm˚ u. Souˇc´ast´ı pr´ace je rovnˇeˇz aplikace, kter´a uveden´e testovac´ı metody implementuje a v´ ysledn´e statistiky ukl´ad´a ve zvolen´em form´atu. V dodatc´ıch pˇrikl´ad´ame uˇzivatelskou a program´atorskou dokumentaci k t´eto aplikaci. Kl´ıˇcov´a slova: koneˇcn´ y automat, regul´arn´ı 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´ace je studovat a navrhnout metody pro testov´an´ı algoritm˚ u pro uˇcen´ı koneˇcn´ ych automat˚ u a navrˇzen´e postupy implementovat. Probl´em uˇcen´ı koneˇcn´ ych automat˚ u nen´ı jednoduch´ y a existuj´ı pro nˇej r˚ uzn´e zp˚ usoby zad´an´ı i postupy ˇreˇsen´ı. Tato pr´ace se bude zab´ yvat uˇcen´ım z tr´enovac´ıch dat. Algoritmy pro uˇcen´ı koneˇcn´ ych automat˚ u z tr´enovac´ıch dat se tak´e naz´ yvaj´ı algoritmy regul´arn´ı inference. Probl´em regul´arn´ı inference je velmi zaj´ımav´ y a uˇziteˇcn´ y. M´a nemal´ y teoretick´ y v´ yznam, ale tak´e ˇsirok´e spektrum aplikac´ı jako je napˇr. identifikace sekvenˇcn´ıch proces˚ u, rozpozn´av´an´ı vzor˚ u, zpracov´an´ı ˇreˇci a pˇrirozen´eho jazyka, exploratorn´ı sekvenˇcn´ı anal´ yza, umˇel´a inteligence nebo data mining. M´ame d´ana nˇejak´a data z jazyka, kter´ y nezn´ame. Z nich chceme z´ıskat automat, kter´ y pozitivn´ı pˇr´ıklady pˇrij´ım´a a negativn´ı pˇr´ıklady zam´ıt´a. Jin´ ymi slovy hled´ame automat konzistentn´ı s tˇemito daty. ˇ sen´ı tohoto probl´emu ale nen´ı jednoznaˇcn´e, jak je vidˇet na n´asleduj´ıc´ım pˇr´ıkladu. Reˇ Pˇr´ıklad dvou automat˚ u konzistentn´ıch se stejn´ ymi tr´enovac´ımi daty, kter´e m˚ uˇzeme oba povaˇzovat za ˇreˇsen´ı probl´emu regul´arn´ı inference, rozpozn´avaj´ıc´ıch r˚ uzn´e jazyky: Tr´enovac´ı data: pozitivn´ı pˇr´ıklady: {10, 101010} negativn´ı pˇr´ıklady: {100}
Automat 1:
5
Automat 2:
V ide´aln´ım pˇr´ıpadˇe by v´ ysledn´ y automat mˇel rozpozn´avat jazyk, z nˇehoˇz byla tr´enovac´ı data nagenerov´ana. Automat m˚ uˇze ale pˇrij´ımat napˇr. nadmnoˇzinu tohoto jazyka a pˇresto bude odpov´ıdat tr´enovac´ım dat˚ um. To znamen´a, ˇze existuje velk´e mnoˇzstv´ı automat˚ u, kter´e rozpozn´avaj´ı slova z tohoto jazyka a nev´ı se tedy, kter´ y konkr´etn´ı automat je nejlepˇs´ı a mˇel by b´ yt vybr´an jako v´ ysledn´ y. Moˇzn´ ym pˇr´ıstupem k ˇreˇsen´ı tohoto probl´emu 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´enˇe stav˚ u m˚ uˇzeme povaˇzovat za lepˇs´ı neˇz automat s v´ıce stavy. Automat s minim´aln´ım poˇctem stav˚ u mezi vˇsemi automaty rozpozn´avaj´ıc´ımi dan´ y jazyk je oznaˇcov´an jako mDFA a bude definov´an v pˇr´ıˇst´ı kapitole. Ovˇsem jak je uvedeno v [8], probl´em hled´an´ı mDFA konzistentn´ıho s tr´enovac´ımi daty je NP-´ upln´ y, proto se v praxi dle [5] hled´a tzv. optim´aln´ı automat, kter´ y se mDFA snaˇz´ı nˇejak´ ym zp˚ usobem pˇribl´ıˇzit. Protoˇze algoritm˚ u regul´arn´ı inference bylo vymyˇsleno pomˇernˇe hodnˇe a vznikaj´ı st´ale nov´e, bylo by uˇziteˇcn´e porovnat existuj´ıc´ı algoritmy i algoritmy novˇe navrˇzen´e a pr´avˇe to by mˇela umoˇznit pˇriloˇzen´a aplikace (d´ale jen aplikace). Tato aplikace implementuje zm´ınˇen´e testov´an´ı kvality algoritm˚ u regul´arn´ı inference pomoc´ı vybran´ ych statistick´ ych metod, kter´e se zamˇeˇruj´ı na r˚ uzn´a hlediska pˇribl´ıˇzen´ı uveden´emu c´ılov´emu automatu, podle nˇehoˇz byla generov´ana tr´enovac´ı a testovac´ı data. Testovan´ y algoritmus je dod´an v podobˇe extern´ıho programu, kter´emu aplikace pˇred´a nagenerovan´a tr´enovac´ı data v pevn´em form´atu a obdrˇz´ı od nˇej (deterministick´ y) koneˇcn´ y automat v pevn´em form´atu. Tyto form´aty budeme d´ale naz´ yvat Abbadingo form´at dat a Abbadingo form´at automatu, protoˇze byly pouˇzity v [1] a odtud jsou tak´e pˇrevzaty. Automat pak aplikace otestuje zvolenou statistickou metodou a vypoˇc´ıt´a statistick´e u ´daje, kter´e je moˇzn´e uloˇzit do souboru ve form´atu vhodn´em pro vloˇzen´ı do publikac´ı (napˇr. obr´azek ˇci LaTeXov´ y k´od). Souˇc´ast´ı aplikace je tak´e nˇekolik program˚ u s algoritmy regul´arn´ı inference staˇzen´ ych z [2], aby bylo moˇzn´e porovnat nov´e algoritmy regul´arn´ı inference se schopn´ ymi a vyzkouˇsen´ ymi. Protoˇze tyto algoritmy byly k dispozici pouze pro UNIXov´e syst´emy, jsou v r´amci pr´ace upraveny tak´e pro MS Windows. Pr´ace je urˇcena pˇredevˇs´ım vˇedeck´ ym pracovn´ık˚ um vyv´ıjej´ıc´ım algoritmy regul´arn´ı inference, kteˇr´ı potˇrebuj´ı otestovat sv´e postupy r˚ uzn´ ymi statistick´ ymi metodami nebo je prezentovat v publikac´ıch. D´ale jistˇe bude uˇziteˇcn´a tˇem, kteˇr´ı vyuˇz´ıvaj´ı algoritmy regul´arn´ı inference, aby si pro sv´e u ´ˇcely mohli vybrat vhodn´ y algoritmus na z´akladˇe srovn´an´ı pomoc´ı pˇriloˇzen´e aplikace. Byla ale naps´ana pro vˇsechny, kteˇr´ı 6
se o zpracovanou problematiku zaj´ımaj´ı nebo si chtˇej´ı jen zkusit otestovat kvalitu nˇekter´eho z algoritm˚ u. Jak je pops´ano v kapitole 4, aplikaci lze snadno rozˇs´ıˇrit napˇr. o dalˇs´ı testovac´ı metody, zp˚ usoby generov´an´ı dat nebo ji upravit pro vlastn´ı specifick´e u ´ˇcely pouˇzit´ı.
1.2
Struˇ cn´ y popis kapitol
Kapitola 2 seznamuje se z´akladn´ımi definicemi a vˇetami z oblasti koneˇcn´ ych automat˚ u a regul´arn´ı inference a s principy algoritm˚ u regul´arn´ı inference. V kapitole 3 jsou pops´any zvolen´e statistick´e metody pro testov´an´ı jejich kvality, Abbadingo form´aty tr´enovac´ıch a testovac´ıch dat a automatu a nakonec samotn´ y pr˚ ubˇeh testov´an´ı. Kapitola 4 shrnuje a hodnot´ı z´ıskan´e poznatky. Dodatky A a B obsahuj´ı uˇzivatelskou a program´atorskou dokumentaci k n´astroji, kter´ y implementuje popsan´e testovac´ı metody. Na z´avˇer pr´ace je pˇriloˇzen seznam pouˇzit´e literatury.
7
Kapitola 2 Z´ akladn´ı teorie Tato kapitola seznamuje se z´akladn´ımi definicemi a vˇetami z oblasti koneˇcn´ ych automat˚ u a regul´arn´ı inference a s principy algoritm˚ u regul´arn´ı inference.
2.1
Koneˇ cn´ e automaty
Tato podkapitola pod´av´a z´akladn´ı 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´yv´ ame ji abeceda), pak + Σ oznaˇcuje mnoˇzinu vˇsech koneˇcn´ych nepr´ azdn´ych posloupnost´ı utvoˇren´ych z prvk˚ u ∗ + mnoˇziny Σ, λ oznaˇcuje pr´azdnou posloupnost a definujeme Σ = Σ ∪ {λ}. Prvky Σ∗ se naz´yvaj´ı ˇ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´yv´ ame jazykem nad abecedou Σ. K popisu jazyk˚ u pouˇz´ıv´ame automaty. Ty m˚ uˇzeme uspoˇr´adat podle jejich vyjadˇrovac´ı s´ıly. Toto uspoˇr´ad´an´ı se naz´ yv´a Chomsk´eho hierarchie. Koneˇcn´e automaty jsou v tomto uspoˇr´ad´an´ı nejn´ıˇze a maj´ı tedy nejmenˇs´ı vyjadˇrovac´ı s´ılu. V n´asleduj´ıc´ım textu definujeme koneˇcn´ y automat, jazyk rozpozn´avan´ y koneˇcn´ ym automatem [4] a prefix tree acceptor [10]. Definice 2.1.4 Koneˇcn´ym automatem naz´yv´ ame kaˇzdou pˇetici A = (Q, Σ, δ, q0 , F ), kde Q je koneˇcn´a nepr´azdn´a mnoˇzina stav˚ u (stavov´y prostor), Σ je koneˇcn´ a nepr´azdn´ a mnoˇzina vstupn´ıch symbol˚ u (vstupn´ı abeceda), δ: Q×Σ → Q je pˇrechodov´ a funkce, q0 ∈ Q je poˇc´ateˇcn´ı stav a F ⊆ Q je mnoˇzina koncov´ych stav˚ u. Definice 2.1.5 Pro koneˇcn´y 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´e q ∈ Q, 2. δ ∗ (q, wa) = δ(δ ∗ (q, w), a) pro kaˇzd´e q ∈ Q, w ∈ Σ∗ , a ∈ Σ. Jazykem rozpozn´avan´ym koneˇcn´ym automatem A pak nazveme jazyk L(A) = {w | w ∈ Σ∗ & δ ∗ (q0 , w) ∈ F }. ˇ ık´ame, ˇ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´e mnoˇzinˇe ˇretˇezc˚ u je koneˇcn´y 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´a cesta z koˇrene do pˇrij´ımac´ıho stavu odpov´ıd´a ˇretˇezci z dan´e mnoˇziny I+ . D´ale 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´y koneˇcn´y automat pˇrij´ımaj´ıc´ı jazyk L. ˇ Definice 2.1.8 Rekneme, ˇze jazyk L je rozpoznateln´y koneˇcn´ym automatem, jestliˇze existuje koneˇcn´y automat A takov´y, ˇze L = L(A). Existuj´ı r˚ uzn´e zp˚ usoby, kter´ ymi m˚ uˇzeme jazyky rozpozn´avan´e koneˇcn´ ymi automaty charakterizovat. Jedn´ım z nich jsou regul´arn´ı 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´arn´ımi jazyky a koneˇcn´ ymi automaty je d´an vˇetou n´ıˇze [4]. Vˇ eta 2.1.10 (Kleene) Libovoln´y jazyk je regul´ arn´ı, pr´ avˇe kdyˇz je rozpoznateln´y koneˇcn´ym automatem. Dalˇs´ım zp˚ usobem charakterizace jazyk˚ u rozpozn´avan´ ych koneˇcn´ ymi automaty jsou regul´arn´ı v´ yrazy [4]. Definice 2.1.11 Mnoˇzinu RV(Σ) regul´ arn´ıch v´yraz˚ 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´e a ∈ Σ. 2. α, β ∈ RV(Σ) ⇒ (α + β) ∈ RV(Σ), (α . β) ∈ RV(Σ), (α)∗ ∈ RV(Σ). Vztah mezi regul´arn´ımi jazyky a regul´arn´ımi v´ yrazy vyjadˇruje definice n´ıˇze [4]. Definice 2.1.12 Kaˇzd´y z regul´ arn´ıch v´yraz˚ u oznaˇcuje jist´y regul´ arn´ı jazyk. V´yraz ø oznaˇcuje pr´azdn´y jazyk, v´yraz λ oznaˇcuje jazyk {λ}, pro a ∈ Σ oznaˇcuje v´yraz a jazyk {a}. Jestliˇze α, β jsou v´yrazy 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´akladn´ı definice z oblasti regul´arn´ı inference a seznamuje s principy algoritm˚ u regul´arn´ı inference. Nejprve je potˇreba vˇedˇet, jak vypadaj´ı tr´enovac´ı data, z nichˇz bude uˇcen´ı automat˚ u prob´ıhat a co je vlastnˇe uˇcen´ı a regul´arn´ı inference [6]. Definice 2.2.1 Tr´enovac´ımi daty pro jazyk L nazveme I = I+ ∪I− mnoˇzinu pˇr´ıklad˚ u sest´avaj´ıc´ı z pozitivn´ıho vzorku I+ , tzn. koneˇcn´e podmnoˇziny z jazyka L, a negativn´ıho vzorku I− , tzn. koneˇcn´e mnoˇziny slov nen´ aleˇzej´ıc´ıch do jazyka L (neboli koneˇcn´e podmnoˇziny doplˇ nku jazyka L). Mnoˇzina I− m˚ uˇze b´yt v nˇekter´ych pˇr´ıpadech pr´ azdn´a. Definice 2.2.2 Necht’ I+ a I− jsou disjunktn´ı podmnoˇziny mnoˇziny Σ∗ , kter´e oznaˇcuj´ı pozitivn´ı a negativn´ı uˇc´ıc´ı vzorky inferenˇcn´ıho algoritmu a I = I+ ∪ I− . Uˇcen´ım naz´yv´ame proces hled´an´ı koneˇcn´eho automatu A takov´eho, ˇze vzorky z mnoˇziny I+ jsou pˇrij´ım´any automatem A a vzorky z mnoˇziny I− jsou automatem A zam´ıt´any. Regul´arn´ı inferenc´ı naz´yv´ame proces uˇcen´ı z tr´enovac´ıch dat I. Nˇekter´e algoritmy regul´arn´ı inference poˇzaduj´ı, aby mnoˇzina I+ byla tzv. struktur´alnˇe kompletn´ı [6]. Definice 2.2.3 Mnoˇzina pozitivn´ıch vzork˚ u I+ je naz´yv´ ana struktur´ alnˇe kompletn´ı vzhledem ke koneˇcn´emu automatu A, pokud existuj´ı pˇrij´ımaj´ıc´ı v´ypoˇcty pro slova z mnoˇziny I+ takov´e, ˇze plat´ı: 1. Kaˇzd´y pˇrechod A je pouˇzit nejm´enˇe jednou pˇri pˇrij´ım´ an´ı ˇretˇezc˚ u z I+ . 2. Kaˇzd´y prvek F (koncov´y stav) je pˇrij´ımac´ı alespoˇ n pro jeden ˇretˇezec z I+ . Pro probl´em regul´arn´ı inference definovan´e v´ yˇse existuje hodnˇe ˇreˇsen´ı. My z nich chceme vybrat pouze jedno, kter´e by n´am nejv´ıce vyhovovalo. Jednou z moˇznost´ı, kter´a byla jiˇz okomentov´ana v u ´vodu pr´ace, je hledat co nejmenˇs´ı v´ ysledn´ y automat co do poˇctu stav˚ u. N´asleduje formalizace t´eto 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´y automat A je ˇreˇsen´ım probl´emu regul´ arn´ı inference, pokud jsou splnˇeny n´ asleduj´ıc´ı podm´ınky: 1. I+ je struktur´alnˇe kompletn´ı vzhledem k A. 2. I− ⊆ Σ∗ − L(A). 3. A je automat s nejmenˇs´ım poˇctem stav˚ u, kter´y 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´em hled´an´ı mDFA konzistentn´ıho s tr´enovac´ımi daty je NP-´ upln´ y, proto se v praxi dle [5] hled´a tzv. optim´aln´ı automat, kter´ y se mDFA snaˇz´ı nˇejak´ ym zp˚ usobem pˇribl´ıˇzit. Pr´avˇe testov´an´ım tohoto optim´aln´ıho automatu zjiˇst’ujeme kvalitu uˇc´ıc´ıho algoritmu podle r˚ uzn´ ych krit´eri´ı volbou vhodn´e testovac´ı metody. Tato krit´eria jsou pops´ana spolu s testovac´ımi metodami v dalˇs´ı kapitole. Dalˇs´ı text popisuje dˇelen´ı a principy algoritm˚ u regul´arn´ı inference s jejich konkr´etn´ımi pˇr´ıklady a je zpracov´an podle [9]. Algoritmy regul´arn´ı inference m˚ uˇzeme rozdˇelit do nˇekolika skupin. Prvn´ı velkou skupinou jsou algoritmy, kter´e zaˇc´ınaj´ı s PTA pro zadan´e I+ a sluˇcuj´ı stavy za u ´ˇcelem z´ısk´an´ı 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´an´ı 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´em pˇr´ıpadˇe k tomu pouˇz´ıv´a pr´avˇe negativn´ı vzorky. Do druh´e velk´e skupiny patˇr´ı genetick´e algoritmy nebo jin´e algoritmy zaloˇzen´e 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´eto kapitole jsou pops´any zvolen´e statistick´e metody pro testov´an´ı jejich kvality, Abbadingo form´aty tr´enovac´ıch a testovac´ıch dat a automatu a nakonec samotn´ y pr˚ ubˇeh testov´an´ı.
3.1
Testovac´ı metody
V t´eto podkapitole jsou uvedeny testovac´ı metody, kter´e provˇeˇruj´ı kvality algoritm˚ u regul´arn´ı inference podle r˚ uzn´ ych hledisek, pouˇzit´e v aplikaci. Vˇsechny metody maj´ı nˇekolik spoleˇcn´ ych rys˚ u, kter´e je vhodn´e u ´vodem popsat. Do v´ ystupn´ıho souboru se statistikami je do tabulky vypisov´ana pr˚ umˇern´a respektive minim´aln´ı/pr˚ umˇern´a/maxim´aln´ı procentu´aln´ı u ´spˇeˇsnost testov´an´ı pro danou metodu a zadan´ y poˇcet pokus˚ u nebo je jako v´ ystup vykreslen graf. Tyto v´ ystupy lze tak´e vz´ajemnˇe kombinovat. D´ıky opakov´an´ı testov´an´ı 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´an´ı probˇehlo pouze jednou. Genetick´e (evoluˇcn´ı) algoritmy jsou obecnˇe nedeterministick´e, proto se pˇri testov´an´ı pouˇzije vˇzdy pr˚ umˇer z 10 bˇeh˚ u algoritmu. Tento poˇcet bˇeh˚ u byl pro testov´an´ı zvolen podle [5]. V n´asleduj´ıc´ım seznamu budou jednotliv´e metody pops´any spolu s vysvˇetlen´ım jejich vyuˇzit´ı: 1. Metoda ovˇ eˇ ren´ı konzistence automatu s tr´ enovac´ımi daty. Pouˇz´ıv´a k tomu stejn´a tr´enovac´ı data, jak´a byla pˇred´ana programu s algoritmem. I kdyˇz se toto testov´an´ı m˚ uˇze na prvn´ı pohled zd´at nesmysln´e, protoˇze by napˇr. staˇcilo, aby automat pˇrij´ımal jazyk sest´avaj´ıc´ı pr´avˇe z pozitivn´ıch vzork˚ u, poslouˇz´ı hlavnˇe v prvn´ıch f´az´ıch v´ yvoje programu, kdy si autor nen´ı jist jeho spr´avnost´ı. M˚ uˇze se tedy st´at, ˇze program dostane tr´enovac´ı data a na v´ ystup vyd´a automat, kter´ y s nimi nen´ı konzistentn´ı. 2. Metoda testov´ an´ı schopnosti automatu klasifikovat testovac´ı data. Ta jsou disjunktn´ı s tr´enovac´ımi daty a lze tedy pomoc´ı nich odhadnout, jak dobˇre automat zobecˇ nuje na nov´a data, kter´a pˇredt´ım jeˇstˇe nevidˇel, protoˇze nebyla obsaˇzena v tr´enovac´ıch datech.
12
3. Metoda Abbadingo podobn´a pˇredchoz´ı metodˇe je pˇrevzata z [11]. Pˇredchoz´ı metoda z n´ı dokonce vych´az´ı a je jej´ı obecnˇejˇs´ı variantou. Aˇckoli je metoda Abbadingo speci´aln´ım pˇr´ıpadem pˇredchoz´ı metody, je pˇresto velmi uˇziteˇcn´a a to proto, ˇze umoˇzn ˇuje jednoduˇse prov´est test pˇresnˇe podle soutˇeˇze Abbadingo [11]. Tato metoda tak´e testuje schopnost automatu klasifikovat testovac´ı data jako pˇredchoz´ı metoda, ale dˇel´a to pouze pro automaty s poˇcty stav˚ u 64, 128, 256 a 512, kter´e pracuj´ı s bin´arn´ı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´anku [11] se povaˇzuje probl´em za vyˇreˇsen´ y (automat od programu s algoritmem je dostateˇcnˇe kvalitn´ı), pokud je automatem spr´avnˇe klasifikov´ano v´ıce neˇz 99% testovac´ıch vzork˚ u. V aplikaci dost´av´ame m´ısto toho v´ ystup, kter´ y je pops´an v u ´vodu t´eto podkapitoly. Pouˇzit´e poˇcty tr´enovac´ıch dat v metodˇe Abbadingo pro vˇsechny kombinace poˇctu stav˚ u a sloˇzitosti jsou uvedeny v Tabulce 1, kter´a je pˇrevzata podle Tabulky 1 z ˇcl´anku [11]. Jak pˇresnˇe metoda pracuje je pops´ano v uˇzivatelsk´e dokumentaci v dodatku a uk´az´ano 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´enovac´ı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´avˇe tato metoda testuje pˇribl´ıˇzen´ı mDFA z hlediska poˇctu stav˚ u. Procentu´aln´ı u ´spˇeˇsnost t´eto metody ale m˚ uˇze b´ yt i vˇetˇs´ı neˇz 100%, protoˇze jednak automat, z nˇehoˇz byla generov´ana tr´enovac´ı data nemusel b´ yt mDFA pro dan´ y jazyk a nav´ıc z˚ ust´av´a pˇri testov´an´ı touto metodou ot´azkou, zda automat od programu pˇrij´ım´a stejn´ y jazyk jako zadan´ y ˇci vygenerovan´ y automat. Je tedy dobr´e tuto metodu kombinovat s metodou testov´an´ı 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´ana 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´eho v [9], kde M je poˇcet vˇsech pˇrechod˚ u, N poˇcet stav˚ u, V velikost abecedy zv´ yˇsen´a o 1, tj poˇcet odchod˚ u ze stavu j pˇri proch´azen´ı tr´enovac´ıch dat a nij poˇcet odchod˚ u ze stavu j symbolem i pˇri proch´azen´ı tr´enovac´ıch dat. Vypoˇc´ıtan´e MML jsou porovn´any 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´eho automatu. MML zjednoduˇsenˇe ˇreˇceno urˇcuje, jak dlouh´a zpr´ava by byla potˇreba, aby byla co nejkratˇs´ı a z´aroveˇ n dok´azala pˇr´ıjemci popsat automat i tr´enovac´ı data zak´odovan´a pomoc´ı automatu tak, aby je podle n´ı umˇel zrekonstruovat.
3.2
Abbadingo form´ aty
V t´eto podkapitole jsou pops´any Abbadingo form´aty tr´enovac´ıch a testovac´ıch dat a automatu i s konkr´etn´ımi pˇr´ıklady podle [1]. Abbadingo form´at tr´enovac´ıch a testovac´ıch dat m´a v hlaviˇcce uveden poˇcet ˇretˇezc˚ u, z nichˇz se data skl´adaj´ı 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´adk˚ u pˇredstavuje jeden pˇr´ıklad. Skl´ad´a se z informace o tom, zda je pozitivn´ı (1), negativn´ı (0) nebo nen´ı zn´amo, zda jej automat pˇrij´ım´a, tedy jedn´a se o testovac´ı data (-1). N´asleduj´ı d´elky ˇretˇezce a symboly ˇretˇezce oddˇelen´e b´ıl´ ymi znaky. D´elka ˇretˇezce je rovna poˇctu symbol˚ u. Pˇr´ıklad Abbadingo form´atu tr´enovac´ı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´atu 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´at 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´adek reprezentuje jeden stav. Postupnˇe obsahuje nez´aporn´e cel´e ˇc´ıslo stavu, informaci o tom, zda je stav koncov´ y a pro kaˇzd´ y symbol z abecedy (nez´aporn´e cel´e ˇ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´atu 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´eto podkapitole je podrobnˇe vysvˇetlen zp˚ usob generov´an´ı tr´enovac´ıch a testovac´ıch dat. Aplikace generuje zadan´ y poˇcet tr´enovac´ıch dat obsahuj´ıc´ıch pozitivn´ı i negativn´ı vzorky, kter´e se mohou opakovat. Pokud bychom tedy chtˇeli testovat algoritmus, kter´ y negativn´ı vzorky nepotˇrebuje, mus´ı se umˇet vypoˇr´adat 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´enovac´ıch datech, tedy mnoˇziny tr´enovac´ıch a testovac´ıch dat mus´ı b´ yt disjunktn´ı. Jejich poˇcet tak´e zad´av´a uˇzivatel. Pˇri generov´an´ı tr´enovac´ıch a testovac´ıch dat lze zvolit, zda tr´enovac´ı data obsahuj´ı pozitivn´ı a negativn´ı vzorky n´ahodnˇe nebo je polovina tr´enovac´ı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´a t´emˇ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´arn´ı 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´e m˚ uˇze pˇrij´ımat u ´plnˇe vˇsechna slova nad danou abecedou, potom by neexistoval ˇz´adn´ y negativn´ı vzorek. V aplikaci se proto po nalezen´ı dostateˇcn´eho poˇctu pozitivn´ıch vzork˚ u pˇri generov´an´ı dat na poloviny omezuje poˇcet pokus˚ u hled´an´ı negativn´ıch vzork˚ u na 1000, po dosaˇzen´ı tohoto limitu je vyps´ana chyba a ukonˇcen bˇeh aplikace. Stejn´ y limit je nastaven pro hled´an´ı pozitivn´ıch vzork˚ u po nalezen´ı dostateˇcn´eho poˇctu negativn´ıch vzork˚ u, kdyby automat nepˇrij´ımal ˇz´adn´a nebo t´emˇeˇr ˇz´adn´a slova. D´ale se liˇs´ı zp˚ usob generov´an´ı dat: • Pokud se jedn´a o bin´arn´ı vzorky, m˚ uˇze uˇzivatel vybrat metodu, kter´a bere data n´ahodnˇe z mnoˇziny 16n2 − 1 vzork˚ u stejnˇe jako v [11], kde n je poˇcet stav˚ u c´ılov´eho automatu. Jejich d´elky 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´emu zm´ınˇen´em na konci pˇredchoz´ıho bodu, dalˇs´ı metoda nejprve vybere d´elku vzorku a pak generuje symboly, dokud nedostane vzorek t´eto d´elky. Vˇsechny d´elky tedy maj´ı stejnou pravdˇepodobnost a nav´ıc lze pouˇz´ıt i jin´e neˇz bin´arn´ı 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´enovac´ı i testovac´ı data druh´a mocnina poˇctu stav˚ u automatu normalizovan´a poˇzadovanou sloˇzitost´ı dat. Pokud aplikace testuje algoritmy tˇret´ı metodou popsanou v pˇredchoz´ı kapitole, jsou speci´alnˇe definov´any poˇzadovan´e poˇcty tr´enovac´ıch a testovac´ıch dat dle [11] (viz Tabulka 1).
3.4
Pr˚ ubˇ eh testov´ an´ı
Tato podkapitola popisuje postupy pˇriloˇzen´e aplikace implementuj´ıc´ı testov´an´ı algoritm˚ u regul´arn´ı inference. Aplikace umoˇzn ˇuje zadat na vstup automaty, na nichˇz m´a prob´ıhat testov´an´ı, tˇremi zp˚ usoby: 1. vygenerovat n´ahodn´e automaty, z nichˇz prvn´ı m´a n stav˚ u a kaˇzd´ y dalˇs´ı m´a o 4 stavy v´ıce (kde n je dˇeliteln´e 4 a urˇcuje jej uˇzivatel stejnˇe jako poˇcet automat˚ u) nebo n´ahodn´e automaty pro testov´an´ı metodou Abbadingo z podkapitoly 3.1, 16
kter´e maj´ı na rozd´ıl od pˇredchoz´ıch pˇredem dan´e poˇcty stav˚ u na 64, 128, 256 a 512 a mohou tedy b´ yt maxim´alnˇe 4 (viz Tabulka 1), 2. naˇc´ıst automaty ze vstupn´ıho souboru pevn´eho form´atu od uˇzivatele, 3. naˇc´ıst automaty pro Tomitovy jazyky, kter´e jsou vyps´any v Tabulce 2 zpracovan´e podle [9] (poˇcty stav˚ u jsou upraveny kv˚ uli pouˇzit´ı Abbadingo form´atu automatu pro bin´arn´ı vzorky). Jazyk L1 L2 L3 L4 L5 L6 L7
Popis (regul´ arn´ı v´ yraz)
Poˇ cet stav˚ u 0* 2 (01)* 3 Nem´a lich´ y poˇcet 1 a potom lich´ y poˇcet 0 5 Maxim´alnˇe dvˇe po sobˇe n´asleduj´ı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´an´ı automat˚ u je pˇrevzato z [11], tedy aplikace nejprve vytvoˇr´ı orientovan´ y graf na 54 n vrchol˚ u stupnˇe 2, n´ahodnˇe vybere vrchol jako poˇc´ateˇcn´ı stav a vezme podgraf obsahuj´ıc´ı vrcholy dosaˇziteln´e z koˇrene. Pro kaˇzd´ y vrchol n´ahodnˇe urˇc´ı, zda se bude nebo nebude jednat o pˇrij´ımac´ı stav. Generov´an´ı se prov´ad´ı tak dlouho, dokud maxim´aln´ı hloubka v´ ysledn´eho grafu nen´ı pr´avˇe 2 log2 n − 2. V´ ysledkem popsan´eho postupu je automat pracuj´ıc´ı s bin´arn´ımi vzorky. Po vytvoˇren´ı automat˚ u si aplikace naˇcte informace o programech s algoritmy, kter´e m´a testovat. Pot´e si vezme jeden automat a opakovanˇe se nageneruj´ı tr´enovac´ı a testovac´ı data, na nichˇz se otestuj´ı vˇsechny algoritmy. Protoˇze testov´an´ı prob´ıh´a pro vˇsechny algoritmy na stejn´ ych datech, kontroluje se struktur´aln´ı kompletnost tr´enovac´ıch dat, pokud to poˇzaduje alespoˇ n jeden z testovan´ ych algoritm˚ u. Pokud skonˇc´ı testov´an´ı 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´atu, jenˇz si uˇzivatel vybere.
17
Kapitola 4 Z´ avˇ er 4.1
Zhodnocen´ı pr´ ace
Probl´em regul´arn´ı inference je velmi zaj´ımav´ y a uˇziteˇcn´ y. M´a nemal´ y teoretick´ y v´ yznam, ale tak´e ˇsirok´e spektrum aplikac´ı jako je napˇr. identifikace sekvenˇcn´ıch proces˚ u, rozpozn´av´an´ı vzor˚ u, zpracov´an´ı ˇreˇci a pˇrirozen´eho jazyka, exploratorn´ı sekvenˇcn´ı anal´ yza, umˇel´a inteligence nebo data mining. V aplikaci se podaˇrilo implementovat nˇekolik metod pro testov´an´ı algoritm˚ u regul´arn´ı inference a poskytnout tak vˇedeck´ ym pracovn´ık˚ um n´astroj k usnadnˇen´ı v´ yvoje tˇechto algoritm˚ u. Souˇc´ast´ı aplikace je tak´e nˇekolik program˚ u s algoritmy regul´arn´ı inference staˇzen´ ych z [2], aby bylo moˇzn´e porovnat nov´e algoritmy regul´arn´ı inference se schopn´ ymi a vyzkouˇsen´ ymi. Protoˇze tyto algoritmy byly k dispozici pouze pro UNIXov´e syst´emy, jsou v r´amci pr´ace upraveny tak´e pro MS Windows. Jako teoretick´ y podklad aplikace slouˇz´ı samotn´ y text t´eto pr´ace, jehoˇz souˇc´ast´ı 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´eto metody spoˇc´ıv´a v prezentaci schopnost´ı algoritmu zobecˇ novat na nov´a data. Zde vˇsak d´ale uˇzivatel m˚ uˇze zvolit zp˚ usob generov´an´ı tr´enovac´ıch a testovac´ıch dat. Zp˚ usob pouˇzit´ y v [11], kter´ ym je vybr´an 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´ahodnˇe vybr´ana d´elka vzorku a pak je teprve vygenerov´an samotn´ y vzorek t´eto d´elky. Celkov´ yu ´spˇech pr´ace uk´aˇ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´e pr´aci je st´ale co zlepˇsovat. Proto vznikla tato kapitola, aby dala prostor k publikaci n´apad˚ u, kter´e nebyly zrealizov´any. Urˇcitˇe existuje v´ıce zp˚ usob˚ u generov´an´ı tr´enovac´ıch a testovac´ıch dat. Bylo by moˇzno napˇr´ıklad nahl´ednout na tuto problematiku z hlediska toho, s jakou pravdˇepodobnost´ı se automat vyd´a po jedn´e nebo druh´e vˇetvi m´ısto pravdˇepodobnosti d´elky 18
vzorku nebo v´ ybˇeru vzorku z jejich dan´e mnoˇziny. Tyto metody totiˇz zp˚ usob´ı, ˇze pokud jsou d´elky libovoln´ ych vˇetv´ı automatu vych´azej´ıc´ıch ze stejn´eho stavu nerovnomˇern´e (na jedn´e z nich lze vygenerovat v´ıce vzork˚ u), pak m´a jedna vˇetev vˇetˇs´ı pravdˇepodobnost neˇz druh´a, ˇze se pˇri generov´an´ı dat automat vyd´a pr´avˇe po n´ı. To by ˇreˇsila metoda, kter´a by brala stejn´e pravdˇepodobnosti, ˇze se automat vyd´a po jedn´e vˇetvi (pokud je stav koncov´ y, mus´ıme to zapoˇc´ıtat jako dalˇs´ı vˇetev). Jistˇe by se tak´e daly zkoumat dalˇs´ı metody testov´an´ı algoritm˚ u regul´arn´ı inference a vymyslet t´ım dalˇs´ı hlediska pohledu na kvalitu automat˚ u, kter´e tyto algoritmy vyd´avaj´ı na v´ ystupu.
19
Dodatek A Uˇ zivatelsk´ a dokumentace A.1
Popis pr´ ace s aplikac´ı
Aplikace slouˇz´ı k testov´an´ı algoritm˚ u regul´arn´ı inference vybran´ ymi testovac´ımi metodami. Bliˇzˇs´ı popis najdeme v hlavn´ı ˇc´asti textu t´eto pr´ace. Aplikace se spouˇst´ı z pˇr´ıkazov´e ˇr´adky pˇr´ıkazem TestAlgDFA a komunikace s n´ı prob´ıh´a prostˇrednictv´ım textov´ ych konfiguraˇcn´ıch soubor˚ u (vzorov´e soubory najdeme na pˇriloˇzen´em CD). V´ ystupy se pak ukl´adaj´ı rovnˇeˇz do soubor˚ u. Nejprve si pop´ıˇseme vstupn´ı konfiguraˇcn´ı soubory, kter´e je potˇreba um´ıstit do pracovn´ıho adres´aˇre aplikace. V´ ystupn´ı soubory najdeme rovnˇeˇz v pracovn´ım adres´aˇri aplikace. Hlavn´ım konfiguraˇcn´ım souborem params.tadfa ˇr´ıd´ıme cel´ y pr˚ ubˇeh testov´an´ı. Jeho obsahem jsou hodnoty potˇrebn´ ych parametr˚ u napsan´e pod sebou. Pokud nˇejakou hodnotu nepotˇrebujeme, v˚ ubec se do souboru neuv´ad´ı. N´asleduj´ıc´ı seznam popisuje vˇsechny parametry, kter´e tento soubor obsahuje a jejich vz´ajemn´e z´avislosti (v´ yrazem Px znaˇc´ıme parametr x, kde x je ˇc´ıslo parametru v seznamu): 1. Inicializovat random gener´ator ruˇcnˇe (1 = ano, 0 = ne). Aplikace pouˇz´ıv´a gener´ator n´ahodn´ ych ˇc´ısel. Jeho ruˇcn´ı nastaven´ı na urˇcitou hodnotu m˚ uˇze b´ yt uˇziteˇcn´e napˇr. pokud hled´ame v programu s algoritmem regul´arn´ı inference nˇejakou chybu a potˇrebujeme jej nastavit opakovanˇe na stejnou hodnotu. 2. Druh automatu (1 = Tomitovy jazyky (v pracovn´ım adres´aˇri mus´ı b´ yt soubor tomita.tadfa), 2 = ze souboru od uˇzivatele, 3 = Abbadingo, n = z gener´atoru (n je poˇcet stav˚ u automatu dˇeliteln´ y 4)). 3. Poˇcet automat˚ u (pokud P2 = 1, 3, 4). Jm´eno souboru (pokud P2 = 2). 4. Poˇcet tr´enovac´ıch dat (uv´ad´ı se jen pro P2 = 1, 2, 4). Je potˇreba zadat rozumn´e mnoˇzstv´ı, protoˇze pokud zad´ame mnoho (v´ıce neˇz lze pro dan´ y automat vygenerovat), mohla by aplikace spotˇrebovat vˇsechny vzorky na generov´an´ı tr´enovac´ıch dat a v generov´an´ı testovac´ıch dat by nastala chyba (testovac´ı data obsahuj´ı pouze vzorky, kter´e nejsou v tr´enovac´ıch datech). Pokud naopak zad´ame pˇr´ıliˇs m´alo, m˚ uˇze b´ yt uˇcen´ı m´enˇe u ´spˇeˇsn´e. 5. Poˇcet testovac´ıch dat (uv´ad´ı se jen pro P2 = 1, 2, 4). 20
6. Stejn´e pravdˇepodobnosti d´elek vzork˚ u (1 = ano, 0 = ne, uv´ad´ı 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´enovac´ımi daty, 2 = schopnost automatu klasifikovat testovac´ı data, 3 = metoda Abbadingo, 4 = porovn´an´ı poˇctu stav˚ u, 5 = porovn´an´ı MML; uv´ad´ı se jen pro P2 = 1, 2, 4). 8. Generovat tr´enovac´ı data n´ahodnˇe (1 = ano, 0 = ne). Pokud je zvoleno 0, bude vygenerov´ana polovina pozitivn´ıch a polovina negativn´ıch vzork˚ u. 9. Poˇcet opakov´an´ı generov´an´ı dat pro automat. Jako v´ ysledek se pak bere pr˚ umˇer z tohoto poˇctu opakov´an´ı. 10. Jm´eno souboru pro uloˇzen´ı tr´enovac´ıch dat (pro P13 = 1 najdeme soubory pod n´azvy jm´eno automat opakov´an´ı sloˇzitost, kde vˇse kromˇe jm´ena jsou ˇc´ısla pˇr´ısluˇsn´e poloˇzky). 11. Jm´eno souboru pro uloˇzen´ı testovac´ıch dat (pro P13 = 1 najdeme soubory pod n´azvy jm´eno automat opakov´an´ı sloˇzitost, kde vˇse kromˇe jm´ena jsou ˇc´ısla pˇr´ısluˇsn´e poloˇzky). 12. Jm´eno souboru pro uloˇzen´ı automatu od programu s algoritmem (pro P14 = 1 najdeme soubory pod n´azvy jm´eno automat opakov´an´ı sloˇzitost algoritmus nedeterminismus, kde nedeterminismus je ˇc´ıslo od 1 do 10 pro nedeterministick´e algoritmy, jinak je vˇzdy rovno 1, vˇse ostatn´ı kromˇe jm´ena jsou ˇc´ısla pˇr´ısluˇsn´e poloˇzky). 13. Ukl´adat tr´enovac´ı a testovac´ı data (1 = ano, 0 = ne). 14. Ukl´adat automaty z gener´atoru (pokud se automaty generuj´ı) a od programu s algoritmem (1 = ano, 0 = ne). 15. Vypisovat v´ ystup do form´atu csv (1 = ano, 0 = ne). 16. Vypisovat v´ ystup jako tabulku do form´atu tex (1 = ano, 0 = ne). 17. Vypisovat pro kaˇzd´ y automat graf pro srovn´an´ı algoritm˚ u (1 = ano, 0 = ne). 18. Vypisovat pro kaˇzd´ y algoritmus graf pro srovn´an´ı automat˚ u (1 = ano, 0 = ne). 19. Poˇcet desetinn´ ych m´ıst pro v´ ypis procentu´aln´ıch u ´spˇeˇsnost´ı ve v´ ystupech. 20. Vypisovat na v´ ystup tak´e minima a maxima (1 = ano, 0 = ne). Pokud je P16 = 1, je maxim´aln´ı 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´atoru (uv´ad´ı se jen pro P1 = 1). 21. C´ 22. Jm´eno souboru pro v´ ystup do form´atu csv (uv´ad´ı se jen pro P15 = 1). 23. Jm´eno souboru pro v´ ystup do form´atu tex (uv´ad´ı se jen pro P16 = 1). 21
24. Jm´eno souboru pro graf s porovn´an´ım algoritm˚ u (uv´ad´ı se jen pro P17 = 1). 25. Jm´eno souboru pro graf s porovn´an´ım automat˚ u (uv´ad´ı se jen pro P18 = 1). 26. Form´at grafu (1 = png, 2 = gif, 3 = jpg; uv´ad´ı se jen pro P17 = 1 nebo P18 = 1). 27. N´asobek z´akladn´ı velikosti grafu 100 x 75 (uv´ad´ı se jen pro P17 = 1 nebo P18 = 1). 28. Cesta k souboru s gnuplotem (absolutn´ı ˇci relativn´ı; gnuplot\bin\pgnuplot znamen´a, ˇze v pracovn´ım adres´aˇri aplikace se nach´az´ı adres´aˇr gnuplot, v nˇem adres´aˇr bin a v nˇem soubor pgnuplot.exe pro spuˇstˇen´ı gnuplotu; uv´ad´ı se jen pro P17 = 1 nebo P18 = 1). Gnuplot je freeware (ke staˇzen´ı napˇr. na [7]). 29. Jm´eno souboru pro uloˇzen´ı automatu z gener´atoru (uv´ad´ı se jen pro P14 = 1, soubory najdeme pod n´azvy jm´eno automat opakov´an´ı sloˇzitost algoritmus nedeterminismus, kde nedeterminismus je ˇc´ıslo od 1 do 10 pro nedeterministick´e algoritmy, jinak je vˇzdy rovno 1, vˇse ostatn´ı kromˇe jm´ena jsou ˇc´ısla pˇr´ısluˇsn´e poloˇzky). D´ale je potˇreba do souboru algors.tadfa napsat informace o algoritmech, kter´e chceme testovat. Kaˇzd´ y ˇr´adek reprezentuje 1 algoritmus a obsahuje jm´eno programu s algoritmem (v MS Windows nen´ı potˇreba ud´avat pˇr´ıponu .exe), informaci o tom, zda je algoritmus deterministick´ y (1 = ano, 0 = ne), informaci o tom, zda algoritmus poˇzaduje struktur´aln´ı kompletnost tr´enovac´ı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´at velikost ok´enka). Pokud chceme testovat automaty zadan´e uˇzivatelem, je tˇreba vytvoˇrit soubor, jenˇz obsahuje na prvn´ım ˇr´adku poˇcet automat˚ u, d´ale n´asleduj´ı jednotliv´e automaty v Abbadingo form´atu automatu. Jm´eno tohoto souboru sdˇel´ıme aplikaci v konfiguraˇcn´ım souboru params.tadfa popsan´em v´ yˇse. K aplikaci jsou pˇriloˇzeny algoritmy red-blue, rlb a traxbar (podrobnˇeji je popisuje posledn´ı odstavec program´atorsk´e dokumentace). Kaˇzd´ y testovan´ y program s algoritmem uveden´ y v souboru algors.tadfa mus´ı b´ yt uloˇzen v pracovn´ım adres´aˇri s aplikac´ı v podobˇe spustiteln´eho souboru. V´ ystup do form´atu tex je reprezentov´an tabulkou, kde pro kaˇzd´ y algoritmus najdeme v´ ysledky ke vˇsem automat˚ um. Poˇcet ˇr´adk˚ u tabulky pro algoritmus se tedy rovn´a poˇctu automat˚ u a vypisov´any jsou pr˚ umˇern´e hodnoty. Pokud ale nav´ıc vypisujeme minima a maxima, u kaˇzd´eho automatu pˇribyde nad ˇr´adkem s pr˚ umˇery ˇr´adek s minimy a pod ˇr´adkem s pr˚ umˇery ˇr´adek 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´an´ı vˇsech algoritm˚ u nebo se bude vykreslovat soubor pro kaˇzd´ y algoritmus a bude vˇzdy obsahovat srovn´an´ı vˇsech automat˚ u. Srovn´an´ı je vyj´adˇreno procentu´aln´ı u ´spˇeˇsnost´ı pro 4 sloˇzitosti tr´enovac´ıch dat, kde horn´ı hranice grafu je volena podle nejvyˇsˇs´ı u ´spˇeˇsnosti, aby se dos´ahlo co moˇzn´a nejlepˇs´ı ˇcitelnosti. Je samozˇrejmˇe moˇzn´e grafy vykreslovat i pro minima a maxima a ne jen pro pr˚ umˇery, potom jm´eno souboru s grafem konˇc´ı min“ resp. max“. ” ” 22
A.2
Pˇ r´ıklad testov´ an´ı
N´asleduj´ıc´ı grafy (4 pro porovn´an´ı klasifikaˇcn´ıch schopnost´ı algoritm˚ u na automatech maj´ıc´ıch 64, 128, 256 a 512 stav˚ u, 2 pro zn´azornˇen´ı zmˇen klasifikaˇcn´ıch schopnost´ı algoritm˚ u s rostouc´ı velikost´ı automatu) a Tabulka 3 ukazuj´ı v´ ysledky re´aln´eho pˇr´ıkladu testov´an´ı metodou Abbadingo pro P1 = 0, P2 = 1, P8 = 1, P19 = 3, P20 = 0, P26 = 3 a P27 = 4. V tomto testov´an´ı byly pouˇzity programy s algoritmy red-blue a rlb. Pro rlb bylo zvoleno ok´enko velikosti 10. Toto testov´an´ı prob´ıh´a pˇresnˇe podle soutˇeˇze Abbadingo [11], ale d´ıky n´ahodn´emu generov´an´ı automat˚ u i dat a d´ıky jin´emu vyhodnocen´ı (v soutˇeˇzi Abbadingo se bere jako v´ ysledek procentu´aln´ı u ´spˇeˇsnost, kde se pokus povaˇzuje za u ´spˇeˇsn´ y, pokud je spr´avnˇe klasifikov´ano 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´an´ı, coˇz pro 1 opakov´an´ı d´av´a pr´avˇe v´ ysledek tohoto pokusu) se mohou v´ ysledky liˇsit. Z graf˚ u je vidˇet, ˇze pˇri zadan´em nastaven´ı algoritmus red-blue pˇrekon´av´a 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´eho testov´an´ı metodou Abbadingo.
25
Dodatek B Program´ atorsk´ a dokumentace Aplikace TestAlgDFA slouˇz´ıc´ı k testov´an´ı kvality algoritm˚ u regul´arn´ı inference je naps´ana v jazyce C++ pro syst´emy MS Windows (32-bit) a syst´emy na b´azi UNIXu. Zkompilov´ana a testov´ana 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´adrem 2.6.22.9-91.fc7 pod g++ (GCC) 4.1.2. Nˇekter´e konstrukce (napˇr. n´azvy funkc´ı) se mezi syst´emy MS Windows a syst´emy na b´azi UNIXu liˇs´ı, v hlaviˇckov´em souboru TestAlgDFA.h jsou proto definov´ana makra rozliˇsuj´ıc´ı mezi tˇemito syst´emy a podle nich je vˇzdy zvolena konstrukce podporovan´a v dan´em operaˇcn´ım syst´emu. Pˇri kompilaci jsou potˇreba kromˇe zdrojov´ ych soubor˚ u aplikace (TestAlgDFA.h, TestAlgDFA.cpp a MainProc.cpp) tak´e hlaviˇckov´e soubory iostream, fstream, map, vector, deque, string, cstdlib, ctime, cmath, iomanip, stdexcept a fcntl.h. Kromˇe toho potˇrebujeme pod syst´emy MS Windows hlaviˇckov´e soubory io.h, sys/stat.h a process.h a pod syst´emy na b´azi UNIXu hlaviˇckov´e soubory unistd.h a sys/wait.h. Pokud je nˇekter´ y z uveden´ ych soubor˚ u v jin´em um´ıstˇen´ı, neˇz kompil´ator oˇcek´av´a, mus´ıme jej nahr´at do adres´aˇre se zdrojov´ ymi soubory aplikace nebo k nˇemu nˇejak´ ym zp˚ usobem zadat cestu. Hlavn´ı funkˇcnost aplikace obstar´av´a funkce main“, kter´a pouˇz´ıv´a dalˇs´ı po” mocn´e fukce definovan´e 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´a dalˇs´ı pomocn´e struktury a funkce deklarovan´e a definovan´e ve stejn´ ych souborech jako ona sama. Funkce main“, tˇr´ıda testovani“ a dalˇs´ı zm´ınˇen´e funkce ” ” a struktury budou v n´asleduj´ıc´ım textu podrobnˇe pops´any. Funkce main“ nejprve pomoc´ı funkce nacti parametry“ naˇcte parametry ” ” zadan´e uˇzivatelem v souboru params.tadfa (tento soubor je pops´an v uˇzivatelsk´e dokumentaci) a inicializuje gener´ator n´ahodn´ ych ˇc´ısel bud’ n´ahodnˇe (podle ˇcasu funkc´ı time“) nebo ˇc´ıslem typu unsigned, kter´e zadal uˇzivatel v souboru params.tadfa. ” D´ale vytvoˇr´ı instanci tˇr´ıdy testovani“ a do n´ı uloˇz´ı poˇzadovan´e automaty. Pokud ” jsou automaty n´ahodnˇe generov´any, mohou b´ yt uloˇzeny do soubor˚ u. Pak jsou jeˇstˇe naˇcteny algoritmy ze souboru algors.tadfa (tento soubor je pops´an v uˇzivatelsk´e dokumentaci), alokuje se pamˇet’ pro parametry spuˇstˇen´ı tˇechto algoritm˚ u a m˚ uˇze zaˇc´ıt vlastn´ı testov´an´ı. 26
Testov´an´ı prob´ıh´a pro kaˇzd´ y automat ve 4 sloˇzitostech tr´enovac´ıch dat a opakuje se vˇzdy tolikr´at, kolikr´at urˇcil uˇzivatel. Pro 1 automat v 1 opakov´an´ı jsou vˇzdy pro 1 sloˇzitost otestov´any vˇsechny algoritmy na stejn´ ych tr´enovac´ıch datech, kter´a jsou pro ten u ´ˇcel vygenerov´ana ve vytvoˇren´e instanci tˇr´ıdy testovani“, zvolenou tes” tovac´ı metodou. V´ ysledky jsou ukl´ad´any tak´e ve vytvoˇren´e instanci tˇr´ıdy testovani“, ” potom jsou normalizov´any poˇctem opakov´an´ı a pˇrevedeny na procenta. Nakonec jsou vyps´any v´ ystupy v uˇzivatelem zvolen´ ych form´atech a je uvolnˇena pamˇet’ alokovan´a pro parametry algoritm˚ u. Funkce main“ vyuˇz´ıv´a tyto pomocn´e funkce: ” • nacti parametry“ ” Naˇc´ıt´a parametry zadan´e do souboru params.tadfa uˇzivatelem a vrac´ı je ve sv´ ych parametrech. • nacti algoritmy“ ” Naˇc´ıt´a algoritmy zadan´e do souboru algors.tadfa uˇzivatelem a vrac´ı je ve sv´em parametru. • preved na argv“ ” Pˇrevede zadan´e parametry algoritm˚ u na char** pro spuˇstˇen´ı algoritm˚ u. • nazev data“ ” Vytvoˇr´ı n´azev souboru pro tr´enovac´ı nebo testovac´ı data. • uloz data“ ” Uloˇz´ı tr´enovac´ı a testovac´ı data do zadan´ ych soubor˚ u. • nazev aut“ ” Vytvoˇr´ı n´azev souboru pro automat od algoritmu regul´arn´ı inference. • nazev gen“ ” Vytvoˇr´ı n´azev souboru pro automat z gener´atoru. • vystup“ ” Obstar´av´a u ´pravu jmen soubor˚ u s grafy a vol´an´ı vykreslen´ı graf˚ u. Grafy se vykresluj´ı pro kaˇzd´ y algoritmus (srovn´an´ı automat˚ u) nebo pro kaˇzd´ y automat (srovn´an´ı algoritm˚ u). Tˇr´ıda testovani“ uchov´av´a c´ılov´e automaty, automaty od algoritmu, tr´enovac´ı ” i testovac´ı data a v´ ysledky testov´an´ı. Pouˇz´ıv´a 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´enovac´ıch nebo testovac´ıch dat a algoritmy“ pro uloˇzen´ı tes” ” tovan´ ych algoritm˚ u a jejich parametr˚ u. Z´aroveˇ n poskytuje funkce pro pr´aci s tˇemito daty. Nejd˚ uleˇzitˇejˇs´ı z nich si pop´ıˇseme (v´ yznam ostatn´ıch je zˇrejm´ y z koment´aˇr˚ u): • gen data“ ” Generuje tr´enovac´ı a testovac´ı data. Vyuˇz´ıv´a k tomu funkce generuj nahod” ne“, generuj napul“, vzorek rovnomerne“, vzorek nahodne“, vrat label“, ” ” ” ” zkontroluj“, je napul“ a kompletni“. Kontrola struktur´aln´ı kompletnosti je ” ” ” 27
omezena na 1000 opakov´an´ı, protoˇze jinak by tato operace tak´e nemusela nikdy skonˇcit napˇr. v pˇr´ıpadˇe, kdy pozitivn´ıch tr´enovac´ıch vzork˚ u je velmi m´alo. • run“ ” Spust´ı program s algoritmem regul´arn´ı inference a pˇred´a mu zadan´e parametry. • shoda trenovaci“ ” Metoda ovˇeˇren´ı konzistence automatu s tr´enovac´ımi daty. • shoda testovaci“ ” Metoda testov´an´ı schopnosti automatu klasifikovat testovac´ı data. • pocet stavu“ ” Metoda porovn´an´ı poˇctu stav˚ u. • shoda mml“ ” Metoda porovn´an´ı minimal message length. • vypis csv“ ” Vypisuje v´ ystup do form´atu csv. • vypis tex“ ” Vypisuje v´ ystup jako tabulku do form´atu tex. • vypis graf“ ” Vypisuje graf (png, gif nebo jpg). Vyuˇz´ıv´a 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´a k tomu funkce vytvor graf“, najdi podgraf“, prejmenuj stavy“, hloubka“ a vytvor au” ” ” ” ” tomat“. • mml“ ” Spoˇc´ıt´a minimal message length pro zadan´ y automat. Vyuˇz´ıv´a k tomu funkce pocet odchodu“ a log2fakt“. ” ” Souˇc´ast´ı aplikace je rovnˇeˇz nˇekolik algoritm˚ u regul´arn´ı inference, kter´e byly staˇzeny z [2]. Protoˇze algoritmy z tohoto odkazu chod´ı jen pod syst´emy na b´azi UNIXu, byly v r´amci pr´ace upraveny tak´e pro syst´emy MS Windows. Potˇrebn´e u ´pravy vˇzdy popisuje soubor readme.txt um´ıstˇen´ y v adres´aˇri s dan´ ym algoritmem. Jednou z nejd˚ uleˇzitˇejˇs´ıch u ´prav je nahrazen´ı hlaviˇckov´eho 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´an´ı automatu pak nastane chyba vstupu, protoˇze pˇri vstupn´ıch operac´ıch prob´ıh´a kontrola datov´ ych typ˚ u (nebo obecnˇe korektnosti vstupn´ıho proudu) pomoc´ı funkce kontrola“. Chybov´e hl´aˇsky jsou vypisov´any funkc´ı chyba“ a z´aroveˇ n je pro” ” gram ukonˇcen s k´odem 1. Touto funkc´ı jsou tedy oˇsetˇrov´any chyby, kter´e zamezuj´ı dalˇs´ımu korektn´ımu bˇehu aplikace. 28
Literatura [1] Abbadingo One: DFA Learning Competition - DFAs: Languages and Learning [online], citov´ano 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´ano 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´anka pro staˇzen´ı gnuplotu [on-line], citov´ano 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´y soubor timeval.h [on-line], citov´ano 13.07.2008, url: http://www.geocities.com/yongweiwu/timeval.h.txt.
30