Deep Learning

深度学习笔记

感知机

定义

其中, sign(x)=1 if x≥0 else 0

几何解释: w⋅x+b 是特征空间的超平面, 把特征空间划分成两部分.

损失函数

  1. 错误分类点总数, 但不是连续可导, 不容易优化
  1. 错误分类点到超平面的距离. 对于给定 x0x_0x​0​​ 到超平面的距离是

其中 ∣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_ix​i​​,y​i​​ 的线形组合形式, 通过求解其系数的到 w,bw,bw,b

输入: 训练集 T=(x1,y1),...,(xN,yN)T={(x_1,y_1),...,(x_N,y_N)}T=(x​1​​,y​1​​),...,(x​N​​,y​N​​) 学习率 η\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

  1. α←0,b←0\alpha \leftarrow 0, b \leftarrow 0α←0,b←0
  2. 在训练集中选取数据 xi,yix_i,y_ix​i​​,y​i​​
  3. 如果

那么

\alpha_i \leftarrow \alpha_i + \eta\\ b \leftarrow b + \eta y_i

  1. 转 2) 直到没有错误分类数据

SVM

定义在特征空间上的间隔最大的线性分类器, 以及核技巧 (非线性分类器)

学习策略是间隔最大化, 可形式化成一个求解凸二次规划 convex quadratic programming 问题

学习方法有:

  • 线性可分 SVM: 当训练数据线性可分, 通过 hard margin maximization 学习
  • 线性 SVM: 当训练数据近似线性可分, 通过 soft margin maximization
  • 非线性 SVM: 当训练数据线性不可分, 通过 kernel trick 及 soft margin maximization 学习

线性可分 SVM

给定线性可分训练集, 通过间隔最大化或等价地求解相应凸二次规划问题而得到的分离超平面

以及相应的分类决策函数

称为线性可分支持向量机

函数间隔

对给定训练集 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}^nR​n​​ 上的连续可微的凸函数, 约束函数 hhh 是 Rn\mathbb{R}^nR​n​​ 上的仿射函数 ( 满足 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∈R​n​​,b∈R,x∈R​n​​ )

当目标函数 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

另一种解释, 最小化以下目标函数

其中第一项是合页损失函数, 定义

线性不可分 SVM

对线性不可分问题, 引入松弛变量, 解决某些样本点不能满足函数间隔大于1的约束条件 (s.t. yi(w⋅xi+b)−1≤0s.t.\ y_i(w\cdot x_i+b)-1\leq 0s.t. y​i​​(w⋅x​i​​+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)(x​i​​,y​i​​) 实例 xix_ix​i​​ 称为支持向量

非线性 SVM

有的二分类问题无法用超平面 (线性模型, 在二维是直线) 分类, 但可用超曲面 (非线性模型, 在二维是椭圆) 将它们正确分开, 那么这个问题是非线性可分问题. 此时可用线性变换, 把非线性问题变换为线性问题

核函数

设 XXX 是输入空间 (欧氏空间 Rn\mathbb{R}^nR​n​​ 的子集或离散集合) , 设 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=1​n​​a​i​​b​i​​

例: 在特征空间 R2\mathbb{R}^2R​2​​, 有

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_jx​i​​⋅x​j​​ 用核函数 K(xi,xj)=ϕ(xi)⋅ϕ(xj)K(x_i,x_j)=\phi(x_i) \cdot \phi(x_j)K(x​i​​,x​j​​)=ϕ(x​i​​)⋅ϕ(x​j​​) 代替, 此时对偶问题的目标函数为

分类决策函数为

正定核

TODO

CNN

BP

BP Hinton, 1986

对神经网络的平方代价函数

BP 是一个快速计算神经网络代价函数梯度的方法

  1. 输入 xxx, 记 a1a^1a​1​​
  2. 正向传播, 对 l=2,3,...,Ll=2,3,...,Ll=2,3,...,L 计算
  1. 输出误差

其中, ∇aC\nabla_{a} C∇​a​​C 可以看做现对于输出激活的 CCC 的改变速率

∇aC=∂C∂ajL\nabla_{a} C = \frac{\partial C}{\partial a_j^L} ∇​a​​C=​∂a​j​L​​​​∂C​​

  1. 将误差反向传播, 对每个 l=L−1,L−2,...,2l=L-1,L-2,...,2l=L−1,L−2,...,2 计算

δl=(wl+1Tδl+1)⊙∂′(zl)\delta^l=(w^{l+1}T\delta^{l+1})\odot \partial'(z^l) δ​l​​=(w​l+1​​Tδ​l+1​​)⊙∂​′​​(z​l​​)

  1. 输出: 代价函数梯度

\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]。

在反向传播中,以下门电路扮演的角色是

  • add gate,梯度传播者
  • max gate,梯度路由
  • mul gate,梯度开关?

LeNet-5

Gradient-based learning applied to document recognition Yan LeCun, 1998

LeNet

AlexNet 12’

ImageNet top-5 error 16.4%

  • Data Augmentation 数据增强: 水平翻转, 随机剪裁、平移变换, 颜色、光照变换, 防止过拟合
  • Dropout , 防止过拟合
  • ReLU, 代替 tanh sigmoid, 好处有: 本质是分段线性模型, 前向计算简单;偏导简单, 反向传播梯度, 无需指数或者除法之类操作;不容易发生梯度发散问题, Tanh和Logistic激活函数在两端的时候导数容易趋近于零, 多级连乘后梯度更加约等于0;关闭了右边, 从而会使得很多的隐层输出为0, 即网络变得稀疏, 起到了类似L1的正则化作用, 可以在一定程度上缓解过拟合. 缺点是会导致部分借点永久关闭, 改进如 pReLU randomReLu
  • Local Response Normalization 利用临近数据组做归一化, top-5 error -1.2%
  • Overlapping Pooling Pooling的步长比Pooling Kernel的对应边要小, top-5 error -0.3%
  • GPU

AlexNet

VGG

home page VGG team, Oxford, 2014

ImageNet top-5 error 7.3%

  • deepper

VGG

GoogLeNet

Going Deeper with Convolutions 2014

ImageNet top-5 error 6.7%

  • Inception, network in network

Inception

GoogLeNet

ResNet

Deep Residual Learning for Image Recognition, Kaiming He et. al., MSRA

ImageNet top-5 error 3.57%

  • Residual network, 解决层次比较深的时候无法训练的问题. 这种借鉴了Highway Network思想的网络相当于旁边专门开个通道使得输入可以直达输出, 而优化的目标由原来的拟合输出H(x)变成输出和输入的差H(x)-x, 其中H(X)是某一层原始的的期望映射输出, x是输入

DenseNet

ECCV 2016 PDF

通过增加跨层的 CNN 连接,解决反向传播时的梯度弥散问题。[5]

DNN-weighted

Deep Neural Networks for YouTube Recommendations 16 RecSys

RNN

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∈R​n​​,W​l​​∈R​n×2n​​

LSTM

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∈R​n​​,W​l​​∈R​4n×2n​​,f 是 forget gate,o 是 leak gate,

与 ResNet 有相似之处,foget gate 可以避免 gradient vanishing

GRU

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 Net:基于内容推荐音乐

Spotify 在 2014 NIPS 发表文章 [9] 和 blog,介绍了利用深度学习,从歌曲原始音频的 mel-spectrograms 中学习用于推荐系统的 laten representation(vector_exp algorithm 生成,一种协同过滤算法),并发现 filter 能够学习到低、中、高级概念,如中文流行歌曲,8-bit 流派,hihop,bass 演奏,ambient 流派等等。

Transfer Learning

Segmentation

end-to-end: 输入图片(smaller),输出标注图片

multi-scale approach: Farable et al. 2013,多个尺寸图片,分别训练模型,最后把结果叠加

refinement: Pinheiro and Collobert, Recurrent CNN for Scene Labeling, ICML 2014 PDF

Attention Model

Soft Attention For Captioning

Show, attend and tell: Neural image caption generation with visual attention, Xu et al., ICML 2015 PDF 基于注意力模型的图像摘要生成。

Reference

[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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂业务下向Mysql导入30万条数据代码优化的踩坑记录

    从毕业到现在第一次接触到超过30万条数据导入MySQL的场景(有点low),就是在顺丰公司接入我司EMM产品时需要将AD中的员工数据导入MySQL中,因此楼主负...

    haifeiWu
  • 【系统设置】CentOS 修改机器名

    ken.io
  • SQL中GROUP BY用法示例

    GROUP BY我们可以先从字面上来理解,GROUP表示分组,BY后面写字段名,就表示根据哪个字段进行分组,如果有用Excel比较多的话,GROUP BY比较类...

    Awesome_Tang
  • 考研英语-1-导学

    英二图表作文要重视。总体而言,英语一会比英语二难点。不过就写作而言,英语二会比英语一有难度,毕竟图表作文并不好写。

    用户1335799
  • ISUX Xcube智能一键生成H5

    腾讯ISUX
  • 知识体系解决迷茫的你

    最近在星球里群里都有小伙伴说道自己对未来的路比较迷茫,一旦闲下来就不知道自己改干啥,今天我这篇文章就是让你觉得一天给你 25 个小时你都不够用,觉得睡觉都是浪费...

    桃翁
  • 理工男图解零维到十维空间,烧脑已过度,受不了啦!

    让我们从一个点开始,和我们几何意义上的点一样,它没有大小、没有维度。它只是被想象出来的、作为标志一个位置的点。它什么也没有,空间、时间通通不存在,这就是零维度。

    钱塘数据
  • 中国互联网协会发布:《2018中国互联网发展报告》

    在2018中国互联网大会闭幕论坛上,中国互联网协会正式发布《中国互联网发展报告2018》(以下简称《报告》)。《中国互联网发展报告》是由中国互联网协会与中国互联...

    钱塘数据
  • 【倒计时7天】2018教育部-腾讯公司产学合作协同育人项目申请即将截止!

    腾讯高校合作
  • 不只是软件,在线也可以免费下载百度文库了。

    不管是学生,还是职场员工,下载各种文档几乎是不可避免的,各种XXX.docx,XXX.pptx更是家常便饭,人们最常用的就是百度文库,豆丁文库,道客巴巴这些下载...

    课代表

扫码关注云+社区

领取腾讯云代金券