<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> # Recuperació d'informació ## Taller Nous Usos de la Informàtica <center><img width="150" src="https://i.imgur.com/vvZMy0I.png"></center> --- ## El problema: recuperació de documents <center><img width="500" src="https://hackmd.io/_uploads/HJJeY1fBT.jpg"></center> --- ## Què és l'*Information Retrieval* (IR)? L'**IR** s'ocupa de la representació, emmagatzematge, organització i accés a elements d'informació (documents, pàgines web, catàlegs en línia, registres estructurats, objectes multimèdia). + Actualment, l'IR inclou: cerca web, classificació de text, interfícies d'usuari, visualització de dades, filtratge i idiomes. Les necessitats d'informació dels usuaris són variades en termes de complexitat i diversitat, però l'enfocament més comú és **traduir** la seva necessitat d'informació a una **consulta** (*query*). --- ## El problema IR Aquest procés de traducció produeix un conjunt de **paraules clau**, o termes indexats, que **resumeixen la necessitat d'informació** de l'usuari. :::danger **L'objectiu clau d'un sistema IR és recuperar tots els elements que són rellevants per a una consulta d'usuari, alhora que es recupera el mínim possible d'elements no rellevants**. ::: --- ## El problema IR Exemple d'un sistema complex: <center><img width="500" src="https://i.imgur.com/nqEKPQN.png"></center> --- ## Recuperació i ordenació --- ## Models d'IR El modelatge en IR és un procés complex destinat a produir una **funció d'ordenació**. :::danger **Funció d'ordenació**: una funció que assigna puntuacions (*scores*) als documents i que representa la seva rellevància respecte a una consulta determinada. ::: Aquest procés consta de dues tasques principals: + La definició d'un esquema de **representació** dels documents i consultes. + La definició d'una **funció d'ordenació** dels documents segons la seva rellevància, fent servir entre d'altres coses les **similituds** entre documents i consultes. --- ## Recuperació i ordenació Els sistemes d'IR solen adoptar els **termes indexats** o **paraules clau** per indexar i recuperar els documents. + En general, un **terme indexat** és qualsevol paraula que apareix en un document i que és **útil** per determinar la seva rellevància respecte a una *query* qualsevol. + La recuperació basada en termes indexats es pot implementar de manera eficient. + A més, els termes indexats són senzills de fer servir en una consulta. + La senzillesa és important perquè redueix l'esforç de formulació de consultes per part de l'usuari. --- ## Recuperació i ordenació Procés de recuperació d'informació: <center><img width="550" src="https://i.imgur.com/sBwgIoO.png"></center> --- ## Recuperació i ordenació + Un **ranking** és una ordenació dels documents que reflecteix la seva rellevància per a una consulta d'usuari. + Per tant, qualsevol sistema IR ha de fer front al problema de predir quins documents els usuaris trobaran rellevants. + Aquest problema encarna, naturalment, un grau d'incertesa o vaguetat. --- ## Conceptes bàsics + Cada document està representat per un conjunt de paraules clau o termes indexats "útils". + Un terme indexat és una paraula o grup de paraules consecutives (*word groups*) en un document. + Es pot utilitzar un conjunt preseleccionat de termes indexats per resumir el contingut del document. + No obstant això, a vegades pot ser interessant suposar que la majoria de les paraules que apareixen en un text són termes indexats (representació de text complet). --- ## Conceptes bàsics Sigui, + $t$ el nombre de termes indexats de la col·lecció de documents. + $k_i$ un terme indexat qualsevol. Llavors, + El vocabulari $V={k_1,\dots, k_t}$ és el conjunt de tots els termes indexats diferents de la col·lecció. --- ## Conceptes bàsics Els documents i les consultes es poden **representar** mitjançant patrons de co-ocurrències dels termes indexats. Aquests patrons representen quins subconjunts de termes indexats apareixen en un document: $d_i = (0,0,1,0,\dots,0,1,0)$. Cadascun d'aquests patrons de co-ocurrència de termes s'anomena **component conjuntiva de termes**. Cada document $d_j$ té associat una única component conjuntiva de termes $c(d_j)$. --- ## La matriu terme-document L'aparició d'un terme $k_i$ en un document $d_j$ estableix una relació entre $k_i$ i $d_j$. Una relació terme-document basada en $k_i$ i $d_j$ es pot quantificar per la **freqüència** del terme al document. En forma de matriu, això es pot escriure com: <center><img width="200" src="https://i.imgur.com/2n21PHU.png"></center> on cada element $f_{i,j}$ representa la freqüència del terme $k_i$ al document $d_j$. --- ## Concepte Bàsics El procés per convertir un text un conjunt de termes indexats sol tenir una sèrie de passos estàndards: eliminació s'*stopwords* (paraules molt comuns sense càrrega semàntica), agrupació de paraules en grups semàntics (*White House*), eliminació de la conjugació dels verbs, etc. <center> <img width="850" src="https://i.imgur.com/4Icl0XE.png"> </center> --- ## El Model Booleà En aquest model, les consultes es representen com a **expressions booleanes** que representen diferents components conjuntives: $$q = k_a \wedge (k_b \lor \lnot k_c)$$ Les freqüències a la matriu terme-document es representen de forma binària: + $f_{ij} \rightarrow w_{ij} \in \{0,1\}$: pes associat al parell $(k_i, d_j)$. La *query* és també binària: + $w_{iq} \in \{0,1\}$: pes associat al parell $(k_i, q)$. Una component conjuntiva de termes $d$ que satisfà una consulta $q$ s'anomena component conjuntiva de consulta $c(q)$. --- ## El Model Booleà La similitud del document $d_j$ amb la consulta $q$ es defineix com: <center> <img width="450" src="https://i.imgur.com/6iPFUJ5.png"></center> El model booleà només pot predir per cada document si és rellevant o és no rellevant. --- ## Inconvenients del model booleà + La recuperació està basada en criteris de decisió binaris, **sense noció de concordança parcial**. Per tant, no es pot proporcionar cap ordenació dels documents (absència d'*score*). + La *query* s'ha de traduir a una expressió booleana, que la majoria dels usuaris troben incòmode. Com a conseqüència, les consultes booleanes formulades pels usuaris solen ser massa simplistes. + El model sovint retorna massa pocs o massa documents en resposta a una consulta de l'usuari. --- ## Ponderació de termes La **ponderació de termes** és una alternativa senzilla al model booleà. Es basa en el fet que els termes d'un document no són igualment útils per descriure el contingut del document. + Per exemple, hi ha termes indexats que són simplement més vagues, ambigus, que d'altres. Algunes propietats estadístiques d'un terme indexat poden ser útils per avaluar la importància del terme en un document. + Per exemple, una paraula que apareix a tots els documents d'una col·lecció és completament inútil per a la recuperació. --- ## Ponderació de termes Per caracteritzar la importància d'un terme, associem un pes $w_{i,j}>0$ a cada terme $k_i$ que apareix al document $d_j$. + Si $k_i$ no apareix al document $d_j$, llavors $w_{i,j}= 0$. + $w_{i,j}$ hauria de quantificar la importància del terme índex $k_i$ per descriure el contingut del document $d_j$. Aquests pesos es poden utilitzar per calcular un *score* per a cada document de la col·lecció pel que fa a una consulta determinada. --- ## Ponderació de termes Sigui, + $k_i$ un terme indexat + $d_j$ un document + $V=\{k_1, k_2,\dots, k_t\}$ el conjunt de tots els termes indexats + $w_{i,j} \geq 0$ el pes associat a $(k_i, d_j)$. Aleshores definim $\mathbf d_j= (w_{1,j}, w_{2,j},\dots, w_{t,j})$ com un vector ponderat que conté el pes $w_{i,j}$ de cada terme $k_i \in V$ del document $d_j$. + Els pesos $w_{i,j}$ es poden calcular basant-se en les **freqüències d'ocurrència** dels termes als documents. --- ## Ponderació de termes + Definim $f_{i,j}$ com la freqüència d'ocurrència del terme índex $k_i$ al document $d_j$. + Definim la **freqüència total** d'ocurrència $F_i$ del terme $k_i$ a la col·lecció com: $$ F_i = \sum_{j=1}^N f_{i,j} $$ + Definim la **freqüència de documents**, $n_i$, d'un terme $k_i$ com el nombre de documents en què apareix. Observeu que $n_i \leq F_i$. --- ## Ponderació de termes + Per exemple, a la col·lecció de documents següent, els valors $f_{i,j}$, $F_i$ i $n_i$ associats amb el terme "do" són: <center> <img width="550" src="https://i.imgur.com/ukHP63c.png"></center> --- ## Ponderació de termes Per als models clàssics de recuperació d'informació, se suposa que els pesos dels termes de l'índex són mútuament independents. + Això vol dir que $w_{i,j}$ no ens diu res sobre $w_{k,j}$ si $i \neq k$. Això és clarament una simplificació perquè les ocurrències de termes d'índex en un document no estan descorrelacionades. + Per exemple, els termes "ordinador" i "xarxa" solen aparèixer junts en un document sobre xarxes d'ordinadors. + En aquest document, l'aparició d'un d'aquests termes atrau l'aparició de l'altre. + Per tant, estan correlacionats i els seus pesos haurien de reflectir aquesta correlació. --- ## Ponderació TF-IDF El mètode de ponderació de termes indexats TF-IDF té dues parts: + Freqüència de terme, Term frequency (TF) + Freqüència inversa de document, Inverse document frequency (IDF) Aquest és l'esquema de ponderació de termes més popular a IR. --- ## Freqüència de terme (TF) **1a assumció**: el valor de $w_{i,j}$ ha de ser proporcional a la freqüència del terme $f_{i,j}$. + És a dir, com més sovint apareix un terme al text del document, més gran és el seu pes. + Això condueix directament a la següent formulació de pes $tf$: $\mbox{tf}_{i,j} = f_{i,j}$. Una variant del pes $tf$ utilitzada a la literatura és: $$\mbox{tf}_{i,j} = (1 + \log_2 f_{i,j})$$ si $f_{i,j} > 0$ i $\mbox{tf}_{i,j} = 0$ en cas contrari. L'expressió amb el logaritme és **la forma preferida** perquè les fa directament comparables amb els pesos $idf$, tal com comentarem més endavant. --- $$(1 + \log_2 x) \mbox{ per } x>0$$ <center> <img width="350" src="https://i.imgur.com/Gg0lhYH.png"></center> --- ## Freqüència de terme (TF) $$\mbox{tf}_{i,j} = (1 + \log_2 f_{i,j})$$ <center> <img width="650" src="https://i.imgur.com/tWxmUw9.png"></center> --- ## Freqüència inversa de document **2a assumció**: el valor de $w_{i,j}$ ha de ser inversament proporcional al nombre de documents en què apareix el terme. + Si s'assignen massa termes a un document, es recuperarà mitjançant consultes per a les quals no sigui rellevant. Amb això reduim el nombre de termes tot i seleccionats els més rellevants. Això s'anomena **especificitat del terme**. --- ## Freqüència inversa de document L'especificitat del terme es pot calcular d'aquesta manera: $$\mbox{idf}_i = \log_2 \frac{N}{n_i}$$ on $N$ és el nombre de documents de la col·lecció i $n_i$ d'un terme $k_i$ és el nombre de documents en què apareix. + L'$\mbox{idf}$ d'un terme rar és alt, mentre que l'$\mbox{idf}$ d'un terme freqüent és baix. + Prenem el logaritme de tot aquest terme, perquè és possible que estiguem indexant milions de documents, i l'$\mbox{idf}$ pot resultar bastant difícil de manejar tret que ens referim en termes d'ordre de magnitud. L'$\mbox{idf}$ s'utilitza per ordenar en gairebé tots els sistemes IR. --- ## Freqüència inversa de document <center> <img width="650" src="https://i.imgur.com/0KgIYzT.png"></center> --- ## tf-idf Els esquemes de ponderació de termes més coneguts utilitzen pesos que combinen factors $idf$ amb freqüències $tf$. Sigui $w_{i,j}$ el pes del terme associat amb el terme $k_i$ i el document $d_j$. Aleshores, definim el pes com: $$ w_{i,j} = (1+\log_2 f_{i,j}) \times \log_2\frac{N}{n_i} $$ si $f_{i,j} > 0$ i $0$ en cas contrari. --- ## tf-idf El mètode $\mbox{tf-idf}$ pondera tots els termes presents a la nostra col·lecció de documents d'exemple: <center> <img width="650" src="https://i.imgur.com/g1qkD4U.png"></center> --- ## Puntuació de concordança Donada una consulta (que, atés que ara la representarem amb un $\mbox{tf-idf}$ ara pot ser una frase, un paràgraf, etc.) i un conjunt de documents, la **puntuació de concordança** és la manera més senzilla de calcular la similitud. Aquest mètode simplement suma els valors $\mbox{tf-idf}$ dels termes presents a la consulta (*query*) per a cada document. + Per exemple, per a la consulta "hola món", hem de comprovar en tots els documents si aquestes paraules existeixen i si la paraula existeix, llavors el valor $\mbox{tf-idf}$ s'afegeix a la puntuació d'aquell document. + Al final, ordenarem i agafarem els $k$ documents més ben puntuats. --- ## Normalització per la longitud del document Encara hi ha un problema en aquesta representació: les mides dels documents poden variar molt. + Això és un problema perquè és més probable que els documents més llargs siguin recuperats per una consulta determinada. + Per compensar aquest efecte no desitjat, **podem dividir l'*score* de cada document per la seva longitud**. --- ## Normalització per la longitud del document La longitud del document ve donada per la norma d'aquest vector, que es calcula de la següent manera: $$ |\mathbf d_j| = \sqrt{\sum^t_{i=1} w^2_{i,j}} $$ + Aquest procediment produeix una millor classificació i s'anomena **normalització de la longitud del document**. --- ## El model vectorial La puntuació de concordança proporciona documents rellevants, però falla bastant quan fem *queries* llargues. L'alternativa és utilitzar un **model vectorial**: + El pes $w_{i,j}$ associat a un parell $(k_i, d_j)$ és positiu i no binari. + Se suposa que els termes indexats són tots mútuament independents. + Les representacions del document $d_j$ i la consulta $q$ són vectors $t$-dimensionals donats per: $$ \mathbf d_j = (w_{1j}, w_{2j}, \dots, w_{tj}) \\ \mathbf q = (w_{1q}, w_{2q}, \dots, w_{tq}) $$ --- ## El model vectorial La similitud entre un document $\mathbf d_j$ i una consulta $\mathbf q$ es pot calcular per la distància del cosinus: $$ \cos \theta = \frac{\mathbf q \cdot \mathbf d_j}{\| \mathbf q \| \| \mathbf d_j\|} $$ Com que $\theta$ varia entre 0 i 90 graus (tots els vectors són positius), $\cos \theta$ varia entre 1 i 0. --- ## Distància del cosinus Diferència entre distància euclidiana ($d$) i dels cosinus ($\theta$): <center> <img width="450" src="https://i.imgur.com/YihAaQS.png"></center> --- ## El model vectorial + Els pesos de la *query* $\mathbf q$ i del document $\mathbf d_j$ al model vectorial són pesos $\mbox{tf-idf}$: $$ w_{i,q} = (1+\log_2 f_{i,q}) \times \log_2 \frac{N}{n_i} \\ w_{i,j} = (1+\log_2 f_{i,j}) \times \log_2\frac{N}{n_i} $$ + Aquestes equacions només s'han d'aplicar per a valors de freqüència del terme superiors a zero. + Si el terme freqüència és zero, el pes respectiu també és zero. --- ## El model vectorial Ordenació de documents calculada amb el mode vectorial per la *query* `to do`: <center> <img width="650" src="https://i.imgur.com/Pt6zTKX.png"></center> --- ## El model vectorial Avantatges: + La fórmula ordena els documents segons un grau de similitud amb la consulta. + La **normalització de la longitud del document està integrada de manera natural** a la classificació, atès que només mirem el cosinus entre els vectors, independentment de la seva magnitud. Desavantatges: + Assumeix la independència dels termes de l'índex.