15-859(B) Machine Learning Theory            03/19/02

* Cryptographic hardness results for learning
* Angluin's algorithm for learning DFAs
=========================================================================

CRYPTO-BASED HARDNESS RESULTS FOR LEARNING
------------------------------------------

Last time: If can learn DFAs in PAC model, then can learn NC^1
circuits in PAC model.

Today: If can learn NC^1 (equivalently, boolean formulas), even with
membership queries, and even weakly over the uniform distribution,
then can factor.  (Kharitonov).

****************************
--> see notes from last time.
****************************


ANGLUIN'S ALGORITHM FOR LEARNING DFAS
=====================================

Now, a neat algorithm by Dana Angluin for learning DFAs from
membership queries and counterexamples.  

- Membership query: propose x, get f(x).
- Counterexample: propose h, get x such that h(x) != f(x) if one exists.
  (Sometimes called "equivalence queries")

Goal: we want #queries, #counterexamples, running time to be
polynomial in the size of the target DFA.  (and, technically, in the
size of the largest counterexample)

This is basically the same as the "query + mistake bound model".  You
can also replace counterexamples with PAC: just test h on D, and if
you don't see a counterexample, then you know that whp h has low
error.

 - Passive observation alone is not sufficient (by crypto results).

 - Why are MQs alone not sufficient?  I.e., why can't we hope
   to get an exact model of f from just a polynomial number of queries?

   "combination-lock automata".


Another view: learning a deterministic finite state device, or
learning a deterministic finite state environment, when a "reset
button" is available.

*********************
--> See slides.
*********************
--> See other notes
*********************


How to use the counterexample to figure out where we went wrong?  Key
trick: look at all ways to split the counterexample into a (prefix,
suffix).  For each split, replace prefix with our predicted string in
S and make a membership query.  We are guaranteed to find two adjacent
pairs (pref_i, suff_{n-i}), (pref_{i+1}, suff_{n-i-1}) whose outputs
differ, and this gives us a new experiment (specifically,
suff_{n-i-1}) to use.


Learning algorithm creates up to n rows in top part of table and n*|A|
rows in the bottom part.  # experiments is at most n since each one
distinguishes a new state. 
	-> # EQ's is at most n
	-> # MQ's is at most n(|A| + 1)*n + n*log(m)
         	(first term is the number of rows times the number of
		experiments (i.e., the table size), and the second is how many
		queries it takes to find the next experiment given a
		counterexample * number of counterexamples.)
		(m = max length of counterexample)

What if there is no reset?  -> next time.