AI-Complete

Google is your friend

2005-02-08T20:33:00.000-07:00

After a long hiatus, I'm going to start blogging again with this paper on "Automatic Meaning Discovery using Google" by Paul Vitanyi (the Kolmogorov complexity guy) and Rudi Cilibrasi, which has generated a flurry of interest, even sparking a slashdot discussion. The essence of the paper is this : Using the page counts returned by the Google search engine to define a distribution over words and word pairs and using it to automatically extract meaning from the world wide web. For example, the number of page counts returned by the query "horse"+"rider"(about 2,710,000) versus "hoarse"+"rider"(31,400) gives some information on the semantic associations between these words. In this way they are trying to exploit the huge but low-quality information source that is the world wide web to generate a lexicon and an ontology, in comparison to Cyc for example which is building a hand-crafted knowledge base.

The idea has been suggested before but this is the first realistic attempt that I know of. Their approach is interesting for two reasons. First, it has strong theoretical justification: an argument based on Kolmogorov complexity and optimal string encodings. Basically the metric they use, called the Normalized Google Distance, is universal w.r.t. the Google Distance of individual authors ie. the NGD of any two words is within a linear factor of the GD of those words in the web documents originating from any one source.

Secondly they have impressive experimental results, especially one involving the heirarchical classification of a set of numbers and colours. Another set of experiments uses the NGD between an instance word and a set of "anchor" words to define a set of features that is used as input to an SVM. By using the correct set of anchor words, they were able to classify all words that are "electrical" terms with 100% accuracy.

Godel Demystified

2004-12-07T15:07:00.000-07:00

Apu Kapadia asked me some questions today about "Logic and Godel and stuff" and I sent him a long mail putting it all in a nutshell. I thought it might be useful to reproduce it here. The following is a massively condensed description of First Order Logic and its (in-)completeness theorems. I have not ventured into any philosophical speculations. A good book for that would be Douglas Hofstadter's Godel,Escher, Bach.

Every First Order Logic theory is in a language (say L) with 3 kinds of symbols - predicates, constants and functions. So you can make a statement like P(a,b) ^ Q(f(b),c) which means "P holds of a and b, and Q holds of f(b) and c".

To give semantics to a first order formula, each of these symbols must have an interpretation. This is done by using what is called an L-structure. There are two things required for an L-structure, first a set of objects called the universe, and an interpretation for each symbol of L w.r.t this universe. So each constant refers to some element of the universe and each function symbol (predicate symbol) refers to a function (relation) on the domain of these objects. Depending on how you define your L-structure M, it can either satisfy a First order formula 'phi' written in the language L, or not. If it does, it's called a model and you write M |= phi. For eg. suppose G= (U, @) is an L-structure for the language L with just the relational symbol P, s.t. @ is commutative over U. @ is the interpretation of P in G. Therefore G |= P(x,y) = P(y,x).

Suppose you have two formulas phi and psi s.t. every model of phi is a model of psi, then you write phi |= psi .

Now we need to define provability. First we define a set of syntactic manipulations you can do to a formula to get another one. If by taking some fomulas (axioms) Sigma and doing those manipulations you get phi, then you can write Sigma |- phi. For eg. Modus Ponens: if you have Sigma |- phi => psi and Sigma |- phi, then you can say Sigma |- psi .

Godel's Completeness theorem states that, Sigma |- psi iff Sigma |= psi. So in one sense the notion of provability captures the notion of truth, but only if by truth you mean what statements your axioms can entail.
Godel's Incompleteness theorem however says this: Let L contain the symbols {0, S, +, x, <}. Consider an L-structure NN defined in this way: Take N as the set of natural numbers and define the other symbols in the obvious way (S is the successor function so S(0) is 1, S(S(0)) is 2 etc). Let Th(NN) be all the formulas written in L that are true in the model NN. Can we find an axiomatization of Th(NN), ie. a set of formulas Sigma, s.t. if NN |= phi then Sigma |- phi ? Can we do it so that Sigma is computable ie. there exists an algorithm which recognizes if some formula belongs in the set of axioms Sigma? Godel showed that this was impossible. Church showed in addition that Th(NN) is algorithmically undecidable.

So therefore, when you're interested only in the "truth" w.r.t a particular model NN, then your proof system will be incomplete.

Finally to clear up a common misconception, the Continuum Hypothesis is not an example of such a Godel statement (true but not provable). The truth of the CH depends on the choice of the model you choose from among the models that satisfy the axioms of Set theory. In some models it is true, and in others it isn't.

In another post perhaps, I'll mention some lesser known but almost-as-wonderful results in logic such as the Compactness theorem, the existence of non-standard models of arithmetic and Tarski's "Undefinability of truth".

Sequential Minimal Optimization

2004-12-04T23:21:00.000-07:00

A Support Vector Machine is a linear classifier that attempts to maximise the margin (ie. the distance between the classifier and the nearest training datum). Although SVMs are not Bayes-efficient, in practice they often generalize well and are particularily useful in conjunction with the kernel trick, which allows the classifier to work in a large (even infinite) feature space. The standard tutorial on SVM's is Burges' A tutorial on Support Vector Machines for Pattern Recognition. Shivani Agarwal has a very good introductory presentation on SVM's.

Training an SVM requires the solution of a very large quadratic programming problem (finding lagrange multipliers for each data point) which is often intractable. Sequential Minimal Optimization approaches the solution by solving for two l.m.'s (keeping the others fixed) at each step, and doing hill-climbing. Because there are only two variables, the QP can be solved analytically, making the inner loop of the training program very fast.

SMO is competitive with other SVM training methods such as Projected Conjugate Gradient "chunking" and in addition is easier to implement. SMO is the work of John Platt at Microsoft Research, and he maintains a reference page on the topic here.

Finally, there is also an SVM mailing list.

Next Year's Conferences

2004-11-27T17:40:00.000-07:00

I've compiled a list of AI and AI-related conferences that are happening next year. These are just some of the most important ones. If you can add to the list please do so. I've listed them in the order of Name, Venue, Conference date and Submission deadline.

International Joint Conference on Artificial Intelligence(IJCAI); Edinburgh, Scotland; Aug 1-5 ; Jan 21

American Association for Artificial Intelligence(AAAI); Pittsburgh, Pennsylvania; July 9-13; March 18 (right after the IJCAI notification deadline)

The European Conference on AI(ECAI) is not taking place this year because of IJCAI.

Uncertainty in Artificial Intelligence(UAI); Edinburgh, Scotland; July 26th-July 29th; March 16th

International Conference on Machine Learning(ICML); Bonn, Germany; August 7-11 ; 1st March

Conference on Learning Theory(COLT); Bertinoro, Italy; June 27-30 ;Feb 2

International Conference on Automated Planning & Scheduling(ICAPS) ; Monterey, California, USA ; June 5-10 ; Nov 17, 2004

International Conference on Theory and Applications of Satisfiability Testing(SAT); St. Andrews, Scotland; June 19th-23rd; Feb 20

UPDATE:

International Conference on Automated Deduction(CADE) ; Tallinn, Estonia; July 22 - July 27; February 25

International Joint Conference on Neural Networks (IJCNN); Montreal, Canada; July 31st - August 4th 2005; Jan. 31

Steve's Grand Vision

2004-11-17T21:46:00.000-07:00

Steve Grand, the creator of Creatures, and an independent AI researcher in his own right, has written an article in the IEEE Intelligent Systems magazine called Moving AI out of its Infancy: Changing our preconceptions. I find his ideas interesting, but not as groundbreaking or revolutionary as he imagines.

He dismisses traditional AI and connectionist methods as unsuccessful and based on false assumptions. A more or less fair assesment perhaps, but I think he has misunderstood the nature of what he calls "New AI", specifically claiming that it is influenced by the nervous systems of the simplest invertebrates. He is in search of what he calls the "periodic table" of AI, some radical new paradigm of intelligence that will transform AI from alchemy to chemistry, so to speak. I have serious issues with this. First, he bases his methods on being able to simulate the human brain, a very anthropocentric approach that may not be the best idea, given the tools of computation we have now and how little we understand (or even think we understand) the human brain.

Second, i think the view that intelligence must be based on one simple and easily described paradigm, that we just need to find and apply, is wrong. Researchers in Computational Brain Theory seem to be coming round to the view that the intelligence of the brain doesnt follow from one particular model of computation/cognition (say a hopfield network) but is an emergent behaviour of some pretty complex sub-systems which are functionally and operationally quite different.(More on this in a later post.) Intelligence must be engineered, using many different ideas, and we will most likely approach it asymptotically, like evolution did.

The rest of the article mentions some of the insights that he has, and I think a couple are worth mentioning, "Brains dont make decisions" and "Brains preform coordinate transforms". But I think these are just interesting alternate viewpoints on the problem itself and not necessarily constructive steps to a solution. I was disappointed that he seems to be focusing on questions that are exclusively in the realm of robotics. What about common sense, learning etc. ? Oh Well.

Conditional Preference Nets

2004-11-09T20:51:00.000-07:00

Conditional Preference nets, not to be confused with coloured petri nets, are a relatively new and hot area in decision theory today. At AAAI'04, there was a whole session devoted to them. CP-nets are an intuitive way of representing qualitative preferences between a set of possible outcomes, in a form analogous to a directed graphical model of a probability distribution, i.e. a Bayes Net. This obviously borrows ideas from utility theory and reasoning in graphical models. The main idea that CP-nets borrow from utility theory is the attempt to elicit preferences between two features of the outcome Ceteris Paribus (all else being equal). The classic example is "Given that fish is being served, I prefer white wine to red." The major difference is that wheras utility theory attempts to quantifies the preference by comparing one outcome to the lottery between two others (for eg. if our preferences are A < B < C, then the utility of B can be decided by computing the value of p s.t. the user is indifferent to a choice between B and a lottery of A and C with distribution (p, 1-p)), a CP net merely quantifies those preferences, but in a compact form.

It does this with a representation similar to the conditional probability tables used in a Bayes Net. Consider the following diagram and imagine the arrows on the edges all point downwards.

A B
\ /
  C
  |
  D

Then the preference for the attribute A could be A < A' and for B, B < B' . Since C has A and B has parents, its conditional preference has to be a function of their values. For e.g.
(A^B)V(A'^B') => C < C'
(A^B')V(A'^B) => C' < C
Finally, the preference for D is a function of C :
C => D < D'
C' => D' < D

The CP-net represents a complex 'joint preference distribution' in a compact form. The standard inference task in a CP-net is to compute dominating outcomes - those which are either preferred over or indifferent to all other outcomes. Reasoning with feasibiity constraints over the outcomes can also be done; this is like reasoning in a Bayes Net with evidence nodes. Some recent extensions to the CP-nets paradigm include TCP-nets, where there are preferences among preferences, UCP nets, which incorporate utilites into the network and mCP nets, which maintain seperate CP-nets for multiple agents that can share or make visible certain attributes.

A tutorial on CP-nets by Boutilier, Brafman, Domshlak, Hoos and Poole appeared in JAIR'04.

Rats flying F-22's

2004-10-24T22:30:00.000-06:00

Scientists at the University of Florida have successfully conducted a very intriguing experiment.

A collection of 25,000 "living" neurons were taken from the brain of a rat and cultured in a petri dish. Soon, they claimed, they had a living computation device with enough power to control an F-22 fighter jet. Using a multielectrode array to interface between the neurons and a desktop computer, they set up a bidirectional communication channel and "taught" the neurons to operate a flight simulator. Pretty soon, they had a network that could maintain a relatively stable flight by controlling the pitch and roll of the aircraft in various weather condition.

Pretty impressive I'll admit. My roommate, a microbiologist, is all over me - "Ha Ha. we'll have AI before you will." But it's one thing to learn to control aircraft, another to do ,say, common sense reasoning, as AI researchers have found. Pretty soon they're going to run into the same problems we did, when they try to "scale things up." They seem pretty optimistic:

"We're just starting out. But using this model will help us understand the crucial bit of information between inputs and the stuff that comes out ... And you can imagine the more you learn about that, the more you can harness the computation of these neurons into a wide range of applications."

Best of luck guys, you'll need it.

Conditional Random Fields

2004-10-23T23:17:00.001-06:00

Consider the problem of learning to assign labels to a set of observation sequences, for eg. assigning Part-of-Speech tags to the words in a sentence. Traditionally this task is performed using a Hidden Markov Model to define a generative model for the joint probability P(X, Y) where X and Y are the observations and the labels respectively. HMM's can be learnt using the incredibly efficient Baum-Welch Training algorithm but make frequently unrealistic assumptions on the independence of the variables.

Conditional Random Fields were introduced by Laferty, McCallum and Periera as a framework for labeling and segmenting data that models the conditional probability P(Y|x), thus allowing relaxation of the strong independence assumptions made by HMM's. It is convenient to consider a CRF as behaving like a Markov Random Field when conditioned on the observations X, that is given a particular observation sequence the CRF defines a single log-linear distribution over the label sequence.

In theory, the graph may be arbitrary but it is often the case that the nodes corresponding to Y form a First Order chain. Inference in a CRF is done by Dynamic Programming and typically the parameters are learnt by iterative scaling (since it is really a Maximum-Entropy approach). On many real world labelling problems, CRF's outperform HMM's .An interesting property of CRF's is that they do not suffer from the label bias problem, a property of some models where states with low entropy next-state distributions effectively ignore observations when conditioning on data.

A good introduction to CRF's can be found here.

The Cyborgs are coming !!

2004-10-18T21:02:00.000-06:00

Yahoo! News has an unusually detailed report about Braingate, technology that allows sensors to tap into the brains of quadriplegics and help them use their thoughts to control a computer and even play a game of pong. "It's Luke Skywalker," says John Donoghue, the neuroscientist who led development of the technology at Brown University and in 2001 founded Cyberkinetics Inc, the company behind the product. Those with long memories, might remember Kevin Warwick, the guy who started it all with a chip on his shoulder (literally), and who was incidentally a visiting professor here at UIUC for some time.

What fascinates me is the possibilty of extending the power of the mind with a cybernetic implant. So far our best efforts at AI have been crude attempts at replicating the general reasoning abilities of our brains, but for certain narrow tasks like mathematical theorem-proving or playing poker, we have software that can outdo humans. Consider the implications of having Mathematica or Cyc embedded into your brain. If you feel queasy about the whole idea, maybe you should read this essay by Nick Bostrom on the ethics of transhumanism.

Livingstone Version 2, I presume

2004-10-12T22:27:00.000-06:00

Nitish pointed me to this article about NASA successfully uploading a diagnostic AI software called Livingstone Version 2 onto a satellite. They're using it to simulate and identify faults in its robotic systems and plan alternate courses of action when failures occur. Like most news articles, this one is light on technical details.

Diagnostic software like this isnt new of course, but this seems significant for two reasons:

The tasks it preforms are almost completely automated, including the task of contigency planning. That is pretty much unprecedented, especially for the complex systems NASA builds.

NASA scientists are calling it a 'reasoner' , and claim that it's a general purpose system that can be easily adapted for most other kinds of machinery they have, like a planetary rover.

This reminds me of the keynote address given by Daniel J. Clancy from the NASA Ames Research Center at AAAI'04 on AI and NASA's New Exploration Vision. He had a rather optimistic outlook on AI's role in future NASA missions. The emphasis at NASA apparently, is not on algorithmic innovation but on architectural innovation. Kenneth Conley has a nice summary of his talk here.

Programs with Common Sense

2004-10-10T15:45:00.000-06:00

My first real Blog post will be about John McCarthy's classic paper Programs with Common Sense which may be regarded as the canonical description of a Good Old Fashioned Artificial Intelligence. John McCarthy, of course, was one of the original founders of our discipline, and came up with the name "Artificial Intelligence" (He's also my advisor's advisor, my grand-advisor if you will.)

In this paper, McCarthy lays out his vision for a thinking machine he calls the Advice Taker. When he and Marvin Minsky started working on this project, there was already talk of constructing intelligent machines, most notably the Logic Theory Machine of Newell, Simon and Shaw. All these proposals involved a reasoning system that used heuristics that were preprogrammed. McCarthy envisioned a machine whose heuristics would be in the representation language itself. Thus it's Behaviour could be improved merely by gaining knowledge about the outside world. On this basis McCarthy defined Common Sense - the ability of the machine to automatically deduce for itself a sufficiently wide class of immediate consequences of anything it is told and what it already knows.

To do so, he realised, one needs a language where interesting changes in behaviour could be expressible in a simple way. Thus he argued, the use of declarative sentences to express knowledge should be favored over imperative sentences to guide action. This was the same rationale that led to the invention of Lisp.

He goes on to describe the function of the Advice Taker in detail. It would use the First Order Predicate Calculus, the representation that dominated Knowledge Representation in AI research until today. Even by the standards of the next decade, the inference system was ridiculously naive. Modus Ponens was its one inference rule.

But as he demonstrated with his want(at(I,airport)) example, the deductive power of such a system was potentially immense. He also pointed out the fundamental stumbling block that would plague GofAI - the inherent non-determinism of reasoning. McCarthy realised that the Common-Sense of the machine would be a function of how good its heuristics would be in picking out the "right" line of deduction.

The discussion after the presentation of the paper is interesting as well. It seems that Professor Y. Bar-Hillel who dismissed Mccarthy's ideas as "half-baked", misunderstood his work and did not truly appreciate the scope of what McCarthy was attempting. However a couple of his criticisms were right on the mark and foreshadowed the identification of the qualification problem and the frame problem, which were dealt with in more detail in Mccarthy and Hayes 1969 paper Some Philosophical Problems From the Standpoint of Artificial Intelligence, as a primary weakness of the system.

Looking back now, the idea of a Software program with a large knowledge bank of rules, chugging along grinding out conclusions and dispensing advice, seems way too simplistic. But the real contribution of this paper was giving a goal and a direction to AI research that stimulated computer scientists for the next couple of decades.

AI for Fun and Profit

2004-10-09T22:04:00.000-06:00

What can one do with an Artificial Intelligence blog? One could wildly speculate about AI's impact on Human Affairs and the approach of the Vingean Singularity. Or gush about HAL, Wintermute and Marvin the paranoid robot. Argue about the incompleteness of formal systems and rooms that speak Chinese.

I probably will end up doing all of these. But mostly this blog is about the discipline of AI as a distinct subfield of Computer Science - The effort to build machines that think, know, learn and are aware. Along the way, if we could define what these terms mean exactly, well that would certainly help. I hope to take it in the same direction as Lance Fortnow's Computational Complexity Blog .

I will be the first to admit that AI hasnt delivered on the grand promise of 50 years ago. But we have made progress - at least now we are beginning to get an understanding of what acheiving AI entails and it is a daunting task. But one eminently worth pursuing. It will take a lot more science, quite a bit of mathematics and as we are beginning to realize - a nontrivial amount of Engineering. But we'll get there and hopefully this blog will be of help in documenting our efforts.
To quote David Hilbert (who long ago had formalist dreams of his own) - "Wir müssen wissen, wir werden wissen" (We must know, we shall know).