Exploring Computational Thinking

Posted by Elaine Kao, Education Program Manager

Over the past year, a group of California-credentialed teachers along with our own Google engineers came together to discuss and explore ideas about how to incorporate computational thinking into the K-12 curriculum to enhance student learning and build this critical 21st century skill in everyone.

What exactly is computational thinking? Well, that would depend on who you ask as there are several existing resources on the web that may define this term slightly differently. We define computational thinking (CT) as a set of skills that software engineers use to write the programs that underlay all of the computer applications you use every day. Specific CT techniques include:

• Problem decomposition: the ability to break down a problem into sub-problems
• Pattern recognition: the ability to notice similarities, differences, properties, or trends in data
• Pattern generalization: the ability to extract out unnecessary details and generalize those that are necessary in order to define a concept or idea in general terms
• Algorithm design: the ability to build a repeatable, step-by-step process to solve a particular problem

Given the increasing prevalence of technology in our day-to-day lives and in most careers outside of computer science, we believe that it is important to raise this base level of understanding in everyone.

To this end, we’d like to introduce you to a new resource: Exploring Computational Thinking. Similar to some of our other initiatives in education, including CS4HS and Google Code University, this program is committed to providing educators with access to our curriculum models, resources, and communities to help them learn more about CT, discuss it as a strategy for teaching and understanding core curriculum, as well as easily incorporate CT into their own curriculum, whether it be in math, science, language, history or beyond. The materials developed by the team reflect both the teachers’ expertise in pedagogy and K-12 curriculum as well as our engineers’ problem-solving techniques that are critical to our industry.

Prior to launching this program, we reached out to several educators and classrooms and had them try our materials. Here’s some of the feedback we received:

• CT as a strategy for teaching and student learning works well with many subjects, and can easily be incorporated to support the existing K-12 curriculum
• Our models help to call out the specific CT techniques and provide more structure around the topics taught by educators, many of who were already unknowingly applying CT in their classrooms
• Including programming exercises in the classroom can significantly enrich a lesson by both challenging the advanced students and motivating the students who have fallen behind
• Our examples provide educators with a means of re-teaching topics that students have struggled with in the past, without simply going through the same lesson that frustrated them before

To learn more about our program or access CT curriculum materials and other resources, visit us at www.google.com/edu/ect.

Google at the Conference on Empirical Methods in Natural Language Processing (EMNLP '10)

Posted by Slav Petrov, Research Scientist

The Conference on Empirical Methods in Natural Language Processing (EMNLP '10) was recently held at the MIT Stata Center in Massachusetts. Natural Language Processing is at the core of many of the things that we do here at Google. Googlers have therefore been traditionally part of this research community, participating as program committee members, paper authors and attendees.

At this year's EMNLP conference Google Fellow, Amit Singhal gave an invited keynote talk on "Challenges in running a commercial search engine" where he highlighted some of the exciting opportunities, as well as challenges, that Google is currently facing. Furthermore, Terry Koo (who recently joined Google), David Sontag (former Google PhD Fellowship recipient) and their collaborators from MIT received the Fred Jelinek Best Paper Award for their innovative work on syntactic parsing with the title "Dual Decomposition for Parsing with Non-Projective Head Automata".

Here is a complete list of the papers presented by Googlers at the conference:

• Dual Decomposition for Parsing with Non-Projective Head Automata (Fred Jelinek Best Paper Award) by Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag
• "Poetic" Statistical Machine Translation: Rhyme and Meter (see also here) by Dmitriy Genzel, Jakob Uszkoreit, and Franz Och
• Efficient Graph-Based Semi-Supervised Learning of Structured Tagging Models by Amarnag Subramanya, Slav Petrov, and Fernando Pereira
• Uptraining for Accurate Deterministic Question Parsing by Slav Petrov, Pi-Chuan Chang, Michael Ringgaard, and Hiyan Alshawi
• Self-training with Products of Latent Variable Grammars by Zhongqiang Huang, Mary Harper, and Slav Petrov

Kuzman Ganchev Receives Presidential Award from the Republic of Bulgaria

Posted by Slav Petrov, Research Scientist

We would like to congratulate Kuzman Ganchev for being the runner-up for the John Atanasoff award from the President of the Republic of Bulgaria. Kuzman recently joined our New York office as a research scientist, after completing his doctoral studies at the University of Pennsylvania.

The John Atanasoff award was established in 2003 and is given annually to a Bulgarian scientist under 35 for scientific or practical contributions to the development of computer and information technology worldwide and significant economic or social importance for Bulgaria. Kuzman received the award for his contributions to computational linguistics and machine learning. Kuzman is the co-author of more than 20 publications that have appeared in international conferences and journals.

Korean Voice Input -- Have you Dictated your E-Mails in Korean lately?

Posted by Mike Schuster & Kaisuke Nakajima, Google Research

Google Voice Search has been available in various flavors of English since 2008, in Mandarin and Japanese since 2009, in French, Italian, German and Spanish since June 2010 (see also in this blog post), and shortly after that in Taiwanese. On June 16th 2010, we took the next step by launching our Korean Voice Search system.

Korean Voice Search, by focusing on finding the correct web page for a spoken query, has been quite successful since launch. We have improved the acoustic models several times which resulted in significantly higher accuracy and reduced latency, and we are committed to improving it even more over time.

While voice search significantly simplifies input for search, especially for longer queries, there are numerous applications on any smartphone that could also benefit from general voice input, such as dictating an email or an SMS. Our experience with US English has taught us that voice input is as important as voice search, as the time savings from speaking rather than typing a message are substantial. Korean is the first non-English language where we are launching general voice input. This launch extends voice input to emails, SMS messages, and more on Korean Android phones. Now every text field on the phone will accept Korean speech input.

Creating a general voice input service had different requirements and technical challenges compared to voice search. While voice search was optimized to give the user the correct web page, voice input was optimized to minimize (Hangul) character error rate. Voice inputs are usually longer than searches (short full sentences or parts of sentences), and the system had to be trained differently for this type of data. The current system’s language model was trained on millions of Korean sentences that are similar to those we expect to be spoken. In addition to the queries we used for training voice search, we also used parts of web pages, selected blogs, news articles and more. Because the system expects spoken data similar to what it was trained on, it will generally work well on normal spoken sentences, but may yet have difficulty on random or rare word sequences -- we will work to keep improving on those.

Korean voice input is part of Google’s long-term goal to make speech input an acceptable and useful form of input on any mobile device. As with voice search, our cloud computing infrastructure will help us to improve quality quickly, as we work to better support all noise conditions, all Korean dialects, and all Korean users.

Clustering Related Queries Based on User Intent

Posted by Jayant Madhavan and Alon Halevy

People today use search engines for all their information needs, but when they pose a particular search query, they typically have a specific underlying intent. However, when looking at any query in isolation, it might not entirely be clear what the underlying intent is. For example, when querying for mars, a user might be looking for more information about the planet Mars, or the planets in the solar system in general, or the Mars candy bar, or Mars the Roman god of war. The ambiguity in intent is most pronounced for queries that are inherently ambiguous and for queries about prominent entities about which there are various different types of information on the Internet. Given such ambiguity, modern search engines try to complement their search results with lists of related queries that can be used to further explore a particular intent.

In a recent paper, we explored the problem of clustering the related queries as a means of understanding the different intents underlying a given user query. We propose an approach that combines an analysis of anonymized document-click logs (what results do users click on) and query-session logs (what sequences of queries do users pose in a search session). We model typical user search behavior as a traversal of a graph whose nodes are related queries and clicked documents. We propose that the nodes in the graph, when grouped based on the probability of a typical user visiting them within a single search session, yield clusters that correspond to distinct user intents.

Our results show that underlying intents (clusters of related queries) almost always correspond to well-understood, high-level concepts. For example, for mars, in addition to re-constructing each of the intents listed earlier, we also find distinct clusters grouping queries about NASA’s missions to the planet, about specific interest in life on Mars, as well as a Japanese comic series, and a grocery chain named Mars. We found that our clustering approach yields better results than earlier approaches that either only used document-click or only query-session information. More details about our proposed approach and an analysis of the resulting clusters can be found in our paper that was presented at the International World Wide Web conference earlier this year.

Google at USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘10)

Posted by Murray Stokely, Software Engineer

The 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI ‘10) was recently held in Vancouver, B.C. This biennial conference is one of the premiere forums for presenting innovative research in distributed systems from both academia and industry, and we were glad to be a part of it.

In addition to sponsoring this conference since 2002, Googlers contributed to the exchange of scientific ideas through authoring or co-authoring 3 published papers, organizing workshops, and serving on the program committee. A short summary of the contributions:

• Large-scale Incremental Processing Using Distributed Transactions and Notifications.
  Google replaced its batch-oriented indexing system with an incremental system, Percolator. Rather than running a series of high-latency map-reduces over large batches of documents, we now index individual documents at very low latency. The result is a 50% reduction in search result age; our paper discusses this project and the implications of the result.
• Availability in Globally Distributed Storage Systems.
  Reliable and efficient storage systems are a key component of cloud-based services. In this paper we characterize the availability properties of cloud storage systems based on extensive monitoring of Google's main storage infrastructure and present statistical models that enable further insight into the impact of multiple design choices, such as data placement and replication strategies. We demonstrate the utility of these models by computing data availability under a variety of replication schemes given the real patterns of failures observed in our fleet.
  
• Onix: A Distributed Control Platform for Large-scale Production Networks.
  There has been recent interest in a new networking paradigm called Software-Defined Networking (SDN). The crucial enabler for SDN is distributed control platform that shields developers from the details of the underlying physical infrastructure and allows them to write sophisticated control logic against a high-level API. Onix provides such a control platform for large-scale production networks.
  

In addition to the papers presented by current Googlers, we were also happy to see that the recipient of the 2009 Google Ph.D. Fellowship in Cloud Computing, Roxana Geambasu, presented her work on Comet: An active distributed key-value store.

Videos of all of the talks from OSDI are available on the conference website for attendees and current USENIX members. There is also a USENIX YouTube channel with a growing subset of the conference videos open to everyone.

Google is making substantial progress on many of the grand challenge problems in computer science and artificial intelligence as part of its mission to organize the worlds information and make it useful. Given the continuing increase in the scale of our distributed systems it’s fair to say we’ll have some other exciting new work to share at the next OSDI. Hope to see you in 2012.

Making an Impact on a Thriving Speech Research Community

Posted by Vincent Vanhoucke, Google Research

While we continue to launch exciting new speech products--most recently Voice Actions and Google Search by Voice in Russian, Czech and Polish--we also strive to contribute to the academic research community by sharing both innovative techniques and experiences with large-scale systems.

This year’s gathering of the world’s experts in speech technology research, Interspeech 2010 in Makuhari, Japan, which Google co-sponsored, was a fantastic demonstration of the momentum of this community, driven by new challenges such as mobile voice communication, voice search, and the increasing international reach of speech technologies.

Googlers published papers that showcased the breadth and depth of our speech recognition research. Our work addresses both fundamental problems in acoustic and language modeling, as well as the practical issues of building scalable speech interfaces that real people use everyday to make their lives easier.

Here is a list of the papers presented by Googlers at the conference:

• Direct Construction of Compact Context-Dependency Transducers From Data, David Rybach and Michael Riley (Computer Speech & Language Best Paper Award).
• Voice Search for Development, Etienne Barnard, Johan Schalkwyk, Charl van Heerden and Pedro J. Moreno.
• Unsupervised Discovery and Training of Maximally Dissimilar Cluster Models, Françoise Beaufays, Vincent Vanhoucke and Brian Strope.
• Search by Voice in Mandarin Chinese, Jiulong Shan, Genqing Wu, Zhihong Hu, Xiliu Tang, Martin Jansche and Pedro J. Moreno.
• On-Demand Language Model Interpolation for Mobile Speech Input, Brandon Ballinger, Cyril Allauzen, Alexander Gruenstein, and Johan Schalkwyk.
• Building Transcribed Speech Corpora Quickly and Cheaply for Many Languages, Thad Hughes, Kaisuke Nakajima, Linne Ha, Atul Vasu, Pedro J. Moreno and Mike LeBeau.
• Say What? Why Users Choose to Speak their Web Queries, Maryam Kamvar and Doug Beeferman.
• Study on Interaction between Entropy Pruning and Kneser-Ney Smoothing, Ciprian Chelba, Thorsten Brants, Will Neveitt and Peng Xu.
• Decision Tree State Clustering with Word and Syllable Features, Hank Liao, Chris Alberti, Michiel Bacchiani and Olivier Siohan.

Bowls and Learning

Posted by Phil Long, Research Team

It is easy to find the bottom of a bowl no matter where you start -- if you toss a marble anywhere into the bowl, it will roll downhill and find its way to the bottom.

What does this have to do with Machine Learning? A natural way to try to construct an accurate classifier is to minimize the number of prediction errors the classifier makes on training data. The trouble is, even for moderate-sized data sets, minimizing the number of training errors is a computationally intractable problem. A popular way around this is to assign different training errors different costs and to minimize the total cost. If the costs are assigned in a certain way (according to a “convex loss function”), the total cost can be efficiently minimized the way a marble rolls to the bottom of a bowl.

In a recent paper, Rocco Servedio and I show that no algorithm that works this way can achieve a simple and natural theoretical noise-tolerance guarantee that can be achieved by other kinds of algorithms. A result like this is interesting for two reasons: first, it's important to understand what you cannot do with convex optimization in order to get a fuller understanding of what you can do with it. Second, this result may spur more research into noise-tolerant training algorithms using alternative approaches.

Poetic Machine Translation

Posted by Dmitriy Genzel, Software Engineer

Once upon a midnight dreary, long we pondered weak and weary,
Over many a quaint and curious volume of translation lore.
When our system does translation, lifeless prose is its creation;
Making verse with inspiration no machine has done before.
So we want to boldly go where no machine has gone before.
Quoth now Google, "Nevermore!"

Robert Frost once said, “Poetry is what gets lost in translation.” Translating poetry is a very hard task even for humans, and is clearly beyond the capability of current machine translation systems. We therefore, out of academic curiosity, set about testing the limits of translating poetry and were pleasantly surprised with the results!

We are going to present a paper on poetry translation at the EMNLP conference this year. In this paper, we investigate the purely technical challenges around generating translations with fixed rhyme and meter schemes.

The value of preserving meter and rhyme in poetic translation has been highly debated. Vladimir Nabokov famously claimed that, since it is impossible to preserve both the meaning and the form of the poem in translation, one must abandon the form altogether. Another authority (and for us computer scientists, perhaps the more familiar one), Douglas Hofstadter argues that preserving the form is very important to maintaining the feeling and the sound of a poem. It is in this spirit that we decided to experiment with translating not only poetic meaning, but form as well.

A Statistical Machine Translation system, like Google Translate, typically performs translations by searching through a multitude of possible translations, guided by a statistical model of accuracy. However, to translate poetry, we not only considered translation accuracy, but meter and rhyming schemes as well. In our paper we describe in more detail how we altered our translation model, but in general we chose to sacrifice a little of the translation’s accuracy to get the poetic form right.

As a pleasant side-effect, the system is also able to translate anything into poetry, allowing us to specify the genre (say, limericks or haikus), or letting the system pick the one it thinks fits best. At the moment, the system is too slow to be made publicly accessible, but we thought we’d share some excerpts:

A stanza from Essai monographique sur les Dianthus des Pyrénées françaises by Edouard Timbal-Lagrave and Eugène Bucquoy, translated to English as a pair of couplets in iambic tetrameter:

So here's the dear child under land,
will not reflect her beauty and
besides the Great, no alter dark,
the pure ray, fronts elected mark.

Voltaire’s La Henriade, translated as a couplet in dactylic tetrameter:

These words compassion forced the small to lift her head
gently and tell him to whisper: “I'm not dead."

Le Miroir des simples âmes, an Old French poem by Marguerite Porete, translated to Modern French by M. de Corberon, and then to haiku by us:

“Well, gentle soul”, said
Love, “say whatever you please,
for I want to hear.”

More examples and technical details can be found in our research paper (as well as clever commentary).