机器学习与高维信息检索 - Note 2 - 统计决策和机器学习_信息检索问题 机器学习

2. 统计决策和机器学习

基本问题是，对于随机变量$X\in {\mathbb{R}}^p$中的某些观测，我们想获得随机变量$Y$的 "最可能 "值。为简单起见，我们假设$Y$在$\mathbb{R}$中的实现。我们进一步假设得到的联合概率密度$p_{X,Y}(x,y)$已经给出。

例2.1
$X$是一个人的（矢量）图像。 在下面的图2.1中，这个观测表示了一张只包含一个像素的图片，它的灰色程度各不相同。

$$Y=\{\begin{array}{ll}1:& X\text{ is picture of person }\mathrm{A}\\ 0:& X\text{ is not }\end{array}$$

其目的是预测给定$X$的$Y$。如果有个叫$\mathrm{A}$的人，他主要穿着深色衣服

图2.1: 两个离散随机变量$X$和$Y$的联合概率分布

有理由认为，事件的各自概率表现为：$p_{42}>p_{32}>p_{22}>p_{12}$ 和$p_{11}>p_{21}>p_{31}>p_{41}$.

为了确定 "最可能 "的含义，我们考虑平方损失函数${}^1$

${}^1$ 注意，其他损失函数也是可能的，而且也确实有意义，选择平方距离只是出于方便的原因。

$$L(Y,f(X))=(Y-f(X){)}^2.\text{\hspace{1em}(2.1)}$$

我们要选择$f$，使损失函数的预期值，即所谓的预期预测误差
$$\mathrm{EPE}(f)=\mathbb{E}[L(Y,f(X))]$$
是最小的。使用第1.2小节中描述的工具进行简单计算，可以得到

$$\begin{array}{rl}\mathrm{EPE}(f)& =\mathbb{E}[L(Y,f(X))]=\mathbb{E}\left[(Y-f(X){)}^2\right]\\ & ={\int }_{{\mathbb{R}}^p\times \mathbb{R}}(y-f(x){)}^2{p}_{X,Y}(x,y)\mathrm{d}x\mathrm{d}y\\ & ={\int }_{{\mathbb{R}}^p}\underset{=:{\mathbb{E}}_{Y\mid X=x}\left[(Y-f(X){)}^2\right]}{\underbrace{{\int }_{\mathbb{R}}(y-f(x){)}^2{p}_{Y\mid X=x}(y)\mathrm{d}y}}{p}_X(x)\mathrm{d}x\\ & ={\mathbb{E}}_X{\mathbb{E}}_{Y\mid X=x}\left[(Y-f(X){)}^2\right]\end{array}$$
因此$f(X)=\underset{c}{\mathrm{argmin}}{\mathbb{E}}_{Y\mid X=x}\left[(Y-c{)}^2\right]$。由于$\mathbb{E}[\cdot ]$的线性，这可简化为

$$f(X)=\underset{c}{\mathrm{argmin}}\left({\mathbb{E}}_{Y\mid X=x}\left[Y^2\right]-2c{\mathbb{E}}_{Y\mid X=x}[Y]+c^2\right).\text{\hspace{1em}(2.2)}$$

二次方项很容易被最小化，最优值为
$$f(X)={\mathbb{E}}_{Y\mid X=x}[Y].\text{\hspace{1em}(2.3)}$$

定理2.2

在给定$X$的情况下，如果最佳预测是以损失的平方来衡量的，对$Y$的最佳预测是条件平均数。

如上所述，条件平均数作为最佳预测依赖于我们使用平方损失作为质量测量的事实。我们可以证明，如果我们采用绝对值$|Y-f(X)|$作为损失函数–所谓的${\ell }_1$损失，最佳预测是条件中值。虽然这个声明的严格证明超出了本讲义的范围，但我们可以很容易地看到，中位数是经验${\ell }_1$损失最小化的最佳值

$$\underset{c}{\mathrm{argmin}}\frac{1}{n}\sum _i\left|y_i-c\right|.\text{\hspace{1em}(2.4 )}$$

我们只需要一个非光滑凸优化的结果，即对于有子梯度的凸函数，当且仅当$c^{\ast }$处的子梯度包含0时，才能实现$c^{\ast }$的最小值。在我们的例子中，经验${\ell }_1$损失相对于$c$的子梯度是$\frac{1}{n}{\sum }_i\mathrm{sign}\left(y_i-c\right)$对于$c\ne y_i$ 与$\left\{\frac{1}{n}{\sum }_{i\ne j}\mathrm{sign}\left(y_i-c\right)+t\mid -1\le t\le 1\right\}$ 对于$c=y_j$。因此，我们看到，只有当小于$c$的$y_i$的数量与大于c的$y_i$的数量相同时，$c$处的子梯度才包含零。在奇数$n$的情况下，$c$必须与$y_i$的$(n+1)/2$的最大值相吻合。这正是中位数的定义。

2.1 监督决策的一般设置和泛化误差

让我们从一个更高层次的角度来恢复上述章节的内容。我们引入了一个损失函数，基于训练样本$\left(x_i,y_i\right),i=1,\dots ,N$，可以从一个给定的函数类$\mathcal{F}$中学习最佳预测函数$f$。这种方法被称为监督学习方法，因为它们需要一个训练集，其中每个样本$x_i$都有一个相应的$y_i$。一般的问题陈述是:

让$(X,Y)\in {\mathbb{R}}^p$中的随机变量，让$\mathcal{F}$是来自${\mathbb{R}}^p\Rightarrow \mathbb{R}$中的一类函数。这些函数可以被有限的参数化，例如$\Theta \in {\mathbb{R}}^M$。此外，让$L:\mathbb{R}\times \mathbb{R}\to {\mathbb{R}}_0^{+}$是一个损失函数，用来衡量$Y$和$f(X)$的偏差。监督下的预测方法的目的是在$\hat{f}\in \mathcal{F}$中找到最小的预期预测误差$\mathbb{E}[L(Y,f(X)]$。

事实上，为了建立一个有监督的机器学习方法，我们需要弄清楚三个问题。

• 我们必须指定损失函数$L$。

• 我们必须指定函数类别$\mathcal{F}$。

• 由于在实践中，我们不知道$(X,Y)$的联合分布，我们需要训练样本$\left(x_i,y_i\right),i=1,\dots ,N$来接近预期预测误差。

所以我们就得到了一个优化问题

$$\hat{f}=\underset{f\in \mathcal{F}}{\mathrm{argmin}}\frac{1}{N}\sum _{i=1}^{N}L\left(y_i,f\left(x_i\right)\right)\text{\hspace{1em}(2.5)}$$

这些优化问题或多或少都很难解决，但原则上，它们可以以上述形式送入优化工具箱。

例子：线性回归
对于线性回归，我们选择$L$为二次损失，即$L(Y,f(X))=(Y-f(X){)}^2$，我们选择$\mathcal{F}$为仿射函数

$$f(x)={\theta }_0+\sum _{k=1}^p{\theta }_k{x}^{(k)},\text{\hspace{1em}(2.6)}$$

其中$x^{(k)}$是向量$x$的条目。考虑到$N$的训练样本，那么优化问题就是

$$\hat{\Theta }=\underset{{\theta }_0,\dots ,{\theta }_p}{\mathrm{argmin}}\frac{1}{N}\sum _{i=1}^N{\left(y_i-{\theta }_0-\sum _{k=1}^p{\theta }_k{x}_i^{(k)}\right)}^2.\text{\hspace{1em}(2.7)}$$

定义：
对于一个给定的函数$f$，经验损失和预期损失之间的差异

$$G_N(f)=\mathbb{E}\left[L(Y,f(X)\right]-\frac{1}{N}\sum _{i=1}^{N}L\left(y_i,f\left(x_i\right)\right).\text{\hspace{1em}(2.8)}$$

被称为$f$的泛化误差。

根据大数定律，我们知道$G_N$在$N$趋于无穷大时趋于0。然而，很多时候训练样本的数量是有限的，此外，收敛的速度高度依赖于$(X,Y)$的（未知）概率分布。因此，机器学习的一个目标是以高概率来约束泛化误差。

在实践中，我们使用交叉验证(交叉熵 )来检查$f$与数据的匹配程度。

2.2 k近邻

在实践中，我们面临的问题是我们不知道$X$和$Y$的联合分布，因此我们必须估计公式（2.3）中的条件平均值。通常情况下，这将通过给定特定实现$X$的$Y$的相对频率来完成。然而，在连续的情况下，问题出现了，即使在许多观测值$\left(x_i,y_i\right)$中，也可能没有$x_i=x$。这个问题可以通过扩大$x$周围的区域并考虑所有$x_i$接近期望的$x$的观测来解决。这就引出了$k$近邻的概念。

图2.2: 给出事件$(1,1),(2,5),(3,3),(4,1),(5,4)$的二元分布$(X,Y)$。虽然${\mathbb{E}}_{Y\mid X=4}[Y]=5$，对3个近邻的平均化提供了${\hat{f}}_{k=3}（4）=（2+3+5）/3=10/3$。

$k$近邻的方法是通过以下方式估计$f$：

$${\hat{f}}_k(x)=\text{ average }\left(y_i\mid x_i\in N_k(x)\right)\text{, }\text{\hspace{1em}(2.9)}$$

其中$N_k(x)$表示$x$的$k$近邻的集合。这里有两个近似值。

1. 预期是通过平均数来近似的。

2. 在一个点上的条件被某些区域（在该点周围）的条件所近似。

如果$N$是观察值的数量，那么要注意以下几点。如果$N$增加，$x_i$就会接近$x$。此外，如果$k$增加，平均数会趋向于期望值。更确切地说，在联合概率测量的温和条件下，我们有

$$\underset{N,k\to \infty ,\frac{k}{N}\to 0}{\lim }\hat{f}(x)={\mathbb{E}}_{Y\mid X=x}[Y].\text{\hspace{1em}(2.10)}$$

然而，样本量$N$通常是有限的，因此样本量是不足够满足条件的。

有两种方法可以克服这个问题。

• 对$f$施加模型假设，例如，$f(x)\approx x^{\mathrm{T}}\beta$得到线性回归。

• 通过 "降低"$X$的维度。这就导致了降维的动机。

找到$f:\left[\begin{array}{c}{x}_1\\ ⋮\\ x_p\end{array}\right]\mapsto \left[\begin{array}{c}{s}_1\\ ⋮\\ s_k\end{array}\right]$，使$f$保持观测的 "内在 "距离。

2.3 维度诅咒

让$X\in {\mathbb{R}}^p$为随机变量。有几件事需要观察。

首先，$X$的绝对噪声随着特征的数量（即随着$p$）增加，因为噪声在所有维度上都会累积。

第二，估计$X$的密度函数所需的观测值数量随着维度$p$的增加而急剧增加。密度函数通常是借助于一个发生率的相对频率来估计的。作为一个例子，假设在一个一维空间中的$N$观测值需要估计某个密度函数，达到预定的精度。如果观察空间增加到2维，观察的数量必须增加到$N^2$的数量才能保持同样的精度。对于3维空间，大约需要$N^3$的观测，以此类推。这意味着，为了使密度函数的估计具有相同的精度，所需的测量数量随测量空间的维度呈指数增长。

维度诅咒的一个原因是空空间现象（Scott），它指出高维空间本质上是稀疏的。鉴于数据点均匀地分布在10维单位球体中，一个点离中心的距离超过0.9的概率小于35%。因此，高维分布中的尾部要比一维分布中的尾部重要得多。给定一个高维多变量随机变量，有一个成分位于其分布的尾部，就足以使整个样本位于共同密度函数的尾部。图2.3说明了一维的情况。

图2.3：对于一维随机变量，大多数观测值都在平均值附近。更高维度的情况则不然。