Questo è stato creato da 1948 Shannon in (Shannon 1948). Questa nozione è basata sulla nozione di probabilità, perché le cose rare sono più informative rispetto a qualcosa che accade spesso.

Introduction to Entropy

The Shannon Information Content

This is dependent on the notion of the Shannon information content defined as

$$ h(x = a_{i}) = \log_{2}\frac{1}{P(x = a_{i})} $$

We will see that the entropy is a weighted average of the information, so the expected information content in a distribution.

Kolmogorov complexity è un modo diverso per definire la complessità. Legato è Neural Networks#Kullback-Leibler Divergence.

We can model the classical view of entropy as the from [^1]

Expected value of Surprisal which is the uncertainty of a random variable $X$ taking a certain value which is $p(X = x) = P(x)$, but we want to measure it using log-likelihood.

With $\lvert \mathcal{X} \rvert < \infty$, $P_{X}(\cdot)$.

$$ H(\mathcal{X}) = - \sum_{x \in \mathcal{X}, P_{\mathcal{X}}(x) > 0} p(x)\log(p(x)) \tag{1.1} $$

Ossia, possiamo dire in modo intuitivo quanto sarebbe sorprendente vedere che si avverasse quell’evento.

This is the graph for the binary case: $$ H(\mathcal{X}) = p\log \frac{1}{p} + (1- p) \log \frac{1}{1 - p} $$

Oppure come descritto da [^2]

$$ \begin{align*} H(X) := E[I(X)] &= \sum_{i=1}^n P(x_i)I(x_i) \\ &= \sum_{i=1}^n p_i \log(1/p_i) \\ &= -\sum_{i=1}^n p_i \log(p_i) \tag{1.2} \end{align*} $$

Axiomatic Approach to Entropy

We can define the entropy as the only function that satisfies the following properties:

1. $H(X) \geq 0$ for every discrete r.v. which is related to the code length, which we don’t want to be negative
2. $H(X, Y) = H(X) + H(Y)$ when $X, Y$ are independent random variables.
3. $H(X) \text{ is maximal }$ when $X \sim Unif(0, 1)$ this concept is related to hard to guess the results.

Then one can prove that the only function that satisfies these properties is the entropy. Which is:

$$ H(X) = - \sum_{x \in \mathcal{X}} p(x) \log p(x) $$

Properties of the entropy

One observation is that labels don’t matter, we just need the probability vector and don’t care about what it represents.

The entropy is always positive. It’s easy to prove because all probabilities are $0 < p \leq 1$ so every term in the sum is positive because log in that interval is also positive.

Axiomatic approach

One could derive the entropy from an axiomatic point of view, with the idea of Surprise We just need three requirements: Given a probability space $\Omega, \mathcal{A}, \mathbb{P}$ , then the surprise of an even $E \subseteq \mathcal{A}$ is equal to a function $S([\mathbb{P}(E)])$ which satisfies the following properties:

1. $S(1) = 0$
2. $S$ is continuous
3. $S$ is monotonic decreasing, meaning that if $p > q$ then $S(p) < S(q)$
4. $S$ is additive, meaning that $S(pq) = S(p) + S(q)$ when $p, q$ are independent.

Then we can prove that the only function satisfying these properties has the form:

$$ S(p) = - \log(p) $$

The entropy is just the expected value of the surprise.

Chain Rule

non fare. Una proprietà random è

$$ H(X, Y) = H(X) + H(X|Y) $$

La dimostrazione è abbastanza banale una volta che si conoscono le definizioni…. La cosa interessante è che si può generale per qualunque numero di variabili aleatorie:

$$ H(X_{0}, X_{1}, \dots, X_{i}) = \sum_{i}H(X_{i}|X_{i-1}\dots X_{0}) $$

Upper bound

$$ H(X) \leq \log \lvert \mathcal{X} \rvert $$

Con $\mathcal{X}$ l’insieme immagine della variabile aleatoria discreta $X$. Importante in questo caso che la nostra variabile sia discreta, altrimenti il teorema provvisto in (Cover & Thomas 2012) 2.6.4 non funziona. Non è molto banale l’idea di utilizzare la uniforme per modellare il numero di elementi. e usare la positività di KL per finire l’upper bound.

We can prove the equality by having an uniform distribution. The computation is easy: If $\mathcal{X}$ is uniform then:

$$ P_{X}(x) = \frac{1}{\lvert \mathcal{X} \rvert } $$

And so we have

$$ \sum P_{X}(x) \log \frac{1}{P_{X}(x)} = \log \frac{1}{P_{X}(x)} = \log \lvert X \rvert $$

Proving the upper bound Let’s take $D(P_{X} \mid \mid U)$ into consideration, then we have that this value is

$$ \sum P_{X}(x) \log \frac{P_{X}(x)}{\frac{1}{\lvert \mathcal{X} \rvert }} = \sum P_{X} \log P(x) + \sum P_{X}(x) \log \lvert \mathcal{X} \rvert = \log \lvert \mathcal{X} \rvert - H(X) $$

And by knowing that the Kullback Leibler divergence is positive we know that

$$ \log \lvert \mathcal{X} \rvert - H(X) \geq 0 $$

Which ends the proof.

Entropy is concave

Uso l’upper bound e il fatto che KL è convesso per dimostrare questa cosa.

Functional dependency

Non fare Se $Y = f(X)$ per qualche funzione, allora $H(Y|X) = H(X|Y) = 0$ si può risolvere con qualche ragionamento sul supporto di entropia. Interessante vedere che ha una piccola relazione con Normalizzazione dei database#Dipendenze funzionali.

Monotonicity of new variables

This theorem states that

$$ H(X) \geq H(X \mid Y) $$

It is also called the principle Information never hurts meaning you are never more uncertain about a random variable when you have more information about it.

It’s easy to see why its true!

$$ H(X) - H(X \mid Y) = \sum P(x) \log P(x) - \sum P(x, y) \log P(x \mid y) = \sum P(x, y) \log \frac{P(x, y)}{P(x)} \geq 0 $$

Types of entropy

Conditional Entropy

$$ H(Y|X) = \sum_{x \in \mathcal{X}}p(x) H(Y|X=x) = \sum_{x \in \mathcal{X}, y \in \mathcal{Y}} p(x, y) \log \frac{1}{P(y|x)} = \mathbf{E}\left[ \log\frac{1}{p(Y|X)} \right] $$

La nozione con il valore atteso è la più semplice anche in questo caso.

conditional entropy corresponds to the expected remaining uncertainty in $Y$ after we observe $X$

We can also express conditional entropy as

$$ H(Y \mid X) = \mathbb{E}_{(x, y) \sim p(x, y)}\left[ \log \frac{1}{p(y \mid x)} \right] $$

Joint Entropy

$$ H(X, Y) = - \sum_{x, y} p(x, y) \log p(x, y) $$

We observe that there is a relation between Joint entropy and the conditional entropy:

$$ H(X, Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y) $$

Relative Entropy or Kullback-Leibler

Let’s take $\lvert \mathcal{X} \rvert < \infty$, and take distributions P, Q, $\mathcal{X} \to \mathbb{R}$ such that $p(x) \geq 0 \forall x \in \mathcal{X}$ and the sum is 1, same thing for $Q$, then we define the Kullback-Leibler Divergence between those distributions to be

$$ D(P \mid \mid Q) = \sum_{x \in \mathcal{X}} P(x) \log \frac{P(x)}{Q(x)} $$

We need to define some corner cases:

• If $P(x) = 0$ and $Q$ is anything then its 0
• If $\exists \xi \in \mathcal{X}$ such that $P(\xi) > 0$ and $Q(\xi) = 0$ => $D(P \mid \mid Q) = + \infty$.
• If $P \ll Q$ then $D(P \mid \mid Q) < \infty$ (I did not understand why)

This has some relations with the entropy, we can use some log properties and have the following result:

$$ D(P \mid \mid Q) = - H(P) - \sum P(x) \log Q(x) $$

The second addendum can be called cross-entropy.

In modo praticamente equivalente possiamo definire una versione condizionata. e si può applicare anche in questo caso una chain rule

$$ DL(P(x, y) \mid\mid Q(x, y) = DL(P(x) \mid\mid Q(x)) + DL(P(x|y) \mid\mid Q(x|y)) $$

Relative entropy is not a distance not a metric, so its incorrect to say it is a distance, but for practical purposes it seems to work well: if the Relative entropy is small also the probability vectors are small.

KL is positive or null

Ossia per ogni distribuzione $p$ o $q$ si ha che

$$ DL(P \mid\mid Q) \geq 0 $$

Con uguaglianza se hanno esattamente la stessa distribuzione. We have that $D(P \mid \mid Q) = 0 \iff P = Q$ .

E ricordandoci che $\log$ è una funzione concava, quindi si può utilizzare Jensen. Lo dimostriamo ora in breve. Sappiamo che la funzione $-\log(x) = \log\left( \frac{1}{x} \right)$ è una funzione convessa, perché il negativo di una funzione concava, che è il logaritmo.

Allora consideriamo $\frac{1}{u} = \frac{Q(x)}{P(x)}$ che è la parte dentro al logaritmo perché così possiamo usare Jensen Allora comunque abbiamo

$$ \sum_{x} P(x) \log\left( \frac{Q(x)}{P(x)} \right) \geq \log\left( \sum_{x} P(x) \cdot \frac{Q(x)}{P(x)} \right) = \log(1) = 0 $$

Che conclude che

$$ D_{KL}(P \mid \mid Q) \geq 0 $$

In modo facile.

KL is convex

$DL(p\mid\mid q)$ è convesso sulla coppia $(p, q)$, 2.7.2 di (Cover & Thomas 2012). Anche sula 2.26 di McKay è buono, anche se non esattamente parla di questo.

Mutual information

Questa nozione definisce quanta informazione hanno in comune due variabili aleatorie

Definizione

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

Si può fare dopo un po’ di calcoli che qui ho omesso, ma non dovrebbe essere difficile farlo.888

Si può intendere la mutual information anche come KL fra le distribuzioni $p(x, y)$ e $p(x)p(y)$ si può notare che queste due sono uguali quando le due sono indipendenti, che è coerente con la nostra nozione che abbiamo dell’indipendenza.

Proprietà

Another property: $$ I(X; Y\mid Z) = I(X ; Y, Z) - I(X ; Z) $$

Redundancy and Synergy

TODO

Sufficient Statistics

Possiamo rappresentare il sampling da una certa famiglia di distribuzioni $f_{\theta}(x)$ , rappresentato da $X$, e una sua statistica a caso (media varianza etc, che credo basti una funzione sul valore) come T, allora possiamo rappresentarlo come una Markov Chains#Catena di 3 variabili $\theta \to X \to T(X)$ E vale il teorema di information processing

$$ I(\theta; T(X)) \leq I(\theta; X) $$

Si può chiamare una statistica per $\theta$ sufficiente se $X$ contiene tutta l’informazione di $\theta$. Non so bene cosa significhi. La cosa importante è che la statistica sufficiente preserva la mutua informazione ossia si ha una uguaglianza in quella relazione di sopra. Vedere 2.9 di (Cover & Thomas 2012) per esempi .

Questa cosa potrebbe permettere di dire che usando quella statistica io posso dimenticarmi del parametro, perché riesco a ricavarmelo senza problemi credo….

The purpose of sufficiency is to demonstrate that statistics that satisfy this property do not discard information about the parameter, and as such, estimators that might be based on a sufficient statistic are in a sense “good” ones to choose.

Da https://math.stackexchange.com/questions/1186645/understanding-sufficient-statistic. Sufficient statistics also have a quite nice relationship with The Exponential Family.

Fano’s inequality

L"idea principale è utilizzare una variabile aleatoria per stimarne una altra, usando l’entropia condizionale fra le due.

Enunciato fano

Per ogni estimantore $\hat{X}$ tale per cui $X \to Y \to \hat{X}$ sia una catena di markov, e con $P_{e} = Pr(X \not= \hat{X})$ ossia la probabilità di errore, abbiamo che vale

$$ H(P_{e}) + P_{e}\log \lvert \mathcal{X} \rvert \geq H(X|\hat{X}) \geq H(X|Y) $$

Ci sono forme più deboli che possiamo considerare in un certo senso corollari, ossia che

$$ 1 + P_{e} \log \lvert \mathcal{X} \rvert \geq H(X|Y) $$

Dimostrazione Fano

Questa è una bomba da fare. Poi però ha un sacco di conseguenze non applicabili in modo immediato (cioè non ci arrivi subito se non le fai un po’ prima).

Maximum Distribution entropy

Un problema classico nella teoria dell’informazione è trovare la distribuzione che massimizzi l’entropia (quindi l’informazione contenuta credo) dati certe conoscenze a priori, Ossia data una funzione $f$ e certe condizioni che deve rispettare, massimizzare l’entropia.

SI può dimostrare (lo si può vedere da una reference di sopra) che la distribuzione che massimizza l’entropia, avendo solamente la condizione di probabilità, ossia che $\sum_{x}p(x) = 1$ è la distribuzione uniforme. Mentre se assumo anche media $\mu$ e varianza $\sigma^{2}$ allora è la gaussiana (dimostrato in Maximum Entropy Principle. In un certo senso possiamo dire che queste distribuzioni sono molto ricche di informazioni.

Codewords

Jensen’s Inequality

Questo è un teorema fondamentale per moltissime cose, e da un certo punto di vista è una cosa banale per le cose convesse/concave. Allora, sia data una funzione in $[a, b]$ tale che sia convessa (concava) in questo intervallo, allora vale che

$$ f\left( \sum_{i} \lambda_{i} x_{i} \right) \leq \sum_{i}\lambda_{i}f(x_{i}) $$

Con $\sum_{i}\lambda_{i} = 1$. Questa cosa si estende in modo molto semplice a variabili aleatorie e $E$ quando al posto di $\lambda_{i}$ mettiamo una probabilità in un punto.

La dimostrazione non dovrebbe essere molto difficile. La strategia è utilizzare l’induzione in modo abbastanza classico. Non so in che modo si estende su funzioni continue, ma quelle sono cose tecniche matematiche non interessantissime.

Log sum inequality

Siano $a_{1}, a_{2}, \dots a_{n}$ e $b_{1}, b_{2}, \dots, b_{n}$ numeri non negativi, allora vale che

$$ \sum_{i=1}^{n}a_{i} \log\left( \frac{a_{i}}{b_{i}} \right) \geq \left( \sum_{i=1}^{n}a_{i} \right)\log \frac{\left( \sum_{i=1}^{n} a_{i} \right)}{\sum_{i=1}^{n}b_{i}} $$

Con uguaglianza se vale che $\forall i, \frac{a_{i}}{b_{i}}= const$

Krafts Inequality

https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_inequality Questo teorema interessa cose dei codewords, perché ci interessano dei set di prefixfree che sono molto più gestibili probabilmente dal punto di vista dell’interpretazione. La cosa interessante è:

Siano $l_{1}, l_{2}, l_{3}, \dots, l_{n}$ lunghezze di code-words all’interno del nostro alfabeto, allora vale che esistono dei code-words (stringhe binarie) che hanno quelle lunghezze se e solo se viene soddisfatta la proprietà

$$ \sum_{x} 2^{-l(x)} \leq 1 $$

Il motivo è abbastanza semplice, questo si spiega in modo grafico in maniera praticamente immediata quando facciamo il disegno. Si può vedere dall’albero binario corrispondente di un insieme di set binari con prefissi che se un parente è scelto (colorato nel disegno), allora nessun discendente può essere scelto perché altrimenti avresti un prefisso. Inoltre se colori quelli sopra, significa che al massimo se sommi tutti quei valori otterrai 1 sse hai utilizzato tutti i rami a tua disposizione (meaning, che non puoi scegliere altri code-work, altrimenti perdi la prefix property).

Source coding theorem for symbol codes

Chiamata anche come la relazione con Kolmogorov. 1.11.3 di (Li & Vitányi 2019), allora se prendiamo un set di code-words con $L$ il minimo prefix code che possiamo mai avere Ossia $L = \sum_{x} P(x)l(x)$, con $l$ scelto il minimo possibile. Allora vale che

$$ H(P) \leq L \leq H(P) + 1 $$

Ossia la lunghezza migliore possibile è boundata da valori di entropia. Che è una cosa abbastanza forte perché relaziona come deve essere fatto il code-words, con la complessità dell’informazione che vogliamo andare a utilizzare. La dimostrazione non la facciamo qui, ma è fattibile con le tue conoscenze credo, ti serve la Gibbs inequality qui sotto per una freccia

Dimostrazione Prendiamo $q_{i} = 2^{-l_{i}}$, allora abbiamo $l_{i} = \log\left( \frac{1}{q_{i}} \right)$ vale

$$ L = \sum_{x} p(x) l(x) = \sum_{x} \left( p(x) \log\left( \frac{1}{q(x)} \right) \right) \geq \sum_{x}p(x) \log\left( \frac{1}{p(x)} \right) =H(x) $$

Dove abbiamo usato anche l’ineguaglianza di Gibbs #Gibbs Inequality e il fatto che vale #Krafts Inequality.

Provando a dimostrare l’altro bound, supponiamo che

$$ l_{i} = \lceil -\log_{2}(p_{i}) \rceil $$

Si può dimostrare che questo è un prefix code, perché soddisfa Kraft. Allora si può notare come

$$ L = \sum_{x} p(x) l(x) = \sum_{x} p(x) \lceil -\log_{2}(p_{x}) \rceil \leq \sum_{x}p(x) \left( \log_{2}\left( \frac{1}{p(x)}\right) +1 \right) = H(x) + 1 $$

Una nota interessante è questo teorema ci permette di definire un concetto di efficienza di rappresentazione. Tutto quanto dato da KL divergence è una specie di inefficienza.

Infatti possiamo scrivere

$$ L = H(x) + D_{KL}(P \mid \mid Q) $$

Con $Q$ la probabilità associata alle singole codewords, assumendo che siano uniformi e simili per dire.

Gibbs Inequality

Afferma che l’entropia è minore rispetto alla cross-entropy di qualunque cosa, ossia

$$ \sum_{x} P(x) \log\left( \frac{1}{P(x)} \right) \leq \sum_{x} P(x) \log\left( \frac{1}{Q(x)} \right) $$

Qualunque sia l’altra distribuzione. Si può dimostrare in modo abbastanza diretto utilizzando il fatto che la Kullback Leibler divergence, presentato in Neural Networks, è sempre positiva o uguale a 0. Infatti la parte di sopra si può riscrivere come

$$ -\sum_{x} P(x) \log\left( \frac{P(x)}{Q(x)} \right) = D_{KL}(P \mid \mid Q) $$

References

[1] Cover & Thomas “Elements of Information Theory” John Wiley & Sons 2012

[2] Shannon “A Mathematical Theory of Communication” The Bell System Technical Journal Vol. 27, pp. 379–423, 623–656 1948

[3] Li & Vitányi “An Introduction to Kolmogorov Complexity and Its Applications” Springer International Publishing 2019