Basically he brought Bayesian Networks to machine learning. He did a lot in their structure and in particular efficient/approximate inference on Bayesian Networks. He has been contributing brilliant ideas since the early 80s I think.
Search belief propagation, junction tree algo, markov blanket, belief propagation statistical physics. The last search showing his ideas finding use beyond where he introduced them. Whenever ideas keep showing uses in different places especially in something as well evinced as the thermodynamic/information link then you know you have done something profound.
A few years ago I looked up his earliest papers, and it's interesting that his work on Bayesian networks essentially seemed to start as an effort to detect causality among sets of random variables, i.e. given a Bayesian network, which random variables can be said to "cause" others? Of course, Bayesian networks start by assuming you know every random variable's distribution, so verifying independence is easy but finding it is hard. I've always thought an interesting research project would be to try the same approach with correlation functions instead of distributions, and see how far you can get.
Well, as the linked article says, he basically coined the term "Bayesian network" and developed much of the underlying theory (e.g., which kind of independencies it can/cannot capture). This was arguably a crucial step for many areas of modern AI in terms of dealing with uncertainty, cf. the full ACM press release: http://www.acm.org/press-room/news-releases/2012/turing-awar...
He is also credited with first describing the ever-popular belief propagation algorithm for approximate reasoning in Bayesian networks and graphical models in general.
Judea Pearl's work wasn't about machine learning so much as introducing the idea of using probability to AI reasoning. In the early days uncertainty was handled in AI using ad hoc techniques (e.g. Mycin) and the use of probability was regarded as too complex because the joint probability distribution grows exponentially with the size of the domain. Pearl showed that probability could be used for reasoning in a natural way using conditional independence to simplify the joint, and that belief networks behaved in interesting ways (e.g. "explaining away"). He then described an elegant algorithm for the propagation of probbilities in a simple form of a belief net (trees). This still forms the basis of inference today, most algorithms create a clique tree from multiply connected networks and use message passing. Shacter et.al. later showed that all exact algorithms are a form of this method. I'm a big fan as you can tell.
You've probably heard of Hidden Markov Models. They're widely used in many machine learning applications. An HMM is just a simple, easy-to-compute Bayesian inference network.
The idea of Markov chains predates Pearl. His work was a demonstration of the accuracy and power of Bayesian inference networks. He revitalized that idea at a time where programmers were just beginning to have the data and processing power to apply machine learning.
Bayesian Networks tend to be used not as classifiers but a tool to explore joint probability distributions.
Interestingly related to your topic, HMMs and Naive Bayes are related in that HMMs are kinda like the sequence sensitive version. HMMs and Naive Bayes are generative models. They both model/estimate a joint probability on the data with very strong conditional independence assumptions. Where as Logistic regression and Conditional Random Fields estimate the conditional probability of the output/labels directly.
HMMs : Naive Bayes as linear chain CRFs : Logistic Regression. CRFs are state of the art at sequence and time series prediction. I have not yet gotten my head round them though. The relationship between logistic regression and naive bayes is not commonly known (although the comparison of log reg to a simple Neural network is common). Knowing when Logistic regression outperforms Naive Bayes is useful (simple rule of thumb: logistic regression less sensitive to independence assumption, more data use log reg, less data use naive bayes). I've implemented a multi class sparse regularized logistic: SMLR. Its up there with linear SVMs but simpler but also gives a probability.
PG's old spam filter (http://www.paulgraham.com/spam.html) is another example of applied Bayesian inference. Not directly related to Pearl's work, but he basically deserves credit for the wider renaissance in Bayesian techniques.
> Not directly related to Pearl's work, but he basically deserves credit for the wider renaissance in Bayesian techniques.
Post hoc ergo propter hoc? The success of naive Bayes classifiers for spam filtering must have improved popular perceptions of Bayesian techniques, but let us not go overboard.
