論文の概要: Active Learning for Decision Trees with Provable Guarantees

• arxiv url: http://arxiv.org/abs/2601.20775v1
• Date: Wed, 28 Jan 2026 17:02:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-29 15:46:07.032019
• Title: Active Learning for Decision Trees with Provable Guarantees
• Title（参考訳）: 確率的保証をもつ決定木に対する能動的学習
• Authors: Arshia Soltani Moakhar, Tanapoom Laoaron, Faraz Ghahremani, Kiarash Banihashem, MohammadTaghi Hajiaghayi,
• Abstract要約: 決定木に対する不一致係数を初めて解析する。 乗算誤差保証を実現する二項分類のための最初の一般能動学習アルゴリズムを提案する。 我々はラベルの複雑さを低くし、アルゴリズムのエラー耐性への依存度が$$が最適に近いことを示す。
• 参考スコア（独自算出の注目度）: 21.408034432864614
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This paper advances the theoretical understanding of active learning label complexity for decision trees as binary classifiers. We make two main contributions. First, we provide the first analysis of the disagreement coefficient for decision trees-a key parameter governing active learning label complexity. Our analysis holds under two natural assumptions required for achieving polylogarithmic label complexity, (i) each root-to-leaf path queries distinct feature dimensions, and (ii) the input data has a regular, grid-like structure. We show these assumptions are essential, as relaxing them leads to polynomial label complexity. Second, we present the first general active learning algorithm for binary classification that achieves a multiplicative error guarantee, producing a $(1+ε)$-approximate classifier. By combining these results, we design an active learning algorithm for decision trees that uses only a polylogarithmic number of label queries in the dataset size, under the stated assumptions. Finally, we establish a label complexity lower bound, showing our algorithm's dependence on the error tolerance $ε$ is close to optimal.
• Abstract（参考訳）: 本稿では,二項分類器としての決定木に対するアクティブラーニングラベルの複雑性の理論的理解を推し進める。 主な貢献は2つある。 まず、意思決定木に対する不一致係数の最初の分析を行い、アクティブラーニングラベルの複雑さを規定する重要なパラメータについて述べる。 我々の分析は、多言語ラベルの複雑さを達成するのに必要な2つの自然な仮定の下に成り立っている。 (i)各ルート・ツー・リーフパスクエリが特徴次元を区別し、 (ii)入力データは、正規のグリッドのような構造を持つ。 これらの仮定は、それらの緩和が多項式ラベルの複雑さにつながるため、不可欠であることを示す。 第二に、二項分類のための最初の一般能動学習アルゴリズムを提案し、乗算誤差保証を実現し、$(1+ε)$-approximate 分類器を生成する。 これらの結果を組み合わせることで,提案した仮定に基づいて,データセットサイズにおけるラベルクエリの多対数数のみを使用する決定木に対する能動的学習アルゴリズムを設計する。 最後に、ラベル複雑性の低い境界を確立し、エラー耐性へのアルゴリズムの依存度が$ε$と最適に近いことを示す。

関連論文リスト

• Efficient and Scalable Neural Symbolic Search for Knowledge Graph Complex Query Answering [50.1887329564127]
  複雑なクエリに対する効率的でスケーラブルなシンボル検索フレームワークを提案する。 我々のフレームワークは、ほぼ同じ性能を維持しながら、シンボリックメソッドの計算負荷を90%削減する。
  論文  参考訳（メタデータ） (2025-05-13T01:24:09Z)
• Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
  我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。 サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。 例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
  論文  参考訳（メタデータ） (2025-03-05T15:02:46Z)
• Bidirectional Logits Tree: Pursuing Granularity Reconcilement in Fine-Grained Classification [89.20477310885731]
  本稿では,粒度分類タスクにおけるグラニュラリティコンペティションの課題について述べる。 既存のアプローチは通常、共通のベースエンコーダから抽出された共有特徴に基づいて、独立した階層認識モデルを開発する。 グラニュラリティ再構成のための双方向ロジットツリー(BiLT)と呼ばれる新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-12-17T10:42:19Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  カリキュラムベースの論理認識型チューニングフレームワークであるLACTを提案する。 具体的には、任意の一階論理クエリをバイナリツリー分解によって拡張する。 広く使われているデータセットに対する実験では、LATは高度な手法よりも大幅に改善(平均+5.5% MRRスコア)し、新しい最先端技術を実現している。
  論文  参考訳（メタデータ） (2024-05-02T18:12:08Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
  論文  参考訳（メタデータ） (2023-06-09T14:01:26Z)
• Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
  任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。 本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
  論文  参考訳（メタデータ） (2023-02-09T08:35:17Z)
• Exact learning and test theory [0.0]
  任意の無限二元情報システムについて検討し、そのそれぞれが無限個の要素からなる。 本稿では,有限個の属性によって記述される情報システムに関する問題について考察する。
  論文  参考訳（メタデータ） (2022-01-12T15:10:22Z)
• Measure Inducing Classification and Regression Trees for Functional Data [0.0]
  機能的データ分析の文脈における分類と回帰問題に対する木に基づくアルゴリズムを提案する。 これは、制約付き凸最適化により重み付き汎函数 L2$ 空間を学習することで達成される。
  論文  参考訳（メタデータ） (2020-10-30T18:49:53Z)
• Probabilistic Label Trees for Extreme Multi-label Classification [8.347190888362194]
  極端なマルチラベル分類(XMLC)の問題は,木としてラベルを整理することで効率的に処理される。 PLTは多ラベル問題に対する階層的ソフトマックスの一般化として扱うことができる。 このモデルを導入し、トレーニングと推論手順とその計算コストについて論じる。 完全にオンラインのアルゴリズムと木構造を持つアルゴリズムとの間には,特定の等価性があることを実証する。
  論文  参考訳（メタデータ） (2020-09-23T15:30:00Z)

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

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