Zagadnienia osobliwości w modelu mieszanki Gaussa

15

W rozdziale 9 książki Rozpoznawanie wzorców i uczenie maszynowe jest ta część o modelu mieszanki Gaussa:

Szczerze mówiąc, tak naprawdę nie rozumiem, dlaczego stworzyłoby to osobliwość. Czy ktoś może mi to wytłumaczyć? Przykro mi, ale jestem tylko studentem i początkującym w uczeniu maszynowym, więc moje pytanie może zabrzmieć trochę głupio, ale proszę, pomóż mi. Dziękuję Ci bardzo

gaussian-mixture

— Dang Manh Truong
źródło

Wygląda na to, że łatwo go też naprawić, zmień parametry na

a następnie ukaraj

za zbyt bliskie zeru podczas optymalizacji.

σ_{k}^{2} = τ^{2} γ_{k}

$\sigma_k^2=\tau^2\gamma_k$

γ_{k}

$\gamma_k$

— probabilityislogic

1

@probabilityislogic Nie jestem pewien, czy śledzę tutaj :(

— Dang Manh Truong

11

Jeśli chcemy dopasować Gaussa do pojedynczego punktu danych z maksymalnym prawdopodobieństwem, otrzymamy bardzo kolczasty Gaussa, który „zapadnie się” do tego punktu. Wariancja wynosi zero, gdy jest tylko jeden punkt, który w przypadku wielowymiarowym przypadku Gaussa prowadzi do pojedynczej macierzy kowariancji, więc nazywa się to problemem osobliwości.

Kiedy wariancja osiągnie zero, prawdopodobieństwo elementu Gaussa (wzór 9.15) przechodzi w nieskończoność, a model staje się przeregulowany. Nie dzieje się tak, gdy dopasujemy tylko jednego Gaussa do wielu punktów, ponieważ wariancja nie może wynosić zero. Ale może się to zdarzyć, gdy mamy mieszankę Gaussów, jak pokazano na tej samej stronie PRML.

Aktualizacja :
książka sugeruje dwie metody rozwiązania problemu osobliwości

1) resetowanie średniej i wariancji w przypadku wystąpienia osobliwości

2) za pomocą MAP zamiast MLE poprzez dodanie wcześniejszego.

— dontloo
źródło

Jeśli chodzi o pojedynczy przypadek Gaussa, dlaczego wariancja nie może wynosić zero? W podręczniku czytamy: „Przypomnijmy, że ten problem nie pojawił się w przypadku pojedynczego rozkładu Gaussa. Aby zrozumieć różnicę, zauważ, że jeśli pojedynczy Gaussian zapadnie się w punkcie danych, przyczyni się on do mnożenia czynników funkcji prawdopodobieństwa wynikających z drugiego punkty danych, a te czynniki szybko wzrosną do zera wykładniczo, co daje ogólne prawdopodobieństwo, że dojdzie do zera, a nie do nieskończoności. "ale nie bardzo to rozumiem :(

— Dang Manh Truong

@DangManhTruong to dlatego, że zgodnie z definicją wariancji,

, chyba że wszystkie punkty mają tę samą wartość, zawsze mamy niezerową wariancję.

v a r (x) = E [(x - μ)^{2}]

$var(x) = E[(x-\mu)^2]$

— dontloo,

Widzę! Dzięki: D Więc w praktyce, co powinniśmy zrobić, aby tego uniknąć? Książka nie wyjaśnia tego.

— Dang Manh Truong,

@DangManhTruong cześć, dodałem go do odpowiedzi, proszę spojrzeć :)

— dontloo

@DangManhTruong nie ma za co

— poniedziałek

3

Przypomnijmy, że problem ten nie pojawił się w przypadku pojedynczego rozkładu Gaussa. Aby zrozumieć różnicę, należy zauważyć, że jeśli pojedynczy Gaussian padnie na punkt danych, przyczyni się on do mnożenia czynników funkcji prawdopodobieństwa wynikających z innych punktów danych i przyczyni się do mnożenia tych czynników, a czynniki te szybko wzrosną do zera w sposób wykładniczy, co daje ogólne prawdopodobieństwo, że raczej do zera niż nieskończoność.

Ta część mnie też trochę myliła i oto moja interpretacja. Dla uproszczenia weź skrzynkę 1D.

Kiedy pojedynczy gaussowski „zapada się” w punkcie danych , tj. , ogólne prawdopodobieństwo wynosi: $x_i$ $\mu=x_i$

p (x) = p (x_{i}) p (x ∖ i) = (\frac{1}{\sqrt{2 π} σ}) (\prod_{n \neq i}^{N} \frac{1}{\sqrt{2 π} σ} e^{- \frac{(x_{n} - μ)^{2}}{2 σ^{2}}})

$p(\mathbf{x}) = p(x_i) p(\mathbf{x}\setminus{i}) = (\frac{1}{\sqrt{2\pi}\sigma}) (\prod_{n \neq i}^N \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x_n-\mu)^2}{2\sigma^2}} )$

Widzisz jako , termin po lewej , który jest podobny do przypadku patologicznego w GMM, ale termin po prawej, który jest prawdopodobieństwem innych punktów danych , nadal zawiera terminy takie jak $\sigma \to 0$ $p(x_i) \to \infty$ $p(\mathbf{x}\setminus{i})$ którewykładniczo szybko jak, więc ogólny wpływ na prawdopodobieństwo jest to, że osiągnie zero. $e^{-\frac{(x_n-\mu)^2}{2\sigma^2}}$ $\to 0$ $\sigma \to 0$

Głównym punktem tutaj jest to, że przy dopasowywaniu pojedynczego Gaussa wszystkie punkty danych muszą dzielić jeden zestaw parametrów , w przeciwieństwie do przypadku mieszanki, w którym jeden składnik może „skupić się” na jednym punkcie danych bez uszczerbku dla ogólnego prawdopodobieństwa danych . $\mu, \sigma$

— Yibo Yang
źródło

2

Ta odpowiedź da wgląd w to, co się dzieje, co prowadzi do pojedynczej macierzy kowariancji podczas dopasowywania GMM do zbioru danych, dlaczego tak się dzieje, a także co możemy zrobić, aby temu zapobiec.

Dlatego najlepiej zacząć od podsumowania kroków podczas dopasowywania modelu mieszanki Gaussa do zestawu danych.

0. Zdecyduj, ile źródeł / klastrów (c) chcesz dopasować do swoich danych
1. Zainicjuj parametry średnie , kowariancja i fraction_per_class na klaster c $\mu_c$ $\Sigma_c$ $\pi_c$

$\underline{E-Step}$

Obliczyć dla każdego punktu danych prawdopodobieństwo że punkt danych należy do klastra c za pomocą: $x_i$ $r_{ic}$ $x_i$

gdzieopisuje wielowariantowy gaussowski z: $r_{ja do} = \frac{π_{do} N. (x_{ja} | μ_{do}, Σ_{do})}{Σ_{k = 1}^{K.} π_{k} N. (x_{ja} | μ_{k}, Σ_{k})}$ $r_{ic} = \frac{\pi_c N(\boldsymbol{x_i} \ | \ \boldsymbol{\mu_c},\boldsymbol{\Sigma_c})}{\Sigma_{k=1}^K \pi_k N(\boldsymbol{x_i \ | \ \boldsymbol{\mu_k},\boldsymbol{\Sigma_k}})}$ $N(\boldsymbol{x} \ | \ \boldsymbol{\mu},\boldsymbol{\Sigma})$

daje nam dla każdego punktu danychmiarę: $N. (x_{ja}, μ_{do}, Σ_{do}) = \frac{1}{(2) π)^{\frac{n}{2)}} | Σ_{do} |^{\frac{1}{2)}}} mi x p (- \frac{1}{2)} (x_{ja} - μ_{do})^{T.} Σ_{do}^{- 1} (x_{ja} - μ_{do}))$ $N(\boldsymbol{x_i},\boldsymbol{\mu_c},\boldsymbol{\Sigma_c}) \ = \ \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma_c|^{\frac{1}{2}}}exp(-\frac{1}{2}(\boldsymbol{x_i}-\boldsymbol{\mu_c})^T\boldsymbol{\Sigma_c^{-1}}(\boldsymbol{x_i}-\boldsymbol{\mu_c}))$

$r_{ic}$ $x_i$ W związku z tym, jeżelijest bardzo blisko Gaussa C, to uzyskać wysokąwartością dla innych gaussowskich i stosunkowo niskich wartości. Dla każdej grupy c: Oblicz masę całkowitą $\frac{Probability \ that \ x_i \ belongs \ to \ class \ c}{Probability \ of \ x_i \ over \ all \ classes}$ $x_i$ $r_{ic}$

$\underline{M-Step}$

$m_c$ (luźno mówiąc, ułamek punktów przydzielonych do klastra c) i zaktualizuj , i używając z: $\pi_c$ $\mu_c$ $\Sigma_c$ $r_{ic}$

$m_{do} = Σ_{ja} r_{ja} do$ $m_c \ = \ \Sigma_i r_ic$
$π_{do} = \frac{m_{do}}{m}$ $\pi_c \ = \ \frac{m_c}{m}$
$μ_{do} = \frac{1}{m_{do}} Σ_{ja} r_{ja do} x_{ja}$ $\boldsymbol{\mu_c} \ = \ \frac{1}{m_c}\Sigma_i r_{ic} \boldsymbol{x_i}$
Pamiętaj, że musisz użyć zaktualizowanych środków w tym ostatnim wzorze. Iteracyjnie powtarzaj krok E i M, aż funkcja prawdopodobieństwa logarytmicznego naszego modelu zbiega się, gdzie prawdopodobieństwo logarytmu jest obliczane z: $Σ_{do} = \frac{1}{m_{do}} Σ_{ja} r_{ja do} (x_{ja} - μ_{do})^{T.} (x_{ja} - μ_{do})$ $\boldsymbol{\Sigma_c} \ = \ \frac{1}{m_c}\Sigma_i r_{ic}(\boldsymbol{x_i}-\boldsymbol{\mu_c})^T(\boldsymbol{x_i}-\boldsymbol{\mu_c})$

$l n p (X | π, μ, Σ) = Σ_{ja = 1}^{N.} l n (Σ_{k = 1}^{K.} π_{k} N. (x_{ja} | μ_{k}, Σ_{k}))$ $ln \ p(\boldsymbol{X} \ | \ \boldsymbol{\pi},\boldsymbol{\mu},\boldsymbol{\Sigma}) \ = \ \Sigma_{i=1}^N \ ln(\Sigma_{k=1}^K \pi_k N(\boldsymbol{x_i} \ | \ \boldsymbol{\mu_k},\boldsymbol{\Sigma_k}))$

$X$ $AX = XA = I$

[\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}]

$\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$

A

$A$

X

$X$

I

$I$

Σ_{c}^{- 1}

$\boldsymbol{\Sigma_c^{-1}}$

0

$\boldsymbol{0}$ powyższa macierz kowariancji, jeśli wielowymiarowy Gaussian wpada w jeden punkt podczas iteracji między krokiem E i M. Może się to zdarzyć, jeśli mamy na przykład zestaw danych, do którego chcemy dopasować 3 gaussów, ale który w rzeczywistości składa się tylko z dwóch klas (klastrów) tak, że luźno mówiąc, dwóch z tych trzech gaussów łapie własny klaster, podczas gdy ostatni gaussian nim zarządza złapać jeden punkt, na którym on siedzi. Zobaczymy jak to wygląda poniżej. Ale krok po kroku: Załóżmy, że masz dwuwymiarowy zestaw danych, który składa się z dwóch klastrów, ale nie wiesz tego i chcesz dopasować do niego trzy modele gaussowskie, to znaczy c = 3. Inicjujesz swoje parametry w kroku E i wykreśl gaussowie na górze twoich danych, które wyglądają na coś jak (może widzisz dwa stosunkowo rozproszone skupiska w lewym dolnym rogu i prawym górnym rogu):

μ_{c}

$\mu_c$

π_{c}

$\pi_c$

r_{i c}

$r_{ic}$

c o v

$cov$

r_{i c}

$r_{ic}$

r_{ja do} = \frac{π_{do} N. (x_{ja} | μ_{do}, Σ_{do})}{Σ_{k = 1}^{K.} π_{k} N. (x_{ja} | μ_{k}, Σ_{k})}

$r_{ic} = \frac{\pi_c N(\boldsymbol{x_i} \ | \ \boldsymbol{\mu_c},\boldsymbol{\Sigma_c})}{\Sigma_{k=1}^K \pi_k N(\boldsymbol{x_i \ | \ \boldsymbol{\mu_k},\boldsymbol{\Sigma_k}})}$

r_{i c}

$r_{ic}$

r_{i c}

$r_{ic}$

x_{i}

$x_i$

x_{i}

$x_i$

x_{i}

$x_i$

r_{i c}

$r_{ic}$

x_{i}

$x_i$

r_{i c}

$r_{ic}$

r_{i c}

$r_{ic}$

Σ_{do} = Σ_{ja} r_{ja do} (x_{ja} - μ_{do})^{T.} (x_{ja} - μ_{do})

$\boldsymbol{\Sigma_c} \ = \ \Sigma_i r_{ic}(\boldsymbol{x_i}-\boldsymbol{\mu_c})^T(\boldsymbol{x_i}-\boldsymbol{\mu_c})$

r_{i c}

$r_{ic}$

x_{i}

$x_i$

(x_{i} - μ_{c})

$(\boldsymbol{x_i}-\boldsymbol{\mu_c})$

μ_{c}

$\boldsymbol{\mu_c}$

x_{i}

$x_i$

j

$j$

μ_{j}

$\boldsymbol{\mu_j}$

μ_{j} = x_{n}

$\boldsymbol{\mu_j} = \boldsymbol{x_n}$

r_{i c}

$r_{ic}$

[\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}]

$\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix}$

0

$\boldsymbol{0}$

0

$\boldsymbol{0}$ matryca. Odbywa się to poprzez dodanie bardzo małej wartości (w GaussianMixture sklearn'a wartość ta jest ustawiona na 1e-6) do cyfr cyfr macierzy kowariancji. Istnieją również inne sposoby zapobiegania osobliwości, takie jak zauważanie, gdy gaussian się zapada i ustawianie jego średniej i / lub macierzy kowariancji na nową, arbitralnie wysoką wartość (wartości). Ta normalizacja kowariancji jest również zaimplementowana w poniższym kodzie, za pomocą którego otrzymujesz opisane wyniki. Być może trzeba uruchomić kod kilka razy, aby uzyskać pojedynczą macierz kowariancji od, jak już powiedziano. nie może się to zdarzyć za każdym razem, ale zależy również od początkowej konfiguracji gaussianów.

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
źródło

0

Imho, wszystkie odpowiedzi pomijają fundamentalny fakt. Jeśli spojrzy się na przestrzeń parametrów dla modelu mieszanki Gaussa, przestrzeń ta jest pojedyncza wzdłuż podprzestrzeni, w której w mieszance jest mniej niż pełna liczba składników. Oznacza to, że pochodne są automatycznie zerowe i zazwyczaj cała podprzestrzeń pojawia się jako mle. Mówiąc bardziej filozoficznie, podprzestrzeń kowariancji niższych niż ranga jest granicą przestrzeni parametrów i zawsze należy być podejrzliwym, gdy mle pojawia się na granicy - zwykle oznacza to, że czai się większa przestrzeń parametrów, w której można znaleźć „prawdziwy” mle. Istnieje książka zatytułowana „Statystyka algebraiczna” autorstwa Drtona, Sturmfelda i Sullivanta. Zagadnienie to zostało szczegółowo omówione w tej książce. Jeśli jesteś naprawdę ciekawy, powinieneś na to spojrzeć.

— meh
źródło

-2

$x_n$

N. (x_{n} | x_{n}, σ_{jot} 1 1) \to lim_{σ_{jot} \to x_{n}} \frac{1}{(2) π)^{1 / 2)} σ_{jot}} \exp (- \frac{1}{σ_{jot}} | x_{n} - σ_{jot} |^{2)}) = \frac{1}{(2) π)^{1 / 2)} σ_{jot}}

$\begin{equation} {\cal N}(x_n|x_n,\sigma_j 1\!\!1)\rightarrow \lim_{\sigma_j\rightarrow x_n}\frac{1}{(2\pi)^{1/2}\sigma_j} \exp \left( -\frac{1}{\sigma_j}|x_n-\sigma_j|^2 \right)= \frac{1}{(2\pi)^{1/2}\sigma_j} \end{equation}$

σ_{j} \to 0

$\sigma_j\rightarrow 0$

$x_m$ $\sigma_j$

N. (x_{m} | x_{m}, σ_{jot} 1 1) = \frac{1}{(2) π)^{1 / 2)} σ_{jot}} \exp (- \frac{1}{σ_{jot}} | x_{m} - σ_{jot} |^{2)})

$\begin{equation} {\cal N}(x_m|x_m,\sigma_j 1\!\!1)= \frac{1}{(2\pi)^{1/2}\sigma_j} \exp \left( -\frac{1}{\sigma_j}|x_m-\sigma_j|^2 \right) \end{equation}$

σ_{j} \to 0

$\sigma_j\rightarrow 0$

— Nacięcie
źródło

μ_{j}

$\mu_j$

σ_{j}

$\sigma_j$