Sunday, March 18, 2012

Cloud and AI

Or, Running Lisp Probabilistically, backwards.


It started at a talk I attended in previous post. Yes, there's been lots of talk about analytics and cloud, even made famous in popular media.... But the "whats" and the "hows" are in constant flux. The curiosity triggered by the subtitle, lead to a weekend filled with AI and to this post.

AI is a big space. I'm focusing on one small part, Machine Learning. And specifically, translation and categorization, in exploring how The cloud supports AI, and AI supports the cloud...

What does the could have to do with machine translation? The early attempts at machine translation (circa 1950's) went down the path of Natural Language Processing. They failed for various reasons. current approaches (do the quizzes!!), as in Google Translate, play a matching game. Use the cloud to collect ridiculous amounts of sample translations, e.g a newspaper which publishes in more than language, restaurant menus and other sources of correlated text in multiple languages. These examples "teach" the machine, by example, what words in one language correspond to in other languages. The results are so surprisingly good, that you might be tempted to believe the machine actually knows what the words mean...

The ""standard"" proof that the meaning of the word was lost on the machines was translating this phrase: "The spirit is noble, but the flesh weak". Translating to a foreign language, and then back to English typically resulted in compliments for the wine and complaints about the meat... However, the genius of Google translate is the continuous learning, augmented by humans. If it got your translation wrong - you can teach Translate about the true meaning of the phrase. So far, it seems that French, Hebrew and even Korean round-trip correctly to English. Learning is an ongoing process...even for machines. Who knows we might have those electric monks sooner than later...

So, the cloud can provide a huge source for learning.... not just for tweens doing homework, but for machines too.

How does AI help the cloud? And where's that backward LISP thing?

The Target story involved lots of human intuition, and lots of data. A set of problems in AI, Unsupervised Categorization learning, is aiming at replicating the human intuition component. The CorssCat algorithm from MIT's CASIL is a really interesting (and successful) attempt at replicating the brains ability to find patterns in apparently random data. Given objects and features, it can discover different, even orthogonal, systems of categories to which these objects belong.
The core idea is simple - pick objects' features to use for a classification system, randomly. Then classify the objects into the resulting categories. Using Bayesian inference, score the probability of the resulting classification. In English, assume that the random set of features and categories is correct and calculate how likely it is for the objects fit into their assigned categories.
To estimate the probabilities (exact computation is really expensive) Markov Chain Monte Carlo (MCMC) are used to randomly pick values for variables, based on the current best estimate of the probability of the result.
Ok, that last sentence was a painful introduction to the concept of probabilistic programming, and specifically the Church language..... which runs LISP probabilistically, backwards. A program in Church provides answers to question like "how likely is this to happen?", or "what's the most likely categorization?". This is not your daddy's lisp...

A probabilistic algorithm basically has normal logic, interspersed with random functions. Whenever a random function is encountered, the system produces a ...random value for it, based on a probability distribution function. E.g. if you model a coin flip, (the 'flip' function in Church) - you'll get Heads half the time, and Tails the other (assuming a fair coin, it's likely to be 50/50).  The algorithm keeps running with the selected value(s), computing the overall result. Once a result is computed, the "query" function (the workhorse of Church) walks the evaluation history that lead to this result, and computes the joint-probability of the random choices made along the way. This overall probability is the desired outcome - how likely, overall, is it to arrive at this particular outcome. The system runs the algorithm repeatedly, making random choices and evaluating their results, and the probability of each result. Depending on how it was written, the program either produces the most likely result, or a distribution of the possible results.

Back to Target... applying CrossCat, Target could mine their shoppers' buying habits, and identify categories of shoppers based on their historical "features". Shoppers that share enough of the same "features" would probably fall into the same category, and are thus likely to share behaviors not yet exhibited...

AI can extract that information from all the data produced in the cloud, using human like intuition!








Monday, March 12, 2012

Cloudy data

Or, if you have the bits, but not the information....

I'm sitting at an event which combines a common thread of thoughts that has been floating in my head - Hadoop deals with lots of data... but how do I get to the Information contained there.
ThaDa... Big Data and machine learning are made for each other.

I've just learned about the Mahout - the tool to make information out of data, by using machine learning! Definitely something to look at.


Update:
I've spent some time reading and digesting some of the AI topics, with the results in this followup post