Friday, March 16, 2012

Judea Pearl wins Turing Award

(In this age of lightenting fast communication I suspect you all already know that Judea Pearl won the Turing Award. Even so, it is worth posting about.)

Judea Pearl has won the 2011 Turing award (given in 2012). (see here for the announcement). He is not a theorist; however, he did champion the use of probability and graph theory in AI.

Strong AI is the attempt to make computers match or exceed human intelligence. People in Strong AI might see how humans do things and try to get a program to mimic that. Putting aside philosophy (are we all just rather complicated DFA's?) the goal of Strong AI seems to just be hard to do even if it is possible (complexity issues?)

Weak AI has more modest goals (and a much shorter Wikipedia Page)- lets get a computer that can do a well defined task (e.g., Medical Diagnosis) well. They want to get things to work and may very well NOT take how humans do it as an inspiration. Do humans do the kinds of probabilistic calculations that Judea Pearl works with? I tend to doubt it.

Once Strong AI produces real results it is called Weak AI. Once Weak AI produces real world products its called something else (Robotics, Nat. Lang Proc, Vision, there are other examples).

I ask all of the following nonrhetorically. NONE of the questions are meant to question the award.

Did Judea Pearl work in Strong AI to Weak AI?

Was Judea Pearl one of the first people to incorporate serious AI on a more rigorous foundation?

Does AI use serious math? (I know that Control theory does, though is that AI?)

Did Judea Pearl (or his group) build software that is actually being used someplace?

What is the criteria for good work in AI?

Who might be the next AI Turing Award Winner?


  1. 1. Do AI people even make a distinction between "strong" and "weak" AI? I always thought that was something that AI skeptics invented so that they could keep shifting the goalposts.

    2. I don't know but I doubt it. AI is about efficiently finding decent approximate solutions to computationally hard problems (NP-hard problems), so if you want to go in a mathy direction, there's plenty of opportunity for it.

    3. Some AI does.

    4. Don't know, but his work has certainly inspired software that is being used.

    5. Depends on whether it's theoretical work or experimental work. I'm more of an experimentalist, so for me the main criteria is good results (improvement over baseline by some measurement). Pearl's work is more theoretical. Not complexity-theoretical or algorithmic-theoretical though.

    6. Don't know.

  2. I challenge the assertion that Pearl is "not a theorist". Plenty of his work is theoretical in nature. Consider, e.g., a representative paper, "The Structural Theory of Causation":

    Perhaps you are trying to say he is "not a theorist in the current STOC/FOCS mold", or "does a mix of theory and practice." Both true enough, but those are very different assertions. As someone in the STOC/FOCS camp, I would really like us to avoid pissing off other computer scientists by asserting or insinuating a non-inclusive definition of "theory" or "TCS".

    1. Exellent point!- I was not using the term `theorist'

      Would it really piss off a computer scientist if we say
      they ARE NOT a theorist? I didn't mean it as an insult.
      Some would call it a compliment.

    2. I know you didn't mean it as an insult; but researchers who do lots of work of a theoretical nature may understandably be upset if they're referred to as non-theorists. It can easily be interpreted as denigrating their work.

      The issue goes beyond the potential for hurt feelings, however. I think a more important risk, if we use "theorist" and "theory" in non-inclusive ways (as meaning "algorithms and complexity", say, or "STOC/FOCS stuff"), is that we will create barriers in our own thought, and miss the interesting stuff that's going on outside our academic subcommunity, stuff that also has theoretical depth and has potential relevance to influence our own intellectual projects.

    3. It is absolutely the case that that the STOC/FOCS complexity crowd regularly act like the only theory is that, rather limited, brand of theory.

      I think to everyone outside of that clique, Pearl's work is deeply theoretical-- he would never be described as applied. The study of causality and understanding of reasoning under uncertainty gets right at the heart of what it means to be "theory".

      I think the anonymous's above point is right on.

  3. Incidentally, Judea Pearl is also the father of murdered WSJ reporter Daniel Pearl.

  4. I agree with anonymous above.
    Some people in the STOC/FOCS community tend to have a rather narrow
    view of 'theory'.
    Pearl invented a new algorithm 'belief propagation' which had
    enormous influence and impact in many fields. He also proved many
    theorems on graphical models and built a whole theory of causal inference - I would call this 'theory'.
    More generally, some people are doing great theoretical work in AI, learning, signal processing, comp. bio etc.

    1. Yes honestly I am very surprised by Will's post (not in a good way). I won't hide that, though I would not like to comment on it otherwise.

      I also agree with comments below that Geoff Hinton or Vladimir Vapnik might win it some time in the future.

  5. I think Vapnik and/or Hinton will be the next AI/ML Turing award winner.

  6. Did Judea Pearl (or his group) build software that is actually being used someplace?

    This I do not know. However, some of my former colleagues in the CS and Maths Departments at Aalborg University certainly did. See here. The system is, however, based on an algorithm developed by Jensen, Lauritzen (now professor of Statistics at the University of Oxford and FRS) and Olesen, rather on Judea Pearl's polytree algorithm.

  7. 1. Did Judea Pearl work in Strong AI to Weak AI? I don't think many people in machine learning (and even AI more broadly) typically think in these terms. In a sense, Pearl's work was more fundamental - computational mechanisms for describing probabilistic dependence and then using it to make decisions/predictions.

    2. Was Judea Pearl one of the first people to incorporate serious AI on a more rigorous foundation? I'm not sure what the definition is of "rigorous foundation", but I think many people who did work on AI and ML before the late 80's might take offense (Wiener, Minsky, Hinton, Hopfield, McCarthy).

    Does AI use serious math? (I know that Control theory does, though is that AI?) I think there is no doubt whatsoever that machne learning, which is generally considered a subfield of AI, does serious math. Starting with, e.g., PAC learning, and running through, e.g., modern Bayesian nonparametrics. Are COLT papers not doing "serious math"?

    Did Judea Pearl (or his group) build software that is actually being used someplace? I don't know if *he* or his group did, but I think it's quite safe to say that probabilistic graphical models have made their way into an incredible number of practical applications, from the system that sits behind the XBox player matching, to methods that Google uses to index data.

    What is the criteria for good work in AI? I think these are the same general criteria as in other areas of computer science: do you push forward our understanding of important problems? Do you define new important problems? Do you create new useful abstractions? Do you show how to build things that do well on difficult tasks?

    Who might be the next AI Turing Award Winner? I agree that Hinton and Vapnik seem like a good guesses.

  8. Judea Pearl IS a theorist. I am sure Will did not mean this as an offence but still consider a hypothetical scenario where a Bourbakist from the 60s lands here and says that somebody like Endre Szemeredi is not a mathematician (if he wins the Abel prize next week) because he is a combinatorist and not a "pure" mathematician. This sounds like that to me.

    1. Did Judea Pearl work in Strong AI to Weak AI?
    I don't like the distinction between weak AI and Strong AI. But if I were to consider the strong distinctions, then weak AI. But if there would ever be something like strong AI, then his work would be foundational to it. Consider the case where even thinking of recurrent neural nets is useful through the bayesian eye.

    2. Was Judea Pearl one of the first people to incorporate serious AI on a more rigorous foundation?

    Maybe one could say that. I would like to think that Turing and Ray Solomonoff could take that distinction if the set of "first" people is reduced to two. But Pearl was certainly one of the driving forces.

    3. Does AI use serious math? (I know that Control theory does, though is that AI?)
    Absolutely. If you agree Information Theory needs serious math, then so does AI by a "p-reduction".

    4. Did Judea Pearl (or his group) build software that is actually being used someplace?

    No. I don't think so. Because Pearl is a theorist. But it's not a stretch to think that a lot of Bayesian software so frequently used has borrowed from his ideas.

    5. Who might be the next AI Turing Award Winner?
    I don't see anybody winning it in the next five years. Vapnik might be too old by then. Hinton seems like a distant possibility.

  9. Few things seem more pointless than debating whether Pearl is a "theorist"! No, he's not a STOC/FOCS theorist (at least not yet :-) ). Yes, he is a theorist (and probably the world's leading theorist) of causal networks and reasoning about uncertainty.

    I think a much more productive question is: given that there exists this wonderful body of theoretical work in computer science which falls mostly outside the STOC/FOCS purview, how should we now go about assimilating it, and making it part of our purview? :) Or less contentiously: what are the open problems raised by Pearl's work that STOC/FOCS people could profitably address?

    I've seen NP- and #P-hardness results for various problems involving inference on Bayes nets, but that doesn't strike me as the most exciting direction.

    One vague question I've been toying with since the summer is the following. "Ordinary" statistics (where the goal is finding a hypothesis that predicts most future data) is to Valiant's PAC model, as "Pearlian statistics" (where the goal is unraveling the causal relationships) is to what? I.e., what can be said about the sample complexity and computational complexity of learning causal relationships between variables -- given, presumably, the ability to perform certain "controlled experiments" on those variables?

    Work by Dana Angluin, James Aspnes, et al., on learning circuits using "value injection queries", could be seen as an excellent start on that question, but it remains to make explicit contact with what Pearl did.

  10. It seems a rather one-sided debate, frankly-- I suppose in that sense it's pointless. But perhaps less so if it discourages the complexity crowd from ignoring the rest of theory.

    "I think a much more productive question is"-- well, perhaps that's the more productive query for the STOC/FOCS crowd, but not necessarily the rest of the theory world.

    Perhaps the more productive question is what tools that have been generated by the computational complexity crowd have the potential for impact on the greater theory world.

  11. I also don't think that the post was greatly articulated but it's not a big deal, I guess this discussion is good and can generate some awareness about his results that are relevant for the overall CS community (theory included).

    I have been reading Pearl in the last few years and his results are really theoretical. I even already heard from other peers in the AI community complains on how theoretically inclined Pearl is.

    I don't have much knowledge about his book on Heuristics from 1984, but what I heard is that he formalizes the basic ideas behind the subject. Personally, the more interesting part of the history starts in his 1988 book when the AI research was fighting around the question of what was the correct language to represent and reason with common sense knowledge.

    What's more mathematical than finding the most suitable language for a given task?

    At this point I recall some logic classes when we discussed about the emergence of mathematical logic as a discipline in the beginning of last century, and all the stories on how great mathematicians made mistakes for the lack of an adequate formal language.

    But Pearl's question was not only on representation, but he was also interested in space complexity related to the storage of knowledge as well as the time complexity that could make reasoning feasible.

    Is this not theoretical? I am kinda bias but it's the best possible theory in the world since we use all computer science background and still have contact with the reality. It's very different than ad hoc methods.

    Interestingly that at that time there was a line of researchers betting on pure logic (starting with the propositional one), and Pearl and others showed that this was not the best choice.

    How? They formally generalized propositional logic adding a layer of probability on top of it, I guess this is amazing. (And also there were clear examples showing very pathological behavior.) Not only that, but there were some deep insights on how to connect the ancient area of Euler's graph theory with Kolmogorov's probability theory, what was rather surprising and powerful. There're plenty of theoretical results by him, Geiger, Verma, Paz, and other of his colleagues in this line of research. The area exploded early 1990 since his foundational work.

    After that he focused his attention on Causality and I am quite excited about his 2000's book about the subject. The problem on how to formalize causal notions was open for centuries, and we can trace back it for the great philosophers, mathematicians and scientists, all of them struggling on how to formally define simple concepts as 'causes' and 'effects'. This problem looks non-intuitive to us since as human beings we have such a great power and intuition on these notions, but the question boils down on how to formally do that. Again, he not only gave formal dressing for these and related concepts but also took care on complexity and computability.

    There're some interesting results in the line of impossibility a la the ones that we have in complexity theory, but in regard to causality. For instance, we have typical statements in TCS about impossibility of performing a given task efficiently (unless P = NP), and some of his results state that it is impossible to make a given causal claim with a specific set of assumptions (casted even as a decision problem). There's much more but I am not trying to be exhaustive.

  12. So Endre Szemeredi DID win the Abel Prize. :)

  13. What an absurd post. It's hard to imagine that the intent was anything other than to insult. If Pearl is not a theorist, exactly what is he then?

  14. 1) Calling someone a theorist or a non-theorist is not an insult
    or a compliment.

    2) If I had labelled this post `THEORIST WINS TURING AWARD'
    that doesn't seem quite right either.

    3) The most intelligent discussion of Pearl and Theory that I know of is Scotts comment above. See that please