33 Markov: Sınıflandırma ve Tersinirlik

Detailed balance = MCMC’nin temeli

Bölüm bilgisi

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

33.1 Bu Derste Ne Var?

İndirgenemezlik (irreducibility): her durumdan her duruma.
Geri dönüşlü / geçici / yutucu / periyodik durumlar.
Durağan teoremleri: var + tek + $s_i = 1/r_i$ + yakınsama (aperiyodik).
Tersinirlik (detailed balance): $s_i q_{ij} = s_j q_{ji}$.
Yönsüz ağ rassal yürüyüşü: $s_i = d_i/\sum d_j$ (dereceyle orantılı).

Builder Notu — ML Köprüleri

Detailed balance = Metropolis-Hastings tasarım ilkesi.
İndirgenemez + aperiyodik = ergodiklik (MCMC neden işler).
Rassal yürüyüş ∝ derece → PageRank, degree centrality.
Graf gömme (DeepWalk, node2vec) = ağda rassal yürüyüş.
GNN difüzyonu = komşu ortalaması rassal yürüyüş.

33.2 İndirgenemezlik

Her durumdan her duruma ulaşılabilir (pozitif olasılıkla, sonlu adımda).

“Irreducible means you can get from anywhere to anywhere.” — Blitzstein, 5:32

Builder Notu — MCMC Indirgenemezlik

MCMC zincirinin örnek uzayını tamamen dolaşabilmesi koşulu. PageRank’te ışınlanma (teleportation) indirgenemezliği garanti eder (yoksa çıkışsız sayfalar tuzak olur).

33.3 Durum Türleri

Geri dönüşlü: olasılık 1 ile döner (sonsuz kez). İndirgenemez sonlu zincirde tüm durumlar geri dönüşlü.
Geçici: eninde sonunda dönmez.
Yutucu: girince hep orada (kumarbazın iflası).
Periyodik: belirli periyod katlarında dönüş.

33.4 Durağan Dağılım Teoremleri

İndirgenemez sonlu zincir:

Var.
Tek.
$s_i = 1/r_i$ ($r_i$ = ortalama geri dönüş süresi).
Aperiyodikse $tQ^n \to s$ (başlangıçtan bağımsız).

Builder Notu — Ergodiklik

İndirgenemez + aperiyodik = ergodiklik. Zaman-ortalaması (tek uzun yürüyüş) = uzay-ortalaması (durağan beklenti). Tek MCMC zincirinden örnek toplayabilmenin gerekçesi.

33.5 Tersinirlik (Detailed Balance)

\[ \boxed{s_i\, q_{ij} = s_j\, q_{ji}} \]

Teorem: $s$ detailed balance sağlıyorsa $s$ durağandır.

İspat: $\sum_i$ uygula:

\[ \sum_i s_i q_{ij} = \sum_i s_j q_{ji} = s_j \sum_i q_{ji} = s_j \cdot 1 = s_j \]

Sol = $(sQ)_j$ → $sQ = s$. ∎

Builder Notu — Metropolis-Hastings’in Sırrı

Detailed balance = MH’in tasarım ilkesi. Kabul olasılığı ($\min(1, \ldots)$) tam $s_i q_{ij} = s_j q_{ji}$ sağlanacak şekilde — normalizasyon sabiti gerekmez, sadece oran $s_j/s_i$! Bu, Bayesçi posterior’un (sabiti hesaplanamayan) örneklenmesini mümkün kılan can alıcı numara.

33.6 Yönsüz Ağda Rassal Yürüyüş

$d_i$ = derece, $q_{ij} = 1/d_i$ (komşuysa).

Detailed balance kontrolü: $d_i \cdot 1/d_i = 1 = d_j \cdot 1/d_j$ ✓

\[ \boxed{s_i = \frac{d_i}{\sum_j d_j}} \]

Durağan dağılım dereceyle orantılı — matris çözmeden.

import numpy as np
import matplotlib.pyplot as plt

# 5-düğümlü graf
A = np.array([
    [0,1,1,0,0],
    [1,0,1,1,0],
    [1,1,0,1,1],
    [0,1,1,0,1],
    [0,0,1,1,0],
], dtype=float)

deg = A.sum(axis=1)
Q = A / deg[:, None]

# (a) Formül
s_formula = deg / deg.sum()

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

# (c) Simülasyon
rng = np.random.default_rng(0)
state, counts = 0, np.zeros(5)
for _ in range(500_000):
    counts[state] += 1
    state = rng.choice(5, p=Q[state])
s_sim = counts / counts.sum()

fig, ax = plt.subplots(figsize=(10, 5))
x = np.arange(5)
w = 0.25
ax.bar(x - w, s_formula, w, color='#A51C30', label='(a) $d_i / \\sum d$ (formül)')
ax.bar(x, s_eig, w, color='#DD6B20', label='(b) Özvektör')
ax.bar(x + w, s_sim, w, color='#2C5282', label='(c) Simülasyon (500k adım)')
ax.set_xticks(x)
ax.set_xticklabels([f'Düğüm {i+1}\n(d={int(d)})' for i, d in enumerate(deg)])
ax.set_ylabel('durağan olasılık', fontsize=12)
ax.set_title(f'Durağan ∝ derece — toplam derece = {int(deg.sum())}', fontsize=12)
ax.legend(fontsize=11)
ax.grid(True, axis='y', alpha=0.3)
plt.tight_layout()
plt.show()

Şekil 33.1

Builder Notu — PageRank, GNN, DeepWalk

“Durağan ∝ derece” = PageRank’in çekirdeği. Web grafında sayfa önemi = rassal gezginin durağan dağılımı. Degree centrality, DeepWalk / node2vec (rassal yürüyüş örnekleme), GNN’in komşu ortalaması adımları — hepsi bu zincirden.

33.7 Bu Dersin Özeti

İndirgenemez + sonlu → tüm durumlar geri dönüşlü.
Durağan teoremi: var + tek + $s_i = 1/r_i$ + aperiyodikse yakınsar.
Detailed balance: $s_i q_{ij} = s_j q_{ji}$ ⟹ durağan.
Rassal yürüyüş: $s_i \propto d_i$.

Tek bir cümle

İndirgenemez + aperiyodik → durağan var/tek + yakınsama (ergodiklik = MCMC işler). Detailed balance ($s_i q_{ij} = s_j q_{ji}$) durağanı matris çözmeden verir — Metropolis-Hastings’in tasarım ilkesi. Yönsüz ağ rassal yürüyüş = derece orantılı = PageRank.

33.8 Kontrol Soruları

Soru 1: İndirgenemez sonluda geçici olabilir mi?

Cevap: Hayır. Hepsi geri dönüşlü.

Soru 2: s_i = 0.2 → r_i?

Cevap: $r_i = 5$. Ters orantı.

Soru 3: Detailed balance → durağan ispatı?

Cevap: $i$ üzerinden topla: $\sum s_i q_{ij} = s_j \cdot 1 = s_j$ → $sQ = s$.

Soru 4: d = (2, 2, 3, 1) durağan?

Cevap: $s = (2/8, 2/8, 3/8, 1/8)$.

33.9 Egzersizler

Egzersiz 1. Zinciri sınıflandır: 1→2, 2→1/2→3, 3→4, 4→3.

Egzersiz 2. İki durumlu Q, detailed balance kontrolü.

Egzersiz 3. $C_4$ döngüsü. Periyodik mi?

Egzersiz 4. Yıldız grafı: merkez vs yaprak.

Egzersiz 5. (Python — Üç yolla durağan)

import numpy as np
A = np.array([[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]], dtype=float)
deg = A.sum(axis=1)
Q = A / deg[:, None]

s_formula = deg / deg.sum()
vals, vecs = np.linalg.eig(Q.T)
pi = np.real(vecs[:, np.argmin(np.abs(vals - 1))])
print(f"Formül: {s_formula}")
print(f"Özvektör: {pi/pi.sum()}")

# Detailed balance
ok = np.allclose(s_formula[:, None] * Q, (s_formula[:, None] * Q).T)
print(f"Detailed balance: {ok}")

33.10 Sonraki Ders İçin Hazırlık

Ders 33: Markov + PageRank — ağırlıklı yürüyüş, Google’ın milyar dolarlık fikri.

Ders 33 öncesi yapılacak

Egzersizleri çöz.
Detailed balance + derece formülünü içselleştir.

33.11 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Not
İndirgenemez	Her → her	“Connected”
Geri dönüşlü	$P(\text{dönüş}) = 1$	Sonlu indirgenemez = hepsi
Yutucu	Hep orada	Iflas
Periyodik	Periyot katları	Yakınsamayı bozar
Durağan var+tek	$sQ = s$	İndirgenemez sonlu
$s_i = 1/r_i$	Ort. geri dönüş	Ters orantı
Yakınsama	$tQ^n \to s$	Aperiyodik
Detailed balance	$s_i q_{ij} = s_j q_{ji}$	⟹ durağan
Rassal yürüyüş	$s_i = d_i/\sum d_j$	Dereceyle orantılı

33.12 ML Bağlantıları Özeti

6 köprü

Metropolis-Hastings → detailed balance.
Ergodiklik → tek zincirden örnek.
PageRank → durağan dağılım.
DeepWalk / node2vec → rassal yürüyüş örnekleme.
GNN → rassal yürüyüş difüzyonu.
RL terminal → yutucu durum.

Tek bir şey alıp gideceksen

İndirgenemez + aperiyodik = MCMC’nin işlemesinin sebebi. Detailed balance = Metropolis-Hastings’in sırrı. Rassal yürüyüş ∝ derece = PageRank.

--- title: "Markov: Sınıflandırma ve Tersinirlik" subtitle: "Detailed balance = MCMC'nin temeli" --- ::: {.callout-note title="Bölüm bilgisi"} - **Blitzstein'in videosu:** [YouTube — Lecture 32](https://www.youtube.com/watch?v=aBGOyZv2pZE) (≈48 dk) - **Okuma süresi:** ≈23 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} 1. **İndirgenemezlik (irreducibility):** her durumdan her duruma. 2. **Geri dönüşlü / geçici / yutucu / periyodik** durumlar. 3. **Durağan teoremleri:** var + tek + $s_i = 1/r_i$ + yakınsama (aperiyodik). 4. **Tersinirlik (detailed balance):** $s_i q_{ij} = s_j q_{ji}$. 5. **Yönsüz ağ rassal yürüyüşü:** $s_i = d_i/\sum d_j$ (dereceyle orantılı). ::: {.callout-tip title="Builder Notu — ML Köprüleri"} - **Detailed balance** = **Metropolis-Hastings** tasarım ilkesi. - **İndirgenemez + aperiyodik** = **ergodiklik** (MCMC neden işler). - **Rassal yürüyüş ∝ derece** → **PageRank**, **degree centrality**. - **Graf gömme** (**DeepWalk, node2vec**) = ağda rassal yürüyüş. - **GNN difüzyonu** = komşu ortalaması rassal yürüyüş. ::: ## İndirgenemezlik {#sec-indirgenemez} Her durumdan her duruma **ulaşılabilir** (pozitif olasılıkla, sonlu adımda). > *"Irreducible means you can get from anywhere to anywhere."* — Blitzstein, 5:32 ::: {.callout-tip title="Builder Notu — MCMC Indirgenemezlik"} MCMC zincirinin **örnek uzayını tamamen dolaşabilmesi** koşulu. **PageRank**'te **ışınlanma (teleportation)** indirgenemezliği garanti eder (yoksa çıkışsız sayfalar tuzak olur). ::: ## Durum Türleri {#sec-durum-turleri} - **Geri dönüşlü:** olasılık 1 ile döner (sonsuz kez). İndirgenemez sonlu zincirde **tüm durumlar** geri dönüşlü. - **Geçici:** eninde sonunda dönmez. - **Yutucu:** girince hep orada (kumarbazın iflası). - **Periyodik:** belirli periyod katlarında dönüş. ## Durağan Dağılım Teoremleri {#sec-duragan-teorem} İndirgenemez sonlu zincir: 1. **Var.** 2. **Tek.** 3. $s_i = 1/r_i$ ($r_i$ = ortalama geri dönüş süresi). 4. **Aperiyodikse** $tQ^n \to s$ (başlangıçtan bağımsız). ::: {.callout-important title="Builder Notu — Ergodiklik"} **İndirgenemez + aperiyodik = ergodiklik**. Zaman-ortalaması (tek uzun yürüyüş) = uzay-ortalaması (durağan beklenti). **Tek MCMC zincirinden örnek toplayabilmenin gerekçesi.** ::: ## Tersinirlik (Detailed Balance) {#sec-tersinirlik} $$ \boxed{s_i\, q_{ij} = s_j\, q_{ji}} $$ **Teorem:** $s$ detailed balance sağlıyorsa $s$ **durağandır**. **İspat:** $\sum_i$ uygula: $$ \sum_i s_i q_{ij} = \sum_i s_j q_{ji} = s_j \sum_i q_{ji} = s_j \cdot 1 = s_j $$ Sol = $(sQ)_j$ → $sQ = s$. ∎ ::: {.callout-important title="Builder Notu — Metropolis-Hastings'in Sırrı"} **Detailed balance = MH'in tasarım ilkesi**. Kabul olasılığı ($\min(1, \ldots)$) tam $s_i q_{ij} = s_j q_{ji}$ sağlanacak şekilde — **normalizasyon sabiti gerekmez**, sadece **oran $s_j/s_i$**! Bu, Bayesçi posterior'un (sabiti hesaplanamayan) örneklenmesini mümkün kılan **can alıcı numara**. ::: ## Yönsüz Ağda Rassal Yürüyüş {#sec-yonsuz-ag} $d_i$ = derece, $q_{ij} = 1/d_i$ (komşuysa). **Detailed balance kontrolü:** $d_i \cdot 1/d_i = 1 = d_j \cdot 1/d_j$ ✓ $$ \boxed{s_i = \frac{d_i}{\sum_j d_j}} $$ **Durağan dağılım dereceyle orantılı** — matris çözmeden. ```{python} #| label: fig-yonsuz-yuruyus #| fig-cap: "Yönsüz ağda rassal yürüyüş: durağan dağılım dereceyle orantılı. Üç farklı hesaplama yolu (formül, özvektör, simülasyon) aynı sonuca varır. PageRank, GNN, DeepWalk'un temel sezgisi." #| fig-width: 10 #| fig-height: 5 import numpy as np import matplotlib.pyplot as plt # 5-düğümlü graf A = np.array([ [0,1,1,0,0], [1,0,1,1,0], [1,1,0,1,1], [0,1,1,0,1], [0,0,1,1,0], ], dtype=float) deg = A.sum(axis=1) Q = A / deg[:, None] # (a) Formül s_formula = deg / deg.sum() # (b) Özvektör vals, vecs = np.linalg.eig(Q.T) pi = np.real(vecs[:, np.argmin(np.abs(vals - 1))]) s_eig = pi / pi.sum() # (c) Simülasyon rng = np.random.default_rng(0) state, counts = 0, np.zeros(5) for _ in range(500_000): counts[state] += 1 state = rng.choice(5, p=Q[state]) s_sim = counts / counts.sum() fig, ax = plt.subplots(figsize=(10, 5)) x = np.arange(5) w = 0.25 ax.bar(x - w, s_formula, w, color='#A51C30', label='(a) $d_i / \\sum d$ (formül)') ax.bar(x, s_eig, w, color='#DD6B20', label='(b) Özvektör') ax.bar(x + w, s_sim, w, color='#2C5282', label='(c) Simülasyon (500k adım)') ax.set_xticks(x) ax.set_xticklabels([f'Düğüm {i+1}\n(d={int(d)})' for i, d in enumerate(deg)]) ax.set_ylabel('durağan olasılık', fontsize=12) ax.set_title(f'Durağan ∝ derece — toplam derece = {int(deg.sum())}', fontsize=12) ax.legend(fontsize=11) ax.grid(True, axis='y', alpha=0.3) plt.tight_layout() plt.show() ``` ::: {.callout-important title="Builder Notu — PageRank, GNN, DeepWalk"} "Durağan ∝ derece" = **PageRank'in çekirdeği**. Web grafında sayfa önemi = rassal gezginin durağan dağılımı. **Degree centrality**, **DeepWalk / node2vec** (rassal yürüyüş örnekleme), **GNN'in komşu ortalaması adımları** — hepsi bu zincirden. ::: ## Bu Dersin Özeti {#sec-ozet} 1. **İndirgenemez** + sonlu → tüm durumlar geri dönüşlü. 2. **Durağan teoremi:** var + tek + $s_i = 1/r_i$ + aperiyodikse yakınsar. 3. **Detailed balance:** $s_i q_{ij} = s_j q_{ji}$ ⟹ durağan. 4. **Rassal yürüyüş:** $s_i \propto d_i$. ::: {.callout-important title="Tek bir cümle"} **İndirgenemez + aperiyodik** → durağan var/tek + yakınsama (**ergodiklik = MCMC işler**). **Detailed balance** ($s_i q_{ij} = s_j q_{ji}$) durağanı matris çözmeden verir — **Metropolis-Hastings'in tasarım ilkesi**. **Yönsüz ağ rassal yürüyüş** = derece orantılı = **PageRank**. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: İndirgenemez sonluda geçici olabilir mi?"} **Cevap:** Hayır. Hepsi geri dönüşlü. ::: ::: {.callout-note collapse="true" title="Soru 2: s_i = 0.2 → r_i?"} **Cevap:** $r_i = 5$. Ters orantı. ::: ::: {.callout-note collapse="true" title="Soru 3: Detailed balance → durağan ispatı?"} **Cevap:** $i$ üzerinden topla: $\sum s_i q_{ij} = s_j \cdot 1 = s_j$ → $sQ = s$. ::: ::: {.callout-note collapse="true" title="Soru 4: d = (2, 2, 3, 1) durağan?"} **Cevap:** $s = (2/8, 2/8, 3/8, 1/8)$. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** Zinciri sınıflandır: 1→2, 2→1/2→3, 3→4, 4→3. **Egzersiz 2.** İki durumlu Q, detailed balance kontrolü. **Egzersiz 3.** $C_4$ döngüsü. Periyodik mi? **Egzersiz 4.** Yıldız grafı: merkez vs yaprak. **Egzersiz 5.** *(Python — Üç yolla durağan)* ```{python} #| label: ex-markov-cls #| code-fold: false import numpy as np A = np.array([[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]], dtype=float) deg = A.sum(axis=1) Q = A / deg[:, None] s_formula = deg / deg.sum() vals, vecs = np.linalg.eig(Q.T) pi = np.real(vecs[:, np.argmin(np.abs(vals - 1))]) print(f"Formül: {s_formula}") print(f"Özvektör: {pi/pi.sum()}") # Detailed balance ok = np.allclose(s_formula[:, None] * Q, (s_formula[:, None] * Q).T) print(f"Detailed balance: {ok}") ``` ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 33: Markov + PageRank** — ağırlıklı yürüyüş, Google'ın milyar dolarlık fikri. ::: {.callout-warning title="Ders 33 öncesi yapılacak"} - Egzersizleri çöz. - Detailed balance + derece formülünü içselleştir. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Not | |--------|-------|------| | **İndirgenemez** | Her → her | "Connected" | | **Geri dönüşlü** | $P(\text{dönüş}) = 1$ | Sonlu indirgenemez = hepsi | | **Yutucu** | Hep orada | Iflas | | **Periyodik** | Periyot katları | Yakınsamayı bozar | | **Durağan var+tek** | $sQ = s$ | İndirgenemez sonlu | | **$s_i = 1/r_i$** | Ort. geri dönüş | Ters orantı | | **Yakınsama** | $tQ^n \to s$ | Aperiyodik | | **Detailed balance** | $s_i q_{ij} = s_j q_{ji}$ | ⟹ durağan | | **Rassal yürüyüş** | $s_i = d_i/\sum d_j$ | Dereceyle orantılı | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="6 köprü"} 1. **Metropolis-Hastings** → detailed balance. 2. **Ergodiklik** → tek zincirden örnek. 3. **PageRank** → durağan dağılım. 4. **DeepWalk / node2vec** → rassal yürüyüş örnekleme. 5. **GNN** → rassal yürüyüş difüzyonu. 6. **RL terminal** → yutucu durum. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} **İndirgenemez + aperiyodik = MCMC'nin işlemesinin sebebi**. **Detailed balance** = Metropolis-Hastings'in sırrı. **Rassal yürüyüş ∝ derece** = PageRank. :::