Jakie jest prawdopodobieństwo, że

24

Biorąc pod uwagę punktów danych, każdy z cechami , są oznaczone jako , pozostałe są oznaczone jako . Każda cecha przyjmuje losowo wartość z (rozkład równomierny). Jakie jest prawdopodobieństwo, że istnieje hiperpłaszczyzna, która może podzielić dwie klasy?d n / 2 0 n / 2 1 [ 0 , 1 ]ndn/20n/21[0,1]

Najpierw rozważmy najprostszy przypadek, tj. .d=1

Xing Shi
źródło
3
To naprawdę interesujące pytanie. Myślę, że można to przeformułować pod kątem tego, czy wypukłe kadłuby dwóch klas punktów przecinają się, czy nie - choć nie wiem, czy to sprawia, że ​​problem jest prostszy, czy nie.
Don Walpola,
Będzie to oczywiście funkcja względnych wielkości & . Rozważ najprostszy przypadek w / , jeśli , to w / dane naprawdę ciągłe (tj. Bez zaokrąglania do dowolnego miejsca po przecinku), prawdopodobieństwo, że można je liniowo oddzielić wynosi . OTOH, . d d = 1 n = 2 1 lim n Pr (liniowo rozdzielalne) 0ndd=1n=21limn  Pr(linearly separable)0
Gung - Przywróć Monikę
Powinieneś także wyjaśnić, czy hiperpłaszczyzna musi być „płaska” (czy może to być, powiedzmy, parabola w sytuacji typu 2d ). Wydaje mi się, że pytanie silnie implikuje płaskość, ale prawdopodobnie należy to wyraźnie zaznaczyć.
gung - Przywróć Monikę
4
@gung Myślę, że słowo „hiperpłaszczyzna” jednoznacznie oznacza „płaskość”, dlatego zredagowałem tytuł, by powiedzieć „liniowo rozdzielne”. Oczywiście każdy zestaw danych bez duplikatów może w zasadzie być nieliniowo rozdzielny.
ameba mówi Przywróć Monikę
1
@gung IMHO „płaski hiperpłaszczyzna” to pleonasm. Jeśli argumentujesz, że „hiperpłaszczyzna” może być zakrzywiona, to „płaskie” może być również zakrzywione (w odpowiedniej metryki).
ameba mówi Przywróć Monikę

Odpowiedzi:

4

Zakładając, że w danych nie ma duplikatów.

Jeśli nd+1 , prawdopodobieństwo wynosi Pr=1 .

Dla innych kombinacji (n,d) zobacz następujący wykres:

wprowadź opis zdjęcia tutaj

Wygenerowałem ten wykres symulując dane wejściowe i wyjściowe określone w PO. Liniowa separowalność została zdefiniowana jako brak zbieżności w modelu regresji logistycznej z powodu efektu Haucka-Donnera .

Widzimy spadek prawdopodobieństwa wzrostu . W rzeczywistości mogliśmy dopasować model odnoszący się od do , i taki był wynik:nn,dp

P(n,d)=11+e(5.829444.58261×n+1.37271×d0.0235785×n×d)

wprowadź opis zdjęcia tutaj


Kod fabuły (w Julii):

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

Kod modelu odnoszącego się do do (w Julii):(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
źródło
+1. Dlaczego log (n), a nie n? Żółto-czarna granica wygląda dla mnie jak prosta linia na górnej figurze, ale wydaje się wygięta na drugiej figurze. Czy to może z powodu log (n)? Niepewny.
ameba mówi Przywróć Monikę
@amoeba Zmieniłem to. I również oddziaływania, ponieważ może to wyjaśnić stopniowe rozszerzenie granicy , a (który był powodem, że próbował logarytm wcześniej). p = 0p=1p=0
Firebug,