Given $n$ data points, each with $d$ features, $n/2$ are labeled as $0$, the other $n/2$ are labeled as $1$. Each feature takes a value from $[0,1]$ randomly (uniform distribution). What's the probability that there exists a hyperplane that can split the two classes?

Let's consider the easiest case first, i.e. $d = 1$.

  • 3
    $\begingroup$ This is a really interesting question. I think this might be able to be reformulated in terms of whether or not the convex hulls of the two classes of points intersect or not - though I don't know if that makes the problem more straightforward or not. $\endgroup$ Sep 10, 2018 at 2:55
  • $\begingroup$ This will clearly be a function of the relative magnitudes of $n$ & $d$. Consider the easiest case w/ $d=1$, if $n=2$, then w/ truly continuous data (ie, no rounding to any decimal place), the probability they can be linearly separated is $1$. OTOH, $\lim n\to \infty\ \ \text{Pr(linearly separable)} \to 0$. $\endgroup$ Sep 10, 2018 at 14:08
  • $\begingroup$ You should also clarify if the hyperplane needs to be 'flat' (or if it could be, say, a parabola in a $2d$-type situation). It seems to me that the question strongly implies flatness, but this should probably be stated explicitly. $\endgroup$ Sep 10, 2018 at 14:13
  • 4
    $\begingroup$ @gung I think the word "hyperplane" unambiguously implies "flatness", that's why I edited the title to say "linearly separable". Clearly any dataset without duplicates can is in principle nonlinearly separable. $\endgroup$
    – amoeba
    Sep 10, 2018 at 15:30
  • 1
    $\begingroup$ @gung IMHO "flat hyperplane" is a pleonasm. If you argue that "hyperplane" can be curved, then "flat" can also be curved (in an appropriate metric). $\endgroup$
    – amoeba
    Sep 10, 2018 at 18:07

2 Answers 2


Assuming no duplicates exist in the data.

If $n\leq d+1$, the probability is $\text{Pr}=1$.

For other combinations of $(n,d)$, see the following plot:

enter image description here

I generated this plot simulating input and output data as specified in the OP. Linear separability was defined as failure of convergence in a logistic regression model, due to the Hauck-Donner effect.

We can see the probability decreases for increasing $n$. In fact, we could fit a model relating $n, d$ to $p$, and this was the result:

$$P(n,d)={ 1 \over {1 + e^ {-(5.82944-4.58261\times n + 1.37271 \times d -0.0235785 \times n \times d)} } }$$

enter image description here

Code for the plot (in Julia):

using GLM

ds = 10; #number of dimensions to be investigated
ns = 100 #number of examples to be investigated
niter = 1000; #number of iterations per d per n
P = niter * ones(Int64, ds, ns); #starting the number of successes

for d in 1:ds
    for n in (d+1):ns
        p = 0 #0 hits
        for i in 1:niter
            println("Dimensions: $d; Samples: $n; Iteration: $i;")
            try #we will try to catch errors in the logistic glm, these are due to perfect separability
                X = hcat(rand((n,d)), ones(n)); #sampling from uniform plus intercept
                Y = sample(0:1, n)  #sampling a binary outcome
                glm(X, Y, Binomial(), LogitLink())
                p = p+1 #if we catch an error, increase the count
        P[d,n] = p

using Plots

gui(heatmap(P./niter, xlabel = "Number of Samples", ylabel = "Number of Dimensions", title = "Probability of linear separability"))

Code for the model relating $(n,d)$ to $p$ (in Julia):

probs = P./niter
N = transpose(repmat(1:ns, 1, ds))
D = repmat(1:ds, 1, ns)

fit = glm(hcat(log.(N[:]), D[:], N[:].*D[:], ones(ds*ns)), probs[:], Binomial(), LogitLink())
#4-element Array{Float64,1}:
# -4.58261
#  1.37271
# -0.0235785
#  5.82944

gui(heatmap(reshape(predict(fit), ds, ns), xlabel = "Number of Samples", ylabel = "Number of Dimensions", title = "Fit of probability of linear separability"))
  • $\begingroup$ +1. Why log(n) and not n? The yellow-black boundary looks like a straight line to me on the top figure, but appears bent on the second figure. Is it maybe because of the log(n)? Not sure. $\endgroup$
    – amoeba
    Sep 26, 2018 at 13:50
  • $\begingroup$ @amoeba I changed it. I also included the interaction, because it could explain the gradual broadening of the border between $p=1$ and $p=0$ (which was the reason I had tried the logarithm before). $\endgroup$
    – Firebug
    Sep 26, 2018 at 16:54

This is related to Cover's theorem.

A nice summary by Emin Orhan is given here.

Ps: I would post this in a comment but don't have enough reputation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.