Calcolo pagerank: dubbi

[ginog81]

Ciao, avrei qualche dubbio per quanto riguarda il pagerank.

1) Da quello che ho capito i valori calcolati con questa formula

cambiano ad ogni iterazione ma quello che non ho capito è il perchè. Probabilmente perchè si tratta di un algoritmo iterativo che, partendo da un punteggio iniziale di 1/n, ad ogni passo ricalcola il punteggio fermandosi in corrispondenza di un criterio di "stop" (il punteggio cercato è rappresentato dal valore finale)?

2) Su ogni colonna della matrice (3) la somma degli elementi vale 1:

E' vero solo in questo esempio o questo vale in generale? Se è vero in generale, questo può valere anche per le righe?

[ginog81]

nessuno mi sa aiutare?

[hamming_burst]

"ginog81":Ciao, avrei qualche dubbio per quanto riguarda il pagerank.

1) Da quello che ho capito i valori calcolati con questa formula

cambiano ad ogni iterazione ma quello che non ho capito è il perchè. Probabilmente perchè si tratta di un algoritmo iterativo che, partendo da un punteggio iniziale di 1/n, ad ogni passo ricalcola il punteggio fermandosi in corrispondenza di un criterio di "stop" (il punteggio cercato è rappresentato dal valore finale)?

mi domando, conosci la teoria che sta sopra a quella formula?
secondo te cosa è quel criterio di "stop"?

PS: "punteggio" è un po' inguardabile...non so chi ha scritto quelle note, ma è meglio utilizzare "rank".

2) Su ogni colonna della matrice (3) la somma degli elementi vale 1:

E' vero solo in questo esempio o questo vale in generale? Se è vero in generale, questo può valere anche per le righe?

mmm non mi convice quella matrice, secondo me è già stata calcolata in modo da poterla usare nell'esercizio.
Spero tu sappia essere una matrice stocastica, per righe o per colonne deve aver somma $1$ (per definizione), entrambe non è detto nel PageRank, è solo un caso se capita.
Da quello che ricordo la matrice $A$ è una matrice stocastica per righe, e nel calcolo è una matrice stocastica per colonne (sai perchè?).

[ginog81]

"hamming_burst":
mi domando, conosci la teoria che sta sopra a quella formula?
secondo te cosa è quel criterio di "stop"?

PS: "punteggio" è un po' inguardabile...non so chi ha scritto quelle note, ma è meglio utilizzare "rank".

secondo me quel criterio di "stop" potrebbe coincidere con il "rank" migliore ottenuto dopo una serie di passi iterativi fatti su quella formula. ma potrei tranquillamente sbagliarmi.

"hamming_burst":
mmm non mi convice quella matrice, secondo me è già stata calcolata in modo da poterla usare nell'esercizio.
Spero tu sappia essere una matrice stocastica, per righe o per colonne deve aver somma $1$ (per definizione), entrambe non è detto nel PageRank, è solo un caso se capita.
Da quello che ricordo la matrice $A$ è una matrice stocastica per righe, e nel calcolo è una matrice stocastica per colonne (sai perchè?).

Quindi da quello che ho capito quella matrice $A$ è una matrice creata apposta per l'esercizio. In generale però non è detto che nel PageRank la matrice ottenuta abbia la somma delle righe e/o delle colonne pari a 1. E' corretto?
In ogni caso vedrò di comprendere meglio la teoria che c'è sulle matrici stocastiche.

[hamming_burst]

"ginog81":secondo me quel criterio di "stop" potrebbe coincidere con il "rank" migliore ottenuto dopo una serie di passi iterativi fatti su quella formula. ma potrei tranquillamente sbagliarmi.

ok su questo siam d'accordo. Dopo un certo numero di iterazioni si trova un valore migliore rispetto all'iterazione precedente.
Quel valore (autovalore massimo) corrisponde all'autovettore principale o dominante. L'esistenza di questo valore è il fulcro di tutto l'algoritmo di PageRank, se non si capisce cosa sia e come ci si arriva, si può chiuder baracca
il resto è solo contorno.
L'iterazione dell'algoritmo e lo "stop" è un'implicazione del metodo utilizzato.

Ci son almeno tre teorie principalmente che si basan sull'algoritmo di PageRank:
- autovalori, autovettori (se vuoi anche decomposizione spettrale)
- metodo delle potenze
- matrici stocastiche e catene di Markov

non serve comprender a pieno tutto, basta anche una sfarinatura per capire cosa sia il "rank" e perchè l'algoritmo si ferma dopo qualche iterazione, o meglio perchè il metodo delle potenze converge all'autovettore dominante.
Se conosci questi argomenti, cosa non ti è chiaro dell'algoritmo, non comprendi perchè l'algoritmo calcola il rank migliore?

Quindi da quello che ho capito quella matrice $A$ è una matrice creata apposta per l'esercizio. In generale però non è detto che nel PageRank la matrice ottenuta abbia la somma delle righe e/o delle colonne pari a 1. E' corretto?

Forse ho scritto male, chiedo venia.
Una matrice stocastica ha per definizione gli elementi sommati per righe oppure per colonne uguali ad $1$.
Se per righe che per colonne hanno sempre somma uno, è una proprietà in più ma non cambia l'algoritmo. Al massimo cambia il grafo associato alla matrice originale.
Il punto principale da tener in considerazione è che la matrice $A$ si deve considerare per colonne nel calcolo del ranking, quella dell'esercizio è semplicemente già stata messa a posto.
Di solito si mette per righe la matrice $A$ (perciò la somma sara $1$ per righe), poi nel calcolo si fa la trasposta e diventa per colonne (e diventa stocastica per colonne). E' semplice convenzione, nulla di più.

In ogni caso vedrò di comprendere meglio la teoria che c'è sulle matrici stocastiche.

non tanto le matrici stocastiche che è una banale definizione, ma ciò le teorie che ci stan sotto, le catene di Markov...(perciò matrici stocastiche irriducibili ed aperiodiche, se non hanno questa proprietà la convergenza del metodo non è garantita per nulla, mi pare che non funziona nemmeno, dovrei rivedere).

[ginog81]

cercherò di comprendere a pieno quegli argomenti.
grazie 1000 per la chiarezza e la disponibilità.

[hamming_burst]

"ginog81":cercherò di comprendere a pieno quegli argomenti.
grazie 1000 per la chiarezza e la disponibilità.

di nulla
se avrai dubbi, scrivili pure qui sul forum