Google Research Blog

Launching the Quantum Artificial Intelligence Lab

2013-05-16T02:00:00.000-07:00

Posted by Hartmut Neven, Director of Engineering

We believe quantum computing may help solve some of the most challenging computer science problems, particularly in machine learning. Machine learning is all about building better models of the world to make more accurate predictions. If we want to cure diseases, we need better models of how they develop. If we want to create effective environmental policies, we need better models of what’s happening to our climate. And if we want to build a more useful search engine, we need to better understand spoken questions and what’s on the web so you get the best answer.

So today we’re launching the Quantum Artificial Intelligence Lab. NASA’s Ames Research Center will host the lab, which will house a quantum computer from D-Wave Systems, and the USRA (Universities Space Research Association) will invite researchers from around the world to share time on it. Our goal: to study how quantum computing might advance machine learning.

Machine learning is highly difficult. It’s what mathematicians call an “NP-hard” problem. That’s because building a good model is really a creative act. As an analogy, consider what it takes to architect a house. You’re balancing lots of constraints -- budget, usage requirements, space limitations, etc. -- but still trying to create the most beautiful house you can. A creative architect will find a great solution. Mathematically speaking the architect is solving an optimization problem and creativity can be thought of as the ability to come up with a good solution given an objective and constraints.

Classical computers aren’t well suited to these types of creative problems. Solving such problems can be imagined as trying to find the lowest point on a surface covered in hills and valleys. Classical computing might use what’s called “gradient descent”: start at a random spot on the surface, look around for a lower spot to walk down to, and repeat until you can’t walk downhill anymore. But all too often that gets you stuck in a “local minimum” -- a valley that isn’t the very lowest point on the surface.

That’s where quantum computing comes in. It lets you cheat a little, giving you some chance to “tunnel” through a ridge to see if there’s a lower valley hidden beyond it. This gives you a much better shot at finding the true lowest point -- the optimal solution.

We’ve already developed some quantum machine learning algorithms. One produces very compact, efficient recognizers -- very useful when you’re short on power, as on a mobile device. Another can handle highly polluted training data, where a high percentage of the examples are mislabeled, as they often are in the real world. And we’ve learned some useful principles: e.g., you get the best results not with pure quantum computing, but by mixing quantum and classical computing.

Can we move these ideas from theory to practice, building real solutions on quantum hardware? Answering this question is what the Quantum Artificial Intelligence Lab is for. We hope it helps researchers construct more efficient and more accurate models for everything from speech recognition, to web search, to protein folding. We actually think quantum machine learning may provide the most creative problem-solving process under the known laws of physics. We’re excited to get started with NASA Ames, D-Wave, the USRA, and scientists from around the world.

Two Googlers elected to the American Academy of Arts and Sciences

2013-04-25T13:52:00.001-07:00

Posted by Alfred Spector, Vice President, Engineering

Cross-posted with the Official Google Blog

On Wednesday, the American Academy of Arts and Sciences announced its list of 2013 elected members. We’re proud to congratulate Peter Norvig, director of research, and Arun Majumdar, vice president for energy; two Googlers who are among the new members elected this year.

Membership in the American Academy of Arts and Sciences is considered one of the nation’s highest honors, with those elected recognized as leaders in the arts, public affairs, business, and academic disciplines. With more than 250 Nobel Prize laureates and 60 Pulitzer Prize winners among its fellows, the American Academy celebrates the exceptional contributions of the elected members to critical social and intellectual issues.

With their election, Peter and Arun join six other Googlers as American Academy members: Eric Schmidt, Vint Cerf, Alfred Spector, Hal Varian, Ray Kurzweil, and founders Sergey Brin and Larry Page, all of whom embody our commitment to innovation and real-world impact. You can read more detailed summaries of Peter and Arun’s achievements below.

Dr. Peter Norvig, currently director of research at Google, is known most for his broad expertise in computer science and artificial intelligence, exemplified by his co-authorship (with Stuart Russell) of the leading college text, Artificial Intelligence: A Modern Approach. With more than 50 publications and a plethora of webpages, essays and software programs on a wide variety of CS topics, Peter is a catalyst of fundamental research across a wide range of disciplines while remaining a hands-on scientist who writes his own code. Recently, he has taught courses on artificial intelligence and the design of computer programs via massively open online courses (MOOC). Learn more about Peter and his research on norvig.com.

Dr. Arun Majumdar leads Google.org’s energy initiatives and advises Google on its broader energy strategy. Prior to joining Google last year, he was the founding director of the U.S. Department of Energy's Advanced Research Projects Agency-Energy (ARPA-E), where he served from October 2009 until June 2012. Earlier, he was a professor of mechanical engineering as well as materials science and engineering at the University of California, Berkeley, and headed the Environmental Energy Technologies Division at the Lawrence Berkeley National Laboratory. He has published several hundred papers, patents, and conference proceedings. Find out more about Arun.

50,000 Lessons on How to Read: a Relation Extraction Corpus

2013-04-11T09:00:00.000-07:00

Posted by Dave Orr, Product Manager, Google Research

One of the most difficult tasks in NLP is called relation extraction. It’s an example of information extraction, one of the goals of natural language understanding. A relation is a semantic connection between (at least) two entities. For instance, you could say that Jim Henson was in a spouse relation with Jane Henson (and in a creator relation with many beloved characters and shows).

The goal of relation extraction is to learn relations from unstructured natural language text. The relations can be used to answer questions (“Who created Kermit?”), learn which proteins interact in the biomedical literature, or to build a database of hundreds of millions of entities and billions of relations to try and help people explore the world’s information.

To help researchers investigate relation extraction, we’re releasing a human-judged dataset of two relations about public figures on Wikipedia: nearly 10,000 examples of “place of birth”, and over 40,000 examples of “attended or graduated from an institution”. Each of these was judged by at least 5 raters, and can be used to train or evaluate relation extraction systems. We also plan to release more relations of new types in the coming months.

Each relation is in the form of a triple: the relation in question, called a predicate; the subject of the relation; and the object of the relation. In the relation “Stephen Hawking graduated from Oxford,” Stephen Hawking is the subject, graduated from is the relation, and Oxford University is the object. Subjects and objects are represented by their Freebase MID’s, and the relation is defined as a Freebase property. So in this case, the triple would be represented as:

"pred":"/education/education/institution"
"sub":"/m/01tdnyh"
"obj":"/m/07tgn"

Just having the triples is interesting enough if you want a database of entities and relations, but doesn’t make much progress towards training or evaluation a relation extraction system. So we’ve also included the evidence for the relation, in the form of a URL and an excerpt from the web page that our raters judged. We’re also including examples where the evidence does not support the relation, so you have negative examples for use in training better extraction systems. Finally, we included ID’s and actual judgments of individual raters, so that you can filter triples by agreement.

Gory Details

The corpus itself, extracted from Wikipedia, can be found here: https://code.google.com/p/relation-extraction-corpus/

The files are in JSON format. Each line is a triple with the following fields:

pred: predicate of a triple
sub: subject of a triple
obj: object of a triple
evidences: an array of evidences for this triple

url: the web page from which this evidence was obtained
snippet: short piece of text supporting the triple

judgments: an array of judgements from human annotators

rator: hash code of the identity of the annotator
judgment: judgement of the annotator. It can take the values "yes" or "no"

Here’s an example:

{"pred":"/people/person/place_of_birth","sub":"/m/026_tl9","obj":"/m/02_286","evidences":[{"url":"http://en.wikipedia.org/wiki/Morris_S._Miller","snippet":"Morris Smith Miller (July 31, 1779 -- November 16, 1824) was a United States Representative from New York. Born in New York City, he graduated from Union College in Schenectady in 1798. He studied law and was admitted to the bar. Miller served as private secretary to Governor Jay, and subsequently, in 1806, commenced the practice of his profession in Utica. He was president of the village of Utica in 1808 and judge of the court of common pleas of Oneida County from 1810 until his death."}],"judgments":[{"rater":"11595942516201422884","judgment":"yes"},{"rater":"16169597761094238409","judgment":"yes"},{"rater":"1014448455121957356","judgment":"yes"},{"rater":"16651790297630307764","judgment":"yes"},{"rater":"1855142007844680025","judgment":"yes"}]}

The web is chock full of information, put there to be read and learned from. Our hope is that this corpus is a small step towards computational understanding of the wealth of relations to be found everywhere you look.

This dataset is licensed by Google Inc. under the Creative Commons Attribution-Sharealike 3.0 license.

Thanks to Shaohua Sun, Ni Lao, and Rahul Gupta for putting this dataset together.

Thanks also to Michael Ringgaard, Fernando Pereira, Amar Subramanya, Evgeniy Gabrilovich, and John Giannandrea for making this data release possible.

Advanced Power Searching with Google: Lessons Learned

2013-04-09T09:30:00.000-07:00

Posted by Dan Russell, Uber Tech Lead, Search Quality & User Happiness and Maggie Johnson, Director of Education and University Relations

Large classes are something you normally want to avoid like the plague. So the idea of being in a class with tens of thousands of students seems like a completely crazy idea.

But in January, 2013, Google offered a free “MOOC” (a Massive Open Online Course) to teach Advanced Power Searching (APS) to a wide variety of information professionals.

The wholly online class ran for two weeks covering advanced research skills in a challenge-based format. It also had a bit more than 35,000 students sign up for the class.

In this case, the large class size was a boon to the students. Not only was there a vigorous discussion of the material in the social media, but with a class this large, anytime you had a question, someone else in the class had almost certainly asked the same question and had an answer ready. As in many MOOCs, the large online class size did not stress any lecture hall capacities, but it did give the students the benefit of multicultural classmates that were effectively always present in the social spaces of the MOOC.

A typical Massive Open Online Course (MOOC) is a simple progression through a series of mini-lectures--usually a short video followed by reflective questions, problem sets and a few assessments. MOOCs can have huge numbers of students; dozens have been offered with over 150,000 students enrolled. Based on our experiments with Power Searching with Google in 2012, we wanted to do something different. When we offered Advanced Power Searching with Google (APS) in January of 2013, we decided to try out a number of new ideas.

Through this course, we wanted to enable our students to solve complex research questions using a variety of tools, such as Google Scholar, Patents, Books, Google+, etc.. We defined complex problems that had more than one right answer and more than one way to find those answers.

Unlike a traditional MOOC, the APS course had twelve challenges that students could tackle in any order they liked. There were four easy, four medium and four difficult challenges. Part of the design of the class was to have students discover the skills they’d need to solve the challenges and select appropriate video or text lessons. Students could also access case studies that showed how others solve similar problems.

We called our MOOC design “Choose your own adventure.” Each challenge presented a research question like this:

“You are in the city that is home to the House of Light. Nearby there is a museum in a converted school featuring paintings from the far-away Forest of Honey.

What traditional festival are you visiting?”

In this class, the large cohort of 35,000 students worked through the materials together, using online forums to ask questions as well as Google+ Hangouts to attend office hours and collaborate on solving challenges. Instructor Dan Russell and a group of teaching assistants monitored students’ activities and provided support as needed.

If they needed additional help, students could post a question on the forum or see how others solved the challenge. Students could post their solutions to challenges in a special “Peer explanations” section; a feature that many students appreciated as it let them see how others in the class approached the problem in their own ways.

In analyzing the data, we found that there were a decreasing number of views on each challenge page, indicating that students most likely tried the challenges in the order given. While some liked the ability to jump around, most tended to go through the content linearly. Most students who completed the course tried (or at least looked at) all twelve challenges. Many students who did not complete the course tried three or fewer challenges.

To earn a certificate of completion, students submitted two detailed case studies of how they solved a complex search challenge. Students provided great examples of how they used Google tools to research their family’s history, the origins of common objects, or trips they anticipate taking. In addition to listing their queries, they wrote details about how they knew websites were credible and what they learned along the way.

To assess their work, we experimented with letting the students grade their assignments based on a rubric. We collected their scores and compared them with a random sample of assignments graded by TAs. There was a moderate yet statistically significant correlation (r=0.44) between student scores and TA scores. In fact, the majority of students graded themselves within two points of how an expert grader assessed their work. This is a positive result since it suggests that self-graded project work in a MOOC can be valuable as a source of insight into student performance.

The challenge format seemed to be effective and motivating for a small, dedicated population of students. We had 35,000 registrants for this advanced course, and 12% earned a certificate of completion. This rate is somewhat lower than what we saw for Power Searching with Google, a more traditional MOOC. Students who did not complete the course reported a lack of time, and difficulty of the content as barriers.

One interesting point was that labeling the challenges as easy, medium or difficult likely had an unintentional effect. The first challenge was marked as “easy,” but many people found it difficult. This may have de-motivated students from attempting more difficult challenges. Next time, we plan to ask students if the first challenge was too easy, or too challenging, and then send them to a challenge at an appropriate level of difficulty.

Watch for more MOOCs on our products and services in the coming months. And watch for more experimentation as we apply what we have learned, and try more ideas and new approaches in future online courses.

Education Awards on Google App Engine

2013-03-27T10:00:00.000-07:00

Posted by Andrea Held, Google University Relations

Cross-posted with Google Developers Blog

Last year we invited proposals for innovative projects built on Google’s infrastructure. Today we are pleased to announce the 11 recipients of a Google App Engine Education Award. Professors and their students are using the award in cloud computing courses to study databases, distributed systems, web mashups and to build educational applications. Each selected project received $1000 in Google App Engine credits.

Awarding computational resources to classroom projects is always gratifying. It is impressive to see the creative ideas students and educators bring to these programs.
Below is a brief introduction to each project. Congratulations to the recipients!

John David N. Dionisio, Loyola Marymount University
Project description: The objective of this undergraduate database systems course is for students to implement one database application in two technology stacks, a traditional relational database and on Google App Engine. Students are asked to study both models and provide concrete comparison points.

Xiaohui (Helen) Gu, North Carolina State University
Project description: Advanced Distributed Systems Class
The goal of the project is to allow the students to learn distributed system concepts by developing real distributed system management systems and testing them on real world cloud computing infrastructures such as Google App Engine.

Shriram Krishnamurthi, Brown University
Project description: WeScheme is a programming environment that runs in the Web browser and supports interactive development. WeScheme uses App Engine to handle user accounts, serverside compilation, and file management.

Feifei Li, University of Utah
Project description: A graduate-level course that will be offered in Fall 2013 on the design and implementation of large data management system kernels. The objective is to integrate features from a relational database engine with some of the new features from NoSQL systems to enable efficient and scalable data management over a cluster of commodity machines.

Mark Liffiton, Illinois Wesleyan University
Project description: TeacherTap is a free, simple classroom-response system built on Google App Engine. It lets students give instant, anonymous feedback to teachers about a lecture or discussion from any computer or mobile device with a web browser, facilitating more adaptive class sessions.

Eni Mustafaraj, Wellesley College
Project description: Topics in Computer Science: Web Mashups. A CS2 course that combines Google App Engine and MIT App Inventor. Students will learn to build apps with App Inventor to collect data about their life on campus. They will use Google App Engine to build web services and apps to host the data and remix it to create web mashups. Offered in the 2013 Spring semester.

Manish Parashar, Rutgers University
Project description: Cloud Computing for Scientific Applications -- Autonomic Cloud Computing teaches students how a hybrid HPC/Grid + Cloud cyber infrastructure can be effectively used to support real-world science and engineering applications. The goal of our efforts is to explore application formulations, Cloud and hybrid HPC/Grid + Cloud infrastructure usage modes that are meaningful for various classes of science and engineering application workflows.

Orit Shaer, Wellesley College
Project description: GreenTouch
GreenTouch is a collaborative environment that enables novice users to engage in authentic scientific inquiry. It consists of a mobile user interface for capturing data in the field, a web application for data curation in the cloud, and a tabletop user interface for exploratory analysis of heterogeneous data.

Elliot Soloway, University of Michigan
Project description: WeLearn Mobile Platform: Making Mobile Devices Effective Tools for K-12. The platform makes mobile devices (Android, iOS, WP8) effective, essential tools for all-the-time, everywhere learning. WeLearn’s suite of productivity and communication apps enable learners to work collaboratively; WeLearn’s portal, hosted on Google App Engine, enables teachers to send assignments, review, and grade student artifacts. WeLearn is available to educators at no charge.

Jonathan White, Harding University
Project description: Teaching Cloud Computing in an Introduction to Engineering class for freshmen. We explore how well-designed systems are built to withstand unpredictable stresses, whether that system is a building, a piece of software or even the human body. The grant from Google is allowing us to add an overview of cloud computing as a platform that is robust under diverse loads.

Dr. Jiaofei Zhong, University of Central Missouri
Project description: By building an online Course Management System, students will be able to work on their team projects in the cloud. The system allows instructors and students to manage the course materials, including course syllabus, slides, assignments and tests in the cloud; the tool can be shared with educational institutions worldwide.

Scaling Computer Science Education

2013-03-13T11:15:00.000-07:00

Posted by Maggie Johnson, Director of Education and University Relations

Last week, I attended the annual SIGCSE (Special Interest Group, Computer Science Education) conference in Denver, CO. Google has been a platinum sponsor of SIGCSE for many years now, and the conference provides an opportunity for hundreds of computer science (CS) educators to share ideas and work on strategies to bring high quality CS education to K12 and undergraduate students.

Significant accomplishments over the last few years have laid a strong foundation for scaling CS curriculum, professional development (PD) and related programs in this country. The NSF has been funding curriculum and PD around the new CS Principles Advanced Placement course. The CSTA has published standards for K12 CS and a report on the limited extent to which schools, districts and states provide CS instruction to their students. CS Advocacy group, Computing in the Core, even provides a toolkit for communities to follow as they urge legislators for integration of Computer Science education into core K12 curriculum.

All of this work has made an impact, but there is still more to do.

I see our priorities in CS education to be ones of awareness and access. As CS educators, we must continue to raise awareness about the tremendous demand for jobs in the computing sector, and balance misconceptions with accurate data. Many students, parents, teachers and administrators remember the hype and disillusionment of the Dotcom period and myths on outsourcing and dwindling jobs yet the US Bureau of Labor Statistics (BLS) reports that ⅔ of all job growth in Science and Engineering will be in Computer Science employment over the next decade. (See 2010 BLS report here.) Clearing up this misconception is essential if we hope to satisfy US labor needs with recent graduates over the next several years.

Source: Gianchandani, Erwin. Revisiting ‘Where the Jobs Are’. The Computing Community Consortium Blog post on 23 May 2012. Link accessed on 8 March 2013.

Another misconception surrounds the range of CS-focused occupations that exist. The world of CS is expanding rapidly and we should celebrate the diversity of CS applications that are gaining momentum. Instead of the archetype of a sun-starved computer scientist, or software engineers working in isolation with little teamwork or communication opportunities, educators can encourage project-based learning, video game development, robotics, and graphic design as more concrete representations for abstract computational thinking.

Google believes that computing and CS are critical to our future, not only in the high tech sector, but for everyone. Our economy is becoming more and more dependent on technology-based solutions, which will require a future workforce with significant levels of CS knowledge and experience. In addition, we anticipate new career opportunities opening up in the next 3-5 years as more businesses move into the cloud and shift the way they run their IT departments.

Help us get the word out about the great opportunities in computing through organizations such as code.org, ACM, and NCWIT. Google is doing its part to support CS education and outreach through many programs including CS4HS, our Exploring Computational Thinking curriculum, and several student and teacher programs. So much opportunity, so little time!

Our Commitment to Social Computing Research: Social Interactions Focused Awards Announcement

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

Ed H. Chi, Staff Research Scientist

Social interactions have always been an important part of the human experience. Social interaction research has shown results ranging from influences on our behavior from social networks [Aral2012] to our understanding of social belonging on health [Walton2011], as well as how conflicts and coordination play out in Wikipedia [Kittur2007]. Interestingly, social scientists have studied social interactions for many years, but it wasn’t until very recently that researchers can study these mechanisms through the explosion of services and data available on web-based social systems.

From information dissemination and the spread of innovation and ideas, to scientific discovery, we are seeing how a deep understanding of social interactions is affecting many different fields, such as health and education. For instance, scientists now have strong evidence that social interactions underlie many fundamental learning mechanisms starting from infancy well into adulthood [Meltzoff2009], and that peer discussions are critical in conceptual learning in college classes [Smith2009]. How might these learning science findings be built into social systems and products so that users maximize what they learn on the Web?

We know that interactions on the Web are diverse and people-centered. Google now enables social interactions to occur across many of our products, from Google+ to Search to YouTube. To understand the future of this socially connected web, we need to investigate fundamental patterns, design principles, and laws that shape and govern these social interactions.

We envision research at the intersection of disciplines including Computer Science, Human-Computer Interaction (HCI), Social Science, Social Psychology, Machine Learning, Big Data Analytics, Statistics and Economics. These fields are central to the study of how social interactions work, particularly driven by new sources of data, for example, open data sets from Web2.0 and social media sites, government databases, crowdsourcing, new survey techniques, and crisis management data collections. New techniques from network science and computational modeling, social network and sentiment analysis, application of statistical and machine learning, as well as theories from evolutionary theory, physics, and information theory, are actively being used in social interaction research.

We’re pleased to announce that Google has awarded over $1.2 million dollars to support the Social Interactions Research Awards, which are given to university research groups doing work in social computing and interactions. Research topics range from crowdsourcing, social annotations, a social media behavioral study, social learning, conversation curation, and scientific studies of how to start online communities.

We have awarded 15 researchers in 7 universities. We selected these proposals after a rigorous internal review. We believe the results will be broadly useful to product development and will further scientific research.

Joseph Konstan, Loren Terveen, and John Riedl from University of Minnesota. Precision Crowdsourcing: Closing the Loop to turn Information Consumers into Information Contributors.
Mor Naaman from Rutgers University, and Oded Nov from Polytechnic Institute of New York University. Examining the Impact of Social Traces on Page Visitors’ Opinions and Engagement.
Paul Resnick, Eytan Adar, and Cliff Lampe from University of Michigan. MTogether: A Living Lab for Social Media Research.
Marti Hearst from UC Berkeley. Understanding Social Learning Among Subgroups Within Large Online Learning Environments.
David Karger and Rob Miller from MIT. Crowdsourced Curation of Conversations.
Robert Kraut, Laura Dabbish, Jason Hong, Aniket Kittur from CMU. Successfully Starting Online Groups.

We look forward to working with these researchers, and we hope that we will jointly push the frontier of social interactions research to the next level.

References
[1] Aral, S., & Walker, D. (2012). Identifying Influential and Susceptible Members of Social Networks. Science , 337 (6092 ), 337–341. doi:10.1126/science.1215842
[2] Walton, G. M., & Cohen, G. L. (2011). A Brief Social-Belonging Intervention Improves Academic and Health Outcomes of Minority Students. Science , 331 (6023 ), 1447–1451. doi:10.1126/science.1198364
[3] Aniket Kittur, Bongwon Suh, Bryan Pendleton, Ed H. Chi. He Says, She Says: Conflict and Coordination in Wikipedia. In Proc. of ACM Conference on Human Factors in Computing Systems (CHI2007), pp. 453--462, April 2007. ACM Press. San Jose, CA.
[4] Meltzoff, A. N., Kuhl, P. K., Movellan, J., & Sejnowski, T. J. (2009). Foundations for a New Science of Learning. Science , 325 (5938), 284–288. doi:10.1126/science.1175626
[5] Smith, M. K., Wood, W. B., Adams, W. K., Wieman, C., Knight, J. K., Guild, N., & Su, T. T. (2009). Why Peer Discussion Improves Student Performance on In-Class Concept Questions. Science , 323 (5910), 122–124. doi:10.1126/science.1165919

Learning from Big Data: 40 Million Entities in Context

2013-03-08T10:30:00.000-08:00

Posted by Dave Orr, Amar Subramanya, and Fernando Pereira, Google Research

When someone mentions Mercury, are they talking about the planet, the god, the car, the element, Freddie, or one of some 89 other possibilities? This problem is called disambiguation (a word that is itself ambiguous), and while it’s necessary for communication, and humans are amazingly good at it (when was the last time you confused a fruit with a giant tech company?), computers need help.

To provide that help, we are releasing the Wikilinks Corpus: 40 million total disambiguated mentions within over 10 million web pages -- over 100 times bigger than the next largest corpus (about 100,000 documents, see the table below for mention and entity counts). The mentions are found by looking for links to Wikipedia pages where the anchor text of the link closely matches the title of the target Wikipedia page. If we think of each page on Wikipedia as an entity (an idea we’ve discussed before), then the anchor text can be thought of as a mention of the corresponding entity.

Dataset	Number of Mentions	Number of Entities
Bentivogli et al. (data) (2008)	43,704	709
Day et al. (2008)	less than 55,000	3,660
Artiles et al. (data) (2010)	57,357	300
Wikilinks Corpus	40,323,863	2,933,659

What might you do with this data? Well, we’ve already written one ACL paper on cross-document co-reference (and received lots of requests for the underlying data, which partly motivates this release). And really, we look forward to seeing what you are going to do with it! But here are a few ideas:

Look into coreference -- when different mentions mention the same entity -- or entity resolution -- matching a mention to the underlying entity
Work on the bigger problem of cross-document coreference, which is how to find out if different web pages are talking about the same person or other entity
Learn things about entities by aggregating information across all the documents they’re mentioned in
Type tagging tries to assign types (they could be broad, like person, location, or specific, like amusement park ride) to entities. To the extent that the Wikipedia pages contain the type information you’re interested in, it would be easy to construct a training set that annotates the Wikilinks entities with types from Wikipedia.
Work on any of the above, or more, on subsets of the data. With existing datasets, it wasn’t possible to work on just musicians or chefs or train stations, because the sample sizes would be too small. But with 10 million Web pages, you can find a decent sampling of almost anything.

Gory Details

How do you actually get the data? It’s right here: Google’s Wikilinks Corpus. Tools and data with extra context can be found on our partners’ page: UMass Wiki-links. Understanding the corpus, however, is a little bit involved.

For copyright reasons, we cannot distribute actual annotated web pages. Instead, we’re providing an index of URLs, and the tools to create the dataset, or whichever slice of it you care about, yourself. Specifically, we’re providing:

The URLs of all the pages that contain labeled mentions, which are links to English Wikipedia
The anchor text of the link (the mention string), the Wikipedia link target, and the byte offset of the link for every page in the set
The byte offset of the 10 least frequent words on the page, to act as a signature to ensure that the underlying text hasn’t changed -- think of this as a version, or fingerprint, of the page
Software tools (on the UMass site) to: download the web pages; extract the mentions, with ways to recover if the byte offsets don’t match; select the text around the mentions as local context; and compute evaluation metrics over predicted entities.

The format looks like this:

URL http://1967mercurycougar.blogspot.com/2009_10_01_archive.html

MENTION Lincoln Continental Mark IV 40110 http://en.wikipedia.org/wiki/Lincoln_Continental_Mark_IV

MENTION 1975 MGB roadster 41481 http://en.wikipedia.org/wiki/MG_MGB

MENTION Buick Riviera 43316 http://en.wikipedia.org/wiki/Buick_Riviera

MENTION Oldsmobile Toronado 43397 http://en.wikipedia.org/wiki/Oldsmobile_Toronado

TOKEN seen 58190

TOKEN crush 63118

TOKEN owners 69290

TOKEN desk 59772

TOKEN relocate 70683

TOKEN promote 35016

TOKEN between 70846

TOKEN re 52821

TOKEN getting 68968

TOKEN felt 41508

We’d love to hear what you’re working on, and look forward to what you can do with 40 million mentions across over 10 million web pages!

Thanks to our collaborators at UMass Amherst: Sameer Singh and Andrew McCallum.

Applauding the White House Memorandum on Open Access

2013-02-25T14:00:00.000-08:00

Posted by Alfred Spector, Vice President of Research and Special Initiatives

Last week the Obama Administration issued a Memorandum that could vastly increase the impact of federally funded research on innovation and the economy. Entrepreneurs, businesses, students, patients, researchers, and the public will soon have digital access to the wealth of research publications and data funded by Federal agencies. We're excited that this important work will be made more broadly accessible.

This memorandum directs federal agencies with annual research and development budgets of $100 million or more to open up access to the crucial results of publicly funded research (including both unclassified articles and data). These agencies will need to provide the public with free and unlimited online access to the results of that research after a guideline 12 month embargo period. Before last week only one agency, the National Institutes of Health, had a public research access policy.

The federal government funds tens of billions of dollars in research each year through agencies like the National Science Foundation, National Institutes of Health, and the Department of Energy. These investments are intended to advance science, accelerate innovation, grow our economy, and improve the lives of all Americans and members of the public. Opening this research up to the public will accelerate these goals.

Federal investment in research and development only pays off if it has an impact. Researchers, businesses, policymakers, entrepreneurs, and the public need to be able to access and use the knowledge contained in the articles and data generated by those funds. Making the results of scholarly research accessible and reusable in digital form is one important way to increase the impact of existing taxpayer investments.

Google Research Awards: Winter, 2013

2013-02-22T09:00:00.000-08:00

Posted by Maggie Johnson, Director of Education & University Relations

Another round of the Google Research Awards has just been completed. This is our bi-annual open call for proposals on a variety of computer science-related topics, including systems, machine perception, natural language processing, security and many others. Our grants cover tuition and travel for a graduate student and provides faculty and students the opportunity to work directly with Google scientists and engineers.

This round, we received almost 600 proposals from 46 different countries. After expert reviews and committee discussions, we decided to fund 102 projects. The subject areas that received the highest level of support were human-computer interaction, machine learning, and mobile. In addition, 22% of the funding was awarded to universities outside the U.S.

Google’s University Relations funding falls into three categories. The first is the Google Research Award program which funds new faculty and innovative projects, or helps faculty get a new research program off the ground. We fund over 200 projects annually through this program. We feel this is a great way for Google to support a large number of faculty and projects, and it helps us keep a pulse on what’s going on in academic computer science research.

The second category of funding goes toward more focused, longer-term projects, where we collaborate closely on projects of mutual interest. Our PhD Fellowship program is also a part of our focused program strategy. The third category goes toward new programs and initiatives, and to the development of research and education in emerging countries.

Congratulations to the well-deserving recipients of this round’s awards. If you are interested in applying for the next round (deadline is April 15), please visit our website for more information.

Mobile interaction research at Google

2013-02-15T09:00:00.000-08:00

Posted by Xiaojun Bi, Ciprian Chelba, Tom Ouyang, Kurt Partridge and Shumin Zhai

Google takes a hybrid approach to research - research happens across the entire company, and affects everything we do. As one example, we have a group that focuses on mobile interaction research. With research backgrounds in human-computer interaction, machine learning, statistical language modeling, and ubicomp, the group has focused on both foundational work and feature innovations for smart touchscreen keyboards. These innovations help us make things like typing messages on your Android device easier for hundreds of millions of people each day.

We work closely with world-class engineers, designers, product managers, and UX researchers across the company, which enables us to rapidly integrate the fruits of our research into the Android platform. The first major integration was the launch of Gesture Typing in Android 4.2.

Rapidly developed from basic concepts up to product code, and built on years of Android platform groundwork on input method editors (IME) and input method framework (IMF), Gesture Typing uses novel algorithms to dynamically infer and display the user’s intended word right at the fingertip. Often the intended word is displayed even before the user has finished gesturing--creating a magical experience for the user. Seamlessly integrated with touch tapping, Gesture Typing also supports two-thumb use.

It is exciting and rewarding to do research inside a product team that enforces engineering and user experience discipline. At the same time, we as researchers also contribute to the broader research community; publication, whether in the form of papers, code, or data, bind a research community together. The following papers are based on our work over the last year, some with bright and hardworking student interns:

Octopus: Evaluating Touchscreen Keyboard Correction and Recognition Algorithms via “Remulation”
by Xiaojun Bi, Shiri Azenkot (U. of Washington), Kurt Partridge, Shumin Zhai
CHI 2013, in press (link to come)

FFitts Law: Modeling Finger Touch with Fitts’ Law
by Xiaojun Bi, Yang Li, Shumin Zhai
CHI 2013, in press (link to come)

Making Touchscreen Keyboards Adaptive to Keys, Hand Postures, and Individuals - A Hierarchical Spatial Backoff Model Approach
by Ying Yin (MIT), Tom Ouyang, Kurt Partridge, Shumin Zhai
CHI 2013, in press (link to come)

Bimanual gesture keyboard.
by Xiaojun Bi, Ciprian Chelba, Tom Ouyang, Kurt Partridge, and Shumin Zhai
UIST 2012

Touch Behavior with Different Postures on Soft Smart Phone Keyboards
by Shiri Azenkot (U. Washington) and Shumin Zhai
MobileHCI 2012

Research Projects on Google App Engine

2013-02-12T10:00:00.000-08:00

By Andrea Held, Program Manager, Google University Relations

Cross-posted on the Google Developers Blog

Last spring Google University Relations announced an open call for proposals for Google App Engine Research Awards. We invited academic researchers to use Google App Engine for research experiments and analysis, encouraging them to take advantage of the platform’s ability to manage heavy data loads and run large-scale applications. Submissions included exciting proposals in various subject areas from mathematics, computer vision, bioinformatics, climate and computer science. We have selected seven projects that have the potential to impact people’s lives by making community seismic networks affordable, creating individualized DNA profiles, collecting useful local data through social media, and by understanding global climate trends, just to mention a few.

We have donated $60,000 in Google App Engine credits to each of these projects recognizing the innovation and vision of the Principal Investigator and his collaborators. Congratulations to all of them!

Below is a brief introduction of the award recipients and their research. We look forward to learning about their progress and will share the news right here. Stay tuned!

K. Mani Chandy, Simon Ramo Professor and Professor of Computer Science, California Institute of Technology
Project title: Cloud-based Event Detection for Sense and Response
Description and research goals: We developed an App Engine-based sense and response platform for the Community Seismic Network (CSN) project. CSN's goals include measuring seismic events with finer spatial resolution than previously possible and developing a low-cost alternative to traditional seismic networks, which have high capital costs for acquisition, deployment, and ongoing maintenance. We are working on generalizing our implementation and experience to provide a system for other members of the community to use in future sense and response applications.

Lawrence Chung, Associate Professor, The University of Texas at Dallas
Project title: Google App Engine: Software Benchmark and Simulation Forecaster
Description and research goals: An important consideration before migrating a company’s application software to Google App Engine is performance and operating cost.
Similarly, the Google App Engine organization would want to estimate Google App Engine’s resource usage and how well the particular resource allocation will meet the performance and cost requirements, as in the service level agreements (SLAs). This research project aims to develop a Google App Engine simulation forecaster - a tool for estimating the performance and cost of software operating on Google App Engine, and produce some important operational benchmark.

Julian Gough, Professor, University of Bristol, UK
Project title: Personalised DNA Analysis
Description and research goals: Personal genomics is still in its infancy and although it is easy, and relatively cheap to obtain personal genotype data, the available analysis is not personalised; it is the same for everybody. In this project we will set up a service powered by App Engine that provides personal DNA analysis specific to each individual. The proposed service does not focus on disease, but on identifying aspects of a healthy person that make them unique. What does your genome tell you about yourself that makes you special?

Ramesh Raskar, PhD, MIT Media Lab; Dr. Erick Baptista Passos, IFPI (Federal Institute of Technology, Brazil)
Project title: Vision Blocks
Description and research goals: Vision Blocks is a research project that aims to make computer vision available to everyone. Its primary goal is to develop tools for delivering computer vision to masses through an extensible visual programming language and an online application building and sharing system. We have a prototype HTML5 client that already performs computer vision tasks locally. Our goals for the next iterations include integration with App Engine for preprocessing of video streaming platforms.

Norman Sadeh, Professor, Director of Mobile Commerce Lab, School of
Computer Science, Carnegie Mellon University; Justin Cranshaw, PhD student, School of Computer Science, Hazim Almuhimedi, PhD student, School of Computer Science
Project title: Mapping the Dynamics of a City & Nudging Twitter Users
Description and research goals: We are working on two research
projects. The first is Livehoods in which we take a computational approach to analyzing large-scale trends in the ways people move through dense urban areas. Our goal is to find algorithmic ways of uncovering local collective knowledge about the city using social media. The second is “Nudging Twitter Users” in which we utilize quantitative and qualitative approaches to understand why people post things on Twitter they wish they had not, and also to understand the nature of these posts. Our objective is to develop tools that help nudge users to reduce the likelihood of those posts.

William Stein, Professor of Mathematics, University of Washington
Project title: Sage: Creating a Viable Free Open Source Alternative to Magma, Maple, Matlab, and Mathematica
Description and research goals: The goal is to create a highly scalable and resilient website through which very large numbers of people can use Sage. This is the next step.

Enrique Vivoni, Associate Professor, Hydrologic Science, Engineering & Sustainability, Arizona State University; Dr. Giuseppe Mascaro, Research Engineer; Jyothi Marupila, Graduate Student; Mario A. Rodriguez, Software Engineer
Project title: Cloud Computing-Based Visualization and Access of Global Climate Data Sets
Description and research goals: Our project uses Google App Engine for analyzing global climate data within the Google Maps API. At this stage, we are able to generate loads from the Global Land Data Assimilation Systems (GLDAS) climate model into the Google App Engine datastore. We select the climate variable to be used and aggregate data at different spatial resolutions. We are using Google App Engine Task Queue API to load large files. For the presentation layer, we are using Django templates to integrate the display of many data points in the Google Maps API. Our objective is to provide scientific data on global climate trends by allowing map-based queries and summaries at the appropriate resolutions. Sample Map

Currently, no further rounds for Google App Engine Research Awards have been planned. We will announce any updates to the program on our website.

Advanced Power Searching with Google -- Registration Opens Today

2013-01-10T08:45:00.000-08:00

Posted by Daniel Russell, Über Tech Lead for Search Quality and User Happiness

Cross-posted at Inside Search Blog

What historic cafe inspired a poem by a Nobel Laureate? In the last three barista world championships, which winners did not use beans from their home country? If you were preparing a blog post on “Curious Trivia of Coffee Culture,” how would you find the answers to these questions? What else would you discover? Now you can sign up for our Advanced Power Searching with Google online course and find out.

Building on Power Searching with Google, Advanced Power Searching with Google helps you gain a deeper understanding of how to become a better researcher. You will solve complex search challenges similar to those I pose in my blog, or a Google a Day, and explore Google’s advanced search tools not covered in the first class.

Oftentimes the most intriguing questions invite you to explore beyond the initial answer, and there’s no single correct path to get there. When looking for questions that can’t be solved with a single query, “search” can quickly turn into “research.” Google Search offers a palette of tools to help you dive deeper into the web of knowledge.

Visit www.powersearchingwithgoogle.com to learn more about our online search courses, and review our search tips on the Power Searching with Google Quick Reference Guide. Advanced Power Searching begins on January 23 and ends on February 8th.

Conference Report: Workshop on Internet and Network Economics (WINE) 2012

2012-12-19T08:00:00.000-08:00

Posted by Vahab Mirrokni, Research Scientist, Google Research New York

Google regularly participates in the WINE conference: Workshop on Internet & Network Economics. WINE’12 just happened last week in Liverpool, UK, where there is a strong economics and computation group. WINE provides a forum for researchers across various disciplines to examine interesting algorithmic and economic problems of mutual interest that have emerged from the Internet over the past decade. For Google, the exchange of ideas at this selective workshop has resulted in innovation and improvements in algorithms and economic auctions, such as our display ad allocation.

Googlers co-authored three papers this year; here’s a synopsis of each, as well as some highlights from invited talks at the conference:

Budget Optimization for Online Campaigns with Positive Carryover Effects
This paper first argues that ad impressions may have some long-term impact on user behaviour, and refers to an older WWW ’10 paper. Based on this motivation, the paper presents a scalable budget optimization algorithm for online advertising campaigns in the presence of Markov user behavior. In such settings, showing an ad to a user may change their actions in the future through a Markov model, and the probability of conversion for the ad does not only depend on the last ad shown, but also on earlier user activities. The main purpose of the paper is to give a simpler algorithm to solve a constrained Markov Decision Process, and confirms this easier solution via simulations on some advertising data sets. The paper was written when Nikolay Archak, a PhD student at NYU business school, was an intern with the New York market algorithms research team.

On Fixed-Price Marketing for Goods with Positive Network Externalities
This paper presents an approximation algorithm for marketing “networked goods” and services that exhibit positive network externalities - for example, is the buyer's value for the goods or service influenced positively by other buyers owning the goods or using the service? Such positive network externalities arise in many products like operating systems or smartphone services. While most of previous research is concerned with influence maximization, this paper attempts to identify a revenue maximizing marketing strategy for such networked goods, as follows: The seller selects a set (S) of buyers and gives them the goods for free, then sets a fixed per-unit price (p), at which other consumers can buy the item. The strategy is consistent with practice and is easy to implement. The authors use ideas from non-negative submodular maximization to find the optimal revenue maximizing fixed-price marketing strategy.

The AND-OR game: Equilibrium Characterization
Yishay Mansour, former Visiting Faculty in Google New York, presented the results; he first argued that the existence and uniqueness of market equilibria is only known for markets with divisible goods and concave or convex utilities. Then he described a simple market AND-OR game for divisible goods. To my surprise, he showed a class of mixed strategies are basically the unique set of randomized equilibria for this market (up to minor changes in the outcome). At the end, Yishay challenged the audience to give such characterization for more general markets with indivisible goods.

Kamal Jain of Ebay Research gave an interesting talk about mechanism design problems, inspired by application in companies like Ebay and Google. In one part, Kamal proposed "coopetitive ad auctions" for settings in which the auctioneer runs an auction among buyers who may cooperate with some advertisers, and at the same time compete with others for sealing advertising slots. He gave context around "product ads"; for example, a retailer like Best Buy may cooperate with a manufacturer like HP to put out a product ad for an HP computer sold at Best Buy. Kamal argued that if the cooperation is not an explicit part of the auction, an advertiser may implicitly end up competing with itself, thus decreasing the social welfare. By making the cooperation an explicit part of the auction, he was able to design a mechanism with better social welfare and revenue properties, compared to both first-price and second-price auctions. Kamal also discussed optimal mechanisms for intermediaries, and “surplus auctions” to avoid cyclic bidding behavior resulted from running naive variants of first-price auctions in repeated settings.

David Parkes of Harvard University discussed techniques to combine mechanism design with machine learning or heuristic search algorithms. At one point David discussed how to implement a branch-and-bound search algorithm in a way that results in a "monotone" allocation rule, so that if we implement a VCG-type allocation and pricing rule based on this allocation algorithm, the resulting mechanism becomes truthful. David also presented ways to compute a set of prices for any allocation, respecting incentive compatibility constraints as much as possible. Both of these topics appeared in ACM EC 2012 papers that he had co-authored.

At the business meeting, there was a proposal to change the title of the conference from “workshop” to “conference” or “symposium” to reflect its fully peer-reviewed and archival nature, keeping the same acronym of WINE. (Changing the title to “Symposium on the Web, Internet, and Network Economics” was rejected: SWINE!) WINE 2013 will be held at Harvard University in Boston, MA, and we look forward to reconnecting with fellow researchers in the field and continuing to nurture new developments and research topics.

Using online courses in Spain to teach entrepreneurship

2012-12-18T13:00:00.000-08:00

Posted by Francisco Ruiz Anton, Policy Manager, Google Spain

Cross-posted with the Policy by the Numbers Blog

At the end of the third quarter in 2012, roughly 25% of adults in Spain were out of work. More than half of adults under 24 years old are unemployed. Recent graduates and young adults preparing to enter the workforce face the toughest job market in decades.

The Internet presents an opportunity for growth and economic development. According to recent research, more than 100,000 jobs in Spain originate from the Internet and it directly contributes to the GDP with 26.7 billion euros (2.5%). That impact that could triple by 2015 under the right conditions.

One of those conditions is making high-quality education accessible, echoed by a recent OECD report on the youth labor market in Spain. This is no easy task. University degrees are in high demand, straining the reach of our existing institutions.

The web has become a way for learners to develop new skills when traditional institutions aren’t an option. Recent courses on platforms like Udacity, Coursera and edX have seen hundreds of thousands of students enroll and participate in courses taught by prestigious professors and lecturers.

Google is partnering with numerous organizations and universities in Spain to organize UniMOOC, an online course intended to educate citizens in Spain and the rest of the Spanish-speaking world about entrepreneurship. It was built with Course Builder, Google’s new open source toolkit for constructing online courses.

To date nearly 10,000 students have registered for the course, over two-thirds of them from Spain and one-third from 93 countries. It recently won an award for the “Most innovative project” in 2012 from the newspaper El Mundo.

Spain’s situation is not entirely unique in Europe. Policymakers across the continent are asking themselves how best to create economic opportunity for their citizens, and how to ensure that their best and brightest students are on a path toward financial success. Our hope is that the people taking this course will be more empowered with the right skills and tools to start their own businesses that can create jobs. They will push not only Spain, but Europe and the rest of the world towards economic recovery and growth.

The course is still running, and you’re able to join today.

Millions of Core-Hours Awarded to Science

2012-12-17T09:00:00.000-08:00

Posted by Andrea Held, Program Manager, University Relations

In 2011 Google University Relations launched a new academic research awards program, Google Exacycle for Visiting Faculty, offering up to one billion core-hours to qualifying proposals. We were looking for projects that would consume 100M+ core-hours each and be of critical benefit to society. Not surprisingly, there was no shortage of applications.

Since then, the following seven scientists have been working on-site at Google offices in Mountain View and Seattle. They are here to run large computing experiments on Google’s infrastructure to change the future. Their projects include exploring antibiotic drug resistance, protein folding and structural modelling, drug discovery, and last but not least, the dynamic universe.

Today, we would like to introduce the Exacycle award recipients and their work. Please stay tuned for updates next year.

Simulating a Dynamic Universe with the Large Synoptic Sky Survey
Jeff Gardner, University of Washington, Seattle, WA
Collaborators: Andrew Connolly, University of Washington, Seattle, WA, and John Peterson, Purdue University, West Lafayette, IN

Research subject: The Large Synoptic Survey Telescope (LSST) is one of the most ambitious astrophysical research programs ever undertaken. Starting in 2019, the LSST’s 3.2 Gigapixel camera will repeatedly survey the southern sky, generating tens of petabytes of data every year. The images and catalogs from the LSST have the potential to transform both our understanding of the universe and the way that we engage in science in general.
Exacycle impact: In order to design the telescope to yield the best possible science, the LSST collaboration has undertaken a formidable computational campaign to simulate the telescope itself. This will optimize how the LSST surveys the sky and provide realistic datasets for the development of analysis pipelines that can operate on hundreds of petabytes. Using Exacycle, we are reducing the time required to simulate one night of LSST observing, roughly 5 million images, from 3 months down to a few days. This rapid turnaround will enable the LSST engineering teams to test new designs and new algorithms with unprecedented precision, which will ultimately lead to bigger and better science from the LSST.

Designing and Defeating Antibiotic Drug Resistance
Peter Kasson, Assistant Professor, Departments of Molecular Physiology and Biological Physics and of Biomedical Engineering, University of Virginia

Research subject: Antibiotics have made most bacterial infections routinely treatable. As antibiotic use has become common, bacterial resistance to these drugs has also increased. Recently, some bacteria have arisen that are resistant to almost all antibiotics. We are studying the basis for this resistance, in particular the enzyme that acts to break down many antibiotics. Identifying the critical changes required for pan-resistance will aid surveillance and prevention; it will also help elucidate targets for the development of new therapeutic agents.
Exacycle impact: Exacycle allows us to simulate the structure and dynamics of several thousand enzyme variants in great detail. The structural differences between enzymes from resistant and non-resistant bacteria are subtle, so we have developed methods to compare structural "fingerprints" of the enzymes and identify distinguishing characteristics. The complexity of this calculation and large number of potential bacterial sequences mean that this is a computationally intensive task; the massive computing power offered by Exacycle in combination with some novel sampling strategies make this calculation tractable.

Sampling the conformational space of G protein-coupled receptors
Kai Kohlhoff, Research Scientist at Google
Collaborators: Research labs of Vijay Pande and Russ Altman at Stanford University

Research subject: G protein-coupled receptors (GPCRs) are proteins that act as signal transducers in the cell membrane and influence the response of a cell to a variety of external stimuli. GPCRs play a role in many human diseases, such as asthma and hypertension, and are well established as a primary drug target.
Exacycle impact: Exacycle let us perform many tens of thousands of molecular simulations of membrane-bound GPCRs in parallel using the Gromacs software. With MapReduce, Dremel, and other technologies, we analyzed the 100s of Terabytes of generated data and built Markov State Models. The information contained in these models can help scientists design drugs that have higher potency and specificity than those presently available.
Results: Our models let us explore kinetically meaningful receptor states and transition rates, which improved our understanding of the structural changes that take place during activation of a signaling receptor. In addition, we used Exacycle to study the affinity of drug molecules when binding to different receptor states.

Modeling transport through the nuclear pore complex
Daniel Russel, post doc in structural biology, University of California, San Francisco

Research subject: Our goal is to develop a predictive model of transport through the nuclear pore complex (NPC). Developing the model requires understanding how the behavior of the NPC varies as we change the parameters governing the components of the system. Such a model will allow us to understand how transportins, the unstructured domains and the rest of the cellular milieu, interact to determine efficiency and specificity of macromolecular transport into and out of the nucleus.
Exacycle impact: Since data describing the microscopic behavior of most parts of the nuclear transport process is incomplete and contradictory, we have to explore a larger parameter space than would be feasible with traditional computational resources.
Status: We are currently modeling various experimental measurements of aspects of the nuclear transport process. These experiments range from simple ones containing only a few components of the transport process to measurements on the whole nuclear pore with transportins and cellular milieu.

Large scale screening for new drug leads that modulate the activity of disease-relevant proteins
James Swetnam, Scientific Software Engineer, drugable.org, NYU School of Medicine
Collaborators: Tim Cardozo, MD, PhD - NYU School of Medicine.

Research subject: We are using a high throughput, CPU-bound procedure known as virtual ligand screening to ‘dock’, or produce rough estimates of binding energy, for a large sample of bioactive chemical space to the entirety of known protein structures. Our goal is the first computational picture of how bioactive chemistry with therapeutic potential can affect human and pathogen biology.
Exacycle Impact: Typically, using our academic lab’s resources, we could screen a few tens of thousands of compounds against a single protein to try to find modulators of its function. To date, Exacycle has enabled us to screen 545,130 compounds against 8,535 protein structures that are involved in important and underserved diseases as cancer, diabetes, malaria, and HIV to look for new leads towards future drugs.
Status: We are currently expanding our screens to an additional 206,190 models from
ModBase. We aim to have a public dataset for the research community in the first half of 2013.

Protein Structure Prediction and Design
Michael Tyka, Research Fellow, University of Washington, Seattle, WA

Research subject: The precise relationship between the primary sequence and the three dimensional structure of proteins is one of the unsolved grand challenges of computational biochemistry. The Baker Lab has made significant progress in recent years by developing more powerful protein prediction and design algorithms using the Rosetta Protein Modelling suite.
Exacycle impact: Limitations in the accuracy of the physical model and lack of sufficient computational power have prevented solutions to broader classes of medically relevant problems. Exacycle allows us to improve model quality by conducting large parameter optimization sweeps with a very large dataset of experimental protein structural data. The improved energy functions will benefit the entire theoretical protein research community.

We are also using Exacycle to conduct simultaneous docking and one-sided protein design to develop novel protein binders for a number of medically relevant targets. For the first time, we are able to aggressively redesign backbone conformations at the binding site. This allows for a much greater flexibility in possible binding shapes but also hugely increases the space of possibilities that have to be sampled. Very promising designs have already been found using this method.

Continuing the quest for future computer scientists with CS4HS

2012-12-13T09:00:00.000-08:00

Erin Mindell, Program Manager, Google Education

Computer Science for High School (CS4HS) began five years ago with a simple question: How can we help create a much needed influx of CS majors into universities and the workforce? We took our questions to three of our university partners--University of Washington, Carnegie Mellon, and UCLA--and together we came up with CS4HS. The model was based on a “train the trainer” technique. By focusing our efforts on teachers and bringing them the skills they need to implement CS into their classrooms, we would be able to reach even more students. With grants from Google, our partner universities created curriculum and put together hands-on, community-based workshops for their local area teachers.

Since the initial experiment, CS4HS has exploded into a worldwide program, reaching more than 4,000 teachers and 200,000 students either directly or indirectly in more than 34 countries. These hands-on, in-person workshops are a hallmark of our program, and we will continue to fund these projects going forward. (For information on how to apply, please see our website.) The success of this popular program speaks for itself, as we receive more quality proposals each year. But success comes at a price, and we have found that the current format of the workshops is not infinitely scalable.

This is where Research at Google comes in. This year, we are experimenting with a new model for CS4HS workshops. By harnessing the success of online courses such as Power Searching with Google, and utilizing open-source platforms like the one found in Course Builder, we are hoping to put the “M” in “MOOC” and reach a broader audience of educators, eager to learn how to teach CS in their classrooms.

For this pilot, we are looking to sponsor two online workshops, one that is geared toward CS teachers, and one that is geared toward CS for non-CS teachers to go live in 2013. This is a way for a university (or several colleges working together) to create one incredible workshop that has the potential to reach thousands of enthusiastic teachers. Just as with our in-person workshops, applications will be open to college, university, and technical schools of higher learning only, as we depend on their curriculum expertise to put together the most engaging programs. For this pilot, we will be looking for MOOC proposals in the US and Canada only.

We are really excited about the possibilities of this new format, and we are looking for quality applications to fund. While applications don’t have to run on our Course Builder platform, we may be able to offer some additional support to funded projects that do. If you are interested in joining our experiment or just learning more, you can find information on how to apply on our CS4HS website (or click here).

Applications are open until February 16, 2013; we can’t wait to see what you come up with. If you have questions, please email us at cs4hs@google.com.

Large Scale Language Modeling in Automatic Speech Recognition

2012-10-31T09:10:00.000-07:00

Posted by Ciprian Chelba, Research Scientist

At Google, we’re able to use the large amounts of data made available by the Web’s fast growth. Two such data sources are the anonymized queries on google.com and the web itself. They help improve automatic speech recognition through large language models: Voice Search makes use of the former, whereas YouTube speech transcription benefits significantly from the latter.

The language model is the component of a speech recognizer that assigns a probability to the next word in a sentence given the previous ones. As an example, if the previous words are “new york”, the model would assign a higher probability to “pizza” than say “granola”. The n-gram approach to language modeling (predicting the next word based on the previous n-1 words) is particularly well-suited to such large amounts of data: it scales gracefully, and the non-parametric nature of the model allows it to grow with more data. For example, on Voice Search we were able to train and evaluate 5-gram language models consisting of 12 billion n-grams, built using large vocabularies (1 million words), and trained on as many as 230 billion words.

The computational effort pays off, as highlighted by the plot above: both word error rate (a measure of speech recognition accuracy) and search error rate (a metric we use to evaluate the output of the speech recognition system when used in a search engine) decrease significantly with larger language models.

A more detailed summary of results on Voice Search and a few YouTube speech transcription tasks (authors: Ciprian Chelba, Dan Bikel, Maria Shugrina, Patrick Nguyen, Shankar Kumar) presents our results when increasing both the amount of training data, and the size of the language model estimated from such data. Depending on the task, availability and amount of training data used, as well as language model size and the performance of the underlying speech recognizer, we observe reductions in word error rate between 6% and 10% relative, for systems on a wide range of operating points.

Cross-posted with the Research at Google G+ Page

Ngram Viewer 2.0

2012-10-18T07:09:00.000-07:00

Posted by Jon Orwant, Engineering Manager

Since launching the Google Books Ngram Viewer, we’ve been overjoyed by the public reception. Co-creator Will Brockman and I hoped that the ability to track the usage of phrases across time would be of interest to professional linguists, historians, and bibliophiles. What we didn’t expect was its popularity among casual users. Since the launch in 2010, the Ngram Viewer has been used about 50 times every minute to explore how phrases have been used in books spanning the centuries. That’s over 45 million graphs created, each one a glimpse into the history of the written word. For instance, comparing flapper, hippie, and yuppie, you can see when each word peaked:

Meanwhile, Google Books reached a milestone, having scanned 20 million books. That’s approximately one-seventh of all the books published since Gutenberg invented the printing press. We’ve updated the Ngram Viewer datasets to include a lot of those new books we’ve scanned, as well as improvements our engineers made in OCR and in hammering out inconsistencies between library and publisher metadata. (We’ve kept the old dataset around for scientists pursuing empirical, replicable language experiments such as the ones Jean-Baptiste Michel and Erez Lieberman Aiden conducted for our Science paper.)

At Google, we’re also trying to understand the meaning behind what people write, and to do that it helps to understand grammar. Last summer Slav Petrov of Google’s Natural Language Processing group and his intern Yuri Lin (who’s since joined Google full-time) built a system that identified parts of speech—nouns, adverbs, conjunctions and so forth—for all of the words in the millions of Ngram Viewer books. Now, for instance, you can compare the verb and noun forms of “cheer” to see how the frequencies have converged over time:

Some users requested the ability to combine Ngrams, and Googler Matthew Gray generalized that notion into what we’re calling Ngram compositions: the ability to add, subtract, multiply, and divide Ngram counts. For instance, you can see how “record player” rose at the expense of “Victrola”:

Our info page explains all the details about this curious notion of treating phrases like components of a mathematical expression. We’re guessing they’ll only be of interest to lexicographers, but then again that’s what we thought about Ngram Viewer 1.0.

Oh, and we added Italian too, supplementing our current languages: English, Chinese, Spanish, French, German, Hebrew, and Russian. Buon divertimento!

ReFr: A New Open-Source Framework for Building Reranking Models

2012-10-04T13:45:00.000-07:00

Posted by Dan Bikel and Keith Hall, Research Scientists at Google

We are pleased to announce the release of an open source, general-purpose framework designed for reranking problems, ReFr (Reranker Framework), now available at: http://code.google.com/p/refr/.

Many types of systems capable of processing speech and human language text produce multiple hypothesized outputs for a given input, each with a score. In the case of machine translation systems, these hypotheses correspond to possible translations from some sentence in a source language to a target language. In the case of speech recognition, the hypotheses are possible word sequences of what was said derived from the input audio. The goal of such systems is usually to produce a single output for a given input, and so they almost always just pick the highest-scoring hypothesis.

A reranker is a system that uses a trained model to rerank these scored hypotheses, possibly inducing a different ranked order. The goal is that by employing a second model after the fact, one can make use of additional information not available to the original model, and produce better overall results. This approach has been shown to be useful for a wide variety of speech and natural language processing problems, and was the subject of one of the groups at the 2011 summer workshop at Johns Hopkins’ Center for Language and Speech Processing. At that workshop, led by Professor Brian Roark of Oregon Health & Science University, we began building a general-purpose framework for training and using reranking models. The result of all this work is ReFr.

From the outset, we designed ReFr with both speed and flexibility in mind. The core implementation is entirely in C++, with a flexible architecture allowing rich experimentation with both features and learning methods. The framework also employs a powerful runtime configuration mechanism to make experimentation even easier. Finally, ReFr leverages the parallel processing power of Hadoop to train and use large-scale reranking models in a distributed computing environment.

EMEA Faculty Summit 2012

2012-10-02T12:15:00.002-07:00

Michel Benard, University Relations Manager

Last week we held our fifth Europe, Middle East and Africa (EMEA) Faculty Summit in London, bringing together 94 of EMEA’s foremost computer science academics from 65 universities representing 25 countries, together with more than 60 Googlers.

This year’s jam-packed agenda included a welcome reception at the Science Museum (plus a tour of the special exhibition: “Codebreaker - Alan Turing’s life and legacy”), a keynote on “Research at Google” by Alfred Spector, Vice President of Research and Special Initiatives and a welcome address by Nelson Mattos, Vice President of Engineering and Products in EMEA, covering Google’s engineering activity and recent innovations in the region.

The Faculty Summit is a chance for us to meet with academics in Computer Science and other areas to discuss the latest exciting developments in research and education, and to explore ways in which we can collaborate via our our University Relations programs.

The two and a half day program consisted of tech talks, break out sessions, a panel on online education, and demos. The program covered a variety of computer science topics including Infrastructure, Cloud Computing Applications, Information Retrieval, Machine Translation, Audio/Video, Machine Learning, User Interface, e-Commerce, Digital Humanities, Social Media, and Privacy. For example, Ed H. Chi summarized how researchers use data analysis to understand the ways users share content with their audiences using the Circle feature in Google+. Jens Riegelsberger summarized how UI design and user experience research is essential to creating a seamless experience on Google Maps. John Wilkes discussed some of the research challenges - and opportunities - associated with building, managing, and using computer systems at massive scale. Breakout sessions ranged from technical follow-ups on the talk topics to discussing ways to increase the presence of women in computer science.

We also held one-on-one sessions where academics and Googlers could meet privately and discuss topics of personal interest, such as how to develop a compelling research award proposal, how to apply for a sabbatical at Google or how to gain Google support for a conference in a particular research area.

The Summit provides a great opportunity to build and strengthen research and academic collaborations. Our hope is to drive research and education forward by fostering mutually beneficial relationships with our academic colleagues and their universities.

Running Continuous Geo Experiments to Assess Ad Effectiveness

2012-09-18T09:00:00.000-07:00

Posted by Jon Vaver, Research Scientist and Lizzy Van Alstine, Marketing Manager

Advertisers have a fundamental need to measure the effectiveness of their advertising campaigns. In a previous paper, we described the application of geo experiments to measuring the impact of advertising on consumer behavior (e.g. clicks, conversions, downloads). This method involves randomly assigning experimental units to control and test conditions and measuring the subsequent impact on consumer behavior. It is a practical way of incorporating the gold standard of randomized experiments into the analysis of marketing effectiveness. However, advertising decisions are not static, and the original method is most applicable to a one-time analysis. In a follow-up paper, we generalize the approach to accommodate periodic (ongoing) measurement of ad effectiveness.

In this expanded approach, the test and control assignments of each geographic region rotate across multiple test periods, and these rotations provide the opportunity to generate a sequence of measurements of campaign effectiveness. The data across test periods can also be pooled to create a single aggregate measurement of campaign effectiveness. These sequential and pooled measurements have smaller confidence intervals than measurements from a series of geo experiments with a single test period. Alternatively, the same confidence interval can be achieved with a reduced magnitude or duration of ad spend change, thereby lowering the cost of measurement. The net result is a better method for periodic and isolated measurement of ad effectiveness.

Power Searching with Google is back

2012-09-11T09:00:00.000-07:00

Posted by Dan Russell, Uber Tech Lead, Search Quality & User Happiness

If you missed Power Searching with Google a few months ago or were unable to complete the course the first time around, now’s your chance to sign up again for our free online course that aims to empower our users with the tools and knowledge to find what they’re looking for more quickly and easily.

The community-based course features six 50-minute classes along with interactive activities and the opportunity to hear from search experts and Googlers about how search works. Beginning September 24, you can take the classes over a two-week period, share what you learn with other students in a community forum, and complete the course assessments to earn a certificate of completion.

During the course’s first run in July, people told us how they not only liked learning about new features and more efficient ways to use Google, but they also enjoyed sharing tips and learning from one another through the forums and Hangouts. Ninety-six percent of people who completed the course also said they liked the format and would be interested in taking similar courses, so we plan to offer a suite of upcoming courses in the coming months, including Advanced Power Searching.

Stay tuned for further announcements on those upcoming courses, and don’t forget to register now for Power Searching with Google. You’ll learn about things like how to search by color, image, and time and how to solve harder trivia questions like our A Google a Day questions. We’ll see you when we start up in two weeks!

Helping the World to Teach

2012-09-11T08:30:00.000-07:00

Posted by Peter Norvig, Director of Research

In July, Research at Google ran a large open online course, Power Searching with Google, taught by search expert, Dan Russell. The course was successful, with 155,000 registered students. Through this experiment, we learned that Google technologies can help bring education to a global audience. So we packaged up the technology we used to build Power Searching and are providing it as an open source project called Course Builder. We want to make this technology available so that others can experiment with online learning.

The Course Builder open source project is an experimental early step for us in the world of online education. It is a snapshot of an approach we found useful and an indication of our future direction. We hope to continue development along these lines, but we wanted to make this limited code base available now, to see what early adopters will do with it, and to explore the future of learning technology. We will be hosting a community building event in the upcoming months to help more people get started using this software. edX shares in the open source vision for online learning platforms, and Google and the edX team are in discussions about open standards and technology sharing for course platforms.

We are excited that Stanford University, Indiana University, UC San Diego, Saylor.org, LearningByGivingFoundation.org, Swiss Federal Institute of Technology in Lausanne (EPFL), and a group of universities in Spain led by Universia, CRUE, and Banco Santander-Universidades are considering how this experimental technology might work for some of their online courses. Sebastian Thrun at Udacity welcomes this new option for instructors who would like to create an online class, while Daphne Koller at Coursera notes that the educational landscape is changing and it is exciting to see new avenues for teaching and learning emerge. We believe Google’s preliminary efforts here may be useful to those looking to scale online education through the cloud.

Along with releasing the experimental open source code, we’ve provided documentation and forums for anyone to learn how to develop and deploy an online course like Power Searching. In addition, over the next two weeks we will provide educators the opportunity to connect with the Google team working on the code via Google Hangouts. For access to the code, documentation, user forum, and information about the Hangouts, visit the Course Builder Open Source Project Page. To see what is possible with the Course Builder technology register for Google’s next version of Power Searching. We invite you to explore this brave new world of online learning with us.

Users love simple and familiar designs – Why websites need to make a great first impression

2012-08-29T12:01:00.000-07:00

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

I’m sure you’ve experienced this at some point: You click on a link to a website, and after a quick glance you already know you’re not interested, so you click ‘back’ and head elsewhere. How did you make that snap judgment? Did you really read and process enough information to know that this website wasn’t what you were looking for? Or was it something more immediate?

We form first impressions of the people and things we encounter in our daily lives in an extraordinarily short timeframe. We know the first impression a website’s design creates is crucial in capturing users’ interest. In less than 50 milliseconds, users build an initial “gut feeling” that helps them decide whether they’ll stay or leave. This first impression depends on many factors: structure, colors, spacing, symmetry, amount of text, fonts, and more.

In our study we investigated how users' first impressions of websites are influenced by two design factors:

Visual complexity -- how complex the visual design of a website looks
Prototypicality -- how representative a design looks for a certain category of websites

We presented screenshots of existing websites that varied in both of these factors -- visual complexity and prototypicality -- and asked users to rate their beauty.

The results show that both visual complexity and prototypicality play crucial roles in the process of forming an aesthetic judgment. It happens within incredibly short timeframes between 17 and 50 milliseconds. By comparison, the average blink of an eye takes 100 to 400 milliseconds.

And these two factors are interrelated: if the visual complexity of a website is high, users perceive it as less beautiful, even if the design is familiar. And if the design is unfamiliar -- i.e., the site has low prototypicality -- users judge it as uglier, even if it’s simple.

In other words, users strongly prefer website designs that look both simple (low complexity) and familiar (high prototypicality). That means if you’re designing a website, you’ll want to consider both factors. Designs that contradict what users typically expect of a website may hurt users’ first impression and damage their expectations. Recent research shows that negative product expectations lead to lower satisfaction in product interaction -- a downward spiral you’ll want to avoid. Go for simple and familiar if you want to appeal to your users’ sense of beauty.