Google Research Blog

Machine Learning Meeting

2008-05-20T17:32:00.000-07:00

Machine Learning is a branch of Artificial Intelligence in which, naturally enough, the aim is to get computers to learn: things like improving performance over time, and recognizing general tendencies among a number of specific cases. We have many ways to exploit Machine Learning programs, and a lot of data to give them. Machine Learning helps us to estimate what content users like most, what content is even legitimate, and how to match ads to content. It also plays key roles in products such as Google Translate and 1-800-GOOG-411.

Last week, Google held a Machine Learning Summit in New York, gathering together engineers from around the world, including participants from Beijing, Zurich, Boston, Haifa, and Mountain View. The program included invited talks by CJ Lin and Peng Xu, and many shorter presentations by Googlers on topics including broadly applicable Machine Learning software, especially challenging applications, and some mathematical analysis.

Can You Publish at Google?

2008-05-06T15:10:00.000-07:00

Posted by Rich Gossweiler

As part of the interview process at Google we try to describe what it is like to do research here. A common question I get is "How hard is it to publish at Google?" I want to dispel the myth that it is hard. It is easy to publish, easy to put code into open source, easy to give talks, etc. But it is also easy for great research to become great engineering, and that is an incredible lure. Great barriers of despair exist between research and development at many companies; researchers can find it hard to have impact beyond demos, papers, or patents.

Here at Google it is not uncommon for researchers to work on products (and is modus operandi for me); you can come up with something interesting, experiment to convince yourself and others that it is worthwhile, and then work as part of the team to build it and help create world-changing products. But are you willing to do that? That decision is the hard part, not publishing a paper.

I think from a Google standpoint, we need to make sure these barriers don't form, that making products, experimenting and having a venue for trying bold new approaches continues to be part of the culture .

VisualRank

2008-05-01T13:30:00.000-07:00

Posted by Shumeet Baluja and Yushi Jing

At WWW-2008, in Beijing, China, we presented our paper "PageRank for Product Image Search". In this paper, we presented a system that used visual cues, instead of solely text information, to determine the rank of images. The idea was simple: find common visual themes in a set of images, and then find a small set of images that best represented those themes. The resulting algorithm wound up being PageRank, but on an entirely inferred graph of image similarities. Since the release of the paper, we've noticed lots of coverage in the press and have received quite a few questions. We thought we could answer a few of them here.

"Why did we choose to use products for our test case?" First and foremost, product queries are popular in actual usage; addressing them is important. Second, users have strong expectations of what results we should return for these queries; therefore, this category provides an important set of examples that we need to address especially carefully. Third, on a pragmatic note, they lend themselves well to the type of "image features" that we selected in this study. Since the publication of the paper, we've also extended our results to other query types, including travel-related queries. One of the nice features of the approach is that (we hope) it will be easy to extend to new domains; as research in measuring image or object similarity continues, the advances can easily be incorporated into the similarity calculation to compute the underlying graph; the computations on the graph do not change.

"Where are we going from here?" Besides broadening the sets of queries (and sets of features) for which we can use this approach, there are three directions we're exploring. First, estimating similarity measures for all of the images on the web is computationally expensive; approximations or alternative computations are needed. Second, we hope to evaluate our approach with respect to the large number of recently proposed alternative clustering methods. Third, many variations of PageRank can be used in quite interesting ways for image search. For example, we can use some of these previously published methods to reintroduce, in a meaningful manner, the textual information that the VisualRank algorithm removed. In the end, we have an approach that has an easy integration with both text and visual clues. Stay tuned for more on that in the coming months.

And now to answer the most commonly asked question, "Is it live?" Not yet. Currently, it is research in progress (click here to help speed up the process). In the meantime, though, if you'd like another sneak peek of our research on large graphs, this time in the context of YouTube datamining, just follow the link.

Finally, we want to extend our deepest thanks to the people who helped on this project, especially the image-search team; without their help, this research would not have been possible.

Research in the Cloud: Providing Cutting Edge Computational Resources to Scientists

2008-04-23T14:13:00.000-07:00

Posted by Christophe Bisciglia, Senior Software Engineer, and Alfred Spector, Vice President of Research

The emergence of extremely large datasets, well beyond the capacity of almost any single computer, has challenged traditional and contemporary methods of analysis in the research world. While a simple spreadsheet or modest database remains sufficient for some research, problems in the domain of "computational science," which explores mathematical models via computational simulation, require systems that provide huge amounts of data storage and computer processing (current research areas in computational science include climate modeling, gene sequencing, protein mapping, materials science and many more). As an added hurdle, this level of computational infrastructure is often not affordable to research teams, who usually work with significant budgetary restrictions.

Fortunately, as the Internet technology industry expands its global infrastructure, accessing world class distributed computational and storage resources can be as simple as visiting a website. Building on its Academic Cloud Computing Initiative (ACCI) announced last October, Google and IBM, with the National Science Foundation, announced in February the CluE initiative to address this particular need. After coordinating the technical details with Google and IBM, the NSF posted the official solicitation of proposals last week.

Our primary goal in participating in the CluE initiative is to encourage the understanding, further refinement and --importantly-- targeted application of the latest distributed computing technology and methods across many academic disciplines. Engaging educators and researchers with the new potential of distributed computing for processing and analyzing extremely large datasets is an invaluable investment for any technology company to make, and Google in particular is pleased to make a contribution to the academic community that has enabled so many recent advances in the industry.

We're looking forward to an eclectic collection of proposals from the NSF's solicitation. We believe many will leverage the power of distributed computing to produce a diverse range of knowledge that will provide long term benefit to both the research community and the public at large. We also hope that Google's contribution to this low cost, open source approach to distributed computing will allow many more in the academic community to take advantage of this pervasive technological shift.

More details, including information on how to apply for access to these resources, is available on the NSF site.

Deploying Goog411

2008-03-28T15:34:00.000-07:00

Posted by Francoise Beaufays

A couple of years ago, a few of us got together and decided to build Goog411. It would be a free phone service that users could call to connect to any business in the US, or simply to browse through a list of businesses such as "bookstores" in a given city. Everything would be fully automated, with no operator in the background, just a speech recognition system to converse with the user, and Google Maps to execute the business search.

We knew that speech recognition is not a solved problem; there would be users for whom the system wouldn't work well, and queries that would be harder to recognize than others. But we got big assets through hosting the service: we could iterate as often as we wanted on any component of the system, we'd have access to all the data, and we could measure whatever seemed relevant to callers. So we built Goog411, started taking some traffic, defining metrics, and iterated many, many times.

We learned a few interesting things in the process (see our ICASSP paper). For example, we discovered that databases with lists of business names are almost useless to train a language model for how users answer the question "What business name or category?"; aggregated web query logs from Google Maps yield far better performance. And we found the speech data we collect through our own service is almost as useful to model new queries as the web data, even though we have orders of magnitude less of it. After all, you may type "real estate" in Google Maps to glance at a few properties, but would you ask for it over the phone while driving your car?

Today Goog411 has grown from an experiment into a product, and we're working on expanding the service to Canada. As calls flow through the system, our focus is still on making the best use of the increasing data, defining metrics that best correlate to the user's experience, and taking advantage of the computer resources and data sources available within Google.

Maybe our most rewarding experience so far has been to see our traffic grow, and to see repeat callers succeed more and more often with the system. Have you tried it already? Just call 1-800-GOOG-411, and don't hesitate to send us feedback!

This year's scalability conference

2008-02-11T11:53:00.000-08:00

Posted by Andrew Schwerin, Software Engineer

Managing huge repositories of data and large clusters of machines is no easy task -- and building systems that use those clusters to usefully process that data is even harder. Last year, we held a conference on scalable systems so a bunch of people who work on these challenges could get together and share ideas. Well, it was so much fun that we've decided to do it again.

This year, the conference is taking place in Seattle on Saturday, June 14. (Registration is free.) If you'd like to talk about a topic on scalable or large-scale systems that is near and dear to your heart, we'd love to hear from you. Potential topics include:

Development, deployment and production:

Systems, environments and languages for building, deploying and debugging complex datacenter-scale apps, or for allowing teams of collaborating engineers to work together on such apps more effectively

Mobile applications:

Unique challenges of scaling services for mobile devices
Location-aware scaling techniques
Experiences designing scalable apps involving mobile devices

Of course, you've probably got more ideas. Send a 500-word abstract of your 30-minute presentation to scalabilityconf@google.com no later than Friday, April 11, and we'll post registration details in the next couple of months.

Google Education Summit

2007-10-18T17:31:00.000-07:00

Posted by Jeff Walz and Kevin McCurley

The world's research and educational infrastructures are tightly intertwined. Research universities enable students to participate in research activities, and research contributes to the vitality of the educational experience. At Google, we also recognize the importance of education to our research and engineering activities. In addition to our own in-house activities, we maintain strong ties to academic institutions through visiting faculty programs and summer internships. In recognition of the importance of education to Google's mission, we also recently organized a Google Education Summit. Mehran Sahami has more to say about this in a recent blog post.

OpenHTMM Released

2007-09-23T14:01:00.000-07:00

Posted by Ashok C. Popat, Research Scientist

Statistical methods of text analysis have become increasingly sophisticated over the years. A good example is automated topic analysis using latent models, two variants of which are Probabilistic latent semantic analysis and Latent Dirichlet Allocation.

Earlier this year, Amit Gruber, a Ph.D. student at the Hebrew University of Jerusalem, presented a technique for analyzing the topical content of text at the Eleventh International Conference on Artificial Intelligence and Statistics in Puerto Rico.

Gruber's approach, dubbed Hidden Topic Markov Models (HTMM), was developed in collaboration with Michal Rosen-Zvi and Yair Weiss. It differs notably from others in that, rather than treat each document as a single "bag of words," it imposes a temporal Markov structure on the document. In this way, it is able to account for shifting topics within a document, and in so doing, provides a topic segmentation within the document, and also seems to effectively distinguish among multiple senses that the same word may have in different contexts within the same document.

Amit is currently a doing graduate internship at Google. As part of his project, he has developed a fresh implementation of his method in C++. We are pleased to release it as the OpenHTMM package to the research community under the Apache 2 license, in the hopes that it will be of general interest and facilitate further research in this area.

The Sky is Open

2007-09-19T16:16:00.000-07:00

Posted by Jeremy Brewer

We've gotten an incredible amount of positive feedback about Sky in Google Earth, which lets Google Earth users explore the sky above them with hundreds of millions of stars and galaxies taken from astronomy imagery.

From the start though, we have wanted to open the sky up to everyone. As a first step, we've been hard at work developing tools to let astronomers add their own imagery, and we think we've come up with something that does the job nicely. We're pleased to announce the availability of wcs2kml, an open source project for importing astronomical imagery into Sky.

Modern telescopes output imagery in the FITS binary format that contains a set of headers known as a World Coordinate System (that's the "wcs" part) specifying the location of the image on the sky. Wcs2kml handles the task of transforming this imagery into the projection system used by Google Earth (the "kml" part) so that it can be viewed directly in Sky. Wcs2kml also includes tools to simplify uploading this data to a web server and sharing it with friends.

We were astounded at the imagery and novel applications people created when we opened the Google Earth API to our users. Now, by opening Sky in Google Earth to the astronomy community, we hope to open a floodgate of new imagery for Sky!

Introducing Sky in Google Earth

2007-08-21T19:46:00.000-07:00

Posted by Andy Connolly and Ryan Scranton

At Google we are always interested in creating new ways to share ideas and information and applying these techniques to different research fields. Astronomy provides a great opportunity with an abundance of images and information that are accessible to researchers and indeed, anyone with an interest in the stars. With the release of the Google Earth 4.2 client the new Sky feature acts as a virtual telescope that provides a view of some of the most detailed images ever taken of the night sky. By clicking on the Sky button, you can explore the universe, seamlessly zooming from the familiar views of the constellations and stars, to the deepest images ever taken of galaxies and more. From planets moving across the sky to supernovae exploding in distant galaxies, Sky provides a view of a dynamic universe that we hope you will enjoy.

In addition to allowing educators, amateurs or anyone with an interest in space to visually explore the sky, one of the most exciting aspects of Sky is its capability for research and discovery in astronomy. With the latest features in KML you can connect astronomical image and catalog databases directly to the visualization capabilities of Sky ( e.g. searching the Sloan Digital Sky Survey database for the highest redshift quasars or correlating the the infrared and optical sky to detect the presence of dust within our Galaxy). From releasing new data about the latest discovery of planets around nearby stars to identifying the host galaxy of a gamma ray burst the possibilities are endless. Examples of how to build research applications such as a view of the microwave background emission from the remnant of the Big Bang can be found in the Google Earth Gallery.

It has been a lot of fun creating Google's first astronomical observatory. Go check it out; explore the sky from the comfort of your home; If you find something interesting let us know on the Sky section of the Google Earth Community, or author your own KML applications to to share your discoveries and data with everyone else. You can also find more Sky resources on our website.

Drink from the firehose with University Research Programs

2007-07-26T11:27:00.000-07:00

Posted by Michael Lancaster and Josh Estelle, Software Engineers

Whenever we talk to university researchers, we hear a consistent message: they wish they had Google infrastructure. In pursuit of our company mission, we have built an elaborate set of systems for collecting, organizing, and analyzing information about the web. Operating and maintaining such an infrastructure is a high barrier to entry for many researchers. We recognize this and want to share some of the fruits of our labor with the research community. Today, in conjunction with the Google Faculty Summit we're making two services available under the new University Research Programs, namely access to web search, and machine translation.

University Research Program for Google Search

Google is focused on the success of the web, which is essentially an organism in and of itself with extremely complex contents and an ever-evolving structure. The primary goal of the University Research Program for Google Search is to promote research that creates a greater understanding of the web. We want to make it easy for researchers to analyze millions of queries in a reasonably short amount of time. We feel that such research can benefit everyone. As such, we've added a proviso that all research produced through this program must be published in a freely accessible manner.

University Research Program for Google Translate

The web is a global information medium with content from many cultures and languages. In order to break the language barrier, many researchers are hard at work building high quality, automatic, machine translation systems. We've been successful with our own statistical machine translation system, and are now happy to provide researchers greater access to it. The University Research Program for Google Translate provides researchers access to translations, including detailed word alignment information and lists of the n-best translations with detailed scoring information. We hope this program will be a terrific resource to help further the state of the art in automatic machine translation.

The web holds a wealth of untapped research potential and we look forward to seeing great new publications enabled by these new programs. Go ahead - surprise us!

By the way, since many researchers lead a double life as educators, we want to let you know about a site that recently launched: Google Code for Educators, designed to make it easy for CS faculty to integrate cutting-edge computer science topics into their courses. Check it out.

New Conference on Web Search and Data Mining

2007-06-18T15:10:00.000-07:00

Posted by Ziv Bar-Yossef and Kevin McCurley, Research Team

The pace of innovation on the World Wide Web continues unabated more than fifteen years after the first servers went live. The web was initially used by only a small community of scientists, but there are now over a billion people on the planet who use the web in their lives. The World Wide Web grows and changes as a young organism might, reflecting the social forces of the users and information producers. Each year seems to bring a radical new change, including the movement of commerce to the web, the availability of realtime news on the web, mobile users being able to access the web from anywhere, new forms of media such as video, and the emergence of blogs changing politics and publishing.

This rapid pace of innovation and scale presents many interesting research questions. At Google our goal is to organize information in ways that are useful to users, and we regularly find ourselves solving problems that seemed like ridiculous thought experiments just a few years ago. We therefore welcome the arrival of a new conference on Web Search and Data Mining, prosaically named with the acronym WSDM (pronounced as wisdom). WSDM is intended to be complementary to the World Wide Web Conference tracks in search and data mining. The soaring volume of submissions to these two tracks over the past few years justifies the foundation of a new top-tier conference on web search and mining. WSDM is a joint effort of researchers from the three large search engines (Google, Yahoo, MSN) as well as top-notch scientists from the Academia (such as Jon Kleinberg from Cornell, Rajeev Motwani from Stanford, and Monika Henzinger from Google and EPFL). The first WSDM conference will take place at Stanford University (the place where both Google and Yahoo! were conceived by their founders). The conference will be held in February of 2008, and the deadline for submissions is July 30, 2007. For further information see the WSDM web site. If you have good papers on search or data mining in the pipeline, please consider sending them to WSDM.

We look forward to seeing you there!

Videos of talks

2007-06-18T14:38:00.000-07:00

Posted by Kevin McCurley, Research Team

We've recently launched a Google Research web site that we'll be updating to provide information about research activities at Google. Among other things, one thing you'll find there is the ability to search and view videos of talks at Google.

One of the best features of working at Google is the rich variety of talks that we can attend, both technical and general interest. Most of these are videotaped for later viewing. This has multiple benefits:

In case of a scheduling conflict, Google employees may view talks at a later time (yes, some of us do have other things to do in the day).

Talks are available for viewing by Google employees at other sites. This provides us with a much more cohesive intellectual culture than most global companies.

When appropriate, speakers may opt to have their talks available on the World Wide Web. This provides a benefit to both viewers and speakers, since it allows speakers to reach a much broader audience, and it allows viewers to hear interesting talks without the need to be
physically present.

The World Wide Web started out as a means for scientists to communicate among themselves. In the early days it provided a less formal and timely means of distributing information than archival refereed publications, and it's now routine for a scientist to have a home page from which they distribute their writings and thoughts. Moreover, it's also now commonplace to find a large fraction of current scientific literature through the web, both refereed and unrefereed. In fact, the situation has evolved to the point where scientists often consult the web for publications before going to a library.

Archival publications are but one means of communication that has typically been used by scientists. Another mode of communication that has a long history of use is the presentation of talks at meetings and during visits to other institutions. Oral presentations have historically been less formal, and allow the speaker to be more speculative and interactive.

In the last few years, several technological developments have made it possible to distribute high quality video of talks on the web in addition to written publications. This distribution of videos from talks holds the promise of changing the way that scientists think about communication. Imagine what lessons would be available to us if we had the ability to view lectures by Kepler, Einstein, Turing, Shannon, or von Neumann! Imagine also what it would be like to be able to watch and listen to selected talks from conferences that are across the world, without having to suffer the burden of traveling to the remote location. Such media are unlikely to ever completely supplant the richness of communication that arises from personal interaction in physical proximity, but it will probably still change scientific communication as much as email and the web have already.

Seattle conference on scalability

2007-02-16T11:15:00.000-08:00

Posted by Amanda Camp, Software Engineer

We care a lot about scalability at Google. An algorithm that works only on a small scale doesn't cut it when we are talking global access, millions of people, millions of search queries. We think big and love to talk about big ideas, so we're planning our first ever conference on scalable systems. It will take place on June 23 at our Seattle office. Our goal: to create a collegial atmosphere for participants to brainstorm different ways to build the robust systems that can handle, literally, a world of information.

If you have a great new idea for handling a growing system or an innovative approach to scalability, we want to hear from you. Send a short note about who you are and a description of your 45-minute talk in 500 words or less to scalabilityconf@google.com by Friday, April 20.

With your help, we can create an exciting event that brings together great people and ideas. (And by the way, we'll bring the food.) If you'd like to attend but not speak, we'll post registration details later.

Hear, here. A Sample of Audio Processing at Google.

2007-02-14T09:54:00.000-08:00

Posted by Shumeet Baluja, Michele Covell, Pedro Moreno & Eugene Weinstein

Text isn't the only source of information on the web! We've been working on a variety of projects related to audio and visual recognition. One of the fundamental constraints that we have in designing systems at Google is the huge amounts of data that we need to process rapdily. A few of the research papers that have come out of this work are shown here.

In the first pair of papers, to be presented at the 2007 International Conference on Acoustics, Speech and Signal Processing (Waveprint Overview, Waveprint-for-Known-Audio), we show how computer vision processing techniques, combined with large-scale data stream processing, can create an efficient system for recognizing audio that has been degraded by various means such as cell phone playback, lossy compression, echoes, time-dilation (as found on the radio), competing noise, etc.

It is also fun and surprising to see how often in research the same problem can be approached from a completely different perspective. In the third paper to be presented at ICASSP-2007 (Music Identification with WFST) we explore how acoustic modeling techniques commonly used in speech recognition, and finite state transducers used to represent and search large graphs, can be used in the problem of music identification. Our approach learns a common alphabet of music sounds (which we call music-phones) and represents large song collections as a big graph where efficient search is possible.

Perhaps one of the most interesting aspects of audio recognition goes beyond the matching of degraded signals, and instead attempts to capture meaningful notions of similarity. In our paper presented at the International Conference on Artificial Intelligence (Music Similarity), we describe a system that learns relevant similarities in music signals, while maintaining efficiency by using these learned models to create customized hashing functions.

We're extending these pieces of work in a variety of ways, not only in the learning algorithms used, but also the application areas. If you're interested in joining google research and working on these projects, be sure to drop us a line.

Google Research Picks for Videos of the Year

2006-12-11T14:58:00.000-08:00

Posted by Peter Norvig

Everyone else is giving you year-end top ten lists of their favorite movies, so we thought we'd give you ours, but we're skipping Cars and The Da Vinci Code and giving you autonomous cars and open source code. Our top twenty (we couldn't stop at ten):

Winning the DARPA Grand Challenge: Sebastian Thrun stars in the heartwarming drama of a little car that could.
The Graphing Calculator Story: A thriller starring Ron Avitzur as the engineer who snuck into the Apple campus to write code.
Should Google Go Nuclear?: Robert Bussard (former Asst. Director of the AEC) talks about inertial electrostatic fusion.
A New Way to Look at Networking: Van Jacobson as the old pro discovering that the old problems have not gone away.
Python 3000: Guido van Rossum always looks on the bright side of life in this epic look at the future of Python.
How to Survive a Robot Uprising: Daniel Wilson stars in this sci-fi horror story.
The New "Bill of Rights of Information Society": Raj Reddy talks about how to get the right information to the right people at the right time.
Practical Common Lisp: In this foreign film, Peter Seibel introduces the audience to a new language. Subtitles in parentheses.
Debugging Backwards in Time: Starring Bil Lewis in this sequel to Back to the Future.
Building Large Systems at Google: Narayanan Shivakumar takes us behind the scenes to see how Google builds large distributed systems. Like Charlie and the Chocolate Factory but without the Oompa-Loompas.
The Science and Art of User Experience at Google: Jen Fitzpatrick continues the behind-the-scenes look.
Universally Accessible Demands Accessibility for All of Humanity: McArthur "Genius Award" Fellow Jim Fruchterman talks about accessibility for the blind and others.
DNA and the Brain: Nobel Laureate James Watson explains how the key to understanding the brain is in our genes.
Steve Wozniak: This one-man show is playing to boffo reviews.
Jane Goodall: The celebrated primatologist discusses her mission to empower individuals to improve the environment.
Computers Versus Common Sense: Doug Lenat reprises his role as the teacher trying to get computers to understand.
The Google Story: David Vise talks about his book on Google.
The Search: John Battelle talks about his book on Google.
The Archimedes Palimpsest: Like Da Vinci Code, only true.
The Paradox of Choice - Why More is Less: With Barry Schwartz. Hmm, maybe I should have made this a top three list?

CSCW 2006: Collaborative editing 20 years later

2006-11-28T09:37:00.000-08:00

Posted by Lilly Irani & Jens Riegelsberger, User Experience team

9am Mountain View, California. 6pm Zurich, Switzerland. The two of us sit separated by thousands miles, telephones tucked under our ears, talking about this blog post and typing words and edits into Google Docs. As we talk about the title, we start typing into the same paragraph -- and Lilly gets a warning: "You've edited a paragraph that Jens has been editing!" Lilly stops typing so she doesn't lose her thoughts and coordinates with Jens over the phone. Then we realize "We just talked about this problem at the conference we're writing about!"

Two weeks ago four Googlers ventured north to attend ACM CSCW in Banff, Alberta, Canada. CSCW is ACM's conference on Computer Supported Cooperative Work and brings together computer scientists, social scientists, and designers interested in how people live their lives -- at work, at play, and in between -- with and around technology, with a focus on undestanding the design of technological systems. Topics like issues and implementation of collaborative editing are staples at CSCW.

As this year was the conference's 20th anniversary, we had a chance to hear from many of the founders of CSCW: Irene Greif, Jonathan Grudin, Tom Malone, Judy Olson, Lucy Suchman, among others. Not surprisingly, the mood was introspective, with many speakers tracing the impact of the community over time and looking critically and constructively at the future paths the research community might take. Many sessions focused on less traditional areas of research, such as how Facebook figures into college students' school transitions and how tagging vocabularies evolve and are shaped by technology in a movie community. Jens also gave a talk on his pre-Google research on how photos and voice profiles affect people's choice of gaming partners. And he participated in a workshop exploring how people trust -- and learn to trust -- in online environments.

Apart from actively taking part in the debates and Q&As, we also demo-ed Google's tools for getting things done, collaboratively or solo: Google Docs & Spreadsheets and Google Notebook. These were met with much interest, as these publicly available Google tools build on insights gained in the CSCW field over the last 20 years.

If you're interested in these issues, you'd be a great addition to our team. Learn about available positions in user experience research and design.

And the Awards Go To ...

2006-09-22T09:25:00.000-07:00

Posted by Proud Googlers

We're usually a modest bunch, but we we couldn't help but let you know about some honors and awards bestowed on Googlers recently:

Ramakrishnan Srikant is the winner of the 2006 ACM SIGKDD Innovation Award for his work on pruning techniques for the discovery of association rules, and for developing new data mining approaches that respect the privacy of people in the data base.
Henry Rowley and Shumeet Baluja, along with CMU professor Takeo Kanade, received the Longuet-Higgins prize for "a contribution which has stood the test of time," namely their 1996 paper Neural Network based face detection. The award was given at the 2006 Computer Vision and Pattern Recognition (CVPR) Conference.
Team Smartass, consisting of Christopher Hendrie, Derek Kisman, Ambrose Feinstein and Daniel Wright won first place in the ICFP (International Conference on Functional Programming) programming contest, using a combination of C++, Haskell and 2D. Third place went to Can't Spell Awesome without ASM, a team consisting of Google engineer Jon Dethridge, former Google interns Ralph Furmaniak and Tomasz Czajka, and Reid Barton of Harvard. They got the judges at the functional programming conference to admit "Assembler is not too shabby."
Peter Norvig was named a Berkeley Distinguished Alumni in Computer Science, and gave the keynote commencement address. We'd also like to congratulate Prabhakar Raghavan, Head of Yahoo Research, who was a co-recipient of this award.
Simon Quellen Field's book Return of Gonzo Gizmos was a selection of the Scientific American Book Club.
Google summer intern Rion Snow (along with Stanford professors Dan Jurafsky and Andrew Ng) got the best paper award at the 2006 ACL/COLING (computational linguistics) conference for his paper titled Semantic taxonomy induction from heterogenous evidence.
Google summer intern Lev Reyzin won the outstanding student paper award at ICML (International Conference on Machine Learning) for work with Rob Schapire of Princeton on How Boosting the Margin Can Also Boost Classifier Complexity.
As we mentioned earlier, Michael Fink, Michele Covell and Shumeet Baluja won a best paper award for Social- and Interactive-Television Applications Based on Real-Time Ambient-Audio Identification.
Update 13 Oct 2006: Paul Rademacher has been named one of the top innovators under 35 by MIT's Technology Review. He was cited
for his mashup of Google Maps and Craig's List housing data at housingmaps.com.
Update 31 Oct 2006: We forgot Alon Halevy, who won the VLDB 10 Year Best Paper Award for Querying Heterogeneous Information Sources Using Source Descriptions with Anand Rajaraman and Joann J. Ordille.

All Our N-gram are Belong to You

2006-08-03T11:26:00.000-07:00

Posted by Alex Franz and Thorsten Brants, Google Machine Translation Team

Here at Google Research we have been using word n-gram models for a variety of R&D projects, such as statistical machine translation, speech recognition, spelling correction, entity detection, information extraction, and others. While such models have usually been estimated from training corpora containing at most a few billion words, we have been harnessing the vast power of Google's datacenters and distributed processing infrastructure to process larger and larger training corpora. We found that there's no data like more data, and scaled up the size of our data by one order of magnitude, and then another, and then one more - resulting in a training corpus of one trillion words from public Web pages.

We believe that the entire research community can benefit from access to such massive amounts of data. It will advance the state of the art, it will focus research in the promising direction of large-scale, data-driven approaches, and it will allow all research groups, no matter how large or small their computing resources, to play together. That's why we decided to share this enormous dataset with everyone. We processed 1,024,908,267,229 words of running text and are publishing the counts for all 1,176,470,663 five-word sequences that appear at least 40 times. There are 13,588,391 unique words, after discarding words that appear less than 200 times.

Watch for an announcement at the Linguistics Data Consortium (LDC), who will be distributing it soon, and then order your set of 6 DVDs. And let us hear from you - we're excited to hear what you will do with the data, and we're always interested in feedback about this dataset, or other potential datasets that might be useful for the research community.

Update (22 Sept. 2006): The LDC now has the data available in their catalog. The counts are as follows:


File sizes: approx. 24 GB compressed (gzip'ed) text files

Number of tokens:    1,024,908,267,229
Number of sentences:    95,119,665,584
Number of unigrams:         13,588,391
Number of bigrams:         314,843,401
Number of trigrams:        977,069,902
Number of fourgrams:     1,313,818,354
Number of fivegrams:     1,176,470,663

The following is an example of the 3-gram data contained this corpus:


ceramics collectables collectibles 55
ceramics collectables fine 130
ceramics collected by 52
ceramics collectible pottery 50
ceramics collectibles cooking 45
ceramics collection , 144
ceramics collection . 247
ceramics collection </S> 120
ceramics collection and 43
ceramics collection at 52
ceramics collection is 68
ceramics collection of 76
ceramics collection | 59
ceramics collections , 66
ceramics collections . 60
ceramics combined with 46
ceramics come from 69
ceramics comes from 660
ceramics community , 109
ceramics community . 212
ceramics community for 61
ceramics companies . 53
ceramics companies consultants 173
ceramics company ! 4432
ceramics company , 133
ceramics company . 92
ceramics company </S> 41
ceramics company facing 145
ceramics company in 181
ceramics company started 137
ceramics company that 87
ceramics component ( 76
ceramics composed of 85
ceramics composites ferrites 56
ceramics composition as 41
ceramics computer graphics 51
ceramics computer imaging 52
ceramics consist of 92

The following is an example of the 4-gram data in this corpus:


serve as the incoming 92
serve as the incubator 99
serve as the independent 794
serve as the index 223
serve as the indication 72
serve as the indicator 120
serve as the indicators 45
serve as the indispensable 111
serve as the indispensible 40
serve as the individual 234
serve as the industrial 52
serve as the industry 607
serve as the info 42
serve as the informal 102
serve as the information 838
serve as the informational 41
serve as the infrastructure 500
serve as the initial 5331
serve as the initiating 125
serve as the initiation 63
serve as the initiator 81
serve as the injector 56
serve as the inlet 41
serve as the inner 87
serve as the input 1323
serve as the inputs 189
serve as the insertion 49
serve as the insourced 67
serve as the inspection 43
serve as the inspector 66
serve as the inspiration 1390
serve as the installation 136
serve as the institute 187
serve as the institution 279
serve as the institutional 461
serve as the instructional 173
serve as the instructor 286
serve as the instructors 161
serve as the instrument 614
serve as the instruments 193
serve as the insurance 52
serve as the insurer 82
serve as the intake 70
serve as the integral 68

Call for attendees - Conference on Test Automation

2006-07-12T15:28:00.000-07:00

Posted by Allen Hutchison, Engineering Manager

As we noted earlier, we're hosting our first-ever Conference on Test Automation in London in September.

We've heard from many interested parties, and now have 13 excellent presentations lined up. Now we are soliciting people who want to attend. Because we expect lots of interest and space is limited, we're asking everyone who's interested to write a short note (400 words or less) on why you want to be there. There's an easy form for requesting a spot, and we hope to hear from you. The deadline for writing in is July 28th - and you'll hear back by August 4.

Interactive TV: Conference and Best Paper

2006-06-06T10:13:00.000-07:00

Posted by Michele Covell & Shumeet Baluja, Research Scientists

Euro ITV (the interactive television conference) took place in Athens last week. The presentations included a diverse collection of user studies, new application areas, and exploratory business models. One of the main themes was the integration of multiple information sources. For example, during a time-out in a live sporting event, some viewers may enjoy reviewing highlight footage, while others may prefer to view a parallel program to view player profiles and statistics before being automatically returned to the soccer match once the event was back underway.

Other papers explored the idea of selecting and recommending videos. When many videos are available, such as through IPTV or digital cable, we see a heavy-tailed distribution of content accesses (much like that on the internet). There are a small number of popular channels but the combined viewings from thousands of "niche" channels outweigh the popular channels. As on the web, the problem that arises from this situation is one of discovery. A TV guide type resource is not practical; methods like collaborative-filtering can help. Nonetheless, new ideas and interfaces are needed.

We also presented our work at the conference. Our paper [pdf] (which received the best paper award :) focused on using broadcast viewing to automatically present relevant information on a web browser. We showed how to sample the ambient sound emitted from a TV and automatically determine what is being watched from a small signature of the sound -- all with complete privacy and minuscule effort. The system could keep up with users while they channel surf, presenting them with a real-time forum about a live political debate one minute and an ad-hoc chat room for a sporting event in the next. And, all of this would be done without users ever having to type or to even know the name of the program or channel being viewed. Taking this further, we could collect snippets from the web describing the actors appearing in a movie or present maps of locales within the movie as it takes place (no matter if users are watching it as a live broadcast or as a recoded broadcast).

Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

2006-06-02T08:34:00.000-07:00

Posted by Joshua Bloch, Software Engineer

I remember vividly Jon Bentley's first Algorithms lecture at CMU, where he asked all of us incoming Ph.D. students to write a binary search, and then dissected one of our implementations in front of the class. Of course it was broken, as were most of our implementations. This made a real impression on me, as did the treatment of this material in his wonderful Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000). The key lesson was to carefully consider the invariants in your programs.

Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.

So what's the bug? Here's a standard binary search, in Java. (It's one that I wrote for the java.util.Arrays):

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

The bug is in this line:

 6:             int mid =(low + high) / 2;

In Programming Pearls Bentley says that the analogous line "sets m to the average of l and u, truncated down to the nearest integer." On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2³¹ - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException.

This bug can manifest itself for arrays whose length (in elements) is 2³⁰ or greater (roughly a billion elements). This was inconceivable back in the '80s, when Programming Pearls was written, but it is common these days at Google and other places. In Programming Pearls, Bentley says "While the first binary search was published in 1946, the first binary search that works correctly for all values of n did not appear until 1962." The truth is, very few correct versions have ever been published, at least in mainstream programming languages.

So what's the best way to fix the bug? Here's one way:

 6:             int mid = low + ((high - low) / 2);

Probably faster, and arguably as clear is:

 6:             int mid = (low + high) >>> 1;

In C and C++ (where you don't have the >>> operator), you can do this:

 6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;

And now we know the binary search is bug-free, right? Well, we strongly suspect so, but we don't know. It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. With concurrent programs, it's even worse: You have to test for all internal states, which is, for all practical purposes, impossible.

The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.

We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

Update 17 Feb 2008: Thanks to Antoine Trux, Principal Member of Engineering Staff at Nokia Research Center Finland for pointing out that the original proposed fix for C and C++ (Line 6), was not guaranteed to work by the relevant C99 standard (INTERNATIONAL STANDARD - ISO/IEC - 9899 - Second edition - 1999-12-01, 3.4.3.3), which says that if you add two signed quantities and get an overflow, the result is undefined. The older C Standard, C89/90, and the C++ Standard are both identical to C99 in this respect. Now that we've made this change, we know that the program is correct;)

Resources

Programming Pearls - Highly recommended. Get a copy today!
The Sun bug report describing this bug in the JDK
A 2003 paper by Salvatore Ruggieri discussing a related problem - The problem is a bit more general but perhaps less interesting: the average of two numbers of arbitrary sign. The paper does not discuss performance, and its solution is not fast enough for use in the inner loop of a mergesort.

Statistical machine translation live

2006-04-28T15:40:00.000-07:00

Posted by Franz Och, Research Scientist

Because we want to provide everyone with access to all the world's information, including information written in every language, one of the exciting projects at Google Research is machine translation. Most state-of-the-art commercial machine translation systems in use today have been developed using a rules-based approach and require a lot of work by linguists to define vocabularies and grammars.

Several research systems, including ours, take a different approach: we feed the computer with billions of words of text, both monolingual text in the target language, and aligned text consisting of examples of human translations between the languages. We then apply statistical learning techniques to build a translation model. We have achieved very good results in research evaluations.

Now you can see the results for yourself. We recently launched an online version of our system for Arabic-English and English-Arabic. Try it out! Arabic is a very challenging language to translate to and from: it requires long-distance reordering of words and has a very rich morphology. Our system works better for some types of text (e.g. news) than for others (e.g. novels) -- and you probably should not try to translate poetry ... but do stay tuned for more exciting developments.

Update: We've just opened a discussion forum for all topics related to machine translation.

Our conference on automated testing

2006-04-27T09:45:00.000-07:00

Posted by Allen Hutchison, Engineering Manager

Automated testing is one of my passions: it has hard problems to be solved, and they get harder every day. Over the past few years, I've had the opportunity to work on several automation projects, and now I'm getting a chance to combine my passion for automation with my love for the city of London.

I'm happy to announce that Google will be hosting a Conference on Test Automation in our London office on September 7 and 8, 2006. Our goal is to create a collegial atmosphere where participants can discuss challenges facing people on the cutting edge of test automation, and evaluate solutions for meeting those challenges.

Call for Presentations
We're looking for speakers with exciting ideas and new approaches to test automation. If you have a subject you'd like to talk about, please send me email at londontestconf@google.com that includes a description of your 60- or 90-minute talk in 500 words or less. Deadline for submissions is June 1.

We're planning to have 10 people give presentations at the conference followed by adequate time for discussion. If you'd like to attend as a non-speaker, watch this space. Once we've got a slate of speakers, we'll post it along with details on attending.

See you at CHI

2006-04-23T08:01:00.000-07:00

Posted by Rick Boardman, User Experience Researcher

The raison d’etre for our user experience research team is driven by Google's keen interest in focusing on the user. So we help many product teams provide the best possible experience to everyone around the world, primarily by inviting thousands of people to take part in usability tests in our labs, and by analyzing our logs to identify problems which need fixing. From this we get the data we help our engineers make Google products as easy as possible to use for the millions of people out there who think computers are far too complicated. People like my Mum, Dad, girlfriend, Gran — and pretty much everyone I know!

We’re one of several Google teams that publish research at academic and industry conferences, and this week a number of us will be attending the CHI (Computer-Human Interaction) conference in Montreal, the world's premiere gathering for CHI researchers and practitioners. Googlers from several teams will take part in eight sessions, each focusing on different aspects of human-computer interaction. (The full program is here – it’s a PDF file.)

A Large Scale Study of Wireless Search Behavior: Google Mobile Search – In a session on Search and Navigation: Mobiles and Audio, we'll present the first large-scale study of search behavior for mobile users, highlighting some shortcomings of wireless search interfaces.

Scaling the card sort method to over 500 items: Restructuring the Google AdWords Help Center – Here we adapt the popular card-sorting research methodology to large information sets where the traditional approach is impractical and discuss how we've applied this technique.

No IM Please, We’re Testing – During the Usability Evaluations: Challenges and Solutions session we’ll discuss the use of instant messaging tools like Google Talk in usability tests, and the benefits of this technique for enabling live collaboration between test moderators and observers.

Add a Dash of Interface: Taking Mash-Ups to the Next Level – Here we contribute to the discussion of how extendable interfaces like Google Maps are enabling exciting new online innovation through the combining of data sources.

Why Do Tagging Systems Work? – This panel will address the design challenges of scaling tagging systems to meet their recent surge in popularity. Gmail is an example of email tagging that offers more flexibility than traditional hierarchical systems.

Design Communication: How Do You Get Your Point Across? – A key challenge for UI designers is communicating solutions and challenges within product teams. This panel focuses on effective ways to do that.

“It’s About the Information, Stupid!” Why We Need a Separate Field of Human Information Interaction – This interdisciplinary panel will discuss arguments for and against a distinct field focusing on information rather than computing technology. One for the theoreticians? (-;

Incorporating Eyetracking into User Studies at Google – In this Eyetracking in Practice workshop, we’ll talk about some of the challenges we’ve encountered in studies of eyetracking in our labs.

If you work in, or study, the area of human-computer interaction, the user experience team is hiring. Right now we’re looking for user experience researchers (including those with specialized quantitative skills), UI designers, and more.