机器学习与高维信息检索 - Note 1 - 信息检索、机器学习与随机变量
1. 簡(jiǎn)介
1.1 信息檢索和機(jī)器學(xué)習(xí)
從高維數(shù)據(jù)中提取信息的問(wèn)題與降維問(wèn)題密不可分,也就是說(shuō),從典型的高維觀察中提取一些合理的特征的問(wèn)題。例如,考慮一下人類在圖像上識(shí)別人臉的能力。該圖像被視為一個(gè)高維向量,例如 800×600800 \times 600800×600 的像素值,肯定不能作為原始像素?cái)?shù)據(jù)存儲(chǔ)在人類的大腦中。相反,我們必須提取一些特征,例如眼睛之間的相對(duì)距離,鼻子的長(zhǎng)度,以及更抽象的不同臉部區(qū)域的相互作用,作為一個(gè)整體。儲(chǔ)存和回憶這幾個(gè)抽象特征的能力使我們有可能識(shí)別出一張臉,而不受不同的背景、太陽(yáng)鏡或部分遮擋的影響,并能區(qū)分不同的臉。在廣泛的數(shù)據(jù)分析領(lǐng)域有更多的例子,通過(guò)提取特征可以從高維數(shù)據(jù)中擠出信息,從基因數(shù)據(jù)分類到音頻信號(hào)處理,從數(shù)據(jù)可視化到腦電圖(EEG)數(shù)據(jù)分析。
從形式上看,降維的問(wèn)題是這樣的。給定一個(gè)ppp維的實(shí)值隨機(jī)變量X=[X1…Xp]?X=\left[X_{1} \ldots X_{p}\right]^{\top}X=[X1?…Xp?]?,找到一個(gè)圖或算法
f:Rp→Rkwith?k?p,f: \mathbb{R}^{p} \rightarrow \mathbb{R}^{k} \text { with } k \ll p, f:Rp→Rk?with?k?p,
使得S=f(X)S=f(X)S=f(X)包含 “盡可能多的來(lái)自XXX的信息”。根據(jù)上述例子的精神,Rp\mathbb{R}^{p}Rp將被稱為原始數(shù)據(jù)空間,Rk\mathbb{R}^{k}Rk被稱為還原數(shù)據(jù)空間或特征空間。
例如,信息的保存可以用方差來(lái)衡量,因此SSS的方差應(yīng)該反映XXX的方差。這也可以解釋為消除數(shù)據(jù)中的冗余。考慮下面的例子:溫度被測(cè)量,一次是攝氏度(這將是隨機(jī)變量的第一個(gè)條目X1X_{1}X1?),一次是華氏度(X2)\left(X_{2}\right)(X2?)。顯然,這些信息可以簡(jiǎn)化為一個(gè)變量,例如S1=X1S_{1}=X_{1}S1?=X1?,甚至不損失任何信息。
矩陣X?Rp×n\mathbf{X}\subset\mathbb{R}^{p\times n}X?Rp×n中的(i,j)(i, j)(i,j)條目xijx_{i j}xij?表示隨機(jī)變量XiX_{i}Xi?在觀測(cè)jjj的實(shí)現(xiàn),稱為觀測(cè)矩陣。其列是ppp維隨機(jī)變量XXX的實(shí)現(xiàn)。
期望值用E(X)=μ∈Rp\mathbb{E}(X)=\mu\in \mathbb{R}^{p}E(X)=μ∈Rp來(lái)表示。由于我們處理的是一個(gè)多變量隨機(jī)變量,方差現(xiàn)在由協(xié)方差矩陣(也稱為方差-協(xié)方差矩陣)表示,其定義為
Σ=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} Σ=Var(X)=E((X?μ)(X?μ)?)∈Rp×p.(1.1)
其(i,j)(i, j)(i,j)項(xiàng)是ith?i^{\text {th }}ith?和jth?j^{\text {th }}jth?隨機(jī)變量之間的協(xié)方差。協(xié)方差矩陣是對(duì)稱的,即Σ=Σ?\Sigma=\Sigma^{\top}Σ=Σ?,并且是正半無(wú)限的1{ }^{1}1,即Σ≥0?\Sigma \geq 0 \LeftrightarrowΣ≥0? x?Σx≥0?xx^{\top} \Sigma x \geq 0 \forall xx?Σx≥0?x。
1{ }^{1}1 in contrast to positive definite, i.e. x?Σx>0?x≠0x^{\top} \Sigma x>0 \forall x \neq 0x?Σx>0?x?=0 and x?Σx=0?x=0x^{\top} \Sigma x=0 \Leftrightarrow x=0x?Σx=0?x=0
例1.1. 考慮兩個(gè)常數(shù)隨機(jī)變量X1≡constX_{1} \equiv \text{const}X1?≡const ,X2≡constX_{2} \equiv \text{const}X2?≡const。這意味著我們有一個(gè)協(xié)方差矩陣Σ=0\Sigma=0Σ=0的二維隨機(jī)變量。這個(gè)例子表明,Σ\SigmaΣ不一定是正定的。
由于隨機(jī)變量的實(shí)際分布通常是未知的,期望值通常是在nnn觀測(cè)值的基礎(chǔ)上估計(jì)的。
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} n1?j=1∑n?????x1j??xpj??????=n1?X1n?:=μ^?(1.2)
利用這個(gè)估計(jì)的期望值和克羅內(nèi)克積(Kronecker product)2^{2}2?\otimes?,
可以計(jì)算出居中的觀測(cè)矩陣X\mathbf{X}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} X=X?μ^??[1???1?](1.3)
2{ }^{2}2 The Kronecker product of two matrices A?B\mathbf{A} \otimes \mathbf{B}A?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}A={aij?}∈Rk×l,B={bij?}∈Rm×n is a (km×ln)(k m \times l n)(km×ln)-matrix C\mathbf{C}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]C=????a11?B?ak1?B?????a1l?B?akl?B?????
有了居中的觀察矩陣X ̄\overline{\mathrm{X}}X,協(xié)方差矩陣Σ=Cov?(X)\Sigma=\operatorname{Cov}(X)Σ=Cov(X)可以通過(guò)以下方式估計(jì)
Σ^=1n?1X ̄X ̄?.\widehat{\Sigma}=\frac{1}{n-1} \overline{\mathbf{X}} \overline{\mathbf{X}}^{\top} . Σ=n?11?XX?.
由于在實(shí)際應(yīng)用中nnn趨向于大,也可以使用近似值 1nX ̄X ̄?\frac{1}{n} \overline{\mathbf{X}} \overline{\mathbf{X}}^{\top}n1?XX?.
1.2 關(guān)于隨機(jī)變量的初步說(shuō)明
我們想回顧一下概率論中的一些基本定義和符號(hào),在本講義中我們偶爾會(huì)用到。為了我們的目的,考慮連續(xù)或離散的實(shí)數(shù)多維隨機(jī)變量就足夠了。更正式地說(shuō),讓XΩ→RpX \Omega\rightarrow\mathbb{R}^{p}XΩ→Rp是一個(gè)隨機(jī)變量,并將其相對(duì)于通常勒貝格測(cè)度的密度表示為pX(x)p_{X}(x)pX?(x)。我們將使用非常草率但非常方便的符號(hào)X∈RpX\in\mathbb{R}^{p}X∈Rp來(lái)表示隨機(jī)變量XXX在Rp\mathbb{R}^{p}Rp中取值。
對(duì)于(絕對(duì))連續(xù)隨機(jī)變量,密度是一個(gè)從Rp\mathbb{R}^{p}Rp到R\mathbb{R}R的連續(xù)函數(shù)。如果是離散隨機(jī)變量,其取值為xix_{i}xi?,概率為pip_{i}pi?,我們采用狄拉克δ函數(shù)3{ }^{3}3來(lái)描述其密度,即
pX(x)=∑ipiδ(x?xi).p_{X}(x)=\sum_{i} p_{i} \delta\left(x-x_{i}\right) . pX?(x)=i∑?pi?δ(x?xi?).
3{ }^{3}3 The Dirac-Delta-Function fulfills the condition that δ(t)=0\delta(t)=0δ(t)=0 for t≠0t \neq 0t?=0 and ∫Rpδ(t)dt=1p\int_{\mathbb{R}^{p}} \delta(t) \mathrmze8trgl8bvbq t=\mathbb{1}_{p}∫Rp?δ(t)dt=1p?. i.e. δ\deltaδ has an infinitely high peak at 0.0 .0.
所以,如果A?Rp\mathcal{A} \subset \mathbb{R}^{p}A?Rp,則XXX在A\mathcal{A}A中取值的概率為
Pr?(X∈A)=∫ApX(x)dx.\operatorname{Pr}(X \in \mathcal{A})=\int_{\mathcal{A}} p_{X}(x) \mathrmze8trgl8bvbq x . Pr(X∈A)=∫A?pX?(x)dx.
注意,在離散隨機(jī)變量的情況下,這個(gè)表達(dá)式只是
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) \mathrmze8trgl8bvbq x=\sum_{\left\{i \mid x_{i} \in \mathcal{A}\right\}} p_{i} . Pr(X∈A)=∫A?i∑?pi?δ(x?xi?)dx={i∣xi?∈A}∑?pi?.
通過(guò)知道兩個(gè)隨機(jī)變量X∈RpX\in \mathbb{R}^{p}X∈Rp和Y∈RkY\in \mathbb{R}^{k}Y∈Rk的聯(lián)合密度pX,Y(x,y)p_{X, Y}(x, y)pX,Y?(x,y),就可以分別推導(dǎo)出XXX和YYY的個(gè)體密度。這些被稱為邊緣密度(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) \mathrmze8trgl8bvbq y, \\ &p_{Y}(y)=\int_{\mathbb{R}^{p}} p_{X, Y}(x, y) \mathrmze8trgl8bvbq x . \end{aligned} ?pX?(x)=∫Rk?pX,Y?(x,y)dy,pY?(y)=∫Rp?pX,Y?(x,y)dx.?
如果聯(lián)合密度函數(shù)是給定的,對(duì)兩個(gè)變量之一的某個(gè)實(shí)現(xiàn)的了解,例如XXX,可以推斷出關(guān)于YYY的分布信息。由此產(chǎn)生的密度函數(shù)被稱為條件密度函數(shù),如果XXX的實(shí)現(xiàn)是x∈Rpx \in \mathbb{R}^{p}x∈Rp,它由以下公式給出
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)} . pY∣X=x?(y)=pX?(x)pX,Y?(x,y)?.
4{ }^{4}4 從形式上看,這個(gè)集合必須是可測(cè)的,相對(duì)于博雷爾σ\sigmaσ-代數(shù)而言,但如果你不知道什么是可測(cè)的,你能想象的所有子集都滿足這個(gè)條件。有兩個(gè)量在描述隨機(jī)變量X∈RpX\in\mathbb{R}^{p}X∈Rp的統(tǒng)計(jì)屬性時(shí)起著突出的作用。它們是第一和第二時(shí)刻,也被稱為期望值
E[X]=∫RpxpX(x)dx=:μ\mathbb{E}[X]=\int_{\mathbb{R}^{p}} x p_{X}(x) \mathrmze8trgl8bvbq x=: \mu E[X]=∫Rp?xpX?(x)dx=:μ
和方差/協(xié)方差
Var?[X]=∫Rp(x?μ)(x?μ)?pX(x)dx.\operatorname{Var}[X]=\int_{\mathbb{R}^{p}}(x-\mu)(x-\mu)^{\top} p_{X}(x) \mathrmze8trgl8bvbq x . Var[X]=∫Rp?(x?μ)(x?μ)?pX?(x)dx.
注意,μ∈Rp\mu\in\mathbb{R}^{p}μ∈Rp和Var?[X]\operatorname{Var}[X]Var[X]是Rp×p\mathbb{R}^{p\times p}Rp×p的半正定矩陣。
Exercise:證明方差/協(xié)方差矩陣是正半定的
| x1x_{1}x1? | x2x_{2}x2? | x3x_{3}x3? | x4x_{4}x4? | py(Y)↓p_{y}(Y) \downarrowpy?(Y)↓ | |
|---|---|---|---|---|---|
| y1y_{1}y1? | 18\frac{1}{8}81? | 116\frac{1}{16}161? | 132\frac{1}{32}321? | 132\frac{1}{32}321? | 14\frac{1}{4}41? |
| y2y_{2}y2? | 116\frac{1}{16}161? | 18\frac{1}{8}81? | 132\frac{1}{32}321? | 132\frac{1}{32}321? | 14\frac{1}{4}41? |
| y3y_{3}y3? | 116\frac{1}{16}161? | 116\frac{1}{16}161? | 116\frac{1}{16}161? | 116\frac{1}{16}161? | 14\frac{1}{4}41? |
| y4y_{4}y4? | 14\frac{1}{4}41? | 0 | 0 | 0 | 14\frac{1}{4}41? |
| px(X)p_{x}(X)px?(X) | 12\frac{1}{2}21? | 14\frac{1}{4}41? | 18\frac{1}{8}81? | 18\frac{1}{8}81? | 1 |
表1.1: 該表顯示了一個(gè)示例性的聯(lián)合概率分布。
例1.2. 表1.1中給出了一個(gè)二維離散隨機(jī)變量的聯(lián)合概率分布的例子。邊際密度分別用pY(y)p_{Y}(y)pY?(y)和pX(x)p_{X}(x)pX?(x)表示。作為一個(gè)練習(xí),請(qǐng)計(jì)算在Y=y2Y=y_{2}Y=y2?的情況下XXX的條件密度。
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)pX∣Y=y2??(x)=∑i?pi?δ(x?xi?), with p1=1/4,p2=1/2,p3=1/8,p4=1/8.p_{1}=1 / 4, p_{2}=1 / 2, p_{3}=1 / 8, p_{4}=1 / 8 .p1?=1/4,p2?=1/2,p3?=1/8,p4?=1/8.
總結(jié)
以上是生活随笔為你收集整理的机器学习与高维信息检索 - Note 1 - 信息检索、机器学习与随机变量的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: ADPRL - 近似动态规划和强化学习
- 下一篇: 机器学习与高维信息检索 - Note 2