Wie groß ist die Wahrscheinlichkeit, dass zufällige Punkte in Dimensionen linear trennbar sind?

Bei Datenpunkten mit jeweils Merkmalen werden als und die anderen als . Jedes Merkmal erhält zufällig einen Wert von (gleichmäßige Verteilung). Wie groß ist die Wahrscheinlichkeit, dass es eine Hyperebene gibt, die die beiden Klassen aufteilen kann? $n$ $d$ $n/2$ $0$ $n/2$ $1$ $[0,1]$

Betrachten wir zunächst den einfachsten Fall, . $d = 1$

probability classification mathematical-statistics separation Xing Shi
quelle

Das ist eine wirklich interessante Frage. Ich denke, dies könnte dahingehend umformuliert werden, ob sich die konvexen Hüllen der beiden Punktklassen überschneiden oder nicht - obwohl ich nicht weiß, ob dies das Problem einfacher macht oder nicht.

Don Walpola

Dies wird eindeutig eine Funktion der relativen Größen von & . Betrachten Sie den einfachsten Fall w / , wenn , dann w / wirklich kontinuierliche Daten (dh keine Rundung auf eine Dezimalstelle), die Wahrscheinlichkeit, dass sie linear getrennt werden können, ist . OTOH, .

n

$n$

d

$d$

d = 1

$d=1$

n = 2

$n=2$

1

$1$

lim n \to \infty Pr(linearly separable) \to 0

$\lim n\to \infty\ \ \text{Pr(linearly separable)} \to 0$

gung - Wiedereinsetzung von Monica

Sie sollten auch klären, ob die Hyperebene "flach" sein muss (oder ob es sich beispielsweise um eine Parabel in einer Situation vom

2 d

$2d$ Typ handeln könnte). Es scheint mir, dass die Frage stark Flachheit impliziert, aber dies sollte wahrscheinlich explizit angegeben werden.

gung - Wiedereinsetzung von Monica

@gung Ich denke, das Wort "Hyperebene" impliziert eindeutig "Ebenheit". Deshalb habe ich den Titel so bearbeitet, dass er "linear trennbar" lautet. Es ist klar, dass jeder Datensatz ohne Duplikate grundsätzlich nichtlinear trennbar ist.

Amöbe sagt Reinstate Monica

@gung IMHO "flache Hyperebene" ist ein Pleonasmus. Wenn Sie argumentieren, dass "Hyperebene" gekrümmt sein kann, dann kann "flach" auch gekrümmt sein (in einer geeigneten Metrik).

Amöbe sagt Reinstate Monica

Antworten:

Vorausgesetzt, die Daten enthalten keine Duplikate.

Wenn , ist die Wahrscheinlichkeit . $n\leq d+1$ $\text{Pr}=1$

Für andere Kombinationen von $(n,d)$ siehe das folgende Diagramm:

Ich habe diesen Plot generiert, in dem Eingangs- und Ausgangsdaten wie im OP angegeben simuliert wurden. Die lineare Separierbarkeit wurde aufgrund des Hauck-Donner-Effekts als Konvergenzfehler in einem logistischen Regressionsmodell definiert .

Wir können sehen, dass die Wahrscheinlichkeit abnimmt, wenn zunimmt . Tatsächlich konnten wir ein Modell anpassen, das und in , und dies war das Ergebnis: $n$ $n, d$ $p$

P (n, d) = \frac{1}{1 + e^{- (5,82944 - 4,58261 \times n + 1.37271 \times d - 0,0235785 \times n \times d)}}

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

Code für das Grundstück (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 für das Modell bezüglich zu (in Julia): $(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"))

Firebug
quelle

+1. Warum log (n) und nicht n? Die gelb-schwarze Begrenzung sieht für mich in der oberen Figur wie eine gerade Linie aus, erscheint aber in der zweiten Figur gebogen. Liegt es vielleicht am log (n)? Nicht sicher.

Amöbe sagt Reinstate Monica

@amoeba Ich habe es geändert. Ich habe auch die Wechselwirkung mit einbezogen, weil sie die allmähliche Verbreiterung der Grenze zwischen und erklären könnte (aus diesem Grund hatte ich den Logarithmus bereits früher versucht).

p = 1

$p=1$

p = 0

$p=0$

Firebug