論文の概要: Fast decision tree learning solves hard coding-theoretic problems
- arxiv url: http://arxiv.org/abs/2409.13096v2
- Date: Wed, 25 Sep 2024 21:46:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-07 11:52:12.988342
- Title: Fast decision tree learning solves hard coding-theoretic problems
- Title（参考訳）: 高速決定木学習はハードコーディング理論の問題を解決する
- Authors: Caleb Koch, Carmen Strassle, Li-Yang Tan,
- Abstract要約: 我々は、Ehrenfeucht と Haussler のアルゴリズムの改善により、$k$-NCP に対して$O(log n)$-approximation アルゴリズムが得られることを示す。
これは、$k$-NCPのアルゴリズムを設計するための新しい道、あるいはEhrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
- 参考スコア（独自算出の注目度）: 7.420043502440765
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem ($k$-NCP). Despite significant effort by the respective communities, algorithmic progress on both problems has been stuck: the fastest known algorithm for the former runs in quasipolynomial time (Ehrenfeucht and Haussler 1989) and the best known approximation ratio for the latter is $O(n/\log n)$ (Berman and Karpinsky 2002; Alon, Panigrahy, and Yekhanin 2009). Research on both problems has thus far proceeded independently with no known connections. We show that $\textit{any}$ improvement of Ehrenfeucht and Haussler's algorithm will yield $O(\log n)$-approximation algorithms for $k$-NCP, an exponential improvement of the current state of the art. This can be interpreted either as a new avenue for designing algorithms for $k$-NCP, or as one for establishing the optimality of Ehrenfeucht and Haussler's algorithm. Furthermore, our reduction along with existing inapproximability results for $k$-NCP already rule out polynomial-time algorithms for properly learning decision trees. A notable aspect of our hardness results is that they hold even in the setting of $\textit{weak}$ learning whereas prior ones were limited to the setting of strong learning.
- Abstract（参考訳）: 我々は、PAC学習決定ツリーの適切な問題とパラメータ化Nearest Codeword Problem(k$-NCP)を結びつける。
半ポリノミカル時間における前者の最速のアルゴリズム (Ehrenfeucht and Haussler 1989) と後者の近似比は$O(n/\log n)$ (Berman and Karpinsky 2002; Alon, Panigrahy, Yekhanin 2009) である。
これまでのところ、両問題の研究は無関係で独立に進められている。
我々は、Ehrenfeucht と Haussler のアルゴリズムの改善に対して、$k$-NCP に対して$O(\log n)$-approximation アルゴリズムが得られることを示す。
これは、$k$-NCPのアルゴリズムを設計するための新しい道か、Ehrenfeucht と Haussler のアルゴリズムの最適性を確立するための道と解釈できる。
さらに、既存の$k$-NCPに対する不適応性とともに、決定木を適切に学習するための多項式時間アルゴリズムを既に除外している。
難易度の結果の顕著な側面は、$\textit{weak}$ Learningの設定であっても、以前のものは強い学習の設定に限られていたことです。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning [9.594432031144716]
アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。
NPハードな定性推論問題を解くための新しい枠組みを提案する。
我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
論文 参考訳（メタデータ） (2023-05-25T11:45:12Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文 参考訳（メタデータ） (2021-09-01T22:12:47Z) - Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。
非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。
基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
論文 参考訳（メタデータ） (2021-07-03T13:04:41Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Adversarial Online Learning with Changing Action Sets: Efficient
Algorithms with Approximate Regret Bounds [48.312484940846]
睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。
各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。
我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-03-07T02:13:21Z) - Optimal Sparse Decision Trees [25.043477914272046]
この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。
このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。
我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
論文 参考訳（メタデータ） (2019-04-29T17:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。