A breadth-first search through the arts & sciences

Disclaimer: these writeups aren’t detailed to be sufficient for learning or even making sense of the material; they’re just detailed enough to force myself to re-work all the theorems from scratch (and littered with enough keywords so that I can Google up my more detailed handwritten notes). I don’t have handwritten notes for the first few lectures, but I’m writing them up anyway, just to make myself prove all the theorems.

Learning Disjunctions (or Conjunctions): Set the initial hypothesis to everything (2n). Cross off at least one variable for each mistake: MB = . We basically do the same thing for conjunctions.

Decision Tree: See notes for definition. Size = number of nodes = .

How powerful are these compared to decision lists? Just consider parity! We need to remove the restriction that each block is a single boolean variable to express an arbitrary DT as a DL.

How large a DL do we need then? Call an n-decision list one with blocks of size n. We can obviously convert a DT to a DL by traversing the tree, and putting each traversal in a block. How can we do better? Consider the concept of rank: rank of a leaf = 0. Otherwise, rank = max(rank(,) when and rank otherwise.

What’s the rank of a tree with leaves? At most : by induction, number of leaves is at most . But any rank DT is a k-DL: Induct on the depth of the tree. Let $x_i$ be the variable at some level. WLOG, has rank . So our DL is the DL of with $x_i$, and the DL of .

So we can learn a DT in .

What’s the next step up in complexity from a DT? DNF (Sum of products for us EE folks). Why is it a step up? We can take any DT and turn it into DNF by traversing the tree and setting that traversal to one of the conjunctions.

Augmented Decision Tree: this is just a DT with DNF formulas at the leaves. If this is a t-DT, any poly sized DNF with terms over variables has a -DT. Consider all terms with length > t: take the most common variable, and put it at the root. Repeat.

Now we can extend our DL to have DNFs at the outputs instead of 0s and 1s. Say we have an augmented DT with rank R and term length t. We can turn an R-DT into a extended R-DL, and convert that into an (R+t)-DL by pushing variables from the DNFs into the decision blocks. This means we can turn an term variable DNF into a -DL. This is minimum when , so our MB is

‘05 scribe notes

Scribing and writing up summaries of the gnofai MCMC tutorial made me realize how useful it is to force myself to review my notes by writing up summaries, so I’m going to write up searchable summaries of my handwritten notes for the Computational/Statistical Learning Theory class Adam Klivans and Pradeep Ravikumar ran last semester. I missed the first month of class due to a scheduling conflict, but I’ll write up summaries of those lectures anyway.

Apropos of nothing, I’m still shocked by how friendly and accommodating people are here at UT. Adam was nice enough to move the class to a time that would work for me even though I was just another nameless first-semester grad student from another department.

WARNING: these writeups aren’t detailed to be sufficient for learning or even making sense of the material; they’re just detailed enough to force myself to re-work all the theorems as exercises (and detailed enough that I can Google up my handwritten notes).

Mistake Bound (MB) model: the learner wants to learn some . The learner gets some unlabeled example, , makes a prediction based on , and then finds out the truth, . The learner updates if it made a mistake (which is equivalent to always being able to update for obvious reasons).

Definition: A concept class, , over is efficiently learnable in MB if there exists an algorithm such that for any $c \in C$, A has an MB and its running time in each trial is also , where is the description length of c under some encoding scheme. If the MB is instead of , i.e., if it’s poly in the “size” of the function being learned, as opposed to poly in the number of features in the domain (which we care about in the high-dimensional case), then is attribute efficient.

Learning Decision Lists: We can learn a DL () of length k with MB . Start with everything at the top of the list, and push it down every time we make a mistake, a.k.a., use the bag algorithm. This gives us . Note that this doesn’t actually produce a DL, but the hyp we get will be consistent with . Of course we can get a DL from our list of bags by picking arbitrarily from each bag.

‘05 scribe notes (which seem to be broken at the moment)
‘06 scribe notes