Quelle est la probabilité que

Étant donné points de données, chacun avec caractéristiques, sont étiquetés comme , les autres sont étiquetés comme . Chaque entité prend une valeur de au hasard (distribution uniforme). Quelle est la probabilité qu'il existe un hyperplan pouvant diviser les deux classes?d n / 2 0 n / 2 1 [ 0 , 1 $n$$d$$n/2$$0$$n/2$$1$$[0,1]$

Considérons d'abord le cas le plus simple, c'est-à-dire .$d = 1$

En supposant qu'aucun doublon n'existe dans les données.

Si $n\leq d+1$ , la probabilité est $\text{Pr}=1$ .

Pour d'autres combinaisons de $(n,d)$ , voir le graphique suivant:

J'ai généré ce tracé simulant les données d'entrée et de sortie comme spécifié dans l'OP. La séparabilité linéaire a été définie comme l'échec de la convergence dans un modèle de régression logistique, en raison de l'effet Hauck-Donner .

Nous pouvons voir que la probabilité diminue pour augmenter $n$ . En fait, nous avons pu ajuster un modèle reliant $n, d$ à $p$ , et voici le résultat:

Code de l'intrigue (en 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"))

$(n,d)$$p$

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"))