RANSAC for Regression With Contaminated Responses

Why Use RANSAC?

Least-squares regression can be pulled far from the pattern in most observations by a few extreme responses. Robust regression methods can reduce this sensitivity, but RANSAC takes a different approach: it repeatedly fits a model to a small randomly selected subset, then asks whether that model is supported by many of the remaining observations. The method is particularly useful when a substantial fraction of responses may be contaminated and a large group still follows a common regression pattern.

RANSAC stands for Random Sample Consensus. It is an algorithm for finding a candidate fit supported by a large consensus set; it is not, by itself, a probability model for the data or a method for calculating standard errors and confidence intervals. Its result depends on choices such as the residual threshold, the number of random trials, and how ties between candidate fits are handled.

Model, Contamination, and Inliers

For simple linear regression, write the response for observation \(i\) as \(y_i\) and its predictor value as \(x_i\). The intended regression pattern for the uncontaminated observations is

y_i=\beta_0+\beta_1x_i+\epsilon_i.

Here \(\beta_0\) is the intercept, \(\beta_1\) is the slope, and \(\epsilon_i\) is the ordinary deviation from the pattern. In a response-contamination problem, some recorded \(y_i\) values may instead be far from the relationship shared by the main group. RANSAC aims to find that main group without allowing those extreme responses to determine the fit.

The useful working conditions are that a sufficiently large group shares one regression relationship, that its residuals are small enough under a chosen threshold, and that a sampled subset can uniquely determine a candidate fit. For a line with an intercept, a minimal subset contains two observations with different \(x\)-values. For a regression with \(p\) predictors and an intercept, a minimal subset has \(p+1\) observations whose predictor values allow the coefficients to be determined. A subset that cannot determine a unique fit is degenerate and cannot serve as a candidate.

Definition: Given a candidate fitted value \(\hat{y}_i\) and a nonnegative residual threshold \(\tau\), the residual is \(e_i=y_i-\hat{y}_i\). Observation \(i\) is an inlier for that candidate if \(|e_i|\leq\tau\); otherwise it is an outlier for that candidate. The consensus set is the collection of inliers, and its size is the candidate’s consensus count.

The threshold \(\tau\) is expressed in the units of the response. It should reflect how much residual variation is compatible with the intended pattern; there is no universal threshold that suits every data set. A threshold that is too small can exclude genuine observations with ordinary noise, while one that is too large can count contaminated responses as inliers. The classification is relative to the candidate and threshold, not a permanent label declaring an observation erroneous.

The RANSAC Cycle

A basic RANSAC procedure repeats four actions. Each candidate is assessed against all observations, not just the subset used to fit it.

Sample a minimal subset.
Choose the required number of observations at random. Skip a subset if it is degenerate and cannot determine a unique fit.

Fit a candidate.
Use only the sampled observations to calculate the candidate regression coefficients.

Count consensus.
Calculate residuals for all observations and count those satisfying \(|e_i|\leq\tau\). Retain candidates with a large consensus count.

Select and refit.
Select the candidate with the largest consensus set (using a stated tie-breaking rule if needed), then refit the regression using that set.

The refit matters because a candidate based on a minimal subset is determined by very little data. Once a promising consensus set has been found, fitting to all its observations generally uses the supported data more effectively. In a common version, residuals are then recalculated from the refitted model and the inlier set may be updated. If an implementation does this, it should state the update rule; the final fit and set must be understood as the result of that specified procedure.

Worked Example: Finding a Line Despite Four Contaminated Responses

Consider this hypothetical data set. Suppose the first five responses follow a line and the last four are contaminated. Choose the residual threshold \(\tau=0.5\) response units.

\(x_i\)	\(y_i\)
0	1
1	3
2	5
3	7
4	9
5	18
6	-4
7	25
8	-10

Suppose one random minimal subset contains \((0,1)\) and \((1,3)\). These points determine a line with slope \((3-1)/(1-0)=2\) and intercept \(1\), so the candidate is \(\hat{y}=1+2x\). Its residuals are:

\begin{array}{c|rrrrrrrrr} x_i&0&1&2&3&4&5&6&7&8\\ e_i&0&0&0&0&0&7&-17&10&-27 \end{array}

The five observations at \(x=0,1,2,3,4\) have \(|e_i|\leq0.5\), while the other four do not. The candidate therefore has a consensus count of five. Refit the line using just those five inliers. Their means are \(\bar{x}=2\) and \(\bar{y}=5\). The slope is

\hat{\beta}_1= \frac{\sum (x_i-\bar{x})(y_i-\bar{y})} {\sum (x_i-\bar{x})^2} =\frac{20}{10}=2, \qquad \hat{\beta}_0=\bar{y}-\hat{\beta}_1\bar{x} =5-(2)(2)=1.

The refitted line is again \(\hat{y}=1+2x\). In this deliberately clear example, the candidate already matches all five inliers exactly, so the refit does not change the coefficients. In less exact data, refitting can change them. The algorithm has identified a large group consistent with a line without letting the four extreme responses set the fit.

How Many Random Subsets?

A limited number of random draws may fail to select even one all-inlier minimal subset. A useful calculation estimates how many trials are needed to make that failure unlikely. Suppose there are \(n\) observations, \(I\) of them are inliers, and each random subset of size \(m\) is chosen uniformly without replacement. The probability that one subset consists entirely of inliers is

q=\frac{\binom{I}{m}}{\binom{n}{m}}.

If the trials are independent, the probability that none of \(R\) trials is an all-inlier subset is \((1-q)^R\): each trial fails with probability \(1-q\), and the probability of failing on every trial is the product of those probabilities. Thus the probability of at least one all-inlier subset is \(1-(1-q)^R\). To make this probability at least a target confidence \(c\), solve

1-(1-q)^R\geq c \quad\Longrightarrow\quad R\geq\frac{\log(1-c)}{\log(1-q)}.

Because the number of trials must be a whole number, round the result up. This calculation concerns the chance of drawing an all-inlier subset, not a guarantee that a useful model will be selected: the subset must also be nondegenerate, the inliers must support the intended relationship, and the residual threshold must be suitable.

Worked Example: Choosing a Trial Count

Use the nine-observation example above, where five observations belong to the main group and a line requires a subset of \(m=2\). Assume uniform sampling of pairs without replacement. The chance that one pair contains only inliers is

q=\frac{\binom{5}{2}}{\binom{9}{2}} =\frac{10}{36} =\frac{5}{18}\approx0.2778.

For a target chance \(c=0.99\) of drawing at least one all-inlier pair, the required number of independent trials satisfies

R\geq \frac{\log(1-0.99)}{\log(1-5/18)} =\frac{\log(0.01)}{\log(13/18)} \approx14.15.

Rounding up gives \(R=15\) trials. Under these assumptions, the chance of at least one all-inlier draw is \(1-(13/18)^{15}\), which is at least \(0.99\). In practice the number of inliers is not known in advance, so a trial-count calculation must use an estimate or be updated as the search proceeds.

Thresholds and the Final Refit

The same data can produce different consensus sets under different thresholds. This does not mean one threshold is automatically correct: it means that the threshold is part of the method and should be chosen in the response’s units with the expected ordinary variation in mind. The next example shows how a candidate’s consensus is assessed and how refitting can use the selected observations.

Worked Example: Classifying Inliers and Refitting Noisy Data

For this hypothetical data, take the threshold to be \(\tau=0.5\) response units. A sampled pair \((0,2)\) and \((1,5.2)\) gives the candidate slope \((5.2-2)/(1-0)=3.2\) and intercept \(2\). The complete data are \((0,2),(1,5.2),(2,8.1),(3,11.1),(4,4),(5,40)\).

The candidate is \(\hat{y}=2+3.2x\). At \(x=2\), the fitted response is \(8.4\), so the residual is \(8.1-8.4=-0.3\). At \(x=3\), the fitted response is \(11.6\), giving residual \(11.1-11.6=-0.5\). Both satisfy \(|e_i|\leq0.5\). The two sampled observations have residual zero. At \(x=4\), the residual is \(4-(2+3.2(4))=-10.8\), and at \(x=5\), it is \(40-(2+3.2(5))=22\). Those two observations are not inliers. The consensus set therefore contains the first four observations.

For the refit, \(\bar{x}=1.5\), \(\bar{y}=6.6\), \(\sum(x_i-\bar{x})^2=5\), and

\sum(x_i-\bar{x})(y_i-\bar{y}) =6.9+0.7+0.75+6.75=15.1.

Thus the refitted slope is \(15.1/5=3.02\), and the intercept is \(6.6-(3.02)(1.5)=2.07\). The refitted line is \(\hat{y}=2.07+3.02x\). It is supported by the selected four observations; it is not a claim that the two excluded responses are errors or that the line describes every possible observation.

What RANSAC Can and Cannot Establish

RANSAC is useful when a large, coherent group is expected to share a regression pattern but a substantial number of responses may be far from it. Unlike a fit based on squared residuals over the whole data set, candidate generation can isolate a small subset first, and consensus scoring gives each observation a threshold-based inlier or outlier status. Its strengths depend on the existence of a dominant group and on appropriate choices of threshold and trial count.

A large consensus count is evidence that many observations lie near a candidate under the chosen residual rule. It does not prove that the candidate represents the scientifically meaningful relationship, explain why observations disagree, or justify deleting observations. An unusual response may be a recording problem, a different process, or a genuine case that matters to the question. Investigate the observations and report the choices made.

The procedure described here targets contamination in the responses, with predictor values treated as usable for fitting and residual assessment. RANSAC should not be taken as a general solution to every unusual predictor configuration: a problematic predictor value can affect which minimal subsets are selected and how a fitted relationship behaves. The limits of residual-based robust methods in the presence of high leverage are a separate issue.

Common Mistakes

Counting only the sampled observations. A minimal subset defines the candidate; its support is assessed by calculating residuals for all observations.
Treating the threshold as unit-free. The residual threshold has the same units as the response, so a value must be interpreted in context.
Assuming a high trial count guarantees the right model. More trials improve the chance of drawing an all-inlier subset under the stated sampling assumptions, but do not fix a poor threshold or an unsuitable model.
Calling every non-inlier an error. The label depends on a particular candidate and threshold. It signals disagreement with that fit, not the cause or status of the observation.
Reporting only the minimal-subset fit. The selected consensus set should ordinarily be refitted, and the resulting fit should be described as conditional on the stated RANSAC choices.

Key takeaway: RANSAC repeatedly fits minimal subsets, scores each candidate by the number of observations within a chosen residual threshold, and refits the largest consensus set. Its robustness depends on a sufficiently large shared pattern, a suitable threshold, and enough valid random trials.

Check Your Understanding

Try these questions without looking back.

For a simple regression line with an intercept, how many observations are needed in a minimal subset, and what makes a two-point subset degenerate?
If a candidate predicts \(12.4\) response units for an observation with observed response \(13.0\), is it an inlier when \(\tau=0.5\)? Explain using the residual rule.
In the nine-observation example, why does the all-inlier-pair probability use \(\binom{5}{2}/\binom{9}{2}\), rather than simply \(5/9\)?
What does a 0.99 target in a trial-count calculation describe, and what does it not guarantee?
Why should an observation outside the selected consensus set not automatically be described as a data error?