<style> .reveal section img { background:none; border:none; box-shadow:none; } .reveal { font-size: 30px; } .reveal p { text-align: left; } .reveal ul { display: block; } .reveal ol { display: block; } </style> # El Teorema de Bayes ## Taller Nous Usos de la Informàtica <center><img width="150" src="https://i.imgur.com/vvZMy0I.png"></center> --- ## Objectius + Pensar com un analista de dades *bayesià* (metodologia). + Usar la fòrmula de Bayes per fer un model probabilístic a partir de dades (eina). --- ## Recordatori Donat un conjunt de dades representades per característiques $(A,B,C,\dots)$, els següents conceptes són crítics per la seva interpretació i ús: + $P(A)$, probabilitat **marginal**, o probabilitat d'ocurrència d'$A$ independentment d'altres variables. + $P(A,B)$, probabilitat **conjunta**, o probabilitat d'ocurrència **a la vegada** d'$A$ i $B$. + $P(A|B)$, probabilitat **condicional**, o probabilitat d'ocurrència d'$A$ **sabent** el valor de $B$. --- ## Recordatori Quina és la probabilitat que un estudiant seleccionat a l'atzar suspengui `ALGORISMICA AVANÇADA` sabent que va aprovar `ALGORISMICA`? Dades: <center><img width="450" src="https://i.imgur.com/IjeVy5b.png"></center> --- ## Recordatori $P(B|A)$? + $A$ és el conjunt d'estudiants que han aprovat `ALGORISMICA`. + $B$ és el conjunt d'estudiants que han suspès `ALGORISMICA AVANÇADA`. --- ## Recordatori Dades: <center><img width="350" src="https://i.imgur.com/IjeVy5b.png"></center> Càlcul de la probabilitat: $$P(B|A) = P(A,B) / P(A) = 6 / (54+6) = 0.1$$ --- ## Teorema de Bayes El Teorema de Bayes és fàcil de derivar a partir de les propietats bàsiques de la probabilitat: 1. Sabem (regla de la cadena) que: + $P(B|A) P(A) = P(A,B)$ + $P(A|B) P(B) = P(A,B)$ 2. Combinant aquestes dues equacions podem escriure: + $P(A)P(B|A) = P(B)P(A|B)$ --- ## Teorema de Bayes 3. Fòrmula de Bayes (1763): $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ El seu ús fonamental és passar de $P(B|A)$ a $P(A|B)$ (o viceversa). És útil sempre i quan el terme de la dreta de la igualtat, $P(B|A)$, sigui més fàcil de calcular que $P(A|B)$. --- ## Una injusticia històrica? Tot i que s'anomena teorema de Bayes, la forma general del teorema, tal com l'hem enunciat aquí, va ser escrita per primera vegada no per Thomas Bayes, sinó per Pierre-Simon Laplace (1749-1827). El que va fer Bayes va ser derivar el cas especial d'aquesta fórmula per "invertir" la distribució binomial. --- ## Teorema de Bayes ### Interpretacio diacrònica Fòrmula de Bayes bàsica: $$P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ La fòrmula de Bayes té una interpretació interessant en el camp de l'anàlisi de dades, quan parlem en termes d'hipòtesis/models i dades. --- ## Teorema de Bayes ### Interpretacio diacrònica Anàlisi d'un escenari en termes bayesians: + A dia d'avui creiem (tenim una **hipòtesi**) fermament (**mai de forma absoluta**) que `les dones han estat històricament discriminades` en el mercat de treball a causa dels biaixos de gènere durant els processos de contractació. Aquesta és una hipòtesi possible si considerem dues possibilitats: `hi ha discriminació històrica`, `no hi ha discriminació històrica`. + Llavors, obtenim la darrera base de **dades** de la Conselleria de Treball que conté dades rellevants, no conegudes abans, per analitzar aquesta hipòtesi. + L'anàlisi de les dades pot produir dos resultats: reduir o reforçar la nostra hipòtesi... --- ## Teorema de Bayes ### Interpretacio diacrònica Donades unes dades $D$ (o **evidències**) i un **conjunt** de possibles **hipòtesis** sobre aquestes dades $H$, voldriem un mètode objectiu per **modificar la nostra hipòtesi** en funció de les dades. Llavors, podem definir: + $P(H)$, o la probabilitat **a priori** de cada hipòtesi, ABANS de veure les dades. + $P(H|D)$, o la probabilitat de cada hipòtesi DESPRÉS de veure les dades. --- ## Teorema de Bayes ### Interpretacio diacrònica Expressant-ho amb la fòrmula de Bayes ens queda: $$P(H|D) = \frac{P(D|H)P(H)}{P(D)}$$ $P(D|H)$, tal com veurem, és normalment fàcil de calcular. En canvi, l'única forma de calcular $P(H|D)$, que és el que realment ens interessa, és amb la fòrmula de Bayes! --- ## Teorema de Bayes ### (versus freqüentista) L'estadística bayesiana interpreta les probabilitats com a mesures de **credibilitat** (la confiança que tenim) en un esdeveniment o hipòtesi, no com la freqüència d'esdeveniments a llarg termini. Les diferents creences no s'interpreten com a errors sinó com a diferents estats de coneixement sobre un esdeveniment per part de diferents observadors. La fórmula s'interpreta com una actualització de la creença després d'observar les dades. --- ## Exemple Volem assignar una probabilitat al fet que Bin Laden estigui mort. :::info :bulb: En aquest cas, la noció freqüentista de sèrie d'assaigs no està ben definida: no hi ha sèries d'assaigs idèntics (basats en esdeveniments repetibles) a considerar. Podem concloure que la noció clàssica de probabilitat no s'aplica a aquestes situacions. ::: --- ## Exemple El bayesianisme defineix la probabilitat d'una altra manera: el grau de creença que es produirà un esdeveniment. :::info :bulb: Per a un **freqüentista** no hi ha probabilitat d'aquest esdeveniment perquè no hi ha proves possibles (Bin Laden ha mort o no, no és una qüestió de probabilitat). Un **bayesià** assignaria una probabilitat a aquest esdeveniment en funció del seu estat de coneixement. L'estat del coneixement canvia quan es disposa de nova informació. ::: --- ## Hipòtesis i evidències (dades) $$P(H|E) = \frac{P(E|H)}{P(E)} P(H)$$ + $𝑃(𝐻|𝐸)$ s'anomena probabiitat **a posteriori** de l'hipòtesi. + $𝑃(𝐻)$ s'anomena probabilitat **a priori** de l'hipòtesi. + $𝑃(𝐸|𝐻)$ s'anomena la **versemblança** de l'evidència. + $𝑃(𝐸)$ és una constant de normalització. --- ## Hipòtesis i evidències (dades) La **versemblança** $𝑃(𝐸|𝐻)$ representa com de bé una determinada hipòtesi *explica* unes dades. Si les dades $E=\{x_1, \dots, x_n\}$ són independents, es calcula com: $$ \prod_i p_H(x_i) $$ on $p_H$ representa la funció de distribució de les dades segons aquella hipòtesi. --- ## Teorema de Bayes ### Interpretacio diacrònica <center><img width="700" src="https://hackmd.io/_uploads/SkqG-LCkbx.png"></center> --- ## Hipòtesis i evidències (dades) Si hi ha $n$ hipòtesis que són **mutuament exclusives** i **col·lectivament exhaustives**, podem calcular $P(E)$ com: $$ 𝑃(𝐸)=𝑃(𝐻_1)𝑃(𝐸|𝐻_1)+⋯+𝑃(𝐻_𝑛)𝑃(𝐸|𝐻_𝑛) $$ :::warning En general, tal com veurem, $𝑃(𝐻|𝐸),𝑃(𝐻),𝑃(𝐸|𝐻)$ i $𝑃(𝐸)$ seran funcions! ::: --- ## Exemple: Test mèdic Suposem que fem una prova mèdica per diagnosticar una malaltia a una població amb les següents característiques: + Sabem que $P(H_{sí})=5\%$. Això s'anomena la **prevalença** d'una malaltia. + A cada individu se li fa una prova amb precisió $P(E_{sí}|H_{sí})=P(E_{no}|H_{no}) = 90\%$. Això és fàcil de calcular amb una **prova controlada aleatòria clínica**. Volem saber la **probabilitat de tenir la malaltia si dones positiu**: $$Pr(H_{sí}|E_{sí})$$ --- ## Exemple: Test mèdic Podem utilitzar la regla de Bayes per calcular aquesta probabilitat a posteriori: $$ P(H_{sí}|E_{sí}) = \frac{P(E_{sí}|H_{sí}) P(H_{sí})}{P(E_{sí})} = $$ $$ = \frac{P(E_{sí}|H_{sí}) P(H_{sí})}{P(H_{sí})P(E_{sí}|H_{sí}) + P(H_ {no})P(E_{sí}|H_{no})} $$ --- ## Exemple: Test mèdic $$ P(H_{sí}|E_{sí}) = \frac{0,05 \times 0,9}{0,05 \times 0,9 + 0,95 \times 0,1} \approx 0.32 $$ Molts consideren contraintuïtiu que aquesta probabilitat sigui molt inferior a $90\%$! --- ## Exemple: Test mèdic Explicació visual: <center><img width="650" src="https://i.imgur.com/b6AyY75.png"></center> --- ## Exemple: Monty Hall Problem :::info :tv: Info: "**Let's Make a Deal**" is a television game show which originated in the United States and has since been produced in many countries throughout the world. The show is based around deals offered to members of the audience by the host. The traders usually have to weigh the possibility of an offer for valuable prizes, or undesirable items, referred to as "Zonks". *Source: Wikipedia*. ::: --- ## Exemple: Monty Hall Problem <center><img width="650" src="https://i.imgur.com/Z6ZMzbY.jpg"></center> --- ## Exemple: Monty Hall Problem :::info :tv: Info: **Monty Hall** was the original host of the game. The **Monty Hall problem** is based on one of the regular games of the show. It is a stick or switch problem: + Suppose you're on the game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. + You pick a door, say Door $A$ (the door is not open), and the host, who knows what's behind the doors, opens Door $B$, which has a goat. + He then says to you, "Do you want to pick Door $C$?" Is it to your advantage to switch your choice? *Source: Wikipedia*. ::: --- ## Exemple: Monty Hall Problem Podem utilitzar el punt de vista bayesià per resoldre aquest problema. + Al principi, hi ha diferents hipòtesis $H$ amb les seves probabilitats **a priori** corresponents: + $A$: el cotxe està darrere de la porta $A$; $P(H=\mbox{'A'}) = 1/3$ + $B$: el cotxe està darrere de la porta $B$; $P(H=\mbox{'B'}) = 1/3$ + $C$: el cotxe està darrere de la porta $C$; $P(H=\mbox{'C'}) = 1/3$ --- ## Exemple: Monty Hall Problem + Suposem que triem $A$ a l'atzar i Monty obre la porta $B$ (aquesta és la nostra evidència *$E$*). + Podem calcular $P(H=\mbox{'A'}|E) = \frac{P(H=\mbox{'A'})P(E|H=\mbox{'A'})}{P(E)}$ $$ = \frac{1/3 \times 1/2}{1/3 \times 1/2 + 1/3 \times 0 + 1/3 \times 1} = 1/3 $$ --- ## Exemple: Monty Hall Problem + El termes del denominador es poden entendre d'aquesta manera: + Suposem que inicialment vam triar $A$. + Es dedueix que si el cotxe està darrere de $A$, Monty ens mostrarà una cabra darrere de $B$ la meitat del temps. + Si el cotxe està darrere de $B$, Monty mai ens mostrarà una cabra darrere de $B$. + Finalment, si el cotxe està darrere de $C$, Monty ens mostra una cabra darrere de B cada cop. La majoria de la gent pensa intuïtivament que no hi ha cap diferència quedar-se o canviar, però això està malament. La veritat és que si no canvies de porta, la probabilitat de guanyar és d'1/3; si canvies, les teves possibilitats són 2/3. --- ## Exemple: Monty Hall Problem Per conèixer $P(H=\mbox{'C'}|E)$ podeu aplicar directament el teorema de Bayes, però hi ha una manera més senzilla de calcular-lo: ja que la probabilitat que estigui darrere de $A$ és 1/3 i la suma de les dues probabilitats ha de ser igual a 1, la probabilitat que el cotxe estigui darrere de $C$ és $1−1/3=2/3$. --- ## Exemple: Monty Hall Problem :::info :bulb: In fact, Paul Erdős, one of the most prolific and foremost mathematicians involved in probability, when initially told of the Monty Hall problem also fell victim to not understanding why opening a door should make any difference. Even when given the mathematical explanation multiple times, he wasn’t really convinced. It took several days before he finally understood the correct solution. *Source: Samuel Arbesman, Wired, 11.26.14* ::: --- ## Exemple: Monty Hall Problem ```python= import random iterations = 100000 doors = ["goat"] * 2 + ["car"] change_wins = 0 change_loses = 0 for i in range(iterations): random.shuffle(doors) n = random.randrange(3) sequence = list(range(3)) random.shuffle(sequence) for k in sequence: if k == n or doors[k] == "car": continue if doors[n] == "car": change_loses += 1 else: change_wins += 1 perc = (100.0 * change_wins) / (change_wins + change_loses) ``` --- ## El problema de la locomotora. + Una companyia ferroviària numera les seves locomotores per ordre $1 \dots N$. + Un dia veus una locomotora amb el número $60$. + Pots estimar quantes locomotores té la companyia ferroviària. --- ## El problema de la locomotora. :::info <small> :bulb: Durant la Segona Guerra Mundial, la *Divisió de Guerra Econòmica* de l'Ambaixada dels Estats Units a Londres va utilitzar anàlisis estadístiques per estimar la producció alemanya de tancs i altres equips. Els aliats occidentals havien capturat llibres de registre, inventaris i registres de reparació que incloïen números de sèrie de xassís i motor per a tancs individuals. L'anàlisi d'aquests registres va indicar que els números de sèrie s'assignaven per fabricant i tipus de tanc en blocs de 100 números, que els números de cada bloc s'utilitzaven seqüencialment i que no es van utilitzar tots els números de cada bloc. Així, el problema d'estimar la producció de tancs alemanys es podria reduir, dins de cada bloc de 100 números, a una forma del problema de la locomotores. A partir d'aquesta visió, els analistes nord-americans i britànics van produir estimacions substancialment inferiors a les estimacions d'altres formes d'intel·ligència. I després de la guerra, els registres indicaven que eren substancialment més precisos.</small> ::: <small> *(Source: http://greenteapress.com/thinkbayes/html/thinkbayes004.html#toc24)*</small> --- ## El problema de la locomotora. Segons l'observació, **sabem que el ferrocarril té 60 o més** locomotores. Però quantes més? Per aplicar el raonament bayesià, podem dividir aquest problema en dos passos: + Què sabíem sobre $N$ abans de veure les dades? + Per a qualsevol valor de $N$, quina és la probabilitat de veure les dades (una locomotora amb el número 60)? La resposta a la primera pregunta és $P(H)$. La resposta a la segona és $P(E|H)$. --- ## El problema de la locomotora. No tenim gaire base per triar $P(H)$, però podem començar amb alguna cosa senzilla i després considerar alternatives. Suposem que $N$ pot ser qualsevol valor d'1 a 1000: ```python= hypos = np.array(range(1, 1001)) priors = np.array([1.0/len(hypos) for hypo in hypos]) ``` <center><img width="650" src="https://i.imgur.com/eyzpSYT.png"></center> --- ## El problema de la locomotora. Ara necessitem calcular $P(E|H)$: + En una flota hipotètica de $N$ locomotores, quina és la probabilitat que veiem el número 60? Si hi ha $N$ locomotores, possibilitat de veure qualsevol locomotora en particular és d'1 $/N$. ```python= def Likelihood(data, hypo): if hypo < data: return 0.0 else: return 1.0/hypo ``` --- ## El problema de la locomotora. Si ho ajuntem tot calculant $P(H) P(E|H)$ per cada $H$: ```python= def Posterior(data, hypos, priors): import numpy as np posterior = np.array([Likelihood(data, hypo) for hypo in hypos]) * priors return posterior # After an update, the distribution is no longer normalized, # but because these hypotheses are mutually exclusive and # collectively exhaustive, we can renormalize. def Normalize(d): total = d.sum() factor = 1.0 / total for i in range(len(d)): d[i] *= factor return d posterior = Normalize(Posterior(60, hypos, priors)) ``` --- ## El problema de la locomotora. <center><img width="650" src="https://i.imgur.com/SgoOk9j.png"></center> El valor més probable, si l'haguéssiu d'endevinar, és 60. Potser no sembla una bona suposició; al cap i a la fi, quines possibilitats hi ha que acabis de veure el tren amb el nombre més alt? No obstant això, si voleu maximitzar les possibilitats d'obtenir la resposta exactament correcta (**hipòtesi més probable**), heu de dir 60. --- ## El problema de la locomotora. Però potser aquest no és l'objectiu correcte. Els bayesians proposen com alternativa calcular la **hipòtesi que correspon al valor mitjà de la distribució posterior**: ```python= def Meanp(hypos, posterior): total = 0.0 s = hypos * posterior return s.mean()*len(hypos) ``` i això és 333. --- ## Models de dades i Bayes --- ## Models de dades i Bayes Què podem fer amb un **corpus** de milions de paraules de llenguatge natural? + Entre d'altres moltes coses, podem fer un segmentador de frases, o com decidir que la frase `wheninthecourseofhumaneventsitbecomesnecessary`, que té aproximadament 35.000.000.000.000 maneres possibles de segmentar-se, ha de partir-se d'una manera concreta. --- ## Models de dades i Bayes L'any 2006, Google va fer públic (http://tinyurl.com/ngrams) un conjunt de dades estadístiques extretes d'una sèrie de documents en llenguatge natural que contenien més de 1.000.000.000.000 paraules en anglès. + Number of tokens: 1,024,908,267,229 + Number of sentences: 95,119,665,584 + Number of unigrams: 13,588,391 + Number of bigrams: 314,843,401 + Number of trigrams: 977,069,902 + Number of fourgrams: 1,313,818,354 + Number of fivegrams: 1,176,470,663 --- ## Models de dades i Bayes Les dades resumeixen els documents *comptant* el nombre de vegades que hi apareix una determinada paraula i també les seqüències de dues, tres, quatre i cinc paraules concretes. + Per exemple, `the` apareix 23.000.000.000 vegades (és un 2.2\% del total de paraules) i és la paraula més freqüent. + La paraula `rebating` apareix 12.750 vegades (és un 0.000001\% del total de paraules), les mateixes vegades que `fnuny` (aparentment, un error de la paraula `funny`). + Respecte a les seqüències de tres paraules, `Find all posts` apareix 13 milions de vegades (0.001\%), tant sovint com `each of the`, però molt menys que les 100 milions de vegades de `All Rights Reserved` (0.01\%). --- ## Models de dades i Bayes + Una col·lecció de textos s'anomena *corpus*. + El corpus està format per una seqüència de *tokens*, paraules i signes de puntuació/blancs. + Cada token diferent s'anomena *tipus*, i per tant la frase `Run, Lola Run` té 4 tokens (la coma conta) però només 3 tipus. + El conjunt de tots els tipus s'anomena *vocabulari*. El corpus de Google té un vocabulari de 13.000.000 de tipus. La majoria dels tipus tenen una freqüència petita: els 10 tipus més freqüents cobreixen casi una tercera part dels tokens, els 1000 més freqüents dues terceres parts, i els 100.000 més freqüents cobreixen el 98\% del corpus. + Una seqüència d'un token és un *unigrama*, una de dos token és un *bigrama* i una de $n$ token és un *ngrama*. --- ## Models de dades i Bayes + Direm que un cert tipus té una probabilitat $P$, com per exemple $P({\tt the})=0.022$, quan la freqüència del tipus al corpus sigui d'un $P \times 100$ \%. + Si $W$ és una seqüència de tokens, $W_3$ representa el tercer token i $W_{1:3}$ representa la seqüència del primer al tercer. + $P(W_i={\tt the} | W_{i-1}={\tt of} )$ s'anomena la probabilitat condicional de `the`, donat que `of` és el token anterior. --- ## Segmentació Com hem de segmentar? + Suposem que trobem la seqüència `insufficientnumbers`. + Si consultem el corpus, veurem que `insufficient numbers` hi apareix 20751 vegades i `in sufficient numbers` hi apareix 32378 vegades. + Tot i que la segona opció sembla més probable, no tenim seguretat. Cal una metodologia que ens permeti agregar totes les evidències i combinar-les de forma adequada. --- ## Solució amb un Model Probabilístic 1. Definim un *model probabilistic*. En el nostre cas, l'anomenarem **model de llenguatge** i serà una distribució de probabilitats sobre tots els possibles *strings* que es puguin formar a partir dels tipus definits. Els paràmetres d'aquest models s'aprendran del corpus i ens serviran per assignar una probabilitat a cada possible solució. 2. *Enumerem les solucions candidates*. En el nostre cas, hem d'enumerar de forma eficient totes les possibles segmentacions de la nostra seqüència. 3. *Escollim la solució amb màxima probabilitat*. En el nostre cas, aplicarem el model de llenguatge a cada possible solució candidata. --- ## Model Probabilístic En terminologia probabilística, el que volem s'escriu així: $$ solució = \arg\max_{c \in candidates} P_M(c) $$ on $M$ és un model de llenguatge calculat a partir del corpus. A partir d'ara, com que només considerarem un model, escriurem directament $P(c)$. La probabilitat d'una seqüència de paraules és pot escriure com: \begin{equation} P(W_{1:n}) = \prod_{k=1,\dots,n} P(W_k | W_{1:k-1}) \\ = P(W_1) \times P(W_2 | W_1) \dots \times P(W_n | W_{1:n-1}) \end{equation} --- ## Model Probabilístic És evident que no hi ha prou dades per calcular aquestes probabilitats, atès que hauríem de calcular $P(W_k | W_{1:k-1})$ per cada possible seqüència $W_{1:k-1}$. + Podem considerar el model simplificat que només pren en consideració els unigrames: $$ P(W_{1:n}) \approx \prod_{k=1,\dots,n} P(W_k) $$ En aquest cas, per segmentar `lacasade`, hem de considerar com a solució candidata el conjunt {`la`, `casa`, `de`} i calcular la seva probabilitat $P({\tt la}) \times P({\tt casa}) \times P({\tt de})$. Si cap altre conjunt un producte més gran de probabilitats, llavors ja hem trobat la solució. --- ## Com seleccionem els candidats? + Un string de $n$ caràcters té $2^{n-1}$ segmentacions possibles, atès que hi ha $n-1$ llocs possibles entre lletra i lletra. + Per tant, l'enumeració de tots els candidats possibles no és una opció i hem de buscar una opció més eficient. + Podem implementar una aproximació *recursiva* definida a partir de segmentació entre una primera paraula (la longitud de la qual està limitada per la longitud de la paraula més llarga del corpus) i la resta del text. + De tots els possibles candidats, la que té $P(first) \times P(remaining)$ màxima és la millor. --- ## Com seleccionem els candidats? Suposem que tenim `wheninthecourseofhumaneventsitbecomesnecessary`. L'algorisme determinaria que `when` és la primera paraula d'aquesta manera:  --- ## Com seleccionem els candidats? <center><img width="550" src="https://i.imgur.com/EUBHTS0.png"></center> + `product` és una funció que multiplica una llista de nombres. + `Pw` és una funció que retorna la probabilitat d'una paraula de la llista dels unigrames. --- ## Com seleccionem els candidats? + `demo` és un *decorador* de Python que manté en memòria els resultats de les crides anteriors d'una funció de manera que no s'han de recalcular si es tornen a necessitar. ```python def memo(f): "Memoize function f." table = {} def fmemo(*args): if args not in table: table[args] = f(*args) return table[args] fmemo.memo = table return fmemo ``` --- ```python= @memo def fib(n): if n==1: return 1 if n==0: return 0 return fib(n-1) + fib(n-2) def fibonacci(n): import time import math t1 = time.clock() a = fib(n) t2 = time.clock() print "El temps de proces ha estat %1.3f ms" % ((t2-t1)*1000) >>> fibonacci(300) El temps de proces ha estat 0.845 ms >>> fibonacci(301) El temps de proces ha estat 0.006 ms ``` --- ```python >>> splits("noususos") [('n', 'oususos'), ('no', 'ususos'), ('nou', 'susos'), ('nous','usos'), ('nousu', 'sos'), ('nousus', 'os'), ('noususo','s'), ('noususos', '')] >>> segment("noususos") ['nous', 'usos'] ``` --- ## El programa + Sense `memo` la crida a la funció `segment` amb un string de $n$ caracters implica $2^n$ crides recursives. + Amb `memo` ho transformem en un procés de *programació dinàmica* i només en fa $n$. Cada crida considera $O(L)$ segmentacions (on $L$ és la longitud màxima d'una paraula), i per cada una evalua $O(n)$ probabilitats, per tant la complexitat és $O(n^2L)$. + Respecte `Pw`, accedeix al fitxer amb els estadístics (`count`) de cada paraula i estima la probabilitat com `count(word)/N`, on $N$ és el nombre d'elements del corpus. --- ## Com calculem `Pw` Què fem si la paraula no és al diccionari? (no podem retornar 0) + La paraula menys vista del diccionari té una probabilitat de $12710/N$ i per tant una paraula no vista hauria de tenir una probabilitat menor. + Una heurística que funciona és assignar una probabilitat inicial de $12710/N$, però decrementem per un factor 10 per cada lletra de la paraula no vista (com més llarga, més improbable). --- ## Resultats <center><img width="650" src="https://i.imgur.com/FtIY2ag.jpg"></center> --- ## Resultats + Un dels errors que hi ha és que no ha segmentat les paraules `sitdown`. + El motiu és que el producte de les probabilitats de les dues paraules (que tenen probabilitats 0.003\% i 0.04\% respectivament) és lleugerament inferior que la de `sitdown`. Però si miréssim les probabilitats dels bigrames, veuriem que la probabilitat de `sit down` és 100 vegades superior a la de `sitdown`! + Per tant, aquest error es pot resoldre considerant un model de bigrames: $$ P(W_{1:n}) = \prod_{k=1,\dots,n} P(W_k | W_{k-1}) $$ --- ## Model de bigrames Però la taula amb els valors de tots els bigrames no cap a la memòria! + Si considerem els bigrames que apareixen més de 100.000 vegades obtenim una taula de 250.000 entrades, que si que hi cap. Llavors podem estimar $P({\tt down}|{\tt sit})$ com `count(sit down)/count(sit)`. + Si un bigrama no apareix a la taula, llavors usem l'estimació dels unigrames. <center><img width="450" src="https://i.imgur.com/Ej5ZbW4.png"></center> --- ## Model de bigrames + La funció `cPw` no genera una distribució de probabilitats (pot sumar més que 1), tot i que a la pràctica funciona bé. Per aquest motiu s'anomena *stupid backoff*. + Els nous resultats són que ara trobem `sit down` 1.698 vegades més probable que `sitdown` perquè `sit down` té una freqüència alta i `to sitdown` no: <center><img width="450" src="https://i.imgur.com/5t1yqXo.png"></center> --- ## Model de bigrames Compte! + Quan apliquem la funció `Pwords` a una seqüència llarga de paraules podem tenir problemes d'*underflow* per culpa del nombre de multiplicacions. + El nombre més petit que podem representar a l'ordinador és $4.9 \times 10^{-324}$ i qualsevol cosa més petita és 0. + Una solució senzilla és treballar amb els logaritmes de les probabilitats i fer una suma de logaritmes enlloc d'una multiplicació. $$ \log \prod_{i} x_i = \sum_i \log x_i $$ + Treballar amb els logaritmes de les probabilitats no afecta $\arg\max_{c \in candidates} P(c)$, el màxim és el mateix candidat. --- ## Model de bigrames <center><img width="550" src="https://i.imgur.com/KwLY1lE.png"></center>