ალბათობის სიმპლექსი
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 (1−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 დივერგენცია
Kullback-Leibler დივერგენცია (ფარდობითი ენტროპია) განაწილებიდან 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 bits
არხის სიმძლავრე გეომეტრიული მანძილად
არხის სიმძლავრე აქვს გეომეტრიული ინტერპრეტაცია ალბათობის განაწილებების სივრცეში.
არხისთვის 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)) არის მინიმალური-ინფორმაციის გამოტანის განაწილება — წერტილი გამოტანის ალბათობის სივრცეში ყველაზე ახლოს (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)) BSC-ის შემთხვევაში Q = 0.1, r(y) = (0.5, 0.5).
p(y|x=0) = (0.9, 0.1) (გაგზავნა 0, მიღება 0 ალბათობით 0.9, მიღება 1 ალბათობით 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 bits
შემოწმება: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 bits ✓
სიჩქარე-დამახინჯება & შეკუმშვის ლიმიტები
სიჩქარე-დამახინჯების თეორია ფართობზე აჩენს ინფორმაციის თეორიას დაკარგული შეკუმშვაზე. ამის ნაცვლად "რა არის მინიმალური bits წყაროს ზუსტი წარმოჩენისთვის?" ის ითხოვს: "გაწყალებულობის რაღაცა საშუალო დამახინჯებით D, რა არის მინიმალური სიჩქარე R(D) bits თითო სიმბოლოზე?"
სიჩქარე-დამახინჯების ფუნქცია 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. მრუდი არის გეომეტრიული ფრონტიერი (სიჩქარე, დამახინჯება) სივრცეში.