ML - 11 - Probabilistic Classification I

Per stimare \(P(C_k)\) possiamo applicare lo stimatore ML (Maximum Likelihood) a partire dalle collezioni \(\mathcal{C}_1 \mathcal{C}_2\) per ottenere

\[\begin{split} P(C_1) &= \frac{|\mathcal{C}_1|}{|\mathcal{C}_1| + |\mathcal{C}_2|} \\ \\ P(C_2) &= \frac{|\mathcal{C}_2|}{|\mathcal{C}_1| + |\mathcal{C}_2|} \\ \end{split}\]

---

Per sitmare le probabilità \(P(d|C_k)\) invece utilizziamo l'ipotesi bag of words per considerare il documento \(d\) come un multiset di \(n_d\) termini

\[d = \{\overline{t}_1, \overline{t}_2, \ldots, \overline{t}_{n_d}\}\]

Tramite la regola del prodotto delle probabilità otteniamo

\[\begin{split} P(d|C_k) &= P(\overline{t}_1, \overline{t}_2, \ldots, \overline{t}_{n_d} | C_k) \\ &= P(\overline{t}_1 | C_k) P(\overline{t}_2 | \overline{t}_1, C_k) \cdots P(\overline{t}_{n_d} | \overline{t}_1, \overline{t}_2, \ldots, \overline{t}_{n_{d - 1}}C_k) \\ \end{split}\]

Per semplificare ulteriormente il calcolo introduciamo quindi un'ulteriore ipotesi semplificativa, nota con il nome di naïve naive bayes assumption. Questa ipotesi ci dice che i termini sono pairwise conditionally independent, ovvero che data la classe \(C_k\) si ha che

\[P(\overline{t}_i, \overline{t}_j | C_k) = P(\overline{t}_i | C_k) P(\overline{t}_2 | C_k)\]

Applicando questa uguaglianza al risultato di prima otteniamo

\[\begin{split} P(d|C_k) &= P(\overline{t}_1 | C_k) P(\overline{t}_2 | \overline{t}_1, C_k) \cdots P(\overline{t}_{n_d} | \overline{t}_1, \overline{t}_2, \ldots, \overline{t}_{n_{d - 1}}C_k) \\ &= P(\overline{t}_1 | C_k) P(\overline{t}_2 | C_k) \cdots P(\overline{t}_{n_d} | C_k) \\ &= \prod\limits_{j = 1}^{n_d} P(\overline{t}_j |C_k) \\ \end{split}\]

Se abbiamo due classi \((K = 2)\) avevamo visto che

\[P(C_1 | x) = \sigma(a(x))\]

dove

\[a(x) = \log{\frac{P(x|C_1) P(C_1)}{P(x|C_2) P(C_2)}}\]

Andando a sostituire l'espressione di prima per \(P(x|C_k)\) otteniamo quindi

\[\begin{split} a(x) &= \log{\frac{P(x|C_1) P(C_1)}{P(x|C_2) P(C_2)}} \\ &= \log{\frac{\frac{1}{(2\pi)^{d/2} |\mathbf{\Sigma}|^{1/2}} \cdot \text{exp}\Big(-\frac12 (x - \mathbf{\mu}_1)^T \mathbf{\Sigma}^{-1} (x - \mathbf{\mu}_1) \Big)P(C_1)}{\frac{1}{(2\pi)^{d/2} |\mathbf{\Sigma}|^{1/2}} \cdot \text{exp}\Big(-\frac12 (x - \mathbf{\mu}_2)^T \mathbf{\Sigma}^{-1} (x - \mathbf{\mu}_2) \Big)P(C_2)}} \\ &= \frac12 \Big(\mathbf{\mu}_2^T \mathbf{\Sigma}^{-1} \mathbf{\mu}_2 - x^T \mathbf{\Sigma}^{-1} \mathbf{\mu}_2 - \mathbf{\mu}_2^T \mathbf{\Sigma}^{-1} x\Big) \\ &\;\;\;\;\; - \frac12 \Big( \mathbf{\mu}_1^T \mathbf{\Sigma}^{-1}\mathbf{\mu}_1 - x^T \mathbf{\Sigma}^{-1} \mathbf{\mu}_1 - \mathbf{\mu}_1^T \mathbf{\Sigma}^{-1} x\Big) + \log{\frac{P(C_1)}{P(C_2}}\\ \end{split}\]

Notando poi che i risultati di tutti i prodotti che coinvolgono \(\mathbf{\Sigma}^{-1}\) sono scalari, e in particolare dato che ogni scalare è uguale al suo trasporto, otteniamo che

\[\begin{split} x^T \mathbf{\Sigma}^{-1} \mathbf{\sigma}_1 &= \sigma_1^T \mathbf{\Sigma}^{-1} x \\ \\ x^T \mathbf{\Sigma}^{-1} \mathbf{\sigma}_2 &= \sigma_2^T \mathbf{\Sigma}^{-1} x \\ \end{split}\]

possiamo quindi semplificare per ottenere

\[\begin{split} a(x) &= \frac12 \Big(\mu_2^T \mathbf{\Sigma}^{-1} \mu_2 - \mu_1^T \mathbf{\Sigma}^{-1} \mu_1 \Big) + \Big(\mu_1^T \mathbf{\Sigma}^{-1} - \mu_2^T \mathbf{\Sigma}^{-2} \Big)x + \log{\frac{P(C_1)}{P(C_2)}} \\ &= \mathbf{w}^T \mathbf{x} + w_0 \\ \end{split}\]

con

\[\begin{split} \mathbf{w} &= \mathbf{\Sigma}^{-1}(\mu_1 - \mu_2) \\ \\ w_0 &= \frac12 \Big(\mu_2^T \mathbf{\Sigma}^{-1} \mu_2 - \mu_1^T \mathbf{\Sigma}^{-1} \mu_1 \Big) + \log{\frac{P(C_1)}{P(C_2)}} \\ \end{split}\]

---

Alla fine abbiamo quindi ottenuto

\[P(C_1 | x) = \sigma(\mathbf{w}^T x + w_0)\]

Dove \(\mathbf{w}\) e \(w_0\) possono essere stimati a partire dal training set. Una volta calcolate queste probabilità possiamo poi classificare l'elemento \(x\) in una delle due classi \(C_1\) o \(C_2\).

---

Volendo vedere la funzione discriminante che partiziona il piano tra i punti appartenenti alla classe \(C_1\) e quelli appartenenti alla classe \(C_2\) l'idea è quelal di imporre la condizione

\[P(C_1|x) = P(C_2|x) \iff \sigma(a(x)) = \sigma(-a(x))\]

e dato che la funzione è monotona questo equivale a dire che \(a(x) = -a(x)\) e quindi \(a(x) = 0\). Il luogo dei punti che fa da confine tra le due classi è quindi descritto dai punti che soddisfano la seguente equazione

\[\mathbf{w}^T x + w_0 = 0\]

sostituendo in termini dei parametri delle gaussiane sottostanti otteniamo

\[\mathbf{\Sigma}^{-1}(\mu_1 - \mu_2)x + \frac12(\mu_2^T \mathbf{\Sigma}^{-1} \mu_2 - \mu_1^T \mathbf{\Sigma}^{-1} \mu_1) + \log{\frac{P(C_2)}{P(C_1)}} = 0\]

---

Se poi assumiamo che la matrice di covarianza è diagonale a valori costanti, ovvero che non ci sia correlazione tra features diverse, in formula \(\mathbf{\Sigma} = \lambda \mathbf{I}\), allora la funzione discriminante è data da

\[2(\mu_2 - \mu_1) x + ||\mu_1||^2 - ||\mu_2||^2 + 2 \lambda \log{\frac{P(C_2)}{P(C_1)}} = 0\]

Geometricamente questa ulteriore assunzione ci dice che le due distribuzioni hanno simmetrica sferica.

---

Quanto visto per il caso binario può essere facilmente esteso quando abbiamo più di due classi \((K > 2)\). In questo caso al posto di utilizzare la funzione sigmoid utilizziamo la funzione softmax

\[P(C_k|x) = s(a_k(x))\]

con

\[a_k = \log{\Big(P(x|C_k)P(C_k)\Big)}\]

Applicando le stesse considerazioni fatte prima si ottiene

\[\begin{split} a_k(x) &= \frac12 \Big(\mu_k^T \mathbf{\Sigma}^{-1} x - \mu_k^T \mathbf{\Sigma}^{-1} \mu_k \Big) + \log{P(C_k)} - \frac{d}{2} \log{(2\pi)} - \frac12 \log{|\mathbf{\Sigma}|} \\ &= \mathbf{w}_k^T x + w_{0,k} \\ \end{split}\]

e quindi anche \(a_k(x)\) è ottenuta tramite una combinazione lineare delle features.

---

Nel caso in cui abbiamo più classi i decision boundaries corrispondono alle regioni in cui ci sono due classi \(C_j\) e \(C_k\) tali per cui le probabilità a posteriori sono uguali tra loro e sono più grandi di tutte le altre classi. In formula,

\[P(C_k|x) = P(C_j|x) \;\;\;\;\;,\;\;\;\; P(C_i|x) < P(C_k|x) \,\,\,\,\,\, i \neq j, k\]

In questo caso quindi si ha

\[e^{a_k(x)} = e^{a_j(x)} \;\;\;\;\;,\;\;\;\; e^{a_i(x)} < e^{a_k(x)} \,\,\,\,\,\, i \neq j, k\]

e quindi

\[a_k(x) = a_j(x) \;\;\;\;\;,\;\;\;\; a_i(x) < a_k(x) \,\,\,\,\,\, i \neq j, k\]

ovvero questi boundaries sono lineari.

La derivata della log-likelihood rispetto a \(\pi\) è data da

\[\begin{split} \frac{\partial l}{\partial \pi} &= \frac{\partial }{\partial \pi} \sum\limits_{i = 1}^n \Big( t_i \log{\pi} + (1 - t_i) \log{(1 - \pi)}\Big) \\ &= \sum\limits_{i = 1}^n \Big(\frac{t_1}{\pi} - \frac{(1 - t_i)}{1 - \pi}\Big) \\ &= \frac{n_1}{\pi} - \frac{n_2}{1 - \pi} \\ \end{split}\]

che quando impostata a \(0\) ci da come risultato

\[\pi = \frac{n_1}{n}\]

---

Allo stesso modo, il massimo rispetto alle medie \(\mu_1\) (e \(\mu_2)\) può essere calcolato tramite il gradiente della log-likelihood

\[\begin{split} \frac{\partial l}{\partial \mu_1} &= \frac{\partial}{\partial \mu_1} \sum\limits_{i = 1}^n t_i \log{(\mathcal{N}(x_i | \mu_1, \mathbf{\Sigma}))} \\ &= \ldots \\ &= \mathbf{\Sigma}^{-1} \sum\limits_{i = 1}^n t_i(x_i - \mu_1) \\ \end{split}\]

notiamo quindi che abbiamo \(\frac{\partial l}{\partial \mu_1} = 0\) quando

\[\sum\limits_{i = 1}^n t_i x_i = \sum\limits_{i = 1}^n t_i \mu_1 \]

e quindi

\[\mu_1 = \frac{1}{n_1} \sum\limits_{x_i \in C_1} x_i\]

che è proprio il punto medio degli elementi facente parte della classe \(C_1\).

---

Infine, per quanto riguarda \(\mathbf{\Sigma}\), è possibile vedere che

\[\mathbf{\Sigma} = \frac{n_1}{n} \mathbf{S}_1 + \frac{n_2}{n} \mathbf{S}_2\]

dove

\[\begin{split} \mathbf{S}_1 &= \frac{1}{n_1} \sum\limits_{x_1 \in C_1} (x_i - \mu_1) (x_i - \mu_1)^T \\ \\ \mathbf{S}_2 &= \frac{1}{n_2} \sum\limits_{x_1 \in C_2} (x_i - \mu_2) (x_i - \mu_2)^T \\ \end{split}\]