<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>
# Information Retrieval II
## Taller Nous Usos de la Informàtica
<center><img width="150" src="https://i.imgur.com/vvZMy0I.png"></center>
---
## Indexing
---
## Basic Concepts
+ **Inverted index**: a word-oriented mechanism for indexing a text collection to speed up the searching task.
+ The inverted index structure is composed of two elements: the **vocabulary** and the **occurrences**.
+ The vocabulary is the set of all different words in the text.
+ For each word in the vocabulary the index stores the documents which contain that word (inverted index).
---
## Basic Concepts
The term-document matrix is the simplest way to represent the documents that contain each word of the vocabulary.
<center>
<img width="650" src="https://i.imgur.com/JGBGTOa.png"></center>
---
## Basic Concepts
The main problem of this simple solution is that it requires too much space.
As this is a sparse matrix, the solution is to associate a list of lists of documents with each word. The list `[[1,4],[2,2]]` represents a word that occurs 4 times in document 1 and 2 times in document 2.
---
## Basic Index
Basic inverted index:
<center>
<img width="650" src="https://i.imgur.com/DvwB2aH.png"></center>
---
## Full Inverted Indexes
The basic index is not suitable for answering phrase or **proximity queries**.
Hence, we need to add the positions of each word in each document (**occurrence list**) to the index (full inverted index).
<center>
<img width="750" src="https://i.imgur.com/65Z3c24.png"></center>
---
## Full Inverted Indexes
In the case of multiple documents, we need to store one occurrence list per term-document pair.
<center>
<img width="650" src="https://i.imgur.com/fywgBMt.png"></center>
---
## Full Inverted Indexes
The space required for the vocabulary is rather small.
+ (Empirical) **Heaps’ law**: the vocabulary grows as $O(n^\beta)$, where $n$ is the collection size (in bytes), $\beta$ is a collection-dependent constant between 0.4 and 0.6.
+ For instance, in 1GB text collection, the vocabulary occupies only 5 megabytes.
+ This may be further reduced by stemming and other normalization techniques.
---
## Full Inverted Indexes
The occurrences demand much more space.
+ The extra space will be $O(n)$ and is around 40% of the text size if stop words are omitted. 80% when stopwords are indexed.
---
## Full Inverted Indexes
To reduce space requirements, a technique called **block addressing** is used.
+ The documents are divided into blocks, and theo ccurrences point to the blocks where the word appears.
<center><img width="650" src="https://i.imgur.com/ikeCaOr.png"></center>
---
## Single word queries
The simplest type of search is that for the occurrences of a single word.
+ The vocabulary search can be carried out using any suitable data structure, ex: hashing.
+ Hashing provides $O(m)$ search cost, where $m$ is the length of the query.
+ We note that the vocabulary is in most cases sufficiently small so as to stay in main memory. The occurrence lists, on the other hand, are usually fetched from disk.
---
## Multiple word queries
If the query has more than one word, we have to consider two cases: conjunctive (**AND operator**) queries and disjunctive (**OR operator**) queries.
+ Conjunctive queries imply to search for all the words in the query, obtaining one inverted list for each word.
+ Following, we have to intersect all the inverted lists to obtain the documents that contain all these words.
+ For disjunctive queries the lists must be merged.
+ The first case is popular in the Web due to the size of the document collection and because the most time-demanding operation on inverted indexes is the merging of the lists of occurrences.
---
## Phrase and Proximity Queries
Context queries are more difficult to solve with inverted indexes.
+ The lists of all elements must be traversed to find places where all the words appear in sequence (for a phrase), or appear close enough (for proximity).
+ These algorithms are similar to a list intersection algorithm.
---
## Ranking
How to find the top-$k$ documents and return them to the user when we have inverted lists?
+ The index may have frequencies, or weights.
+ In all these cases, we can pre-sort and store the lists by weights.
+ If we have a single word query, the answer is trivial as the list can be already sorted by the desired ranking.
+ For other queries, we need to merge the lists.
---
## PageRank
---
## PageRank
L'algorisme **PageRank** és l'algorisme que va servir a Google per col·locar-se en la posició dominant que té entre els buscadors.
+ **PageRank** realitza una mesura objectiva de la importància de les pgines web mitjanant la resolució d’una equació amb centernars de milions de variables i milers de milions de termes.
+ **PageRank** interpreta un enllaç de la pàgina A a la B com a un vot que la pàgina A dóna a la pàgina B.
+ **PageRank** assigna una importància a cada pàgina segons el nombre de vots ponderats que rep. La ponderació depèn d’una anàlisi global de la distribució de vots a la web.
---
## PageRank
L’algorisme **PageRank**, inventat pels fundadors de Google, calcula un *score* per cada pàgina indicant la seva *importància*.
L'importància d'una pàgina es calcula a partir de la importància de les pàgines que l’apunten i del nombre total de links que surten d’elles.
+ Els *out-links* de la pàgina $i$ són els *hyperlinks* que apunten des de la pàgina $i$ a una altra pàgina.
+ Els *in-links* de la pàgina $i$ són els *hyperlinks* que apunten des d’altres pàgines a la pàgina $i$.
---
## PageRank
+ Un *hyperlink* d’una pàgina apuntant a una altra pàgina s’entén com una concessió implícita d’autoritat a la pàgina receptora.
+ Com més *in-links* té una pàgina $i$, més prestigi té la pàgina $i$.
+ Les pàgines que apunten a la pàgina $i$ també tenen el seu prestigi.
+ Una pàgina amb prestigi alt apuntant a $i$ és més important que una pàgina amb un prestigi menor apuntant a $i$.
En altres paraules, **una pàgina és important si és apuntada per pàgines importants**.
---
## PageRank
+ La concessió implícita d’autoritat, que s’ha de calcular ”recursivament”, determina un **PageRank Score** per cada pàgina.
+ Segons el model d’ordenació per prestigi en xarxes, la importància d’una pàgina $i$ (o PageRank Score) està determinat per la suma dels PageRank Scores de les pàgines que apunten a $i$.
+ Com que una pàgina pot apuntar a moltes altres pàgines, el seu prestigi s’ha de compartir entre les pàgines a les que apunta.
---
## PageRank
Per formalitzar les idees de PageRank, considerem la web com un graf dirigit $G= (V,E)$, on $V$ és el conjunt de $n$ nodes (o sigui, el conjunt de pàgines web) i $E$ el conjunt d’arcs dirigits (o sigui, els *hyperlinks*).
<center>
<img width="350" src="https://i.imgur.com/3aCp0g7.png"></center>
---
## PageRank
Sigui $n=|V|$ el nombre total de pàgines web.
El PageRank Score de la pàgina $i$ es defineix com:
$$
P(i) = \sum_{(j,i) \in E} \frac{P(j)}{O_j}
$$
on $O(j)$ és el nombre de *out-links* de la pàgina $j$.
Matemàticament, això és un sistema de $n$ equacions lineals amb $n$ incògnites.
---
## PageRank
Podem usar una matriu per representar les equacions:
+ Sigui $p$ un vector columna $n$ dimensional de PageRank Scores,
$$
P = (P(1), P(2), \dots, P(n))^\mathrm{T}
$$
+ Sigui $A$ la matriu d'adjacència del graf:
$$
A_{ij} = \left\{ \begin{array}{rr} \frac{1}{O_i} & \mbox{ si } (i,j)\in E
\\
0 & \mbox{altrament} \end{array}\right.
$$
+ Llavors podem escriure el sistema de $n$ equacions com ${\bf
P} = {\bf A}^\mathrm{T} {\bf P}$.
---
## PageRank
La matriu ${\bf A}$ té un parell de característiques importants:
+ Totes les seves entrades són no negatives: $A_{ij} \geq 0$.
+ La suma de les entrades d'una fila són 1 excepte en el
cas que la pàgina corresponent a aquella fila no contingui cap
link: $\sum_j A_{ij} = 1$.
El vector ${\bf P}$ s'anomena el *vector estacionari* d'${\bf A}$ i correspon a l'eigenvector d'${\bf A}$ amb eigenvalor 1.
---
## PageRank: Exemple
<center>
<img width="550" src="https://i.imgur.com/gviudJg.png"></center>
---
## PageRank: Exemple
La matriu és:
$$
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 1/3 & 0 \\
1/2 & 0 & 1/2 & 1/3 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1/2 & 1/3 & 0 & 0 & 1/3 & 0 \\
0 & 0 & 0 & 1/3 & 1/3 & 0 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 1/3 & 0 & 0 & 1/2 \\
0 & 0 & 0 & 0 & 1/3 & 1 & 1/3 & 0 \\
\end{bmatrix}
$$
El vector de probabilitats estacionàries és:
$$(0.06, 0.0675, 0.03,0.0675, 0.0975, 0.02025, 0.18,0.295)$$
---
## PageRank: Exemple
<center>
<img width="550" src="https://i.imgur.com/Jo3yLVY.png"></center>
---
## PageRank: Exemple
<center>
<img width="550" src="https://i.imgur.com/dfg3a5S.png"></center>
---
## PageRank: L'algorisme
Aquesta formulació es pot interpretar amb el model conegut com el *random surfer*: un usuari que navega seguint links de forma aleatòria i ininterrompuda per la web té una probabilitat estacionària $P(i)$ d'estar en un determinat moment a la pàgina $i$.
Com podem calcular la distribució $P(i)$?
+ Cal tenir en compte que la matriu ${\bf A}$ té milers de milions de files i columnes, però és *sparse* atès que les pàgines web tenen una mitja de 10 links de sortida.
+ Per aquest tipus de matrius és adequat usar un mètode iteratiu de càlcul del vector estacionari conegut amb el nom del **mètode de la potència**.
---
## PageRank: L'algorisme
El vector $P(i,0)$ es pot inicialitzar de diverses maneres.
+ Per l'exemple anterior, si inicialitzem amb $P(1,0)=1$ i la resta a 0, les iteracions donarien:
$$
\begin{matrix}
P(i,1)= & (1 & 0 & 0 & 0 & 0.0278 & ... & 0.06 & 0.06) \\
P(i,2)= & (0 & 0.5 & 0.25 & 0.1667 & 0.0833 & ... & 0.0675 & 0.0675) \\
P(i,3)= & (0 & 0.5 & 0 & 0 & 0 & ... & 0.03 & 0.03) \\
P(i,4)= & (0 & 0 & 0.5 & 0.25 & 0.1667 & ... & 0.0675 & 0.0675) \\
P(i,5)= & (0 & 0 & 0.25 & 0.1667 & 0.1111 & ... & 0.0975 & 0.0975) \\
P(i,6)= & (0 & 0 & 0 & 0.25 & 0.1806 & ... & 0.2025 & 0.2025) \\
P(i,7)= & (0 & 0 & 0 & 0.0833 & 0.0972 & ... & 0.18 & 0.18) \\
P(i,8)= & (0 & 0 & 0 & 0.0833 & 0.3333 & ... & 0.295 & 0.295) \\
\end{matrix}
$$
---
## PageRank: L'algorisme
Considerant la forma de resoldre el problema, ens podem fer dues preguntes rellevants:
+ Convergeix sempre l'algorisme?
+ És independent la solució final dels valors inicials?
I la resposta a les dues preguntes és "no", tot i que una petita modificació de l'algorisme les fa positives.
---
## PageRank: L'algorisme
La xarxa formada per dos nodes i un únic link ús un exemple simple on no funciona.
En aquest cas l'algorisme convergeix al vector $(0,0)$, que no té sentit.
<center>
<img width="150" src="https://i.imgur.com/v1dzBKE.png"></center>
El problema ve causat per l'existència de nodes sense links.
---
## PageRank: L'algorisme
En aquest altre cas l'algorisme tampoc no convergeix i va
generant una seqüència infinita: $(1,0,0,0,0)$, $(0,1,0,0,0)$, $(0,0,1,0,0)$, $(0,0,0,1,0)$,$(0,0,0,0,1)$, $(1,0,0,0,0)$, $...$, que no té sentit.
<center>
<img width="250" src="https://i.imgur.com/HE4SZCD.png"></center>
El problema és que el segon eigenvector d'aquesta matriu és $\geq 1.0$ i sota aquestes condicions el mètode la potència no funciona.
---
## PageRank: L'algorisme
En aquest altre cas l'algorisme convergeix al vector $(0,0,0,0,0.12,0.24,0.24,0.4)$, que no té sentit.
<center>
<img width="350" src="https://i.imgur.com/nLkXR8G.png"></center>
El problema ve causat per l'existència d'un grup de nodes sense links de sortida.
---
## PageRank: L'algorisme
Matemàticament, podem assegurar l'existència d'un vector propi estacionari amb eigenvalor 1 si la matriu és *estocàstica* i *primitiva*.
+ Una matriu no negativa ${\mathbf A}$ tal que la suma de les entrades d'una columna és 1 s'anomena **matriu estocàstica**.
+ Una matriu ${\bf A}$ és **primitiva** si per algun $m$, ${\mathbf A}^m$ té totes les seves entrades positives. En altres paraules, si donades dues pàgines qualsevol, és possible arribar d'una pàgina a l'altre després de seguir $m$ enllaços.
---
## PageRank: L'algorisme
El model que hem proposat per l'algorisme es pot modificar si considerem:
+ que l'usuari, amb una probabilitat $1-d$, pot decidir no seguir cap link de la pàgina on està i seleccionar la següent pàgina de forma aleatòria d'entre les $N$ possibles,
+ que quan arribem a una pàgina sense *out-links*, saltem a la següent pàgina de forma aleatòria d'entre les $N$ possibles.
---
## PageRank: L'algorisme
+ Llavors la probabilitat de visitar una pàgina depèn tant de la probabilitat d'arribar-hi aleatòriament com de la d'arribar-hi
pels links:
$$
P(i) = \frac{1-d}{N} + d \sum_{(j,i) \in E} \frac{P(j)}{O_j}
$$
+ Amb aquesta petita modificació es pot demostrar que l'algorisme convergeix sempre a la solució desitjada atès que tenim una matriu estocàstica i primitiva.
---
## PageRank: L'algorisme
La probabilitat $d$ s’ha estimat experimentalment en el cas de la Web i s’ha fixat a $d= 0.85$.
<center>
http://infolab.stanford.edu/pub/papers/google.pdf
</center>
---
## PageRank: L'algorisme
<center>
<img width="550" src="https://i.imgur.com/bVJ6bGq.png"></center>
---
## Altres aplicacions
Aquest algorisme es pot fer servir per avaluar la importància de les publicacions científiques a partir de les seves cites, dels programes de doctorat universitaris a partir de la col·locació dels seus estudiants, etc.
---
## Altres aplicacions
O per la cerca d'imatges...
La idea és calcular una mesura de semblança entre imatges i llavors calcular un ordre entre elles.
+ Suposem que tenim un mètode que posa punts en correspondència entre dues imatges:
<center>
<img width="350" src="https://i.imgur.com/VBU4UCY.png"></center>
+ Amb això podem crear un graf de veinatge entre imatges (connectar cada imatge a les que tenen més de $k$ punts en comú amb ella) i aplicar el mètode PageRank.
---
## Altres aplicacions
<center>
<img width="350" src="https://i.imgur.com/szfaLH1.jpg"></center>
---
## Altres aplicacions
<center>
<img width="500" src="https://i.imgur.com/Y9NuLJR.jpg"></center>
---
## Altres aplicacions
Si volem diversitat, podem triar nodes amb *scoring* alt però allunyats en el graf.
<center>
<img width="550" src="https://i.imgur.com/3CbFFKx.jpg"></center>
{"metaMigratedAt":"2023-06-16T15:21:19.302Z","metaMigratedFrom":"YAML","title":"10 Information Retrieval II","breaks":true,"slideOptions":"{\"theme\":\"white\",\"transition\":\"fade\"}","contributors":"[{\"id\":\"27c1cf26-ef2c-44cb-8ae1-2edc488d3f8e\",\"add\":15233,\"del\":394}]","description":"Inverted index: a word-oriented mechanism for indexing a text collection to speed up the searching task."}