論文の概要: Decision trees as partitioning machines to characterize their
generalization properties
- arxiv url: http://arxiv.org/abs/2010.07374v1
- Date: Wed, 14 Oct 2020 19:25:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 13:54:37.181062
- Title: Decision trees as partitioning machines to characterize their
generalization properties
- Title（参考訳）: 分割機械としての決定木とその一般化特性
- Authors: Jean-Samuel Leboeuf, Fr\'ed\'eric LeBlanc and Mario Marchand
- Abstract要約: データの分割の観点から、実値の特徴について二分決定木を再検討する。
内部ノードが$N$である二分木構造のVC次元が$N log(Nell)$であることを示す。
我々は,これらの結果に基づいて,多数のデータセット上でのCARTアルゴリズムよりも優れたプルーニングアルゴリズムを詳述する。
- 参考スコア（独自算出の注目度）: 2.370481325034443
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decision trees are popular machine learning models that are simple to build
and easy to interpret. Even though algorithms to learn decision trees date back
to almost 50 years, key properties affecting their generalization error are
still weakly bounded. Hence, we revisit binary decision trees on real-valued
features from the perspective of partitions of the data. We introduce the
notion of partitioning function, and we relate it to the growth function and to
the VC dimension. Using this new concept, we are able to find the exact VC
dimension of decision stumps, which is given by the largest integer $d$ such
that $2\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$, where $\ell$
is the number of real-valued features. We provide a recursive expression to
bound the partitioning functions, resulting in a upper bound on the growth
function of any decision tree structure. This allows us to show that the VC
dimension of a binary tree structure with $N$ internal nodes is of order $N
\log(N\ell)$. Finally, we elaborate a pruning algorithm based on these results
that performs better than the CART algorithm on a number of datasets, with the
advantage that no cross-validation is required.
- Abstract（参考訳）: 決定木は、構築が簡単で解釈が容易な一般的な機械学習モデルである。
決定木を学ぶアルゴリズムは50年近く遡るが、その一般化エラーに影響する重要な特性は依然として弱い境界である。
したがって、データの分割の観点から、実数値特徴のバイナリ決定木を再検討する。
分割関数の概念を導入し,成長関数やvc次元と関連づける。
この新しい概念を用いることで、決定切り株のVC次元を正確に見つけることができ、これは最大整数$d$で与えられるもので、$\ell \ge \binom{d}{\left\lfloor\frac{d}{2}\right\rfloor}$である。
分割関数のバウンドに対する再帰的表現を提供し,任意の決定木構造の成長関数の上界を導出する。
これにより、$N$内部ノードを持つ二分木構造のVC次元が$N \log(N\ell)$であることを示すことができる。
最後に,これらの結果に基づくプルーニングアルゴリズムを詳述し,クロスバリデーションを必要とせず,多数のデータセット上でカートアルゴリズムよりも優れた性能を示す。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。
我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
論文 参考訳（メタデータ） (2024-02-06T07:40:53Z) - On the Trade-off between the Number of Nodes and the Number of Trees in
a Random Forest [8.340919965932443]
我々は、$n$変数の多数関数は、$n-T$が定数であれば、それぞれ大きさで$T$$$(n$)決定ツリーのバッグで表現できることを示した。
k$-out-of-n$関数に関する関連する結果も提示される。
論文 参考訳（メタデータ） (2023-12-16T02:09:34Z) - On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - Generalization Properties of Decision Trees on Real-valued and
Categorical Features [2.370481325034443]
データ分割の観点から二分決定木を再検討する。
我々は3種類の特徴を考察する: 実数値、分類的順序、分類的名目で、それぞれ異なる分割規則を持つ。
論文 参考訳（メタデータ） (2022-10-18T21:50:24Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - Tree in Tree: from Decision Trees to Decision Graphs [2.2336243882030025]
Tree in Tree decision graph (TnT)は、従来の決定木をより汎用的で強力な非巡回グラフに拡張するフレームワークである。
提案するモデルは,広く用いられている決定木に代わる,新しい,より効率的かつ正確な代替手段である。
論文 参考訳（メタデータ） (2021-10-01T13:20:05Z) - Properly learning decision trees in almost polynomial time [25.763690981846125]
我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。
我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。
すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
論文 参考訳（メタデータ） (2021-09-01T22:12:47Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。