From 19baba7541c3778cd25b258f5df8c0ac7477b10a Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Tue, 13 Oct 2009 23:35:56 +0200 Subject: [PATCH] Finita la lezione del 12 ottobre anche se alcune cose andrebbero precisate meglio parlando di martici cicliche. In ogni caso spero che Bini torni sull'argomento --- AppPageRank.tex | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++ CalcoloScientifico.tex | 3 +- 2 files changed, 84 insertions(+), 1 deletion(-) diff --git a/AppPageRank.tex b/AppPageRank.tex index 1133e67..5510c2c 100644 --- a/AppPageRank.tex +++ b/AppPageRank.tex @@ -70,4 +70,86 @@ La matrice di connessione $H$ associata a questo grafo è la seguente 0 & 1 & 0 \end{array} \right] \] +\begin{os} \label{os:pageranknumcoll} + \`E facile verificare che valgono le seguenti uguaglianze + \[ + \left\{ \begin{array}{ll} + \sharp \{ \text{collegamenti uscenti da} \ i \} & = \sum_{j=1}^{N} h_{ij} \\ + \sharp \{ \text{collegamente che arrivano a} \ j \} & = \sum_{i=1}^{N} h_{ij} + \end{array} \right. + \] +\end{os} +In particolare sarebbe piuttosto immediato calcolare, partendo dalla matrice $H$, i valori +del Page Rank con i metodi ipotizzati all'inizio del capitolo (per altro reputati incompleti) +Siamo dunque interessati a calcolare il vettore $W$ dove $w_i$ è l'importanza della pagina $i$, +in modo che rispetti le linee guide definite precedentemente. + +Chiamiamo $d_i$ il numero di link uscenti dalla pagina $i$ +(facilmente calcolabile come visto nell'Osservazione~\ref{os:pageranknumcoll}. Chiameremo inoltre +$D$ la matrice con i $d_i$ sulla diagonale e nulla per i restanti valori. +Introdotta questa notazione, secondo il nostro modello ogni componente di $W$ dovrebbe rispettare +la seguente equazione +\[ + w_j = \sum_{i=1}^{N} w_i \frac{h_{ij}}{d_i} +\] +che rappresenta esattamente l'idea che l'importanza di ogni pagina è la somma delle importanze di quelle +che la linkano, in cui ogni addendo è normalizzato sul numero di link uscenti\footnote{probabilmente l'equazione +è molto più chiara di questa frase, ma non commentare mi sarebbe sembrato inopportuno}. +\`E quindi chiaro come il nostro problema si sia trasformato in un problema di autovalori ed autovettori. In +particolare, se poniamo $M = D^{-1}H$ la nostra richiesta si può scrivere nella forma più compatta +$\trasp{W} = \trasp{W}M$, ovvero $\trasp{W}$ è un autovettore sinistro di $M$. Sorgono spontanee alcune +domande a cui dobbiamo rispondere prima di procedere oltre. +\begin{enumerate}[(a)] + \item \label{en:pagerank:a} Cosa succede se per qualche $i$ si ha $d_i = 0$? Stiamo tacitamente assumendo che $D$ sia invertibile + ma questo non è garantito a priori; + \item \label{en:pagerank:b} L'autovalore $1$ fa parte dello spettro delle matrice $M$? Se questo non fosse vero la nostra + richiesta non ammette soluzione, e quindi possiamo rinunciare in partenza alla nostra idea; + \item \label{en:pagerank:c} Se l'autovettore $W$ esiste, è unico? (a meno di multipli scalari, ovviamente). Se così non fosse + sorgerebbero dei seri problemi su come interpretare i risultati ottenuti; + \item \label{en:pagerank:d} Possiamo scegliere l'autovettore $W$ in modo che $w_i \geq 0$ per ogni $i$? Questo non è necessario, + a priori, ma sembrerebbe coerente fare in modo che delle votazioni siano numeri positivi; +\end{enumerate} + +Cominciamo col rispondere alla domanda~(\ref{en:pagerank:a}). Ovviamente potrebbe benissimo succedere +che per qualche $i$ $d_i = 0$. Questi ``nodi'' vengono chiamati \emph{dangling node}, ovvero ``nodi penzolanti'', +che non portano a niente. Per risolvere questo problema si sostituisce la matrice $H$ con una matrice $\hat H$ +tale che se $h_ij = 0 \: \forall j$ allora $\hat h_{ij} = 1 \: \forall j$, e in caso contrario $h_{ij} = \hat h_{ij}$. +Questa matrice risolve evidentemente il problema e cambia di poco il modello. Supporre che una determinata pagina +non distribuisca la sua importanza a nessuno o la distribuisca in maniera analoga a tutti non è un gran cambiamento. + +La domanda~(\ref{en:pagerank:b}) ha invece una risposta immediata. Sì, l'autovalore $1$ fa parte dello spettro +ed un autovettore (destro) a lui associato è quello composto di tutti $1$. La verifica è un banale conto. + +Per rispondere alle domande~(\ref{en:pagerank:c}) e (\ref{en:pagerank:d}) ci appoggiamo ad un risultato +che non dimostreremo (in questa sede) ottenuto da Perron-Frobenius sulla Teoria delle Matrici non negative. +\begin{te}[di Perron-Frobenius] \label{te:PerronFrobenius} + Se $A$ è irriducibile allora $\rs{A} > 0$ è un autovalore semplice e esistono $x,y$ autovettori destro e sinistro + con componenti strettamente positive. +\end{te} +\begin{os} + Sembrerebbe, a priori, che non siamo in grado di determinare il raggio spettrale di $A$. Consideriamo però + che $1$ è nell spettro e che $||A||_{\infty} = 1$ e ogni norma indotta supera il raggio spettrale. Si può + quindi concludere che $\rs{A} = 1$ e quindi possiamo applicare il Teorema~\ref{te:PerronFrobenius}. +\end{os} +Sfortunatamente si può osservare che, pur con tutte queste buone proprietà, in generale i metodi applicati +per trovare l'autovettore (il metodo delle potenze) potrebbe non essere convergente, perché gli autovalori +diversi da $1$ potrebbero ancora avere modulo $1$\footnote{Come visto nella teoria, la velocità di convergenza +del metodo di iterazione è data dal rapporto fra il più grande autovalore diverso da quello di cui si sta cercando +l'autovettore e l'autovalore in questione. In questo caso il rapporto potrebbe essere $1$, che darebbe una situazione +di non convergenza}. +Per superare questo problema si può, ancora una volta, modificare il modello. Consideriamo che il visitatore +possa in ogni pagina, con probabilità $1-\gamma$, decidere di aprire una pagina a caso. Potremmo rappresentare +questa nuova situazione sostituendo $M$ con la matrice +\[ + A = \gamma M + (1-\gamma) \left[ \begin{array}{c} + 1 \\ + \vdots \\ + 1 + \end{array} \right] \left[ 1 \: \hdots \: 1 \right] +\] +%% TODO: Spiegare meglio la condizione di ciclicità +ovvero con una combinazione convessa della matrice $M$ con la matrice di soli $1$. Il valore di $\gamma$ si può +scegliere a piacimento; Google usa un valore $\gamma = 0.85$. In questo caso la matrice $A$ non ha elementi nulli +e quindi è irriducibile e non è ciclica\footnote{La condizione di ciclicità è quella che crea problemi +con gli autovalori di modulo uguale al raggio spettrale}. \ No newline at end of file diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index d99a093..4fc8ec0 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -62,6 +62,7 @@ %% \newcommand{\cond}[1]{\mathcal{K}(#1)} \newcommand{\spe}[1]{Sp(#1)} +\newcommand{\rs}[1]{\rho(#1)} %% @@ -139,7 +140,7 @@ %% Rinnoviamo il comando section mark tentando di mantere i caratteri minuscoli %% per il nome della sezione. -\renewcommand{\chaptermark}[1]{ \markboth{Capitolo~\thechapter\ -- #1}{} } +\renewcommand{\chaptermark}[1]{ \markboth{\thechapter\ -- #1}{} } %% Resettiamo qualsiasi header presente \fancyhf{} -- 2.1.4