在应用中，用于训练的源数据(source domain)和测试的目标数据(target domain)之间的分布可能会有所不同，因此需要研究两者的分布。

本章研究的就是采样到的数据 X={x1,x2,…,xN}\mathcal{X}=\{x_{1},x_{2},\ldots,x_{N}\} 和数据分布 θ\theta 之间的关系。比如对于高斯分布而言，给定一系列采样数据，我们可以估计出其参数；而如果给定参数，我们又可以对其进行采样。

From sample to distribution

  1. 首先要知道分布类型。常见分布有
    1. 二项分布：p(k∣n,p)=n!k!(n−k)!pk(1−p)n−kp(k|n,p)=\frac{n!}{k!(n-k)!} p^{k}(1-p)^{n-k}
    2. 泊松分布：p(k∣λ)=e−λλkk!p(k|\lambda)=\frac{e^{-\lambda}\lambda^{k}}{k!}
    3. 高斯分布：p(x∣μ,Σ)=12πσ2exp⁡[−(x−μ)22σ2]p(x|\mu, \Sigma)= \frac{1}{\sqrt{2\pi \sigma^{2}}}\exp \left[ - \frac{(x-\mu)^{2}}{2\sigma^{2}} \right]
  2. 然后得到参数
    1. 假如有足够的先验信息，比如知道数据如何产生，那么就能直接得到参数
    2. 如果没有先验信息，那么可以根据样本进行估计。常用的估计方式为最大似然估计。

Maximum Likelihood Estimation (MLE)

但是如果对数据没有任何先验知识，那么还需要假设一个分布，通常我们假设数据为高斯分布。然后我们可以使用最大似然估计来估计高斯分布的参数：

p(x1,x2,…,xN∣θ)=∏i=1Np(xi∣μ,σ)=(12πσ2)N2exp⁡(−∑i=1N(xi−μ)22σ2)p(x_1,x_2,\dots,x_N|\boldsymbol{\theta})=\prod_{i=1}^Np(x_i|\mu,\sigma)=(\frac{1}{2\pi\sigma^2})^{\frac{N}{2}}\exp\left(-\frac{\sum_{i=1}^N(x_i-\mu)^2}{2\sigma^2}\right)

然后将上述似然函数分别对参数 μ\mu 和 σ\sigma 求导：

∂log⁡p(x1,x2,...,xN∣θ)∂μ=0⟶μ^=1N∑i=1Nxi∂log⁡p(x1,x2,...,xN∣θ)∂σ=0⟶σ^2=1N∑i=1N(xi−μ^)2\begin{aligned}&\frac{\partial\log p(x_1,x_2,...,x_N|\boldsymbol{\theta})}{\partial\mu}=0\longrightarrow\hat{\mu}=\frac{1}{N}\sum_{i=1}^{N}x_{i}\\&\frac{\partial\log p(x_1,x_2,...,x_N|\boldsymbol{\theta})}{\partial\sigma}=0\longrightarrow\hat{\sigma}^2=\frac{1}{N}\sum_{i=1}^N(x_i-\hat{\mu})^2\end{aligned}

Biased estimation

对分布进行参数估计之后，还可以分析估计的参数是否有偏。这里同样以高斯分布为例，假设真实分布的参数为 μ\mu 和 σ\sigma，而极大似然估计得到的参数为：

μ^=1N∑i=1Nxiσ^2=1N∑i=1N(xi−μ^)2\hat{\mu} = \frac{1}{N} \sum_{i=1}^{N} x_i \quad \hat{\sigma}^{2} = \frac{1}{N} \sum_{i=1}^{N} (x_i-\hat{\mu})^{2}

对于参数 μ^\hat{\mu}:

E[μ^]=E[1N∑i=1Nxi]=1N∑i=1NE[xi]=μ\mathbb{E}[\hat{\mu}] = \mathbb{E} \left[ \frac{1}{N} \sum_{i=1}^{N} x_i \right] = \frac{1}{N} \sum_{i=1}^{N} \mathbb{E}[x_i] = \mu

为无偏估计。而对于参数 σ^2\hat{\sigma}^{2}:

E[σ^2]=E[1N∑i=1N(xi−μ^)2]=E[x2]−2E[1N∑i=1Nxiμ^]+E[μ^2]=E[x2]−E[μ^2]=Var⁡[x]+E[x]2−Var⁡[μ^]−E[μ^]2=Var⁡[x]−1NVar⁡[x]=N−1Nσ2\begin{aligned} \mathbb{E}[\hat{\sigma}^{2}] &= \mathbb{E}\left[ \frac{1}{N} \sum_{i=1}^{N} (x_i-\hat{\mu})^{2} \right] \\ &= \mathbb{E}[x^{2}] - 2\mathbb{E}\left[ \frac{1}{N}\sum_{i=1}^{N}x_i \hat{\mu} \right] + \mathbb{E}[\hat{\mu}^{2}] \\ &= \mathbb{E}[x^{2}] - \mathbb{E}[\hat{\mu}^{2}] \\ &= \operatorname{Var}[x] + \mathbb{E}[x]^{2} - \operatorname{Var}[\hat{\mu}] - \mathbb{E}[\hat{\mu}]^{2} \\ &= \operatorname{Var}[x] - \frac{1}{N} \operatorname{Var}[x] \\ &= \frac{N-1}{N} \sigma^{2} \end{aligned}

因此参数 σ^2\hat{\sigma}^{2} 的估计为有偏估计。但是在采样过程中，只要 N→∞N\rightarrow\infty，那么 σ^2\hat{\sigma}^{2} 就会接近无偏估计。

Gaussian Mixture Model

如果数据的分布较为复杂，那么仅仅使用一个高斯分布显然是不够的，因此需要引入混合高斯分布(Gaussian Mixture Model, GMM)。GMM 的建模与求解此处略去，具体可见文章Clustering的最后一节。

From distribution to sample

已知数据分布，想要得到数据，就需要进行采样。而目前只有特定几种简单的分布有高效的采样方式，比如对于范围在 [vl,vh][v_l,v_h] 的均匀分布，采样方式为：

x=vl+rand(0,1)(vh−vl)x=v_l+rand(0,1)(v_h-v_l)

而较为复杂的采样则需要通过一些技巧解决。

Rejection sampling

对于分布 p(z)p(z)

  1. 首先找到一个简单的分布 q(z)q(z)，使得 ∀z\forall z，有 kq(z)≥p(z)kq(z)\ge p(z)。此时 q(z)q(z) 称为 envelope distribution。
  2. 对 qq 进行采样 z0∼qz_0 \sim q
  3. 对于采样值 z0z_0，以 h1h0+h1=p(z0)kq(z0)\frac{h_{1}}{h_{0}+h_{1}}=\frac{p(z_{0})}{kq(z_{0})} 的概率接收。

Adaptive rejection sampling

但有时候，envelope distribution 并不容易找到。

和 rejection sampling 类似，只是这里的 envelope distribution 变成了分段形式。只要 p(z)p(z) 满足 log concave，那么就能找到

q(z)=kiλiexp⁡{−λi(z−zi−1)},zi−1<z≤ziq(z)=k_i\lambda_i\exp\{-\lambda_i(z-z_{i-1})\},\quad z_{i-1}<z\leq z_i

如下图所示：

Importance sampling

还有时候，我们的目的并不是采样 x∼px \sim p，而是希望求出期望 Ex∼p[f(x)]\mathbb{E}_{x\sim p}[f(x)]

∫f(x)p(x)dx=∫f(x)p(x)q(x)q(x)dx≈1S∑s=1Sf(xs)p(xs)q(xs)\begin{aligned} \int f(x)p(x)dx& =\int f(x)\frac{p(x)}{q(x)}q(x)dx \\ &\approx\frac1S\sum_{s=1}^Sf(x^s)\frac{p(x^s)}{q(x^s)} \end{aligned}

此时仅仅在分布 xs∼qx^{s}\sim q 上采样即可

Markov Chain Monte Carlo (MCMC)

MCMC 是一种通用的策略，通过有偏的随机游走(biased random walk)来近似采样，随机游走的规则根据 p(x)p(x) 来设计。比如需要采样下图中的高斯分布，除去初始几个噪音点，后面游走到的点可作为采样点。

Metropolis–Hastings algorithm (unit-variate)

这是一种针对单变量的MCMC算法。算法流程为：

  1. 初始话
    1. 选择初始状态 x0x_0
    2. 设置 t=0t=0
  2. 迭代
    1. 根据分布 g(⋅∣xt)g(\cdot |x_t)，生成一个 candidate state x′x'。其中分布 gg 类似于 kernel，是一个需要事先规定好的条件概率。
    2. 计算接受概率 A(x′,xt)=min⁡(1,p(x′)p(xt)g(xt∣x′)g(x′∣xt))A(x',x_t)=\min\left(1,\frac{p(x')}{p(x_t)}\frac{g(x_t|x')}{g(x'|x_t)}\right)
    3. 以概率 AA 接收 xt+1=x′x_{t+1}=x'，否则 xt+1=xtx_{t+1}=x_t
    4. t=t+1t = t+1

Gibbs sampling

该采样针对高维变量。整体思想为将 dd 维向量分成两部分，相互生成。记第 ii 个采样到的样本为 xi=(xi1,xi2,…,xid)\mathbf{x}_i=(x_i^1,x_i^2,\ldots,x_i^d)

  1. 初始化
    1. 选择初始状态 x0=(x01,x02,…,x0d)\mathbf{x}_0=(x_0^1,x_0^2,\ldots,x_0^d)
    2. 设置 t=0t=0
  2. 迭代
    1. 令 j=mod(t,d)j=mod(t,d)
    2. 根据条件概率 p(xj∣xt1,…,xtj−1,xtj+1,…,xtd)p(x^j|x_t^1,\ldots,x_t^{j-1},x_t^{j+1},\ldots,x_t^d) 生成 xt+1jx_{t+1}^{j}
    3. xt+1=(xt1,…,xtj−1,xt+1j,xtj+1,…,xtd)\mathbf{x}_{t+1}=(x_{t}^{1},\ldots,x_{t}^{j-1},x_{t+1}^{j},x_{t}^{j+1},\ldots,x_{t}^{d})
    4. t=t+1t=t+1