Jurnalning tengsizligi - Log sum inequality

The log sumining tengsizligi teoremalarini isbotlash uchun ishlatiladi axborot nazariyasi.

Bayonot

Ruxsat bering ${displaystyle a_ {1}, ldots, a_ {n}}$ va ${displaystyle b_ {1}, ldots, b_ {n}}$ manfiy bo'lmagan raqamlar bo'ling. Hammasining yig'indisini belgilang ${displaystyle a_ {i}}$s tomonidan ${displaystyle a}$ va barchasining yig'indisi ${displaystyle b_ {i}}$s tomonidan ${displaystyle b}$. Jurnal yig'indisi tengsizligi shuni ko'rsatadiki

${displaystyle sum _ {i = 1} ^ {n} a_ {i} log {frac {a_ {i}} {b_ {i}}} geq alog {frac {a} {b}},}$

tenglik bilan va agar shunday bo'lsa ${displaystyle {frac {a_ {i}} {b_ {i}}}}$ hamma uchun tengdir ${displaystyle i}$, boshqa so'zlar bilan aytganda ${displaystyle a_ {i} = cb_ {i}}$ Barcha uchun ${displaystyle i}$.^[1]

(Oling ${displaystyle a_ {i} log {frac {a_ {i}} {b_ {i}}}}$ bolmoq ${displaystyle 0}$ agar ${displaystyle a_ {i} = 0}$ va ${displaystyle infty}$ agar ${displaystyle a_ {i}> 0, b_ {i} = 0}$. Tegishli raqamga moyil bo'lganligi sababli olingan chegara qiymatlari ${displaystyle 0}$.)^[1]

Isbot

Sozlamadan keyin bunga e'tibor bering ${displaystyle f (x) = xlog x}$ bizda ... bor

${displaystyle {egin {aligned} sum _ {i = 1} ^ {n} a_ {i} log {frac {a_ {i}} {b_ {i}}} & {} = sum _ {i = 1} ^ {n} b_ {i} uchish ({frac {a_ {i}} {b_ {i}}} ight) = bsum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} uchish ({frac {a_ {i}} {b_ {i}}} ight) & {} geq bfleft (sum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} { frac {a_ {i}} {b_ {i}}} ight) = bfleft ({frac {1} {b}} sum _ {i = 1} ^ {n} a_ {i} ight) = bfleft ({frac {a} {b}} ight) & {} = alog {frac {a} {b}}, oxiri {aligned}}}$

bu erda tengsizlik kelib chiqadi Jensen tengsizligi beri ${displaystyle {frac {b_ {i}} {b}} geq 0}$, ${displaystyle sum _ {i = 1} ^ {n} {frac {b_ {i}} {b}} = 1}$va ${displaystyle f}$ qavariq.^[1]

Umumlashtirish

Tengsizlik amal qiladi ${displaystyle n = yaroqsiz}$ sharti bilan ${displaystyle a$ va ${displaystyle b$.^{[iqtibos kerak ]}Yuqoridagi isbot har qanday funktsiya uchun amal qiladi ${displaystyle g}$ shu kabi ${displaystyle f (x) = xg (x)}$ barcha doimiy kamayib ketmaydigan funktsiyalar singari qavariqdir. Logarifmdan tashqari kamaymaydigan funktsiyalarga umumlashtirish Csisz 谩 r, 2004 yilda berilgan.

Ilovalar

Axborot nazariyasidagi tengsizlikni isbotlash uchun log summasining tengsizligidan foydalanish mumkin. Gibbsning tengsizligi deb ta'kidlaydi Kullback-Leyblerning ajralib chiqishi manfiy emas va agar uning argumentlari teng bo'lsa, aniq nolga teng.^[2] Bitta dalil jurnal yig'indisi tengsizligidan foydalanadi.

Isbot[1]

Ruxsat bering ${displaystyle P = (p_ {i}) _ {iin mathbb {N}}}$ va ${displaystyle Q = (q_ {i}) _ {iin mathbb {N}}}$ pmfs bo'ling. Jurnal yig'indisida tengsizlik, o'rnini bosadi ${displaystyle n = yaroqsiz}$, ${displaystyle a_ {i} = p_ {i}}$ va ${displaystyle b_ {i} = q_ {i}}$ olish uchun; olmoq ${displaystyle mathbb {D} _ {mathrm {KL}} (P | Q) teng sum _ {i} p_ {i} log _ {2} {frac {p_ {i}} {q_ {i}}} geq 1log {frac {1} {1}} = 0}$ tenglik bilan va agar shunday bo'lsa ${displaystyle p_ {i} = q_ {i}}$ barchasi uchun men (ikkalasi kabi) ${displaystyle P}$ va ${displaystyle Q}$ yig'indisi 1).

Tengsizlik Kullback-Leybler divergentsiyasining konveksligini ham isbotlashi mumkin.^[3]

Izohlar

Adabiyotlar

• Tomas M. Qopqoq; Joy A. Tomas (1991). Axborot nazariyasining elementlari. Xoboken, Nyu-Jersi: Uili. ISBN  978-0-471-24195-9.
• Csisz 谩 r, I.; Shilds, P. (2004). "Axborot nazariyasi va statistikasi: o'quv qo'llanma" (PDF). Aloqa va axborot nazariyasining asoslari va tendentsiyalari. 1 (4): 417–528. doi:10.1561/0100000004. Olingan 2009-06-14.
• T.S. Xan, K. Kobayashi, Axborot va kodlash matematikasi. Amerika matematik jamiyati, 2001 yil. ISBN  0-8218-0534-7.
• Axborot nazariyasi kursi materiallari, Yuta shtati universiteti [1]. 2009-06-14 da olingan.
• MakKay, Devid JK (2003). Axborot nazariyasi, xulosa chiqarish va o'rganish algoritmlari. Kembrij universiteti matbuoti. ISBN  0-521-64298-1.