周报（2016-10-14）

1.PAC-Learnable：

• 1.定义
  X:输入空间，所有可能的数据
  Y：输出空间,所有可能标记
  concept  c:映射       $c: {X} \rightarrow Y$
  C:   希望学习得到的概念集合
  S:样本
  D：分布（函数）
  H：可能的concept
  $h_s$:样本中可能的concept
  m：样本大小
  样本误差：
  若对于任意实数$\epsilon >0,\delta >0$,X上的任意分布D，任意$c \in C$，都存在一个算法A和多项式（函数）$poly（...,....,....）$,满足： $m>poly(\frac {1}{\epsilon},\frac{1}{\delta},size(c))$,且
  $Pr[R(h_s)\leq \epsilon ] \geq 1-\delta$ ,则认为C是PAC-可学习的.
  若多项式（函数）$poly（...,....,....）$依赖于算法A，则称C是有效PAC可学习的。
• $2$ . PAC框架的性质
  不依赖于分布（函数）
  训练集和测试集取自相同分布（函数）

2.不可知PAC可学习

• 若对于任意实数$\epsilon >0,\delta >0$,X上的任意分布D，任意$c \in C$，都存在一个算法A和多项式（函数）$poly（...,....,....）$,满足： $m>poly(\frac {1}{\epsilon},\frac{1}{\delta},size(c))$,且
  $Pr[R(h_s)-\min R(h)\leq \epsilon ] \geq 1-\delta$ ,则认为A是一个不可知PAC-可学习的算法.

3.

• 贝叶斯误差：
  D：$X\times Y$上的分布
  h:   $X\rightarrow Y$
  

  $$R^{*}=\inf \limits_{h}R(h)$$
  当 R(h)=$R^*$时的h称为Bayes hypothesis 或者 Bayes classifier

• 噪声：
  

  $$noise(x)=min\{Pr[1|x], Pr[0|x]\}$$
  $R(h)-R^*=(R(h)-R(h^*))+(R(h^*)-R^*)$
  $h^*$：假设集合H具有最小误差的项
  $R(h)-R(h^*)$:估计项
  $R(h^*)-R^*$:近似项
  $h_s^{ERM}$:       由最小经验误差算法(ERM)返回的h
  $h_s^{ERM}=argmin \hat{R_s}(h)$

3.结构风险最小化方法（SRM）

• 考虑的是大小逐渐递增的假设集合H的递增无穷序列
  对于机器学习的一般模型必须从有限的数据集，随之会产生过拟合的问题。而SRM通过平衡模型的复杂度和拟合的相似度解决了这个问题。（From Wikipedia）
  $$h_s^{SRM}=argmin \hat{R_s}+complexity(H_n,m)$$