論文の概要: Estimating decision tree learnability with polylogarithmic sample
complexity
- arxiv url: http://arxiv.org/abs/2011.01584v1
- Date: Tue, 3 Nov 2020 09:26:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 06:04:15.895484
- Title: Estimating decision tree learnability with polylogarithmic sample
complexity
- Title(参考訳): 多対数サンプル複雑性を用いた決定木学習可能性の推定
- Authors: Guy Blanc, Neha Gupta, Jane Lange, Li-Yang Tan
- Abstract要約: トップダウン決定木学習は,高効率な学習可能性推定に有効であることを示す。
決定木仮説のラベル $T(xstar$)$ が多対数的に多くのラベル付き例で計算可能であることを示す。
- 参考スコア(独自算出の注目度): 16.832966312395126
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We show that top-down decision tree learning heuristics are amenable to
highly efficient learnability estimation: for monotone target functions, the
error of the decision tree hypothesis constructed by these heuristics can be
estimated with polylogarithmically many labeled examples, exponentially smaller
than the number necessary to run these heuristics, and indeed, exponentially
smaller than information-theoretic minimum required to learn a good decision
tree. This adds to a small but growing list of fundamental learning algorithms
that have been shown to be amenable to learnability estimation.
En route to this result, we design and analyze sample-efficient minibatch
versions of top-down decision tree learning heuristics and show that they
achieve the same provable guarantees as the full-batch versions. We further
give "active local" versions of these heuristics: given a test point $x^\star$,
we show how the label $T(x^\star)$ of the decision tree hypothesis $T$ can be
computed with polylogarithmically many labeled examples, exponentially smaller
than the number necessary to learn $T$.
- Abstract(参考訳): 単調な対象関数の場合、これらのヒューリスティックによって構築された決定木仮説の誤差は、多くのラベル付き例で推定でき、これらのヒューリスティックスを実行するのに必要な数よりも指数関数的に小さく、実際、良い決定木を学ぶのに必要な情報理論最小値よりも指数関数的に小さい。
これは、学習可能性の推定に適していることが示されている基本的な学習アルゴリズムのごく小さなリストに追加される。
その結果、トップダウン決定木学習ヒューリスティックスのサンプル効率のよいミニバッチバージョンを設計・解析し、フルバッチ版と同じ保証を実現することを示す。
テストポイント $x^\star$ が与えられたとき、決定木仮説 $t$ のラベル $t(x^\star)$ が、多くのラベル付き例で計算できることを示し、$t$ を学ぶのに必要な数よりも指数関数的に小さい。
関連論文リスト
- Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。
16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
論文 参考訳(メタデータ) (2021-12-29T18:22:28Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳(メタデータ) (2021-10-27T10:45:21Z) - Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文 参考訳(メタデータ) (2021-09-01T22:12:47Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-01T14:10:38Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文 参考訳(メタデータ) (2021-06-02T01:37:52Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳(メタデータ) (2021-01-22T01:57:35Z) - Dive into Decision Trees and Forests: A Theoretical Demonstration [0.0]
決定木は"divide-and-conquer"の戦略を使用して、入力機能とラベル間の依存性に関する複雑な問題を小さなものに分割します。
近年, 計算広告, 推薦システム, 情報検索などの性能が大幅に向上している。
論文 参考訳(メタデータ) (2021-01-20T16:47:59Z) - Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
最適な$O(n ln n/epsilon2)$サンプルから,$n$-variable tree-structured Isingモデルが全変動距離$epsilon$の範囲内で計算効率良く学習可能であることを示す。
我々の保証は、Chow-Liuアルゴリズムの既知の結果に従わない。
論文 参考訳(メタデータ) (2020-10-28T10:17:48Z) - Recursive Top-Down Production for Sentence Generation with Latent Trees [77.56794870399288]
自然および合成言語に対する文脈自由文法の生成特性をモデル化する。
潜伏二分木構造にN$の葉を持つ動的プログラミングアルゴリズムを提案する。
また,Multi30kデータセットを用いたドイツ語と英語の翻訳実験を行った。
論文 参考訳(メタデータ) (2020-10-09T17:47:16Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。