Gitta ("Grammar Induction using a Template Tree Approach") is a method for inducing context-free grammars. It performs exceptionally well on datasets with latent templates, e.g., forum topics, writing prompts, and output from template-based text generators. The found context-free grammars can easily be converted into grammars for use in grammar languages such as Tracery & Babbly.

Demo

A demo for Gitta can be found & executed on Google Colaboratory.

The code itself is publically available on Github

Example

GITTA can detect textual structures in text by discovering templates. Additionally, it detects which elements are likely shared as slot values between templates. These are then outputted as a regular grammar, which can generate many similar texts.

For example, when given the following five examples:

• I like cats and dogs
• I like bananas and geese
• I like geese and cats
• bananas are not supposed to be in a salad
• geese are not supposed to be in the zoo

It then discovers the following grammar:

• S -> (<B> are not supposed to be in <C>) | (I like <B> and <B>)
• B -> bananas | cats | dogs | geese
• C -> a salad | the zoo

In turn, this generates all the following 24 similar texts:

• dogs are not supposed to be in the zoo
• cats are not supposed to be in a salad
• I like geese and cats
• cats are not supposed to be in the zoo
• bananas are not supposed to be in a salad
• I like dogs and dogs
• bananas are not supposed to be in the zoo
• I like dogs and bananas
• geese are not supposed to be in the zoo
• geese are not supposed to be in a salad
• I like cats and dogs
• I like dogs and geese
• I like cats and bananas
• I like bananas and dogs
• I like bananas and bananas
• I like cats and geese
• I like geese and dogs
• I like dogs and cats
• I like geese and bananas
• I like bananas and geese
• dogs are not supposed to be in a salad
• I like cats and cats
• I like geese and geese
• I like bananas and cats

GITTA can thus discover similar patterns in a text and exploit these to generate text similar to the input text, even when few examples are given.

In the paper, we also found that it can reverse engineer human-created grammars in Twitterbots from just a few tweets.

Paper

If you would like to refer to this work, or if you use this work in an academic context, please consider citing the following paper:

@article{winters2020gitta,
    title={Discovering Textual Structures: Generative Grammar Induction using Template Trees},
    author={Winters, Thomas and De Raedt, Luc},
    journal={Proceedings of the 11th International Conference on Computational Creativity},
    pages = {177-180},
    year={2020},
    publisher={Association for Computational Creativity}
}

Or APA style:

Winters, T., & De Raedt, L. (2020). Discovering Textual Structures: Generative Grammar Induction using Template Trees. Proceedings of the 11th International Conference on Computational Creativity.