Machine Learning Week07

Posted on Edited on In Views: Symbols count in article: 3.1k Reading time ≈ 3 mins.

Support Vector Machines 支持向量机

Large Margin Classification

  1. Optimization Objective 优化目标

    • 在复杂非线性方程的学习上有优势。

    • image-20201206123628670
    • image-20201206124245802

      注：实际上在训练代价函数时，分界线为-1，1

  2. Large Margin Intuition

    • 代价函数： \[ \min _{\theta} C \sum_{i=1}^{m}\left[y^{(i)} {\operatorname{cost}_{1}\left(\theta^{T} x^{(i)}\right)}+\left(1-y^{(i)}\right) \operatorname{cost}_{0}\left(\theta^{T} x^{(i)}\right)\right]+\frac{1}{2} \sum_{i=1}^{n} \theta_{j}^{2}\\ if\ y=1, we\ want\ \theta^{T} x \geq 1\ (not\ just \left.\geq 0\right)\\ if\ y=0, we\ want\ \theta^{T} x \leq-1\ (not\ just<0 ) \]

    • SVM也被叫做大间距分类器，因为它尽量用最大间距分类样本，使得SVM更具有鲁棒性

    • 其中正则化参数C不适合设置得过大，因为这会使得一些异常值（outliner) 会使得分类向异常值产生比较大得偏差，这就类似与逻辑回归里过小的λ 。

  3. Mathematics Behind Large Margin Classification

    • 向量内积：\(\lVert u \rVert\)表明u的范数，即u向量的长度。\(u^Tv=p\cdot\lVert u \rVert\), p 是v在u上的投影长度

    • 本图演示了为什么这种方式可以最小化θimage-20201206171424283

      注：这里决策边界和θ是具有垂直关系的

    • 这里最小化θ范数等价于最大化所有的p，即最大化所有点到决策边界的margin。

    • 即使\(\theta_0\ne0\)推理过程也和上述类似

Kernels

  1. 非线性决策边界

    • 用相似度函数similarity function代替高阶项，度量样本x和第一个标记的相似度，即核函数，例如：高斯核函数：\(f_1=similarity(x,l^{(1)})=exp(-\frac{\lVert x-l^{(1)} \rVert^2}{2\sigma^2})=exp(-\frac{\Sigma_{j=1}^{n}(x_j-l_j^{(i)})^2}{2\sigma^2})\)

      ==问：这里σ是什么，如何计算？==

    • 通过用f替代特征，可以训练出复杂的非线性边界：例如：预测y=1，当\(\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3\ge0\)

  2. 选择landmark标记点 l :

    • Given一系列x，令\(l^1=x^1\), \(f_{m}^{(i)}=similarity(x^{(i)},l^{(m)})\)
    • 将\(x^{(i)}\in \mathbb{R}^{n+1}\)，转变为\(f^{(i)}=\begin{bmatrix}f_0^{(i)}\\f_0^{(i)}\\ \vdots \\ f_m^{(i)} \end{bmatrix}\)，\(f_0^{(i)}=1\)。\(f\in \mathbb{R}^{m+1}\)

  3. Hypothesis：Given x ， compute features f

    Predict "y=1" if \(\theta^Tf\ge0\)

  4. 代价函数： \[ \min _{\theta} C \sum_{i=1}^{m} y^{(i)} \operatorname{cost}_{1}\left(\theta^{T} f^{(i)}\right)+\left(1-y^{(i)}\right) \operatorname{cost}_{0}\left(\theta^{T} f^{(i)}\right)+\frac{1}{2} \sum_{j=1}^{m } \theta_{j}^{2} \] 在SVM的实际应用中，最后一项通常会用\(\theta^TM\theta\)，其中M和核函数有关，是为了提高计算效率

  5. 参数的选择：

    • C(=\(\frac{1}{\lambda}\))

      • Large C：Lower bias；High variance
      • Small C：Higher bias；Low variance

    • \(\sigma^2\)

      • Large \(\sigma^2\): Fearures fi vary more smoothly.

        ​ Higher bias; Lower variance

      • Small \(\sigma^2\): Features fi vary less smoothly.

        ​ Lower bias, Higher variance.

    • 方差（variance）：方差描述的是训练数据在不同迭代阶段的训练模型中，预测值的变化波动情况（或称之为离散情况）。

    • 偏差（bias）：偏差衡量了模型的预测值与实际值之间的偏离关系。

    • 低偏差高方差：过拟合；

    • You want to train C and the parameters for the kernel function using the training and cross-validation datasets.

SVMs in Practice

  1. 应用SVM

    • 选择C和σ

      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
      function [C, sigma] = dataset3Params(X, y, Xval, yval)
      % 这里x是训练集，xval是验证集
      value = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30];

      minC = 0;
      minSigma = 0;
      % 最小值设为交叉验证集的用例数
      minError = size(Xval,1);
      for i = 1:8,
          for j = 1:8,
              model= svmTrain(X, y, value(i), @(x1, x2) gaussianKernel(x1, x2, value(j)));
              predictions = svmPredict(model,Xval);
              error = mean(double(predictions ~= yval));
              if minError > error
                  minError = error;
                  minC = value(i);
                  minSigma = value(j);
              end;
          end;
      end;

      C = minC;
      sigma = minSigma;

      end

    • 选择核函数（相似度函数）

      • 线性核函数（=没有核函数）

    • 需要对特征向量归一化，否则一个特征会占据主要位置

    • 不是所有函数都能作为核函数，需要满足Mercer‘s Theorem莫塞尔定理，来确保SVM优化包能够正确运行

    • 其他核函数：

      • 多项式核函数
      • 字符串核函数string kernel；
      • 卡方核函数chi-square kernel
      • 直方图交叉核函数histogram intersection kernel

    • 多类别分类

      • svm包多数内置了
      • 否则用one-vs-all ：训练得到K组θ的值，然后选择θx最大的那一组作为分类结果

    • 逻辑回归和SVM，什么时候用？

      • n为特征数，m为训练集样本数。如果n相对于m来说比较大，使用逻辑回归或者没有核函数的SVM（linear kernel）
      • n小，m中等大。使用高斯核函数
      • n小，m很大。运行很慢，逻辑回归或没有核函数的SVM
      • 神经网络上面都适用，但有时可能会比SVM慢很多

    • SVM属于凸优化问题，大多数包都会找到全局最优，无需担心局部最优。神经网络的局部最优问题不是非常大但也不小。

Related Posts