論文の概要: Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees
- arxiv url: http://arxiv.org/abs/2302.03994v2
- Date: Fri, 10 Feb 2023 09:14:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 12:02:28.152159
- Title: Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees
- Title（参考訳）: 最悪の更新時間保証を備えた完全動的近似決定木
- Authors: Marco Bressan and Mauro Sozio
- Abstract要約: ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 3.5509551353363644
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give the first algorithm that maintains an approximate decision tree over
an arbitrary sequence of insertions and deletions of labeled examples, with
strong guarantees on the worst-case running time per update request. For
instance, we show how to maintain a decision tree where every vertex has Gini
gain within an additive $\alpha$ of the optimum by performing
$O\Big(\frac{d\,(\log n)^4}{\alpha^3}\Big)$ elementary operations per update,
where $d$ is the number of features and $n$ the maximum size of the active set
(the net result of the update requests). We give similar bounds for the
information gain and the variance gain. In fact, all these bounds are
corollaries of a more general result, stated in terms of decision rules --
functions that, given a set $S$ of labeled examples, decide whether to split
$S$ or predict a label. Decision rules give a unified view of greedy decision
tree algorithms regardless of the example and label domains, and lead to a
general notion of $\epsilon$-approximate decision trees that, for natural
decision rules such as those used by ID3 or C4.5, implies the gain
approximation guarantees above. The heart of our work provides a deterministic
algorithm that, given any decision rule and any $\epsilon > 0$, maintains an
$\epsilon$-approximate tree using $O\!\left(\frac{d\, f(n)}{n}
\operatorname{poly}\frac{h}{\epsilon}\right)$ operations per update, where
$f(n)$ is the complexity of evaluating the rule over a set of $n$ examples and
$h$ is the maximum height of the maintained tree.
- Abstract（参考訳）: ラベル付き例の挿入と削除の任意のシーケンス上で近似決定木を維持する最初のアルゴリズムを与え,更新要求毎の最悪のケースの実行時間に対して強い保証を与える。
例えば、すべての頂点がginiゲインを持つ決定木を最適値の付加値$\alpha$で維持する方法を示す。$o\big(\frac{d\,(\log n)^4}{\alpha^3}\big)$ 更新ごとに基本操作を実行し、$d$ は特徴数、$n$ はアクティブセットの最大サイズ(更新要求のネット結果)である。
我々は、情報ゲインと分散ゲインに同様の境界を与える。
実際、これらの境界はすべてより一般的な結果の系であり、決定規則の項で述べられている - ラベル付き例のセット$S$を与えられた関数は、$S$を分割するかラベルを予測するかを決定する。
決定規則は、例やラベル領域に関係なく、欲張りな決定木アルゴリズムの統一的なビューを与え、また、id3やc4.5で使われるような自然決定木に対して、上記のゲイン近似の保証を意味する$\epsilon$-approximate 決定木という一般的な概念に繋がる。
私たちの研究の核心は決定論的アルゴリズムを提供し、任意の決定規則と$\epsilon > 0$が与えられた場合、$O\!
\left(\frac{d\, f(n)}{n} \operatorname{poly}\frac{h}{\epsilon}\right)$ operations per update ここで$f(n)$は$n$の例のセットに対するルールの評価の複雑さであり、$h$は維持ツリーの最大高さである。
関連論文リスト
- Tight Bounds for $\gamma$-Regret via the Decision-Estimation Coefficient [88.86699022151598]
任意の構造化バンディット問題に対する$gamma$-regretの統計的特徴を与える。
この$gamma$-regretは、関数クラス$mathcalF$上の構造化バンディット問題に現れる。
論文 参考訳（メタデータ） (2023-03-06T17:54:33Z) - Fully-Dynamic Decision Trees [3.0058005235097114]
ラベル付き例の挿入と削除の任意のシーケンス上で決定木を維持するための,最初の完全動的アルゴリズムを開発した。
実数値機能の場合、このアルゴリズムは挿入/削除毎に$Obig(fracd log3 nepsilon2big)$.amortized run timeを持つ。
同様の保証を持つアルゴリズムは、amortized run time $Omega(d)$と space $tildeOmega (n d)$を使用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:19Z) - Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。
その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。
学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
論文 参考訳（メタデータ） (2022-10-12T16:25:48Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - 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) - 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) - 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) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。
すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。
アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文 参考訳（メタデータ） (2020-06-01T06:44:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。