Bump Hunting

There are big courses, and then there are BIG courses

2011-08-17T15:26:00.000-07:00

Having TA'd large lecture courses in grad school, I know how much work goes into teaching them. But this is an entirely different scale:

“Stanford University has opened up to the public an introductory artificial intelligence class, taught by two luminaries in the field: 70,000 people have signed up to receive registration information for the course (blogs.scientificamerican.com)”

70,000 is a lot of assignments to grade. I feel feel sorry for the TA’s.

Bill O'Reilly is Such an Embarassment

2011-02-07T00:15:00.000-08:00

Bill O'Reilly's gall, hubris and ignorance are astounding:

Fox has to get rid of him. Who cares how much money he brings in. If they had any standards, they'd let him go. Stephen Colbert put it best (after the Anderson Cooper bit). O'Reilly's understanding of the world really is from the 13th century.

NP Incomplete Problems?

2010-08-13T23:44:00.000-07:00

In the wake of Vinay Deolalikar's maybe proof that P != NP, I found myself thinking about the old P ?= NP question. I realized that while I know of a many problems that are NP complete, I don't know of any problems that are:

1. in NP
2. not known to be in P
3. not known to be NP-complete

Are there such "NP incomplete" problems? And has anyone proved that if P not equal to NP, such NP-incomplete problems must exist? It would be surprising if they didn't since the NP-complete problems are the hardest problems in NP. Without an NP-incomplete class, there would be a sudden jump from so-called "easy" (in P) to hardest (NP-complete).

NBC's "Law and Order" receives ultimate punishment

2010-05-27T22:12:00.000-07:00

There may no longer be "Law and Order" in the world, but at least there's justice. Belinda Goldsmith reports that the long-running criminal justice drama has finally been canceled. Unfortunately, we will still be victimized by it's various spin-offs, as they are slated to continue.

A Supreme Court without Protestants?

2010-05-10T21:41:00.000-07:00

Headline from today's Boston Globe on the nomination of Elena Kagan: "If she’s confirmed, court would have no Protestants." Who is this relevant to in 2010? I kind of thought we were past this stuff when we elected a black man for president...

2009-09-02T12:20:00.000-07:00

The following seems note-worthy. Codexon reports that in Python, an int on a 32-bit machine now takes up 12 bytes of storage. This seems a little excessive. I mean how much tag space is really needed here? (Or is there other information stored as well? e.g., GC reference counts.)

What are good prequisite textbooks for someone interested in machine learning?

2009-07-22T15:07:00.000-07:00

As mentioned in the last post, machine learning requires a good amount of background knowledge just to make sense of the topic. The core subject areas are:

calculus
linear algebra
combinatorics / discrete math
probability
statistics
information theory
real analysis
optimization theory

The following is a list of basic, introductory textbooks for each of these subjects :

Calculus and Analytic Geometry by Thomas Finney. This was the plug and chug book we used in my college courses.

Linear Algebra and its Applications by Gilbert Strang. Gilbert Strang also has another book, Introduction to Linear Algebra, which I haven't read. I'm guessing either would be fine.

Concrete Mathematics by Ronald L. Graham, Donald E. Knuth, Oren Patashnik.

A First Course in Probability by Sheldon Ross. Additionally helpful is William Feller's An Introduction to Probability Theory and Its Applications, Vol. 1.

Mathematical Statistics with Applications by Wackerly, Mendenhall and Scheaffer. This is a pretty standard stats book.

Elements of Information Theory by Cover and Thomas. I can't recommend this book highly enough.

For real analysis, Marsden and Hoffman's Elementary Classical Analysis is pretty standard. It's not a great book though. I find it annoying that the proofs are left for the ends of the chapters.

A First Course in Optimization Theory by Rangarajan K. Sundaram.
The Mathematics of Nonlinear Programming by Anthony L. Peressini, Francis E. Sullivan and J.J. Jr. Uhl

These books are very basic, at the undergraduate level for the most part. However, if, like me, you weren't a math or engineering major, you will probably find them useful for quickly filling in the gaping holes in your education. Later I'll post some introductory books at the graduate level.

What books should I read if I want to learn about machine learning?

2009-07-03T19:25:00.000-07:00

I see this question posted on the web not infrequently and I wanted to throw in my two cents. The real answer is that it greatly depends on your background and your interests. Machine learning is vastly interdisciplinary, and the disciplines it builds on require individual study before learning about machine learning really becomes fruitful. Aside from computer science, the prerequisite subjects for machine learning are, at the very least, real analysis, probability, statistics, information theory and optimization theory --- Quite a list!

I was doing computer science at the undergraduate level when I became interested in machine learning. Having taken courses in basic algorithm design, theory of computation, programming languages, and AI, I thought I had the necessary background to start doing some machine learning. After all, it's still computer science, right? Wrong --- in fact totally wrong. The thing about machine learning as opposed to many other areas of computer science is that it's continuous rather than discrete math, or a lot of it is at least. So if you have a math, physics, engineering or statistics background, you are in much better shape to start reading literature on machine learning than if you are versed in fundamental CS. Of course, CS is useful, too, but it's less necessary in getting started. In fact, many of the best people in machine learning did not come from the computer science.

The other thing that makes answering this question difficult is that machine learning has more than a few sub-disciplines. Picking the right book really depends on which of these you want to delve into. Do you want to do theory? Applications? Applications in a particular domain? If you want to do natural language processing, then you shouldn't get a book on kernels. However, if you want to understand machine learning in general, then you should get a survey book. There are some decent survey texts out there, but the better ones are only useful given some mathematical maturity. Even then, it may be rough going.

The best intro-to machine learning textbook I know of which is relatively accessible to people with a traditional computer science education is Tom Mitchell's Machine Learning. However, it is rudimentary and is quickly becoming completely out of date (how sad!). There is also Russell and Norvig's Artificial Intelligence: A Modern Approach, which covers topics in more classical AI at the expense of machine learning topics.

I think the best survey texts on machine learning are probably Hastie, Tibshirani and Friedman's Elements of Statistical Learning, whose recent arrival in an expanded 2nd edition is what prompted me to write this post, and Chris Bishop's Pattern Recognition and Machine Learning, which attempts to be the end-all-be-all modern machine learning textbook. However, these books require more facility in the above prerequisite subjects than the average computer scientist usually has. Another commonly cited survey book in the same vein is Duda, Hart and Stork's Pattern Classification. It's more basic than the previous two and I've found it to be less useful as well.

If you are interested in natural language processing, you are in luck because the survey texts are more accessible to a general CS audience. There's Manning and Schutze's Foundations of Statistical Natural Language Processing, and Jurafsky and Martin's Speech and Language Processing. Fred Jelinek also has a wonderful book, Statistical Methods for Speech Recognition.

So these are my suggestions. Other people will have others (which I am eager to hear about). Later I will post my suggestions on good textbooks for the prereqs. Happy 4th of July, everyone.

--------------------------------------------------

Here are a couple of additions to the ML book list, and best of all, they are freely available online:

(1) Nils J. Nilsson's Introduction to Machine Learning, Draft of Incomplete Notes is similar in spirit to Tom Mitchell's book.

(2) David MacKay's Information Theory, Inference, and Learning Algorithms. This book has a different focus from the other intro books listed above. Rather than provide a comprehensive survey of machine learning methods, it seeks to introduce machine learning by way of information theory and Bayesian modeling, and thus put the topic on solid theoretical footing. Its focus is also on developing the intellectual abilities of the reader, which frankly makes it a far better introduction than the others above. And from I've read so far, MacKay's writing is insanely entertaining. I'm definitely looking forward to having more time to read this gem.