感知机算法

感知机算法求线性分界面———《模式识别导论》实验报告一

实验题目

  1. 已知二维模式样本集$X_1={(1,0),(1,1),(0,2)}$,$X_2={(2,1),(2,2),(1,3)}$,用感知机算法固定增量求分界面方程，并且作图；
  2. 分别改变初始权向量和样本集中的顺序来获得不同结果；
  3. （选做）自定义线性不可分样本，通过限定算法迭代次数得到结果并分析。

实验目的

  1. 学习线性可分问题以及感知机算法
  2. 熟悉numpy等包工具，掌握科学绘图
  3. 线性不可分问题的分析与处理

实验原理

对于两类（$\omega_i, \omega_j$）线性分类问题，给定一个D维样本$\chi = [\boldsymbol{x_1},\boldsymbol x_2,…\boldsymbol x_n]^T$，我们用
$$\hat y = sgn(\boldsymbol w^T \boldsymbol x_k)\qquad k=1,2,…n$$
上式已转化为增广形式，即$\boldsymbol x = [x_1,x_2,…x_D,1]^T，\hat y = sgn(g(\boldsymbol x))$

$$ g(\boldsymbol{x, w}) = w_1x_1+w_2x_2+…+w_Dx_D+b = \boldsymbol w^T \boldsymbol x$$

对于(g>0 ，\hat y=1)，认为(x \in \omega_i);(g<0 ， \hat y= -1)，认为(x \in \omega_j)。同理，我们用这种规则来标注样本，作为标签值$y^{(k)}$。
作为判别函数，几何上$ w $可表示为一个多维空间中的（超）平面的法向量，这个平面称为分界面。
如何得到一个好的$ g(\boldsymbol x) = w^T \boldsymbol x$，实验采用感知机算法，描述如下：

  1. 迭代数epochs=0, 赋$w$初值。
  2. 输入$\boldsymbol x_k$。
  3. 计算函数值$g(\boldsymbol x_k)$。
  4. 修正权向量$w_k$，epochs表示迭代代数。
    运用以下算法，计算$\boldsymbol w_k^Tx^{(k)}$和$y^{(k)}$是否异号来进行迭代决策，无需改变样本集$\omega_j$中的$\hat y$。

    if $\boldsymbol w_k^T(y^{(k)}\boldsymbol x^{(k)})\leq0$ then
    $\boldsymbol w = \boldsymbol w + c*y^{(k)}\boldsymbol x^{(k)}$
    其中$c$为学习率，取0,1之间的值。
  5. epochs+1，进入下一轮迭代。直到w对所有训练样本均稳定不变，程序结束。

设计思路

  1. 本实验通过numpy科学包处理。
    超参数取$c = 1$。$w$已经采用增广形式，并且在numpy的矩阵表示中，一维向量认为是行向量。
features = np.array([[1,0,1],[1,1,1],[0,2,1],[2,1,1],[2,2,1],[1,3,1]])
labels = np.array([1, 1, 1, -1, -1, -1]).reshape(6,1)
w = np.array([1,1,1])
  1. 利用pandas包对矩阵进行行重排，随机排列$\chi$内样本点，以得到不同的样本集及结果。
featuresT = features.transpose()
print(featuresT)
print(np.array(pd.DataFrame(featuresT).reindex(columns=[2,0,4,5,1,3]))) #需手动指定重排顺序
features = featuresT.transpose()
  1. 开始训练，采用如上所述修正$w$算法。
    检测$w$何时对所有样本收敛，停止迭代。
# 在一轮循环前
v = np.array(w)
# 开始一轮
for i in range(num_examples)：
        ……
u = (v == w)
if(u.all() == True):
        break

结果分析

  1. 调整样本点顺序，对最终结果无影响，但是改变$w$初始向量值会导致结果不同。
    初始$\boldsymbol w=(1,1,1)$ $\boldsymbol w_1 = (-4,-2,8)$
    初始$\boldsymbol w=(1,2,1)$ $\boldsymbol w_2 = (-4,-2,8)$
    初始$\boldsymbol w=(-5,-4,1)$ $\boldsymbol w_3 = (-3,-1,5)$
    初始$\boldsymbol w=(0,2,1)$ $\boldsymbol w_4 = (-3,-1,5)$
    初始$\boldsymbol w=(-10,-10,1)$ $\boldsymbol w_1 = (-4,-2,9)$

  2. 画图调用matplotlib包
    $\boldsymbol w = (1,1,1)$，epochs=15轮后权向量收敛，
    分界面$w_0 x + w_1 y + w_2 z = 0$，由于$z = 1$
    分界面在平面上的投影为$y = - w_0x /w_1 - w_2/w_1$
    结果如下所示：蓝色点代表样本集，绿色直线即为投影。
    figure_1

选做实验

1.不可分样本问题
自定义线性不可分样本$\chi _1={(1,0),(0,2)}$,$X_2={(0,0),(3,1)}$,用感知机算法求分界面方程。

2.处理方法
设置max_epochs = 500，一轮循环过后，如果达到最大迭代数，结束程序。

3.计算结果
初始$\boldsymbol w=(1,1,1) \qquad \boldsymbol epochs =501\qquad w_1 = (-3,1,-2)$
初始$\boldsymbol w=(4,-2,1) \qquad \boldsymbol epochs =501\qquad w_1 = (-1,2,-1)$
可以得出结论，线性不可分样本，算法不能收敛到某一个分界面，如果不设置轮数限制，会无止境的计算下去。为此，通常情况应该设置一个足够大的max_epochs，以防止陷入死循环。