本节主要介绍了样本数据预处理,权重矩阵的初始化,规则化技术,以及一些损失函数。

Setting up the data and the model

Data Preprocessing

  1. 均值减法

  2. 归一化:
    零中心化 + 每个维度/std(x, axis = 0)
    每个维度做归一化,使得其值最大为1,最小为-1

  3. PCA
    首先将数据去中心化,然后求数据的协方差矩阵,并进行奇异值分解,接着可以得到原始样本数据去相关性后的新样本数据,同时,如果我们想要对数据进行降维处理,只需要选择奇异值分解得到的左特征矩阵的前n个特征向量来去相关性计算就可以了。
    code:

    1
    2
    3
    4
    5
    6
    # Assume input data matrix X of size [N x D]
    X -= np.mean(X, axis = 0) # zero-center the data (important)
    cov = np.dot(X.T, X) / X.shape[0] # get the data covariance matrix
    U,S,V = np.linalg.svd(cov)
    Xrot = np.dot(X, U) # decorrelate the data
    Xrot_reduced = np.dot(X, U[:,:100]) # Xrot_reduced becomes [N x 100]
  4. 白化
    白化操作实际上是在去相关性的数据样本上除以他们对应的特征值矩阵,进行归一化。
    几何解释:当输入数据服从一个多元高斯分布,那么白化就是将这些样本数据转变成服从一个零均值,单位协方差矩阵的高斯分布。
    code:

    1
    2
    3
    # whiten the data:
    # divide by the eigenvalues (which are square roots of the singular values)
    Xwhite = Xrot / np.sqrt(S + 1e-5)

下面三幅图片分别描述原始数据,去相关性的数据,和白化后的数据。

在实际的操作中,对于卷积神经网络,PCA/白化技术运用的并不多,通常会将数据进行零中心化处理。

Weight Initialization

  1. 错误:全零初始化,每个单元都一致,造成了对称性。

  2. 小随机值初始化: 非常接近0但又不等于0

  3. 使用 $1/sqrt(n)$ 来校准方差:
    理论推导:
    考虑内积$s=\sum_i^n w_i x_i$, 计算 $s$ 的方差:

    \begin{align}
    Var(s) &= Var(\sum_i^n w_ix_i) \\
    &= \sum_i^n Var(w_ix_i) \\
    &= \sum_i^n[E(w_i)]^2 Var(x_i)+E[(x_i)]^2 Var(w_i)+Var(x_i)Var(w_i) \\
    &= \sum_i^n Var(x_i)Var(w_i) \\
    &= (n Var(w))Var(x)
    \end{align}
    所以,初始化权重矩阵 w = np.random.randn(n) / sqrt(n)
    对于ReLU,初始化:w = np.random.randn(n) * sqrt(2.0/n)
    Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification(He et al.)

  4. 稀疏初始化

  5. bias初始化:通常为0

  6. Batch Normalization: 在网络的每一层之前都做预处理,只是这种操作以另一种方式与网络集成在一起。
    下图给出了Batch Normalization的具体形式:
    batch normalization

Regularization

  1. $L_2$规则化: $\frac{1}{2}\lambda w^2$
    对于大数值的权重向量进行严厉的惩罚,倾向于更加分散的权重向量。

  2. $L_1$规则化: $\lambda |w|$
    具有稀疏性

  3. $L_1 \& L_2$混合规则化: $\lambda_1 |w| + \lambda_2 w^2 $
    Elastic net regularization

  4. Max norm constraints(最大范式约束):
    给每个神经元中权重向量的数量设定上限,并使用投影梯度下降来确保这一约束

  5. Dropout(随机失活):
    让神经元以超参数p的概率被激活或被设置为0
    这属于网络在前向传播中有随机行为的方法

Dropout
上图表示Dropout方法的具体形式,下面给出对应的代码逻辑:
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
""" Vanilla Dropout: Not recommended implementation (see notes below) """
p = 0.5 # probability of keeping a unit active. higher = less dropout
def train_step(X):
""" X contains the data """
# forward pass for example 3-layer neural network
H1 = np.maximum(0, np.dot(W1, X) + b1)
U1 = np.random.rand(*H1.shape) < p # first dropout mask
H1 *= U1 # drop!
H2 = np.maximum(0, np.dot(W2, H1) + b2)
U2 = np.random.rand(*H2.shape) < p # second dropout mask
H2 *= U2 # drop!
out = np.dot(W3, H2) + b3
# backward pass: compute gradients... (not shown)
# perform parameter update... (not shown)
def predict(X):
# ensembled forward pass
H1 = np.maximum(0, np.dot(W1, X) + b1) * p # NOTE: scale the activations
H2 = np.maximum(0, np.dot(W2, H1) + b2) * p # NOTE: scale the activations
out = np.dot(W3, H2) + b3

inverted dropout
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
Inverted Dropout: Recommended implementation example.
We drop and scale at train time and don't do anything at test time.
"""
p = 0.5 # probability of keeping a unit active. higher = less dropout
def train_step(X):
# forward pass for example 3-layer neural network
H1 = np.maximum(0, np.dot(W1, X) + b1)
U1 = (np.random.rand(*H1.shape) < p) / p # first dropout mask. Notice /p!
H1 *= U1 # drop!
H2 = np.maximum(0, np.dot(W2, H1) + b2)
U2 = (np.random.rand(*H2.shape) < p) / p # second dropout mask. Notice /p!
H2 *= U2 # drop!
out = np.dot(W3, H2) + b3
# backward pass: compute gradients... (not shown)
# perform parameter update... (not shown)
def predict(X):
# ensembled forward pass
H1 = np.maximum(0, np.dot(W1, X) + b1) # no scaling necessary
H2 = np.maximum(0, np.dot(W2, H1) + b2)
out = np.dot(W3, H2) + b3

Loss functions

  1. 分类问题:

    1) SVM : $L_i = \sum_{j\neq y_i} max(0, f_j - f_{y_i} + 1)$

    2) Softmax : $L_i = - log\frac{e^{f_{y_i}}}{\sum_j e^{f_j}}$

    3) 当样本的类别数据巨大时,需要使用Hierarchical Softmax

    4) 属性分类: 多标签/每个样本可能没有某个属性,属性之间不互相排斥
    可以为每个属性创建一个独立的二分类的分类器

  2. 回归问题
    $L_2$范式: $L_i = |f - y_i|^2_2$
    $L_1$范式: $L_i = |f - y_i|_1 = \sum_j |f_j - (y_i)_j|$

references

  1. CS231n:Neural Networks Part 2: Setting up the Data and the Loss
  2. CS231n (winter 2016) : Assignment1
  3. 知乎:CS231n课程笔记翻译:神经网络笔记 2

从这一节开始,课程重点:神经网络来了,本节主要讲一些神经网络中常用的损失函数,激活函数以及层次结构等。

Modeling one neuron

很多人都知道神经网络中基本单元是受人脑中的神经元的启发而设计的,所以,本节一开始通过人脑中的基本神经元-突触来揭示了其工作原理,以及到神经网络中基本单元的类比。

然后,介绍了几个基本的线性分类器 Binary Softmax classifierBinary SVM classifier

常用的激活函数:

sigmoid:
函数形式: $$\sigma(x)=\frac{1}{1+e^{-x}}$$
函数图像可见sigmoid function 和 sigmoid kernel
优点
对于神经元的激活频率有着良好的解释:从完全不激活(0)到在求和后的最大频率处的完全饱和的激活(1)
缺点

  1. 饱和会使得梯度消失
  2. 输出不是零中心的

tanh
函数形式: $$\tanh(x)=\tanh(\alpha x^T y+c) = 2\sigma(2x)-1$$
具有与sigmoid一样的性能,不过也有梯度会消失的缺点

ReLU (Rectified Linear Unit)
函数形式:
$$f(x) = \max(0, x)$$
函数图像:
ReLU
根据函数图像易知,当 $x <= 0$ 时,函数值为0;当 $x > 0$时,函数斜率为1.

优点

  1. 对随机梯度下降的收敛有巨大的作用
  2. 计算资源耗费少
    缺点
    在训练时,比较脆弱,并且可能“死掉”(这里有疑问,为什么会死掉?

Leaky ReLU
函数形式:

$$f(x)=\mathbb{I}(x<0) (\alpha x) + \mathbb{I}(x\geq 0) (x)$$

函数图像:
Leaky ReLU
根据函数图像,可以看出Leaky ReLU是对ReLU的一个改进,当 $x<=0$ 时,函数给出一个很小的负数梯度量

PReLU (Delving Deep into Rectifiers, Kaiming He, 2015)
把负区间上的斜率当作每个神经元中的一个参数来学习

Maxout
函数形式:
$$f(x) = \max(W_1^T x + b_1, W^T_2 x + b_2)$$

该方法是对ReLU和Leaky ReLU的一般化归纳
当 $W_1 = 0, b_1 = 0$ 时,就变成了ReLU
优点
拥有ReLU的优点(线性操作&不饱和),而没有他的缺点(死亡的ReLU单元)
缺点
每个神经元的参数数量增加了一倍,导致整体参数的数量激增。

Neural Network architectures

  1. 层的结构
    神经网络模型是通过层状无环结构组成,比如全连接层结构。
    其次,通常所说的几层神经网络是不连输入层的,比如下图为3层神经网络。
    3-layer NN

  2. 前向传播
    一般是先进行一个矩阵乘法,然后加上偏置并运用激活函数来实现。

  3. 表达能力
    给出任意连续函数 $f(x)$ 和任意 $\epsilon > 0$,均存在一个至少含1个隐层的神经网络 $g(x)$ (并且网络中有合理选择的非线性激活函数,比如Sigmoid),对于 $\forall x$,使得 $|f(x) - g(x)| < \epsilon$.

  4. 设置层的数量和尺寸
    隐层单元越多,网络的表达能力越强
    当出现Overfit时,应选择规则化而不是减少层数和单元数

references

  1. CS231n:Neural Networks Part 1: Setting up the Architecture
  2. CS231n (winter 2016) : Assignment1 这个作者自己总结的还是挺好的,值得参考,感谢博主!
  3. 知乎:CS231n课程笔记翻译:神经网络笔记1上
    知乎:CS231n课程笔记翻译:神经网络笔记1下

这一节主要介绍了反馈网络中的链式求导法则,非常的基础。

Simple expressions and interpretation of the gradient

这段通过一个简单的栗子来解释梯度的意义,其实在高数中有学过,物理意义是:一个函数在某一点沿着某个方向的梯度方向便是上升最快的地方,所以,要使得目标函数值能够下降最快,便是沿着负梯度方向就好了。
课程中的解释是通过具体的数字来体现的:
函数:$$f(x, y) = xy$$
所以,该函数在 $x, y$ 方向上的梯度是 $$\frac{\partial f}{\partial x} = y;\quad \frac{\partial f}{\partial y} = x$$
当取$x=4, y=-3$时,函数$f(x, y) = -12$,且在 $x$ 上的导数是$\frac{\partial f}{\partial x} = -3$,这表明当我们给 $x$ 值增加一个很小的值,目标函数值就会下降(导数值是负的),且下降的幅度为 $3$。所以,函数在某个变量上的导数告诉了我们整个函数对于这个变量的敏感程度。
课程中还举了一个加法和max的例子,这里就不赘述了。

Compound expressions with chain rule

主要介绍链式法则。
函数:
$$f(x, y, z) = (x + y)z$$
将这个函数拆分成两个表达式:$q = x + y;\quad f = qz$,接着,分别对这两个子表达式中变量进行求导:$\frac{\partial f}{\partial q} = z; \quad \frac{\partial f}{\partial z} = q$, $\frac{\partial q}{\partial x} = 1; \quad \frac{\partial q}{\partial y} = 1$.那么要求函数$f$对$x$的导数便易得:$\frac{\partial f}{\partial x} = \frac{\partial f}{\partial q} \frac{\partial q}{\partial x}$。
code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# set some inputs
x = -2; y = 5; z = -4
# perform the forward pass
q = x + y # q becomes 3
f = q * z # f becomes -12
# perform the backward pass (backpropagation) in reverse order:
# first backprop through f = q * z
dfdz = q # df/dz = q, so gradient on z becomes 3
dfdq = z # df/dq = z, so gradient on q becomes -4
# now backprop through q = x + y
dfdx = 1.0 * dfdq # dq/dx = 1. And the multiplication here is the chain rule!
dfdy = 1.0 * dfdq # dq/dy = 1

Intuitive understanding of backpropagation

对于反馈网络的理解,课程中是通过网络中每个门(gate)来解释的,每个门在接受输入后,完成两件事:1.给出输出;2.给出关于输出的,输入的局部梯度。
所以,整个反馈网络都是通过着一些个门来互相交流的,比如他们是想要更高或是更低的输出,最终对整个函数的结果产生影响。

后面课程中有举了两个复杂一点的函数例子,这里就不搬过来了。

Patterns in backward flow

课程介绍了三种门的特性:
add gate: distribute gradients equally to all its inputs
max gate: routes the gradients to the higher input
multiply gate: take the input activations, swap them and multiplies by its gradient

对样本数据预处理的理解:
一般函数中都会有 $W^T x_i$ , 由于这样乘法的形式,如果给样本数据 $x_i * 1000$, 那么权重 $W$ 的梯度就会增加1000倍,变化率是很大的了,此时,就需要更低的学习率来中和这样的影响,所以,预处理要将样本数据进行规范化,以便不再出现上面奇怪的问题。

reference

  1. CS231n: Backpropagation, Intuitions

这一节主要介绍一种优化方法,随机梯度下降,用于求解前面章节提到的目标函数中的权重矩阵$W$.

Visualizing the loss function

这里主要通过一些简单的例子来表明,我们所要求解的目标函数是一个凸问题,通过形象化的图形来体会优化的过程。同时,课程中也提到如果在神经网络中,目标函数就不再是凸的了,所以需要新的求解方法。

Optimization

首先限定一个最大迭代步数,然后在每一次迭代中都将随机的$W$值代入求得目标函数值,并记录下使得目标函数值取得当前最小的$W$作为最终的输出

code:

1
2
3
4
5
6
7
for num in xrange(1000):
W = np.random.randn(10, 3073) * 0.0001 # generate random parameters
loss = L(X_train, Y_train, W) # get the loss over the entire training set
if loss < bestloss: # keep track of the best solution
bestloss = loss
bestW = W
print 'in attempt %d the loss was %f, best %f' % (num, loss, bestloss)

对上面方法的一个改进,就是不是在每次的迭代中都给$W$赋随机值,而是根据初始赋随机值进行微调,如果能够使得目标函数值下降,则记录下该微调之后的$W$,直到迭代步数达到设定的值。

code:

1
2
3
4
5
6
7
8
9
10
W = np.random.randn(10, 3073) * 0.001 # generate random starting W
bestloss = float("inf")
for i in xrange(1000):
step_size = 0.0001
Wtry = W + np.random.randn(10, 3073) * step_size
loss = L(Xtr_cols, Ytr, Wtry)
if loss < bestloss:
W = Wtry
bestloss = loss
print 'iter %d loss is %f' % (i, bestloss)

Strategy 3: Following the gradient

显然,策略2已经很接近通用的梯度下降方法了,唯一的区别是,我们在每一步迭代中都是取使目标函数下降最大的方向进行优化的,而要想能够找到使得目标函数下降最大的方向,就需要用到梯度了。

Computing the gradient

对于梯度的计算,课程中提供了两种方法

Numerically with finite differences

标签:a slow, approximate,but easy way

公式:
$$\frac{d f(x)}{d x}=\lim_{x\to 0} \frac{f(x+h)-f(x)}{h}$$

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fx = f(x) # evaluate function value at original point
grad = np.zeros(x.shape)
h = 0.00001
# iterate over all indexes in x
it = np.nditer(x, flags=['multi_index'], op_flags=['readwrite'])
while not it.finished:
# evaluate function at x+h
ix = it.multi_index
old_value = x[ix]
x[ix] = old_value + h # increment by h
fxh = f(x) # evalute f(x + h)
x[ix] = old_value # restore to previous value (very important!)
# compute the partial derivative
grad[ix] = (fxh - fx) / h # the slope
it.iternext() # step to next dimension

Analytically with calculus

标签: a fast, exact but more error-prone way

以SVM损失函数在某个样本下的形式为例:
$$L_i = \sum_{j\neq y_i} \left [\max(0, w_j^T x_i - w_{y_i}^T x_i + \Delta) \right ]$$
计算上式对 $w_{y_i}$ 的梯度:
$$\nabla_{w_{y_i}}L_i = -\left (\sum_{j\neq y_i} \mathbb{I} (w_j^T x_i - w_{y_i}^T x_i + \Delta > 0)\right )x_i$$
计算上式对 $j\neq y_i$ 的 $W_j$ 的梯度:
$$\nabla_{w_j}L_i = \mathbb{I} (w_j^T x_i - w_{y_i}^T x_i + \Delta > 0)x_i$$

Gradient Descent

梯度下降方法的主要思路是,在梯度方向上,进行某一步长的移动以使得目标函数呈不增的趋势。

code:

1
2
3
while True:
weights_grad = evaluate_gradient(loss_fun, data, weights)
weights += - step_size * weights_grad # perform parameter updat

Mini-batch gradient descent
当数据集非常的大时,机器资源可能不能一次性的加载进所有的数据,所以可以每次只选择其中的一小部分进行处理。

code:

1
2
3
4
while True:
data_batch = sample_training_data(data, 256) # sample 256 examples
weights_grad = evaluate_gradient(loss_fun, data_batch, weights)
weights += - step_size * weights_grad # perform parameter update

对于Mini-batch的大小,通常不用交叉验证的方式来选择,通常是根据经验提前设定的(根据计算资源而定):$[32, 64, 128,…]$,通常选择的是2的倍数,因为这符合计算机的二进制计数原理。

Stochastic Gradient Descent (SGD)
当Mini-batch gradient descent取极限时,即每次只取所有样本中的一个样例用于训练。但是由于在实践中发现,计算100个样本的梯度往往要优于计算某一个样本100次所得到的权重矩阵,所以Mini-batch gradient descent较为常用,而SGD有时也指Mini-batch gradient descent。

reference

  1. CS231n: Optimization: Stochastic Gradient Descent

在第一节的课程中主要介绍了KNN方法,由于knn是lazy Learning,主要有两个缺点:要记住所有的训练点;将测试点与所有训练点进行比较,为了克服这些缺点,通常会选择其他的分类方法,本节介绍了SVM和softmax classifier.

对线性分类器的解释

线性分类器的形式:
$$f(x_i;W,b)=Wx_i + b$$

结果向量 $f(x_i;W,b)$ 中值的大小

上图表示判定样例$x_i$是属于各种类别的得分情况,向量$f(x_i;W,b)$的值来看此样例小猫被判定到了狗狗的类别中,所以分类错误,需要进一步的学习。

权重矩阵$W$的每一行都是一个template

上图是通过将权重矩阵$W$中每一行reshape后画出来的图像,我们其实可以粗略的判断出一些类别,比如第二幅图是一辆偏粉红色的小汽车,表明,我们数据集中的小汽车颜色可能都偏红色,倒数第三章是有左右两个头的马儿,其实这跟训练数据集有关,可能数据集中包含了两个方向的马儿图片。
在分类时,其实是将样例与template进行内积运算以判断与template的距离,与相近则值越大。

损失函数

多类分类SVM

损失函数:
$$L_i = \sum_{j\neq y_i} \max(0, S_j - S_{y_i} + \Delta); \quad S_j = f(x_i, W)_j \tag 1$$

这里损失函数想要表达的是:每一个错误类别的得分至少要比正确类别的得分小$\Delta$, 另外,这里的$\Delta$其实有点像经典SVM推导中的函数间隔,由于可以通过$W$的大小来调节最终值得大小,所以这里可以将$\Delta$设为1。

这里的损失函数是hinge loss,不过与我们常见的SVM中的形式不太一样,
$$L_i = \max(0, 1- y_i f(x_i))\tag 2$$
一方面,公式(1)可以用于多类分类,而公式(2)用于多类分类需要使用其他策略,比如one-VS-all或者all-VS-all。

规则化:
$$R(W)=\sum_k\sum_l W_{k,l}^2$$

所以,多类分类最终的目标函数为:
$$\min L = \frac{1}{N}\sum_i L_i + \lambda R(W)\tag 3$$

Softmax 分类器

主要将公式(3)中的hinge loss换成cross-entropy 损失(交叉熵损失):
$$L_i = - \log(\frac{e^{f_{y_i}}}{\sum_j e^{f_j}}) = -f_{y_i} + \log\sum_j e^{f_j} \tag 4$$

其中$f_j(z) = \frac{e^{z_j}}{\sum_k e^{z_k}}$ 称为Softmax function,所以将这种损失函数命名为Softmax classifier。

Softmax classifier其实是binary Logistic regression classifier 在Multiple class上的一个泛化。

Softmax分类器的优点主要是能够给出分类类别的概率。

对于Softmax 分类器的解释主要有两种:

  1. information theory view
    在“真实”分布p和估计分布q之间的交叉熵定义如下:
    $$H(p, q)=-\sum_x p(x) \log q(x)$$

    因此,Softmax分类器所做的就是最小化在估计分类概率(就是上面的$e^{f_{y_i}}/\sum_j e^{f_j}$)和“真实”分布之间的交叉熵,在这个解释中,“真实”分布就是所有概率密度都分布在正确的类别上(比如: $p=[0,\cdots, 1,\cdots, 0]$中的$y_i$的位置就有一个单独的1)。
    交叉熵损失函数“想要”预测分布的所有概率密度都在正确分类类别上。

  2. probabilistic interation
    Softmax classifier将输出向量$f$中的评分值解释为没有归一化的对数概率,所以,先对$f$进行指数操作得到没有归一化的概率,然后,在进行归一化得到相应的概率值。

从数值上进行分析: 首先 $e^{f_{y_i}}/\sum_j e^{f_j}$ 必定属于 $(0, 1]$,要想目标函数尽量的小,那么 $\log()$ 就要尽量的大,由于 $\log$ 函数是单调递增的,所以即要求 $e^{f_{y_i}}/\sum_j e^{f_j}$ 尽量的大,而这正符合正确分类的要求。

Logistic Regression

对于Logistic Regression的讲解,西瓜书上讲的挺清楚的,这里将一个简单的思路记录写下来以促进理解。
首先,对于一般的二类分类问题,输出标记为 ${0, 1}$, 而通常的线性回归模型产生的预测值为实值,我们需要将这些实值转成 $0/1$ 值,当然,最理想的便是“单位阶跃函数”

$$y=
\begin{cases}
0, z < 0; \
0.5, z = 0; \
1, z > 0,
\end{cases}$$

但是,单位阶跃函数不连续的性质,在求解的时候会很不方便,所以就需要寻找一个替代函数,并希望其能够单调可微。这时便需要用到对数几率函数。
对数几率函数的形式为:
$$y=\frac{1}{1+ e^{-(w^Tx + b)}}\tag 5$$
这其实是Sigmoid函数的形式。该函数对应的模型称为Logistic Regression。

将公式(5)进行简单的变化得到:
$$\ln\frac{y}{1-y}=w^Tx + b$$
这里将 $y$ 视为样本 $x$ 作为正例的可能性,则 $1-y$ 是其反例的可能性,两者的比值为 $y/(1-y)$ 称为“几率”(odds),反映了 $x$ 作为正例的相对可能性。对几率取对数则得到”对数几率”(log odds),所以,Logistic regression 又被称为“对数几率回归”。

references

  1. cs231n: Linear classification: Support Vector Machine, Softmax
  2. CS231n课程笔记翻译:线性分类笔记(下)
  3. 机器学习. 周志华 对数几率回归章节

在迭代型算法的优化问题中,我们经常会看到用Armijo Rule来更新步长,找到一个可行点进入下一次迭代。下面将我对Armijo的理解整理下来。

Goldstein-Armijo Rule

我们这里以梯度方法为例:

初始点 $x_0 \in R^n$
迭代 : $ x_{k+1} = x_k - h_k f’(x_k), k=0,1,… $

这里$h_k$表示步长(大于0),$f’(x_k)$表示函数$f(x)$在$x_k$这一点的梯度方向。前面为负表示负梯度方向为函数下降最快的方向,至于为什么在这一点会下降最快,其实是有很好的理论证明的,后面有时间整理出来。
那么,对于步长的确定可以有很多方法,最简单的一种便是提前预定义好:
$$h_k = h > 0$$
$$h_k = \frac{h}{\sqrt{k+1}}$$
这种方法在凸优化的框架下使用较多,主要由于凸优化函数的变化趋势是可预测的。
另外还有一种非常理想化的方法:
$$h_k = arg \min_{h\geq0}f(x_k - h f’(x_k))$$
显然,这种方法在实际的运用中属于空中楼阁,并没有可操作性。
下面最最常用的便是Armijo Rule了:

Find $x_{k+1} = x_k - h f’(x_k)$ such that

$$\alpha <f’(x_k), x_k - x_{k+1}> \quad \leq \quad f(x_k) - f(x_{k+1}) \tag 1$$

$$\beta <f’(x_k), x_k - x_{k+1}> \quad \geq \quad f(x_k) - f(x_{k+1}) \tag 2$$
where $0 < \alpha < \beta < 1$ are some fixed parameters

对于这个规则,可能咋看并不能理解他的意图,下面通过一段证明来看一下这个规则的作用。

证明

假设有如下问题
$$\min_{x\in R^n} f(x)$$
其中$f\in C^{1,1}_L(R^n)$。并且,我们这里假设函数有下界。

这里$f\in C^{1,1}_L(R^n)$表示函数$f(x)$在$R^n$上是一阶连续可微的,并且其一阶导满足Lipschitz 连续性,参数为L,具体的公式如下
$$|f(y)-f(x)-<f’(x), y-x>| \quad \leq \quad \frac{L}{2} ||y-x||^2$$

对于一个gradient step,我们有

\begin{align}
f(y) & \leq f(x) + <f’(x), y-x> + \frac{L}{2}|y-x|^2 \\
& = f(x) - h|f’(x)|^2 + \frac{h^2}{2}L|f’(x)|^2 \\
& = f(x) - h(1-\frac{h}{2}L)|f’(x)|^2 \tag 3
\end{align}

所以,为了使得我们的目标函数值有尽大程度的减小,我们需要求解下面的一维问题:
$$\Delta(h) = -h(1-\frac{h}{2}L) \to \min_h$$
对上式求导,得到$\Delta’(h)=hL-1=0$,所以$h^* = \frac{1}{L}$,由于$\Delta’’(h)=L \gt 0$,所以此时取得最小值。这样,将其代入上式,我们就能够得到单步梯度下降,目标函数值至少下降多少的形式:
$$f(y)\leq f(x)-\frac{1}{2L}|f’(x)|^2 \tag 4$$

下面,我们来看一下Armijo Rule规定的两个式子与这目标函数值最小下降之间的关系。
首先,令$x_{k+1} = x_k - h_k f’(x_k)$,对于固定步长策略$h_k = h$,我们有
$$f(x_k) - f(x_{k+1}) \geq h(1-\frac{h}{2}L)|f’(x)|^2$$
所以当我们选择$h_k = \frac{2\alpha}{L}, \alpha \in (0, 1)$时,有

$$f(x_k) - f(x_{k+1}) \geq \frac{2}{L}\alpha (1-\alpha)|f’(x)|^2 \tag 5$$

显然,当$\alpha = \frac{1}{2}$时,取得最大值,即为前面(4)式等价。
接着,我们考虑Armijo Rule提到的两个式子:
首先,我们考虑公式(2),有
$$f(x_k)-f(x_{k+1}) \quad \leq \quad \beta <f’(x_k), x_k-x_{k+1}>\quad = \quad\beta h_k |f’(x)|^2$$
结合公式(3),我们有
$$h_k \geq \frac{2}{L}(1-\beta) \tag 6$$
接着,我们考虑公式(1),有

$$f(x_k)-f(x_{k+1}) \quad \geq \quad \alpha <f’(x_k), x_k-x_{k+1}>\quad = \quad\alpha h_k |f’(x)|^2$$

结合不等式(6),我们有

$$f(x_k)-f(x_{k+1}) \quad \geq \quad \frac{2}{L}\alpha(1-\beta)|f’(x_k)|^2 \tag 7$$

结合公式(4)(5)(7),容易得到
$$\frac{2}{L}\alpha(1-\beta) \leq \frac{2}{L}\alpha(1-\alpha) \leq \frac{1}{2L}, 0\leq \alpha \leq \beta \leq 1$$
所以,这表明对于给定的$\alpha,\beta$,只要满足公式(1)(2),就至少有公式(7)的下降程度,也就更趋近于最大下降(相当于满足了我们期望的下降)。

reference

[1] : introductory lectures on convex optimization: a basic course(26页), Yurii Nesterov

LibSVM是台大林智仁教授开发的专门用于求解各种支持向量机问题的工具包,目前已经有Python、MATLAB、Java等平台下的工具包。其实很早就有听说这个工具包,最近要实现一个对比实验需要用到所以终于有机会感受一下她的强大了。

下面简单介绍几个libsvm中常用的命令:
svmtrain
svmpredict
confusionmat

svmtrain

1
model = libsvmtrain(training_label_vector, training_instance_matrix [, 'libsvm_options']);

svmpredict

1
2
[predicted_label, accuracy, decision_values/prob_estimates]
    = libsvmpredict(testing_label_vector, testing_instance_matrix, model [, 'libsvm_options']);

svmtrain参数设置

options:

  • -s svm_type : set type of SVM (default 0)

    0 – C-SVC

    1 – nu-SVC

    2 – one-class SVM

    3 – epsilon-SVR

    4 – nu-SVR

  • -t kernel_type : set type of kernel function (default 2)

    0 – linear: $u’*v$

    1 – polynomial: $(gamma * u^T * v + coef0)^{degree}$

    2 – radial basis function: $exp(-gamma*|u-v|^2)$

    3 – sigmoid: $ tanh(gamma * u^T * v + coef0)$

    4 – precomputed kernel (kernel values in training_instance_matrix)

  • -d degree : set degree in kernel function (default 3)

  • -g gamma : set gamma in kernel function (default 1/num_features)

  • -r coef0 : set coef0 in kernel function (default 0)

  • -c cost : set the parameter C of C-SVC, epsilon-SVR, and nu-SVR (default 1)

  • -n nu : set the parameter nu of nu-SVC, one-class SVM, and nu-SVR (default 0.5)

  • -p epsilon : set the epsilon in loss function of epsilon-SVR (default 0.1)

  • -m cachesize : set cache memory size in MB (default 100)

  • -e epsilon : set tolerance of termination criterion (default 0.001)

  • -h shrinking: whether to use the shrinking heuristics, 0 or 1 (default 1)

  • -b probability_estimates: whether to train a SVC or SVR model for probability estimates, 0 or 1 (default 0)

  • -wi weight: set the parameter C of class i to weight*C, for C-SVC (default 1)

对应的中文解释2

  • -s svm类型:SVM设置类型(默认0)

    0 — C-SVC;

    1 – v-SVC;

    2 – 一类SVM;

    3 — e-SVR;

    4 — v-SVR

  • -t 核函数类型:核函数设置类型(默认2)

    0 – 线性核函数:$u’*v$

    1 – 多项式核函数:$(gamma * u^T * v + coef0)^{degree}$

    2 – RBF(径向基)核函数:$exp(-gamma*|u-v|^2)$

    3 – sigmoid核函数:$ tanh(gamma * u^T * v + coef0)$

    4 - 预先计算好的核矩阵 (核矩阵取代training_instance_matrix)

  • -d degree:核函数中的degree设置(针对多项式核函数)(默认3)

  • -g r(gamma):核函数中的gamma函数设置(针对多项式/rbf/sigmoid核函数)(默认1/k,k为总类别数)

  • -r coef0:核函数中的coef0设置(针对多项式/sigmoid核函数)((默认0)

  • -c cost:设置C-SVC,e -SVR和v-SVR的参数(损失函数)(默认1)

  • -n nu:设置v-SVC,一类SVM和v- SVR的参数(默认0.5)

  • -p p:设置e -SVR 中损失函数p的值(默认0.1)

  • -m cachesize:设置cache内存大小,以MB为单位(默认40)

  • -e eps:设置允许的终止判据(默认0.001)

  • -h shrinking:是否使用启发式,0或1(默认1)

  • -wi weight:设置第几类的参数C为weight*C (C-SVC中的C) (默认1)

  • -v n: n-fold交互检验模式,n为fold的个数,必须大于等于2

svmtrain输出model的含义

libsvmtrain函数返回训练好的SVM分类器模型,可以用来对未知的样本进行预测。这个模型是一个结构体,包含以下成员2

  • -Parameters: 一个5 x 1的矩阵,从上到下依次表示:

    -s SVM类型(默认0);

    -t 核函数类型(默认2)

    -d 核函数中的degree设置(针对多项式核函数)(默认3);

    -g 核函数中的r(gamma)函数设置(针对多项式/rbf/sigmoid核函数) (默认类别数目的倒数);

    -r 核函数中的coef0设置(针对多项式/sigmoid核函数)((默认0)

  • -nr_class: 表示数据集中有多少类别,比如二分类时这个值即为2。

  • -totalSV: 表示支持向量的总数。

  • -rho: 决策函数wx+b中的常数项的相反数(-b)。

  • -Label: 表示数据集中类别的标签,比如二分类常见的1和-1。

  • -sv_indices: 表示支持向量对应的样本索引

  • -ProbA: 使用-b参数时用于概率估计的数值,否则为空。

  • -ProbB: 使用-b参数时用于概率估计的数值,否则为空。

  • -nSV: 表示每类样本的支持向量的数目,和Label的类别标签对应。如Label=[1; -1],nSV=[63; 67],则标签为1的样本有63个支持向量,标签为-1的有67个。

  • -sv_coef: 表示每个支持向量在决策函数中的系数。

  • -SVs: 表示所有的支持向量,如果特征是n维的,支持向量一共有m个,则为m x n的稀疏矩阵。

另外,如果在训练中使用了-v参数进行交叉验证时,返回的不是一个模型,而是交叉验证的分类的正确率或者回归的均方根误差。

svmpredice输出含义

  • -predicted_label:第一个返回值,表示样本的预测类标号。

  • -accuracy:第二个返回值,一个3 x 1的数组,表示分类的正确率、回归的均方根误差、回归的平方相关系数。

  • -decision_values/prob_estimates:第三个返回值,一个矩阵包含决策的值或者概率估计。对于n个预测样本、k类的问题,如果指定“-b 1”参数,则n x k的矩阵,每一行表示这个样本分别属于每一个类别的概率;如果没有指定“-b 1”参数,则为n x k*(k-1)/2的矩阵,每一行表示k(k-1)/2个二分类SVM的预测结果。

confusionmat

1
C = confusionmat(testLabel, predLabel)

输出的是混淆矩阵

运用中遇到的一些问题

precomputed kernel

在svmtrain的参数中,对于核函数类型的选择,参数4比较特殊,是我们自己计算好核矩阵给libsvm来求解,其中有两个注意点:

  1. 核矩阵的位置–取代原来训练实例矩阵的位置

  2. 核矩阵需要处理一下:

To use precomputed kernel, you must include sample serial number as the first column of the training and testing data.

上面的话用代码来表示:

1
2
3
K = getKernel(X, Y, options);
K = [(1:size(K, 1))', K];
model = svmtrain(trainLabel, K, '-t 4');

libsvmpredict的工作原理

在应用中,有时我们只需要libsvmtrain的功能,在得到特征向量的信息之后,根据不同的需求来求解精度,而不再需要使用libsvmpredict的功能。这样我们就需要了解通过libsvmtrain求得得model来实现predict得功能。

model的信息上面已经说明了,我们只需要利用好sv得信息:model.sv_indices, model.sv_coef, model.SVs。另外需要注意的是,model.sv_coef是支持向量的系数,相当于alpha .* y_train,所以,我们在求解时就不需要再乘y_train了,具体的形式为:

$$predLabel = sign(\sum^n_{i=1} w_i K(x_i, x)) + b$$

  • 当输入libsvmtrain的是原始样本信息(而不是kernel matrix)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    model = libsvmtrain(y_train, x_train, '-s 0 -t 2 -c 1.2 -g 2.8');
    [predictLabel, accuracy, prob_estimate] = libsvmpredict(y_test, x_test, model);
    b = -model.rho;
    sv_mat_sparse = model.SVs;
    sv_mat_full = full(sv_mat_sparse)';
    gamma = model.Parameters(4);
    tmp = @(x, y) (bsxfun(@plus, sum(x.^2, 1).', sum(y.^2, 1)) - 2 * (x' * y));
    RBF = exp(-gamma * tmp(sv_mat_full, x_test));
    pred_label = model.sv_coef' * RBF + b;
    accuracy_self = mean(sign(pred_label') == y_test);
  • 当输入libsvmtrain的是precomputed kernel matrix

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    train_kernel_mat = exp( -gamma * tmp(x_train, x_train));
    train_kernel_tilde = [(1:size(train_kernel_mat, 1))', train_kernel_mat];
    model = libsvmtrain(y_train, train_kernel_tilde, '-t 4');
    test_kernel_mat = exp(-gamma * tmp(x_train, x_test));
    test_kernel_tilde = [(1:size(test_kernel_mat, 1))', test_kernel_mat];
    [predictLabel, accuracy, prob_estimate] = libsvmpredict(y_test, test_kernel_tilde, model);
    b = -model.rho;
    sv_mat = x_train(:, model.sv_indices');
    gamma = model.Parameters(4);
    RBF = exp(-gamma * tmp(sv_mat, x_test));
    pred_label = model.sv_coef' * RBF + b;
    accuracy_self = mean(sign(pred_label') == y_test);

我们会发现accuracy_selfaccuracy的值是一样的。

reference

1 : 林智仁Libsvm主页
2 : LIBSVM在Matlab下的使用
3 : using precomputed kernels with libsvm

两个quad空格 a \qquad b $a \qquad b$ 两个m的宽度
quad空格     a \quad b $a \quad b$ 一个m的宽度
大空格       a\ b $a\ b$ 1/3m宽度
中等空格     a\;b $a\;b$ 2/7m宽度
小空格       a\,b $a\,b$ 1/6m宽度
没有空格     ab $ab\,$
紧贴         a\!b $a\!b$ 缩进1/6m宽度(在hexo中需要写成a\\!b)

approximately the width of an “M” in the current font

m 代表当前字体下接近字符‘M’的宽度

由于写的博客中有很多公式,在线下编辑的时候都能正常显示,可是发布了之后出现了各种蛋疼的效果,折腾了好久,总结下来以备忘。

多行公式显示

\begin{align} \\
\max_{w,b} \quad & \gamma \\
s.t. \quad &y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})\geq \gamma, i=1,2,…,N
\end{align}

1
2
3
4
5
code:
\begin{align} \\\\
\max_{w,b} \quad & \gamma \\\\
s.t. \quad &y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})\geq \gamma, i=1,2,...,N
\end{align}

注意,这里在最后不能加 $ ,加上之后会显示不正常,然后每一行公式的最后要加四个 \ ,我想原因是hexo中对于 \ 是需要通过 \ 转义的,所以两个 \\经过转义后等于一个 \
另外,对于绝对值的写法在这里也失效了,只能简单粗暴的用四个 | 来解决了

对于下标的转义

$$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^N\alpha_i y_i (w \cdot x_i + b) + \sum_{i=1}^N\alpha_i$$

1
2
code:
$$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum\_{i=1}^N\alpha\_i y\_i (w \cdot x\_i + b) + \sum\_{i=1}^N\alpha\_i$$

这里出现了两个\sum\_{i=1}^N如果不对下标进行转义,写成\sum_{i=1}^N,就不能正常显示,不知道原因。只能先加上解决问题了

对于$*$上标的转义

$$\lambda^*$$

1
2
code:
$$\lambda^\*$$

SVM是非常经典的分类方法,在李航的《统计学习方法》中给出基本模型是定义在特征空间上间隔最大的线性分类器,学习策略是间隔最大化,学习算法是求解凸二次规划的最优化算法。详细的推导过程书上写的很明确了,现在我自己再梳理一下,并穿插就一些疑问尝试给出自己的答案。

首先,SVM的一种思路就是间隔最大化,对于间隔有函数间隔与几何间隔,由于函数间隔并不唯一确定,所以选择几何间隔,得到原始优化目标函数

\begin{align} \\
\max_{w,b} \quad & \gamma \\
s.t. \quad &y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})\geq \gamma, i=1,2,…,N
\end{align}

根据函数间隔与几何间隔之间的关系,可以将约束中的$||w||$去掉

\begin{align} \\
\max_{w,b} \quad &\frac{\hat \gamma}{|w|} \\
s.t. \quad &y_i(w\cdot x_i+b)\geq \hat \gamma, i=1,2,…,N
\end{align}

取$\hat \gamma = 1$并作简单变换得到

\begin{align} \\
\min_{w,b} \quad &\frac{1}{2}|w|^2 \\
s.t. \quad &y_i(w\cdot x_i + b) - 1 \geq 0,i=1,2,…,N
\end{align}

这样,我们就得到了线性可分SVM的基本优化目标函数。接下来,是运用Lagrange对偶化来求解对偶问题。

这里Lagrange对偶化有一个对偶间隔的问题,当目标函数和约束函数均是凸的情况下,当对偶问题的解满足KKT条件时,对偶间隔为0,即对偶问题与原问题等价。所以我们可以放心大胆的去求对偶问题了。注意,这里的KKT条件并不是SVM中独有的,应该是针对Lagrange对偶化的一个条件。但是,由于Lagrange对偶化是针对凸函数而言的,当核函数不定时,目标函数不再是凸函数,所以也就不能运用Lagrange对偶化来求解了,因为存在对偶间隔。

Lagrange对偶化后得到Lagrange函数

$$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^N\alpha_i y_i (w \cdot x_i + b) + \sum_{i=1}^N\alpha_i$$

对$w,b$求偏导,并代入得到

\begin{align} \\
\min_\alpha \quad &\frac{1}{2}\sum_{i=1}^N\sum_{i=1}^N \alpha_i \alpha_j y_i y_j (x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\
s.t. \quad &\sum_{i=1}^N \alpha_i y_i = 0 \\
&\alpha_i \geq 0, i= 1,2,…,N
\end{align}

到了这里,SVM的对偶优化目标就得到了。但是目前的模型容易过拟合,并且当样本数据不能够线性划分时,需要引入软间隔,此时原问题的优化目标为

\begin{align}
\min_{w,b} \quad &\frac{1}{2}||w||^2 + C\sum_{i=1}^N \xi_i \\
s.t. \quad &y_i(w\cdot x_i + b) \geq 1 - \xi_i ,i=1,2,…,N \\
&\xi_i \geq 0, i=1,2,…,N
\end{align}

同样运用Lagrange对偶化后得到对应的对偶优化目标

\begin{align}
\min_\alpha \quad &\frac{1}{2}\sum_{i=1}^N\sum_{i=1}^N \alpha_i \alpha_j y_i y_j (x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\
s.t. \quad &\sum_{i=1}^N \alpha_i y_i = 0 \\
&0 \leq \alpha_i \leq C, i= 1,2,…,N
\end{align}

然后根据求解得到最优的$\alpha^*$,根据公式就能够求得$w^*$,$b^*$了。这里$w^*$是唯一的,而$b^*$不是。
到这里,SVM的通过间隔最大化的大体推导思路就结束了。接下来需要关注的就是对于支持向量的讨论了,在《统计学习方法》的P113有较为详细的分析,讲的非常好,这里作简要分析。
软间隔支持向量

根据软间隔支持向量的图,可以看出主要有四种情况:

  • $\alpha_i^* \lt C$,则 $\xi_i = 0$,且支持向量$x_i$恰好落在间隔边界上(即图中的虚线上)

    在Lagrange对偶化的过程中,有$C-\alpha_i-\mu_i = 0$这样一个约束,由于$\alpha_i^* \lt C$,那么有$\mu_i^* > 0$,那么表明对应的$\xi_i = 0$(KKT条件),即表明对于这一样本点,对于间隔超平面偏差为0.

  • $\alpha_i^* = C, 0 <\xi_i< 1$,则该样本分类正确,且落在间隔边界与分离超平面之间

  • $\alpha_i^* = C, \xi_i = 1$, 则该样本落在分离超平面上
  • $\alpha_i^* = C, \xi_i > 1$, 则该样本位于分离超平面误分的一侧。

到这里线性SVM的基本知识点就差不多了。然后,在《统计学习方法》和西瓜书《机器学习》中都有降到对于SVM的另外一种解释。就是损失函数+正则化项的目标函数。

$$\min_{w,b} [1-y_i(w\cdot x_i + b)]_+ + \lambda ||w||^2$$

在西瓜书中明确说了这一模型与前面说的硬间隔最大化的原问题模型是等价的。其中,损失函数是一个非凸和非连续的函数,所以通常就选择一种替代损失函数,有hinge loss,指数损失, 对率损失。后一项正则化项可以根据需求来选择不同的范数,在间隔最大化的思路中,正则化项就选择的是$L_2$范数,这倾向于给出更多的支持向量点,而需要稀疏的支持向量时,可以选择$L_0, L_1$范数,其中,$L_0$范数会导致目标函数非凸,这样就又变成一个新的SVM问题—非凸SVM的求解。

对于损失函数,通常选择的是hinge loss,一个很重要的点是它也能够带来稀疏的支持向量点。

接下来,就是核函数的引入了,其实做法很简单,就是将样本内积换成核函数的形式,其他的都没有改动。

\begin{align}
\min_\alpha &\frac{1}{2}\sum_{i=1}^N\sum_{i=1}^N \alpha_i \alpha_j y_i y_j K(x_i\cdot x_j) - \sum_{i=1}^N \alpha_i \\
s.t. &\sum_{i=1}^N \alpha_i y_i = 0 \\
&0 \leq \alpha_i \leq C, i= 1,2,…,N
\end{align}

其实对于核函数的理解需要了解再生核希尔伯特空间的一些具体性质(比如为什么$K(x_i, x_j)$就能够表示样本映射到特征空间(Hilbert空间)后的内积,这其实就是再生核的性质,具体的可以参考再生核希尔伯特空间的介绍)
最后,就是对这个优化问题的求解了,经典的快速算法就是SMO算法,可以参考SMO算法实现

参考

  1. 李航老师的统计学习方法
  2. 周志华老师的机器学习