Change search
ReferencesLink to record
Permanent link

Direct link
Genetic Programming for Grammar Induction.
KTH, School of Computer Science and Communication (CSC).
2011 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In this paper the problem of Grammar Induction is approached with Genetic Programming. We used the framework PerlGP to implement the evolution of grammars.

A simple grammar was used to generate an artificial text which in the next step was used for evaluating how grammars were evolved by the GP method. We evaluated the influence by some variations: how many and by what frequencies words were used in the artificial text, if the grammar in its entirety needed to match phrases or not. An implementation to allow reuse of parts of the grammar as well as recursion was also evaluated. The results were encouraging though the implementation scaled badly with the number of occuring words in the text. In our experiments with natural texts the texts where thus first tagged with word classes to reduce the vocabulary used in the GP process.

Abstract [sv]

I denna rapport angrips problemet att automatiskt härleda grammatiker med hjälp av genetisk programering (GP). Ramverket PerlGP användes för att att implementera evolution av grammatiker.

En enkel grammatik användes för att generera articifiell text. Denna text användes för att evaluera hur grammatiker utvecklas med GP. Vi evaluerade inflytandet av några variationer: hur många och med vilken frekvens ord användes i den articifiella texten, omifall hela grammatiken behövde matcha fraser eller inte. En implementation som tillät återanvändning av delar av en grammatik samt rekursion evaluerades också. Resultaten var uppmuntrande men implementationen skalade dåligt med antalet förekommande ord i texten. I våra försök med naturliga texter taggade vi därför först orden med ordklasser för att reducera den använda vokabulären vid den genetiska programmeringensprocessen.

Place, publisher, year, edition, pages
Trita-CSC-E, ISSN 1653-5715 ; 2011:077
National Category
Computer Science
URN: urn:nbn:se:kth:diva-130776OAI: diva2:654223
Educational program
Master of Science in Engineering -Engineering Physics
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

Other links
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link