PLA输出【离散类别】

核心公式

h(x) = $sign({\sum }_{i=1}^d{w}_i{x}_i-threshold)$
增广形式：$x_0=1,w_0=-threshold,h(x)=sign(w^{T}x)$
其中w是权重向量，x是输入特征向量，sign是符号函数

1.PLA感知器算法

寻找最优权重w，使得损失函数$l_{in}=0$

【损失函数】${\ell }_{in}=[[y_n\ne \widehat{y_n}]]$ 即0-1损失函数

【步骤】

• 初始化：w₀=0
• 迭代：对于错分样本 $(x_n,y_n)$,更新权重$w_{t+1}=w_t+y_n{x}_n$
• 终止：所有样本都被正确分类或达到最大迭代次数

注意：迭代结果与样本遍历顺序相关

2.收敛性分析

【证明】线性可分情况下，PLA 经有限次迭代必收敛到正确分类面。
证明逻辑：$w_t$​与$w_f$​方向逐步接近，且$w_t$​模长增长有界,迭代次数上界：$T\le \frac{R^2}{{\rho }^2}$
其中$R^2=ma{x}_n||x_n|{|}^2$(样本最大模长平方)，$\rho =mi{n}_n{y}_n\frac{w_f^T}{||w_f||}{x}_n$(样本最小规范间隔)​

3.Pocket算法——处理线性不可分问题

【步骤】

• 初始化：$w_0=0$，口袋权重$\hat{w}=w_0$
• 迭代更新：若$w_t$​错分样本，更新$w_{t+1}=w_t+y_n{x}_n$；若$w_{t+1}$​错分样本数少于$\hat{w}$，则替换$\hat{w}=w_{t+1}$
• 停止条件：达到迭代次数

附录：

PLA关键代码（以二维数据为例）

# PLA算法实现
def pla_train(X, y, max_iter=1000, random_state=None):#max_iter指最大迭代次数
    n_samples, n_features = X.shape
    
    # 样本增广：第一列加1，增广后格式[1, x1, x2]
    X_augmented = np.hstack([np.ones((n_samples, 1)), X])  
    # 初始化增广权向量：维度n_features+1
    w_augmented = np.zeros(n_features + 1)  
    
    for _ in range(max_iter):
        # 寻找误分类样本
        misclassified = []
        for i in range(n_samples):
            if y[i] * np.dot(w_augmented, X_augmented[i]) <= 0:
                misclassified.append(i)
        
        # 若所有样本正确分类，停止迭代
        if not misclassified:
            print(f"PLA在第{_+1}次迭代收敛，所有样本正确分类")
            break
        
        # 随机选择一个误分类样本更新权向量
        i = np.random.choice(misclassified)
        w_augmented += y[i] * X_augmented[i]  
    
    return w_augmented


def pla_predict(X, w_augmented): # 预测函数
    n_samples = X.shape[0]
    # 预测函数增广
    X_augmented = np.hstack([np.ones((n_samples, 1)), X])
    # 决策值计算：w0*1 + w1*x1 + w2*x2
    scores = np.dot(X_augmented, w_augmented) 
    return np.where(scores >= 0, 1, -1)