Fugu-MT 論文翻訳(概要): On Computing Optimal Tree Ensembles

論文の概要: On Computing Optimal Tree Ensembles

arxiv url: http://arxiv.org/abs/2306.04423v2
Date: Tue, 24 Sep 2024 08:53:21 GMT
ステータス: 処理完了
システム内更新日: 2024-11-09 15:02:22.841194
Title: On Computing Optimal Tree Ensembles
Title（参考訳）: 最適木アンサンブルの計算について
Authors: Christian Komusiewicz, Pascal Kunz, Frank Sommer, Manuel Sorge,
Abstract要約: ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
参考スコア（独自算出の注目度）: 7.424944196676223
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: We obtain an algorithm that, given a training-data set and an size bound $S \in \mathbb{R}$, computes a tree ensemble of size at most $S$ that classifies the data correctly. The algorithm runs in $(4\delta D S)^S \cdot poly$-time, where $D$ the largest domain size, $\delta$ is the largest number of features in which two examples differ, $n$ the number of input examples, and $poly$ a polynomial of the input size. For decision trees, that is, ensembles of size 1, we obtain a running time of $(\delta D s)^s \cdot poly$, where $s$ is the size of the tree. To obtain these algorithms, we introduce the witness-tree technique, which seems promising for practical implementations. Secondly, we show that dynamic programming, which has been applied successfully to computing decision trees, may also be viable for tree ensembles, providing an $\ell^n \cdot poly$-time algorithm, where $\ell$ is the number of trees. 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つの新しいアルゴリズムと対応する下位境界を提供する。まず、決定木に対するトラクタビリティーの結果を大幅に改善することができる: トレーニングデータセットとサイズが有界な$S \in \mathbb{R}$を与えられた場合、最大で$S$でツリーアンサンブルを計算し、データを正しく分類するアルゴリズムを得る。このアルゴリズムは$(4\delta D S)^S \cdot poly$-timeで実行され、$D$は最大のドメインサイズ、$\delta$は2つの異なる例、$n$は入力例、$poly$は入力サイズの多項式である。決定木、すなわち、サイズ1のアンサンブルに対して、$(\delta D s)^s \cdot poly$ のランニング時間を得る。これらのアルゴリズムを実現するために,実践的な実装に期待できる目撃者木技術を導入する。第2に、決定木にうまく適用された動的プログラミングは、木アンサンブルにも有効である可能性を示し、$\ell^n \cdot poly$-timeアルゴリズムを提供し、$\ell$は木数である。最後に、決定木と木アンサンブルのトレーニングデータセットの分類に必要なカット数を比較し、アンサンブルが木数の増加に指数関数的に少ないカットを必要とすることを示す。

関連論文リスト

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)

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

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