論文の概要: On Computing Optimal Tree Ensembles
- arxiv url: http://arxiv.org/abs/2306.04423v1
- Date: Wed, 7 Jun 2023 13:30:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-08 14:21:00.689318
- Title: On Computing Optimal Tree Ensembles
- Title(参考訳): 最適ツリーアンサンブルの計算について
- Authors: Christian Komusiewicz, Pascal Kunz, Frank Sommer and Manuel Sorge
- Abstract要約: ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
- 参考スコア(独自算出の注目度): 8.941441654913644
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Random forests and, more generally, (decision\nobreakdash-)tree ensembles are
widely used methods for classification and regression. Recent algorithmic
advances allow to compute decision trees that are optimal for various measures
such as their size or depth. We are not aware of such research for tree
ensembles and aim to contribute to this area. Mainly, we provide two novel
algorithms and corresponding lower bounds. First, we are able to carry over and
substantially improve on tractability results for decision trees, obtaining a
$(6\delta D S)^S \cdot poly$-time algorithm, where $S$ is the number of cuts in
the tree ensemble, $D$ the largest domain size, and $\delta$ is the largest
number of features in which two examples differ. To achieve this, we introduce
the witness-tree technique which also seems promising for practice. Second, we
show that dynamic programming, which has been successful for decision trees,
may also be viable for tree ensembles, providing an $\ell^n \cdot poly$-time
algorithm, where $\ell$ is the number of trees and $n$ the number of examples.
Finally, we compare the number of cuts necessary to classify training data sets
for decision trees and tree ensembles, showing that ensembles may need
exponentially fewer cuts for increasing number of trees.
- Abstract(参考訳): ランダム林やより一般的には(決定的)ノブレイクダッシュ-(ツリーアンサンブルは分類と回帰のために広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
我々は、このような樹木アンサンブルの研究を意識しておらず、この領域に貢献することを目指している。
主に2つの新しいアルゴリズムとそれに対応する下限を提供する。
まず、決定木に対するトラクタビリティの結果を大幅に改善し、$(6\delta D S)^S \cdot poly$-timeアルゴリズムを得ることができ、ここでは$S$はツリーアンサンブルのカット数、$D$は最大のドメインサイズ、$\delta$は2つの例が異なる最大の特徴数である。
これを実現するために,実演にも有望と思われる証人ツリー手法を紹介する。
第2に、決定木で成功した動的プログラミングは、ツリーアンサンブルでも実行可能な可能性を示し、$\ell^n \cdot poly$-timeアルゴリズムを提供し、$\ell$は木の数、$n$は例の数である。
最後に、決定木と木アンサンブルのトレーニングデータセットの分類に必要なカット数を比較し、アンサンブルが木数を増やすために指数関数的に少ないカットを必要とすることを示す。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [80.49817544396379]
本稿では,従来のアルゴリズムから出力されたフィルタを用いてトランスフォーマーモデルを用いて,分類のための強力な決定木を生成するメタトレーについて紹介する。
次にMetaTreeをトレーニングして、強力な一般化パフォーマンスを実現するツリーを生成します。
論文 参考訳(メタデータ) (2024-02-06T07:40:53Z) - End-to-end Feature Selection Approach for Learning Skinny Trees [15.047418632192754]
複合機能選択とツリーアンサンブル学習は難しい課題である。一般的な木アンサンブルツールキット(グラディエントツリーやランダムフォレストなど)は、誤解を招くことが知られている特徴量に基づいた特徴選択をサポートし、パフォーマンスを著しく損なう可能性がある。
本研究では,木組におけるアンサンブル選択のためのスキニーツリーツールキットを提案し,特徴選択とツリーアンサンブル学習を同時に行う。
論文 参考訳(メタデータ) (2023-10-28T00:15:10Z) - MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees [2.421336072915701]
本稿では,決定木誘導に対するベイズ的アプローチを提案する。
そこで我々は,MAPTreeとよばれるAND/OR探索アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-26T23:43:37Z) - New Linear-time Algorithm for SubTree Kernel Computation based on
Root-Weighted Tree Automata [0.0]
本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。
提案アルゴリズムの主な考え方は、DAGの削減とノードのソートを置き換えることである。
我々のアプローチには3つの大きな利点がある:それは出力に敏感であり、木の種類(順序のない木と順序のない木)に敏感であり、インクリメンタルな木カーネルベースの学習手法によく適応している。
論文 参考訳(メタデータ) (2023-02-02T13:37:48Z) - SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。
Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
論文 参考訳(メタデータ) (2022-09-28T09:55:47Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳(メタデータ) (2022-05-25T09:57:28Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳(メタデータ) (2021-04-14T18:15:27Z) - 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) - Decision trees as partitioning machines to characterize their
generalization properties [2.370481325034443]
データの分割の観点から、実値の特徴について二分決定木を再検討する。
内部ノードが$N$である二分木構造のVC次元が$N log(Nell)$であることを示す。
我々は,これらの結果に基づいて,多数のデータセット上でのCARTアルゴリズムよりも優れたプルーニングアルゴリズムを詳述する。
論文 参考訳(メタデータ) (2020-10-14T19:25:58Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。