論文の概要: 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$は例の数である。
最後に、決定木と木アンサンブルのトレーニングデータセットの分類に必要なカット数を比較し、アンサンブルが木数を増やすために指数関数的に少ないカットを必要とすることを示す。
関連論文リスト
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳（メタデータ） (2024-06-29T05:14:04Z) - Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Harnessing the Power of Choices in Decision Tree Learning [20.08390529995706]
本稿では,ID3,C4.5,CARTなどの決定木学習アルゴリズムを簡易に一般化し,実証的に成功した決定木学習アルゴリズムを提案する。
私たちのアルゴリズムであるTop-$k$は、$k$のベスト属性を単一のベスト属性ではなく、可能な分割として考慮しています。
広範な実験を通して、Top-k$は、決定木学習の2つの主要なアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2023-10-02T18:45:46Z) - 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) - Testing and reconstruction via decision trees [19.304587350775385]
決定木に対する部分線形および局所計算アルゴリズムを,テストと再構成に焦点をあてて検討した。
mathrmpoly(log s, 1/varepsilon)cdot nlog n$ time で実行するテスターは、未知の関数への$mathrmpoly(log s, 1/varepsilon)cdot n$ queryを作る。
論文 参考訳（メタデータ） (2020-12-16T04:18:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。