推导&实现：感知器准则&MSE算法&Fisher准则

1 感知器准则

1.1 推导

第二个类别的样本特征向量 \(\times -1\) ，再给所有样本增加一维表示 label ，第一类 label 等于 \(1\)，第二类 label 等于 \(-1\)

感知器算法采用最直观的准则，即最小错分样本数，（MSE的区别在于迭代更新 \(a\) 时不同）。将错分样本到判别界面距离之和作为准则，称为感知器准则，表示如下：

\[J(\boldsymbol{a}) = \sum_{\boldsymbol{y} \in Y }^{}{-\boldsymbol{a}^T \boldsymbol{y}} \tag{3} \]

其中 \(Y\) 为错分样本的集合。

为了求解感知器的准则函数，就是找到一个权矢量，使得惩罚函数最小化。我们使用机器学习中常用的梯度下降方法来迭代。惩罚函数对权矢量的梯度公式为：

\[\bigtriangledown J_p(\boldsymbol{a}) = \frac{\partial J_p(\boldsymbol{a})}{\partial \boldsymbol{a}} = \sum_{\boldsymbol{y} \in Y} {(-\boldsymbol{y})} \tag{4} \]

利用梯度下降，我们有：

\[\boldsymbol{a_{k+1}} = \boldsymbol{a_k} - \eta_k\bigtriangledown J_p(\boldsymbol{a}) = \boldsymbol{a_k} + \eta_k\sum_{\boldsymbol{y} \in Y} {\boldsymbol{y}} \tag{5} \]

其中 \(\eta_k\) 是学习率（或步长）。

1.2 算法步骤

我们得到下列感知器算法（批量调整版本）：

当然，我们都知道这种对所有错分样本放到一起进行修正的做法是不妥当的，更妥当的办法是对每一个错分样本都单独修正，且每次都使用同一个固定步长，假如设步长为1，得到单样本调整版本的感知器算法：

感知器算法特点：

当样本线性可分情况下，学习率 \(\eta_k\) 合适时，算法具有收敛性
收敛速度较慢
当样本线性不可分情况下，算法不收敛，且无法判断样本是否线性可分

1.3 代码实现

# mnist训练集，感知器准则实现5&8二分类
# 核心代码
class Perceptron(Model):
    def __init__(self, alpha=0.04, n_iter=20): #初始化
        self.alpha = alpha #学习率
        self.n_iter = n_iter #迭代次数
        self.loss_saver = [] #损失收集

    def fit(self, X, Y): #训练
        m, n = np.shape(X) 
        self.bias = 0 
        self.W = np.ones(n) # w的初值是全1的长度为 n 的向量

        for i in tqdm(range(self.n_iter)): # 循环迭代 显示进度条
            for x, y in zip(X, Y): #遍历所有样本
                y_now = np.dot(x, self.W) + self.bias # y_i=x_i*w+b
                if y * y_now < 0.: #如果分类错误 更新w和b
                    self.W += x * self.alpha * y 
                    self.bias += self.alpha * y
            self.loss_saver.append(self.acc(X, Y))# 迭代一次加一个acc进序列
            if 1-self.acc(X, Y) < EPS: # 结束
                return
    def predict(self, X): 
        return np.dot(X, self.W) + self.bias #预测值
    def acc(self, X, Y): 
        return metrics.accuracy_score(Y, np.sign(self.predict(X))) #正确分类的比例

2 最小均方误差算法

2.1 推导

假设我们有一组二分类数据集 \(D = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_n, y_n)\}\)，其中 \(\mathbf{x}_i\) 表示样本特征向量，\(y_i \in \{-1, 1\}\) 表示样本的标签，\(n\) 表示样本的数量。

将所有 \(y=-1\) 的样本都 \(\times -1\)，从而正确分类的样本都满足 \(x_iw>0\)

引入一个列向量 \(b=[b_1,b_2,...,b_n]>0\)，

定义损失函数为所有 \(b_i-x_iw\) 的平方和：

\[L = \sum_{i=1}^n (b_i-x_iw)^2 \]

此处包含两个我们需要求解的东西：\(w,b\) ，并且当我们确定 \(b\) 后，求 \(w\) 的偏导为0，此时 \(L\) 取最小值。所以：

\[\frac{\partial L}{\partial w}=2x^T(xw^*-b)=0\\ 移项得\ \ w^*=(x^Tx)^{-1}x^Tb \]

其中 \((x^Tx)x^T\) 为 \(x\) 的伪逆，记为 \(x^\#\)

接下来要做的就是迭代求解最优的 \(b\) ，本讲介绍的方法是梯度下降法：

\[b(k+1)=b(k)-c(\frac{\partial L}{\partial b})_{w=w^*}=b(k)+c(xw^*-b+|xw^*-b|)\\ \frac{\partial L}{\partial b}=\frac{\sum (w^Tx_i-b_i)^2}{\partial b}\\ \frac{\partial L}{\partial b}=-2(xw^*-b)=-2e_k\\ b(k+1)=b(k)+c(e_k+|e_k|) \]

2.2 算法步骤

将训练样本符号规范化，得 x，计算其伪逆 \(x^\#\)
初始化：\(b(1)=[1,1,...,1]^T,k=1,c\in(0,1)\) ，其中 \(b\) 只要为正即可
计算权重 \(w(k)=x^\#b(k)\) ，及误差 \(e(k)=xw(k)-b(k)\) ，注：\(x^\#=(x^Tx)^{-1}x^T\)
如果 \(e(k)\) 的所有分量都为负数，则算法结束，无解；

如果 \(e(k)=0\) ，则算法结束，输出权重 \(w(k)\) ;
令 \(k=k+1\)，返回步骤 3

2.3 代码实现

# mnist训练集，MSE算法实现5&8二分类
# 核心代码
class MSE(Model):
    def __init__(self, c=0.04, n_iter=20): 
        self.c = c
        self.n_iter = n_iter
        self.loss_saver = []

    def fit(self, X, Y):
        m, n = X.shape
        b = np.ones((m, 1)) #初始是一个全为1的列向量
        X = np.concatenate([X, b], axis=1) 
        Y = Y.reshape((-1, 1)) #转置
        X = X * Y #把-1类的样本的向量*-1

        self.b = np.ones(m, dtype=np.float) 
        X_shape = linalg.pinv(X) #x的伪逆

        for i in trange(self.n_iter): #对b用梯度下降法进行迭代
            self.W = np.dot(X_shape, self.b) #算出此时的w*
            self.err = np.dot(X, self.W) - self.b #计算误差
            self.b = self.b + self.c * (self.err + np.abs(self.err)) #更新b
            self.loss_saver.append(np.linalg.norm(self.err, ord=2)) #把loss加入序列
            if self.loss_saver[-1] < EPS: #结束
                return

    def predict(self, X):
        b = np.ones((X.shape[0], 1))
        X = np.concatenate([X, b], axis=1) #需要加一列全1（方程的常数项）
        return np.dot(X, self.W)

3 Fisher线性判别准则

3.1 推导

底层逻辑就是一个 LDA 推导：PCA主成分分析&LDA线性判别分析 - 缙云山车神 - 博客园 (cnblogs.com)

3.2 算法步骤

把两类样本分为 \(X_1,X_2\)
计算两类的均值 \(m_k=\cfrac{1}{N_k}\sum_{x_i\in X_k} x_i\ ,\ \ k=1,2\)
计算两类的类内散度矩阵 \(S_w^k=\sum_{x_i\in X_k} (x_i-m_k)(x_i-m_k)^T\)
计算总的l类内散度矩阵 \(S_w=S_w^1+S_w^2\)
计算 Fisher 最佳投影方向 \(w^*=S_w^{-1}(m_1-m_2)\)

3.3 代码实现

# mnist训练集，Fisher线性判别准则实现5&8二分类
# 核心代码
class Fisher(Model):
    def __init__(self, iter_n = 10):
        self.c = 0.
        self.iter_n = iter_n
        self.loss_saver = []
    @staticmethod
    def _cal_cov_avg(X):
        u = np.mean(X, axis=0) #均值向量
        cov = np.cov(X, rowvar=False) #协方差矩阵 衡量类内的相关程度
        return cov, u
    def fit(self, X, Y):
        Y = Y.reshape((-1, 1))
        X = X / 255 #把x缩小到0~1之间
        X_all = np.concatenate([X, Y], axis=1) #样本和label放一起
        X_0 = X_all[X_all[:, -1] == -1] #然后判断label颜色把两类分开
        X_1 = X_all[X_all[:, -1] == 1]
        X_0, X_1 = X_0[:, :-1], X_1[:, :-1] #把label割掉
        cov_0, u_0 = self._cal_cov_avg(X_0) #计算均值向量和协方差矩阵
        cov_1, u_1 = self._cal_cov_avg(X_1)
        s_w = cov_0 + cov_1 
        s_w_inv = linalg.pinv(s_w)
        self.W = np.dot(s_w_inv, u_0 - u_1) #按公式算的投影的超平面
        self.u_0 = np.dot(u_0, self.W) #把两个均值向量投影到平面上
        self.u_1 = np.dot(u_1, self.W)
        acc = 0.
        c = 0.# 初始的分割点
        for i in trange(self.iter_n): #对分割点进行迭代
            self.c = i / self.iter_n 
            l_acc = self.loss(X * 255, Y)
            self.loss_saver.append(l_acc)
            if l_acc > acc: #保留正确率最高的
                c = self.c
                acc = l_acc
        self.c = c
    def loss(self, X, Y): 
        return metrics.accuracy_score(Y, np.sign(self.predict(X)))
    def predict(self, X): 
        X = X / 255
        return -(np.dot(X, self.W) - (self.u_0 + (self.u_1 - self.u_0) * self.c))
        # 通过正负情况反映观测点在分割点的左边还是右边