20 Eyer Noktaları (Devam), Maxmin İlkesi

Courant-Fischer maxmin ilkesi, interlacing kanıtı ve covariance köprüsü

Bölüm bilgisi

Video: MIT 18.065 — Saddle Points Continued, Maxmin Principle · OCW: Lecture 19 · Okuma süresi: ≈32 dk · Konuşmacı: Gilbert Strang · Önkoşul: Ders 18 (parametre sayımı, Rayleigh, eyer).

Ders 18’in eyer noktası fikrini tamamlıyoruz. Çekirdek: maxmin ilkesi (Courant-Fischer) — aradaki bir özdeğeri (eyer değeri) bir maks-min olarak yaz. Bu, Ders 15’in interlacing teoremini doğrudan kanıtlar. Dersin sonu istatistiğe (covariance) köprü kurar; lineer cebir bloğu kapanıyor, istatistik bloğu başlıyor.

20.1 Bu Derste Ne Var?

Bu ders Ders 18’in yarım kalan eyer tartışmasını kapatır ve dört sonuca yürür: önce somut bir Rayleigh örneğinde değerlerin nereden geldiğini görürüz, ardından her kritik noktanın bir özvektör (değeri bir özdeğer) olduğunu okuruz, sonra eyer değerini bir maks-min olarak yazan ilkeyi (Courant-Fischer) kurarız ve son olarak bu ilkeden interlacing kanıtının nasıl düştüğünü görürüz. Kapanışta covariance köprüsü açılır.

Dört sonuç:

Rayleigh örneği: $S = \mathrm{diag}(5, 3, 1)$ için $R$’nin maks = 5 (özdeğer $\lambda_{1}$, özvektör $e_{1}$), min = 1 ($\lambda_{3}$, $e_{3}$), eyer = 3 ($\lambda_{2}$, $e_{2}$).
Değerler = özdeğer, yerler = özvektör: Rayleigh’in tüm kritik noktaları özvektör, değerleri özdeğer.
Maxmin ilkesi: $\lambda_{k} = \max$ (boyut-$k$ alt-uzaylar $V$) $\min$ ($x \in V$) $R(x)$. Eyeri maks-min’e çevirir.
Interlacing kanıtı: maxmin’den, $S$ perturbe edilince veya bir satır+sütun atılınca özdeğerlerin neden içiçe geçtiği düşer.

“…what happens if you have a saddle point or a degenerate minimum?” — Strang, 1:00 (derin öğrenme motivasyonu)

flowchart TB
    M["Eyer noktalari + maxmin"]

    M --> R["Rayleigh ornegi diag(5,3,1):<br/>maks 5, min 1, EYER 3"]
    M --> V["degerler = ozdeger,<br/>yerler = ozvektor"]
    M --> S["eyer tanimi:<br/>gradyan 0 + Hessian belirsiz"]
    M --> C["maxmin (Courant-Fischer):<br/>lambda_k = max uzerinden min"]
    C --> I["maxmin -> interlacing kaniti<br/>(Ders 15)"]

    N["NYU koprusu: graf Laplacian /<br/>GCN / Fiedler lambda_2"]
    P["covariance onizleme:<br/>simetrik PSD (Ders 20)"]

    classDef center fill:#1f4e79,stroke:#163a5c,color:#ffffff,stroke-width:2px;
    classDef branch fill:#2e75b6,stroke:#1f4e79,color:#ffffff,stroke-width:1px;
    classDef side fill:#9dc3e6,stroke:#2e75b6,color:#11151c,stroke-width:1px;

    class M center;
    class R,V,S,C,I branch;
    class N,P side;

Şekil 20.1: Ders 19 kavram haritasi: eyer noktalari ve maxmin ilkesi merkezde; Rayleigh ornegi, ozdeger-ozvektor okumasi, eyer tanimi, Courant-Fischer maxmin ve interlacing kaniti dallarda; NYU GCN koprusu ve covariance onizlemesi ayri dugumlerde.

Kavram haritası (Şekil 20.1) dersin omurgasını gösterir: merkezde eyer noktaları ve maxmin ilkesi, dallarda Rayleigh örneği, özdeğer-özvektör okuması, eyer tanımı ve Courant-Fischer’dan interlacing’e giden kanıt; yan düğümlerde NYU GCN köprüsü ve covariance önizlemesi.

Builder Notu — Eyerden Maks-Min’e

Eyer noktaları = derin öğrenmenin merkezi: yüksek boyutlu kayıp yüzeyinde minimumdan çok eyer var; gradient descent’in (Ders 22) eyerlerden kaçışı başarının anahtarı.
Maxmin (Courant-Fischer) — ara özdeğerleri optimizasyon diliyle tanımlar; spektral graf teorisinin (NYU paralel ders, GCN) temeli.
$\lambda_{2}$ = Fiedler değeri — graf bölmenin (spektral kümeleme, Ders 35) anahtarı; maxmin ile karakterize edilir.
Geriye köprü: Ders 18 (Rayleigh, eyer, KKT), Ders 15 (interlacing), Ders 16 (Weyl), Ders 5 (pozitif tanımlı).

20.2 Eyer Noktaları Neden Önemli?

Strang neden eyer noktalarına bu kadar yer ayırdığını açıklar: derin öğrenmenin kalbi, toplam maliyet fonksiyonunun minimumunu gradient descent ile bulmaktır. Ama yüksek boyutta her şey minimum değildir.

“…what happens if you have a saddle point or a degenerate minimum?” — Strang, 1:00

Maksimum ve minimumu biliyoruz; eyer noktaları daha bulanık. Derin öğrenmenin anlaşılması giderek “gradient descent ne üretiyor, eyerlerde ne oluyor?” sorusuna odaklanıyor. Bu yüzden eyeri netleştirmek şart.

Builder Notu — Kayıp Yüzeyinin Çoğu Eyer

Yüksek boyutlu kayıp yüzeylerinde kritik noktaların ezici çoğunluğu eyerdir — gerçek yerel minimum nadirdir. ML köprüsü: derin öğrenmenin “neden çalışıyor?” gizeminin büyük kısmı, SGD’nin (Ders 25) eyerlerden nasıl kaçtığıyla ilgili; eyer geometrisi optimizasyon teorisinin sıcak konusu.

20.3 Rayleigh Örneği: S = diag(5, 3, 1)

Somut örnek. Köşegen (dolayısıyla simetrik) bir matris al — her simetrik matris ortogonal değişkene dönüştürülebileceğinden genelliği kaybetmeyiz. $x = (u, v, w)$, 3 boyut:

\[R(x) = \frac{x^{T}Sx}{x^{T}x} = \frac{5u^{2} + 3v^{2} + w^{2}}{u^{2} + v^{2} + w^{2}}\]

Üç soru: maks, min ve eyer. Maks = 5: tüm ağırlığı $u$’ya yükle, $x = (1, 0, 0)$. Min = 1: her şeyi $w$’ye yükle, $x = (0, 0, 1)$. Birinci türevlerin sıfır olduğu üçüncü bir nokta daha var mı? Evet:

\[\max R = 5\ \text{at}\ (1,0,0), \quad \min R = 1\ \text{at}\ (0,0,1), \quad \text{saddle } R = 3\ \text{at}\ (0,1,0)\]

Eyer değeri 3, orta noktada $(0, 1, 0)$.

İki düzlem kesiti bunu görselleştirir (Şekil 20.2): birim çemberi $(u,v,0)$ düzleminde gezdirirsen $R$ değerleri $[3, 5]$ arasında salınır (5 ile 3’ün arası); $(0,v,w)$ düzleminde ise $[1, 3]$ arasında. Eyer değeri 3, iki düzlemin ORTAK değeridir — bir düzlemde maks, diğerinde min. İşte eyerin geometrik imzası budur.

Kod

th, puv, pvw = two_plane_sections(S19)

fig, ax = plt.subplots(figsize=(8, 4.2))
ax.plot(th, puv, color=COL_PRIMARY, lw=2, label="(u,v,0) düzlemi: 5 ile 3 arası")
ax.plot(th, pvw, color=COL_VEC3, lw=2, label="(0,v,w) düzlemi: 3 ile 1 arası")
ax.axhline(5, color=COL_STEEL_300, ls="--", lw=1.2)
ax.axhline(1, color=COL_STEEL_300, ls="--", lw=1.2)
ax.axhline(3, color=COL_TEAL, ls="--", lw=1.8, label="eyer = 3: iki düzlemin ORTAK değeri")
ax.set_xlabel("theta (birim çember)")
ax.set_ylabel("R(x)")
ax.legend()
ax.set_title("Rayleigh iki düzlemde: (u,v) kesiti [3,5], (v,w) kesiti [1,3] — eyer 3 ikisinin kesişimi")
apply_style(ax)
plt.show()

Şekil 20.2: Rayleigh iki düzlemde: (u,v) kesiti [3,5], (v,w) kesiti [1,3] — eyer 3 ikisinin kesişimi (maks bir düzlemde min diğerinde)

Builder Notu — Önce Köşegenleştir Sonra Oku

Rayleigh bölümünü köşegen $S$ ile incelemek tüm genelliği korur (Ders 18): herhangi simetrik $S$, ortogonal bir değişken dönüşümüyle köşegen hâle gelir, $R$’nin maks/min/eyer yapısı değişmez. Bu “önce köşegenleştir, sonra oku” stratejisi spektral analizin standart ilk hamlesidir.

20.4 Değerler = Özdeğer, Yerler = Özvektör

Rayleigh bölümünün kritik noktalarının (birinci türevin sıfır olduğu yerler) tümü $S$’nin özvektörleridir; oradaki değerler özdeğerlerdir:

“The values there are the eigenvalues. And the places where you reach them are the eigenvectors.” — Strang, 7:38

Örnekte: maks 5 = $\lambda_{1}$ ($e_{1}$), min 1 = $\lambda_{3}$ ($e_{3}$), eyer 3 = $\lambda_{2}$ ($e_{2}$). Rayleigh karmaşık bir fonksiyon (türevi için bölüm kuralı veya Lagrange çarpanı gerek), ama sonucu kusursuz: değerler özdeğer, yerler özvektör. Pratik not: en büyük ve en küçük özvektörü hesaplamak, aradaki (eyer) özvektörleri hesaplamaktan genelde çok daha kolaydır.

İki düzlem kesiti (Şekil 20.2) bunu da gösterir: tepe değer 5 ile dip değer 1, eğrilerin uç noktalarında (özvektör doğrultularında) okunur; eyer değeri 3 ise iki düzlemin ortak noktasıdır.

Builder Notu — Uçlar Kolay Ara Zor

“Uç özdeğerler kolay, ara özdeğerler zor” gerçeği sayısal lineer cebirin temel asimetrisidir: power iteration en büyüğü bulur, ama $\lambda_{2}$’yi (Fiedler) bulmak deflation/Lanczos ister. ML köprüsü: spektral kümeleme (Ders 35) tam da $\lambda_{2}$ özvektörüne (Fiedler vektörü) ihtiyaç duyar — bu yüzden iyi kodlar ve dikkat gerektirir.

20.5 Eyer = Gradyan 0, Hessian Belirsiz

Eyer noktası iki koşulla tanımlanır. (1) Birinci türevler (gradyan vektörü) sıfır:

\[\nabla R = \left(\frac{\partial R}{\partial u}, \frac{\partial R}{\partial v}, \frac{\partial R}{\partial w}\right) = 0\]

İkinci türevler — $3\times 3$ bir matris (Hessian). Karışık türevler eşit olduğundan ($\partial^{2}R/\partial u\,\partial v = \partial^{2}R/\partial v\,\partial u$) bu matris simetrik:

\[H = \begin{bmatrix} R_{uu} & R_{uv} & R_{uw} \\ R_{vu} & R_{vv} & R_{vw} \\ R_{wu} & R_{wv} & R_{ww} \end{bmatrix}\]

Maksimumda $H$ negatif tanımlı, minimumda pozitif tanımlı, eyerde belirsiz (karışık işaretli özdeğerler) — bazı yönlerde yukarı, bazılarında aşağı.

Üç kritik noktada sayısal Hessian’ı (merkez fark) hesaplayıp özdeğerlerine bakınca işaret deseni netleşir (Şekil 20.3): maks $q_{1}$’de $[-8, -4, 0] \leq 0$ (negatif-tanımlı), min $q_{3}$’te $[0, 4, 8] \geq 0$ (pozitif-tanımlı), eyer $q_{2}$’de ise $[-4, 0, +4]$ — işaretler karışık. Buradaki 0 özdeğer radyal yöndendir: $R$ ölçekten bağımsız (0-homojen) olduğundan o yönde değişmez. Sınıflandırmayı yapan tam da bu işaret desenidir.

Kod

H1 = rayleigh_hessian_numeric(S19, np.array([1., 0., 0.]))
H2 = rayleigh_hessian_numeric(S19, np.array([0., 1., 0.]))
H3 = rayleigh_hessian_numeric(S19, np.array([0., 0., 1.]))
eig1 = np.sort(np.linalg.eigvalsh(H1))
eig2 = np.sort(np.linalg.eigvalsh(H2))
eig3 = np.sort(np.linalg.eigvalsh(H3))

fig, axes = plt.subplots(1, 3, figsize=(10, 3.6))
panels = [
    (axes[0], eig1, "q1 (maks): [-8, -4, 0] <= 0"),
    (axes[1], eig2, "q2 (EYER): [-4, 0, +4] KARISIK"),
    (axes[2], eig3, "q3 (min): [0, 4, 8] >= 0"),
]
for ax, eig, title in panels:
    cols = []
    for v in eig:
        if abs(v) < 1e-3:
            cols.append(COL_STEEL_300)
        elif v > 0:
            cols.append(COL_PRIMARY)
        else:
            cols.append(COL_VEC3)
    xpos = np.arange(len(eig))
    ax.bar(xpos, eig, color=cols, edgecolor=COL_TEXT, linewidth=0.7, width=0.6)
    ax.axhline(0.0, color=COL_TEXT, linewidth=0.9)
    ax.set_xticks(xpos)
    ax.set_xticklabels(["ozdeger 1", "ozdeger 2", "ozdeger 3"], fontsize=8)
    ax.set_ylim(-9.5, 9.5)
    ax.set_title(title, color=COL_TEXT, fontsize=10, fontweight="bold")
    for x, v in zip(xpos, eig):
        off = 0.5 if v >= 0 else -0.5
        va = "bottom" if v >= 0 else "top"
        ax.text(x, v + off, "{:.0f}".format(v), ha="center", va=va, color=COL_TEXT, fontsize=9, fontweight="bold")
    apply_style(ax)
axes[0].set_ylabel("Hessian ozdegeri", color=COL_TEXT)
fig.suptitle("Hessian kritik noktayi siniflar: maks negatif-tanimli, min pozitif-tanimli, EYER belirsiz (0 = radyal yon, R olcekten bagimsiz)", fontsize=10.5, color=COL_TEXT)
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 20.3: Üç kritik noktanın sayısal Hessian özdeğerleri (merkez fark). Maksimum (q₁) negatif-tanımlı [−8, −4, 0], minimum (q₃) pozitif-tanımlı [0, 4, 8], eyer (q₂) ise işaretleri karışık [−4, 0, +4] — sınıflandırmayı yapan tam da bu işaret deseni.

Builder Notu — İşaretler Kritik Noktayı Sınıflar

Hessian’ın tanımlılığı bir kritik noktayı sınıflar: pozitif tanımlı = minimum, negatif tanımlı = maksimum, belirsiz = eyer (Ders 5 + Ders 18 pivot/atalet testi). ML köprüsü: ikinci-derece optimizasyon (Newton) ve eyer-kaçış yöntemleri Hessian’ın özdeğer işaretlerine bakar; derin ağ eğitiminde negatif eğrilik (negative curvature) yönleri eyerden çıkış kapısıdır.

20.6 Maxmin İlkesi (Courant-Fischer)

Eyer için en güzel fikir: onu bir maksimum-minimum olarak yaz, böylece maks/min’in kolaylığına geri dön.

“…write it as the maximum of a minimum.” — Strang, 10:38

İkinci özdeğer $\lambda_{2}$ için: tüm 2-boyutlu alt-uzaylar $V$ üzerinde, her $V$ içinde Rayleigh’in minimumunu al, sonra bu minimumların maksimumunu al:

\[\lambda_{2} = \max_{\dim V = 2}\ \min_{0 \neq x \in V}\ R(x)\]

Genel hâli (Courant-Fischer): $k$’inci özdeğer, boyut-$k$ alt-uzaylar üzerinde maks-min:

\[\lambda_{k} = \max_{\dim V = k}\ \min_{0 \neq x \in V}\ \frac{x^{T}Sx}{x^{T}x}\]

“…I’m going to take a maximum over two dimensional spaces…” — Strang, 12:08

Bu, sayısal olarak doğrudan doğrulanabilir (Şekil 20.5): 2000 rastgele 2B alt-uzayda Rayleigh’in minimumu hesaplanır; hepsi $\lambda_{2} = 3$’ün altında kalır (max-of-mins 2.999999) ve eşitlik yalnız özvektör uzayında ($\mathrm{span}\{q_{1}, q_{2}\}$) sağlanır. Aynı ilkenin ayna ikizi minimax’tır (Şekil 20.4, Egz4): $n-k+1$ boyutlu rastgele uzayların TÜM max değerleri $\lambda_{2} = 3$’ün üstünde (min-of-maxs 3.000012); kazanan $\mathrm{span}\{q_{2}, q_{3}\}$ tam 3.0 verir.

Kod

maxs, lam2b, winner_mm = minimax_experiment(S19, k=2, trials=2000)

fig, ax = plt.subplots(figsize=(7, 4))
ax.hist(maxs, bins=60, color=COL_ACCENT, alpha=0.9)
ax.axvline(3.0, color=COL_VEC3, linewidth=2.6)
ax.annotate("lambda_2 = 3 (hicbir V altina inemez)", xy=(3.0, ax.get_ylim()[1] * 0.92),
            xytext=(3.15, ax.get_ylim()[1] * 0.92), color=COL_VEC3, fontsize=9, fontweight="bold", va="center")
ax.annotate("kazanan: span{q2,q3} -> max = 3.0", xy=(3.0, ax.get_ylim()[1] * 0.55),
            xytext=(3.15, ax.get_ylim()[1] * 0.55), color=COL_PRIMARY, fontsize=9,
            arrowprops=dict(arrowstyle="->", color=COL_PRIMARY), va="center")
ax.set_xlabel("max R (V icinde)")
ax.set_ylabel("frekans")
ax.set_title("Minimax ikizi (Egz4): rastgele uzaylarin TUM max degerleri 3 un ustunde\n"
             "(min-of-maxs 3.000012) — maxmin in ayna simetrisi", fontsize=10)
apply_style(ax)
fig.tight_layout()
plt.show()

Şekil 20.4: Minimax ikizi (Egz4): n-k+1 boyutlu rastgele uzaylarin TUM max degerleri lambda_2 = 3 un ustunde (min-of-maxs 3.000012) — maxmin ilkesinin ayna simetrisi.

Builder Notu — Zoru İki Kolaya Böl

Maxmin, eyer noktasını (zor) iki kolay işlemin (min, sonra maks) bileşimine indirger — optimizasyonun klasik “minimax” yapısı (Ders 24 oyun teorisi/LP ile akraba). ML köprüsü: GAN’lar (üretici-ayırıcı) tam bir minimax problemidir; robust optimizasyon, adversarial eğitim hep maks-min/min-maks dengesi arar. Courant-Fischer bu yapının spektral kökenidir.

20.7 Örnek Hesap: λ₂ = 3

İlkeyi örnekte çalıştır ($S = \mathrm{diag}(5, 3, 1)$, $\lambda_{2} = 3$ bekliyoruz). $V = \mathrm{span}\{e_{1}, e_{2}\}$ al, yani $(u, v, 0)$ vektörleri ($w = 0$). Bu 2B uzayda Rayleigh:

\[R = \frac{5u^{2} + 3v^{2}}{u^{2} + v^{2}} \;\Rightarrow\; \min = 3 \ (\text{tum agirlik } v)\]

Bu $V$ için min = 3. Şimdi maks: başka bir $V$ denersek, örn. $\mathrm{span}\{e_{2}, e_{3}\} = (0, v, w)$ vektörleri:

\[R = \frac{3v^{2} + w^{2}}{v^{2} + w^{2}} \;\Rightarrow\; \min = 1\]

Bu $V$’nin minimumu 1 — daha küçük, kazanan değil. Tüm 2B uzaylar üzerinde minimumların maksimumu 3’tür (en iyi seçim $\mathrm{span}\{e_{1}, e_{2}\}$). Yani $_{2} = $ max-min $= 3$. ✓

Sayısal deney bunu tam onaylar (Şekil 20.5): solda 2000 rastgele 2B alt-uzayın min’leri histogramda hep $\lambda_{2} = 3$’ün altında toplanır (hiçbir $V$ geçemez); sağda iki örnek $V$ — $\mathrm{span}\{e_{1}, e_{2}\}$ min = 3 (kazanan) ile $\mathrm{span}\{e_{2}, e_{3}\}$ min = 1 karşılaştırılır.

Kod

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4.2))

# --- Sol: maxmin deneyi histogramı ---
mins, lam2, winner = maxmin_experiment(S19, k=2, trials=2000)
axL.hist(mins, bins=60, color=COL_PRIMARY, alpha=0.9)
axL.axvline(3.0, color=COL_VEC3, linewidth=3.0,
            label="lambda_2 = 3 (hicbir V gecemez)")
axL.annotate("kazanan: span{q1,q2} -> min = 3.0 birebir",
             xy=(winner, 0.0), xytext=(0.30, 0.82), textcoords="axes fraction",
             fontsize=9, color=COL_TEXT,
             arrowprops=dict(arrowstyle="->", color=COL_TEAL, lw=1.4))
axL.set_xlabel("min R (V icinde)")
axL.set_ylabel("frekans (2000 rastgele 2B alt-uzay)")
axL.legend(loc="upper left", fontsize=8)
apply_style(axL)

# --- Sag: iki ornek V bar ---
v_e12 = subspace_min(S19, np.eye(3)[:, :2])    # span{e1,e2} -> 3
v_e23 = subspace_min(S19, np.eye(3)[:, 1:])    # span{e2,e3} -> 1
xs = [0, 1]
axR.bar(xs[0], v_e12, width=0.55, color=COL_PRIMARY, label="span{e1,e2}")
axR.bar(xs[1], v_e23, width=0.55, color=COL_ACCENT, label="span{e2,e3}")
axR.axhline(3.0, color=COL_VEC3, linewidth=2.0, linestyle="--",
            label="lambda_2 = 3")
axR.set_xticks(xs)
axR.set_xticklabels(["span{e1,e2}", "span{e2,e3}"])
axR.set_ylabel("min R (V icinde)")
axR.legend(loc="upper right", fontsize=8)
apply_style(axR)

fig.suptitle("Courant-Fischer SAYISAL KANIT: 2000 rastgele alt-uzayin TUM min leri "
             "lambda_2 = 3 un altinda (max-of-mins 2.999999); esitlik yalniz ozvektor uzayinda",
             fontsize=9, color=COL_TEXT)
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 20.5: Courant-Fischer maxmin SAYISAL KANIT: 2000 rastgele 2B alt-uzayın TÜM min değerleri λ₂ = 3’ün altında (max-of-mins 2.999999); eşitlik yalnız özvektör uzayında. Sağda iki örnek: span{e₁,e₂} → min = 3 (kazanan), span{e₂,e₃} → min = 1.

Builder Notu — Kazanan Alt-Uzay Özvektörlerin

“Doğru alt-uzayı seç, minimumu maksimize et” hesabı, maxmin’in neden tam $\lambda_{2}$’yi verdiğini somutlaştırır: en iyi 2B uzay, ilk iki özvektörün gerdiği uzaydır ve oradaki min tam $\lambda_{2}$’dir. ML köprüsü: bu, PCA’nın “en iyi $k$-boyutlu alt-uzay” karakterizasyonunun (Ders 7 Eckart-Young) özdeğer ikizidir — alt-uzay optimizasyonu ve spektral gömme aynı maxmin iskeletini paylaşır.

20.8 Maxmin → Interlacing Kanıtı

Maxmin ilkesi sadece şık bir tanım değil — Ders 15’in interlacing teoremini doğrudan üretir:

“…would lead you… very quickly to the interlacing theorem…” — Strang, 11:31

Sezgi: $\lambda_{k} = \max_{\dim V = k} \min_{x\in V} R(x)$. Şimdi $S$’yi perturbe et (rank-1 ekle) veya bir satır+sütun at (alt-matris, Ders 15). Kısıtlama, alt-uzay seçim havuzunu daraltır veya genişletir; ama maks-min bir adım kayar. Örneğin bir satır+sütun atmak, alt-uzayları bir boyut daha kısıtlar — yeni $\lambda$’lar eski $\lambda$’ların arasına sıkışır:

\[\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)\]

Çünkü min-üzerinden-max yapısında bir kısıt eklemek değeri ne çok yukarı ne çok aşağı oynatabilir — tam interlacing. Ders 16’nın Weyl eşitsizliği de aynı maxmin makinesinden gelir.

Sayı doğrusu üzerinde bu içiçe geçiş açıkça görünür (Şekil 20.6): $4\times 4$ rastgele simetrik bir $S$ için özdeğerler $\lambda = [2.886, 0.927, -0.812, -1.341]$, son satır+sütun atılınca elde edilen $3\times 3$ alt-matrisin özdeğerleri $\mu = [2.886, 0.311, -1.146]$ — her $\mu_{k}$ tam olarak $\lambda_{k}$ ile $\lambda_{k+1}$ arasına sıkışır. 50 rastgele matriste ihlal sayısı 0.

Kod

rng = np.random.default_rng(3)
B = rng.standard_normal((4, 4)); S4 = (B + B.T) / 2
lam, mu, okc = interlace_submatrix(S4)

fig, ax = plt.subplots(figsize=(8, 3.4))

# gri ince kesik dikey baglar: her mu_k, lambda_k ve lambda_{k+1} arasina sikisir
for k in range(len(mu)):
    ax.plot([lam[k], lam[k]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1)
    ax.plot([lam[k + 1], lam[k + 1]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1)
    ax.plot([mu[k], mu[k]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1)

# lambda (S): y=1, navy yuvarlak
ax.scatter(lam, np.ones_like(lam), s=80, color=COL_PRIMARY, marker="o", zorder=3,
           edgecolors=COL_WHITE, linewidths=0.8)
for v in lam:
    ax.annotate(f"{v:.3f}", (v, 1), textcoords="offset points", xytext=(0, 9),
                ha="center", fontsize=8, color=COL_TEXT)

# mu (satir+sutun atilmis): y=0, steel kare
ax.scatter(mu, np.zeros_like(mu), s=80, color=COL_ACCENT, marker="s", zorder=3,
           edgecolors=COL_WHITE, linewidths=0.8)
for v in mu:
    ax.annotate(f"{v:.3f}", (v, 0), textcoords="offset points", xytext=(0, -16),
                ha="center", fontsize=8, color=COL_TEXT)

ax.set_ylim(-0.5, 1.5)
ax.set_yticks([0, 1])
ax.set_yticklabels(["mu (satir+sutun atilmis)", "lambda (S)"])
ax.set_title("Maxmin -> interlacing: mu lar lambda larin ARASINA sikisir "
             "(lambda_k >= mu_k >= lambda_k+1) — 50 rastgele matriste ihlal 0",
             fontsize=9.5)
apply_style(ax)

plt.show()

Şekil 20.6: Maxmin -> interlacing: satir+sutun atinca mu lar lambda larin ARASINA siksir (lambda_k >= mu_k >= lambda_k+1) — 50 rastgele matriste ihlal 0.

Builder Notu — Bir İlke İki Teorem

Maxmin’in interlacing’i “ücretsiz” üretmesi, doğru soyutlamanın gücüdür: tek bir ilke (Courant-Fischer) hem özdeğer tanımını hem perturbasyon teoremlerini verir. ML köprüsü: NYU paralel dersinin spektral graf evrişim ağları (GCN), graf Laplacian’ının özdeğerlerini kullanır; bu özdeğerler maxmin ile tanımlanır ve graf değişince (kenar ekle/çıkar) interlacing onların nasıl kayacağını sınırlar — dinamik/gürültülü graflarda GCN kararlılığının teorik temeli. NYU H13 GCN (konuk Bresson): graf Laplacian özdeğerleri maxmin ile tanımlanır; $\lambda_{2}$ = Fiedler değeri spektral kümelemenin anahtarı; interlacing dinamik graflarda spektrum kararlılığını sınırlar.

20.9 Covariance Önizlemesi (Ders 20 Köprüsü)

Strang dersin sonunda yeni konuya — istatistik ve covariance matrisine — köprü kurar. Mean ve variance bilinen kavramlar; sıradaki adım covariance (değişkenler arası ilişki). Anahtar gerçek:

“…that covariance matrix… will be symmetric positive definite, or semidefinite.” — Strang, 51:36

Covariance matrisi her zaman simetrik ve pozitif yarı-tanımlıdır (Ders 5). Yarı-tanımlı (tekil) durum, değişkenler tam bağımlı olduğunda ortaya çıkar (Strang’ın benzetmesiyle: “birbirine yapıştırılmış paralar”). Bağımsız değişkenlerde köşegen, bağımlılıkta köşegen-dışı terimler dolar.

Bunu iki örnek gösterir (Şekil 20.7): solda bağımsız değişkenlerde covariance tam-rank PSD’dir (özdeğerler $[0.53, 1.95]$), elips iki yöne de açılır; sağda “yapıştırılmış paralar” ($y = 2x$) tam bağımlılığında covariance TEKİL olur ($\lambda_{\min} = 0$), elips bir doğruya çöker — $C = \begin{bmatrix} v & 2v \\ 2v & 4v \end{bmatrix}$ yapısı tam bağımlılığı kodlar.

Kod

X_ind, C_ind, X_dep, C_dep = covariance_demo()

fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4))

# Sol: bağımsız değişkenler — cov TAM-RANK
axL.scatter(X_ind[:, 0], X_ind[:, 1], s=8, color=COL_STEEL_300, alpha=0.7)
lam, Q = np.linalg.eigh(C_ind)
theta = np.linspace(0, 2 * np.pi, 100)
ell = Q @ np.diag(2 * np.sqrt(lam)) @ np.vstack([np.cos(theta), np.sin(theta)])
mu = X_ind.mean(axis=0)
axL.plot(ell[0] + mu[0], ell[1] + mu[1], color=COL_PRIMARY, lw=2)
axL.set_title("bağımsız: cov TAM-RANK (lambda [0.53, 1.95])", color=COL_TEXT, fontsize=11, fontweight="bold")
axL.set_aspect("equal")
apply_style(axL)

# Sağ: yapıştırılmış paralar (y = 2x) — cov TEKİL
axR.scatter(X_dep[:, 0], X_dep[:, 1], s=8, color=COL_VEC3, alpha=0.7)
xs = np.array([X_dep[:, 0].min(), X_dep[:, 0].max()])
axR.plot(xs, 2 * xs, color=COL_PRIMARY, lw=1)
axR.set_title("yapıştırılmış paralar (y = 2x): cov TEKIL (lambda_min = 0)", color=COL_TEXT, fontsize=11, fontweight="bold")
apply_style(axR)

fig.suptitle("Covariance önizlemesi (Ders 20 köprüsü): her cov simetrik PSD; tam bağımlılık = tekil durum",
             color=COL_TEXT, fontsize=12, fontweight="bold")

plt.show()

Şekil 20.7: Covariance önizlemesi (Ders 20 köprüsü): bağımsız değişkenlerde kovaryans matrisi tam-rank PSD (özdeğerler [0.53, 1.95]); ‘yapıştırılmış paralar’ (y = 2x) tam bağımlılığında kovaryans TEKİL olur (lambda_min = 0). Her kovaryans simetrik ve PSD’dir — bu da Ders 20’nin başlangıç noktasıdır.

Builder Notu — Yapıştırılmış Paralar

Covariance matrisinin pozitif yarı-tanımlı olması, tüm bu lineer cebir bloğunu istatistiğe bağlar: özdeğerleri varyans yönlerini (PCA, Ders 7), pozitif tanımlılığı geçerli bir olasılık yapısını garanti eder. ML köprüsü: Gauss dağılımı, Mahalanobis mesafesi, Kalman filtresi (Ders 14) ve PCA hep covariance matrisinin spektral yapısına dayanır — bir sonraki blok (istatistik → optimizasyon → derin öğrenme) buradan başlar.

20.10 Bu Dersin Özeti

Eyer = derin öğrenme: yüksek boyutta minimumdan çok eyer var; gradient descent’in eyerlerden kaçışı önemli.
Rayleigh örneği: $S = \mathrm{diag}(5,3,1)$ → maks 5 ($\lambda_{1}$, $e_{1}$), min 1 ($\lambda_{3}$, $e_{3}$), eyer 3 ($\lambda_{2}$, $e_{2}$).
Değerler = özdeğer, yerler = özvektör: Rayleigh’in tüm kritik noktaları özvektör. Uç özdeğerler kolay, ara (eyer) zor.
Eyer tanımı: gradyan $\nabla R = 0$ + Hessian belirsiz (karışık işaretli özdeğer).
Maxmin (Courant-Fischer): $\lambda_{k} = \max_{\dim V = k} \min_{x\in V} R(x)$. Örnekte $_{2} = $ max-min $= 3$.
Interlacing: maxmin’den düşer — $S$ perturbe/alt-matris olunca özdeğerler $\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$ arasına sıkışır. Weyl de aynı kaynaktan.
Covariance önizleme: simetrik pozitif (yarı-)tanımlı; yarı-tanımlı = tam bağımlı değişkenler (Ders 20).

Tek Bir Cümle

Bir simetrik matrisin aradaki özdeğerleri Rayleigh bölümünün eyer noktalarıdır ve maxmin ilkesiyle ($_{k} = $ boyut-$k$ alt-uzaylar üzerinde maks, alt-uzay içinde min) maks-min olarak yazılabilir — bu da interlacing teoremini doğrudan kanıtlar.

20.11 Kontrol Soruları

Soru 1: S = diag(5, 3, 1) için Rayleigh bölümünün maks, min ve eyer değerleri nedir, hangi vektörlerde

Cevap: Maks = 5, $x = (1,0,0)$ ($\lambda_{1}$, $e_{1}$); min = 1, $x = (0,0,1)$ ($\lambda_{3}$, $e_{3}$); eyer = 3, $x = (0,1,0)$ ($\lambda_{2}$, $e_{2}$). Değerler özdeğerler, yerler özvektörlerdir. Maks tüm ağırlığı en büyük köşegene (5), min en küçüğe (1), eyer ortadakine (3) yükleyince çıkar.

Soru 2: Bir kritik noktanın eyer olduğunu Hessian’dan nasıl anlarsın

Cevap: Eyerde gradyan $\nabla R = 0$ (tüm birinci türevler sıfır) ve Hessian (ikinci türev matrisi, simetrik) belirsizdir — özdeğerleri karışık işaretli. Minimumda Hessian pozitif tanımlı, maksimumda negatif tanımlı; eyerde hem pozitif hem negatif özdeğer var (bazı yönde yukarı, bazı yönde aşağı).

Soru 3: Maxmin (Courant-Fischer) ilkesiyle λ₂ nasıl yazılır

Cevap: $\lambda_{2} = \max_{\dim V = 2} \min_{0\neq x\in V} R(x)$: tüm 2-boyutlu alt-uzaylar $V$ üzerinde, her $V$ içinde Rayleigh’in minimumunu al, sonra bu minimumların maksimumunu al. Genel olarak $_{k} = $ boyut-$k$ alt-uzaylar üzerinde maks, alt-uzay içinde min. Eyer değerini iki kolay işlemin (min sonra maks) bileşimine indirger.

Soru 4: Maxmin ilkesi interlacing teoremini neden kolayca verir

Cevap: $_{k} = $ max-min yapısında bir kısıt eklemek ($S$’yi perturbe etmek veya bir satır+sütun atmak) alt-uzay seçim havuzunu daraltır/genişletir; bu, maks-min değerini sadece bir adım oynatabilir — ne çok yukarı ne çok aşağı. Sonuç: yeni özdeğerler eski özdeğerlerin arasına sıkışır, $\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$. Weyl eşitsizliği de aynı maxmin makinesinden gelir.

20.12 Egzersizler

Rayleigh kritik noktaları. $S = \mathrm{diag}(6, 4, 2)$. $R(x)$’in maks, min ve eyer değerlerini ve bunlara karşılık gelen vektörleri yaz. Eyer değeri hangi özdeğer? (İpucu: maks 6, min 2, eyer 4 = $\lambda_{2}$.)
2B minimum. $S = \mathrm{diag}(6, 4, 2)$, $V = \mathrm{span}\{e_{1}, e_{3}\}$ (yani $(u, 0, w)$ vektörleri). Bu $V$ üzerinde $R$’nin minimumunu bul. Maxmin yarışında bu $V$ kazanır mı ($\lambda_{2} = 4$ için)? (İpucu: $\mathrm{span}\{e_{1}, e_{3}\}$ min = 2; kazanmaz.)
Maxmin doğrulaması. Egzersiz 2’deki $S$ için, $\lambda_{2} = 4$’ü veren kazanan 2B alt-uzayı bul ve o uzaydaki minimumun 4 olduğunu göster. (İpucu: kazanan $\mathrm{span}\{e_{1}, e_{2}\}$, min = 4 = $\lambda_{2}$.)
Minimax dual. Maxmin’in ikizi minimax: $\lambda_{k} = \min_{\dim V = n-k+1} \max_{x\in V} R(x)$. $S = \mathrm{diag}(5,3,1)$ için $\lambda_{2}$’yi minimax formuyla (3-boyutta $n-k+1 = 2$ boyutlu uzaylar) hesapla; yine 3 çıktığını doğrula. Minimax ikizinin sayısal kanıtı (Şekil 20.4): 2000 rastgele 2B uzayın TÜM max’ları $\lambda_{2} = 3$’ün üstünde (min-of-maxs 3.000012), kazanan $\mathrm{span}\{q_{2}, q_{3}\}$ tam 3.0.
(Ders 20 habercisi) Bu derste covariance matrisinin simetrik pozitif yarı-tanımlı olduğunu gördük. Peki covariance matrisi tam olarak nasıl tanımlanır? Mean’den sapmaların hangi çarpımı? Ne zaman tekil (yarı-tanımlı) olur? Bir tahmin yaz — Ders 20 “tanımlar ve eşitsizlikler” (covariance, mean, variance) ile istatistik bloğunu açıyor.

20.13 Sonraki Ders İçin Hazırlık

Ders 20: Tanımlar ve Eşitsizlikler (Mean, Variance, Covariance). Lineer cebir bloğu kapandı; istatistik başlıyor. Strang covariance matrisini tanımlar (mean’den sapmaların dış-çarpım ortalaması), pozitif yarı-tanımlılığını kanıtlar ve temel olasılık eşitsizliklerini (Markov, Chebyshev) işler — PCA, Gauss dağılımı ve gradient descent’in (Ders 22+) istatistiksel temeli.

Ders 20 Öncesi Yapılacak

Bu dersin covariance önizlemesini (Şekil 20.7) gözden geçir: bağımsız değişkende cov tam-rank, tam bağımlılıkta (“yapıştırılmış paralar”, $y = 2x$) tekil ($\lambda_{\min} = 0$). Ders 20 bu PSD yapısını tanımdan kanıtlayacak — lineer cebir bloğunun (özdeğer/SVD/eyer/maxmin) istatistiğe açılan kapısı buradan başlıyor.

20.14 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
Eyer = derin öğrenme	gradient descent eyerden kaçış (Ders 22)	1m00
Rayleigh örneği	$S = \mathrm{diag}(5,3,1)$: maks 5, min 1, eyer 3	4m05
Değerler = özdeğer	kritik noktalar özvektör, değerler özdeğer	7m38
Eyer tanımı	$\nabla R = 0$ + Hessian belirsiz	8m10
Maxmin (Courant-Fischer)	$\lambda_{k} = \max_{\dim V=k} \min_{x\in V} R(x)$	10m38
Örnek $\lambda_{2} = 3$	$\mathrm{span}\{e_{1},e_{2}\}$ min = 3 = maks-min	12m08
Maxmin → interlacing	$\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$	11m31
Covariance önizleme	simetrik pozitif (yarı-)tanımlı	51m36

20.15 ML Bağlantıları Özeti

Eyer geometrisi: derin ağ kayıp yüzeyinde minimumdan çok eyer; SGD gürültüsü (Ders 25) ve negatif eğrilik yönleri eyerden kaçışı sağlar.
Maxmin / minimax: GAN (üretici-ayırıcı), adversarial/robust eğitim hep min-maks dengesi; Courant-Fischer bu yapının spektral kökeni.
Spektral graf / GCN (NYU paralel ders): graf Laplacian özdeğerleri maxmin ile tanımlanır; $\lambda_{2}$ (Fiedler değeri) graf bölme ve spektral kümelemenin (Ders 35) anahtarı; interlacing graf değişiminde spektrum kararlılığını sınırlar.
PCA köprüsü: maxmin “en iyi $k$-boyutlu alt-uzay” karakterizasyonu = Eckart-Young’ın (Ders 7) özdeğer ikizi; spektral gömme aynı iskelet.
İkinci-derece optimizasyon: Hessian özdeğer işaretleri (eyer mi minimum mu) Newton ve eyer-kaçış yöntemlerinin temeli (Ders 18 pivot/atalet).
Covariance → istatistik bloğu: pozitif yarı-tanımlı covariance (Ders 20), Gauss dağılımı, Kalman filtresi (Ders 14), PCA — sıradaki blok buradan başlar.
Geriye köprü: Ders 18 (Rayleigh, eyer, KKT), Ders 15 (interlacing), Ders 16 (Weyl), Ders 7 (Eckart-Young), Ders 5 (pozitif tanımlı).

Maks-Min Eyeri Çözer, İnterlacing’i Armağan Eder

“…write it as the maximum of a minimum.” — Strang, 10:38 — Eyer noktası, doğru alt-uzay seçildiğinde bir maks-min’e dönüşür; bu ilke ara özdeğerleri tanımlar, interlacing’i kanıtlar ve spektral graf yöntemlerinin kapısını açar.

--- title: "Eyer Noktaları (Devam), Maxmin İlkesi" subtitle: "Courant-Fischer maxmin ilkesi, interlacing kanıtı ve covariance köprüsü" --- ::: {.callout-note title="Bölüm bilgisi"} **Video:** [MIT 18.065 — Saddle Points Continued, Maxmin Principle](https://www.youtube.com/watch?v=2K7CvGnebO0) · **OCW:** Lecture 19 · **Okuma süresi:** ≈32 dk · **Konuşmacı:** Gilbert Strang · **Önkoşul:** Ders 18 (parametre sayımı, Rayleigh, eyer). Ders 18'in eyer noktası fikrini tamamlıyoruz. Çekirdek: **maxmin ilkesi** (Courant-Fischer) — aradaki bir özdeğeri (eyer değeri) bir **maks-min** olarak yaz. Bu, Ders 15'in **interlacing** teoremini doğrudan kanıtlar. Dersin sonu istatistiğe (covariance) köprü kurar; lineer cebir bloğu kapanıyor, istatistik bloğu başlıyor. ::: ```{python} #| echo: false """ _engine19.py — MIT 18.065 Ders 19 (Eyer Devam, Maxmin/Courant-Fischer, Interlacing Kanıtı) motor + viz. Setup hücresi = cat. Figür testi `from _engine19 import *`. matplotlib.use("Agg") burada YOK. """ import numpy as np import matplotlib.pyplot as plt from matplotlib.colors import LinearSegmentedColormap COL_PRIMARY = "#1f4e79"; COL_ACCENT = "#2e75b6"; COL_TEXT = "#13243a" COL_BG = "#eaf1f8"; COL_STEEL_300 = "#aac4dd"; COL_SKY_400 = "#6fa8dc" COL_WHITE = "#ffffff" COL_VEC1 = "#1f4e79"; COL_VEC2 = "#2e75b6"; COL_VEC3 = "#e67e22" COL_TEAL = "#17a2b8"; COL_PURPLE = "#6f42c1" NAVY_CMAP = LinearSegmentedColormap.from_list("strang_navy", ["#ffffff", "#cfe0f0", "#6fa8dc", "#2e75b6", "#1f4e79"]) DIVERGE = LinearSegmentedColormap.from_list("div", [COL_VEC3, "#ffffff", COL_PRIMARY]) def apply_style(ax): ax.set_facecolor(COL_WHITE); ax.grid(True, alpha=0.25, color=COL_STEEL_300, linewidth=0.8) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) ax.tick_params(colors=COL_TEXT); ax.title.set_color(COL_TEXT) ax.xaxis.label.set_color(COL_TEXT); ax.yaxis.label.set_color(COL_TEXT) return ax def heatmap(ax, M, title=None, cmap=None, annotate=True, fmt="{:.2g}", vmin=None, vmax=None, fontsize=11, text_thresh=None): M = np.asarray(M, dtype=float) if cmap is None: cmap = NAVY_CMAP if vmin is None: vmin = float(np.min(M)) if vmax is None: vmax = float(np.max(M)) if abs(vmax - vmin) < 1e-12: vmax = vmin + 1.0 ax.imshow(M, cmap=cmap, vmin=vmin, vmax=vmax, aspect="equal"); nr, nc = M.shape if text_thresh is None: text_thresh = vmin + 0.62*(vmax-vmin) if annotate and nr*nc <= 36: for i in range(nr): for j in range(nc): v = M[i, j] ax.text(j, i, fmt.format(v), ha="center", va="center", color=COL_WHITE if v >= text_thresh else COL_TEXT, fontsize=fontsize, fontweight="bold") ax.set_xticks(range(nc)); ax.set_yticks(range(nr)); ax.set_xticklabels([]); ax.set_yticklabels([]); ax.tick_params(length=0) for sp in ax.spines.values(): sp.set_color(COL_STEEL_300) if title: ax.set_title(title, color=COL_TEXT, fontsize=12, fontweight="bold") # ---- Ders 19 motoru: Rayleigh eyeri + maxmin/Courant-Fischer ---- S19 = np.diag([5.0, 3.0, 1.0]) # dersin ana örneği (D18 ile aynı) S19B = np.diag([6.0, 4.0, 2.0]) # Egz1-3 matrisi def rayleigh(S, x): """R(x) = xᵀSx / xᵀx.""" x = np.asarray(x, dtype=float) return float(x @ np.asarray(S, dtype=float) @ x / (x @ x)) def rayleigh_grad(S, x): """∇R(x) = 2(Sx − R(x)x)/xᵀx — özvektörlerde sıfır.""" S = np.asarray(S, dtype=float); x = np.asarray(x, dtype=float) return 2.0 * (S @ x - rayleigh(S, x) * x) / (x @ x) def rayleigh_hessian_numeric(S, x0, h=1e-5): """R'nin x0'daki sayısal Hessian'ı (merkez fark). Eyerde BELİRSİZ: q₂'de işaretler (+, 0, −) — radyal yön (R 0-homojen) 0 özdeğer verir.""" S = np.asarray(S, dtype=float); x0 = np.asarray(x0, dtype=float) n = len(x0); H = np.zeros((n, n)) for i in range(n): for j in range(n): ei = np.zeros(n); ei[i] = h ej = np.zeros(n); ej[j] = h H[i, j] = (rayleigh(S, x0 + ei + ej) - rayleigh(S, x0 + ei - ej) - rayleigh(S, x0 - ei + ej) + rayleigh(S, x0 - ei - ej)) / (4.0 * h * h) return (H + H.T) / 2.0 def orth_subspace(M): """Verilen kolonlardan ortonormal baz (QR).""" Q, _ = np.linalg.qr(np.asarray(M, dtype=float)) return Q def subspace_min(S, V): """min_{0≠x∈span(V)} R(x) = λ_min(VᵀSV) (V ortonormal kolonlar).""" V = np.asarray(V, dtype=float) return float(np.min(np.linalg.eigvalsh(V.T @ np.asarray(S, dtype=float) @ V))) def subspace_max(S, V): """max_{0≠x∈span(V)} R(x) = λ_max(VᵀSV).""" V = np.asarray(V, dtype=float) return float(np.max(np.linalg.eigvalsh(V.T @ np.asarray(S, dtype=float) @ V))) def maxmin_experiment(S, k=2, trials=2000, seed=7): """Courant-Fischer sayısal tanığı: rastgele boyut-k alt-uzaylarda min R dağılımı. Döner: (mins dizisi, λₖ, kazanan özvektör-uzayındaki min). Tüm min'ler ≤ λₖ; kazananda eşitlik.""" S = np.asarray(S, dtype=float); n = S.shape[0] lam = np.sort(np.linalg.eigvalsh(S))[::-1] rng = np.random.default_rng(seed) mins = np.array([subspace_min(S, orth_subspace(rng.standard_normal((n, k)))) for _ in range(trials)]) Q = np.linalg.eigh(S)[1][:, ::-1] # azalan özvektörler winner = subspace_min(S, Q[:, :k]) # span{q₁..qₖ} return mins, float(lam[k - 1]), float(winner) def minimax_experiment(S, k=2, trials=2000, seed=8): """Minimax ikizi (Egz4): λₖ = min_{dim V = n−k+1} max_{x∈V} R(x). Döner: (maxs dizisi, λₖ, kazanan uzaydaki max). Tüm max'lar ≥ λₖ; kazananda eşitlik.""" S = np.asarray(S, dtype=float); n = S.shape[0] lam = np.sort(np.linalg.eigvalsh(S))[::-1] d = n - k + 1 rng = np.random.default_rng(seed) maxs = np.array([subspace_max(S, orth_subspace(rng.standard_normal((n, d)))) for _ in range(trials)]) Q = np.linalg.eigh(S)[1][:, ::-1] winner = subspace_max(S, Q[:, k - 1:]) # span{qₖ..qₙ} return maxs, float(lam[k - 1]), float(winner) def interlace_submatrix(S): """Satır+sütun atma interlacing'i (maxmin kanıtının test ettiği eşitsizlik): λₖ(S) ≥ μₖ(Sₙ₋₁) ≥ λₖ₊₁(S). (λ, μ, zincir_ok) döner.""" S = np.asarray(S, dtype=float) lam = np.sort(np.linalg.eigvalsh(S))[::-1] mu = np.sort(np.linalg.eigvalsh(S[:-1, :-1]))[::-1] ok = all(lam[k] >= mu[k] - 1e-10 and mu[k] >= lam[k + 1] - 1e-10 for k in range(len(mu))) return lam, mu, bool(ok) def two_plane_sections(S, n_t=361): """Birim çember kesitleri: (u,v,0) düzlemi (maks 5 ↔ eyer 3) ve (0,v,w) düzlemi (eyer 3 ↔ min 1).""" S = np.asarray(S, dtype=float) th = np.linspace(0.0, 2.0 * np.pi, n_t) plane_uv = np.array([rayleigh(S, [np.cos(t), np.sin(t), 0.0]) for t in th]) plane_vw = np.array([rayleigh(S, [0.0, np.cos(t), np.sin(t)]) for t in th]) return th, plane_uv, plane_vw def covariance_demo(n=400, seed=12): """Covariance önizlemesi: bağımsız veri → tam-rank PSD cov; tam-bağımlı ('yapıştırılmış paralar': y = 2x) → TEKİL cov (λ_min ≈ 0).""" rng = np.random.default_rng(seed) X_ind = rng.standard_normal((n, 2)) * np.array([1.5, 0.7]) C_ind = np.cov(X_ind.T) x = rng.standard_normal(n) X_dep = np.column_stack([x, 2.0 * x]) # tam bağımlı C_dep = np.cov(X_dep.T) return X_ind, C_ind, X_dep, C_dep def cov_eig_summary(C): """(λ_min, λ_max, simetrik mi, PSD mi).""" C = np.asarray(C, dtype=float) lam = np.linalg.eigvalsh(C) return float(lam[0]), float(lam[-1]), bool(np.allclose(C, C.T)), bool(lam[0] > -1e-10) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d19} Bu ders Ders 18'in yarım kalan eyer tartışmasını kapatır ve dört sonuca yürür: önce somut bir Rayleigh örneğinde değerlerin nereden geldiğini görürüz, ardından her kritik noktanın bir özvektör (değeri bir özdeğer) olduğunu okuruz, sonra eyer değerini bir **maks-min** olarak yazan ilkeyi (Courant-Fischer) kurarız ve son olarak bu ilkeden **interlacing** kanıtının nasıl düştüğünü görürüz. Kapanışta covariance köprüsü açılır. Dört sonuç: 1. **Rayleigh örneği:** $S = \mathrm{diag}(5, 3, 1)$ için $R$'nin maks = 5 (özdeğer $\lambda_{1}$, özvektör $e_{1}$), min = 1 ($\lambda_{3}$, $e_{3}$), **eyer = 3** ($\lambda_{2}$, $e_{2}$). 2. **Değerler = özdeğer, yerler = özvektör:** Rayleigh'in tüm kritik noktaları özvektör, değerleri özdeğer. 3. **Maxmin ilkesi:** $\lambda_{k} = \max$ (boyut-$k$ alt-uzaylar $V$) $\min$ ($x \in V$) $R(x)$. Eyeri maks-min'e çevirir. 4. **Interlacing kanıtı:** maxmin'den, $S$ perturbe edilince veya bir satır+sütun atılınca özdeğerlerin neden içiçe geçtiği düşer. > *"...what happens if you have a saddle point or a degenerate minimum?"* — Strang, 1:00 (derin öğrenme motivasyonu) ```{mermaid} %%| label: fig-kavram-haritasi-l19 %%| fig-cap: "Ders 19 kavram haritasi: eyer noktalari ve maxmin ilkesi merkezde; Rayleigh ornegi, ozdeger-ozvektor okumasi, eyer tanimi, Courant-Fischer maxmin ve interlacing kaniti dallarda; NYU GCN koprusu ve covariance onizlemesi ayri dugumlerde." %%| echo: false flowchart TB M["Eyer noktalari + maxmin"] M --> R["Rayleigh ornegi diag(5,3,1): maks 5, min 1, EYER 3"] M --> V["degerler = ozdeger, yerler = ozvektor"] M --> S["eyer tanimi: gradyan 0 + Hessian belirsiz"] M --> C["maxmin (Courant-Fischer): lambda_k = max uzerinden min"] C --> I["maxmin -> interlacing kaniti (Ders 15)"] N["NYU koprusu: graf Laplacian / GCN / Fiedler lambda_2"] P["covariance onizleme: simetrik PSD (Ders 20)"] classDef center fill:#1f4e79,stroke:#163a5c,color:#ffffff,stroke-width:2px; classDef branch fill:#2e75b6,stroke:#1f4e79,color:#ffffff,stroke-width:1px; classDef side fill:#9dc3e6,stroke:#2e75b6,color:#11151c,stroke-width:1px; class M center; class R,V,S,C,I branch; class N,P side; ``` Kavram haritası (@fig-kavram-haritasi-l19) dersin omurgasını gösterir: merkezde eyer noktaları ve maxmin ilkesi, dallarda Rayleigh örneği, özdeğer-özvektör okuması, eyer tanımı ve Courant-Fischer'dan interlacing'e giden kanıt; yan düğümlerde NYU GCN köprüsü ve covariance önizlemesi. ::: {.callout-tip title="Builder Notu — Eyerden Maks-Min'e"} - **Eyer noktaları = derin öğrenmenin merkezi:** yüksek boyutlu kayıp yüzeyinde minimumdan çok eyer var; gradient descent'in (Ders 22) eyerlerden kaçışı başarının anahtarı. - **Maxmin (Courant-Fischer)** — ara özdeğerleri optimizasyon diliyle tanımlar; spektral graf teorisinin (NYU paralel ders, GCN) temeli. - **$\lambda_{2}$ = Fiedler değeri** — graf bölmenin (spektral kümeleme, Ders 35) anahtarı; maxmin ile karakterize edilir. - **Geriye köprü:** Ders 18 (Rayleigh, eyer, KKT), Ders 15 (interlacing), Ders 16 (Weyl), Ders 5 (pozitif tanımlı). ::: ## Eyer Noktaları Neden Önemli? {#sec-neden-onemli} Strang neden eyer noktalarına bu kadar yer ayırdığını açıklar: derin öğrenmenin kalbi, toplam maliyet fonksiyonunun minimumunu gradient descent ile bulmaktır. Ama yüksek boyutta her şey minimum değildir. > *"...what happens if you have a saddle point or a degenerate minimum?"* — Strang, 1:00 Maksimum ve minimumu biliyoruz; eyer noktaları daha bulanık. Derin öğrenmenin anlaşılması giderek "gradient descent ne üretiyor, eyerlerde ne oluyor?" sorusuna odaklanıyor. Bu yüzden eyeri netleştirmek şart. ::: {.callout-tip title="Builder Notu — Kayıp Yüzeyinin Çoğu Eyer"} Yüksek boyutlu kayıp yüzeylerinde kritik noktaların ezici çoğunluğu eyerdir — gerçek yerel minimum nadirdir. ML köprüsü: derin öğrenmenin "neden çalışıyor?" gizeminin büyük kısmı, SGD'nin (Ders 25) eyerlerden nasıl kaçtığıyla ilgili; eyer geometrisi optimizasyon teorisinin sıcak konusu. ::: ## Rayleigh Örneği: S = diag(5, 3, 1) {#sec-rayleigh-ornegi} Somut örnek. Köşegen (dolayısıyla simetrik) bir matris al — her simetrik matris ortogonal değişkene dönüştürülebileceğinden genelliği kaybetmeyiz. $x = (u, v, w)$, 3 boyut: $$R(x) = \frac{x^{T}Sx}{x^{T}x} = \frac{5u^{2} + 3v^{2} + w^{2}}{u^{2} + v^{2} + w^{2}}$$ Üç soru: maks, min ve eyer. **Maks** = 5: tüm ağırlığı $u$'ya yükle, $x = (1, 0, 0)$. **Min** = 1: her şeyi $w$'ye yükle, $x = (0, 0, 1)$. Birinci türevlerin sıfır olduğu **üçüncü** bir nokta daha var mı? Evet: $$\max R = 5\ \text{at}\ (1,0,0), \quad \min R = 1\ \text{at}\ (0,0,1), \quad \text{saddle } R = 3\ \text{at}\ (0,1,0)$$ Eyer değeri 3, orta noktada $(0, 1, 0)$. İki düzlem kesiti bunu görselleştirir (@fig-iki-duzlem): birim çemberi $(u,v,0)$ düzleminde gezdirirsen $R$ değerleri $[3, 5]$ arasında salınır (5 ile 3'ün arası); $(0,v,w)$ düzleminde ise $[1, 3]$ arasında. Eyer değeri **3, iki düzlemin ORTAK değeridir** — bir düzlemde maks, diğerinde min. İşte eyerin geometrik imzası budur. ```{python} #| label: fig-iki-duzlem #| fig-cap: "Rayleigh iki düzlemde: (u,v) kesiti [3,5], (v,w) kesiti [1,3] — eyer 3 ikisinin kesişimi (maks bir düzlemde min diğerinde)" #| fig-width: 8 #| fig-height: 4.2 #| code-fold: true th, puv, pvw = two_plane_sections(S19) fig, ax = plt.subplots(figsize=(8, 4.2)) ax.plot(th, puv, color=COL_PRIMARY, lw=2, label="(u,v,0) düzlemi: 5 ile 3 arası") ax.plot(th, pvw, color=COL_VEC3, lw=2, label="(0,v,w) düzlemi: 3 ile 1 arası") ax.axhline(5, color=COL_STEEL_300, ls="--", lw=1.2) ax.axhline(1, color=COL_STEEL_300, ls="--", lw=1.2) ax.axhline(3, color=COL_TEAL, ls="--", lw=1.8, label="eyer = 3: iki düzlemin ORTAK değeri") ax.set_xlabel("theta (birim çember)") ax.set_ylabel("R(x)") ax.legend() ax.set_title("Rayleigh iki düzlemde: (u,v) kesiti [3,5], (v,w) kesiti [1,3] — eyer 3 ikisinin kesişimi") apply_style(ax) plt.show() ``` ::: {.callout-tip title="Builder Notu — Önce Köşegenleştir Sonra Oku"} Rayleigh bölümünü köşegen $S$ ile incelemek tüm genelliği korur (Ders 18): herhangi simetrik $S$, ortogonal bir değişken dönüşümüyle köşegen hâle gelir, $R$'nin maks/min/eyer yapısı değişmez. Bu "önce köşegenleştir, sonra oku" stratejisi spektral analizin standart ilk hamlesidir. ::: ## Değerler = Özdeğer, Yerler = Özvektör {#sec-deger-yer} Rayleigh bölümünün kritik noktalarının (birinci türevin sıfır olduğu yerler) tümü $S$'nin özvektörleridir; oradaki değerler özdeğerlerdir: > *"The values there are the eigenvalues. And the places where you reach them are the eigenvectors."* — Strang, 7:38 Örnekte: maks 5 = $\lambda_{1}$ ($e_{1}$), min 1 = $\lambda_{3}$ ($e_{3}$), eyer 3 = $\lambda_{2}$ ($e_{2}$). Rayleigh karmaşık bir fonksiyon (türevi için bölüm kuralı veya Lagrange çarpanı gerek), ama sonucu kusursuz: değerler özdeğer, yerler özvektör. Pratik not: en büyük ve en küçük özvektörü hesaplamak, **aradaki** (eyer) özvektörleri hesaplamaktan genelde çok daha kolaydır. İki düzlem kesiti (@fig-iki-duzlem) bunu da gösterir: tepe değer 5 ile dip değer 1, eğrilerin uç noktalarında (özvektör doğrultularında) okunur; eyer değeri 3 ise iki düzlemin ortak noktasıdır. ::: {.callout-tip title="Builder Notu — Uçlar Kolay Ara Zor"} "Uç özdeğerler kolay, ara özdeğerler zor" gerçeği sayısal lineer cebirin temel asimetrisidir: power iteration en büyüğü bulur, ama $\lambda_{2}$'yi (Fiedler) bulmak deflation/Lanczos ister. ML köprüsü: spektral kümeleme (Ders 35) tam da $\lambda_{2}$ özvektörüne (Fiedler vektörü) ihtiyaç duyar — bu yüzden iyi kodlar ve dikkat gerektirir. ::: ## Eyer = Gradyan 0, Hessian Belirsiz {#sec-eyer-tanimi} Eyer noktası iki koşulla tanımlanır. (1) Birinci türevler (gradyan vektörü) sıfır: $$\nabla R = \left(\frac{\partial R}{\partial u}, \frac{\partial R}{\partial v}, \frac{\partial R}{\partial w}\right) = 0$$ (2) İkinci türevler — $3\times 3$ bir matris (Hessian). Karışık türevler eşit olduğundan ($\partial^{2}R/\partial u\,\partial v = \partial^{2}R/\partial v\,\partial u$) bu matris **simetrik**: $$H = \begin{bmatrix} R_{uu} & R_{uv} & R_{uw} \\ R_{vu} & R_{vv} & R_{vw} \\ R_{wu} & R_{wv} & R_{ww} \end{bmatrix}$$ Maksimumda $H$ negatif tanımlı, minimumda pozitif tanımlı, **eyerde belirsiz** (karışık işaretli özdeğerler) — bazı yönlerde yukarı, bazılarında aşağı. Üç kritik noktada sayısal Hessian'ı (merkez fark) hesaplayıp özdeğerlerine bakınca işaret deseni netleşir (@fig-hessian-isaretleri): maks $q_{1}$'de $[-8, -4, 0] \leq 0$ (negatif-tanımlı), min $q_{3}$'te $[0, 4, 8] \geq 0$ (pozitif-tanımlı), eyer $q_{2}$'de ise $[-4, 0, +4]$ — işaretler **karışık**. Buradaki 0 özdeğer radyal yöndendir: $R$ ölçekten bağımsız (0-homojen) olduğundan o yönde değişmez. Sınıflandırmayı yapan tam da bu işaret desenidir. ```{python} #| label: fig-hessian-isaretleri #| fig-cap: "Üç kritik noktanın sayısal Hessian özdeğerleri (merkez fark). Maksimum (q₁) negatif-tanımlı [−8, −4, 0], minimum (q₃) pozitif-tanımlı [0, 4, 8], eyer (q₂) ise işaretleri karışık [−4, 0, +4] — sınıflandırmayı yapan tam da bu işaret deseni." #| fig-width: 10 #| fig-height: 3.6 #| code-fold: true H1 = rayleigh_hessian_numeric(S19, np.array([1., 0., 0.])) H2 = rayleigh_hessian_numeric(S19, np.array([0., 1., 0.])) H3 = rayleigh_hessian_numeric(S19, np.array([0., 0., 1.])) eig1 = np.sort(np.linalg.eigvalsh(H1)) eig2 = np.sort(np.linalg.eigvalsh(H2)) eig3 = np.sort(np.linalg.eigvalsh(H3)) fig, axes = plt.subplots(1, 3, figsize=(10, 3.6)) panels = [ (axes[0], eig1, "q1 (maks): [-8, -4, 0] <= 0"), (axes[1], eig2, "q2 (EYER): [-4, 0, +4] KARISIK"), (axes[2], eig3, "q3 (min): [0, 4, 8] >= 0"), ] for ax, eig, title in panels: cols = [] for v in eig: if abs(v) < 1e-3: cols.append(COL_STEEL_300) elif v > 0: cols.append(COL_PRIMARY) else: cols.append(COL_VEC3) xpos = np.arange(len(eig)) ax.bar(xpos, eig, color=cols, edgecolor=COL_TEXT, linewidth=0.7, width=0.6) ax.axhline(0.0, color=COL_TEXT, linewidth=0.9) ax.set_xticks(xpos) ax.set_xticklabels(["ozdeger 1", "ozdeger 2", "ozdeger 3"], fontsize=8) ax.set_ylim(-9.5, 9.5) ax.set_title(title, color=COL_TEXT, fontsize=10, fontweight="bold") for x, v in zip(xpos, eig): off = 0.5 if v >= 0 else -0.5 va = "bottom" if v >= 0 else "top" ax.text(x, v + off, "{:.0f}".format(v), ha="center", va=va, color=COL_TEXT, fontsize=9, fontweight="bold") apply_style(ax) axes[0].set_ylabel("Hessian ozdegeri", color=COL_TEXT) fig.suptitle("Hessian kritik noktayi siniflar: maks negatif-tanimli, min pozitif-tanimli, EYER belirsiz (0 = radyal yon, R olcekten bagimsiz)", fontsize=10.5, color=COL_TEXT) fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` ::: {.callout-tip title="Builder Notu — İşaretler Kritik Noktayı Sınıflar"} Hessian'ın tanımlılığı bir kritik noktayı sınıflar: pozitif tanımlı = minimum, negatif tanımlı = maksimum, belirsiz = eyer (Ders 5 + Ders 18 pivot/atalet testi). ML köprüsü: ikinci-derece optimizasyon (Newton) ve eyer-kaçış yöntemleri Hessian'ın özdeğer işaretlerine bakar; derin ağ eğitiminde negatif eğrilik (negative curvature) yönleri eyerden çıkış kapısıdır. ::: ## Maxmin İlkesi (Courant-Fischer) {#sec-maxmin} Eyer için en güzel fikir: onu bir **maksimum-minimum** olarak yaz, böylece maks/min'in kolaylığına geri dön. > *"...write it as the maximum of a minimum."* — Strang, 10:38 İkinci özdeğer $\lambda_{2}$ için: tüm **2-boyutlu** alt-uzaylar $V$ üzerinde, her $V$ içinde Rayleigh'in minimumunu al, sonra bu minimumların maksimumunu al: $$\lambda_{2} = \max_{\dim V = 2}\ \min_{0 \neq x \in V}\ R(x)$$ Genel hâli (Courant-Fischer): $k$'inci özdeğer, boyut-$k$ alt-uzaylar üzerinde maks-min: $$\lambda_{k} = \max_{\dim V = k}\ \min_{0 \neq x \in V}\ \frac{x^{T}Sx}{x^{T}x}$$ > *"...I'm going to take a maximum over two dimensional spaces..."* — Strang, 12:08 Bu, sayısal olarak doğrudan doğrulanabilir (@fig-maxmin-deney): 2000 rastgele 2B alt-uzayda Rayleigh'in minimumu hesaplanır; **hepsi $\lambda_{2} = 3$'ün altında** kalır (max-of-mins 2.999999) ve eşitlik yalnız özvektör uzayında ($\mathrm{span}\{q_{1}, q_{2}\}$) sağlanır. Aynı ilkenin ayna ikizi minimax'tır (@fig-minimax-dual, Egz4): $n-k+1$ boyutlu rastgele uzayların **TÜM max değerleri $\lambda_{2} = 3$'ün üstünde** (min-of-maxs 3.000012); kazanan $\mathrm{span}\{q_{2}, q_{3}\}$ tam 3.0 verir. ```{python} #| label: fig-minimax-dual #| fig-cap: "Minimax ikizi (Egz4): n-k+1 boyutlu rastgele uzaylarin TUM max degerleri lambda_2 = 3 un ustunde (min-of-maxs 3.000012) — maxmin ilkesinin ayna simetrisi." #| fig-width: 7 #| fig-height: 4 #| code-fold: true maxs, lam2b, winner_mm = minimax_experiment(S19, k=2, trials=2000) fig, ax = plt.subplots(figsize=(7, 4)) ax.hist(maxs, bins=60, color=COL_ACCENT, alpha=0.9) ax.axvline(3.0, color=COL_VEC3, linewidth=2.6) ax.annotate("lambda_2 = 3 (hicbir V altina inemez)", xy=(3.0, ax.get_ylim()[1] * 0.92), xytext=(3.15, ax.get_ylim()[1] * 0.92), color=COL_VEC3, fontsize=9, fontweight="bold", va="center") ax.annotate("kazanan: span{q2,q3} -> max = 3.0", xy=(3.0, ax.get_ylim()[1] * 0.55), xytext=(3.15, ax.get_ylim()[1] * 0.55), color=COL_PRIMARY, fontsize=9, arrowprops=dict(arrowstyle="->", color=COL_PRIMARY), va="center") ax.set_xlabel("max R (V icinde)") ax.set_ylabel("frekans") ax.set_title("Minimax ikizi (Egz4): rastgele uzaylarin TUM max degerleri 3 un ustunde\n" "(min-of-maxs 3.000012) — maxmin in ayna simetrisi", fontsize=10) apply_style(ax) fig.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Zoru İki Kolaya Böl"} Maxmin, eyer noktasını (zor) iki kolay işlemin (min, sonra maks) bileşimine indirger — optimizasyonun klasik "minimax" yapısı (Ders 24 oyun teorisi/LP ile akraba). ML köprüsü: GAN'lar (üretici-ayırıcı) tam bir minimax problemidir; robust optimizasyon, adversarial eğitim hep maks-min/min-maks dengesi arar. Courant-Fischer bu yapının spektral kökenidir. ::: ## Örnek Hesap: λ₂ = 3 {#sec-ornek-hesap} İlkeyi örnekte çalıştır ($S = \mathrm{diag}(5, 3, 1)$, $\lambda_{2} = 3$ bekliyoruz). $V = \mathrm{span}\{e_{1}, e_{2}\}$ al, yani $(u, v, 0)$ vektörleri ($w = 0$). Bu 2B uzayda Rayleigh: $$R = \frac{5u^{2} + 3v^{2}}{u^{2} + v^{2}} \;\Rightarrow\; \min = 3 \ (\text{tum agirlik } v)$$ Bu $V$ için min = 3. Şimdi maks: başka bir $V$ denersek, örn. $\mathrm{span}\{e_{2}, e_{3}\} = (0, v, w)$ vektörleri: $$R = \frac{3v^{2} + w^{2}}{v^{2} + w^{2}} \;\Rightarrow\; \min = 1$$ Bu $V$'nin minimumu 1 — daha küçük, kazanan değil. Tüm 2B uzaylar üzerinde minimumların maksimumu 3'tür (en iyi seçim $\mathrm{span}\{e_{1}, e_{2}\}$). Yani $\lambda_{2} = $ max-min $= 3$. ✓ Sayısal deney bunu tam onaylar (@fig-maxmin-deney): solda 2000 rastgele 2B alt-uzayın min'leri histogramda hep $\lambda_{2} = 3$'ün altında toplanır (hiçbir $V$ geçemez); sağda iki örnek $V$ — $\mathrm{span}\{e_{1}, e_{2}\}$ min = 3 (kazanan) ile $\mathrm{span}\{e_{2}, e_{3}\}$ min = 1 karşılaştırılır. ```{python} #| label: fig-maxmin-deney #| fig-cap: "Courant-Fischer maxmin SAYISAL KANIT: 2000 rastgele 2B alt-uzayın TÜM min değerleri λ₂ = 3'ün altında (max-of-mins 2.999999); eşitlik yalnız özvektör uzayında. Sağda iki örnek: span{e₁,e₂} → min = 3 (kazanan), span{e₂,e₃} → min = 1." #| fig-width: 10 #| fig-height: 4.2 #| code-fold: true fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4.2)) # --- Sol: maxmin deneyi histogramı --- mins, lam2, winner = maxmin_experiment(S19, k=2, trials=2000) axL.hist(mins, bins=60, color=COL_PRIMARY, alpha=0.9) axL.axvline(3.0, color=COL_VEC3, linewidth=3.0, label="lambda_2 = 3 (hicbir V gecemez)") axL.annotate("kazanan: span{q1,q2} -> min = 3.0 birebir", xy=(winner, 0.0), xytext=(0.30, 0.82), textcoords="axes fraction", fontsize=9, color=COL_TEXT, arrowprops=dict(arrowstyle="->", color=COL_TEAL, lw=1.4)) axL.set_xlabel("min R (V icinde)") axL.set_ylabel("frekans (2000 rastgele 2B alt-uzay)") axL.legend(loc="upper left", fontsize=8) apply_style(axL) # --- Sag: iki ornek V bar --- v_e12 = subspace_min(S19, np.eye(3)[:, :2]) # span{e1,e2} -> 3 v_e23 = subspace_min(S19, np.eye(3)[:, 1:]) # span{e2,e3} -> 1 xs = [0, 1] axR.bar(xs[0], v_e12, width=0.55, color=COL_PRIMARY, label="span{e1,e2}") axR.bar(xs[1], v_e23, width=0.55, color=COL_ACCENT, label="span{e2,e3}") axR.axhline(3.0, color=COL_VEC3, linewidth=2.0, linestyle="--", label="lambda_2 = 3") axR.set_xticks(xs) axR.set_xticklabels(["span{e1,e2}", "span{e2,e3}"]) axR.set_ylabel("min R (V icinde)") axR.legend(loc="upper right", fontsize=8) apply_style(axR) fig.suptitle("Courant-Fischer SAYISAL KANIT: 2000 rastgele alt-uzayin TUM min leri " "lambda_2 = 3 un altinda (max-of-mins 2.999999); esitlik yalniz ozvektor uzayinda", fontsize=9, color=COL_TEXT) fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` ::: {.callout-tip title="Builder Notu — Kazanan Alt-Uzay Özvektörlerin"} "Doğru alt-uzayı seç, minimumu maksimize et" hesabı, maxmin'in neden tam $\lambda_{2}$'yi verdiğini somutlaştırır: en iyi 2B uzay, ilk iki özvektörün gerdiği uzaydır ve oradaki min tam $\lambda_{2}$'dir. ML köprüsü: bu, PCA'nın "en iyi $k$-boyutlu alt-uzay" karakterizasyonunun (Ders 7 Eckart-Young) özdeğer ikizidir — alt-uzay optimizasyonu ve spektral gömme aynı maxmin iskeletini paylaşır. ::: ## Maxmin → Interlacing Kanıtı {#sec-interlacing-d19} Maxmin ilkesi sadece şık bir tanım değil — Ders 15'in **interlacing** teoremini doğrudan üretir: > *"...would lead you... very quickly to the interlacing theorem..."* — Strang, 11:31 Sezgi: $\lambda_{k} = \max_{\dim V = k} \min_{x\in V} R(x)$. Şimdi $S$'yi perturbe et (rank-1 ekle) veya bir satır+sütun at (alt-matris, Ders 15). Kısıtlama, alt-uzay seçim havuzunu daraltır veya genişletir; ama maks-min bir adım kayar. Örneğin bir satır+sütun atmak, alt-uzayları bir boyut daha kısıtlar — yeni $\lambda$'lar eski $\lambda$'ların **arasına** sıkışır: $$\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$$ Çünkü min-üzerinden-max yapısında bir kısıt eklemek değeri ne çok yukarı ne çok aşağı oynatabilir — tam interlacing. Ders 16'nın Weyl eşitsizliği de aynı maxmin makinesinden gelir. Sayı doğrusu üzerinde bu içiçe geçiş açıkça görünür (@fig-interlacing-maxmin): $4\times 4$ rastgele simetrik bir $S$ için özdeğerler $\lambda = [2.886, 0.927, -0.812, -1.341]$, son satır+sütun atılınca elde edilen $3\times 3$ alt-matrisin özdeğerleri $\mu = [2.886, 0.311, -1.146]$ — her $\mu_{k}$ tam olarak $\lambda_{k}$ ile $\lambda_{k+1}$ arasına sıkışır. 50 rastgele matriste ihlal sayısı 0. ```{python} #| label: fig-interlacing-maxmin #| fig-cap: "Maxmin -> interlacing: satir+sutun atinca mu lar lambda larin ARASINA siksir (lambda_k >= mu_k >= lambda_k+1) — 50 rastgele matriste ihlal 0." #| fig-width: 8 #| fig-height: 3.4 #| code-fold: true rng = np.random.default_rng(3) B = rng.standard_normal((4, 4)); S4 = (B + B.T) / 2 lam, mu, okc = interlace_submatrix(S4) fig, ax = plt.subplots(figsize=(8, 3.4)) # gri ince kesik dikey baglar: her mu_k, lambda_k ve lambda_{k+1} arasina sikisir for k in range(len(mu)): ax.plot([lam[k], lam[k]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1) ax.plot([lam[k + 1], lam[k + 1]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1) ax.plot([mu[k], mu[k]], [0, 1], color=COL_STEEL_300, ls="--", lw=0.8, zorder=1) # lambda (S): y=1, navy yuvarlak ax.scatter(lam, np.ones_like(lam), s=80, color=COL_PRIMARY, marker="o", zorder=3, edgecolors=COL_WHITE, linewidths=0.8) for v in lam: ax.annotate(f"{v:.3f}", (v, 1), textcoords="offset points", xytext=(0, 9), ha="center", fontsize=8, color=COL_TEXT) # mu (satir+sutun atilmis): y=0, steel kare ax.scatter(mu, np.zeros_like(mu), s=80, color=COL_ACCENT, marker="s", zorder=3, edgecolors=COL_WHITE, linewidths=0.8) for v in mu: ax.annotate(f"{v:.3f}", (v, 0), textcoords="offset points", xytext=(0, -16), ha="center", fontsize=8, color=COL_TEXT) ax.set_ylim(-0.5, 1.5) ax.set_yticks([0, 1]) ax.set_yticklabels(["mu (satir+sutun atilmis)", "lambda (S)"]) ax.set_title("Maxmin -> interlacing: mu lar lambda larin ARASINA sikisir " "(lambda_k >= mu_k >= lambda_k+1) — 50 rastgele matriste ihlal 0", fontsize=9.5) apply_style(ax) plt.show() ``` ::: {.callout-tip title="Builder Notu — Bir İlke İki Teorem"} Maxmin'in interlacing'i "ücretsiz" üretmesi, doğru soyutlamanın gücüdür: tek bir ilke (Courant-Fischer) hem özdeğer tanımını hem perturbasyon teoremlerini verir. ML köprüsü: NYU paralel dersinin spektral graf evrişim ağları (GCN), graf Laplacian'ının özdeğerlerini kullanır; bu özdeğerler maxmin ile tanımlanır ve graf değişince (kenar ekle/çıkar) interlacing onların nasıl kayacağını sınırlar — dinamik/gürültülü graflarda GCN kararlılığının teorik temeli. **NYU H13 GCN (konuk Bresson):** graf Laplacian özdeğerleri maxmin ile tanımlanır; $\lambda_{2}$ = Fiedler değeri spektral kümelemenin anahtarı; interlacing dinamik graflarda spektrum kararlılığını sınırlar. ::: ## Covariance Önizlemesi (Ders 20 Köprüsü) {#sec-covariance-d19} Strang dersin sonunda yeni konuya — istatistik ve **covariance matrisi**ne — köprü kurar. Mean ve variance bilinen kavramlar; sıradaki adım covariance (değişkenler arası ilişki). Anahtar gerçek: > *"...that covariance matrix... will be symmetric positive definite, or semidefinite."* — Strang, 51:36 Covariance matrisi her zaman simetrik ve pozitif yarı-tanımlıdır (Ders 5). Yarı-tanımlı (tekil) durum, değişkenler **tam bağımlı** olduğunda ortaya çıkar (Strang'ın benzetmesiyle: "birbirine yapıştırılmış paralar"). Bağımsız değişkenlerde köşegen, bağımlılıkta köşegen-dışı terimler dolar. Bunu iki örnek gösterir (@fig-covariance-onizleme): solda bağımsız değişkenlerde covariance tam-rank PSD'dir (özdeğerler $[0.53, 1.95]$), elips iki yöne de açılır; sağda "yapıştırılmış paralar" ($y = 2x$) tam bağımlılığında covariance **TEKİL** olur ($\lambda_{\min} = 0$), elips bir doğruya çöker — $C = \begin{bmatrix} v & 2v \\ 2v & 4v \end{bmatrix}$ yapısı tam bağımlılığı kodlar. ```{python} #| label: fig-covariance-onizleme #| fig-cap: "Covariance önizlemesi (Ders 20 köprüsü): bağımsız değişkenlerde kovaryans matrisi tam-rank PSD (özdeğerler [0.53, 1.95]); 'yapıştırılmış paralar' (y = 2x) tam bağımlılığında kovaryans TEKİL olur (lambda_min = 0). Her kovaryans simetrik ve PSD'dir — bu da Ders 20'nin başlangıç noktasıdır." #| fig-width: 10 #| fig-height: 4 #| code-fold: true X_ind, C_ind, X_dep, C_dep = covariance_demo() fig, (axL, axR) = plt.subplots(1, 2, figsize=(10, 4)) # Sol: bağımsız değişkenler — cov TAM-RANK axL.scatter(X_ind[:, 0], X_ind[:, 1], s=8, color=COL_STEEL_300, alpha=0.7) lam, Q = np.linalg.eigh(C_ind) theta = np.linspace(0, 2 * np.pi, 100) ell = Q @ np.diag(2 * np.sqrt(lam)) @ np.vstack([np.cos(theta), np.sin(theta)]) mu = X_ind.mean(axis=0) axL.plot(ell[0] + mu[0], ell[1] + mu[1], color=COL_PRIMARY, lw=2) axL.set_title("bağımsız: cov TAM-RANK (lambda [0.53, 1.95])", color=COL_TEXT, fontsize=11, fontweight="bold") axL.set_aspect("equal") apply_style(axL) # Sağ: yapıştırılmış paralar (y = 2x) — cov TEKİL axR.scatter(X_dep[:, 0], X_dep[:, 1], s=8, color=COL_VEC3, alpha=0.7) xs = np.array([X_dep[:, 0].min(), X_dep[:, 0].max()]) axR.plot(xs, 2 * xs, color=COL_PRIMARY, lw=1) axR.set_title("yapıştırılmış paralar (y = 2x): cov TEKIL (lambda_min = 0)", color=COL_TEXT, fontsize=11, fontweight="bold") apply_style(axR) fig.suptitle("Covariance önizlemesi (Ders 20 köprüsü): her cov simetrik PSD; tam bağımlılık = tekil durum", color=COL_TEXT, fontsize=12, fontweight="bold") plt.show() ``` ::: {.callout-tip title="Builder Notu — Yapıştırılmış Paralar"} Covariance matrisinin pozitif yarı-tanımlı olması, tüm bu lineer cebir bloğunu istatistiğe bağlar: özdeğerleri varyans yönlerini (PCA, Ders 7), pozitif tanımlılığı geçerli bir olasılık yapısını garanti eder. ML köprüsü: Gauss dağılımı, Mahalanobis mesafesi, Kalman filtresi (Ders 14) ve PCA hep covariance matrisinin spektral yapısına dayanır — bir sonraki blok (istatistik → optimizasyon → derin öğrenme) buradan başlar. ::: ## Bu Dersin Özeti {#sec-ozet-d19} - **Eyer = derin öğrenme:** yüksek boyutta minimumdan çok eyer var; gradient descent'in eyerlerden kaçışı önemli. - **Rayleigh örneği:** $S = \mathrm{diag}(5,3,1)$ → maks 5 ($\lambda_{1}$, $e_{1}$), min 1 ($\lambda_{3}$, $e_{3}$), eyer 3 ($\lambda_{2}$, $e_{2}$). - **Değerler = özdeğer, yerler = özvektör:** Rayleigh'in tüm kritik noktaları özvektör. Uç özdeğerler kolay, ara (eyer) zor. - **Eyer tanımı:** gradyan $\nabla R = 0$ + Hessian belirsiz (karışık işaretli özdeğer). - **Maxmin (Courant-Fischer):** $\lambda_{k} = \max_{\dim V = k} \min_{x\in V} R(x)$. Örnekte $\lambda_{2} = $ max-min $= 3$. - **Interlacing:** maxmin'den düşer — $S$ perturbe/alt-matris olunca özdeğerler $\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$ arasına sıkışır. Weyl de aynı kaynaktan. - **Covariance önizleme:** simetrik pozitif (yarı-)tanımlı; yarı-tanımlı = tam bağımlı değişkenler (Ders 20). ::: {.callout-important title="Tek Bir Cümle"} Bir simetrik matrisin aradaki özdeğerleri Rayleigh bölümünün eyer noktalarıdır ve maxmin ilkesiyle ($\lambda_{k} = $ boyut-$k$ alt-uzaylar üzerinde maks, alt-uzay içinde min) maks-min olarak yazılabilir — bu da interlacing teoremini doğrudan kanıtlar. ::: ## Kontrol Soruları {#sec-sorular-d19} ::: {.callout-note title="Soru 1: S = diag(5, 3, 1) için Rayleigh bölümünün maks, min ve eyer değerleri nedir, hangi vektörlerde" collapse="true"} **Cevap:** Maks = 5, $x = (1,0,0)$ ($\lambda_{1}$, $e_{1}$); min = 1, $x = (0,0,1)$ ($\lambda_{3}$, $e_{3}$); eyer = 3, $x = (0,1,0)$ ($\lambda_{2}$, $e_{2}$). Değerler özdeğerler, yerler özvektörlerdir. Maks tüm ağırlığı en büyük köşegene (5), min en küçüğe (1), eyer ortadakine (3) yükleyince çıkar. ::: ::: {.callout-note title="Soru 2: Bir kritik noktanın eyer olduğunu Hessian'dan nasıl anlarsın" collapse="true"} **Cevap:** Eyerde gradyan $\nabla R = 0$ (tüm birinci türevler sıfır) **ve** Hessian (ikinci türev matrisi, simetrik) **belirsizdir** — özdeğerleri karışık işaretli. Minimumda Hessian pozitif tanımlı, maksimumda negatif tanımlı; eyerde hem pozitif hem negatif özdeğer var (bazı yönde yukarı, bazı yönde aşağı). ::: ::: {.callout-note title="Soru 3: Maxmin (Courant-Fischer) ilkesiyle λ₂ nasıl yazılır" collapse="true"} **Cevap:** $\lambda_{2} = \max_{\dim V = 2} \min_{0\neq x\in V} R(x)$: tüm 2-boyutlu alt-uzaylar $V$ üzerinde, her $V$ içinde Rayleigh'in minimumunu al, sonra bu minimumların maksimumunu al. Genel olarak $\lambda_{k} = $ boyut-$k$ alt-uzaylar üzerinde maks, alt-uzay içinde min. Eyer değerini iki kolay işlemin (min sonra maks) bileşimine indirger. ::: ::: {.callout-note title="Soru 4: Maxmin ilkesi interlacing teoremini neden kolayca verir" collapse="true"} **Cevap:** $\lambda_{k} = $ max-min yapısında bir kısıt eklemek ($S$'yi perturbe etmek veya bir satır+sütun atmak) alt-uzay seçim havuzunu daraltır/genişletir; bu, maks-min değerini sadece bir adım oynatabilir — ne çok yukarı ne çok aşağı. Sonuç: yeni özdeğerler eski özdeğerlerin arasına sıkışır, $\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$. Weyl eşitsizliği de aynı maxmin makinesinden gelir. ::: ## Egzersizler {#sec-egzersizler-d19} 1. **Rayleigh kritik noktaları.** $S = \mathrm{diag}(6, 4, 2)$. $R(x)$'in maks, min ve eyer değerlerini ve bunlara karşılık gelen vektörleri yaz. Eyer değeri hangi özdeğer? *(İpucu: maks 6, min 2, eyer 4 = $\lambda_{2}$.)* 2. **2B minimum.** $S = \mathrm{diag}(6, 4, 2)$, $V = \mathrm{span}\{e_{1}, e_{3}\}$ (yani $(u, 0, w)$ vektörleri). Bu $V$ üzerinde $R$'nin minimumunu bul. Maxmin yarışında bu $V$ kazanır mı ($\lambda_{2} = 4$ için)? *(İpucu: $\mathrm{span}\{e_{1}, e_{3}\}$ min = 2; kazanmaz.)* 3. **Maxmin doğrulaması.** Egzersiz 2'deki $S$ için, $\lambda_{2} = 4$'ü veren kazanan 2B alt-uzayı bul ve o uzaydaki minimumun 4 olduğunu göster. *(İpucu: kazanan $\mathrm{span}\{e_{1}, e_{2}\}$, min = 4 = $\lambda_{2}$.)* 4. **Minimax dual.** Maxmin'in ikizi minimax: $\lambda_{k} = \min_{\dim V = n-k+1} \max_{x\in V} R(x)$. $S = \mathrm{diag}(5,3,1)$ için $\lambda_{2}$'yi minimax formuyla (3-boyutta $n-k+1 = 2$ boyutlu uzaylar) hesapla; yine 3 çıktığını doğrula. Minimax ikizinin sayısal kanıtı (@fig-minimax-dual): 2000 rastgele 2B uzayın TÜM max'ları $\lambda_{2} = 3$'ün üstünde (min-of-maxs 3.000012), kazanan $\mathrm{span}\{q_{2}, q_{3}\}$ tam 3.0. 5. **(Ders 20 habercisi)** Bu derste covariance matrisinin simetrik pozitif yarı-tanımlı olduğunu gördük. Peki covariance matrisi tam olarak nasıl tanımlanır? Mean'den sapmaların hangi çarpımı? Ne zaman tekil (yarı-tanımlı) olur? Bir tahmin yaz — Ders 20 "tanımlar ve eşitsizlikler" (covariance, mean, variance) ile istatistik bloğunu açıyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d19} **Ders 20: Tanımlar ve Eşitsizlikler (Mean, Variance, Covariance).** Lineer cebir bloğu kapandı; istatistik başlıyor. Strang covariance matrisini tanımlar (mean'den sapmaların dış-çarpım ortalaması), pozitif yarı-tanımlılığını kanıtlar ve temel olasılık eşitsizliklerini (Markov, Chebyshev) işler — PCA, Gauss dağılımı ve gradient descent'in (Ders 22+) istatistiksel temeli. ::: {.callout-warning title="Ders 20 Öncesi Yapılacak"} Bu dersin covariance önizlemesini (@fig-covariance-onizleme) gözden geçir: bağımsız değişkende cov tam-rank, tam bağımlılıkta ("yapıştırılmış paralar", $y = 2x$) tekil ($\lambda_{\min} = 0$). Ders 20 bu PSD yapısını tanımdan kanıtlayacak — lineer cebir bloğunun (özdeğer/SVD/eyer/maxmin) istatistiğe açılan kapısı buradan başlıyor. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d19} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **Eyer = derin öğrenme** | gradient descent eyerden kaçış (Ders 22) | 1m00 | | **Rayleigh örneği** | $S = \mathrm{diag}(5,3,1)$: maks 5, min 1, eyer 3 | 4m05 | | **Değerler = özdeğer** | kritik noktalar özvektör, değerler özdeğer | 7m38 | | **Eyer tanımı** | $\nabla R = 0$ + Hessian belirsiz | 8m10 | | **Maxmin (Courant-Fischer)** | $\lambda_{k} = \max_{\dim V=k} \min_{x\in V} R(x)$ | 10m38 | | **Örnek $\lambda_{2} = 3$** | $\mathrm{span}\{e_{1},e_{2}\}$ min = 3 = maks-min | 12m08 | | **Maxmin → interlacing** | $\lambda_{k}(S) \geq \mu_{k}(S_{n-1}) \geq \lambda_{k+1}(S)$ | 11m31 | | **Covariance önizleme** | simetrik pozitif (yarı-)tanımlı | 51m36 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d19} - **Eyer geometrisi:** derin ağ kayıp yüzeyinde minimumdan çok eyer; SGD gürültüsü (Ders 25) ve negatif eğrilik yönleri eyerden kaçışı sağlar. - **Maxmin / minimax:** GAN (üretici-ayırıcı), adversarial/robust eğitim hep min-maks dengesi; Courant-Fischer bu yapının spektral kökeni. - **Spektral graf / GCN (NYU paralel ders):** graf Laplacian özdeğerleri maxmin ile tanımlanır; $\lambda_{2}$ (Fiedler değeri) graf bölme ve spektral kümelemenin (Ders 35) anahtarı; interlacing graf değişiminde spektrum kararlılığını sınırlar. - **PCA köprüsü:** maxmin "en iyi $k$-boyutlu alt-uzay" karakterizasyonu = Eckart-Young'ın (Ders 7) özdeğer ikizi; spektral gömme aynı iskelet. - **İkinci-derece optimizasyon:** Hessian özdeğer işaretleri (eyer mi minimum mu) Newton ve eyer-kaçış yöntemlerinin temeli (Ders 18 pivot/atalet). - **Covariance → istatistik bloğu:** pozitif yarı-tanımlı covariance (Ders 20), Gauss dağılımı, Kalman filtresi (Ders 14), PCA — sıradaki blok buradan başlar. - **Geriye köprü:** Ders 18 (Rayleigh, eyer, KKT), Ders 15 (interlacing), Ders 16 (Weyl), Ders 7 (Eckart-Young), Ders 5 (pozitif tanımlı). ::: {.callout-important title="Maks-Min Eyeri Çözer, İnterlacing'i Armağan Eder"} > *"...write it as the maximum of a minimum."* — Strang, 10:38 — Eyer noktası, doğru alt-uzay seçildiğinde bir maks-min'e dönüşür; bu ilke ara özdeğerleri tanımlar, interlacing'i kanıtlar ve spektral graf yöntemlerinin kapısını açar. :::