論文の概要: Efficient & Correct Predictive Equivalence for Decision Trees

• arxiv url: http://arxiv.org/abs/2509.17774v3
• Date: Fri, 03 Oct 2025 15:03:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:51.986617
• Title: Efficient & Correct Predictive Equivalence for Decision Trees
• Title（参考訳）: 決定木に対する効率的かつ正確な予測等価性
• Authors: Joao Marques-Silva, Alexey Ignatiev,
• Abstract要約: Rashomonの意思決定ツリー(DT)は、重要な使用方法を見つけます。 同じ分類関数、すなわち予測等価DTを計算するDTは、ラショーモン集合のかなりの部分を表すことができる。 本稿では,Quine-McCluskey (QM) 法において,最悪ケースの指数的実行時間と空間を誘導する決定木が存在することを示す。
• 参考スコア（独自算出の注目度）: 7.615032824973038
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Rashomon set of decision trees (DTs) finds importance uses. Recent work showed that DTs computing the same classification function, i.e. predictive equivalent DTs, can represent a significant fraction of the Rashomon set. Such redundancy is undesirable. For example, feature importance based on the Rashomon set becomes inaccurate due the existence of predictive equivalent DTs, i.e. DTs with the same prediction for every possible input. In recent work, McTavish et al. proposed solutions for several computational problems related with DTs, including that of deciding predictive equivalent DTs. The approach of McTavish et al. consists of applying the well-known method of Quine-McCluskey (QM) for obtaining minimum-size DNF (disjunctive normal form) representations of DTs, which are then used for comparing DTs for predictive equivalence. Furthermore, the minimum-size DNF representation was also applied to computing explanations for the predictions made by DTs, and to finding predictions in the presence of missing data. However, the problem of formula minimization is hard for the second level of the polynomial hierarchy, and the QM method may exhibit worst-case exponential running time and space. This paper first demonstrates that there exist decision trees that trigger the worst-case exponential running time and space of the QM method. Second, the paper shows that the QM method may incorrectly decide predictive equivalence, if two key constraints are not respected, and one may be difficult to formally guarantee. Third, the paper shows that any of the problems to which the smallest DNF representation has been applied to can be solved in polynomial time, in the size of the DT. The experiments confirm that, for DTs for which the worst-case of the QM method is triggered, the algorithms proposed in this paper are orders of magnitude faster than the ones proposed by McTavish et al.
• Abstract（参考訳）: Rashomonの意思決定ツリー(DT)は、重要な使用方法を見つけます。 近年の研究では、DTが同じ分類関数、すなわち予測等価DTを演算することは、Rashomon集合のかなりの割合を表現できることが示されている。 そのような冗長性は望ましくない。 例えば、ラショモン集合に基づく特徴重要度は、予測等価なDTの存在、すなわち全ての可能な入力に対して同じ予測を持つDTの存在によって不正確なものとなる。 最近の研究でMcTavishらは、予測等価DTを決定することを含む、DTに関連するいくつかの計算問題に対する解決策を提案した。 McTavish et al のアプローチは、DT の最小サイズ DNF (disjunctive normal form) 表現を得るために、Quine-McCluskey (QM) のよく知られた方法を適用することで成り立っている。 さらに、DTによる予測の計算説明や、欠落データの有無の予測にも、最小サイズDNF表現を適用した。 しかし、多項式階層の第2レベルにおいては、式最小化の問題は困難であり、QM法は最悪の指数的な実行時間と空間を示す可能性がある。 本稿ではまず,QM法における最悪の指数的実行時間と空間を誘導する決定木の存在を実証する。 第2に,2つの鍵制約が尊重されない場合,QM法が誤った予測等価性を決定する可能性があること,また,公式に保証することが困難であることを示す。 第三に、最小のDNF表現が適用された問題のどれでも、DTのサイズで多項式時間で解けることを示す。 実験により,QM法の最悪のケースが引き起こされるDTに対して,本論文で提案するアルゴリズムは,McTavishらの提案よりも桁違いに高速であることが確認された。

関連論文リスト

• An Eager Satisfiability Modulo Theories Solver for Algebraic Datatypes [4.393684402895834]
  Algebraic Data Types (ADT) は関数型プログラミング言語で古典的に見られる構造である。 我々は,基本的に異なるアプローチ,エフェーガーアプローチを採るSMTソルバを提案する。
  論文  参考訳（メタデータ） (2023-10-18T18:14:18Z)
• AdjointDPM: Adjoint Sensitivity Method for Gradient Backpropagation of Diffusion Probabilistic Models [103.41269503488546]
  既存のカスタマイズ方法は、事前訓練された拡散確率モデルをユーザが提供する概念に合わせるために、複数の参照例にアクセスする必要がある。 本論文は、DPMカスタマイズの課題として、生成コンテンツ上で定義された差別化可能な指標が唯一利用可能な監督基準である場合に解決することを目的とする。 本稿では,拡散モデルから新しいサンプルを初めて生成するAdjointDPMを提案する。 次に、随伴感度法を用いて、損失の勾配をモデルのパラメータにバックプロパゲートする。
  論文  参考訳（メタデータ） (2023-07-20T09:06:21Z)
• DisDiff: Unsupervised Disentanglement of Diffusion Probabilistic Models [42.58375679841317]
  拡散確率モデル(DPM)の解離という新たな課題を提案する。 この課題は、観測の背後にある固有の因子を自動的に発見し、DPMの勾配場を下位段階の磁場に分解することである。 そこで我々は,DPMの枠組みにおいて,不整合表現学習を実現するために,DisDiffという教師なしのアプローチを考案した。
  論文  参考訳（メタデータ） (2023-01-31T15:58:32Z)
• Provably Precise, Succinct and Efficient Explanations for Decision Trees [32.062312674333775]
  決定木(DT)は解釈可能な分類器を具現化する。 DTの予測は厳密な説明で説明されるべきである。 デルタ関連集合は簡潔で正確であることを示す。
  論文  参考訳（メタデータ） (2022-05-19T13:54:52Z)
• A Novel Splitting Criterion Inspired by Geometric Mean Metric Learning for Decision Tree [27.253204680627952]
  決定木(DT)は、多くのアプリケーションにおいて、その印象的な経験的性能と解釈可能性のために、永続的な研究の注目を集めている。 本稿では,成長速度を上げるために分割基準を新たに設計する。 この基準は、幾何学的平均距離学習(GMML)から導出され、その対角化行列制約の下で最適化される。
  論文  参考訳（メタデータ） (2022-04-23T07:33:57Z)
• LSDAT: Low-Rank and Sparse Decomposition for Decision-based Adversarial Attack [74.5144793386864]
  LSDATは、入力サンプルのスパース成分と対向サンプルのスパース成分によって形成される低次元部分空間における摂動を加工する。 LSDは画像ピクセル領域で直接動作し、スパース性などの非$ell$制約が満たされることを保証します。
  論文  参考訳（メタデータ） (2021-03-19T13:10:47Z)
• Risk Aware Optimization of Water Sensor Placement [0.0]
  センサ毎のデータ構造(時間的ヒートマップの集合)収集シミュレーションを提案する。 我々は問題固有の収束問題を検出する指標を特定する。 ベンチマークと実世界ネットワークの結果を提示します。
  論文  参考訳（メタデータ） (2021-03-08T16:12:02Z)
• On Explaining Decision Trees [17.646704122091087]
  決定木(DT)は、解釈可能な機械学習(ML)モデルとして知られるようになったものをエピトマイズする。 本稿では,DT の経路が PI-Explanation よりも任意に大きいような条件下では DT の解釈が困難であることを示す。
  論文  参考訳（メタデータ） (2020-10-21T14:33:53Z)

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

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