論文の概要: Fully-Dynamic Decision Trees

• arxiv url: http://arxiv.org/abs/2212.00778v1
• Date: Thu, 1 Dec 2022 18:58:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-02 15:29:14.363832
• Title: Fully-Dynamic Decision Trees
• Title（参考訳）: 完全動的決定木
• Authors: Marco Bressan and Gabriel Damay and Mauro Sozio
• Abstract要約: ラベル付き例の挿入と削除の任意のシーケンス上で決定木を維持するための,最初の完全動的アルゴリズムを開発した。 実数値機能の場合、このアルゴリズムは挿入/削除毎に$Obig(fracd log3 nepsilon2big)$.amortized run timeを持つ。 同様の保証を持つアルゴリズムは、amortized run time $Omega(d)$と space $tildeOmega (n d)$を使用する。
• 参考スコア（独自算出の注目度）: 3.0058005235097114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop the first fully dynamic algorithm that maintains a decision tree over an arbitrary sequence of insertions and deletions of labeled examples. Given $\epsilon > 0$ our algorithm guarantees that, at every point in time, every node of the decision tree uses a split with Gini gain within an additive $\epsilon$ of the optimum. For real-valued features the algorithm has an amortized running time per insertion/deletion of $O\big(\frac{d \log^3 n}{\epsilon^2}\big)$, which improves to $O\big(\frac{d \log^2 n}{\epsilon}\big)$ for binary or categorical features, while it uses space $O(n d)$, where $n$ is the maximum number of examples at any point in time and $d$ is the number of features. Our algorithm is nearly optimal, as we show that any algorithm with similar guarantees uses amortized running time $\Omega(d)$ and space $\tilde{\Omega} (n d)$. We complement our theoretical results with an extensive experimental evaluation on real-world data, showing the effectiveness of our algorithm.
• Abstract（参考訳）: ラベル付き例の挿入と削除の任意の列上で決定木を維持する最初の完全動的アルゴリズムを開発した。 与えられた$\epsilon > 0$のアルゴリズムは、すべての時点において、決定ツリーのすべてのノードが、最適値の加法$\epsilon$内のGiniゲインの分割を使用することを保証します。 実数値の関数に対しては、アルゴリズムは$o\big(\frac{d \log^3 n}{\epsilon^2}\big)$の挿入/削除毎にamortized実行時間を持ち、バイナリまたはカテゴリの特徴に対して$o\big(\frac{d \log^2 n}{\epsilon}\big)$になるが、スペース$o(n d)$を使用する。 我々のアルゴリズムはほぼ最適であり、同様の保証を持つ任意のアルゴリズムは、アモルティックランニングタイム$\Omega(d)$とスペース$\tilde{\Omega} (n d)$を使用する。 本研究では,実世界データに対する広範囲な実験評価を行い,アルゴリズムの有効性を示す。

関連論文リスト

• Mini-Batch Kernel $k$-means [4.604003661048267]
  私たちのアルゴリズムの1つのイテレーションは$widetildeO(kb2)$時間であり、フルバッチカーネルの$k$-meansに必要な$O(n2)$時間よりもはるかに高速です。 実験により,本アルゴリズムは品質の低下を最小限に抑えた10-100倍の高速化を実現していることがわかった。
  論文  参考訳（メタデータ） (2024-10-08T10:59:14Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• 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)
• 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)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)

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

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