The Quest for the Proper Proper Subset Classification

Switch to SVM 

We’ve switched from logistic regression with HOG features to Support Vector Machines using a variant of SIFT descriptors. 

Our code is a slightly modified version of this vl_feat example code.

Here is a description of what the code does, as far as I currently understand it:

The code first trains a bag of visual words “vocabulary” based on PHOW descriptors (a variant of dense SIFT, implemented in vl_feat and described in this paper: Image Classification using Random Forests and Ferns. The "vocabulary" is created by running k-means on the PHOW descriptors.

The vocabulary comes from a subset of the training data, and afterwards all the

training data is given a feature description based on PHOW descriptors and the vocabulary.

A feature map is then computed using the chi-squared kernel.  

The SVM solver is called "pegasos" and is based on this paper

The classification is done through all-vs-one classification, I'm thinking about possibly altering it to training a bunch of binary classifiers then doing a decision tree or a voting thing. Also, I need to make the output soft for the parser.

This is a good tutorial for SVM's.

Experimental Results

Methodology: We have 300 samples for each of the 17 classes. I wrote a python script that randomly selected 20 of each of the class examples to be "holdout" data. I haven't modified the code yet to do cross-validation.

The 20 holdout data samples per class were used to create various formulas in first-order logic (the definition of function and the definition of proper subset). When the segmentation and extractor get better new novel data will be used instead of these hold-out samples for testing the effectiveness of the system.

At first I used 50 random samples as training and the remaining 230 as test. I observed that most of the errors were due to classifying symbols as negation.

Observing the (scores,classes) output of the svm one-vs-all classifier, I saw that for the "negation errors" the correct label usually was the 2nd most likely.


Here is an example of the scores for a "z" that was mistaken for a "negation":

    scores   class
   -0.2888   11 (neg)        
   -0.3795   17 (z)      
   -0.4663    9 (left paren)        
   -0.4823    7 (if then)        
   -0.5354   12 (or)            
   -0.5367   16 (y)        
   -0.5602   10 (ne)          
   -0.5620   13 (right paren)            
   -0.5640   14 (subset)        
   -0.5786    4 (elem)      
   -0.6220   15 (x)        
   -0.6455    2 (R)          
   -0.6618    5 (exist)      
   -0.6747    3 (and)      
   -0.6786    1 (F)      
   -0.7181    6 (for all)    
   -0.7594    8 (iff)      




I decided to create alternate samples that used a tilde instead of  the hook-like symbol for negation, to see how that would affect the results.

In the end I trained 4 models and tested each of them on 2 different formulas:

Models:
1) 50 train
2) 230 train
3) 50 train (tilde for negation)
4) 230 train (tilde for negation)

Formulas:

1)Function definition

Correct classification for function definition 

2)Proper Subset definition

Proper classification, definition of proper subset

PARAMS that may need to be tweaked:

There are a few parameters in the svm code. I need do more testing to see how tweaking these will affect classification results.

Number of words: This is the "vocabulary" created by k-means. It was originally set to 300, but I increased it to 600. I'm not sure yet if this helped or hurt, more testing is needed. 

K-means algorithm: The vl_feat implementation of k-mean can use the standard Lloyd's algorithm or UCSD professor Elkan's accelerated k-mean's algorithm. Current results use Elkan's algorithm, but I'm not sure if this sped-up version gives the same results for our (relatively) small dataset.

Kernel:  The feature map is computed using the vl_homkermap function. This function has a few parameters and potentially other kernel mappings could be swapped for it.

Confusion Matrices




"Hook" negation:

50 training examples, 230 test

230 training, 50 test




Tilde negation:

50 train, 230 test, tilde for negation

230 train, 50 test, tilde for negation




Parsing Results for Holdout Data Formulas

Function Formula(7 symbols from holdout):

50 training ( 0 errors!)

230 training ( 0 errors!)

50 training with tilde for negation (2 errors)

230 training with tilde for negation (1 error, left paren for x)

Proper Subset Formula (30 symbols from holdout):

50 training (7 errors)

230 train (8 errors)

50 training with tilde for negation (4 errors)

230 training with tilde for negation (4 errors)

Current Goals:

Classification seems "good enough", next to do is: 

1) Implementing the graph structure/Context Free Grammar for parsing

2) Improving segmentation and extraction 

3) Expanding the data to include numbers.

Prototype: Iteration 1

All major parts of the pipeline have been touched now, and given basic functionality.

For ease of implementation, we decided that working with a proper subset of 1st order logic would be a reasonable goal. This allows us to get a "working" prototype while side-stepping issues like superscripts/subscripts and bounding box problems. As we get this prototype to increase accuracy on first-order logic, we will look into ways to expanding it to deal with more complex mathematical structures.

The subset of first-order logic that we will be working with for now includes the following symbols:

16 symbols total

It is quite literally a *proper* subset, as it only includes the proper subset symbol! In this scheme equals is created using not and not-equals.

New Dataset:

To help with this goal we have started creating a second toy dataset, made out of 300 examples each of 16 symbols. The scripts that do preprocessing and turn these images into matrices has been turned into functions that automate a lot of what we were doing tediously by matlab commands before.

So far we have 5 symbols finished.

Extraction:

Oren wrote code that takes the bounding boxes from the segmenter and extracts the characters into individual images. We are trying to keep this code as independent of the segmenter as possible. The extractor works well, but it is given lots of garbage by the segmenter.  

The next iteration of this code will have to output positional information about the symbols as well, so that a graph structure can be created to help the parser.

Classification:

We have trained on the 5 symbols we have data for (forAll, exist, x, y, R,). Accuracy was greater than chance! However, only 2 classes were ever predicted (exist and x) so the 40% didn't seem very meaningful.

The next step with the classifier is the find new features, and to modify it so that it gives "soft" predictions of the top few most probable classes. This soft output will be helpful for the parser.

Parsing:

I wrote a simple substitution based linear parser in python using scipy/numpy. This was a task that was much easier doing in python than matlab. Creating complex graph structures and parsing them is not something I am looking forward to doing in matlab, but would be a joy in python, so I'm planning on using python for this process for the time being.

If we have time, the code may be ported to matlab (or the rest of the matlab code might be ported to python!!)!

Prototype Iteration 1 Demo:

To test the prototype the following formula was scanned:

This sentence is the definition of a function.

We ran it through the segmenter, which output 21 boxes given these 7 symbols. 

Of those, 6 were garbage from a smear on the paper. The rest were slight translations of the correct character extraction. 

We cheated and filtered out the garbage and repetitions for the sake of a first demo. The seven selected images were then run through the classifier. The classifiers output was then run through the parser, resulting in the following .tex file:

LaTeX generated by parser.

Which results in this after pdflatex:

Our systems prediction 

While the original samples true results should have been:

The correct classification/parsing

TODO:

• Classification the most important now, we need to find features with greater discriminative power
• We have decided to read at least one computer vision paper a week in order to get ideas and get a good feel for what we should make our final paper look like.
• We need to start work on outputting the graph structure for the parser.

Looking ahead (perhaps too far), the following is a tentative list of how we will expand the scope of this project as the 1st order logic accuracy increases:

1) add numbers

2) add subscripts/superscripts

3) Discrete Math symbols

4) Calculus symbols

5) Linear Algebra (matrices)

6) ???????

7) Profit!!

I expect to get to at least 3, possibly 4. Once work begins on creating the graph structure for parsing, we can see how distant a goal linear algebra is. 

Pipeline + random updates

To help with planning the project I created a diagram of the planned pipeline for HERC using http://www.diagram.ly/. The most updated pipeline image can be found in the repo here.

As shown, the pre-processing, localization, and classification components have "Basic Functionality" implemented, though they have a long way to go until they have "Decent Functionality".

A current goal is the try to get all the components "Basic Functionality" implemented (even if they don't exactly "work") so we can do ceiling analysis. Ceiling analysis is where you see how much a part of the pipeline working 100% would increase overall performance of the system. To do this you iteratively hand feed correct results from each part to the rest of the parts and see how much the entire systems accuracy increases.

This is a method to help prioritize which parts of the pipeline to work on. More information can be found on the Stanford ml-class preview videos site in unit XVIII video "Ceiling Analysis: What Part of the Pipeline to Work on Next "

________________________________________________________________________

Classifier Improvement

Last post, we implemented cross validation and discovered that our classifier didn't perform better than chance. We were just using the raw pixels so this wasn't too surprising.

I found a file on the matlab fileexchange for HOG(Histogram of Oriented Gradients) features. Putting our toy dataset through it transformed a 1000x24963 matrix into a 1000x83 matrix.

This significantly increased the speed it takes to run from 8 minutes for one fold to 5 folds in 32 seconds.

The accuracy also went up, from 5.7 to 11.4! Which is *better* than chance. Confusion matrices have been generated for each fold and put in mistakes.mat in the repo, but we haven't interpreted them yet to figure out where to go from here.




The speed increase made it easier to explore the effect of different values of the lambda parameter for regularized logistic regression .

High values of lambda didn't help

Exploring closer to .1

The values  
[0 0.0900 0.1000 0.1100 0.1250 0.1500 0.2000 0.5000 0.7500 1.0000  
10.0000 20.0000] were tested.


The corresponding mean cross-validation accuracies were:

[10.5000   11.2000   11.4000   10.6000   11.2000   10.6000   10.3000    9.9000   10.3000 10.7000    9.6000    9.7000]



In the end .1, the value that lambda had originally been set to, worked best.

Accuracies for different values of lambda at each fold can be found here.


___________________________________________________________________________

Localization Update

We still haven't gotten around to figuring out how use some of the infty dataset. We need to parse some comma-separated values in .txt files to do this. Some of the dataset, however, was given in raw images. I passed these through the localizer to see how it performed. It does well (which is to be expected, as these aren't noisy handwritten images), but still has the same problems with non-connected parts.

 ____________________________________________________________________________

Misc

A few things accomplished since monday:

• Cleaned up some code (vectorizing stuff,  replacing own implementation of a few things with matlab commands, added/deleted/fixed comments)
• Started research on making synthetic data to expand toy dataset
• Made folder of each toy dataset sample as an individual image, to help with feature extraction/testing

Cross-Validation

When training a classifier, data is separated into a training set, and a testing set. The training set is used to learn about the aspects that differentiate items, and the testing set is used to evaluate the results. While it is tempting to use all the data to train the classifier, this can cause problems if the classifier merely memorizes the training set, and fails at classifying novel samples.

This effect is called overfitting.

(image from http://victoranchidin.blogspot.com/2009/10/overfitting-vs-overtraining.html)

In order to avoid overfitting, there is a technique called cross-validation. Cross-validation takes a dataset, breaks it into partitions, and uses them to separately train and test a classifier. By using the data to separately train and test in different combinations, it is easier to see how well a classifier performs.

(image from nltk)

Cross-Validation helps prevent fallacious reasoning when testing hypotheses suggested by the data (http://en.wikipedia.org/wiki/Testing_hypotheses_suggested_by_the_data). The problem occurs when a trend is found in data, then that same data is used to evalute if that trend is real. According to wikipedia, this is sometimes called a type III error.

We first implemented cross-validation the easiest way that came to mind, manually breaking our data into partitions using if statements and careful matrix indexing. There is also a matlab command, cvpartition (http://www.mathworks.com/help/toolbox/stats/cvpartition.html), which breaks your data up for you. Later on, we might switch to this for analyzing our results.

 Results of running 5-fold cross-validation with a few different lambda values.

lambda	fold 1	fold 2	fold 3	fold 4	fold 5	average
0.1	3.5	6.5	8	4	6.5	5.7
.5	4	7.5	4	6	4.5	5.2
1	4	7	5	5	6.5	5.5
10	4	9	5.5	5.5	5	5.9
100	3.5	6	4.5	5.5	4	4.8

As you can see, our accuracy is not very good. With 20 classes, ~5% accuracy isn’t better than a classifier that always outputs the same value. Our low accuracy could be due to our small sample size. Our next step is to collect more data and see if this could improve results.

It also takes a long time to train our classifier (~8 minutes). It might be possible to reduce the size of the image files in order to decrease the runtime, and see if that makes a difference when training with more data.

Current Classifier results

I’ve written code that takes our images and creates a data_x matrix where the rows are character samples and a data_y matrix of corresponding class identities. We fed these into code I wrote for the stanford ml-class. The code builds an one-vs-all classifier using regularized logistic regression.

Originally it reported a 80.7% true positives rating on the training set, but after Oren’s preprocessing script removed some noise true positives shot up to 90.8%!


These numbers are exciting but they don't actually mean much because we didn't do cross-validation or have a training/test set division. This was mostly to make sure the toy dataset would work with the classifier. Adding correct methodology and increasing accuracy are both high priorities now.

There are 20 classes that have 50 samples each, for a total of 1000 samples.

Below is the confusion matrix:

row/col legend:
1 +
2 (
3 )
4 =
5 f
6 -
7 /
8 ^
9 alpha
10 x
11.      0
12.      1
13.      2
14.      3
15. 4
16.      5
17.      6
18.      7
19.      8
20.     9

Classifier TODO:
Look into ways to increase accuracy.
Cross validation
Different lambda parameters
Run the code on a larger dataset.
Consider alternate ways to classify (SVM?)