Medida de la cantidad de información que se pierde en una implicación

Question

En una implicación como $p \implies q$, ¿hay alguna medida de la cantidad de información que se pierde en la implicación? Por ejemplo, considere las siguientes implicaciones, donde $x \in \{0,1,\ldots,9\}$:

\begin{align} P &: (x = 6) \implies (x \equiv 0 \pmod{2}) \\ Q &: (x = 6) \implies (x \equiv 0 \pmod{3}) \\ R &: (x = 6) \implies (x \equiv 6 \pmod{8}) \\ \end{align}

Yo diría que menos información acerca de $x$ se pierde en la implicación $Q$ que en implicación $P$:$x \equiv 0 \pmod{3}$$x \in \{0,1,\ldots,9\}$, hay menos posibilidades de $x$ que si le dieran $x \equiv 0 \pmod{2}$.

En implicación $R$, yo diría que no hay información acerca de $x$ se ha perdido, ya que si $x \equiv 6 \pmod{8}$$x \in \{0,1,\ldots,9\}$, entonces se puede concluir $x=6$. En general, cualquier "si y sólo si" relación no pierde información en la implicación.

Estoy familiarizado con los conceptos de entropía de Shannon y (vagamente) la complejidad de Kolmogorov. Hay una medida análoga de la pérdida de información de una implicación? Tal vez uno de los dos podría ser utilizada de manera natural aquí?

^{(Nota: no estoy preguntando por el teorema del resto Chino. Estoy usando aritmética modular como un ejemplo.)}

Answer 1

Lo que es una idea interesante! De forma análoga a la entropía de Shannon, se puede definir el volumen de la posible $x$ como una medida de la incertidumbre.

Deje $P(x)$ ser un predicado unario en algunos de $x \in X$. El predicado se define un conjunto de átomos que posee cierto, yo.e, la $A_P = \{ x \in X, P(x)\}$. Si este conjunto contiene exactamente un átomo, podemos decir que no hay incertidumbre. En el otro lado, si $A_P = X$, no sabemos nada acerca de lo $P$ está tratando de punto. Por lo tanto, sugiero a la definición de la entropía de un predicado unario como:

$$ H(P) = \log \left|\{x \in X, P(x)\}\right|$$

donde $|\cdot |$ es la cardinalidad del conjunto, para cualquier $P(x) \neq \bot$, por lo que el $A_P$ no está vacío. Esto supone que $X$ es contable.

Esto se puede considerar como un caso especial de la entropía de Shannon, asumiendo que todos los átomos en el juego son igualmente probables, es decir, cada átomo tiene la probabilidad de $\frac{1}{|A_P|}$. Por lo tanto, la entropía de Shannon es: $$H\left(\frac{1}{|A_P|}, \ldots, \frac{1}{|A_P|}\right) = -|A_P| \frac{1}{|A_P|} \log_2 \left(\frac{1}{|A_P|}\right) = \log_2 |A_P|$$

Ahora, si desea definir la pérdida de información, se puede utilizar de forma análoga a la diferencia de entropías. Específicamente, para $P(x) \implies Q(x)$ en su inferencia, tenga en cuenta que $H(P) \leq H(Q)$, por lo que la diferencia de entropía $D(P, Q) = H(Q) - H(P)$ es siempre no negativo. $D(P,Q)$ mide la cantidad de incertidumbre que se ganó, que es equivalente a la cantidad de información que se pierde la identidad de $x$.

Puedo pensar en muchas extensiones, pero este no es mi campo, por lo que no se sabe el de la literatura. (Multivariante de los predicados, y la información mutua son evidentes en el siguiente paso a tomar).

EDIT: información Mutua está vinculado al índice de Jaccard.

Answer 2

La entropía de Shannon, $H(X)$, puede ser intuitivamente pensamiento de como la cantidad de incertidumbre presente en una variable aleatoria (r.v.). El condicional de la entropía $H(X|Y)$ es la cantidad de incertidumbre restante en r.v. $X$ r.v. $Y$. Esto tiene cierto paralelo con la pérdida de información que se describe anteriormente. Por ejemplo, si $H(X|Y_1) < H(X|Y_2)$, entonces se puede considerar que el $Y_1$ tiene más información acerca de $X$$Y_2$, ya que hay una mayor reducción de la incertidumbre. Otra de las medidas que pueden ser de interés para usted es la información mutua, que es $I(X;Y) := H(X) - H(X|Y)$. Esta cantidad es la cantidad de información que queda en r.v. $X$ después de que lo conocemos $Y$ (y viceversa).

Por desgracia, estas medidas sólo es riguroso en un probabilística de la configuración. La entropía de determinista eventos como $X=6$ donde $\mathbb{P}(X=6)=1$ sería igual a cero.

Espero que esto fue útil.

Answer 3

Sin duda se puede decir que el $x=6$ le da certeza del valor, mientras que $x\equiv 0 \pmod 2$ le ofrece cinco posibilidades. Que es $\log_2 5$ bits menos información. Mientras tanto, $x \equiv 0 \pmod 3$ da cuatro posibilidades, por lo que necesita $2$ bits para obtener certeza, y $x\equiv 6 \pmod 8$ es cierto.