深度学习笔记
其中, sign(x)=1 if x≥0 else 0
几何解释: w⋅x+b 是特征空间的超平面, 把特征空间划分成两部分.
其中 ∣w∣ 是 L2范式. 那么有损失函数
其中 MMM 是错误分类点的集合
随机梯度下降法 stochastic gradient descent
梯度
\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i\\ \nabla_bL(w,b)=-\sum_{x_i\in M}y_i
随机取一个错误分类点, 对 w,bw,bw,b 进行更新
w\leftarrow w+\eta y_ix_i\\ b\leftarrow b+\eta y_i\\ 0 \le \eta \le1
TODO
将 w,bw,bw,b 表示为实例 xi,yix_i,y_ixi,yi 的线形组合形式, 通过求解其系数的到 w,bw,bw,b
输入: 训练集 T=(x1,y1),...,(xN,yN)T={(x_1,y_1),...,(x_N,y_N)}T=(x1,y1),...,(xN,yN) 学习率 η\etaη
输出:
\alpha,b,f(x)=sign\bigg(\sum_{j=1}^{N}\alpha_jy_jx_j\bigg)\\ \alpha=(\alpha_1,...,\alpha_N)^T, \alpha_i=n_i\eta
那么
\alpha_i \leftarrow \alpha_i + \eta\\ b \leftarrow b + \eta y_i
定义在特征空间上的间隔最大的线性分类器, 以及核技巧 (非线性分类器)
学习策略是间隔最大化, 可形式化成一个求解凸二次规划 convex quadratic programming 问题
学习方法有:
给定线性可分训练集, 通过间隔最大化或等价地求解相应凸二次规划问题而得到的分离超平面
以及相应的分类决策函数
称为线性可分支持向量机
对给定训练集 T 和超平面 (w,b)(w,b)(w,b), 定义超平面关于样本点 (xi,yi) 的函数间隔为
定义超平面关于所有样本点的函数间隔为
\hat \gamma = \underset {i=1,...,N} {\min} \hat \gamma_i
函数间隔用来表示分类的正确性和确信度
但成比例地改变 w,bw,bw,b 会使函数间隔改变, 为解决这个问题, 可以对法向量加约束如 ∣∣w∣∣=1||w||=1∣∣w∣∣=1, 使间隔确定, 即几何间隔的思想
对给定训练集 T 和超平面 (w,b), 定义超平面关于样本的几何间隔为
\gamma = \underset {i=1,...,N} {\min} \gamma_i\\ \gamma_i = y_i \bigg(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||}\bigg)
函数间隔、几何间隔的关系有
\gamma_i=\frac {\hat \gamma_i}{||w||}\\ \gamma=\frac {\hat \gamma}{||w||}
线性可分问题中, 分离超平面有无穷多个 (感知机) , 但几何间隔最大的分离超平面上唯一的
线性[可分|不可分]间隔最大化又称 [hard|soft] margin maximization
可以表示为最优化问题
\begin{align} \underset {w,b}{\max}\ &\gamma\\ s.t.\ &y_i\bigg(\frac{w}{||w||}\cdot x_i + \frac{b}{||w||}\bigg) \geq \gamma, i=1,2,...,N \end{align}
考虑集合间隔和函数间隔的关系, 有
\begin{align} \underset {w,b}{\max}\ &\hat\gamma\\ s.t.\ &y_i (w\cdot x_i + b) \geq \hat \gamma, i=1,2,...,N \end{align}
令 γ^=1\hat \gamma = 1γ^=1, 优化问题等价于一个凸二次优化问题
\begin{align} \underset {w,b}{\min}\ &\frac{1}{2}||w||^2\\ s.t.\ &y_i (w\cdot x_i + b) - 1\geq 0, i=1,2,...,N \end{align}
凸优化问题指
\begin{align} \underset {w}{\min}\ &f(w)\\ s.t.\ &g_i(w) \leq 0, i=1,2,...,k\\ &h_i(w)=0, i=1,2,...,l \end{align}
其中, 目标函数 fff 和约束函数 ggg 都是 Rn\mathbb{R}^nRn 上的连续可微的凸函数, 约束函数 hhh 是 Rn\mathbb{R}^nRn 上的仿射函数 ( 满足 h(x)=a⋅x+b,a∈Rn,b∈R,x∈Rnh(x)=a\cdot x + b, a \in \mathbb{R}^n, b \in \mathbb{R},x \in \mathbb{R}^nh(x)=a⋅x+b,a∈Rn,b∈R,x∈Rn )
当目标函数 fff 是二次函数且约束函数 ggg 是仿射函数时, 上述问题称为凸二次规划问题 convex quadratic programming
TODO 证明存在性
证明唯一性
TODO 应用拉格朗日对偶性, 推导得到对偶形式《统计学习方法》P103
\begin{align} \underset{\alpha} {\min}\ & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i\\ s.t.\ & \sum_{i=1}^{N}\alpha_i y_i=0\\ & 0 \le \alpha_i , i = 1,2,...,N \end{align}
hinge loss
另一种解释, 最小化以下目标函数
其中第一项是合页损失函数, 定义
对线性不可分问题, 引入松弛变量, 解决某些样本点不能满足函数间隔大于1的约束条件 (s.t. yi(w⋅xi+b)−1≤0s.t.\ y_i(w\cdot x_i+b)-1\leq 0s.t. yi(w⋅xi+b)−1≤0) , 优化问题变为
\begin{align} \underset {w,b}{\min}\ &\frac{1}{2}||w||^2 + C\sum_{i=1}^N \xi_i\\ s.t.\ &y_i (w\cdot x_i + b) \geq 1 - \xi_i, i=1,2,...,N\\ & \xi_i \geq 0 \end{align}
可以证明 www 时唯一的, bbb 不唯一但存在于一个区间
\begin{align} \underset{\alpha} {\min}\ & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i\\ s.t.\ & \sum_{i=1}^{N}\alpha_i y_i=0\\ & 0 \le \alpha_i \le C, i = 1,2,...,N \end{align}
线性不可分时, 将对偶问题的解 α∗=(α1∗,...,αN∗)T\alpha^*=(\alpha_1^*,...,\alpha_N^*)^Tα∗=(α1∗,...,αN∗)T 中对应于 αi∗>0\alpha_i^* > 0αi∗>0 的样本点 (xi,yi)(x_i,y_i)(xi,yi) 实例 xix_ixi 称为支持向量
有的二分类问题无法用超平面 (线性模型, 在二维是直线) 分类, 但可用超曲面 (非线性模型, 在二维是椭圆) 将它们正确分开, 那么这个问题是非线性可分问题. 此时可用线性变换, 把非线性问题变换为线性问题
设 XXX 是输入空间 (欧氏空间 Rn\mathbb{R}^nRn 的子集或离散集合) , 设 HHH 为特征空间 (Hilbert 空间) , 如果存在一个
使得对所有 x,z∈Xx,z \in Xx,z∈X , 函数 K(x,z)满足条件
则称 K(x,z)K(x,z)K(x,z) 为核函数, ϕ(x)\phi(x)ϕ(x) 为映射函数, 其中 ⋅\cdot⋅ 表示内积即 a⋅b=∑i=1naibia \cdot b=\sum_{i=1}^{n} a_ib_ia⋅b=∑i=1naibi
例: 在特征空间 R2\mathbb{R}^2R2, 有
K(x,z)=(x \cdot z)^2\\ \phi(x) = ((x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)}, (x^{(2)})^2)^T
在学习与预测中只定义核函数 K(x,z)K(x,z)K(x,z), 而不显式地定义映射函数 ϕ\phiϕ
通常, 直接计算 KKK 比较容易, 通过 ϕ\phiϕ 计算 KKK 不容易. 把 SVM 的目标函数、决策函数的内积 xi⋅xjx_i \cdot x_jxi⋅xj 用核函数 K(xi,xj)=ϕ(xi)⋅ϕ(xj)K(x_i,x_j)=\phi(x_i) \cdot \phi(x_j)K(xi,xj)=ϕ(xi)⋅ϕ(xj) 代替, 此时对偶问题的目标函数为
分类决策函数为
TODO
BP Hinton, 1986
对神经网络的平方代价函数
BP 是一个快速计算神经网络代价函数梯度的方法
其中, ∇aC\nabla_{a} C∇aC 可以看做现对于输出激活的 CCC 的改变速率
∇aC=∂C∂ajL\nabla_{a} C = \frac{\partial C}{\partial a_j^L} ∇aC=∂ajL∂C
δl=(wl+1Tδl+1)⊙∂′(zl)\delta^l=(w^{l+1}T\delta^{l+1})\odot \partial'(z^l) δl=(wl+1Tδl+1)⊙∂′(zl)
\frac{\partial C}{\partial w_{jk}^{l}}=a_{k}^{l-1}\delta_j^l \\ \frac{\partial C}{\partial b_j^l}=\delta_j^l
其中,⊙\odot⊙
导数通过链式法则 ∂f∂x=∂f∂h∂h∂x\frac{\partial f}{\partial x} =\frac{\partial f}{\partial h} \frac{\partial h}{\partial x}∂x∂f=∂h∂f∂x∂h 计算,每个节点只需要提供 forward()
backward()
的 API,详见 [3]。
在反向传播中,以下门电路扮演的角色是
Gradient-based learning applied to document recognition Yan LeCun, 1998
ImageNet top-5 error 16.4%
home page VGG team, Oxford, 2014
ImageNet top-5 error 7.3%
Going Deeper with Convolutions 2014
ImageNet top-5 error 6.7%
Deep Residual Learning for Image Recognition, Kaiming He et. al., MSRA
ImageNet top-5 error 3.57%
ECCV 2016 PDF
通过增加跨层的 CNN 连接,解决反向传播时的梯度弥散问题。[5]
DNN-weighted
Deep Neural Networks for YouTube Recommendations 16 RecSys
Karpathy et al. 2015 [6] 发现,RNN 的 cell 有特殊职责,如:引用 cell,代码缩进 cell
h_t^l = \tanh{} W^l \left( \begin{array} \\ h^{l-1}_t \\ h^{l}_{t-1} \end{array} \right) \\
其中 h∈Rn,Wl∈Rn×2nh \in \mathbb R^n , W^l \in \mathbb R^{n \times 2n}h∈Rn,Wl∈Rn×2n
Hochereiter et al. 1997 [7] 提出 Long Short Term Memory
\left( \begin{array} \\ i \\ f \\ o \\ g \end{array} \right) = \left( \begin{array}\\ \text{sigm}\\ \text{sigm}\\ \text{sigm}\\ \tanh \end{array} \right) W^l \left( \begin{array}\\ h_l^{l-1} \\ h_{t-1}^l \end{array} \right) \\ c_t^l = f \odot c_{t-1}^l + i \odot g \\ h_t^l = o \odot \tanh(c_t^l)
其中 x∈Rn,Wl∈R4n×2nx\in \mathbb R^n, W^l \in \mathbb R^{4n \times 2n}x∈Rn,Wl∈R4n×2n,f 是 forget gate,o 是 leak gate,
与 ResNet 有相似之处,foget gate 可以避免 gradient vanishing
Cho et al. 2014 提出的 LSTM 变种,更容易实现,效果与 LSTM 差不多
r_l = \text{sigm} (W_{xr}x_l + W_{hr}h_{t-1} + b_r)\\ z_l = \text{sigm} (W_{xz}x_l + W_{hz}h_{t-1} + b_z)\\ \tilde h_l = \tanh (W_{xh}x_l + W_{hh}(r_t \odot h_{t-1}) + b_h)\\ h_t = z_t \odot h_{t-1} + (1-z_t) \odot \tilde h_t
Spotify 在 2014 NIPS 发表文章 [9] 和 blog,介绍了利用深度学习,从歌曲原始音频的 mel-spectrograms 中学习用于推荐系统的 laten representation(vector_exp algorithm 生成,一种协同过滤算法),并发现 filter 能够学习到低、中、高级概念,如中文流行歌曲,8-bit 流派,hihop,bass 演奏,ambient 流派等等。
end-to-end: 输入图片(smaller),输出标注图片
multi-scale approach: Farable et al. 2013,多个尺寸图片,分别训练模型,最后把结果叠加
refinement: Pinheiro and Collobert, Recurrent CNN for Scene Labeling, ICML 2014 PDF
Show, attend and tell: Neural image caption generation with visual attention, Xu et al., ICML 2015 PDF 基于注意力模型的图像摘要生成。
[1]《统计学习方法》李航
[2] Pan S J, Yang Q. A survey on transfer learning[J]. IEEE Transactions on knowledge and data engineering, 2010, 22(10): 1345-1359. PDF
[3] CS231n Winter 2016 Lecture 4 Backpropagation, Neural Networks VIDEO PPT
[4] CS231n Winter 2016 Lecture 4 Backpropagation, Neural Networks VIDEO PDF
[5] 为什么ResNet和DenseNet可以这么深? HTML
[6] Karpathy A, Johnson J, Fei-Fei L. Visualizing and understanding recurrent networks[J]. arXiv preprint arXiv:1506.02078, 2015. PDF
[7] Hochreiter S, Schmidhuber J. Long short-term memory[J]. Neural computation, 1997, 9(8): 1735-1780. PDF
[8] Cho K, Van Merriënboer B, Gulcehre C, et al. Learning phrase representations using RNN encoder-decoder for statistical machine translation[J]. arXiv preprint arXiv:1406.1078, 2014. PDF
[9] Mack, Jacob E., Theophilus D. Owusu, and John J. Scarpino. “CONFIDENTIALITY, PRIVACY, ACCESSIBILITY AND SECURITY OF BIG DATA USAGES WITHIN MOBILE RECOMMENDER SYSTEMS, AS SOCIETY EMBRACES CLOUD BASED TECHNOLOGY.” Issues in Information Systems 17.1 (2016). PDF