感知机

• 二分类的线性分类模型
• 模型：$f(x)=sign(w·x+b)$。$w$，权值向量（weight vector）；$b$，偏置（bias）。对应于输入空间中的分离超平面。
  • 损失函数：对应于所有点到分离超平面的总距离。
  • $L(w,b)=-\sum y_i(w·x_i+b)$
• 策略：最小化损失函数
• 算法：基于随机梯度下降法对损失函数的最优化算法。
  • 学习率$0<\eta \le 1$
  • 原始形式
    • $w_k=w_{k-1}+\eta y_i{x}_i$
    • $b_k=b_{k-1}+\eta y_i$
  • 对偶形式
    • ${\alpha }_i=n_i\eta$
• 收敛性（Novikoff定理）：当训练数据集线性可分时。扩展权值向量$\hat{w}=(w^T,b{)}^T$，输入向量扩展$\hat{x}=(x,1)$。$i=1,2,...N$
  • (1) 存在$||{\hat{w}}_{opt}||=1$，使超平面${\hat{w}}_{opt}·\hat{x}=w_{opt}·x+b_{opt}=0$将训练数据集完全正确分开，且存在$\gamma >0$，使$y_i({\hat{w}}_{opt}·\hat{x})=y_i(w_{opt}{x}_i+b)\ge \gamma$
  • (2) 误分类次数k满足： $k\le (\frac{R}{\gamma }{)}^2$，其中$R=max\{||\widehat{x_i}||\}$
  • 定理证明