今天讲的课题就是Noise and Error。其中，noise就是噪音，error就是错误，我们要研究的就是在有noise的情况下，怎么衡量这些error。

Noise and Probablistic Target

我们上节课已经掌握了机器学习中最重要的一项工具 - vc dimension。我们知道如果我们的hypothesis set的vc dimension是有限的，而且我们有足够多的数据，而且我们的算法又能够找到一个\(E_{in}\)很小的hypothesis，那我们就大概可以说我们学到了东西。

今天我们就从这里出发，对于在推导vc bound中的假设，我们考虑怎样放宽它们，来让我们对vc bound的了解能够放宽到更多的问题上。

我们先来复习一下我们学过的learning flow： 图8-1

通过前面的学习，我们知道，好的hypothesis set是vc dimension最finite的，好的hypothesis是\(E_{in}\)是最低的。经过几个礼拜的推导，我们知道在这样的情况下，我们是能够做到学习的。那如果有了noise的情况下，好像我们也还可以设计机器学习算法（例如pocket算法），但是这对我们之前理论的推导会不会产生影响呢？这就是现在我们的课题。

来看noise的一些例子： 图8-2

问题：如果customer information错了，但并没有影响它的label，这种情况下还算noise吗？

所以不管是input x还是output y，都可能有noise。那有这些noise的情况下，我们的vc bound还是不是可以很好地作用呢？

为了回答这个问题，我们要从vc bound的核心 - 估计罐子中橘色弹珠的比例出发：

之前我们研究的都是确定性（deterministic）弹珠，即：

  • 弹珠\(\mathbf{x} \sim P(\mathbf{x})\)
  • 确定的颜色由\([f(\mathbf{x}) \neq h(\mathbf{x})]\)决定

而有了noise之后，我们更像是在研究非确定性（non-deterministic）的弹珠：

  • 弹珠\(\mathbf{x} \sim P(\mathbf{x})\)
  • 不确定的颜色\([y \neq h(\mathbf{x})]\)，其中\(y \sim P(y|\mathbf{x})\)

也就是说，这个弹珠的颜色是变来变去的。比如60%的时间是绿色，40%的时间是橘色等等。但是整个罐子看，还是会有一个橘色弹珠的比例的。我们还是可以抽样，并记录抽出弹珠的瞬间橘色弹珠的比例。这种会变色的弹珠，我们称为probablistic marble。对应到学习问题中，就是有noise的情形，也就是说label会变来变去。既然我们还是可以用抽样的方式估计弹珠比例的话，那无论是deterministic还是probablistic的弹珠，vc bound都成立： 图8-4

整合一下，就是说只要我们的每个example（\((\mathbf{x}, y)\)）在training和test过程中都i.i.d.地来自某个分布\(P(\mathbf{x}, y)\)的话，那我们整个的vc bound的架构都是成立的。

我们一般把\(P(\mathbf{x}, y)\)叫做target distribution：

  • 可以被看做理想的mini-target + noise
    • 比如\(P(o|\mathbf{x}) = 0.7, P(x|\mathbf{x}) = 0.3\)
    • 理想的mini-target \(f(\mathbf{x}) = o\)
    • noise的水平就是0.3
  • 之前用的deterministic target f是target distribution的一种特殊情况：
    • \(P(y|\mathbf{x}) = 1\)，当\(y = f(\mathbf{x})\)时
    • \(P(y|\mathbf{x}) = 0\)，当\(y \neq f(\mathbf{x})\)时

今后在使用target distribution时，和我们之前使用target function并没有什么不一样。

今后我们学习的目的就是：在那些经常出现的输入点（相对于\(P(\mathbf{x}\)））而言，我们要尽量预测的准一点（相对于\(P(y|\mathbf{x})\)）.

现在，我们有有了新的learning flow： 图8-5

这样一来，我们就解释了pocket算法，因为即使在有noise的情况下，vc bound还是成立的。

Error Measure

在整个learning flow中，我们一直有一步，就是衡量g和f一不一样。

在之前，我们衡量的标准是\(E_{out}\)： \[ E_{out}(g) = \epsilon_{\mathbf{x} \sim P}[g(\mathbf{x}) \neq f(\mathbf{x})] \]

注：这里的\(\mathbf{x} \sim P\)是指按照P从X中sample出\(\mathbf{x}。\)

更一般地说，我们要有一个衡量误差的方式：\(E(g, f)\)。

我们之前使用的E有三个特性：

  • out-of-sample：还没有看过，未来抽样出来的\(\mathbf{x}\)
  • pointwise：可以在单个\(\mathbf{x}\)上衡量，然后做抽样的平均
  • classification：我们之前研究的只是classification，所以看的只是prediction是否等于target。（通常把classification error叫做‘0/1 error’）