Google Americas Faculty Summit Day 1: Mobile Search

Posted by Johan Schalkwyk, Software Engineer

On July 14 and 15, we held our seventh annual Faculty Summit for the Americas with our New York City offices hosting for the first time. Over the next few days, we will be bringing you a series of blog posts dedicated to sharing the Summit's events, topics and speakers. --Ed

Google’s mobile speech team has a lofty goal: recognize any search query spoken in English and return the relevant results. Regardless of whether your accent skews toward a Southern drawl, a Boston twang, or anything in between, spoken searches like “navigate to the Metropolitan Museum,” “call California Pizza Kitchen” or “weather, Scarsdale, New York” should provide immediate responses with a map, the voice of the hostess at your favorite pizza place or an online weather report. The responses must be fast and accurate or people will stop using the tool, and—given that the number of speech queries has more than doubled over the past year—the team is clearly succeeding.

As a software engineer on the mobile speech team, I took the opportunity of the Faculty Summit this week to present some of the interesting challenges surrounding developing and implementing mobile search. One of the immediate puzzles we have to solve is how to train a computer system to recognize speech queries. There are two aspects to consider: the acoustic model, or the sound of letters and words in a language; and the language model, which in English is essentially grammar, or what allows us to predict words that follow one another. The language model we can put together using a huge amount of data gathered from our query logs. The acoustic model, however, is more challenging.

To build our acoustic model, we could conduct “supervised learning” where we collect 100+ hours of audio data from search queries and then transcribe and label the data. We use this data to translate a speech query into a written query. This approach works fairly well, but it doesn’t improve as we collect more audio data. Thus, we use an “unsupervised model” where we continuously add more audio data to our training set as users do speech queries.

Given the scale of this system, another interesting challenge is testing accuracy. The traditional approach is to have human testers run assessments. Over the past year, however, we have determined that our automated system has the same or better level of accuracy as our human testers, so we’ve decided to create a new method for automated testing at scale, a project we are working on now.

The current voice search system is trained on over 230 billion words and has a one million word vocabulary, meaning it understands all the different contexts in which those one million words can be used. It requires multiple CPU decades for training and data processing, plus a significant amount of storage, so this is an area where Google’s large infrastructure is essential. It’s exciting to be a part of such cutting edge research, and the Faculty Summit was an excellent opportunity to share our latest innovations with people who are equally inspired by this area of computer science.

What You Capture Is What You Get: A New Way for Task Migration Across Devices

Posted by Yang Li, Research Scientist

We constantly move from one device to another while carrying out everyday tasks. For example, we might find an interesting article on a desktop computer at work, then bring the article with us on a mobile phone during the commute and keep reading it on a laptop or a TV when we get home. Cloud computing and web applications have made it possible to access the same data and applications on different devices and platforms. However, there are not many ways to easily move tasks across devices that are as intuitive as drag-and-drop in a graphical user interface.

Since last year, our research team started developing new technologies for users to easily migrate their tasks across devices. In a project named Deep Shot, we demonstrated how a user can easily move web pages and applications, such as Google Maps directions, between a laptop and an Android phone by using the phone camera. With Deep Shot, a user can simply take a picture of their monitor with a phone camera, and the captured content automatically shows up and becomes instantly interactive on the mobile phone.

This project was inspired by our observations that many people tend to take a picture of map directions on the monitor using their mobile phone camera, rather than using other approaches such as email. Taking pictures feels more direct and convenient, and fits well our everyday activity that is often more opportunistic. Instead of just capturing raw pixels, Deep Shot recovers the actual contents and applications on the mobile phone based on these pixels. You can find out how Deep Shot keeps user interaction simple and what happens behind the scenes here. Similar to WYSIWYG—What You See Is What You Get—for graphical user interfaces, Deep Shot demonstrates WYCIWYG—What You Capture Is What You Get—for cross-device interaction. We are exploring this interaction style for various task migration situations in our everyday life.



Deep Shot remains a research project at Google. With increasing capabilities of mobile phones and fast growing web applications, we hope to explore more exciting ways to help users carry out their everyday activities.

Languages of the World (Wide Web)

Posted by Daniel Ford and Josh Batson

The web is vast and infinite. Its pages link together in a complex network, containing remarkable structures and patterns. Some of the clearest patterns relate to language.

Most web pages link to other pages on the same web site, and the few off-site links they have are almost always to other pages in the same language. It's as if each language has its own web which is loosely linked to the webs of other languages. However, there are a small but significant number of off-site links between languages. These give tantalizing hints of the world beyond the virtual.

To see the connections between languages, start by taking the several billion most important pages on the web in 2008, including all pages in smaller languages, and look at the off-site links between these pages. The particular choice of pages in our corpus here reflects decisions about what is `important'. For example, in a language with few pages every page is considered important, while for languages with more pages some selection method is required, based on pagerank for example.

We can use our corpus to draw a very simple graph of the web, with a node for each language and an edge between two languages if more than one percent of the offsite links in the first language land on pages in the second. To make things a little clearer, we only show the languages which have at least a hundred thousand pages and have a strong link with another language, meaning at least 1% of off-site links go to that language. We also leave out English, which we'll discuss more in a moment. (Figure 1)

Looking at the language web in 2008, we see a surprisingly clear map of Europe and Asia.
The language linkages invite explanations around geopolitics, linguistics, and historical associations.

Figure 1: Language links on the web. 

The outlines of the Iberian and Scandinavian Peninsulas are clearly visible, which suggest geographic rather than purely linguistic associations.

Examining links between other languages, it seems that many are explained by people and communities which speak both languages.

The language webs of many former Soviet republics link back to the Russian web, with the strongest link from Ukrainian. While Russia is the major importer of Ukrainian products, the bilingual nature of Ukraine is a more plausible explanation. Most Ukrainians speak both languages, and Russian is even the dominant language in large parts of the country.

The link from Arabic to French speaks to the long connection between France and its former colonies. In many of these countries Arabic and French are now commonly spoken together, and there has been significant emigration from these countries to France.

Another strong link is between the Malay/Malaysian and Indonesian webs. Malaysia and Indonesia share a border, but more importantly the languages are nearly eighty percent cognate, meaning speakers of one can easily understand the other.

What about the sizes of each language web? Both the number of sites in each language and the number of urls seen by Google's crawler follow an exponential distribution, although the ordering for each is slightly different (Figure 2). The exact number of pages in each language in 2008 is unknown, since multiple urls may point to the same page and some pages may not have been seen at all. However, the language of an un-crawled url can be guessed by the dominant language of its site. In fact, calendar pages and other infinite spaces mean that there really are an unlimited number of pages on the web, though some are more useful than others.

Figure 2: The number of sites and seen urls per language are roughly exponentially distributed. 

The largest language on the web, in terms of size and centrality, has always been English, but where is it on our map?

Every language on the web has strong links to English, usually with around twenty percent of offsite links and occasionally over forty five percent, such as from Tagalog/Filipino, spoken in the Philippines, and Urdu, principally spoken in Pakistan (Figure 3). Both the Philippines and Pakistan are former British colonies where English is one of the two official languages.

Figure 3: Language links to and from English 

You might wonder whether off-site links landing on English pages can be explained simply by the number of English pages available to be linked to. The webs of other languages in our corpus typically have sixty to eighty percent of their out-language links to English pages. However, only 38 percent of the pages and 42 percent of sites in our set are English, while it attracts 79 percent of all out-language links from other languages.

Chinese and Japanese also seem unusual because there are relatively few links from pages in these languages to pages in English. This is despite the fact that Japanese and Chinese sites are the most popular non-English sites for English sites to link to. However, the number of sites in a language is a strong predictor of its `introversion', or fraction of off-site links to pages in the same language. Taking this into account shows that Chinese and Japanese webs are not unusually introverted given their size. In general, language webs with more sites are more introverted, perhaps due to better availability of content. (Figure 4)

Figure 4: Language size vs introversion. 

There is a roughly linear relationship between the (log) number of sites in a language and the fraction of off-site links which point to pages in the same language, with a correlation of 0.9 if English is removed. However, only 45 percent of off-site links from English pages are to other English pages, making English the most extroverted web language given its size. Other notable outliers are the Hindi web, which is unusually introverted, and the Tagalog and Malay webs which are unusually extroverted.

We can generate another map by connecting languages if the number of links from one to the other is 50 times greater than expected given the number of out-of-language links and the size of the language linked to (Figure 5). This time, the native languages of India show up clearly. Surprising links include those from Hindi to Ukrainian, Kurdish to Swedish, Swahili to Tagalog and Bengali, and Esperanto to Polish.

Figure 5: Unexpected connections, given the size of each language. 

What's happened since 2008? The languages of the web have become more densely connected. There is now significant content in even more languages, and these languages are more closely linked. We hope that tools like Google page translation, voice translation, and other services will accelerate this process and bring more people in the world closer together, whichever languages they speak.

UPDATE 9 July 2011: As has been pointed out in the comments, in both the Philippines and Pakistan, English is one of the two official languages; however, the Philippines was not a British colony.

“Mobile”-ize your business with Google Sites

By the end of this year, it is predicted that over half of all Americans will own a smartphone. With 51% of consumers more likely to purchase from retailers that have mobile-optimized sites, is your website ready to take on this growing mobile trend? We understand that time is the most valuable resource for a small business owner, so to help you save time, we’re launching a new tool: Google Sites mobile landing pages. With Google Sites mobile landing pages, you can build a professional mobile landing page for your business in minutes, for free -- and without any coding experience.

You can set up your mobile site in just a few steps:

1. Visit sites.google.com/mobilize.
2. Choose from one of five templates for your site or start with a blank template.
3. Choose a site name and URL.
4. Give your site a description to make it easier for people to find.
5. Choose whether you want your site to be visible to everyone or only certain people.
6. Add text, images, buttons and gadgets to your site to help personalize it and deliver your message.

Watch the video below to see how easy it was for small business owner, Bob, to mobilize his business with Google Sites:

To get started, visit sites.google.com/mobilize, and see how going mobile can boost your business!

Posted by Shiv Kumar, Google Mobile Specialist

Google Translate welcomes you to the Indic web

Posted by Ashish Venugopal, Research Scientist

(Cross-posted on the Translate Blog and the Official Google Blog)

 

Beginning today, you can explore the linguistic diversity of the Indian sub-continent with Google Translate, which now supports five new experimental alpha languages: Bengali, Gujarati, Kannada, Tamil and Telugu. In India and Bangladesh alone, more than 500 million people speak these five languages. Since 2009, we’ve launched a total of 11 alpha languages, bringing the current number of languages supported by Google Translate to 63.

Indic languages differ from English in many ways, presenting several exciting challenges when developing their respective translation systems. Indian languages often use the Subject Object Verb (SOV) ordering to form sentences, unlike English, which uses Subject Verb Object (SVO) ordering. This difference in sentence structure makes it harder to produce fluent translations; the more words that need to be reordered, the more chance there is to make mistakes when moving them. Tamil, Telugu and Kannada are also highly agglutinative, meaning a single word often includes affixes that represent additional meaning, like tense or number. Fortunately, our research to improve Japanese (an SOV language) translation helped us with the word order challenge, while our work translating languages like German, Turkish and Russian provided insight into the agglutination problem.

You can expect translations for these new alpha languages to be less fluent and include many more untranslated words than some of our more mature languages—like Spanish or Chinese—which have much more of the web content that powers our statistical machine translation approach. Despite these challenges, we release alpha languages when we believe that they help people better access the multilingual web. If you notice incorrect or missing translations for any of our languages, please correct us; we enjoy learning from our mistakes and your feedback helps us graduate new languages from alpha status. If you’re a translator, you’ll also be able to take advantage of our machine translated output when using the Google Translator Toolkit.

Since these languages each have their own unique scripts, we’ve enabled a transliterated input method for those of you without Indian language keyboards. For example, if you type in the word “nandri,” it will generate the Tamil word நன்றி (see what it means). To see all these beautiful scripts in action, you’ll need to install fonts* for each language.

We hope that the launch of these new alpha languages will help you better understand the Indic web and encourage the publication of new content in Indic languages, taking us five alpha steps closer to a web without language barriers.

*Download the fonts for each language: Tamil, Telugu, Bengali, Gujarati and Kannada.

Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths

Posted by Matthias Grundmann, Vivek Kwatra, and Irfan Essa, Research Team

Earlier this year, we announced the launch of new features on the YouTube Video Editor, including stabilization for shaky videos, with the ability to preview them in real-time. The core technology behind this feature is detailed in this paper, which will be presented at the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR 2011).

Casually shot videos captured by handheld or mobile cameras suffer from significant amount of shake. Existing in-camera stabilization methods dampen high-frequency jitter but do not suppress low-frequency movements and bounces, such as those observed in videos captured by a walking person. On the other hand, most professionally shot videos usually consist of carefully designed camera configurations, using specialized equipment such as tripods or camera dollies, and employ ease-in and ease-out for transitions. Our goal was to devise a completely automatic method for converting casual shaky footage into more pleasant and professional looking videos.



Our technique mimics the cinematographic principles outlined above by automatically determining the best camera path using a robust optimization technique. The original, shaky camera path is divided into a set of segments, each approximated by either a constant, linear or parabolic motion. Our optimization finds the best of all possible partitions using a computationally efficient and stable algorithm.

To achieve real-time performance on the web, we distribute the computation across multiple machines in the cloud. This enables us to provide users with a real-time preview and interactive control of the stabilized result. Above we provide a video demonstration of how to use this feature on the YouTube Editor. We will also demo this live at Google’s exhibition booth in CVPR 2011.

For further details, please read our paper.

Google at CVPR 2011

Posted by Mei Han and Sergey Ioffe, Research Team

The computer vision community will get together in Colorado Springs the week of June 20th for the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR 2011). This year will see a record number of people attending the conference and 27 co-located workshops and tutorials. The registration was closed at 1500 attendees even before the conference started.

Computer Vision is at the core of many Google products, such as Image Search, YouTube, Street View, Picasa, and Goggles, and as always, Google is involved in several ways with CVPR. Andrew Senior is serving as an area chair of CVPR 2011 and many Googlers are reviewers. Googlers also co-authored these papers:

• Where's Waldo: Matching People in Images of Crowds by Rahul Garg, Deva Ramanan, Steve Seitz, Noah Snavely
• Visual and Semantic Similarity in ImageNet by Thomas Deselaers, Vittorio Ferrari
• Multicore Bundle Adjustment by Changchang Wu, Sameer Agarwal, Brian Curless, Steve Seitz
• A Hierarchical Conditional Random Field Model for Labeling and Segmenting Images of Street Scenes by Qixing Huang, Mei Han, Bo Wu, Sergey Ioffe
• Kernelized Structural SVM Learning for Supervised Object Segmentation by Luca Bertelli, Tianli Yu, Diem Vu, Salih Gokturk
• Discriminative Tag Learning on YouTube Videos with Latent Sub-tags by Weilong Yang, George Toderici
• Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths by Matthias Grundmann, Vivek Kwatra, Irfan Essa
• Image Saliency: From Local to Global Context by Meng Wang, Janusz Konrad, Prakash Ishwar, Yushi Jing, Henry Rowley

If you are attending the conference, stop by Google’s exhibition booth. In addition to talking with Google researchers, you will get to see examples of exciting computer vision research that has made it into Google products including, among others, the following:

• Google Earth Facade Shadow Removal by Mei Han, Vivek Kwatra, and Shengyang Dai
  We will demonstrate our technique for removing shadows and other lighting/texture artifacts from building facades in Google Earth. We obtain cleaner, clearer, and more uniform textures which provide users with an improved visual experience.
• Video Stabilization on YouTube Editor by Matthias Grundmann, Vivek Kwatra, and Irfan Essa
  Casually shot videos captured by handheld or mobile cameras suffer from significant amount of shake. In contrast, professionally shot video usually employs stabilization equipment such as tripods or camera dollies, and employ ease-in and ease-out for transitions. Our technique mimics these cinematographic principles, by optimally dividing the original, shaky camera path into a set of segments and approximating each with either constant, linear or parabolic motion using a computationally efficient and stable algorithm. We will showcase a live version of our algorithm, featuring real-time performance and interactive control, which is publicly available at youtube.com/editor.
• Tag Suggest for YouTube by George Toderici and Mehmet Emre Sargin
  YouTube offers millions of users the opportunity to upload videos and share them with their friends. Many users would love to have their videos discoverable but don't annotate them properly. One new feature on YouTube that seeks to address this problem is tag prediction based on video content and independently based on text metadata.

6/17/2011 UPDATE: "Posted by" was changed to include Sergey Ioffe.