論文の概要: Popular decision tree algorithms are provably noise tolerant

• arxiv url: http://arxiv.org/abs/2206.08899v1
• Date: Fri, 17 Jun 2022 17:15:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-20 16:15:30.328130
• Title: Popular decision tree algorithms are provably noise tolerant
• Title（参考訳）: 一般的な決定木アルゴリズムはノイズに耐性がある
• Authors: Guy Blanc, Jane Lange, Ali Malik, Li-Yang Tan
• Abstract要約: 我々は,古典的なID3,C4.5,CARTを含む不純物に基づく決定木学習アルゴリズムが,耐雑音性が高いことを証明した。 我々の研究は、これらの実践的な決定木アルゴリズムの実証的な成功を、しっかりとした理論的な足場に置きたいという、継続的な研究の行に繋がる。
• 参考スコア（独自算出の注目度）: 17.775217381568478
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guarantees hold under the strongest noise model of nasty noise, and we provide near-matching upper and lower bounds on the allowable noise rate. We further show that these algorithms, which are simple and have long been central to everyday machine learning, enjoy provable guarantees in the noisy setting that are unmatched by existing algorithms in the theoretical literature on decision tree learning. Taken together, our results add to an ongoing line of research that seeks to place the empirical success of these practical decision tree algorithms on firm theoretical footing.
• Abstract（参考訳）: ブースティングの枠組みを用いて,古典的なID3,C4.5,CARTを含む不純物に基づく決定木学習アルゴリズムが耐雑音性が高いことを示す。 提案手法は,高音質雑音の最大雑音モデルに準拠し,許容雑音率の上限値と下限値とをほぼ一致させる。 さらに、これらのアルゴリズムは、日常的な機械学習の中心であり、決定木学習に関する理論的文献において、既存のアルゴリズムに適合しないノイズのある環境で、証明可能な保証を享受していることを示す。 同時に,本研究は,これらの実践的決定木アルゴリズムの実証的な成功を確固とした理論的足場に据えるための一連の研究を継続する。

関連論文リスト

• Learning Constant-Depth Circuits in Malicious Noise Models [9.036777309376697]
  我々は、定数深度回路を学習するためのLinial, Mansour, Nisanの準ポリノミカル時間アルゴリズムを証明した。 ノイズ率に最も依存しうることを達成し、最も厳しいノイズモデルの実現に成功した。
  論文  参考訳（メタデータ） (2024-11-06T00:19:58Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Online Learning of Decision Trees with Thompson Sampling [12.403737756721467]
  決定木は解釈可能な機械学習のための顕著な予測モデルである。 オンライン環境で最適な決定木を生成できるモンテカルロ木探索アルゴリズムを考案した。
  論文  参考訳（メタデータ） (2024-04-09T15:53:02Z)
• A Robust Hypothesis Test for Tree Ensemble Pruning [2.4923006485141284]
  そこで我々は,勾配増進木アンサンブルの分割品質に関する理論的に正当化された新しい仮説を考案し,提示する。 本手法は, 一般的なペナルティ条件ではなく, サンプル損失の低減につながることを示す。 また,この手法にいくつかの革新的な拡張を加えて,様々な新しい木刈りアルゴリズムの扉を開く。
  論文  参考訳（メタデータ） (2023-01-24T16:31:49Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Learning with Group Noise [106.56780716961732]
  グループノイズを用いた学習のための新しいマックスマッチング手法を提案する。 いくつかの学習パラダイムの領域における実世界のデータセットのレンジのパフォーマンスは、Max-Matchingの有効性を示している。
  論文  参考訳（メタデータ） (2021-03-17T06:57:10Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• A Weighted Mutual k-Nearest Neighbour for Classification Mining [4.538870924201896]
  kNNは非常に効果的なインスタンスベースの学習方法であり、実装が容易です。 本稿では,データセットから疑似近傍の異常検出と除去を行う新しい学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-14T18:11:30Z)

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

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