論文の概要: On the Trade-off between the Number of Nodes and the Number of Trees in
a Random Forest
- arxiv url: http://arxiv.org/abs/2312.11540v1
- Date: Sat, 16 Dec 2023 02:09:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-20 18:46:59.199815
- Title: On the Trade-off between the Number of Nodes and the Number of Trees in
a Random Forest
- Title（参考訳）: ランダム林におけるノード数と樹木数とのトレードオフについて
- Authors: Tatsuya Akutsu, Avraham A. Melkman, Atsuhiro Takasu
- Abstract要約: 我々は、$n$変数の多数関数は、$n-T$が定数であれば、それぞれ大きさで$T$$$(n$)決定ツリーのバッグで表現できることを示した。
k$-out-of-n$関数に関する関連する結果も提示される。
- 参考スコア（独自算出の注目度）: 8.340919965932443
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we focus on the prediction phase of a random forest and study
the problem of representing a bag of decision trees using a smaller bag of
decision trees, where we only consider binary decision problems on the binary
domain and simple decision trees in which an internal node is limited to
querying the Boolean value of a single variable. As a main result, we show that
the majority function of $n$ variables can be represented by a bag of $T$ ($<
n$) decision trees each with polynomial size if $n-T$ is a constant, where $n$
and $T$ must be odd (in order to avoid the tie break). We also show that a bag
of $n$ decision trees can be represented by a bag of $T$ decision trees each
with polynomial size if $n-T$ is a constant and a small classification error is
allowed. A related result on the $k$-out-of-$n$ functions is presented too.
- Abstract（参考訳）: 本稿では,ランダム林の予測フェーズに着目し,二分領域上の二分決定問題と,内部ノードが1つの変数のブール値のクエリに制限される単純な決定木についてのみ考慮した,より小さな決定木を用いて決定木の袋を表現する問題を考察する。
主な結果として、$n$変数の多数関数は、多項式サイズの$T$$$<n$)決定ツリーのバッグで表され、$n-T$が定数であれば、$n$と$T$は奇数でなければならない(タイブレークを避けるために)。
また、n$決定木の袋は、n-t$が定数であり、小さな分類誤差が許容される場合に多項式サイズでそれぞれ$t$決定ツリーの袋で表現できることを示した。
k$-out-of-n$関数に関する関連する結果も提示される。
関連論文リスト
- Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文 参考訳（メタデータ） (2022-10-12T16:25:48Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - On Computing Probabilistic Explanations for Decision Trees [4.406418914680962]
十分な理由は、決定木を$T$とインスタンスを$x$とすると、決定を$T(x)$とします。
本稿では,決定木に対する$delta$sufficient-reasonsの計算複雑性について検討する。
決定木の構造的制約を識別し,SATソルバがこれらの問題に実際にどのように対処できるかを示す。
論文 参考訳（メタデータ） (2022-06-30T21:58:31Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - On Learning and Testing Decision Tree [0.22843885788439797]
我々は$phi(s,1/epsilon)=2O(log3s)/epsilon3)$を達成する新しいアルゴリズムを与える。
また,Deep-d$決定木の試験可能性について検討し,分布自由なテスターを与える。
論文 参考訳（メタデータ） (2021-08-10T11:04:06Z) - 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) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。
我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文 参考訳（メタデータ） (2020-08-20T03:42:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。