論文の概要: Approximate Optimal Active Learning of Decision Trees

• arxiv url: http://arxiv.org/abs/2512.03971v1
• Date: Wed, 03 Dec 2025 17:03:39 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-04 12:07:01.250567
• Title: Approximate Optimal Active Learning of Decision Trees
• Title（参考訳）: 決定木の近似最適能動学習
• Authors: Zunchen Huang, Chenglu Jin,
• Abstract要約: 本稿では,メンバシップクエリのみを用いて未知のバイナリ決定木を積極的に学習する問題について考察する。 本稿では,仮説空間の減少を推定するために近似モデル計数を用いる決定木を能動的に学習するための記号的手法を提案する。 決定木に関する実験により、この手法は少数のクエリのみを用いて正しいモデルに確実に収束することが示された。
• 参考スコア（独自算出の注目度）: 4.834817711255487
• License:
• Abstract: We consider the problem of actively learning an unknown binary decision tree using only membership queries, a setting in which the learner must reason about a large hypothesis space while maintaining formal guarantees. Rather than enumerating candidate trees or relying on heuristic impurity or entropy measures, we encode the entire space of bounded-depth decision trees symbolically in SAT formulas. We propose a symbolic method for active learning of decision trees, in which approximate model counting is used to estimate the reduction of the hypothesis space caused by each potential query, enabling near-optimal query selection without full model enumeration. The resulting learner incrementally strengthens a CNF representation based on observed query outcomes, and approximate model counter ApproxMC is invoked to quantify the remaining version space in a sound and scalable manner. Additionally, when ApproxMC stagnates, a functional equivalence check is performed to verify that all remaining hypotheses are functionally identical. Experiments on decision trees show that the method reliably converges to the correct model using only a handful of queries, while retaining a rigorous SAT-based foundation suitable for formal analysis and verification.
• Abstract（参考訳）: 本稿では,正規の保証を維持しつつ,学習者が大きな仮説空間を推論しなければならないような,未知のバイナリ決定木を会員クエリのみを用いて積極的に学習する問題について考察する。 候補木を列挙したり、ヒューリスティック不純物やエントロピー測度に依存するのではなく、SAT式に象徴される有界深度決定木の全体空間を符号化する。 そこで本研究では,決定木を探索的に学習するシンボリックな手法を提案する。この手法は,潜在的なクエリ毎に発生する仮説空間の減少を近似モデルカウントを用いて推定し,完全なモデル列挙を行なわずにほぼ最適なクエリ選択を可能にする。 得られた学習者は、観測されたクエリ結果に基づいてCNF表現を漸進的に強化し、近似モデルカウンタ ApproxMC を起動して、残りのバージョン空間を健全でスケーラブルな方法で定量化する。 さらに、ApproxMCが停滞すると、残りの全ての仮説が機能的に同一であることを検証するために、関数同値チェックが実行される。 決定木に関する実験により,本手法は形式解析と検証に適した厳密なSATベース基盤を維持しつつ,少数のクエリのみを用いて正しいモデルに確実に収束することが示された。

関連論文リスト

• Leveraging Predictive Equivalence in Decision Trees [25.79772180003752]
  決定木は解釈可能な機械学習に広く使われている。 本稿では,予測等価性を示さない決定木の表現について述べる。 決定木は、機能値のテスト時間不足に対して驚くほど堅牢であることを示す。
  論文  参考訳（メタデータ） (2025-06-17T03:11:30Z)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  本稿では,予測決定木アンサンブルを学習するためのハイブリッドアモータイズされた構造推論手法を提案する。 提案手法であるDT-GFNは,標準分類ベンチマークにおける最先端決定木やディープラーニング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2025-03-10T07:05:07Z)
• Model-free Methods for Event History Analysis and Efficient Adjustment (PhD Thesis) [55.2480439325792]
  この論文は、モデルフリーの観点から統一された統計学への独立した貢献のシリーズである。 第1章では、機械学習から予測技術を活用する柔軟なメソッドを定式化するために、モデルフリーの視点をどのように利用できるか、詳しく説明している。 第2章では、あるプロセスの進化が他のプロセスに直接影響されるかどうかを記述した地域独立の概念を研究している。
  論文  参考訳（メタデータ） (2025-02-11T19:24:09Z)
• Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
  本稿では,大規模言語モデル(LLM)を用いて,効率的な特徴生成ルールを同定するフレームワークを提案する。 我々は、自然言語で容易に表現できるため、この推論情報を伝達するために決定木を使用します。 OCTreeは様々なベンチマークで様々な予測モデルの性能を継続的に向上させる。
  論文  参考訳（メタデータ） (2024-06-12T08:31:34Z)
• Learning accurate and interpretable tree-based models [27.203303726977616]
  我々は、同じドメインからデータに繰り返しアクセスする木に基づく学習アルゴリズムを設計するためのアプローチを開発する。 本稿では,よく使われるエントロピーとジニ不純物に基づく基準を補間するトップダウンアルゴリズムにおいて,ノード分割基準の新しいパラメータ化クラスを提案する。 我々は、ランダムな森林や傾斜した木など、一般的な木に基づくアンサンブルのチューニングに結果を拡張した。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• Bisimulation Learning [55.859538562698496]
  我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。 提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
  論文  参考訳（メタデータ） (2024-05-24T17:11:27Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Regularized impurity reduction: Accurate decision trees with complexity guarantees [20.170305081348328]
  本稿では,木複雑性の対数近似を保証する木推論アルゴリズムを提案する。 改良されたアルゴリズムは予測精度と木の複雑さのバランスが良好である。
  論文  参考訳（メタデータ） (2022-08-23T13:15:19Z)
• The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
  理想のゴッテマン・キタエフ・プレスキル安定化状態からなる計算モデルを考える。 測定結果の確率密度関数を計算するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-19T18:03:17Z)

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

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