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}}$$

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

  

距离

• 距离可认为是两个对象 $x,y$ 之间的 相似程度
  • 距离和相似度是互补的
  • 可以根据处理问题的情况，自定义距离

Bregman Divergence

$$D(x, y) = \Phi(x) - \Phi(y) - <\nabla \Phi(y), (x - y)>$$

• $Phi(x)$：凸函数

• 布雷格曼散度：穷尽所有关于“正常距离”的定义

  • 给定 $R^n * R^n \rightarrow R$ 上的正常距离 $D(x,y)$，一定可以表示成布雷格曼散度形式
  • 直观上：$x$处函数、函数过$y$点切线（线性近似）之差
    • 可以视为是损失、失真函数：$x$由$y$失真、近似、添加噪声得到

• 特点

  • 非对称：$D(x, y) = D(y, x)$
  • 不满足三角不等式：$D(x, z) \leq D(x, y) + D(y, z)$
  • 对凸集作 Bregman Projection 唯一
    • 即寻找凸集中与给定点Bregman散度最小点
    • 一般的投影指欧式距离最小

• 正常距离：对满足任意概率分布的点，点平均值点（期望点）应该是空间中距离所有点平均距离最小的点
• 布雷格曼散度对一般概率分布均成立，而其本身限定由凸函数生成

  • 和 Jensen 不等式有关？凸函数隐含部分对期望的度量

• http://www.jmlr.org/papers/volume6/banerjee05b/banerjee05b.pdf

单点距离

Minkowski Distance

闵科夫斯基距离：向量空间 $\mathcal{L_p}$ 范数

$$d_{12} = \sqrt [1/p] {\sum_{k=1}^n |x_{1,k} - x_{2,k}|^p}$$

• 表示一组距离族

  • $p=1$：Manhattan Distance，曼哈顿距离
  • $p=2$：Euclidean Distance，欧式距离
  • $p \rightarrow \infty$：Chebychev Distance，切比雪夫距离

• 闵氏距离缺陷

  • 将各个分量量纲视作相同
  • 未考虑各个分量的分布

Mahalanobis Distance

马氏距离：表示数据的协方差距离

$$d_{12} = \sqrt {({x_1-\mu}^T) \Sigma^{-1} (x_2-\mu)}$$

• $\Sigma$：总体协方差矩阵

• 优点
  • 马氏距离和原始数据量纲无关
  • 考虑变量相关性
• 缺点
  • 需要知道总体协方差矩阵，使用样本估计效果不好

LW Distance

兰氏距离：Lance and Williams Distance，堪培拉距离

$$d_{12} = \sum^{n}_{k=1} \frac {|x_{1,k} - x_{2,k}|} {|x_{1,k} + x_{2,k}|}$$

• 特点
  • 对接近0的值非常敏感
  • 对量纲不敏感
  • 未考虑变量直接相关性，认为变量之间相互独立

Hamming Distance

汉明距离：差别

$$diff = \frac 1 p \sum_{i=1}^p (v^{(1)}_i - v^{(2)}_i)^k$$

• $v_i \in {0, 1}$：虚拟变量
• $p$：虚拟变量数量

• 可以衡量定性变量之间的距离

Embedding

• 找到所有点、所有维度坐标值中最大值 $C$
• 对每个点 $P=(x_1, x_2, \cdots, x_d)$
  • 将每维 $x_i$ 转换为长度为 $C$ 的 0、1 序列
  • 其中前 $x_i$ 个值为 1，之后为 0
• 将 $d$ 个长度为 $C$ 的序列连接，形成长度为 $d * C$ 的序列

• 以上汉明距离空间嵌入对曼哈顿距离是保距的

Jaccard 系数

Jaccard 系数：度量两个集合的相似度，值越大相似度越高

$$sim = \frac {\|S_1 \hat S_2\|} {\|S_1 \cup S_2\|}$$

• $S_1, S_2$：待度量相似度的两个集合

Consine Similarity

余弦相似度

$$similarity = cos(\theta) = \frac {x_1 x_2} {\|x_1\|\|x_2\|}$$

• $x_1, x_2$：向量

欧式距离

点到平面

• $T={(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)}$：样本点集
• $wx + b = 0$：超平面

Functional Margin 函数间隔

$$\hat{\gamma_i} = y_i(wx_i + b)$$

• 函数间隔可以表示分类的正确性、确信度

  • 正值表示正确
  • 间隔越大确信度越高

• 点集与超平面的函数间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

• 超平面参数 $w, b$ 成比例改变时，平面未变化，但是函数间隔成比例变化

Geometric Margin 几何间隔

$$\begin{align*} \gamma_i & = \frac {y_i} {\|w\|} (wx_i + b) \\ & = \frac {\hat \gamma_i} {\|w\|} \end{align*}$$

• 几何间隔一般是样本点到超平面的 signed distance

  • 点正确分类时，几何间隔就是点到直线的距离

• 几何间隔相当于使用 $|w|$ 对函数间隔作规范化

  • $|w|=1$ 时，两者相等
  • 几何间隔对确定超平面、样本点是确定的，不会因为超平面表示形式改变而改变

• 点集与超平面的几何间隔取点间隔最小值 $\hat{T} = \min_{i=1,2,\cdots,n} \hat{\gamma_i}$

Levenshtein/Edit Distance

（字符串）编辑距离：两个字符串转换需要进行插入、删除、替换操作的次数

$$lev_{A,B}(i, j) = \left \{ \begin{array}{l} i, & j = 0 \\ j, & i = 0 \\ min \left \{ \begin{array}{l} lev_{A,B}(i,j-1) + 1 \\ lev_{A,B}(i-1,j) + 1 \\ lev_{A,B}(i-1, j-1) + 1 \end{array} \right. & A[i] != B[j] \\ min \left \{ \begin{array}{l} lev_{A,B}(i,j-1) + 1 \\ lev_{A,B}(i-1,j) + 1 \\ lev_{A,B}(i-1, j-1) \end{array} \right. & A[i] = B[j] \\ \end{array} \right.$$

组间距离

Single Linkage

Average Linkage

Complete Linkage

Legendre Transformation

勒让德变换：用 $f^{ * }(p)$ 表示凸、可导函数 $f(x)$ 的变换，其中 $p$ 是 $f(x)$ 导数

$$f^{*}(p) = p^T x - f(x)|_{\frac {d(p^T x - f(x))} {dx} = 0}$$

• $x$：参数，满足 $\frac {d(p^T x - f(x))} {dx} = 0$，随 $p$ 取值改变
• 可导：有导数；凸：导数唯一

• 勒让德变换是实变量的实值凸函数的对合变换
  • 把定义在线性空间上的函数变换至对偶空间的函数
  • 是点、（切）线之间对偶关系的应用
    • 严格凸函数中，切线、导数一一对应
    • 函数关系 $f(x)$ 可使用 $(x, y=f(x))$ 点集表示，也可用切线集合表示

• involution 对合：对合函数 $f$ 的反函数的为自身，即 $f(f(x))=x$；对合线性变换 $V$ 满足 $V^2 = E$

Legendre 变换理解（按 Fenchel 共轭）

• $f^{*}(p)$：可理解为斜率为 $p$、同 $f(x)$ 有交点 $x_0$ 的直线在零点处值（截距）和 $f(x_0)$ 的最大差

  

• $x$：可以理解为函数 $f(x)$ 上距离给定斜率为 $p$、过原点的直线 $f(x)=px$ 竖直距离最大的点

  

  • 类似一个端点为 $0$ 的 Bregman 散度

• Legendre 变换为对合变换，进行两次的变换得到原函数

  

  $$\begin{align*} f^{**}(x) & = \sup_{p \in dom(f^{*})} [x^T p - f^{*}(p)] \\ & = \sup_{u \in dom(f)}[x^T \nabla f(u) - \nabla f(u)^T u + f(u)] \\ & = \sup_{u \in dom(f)}[f(u) + \nabla f(u)^T (x-u)] \\ & = f(x) \end{align*}$$

• 若视凸函数 $f(x)$ 视为积分，则其共轭 $f^{ * }(x)$ 为对另一轴积分，二者导函数互为反函数

  $$f(x) + f^{*}(p) = xp, p = \frac {df(x)} {dx}$$

• 以上性质均按 Fenchel 共轭，但要求 $f(x)$ 为凸、可导函数，故等价于 Legendre 变换

Legendre 变换最大值式定义

$$\begin{align*} L(p, x) &= px - f(x) \\ \frac {\partial (px - f(x))} {\partial x} &= p - \frac {df(x)} {dx} = 0 \\ \Rightarrow & p = \frac {df(x)} {dx} \end{align*}$$

• Legendre 变换可以视为寻找 $px-f(x)$ 最大值（如前述）
  • $f(x)$ 为凸函数，则 $p=\frac {df(x)} {dx}$ 是最大值点
  • 则将 $f(x)$ 导函数的反函数 $x=f^{-1}(p)$ 带入即可

Legendre 变换数学性质

• 标度性质

  $$\begin{align*} f(x) & = a g(x) \rightarrow f^{*}(p) = a g^{*}(\frac p a) \\ f(x) & = g(ax) \rightarrow f^{*}(p) = g^{*}(\frac p a) \end{align*}$$

  由此，$r$次齐次函数的勒让德变换是$s$次齐次函数，满足

  $$\frac 1 r + \frac 1 s = s$$

• 平移性质

  $$\begin{align*} f(x) & = g(x) + b \rightarrow f^{*}(p) = g^{*}(p) - b f(x) & = g(x+y) \rightarrow f*^{*}(p) = g^{*}(p) - py \end{align*}$$

• 反演性质

  $$f(x) = g^{-1}(x) \rightarrow f^{*}(p) = -p g^{*}(\frac 1 p)$$

• 线性变换性质

  $$(Af)^{*} = f^{*}A^{*}$$

  • $f$：$R^n$上的凸函数
  • $A$：$R^n \rightarrow R^m$的线性变换
  • $A^{}: <Ax, y^{}> = $：$A$伴随算子

Fenchel Conjugate / 凸共轭

$$f^{*}(p) = \sup_{x \in R}{p^Tx - f(x)}$$

• Fenchel 共轭是对 Legendre 变换的扩展，不再局限于凸、可导函数
  • Fenchel 共轭可类似 Legendre 理解，但是适用范围更广
  • 对凸函数 Fenchel 共轭的共轭即为原函数，对非凸函数 Fenchel 共轭得到原函数凸包
  • 用罗尔中值定理描述极值、导数关系：兼容 Legendre 变换中导数支撑面

• 非凸函数线性外包络是凸函数

Fenchel-Young不等式

$$f(x) + f^{*}(p) \geq <p, x>$$

• 证明

  $$\begin{align*} f(x) + f^{*}(p) & = f(x) + \sup_{x \in dom(f)} {(x^T p - f(x))} \\ & \geq f(x) + x^T p - f(x) = x^T p \end{align*}$$

• 按积分理解，仅$p$为$x$共轭时取等号

  

Fenchel Conjugate 推导 Lagrange Duality

• 原问题 Prime

  $$\begin{align*} & \min {f(x)} \\ s.t. & g(x) \leq 0 \\ \end{align*}$$

• 约束条件 $g(x) \leq 0$ 扰动函数化、求 Fenchel 共轭

  $$\begin{align*} p(u) & = \inf_{x \in X, g(x) \leq u} f(x) \\ p^{*}(y) & = \sup_{y \in R^r} \{u^T y - p(u)\} \end{align*}$$

• 记 $\lambda = -y$，并将 $y=-\lambda$ 带入 $-p^{*}(y)$ 中得到

  $$\begin{align*} -p^{*}(y) & = \inf_{u \in R^r} \{p(u) - u^T y\} \\ d(\lambda) & = \inf_{u \in R^r} \{p(u) + u^T \lambda\} \\ & = \inf_{u \in R^r} \{\inf_{x \in X, g(x) \leq u} f(x) + \lambda^T u\} \end{align*}$$

  • $\lambda = -y$

• 将 $\inf_{x \in X, g(x) \leq u}$ 外提，并考虑到约束 $g(x) \leq u$（即 $u \geq g(x)$），则

  $$\begin{align*} \lambda \geq 0 & \Rightarrow \lambda^T g(x) \leq \lambda u \\ d(\lambda) & = \left \{ \begin{array}{l} \inf_{x \in X} \{f(x) + \lambda^T g(x)\}, & \lambda \geq 0 \\ -\infty, & otherwise \end{array} \right. \end{align*}$$

• 考虑 Fenchel 不等式

  $$\begin{align*} p(u) + p^{*}(-y) & \geq u^T (-y) \\ p(0) + p^{*}(-y) & \geq 0 \\ p(0) & \geq -p^{*}(-y) \\ p(0) & \geq d(\lambda) \end{align*}$$

• 则可得 Lagrange 对偶 Prime、Dual 最优关系

  $$L(x, \lambda) = f(x) + \lambda^T g(x), \lambda \geq 0 \\ D^{*} := \max_{\lambda \geq 0} \min_x L(x, \lambda) \leq \min_x \max_{\lambda \geq 0} L(x, \lambda) =: P^{*}$$

  

Lagrange Duality 推导 Fenchel 对偶

• Fenchel 对偶可以视为 Lagrange 对偶的应用

• 原问题、等价问题

  $$\begin{align*} & \min_x & f(x) - g(x) \\ \Leftrightarrow & \min_{x,z} & f(x) - g(z) \\ & s.t. & x = z \end{align*}$$

• 对上式取 Lagrange 对偶 $L(u)$、等价得到

  $$\begin{align*} L(u) &= \min_{x,z} f(x) - g(z) + u^T(z-x) \\ &= -(f^{*}(u) - g^{(-u)}) \end{align*}$$

• Fenchel 对偶：寻找截距差值最大的平行切线

Fourier Transformation

（连续）傅里叶变换：将时域映射到频域的变换

$$F(\xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi ix \xi} dx$$

• $x$：自变量，多表示时间
• $F(\xi)$：频率

傅里叶变换理解

• 将自变量 $x$ 线性映射为极坐标系中角度，调整线性映射的比例（即频率），即可绘制出不同的曲线

  

• 计算不同频率下曲线围成的图像的质心（径向）坐标

  • 质心的角度坐标只需原函数沿 $x$ 轴平移即可改变
  • 若原图像不关于 $x$ 轴对称，则质心在频率 0 点处有较大值

  

• 据以上：周期函数映射在极坐标系下图像，其质心位置在对应频率下取波峰值

• https://charlesliuyx.github.io/2018/02/18/%E3%80%90%E7%9B%B4%E8%A7%82%E8%AF%A6%E8%A7%A3%E3%80%91%E8%AE%A9%E4%BD%A0%E6%B0%B8%E8%BF%9C%E5%BF%98%E4%B8%8D%E4%BA%86%E7%9A%84%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2%E8%A7%A3%E6%9E%90/

傅里叶变换计算

• 利用复数项 $e^{-2\pi ix \xi}$ 表示在复平面中的旋转角度

  • $x$ 为函数自变量，$\xi$ 为频率（即自变量映射比例）
  • 傅里叶变换中旋转为缺省为顺时针，所以补足负号
  • 函数在复平面中则表示为 $f(x) e^{-2\pi ix \xi}$

• 函数围成的曲线质心则为 $\frac 1 {x2 - x_1} \int{x_1}^{x_2} f(x) e^{-2\pi ix \xi} dx$

  • 系数 $\frac 1 {x_2 - x_1}$ 将积分结果放缩回质心，可省略
  • 将原积分区域外函数值定为 0，积分上下限扩展至 $-\infty, \infty$ 不影响积分结果
  • 函数有效取值部分越长，质心波动约迅速

傅里叶变换

Discrete Fourier Transformation

DFT：归一化二维离散傅里叶变换

$$\begin{align*} F(u,v) & = \frac 1 {\sqrt{NM}} \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} f(x,y) e^{-\frac {2\pi i} N ux} e^{-\frac {2\pi i} M vy} \\ f(x,y) & = \frac 1 {\sqrt{NM}} \sum_{u=0}^{N-1} \sum_{v=0}^{M-1} F(u,v) e^{\frac {2\pi i} N ux} e^{\frac {2\pi i} M vy} \\ \end{align*}$$

Discrete Consine Transformation

余弦变换

• 在给定区间为满足狄利克雷条件的连续实对称函数，可以展开为 仅含余弦项的傅里叶级数

• 对于定义在正实数域上的函数，可以通过偶延拓、或奇延拓满足 上述条件

离散余弦变换

• $(x,y) or (u,v) = (0,0)$时

  $$\begin{align*} F(u,v) & = \frac 1 N \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 N \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$

• 其他

  $$\begin{align*} F(u,v) & = \frac 1 {2N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 {2N} \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$