Google at USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘10)

Posted by Murray Stokely, Software Engineer

The 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘10) was recently held in Vancouver, B.C. This biennial conference is one of the premiere forums for presenting innovative research in distributed systems from both academia and industry, and we were glad to be a part of it.

In addition to sponsoring this conference since 2002, Googlers contributed to the exchange of scientific ideas through authoring or co-authoring 3 published papers, organizing workshops, and serving on the program committee. A short summary of the contributions:

• Large-scale Incremental Processing Using Distributed Transactions and Notifications.
  Google replaced its batch-oriented indexing system with an incremental system, Percolator. Rather than running a series of high-latency map-reduces over large batches of documents, we now index individual documents at very low latency. The result is a 50% reduction in search result age; our paper discusses this project and the implications of the result.
• Availability in Globally Distributed Storage Systems.
  Reliable and efficient storage systems are a key component of cloud-based services. In this paper we characterize the availability properties of cloud storage systems based on extensive monitoring of Google's main storage infrastructure and present statistical models that enable further insight into the impact of multiple design choices, such as data placement and replication strategies. We demonstrate the utility of these models by computing data availability under a variety of replication schemes given the real patterns of failures observed in our fleet.
  
• Onix: A Distributed Control Platform for Large-scale Production Networks.
  There has been recent interest in a new networking paradigm called Software-Defined Networking (SDN). The crucial enabler for SDN is distributed control platform that shields developers from the details of the underlying physical infrastructure and allows them to write sophisticated control logic against a high-level API. Onix provides such a control platform for large-scale production networks.
  

In addition to the papers presented by current Googlers, we were also happy to see that the recipient of the 2009 Google Ph.D. Fellowship in Cloud Computing, Roxana Geambasu, presented her work on Comet: An active distributed key-value store.

Videos of all of the talks from OSDI are available on the conference website for attendees and current USENIX members. There is also a USENIX YouTube channel with a growing subset of the conference videos open to everyone.

Google is making substantial progress on many of the grand challenge problems in computer science and artificial intelligence as part of its mission to organize the worlds information and make it useful. Given the continuing increase in the scale of our distributed systems it’s fair to say we’ll have some other exciting new work to share at the next OSDI. Hope to see you in 2012.

Making an Impact on a Thriving Speech Research Community

Posted by Vincent Vanhoucke, Google Research

While we continue to launch exciting new speech products--most recently Voice Actions and Google Search by Voice in Russian, Czech and Polish--we also strive to contribute to the academic research community by sharing both innovative techniques and experiences with large-scale systems.

This year’s gathering of the world’s experts in speech technology research, Interspeech 2010 in Makuhari, Japan, which Google co-sponsored, was a fantastic demonstration of the momentum of this community, driven by new challenges such as mobile voice communication, voice search, and the increasing international reach of speech technologies.

Googlers published papers that showcased the breadth and depth of our speech recognition research. Our work addresses both fundamental problems in acoustic and language modeling, as well as the practical issues of building scalable speech interfaces that real people use everyday to make their lives easier.

Here is a list of the papers presented by Googlers at the conference:

• Direct Construction of Compact Context-Dependency Transducers From Data, David Rybach and Michael Riley (Computer Speech & Language Best Paper Award).
• Voice Search for Development, Etienne Barnard, Johan Schalkwyk, Charl van Heerden and Pedro J. Moreno.
• Unsupervised Discovery and Training of Maximally Dissimilar Cluster Models, Françoise Beaufays, Vincent Vanhoucke and Brian Strope.
• Search by Voice in Mandarin Chinese, Jiulong Shan, Genqing Wu, Zhihong Hu, Xiliu Tang, Martin Jansche and Pedro J. Moreno.
• On-Demand Language Model Interpolation for Mobile Speech Input, Brandon Ballinger, Cyril Allauzen, Alexander Gruenstein, and Johan Schalkwyk.
• Building Transcribed Speech Corpora Quickly and Cheaply for Many Languages, Thad Hughes, Kaisuke Nakajima, Linne Ha, Atul Vasu, Pedro J. Moreno and Mike LeBeau.
• Say What? Why Users Choose to Speak their Web Queries, Maryam Kamvar and Doug Beeferman.
• Study on Interaction between Entropy Pruning and Kneser-Ney Smoothing, Ciprian Chelba, Thorsten Brants, Will Neveitt and Peng Xu.
• Decision Tree State Clustering with Word and Syllable Features, Hank Liao, Chris Alberti, Michiel Bacchiani and Olivier Siohan.

Bowls and Learning

Posted by Phil Long, Research Team

It is easy to find the bottom of a bowl no matter where you start -- if you toss a marble anywhere into the bowl, it will roll downhill and find its way to the bottom.

What does this have to do with Machine Learning? A natural way to try to construct an accurate classifier is to minimize the number of prediction errors the classifier makes on training data. The trouble is, even for moderate-sized data sets, minimizing the number of training errors is a computationally intractable problem. A popular way around this is to assign different training errors different costs and to minimize the total cost. If the costs are assigned in a certain way (according to a “convex loss function”), the total cost can be efficiently minimized the way a marble rolls to the bottom of a bowl.

In a recent paper, Rocco Servedio and I show that no algorithm that works this way can achieve a simple and natural theoretical noise-tolerance guarantee that can be achieved by other kinds of algorithms. A result like this is interesting for two reasons: first, it's important to understand what you cannot do with convex optimization in order to get a fuller understanding of what you can do with it. Second, this result may spur more research into noise-tolerant training algorithms using alternative approaches.

Poetic Machine Translation

Posted by Dmitriy Genzel, Software Engineer

Once upon a midnight dreary, long we pondered weak and weary,
Over many a quaint and curious volume of translation lore.
When our system does translation, lifeless prose is its creation;
Making verse with inspiration no machine has done before.
So we want to boldly go where no machine has gone before.
Quoth now Google, "Nevermore!"

Robert Frost once said, “Poetry is what gets lost in translation.” Translating poetry is a very hard task even for humans, and is clearly beyond the capability of current machine translation systems. We therefore, out of academic curiosity, set about testing the limits of translating poetry and were pleasantly surprised with the results!

We are going to present a paper on poetry translation at the EMNLP conference this year. In this paper, we investigate the purely technical challenges around generating translations with fixed rhyme and meter schemes.

The value of preserving meter and rhyme in poetic translation has been highly debated. Vladimir Nabokov famously claimed that, since it is impossible to preserve both the meaning and the form of the poem in translation, one must abandon the form altogether. Another authority (and for us computer scientists, perhaps the more familiar one), Douglas Hofstadter argues that preserving the form is very important to maintaining the feeling and the sound of a poem. It is in this spirit that we decided to experiment with translating not only poetic meaning, but form as well.

A Statistical Machine Translation system, like Google Translate, typically performs translations by searching through a multitude of possible translations, guided by a statistical model of accuracy. However, to translate poetry, we not only considered translation accuracy, but meter and rhyming schemes as well. In our paper we describe in more detail how we altered our translation model, but in general we chose to sacrifice a little of the translation’s accuracy to get the poetic form right.

As a pleasant side-effect, the system is also able to translate anything into poetry, allowing us to specify the genre (say, limericks or haikus), or letting the system pick the one it thinks fits best. At the moment, the system is too slow to be made publicly accessible, but we thought we’d share some excerpts:

A stanza from Essai monographique sur les Dianthus des Pyrénées françaises by Edouard Timbal-Lagrave and Eugène Bucquoy, translated to English as a pair of couplets in iambic tetrameter:

So here's the dear child under land,
will not reflect her beauty and
besides the Great, no alter dark,
the pure ray, fronts elected mark.

Voltaire’s La Henriade, translated as a couplet in dactylic tetrameter:

These words compassion forced the small to lift her head
gently and tell him to whisper: “I'm not dead."

Le Miroir des simples âmes, an Old French poem by Marguerite Porete, translated to Modern French by M. de Corberon, and then to haiku by us:

“Well, gentle soul”, said
Love, “say whatever you please,
for I want to hear.”

More examples and technical details can be found in our research paper (as well as clever commentary).

Veni, Vidi, Verba Verti

Posted by Jakob Uszkoreit, Ingeniarius Programmandi

Ut munimenta linguarum convellamus et scientiam mundi patentem utilemque faciamus, instrumenta convertendi multarum nationum linguas creavimus. Hodie nuntiamus primum instrumentum convertendi linguam qua nulli nativi nunc utuntur: Latinam. Cum pauci cotidie Latine loquantur, quotannis amplius centum milia discipuli Americani Domesticam Latinam Probationem suscipiunt. Praeterea plures ex omnibus mundi populis Latinae student.

Hoc instrumentum convertendi Latinam rare usurum ut convertat nuntios electronicos vel epigrammata effigierum YouTubis intellegemus. Multi autem vetusti libri de philosophia, de physicis, et de mathematica lingua Latina scripti sunt. Libri enim vero multi milia in Libris Googlis sunt qui praeclaros locos Latinos habent.

Convertere instrumentis computatoriis ex Latina difficile est et intellegamus grammatica nostra non sine culpa esse. Autem Latina singularis est quia plurimi libri lingua Latina iampridem scripti erant et pauci novi posthac erunt. Multi in alias linguas conversi sunt et his conversis utamur ut nostra instrumenta convertendi edoceamus. Cum hoc instrumentum facile convertat libros similes his ex quibus edidicit, nostra virtus convertendi libros celebratos (ut Commentarios de Bello Gallico Caesaris) iam bona est.

Proximo tempore locum Latinum invenies vel auxilio tibi opus eris cum litteris Latinis, conare hunc.

Remembering Fred Jelinek

Posted by Ciprian Chelba, Research Team

It is with great sadness that we note the passing of Fred Jelinek, teacher and colleague to many of us here at Google. His seminal contributions to statistical modeling of speech and language influenced not only us, but many more members of the research community.

Several of us at Google remember Fred:

Ciprian Chelba:
Fred was my thesis advisor at CLSP. My ten years of work in the field after graduation led me to increasingly appreciate the values that Fred instilled by personal example: work on the hard problem because it simply cannot be avoided, bring fundamental and original contributions that steer clear of incrementalism, exercise your creativity despite the risks entailed, and pursue your ideas with determination.

I recently heard a comment from a colleague, “A natural born leader is someone you follow even if only out of curiosity.” I immediately thought of Fred. Working with him marked a turning point in my life, and his influential role will be remembered.

Bob Moore:
I first met Fred Jelinek in 1984 at an IBM-sponsored workshop on natural-language processing. Fred's talk was my first exposure to the application of statistical ideas to language, and about the only thing I understood was the basic idea of N-gram language modeling: estimate the probability of the next word in a sequence based on a small fixed number of immediately preceding words. At the time, I was so steeped in the tradition of linguistically-based formal grammars that I was sure Fred's approach could not possibly be useful.

Starting about five years later, however, I began to interact with Fred often at speech and language technology meetings organized by DARPA, as well as events affiliated with the Association for Computational Linguistics. Gradually, I (along with much of the computational linguistics community) began to understand and appreciate the statistical approach to language technology that Fred and his colleagues were developing, to the point that it now dominates the field of computational linguistics, including my own research. The importance of Fred's technical contributions and visionary leadership in bringing about this revolution in language technology cannot be overstated. The field is greatly diminished by his passing.

Fernando Pereira:
I met Fred first at a DARPA-organized workshop where one of the main topics was how to put natural language processing research on a more empirical, data-driven path. Fred was leading the charge for the move, drawing from his successes in speech recognition. Although I had already started exploring those ideas, I was not fully convinced by Fred’s vision. Nevertheless, Fred’s program raised many interesting research questions, and I could not resist some of them. Working on search for speech recognition at AT&T, I was part of the small team that invented the finite-state transducer representation of recognition models. I gave what I think was the first public talk on the approach at a workshop session that Fred chaired. It was Fred’s turn to be skeptical, and we had a spirited exchange in the discussion period. At the time, I was disappointed that I had failed to interest Fred in the work, but later I was delighted when Fred became a strong supporter of our work after a JHU Summer workshop where Michael Riley led the use of our software tools in successful experiments with a team of JHU researchers and students. Indeed, in hindsight, Fred was right to be skeptical before we had empirical validation for the approach, and his strong support when the results started coming in was thus much more meaningful and gratifying. Through these experiences and much more, I came to respect immensely Fred’s pioneer spirit, vision, and sharp mind. Many of my most successful projects benefited directly or indirectly from his ideas, his criticism, and his building of thriving institutions, from CLSP to links with the research team at Charles University in Prague. I saw Fred last at ACL in Uppsala. He was in great form, and we had a good discussion on funding for the summer workshops. I am very sad that he will not be with us to continue these conversations.

Shankar Kumar:
Fred was my academic advisor at CLSP/JHU and I interacted with him throughout my Ph.D. program. I had the privilege of having him on my thesis committee. My very first exposure to research in speech and NLP was through an independent study that I did under him. A few years later, I was his teaching assistant for the speech recognition class. Fred's energy and passion for research made a strong impression on me back then and continues to influence my work to this day. I remember Fred carefully writing up his ideas and sending them out as a starting point to our discussions. While I found this curiously amusing at the time, I now think this was his unique approach to ensure clarity of thought and to steer the discussion without distractions. Fred's enthusiasm for learning new concepts was infectious! I attended several classes and guest lectures with him - graphical models, NLP, and many more. His insightful questions and his active participation in each one of these classes made them memorable for me. He epitomized what a life-long learner should be. I will always recall Fred's advice on sharing credit generously. In his own words, "The contribution of a research paper does not get divided by the number of authors". By his passing, we have lost a role model who dedicated his life to research and whose contributions will continue to impact and shape the field for years to come.

Michael Riley:
I got to know Fred pretty well having attended two of the CLSP six-week summer workshops, working on a few joint grants, and visiting CLSP in between. If there is a ‘father of speech recognition’, its got to be Fred Jelinek - he led the IBM team that invented and popularized many of the key methods used today. His intellect, wide knowledge, and force of will served him well later as the leader of the JHU Center for Language and Speech Processing - a sort of academic hearth where countless speech/NLP researchers and students interacted over the years in seminars and workshops. I was impressed that at an age when many retired and after which most of his IBM colleagues had gone into (very lucrative) financial engineering, he remained a vigorous, leading academic. Fernando mentioned the initial skepticism he had for our work on weighted FSTs for ASR. Some years later though I heard that he praised the work to my lab director, Larry Rabiner, on a plane ride that likely helped my promotion shortly thereafter. And no discussion of Fred would be complete without a mention of his inimitable humor, delivered in that loud Czech-accented voice:

Riley [at workshop planning meeting]: “Could they hold the summer workshop in some nicer place than Baltimore to help attract people?”
Fred: “Riley, we’ll hold it in Rome next year and get better people than you!”

Seminar presenter: [fumbling with Windows configuration for minutes].
Fred [very loud]: “How long do we have to endure this high-tech torture?”

The website of The Johns Hopkins University’s Center for Language and Speech Processing links to Fred’s own descriptions of his life and technical achievements.

Frowns, Sighs, and Advanced Queries -- How does search behavior change as search becomes more difficult?

Posted by Anne Aula, Rehan Khan, and Zhiwei Guan, User Experience Team

How does search behavior change as search becomes more difficult?

At Google, we strive to make finding information easy, efficient, and even fun. However, we know that once in a while, finding a specific piece of information turns out to be tricky. Based on dozens of user studies over the years, we know that it’s relatively easy for an observer to notice that the user is having problems finding the information, by watching changes in language, body language, and facial expressions:



Computers, however, don’t have the luxury of observing a user the way another person would. But would it be possible for a computer to somehow tell that the user is struggling to find information?

We decided to find out. We first ran a study in the usability lab where we gave users search tasks, some of which we knew to be difficult. The first couple of searches always looked pretty much the same independent of task difficulty: users formulated a query, quickly scanned the results and either clicked on a result or refined the query. However, after a couple of unsuccessful searches, we started noticing interesting changes in behavior. In addition to many of them sighing or starting to bite their nails, users sometimes started to type their searches as natural language questions, they sometimes spent a very long time simply staring at the results page, and they sometimes completely changed their approach to the task.

We were fascinated by these findings as they seemed to be signals that the computer could potentially detect while the user is searching. We formulated the initial findings from the usability lab study as hypotheses which we then tested in a larger web-based user study.

The overall findings were promising: we found five signals that seemed to indicate that users were struggling in the search task. Those signals were: use of question queries, use of advanced operators, spending more time on the search results page, formulating the longest query in the middle of the session, and spending a larger proportion of the time on the search results page. None of these signals alone are strong enough predictors of users having problems in search tasks. However, when used together, we believe we can use them to build a model that will one day make it possible for computers to detect frustration in real time.

You can read the full text of the paper here.

Focusing on Our Users: The Google Health Redesign

Posted by Hendrik Mueller, User Experience Researcher

When I relocated to New York City a few years ago, some of the most important health information for me to have on hand was my immunization history. At the time, though, my health records were scattered, and it felt like a daunting task to organize them -- a not-uncommon problem that many people face. For me, the solution came when Google Health became available in May of 2008, and I started using it to organize my health information and keep it more manageable. I also saw the potential to do much more within Google Health, such as tracking my overall fitness goals. When I joined the Google Health team as the lead user experience researcher, I was curious about the potential for Google Health to impact people’s lives beyond things like immunization tracking and how we could make the product a lot easier to use. So I set out to explore how to expand and improve Google Health.

Here at Google, we focus on the user throughout the entire product development process. So before Google Health was first launched, we interviewed many people about how they managed their medical records and other health information to better understand their needs. We then iteratively created and tested multiple concepts and designs. After our initial launch, we followed up with actual Google Health users through surveys, interviews, and usability studies to understand how well we were meeting their needs.



From this user research, we learned what was working in the product and what needed to be improved. Here are some of the things our users found especially useful:

• Organizing and tracking health-related information in a single place that is accessible from anywhere at any time
• Sharing medical records easily with loved ones and health care providers, either by allowing online access or by printing out health summaries
• Referencing rich information about health topics, aggregated from trusted sources and Google search results

Our users also described to us the benefits they saw from using Google Health:

“Google Health gives me many tools to research my prescriptions and symptoms, and to track all of the many tests I keep having. Google Health made several necessary and cumbersome tasks easy and worry free.”

“For years now, I've tried to remember my son’s allergies and medications, but the list has grown so long, that I kept forgetting one or two when a doctor asked me about them. That can't happen again because I now have a single place to keep up with them. And I love the fact that I can print off information for situations when I really need it.”

“I really like that I can share my profile with others. I want my mom to know my medical information, just in case anything ever happens to me.”

While we learned that our users were clearly getting positive results from using Google Health, our research also taught us that more was needed. We learned that we needed to make fundamental changes to fully meet the needs of all of our current and prospective users, such as those that are chronically ill, those who care for family members, and especially those users looking to track and improve their wellness and fitness.

On this last point, our user surveys already pointed out that there was more we could do to help our users track and manage their wellness, not just their sickness, so we conducted further research about how people collect, monitor, track, and analyze their wellness data. We interviewed several people in their homes and invited others into our usability labs. As a result, we identified several areas where we could improve Google Health to make it a more useful wellness tool, including:

• Dedicated wellness tracking including pre-built and custom trackers
• Efficient manual data entry as well as automatic data collection through devices
• A customizable summary dashboard of wellness and other health topics
• Goal setting and progress tracking using interactive charts
• Personalized pages for each topic with rich charts, journaling, and related information

These insights led us to a whole new set of design proposals. We gathered feedback on the resulting sketches, wire-frames, and screenshots from active and new Google Health users. The results throughout this process were eye-opening. While we were on the right track for some parts of the design, other parts had to be corrected or even redesigned. We went through several iterations until we had a design that tested well and we felt met the user needs our research had uncovered. Finally, we conducted several usability studies with a functioning prototype throughout the product development process to continuously improve usability and function.



At the end, the collaboration between the user experience, engineering, and product management teams resulted in an entirely new user experience for Google Health combined with a set of new functionality that is now available for you to try out at www.google.com/health. See for yourself how the old and new versions compare. Here is a screenshot of a health profile in the new version:



And this is how the same account and profile looked in the old user interface:



As a Google Health user, I am excited to take advantage of the new design and have already started using it for my own exercise and weight tracking. And on behalf of the user experience team and the entire Google Health team, we’re excited about being able to bring you a new design and more powerful tool that we think will meet more of your health and wellness needs.

We look forward to continuing to explore how we can make Google Health even more useful and easier to use for people like you. As you use Google Health, you may see a link to a feedback survey at the top of the application. If you do, please take the time to fill it out - we will be listening to your input!

Discontinuous Seam Carving for Video Retargeting

Posted by Matthias Grundmann and Vivek Kwatra, Google Research

Videos come in different sizes, resolutions and aspect ratios, but the device used for playback, may it be your TV, mobile phone, or laptop, only has a fixed resolution and form factor. As a result, you cannot watch your favorite old show that came in 4:3 on your new 16:9 HDTV without having black bars on the side, referred to as letterboxing. Likewise, widescreen movies and user-videos uploaded on YouTube are shot using various cameras with wide-ranging formats, so they do not fit completely on the screen. As an alternative to letterboxing, several devices try to upscale the content uniformly, which either changes the aspect ratio, making everything look stretched out, or simply crop the frame, thereby discarding any content that cannot fit the screen after scaling.

At Google Research, together with collaborators from Georgia Tech, we have developed an algorithm that resizes (or retargets) videos to fit the form factor of a given device without cropping, stretching or letterboxing. Our approach uses all of the screen’s precious pixels, while striving to deliver as much video-content of the original as possible. The result is a video that adapts to your needs, so you don’t have to adapt to the video.


Six frames from the result of our retargeting algorithm applied to a sub-clip of “Apologize”, © 2006 One Republic. Original frame is shown on the left, our resized result on the right. The original content is fit to a new aspect ratio.

The key insight is that we can separate the video into salient and non-salient content, which are then treated differently. Think of salient content as actors, faces, or structured objects, where the viewer anticipates specific, important details to perceive it as being correct and unaltered. We cannot change this content beyond uniform scaling without it being noticeable. On the other hand, non-salient content, such as sky, water or a blurry out-of-focus background can be squished or stretched without changing the overall appearance or the viewer noticing a dramatic change.

Our technique, which we call discontinuous seam carving -- named so because it modifies the video by adding or removing disconnected seams (or chains) of pixels -- allows greater freedom in the resizing process than previous approaches. By optimizing for the retargeted video to be consistent with the original, we carefully preserve the shape and motion of the salient content while being less restrictive with non-salient content. The key innovations of our research include: (a) a solution that maintains temporal continuity of the video in addition to preserving its spatial structure, (b) space-time smoothing for automatic as well as interactive (user-guided) salient content selection, and (c) sequential frame-by-frame processing conducive for arbitrary length and streaming video. The outcome is a scalable system capable of retargeting videos featuring complex motions of actors and cameras, highly dynamic content and camera shake. For more details, please refer to our paper or visit the project web-site.

Google Search by Voice: A Case Study

Posted by Johan Schalkwyk, Google Research

Wind the clock back two years with your smart phone in hand. Try to recall doing a search for a restaurant or the latest scores of your favorite sports team. If you’re like me you probably won’t even bother, or you’ll suffer with tiny keys or fat fingers on a touch screen. With Google Search by Voice all that has changed. Now you just tap the microphone, speak, and within seconds you see the result. No more fat fingers.

Google Search by Voice is a result of many years of investment in speech at Google. We started by building our own recognizer (aka GReco ) from the ground up. Our first foray in search by voice was doing local searches with GOOG-411. Then, in November 2008, we launched Google Search by Voice. Now you can search the entire Web using your voice.

What makes search by voice really interesting is that it requires much more than a just good speech recognizer. You also need a good user interface and a good phone like an Android in the hands of millions of people. Besides the excellent computational platform and data availability, the project succeeded due to Google’s culture built around teams that wholeheartedly tackle such challenges with the conviction that they will set a new bar.

In our book chapter, “Google Search by Voice: A Case Study”, we describe the basic technology, the supporting technologies, and the user interface design behind Google Search by Voice. We describe how we built it and what lessons we have learned. As the product required many helping hands to build, this chapter required many helping hands to write. We believe it provides a valuable contribution to the academic community.

The book, Advances in Speech Recognition, is available for purchase from Springer.