Helping the World to Teach

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.

Python scripts inside PowerShell window

After installing Python on Windows, you can start a Python script by executing the script file-name.
E.g.:
./MyScript.py

However, the command is not executed in the same PowerShell window.  It opens a new command window to start "python.exe", which executes the command (and immediately closes the window).

This behavior can be changed, and the script can be executed within the current PowerShell window.

Just add the ".py" file extension to the PATHEXT environment variable.  This can be done by executing this command:
$env:PATHEXT += ";.py"

You can add this command to your "$profile" file, so you don't need to execute this command in every newly started PowerShell window.  Run the next command to add this line to your $profile automatically:
"`n" + '$env:PATHEXT += ";.py" # Transparent execution of Python scripts' |Out-File $profile -Append -Encoding Default

You can test it by creating and running a small script:

'print("Hello, World!")' | Out-File MyScript.py -Encoding Default

.\MyScript.py

Uploading a file to Amazon Glacier using PowerShell

For my own convenience, I created a PowerShell module to upload backup files to Amazon's new backup service "Glacier".

The module is contained in this file:
http://dl.dropbox.com/u/2350654/blog/FxAWS.zip
(including the Amazon AWS SDK library)
Extract it into your Powershell module directory, e.g.
C:\Users\<your name>\Documents\WindowsPowerShell\Modules.
(this will create a directory FxAWS under the directory Modules)

Start powershell and run:
Import-Module FxAWS

C:\Users\wim devos.GENOFFICE> Write-AWSGlacier -AWSAccessKey '<access key>' -AWSSecretKey '<secret key>' -AWSRegion <some region> -
GlacierVault <vault name> -Filename <filename> -Description <description>

e.g.

Write-AWSGlacier -AWSAccessKey '[your access key]' -AWSSecretKey ' [your secret key] ' -AWSRegion us-east-1 -GlacierVault "backup" -Filename "backup-20120830.7z"


The parameters are:

• AWSAccessKey and AWSSecretKey.
  These are NOT your login and password to log on to the Amazon.com web site.
  You can find the access key and secret key in your Amazon.com account:
  https://portal.aws.amazon.com/gp/aws/securityCredentials
  Extra credentials can be created and they can be removed individually.
• AWSRegion.
  The region where your Glacier Vault has been created.
• GlacierVault
  The name of the Vault that you created in the Glacier administration website.
• FileName
  The file that you want to upload.
• Description (optional)
  A description used in the Glacier administration website.  When none is specified, the last part of the filename path is used.

You can create 3 (global) PowerShell variabled $AWSAccessKey_Default, $AWSSecretKey_Default and $AWSRegion_Default, in which case you can omit the -AWS* parameters.

GIT External Diff / Merge tools

Occording to the GIT book, GIT supports these external Diff / Merge tools:

• [araxis] Araxis Merge - Commercial
• [bc3] Beyond Compare 3 - Commercial
• [diffuse] Diffuse - Open source
• [ecmerge] ECMerge - Commercial
• [emerge] Emerge (Emacs) - Open source
• [gvimdiff] gvimdiff - Open source
• [kdiff3] KDiff3 - Open source
• [meld] Meld merge - Open source
• [opendiff] opendiff - OS X Developer Tools
• [p4merge] P4Merge - Commercial
• [tkdiff] TkDiff - Open source
• [tortoisemerge] TortoiseMerge - Open source - [ Merge tool only ]
• [vimdiff] vimdiff - Open source
• [xxdiff] xxdiff - Open source
• [kompare] Kompare - Open source - [ Diff tool only ]

You can choose your prefered diff / merge tool by executing this command (Windows or Linux), in this case for my favorite kdiff3.

git config --global diff.tool kdiff3 

git config --global merge.tool kdiff3

The external diff is started using this command:

git difftool

You will probably get the error "The diff tool kdiff3 is not available as 'kdiff3'. external diff died, stopping at <filename>.", because GIT doesn't find your tool.
This can be resolved by adding your tool to the environment PATH variable, or by telling GIT where to find your tool(s):

git config --global difftool.kdiff3.path "C:/Program Files (x86)/KDiff3/kdiff3.exe"

git config --global mergetool.kdiff3.path "C:/Program Files (x86)/KDiff3/kdiff3.exe" 

Any configuration can be undone by executing:

git config --global <config item> --unset

e.g.

git config --global mergetool.kdiff3.path --unset

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

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:

1. Visual complexity -- how complex the visual design of a website looks 
2. 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.

Google at UAI 2012

Posted by Kevin Murphy, Research Scientist

The conference on Uncertainty in Artificial Intelligence (UAI) is one of the premier venues for research related to probabilistic models and reasoning under uncertainty. This year's conference (the 28th) set several new records: the largest number of submissions (304 papers, last year 285), the largest number of participants (216, last year 191), the largest number of tutorials (4, last year 3), and the largest number of workshops (4, last year 1). We interpret this as a sign that the conference is growing, perhaps as part of the larger trend of increasing interest in machine learning and data analysis.

There were many interesting presentations. A couple of my favorites included:

• "Video In Sentences Out," by Andrei Barbu et al. This demonstrated an impressive system that is able to create grammatically correct sentences describing the objects and actions occurring in a variety of different videos. 
• "Exploiting Compositionality to Explore a Large Space of Model Structures," by Roger Grosse et al. This paper (which won the Best Student Paper Award) proposed a way to view many different latent variable models for matrix decomposition - including PCA, ICA, NMF, Co-Clustering, etc. - as special cases of a general grammar. The paper then showed ways to automatically select the right kind of model for a dataset by performing greedy search over grammar productions, combined with Bayesian inference for model fitting.

A strong theme this year was causality. In fact, we had an invited talk on the topic by Judea Pearl, winner of the 2011 Turing Award, in addition to a one-day workshop. Although causality is sometimes regarded as something of an academic curiosity, its relevance to important practical problems (e.g., to medicine, advertising, social policy, etc.) is becoming more clear. There is still a large gap between theory and practice when it comes to making causal predictions, but it was pleasing to see that researchers in the UAI community are making steady progress on this problem.

There were two presentations at UAI by Googlers. The first, "Latent Structured Ranking," by Jason Weston and John Blitzer, described an extension to a ranking model called Wsabie, that was published at ICML in 2011, and is widely used within Google. The Wsabie model embeds a pair of items (say a query and a document) into a low dimensional space, and uses distance in that space as a measure of semantic similarity. The UAI paper extends this to the setting where there are multiple candidate documents in response to a given query. In such a context, we can get improved performance by leveraging similarities between documents in the set.

The second paper by Googlers, "Hokusai - Sketching Streams in Real Time," was presented by Sergiy Matusevych, Alex Smola and Amr Ahmed. (Amr recently joined Google from Yahoo, and Alex is a visiting faculty member at Google.) This paper extends the Count-Min sketch method for storing approximate counts to the streaming context. This extension allows one to compute approximate counts of events (such as the number of visitors to a particular website) aggregated over different temporal extents. The method can also be extended to store approximate n-gram statistics in a very compact way.

In addition to these presentations, Google was involved in UAI in several other ways: I held a program co-chair position on the organizing committee, several of the referees and attendees work at Google, and Google provided some sponsorship for the conference.

Overall, this was a very successful conference, in an idyllic setting (Catalina Island, an hour off the coast of Los Angeles). We believe UAI and its techniques will grow in importance as various organizations -- including Google -- start combining structured, prior knowledge with raw, noisy unstructured data.

Solving ANTLR errors using ANTLRWorks

Solving ANTLR grammar errors can be very difficult, especially in complex grammar files.

Below is a simple example, based on the GQL ANTLR-grammar used in FxGqlC.
(reduced to illustrate the problem.  A complete grammar can be found here.  GQL is a domain language similar to SQL / T-SQL)

grammar sql;
select_command
: SELECT (WS top_clause)? WS column_list EOF
;
top_clause
: TOP expression
;
column_list
: expression (WS? ',' WS? expression)*
;
expression
: expression_3
;
expression_3
: expression_2 (WS? op_3 WS? expression_2)*
;
op_3 : '+' | '-' | '&' | '|' | '^'
;
expression_2
: expression_1 (WS? op_2 WS? expression_1)*
;
op_2 : '*' | '/' | '%'
;
expression_1
: op_1 WS? expression_1
| expression_atom
;
op_1 : '~' | '+' | '-'
;
expression_atom
: NUMBER
| '(' WS? expression WS? ')'
;
SELECT : 'select' ;
TOP : 'top' ;
NUMBER : DIGIT+;
WS
: (' '|'\t'|'\n'|'\r'|'\u000C')+
;
 
fragment DIGIT : '0'..'9';

The 3 expression "levels" are used to handle operator precedence. The grammar is designed to be able to parse expressions like:

• SELECT 17
• SELECT 17 * 14 + 3
• SELECT 17 + 14 + 3
• SELECT - 17
• SELECT 17 * - 14 + 3
• SELECT 17 + 14 + - 3
• SELECT TOP 3 17
• ...

When trying to 'compile' or 'Interpret' the grammar in ANTLRWorks, you get this error:

[11:36:44] error(211): <notsaved>:21:43: [fatal] rule expression_3 has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
[11:36:44] warning(200): <notsaved>:21:43:
Decision can match input such as "WS {'+', '-'} WS NUMBER" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input

Solving this error just by analyzing the grammar is quite a challenge, even for this very simple example. When using a large grammar file it is nearly impossible.
But ANTLRWorks has a very useful tool to show what's going wrong.

• The error message indicates that there is a problem with expression_3 (expression_3 is also indicated in red in the list of rules/tokens in the left pane).
• Put your cursor in expression_3, and select the tab "Syntax Diagram" in the lower pane.
• First, in the lower pane, select "Alternatives '1'" in the upper right corner.
  ==> In green you see how the grammar matches "WS '+' WS NUMBER", which is exactly what we want.
  
• Next, select "Alternatives '2'" in the upper right corner.
  ==> In red you see how the grammar matches "WS '+' WS NUMBER".
  
• In the latter case, you can see that the matching starts in the TOP-clause.

This is what's happening: there can be an ambiguity when parsing "SELECT TOP 1 + 2 + 20".
It is not clear where the top-clause ends and the column-list starts.  Both '+' signs can be unary or binary.

• It can be: "SELECT [TOP 1] [+ 2 + 20]", being equivalent to "SELECT TOP 1 22"
• Or it can be: "SELECT [TOP 1 + 2] [+ 20]", being equivalent to "SELECT TOP 3 20"

This ambiguity must be resolved, because only one interpretation should be valid.
In this specific case, the grammar could be changed in a way that the top-clause expression should always have parentheses surrounding it when it is not a simple number.
This can easily be achieved by changing:

top_clause
: TOP expression
;

to:

top_clause : TOP expression_atom ;

This solves the ambiquity. The text "SELECT TOP 1 + 2 + 20" is now parsed as "SELECT [TOP 1] [+ 2 + 20]".
And if somebody wants to use "1 + 2" in the TOP-clause, he should use: "SELECT TOP (1 + 2) + 20", which is parsed as: "SELECT [TOP (1 + 2)] [+ 20]"

Below you find the complete example, with the TOP-clause corrected:

grammar sql;
select_command
: SELECT (WS top_clause)? WS column_list EOF
;
top_clause
: TOP expression_atom
;
column_list
: expression (WS? ',' WS? expression)*
;

expression
: expression_3
;
expression_3
: expression_2 (WS? op_3 WS? expression_2)*
;
op_3 : '+' | '-' | '&' | '|' | '^'
;
expression_2
: expression_1 (WS? op_2 WS? expression_1)*
;
op_2 : '*' | '/' | '%'
;
expression_1
: op_1 WS? expression_1
| expression_atom
;
op_1 : '~' | '+' | '-'
;
expression_atom
: NUMBER
| '(' WS? expression WS? ')'
;
SELECT : 'select' ;
TOP : 'top' ;
NUMBER : DIGIT+;
WS
: (' '|'\t'|'\n'|'\r'|'\u000C')+
;
 
fragment DIGIT : '0'..'9';