Gesture classification pipeline

There are a couple gesture classification pipeline which provides a clean and nice framework. Here I am going to list their basic structures.

• Gesture recognition toolkit
• pipeline
• pre-processing
• feature extraction: should be chainable
• classifier
• post-processing 
• methods
• train
• test
• F measure
• precision
• recall

Mahalanobis distance and Gaussian distribution

The Mahalanobis distance is a distance measure that accounts for the covariance or "stretch" of the shape in which the data lies.

$$D_{\text{Mahalanobis}}(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x} - \mathbf{y})^T\Sigma^{-1}(\mathbf{x} - \mathbf{y})}$$

This is very similar to the exponential term in the Gaussian distribution.

It is useful to get an intuitive feel about the standard deviation. In the one-dimensional case, where
$$ p(x) = \frac{1}{\sigma \sqrt{2\pi}}e^{-\frac{(x - \mu)^2}{2\sigma}}$$
the probability at one standard deviation away from the center is \(\frac{1}{e}\) (37%) of the peak probability.

Source:
https://en.wikipedia.org/wiki/File:Normal_Distribution_PDF.svg

Go and Scala

Start to learn Go and Scala. I'm going to jot down some notes here.

Both Scala and Go have similar type declaration syntax, with type name on the right.
Scala:

class Person(first: String, lastName: String)

Go:

func needInt(x int) int {return x * 10 + 1}

Machine learning

Perceptron

Repeat until convergence:

For t = 1 ... n

1. \(y'\) = sign(\(\underline{x}_t\cdot\underline{\theta}\))
2. If \(y'\ne y_t\) Then \(\underline{\theta} = \underline{\theta} + y_t\underline{x}_t\), Else leave \(\underline{\theta}\) unchanged.

Kernel form of the perceptron

• Definition: for any \(\underline{x}\), define \(g(x) = \sum_{j=1}^n\alpha_jy_jK(\underline{x}_j,\underline{x})\) where \(K(\underline{x}_j,\underline{x}) = \phi(\underline{x}_j)\cdot\phi(\underline{x})\)
• Repeat until convergence:
• For t = 1 ... n
1. y' = sign(g(\(\underline{x}_t\))
2. If \(y'\ne y_t\) Then \(\alpha_t = \alpha_t + 1\)

Algorithms for inference

Definitions

Chordal graph: a graph is chordal if any cycle of the graph of size >= 4 has a chord.

Formulas

Parameter estimation for HMM with Gaussian distribution for emission probabilities:

$$\underline{\mu}_s^t = \frac{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)\underline{x}_{i,j}}{\sum_{i=1}^n\sum_{j=1}^mp(S_j = s|\underline{x}_{i,1}\dots\underline{x}_{i,m};\theta)}$$

General form of EM algorithm

The basic idea is that we want to maximize the likelihood of the "complete" data. Because we don't know the "complete" data, we need to take the expectation of the "complete" data with respect to the probability distribution of the hidden variables.

Let \(\mathbf{Z}\) denote all the hidden variables for all the examples, and let \(\boldsymbol{\theta}\) be all the parameters for the probability model. \begin{aligned}\boldsymbol{\theta}^{(i+1)} &= \underset{\boldsymbol{\theta}}{\arg\max}\sum_{\boldsymbol{z}}P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})L(\boldsymbol{x}, \boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{\theta}) \\ &=\underset{\boldsymbol{\theta}}{\arg\max}E_{P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})}L(\boldsymbol{x}, \boldsymbol{Z}= \boldsymbol{z}|\boldsymbol{\theta}) \end{aligned}
The E-step is the computation of the summation, which is the expectation of the log likelihood of the "completed" data with respect to the distribution \(P(\boldsymbol{Z} = \boldsymbol{z}|\boldsymbol{x}, \boldsymbol{\theta}^{(i)})\).

Complexity theory

The class NP consists decision problems with solutions that can be "checked" in polynomial time. Equivalently, it can also be defined as a set of decision problems solvable in polynomial time via a "lucky" algorithm. This is a nondeterministic model where an algorithm makes guesses and then says YES or NO.  The name "NP" stands for "nondeterministic polynomial time".

A problem is in the class NP-complete, if it is in NP and is as "hard" as any problem in NP. So NP-complete problems are the hardest problems in NP.

Examples of NP-complete problems:

• Knapsack (pseudopolynomial, O(nS) where n is number of items and S is the size of the knapsack)
• Traveling salesman problem
• SAT
• Tetris
• 3-coloring a given graph

MIT 6.006 notes: http://courses.csail.mit.edu/6.006/fall11/lectures/lecture23.pdf

TED talk: How movies teach manhood

I really enjoyed this talk. Colin Stokes is both eloquent and humorous. I agree with his observation that there are movies that teach girls to fight against patriarchy (like many Disney movies), but they are all tailored to girls and there are very few movies that teach boys to fight against patriarchy. As a result, there are no role models for boys to know how to respect women and treat them as equals. In a quest to achieve equality, we need work on both sides: encouraging girls to pursue their dreams without restrained by stereotypes and fostering the idea that female leadership is as normal as male leadership in boys. That's why Stokes asks for more movies that send positive messages to boys: that cooperation is heroic, and respecting women is as manly as defeating the villain.

In his talk, he mentioned the Bechdel test for movies. It is used to identify gender bias in fiction. I've heard this test before on a graduate women mailing list about showing movies that pass the test. The test has 3 requirements:

1. Are there at least 2 named female characters?
2. Did the two talk to each other?
3. Did they talk about something other than men?

You have to agree that these these criteria are some what simplistic, but it can be a good start. Even with this these simple criteria, there are only about 50% of the movies in a year pass it.

Stokes also mentioned the movie Brave, which is an nontraditional princess movie. Unlike the usual princess movies which resolve around a male romantic attachment, this movie is purely about mother-daughter relationship. There is no point in the movie that the princess becomes romantic with a male character. This is indeed quite rare in Hollywood movies. It's good that Brave also wins the Oscar for the best animated film. 

Matlab save path

Matlab allows you to add paths to the search path and you are supposed to be able to save it so that you don't need to add the paths again the next time. However when I tried to save the paths, the new paths didn't show up when I restarted Matlab. I'm running MATLAB R2012a and Ubuntu 12.04.

This post helps me solve the problem. After saving the new paths, a new file is created in ~/Documents/MATLAB because I do not have write permission in the default installation location. However the new pathdef.m file is not read when Matlab starts. To solve this, you can add startup.m in ~/Documents/MATLAB if that's your urserpath. Add the following line to the file:

path(pathdef)

On Windows 7, when you set path through the dialog box, it will add the new paths to the pathdef.m file in the installation folder. This will affect other users' path. To add the paths so only you will see it, you can do the similar thing before by adding a startup.m file in C:\Users\[username]\Documents\MATLAB if that is your statup path. On Windows, it won't ask you to specifiy a new file to save the paths, so you need to copy the pathdef.m file from the installation folder (default is C:\Program Files\MATLAB\R2013a\toolbox\local\pathdef.m) to the userpath.

However, one problem I encountered when I start from the userpath is that some functions in the parallel computing toolbox no longer work. Turns that there seem to be some conflicts between the toolbox and the Bayesian Network Toolbox (BNT) I'm using. After moving the BNT to the bottom of the search path, everything works again.