2. Персептрон

Принцип персептрона

• Персептрон представляет собой линейную модель с двумя категориями.Его входом является вектор признаков экземпляра, а выходом является категория экземпляра, которые равны +1 и -1 соответственно, которые принадлежат дискриминантной модели. Предполагая, что набор обучающих данных линейно разделим, цель обучения персептрона состоит в том, чтобы получитьГиперплоскость разделения, в которой положительные и отрицательные точки экземпляра точно разделены. Если данные нелинейно разделимы, гиперплоскость не может быть получена в конце

• расстояние от точки до линии

  • Уравнение прямой в формуле имеет вид$A x+B y+C=0$, точка$P$Координаты г.$\left(x_{0}, y_{0}\right)$.$d=\frac{A x_{0}+B y_{0}+C}{\sqrt{A{2}+B{2}}}$

• Расстояние от образца до гиперплоскости

  • Предположим, что гиперплоскость$h=w \cdot x+b$, в$w=\left(w_{0}, w_{1}, \ldots w_{m}\right), x=\left(x_{0}, x_{1}, \ldots x_{m}\right)$, точка выборки$x^{\prime}$Расстояние до гиперплоскости заключается в следующем:$d=\frac{w \cdot x^{\prime}+b}{\|w\|}$

• Гиперпланы

  • гиперплоскость в космосе$R^d$подпространство в$R^{d-1}$. Гиперплоскость в 2D-пространстве — это линия, а гиперплоскость в 3D-пространстве — плоскость.

модель персептрона

• определение2.1$\влево(\вправо. Персептрон)$Предположим, что входное пространство (пространство признаков) равно$X \subseteq R^{n}$, выходное пространство$\mathrm{y}=\{+1,-1\}_{\circ}$входить$x \in X$вектор признаков, представляющий экземпляр, соответствующий точкам во входном пространстве (пространстве признаков); выход$y \in Y$Представляет класс экземпляра. Следующая функция из входного пространства в выходное пространство$f(x)=\operatorname{sign}(w \bullet x+b)\quad(2.1)$называется перцептроном. в$w$и$b$– параметры модели персептрона,$w \in R^{n}$называется весом или весовым вектором,$b \in R$называется предвзятостью,$w \bullet x$выражать$\mathrm{w}$и$\mathrm{x}$внутренний продукт.$\operatorname{sign}$является символической функцией, то есть: ​$\operatorname{sign}(x)=\left\{\begin{array}{l}+1, x \geq 0 \\ -1, x<0\end{array} \quad\right.$
• Персептрон представляет собой линейную классификационную модель, относящуюся к дискриминационной модели.
• Геометрическая интерпретация персептрона представляет собой линейное уравнение:$w \bullet x+b=0$соответствует пространству признаков$R^{n}$гиперплоскость в$S$,в$w$- вектор нормали к гиперплоскости,$b$является точкой пересечения гиперплоскости. Эта гиперплоскость делит пространство признаков на две части. Точки (собственные векторы), расположенные в двух частях, делятся наположительный и отрицательный. Поэтому гиперплоскость S становится разделяющей гиперплоскостью, как показано на рис. 2.1.Обучение персептрона из обучающих наборов данных (векторы признаков и категории экземпляров)$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}\}$в$x_{i} \in X=R^{n}, y_{i} \in Y=\{+1,-1\}, i=1,2, \ldots, N$, получить модель персептрона$(2.1)$, то есть найти параметры модели$w, b_{\circ}$Прогнозирование персептрона с помощью изученной модели персептрона дает соответствующую категорию выходных данных для нового входного экземпляра.
  • Докажите, почему w является нормальным вектором прямой линии (гиперплоскости в многомерном пространстве).

Стратегии обучения для персептронов

функция потерь

• Естественным выбором функции потерь является общее количество ошибочно классифицированных точек, но тогда функция потерь не является параметром.$w$и$b$Постоянно доступную функцию нелегко оптимизировать. Другой выбор функции потерь - ошибочная классификация точек на гиперплоскость.$S$Общее расстояние, которое используется персептроном. Для этого сначала запишите входное пространство$R^{n}$любая точка$x_{0}$расстояние до гиперплоскости S$\frac{1}{\|w\|}\left|w \bullet x_{0}+b\right|$,здесь,$\|w\|$ш$L_{2}$норма. Во-вторых, для неправильно классифицированных данных$\left(x_{i}, y_{i}\right)$Сказать,$-y_{i}\left(w \bullet x_{i}+b\right)>0$учредил. потому что когда$w \bullet x_{i}+b>0$Время,$y_{i}=-1$, и когда$w \bullet x_{i}+b<0$Время,$y_{i}=+ 1$. Следовательно, неправильно классифицированные баллы$x_{i}$Расстояние до гиперплоскости S равно$\frac{1}{\|w\|} y_{i}\left(w \bullet x_{i}+b\right)$Таким образом, предполагая гиперплоскость$S$Набор ошибочно классифицированных точек$M,$Тогда общее расстояние от всех ошибочно классифицированных точек до гиперплоскости S равно$\frac{1}{\|w\|} \sum_{x_{i}\in M} y_{i}\left(w \bullet x_{i}+b\right)$Не рассматривать$\frac{1}{\|w\|}$, получена функция потерь обучения персептрона.

• почему бы не рассмотреть$\frac{1}{\|w\|}$? ? кто-то сказал$\frac{1}{\|w\|}$является фиксированным значением, но я думаю, что самолет не уникален, и это значение обязательно будет меняться. Ссылаясь на точки зрения других людей и размышляя об этом, я чувствую, что причины могут быть перечислены в виде следующих двух моментов.

  1. $\frac{1}{\|w\|}$не влияет$y_{i}\left(w \cdot x_{i}+b\right)$Положительные и отрицательные суждения, то есть не влияют на промежуточный процесс алгоритма обучения. Поскольку алгоритм обучения персептрона управляется ошибочной классификацией, здесь следует отметить, что так называемый «привод ошибочной классификации» означает, что нам нужно только судить$- y_{i}\left(w \cdot x_{i}+b\right)$положительный и отрицательный, чтобы судить, правильный ли счет или нет, и$\frac{1}{\|w\|}$Это не влияет на оценку положительных и отрицательных значений. так$\frac{1}{\|w\|}$Промежуточный процесс алгоритма обучения персептрона можно игнорировать.
  2. $\frac{1}{\|w\|}$Не влияет на конечный результат алгоритма обучения персептрона. Потому что окончательное условие завершения алгоритма обучения персептрона состоит в том, что все входные данные правильно классифицированы, то есть нет ошибочно классифицированных точек. Тогда функция потерь в это время равна 0. Соответственно$-\frac{1}{\|w\|} \sum_{i \in M} y_{i}\left(w \cdot x_{i}+b\right)$, то есть числитель равен 0. Видно, что$\frac{1}{\|w\|}$На конечный результат это никак не влияет.

  Подводя итог, даже игнорируя$\frac{1}{\|w\|}$, и никак не повлияет на выполнение алгоритма обучения персептрона. Наоборот, это может упростить операцию и повысить эффективность выполнения алгоритма.

Алгоритмы обучения персептрона

первоначальная форма

• Алгоритм 2.1 (исходная форма алгоритма обучения персептрона)Вход: обучающий набор данных$T = \ влево \ {\ влево (x_ {1}, y_ {1} \ вправо), \ влево (x_ {2}, y_ {2} \ вправо), \ ldots, \ влево (x_ {N}, y_ {N}\right)\right\} , где x_{i} \in X=R^{n}, y_{i} \in Y=-1,+1, i=1,2, \ldots, N$; скорость обучения$\eta(0<\eta \leq 1)$; вывод:$w$, $b$; модель персептрона$f(x)=\operatorname{sign}(w \bullet x+b)$
  1. выберите начальное значение$w_{0}$, $b_{0}$
  2. Выберите данные в обучающем наборе$\left(x_{i}, y_{i}\right)$
  3. если$y_{i}\left(w \bullet x_{i}+b\right) \leq 0$ $w<-w+\eta y_{i} x_{i}$ $b<-b+\eta y_{i}$
  4. перейти к$2$, пока в обучающей выборке не останется ошибочно классифицированных точек.
• Когда точка экземпляра неправильно классифицирована и находится на неправильной стороне гиперплоскости разделения, отрегулируйте значения w, b, чтобы переместить гиперплоскость разделения в сторону ошибочно классифицированной точки, чтобы уменьшить точку ошибочной классификации и расстояние гиперплоскости до гиперплоскости. пересекает ошибочно классифицированную точку, чтобы сделать ее правильно классифицированной.

двойная форма

• Алгоритм 2.2 (двойная форма алгоритма обучения персептрона)Вход: линейно разделимый набор данных$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{N}, y_{N}\right)\right\}$, в$x_{i} \in R, y_{i} \in\{-1,+1\}, i=1,2, \ldots, N$; скорость обучения$\eta(0<\eta \leq 1) \text { ; }$вывод:$\alpha, b ;$модель персептрона$f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \bullet x+b\right)$в$\alpha=\left(\alpha_{1}, \alpha_{2}, \ldots, \alpha_{N}\right)^{T}$

  1. $\alpha \leftarrow 0, b \leftarrow 0$
  2. Выберите данные в обучающем наборе$\left(x_{i}, y_{i}\right)$
  3. если$y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \bullet x_{i}+b\right) \leq 0$​$\alpha_{i}<\alpha_{i}+\eta$​$b \leftarrow b+\eta y_{i}$
  4. перейти к$2$пока нет ошибочно классифицированных данных.
     

  В двойственной форме обучающие экземпляры появляются только в виде внутреннего продукта.Для удобства внутренний продукт между экземплярами в обучающем наборе может быть рассчитан заранее и сохранен в виде матрицы.Эта матрица так называемая матрица Грама.$G=\left[x_{i} \bullet x_{j}\right]_{M \times N}$

• проблема

  1. Как рассчитывается матрица Грамма?

  

  2. Как быть с числами с плавающей запятой, полученными в двойственной форме?$w$Это не обязательно должно быть целое число, числа с плавающей запятой также могут быть
  3. как понять$\eta_{i}$? ?$\eta_{i}$означает первый$i$Количество раз, когда точка выборки была неверно оценена, и персептрон в общей форме$w$На самом деле этоКоличество ложных позитивов для каждой точки образца умножается на$x_{i}y_{i}$Совокупная сумма , то есть$\sum _ { i = 1 } ^ { N } \eta_{i}{\eta}x_{i}y_{i}$. На каждой итерации$\eta_{i}$Значит этоДо сих пор$i$Количество раз, когда точка выборки была неверно оценена, это очень важно. Потому что необходимо многократно пускать вход в точку выборки$x$Умножьте два на два (вычисляется в общем виде$w$Это тоже тот случай, когда пора симулировать, а вы сами найдете), поэтому сделайте матрицу и сохраните ее заранее, что аналогично обычному способу зачистки алгоритма. Таким образом, две формы по существу одинаковы, но положим$w$Выразить в другой форме.

считать

$N$размер обучающей выборки,$n$это количество функций

1. Двойная форма: подметать один раз$N$Расчет каждых данных перед добавлением несколько ($a_{i}$) раз (когда$\eta$Выбирать$1$час,$a_{i}$Эквивалент градиента i-й группы данных$x_{i}y_{i}$Его добавляли несколько раз, причем добавляли сразу после обнаружения точки ошибочной классификации, вместо того, чтобы добавлять каждый раз), т.к.$x_{i}x_{j}$был рассчитан заранее в матрице Грамма, поэтому каждый раз$О(1)$, затем отсканируйте его$N$это$НА)$.
2. Необработанная форма: каждый расчет$w*x$, сложность вычисления этого внутреннего продукта равна$На)$

Итак, глядя на это, какой метод расчета выбрать, зависит от размера тренировочного набора и количества функций.

Код

первоначальная форма

• Для входного пространства персептрон отображает его в$\{+1,-1\}\}$выходное пространство$f(x)=\operatorname{sign}(w \cdot x+b)$
  1. за все ошибочно классифицированные точки$i \in M$, имеют$-y_{i}\left(w \cdot x_{i}+b\right)>0$Таким образом, мы можем определить следующую функцию потери в качестве критерия оптимизации:$L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$
  2. Решая градиент функции потерь, ​$\begin{array}{l}\nabla_{w} L(w, b)=-\sum_{x_{i} \in M} y_{i} x_{i} \\\nabla_{b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\end{array}$
  3. Легко получить исходный вид алгоритма обучения персептрона ​$\begin{array}{l} w \leftarrow w+\eta y_{i} x_{i} \\ b \leftarrow b+\eta y_{i} \end{array}$
  4. Весь алгоритм работы выглядит следующим образом:
     1. выберите начальное значение$w_{0}, b_{0}$
     2. Произвольно выбирать точки в тренировочном наборе$(x_{i},y_{i})$
     3. если$- y_{i}\left(w \cdot x_{i}+b\right)>0$затем согласно$3$Обновлять$\mathrm{w}, \mathrm{b}$
     4. повторение$2$пока не будет неправильной классификации

•   from __future__ import division
    import random
    import numpy as np
    import matplotlib.pyplot as plt  
  
  
    def sign(v):
        if v>=0:
            return 1
        else:
            return -1
  
    def train(train_num,train_datas,lr):
        w=[0,0]
        b=0
        for i in range(train_num):
            x=random.choice(train_datas)
            x1,x2,y=x
            if(y*sign((w[0]*x1+w[1]*x2+b))<=0):
                w[0]+=lr*y*x1
                w[1]+=lr*y*x2
                b+=lr*y
        return w,b
    def plot_points(train_datas,w,b):
        plt.figure()
        x1 = np.linspace(0, 8, 100)  
        x2 = (-b-w[0]*x1)/w[1]
        plt.plot(x1, x2, color='r', label='y1 data')
        datas_len=len(train_datas)
        for i in range(datas_len):
            if(train_datas[i][-1]==1):
                plt.scatter(train_datas[i][0],train_datas[i][1],s=50)  
            else:
                plt.scatter(train_datas[i][0],train_datas[i][1],marker='x',s=50)  
        plt.show()
  
  
    if __name__=='__main__':
        train_data1 = [[1, 3, 1], [2, 2, 1], [3, 8, 1], [2, 6, 1]]  # 正样本
        train_data2 = [[2, 1, -1], [4, 1, -1], [6, 2, -1], [7, 3, -1]]  # 负样本
        train_datas = train_data1 + train_data2  # 样本集
        w,b=train(train_num=800,train_datas=train_datas,lr=0.01)
        plot_points(train_datas,w,b)
  

двойная форма

• Короче говоря, двойственная форма персептрона — это$w, b$обучение стало$\alpha, b$обучения в его первоначальном виде,$w$Его необходимо обновлять, когда он неправильно классифицируется в каждом раунде итерации, а также при использовании двойного метода для определенной точки.$(x_{i},y_{i})$Когда возникает неправильная классификация, нам нужно только обновить ее соответствующую$\alpha_{i}$ОК, и, наконец, следуйте$5$формула может быть рассчитана один раз$w$, В то же время мы выше шаги$3$середина$y_{i}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x_{i}+b\right) \leq 0$Как можно видеть,$x_{j} \cdot x_{i}$появляется только как внутренний продукт, поэтому мы можем сначала вычислить$x$из$gram$Матрица хранится, так что формальному обучению нужно только посмотреть таблицу, чтобы получить$x_{j} \cdot x_{i}$Значение , которое может облегчить оптимизацию программы и повысить скорость работы. Обработка параметра b одинакова для примитивной и двойственной форм. ​$5$Формула$f(x)=\operatorname{sign}\left(\sum_{j=1}^{N} \alpha_{j} y_{j} x_{j} \cdot x+b\right)$

• from __future__ import division
  import random
  import numpy as np
  import matplotlib.pyplot as plt  
  
  
  def train(train_num,train_datas,lr):
      w=0.0
      b=0
      datas_len = len(train_datas)
      alpha = [0 for i in range(datas_len)]
      train_array = np.array(train_datas)
      gram = np.dot(train_array[:,0:-1] , train_array[:,0:-1].T)
      for idx in range(train_num):
          tmp=0
          i = random.randint(0,datas_len-1)
          yi=train_array[i,-1]
          for j in range(datas_len):
              tmp+=alpha[j]*train_array[j,-1]*gram[i,j]
          tmp+=b
          if(yi*tmp<=0):
              alpha[i]=alpha[i]+lr
              b=b+lr*yi
      for i in range(datas_len):
          w+=alpha[i]*train_array[i,0:-1]*train_array[i,-1]
      return w,b,alpha,gram
  
  def plot_points(train_datas,w,b):
      plt.figure()
      x1 = np.linspace(0, 8, 100)
      x2 = (-b-w[0]*x1)/(w[1]+1e-10)
      plt.plot(x1, x2, color='r', label='y1 data')
      datas_len=len(train_datas)
      for i in range(datas_len):
          if(train_datas[i][-1]==1):
              plt.scatter(train_datas[i][0],train_datas[i][1],s=50)  
          else:
              plt.scatter(train_datas[i][0],train_datas[i][1],marker='x',s=50)  
      plt.show()
  
  if __name__=='__main__':
      train_data1 = [[1, 3, 1], [2, 2, 1], [3, 8, 1], [2, 6, 1]]  # 正样本
      train_data2 = [[2, 1, -1], [4, 1, -1], [6, 2, -1], [7, 3, -1]]  # 负样本
      train_datas = train_data1 + train_data2  # 样本集
      w,b,alpha,gram=train(train_num=500,train_datas=train_datas,lr=0.01)
      plot_points(train_datas,w,b)