概率论

贝叶斯网络

贝叶斯网络可以视为联合概率的一种分解的图表示。贝叶斯网络的参数为条件概率表 CPT。

对于节点 $Y$ 在给定其父节点 $\mathrm{Parents}(Y)=\{X_1,X_2,\cdots ,X_k\}$ 的情况下，其与所有非后代节点条件独立

联合概率的边缘化在贝叶斯网络中

• 先验概率计算需要边缘化无关变量只需要关注祖先图

Causal prediction：P(Effect | Reason) 直接查表
Diagnostic inference：P(Reason | Effect)，使用贝叶斯定理

d-separation

考虑三点二边的基本情况：

1. Common cause / Fork：$X\leftarrow Z\to Y$：
   • $Z$ 未知时，$X,Y$ 不独立（存在信息流）
   • $Z$ 已知时，$X,Y$ 条件独立。$X,Y$ 的概率分布都可以通过 $Z$ 的 Causal prediction 确定。
   • $\text{Umbrella}\leftarrow \text{Rain}\to \text{Wet}$
2. Chain / Causal chain：$X\to Z\to Y$
   • $Z$ 未知时，$X,Y$ 不独立
   • $Z$ 已知时，$X,Y$ 条件独立。$X$ 的概率分布可以通过 $Z$ 的 Diagnostic inference 确定，$Y$ 的概率分布可以用 $Z$ 的 Causal prediction 确定
   • $\text{Virus}\to \text{Fever}\to \text{Skip class}$
3. Collider / V-structure：$X\to Z\leftarrow Y$
   • $Z$ 未知时，$X,Y$ 条件独立独立
   • $Z$ 已知，$X,Y$ 不独立
   • $\text{Earthquake}\to \text{Alarm}\leftarrow \text{Theft}$

如果 $X,Y$ 之间的所有通路都被上述中的 $Z$（已知或未知）阻断，那么 $X,Y$ 在给定已知的 $Z$ 的情况下条件独立

Markov Blanket

一个结点 $X$ 的马尔可夫毯包括

• $\mathrm{Parents}(X)$
• $\mathrm{Children}(X)$
• $\mathrm{Spouses}(X)$

$V\setminus MB(X)$ 的信息相对于 $MB(X)$ 提供的信息而言都是冗余的，马尔可夫毯是最小的能够提供完全描述 $X$ 的信息的点集，或者说屏蔽 $X$ 所需要的最小集合

信息论

• 一个事件（Event）$X$ 在被观测之前（未知情况下）是一个随机事件。如果其一个状态 $x$ 出现的概率为 $p(x)$ 那么这个状态所蕴含的信息量（观测到时的惊讶度）为 $I(x)=-{\log }_{2}p$。一个事件的信息熵（观测事件 $X$ 带来的信息量期望、或者说最优编码需要的比特数）为所有状态的信息量关于它们发生概率的加权平均 $H(X)=\mathbb{E}[I(X)]=\mathbb{E}[-{\log }_{2}p(X)]=-\sum _{x}p(x){\log }_{2}p(x)$。

• 信息熵的最大值在均匀分布时取得。

• 一个消息（Message）是一列相互独立的事件

• 我们可以类似地定义事件的联合熵 $H(X,Y)$（同时观测事件 $X,Y$ 的信息量期望）、条件熵 $H(X\mid Y)=H(X,Y)-H(Y)$（已经观测完 $Y$ 的情况下观测 $X$ 带来的的信息量期望）

• 交叉熵和相对熵：$X$ 的真实分布为 $P(X)$，我们的预测分布为 $Q(X)$，交叉熵 $\mathrm{CE}(P,Q)=-\sum _{x}P(X=x){\log }_{2}Q(X=x)$，理解为针对分布 $Q(X)$ 设计的最优编码在真实分布下的平均编码长度，相对熵（KL 散度）${\mathrm{D}}_{\mathrm{KL}}(P\parallel Q)=\mathrm{CE}(P,Q)-H(P)$ 即真实分布下针对预测分布设计的最优编码的相对于针对真实分布设计的最优编码所需要的额外编码长度，这可以衡量预测分布到真实分布之间的差距。${\mathrm{D}}_{\mathrm{KL}}(P,Q)=0\iff P=Q$；相对熵不对称。

• 互信息：$I(X;Y)=H(X)-H(X\mid Y)=H(X)+H(Y)-H(X,Y)$ 是 $X,Y$ 的所蕴含的共同信息的信息量。它是一个具有普适性的相关性测度（比如相对于相关系数而言）。

• 当事件被观测之后，成为了确定性的状态记录，此时视为仅仅具有一种状态，蕴含零信息量，我们获得了其具有的信息量。???????????

• 这里的观测者 “我们" 可以视为一个特定的条件概率分布 $P(Y\mid X)$，$Y$ 为观测者接收到的来自于信源的信息，$Y$ 的分布表示观测者对于某一个信源的认知，$X$ 是信源，$X$ 的分布表示信源的真实情况。

• 一次观测可以视为条件概率分布 $P(Y\mid X)$ 从此次观测前的先验分布到此次观测后的后验分布的转化。

• 不同的观测者具有不同的最初先验分布；相同的观测者在不同的时间也会具有随着观测行为不断更新的不同的后验分布。

• 重复观测一个事件不会重复获得信息量。对于已经可以被当前的先验分布完美预测的信息，后验分布不会发生改变，即新的观测结果符合我们先前的认知。

决策树

决策树（DAG？）描述了一个以最大化信息获取效率消除不确定性的过程

根节点是原始数据，每个中间节点进行一次特征划分，叶子节点是已经被完全分类的数据。

对于一个中间节点，待划分的随机变量为 $Y$，候选的划分特征为 $X_1,X_2,\cdots ,X_k$，我们的策略是选择 $\arg \underset{X_i}{max}\mathrm{Gain}(Y,X_i)$ 其中信息增益 $\mathrm{Gain}(Y,X_i)=H(Y)-H(Y\mid X)=I(Y;X)$（知道 $X$ 能减少多少 $Y$ 的不确定性）

随机过程

随机过程是一列表示不同时间的系统状态的随机变量 $S_1,S_2,\cdots ,S_t$

Markov 过程是满足 $\mathbb{P}(S_{t+1}\mid S_1,S_2,\cdots ,S_t)=\mathbb{P}(S_{t+1}\mid S_t)$ 的随机过程，如果系统状态的全集为有限集 $U$，那么我们可以用状态转移矩阵 $P$ 来描述 Markov 过程，$P_{ij}$ 表示已知当前状态 $s_i$，下一个状态为 $s_j$ 的概率，如果把状态 $S_i$ 视为一个以不同状态取值概率的列向量，我们有 $(S_{t+1}{)}_j=\sum _i{P}_{ij}(S_t{)}_i=P_{:j}^T\cdot S_t$，$S_{t+1}=P^T{S}_t$，$S_{t+1}^T=S_t^{T}P$，所以把 $S_i$ 定义为行向量会更好。定义行向量 ${\pi }_i$ 满足 $({\pi }_i{)}_j=P(S_i=s_j)$ 就有 ${\pi }_n={\pi }_0{P}^n$。

平稳分布 $\pi =\pi P$ 对应 $P$ 的特征值为 $1$ 的正单位左特征向量。

收敛性？

马尔可夫决策过程

马尔可夫决策过程（MDP）：$(S,A,P,R,\gamma )$

• $S$ 为状态空间
• $A$ 为动作空间
• $P$ 为状态转移概率，$P(s^{\prime }\mid s,a)=P(S_{t+1}=s^{\prime }\mid S_t=s,A_t=a)$ （如果环境具有随机性其可能非定值）
• $R$ 为奖励函数 $R(s,a,s^{\prime })=\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a,S_{t+1}=s^{\prime }]$
• $\gamma$ 折扣因子（远视程度），介于 $[0,1]$

我们的目标是找到策略 $\pi (a\mid s)$ 来最大化累计回报 $G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$

状态价值函数 $V^{\pi }(s)$ 当前处于 $s$ 按照 $\pi$ 走下去的期望总回报
动作价值函数 $Q^{\pi }(s,a)$ 当前处于 $s$ 并采取 $a$ 之后按照 $\pi$ 走下去的期望总回报。

优化

一般形式 $minf(x)\text{ s.t. }{g}_i(x)\le 0(i=1,2,\cdots ,m),h_j(x)=0(j=1,2,\cdots ,n)$ ，其中 $X\in {\mathbb{R}}^d,f:{\mathbb{R}}^d\to \mathbb{R},g_i:{\mathbb{R}}^d\to \mathbb{R},h_j:{\mathbb{R}}^d\to \mathbb{R}$

我们只关注具有良好性质的优化问题：凸优化问题

• $f$ 是凸函数
• $g_i$ 是凸函数
• $h_j$ 是仿射函数

这些性质蕴含了

• 凸优化问题的可行域是一个凸集
• 凸优化问题在可行域上的局部极小值必定是全局最小值

凸函数的定义

我们考虑的函数为 $f:\mathrm{\Omega }\to \mathbb{R}$ ，$\mathrm{\Omega }$ 是 ${\mathbb{R}}^d$ 的一个凸集。

零阶几何定义：任意 $x,y\in \mathrm{\Omega }$ 和 $\theta \in [0,1]$ 都有 $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$
一阶微分定义：如果 $f\in C^1(\mathrm{\Omega })$，那么 $f$ 的凸性等价于任意 $x,y\in \mathrm{\Omega }$ 都有 $f(y)\ge f(x)+\mathrm{\nabla }f(x{)}^T(y-x)$，其中 $\mathrm{\nabla }f(x)={[\frac{\partial f}{\partial x_1}\cdots \frac{\partial f}{\partial x_d}]}^T$ 。
二阶微分定义：如果 $f\in C^2(\mathrm{\Omega })$，那么 $f$ 的凸性等价于任意 $x\in \mathrm{\Omega }$ 都有 ${\mathrm{\nabla }}^{2}f(x)⪰0$，其中 ${\mathrm{\nabla }}^{2}f(x)$ 为海森矩阵。

等价性证明？

凸优化问题

凸优化问题的可行域是一个凸集：可行域 $\mathcal{D}=\{x\in {\mathbb{R}}^d\mid g_i(x)\le 0,h_j(x)=0\}$，考虑任意 $x,y\in \mathcal{D}$ 和 $\theta \in [0,1]$：

• 利用 $g_i$ 在 $\mathcal{D}\subseteq \mathrm{dom}(g_i)$ 上的凸性，$g_i(\theta x+(1-\theta )y)\le \theta g_i(x)+(1-\theta )g_i(y)$
• 利用 $h_i$ 在 $\mathcal{D}\subseteq \mathrm{dom}(h_j)$ 上的仿射性，$h_j(\theta x+(1-\theta )y)=\theta h_j(x)+(1-\theta )h_j(y)$
• 点 $\theta x+(1-\theta )y$ 仍然在可行域内

凸优化问题在可行域上的局部极小值必定是全局最小值：利用反证法，根据可行域的凸性构造取值在局部极小值和全局最小值之间的点，和局部极小值的局部最小性引发矛盾。

优化方法

Unconstrained minimization：

• 迭代：
  • 梯度下降 $x_{t+1}=x_t-\eta \mathrm{\nabla }f(x_t)$
    • 固定梯度，梯度过小导致收敛慢
  • 牛顿迭代 $x_{t+1}=x_t-({\mathrm{\nabla }}^{2}f(x_t){)}^{-1}\mathrm{\nabla }f(x_t)$
    • 如果目标函数为二次凸函数那么一步到位
    • 高维时 Hessian 求逆 $O(n^3)$ 储存 $O(n^2)$ 用 L-BFGS / Adam 代替
• 直接：好的形式可以有封闭解

Constrained minimization：

• Penalty Function Method
  • Quadratic Penalty Method
  • Interior-Point Method（Logarithmic Penalty Method, Barrier Method）
  • Augmented Lagrangian method

External Penalty Method：

对 $g_i(x)>0$ 和 $h_j(x)\ne 0$ 施加关于差的二次约束，通过不断求解问题 $P(x,{\sigma }_k)$ 并增大惩罚因子来逼近最优解（最终时尽量进入约束范围）

Internal Penalty Method（只有不等式约束）

需要找到一个合格的初始点，迭代点始终可行，通过不断求解问题 $B(x,{\mu }_k)$ 并减小障碍因子来逼近最优解（开始时尽量远离边界）

Central path：$x^{\star }(\mu )=\arg \underset{x}{min}B(x,\mu )$

• 曲线 $x\ast (\mu ),\mu \in [0,\mathrm{\infty })$ 被称为中心路径。
• 点 $x^{\star }(\mathrm{\infty })$ 被称为可行域的解析中心

内点法的迭代方法通常需要一步额外的投影（到可行域）

线性规划 Linear Programming

规范形式（Canonical Form）：

• 所有不等式约束和等式约束均为一次函数
• 目标函数为一次函数

转化

• 把所有的等式约束转化为两个只有不等号相反的不等式约束
• 把所有不等式约束按照拼接成一个矩阵不等式约束
• 对于自由 $x$ 取 $x=x^{+}-x^{-}$ 并施加 $x^{+}\ge 0,x^{-}\ge 0$ 然后进行拼接 $x_{new}=[{x^{+}}^T{x^{-}}^T{]}^T\ge 0$

规律：

• 所有的一次等式约束都可以写成一次不等式约束，所以我们不需要考虑等式约束
• 多个一次不等式约束的紧凑写法：所有的一次不等式约束可以写成 $Ax\le b$

线性规划基本定理：线性规划问题的可行域是一个凸多面体，且其最优解必定在可行域的某个顶点上取到。

单纯形法：目标函数极大化，约束条件通过引入松弛变量变为等式，变量全非负。变为 $n$ 个变量 $m$ 个线性方程

• 选 $m$ 个变量使系数矩阵可逆，称为基变量，令所有非基变量为零能得到一个唯一解，如果满足 $\ge 0$ 那么称为一个基可行解（通常选择原点作为基可行解）

二次规划 Quadratic Programming

• 所有不等式约束和等式约束均为一次函数
• 目标函数为凸二次函数

转化

• 把所有一次等式约束和一次不等式约束转化为 $Ax\le b$

二次约束二次规划 Quadratically Constrained Quadratic Programming

• 所有不等式约束均为一次函数或者二次凸函数，所有等式约束为一次函数
• 目标函数为二次函数

转化

• 一次不等式约束可以视为二次凸不等式约束的退化情形 $P_i=0$，不同的二次等式约束似乎没有紧凑写法，所以保留 $\frac{1}{2}{x}^{\mathrm{\top }}{P}_{i}x+q_i^{\mathrm{\top }}x+r_i\le 0$
• 一次等式约束这里的得到了保留，原因何在？

图的最大割：分割无向图 $G=(V,E)$ 的 $V$ 为 $S,T$，最大化 $\mathrm{card}(S\times T\cap E)$，令 $x_i=1\text{ if }{v}_i\in S\text{ else }-1$

• 等价于 $\underset{(v_i,v_j)\in E}{max}\frac{1}{2}(1-x_i{x}_j)\text{ s.t. }{x}_i\in \{-1,1\}$
• 等价于 $max\frac{1}{4}\sum _{i,j}(1-x_i{x}_j)G_{ij}\text{s.t. }{x}_i^2=1$
• 等价于 $min{x}^{T}Gx\text{ s.t. }{x}_i^2=1$

几何规划 Geometric Programming

几何规划的原始形式是非凸，但是通过对数变量带话可以被转化为凸优化问题

GP 单项式（Monomial）：$f(x)=c{x}_1^{a_1}{x}_2^{a_2}\cdots x_n^{a_n}$ 满足 $c>0$ 和 $a_i\in \mathbb{R}$
GP 正项式（Posynomial）：多个 GP 单项式的和

• $f,g_i$ 为正项式，$h_j$ 为单项式

半正定规划 Semidefinite Programming

半正定矩阵约束？

凸优化问题分类之间的包含关系？

Lagrange 对偶

Primal problem：

引入 ${\lambda }_i\ge 0$ 和 ${\mu }_j\in \mathbb{R}$ 构造 Lagrange 函数并改写原问题的目标函数（Primal Objective）

定义 Lagrange 对偶函数和 Lagrange 对偶问题

弱对偶性：恒成立 $d^{\star }\le p^{\star }$
强对偶性：$d^{\star }=p^{\star }$

Slater 条件是凸优化问题的强对偶性成立的一个充分条件：

• 存在可行域内部的一个点使得所有非线性不等式约束都严格成立，这个点被称为严格可行点

原问题的最优解为 $x^{\star }$，对偶问题的最优解为 ${\lambda }^{\star },{\mu }^{\star }$

• 对于凸优化问题，如果 $f,g_i,h_j$ 一阶可微，那么 $(x,\lambda ,\mu )=(x^{\star },{\lambda }^{\star },{\mu }^{\star })$ 等价于 $(x,\lambda ,\mu )$ 满足 KKT 条件。
• 对于非凸优化问题，满足特定条件的局部或者全局最优解也满足 KKT 条件

KKT 条件：

• 平稳性：${\mathrm{\nabla }}_{x}L(x^{\star },{\lambda }^{\star },{\mu }^{\star })=0$
• 原始可行性：$g_i(x^{\star })\le 0\wedge h_j(x)=0$
• 对偶可行性：${\lambda }_i^{\star }\ge 0$
• 互补松驰性：${\lambda }_i^{\star }{g}_i(x^{\star })=0$

理解平稳性：

$-\mathrm{\nabla }f(x^{\ast })$ 是 $f$ 梯度带来的向低处的拉力，$g_i$ 是超平面单向墙，$-\mathrm{\nabla }{g}_i(x^{\ast })$ 是 $g_i$ 带来的防止走出墙外的拉力方向，${\lambda }_i$ 是这个拉力的相对大小，$h_i$ 是超平面轨迹限制，$-\mathrm{\nabla }{h}_j(x^{\ast })$ 是 $h_j$ 带来的防止偏离轨迹的拉力方向，${\mu }_j$ 是这个拉力的相对大小。三者达成一个受力平衡

理解互补松驰性

• 如果 $g_i(x^{\ast })<0$，此时在墙内，没有拉力 ${\lambda }_i=0$
• 如果 $g_i(x^{\star })=0$，此时恰好在墙上，存在非负拉力。