Submodularidad de la información mutua

Question

La submodularidad es una propiedad de funciones del conjunto $f: 2^{V} \rightarrow \mathbb{R}$ que asignan a cada subconjunto $S\subseteq V$ un valor $f(S)$ . $F$ se llama submodular si para todo $A, B \subseteq V$ sostiene que \begin {ecuación} F(A) + F(B) \geq F(A \cup B) - F(A \cap B) \end {Ecuación}

Alternativamente, una función de conjunto es submodular si para todo $A \subseteq B \subseteq V$ y $s \in V \setminus B$ se sostiene que \begin {Ecuación} F(A \cup \ {s\}) - F(A) \geq F(B \cup \ {s\}) - F(B) \end {Ecuación}

Mi pregunta es cómo demostrar que la información mutua $I(X;Y)$ es submodular?

Answer 1

El IM puede expresarse como una función de conjunto $f(A) = I(X;Y_A)$ . Hacemos una distinción entre las variables latentes $X$ y las variables observadas $Y$ . Para cualquier par $I, J \subseteq V$ tal que $I \cap J = \emptyset$ asumimos que $Y_I$ es independiente de $Y_J$ dado $X$ . Dejemos que $A\subseteq B\subseteq V$ y $j \in V\setminus B$ tenemos: \begin {eqnarray} I(Y_j; Y_{B \setminus A} | Y_A) & \geq & 0 \\ H(Y_j|Y_A) - H(Y_j|Y_{(B \setminus A) \cup A}) & \geq & 0 \\ H(Y_j|Y_A) & \geq y H(Y_j|Y_B) \end {eqnarray} que es la submodularidad para la entropía. Continuando con la hipótesis de independencia condicional y restando $H(Y_j|X)=H(Y_j|X,Y_A)=H(Y_j|X,Y_B)$ de ambos lados: \begin {eqnarray} H(Y_j|Y_A) - H(Y_j|X) & \geq & H(Y_j|Y_B) - H(Y_j|X) \\ H(Y_j|Y_A) - H(Y_j|X,Y_A) & \geq & H(Y_j|Y_B) - H(Y_j|X, Y_B) \\ I(Y_j;X|Y_A) & \geq & I(Y_j;X|Y_B) \\ I(X;Y_j|Y_A) & \geq & I(X;Y_j|Y_B) \end {eqnarray}