34 Markov: Ağırlıklı Yürüyüş ve Google PageRank

Power iteration + ışınlanma; olasılığın milyar dolarlık fikri

Bölüm bilgisi

Blitzstein’in videosu: YouTube — Lecture 33 (≈48 dk)
Okuma süresi: ≈23 dk

34.1 Bu Derste Ne Var?

Ağırlıklı rassal yürüyüş: $q_{ij} = w_{ij}/\sum_k w_{ik}$, $w_{ij} = w_{ji}$.
Her tersinir zincir ağırlıklı ağ yürüyüşüdür.
PageRank: $s = sQ$, web önem skoru.
Google zinciri: $G = \alpha Q + (1-\alpha) J/M$.
Power iteration: $tG^n \to s$.

Builder Notu — ML Köprüleri

PageRank → eigenfactor, eigenvector centrality, öneri sistemleri.
Power iteration → büyük-ölçek özvektör, spektral kümeleme.
Işınlanma → düzenlileştirme (label smoothing, $\epsilon$-greedy).
Ağırlıklı graf → spektral, GNN, attention-weighted komşu.
DeepWalk / node2vec → rassal yürüyüş gömme.

34.2 Ağırlıklı Rassal Yürüyüş

Yönsüz, $w_{ij} = w_{ji}$:

\[ q_{ij} = \frac{w_{ij}}{\sum_k w_{ik}} \]

Detailed balance kontrolü → durağan ağırlık-toplamıyla orantılı:

\[ s_i \propto \sum_k w_{ik} \]

34.3 Her Tersinir Zincir = Ağırlıklı Yürüyüş

Teorem: Tersinir zincir → $w_{ij} = s_i q_{ij}$ koy. Tersinirlik ($s_i q_{ij} = s_j q_{ji}$) → $w_{ij} = w_{ji}$ (simetrik). Geçişi hesapla:

\[ \frac{w_{ij}}{\sum_k w_{ik}} = \frac{s_i q_{ij}}{s_i \sum_k q_{ik}} = q_{ij} \]

34.4 PageRank Markov Zinciri

İçgörü: Sayfa önemi = bağlantı verenlerin öneminden doğar (sabit nokta).

\[ s_j = \sum_i s_i q_{ij} \;\Rightarrow\; s = sQ \]

Seyreltme: $q_{ij} = 1/(\text{çıkış sayısı})$. Sarkan sayfa: $1/M$ tüm sayfalara.

“The importance of a page is the long-run fraction of time that you spend at that page, randomly surfing the web.” — Blitzstein, 31:34

34.5 Google Zinciri ve Işınlanma

\[ \boxed{G = \alpha Q + (1 - \alpha)\frac{J}{M}}, \quad \alpha = 0{,}85 \]

%85 bağlantı takip + %15 rastgele sayfaya ışınlan.

Neden ışınlanma?

İndirgenemezlik garantisi.
Aperiyodiklik / sıfırsızlık → durağan teoremleri uygulanır (tersinir olmasa bile).

Builder Notu — Düzenlileştirme

Işınlanma = düzenlileştirme: ana modele küçük düzgün bileşen karıştırmak. Aynı kalıp: label smoothing, $\epsilon$-greedy (RL), Laplace düzeltmesi, dropout. Patolojileri eler.

34.6 Power Iteration

\[ t, tG, tG^2, \ldots, tG^n \to s \]

Neden ucuz?

$Q$ çok seyrek (tipik sayfa az bağlantı).
$tJ$ = hepsi-1 vektörü (toplamı 1).

Her adım $O(\text{kenar sayısı})$ — milyarlarca sayfada uygulanabilir.

import numpy as np
import matplotlib.pyplot as plt

L = np.array([
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0],  # sarkan
], dtype=float)

M = L.shape[0]
out = L.sum(axis=1)
for i in range(M):
    if out[i] == 0:
        L[i] = 1.0 / M
    else:
        L[i] = L[i] / out[i]
Q = L
alpha = 0.85
G = alpha * Q + (1 - alpha) * np.ones((M, M)) / M

# Power iteration
t = np.ones(M) / M
history = [t.copy()]
for _ in range(40):
    t = t @ G
    history.append(t.copy())
history = np.array(history)

# Özvektör (kontrol)
vals, vecs = np.linalg.eig(G.T)
pi = np.real(vecs[:, np.argmin(np.abs(vals - 1))])
pi = pi / pi.sum()

fig, ax = plt.subplots(figsize=(11, 5))
renkler = ['#A51C30', '#DD6B20', '#2C5282', '#6B46C1']
for k, c in enumerate(renkler):
    ax.plot(history[:, k], color=c, linewidth=2.2, label=f'Sayfa {k+1}')
    ax.axhline(pi[k], color=c, linestyle=':', linewidth=1.5, alpha=0.6)

ax.set_xlabel('iterasyon n', fontsize=12)
ax.set_ylabel('PageRank skoru', fontsize=12)
ax.set_title(f'PageRank power iteration → {np.round(pi, 3)}', fontsize=12)
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print(f"\nFinal sıralama (yüksek→düşük): {np.argsort(-pi) + 1}")

Şekil 34.1

Builder Notu — Spektral Yöntemler

Power iteration = en büyük özdeğerin özvektörünü bulmanın standart yöntemi. Spektral kümeleme, latent faktör çıkarımı, hatta bazı verimli attention yaklaşımları (linear attention) aynı desen. “Devasa ama seyrek operatörün baskın özvektörü, operatörü tekrar tekrar uygulayarak” — büyük-ölçek ML’in her yerinde.

34.7 Bu Dersin Özeti

Ağırlıklı yürüyüş: $s_i \propto \sum w_{ik}$.
Her tersinir = ağırlıklı ağ yürüyüşü ($w_{ij} = s_i q_{ij}$).
PageRank: $s = sQ$.
Google: $G = \alpha Q + (1-\alpha) J/M$.
Power iteration + seyreklik.

Tek bir cümle

Her tersinir Markov zinciri ağırlıklı ağ yürüyüşüdür (durağan ∝ ağırlık-derece); PageRank ise tersinir-olmayan dev zincir — web sayfalarını ışınlanmayla sağlamlaştırılmış Google zincirinin durağan dağılımını power iteration ile sıralar. Önem = uzun vadede o sayfada geçirilen zaman.

34.8 Kontrol Soruları

Soru 1: Her tersinir → ağ yürüyüşü ispatı?

Cevap: $w_{ij} = s_i q_{ij}$. Tersinirlik → $w_{ij} = w_{ji}$. Geçiş: $w_{ij}/\sum w_{ik} = q_{ij}$ ($s_i$ sadeleşir).

Soru 2: Seyreltme + sarkan sayfa?

Cevap: $q_{ij} = 1/$çıkış sayısı. Sarkan → $1/M$ tüm sayfalara → satır toplamı 1.

Soru 3: Işınlanma niye?

Cevap: İndirgenemezlik + sıfırsız → durağan teoremleri uygulanır.

Soru 4: Neden power iteration?

Cevap: $O(m^3)$ imkânsız. $tG^n \to s$ ve seyreklik + $tJ$ = hepsi-1 → her adım ucuz.

34.9 Egzersizler

Egzersiz 1. Üçgen, $w_{12}=1, w_{13}=2, w_{23}=3$. Durağan?

Egzersiz 2. Detailed balance kontrolü.

Egzersiz 3. Küçük web: 1→2,3; 2→3; 3→1. $Q$ matrisi.

Egzersiz 4. Egzersiz 3’te $\alpha = 0{,}85$ ile $G_{11}$?

Egzersiz 5. (Python — PageRank)

import numpy as np

L = np.array([[0,1,1,0],[1,0,1,0],[0,0,0,1],[0,0,0,0]], dtype=float)
M = L.shape[0]
out = L.sum(axis=1)
for i in range(M):
    L[i] = L[i] / out[i] if out[i] > 0 else 1/M
Q = L
alpha = 0.85
G = alpha * Q + (1 - alpha) * np.ones((M, M)) / M

t = np.ones(M) / M
for _ in range(100):
    t = t @ G
print(f"PageRank: {np.round(t, 4)}")
print(f"Sıralama: {np.argsort(-t) + 1}")

34.10 Sonraki Ders İçin Hazırlık

Ders 34: İleriye Bakış — kursun son dersi! Top Ten + ötesi.

Ders 34 öncesi yapılacak

Tüm kursu gözden geçir.
Markov + PageRank’i içselleştir.

34.11 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Not
Ağırlıklı yürüyüş	$q = w/\sum w$	Simetrik
Durağan	$s_i \propto \sum w$	Ağırlık-derece
Tersinir = ağ	$w_{ij} = s_i q_{ij}$	Hepsi
PageRank	$s = sQ$	Önem
Seyreltme	$1/$çıkış	Sarkan: $1/M$
Google	$G = \alpha Q + (1-\alpha) J/M$	$\alpha = 0.85$
Işınlanma	Düzenlileştirme	Patoloji eler
Power iteration	$tG^n$	Seyrek + $tJ$ ucuz

34.12 ML Bağlantıları Özeti

6 köprü

PageRank → eigenfactor, eigenvector centrality.
Power iteration → spektral kümeleme.
Işınlanma → label smoothing, $\epsilon$-greedy.
Ağırlıklı graf → GNN, attention.
Tersinirlik → MCMC spektral analiz.
Random walk gömme → DeepWalk, node2vec.

Tek bir şey alıp gideceksen

Her tersinir zincir = ağırlıklı ağ yürüyüşü. PageRank = devasa Markov zincirinin durağan dağılımı + power iteration. Olasılığın milyar dolarlık fikri.

--- title: "Markov: Ağırlıklı Yürüyüş ve Google PageRank" subtitle: "Power iteration + ışınlanma; olasılığın milyar dolarlık fikri" --- ::: {.callout-note title="Bölüm bilgisi"} - **Blitzstein'in videosu:** [YouTube — Lecture 33](https://www.youtube.com/watch?v=Q-pCzTpwPBU) (≈48 dk) - **Okuma süresi:** ≈23 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} 1. **Ağırlıklı rassal yürüyüş:** $q_{ij} = w_{ij}/\sum_k w_{ik}$, $w_{ij} = w_{ji}$. 2. **Her tersinir zincir** ağırlıklı ağ yürüyüşüdür. 3. **PageRank:** $s = sQ$, web önem skoru. 4. **Google zinciri:** $G = \alpha Q + (1-\alpha) J/M$. 5. **Power iteration:** $tG^n \to s$. ::: {.callout-tip title="Builder Notu — ML Köprüleri"} - **PageRank** → eigenfactor, **eigenvector centrality**, öneri sistemleri. - **Power iteration** → büyük-ölçek özvektör, **spektral kümeleme**. - **Işınlanma** → **düzenlileştirme** (label smoothing, $\epsilon$-greedy). - **Ağırlıklı graf** → spektral, **GNN**, attention-weighted komşu. - **DeepWalk / node2vec** → rassal yürüyüş gömme. ::: ## Ağırlıklı Rassal Yürüyüş {#sec-agirlikli} Yönsüz, $w_{ij} = w_{ji}$: $$ q_{ij} = \frac{w_{ij}}{\sum_k w_{ik}} $$ Detailed balance kontrolü → durağan ağırlık-toplamıyla orantılı: $$ s_i \propto \sum_k w_{ik} $$ ## Her Tersinir Zincir = Ağırlıklı Yürüyüş {#sec-tersinir-yuruyus} **Teorem:** Tersinir zincir → $w_{ij} = s_i q_{ij}$ koy. Tersinirlik ($s_i q_{ij} = s_j q_{ji}$) → $w_{ij} = w_{ji}$ (simetrik). Geçişi hesapla: $$ \frac{w_{ij}}{\sum_k w_{ik}} = \frac{s_i q_{ij}}{s_i \sum_k q_{ik}} = q_{ij} $$ ## PageRank Markov Zinciri {#sec-pagerank} **İçgörü:** Sayfa önemi = **bağlantı verenlerin öneminden** doğar (sabit nokta). $$ s_j = \sum_i s_i q_{ij} \;\Rightarrow\; s = sQ $$ **Seyreltme:** $q_{ij} = 1/(\text{çıkış sayısı})$. **Sarkan sayfa:** $1/M$ tüm sayfalara. > *"The importance of a page is the long-run fraction of time that you spend at that page, randomly surfing the web."* — Blitzstein, 31:34 ## Google Zinciri ve Işınlanma {#sec-google-zinciri} $$ \boxed{G = \alpha Q + (1 - \alpha)\frac{J}{M}}, \quad \alpha = 0{,}85 $$ %85 bağlantı takip + %15 **rastgele sayfaya ışınlan**. **Neden ışınlanma?** - **İndirgenemezlik garantisi.** - **Aperiyodiklik / sıfırsızlık** → durağan teoremleri uygulanır (tersinir olmasa bile). ::: {.callout-important title="Builder Notu — Düzenlileştirme"} **Işınlanma = düzenlileştirme**: ana modele küçük düzgün bileşen karıştırmak. Aynı kalıp: **label smoothing**, **$\epsilon$-greedy** (RL), **Laplace düzeltmesi**, **dropout**. Patolojileri eler. ::: ## Power Iteration {#sec-power-iteration} $$ t, tG, tG^2, \ldots, tG^n \to s $$ **Neden ucuz?** - $Q$ **çok seyrek** (tipik sayfa az bağlantı). - $tJ$ = hepsi-1 vektörü (toplamı 1). Her adım $O(\text{kenar sayısı})$ — milyarlarca sayfada uygulanabilir. ```{python} #| label: fig-pagerank #| fig-cap: "PageRank power iteration: 4 sayfalı web (sayfa 4 sarkan). t G^n hızla durağan dağılıma yakınsar. α = 0.85, ışınlanma minik ama indirgenemezlik + aperiyodiklik garantisi. Google'ın milyar dolarlık fikri tek bir Markov zincirinin durağan dağılımı." #| fig-width: 11 #| fig-height: 5 import numpy as np import matplotlib.pyplot as plt L = np.array([ [0, 1, 1, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0], # sarkan ], dtype=float) M = L.shape[0] out = L.sum(axis=1) for i in range(M): if out[i] == 0: L[i] = 1.0 / M else: L[i] = L[i] / out[i] Q = L alpha = 0.85 G = alpha * Q + (1 - alpha) * np.ones((M, M)) / M # Power iteration t = np.ones(M) / M history = [t.copy()] for _ in range(40): t = t @ G history.append(t.copy()) history = np.array(history) # Özvektör (kontrol) vals, vecs = np.linalg.eig(G.T) pi = np.real(vecs[:, np.argmin(np.abs(vals - 1))]) pi = pi / pi.sum() fig, ax = plt.subplots(figsize=(11, 5)) renkler = ['#A51C30', '#DD6B20', '#2C5282', '#6B46C1'] for k, c in enumerate(renkler): ax.plot(history[:, k], color=c, linewidth=2.2, label=f'Sayfa {k+1}') ax.axhline(pi[k], color=c, linestyle=':', linewidth=1.5, alpha=0.6) ax.set_xlabel('iterasyon n', fontsize=12) ax.set_ylabel('PageRank skoru', fontsize=12) ax.set_title(f'PageRank power iteration → {np.round(pi, 3)}', fontsize=12) ax.legend(fontsize=11) ax.grid(True, alpha=0.3) plt.tight_layout() plt.show() print(f"\nFinal sıralama (yüksek→düşük): {np.argsort(-pi) + 1}") ``` ::: {.callout-important title="Builder Notu — Spektral Yöntemler"} **Power iteration** = en büyük özdeğerin özvektörünü bulmanın standart yöntemi. **Spektral kümeleme**, **latent faktör çıkarımı**, hatta bazı verimli **attention** yaklaşımları (linear attention) aynı desen. "Devasa ama seyrek operatörün baskın özvektörü, operatörü tekrar tekrar uygulayarak" — büyük-ölçek ML'in her yerinde. ::: ## Bu Dersin Özeti {#sec-ozet} 1. **Ağırlıklı yürüyüş:** $s_i \propto \sum w_{ik}$. 2. **Her tersinir = ağırlıklı ağ yürüyüşü** ($w_{ij} = s_i q_{ij}$). 3. **PageRank:** $s = sQ$. 4. **Google:** $G = \alpha Q + (1-\alpha) J/M$. 5. **Power iteration** + seyreklik. ::: {.callout-important title="Tek bir cümle"} **Her tersinir Markov zinciri ağırlıklı ağ yürüyüşüdür** (durağan ∝ ağırlık-derece); **PageRank** ise tersinir-olmayan dev zincir — web sayfalarını **ışınlanmayla sağlamlaştırılmış** Google zincirinin durağan dağılımını **power iteration** ile sıralar. **Önem = uzun vadede o sayfada geçirilen zaman.** ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: Her tersinir → ağ yürüyüşü ispatı?"} **Cevap:** $w_{ij} = s_i q_{ij}$. Tersinirlik → $w_{ij} = w_{ji}$. Geçiş: $w_{ij}/\sum w_{ik} = q_{ij}$ ($s_i$ sadeleşir). ::: ::: {.callout-note collapse="true" title="Soru 2: Seyreltme + sarkan sayfa?"} **Cevap:** $q_{ij} = 1/$çıkış sayısı. Sarkan → $1/M$ tüm sayfalara → satır toplamı 1. ::: ::: {.callout-note collapse="true" title="Soru 3: Işınlanma niye?"} **Cevap:** İndirgenemezlik + sıfırsız → durağan teoremleri uygulanır. ::: ::: {.callout-note collapse="true" title="Soru 4: Neden power iteration?"} **Cevap:** $O(m^3)$ imkânsız. $tG^n \to s$ ve seyreklik + $tJ$ = hepsi-1 → her adım ucuz. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** Üçgen, $w_{12}=1, w_{13}=2, w_{23}=3$. Durağan? **Egzersiz 2.** Detailed balance kontrolü. **Egzersiz 3.** Küçük web: 1→2,3; 2→3; 3→1. $Q$ matrisi. **Egzersiz 4.** Egzersiz 3'te $\alpha = 0{,}85$ ile $G_{11}$? **Egzersiz 5.** *(Python — PageRank)* ```{python} #| label: ex-pagerank #| code-fold: false import numpy as np L = np.array([[0,1,1,0],[1,0,1,0],[0,0,0,1],[0,0,0,0]], dtype=float) M = L.shape[0] out = L.sum(axis=1) for i in range(M): L[i] = L[i] / out[i] if out[i] > 0 else 1/M Q = L alpha = 0.85 G = alpha * Q + (1 - alpha) * np.ones((M, M)) / M t = np.ones(M) / M for _ in range(100): t = t @ G print(f"PageRank: {np.round(t, 4)}") print(f"Sıralama: {np.argsort(-t) + 1}") ``` ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 34: İleriye Bakış** — kursun **son dersi**! Top Ten + ötesi. ::: {.callout-warning title="Ders 34 öncesi yapılacak"} - Tüm kursu gözden geçir. - Markov + PageRank'i içselleştir. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Not | |--------|-------|------| | **Ağırlıklı yürüyüş** | $q = w/\sum w$ | Simetrik | | **Durağan** | $s_i \propto \sum w$ | Ağırlık-derece | | **Tersinir = ağ** | $w_{ij} = s_i q_{ij}$ | Hepsi | | **PageRank** | $s = sQ$ | Önem | | **Seyreltme** | $1/$çıkış | Sarkan: $1/M$ | | **Google** | $G = \alpha Q + (1-\alpha) J/M$ | $\alpha = 0.85$ | | **Işınlanma** | Düzenlileştirme | Patoloji eler | | **Power iteration** | $tG^n$ | Seyrek + $tJ$ ucuz | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="6 köprü"} 1. **PageRank** → eigenfactor, eigenvector centrality. 2. **Power iteration** → spektral kümeleme. 3. **Işınlanma** → label smoothing, $\epsilon$-greedy. 4. **Ağırlıklı graf** → GNN, attention. 5. **Tersinirlik** → MCMC spektral analiz. 6. **Random walk gömme** → DeepWalk, node2vec. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} **Her tersinir zincir = ağırlıklı ağ yürüyüşü**. **PageRank** = devasa Markov zincirinin durağan dağılımı + power iteration. Olasılığın milyar dolarlık fikri. :::