Ewolucyjne generowanie gramatyk bezkontekstowych z wykorzystaniem algorytmów genetycznych

• Autorzy: Pałka D.

Warianty tytułu

EN

Evolutionary context free grammar induction using genetic algorithm

• Języki publikacji: PL

Abstrakty

PL

Jedną z dziedzin, w której syntaktyczne metody rozpoznawania obrazu okazały się niezwykle użyteczne, jest analiza i wspomaganie diagnostyki niektórych schorzeń na podstawie określonych typów obrazów medycznych. Metody te cechują się większą ogólnością i elastycznością w porównaniu z powszechnie stosowanymi w diagnostyce medycznej metodami minimalno-odległościowymi. Jednak zastosowanie metod syntaktycznych wiąże się z dodatkowymi trudnościami, z których jedną z najważniejszych jest znalezienie odpowiedniej gramatyki pozwalającej na poprawne klasyfikowanie obrazów. W niniejszej pracy podjęta została próba automatyzacji procesu generowania gramatyk bezkontekstowych na podstawie zestawu słów należących do języka (przykładów pozytywnych) oraz słów nienależących do tego języka (przykładów negatywnych). Zaprezentowane podejście opiera się na technice algorytmów genetycznych z kodowaniem chromosomu, opisującego produkcje gramatyki w postaci drzewa.

EN

One of the areas in which syntactic pattern recognition methods have proved extremely useful is the analysis and the assistance of the diagnosis of some ailments on the basis of selected medical images. These methods are more general and more easily adaptable in comparison to the minimal distance methods which are commonly used in medical diagnosis. However, applying the syntactic base pattern recognition methods is not devoid of difficulties, the gravest one being the identification of the grammar allowing for the correct image classification. The paper attempts to automatise the process of generating context free grammars on the basis of the set of strings belonging to a given formal language (positive samples) and strings not belonging to this formal language (negative samples). The adopted approach is based on the genetic algorithm (GA) with direct encoding grammar production rules, which describes the production of the grammar in a tree form.

Słowa kluczowe

PL

generowanie gramatyk; algorytm genetyczny; gramatyki bezkontekstowe

EN

grammar induction; genetic algorithm; context-free grammars

• Wydawca: Wydawnictwa AGH
• Czasopismo: Elektrotechnika i Elektronika
• Rocznik: 2004
• Tom: T. 23, z. 1
• Strony: 58--63
• Opis fizyczny: Bibliogr. 8 poz., rys., wykr., fot.

Twórcy

autor

Pałka D.

• Katedra Informatyki i Metod Komputerowych, Akademia Pedagogiczna im. Komisji Edukacji Narodowej w Krakowie

Bibliografia

• [1] Arabas J.: Wykłady z algorytmów ewolucyjnych. Warszawa, WNT 2001
• [2] Keller B., Lutz R.: Evolving stochastic context-free grammars from examples using a minimum description length principle. The Workshop on Automata, Inductive Grammatical Inference and Language Acquisition, ICML-97, 1997
• [3] Korkmaz E.E., Üçoluk G.: Genetic Programming for Grammar Induction. [in:] Proceedings of 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, 2001
• [4] Koza J.R.: Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992
• [5] Ogiela M.R.: Syntaktyczne metody rozpoznawania obrazów i ich wy korzystanie w analizie wybranych obrazów medycznych. Kraków, UWND AGH 2001, Rozprawy Monografie, nr 100
• [6] Mernik M., Gerlič G., Žumer V., Bryant B.: Can a Parser be Genera ted from Examples? Proceedings of the ACM Symposium on Ap plied Computing, Melbourne 2003, 1063–1067
• [7] Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne. Warszawa, WNT 1996
• [8] Spector L., Langdon W.B., O'Reilly U.M., Angeline P.J. (Eds): Ad vances in Genetic Programming 3. MIT Press, 1999