प्रायिकता सिम्प्लेक्स
q प्रतीकों पर एक प्रायिकता वितरण (q−1)-आयामी सिम्प्लेक्स में एक बिंदु है: सभी सदिशों (p₁, ..., p_q) का समुच्चय जिसमें pᵢ ≥ 0 और Σ pᵢ = 1।
q = 2 के लिए: सिम्प्लेक्स एक रेखा खंड [0,1] है, जिसे एक एकल प्रायिकता p द्वारा पैरामीट्रिज़ किया जाता है। q = 3 के लिए: सिम्प्लेक्स ℝ² में एक समबाहु त्रिभुज है। प्रत्येक कोना एक नियतात्मक वितरण है (सभी प्रायिकता एक प्रतीक पर); केंद्र एकसमान वितरण है।
एंट्रॉपी H(p) सिम्प्लेक्स के प्रत्येक बिंदु को एक वास्तविक संख्या निर्दिष्ट करती है। फ़ंक्शन की ज्यामिति कई मौलिक परिणामों को निर्धारित करती है।
अवतलता
H सिम्प्लेक्स पर अवतल है: किन्हीं दो वितरणों p और q और किन्हीं λ ∈ [0,1] के लिए:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
दो वितरणों का एक मिश्रण कम से कम उनकी व्यक्तिगत एंट्रॉपी के भारित औसत जितनी बड़ी एंट्रॉपी रखता है। अंतर्ज्ञान: दो स्रोतों को मिश्रित करने से अनिश्चितता बढ़ती है।
अवतलता की पुष्टि
बाइनरी एंट्रॉपी H(p) के लिए, अवतलता ग्राफ़ में दृश्यमान है: वक्र ऊपर की ओर झुका हुआ है, कभी भी दो बिंदुओं को जोड़ने वाली किसी भी जीवा के नीचे नहीं आता।
अवतलता के लिए औपचारिक परीक्षण: द्वितीय अवकलज H''(p) ≤ 0 हर जगह।
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 सभी p ∈ (0,1) के लिए
द्वितीय अवकलज अंदरूनी हिस्से में हर जगह कठोरतः ऋणात्मक है: H कठोरतः अवतल है।
क्षमता-प्राप्त वितरण
चैनल क्षमता को सभी इनपुट वितरणों p(x) पर पारस्परिक सूचना के अधिकतम के रूप में परिभाषित किया गया है:
C = max_{p(x)} I(X; Y)
जहां I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y)।
बाइनरी सममित चैनल के लिए त्रुटि संभावना Q के साथ: क्षमता-प्राप्त इनपुट वितरण एकसमान वितरण p(0) = p(1) = 0.5 है।
क्यों: H(Y) एकसमान आउटपुट वितरण द्वारा अधिकतमीकृत है। एक BSC के साथ, एकसमान इनपुट एकसमान आउटपुट देता है। कोई अन्य इनपुट वितरण H(Y) को छोटा बनाता है, I(X;Y) को कम करता है।
ज्यामितीय रूप से: पारस्परिक सूचना I(X;Y) सिम्प्लेक्स पर इनपुट वितरण p(x) में एक अवतल कार्य है। एक उत्तल समुच्चय पर एक अवतल कार्य का अधिकतम एक अनोखे बिंदु पर प्राप्त होता है (सममित चैनल के लिए केंद्र)।
KL विचलन
वितरण q से वितरण p का कुलबैक-लीबलर विचलन (सापेक्ष एंट्रॉपी):
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 हमेशा (गिब्स असमानता)। D(p || q) = 0 यदि और केवल यदि p = q।
D एक सच्ची दूरी नहीं है: यह असममित है (सामान्य रूप से D(p||q) ≠ D(q||p)) और त्रिभुज असमानता को संतुष्ट नहीं करता है। लेकिन यह प्रायिकता स्पेस में p कितना 'दूर' q से है इसका एक उपाय के रूप में कार्य करता है।
KL विचलन सूचना सिद्धांत में हर जगह दिखाई देता है:
- पारस्परिक सूचना: I(X;Y) = D(p(x,y) || p(x)p(y))। पारस्परिक सूचना संयुक्त वितरण और सीमांत वितरण के गुणनफल के बीच KL विचलन है — संयुक्त कितना दूर है स्वतंत्रता से।
- गिब्स असमानता: शोरहीन कोडिंग प्रमेय सीधे D(p || q) ≥ 0 से अनुसरण करता है।
- चैनल क्षमता: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y))।
KL विचलन की गणना
उदाहरण: p = (0.5, 0.5) एकसमान बाइनरी, q = (0.8, 0.2) पक्षपातपूर्ण बाइनरी।
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 बिट्स
चैनल क्षमता ज्यामितीय दूरी के रूप में
चैनल क्षमता का प्रायिकता वितरण के स्पेस में एक ज्यामितीय व्याख्या है।
एक चैनल p(y|x) के लिए, क्षमता-प्राप्त इनपुट वितरण p*(x) को परिभाषित करें। क्षमता संतुष्ट करती है:
C = D(p*(y) || r(y))
जहां p(y) = Σ p(x) p(y|x) इष्टतम इनपुट के तहत आउटपुट वितरण है, और r(y) = argmin_r max_x D(p(y|x) || r(y)) न्यूनतम-सूचना आउटपुट वितरण है — आउटपुट प्रायिकता स्पेस में वह बिंदु जो सभी सशर्त आउटपुट वितरण p(y|x=0) और p(y|x=1) के लिए एक साथ KL विचलन में निकटतम है।
यह सूचना-ज्यामितीय दृष्टि है: चैनल क्षमता आउटपुट वितरण स्पेस में सबसे छोटी KL-विचलन गेंद की त्रिज्या है जो सभी सशर्त वितरण p(y|x=0) और p(y|x=1) को शामिल करती है।
BSC के लिए: p(y|x=0) = (1−Q, Q) और p(y|x=1) = (Q, 1−Q)। समरूपता द्वारा, न्यूनतम-सूचना आउटपुट r(y) = (0.5, 0.5)। क्षमता = D((1−Q, Q) || (0.5, 0.5)) = 1 − H(Q)। सूत्र मानक परिणाम को ज्यामिति से पुनः प्राप्त करता है।
KL विचलन से क्षमता
ज्यामितीय सूत्र की पुष्टि करें: C = D(p(y|x=0) || r(y)) Q = 0.1 के साथ BSC के लिए, r(y) = (0.5, 0.5)।
p(y|x=0) = (0.9, 0.1) (0 भेजें, संभावना 0.9 के साथ 0 प्राप्त करें, संभावना 0.1 के साथ 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 बिट्स
जांचें: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 बिट्स ✓
दर-विरूपण & संपीड़न की सीमाएं
दर-विरूपण सिद्धांत सूचना सिद्धांत को हानिपूर्ण संपीड़न तक विस्तारित करता है। इसके बजाय कि 'स्रोत को सटीक रूप से प्रतिनिधित्व करने के लिए न्यूनतम बिट्स क्या है?' यह पूछता है: 'कुछ औसत विरूपण D के लिए सहनशीलता को देखते हुए, न्यूनतम दर R(D) बिट्स प्रति प्रतीक क्या है?'
दर-विरूपण कार्य R(D) उत्तल और घटता D में है: अधिक विरूपण सहनशीलता कम दरों की अनुमति देती है। D = 0 पर (हानिरहित): R(0) = H(स्रोत)। जैसे-जैसे D बढ़ता है, R(D) → 0।
ज्यामितीय रूप से: R(D) (दर, विरूपण) विमान पर एक वक्र को ट्रेस करता है। हर प्राप्य (R, D) जोड़ी इस वक्र पर या ऊपर स्थित है। वक्र के नीचे के बिंदु असंभव हैं — आप किसी भी विरूपण स्तर पर मौलिक सीमा के नीचे संपीड़ित नहीं कर सकते।
दर-विरूपण प्रमेय (शैनन, 1959): किसी भी R > R(D) के लिए, कोड अस्तित्व में हैं जो D पर सबसे अधिक की अपेक्षित विरूपण प्राप्त करते हैं। R < R(D) के लिए: कोई कोड D की प्राप्त अपेक्षित विरूपण नहीं करता है। वक्र (दर, विरूपण) स्पेस में एक ज्यामितीय सीमांत है।