Ograniczone wzajemne informacje ograniczają się do punktowej wzajemnej informacji

Załóżmy, że mam dwa zbiory $X$ i oraz łączny rozkład prawdopodobieństwa dla tych zbiorów . Niech i oznaczają brzegowe rozkładu ponad i odpowiednio. $Y$ $p(x,y)$ $p(x)$ $p(y)$ $X$ $Y$

Wspólna informacja między i jest zdefiniowana jako: $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)$

tzn. jest to średnia wartość punktowej wzajemnej informacji pmi . $(x,y) \equiv \log\left(\frac{p(x,y)}{p(x)p(y)}\right)$

Załóżmy, że znam górną i dolną granicę dla pmi : tj. Wiem, że dla wszystkich następujące blokady: $(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$

Jaka górna granica oznacza to dla . Oczywiście oznacza to , ale chciałbym ściślej związać, jeśli to możliwe. Wydaje się prawdopodobne, aby mnie, bo p określa rozkład prawdopodobieństwa i PMI nie może zająć jego maksymalną wartość (lub nawet być nieujemna) dla każdej wartości i . $I(X; Y)$ $I(X; Y) \leq k$ $(x,y)$ $x$ $y$

entropy mutual-information information-theory

— Florian
źródło

Kiedy prawdopodobieństwa łączne i krańcowe są jednakowe, pmi ( , ) jest równomiernie zerowe (a zatem nieujemne, najwyraźniej zaprzecza twojemu ostatniemu stwierdzeniu, ale tylko nieznacznie). Wydaje mi się, że jeśli się nie mylę, zaburzanie tej sytuacji przez małe podzbiory wskazuje, że granice pmi nie mówią prawie nic o samym .

x

$x$

y

$y$

X \times Y

$X \times Y$

I (X; Y)

$I(X;Y)$

— whuber

W rzeczywistości, jeśli i są niezależne, to jest stały, niezależnie od rozkładów krańcowych. Tak jest cała grupa rozkładów , dla których uzyskuje swoją maksymalną wartość dla każdego i .

X

$X$

Y

$Y$

p m i (x, y)

$\mathrm{pmi}(x,y)$

p (x, y)

$p(x,y)$

p m i (x, y)

$\mathrm{pmi}(x,y)$

x

$x$

y

$y$

— kardynał

Tak, z pewnością jest prawdą, że pmi może być równe dla wszystkich i , ale to nie wyklucza ściślejszej granicy. Na przykład nie jest trudno udowodnić, że . Jest to gdy , i jest nietrywialnym wzmocnieniem związanego gdy . Zastanawiam się, czy istnieją trywialne granice, które mają bardziej ogólny charakter.

(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

Wątpię, aby uzyskać lepszą granicę niż dla . Jeśli chcesz się bardziej przyjrzeć, spróbuj ponownie sformułować swoje pytanie pod względem rozbieżności KL między p (x) p (y) i p (x, y). Nierówność Pinskera stanowi dolną granicę MI, która może potwierdzić moje przeczucie. Zobacz także sekcję 4 ajmaa.org/RGMIA/papers/v2n4/relog.pdf .

O (k^{2})

$O(k^2)$

k \to 0

$k \to 0$

— vqv

Odpowiedzi:

Mój wkład składa się z przykładu. Ilustruje pewne ograniczenia, w jaki sposób można ograniczyć wzajemne informacje, biorąc pod uwagę granice wzajemnej informacji punktowej.

Wziąć $X = Y = \{1,\ldots, n\}$ i $p(x) = 1/n$ dla wszystkich $x \in X$ . Dla dowolnego $m \in \{1,\ldots, n/2\}$ niech $k > 0$ będzie rozwiązaniem równania

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

$m e^{k} + (n - m) e^{-k} = n.$ Następnie umieszczamy masę punktową

e^{k} / n^{2}

$e^k / n^2$ in

n m

$nm$ punktów w przestrzeni produktu

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

$\{1,\ldots,n\}^2$ w taki sposób, że w każdym rzędzie i każdej kolumnie znajduje się

m

$m$ tych punktów. (Można to zrobić na kilka sposobów. Zacznij na przykład od pierwszych

m

$m$ punktów w pierwszym rzędzie, a następnie wypełnij pozostałe rzędy, przesuwając

m

$m$ punkty o jeden w prawo z warunkiem cyklicznej granicy dla każdego rzędu). Masę punktową

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

$e^{-k}/n^2$ w pozostałych

punktów. Suma tych mas punktowych wynosi

n^{2} - n m

$n^2 - nm$

więc dają miarę prawdopodobieństwa. Wszystkie prawdopodobieństwa punktu krańcowego są

\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,$

więc oba rozkłady krańcowe są jednolite.

\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},$

Z konstrukcji jasno wynika, że dla wszystkich i (po niektórych obliczeniach) $\mathrm{pmi}(x,y) \in \{-k,k\},$ $x,y \in \{1,\ldots,n\}$ z wzajemnego informowania zachowują się tak,dlai jakodla.

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
źródło

Nie jestem pewien, czy tego właśnie szukasz, ponieważ jest to głównie algebraiczne i nie do końca wykorzystuje właściwości p będące rozkładem prawdopodobieństwa, ale tutaj możesz spróbować.

Ze względu na granice pmi, wyraźnie $\frac{p(x,y)}{p(x)p(y)}\leq e^k$ and thus $p(x,y)\leq p(x)p(y)\cdot e^k$ . We can substitute for $p(x,y)$ in $I(X;Y)$ to get $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$

I'm not sure if that's helpful or not.

EDIT: Upon further review I believe this is actually less useful than the original upper bound of k. I won't delete this though in case it might hint at a starting point.

— Michael McGowan
źródło

The value of this bound becomes apparent after you note

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

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

k \geq 0

$k \ge 0$ ) that

e^{k} \geq 1

$e^k \ge 1$ .

— whuber

Yes, when I realized that I made my edit.

— Michael McGowan