自学(3)：数学基础

大二上学期及寒假的自学笔记，由信息论、最优化方法、形式语言与自动机和博弈论组成。

一、信息论

1. 错误检测码

1. 奇偶校验码：在数据后加一位，使得 1 的个数为奇数或偶数（例：$\mathrm{ASCII}$）
2. 改进：按 $N$ 位划分数据块，添加 $N$ 位校验码
3. 加权校验码：$wxyz\to 4w+3x+2y+z$，再加一位使得和能被某数整除（例：身份证号）
4. $x_4=x_1+x_2,x_5=x_1+x_3,x_6=x_2+x_3$

2. 错误纠正码

1. 线性码：将 $k$ 位映射到 $n$ 位，$x=sG$，$G$ 为 $k\times n$ 矩阵
2. 校验：$Hy^T\neq 0$ 则有错，$H$ 为 $(n-k)\times n$ 矩阵，$HG^T=0$
3. 对偶码：将 $H$ 作为生成矩阵，$G$ 作为校验矩阵
4. 例：三重重复码、$(7,4)\ \mathrm{Hamming}$ 码 $(p_1=x_1+x_2+x_4,p_2=x_1+x_3+x_4,p_3=x_2+x_3+x_4)$

3. 数据压缩

1. 熵：$H(X)=-\sum p(x)\log p(x)$
2. 香农第一定理：编码平均长度 $\geq H(X)$，取等时必为平均分布
3. 数据压缩码：$\mathrm{Huffman}$ 码（最优前缀码、最优唯一可译码）

4. 信道编码

1. 定义 $P_{X,Y}(x_i,y_j)$：发出 $x_i$ 且接收 $y_j$ 的概率，$P_{Y|X}(y_j|x_i)$：发出 $x_i$ 时接收 $y_j$ 的条件概率
2. 熵：$H(X,Y)=-\sum P_{X,Y}(x_i,y_j)\log P_{X,Y}(x_i,y_j)$，$H(Y|X)=-\sum P_{X,Y}(x_i,y_j)\log P_{Y|X}(y_j|x_i)$
3. 链式法则：$H(X,Y)=H(X)+H(Y|X)$（信道的总熵等于输入的熵加上信道引入的熵）
4. 互信息：$I(x_i;y_j)=\log(\frac{1}{P_{X}(x_i)})-\log(\frac{1}{P_{X|Y}(x_i|y_j)})$（接收到 $y_j$ 后对 $x_i$ 的不确定性减少了多少）
5. 平均互信息：$I(X;Y)=\sum P_{X,Y}(x_i,y_j)I(x_i;y_j)=H(X)-H(X|Y)$
6. 性质：$I(X;Y)=H(X)$ 当且仅当无损；$I(X;Y)=0$ 当且仅当 $X,Y$ 独立（无信息量）
7. 信道容量：$\displaystyle C=\max_{P_X(\cdot)}I(X;Y)$（对所有可能的输入分布求最大平均互信息）
8. 香农第二定理：若 $R<C$，则存在编码使得误码率 $\to 0$，只要码长足够长；若 $R>C$，则任何编码误码率均有下限，其中 $R$ 为信道传输速率（用几个比特传输一个符号）

二、最优化方法

1. 最优性理论

1. 共轭函数：$\displaystyle f^*(y)=\sup_{x\in \mathrm{dom}f}(y^Tx-f(x))$，二次共轭 $\displaystyle f^{**}(x)=\sup_{y\in \mathrm{dom}f^*}(y^Tx-f^*(y))=f(x)$
2. 拉格朗日函数 $L(x,\lambda)=f(x)+\sum_{i=1}^m \lambda_i g_i(x),\lambda_i \geq 0,g_i(x)\leq 0$ 是原函数的下界
3. 对偶函数 $\displaystyle g(\lambda)=\inf_{x\in \mathrm{dom}f}L(x,\lambda)$ 是原问题的下界，对偶问题即最优下界 $\displaystyle \max_{\lambda} g(\lambda),\lambda \geq 0$
4. 一阶 $\mathrm{KKT}$ 条件：
   1. 可行性条件：$g_i(x^*)\leq 0,h_j(x^*)=0$
   2. 对偶可行性条件：$\lambda_i^* \geq 0$
   3. 驻点条件：$\nabla_x L(x^*,\lambda^*)=0$
   4. 互补松弛条件：$\lambda_i^* g_i(x^*)=0$
5. 二阶条件：$d^T\nabla_{xx}^2 L(x^*,\lambda^*)d \geq 0$ 对所有临界锥内的 $d$，即 $\lambda_i^*\nabla g_i(x^*)^Td=0$

2. 无约束优化

1. 牛顿法：$f(x^k+d^k)\approx f(x^k)+\nabla f(x^k)^Td^k+\frac{1}{2}d^{kT}\nabla^2 f(x^k)d^k$，右边驻点 $\nabla f(x^k)+\nabla^2 f(x^k)d^k=0$
2. 拟牛顿法：估计 $\nabla^2 f(x^k)$，秩一更新 $B^{k+1}=B^k+auu^T$，$\mathrm{BFGS}$ 法 $B^{k+1}=B^k+auu^T+bvv^T$
3. 信赖域法：求解子问题 $\min m_k(d)=f(x^k)+\nabla f(x^k)^Td+\frac{1}{2}d^TB^kd,|d|\leq \Delta_k$
4. 最小二乘高斯-牛顿法：$f(x)=\frac{1}{2}\sum_{i=1}^m r_i^2(x)$，$\nabla f(x)=J(x)^T r(x),\nabla^2 f(x)=J(x)^T J(x)+\sum_{i=1}^m r_i(x)\nabla^2 r_i(x)\approx J(x)^T J(x)$，计算 $QR$ 分解求解

3. 约束优化

1. 罚函数法：外点二次罚函数罚因子递增，内点对数罚函数罚因子递减
2. 增广拉格朗日函数法：$L_\sigma(x,\lambda)=f(x)+\sum\lambda_i c_i(x)+\frac{\sigma}{2}\sum \hat{c_i}^2(x)$，$\lambda_i^{k+1}=\max\{\lambda_i^k+\sigma_k c_i(x^{k+1}),0\}$ 与 $\sigma$ 交替更新

4. 复合优化

1. 邻近算子法：$\mathrm{prox}_h(x)=\arg\min\{h(u)+\frac{1}{2}|u-x|^2\}$，$\min \psi(x)=f(x)+h(x)$，可微 $f$ 做梯度下降，非光滑 $h$ 用邻近算子
2. 分块坐标下降法：将自变量 $x$ 拆成 $s$ 块，固定其他块交替优化每一块
3. 随机优化：详见机器学习

三、形式语言与自动机

1. 基本概念

1. 0型/短语结构文法 $\mathrm{PSG}$：无限制，生成递归可枚举语言
2. 1型/上下文有关文法 $\mathrm{CSG}$：$\forall\alpha\to\beta\in P,|\beta|\ge|\alpha|$
3. 2型/上下文无关文法 $\mathrm{CFG}$：$\alpha\in V$
4. 3型/正则/右线性文法 $\mathrm{RG}$：$A\to w|wB,A,B\in V,w\in T^*$

2. 正则语言

1. 有限状态自动机 $\mathrm{FA}$：读入读头字符，转移状态，右移读头
2. 正则表达式 $\mathrm{RE}$：$r,s$ 表示语言 $R,S$，$(r+s)$ 表示 $R\cup S$；$a^+,a^*$
3. 正则文法 $\Leftrightarrow$ 正则表达式 $\Leftrightarrow$ 有限状态自动机 $\mathrm{FA}$

3. 上下文无关语言

1. 乔姆斯基范式 $\mathrm{CNF}$：$A\to BC|a$
2. 格雷巴赫范式 $\mathrm{GNF}$：$A\to a\alpha,a\in T,\alpha\in V^*$
3. 自嵌套文法：$\exists A\overset{+}{\Rightarrow} \alpha A\beta,\alpha,\beta\in (V\cup T)^+$
4. 非自嵌套文法 $\Rightarrow$ 正则语言
5. 下推自动机 $\mathrm{PDA}$：基于 $\mathrm{GNF}$，读入读头字符，弹出栈顶符号，压入栈顶符号串并转移状态，右移读头
6. 上下文无关文法 $\Leftrightarrow$ 下推自动机

4. 图灵机

1. 图灵机 $\mathrm{TM}$：读入读头字符，写入带符号，左/右移读头，转移状态
2. 变形：双向、多带、不确定、多维、多头、离线（只读）
3. 图灵机 $\Leftrightarrow$ 短语结构文法
4. 可判定性：递归语言（图灵机停机），是递归可枚举语言的真子集
5. $\mathrm{P/NP/NPC/NP-hard}$：多项式可解/多项式可验证/多项式归约到所有 $\mathrm{NP}$ 且属于 $\mathrm{NP}$/多项式归约到所有 $\mathrm{NP}$

5. 上下文有关语言

1. 线性有界自动机 $\mathrm{LBA}$：非确定图灵机，读头限制在端点间，端点不可改写
2. 上下文有关文法 $\Leftrightarrow$ 线性有界自动机

四、博弈论

1. 自身的策略要最大化对方的策略可能带来的最小收益
2. 鞍点：每个参与者的策略在给定其他参与者策略的情况下都是最优的（纯策略纳什均衡）
3. 混合策略：最大化对方选择每一个纯策略所带来的最小期望收益
4. 最大最小值定理：零和博弈两个混合策略线性规划互为对偶，最优值相等（对偶定理）
5. 非常和博弈：纳什均衡存在定理（纯策略或混合策略），但不一定是帕累托最优