Maybe your computer just needs a hug

Posted by Anthony Francis

Maybe your computer just needs a hug
I'm Anthony Francis, an artificial intelligence researcher working in Google's Search Quality group.  One of the things I like about Google is that we give back to the world in ways that make sense for our business, both as a company and as individuals.  Google's search engine runs on electrical power, and so Google as a company invests in renewable energy and encourages Googlers as individuals to conserve energy.  Google's search engine runs on open source software, and so Google as a company open sources its software and encourages Googlers to participate in existing open source projects.

What may be less obvious is that Google's search engine runs on ideas.  Google as a company has a great Research department, but it also encourages Googlers to participate in the research community - both in visible, obvious ways like writing papers and attending conferences, but also in less visible but still necessary chores that keep the research community running, like reviewing papers and organizing conferences.  What I'd like to tell you about today is how Google helped me give back to the research community by letting me take time to write a paper on work I did before I came to Google.

The Personal Pet Project
Ashwin Ram's Cognitive Computing Lab at Georgia Tech has been working on emotional agents for over ten years, first with robots, and more recently in computer games and virtual environments.  I worked on one of our earliest efforts in this area, the PEPE (Personal Pet) project, a joint effort with Yamaha to develop an robotic pet.  Dr. Ram noticed that many consumer electronics require configuration steps that are frustrating, even baffling: everything from VCRs to toasters has blinking clocks and unused features.  Pets, on the other hand, don't have to be "configured": they understand us on emotional level, noticing what makes us happy or angry, remembering what brings reward and punishment, and learning to respond appropriately without us reading a manual or pushing a button.

PEPE emulated this intuitive understanding with an emotional long term memory module, which I developed.  This module had three parts: basic emotions, emotional memory, and emotional reminding.  Basic emotions gave the robot realistic behavior "out of the box": for example, the robot interpreted being petted on the head as being pleasant, which made it want to socialize; it interpreted a kick to the rear as unpleasant, which made it want to hide.  The emotional memory associated these primitive emotions with the people and objects the robot saw in its environment.  Emotional reminding closed the loop: when the robot saw a person or object again, it was reminded of the past emotion, which influenced but did not determine the robot's ultimate emotional expression.  So the robot naturally wanted to play with people who petted it and fled people who had kicked it in the past, but it would be possible to overcome that past learning by ignoring the robot (if you didn't want to play with it as much anymore) or by petting it (if you had kicked it but no longer wanted it to be scared of you).

I worked with a team of engineers at Yamaha in Japan to implement this emotional long term memory on a small robot they were building.  Our job was easier because PEPE's basic architecture enabled creating many different kinds of behaviors that could easily interact with each other, in parallel or in sequence.  On top of this architecture, we added basic emotions, emotional learning and emotional reminding in stages.  Our initial tests were positive, and upon my return to the United States, we began porting this software back to Georgia Tech's PEPE robot.  PEPE even had a brief moment of fame, appearing on a local TV station; ultimately, however, Georgia Tech and Yamaha decided to move on to new projects.

Characters with Personality
But the dream of emotional agents didn't die.  Manish Mehta, a graduate student at Georgia Tech researching interactive games, began working with Ram to try to develop more sophisticated models of emotional change.  Mehta realized that emotional events can act as a trigger for behavioral change: if we humans try something that works really poorly, or spectacularly well, the emotions generated by that experience can prompt us to make changes to our behavior in the future --- for example, remembering to bring that umbrella in the future so we no longer have to walk home wet in the rain.

Mehta used ABL, an agent language developed by Michael Mateas and Andrew Stern for the Facade project.  Like the fundamental architecture of PEPE, ABL enabled the author of an agent to design complicated behaviors that could interact in sequence, in parallel, or through complex triggering.  Mehta extended ABL to allow an agent to rewrite its own behaviors, and triggered that rewriting based on charged emotional events.  This worked: using two agents playing tag, Mehta was able to make them revise their behaviors based on how well they played the game. However, it had an unintended consequence: one of the agents decided it was less stressed out when it was "IT".  When it was "IT", it wasn't being chased and wasn't feeling stressed, so it just let itself get tagged, enabling it to "chase" the other player at a leisurely pace.

While this result was surprising, even amazing, it failed to achieved the original objective.   Mehta realized this had exposed one more property of human behavioral change: emotional events can prompt change, but we also have a self image - a model of what we think our personality should be like.  As our personalities change, we audit the changes to make sure they fit our self image and apply further corrections.  For a computer game character, that "personality" is really the designer's intent, so Mehta augmented his emotional learning system to check potential behavioral changes and make sure that they did not violate the original intended design.  With this change, both characters were able to learn from their good and bad experiences playing tag, and neither "quit playing the game" just because they didn't want the stress of being chased.

Putting It All Together
The paper that Ram, and Mehta and I wrote for the Handbook of Synthetic Emotions and Sociable Robotics reports this work and ties together all of these threads.  We were not alone in challenges we faced in developing intelligent agents: others faced them too, in robotics, computer games and academic AI.  Many people use flexible behavior systems like PEPE's architecture or like ABL, but building large systems out of these can be challenging and extremely labor intensive.  What Mehta and I found, however, is that the use of emotion models acted like a force multiplier: adding basic emotional responses to an existing behavior system radically increased the flexibility and apparent realism of an intelligent agent, whether it was a robotic puppy or a character in a computer game.

Moreover, the more components of the emotion stack you add to an agent, the easier it becomes to extend.  While adding emotion made PEPE extended the behaviors it could perform; modifying those emotions using memories changed the character of its behavior, making it seem more lifelike.  Mehta's work in extending ABL took this further, enabling creative behavior changes in response to agent frustration.  Adding personality models makes these changes stable, enabling the agent to adapt to new situations while staying consistent with their designer's intent.  Often, just adding more behaviors to an existing agent can make it more brittle; we found in contrast adding new layers inspired by research in human and animal emotion made the agent more sophisticated and robust.

Giving Something Back
Writing this paper did not take much time from Google.  Most of it was done in the evening on my own time, with the occasional email exchange with my coauthors and editors during the day while I was waiting on compiles.  And that is how it should be: it may be a long time before this work directly benefits Google, since we do not currently develop robots or computer games.  But Google still benefited because the advances that we need to improve our search engine often start in academia.

By encouraging our staff to follow up on their research work and to contribute to the research community, Google supports the growth of the next big idea.  Knowing that we can follow up on our past work makes researchers at Google feel more empowered to pursue new ideas and continually exposes us to sources of inspiration.  And that inspiration, which makes Google a better place to work, is exactly what I need to keep trying new ideas, which in the end will help make Google a better place to search.

Translation is Risky Business

Posted by Shankar Kumar and Wolfgang Macherey

At Google, we like search. So it's no surprise that we treat language translation as a search problem. We build statistical models of how one language maps to another (the translation model) and models of what the target language is supposed to look like (the language model) and then we search for the best translation according to those models (combined into one big log linear model for those of you taking notes).

But, just as putting all of your money in the investment with the highest historical return is not always the best idea, choosing the translation with the highest probability is not always the best idea either - especially when you have a relatively flat distribution among the top candidates. Instead, we can use the Minimum Bayes Risk (MBR) criterion. Essentially, we look at a sample of the best candidate translations (the so called n-best list) and choose the safest one, the one most likely to do the least amount of damage (where 'damage' is defined by our measurement of translation quality). You might want to view this as choosing a translation that is a lot like the other good translations instead of choosing that strange one that had the good model score.

If this is our 'diversification' strategy, how can we make things even safer? Exactly the same way as we do for investments, we diversify even more. That is, we look at more of the candidate translations to make the MBR decision. A lot more. And the way to do that is to build a lattice of translations during the search and then we do our MBR search over the lattice. Instead of 100 or 1000 best translations that we would use for the n-best approach, lattices give us access to a number that rivals the number of particles in the visible universe (really, it's huge).

 Interested? You can read all about it here.

plop: Probabilistic Learning of Programs

Posted by Moshe Looks

Cross-posted with Open Source at Google blog

Traditional machine learning systems work with relatively flat, uniform data representations, such as feature vectors, time-series, and probabilistic context-free grammars. However, reality often presents us with data which are best understood in terms of relations, types, hierarchies, and complex functional forms. The best representational scheme we computer scientists have for coping with this sort of complexity is computer programs. Yet there are comparatively few machine learning methods that operate directly on programmatic representations, due to the extreme combinatorial explosions involved and the semantic complexities of programs.

The plop project is part a new approach to learning programs being developed at Google and elsewhere that takes on the challenges of learning programs through a unified approach based on reducing programs to a hierarchical normal form, building sequences of specialized representations for programs as search progresses, maintaining alternative representations, and managing uncertainty probabilistically by applying estimation-of-distribution algorithms over program spaces, and exploiting probabilistic background knowledge.

For more information on this approach to learning programs, see my doctoral dissertation. For more on the overall philosophy and where things are going, see the plop wiki on Google Code.

New Technology Roundtable Series

Posted by Alfred Spector, VP of Research and Special Initiatives

We've just posted the first three videos in the Google Technology Roundtable Series.  Each one is a discussion with senior Google researchers and technologists about one of our most significant achievements. We use a talk show format, where I lead a discussion on the technology. 

While the videos are intended for a reasonably technical audience, I think they may be interesting to many as an overview of the key challenges and ideas underlying Google's systems. And of course they offer a glimpse into the people behind Google.

The first one we made is Large-Scale Search System Infrastructure and Search Quality." I interview Google Fellows Jeff Dean and Amit Singhal on their insights in how search works at Google.

The next title is "Map Reduce," a discussion of this key technology (first, at Google, and now having a great impact across the field) for harnessing parallelism provided by very large-scale clusters computers, while mitigating the component failures that inevitably occur in such big systems. My discussion is with four of our Map Reduce expert engineers: Sanjay Ghemawat and Jeff Dean again, plus Software Engineers Jerry Zhao and Matt Austern, who discuss the origin, evolution and future of Map Reduce. By the way, this type of infrastructure underlies the infrastructure concepts in our recent post on "The Intelligent Cloud."

The third video, "Applications of Human Language Technology," is a discussion of our enormous progress in large-scale automated translation of languages and speech recognition. Both of these technology domains are coming of age with capabilities that will truly impact what we expect of computers on a day-to-day basis. I discuss these technologies with human language technology experts Franz Josef Och, an expert in the automated translation of languages, and Mike Cohen, an expert in speech processing.

We hope to produce more of these, so please leave feedback at YouTube (in the comments field for each video), and we will incorporate your ideas into our future efforts.

Doubling Up

Posted by Franz Josef Och

Machine translation is hard. Natural languages are so complex and have
so many ambiguities and exceptions that teaching a computer to
translate between them turned out to be a much harder problem than
people thought when the field of machine translation was born over 50
years ago. At Google Research, our approach is to have the machines
learn to translate by using learning algorithms on gigantic amounts of
monolingual and translated data. Another knowledge source is user
suggestions. This approach allows us to constantly improve the
quality of machine translations as we mine more data and
get more and more feedback from users.

A nice property of the learning algorithms that we use is that they
are largely language independent -- we use the same set of core
algorithms for all languages. So this means if we find a lot of
translated data for a new language, we can just run our algorithms and
build a new translation system for that language.

As a result, we were recently able to significantly increase the number of
languages on translate.google.com. Last week, we launched eleven new
languages: Catalan, Filipino, Hebrew, Indonesian, Latvian, Lithuanian, Serbian,
Slovak, Slovenian, Ukrainian, Vietnamese. This increases the
total number of languages from 23 to 34.  Since we offer translation
between any of those languages this increases the number of language
pairs from 506 to 1122 (well, depending on how you count simplified
and traditional Chinese you might get even larger numbers). We're very
happy that we can now provide free online machine translation for many
languages that didn't have any available translation system before.

So how far can we go with adding new languages in the future? Can we
go to 40, 50 or even more languages?  It is certainly getting harder,
as less data is available for those languages and as a result it is
harder to build systems that meet our quality bar.  But we're working
on better learning algorithms and new ways to mine data and so even if
we haven't covered your favorite language yet, we hope that we will have
it soon.

Remembering Randy Pausch

Posted by Kevin McCurley, Research Team

It is with great sadness that we note the passing of Randy Pausch, who taught computer science at Carnegie Mellon University. Randy was well-known by many within the research community, including quite a number of us here at Google. Alfred Spector, our Vice President of Research, was his Ph.D. advisor. Rich Gossweiler, a Senior Research Scientist, was his first Ph.D. student. Several other former colleagues and coauthors (Joshua Bloch, Adam Fass, and Ning Hu) now work here.

All of us strive to make an impact with our research, and Randy was no exception. He will be remembered for his work, but also for his contributions to humanity at large. Millions have watched the video on YouTube from his lecture titled Achieving your Childhood Dreams. The strength of his character was already known to his family, his colleagues, and the broader computer science research community. The courage and optimism that he displayed at the end of his life became inspirational to millions more.

I've seen Randy repeatedly go to bat for what is right. As a leader, he consistently evoked incredible enthusiasm and optimism for the subjects he embraces. Randy had a very human passion about people and not just who they are, but their potential, despite any flaws or obstacles in their way. His contributions will be remembered for generations to come. - Rich Gossweiler

Randy was one of the most vibrant, passionate people I've ever known. His passion was inspirational not only to his family and colleagues, but also, because of his courageous presentations beginning with his well-known Last Lecture, he has influenced millions more. - Alfred Spector

We will miss Randy very much, and remember him fondly.

Machine Learning Meeting

Posted by Phil Long

Machine Learning is a branch of Artificial Intelligence in which, naturally enough, the aim is to get computers to learn: things like improving performance over time, and recognizing general tendencies among a number of specific cases.  We have many ways to exploit Machine Learning programs, and a lot of data to give them.  Machine Learning helps us to estimate what content users like most, what content is even legitimate, and how to match ads to content.  It also plays key roles in products such as Google Translate and 1-800-GOOG-411.

Last week, Google held a Machine Learning Summit in New York, gathering together engineers from around the world, including participants from Beijing, Zurich, Boston, Haifa, and Mountain View. The program included invited talks by CJ Lin and Peng Xu, and many shorter presentations by Googlers on topics including broadly applicable Machine Learning software, especially challenging applications, and some mathematical analysis.

Can You Publish at Google?

Posted by Rich Gossweiler

As part of the interview process at Google we try to describe what it is like to do research here. A common question I get is "How hard is it to publish at Google?" I want to dispel the myth that it is hard. It is easy to publish, easy to put code into open source, easy to give talks, etc. But it is also easy for great research to become great engineering, and that is an incredible lure. Great barriers of despair exist between research and development at many companies; researchers can find it hard to have impact beyond demos, papers, or patents.

Here at Google it is not uncommon for researchers to work on products (and is modus operandi for me); you can come up with something interesting, experiment to convince yourself and others that it is worthwhile, and then work as part of the team to build it and help create world-changing products. But are you willing to do that? That decision is the hard part, not publishing a paper.

I think from a Google standpoint, we need to make sure these barriers don't form, that making products, experimenting and having a venue for trying bold new approaches continues to be part of the culture.

VisualRank

Posted by Shumeet Baluja and Yushi Jing

At WWW-2008, in Beijing, China, we presented our paper "PageRank for Product Image Search". In this paper, we presented a system that used visual cues, instead of solely text information, to determine the rank of images. The idea was simple: find common visual themes in a set of images, and then find a small set of images that best represented those themes. The resulting algorithm wound up being PageRank, but on an entirely inferred graph of image similarities. Since the release of the paper, we've noticed lots of coverage in the press and have received quite a few questions. We thought we could answer a few of them here.


"Why did we choose to use products for our test case?" First and foremost, product queries are popular in actual usage; addressing them is important. Second, users have strong expectations of what results we should return for these queries; therefore, this category provides an important set of examples that we need to address especially carefully. Third, on a pragmatic note, they lend themselves well to the type of "image features" that we selected in this study. Since the publication of the paper, we've also extended our results to other query types, including travel-related queries. One of the nice features of the approach is that (we hope) it will be easy to extend to new domains; as research in measuring image or object similarity continues, the advances can easily be incorporated into the similarity calculation to compute the underlying graph; the computations on the graph do not change.

"Where are we going from here?" Besides broadening the sets of queries (and sets of features) for which we can use this approach, there are three directions we're exploring. First, estimating similarity measures for all of the images on the web is computationally expensive; approximations or alternative computations are needed. Second, we hope to evaluate our approach with respect to the large number of recently proposed alternative clustering methods. Third, many variations of PageRank can be used in quite interesting ways for image search. For example, we can use some of these previously published methods to reintroduce, in a meaningful manner, the textual information that the VisualRank algorithm removed. In the end, we have an approach that has an easy integration with both text and visual clues. Stay tuned for more on that in the coming months.

And now to answer the most commonly asked question, "Is it live?" Not yet. Currently, it is research in progress (click here to help speed up the process). In the meantime, though, if you'd like another sneak peek of our research on large graphs, this time in the context of YouTube datamining, just follow the link.

Finally, we want to extend our deepest thanks to the people who helped on this project, especially the image-search team; without their help, this research would not have been possible.

Research in the Cloud: Providing Cutting Edge Computational Resources to Scientists

Posted by Christophe Bisciglia, Senior Software Engineer, and Alfred Spector, Vice President of Research

The emergence of extremely large datasets, well beyond the capacity of almost any single computer, has challenged traditional and contemporary methods of analysis in the research world. While a simple spreadsheet or modest database remains sufficient for some research, problems in the domain of "computational science," which explores mathematical models via computational simulation, require systems that provide huge amounts of data storage and computer processing (current research areas in computational science include climate modeling, gene sequencing, protein mapping, materials science and many more). As an added hurdle, this level of computational infrastructure is often not affordable to research teams, who usually work with significant budgetary restrictions.

Fortunately, as the Internet technology industry expands its global infrastructure, accessing world class distributed computational and storage resources can be as simple as visiting a website. Building on its Academic Cloud Computing Initiative (ACCI) announced last October, Google and IBM, with the National Science Foundation, announced in February the CluE initiative to address this particular need. After coordinating the technical details with Google and IBM, the NSF posted the official solicitation of proposals last week.

Our primary goal in participating in the CluE initiative is to encourage the understanding, further refinement and --importantly-- targeted application of the latest distributed computing technology and methods across many academic disciplines. Engaging educators and researchers with the new potential of distributed computing for processing and analyzing extremely large datasets is an invaluable investment for any technology company to make, and Google in particular is pleased to make a contribution to the academic community that has enabled so many recent advances in the industry.

We're looking forward to an eclectic collection of proposals from the NSF's solicitation. We believe many will leverage the power of distributed computing to produce a diverse range of knowledge that will provide long term benefit to both the research community and the public at large. We also hope that Google's contribution to this low cost, open source approach to distributed computing will allow many more in the academic community to take advantage of this pervasive technological shift.

More details, including information on how to apply for access to these resources, is available on the NSF site.