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.

Read More

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
იღბალს მივენდობი

Read More

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.

Read More

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.

Read More

Announcing Google's Focused Research Awards

Posted by Alfred Spector, Vice President of Research and Special Initiatives

[cross-posted with the Official Google Blog]

It is said that Google is like a university — and not just because everyone eats their lunch off trays in the cafeteria. Like a university, we devote significant energy to research across a wide array of subjects — from semantics to help improve search, to ways we can improve the efficiency of our data centers. Along with our internal efforts, we've long invested in building a strong, mutually beneficial relationship with universities and the research community. We give approximately 150 research grants a year to fund projects across a variety of subjects, we host visiting faculty members here at Google on sabbatical, and last year we started the Google Fellowship Program to fund graduate students doing innovative research in several fields.

Today, we're announcing the first-ever round of Google Focused Research Awards — funding research in areas of study that are of key interest to Google as well as the research community. These awards, totaling $5.7 million, cover four areas: machine learning, the use of mobile phones as data collection devices for public health and environment monitoring, energy efficiency in computing, and privacy. These are all areas in which Google is already deeply invested, and yet there is a long way to go. We're excited to see what these projects contribute to the body of research in these important areas.

These unrestricted grants are for two to three years, and the recipients will have the advantage of access to Google tools, technologies and expertise. We've given awards to 12 projects led by 31 professors at 10 universities:

Machine Learning: William Cohen, Christos Faloutsos, Garth Gibson and Tom Mitchell, Carnegie Mellon University

Use of mobile phones as data collection devices for public health and environment monitoring: Gaetano Borriello, University of Washington and Deborah Estrin, UCLA

Energy efficiency in computing:

• Ricardo Bianchini, Rutgers, Fred Chong, UC Santa Barbara, Thomas F. Wenisch, University of Michigan and Sudhanva Gurumurthi, University of Virginia
• Christos Kozyrakis, Mark Horowitz, Benjamin Lee, Nick McKeown and Mendel Rosenblum, Stanford
• David G. Andersen and Mor. Harchol-Balter, Carnegie Mellon University
• Tajana Simunic Rosing, Steven Swanson and Amin Vahdat, UCSD
• Thomas F. Wenisch, Trevor Mudge, David Blaauw and Dennis Sylvester, University of Michigan
• Margaret Martonosi, Jennifer Rexford, Michael Freedman and Mung Chiang, Princeton

Privacy:

• Ed Felten, Princeton
• Lorrie Cranor, Allesandro Acquisti and Norman Sadeh, Carnegie Mellon University
• Ryan Calo, Stanford CIS
• Andy Hopper, Cambridge University Computing Laboratory

We look forward to working with these researchers over the coming years. And, as we continue to identify key areas of research that are of mutual interest to both university researchers and Google, we will provide awards to support these collaborations. For more information about all of our research programs, check out our University Relations site.

Update at 1:14 PM: Added Allesandro Acquisti and Norman Sadeh to the list of PIs on the CMU privacy project.

Read More

Research Areas of Interest: Building scalable, robust cluster applications

Posted by Brad Chen, Technical Lead/Manager

As part of our series on research areas of interest to Google, we discuss some important areas relating to cluster applications in distributed systems. In the last two decades distributed systems have undergone a metamorphosis from academic curiosities to the foundation of an entire industry. Despite these successes, at Google we see distributed systems as a technology in its infancy, with huge gaps in the supporting research (some examples here and here) that represent some of the most important problems in the space. Here are some examples:

• Resource sharing: Stranded resources like idle memory, CPU, and disk bandwidth represent huge capital and operating expenses that deliver no business value. A cluster system based upon the best published research would be likely to leave 50% or more of hardware resources idle. We encourage researchers to explore hardware/software architectures that facilitate more supple sharing to avoid stranded and underutilized computational resources.
• Balancing cost, performance, and reliability: Current cluster applications tend to be excessively rigid and brittle, offering only coarse controls to tune the balance between reliability, performance and cost. We envision systems that allow cost to be optimized based on an input specification of performance and reliability requirements. An effective solution might allow service level settings to propagate downward through the layered structure of the system.
• Self-maintaining systems: The level of expertise required to troubleshoot today's large systems is one of the biggest barriers to more and larger deployments. The published research in this area has at best marginally improved the need for such rare expertise. We envision systems that can adapt automatically to changing conditions, in which redundancy and multiple geographically distributed data centers simplify rather than complicate manageability. This will require breakthroughs in monitoring and data analysis to address the diversity of failure modes and simplify the task of keeping systems healthy.

Research in these areas will improve the current state of cluster applications enabling systems that are less expensive, easier to monitor, and can scale more efficiently.

Previous posts in the series: Mulitmedia

Read More

Google Cluster Data

Posted by Joseph L. Hellerstein, Manager of Google Performance Analytics

Google faces a large number of technical challenges in the evolution of its applications and infrastructure. In particular, as we increase the size of our compute clusters and scale the work that they process, many issues arise in how to schedule the diversity of work that runs on Google systems.

We have distilled these challenges into the following research topics that we feel are interesting to the academic community and important to Google:

• Workload characterizations: How can we characterize Google workloads in a way that readily generates synthetic work that is representative of production workloads so that we can run stand alone benchmarks?
• Predictive models of workload characteristics: What is normal and what is abnormal workload? Are there "signals" that can indicate problems in a time-frame that is possible for automated and/or manual responses?
• New algorithms for machine assignment: How can we assign tasks to machines so that we make best use of machine resources, avoid excess resource contention on machines, and manage power efficiently?
• Scalable management of cell work: How should we design the future cell management system to efficiently visualize work in cells, to aid in problem determination, and to provide automation of management tasks?

To aid researchers in addressing these questions in a realistic manner, we will provide data from Google production systems. The initial focus of these data will be workload characterization. Details of the data can be found here. The data are structured as follows:

• Time (int) - time in seconds since the start of data collection
• JobID (int) - Unique identifier of the job to which this task belongs
• TaskID (int) - Unique identifier of the executing task
• Job Type (0, 1, 2, 3) - class of job (a categorization of work)
• Normalized Task Cores (float) - normalized value of the average number of cores used by the task
• Normalized Task Memory (float) - normalized value of the average memory consumed by the task

We solicit your feedback in terms of: (a) the quality and content of the data we are providing; (b) technical approaches and/or results related to the topics above; and (c) other research topics that you feel Google should be addressing in the area of Cloud Computing (along with details of the data required to address these topics).

Read More