机器学习笔记

前言

章节目录

1. 感知机模型

2. 感知机学习策略

1. 数据集的线性可分性

2. 感知机学习策略

3. 感知机学习算法

3. 感知机学习算法

1. 感知机学习算法的原始形式

2. 算法的收敛性

3. 感知机学习算法的对偶形式

导读

感知机是二类分类的线性分类模型。

• 损失函数L(w,b)的经验风险最小化

• 本章中涉及到向量内积，有超平面的概念，也有线性可分数据集的说明，在策略部分有说明损关于失函数的选择的考虑。另外， 感知机和SVM的更多联系源自$margin$的思想;

• 本章涉及的两个例子，思考一下为什么\( \eta = 1 \)，进而思考一下参数空间；

• 在收敛性证明那部分提到了偏置合并到权重向量的技巧，合并后的权重向量叫做扩充权重向量，这点在LR和SVM中都有应用，但是这种技巧在书中的表示方式是不一样的；

• 第一次涉及Gram 矩阵 \( \mathbf{G} = [x_i \cdot x_j]_{N \times N} \) ；

• 感知机的激活函数是符号函数（sign()）；

• 感知机是神经网络和支持向量机的基础，也是最简单的一种；

• 当我们讨论决策边界的时候, 实际上是在考虑算法的几何解释。

• 关于感知机为什么不能处理异或问题, 可以借助下图理解（python绘制）

上面紫色和橙色为两类点, 线性的分割超平面应该要垂直于那些红粉和紫色的线.

• 书中有提到函数间隔，几何间隔；区别在于$w$的线性问题；

• 分离超平面将特征空间划分为两个部分，一部分是正类， 一部分是负类。法向量指向的一侧为正类，另一侧为负类。矩阵线性变换，特征向量部分内容；

• 感知机的损失函数 \( L \) 定义为：  \[ L = \max(0, -y_i (w \cdot x_i + b)) \]  其中，\( y_i \) 是样本 \( i \) 的标签，\( w \) 是权重向量，\( x_i \) 是输入特征向量，\( b \) 是偏置项。

三要素

模型

• 输入空间是一个 \( n \) 维实数空间 \( \mathbf{R}^n \) 的子集，表示为\( \mathcal{X} \subseteq \mathbf{R}^n \)；

• 输出空间则是一个有限集合，仅包含两个元素，即 +1 和 -1，表示为\( \mathcal{Y} = \{+1, -1\} \)

决策函数：\[ f(x) = \text{sign}(w \cdot x + b) \]

策略

确定学习策略就是定义(经验)损失函数并将损失函数最小化。

损失函数选择

损失函数的一个自然选择是误分类点的总数，但是，这样的损失函数不是参数$w$,$b$的连续可导函数，不易优化

损失函数的另一个选择是误分类点到超平面$S$的总距离，这是感知机所采用的

感知机学习的经验风险函数(损失函数)

$$
L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)
$$

其中M是误分类点的集合给定训练数据集T，损失函数L(w,b)是w和b的连续可导函数；尤其注意理解最前面的负号；

算法

原始形式

输入：

训练集 \( T = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\} \)，其中 \( x_i \in \mathcal{X} = \mathbb{R}^n \)，\( y_i \in \mathcal{Y} = \{-1, +1\} \)，\( i = 1, 2, \dots, N \)；学习率 \( 0 < \eta \leq 1 \)。

输出：

权重向量 \( w \) 和偏置 \( b \)，函数 \( f(x) = \text{sign}(w \cdot x + b) \)。

步骤：

1. 选取初值 \( w_0, b_0 \)  

2. 从训练集中选取数据 \( (x_i, y_i) \)

3. 如果 \( y_i(w \cdot x_i + b) \leq 0 \) 执行更新：   \[ w \leftarrow w + \eta y_i x_i \]            \[ b \leftarrow b + \eta y_i \]

4. 返回步骤2，直到训练集中没有误分类点

注意这个原始形式中的迭代公式，可以对$x$补1，将$w$和$b$合并在一起，合在一起的这个叫做扩充权重向量，书上有提到。

对偶形式

对偶形式的基本思想是将w和b表示为实例x_i和标记y_i的线性组合的形式，通过求解其系数而求得w和b。

输入：

训练集 \( T = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\} \)，其中 \( x_i \in \mathcal{X} = \mathbb{R}^n \)，\( y_i \in \mathcal{Y} = \{-1, +1\} \)，\( i = 1, 2, \dots, N \)；学习率 \( 0 < \eta \leq 1 \)；

输出：

系数 \( \alpha, b \)，函数 \( f(x) = \text{sign}\left(\sum_{j=1}^N \alpha_j y_j x_j \cdot x + b\right) \)，系数向量 \( \alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T \)。

初始化：

 \( \alpha \leftarrow 0, b \leftarrow 0 \)。

从训练集中选取数据 \( (x_i, y_i) \)；

如果 \( y_i \left(\sum_{j=1}^N \alpha_j y_j x_j \cdot x + b\right) \leq 0 \) 执行以下更新：            \[            \alpha_i \leftarrow \alpha_i + \eta \\            b \leftarrow b + \eta y_i            \]     

返回步骤 1，直到训练集中没有误分类点

Gram matrix

对偶形式中，训练实例仅以内积的形式出现。为了方便可预先将训练集中的实例间的内积计算出来并以矩阵的形式存储，这个矩阵就是所谓的Gram矩阵

$$
G=[x_i\cdot x_j]_{N\times N} \nonumber
$$

例子

这里使用经典鸢尾花内置数据集进行一个简单的二分类感知机的代码实现：

• 加载鸢尾花数据集，进行了基本统计描述，并绘制了两种类别的散点图来展示萼片长度与萼片宽度的关系。

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
%matplotlib inline

# load data
iris = load_iris()  #zy嫌弃麻烦选择加载内置的鸢尾花数据集
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target

df.columns = [
'sepal length', 'sepal width', 'petal length', 'petal width', 'label'
]
df.describe()

plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

• 提取前100个样本的特征和标签，并将标签转换为二分类格式。

data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
y = np.array([1 if i == 1 else -1 for i in y])

• 正式构建感知机

  定义了一个简单的感知机模型类Model，包含随机权重初始化、线性签名函数、随机梯度下降训练方法和未实现的评分方法。训练使用符号函数判断分类，通过不断更新权重和偏置直到全部样本正确分类为止。

class Model:
    def __init__(self):
        self.w = np.random.rand(len(data[0]) - 1).astype(np.float32)
        self.b = 0
        self.l_rate = 0.01
        # self.data = data

    def sign(self, x, w, b):
        y = np.dot(x, w) + b
        return y

    # 随机梯度下降法
    def fit(self, X_train, y_train):
        is_wrong = False
        while not is_wrong:
            wrong_count = 0
            for d in range(len(X_train)):
                X = X_train[d]
                y = y_train[d]
                if y * self.sign(X, self.w, self.b) <= 0:
                    self.w = self.w + self.l_rate * np.dot(y, X)
                    self.b = self.b + self.l_rate * y
                    wrong_count += 1
            if wrong_count == 0:
                is_wrong = True
        return 'Perceptron Model!'
    
    def score(self):
        pass
        
perceptron = Model()
perceptron.fit(X, y)

• 模型结果展示
  

x_points = np.linspace(4, 7, 10)
y_ = -(perceptron.w[0] * x_points + perceptron.b) / perceptron.w[1]
plt.plot(x_points, y_)

plt.plot(data[:50, 0], data[:50, 1], 'bo', color='blue', label='0')
plt.plot(data[50:100, 0], data[50:100, 1], 'bo', color='orange', label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

为便于数据处理跑模型，截取的数据量较小；所以一些参数设置的可能不是很好，经验之谈，学习率设置在3$e$^-5；采用$Pycharm$的科学数据模式可以实时查看变量以及参数训练过程；

当然可以直接使用scikit-learn进行，不用自己定义模型；

# 如果未安装，可以直接使用conda install 或者 pip install

import sklearn
from sklearn.linear_model import Perceptron

print(sklearn.__version__)   #1.4.2

clf = Perceptron(fit_intercept=True,
max_iter=1000,
shuffle=True)
clf.fit(X, y)

print(clf.coef_)  # [[ 23.2 -38.7]]
print(clf.intercept_)  # [-5.]

plt.figure(figsize=(16,9))
plt.title('')

plt.scatter(data[:50, 0], data[:50, 1], c='b', label='Iris-setosa',)
plt.scatter(data[50:100, 0], data[50:100, 1], c='orange', label='Iris-versicolor')

x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

• 你可能已经注意到了，左下角有一个点未能被正常分类；

• 因为在sklearn中perceptron，实例中有一个tol参数，tol参数规定了如果本次迭代的损失和上次迭代的损失之差小于一个特定值时，停止迭代。所以我们需要设置tol=None使之可以继续迭代：

clf = Perceptron(fit_intercept=True,
                max_iter=1000,
                tol=None,
                shuffle=True)
clf.fit(X, y)

print(clf.coef_)  # [[ 23.2 -38.7]]
print(clf.intercept_)  # [-5.]

plt.figure(figsize=(16,9))
plt.title('')

plt.scatter(data[:50, 0], data[:50, 1], c='b', label='Iris-setosa',)
plt.scatter(data[50:100, 0], data[50:100, 1], c='orange', label='Iris-versicolor')

x_ponits = np.arange(4, 8)
y_ = -(clf.coef_[0][0]*x_ponits + clf.intercept_)/clf.coef_[0][1]
plt.plot(x_ponits, y_)

plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()

问题

损失函数

知乎上有个问题

感知机中的损失函数中的分母为什么可以不考虑？有些人解释是正数，不影响，但是分母中含有 w，而其也是未知数，
在考虑损失函数的最值时候会不影响么？

这个对应了书中不考虑1/||w||，就得到感知机学习的损失函数

• 损失函数定义：感知机的损失函数通常关注误分类点。

• 分母的作用：分母为正的常数项，不影响最值点。

• 最优化问题：在求解最值时，分母不影响极值点的位置，只影响损失的尺度。

• 权重的影响：权重 \( w \) 是模型参数，通过训练数据优化确定，分母不包含 \( w \)。

也就是说感知机本身就是针对于线性可分的数据集（你要说拿它做非这种类型的，那你是对的），所以我们不关注偏差是多少，关注的是有没有偏差，有没有被错误分类的；所以分母加不加都可以，加了只是影响计算性能；

总结

感知机是最基础入门的机器学习方法，但是不要和线性回归等内容混淆，最后总结一下：

1．感知机是根据输入实例的特征向量$x$对其进行二类分类的线性分类模型：
$$ f(x)=\operatorname{sign}(w \cdot x+b) $$ 

感知机模型对应于输入空间（特征空间）中的分离超平面$w \cdot x+b=0$。 

2．感知机学习的策略是极小化损失函数：
$$ \min _{w, b} L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right) $$

损失函数对应于误分类点到分离超平面的总距离。 

3．感知机学习算法是基于随机梯度下降法的对损失函数的最优化算法，有原始形式和对偶形式。算法简单且易于实现。原始形式中，首先任意选取一个超平面，然后用梯度下降法不断极小化目标函数。在这个过程中一次随机选取一个误分类点使其梯度下降。 

4．当训练数据集线性可分时，感知机学习算法是收敛的。感知机算法在训练数据集上的误分类次数$k$满足不等式：
$$ k \leqslant\left(\frac{R}{\gamma}\right)^{2} $$ 

当训练数据集线性可分时，感知机学习算法存在无穷多个解，其解由于不同的初值或不同的迭代顺序而可能有所不同。 

 二分类模型

 $f(x) = sign(w\cdot x + b)$
$\operatorname{sign}(x)=\left\{\begin{array}{ll}{+1,} & {x \geqslant 0} \\ {-1,} & {x<0}\end{array}\right.$
给定训练集：
$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$
定义感知机的损失函数
$L(w, b)=-\sum_{x_{i} \in M} y_{i}\left(w \cdot x_{i}+b\right)$ 

算法

随即梯度下降法 Stochastic Gradient Descent
随机抽取一个误分类点使其梯度下降。
$w = w + \eta y_{i}x_{i}$
$b = b + \eta y_{i}$
当实例点被误分类，即位于分离超平面的错误侧，则调整$w$, $b$的值，使分离超平面向该无分类点的一侧移动，直至误分类点被正确分类。

2024-08-20