EL REDUKCIÓ ALKALMAZÁSA A TBL ALGORITMUS IDKÖLTSÉGÉNEK CSÖKKENTÉSÉRE TÓTH ZSOLT, LÁSZLÓ KOVÁCS
Kivonat. A környezet független nyelvek generálása egy N P nehéz probléma, amire a TBL algoritmus[1][2] egy lehetséges megoldást nyújt. A TBL algoritmus magas az id®költsége miatt nem alkalmazható nagy méret¶ problémák megoldására. Az id®költség csökkentésére egy el®redukciós lépést ismertetek, aminek a segítségével a jelent®s mértékben lehet csökkenteni az id®költséget. Az el®redukciós eljárás ismertetése után tapasztalati mérések segítségével becsülöm meg a várható hatékonyság növekedést.
1.
Bevezetés
A természetes és mesterséges nyelvek feldolgozása napjaink egyik aktív kutatási területének számít. A formális nyelvek egy matematikai formalizmus mellyel természetes és mesterséges nyelveket egyaránt le lehet írni. Egy adott L nyelvet a nyelvtana G írja le, ilyenkor azt mondjuk, hogy L nyelvet a G nyelvtan generálja, ezt L(G)vel jelöljük. A G nyelvtant a G = hT , N , P, Si négyes írja le, ahol: T : a terminális szimbólumok halmaza ( a, b, c, · · · ∈ T ) N : a nem terminális szimbólumok halmaza ( A, B, C, · · · ∈ N ) P : a képzési szabályok halmaza P ⊆ α × β ahol α, β, · · · ⊆ {T ∪ N }∗ . S : a mondat szimbólumok halmaza S ⊆ N × N Az egyes formális nyelveket osztályokba sorolhatjuk, az egyik legismertebb osztályozási módszer a Chomsky féle osztályozás[5]. A Chomsky féle osztályozás a nyelveket a képzési szabály alapján sorolja osztályokba, az egyes osztályokat a 1. táblázat foglalja össze. A nyelvtani osztályok közül a környezet független nyelvek osztálya kell®en rugalmas és hatékony módszer a természetes és mesterséges nyelvek reprezentálására. 1. táblázat. A Chomksy féle nyelvtani osztályok Osztály Rekurzívan felsorolható nyelvek Környezet függ® nyelvek Környezet független nyelvek Reguláris nyelvek
Szabály alak α→β αAβ → αγβ α→β A → a és A → Ba vagy A → aB
Számos különböz® módszer létezik CFG 1 generálására pozitív ( U+ ) és negatív (U− ) minta mondatok alapján. Az egyik ilyen módszer a TBL 2 algoritmus. 1Context Free Grammar Környezet Független Nyelvtan 2TaBuLar representation
126
2.
TBL algoritmus
A TBL algoritmust 1999-ben Sakakibara és Kondo ismertette[1], majd Sakakibara vizsgálta[2]. Az Improved TBL algoritmus[3][4] a TBL algoritmus módosított, fejlesztett változata, ami csak az alkalmazott GA 3ban tér el az eredetit®l. A TBL algoritmus képes pozitív ( U+ ) és negatív (U− ) minta mondatok alapján CFG nyelvtant generálni. A nyelvtan generálása során GAt használ, a legtömörebb nyelvtan megkeresésére. A GA a legkisebb olyan partícionálását keresi a nem terminális szimbólumoknak, ami elfogadja az összes pozitív minta mondatot, de nem fogad el egy negatív minta mondatot sem.
2.1.
A TBL algoritmus lépései. A TBL algoritmus az alábbi három f® lépésre os-
ztható: (1) Primitív nyelvtanok ( Gω (T (ω))) meghatározása minden pozitív tanító mondatra (ω ∈ U+ ). (2) Ered® nyelvtan el®állítása a primitív nyelvtanok segítségével ( G(U+ ) = ∪Gω (T (ω))). (3) Az ered® nyelvtan redukálása GA segítségével.
2.1.1. A primitív nyelvtanok el®állítása. A primitív nyelvtanok el®állítására egy, a CYK 4 algoritmusban használt táblázat szer¶ adat struktúrát használ a TBL algoritmus. A táblázat egy n × nes alsó háromszög mátrixra hasonlít, ahol n a mondatok szavainak a száma, a celláiban pedig nem terminális szimbólumok tömbje helyezkedik el. A TBL algoritmus a táblázatot a minta mondat alapján feltölti és meghatározza ez alapján a tanító mondat primitív nyelvtanát. A primitív nyelvtan tartalmazza az adott mondat el®állításához alkalmazható összes lehetséges levezetési fát. Az ered® nyelvtant a primitív nyelvtanokból állítja el® únió képzéssel. 2.1.2. Az alkalmazott GA. A TBL algoritmus az ered® nyelvtan redukálására GAt alkalmaz. A GA osztályokba sorolja az egyes nem terminális szimbólumokat és az azonos osztályba tartozó nem terminális szimbólumokat összevonja. Így csökkenti a szimbólumok és a képzési szabályok számát. A GA a partícionálás során csoport szám kódolást alkalmaz az egyes egyedek reprezentálására, ami azt jelenti, hogy minden egyes nem terminális szimbólumhoz egy-egy számot rendel, ami egy adott csoportot jelképez. Tehát a gén hossza, így egy-egy genetikus operátor id®költsége is függ a nem terminális szimbólumok számától, azaz a bemen® mondatok hosszától. A TBL algoritmus id®költségének jelent®s részét az alkalmazott GA teszi ki.
TBL tness fügvénye A TBL algoritmus tness függvénye az alábbi két segéd függvényt használja.
f1 (p) =
| {ω ∈ U+ | G(T (U+ ))/πp } | | U+ | f2 (p) =
1 | πp |
3Genetic Algorithm Genetikus Algoritmus 4Cocke, Younger, Kashami
127
ha ∃ω ∈ U− úgy, hogy ω ∈ L(G(T (U+ ))/πp ) egyébként Az ITBL algoritmus egy harmadik segéd tness függvényt is alkalmaz és elfogad olyan nyelvtanokat is amik képesek negatív mintamondatokat generálni, de ezekhez a nyelvtanokhoz kis tness értéket rendel.
f (p) =
0
C1 f1 (p)+C2 f2 (p) C1 +C2
f3 (p) = f (p) =
| {ω ∈ U− | G(T (U+ ))/πp } | | U− |
−(C3 f3 + C4 (1 − f1 )) C1 f1 (p)+C2 f2 (p) C1 +C2
∃ω ∈ U− úgy, hogy ω ∈ L(G(T (U+ ))/πp ) egyébként
Ahol C1 , C2 , C3 és C4 a GA paraméterei. Látható, hogy a GA id®költségének egyik meghatározó tényez®je a tness érték meghatározásának költsége. 3.
El® redukció
A TBL és az ITBL algoritmus a m¶ködése során a pozitív tanító mondatokból ( ω ∈ U+ ) primitív nyelvtanokat ( Gω (T (ω))) állít el®, melyek tartalmazzák az adott mondat összes lehetséges levezetési fáját és a szabályok Chomsky-féle normál alakban vannak ( A → BC , A → a, A → ). Gω (T (ω)) A primitív nyelvtanok alapján egy ered® nyelvtant határoz meg, ami tartalmazza az össze pozitív nyelvtant és az ered® nyelvtan alapján levezethet® az össze pozitív tanító mondatot. [ Gω (T (ω)) G= ω∈U+
A TBL és az ITBL algoritmusok az ered® nyelvtant GA segítségével redukálják. A GA tness függvényének nagy az id®költsége, mivel az egyes egyedekre el® kell állítani a redukált nyelvtant, és azokon hajtanak végre m¶veleteket. Az algoritmust egyszer¶ SQL parancsokra (mondatokra) tesztelve arra az eredményre jutottam, hogy az algoritmus id® költsége a mondatok hosszában jelent®s mértékben változik. Az algoritmus futási ideje viszonylag kevés (10-15) tanító mondat esetén is meghaladhatja egy átlagos PC számítási kapacitását, ezért a kit¶zött cél a futási id® csökkentése. Ezt a cél valamilyen el® redukciós lépéssel lehetne megoldani, ami csökkenti az ered® nyelvtanban a nem terminális szimbólumok számát, így csökkentve a GA futási idejét. A javasolt el®redukciós eljárást az alábbi két lépésre lehet bontani: • A → a alakú szabályok összevonása • A → BC és D → BC szabályok összevonása, Bottom Up redukciós eljárás
3.1. A → a redukció. A primitív mondat el®állítása egy terminális szimbólumra több szabály is mutat (a táblázatos reprezentációnak köszönhet®en). A redukciós módszer célja P ezen szabályok összevonása, így ω∈U+ | ω | darab szabály helyett | T | darab A → a típusú szabályt tartalmaz a mondat, ahol | ω | az ω mondat hossza. El®nye
• Egyszer¶en implementáció
128
• Kevés szó és sok mondat esetén hatékony
Hátránya • Sok szó és ritka szavak esetén kevésbé hatékony • Az összes szabálynak csak egy kis hányadát érinti, így nagy hosszú mondatok esetén nem túl hatékony, kevés nem terminális szimbólumot von össze
3.2.
Bottom Up redukció. A Bottom Up redukciós eljárás el®feltétele az A → a redukció! A Bottom Up redukció alapelve, hogy összevonja azokat a szabályokat amelyeknek azonos a jobb oldaluk. A környezet független nyelvek a Chomsky féle osztályozás alapján csak A → α alakú szabályokat tartalmaznak, de a TBL algoritmus a m¶ködéséb®l adódóan CNF5ban lev® szabályokkal dolgozik. A CNFban lev® szabályok csak A → a, A → BC A → alakúak. 3.2.1. (1) (2) (3) (4)
A Bottom Up redukciós algoritmus. Inverz lista készítése A → BC =⇒ BC ← A, G, H, Z, . . . Inverz lista alapján a megfelel® bal oldalak összevonása Az összevonás után az új szabályok meghatározása Ha volt összevonás akkor újra az 1-t®l a redukált szabály listára, különben kilépés.
El®nye • Viszonylag gyors • A minden alakú szabályt vizsgál • Jelent®s szimbólum redukciót lehet vele elérni
Hátránya • A → a el® redukciót igényel 3.2.2. Példa. A kiinduló szabályokat az 2. táblázat tartalmazza. A szabályok alapján a 3 táblázatban szerepl® inverz szabály listát kaptam. Az inverz szabály lista alapján az A, H, K és a D, J szabályokat lehet összevonni, így egy redukált inverz listát eredményez lásd 4. táblázat. A redukált inverz szabály lista alapján egy redukált szabály listát lehet készíteni, lásd 5. táblázat. 2. táblázat. Kiinduló szabályok No 1 2 3 4 5 6 7
Bal A D G H I J K
→ → → → → → → →
Jobb1 B E C B B E B
3. táblázat. Inverz Szabály Lista
Jobb2 C F E C E F C
No 1 2 3 4
5Chomskian Normal Form Chomksy féleNormál Forma
129
Jobb BC EF CE BE
⇐= ⇐= ⇐= ⇐= ⇐=
Ball A,H,K D,J G I
4. táblázat. Redukált Inverz Szabály Lista No 1 2 3 4
Jobb BC EF CE BE
5. táblázat. Redukált szabályok
Ball A D G I
⇐= ⇐= ⇐= ⇐= ⇐=
No 1 2 3 4
Bal A D G I
→ → → → →
Jobb1 B E C B
Jobb2 C F E E
3.2.3. Tapasztalati eredmény. Az el® redukciót és a TBL algoritmust ugyan azon tanító halmazon futtatva a 6. táblázatban látható eredményeket kaptam. A kapott eredményb®l látható, hogy a heurisztikus el®redukció jelent®s mértékben csökkentette a nem terminális szimbólumok számát, illetve a képzési szabályok számát. Ebb®l következik, hogy a TBL algoritmus futási ideje is csökken, ami a jelen mérés alapján jelent®s, mert a sima TBL algoritmusnak 117936msra volt szüksége addig az el® redukció után végrehajtott TBL algoritmusnak csak 22340ms kellett a futáshoz ugyan azon C1 , C2 paraméterek mellett, azaz el® redukció után elegend® volt a futási id® 18, 94%a. 6. táblázat. Tapasztalati eredmények Szimbólum |T | |N | |P| |T ∪N | Tksg
Ered® 10 98 112 108 2 4.
Heurisztikus 10 74 88 84 40
TBL 10 50 86 60 117936
Heurisztikus + TBL 10 24 110 34 22340
Köszönet nyilvánítás
A kutató munka a TÁMOP-4.2.2/B-10/1-2010-0008 jel¶ projekt részeként - az Új Magyarország Fejlesztési Terv keretében - az Európai Unió támogatásával, az Európai Szociális Alap társ nanszírozásával valósult meg. Hivatkozások
[1] Yasubumi Sakakibara, Mitsuhiro Kondo: GA-based learning of context-free grammars using tabular representations [2] Yasubumi Sakakibara: Learning context-free grammars using tabular representation [3] Marcin Jaworski, Olgierd Unold: Improved TBL algorithm for learning context-free grammar [4] Marcin Jaworski, Olgierd Unold: Learning context-free grammar using improved tabular representation [5] Chomsky féle osztályozás: http://en.wikipedia.org/wiki/Chomsky_hierarchy [6] Wikipedia O jelölés: http://hu.wikipedia.org/wiki/O_jel%C3%B6l%C3%A9s
130
TARTALOMJEGYZÉK Antal Dániel EJTÉSI TESZT EGYSZER SÍTETT MODELLEZÉSE A TERVEZÉS FÁZISÁBAN
1
Bodolai Tamás MINTATESZTEL SZOFTVER FEJLESZTÉSE LINE SCAN KAMERÁS ALKALMAZÁSOKHOZ
7
Bodzás Sándor DESIGNING AND MODELLING OF WORM GEAR HOB
12
Burmeister Dániel BUCKLING OF SHELL-STIFFENED AND AXISYMMETRICALLY LOADED ANNULAR PLATES
18
Daróczy Gabriella EMOTION AND THE COMPUTATIONAL MODEL OF METAPHORS
24
Drágár Zsuzsa NEM SZABVÁNYOS SZERSZÁM-ALAPPROFIL KIALAKÍTÁSÁNAK LEHET SÉGEI FOGASKEREKEKHEZ
30
Fekete Tamás MEMBRÁNOK ALKAKMAZÁSA SZINKRON VÁLTAKOZÓ ÁRAMÚ HIDRAULIKUS HAJTÁSOKBAN
35
Ferenczi István MODELING THE BEHAVIOR OF PROFINET IRT IN GIGABIT ETHERNET NETWORK 41 Ficsor Emese AUTOMATIZÁLT AZONOSÍTÁSTECHNIKAI ÉS NYOMONKÖVETÉSI LEHET SÉGEK VIZSGÁLATA INTERMODÁLIS SZÁLLÍTÁS SORÁN
47
Gáspár Marcell Gyula NAGYSZILÁRDSÁGÚ ACÉL HEGESZTÉSTECHNOLÓGIÁJÁNAK FEJLESZTÉSE A H LÉS ID ELEMZÉSÉVEL
54
Hriczó Krisztián NEMNEWTONI FOLYADÉKOK HATÁRRÉTEG ÁRAMLÁSÁNAK HASONLÓSÁGI MEGOLDÁSAI KONVEKTÍV FELÜLETI PEREMFELTÉTELEK MELLETT 60 Kelemen László Attila DOMBORÍTOTT FOGAZAT MATEMATIKAI MODELLEZÉSE FOGASGY R S TENGELYKAPCSOLÓKHOZ 66
Krizsán Zoltán STRUCTURAL IMPROVEMENTS OF THE OPENRTM ROBOT MIDDLEWARE 72 Mándy Zoltán A POSSIBLE NEURAL NETWORK FOR A HOLONIC MANUFACTURING SYSTEM 78 Simon Pál GRAFIKUS PROCESSZOROK ALKALMAZÁSA KÉPFELDOLGOZÁSI FELADATOKRA
84
Skapinyecz Róbert OPTIMALIZÁLÁSI LEHET SÉGEK VIZSGÁLATA EGY E-PIACTÉRREL INTEGRÁLT VIRTUÁLIS SZÁLLÍTÁSI VÁLLALATNÁL 90 Somosk i Gábor COLD METAL TRANSFER – THE CMT PROCESS Szabó Adél Anett A TELJES KÖLTSÉG KONCEPCIÓ BESZERZÉSI GYAKORLATBAN
JELENT SÉGE
96 A
Szamosi Zoltán MEZ GAZDASÁGI HULLADÉKOK VIZSGÁLATA Szilágyiné Biró Andrea BETÉTEDZÉS ACÉLOK KARBONITRIDÁLÁSA
KÜLÖNBÖZ
VÁLLALATI 102 108
H MÉRSÉKLET 114
Tomkovics Tamás DARABÁRU OSZTÁLYOZÓ RENDSZEREK KISZOLGÁLÁSI STRATÉGIÁIT BEFOLYÁSOLÓ JELLEMZ K; A RENDSZEREK MODULJAI KÖZÖTTI ÖSSZEFÜGGÉSEK FELTÁRÁSA 120 Tóth Zsolt EL REDUKCIÓ ALKALMAZÁSA A TBL ALGORITMUS ID KÖLTSÉGÉNEK CSÖKKENTÉSÉRE 126 Varga Zoltán KONKRÉT LOGISZTIKAI MINTARENDSZER MODELLEZÉSE
131
Vincze Dávid MATLAB INTERFACE FOR THE 3D VIRTUAL COLLABORATION ARENA 137 Wagner György INTENZÍTÁS BÁZISÚ OPTIMALIZÁLÁS FORGÁCSOLÁSI PARAMÉTEREK MEGHATÁROZÁSÁHOZ 143
