2010-10-08: More on the mistake-bounded model

Today:

• we finished the proof that linear functions F^n --> F for a field F are learnable with n mistakes
• we showed that subspaces of F^n are learnable with n mistakes (furthermore, they're positive mistakes)
• we showed that if a concept class C is learnable from b positive mistakes, then the class DIFF_k(C)  of nested differences of at most k concepts in C is learnable from b*k mistakes.
• we argued (by informal "reductions") that the set of conjunctions of literals on n variables is learnable  with 2n mistakes, and that concepts specified by non-homogeneous linear equations over a field are learnable with n+1 mistakes.

Later in the course, we will define formally this idea of "learning reduction". But, for the time being, we proposed:

Exercise 1: Show that 2-CNF are learnable with O(n^2) mistakes by reduction to conjunctions of boolean variables.

Exercise 2: Show that n-variable, degree-d polynomials over a field are learnable from O(n^d) mistakes, by reduction to the degree-1 case.