回归直方图 | Codeboy's Blog

形式陈述

回归直方图先把输入空间划成固定区域，再对落在同一区域的响应求平均。给定事先固定的有限可测划分 $B_1,\ldots,B_J$ ，以及 $n$ 个IID训练对。若划分由独立pilot资料学习，以下全部陈述先条件于已冻结的划分，训练对与测试输入均独立于该pilot；需要无条件风险时再对划分平均。记

N_j=\sum_{i=1}^n\mathbf1_{X_i\in B_j},\qquad T_j=\sum_{i=1}^nY_i\mathbf1_{X_i\in B_j}.

本页固定空箱后备值为零，预测器为

\widehat m(x)=\begin{cases}T_j/N_j,&x\in B_j,\ N_j>0,\\0,&x\in B_j,\ N_j=0.\end{cases}\tag{1}

每个输入恰属一箱。对 $[0,1]$ 等宽分箱，除最后一箱包含右端点1外，其余取左闭右开；查询在声明域外则报告超出范围。另一种后备值、合并空箱或向邻箱借数据都可以使用，但需要另写规则。

目标是平方损失回归中的 $m(x)=E(Y\mid X=x)$ 。设 $EY^2<\infty$ ，对概率 $p_j=P(X\in B_j)>0$ 的箱定义

m_j=E(Y\mid X\in B_j),\quad v_j=\operatorname{Var}(Y\mid X\in B_j),\quad A_j=E[(m(X)-m_j)^2\mid X\in B_j].

训练样本与一个新输入 $X$ 独立。对两者取平均的函数估计风险有精确公式

E_{\rm train}E_X[(\widehat m(X)-m(X))^2] =\sum_{j:p_j>0}p_j\left[A_j+ v_j E\frac{\mathbf1_{N_j>0}}{N_j} +m_j^2(1-p_j)^n\right].\tag{2}

分式在 $N_j=0$ 时按整项为零理解。三个部分分别来自箱内真曲线变化、非空箱的样本平均波动、空箱的后备值误差。它们均是有限样本项。

直觉

箱内所有输入共用一个预测值，所以分箱压缩的是输入信息。即使有无限样本，固定箱也只能学到 $m_j$ ；缩小箱才可能减少这项近似误差。箱缩得太多，另一个困难随之出现：有些箱只有一条记录，甚至根本没有记录。

回归箱高是响应均值，单位与响应相同。密度直方图的箱高则是“该箱人数占比除以箱宽”，单位是输入单位的倒数。两者使用同一份计数，却估计不同对象。矩形NW窗口随查询滑动；固定分箱的边界不随查询移动，这也导致不同的计算与风险结构。

例子与边界

空箱不是一个零响应观测

把 $[0,1]$ 分为 $[0,0.3),[0.3,0.6),[0.6,1]$ 。三条数据为 $(0.1,2),(0.2,4),(0.7,10)$ ，得到

N=(2,0,1),\qquad T=(6,0,10),\qquad \widehat m=(3,0,10)\ \text{按三箱取值}.

因此查询0.25返回3，查询0.45返回预定后备值0，查询0.6返回10。第二个0表示“没有资料，使用规则”，并不表示观察到了真实响应零。

把全部已有响应加100，非空箱输出变为103与110，空箱仍输出0。这个算法没有整体平移等变性，原因完全来自固定后备值。若业务上零是极不合理的后备预测，可预定一个更合适的常数或拒绝预测，并用对应损失重新评估。

一个有精确期望的稀有箱

设某箱概率 $p=1/4$ ，本箱内响应恒为2，训练样本数 $n=2$ 。箱内没有噪声也没有曲线变化，所以 $v=A=0$ 。但空箱概率为 $(3/4)^2=9/16$ 。

条件于测试输入落在该箱，估计量的MSE为 $4\times9/16=9/4$ ；该箱对整体风险贡献为 $(1/4)(9/4)=9/16$ 。算法在这个箱上的期望预测仅为 $2(1-9/16)=7/8$ ，不能把随机比值的期望写成 $E T/E N=2$ 。

再令该箱内响应以相等概率取0与4，仍有 $m_j=2$ ，现在 $v_j=4$ 。 $N\sim\operatorname{Binomial}(2,1/4)$ ，所以

E\frac{\mathbf1_{N>0}}N=P(N=1)+\tfrac12P(N=2) =\frac38+\frac1{32}=\frac{13}{32}.

若条件均值在该箱仍恒为2，则该箱的整体风险贡献为

\frac14\left(4\frac{13}{32}+4\frac9{16}\right)=\frac{31}{32}.

把 $1/N$ 偷换成 $1/(np)=2$ ，会得到错误的波动项。空箱、随机分母和响应噪声需要同时记账。

看过响应再分箱会改变保证

若在许多切点中挑一个使训练平方误差最小的切点，箱边界已依赖响应。给定最终箱再假装它从一开始固定，箱内观测不再拥有下文所用的简单条件抽样解释。回归树可以研究这种自适应划分，但要分析选择过程，或在独立一批资料上学习划分、再用本批资料估计各箱均值。

推论与应用

证明随机计数风险公式

固定箱 $j$ ， $N_j$ 服从二项分布。给定 $N_j=r>0$ ，落入该箱的 $r$ 个响应来自箱内条件分布，故

E(\widehat m_j\mid N_j=r)=m_j,\qquad E[(\widehat m_j-m_j)^2\mid N_j=r]=v_j/r.

$N_j=0$ 时平方误差是 $m_j^2$ 。平均计数就给式(2)后两项。对一个独立测试输入，写

\widehat m_j-m(X)=(\widehat m_j-m_j)+(m_j-m(X)).

因为 $E[m(X)-m_j\mid X\in B_j]=0$ ，交叉项对该箱内的测试输入平均后消失，余下 $A_j$ 。最后乘以测试输入落入该箱的概率 $p_j$ 并求和，完成式(2)。此证明不要求各箱计数独立；事实上它们总和固定为 $n$ 。

有界响应下，从空箱账本推导速率

假设 $X\in[0,1]^d$ 、 $|Y|\le M$ 、 $m$ 为 $L$ -Lipschitz。每一坐标等分成 $q$ 段，得到 $J=q^d$ 个边长 $h=1/q$ 的立方箱。箱内任意两点距离至多 $\sqrt d\,h$ ，因此 $A_j\le L^2d h^2$ ，且 $v_j\le M^2$ 、 $|m_j|\le M$ 。

对 $N\sim\operatorname{Binomial}(n,p)$ 、 $p>0$ ，由 $1/r\le2/(r+1)$ （ $r\ge1$ ）和二项系数恒等式，

E\frac{\mathbf1_{N>0}}N\le2E\frac1{N+1} =\frac{2[1-(1-p)^{n+1}]}{(n+1)p}\le\frac2{(n+1)p}.

中间等号可用 $\binom nr/(r+1)=\binom{n+1}{r+1}/(n+1)$ 逐项求和核对。又有 $p(1-p)^n\le1/(n+1)$ ：在 $[0,1]$ 上求导，其最大点是 $p=1/(n+1)$ ，最大值还乘着一个不超过1的因子。

把这些界代回式(2)，得到

E\|\widehat m-m\|_{L^2(P_X)}^2 \le L^2d q^{-2}+\frac{3M^2q^d}{n+1}.\tag{3}

这里没有要求输入密度有统一正下界，稀有箱通过其小测试概率被一并控制。取整数 $q\asymp n^{1/(d+2)}$ ，得到 $O(n^{-2/(d+2)})$ 的积分风险上界。这是明确函数类和损失下的上界；要声称极小极大最优，还要另给下界。

计算接口与其他目标

初始化每箱计数与响应和为零；扫描数据并各更新一次；最后对非空箱除法、为空箱登记后备状态。规则网格用坐标取整定位，训练工作为 $O(nd+J)$ ，存储 $O(J)$ ；每个新查询定位需 $O(d)$ ，取箱均值为常数时间。稀疏字典可只存非空箱，查询时仍须能识别空箱。没有数值迭代或收敛容差。

分箱数的选择可用训练/选择隔离的验证。若改用箱内分位数而非均值，就得到分位数回归的一种分块常数实现；损失、空箱处理和理论保证都须相应改变。

自测与答案

稀有箱无噪声例把空箱后备值改为1，该箱整体风险是多少？ $p(2-1)^2(1-p)^n=9/64$ ；此时式(2)的空箱项应为 $(m_j-1)^2(1-p_j)^n$ 。
把所有 $q^d$ 箱机械各分为 $2^d$ 个小箱，式(3)两项怎样变？几何项乘 $1/4$ ，计数项乘 $2^d$ 。更多箱并不自动提高有限样本准确度。

参考资料

Larry Wasserman, Lecture Notes 21: Nonparametric Regression，§1，PDF p. 1：回归直方图的分箱接口。
Yen-Chi Chen, Lecture 9: Regression: Regressogram and Kernel Regression, University of Washington, 2018，§9.2–9.3，PDF pp. 1–2：固定分箱与移动窗口的区别。式(2)–(3)采用本页的有界响应、固定划分、零后备规则，并逐步证明，不借用随机比值的一阶近似。

形式陈述 ​

空箱不是一个零响应观测 ​

一个有精确期望的稀有箱 ​

看过响应再分箱会改变保证 ​

证明随机计数风险公式 ​

有界响应下，从空箱账本推导速率 ​

计算接口与其他目标 ​

自测与答案 ​

反向链接