使用Bin Model来回答Machine Learning机制的合理性

Motivation

Machine leanring的核心思想是：通过大量的数据来拟合出模型（hypothesis）的参数，进而使用参数齐全的模型来做出预测。模型的本质是用数学的形式来描述你对数据的一种偏见、看法和主观感受。它以数学的方式阐述了：“你认为”这堆数据是按照什么样的规则被产生的。

那么既然是“主观认为”，要将其变成令人信服的相对客观的规律，就需要你使用各种方式来证明你的这种“认为”是合情合理的。

最直观的“证明”当然是：对给出的数据集（training data）我的模型都能够做到完美预测。但这种证明的一个强有力的反例是：只需要构建一个模型将所有training data的结果记住，而在其它数据点做任意的预测，也能满足。

显然，这样的模型毫无意义，等同于：只掌握了课程考试需要的题目，并不意味着你掌握了这门课程。

那么，更广泛地讲，你所能得到的数据集，永远只能是一个局部。模型是产生数据的机制，它可以产生无数的数据，而training data只是一个模型产生出来的一个特定的、小的结果集合。一系列直指核心的问题是：

• 为什么可以通过局部（training data）来获得全局的运转机制（模型）？
• 这样的预测，其准确度是多少？
• 有精确的“数量关系”来描述局部样本预测全局机制准确性吗？

无法回答这些问题，machine learning就没有了存在的意义，所有模型参数拟合将变为一厢情愿的瞎忙。而bin model的引入，便是为了系统性地回答这些根本性的问题。

构建Bin Model

在详细地讨论之前，我们首先需要区分"真正的"模型和"假设的"（hypothesis）模型。所谓真实的模型，就是这堆数据真正产生的机制。这只是一个理想中的存在物，如同上帝的存在。引入它，仅仅是为了方便讨论，将不确定性控制在一个概念中。而hypothesis，就是我们根据数据所得出的一种偏见，即我们认为这堆数据会按照什么样的机制来被产出。

不妨假设那个如同上帝般存在的真实模型为$f$f，即一个函数 $f: X \rarr Y$f:X→Y 。我们的偏见所构成的模型为$h$h，即函数 $h: X \rarr Y$h:X→Y。我们要做的便是找到足够好的$h$h，使得它能够尽可能地逼近$f$f。什么叫做尽可能地逼近f呢？就是在对于 $f$f 定义域$X$X上的点$x$x，使其能够满足 $h(x) = f(x)$h(x)=f(x) ，这样的点越多，则说明 $h$h 越是逼近 $f$f 。

如此一来，对于 $\forall x \in X$∀x∈X ,只有关于模型 $f$f 和假设 $h$h 只有两种结果：

• $h(x) = f(x)$h(x)=f(x)
• 或 $h(x) \neq f(x)$h(x)̸​=f(x) .

如果把整个$X$X看作是bin里面的所有弹珠，那么，可以把满足 $h(x) \neq f(x)$h(x)̸​=f(x) 的 $x$x 当做桔色弹珠，把满足 $h(x) = f(x)$h(x)=f(x) 的点当做是绿色弹珠。

(为什么要把 $h(x) \neq f(x)$h(x)̸​=f(x) 当做主体——桔色弹珠？因为我们对误差更感兴趣，也即是通过样本的误差，来考察总体的误差。)

那么，我们要回答的核心列表中问题便可以转换为：通过training data，即从bin里抽取出来的一部分弹珠颜色的结果，我们能够对整个bin里的弹珠颜色成什么样的分布说些什么呢？

通常，直接考察这个bin中桔色弹珠的比例是困难和不切实际的。在工业生产中的做法当然是取一部分的小样，即通过样本，来倒推整个总体的分布。

此时，引入数学变量：

• 设整个bin中（即真实的总体）桔色弹珠的比例为 $\mu$μ ，那么相应的绿色弹珠的比例就为 $1-\mu$1−μ 。
• 设取出来的样本中（training data）中桔色弹珠的比例为 $\nu$ν ，那么相应的绿色弹珠的比例为 $1-\nu$1−ν 。

回顾我们间接要回答的核心问题，即是：通过小样本的 $\nu$ν （即通过在training data中看到的 $h$h 和 $f$f 的误差），我们能够对真实的总体 $\mu$μ （即在 $f$f 整个定义域上 $h$h 和 $f$f 的误差 ）说些什么呢？

在数学上，有 Hoeffding’s Inequality 给出的一个结论：

$\mathcal{P} [|\mu -\nu |\gt \epsilon] \leq 2 \exp{(-2\epsilon^2 \cdot N)}$P[∣μ−ν∣>ϵ]≤2exp(−2ϵ2⋅N)

这即是说，当样本足够多时， $h$h 和 $f$f 在"training data上的误差"（ $\nu$ν ）将会同它们在"总体上的误差"（ $\mu$μ ）非常接近。并且，这个接近程度可由上述不等式来做数值上的度量。

下面使用更形式化的语言来说明：

• 假设数据产生的真实机制为：$f: X\rarr Y$f:X→Y
• 一个待探讨的、确定的假设为：$h: X \rarr Y$h:X→Y
• training data按照定义在$X$X上的概率分布 $\mathcal{P}$P 从 $X$X 中被取出。
• 在training data上 (known)，$h$h 同 $f$f 的误差期望定义为 $E_{in}$Ein​ ，表示in training data的误差。
• 在非training data上 (unknown)，$h$h 同 $f$f 的误差期望定义为 $E_{out}$Eout​ ，表示out of training data的误差

$E_{in}$Ein​ 和 $E_{out}$Eout​ 满足：

那么，根据 Hoeffding’s Inequality 我们有：

$\mathcal{P} [|E_{in}(h) -E_{out}(h) |\gt \epsilon] \leq 2 \exp{(-2\epsilon^2 \cdot N)}$P[∣Ein​(h)−Eout​(h)∣>ϵ]≤2exp(−2ϵ2⋅N)

即，当样本数量足够大时， $h$h 和 $f$f 在整个$X$X 上的误差，便能够由 $h$h 和 $f$f 在training data上的误差来体现。如此，也就回答了最开始的根本性的问题，为什么我们只需要考察在training data上 $h$h 的表现，便能够知晓它在整个 $X$X 上的表现：只要training data的数量足够大。并且，对于不同的精度，这个training data的数量需要有多大？这同样可以由 Hoeffding’s Inequality 来回答。