Artificial Intelligence and Robotics blog
Artificial Intelligence
A model Turing machine
Mar 28th
If you don’t know what a Turing machine is but would like to after watching the below video of Mike’s magnificent device then check out the information here and/or here. You can also get additional information about the hardware, software, and example programs that Mike’s device can execute then go here.
First ever chess playing computer program
Mar 22nd
Programming computers to play games has been central to Artificial Intelligence research since its early days back in the fifties. By now, most of us have heard of IBM’s Deep Blue supercomputer defeating world chess champion Garry Kasparov in the game of chess and becoming the first ever computer to defeat man in this very complex game. Less than 3 years ago, we wrote about Jonathan Schaeffer’s unbeatable checkers program known as Chinook; it took the researchers in Schaeffer’s group 18 years to explore enough of the search space to solve the game of checkers. The same group is now trying to develop expert poker playing programs and recently they organized the first ever man-machine poker challenge (man was the winner of this first encounter.)
However, few people know about the first ever chess playing program.
This program was designed by no other than the famous British mathematician and computer pioneer Alan Turing. Starting in 1948, Turing wrote the program in collaboration with D.G. Champernowne, a former undergraduate colleague of his. Four years later in 1952, when it was time to have a match against a human opponent, Turing had no access to a computer fast enough to execute his state-of-the-art program and so he did what every one of us would do in the same situation; he simulated the program using pen and paper requiring half an hour of computation for each move!
The game was won by the human participant Alick Glennie who was another of Turing’s colleagues. Alick defeated the computer in 29 moves playing the black pieces.
If you are a chess enthusiast, you can check out the full game here. The image at the top of this post shows the board at its conclusion.
Peter Norvig interview
Mar 3rd
The interview is about 30 minutes long and I have included the video below. If you want to know what Novig considers the biggest success and failure of AI and how he spends his time at Google then you should watch it. Most importantly, he answers the question as to whether Google is working on Strong AI; I like the fact that he first defines the term in two different ways and then relates the work at Google with respect to these definitions. He also explains why LISP is not used more widely at Google and shares some of his thoughts on programming.
Other than the interview, there is also an interesting post-interview discussion over at reddit with many insightful comments from the site’s users. You can be part of the conversation here.
Rewinding AI Research
Dec 10th
Research into Artificial Intelligence is being rewinded 30 years back by twenty scientists who have made great innovations in the field. Called “The Mind Machine Project”, it will operate for five years on a $5 million grand, with primary work taking place at the Massachusetts Institute of Technology.
Although the study of AI is more than 50 years old, many feel it has been limited and has not really explored the areas which hold the biggest potential—the mind, body and memory. The focus of the MMP will be to delve into this territory again and try to create a robot that is able to use all three of them to communicate with humans. Essentially, the team hopes to develop a way for AI machines to use real, practical thought based on their capabilities.
As described by Neil Gershenfeld, one of the head scientists of the project and director of the MIT Center for Bits and Atoms, the ultimate goal of this reunion is to create an AI machine that can, for example, read a children’s book, understand the concept and meaning on its own, and then explain what happened. The robot will come to this comprehension on its own, and not simply repeat a fixed program it has been implemented with. Although its thoughts would still be limited as to how far they can reach, it would be a stunning innovation that has never quite been achieved before.
In the future, this research can aid people suffering from different types of diseases which limit their cognitive ability, such as Alzheimer’s. It may be able to create a brain “co-processor”, which will help them with different types of mind activities and increase their quality of life. More than anything, I think this shows the true potential of the project.
[source BBC]
The Lumiere project: The origins and science behind Microsoft’s Office Assistant
Aug 31st
I think by now just about everyone has heard about the most annoying feature to have been included in a commercial piece of software. I am talking, of course, about Clippy, the Microsoft Office Assistant that many loved to hate. Clippy was first included in the 1997 release of the Office suite and continued to be part of the product line until 2007 when it was permanently removed.
Many people know Clippy as a major nuisance but few know the story behind the technology and why it sucked so much. Keep reading because I am about to tell you all about it (if you don’t want to read the whole story, you can just jump to the video at the middle of this post; if you watch the last minute you will get a glimpse of Clippy’s grandfather.)
Origins
In 1993, Microsoft researchers from the Decision Theory & Adaptive Systems Group established the Lumiere project to study and improve human computer interaction using Bayesian methods. The group wanted to create smart technologies that can observe a user interacting with a computer program and infer his/her goals and needs providing valuable feedback and assistance as necessary. Developing such a technology makes sense since many people often become intimidated by complex software interfaces. I won’t bore you with the details of what Bayesian methods are and why they are good. The mathematics behind such methods is solid and has had many useful applications to date.
So, is this an easy problem to solve?
Actually, inferring a user’s intent is a very hard problem no matter how good your math is. The Microsoft team had to infer user intent from his interaction with the program, e.g., mouse movement, what menu items were selected, context (what is the user trying to do – remember how Clippy always came up saying something like “I think you are trying to write a letter. Would you like some help?”) and specific text queries by the user, e.g., how do I print a document?
Any user model that can adequately capture all the relevant information will necessarily have many variables. The values of these variables must be estimated over time. Moreover, different users tend to interact with a piece of software differently. For example, an experienced user is most likely to need less help; the same user may also help with the more obscure features of the software compared to a novice. Personalization is a very important factor in ensuring that such systems work well.
To make a long story short, the Microsoft researchers led by the senior scientist Dr. Eric Horvitz were making good progress and in 2 years time they already had a nice system working. So, in 1995 and as the team had already started collaborating with the Microsoft Office production team, they put together a demonstration of Lumiere’s inference engine for Excel. The video below is a 9-minute tour of Lumiere working in Excel. In the video, Horvitz explains how the inference engine worked in 1995 and how they envisioned it working in later versions using a cartoon character front-end. Watch the last minute of the video for a glimpse of Clippy’s grandfather.
After the video, I explain using evidence from a number of Microsoft Research publications and personal knowledge why Clippy worked so poorly in the 1997 release of Microsoft Office.
Clippy debuts
The Bayesian inference engine demonstrated in the above video works like a charm monitoring the user’s behavior, inferring his intent, and providing help in a contextual and personalized fashion.
Two years after this video was recorded and after much collaboration between the research and product teams, the Lumiere project debuted as a well advertised feature of Microsoft Office 97. Clippy was one of the many cartoon characters that were available as the engine’s front end interacting with the user.
Unfortunately and as we all know, Clippy worked so poorly that it was not long before users started complaining about its behavior. So, what went wrong?
The reasons behind Clippy’s massive failure
Well, after doing some research I found out what went wrong. In a paper published in 1998 at the Conference on Uncertainty in Artificial Intelligence (UAI), the Lumiere team described the inner workings of the Assistant’s inference engine and also how much of it was included in the released version of Office 97. Below is a list of the features that were excluded from the product release (those keen enough can cross reference the list with what was demoed in the video above.)
- No persistent user profiles.
- No reasoning about user competence, i.e., novice versus experienced user
Small event queue with emphasis only on the most recent interactions of the user with the software interface (this means the engine was trying to guess the values of many variables using very little data.) - Separation between user interface events and word-based queries; for word-based queries the engine ignored any context and user actions.
- Last and possibly most important and I quote from the paper, “The automated facility of providing assistance based on the likelihood that a user may need assistance or on the expected utility of such autonomous action was not employed.” Instead, “The Office team has employed a relatively simple rule-based system on top of the Bayesian query analysis system to bring the agent to the foreground with a variety of tips.” This is why Clippy kept popping up all the time. It was not using the mathematically correct engine that the researchers had designed. It was driven by some rule-based system that one or more of the developers from the product team thought was a reasonable substitute.
Why did Microsoft cripple Clippy?
Obviously for some reason many of the features in Lumiere’s Bayesian inference engine never made it into Office 97.
Why?
I have not been able to find an official document that explains why most if not all of the inference engine’s features were not included in the Office 97 release. However, I can provide some informal evidence based on personal knowledge.
Some time in 2000 or 2001 when I was still a graduate student, Dr. Horvitz gave an invited talk at my university. He talked much about his HCI research and the Bayesian modeling techniques he had been studying for years. A question about Clippy was eventually and unavoidably asked. What the heck happened with that?
I recall his response being that what happened was as noted earlier much of their careful mathematical modeling of users never made it in the final product. He explained that the reason for this was a lack of disk space. You see, the Office suite ended up being much more bloated than originally expected and since most of the more mundane features were considered essential the product team decided to limit the amount of space available for the Office Assistant component. This is why so many features had to be removed. They did not have space for it all.
This is the story of the Microsoft Office Assistant or Clippy as it is most widely known. Microsoft discontinued the Office Assistant (more accurately turned off the feature and I very much doubt that anyone bothered to turn it back on) with the release of Office XP on 2001 and so Clippy is now resting in peace somewhere in a backup drive in Redmond.
The courageous story of Clippy and the tragic story behind its humble beginnings, rise to fame, and downfall are now part of history. But at least, you now know the truth of the reasons behind its unfortunate demise.
AIspace: Learn artificial intelligence using this collection of freely available interactive tools
Aug 23rd
A few days ago, I wrote about what I believe is the average person’s irrational fear of robots. As some people pointed out, some of these fears exist because we don’t really understand what Artificial Intelligence is and what it is capable of. So, I thought that some/many/all of our readers may benefit from learning the basics of AI.
To that effect, I would like to bring your attention to AIspace which is an online collection of interactive tools specifically designed for teaching introductory AI concepts to students. The tools have been under continuous development since 1999 at the University of British Columbia, Canada.
AIspace includes interactive tools for learning about arc consistency for constraint satisfaction problems, belief networks, graph searching, decision networks, neural networks, planning, and robot control. The tools are also accompanied with plenty of documentation to help anyone get started in AI.
The video below provides a short overview of AIspace. For the record, the person narrating in the video is Prof. Alan Mackworth who among many other honors is also the Founding Father of Robot soccer, i.e., Robocup.
Netflix prize claimed by international research team
Jun 27th
In the span of 3 years, some 40,000 teams from around the world took up Netflix’s challenge of improving movie recommendations by 10% over the company’s Cinematch engine. And just a day ago, one of these teams has claimed the top prize and the $1,000,000 that go with it. This team consists of the 2007 and 2008 progress prize winning team BellKor from the USA, Austria’s Big Chaos team, and Canada’s Pragmatic Theory team. Until recently, the teams were competing against each other unable to reach the 10% improvement threshold but they put an end to the competition when they joined forces.
Other teams now have 30 days to submit their solutions and outdo the top team for a chance to claim the top prize for themselves; keep an eye on the official leaderboard here. Can others do it? Well, you never know so it will be an interesting 30 days.
I have to admit that a couple of years ago I really didn’t think that this day would come. I was certain that the 10% improvement had been selected by Netflix to prevent people from ever claiming the million dollar prize. I guess, I was wrong after all.
That said, I am currently reading Don Tapscott and Anthony D. Williams’ best seller Wikinomics: How Mass Collaboration Changes Everything and I think the Netflix competition would make for a great story for this book. It is yet another example of how computers and the Internet allow thousands of people across the globe to collaborate effectively and efficiently to solve problems at a fraction of the cost of a single corporation doing the work in house. I don’t know how much money in Research and Development Netflix will save from this competition but I suspect they stand to make a lot of money from the 10% improvement in recommendation accuracy. They will certainly make back the prize money in no time (if they haven’t already considering that improvements over 7% have been achieved by many teams over the course of the last 2 years.)
Kudos to the teams for their achievement and kudos to Netflix for taking a chance most corporations would never dare take.
Game AI: The trade-off between entertainment and believable AI
Mar 22nd
I don’t write much about game AI since there is hardly anything cutting edge in game AI to talk about. More than a year ago, I wrote a post commenting on some research out of the Austrian Research Institute for Artificial Intelligence showing that even irrational players could easily defeat the AI in the real-time strategy game Age of Mythology. I have been playing video games for almost 20 years now and every year people talk about how the new games will have so much better AI and every year game developers fail to deliver. The truth is, that the kind of AI that goes into a computer game has different requirements than the AI systems researchers are trying to build for solving real-world problems. The differences is what makes creating good game AI systems difficult.
Game AI has to be good enough to make the game challenging for the person who paid for it but also less than optimal in its decision making so that it is not unbeatable. Nobody would enjoy playing chess against Deep Blue that even Kasparov could not defeat; it just would not be fun for anyone and let’s face it, computer games are designed to entertain more than anything else. So, game developers have to create AI systems that fulfill the above requirements something that is not an easy task.
Gamasutra recently republished an article that appeared in Game Developer magazine on the subject of creating AI systems that make mistakes giving the human opponent a chance to win the game but at the same time without making the game AI look totally stupid. Mick West, the article’s author, explains how one way to make AI systems to be both challenging and entertaining is by simply limiting the computational resources available to them during gameplay.
The simplest way to introduce stupidity into AI is to reduce the amount of computation that it’s allowed to perform. Chess AI generally performs billions of calculations when deciding what move to make.
The more calculations that are made (and the more time taken), then (generally) the better the computer will play. If you reduce the amount of calculations performed, the computer will be a worse player.
He argues that the above method which is commonly used in games is not easy to work with because developers have a hard time finding the correct threshold for computation time. The alternative method that Mick proposes is one that has the game AI intentionally playing poorly at times to give the human player a chance at winning.
The computer has to throw the game in order to make it fun. When you beat the computer, it’s an illusion. The computer let you win. We just want it to let you win in a way that feels good.
AI programmers need to get used to this idea. We are manipulating the game, creating artificial stupidity, fake stupidity. But we are not predetermining the outcome of the game.
We don’t set our AI with the intent to lose the game, but rather to give the human player a reasonable chance of winning. If the human plays poorly, the AI will still win, but the player will at least feel like she came close to beating a strong opponent, and thus feel like playing one more game.
The AI engine of the chess game Fritz was designed in such a way that the game will try to create situations that a smart chess player could exploit to earn an advantage over the computer and as such have a fair chance of winning. According to Mick, the game AI is not limited in the available computational resources but instead requires more in order to do this extra bit of thinking such that the game is both entertaining and challenging.
The article which you can read here, gives more examples of game AI employing the above tactic for poker and snooker.
Wolfram Alpha computational knowledge engine
Mar 10th
Stephen Wolfram announced a couple of days ago in a blog post that he and his team will soon unveil a new online computational knowledge engine called
Wolfram Alpha that will be able to answer questions posed to it in natural language. If successful, this would be the holly grail of computational intelligence for no other reason that questions posed in natural language could be directly answered by the system as opposed to simply returning online documents that might include the answer; the latter is the way that Internet search engines such as Google work.
Granted, for some questions, Google is very capable of directly giving answers such as for example asking “what is the population of China?” But whereas Google’s answers are likely found in some online document that directly answers the query, Wolfram Alpha will compute the answer by deriving it from its computational knowledge base. In other words, Wolfram Alpha will be able to derive new facts from known facts and a set of rules. This is what Artificial Intelligence researchers have dreamed of being able to do for more than 50 years.
Many details of how Wolfram Alpha is going to work were not provided in Stephen Wolfram’s blog post. In just a few sentences, this is how he describes the inner workings of the computational knowledge engine,
So how can we deal with that? Well, some people have thought the way forward must be to somehow automatically understand the natural language that exists on the web. Perhaps getting the web semantically tagged to make that easier.
But armed with Mathematica and NKS (New Kind of Science) I realized there’s another way: explicitly implement methods and models, as algorithms, and explicitly curate all data so that it is immediately computable.
It’s not easy to do this. Every different kind of method and model—and data—has its own special features and character. But with a mixture of Mathematica and NKS automation, and a lot of human experts, I’m happy to say that we’ve gotten a very long way.
I wasn’t at all sure it was going to work. But I’m happy to say that with a mixture of many clever algorithms and heuristics, lots of linguistic discovery and linguistic curation, and what probably amount to some serious theoretical breakthroughs, we’re actually managing to make it work.
You can read the Wolfram’s entire post here.
Wolfram Alpha will go online in May of 2009, just 2 months from now. I am looking forward to it. I don’t expect it to be perfect but I trust those people with access to the alpha version who say that it works very well. The only thing I have to figure out over the next two months is what to ask it when I finally get my chance. Maybe the answer to my question will be 42.
Siftables: From wireless sensor networks to tangible user interfaces
Feb 14th
Interacting with a computer using a keyboard and mouse is really starting to get old. I recently purchased a Tablet netbook and I have found the touch screen interface a pleasure to use over using the mouse; coupled with Vista’s excellent handwriting recognition, the tablet has become my number one machine for use daily. But how about new paradigms for human-computer interaction that are not just a small change over how we interact with computers today but a completely new one?
Say hello to Siftables, the creation of MIT Media Lab graduate student David Merrill and his colleagues. Siftables are small blocks with a microprocessor, an LCD display screen, and the ability to sense other Siftables around them.
Siftables applies technology and methodology from wireless sensor networks to tangible user interfaces. Siftables are independent, compact devices with sensing, graphical display, and wireless communication capabilities. They can be physically manipulated as a group to interact with digital information and media. Siftables can be used to implement any number of gestural interaction languages and HCI applications.
It is very difficult to appreciate how innovative Siftables are to human-computer interaction from a textual description so I encourage you to watch the following video of David’s TED conference presentation of his work. It is truly an amazing idea!
Recent Comments