Google at INFOCOM 2012

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!

Read More

Gamification for Improved Search Ranking for YouTube Topics

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:

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


2. 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!

Read More

Search Ads Pause Studies Update

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.

Read More

Keeping an “OER mind” about shared resources for education

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.

Read More

Announcing Google-hosted workshop videos from NIPS 2011

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!

Read More

2011 EMEA Android Educational Outreach Program Awards Mobile Phones to Universities

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.

Read More

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

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:

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

Read More