# Machine Learning (Theory)

## 9/30/2007

### NIPS workshops are out.

Here. I’m particularly interested in the Web Search, Efficient ML, and (of course) Learning Problem Design workshops but there are many others to check out as well. Workshops are a great chance to make progress on or learn about a topic. Relevance and interaction amongst diverse people can sometimes be magical.

## 9/18/2007

### It’s MDL Jim, but not as we know it…(on Bayes, MDL and consistency)

I have recently completed a 500+ page-book on MDL, the first comprehensive overview of the field (yes, this is a sneak advertisement ).
Chapter 17 compares MDL to a menagerie of other methods and paradigms for learning and statistics. By far the most time (20 pages) is spent on the relation between MDL and Bayes. My two main points here are:

1. In sharp contrast to Bayes, MDL is by definition based on designing universal codes for the data relative to some given (parametric or nonparametric) probabilistic model M. By some theorems due to Andrew Barron, MDL inference must therefore be statistically consistent, and it is immune to Bayesian inconsistency results such as those by Diaconis, Freedman and Barron (I explain what I mean by “inconsistency” further below). Hence, MDL must be different from Bayes!
2. In contrast to what has sometimes been claimed, practical MDL algorithms do have a subjective component (which in many, but not all cases, may be implemented by something similar to a Bayesian prior; the interpretation is different though; it is more similar to what has been called a “luckiness function” in the computational learning theory literature).

Both points are explained at length in the book (see esp page 544). Here I’ll merely say a bit more about the first.

MDL is always based on designing a universal code L relative to some given model M. Informally this is a code such that whenever some distribution P in M can be used to compress some data set well, then L will compress this data set well as well (I’ll skip the formal definition here). One method (but by no means the only method) for designing a universal code relative to model M is by taking some prior W on M and using the corresponding Shannon-Fano code, i.e. the code that encodes data z with length

L(z) = – log Pbayes(z),

where Pbayes(.) = \int P(.) d W(P) is the Bayesian marginal distribution for M relative to prior W. If M is parametric, then with just about any ‘smooth’ prior, the Bayesian code with lengths L(z) = – log Pbayes(z) leads to a reasonable universal code. But if M is nonparametric (infinite dimensional, such as in Gaussian process regression, or histogram density estimation with an arbitrary nr of components) then many priors which are perfectly fine according to Bayesian theory are ruled out by MDL theory. The reason is that for some P in M, the Bayesian codes based on such priors do not compress data sampled from P at all, even if the amount of data tends to infinity. One can formally prove that such Bayesian codes are not “universal” according to the standard definition of universality.

Now there exist two theorems by Andrew Barron (from 1991 and 1998, respectively) that directly connect data compression with frequentist statistical consistency. In essence, they imply that estimation based on universal codes must always be statistically consistent (the theorems also directly connect the convergence rates to the amount of compression obtained). For Bayesian inference, there exist various inconsistency results such as those by Diaconis and Freedman (1986) and Barron (1998). These say that, for some nonparametric models M, and with some priors on M, Bayesian inference can be inconsistent, in the sense that for some P in M, if data are i.i.d. sampled from P then even with an infinite amount of data, the posterior puts all its mass on distributions P’ in M that are substantially different from the “true” P. By Barron’s theorems, something like this can never happen for MDL; Diaconis and Freedman use priors which are not allowed according to MDL theory. In fact, MDL-based reasoning can also motivate certain prior choices in nonparametric contexts. For example, if one has little prior knowledge, why would one adopt an RBF kernel in Gaussian process regression? Answer: because the corresponding code has excellent universal coding properties, as shown by Kakade, Seeger and Foster (NIPS 2005): it has only logarithmic coding overhead if the underlying data generating process satisfies some smoothness properties; many other kernels have polynomial overhead. Thus, Gaussian processes combined with RBF kernels lead to substantial compression of the data, and therefore, by Barron’s theorem, predictions based on such Gaussian processes converge fast to the optimal predictions that one could only make make if one had access to the unknown imagined “true” distribution.

In general, it is often thought that different priors on M lead to codes that better compress data for some P in M, and that worse compress data for other P in M. But with nonparametric contexts, it is not like that: then there exist priors with “universally good” and “universally bad” coding properties.

This is not to say that all’s well for MDL in terms of consistency: as John and I showed in a paper that appeared earlier this year (but is really much older), if the true distribution P is not contained in the model class M under consideration but contains a good approximation P’ in M then both MDL and Bayes may become statistically inconsistent in the sense that they don’t necessarily converge to P’ or any other good approximation of P.

Thus: if model M parametric and P in M , then MDL and Bayes consistent. If model M nonparametric and P in M, then MDL consistent, Bayes not necessarily so. If P not in M, then both Bayes and MDL may be inconsistent.

This leaves one more very important case: what if P is in the closure of M, but not in M itself? For example, M is the set of all Gaussian mixtures with arbitrarily many components, and P is not a Gaussian mixture, but can be arbitrarily well-approximated (in the sense of KL divergence) by a sequence of Gaussian mixtures with ever more components? In this case, Bayes will be consistent but it can be too slow, i.e. it needs more data before the posterior converges than some other methods (like leave-one-out-cross-validation combined with ML estimation). In our forthcoming NIPS 2007 paper, Steven de Rooij, Tim van Erven and I provide a universal-coding based procedure which converges faster than Bayes in those cases, but does not suffer from the disadvantages of leave-one-out-cross validation. Since the method is directly based on universal coding, I’m tempted to call it “MDL”, but the fact that nobody in the MDL community has thought about our idea before, makes me hesitate. When I talked about it to the famous Bayesian Jim Berger, I said “it’s MDL Jim, but not as we know it”.

## 9/16/2007

### Optimizing Machine Learning Programs

Tags: Machine Learning jl@ 9:33 pm

Machine learning is often computationally bounded which implies that the ability to write fast code becomes important if you ever want to implement a machine learning algorithm. Basic tactical optimizations are covered well elsewhere, but I haven’t seen a reasonable guide to higher level optimizations, which are the most important in my experience. Here are some of the higher level optimizations I’ve often found useful.

1. Algorithmic Improvement First. This is Hard, but it is the most important consideration, and typically yields the most benefits. Good optimizations here are publishable. In the context of machine learning, you should be familiar with the arguments for online vs. batch learning.
2. Choice of Language. There are many arguments about the choice of language. Sometimes you don’t have a choice when interfacing with other people. Personally, I favor C/C++ when I want to write fast code. This (admittedly) makes me a slower programmer than when using higher level languages. (Sometimes I prototype in Ocaml.) Choosing the wrong language can result in large slowdowns.
3. Avoid Pointer-Based Representations. The way your represent information in your program can have a dramatic impact on performance. My rule of thumb is “for fast programs, it’s all arrays in the end”. As an example, consider maps. STL provides map (a tree-based datastructure) and hash_map (an array-of-pointers data structure). Where a hash_map works, it’s common to observe an order-of-magnitude improvement in performance over a map. (Sometimes you must futz with the hash function to observe this). The Google dense_hash_map replaces the array of pointers with a plain old array and (unsurprisingly) is even faster.

What’s fundamentally happening here is locality: dereferencing pointers is a very expensive operation on modern computers because the CPU runs much faster than the latency to RAM. By converting everything into an array, you compute rather than dereference the location of data. Converting things into an array is not always easy, but it is often possible with a little bit of thought and care.

4. Cached Parsing. Fast algorithms are required for large quantities of data. Unfortunately, the computational process of reading and parsing the data is often intensive. By caching parsed examples in a machine representation format (either in RAM or on disk), a substantial performance boost is achievable. This comes from two sources:
1. You avoid the work of parsing again.
2. The machine representation can be more concise implying improved system caching effects.
5. Deshuffle. Avoid copying information. It’s easy to end up copying data from one place to another. Commonly, the best implementation avoids this, which has strong implications on representation choice.
6. Write less Code. There are many reasons to write less code where you can. For the purposes of optimization, having less code in the bottleneck is the surest way to reduce work in the bottleneck. There are lots of techniques for doing this—some of them are purely syntactic transformations while others involve redesigning the algorithm itself.
7. Don’t trust libraries. In particular, don’t trust library calls inside the bottleneck. It’s often the case that a library function is general purpose while you can get away with a much faster hand-crafted (and inlined) function.
8. Buffered disk I/O. There is a huge difference in performance between reading and writing directly from the disk and doing this through a buffering layer. In general, it’s not obvious which I/O library functions buffer properly. You can experiment, or implement your own buffering system. C++ I/O libraries seem to handle this better than C libraries in general.
9. Amortization. Amortization is a very powerful technique for algorithm optimization. The basic idea is to always make sure that one computation (a secondary one) is amortized by another (your primary computation).
10. Optimize while you wait. There is always a question about how much time should be spent on optimization vs. other aspects of programming. A reasonable rule of thumb is to spend time on optimization when you are waiting for the program to finish running. This is ammortization, applied to yourself.

In all program optimization, it is critical to know where the bottleneck is, and optimize preferentially there. This is fairly tricky on a modern computer because there are many ways that hidden latency can creep in. Tools like gprof and Valgrind can be helpful here, but there is no substitute for having a basic understanding of how a computer works.