Masalah singularitas dalam model campuran Gaussian

15

Dalam bab 9 buku Pengenalan pola dan pembelajaran mesin, ada bagian ini tentang model campuran Gaussian:

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini Sejujurnya saya tidak begitu mengerti mengapa ini akan menciptakan singularitas. Adakah yang bisa menjelaskan hal ini kepada saya? Maaf, saya hanya sarjana dan pemula dalam pembelajaran mesin, jadi pertanyaan saya mungkin terdengar sedikit konyol, tapi tolong bantu saya. Terima kasih banyak

Dang Manh Truong
sumber
Sepertinya itu mudah diperbaiki juga, reparameterize ke σk2=τ2γk dan kemudian menghukum γk karena terlalu dekat dengan nol ketika mengoptimalkan.
probabilityislogic
1
@probabilityislogic Tidak yakin apakah saya mengikuti di sini :(
Dang Manh Truong

Jawaban:

11

Jika kita ingin mencocokkan Gaussian ke satu titik data menggunakan kemungkinan maksimum, kita akan mendapatkan Gaussian yang sangat runcing yang "runtuh" ​​ke titik itu. Variansnya nol ketika hanya ada satu titik, yang dalam kasus multi-variate Gaussian, mengarah ke matriks kovarians singular, sehingga disebut masalah singularitas.

Ketika varians menjadi nol, kemungkinan komponen Gaussian (rumus 9.15) berubah hingga tak terbatas dan model menjadi terlalu pas. Ini tidak terjadi ketika kami hanya memasukkan satu Gaussian ke sejumlah poin karena variansnya tidak boleh nol. Tapi itu bisa terjadi ketika kita memiliki campuran Gaussians, seperti diilustrasikan pada halaman PRML yang sama.

masukkan deskripsi gambar di sini

Pembaruan :
Buku ini menyarankan dua metode untuk mengatasi masalah singularitas, yaitu

1) mengatur ulang mean dan varians ketika singularitas terjadi masukkan deskripsi gambar di sini

2) menggunakan MAP, bukan MLE dengan menambahkan sebelumnya. masukkan deskripsi gambar di sini

dontloo
sumber
Tentang kasus Gaussian tunggal, mengapa varians tidak boleh nol? Buku teks itu mengatakan: "Ingat bahwa masalah ini tidak muncul dalam kasus distribusi Gaussian tunggal. Untuk memahami perbedaannya, perhatikan bahwa jika satu Gaussian runtuh ke titik data, itu akan berkontribusi faktor multiplikasi ke fungsi kemungkinan yang timbul dari yang lain titik data dan faktor-faktor ini akan menjadi nol secara eksponensial cepat, memberikan kemungkinan keseluruhan yang menjadi nol daripada tanpa batas. "tapi saya tidak terlalu memahaminya :(
Dang Manh Truong
@DangManhTruong itu karena menurut definisi varians, , kecuali semua poin memiliki nilai yang sama, kami selalu memiliki varian non-nol. vSebuahr(x)=E[(x-μ)2]
dontloo
Saya melihat! Terima kasih: D Jadi dalam praktiknya apa yang harus kita lakukan untuk menghindarinya? Buku itu tidak menjelaskan tentang itu.
Dang Manh Truong
@DangManhTruong hai, saya menambahkannya ke jawabannya, silakan lihat :)
dontloo
@DangManhTruong sama
sama
3

Ingatlah bahwa masalah ini tidak muncul dalam kasus distribusi Gaussian tunggal. Untuk memahami perbedaannya, perhatikan bahwa jika satu Gaussian runtuh ke titik data, itu akan berkontribusi faktor multiplikasi ke fungsi kemungkinan yang timbul dari titik data lainnya dan faktor-faktor ini akan menjadi nol secara eksponensial cepat, memberikan kemungkinan keseluruhan yang menjadi nol daripada dari tak terbatas.

Saya juga agak bingung dengan bagian ini, dan inilah interpretasi saya. Ambil case 1D untuk kesederhanaan.

Ketika satu Gaussian "runtuh" ​​pada titik data , yaitu, μ = x i , kemungkinan keseluruhan menjadi:xiμ=xi

p(x)=p(xi)p(xi)=(12πσ)(niN12πσe(xnμ)22σ2)

Anda melihat sebagai , istilah di p kiri ( x i ) , yang seperti kasus patologis dalam GMM, tetapi istilah di sebelah kanan, yang merupakan kemungkinan titik data lainnya p ( xi ) , masih mengandung istilah seperti eσ0p(xi)p(xi) yang0secara eksponensial secepatσ0, sehingga efek keseluruhan pada kemungkinannya adalah nol.e(xnμ)22σ20σ0

Poin utama di sini adalah bahwa ketika memasang Gaussian tunggal, semua titik data harus berbagi satu set parameter , tidak seperti dalam kasus campuran di mana satu komponen dapat "fokus" pada satu titik data tanpa penalti terhadap kemungkinan data keseluruhan .μ,σ

Yibo Yang
sumber
2

Jawaban ini akan memberikan wawasan tentang apa yang terjadi yang mengarah ke matriks kovarian singular selama pemasangan GMM ke dataset, mengapa ini terjadi serta apa yang bisa kita lakukan untuk mencegahnya.

Oleh karena itu, sebaiknya kita mulai dengan merekapitulasi langkah-langkah selama pemasangan Model Campuran Gaussian ke dataset.


0. Tentukan berapa banyak sumber / kluster (c) yang Anda inginkan agar sesuai dengan data Anda
1. Inisialisasi parameter berarti μc , covariance , dan fraction_per_classΣc per cluster c πc

EStep_

  1. Hitung untuk setiap datapoint probabilitas r i c bahwa datapoint x i milik cluster c dengan: r i c = π c N ( x ixiricxi

    di manaN(x|μ,Σ)menjelaskan mulitvariate Gaussian dengan: N(xi,μc,Σc)=1
    ric=πcN(xi | μc,Σc)Σk=1KπkN(xi | μk,Σk)
    N(x | μ,Σ)

    ricmemberi kita untuk setiap datapointxiukuran:Probabilitythatxibelongstoclas
    N(xi,μc,Σc) = 1(2π)n2|Σc|12exp(12(xiμc)TΣc1(xiμc))


    ricxi maka jikaxisangat dekat dengan salah satu c gaussian, itu akan mendapatkan tinggiricnilai untuk nilai-nilai gaussian dan relatif rendah ini sebaliknya. M-Step_(longgar berbicara fraksi poin dialokasikan untuk klaster c) dan memperbaruiπcProbability that xi belongs to class cProbability of xi over all classesxiric

    MStep_

    Untuk setiap cluster c: Hitung total berat mcπc , , dan Σ c menggunakan r i c π c = m cμcΣcricdengan:

    mc = Σiric

    πc = mcm

    μc = 1mcΣiricxi

    Harap diingat bahwa Anda harus menggunakan cara yang diperbarui dalam formula terakhir ini. Ulangi langkah E dan M secara berulang sampai fungsi log-likelihood dari model kami bertemu di mana log likelihood dihitung dengan: lnp(X|π,μ,Σ)=Σ N i = 1 ln(Σ K
    Σc = 1mcΣiric(xiμc)T(xiμc)





    ln p(X | π,μ,Σ) = Σi=1N ln(Σk=1KπkN(xi | μk,Σk))



XAX=XA=I

[0000]


AXIΣc1
0matriks kovarians di atas jika Gaussian Multivarian jatuh ke satu titik selama iterasi antara langkah E dan M. Ini bisa terjadi jika kita memiliki misalnya dataset yang ingin kita masukkan 3 gaussians tetapi yang sebenarnya hanya terdiri dari dua kelas (cluster) sehingga secara longgar, dua dari tiga gaussi ini menangkap cluster mereka sendiri sedangkan gaussian terakhir hanya mengaturnya untuk menangkap satu titik di mana ia duduk. Kita akan melihat bagaimana ini terlihat di bawah. Tetapi langkah demi langkah: Asumsikan Anda memiliki dataset dua dimensi yang terdiri dari dua cluster tetapi Anda tidak tahu itu dan ingin mencocokkan tiga model gaussian, yaitu c = 3. Anda menginisialisasi parameter Anda dalam langkah E dan plot gaussians di atas data Anda yang terlihat suram. seperti (mungkin Anda dapat melihat dua kelompok yang relatif tersebar di kiri bawah dan kanan atas): enter image description hereμcπcenter image description here

riccovric
ric=πcN(xi | μc,Σc)Σk=1KπkN(xi | μk,Σk)
ricricxienter image description herexixirsayacxsaya. (runtuh ke datapoint ini -> Ini terjadi jika semua titik lainnya lebih mungkin bagian dari satu atau dua gaussian dan karenanya ini adalah satu-satunya titik yang tersisa untuk gaussian tiga -> Alasan mengapa hal ini terjadi dapat ditemukan dalam interaksi antara dataset itu sendiri dalam inisialisasi gaussians. Artinya, jika kita telah memilih nilai awal lainnya untuk gaussians, kita akan melihat gambar lain dan gaussian ketiga mungkin tidak akan runtuh). Ini cukup jika Anda semakin jauh paku gaussian ini. Itursayacmeja kemudian terlihat suram. seperti: enter image description here Seperti yang Anda lihat, itursayacdari kolom ketiga, yaitu untuk gaussian ketiga adalah nol, bukan satu baris ini. Jika kita mencari datapoint mana yang diwakili di sini kita mendapatkan datapoint: [23.38566343 8.07067598]. Ok, tapi mengapa kita mendapatkan matriks singularitas dalam kasus ini? Nah, dan ini adalah langkah terakhir kami, oleh karena itu kami harus sekali lagi mempertimbangkan perhitungan matriks kovarian yaitu:
Σc = Σsayarsayac(xsaya-μc)T(xsaya-μc)
kita telah melihat itu semua rsayac bukan nol untuk yang satu xsayadengan [23.38566343 8.07067598]. Sekarang formula ingin kita menghitung(xsaya-μc). Jika kita melihatμcuntuk gaussian ketiga ini kita mendapatkan [23.38566343 8.07067598]. Oh, tapi tunggu, itu persis sama denganxsaya dan itulah yang ditulis oleh Bishop: "Misalkan salah satu komponen dari model campuran, mari kita katakan j komponen th, memiliki rerata μj persis sama dengan salah satu titik data sehingga μj=xnuntuk beberapa nilai n "(Bishop, 2006, p.434). Jadi apa yang akan terjadi? Nah, istilah ini akan menjadi nol dan karenanya datapoint ini adalah satu-satunya kesempatan bagi matriks kovarians untuk tidak mendapatkan nol (karena datapoint ini adalah satu-satunya tempatrsayac> 0), sekarang menjadi nol dan terlihat seperti:

[0000]


Akibatnya seperti yang disebutkan di atas, ini adalah matriks tunggal dan akan menyebabkan kesalahan selama perhitungan gaussian multivariat. Jadi bagaimana kita bisa mencegah situasi seperti itu. Nah, kita telah melihat bahwa matriks kovarians adalah singular jika itu adalah0matriks. Karenanya untuk mencegah singularitas kita hanya perlu mencegah agar matriks kovarians menjadi a0matriks. Hal ini dilakukan dengan menambahkan nilai yang sangat kecil (dalam GaussianMixture sklearn nilai ini diatur ke 1e-6) ke digonal dari matriks kovarians. Ada juga cara lain untuk mencegah singularitas seperti memperhatikan ketika sebuah gaussian runtuh dan menetapkan mean dan / atau matriks kovariansnya ke nilai baru yang sewenang-wenang. Peraturan kovarian ini juga diterapkan dalam kode di bawah ini yang dengannya Anda mendapatkan hasil yang diuraikan. Mungkin Anda harus menjalankan kode beberapa kali untuk mendapatkan matriks kovarians tunggal, seperti yang dikatakan. ini tidak boleh terjadi setiap kali tetapi juga tergantung pada pengaturan awal gaussians.
import matplotlib.pyplot as plt
from matplotlib import style
style.use('fivethirtyeight')
from sklearn.datasets.samples_generator import make_blobs
import numpy as np
from scipy.stats import multivariate_normal


# 0. Create dataset
X,Y = make_blobs(cluster_std=2.5,random_state=20,n_samples=500,centers=3)

# Stratch dataset to get ellipsoid data
X = np.dot(X,np.random.RandomState(0).randn(2,2))


class EMM:

    def __init__(self,X,number_of_sources,iterations):
        self.iterations = iterations
        self.number_of_sources = number_of_sources
        self.X = X
        self.mu = None
        self.pi = None
        self.cov = None
        self.XY = None



    # Define a function which runs for i iterations:
    def run(self):
        self.reg_cov = 1e-6*np.identity(len(self.X[0]))
        x,y = np.meshgrid(np.sort(self.X[:,0]),np.sort(self.X[:,1]))
        self.XY = np.array([x.flatten(),y.flatten()]).T


        # 1. Set the initial mu, covariance and pi values
        self.mu = np.random.randint(min(self.X[:,0]),max(self.X[:,0]),size=(self.number_of_sources,len(self.X[0]))) # This is a nxm matrix since we assume n sources (n Gaussians) where each has m dimensions
        self.cov = np.zeros((self.number_of_sources,len(X[0]),len(X[0]))) # We need a nxmxm covariance matrix for each source since we have m features --> We create symmetric covariance matrices with ones on the digonal
        for dim in range(len(self.cov)):
            np.fill_diagonal(self.cov[dim],5)


        self.pi = np.ones(self.number_of_sources)/self.number_of_sources # Are "Fractions"
        log_likelihoods = [] # In this list we store the log likehoods per iteration and plot them in the end to check if
                             # if we have converged

        # Plot the initial state    
        fig = plt.figure(figsize=(10,10))
        ax0 = fig.add_subplot(111)
        ax0.scatter(self.X[:,0],self.X[:,1])
        for m,c in zip(self.mu,self.cov):
            c += self.reg_cov
            multi_normal = multivariate_normal(mean=m,cov=c)
            ax0.contour(np.sort(self.X[:,0]),np.sort(self.X[:,1]),multi_normal.pdf(self.XY).reshape(len(self.X),len(self.X)),colors='black',alpha=0.3)
            ax0.scatter(m[0],m[1],c='grey',zorder=10,s=100)


        mu = []
        cov = []
        R = []


        for i in range(self.iterations):               

            mu.append(self.mu)
            cov.append(self.cov)


            # E Step
            r_ic = np.zeros((len(self.X),len(self.cov)))

            for m,co,p,r in zip(self.mu,self.cov,self.pi,range(len(r_ic[0]))):
                co+=self.reg_cov
                mn = multivariate_normal(mean=m,cov=co)
                r_ic[:,r] = p*mn.pdf(self.X)/np.sum([pi_c*multivariate_normal(mean=mu_c,cov=cov_c).pdf(X) for pi_c,mu_c,cov_c in zip(self.pi,self.mu,self.cov+self.reg_cov)],axis=0)
            R.append(r_ic)

            # M Step

            # Calculate the new mean vector and new covariance matrices, based on the probable membership of the single x_i to classes c --> r_ic
            self.mu = []
            self.cov = []
            self.pi = []
            log_likelihood = []

            for c in range(len(r_ic[0])):
                m_c = np.sum(r_ic[:,c],axis=0)
                mu_c = (1/m_c)*np.sum(self.X*r_ic[:,c].reshape(len(self.X),1),axis=0)
                self.mu.append(mu_c)

                # Calculate the covariance matrix per source based on the new mean
                self.cov.append(((1/m_c)*np.dot((np.array(r_ic[:,c]).reshape(len(self.X),1)*(self.X-mu_c)).T,(self.X-mu_c)))+self.reg_cov)
                # Calculate pi_new which is the "fraction of points" respectively the fraction of the probability assigned to each source 
                self.pi.append(m_c/np.sum(r_ic)) 



            # Log likelihood
            log_likelihoods.append(np.log(np.sum([k*multivariate_normal(self.mu[i],self.cov[j]).pdf(X) for k,i,j in zip(self.pi,range(len(self.mu)),range(len(self.cov)))])))



        fig2 = plt.figure(figsize=(10,10))
        ax1 = fig2.add_subplot(111) 
        ax1.plot(range(0,self.iterations,1),log_likelihoods)
        #plt.show()
        print(mu[-1])
        print(cov[-1])
        for r in np.array(R[-1]):
            print(r)
        print(X)

    def predict(self):
        # PLot the point onto the fittet gaussians
        fig3 = plt.figure(figsize=(10,10))
        ax2 = fig3.add_subplot(111)
        ax2.scatter(self.X[:,0],self.X[:,1])
        for m,c in zip(self.mu,self.cov):
            multi_normal = multivariate_normal(mean=m,cov=c)
            ax2.contour(np.sort(self.X[:,0]),np.sort(self.X[:,1]),multi_normal.pdf(self.XY).reshape(len(self.X),len(self.X)),colors='black',alpha=0.3)




EMM = EMM(X,3,100)     
EMM.run()
EMM.predict()
2Obe
sumber
0

Imho, semua jawaban ketinggalan fakta mendasar. Jika seseorang melihat ruang parameter untuk model campuran Gaussian, ruang ini tunggal di sepanjang subruang di mana ada kurang dari jumlah penuh komponen dalam campuran. Itu berarti bahwa turunannya secara otomatis nol dan biasanya seluruh subruang akan muncul sebagai mle. Secara lebih filosofis, subruang dari kovarian pangkat kurang dari adalah batas ruang parameter dan seseorang harus selalu curiga ketika mle terjadi pada batas-biasanya menunjukkan bahwa ada ruang parameter lebih besar yang bersembunyi di mana orang dapat menemukan 'nyata' mle. Ada sebuah buku yang disebut "Statistik Aljabar" oleh Drton, Sturmfeld, dan Sullivant. Masalah ini dibahas dalam buku itu secara terperinci. Jika Anda benar-benar penasaran, Anda harus melihatnya.

meh
sumber
-2

Untuk Gaussian tunggal, nilai rata-rata mungkin sama dengan salah satu poin data (xn misalnya) dan kemudian ada istilah berikut dalam fungsi kemungkinan:

N(xn|xn,σj11)limσjxn1(2π)1/2σjexp(-1σj|xn-σj|2)=1(2π)1/2σj
Batasnya σj0 sekarang jelas berbeda karena argumen eksponensial menghilang.

Namun untuk titik data xm berbeda dengan rerata σj, kami akan memiliki

N(xm|xm,σj11)=1(2π)1/2σjexp(-1σj|xm-σj|2)
dan sekarang argumen divergen eksponensial (dan negatif) dalam batas σj0. Akibatnya produk dari dua istilah ini dalam fungsi kemungkinan akan hilang.
Nick
sumber
Jawaban ini salah karena tidak ada alasan untuk mengidentifikasi maksud μj dan standar deviasi σj.
Xi'an