这个关于ML的系列中，我想总结下一些基础和经典的算法，包括理论，实现，以及面试点。这个系列主要参考的文献是[1,2,3]。
做为这个系列的第一篇，我们会讨论PAC Learning。它确定了理论体系，为之后的算法讨论奠定了基础。
既然说机器学习，那显然就是让机器能够自动学习到某种知识，模式，从而在之后能给出有意义的行为。学习算法有很多种，我们会在之后的篇章中讨论，在本篇中，我们首先确定一种算法训练以及预测的流程，或者说体系。
ERM
不妨问自己一个问题，在日常生活中，我们是怎么学习，理解新知识，再应用的呢？假设说你要应付一个考试，而且还有一些往年的卷子。一个很直观的想法就是把这些卷子写了，再根据答案，看看自己哪里错了，从而订正理解有问题的点。这样，即使我们不知道真正的考试试卷，我们至少不会做错这些已经见过的题（希望如此）。
ERM (Empirical Risk Minimization) 就是这样一种根据经验的学习流程。假设说我们有training set $S$, 它是从distribution $D$中采样得来的。这些数据的真实label是由函数$f$所确定的。虽然我们的目标是找到算法$h_S$，使得其在$D$和$f$上的error最小，但是由于$D$和$f$往往是未知的，我们只能选择那些在training set上表现最好的算法。
正式来说，定义training/empirical error为
这里$m$是training set的大小，$[m]=\{1, \dots, m\}$。Empirical Risk Minimization就是找到算法$h$，其在$S$上的empirical error最小。
[1] Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David
[2] 机器学习西瓜书，周志华
[3] 统计学习方法(第二版), 李航