Simples Kemungkinan
Distribusi kemungkinan atas q simbol adalah titik dalam (q−1)-dimensi simples: himpunan semua vektor (p₁, ..., p_q) dengan pᵢ ≥ 0 dan Σ pᵢ = 1.
Untuk q = 2: simples adalah garis segitiga [0,1], di parameter oleh sebuah kemungkinan p. Untuk q = 3: simples adalah segitiga sama sisi di ℝ². Setiap sudut adalah distribusi deterministik (semua kemungkinan pada satu simbol); pusat adalah distribusi seragam.
Entropi H(p) menetapkan sebuah bilangan real pada setiap titik simples. Geometri fungsi tersebut menentukan banyak hasil fundamental.
Konkaf
H adalah konkaf pada simples: untuk dua distribusi p dan q dan λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
Campuran dari dua distribusi memiliki entropi setidaknya sebesar rata-rata berat individu entropi mereka. Intuisi: mencampur dua sumber meningkatkan ketidaktahuan.
Mengverifikasi Konkaf
Untuk entropi biner H(p), konkaf terlihat dalam grafik: kurva melengkung ke atas, tidak pernah jatuh di bawah apa pun garis lurus yang menghubungkan dua titik.
Uji formal untuk konkaf: turunan kedua H''(p) ≤ 0 di mana-mana.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 untuk semua p ∈ (0,1)
Turunan kedua negatif di mana-mana di dalam: H konkaf ketat.
Distribusi yang Mencapai Kapasitas
Kapasitas saluran didefinisikan sebagai mutual information maksimum atas semua distribusi input p(x):
C = max_{p(x)} I(X; Y)
di mana I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
Untuk saluran biner simetri dengan probabilitas kesalahan Q: distribusi input yang mencapai kapasitas adalah distribusi seragam p(0) = p(1) = 0.5.
Mengapa: H(Y) maksimum dengan distribusi output seragam. Dengan BSC, input seragam menghasilkan distribusi output seragam. Distribusi input lain membuat H(Y) lebih kecil, mengurangi I(X;Y).
Geometris: mutual information I(X;Y) adalah fungsi concave dari distribusi input p(x) pada simples. Maksimum dari fungsi concave pada himpunan convex dicapai pada titik unik (tengah, untuk saluran simetri).
Divergensi KL
Divergensi Kullback-Leibler (entropi relatif) dari distribusi q ke distribusi p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 selalu (kesatuan Gibbs). D(p || q) = 0 jika dan hanya jika p = q.
D adalah bukan jarak sebenarnya: itu tidak simetris (D(p||q) ≠ D(q||p) pada umumnya) dan tidak memenuhi ketidaksetaraan segitiga. Namun, itu berfungsi sebagai ukuran seberapa 'jauh' p dari q di ruang probabilitas.
Divergensi KL muncul di seluruh teori informasi:
- Informasi mutual: I(X;Y) = D(p(x,y) || p(x)p(y)). Informasi mutual adalah divergensi KL antara distribusi bersama dan produk marginals — seberapa jauh distribusi bersama dari independen.
- Kesatuan Gibbs: teorema pengodean bebas dari D(p || q) ≥ 0.
- Kapasitas saluran: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
Menghitung Divergensi KL
Contoh: p = (0.5, 0.5) biner seragam, q = (0.8, 0.2) biner bias.
D(p || q) = 0.5 log₂(0.5/0.8) + 0.5 log₂(0.5/0.2)
= 0.5 log₂(0.625) + 0.5 log₂(2.5)
≈ 0.5 × (−0.678) + 0.5 × 1.322 ≈ −0.339 + 0.661 ≈ 0.322 bit
Kapasitas Saluran sebagai Jarak Geometrik
Kapasitas saluran memiliki interpretasi geometrik dalam ruang distribusi probabilitas.
Untuk saluran p(y|x), definisikan distribusi input memiliki kapasitas p*(x). Kapasitas memenuhi:
C = D(p*(y) || r(y))
di mana p(y) = Σ p(x) p(y|x) adalah distribusi output di bawah input optimal, dan r(y) = argmin_r max_x D(p(y|x) || r(y)) adalah distribusi output dengan informasi terendah — titik dalam ruang probabilitas output terdekat (dalam divergensi KL) dari semua distribusi output kondisional secara bersamaan.
Ini adalah pandangan geometrik informasi : kapasitas saluran adalah jari-jari bola KL-divergence terkecil dalam ruang distribusi output yang mengandung semua distribusi kondisional p(y|x=0) dan p(y|x=1).
Untuk BSC: p(y|x=0) = (1−Q, Q) dan p(y|x=1) = (Q, 1−Q). Dengan simetri, distribusi output terinformasi terendah r(y) = (0.5, 0.5). Kapasitas = D((1−Q, Q) || (0.5, 0.5)) = 1 − H(Q). Rumus ini menghasilkan hasil standar dari geometri.
Kapasitas dari Divergensi KL
Verifikasi rumus geometrik: C = D(p(y|x=0) || r(y)) untuk BSC dengan Q = 0.1, r(y) = (0.5, 0.5).
p(y|x=0) = (0.9, 0.1) (kirim 0, terima 0 dengan probabilitas 0.9, terima 1 dengan probabilitas 0.1).
D((0.9, 0.1) || (0.5, 0.5)) = 0.9 log₂(0.9/0.5) + 0.1 log₂(0.1/0.5)
= 0.9 log₂(1.8) + 0.1 log₂(0.2)
log₂(1.8) ≈ 0.848, log₂(0.2) ≈ −2.322
= 0.9×0.848 + 0.1×(−2.322) ≈ 0.763 − 0.232 ≈ 0.531 bit
Periksa: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 bit ✓
Rate-Distortion & Batas-Batas Pengkompresian
Teori rate-distorsi memperluas teori informasi ke pengkompresian hilang. Sebagai ganti mengajukan 'apa yang merupakan bit-bit minimum untuk mewakili sumber dengan akurat?', itu bertanya: 'dengan toleransi rata-rata distorsi D, apa yang merupakan rate minimum R(D) bit per simbol?'
Fungsi rate-distorsi R(D) adalah konveks dan menurun dalam D: toleransi lebih banyak distorsi memungkinkan rate yang lebih rendah. Di D = 0 (tanpa kehilangan): R(0) = H(sumber). Saat D meningkat, R(D) → 0.
Geometris: R(D) mengikuti kurva pada ruang (rate, distorsi). Setiap pasangan (R, D) yang dapat dicapai terletak di atau di atas kurva ini. Titik di bawah kurva tidak mungkin — Anda tidak dapat mengkompresi di bawah batas fundamental pada setiap tingkat distorsi.
Teorema rate-distorsi (Shannon, 1959): untuk setiap R > R(D), kode-kode ada yang mencapai distorsi rata-rata tidak lebih dari D. Untuk R < R(D): tidak ada kode yang mencapai distorsi D. Kurva adalah batas geometri di ruang (rate, distorsi).