31 ImageNet bir CNN’dir, Evrişim Kuralı

AlexNet devrimi, evrişim = polinom çarpımı, özdeğerlerin çarpıldığı kural ve Kronecker ile iki boyut

Bölüm bilgisi

Bu ders sirkülant/Fourier’i (Ders 30-31) evrişime ve CNN’lere taşır. Strang’in Ders 32 videosu (≈47 dk) ve OCW Lecture 32 (≈32 dk okuma) temel alınmıştır. Önkoşul Ders 30-31 (sirkülant/Fourier/FFT) ve Ders 26 (sinir ağı yapısı).

31.1 Bu Derste Ne Var?

Ders 30-31’in sirkülant/Fourier fikrini evrişime ve görüntülere taşıyoruz. Evrişim (convolution) = polinom çarpımı; evrişim kuralı Fourier ile evrişimi çarpmaya çevirir; CNN’ler bu yapıyı görüntüye uygular.

Beş sonuç:

ImageNet/AlexNet (2012): Krizhevsky-Sutskever-Hinton; CNN %15 hata (2.’lik %26) — derin öğrenme devrimi. CNN az ağırlık (paylaşım).
Evrişim tanımı: $(c * d)_{k} = \sum_{i+j=k} c_{i}\,d_{j}$; polinom çarpımından gelir. Fonksiyon: $(f * g)(x) = \int f(t)\,g(x-t)\,dt$.
Evrişim kuralı: sirkülant CD’nin özdeğerleri = $\lambda(C) \odot \lambda(D)$ (bileşen-bileşen); $F(c \circledast d) = (Fc) \odot (Fd)$.
FFT iki yol: ya evriş→dönüştür ($O(n^2)$), ya ayrı-dönüştür→çarp ($2n\log n + n$). FFT ikincisini hızlı kılar.
2B + Kronecker: 2B evrişim çift-integral; Kronecker çarpımı (1B→2B), Laplacian = Kron(A,I)+Kron(I,A) (Kronecker toplamı).

“…the MATLAB command is Kron.” — Strang, 38:55

flowchart TD
    C["Evrisim kurali:<br/>F(c conv d) = (Fc) . (Fd)"]

    C --> A["AlexNet 2012:<br/>CNN yuzde 15 hata (devrim)"]
    C --> P["evrisim = polinom carpimi<br/>(usler i+j=k)"]
    C --> I["fonksiyon evrisimi:<br/>integral f(t) g(x-t) dt"]
    C --> L["ozdegerler carpilir:<br/>lambda(CD) = lambda(C) . lambda(D)"]
    C --> Y["iki yol: evris-donustur<br/>vs donustur-carp (FFT kazanir)"]
    C --> D2["2B evrisim<br/>(CNN conv katmani)"]
    C --> KR["Kronecker: Kron(A,B);<br/>Laplacian = Kron(A,I)+Kron(I,A)"]

    K1["D30-31 sirkulant / Fourier / FFT"]
    K2["D33 ogrenme fonksiyonu (sonraki)"]
    K3["fast.ai L15 im2col / NYU H6 /<br/>Karpathy makemore CNN"]

    K1 --> C
    L --> K2
    D2 --> K3

    classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff;
    classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff;
    classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330;
    classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff;

    class C merkez;
    class A,P,I,L,Y,D2,KR dal;
    class K1 vec;
    class K2,K3 teal;

Şekil 31.1: Ders 32 kavram haritasi: evrisim kurali F(c conv d) = (Fc) . (Fd) sirkulantlari ortak Fourier tabaninda kosegenlestirir, kosegenler carpilir. Yedi dal: AlexNet 2012 CNN yuzde 15 hata (ImageNet devrimi); evrisim = polinom carpimi (usler i+j=k toplanir); fonksiyon evrisimi integral f(t) g(x-t) dt; ozdegerler carpilir lambda(CD) = lambda(C) . lambda(D); iki yol evris-sonra-donustur vs donustur-sonra-carp (FFT kazanir, buyuk-tamsayi/kriptografi); 2B evrisim = CNN conv katmani; Kronecker Kron(A,B) 1B yapiyi 2B ye tasir, Laplacian = Kron(A,I)+Kron(I,A). Koprular: D30-31 sirkulant/Fourier/FFT, D33 ogrenme fonksiyonu (sonraki), fast.ai L15 im2col / NYU H6 / Karpathy makemore CNN.

Şekil 31.1 dersin iskeletini gösterir: merkezdeki evrişim kuralı $F(c \circledast d) = (Fc) \odot (Fd)$ fikrinden yedi dala ayrılır — AlexNet 2012 (CNN %15 hata, ImageNet devrimi), evrişim = polinom çarpımı (üsler $i+j=k$), fonksiyon evrişimi $\int f(t)\,g(x-t)\,dt$, özdeğerler çarpılır $\lambda(CD) = \lambda(C) \odot \lambda(D)$, iki yol (evriş-dönüştür vs dönüştür-çarp, FFT kazanır), 2B evrişim (CNN conv katmanı) ve Kronecker Kron(A,B) + Laplacian = Kron(A,I)+Kron(I,A); köprü düğümleri D30-31 (sirkülant/Fourier/FFT), D33 öğrenme fonksiyonu (sonraki) ve fast.ai L15 im2col / NYU H6 / Karpathy makemore CNN dalları önceki ile sonraki derslere bağlar.

Builder Notu — Sinyal İşleme Derin Öğrenmeyle Buluşunca

CNN = ağırlık paylaşımı: AlexNet 60M parametre, 5 conv + 3 tam-bağlı, max pooling, dropout; konvolüsyon tam matrisi küçük filtreye indirir.
Evrişim kuralı + FFT: büyük evrişimleri F-dönüştür-çarp-geri-dön ile $O(n \log n)$’de yap; büyük-tamsayı çarpımı, ses, FFT-conv.
Kronecker = 2B yapı: 1B matrislerden 2B (görüntü) matrisi; 2B Fourier = Kron(F,F), 2B Laplacian = Kronecker toplamı.
Geriye köprü: Ders 30-31 (sirkülant/cyclic convolution/Fourier/FFT), Ders 4 (özdeğer çarpımı). Paralel: fast.ai L15 (conv2d/im2col), NYU H6 (CNN), Karpathy makemore CNN.

Tek cümle: Evrişim polinom çarpımıdır; evrişim kuralı (Fourier’de çarpmaya döner) FFT ile evrişimi hızlandırır; CNN’ler bu evrişimi (ağırlık paylaşımıyla) görüntüye uygular, 2B’ye geçiş Kronecker çarpımıyla yapılır.

31.2 1. ImageNet ve AlexNet (2012)

Derin öğrenmenin dönüm noktası: Krizhevsky-Sutskever-Hinton’ın 2012 ImageNet yarışması makalesi (AlexNet).

“We trained a large deep convolutional neural network.” — Strang, 2:33

1.2 milyon görüntü, 2 GPU’da 5 gün eğitim. Sonuç: top-5 test hatası %15 (ikinci takım %26) — devrim niteliğinde. Ağ: 60 milyon parametre, 5 konvolüsyon katmanı + 3 tam-bağlı katman, max pooling (boyut indirme), dropout (aşırı-öğrenme önleme). Kritik: CNN az ağırlık kullanır — tam matris yerine sadece üst-satır (filtre) ağırlıkları (Ders 31 ağırlık paylaşımı).

Kod

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

# --- Sol panel: ImageNet 2012 top-5 hata bar (AlexNet 15 vs 2. takim 26) ---
vals = [15, 26]
cols = [COL_PRIMARY, COL_VEC3]
xpos = np.arange(2)
axL.bar(xpos, vals, color=cols, width=0.6, edgecolor=COL_WHITE, linewidth=1.4)
for i, v in enumerate(vals):
    axL.text(xpos[i], v + 0.7, "%{}".format(v), ha="center", va="bottom",
             fontsize=13, fontweight="bold", color=cols[i])
apply_style(axL)
axL.set_xticks(xpos); axL.set_xticklabels(["AlexNet (CNN)", "2. takim"], fontsize=11)
axL.set_ylabel("top-5 hata (%)")
axL.set_ylim(0, 30)
axL.set_title("AlexNet devrimi (2012)", fontsize=12, fontweight="bold")

# --- Sag panel: AlexNet mimari serit (8 kutu: 5 conv navy + 3 fc turuncu) ---
conv_names = ["conv1", "conv2", "conv3", "conv4", "conv5"]
fc_names = ["fc6", "fc7", "fc8"]
names = conv_names + fc_names
colors = [COL_PRIMARY] * 5 + [COL_VEC3] * 3
pool_after = {0, 1, 4}  # conv1, conv2, conv5 sonrasi pool

n_box = 8
bw = 0.085          # kutu genisligi (axes fraction)
gap = 0.025         # kutular arasi bosluk
x0 = 0.04           # sol baslangic
by = 0.50           # kutu dikey merkez
bh = 0.30           # kutu yuksekligi
for k in range(n_box):
    x = x0 + k * (bw + gap)
    axR.add_patch(plt.Rectangle((x, by - bh / 2), bw, bh, fc=colors[k], ec=COL_WHITE,
                                lw=1.6, transform=axR.transAxes, zorder=2))
    axR.text(x + bw / 2, by, names[k], ha="center", va="center", fontsize=8.5,
             color=COL_WHITE, fontweight="bold", rotation=90, transform=axR.transAxes, zorder=3)
    if k in pool_after:
        axR.text(x + bw / 2, by - bh / 2 - 0.05, "pool", ha="center", va="top",
                 fontsize=7.5, color=COL_TEXT, transform=axR.transAxes, zorder=3)

# kutular arasi oklar
for k in range(n_box - 1):
    xa = x0 + k * (bw + gap) + bw
    xb = x0 + (k + 1) * (bw + gap)
    axR.annotate("", xy=(xb, by), xytext=(xa, by), xycoords="axes fraction",
                 arrowprops=dict(arrowstyle="-|>", color=COL_ACCENT, lw=1.4))

# altta tarihsel metin
axR.text(0.5, 0.10, "60M parametre, 1.2M goruntu, 2 GPU x 5 gun, dropout",
         ha="center", va="center", fontsize=9.5, color=COL_PRIMARY, fontweight="bold",
         transform=axR.transAxes)
axR.set_xlim(0, 1); axR.set_ylim(0, 1)
axR.axis("off")

fig.suptitle("ImageNet 2012: derin ogrenme devriminin tetigi — CNN agirlik "
             "paylasimiyla az agirlik, yuzde 15 vs 26",
             fontsize=11.5, color=COL_PRIMARY, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.93])
plt.show()

Şekil 31.2: AlexNet’in 2012 ImageNet zaferi — derin öğrenme devriminin tetiği. Sol: top-5 hata, AlexNet (CNN) %15 (navy) vs ikinci takım %26 (turuncu); on bir puanlık fark bir CNN’in eseri. Sağ: AlexNet mimari şeridi — 8 katman zinciri, 5 evrişim katmanı (conv1..conv5, navy) + 3 tam bağlı katman (fc6..fc8, turuncu), conv1/conv2/conv5 sonrası max pool. 60M parametre, 1.2M görüntü, 2 GPU × 5 gün, dropout: ağırlık paylaşımı sayesinde derin ama az ağırlıklı.

Şekil 31.2 2012 sıçramasını iki panelde toplar: solda top-5 hata barı — AlexNet (CNN) %15 (navy) ile ikinci takım %26 (turuncu) arasındaki on bir puanlık fark tek bir CNN’in eseridir; sağda AlexNet mimari şeridi — sekiz katman zinciri, 5 evrişim katmanı (conv1..conv5, navy) + 3 tam-bağlı katman (fc6..fc8, turuncu), conv1/conv2/conv5 sonrası max pool, altta 60M parametre, 1.2M görüntü, 2 GPU × 5 gün, dropout. Ağırlık paylaşımı sayesinde ağ derin ama az ağırlıklıdır.

Builder Notu — On Beşe Karşı Yirmi Altı

“AlexNet 2012 = derin öğrenme devriminin tetiği” ML tarihinin dönüm noktası. ML köprüsü: %15 vs %26 sıçraması (ve sonraki yıllarda hızla düşmesi) CNN’in görüntü tanımayı dönüştürdüğünü kanıtladı; dropout, ReLU, GPU eğitimi bu makaleyle yaygınlaştı. Sutskever sonra OpenAI’ı kurdu — bu makale modern AI’ın başlangıç noktalarından.

31.3 2. Evrişim Tanımı: Polinom Çarpımı

Evrişim (convolution) iki vektörü “kaydır-çarp-topla” ile birleştirir. k’ıncı bileşen, indisleri k’ya toplanan tüm çarpımların toplamı:

“…index i plus j adds to k.” — Strang, 6:04

\[(c * d)_{k} = \sum_{i+j=k} c_{i}\,d_{j} = \sum_{i} c_{i}\,d_{k-i}\]

Nereden gelir? Polinom çarpımından. c’yi ($c_0 + c_1 x + \dots$) ve d’yi ($d_0 + d_1 x + \dots$) polinom say, çarp; $x^k$’nin katsayısı tam bu toplamdır (üsler $i + j = k$ toplanır). Evrişim = polinom çarpımının katsayıları.

Kod

fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10.5, 4))

# ---- Sol: kaydır-çarp-topla şeması ----
ax0.set_xlim(0, 10); ax0.set_ylim(0, 10); ax0.axis("off")
ax0.set_title("kaydir-carp-topla: d=(1,1) TERS kayan pencere", color=COL_TEXT, fontsize=11, fontweight="bold")

c = [1, 2, 3]
# üstte c=(1,2,3) üç navy kutu
for idx, ci in enumerate(c):
    x = 1.0 + idx * 1.0
    ax0.add_patch(plt.Rectangle((x, 8.6), 0.9, 0.8, facecolor=COL_PRIMARY, edgecolor=COL_WHITE, lw=1.2))
    ax0.text(x + 0.45, 9.0, str(ci), ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold")
ax0.text(0.7, 9.0, "c=", ha="right", va="center", color=COL_TEXT, fontsize=10, fontweight="bold")

# altta d=(1,1) TERS çevrilmiş turuncu pencere, k=0..3 dört konumda (dikeyde 4 sıra)
results = ["k=0: 1*1=1", "k=1: 1*1+2*1=3", "k=2: 2*1+3*1=5", "k=3: 3*1=3"]
sc = 0.55  # küçük ölçek
row_y = [7.2, 5.6, 4.0, 2.4]
for k in range(4):
    y = row_y[k]
    base = 1.0 + (k - 1) * 1.0
    for w in range(2):
        x = base + w * sc * 1.0
        ax0.add_patch(plt.Rectangle((x, y), sc * 0.9, sc * 0.9, facecolor=COL_VEC3, edgecolor=COL_WHITE, lw=1.0))
        ax0.text(x + sc * 0.45, y + sc * 0.45, "1", ha="center", va="center", color=COL_WHITE, fontsize=8, fontweight="bold")
    ax0.text(5.3, y + sc * 0.45, results[k], ha="left", va="center", color=COL_TEXT, fontsize=9, fontweight="bold")

# ---- Sağ: bar (1,3,5,3) ----
coeffs = poly_mult_coeffs(c, [1, 1])  # motor: (1,3,5,3)
xs = np.arange(4)
ax1.bar(xs, coeffs, color=COL_PRIMARY, edgecolor=COL_WHITE, width=0.62)
for xi, ci in zip(xs, coeffs):
    ax1.text(xi, ci + 0.12, f"{ci:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold")
ax1.set_xticks(xs); ax1.set_xticklabels(["x^0", "x^1", "x^2", "x^3"])
ax1.set_ylim(0, 6)
ax1.text(1.5, 5.6, "(1 + 2x + 3x^2)(1 + x)", ha="center", va="center", color=COL_TEXT, fontsize=11, fontweight="bold")
ax1.set_title("katsayilar = evrisim (motor BIREBIR)", color=COL_TEXT, fontsize=12, fontweight="bold")
apply_style(ax1)

fig.suptitle("Evrisim = polinom carpimi: usler i+j=k toplanir — (1,2,3) conv (1,1) = (1,3,5,3)",
             color=COL_TEXT, fontsize=12, fontweight="bold")
fig.tight_layout(rect=[0, 0, 1, 0.94])
plt.show()

Şekil 31.3: Evrisim = polinom carpimi: usler i+j=k toplanir — (1,2,3) conv (1,1) = (1,3,5,3)

Şekil 31.3 tanımı iki açıdan somutlaştırır: solda kaydır-çarp-topla şeması — c=(1,2,3) üç navy kutu, altında d=(1,1) ters çevrilmiş turuncu kayan pencere dört konumda (k=0..3), her konumda örtüşen çarpımların toplamı sağda yazılı (k=0: 1, k=1: 3, k=2: 5, k=3: 3); sağda polinom karşılığı — $(1 + 2x + 3x^2)(1 + x)$ çarpımının katsayıları bar olarak (1,3,5,3) ($x^0, x^1, x^2, x^3$ üsleri), poly_mult_coeffs motoruyla birebir. Evrişim ile polinom çarpımı aynı sayıyı verir — üsler $i+j=k$ toplandığı için.

Builder Notu — Kaydır Çarp Topla

“Evrişim = polinom çarpımı” sinyal işlemenin cebirsel kökeni. ML köprüsü: CNN’deki konvolüsyon katmanı tam bu kaydır-çarp-topla; bir filtre (çekirdek) görüntü üzerinde kaydırılır, her konumda nokta-çarpım. fast.ai L15 im2col bu evrişimi büyük matris çarpımına açar (GPU verimliliği için).

31.4 3. Fonksiyon Evrişimi

Aynı fikir sürekli fonksiyonlarda — toplam yerine integral:

“…f star g at x.” — Strang, 10:02

\[(f * g)(x) = \int f(t)\, g(x - t)\, dt\]

Vektör evrişiminin sürekli karşılığı: $c_i \to f(t)$, $d_{k-i} \to g(x-t)$, toplam → integral. g, ters çevrilip kaydırılır ($x-t$); t değiştikçe kayma miktarı değişir — bir filtrenin tam yaptığı şey. (Daire koymadım: bu sıradan/döngüsüz evrişim; periyodik fonksiyonlarda döngüsel olur.)

Builder Notu — Ters Çevirip Kaydırmak

“Fonksiyon evrişimi = ters çevir, kaydır, çarp, integre et” sinyal işlemenin sürekli dili. ML köprüsü: filtreleme (sinyal/görüntü), olasılıkta iki bağımsız değişkenin toplamının dağılımı (yoğunlukların evrişimi), ve sürekli CNN’ler/Gauss bulanıklaştırma hep bu integral. Ters-çevirme, evrişimi korelasyondan ayıran detaydır (CNN’ler aslında çapraz-korelasyon kullanır).

31.5 4. Evrişim Kuralı: Özdeğerler Çarpılır

Ders 30-31’i birleştir. İki sirkülant C, D çarpılınca CD yine sirkülanttır; köşegenleri $c \circledast d$ (döngüsel evrişim). CD’nin özdeğerleri ne? Sirkülantlar değişmeli ve aynı özvektörleri (Fourier) paylaştığından:

“…the eigenvalues just multiply.” — Strang, 28:52

\[\lambda(CD) = \lambda(C) \odot \lambda(D) \quad (\text{bilesen-bilesen carpim})\]

Özdeğerler bileşen-bileşen (MATLAB .*, Hadamard çarpımı) çarpılır. Özdeğerler = ilk kolonun Fourier dönüşümü olduğundan (Ders 31), bu şu demek: $c \circledast d$’nin Fourier dönüşümü = (c’nin Fourier’i) $\odot$ (d’nin Fourier’i). Zaman uzayında evrişim → frekans uzayında çarpma. Şekil 31.4 bu kuralı ve aşağıdaki iki yolu (§5) tek figürde doğrular.

Builder Notu — Köşegenler Çarpılır

“Evrişimin özdeğerleri çarpılır” konvolüsyon teoreminin spektral ispatı: sirkülantlar ortak özvektör (Fourier) tabanında köşegenleşir, köşegenler (özdeğerler) çarpılır. ML köprüsü: bu, evrişimi frekans uzayında nokta-çarpıma çeviren temel teorem; ses (spektrogram), görüntü filtreleme ve FFT-tabanlı konvolüsyon hep buna dayanır.

31.6 5. İki Yol: Evrişim Kuralı + FFT

Evrişim kuralı (C kuralı) aynı sonuca iki yol verir:

“…Convolve then transform by F. Or transform separately by F.” — Strang, 30:50

\[F(c \circledast d) = (Fc) \odot (Fd)\]

Yol 1: önce evriş ($c \circledast d$), sonra Fourier’le dönüştür. Yol 2: her birini ayrı dönüştür ($Fc$, $Fd$), sonra bileşen-bileşen çarp. İkisi aynı sonuç. Neden önemli? Çünkü Fourier dönüşümü FFT ile çok hızlı ($O(n \log n)$). FFT’nin varlığı, Yol 2’yi çok cazip kılar.

Kod

fig, (ax0, ax1, ax2) = plt.subplots(1, 3, figsize=(12, 4.2))

# --- Sol: ozdegerler carpilir ---
rng = np.random.default_rng(32)
c4 = rng.uniform(-2, 2, 4); d4 = rng.uniform(-2, 2, 4)
F = fourier_matrix(4)
C = circulant(c4); D = circulant(d4)
lamCD = np.abs(np.diag(np.linalg.solve(F, (C @ D) @ F)))
lamprod = np.abs(np.diag(np.linalg.solve(F, C @ F)) * np.diag(np.linalg.solve(F, D @ F)))
x = np.arange(4)
ax0.bar(x - 0.18, lamCD, width=0.36, color=COL_PRIMARY, label=r"$\lambda(CD)$")
ax0.bar(x + 0.18, lamprod, width=0.36, color=COL_VEC3, label=r"$\lambda(C)\cdot\lambda(D)$")
ax0.set_title("özdeğerler çarpılır (defect 1.8e-15)", color=COL_TEXT, fontsize=11, fontweight="bold")
ax0.set_xticks(x); ax0.set_xticklabels([f"$\\lambda_{i}$" for i in range(4)])
ax0.set_ylabel("|özdeğer|"); ax0.legend(fontsize=8)
apply_style(ax0)

# --- Orta: iki yol akis semasi ---
ax1.set_xlim(0, 10); ax1.set_ylim(0, 10); ax1.axis("off")

def kutu(ax, cx, cy, w, h, text, color):
    ax.add_patch(plt.Rectangle((cx - w/2, cy - h/2), w, h, facecolor=color,
                               edgecolor=COL_TEXT, linewidth=1.3, alpha=0.92))
    ax.text(cx, cy, text, ha="center", va="center", color=COL_WHITE,
            fontsize=8.5, fontweight="bold")

def ok(ax, x0, x1, y, color):
    ax.annotate("", xy=(x1, y), xytext=(x0, y),
                arrowprops=dict(arrowstyle="-|>", color=color, lw=1.8))

# ust zincir (navy) — evris yolu
uy = 7.2
kutu(ax1, 1.7, uy, 1.8, 1.1, "c, d", COL_PRIMARY)
kutu(ax1, 4.6, uy, 2.1, 1.1, "evriş:\nc conv d", COL_PRIMARY)
kutu(ax1, 7.6, uy, 1.9, 1.1, "F ile\ndönüştür", COL_PRIMARY)
ok(ax1, 2.6, 3.55, uy, COL_PRIMARY)
ok(ax1, 5.65, 6.65, uy, COL_PRIMARY)
# alt zincir (turuncu) — donustur-carp yolu
ay = 2.8
kutu(ax1, 1.7, ay, 1.8, 1.1, "c, d", COL_VEC3)
kutu(ax1, 4.6, ay, 2.1, 1.1, "Fc, Fd\nayrı", COL_VEC3)
kutu(ax1, 7.6, ay, 2.1, 1.1, "bileşen\nçarp", COL_VEC3)
ok(ax1, 2.6, 3.55, ay, COL_VEC3)
ok(ax1, 5.65, 6.55, ay, COL_VEC3)
# bulusma kutusu
kutu(ax1, 9.0, 5.0, 1.5, 1.3, "AYNI\nsonuç", COL_TEAL)
ax1.annotate("", xy=(9.0, 5.65), xytext=(8.55, uy - 0.55),
             arrowprops=dict(arrowstyle="-|>", color=COL_TEXT, lw=1.6))
ax1.annotate("", xy=(9.0, 4.35), xytext=(8.65, ay + 0.55),
             arrowprops=dict(arrowstyle="-|>", color=COL_TEXT, lw=1.6))
ax1.set_title("iki yol → tek sonuç", color=COL_TEXT, fontsize=11, fontweight="bold")

# --- Sag: Egz2 sifir-evrisim ---
F2 = fourier_matrix(2)
Fc = np.abs(F2 @ np.array([1.0, 1.0]))    # (2, 0)
Fd = np.abs(F2 @ np.array([1.0, -1.0]))   # (0, 2)
xb = np.arange(2)
ax2.bar(xb - 0.18, Fc, width=0.36, color=COL_PRIMARY, label="Fc = (2, 0)")
ax2.bar(xb + 0.18, Fd, width=0.36, color=COL_VEC3, label="Fd = (0, 2)")
ax2.set_title("Egz2: c conv d = (0,0), iki yol aynı", color=COL_TEXT, fontsize=11, fontweight="bold")
ax2.set_xticks(xb); ax2.set_xticklabels(["frek 0", "frek 1"])
ax2.set_ylim(0, 2.6); ax2.legend(fontsize=8)
ax2.annotate("ayrık frekanslar → çarpım (0,0)", xy=(0.5, 2.25), ha="center",
             fontsize=8.5, color=COL_TEXT, fontweight="bold")
apply_style(ax2)

fig.suptitle(r"Evrişim kuralı $F(c \circledast d) = (Fc)\cdot(Fd)$: sirkülantlar ortak Fourier tabanında köşegenleşir, köşegenler çarpılır",
             fontsize=12.5, fontweight="bold", color=COL_TEXT)
fig.tight_layout(rect=[0, 0, 1, 0.95])
plt.show()

Şekil 31.4: Evrişim kuralı $F(c \circledast d) = (Fc)\cdot(Fd)$ üç açıdan. Sol: rastgele $c_4, d_4$ (seed 32) için $\lambda(CD)$ ile $\lambda(C)\cdot\lambda(D)$ çubukları üst üste oturur — ortak Fourier tabanında köşegenler bileşen-bileşen çarpılır, defect 1.8e-15. Orta: iki güzergah aynı sonuca varır — üstte evriş yapıp dönüştür, altta önce dönüştürüp bileşen-bileşen çarp. Sağ: Egz2 sıfır-evrişim — $c=(1,1)$ ve $d=(1,-1)$ ayrık frekanslarda yaşar, $Fc=(2,0)$ ile $Fd=(0,2)$ çakışmaz, çarpımları (0,0) olur ve $c \circledast d = (0,0)$ çıkar.

Şekil 31.4 dersin amiral görselidir ve kuralı üç açıdan doğrular: solda rastgele $c_4, d_4$ (seed 32) için $\lambda(CD)$ (navy) ile $\lambda(C) \odot \lambda(D)$ (turuncu) barları üst üste oturur — ortak Fourier tabanında köşegenler bileşen-bileşen çarpılır, defect yalnızca 1.8e-15 (n=4; n=8 için <1e-10); ortada iki güzergah aynı sonuca varır — üst yol (navy) evriş yapıp F ile dönüştürür, alt yol (turuncu) önce ayrı dönüştürüp bileşen-bileşen çarpar, ikisi “AYNI sonuç”ta buluşur; sağda Egz2 sıfır-evrişim — $c=(1,1)$ ile $d=(1,-1)$ ayrık frekanslarda yaşar, $Fc=(2,0)$ ile $Fd=(0,2)$ çakışmaz, çarpımları (0,0) olur ve $c \circledast d = (0,0)$ çıkar (iki yol da aynı sıfırı verir — conv_rule_defect Strang F konvansiyonuyla D30 örneği (3,1,2)/(4,6,1) için de <1e-10).

Builder Notu — Aynı Hedefe İki Güzergah

“İki yol: evriş-sonra-dönüştür vs dönüştür-sonra-çarp” konvolüsyon teoreminin pratik gücü. ML köprüsü: bu seçim büyük-çekirdek konvolüsyonları hızlandırır — uzun filtrelerle FFT-conv (dönüştür-çarp-geri-dön) doğrudan evrişimden hızlıdır; ses işleme ve bazı CNN katmanları bunu kullanır.

31.7 6. Maliyet: N² vs N log N

Hangi yol hızlı? Maliyet say. Doğrudan evrişim: her c her d’yi çarpar → $O(n^2)$ küçük çarpım. FFT yolu: iki Fourier dönüşümü ($2 \cdot n \log n$) + bileşen-bileşen çarpım (n) = effektif $n \log n$:

\[\text{evris: } O(n^{2}) \qquad \text{FFT yolu: } 2(n\log n) + n\]

“…this is the fast way.” — Strang, 35:32

Büyük n’de FFT yolu kazanır. Uygulama: iki büyük tamsayı çarpmak (kriptografide 128+ haneli) — ayrı ayrı FFT al, bileşen-bileşen çarp, geri dönüştür. Evrişim kuralı + FFT bunu mümkün kılar.

Kod

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

ns = 2 ** np.arange(4, 15)
ax.loglog(ns, ns ** 2.0, color=COL_VEC3, lw=2, label="doğrudan $n^2$")
ax.loglog(ns, 2 * ns * np.log2(ns) + ns, color=COL_PRIMARY, lw=2, label="FFT yolu $2n\\log n + n$")
ax.axvline(1024, color=COL_STEEL_300, ls="--", lw=1.4)
ax.annotate("n=1024: 1.048.576 vs 21.504 = 48.8x", xy=(1024, 1024 ** 2),
            xytext=(40, 5e7), fontsize=9, color=COL_TEXT,
            arrowprops=dict(arrowstyle="->", color=COL_STEEL_300, lw=1.2))
ax.set_xlabel("n (log)"); ax.set_ylabel("işlem sayısı (log)")
ax.set_title("Sayma kazandırır: büyük n'de FFT yolu açık ara —\nbüyük-tamsayı çarpımı (kriptografi) böyle hızlanır", fontsize=11)
apply_style(ax)
ax.legend()

plt.show()

Şekil 31.5: Sayma kazandırır: doğrudan evrişim $O(n^2)$, FFT yolu $2n\log n + n$. log-log eksende iki eğri açılır; n=1024’te doğrudan 1.048.576 işlem ister, FFT yolu yalnızca 21.504 — oran 48.8x (kabaca ~50x). Büyük-tamsayı çarpımı (kriptografi) tam bu nedenle FFT ile hızlanır.

Şekil 31.5 iki yolun maliyetini log-log eksende açar: turuncu eğri doğrudan evrişim $n^2$, navy eğri FFT yolu $2n \log n + n$; n=1024’te gri kesik çizgi iki eğriyi ayırır — doğrudan yol 1.048.576 işlem ister, FFT yolu yalnızca 21.504, oran 48.8× (kabaca ~50×). Büyük n büyüdükçe makas açılır; büyük-tamsayı çarpımı (kriptografide 128+ haneli sayılar) tam bu nedenle FFT ile hızlanır.

Builder Notu — Sayma Kazandırır

“FFT yolu $O(n \log n)$, doğrudan $O(n^2)$” hesaplamalı kazanç. ML köprüsü: büyük-tamsayı çarpımı (kriptografi), polinom çarpımı, büyük-çekirdek konvolüsyon — hepsi FFT-conv ile hızlanır. Modern derin öğrenmede küçük çekirdekler (3×3) için doğrudan conv daha hızlı, ama uzun-bağlam/büyük-çekirdek modeller FFT’ye döner.

31.8 7. 2B Evrişim (Görüntü)

Görüntüler 2 boyutludur — evrişim çift integrale dönüşür:

“…what is a two dimensional convolution?” — Strang, 36:38

\[(f * g)(x, y) = \iint f(t, u)\, g(x - t,\, y - u)\, dt\, du\]

Aynı imza: g’nin argümanı $(x-t, y-u)$ — iki yönde ters çevir-kaydır. Bir görüntüyü bir 2B çekirdekle (filtre) evirmek tam bu. CNN’lerin konvolüsyon katmanı 2B evrişimdir: küçük bir filtre (örn. 3×3) görüntü boyunca her iki yönde kaydırılır.

Kod

fig, axes = plt.subplots(1, 3, figsize=(12, 4))

img = make_test_image()
edge = conv2d_full(img, SOBEL_X)

# Sol: girdi görüntüsü
axes[0].imshow(img, cmap="gray")
axes[0].set_title("girdi: kare + köşegen şerit", color=COL_TEXT, fontsize=12, fontweight="bold")
axes[0].axis("off")

# Orta: Sobel-X çekirdeği heatmap
heatmap(axes[1], SOBEL_X, title="3x3 çekirdek (Sobel-X, dikey kenar)", cmap=DIVERGE, fmt="{:.0f}")

# Sağ: çıktı kenar haritası
axes[2].imshow(np.abs(edge), cmap=NAVY_CMAP)
axes[2].set_title("çıktı: dikey kenarlar parlar (max 4.21)", color=COL_TEXT, fontsize=12, fontweight="bold")
axes[2].axis("off")

fig.suptitle("2B evrişim = çift integralin ayrık hali: 3x3 çekirdek iki yönde ters çevir-kaydır — CNN'in conv katmanı (PyTorch conv2d) tam bu",
             color=COL_TEXT, fontsize=12, fontweight="bold")

plt.show()

Şekil 31.6: 2B evrişim = çift integralin ayrık hali: 3x3 çekirdek iki yönde ters çevir-kaydır — CNN’in conv katmanı (PyTorch conv2d) tam bu

Şekil 31.6 2B evrişimi gerçek bir kenar-dedektörüyle gösterir: solda girdi görüntüsü (parlak kare + köşegen şerit), ortada 3×3 Sobel-X çekirdeği (dikey kenar dedektörü, DIVERGE ısı haritası), sağda conv2d_full çıktısı $|$kenar$|$ — dikey kenarlar parlar, max yanıt 4.21. Çekirdek görüntü boyunca iki yönde ters çevrilip kaydırılır (çift-toplam); bu PyTorch conv2d’nin tam yaptığı işlemdir. (Sobel ayrıca ayrılabilirdir — kolon $(1,2,1)$ ∗ satır $(1,0,-1)$ evrişimi birebir, §8 Kronecker önizlemesi.)

Builder Notu — Çift İntegralin Filtresi

“2B evrişim = çift integral, iki yönde kaydır” CNN’in çekirdek operasyonu. ML köprüsü: PyTorch conv2d tam bu; 3×3 çekirdek tüm görüntü konumlarına uygulanır (ağırlık paylaşımı). fast.ai L15 im2col 2B evrişimi tek bir büyük matris çarpımına açar (GPU için); kenar/doku dedektörleri ilk CNN katmanlarının öğrendiği 2B filtrelerdir.

31.9 8. Kronecker Çarpımı ve Toplamı

1B’den 2B’ye geçişin matris aracı Kronecker çarpımı:

“…the MATLAB command is Kron.” — Strang, 38:55

İki n×n matris A, B’den n²×n² bir matris üretir; her $a_{ij}$ bloğu B ile çarpılır:

\[\text{Kron}(A, B) = \begin{bmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{n1}B & \cdots & a_{nn}B \end{bmatrix} \quad (n^{2} \times n^{2})\]

Örnek: 2B Fourier dönüşümü = Kron(F, F). 2B Laplacian (her iki yönde −1, 2, −1 ikinci fark, 5-nokta şablon): tek Kronecker çarpımı değil, Kronecker toplamı:

\[\text{Laplacian} = \text{Kron}(A, I) + \text{Kron}(I, A)\]

Kron(A,I) x yönündeki ikinci türevi, Kron(I,A) y yönündekini verir; toplamı 2B Laplacian.

Kod

fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.4))

# Sol: Kron(A, I) — her a_ij bloğu I çarpanı
A2 = np.array([[2., -1], [-1, 2]])
KAI = np.kron(A2, np.eye(2))
heatmap(axes[0], KAI, title="Kron(A, I): her a_ij bloğu I çarpanı", cmap=DIVERGE, fmt="{:.0f}")
axes[0].axhline(1.5, color=COL_WHITE, lw=2)
axes[0].axvline(1.5, color=COL_WHITE, lw=2)

# Sağ: 2B Laplacian = Kron(A,I)+Kron(I,A), 9x9 (köşegen 4, 5-nokta)
L = kron_sum_laplacian(3)
heatmap(axes[1], L, title="2B Laplacian = Kron(A,I)+Kron(I,A): köşegen 4, 5-nokta", cmap=DIVERGE, fmt="{:.0f}", fontsize=8)
vmin9, vmax9 = float(np.min(L)), float(np.max(L)); thr9 = vmin9 + 0.62*(vmax9-vmin9)
for i in range(9):
    for j in range(9):
        v = L[i, j]
        axes[1].text(j, i, "{:.0f}".format(v), ha="center", va="center", color=COL_WHITE if v >= thr9 else COL_TEXT, fontsize=8, fontweight="bold")

fig.suptitle("Kronecker çarpımı 1B yapıyı 2B'ye taşır (2B Fourier = Kron(F,F), kimlik 4.4e-16); Laplacian Kronecker TOPLAMIdır — Egz4 köşegeni 2+2 = 4", fontsize=10, color=COL_TEXT)
fig.tight_layout()
plt.show()

Şekil 31.7: Kronecker çarpımı 1B yapıyı 2B’ye taşır (2B Fourier = Kron(F,F), kimlik 4.4e-16); Laplacian Kronecker TOPLAMIdır — Egz4 köşegeni 2+2 = 4

Şekil 31.7 Kronecker yapısını iki ısı haritasıyla gösterir: solda Kron(A, I) 4×4 — A=[[2,−1],[−1,2]]’nin her $a_{ij}$ girdisi 2×2 birim matrisle çarpılır (sol-üst blok 2I), beyaz çizgiler blok sınırlarını ayırır; sağda 2B Laplacian = Kron(A,I)+Kron(I,A) 9×9 (3×3 ızgara) — köşegende 4, iç satırlarda 5-nokta şablonu {4, −1×4}. Kronecker-vec kimliği $(B \otimes A)\cdot\text{vec}(X) = \text{vec}(AXB^{\top})$ motorda 4.44e-16; 2B Fourier = Kron(F,F) tanığı ($(F \otimes F)\text{vec}(X) = \text{vec}(FXF^{\top})$, F simetrik) yine 4.44e-16. Laplacian tek çarpım değil Kronecker toplamıdır — Egz4’ün köşegeni 2+2 = 4.

Builder Notu — Bloklarla İki Boyut Kurmak

“Kronecker çarpımı = 2B yapı, Kronecker toplamı = 2B Laplacian” çok-boyutlu operatörlerin matris dili. ML köprüsü: 2B/3B konvolüsyon, ayrılabilir (separable) filtreler (Kron(satır, sütun)), ve tensör işlemleri (PyTorch’ta kron) bu yapıyı kullanır; çözünürlük-uzayı yöntemleri (PDE çözücüler, fizik-bilgili ağlar) 2B Laplacian’ı Kronecker toplamıyla kurar.

31.10 Bu Dersin Özeti

ImageNet/AlexNet (2012): Krizhevsky-Sutskever-Hinton; CNN %15 hata (devrim); 60M parametre, conv+pool+dropout; CNN az ağırlık (paylaşım).
Evrişim: $(c*d)_k = \sum c_i\,d_{k-i}$ (polinom çarpımı); fonksiyon: $(f * g)(x) = \int f(t)\,g(x-t)\,dt$.
Evrişim kuralı: sirkülant CD özdeğerleri = $\lambda(C) \odot \lambda(D)$; $F(c \circledast d) = (Fc) \odot (Fd)$. Evrişim → frekansta çarpma.
İki yol + FFT: evriş-dönüştür ($O(n^2)$) vs ayrı-dönüştür-çarp ($2n\log n + n$); FFT ikinciyi hızlı kılar.
2B evrişim: çift integral $\iint f(t,u)\,g(x-t,y-u)\,dt\,du$; CNN’in conv katmanı.
Kronecker: çarpım Kron(A,B) ($n^2 \times n^2$, bloklar $a_{ij}B$) 2B yapı; Laplacian = Kron(A,I)+Kron(I,A) (Kronecker toplamı).

Tek Bir Cümle

Evrişim polinom çarpımıdır $(c*d)_k = \sum c_i\,d_{k-i}$; evrişim kuralı onu Fourier’de çarpmaya çevirir ($F(c \circledast d)=(Fc)\odot(Fd)$) ve FFT ile hızlandırır; CNN’ler bu evrişimi ağırlık paylaşımıyla görüntüye uygular (AlexNet), 2B’ye geçiş Kronecker çarpımıyla yapılır.

31.11 Kontrol Soruları

Soru 1 — AlexNet (2012) neden dönüm noktası ve CNN neden az ağırlık kullanır

AlexNet ImageNet 2012’de top-5 hatayı %15’e indirdi (ikinci takım %26) — CNN’in görüntü tanımayı dönüştürdüğünü kanıtladı. CNN az ağırlık kullanır çünkü ağırlık paylaşımı: aynı filtre (üst-satır ağırlıkları, sirkülant/Toeplitz) tüm konumlara uygulanır — tam $n^2$-ağırlık matrisi yerine küçük bir çekirdek. 60M parametre yine çoktu ama tam-bağlıdan çok azdı.

Soru 2 — Evrişim neden polinom çarpımıdır

c ve d’yi polinom katsayıları say ($c_0 + c_1 x + \dots$, $d_0 + d_1 x + \dots$). Çarpımda $x^k$’nin katsayısı, üsleri k’ya toplanan tüm $c_i d_j$ çarpımlarının toplamıdır ($i+j=k$). Bu tam $(c*d)_k = \sum_i c_i\,d_{k-i}$. Yani evrişim = polinom çarpımının katsayıları (kaydır-çarp-topla).

Soru 3 — Evrişim kuralı nedir ve neden FFT ile hızlıdır

$F(c \circledast d) = (Fc) \odot (Fd)$: döngüsel evrişimin Fourier dönüşümü = ayrı Fourier dönüşümlerinin bileşen-bileşen çarpımı (sirkülantlar ortak Fourier özvektörlerinde köşegenleşir, özdeğerler çarpılır). FFT ile hızlı: doğrudan evrişim $O(n^2)$; ama “iki kez FFT ($2n\log n$) + bileşen-çarpım (n)” yolu $O(n \log n)$ — büyük n’de çok daha hızlı.

Soru 4 — Kronecker çarpımı ve toplamı nedir, 2B Laplacian hangisidir

Kronecker çarpımı Kron(A,B): iki n×n matristen $n^2 \times n^2$ matris, her $a_{ij}$ bloğu B ile çarpılır — 1B’den 2B yapıya geçiş (örn. 2B Fourier = Kron(F,F)). 2B Laplacian tek çarpım değil Kronecker toplamıdır: Kron(A,I) + Kron(I,A) — biri x yönündeki ikinci türevi, diğeri y yönündekini verir, toplamı 5-nokta şablonu.

31.12 Egzersizler

Evrişim hesabı. $(1, 2, 3)$ ile $(1, 1)$ vektörlerini evir (sıradan, döngüsüz). Polinom $(1 + 2x + 3x^2)(1 + x)$ çarpımıyla doğrula. (Motor tanığı: $(1,2,3) \ast (1,1) = (1,3,5,3)$, poly_mult_coeffs ile birebir; D30 örneği $(3,1,2) \ast (4,6,1) = (12,22,17,13,2)$ de tutarlı.)
Konvolüsyon teoremi. n=2’de c=(1,1), d=(1,−1). Döngüsel evrişim $c \circledast d$’yi doğrudan hesapla. Sonra Fc, Fd al (F=[[1,1],[1,−1]]), bileşen-bileşen çarp, $F^{-1}$ ile geri dön; aynı sonucu bulduğunu göster. (Motor tanığı: $c \circledast d = (0,0)$ doğrudan; Fourier yolu $Fc=(2,0)$, $Fd=(0,2)$ → $\odot=(0,0)$ → $F^{-1}$ → (0,0). İki yol aynı — ve örnek özel: c, d ayrık frekanslarda yaşar, çarpımları sıfırlanır.)
Maliyet. n = 1024 için doğrudan evrişim ($n^2$) ve FFT yolu ($2n\log_2 n + n$) kaç işlem? FFT kaç kat hızlı (kabaca)? (Motor tanığı: doğrudan 1.048.576 vs FFT yolu $2 + 1024 = $ 21.504 → oran 48.8×, kabaca ~50×.)
Kronecker. A = [[2,−1],[−1,2]] (1B Laplacian, 2×2). Kron(A, I₂) ve Kron(I₂, A)’yı (4×4) yaz. Toplamlarının köşegeninin 4 olduğunu (2+2) göster. (Motor tanığı: Kron(A,I₂)+Kron(I₂,A) köşegeni (4,4,4,4); 3×3 ızgara 2B Laplacian 9×9, iç satır 5-nokta {4, −1×4}.)
(Ders 33 habercisi) CNN’ler evrişimi katman katman uygular; ama bir sinir ağının “öğrendiği fonksiyon” tam olarak ne, hangi fonksiyonları temsil edebilir? Bir tahmin yaz — Ders 33 “sinir ağları ve öğrenme fonksiyonu”nu (Ders 26’nın derinleşmesi) işliyor.

31.13 Sonraki Ders İçin Hazırlık

Ders 33: Sinir Ağları ve Öğrenme Fonksiyonu. Ders 26’nın sinir-ağı yapısını derinleştirir: öğrenme fonksiyonu $F(x, v)$’nin ifade gücü, hangi fonksiyonları öğrenebildiği, ve eğitim (SGD + backprop, Ders 25/27) ile yapının birleşimi. Derin öğrenme bloğunun kapanışına doğru.

Hazırlık

Bu dersin Egzersiz 5’inin sorduğu soruyu zihninde tut: CNN’ler evrişimi katman katman uygularken, bir sinir ağının “öğrendiği fonksiyon” tam olarak ne ve hangi fonksiyonları temsil edebilir? Ders 33, öğrenme fonksiyonu $F(x, v)$’yi (Ders 26’nın sinir-ağı yapısının derinleşmesi) işler — ifade gücü, temsil edebildiği fonksiyon sınıfı, ve eğitim (SGD + backprop, Ders 25/27) ile birleşimi. Derin öğrenme bloğunun kapanışına yaklaşıyoruz.

31.14 Anahtar Kavramlar (Cheat Sheet)

Kavram	Formül / Fikir	Strang (dk)
ImageNet/AlexNet	CNN %15 hata (2012); 60M param; ağırlık paylaşımı	2m33
Evrişim	$(c*d)_k = \sum c_i\,d_{k-i}$; polinom çarpımı	6m04
Fonksiyon evrişimi	$(f * g)(x) = \int f(t)\,g(x-t)\,dt$	10m02
Evrişim kuralı	$\lambda(CD) = \lambda(C) \odot \lambda(D)$; $F(c \circledast d) = (Fc)\odot(Fd)$	28m52
İki yol	evriş-dönüştür vs ayrı-dönüştür-çarp	30m50
Maliyet	doğrudan $O(n^2)$ vs FFT yolu $O(n \log n)$	35m32
2B evrişim	$\iint f(t,u)\,g(x-t,y-u)\,dt\,du$	36m38
Kronecker	Kron(A,B) $n^2 \times n^2$; Laplacian = Kron(A,I)+Kron(I,A)	38m55

31.15 ML Bağlantıları Özeti

CNN = ağırlık paylaşımı: AlexNet (2012) derin öğrenme devrimi; konvolüsyon tam matrisi küçük filtreye indirir; dropout/max pooling/ReLU yaygınlaştı.
Evrişim = polinom çarpımı = kaydır-çarp-topla: PyTorch conv2d; fast.ai L15 im2col evrişimi matris çarpımına açar (GPU).
Konvolüsyon teoremi + FFT: $F(c \circledast d)=(Fc)\odot(Fd)$; büyük-çekirdek konvolüsyon FFT-conv ile $O(n \log n)$; ses (spektrogram), FNet.
2B evrişim: çift integral; CNN’in conv katmanı; kenar/doku dedektörleri ilk katman filtreleri.
Kronecker: 1B→2B (Kron(F,F) 2B Fourier); ayrılabilir filtreler; 2B Laplacian = Kronecker toplamı (PDE çözücüler, PINN).
Geriye köprü: Ders 30-31 (sirkülant/cyclic convolution/Fourier/FFT), Ders 4 (özdeğer çarpımı). Paralel: fast.ai L15 (conv2d/im2col), NYU H6 (CNN), Karpathy makemore CNN bölümü.

Kapanış

“…the MATLAB command is Kron.” — Strang, 38:55

Evrişim sirkülant/Fourier dünyasından doğar (convolution teoremi + FFT), CNN’ler onu ağırlık paylaşımıyla görüntüye uygular, ve Kronecker çarpımı tüm bunu 2B’ye taşır — sinyal işleme ile derin öğrenmenin buluştuğu nokta.

--- title: "ImageNet bir CNN'dir, Evrişim Kuralı" subtitle: "AlexNet devrimi, evrişim = polinom çarpımı, özdeğerlerin çarpıldığı kural ve Kronecker ile iki boyut" --- ::: {.callout-note title="Bölüm bilgisi"} Bu ders sirkülant/Fourier'i (Ders 30-31) evrişime ve CNN'lere taşır. Strang'in [Ders 32 videosu](https://www.youtube.com/watch?v=hwDRfkPSXng) (≈47 dk) ve [OCW Lecture 32](https://ocw.mit.edu/courses/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/resources/lecture-32-imagenet-is-a-cnn-the-convolution-rule/) (≈32 dk okuma) temel alınmıştır. Önkoşul Ders 30-31 (sirkülant/Fourier/FFT) ve Ders 26 (sinir ağı yapısı). ::: ```{python} #| echo: false """ _engine32.py — MIT 18.065 Ders 32 (ImageNet/CNN + Evrişim Kuralı + Kronecker) motor + viz. Zincir: evrişim = polinom çarpımı → evrişim kuralı λ(CD)=λ(C)⊙λ(D), F(c⊛d)=(Fc)⊙(Fd) → iki yol maliyeti n² vs 2n·log n + n → 2B evrişim (conv2d elle) → Kronecker çarpım/toplam. Setup hücresi = cat. Figür testi `from _engine32 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=10, 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 <= 64: 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") # ============ D30-31 TEMELİ (self-contained) ============ def cyclic_P(n=4): P = np.zeros((n, n)) for i in range(n): P[i, (i - 1) % n] = 1.0 return P def circulant(c): c = np.asarray(c, dtype=complex); n = len(c); P = cyclic_P(n) C = np.zeros((n, n), dtype=complex); Pk = np.eye(n) for k in range(n): C += c[k] * Pk Pk = P @ Pk return C.real if np.allclose(C.imag, 0) else C def linear_conv(a, b): """Döngüsüz evrişim = polinom çarpımının katsayıları.""" return np.convolve(np.asarray(a, float), np.asarray(b, float)) def cyclic_conv(a, b): a = np.asarray(a, float); b = np.asarray(b, float); n = len(a) out = np.zeros(n) for i in range(n): for j in range(n): out[(i + j) % n] += a[i] * b[j] return out def fourier_matrix(n=4): w = np.exp(2j * np.pi / n) j, k = np.meshgrid(np.arange(n), np.arange(n), indexing="ij") return w ** (j * k) # ============ (2) POLİNOM ÇARPIMI = EVRİŞİM ============ def poly_mult_coeffs(c, d): """Polinom çarpımının katsayıları — evrişimle BİREBİR aynı olmalı (tanım tanığı).""" c = np.asarray(c, float); d = np.asarray(d, float) out = np.zeros(len(c) + len(d) - 1) for i, ci in enumerate(c): for j, dj in enumerate(d): out[i + j] += ci * dj # üsler i+j=k toplanır return out # ============ (4-5) EVRİŞİM KURALI ============ def eigenvalue_rule_defect(c, d): """‖λ(CD) − λ(C)⊙λ(D)‖_max — ortak Fourier tabanında köşegenler çarpılır.""" n = len(c); F = fourier_matrix(n) C = circulant(c); D = circulant(d) lamC = np.diag(np.linalg.solve(F, C @ F)) lamD = np.diag(np.linalg.solve(F, D @ F)) lamCD = np.diag(np.linalg.solve(F, (C @ D) @ F)) return float(np.max(np.abs(lamCD - lamC * lamD))) def conv_rule_defect(c, d): """‖F(c⊛d) − (Fc)⊙(Fd)‖_max — Strang F konvansiyonuyla evrişim kuralı (Notion formülü).""" n = len(c); F = fourier_matrix(n) lhs = F @ cyclic_conv(c, d) rhs = (F @ np.asarray(c, complex)) * (F @ np.asarray(d, complex)) return float(np.max(np.abs(lhs - rhs))) def two_path_costs(n): """Doğrudan evrişim n² vs FFT yolu 2·n·log2(n) + n (Egz3 maliyet modeli).""" return float(n) ** 2, 2 * n * np.log2(n) + n # ============ (7) 2B EVRİŞİM (elle, scipy YOK) ============ def conv2d_full(img, ker): """2B döngüsüz tam evrişim: out[x,y] = ΣΣ img[t,u]·ker[x−t, y−u] (çift-toplam, ters çevir-kaydır).""" img = np.asarray(img, float); ker = np.asarray(ker, float) m1, n1 = img.shape; m2, n2 = ker.shape out = np.zeros((m1 + m2 - 1, n1 + n2 - 1)) for t in range(m1): for u in range(n1): out[t:t + m2, u:u + n2] += img[t, u] * ker return out def make_test_image(n=48, seed=32): """Kenarlı sentetik gri görüntü: parlak kare + köşegen şerit (kenar-dedektör tanığı).""" img = np.zeros((n, n)) img[10:30, 8:26] = 1.0 # parlak kare for i in range(n): j = i + 6 if 0 <= j < n: img[i, max(0, j - 2):j + 1] = 0.7 # köşegen şerit rng = np.random.default_rng(seed) return img + rng.normal(0, 0.04, (n, n)) SOBEL_X = np.array([[1.0, 0, -1], [2, 0, -2], [1, 0, -1]]) # dikey kenar dedektörü # ============ (8) KRONECKER ÇARPIM + TOPLAM ============ def lap1d(n): """1B Laplacian (ikinci fark): köşegen 2, komşular −1.""" A = 2 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1) return A def kron_sum_laplacian(n): """2B Laplacian = Kron(A,I) + Kron(I,A) — 5-nokta şablonu (n²×n²).""" A = lap1d(n); I = np.eye(n) return np.kron(A, I) + np.kron(I, A) def kron_vec_identity_defect(A, B, X): """‖(B ⊗ A)·vec(X) − vec(AXBᵀ)‖_max — Kronecker-vec kimliği (sütun-major vec).""" lhs = np.kron(B, A) @ X.flatten("F") rhs = (A @ X @ B.T).flatten("F") return float(np.max(np.abs(lhs - rhs))) def kron2d_fourier_defect(n, seed=32): """2B Fourier = Kron(F,F) tanığı: (F⊗F)·vec(X) = vec(F·X·Fᵀ) (F simetrik: Fᵀ=F).""" F = fourier_matrix(n) X = np.random.default_rng(seed).uniform(-1, 1, (n, n)) lhs = np.kron(F, F) @ X.flatten("F") rhs = (F @ X @ F.T).flatten("F") return float(np.max(np.abs(lhs - rhs))) ``` ## Bu Derste Ne Var? {#sec-bu-derste-d32} Ders 30-31'in sirkülant/Fourier fikrini evrişime ve görüntülere taşıyoruz. **Evrişim** (convolution) = polinom çarpımı; **evrişim kuralı** Fourier ile evrişimi çarpmaya çevirir; CNN'ler bu yapıyı görüntüye uygular. Beş sonuç: 1. **ImageNet/AlexNet (2012):** Krizhevsky-Sutskever-Hinton; CNN %15 hata (2.'lik %26) — derin öğrenme devrimi. CNN az ağırlık (paylaşım). 2. **Evrişim tanımı:** $(c * d)_{k} = \sum_{i+j=k} c_{i}\,d_{j}$; polinom çarpımından gelir. Fonksiyon: $(f * g)(x) = \int f(t)\,g(x-t)\,dt$. 3. **Evrişim kuralı:** sirkülant CD'nin özdeğerleri = $\lambda(C) \odot \lambda(D)$ (bileşen-bileşen); $F(c \circledast d) = (Fc) \odot (Fd)$. 4. **FFT iki yol:** ya evriş→dönüştür ($O(n^2)$), ya ayrı-dönüştür→çarp ($2n\log n + n$). FFT ikincisini hızlı kılar. 5. **2B + Kronecker:** 2B evrişim çift-integral; Kronecker çarpımı (1B→2B), Laplacian = Kron(A,I)+Kron(I,A) (Kronecker toplamı). > *"...the MATLAB command is Kron." — Strang, 38:55* ```{mermaid} %%| label: fig-kavram-haritasi-l32 %%| fig-cap: "Ders 32 kavram haritasi: evrisim kurali F(c conv d) = (Fc) . (Fd) sirkulantlari ortak Fourier tabaninda kosegenlestirir, kosegenler carpilir. Yedi dal: AlexNet 2012 CNN yuzde 15 hata (ImageNet devrimi); evrisim = polinom carpimi (usler i+j=k toplanir); fonksiyon evrisimi integral f(t) g(x-t) dt; ozdegerler carpilir lambda(CD) = lambda(C) . lambda(D); iki yol evris-sonra-donustur vs donustur-sonra-carp (FFT kazanir, buyuk-tamsayi/kriptografi); 2B evrisim = CNN conv katmani; Kronecker Kron(A,B) 1B yapiyi 2B ye tasir, Laplacian = Kron(A,I)+Kron(I,A). Koprular: D30-31 sirkulant/Fourier/FFT, D33 ogrenme fonksiyonu (sonraki), fast.ai L15 im2col / NYU H6 / Karpathy makemore CNN." %%| echo: false flowchart TD C["Evrisim kurali: F(c conv d) = (Fc) . (Fd)"] C --> A["AlexNet 2012: CNN yuzde 15 hata (devrim)"] C --> P["evrisim = polinom carpimi (usler i+j=k)"] C --> I["fonksiyon evrisimi: integral f(t) g(x-t) dt"] C --> L["ozdegerler carpilir: lambda(CD) = lambda(C) . lambda(D)"] C --> Y["iki yol: evris-donustur vs donustur-carp (FFT kazanir)"] C --> D2["2B evrisim (CNN conv katmani)"] C --> KR["Kronecker: Kron(A,B); Laplacian = Kron(A,I)+Kron(I,A)"] K1["D30-31 sirkulant / Fourier / FFT"] K2["D33 ogrenme fonksiyonu (sonraki)"] K3["fast.ai L15 im2col / NYU H6 / Karpathy makemore CNN"] K1 --> C L --> K2 D2 --> K3 classDef merkez fill:#1f4e79,stroke:#13243a,stroke-width:2px,color:#ffffff; classDef dal fill:#2e75b6,stroke:#1f4e79,stroke-width:1.5px,color:#ffffff; classDef vec fill:#ff8c42,stroke:#c25a16,stroke-width:1.5px,color:#1f2330; classDef teal fill:#2ca6a4,stroke:#1f6f6e,stroke-width:1.5px,color:#ffffff; class C merkez; class A,P,I,L,Y,D2,KR dal; class K1 vec; class K2,K3 teal; ``` @fig-kavram-haritasi-l32 dersin iskeletini gösterir: merkezdeki **evrişim kuralı $F(c \circledast d) = (Fc) \odot (Fd)$** fikrinden yedi dala ayrılır — AlexNet 2012 (CNN %15 hata, ImageNet devrimi), evrişim = polinom çarpımı (üsler $i+j=k$), fonksiyon evrişimi $\int f(t)\,g(x-t)\,dt$, özdeğerler çarpılır $\lambda(CD) = \lambda(C) \odot \lambda(D)$, iki yol (evriş-dönüştür vs dönüştür-çarp, FFT kazanır), 2B evrişim (CNN conv katmanı) ve Kronecker Kron(A,B) + Laplacian = Kron(A,I)+Kron(I,A); köprü düğümleri D30-31 (sirkülant/Fourier/FFT), D33 öğrenme fonksiyonu (sonraki) ve fast.ai L15 im2col / NYU H6 / Karpathy makemore CNN dalları önceki ile sonraki derslere bağlar. ::: {.callout-tip title="Builder Notu — Sinyal İşleme Derin Öğrenmeyle Buluşunca"} - **CNN = ağırlık paylaşımı:** AlexNet 60M parametre, 5 conv + 3 tam-bağlı, max pooling, dropout; konvolüsyon tam matrisi küçük filtreye indirir. - **Evrişim kuralı + FFT:** büyük evrişimleri F-dönüştür-çarp-geri-dön ile $O(n \log n)$'de yap; büyük-tamsayı çarpımı, ses, FFT-conv. - **Kronecker = 2B yapı:** 1B matrislerden 2B (görüntü) matrisi; 2B Fourier = Kron(F,F), 2B Laplacian = Kronecker toplamı. - **Geriye köprü:** Ders 30-31 (sirkülant/cyclic convolution/Fourier/FFT), Ders 4 (özdeğer çarpımı). Paralel: fast.ai L15 (conv2d/im2col), NYU H6 (CNN), Karpathy makemore CNN. Tek cümle: Evrişim polinom çarpımıdır; evrişim kuralı (Fourier'de çarpmaya döner) FFT ile evrişimi hızlandırır; CNN'ler bu evrişimi (ağırlık paylaşımıyla) görüntüye uygular, 2B'ye geçiş Kronecker çarpımıyla yapılır. ::: ## 1. ImageNet ve AlexNet (2012) {#sec-imagenet-alexnet} Derin öğrenmenin dönüm noktası: Krizhevsky-Sutskever-Hinton'ın 2012 ImageNet yarışması makalesi (AlexNet). > *"We trained a large deep convolutional neural network." — Strang, 2:33* 1.2 milyon görüntü, 2 GPU'da 5 gün eğitim. Sonuç: top-5 test hatası **%15** (ikinci takım %26) — devrim niteliğinde. Ağ: 60 milyon parametre, 5 konvolüsyon katmanı + 3 tam-bağlı katman, max pooling (boyut indirme), dropout (aşırı-öğrenme önleme). Kritik: **CNN az ağırlık** kullanır — tam matris yerine sadece üst-satır (filtre) ağırlıkları (Ders 31 ağırlık paylaşımı). ```{python} #| label: fig-alexnet #| fig-cap: "AlexNet'in 2012 ImageNet zaferi — derin öğrenme devriminin tetiği. Sol: top-5 hata, AlexNet (CNN) %15 (navy) vs ikinci takım %26 (turuncu); on bir puanlık fark bir CNN'in eseri. Sağ: AlexNet mimari şeridi — 8 katman zinciri, 5 evrişim katmanı (conv1..conv5, navy) + 3 tam bağlı katman (fc6..fc8, turuncu), conv1/conv2/conv5 sonrası max pool. 60M parametre, 1.2M görüntü, 2 GPU × 5 gün, dropout: ağırlık paylaşımı sayesinde derin ama az ağırlıklı." #| fig-width: 10.5 #| fig-height: 4 #| code-fold: true fig, (axL, axR) = plt.subplots(1, 2, figsize=(10.5, 4)) # --- Sol panel: ImageNet 2012 top-5 hata bar (AlexNet 15 vs 2. takim 26) --- vals = [15, 26] cols = [COL_PRIMARY, COL_VEC3] xpos = np.arange(2) axL.bar(xpos, vals, color=cols, width=0.6, edgecolor=COL_WHITE, linewidth=1.4) for i, v in enumerate(vals): axL.text(xpos[i], v + 0.7, "%{}".format(v), ha="center", va="bottom", fontsize=13, fontweight="bold", color=cols[i]) apply_style(axL) axL.set_xticks(xpos); axL.set_xticklabels(["AlexNet (CNN)", "2. takim"], fontsize=11) axL.set_ylabel("top-5 hata (%)") axL.set_ylim(0, 30) axL.set_title("AlexNet devrimi (2012)", fontsize=12, fontweight="bold") # --- Sag panel: AlexNet mimari serit (8 kutu: 5 conv navy + 3 fc turuncu) --- conv_names = ["conv1", "conv2", "conv3", "conv4", "conv5"] fc_names = ["fc6", "fc7", "fc8"] names = conv_names + fc_names colors = [COL_PRIMARY] * 5 + [COL_VEC3] * 3 pool_after = {0, 1, 4} # conv1, conv2, conv5 sonrasi pool n_box = 8 bw = 0.085 # kutu genisligi (axes fraction) gap = 0.025 # kutular arasi bosluk x0 = 0.04 # sol baslangic by = 0.50 # kutu dikey merkez bh = 0.30 # kutu yuksekligi for k in range(n_box): x = x0 + k * (bw + gap) axR.add_patch(plt.Rectangle((x, by - bh / 2), bw, bh, fc=colors[k], ec=COL_WHITE, lw=1.6, transform=axR.transAxes, zorder=2)) axR.text(x + bw / 2, by, names[k], ha="center", va="center", fontsize=8.5, color=COL_WHITE, fontweight="bold", rotation=90, transform=axR.transAxes, zorder=3) if k in pool_after: axR.text(x + bw / 2, by - bh / 2 - 0.05, "pool", ha="center", va="top", fontsize=7.5, color=COL_TEXT, transform=axR.transAxes, zorder=3) # kutular arasi oklar for k in range(n_box - 1): xa = x0 + k * (bw + gap) + bw xb = x0 + (k + 1) * (bw + gap) axR.annotate("", xy=(xb, by), xytext=(xa, by), xycoords="axes fraction", arrowprops=dict(arrowstyle="-|>", color=COL_ACCENT, lw=1.4)) # altta tarihsel metin axR.text(0.5, 0.10, "60M parametre, 1.2M goruntu, 2 GPU x 5 gun, dropout", ha="center", va="center", fontsize=9.5, color=COL_PRIMARY, fontweight="bold", transform=axR.transAxes) axR.set_xlim(0, 1); axR.set_ylim(0, 1) axR.axis("off") fig.suptitle("ImageNet 2012: derin ogrenme devriminin tetigi — CNN agirlik " "paylasimiyla az agirlik, yuzde 15 vs 26", fontsize=11.5, color=COL_PRIMARY, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.93]) plt.show() ``` @fig-alexnet 2012 sıçramasını iki panelde toplar: solda top-5 hata barı — AlexNet (CNN) **%15** (navy) ile ikinci takım **%26** (turuncu) arasındaki on bir puanlık fark tek bir CNN'in eseridir; sağda AlexNet mimari şeridi — sekiz katman zinciri, 5 evrişim katmanı (conv1..conv5, navy) + 3 tam-bağlı katman (fc6..fc8, turuncu), conv1/conv2/conv5 sonrası max pool, altta **60M parametre, 1.2M görüntü, 2 GPU × 5 gün, dropout**. Ağırlık paylaşımı sayesinde ağ derin ama az ağırlıklıdır. ::: {.callout-tip title="Builder Notu — On Beşe Karşı Yirmi Altı"} "AlexNet 2012 = derin öğrenme devriminin tetiği" ML tarihinin dönüm noktası. ML köprüsü: %15 vs %26 sıçraması (ve sonraki yıllarda hızla düşmesi) CNN'in görüntü tanımayı dönüştürdüğünü kanıtladı; dropout, ReLU, GPU eğitimi bu makaleyle yaygınlaştı. Sutskever sonra OpenAI'ı kurdu — bu makale modern AI'ın başlangıç noktalarından. ::: ## 2. Evrişim Tanımı: Polinom Çarpımı {#sec-evrisim-tanim} **Evrişim** (convolution) iki vektörü "kaydır-çarp-topla" ile birleştirir. k'ıncı bileşen, indisleri k'ya toplanan tüm çarpımların toplamı: > *"...index i plus j adds to k." — Strang, 6:04* $$(c * d)_{k} = \sum_{i+j=k} c_{i}\,d_{j} = \sum_{i} c_{i}\,d_{k-i}$$ Nereden gelir? **Polinom çarpımından.** c'yi ($c_0 + c_1 x + \dots$) ve d'yi ($d_0 + d_1 x + \dots$) polinom say, çarp; $x^k$'nin katsayısı tam bu toplamdır (üsler $i + j = k$ toplanır). Evrişim = polinom çarpımının katsayıları. ```{python} #| label: fig-evrisim-tanim #| fig-cap: "Evrisim = polinom carpimi: usler i+j=k toplanir — (1,2,3) conv (1,1) = (1,3,5,3)" #| fig-width: 10.5 #| fig-height: 4 #| code-fold: true fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(10.5, 4)) # ---- Sol: kaydır-çarp-topla şeması ---- ax0.set_xlim(0, 10); ax0.set_ylim(0, 10); ax0.axis("off") ax0.set_title("kaydir-carp-topla: d=(1,1) TERS kayan pencere", color=COL_TEXT, fontsize=11, fontweight="bold") c = [1, 2, 3] # üstte c=(1,2,3) üç navy kutu for idx, ci in enumerate(c): x = 1.0 + idx * 1.0 ax0.add_patch(plt.Rectangle((x, 8.6), 0.9, 0.8, facecolor=COL_PRIMARY, edgecolor=COL_WHITE, lw=1.2)) ax0.text(x + 0.45, 9.0, str(ci), ha="center", va="center", color=COL_WHITE, fontsize=11, fontweight="bold") ax0.text(0.7, 9.0, "c=", ha="right", va="center", color=COL_TEXT, fontsize=10, fontweight="bold") # altta d=(1,1) TERS çevrilmiş turuncu pencere, k=0..3 dört konumda (dikeyde 4 sıra) results = ["k=0: 1*1=1", "k=1: 1*1+2*1=3", "k=2: 2*1+3*1=5", "k=3: 3*1=3"] sc = 0.55 # küçük ölçek row_y = [7.2, 5.6, 4.0, 2.4] for k in range(4): y = row_y[k] base = 1.0 + (k - 1) * 1.0 for w in range(2): x = base + w * sc * 1.0 ax0.add_patch(plt.Rectangle((x, y), sc * 0.9, sc * 0.9, facecolor=COL_VEC3, edgecolor=COL_WHITE, lw=1.0)) ax0.text(x + sc * 0.45, y + sc * 0.45, "1", ha="center", va="center", color=COL_WHITE, fontsize=8, fontweight="bold") ax0.text(5.3, y + sc * 0.45, results[k], ha="left", va="center", color=COL_TEXT, fontsize=9, fontweight="bold") # ---- Sağ: bar (1,3,5,3) ---- coeffs = poly_mult_coeffs(c, [1, 1]) # motor: (1,3,5,3) xs = np.arange(4) ax1.bar(xs, coeffs, color=COL_PRIMARY, edgecolor=COL_WHITE, width=0.62) for xi, ci in zip(xs, coeffs): ax1.text(xi, ci + 0.12, f"{ci:.0f}", ha="center", va="bottom", color=COL_TEXT, fontsize=11, fontweight="bold") ax1.set_xticks(xs); ax1.set_xticklabels(["x^0", "x^1", "x^2", "x^3"]) ax1.set_ylim(0, 6) ax1.text(1.5, 5.6, "(1 + 2x + 3x^2)(1 + x)", ha="center", va="center", color=COL_TEXT, fontsize=11, fontweight="bold") ax1.set_title("katsayilar = evrisim (motor BIREBIR)", color=COL_TEXT, fontsize=12, fontweight="bold") apply_style(ax1) fig.suptitle("Evrisim = polinom carpimi: usler i+j=k toplanir — (1,2,3) conv (1,1) = (1,3,5,3)", color=COL_TEXT, fontsize=12, fontweight="bold") fig.tight_layout(rect=[0, 0, 1, 0.94]) plt.show() ``` @fig-evrisim-tanim tanımı iki açıdan somutlaştırır: solda kaydır-çarp-topla şeması — c=(1,2,3) üç navy kutu, altında d=(1,1) **ters çevrilmiş** turuncu kayan pencere dört konumda (k=0..3), her konumda örtüşen çarpımların toplamı sağda yazılı (k=0: 1, k=1: 3, k=2: 5, k=3: 3); sağda polinom karşılığı — $(1 + 2x + 3x^2)(1 + x)$ çarpımının katsayıları bar olarak **(1,3,5,3)** ($x^0, x^1, x^2, x^3$ üsleri), `poly_mult_coeffs` motoruyla birebir. Evrişim ile polinom çarpımı aynı sayıyı verir — üsler $i+j=k$ toplandığı için. ::: {.callout-tip title="Builder Notu — Kaydır Çarp Topla"} "Evrişim = polinom çarpımı" sinyal işlemenin cebirsel kökeni. ML köprüsü: CNN'deki konvolüsyon katmanı tam bu kaydır-çarp-topla; bir filtre (çekirdek) görüntü üzerinde kaydırılır, her konumda nokta-çarpım. fast.ai L15 im2col bu evrişimi büyük matris çarpımına açar (GPU verimliliği için). ::: ## 3. Fonksiyon Evrişimi {#sec-fonksiyon-evrisim} Aynı fikir sürekli fonksiyonlarda — toplam yerine integral: > *"...f star g at x." — Strang, 10:02* $$(f * g)(x) = \int f(t)\, g(x - t)\, dt$$ Vektör evrişiminin sürekli karşılığı: $c_i \to f(t)$, $d_{k-i} \to g(x-t)$, toplam → integral. g, **ters çevrilip kaydırılır** ($x-t$); t değiştikçe kayma miktarı değişir — bir filtrenin tam yaptığı şey. (Daire koymadım: bu sıradan/döngüsüz evrişim; periyodik fonksiyonlarda döngüsel olur.) ::: {.callout-tip title="Builder Notu — Ters Çevirip Kaydırmak"} "Fonksiyon evrişimi = ters çevir, kaydır, çarp, integre et" sinyal işlemenin sürekli dili. ML köprüsü: filtreleme (sinyal/görüntü), olasılıkta iki bağımsız değişkenin toplamının dağılımı (yoğunlukların evrişimi), ve sürekli CNN'ler/Gauss bulanıklaştırma hep bu integral. Ters-çevirme, evrişimi korelasyondan ayıran detaydır (CNN'ler aslında çapraz-korelasyon kullanır). ::: ## 4. Evrişim Kuralı: Özdeğerler Çarpılır {#sec-evrisim-kurali} Ders 30-31'i birleştir. İki sirkülant C, D çarpılınca CD yine sirkülanttır; köşegenleri $c \circledast d$ (döngüsel evrişim). CD'nin özdeğerleri ne? Sirkülantlar **değişmeli** ve aynı özvektörleri (Fourier) paylaştığından: > *"...the eigenvalues just multiply." — Strang, 28:52* $$\lambda(CD) = \lambda(C) \odot \lambda(D) \quad (\text{bilesen-bilesen carpim})$$ Özdeğerler bileşen-bileşen (MATLAB `.*`, Hadamard çarpımı) çarpılır. Özdeğerler = ilk kolonun Fourier dönüşümü olduğundan (Ders 31), bu şu demek: $c \circledast d$'nin Fourier dönüşümü = (c'nin Fourier'i) $\odot$ (d'nin Fourier'i). Zaman uzayında evrişim → frekans uzayında çarpma. @fig-evrisim-kurali bu kuralı ve aşağıdaki iki yolu (§5) tek figürde doğrular. ::: {.callout-tip title="Builder Notu — Köşegenler Çarpılır"} "Evrişimin özdeğerleri çarpılır" konvolüsyon teoreminin spektral ispatı: sirkülantlar ortak özvektör (Fourier) tabanında köşegenleşir, köşegenler (özdeğerler) çarpılır. ML köprüsü: bu, evrişimi frekans uzayında nokta-çarpıma çeviren temel teorem; ses (spektrogram), görüntü filtreleme ve FFT-tabanlı konvolüsyon hep buna dayanır. ::: ## 5. İki Yol: Evrişim Kuralı + FFT {#sec-iki-yol} Evrişim kuralı (C kuralı) aynı sonuca iki yol verir: > *"...Convolve then transform by F. Or transform separately by F." — Strang, 30:50* $$F(c \circledast d) = (Fc) \odot (Fd)$$ **Yol 1:** önce evriş ($c \circledast d$), sonra Fourier'le dönüştür. **Yol 2:** her birini ayrı dönüştür ($Fc$, $Fd$), sonra bileşen-bileşen çarp. İkisi aynı sonuç. Neden önemli? Çünkü Fourier dönüşümü **FFT** ile çok hızlı ($O(n \log n)$). FFT'nin varlığı, Yol 2'yi çok cazip kılar. ```{python} #| label: fig-evrisim-kurali #| fig-cap: "Evrişim kuralı $F(c \\circledast d) = (Fc)\\cdot(Fd)$ üç açıdan. Sol: rastgele $c_4, d_4$ (seed 32) için $\\lambda(CD)$ ile $\\lambda(C)\\cdot\\lambda(D)$ çubukları üst üste oturur — ortak Fourier tabanında köşegenler bileşen-bileşen çarpılır, defect 1.8e-15. Orta: iki güzergah aynı sonuca varır — üstte evriş yapıp dönüştür, altta önce dönüştürüp bileşen-bileşen çarp. Sağ: Egz2 sıfır-evrişim — $c=(1,1)$ ve $d=(1,-1)$ ayrık frekanslarda yaşar, $Fc=(2,0)$ ile $Fd=(0,2)$ çakışmaz, çarpımları (0,0) olur ve $c \\circledast d = (0,0)$ çıkar." #| fig-width: 12 #| fig-height: 4.2 #| code-fold: true fig, (ax0, ax1, ax2) = plt.subplots(1, 3, figsize=(12, 4.2)) # --- Sol: ozdegerler carpilir --- rng = np.random.default_rng(32) c4 = rng.uniform(-2, 2, 4); d4 = rng.uniform(-2, 2, 4) F = fourier_matrix(4) C = circulant(c4); D = circulant(d4) lamCD = np.abs(np.diag(np.linalg.solve(F, (C @ D) @ F))) lamprod = np.abs(np.diag(np.linalg.solve(F, C @ F)) * np.diag(np.linalg.solve(F, D @ F))) x = np.arange(4) ax0.bar(x - 0.18, lamCD, width=0.36, color=COL_PRIMARY, label=r"$\lambda(CD)$") ax0.bar(x + 0.18, lamprod, width=0.36, color=COL_VEC3, label=r"$\lambda(C)\cdot\lambda(D)$") ax0.set_title("özdeğerler çarpılır (defect 1.8e-15)", color=COL_TEXT, fontsize=11, fontweight="bold") ax0.set_xticks(x); ax0.set_xticklabels([f"$\\lambda_{i}$" for i in range(4)]) ax0.set_ylabel("|özdeğer|"); ax0.legend(fontsize=8) apply_style(ax0) # --- Orta: iki yol akis semasi --- ax1.set_xlim(0, 10); ax1.set_ylim(0, 10); ax1.axis("off") def kutu(ax, cx, cy, w, h, text, color): ax.add_patch(plt.Rectangle((cx - w/2, cy - h/2), w, h, facecolor=color, edgecolor=COL_TEXT, linewidth=1.3, alpha=0.92)) ax.text(cx, cy, text, ha="center", va="center", color=COL_WHITE, fontsize=8.5, fontweight="bold") def ok(ax, x0, x1, y, color): ax.annotate("", xy=(x1, y), xytext=(x0, y), arrowprops=dict(arrowstyle="-|>", color=color, lw=1.8)) # ust zincir (navy) — evris yolu uy = 7.2 kutu(ax1, 1.7, uy, 1.8, 1.1, "c, d", COL_PRIMARY) kutu(ax1, 4.6, uy, 2.1, 1.1, "evriş:\nc conv d", COL_PRIMARY) kutu(ax1, 7.6, uy, 1.9, 1.1, "F ile\ndönüştür", COL_PRIMARY) ok(ax1, 2.6, 3.55, uy, COL_PRIMARY) ok(ax1, 5.65, 6.65, uy, COL_PRIMARY) # alt zincir (turuncu) — donustur-carp yolu ay = 2.8 kutu(ax1, 1.7, ay, 1.8, 1.1, "c, d", COL_VEC3) kutu(ax1, 4.6, ay, 2.1, 1.1, "Fc, Fd\nayrı", COL_VEC3) kutu(ax1, 7.6, ay, 2.1, 1.1, "bileşen\nçarp", COL_VEC3) ok(ax1, 2.6, 3.55, ay, COL_VEC3) ok(ax1, 5.65, 6.55, ay, COL_VEC3) # bulusma kutusu kutu(ax1, 9.0, 5.0, 1.5, 1.3, "AYNI\nsonuç", COL_TEAL) ax1.annotate("", xy=(9.0, 5.65), xytext=(8.55, uy - 0.55), arrowprops=dict(arrowstyle="-|>", color=COL_TEXT, lw=1.6)) ax1.annotate("", xy=(9.0, 4.35), xytext=(8.65, ay + 0.55), arrowprops=dict(arrowstyle="-|>", color=COL_TEXT, lw=1.6)) ax1.set_title("iki yol → tek sonuç", color=COL_TEXT, fontsize=11, fontweight="bold") # --- Sag: Egz2 sifir-evrisim --- F2 = fourier_matrix(2) Fc = np.abs(F2 @ np.array([1.0, 1.0])) # (2, 0) Fd = np.abs(F2 @ np.array([1.0, -1.0])) # (0, 2) xb = np.arange(2) ax2.bar(xb - 0.18, Fc, width=0.36, color=COL_PRIMARY, label="Fc = (2, 0)") ax2.bar(xb + 0.18, Fd, width=0.36, color=COL_VEC3, label="Fd = (0, 2)") ax2.set_title("Egz2: c conv d = (0,0), iki yol aynı", color=COL_TEXT, fontsize=11, fontweight="bold") ax2.set_xticks(xb); ax2.set_xticklabels(["frek 0", "frek 1"]) ax2.set_ylim(0, 2.6); ax2.legend(fontsize=8) ax2.annotate("ayrık frekanslar → çarpım (0,0)", xy=(0.5, 2.25), ha="center", fontsize=8.5, color=COL_TEXT, fontweight="bold") apply_style(ax2) fig.suptitle(r"Evrişim kuralı $F(c \circledast d) = (Fc)\cdot(Fd)$: sirkülantlar ortak Fourier tabanında köşegenleşir, köşegenler çarpılır", fontsize=12.5, fontweight="bold", color=COL_TEXT) fig.tight_layout(rect=[0, 0, 1, 0.95]) plt.show() ``` @fig-evrisim-kurali dersin amiral görselidir ve kuralı üç açıdan doğrular: solda rastgele $c_4, d_4$ (seed 32) için $\lambda(CD)$ (navy) ile $\lambda(C) \odot \lambda(D)$ (turuncu) barları üst üste oturur — ortak Fourier tabanında köşegenler bileşen-bileşen çarpılır, defect yalnızca **1.8e-15** (n=4; n=8 için <1e-10); ortada iki güzergah aynı sonuca varır — üst yol (navy) evriş yapıp F ile dönüştürür, alt yol (turuncu) önce ayrı dönüştürüp bileşen-bileşen çarpar, ikisi "AYNI sonuç"ta buluşur; sağda Egz2 sıfır-evrişim — $c=(1,1)$ ile $d=(1,-1)$ ayrık frekanslarda yaşar, $Fc=(2,0)$ ile $Fd=(0,2)$ çakışmaz, çarpımları (0,0) olur ve $c \circledast d = (0,0)$ çıkar (iki yol da aynı sıfırı verir — `conv_rule_defect` Strang F konvansiyonuyla D30 örneği (3,1,2)/(4,6,1) için de <1e-10). ::: {.callout-tip title="Builder Notu — Aynı Hedefe İki Güzergah"} "İki yol: evriş-sonra-dönüştür vs dönüştür-sonra-çarp" konvolüsyon teoreminin pratik gücü. ML köprüsü: bu seçim büyük-çekirdek konvolüsyonları hızlandırır — uzun filtrelerle FFT-conv (dönüştür-çarp-geri-dön) doğrudan evrişimden hızlıdır; ses işleme ve bazı CNN katmanları bunu kullanır. ::: ## 6. Maliyet: N² vs N log N {#sec-maliyet} Hangi yol hızlı? Maliyet say. **Doğrudan evrişim:** her c her d'yi çarpar → $O(n^2)$ küçük çarpım. **FFT yolu:** iki Fourier dönüşümü ($2 \cdot n \log n$) + bileşen-bileşen çarpım (n) = effektif $n \log n$: $$\text{evris: } O(n^{2}) \qquad \text{FFT yolu: } 2(n\log n) + n$$ > *"...this is the fast way." — Strang, 35:32* Büyük n'de FFT yolu kazanır. Uygulama: iki büyük tamsayı çarpmak (kriptografide 128+ haneli) — ayrı ayrı FFT al, bileşen-bileşen çarp, geri dönüştür. Evrişim kuralı + FFT bunu mümkün kılar. ```{python} #| label: fig-maliyet #| fig-cap: "Sayma kazandırır: doğrudan evrişim $O(n^2)$, FFT yolu $2n\\log n + n$. log-log eksende iki eğri açılır; n=1024'te doğrudan 1.048.576 işlem ister, FFT yolu yalnızca 21.504 — oran 48.8x (kabaca ~50x). Büyük-tamsayı çarpımı (kriptografi) tam bu nedenle FFT ile hızlanır." #| fig-width: 8 #| fig-height: 4.4 #| code-fold: true fig, ax = plt.subplots(figsize=(8, 4.4)) ns = 2 ** np.arange(4, 15) ax.loglog(ns, ns ** 2.0, color=COL_VEC3, lw=2, label="doğrudan $n^2$") ax.loglog(ns, 2 * ns * np.log2(ns) + ns, color=COL_PRIMARY, lw=2, label="FFT yolu $2n\\log n + n$") ax.axvline(1024, color=COL_STEEL_300, ls="--", lw=1.4) ax.annotate("n=1024: 1.048.576 vs 21.504 = 48.8x", xy=(1024, 1024 ** 2), xytext=(40, 5e7), fontsize=9, color=COL_TEXT, arrowprops=dict(arrowstyle="->", color=COL_STEEL_300, lw=1.2)) ax.set_xlabel("n (log)"); ax.set_ylabel("işlem sayısı (log)") ax.set_title("Sayma kazandırır: büyük n'de FFT yolu açık ara —\nbüyük-tamsayı çarpımı (kriptografi) böyle hızlanır", fontsize=11) apply_style(ax) ax.legend() plt.show() ``` @fig-maliyet iki yolun maliyetini log-log eksende açar: turuncu eğri doğrudan evrişim $n^2$, navy eğri FFT yolu $2n \log n + n$; n=1024'te gri kesik çizgi iki eğriyi ayırır — doğrudan yol **1.048.576** işlem ister, FFT yolu yalnızca **21.504**, oran **48.8×** (kabaca ~50×). Büyük n büyüdükçe makas açılır; büyük-tamsayı çarpımı (kriptografide 128+ haneli sayılar) tam bu nedenle FFT ile hızlanır. ::: {.callout-tip title="Builder Notu — Sayma Kazandırır"} "FFT yolu $O(n \log n)$, doğrudan $O(n^2)$" hesaplamalı kazanç. ML köprüsü: büyük-tamsayı çarpımı (kriptografi), polinom çarpımı, büyük-çekirdek konvolüsyon — hepsi FFT-conv ile hızlanır. Modern derin öğrenmede küçük çekirdekler (3×3) için doğrudan conv daha hızlı, ama uzun-bağlam/büyük-çekirdek modeller FFT'ye döner. ::: ## 7. 2B Evrişim (Görüntü) {#sec-2b-evrisim} Görüntüler 2 boyutludur — evrişim çift integrale dönüşür: > *"...what is a two dimensional convolution?" — Strang, 36:38* $$(f * g)(x, y) = \iint f(t, u)\, g(x - t,\, y - u)\, dt\, du$$ Aynı imza: g'nin argümanı $(x-t, y-u)$ — iki yönde ters çevir-kaydır. Bir görüntüyü bir 2B çekirdekle (filtre) evirmek tam bu. CNN'lerin konvolüsyon katmanı 2B evrişimdir: küçük bir filtre (örn. 3×3) görüntü boyunca her iki yönde kaydırılır. ```{python} #| label: fig-conv2d #| fig-cap: "2B evrişim = çift integralin ayrık hali: 3x3 çekirdek iki yönde ters çevir-kaydır — CNN'in conv katmanı (PyTorch conv2d) tam bu" #| fig-width: 12 #| fig-height: 4 #| code-fold: true fig, axes = plt.subplots(1, 3, figsize=(12, 4)) img = make_test_image() edge = conv2d_full(img, SOBEL_X) # Sol: girdi görüntüsü axes[0].imshow(img, cmap="gray") axes[0].set_title("girdi: kare + köşegen şerit", color=COL_TEXT, fontsize=12, fontweight="bold") axes[0].axis("off") # Orta: Sobel-X çekirdeği heatmap heatmap(axes[1], SOBEL_X, title="3x3 çekirdek (Sobel-X, dikey kenar)", cmap=DIVERGE, fmt="{:.0f}") # Sağ: çıktı kenar haritası axes[2].imshow(np.abs(edge), cmap=NAVY_CMAP) axes[2].set_title("çıktı: dikey kenarlar parlar (max 4.21)", color=COL_TEXT, fontsize=12, fontweight="bold") axes[2].axis("off") fig.suptitle("2B evrişim = çift integralin ayrık hali: 3x3 çekirdek iki yönde ters çevir-kaydır — CNN'in conv katmanı (PyTorch conv2d) tam bu", color=COL_TEXT, fontsize=12, fontweight="bold") plt.show() ``` @fig-conv2d 2B evrişimi gerçek bir kenar-dedektörüyle gösterir: solda girdi görüntüsü (parlak kare + köşegen şerit), ortada 3×3 Sobel-X çekirdeği (dikey kenar dedektörü, DIVERGE ısı haritası), sağda `conv2d_full` çıktısı $|$kenar$|$ — dikey kenarlar parlar, max yanıt **4.21**. Çekirdek görüntü boyunca iki yönde ters çevrilip kaydırılır (çift-toplam); bu PyTorch `conv2d`'nin tam yaptığı işlemdir. (Sobel ayrıca **ayrılabilirdir** — kolon $(1,2,1)$ ∗ satır $(1,0,-1)$ evrişimi birebir, §8 Kronecker önizlemesi.) ::: {.callout-tip title="Builder Notu — Çift İntegralin Filtresi"} "2B evrişim = çift integral, iki yönde kaydır" CNN'in çekirdek operasyonu. ML köprüsü: PyTorch `conv2d` tam bu; 3×3 çekirdek tüm görüntü konumlarına uygulanır (ağırlık paylaşımı). fast.ai L15 im2col 2B evrişimi tek bir büyük matris çarpımına açar (GPU için); kenar/doku dedektörleri ilk CNN katmanlarının öğrendiği 2B filtrelerdir. ::: ## 8. Kronecker Çarpımı ve Toplamı {#sec-kronecker} 1B'den 2B'ye geçişin matris aracı **Kronecker çarpımı**: > *"...the MATLAB command is Kron." — Strang, 38:55* İki n×n matris A, B'den n²×n² bir matris üretir; her $a_{ij}$ bloğu B ile çarpılır: $$\text{Kron}(A, B) = \begin{bmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{n1}B & \cdots & a_{nn}B \end{bmatrix} \quad (n^{2} \times n^{2})$$ Örnek: 2B Fourier dönüşümü = Kron(F, F). 2B Laplacian (her iki yönde −1, 2, −1 ikinci fark, 5-nokta şablon): tek Kronecker çarpımı değil, **Kronecker toplamı**: $$\text{Laplacian} = \text{Kron}(A, I) + \text{Kron}(I, A)$$ Kron(A,I) x yönündeki ikinci türevi, Kron(I,A) y yönündekini verir; toplamı 2B Laplacian. ```{python} #| label: fig-kronecker #| fig-cap: "Kronecker çarpımı 1B yapıyı 2B'ye taşır (2B Fourier = Kron(F,F), kimlik 4.4e-16); Laplacian Kronecker TOPLAMIdır — Egz4 köşegeni 2+2 = 4" #| fig-width: 10.5 #| fig-height: 4.4 #| code-fold: true fig, axes = plt.subplots(1, 2, figsize=(10.5, 4.4)) # Sol: Kron(A, I) — her a_ij bloğu I çarpanı A2 = np.array([[2., -1], [-1, 2]]) KAI = np.kron(A2, np.eye(2)) heatmap(axes[0], KAI, title="Kron(A, I): her a_ij bloğu I çarpanı", cmap=DIVERGE, fmt="{:.0f}") axes[0].axhline(1.5, color=COL_WHITE, lw=2) axes[0].axvline(1.5, color=COL_WHITE, lw=2) # Sağ: 2B Laplacian = Kron(A,I)+Kron(I,A), 9x9 (köşegen 4, 5-nokta) L = kron_sum_laplacian(3) heatmap(axes[1], L, title="2B Laplacian = Kron(A,I)+Kron(I,A): köşegen 4, 5-nokta", cmap=DIVERGE, fmt="{:.0f}", fontsize=8) vmin9, vmax9 = float(np.min(L)), float(np.max(L)); thr9 = vmin9 + 0.62*(vmax9-vmin9) for i in range(9): for j in range(9): v = L[i, j] axes[1].text(j, i, "{:.0f}".format(v), ha="center", va="center", color=COL_WHITE if v >= thr9 else COL_TEXT, fontsize=8, fontweight="bold") fig.suptitle("Kronecker çarpımı 1B yapıyı 2B'ye taşır (2B Fourier = Kron(F,F), kimlik 4.4e-16); Laplacian Kronecker TOPLAMIdır — Egz4 köşegeni 2+2 = 4", fontsize=10, color=COL_TEXT) fig.tight_layout() plt.show() ``` @fig-kronecker Kronecker yapısını iki ısı haritasıyla gösterir: solda Kron(A, I) 4×4 — A=[[2,−1],[−1,2]]'nin her $a_{ij}$ girdisi 2×2 birim matrisle çarpılır (sol-üst blok 2I), beyaz çizgiler blok sınırlarını ayırır; sağda 2B Laplacian = Kron(A,I)+Kron(I,A) 9×9 (3×3 ızgara) — köşegende 4, iç satırlarda 5-nokta şablonu {4, −1×4}. Kronecker-vec kimliği $(B \otimes A)\cdot\text{vec}(X) = \text{vec}(AXB^{\top})$ motorda **4.44e-16**; 2B Fourier = Kron(F,F) tanığı ($(F \otimes F)\text{vec}(X) = \text{vec}(FXF^{\top})$, F simetrik) yine **4.44e-16**. Laplacian tek çarpım değil Kronecker **toplamıdır** — Egz4'ün köşegeni 2+2 = 4. ::: {.callout-tip title="Builder Notu — Bloklarla İki Boyut Kurmak"} "Kronecker çarpımı = 2B yapı, Kronecker toplamı = 2B Laplacian" çok-boyutlu operatörlerin matris dili. ML köprüsü: 2B/3B konvolüsyon, ayrılabilir (separable) filtreler (Kron(satır, sütun)), ve tensör işlemleri (PyTorch'ta `kron`) bu yapıyı kullanır; çözünürlük-uzayı yöntemleri (PDE çözücüler, fizik-bilgili ağlar) 2B Laplacian'ı Kronecker toplamıyla kurar. ::: ## Bu Dersin Özeti {#sec-ozet-d32} - **ImageNet/AlexNet (2012):** Krizhevsky-Sutskever-Hinton; CNN %15 hata (devrim); 60M parametre, conv+pool+dropout; CNN az ağırlık (paylaşım). - **Evrişim:** $(c*d)_k = \sum c_i\,d_{k-i}$ (polinom çarpımı); fonksiyon: $(f * g)(x) = \int f(t)\,g(x-t)\,dt$. - **Evrişim kuralı:** sirkülant CD özdeğerleri = $\lambda(C) \odot \lambda(D)$; $F(c \circledast d) = (Fc) \odot (Fd)$. Evrişim → frekansta çarpma. - **İki yol + FFT:** evriş-dönüştür ($O(n^2)$) vs ayrı-dönüştür-çarp ($2n\log n + n$); FFT ikinciyi hızlı kılar. - **2B evrişim:** çift integral $\iint f(t,u)\,g(x-t,y-u)\,dt\,du$; CNN'in conv katmanı. - **Kronecker:** çarpım Kron(A,B) ($n^2 \times n^2$, bloklar $a_{ij}B$) 2B yapı; Laplacian = Kron(A,I)+Kron(I,A) (Kronecker toplamı). ::: {.callout-important title="Tek Bir Cümle"} Evrişim polinom çarpımıdır $(c*d)_k = \sum c_i\,d_{k-i}$; evrişim kuralı onu Fourier'de çarpmaya çevirir ($F(c \circledast d)=(Fc)\odot(Fd)$) ve FFT ile hızlandırır; CNN'ler bu evrişimi ağırlık paylaşımıyla görüntüye uygular (AlexNet), 2B'ye geçiş Kronecker çarpımıyla yapılır. ::: ## Kontrol Soruları {#sec-sorular-d32} ::: {.callout-note collapse="true" title="Soru 1 — AlexNet (2012) neden dönüm noktası ve CNN neden az ağırlık kullanır"} AlexNet ImageNet 2012'de top-5 hatayı %15'e indirdi (ikinci takım %26) — CNN'in görüntü tanımayı dönüştürdüğünü kanıtladı. CNN az ağırlık kullanır çünkü **ağırlık paylaşımı**: aynı filtre (üst-satır ağırlıkları, sirkülant/Toeplitz) tüm konumlara uygulanır — tam $n^2$-ağırlık matrisi yerine küçük bir çekirdek. 60M parametre yine çoktu ama tam-bağlıdan çok azdı. ::: ::: {.callout-note collapse="true" title="Soru 2 — Evrişim neden polinom çarpımıdır"} c ve d'yi polinom katsayıları say ($c_0 + c_1 x + \dots$, $d_0 + d_1 x + \dots$). Çarpımda $x^k$'nin katsayısı, üsleri k'ya toplanan tüm $c_i d_j$ çarpımlarının toplamıdır ($i+j=k$). Bu tam $(c*d)_k = \sum_i c_i\,d_{k-i}$. Yani evrişim = polinom çarpımının katsayıları (kaydır-çarp-topla). ::: ::: {.callout-note collapse="true" title="Soru 3 — Evrişim kuralı nedir ve neden FFT ile hızlıdır"} $F(c \circledast d) = (Fc) \odot (Fd)$: döngüsel evrişimin Fourier dönüşümü = ayrı Fourier dönüşümlerinin bileşen-bileşen çarpımı (sirkülantlar ortak Fourier özvektörlerinde köşegenleşir, özdeğerler çarpılır). FFT ile hızlı: doğrudan evrişim $O(n^2)$; ama "iki kez FFT ($2n\log n$) + bileşen-çarpım (n)" yolu $O(n \log n)$ — büyük n'de çok daha hızlı. ::: ::: {.callout-note collapse="true" title="Soru 4 — Kronecker çarpımı ve toplamı nedir, 2B Laplacian hangisidir"} Kronecker çarpımı Kron(A,B): iki n×n matristen $n^2 \times n^2$ matris, her $a_{ij}$ bloğu B ile çarpılır — 1B'den 2B yapıya geçiş (örn. 2B Fourier = Kron(F,F)). 2B Laplacian tek çarpım değil **Kronecker toplamıdır**: Kron(A,I) + Kron(I,A) — biri x yönündeki ikinci türevi, diğeri y yönündekini verir, toplamı 5-nokta şablonu. ::: ## Egzersizler {#sec-egzersizler-d32} 1. **Evrişim hesabı.** $(1, 2, 3)$ ile $(1, 1)$ vektörlerini evir (sıradan, döngüsüz). Polinom $(1 + 2x + 3x^2)(1 + x)$ çarpımıyla doğrula. (Motor tanığı: $(1,2,3) \ast (1,1) = (1,3,5,3)$, `poly_mult_coeffs` ile birebir; D30 örneği $(3,1,2) \ast (4,6,1) = (12,22,17,13,2)$ de tutarlı.) 2. **Konvolüsyon teoremi.** n=2'de c=(1,1), d=(1,−1). Döngüsel evrişim $c \circledast d$'yi doğrudan hesapla. Sonra Fc, Fd al (F=[[1,1],[1,−1]]), bileşen-bileşen çarp, $F^{-1}$ ile geri dön; aynı sonucu bulduğunu göster. (Motor tanığı: $c \circledast d = (0,0)$ doğrudan; Fourier yolu $Fc=(2,0)$, $Fd=(0,2)$ → $\odot=(0,0)$ → $F^{-1}$ → (0,0). İki yol aynı — ve örnek özel: c, d ayrık frekanslarda yaşar, çarpımları sıfırlanır.) 3. **Maliyet.** n = 1024 için doğrudan evrişim ($n^2$) ve FFT yolu ($2n\log_2 n + n$) kaç işlem? FFT kaç kat hızlı (kabaca)? (Motor tanığı: doğrudan **1.048.576** vs FFT yolu $2 \cdot 1024 \cdot 10 + 1024 = $ **21.504** → oran **48.8×**, kabaca ~50×.) 4. **Kronecker.** A = [[2,−1],[−1,2]] (1B Laplacian, 2×2). Kron(A, I₂) ve Kron(I₂, A)'yı (4×4) yaz. Toplamlarının köşegeninin 4 olduğunu (2+2) göster. (Motor tanığı: Kron(A,I₂)+Kron(I₂,A) köşegeni **(4,4,4,4)**; 3×3 ızgara 2B Laplacian 9×9, iç satır 5-nokta {4, −1×4}.) 5. **(Ders 33 habercisi)** CNN'ler evrişimi katman katman uygular; ama bir sinir ağının "öğrendiği fonksiyon" tam olarak ne, hangi fonksiyonları temsil edebilir? Bir tahmin yaz — Ders 33 "sinir ağları ve öğrenme fonksiyonu"nu (Ders 26'nın derinleşmesi) işliyor. ## Sonraki Ders İçin Hazırlık {#sec-sonraki-d32} **Ders 33: Sinir Ağları ve Öğrenme Fonksiyonu.** Ders 26'nın sinir-ağı yapısını derinleştirir: öğrenme fonksiyonu $F(x, v)$'nin ifade gücü, hangi fonksiyonları öğrenebildiği, ve eğitim (SGD + backprop, Ders 25/27) ile yapının birleşimi. Derin öğrenme bloğunun kapanışına doğru. ::: {.callout-warning title="Hazırlık"} Bu dersin Egzersiz 5'inin sorduğu soruyu zihninde tut: CNN'ler evrişimi katman katman uygularken, bir sinir ağının "öğrendiği fonksiyon" tam olarak ne ve hangi fonksiyonları temsil edebilir? Ders 33, **öğrenme fonksiyonu $F(x, v)$**'yi (Ders 26'nın sinir-ağı yapısının derinleşmesi) işler — ifade gücü, temsil edebildiği fonksiyon sınıfı, ve eğitim (SGD + backprop, Ders 25/27) ile birleşimi. Derin öğrenme bloğunun kapanışına yaklaşıyoruz. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet-d32} | Kavram | Formül / Fikir | Strang (dk) | |--------|----------------|-------------| | **ImageNet/AlexNet** | CNN %15 hata (2012); 60M param; ağırlık paylaşımı | 2m33 | | Evrişim | $(c*d)_k = \sum c_i\,d_{k-i}$; polinom çarpımı | 6m04 | | Fonksiyon evrişimi | $(f * g)(x) = \int f(t)\,g(x-t)\,dt$ | 10m02 | | Evrişim kuralı | $\lambda(CD) = \lambda(C) \odot \lambda(D)$; $F(c \circledast d) = (Fc)\odot(Fd)$ | 28m52 | | İki yol | evriş-dönüştür vs ayrı-dönüştür-çarp | 30m50 | | Maliyet | doğrudan $O(n^2)$ vs FFT yolu $O(n \log n)$ | 35m32 | | 2B evrişim | $\iint f(t,u)\,g(x-t,y-u)\,dt\,du$ | 36m38 | | Kronecker | Kron(A,B) $n^2 \times n^2$; Laplacian = Kron(A,I)+Kron(I,A) | 38m55 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar-d32} - **CNN = ağırlık paylaşımı:** AlexNet (2012) derin öğrenme devrimi; konvolüsyon tam matrisi küçük filtreye indirir; dropout/max pooling/ReLU yaygınlaştı. - **Evrişim = polinom çarpımı = kaydır-çarp-topla:** PyTorch conv2d; fast.ai L15 im2col evrişimi matris çarpımına açar (GPU). - **Konvolüsyon teoremi + FFT:** $F(c \circledast d)=(Fc)\odot(Fd)$; büyük-çekirdek konvolüsyon FFT-conv ile $O(n \log n)$; ses (spektrogram), FNet. - **2B evrişim:** çift integral; CNN'in conv katmanı; kenar/doku dedektörleri ilk katman filtreleri. - **Kronecker:** 1B→2B (Kron(F,F) 2B Fourier); ayrılabilir filtreler; 2B Laplacian = Kronecker toplamı (PDE çözücüler, PINN). - **Geriye köprü:** Ders 30-31 (sirkülant/cyclic convolution/Fourier/FFT), Ders 4 (özdeğer çarpımı). Paralel: fast.ai L15 (conv2d/im2col), NYU H6 (CNN), Karpathy makemore CNN bölümü. ::: {.callout-important title="Kapanış"} > *"...the MATLAB command is Kron." — Strang, 38:55* Evrişim sirkülant/Fourier dünyasından doğar (convolution teoremi + FFT), CNN'ler onu ağırlık paylaşımıyla görüntüye uygular, ve Kronecker çarpımı tüm bunu 2B'ye taşır — sinyal işleme ile derin öğrenmenin buluştuğu nokta. :::