Julia meets HTML 5

Posted by Daniel Wolf, Software Engineer

Today, we launched Julia Map on Google Labs, a fractal renderer in HTML 5. Julia sets are fractals that were studied by the French mathematician Gaston Julia in the early 1920s. Fifty years later, Benoît Mandelbrot studied the set z2 − c and popularized it by generating the first computer visualisation. Generating these images requires heavy computation resources. Modern browsers have optimized JavaScript execution up to the point where it is now possible to render in a browser fractals like Julia sets almost instantly.

Julia Map uses the Google Maps API to zoom and pan into the fractals. The images are computed with HTML 5 canvas. Each image generally requires millions of floating point operations. Web workers spread the heavy calculations on all cores of the machine.

We hope you will enjoy exploring the different Julia sets, and share the URLs of the most artistic images you discovered. See what others have posted on Twitter under hashtag #juliamap. Click on the images below to dive in to infinity!

Read More

Google at NIPS 2010

Posted by Slav Petrov, Doug Aberdeen, and Lisa McCracken, Google Research

The machine learning community met in Vancouver in December for the 24th Neural Information Processing Systems Conference (NIPS). As always, the single-track program of the main conference featured a number of outstanding talks, followed by interesting late night poster sessions. A record number of workshops covered a wide variety of topics, while allocating sufficient time for skiing in Whistler - after all, many of the most interesting research conversations happen while riding the lift in-between ski runs. This year’s conference also featured a symposium dedicated to Sam Roweis, providing a retrospective on Sam’s life and work. Sam, a fellow Googler and professor at NYU, was at the heart of the NIPS community and is terribly missed.

As always, Google was involved in various ways with NIPS. Here at Google, we take a data-driven approach when solving problems. Therefore, Machine Learning is in one way or another at the core of most of the things that we do. It is therefore unsurprising that many Googlers helped shape the program of the conference or were in the audience. This year, three Googlers served as area chairs and even more were reviewers. Googlers also co-authored the following papers:

• Label Embedding Trees for Large Multi-Class Tasks by Samy Bengio and Jason Weston
• Learning Bounds for Importance Weighting by Corinna Cortes, Yishay Mansour, and Mehryar Mohri
• Online Learning in the Manifold of Low-Rank Matrices by Uri Shalit, Daphna Weinshall, and Gal Chechik
• Deterministic Single–Pass Algorithm for LDA by Issei Sato, Kenichi Kurihara, and Hiroshi Nakagawa
• Distributed Dual Averaging In Networks by John Duchi, Alekh Agarwal, and Martin Wainwright

Additionally, Googlers co-organized three well attended workshops:

• Coarse–to–Fine Learning and Inference by Ben Taskar, David Weiss, Benjamin Sapp, and Slav Petrov
• Low–rank Methods for Large–scale Machine Learning by Arthur Gretton, Michael Mahoney, Mehryar Mohri, and Ameet Talwalkar
• Learning on Cores, Clusters, and Clouds by John Duchi, Ofer Dekel, John Langford, Lawrence Cayton, and Alekh Agarwal

Finally, Yoram Singer gave a great talk on Learning Structural Sparsity at the Sam Roweis symposium and Googlers presented the following talks during the workshops:

• Online Learning in the Manifold of Low–Rank Matrices by Uri Shalit, Daphna Weinshall, and Gal Chechik
• Distributed MAP Inference for Undirected Graphical Models by Sameer Singh, Amar Subramanya, Fernando Pereira, and Andrew McCallum
• MapReduce/Bigtable for Distributed Optimization by Keith Hall, Scott Gilpin and Gideon Mann
• Self-Pruning Prediction Trees by Sally Goldman
• Web Scale Image Annotation: Learning to Rank with Joint Word-Image Embeddings by Jason Weston, Samy Bengio, and Nicolas Usunier
• Coarse–to–fine Decoding for Parsing and Machine Translation by Slav Petrov

Overall, it was a very successful conference and it was good to be back in Vancouver one last time. This coming year NIPS 2011 will be in Granada, Spain. Hasta luego!

Read More

More Google Contributions to the Broader Scientific Community

Posted by Corinna Cortes and Alfred Spector, Google Research

Googlers actively engage with the scientific community by publishing technical papers, contributing open-source packages, working on standards, introducing new APIs and tools, giving talks and presentations, participating in ongoing technical debates, and much more. Our publications offer technical and algorithmic advances, demonstrate things we learn as we develop novel products and services, and shed light on some of the technical challenges we face at Google.

In an effort to highlight some of our work, we periodically select a number of publications to be featured on this site. We first posted a set of papers on this blog in mid-2010 and subsequently discussed them in more detail in the following blog postings. This blog posting highlights a few new noteworthy papers authored or co-authored by Googlers from the later half of 2010. In the coming weeks we will be offering a more in-depth look at these publications, but here are some summaries:

Algorithms and Electronic Commerce

Robust Mechanisms for Risk-Averse Sellers
ACM Conference on Electronic Commerce (EC)

Mukund Sundararajan and Qiqi Yan, Stanford University

In his seminal Nobel prize-winning work, Roger Myerson identified the revenue-maximizing auction for a risk-neutral auctioneer. In contrast, this work identifies good mechanisms for risk-averse auctioneers. These mechanisms trade a little revenue for better certainty, in the best possible way. We expect this work will help guide reserve-price selection in auctions where auctioneers/sellers want better control over their revenue.

Monitoring Algorithms for Negative Feedback Systems
World Wide Web Conference (WWW)

Mark Sandler and S. Muthukrishnan

In negative feedback systems, users report abusive content at a site to its owner for consideration or removal, but the users might not be honest. For the site owners, this represents a trade-off between vetting such user reports by humans vs. accepting them without vetting. This paper presents a mathematical framework for design and analysis of such systems and presents algorithms with provably good trade-offs against malicious users.

HCI

Children's Roles Using Keyword Search Interfaces in the Home
Computer Human Interactions (CHI)

Allison Druin, University of Maryland, Elizabeth Foss, University of Maryland, Hilary Hutchinson, Evan Golub, University of Maryland, and Leshell Hatley, University of Maryland

In this paper, we describe seven search roles children display as information seekers using Internet keyword interfaces, based on a home study of 83 children ages 7, 9, and 11.

Machine Learning

Large Scale Image Annotation: Learning to Rank with Joint Word-Image Embeddings

European Conference on Machine Learning (ECML) Best Paper

Jason Weston, Samy Bengio, and Nicolas Usunier, Universite Paris 6 - LIP6

In this paper, we introduce a generic framework to find a joint representation of images and their labels, which can then be used for various tasks, including image ranking and image annotation. We simultaneously propose an efficient training algorithm that scales to tens of millions of images and hundreds of thousands of labels, while focusing training on making good predictions at the top of the ranked list. The models are both fast at prediction time and have low memory usage making it possible to house such systems on a laptop or mobile device.

Overlapping Experiment Infrastructure: More, Better

Faster Experimentation, Knowledge Discovery and Datamining (KDD)

Diane Tang, Ashish Agarwal, Deirdre O'Brien, and Mike Meyer

Google's data driven culture requires running a large number of live traffic experiments. This paper describes Google's overlapping experimental infrastructure where a single event (e.g. a web search) can be assigned to multiple simultaneous large experiments. The infrastructure and supporting tools provide a framework that enables running experiments from design to decision making and launch, and can be generalized to many other web applications.

NLP

Products of Random Latent Variable Grammars

North American Chapter of the Association for Computational Linguistics (NAACL)

Slav Petrov

It is well known that the Expectation Maximization algorithm can converge to widely varying local maxima. This paper shows that this can be advantageous when learning latent variable grammars for syntactic parsing. By combining multiple state-of-the-art individual grammars into an unweighted product model, parsing accuracy can be improved from 90.2% to 91.8% for English, and from 80.3% to 84.5% for German.

Software Engineering

Contention Aware Execution: Online Contention Detection and Response

International Symposium on Code Generation and Optimization (CGO)

Jason Mars, University of Virginia, Neil Vachharajani, Robert Hundt, Mary Lou Soffa, University of Virginia

This paper makes a big step forward in addressing an important and pressing problem in the field of Computer Science today. This work presents a lightweight runtime solution that significantly improves the utilization of datacenter servers by up to 58% on average. This work also received the CGO 2010 Best Presentation Award.

Speech

Say What? Why users choose to speak their web queries

Interspeech

Maryam Kamvar and Doug Beeferman

Say What? Have you been speaking your search queries into your mobile device rather than typing them? Spoken search is available on Android, iPhone and Blackberry devices and we see an increasing numbers of searches coming in by voice on these phones. In our paper “Say What: Why users choose to speak their web queries” we investigate, on an aggregate level, what factors are most predictive of spoken queries. Understanding context in which a speech-driven search is used (or conversely not used) can be used to improve recognition engines and spoken interface design. So, save keystrokes and say your query!

Query Language Modeling for Voice Search

IEEE Workshop on Spoken Language Technology

Ciprian Chelba, Johan Schalkwyk, Thorsten Brants, Vida Ha, Boulos Harb, Will Neveitt, Carolina Parada*, Johns Hopkins University, and Peng Xu

The paper describes language modeling for google.com query data, and its application to speech recognition for Google Voice Search.
Our empirical findings include:

• 10% relative gains in WER from large scale modeling,
• a less known yet potentially quite detrimental interaction between Kneser-Ney smoothing and entropy pruning (approx. 10% relative increase in WER)
• evidence that hints at non-stationarity of the query stream, and
• surprisingly strong dependence across three English locales---USA, Britain and Australia.

Structured Data

Dremel: Interactive Analysis of Web-Scale Datasets

Very Large Data Bases (VLDB)

Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, and Theo Vassilakis, Google Inc.

Dremel is a scalable, interactive ad-hoc query system. By combining multi-level execution trees and columnar data layout, it is capable of running aggregation queries over trillion-row tables in seconds. The system is widely used at Google and serves as the foundational technology behind BigQuery, a product launched in limited preview mode.

Systems and Infrastructure

Large-scale Incremental Processing Using Distributed Transactions and Notifications

USENIX Symposium on Operating Systems Design and Implementation (OSDI)

Daniel Peng and Frank Dabek

In the past, Google accumulated a whole day’s worth of changes to the web and ran a series of enormous MapReduces to apply this batch of changes to our index of the web. This system led to a delay of several days between crawling a document and presenting it to users in search results. To meet our goal of reducing the indexing delay to minutes, we needed to update the index as each individual document was crawled, rather than in daily batches. No existing infrastructure supported this kind of incremental transformation at web scale, so we built Percolator: a framework for transforming a large repository using small ACID transactions.

Availability in Globally Distributed Storage Systems

USENIX Symposium on Operating Systems Design and Implementation (OSDI)

Daniel Ford, Francois Labelle, Florentina Popovici, Murray Stokely, Van-Anh Truong*, Columbia University, Luiz Barroso, Carrie Grimes, and Sean Quinlan

In our paper, we characterize the availability of cloud storage systems, based on extensive monitoring of Google's main storage infrastructure, and the sources of failure which affect availability. We also present statistical models for reasoning about the impact of design choices such as data placement, recovery speed, and replication strategies, including replication across multiple data centers.

Vision

Improved Consistent Sampling, Weighted Minhash and L1 Sketching

IEEE International Conference on Data Mining (ICDM)

Sergey Ioffe

With the huge amounts of very high-dimensional data, such as images and videos, we frequently need to "sketch" the data -- that is, represent it in a much more compact form, while still allowing us to accurately determine how different any two images or videos are. In this paper, we describe a sketching method for L1, one of the most common distance measures. It works by first hashing the data with a new algorithm, and then compressing each hash to a small number of bits, which is learned from data. This method is fast and allows the distances to be estimated accurately, while reducing the storage requirements by a factor of 100.

*) work carried out while at Google

Read More

Supporting computer science education with CS4HS

Posted by Terry Ednacot, Education Program Manager

Recent statistics have shown a decline in the number of U.S. students taking computer science AP classes, which also leads to a decline in students declaring computer science as their majors—a concerning trend in the U.S. as we try to remain competitive in the global economy. With programs like Computer Science for High School (CS4HS), we hope to increase the number of CS majors —and therefore the number of people entering into careers in CS—by promoting computer science curriculum at the high school level.

For the fourth consecutive year, we’re funding CS4HS to invest in the next generation of computer scientists and engineers. CS4HS is a workshop for high school and middle school computer science teachers that introduces new and emerging concepts in computing and provides tips, tools and guidance on how to teach them. The ultimate goals are to “train the trainer,” develop a thriving community of high school CS teachers and spread the word about the awe and beauty of computing.

In 2011 we’re expanding the program considerably and hope to double the number of schools we funded in 2010. If you’re a university, community college, or technical School in the U.S., Canada, Europe, Middle East or Africa and are interested in hosting a workshop at your institution, please visit www.cs4hs.com to submit an application for grant funding. Applications will be accepted between January 18, 2011 and February 18, 2011.

In addition to submitting your application, on the CS4HS website you’ll find info on how to organize a workshop, as well as websites and agendas from last year’s participants to give you an idea of how the workshops were structured in the past. There’s also a collection of CS4HS curriculum modules that previous participating schools have shared for future organizers to use in their own program.

Previous organizers have told us that teachers have left their workshops excited about the new materials they learned and the innovative ideas they’ve discussed with other teachers. We’re hopeful that they’ll pass on to their students not only the skills that they learned but also that passion.

Read More

More researchers dive into the digital humanities

Posted by Jon Orwant, Engineering Manager for Google Books

When we started Google Book Search back in 2004, we were driven by the desire to make books searchable and discoverable online. But as that corpus grew -- we’ve now scanned approximately 10% of all books published in the modern era -- we began to realize how useful it would be for scholarly work. Humanities researchers have started to ask and answer questions about history, society, linguistics, and culture via quantitative techniques that complement traditional qualitative methods.

We’ve been gratified at the positive response to our initial forays into the digital humanities, from our Digital Humanities Research Awards earlier this year, to the Google Books Ngram Viewer and datasets made public just last week. Today we’re pleased to announce a second set of awards focusing on European universities and research centers.

We’ve given awards to 12 projects led by 15 researchers at 13 institutions:

• Humboldt-Universität zu Berlin. Annotated Corpora in Studying and Teaching Variation and Change in Academic German, Anke Lüdeling
• LIMSI/CNRS, Université Paris Sud. Building Multi-Parallel Corpora of Classical Fiction, François Yvon
• Radboud Universiteit. Extracting Factoids from Dutch Texts, Suzan Verberne
• Slovenian Academy of Sciences and Arts, Jožef Stefan Institute. Language models for historical Slovenian, Matija Ogrin and Tomaž Erjavec
• Université d'Avignon, Université de Provence. Robust and Language Independent Machine Learning Approaches for Automatic Annotation of Bibliographical References in DH Books, Articles and Blogs, Patrice Bellot and Marin Dacos
• Université François Rabelais-Tours. Full-text retrieval and indexation for Early Modern French, Marie-Luce Demonet
• Université François Rabelais-Tours. Using Pattern Redundancy for Text Transcription, Jean-Yves Ramel and Jean-Charles Billaut
• Universität Frankfurt. Towards a “Corpus Caucasicum”: Digitizing Pre-Soviet Cyrillic-Based Publications on the Languages of the Caucasus, Jost Gippert
• Universität Hamburg. CLÉA: Literature Éxploration and Annotation Environment for Google Books Corpora, Jan-Christoph Meister
• Universität zu Köln. Integrating Charter Research in Old and New Media, Manfred Thaller
• Universität zu Köln. Validating Metadata-Patterns for Google Books' Ancient Places and Sites, Reinhard Foertsch
• University of Zagreb. A Profile of Croatian neo-Latin, Neven Jovanović

Projects like these, blending empirical data and traditional scholarship, are springing up around the world. We’re eager to see what results they yield and what broader impact their success will have on the humanities.

(Cross-posted from the European Public Policy Blog)

Read More

Robot hackathon connects with Android, browsers and the cloud

Posted by Ryan Hickman and Mamie Rheingold, 20% Robotics Task Force

With a beer fridge stocked and music blasting, engineers from across Google—and the world—spent the month of October soldering and hacking in their 20% time to connect hobbyist and educational robots with Android phones. Just two months later we’re psyched to announce three ways you can play with your iRobot Create(R), LEGO(R) MINDSTORMS(R) or VEX Pro(R) through the cloud:

• App Inventor for Android
• Cellbots for Android
• Python library for the Scripting Layer 4 Android

For the month of October, we invited any Googler who wanted to contribute to connect robots to Google’s services in the cloud to pool their 20% time and participate in as much of the process as they could, from design to hard-core coding.

Thanks to our hardware partners (iRobot, LEGO Group, and VEX Robotics), we never suffered a shortage of supplies. Designers flew in from London, and prototypes were passed between engineers in Tel-Aviv, Hyderabad, Zurich, Munich and California. In Mountain View, we gathered around every Thursday night, rigging up a projector against the wall to share our week’s worth of demos while chowing on pizza. And here is what we produced (so far!):

• App Inventor: Low level Bluetooth support for connecting with many serial-enabled robots, and of course tight integration with LEGO MINDSTORMS.
• Cellbots for Android: Brand new Java app from Cellbots.com, which is open source and available for free in the Android Market.
• Python library: Modularized version of the popular Cellbots project, which is all open source code.

We hope these applications provide some fun and inspire you to build upon this lightweight connectivity between robots, Android, the cloud and your browser.

Read More

Find out what’s in a word, or five, with the Google Books Ngram Viewer

Posted by Jon Orwant, Engineering Manager, Google Books

[Cross-posted from the Google Books Blog]

Scholars interested in topics such as philosophy, religion, politics, art and language have employed qualitative approaches such as literary and critical analysis with great success. As more of the world’s literature becomes available online, it’s increasingly possible to apply quantitative methods to complement that research. So today Will Brockman and I are happy to announce a new visualization tool called the Google Books Ngram Viewer, available on Google Labs. We’re also making the datasets backing the Ngram Viewer, produced by Matthew Gray and intern Yuan K. Shen, freely downloadable so that scholars will be able to create replicable experiments in the style of traditional scientific discovery.

Comparing instances of [flute], [guitar], [drum] and [trumpet] (

blue, red, yellow and green respectively)

in English literature from 1750 to 2008

Since 2004, Google has digitized more than 15 million books worldwide. The datasets we’re making available today to further humanities research are based on a subset of that corpus, weighing in at 500 billion words from 5.2 million books in Chinese, English, French, German, Russian, and Spanish. The datasets contain phrases of up to five words with counts of how often they occurred in each year.

These datasets were the basis of a research project led by Harvard University’s Jean-Baptiste Michel and Erez Lieberman Aiden published today in Science and coauthored by several Googlers. Their work provides several examples of how quantitative methods can provide insights into topics as diverse as the spread of innovations, the effects of youth and profession on fame, and trends in censorship.

The Ngram Viewer lets you graph and compare phrases from these datasets over time, showing how their usage has waxed and waned over the years. One of the advantages of having data online is that it lowers the barrier to serendipity: you can stumble across something in these 500 billion words and be the first person ever to make that discovery. Below I’ve listed a few interesting queries to pique your interest:

World War I, Great War
child care, nursery school, kindergarten
fax, phone, email
look before you leap, he who hesitates is lost
virus, bacteria
tofu, hot dog
burnt, burned
flute, guitar, trumpet, drum
Paris, London, New York, Boston, Rome
laptop, mainframe, microcomputer, minicomputer
fry, bake, grill, roast
George Washington, Thomas Jefferson, Abraham Lincoln
supercalifragilisticexpialidocious

We know nothing can replace the balance of art and science that is the qualitative cornerstone of research in the humanities. But we hope the Google Books Ngram Viewer will spark some new hypotheses ripe for in-depth investigation, and invite casual exploration at the same time. We’ve started working with some researchers already via our Digital Humanities Research Awards, and look forward to additional collaboration with like-minded researchers in the future.

Read More