論文の概要: Decision tree heuristics can fail, even in the smoothed setting
- arxiv url: http://arxiv.org/abs/2107.00819v1
- Date: Fri, 2 Jul 2021 04:24:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-05 12:57:00.802972
- Title: Decision tree heuristics can fail, even in the smoothed setting
- Title（参考訳）: 決定木ヒューリスティックスは滑らかな設定でも失敗する可能性がある
- Authors: Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan
- Abstract要約: 高い精度を達成する前に、深さ2Omega(k)$のツリーを構築できるターゲットが、$k$-juntasに非常に近いことを示している。
我々は、深さ$k$決定木であるターゲットを構築し、滑らかな設定であっても、高い精度を達成する前に深さ$2Omega(k)$のツリーを構築することを示す。
- 参考スコア（独自算出の注目度）: 25.763690981846125
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Greedy decision tree learning heuristics are mainstays of machine learning
practice, but theoretical justification for their empirical success remains
elusive. In fact, it has long been known that there are simple target functions
for which they fail badly (Kearns and Mansour, STOC 1996).
Recent work of Brutzkus, Daniely, and Malach (COLT 2020) considered the
smoothed analysis model as a possible avenue towards resolving this disconnect.
Within the smoothed setting and for targets $f$ that are $k$-juntas, they
showed that these heuristics successfully learn $f$ with depth-$k$ decision
tree hypotheses. They conjectured that the same guarantee holds more generally
for targets that are depth-$k$ decision trees.
We provide a counterexample to this conjecture: we construct targets that are
depth-$k$ decision trees and show that even in the smoothed setting, these
heuristics build trees of depth $2^{\Omega(k)}$ before achieving high accuracy.
We also show that the guarantees of Brutzkus et al. cannot extend to the
agnostic setting: there are targets that are very close to $k$-juntas, for
which these heuristics build trees of depth $2^{\Omega(k)}$ before achieving
high accuracy.
- Abstract（参考訳）: 生意気な決定木学習ヒューリスティックスは、機械学習の実践の主役であるが、その経験的成功に対する理論的正当化は、いまだ解明されていない。
実際、それらがひどく失敗する単純な対象関数があることは長年知られている(Kearns and Mansour, STOC 1996)。
Brutzkus, Daniely, and Malach (COLT 2020) の最近の研究は、スムーズな解析モデルを、この切断を解決するための道のりとして考えている。
平滑化設定の中で、目標の$f$は$k$-juntasであり、これらのヒューリスティックは$f$を深さ$k$決定木仮説で学べることを示した。
彼らは、同じ保証がより一般に深さが$k$決定木である目標に対して成り立つと推測した。
我々は、深さ$k$決定木であるターゲットを構築し、滑らかな設定であっても、これらのヒューリスティックスは高い精度を達成する前に深さ$2^{\Omega(k)}$のツリーを構築することを示す。
また、brutzkusらによる保証も示している。
目標が$k$-juntasに非常に近い場合、これらのヒューリスティックスは高い精度を達成する前に深さ270Omega(k)}$のツリーを構築する。
関連論文リスト
- Any Target Can be Offense: Adversarial Example Generation via Generalized Latent Infection [83.72430401516674]
GAKerは任意のターゲットクラスに対して逆例を構築することができる。
本手法は,未知のクラスに対する攻撃成功率を約14.13%で達成する。
論文 参考訳（メタデータ） (2024-07-17T03:24:09Z) - Learnability of high-dimensional targets by two-parameter models and gradient flow [13.794391803767617]
Wd$ に対して、GF-非学習可能なターゲットの大規模な部分集合が必ず存在することを示す。
特に、学習可能な対象の集合は $mathbb Rd$ では密でなく、$mathbb Rd$ の任意の部分集合は $W$-次元球面に同型であり、非学習可能な対象を含む。
論文 参考訳（メタデータ） (2024-02-26T23:56:11Z) - Understanding Deep Neural Function Approximation in Reinforcement
Learning via $\epsilon$-Greedy Exploration [53.90873926758026]
本稿では、強化学習(RL)における深部神経機能近似の理論的研究について述べる。
我々は、Besov(およびBarron)関数空間によって与えられるディープ(および2層)ニューラルネットワークによる$epsilon$-greedy探索により、バリューベースのアルゴリズムに焦点を当てる。
我々の解析は、ある平均測度$mu$の上の$L2(mathrmdmu)$-integrable空間における時間差誤差を再構成し、非イド設定の下で一般化問題に変換する。
論文 参考訳（メタデータ） (2022-09-15T15:42:47Z) - There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning
for Mazes [64.05903267230467]
相互理解性は,強化学習システムにおける信頼性に不可欠なビルディングブロックである。
場合によっては、最適性を保ちつつ、政策の解釈可能性を達成することができることを示す。
論文 参考訳（メタデータ） (2022-06-09T04:23:26Z) - Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。
16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
論文 参考訳（メタデータ） (2021-12-29T18:22:28Z) - Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文 参考訳（メタデータ） (2021-09-01T22:12:47Z) - Growing Deep Forests Efficiently with Soft Routing and Learned
Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。
我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。
MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文 参考訳（メタデータ） (2020-12-29T18:05:05Z) - An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃
提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。
私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
論文 参考訳（メタデータ） (2020-10-22T10:59:49Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳（メタデータ） (2020-08-20T03:42:40Z) - Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文 参考訳（メタデータ） (2020-06-01T06:44:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。