Open Access for Publications

Posted by Alfred Spector, Vice President, Engineering

The Association for Computing Machinery (ACM) recently announced a new option for publication rights management, wherein researchers can choose to pay for the public to have perpetual open access to the publication. Google applauds this new option, and today we are announcing that we will pay the open access fees for all articles by Google researchers that are published in ACM journals. IEEE also has an open access option for some of its publications, and we also pay the open access fee for them and for publications in like organizations.

Google has always believed that by improving access to the world’s knowledge, we can help improve everyone’s lives. When it comes to scientific research, we have consistently said that open access to publications speeds up research, accelerates innovation, and helps grow the global economy.

Policies like ACM’s continue to demonstrate the sustainability of open access publishing. It will also provide better access to the papers that we write at Google. We encourage researchers everywhere to pursue open access options whenever publishing articles, and to continue to make publications available as widely as possible, within your rights.

Read More

Explore more with Mapping with Google

Posted by Tina Ornduff, Program Manager

In September 2012 we launched Course Builder, an open source learning platform for educators or anyone with something to teach, to create online courses. This was our experimental first step in the world of online education, and since then the features of Course Builder have continued to evolve. Mapping with Google, our latest MOOC, showcases new features of the platform.

From your own backyard all the way to Mount Everest, Google Maps and Google Earth are here to help you explore the world. You can learn to harness the world’s most comprehensive and accurate mapping tools by registering for Mapping with Google.

Mapping with Google is a self-paced, online course developed to help you better navigate the world around you by improving your use of the new Google Maps, Maps Engine Lite, and Google Earth. All registrants will receive an invitation to preview the new Google Maps.

Through a combination of video and text lessons, activities, and projects, you’ll learn to do much more than look up directions or find your house from outer space. Tell a story of your favorite locations with rich 3D imagery, or plot sights to see on your upcoming trip and share with your travel buddies. During the course, you’ll have the opportunity to learn from Google experts and collaborate with a worldwide community of participants, via Google+ Hangouts and a course forum.

Mapping with Google will be offered from June 10 - June 24, and you can choose whether to explore the features of Google Maps, Google Earth, or both. In addition, you’ll have the option to complete a project, applying the skills you’ve learned to earn a certificate. Visit g.co/mappingcourse to learn more and register today.

The world is a big place; we like to think that you can make it a bit more manageable and adventurous with Google’s mapping tools.

Read More

Syntactic Ngrams over Time

Posted by Yoav Goldberg, Professor at Bar Ilan University & Post-doc at Google 2011-2013

We are proud to announce the release of a very large dataset of counted dependency tree fragments from the English Books Corpus. This resource will help researchers, among other things, to model the meaning of English words over time and create better natural-language analysis tools. The resource is based on information derived from a syntactic analysis of the text of millions of English books.

Sentences in languages such as English have structure. This structure is called syntax, and knowing the syntax of a sentence is a step towards understanding its meaning. The process of taking a sentence and transforming it into a syntactic structure is called parsing. At Google, we parse a lot of text every day, in order to better understand it and be able to provide better results and services in many of our products.

There are many kinds of syntactic representations (you may be familiar with sentence diagramming), and at Google we've been focused on a certain type of syntactic representation called "dependency trees". Dependency-trees representation is centered around words and the relations between them. Each word in a sentence can either modify or be modified by other words. The various modifications can be represented as a tree, in which each node is a word.

For example, the sentence "we really like syntax" is analyzed as:



The verb "like" is the main word of the sentence. It is modified by a subject (denoted nsubj) "we", a direct object (denoted dobj) "syntax", and an adverbial modifier "really".

An interesting property of syntax is that, in many cases, one could recover the structure of a sentence without knowing the meaning of most of the words. For example, consider the sentence "the krumpets gnorked the koof with a shlap". We bet you could infer its structure, and tell that group of something which is called a krumpet did something called "gnorking" to something called a "koof", and that they did so with a "shlap".

This property by which you could infer the structure of the sentence based on various hints, without knowing the actual meaning of the words, is very useful. For one, it suggests that a even computer could do a reasonable job at such an analysis, and indeed it can! While still not perfect, parsing algorithms these days can analyze sentences with impressive speed and accuracy. For instance, our parser correctly analyzes the made-up sentence above.



Let's try a more difficult example. Something rather long and literary, like the opening sentence of One hundred years of solitude by Gabriel García Márquez, as translated by Gregory Rabassa:

Many years later, as he faced the firing squad, Colonel Aureliano Buendía was to remember that distant afternoon when his father took him to discover ice.



Pretty good for an automatic process, eh?

And it doesn’t end here. Once we know the structure of many sentences, we can use these structures to infer the meaning of words, or at least find words which have a similar meaning to each other.

For example, consider the fragments:
"order a XYZ"
"XYZ is tasty"
"XYZ with ketchup"
"juicy XYZ"

By looking at the words modifying XYZ and their relations to it, you could probably infer that XYZ is a kind of food. And even if you are a robot and don't really know what a "food" is, you could probably tell that the XYZ must be similar to other unknown concepts such as "steak" or "tofu".

But maybe you don't want to infer anything. Maybe you already know what you are looking for, say "tasty food". In order to find such tasty food, one could collect the list of words which are objects of the verb "ate", and are commonly modified by the adjective "tasty" and "juicy". This should provide you a large list of yummy foods.

Imagine what you could achieve if you had hundreds of millions of such fragments. The possibilities are endless, and we are curious to know what the research community may come up with. So we parsed a lot of text (over 3.5 million English books, or roughly 350 billion words), extracted such tree fragments, counted how many times each fragment appeared, and put the counts online for everyone to download and play with.

350 billion words is a lot of text, and the resulting dataset of fragments is very, very large. The resulting datasets, each representing a particular type of tree fragments, contain billions of unique items, and each dataset’s compressed files takes tens of gigabytes. Some coding and data analysis skills will be required to process it, but we hope that with this data amazing research will be possible, by experts and non-experts alike.

The dataset is based on the English Books corpus, the same dataset behind the ngram-viewer. This time there is no easy-to-use GUI, but we still retain the time information, so for each syntactic fragment, you know not only how many times it appeared overall, but also how many times it appeared in each year -- so you could, for example, look at the subjects of the word “drank” at each decade from 1900 to 2000 and learn how drinking habits changed over time (much more ‘beer’ and ‘coffee’, somewhat less ‘wine’ and ‘glass’ (probably ‘of wine’). There’s also a drop in ‘whisky’, and an increase in ‘alcohol’. Brandy catches on around 1930s, and start dropping around 1980s. There is an increase in ‘juice’, and, thankfully, some decrease in ‘poison’).

The dataset is described in details in this scientific paper, and is available for download here.

Read More

Launching the Quantum Artificial Intelligence Lab

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.

Read More

Two Googlers elected to the American Academy of Arts and Sciences

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.

Read More

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

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.

Read More

Advanced Power Searching with Google: Lessons Learned

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.

Read More