Induktion av reguljära språk

I beräkningslärandeteori hänvisar induktion av reguljära språk till uppgiften att lära sig en formell beskrivning (t.ex. grammatik) av ett reguljärt språk från en given uppsättning exempelsträngar. Även om E. Mark Gold har visat att inte alla vanliga språk kan läras in på detta sätt (se språkidentifiering i gränsen ), har tillvägagångssätt undersökts för en mängd olika underklasser. De är skissade i den här artikeln. För att lära sig mer allmänna grammatiker, se Grammatikinduktion .

Exempel

Ett reguljärt språk definieras som en (ändlig eller oändlig) uppsättning strängar som kan beskrivas av en av de matematiska formalismer som kallas " finite automaton ", " reguljär grammatik " eller " reguljärt uttryck ", som alla har samma uttryckskraft. . Eftersom den senare formalismen leder till kortaste notationer, ska den introduceras och användas här. Med en uppsättning Σ av symboler (alias alfabetet), kan ett reguljärt uttryck vara vilket som helst av

  • ∅ (betecknar den tomma uppsättningen strängar),
  • ε (betecknar singeluppsättningen som bara innehåller den tomma strängen),
  • a (där a är vilket tecken som helst i Σ; betecknar singeluppsättningen som bara innehåller enteckensträngen a ),
  • r + s (där r och s i sin tur är enklare reguljära uttryck; betecknar deras uppsättnings förening)
  • r ⋅ s (betecknar mängden av alla möjliga sammanlänkningar av strängar från r och s -mängder),
  • r + (betecknar uppsättningen av n -faldiga upprepningar av strängar från r :s uppsättning, för alla n ≥1), eller
  • r * (betecknar på liknande sätt uppsättningen av n -faldiga repetitioner, men även inklusive den tomma strängen, ses som 0-faldig repetition).

Med t.ex. Σ = { 0,1 } betecknar det reguljära uttrycket (0+1+ε)⋅(0+1) mängden av alla binära tal med en eller två siffror (inledande noll tillåts), medan 1⋅( 0+1) * ⋅0 anger den (oändliga) mängden av alla jämna binära tal (inga inledande nollor).

Givet en uppsättning strängar (även kallade "positiva exempel"), är uppgiften med vanlig språkinduktion att komma på ett reguljärt uttryck som betecknar en uppsättning som innehåller dem alla. Som ett exempel, givet { 1, 10, 100 }, kan en "naturlig" beskrivning vara det reguljära uttrycket 1⋅0 * , motsvarande den informella karaktäriseringen " a 1 följt av godtyckligt många (kanske till och med inga) 0es ". Men (0+1) * och 1+(1⋅0)+(1⋅0⋅0) är ett annat reguljärt uttryck, som betecknar den största (förutsatt att Σ={0,1}) och den minsta mängden innehåller de givna strängarna , och kallade den triviala övergeneraliseringen respektive undergeneraliseringen . Vissa metoder fungerar i en utökad miljö där också en uppsättning "negativa exempel"-strängar ges; då finns ett reguljärt uttryck som genererar alla positiva, men inget av de negativa exemplen.

Galler av automater

Delordning av automater som genererar strängarna 1, 10 och 100 (positiva exempel). För var och en av de negativa exempelsträngarna 11, 1001, 101 och 0 visas den övre uppsättningen av automater som genererar den. De enda automaterna som genererar alla { 1, 10, 100 }, men ingen av { 11, 1001, 101, 0 } är den triviala bottenautomaten och den som motsvarar det reguljära uttrycket 1⋅0 * .

Dupont et al. har visat att uppsättningen av alla strukturellt kompletta finita automater som genererar en given ingångsuppsättning av exempelsträngar bildar ett gitter , med den triviala undergeneraliserade och den triviala övergeneraliserade automaten som botten- respektive toppelement. Varje medlem av detta gitter kan erhållas genom att faktorisera den undergeneraliserade automaten med en lämplig ekvivalensrelation .

För ovanstående exempel på stränguppsättning { 1, 10, 100 } visar bilden längst ner den undergeneraliserade automaten A a, b, c,d i grått , bestående av tillstånden a , b , c och d . På tillståndsmängden { a,b,c,d } finns totalt 15 ekvivalensrelationer som bildar ett gitter. Genom att kartlägga varje ekvivalens E till motsvarande kvotautomatspråk L ( A a,b,c,d / E ) erhålls den delvis ordnade uppsättningen som visas i bilden. Varje nods språk betecknas med ett reguljärt uttryck. Språket kan kännas igen av kvotautomater med olika ekvivalensrelationer, som alla visas under noden. En pil mellan två noder indikerar att den nedre nodens språk är en riktig delmängd av de högre nodernas.

Om både positiva och negativa exempelsträngar ges, visar Dupont et al. bygg gittret från de positiva exemplen och undersök sedan separationsgränsen mellan automater som genererar något negativt exempel och sådana som inte gör det. Mest intressant är dessa automater omedelbart under gränsen. På bilden visas separationsgränser för de negativa exempelsträngarna 11 ( grön ), 1001 ( blå ) , 101 ( cyan ) och 0 ( röd ).

Coste och Nicolas presenterar en egen sökmetod inom gittret, som de relaterar till Mitchells versionsrymdparadigm . För att hitta separationsgränsen använder de en graffärgningsalgoritm för ojämlikhetsrelationen tillstånd som induceras av de negativa exemplen. Senare undersöker de flera ordningsrelationer på uppsättningen av alla möjliga statsfusioner.

Kudo och Shimbo använder representationen av automatfaktoriseringar för att ge ett unikt ramverk för följande tillvägagångssätt (skissade nedan ):

Var och en av dessa tillvägagångssätt har visat sig motsvara en viss typ av ekvivalensrelationer som används för faktorisering.

Närmar sig

k -reversibla språk

Angluin betraktar så kallade " k -reversibla" vanliga automater, det vill säga deterministiska automater där varje tillstånd kan nås från högst ett tillstånd genom att följa en övergångskedja med längden k . Formellt, om Σ, Q och δ betecknar inmatningsalfabetet, tillståndsmängden respektive övergångsfunktionen för en automat A , så kallas A k -reversibel om: 000 ∀ a ,..., a k ∈ Σ ∀ s 1 , s 2 ∈ Q : δ * ( s 1 , a ... a k ) = δ * ( s 2 , a ... a k ) ⇒ s 1 = s 2 , där δ * betyder den homomorfa förlängningen av δ till godtyckliga ord. Angluin ger en kubisk algoritm för inlärning av det minsta k -reversibla språket från en given uppsättning inmatningsord; för k =0 har algoritmen till och med nästan linjär komplexitet. Den erforderliga tillståndsunikheten efter k +1 givna symboler tvingar fram förenande automattillstånd, vilket leder till en korrekt generalisering som skiljer sig från den triviala undergeneraliserade automaten. Denna algoritm har använts för att lära sig enkla delar av engelsk syntax; senare har en inkrementell version tillhandahållits. Ett annat tillvägagångssätt baserat på k -reversibla automater är svansklustringsmetoden .

Efterträdare automater

Från en given uppsättning inmatningssträngar bygger Vernadat och Richetin en så kallad efterföljarautomat , bestående av ett tillstånd för varje distinkt tecken och en övergång mellan varje två angränsande teckens tillstånd. Till exempel leder singleton-inmatningen { aabbaabb } till en automat som motsvarar det reguljära uttrycket ( a + ⋅ b + ) * .

En förlängning av detta tillvägagångssätt är metoden föregångare-efterföljare som generaliserar varje teckenupprepning omedelbart till ett Kleene + och sedan inkluderar för varje tecken uppsättningen av dess möjliga föregångare i sitt tillstånd. Efterföljande automater kan lära sig exakt samma klass av lokala språk . Eftersom varje reguljärt språk är den homomorfa bilden av ett lokalt språk, kan grammatik från den tidigare klassen läras in genom att lyfta , om en lämplig (beroende på den avsedda tillämpningen) homomorfism tillhandahålls. I synnerhet finns det en sådan homomorfism för klassen av språk som kan läras in med föregångare-efterträdare-metoden. Lärbarheten för lokala språk kan reduceras till den för k- reversibla språk.

Tidiga närmar sig

Illustration av pumplemma för vanliga automater

Chomsky och Miller (1957) använde pumplemmat : de gissar en del v av en inmatningssträng uvw och försöker bygga in en motsvarande cykel i automaten som ska läras in; med hjälp av medlemsfrågor frågar de efter lämplig k , vilken av strängarna uw , uvvw , uvvvw , ..., uv k w som också tillhör språket som ska läras, och förfinar därigenom strukturen på deras automat. 1959 generaliserade Solomonoff denna inställning till sammanhangsfria språk , som också lyder ett pumpande lemma .

Täck automater

Câmpeanu et al. lära sig en finit automat som en kompakt representation av ett stort finita språk. Givet ett sådant språk F söker de en så kallad täckautomat A så att dess språk L ( A ) täcker F i följande betydelse: L ( A ) ∩ Σ ≤ l = F , där l är längden på den längsta strängen i F , och Σ ≤ l anger mängden av alla strängar som inte är längre än l . Om en sådan täckautomat finns, bestäms F unikt av A och l . Till exempel har F = { ad , read , reread } l =6 och en omslagsautomat som motsvarar det reguljära uttrycket ( r ⋅ e ) * ⋅ a ⋅ d .

För två strängar x och y , Câmpeanu et al. definiera x ~ y om xz ∈ F ⇔ yz ∈ F för alla strängar z med en längd så att både xz och yz inte är längre än l . Baserat på denna relation, vars brist på transitivitet orsakar avsevärda tekniska problem, ger de en O ( n 4 ) algoritm för att konstruera från F en täckautomat A med minimalt tillståndsantal. Dessutom, för förening, skärning och skillnad mellan två finita språk tillhandahåller de motsvarande operationer på deras omslagsautomater. Păun et al. förbättra tidskomplexiteten till O ( n 2 ).

Kvarvarande automater

Brzozowski-derivat (på röd bakgrund) av en ordboksstränguppsättning med avseende på " con "

För en uppsättning S av strängar och en sträng u , definieras Brzozowski-derivatan u −1 S som mängden av alla vilosträngar som kan erhållas från en sträng i S genom att skära av dess prefix u (om möjligt), formellt: u −1 S = { v ∈ Σ * : uv ∈ S } , jfr. bild. Denis et al. definiera en restautomat som en icke-deterministisk finit automat A där varje tillstånd q motsvarar en Brzozowski-derivata av dess accepterade språk L ( A ), formellt: ∀ q ∈ Q ∃ u ∈Σ * : L ( A , q ) = u − 1 L ( A ) , där L ( A , q ) anger språket som accepteras från q som starttillstånd.

De visar att varje vanligt språk genereras av en unikt bestämd minimal restautomat. Dess tillstånd är ∪ -okomponerbara Brzozowski-derivat, och det kan vara exponentiellt mindre än den minimala deterministiska automaten. Dessutom visar de att restautomater för vanliga språk inte kan läras in i polynomtid, även om man antar optimala provingångar. De ger en inlärningsalgoritm för återstående automater och bevisar att den lär sig automaten från dess karakteristiska urval av positiva och negativa inmatningssträngar.

Query Learning

Reguljära språk kan inte läras in i polynomtid med hjälp av enbart medlemskapsfrågor eller med hjälp av enbart ekvivalensfrågor. Angluin har dock visat att vanliga språk kan läras in i polynomtid med hjälp av medlemskapsfrågor och ekvivalensfrågor, och har tillhandahållit en inlärningsalgoritm som kallas L* som gör exakt det. L*-algoritmen generaliserades senare för att mata ut en NFA ( icke-deterministisk finita automata ) snarare än en DFA ( deterministisk finita automata) , via en algoritm som kallas NL*. Detta resultat generaliserades ytterligare och en algoritm som matar ut en AFA ( alternating finite automata ) kallad AL* utarbetades. Det noteras att NFA kan vara exponentiellt mer kortfattade än DFAs, och att AFAs kan vara exponentiellt mer kortfattade än NFAs och dubbelt exponentiellt mer koncisa än DFAs.

Minskade reguljära uttryck

Brill definierar ett reducerat reguljärt uttryck som något av

  • a (där a är vilket tecken som helst i Σ; betecknar singeluppsättningen som bara innehåller enteckensträngen a),
  • ¬ a (betecknar alla andra enstaka tecken i Σ utom a ),
  • • (betecknar ett enskilt tecken i Σ)
  • a * , (¬ a ) * eller • * (betecknar godtyckligt många, möjligen noll, upprepningar av tecken från uppsättningen av a , ¬ a , eller •), eller
  • r ⋅ s (där r och s i sin tur är enklare reducerade reguljära uttryck; betecknar mängden av alla möjliga sammanlänkningar av strängar från r s och s s mängder).

Givet en ingångsuppsättning av strängar, bygger han steg för steg ett träd med varje gren märkt med ett reducerat reguljärt uttryck som accepterar ett prefix för några inmatningssträngar, och varje nod märkt med uppsättningen längder av accepterade prefix. Han syftar till att lära sig korrigeringsregler för engelska stavfel, snarare än på teoretiska överväganden om inlärbarhet av språkklasser. Följaktligen använder han heuristik för att beskära träduppbyggnaden, vilket leder till en avsevärd förbättring av körtiden.

Ansökningar

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Induction_of_regular_languages&oldid=1141026903 "