論文の概要: Improving Decision Trees through the Lens of Parameterized Local Search
- arxiv url: http://arxiv.org/abs/2510.12726v1
- Date: Tue, 14 Oct 2025 17:06:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-15 21:19:15.003318
- Title: Improving Decision Trees through the Lens of Parameterized Local Search
- Title（参考訳）: パラメータ化局所探索レンズによる決定木の改良
- Authors: Juha Harviainen, Frank Sommer, Manuel Sorge,
- Abstract要約: 本研究では,これらの操作の1種類の固定数を実行することにより,分類誤差の最小化について検討する。
本稿では,本アルゴリズムの概念実証実装と実験結果について報告する。
- 参考スコア（独自算出の注目度）: 9.426097667758627
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |I|^{O(1)}$ time, where $|I|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.
- Abstract（参考訳）: 決定木を学習するためのアルゴリズムは、(1)カットの閾値を調整する、または(2)カットの特徴を交換するといったヒューリスティックな局所探索操作を含むことが多い。
本研究では,これらの操作の1種類の固定数を実行することにより,分類誤差の最小化について検討する。
対応する問題は一般にNP完全であることが分かるが, 難易度と難易度を説明する問題の性質を解析するために, 包括的パラメータ化・複雑度解析を行う。
例えば、小さな$d$機能や小さなドメインサイズの$D$の場合、問題は依然として難しいが、両者の組み合わせは固定パラメータのトラクタビリティを損なう。
すなわち、問題は$(D + 1)^{2d} \cdot |I|^{O(1)} の時間で解ける。
また,本アルゴリズムの概念実証実装を行い,実験結果について報告する。
関連論文リスト
- Optimal Decision Tree Pruning Revisited: Algorithms and Complexity [22.57063332430197]
我々は,サブツリーの更新と育成の基本的な作業に焦点をあてる。
サブツリー置換に間に合うように最適プルーニングを行うことができるが、サブツリーの更新にはNP完全である。
例えば、サブツリーの上昇は小さなドメインサイズでは難しいが、$D2d cdot |I|O(1)$timeでは、$|I|$が入力サイズである。
論文 参考訳（メタデータ） (2025-03-05T15:02:46Z) - Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Trainability Barriers in Low-Depth QAOA Landscapes [0.0]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための変分量子アルゴリズムである。
以前の結果から、小さなパラメータの固定数の解析性能が保証された。
本研究は,近年の数値研究の焦点である中間体制における訓練の難しさについて考察する。
論文 参考訳（メタデータ） (2024-02-15T18:45:30Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Experimental Design for Causal Effect Identification [31.23071073904698]
必要な効果を識別するために,最小限のコストで介入の収集を設計する問題を考察する。
まず、この問題がNPハードであることを証明し、次に最適な解や対数近似を求めるアルゴリズムを提案する。
これらのアルゴリズムは準最適解に反する可能性があるが、我々のシミュレーションはランダムグラフに対する小さな後悔を達成していることを示している。
論文 参考訳（メタデータ） (2022-05-04T13:19:04Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation [19.660527989370646]
我々は、その最適値に対する下界を自然に定義する緩和の族を提案する。
この族は常にゆるやかな緩和を含んでおり、我々はそれを見つけることができるアルゴリズムを与え、したがって、最初の非緩和NP-ハード問題を解く。
緩和を考えると、元の問題を2つの非重複部分(LP-tight 部分と難しい部分)に分解する。
論文 参考訳（メタデータ） (2020-04-14T09:10:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。