arXiv:2505.03955cs.LGcs.SI2025-05

提出网络流优化方法,实现高效多层预测一致性校正。

Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation

  • 将层级预测校正建模为网络流优化问题,支持任意网络结构。
  • 在稀疏网络下复杂度降至O(n² log n),比MinT快3-40倍。
  • 支持动态更新且保持最优性,适合实时预测场景。

层级预测校正需确保多级汇总关系一致(如区级预测之和等于省级)。现有方法如MinT仅适用于树形结构且计算成本高。本文提出FlowRec,将层级预测校正转化为网络流优化,可处理任意网络结构。尽管ℓ₀范数下校正为NP难,但所有ℓₚ(p>0)范数及严格凸可微损失函数下均可多项式求解。稀疏网络中复杂度为O(n² log n),显著优于MinT的O(n³)。FlowRec通过直接利用网络结构替代MinT的误差协方差估计,实现了对一般网络的扩展。其关键创新在于动态场景下的高效局部更新:当基础预测改进时,初始校正仍保持最优。此外,建立误差有界近似校正机制,支持时间敏感应用中的快速更新。在模拟与真实数据集上的实验表明,FlowRec在准确率、运行时间(提升3-40倍)和内存使用(降低5-7倍)上均显著优于基线。

原文摘要 · Abstract (English)

Hierarchical forecasting with reconciliation requires forecasting values of a hierarchy (e.g.~customer demand in a state and district), such that forecast values are linked (e.g.~ district forecasts should add up to the state forecast). Basic forecasting provides no guarantee for these desired structural relationships. Reconciliation addresses this problem, which is crucial for organizations requiring coherent predictions across multiple aggregation levels. Current methods like minimum trace (MinT) are mostly limited to tree structures and are computationally expensive. We introduce FlowRec, which reformulates hierarchical forecast reconciliation as a network flow optimization, enabling forecasting on generalized network structures. While reconciliation under the $\ell_0$ norm is NP-hard, we prove polynomial-time solvability for all $\ell_{p > 0}$ norms and , for any strictly convex and continuously differentiable loss function. For sparse networks, FlowRec achieves $O(n^2\log n)$ complexity, significantly improving upon MinT's $O(n^3)$. Furthermore, we prove that FlowRec extends MinT to handle general networks, replacing MinT's error-covariance estimation step with direct network structural information. A key novelty of our approach is its handling of dynamic scenarios: while traditional methods recompute both base forecasts and reconciliation, FlowRec provides efficient localised updates with optimality guarantees. Monotonicity ensures that when forecasts improve incrementally, the initial reconciliation remains optimal. We also establish efficient, error-bounded approximate reconciliation, enabling fast updates in time-critical applications. Experiments on both simulated and real benchmarks demonstrate that FlowRec improves accuracy, runtime by 3-40x and memory usage by 5-7x. These results establish FlowRec as a powerful tool for large-scale hierarchical forecasting applications.

预测校正网络流层级预测动态更新

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。