Google Research Blog

From Words to Concepts and Back: Dictionaries for Linking Text, Entities and Ideas

2012-05-18T09:30:00.000-07:00

Posted by Valentin Spitkovsky and Peter Norvig, Research Team

Yet in each word some concept there must be...

— from Goethe's Faust (Part I, Scene III)

Human language is both rich and ambiguous. When we hear or read words, we resolve meanings to mental representations, for example recognizing and linking names to the intended persons, locations or organizations. Bridging words and meaning — from turning search queries into relevant results to suggesting targeted keywords for advertisers — is also Google's core competency, and important for many other tasks in information retrieval and natural language processing. We are happy to release a resource, spanning 7,560,141 concepts and 175,100,788 unique text strings, that we hope will help everyone working in these areas.

How do we represent concepts? Our approach piggybacks on the unique titles of entries from an encyclopedia, which are mostly proper and common noun phrases. We consider each individual Wikipedia article as representing a concept (an entity or an idea), identified by its URL. Text strings that refer to concepts were collected using the publicly available hypertext of anchors (the text you click on in a web link) that point to each Wikipedia page, thus drawing on the vast link structure of the web. For every English article we harvested the strings associated with its incoming hyperlinks from the rest of Wikipedia, the greater web, and also anchors of parallel, non-English Wikipedia pages. Our dictionaries are cross-lingual, and any concept deemed too fine can be broadened to a desired level of generality using Wikipedia's groupings of articles into hierarchical categories.

The data set contains triples, each consisting of (i) text, a short, raw natural language string; (ii) url, a related concept, represented by an English Wikipedia article's canonical location; and (iii) count, an integer indicating the number of times text has been observed connected with the concept's url. Our database thus includes weights that measure degrees of association. For example, the top two entries for football indicate that it is an ambiguous term, which is almost twice as likely to refer to what we in the US call soccer:

text=football	url	count
1.	Association football	44,984
2.	American football	23,373
⋮

An inverted index can be used to perform reverse look-ups, identifying salient terms for each concept. Some of the highest-scoring strings — including synonyms and translations — for both sports, are listed below:

concept:

“soccer”

football and Football

Soccer and soccer

Association football

fútbol and Fútbol

footballer

Futbol and futbol

Fußball

futebol

futbolista

サッカー

축구

footballeur

Fußballspieler

sepak bola

足球

فوتبال

футболист

כדורגל

piłkarz

voetbalclub

ฟุตบอล

bóng đá

voetbal

Foutbaal

futebolista

لعبة كرة القدم

fotbal

concept:

“football”

American football

football and Football

fútbol americano

football américain

アメリカンフットボール

American football rules

futebol americano

فوتبال آمریکایی

美式足球

football americano

Amerikan futbolu

Le Football Américain

football field

อเมริกันฟุตบอล

פוטבול

كرة القدم الأمريكية

Futbol amerykański

미식축구

futbolu amerykańskiego

football team

американского футбола

Amerikai futball

sepak bola Amerika

football player

američki fudbal

反則

كرة القدم الأميركية

Associated counts can easily be turned into percentages. The following table illustrates the concept-to-words dictionary direction — which may be useful for paraphrasing, summarization and topic modeling — for the idea of soft drink, restricted to English (and normalized for punctuation, pluralization and capitalization differences):

url=Soft_drink	text		%
1.	soft drink	(and soft-drinks)	28.6
2.	soda	(and sodas)	5.5
3.	soda pop		0.9
4.	fizzy drinks		0.6
5.	carbonated beverages	(and beverage)	0.3
6.	non-alcoholic		0.2
7.	soft		0.1
8.	pop		0.1
9.	carbonated soft drink	(and drinks)	0.1
10.	aerated water		0.1
11.	non-alcoholic drinks	(and drink)	0.1
12.	soft drink controversy		0.0
13.	citrus-flavored soda		0.0
14.	carbonated		0.0
15.	soft drink topics		0.0
⋮

The words-to-concepts dictionary direction can disambiguate senses and link entities, which are often highly ambiguous, since people, places and organizations can (nearly) all be named after each other. The next table shows the top concepts meant by the string Stanford, which refers to all three (and other) types:

text=Stanford	url	%	type
1.	Stanford University	50.3	ORGANIZATION
2.	Stanford (disambiguation)	7.7	a disambiguation page
3.	Stanford, California	7.5	LOCATION
4.	Stanford Cardinal football	5.7	ORGANIZATION
5.	Stanford Cardinal	4.1	multiple athletic programs
6.	Stanford Cardinal men's basketball	2.0	ORGANIZATION
7.	Stanford prison experiment	2.0	a famous psychology experiment
8.	Stanford, Kentucky	1.7	LOCATION
9.	Stanford, Norfolk	1.0	LOCATION
10.	Bank of the West Classic	1.0	a recurring sporting event
11.	Stanford, Illinois	0.9	LOCATION
12.	Leland Stanford	0.9	PERSON
13.	Charles Villiers Stanford	0.8	PERSON
14.	Stanford, New York	0.8	LOCATION
15.	Stanford, Bedfordshire	0.8	LOCATION
⋮

The database that we are providing was designed for recall. It is large and noisy, incorporating 297,073,139 distinct string-concept pairs, aggregated over 3,152,091,432 individual links, many of them referencing non-existent articles. For technical details, see our paper (to be presented at LREC 2012) and the README file accompanying the data.

We hope that this release will fuel numerous creative applications that haven't been previously thought of!

Produced by Angel X. Chang and Valentin I. Spitkovsky; parts of this work are descended from an earlier collaboration between University of Basque Country's Ixa Group's Eneko Agirre and Stanford's NLP Group, including Eric Yeh, presently of SRI International, and our Ph.D. advisors, Christopher D. Manning and Daniel Jurafsky.

Smart Pricing may increase average publisher revenue

2012-05-15T10:00:00.000-07:00

Posted by Guy Calvert, AdSense Sales

Online publisher networks, such as Google’s AdSense or the Yahoo! Publisher Network, enable advertisers to simultaneously contest click auctions for thousands - even millions - of web publisher ad slots, all with a single max CPC bid. Recognizing that different publishers deliver disparate performance for advertisers, some networks feature automated systems to help advertisers bid more efficiently with that single bid - effectively discounting click prices on publishers according to the relative value of clicks on each publisher’s ad slots. Google, for example, applies Smart Pricing (SP) for this purpose to appropriately discount advertiser bids on the Google Display Network.

It is widely accepted that a well-executed system like SP enhances advertiser value. Whether SP also improves network revenue - and hence, via publisher revenue sharing agreements - average publisher revenue, remains a matter of some dispute. While it is clear that higher performing publishers will do better than lower performing publishers, opinion is divided as to whether publishers are on average better or worse off with SP.

Skepticism is understandable - the system by its very nature entails discounting advertiser bids. But if advertisers indeed get more value from a smart-priced network then we would expect them to bid higher because of that feature. The key question is whether the network revenue produced by their SP-discounted higher bids is more, less, or the same as the revenue produced by their undiscounted regular bids. In other words, does Smart Pricing grow the revenue pie?

In this paper, I develop a simple and tractable model of an auction-based publisher click network, replete with an idealized version of SP and profit-maximizing advertisers, and use it to derive insights into the revenue effects of systems like SP. While there is no claim here with regard to the revenue impact of SP-like systems on any actual publisher network, it is hoped that the arguments in the paper will help guide intuition and shape realistic expectations for publishers. And the main implication of this analysis is good news for networks and publishers alike - under reasonable conditions Smart Pricing, and its non-Google analogs, can significantly grow the pie.

Is beautiful usable? What is the influence of beauty and usability on reactions to a product?

2012-05-14T13:15:00.000-07:00

Posted by Javier Bargas-Avila, Senior User Experience Researcher at YouTube UX Research

Did you ever come across a product that looked beautiful but was awful to use? Or stumbled over something that was not nice to look at but did exactly what you wanted?

Product usability and aesthetics are coexistent, but they are not identical. To understand how usability and aesthetics influence reactions to a product, we conducted an experimental lab study with 80 participants. We created four versions of an online clothing shop varying in beauty (high vs. low) and usability (high vs. low). Participants had to find a number of items in one of those shops and buy them. To understand how the factors of beauty and usability influence final users happiness, we measured how they much they liked the shop before and after interaction.

The results showed that the beauty of the interface did not affect how users perceived the usability of the shops: Participants (or Users) were capable of distinguishing if a product was usable or not, no matter how nice it looked. However, the experiment showed that the usability of the shops influenced how users rated the products' beauty. Participants using shops with bad usability rated the shops as less beautiful after using the shops. We showed that poor usability lead to frustration, which put the users in a bad mood and made them rate the product as less beautiful than before interacting with the shop.

Successful products should be beautiful and usable. Our data provide insight into how these factors work together.

Google, the World Wide Web and WWW conference: years of progress, prosperity and innovation

2012-05-07T10:00:00.000-07:00

Posted by Prabhakar Raghavan, Vice President of Engineering

More than forty members of Google’s technical staff gathered in Lyon, France in April to participate in the global dialogue around the state of the web at the World Wide Web conference (WWW) 2012. A decade ago, Larry Page and Sergey Brin applied their research to an information retrieval problem and their work—presented at WWW in 1998—led to the invention of today’s most popular search engine.

As I've watched the WWW conference series evolve over the years, a couple of larger trends struck me in this year's edition. First, there seems to be more of a Mobile Web presence in the technical program, relative to recent years. The refereed program included several interesting Mobile papers, including the Best Student Paper Awardee from Stanford University researchers: Who Killed My Battery: Analyzing Mobile Browser Energy Consumption, Narendran Thiagarajan, Gaurav Aggarwal, Angela Nicoara, Dan Boneh, Jatinder Singh.

Second, one gets the sense that the WWW community is moving from the classic "bag of words" view of web pages, to an entity-centric view. There were a number of papers on identifying and using entities in Web pages. While I'm loathe to view this as a vindication of "the Semantic Web" (mainly because this has become an overloaded phrase that people elect to interpret as suits them), the technical capability to get at entities is clearly here. The question is -- what is the killer application? Finally, it’s nice to see that recommendation systems are becoming a major topic of focus at WWW. This paper was a personal favorite: Build Your Own Music Recommender by Modeling Internet Radio Streams, Natalie Aizenberg, Yehuda Koren, Oren Somekh.

In keeping with tradition, Google was a major supporter, sponsoring the conference, the Best Paper Award (Counting beyond a Yottabyte, or how SPARQL 1.1 Property Paths will prevent adoption of the standard, Marcelo Arenas, Sebastián Conca and Jorge Pérez) and four PhD student travel grants. We chatted with hundreds of attendees who hung out with us at the Google booth to chat and see demos about the latest Google product and research developments (see full schedule of booth talks).

Googlers were also active member of the vibrant research community at WWW:

David Assouline delivered the keynote for the Demo Track -- to a standing-room-only crowd -- on the Google Art Project, which uses a combination of various Google technologies and expert information provided by our museum partners to create a unique online art experience. Googler Alon Halevy served as a program committee member. Googlers were also co-authors of the following papers:

Risk-Aware Revenue Maximization in Display Advertising by Ana Radovanovic and William Heavlin (Googlers)
SessionJuggler: Secure Web Login From an Untrusted Terminal Using Session Hijacking by Elie Bursztein (Googler), Chinmay Soman, Dan Boneh and John Mitchell
Spotting Fake Reviewer Groups in Consumer Reviews by Arjun Murkherjee, Bing Liu, and Natalie Glance (Googler)
Your Two Weeks of Fame and Your Grandmother’s by James Cook, Atish Das Sarma, Alexander Fabrikant and Andrew Tomkins (Googlers)
YouTube Around the World: Geographic Popularity of Videos by Mirjam Wattenhofer (Googler), Anders Brodersen (Googler), and Salvatore Scellato
Who Killed My Battery: Analyzing Mobile Browser Energy Consumption by Narendran Thiagarajan, Gaurav Aggarwal (Googler), Angela Nicoara, Dan Boneh and Jatinder Singh
A Multimodal Search Engine based on Rich Unified Content Description by Thomas Steiner (Googler), Lorenzo Sutton, Sabine Spiller, Marilena Lazzaro, Francesco Saverio Nucci, Vincenzo Croce, Alberto Massari, Antonio Camurri, Anne Verroust-Blondet, Laurent Joyeux
Enabling on-the-fly Video Shot Detection on YouTube by Thomas Steiner (Googler), Ruben Verborgh, Joaquim Gabarro, Michael Hausenblas, Raphael Troncy and Rik Van De Walle
Fixing the Web one page at a time, or actually implementing xkcd #37 by Thomas Steiner (Googler), Ruben Verborgh, and Rik Van de Valle

Googlers co-organized three workshops:

Appification of the Web by Ed Chi (Googler), Brian Davison, and Evgeniy Gabrilovich (Googler)
Extracting Unambiguous Keywords from Microposts Using Web and Query Logs Data, as part of the Making Sense of Microsposts workshop by Davi Reis, Felipe Portavales Goldstein, and Fred Quintao (Googlers)
Human Computation Must Be Reproducible, as part of the CrowdSearch: Crowdsourcing Web search workshop by Praveen Paritosh (Googler)
WebQuality 2012: The Anti-Social Web by Zoltan Gyongyi (Googler), Carlos Castillo, Adam Jatowt, and Katsumi Tanaka

Additionally, a Googler led a tutorial:

The Role of Human-Generated and Automatically-Extracted Lexico-Semantic Resources in Web Search by Marius Pasca (Googler)

Googlers presented a poster:

Google Image Swirl by Yushi Jing, Henry Rowley, Jingbin Wang, David Tsai, Chuck Rosenberg, Michele Covell (Googlers)

At the conference, we also paid homage to the founding of the World Wide Web and the strong community and enterprise it’s created since the 1990s, seen in the Euronews report: Web inventor Tim Berners-Lee on imagining worlds. Through our products and support of WWW in 2013, we look forward to continuing to nurture the world wide web’s open ecosystem of knowledge, innovation and progress.

Add Research at Google to your circles on G+ to learn more about our academic conference involvement, view pictures from events, and hear about upcoming programming and presence at conferences

Video Stabilization on YouTube

2012-05-04T13:44:00.000-07:00

Posted by Matthias Grundmann, Vivek Kwatra, and Irfan Essa, Research at Google

One thing we have been working on within Research at Google is developing methods for making casual videos look more professional, thereby providing users with a better viewing experience. Professional videos have several characteristics that differentiate them from casually shot videos. For example, in order to tell a story, cinematographers carefully control lighting and exposure and use specialized equipment to plan camera movement.

We have developed a technique that mimics professional camera moves and applies them to videos recorded by hand-held devices. Cinematographers use specialized equipment such as tripods and dollies to plan their camera paths and hold them steady. In contrast, think of a video you shot using a mobile phone camera. How steady was your hand and were you able to anticipate an interesting moment and smoothly pan the camera to capture that moment? To bridge these differences, we propose an algorithm that automatically determines the best camera path and recasts the video as if it were filmed using stabilization equipment. Specifically, we divide the original, shaky camera path into a set of segments, each approximated by either a constant, linear or parabolic motion of the camera. Our optimization finds the best of all possible partitions using a computationally efficient and stable algorithm. For details, check out our earlier blog post or read our paper, Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths, published in IEEE CVPR 2011.

The next time you upload your videos to YouTube, try stabilizing them by going to the YouTube editor or directly from the video manager by clicking on Edit->Enhancements. For even more convenience, YouTube will automatically detect if your video needs stabilization and offer to do it for you. Many videos on YouTube have already been enhanced using this technology.

More recently, we have been working on a related problem common in videos shot from mobile phones. The camera sensors in these phones contain what is known as an electronic rolling shutter. When taking a picture with a rolling shutter camera, the image is not captured instantaneously. Instead, the camera captures the image one row of pixels at a time, with a small delay when going from one row to the next. Consequently, if the camera moves during capture, it will cause image distortions ranging from shear in the case of low-frequency motions (for instance an image captured from a driving car) to wobbly distortions in the case of high-frequency perturbations (think of a person walking while recording video). These distortions are especially noticeable in videos where the camera shake is independent across frames. For example, take a look at the video below.

Original video with rolling shutter distortions

In our recent paper titled Calibration-Free Rolling Shutter Removal, which was awarded the best paper at IEEE ICCP 2012, we demonstrate a solution to correct these rolling shutter distortions in videos. A significant feature of our approach is that it does not require any knowledge of the camera used to shoot the video. The time delay in capturing two consecutive rows that we mention above is in fact different for every camera and affects the extent of distortions. Having knowledge of this delay parameter can be useful, but difficult to obtain or estimate via calibration. Imagine a video that is already uploaded to YouTube -- it will be challenging to obtain this parameter! Instead, we show that just the visual data in the video has enough information to appropriately describe and compensate for the distortions caused by the camera motion, even in the presence of a rolling shutter. For more information, see the narrated video description of our paper.

This technique is already integrated with the YouTube stabilizer. Starting today, if you stabilize a video from a mobile phone or other rolling shutter cameras, we will also automatically compensate for rolling shutter distortions. To see our technique in action, check out the video below, obtained after applying rolling shutter compensation and stabilization to the one above.

After stabilization and rolling shutter removal

An Experiment in Music and Crowd-Sourcing

2012-05-04T10:00:00.000-07:00

Posted by Maggie Johnson, Director of Education and University Relations

The Bodleian Library is the main research library at the University of Oxford. It is also one of the oldest libraries in the world, dating back to the 14th century. But the staff of the Bodleian operates very much in the 21st century, using the latest technology to solve their unique problems.

A few years ago, the library acquired a set of 4,000 popular piano pieces from the mid-Victorian period. There’s very little information available on these pieces, so Bodleian staff decided to use crowdsourcing to collect information on this corpus of music. Through a Google Focused Award, they have digitized and made the entire set of music available online.

By visiting the What’s-the-Score website, which opened yesterday, ‘citizen librarians’ can help by describing the scores and contributing to the creation of an online catalogue. They can also include links to audio or video recordings. This is the first time the Bodleian has used this approach to collect catalog information. Typically, a large group of researchers are required to find this information.

Martin Holmes, Alfred Brendel Curator of Music at the Bodleian Libraries, commented: ‘In making the scores available online, they will not only be accessible for academic study and research but will also be there to enjoy for anyone who is interested in various aspects of Victorian music, culture and society.’

The Bodleian Library is one of dozens of recipients of Google Focused Awards. These awards are for research in areas of study that are of key interest to Google as well as the research community. These unrestricted gifts are for two to three years, and the recipients have the advantage of access to Google tools, technologies, and expertise. The Bodleian’s experiment in crowdsourcing to build up data on a specialized collection is timely and interesting, given the number of such collections becoming available on the web.

From Open Research to Open Flow

2012-05-02T10:00:00.001-07:00

Posted by Jeff Walz, University Relations Team

Did you know Open Flow has its roots in academia? Back in May 2006 Vint Cerf was visiting Stanford to deliver an invited lecture. Following the talk he met with Stanford Professor Nick McKeown and learned about the Clean Slate Internet project. Nick was looking for support and Google’s involvement in what he described as a lab for “radical new ideas in networking”. Vint felt the program looked “intellectually healthy but might be a very long term matter to bear fruit”. Vint explained that for us to get involved we would want to have Google engineers excited and engaged.

Professor McKeown met with Google networking and infrastructure experts to present his ideas. Everybody knew that Software-Defined Networking (SDN) had great promise but the Open Flow effort seemed a bit ambitious for a professor and a couple of grad students. Googlers Dave Presotto and Stephen Stuart agreed to take a chance on it and sponsor a small research grant to fund another student and to get Google engaged. As Google and the industry got more involved, Open Flow began to gain traction. In June 2008 Google provided another grant to support more students and in late 2009 Google joined the initiatives consortium with other industry members.

Google engineers Stephen Stuart and Jim Wanderer worked closely with Stanford and lead Google’s Open Flow development and deployment. In 2011 the Open Networking Foundation (ONF) was formed to accelerate Software-Defined Networking standards and foster a robust market and ecosystem. Google’s own Urs Hölzle became ONF’s first President and Chairman of the Board.

Google involvement and support of this academic effort was a key factor to the speedy development and deployment of Open Flow and SDN - technology that made it from a university research project to running Google’s WAN in record time.

Joining forces to support computer science majors

2012-04-26T11:00:00.000-07:00

Posted by Maggie Johnson, Director of Education and University Relations

A few weeks ago, I attended the annual SIGCSE (Special Interest Group, Computer Science Education) conference in Raleigh, NC. Google has been a platinum sponsor of SIGCSE for many years now, and the conference provides an opportunity for thousands of CS educators to come together, share ideas and work on significant challenges that have emerged over the last five years.

Five years ago, the Advanced Placement Computer Science course and exam almost died. Due to lack of student interest, the B part of the AP CS was discontinued and there was a risk that the A part would also be discontinued. At that time, the number of CS majors at the undergraduate level also hit an all time low. Specifically, the number of students taking the AP CS exam fell 15 % between 2001 and 2007, and the number of college freshmen intending to major in CS plummeted more than 70% during the same period. This was a paradox for CS educators. They knew (and know) that advancing U.S. students' understanding of the principles and practices of computing is critical to developing a globally competitive workforce for the 21st century.

Rather than be defeated, a commission of ten secondary and higher education faculty came together and used this as an opportunity to reinvigorate interest in CS. They re-invented the AP CS into a course that not only introduces students to programming, but also gives them an understanding of the fundamental concepts of computing, its breadth of application and its potential for transforming the world.

The NSF generously funded the development and piloting of this new CS Principles course two years ago. This academic year, the NSF has funded several high school pilots as well. The pilots have been so successful that the College Board has now committed to developing a new state-of-the-art exam for the course. This is a critical accomplishment. The AP CS is the only standardized computing course we have in high school. The high school curriculum is packed—it’s nearly impossible to get any new course from any domain into the curriculum, and the AP CS is our stake in the ground.

Concurrent with the AP CS development, the ACM has pushed forward on two fronts that are also making significant impact. The CSTA (Computer Science Teachers Association) now has 11,000 members with 2300 College Board-certified to teach the AP CS Part A (which is still being offered). Membership and interest is rising, and this community plays a key role in professional development, CS standards definition (another critical stake in the ground) and scaling of the new AP CS.

In addition, we have the Computing in the Core Coalition, which is a non-partisan advocacy group of associations, corporations, scientific societies and other nonprofits that is working to elevate CS to a core academic subject in K-12 education. The Coalition does this through advocacy with government agencies and Congress, and by raising general awareness through CSEdWeek.

The good news is we are starting to see positive indicators of change. CS majors are rebounding at the undergraduate level.

The latest Employment Projections for 2010 to 2020 (Bureau of Labor Statistics) show a 6.9% increase in employment from 2006-2010 in computer and mathematical occupations, and a projected 22.0% increase from 2010-2020. This is in comparison to a 14.3% increase, on average, for all other growing occupations.

Students, parents, teachers, administrators and government officials are starting to hear the message:

There is an exponentially growing demand in computing job opportunities
Computing is inherently creative, innovative and team-based
Technology and computing are transforming the world

Of course, we still do not have nearly enough supply coming out of colleges and universities to meet the demand, but the situation has improved in the last two years.

We believe that computing and CS are critical to our future, and we support CS education through many programs including CS4HS, App Inventor (just re-launched from MIT), our Exploring Computational Thinking curriculum, and other outreach programs and partnerships. Computing is at the foundation of all things technology, and computer science is at the foundation of computing.

Working with your Data: Easier and More Fun

2012-04-12T09:00:00.000-07:00

Posted by Rebecca Shapley, Fusion Tables Team

The Fusion Tables team has been a little quiet lately, but that’s just because we’ve been working hard on a whole bunch of new stuff that makes it easier to discover, manage and visualize data.

A new way to look at your Fusion Table - Try the “Experimental” version of our Fusion Tables web application. The new design helps you explore and collaborate better on data. Faceted search make it easier to dive into a big data set and specify what you want to see. Multiple tabs let you experiment, trying different views of a table. And the new card layout lets you give a row of data your own custom layout. Give it a spin.

More visualizations on lots of data - People love using Fusion Tables to put data on a map, but there are new visualizations available in our Experiment menu.Try the Zoomable Line chart. Playing with social network data? Try out the Network Graph visualization.

New Fusion Tables API works great with javascript - Our new API, currently available to trusted testers, is more powerful and easier to use. The API can now return data in JSON so it’s easy to get data and manipulate it with javascript, right from the browser. You can now also RESTfully modify tables, templates and map styles. Want to try it out early and give your feedback? We’re looking for Trusted Testers... just join this group to become one.

New open-source tools library welcomes your contributions - Fond of Fusion Tables Layer wizard? Just recently discovered the chart creator? These great point-n-click tools and more for working with Fusion Tables are now available in the Fusion Tables open source library. Please contribute your tools and enhancements!

You’ll notice a bunch of our new things are “Experimental”....that’s because we need you to use them and tell us what you love and what could be better. But we didn’t want to keep them secret any longer! On behalf of the Fusion Table team, thanks for all you do with Fusion Tables, and we’re looking forward to hearing your thoughts and feedback.

Google App Engine Research Awards for scientific discovery

2012-03-29T12:00:00.000-07:00

Posted by Maggie Johnson, Director of Education and University Relations and Andrea Held, University Relations Program Manager

Since its launch four years ago, Google App Engine has been the platform for innovative and diverse applications. Today, Google’s University Relations team is inviting academic researchers to explore App Engine as a platform for their research activities through a new program: the Google App Engine Research Awards.

These research awards provide an opportunity for university faculty to experiment with App Engine, which provides services for building and hosting web applications on the same systems that power Google’s products and services. App Engine offers fast development and deployment, simple administration and built-in scalability -- it’s designed to adapt to large-scale data storage needs and sudden traffic spikes.

As part of Google’s ongoing commitment to support cutting-edge scientific research across the board, this call for applications welcomes university faculty’s proposals in all fields. Projects may focus on activities such as social or economic experiments, development of academic aids, analysis of gene sequence data, or using App Engine MapReduce to crunch large datasets, just to name a few.

This new award program will support up to 15 projects by providing App Engine credits in the amount of $60,000 to each project for one year. In its first year, the program is launched in a limited number of countries. Please see the RFP for details.

If your research has the potential to advance scientific discovery, generates heavy data loads, or needs a reliable platform for running large-scale apps, we encourage you to submit your proposal. Information on how to apply is available on the Google Research website. Applications will be accepted until 11:59 p.m. PST, May 11, 2012.

Impact of Organic Ranking on Ad Click Incrementality

2012-03-27T12:45:00.001-07:00

Posted by David Chan, Statistician and Lizzy Van Alstine, Research Evangelist

In 2011, Google released a Search Ads Pause research study which showed that 89% of the clicks from search ads are incremental, i.e., 89% of the visits to the advertiser’s site from ad-clicks are not replaced by organic clicks when the search ads are paused. In a follow up to the original study, we address two main questions: (1) how often is an ad impression accompanied by an associated organic result (i.e., organic result for the same advertiser)? and (2) how does the incrementality of the ad clicks vary with the rank of advertiser’s organic results?

A meta-analysis of 390 Search Ads Pause studies highlighted the limited opportunity for clicks from organic search results to substitute for ad clicks when search ads are turned off. We found that on average, 81% of ad impressions and 66% of ad clicks occur in the absence of an associated organic result on the first page of search results. In addition, we found that on average, 50% of the ad clicks that occur with a top rank organic result are incremental. The estimate for average incrementality of the ad clicks increases when the rank is lower; 82% of the ad clicks are incremental when the associated organic search result is between ranks 2 and 4, and 96% of the ad clicks are incremental when the advertiser’s organic result ranked lower than 4 (i.e., 5 and below).

While these findings provide guidance on overall trends, results for individual advertisers may vary. It’s also important to note that the study focuses on clicks rather than conversions. We recommend that advertisers employ randomized experiments (e.g., geo-based experiments) to better quantify the incremental traffic and lift in conversions from the search ad campaigns and that they use the value-per-click calculations in the original search ads pause study to determine the level of investment on their search ads.

For more information, find the full study here.

Excellent Papers for 2011

2012-03-22T11:00:00.001-07:00

Posted by Corinna Cortes and Alfred Spector, Google Research

UPDATE: Added Theo Vassilakis as an author for "Dremel: Interactive Analysis of Web-Scale Datasets"

Googlers across the company 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, feature aspects 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 blog. 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. In a second round, we highlighted new noteworthy papers from the later half of 2010. This time we honor the influential papers authored or co-authored by Googlers covering all of 2011 -- covering roughly 10% of our total publications. It’s tough choosing, so we may have left out some important papers. So, do see the publications list to review the complete group.

In the coming weeks we will be offering a more in-depth look at these publications, but here are some summaries:

Audio processing

“Cascades of two-pole–two-zero asymmetric resonators are good models of peripheral auditory function”, Richard F. Lyon, Journal of the Acoustical Society of America, vol. 130 (2011), pp. 3893-3904.
Lyon's long title summarizes a result that he has been working toward over many years of modeling sound processing in the inner ear. This nonlinear cochlear model is shown to be "good" with respect to psychophysical data on masking, physiological data on mechanical and neural response, and computational efficiency. These properties derive from the close connection between wave propagation and filter cascades. This filter-cascade model of the ear is used as an efficient sound processor for several machine hearing projects at Google.

Electronic Commerce and Algorithms

“Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations”, Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta, SODA 2011.
The authors introduce an elegant and powerful algorithmic technique to the area of online ad allocation and matching: a hybrid of random perturbations and greedy choice to make decisions on the fly. Their technique sheds new light on classic matching algorithms, and can be used, for example, to pick one among a set of relevant ads, without knowing in advance the demand for ad slots on future web page views.

“Milgram-routing in social networks”, Silvio Lattanzi, Alessandro Panconesi, D. Sivakumar, Proceedings of the 20th International Conference on World Wide Web, WWW 2011, pp. 725-734.
Milgram’s "six-degrees-of-separation experiment" and the fascinating small world hypothesis that follows from it, have generated a lot of interesting research in recent years. In this landmark experiment, Milgram showed that people unknown to each other are often connected by surprisingly short chains of acquaintances. In the paper we prove theoretically and experimentally how a recent model of social networks, "Affiliation Networks", offers an explanation to this phenomena and inspires interesting technique for local routing within social networks.

“Non-Price Equilibria in Markets of Discrete Goods”, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Noam Nisan, EC, 2011.
We present a correspondence between markets of indivisible items, and a family of auction based n player games. We show that a market has a price based (Walrasian) equilibrium if and only if the corresponding game has a pure Nash equilibrium. We then turn to markets which do not have a Walrasian equilibrium (which is the interesting case), and study properties of the mixed Nash equilibria of the corresponding games.

HCI

“From Basecamp to Summit: Scaling Field Research Across 9 Locations”, Jens Riegelsberger, Audrey Yang, Konstantin Samoylov, Elizabeth Nunge, Molly Stevens, Patrick Larvie, CHI 2011 Extended Abstracts.
The paper reports on our experience with a basecamp research hub to coordinate logistics and ongoing real-time analysis with research teams in the field. We also reflect on the implications for the meaning of research in a corporate context, where much of the value may be less in a final report, but more in the curated impressions and memories our colleagues take away from the the research trip.

“User-Defined Motion Gestures for Mobile Interaction”, Jaime Ruiz, Yang Li, Edward Lank, CHI 2011: ACM Conference on Human Factors in Computing Systems, pp. 197-206.
Modern smartphones contain sophisticated sensors that can detect rich motion gestures — deliberate movements of the device by end-users to invoke commands. However, little is known about best-practices in motion gesture design for the mobile computing paradigm. We systematically studied the design space of motion gestures via a guessability study that elicits end-user motion gestures to invoke commands on a smartphone device. The study revealed consensus among our participants on parameters of movement and on mappings of motion gestures onto commands, by which we developed a taxonomy for motion gestures and compiled an end-user inspired motion gesture set. The work lays the foundation of motion gesture design—a new dimension for mobile interaction.

Information Retrieval

“Reputation Systems for Open Collaboration”, B.T. Adler, L. de Alfaro, A. Kulshrestra, I. Pye, Communications of the ACM, vol. 54 No. 8 (2011), pp. 81-87.
This paper describes content based reputation algorithms, that rely on automated content analysis to derive user and content reputation, and their applications for Wikipedia and google Maps. The Wikipedia reputation system WikiTrust relies on a chronological analysis of user contributions to articles, metering positive or negative increments of reputation whenever new contributions are made. The Google Maps system Crowdsensus compares the information provided by users on map business listings and computes both a likely reconstruction of the correct listing and a reputation value for each user. Algorithmic-based user incentives ensure the trustworthiness of evaluations of Wikipedia entries and Google Maps business information.

Machine Learning and Data Mining

“Domain adaptation in regression”, Corinna Cortes, Mehryar Mohri, Proceedings of The 22nd International Conference on Algorithmic Learning Theory, ALT 2011.
Domain adaptation is one of the most important and challenging problems in machine learning. This paper presents a series of theoretical guarantees for domain adaptation in regression, gives an adaptation algorithm based on that theory that can be cast as a semi-definite programming problem, derives an efficient solution for that problem by using results from smooth optimization, shows that the solution can scale to relatively large data sets, and reports extensive empirical results demonstrating the benefits of this new adaptation algorithm.

“On the necessity of irrelevant variables”, David P. Helmbold, Philip M. Long, ICML, 2011
Relevant variables sometimes do much more good than irrelevant variables do harm, so that it is possible to learn a very accurate classifier using predominantly irrelevant variables. We show that this holds given an assumption that formalizes the intuitive idea that the variables are non-redundant. For problems like this it can be advantageous to add many additional variables, even if only a small fraction of them are relevant.

“Online Learning in the Manifold of Low-Rank Matrices”, Gal Chechik, Daphna Weinshall, Uri Shalit, Neural Information Processing Systems (NIPS 23), 2011, pp. 2128-2136.
Learning measures of similarity from examples of similar and dissimilar pairs is a problem that is hard to scale. LORETA uses retractions, an operator from matrix optimization, to learn low-rank similarity matrices efficiently. This allows to learn similarities between objects like images or texts when represented using many more features than possible before.

Machine Translation

“Training a Parser for Machine Translation Reordering”, Jason Katz-Brown, Slav Petrov, Ryan McDonald, Franz Och, David Talbot, Hiroshi Ichikawa, Masakazu Seno, Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP '11).
Machine translation systems often need to understand the syntactic structure of a sentence to translate it correctly. Traditionally, syntactic parsers are evaluated as standalone systems against reference data created by linguists. Instead, we show how to train a parser to optimize reordering accuracy in a machine translation system, resulting in measurable improvements in translation quality over a more traditionally trained parser.

“Watermarking the Outputs of Structured Prediction with an application in Statistical Machine Translation”, Ashish Venugopal, Jakob Uszkoreit, David Talbot, Franz Och, Juri Ganitkevitch, Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP).
We propose a general method to watermark and probabilistically identify the structured results of machine learning algorithms with an application in statistical machine translation. Our approach does not rely on controlling or even knowing the inputs to the algorithm and provides probabilistic guarantees on the ability to identify collections of results from one’s own algorithm, while being robust to limited editing operations.

“Inducing Sentence Structure from Parallel Corpora for Reordering”, John DeNero, Jakob Uszkoreit, Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP).
Automatically discovering the full range of linguistic rules that govern the correct use of language is an appealing goal, but extremely challenging. Our paper describes a targeted method for discovering only those aspects of linguistic syntax necessary to explain how two different languages differ in their word ordering. By focusing on word order, we demonstrate an effective and practical application of unsupervised grammar induction that improves a Japanese to English machine translation system.

Multimedia and Computer Vision

“Kernelized Structural SVM Learning for Supervised Object Segmentation”, Luca Bertelli, Tianli Yu, Diem Vu, Burak Gokturk,Proceedings of IEEE Conference on Computer Vision and Pattern Recognition 2011.
The paper proposes a principled way for computers to learn how to segment the foreground from the background of an image given a set of training examples. The technology is build upon a specially designed nonlinear segmentation kernel under the recently proposed structured SVM learning framework.

“Auto-Directed Video Stabilization with Robust L1 Optimal Camera Paths”, Matthias Grundmann, Vivek Kwatra, Irfan Essa, IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011).
Casually shot videos captured by handheld or mobile cameras suffer from significant amount of shake. Existing in-camera stabilization methods dampen high-frequency jitter but do not suppress low-frequency movements and bounces, such as those observed in videos captured by a walking person. On the other hand, most professionally shot videos usually consist of carefully designed camera configurations, using specialized equipment such as tripods or camera dollies, and employ ease-in and ease-out for transitions. Our stabilization technique automatically converts casual shaky footage into more pleasant and professional looking videos by mimicking these cinematographic principles. The original, shaky camera path is divided into a set of segments, each approximated by either constant, linear or parabolic motion, using an algorithm based on robust L1 optimization. The stabilizer has been part of the YouTube Editor (youtube.com/editor) since March 2011.

“The Power of Comparative Reasoning”, Jay Yagnik, Dennis Strelow, David Ross, Ruei-Sung Lin, International Conference on Computer Vision (2011).
The paper describes a theory derived vector space transform that converts vectors into sparse binary vectors such that Euclidean space operations on the sparse binary vectors imply rank space operations in the original vector space. The transform a) does not need any data-driven supervised/unsupervised learning b) can be computed from polynomial expansions of the input space in linear time (in the degree of the polynomial) and c) can be implemented in 10-lines of code. We show competitive results on similarity search and sparse coding (for classification) tasks.

NLP

“Unsupervised Part-of-Speech Tagging with Bilingual Graph-Based Projections”, Dipanjan Das, Slav Petrov, Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL '11), 2011, Best Paper Award.
We would like to have natural language processing systems for all languages, but obtaining labeled data for all languages and tasks is unrealistic and expensive. We present an approach which leverages existing resources in one language (for example English) to induce part-of-speech taggers for languages without any labeled training data. We use graph-based label propagation for cross-lingual knowledge transfer and use the projected labels as features in a hidden Markov model trained with the Expectation Maximization algorithm.

Networks

“TCP Fast Open”, Sivasankar Radhakrishnan, Yuchung Cheng, Jerry Chu, Arvind Jain, Barath Raghavan, Proceedings of the 7th International Conference on emerging Networking EXperiments and Technologies (CoNEXT), 2011.
TCP Fast Open enables data exchange during TCP’s initial handshake. It decreases application network latency by one full round-trip time, a significant speedup for today's short Web transfers. Our experiments on popular websites show that Fast Open reduces the whole-page load time over 10% on average, and in some cases up to 40%.

“Proportional Rate Reduction for TCP”, Nandita Dukkipati, Matt Mathis, Yuchung Cheng, Monia Ghobadi, Proceedings of the 11th ACM SIGCOMM Conference on Internet Measurement 2011, Berlin, Germany - November 2-4, 2011.
Packet losses increase latency of Web transfers and negatively impact user experience. Proportional rate reduction (PRR) is designed to recover from losses quickly, smoothly and accurately by pacing out retransmissions across received ACKs during TCP’s fast recovery. Experiments on Google Web and YouTube servers in U.S. and India demonstrate that PRR reduces the TCP latency of connections experiencing losses by 3-10% depending on response size.

Security and Privacy

“Automated Analysis of Security-Critical JavaScript APIs”, Ankur Taly, Úlfar Erlingsson, John C. Mitchell, Mark S. Miller, Jasvir Nagra, IEEE Symposium on Security & Privacy (SP), 2011.
As software is increasingly written in high-level, type-safe languages, attackers have fewer means to subvert system fundamentals, and attacks are more likely to exploit errors and vulnerabilities in application-level logic. This paper describes a generic, practical defense against such attacks, which can protect critical application resources even when those resources are partially exposed to attackers via software interfaces. In the context of carefully-crafted fragments of JavaScript, the paper applies formal methods and semantics to prove that these defenses can provide complete, non-circumventable mediation of resource access; the paper also shows how an implementation of the techniques can establish the properties of widely-used software, and find previously-unknown bugs.

“App Isolation: Get the Security of Multiple Browsers with Just One”, Eric Y. Chen, Jason Bau, Charles Reis, Adam Barth, Collin Jackson, 18th ACM Conference on Computer and Communications Security, 2011.
We find that anecdotal advice to use a separate web browser for sites like your bank is indeed effective at defeating most cross-origin web attacks. We also prove that a single web browser can provide the same key properties, for sites that fit within the compatibility constraints.

Speech

“Improving the speed of neural networks on CPUs”, Vincent Vanhoucke, Andrew Senior, Mark Z. Mao, Deep Learning and Unsupervised Feature Learning Workshop, NIPS 2011.
As deep neural networks become state-of-the-art in real-time machine learning applications such as speech recognition, computational complexity is fast becoming a limiting factor in their adoption. We show how to best leverage modern CPU architectures to significantly speed-up their inference.

“Bayesian Language Model Interpolation for Mobile Speech Input”, Cyril Allauzen, Michael Riley, Interspeech 2011.
Voice recognition on the Android platform must contend with many possible target domains - e.g. search, maps, SMS. For each of these, a domain-specific language model was built by linearly interpolating several n-gram LMs from a common set of Google corpora. The current work has found a way to efficiently compute a single n-gram language model with accuracy very close to the domain-specific LMs but with considerably less complexity at recognition time.

Statistics

“Large-Scale Parallel Statistical Forecasting Computations in R”, Murray Stokely, Farzan Rohani, Eric Tassone, JSM Proceedings, Section on Physical and Engineering Sciences, 2011.
This paper describes the implementation of a framework for utilizing distributed computational infrastructure from within the R interactive statistical computing environment, with applications to timeseries forecasting. This system is widely used by the statistical analyst community at Google for data analysis on very large data sets.

Structured Data

“Dremel: Interactive Analysis of Web-Scale Datasets”, Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis, Communications of the ACM, vol. 54 (2011), pp. 114-123.
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. Besides continued growth internally to Google, Dremel now also backs an increasing number of external customers including BigQuery and UIs such as AdExchange front-end.

“Representative Skylines using Threshold-based Preference Distributions”, Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jim Xu, International Conference on Data Engineering (ICDE), 2011.
The paper adopts principled approach towards representative skylines and formalizes the problem of displaying k tuples such that the probability that a random user clicks on one of them is maximized. This requires mathematically modeling (a) the likelihood with which a user is interested in a tuple, as well as (b) how one negotiates the lack of knowledge of an explicit set of users. This work presents theoretical and experimental results showing that the suggested algorithm significantly outperforms previously suggested approaches.

“Hyper-local, directions-based ranking of places”, Petros Venetis, Hector Gonzalez, Alon Y. Halevy, Christian S. Jensen, PVLDB, vol. 4(5) (2011), pp. 290-30.
Click through information is one of the strongest signals we have for ranking web pages. We propose an equivalent signal for raking real world places: The number of times that people ask for precise directions to the address of the place. We show that this signal is competitive in quality with human reviews while being much cheaper to collect, we also show that the signal can be incorporated efficiently into a location search system.

Systems

“Power Management of Online Data-Intensive Services”, David Meisner, Christopher M. Sadler, Luiz André Barroso, Wolf-Dietrich Weber, Thomas F. Wenisch, Proceedings of the 38th ACM International Symposium on Computer Architecture, 2011.
Compute and data intensive Web services (such as Search) are a notoriously hard target for energy savings techniques. This article characterizes the statistical hardware activity behavior of servers running Web search and discusses the potential opportunities of existing and proposed energy savings techniques.

“The Impact of Memory Subsystem Resource Sharing on Datacenter Applications”, Lingjia Tang, Jason Mars, Neil Vachharajani, Robert Hundt, Mary-Lou Soffa, ISCA, 2011.
In this work, the authors expose key characteristics of an emerging class of Google-style workloads and show how to enhance system software to take advantage of these characteristics to improve efficiency in data centers. The authors find that across datacenter applications, there is both a sizable benefit and a potential degradation from improperly sharing micro-architectural resources on a single machine (such as on-chip caches and bandwidth to memory). The impact of co-locating threads from multiple applications with diverse memory behavior changes the optimal mapping of thread to cores for each application. By employing an adaptive thread-to-core mapper, the authors improved the performance of the datacenter applications by up to 22% over status quo thread-to-core mapping, achieving performance within 3% of optimal.

“Language-Independent Sandboxing of Just-In-Time Compilation and Self-Modifying Code”, Jason Ansel, Petr Marchenko, Úlfar Erlingsson, Elijah Taylor, Brad Chen, Derek Schuff, David Sehr, Cliff L. Biffle, Bennet S. Yee, ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2011.
Since its introduction in the early 90's, Software Fault Isolation, or SFI, has been a static code technique, commonly perceived as incompatible with dynamic libraries, runtime code generation, and other dynamic code. This paper describes how to address this limitation and explains how the SFI techniques in Google Native Client were extended to support modern language implementations based on just-in-time code generation and runtime instrumentation. This work is already deployed in Google Chrome, benefitting millions of users, and was developed over a summer collaboration with three Ph.D. interns; it exemplifies how Research at Google is focused on rapidly bringing significant benefits to our users through groundbreaking technology and real-world products.

“Thialfi: A Client Notification Service for Internet-Scale Applications”, Atul Adya, Gregory Cooper, Daniel Myers, Michael Piatek,Proc. 23rd ACM Symposium on Operating Systems Principles (SOSP), 2011, pp. 129-142.
This paper describes a notification service that scales to hundreds of millions of users, provides sub-second latency in the common case, and guarantees delivery even in the presence of a wide variety of failures. The service has been deployed in several popular Google applications including Chrome, Google Plus, and Contacts.

Google at INFOCOM 2012

2012-03-21T09:00:00.000-07:00

Posted by Emilie Danna, Google Research & Michal Segalov,Networking Software

The computer networking community will get together in Orlando, Florida the week of March 25th for INFOCOM 2012, the Annual IEEE International Conference on Computer Communications.

At the conference, we will discuss topics such as traffic engineering, traffic anomaly detection, and random walk algorithms for topology-aware networks. We serve so much internet traffic to Google users and exchange so much data between our data centers that computer networking is naturally something we care about. As traffic grows with richer content (photos, video, ...), new modes of engagement (cloud computing, social networking, ...) and an increasing number of users, engineering and research efforts are necessary to help networks scale.

The following papers were co-authored by Googlers from offices around the world:

Near-optimal random walk sampling in distributed networks by Atish Das Sarma, Anisur Molla, and Gopal Pandurangan
How to split a flow by Tzvika Hartman, Avinatan Hassidim, Haim Kaplan, Danny Raz, and Michal Segalov
Upward max-min fairness by Emilie Danna, Avinatan Hassidim, Haim Kaplan, Alok Kumar, Yishay Mansour, Danny Raz, and Michal Segalov (runner up for best paper)
A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering by Emilie Danna, Subhasree Mandal, and Arjun Singh
Traffic anomaly detection based on the IP size distribution by Fabio Soldo and Ahmed Metwally

If you are attending, stop by and say hi!

Gamification for Improved Search Ranking for YouTube Topics

2012-03-19T15:00:00.000-07:00

Posted by Charles DuHadway and Sanketh Shetty, Google Research

In earlier posts we discussed automatic ways to find the most talented emerging singers and the funniest videos using the YouTube Slam experiment. We created five “house” slams -- music, dance, comedy, bizarre, and cute -- which produce a weekly leaderboard not just of videos but also of YouTubers who are great at predicting what the masses will like. For example, last week’s cute slam winning video claims to be the cutest kitten in the world, beating out four other kittens, two puppies, three toddlers and an amazing duck who feeds the fish. With a whopping 620 slam points, YouTube user emoatali99 was our best connoisseur of cute this week. On the music side, it is no surprise that many of music slam’s top 10 videos were Adele covers. A Whitney Houston cover came out at the top this week, and music slam’s resident expert on talent had more than a thousand slam points. Well done! Check out the rest of the leaderboards for cute slam and music slam.

Can slam-style game mechanics incentivize our users to help improve the ranking of videos -- not just for these five house slams -- but for millions of other search queries and topics on YouTube? Gamification has previously been used to incentivize users to participate in non-game tasks such as image labeling and music tagging. How many votes and voters would we need for slam to do better than the existing ranking algorithm for topic search on YouTube?

As an experiment, we created new slams for a small number of YouTube topics (such as Latte Art Slam and Speed Painting Slam) using existing top 20 videos for these topics as the candidate pool. As we accumulated user votes, we evaluated the resulting YouTube Slam leaderboard for that topic vs the existing ranking on youtube.com/topics (baseline). Note that both the slam leaderboard and the baseline had the same set of videos, just in a different order.

What did we discover? It was no surprise that slam ranking performance had a high variance in the beginning and gradually improved as votes accumulated. We are happy to report that four of five topic slams converged within 1000 votes with a better leaderboard ranking than the existing YouTube topic search. In spite of small number of voters, Slam achieves better ranking partly because of gamification incentives and partly because it is based on machine learning, using:

Preference judgement over a pair, not absolute judgement on a single video, and,

Active solicitation of user opinion as opposed to passive observation. Due to what is called a “cold start” problem in data modeling, conventional (passive observation) techniques don’t work well on new items with little prior information. For any given topic, Slam’s improvement over the baseline in ranking of the “recent 20” set of videos was in fact better than the improvement in ranking of the “top 20” set.

Demographics and interests of the voters do affect slam leaderboard ranking, especially when the voter pool is small. An example is a Romantic Proposals Slam we featured on Valentine’s day last month. Men thought this proposal during a Kansas City Royals game was the most romantic, although this one where the man pretends to fall off a building came close. On the other hand, women rated this meme proposal in a restaurant as the best, followed by this movie theater proposal.

Encouraged by these results, we will soon be exploring slams for a few thousand topics to evaluate the utility of gamification techniques to YouTube topic search. Here are some of them: Chocolate Brownie, Paper Plane, Bush Flying, Stealth Technology, Stencil Graffiti, Yosemite National Park, and Stealth Technology.

Have fun slamming!

Search Ads Pause Studies Update

2012-03-12T09:00:00.000-07:00

Posted by Lizzy Van Alstine, Research Evangelist and David Chan, Statistician

In July 2011, Google released a study called "Incremental Clicks Impact of Search Advertising" that showed the amount of search ad traffic that is incremental to traffic from an advertiser’s organic search results. In that study, we asked these questions: What happens when search ads are paused? How much does organic traffic make up for the loss in traffic from search ads?

We found that an average 89% of paid clicks are essentially lost and not recovered by an increase in organic clicks when a search campaign is paused. This number - what we call the Incremental Ad Clicks (IAC) - was consistent across all verticals.

In that initial study, we only examined cases where ads were completely paused. In this update, we looked at three additional change scenarios and included new cases up to August 2011, giving a total of more than 5,300 cases.

For the paused cases, the average IAC of 85% was a little lower than the previous value of 89%. We see there was some volatility in this estimate, month-to-month, driven purely by the mix of advertisers who choose to pause their ads in that month.

In the cases where spend was decreased (as opposed to paused), we found that the ads associated with the spend decrease drive on average 80% incremental traffic. This means that 80% of the traffic from those ads would not be made up for by organic traffic. This value is lower than the 85% value in the paused cases, possibly due to advertisers selectively turning down parts of their search advertising which they find less effective.

In cases where an advertiser was already spending on search ads and subsequently increased their ad spend, we also found that the associated ads drive, on average, 78% incremental traffic. In the last scenario, where advertisers were previously not advertising with search ads, and then turned on search ads, the incremental traffic was 79%.

Across the board, our findings are consistent: ads drive a very high proportion of incremental traffic - traffic that is not replaced by navigation from organic listings when the ads are turned off or turned down.

Click here for an infographic.

Keeping an “OER mind” about shared resources for education

2012-03-05T09:00:00.000-08:00

Posted by Maggie Johnson, Director of Education and University Relations

With ever-increasing demands being placed on our education system, including new skill sets that need to be taught to create a pipeline that can fill 21st century jobs, we must figure out how to make high-quality education more accessible to more people without overburdening our existing educational institutions. The Internet, and the platforms, tools and programs it enables, will surely be a part of the answer to this challenge.

Open Educational Resources (OER) are one piece of the solution. OER are teaching and learning resources that anyone can share, reuse and remix. As part of our ongoing commitment to increasing access to a cost-effective, high-quality education, we’re supporting the OpenCourseWare Consortium — a collaboration of higher education institutions and associated organizations from around the world creating OER — in organizing Open Education Week 2012, which begins today.

An example of OER in action is OpenStax, a recent non-profit initiative of Rice University and Connexions to offer students free, professional quality textbooks that meet scope and sequence requirements for several courses. They believe that these books could save students over $90 million in the next five years. Non-profit isn’t the only model for open education. Flat World Knowledge has built a business around OER by providing free online access to open textbooks, then selling print-on-demand copies and supplemental materials.

We’ll be acknowledging OER week through a panel event in Washington, DC, and over on our +Google in Education page, where we’ll be posting articles, sharing stories and interviews about the benefits of open education resources. Opening these resources to everyone can improve the quality of education while getting more out of our investments in educational resources. We hope you’ll join us in celebrating Open Education Week. Go to openeducationweek.org to learn more and get involved.

Announcing Google-hosted workshop videos from NIPS 2011

2012-02-23T08:00:00.000-08:00

Posted by John Blitzer and Douglas Eck, Google Research

At the 25th Neural Information Processing Systems (NIPS) conference in Granada, Spain last December, we engaged in dialogue with a diverse population of neuroscientists, cognitive scientists, statistical learning theorists, and machine learning researchers. More than twenty Googlers participated in an intensive single-track program of talks, nightly poster sessions and a workshop weekend in the Spanish Sierra Nevada mountains. Check out the NIPS 2011 blog post for full information on Google at NIPS.

In conjunction with our technical involvement and gold sponsorship of NIPS, we recorded the five workshops that Googlers helped to organize on various topics from big learning to music. We’re now pleased to provide access to these rich workshop experiences to the wider technical community.

Watch videos of Googler-led workshops on the YouTube Tech Talks Channel:

Big Learning: Algorithms, Systems, and Tools for Learning at Scale by Joseph Gonzalez, Sameer Singh, Graham Taylor, James Bergstra, Alice Zheng, Misha Bilenko, Yucheng Low, Yoshua Bengio, Michael Franklin, Carlos Guestrin, Andrew McCallum, Alexander Smola, Michael Jordan, Sugato Basu (Googler)
Domain Adaptation Workshop: Theory and Application by John Blitzer, Corinna Cortes, Afshin Rostamizadeh (all Googlers)
Learning Semantics by Antoine Bordes, Jason Weston (Googler), Ronan Collobert, Leon Bottou
Sparse Representation and Low-rank Approximation by Ameet Talwalkar, Lester Mackey, Mehryar Mohri (Googler), Michael Mahoney, Francis Bach, Mike Davies, Remi Gribonval, Guillaume Obozinski
International Workshop on Music and Machine Learning: Learning from Musical Structure by Rafael Ramirez, Darrell Conklin, Douglas Eck (Googler), Ryan Rifkin (Googler)

To highlight a few workshops: The Domain Adaptation workshop organized by Google, which fused theoretical and practical domain adaptation, featured invited talks from Shai Ben-David and Googler Mehryar Mohri from the theory side and Dan Roth from the applications side. This was just next door to Googlers Doug Eck and Ryan Rifkin's workshop on Machine Learning and Music, with musical demonstrations loud enough for the next-door neighbors to ask them to “turn it down a bit, please.” In addition to the Googler-run workshops, the Integrating Language and Vision workshop showcased invited talks by Google postdoctoral fellow Percy Liang on the pragmatics of visual scene description and Josh Tenenbaum on physical models as a cognitive plausible mechanism for bridging language and vision. Finally, Google consultant Andrew Ng was one of the organizers of the Deep Learning and Unsupervised Feature Learning, which offered an extended tutorial, several inspiring talks, and two panel discussions (one with Googler Samy Bengio as panelist) exploring the question of “How deep is deep?”

As the workshop weekend drew to a close, an airline strike in Spain left NIPS attendees scrambling to get home for the holidays. We hope the skies look clear for 2012 when NIPS lands in Google’s neck of the woods, Lake Tahoe!

2011 EMEA Android Educational Outreach Program Awards Mobile Phones to Universities

2012-02-22T07:01:00.001-08:00

Posted by David Harper, Head of University Relations, EMEA

As part of EMEA’s 2011 Android Educational Outreach program, we recently granted over 300 Android-powered mobile phones to 40 universities across Europe, the Middle East, and Africa. These phones will be used to support mobile related project work in university teaching and research. Our steering committee reviewed applications from 77 universities in 24 countries across the region and selected finalists based on each proposal’s scope to generate interest in mobile engineering, reach many students, and be applicable both within and outside the university.

This is the second year we have awarded mobile phones to universities. This is largely attributable to the enthusiastic feedback from last year’s recipients who were interested in continued support for Android project work. The phones donated last year were used in a range of interesting projects, including:

George Candea, EPFL (Switzerland): The Pocket Campus, an application that helps students, graduates, staff and visitors to find their way around the EPFL campus was created as a course project. After the course, some of the students decided to continue development of the application. It has become so successful that it’s now EPFL’s campus-wide smartphone app.
Andrew Rice, University of Cambridge (United Kingdom): Students in the summer programme developed Learn!, a flashcard-based learning application that is available in Android Market. This project investigated how one might incorporate features of modern phones such as multimedia capture and playback, data communications and significant computation power into a learning application.
Alan Smeaton and colleagues, Dublin City University (Ireland): Undergraduate, master’s, and PhD students embarked on a wide variety of projects, which included lifelogging (recording everyday activities using the phone); measuring the strengths of wireless networks as an aid to mapping wireless propagation; and interface design for an augmented reality application.
Nicolae Tapus, University Politehnica of Bucharest (Romania): Numerous applications were developed by students, including: TaxiFinder, an application that finds the closest taxi number with the lowest price, and Viewlity, an augmented reality engine for showing nearby points of interest (e.g., gas stations, restaurants, ATMs, places of worship) on an Android phone.
Gerhard Tröster, ETH Zurich (Switzerland): Martin Wirz and his team are using mobile phones to conduct research in the field of wearable computing and machine learning. The devices are used to collect all kinds of sensor information (e.g., accelerometer, magnetometer, microphone, GPS) to infer personal activities, psychological behaviors and social phenomena.

We are looking forward to sharing the great projects resulting from this year’s Android Educational Outreach program early next summer.

Quantifying comedy on YouTube: why the number of o’s in your LOL matter

2012-02-09T07:30:00.000-08:00

Posted by Sanketh Shetty, YouTube Slam Team, Google Research

In a previous post, we talked about quantification of musical talent using machine learning on acoustic features for YouTube Music Slam. We wondered if we could do the same for funny videos, i.e. answer questions such as: is a video funny, how funny do viewers think it is, and why is it funny? We noticed a few audiovisual patterns across comedy videos on YouTube, such as shaky camera motion or audible laughter, which we can automatically detect. While content-based features worked well for music, identifying humor based on just such features is AI-Complete. Humor preference is subjective, perhaps even more so than musical taste.

Fortunately, at YouTube, we have more to work with. We focused on videos uploaded in the comedy category. We captured the uploader’s belief in the funniness of their video via features based on title, description and tags. Viewers’ reactions, in the form of comments, further validate a video’s comedic value. To this end we computed more text features based on words associated with amusement in comments. These included (a) sounds associated with laughter such as hahaha, with culture-dependent variants such as hehehe, jajaja, kekeke, (b) web acronyms such as lol, lmao, rofl, (c) funny and synonyms of funny, and (d) emoticons such as :), ;-), xP. We then trained classifiers to identify funny videos and then tell us why they are funny by categorizing them into genres such as “funny pets”, “spoofs or parodies”, “standup”, “pranks”, and “funny commercials”.

Next we needed an algorithm to rank these funny videos by comedic potential, e.g. is “Charlie bit my finger” funnier than “David after dentist”? Raw viewcount on its own is insufficient as a ranking metric since it is biased by video age and exposure. We noticed that viewers emphasize their reaction to funny videos in several ways: e.g. capitalization (LOL), elongation (loooooool), repetition (lolololol), exclamation (lolllll!!!!!), and combinations thereof. If a user uses an “loooooool” vs an “loool”, does it mean they were more amused? We designed features to quantify the degree of emphasis on words associated with amusement in viewer comments. We then trained a passive-aggressive ranking algorithm using human-annotated pairwise ground truth and a combination of text and audiovisual features. Similar to Music Slam, we used this ranker to populate candidates for human voting for our Comedy Slam.

So far, more than 75,000 people have cast more than 700,000 votes, making comedy our most popular slam category. Give it a try!

Further reading:

“Opinion Mining and Sentiment Analysis,” by Bo Pang and Lillian Lee.
“A Great Catchy Name: Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews,” by Oren Tsur, Dmitry Davidov, and Ari Rappoport.
“That’s What She Said: Double Entendre Identiﬁcation,” by Chloe Kiddon and Yuriy Brun.

Data and code open sourced from Google's Renewable Energy Cheaper than Coal project

2012-01-30T08:00:00.001-08:00

Posted by Ross Koningstein, Engineer, Google RE<C team

Cross-posted with the Open Source at Google Blog

Google’s RE<C renewable energy research project has recently open sourced a new tool and a significant amount of data to support future CSP (concentrating solar power) heliostat development.

HOpS Open Source Site

HOpS, heliostat optical simulation, is an open source software tool for accurately and efficiently performing optical simulations of fields of heliostats, the actuated mirror assemblies that direct sunlight onto a target in CSP applications.

Google used this tool to help evaluate heliostat field layouts and calculate heat input into a CSP receiver for power production. HOpS works by passing "packets" of light between optical elements (the sun, heliostats, and elements of the target surface), tracking shadowing and blocking masks along the way. For our analysis goals, this approach gave our researchers more flexibility and accuracy than analytic tools (such as DELSOL or HFLCAL), and it was easier to set up for thousands of runs than using ray tracers. Output from the simulation includes heliostat efficiency, target irradiance, and more, while an included shell script facilitates plotting heat maps of the output data using gnuplot.

REC-CSP Open Source Site

The REC_CSP open source project contains data sets and software useful for designing cheaper heliostats.

Available on the project site are:

1. Thirty days of three-dimensional wind measurement data taken with ultrasonic anemometers (sampled at ~7 Hz), recorded at several near surface elevations. The data is presented in the RE<C wind data collection document and is available for download on the open source site here.

2. A collection of heliostat aerodynamic load data obtained in a NASA wind tunnel and graphically represented in the appendix. This data is available for download on the open source site here.

3. Matlab software for high-precision, on-target heliostat control with built-in simulation for testing. This is essentially the same software used in the RE<C heliostat control demonstrations and described in the accelerometer sensing and control system design documents. The source code is available for download here.

Video: Demonstrating single and multiple heliostat control

Open-sourcing Sky Map and collaborating with Carnegie Mellon University

2012-01-20T13:30:00.000-08:00

Posted by John Taylor and Kevin Serafini

In May 2009 we launched Google Sky Map: our “window on the sky” for Android phones. Created by half a dozen Googlers at the Pittsburgh office in our 20% time, the app was designed to show off the amazing capabilities of the sensors in the first generation Android phones. Mostly, however, we wrote it because we love astronomy. And, thanks to Android’s broad reach, we have managed to share this passion with over 20 million Android users as well as with our local community at events such as the Urban Sky Party.

Today, we are delighted to announce that we are going to share Sky Map in a different way: we are donating Sky Map to the community. We are collaborating with Carnegie Mellon University in an exciting partnership that will see further development of Sky Map as a series of student projects. Sky Map’s development will now be driven by the students, with Google engineers remaining closely involved as advisors. Additionally, we have open-sourced the app so that other astronomy enthusiasts can take the code and augment it as they wish.

The Google Sky Map team would like to thank all of our users who have taken the time to send us comments over the past 3 years. You tell us that Sky Map has helped you show off your phone, enabled you to see the stars when the urban light pollution or weather obscured them and even find romance! The feedback that touched us most though can be summarized by this short email:

“sat down with my son and looked around at the planets for about 45 minutes...time well spent, thanx”

CDC Birth Vital Statistics in BigQuery

2012-01-13T10:46:00.000-08:00

Posted by Dan Vanderkam, Software Engineer

Google’s BigQuery Service lets enterprises and developers crunch large-scale data sets quickly. But what if you don’t have a large-scale data set of your own?

To help the data-less masses, BigQuery offers several large, public data sets. One of these is the natality data set, which records information about live births in the United States. The data is derived from the Division of Vital Statistics at the Centers for Disease Control and Prevention, which has collected an electronic record of birth statistics since 1969. It is one of the longest-running electronic records in existence.

Each row in this database represents a live birth. Using simple queries, you can discover fascinating trends from the last forty years.

For example, here’s the average age of women giving birth to their first child:

The average age has increased from 21.3 years in 1969 to 25.1 years in 2008. Using more complex queries, one could analyze the factors which have contributed to this increase, i.e. whether it can be explained by changing racial/ethnic composition of the population.

You can see more examples like this one on the BigQuery site.

Google Correlate expands to 49 additional countries

2012-01-03T09:58:00.000-08:00

Posted by Matt Mohebbi, Software Engineer

In May of this year we launched Google Correlate on Google Labs. This system enables a correlation search between a user-provided time series and millions of time series of Google search traffic. Since our initial launch, we've graduated to Google Trends and we've seen a number of great applications of Correlate in several domains, including economics (consumer spending, unemployment rate and housing inventory), sociology and meteorology. The correspondence of gas prices and search activity for fuel efficient cars was even briefly discussed in a Fox News presidential debate and NPR recently covered correlations related to political commentators.

Health has always been an area of particular interest to our team (Matt Mohebbi, Julia Kodysh, Rob Schonberger and Dan Vanderkam). Correlate was inspired by Google Flu Trends and many of us worked on both systems. So we were very excited when the BioSense division at the CDC published a page which shows correlations between some of their national trends in patient diagnosis activity and Google search activity. With just three years of weekly data, relevant search terms are surfaced. For example, the time series for bloody nose surfaces "bloody snot" and "blood in snot".

While these terms shouldn't come as a surprise, there are others which are more interesting, including searches related to static electricity, dry skin, and red cheeks. Of course, correlation is not causation but we hope that Correlate can be used as a method for researchers to generate new hypotheses with their data.

To help researchers outside the United States, we're pleased to announce support for 49 additional countries in Google Correlate. It's now possible to see correlations like "snorkeling" in Australia, "cherry blossoms" in Japan , and "beer garden" in Germany. We look forward to seeing what new correlations researchers can find with this data!

Academic Successes in Cluster Computing

2011-12-22T15:00:00.000-08:00

Posted by Alfred Spector, VP of Research

Access to massive computing resources is foundational to Research and Development. Fifteen awardees of the National Science Foundation (NSF) Cluster Exploratory Service (CLuE) program have been applying large scale computational resources donated by Google and IBM.

Overall, 1,328 researchers have used the cluster to perform over 120 million computing tasks on the cluster and in the process, have published 49 scientific publications, educated thousands of students on parallel computing and supported numerous post-doctoral candidates in their academic careers. Researchers have used the program for such diverse fields as astronomy, oceanography and linguistics. Besides validating MapReduce as a useful tool in academic research, the program has also generated significant scientific knowledge.

Three years later, there are many viable, affordable alternatives to the Academic Cloud Computing Initiative, so we have decided to bring our part of the program to a close. It has been a great opportunity to collaborate with IBM, the NSF and the many universities on this program. It was state-of-the-art four years ago when it was started; now, Academic Cloud Computing is a worldwide phenomena and there are many low-cost cloud computing options that provide viable alternatives to the Academic Cloud Computing Initiative.

Measuring Ad Effectiveness Using Geo Experiments

2011-12-09T08:48:00.000-08:00

Posted by Lizzy Van Alstine and Jon Vaver, Quantitative Analysis Team

Advertisers want to be able to measure the effectiveness of their advertising. Many methods have been used to address this need, but the most rigorous and trusted of these are randomized experiments, which involve randomly assigning experimental units to control and test conditions. At Google, we have found that randomized geo experiments are a powerful approach to measuring the effectiveness of advertising.

Many advertising platforms allow advertising to be targeted by geographical region. In these experiments, we first assign geographic regions to test or control conditions and employ AdWords’ geo-targeted advertising capabilities to increase or decrease the regional advertising spend accordingly. The use of randomized assignments guards against potential hidden test/control biases that could impact the measurements. Our approach also accounts for seasonal changes that impact the volume and cost of advertising across the length of the experiment.

In this paper, we describe the application of geo experiments for measuring the impact of advertising on consumer behavior (e.g. clicks, conversions, downloads, etc.). This description includes the results of a geo experiment that our research team ran for a Google advertiser.