hypg.tex

   1 \documentclass[a4paper,10pt,notitlepage]{article}
   2
   3 \usepackage[latin1]{inputenc}
   4 \usepackage[italian]{babel}
   5 \usepackage{fontenc}
   6 \usepackage{graphicx}
   7
   8 \author{Ivan Molineris}
   9 \date{2009-02-05}
  10
  11 \begin{document}
  12 \section{Formula base}
  13 Essendo:
  14 \begin{itemize}
  15  \item $a_k$ il $k$esimo articolo,
  16  \item $u_i$ l'$i$esimo utente,
  17  \item $A_i$ le bookmarks per l'utente $u_i$: $A_i=\lbrace a_k / a_k$ \`e taggato da $ u_i\rbrace$,
  18  \item $r_{a_k u_i}$ il valore di rank di $a_k$ per $u_i$,
  19  \item $P_\mathrm{H}\left(U, A, B\right)$ la probabilit\`a $P(x'\geq x)$ con $x=\sharp A \cap B$ considerando come indipendente la probabilit\`a che un elemento $a$ dell'universo $U$ appartenga ad $A$ or $B$ (secondo un modello ipergeometrico o un'approssimazione binomiale).
  20 \end{itemize}
  21
  22 propongo la seguente formula per calcolare $r_{a_k u_i}$:
  23
  24 \begin{equation}
  25 r_{a_ku_i}=-\sum_{u_{j\ne i}}\log\left(P_\mathrm{H}\left(A_i\cap A_j\right)\right)\delta_{a_k\in A_j}
  26 \end{equation}
  27
  28 Il significato pratico di questa formula \`e il seguente: ogni utente $u_j$ che ha nel suo set $A_j$ (bookmark) l'articolo $a_k$ contribuisce al rank di $a_k$ per $u_i$ in modo proporzionale (al log del) all'inverso della probabilit\`a che le bookmarks di $u_j$ siano indipendenti da quelle di $u_i$.
  29 \subsection{Multiple testing}
  30 Espresso in questo modo ogni utente $u_j$ con $ A_j\cap A_i \ne \O{}$ porta dell'informazione. Tuttavia, essendo il numero di utenti elevato e pari al numero di test statistici effettuati (a fissato $u_i$), pu\`o accadere che la probabilit\`a $P_\mathrm{H}\left(A_i\cap A_j\right)$ sia piccola per caso. Il modo pi\`u semplice per abbattere questo rumore che entrerebbe nella sommatoria \`e applicare la ricetta di Bonferroni che prevede di mandare a 1 la probabilit\`a quando essa supera una certa soglia pari a $N\lambda$ con $\lambda$ pari alla significativit\`a desiderata del test (es $0.5$) e $N$ pari al numero di utenti.
  31 Siccome \`e noto che questa correzione \`e eccessivamente conservativa quello che si potrebbe pi\`u proficuamente fare \`e stimare l'$N$ empirico che ottimizza i risultati.
  32
  33 \section{Formula ricorsiva}
  34 L'effetto della formula proposta pu\`o essere interpretato nel seguente modo: inizialmente l'informazione che si ha su ciascun $a_k$ a fissato $u_i$ \`e la presenza o meno di $a_k$ in $A_i$ quindi si pu\`o immaginare associato a ciascun $a_k$ un $r_{a_k u_i} = 1$ se $a_k\in A_i$, $0$ altrimenti. Calcolando $r_{a_k u_i}$ si passa da un sistema a 2 stati ad un sistema contino: ogni $a_k$, dentro e fuori $A_i$, ha possibilmente un peso diverso.
  35
  36 Supponiamo di iterare il processo, mantenendo fissi gli $A_j$; sia $r_{a_k u_i}(t)$ il rank al tempo $t$:
  37 \begin{equation}
  38 r_{a_ku_i}(t)=-\sum_{u_{j\ne i}}r_{a_k u_j}(t-1)\log\left(P_\mathrm{H}\left(A_i\cap A_j\right)\right)\delta_{a_k\in A_j}
  39 \end{equation}
  40
  41 essendo $r_{a_k u_j}(0) = 1$ se $a_k\in A_j$, 0 altrimenti.
  42
  43 Nel primo passo passiamo da un sistema a 2 stati ad un sistema continuo, nei passi successivi raffiniamo via via il rank, usando ad ogni step il rank stimato al passo precedente.
  44
  45 In formalismo matriciale si pu\`o scrivere
  46
  47 \begin{equation}
  48 \vec{r}_{u_i}(t) = M \vec{r}_{u_i}(t-1)
  49 \end{equation}
  50
  51 con $M_{\alpha\beta}=-\log\left(P_\mathrm{H}\left(A_\alpha\cap A_\beta\right)\right)$. Essendo $P_\mathrm{H}\left(A_\alpha\cap A_\beta\right) = P_\mathrm{H}\left(A_\beta\cap A_\alpha\right)$ la matrice \`e simmetrica, inoltre si ha $M_{\alpha\beta}\geq 0 ~ \forall~ \alpha,\beta$, quindi esiste un set completo di autovettori. Sia $\lambda$ l'autovalore maggiore, cerchiamo $\vec{r}_{u_i}$ tale che:
  52 $$\vec{r}_{u_i} = \lambda M \vec{r}_{u_i}$$
  53
  54 L'esistenza degli autovettori significa anche che il sistema dinamico discreto
  55 $\vec{r}_{u_i}(t) = \lambda M \vec{r}_{u_i}(t-1)$
  56 descritto sopra ha punti stazionari. Vedi wikipedia alla voce \underline{Arnoldi iteration} e \underline{Lanczos algorithm} per vedere come il processo iterativo converge agli autovettori. In analogia con PageRank, il vettore $\vec{r}_{u_i}$ ricercato \`e quello associato all'autovalore massimo (che equivale forse a quello pi\`u stabile).
  57
  58 \section{Ricorsione con matrice variabile nel tempo}
  59
  60 \subsection{Criteri per la variazione delle bookmarks}
  61
  62 Si possono introdurre dei criteri di variazione delle bookmarks $A_i(t)$ sulla base di $\vec{r}_{u_i}(t-1)$.
  63
  64 \paragraph{Criterio del massimo e minimo.}
  65 Dato il complementare delle bookmarks $\bar{A}_i=U-A_i$ supponiamo che al tempo $t$ si abbia: $$ \max_{\bar{A}_i}(r_{a_k u_i} ) > \min_{A_i}(r_{a_k u_i}) $$
  66 allora potremo decidere di scambiare l'articolo $a_k \in \bar{A}_i$ che genera il massimo rank in $\bar{A}_i$ con quello $a_l\in A_i$ che genera il minimo rank in $A_i$.
  67
  68 \paragraph{Scala tipica in $\vec{r}$.}
  69
  70 Se da una analisi teoria o empirica risultasse che i valori delle componenti del vettore $\vec{r}_i$ non si distribuiscono in modo graduale tra il massimo e il minimo ma si formano due set distinti di componenti, qualcuna con un valore nettamente maggiore di un certo valore di taglio $c$ e altre nettamente al di sotto (con poche componenti con valore attorno a $c$); allora si potrebbe usare $c$ come discriminante e assumere che gli articoli in $A_i(t)$ sono quelli con $r_{a_k u_i}(t-1)>c$.
  71 \\
  72
  73 Qualunque sia il criterio con cui $A_i$ e quindi $M$ varia nel tempo, il problema diventa
  74
  75 $$r_{a_ku_i}(t)=-\sum_{u_{j\ne i}}r_{a_k u_j}(t-1)\log\left(P_\mathrm{H}\left(A_i(t-1)\cap A_j(t-1)\right)\right)\delta_{a_k\in A_j(t-1)}$$
  76
  77 Forse in matematica questo problema \`e noto e sarebbe interessante vedere se (date le propriet\`a di $M(t)$ e della funzione $f(\vec{r}_i,M) \mapsto M'$ con cui $M$ evolve) potessimo affermare che esiste una $M$ di equilibrio e vedere quanto il vettore di rank all'equilibrio differirebbe dal caso in cui $M$ \`e tenuta costante.
  78
  79 In questa formulazione l'obbiettivo non sarebbe tanto quello di calcolare il vettore di rank all'equilibrio quanto ricavare direttamente dalla dinamica gli $A_i$ di equilibrio.
  80
  81 \section{Disambiguare sui tag.}
  82
  83 Prendiamo due utenti $u_i$ e $u_j$ supponiamo che ciascuno abbia nelle proprie bookmarks articoli che si riferiscono a due diversi ambiti di interesse. Assumiamo che gli ambiti di interesse siano caratterizzati da due tag diversi da ciascu untente. Tuttavia non facciamo affidamento sulla morfologia del tag, ovvero assumiamo che ogni utente possa utilizzare termini diversi per indicare lo stesso ambito di interesse. In tutto abbiamo 4 tag diversi (se fossero uguali morfologicamente considereremmo il fatto come accidentale e assumeremmo comunque i tag come diversi) associati a 4 ambiti di interesse; questi ultimi per\`o possono non essere diversi, anzi assumiamo che uno dei 2 ambiti di interesse di $u_i$ coincida con uno dei 2 ambiti di interesse di $u_j$.
  84 Definiamo $A_{i\tau}$ come $ A_i\supseteq A_{i\tau}=\lbrace a_k / a_k$ \`e taggato da $ u_i$ con il tag $\tau\rbrace$ e assumiamo che $A_{i\tau}$ contenga articoli tutti afferenti allo stesso ambito di interesse, eventualmente parzialmente (ma non molto) sovrapposto ad altri ambiti di interesse caratterizzati da altri tag.
  85 In questo caso \`e probabile che il numero di elementi in ciascuna intersezione $A_{i\alpha}\cap A_{i\beta}$ sia diverso: ci aspettiamo una maggiore intersezione per quella coppia di tag $\alpha\in T_{u_i}$ e $\beta \in T_{u_j}$ che caratterizzano lo stesso ambito di interesse (dove abbiamo indicato con $T_{u_i}$ l'insieme dei tag utilizzati da $u_i$).
  86 Analogamente, sulla base delle size relative dei vari $A_{i\tau}$, $P_{H}(U,A_i\cap A_j)$ potrebbe essere non significativa e contemporaneamente potrebbe esistere una coppia di tag $\alpha\in T_{u_i}$ e $\beta \in T_{u_j}$ tali che $P_{H}(U,A_{i\alpha}\cap A_{j\beta})$ sia significativa.
  87
  88 Proponiamo quindi un nuovo modo di calcolare il rank che tenga conto di queste considerazioni sui diversi ambiti di interesse $A_{i\tau}$da cui $A_i$ pu\`o essere composta:
  89 $$r_{a_ki}=-\sum_{j,\alpha\in T_{u_i},\beta\in T_{u_j}}\log\left(P_\mathrm{H}\left(A_{i\alpha}\cap A_{j\beta}\right)\right)\delta_{a_k\in A_{j\beta}}$$
  90
  91 Abbiamo qui esteso, considerando i tag, solo la formula di base, ma analoghe estensioni si possono fare per la formula ricorsiva e quella con matrice variabile nel tempo.
  92 \end{document}