Thursday, Oct 23, 1:30 pm

Applied Science Building 9705

Descriptive Complexity for Learning Problems

Wei Luo, Simon Fraser University

Abstract: In this presentation, I characterize the topological or information-theoretic complexity of language learning problems. In a language learning problem, the learner has to guess a target language given increasing samples of strings drawn from the target language. The learner succeeds if its guesses converge to the correct language. Inductive Logic Programming and learning formal grammars are instances of the language learning problem.

A common way to measure the complexity of a language learning problem is in terms of how many times a learner may have to change its mind before it settles on the target language. My main result gives necessary and sufficient conditions for learning a language with a given bound on the number of mind changes. It turns out that the classic topological concept of accumulation order, introduced by Cantor in the 19th century, characterizes the mind change complexity of languages.