論文の概要: Bayesian Decision Trees via Tractable Priors and Probabilistic
Context-Free Grammars
- arxiv url: http://arxiv.org/abs/2302.07407v1
- Date: Wed, 15 Feb 2023 00:17:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-16 16:10:33.937445
- Title: Bayesian Decision Trees via Tractable Priors and Probabilistic
Context-Free Grammars
- Title（参考訳）: 確率論的文脈自由文法によるベイズ決定木
- Authors: Colin Sullivan, Mo Tiwari, Sebastian Thrun, Chris Piech
- Abstract要約: ベイズ決定木を学習するための新しい基準を提案する。
BCART-PCFGは、データから得られる木々間の後部分布から決定木を効率的にサンプリングすることができる。
BCART-PCFGで採取した木は、優雅に構築された決定木に匹敵する性能を示した。
- 参考スコア（独自算出の注目度）: 7.259767735431625
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision Trees are some of the most popular machine learning models today due
to their out-of-the-box performance and interpretability. Often, Decision Trees
models are constructed greedily in a top-down fashion via heuristic search
criteria, such as Gini impurity or entropy. However, trees constructed in this
manner are sensitive to minor fluctuations in training data and are prone to
overfitting. In contrast, Bayesian approaches to tree construction formulate
the selection process as a posterior inference problem; such approaches are
more stable and provide greater theoretical guarantees. However, generating
Bayesian Decision Trees usually requires sampling from complex, multimodal
posterior distributions. Current Markov Chain Monte Carlo-based approaches for
sampling Bayesian Decision Trees are prone to mode collapse and long mixing
times, which makes them impractical. In this paper, we propose a new criterion
for training Bayesian Decision Trees. Our criterion gives rise to BCART-PCFG,
which can efficiently sample decision trees from a posterior distribution
across trees given the data and find the maximum a posteriori (MAP) tree.
Learning the posterior and training the sampler can be done in time that is
polynomial in the dataset size. Once the posterior has been learned, trees can
be sampled efficiently (linearly in the number of nodes). At the core of our
method is a reduction of sampling the posterior to sampling a derivation from a
probabilistic context-free grammar. We find that trees sampled via BCART-PCFG
perform comparable to or better than greedily-constructed Decision Trees in
classification accuracy on several datasets. Additionally, the trees sampled
via BCART-PCFG are significantly smaller -- sometimes by as much as 20x.
- Abstract（参考訳）: 決定木(Decision Tree)は、現在最も人気のある機械学習モデルのひとつだ。
決定木モデルは、しばしば、ジーニの不純物やエントロピーのようなヒューリスティックな探索基準によって、トップダウンの方法で優雅に構築される。
しかし、この方法で構築された木は、トレーニングデータの小さなゆらぎに敏感であり、過度に適合する傾向がある。
対照的に、木構築に対するベイズ的アプローチは、選択過程を後部推論問題として定式化し、そのようなアプローチはより安定であり、より理論的な保証を提供する。
しかし、ベイズ決定木の生成は通常、複雑で多モードな後続分布からのサンプリングを必要とする。
現在のマルコフ連鎖モンテカルロに基づくベイズ決定木サンプリングのアプローチは、モード崩壊と長い混合時間の傾向があり、現実的ではない。
本稿では,ベイズ決定木を訓練するための新しい基準を提案する。
我々の基準はBCART-PCFGを生じさせ、データから得られた木々の後方分布から決定木を効率よくサンプリングし、最大後葉(MAP)木を見つけることができる。
後方学習とサンプラーのトレーニングは、データセットサイズの多項式である時間内に行うことができる。
後輪が学習されると、木を効率的に(ノード数に線形に)サンプリングすることができる。
本手法の核となるのは,確率論的文脈自由文法からの導出をサンプリングするための後部サンプリングの削減である。
BCART-PCFGによってサンプリングされた木は、いくつかのデータセットの分類精度において、優雅に構築された決定木に匹敵する、あるいはそれより優れている。
さらに、BCART-PCFGで採取された木は、時には20倍も小さくなっている。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees [2.421336072915701]
本稿では,決定木誘導に対するベイズ的アプローチを提案する。
そこで我々は,MAPTreeとよばれるAND/OR探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-26T23:43:37Z) - Hierarchical Shrinkage: improving the accuracy and interpretability of
tree-based methods [10.289846887751079]
木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。
HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。
すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
論文 参考訳（メタデータ） (2022-02-02T02:43:23Z) - Probability Distribution on Rooted Trees [1.3955252961896318]
根付き木の階層的表現能力は、データ圧縮、画像処理、機械学習など、さまざまな領域の統計モデルを表現するために応用される。
これを解決するための統一的なアプローチはベイズ的アプローチであり、ルート木をランダム変数とみなし、選択されたモデルや新しいデータポイントの予測値に対して直接損失関数を仮定することができる。
本稿では,最大子ノード数と最大深さのみを固定したルート木に対して,一般化された確率分布を提案する。
論文 参考訳（メタデータ） (2022-01-24T05:13:58Z) - 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) - Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。
STDRの分割ステップは非ランダムです。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
論文 参考訳（メタデータ） (2021-02-26T02:47:42Z) - 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) - Growing Deep Forests Efficiently with Soft Routing and Learned
Connectivity [79.83903179393164]
この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。
我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。
MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
論文 参考訳（メタデータ） (2020-12-29T18:05:05Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳（メタデータ） (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。