Google launches Korean Voice Search

Posted by Mike Schuster & Martin Jansche, Google Research

On June 16th, we launched our Korean voice search system. Google Search by Voice has been available in various flavors of English since 2008, in Mandarin and Japanese since 2009, and in French, Italian, German and Spanish just a few weeks ago (some more details in a recent blog post).

Korean speech recognition has received less attention than English, which has been studied extensively around the world by teams in both English and non-English speaking countries. Fundamentally, our methodology for developing a Korean speech recognition system is similar to the process we have used for other languages. We created a set of statistical models: an acoustic model for the basic sounds of the language, a language model for the words and phrases of the language, and a dictionary mapping the words to their pronunciations. We trained our acoustic model using a large quantity of recorded and transcribed Korean speech. The language model was trained using anonymized Korean web search queries. Once these models were trained, given an audio input, we can compute and display the most likely spoken phrase, along with its search result.

There were several challenges in developing a Korean speech recognition system, some unique to Korean, some typical of Asian languages and some universal to all languages. Here are some examples of problems that stood out:

• Developing a Korean dictionary: Unlike English, where there are many publicly-available dictionaries for mapping words to their pronunciations, there are very few available for Korean. Since our Korean recognizer knows several hundred thousand words, we needed to create these mappings ourselves. Luckily, Korean has one of the most elegant and simple writing systems in the world (created in the 15th century!) and this makes mapping Korean words to pronunciations relatively straightforward. However, we found that Koreans also use quite a few English words in their queries, which complicates the mapping process. To predict these pronunciations, we built a statistical model using data from an existing (smaller) Korean dictionary.
• Korean word boundaries: Although Korean orthography uses spaces to indicate word boundaries (unlike Japanese or Mandarin), we found that people use word boundaries inconsistently for search queries. To limit the size of the vocabulary generated from the search queries, we used statistical techniques to cut rare long words into smaller sub-words (similarly to the system we developed for Japanese).
  
• Pronunciation exceptions: Korean (like all other languages) has many exceptions for pronunciations that are not immediately obvious. For example, numbers are often written as digit sequences but not necessarily spoken this way (2010 = 이천십). The same is true for many common alphanumeric sequences like “mp3”, “kbs2” or mixed queries like “삼성 tv”, which often contain spelled letters and possibly English spoken digits as opposed to Korean ones.
• Encoding issues: Korean script (Hangul) is written in syllabic blocks, with each block containing at least two of the 24 modern Hangul letters (Jamo), at least one consonant and one vowel. Including the normal ASCII characters this brings the total number of possible basic characters to over 10000, not including Hanja (used mostly in the formal spelling of names). So, despite its simple writing system, Korean still presents the same challenge of handling a large alphabet that is typical of Asian languages.
• Script ambiguity: We found that some users like to use English native words and others the Korean transliteration (example: “ncis season 6” vs. “ncis 시즌6”). This makes it challenging to train and evaluate the system. We use a metric that estimates whether our transcription will give the correct web page result on the user’s smart phone screen, and such script variations make this tricky.
• Recognizing rare words: The recognizer is good at recognizing things users often type into the search engine, such as cities, shops, addresses, common abbreviations, common product model numbers and well-known names like “김연아”. However, rare words (like many personal names) are often harder for us to recognize. We continue to work on improving those.
• Every speaker sounds different: People speak in different styles, slow or fast, with an accent or without, have lower or higher pitched voices, etc. To make our system work for all these different conditions, we trained our system using data from many different sources to capture as many conditions as possible.
  

When speech recognizers make errors, the reason is usually that the models are not good enough, and that often means they haven’t been trained on enough data. For Korean (and all other languages) our cloud computing infrastructure allows us to retrain our models frequently and using an ever growing amount of data to continually improve performance. Over time, we are committed to improve the system regularly to make speech a user-friendly input method on mobile devices.

Google Search by Voice now available in France, Italy, Germany and Spain

Posted by Thad Hughes, Martin Jansche, and Pedro Moreno, Google Research

Google’s speech team is composed of people from many different cultural backgrounds. Indeed, if we count the languages spoken by our teammates, the number comes to well over a dozen. Given our own backgrounds and interests, we are naturally excited to extend our software to work with many different languages and dialects. After testing the waters with English, Mandarin Chinese, and Japanese, we decided to tackle four main European languages which are often referred to as FIGS - French, Italian, German and Spanish.

Developing Voice Search systems in each of these languages presented its own challenges. French and Spanish required special work to deal with diacritic and accent marks (e.g. ç in French, ñ in Spanish). When we develop a new language we tweak our dictionaries based on user generated content. To our surprise we found that a lot of this content in French and Spanish often uses non-standard orthography. For example a French speaker might type “francoise” into a search engine and still expect it to return results for “Françoise”. Likewise in Spanish a user might type “espana” and expect results for the term “España”. Of course a lot of this has to do with the fact that, until recently, domain names (like www.elpais.es) did not allow diacritics, and that entering special characters is often painful but omitting diacrictics is usually not an obstacle to communication. However, non-standard spellings distort the intended pronunciations. For example, if “francoise” were a real French word, one would expect it to be pronounced “franquoise”. In order to capture the intended pronunciation of the non-standard spellings, we fixed the orthography in our dictionaries for Spanish and French automatically. While this is not perfect, it deals with many of the offending cases.

Since our Voice search systems typically understand more than a million different words in each language, developing pronunciation dictionaries is one of the most critical tasks. We need the dictionary to match what the user said with the written form. Not surprisingly we found that dictionary development for some languages like Spanish and Italian to be extremely easy, as they have very regular orthographies. In fact the core of our Spanish pronunciation module consists of less than 100 lines of source code. Other languages like German and French have more complex orthographies. For example in French “au”, “eaux” and “hauts” are all pronounced “o”.

A notable aspect of German (especially “Internet German”) is that a lot of English words are in common usage. We do our best to recognize thousands of English words, even though English contains some sounds that don’t exist in German, like “th” in “the”. One of the trickiest examples we came across was when one of our volunteers read “nba playoffs 2009”, saying “nba playoffs” in English followed by “zwei tausend neun” in German. So go ahead and search for “Germany’s Next Topmodel” or “Postbank Online”, see if it works for you.

German is also notorious for having long, complex words. Our favorite examples include:

• Berufskraftfahrerqualifikationsgesetz (or shorter: BKrFQG)
• Eierschalensollbruchstellenverursacher
• Verkehrsinfrastrukturfinanzierungsgesellschaft
• Stichpimpulibockforcelorum
• Hypothalamus-Hypophysen-Nebennierenrinde-Achse

Just for fun, compare how long it takes you to say these to Voice Search vs. typing them.

Even though a vocabulary size of one million words sounds like a large number, each of these languages has even more words, so we need a procedure to select which ones to model. We obviously do not do this manually and instead use statistical procedures to identify the list of words we will allow. We do this by looking at many sources of data and looking at the frequency of words. It is therefore surprising to find sometimes really weird terms selected by our algorithms. For example in Spanish we found these unusual words:

• supercalifragilisticespialidoso
• chiripitiflautico
• esternocleidomastoideo

So, in the unlikely event that you ever try a Spanish voice search query like this “imágenes del músculo supercalifragilisticoespialidoso chiripitiflautico esternocleidomastoideo” you may be surprised to see that it works.

French, Italian, German, and Spanish are spoken in many parts of the world. In this first release of Google Search by Voice in these languages, we initially only support the varieties spoken in France, Italy, Germany, and Spain, respectively. The reason is that almost all aspects of a Voice Search system are affected by regional variation: French speakers from different regions have slightly different accents, use a number of different words, and will want to search for different things. Eventually, we plan to support other regions as well, and we will work hard to make sure our systems work well for all of you.

So, we hope you find these new voice search system useful and fun to use. We definitely had a “supercalifragilisticoespialidoso chiripitiflautico” time developing them.

Google Fusion Tables celebrates one year of data management

Posted by Alon Halevy, Google Research and Rebecca Shapley, User Experience

A year ago we launched Google Fusion Tables, an easy way to integrate, visualize and collaborate on data tables in the Google cloud. You used it and saw the potential, and told us what else you wanted. Since then, we’ve responded by offering programmatic access through the Fusion Tables API, math across data columns owned by multiple people, and search on the collection of tables that have been made public. We published about Fusion Tables in SIGMOD 2010 and in the First Symposium on Cloud Computing. And since the map visualizations were such a hit, we made them even better by supporting large numbers of points, lines and polygons, custom HTML in map pop-up balloons complete with tutorials and integration with the Google Maps API. We’ve made all this capability available on Google’s cloud and are excited to see examples every day of how our cloud approach to data tables is changing the game and making structured data management, collaboration, and publishing fast, easy, and open.

But more exciting than all the features we’ve been releasing is the things that people have been *doing* with Fusion Tables. News agencies have been taking advantage of Fusion Tables to map data that governments make public, and tell a more complete story (see the L.A. Times, Knoxville News, and Chicago Tribune). Just this month the State of California kicked off an application development contest, hosting data sets like this one in Fusion Tables for easy API access for developers. And the US Department of Health and Human Services held the Community Health Data Forum, where attendees presented data applications such as the heart-friendly and people-friendly hospital-finder, built with Google Fusion Tables.

It continues to astound us how quickly our users are able to pull together these kinds of compelling data applications with Fusion Tables, again showing the power of a cloud approach to data. Fusion Tables were the multimedia extension to Joseph Rossano’s art exhibit on Butterflies and DNA barcodes, an easy way to map real-estate in Monterey county or potholes in Spain, provided the geo-catalog for wind power data and ethanol-selling stations, and even the data backend for an geo portal to organize water data for Africa, among many, many other uses.

As we head into our second year, we’re looking forward to delivering more tools that make data management easier and more powerful on the web. What’s next for Fusion Tables? Request your favorite features on our Feature Request (a special implementation of Google Moderator), and follow the latest progress of Fusion Tables on our User Group, Facebook, and Twitter. We love to hear from you!

Recent Accomplishments by Research Award Recipients

Posted by Maggie Johnson, Director of Education and University Relations

Through Google’s University Relations program, we maintain strong ties with academic institutions globally, pursuing innovative research in core areas relevant to our mission. It’s especially satisfying when our award recipients are honored for the work that we have been fortunate to sponsor. Here are some recent accomplishments:

• Jimmy Lin and his student Chris Dyer (University of Maryland; Google/IBM ACCI, NSF award) just published a book on "Data-Intensive Text Processing with MapReduce", Morgan & Claypool Publishers, 2010
• Raju Balakrishnan's work on SourceRank (Subbarao Kambhampati's student at Arizona State University; 2008 grant) was given the best poster award at the World Wide Web conference
• Allison Druin and Ben Bederson (University of Maryland; 2008 grant) received a Social Impact Award from ACM, 2010
• Susan Eggers (University of Washington; 2009 grant) received ACM-W Athena Lecturer Award, 2009
• Nick McKeown (Stanford University; 2008 grant) received IEEE Koji Kobayashi Computers and Communication Award, 2009
• Students from Shanghai Jiaotong University have been crowned the 2010 ACM International Collegiate Programming Contest World Champions. Shanghai Jiaotong and 3 other Chinese universities that placed in the top 15 are Google partner universities in China, 2 of which were recipients of Google research awards
  

We're glad to have been a part of making these fantastic accomplishments possible. More information on our research award program can be found on our website.

Five more languages on translate.google.com

[Cross-posted with the Google Translate Blog and the Official Google Blog]

Posted by Ashish Venugopal, Research Scientist

At Google, we are always trying to make information more accessible, whether by adding auto-captioning on YouTube and virtual keyboards to search or by providing free translation of text, websites and documents with Google Translate. In 2009, we announced the addition of our first “alpha” language, Persian, on Google Translate. Today, we are excited to add five more alpha languages: Azerbaijani, Armenian, Basque, Urdu and Georgian — bringing the total number of languages on Google Translate to 57.

These languages are available while still in alpha status. You can expect translations to be less fluent than for our other languages, but they should still help you understand the multilingual web. We are working hard to “graduate” these new language out of alpha status, just as we did some time ago with Persian. You can help us improve translation quality as well. If you notice an incorrect translation, we invite you click "Contribute a better translation". If you are a translator, then you can contribute translation memories with the Translator Toolkit. This helps us build better machine translation systems especially for languages that are not well represented on the web.

Collectively, Armenian, Azerbaijani, Basque, Georgian and Urdu have roughly 100 million speakers. We hope that these speakers can now more easily access the entire multilingual web in their own language. Try translating these and other languages at translate.google.com. Here are some phrases from the new alpha languages to get you started:

Baietz lehenengoan
میں خوش قسمت محسوس کر رہا ہوں
բախտաւոր եմ զգում
Mən şanslıyam
იღბალს მივენდობი

Lessons learned developing a practical large scale machine learning system

Posted by Simon Tong, Google Research

When faced with a hard prediction problem, one possible approach is to attempt to perform statistical miracles on a small training set. If data is abundant then often a more fruitful approach is to design a highly scalable learning system and use several orders of magnitude more training data.

This general notion recurs in many other fields as well. For example, processing large quantities of data helps immensely for information retrieval and machine translation.

Several years ago we began developing a large scale machine learning system, and have been refining it over time. We gave it the codename “Seti” because it searches for signals in a large space. It scales to massive data sets and has become one of the most broadly used classification systems at Google.

After building a few initial prototypes, we quickly settled on a system with the following properties:

• Binary classification (produces a probability estimate of the class label)


• Parallelized


• Scales to process hundreds of billions of instances and beyond


• Scales to billions of features and beyond


• Automatically identifies useful combinations of features


• Accuracy is competitive with state-of-the-art classifiers


• Reacts to new data within minutes

Seti’s accuracy appears to be pretty decent. For example, tests on standard smaller datasets indicate that it is comparable with modern classifiers.

Seti has the flexibility to be used on a broad range of training set sizes and feature sets. These sizes are substantially larger than those typically used in academia (e.g., the largest UCI dataset has 4 million instances). A sample of the data sets used with Seti gives the following statistics:

	Training set size	Unique features
Mean	100 Billion	1 Billion
Median	1 Billion	10 Million

A good machine learning system is all about accuracy, right?

In the process of designing Seti we made plenty of mistakes. However, we made some good key decisions as well. Here are a few of the practical lessons that we learned. Some are obvious in hindsight, but we did not necessarily realize their importance at the time.

Lesson: Keep it simple (even at the expense of a little accuracy).

Having good accuracy across a variety of domains is very important, and we were tempted to focus exclusively on this aspect of the algorithm. However, in a practical system there are several other aspects of an algorithm that are equally critical:

• Ease of use: Teams are more willing to experiment with a machine learning system that is simple to set up and use. Those teams are not necessarily die-hard machine learning experts, and so they do not want to waste much time figuring out how to get a system up and running.


• System reliability: Teams are much more willing to deploy a reliable machine learning system in a live environment. They want a system that is dependable and unlikely to crash or need constant attention. Early versions of Seti had marginally better accuracy on large data sets, but were complex, stressed the network and GFS architecture considerably, and needed constant babysitting. The number of teams willing to deploy these versions was low.

Seti is typically used in places where a machine learning system will provide a significant improvement in accuracy over the existing system. The gains are usually large enough that most teams do not care about the small differences in accuracy between different flavors of algorithms. And, in practice, the small differences are often washed out by other effects such as better data filtering, adding another useful feature, parameter tuning, etc. Teams much prefer having a stable, scalable and easy-to-use classification system. We found that these other aspects can be the difference between a deployable system and one that gets abandoned.

It is perhaps less academically interesting to design an algorithm that is slightly worse in accuracy, but that has greater ease of use and system reliability. However, in our experience, it is very valuable in practice.

Lesson: Start with a few specific applications in mind.

It was tempting to build a learning system without focusing on any particular application. After all, our goal was to create a large scale system that would be useful on a wide variety of present and future classification tasks. Nevertheless, we decided to focus primarily on a small handful of initial applications. We believe this decision was useful in several ways:

• We could examine what the small number of domains had in common. By building something that would work for a few domains, it was likely the resulting system would be useful for others.


• More importantly, it helped us quickly decide what aspects were unnecessary. We noticed that it was surprisingly easy to over-generalize or over-engineer a machine learning system. The domains grounded our project in reality and drove our decision making. Without them, even deciding how broad to make the input file format would have been harder (e.g., is it important to permit binary/categorical/real-valued features? Multiple classes? Fractional labels? Weighted instances?).


• Working with a few different teams as initial guinea pigs allowed us to learn about common teething problems, and helped us smooth the process of deployment for future teams.

Lesson: Know when to say “no”.

We have a hammer, but we don't want to end up with bent screws. Being machine learning practitioners, it was very tempting for us to always recommend using machine learning for a problem. We saw very early on that, despite its many significant benefits, machine learning typically adds complexity, opacity and unpredictability to a system. In reality, simpler techniques are sometimes good enough for the task at hand. And in the long run, the extra effort that would have been spent integrating, maintaining and diagnosing issues with a live machine learning system could be spent on other way of improving the system instead.

Seti is often used in places where there is a good chance of significantly improving predictive accuracy over the incumbent system. And we usually advise teams against trying the system when we believe there is likely to be only a small improvement.

Large-scale machine learning is an important and exciting area of research. It can be applied to many real world problems. We hope that we have given a flavor of the challenges that we face, and some of the practical lessons that we have learned.

Hopping on a Face Manifold via People Hopper

Posted by Sanjiv Kumar and Henry Rowley, Google Research

A few weeks ago we announced the launch of a new orkut application in Google Labs called People Hopper that lets you take your profile image and "morph" it into a friend's photo, using publicly available images from other orkut users along the way. No computer graphics tricks are used; every image along the transition comes from real orkut users.



The application hops across millions of public user images in orkut so that one image is smoothly transformed into another. First, faces are automatically detected in public profile images and normalized in contrast and size. Then, for each image, we find other public profile images that are similar to it. Finally, when you pick two faces, we just hop between similar public images, step-by-step, until the connection is made.

People Hopper was outcome of the following research question: Is it possible to learn a low-dimensional space (i.e. a manifold) in which all the human face images live? It is well-known in the machine learning community that to recover the true underlying manifold one needs a large number of samples from it. In 2008, we published a paper at CVPR in which we learned a face manifold using tens of millions of images, which is still the largest scale manifold learning study to date.

To be able to do manifold learning at such a large scale, we had to address two key issues: First, how to do nearest neighbor search in very large databases? We used spill-trees to speed up the search to construct the neighborhood graph. Second, how to do spectral decomposition of matrices which are hundreds of terabytes in size? We investigated sampling-based matrix decomposition methods to handle such matrices.

One way to visualize the quality of the manifold is to find shortest paths between pairs of faces in the manifold, and observe the smoothness of the transitions between them. This is exactly what People Hopper does. Curious? Try People Hopper on orkut now!

The quality of the face manifold depends on three main factors: the number of faces in the manifold, the appearances of those faces, and the similarity measure used for image matching. Since we cannot control the number or appearance of the faces in orkut profiles, it may happen that for a particular image there exists no visually similar image in the database. We plan to update our graph over public profile images frequently, so the quality of paths will change as users join orkut or update their profile images. Finding better contrast normalization and similarity measures is a topic of continuing research. Currently we don't use any face-specific features during this process, just simple image distances.

We are eager to hear your feedback on how we can make this application more fun and useful. Also, if for any reason you would prefer your profile image not to appear in any People Hopper path, you can choose to opt out by visiting our People Hopper homepage.