矩阵分解

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

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

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

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

矩阵加法分解

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

  

Convolutional

卷积：卷积区域逐点乘积、求和作为卷积中心取值

• 用途：

  • 提取更高层次的特征，对图像作局部变换、但保留局部特征
  • 选择和其类似信号、过滤掉其他信号、探测局部是否有相应模式，如
    • sobel 算子获取图像边缘

• 可变卷积核与传统卷积核区别

  • 传统卷积核参数人为确定，用于提取确定的信息
  • 可变卷积核通过训练学习参数，以得到效果更好卷积核

• 卷积类似向量内积

特点

• 局部感知：卷积核所覆盖的像素只是小部分、局部特征

  • 类似于生物视觉中的 receptive field

• 多核卷核：卷积核代表、提取某特征，多各卷积核获取不同特征

• 权值共享：给定通道、卷积核，共用滤波器参数

  • 卷积层的参数取决于：卷积核、通道数
  • 参数量远小于全连接神经网络

• receptive field：感受野，视觉皮层中对视野小区域单独反应的神经元

  • 相邻细胞具有相似和重叠的感受野
  • 感受野大小、位置在皮层之间系统地变化，形成完整的视觉空间图

发展历程

• 1980 年 neocognitron 新认知机提出
  • 第一个初始卷积神经网络，是感受野感念在人工神经网络首次应用
  • 将视觉模式分解成许多子模式（特征），然后进入分层递阶式的特征平面处理

卷积应用

Guassian Convolutional Kernel

高斯卷积核：是实现 尺度变换 的唯一线性核

$$\begin{align*} L(x, y, \sigma) & = G(x, y, \sigma) * I(x, y) \\ G(x, y, \sigma) & = \frac 1 {2\pi\sigma^2} exp\{\frac {-((x-x_0)^2 + (y-y_0)^2)} {2\sigma^2} \} \end{align*}$$

• $G(x,y,\sigma)$：尺度可变高斯函数
• $I(x,y)$：放缩比例，保证卷积核中各点权重和为 1
• $(x,y)$：卷积核中各点空间坐标
• $\sigma$：尺度变化参数，越大图像的越平滑、尺度越粗糙

Attention Machanism

注意力机制：将query、key-value映射至输出的权重生成机制

$$Attention(Q, K, V) = \phi(f_{Att}(Q, K), V)$$

• $V_{L d_v}$：value矩阵，*信息序列矩阵
• $K_{L * d_k}$：key矩阵，大部分情况即为$V$
• $Q_{L * d_k}$：query矩阵，其他环境信息
• $L, d_k, d_v$：输入序列长度、key向量维度、value向量维度
• key、value向量为$K, V$中行向量

• 合理分配注意力，优化输入信息来源

  • 给重要特征分配较大权
  • 不重要、噪声分配较小权

• 在不同模型间学习对齐

  • attention机制常联合Seq2Seq结构使用，通过隐状态对齐
  • 如：图像至行为、翻译

Attention Model

• Attenion机制一般可以细化如下

$$\begin{align*} c_t & = \phi(\alpha_t, V) \\ \alpha_{t} & = softmax(e_t) \\ & = \{ \frac {exp(e_{t,j})} {\sum_{k=1}^K exp(e_{t,k})} \} \\ e_t & = f_{Att}(K, Q) \end{align*}$$

• $c_t$：context vector，注意力机制输出上下文向量
• $e_{t,j}$：$t$时刻$i$标记向量注意力得分
• $\alpha_{t,i}$：$t$时刻$i$标记向量注意力权重
• softmax归一化注意力得分

• $f_{Att}$：计算各标记向量注意力得分

  • additive attention
  • multiplicative/dot-product attention：
  • local attention

  • 其参数需联合整个模型训练、输入取决于具体场景

• $\phi_{Att}$：根据标记向量注意力权重计算输出上下文向量

  • stochastic hard attention
  • deterministic soft attention

• $Q$可能包括很多信息

  • Decoder结构输出、Encoder结构输入
  • $W$待训练权重矩阵
  • LSTM、RNN等结构隐状态

Additive Attention

• 单隐层前馈网络（MLP）

  $$e_{t,j} = v_a^T f_{act}(W_a [h_{t-1}; g_j])$$

  • $h_{t-1}$：输出结构隐状态
  • $g_j$：输入结构隐状态
  • $W_a, v_a$：待训练参数
  • $f_{act}$：激活函数$tanh$、$ReLU$等

Multiplicative/Dot-product Attention

$$e_{t,j} = \left \{ \begin{array}{l} h_{t-1}^T g_j, & dot \\ h_{t-1}^T W_a g_j, & general \\ W_a h_{t-1}, & location \end{array} \right.$$

• 相较于加法attention实际应用中更快、空间效率更高 （可以利用高度优化的矩阵乘法运算）

• MLP
• 內积形式

Tricks

• 将输出作为输入引入，考虑上一次输出影响

  

• Scaled Dot-Product Attention

  $$f_{Att} = \frac {Q K^T} {\sqrt{d_k}}$$
  • 避免內积随着key向量维度$d_k$增大而增大，导致softmax 中梯度过小

Stochastic Hard Attention

hard attention：随机抽取标记向量作为注意力位置

• 注意力位置视为中间one-hot隐向量，每次只关注某个标记向量

• 模型说明

  • $f_{Att}$为随机从标记向量$a$中抽取一个
  • $\alpha$视为多元伯努利分布参数，各分量取值表示对应 标记向量被抽中概率，此时上下文向量也为随机变量

$$\begin{align*} p(s_{t,i}=1) & = \alpha_{t,i} \\ c_t & = V s \end{align*}$$

• $s$：注意力位置，中间隐one-hot向量，服从$\alpha$指定的 多元伯努利分布
• $h_i$：第$i$上下文向量

参数训练

• 参数$\alpha$不可导、含有中间隐变量$s$，考虑使用EM算法 思想求解

  $$\begin{align*} log p(y) & = log \sum_s p(s) p(y|s) \\ & \geq \sum_s p(s) log p(y|s) := L_s \\ \frac {\partial L_s} {\partial W} & = \sum_s [ \frac {\partial p(s)} {\partial W} + \frac 1 {p(y|s)} \frac {\partial p(y|s)} {\partial W}] \\ & = \sum_s p(s) [\frac {\partial log p(y|s)} {\partial W} + log p(y|s) \frac {\partial log p(s|a)} {\partial W}] \end{align*}$$

  • $L_s$：原对数似然的函数的下界，以其作为新优化目标
  • $W$：参数

• 用蒙特卡罗采样方法近似求以上偏导

  • $s$按多元伯努利分布抽样$N$次，求$N$次偏导均值

    $$\frac {\partial L_s} {W} \approx \frac 1 N \sum_{n=1}^N [\frac {\partial log p(y|\tilde s_n)} {\partial W} + log p(y|\tilde s_n) \frac {\partial log p(\tilde s_n|a)} {\partial W}]$$

    • $\tilde s_n$：第$n$次抽样结果

  • 可对$p(y|\tilde s_n)$进行指数平滑减小估计方差

Deterministic Soft Attention

soft attention：从标记向量估计上下文向量期望

• 考虑到所有上下文向量，所有标记向量加权求和上下文向量
• 模型说明
  • $f_{Att}$计算所有标记向量注意力得分
  • $\alpha$可视为个标记向量权重

$$E_{p(s_t)} [c_t] = \sum_{i=1}^L \alpha_{t,i} a_i$$

• 模型光滑可微：可直接用反向传播算法训练

Local Attention

local attention：从所有标记向量中选取部分计算soft attention

• 可以视为hard、soft attention结合
  • hard attention选取标记向量子区间，避免噪声干扰
  • soft attention加权求和，方便训练

子区间选取

• 为目标$t$选取对齐位置$p_t$，得到子区间$[p_t-D, p_t+D]$ （$D$为经验选取）

• monotonic alignment：直接设置$p_t=t$

• predictive alignment：

  $$p_t = S sigmoid(v_p^T tanh(W_p h_t))$$

  • $W_p, v_p$：待学习参数

• 可以使用高斯分布给注意力权重加权，强化$p_t$附近标记向量 （根据经验可以设置$\sigma = \frac D 2$） $$\alpha_{t,j} = softmax(e_{t,j}) exp(-\frac {(j - p_t)^2} {2\sigma^2})$$

Self Attention

Self Attention/Intra-Attention：关联同一序列内不同位置、 以学习序列表示的attenion机制

• 类似卷积、循环结构

  • 将不定长的序列映射为等长的另一序列
  • 从序列中提取高层特征

• 特点

  • 类似卷积核，多个self attention可以完全并行
  • 无需循环网络多期传递信息，输入序列同期被处理
  • 可使用local attention机制限制计算复杂度

Multi-Head Attention

Multi-Head Attention：从相同输入、输出序列学习多个 attention机制

$$\begin{align*} MultiHead(X) & = Concat(head1, ..., head_h) W^O \\ head_i & = Attention(QW_i^Q, KW_i^K, VW_i^V) \end{align*}$$

• $Q, K, V$：元信息矩阵，据此训练多组query、key-value， 一般就是原始输入序列矩阵

• 可以并行训练，同时从序列中提取多组特征

人工交互作用层

交互作用层：人工设置特征之间交互方式

Flatten Layer

展平层：直接拼接特征，交互作用交由之后网络训练

$$f_{Flat}(V_x) = \begin{bmatrix} x_1 v_1 \\ \vdots\\ x_M v_M \end{bmatrix}$$

• $V_x$：特征向量集合

• 对同特征域特征处理方式
  • 平均
  • 最大

二阶交互作用

二阶交互作用层：特征向量之间两两逐元素交互

• 交互方式
  • 逐元素
    • 乘积
    • 求最大值：无
  • 按向量
• 聚合方式
  • 求和
    • 平权
    • Attention加权
  • 求最大值：无

Bi-Interaction Layer

Bi-Interaction Layer：特征向量两两之间逐元素乘积、求和

$$\begin{align*} f_{BI}(V) & = \sum_{i=1}^M \sum_{j=i+1}^M v_i \odot v_j \\ & = \frac 1 2 (\|\sum_{i=1}^M v_i\|_2^2 - \sum_{i=1}^M \|v_i\|_2^2) \end{align*}$$

• $\odot$：逐元素乘积

• 没有引入额外参数，可在线性时间$\in O(kM_x)$内计算
• 可在低层次捕获二阶交互影响，较拼接操作更informative
  • 方便学习更高阶特征交互
  • 模型实际中更容易训练

Attention-based Pooling

Attention-based Pooling：特征向量两两之间逐元素乘积、加权 求和

$$f_{AP}(V) & = \sum_{i=1}^M \sum_{j=i+1}^M \alpha_{i,j} (v_i \odot v_j)$$

• $\alpha_{i,j}$：交互作用注意力权重，通过注意力网络训练

Embedding

嵌入层：将高维空间中离散变量映射为低维稠密 embedding 向量表示

• embedding 向量更能体现样本之间关联

  • 內积（內积）体现样本之间接近程度
  • 可通过可视化方法体现样本差异

• embedding 向量更适合某些模型训练

  • 模型不适合高维稀疏向量
  • embedding 向量矩阵可以联合模型整体训练，相当于提取特征
  • embedding 向量也可能类似迁移学习独立训练之后直接融入模型中

• Embedding：将度量空间中对象映射到另个（低维）度量空间，并尽可能保持不同对象之间拓扑关系，如 Word-Embedding

Embedding表示

• 特征不分组表示

  $$\begin{align*} \varepsilon_x & = E x \\ & = [x_1v_1, x_2v_2, \cdots, x_Mv_M] \\ & = [x_{M_1} v_{M_1}, \cdots, x_{M_m} v_{M_m}] \end{align*}$$

  • $E$：embedding向量矩阵
  • $M$：特征数量
  • $v_i$：$k$维embedding向量
  • $x_i$：特征取值，对0/1特征仍等价于查表，只需考虑非0特征

    • $x_{M_i}$：第$j$个非0特征，编号为$M_i$
    • $m$：非零特征数量

  • $\varepsilon_x$：特征向量集合

• 特征分组表示

  $$\begin{align*} \varepsilon_x & = [V_1 g_1, V_2 g_2, \cdots, V_G g_G] \end{align*}$$

  • $G$：特征组数量
  • $V_i$：第$i$特征组特征向量矩阵
  • $g_i$：第$i$特征组特征取值向量

池化/下采样

池化：在每个区域中选择只保留一个值

• 用于减小数据处理量同时保留有用的信息

  • 相邻区域特征类似，单个值能表征特征、同时减少数据量

• 保留值得选择有多种

  • 极值
  • 平均值
  • 全局最大

• 直观上

  • 模糊图像，丢掉一些不重要的细节

Max Pooling

最大值采样：使用区域中最大值作为代表

Average Pooling

平均值采样：使用池中平均值作为代表

Recurrent Neural Network

RNN：处理前后数据有关联的序列数据

• 左侧：为折叠的神经网络，右侧：按时序展开后的网络
• $h$：循环隐层，其中神经元之间有权连接，随序列输入上一期 隐层会影响下一期
• $o$、$y$：输出预测值、实际值
• $L$：损失函数，随着时间累加

• 序列往往长短不一，难以拆分为独立样本通过普通DNN训练

结构

• 普通的DNN：固定大小输入得到固定输出
• 单个输入、序列输出：输入图片，得到描述文字序列
• 序列输入、单个输出：情感分析
• 异步序列输入、输出：机器翻译
• 同步序列输入、输出：视频帧分类

权值连接

• 循环隐层内神经元之间也建立权连接，即循环

  • 基础神经网络只在层与层之间建立权值连接是RNN同普通DNN 最大不同之处

• 循环隐层中神经元只会和其当前层中神经元建立权值连接

  • 即不受上期非同层神经元影响
  • 循环隐层中神经元$t$期状态$h^{(t)}$由当期输入、 $h^{(t-1)}$共同决定

• Gated Feedback RNN：循环隐层会对下期其他隐层产生影响

逻辑结构

• RNN网络实际结构是线性、折叠的，逻辑结构则是展开的结构， 考虑RNN性质应该在展开的逻辑结构中考虑

• 序列输入

  • 实际结构：依次输入
  • 逻辑结构：里是整体作为一次输入、才是一个样本，损失、 反向传播都应该以完整序列为间隔

• 权值共享

  • 实际结构：不同期的权值实际是同一组
  • 逻辑结构：称为权值共享

• 重复模块链

  • 实际结构：同一个模块
  • 逻辑结构：不同期模块之间信息流动形成链式形式

信息传递

• RNN循环层中信息只能由上一期直接传递给下一期

• 输入、输出相关信息间隔较近时，普通RNN可以胜任

  

• 当间隔很长，RNN理论上虽然能够处理，但由于梯度消失问题， 实际上长期依赖会消失，需要LSTM网络

  

Forward Propogation

• $h^{(t)} = \sigma(z^{(t)}) = \sigma(Ux^{(t)} + Wh^{(t-1)} +b )$

  • $\sigma$：RNN激活函数，一般为$tanh$
  • $b$：循环隐层偏置

• $o^{(t)} = Vh^{(t)} + c$

  • $c$：输出层偏置

• $\hat{y}^{(t)} = \sigma(o^{(t)})$

  • $\sigma$：RNN激活函数，分类时一般时$softmax$

Back-Propogation Through Time

BPTT：训练RNN的常用方法

• 本质仍然是BP算法，但是RNN处理序列数据，损失随期数累加， 即计算梯度时使用最终损失$L = \sum_{t=1}^\tau L^{(t)}$

• 对循环层中参数，梯度沿着期数反向传播，第t期反向传播时， 需要逐级求导

• 序列整体作为一次输入，进行一次反向传播
• 理论上可以漂亮的解决序列数据的训练，但是和DNN一样有梯度 消失的问题，尤其是序列很长时，所以一般不能直接应用

非循环层

• $\frac{\partial L}{\partial c}$

  $$\begin{align*} \frac{\partial L}{\partial c} & = \sum_{t=1}^{\tau} \frac{\partial L^{(t)}}{\partial c} & = \sum_{t=1}^{\tau}\frac{\partial L^{(t)}} {\partial o^{(t)}} \frac{\partial o^{(t)}}{\partial c} & = \sum_{t=1}^{\tau}\hat{y}^{(t)} - y^{(t)} \end{align*}$$

  • $L^{(t)} = \frac 1 2 (\hat{y}^{(t)} - y^{(t)})^2$： 使用平方损失

• $\frac{\partial L}{\partial V}$

  $$\begin{align*} \frac{\partial L}{\partial V} & = \sum_{t=1}^{\tau} \frac{\partial L^{(t)}}{\partial V} & = \sum_{t=1}^{\tau} \frac{\partial L^{(t)}} {\partial o^{(t)}} \frac{\partial o^{(t)}}{\partial V} & = \sum_{t=1}^{\tau}(\hat{y}^{(t)} - y^{(t)}) (h^{(t)})^T \end{align*}$$

循环层

• 为方便定义： $\delta^{(t)} = \frac {\partial L} {\partial h^{(t)}}$

• $\delta^{(t)}$

  $$\begin{align*} \delta^{(t)} & = \frac {\partial L} {\partial h^{(t)}} \\ & = \frac{\partial L}{\partial o^{(t)}} \frac{\partial o^{(t)}}{\partial h^{(t)}} + \frac{\partial L}{\partial h^{(t+1)}} \frac{\partial h^{(t+1)}}{\partial h^{(t)}} & = V^T(\hat{y}^{(t)} - y^{(t)}) + W^T\delta^{(t+1)}diag(1-h^{(t+1)})^2) \end{align*}$$

  • $\frac{\partial h^{(t+1)}}{\partial h^{(t)}} = diag(1-h^{(t+1)})^2)$ ：$tanh(x)$梯度性质
  • $h^{(t)}(t<\tau)$梯度：被后一期影响（反向传播），需递推

• $\delta^{(\tau)}$

  $$\begin{align*} \delta^{(\tau)} & = \frac{\partial L}{\partial o^{(\tau)}} \frac{\partial o^{(\tau)}}{\partial h^{(\tau)}} & = V^T(\hat{y}^{(\tau)} - y^{(\tau)}) \end{align*}$$

  • $\tau$期后没有其他序列，可以直接求出

• $\frac{\partial L}{\partial W}$

  $$\begin{align*} \frac{\partial L}{\partial W} & = \sum_{t=1}^{\tau} \frac{\partial L}{\partial h^{(t)}} \frac{\partial h^{(t)}}{\partial W} & = \sum_{t=1}^{\tau}diag(1-(h^{(t)})^2) \delta^{(t)}(h^{(t-1)})^T \end{align*}$$

  • 需要由$\sigma^{(t)}$累加得到

• $\frac{\partial L}{\partial b}$

  $$\begin{align*} \frac{\partial L}{\partial b} & = \sum_{t=1}^{\tau} \frac{\partial L}{\partial h^{(t)}} \frac{\partial h^{(t)}}{\partial b} & = \sum_{t=1}^{\tau} diag(1-(h^{(t)})^2)\delta^{(t)} \end{align*}$$

• $\frac{\partial L}{\partial U}$

  $$\begin{align*} \frac{\partial L}{\partial U} & = \sum_{t=1}^{\tau} \frac{\partial L}{\partial h^{(t)}} \frac{\partial h^{(t)}}{\partial U} & = \sum_{t=1}^{\tau}diag(1-(h^{(t)})^2) \delta^{(t)}(x^{(t)})^T \end{align*}$$

}$$

Long Short Term Memory

LSTM：通过刻意设计、默认可以学习长期依赖信息的RNN网络

• LSTM中每个重复的模块（层）称为细胞

  • 细胞结构经过特殊设计，相较于准RNN简单细胞结构能较好 保留长时信息

• 多个LSTM细胞可以组成block，其中细胞门权值共享

  • block中各个细胞状态不同
  • 这个是同时刻、不同层的真权值共享，类似CNN中的卷积核
  • 减少参数个数，效率更高

• long term memory：长期记忆，参数
• short term memory：短期记忆，数据流
• long short term memory：长[的]短期记忆，细胞状态

LSTM标准细胞结构

$$\begin{align*} i^{(t)} & = \sigma(W_i[x^{(t)}, h^{(t-1)}], b_i), & input gate \\ f^{(t)} & = \sigma(W_f[x^{(t)}, h^{(t-1)}], b_f), & forget gate \\ o^{(t)} & = \sigma(W_o[x^{(t)}, h^{(t-1)}], b_o), & output gate \\ \tilde C^{(t)} & = tanh((W_c[x^{(t)}, h^{(t)}])), & memory alternates \\ C^{(t)} & = f^{(t)} \odot c^{(t-1)} + i^{(t)} \odot c^{(t)}, & new memory \\ h^{(t)} & = o^{(t)} \odot tanh(c^{(t)}), & output \end{align*}$$

• $W_i, b_i, W_f, b_f, W_o, b_o$：输入门、遗忘门、输出门 参数
• $\odot$：逐项乘积
• $x_t$：第$t$期输入
• $i^{(t)}$：输出门权重，决定需要更新的信息
• $f^{(t)}$：遗忘门权重，决定需要遗忘的信息
• $o^{(t)}$：输出门权重，决定需要输出的信息
• $h^{(t-1)}$：第$t-1$期细胞状态输出
• $\tilde C_t$：第$t$期更新备选内容
• $C^{(t)}$：第$t$期更新完成后细胞状态

• 输入、遗忘、输出门特点

  • 当期输入$x^{(t)}$、上期输出$h^{(t-1)}$作为输入
  • sigmoid作为激活函数，得到$[0,1]$间控制、权重向量
    • 1：完全保留
    • 0：完全舍弃

• 细胞状态、输出特点

  • tanh作激活函数，得到$[-1,1]$间信息向量
    • $h^{(t-1)}, x^t$：备选更新信息输入
    • $C^{(t-1)}$：输出信息输入
  • 与门限权重逐项乘积确定最终遗忘、输入、输出

  • 细胞状态选择（候选、输出）都是使用双曲正切激活，应该 是为了有正由负

Gates

• Forget Gate：遗忘门，决定要从细胞状态中舍弃的信息

  

• Input Gate：输入门，决定向细胞状态中保留的信息

  

• Ouput Gate：输出门，决定从细胞状态中输出的信息

  

Cell State

细胞状态：LSTM中最重要的核心思想

• 随着时间流动，承载之前所有状态信息，代表长期记忆

  • 类似于传送带，直接在整个链上运行，只有少量线性交互
  • 信息其上流派很容易保持不变
  • 通过“三个门”保护、控制

• LSTM可以保证长短时记忆可以理解为

  • $C_t$中历史信息比重由$f^{(t)}$确定
  • $f^{(t)}$趋近于1时历史信息能较好的保留

Gated Recurrent Unit

$$\begin{align*} r^{(t)} & = \sigma(W_r [h^{(t-1)}, x^{(t)}] + b_r), & reset gate \\ z^{(t)} & = \sigma(W_z [h^{(t-1)}, x^{(t)}] + b_z), & update gate \\ \tilde h^{(t)} &= tanh(W_h [r^{(t)} h^{(t-1)}, x^{(t)}]), & memory alternates\\ h^{(t)} & = (1 - z^{(t)}) \odot h^{(t-1)} + z^{(t)} \odot \tilde h^{(t)}, & new memory \end{align*}$$

• $W_r, b_r, W_z, b_z$：重置门、更新门参数
• $h^{(t)}$：原细胞状态、隐层输出合并
• $\tilde{h}_t$：第$t$期更新备选信息
• $r^{(t)}$：重置门权重输出，重置上期状态$h_{t-1}$再作为更新 门输入
• $z^{(t)]$：更新门权重输出，当期状态$ht$中$h{t-1}$、 $\tilde{h}_t$占比（遗忘、更新的结合）

• 合并细胞状态、隐层输出
• 合并遗忘门、输出门为更新门

其他变体结构

Vanilla LSTM

• Peephole Connection：细胞状态也作为3个门中sigmoid的 输入，影响控制向量的生成

Coupled Input and Forget Gate

• $1-f_i$代替$i_t$，结合遗忘门、输入门

结构比较

在Vanilla LSTM基础上的8个变体在TIMIT语音识别、手写字符识别、 复调音乐建模三个应用中比较

• No Input Gate：NIG，没有输入门
• No Forget Gate：NFG，没有遗忘门
• No Output Gate：NOG，没有输出门
• No Input Acitivation Function：NIAF，输入门没有tanh 激活
• No Output Activation Function：NOAF，输出门没有tanh 激活
• No Peepholes：NP，普通LSTM
• Coupled Input and Forget Gate：CIFG，遗忘、输出门结合
• Full Gate Recurrence：FGR，所有门之间有回路

• Vanilla LSTM效果均良好，其他变体没有性能提升

• 细胞结构

  • 遗忘门、输入门是最重要的部分
    • 遗忘门对LSTM性能影响十分关键
    • 输出门对限制无约束细胞状态输出必要
  • CIFG、NP简化结构，单对结果没有太大影响

• 超参

  • 学习率、隐层数量是LSTM主要调节参数
    • 两者之间没有相互影响，可以独立调参
    • 学习率可以可以使用小网络结构独立校准
  • 动量因子影响不大
  • 高斯噪声的引入有损性能、增加训练时间

?时间