Algorithmic Learning Theory

Learning Picture


Algorithmic Learning Theory investigates what concepts can be learned depending on the model of learning, of which there are a lot. In this project, the emphasis is not on whether or not a concept is learnable, but on how fast. The speed of learning can be measured in different ways. The following two examples consist of two learning algorithms. The first one learns from positive examples and the second from queries.

Both algorithm learn one-variable patterns. A one-variable pattern is a word that can also contain the variable symbol x. E.g., bxabxaa is a one-variable pattern. The language generated by a one-variable pattern consists of all words you get when you substitute a non-empty word for the variable symbol in the pattern. The language of bxabxaa contains, e.g., the word bbababbabaa, which you get by substituting bab for x.

One-variable pattern languages are a very simple class and are well suited to serve as an example of a learnable concept.

Learning from positive examples

The first algorithm computes a descriptive pattern. It is known that descriptive patterns converge to the correct pattern. The input is a sample consisting of several strings. You can enter the sample in the following text area using one line for each string.

If you provide enough examples, you will get the correct answer eventually.

If you press the button labeled ``Learn'' the algorithm answers with a descriptive one-variable pattern.

Learning from queries

The next algorithm learns a one-variable pattern with superset queries. Here you think of a one-variable pattern and then answer superset queries posed by the algorithm.

The algorithm presents a pattern p and you have to answer yes if the language generated by your pattern is contained in the language generated by p. Otherwise you have to answer no.

If you answer no the algorithm may ask you for a counterexample. In that case you are asked to enter a string that is contained in the language of your pattern, but not in the language of p.


Links to Related Sites: