机器学习的统计模型
任何一门学科都是由三个部分组成的：学习/研究的对象、对象之间的结合关系、控制这些关系的准则/公理。数学研究的是数与形，关系有代数、顺序和拓扑（集合之间的包含），公理是针对具体的量/形而提出的；比如距离三公理：非负、对称、三角不等式。物理研究自然物体（人类可见可感知的东西），物体之间如何分分合合，控制准则是力或能量。
机器学习是一门跨越多种学科的综合学科；涉及概率统计、线性代数、数学分析、数理逻辑、图论、优化理论、哲学、信息论、计算复杂性、控制论、生物学，等等。其研究对象是任务/问题的集合，目的是要搞清楚：什么是学习，机器能够学习吗？怎么学习？结合关系表现为算法，它揭示知识之间的逻辑关系；给出各种任务的快捷算法是机器学习的根本目标。控制公理基于人类或动物的道义准则或价值观；对于魔道，吃人的算法才是公理。
一个算法包括输入和输出两部分。对于一个能够学习的算法，其输入包括三部分：（1）需要认识的对象集X，比如一个地区的某个物种。在数字化的世界里，物种需要用一些数量特征来刻画；比如颜色、密度、表面张力等，这些信息可以用向量或张量来表示。（2）需要识别的特征Y，比如物种的味道、人的好坏、动物的凶残程度等。特征的量化表示不可能准确，实际上是学习者主观意识的反映，数学上可以看作是一个随机变量。（3）训练数据集T = {(xi, yi): i = 1, 2, …, n} ；也就是集合X × Y的一个随机样本。
学习算法的输出是一个预测规则p：X →Y，要对X中的每个对象x给出一个标识y。基于训练集T，自然要求p(xi) = yi，i= 1, 2, …, n。从X到Y的所有对应规则/函数的集合记为Y^X, 它的基数为|Y|^|X|。当X为无限集时，函数集达到连续基数c；即使当X，Y为有限集时，计算复杂度也可能是NP（非多项式）的。我们可以基于经验或计算的简便，提出一个预先假定的规则集H（ 潜规则) ，比如多项式函数甚至线性函数，把H嵌入到实数集R，再从R映射到Y。一个H所代表的，就是一种学习模型；一个算法是否具有学习能力，指的是能否从H中找出最佳的一个预测规则。
对于一个学习者，全体对象集X是未知的，其中个体x的正确标识 y =: b(x) 
Y更是未知的。我们把 (x，y) = z看成一个随机向量，满足某种未知的概率分布D；样本S假设是独立、随机同分布的，所满足的分布记为D^n。D在X上的边缘分布可以记为DX。
我们需要给出p的评估标准（Performance measure）。用p(x) 去预测x的正确标识y时，会有风险（risk）。风险函数R(p, D)) 通常定义为平均损失：E {L(p, z): z ~ D} = Integral {L(p, z) dF(z)}，其中F(z) 是z ~ D的累计概率分布函数；损失函数L(p，(x, y))有多种定义方法，任何表明p(x)与y的偏差的函数都行；比如数量的平方损失 (p(x) – y)^2, 向量的模损失 ||p(x) – y||，0-1损失 L = 0, 若p(x) = y; L = 1, 若 p(x) ≠ y。
为了评估预测p的质量，我们提出一个精度参数ε>0, 如果R(p, D) ≤ ε ，就称p是近似正确的；如果R(p, D) > ε , 则p称为学习者/p的失败。但分布D是未知的，风险函数R的值是无法计算的。我们只能用样本/训练数据集T去估计和验证。
基于某个样本T的风险函数R(p，T)，其值定义为 1/|T| { Sigma [L(p, (xi, yi)): i = 1, 2, …, |T|]} 。如果对该样本T，恰有p(xi) = yi对所有i，则R值为0；T对p过度 “适应” 了。然而，对于其它样本S, 就不一定有R(p, S) = 0了。我们需要的是接近R(p, D)的样本S：|R(p, S) – R(p, D)| ≤ ε。如果对于任何未知分布D，都有|R(p, S) – R(p, D)| ≤ ε, 样本S就具有 “ε-代表性”。在样本空间X × Y中，取到一个具有 “ε-代表性 “的样本的概率的下限，称为学习规则集H的信任度, 1 – δ。δ也是取到非代表性样本的概率上限。
一个学习任务/模型就表示为了：给定一个三元组 (Z, H, L), Z =X × Y，要求一个对应规则p, 使得：对于任意给定的 ε, δ
, 都存在一个正整数N(ε, δ)（称为样本复杂度），当样本数 n = |S| ≥ N时，对于Z上的任何分布D，都有，事件|R(p, S) – R(p, D)| > 
发生的概率P，小于δ；此时就称预测函数p是可能近似正确的（Probably Approximately Correct）, 假设规则集H是PAC可学习的。
找p的办法有多种，一种是使得最大平均损失极小化，也就是概率论中极小极大估计的思想。对于事先选定的训练集T = {（Tx, Ty）} ，可以要求p(Tx) = Ty；那就有R(p, T) = 0。对于任何一个独立同分布的样本S ~ D^n，样本数n = |S| > |T|; 在上确界Sup {R(p, S): S ~ D^n }中，寻找使其达到极小的预测函数p*: Sup { R(p*, S): S ~ D^n} = Inf p H [Sup { R(p, S): S ~ D^n}]；这就转化为了和式的条件极值问题，可以用线性规划、Lagrange乘子法、变分法等求解。
可以证明，当H为有限集合，Y只有二元标识{0， 1}时，可以取N = [ln(2|H|/δ)]/2ε2；也就是说，有限的潜规则集都是PAC可学习的。
对于无穷集H（X必为无穷集），可以把它先限制在X的一个有限子集C上：H|C = {h(C): h H}, 其基数为|Y|^|C|。如果H|C包含了从C到Y的所有函数，就称H遮蔽（shatters）C。能够被H遮蔽的有限集C的最大基数|C|, 称为H的VC维度（由Valdimir Vapnik 和 Alexey Chervonenkis在1970年提出）。如果H可以遮蔽任意大的子集C，它的VC维度就是无穷大。可以证明，H是PAC可学习的，当且仅当它的VC维度是有限的。
这在潜规则集H与样本复杂度|S|之间就得有一个折衷（trade off）：选择广泛与低风险不可兼得；因为没有免费的午餐。具体来说，对于任何一个无限集X和二元标识Y = {0， 1}，设L为0-1损失函数；A是任何一个推导预测函数p的算法；一定存在X × Y上的一个概率分布D，使得，有一个预测函数f满足R（f, D） = 0, 以及至少1/7的概率取到一个样本S，其基数< |X|/2，满足R(p，S) >=1/8。
我们还可以使用Bayes估计：凭经验或专家的意见，对X提出某类先验分布DX（比如均匀分布、正态分布等），按照预定规则集H（其中的函数必须满足训练数据集T）去计算Y（标识符）的分布（可以称为后验分布），然后在H中选取一个使得风险函数R(p, D)达到最小的预测p。再选择一个有代表性的样本S，来加以验证: R(p, S) < R(p, D) + ε。
按照经验风险极小化（ERM）方法推导预测函数的算法A，还需要考虑其运行时间/计算复杂度。对于给定的一个学习任务（Z，H， L），以及学习精度和信任度ε, δ ∈ (0, 1)，我们说算法A在时间O（F(ε, δ）)内完成了任务，如果（1）A本身的运算次数不超过F的一个常数倍，（2）A导出的预测函数p给任何一个样本S|X作出标识的运算次数不超过F的一个常数倍，（3）p是PAC的：事件R(p, D) ≤ min p* ∈H R(p*, D) + ε的概率至少为 1 – δ。
一个算法A称为有效的，如果它能在多项式P(n，1/ε, 1/δ)内解决一系列的学习任务（Zn, Hn, Ln）, n = 1, 2, …. . 对于可实现的Hn, 即Hn包含一个函数p, 它在训练集T上无偏差，p(Tx) = Ty，ERM算法是有效的。如果不作此假定，那么许多常见的函数类H，ERM算法都是非多项式的。除非P = NP，我们不可能找到有效的算法。化NP为P，就成了人类的终极挑战。
