I’ve decided to start writing briefly and informally about technical things, so that I could understand them better, and so that someone else might get some insight. I’ll be writing these under the appropriately vague title of “Stan Explains Things”.
This first one is about a statistical algorithm called Random Sample Consensus, or RANSAC. Very often in statistical modeling, you will try to fit a model to some data. For example, you might have a bunch of points in a plane that you want to fit a line to. In many cases, the underlying and often unexamined assumption is that you are trying to explain all of the data with your model. However, there are certain cases in which it makes sense to fit your model to only the part of the data that matches it best, and ignore the rest. This is what RANSAC does.
Let’s go back to the line-fitting example, and imagine that some subset of points trace out a very clear line while the rest of the points are way off the line (see figure below). The set of points consists of outliers (red) and inliers (blue).
Finding the line that best fits the inliers is a chicken and egg problem.
If you knew the inliers, then you could easily fit a line to them (using e.g. Least Squares). But the inliers and outliers are not labeled — you have to discover what they are automatically. On the other hand, if you knew the line, then you could find the inliers by filtering out points that are “too far away” from the line. Well, with a chicken and egg problem, you have to start somewhere. A reasonble thing to do would be to start with a guess of what the inliers are, and from that compute a best fit line, from which we can once again compute inliers. If we do this right, we can iteratively improve both the inliers and the best fit line.
What’s a reasonable first guess? Well, we are trying to fit a line, and we know two points define a line. So let’s pick two random points and draw a line through them. After that, we can label the inliners and outliers and fit a line to the inliners, and so on. Read more details at the Wikipedia page: http://en.wikipedia.org/wiki/RANSAC.
RANSAC is often used for image registration (aligning two or more images to a common pose). The process goes something like this. First, identify common visual “points of interest” in each image (using something like SIFT). If a certain feature is visible in both images, it should ideally be labeled as the same thing. This gives us a set of correspondences between images. Then, assume that the projected positions of corresponding points are related via an affine transformation (i.e., that they are scaled, rotated, sheared, or translated versions of each other, or some combination of all of these). The goal is to find the parameters of that transformation.
Finding the correct affine transformation is just like the line fitting example above. Images are very noisy, and spurious or misidentified points of interest are common. Hence, there will be points that are clearly related via an affine transformation, but there will also be a lot of outliers that don’t fit this transformation at all. RANSAC can handle this.
computational amusement 
