1. Generalized Bayesian decision

• Formulation

  • Soft decision: $q_x(\cdot|y)$qx​(⋅∣y)
  • Cost function: $C(x,q_x)$C(x,qx​)

• Cost function

  • proper: $p_{x|y}(\cdot|y)=\arg\min\limits_{\{q_x\ge0:\sum_a q(a)=1\}} E[C(x,q_x(\cdot))|\mathsf{y}=y]$px∣y​(⋅∣y)=arg{qx​≥0:∑a​q(a)=1}min​E[C(x,qx​(⋅))∣y=y]
  • local: $C(x,q_x)=\phi(x,q_x(x))$C(x,qx​)=ϕ(x,qx​(x))

• Log-loss criterion: $C(x,q)=-A\log q_x(x) + B(x), \ \ \ A>0$C(x,q)=−Alogqx​(x)+B(x),   A>0

  • proper and local

  Theorem: When the alphabet $\mathcal{X}$X consists of at least 3 values ($|\mathcal{X}| \triangleq L ≥ 3$∣X∣≜L≥3), then the log-loss is the only smooth local, proper cost function.

  Proof: Let $q_{l} \triangleq q_{\times}\left(x_{l}\right), p_{l} \triangleq p_{x | y}\left(x_{l} | y\right), \phi_{l}(\cdot) \triangleq \phi\left(x_{l}, \cdot\right)$ql​≜q×​(xl​),pl​≜px∣y​(xl​∣y),ϕl​(⋅)≜ϕ(xl​,⋅)

  $proper \Longrightarrow p_{1}, \ldots, p_{L}=\underset{\left\{q_{1}, \ldots, q_{L} \geq 0: \sum_{l=1}^{L} q_{l}=1\right\}} {\arg\min} \sum_{l=1}^{L} p_{l} \phi_{l}\left(q_{l}\right)$proper⟹p1​,…,pL​={q1​,…,qL​≥0:∑l=1L​ql​=1}argmin​l=1∑L​pl​ϕl​(ql​)

  $拉格朗日乘子法 \Longrightarrow p_{1}, \ldots, p_{L}=\underset{q_{1}, \ldots, q_{L}}{\arg \min } \varphi, \quad \text { with } \varphi=\sum_{l=1}^{L} p_{l} \phi_{l}\left(q_{l}\right)+\lambda\left(p_{1}, \ldots, p_{L}\right)\left[\sum_{l=1}^{L} q_{l}-1\right]$拉格朗日乘子法⟹p1​,…,pL​=q1​,…,qL​argmin​φ, with φ=l=1∑L​pl​ϕl​(ql​)+λ(p1​,…,pL​)[l=1∑L​ql​−1]

  $proper \Longrightarrow \left.\frac{\partial \varphi}{\partial q_{k}}\right|_{q=p_{l}, l=1, \ldots, L}=p_{k} \dot{\phi}_{k}\left(p_{k}\right)+\lambda\left(p_{1}, \ldots, p_{L}\right)=0, \quad k=1, \ldots, L$proper⟹∂qk​∂φ​∣∣∣∣​q=pl​,l=1,…,L​=pk​ϕ˙​k​(pk​)+λ(p1​,…,pL​)=0,k=1,…,L

  • 由 locality 可推出 $\lambda$λ 为常数，$\phi_k(q)=-\lambda \ln q + c_k, \ \ \ k=1,...,L$ϕk​(q)=−λlnq+ck​,   k=1,...,L

• Gibbs inequality
  $if \ \ \ x\sim p_x(\cdot),\ \ \ \forall q(\cdot) \\ we\ \ have \ \ E_x[\log p(x)] \ge E[\log q(x)] \\ \sum_x p(x)\log p(x) \ge \sum_x p(x)\log q(x) \\ "=" \iff p(x)=q(x)$if   x∼px​(⋅),   ∀q(⋅)we  have  Ex​[logp(x)]≥E[logq(x)]x∑​p(x)logp(x)≥x∑​p(x)logq(x)"="⟺p(x)=q(x)

2. Discrete information theory

• Entropy: $H(\mathrm{x}) \triangleq \min _{q_{\mathrm{x}}} \mathbb{E}\left[C\left(\mathrm{x}, q_{\mathrm{x}}\right)\right]$H(x)≜minqx​​E[C(x,qx​)]

• Conditional entropy: $H(\mathrm{x} | \mathrm{y}) \triangleq \sum_{y} p_{\mathrm{y}}(y) H(\mathrm{x} | \mathrm{y}=y)$H(x∣y)≜∑y​py​(y)H(x∣y=y)
  $H(x | y=y) \triangleq \min _{q_{x}} \mathbb{E}\left[C\left(x, q_{x}\right) | y=y\right]$H(x∣y=y)≜minqx​​E[C(x,qx​)∣y=y]

• Mutual information: $I(\mathrm{x} ; \mathrm{y}) \triangleq H(\mathrm{x})-H(\mathrm{x} | \mathrm{y}) = H(x)+H(y)-H(xy)$I(x;y)≜H(x)−H(x∣y)=H(x)+H(y)−H(xy)

• Conditional mutual information: $I(\mathrm{x} ; \mathrm{y} | \mathrm{z}) \triangleq H(\mathrm{x} | \mathrm{z})-H(\mathrm{x} | \mathrm{y}, \mathrm{z})$I(x;y∣z)≜H(x∣z)−H(x∣y,z)

• Chain rule: $I(x ; y, z)=I(x ; z)+I(x ; y | z)$I(x;y,z)=I(x;z)+I(x;y∣z)

• 

• Information divergence(KL distance)

  • Definition

  $\begin{aligned} D\left(p_{\times} \| q_{\mathbf{x}}\right) & \triangleq \mathbb{E}_{p_{\mathbf{x}}}\left[-\log q_{\mathbf{x}}(\mathbf{x})\right]-\mathbb{E}_{p_{\mathbf{x}}}\left[-\log p_{\mathbf{x}}(\mathbf{x})\right] \\ &=\sum_{a} p_{\mathbf{x}}(a) \log \frac{p_{\mathbf{x}}(a)}{q_{\mathbf{x}}(a)} \end{aligned}$D(p×​∥qx​)​≜Epx​​[−logqx​(x)]−Epx​​[−logpx​(x)]=a∑​px​(a)logqx​(a)px​(a)​​

  • Properties

    • $\ge 0$≥0（只有 p=q 的时候才能取 = 吗？）

    • $I(x;y) = D(p_{x,y}||p_x p_y)$I(x;y)=D(px,y​∣∣px​py​)

    • $\lim _{\delta \rightarrow 0} \frac{D\left(p_{y}(\cdot ; x) \| p_{y}(\cdot ; x+\delta)\right)}{\delta^{2}}=\frac{1}{2} J_{y}(x)​$δ→0lim​δ2D(py​(⋅;x)∥py​(⋅;x+δ))​=21​Jy​(x)​

• Data processing inequality (DPI)

Theorem: if $x \leftrightarrow y \leftrightarrow t$x↔y↔t is a Markov chain, then
$I(x;y) \ge I(x;t)$I(x;y)≥I(x;t)
with “=” $\iff$⟺ $x \leftrightarrow t \leftrightarrow y$x↔t↔y is a Markov chain

Corollary: deterministic $g(\cdot)$g(⋅), $I(x;y) \ge I(x;g(y))$I(x;y)≥I(x;g(y))

Corollary: t=t(y) is sufficient $\iff I(x;y)=I(x;t)$⟺I(x;y)=I(x;t)

Proof: 应用互信息链式法则

Remark: 证明不等式的时候注意取等号的条件 $I(x;y|t)=0$I(x;y∣t)=0

---

Theorem: 若 $q_{\mathrm{x}^{\prime}}(b)=\sum_{a \in \mathcal{X}} W(b | a) p_{\mathrm{x}}(a), \quad q_{\mathrm{y}^{\prime}}(b)=\sum_{a \in \mathcal{X}} W(b | a) p_{\mathrm{y}}(a)$qx′​(b)=∑a∈X​W(b∣a)px​(a),qy′​(b)=∑a∈X​W(b∣a)py​(a)
那么对任意 $W(\cdot|\cdot)$W(⋅∣⋅) 有 $D(q_{x'}||q_{y'}) \le D(p_x||p_y)$D(qx′​∣∣qy′​)≤D(px​∣∣py​)

Proof: 待完成 …

Theorem: 对确定性函数 $\phi(\cdot)$ϕ(⋅)，$\mathsf{w}=\phi(\mathsf{z})$w=ϕ(z)，有 $J_{\mathsf{w}}(x)=J_{\mathsf{z}}(x)$Jw​(x)=Jz​(x)

Proof: 待完成 …

3. Information geometry

• Probability simplex

  • 若字符集有 M 个字符，则概率单形为 M-1 维的超平面，且只位于第一象限

  

• Boundary

  • 根据 p,q 是否位于边界(即存在 $p(y')=0$p(y′)=0) 可决定 $D(p||q)<\infty$D(p∣∣q)<∞ 还是 $D(p||q)=\infty$D(p∣∣q)=∞

• Local information geometry

  取 $p_0 \in \text{int}(\mathcal{P^Y})$p0​∈int(PY)，对任意分布(向量) $p$p 定义其归一化表示
  $\phi(y)=\frac{p(y)-p_0(y)}{\sqrt{2p_0(y)}}$ϕ(y)=2p0​(y)​p(y)−p0​(y)​
  $p_0$p0​ 的邻域被定义为一个球
  $\{p: |\phi_p(y)|\le B, \ \ \forall y \}${p:∣ϕp​(y)∣≤B,  ∀y}
  那么对小邻域内的两个分布 $p_1,p_2$p1​,p2​ 有
  $D(p_1 || p_2) = \sum_y |\phi_1(y)-\phi_2(y)|^2(1+o(1)) \approx ||\phi_1-\phi_2||^2$D(p1​∣∣p2​)=y∑​∣ϕ1​(y)−ϕ2​(y)∣2(1+o(1))≈∣∣ϕ1​−ϕ2​∣∣2
  证明：代入散度公式，应用泰勒级数展开化简。其中需要注意到
  $\sum_y \sqrt{2p_0(y)}\phi(y)=\sum_y p(y)-p_0(y) = 0$y∑​2p0​(y)​ϕ(y)=y∑​p(y)−p0​(y)=0
  Remark：直观理解就是小邻域内散度近似为欧氏距离

4. Information projection

• Definition: q 向闭集 $\mathcal{P}$P 内的投影 $p*=\arg\min_{p\in\mathcal{P}}D(p||q)$p∗=argminp∈P​D(p∣∣q)
  • 存在性：由于 $D(p||q)$D(p∣∣q) 非负且对 p 连续，而 $\mathcal{P}$P 非空且为闭集，因此一定存在
  • 唯一性：不一定唯一，但如果 $\mathcal{P}$P 为凸集，则 p* 唯一
• Pythagoras’ Theorem

Theorem(Pythagoras’ Theorem): p* 是 q 向非空闭凸集 $\mathcal{P}$P 上的投影，那么任意 $p\in\mathcal{P}$p∈P 有
$D(p||q) \ge D(p||p^*) + D(p^*||q)$D(p∣∣q)≥D(p∣∣p∗)+D(p∗∣∣q)
Proof: 取 $p_{\lambda}=\lambda p + (1-\lambda)p^* \in \mathcal{P}$pλ​=λp+(1−λ)p∗∈P

由投影定义可知 $\frac{\partial}{\partial \lambda} D(p_\lambda||q) \Big|_{\lambda=0} \ge 0$∂λ∂​D(pλ​∣∣q)∣∣∣​λ=0​≥0

代入化简可得证

Remark: 直观理解就是不可能通过多次中间投影，使整体的KL距离(散度)减小

---

Corollary: 如果 q 不在 $\mathcal{P^y}$Py 的边界上，那么其在线性分布族 $\mathcal{P}$P 上的投影 $p^*$p∗ 也不可能在 $\mathcal{P^y}$Py 的边界上，除非 $\mathcal{P}$P 中的所有元素都在某个边界上

Proof: 应用散度的 Boundary、毕达哥拉斯定理

• Linear families

  • Definition: $\mathcal{L}$L 是一个线性分布族，如果对于一组映射函数 $t(\cdot)=[t_1(), ..., t_K()]^T$t(⋅)=[t1​(),...,tK​()]T 和对应的常数 $\bar t = [\bar t_1, ..., \bar t_K]^T$tˉ=[tˉ1​,...,tˉK​]T，有 $\mathbb{E}_{p}\left[t_{i}(\mathrm{y})\right]=\bar{t}_{i}, \quad i=1, \ldots, K \quad$Ep​[ti​(y)]=tˉi​,i=1,…,K for all $p \in \mathcal{L}$p∈L
    $\underbrace{\left[\begin{array}{ccc}{t_{1}(1)-\bar{t}_{1}} & {\cdots} & {t_{1}(M)-\bar{t}_{1}} \\ {\vdots} & {\ddots} & {\vdots} \\ {t_{K}(1)-\bar{t}_{K}} & {\cdots} & {t_{K}(M)-\bar{t}_{K}}\end{array}\right]}_{\triangleq \mathbf{T}}\left[\begin{array}{c}{p(1)} \\ {\vdots} \\ {p(M)}\end{array}\right]=\mathbf{0}$≜T⎣⎢⎡​t1​(1)−tˉ1​⋮tK​(1)−tˉK​​⋯⋱⋯​t1​(M)−tˉ1​⋮tK​(M)−tˉK​​⎦⎥⎤​​​⎣⎢⎡​p(1)⋮p(M)​⎦⎥⎤​=0

  • 性质

    • $\mathcal{L}$L 的维度为 M-rank(T)-1
    • $\mathcal{L}$L 是一个闭集、凸集
    • $p_1,p_2 \in \mathcal{L}$p1​,p2​∈L，那么 $p=\lambda p_{1}+(1-\lambda) p_{2} \in \mathcal{P}^{\mathcal{Y}}, \ \ \lambda\in R$p=λp1​+(1−λ)p2​∈PY,  λ∈R，注意 $\lambda$λ 可以取 [0,1] 之外的数

    Theorem(Pythagoras’ Identity): q 向线性分布族 $\mathcal{L}$L 的投影 $p^*$p∗ 满足以下性质
    $D(p \| q)=D\left(p \| p^{*}\right)+D\left(p^{*} \| q\right), \quad \text { for all } p \in \mathcal{L}$D(p∥q)=D(p∥p∗)+D(p∗∥q), for all p∈L
    Proof: 类似前面不等式的证明，只不过现在由于 $\lambda\in R$λ∈R 所以不等号变成了等号

    Theorem(Orthogonal families): $p*\in\mathcal{P^Y}$p∗∈PY 为任一分布，则向线性分布族 $\mathcal{L_t}(p^*)$Lt​(p∗) 的投影为 $p^*$p∗ 的所有分布都属于一个指数分布 $\mathcal{\varepsilon}_t(p^*)$εt​(p∗)
    $$
    \mathcal{L}{\mathbf{t}}\left(p^{*}\right) \triangleq\left{p \in \mathcal{P}^{\mathcal{Y}}: \mathbb{E}{p}[\mathbf{t}(\mathbf{y})]=\overline{\mathbf{t}} \triangleq \mathbb{E}_{p^{*}}[\mathbf{t}(\mathbf{y})]\right} \

    \begin{aligned} \mathcal{E}_{\mathbf{t}}\left(p^{}\right) \triangleq\left{q \in \mathcal{P}^{\mathcal{Y}}: q(y)=p^{}(y) \exp \left{\mathbf{x}^{\mathrm{T}} \mathbf{t}(y)-\alpha(\mathbf{x})\right}\right.\ \text { for all }\left.y \in \mathcal{Y}, \text { some } \mathbf{x} \in \mathbb{R}^{K}\right} \end{aligned}
    $$
    其中需要注意的是 $\mathcal{L}_{\mathbf{t}}\left(p^{*}\right),\mathcal{E}_{\mathbf{t}}\left(p^{*}\right)$Lt​(p∗),Et​(p∗) 的表达形式并不唯一，括号内的 $p^*$p∗ 均可以替换为对应集合内的任意一个其他分布，他们表示的是同一个集合

    

    Remarks：

    1. 根据上面的定理，可以由 $t(\cdot), \bar t$t(⋅),tˉ 求出 q 向线性分布族的投影 p*
    2. 在小邻域范围内，可以发现 $\mathcal{L}_{\mathbf{t}}\left(p^{*}\right),\mathcal{E}_{\mathbf{t}}\left(p^{*}\right)$Lt​(p∗),Et​(p∗) 的正规化表示 $\phi_\mathcal{L}^T \phi_\mathcal{E}=0$ϕLT​ϕE​=0，即二者是正交的

• 点赞
• 收藏
• 分享
• • 文章举报

Bonennult 发布了37 篇原创文章 · 获赞 27 · 访问量 2万+ 私信 关注