Quantification of Information- From the perspective of a Specific Field
为防止markdown渲染出现问题，提供一份pdf版的下载，链接
***
近代通讯及计算机等学科的重要基础之一是信息论，核心内容涉及信息的产生、获取、表示、专递、转换。这就需要对于信息进行量化，将信息以某种数学的形式表示，用数学的理论来指导通信、计算机科学的工作。基于这一目的，我们首先考虑如下的一个“信息源”$—$ 输出一些列有序的（e.g. 某个系统）信号：
$$
\color{blue}{a_1, a_2, a_3, a_4, \cdots, a_i, \cdots, a_N}
$$
注意，上述输出序列（series of ordered outputs）是有序的，i.e. $a_1$ 是“最可能出现”的输出，$a_N$ 是“出现可能最小”的输出。现在有了输出序列（information）$—$ 物质基础，那用什么哪种数学方法进一步量化它呢？答案是$—$ 概率。
一个合理的测量信息的方法应该满足以下条件
- 一个输出信号$a_i$ 的“信息量(information content)” 仅仅取决于 $a_i$ 出现的概率$—$ i.e. $P_i$ , 而不是取决于$a_i$ 的值。 我们用这样一个函数$I(P_i)$ 表示 “信息量”，并将之命名为输出(e.g. $a_i$ )的 self-information. 并且，必需满足：
$$
\sum_i P_i =1
$$
- Self-information 是$P_i$ 的连续函数。
- Self-information 是$P_i$ 的单调递减函数。
- 如果，$P_i = P_j \cdot P_k $ , 那么$I(P_i)= I(P_j) \cdot I(P_k) $
实际上，只有对数函数[^1] 满足上述要求，因此self-information可以写成如下形式：
$$
\color{red}{I(P_i) = -\log(P_i)}
$$
因此，“整个输出序列”[^2] 的所包含的信息即为：该序列所有outputs的self-information的加权和，这个”权重“即为，每个输出$a_i$ 出现的概率$P_i$ (i=1,2, … ,N). 我们把这整个序列的信息命名为 “Shannon-Entropy” 或者 “Entropy”, 记作：
$$
\color{red}{H(X)=\sum_{i=1}^N P_i I(P_i) = -\sum_{i=1}^NP_i\log(P_i) =\sum_{i=1}^N \log(\frac{1}{P_i})^{P_i}}
$$
再次强调，entropy 和 self-information的关系为：前者是后者的加权和，权重为某个output出现的概率。
上述公式中的$X={a_1,a_2,\cdots,a_i, \cdots a_N}$, i.e. 整个输出序列 (sequence of outputs).
以上，是从一个通信领域的一个具体情况说明了information及若干相关概念如：self-information, entropy等的来源。下面的内容，会从信息论理论的角度来阐述、引出一些核心概念，其含义更加广泛、更加本质。
Self-Information(自信息)
顺着第一部分的内容，与其并不冲突。而是从更加宽阔的视角和更加深的理论出发，基于信息论和概率来讲述信息的核心概念。简而言之，在信息论中，self-information or surprisal 是用来刻画:
$$
\color{red}{当抽样到一个随机变量时所附带的不确定性（uncertainty）或者非同寻常的（superise）程度}
$$
鉴于随机变量和随机事件之间有对应关系[^0]（i.e. 一个随机变量是一个定义在随机事件上的实值函数），下文中random variable 和 event 会根据具体的context交互使用，读者只须明白他们的含义和对应关系就好。
根据上述定性的描述，我们不难认同如下结论：
当information接收端事先已确定地知道需要传递的消息（message ）的内容（the content of a message is known priori with certainty），那么这个消息（message）的传递不会带来任何的information。
相应地，与本文第一部分类似，我们同样给出一个序列 $—$ 随机变量$x$ 的所有可能取值：
$$
x_1, x_2, \cdots, x_n, …,x_N
$$
一如前文所述，序列中任何一个 $x_n$ 可看作一个随机事件（event）。该随机事件的self-information表明了该事件出现的不确定性（可能性取负即可），因此 self-information 仅仅取决于该随机事件 (event) 发生的概率，而与别的因素无关, 换句话说一个随机事件/变量 的self-information是该随机事件/变量概率的函数。i.e.
$$
\color{red}{I(x_n)=f(P(x_n))}
$$
完整的写法应该是：$I(X=x_n)=f(P(X=x_n))$
此外函数 $\color{blue}{f(\cdot)}$ 还需具备以下2个性质：
- If $P(x_n)=1$ then $I(x_n)=0$ , if $P(x_n)<1$ then $I(x_n)>0$ .
- 对于两个independent 的随机事件$A, B$, 如果另一个随机事件 $C$ 是它们两个的intersection 事件，则有：$I(C)=I(A\cap B)=I(A)+I(B)$ .
因为有，$C=A\cap B$, 所以$P(C)=P(A\cap B)=P(A)P(B)\Longrightarrow f(P(C))=f(P(A)P(B) \Longrightarrow I(C)=f(P(A)P(B))$ , 由2 中公式可知，$I(C)=I(A)+I(B)=f(P(A))+f(P(B))$ , 从而有：$\color{blue}{f(P(A)P(B))=f(P(A))+f(P(B))}$ .
从而得知，函数$f(\cdot)$ 满足可加性：
$$
f(x\cdot y) =f(x) + f(y)
$$
考虑到以上限制条件，只有对数函数符合要求（底数无关大局），因此一个随机事件/变量 $X$其取值为 $x_n$时self-information 定义为：
$$
I(x_n)=-\log(P(x_n))=\log\frac{1}{P(x_n)}
$$
与第一部分的定义是一致的。但是要注意的是: self-information 针对的是一个随机变量单独的某一个outcome 而言,（i.e. $\omega_n$)来衡量它的不确定性(信息含量)。不是整个随机事件/变量序列 or 某一个随机变量总体 (i.e. $x_1, \cdots, x_N$)的 不确定性。
Point Mutual Information(点互信息)
Pointwise mutual information(PMI) or point mutual information，是针对两个随机变量，对他们之间的关联性(当然，同时也是 无关性)进行measure的量，常用在统计与信息论中。而之前讲到的self-information 是衡量一个(离散)随机变量在某一个固定取值上的不确定性(uncertainty)，注意区分；此外，PMI 涉及的是两个random variable各自单独取一个固定值，后面将要讲的MI 涉及的是两个random variables可能的取值集合，须注意以上区别。
Formal Definition
The PMI of a pair of outcomes x and y belonging to discrete random variable $X$ and $Y$ quantifies the discrepancy between the probability of their coincidence given their joint distribution and their individual distribution, assuming independence. Mathematically,
$$
\begin{equation}
\begin{split}
pmi(x;y)&\equiv \log \frac{p(x,y)}{p(x)p(y)} \\
&=\log \frac{p(x|y)}{p(x)} \\
&=\log \frac{p(y|x)}{p(y)}\\
\end{split}
\end{equation}
$$
PMI的性质
根据PMI的定义，我们可以知道其有如下几个性质：
- 对称性：$pmi(x;y)=pmi(y;x)$
- 取值可以正、负、零。
- 如果$X$ and $Y$ 是相互独立(无关, i.e. independent)的, $pmi(x;y)=pmi(y;x)=0$
- 当 $X$ 和 $Y$ 完全关联的时候，i.e $p(x|y)\, or\, p(y|x)=1$ , PMI 会取最大值。
- 有上下界(bounds)：$-\infty \leqslant pmi(x;y) \leqslant min {-\log p(x), -\log p(y) } $
- 如果固定$p(x|y)$, PMI是关于$p(x)$ 的单调递减；如果固定$P(y|x)$, PMI是关于$p(y)$的单调减函数。
PMI与 Self-information、 mutual information的关系
TO-DO
Chain-rule for PMI
TO-DO
Mutual-Information(互信息)
MI是点PMI的自然延伸，前面我们讲到PMI是针对两个随机变量各自均取一个固定值的情形，用以衡量这两个随机变量各取对应固定值时的关联性或者无关性。MI 也是针对两个随机变量，不同之处在于它针对这两个随机变量的可能取值集合而言，那自然容易联想到其定义是一个基于PMI的加权求和形式，权重为这两个随机变量的联合分布$—P(X,Y)$ , i.e. MI是 $pmi(x;y)$ 的数学期望。
从信息论的角度看，MI quantifies the “amount of information or information content” obtained about one random variable, through the other random variable.
不像相关系数(correlation-coefficient) 局限于 read-valued的随机变量, MI有更大的广泛性并用以判定联合分布$P(X,Y)$ 与边缘分布的乘积$P(X)P(Y)$ 的相似程度(或 差异程度)。
Formal Definition
形式化地，有两个离散型随机变量$X$ with image $\mathcal X$ 和 $Y$ with image $\mathcal Y$ 并且$X$ 和 $Y$ 服从同一概率分布$P$ 其他们的联合概率分布为 $P(X,Y)$ 。则$X$和 $Y$的 mutual information 有如下定义：
$$
I(X;Y)=E[pmi(X,Y)]
$$
完整写法应该为$ I_{(x,y)\sim P(X,Y)}(X;Y)=E_{(x,y)\sim P(X,Y)}[pmi(X,Y)] $
可以显示地写为：
$$
I(X;Y)=\sum_{x\in \mathcal X}\sum_{y\in \mathcal Y}p(x,y)\log \frac{p(x,y)}{p(x)p(y)}
$$
可以明显看到显示定义公式，MI为PMI的数学期望。
Motivation
为什么需要这样一个概念呢？直观上理解，MI 测量了或者说衡量了两个随机变量 $X$ 和 $Y$ 共享的信息：它可以衡量当其中一个随机变量已知的话，可以多大程度上减少另一个随机变量的不确定性。
比如， 如果$X$和$Y$时相互独立的，那么知道 $X$ 不能给出关于$Y$的任何信息，换句话说，就是当我们知道了$X$对于降低$Y$的不确定性没有任何帮助，反之亦然，那么$I(X;Y)=0$.
考虑另一种极端情况，如果$X$ is a deterministic function of $Y$ 并且$Y$ is a deterministic function of $X$, 那么$X$传达或者包含的所有信息均与$Y$是共享的，也即：$X$ 完全决定了$Y$的值，反之亦然。结果，这种情况下，$X$和$Y$的互信息$I(X,Y)$与单独包含在$X$或$Y$中的不确定性是一样的, 其实就是：$X$的熵 $H(X)$ 同时也是$Y$的熵$H(Y)$ ).（一种特殊的情况是，$X$ 和$Y$是同一个随机变量。）
MI 的性质
- 非负性：$I(X,Y)\geq 0$ (如何证明？)
- 对称性：$I(X;Y)=I(Y;X)$
- $I(X;Y)=0$ if and only if $X$ and $Y$ are independent random variables.
MI 与其他量的关系
与条件熵与联合熵的关系（Relation to conditional and joint entropy）
TO-DO
- 与 KL divergence 的关系
Variations
TO-DO
Entropy(熵)
针对离散型随机变量，在本文第一部分已经对entropy进行了定义，即：一个输出序列的entropy 是 该序列中各个输出(output)的self-information的加权和，其权重为各个对应的output出现的概率。形式化如下：
$$
\begin{equation}
\begin{split}
&H(X)=\sum_{n=1}^N P(x_n)I(x_n)= -\sum_{n=1}^N P(x_n)\log P(x_n)\, , \\
&also\ denoted\ H(P)\, , where\ P \ is \ the \ 「PMF」 \ of \ random \ variable \ X. \
\end{split}
\end{equation}
$$
从更本质（概率统计）的角度我们可以 “重新审视 Entropy 的定义 ”，上述定义的形式从概率角度看来，不就是 “随机变量的函数的数学期望 ” 吗？将上述定义从概率角度 “拆解” 如下：
- 随机变量的取值：$x_1,\cdots,x_n,\cdots,x_N$ （离散）
- 离散随机变量：$X$
- 随机变量的函数：$I(x_n)$ (i.e. $I(x_n)=-\log P(x_n)$)，$I(x_n)$ 本身也是一个随机变量。
- 数学期望的定义
- 离散随机变量：$E[g(X)]=\sum_{\rm x} p(x)g(x)$
- 连续随机变量：$E[g(X)] = \int_{-\infty}^{+\infty}g(x)f(x)dx$
- 对比 Entropy 的定义形式，即可知其概率上的本质乃为 Expected Self-Information or Expected Information Content.
因此，我们可以得到另外一种角度的形式定义。同时,尤其应该注意到截至目前为止，entropy的定义仅仅针对一个、离散型的随机变量$X$ ，考虑其在某个image($\mathcal X$) 上所含有的uncertainty$—$ entropy.
Formal Definition
对于一个离散随机变量$X$, 它的可能取值为 ${x_1,\cdots, x_n}$ 并且 其概率质量函数(probability mass function)为 $P(X)$,
$$
\color{red}{H(X)= E_{x\sim P }[I(x)]=E_{x \sim P}[-\log P(x)]=-E_{x \sim P}[\log P(x)]}
$$
这里，$E$ 期望操作符，$I$ 是$X$的self-information or information content. $I(X)$ 本身就是一个随机变量。Entropy可以显式地写为：
$$
\color{red}{H(X)=\sum_{i=1}^n P(x_i)\, I(x_i)=-\sum_{i=1}^n P(x_i)\log_b P(x_i),}
$$
其中，$b$是对数函数的底数，通常取 2, e, 10等。
注意：
这里定义的 Entropy 是针对一个随机变量$X$ 的可能的取值集合而言（i.e. image is $\mathcal X$ ），而不是仅仅针对$X$的某一个具体的取值而言。
Joint Entropy
在信息论中，joint entropy 是对 “由若干随机变量组成的集合” 的不确定性的一种衡量[^4].
Formal Definition
The joint entropy of two discrete random variables $X$ 和 $Y$ is defined as:
$$
\color{red}{H(X,Y)= -\sum_{x\in \mathcal X} \sum_{y\in \mathcal Y} P(x,y)\log [P(x,y)]}
$$
Where $P(\cdot)$ is joint probability distribution, $\mathcal X$ and $\mathcal Y$ is image of random variable $X$ and $Y$, $x$ and $y$ are perticular values of $X$ and $Y$.
For more than two random variables $X_1,…, X_n$ 可以扩展为：
$$
\color{red}{H(X_1,…,X_n)= -\sum_{x_1} \cdots \sum_{x_n} P(x_1,…,x_n) \log [P(x_1,…,x_n)]}
$$
联合熵的性质
非负性：
$$
\begin{equation}
\begin{split}
&H(X,Y)\geq 0 \
&H(X_1,…,X_n)\geq 0
\end{split}
\end{equation}
$$对称性：$H(X,Y)=H(Y,X)$
若干个随机变量的联合熵，不小于单个随机变量的熵
The joint entropy of a set of random variables is greater than or equal to all of the individual entropies of the random variables in the set.
$$
\begin{equation}
\begin{split}
&H(X,Y) \geq max{ H(X),H(Y) } \
&H(X_1,…,X_n) \geq max { H(X_1),…,H(X_n)}
\end{split}
\end{equation}
$$
若干的随机变量的联合熵，不大于 单个随机变量的熵的和
The joint entropy of a set of random variables is less than or equal to the sum of the individual entropties of the random variables in the set. 以下不等式中，当且仅当 $X$ 和 $Y$ 相互独立(independent)的时候等号成立。
$$
\begin{equation}
\begin{split}
&H(X,Y) \leq H(X)+H(Y)\
&H(X_1,…,X_n) \leq H(X_1)+…+H(X_n)
\end{split}
\end{equation}
$$
Joint entropy与其他量的关联
与互信息(mutual information)的关联
$I(X;Y)=H(x)+H(Y)-H(X,Y)$
与条件熵(conditional entropy)的关联
$H(X|Y)=H(X,Y)-H(Y)$ 或者写 $H(X,Y)=H(X|Y)+H(Y)$
and
$H(X_1,…,X_n)=\sum _{k=1}^n H(X_k|X_{k-1},…,X_1)$, 这有些类似概率性质中的chain of rule(链式法则).
Conditional Entropy(条件熵)
定性刻画：为了描述 ”当已知一个给定随机变量X的值时，另一个随机变量Y可能的取值情况“ 所需要的信息总量 (amount of information), 称之为条件熵。The entropy of $Y$ conditioned on $X$ is written as: $H(Y|X)$ .
Formal Definition
If $H(Y|X=x)$ is the entropy of discrete random variables $Y$ conditioned on the discrete random variable $ X$ taking a certain value $x$, then $H(Y|X)$ is the result of averaging $H(Y|X=x)$ over all possible values $x$ that $X$ may take.
给定一个离散随机变量$X$ 及它的像(image) $\mathcal X$ 和 离散随机变量$Y$及它的像(image) $\mathcal Y$ ，则，$Y$在给定$X$时的条件熵 被定义为：$H(Y|X=x)$对 $x$ 每一个可能的值的加权和，其权重为$p(x)$[^3]:
$$
\begin{equation}
\begin{split}
H(Y|X) &= \sum_{x \in \mathcal X} p(x)\, H(Y|X=x) \\
&=-\sum_{x \in \mathcal X}p(x)\sum_{y\in \mathcal Y} p(y|x)\log p(y|x) \\
&=-\sum_{x\in \mathcal X}\sum_{y\in \mathcal Y}p(x,y)\log p(y|x) \\
&= -\sum_{x\in \mathcal X}\sum_{y\in \mathcal Y}p(x,y)\log \frac{p(x,y)}{p(x)} \\
&=\ \ \ \sum_{x\in \mathcal X}\sum_{y\in \mathcal Y}p(x,y)\log \frac{p(x)}{p(x,y)} \\
\end{split}
\end{equation}
$$
*Cross-Entropy(交叉熵)
交叉熵(cross-entropy) 与之前讲的所有对于information content 或者 uncertainty的measure 都不同的的地方在于，前者们针对的是一个或多个随机变量去一个特定的值或在一个image上取所有值的情况；而交叉熵是针对两个不同的概率分布(probability distribution)，关注的对象从random variable转移到了 probability distribution. 也就是说，之前无论是对一个随机变量还是多个随机变量的某些方面的measure，都是限定在同分布(基于一个probability distribution$P(\cdot)$ ), 而现在要涉及2个概率分布：$P(\cdot)$ 和 $Q(\cdot)$ .
Formal definition
Cross-entropy between two probability distributions $P$ and $Q$ over the same underlying set of events measures the amount of information[^5]needed to identify an event drawn from the set, if a coding scheme is used that is optimized for an “unnatural” distribution $Q\, $, rather than the “true” distribution $P$ .
现在，我们在同一个随机变量 $\rm X$ 上有两个概率分布函数 $P$ 和 $Q $, 这两个分布的交叉熵定义如下：
$$
\color{red}{H(P,Q)= E_{X\sim P}[-\log Q(x)]=-E_{X\sim P}[\log Q(x)]}
$$
对于 $X$ 是离散随机变量的情况，上述定义可以具体地写为：
$$
\color{red}{H(P,Q)= -\sum_x P(x)\log Q(x)}
$$
需要注意的是，在交叉熵的定义中 $P$ 是那个“生成数据的分布” 也即 “true distribution”，$Q$ 是那个我们需要通过优化参数得到的分布。两者有主次之分，$P$ 为主，$Q$ 为次。
去其它量的关联
与KL divergence的关联
$H(P,Q) = H(P) + D_{KL}(P||Q)$
*KL divergence (relative entropy)
KL divergence 是衡量一个概率分布与另一个分布的差异度。
同时，KL divergence并不是一种“真正的” metric， 因为 $D_{KL}(P||Q) \neq D_{KL}(Q||P) $, 也就是说它不具有对称性。
Formal Definition
$$
\color{red}{D_{KL}=E_{X\sim P}[\log \frac{P(x)}{Q(x)}]=E_{X\sim P}[\log P(x)-\log Q(x)]}
$$
离散随机变量的KL divergence
$$
\color{red}{D_{KL}(P||Q)=\sum_x P(x)\log \frac{P(x)}{Q(x)}=-\sum_x P(x)\log \frac{Q(x)}{P(x)}}
$$
换句话说，是 $P$ 和 $Q$ 的对数差异[^6]的期望，权重为 $P(x)$.
连续随机变量的KL divergence
$$
D_{KL}(P||Q)=\int _{x\in \mathcal X}p(x)\log \frac{p(x)}{q(x)}\,dx
$$
Where $p$ 和 $q$ denote the densities of $P$ 和 $Q$ .
与其他量的关联
- 与cross-entropy的关联
$$
D_{KL}(P||Q) = H(P,Q) - H(P)
$$
总结
- Self-information 是针对一个随机变量的某一给定取值；PMI针对两个随机变量分别给定某个取值；MI是针对两个随机变量可能的取值集合。
- Shannon entropy 是针对一个随机变量的可能取值的集合，是self-information的期望，i.e. 自信息的加权和，权重为$P(x)$ ; MI 是 PMI的期望，i.e. 加权和，权重为$X$ , $Y$的联合分布$ p(x,y)$ ;
- Joint entropy 是针对多个随机变量的可能取值集合，可以看作是一个随机变量序列的shannon entropy，也可以看作是一个随机变量的self-information的加权和，权重为联合分布。
- Cross entropy是针对两个概率分布的，具有对称性，与KL divergence 关系密切；在machine learning的context中，经常作为分类问题的 loss函数$—$交叉熵loss，也叫 logistic loss 和 log loss(当标签为{+1, -1}时候) 。
- KL divergence是针对两个概率分布的，非对称性，与cross entropy 关系密切。
[^0]: 根据随机变量的的定义，其一个具体取值对应一个实验结果的集合(a set of outcomes)；根据随机事件的定义可知，进而对应一个随机事件。
[^1]: 不同的底数选取仅仅是不通信息单元（如：bytes, bits, nats）下信息量不同程度的rescaling罢了，不影响问题本身。
[^2]: 每一个输出可以看作一个随机变量或者随机事件，因此整个随机序列可以看作N个随机变量乘积。
[^3]: $p(x)$ 是 $P(X=x)$ 的简写。
[^4]: joint entropy is a measure of the uncertainty associated with a set of random variables.
[^5]: 也常称为 information content, e.g. the average number of bits needed.
[^6]: $\log P(x) - \log Q(x)$
