Linear separability

Overview

A set is linearly separable when each of its points can be scored by one linear functional so that it beats every other point, which is a one-versus-rest test. Two sets X and Y are separated when a single threshold puts all of X above and all of Y below the same functional 1801.03421 §2. The shared invariant across the variants below is that the separating rule is a dot product with one vector plus a scalar threshold. What differs is how the vector is chosen and how likely the separation is.

In the card on this page, the authors ask how often random samples in high dimension have this property. Their answer is a set of probability lower bounds, for three sampling models, and a procedure that uses the same geometry to correct a deployed system 1801.03421 §3.1 §3.2.

Variants

Uniform ball: one point against the rest

Draw M points i.i.d. uniformly from the unit ball in R^n, and fix a radius ratio 0 < r < 1 with ρ = sqrt(1 − r²) 1801.03421 §3.1, Thm. 3.1. The direction of the last point itself is the separating functional, with threshold r. The probability that this works for that one point is at least 1 − r^n − 0.5(M − 1)ρ^n 1801.03421 §3.1, Thm. 3.1(a). Requiring it for every point, or for every pair, gives weaker bounds with more terms 1801.03421 §3.1, Thm. 3.1(b–c). The paper's corollary turns these into an upper limit on M for a chosen failure level; the paper says this limit grows at least exponentially with n 1801.03421 §3.1, Cor. 3.1. Card: Blessing of dimensionality.

Product distribution in a cube

Here the coordinates are independent, each in [0, 1], with variances bounded below by σ_0² > 0. Let R_0² be the sum of the coordinate variances and fix 0 < δ < 2/3 1801.03421 §3.1, Thm. 3.2. The paper bounds the chance that centred norms concentrate within a factor (1 ± δ), and that each centred point has small inner product with the direction of the last one. The bound has two exponential terms, one per point and one per pair 1801.03421 §3.1. The paper says the results extend to ellipsoids, Gaussians and weakly dependent variables, but gives no proof for those extensions 1801.03421 §3.1.

Tuples of m points

The question changes: can a group of m points from one set be separated from another set X by one functional? The paper takes the functional to be the normalised mean of the tuple 1801.03421 §3.1, Thm. 3.3. The bound depends on two correlation parameters, β1 and β2, that describe the pairwise inner products inside the tuple. The paper notes two regimes. If the tuple points are uncorrelated, the bound falls as m grows. If they are positively correlated, the bound does not depend on m 1801.03421 §3.1. How to choose β1 and β2 for real data is not stated.

Corrector and knowledge transfer

This variant is a procedure rather than a bound. Each recorded input becomes a vector, and inputs where a student system disagrees with a teacher, or with external checks, form the error set Y 1801.03421 §3.2 §3.3 alg. 1. The error points are centred, whitened and split into positively correlated clusters. For each cluster, the functional is a Fisher-type direction, computed against the rest of the set, and its threshold is the smallest score the cluster receives 1801.03421 alg. 1, step 2b. The paper reports that such correctors can be cascaded 1801.03421 §3.2 fig. 2. The only empirical result is a qualitative plot for a pedestrian detector with dimension 2000, taken from earlier work 1801.03421 §3.2 fig. 3. Compare Linear probing, which fits a linear head on a frozen network but does not use these bounds.

When to use which

Dimension rule of thumb: the paper's conclusion suggests that after whitening, dimensions of about 100 or more, with up to about 10^6 points, give more than 99% probability for the separation results. The paper calls this a rule of thumb, not a theorem 1801.03421 §4.

Implementation sketch

The common core is a dot product with a unit vector and a threshold. The sketch below is the exact one-versus-rest test on a given sample, using the ball functional. The probability statements are separate and are not computed here.

# Exact test: is point i cut from the others by the ball functional?
# [arxiv:1801.03421 §3.1, Thm. 3.1(a)]
# Input:  points (M, n) inside the unit ball; index i; ratio r in (0, 1)
# Output: True if x -> (x, unit_i) > r holds for x_i and < r for all others
def separates_point(points, i, r):
    # Direction of the point itself; no fitting is needed  [§3.1]
    x_i = points[i]
    norm_i = norm(x_i)
    if norm_i <= r:
        return False
    unit_i = x_i / norm_i
    # Every other point must score below the threshold  [§3.1, Thm. 3.1(a)]
    for j in range(len(points)):
        if j != i and dot(points[j], unit_i) >= r:
            return False
    return True

For the corrector variant, the core step is the Fisher-type direction w = (Cov(rest) + Cov(cluster))^(−1) (mean(cluster) − mean(rest)), with threshold equal to the smallest score in the cluster [arxiv:1801.03421 alg. 1, step 2b]. The paper gives no ridge term for the matrix inversion, so a singular sum has to be handled by the implementer.

Contradictions

None known across papers, because this page uses one source. Within the source, the card's compile check found that its hand calculations of the union bound in Proposition 2.1 and of the second bound in Corollary 3.1 did not reproduce the stated limits. Treat the theorem statements as the reference and derive any limit you use 1801.03421 §2 §3.1, Cor. 3.1.

Papers

• Blessing of dimensionality: stochastic separation theorems for uniform ball, cube and tuple samples, and a non-iterative corrector for AI systems. No new experiments.