机器学习与数据挖掘 第一讲 定义与PLA算法

1. 机器学习的实质
2. 机器学习的组成部分
3. 感知机模型举例

机器学习的定义与本质

Machine learning

Tom M. Mitchell定义：A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

即给定任务的条件下，机器学习在通过数据练习获得经验（如某模型或者假设），并可以通过某测量指标量化其对该任务的性能。

Essence

• 存在可学习的规律或模式
• 有能够学习到规律的数据
• 无法用精确的数学公式表达或无法编程实现

Component of Learning

• 输入：1. 数据集data 2.假设集合$H$
• 目标函数：$f$ --假设集合中的理想表达
• 输出：$g$ --通过提取data特征，在$H$中最终选取输出 $g\approx f$

PLA（Perceptron Learning Algorithm )

感知器（perceptron）1957年由Rosenblatt提出，是神经网络与支持向量机的基础。为二类分类的线性分类模型，输入为实例的特征向量，输出为实例的类别(取+1和-1二值)。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面。

组成部分

• 特征空间 $X\subseteq R^n$
• 输出空间 $Y=${-1,+1}
• 目标函数$h(x)=sign(w^{T}x)$

算法思路

1. 初始状态分类器认为所有数据为错误，任意找一数据修正，$w$为分离平面的法向量，分离平面垂直法向量
2. $x_g$为错分数据，则将原来的法向量和数据向量相加，得到旋转之后的法向量，进而不断修正分离超平面，直到所有数据正确分类。

修正思路：若$x_g$被错分为正例，则旋转后的$w+yx$靠近$X$向量；若为错分负例，则旋转后的$w+yx$远离$X$向量。

3. 通过不断遍历特征向量，校正$W_t$,达到最终$W_f$。

PLA算法终止条件

• 线性可分
• $\frac{W_f^T}{||W_f||}\frac{W_T}{||W_T||}\ge \sqrt{T}\cdot constant$ ,$T$为修正数。其证明可参考该博客。¹

此外，台大机器学习基石和【机器学习基础】从感知机模型说起对感知机模型提供了较好的图片解释。

R实现

# download the dataset
temp <- read.csv2("https://www.csie.ntu.edu.tw/~htlin/mooc/datasets/mlfound_math/hw1_15_train.dat",header = F,stringsAsFactors=FALSE,sep = "")
names(temp)=c("x1","x2","x3","x4","y")
# convert to numeric
indx <- sapply(temp,is.character)
temp[indx] <- lapply(temp[indx],function(x) as.numeric(as.character(x)))
str(temp)

PLA <- function(data,delta){
  x <- data[,-dim(data)[2]]
  y <- data[,dim(data)[2]]
  w <- c(0,0,0,0)
  b <- 0
  len <- length(y)
  i <- 1
  while (i<=len){
    if(y[i]*(x[i,]%*%w+b)<=0){
      ## update w and b
      w <- w+delta*y[i]*x[i,]
      b <- b+delta*y[i]
      i <- 1
    }
      else{
      i <- i+1
      }
    }
    return(list(w=w,b=b))
  }
  
  
w <- PLA(data=as.matrix(temp),delta=1)
w