Machine Learning: Nearest Neighbor

This is the simplest technique for instance based learning. Basically, find a previous seen data that is "closest" to the query data point. And then use its previous output for prediction.

The concept of "close" is defined by a distance function, dist(A, B) gives a quantity which need to observe the triangular inequality.
ie: dist(A, B) + dist(B, C) >= dist(A, C)

Defining the distance function can be domain specific. One popular generic distance function is to use the Euclidean distance.
dist(A, B) = square_root(sum_over_i(square(xai - xbi)))

In order to give each attribute the same degree of influence, you need to normalize their scale within the same range. On the other hand, you need to figure out a way to compute the difference between categorical values (ie: whether "red" is more similar to "blue" or "green"). A common approach is to see whether "red" and "blue" affects the output value in a similar way. If both colors has similar probability distribution across each output value, then we consider the two colors are similar.

Therefore you need to transform the attributes xi.

• Normalize their scale: transform xi = (xi - mean) / std-deviation
  
• Quantify categorical data: If xi is categorical, then (xai - xbi) = sum_over_k(P(class[k] | xai) – P(class[k] | xbi))

Nearest neighbor will be sensitive to outliers, say you have a few abnormal data and query point around these outliers will be wrongly estimated. One solution is to use multiple nearest neighbors and combine their output in a certain way. This is known as KNN (k-nearest-neighbor). If the problem is classification, every neighbor will cast a vote with a weight inversely proportional to the "distance" with the query point, and the majority win. If the problem is regression, the weighted average of their output will be used instead.

Execution Optimization

One problem of instance-based learning is that you need to store all previously seen data and also compute the distance of query point to each of them. Both time and space complexity to serve a single query is O(M * N) where M is the number of dimensions and N is the number of previous data points.

Instead of compute the distance between the query point to each of the existing data points, you can organized the existing points into a KD Tree based on the distance function. The KD Tree has the properties that the max distance between two nodes is bound by the level of their common parent.

Using the KD Tree, you navigate the tree starting at the root node. Basically, you calculate the dist(current_node, query_point)

and each of the child nodes of the current_node
dist(child_j, query_point)

And then find the minimum of them, if the minimum is one of its child, then you navigate down the tree by setting current_node to this child and repeat the process. You terminate if the current_node is the minimum, or when there is no more child nodes.

After terminating at a particular node, this node is pretty close to the query point. You need to explore the surrounding nodes around this node (its siblings, siblings child, parent's siblings) to locate the K nearest neighbors.

By using a KD Tree, the time complexity depends on the depth of the tree and hence of order O(M * log N)

Note that KD Tree is not effective when the data has high dimensions (> 6).

Another way is to throw away some of the previous seen data if they won't affect the result prediction (especially effective for classification problem, you can just keep the data at the boundary between two different output values and throw away the interior points of a cluster of data points all has the same output values). However, if you are using KNN, then throwing away some points may change the result. So a general approach is to verify the previous seen data is still correctly predicted after throwing out various combination of points.

Recommendation Engine

A very popular application of KNN is the recommendation engine of many e-commerce web sites using a technique called "Collaborative Filtering". E.g. An online user have purchased a book, the web site looks at other "similar" users to see what other books they have seen and recommends that to the current user.

First of all, how do we determine what attributes of the users to be captured. This is a domain-specific questions because we want to identify those attributes that are most influential, maybe we can use static information such as user's age, gender, city ... etc. But here lets use something more direct ... the implicit transaction information (e.g. if the user has purchased a book online, we know that he likes that book) as well as explicit rating information (e.g. the user rates a book he bought previously so we know whether he/she likes the book or not).

Lets use a simple example to illustrate the idea. Here we have a number of users who rates a set of movies. The ratings is from [0 - 10] where 0 means hates it and 10 means extremely likes it.


The next important things is to define the distance function. We don't want to use the rating directly because of the following reasons.

Some nice users give an average rating of 7 while some tough users give an average rating of 5. On the other hand, the range of ratings of some users are wide while other users are narrow. However, we don't want these factors to affect our calculation of user similarity. We consider two users of same taste as long as they rate the same movie above their average or below their average with the same percentage of their rating range. Two users has different taste if they rate the movies in different directions.

Lets call rating_i_x to denote user_i's rating on movie_x

We can use the correlation coefficient to capture this.

sum_of_product =
sum_over_x( (rating_i_x - avg(rating_i)) * (rating_j_x - avg(rating_j)) )

If this number is +ve, then user_i and user_j are moving in the same direction. If this number is -ve, then they are moving in opposite direction (negatively correlated). If this number is zero, then they are uncorrelated.

We also need to normalize them with the range of the user's ratings, so we compute
root_of_product_square_sum =
square_root(sum_over_x( ((rating_i_x - avg(rating_i)) **2) * ((rating_j_x - avg(rating_j)) **2) )))

Define Pearson Coefficient = sum_of_product / root_of_product_square_sum

Let Pearson Coefficient to quantify the "similarity" between 2 users.

We may also use negatively correlated users to make recommendation. For example, if user_i and user_j is negatively correlated, then we can recommend the movies that user_j hates to user_i. However, this seems to be a bit risky so we are not doing it here.

Machine Learning: Probabilistic Model

Probabilistic model is a very popular approach of “model-based learning” based on Bayesian theory. Under this approach, all input attributes is binary (for now) and the output is categorical.

Here, we are given a set of data with structure [x1, x2 …, y] is presented. (in this case y is the output). The learning algorithm will learn (from the training set) how to predict the output y for future seen data

We assume there exist a hidden probability distribution from the input attributes to the output. The goal is to learn this hidden distribution and apply it to the input attributes of the later encountered query point to pick the class that has the maximum probability.

Making Prediction

Lets say the possible value of output y is {class_1, class_2, class_3}. Given input [x1, x2, x3, x4], we need to compute the probability of each output class_j, and predict the one which has the highest value.

max {P(class_j | observed_attributes)}

According to Bayes theorem, this value is equal to …

max { P(observed_attributes | class_j) * P(class_j) / P(observed_attributes) }

The dominator is the same for all class_j, so we can ignore it, so we just need to find

max { P(observed_attributes | class_j) * P(class_j) }

P(class_j) is easy to find, we just calculate

P(class_j) = (samples_of_class_j / total samples)

Now, lets look at the other term, P(observed_attributes | class_j), from Bayesian theory

P(x1 ^ x2 ^ x3 ^ x4 | class_j) =
P(x1 | class_j) *
P(x2 | class_j ^ x1) *
P(x3 | class_j ^ x1 ^ x2) *
P(x4 | class_j ^ x1 ^ x2 ^ x3)

Learning the probability distribution

In order to provide all the above terms for the prediction, we need to build the probability distribution model by observing the training data set.

Notice that finding the last term is difficult. Assume x1, x2 ... is binary, there can be 2 ** (m – 1) possible situations to watch. It is very likely that we haven’t seen enough situations in the training data, in this case this term for all class_j will be zero. So a common solution is to start with count = 1 for all possible combinations and increase the count when we see an occurrence in the training data.


Bayesian Network

Bayesian Network base on the fact we know certain attributes are clearly independent. By applying this domain knowledge, we draw a dependency graph between attributes. The probability of occurrence of a particular node only depends on the occurrence of its parent nodes and nothing else. To be more precise, nodeA and nodeB (which is not related with a parent-child relationship) doesn't need to be completely independent, they just need to be independent given their parents.

In other words, we don't mean P(A|B) = P(A),
we just need P(A | parentsOfA ^ B) = P(A | parentsOfA)
Therefore P(x4 | class_j ^ x1 ^ x2 ^ x3) = P(x4 | class_j ^ parentsOf_x4)

we only need to find 2 ** p situations of the occurrence combination of the parent nodes where p is the number of parent nodes.


Naive Bayes

Naive Bayes takes a step even further by assuming every node is completely independent


Note that x1, x2, x3, x4 can be categorical as well. For example, if x1 represents zip code, then P('95110' | class_j) is the same as P(x1 = '95110' | class_j).

What if x1 is a continuous variable ? (say height of a person). The challenge is that a continuous variable has infinite possibility such that the chance of seeing one in the training data is almost zero.

One way to deal with continuous variable is to discretetize it. In other words, we can partition x1 into buckets which has an associated range and assign x1 to the corresponding bucket if it falls into that range.

Another way is for each output class_j, we presume a arbitrary distribution function for x1. (lets say we pick the normal distribution function). So the purpose of the training phase is to figure out the parameter of this distribution function (in this case, it is the mean and standard deviation).

In other words, we use the subset of training data whose output class is class_j. Within this subset, we compute the mean and standard deviation of x1 (height of the person). Later on when we want to compute P(x1 = 6.1 feet | class_j), we just apply the distribution function (plug-in the learned mean and standard deviation).

Note that the choice of the form of the distribution function is quite arbitrary here and it may be simply wrong. So it is important to analyze how x1 affects the output class in order to pick the right distribution function.


Spam Filter Application

Lets walk through an application of the Naive Bayes approach. Here we want to classify a particular email to determine whether it is spam or not.

The possible value of output y is {spam, nonspam}

Given an email: "Hi, how are you doing ?", we need to find ...
max of P(spam | mail) and P(nonspam | mail), which is same as ...
max of P(mail | spam) * P(spam) and P(mail | nonspam) * P(nonspam)

Lets focus in P(mail | spam) * P(spam)

We can view mail as an array of words [w1, w2, w3, w4, w5]

P(mail | spam) =
P(w1='hi' | spam) *
P(w2='how' | spam ^ w1='hi') *
P(w3='are' | spam ^ w1='hi' ^ w2='how') *
...

We make some naive assumptions here

• Chance of occurrence is independent of preceding words. In other words, P(w2='how' | spam ^ w1='hi') is the same as P(w2='how' | spam)
• Chance of occurrence is independent of word position. P(w2='how' | spam) is the same as (number of 'how' in spam mail) / (number of all words in spam mail)
  

With these assumptions ...

P(mail | spam) =
(hi_count_in_spam / total_words_in_spam) *
(how_count_in_spam / total_words_in_spam) *
(are_count_in_spam / total_words_in_spam) *
...

What if we haven't seen the word "how" from the training data ? Then the probability will becomes zero. Here we adjust terms such that a reasonable probability is assigned to unseen words.

P(mail | spam) =
((hi_count_in_spam + 1) / (total_words_in_spam + total_vocabulary)) *
((how_count_in_spam + 1) / (total_words_in_spam + total_vocabulary)) *
((are_count_in_spam + 1) / (total_words_in_spam + total_vocabulary)) *
...

What we need is the word_count per word/class combination as well as the word_count per class. This can be done through feeding a large number of training sample mails labeled with "spam" or "nonspam" into a learning process.

The learning process can also be done in parallel using a 2-rounds of Map/Reduce.


Alternatively, we can also update the counts incrementally as new mail arrives.

Machine Learning Intuition

As more and more user data are gathered on different web sites (such as e-commerce, social network), data mining / machine learning technique becomes an increasingly important tool to analysis them and extract useful information out of it.

There a wide variety of machine learning applications, such as …

• Recommendation: After buying a book at Amazon, or rent a movie from Netflix, they recommends what other items that you may be interested
• Fraud detection: To protect its buyer and seller, an auction site like EBay detect abnormal patterns to identify fraudulent transaction
• Market segmentation: Product company divide their market into segments of similar potential customers and design specific marketing campaign for each segment.
• Social network analysis: By analysis the user’s social network profile data, social networking site like Facebook can categorize their users and personalize their experience
• Medical research: Analyzing DNA patterns, Cancer research, Diagnose problem from symptoms

However, machine learning theory involves a lot of math which is non-trivial for people who doesn’t have the rigorous math background. Therefore, I am trying to provide an intuition perspective behind the math.

General Problem

Each piece of data can be represented as a vector [x1, x2, …] where xi are the attributes of the data.

Such attributes can be numeric or categorical. (e.g. age is an numeric attribute and gender is a categorical attribute)

There are basically 3 branch of machine learning ...

Supervised learning

• The main use of supervised learning is to predict an output based on a set of training data. A set of data with structure [x1, x2 …, y] is presented. (in this case y is the output). The learning algorithm will learn (from the training set) how to predict the output y for future seen data.
• When y is numeric, the prediction is called regression. When y is categorical, the prediction is called classification.

Unsupervised learning

• The main use of unsupervised learning is to discover unknown patterns within data. (e.g. grouping similar data, or detecting outliers).
• Identifying clusters is a classical scenario of unsupervised learning

Reinforcement learning

• This is also known as “continuous learning” where the final output is not given. The agent will choose an action based on its current state and then will be present with an award. The agent learns how to maximize its award and come up with a model call “optimal policy”. A policy is a mapping between from “state” to “action” (given I am at a particular state, what action should I take).

Data Warehouse

Data warehouse is not “machine learning”, it is basically a special way to store your data so that it can be easily group in many ways for doing analysis in a manual way.

Typically, data is created from OLTP systems which runs the company’s business operation. OLTP capture the “latest state” of the company. Data are periodically snapshot to the data-warehouse for OLAP, in other words, data-warehouse add a time dimension to the data.

There is an ETL process that extract data from various sources, cleansing the data, transform to the form needed by the data-warehouse and then load into the data cube.

Data-warehouse typically organize the data as a multi-dimensional data cube based on a "Star schema" (1 Fact table + N Dimension tables). Each cell contains aggregate data along different (combination) of dimensions.


OLAP processing involves the following operations

• Rollup: Aggregate data within a particular dimension. (e.g. For the “time” dimension, you can “rollup” the aggregation from “month” into “quarter”)
• Drilldown: Breakdown the data within a particular dimension (e.g. For the “time” dimension, you can “drilldown” from months” into “days”)
• Slice: Cut a layer out of a particular dimension (e.g. Look at all data at “Feb”)
• Dice: Select a sub data cube (e.g. Look at all data at “Jan” and “Feb” as well as product “laptop” and “hard disk”

The Data-warehouse can be further diced into specific “data marts” that focus in different areas for further drilldown analysis.

Some Philosophy

To determine the output from a set of input attributes, one way is to study the physics behinds them and write a function that transform the input attributes to the output. However, what if the relationship is unknown ? or the relationship hasn’t been formally specified ?

Instead of based on a sound theoretical model, machine learning is trying to make prediction based on previously observed data. There are 2 broad type of learning strategies

Instance-based learning

• Also known as lazy learning, the learner remembers all the previous seen examples. When a new piece of input data arrives, it tried to find the best matched data it previous seen and use its output to predict the output of the new data. It has an underlying assumption that if two piece of data are “similar” in their input attributes, their output are also similar.
• Nearest neighbor is a classical approach for instance-based learning
  

Model-based learning

• Also known as eager learning, the learner assume the input attributes and the output are related in a particular model (e.g. linear regression, logistic regression, neural network, probabilistic belief network, decision tree … etc). So the learner learn the parameters of such a model based on previously seen examples. When a new piece of input data arrives, it will use the learned model to predict the output.

Eager learning that learn a generalized model upfront, and lazy learning learn from seen examples at the time of query. Instead of learning a generic model that fits all observed data, lazy learning can focus its analysis close to the query point. However, getting a comprehensible model in lazy learning is harder and it also require large memory to store all seen data.

Good and Bad Public Cloud candidates

I recently have a good conversation with Ed and Dean of RightScale on what are the characteristics making an application a good public cloud citizen.

Good Public Cloud Candidates

Being stateless

• There is no warm up and cool down periods required. Newly started instances are immediately ready to work
• Work dispatching is very simple when any instances can do the work
  

Compute intensive with small dataset size

• Cloud computing enable quick deployment of a lot of CPU to work on you problem. But if it requires to load large amount of data before the CPU can start their computation, the latency and bandwidth cost will be increased
  

Contains only non-sensitive data

• Although cryptography technology is sufficient to protect your data, you don't want to pay the CPU overhead for encrypt/decrypt for every piece of data that you use in the cloud.

Highly fluctuating workload pattern

• Now you don't need to provision inhouse equipment to cater for the peak load, which sits idle for most of the time.
• The "pay as you go" model save cost because you don't pay when you are not using them

New application launch with unknown workload anticipation

• You don't need to take the risk of over-estimating the popularity of your new application, and buy more equipment than you actually need.
• You don't need to take the risk of under-estimating the popularity and ends up frustrating your customer because you cannot handle their workload.
• You can defer your big step investment and still be able to try out new ideas.

Bad Public Cloud Candidates

Demand special hardware

• Most of the cloud equipment are cheap, general purpose commodities. If you application demands a certain piece of hardware (e.g. a graphic processor for rendering), it will just not work or awfully slow.

Demand multi-cast communication facilities

• Most of the cloud providers disable multicast traffic in their network

Need to reside in a particular geographic location

• If there is legal or business requirement demanding your server to run in a physical location and that location is not covered by cloud providers, then you are out of luck.

Contain large dataset

• Bandwidth cost across cloud boundary is high. So you may endup have a large bill when loading large amount of data into the cloud
• Loading large amount of data also takes time. You need to compare that with the overall time of the processing itself to see if it makes sense

Contain highly sensitive data

• Legal, liabilities, auditing practices hasn't catched up yet. Companies running their core business app in the cloud will face a lot of legal challenges

Demand extremely low latency of user response

• Since you have no control about the location of where the machines are residing, latency is usually increase when you run your app in the cloud residing in a remote location

Run by 24 x 7 with extremely stable and non-fluctuating workload pattern

• If you are using a machine without shutting down, then many cost analysis report shows running the machine inhouse will be cheaper (especially for large enterprise who already have data center setup and a team of system administrators)

Hybrid Cloud

I personally believe the real usage pattern of public cloud for large enterprise is to move the fluctuating workload into the public cloud (e.g. Christmas sales for e-commerce site, Newly launched services) but retain most of the steady workload traffic in-house. In fact, I think enterprise is going to move in and out their application constantly based on the change of traffic patterns.

It is much appropriate to do the classification at the component level rather than at the App level. Instead of saying whether the App (as a whole) is suitable or not, we should determine which components of the app should run in the public cloud and which should stay in the data center.

In other words, an Application is running in a hybrid cloud mix, which span across public and private cloud.

The ability to move your application “frictionless” across cloud boundaries and manage the scattered components in a holistic way is key. Once you have this freedom to move, then the price of a particular public cloud provider has less impact on you because you can easily move to any cheaper provider at any time.

Solving TF-IDF using Map-Reduce

TF-IDF (Term Frequency, Inverse Document Frequency) is a basic technique to compute the relevancy of a document with respect to a particular term.

"Term" is a generalized element contains within a document. A "term" is a generalized idea of what a document contains. (e.g. a term can be a word, a phrase, or a concept).

Intuitively, the relevancy of a document to a term can be calculated from the percentage of that term shows up in the document (ie: the count of the term in that document divide by the total number of terms in it). We called this the "term frequency"

On the other hand, if this is a very common term which appears in many other documents, then its relevancy should be reduced. (ie: the count of documents having this term divided by total number of documents). We called this the "document frequency"

The overall relevancy of a document with respect to a term can be computed using both the term frequency and document frequency.

relevancy = term frequency * log (1 / document frequency)

This is called tf-idf. A "document" can be considered as a multi-dimensional vector where each dimension represents a term with the tf-idf as its value.

Compute TF-IDF using Map/Reduce

To extract the terms from a document, the following process is common

• Extract words by tokenize the input streams
• Make the words case-insensitive (e.g. transform to all lower case)
  
• Apply n-gram to extract phrases (e.g. statistically frequent n-grams is likely a phrase)
  
• Filter out stop words
• Stemming (e.g. transform cat, cats, kittens to cat)
  

To keep the term simple, each word itself is a term in our example below.

We use multiple rounds of Map/Reduce to gradually compute …

1. the word count of per word/doc combination
   
2. the total number of words per doc
   
3. the total number of docs per word. And finally compute the TF-IDF
   

Implementation in Apache PIG

There are many ways to implement the Map/Reduce paradigm above. Apache Hadoop is a pretty popular approach using Java or other programming language (ie: Hadoop Streaming).

Apache PIG is another approach based on a higher level language with parallel processing construct built in. Here is the 3 rounds of map/reduce logic implemented in PIG Script

REGISTER rickyudf.jar

/* Build up the input data stream */
A1 = LOAD 'dirdir/data.txt' AS (words:chararray);
DocWordStream1 =
   FOREACH A1 GENERATE
       'data.txt' AS docId,
       FLATTEN(TOKENIZE(words)) AS word;

A2 = LOAD 'dirdir/data2.txt' AS (words:chararray);
DocWordStream2 =
   FOREACH A2 GENERATE
       'data2.txt' AS docId,
       FLATTEN(TOKENIZE(words)) AS word;

A3 = LOAD 'dirdir/data3.txt' AS (words:chararray);
DocWordStream3 =
   FOREACH A3 GENERATE
       'data3.txt' AS docId,
       FLATTEN(TOKENIZE(words)) AS word;

InStream = UNION DocWordStream1,
                DocWordStream2,
                DocWordStream3;

/* Round 1: word count per word/doc combination */
B = GROUP InStream BY (word, docId);
Round1 = FOREACH B GENERATE
            group AS wordDoc,
            COUNT(InStream) AS wordCount;

/* Round 2: total word count per doc */
C = GROUP Round1 BY wordDoc.docId;
WW = GROUP C ALL;
C2 = FOREACH WW GENERATE
        FLATTEN(C),
        COUNT(C) AS totalDocs;
Round2 = FOREACH C2 GENERATE
          FLATTEN(Round1),
          SUM(Round1.wordCount) AS wordCountPerDoc,
          totalDocs;

/* Round 3: Compute the total doc count per word */
D = GROUP Round2 BY wordDoc.word;
D2 = FOREACH D GENERATE
        FLATTEN(Round2),
        COUNT(Round2) AS docCountPerWord;
Round3 = FOREACH D2 GENERATE
          $0.word AS word,
          $0.docId AS docId,
          com.ricky.TFIDF(wordCount,
                        wordCountPerDoc,
                        totalDocs,
                        docCountPerWord) AS tfidf;

/* Order the output by relevancy */
ORDERRound3 = ORDER Round3 BY word ASC,
                             tfidf DESC;
DUMP ORDERRound3;

Here is the corresponding User Defined Function in Java (contained in rickyudf.jar)

package com.ricky;

import java.io.IOException;

import org.apache.pig.EvalFunc;
import org.apache.pig.data.Tuple;

public class TFIDF extends EvalFunc<Double> {

 @Override
 public Double exec(Tuple input) throws IOException {
   // TODO Auto-generated method stub
   long wordCount = (Long) input.get(0);
   long wordCountPerDoc = (Long) input.get(1);
   long totalDocs = (Long) input.get(2);
   long docCountPerWord = (Long) input.get(3);
      
   double tf = (wordCount * 1.0) / wordCountPerDoc;
   double idf = Math.log((totalDocs * 1.0) / docCountPerWord);
      
   return tf * idf;
 }
}

Kids Learning Resources

In chatting with a friend, I think it is useful to summarize a list of good resources for kids learning that I've used in the past.

Learning in this generation is very different given there are a lot of resources out on the internet. It is important to teach the kids to figure out the knowledge themselves.

General tools for knowledge acquisition

• Google search for web pages and images
• Youtube for any educational videos
  
• Wikipedia for simple explanation of any knowledge
• How stuff works
  

Geography and Site seeing

• Google Map for navigating to different places
• Using the street view feature by dragging the little person icon (at the top left corner) into the map, we can visit different countries virtually. Here is the Eiffel tower in Paris, France. Google street view is extending its coverage so expect to see more areas in the world being covered in future.
• Google Earth for an even more sophisticated 3D map navigation. Watch their introduction video.
  

History and Ancient Empire

• Virtual tour of Forbidden City in 3D
• Flying into the Ancient Rome
• Chinese history for kids (this site is in Chinese language)
  

Human Body

• BBC provides has a very useful site that explain human body in easy and fun way.
• There is also an animation of Human Body

Money Management

Develop a good economic sense and planning to use money wisely is important, especially when kids are commonly spoiled by their parents these days.

• Money management

Online Games

I normally don't recommend exposing video or online games to the kids unless they are carefully chosen for educational purposes. Kids are so easily addicted to games. But if you can use their addiction appropriately, it is a good way to motivated them to learn, and it is fun too.

Here are some exceptionally good ones from Lego

• Original Junkbot
• Junkbot version 2
• World builder
  

Game Designing

It is also good to teach them how a game is designed because this gives them an opportunity to switch roles (from a player to a designer) and establish a good overall picture. There are some very good tools for designing games.

• Gamemaker
• Scratch
  
• A great link for designing tools
  

Kids Programming

Programming is all about planning for the steps to achieve a goal, and debugging is all about using a systematic way to find out why something doesn't work out as planned. Even you are not planning your kids to be a programmer or a computer professional, teach them how to programming can develop a very good planning and analytical skills, which is very useful in their daily life.

• The famous LOGO Green turtle is a good start at age 6 - 7
• Lego Mindstorm is a very good one because kids are exposed not just to programming skills but other engineering skills (such as mechanics) as well. It costs some money but I think it is well worth.
• A great link for robot fans.
  
• At around age 10, I found a professional programming language can be taught. I have chosen Ruby given its expressiveness and simplicity.
• One of my colleagues has suggested BlueJ, basically Java, but I personally haven't tried that yet (given I am a Ruby fan).
  

Materials at all subjects and all levels

• Internet for schools provides a great long list that is extremely useful
• Khan has put together a set of good videos (each about 10 mins long) on Math, Physics and Economics, at the high school level
  

Design Pattern for Eventual Consistency

"Eventual Consistency" and "BASE" are the modern architectural approaches to achieve highly scalable web applications. Some of my previous colleagues, Randy Shoup and Dan Pritchett has already written up some very good articles about this.

I recently have some good conversation from the cloud computing Google groups on the "eventual consistency" model. There is a general design pattern that I want to capture here.


The definition of data integrity

"Data integrity" is defined by the business people. It needs to hold at specific stages of the business operation cycle. Here we use a book seller example to illustrate. The data integrity is defined as ...

Sufficient books must be available in stock before shipment is made to fulfil an order.

The application designer, who design the application to support the business, may transform the "data integrity" as ...

Total_books_in_stock > sum_of_all_orders

The app designer is confident that if the above data integrity is observed, then the business integrity will automatically be observed. Note here that "data integrity" may be transformed by the application designer into a more restrictive form.

Now, the designer proceeds with the application implementation ... There are 2 approaches to choose from, with different implications of scalability.


The ACID approach

One way of ensuring the above integrity is observed is to use the traditional ACID approach. Here, a counter "no_of_books_in_stock" is used to keep track of available books in the most up-to-date fashion. When every new order enters, the transaction checks the data integrity still holds.

In this approach, "no_of_books_in_stock" becomes a shared state that every concurrent transacton need to access. Therefore, every transaction take turns sequentially to lock the shared state in order to achieve serializability. A choke point is created and the system is not very scalable.

Hence the second approach ...


The BASE approach

Instead of checking against a "shared state" at the order taking time, the order taking transaction may just get a general idea of how many books is available in stock at the beginning of the day and only checks against that. Note that this is not a shared state, and hence there is no choke points. Of course, since every transaction assumes no other transaction is proceeding, there is a possibility of over-booking.

At the end of the day, there is a reconciliation process that took the sum of all orders taken in the day, and check that against the number of books in stock. Data integrity checking is done here, but in batch mode which is much more efficient. In case the data integity is not maintained, the reconciliation process fire up compensating actions such as print more books, or refund some orders, in order to reestablish the data integrity.


Generalizing the Design pattern of BASE

"Eventual consistency" is based on the notion that every action is revokable by executing a "compensating action". However, all compensating actions different costs involved, which is the sum of this individual compensation plus all compensating actions that it triggers.

In BASE, the design goal is to reduce the probability of doing high-cost revokation. Note that BASE is a probablistic model while ACID is a binary, all-or-none model.

In BASE, data is organized into two kinds of "states": "Provisional state" and "Real state".

All online transactions should only read/write the provisional state, which is a local, non-shared view among these transactions. Since there is no shared state and choke point involved, online transactions can proceed very efficiently.

Real state reflects the actual state of the business (e.g. how many books are actually in stock), which always lacks behind the provisonal state. The "real state" and "provisional state" are brought together periodically via a batch-oriented reconciliation process.

Data integrity checking is defer until the reconciliation process executes. High efficiency is achieved because of its batch nature. When the data integrity does not hold, the reconciliation process will fire up compensating actions in order to reestablish the data integrity. At the end of the reconciliation, the provisional state and real state are brought in sync with each other.

To minimize the cost of compensating actions, we need to confine the deviation between the provisional state and the real state. This may mean that we need to do the reconciliation more frequently. We should also minimize the chaining effect of compensating actions.