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
    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. – Don Walpola Sep 10 at 2:55
  • 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$. – gung Sep 10 at 14:08
  • 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. – gung Sep 10 at 14:13
  • 4
    @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. – amoeba Sep 10 at 15:30
  • 1
    @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). – amoeba Sep 10 at 18:07

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())
            catch
                p = p+1 #if we catch an error, increase the count
            end
        end
        P[d,n] = p
    end
end

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())
coef(fit)
#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"))
  • +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. – amoeba Sep 26 at 13:50
  • @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). – Firebug Sep 26 at 16:54

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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