第一节课

第二节课

第三节课

第四节课 density estimation

介绍：

令$X_1,X_2,...,X_n$X1​,X2​,...,Xn​是来自分布$P$P的密度为$p$p的样本，非参数密度估计目标就是在最少的关于密度$p$p的假设的情况对$p$p进行估计。我们用$\hat p$p^​来表示$p$p的估计。这个估计会依赖一个光滑的参数$h$h，小心的选择$h$h是关键的。为了强调这个对$h$h的依赖，我们使用$\hat p_h$p^​h​记号。

密度估计可被用于：回归、分类、聚类、无监督预测。举例而言：如果$\hat p(x,y)$p^​(x,y)是$p(x,y)$p(x,y)的一个估计，那么我们可以得到回归函数的以下估计：
$\hat m(x)=\int y\hat (y|x)dy$m^(x)=∫y(^​y∣x)dy
其中$\hat p(y|x)=\hat p(y,x)\hat p(x)$p^​(y∣x)=p^​(y,x)p^​(x).对于分类问题而言，我们回忆Bayes rule：
$h(x)=I(p_1(x)\pi_1>p_0(x)\pi_0)$h(x)=I(p1​(x)π1​>p0​(x)π0​)
其中$\pi_1=\mathbb{P}(Y=1),\pi_0=\mathbb{P}(Y=0),p_1(x)=p(x|y=1)$π1​=P(Y=1),π0​=P(Y=0),p1​(x)=p(x∣y=1),$p_0(x)=p(x|y=0)$p0​(x)=p(x∣y=0).输入样本对于$\pi_1,\pi_0$π1​,π0​的估计，对$p_1,p_0$p1​,p0​的密度估计则会产生一个基于Bayes rule的预测。很多你熟悉的分类器可以被用这种方式重新表述。

损失函数

最常使用的损失函数是$L_2$L2​损失：
$\int(\hat p-p(x))^2dx=\int\hat p^2(x)dx-2\int\hat p(x)p(x)+\int p^2(x)dx$∫(p^​−p(x))2dx=∫p^​2(x)dx−2∫p^​(x)p(x)+∫p2(x)dx
风险是 $R(p,\hat p)=\mathbb{E}(L(p,\hat p))$R(p,p^​)=E(L(p,p^​))。
Devroye and Gyorfi(1985) 强烈推荐使用 $L_1$L1​范数
$\|\hat p-p\|_1\equiv\int|\hat p(x)-p(x)|dx$∥p^​−p∥1​≡∫∣p^​(x)−p(x)∣dx
作为$L_2$L2​范数的代替。$L_1$L1​损失有以下的良好解释：如果$P,Q$P,Q是分布，定义全变差度量：
$d_{TV}(P,Q)=sup_A|P(A)-Q(A)|$dTV​(P,Q)=supA​∣P(A)−Q(A)∣
上确界取遍所有的可测集。如果$P,Q$P,Q有密度$p,q$p,q那么有：
$d_{TV}(P,Q)=\frac{1}{2}\int|p-q|=\frac{1}{2}\|p-q\|_1$dTV​(P,Q)=21​∫∣p−q∣=21​∥p−q∥1​
因此，如果$\int|p-q|<\delta$∫∣p−q∣<δ那么我们知道$|P(A)-Q(A)|<\frac{\delta}{2}$∣P(A)−Q(A)∣<2δ​对于所有的$A$A。同样的，$L_1$L1​范数是一个变形不变量(transformation invariant)。假设$T$T是一个一对一的光滑映射，令$Y=T(X)$Y=T(X)。令$p$p和$q$q是$X$X的密度，令$\hat p,\hat q$p^​,q^​是相应的$Y$Y的密度，那么：
$\int|p(x)-q(x)|dx=\int|\hat p(y)-\hat q(y)|dy$∫∣p(x)−q(x)∣dx=∫∣p^​(y)−q^​(y)∣dy
因此在此定义下的距离不会因为一一映射而改变，但无论如何我们还是聚焦于$L_2$L2​损失。

Histograms直方图

Perhaps the simplest density estimators are histograms. For convenience, assume that the data $X_1,...,X_n$X1​,...,Xn​ are contained in the unit cube $X = [0,1]^d$X=[0,1]d (although this assumption is not crucial). Divide $\mathcal X$X into bins, or sub-cubes, of size $h$h. We discuss methods for choosing $h$hlater.

Kernel Density Estimation核密度估计

一个以为的光滑核(smoothing kernel)是任意的一个光滑函数（其定义域内无穷阶数连续可导的函数）$K$K满足$\int K(x)dx=1,$∫K(x)dx=1,$x\int K(x)dx=0,\sigma_k^2\equiv\int x^2K(x)dx>0$x∫K(x)dx=0,σk2​≡∫x2K(x)dx>0。一些常用的核函数如下所示：
Boxcar:$K(x)=\frac{1}{2}I(x)$K(x)=21​I(x)
Gaussian:$K(x)=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}$K(x)=2π​1​e−2x2​
Epanechnikov :$K(x)=\frac{3}{4}(1-x^2)I(x)$K(x)=43​(1−x2)I(x)
Tricube:$K(x)=\frac{70}{81}(1-|x|^3)^3I(x)$K(x)=8170​(1−∣x∣3)3I(x)
其中$I(x)=1$I(x)=1如果$|x|\leq 1$∣x∣≤1。否则$I(x)=0$I(x)=0.这些核的图像如下，常用的多维的核是$\prod_{j=1}^dK(x_j),K(\|x\|)$∏j=1d​K(xj​),K(∥x∥)。


给定一个$X\in\mathcal{R}^d$X∈Rd。给定一个核$K$K和一个正数$h$h，称之为窗宽(bandwidth)，核密度的估计定义为：
$\hat p(x)=\frac{1}{n}\sum_{i=1}^ n{h^dK(\frac{\|x-X_i\|}{h})}$p^​(x)=n1​i=1∑n​hdK(h∥x−Xi​∥​)
更一般的我们定义：
$\hat p_H(x)=\frac{1}{2}\sum_{i=1}^nK_H(x-X_i)$p^​H​(x)=21​i=1∑n​KH​(x−Xi​)
其中$H$H是一个正数定义了窗宽矩阵(bandwidth matrix)以及$K_H=|H|^{-\frac{1}{2}}K(H^{-\frac{1}{2}}x)$KH​=∣H∣−21​K(H−21​x)，为了简化表达，我们令$H=h^2I$H=h2I，然后我们得到先前的公式。

有时我们使用记号$\hat p_h$p^​h​来表达$\hat p$p^​对width $h$h的依赖性。在多元的情况下，每个样本的坐标$X_i$Xi​应当被标准化来使每个样本是同方差的，因为范数 $\|x-X_i\|$∥x−Xi​∥把所有的坐标看做它们是在同一度量下。

核估计对于每个数据点$X_i$Xi​都放置了一个size是$\frac{1}{n}$n1​的质量块，见图3。核的形式选择没有$h$h的选择关键。一个较小的$h$h会带来一个粗糙的估计，一个较大的$h$h会带来一个更光滑的估计。

4.1Risk Analysis

在这节中我们测试核密度的准确性，首先我们需要一些定义：
假设$X_i\in\mathcal{X}\subset\mathbb{R}^d$Xi​∈X⊂Rd其中$\mathcal{X}$X是紧集。令$\beta,L$β,L是正数。给定一个向量$s=(s_1,...,s_d)$s=(s1​,...,sd​)，定义$|s|=s_1+...+s_d$∣s∣=s1​+...+sd​，$s！=s_1!...s_d!$s！=s1​!...sd​!，$x^s=x_1^{s_1}...x_d^{s_d}$xs=x1s1​​...xdsd​​并且
$D^s=\frac{\partial^{s_1+...+s_d}}{\partial x_1^{s_1}...\partial x_d^{s_d}}$Ds=∂x1s1​​...∂xdsd​​∂s1​+...+sd​​
令$\beta$β是一个正整数。定义 Holder class：
$\sum(\beta,L)=\{g:|D^sg(x)-D^sg(y)|\leq L\|x-y\|,for\ all\ s\ such\ that |s|=\beta-1,and\ all\ x,y\}$∑(β,L)={g:∣Dsg(x)−Dsg(y)∣≤L∥x−y∥,for all s such that∣s∣=β−1,and all x,y}
举例而言，如果$d=1,\beta=2$d=1,β=2也就意味着：
$|g'(x)-g'(y)|\leq L|x-y|,for\ all\ x,y$∣g′(x)−g′(y)∣≤L∣x−y∣,for all x,y
最常见的情况就是$\beta=2$β=2，粗略来说这意味着函数被二阶导数限制。
如果$g\in\sum(\beta,L)$g∈∑(β,L)那么$g(x)$g(x)和他的泰勒级数展开是接近的：
$|g(u)-g_{x,\beta}(u)|\leq L\|u-x\|^\beta$∣g(u)−gx,β​(u)∣≤L∥u−x∥β
现在假设核$K$K有形式$K(x)=G(x_1)...G(x_d)$K(x)=G(x1​)...G(xd​)其中$G$G定义在$[-1,1],\int G=1,\int|G|^p<\infty$[−1,1],∫G=1,∫∣G∣p<∞对任意的$p>1$p>1都成立，$\int|t|^\beta|K(t)|dt<\infty,\int t^sK(t)=0$∫∣t∣β∣K(t)∣dt<∞,∫tsK(t)=0对于所有的$s\leq\lfloor\beta\rfloor$s≤⌊β⌋。
一个核函数的例子在$\beta=2$β=2的情况下满足这些条件的是$G(x)=(3/4)(1-x^2)$G(x)=(3/4)(1−x2)对所有的$|x|<1$∣x∣<1。构造一个满足$\int t^sK(t)dt=0$∫tsK(t)dt=0对所有$\beta>2$β>2的核函数需要这个核函数可以取负值。
令$p_h(x)=\mathbb{E}[\hat p_h(x)]$ph​(x)=E[p^​h​(x)]。下一个引理提供了一个偏差$p_h(x)-p(x)$ph​(x)−p(x)的界限。

引理 3

$\hat p$p^​的偏差满足：
$sup_{p\in\sum(\beta,L)}|p_h(x)-p(x)|\leq ch^\beta$supp∈∑(β,L)​∣ph​(x)−p(x)∣≤chβ
对于某个c
证明：我们有：

第一项被$Lh^{\beta}\int K(s)|s|^\beta$Lhβ∫K(s)∣s∣β限制因为$p\in\sum(\beta,L)$p∈∑(β,L)。第二项是0因为K的性质 $p_{x,\beta}(x+hv)-p(x)$px,β​(x+hv)−p(x)是一个阶数为$\lfloor\beta\rfloor$⌊β⌋的多项式（没有常数项）。
下面，我们来限制方差：

引理 4

$\hat p_h$p^​h​的方差满足：
$sup_{p\in\sum(\beta,L)}Var(\hat p_h(x))\leq \frac{c}{nh^d}$supp∈∑(β,L)​Var(p^​h​(x))≤nhdc​
对于某个c

阅读资料：

Density Estimation 10/36-702
https://blog.****.net/weixin_37801695/article/details/84918980
https://blog.****.net/liangzuojiayi/article/details/78152180
https://blog.****.net/unixtch/article/details/78556499