机器学习与高维信息检索 - Note 1 - 信息检索、机器学习与随机变量_综合

1. 简介

1.1 信息检索和机器学习

从高维数据中提取信息的问题与降维问题密不可分，也就是说，从典型的高维观察中提取一些合理的特征的问题。例如，考虑一下人类在图像上识别人脸的能力。该图像被视为一个高维向量，例如 $800 \times 600$ 的像素值，肯定不能作为原始像素数据存储在人类的大脑中。相反，我们必须提取一些特征，例如眼睛之间的相对距离，鼻子的长度，以及更抽象的不同脸部区域的相互作用，作为一个整体。储存和回忆这几个抽象特征的能力使我们有可能识别出一张脸，而不受不同的背景、太阳镜或部分遮挡的影响，并能区分不同的脸。在广泛的数据分析领域有更多的例子，通过提取特征可以从高维数据中挤出信息，从基因数据分类到音频信号处理，从数据可视化到脑电图（EEG）数据分析。

从形式上看，降维的问题是这样的。给定一个 $p$ 维的实值随机变量 $X=[X1…Xp]?X=\left[X_{1} \ldots X_{p}\right]^{\top}$ ，找到一个图或算法

$\mathbb{R}^{p} \rightarrow \mathbb{R}^{k} \text { with } k \ll p,$

使得 $S = f (X)$ 包含 “尽可能多的来自 $X$ 的信息”。根据上述例子的精神， $Rp\mathbb{R}^{p}$ 将被称为原始数据空间， $Rk\mathbb{R}^{k}$ 被称为还原数据空间或特征空间。

例如，信息的保存可以用方差来衡量，因此 $S$ 的方差应该反映 $X$ 的方差。这也可以解释为消除数据中的冗余。考虑下面的例子：温度被测量，一次是摄氏度（这将是随机变量的第一个条目 $X_{1}$ ），一次是华氏度 $(X2)\left(X_{2}\right)$ 。显然，这些信息可以简化为一个变量，例如 $S_{1}=X_{1}$ ，甚至不损失任何信息。

矩阵 $X?Rp×n\mathbf{X}\subset\mathbb{R}^{p\times n}$ 中的 $(i, j)$ 条目 $x_{i j}$ 表示随机变量 $X_{i}$ 在观测 $j$ 的实现，称为观测矩阵。其列是 $p$ 维随机变量 $X$ 的实现。

期望值用 $E(X)=μ∈Rp\mathbb{E}(X)=\mu\in \mathbb{R}^{p}$ 来表示。由于我们处理的是一个多变量随机变量，方差现在由协方差矩阵（也称为方差-协方差矩阵）表示，其定义为

$Σ=Var?(X)=E((X?μ)(X?μ)?)∈Rp×p.(1.1)\Sigma=\operatorname{Var}(X)=\mathbb{E}\left((X-\mu)(X-\mu)^{\top}\right) \in \mathbb{R}^{p \times p} .\tag{1.1}$

其 $(i, j)$ 项是 $i^{\text {th }}$ 和 $j^{\text {th }}$ 随机变量之间的协方差。协方差矩阵是对称的，即 $Σ=Σ?\Sigma=\Sigma^{\top}$ ，并且是正半无限的 ${ }^{1}$ ，即 $Σ≥0?\Sigma \geq 0 \Leftrightarrow$ $x?Σx≥0?xx^{\top} \Sigma x \geq 0 \forall x$ 。

${ }^{1}$ in contrast to positive definite, i.e. $x?Σx>0?x≠0x^{\top} \Sigma x>0 \forall x \neq 0$ and $x?Σx=0?x=0x^{\top} \Sigma x=0 \Leftrightarrow x=0$

例1.1. 考虑两个常数随机变量 $X1≡constX_{1} \equiv \text{const}$ ， $X2≡constX_{2} \equiv \text{const}$ 。这意味着我们有一个协方差矩阵 $Σ=0\Sigma=0$ 的二维随机变量。这个例子表明， $Σ\Sigma$ 不一定是正定的。

由于随机变量的实际分布通常是未知的，期望值通常是在 $n$ 观测值的基础上估计的。

$1n∑j=1n[x1j?xpj]=1nX1n:=μ^(1.2)\frac{1}{n} \sum_{j=1}^{n}\left[\begin{array}{c} x_{1 j} \\ \vdots \\ x_{p j} \end{array}\right]=\frac{1}{n} \mathbf{X} \mathbb{1}_{n}:=\hat{\mu} \tag{1.2}$
利用这个估计的期望值和克罗内克积（Kronecker product） $^{2}$ $?\otimes$ ，
可以计算出居中的观测矩阵 $X\mathbf{X}$ ，如下所示。

$X?=X?μ^?[1?1](1.3)\overline{\mathbf{X}}=\mathbf{X}-\hat{\mu} \otimes\left[\begin{array}{ccc} 1 & \cdots & 1 \end{array}\right]\tag{1.3}$

${ }^{2}$ The Kronecker product of two matrices $A?B\mathbf{A} \otimes \mathbf{B}$ with $A={aij}∈Rk×l,B={bij}∈Rm×n\mathbf{A}=\left\{a_{i j}\right\} \in \mathbb{R}^{k \times l}, \mathbf{B}=\left\{b_{i j}\right\} \in \mathbb{R}^{m \times n}$ is a $km \times l n)$ -matrix $C\mathbf{C}$ , such that $C=[a11B?a1lB???ak1B?aklB]\mathbf{C}=\left[\begin{array}{ccc}a_{11} \mathbf{B} & \cdots & a_{1 l} \mathbf{B} \\ \vdots & \ddots & \vdots \\ a_{k 1} \mathbf{B} & \cdots & a_{k l} \mathbf{B}\end{array}\right]$

有了居中的观察矩阵 $X?\overline{\mathrm{X}}$ ，协方差矩阵 $Σ=Cov?(X)\Sigma=\operatorname{Cov}(X)$ 可以通过以下方式估计

$Σ^=1n?1X?X??.\widehat{\Sigma}=\frac{1}{n-1} \overline{\mathbf{X}} \overline{\mathbf{X}}^{\top} .$

由于在实际应用中 $n$ 趋向于大，也可以使用近似值 $1nX?X??\frac{1}{n} \overline{\mathbf{X}} \overline{\mathbf{X}}^{\top}$ .

1.2 关于随机变量的初步说明

我们想回顾一下概率论中的一些基本定义和符号，在本讲义中我们偶尔会用到。为了我们的目的，考虑连续或离散的实数多维随机变量就足够了。更正式地说，让 $\Omega\rightarrow\mathbb{R}^{p}$ 是一个随机变量，并将其相对于通常勒贝格测度的密度表示为 $p_{X}(x)$ 。我们将使用非常草率但非常方便的符号 $X∈RpX\in\mathbb{R}^{p}$ 来表示随机变量 $X$ 在 $Rp\mathbb{R}^{p}$ 中取值。

对于（绝对）连续随机变量，密度是一个从 $Rp\mathbb{R}^{p}$ 到 $R\mathbb{R}$ 的连续函数。如果是离散随机变量，其取值为 $x_{i}$ ，概率为 $p_{i}$ ，我们采用狄拉克δ函数 ${ }^{3}$ 来描述其密度，即

$pX(x)=∑ipiδ(x?xi).p_{X}(x)=\sum_{i} p_{i} \delta\left(x-x_{i}\right) .$

${ }^{3}$ The Dirac-Delta-Function fulfills the condition that $δ(t)=0\delta(t)=0$ for $\neq 0$ and $∫Rpδ(t)dt=1p\int_{\mathbb{R}^{p}} \delta(t) \mathrm{d} t=\mathbb{1}_{p}$ . i.e. $δ\delta$ has an infinitely high peak at $0 .$

所以，如果 $A?Rp\mathcal{A} \subset \mathbb{R}^{p}$ ，则 $X$ 在 $A\mathcal{A}$ 中取值的概率为

$Pr?(X∈A)=∫ApX(x)dx.\operatorname{Pr}(X \in \mathcal{A})=\int_{\mathcal{A}} p_{X}(x) \mathrm{d} x .$

注意，在离散随机变量的情况下，这个表达式只是

$Pr?(X∈A)=∫A∑ipiδ(x?xi)dx=∑{i∣xi∈A}pi.\operatorname{Pr}(X \in \mathcal{A})=\int_{\mathcal{A}} \sum_{i} p_{i} \delta\left(x-x_{i}\right) \mathrm{d} x=\sum_{\left\{i \mid x_{i} \in \mathcal{A}\right\}} p_{i} .$
通过知道两个随机变量 $X∈RpX\in \mathbb{R}^{p}$ 和 $Y∈RkY\in \mathbb{R}^{k}$ 的联合密度 $p_{X, Y}(x, y)$ ，就可以分别推导出 $X$ 和 $Y$ 的个体密度。这些被称为边缘密度（marginal densities），它们由以下公式给出

$pX(x)=∫RkpX,Y(x,y)dy,pY(y)=∫RppX,Y(x,y)dx.\begin{aligned} &p_{X}(x)=\int_{\mathbb{R}^{k}} p_{X, Y}(x, y) \mathrm{d} y, \\ &p_{Y}(y)=\int_{\mathbb{R}^{p}} p_{X, Y}(x, y) \mathrm{d} x . \end{aligned}$
如果联合密度函数是给定的，对两个变量之一的某个实现的了解，例如 $X$ ，可以推断出关于 $Y$ 的分布信息。由此产生的密度函数被称为条件密度函数，如果 $X$ 的实现是 $\in \mathbb{R}^{p}$ ，它由以下公式给出

$pY∣X=x(y)=pX,Y(x,y)pX(x).p_{Y \mid X=x}(y)=\frac{p_{X, Y}(x, y)}{p_{X}(x)} .$

${ }^{4}$ 从形式上看，这个集合必须是可测的，相对于博雷尔 $σ\sigma$ -代数而言，但如果你不知道什么是可测的，你能想象的所有子集都满足这个条件。有两个量在描述随机变量 $X∈RpX\in\mathbb{R}^{p}$ 的统计属性时起着突出的作用。它们是第一和第二时刻，也被称为期望值

$E[X]=∫RpxpX(x)dx=:μ\mathbb{E}[X]=\int_{\mathbb{R}^{p}} x p_{X}(x) \mathrm{d} x=: \mu$

和方差/协方差

$Var?[X]=∫Rp(x?μ)(x?μ)?pX(x)dx.\operatorname{Var}[X]=\int_{\mathbb{R}^{p}}(x-\mu)(x-\mu)^{\top} p_{X}(x) \mathrm{d} x .$

注意， $μ∈Rp\mu\in\mathbb{R}^{p}$ 和 $Var?[X]\operatorname{Var}[X]$ 是 $Rp×p\mathbb{R}^{p\times p}$ 的半正定矩阵。

Exercise：证明方差/协方差矩阵是正半定的

	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$py(Y)↓p_{y}(Y) \downarrow$
$y_{1}$	$18\frac{1}{8}$	$116\frac{1}{16}$	$132\frac{1}{32}$	$132\frac{1}{32}$	$14\frac{1}{4}$
$y_{2}$	$116\frac{1}{16}$	$18\frac{1}{8}$	$132\frac{1}{32}$	$132\frac{1}{32}$	$14\frac{1}{4}$
$y_{3}$	$116\frac{1}{16}$	$116\frac{1}{16}$	$116\frac{1}{16}$	$116\frac{1}{16}$	$14\frac{1}{4}$
$y_{4}$	$14\frac{1}{4}$	0	0	0	$14\frac{1}{4}$
$p_{x}(X)$	$12\frac{1}{2}$	$14\frac{1}{4}$	$18\frac{1}{8}$	$18\frac{1}{8}$	1

表1.1: 该表显示了一个示例性的联合概率分布。

例1.2. 表1.1中给出了一个二维离散随机变量的联合概率分布的例子。边际密度分别用 $p_{Y}（y）$ 和 $p_{X}（x）$ 表示。作为一个练习，请计算在 $Y=y_{2}$ 的情况下 $X$ 的条件密度。

Answer: $pX∣Y=y2(x)=∑ipiδ(x?xi)p_{X \mid Y=y_{2}}(x)=\sum_{i} p_{i} \delta\left(x-x_{i}\right)$ , with $p_{1}=1 / 4, p_{2}=1 / 2, p_{3}=1 / 8, p_{4}=1 / 8 .$