Wyniki wyszukiwania - BazTech

1

Inferring graph grammars by detecting overlap in frequent subgraphs

Kukluk J. P., Holder L. B., Cook D. J.

International Journal of Applied Mathematics and Computer Science

|

2008

|

Vol. 18, no 2

241-250

EN

In this paper we study the inference of node and edge replacement graph grammars. We search for frequent subgraphs and then check for an overlap among the instances of the subgraphs in the input graph. If the subgraphs overlap by one node, we propose a node replacement graph grammar production. If the subgraphs overlap by two nodes or two nodes and an edge, we propose an edge replacement graph grammar production. We can also infer a hierarchy of productions by compressing portions of a graph described by a production and then inferring new productions on the compressed graph. We validate the approach in experiments where we generate graphs from known grammars and measure how well the approach infers the original grammar from the generated graph. We show graph grammars found in biological molecules, biological networks, and analyze learning curves of the algorithm.

2

Analiza wpływu wybranych parametrów na efektywność systemu GCS

Unold O.

Informatyka Teoretyczna i Stosowana

|

2005

|

R. 5, nr 8

177-189

PL

Przedstawiono nowy model uczącego się systemu klasyfikującego, w którym klasyfikatory reprezentowane są przez produkcję gramatyki bezkontekstowej podane w postaci normaluej Chomsky'ego. System GCS (ang. grammar-based classifier system) odkrywa nowe reguły gramatyki stosując metodę tzw. pokrywania (ang. covering) oraz algorytm genetyczny. Efektywność systemu zależy w znacznej mierze od odpowiedniego ustawienia jego parametrów. W pracy przebadano zależność efektywności od liczności populacji, płodności oraz symbolu dont care.

EN

Grammar-based classifier system (GCS) is a new version of Learning Classifier Systems (LCS) in which classifi-ers arf represented by context-free grammar in Chomsky Normal Form. GCS works basically like all other LCS models but it differs from łbem (i) in the covering, (ii) in the matching, and (iii) in representation. Performance of GCS depends on many parameters. In this paper the influance of size of population, fertility and don't care symbol was tested. The set of experiments was performed on context-free grammar called toy-grammar. The experiments revealed some interesting properties of this faetors and showed that this parameters must be tuned very carefully and knowingly in order to improve performance of the GCS.

3

Context-free grammar induction with grammar-based classifier system

Unold O.

Archives of Control Sciences

|

2005

|

Vol. 15, no. 4

681-690

EN

In the paper we deal with the induction of context-free grammars from sample sentences. We present some extensions to grammar-based classifier system (GCS) that evolves population of classifiers represented by context-free grammar productions rules in Chomsky Normal Form. GCS is a new version of Learning Classifier Systems but it differs from it in the covering, in the matching, and in representation. We modify the discovering component of the GCS and apply system for inferring such context-free languages as toy language, and grammar for large corpora of part-of-speech tagged natural English language. For each task a set of experiments was performed.

4

Generowanie gramatyk bezkontekstowych dla potrzeb syntaktycznego rozpoznawania wzorców

Pałka D.

Informatyka Teoretyczna i Stosowana

|

2004

|

R. 4, nr 7

139-147

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.

5

Ewolucyjne generowanie gramatyk bezkontekstowych z wykorzystaniem algorytmów genetycznych

Pałka D.

Elektrotechnika i Elektronika

|

2004

|

T. 23, z. 1

58-63

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.