Bounding informasi mutual diberikan batasan pada informasi mutual pointwise

Misalkan saya memiliki dua set dan dan distribusi probabilitas gabungan atas set ini . Misalkan dan menunjukkan distribusi marginal lebih dari dan masing-masing. $X$ $Y$ $p(x,y)$ $p(x)$ $p(y)$ $X$ $Y$

Informasi timbal balik antara dan didefinisikan sebagai: $X$ $Y$

I (X; Y) = \sum_{x, y} p (x, y) \cdot \log (\frac{p (x, y)}{p (x) p (y)})

$I(X; Y) = \sum_{x,y}p(x,y)\cdot\log\left(\frac{p(x,y)}{p(x)p(y)}\right)$

yaitu itu adalah nilai rata-rata dari pmi information mutual pointwise . $(x,y) \equiv \log\left(\frac{p(x,y)}{p(x)p(y)}\right)$

Misalkan saya tahu batas atas dan bawah pada pmi : yaitu saya tahu bahwa untuk semua yang berikut ini berlaku: $(x,y)$ $x,y$

- k \leq \log (\frac{p (x, y)}{p (x) p (y)}) \leq k

$-k \leq \log\left(\frac{p(x,y)}{p(x)p(y)}\right) \leq k$

Apa batas atas ini menyiratkan pada $I(X; Y)$ . Tentu saja itu menyiratkan $I(X; Y) \leq k$ , tapi saya ingin ikatan yang lebih ketat jika memungkinkan. Ini tampaknya masuk akal bagi saya karena p mendefinisikan distribusi probabilitas, dan pmi $(x,y)$ tidak dapat mengambil nilai maksimumnya (atau bahkan menjadi tidak negatif) untuk setiap nilai $x$ dan $y$ .

entropy mutual-information information-theory Florian
sumber

Ketika probabilitas gabungan dan marginal seragam, pmi (

x

$x$ ,

y

$y$ ) seragam nol (dan karena itu tidak negatif, tampaknya bertentangan dengan pernyataan terakhir Anda, tetapi hanya nyaris). Sepertinya saya, jika saya tidak salah, bahwa mengganggu situasi ini pada himpunan bagian kecil

X \times Y

$X \times Y$ menunjukkan bahwa batas pada pmi hampir tidak mengatakan apa-apa tentang

I (X; Y)

$I(X;Y)$ itu sendiri.

whuber

Bahkan, jika

X

$X$ dan

Y

$Y$ adalah independen, maka

p m i (x, y)

$\mathrm{pmi}(x,y)$ adalah konstan, terlepas dari distribusi marjinal. Jadi ada seluruh kelas distribusi

p (x, y)

$p(x,y)$ yang

p m i (x, y)

$\mathrm{pmi}(x,y)$ memperoleh nilai maksimum untuk setiap

x

$x$ dan

y

$y$ .

kardinal

Ya, memang benar bahwa pmi dapat sama untuk semua dan , tetapi itu tidak mengesampingkan batas yang lebih ketat. Sebagai contoh, tidak sulit untuk membuktikan bahwa . Ini adalah ketika , dan merupakan penguatan non-sepele dari terikat ketika . Saya bertanya-tanya apakah ada batas non-sepele yang berlaku lebih umum.

(x, y)

$(x,y)$

x

$x$

y

$y$

I (X; Y) \leq k (e^{k} - 1)

$I(X; Y) \leq k(e^k-1)$

\approx k^{2}

$\approx k^2$

k < 1

$k < 1$

k

$k$

k < 1

$k < 1$

Florian

Saya ragu Anda akan mendapatkan batas yang lebih baik daripada untuk . Jika Anda ingin terlihat lebih keras, coba ulang framing pertanyaan Anda dalam hal perbedaan KL antara p (x) p (y) dan p (x, y). Ketidaksetaraan Pinsker memberikan batas bawah pada MI yang mungkin mengkonfirmasi dugaan saya. Lihat juga Bagian 4 dari ajmaa.org/RGMIA/papers/v2n4/relog.pdf .

O (k^{2})

$O(k^2)$

k \to 0

$k \to 0$

vqv

Jawaban:

Kontribusi saya terdiri dari contoh. Ini mengilustrasikan beberapa batasan tentang bagaimana informasi timbal balik dapat diberikan batasan pada informasi timbal balik pointwise.

Ambil dan untuk semua . Untuk setiap biarkan menjadi solusi untuk persamaan Kemudian kita menempatkan titik massa di titik di ruang produk sedemikian rupa sehingga ada dari titik-titik ini di setiap baris dan setiap kolom. (Ini dapat dilakukan dengan beberapa cara. Mulai, misalnya, dengan poin pertama di baris pertama dan kemudian isi baris yang tersisa dengan menggeser $X = Y = \{1,\ldots, n\}$ $p(x) = 1/n$ $x \in X$ $m \in \{1,\ldots, n/2\}$ $k > 0$

m e^{k} + (n - m) e^{- k} = n .

$m e^{k} + (n - m) e^{-k} = n.$

e^{k} / n^{2}

$e^k / n^2$

n m

$nm$

{1, \dots, n}^{2}

$\{1,\ldots,n\}^2$

m

$m$

m

$m$

m

$m$ menunjuk satu ke kanan dengan syarat batas siklik untuk setiap baris). Kami menempatkan massa titik di sisa poin. Jumlah dari massa titik ini adalah sehingga mereka memberikan ukuran probabilitas. Semua probabilitas titik marginal adalah sehingga distribusi marjinal keduanya seragam.

e^{- k} / n^{2}

$e^{-k}/n^2$

n^{2} - n m

$n^2 - nm$

\frac{n m}{n^{2}} e^{k} + \frac{n^{2} - n m}{n^{2}} e^{- k} = \frac{m e^{k} + (n - m) e^{- k}}{n} = 1,

$\frac{nm}{n^2} e^{k} + \frac{n^2 - nm}{n^2} e^{-k} = \frac{me^k + (n-m)e^{-k}}{n} = 1,$

\frac{m}{n^{2}} e^{k} + \frac{m - n}{n^{2}} e^{- k} = \frac{1}{n},

$\frac{m}{n^2} e^{k} + \frac{m - n}{n^2} e^{-k} = \frac{1}{n},$

Dengan konstruksi jelas bahwa untuk semua , dan (setelah beberapa perhitungan) dengan informasi timbal balik berperilaku sebagai untuk dan sebagai untuk . $\mathrm{pmi}(x,y) \in \{-k,k\},$ $x,y \in \{1,\ldots,n\}$

I (X; Y) = k \frac{n m}{n^{2}} e^{k} - k \frac{n^{2} - n m}{n^{2}} e^{- k} = k (\frac{1 - e^{- k}}{e^{k} - e^{- k}} (e^{k} + e^{- k}) - e^{- k}),

$I(X;Y) = k \frac{nm}{n^2} e^{k} - k \frac{n^2 - nm}{n^2} e^{-k} = k\Big(\frac{1-e^{-k}}{e^k - e^{-k}} (e^k + e^{-k}) - e^{-k}\Big),$

k^{2} / 2

$k^2 / 2$

k \to 0

$k \to 0$

k

$k$

k \to \infty

$k \to \infty$

NRH
sumber

Saya tidak yakin apakah ini yang Anda cari, karena sebagian besar aljabar dan tidak benar-benar memanfaatkan properti p sebagai distribusi probabilitas, tetapi di sini ada sesuatu yang bisa Anda coba.

Karena batasan pada pmi, jelas dan dengan demikian . Kita dapat mengganti di untuk mendapatkan $\frac{p(x,y)}{p(x)p(y)}\leq e^k$ $p(x,y)\leq p(x)p(y)\cdot e^k$ $p(x,y)$ $I(X;Y)$ $I(X;Y)\leq \sum_{x,y}p(x)p(y)\cdot e^k\cdot log(\frac{p(x)p(y)\cdot e^k}{p(x)p(y)}) = \sum_{x,y}p(x)p(y)\cdot e^k\cdot k$

Saya tidak yakin apakah itu membantu atau tidak.

EDIT: Setelah ditinjau lebih lanjut, saya yakin ini sebenarnya kurang bermanfaat daripada batas atas asli k. Saya tidak akan menghapus ini kalau-kalau itu mungkin mengisyaratkan pada titik awal.

Michael McGowan
sumber

Nilai dari batas ini menjadi jelas setelah Anda mencatat dan (karena ) bahwa .

\sum_{x, y} p (x) p (y) = 1

$\sum_{x,y}p(x)p(y)=1$

k \geq 0

$k \ge 0$

e^{k} \geq 1

$e^k \ge 1$

whuber

Ya, ketika saya menyadari bahwa saya membuat edit saya.

Michael McGowan