感知机

2019-06-27 本文已影响0人 To_QT

1. 基本概念

1.1 数据要求

数据线性可分，其中，输入：特征向量；输出：类别。
是一種判別模型。

1.2 基本形式

$f(x)=sign(\boldsymbol{w}·\boldsymbol{x}+b)\tag{1.1}$
其中：
$sign(x)=\left\{\begin{matrix} +1 &, x\geq 0\\ -1 &, x< 0 \end{matrix}\right.\tag{1.2}$

1.3 几何意义

首先，根据向量的本质可知， $\boldsymbol{x}$ 的集合 $\chi$ 所张成了一个空间，而线性方程 $\boldsymbol{w}·\boldsymbol{x}+b=0$ 相当于在这个空间中切一刀，希望能够将不同种类的数据最大限度的分开。其中， $\boldsymbol{w}$ 是超平面的法向量， $b$ 是超平面的截距。

2. 学习策略

2.1 目标

希望能够将不同种类的数据区分开。

2.2 损失函数

使分类点到超平面的距离之和最小。

回忆一下二维坐标中点到直线的距离公式。
$d=\left | \frac{AX_0+BY_0+C}{\sqrt{A^2+B^2}} \right |\tag{2.1}$

2.2.1 思路如下：

那么，在 $\boldsymbol{x}$ 的集合所张成的空间中，任意一点到该平面的距离为 $-\frac{|wx+b|} {||w||}$ 。

from《统计学习方法》
图中， $-\frac{b} {||w||}$ 指的是点A（原点）到线性方程的距离。
在分类正确的情况下， $y_i=1$ 时，一定有 $(\boldsymbol{w}·\boldsymbol{x_i}+b)>0$ ，或者是 $y_i=-1$ 时 $(\boldsymbol{w}·\boldsymbol{x_i}+b)<0$ 。
但是假设第 $i$ 个点 $(\boldsymbol{x_i}, y_i)$ 分类错误了，则有 $-y_i(\boldsymbol{w}·\boldsymbol{x_i}+b)>0$ ，则误分类点到超平面的距离为 $-\frac{y_i(wx+b)} {||w||}$ ，则 $n$ 个分类错误的点到该超平面的距离为： $-\frac{\sum _{i=1} ^{n} y_i(wx+b)} {||w||}$

因此，损失函数即为：
$-\sum _{i=1} ^{n} y_i(wx+b)\tag{2.2}$

强调一点:从直观上应该使用误分类点数目最少作为其目标函数,但是由于该表达式不可导,不利于优化参数 $w$ 和 $b$ ,因此选取其误分类点到分离超平面的距离作为其目标函数.
根据公式可知,当误分类点越多,则损失函数值越大,误分类点越少,损失函数值越小.

3. 学习算法（基本形式）

3.1 基本概念

随机梯度下降算法，不是一次使 $n$ 个误分类点梯度下降，而是一次选取一个误分类点梯度下降。
存在两个问题：往哪走与走多远的情况。

往哪走？梯度告诉你走的方向，损失函数对 $w$ 和 $b$ 的求导计算结果为：
$\bigtriangledown w_{L(w,b)}=-\sum_{x_i \in M}y_ix_i\tag{3.1}$
$\bigtriangledown b_{L(w,b)}=-\sum_{x_i \in M}y_i\tag{3.2}$

注意:公式 $(3.1)$ 和公式 $(3.2)$ 中参数的更新也只是说明了该往哪个方向走

走多远？没人知道，设定一次走多远 $\eta$ ，剩下的那就只能一小步一小步的走吧。

对于计算机来说,由于计算是串行化的,不能够像人一样一次性从中找出所有的误分类点,只能一个点一个点的去修正(每次根据一个错误点调整参数,直到没有误分类点为止).
所以,记 $w_i$ 为第 $i$ 次调整的结果,寻找的参数表达式在计算机中实际上是这样的:
$min_{w,b} L_i(w,b) = min_{w,b} L_{1,2,...,i-1}(w_{i-1},b_{i-1})+y_i(w_ix_i+b)$

于是乎，权重与偏差的更新：
$w\leftarrow w+\eta y_ix_i\tag{3.3}$
$b\leftarrow b+\eta y_i\tag{3.4}$
$\eta$ 为步长

《统计学习方法》-感知机学习算法的原始形式

3.2 小结

在基本模式中，没有什么难以理解，通俗的说就是来一个值，根据计算结果调整一下权重和偏差，如此直到线性可分的数据集中没有错误的分类选项。

4. 学习算法（对偶模式）

有的人嫌一小步一小步的走太麻烦，想换一个方法：你告诉我沿一个方向走多远，我一次性走完，然后再换其他的。（说白了就是一次一次的更新太麻烦，我先攒着，看看你需要更新多少次，我一口气给你全部更新完【分期付款和全款的区别】）
于是乎，对偶模式诞生了。与基本形式类似，也是通过不断调整权重和偏差来实现对数据集的分类，但是，还是有原来的两个问题：往哪走，走多远？

往哪走？这个问题没有其他的解决方式，还是和基本形式一样，梯度告诉你。
走多远？在基本模式中，是站在局部视角走，现在，切换到上帝视角看一看。
The God says：
例如：有 $x_1, x_2, x_3, x_4, x_5$ 5条数据，如果这5条数据仅使用一次，那是不合理的，所以你要将这5条数据进行反复的抽取，每一条数据就可以被多次使用，第 $i$ 条数据被抽取的次数记为 $n_i$ 。那么，从初始权重到最终训练好之后，权重经过 $N$ 次更新后，最后会变成这个样子：
$w = \sum _{j=1}^{N} \eta·n_j·y_j·x_j$
$b = \sum _{j=1}^{N} \eta·n_j·y_j$
嗯，从上面可以看出每个方向走多少步（ $n_i$ 说明了一切：第 $i$ 个实例点因为误分类而进行更新的次数）

因此，你需要做如下改变：

4.1 判定表达式的改变

原先 $w$ 代表第i次更新后的结果，现在站在上帝视角可以看出， $w= \sum _{j=1}^{N} \eta·n_j·y_j·x_j$ ，所以，感知机模型就变成了 $f(x)=sign( \sum _{j=1}^{N} \eta n_jy_jx_j·x+b)$

4.2 对偶模式的权重更新方式

在基本形式中，每一次权重是这么更新的：
$w_{i+1} \leftarrow w_i+\eta·y_i·x_i, i \in N$

然而，在对偶模式中，权重按照每条数据被学习的次数进行更新。对偶模式的权重更新就变成了这个样子了：
$\eta·n_{j+1} \leftarrow \eta·n_j+\eta=(n_j+1)·\eta$
$b_{j+1} \leftarrow b_j+\eta·y_j$

4.3 Gram 矩阵

理解感知机对偶形式及Gram矩阵作用——云边的布里茨

5. 参考文献

1.《统计学习方法》
2.理解感知机对偶形式及Gram矩阵作用
3.感知机中的对偶形式理解

6. python代码实现

6.1 基本模式

class Perception(object):
    def __init__(self, input_vecs, labels, activation, lr=0.1):
        '''
        感知机模型权重以及偏置项的初始化
        :param input_shape: <tuple>需要输入层维度信息
        :param activation: <funciton>激活函数
        :param lr: <float>学习率
        '''
        self.input_vecs = input_vecs
        self.n_features = input_vecs.shape[1]
        self.n_nums = input_vecs.shape[0]
        self.activation = activation
        self.weight = np.zeros((1, self.n_features))
        self.bias = np.zeros((1, 1))
        self.lr = lr

    def predict(self, input_vec):
        '''
        输入感知机运算结果
        :param input_vecs: <np.ndarray>训练数据
        :return:对ndarray中的逐元素应用激活函数
        '''
        output = np.dot(input_vec, self.weight.T) + self.bias
        return np.apply_along_axis(self.activation, axis=1, arr=output)

    def _update_weight(self, index_nums, delta):
        '''
        更新权重
        delta_weights = lr * (t - y) * x_i
        w是与x_i输入对应的权重项, t是训练样本的实际值, y是感知器的输出值，lr是学习速率
        ------
        :param input_vecs: <np.ndarray>训练数据
        :param delta: <np.ndarray>误差项
        :return:
        '''
        delta = np.tile(delta, (self.n_features, 1))
        delta_weight = np.dot(self.input_vecs[index_nums].T, delta)
        self.weight += delta_weight

    def _update_bias(self, delta):
        '''
        更新偏差
        delta_bias = lr * (t - y)
        :param delta: <np.ndarray>误差项
        :return:
        '''
        self.bias += delta

    def forward(self, nums, labels):
        '''
        前向计算感知机的输出值
        :param nums: 训练样例的数量
        :param input_vecs: 训练样本的特征值
        :param labels: 训练样本的真实值
        :return:
        '''
        for k in range(nums):
            print('%d th iterations' % k)
            for inums in range(self.n_nums):
                output = self.predict(input_vecs[inums])
                delta = self.lr * (labels[inums] - output)
                self._update_weight(inums, delta)
                self._update_bias(delta)
            # print('weights;', self.weight)
            # print('bias;', self.bias)
            print('output:', self.predict(input_vecs))

6.2 对偶模式

class PerceptionDualModel(object):
    def __init__(self, input_vecs, labels, activation, lr=1):
        '''
        感知机模型权重以及偏置项的初始化
        :param input_vecs: <np.ndarray>输入层的特征值
        :param labels: <np.ndarray>输入层对应的标签
        :param activation: <funciton>激活函数
        :param lr: <float>学习率
        '''
        self.input_vecs = input_vecs
        self.labels = labels

        self.activation = activation
        # 训练集特征的数量
        self.n_features = input_vecs.shape[1]
        # 训练集的数量
        self.n_nums = input_vecs.shape[0]
        self.lr = lr

        # n_i代表第i类数据使用的次数
        self.n = np.zeros((self.n_nums, 1))
        self.bias = 0

        # 计算Gram矩阵，为权重训练做准备
        self.Gram_metrix = self.calculate_Gram()

    def calculate_weights(self):
        '''
        根据公式计算权重
        weights = \sum_{i=1}^{N} n_i * lr * xi * yi
        :return:
        '''
        tmp = np.multiply(self.lr * self.n, self.labels)
        self.weight = (np.dot(tmp.T, self.input_vecs)).T

    def calculate_bias(self):
        '''
        计算偏差
        bias = \sum_{i=1}^{N} n_i * lr * yi
        :return:
        '''
        self.bias = np.dot(self.lr * self.n.T, self.labels)

    def calculate_Gram(self):
        return np.dot(self.input_vecs, self.input_vecs.T)

    def train(self, num_index):
        '''
        对感知机的权重进行驯良
        :param num_index: <int>输入数据的行标签，同时也意味着第几类数据
        :return:对ndarray中的逐元素应用激活函数
        '''

        output = np.dot(
            self.Gram_metrix[num_index],
            np.multiply(self.lr * self.n, self.labels)
        ) + self.bias
        return self.activation(output)

    def _update_weight(self, delta, num_index):
        '''
        更新权重
        n_i * lr = n_i * lr * + lr
        w是与x_i输入对应的权重项, t是训练样本的实际值, y是感知器的输出值，lr是学习速率
        ------
        :param delta: <np.ndarray>误差项
        :param num_index: <int>输入数据的行标签，同时也意味着第几类数据
        :return:
        '''
        # if delta == 0:
        #     print(num_index, ':分类正确')
        # else:
        #     print(num_index, ':分类错误')
        self.n[num_index] += delta

    def _update_bias(self, delta):
        '''
        更新偏差
        delta_bias = lr * y_i
        :param delta: <np.ndarray>误差项
        :return:
        '''
        self.bias += delta * self.lr

    def _predict(self, input_vec):
        '''
        根据特征值计算分类标签
        :param input_vec: 输入特征值
        :return:
        '''
        self.calculate_weights()
        # print('weights;', self.weight)
        # print('bias;', self.bias)
        predict = np.dot(input_vec, self.weight) + self.bias
        return np.apply_along_axis(self.activation, axis=1, arr=predict)


    def forward(self, nums):
        '''
        前向计算感知机的输出值
        :param nums: 训练样例的数量
        :param input_vecs: 训练样本的特征值
        :param labels: 训练样本的真实值
        :return:
        '''
        for k in range(nums):
            print('%d th iterations' % k)
            for num_index in range(self.n_nums):
                output = self.train(num_index)
                delta = self.labels[num_index] - output
                self._update_weight(delta, num_index)
                self._update_bias(delta)
            print(self._predict(input_vecs))

6.3 激活函数与训练数据获取

def activation(x):
    '''
    对x中的所有元素逐元素的进行操作
    :param x:
    :return:
    '''
    return 1 if x > 0 else 0

def getTrainData():
    '''
    得到输入数据和输出数据
    :return:
        input_vecs<ndarray>：输入数据
        labels<ndarray>：标签
    '''
    # 构建训练数据
    # 输入向量列表
    # input_vecs = np.array([[1, 1], [0, 0], [1, 0], [0, 1]])
    # and
    # labels = np.array([1, 0, 0, 0])
    # or
    # labels = np.array([1, 0, 1, 1])

    input_vecs = np.array([[3, 3], [4, 3], [1, 1]])
    labels = np.array([[1], [1], [0]])
    return input_vecs, labels

6.4 函数调用

if __name__ == '__main__':
    input_vecs, labels = getTrainData()
    # ================ 基本模式 ================#
    P = Perception(input_vecs, labels, activation, lr=1)
    P.forward(10, labels)
    print(P.predict(np.array([[8, 6]])))

    # ================ 对偶模式 ================#
    P = PerceptionDualModel(input_vecs, labels, activation)
    P.forward(10)
    print(P._predict(np.array([[8, 6]])))

感知机