Speaker: Wei Luo (joint work with Oliver Schulte)

Date and Time: Thursday June 9, 2005 @ 1:30pm

Place: ASB 9705

Title:

Mind Change Efficient Learning

Abstract:

This talk discusses efficient learning with respect to mind changes, a
complexity measure of incremental learning.
Our starting point is the idea that a learner that is efficient with
respect to
mind changes minimizes mind changes not only globally in the entire
learning
problem, but also locally in subproblems after receiving some evidence.
Formalizing this idea leads to the notion of "uniform mind change
optimality".
We characterize the structure of language classes that can be
identified with at most $\alpha$ mind changes by some learner (not
necessarily effective): A language class $\mathcal{L}$ is identifiable
with
$\alpha$ mind changes iff the accumulation order of $\mathcal{L}$ is at
most
$\alpha$. Accumulation order is a classic concept from point-set
topology.
To aid the construction of learning algorithms, we show that the
characteristic property of uniformly mind change optimal learners is
that
they output conjectures (languages) with maximal accumulation order.
We illustrate the theory by describing mind change optimal learners for
various
problems such as identifying linear subspaces and one-variable
patterns.
The talk will be self-contained; no background in formal learning
theory is assumed.

http://www.cs.sfu.ca/~cl