論文の概要: 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$ を学ぶのに必要な数よりも指数関数的に小さい。

関連論文リスト

• Terminating Differentiable Tree Experts [77.2443883991608]
  本稿では,変圧器と表現生成器の組み合わせを用いて木操作を学習するニューラルシンボリック微分木機械を提案する。 まず、専門家の混在を導入することで、各ステップで使用される一連の異なるトランスフォーマーレイヤを取り除きます。 また,モデルが自動生成するステップ数を選択するための新しい終端アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-02T08:45:38Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Learning accurate and interpretable decision trees [27.203303726977616]
  我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。 本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。 また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• 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)
• 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)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

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