論文の概要: WCDT: Systematic WCET Optimization for Decision Tree Implementations

• arxiv url: http://arxiv.org/abs/2501.17428v1
• Date: Wed, 29 Jan 2025 06:01:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-30 15:53:04.396510
• Title: WCDT: Systematic WCET Optimization for Decision Tree Implementations
• Title（参考訳）: WCDT:決定木実装のための系統的WCET最適化
• Authors: Nils Hölscher, Christian Hakert, Georg von der Brüggen, Jian-Jia Chen, Kuan-Hsun Chen, Jan Reineke,
• Abstract要約: 安全な操作を確保するためには、機械学習モデルの最悪の実行時間(WCET)が必要である。 決定木実装のWCET最適化のための体系的アプローチを開発する。 我々は,サロゲートモデルとWCET最適化アルゴリズムの両方を実験的に評価した。
• 参考スコア（独自算出の注目度）: 4.95559363788634
• License:
• Abstract: Machine-learning models are increasingly deployed on resource-constrained embedded systems with strict timing constraints. In such scenarios, the worst-case execution time (WCET) of the models is required to ensure safe operation. Specifically, decision trees are a prominent class of machine-learning models and the main building blocks of tree-based ensemble models (e.g., random forests), which are commonly employed in resource-constrained embedded systems. In this paper, we develop a systematic approach for WCET optimization of decision tree implementations. To this end, we introduce a linear surrogate model that estimates the execution time of individual paths through a decision tree based on the path's length and the number of taken branches. We provide an optimization algorithm that constructively builds a WCET-optimal implementation of a given decision tree with respect to this surrogate model. We experimentally evaluate both the surrogate model and the WCET-optimization algorithm. The evaluation shows that the optimization algorithm improves analytically determined WCET by up to $17\%$ compared to an unoptimized implementation.
• Abstract（参考訳）: 機械学習モデルは、厳密なタイミング制約のあるリソース制約の組込みシステムにますますデプロイされる。 このようなシナリオでは、安全な操作を保証するために、モデルの最悪の実行時間(WCET)が要求される。 具体的には、決定木は機械学習モデルの顕著なクラスであり、資源制約の組込みシステムで一般的に使用される木に基づくアンサンブルモデル(例:ランダム森林)の主要な構成要素である。 本稿では,決定木実装のWCET最適化のための体系的アプローチを開発する。 この目的のために、経路の長さと取られた分岐数に基づいて、決定木を介して個々の経路の実行時間を推定する線形サロゲートモデルを導入する。 このサロゲートモデルに関して、与えられた決定ツリーのWCET最適化実装を構築的に構築する最適化アルゴリズムを提供する。 我々は,サロゲートモデルとWCET最適化アルゴリズムの両方を実験的に評価した。 評価の結果,最適化アルゴリズムは最適化されていない実装と比較して,解析的に決定されたWCETを最大17.%改善することがわかった。

関連論文リスト

• TREE: Tree Regularization for Efficient Execution [4.205565040528205]
  本稿では,決定木の訓練中に不均一な確率分布を報知することにより,経路長を削減する手法を提案する。 具体的には,CARTアルゴリズムの不純物を規則化し,低不純物だけでなく,分割基準の評価にも高い非対称分布を求める。
  論文  参考訳（メタデータ） (2024-06-18T12:01:06Z)
• When to Update Your Model: Constrained Model-based Reinforcement Learning [50.74369835934703]
  モデルベースRL(MBRL)の非遅延性能保証のための新規で一般的な理論スキームを提案する。 続いて導いた境界は、モデルシフトとパフォーマンス改善の関係を明らかにします。 さらなる例では、動的に変化する探索からの学習モデルが、最終的なリターンの恩恵をもたらすことが示されている。
  論文  参考訳（メタデータ） (2022-10-15T17:57:43Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• bsnsing: A decision tree induction method based on recursive optimal boolean rule composition [2.28438857884398]
  本稿では,決定木帰納過程における分割規則選択を最適化するMIP(Mixed-integer Programming)の定式化を提案する。 商用の解法よりも高速に実例を解くことができる効率的な探索解法を開発した。
  論文  参考訳（メタデータ） (2022-05-30T17:13:57Z)
• Stochastic Optimization Forests [60.523606291705214]
  標準的なランダムな森林アルゴリズムのように予測精度を向上させるために分割するのではなく、分割を選択した木を栽培し、下流の意思決定品質を直接最適化することで、森林決定政策の訓練方法を示す。 概略分割基準は、各候補分割に対して正確に最適化された森林アルゴリズムに近い性能を保ちながら、100倍のランニング時間を短縮できることを示す。
  論文  参考訳（メタデータ） (2020-08-17T16:56:06Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)
• ENTMOOT: A Framework for Optimization over Ensemble Tree Models [57.98561336670884]
  ENTMOOTは、ツリーモデルをより大きな最適化問題に統合するためのフレームワークである。 ENTMOOTは、ツリーモデルの意思決定とブラックボックス最適化への単純な統合を可能にしていることを示す。
  論文  参考訳（メタデータ） (2020-03-10T14:34:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。