6 - About combinatorics

Summary

All generalisations, with the possible exception of this one, are false.

Kurt Gödel

A child of five would understand this. Send someone to fetch a child of five.

Groucho Marx

In order to get a better grasp of the problem of learning grammars, we need to understand both how the individual objects we are trying to infer are shaped and how the set of these objects is structured. This will enable us to formally state learnability and non-learnability results, but also to identify and study the search space and the operators to move around this space; in turn, this will enable us to develop new heuristics.

The first results are mainly negative: if to learn a grammar you have to solve some intractable combinatorial problem, then only wild guessing is going to allow you to identify or infer correctly, but then you are relying on luck, not on convergence probability. This sort of result is usually obtained by reductions: typically, we show that if a well-known hard problem can be solved via a learning algorithm (perhaps with some error, so it may depend on a randomised version), it will mean that something is wrong. The learning algorithm cannot do what it promises to do.

But working on the combinatorics of automata and grammars also helps us to build intuitions that contribute to designing learning processes.