Random sample consensus (RANSAC)

Random sample consensus (RANSAC) is an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers. It is a non-deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at SRI International in 1981.

A basic assumption is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, though may be subject to noise, and "outliers" which are data that do not fit the model. The outliers can come, e.g., from extreme values of the noise or from erroneous measurements or incorrect hypotheses about the interpretation of data. RANSAC also assumes that, given a (usually small) set of inliers, there exists a procedure which can estimate the parameters of a model that optimally explains or fits this data.

http://en.wikipedia.org/wiki/RANSAC

Tutorial:

http://vision.ece.ucsb.edu/~zuliani/Research/RANSAC/docs/RANSAC4Dummies.pdf



Matlab code:

http://www.mathworks.com/discovery/ransac.html

Python code:

http://wiki.scipy.org/Cookbook/RANSAC

Just for fun RANSAC song:

https://www.youtube.com/watch?v=1YNjMxxXO-E

Corner Detector

Detecting corners is often a good first step in computer vision.  If you can match corners from two images you are well on your way to figuring out how they fit together for example.

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D modelling and object recognition. Corner detection overlaps with the topic of interest point detection.

http://en.wikipedia.org/wiki/Corner_detection


Lecture slide decks:


http://www.cse.psu.edu/~rcollins/CSE486/lecture06.pdf

http://courses.cs.washington.edu/courses/cse577/05sp/notes/harris.pdf

Tutorials:

Python/OpenCV

http://opencv-python-tutroals.readthedocs.org/en/latest/py_tutorials/py_feature2d/py_features_harris/py_features_harris.html

YouTube video:

https://www.youtube.com/watch?v=vkWdzWeRfC4

Matlab code:

http://www.mathworks.com/matlabcentral/fileexchange/9272-harris-corner-detector

Restricted Boltzmann machine

Learning to use RBM's is on my todo list...I'll update when I get around to it.  RBM's are just one technique for deep learning.

The Restricted Boltzmann Machine (RBM) has become increasingly popular of late after its success in the Netflix prize competition and other competitions. Most of the inventive work behind RBMs was done by Geoffrey Hinton. In particular the training of RBMs using an algorithm called "Contrastive Divergence" (CD). CD is very similar to gradient descent. A good consequence of the CD is its ability to "dream". Of the various machine learning methods out there, the RBM is the only one which has this capacity baked in implicitly.

http://bayesianthink.blogspot.com/2013/05/the-restricted-boltzmann-machine-rbm.html#.VCnWzikijjI

This is some Matlab code a guy made of a class he was taking.  It is probably not great but if you are working in Matlab it is probably better than starting from scratch:

https://code.google.com/p/matrbm/

RBM tutorial:

http://deeplearning.net/tutorial/rbm.html#rbm


RBM in scikit-learn:

http://scikit-learn.org/stable/modules/neural_networks.html



A Practical Guide to Training Restricted Boltzmann Machines:

http://www.cs.toronto.edu/~hinton/absps/guideTR.pdf

VLFeat open source library computer vision algorithms

The VLFeat open source library implements popular computer vision algorithms specializing in image understanding and local featurexs extraction and matching. Algorithms incldue Fisher Vector, VLAD, SIFT, MSER, k-means, hierarchical k-means, agglomerative information bottleneck, SLIC superpixes, quick shift superpixels, large scale SVM training, and many others. It is written in C for efficiency and compatibility, with interfaces in MATLAB for ease of use, and detailed documentation throughout. It supports Windows, Mac OS X, and Linux.

http://www.vlfeat.org/

AdaBoost

Note: AdaBoost is extremely sensitive to mislabeled samples in your data. For example, if you are trying to classify transactions as either "fraud" or "not fraud" if you have even one mislabeled, then the classifier will over learn that one bad sample and be useless.  There are other versions of boosting algorithms that try to overcome this but if you have data for which you can not be sure of the labels then consider using some other method.


AdaBoost, short for "Adaptive Boosting", is a machine learning meta-algorithm formulated by Yoav Freund and Robert Schapire who won the prestigious "Gödel Prize" in 2003 for their work. It can be used in conjunction with many other types of learning algorithms to improve their performance. The output of the other learning algorithms ('weak learners') is combined into a weighted sum that represents the final output of the boosted classifier. AdaBoost is adaptive in the sense that subsequent weak learners are tweaked in favor of those instances misclassified by previous classifiers. AdaBoost is sensitive to noisy data and outliers. In some problems, however, it can be less susceptible to the overfitting problem than other learning algorithms. The individual learners can be weak, but as long as the performance of each one is slightly better than random guessing (i.e., their error rate is smaller than 0.5 for binary classification), the final model can be proven to converge to a strong learner.

While every learning algorithm will tend to suit some problem types better than others, and will typically have many different parameters and configurations to be adjusted before achieving optimal performance on a dataset, AdaBoost (with decision trees as the weak learners) is often referred to as the best out-of-the-box classifier. When used with decision tree learning, information gathered at each stage of the AdaBoost algorithm about the relative 'hardness' of each training sample is fed into the tree growing algorithm such that later trees tend to focus on harder to classify examples.

http://en.wikipedia.org/wiki/AdaBoost

Very nice AdaBoost slide deck:

http://cmp.felk.cvut.cz/~sochmj1/adaboost_talk.pdf

Matlab and C++ implementations:

http://graphics.cs.msu.ru/en/science/research/machinelearning/adaboosttoolbox