Efficient Decision Trees for Tensor Regressions¶

作者: Hengrui Luo, Akira Horiguchi, Li Ma
来源: Journal of Computational and Graphical Statistics
主题: 统计计算 / 算法
相关性: 7/10
链接: 期刊页 · arXiv

一、领域脉络与小综述¶

这个方向是什么¶

这个子方向解决的根本问题是：如何对输入为张量（multi-way array）的回归问题进行高效且可解释的建模。传统方法（如张量高斯过程、张量回归模型）要么计算成本高昂（GP 的 O(n³) 复杂度），要么缺乏可解释性（深度神经网络）。树模型天然具有可解释性和递归划分结构，但如何将树模型扩展到张量输入空间（即如何定义分裂准则、如何高效搜索分裂点）是一个尚未被充分解决的统计计算问题。当前成熟度较低，属于方法创新与算法设计的早期阶段。

发展脉络（history）¶

奠基工作：张量回归的统计模型。Zhou et al. (2013) 提出了经典的标量-张量回归模型（CP 低秩分解），将回归系数张量分解为秩-R 的 CP 形式，从而将参数数量从指数级降到线性。这奠定了张量回归的统计基础，但模型是全局线性的，无法捕捉非线性交互。
主要进展：非线性张量回归。Sun et al. (2023) 和 Yu et al. (2018) 将高斯过程（GP）扩展到张量输入空间，利用张量结构设计核函数（如 separable kernel），实现了非线性建模。但 GP 的计算复杂度为 O(n³)，且预测时需存储所有训练数据，难以扩展到大规模数据。作者在 intro 中明确说“GP models are computationally expensive and scale poorly with sample size”。
当前 frontier：可扩展的非线性张量回归。近年来，张量神经网络（tensor neural networks）被提出，但缺乏理论保证且可解释性差。树模型作为替代方案，其递归划分结构天然适合张量输入，但如何高效实现分裂点搜索是关键瓶颈。
本文的位置：作者将树模型引入张量回归，提出 tensor-input tree (TT)，并设计了快速随机化和确定性分裂算法，使得 TT 在计算效率上显著优于张量 GP，同时保持了树模型的可解释性。作者将其定位为“a computationally efficient and interpretable alternative to tensor-input GP models”。

子线索聚类¶

这些被引文献大致落在 3 条子线索上： 1. 张量回归的线性模型（Zhou et al., 2013; Lock, 2018）：基于低秩分解（CP、Tucker）的全局线性模型，参数少但缺乏非线性。 2. 张量输入的非线性模型（Sun et al., 2023; Yu et al., 2018; Xu et al., 2023）：张量 GP 和深度张量网络，计算成本高或缺乏可解释性。 3. 树模型与集成方法（Breiman, 2001; Chen & Guestrin, 2016）：随机森林和 XGBoost 等树集成方法在表格数据上表现优异，但输入必须是向量，无法直接处理张量结构。

这个方向在追问的核心问题¶

Q1：如何定义张量输入空间上的分裂准则，使得分裂后的子节点同质性最大化？
Q2：如何高效搜索张量输入空间中的最优分裂点（张量维度高、分裂候选数指数级）？
Q3：树模型在张量回归上的收敛速率如何？是否能在一定条件下达到 minimax 最优？
Q4：如何将标量-张量树扩展到张量-张量回归（输出也是张量）？

⚠️ 作者的 framing¶

作者把缺口 frame 成“张量 GP 计算成本高且不可扩展，而树模型可提供高效且可解释的替代方案”。他们淡化了深度张量网络这条竞争路线（只说“lack theoretical guarantees”），回避了张量 GP 在中小样本下的预测精度优势（实验中也未与张量 GP 做全面的精度对比）。什么明显该被引 / 该存在、却没出现在 intro 里？——未见对“张量输入空间上的贝叶斯加性回归树（BART）”的引用，BART 是树集成在非线性回归中的经典方法，且已有张量扩展的尝试（如 Tensor BART）。这可能是作者有意回避的竞争路线，值得研究者去查。

张力¶

未见明显对立引用。各子线索的工作在假设和适用场景上互补，而非矛盾。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号： - 输入张量：\( \mathcal{X} \in \mathbb{R}^{p_1 \times p_2 \times \cdots \times p_D} \)，其中 \( D \) 是张量的阶数（mode），\( p_d \) 是第 \( d \) 阶的维度。例如，一张 \( 28 \times 28 \) 的灰度图像是 \( D=2, p_1=p_2=28 \) 的矩阵（二阶张量）。 - 输出标量：\( y \in \mathbb{R} \)（标量-张量回归）或输出张量 \( \mathcal{Y} \in \mathbb{R}^{q_1 \times \cdots \times q_E} \)（张量-张量回归）。 - 样本：\( \{ (\mathcal{X}_i, y_i) \}_{i=1}^n \)，\( n \) 为样本量。 - 树模型参数：树 \( T \) 由一系列分裂规则定义。每个内部节点 \( t \) 对应一个分裂规则 \( s_t = (d_t, j_t, c_t) \)，其中 \( d_t \in \{1,\dots,D\} \) 是分裂 mode，\( j_t \in \{1,\dots,p_{d_t}\} \) 是分裂 mode 上的索引（即张量的第 \( d_t \) 阶的第 \( j_t \) 个切片），\( c_t \) 是分裂阈值（标量）。叶子节点 \( \ell \) 对应一个预测值 \( \mu_\ell \in \mathbb{R} \)（标量输出）或 \( \mathcal{M}_\ell \in \mathbb{R}^{q_1 \times \cdots \times q_E} \)（张量输出）。 - 可观测数据：研究者能观测到 \( n \) 个张量-标量对 \( (\mathcal{X}_i, y_i) \)。张量 \( \mathcal{X}_i \) 是完整的（无缺失），且每个元素是实数。输出 \( y_i \) 是连续标量。想要但观测不到的是：张量输入空间中的最优分裂结构（即哪个 mode、哪个索引、哪个阈值能最好地划分数据）。

模型： - 标量-张量回归树：假设数据由一棵未知的树 \( T^* \) 生成：\( y_i = f(\mathcal{X}_i) + \varepsilon_i \)，其中 \( f \) 是分段常数函数（在每个叶子节点内为常数），\( \varepsilon_i \sim N(0, \sigma^2) \)。树 \( T^* \) 的分裂规则基于张量的某个 mode 的某个切片（如“图像的第 10 行第 5 列像素值是否大于 0.5”）。 - 可观测数据：\( \{ (\mathcal{X}_i, y_i) \}_{i=1}^n \)。树结构 \( T^* \) 和叶子节点均值 \( \mu_\ell \) 是未知的，需从数据中估计。

第二步：讲最小内核¶

最简特例：考虑 \( D=2 \)（输入为矩阵，即图像），\( p_1 = p_2 = 2 \)（2×2 矩阵），样本量 \( n=4 \)。输入张量 \( \mathcal{X}_i \in \mathbb{R}^{2 \times 2} \)，输出 \( y_i \in \mathbb{R} \)。假设数据由一棵深度为 1 的树（只有一个分裂节点）生成：分裂规则是“矩阵的 (1,1) 元素 \( x_{i,11} > 0.5 \)”。若 \( x_{i,11} > 0.5 \)，则 \( y_i = 1 \)；否则 \( y_i = 0 \)。噪声 \( \varepsilon_i = 0 \)（无噪声）。

核心思路：如何从数据中学习这个分裂规则？ 1. 候选分裂：对于每个 mode \( d \in \{1,2\} \)，每个索引 \( j \in \{1,\dots,p_d\} \)，每个可能的阈值 \( c \)（从观测到的 \( x_{i,dj} \) 值中取），计算分裂后的均方误差（MSE）减少量。 - 例如，mode=1, j=1（即矩阵的第一行第一列元素），候选阈值 c=0.5。分裂后：左子节点（\( x_{i,11} \leq 0.5 \)）包含样本 {i: \( x_{i,11} \leq 0.5 \)}，右子节点（\( x_{i,11} > 0.5 \)）包含其余样本。计算分裂后 MSE = 0（因为完美分离）。 - 其他候选分裂（如 mode=1, j=2，即第一行第二列元素）无法完美分离数据，MSE 更大。 2. 选择最优分裂：选择使 MSE 减少量最大的 \( (d, j, c) \)。在这个特例中，最优分裂是 (d=1, j=1, c=0.5)。 3. 递归：对每个子节点重复上述过程，直到达到停止条件（如叶子节点样本数小于阈值）。

为什么这个特例是内核：整篇论文的核心困难在于如何高效搜索所有候选分裂。当 \( D \) 和 \( p_d \) 很大时，候选分裂的数量是 \( \sum_{d=1}^D p_d \times n \)（每个 mode 的每个索引有 n 个候选阈值），这在大规模数据下是可行的。但作者进一步设计了随机化算法（随机采样 mode 和索引）来加速，这是本文的主要算法贡献。上述特例展示了分裂搜索的基本逻辑，而论文的一般情形只是将其扩展到更高阶张量和更复杂的树结构。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：如何设计高效且可解释的树模型，用于标量-张量回归和张量-张量回归。
核心工具 / 方法：提出了 tensor-input tree (TT)，包括快速随机化和确定性分裂算法，以及基于加法树集成的张量-张量回归扩展。
主要结论：TT 在计算效率上显著优于张量 GP（训练时间降低 1-2 个数量级），对输入张量逐元素噪声具有鲁棒性，且提供了收敛性保证。

关键设定与假设¶

在第二节最小记号的基础上，补全完整设定： - 标量-张量回归树： - 分裂准则：最小化分裂后的加权 MSE：\( \Delta = \text{MSE}_{\text{parent}} - (n_L/n) \text{MSE}_L - (n_R/n) \text{MSE}_R \)，其中 \( n_L, n_R \) 是左右子节点的样本数。 - 分裂候选：对于每个 mode \( d \)，每个索引 \( j \in \{1,\dots,p_d\} \)，候选阈值 \( c \) 取该索引上所有观测值的唯一值（最多 \( n \) 个）。总候选数 \( \leq \sum_{d=1}^D p_d \times n \)。 - 停止条件：叶子节点样本数小于 \( n_{\min} \)（用户指定），或 MSE 减少量小于阈值。 - 假设：输入张量 \( \mathcal{X}_i \) 的元素是连续随机变量（无离散值），且无缺失。 - 张量-张量回归树： - 加法树集成：\( \mathcal{Y}_i = \sum_{m=1}^M T_m(\mathcal{X}_i) + \mathcal{E}_i \)，其中 \( T_m \) 是标量-张量回归树（输出为标量），但每个 \( T_m \) 预测的是输出张量 \( \mathcal{Y}_i \) 的某个元素或线性组合。具体地，作者将输出张量展平为向量，然后对每个输出维度分别拟合标量-张量树，最后重组为张量。 - 假设：输出张量 \( \mathcal{Y}_i \) 的元素是连续的，且各输出维度之间条件独立（给定输入张量）。 - 相比已有文献的强化 / 放宽： - 相比张量 GP（Sun et al., 2023），TT 不假设核函数的可分性（separable kernel），因此能捕捉更复杂的非线性交互。 - 相比深度张量网络，TT 不需要梯度计算，训练更稳定。 - 相比传统树模型（CART），TT 直接利用张量结构（mode 和索引），而非将张量展平为向量（会丢失结构信息）。

主要结果¶

定理 1（标量-张量回归树的收敛性）：假设真实函数 \( f \) 是分段常数（树结构），且分裂规则基于张量的 mode 和索引。则当样本量 \( n \to \infty \) 时，TT 的预测 MSE 以概率 1 收敛到最优（即贝叶斯风险）。证明依赖于树模型的一致性理论（如 Breiman et al., 1984），但需要处理张量输入空间上的分裂搜索的渐近性质。
定理 2（随机化分裂算法的计算复杂度）：随机化算法（每次随机采样 \( K \) 个 mode 和 \( L \) 个索引）的期望运行时间为 \( O(n K L D) \)，而确定性算法为 \( O(n \sum_{d=1}^D p_d) \)。当 \( K \) 和 \( L \) 远小于 \( p_d \) 时，随机化算法可大幅加速。
实验结论：
在模拟数据上（张量大小 \( 10 \times 10 \times 10 \)，样本量 \( n=1000 \)），TT 的训练时间比张量 GP 快约 50 倍（0.2 秒 vs 10 秒），预测 MSE 相当或略优。
在真实数据上（脑电图 EEG 数据，张量大小 \( 64 \times 128 \times 256 \)，样本量 \( n=200 \)），TT 的预测精度与张量 GP 相当，但训练时间从数小时降至数分钟。
鲁棒性实验：对输入张量添加 10% 的逐元素高斯噪声，TT 的预测 MSE 仅增加 5%，而张量 GP 增加 20%。

证明路线与技术技巧（理论型必写，要具体）¶

整体路线（以定理 1 为例）： 1. 步骤 1：分裂搜索的一致性。证明当样本量足够大时，最优分裂（使 MSE 减少量最大）会收敛到真实分裂规则。这依赖于张量输入空间上的分裂候选的稠密性（每个 mode 的每个索引的阈值覆盖整个实数轴）。 2. 步骤 2：树结构的一致性。证明递归分裂过程会收敛到真实树结构。这需要处理“错误分裂”的概率（即选择了非最优分裂），并证明其随样本量指数衰减。 3. 步骤 3：预测误差的收敛性。利用树模型的一致性，证明叶子节点均值估计（样本均值）收敛到真实均值，从而预测 MSE 收敛到最优。

关键跳跃点： - 跳跃点 1：如何证明分裂搜索的一致性？传统 CART 的证明依赖于输入空间是欧几里得空间（分裂基于单个坐标），而张量输入的分裂基于“mode 和索引”，这相当于在张量的某个“切片”上做分裂。作者需要证明，对于任意 mode \( d \) 和索引 \( j \)，切片上的阈值搜索是稠密的（即任何真实分裂阈值都能被某个观测值逼近）。这依赖于输入张量元素的连续性假设。 - 跳跃点 2：如何控制随机化算法的误差？随机化算法只采样部分 mode 和索引，可能错过最优分裂。作者证明，只要采样数 \( K \) 和 \( L \) 随样本量增长（如 \( K = O(\log n) \)），错过最优分裂的概率趋于 0。这依赖于 mode 和索引的均匀重要性假设（即没有某个 mode 或索引是绝对主导的）。

技术技巧点名： - 随机化分裂搜索：借鉴了“随机森林”的随机特征采样思想，但应用于张量的 mode 和索引，而非单个特征。 - 确定性分裂搜索的剪枝：利用张量结构的稀疏性（如某些 mode 的维度很小），对候选分裂进行剪枝，避免全搜索。 - 加法树集成的梯度提升：对于张量-张量回归，使用梯度提升框架（类似 XGBoost）逐步添加树，每棵树拟合当前残差。

真实例子与应用¶

数据：脑电图（EEG）数据，来自一个公开数据集。输入张量是 \( 64 \times 128 \times 256 \)（64 个电极 × 128 个时间点 × 256 个频率），输出是受试者的认知负荷评分（标量）。
方法应用：将 TT 直接应用于该张量数据，使用随机化分裂算法（\( K=10, L=20 \)），树深度限制为 5，叶子节点最小样本数 10。
结果：TT 的预测 MSE 为 0.12，张量 GP 为 0.11（差异不显著），但 TT 训练时间仅 3 分钟，张量 GP 需 2 小时。
例子想说明什么：TT 在保持与张量 GP 相当预测精度的同时，大幅降低了计算成本，适合大规模张量数据。

🔎 结论是否比证明窄¶

窄结论 1：定理 1 的收敛性证明假设真实函数是分段常数（树结构），但论文在实验和讨论中声称 TT 适用于任意非线性函数。这属于“证明窄于 claim”——分段常数假设是强假设，实际应用中真实函数可能不是分段常数，此时 TT 的收敛性未得到理论保证。
窄结论 2：随机化算法的计算复杂度分析（定理 2）假设 mode 和索引的采样是均匀的，但未证明当某些 mode 或索引更重要时（即非均匀重要性），随机化算法是否仍有效。论文在实验中使用均匀采样，但未讨论非均匀情况。

四、开放问题（点到为止，扎根具体语句）¶

理论保证的扩展：定理 1 假设真实函数是分段常数。能否将收敛性证明扩展到更一般的函数类（如 Lipschitz 连续或 Hölder 连续）？这需要新的分裂准则和证明技巧。扎根于论文第 3 节“Theoretical justification”中的“we assume the true function is piecewise constant”。
随机化算法的自适应采样：论文的随机化算法使用均匀采样，但某些 mode 或索引可能更重要。能否设计自适应采样策略（如基于信息增益的采样），在保持计算效率的同时提高分裂质量？扎根于第 4 节“Randomized splitting algorithm”中的“we uniformly sample K modes and L indices”。
张量-张量回归的联合建模：论文的加法树集成将输出张量展平后独立建模，忽略了输出元素之间的相关性。能否设计一种树模型，直接对输出张量的结构（如低秩分解）进行建模？扎根于第 5 节“Tensor-on-tensor regression”中的“we flatten the output tensor and fit separate trees for each element”。
与贝叶斯方法的结合：论文未讨论贝叶斯树模型（如 BART）。能否将 TT 扩展到贝叶斯框架，提供不确定性量化？这需要设计张量输入空间上的先验分布。扎根于第 7 节“Discussion”中的“future work includes Bayesian extensions”。

Maintained by 陈星宇 · Homepage · Source on GitHub