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

Announcing our Q4 Research Awards

Posted by Maggie Johnson, Director of Education & University Relations and Jeff Walz, Head of University Relations

We do a significant amount of in-house research at Google, but we also maintain strong ties with academic institutions globally, pursuing innovative research in core areas relevant to our mission. One way in which we support academic institutions is the Google Research Awards program, aimed at identifying and supporting world-class, full-time faculty pursuing research in areas of mutual interest.

Our University Relations team and core area committees just completed the latest round of research awards, and we're excited to announce them today. We had a record number of submissions, resulting in 76 awards across 17 different areas. Over $4 million was awarded — the most we have ever funded in a round.

The areas that received the highest level of funding for this round were systems and infrastructure, machine learning, multimedia, human computer interaction, and security. These five areas represent important areas of collaboration with university researchers. We're also excited to be developing more connections internationally. In this round, over 20 percent of the funding was awarded to universities outside the U.S.

Some exciting examples from this round of awards:

Ondrej Chum, Czech Technical University, Large Scale Visual Link Discovery. This project addresses automatic discovery of visual links between image parts in huge image collections. Visual links associate parts of images that share even a relatively small, but distinctive, visual information.

Bernd Gartner, ETH Zurich, Linear Time Kernel Methods and Matrix Factorizations. This project aims to derive faster approximation algorithms for kernel methods as well as matrix approximation problems and leverage these two promising paradigms for better performance on large scale data.

Dawson Engler, Stanford University, High Coverage, Deep Checking of Linux Device Drivers using KLEE + Under-constrained Execution Symbolic execution. This project extends the recently built KLEE, a tool that automatically generates test cases that execute most statements in real programs, so that it allows automatic, deep checking of Linux device drivers.

Jeffrey G. Gray, University of Alabama at Birmingham, Improving the Education and Career Opportunities of the Physically Disabled through Speech-Aware Development Environments. This project will investigate the science and engineering of tool construction to allow those with restricted limb mobility to access integrated development environments (IDEs), which will support programming by voice.

Xiaohui (Helen) Gu, North Carolina State University, Predictive Elastic Load Management for Cloud Computing Infrastructures. This project proposes to use fine-grained resource signatures with signal processing techniques to improve resource utilization by reducing the number of physical hosts required to run all applications.

Jason Hong and John Zimmerman, Carnegie Mellon University, Context-Aware Mobile Mash-ups. This project seeks to build tools for non-programmers to create location and context-aware mashups of data for mobile devices that can present time- and place-approriate information.

S V N Vishwanathan, Purdue University, Training Binary Classifiers using the Quantum Adiabatic Algorithm. The goal of this project is to harness the power of quantum algorithms in machine learning. The advantage of the new quantum methods will materialize even more once new adiabatic quantum processors become available.

Emmett Witchel and Vitaly Shmatikov, University of Texas at Austin, Private and Secure MapReduce. This project proposes to build a practical system for large-scale distributed computation that provides rigorous privacy and security guarantees to the individual data owners whose information has been used in the computation.

Click here to see a full list of this round’s award recipients. More information on our research award program can be found on our website.

Read More

Teaching a Computer to Understand Japanese

Posted by Mike Schuster, Google Research and Kaisuke Nakajima, Google Japan

On December 7th, we launched our new Japanese voice search system (音声検索), which has been available for various flavors of English since last year and for Mandarin Chinese for the past two months. The initial Japanese system works on the Android platform and also through the Google Mobile App on the iPhone as announced in a Japanese blog and a general explanation on how to get started. For developers who want to make use of the speech recognition backend for their own Android applications there is a public API (recognizer intent API) described here.

Although speech recognition has had a long history in Japan, creating a system that can handle a problem as difficult as voice search is still a considerable challenge. Today, most speech recognition systems are large statistical systems that must learn two models from sets of examples, an acoustic model and a language model. The acoustic model represents (statistically) the fundamental sounds of the language, and the language model statistically represents the words, phrases, and sentences of the language. The acoustic model for Japanese voice search was trained using a large amount of recorded Japanese speech, with the associated transcriptions of the words spoken. The language model for Japanese voice search was trained on Japanese search queries.

While speech recognition systems are surprisingly similar across different languages, there are some problems that are more specific to Japanese. Some of the challenges we faced while developing Japanese voice search included:

• Spaces in Japanese text
  As we looked at some popular search queries in Japan we saw that Japanese often doesn't have spaces but sometimes it does. For example, if a user searches for Ramen noodles near Tokyo station they will often type: "東京駅 ラーメン" with a space in between Tokyo station and Ramen -- therefore, we would like to display it in this way as well. Getting the spaces right is difficult and we continue working to improve it.
• Japanese word boundaries
  Word boundaries in Japanese are often not clear and subject to interpretation as most of the time there are not spaces between words. This also makes the definition of the vocabulary (the words that can be recognized theoretically) extremely large. We deal with this problem by finding likely word boundaries using a statistical system which also helps us limit the vocabulary.
• Japanese text is written in 4 different writing systems
  Japanese text as written today uses Kanji, Hiragana, Katakana & Romaji, often mixed in the same sentence and sometimes in the same word, depending on the definition of a word. Try these example queries to see some interesting cases: "価格.com", "マーボー豆腐", "東京都渋谷区桜丘町26-1". We try to display the output in a way that is most user-friendly, which often means to display it as you would write it down.
• Japanese has lots of basic characters and many have several pronunciations depending on context
  To be able to recognize a word you need to know its pronunciation. Western languages in general use only ASCII or a slightly extended set of characters which is relatively small (less than 100 total in most cases). For Japanese the number of basic characters is the union of all basic characters from the four writing systems mentioned above, which is several thousands in total. Finding the correct pronunciations for all words in the very large voice search vocabulary is difficult and is often done using a combination of human effort and automatic statistical systems. This is even more difficult in the Japanese case as the number of basic characters is higher and there are a vast number of exceptions, for example consider the case of: "一人" (hitori) versus "一人前" (ichininmae). Although the phrases look very similar they have completely different pronunciations.
• Encoding issues
  Japanese characters can be written in many encoding systems including UTF-8, Shift_JIS, EUC-JP and others. While at Google we try to use exclusively UTF-8 there are still interesting edge cases to deal with. For example some characters exist in different forms in the same encoding system. Compare for example "カナ"　and "ｶﾅ" -- they both say "kana" and mean the exact same thing, the first in full-width and the second in half-width. There are numerous similar cases like this in Japanese that make normalization of the text data more difficult.
• 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 it work for all these different conditions we trained our system on data from many different sources to capture as many conditions as possible.

The challenges listed above are just a small portion of what we dealt with while building the Japanese voice search system. Over time, we are committed to improve the system as much as and as quickly as possible to make speech, in addition to the keyboard, a user-friendly input modality on mobile devices. We will push a first set of improved models this week.

Read More