Likelihood

似然函数：表示统计模型参数中似然性的（参数的）函数

$$L(w|Y) = \alpha P(Y|W=w)$$

• $Y$：观测所得结果，事件 $Y$
• $W$：模型参数
• $\alpha$：正常量

• 似然函数可以理解为 条件概率的逆反

  • 似然：在已知某些观测所得结果上，对有关事物性质的参数进行估计
    • 似然性：某个参数为特定值的可能性
    • 单独查看某个似然值无价值，要将各种似然值一起比较
  • 概率：在已知某些参数上，预测之后观测所得到结果

• 形式上，似然函数也是条件概率函数，但关注统计模型中参数

  • 似然函数不满足归一性，乘正常数仍然是似然函数
  • 同一似然函数代表的模型中，某个参数具有多种可能，如果存在参数使得似然函数值最大，则该值为最合理的参数值
    • 假设不同模型（经验得到），选择不同的统计模型
    • 则有不同的概率密度（分布）函数，得到不同的似然函数

应用

• 最大似然估计：选取似然函数，整理之后求最大值点

  • 实际中一般选取似然函数对数作为求解对象，结果同直接求似然函数最大值点
  • 似然函数最大值点不一定唯一，也不一定存在
  • 相较于矩估计
    • 精度较高，信息损失少
    • 计算量大

• 似然比检验：利用似然函数检测假设、限制是否有效

  • 将加入某个限制的复杂某些的似然函数最大值和简单模型的似然函数最大值比较，检测某个参数限制是否正确
    • 若参数限制正确，则不应造成似然函数最大值的大幅变动
  • 尼曼-尼尔森引理 说明：似然比检验是所有具有同等显著性差异的检验中，最有统计效力的检验

条件概率分布似然函数

$$\begin{align*} L_P(W|X,Y) &= \prod P(Y|X,W) \\ &= \prod_{x,y} P(Y|X,W)^{N_{x,y}} \\ &= \prod_{x,y} P(Y|X,W)^{N * \tilde P(X,Y)} \\ log(L_P(W|X,Y)) &= N \sum_{x,y} \tilde P(X,Y) log(P(Y|X,W)) \end{align*}$$

• $P$：（所选择）统计模型的概率分布函数
• $\tilde P$：$X,Y$ 的实际分布
• $X,Y$：离散随机变量，$X$ 自变量观察值、$Y$ 因变量观察值
• $W$：条件概率分布 $P$ 的参数
• $N$，$N_{x,y}$：样本数量，取值为 $x,y$ 的样本数量

• 这里是条件概率分布的似然函数，用 $(X,Y)$ 联合分布同样

  $$\begin{align*} L_P &= \prod P(X,Y|W) \\ &= \prod P(Y|X,W) P(X|W) \\ &= \prod P(Y|X,W) P(X) \\ &= \prod P(Y|X,W) \prod P(X) \end{align*}$$

  • 考虑 $W$ 是条件分布参数，与 $X$ 分布无关，有 $P(X|W) = P(X)$
  • 再考虑似然函数乘正常数不改变性质，则结果同上

• 对数似然函数中，样本量 $N$ 可省略

统计量

统计量：统计理论中对数据进行分析、检验的变量

• 传统的统计量具有显式解析表达式

  • 均值：数据之和除数量
  • 中位数：数据中间者

• 统计量同样可以理解为和数据相关优化问题的解

  • 均值：离差平方和最小
  • 中位数：划分均匀

  • 优化问题目标本身也是统计量

Cauthy-Schwarz 不等式

• https://zhuanlan.zhihu.com/p/22004031
• https://zhuanlan.zhihu.com/p/129033407
• https://zhuanlan.zhihu.com/p/70315155
• https://zhuanlan.zhihu.com/p/85283405

常用定理

Lucas 定理

$$C(n, m) \% p = (C(n//p, m//p) * C(n\%p, m\%p)) \% p$$

• $p < 10^5$：必须为素数

Holder 定理

$|x|^{*}_p = |x|_q$

• $\frac 1 p + \frac 1 q = 1$

Radial Basis Function

• RBF 径向基函数：取值仅依赖到原点距离的实值函数，即 $\phi(x) = \phi(|x|)$

  • 也可以按照距离某中心点 $c$ 的距离定义，即 $\phi(x) = \phi(|x-c|)$
  • 其中距离一般为使用 $L_2$ 范数，即欧式距离
  • 函数 $\phi$ 一般与 $|x|$ 负相关

• 径向基函数最初用于解决多变量插值问题

  • 即以各样本为中心创建多个径向基函数
  • 多个径向基函数加权加和即得到拟合的函数曲线，可用于函数插值

  

常见径向基函数

• 定义 $r=|x-x_i|$

• 高斯函数

  $$\phi(r) = e^{-(\epsilon r)^2}$$

• Multiquadric 多二次函数：

  $$\phi(r) = \sqrt {1 + (\epsilon r)^2}$$

• Inverse Quadric 逆二次函数：

  $$\phi(r) = \frac 1 {1 + (\epsilon r)^2}$$

• Polyharmonic Spline 多重调和样条：

  $$\begin{align*} \phi(r) &= r^k, & k=1,3,5,\cdots \\ \phi(r) &= r^k (ln(r))^{}, & k=2,4,6,\cdots \\ \end{align*}$$

• Thin Plate Spline 薄板样条（多重调和样条特例）：

  $$\phi(r) = r^2 ln(r)$$

Truncated Gradient

L1正则化法

L1正则化

$$w^{(t+1)} = w^{(t)} - \eta^{(t)}g^{(t)} - \eta^{(t)} \lambda sgn(w^{(t)})$$

• $\lambda$：正则化项参数
• $sgn$：符号函数
• $g^{(t)}=\nabla_w L(w^{(t)}, Z^{(t)})$：损失函数对参数梯度

• L1正则化项在0处不可导，每次迭代使用次梯度计算正则项梯度
• OGD中每次根据观测到的一个样本进行权重更新 （所以后面正则项次梯度只考虑非0处？？？）

简单截断法

简单截断法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_0 (w^{(t)} - \eta^{(t)} G^{(t)}, \theta) \\ T_0(v_i, \theta) & = \left \{ \begin{array}{l} 0, & |v_i| \leq \theta \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $w^{(t)}$：模型参数
• $g^{(t)}$：损失函数对模型参数梯度
• $T_0$：截断函数
• $\theta$：控制参数稀疏性

截断梯度法

截断梯度法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_1(w^{(t)} - \eta^{(t)} g^{(t)}, \lambda^{(t)} \eta^{(t)}, \theta) \\ T_1(v_i, \alpha, \theta) & = \left \{ \begin{array}{l} max(0, v_i - \alpha), & v_i \in [0, \theta] \\ min(0, v_1 + \alpha), & v_i \in [-\theta, 0] \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $\lambda, \theta$：控制参数$w$稀疏性

• 对简单截断的改进，避免在实际（OgD）中参数因训练不足过小 而被错误截断，造成特征丢失

  

Forward-Backward Spliting

FOBOS：前向后向切分，权重更新方式为proximal method如下

$$\begin{align*} w^{(t.5)} & = w^{(t)} - \eta^{(t)} g^{(t)} \\ w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t.5)}\| + \eta^{(t+0.5)} \Phi(w) \} \\ & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t+0.5)} \Phi(w) \} \end{align*}$$

L1-FOBOS

L1-FOBOS：即令$Phi(w)=\lambda |w|_1$，则根据可加性如下

$$\begin{align*} w^{(t+1)} & = \arg\min_w \sum_{i=1}^N (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) w_i^{(t+1)} = \arg\min_{w_i} (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) \end{align*}$$

• $V=[v_1, v_2, \cdots, v_N]:=w^{(t.5)}$：为方便
• $\tilde \lambda := \eta^{t.5} \lambda$：为方便
• $\eta^{t.5}$：学习率，常取 $\eta^{(t)} \in \theta(\frac 1 {\sqrt t})$

• 则对$w_i$求次梯度、分类讨论，解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} v_i - \tilde \lambda, & v_i > \tilde \lambda \\ 0, & |v_i| < \tilde \lambda \\ v_i + \tilde \lambda, & v_i < -\tilde \lambda \end{array} \right.$$

  • 可以理解为：到当前样本为止，维度权重小于阈值 $\eta^{(t.5)} \lambda$）时，认为该维度不够重要， 权重置为0

  • 可视为$k=1, \theta=\infty$的Tg算法

• 另外，显然有$w_i^{(t+1)} v_i \geq 0$

  $$\begin{align*} \frac 1 2 (w_i^{(t+1)} - v_i)^2 + \tilde \lambda |w_i^{(t+1)}| & = \frac 1 2((w_i^{(t+1)})^2 - 2 w_i^{(t+1)} v_i + v_i^2) + \tilde \lambda |w_i^{(t+1)}| \\ & \leq \frac 1 2 v_i^2 \end{align*}$$

  • 考虑$w_i^{(t+1)}$使得目标函数最小，带入$w=0$则得

Regularized Dual Averaging

RDA算法：正则对偶平均算法，权重更新方式为 包含[增广]正则项的最速下降

$$w^{(t+1)} = \arg\min_w {\frac 1 t \sum_{r=1}^t g^{(r)} w + \Phi(w) + \frac {\beta^{(t)}} t h(w)}$$

• 目标函数包括三个部分

  • $\frac 1 t \sum_{r=1}^t g^{(r)} w$：包含之前所有梯度 均值
  • $\Phi(w)$：正则项
  • $\frac {\beta^{(t)}} t h(w)$：额外正则项，严格凸，且 不影响稀疏性

• 相较于TG、FOBOS是从另一方面求解在线最优化，更有效地提升 特征权重稀疏性

L1 RDA

L1 RDA：令$\Phi(w) := \lambda |w|_1$， 再设$h(w) := |w|_2^2$，根据可加性则有

$$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 t \sum_{r=1}^t <g^{(t)}, w> + \lambda \|w\|_1 + \frac {\gamma} {2\sqrt t} \|w\|_2^2 \} \\ w_i^{(t+1)} & = \arg\min_{w_i} \{bar g_i^{(t)} w_i + \lambda |w_i| \frac {\gamma} {2 \sqrt t} w_i^2 \} \end{align*}$$

• $\lambda > 0, \gamma > 0$
• $\bar gi^{(t)} = \frac 1 t \sum{r=1}^t g_i^{(r)}$

• 对$w_i$求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} -\frac {\sqrt t} {\gamma} (\bar g^{(t)} - \lambda), & \bar g_i^{(t)} > \lambda \\ 0, & |\bar g_i^{(t)}| \leq \lambda \\ -\frac {\sqrt t} {\gamma} (\bar g^{(t)} + \lambda), & \bar g_i^{(t)} < -\lambda \\ \end{array} \right.$$
  • 可以理解为：某维度梯度累计均值绝对值$|bar g_i^{(t)}$ 小于阈值$\lambda$时，对应权重被置零、产生稀疏性

• 相较于L1-FOBOS的截断

  • 截断阈值为常数，更加激进、容易产生稀疏性
  • 截断判断对象为梯度累加均值，避免由于训练不足而产生 截断
  • 只需条件$\lambda$参数，容易权衡精度、稀疏性

Follow the Regularized Leader

FTRL：综合考虑L1-RDA、L1-FOBOS

L1-FOBOS、L1-RDA变换

• 将L1-FOBOS类似近端算法收敛证明中展开、去除无关项、放缩， 得到类似L1-RDA目标函数

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t)} \lambda \|w\|_1 \} \\ & = \arg\min_w \{ g^{(t)} w + \lambda \|w\|_1 + \frac 1 {2 \eta^{(t)}} \|w - w^{(t)}\|_2^2 \} \end{align*}$$

• 将L1-RDA目标函数整体整体放缩，得到

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} w + t \lambda \|w\|_1 + \frac 1 {2\eta^{(t)}} \|w - 0\|_2^2 \}$$

  • $g^{(1:t)} := \sum_{r=1}^t g^{(r)}$

• FTRL综合考虑L1-FOBOS、L1-RDA，得到目标函数

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} W + \lambda_1 \|w\|_1 + \frac {\lambda_2} 2 \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w - w^{(r)}\|_2^2 \}$$
  • 使用累加梯度更新，避免因训练不充分错误截断
  • 包含L1-FOBOS、L1-RDA全部正则化项

求解

• 将FTRL中最后一项拆分、去除无关项

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{(g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)})w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w^{(r)}\|_2^2 \} \\ & = \arg\min_w \{ z^{(t)} w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 \} \\ z^{(t)} &= g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)} \end{align*}$$

• 则同样根据可加性，对各分量求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} - \lambda_1 z_i), & z_i > \lambda_1 \\ 0, & |z_i^{(t)}| \leq \lambda_1 \\ \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} + \lambda_1 z_i), & z_i < -\lambda_1 \\ \end{array} \right.$$

• 其中学习率$\eta$为类似Adagrad优化器的学习率，但包括可学习 参数$\alpha, \beta$

  $$\eta_i^{(t)} = \frac {\alpha} {\beta + \sqrt{\sum_{r=1}^t (g_i^{(r)})^2}}$$

矩阵分解

• 矩阵加法分解：将矩阵分解为三角阵、对角阵之和

  • 常用于迭代求解线性方程组

• 矩阵乘法分解：将矩阵分解为三角镇、对角阵、正交阵之积

• 以下分解均在实数域上，扩展至复数域需同样将相应因子矩阵 扩充至复数域上定义

矩阵加法分解

Jacobi分解

Jacobi分解：将矩阵分解为对角阵、非对角阵

Gauss-Seidel分解

Gauss-Seidel分解：将矩阵分解为上、下三角矩阵

Successive Over Relaxation

SOR：逐次超松弛迭代法，分解为对角、上三角、上三角矩阵，同时 增加权重$w$调整分解后比例

• 利用内在等式应用的平衡性、不动点收敛理论可以快速迭代
  • $x$拆分到等式左右两侧，可以视为$y=x$和另外函数交点
  • 根据不动点收敛理论可以进行迭代求解

LU系列分解

LU Decomposition

LU分解：将方阵分解为lower triangualr matrix、 upper triangluar matrix

$$\begin{align*} A & = L U \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} l_{1,1} & 0 & \cdots & 0 \\ l_{2,1} & l_{2,2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & l_{m,m} \end{bmatrix} \begin{bmatrix} u_{1,1} & u_{1,2} & \cdots & u_{1,m} \\ 0 & u_{2,2} & \cdots & u_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{m,m} \end{bmatrix} \end{align*}$$

• $L$：下三角矩阵
• $U$：上三角矩阵

• 特别的可以要求某个矩阵对角线元素为1
• 几何意义：由单位阵出发，经过竖直、水平切变

特点

• LU分解实际上不需要额外存储空间，矩阵L、U可以合并存储

• LU分解可以快速求解线性方程组，可以视为高斯消元法的矩阵 形式

  • 得到矩阵LU分解后，对任意向量b，可使用已有LU分解 求解

    • L为消元过程中的行系数和对角线全为1的下三角矩阵 （负系数在矩阵中为正值）
    • U为消元结果上三角矩阵

  • 则解方程组$Ax=b$等价于$LUx=b$

    • 先求解$Ly=b$
    • 再求解$Ux=x$

LDU Decomposition

LDU分解：将矩阵分解为下三角、上三角、对角矩阵

$$\begin{align*} A & = L D U \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ l_{2,1} & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & 1 \end{bmatrix} \begin{bmatrix} u_{1,1} & 0 & \cdots & 0\\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{m,m} \end{bmatrix} \begin{bmatrix} 1 & u_{1,2}/u_{1,1} & \cdots & u_{1,m}/u_{1,1} \\ 0 & 1 & \cdots & u_{2,m}/u_{2,2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \end{align*}$$

• LU分解可以方便的得到LDU分解：提取对角阵、然后对应矩阵 元素等比缩放

PLU[Q] Decomposition

• PLU分解：将方阵分解为置换矩阵、下三角、上三角矩阵
• PLUQ分解：将方阵分解为置换矩阵、下三角、上三角、置换矩阵

• 考虑$P^{-1}A=LU$，交换$A$行即可作普通LU分解，PLUQ分解 类似
• PLU分解数值稳定性好、实用工具

LL/Cholesky Decomposition

LL分解：将对称阵分解为下三角、转置

$$\begin{align*} A & = L L^T \\ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,m} \end{bmatrix} & = \begin{bmatrix} l_{1,1} & 0 & \cdots & 0 \\ l_{2,1} & l_{2,2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ l_{m,1} & l_{m,2} & \cdots & l_{m,m} \end{bmatrix} \begin{bmatrix} l_{1,1} & l_{2,1} & \cdots & l_{m,1} \\ 0 & l_{2,2} & \cdots & l_{m,2} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & l_{m,m} \end{bmatrix} \end{align*}$$

• Cholesky分解常用于分解$A^TA$

  • 常用于相关分析，分解相关系数阵、协方差阵

• 相较于一般LU分解，Cholesky分解速度更快、数值稳定性更好

• 类似的有LDL分解，同时提取对角线元素即可

Singular Value Decomposition

SVD奇异值分解：将矩阵分解为正交矩阵、对角矩阵、正交矩阵

$$M_{m*n} = U_{m*r} \Sigma_{r*r} V_{n*r}^T$$

• 特征值分解在任意矩阵上推广：相应的特征值、特征向量 被称为奇异值、奇异向量
• 几何意义：由单位阵出发，经旋转、缩放、再旋转

特点

• $\Sigma$对角线元素为$M^T M$、$M M^T$的奇异值

  • 可视为在输入输出间进行标量的放缩控制
  • 同$U$、$V$的列向量相对应

• $U$的列向量称为左奇异向量

  • $M M^T$的特征向量
  • 与$M$正交的“输入”或“分析”基向量

• $V$的列向量成为右奇异向量

  • $M^T M$的特征向量
  • 与$M$正交的“输出”基向量

低阶近似

• 对$m * n$阶原始矩阵$M$

  • 设其秩为$K \leq min(m, n)$，奇异值为 $d_1 \geq d_2 \geq \cdots \geq d_K > 0$
  • 不失一般性可以设其均值为0

• 根据Eckart and Young的结果

  $$\forall r \leq K, \sum_{k=1}^r d_k u_k v_k^T = \arg\min_{\bar M \in M(r)} \| M - \bar M \|_F^2$$

  • $u_k, v_k$：$U, V$的第$k$列向量
  • $|M|_F$：矩阵的Frobenius范数

QR Decomposition

QR分解：将矩阵分解为正交矩阵、上三角矩阵

$$\begin{align*} A = Q R \end{align*}$$

• 几何意义：由单位阵出发，经旋转、切变

特点

• 正交矩阵逆为其转置，同样可以方便求解线性方程组

Proximal Operator

$$prox_{f}(x) = \arg\min_u (f(u) + \frac 1 2 \|u - x\|^2)$$

• $f(x)$：凸函数

• 由于$L_2$范数的强凸性，近端算子也强凸，解总是唯一存在
• 直观理解：寻找距离点$x$不太远、$f(u)$尽可能小的$u$
• 以下算法都是近端算法的特例
  • shrinkage thresholding algorithm
  • projected Landweber
  • projected gradient
  • alternating projections
  • alternating-directions method of multipliers
  • alternating split Bregman

• 近端算子连续可微

Moreau Envolop

$$\begin{align*} M_{\gamma, f}(x) & = prox_{\gamma, f}(x) \\ &= \arg\min_u (f(u) + \frac 1 {2\gamma} \|u - x\|^2) \\ \nabla prox_{\gamma, f}(x) & = \frac 1 {\gamma}(x - prox_f(x)) \end{align*}$$

• $\gamma > 0$：平衡参数，$\gamma = 1$即为普通近端算子

近端算子求解

• 对一般凸$f(x)$，通常使用次梯度进行优化，其近端算子解为 （即解变动方向$p-x$为负次梯度方向）

  $$p = prox_f(x) \Leftrightarrow x - p \in \partial f(p) \quad (\forall (x,p) \in R^N * R^N)$$

• 对光滑凸函数$f$，上述等式对其近端算子约简为 （即解变动方向$p-x$为负梯度方向）

  $$p = prox_f(x) \Leftrightarrow x-p = \bigtriangledown f(p)$$

性质

分离函数

$$\begin{align*} f(x_1, \cdots, x_m) & = \sum_{i=1}^m f_i(x_i) \\ prox_f(x_1, \cdots, x_m) & = [prox_{f_1}(x_1), \cdots, prox_{fm}(x_m)] \end{align*}$$

• 取$f(x) = |x|_1$，即可得即软阈值算子

  $$(prox_{\gamma, f}(x))_i = \left \{ \begin{array}{l} x_i - \gamma, & x_i \geq \gamma \\ 0, & |x_i| < \gamma \\ x_i + \gamma, & x_i \leq -\gamma \end{array} \right.$$

  • 参考坐标下降：近端算子中二次项中各分量无关，所以一轮 迭代即为最优解

仿射函数分解

$$\begin{align*} f(x) & = g(Ax + b) \\ prox_f(x) & = x + \frac 1 {\alpha} A^T (prox_{\alpha g}(Ax + b) - Ax - b) \end{align*}$$

• $A^T A = \alpha I, \alpha > 0$：线性变换
• $g$：良好闭凸函数

第一投影定理

• 取$f(x)$为示性函数、约束条件，即得到投影算子

$$\begin{align*} prox_{\gamma, f}(x) & = proj_C(x) = \arg\min_{u \in C} \|u - x\|_2^2 \\ f(x) & = I_C(x) = \left \{ \begin{array}{l} 0, x \in C \\ \infty, x \notin C \end{array} \right. \end{align*}$$

第二临近定理

• $f$为良好闭凸函数，则以下三条等价

  • $y = prox_f(x)$
  • $x - y \in \partial f(y)$：由近端算子定义即得
  • $\forall z, \leq f(z) - f(y)$

Moreau Decomposition

$$\begin{align*} prox_f(x) + prox_{f^{*}}(x) & = x \\ prox_{\lambda f}(x) + \lambda prox_{f^{*}/lambda}(x/\lambda) & = x, \lambda > 0 \end{align*}$$

最小值

$$\begin{align*} \min_x prox_f(x) & = \min_x f(x) \\ \arg\min_x prox_f(x) & = \arg\min_x f(x) \end{align*}$$

证明

$$\begin{align*} f(x_f) & = f(x_f) + \frac 1 2 \|x_f - x_f\|_2^2 \\ & \geq \min_u {f(u) + \frac 1 2 \|u - x_f\|_2^2} \\ & = prox_f(x_f) \\ & \geq prox_f(x_p) \\ & = f(x_p) + \frac 1 2 \|x_p - x_f\|_2^2 \\ & \geq f(x_p) \geq f(x_f) \end{align*}$$

• $x_f = \arg\min_x f(x)$
• $x_p = \arg\min_x prox_f(x)$

例

• $f(x)=c$：$prox_{f}(x) = x$

Projection Operator

投影算子

$$\begin{align*} proj_C(x) & = \arg\min_{y \in C} \|y - x\|^2 \\ & = \arg\min_{y \in R^N} l_C(x) + \frac 1 2 \|y-x\|^2 \end{align*}$$

• 点$x$在凸集$C$上的投影：$X$上距离$x$的欧式距离最近的点

Alternating Projection Method

POCS/project onto convex sets method：用于解同时满足多个 凸约束的算法

• $f_i$作为非空闭凸集$C_i$示性函数，表示一个约束，则整个 问题约简为convex feasibility problem

• 只需要找到位于所有$C_i$交集的解即可

• 每次迭代

  $$x^{(k+1)} = P_{C_1}P_{C_2} \cdots P_{C_n}x_k$$

• 在其他问题中投影算子不再适合，需要更一般的算子，在其他 各种同样的凸投影算子中，近端算子最合适

Proximal Gradient Method

近端算法：分两步分别优化可微凸$F(x)$、凸$R(x)$，近似优化目标 函数整体，不断迭代直至收敛

$$\min_{x \in \mathcal{H}}F(x) + R(x)$$

• $F(x)$：可微、凸函数
• $\nabla F(x)$：Lipschitz continous、利普希茨常数为$L$
• $R(x)$：下半连续凸函函数，可能不光滑
• $\mathcal{H}$：目标函数定义域集合，如：希尔伯特空间

• gredient step：从$x^{(k)}$处沿$F(x)$负梯度方向微小移动 达到$x^{(k.5)}$

  $$x^{(k.5)} = x^{(k)} - \gamma \nabla F(x^{(k)})$$

• proximal operator step：在$x^{(k.5)}$处应用$R(x)$近端 算子，即寻找$x^{(k.5)}$附近且使得$R(x)$较小点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k.5)})$$

目标函数推导

$$\begin{align*} prox_{\gamma R}(x - \gamma \nabla F(x)) & = \arg\min_u (R(u) + \frac 1 {2\gamma} \|u - x + \gamma \nabla F(x)\|_2^2) \\ & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + F(x) + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u - x\|_2^2) \\ & \approx \arg\min_u(R(u) + F(u)) \end{align*}$$

• $\frac {\gamma} 2 |\nabla F(x)|_2^2, F(x)$：与$u$无关 ，相互替换不影响极值
• $0 < \gamma \leq \frac 1 L$：保证最后反向泰勒展开成立

• 则$prox_{\gamma R}(x-\gamma \nabla F(x))$解即为 “原问题最优解”（若泰勒展开完全拟合$F(x)$）

  • 近端算法中距离微调项部分可加法分离
  • 若$R(x)$部分也可分离，则整个目标函数可以分离，可以 拆分为多个一元函数分别求极值

• 考虑泰勒展开是局部性质，$u$作为极小值点只能保证在$x$附近 领域成立，可将近端算子解作为下个迭代点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k)} - \gamma \nabla F(x^{(k)}))$$

• 迭代终止条件即

  $$\hat x = prox_{\gamma R}(\hat x - \gamma \nabla F(\hat x))$$

二阶近似证明

$$\begin{align*} F(u) & = F(x) + \nabla F(x)^T (u - x) + \frac 1 2 (u - x)^T \nabla^2 F(\zeta)(u - x) \\ & \geq F(x) + \nabla F(x)^T (u - x) \\ & \leq F(x) + \nabla F(x)^T (u - x) + \frac L 2 \|u-x\|^2 \end{align*}$$

• $\nabla^2 F(\zeta)$：凸函数二阶导正定
• $|\nabla F(u) - \nabla F(x)|_2 \leq L |u-x|_2$： $\nabla F(x)$利普希茨连续性质

参数确定

• $L$已知时，可直接确定$\gamma \in (0, \frac 1 L]$，

• 否则可线性迭代搜索$\gamma := \beta \gamma,\beta < 1$， 直至

  $$F(x - PG_{\gamma R}(x)) \leq F(x) - \nabla F(x) PG_{\gamma R}(x) + \frac 1 2 \|PG_{\gamma R}(x)\|_2^2$$

  • $PG{\gamma R}(x)=x-prox{\gamma R}(x-\gamma \nabla F(x))$
  • 直接根据下述利普希茨条件须求Hasse矩阵，计算量较大

反向推导

• 对$F(x)+R(x)$在$x_0$附近作泰勒展开

  $$F(u)+R(u) \leq F(x) + \nabla F(x)^T (u - x) + \frac 1 {2\gamma} \|u - x\|_2^2 + R(x)$$

  • $\lambda \in (0, \frac 1 L]$
  • $L$：$F(x)$利普希茨常数
  • $\leq$：由Lipschitz连续可取

  • 则不等式右边就是$F(x)+R(x)$的一个上界，可以对将对其 求极小化转化对此上界求极小

• 考虑对极小化目标添加常数项不影响极值，对不等式右侧添加 与$u$无关项$\frac \gamma 2 |\nabla F(x)|_2^2$、剔除 剔除$F(x)$凑出近端算子

  $$\begin{align*} prox_{\gamma R} & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + \|u - x + \frac 1 {2\gamma} \nabla F(x)\|_2^2) \end{align*}$$

近端算法推广

问题推广

• 求解non-differentiable凸优化问题的通用投影形式

$$\min_{x \in R^N} \sum_{i=1}^N f_i(x)$$

• $f_i(x)$：凸函数，不一定处处可微

• 目标函数中包含不处处连续可微函数，整个目标函数不光滑

  • 无法使用传统的光滑优化手段，如：最速下降、共轭梯度
  • 极小化条件为$0 \in \partial(F+R)(x)$

• 分开考虑各个函数，对非光滑函数使用近端算子处理

算子推广

• 考虑使用Bregman Divergence替代近端算子中欧式距离

$$prox_{\gamma, f}(x) = \arg\min_u (f(u) + \mu(u) - \mu(x) + <\nabla \mu(x), u - x>)$$

• 取$\mu(x) = \frac 1 2 |x|_2^2$时，即为普通近端算子

坐标下降

坐标下降法：在当前点处延一个坐标方向进行一维搜索以求得函数 的局部极小值

• 非梯度优化算法，但能提供超过一阶的信息
  • SMO算法就是两块贪心坐标下降

说明

• 优化方向从算法一开始就固定，如：选择线性空间中一组基作为 搜索方向

• 循环极小化各坐标方向上目标函数值，即：若$x^k$给定，则

  $$x_i^{(k+1)} = \arg\min_{x \in R} f(x_1^{k+1}, \cdots, x_{i-1}^{k+1}, x, x_{i+1}^{k}, \cdots, x_n^k)$$

  • $k$：第k轮迭代
  • $i$：某轮迭代中更新第i个方向

• 对初始值为$X_0$得到迭代序列$X_1, \cdots, X_n$，对精确 一维搜索类似最速下降有

  $$F(X_0) \geq F(X_1) \geq \cdots \geq F(x_n)$$

• 若某轮迭代中目标函数无法被有优化，说明已经达到驻点

Adaptive Coordinate Descent

自适应坐标下降：变换坐标系使得在考虑目标函数的情况下，新坐标 间尽可能不相关

• 对非可拆分函数（可加？），算法可能无法在较小迭代步数中 求得最优解

  • 可采用适当坐标系加速收敛，如：主成分分析进行自适应 编码
  • 性能远超过传统坐标下降算法，甚至可以达到梯度下降的 性能

  

• 自适应坐标下降具有以下特性，和最先进的进化算法相当

  • 缩放不变性
  • 旋转不变性

Block Coordinate Descent

块坐标下降：在当前点处在一个超平面内方向进行搜索以求得函数 的局部极小值

• 即同时更新一组坐标的坐标下降

例

Lasso求解

• 目标函数

  $$L(x) = RSS(x) + \lambda \|x\|_1 = \frac 1 2 (Ax - y)^T(Ax - y) + \lambda \|x\|_1$$

• RSS求导

  $$\begin{align*} \frac {\partial RSS} {\partial x} & = (Ax - y)^T A \\ (\frac {\partial RSS} {\partial x})_i & = (Ax - y)^T A_{:i} \\ & = (Ax_{i0} - y)^T A_{:i} + x_i A_{:i}^T A_{:i} \\ & = z_i + \rho_i x_i \end{align*}$$

  • $(\frac {\partial RSS} {\partial x})_i$：RSS对$x$ 导数第$i$分量，即对$x_i$偏导
  • $A_{:i}$：$A$第$i$列
  • $x_{i0}$：$x$第$i$分量置零
  • $zi = (Ax{i0} - y)^T A_{:i}$
  • $\rhoi = A{:i}^T A_{:i}$

• 则$x_i$整体次梯度为

  $$\frac {\partial L} {\partial x_i} = z_i + \rho_i x_i + \left \{ \begin{array}{l} -\lambda, & x_i < 0 \\ [-\lambda, \lambda], & x_i = 0 \\ \lambda, & x_i > 0 \end{array} \right.$$

• 分类讨论：令整体次梯度为0求解$x_i$、回带确定参数条件

  $$x_i = \left \{ \begin{array}{l} \frac {-z_i + \lambda} {\rho_i}, & z_i > \lambda \\ 0 , & -\lambda < z_i < \lambda \\ \frac {-z_i - \lambda} {\rho_i}, & z_i < -\lambda \end{array} \right.$$

  • 此算子也称soft threshholding

  

向量

• 线性组合
• 向量空间
• 空间的基：向量空间的一组基是张成该空间的一个线性无关向量集
• 线性相关

向量点积

• 向量点积性质

  • 向量的数乘等比例影响点积，则可为每个向量找到共线单位向量满足 $u \cdot u=1$

    

  • 点积等同于向量 $b$ 左乘矩阵 $a^T$，即把向量 $b$ 压缩（线性变换）至向量 $a$ 方向上

    

• 点积 $a \cdot b$ 与投影关系（假设向量 $a$ 为单位向量）

  • 投影，即将向量 $b$ 线性变换 至 $a$ 方向上的标量

    • 则投影可以用 $1 * n$ 矩阵表示
    • 投影代表的矩阵则可通过利用基向量的变换结果求解

    

  • 向量 $a$ 本身作为单位向量

    • 坐标轴上单位向量与 $a$ 的内积即为 $a$ 该方向分量，也即 $a$ 在该轴上投影
    • 由对称性显然，坐标轴在 $a$ 方向投影等于 $a$ 在轴方向投影
    • 则投影到向量 $a$ 代表的线性变换矩阵即为 $a^T$

    

  • 扩展到一般情况

    • 考虑标量乘法对点积影响，坐标轴上向量与任意向量 $a$ 内积等价于投影
    • 投影是线性变换，则对空间一组基的变换可以推导到空间中任意向量 $b$

• 高维空间到标量的线性变换与空间中一个向量对应，即应用线性变换等价于同该向量点积

点积用途

• 向量证明基本都是都转换到点积上
  • 正定：行列式恒>0
  • 下降方向：内积<0
  • 方向（趋于）垂直：内积趋于0

求和、积分、点积、卷积

• 卷积：累计中各点的值变为需累计的值，即二次累计

向量叉积

• 向量叉积意义

  • 向量叉积即寻找向量（到标量的线性变换），满足与其点积结果为张成的体积

    

  • 考虑点积性质，则向量叉积的方向与向量构成超平面垂直、模为超平面大小

    

一些规定

• 正交方向：向量空间 $R^n$ 中 $k, k \leq n$ 个向量 $q^{(1)}, \cdots, q^{(k)}$ 两两正交，则称其为 $k$ 个正交方向，若满足所有向量非 0，则称为 $k$ 个非 0 正交方向

• 向量左右

  • 左侧：向量逆时针旋转 $[0, \pi]$ 内
  • 右侧：反左侧

矩阵

• 矩阵（乘法）：对向量的变换

  • 对 $m * n$ 矩阵，即将 $n$ 维空间映射至 $m$ 维空间

• 矩阵相关概念

  • （矩阵）秩：空间维数
  • （矩阵）零空间/核：变换（左乘矩阵）后落在原点的向量的集合

  

• 线性变换：保持空间中坐标轴仍为直线且原点保持不变的变换
• 此处若无特殊说明，向量均以列向量作为基础

特殊矩阵

• 其中正交矩阵、三角阵、对角阵也被成为因子矩阵

• Orthogonal Matrix 正交矩阵：和其转置乘积为单位阵的方阵

  • 左乘正交矩阵几何意义：等价于旋转

    

  • 酉矩阵/幺正矩阵：$n$ 个列向量是 $U$ 空间标准正交基的 $n$ 阶复方阵，是正交矩阵往复数域上的推广

• Diagonal Matrix 对角阵：仅对角线非0的矩阵

  • 左乘对角阵矩阵几何意义：等价于对坐标轴缩放

    

• Triangular Matrix 上/下三角矩阵：左下/右上角全为0的方阵

  • 三角阵是高斯消元法的中间产物，方便进行化简、逐层迭代求解线性方程组

  • 左乘上三角阵几何意义：等价于进行右上切变（水平斜拉）

    

  • 左乘下三角阵几何意义：等价于进行左下切变（竖直斜拉）

    

• Transposation Matrix 置换矩阵：系数只由 0、1 组成，每行、列恰好有一个 1 的方阵

矩阵常用公式

Sherman-Morrison 公式

• 设A是n阶可逆矩阵，$u, v$均为n为向量，若 $1 + v^T A^{-1} u \neq 0$，则扰动后矩阵$A + u v^T$可逆 $$(A + u v^T)^{-1} = A^{-1} - \frac {A^{-1} u v^T A^{-1}} {1 + v^T A^{-1} u}$$

矩阵乘法

• 矩阵乘法

  • 向量左乘矩阵：即是对向量进行变换

    

  • 矩阵乘积：复合变换

    

• 矩阵乘法应按照从右往左阅读，右侧矩阵为输入、左侧矩阵为变换（向量默认为列向量时）

Affline Transformation

仿射变换：对向量空间进行线性变换、平移得到另一个向量空间

$$\begin{align*} y &= Ax + b \\ y &= (A|b^T) \begin {bmatrix} x \\ 1 \end {bmatrix} \end{align*}$$

• $y \in R^n, x \in R^n$
• $A \in R^{n * n}$：可视为产生旋转、放缩
• $b \in R^n$：可视为产生平移

• 仿射变换可以理解为：放缩、旋转、平移

• 从仿射变换的角度，对向量空间进行仿射变换

  • $n+1$ 对变换前、变换后向量坐标即可以求解仿射变换的全部参数
  • 变换后的向量之间仍然保留某种相关性，所以 $n+1$ 对向量坐标可以完全确定仿射变换

• 从仿射变换几何含义，将向量空间中向量统一变换

  • $n+1$ 个不共线 $n$ 维向量即唯一确定n维空间
  • 若所有向量变换均遵循同一“线性”变换规则，即进行相同放缩、旋转、平移，则这样的变换可以使用仿射变换表示

• 说明

  • $n$ 变换前、变换后向量坐标可以求解 $A$（不考虑 $b$），但第 $n+1$ 对向量坐标未必满足 $A$ 变换
  • 若 $n+2$ 对向量坐标不满足 $(A|b)$ 的解，则表示不是进行仿射变换

Perspective Transformation

透视变换：将向量空间映射到更高维度，再降维到另一向量空间

$$\begin{align*} y &= P \begin {bmatrix} x \\ 1 \end {bmatrix} \\ y &= \begin {bmatrix} A & b \\ c & p_{n+1,n+1} \end {bmatrix} \begin {bmatrix} x \\ 1 \end {bmatrix} \end{align*}$$

• $P \in R^{(n+1) (n+1)}, A \in R^{n n}$
• $x \in R^n, y \in R^{n+1}$：这里默认$x$第$n+1$维为1
• $c$：可视为产生透视，若其为0向量，则退化为仿射变换
• $p_{n+1,n+1}$：可视为决定透视放缩，所以若是已确定新向量空间的“位置”，此参数无效，即 $n+2$ 对向量坐标即可求解变换

• 透视变换虽然是向量空间变换至另一向量空间，但仍然存在一个透视“灭点”，作为所有透视线的交点

  • 对平面成像而言，“灭点”是成像平面、视角决定

• 变换后 $y$ 维数增加，一般会再次投影、缩放回原维度空间，如原向量空间 $(R^n,1)$

• 仿射变换可以视为是新的向量空间和原始空间“平行”的透视变换特例

变换矩阵求解

$$\begin{align*} \begin {bmatrix} P & b \\ c & p_{n+1,n+1} \end {bmatrix} \begin {bmatrix} x \\ 1 \end {bmatrix} &= \gamma \begin {bmatrix} x^{'} \\ 1 \end {bmatrix} \\ \Rightarrow Px + b &= \gamma x^{'} \\ c^Tx + p_{n+1,n+1} &= \gamma \\ \Rightarrow Px + b &= (c^Tx + p_{n+1,n+1}) x^{'} \end{align*}$$

• 考虑变换后再次缩放回更低维 $(R^n,1)$ 向量空间
• $\gamma$：变换后向量缩放比例

• 可解性
  • 共 $n+2$ 对变换前、后向量坐标，即 $n*(n+2)$ 组方程
  • 对每对向量，其中 $n$ 组方程如上可以看出是齐次方程组，不包含常数项
  • 则对 $P \in R^{(n+1) * (n+1)}$ 中除 $p_{n+1,n+1}$ 其他项均可被其比例表示（不含常数项）

• 当然 $p_{n+1,n+1}$ 可以置 1 参加运算，不影响结果

Determinant

• 矩阵行列式几何意义：线性变换对空间的拉伸比例

  • 行列式绝对值：拉伸的比例的绝对大小
    • 行列式为 0 时则表示空间降维
    • 则显然应有 $det(M_1 * M_2) = det(M_1) det(M_2)$
  • 行列式正负号：拉伸的方向

  

• 矩阵行列式的用途

  • 行列式为 0 意味着矩阵表示降维变换，则对应线性方程组仅在方程组右侧在矩阵张成空间内，即扩展矩阵秩不增时有解

特别的

• $2 * 2$ 矩阵 $\begin{vmatrix} a & b \ c & d \end{vmatrix} = ad - bc$

  • $a, d$ 分别表示 $(1,0)$、$(0,1)$ 正向放缩比例
  • 而 $b, c$ 则相应的为逆向放缩比例

  

• 二维三点：行列式绝对值为三点构成三角形面积两倍

  $$\begin{vmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ x_3 & y_3 & 1 \\ \end{vmatrix} = x_1y_2 + x_3y_1 + x_2y_3 - x_3y_2 - x_2y_1 - x_1y_3$$

  • $q_3$ 位于 $\overrightarrow{q_1q_2}$ 左侧：行列式大于0
  • $q_3q_1q_2$ 共线：行列式值为 0

• 三维三点：行列式为三个向量张成的平行六面体体积

Eigen Value、Eigen Vector

• 矩阵（变换）特征向量、特征值几何意义

  • 特征向量：在线性变换后仍然在自身生成空间中，即保持方向不变，仅是模变化的向量
  • 特征值：对应特征向量模变化的比例

• 特殊变换中的特征向量、特征值情况

  • 旋转变换：特征值为 $\pm i$，没有特征向量，即特征值为复数表示某种旋转
  • 剪切变换（$\begin{vmatrix} A^{‘} & 0 \ 0 & 1 \end{vmatrix}$$：必然有特征值为 1，且对应特征向量在坐标轴上
  • 伸缩变换（$\lambda E$）：所有向量都是特征向量

• 矩阵对角化

  • 矩阵对角化：即寻找一组基，使得线性变换对该组基向量仅引起伸缩变换
  • 定理：当且仅当 $n$ 阶矩阵 $A$ 有 $n$ 个线性无关的特征向量时，其可以对角化
    • 即变换后有 $n$ 个线性无关向量在自身生成空间中
    • 也即矩阵对应变换为线性变换

线性方程组

Gaussian Elimination

高斯消元法：初等变换n个线性方程组为等价方程组，新方程组系数矩阵为上三角矩阵

• 三角系数矩阵可以方便的递推求解
• 初等变换可将系数矩阵变换为上三角矩阵，而不影响方程解

参考资料

• https://www.bilibili.com/video/av6731067/
• https://charlesliuyx.github.io/2017/10/06/%E3%80%90%E7%9B%B4%E8%A7%82%E8%AF%A6%E8%A7%A3%E3%80%91%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0%E7%9A%84%E6%9C%AC%E8%B4%A8/