Deeplearning Algorithms tutorial

谷歌的人工智能位于全球前列，在图像识别、语音识别、无人驾驶等技术上都已经落地。而百度实质意义上扛起了国内的人工智能的大旗，覆盖无人驾驶、智能助手、图像识别等许多层面。苹果业已开始全面拥抱机器学习，新产品进军家庭智能音箱并打造工作站级别Mac。另外，腾讯的深度学习平台Mariana已支持了微信语音识别的语音输入法、语音开放平台、长按语音消息转文本等产品，在微信图像识别中开始应用。全球前十大科技公司全部发力人工智能理论研究和应用的实现，虽然入门艰难，但是一旦入门，高手也就在你的不远处！ AI的开发离不开算法那我们就接下来开始学习算法吧！

支持向量机（SVM）

支持向量机(Support Vector Machine，SVM)是Corinna Cortes和Vapnik在1995年首先提出的，是一种监督式学习的方法，可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器，这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。

在机器学习中，支持向量机（SVM，还支持矢量网络）是与相关的学习算法有关的监督学习模型，可以分析数据，识别模式，用于分类和回归分析。 支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折中，以求获得最好的推广能力 。

在机器学习中，支持向量机（SVM，还支持矢量网络）是与相关的学习算法有关的监督学习模型，可以分析数据，识别模式，用于分类和回归分析。给定一组训练样本，每个标记为属于两类，一个SVM训练算法建立了一个模型，分配新的实例为一类或其他类，使其成为非概率二元线性分类。一个SVM模型的例子，如在空间中的点，映射，使得所述不同的类别的例子是由一个明显的差距是尽可能宽划分的表示。新的实施例则映射到相同的空间中，并预测基于它们落在所述间隙侧上属于一个类别。 除了进行线性分类，支持向量机可以使用所谓的核技巧，它们的输入隐含映射成高维特征空间中有效地进行非线性分类。

支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。建立方向合适的分隔超平面使两个与之平行的超平面间的距离最大化。其假定为，平行超平面间的距离或差距越大，分类器的总误差越小。

支持向量机（SVM） - 图1

应用示例

  1. # coding: utf8
  2. # svm/smo.py
  4. import numpy as np
  6. from sklearn.metrics.pairwise import rbf_kernel
  8. """
  9. svm模型
  10. """
  12. def linearKernel():
  13.     """线性核函数
  14.     """
  15.     def calc(X, A):
  16.         return X * A.T
  17.     return calc
  19. def rbfKernel(delta):
  20.     """rbf核函数
  21.     """
  22.     gamma = 1.0 / (2 * delta**2)
  24.     def calc(X, A):
  25.         return np.mat(rbf_kernel(X, A, gamma=gamma))
  26.     return calc
  28. def getSmo(X, y, C, tol, maxIter, kernel=linearKernel()):
  29.     """SMO
  31.     Args:
  32.         X 训练样本
  33.         y 标签集
  34.         C 正规化参数
  35.         tol 容忍值
  36.         maxIter 最大迭代次数
  37.         K 所用核函数
  39.     Returns:
  40.         trainSimple 简化版训练算法
  41.         train 完整版训练算法
  42.         predict 预测函数
  43.     """
  44.     # 存放核函数的转化结果
  45.     K = kernel(X, X)
  46.     # Cache存放预测误差，用以加快计算速度
  47.     ECache = np.zeros((m,2))
  49.     def predict(X, alphas, b, supportVectorsIndex, supportVectors):
  50.         """计算权值向量
  52.         Args:
  53.             X 预测矩阵
  54.             alphas alphas
  55.             b b
  56.             supportVectorsIndex 支持向量坐标集
  57.             supportVectors 支持向量
  58.         Returns:
  59.             predicts 预测结果
  60.         """
  61.         Ks = kernel(supportVectors, X)
  62.         predicts = (np.multiply(alphas[supportVectorsIndex], y[
  63.             supportVectorsIndex]).T * Ks + b).T
  64.         predicts = np.sign(predicts)
  65.         return predicts
  67.     def w(alphas, b, supportVectorsIndex, supportVectors):
  68.         """计算权值
  70.         Args:
  71.             alphas alphas
  72.             b b
  73.             supportVectorsIndex 支持向量坐标
  74.             supportVectors 支持向量
  75.         Returns:
  76.             w 权值向量
  77.         """
  78.         return (np.multiply(alphas[supportVectorsIndex], y[
  79.             supportVectorsIndex]).T * supportVectors).T
  81.     def E(i, alphas, b):
  82.         """计算预测误差
  84.         Args:
  85.             i i
  86.             alphas alphas
  87.             b b
  88.         Returns:
  89.             E_i 第i个样本的预测误差
  90.         """
  91.         FXi = float(np.multiply(alphas, y).T * K[:, i]) + b
  92.         E = FXi - float(y[i])
  93.         return E
  95.     def updateE(i, alphas, b):
  96.         ECache[i] = [1, E(i, alphas, b)]
  98.     def selectJRand(i):
  99.         """
  100.         """
  101.         j = i
  102.         while j == i:
  103.             j = int(np.random.uniform(0, m))
  104.         return j
  106.     def selectJ(i, Ei, alphas, b):
  107.         """选择权值 {% math %}\alpha^{(i)}{% endmath %}
  108.         """
  109.         maxJ = 0; maxDist=0; Ej = 0
  110.         ECache[i] = [1, Ei]
  111.         validCaches = np.nonzero(ECache[:, 0])[0]
  112.         if len(validCaches) > 1:
  113.             for k in validCaches:
  114.                 if k==i: continue
  115.                 Ek = E(k, alphas, b)
  116.                 dist = np.abs(abs(Ei-Ek))
  117.                 if maxDist < dist:
  118.                     Ej = Ek
  119.                     maxJ = k
  120.                     maxDist = dist
  121.             return maxJ, Ej
  122.         else:
  123.             ### 随机选择
  124.             j = selectJRand(i)
  125.             Ej = E(j, alphas, b)
  126.             return j, Ej
  128.     def select(i, alphas, b):
  129.         """alpha对选择
  130.         """
  131.         Ei = E(i, alphas, b)
  132.         # 选择违背KKT条件的，作为alpha2
  133.         Ri = y[i] * Ei
  134.         if (Ri < -tol and alphas[i] < C) or \
  135.                 (Ri > tol and alphas[i] > 0):
  136.             # 选择第二个参数
  137.             j = selectJRand(i)
  138.             Ej = E(j, alphas, b)
  139.             # j, Ej = selectJ(i, Ei, alphas, b)
  140.             # get bounds
  141.             if y[i] != y[j]:
  142.                 L = max(0, alphas[j] - alphas[i])
  143.                 H = min(C, C + alphas[j] - alphas[i])
  144.             else:
  145.                 L = max(0, alphas[j] + alphas[i] - C)
  146.                 H = min(C, alphas[j] + alphas[i])
  147.             if L == H:
  148.                 return 0, alphas, b
  149.             Kii = K[i, i]
  150.             Kjj = K[j, j]
  151.             Kij = K[i, j]
  152.             eta = 2.0 * Kij - Kii - Kjj
  153.             if eta >= 0:
  154.                 return 0, alphas, b
  155.             iOld = alphas[i].copy()
  156.             jOld = alphas[j].copy()
  157.             alphas[j] = jOld - y[j] * (Ei - Ej) / eta
  158.             if alphas[j] > H:
  159.                 alphas[j] = H
  160.             elif alphas[j] < L:
  161.                 alphas[j] = L
  162.             if abs(alphas[j] - jOld) < tol:
  163.                 alphas[j] = jOld
  164.                 return 0, alphas, b
  165.             alphas[i] = iOld + y[i] * y[j] * (jOld - alphas[j])
  166.             # update ECache
  167.             updateE(i, alphas, b)
  168.             updateE(j, alphas, b)
  169.             # update b
  170.             bINew = b - Ei - y[i] * (alphas[i] - iOld) * Kii - y[j] * \
  171.                 (alphas[j] - jOld) * Kij
  172.             bJNew = b - Ej - y[i] * (alphas[i] - iOld) * Kij - y[j] * \
  173.                 (alphas[j] - jOld) * Kjj
  174.             if alphas[i] > 0 and alphas[i] < C:
  175.                 bNew = bINew
  176.             elif alphas[j] > 0 and alphas[j] < C:
  177.                 bNew = bJNew
  178.             else:
  179.                 bNew = (bINew + bJNew) / 2
  180.             return 1, alphas, b
  181.         else:
  182.             return 0, alphas, b
  184.     def train():
  185.         """完整版训练算法
  187.         Returns:
  188.             alphas alphas
  189.             w w
  190.             b b
  191.             supportVectorsIndex 支持向量的坐标集
  192.             supportVectors 支持向量
  193.             iterCount 迭代次数
  194.         """
  195.         numChanged = 0
  196.         examineAll = True
  197.         iterCount = 0
  198.         alphas = np.mat(np.zeros((m, 1)))
  199.         b = 0
  200.         # 如果所有alpha都遵从 KKT 条件，则在整个训练集上迭代
  201.         # 否则在处于边界内 (0, C) 的 alpha 中迭代
  202.         while (numChanged > 0 or examineAll) and (iterCount < maxIter):
  203.             numChanged = 0
  204.             if examineAll:
  205.                 for i in range(m):
  206.                     changed, alphas, b = select(i, alphas, b)
  207.                     numChanged += changed
  208.             else:
  209.                 nonBoundIds = np.nonzero((alphas.A > 0) * (alphas.A < C))[0]
  210.                 for i in nonBoundIds:
  211.                     changed, alphas, b = select(i, alphas, b)
  212.                     numChanged += changed
  213.             iterCount += 1
  215.             if examineAll:
  216.                 examineAll = False
  217.             elif numChanged == 0:
  218.                 examineAll = True
  219.         supportVectorsIndex = np.nonzero(alphas.A > 0)[0]
  220.         supportVectors = np.mat(X[supportVectorsIndex])
  221.         return alphas, w(alphas, b, supportVectorsIndex, supportVectors), b, \
  222.             supportVectorsIndex, supportVectors, iterCount
  224.     def trainSimple():
  225.         """简化版训练算法
  227.         Returns:
  228.             alphas alphas
  229.             w w
  230.             b b
  231.             supportVectorsIndex 支持向量的坐标集
  232.             supportVectors 支持向量
  233.             iterCount 迭代次数
  234.         """
  235.         numChanged = 0
  236.         iterCount = 0
  237.         alphas = np.mat(np.zeros((m, 1)))
  238.         b = 0
  239.         L = 0
  240.         H = 0
  241.         while iterCount < maxIter:
  242.             numChanged = 0
  243.             for i in range(m):
  244.                 Ei = E(i, alphas, b)
  245.                 Ri = y[i] * Ei
  246.                 # 选择违背KKT条件的，作为alpha2
  247.                 if (Ri < -tol and alphas[i] < C) or \
  248.                         (Ri > tol and alphas[i] > 0):
  249.                     # 选择第二个参数
  250.                     j = selectJRand(i)
  251.                     Ej = E(j, alphas, b)
  252.                     # get bounds
  253.                     if y[i] != y[j]:
  254.                         L = max(0, alphas[j] - alphas[i])
  255.                         H = min(C, C + alphas[j] - alphas[i])
  256.                     else:
  257.                         L = max(0, alphas[j] + alphas[i] - C)
  258.                         H = min(C, alphas[j] + alphas[i])
  259.                     if L == H:
  260.                         continue
  261.                     Kii = K[i, i]
  262.                     Kjj = K[j, j]
  263.                     Kij = K[i, j]
  264.                     eta = 2.0 * Kij - Kii - Kjj
  265.                     if eta >= 0:
  266.                         continue
  267.                     iOld = alphas[i].copy();
  268.                     jOld = alphas[j].copy()
  269.                     alphas[j] = jOld - y[j] * (Ei - Ej) / eta
  270.                     if alphas[j] > H:
  271.                         alphas[j] = H
  272.                     elif alphas[j] < L:
  273.                         alphas[j] = L
  274.                     if abs(alphas[j] - jOld) < tol:
  275.                         alphas[j] = jOld
  276.                         continue
  277.                     alphas[i] = iOld + y[i] * y[j] * (jOld - alphas[j])
  278.                     # update b
  279.                     bINew = b - Ei - y[i] * (alphas[i] - iOld) * Kii - y[j] * \
  280.                         (alphas[j] - jOld) * Kij
  281.                     bJNew = b - Ej - y[i] * (alphas[i] - iOld) * Kij - y[j] * \
  282.                         (alphas[j] - jOld) * Kjj
  283.                     if alphas[i] > 0 and alphas[i] < C:
  284.                         b = bINew
  285.                     elif alphas[j] > 0 and alphas[j] < C:
  286.                         b = bJNew
  287.                     else:
  288.                         b = (bINew + bJNew) / 2.0
  289.                     numChanged += 1
  290.             if numChanged == 0:
  291.                 iterCount += 1
  292.             else:
  293.                 iterCount = 0
  294.         supportVectorsIndex = np.nonzero(alphas.A > 0)[0]
  295.         supportVectors = np.mat(X[supportVectorsIndex])
  296.         return alphas, w(alphas, b, supportVectorsIndex, supportVectors), b, \
  297.             supportVectorsIndex, supportVectors, iterCount
  298.     return trainSimple, train, predict

相比于神经网络这样更先进的算法，支持向量机有两大主要优势：更高的速度、用更少的样本（千以内）取得更好的表现。这使得该算法非常适合文本分类问题。