Berapakah probabilitas bahwa

Diberikan titik data, masing-masing dengan fitur , diberi label sebagai , yang lain dilabeli sebagai . Setiap fitur mengambil nilai dari secara acak (distribusi seragam). Berapa probabilitas bahwa ada hyperplane yang dapat membagi dua kelas? $n$ $d$ $n/2$ $0$ $n/2$ $1$ $[0,1]$

Mari kita perhatikan kasus yang paling mudah, yaitu . $d = 1$

probability classification mathematical-statistics separation Xing Shi
sumber

Ini pertanyaan yang sangat menarik. Saya pikir ini mungkin dapat dirumuskan kembali dalam hal apakah cembung lambung dari dua kelas titik berpotongan atau tidak - meskipun saya tidak tahu apakah itu membuat masalah lebih mudah atau tidak.

Don Walpola

Ini jelas akan menjadi fungsi dari besaran relatif &

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$

Anda juga harus mengklarifikasi apakah hyperplane perlu 'rata' (atau jika bisa, misalnya, parabola dalam situasi tipe- ). Tampak bagi saya bahwa pertanyaan tersebut sangat menyiratkan kerataan, tetapi ini mungkin harus dinyatakan secara eksplisit.

2 d

$2d$

gung - Reinstate Monica

@ung saya pikir kata "hyperplane" jelas menyiratkan "kerataan", itu sebabnya saya mengedit judul untuk mengatakan "terpisah secara linear". Jelas setiap dataset tanpa duplikat pada prinsipnya dapat dipisahkan secara nonlinier.

Amoeba berkata Reinstate Monica

@gung IMHO "flat hyperplane" adalah pleonasm. Jika Anda berpendapat bahwa "hyperplane" dapat melengkung, maka "flat" juga dapat melengkung (dalam metrik yang sesuai).

Amoeba berkata Reinstate Monica

Jawaban:

Dengan asumsi tidak ada duplikat dalam data.

Jika , probabilitasnya adalah . $n\leq d+1$ $\text{Pr}=1$

Untuk kombinasi lain dari , lihat plot berikut: $(n,d)$

Saya membuat plot ini mensimulasikan data input dan output seperti yang ditentukan dalam OP. Separabilitas linier didefinisikan sebagai kegagalan konvergensi dalam model regresi logistik, karena efek Hauck-Donner .

Kita dapat melihat probabilitas menurun untuk meningkatkan . Faktanya, kita dapat memasukkan model yang berhubungan dengan ke , dan inilah hasilnya: $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)} } }$

Kode untuk plot (dalam 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"))

Kode untuk model yang berkaitan dengan (dalam 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"))

Pembakar
sumber

+1. Mengapa log (n) dan bukan n? Batas kuning-hitam terlihat seperti garis lurus bagiku di gambar atas, tetapi tampak bengkok di gambar kedua. Apakah mungkin karena log (n)? Tidak yakin.

Amuba mengatakan Reinstate Monica

p = 1

$p=1$

p = 0

$p=0$