-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path004_prakticni.tex
127 lines (101 loc) · 11.2 KB
/
004_prakticni.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
Praktični dio napravljen je temeljem rada \citep{resnik2010gibbs}. Resnik i Hardisty objašnjavaju ostvarenje Naivnog Bayesa \engl{Naive Bayes} pomoću Gibbsovog uzorkovanja na primjeru klasifikacije polariteta dokumenata prema riječima u dokumentima.
U praktičnom dijelu napravit će se sustav koji izvodi algoritam Naivnog Bayesa, a potrebne vjerojatnosti računa Gibbsovim uzorkovanjem.
\section{Skup podataka}
\label{sec:skup}
Besplatno dostupna biblioteka \textit{Natural Language Toolkit, NLTK} \footnote{Dostupno na \url{http://www.nltk.org/} .} za programski jezik \textit{Python} sadrži pripremljene korpuse teksta.
Za potrebe Gibbsovog uzorkovanja korišten je skup podataka \textit{movie\_reviews} koji sadrži osvrte na filmove. Format zapisa u korpusu je $<T, S>$, gdje je $T$ tekst osvrta, a $S \in \{'pos', 'neg'\}$ označeni polaritet osvrta. U nastavku će se za \textit{'pos'} kritike koristiti broj $1$, a za \textit{'neg'} kritike broj $0$. Pozitivne kritike označene su oznakom \textit{'pos'}, a negative \textit{'neg'}. Primjer negativne kritike prikazan je unutar slike \ref{fig:critic_example}.
Programski jezik korišten za \textit{Python}, verzija 2.7.3, u 64-bitnom okruženju. Dodatne \textit{Python} biblioteke korištene prilikom izrade programa su \textit{numpy}\footnote{Dostupno na \url{http://www.numpy.org/}.} i već spomenuti \textit{nltk}.
\begin{figure}
\begin{bclogo}
{Universal soldier} \footnotesize{ ex - universal soldier luc has to battle a group of newer - model engineered fighters gone bad . the review jean - claude van damme has a one - liner early on in universal soldier : the return , his latest attempt to remain relevant , that sums up this entire movie ; he says " been there , done that . " no film critic could possibly sum up van damme ' s recent film choices any better . while other ageing action stars have wisely moved into other film genres ( schwarzenegger makes as many family comedies as he does action films ) , van damme stubbornly persists in sticking with what used to work for him : martial arts and guns . this unwillingness or perhaps inability to move into new genres has caused van damme to enter the straight to video world , with legionnaire never seeing the inside of a multiplex . he joins fellow martial artist / action star steven seagal as they watch their film careers rapidly fizzle away . universal soldier : the return is truly poor . the plot is a complete copy of several action films from this decade , specifically terminator 2 : judgement day and the similarly named soldier . soldier ' s kurt russell was an older model super - soldier sent off to retirement when circumstances forced him to battle his successors , for the good of a planet ; schwarzenegger ' s terminator in t2 tried to save john connor from a newer model killing machine , the t - 1000 ; and jean - claude , a former universal soldier , has to save the planet from the rampage of a group of , you guessed it , newer model soldiers .}
\end{bclogo}
\caption{Primjer negativnog osvrta iz movie\_reviews baze podataka}
\label{fig:critic_example}
\end{figure}
\section{Matematički model}
U ovom slučaju, dokument je skup riječi koje sadrži, tzv. \engl{bag of words} princip. Za dokument $W_j$ potrebno je dodijeliti adekvatan polaritet $L_j = 0$ ili $L_j = 1$. Skup dokumenata $\mathbb{C}_{k}$ pripada skupini klase $L_j = k$, a dobije se tako da se prebroje svi dokumenti $W_j$ s $L_j=k$, prema tome $\mathbb{C}_{k} = \{W_j | L_j = k\}$. Potrebno je pronaći polaritet $L_j$ koji, za poznati dokument $W_j$, pronalazi maksimalnu vjerojatnost $P(L_j|W_J)$. Prema Bayesovom pravilu vrijedi:
\begin{equation}
L_j = \argmax_L P(L|W_j) = \argmax_L \frac{P(W_j|L)P(L)}{P(W_j)}.
\end{equation}
Moguće je izostaviti nazivnik $P(W_j)$ jer nije ovisan o $L_j$. Na ovaj način nastoji se modelirati način na koji su dokumenti nastali, što se naziva generativnim modelom \engl{Generative model}. Odabir polariteta $L_j$ modelira se Bernoulijevom raspodjelom s parametrom $\pi$:
\begin{equation}
L_j \sim Bernoulli(\pi),
\end{equation} Potrebno za svaku poziciju riječi u dokumentu $R_i$ odabrati riječ $w_j$ temeljem distribucije vjerojatnosti riječi. Odabir distribucije vjerojatnosti iz koje se uzorkuje ovisan je dodijeljenom polaritetu dokumenta $L_j$. Moguće distribucije označavat će se $\theta_0$ i $\theta_1$. Dokument $W_j$ gradit će se temeljem multinomijalne distribucije:
\begin{equation}
W_j = Multinomijalna(R_j, \theta_{L_{j}}).
\end{equation}
Pretpostavlja se da je uzorkovanje međusobno neovisno. Distribucijama $L_j$ i $W_j$ nastoji se aproksimirati način na koji su dobiveni stvarni podaci.
\subsection{Apriori parametri}
Gore spomenute parametre distribucija $\pi$ i $\theta$ nužno je imati prije generiranja raspodjela za $W_j$ i $L_j$. Dobivanje početnih vrijednosti za $\pi$ i $\theta$ će se dobiti iz jednolike raspodjele. Konkretno, $\pi$ će se generirati Beta distribucijom s parametrima $\gamma_{\pi 1} = 1$ i $\gamma_{\pi 2} = 1$:
\begin{equation}
\pi \sim Beta(\gamma_{\pi}).
\end{equation}
Parametri apriori vrijednosti nazivaju se hiperparametrima. Kako oba parametra Beta distribucije ovdje iznose 1, svi događaji su jednako vjerojatna, što znači da je apriori znanje o sustavu nedostupno. U slučaju $\theta$ parametra, on je modeliran Dirichlechtovom distribucijom, generaliziranom Beta distribucijom važećoj u više od dvije dimenzije:
\begin{equation}
\theta \sim Dirichlet(\gamma_{\theta})
\end{equation}
\subsection{Zajednička distribucija}
Prostor stanja u ovom problemu sastoji se skalarne varijable parametra $\pi$, dva parametarska vektora $\theta_1$ i $\theta_2$, oznaka klase $L_N$ (za svaki od $N$ dokumenata) i vektora $W_J$ ($J$ je broj riječi). Gibbsovo uzorkovanje kreće se kroz $k$-dimenzionalni prostor definiran ovim varijablama. Uvjetne distribucije definiraju matricu prijelaza između stanja, a zajednička distribucija je ciljna distribucija koju želimo aproksimirati. U našem slučaju zajednička distribucija iznosi:
\begin{equation}
P(\pi|\gamma_{\pi 1}\gamma_{\pi 2})P(L|\pi)P(\theta_0 | \gamma_0)P(\theta_1 | \gamma_1)P(\mathbb{C}_0|\theta_0 ,L)P(\mathbb{C}_1 | \theta_1 , L).
\end{equation}
Postupak matematičke preobrazbe dobivene jednadžbe opisan je u \citep{resnik2010gibbs}. Konačan rezultat je:
\begin{equation}
P(\mathbb{C}, L, \pi , \theta_0 , \theta_1 ; \mu) \propto \pi^{C_1+\gamma_{\pi 1}-1}(1-\pi)^{C_0 + \gamma_{\pi 0} - 1} \prod_{i=1}^{V} \theta_{0,i}^{N_{\mathbb{C_0}}(i)+\gamma_{\theta i} - 1}\theta_{1,i}^{\mathbb{C_1}}(i)+\gamma_{\theta i} - 1.
\end{equation}
Dodatno, moguće je integrirati po varijabli $\pi$ i tako reducirati zajedničku distribuciju čime se dobije konačno rješenje:
\begin{equation}
P(L, \mathbb{C}, \theta_0 , \theta_1 ; \mu) \propto \frac{\Gamma(\gamma_{\pi 1}+\gamma_{\pi 0}}{\Gamma(\gamma_{\pi 1})\Gamma(\gamma_{\pi 0})} \frac{\Gamma(C_1+\gamma_{\pi 1}\Gamma(\mathbb{C_0}+\gamma_{\pi 0})}{\Gamma(N+\gamma_{\pi 1} + \gamma_{\pi 0})} \prod_{i=1}^{V} \theta_{0,i}^{N_{\mathbb{C_0}}(i)+\gamma_{\theta i} - 1}\theta_{1,i}^{\mathbb{C_1}}(i)+\gamma_{\theta i} - 1.
\end{equation}
\subsection{Gibbsovo uzrokovanje}
Gibbsovim uzorkovanjem se u općem slučaju dodjeljuje vrijednost varijabli $Z_i$ uzorkovanjem iz uvjetne distribucije:
\begin{equation}
P(Z_i | z_i^{(t+1)}, \dots, z_{i-1}^{t+1}, \dots , z_r^{t}).
\end{equation}
Uzorkovanje vrijednosti u trenutku $(t+1)$ moguć je nakon dobivanja uzorka svih varijabli u trenutku $t$. U našem slučaju, u trenutku $t$ poznat je broj riječi u svakom dokumentu, broj dokumenata označen s negativnim odnosno pozitivnim sentimentom, broj riječi po dokumentima označenim negativnim odnosno pozitivnim sentimentom, oznake sentimenta po dokumentu i trenutne vrijednosti hiperparametara $\theta_1$ i $\theta_2$. Izračun sentimenta $L$ se dobije uzorkovanjem prema vjerojatnostima dobivenih fiksiranjem uvjetnih vjerojatnosti za $L=0$ (negativni sentiment) i $L=1$ (pozitivni sentiment). Prema tome, $L_{i}^{(t+1)}$ se računa iz uvjetne distribucije:
\begin{equation}
P(L_i|L_{1}^{t+1}, \dots , L_{i-1}^{t+1}, \dots , L_{i+1}^t{t}, L_{N}^{t},\mathbb{C}, \theta_{0}^{t}, \theta_{1}^{t}; \mu).
\end{equation}
Na sukladan način se dobiju i vrijednosti $\theta_0$ i $\theta_1$:
\begin{equation}
P(\theta_{0}^{(t+1)}|L_{1}^{(t+1)},\dots , L_{N}^{(t+1)}, \mathbb{C}, \theta_{1}^{(t)};\mu)
\end{equation}
\begin{equation}
P(\theta_{1}^{(t+1)}|L_{1}^{(t+1)},\dots , L_{N}^{(t+1)}, \mathbb{C}, \theta_{0}^{(t+1)};\mu)
\end{equation}
\section{Programska implementacija}
\subsection{Priprema podataka}
Prilikom programske implementacije korištene su brojne biblioteke spomenute u \ref{sec:skup}. Uvoz biblioteka napravljen je kao na slici \ref{alg:import}. U skupu podataka \textit{movie\_reviews} ima 2000 osvrta i približno 32000 različitih riječi. Zbog pojednostavljena uzorkovanja i smanjivanja prostora stanja napravljen je Naivni Bayesov klasifikator te su njime izvučene najveće vjerojatnosti određene oznake za $P(L|w)$, gdje je $L$ oznaka sentimenta, a $w$ riječ. Korišteno je 500 od 32000 mogućih riječi. Deset riječi s tog popisa prikazano je slikom \ref{alg:most_info}. Primjerice, korištenje riječi seagal (glumac) u kritici znači da će vjerojatnost da je kritika biti negativna je 13.2 veća od vjerojatnosti pozitivne vjerojatnosti. Izračun tih riječi prikazan je programskim kodom na slici \ref{alg:naive_bayes}. U konačnici gradi se matrica frekvencije riječi i dokumenata (kod na slici \ref{alg:word_doc_freq}). Element $x$ na indeksu $i,j$ govori da se riječ $j$ pojavljuje u dokumentu $i$ $x$ puta. Matrica je prikazana primjerom \ref{alg:mat_word_freq}.
\begin{figure}
\lstinputlisting[language=Python, firstline=1, lastline=5]{classifier_naive_bayes.py}
\caption{Uvoz bibilioteka}
\label{alg:import}
\end{figure}
\begin{figure}
\lstinputlisting[language=Python]{most_informative.py}
\caption{Riječi s najvišim $P(L|w)$}
\label{alg:most_info}
\end{figure}
\begin{figure}
\lstinputlisting[language=Python, firstline=7, lastline=29]{classifier_naive_bayes.py}
\caption{Algoritam naivnog Bayesa koji računa $P(L|w)$}
\label{alg:naive_bayes}
\end{figure}
\begin{figure}
\lstinputlisting[language=Python, firstline=40, lastline=64]{classifier_naive_bayes.py}
\caption{Izračun matrice frekvencija riječi i dokumenata}
\label{alg:word_doc_freq}
\end{figure}
\begin{figure}
\centering
\lstinputlisting{corpus.txt}
\caption{Primjer matrice frekvencije riječi i dokumenata}
\label{alg:mat_word_freq}
\end{figure}
\subsection{Inicijalizacija}
Matrica frekvencija riječi po dokumentima i pripadajuće oznake sentimenta predstavljaju ulazni skup podataka programu Gibbsovog uzorkovanja. Idući nužni korak je dobivanje inicijalnih vrijednosti hiperparametara $\pi$ i vektora $\theta$. Zahvaljujući \textit{Pythonovim} paketima uzorkovanje iz Dirichletove distribucije moguće je provesti iznimno jednostavno. Temeljem hiperparametara uzorkuju se parametri nužni za Gibbsovo uzorkovanje. Inicijalizacija je prikazana slikom \ref{alg:hyp_params}. Gibbsovo uzorkovanje dodatno je parametrizirano ukupnim brojem iteracija, brojem iteracija odbacivanja, udaljenosti između uzoraka, objašnjenih u poglavlju \ref{cha:gibbs_dsc}.
\begin{figure}
\lstinputlisting[language=Python, firstline=215, lastline=221]{gibbs_sampler.py}
\caption{Inicijalizacija hiperparametara}
\label{alg:hyp_params}
\end{figure}