RANdom SAmple Consensus (RANSAC)

Ok, so the acronym is really a stretch, but RANSAC is a conceptually simple and efficient way of probabilistically estimating the parameters of a model.

I'll illustrate with a simple example: let's say we have 20 people in a class and we want to choose 4 representatives who, well, represent the opinions of the class. We'll run a hundred elections and each will feature four randomly chosen candidates. The four candidates that get the most votes win and as a result, we can have a subsample of the original population that can explain (most of) the opinion of the whole. There's also the darker side to this algorithm that discards the opinions of voters who don't choose the winning candidates, but no one said politics is easy.

That's it!

But isn't it slow? Compared to a closed form solution, sure. If we had a model that was able to choose the four representatives as the four with the highest SAT scores, then yes, we could find our reps much faster. A closed form, however, is sometimes hard or even impossible to find.

But isn't it inaccurate? There are more thorough methods like the Hough transform in computer vision that systematically searches the entire parameter space, but this can be very slow if you have a lot of parameters.