29 Eşitsizlikler

Cauchy-Schwarz, Jensen, Markov, Chebyshev

Bölüm bilgisi

Blitzstein’in videosu: YouTube — Lecture 28 (≈47 dk)
Okuma süresi: ≈22 dk

29.1 Bu Derste Ne Var?

Rassal toplam: $X = \sum_{j=1}^N X_j$, Adam + Eve.
Cauchy-Schwarz: $|E(XY)| \le \sqrt{E(X^2) E(Y^2)}$.
Jensen: dışbükey $g$ → $E(g(X)) \ge g(E(X))$.
Markov: $P(|X| \ge a) \le E|X|/a$.
Chebyshev: $P(|X - \mu| \ge a) \le \sigma^2/a^2$.

Builder Notu — ML Köprüleri

Eşitsizlik ≠ yaklaşım → PAC, generalization bound; kanıtlanmış sınır > tahmin.
Markov → Chebyshev → Chernoff → Hoeffding zinciri = konsantrasyon eşitsizlikleri ailesi.
Jensen → ELBO = variational inference temeli (VAE, diffusion).
Cauchy-Schwarz → kosinüs benzerliği (attention dot product).
Chebyshev → BSY → örneklem büyüklüğü $\sigma^2/(n\epsilon^2)$.

29.2 Rassal Toplam: Adam + Eve

$X = \sum_{j=1}^N X_j$, $N \perp X_j$, $E(X_j) = \mu$, Var$(X_j) = \sigma^2$.

Naif hata: $E(X) = N\mu$ — kategori hatası ($N$ RV!).

Adam: $E(X | N) = \mu N$ → $E(X) = \mu E(N)$.

Eve:

\[ \text{Var}(X) = \sigma^2 E(N) + \mu^2 \text{Var}(N) \]

29.3 Cauchy-Schwarz

\[ |E(XY)| \le \sqrt{E(X^2)\, E(Y^2)} \]

= korelasyon $\in [-1, 1]$ (yeniden).

Builder Notu — Embedding Benzerlik

$E(XY)$ = iç çarpım, $\sqrt{E(X^2)}$ = norm → RV’ler Hilbert uzayı. Attention nokta çarpımı, kosinüs benzerliği $[-1, 1]$’de kalmasının garantisi.

29.4 Jensen Eşitsizliği

Dışbükey $g$ ($g'' \ge 0$):

\[ E(g(X)) \ge g(E(X)) \]

İçbükeyse ($\ln, \sqrt{\cdot}$) yön döner.

İspat (teğet doğrusu): $g(x) \ge a + bx$ tüm $x$ (dışbükeylik). Beklenti al.

Örnekler:

$g(x) = x^2$: $E(X^2) \ge (E(X))^2$ (varyans $\ge 0$).
$g(x) = 1/x$ ($x > 0$): $E(1/X) \ge 1/E(X)$ (oran tahmincisi yanlılığı).
$\ln$: $E(\ln X) \le \ln E(X)$.

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(-2, 4, 200)
g = x**2

fig, ax = plt.subplots(figsize=(9, 5))
ax.plot(x, g, color='#1f2937', linewidth=2.5, label='g(x) = x² (dışbükey)')

# X = -1 veya 3, eşit olası
xs = np.array([-1, 3])
gs = xs**2
EX = xs.mean()  # 1
EgX = gs.mean()  # 5
gEX = EX**2  # 1

ax.plot(xs, gs, 'o', color='#A51C30', markersize=14, label='X değerleri')
ax.plot([xs[0], xs[1]], [gs[0], gs[1]], '--', color='#A51C30', linewidth=1.5,
        label='ortalama doğru (chord)')
ax.plot(EX, EgX, 's', color='#15803d', markersize=14, label=f'E(g(X)) = {EgX} (orta)')
ax.plot(EX, gEX, 'D', color='#2C5282', markersize=14, label=f'g(E(X)) = {gEX} (eğri üstü)')
ax.annotate('', xy=(EX, EgX), xytext=(EX, gEX),
            arrowprops=dict(arrowstyle='<->', color='#DD6B20', lw=2))
ax.text(EX + 0.15, 3, 'Jensen\nE(g) ≥ g(E)', color='#9a3412', fontsize=12, weight='bold')

ax.set_xlabel('x', fontsize=12)
ax.set_ylabel('g(x) = x²', fontsize=12)
ax.set_title('Jensen — dışbükey g için E(g(X)) ≥ g(E(X))', fontsize=12)
ax.legend(loc='upper left', fontsize=10)
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Şekil 29.1

Builder Notu — ELBO ve Cross-Entropy

Jensen ML’de her yerde: (1) ELBO: $\log E[\cdot] \ge E[\log \cdot]$ → variational inference (VAE, diffusion); (2) AM-GM eşitsizliği; (3) oran tahmincisi yanlılığı; (4) karar ağacı bölme kriterleri (Gini, entropi). ELBO = Jensen.

29.5 Markov Eşitsizliği

\[ P(|X| \ge a) \le \frac{E|X|}{a}, \quad a > 0 \]

Hiçbir varsayım yok (X ≥ 0 dışında).

İspat (gösterge): $a \cdot \mathbb{1}_{|X| \ge a} \le |X|$ her durumda. Beklenti al.

Builder Notu — Konsantrasyonun Atası

Markov = tüm konsantrasyon eşitsizliklerinin atası. Chebyshev (kareyle), Chernoff (MGF’yle), Hoeffding, Bernstein — hepsi “negatif olmayan dönüşüme Markov uygula” tarifi. ML’de SGD yakınsama garantisi, diferansiyel mahremiyet gürültü kuyruğu hep Markov ile başlar.

29.6 Chebyshev Eşitsizliği

\[ P(|X - \mu| \ge a) \le \frac{\sigma^2}{a^2} \]

Veya $a = c\sigma$:

\[ P(|X - \mu| \ge c\sigma) \le \frac{1}{c^2} \]

İspat: Markov’u $(X - \mu)^2 \ge a^2$ olayına uygula.

Builder Notu — BSY Motoru

Chebyshev = BSY’nin motoru. $\bar{X}_n$’in varyansı $\sigma^2/n$ → $P(|\bar{X}_n - \mu| \ge \epsilon) \le \sigma^2/(n\epsilon^2) \to 0$. Monte Carlo yakınsama hızı, A/B test örneklem büyüklüğü, minibatch gradyan kalitesi hep bu ölçeklemeden.

29.7 Bu Dersin Özeti

Rassal toplam: $E = \mu E(N)$, Var $= \sigma^2 E(N) + \mu^2$ Var($N$).
Cauchy-Schwarz: korelasyon $[-1, 1]$.
Jensen: dışbükey → yönü hatırla.
Markov: $P \le E/a$.
Chebyshev: $P \le \sigma^2/a^2$.

Tek bir cümle

Dağılımı bilmesen bile dört eşitsizlik kanıtlanmış sınır verir. Markov → Chebyshev = BSY motoru = ML’de konsantrasyon ailesinin atası; Jensen → ELBO = variational inference temeli; Cauchy-Schwarz = embedding benzerlik garantisi.

29.8 Kontrol Soruları

Soru 1: E(X) = Nμ neden yanlış?

Cevap: Kategori hatası — $E(X)$ sayı, $N\mu$ RV. Doğru: $\mu E(N)$.

Soru 2: Rassal toplam Var iki terimi neyi temsil eder?

Cevap: Aleatorik (her müşterinin gürültüsü) + yapısal ($N$ belirsizliği).

Soru 3: X > 0. E(1/X) vs 1/E(X)?

Cevap: $E(1/X) \ge 1/E(X)$ (Jensen, $1/x$ dışbükey).

Soru 4: Chebyshev c=3 vs Normal?

Cevap: Chebyshev $\le 1/9 \approx 0{,}111$ her dağılım için. Normal $\approx 0{,}003$. Evrenselliğin bedeli kabalık.

29.9 Egzersizler

Egzersiz 1. Bileşik Poisson: $N \sim$ Pois($\lambda$), $E(X), \text{Var}(X)$.

Egzersiz 2. $X \ge 0, E(X) = 2$. Markov $P(X \ge 8)$ ≤ ? vs Exp(1/2) gerçek.

Egzersiz 3. Adil para $n$ atış. Chebyshev ile $P(|\bar{X}_n - 0{,}5| \ge 0{,}1) \le 0{,}05$ için $n$?

Egzersiz 4. (Python — Markov + Chebyshev + Jensen)

import numpy as np
rng = np.random.default_rng(0)
N = 1_000_000
X = rng.exponential(scale=2.0, size=N)
mu, sigma = X.mean(), X.std()

# Markov
print(f"Markov: E|X| = {X.mean():.3f}")
for a in [4, 6, 8]:
    print(f"  a={a}: P(X≥a) gerçek={np.mean(X>=a):.4f}  ≤ {X.mean()/a:.4f}")

# Chebyshev
print(f"\nChebyshev: μ={mu:.2f}, σ={sigma:.2f}")
for c in [1, 2, 3]:
    print(f"  c={c}: P(|X-μ|≥cσ) gerçek={np.mean(np.abs(X-mu) >= c*sigma):.4f}  ≤ {1/c**2:.4f}")

# Jensen
print(f"\nJensen: E(1/X) = {np.mean(1/X):.4f}  ≥ 1/E(X) = {1/mu:.4f}")

Egzersiz 5. (Sonraki ders) BSY: Chebyshev ile $\bar{X}_n \to \mu$. MLT: $\bar{X}_n - \mu$ normal şekilde dalgalanır.

29.10 Sonraki Ders İçin Hazırlık

Ders 29: BSY ve MLT — Chebyshev kullanılacak.

Ders 29 öncesi yapılacak

Egzersiz 5 (BSY/MLT sezgi) çöz.
Chebyshev tekrar oku.

29.11 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Not
Rassal toplam E	$\mu E(N)$	Adam
Rassal toplam Var	$\sigma^2 E(N) + \mu^2$ Var($N$)	Eve
Cauchy-Schwarz	$\\|E(XY)\\| \le \sqrt{E(X^2)E(Y^2)}$	Corr $\in [-1,1]$
Jensen	$g$ dışbükey → $E(g) \ge g(E)$	ELBO
Markov	$P(\\|X\\| \ge a) \le E\\|X\\|/a$	Atası
Chebyshev	$P(\\|X-\mu\\| \ge a) \le \sigma^2/a^2$	BSY motoru

29.12 ML Bağlantıları Özeti

6 köprü

Eşitsizlik ≠ yaklaşım → PAC, garanti.
Markov → Chernoff → Hoeffding → konsantrasyon ailesi.
Jensen → ELBO → VAE, diffusion.
Cauchy-Schwarz → embedding, attention.
Eve → aleatoric + epistemic.
Chebyshev → BSY → örneklem $\sigma^2/(n\epsilon^2)$.

Tek bir şey alıp gideceksen

Dağılımı bilmesen bile dört eşitsizlik kanıtlanmış sınır verir. Markov-Chebyshev = BSY + konsantrasyon ailesi. Jensen = ELBO. Cauchy-Schwarz = embedding garantisi.

--- title: "Eşitsizlikler" subtitle: "Cauchy-Schwarz, Jensen, Markov, Chebyshev" --- ::: {.callout-note title="Bölüm bilgisi"} - **Blitzstein'in videosu:** [YouTube — Lecture 28](https://www.youtube.com/watch?v=UtXK_EQ3Pow) (≈47 dk) - **Okuma süresi:** ≈22 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} 1. **Rassal toplam:** $X = \sum_{j=1}^N X_j$, Adam + Eve. 2. **Cauchy-Schwarz:** $|E(XY)| \le \sqrt{E(X^2) E(Y^2)}$. 3. **Jensen:** dışbükey $g$ → $E(g(X)) \ge g(E(X))$. 4. **Markov:** $P(|X| \ge a) \le E|X|/a$. 5. **Chebyshev:** $P(|X - \mu| \ge a) \le \sigma^2/a^2$. ::: {.callout-tip title="Builder Notu — ML Köprüleri"} - **Eşitsizlik ≠ yaklaşım** → **PAC**, generalization bound; kanıtlanmış sınır > tahmin. - **Markov → Chebyshev → Chernoff → Hoeffding** zinciri = **konsantrasyon eşitsizlikleri** ailesi. - **Jensen → ELBO** = variational inference temeli (VAE, diffusion). - **Cauchy-Schwarz → kosinüs benzerliği** (attention dot product). - **Chebyshev → BSY → örneklem büyüklüğü** $\sigma^2/(n\epsilon^2)$. ::: ## Rassal Toplam: Adam + Eve {#sec-rassal-toplam} $X = \sum_{j=1}^N X_j$, $N \perp X_j$, $E(X_j) = \mu$, Var$(X_j) = \sigma^2$. **Naif hata:** $E(X) = N\mu$ — kategori hatası ($N$ RV!). **Adam:** $E(X | N) = \mu N$ → $E(X) = \mu E(N)$. **Eve:** $$ \text{Var}(X) = \sigma^2 E(N) + \mu^2 \text{Var}(N) $$ ## Cauchy-Schwarz {#sec-cauchy-schwarz} $$ |E(XY)| \le \sqrt{E(X^2)\, E(Y^2)} $$ = **korelasyon $\in [-1, 1]$** (yeniden). ::: {.callout-tip title="Builder Notu — Embedding Benzerlik"} $E(XY)$ = iç çarpım, $\sqrt{E(X^2)}$ = norm → RV'ler **Hilbert uzayı**. **Attention nokta çarpımı**, **kosinüs benzerliği** $[-1, 1]$'de kalmasının garantisi. ::: ## Jensen Eşitsizliği {#sec-jensen} **Dışbükey** $g$ ($g'' \ge 0$): $$ E(g(X)) \ge g(E(X)) $$ İçbükeyse ($\ln, \sqrt{\cdot}$) yön döner. **İspat (teğet doğrusu):** $g(x) \ge a + bx$ tüm $x$ (dışbükeylik). Beklenti al. **Örnekler:** - $g(x) = x^2$: $E(X^2) \ge (E(X))^2$ (varyans $\ge 0$). - $g(x) = 1/x$ ($x > 0$): $E(1/X) \ge 1/E(X)$ (oran tahmincisi yanlılığı). - $\ln$: $E(\ln X) \le \ln E(X)$. ```{python} #| label: fig-jensen #| fig-cap: "Jensen: dışbükey g(x) = x² için E(g(X)) ≥ g(E(X)). Iki nokta + olasılıkla seç → ortalama nokta eğrinin üstünde. ELBO/cross-entropy/aritmetik-geometrik eşitsizlik hep Jensen." #| fig-width: 9 #| fig-height: 5 import numpy as np import matplotlib.pyplot as plt x = np.linspace(-2, 4, 200) g = x**2 fig, ax = plt.subplots(figsize=(9, 5)) ax.plot(x, g, color='#1f2937', linewidth=2.5, label='g(x) = x² (dışbükey)') # X = -1 veya 3, eşit olası xs = np.array([-1, 3]) gs = xs**2 EX = xs.mean() # 1 EgX = gs.mean() # 5 gEX = EX**2 # 1 ax.plot(xs, gs, 'o', color='#A51C30', markersize=14, label='X değerleri') ax.plot([xs[0], xs[1]], [gs[0], gs[1]], '--', color='#A51C30', linewidth=1.5, label='ortalama doğru (chord)') ax.plot(EX, EgX, 's', color='#15803d', markersize=14, label=f'E(g(X)) = {EgX} (orta)') ax.plot(EX, gEX, 'D', color='#2C5282', markersize=14, label=f'g(E(X)) = {gEX} (eğri üstü)') ax.annotate('', xy=(EX, EgX), xytext=(EX, gEX), arrowprops=dict(arrowstyle='<->', color='#DD6B20', lw=2)) ax.text(EX + 0.15, 3, 'Jensen\nE(g) ≥ g(E)', color='#9a3412', fontsize=12, weight='bold') ax.set_xlabel('x', fontsize=12) ax.set_ylabel('g(x) = x²', fontsize=12) ax.set_title('Jensen — dışbükey g için E(g(X)) ≥ g(E(X))', fontsize=12) ax.legend(loc='upper left', fontsize=10) ax.grid(True, alpha=0.3) plt.tight_layout() plt.show() ``` ::: {.callout-important title="Builder Notu — ELBO ve Cross-Entropy"} **Jensen ML'de her yerde:** (1) **ELBO**: $\log E[\cdot] \ge E[\log \cdot]$ → variational inference (**VAE, diffusion**); (2) AM-GM eşitsizliği; (3) oran tahmincisi yanlılığı; (4) karar ağacı bölme kriterleri (Gini, entropi). **ELBO = Jensen**. ::: ## Markov Eşitsizliği {#sec-markov} $$ P(|X| \ge a) \le \frac{E|X|}{a}, \quad a > 0 $$ **Hiçbir varsayım yok** (X ≥ 0 dışında). **İspat (gösterge):** $a \cdot \mathbb{1}_{|X| \ge a} \le |X|$ her durumda. Beklenti al. ::: {.callout-tip title="Builder Notu — Konsantrasyonun Atası"} **Markov = tüm konsantrasyon eşitsizliklerinin atası**. Chebyshev (kareyle), **Chernoff** (MGF'yle), **Hoeffding**, Bernstein — hepsi "negatif olmayan dönüşüme Markov uygula" tarifi. ML'de **SGD yakınsama garantisi**, **diferansiyel mahremiyet** gürültü kuyruğu hep Markov ile başlar. ::: ## Chebyshev Eşitsizliği {#sec-chebyshev} $$ P(|X - \mu| \ge a) \le \frac{\sigma^2}{a^2} $$ Veya $a = c\sigma$: $$ P(|X - \mu| \ge c\sigma) \le \frac{1}{c^2} $$ **İspat:** Markov'u $(X - \mu)^2 \ge a^2$ olayına uygula. ::: {.callout-important title="Builder Notu — BSY Motoru"} **Chebyshev = BSY'nin motoru.** $\bar{X}_n$'in varyansı $\sigma^2/n$ → $P(|\bar{X}_n - \mu| \ge \epsilon) \le \sigma^2/(n\epsilon^2) \to 0$. **Monte Carlo yakınsama hızı**, **A/B test örneklem büyüklüğü**, **minibatch gradyan kalitesi** hep bu ölçeklemeden. ::: ## Bu Dersin Özeti {#sec-ozet} 1. **Rassal toplam:** $E = \mu E(N)$, Var $= \sigma^2 E(N) + \mu^2$ Var($N$). 2. **Cauchy-Schwarz:** korelasyon $[-1, 1]$. 3. **Jensen:** dışbükey → yönü hatırla. 4. **Markov:** $P \le E/a$. 5. **Chebyshev:** $P \le \sigma^2/a^2$. ::: {.callout-important title="Tek bir cümle"} **Dağılımı bilmesen bile** dört eşitsizlik kanıtlanmış sınır verir. **Markov → Chebyshev** = **BSY motoru** = ML'de **konsantrasyon ailesinin** atası; **Jensen → ELBO** = variational inference temeli; **Cauchy-Schwarz** = embedding benzerlik garantisi. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: E(X) = Nμ neden yanlış?"} **Cevap:** Kategori hatası — $E(X)$ sayı, $N\mu$ RV. Doğru: $\mu E(N)$. ::: ::: {.callout-note collapse="true" title="Soru 2: Rassal toplam Var iki terimi neyi temsil eder?"} **Cevap:** Aleatorik (her müşterinin gürültüsü) + yapısal ($N$ belirsizliği). ::: ::: {.callout-note collapse="true" title="Soru 3: X > 0. E(1/X) vs 1/E(X)?"} **Cevap:** $E(1/X) \ge 1/E(X)$ (Jensen, $1/x$ dışbükey). ::: ::: {.callout-note collapse="true" title="Soru 4: Chebyshev c=3 vs Normal?"} **Cevap:** Chebyshev $\le 1/9 \approx 0{,}111$ her dağılım için. Normal $\approx 0{,}003$. Evrenselliğin bedeli kabalık. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** Bileşik Poisson: $N \sim$ Pois($\lambda$), $E(X), \text{Var}(X)$. **Egzersiz 2.** $X \ge 0, E(X) = 2$. Markov $P(X \ge 8)$ ≤ ? vs Exp(1/2) gerçek. **Egzersiz 3.** Adil para $n$ atış. Chebyshev ile $P(|\bar{X}_n - 0{,}5| \ge 0{,}1) \le 0{,}05$ için $n$? **Egzersiz 4.** *(Python — Markov + Chebyshev + Jensen)* ```{python} #| label: ex-esitsizlikler #| code-fold: false import numpy as np rng = np.random.default_rng(0) N = 1_000_000 X = rng.exponential(scale=2.0, size=N) mu, sigma = X.mean(), X.std() # Markov print(f"Markov: E|X| = {X.mean():.3f}") for a in [4, 6, 8]: print(f" a={a}: P(X≥a) gerçek={np.mean(X>=a):.4f} ≤ {X.mean()/a:.4f}") # Chebyshev print(f"\nChebyshev: μ={mu:.2f}, σ={sigma:.2f}") for c in [1, 2, 3]: print(f" c={c}: P(|X-μ|≥cσ) gerçek={np.mean(np.abs(X-mu) >= c*sigma):.4f} ≤ {1/c**2:.4f}") # Jensen print(f"\nJensen: E(1/X) = {np.mean(1/X):.4f} ≥ 1/E(X) = {1/mu:.4f}") ``` **Egzersiz 5.** *(Sonraki ders)* **BSY:** Chebyshev ile $\bar{X}_n \to \mu$. **MLT:** $\bar{X}_n - \mu$ normal şekilde dalgalanır. ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 29: BSY ve MLT** — Chebyshev kullanılacak. ::: {.callout-warning title="Ders 29 öncesi yapılacak"} - Egzersiz 5 (BSY/MLT sezgi) çöz. - Chebyshev tekrar oku. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Not | |--------|-------|------| | **Rassal toplam E** | $\mu E(N)$ | Adam | | **Rassal toplam Var** | $\sigma^2 E(N) + \mu^2$ Var($N$) | Eve | | **Cauchy-Schwarz** | $\|E(XY)\| \le \sqrt{E(X^2)E(Y^2)}$ | Corr $\in [-1,1]$ | | **Jensen** | $g$ dışbükey → $E(g) \ge g(E)$ | ELBO | | **Markov** | $P(\|X\| \ge a) \le E\|X\|/a$ | Atası | | **Chebyshev** | $P(\|X-\mu\| \ge a) \le \sigma^2/a^2$ | BSY motoru | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="6 köprü"} 1. **Eşitsizlik ≠ yaklaşım** → PAC, garanti. 2. **Markov → Chernoff → Hoeffding** → konsantrasyon ailesi. 3. **Jensen → ELBO** → VAE, diffusion. 4. **Cauchy-Schwarz** → embedding, attention. 5. **Eve** → aleatoric + epistemic. 6. **Chebyshev → BSY → örneklem** $\sigma^2/(n\epsilon^2)$. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} **Dağılımı bilmesen bile** dört eşitsizlik **kanıtlanmış sınır** verir. Markov-Chebyshev = BSY + konsantrasyon ailesi. Jensen = ELBO. Cauchy-Schwarz = embedding garantisi. :::