优化随机森林推理步骤顺序,让模型在任意中断时仍保持高精度。
Jump Like A Squirrel: Optimized Execution Step Order for Anytime Random Forest Inference
- 按决策树单步粒度设计随时推理算法,提升中间结果质量。
- 后向松鼠序法性能接近最优解(94%),优于所有其他顺序。
- 适合资源受限设备上需快速响应的实时分类任务。
由于高效且体积小,决策树与随机森林是资源受限系统中常用的分类模型。在这些系统中,推理时间可能不足以完成整个模型的执行。理想情况下,已获得的预测置信度应被保留。任何时间算法可在任意时刻中断,同时提供随时间推移质量不断提升的结果。此前方法将随机森林实现为以树为粒度的任何时间算法,即在部分但非全部树执行后停止。然而,由于决策树在每一步对样本空间进行划分,每增加一步都会提升预测质量。本文提出以决策树单步为粒度的任何时间算法,从而可定义森林中步骤的执行顺序,具有优化平均准确率的潜力。我们提出最优顺序(指数时间求解)以及前向松鼠序和后向松鼠序(多项式时间启发式),分别贪心地最大化向下和向上遍历树时每一步的准确率。评估表明,后向松鼠序性能达到最优顺序的约94%,且接近所有其他步骤顺序的99%。
原文摘要 · Abstract (English)
Due to their efficiency and small size, decision trees and random forests are popular machine learning models used for classification on resource-constrained systems. In such systems, the available execution time for inference in a random forest might not be sufficient for a complete model execution. Ideally, the already gained prediction confidence should be retained. An anytime algorithm is designed to be able to be aborted anytime, while giving a result with an increasing quality over time. Previous approaches have realized random forests as anytime algorithms on the granularity of trees, stopping after some but not all trees of a forest have been executed. However, due to the way decision trees subdivide the sample space in every step, an increase in prediction quality is achieved with every additional step in one tree. In this paper, we realize decision trees and random forest as anytime algorithms on the granularity of single steps in trees. This approach opens a design space to define the step order in a forest, which has the potential to optimize the mean accuracy. We propose the Optimal Order, which finds a step order with a maximal mean accuracy in exponential runtime and the polynomial runtime heuristics Forward Squirrel Order and Backward Squirrel Order, which greedily maximize the accuracy for each additional step taken down and up the trees, respectively. Our evaluation shows, that the Backward Squirrel Order performs $\sim94\%$ as well as the Optimal Order and $\sim99\%$ as well as all other step orders.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。