Qrammatik induksiya

Qrammatik induksiya — bu dildə məlum üzvlüyə malik bir sıra müşahidələr (nümunələr) əsasında dilin formal qrammatikasını bərpa edən maşın öyrənmə proseduru.^[1] Prosedur nəticəsində müşahidə olunan obyektlərin modeli nəticə çıxarma qaydaları və ya generasiya qaydaları[az], sonlu avtomat və ya başqa növ avtomat şəklində qurulur. Ümumiyyətlə, qrammatik nəticə, nümunə məkanının sətirlər, ağaclar, qrafiklər kimi diskret kombinator obyektlərindən ibarət olduğu maşın öyrənmə sahələrindən biridir.

Qrammatika dərsləri

Qrammatik nəticə tez-tez müxtəlif tipli sonlu avtomatların öyrənilməsi probleminə çox diqqət yetirir , çünki bu problem üçün effektiv alqoritmlər 1980-ci illərdən bəri mövcuddur. 2000-ci illərin əvvəllərindən etibarən bu yanaşmalar kontekstsiz qrammatikaların və çoxlu kontekstsiz qrammatikalar və paralel çoxsaylı kontekstsiz qrammatikalar kimi daha zəngin formalizmlərin nəticə çıxarmaq vəzifəsinə qədər genişləndirilmişdir. Qrammatik nəticənin öyrənildiyi qrammatikaların digər sinifləri də digər qrammatika sinifləri — kontekstual qrammatikalar və nümunə dilləri üçün də öyrənilmişdir.

Öyrənmə Modelləri

Ən sadə öyrənmə növü öyrənmə alqoritmi sözügedən dilin sözlərindən yalnız nümunələr toplusunu, bəzən isə əks nümunələri qəbul etməsidir. Digər öyrənmə modelləri də var. Tez-tez öyrənilən alternativlərdən biri, məsələn, dəqiq öyrənmə modelində və ya Anqluin [2] tərəfindən təqdim edilən minimal adekvat müəllim modelində olduğu kimi, şagirdin sözün dilə mənsubiyyəti haqqında sual verə bilməsi halıdır.^[2]

Metodologiyalar

Qrammatik nəticə çıxarmaq üçün müxtəlif üsullar işlənib hazırlanmışdır. İki klassik mənbə Fu-nun 1977[3] və 1982[4] sənədləridir. Duda, Hart və Storck[5] da bu problemə kiçik bir bölmə ayırmış və bir çox mənbəyə istinad etmişlər. Onların təqdim etdikləri əsas sınaq və səhv metodu aşağıda müzakirə olunur. Xüsusilə normal dilləri alt siniflərə ayırmaq üçün yanaşmalar üçün Daimi Dillərin İnduksiyasına baxın[en]. Daha yeni bir kitab de la Higuera'nın (2010)[1] kitabıdır, o, müntəzəm dillərdə və sonlu avtomatlarda qrammatik nəticə nəzəriyyəsini əhatə edir. D'Ulysia, Ferry və Grifoni[6] təbii dillər üçün nəticə çıxarma üsulları ilə bağlı araşdırmaları nəzərdən keçirdilər.

Sınaq və səhv yolu ilə qrammatik nəticə

Daud, Hart və Storck-un[5] 8.7-ci bölməsində təklif olunan metod qrammatik qaydaların ardıcıl təxminini və onları müsbət və mənfi müşahidələrə qarşı sınaqdan keçirməyi təklif edir. Qaydalar toplusu genişlənir ki, hər bir müsbət nümunə yaradılsın, lakin verilmiş qaydalar dəsti mənfi nümunə yaradırsa, o, atılmalıdır. Bu xüsusi yanaşma "fərziyyə testi" kimi təsvir edilə bilər və Mitchell alqoritminin versiya sahəsinə bir qədər bənzəyir. Dowd, Hart və Storck[5] tərəfindən yazılmış məqalənin mətni prosesi yaxşı təsvir edən sadə bir nümunə verir, lakin daha böyük problemlər üçün bu cür idarə olunmayan sınaq və səhv yanaşmasının mümkünlüyü şübhə altındadır.

Genetik alqoritmlərlə qrammatik nəticə

Təkamül alqoritmlərindən istifadə edən qrammatik induksiya bir növ təkamül prosesi vasitəsilə hədəf dilin qrammatik təsvirinin inkişaf etdirilməsi prosesidir. Formal qrammatikalar təkamül operatorlarına məruz qala bilən istehsal qaydalarının ağac strukturu kimi asanlıqla təmsil oluna bilər. Bu cür alqoritmlər Con Koza tərəfindən irəli sürülən genetik proqramlaşdırma paradiqmasından qaynaqlanır. Sadə formal dillər üzrə digər erkən işlərdə genetik alqoritmlərin ikili simli təsvirindən istifadə edilirdi, lakin EBNF-də tərtib edilmiş qrammatikaların xas iyerarxik strukturu ağacları daha çevik bir yanaşma etdi. Koza Lisp proqramlarını ağac kimi təmsil edirdi. O, ağac operatorlarının standart dəstində genetik operatorların analoqlarını tapmağa nail olub. Məsələn, alt ağacın dəyişdirilməsi genetik kodun alt sətirlərinin gələcək nəslin fərdinə köçürüldüyü müvafiq genetik keçid prosesinə bərabərdir. Uyğunluq Lisp kodu funksiyalarının çıxışının qiymətləndirilməsi ilə ölçülür. Lisp-in ağac təsviri ilə qrammatikaların ağac kimi təqdim edilməsi arasındakı oxşar analogiyalar qrammatik induksiya üçün genetik proqramlaşdırma üsullarından istifadə etməyə imkan verdi. Qrammatik induksiya vəziyyətində, alt ağacların köçürülməsi bəzi dildən ifadələri təhlil etməyə imkan verən istehsal qaydalarının dəyişdirilməsinə uyğundur. Qrammatikaya uyğunluq operatoru onun hədəf dildə müəyyən qrup cümlələri təhlil etməkdə nə dərəcədə yaxşı performans göstərməsinin müəyyən ölçülərinə əsaslanır. Qrammatikanın ağac təsvirində istehsal qaydasının son simvolu ağacın yarpaq düyününə uyğun gəlir. Onun əsas qovşaqları qaydalar toplusunda qeyri-terminal xarakterə (məsələn, isim ifadəsi və ya fel ifadəsi kimi) uyğun gəlir. Nəhayət, kök düyün qeyri-terminal cümləyə uyğun ola bilər.

Acgöz alqoritmlərlə qrammatik nəticə

Bütün acgöz alqoritmlər kimi, acgöz nəticə alqoritmləri də iterativ olaraq müəyyən mərhələdə ən yaxşısı kimi görünən qərarlar qəbul edir. Qəbul edilən qərarlar, adətən, yeni qaydaların yaradılması, mövcud qaydaların silinməsi, tətbiq olunacaq qaydanın seçilməsi və ya bəzi mövcud qaydaların birləşdirilməsi kimi məsələlərlə bağlıdır. "Mərhələ" və "ən yaxşı"nı müəyyən etməyin bir çox yolu olduğundan, bir çox xəsis nəticə alqoritmləri də var.

Bu kontekstsiz qrammatik generasiya alqoritmləri hər oxunan simvoldan sonra qərar qəbul edir:

Lempel-Ziv-Welch alqoritmi deterministik şəkildə kontekstsiz qrammatika yaradır, belə ki, yaradılan qrammatikanın yalnız ilkin qaydasını saxlamaq lazımdır. Sekitur və onun modifikasiyaları. Bu kontekstsiz qrammatik generasiya alqoritmləri əvvəlcə verilmiş simvol ardıcıllığını oxuyur və sonra qərarlar qəbul etməyə başlayır:

Bayt cütlərinin kodlaşdırılması və onun optimallaşdırılması.

Paylanmış Öyrənmə

Daha müasir yanaşma paylanmış öyrənməyə əsaslanır. Bu yanaşmalardan istifadə edən alqoritmlər kontekstsiz qrammatikaların və zəif kontekstə həssas dillərin öyrənilməsində tətbiq edilmiş və bu qrammatikaların böyük alt sinifləri üçün düzgün və səmərəli olduğu sübut edilmişdir.^[3]

Model Dilləri Öyrənmək

Anqluin nümunəni "Σ-dan sabit simvollar və ayrı-ayrı dəstdən dəyişən simvollar silsiləsi" kimi müəyyən edir. Belə bir nümunənin dili onun bütün boş olmayan əsas nümunələrinin, yəni dəyişən simvollarının boş olmayan sabit simvol sətirləri ilə ardıcıl əvəzlənməsi nəticəsində yaranan bütün sətirlərin məcmusudur. Şablon, giriş dəstini daxil edən bütün şablon dilləri arasında dili minimaldırsa (dəstəyə daxil edilməsinə münasibətdə) sətirlərin sonlu giriş dəstinin təsviri olduğu deyilir. Anqluin, bir x dəyişənindəki bütün təsviri nümunələrin verilmiş giriş sətirləri üçün hesablanması üçün polinom alqoritmini təklif edir. Bu məqsədlə o, bütün mümkün müvafiq nümunələri təmsil edən avtomat qurur; x-in tək dəyişən olmasına əsaslanan mürəkkəb söz uzunluğu arqumentlərindən istifadə etməklə vəziyyətlərin sayı kəskin şəkildə azaldıla bilər.

Erlebach və başqaları Anqluin nümunəsini öyrənmə alqoritminin daha səmərəli versiyasını, eləcə də paralelləşdirilmiş versiyasını verirlər.

Arimura və başqaları göstərir ki, məhdud model birləşmələrindən əldə edilən dil sinfi polinom zamanda öyrənilə bilər.^[4]^[5]

Nümunə nəzəriyyəsi

Ulf Grenander^[6] tərəfindən tərtib edilmiş nümunə nəzəriyyəsi dünya haqqında biliyi nümunələr şəklində təsvir etmək üçün riyazi formalizmdir. O, süni intellektə digər yanaşmalardan onunla fərqlənir ki, o, nümunələri tanımaq və təsnif etmək üçün alqoritmlər və mexanizmlər təyin etməklə başlamır; daha doğrusu, şablon anlayışlarını dəqiq dildə formalaşdırmaq və yenidən formalaşdırmaq üçün söz ehtiyatı təyin edir.

Yeni cəbri lüğətə əlavə olaraq, onun statistik yanaşması öz məqsədinə görə yeni idi:

O zaman ümumi olan süni stimullardan daha çox real dünya məlumatlarından istifadə edərək gizli verilənlər bazası dəyişənlərini təyin edin. Gizli dəyişənlər üçün əvvəlki paylanmaları və Gibbs qrafikinin təpələrini təşkil edən müşahidə olunan dəyişənlər üçün modelləri formalaşdırın. Bu qrafiklərin təsadüfiliyini və dəyişkənliyini öyrənin. Nümunə deformasiyalarını sadalamaqla tətbiq olunan stoxastik modellərin əsas siniflərini yaradın. Modelləri sintez edin (nümunə edin), onlarla yalnız siqnalları təhlil etməyin. Riyazi cəhətdən geniş olan nümunə nəzəriyyəsi cəbr və statistikanı, həmçinin yerli topoloji və qlobal entropiya xassələrini əhatə edir.

Proqramlar

Qrammatik induksiya prinsipi təbii dilin emalının digər aspektlərinə tətbiq edilmiş və (bir çox başqa problemlər arasında) semantik təhlilə,^[7] təbii dilin anlaşılmasına,^[8] nümunə əsasında tərcüməyə,^[9] morfem təhlilinə tətbiq edilmişdir. , və coğrafi adların mənşəyi. [Sitat lazımdır] Qrammatik induksiya həmçinin Minimum Mesaj Uzunluğu (MML) və Minimum Təsvir Uzunluğu (MDL) prinsiplərindən istifadə edərək qrammatika əsaslı sıxılma^[10] və statistik nəticə çıxarmaq üçün istifadə edilmişdir. [Sitat tələb olunur] Qrammatik induksiya dilin mənimsənilməsinin bəzi ehtimal modellərində də istifadə edilmişdir.

İstinadlar

↑ de la Higuera, Colin. Grammatical Inference: Learning Automata and Grammars (PDF). Cambridge: Cambridge University Press. 2010. 2019-02-14 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2022-11-17.
↑ Dana Angluin. "Learning Regular Sets from Queries and Counter-Examples" (PDF). Information and Control. 75 (2). 1987: 87–106. CiteSeerX 10.1.1.187.9414. doi:10.1016/0890-5401(87)90052-6. 2013-12-02 tarixində orijinalından (PDF) arxivləşdirilib.
↑ Clark and Eyraud (2007) Journal of Machine Learning Research; Ryo Yoshinaka (2011) Theoretical Computer Science
↑ T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger; T. Zeugmann. Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries // M. Li; A. Maruoka (redaktorlar ). Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97. LNAI. 1316. Springer. 1997. 260–276. 2022-03-17 tarixində arxivləşdirilib. İstifadə tarixi: 2022-11-17.
↑ Hiroki Arimura; Takeshi Shinohara; Setsuko Otsuki. Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data (PDF) // Proc. STACS 11. LNCS. 775. Springer. 1994. 649–660.^{[ölü keçid]}
↑ Grenander, Ulf, and Michael I. Miller. Pattern theory: from representation to inference.^{[ölü keçid]} Vol. 1. Oxford: Oxford university press, 2007.
↑ Kwiatkowski, Tom, et al. "Lexical generalization in CCG grammar induction for semantic parsing Arxivləşdirilib 2022-11-17 at the Wayback Machine." Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011.
↑ Miller, Scott, et al. "Hidden understanding models of natural language Arxivləşdirilib 2021-06-04 at the Wayback Machine." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.
↑ Brown, Ralf D. "Transfer-rule induction for example-based translation." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.
↑ Cherniavsky, Neva, and Richard Ladner. "Grammar-based compression of DNA sequences." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).

[Grammatical_Inference-1] de la Higuera, Colin. Grammatical Inference: Learning Automata and Grammars (PDF). Cambridge: Cambridge University Press. 2010. 2019-02-14 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2022-11-17.

[2] Dana Angluin. "Learning Regular Sets from Queries and Counter-Examples" (PDF). Information and Control. 75 (2). 1987: 87–106. CiteSeerX 10.1.1.187.9414. doi:10.1016/0890-5401(87)90052-6. 2013-12-02 tarixində orijinalından (PDF) arxivləşdirilib.

[3] Clark and Eyraud (2007) Journal of Machine Learning Research; Ryo Yoshinaka (2011) Theoretical Computer Science

[4] T. Erlebach; P. Rossmanith; H. Stadtherr; A. Steger; T. Zeugmann. Learning One-Variable Pattern Languages Very Efficiently on Average, in Parallel, and by Asking Queries // M. Li; A. Maruoka (redaktorlar ). Proc. 8th International Workshop on Algorithmic Learning Theory — ALT'97. LNAI. 1316. Springer. 1997. 260–276. 2022-03-17 tarixində arxivləşdirilib. İstifadə tarixi: 2022-11-17.

[5] Hiroki Arimura; Takeshi Shinohara; Setsuko Otsuki. Finding Minimal Generalizations for Unions of Pattern Languages and Its Application to Inductive Inference from Positive Data (PDF) // Proc. STACS 11. LNCS. 775. Springer. 1994. 649–660.^{[ölü keçid]}

[6] Grenander, Ulf, and Michael I. Miller. Pattern theory: from representation to inference.^{[ölü keçid]} Vol. 1. Oxford: Oxford university press, 2007.

[Kwiatkowski-7] Kwiatkowski, Tom, et al. "Lexical generalization in CCG grammar induction for semantic parsing Arxivləşdirilib 2022-11-17 at the Wayback Machine." Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011.

[8] Miller, Scott, et al. "Hidden understanding models of natural language Arxivləşdirilib 2021-06-04 at the Wayback Machine." Proceedings of the 32nd annual meeting on Association for Computational Linguistics. Association for Computational Linguistics, 1994.

[9] Brown, Ralf D. "Transfer-rule induction for example-based translation." Proceedings of the MT Summit VIII Workshop on Example-Based Machine Translation. 2001.

[10] Cherniavsky, Neva, and Richard Ladner. "Grammar-based compression of DNA sequences." DIMACS Working Group on The Burrows–Wheeler Transform 21 (2004).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]