Friday, March 11, 2011

Les Valiant wins ACM Turing Award

The ACM recently announced that Les Valiant is the newest recipient of the Turing Award, which is the highest award in the field of computer science. Les Valiant is widely considered to be one of the main founders of modern machine learning. His concept of PAC learning revolutionized the way we reason about machine learning algorithms. The PAC framework provides a way to formally characterize hypothesis testing, and thus also gave justification to concepts like Occam's razor.

The typical way to design programs that you can "trust" to do the right thing is to both (A) empirically verify and (B) formally prove its correctness. For both (A) and (B), one must have a common language or set of benchmarks with which to compare different algorithms. For machine learning programs, ways to reason about (B) were few and far in between before the PAC learning framework. You might say that machine learning before PAC learning was like computing before Turing machines.

In honor of this occasion, I decided to finally read Valiant's seminal paper, "A Theory of the Learnable". It's definitely a good read, and understandable for anyone with working knowledge of computer science. In fact, I found it striking that the paper still felt quite "modern" even after all these years and subsequent advances.

No comments: