論文の概要: Generalization Properties of Decision Trees on Real-valued and
Categorical Features
- arxiv url: http://arxiv.org/abs/2210.10781v1
- Date: Tue, 18 Oct 2022 21:50:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 13:47:02.456037
- Title: Generalization Properties of Decision Trees on Real-valued and
Categorical Features
- Title（参考訳）: 実数値およびカテゴリー的特徴に基づく決定木の一般化特性
- Authors: Jean-Samuel Leboeuf, Fr\'ed\'eric LeBlanc and Mario Marchand
- Abstract要約: データ分割の観点から二分決定木を再検討する。
我々は3種類の特徴を考察する: 実数値、分類的順序、分類的名目で、それぞれ異なる分割規則を持つ。
- 参考スコア（独自算出の注目度）: 2.370481325034443
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We revisit binary decision trees 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. We consider three types of features:
real-valued, categorical ordinal and categorical nominal, with different split
rules for each. For each feature type, we upper bound the partitioning function
of the class of decision stumps before extending the bounds to the class of
general decision tree (of any fixed structure) using a recursive approach.
Using these new results, we are able to find the exact VC dimension of decision
stumps on examples of $\ell$ real-valued features, which is given by the
largest integer $d$ such that $2\ell \ge \binom{d}{\lfloor\frac{d}{2}\rfloor}$.
Furthermore, we show that the VC dimension of a binary tree structure with
$L_T$ leaves on examples of $\ell$ real-valued features is in $O(L_T
\log(L_T\ell))$. Finally, we elaborate a pruning algorithm based on these
results that performs better than the cost-complexity and reduced-error pruning
algorithms on a number of data sets, with the advantage that no
cross-validation is required.
- Abstract（参考訳）: データ分割の観点から二分決定木を再検討する。
分割関数の概念を導入し,成長関数やvc次元と関連づける。
我々は3種類の特徴を考察する: 実数値、分類的順序、分類的名目で、それぞれ異なる分割規則を持つ。
各特徴型について、再帰的アプローチを用いて境界を(任意の固定構造の)一般決定木のクラスに拡張する前に、決定切り株のクラス分割関数を上界とする。
これらの新しい結果から、$$\ell$実数値関数の例でVC次元の正確な決定切り札を見つけることができ、これは、$2\ell \ge \binom{d}{\lfloor\frac{d}{2}\rfloor}$であるような最大整数$d$によって与えられる。
さらに、$L_T$ を持つ二分木構造の VC 次元が $\ell$ 実数値関数の例に残ることを示し、$O(L_T \log(L_T\ell))$ である。
最後に,これらの結果に基づくプルーニングアルゴリズムを詳述し,クロスバリデーションを必要としないという利点を生かして,コスト複雑度や誤差低減プルーニングアルゴリズムよりも優れた性能を示す。
関連論文リスト
- Polynomial Width is Sufficient for Set Representation with
High-dimensional Features [69.65698500919869]
DeepSetsは集合表現のための最も広く使われているニューラルネットワークアーキテクチャである。
a) 線形 + パワーアクティベーション (LP) と (b) 線形 + 指数的アクティベーション (LE) の2つの集合要素埋め込み層を示す。
論文 参考訳（メタデータ） (2023-07-08T16:00:59Z) - On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - On marginal feature attributions of tree-based models [0.11184789007828977]
辺縁的なシャプリー、オーウェンまたはバンジャフの値など、辺縁的な期待に基づく局所的な特徴属性を用いることができる。
パス依存(path-dependent)のTreeSHAPが特徴のランク付けを行うのと全く同じ関数を計算する2つの(統計的に類似した)決定木を提示する。
我々は、CataBoostモデルの余剰Shapley(およびBanzhafとOwen)値についてのみ、複雑さを改善し、内部モデルパラメータの観点からのみ、明示的な式を導出するために対称性を利用する。
論文 参考訳（メタデータ） (2023-02-16T17:18:03Z) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Rethinking Learnable Tree Filter for Generic Feature Transform [71.77463476808585]
Learnable Tree Filterはセマンティックセグメンテーションのためのモデル構造保存関係に対する顕著なアプローチを示す。
幾何学的制約を緩和するために,マルコフ確率場として再構成して解析を行い,学習可能な不定項を導入する。
セマンティックセグメンテーションでは、ベルとホイッスルなしでCityscapesベンチマークでトップパフォーマンス(82.1% mIoU)を達成しています。
論文 参考訳（メタデータ） (2020-12-07T07:16:47Z) - Measure Inducing Classification and Regression Trees for Functional Data [0.0]
機能的データ分析の文脈における分類と回帰問題に対する木に基づくアルゴリズムを提案する。
これは、制約付き凸最適化により重み付き汎函数 L2$ 空間を学習することで達成される。
論文 参考訳（メタデータ） (2020-10-30T18:49:53Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - Universal guarantees for decision tree induction via a higher-order
splitting criterion [16.832966312395126]
本アルゴリズムは,全対象関数に対して,一様分布に対して, -1,1n から -1,1$ の証明可能な保証を実現する。
我々の拡張の要点は、その属性の$f$と小さなサブセットの相関を考慮に入れた、新しい分割基準である。
我々のアルゴリズムは以下の保証を満たす: すべての対象関数 $f : -1,1n to -1,1$, sizes $sin mathbbN$, error parameters $epsilon$ に対して、決定を構成する。
論文 参考訳（メタデータ） (2020-10-16T21:20:45Z) - Decision trees as partitioning machines to characterize their
generalization properties [2.370481325034443]
データの分割の観点から、実値の特徴について二分決定木を再検討する。
内部ノードが$N$である二分木構造のVC次元が$N log(Nell)$であることを示す。
我々は,これらの結果に基づいて,多数のデータセット上でのCARTアルゴリズムよりも優れたプルーニングアルゴリズムを詳述する。
論文 参考訳（メタデータ） (2020-10-14T19:25:58Z) - A deep network construction that adapts to intrinsic dimensionality
beyond the domain [79.23797234241471]
本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。
例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
論文 参考訳（メタデータ） (2020-08-06T09:50:29Z) - Infinite Feature Selection: A Graph-based Feature Filtering Approach [78.63188057505012]
グラフ内の経路として特徴のサブセットを考慮したフィルタリング機能選択フレームワークを提案する。
無限に進むことで、選択プロセスの計算複雑性を制限できる。
Inf-FSはほとんどどんな状況でも、つまり、保持するフィーチャの数が優先順位に固定されているときに、より良く振る舞うことを示す。
論文 参考訳（メタデータ） (2020-06-15T07:20:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。