Generowanie gramatyk bezkontekstowych dla potrzeb syntaktycznego rozpoznawania wzorców

• Autorzy: Pałka D.
• Języki publikacji: PL

Abstrakty

PL

W pracy tej przedstawiony został sposób automatyzacji procesu generowania gramatyk formalnych na podstawie pozytywnych i negatywnych przykładów języka. Sposób ten polega na ewolucji gramatyk w oparciu o technikę programowania genetycznego (GP). Może znaleźć on zastosowanie w procesie syntaktycznego rozpoznawania wzorców w przypadku, gdy reguły syntaktyczne nie są znane a priori, lecz muszą zostać określone na podstawie wzorców przykładowych. Jedną z dziedzin, w której istnieje zapotrzebowanie na tego typu wspomaganie i automatyzację procesu definiowania gramatyk jest syntaktyczna analiza wybranych typów obrazów medycznych dla potrzeb wspomagania diagnostyki różnego rodzaju schorzeń. W pracy przedstawione zostało porównanie rezultatów otrzymanych przy zastosowaniu w procesie ewolucji generatora analizatorów składniowych klasy GLR oraz klasy LALR(1) wykorzystanych do znalezienia gramatyki bezkontekstowej dla języka opisującego przewężenia tętnic wieńcowych.

EN

The article presents a method of automation of the grammatical inference process based on positive and negative language samples. The method makes use of the evolutionary approach based on genetic programming technique (GP) and can be used in the process of syntactic patterns recognition, especially in cases when syntactic rules are not known a priori but need to be induced on the basis of sample patterns. One of the areas in which such assistance and the automation of the grammatical inference process proves particularly useful is the syntactic analysis of selected types of medical images supporting diagnosis of various ailments. The advantages of the syntactic methods include greater generality and easier adaptability in comparison to the minima] distance methods which are commonly used in medical diagnosis. However, the application of the syntactic methods is not devoid of difficulties, the gravest of which being the actual finding of the grammar which would correctly classify images. The method of automation of the context-free grammars generation process based on language samples presented in this article is an attempt of solving this problem. The article presents the results obtained by applying Generalized LR (GLR) parsing algorithm to the evolution process, which allowed to avoid the difficulty of trying to make a language grammar fit the LALR(1) restrictions.

Słowa kluczowe

PL

generowanie gramatyk; programowanie genetyczne; gramatyki bezkontekstowe

EN

grammar induction; genetic programming; context-free grammars

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2004
• Tom: R. 4, nr 7
• Strony: 139--147
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Pałka D.

• Katedra Informatyki i Metod Komputerowych, Akademia Pedagogiczna ul. Podchorążych 2,30-084 Kraków

Bibliografia

• [1] Arabas J., Wykłady z algorytmów ewolucyjnych, WNT, Warszawa 2001.
• [2] Koza J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, 1992.
• [3] Koza J.R., Bennett F.H, Andre D., Keane M.A., Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann, Publishers, Inc. 1999.
• [4] Mernik M., Crepinsek M., Gerlic G., Zumer V.,Bryant B., Sprague A., Learning Context-Free Grammars using an Evolutionary Approach, Technical Report, University of Maribor and University of Alabama at Birmingham, 2003.
• [5] Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 2003.
• [6] Ogiela M.R., Syntaktyczne metody rozpoznawania obrazów i ich wykorzystanie w analizie wybranych obrazów medycznych, Rozprawy Monografie, nr 100, UWND AGH Kraków 2001.
• [7] Pałka D., Ewolucyjne generowanie gramatyk bezkontekstowych z wykorzystaniem algorytmów genetycznych, Półrocznik AGH Elektrotechnika i Elektronika 2004, 23, 1, 58-63.
• [8] Pałka D., Środowisko programowania genetycznego GPSource, Informatyka Teoretyczna i Stosowana 2003, 5, -207.
• [9] Spector L. Langdon W.B., O’Reilly U.M., Angeline P.J. (Eds), Advances in Genetic Programming 3, MIT Press 1999.