$6 million to faculty in Q4 Research Awards

Posted by Maggie Johnson, Director of Education and University Relations

We've just completed the latest round of Google Research Awards, our program which identifies and supports faculty pursuing research in areas of mutual interest. We had a record number of submissions this round, and are funding 112 awards across 20 different areas—for a total of more than $6 million. We’re also providing more than 150 Android devices for research and curriculum development to faculty whose projects rely heavily on Android hardware.

The areas that received the highest level of funding, due to the large number of proposals in these areas, were systems and infrastructure, human computer interaction, security and multimedia. We also continue to support international research; in this round, 29 percent of the funding was awarded to universities outside the U.S.

Some examples from this round of awards:

• Injong Rhee, North Carolina State University. Experimental Evaluation of Increasing TCP Initial Congestion Window (Systems)
• James Jones, University of California, Irvine. Bug Comprehension Techniques to Assist Software Debugging (Software Engineering)
• Yonina Eldar, Technion, Israel. Semi-Supervised Regression with Auxiliary Knowledge (Machine Learning)
• Victor Lavrenko, University of Edinburgh, United Kingdom. Interactive Relevance Feedback for Mobile Search (Information Retrieval)
• James Glass, MIT. Crowdsourcing to Acquire Semantically Labelled Text and Speech Data for Speech Understanding (Speech)
• Chi Keung Tang, The Hong Kong University of Science and Technology. Quasi-Dense 3D Reconstruction from 2D Uncalibrated Photos (Geo/Maps)
• Phil Blunsom, Oxford, United Kingdom. Unsupervised Induction of Multi-Nonterminal Grammars for Statistical Machine Translation (Machine Translation)
• Oren Etzioni, University of Washington. Accessing the Web utilizing Android Phones, Dialogue, and Open Information Extraction (Mobile)
• Matthew Salganik, Princeton. Developments in Bottom-Up Social Data Collection (Social)

The full list of this round’s award recipients can be found in this PDF. For more information on our research award program, visit our website. And if you’re a faculty member, we welcome you to apply for one of next year’s two rounds. The deadline for the first round is February 1.

Four Googlers elected ACM Fellows this year

Posted by Alfred Spector, VP of Research

I am delighted to share with you that, like last year, the Association for Computing Machinery (ACM) has announced that four Googlers have been elected ACM Fellows in 2010, the most this year from any single corporation or institution.

Luiz Barroso, Dick Lyon, Muthu Muthukrishnan and Fernando Pereira were chosen for their contributions to computing and computer science that have provided fundamental knowledge to the field and have generated multiple innovations.

On behalf of Google, I congratulate our colleagues, who join the 10 other ACM Fellows and other professional society awardees at Google in exemplifying our extraordinarily talented people. I’ve been struck by the breadth and depth of their contributions, and I hope that they will serve as inspiration for students and computer scientists around the world.

You can read more detailed summaries of their achievements below, including the official citations from ACM—although it’s really hard to capture everything they’ve accomplished in one paragraph!

Dr. Luiz Barroso: Distinguished Engineer
For contributions to multi-core computing, warehouse scale data-center architectures, and energy proportional computing

Over the past decade, Luiz has played a leading role in the definition and implementation of Google’s cluster architecture which has become a blueprint for the computing systems behind the world’s leading Internet services. As the first manager of Google’s Platforms Engineering team, he helped deliver multiple generations of cluster systems, including the world’s first container-based data center. His theoretical and engineering insights into the requirements of this class of machinery have influenced the processor industry roadmap towards more effective products for server-class computing. His book "The Datacenter as a Computer" (co-authored with Urs Hoelzle) was the first authoritative publication describing these so-called warehouse-scale computers for computer systems professionals and researchers. Luiz was among the first computer scientists to recognize and articulate the importance of energy-related costs for large data centers, and identify energy proportionality as a key property of energy efficient data centers. Prior to Google, at Digital Equipment's Western Research Lab, he worked on Piranha, a pioneering chip-multiprocessing architecture that inspired today’s popular multi-core products. As one of the lead architects and designers of Piranha, his papers, ideas and numerous presentations stimulated much of the research that led to products decades later.

Richard Lyon: Research Scientist
For contributions to machine perception and for the invention of the optical mouse

In the last four years at Google, Dick led the team developing new camera systems and improved photographic image processing for Street View, while leading another team developing technologies for machine hearing and their application to sound retrieval and ranking. He is now writing a book with Cambridge University Press, and will teach a Stanford course this fall on "Human and Machine Hearing," returning to a line of work that he carried out at Xerox, Schlumberger, and Apple while also doing the optical mouse, bit-serial VLSI computing machines, and handwriting recognition. The optical mouse (1980) is especially called out in the citation, because it exemplifies the field of "semi-digital" techniques that he developed, which also led to his work on the first single-chip Ethernet device. And more recently, as chief scientist at Foveon, Dick invented and developed several new techniques for color image sensing and processing, and delivered acclaimed cameras and end-user software. A hallmark of Dick’s work during his distinguished career has been a practical interplay between theory, including biological theory, and practical computing.

Dr. S. Muthukrishnan: Research Scientist
For contributions to efficient algorithms for string matching, data streams, and Internet ad auctions

Muthu has made significant contributions to the theory and practice of Internet ad systems during his more than four years at Google. Muthu's breakthrough WWW’09 paper presented a general stable matching framework that produces a (desirable) truthful mechanism capturing all of the common variations and more, in contradiction to prevailing wisdom. In display ads, where image, video and other types of ads are shown as users browse, Muthu led Ad Exchange at Google, to automate placement of display ads that were previously negotiated offline by sales teams. Prior to Google, Muthu was well known for his pioneering work in the area of data stream algorithmics (including a definitive book on the subject), which led to theoretical and practical advances still in use today to monitor the health and smooth operation of the Internet. Muthu has a talent for bringing new perspectives to longstanding open problems as exemplified in the work he did on string processing. Muthu has made influential contributions to many other areas and problems including IP networks, data compression, scheduling, computational biology, distributed algorithms and database technology. As an educator, Muthu’s avant garde teaching style won him the Award for Excellence in Graduate Teaching at Rutgers CS, where is on the faculty. As a student remarked in his blog: "there is a magic in his class which kinda spellbinds you and it doesn't feel like a class. It’s more like a family sitting down for dinner to discuss some real world problems. It was always like that even when we were 40 people jammed in for cs-513."

Dr. Fernando Pereira: Research Director
For contributions to machine-learning models of natural language and biological sequences

For the past three years, Fernando has been leading some of Google’s most advanced natural language understanding efforts and some of the most important applications of machine learning technology. He has just the right mix of forward thinking ideas and the ability to put ideas into practice. With this balance, Fernando has has helped his team of research scientists apply their ideas at the scale needed for Google. From when he wrote the first Prolog compiler (for the PDP-10 with David Warren) to his days as Chair at University of Pennsylvania, Fernando has demonstrated a unique understanding of the challenges and opportunities that faced companies like Google with their unprecedented access to massive data sets and its application to the world of speech recognition, natural language processing and machine translation. At SRI, he pioneered probabilistic language models at a time when logic-based models were more popular. At AT&T, his work on a toolkit for finite-state models became an industry standard, both as a useful piece of software and in setting the direction for building ever larger language models. And his year at WhizBang had an influence on other leaders of the field, such as Andrew McCallum at University of Massachusetts and John Lafferty and Tom Mitchell at Carnegie Mellon University, with whom Fernando developed the Conditional Random Field model for sequence processing that has become one of the leading tools of the trade.

Finally, we also congratulate Professor Christos Faloutsos of Carnegie Mellon, who is on sabbatical and a Visiting Faculty Member at Google this academic year. Professor Faloutsos is cited for contributions to data mining, indexing, fractals and power laws.

Update 12/8: Updated Dick Lyon's title and added information about Professor Faloutsos.

Google Launches Cantonese Voice Search in Hong Kong

Posted by Posted by Yun-hsuan Sung (宋雲軒) and Martin Jansche, Google Research

On November 30th 2010, Google launched Cantonese Voice Search in Hong Kong. Google Search by Voice has been available in a growing number of languages since we launched our first US English system in 2008. In addition to US English, we already support Mandarin for Mainland China, Mandarin for Taiwan, Japanese, Korean, French, Italian, German, Spanish, Turkish, Russian, Czech, Polish, Brazilian Portuguese, Dutch, Afrikaans, and Zulu, along with special recognizers for English spoken with British, Indian, Australian, and South African accents.

Cantonese is widely spoken in Hong Kong, where it is written using traditional Chinese characters, similar to those used in Taiwan. Chinese script is much harder to type than the Latin alphabet, especially on mobile devices with small or virtual keyboards. People in Hong Kong typically use either “Cangjie” (倉頡) or “Handwriting” (手寫輸入) input methods. Cangjie (倉頡) has a steep learning curve and requires users to break the Chinese characters down into sequences of graphical components. The Handwriting (手寫輸入) method is easier to learn, but slow to use. Neither is an ideal input method for people in Hong Kong trying to use Google Search on their mobile phones.

Speaking is generally much faster and more natural than typing. Moreover, some Chinese characters – like “滘” in “滘西州” (Kau Sai Chau) and “砵” in “砵典乍街” (Pottinger Street) – are so rarely used that people often know only the pronunciation, and not how to write them. Our Cantonese Voice Search begins to address these situations by allowing Hong Kong users to speak queries instead of entering Chinese characters on mobile devices. We believe our development of Cantonese Voice Search is a step towards solving the text input challenge for devices with small or virtual keyboards for users in Hong Kong.

There were several challenges in developing Cantonese Voice Search, some unique to Cantonese, some typical of Asian languages and some universal to all languages. Here are some examples of problems that stood out:

• Data Collection: In contrast to English, there are few existing Cantonese datasets that can be used to train a recognition system. Building a recognition system requires both audio and text data so it can recognize both the sounds and the words. For audio data, our efficient DataHound collection technique uses smartphones to record and upload large numbers of audio samples from local Cantonese-speaking volunteers. For text data, we sample from anonymized search query logs from http://www.google.com.hk to obtain the large amounts of data needed to train language models.
• Chinese Word Boundaries: Chinese writing doesn’t use spaces to indicate word boundaries. To limit the size of the vocabulary for our speech recognizer and to simplify lexicon development, we use characters, rather than words, as the basic units in our system and allow multiple pronunciations for each character.
• Mixing of Chinese Characters and English Words: We found that Hong Kong users mix more English into their queries than users in Mainland China and Taiwan. To build a lexicon for both Chinese characters and English words, we map English words to a sequence of Cantonese pronunciation units.
• Tone Issues: Linguists disagree on the best count of the number of tones in Cantonese – some say 6, some say 7, or 9, or 10. In any case, it’s a lot. We decided to model tone-plus-vowel combinations as single units. In order to limit the complexity of the resulting model, some rarely-used tone-vowel combinations are merged into single models.
• Transliteration: We found that some users use English words while others use the Cantonese transliteration (e.g.,: “Jordan” vs. “佐敦­”). This makes it challenging to develop and evaluate the system, since it’s often impossible for the recognizer to distinguish between an English word and its Cantonese transliteration. During development we use a metric that simply checks whether the correct search results are returned.
• Different Accents and Noisy Environment: People speak in different styles with different accents. They use our systems in a variety of environments, including offices, subways, and shopping malls. To make our system work in all these different conditions, we train it using data collected from many different volunteers in many different environments.

Cantonese is Google’s third spoken language for Voice Search in the Chinese linguistic family, after Mandarin for Mainland China and Mandarin for Taiwan. We plan to continue to use our data collection and language modeling technologies to help speakers of Chinese languages easily input text and look up information.

Voice Search in Underrepresented Languages

Posted by Pedro J. Moreno, Staff Research Scientist and Johan Schalkwyk, Senior Staff Engineer

Welkom*!

Today we’re introducing Voice Search support for Zulu and Afrikaans, as well as South African-accented English. The addition of Zulu in particular represents our first effort in building Voice Search for underrepresented languages.

We define underrepresented languages as those which, while spoken by millions, have little presence in electronic and physical media, e.g., webpages, newspapers and magazines. Underrepresented languages have also often received little attention from the speech research community. Their phonetics, grammar, acoustics, etc., haven’t been extensively studied, making the development of ASR (automatic speech recognition) voice search systems challenging.

We believe that the speech research community needs to start working on many of these underrepresented languages to advance progress and build speech recognition, translation and other Natural Language Processing (NLP) technologies. The development of NLP technologies in these languages is critical for enabling information access for everybody. Indeed, these technologies have the potential to break language barriers.

We also think it’s important that researchers in these countries take a leading role in advancing the state of the art in their own languages. To this end, we’ve collaborated with the Multilingual Speech Technology group at South Africa’s North-West University led by Prof. Ettiene Barnard (also of the Meraka Research Institute), an authority in speech technology for South African languages. Our development effort was spearheaded by Charl van Heerden, a South African intern and a student of Prof. Barnard. With the help of Prof. Barnard’s team, we collected acoustic data in the three languages, developed lexicons and grammars, and Charl and others used those to develop the three Voice Search systems. A team of language specialists traveled to several cities collecting audio samples from hundreds of speakers in multiple acoustic conditions such as street noise, background speech, etc. Speakers were asked to read typical search queries into an Android app specifically designed for audio data collection.

For Zulu, we faced the additional challenge of few text sources on the web. We often analyze the search queries from local versions of Google to build our lexicons and language models. However, for Zulu there weren’t enough queries to build a useful language model. Furthermore, since it has few online data sources, native speakers have learned to use a mix of Zulu and English when searching for information on the web. So for our Zulu Voice Search product, we had to build a truly hybrid recognizer, allowing free mixture of both languages. Our phonetic inventory covers both English and Zulu and our grammars allow natural switching from Zulu to English, emulating speaker behavior.

This is our first release of Voice Search in a native African language, and we hope that it won’t be the last. We’ll continue to work on technology for languages that have until now received little attention from the speech recognition community.

Salani kahle!**

* “Welcome” in Afrikaans
** “Stay well” in Zulu

Suggesting a Better Remote Control

Posted by Ullas Gargi and Rich Gossweiler, Research Team

It seems clear that the TV is a growing source of online audio-video content that you select by searching. Entering characters of a search string one by one using a traditional remote control and onscreen keyboard is extremely tiresome. People have been working on building better ways to search on the TV, ranging from small keyboards to voice input to interesting gestures you might make to let the TV know what you want. But currently the traditional left-right-up-down clicker dominates as the family room input device. To enter the letters of a show, you click over and over until you get to the desired letter on the on-screen keyboard and then you hit enter to select it. You repeat this mind-numbingly slow process until you type in your query string or at least enough letters that the system can put up a list of suggested completions. Can we instead use a Google AutoComplete style recommendation model and novel interface to make character entry less painful?

We have developed an interaction model that reduces the distance to the predicted next letter without scrambling or moving letters on the underlying keyboard (which is annoying and increases the time it takes to find the next letter). We reuse the highlight ring around the currently selected letter and fill it with 4 possible characters that might be next, but we do not change the underlying keyboard layout. With 4 slots to suggest the next letter and a good prediction model trained on the target corpus, the next letter is often right where you are looking and just a click away.

To learn more about this combination of User Experience and Machine Learning to address a growing problem with searching on TVs, check out our WWW 2010 publication,QuickSuggest.

Exploring Computational Thinking

Posted by Elaine Kao, Education Program Manager

Over the past year, a group of California-credentialed teachers along with our own Google engineers came together to discuss and explore ideas about how to incorporate computational thinking into the K-12 curriculum to enhance student learning and build this critical 21st century skill in everyone.

What exactly is computational thinking? Well, that would depend on who you ask as there are several existing resources on the web that may define this term slightly differently. We define computational thinking (CT) as a set of skills that software engineers use to write the programs that underlay all of the computer applications you use every day. Specific CT techniques include:

• Problem decomposition: the ability to break down a problem into sub-problems
• Pattern recognition: the ability to notice similarities, differences, properties, or trends in data
• Pattern generalization: the ability to extract out unnecessary details and generalize those that are necessary in order to define a concept or idea in general terms
• Algorithm design: the ability to build a repeatable, step-by-step process to solve a particular problem

Given the increasing prevalence of technology in our day-to-day lives and in most careers outside of computer science, we believe that it is important to raise this base level of understanding in everyone.

To this end, we’d like to introduce you to a new resource: Exploring Computational Thinking. Similar to some of our other initiatives in education, including CS4HS and Google Code University, this program is committed to providing educators with access to our curriculum models, resources, and communities to help them learn more about CT, discuss it as a strategy for teaching and understanding core curriculum, as well as easily incorporate CT into their own curriculum, whether it be in math, science, language, history or beyond. The materials developed by the team reflect both the teachers’ expertise in pedagogy and K-12 curriculum as well as our engineers’ problem-solving techniques that are critical to our industry.

Prior to launching this program, we reached out to several educators and classrooms and had them try our materials. Here’s some of the feedback we received:

• CT as a strategy for teaching and student learning works well with many subjects, and can easily be incorporated to support the existing K-12 curriculum
• Our models help to call out the specific CT techniques and provide more structure around the topics taught by educators, many of who were already unknowingly applying CT in their classrooms
• Including programming exercises in the classroom can significantly enrich a lesson by both challenging the advanced students and motivating the students who have fallen behind
• Our examples provide educators with a means of re-teaching topics that students have struggled with in the past, without simply going through the same lesson that frustrated them before

To learn more about our program or access CT curriculum materials and other resources, visit us at www.google.com/edu/ect.

Google at the Conference on Empirical Methods in Natural Language Processing (EMNLP '10)

Posted by Slav Petrov, Research Scientist

The Conference on Empirical Methods in Natural Language Processing (EMNLP '10) was recently held at the MIT Stata Center in Massachusetts. Natural Language Processing is at the core of many of the things that we do here at Google. Googlers have therefore been traditionally part of this research community, participating as program committee members, paper authors and attendees.

At this year's EMNLP conference Google Fellow, Amit Singhal gave an invited keynote talk on "Challenges in running a commercial search engine" where he highlighted some of the exciting opportunities, as well as challenges, that Google is currently facing. Furthermore, Terry Koo (who recently joined Google), David Sontag (former Google PhD Fellowship recipient) and their collaborators from MIT received the Fred Jelinek Best Paper Award for their innovative work on syntactic parsing with the title "Dual Decomposition for Parsing with Non-Projective Head Automata".

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

• Dual Decomposition for Parsing with Non-Projective Head Automata (Fred Jelinek Best Paper Award) by Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag
• "Poetic" Statistical Machine Translation: Rhyme and Meter (see also here) by Dmitriy Genzel, Jakob Uszkoreit, and Franz Och
• Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models by Amarnag Subramanya, Slav Petrov, and Fernando Pereira
• Uptraining for Accurate Deterministic Question Parsing by Slav Petrov, Pi-Chuan Chang, Michael Ringgaard, and Hiyan Alshawi
• Self-training with Products of Latent Variable Grammars by Zhongqiang Huang, Mary Harper, and Slav Petrov

Kuzman Ganchev Receives Presidential Award from the Republic of Bulgaria

Posted by Slav Petrov, Research Scientist

We would like to congratulate Kuzman Ganchev for being the runner-up for the John Atanasoff award from the President of the Republic of Bulgaria. Kuzman recently joined our New York office as a research scientist, after completing his doctoral studies at the University of Pennsylvania.

The John Atanasoff award was established in 2003 and is given annually to a Bulgarian scientist under 35 for scientific or practical contributions to the development of computer and information technology worldwide and significant economic or social importance for Bulgaria. Kuzman received the award for his contributions to computational linguistics and machine learning. Kuzman is the co-author of more than 20 publications that have appeared in international conferences and journals.

Korean Voice Input -- Have you Dictated your E-Mails in Korean lately?

Posted by Mike Schuster & Kaisuke Nakajima, Google Research

Google Voice Search has been available in various flavors of English since 2008, in Mandarin and Japanese since 2009, in French, Italian, German and Spanish since June 2010 (see also in this blog post), and shortly after that in Taiwanese. On June 16th 2010, we took the next step by launching our Korean Voice Search system.

Korean Voice Search, by focusing on finding the correct web page for a spoken query, has been quite successful since launch. We have improved the acoustic models several times which resulted in significantly higher accuracy and reduced latency, and we are committed to improving it even more over time.

While voice search significantly simplifies input for search, especially for longer queries, there are numerous applications on any smartphone that could also benefit from general voice input, such as dictating an email or an SMS. Our experience with US English has taught us that voice input is as important as voice search, as the time savings from speaking rather than typing a message are substantial. Korean is the first non-English language where we are launching general voice input. This launch extends voice input to emails, SMS messages, and more on Korean Android phones. Now every text field on the phone will accept Korean speech input.

Creating a general voice input service had different requirements and technical challenges compared to voice search. While voice search was optimized to give the user the correct web page, voice input was optimized to minimize (Hangul) character error rate. Voice inputs are usually longer than searches (short full sentences or parts of sentences), and the system had to be trained differently for this type of data. The current system’s language model was trained on millions of Korean sentences that are similar to those we expect to be spoken. In addition to the queries we used for training voice search, we also used parts of web pages, selected blogs, news articles and more. Because the system expects spoken data similar to what it was trained on, it will generally work well on normal spoken sentences, but may yet have difficulty on random or rare word sequences -- we will work to keep improving on those.

Korean voice input is part of Google’s long-term goal to make speech input an acceptable and useful form of input on any mobile device. As with voice search, our cloud computing infrastructure will help us to improve quality quickly, as we work to better support all noise conditions, all Korean dialects, and all Korean users.

Clustering Related Queries Based on User Intent

Posted by Jayant Madhavan and Alon Halevy

People today use search engines for all their information needs, but when they pose a particular search query, they typically have a specific underlying intent. However, when looking at any query in isolation, it might not entirely be clear what the underlying intent is. For example, when querying for mars, a user might be looking for more information about the planet Mars, or the planets in the solar system in general, or the Mars candy bar, or Mars the Roman god of war. The ambiguity in intent is most pronounced for queries that are inherently ambiguous and for queries about prominent entities about which there are various different types of information on the Internet. Given such ambiguity, modern search engines try to complement their search results with lists of related queries that can be used to further explore a particular intent.

In a recent paper, we explored the problem of clustering the related queries as a means of understanding the different intents underlying a given user query. We propose an approach that combines an analysis of anonymized document-click logs (what results do users click on) and query-session logs (what sequences of queries do users pose in a search session). We model typical user search behavior as a traversal of a graph whose nodes are related queries and clicked documents. We propose that the nodes in the graph, when grouped based on the probability of a typical user visiting them within a single search session, yield clusters that correspond to distinct user intents.

Our results show that underlying intents (clusters of related queries) almost always correspond to well-understood, high-level concepts. For example, for mars, in addition to re-constructing each of the intents listed earlier, we also find distinct clusters grouping queries about NASA’s missions to the planet, about specific interest in life on Mars, as well as a Japanese comic series, and a grocery chain named Mars. We found that our clustering approach yields better results than earlier approaches that either only used document-click or only query-session information. More details about our proposed approach and an analysis of the resulting clusters can be found in our paper that was presented at the International World Wide Web conference earlier this year.