論文の概要: Online Learning of Decision Trees with Thompson Sampling

• arxiv url: http://arxiv.org/abs/2404.06403v1
• Date: Tue, 9 Apr 2024 15:53:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 14:11:18.446058
• Title: Online Learning of Decision Trees with Thompson Sampling
• Title（参考訳）: トンプソンサンプリングによる決定木のオンライン学習
• Authors: Ayman Chaouki, Jesse Read, Albert Bifet,
• Abstract要約: 決定木は解釈可能な機械学習のための顕著な予測モデルである。 オンライン環境で最適な決定木を生成できるモンテカルロ木探索アルゴリズムを考案した。
• 参考スコア（独自算出の注目度）: 12.403737756721467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision Trees are prominent prediction models for interpretable Machine Learning. They have been thoroughly researched, mostly in the batch setting with a fixed labelled dataset, leading to popular algorithms such as C4.5, ID3 and CART. Unfortunately, these methods are of heuristic nature, they rely on greedy splits offering no guarantees of global optimality and often leading to unnecessarily complex and hard-to-interpret Decision Trees. Recent breakthroughs addressed this suboptimality issue in the batch setting, but no such work has considered the online setting with data arriving in a stream. To this end, we devise a new Monte Carlo Tree Search algorithm, Thompson Sampling Decision Trees (TSDT), able to produce optimal Decision Trees in an online setting. We analyse our algorithm and prove its almost sure convergence to the optimal tree. Furthermore, we conduct extensive experiments to validate our findings empirically. The proposed TSDT outperforms existing algorithms on several benchmarks, all while presenting the practical advantage of being tailored to the online setting.
• Abstract（参考訳）: 決定木は解釈可能な機械学習のための顕著な予測モデルである。 C4.5、ID3、CARTといった一般的なアルゴリズムに繋がる固定ラベル付きデータセットのバッチ設定で、これらは徹底的に研究されている。 残念なことに、これらの手法はヒューリスティックな性質を持ち、大域的最適性の保証のない欲望分割に依存しており、しばしば必要以上に複雑で解釈が難しい決定木に繋がる。 最近のブレークスルーは、バッチ設定におけるこの亜最適問題に対処しているが、そのような作業は、データがストリームに到着するオンライン設定を考慮していない。 そこで我々は,モンテカルロ木探索アルゴリズムであるトンプソンサンプリング決定木(TSDT)を考案し,オンライン環境で最適な決定木を生成する。 我々はアルゴリズムを解析し、そのほぼ確実に最適な木への収束を証明する。 さらに,本研究の成果を実証的に検証するための広範囲な実験を行った。 提案されたTSDTは、いくつかのベンチマークで既存のアルゴリズムよりも優れており、オンライン設定に合わせて調整されるという現実的な利点を示している。

関連論文リスト

• Learning Deep Tree-based Retriever for Efficient Recommendation: Theory and Method [76.31185707649227]
  効率的なレコメンデーションのために,Deep Tree-based Retriever (DTR)を提案する。 DTRは、トレーニングタスクを、同じレベルでツリーノード上のソフトマックスベースのマルチクラス分類としてフレーム化している。 非リーフノードのラベル付けによって引き起こされる準最適性を緩和するため、損失関数の補正法を提案する。
  論文  参考訳（メタデータ） (2024-08-21T05:09:53Z)
• 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)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。 HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。 すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
  論文  参考訳（メタデータ） (2022-02-02T02:43:23Z)
• Optimal randomized classification trees [0.0]
  分類と回帰木(英: Classification and Regression Trees、CART)は、現代の統計学と機械学習における既成の技術である。 CARTはgreedyプロシージャによって構築され、分割予測変数と関連するしきい値を逐次決定する。 この強欲なアプローチは、木を非常に高速に木に分類するが、その性質上、それらの分類精度は他の最先端の手順と競合しないかもしれない。
  論文  参考訳（メタデータ） (2021-10-19T11:41:12Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Optimal Survival Trees [2.7910505923792637]
  混合整数最適化(MIO)と局所探索技術を利用して,グローバルに最適化された生存木モデルを生成する,新しい生存木アルゴリズムを提案する。 本研究では,既存のサバイバルツリー法,特に大規模データセットの精度の向上を実証する。
  論文  参考訳（メタデータ） (2020-12-08T09:00:57Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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