論文の概要: Approximating splits for decision trees quickly in sparse data streams

• arxiv url: http://arxiv.org/abs/2601.12525v1
• Date: Sun, 18 Jan 2026 18:19:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:22.664423
• Title: Approximating splits for decision trees quickly in sparse data streams
• Title（参考訳）: スパースデータストリームにおける決定木に対する近似分割
• Authors: Nikolaj Tatti,
• Abstract要約: スパースバイナリ機能とバイナリクラスを扱う場合、最適な分割の検索を高速化する方法に焦点をあてる。 我々の実験では、ほぼ最適で、ベースラインよりも高速で、理論近似の保証を上回ります。
• 参考スコア（独自算出の注目度）: 6.184770559759073
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decision trees are one of the most popular classifiers in the machine learning literature. While the most common decision tree learning algorithms treat data as a batch, numerous algorithms have been proposed to construct decision trees from a data stream. A standard training strategy involves augmenting the current tree by changing a leaf node into a split. Here we typically maintain counters in each leaf which allow us to determine the optimal split, and whether the split should be done. In this paper we focus on how to speed up the search for the optimal split when dealing with sparse binary features and a binary class. We focus on finding splits that have the approximately optimal information gain or Gini index. In both cases finding the optimal split can be done in $O(d)$ time, where $d$ is the number of features. We propose an algorithm that yields $(1 + α)$ approximation when using conditional entropy in amortized $O(α^{-1}(1 + m\log d) \log \log n)$ time, where $m$ is the number of 1s in a data point, and $n$ is the number of data points. Similarly, for Gini index, we achieve $(1 + α)$ approximation in amortized $O(α^{-1} + m \log d)$ time. Our approach is beneficial for sparse data where $m \ll d$. In our experiments we find almost-optimal splits efficiently, faster than the baseline, overperforming the theoretical approximation guarantees.
• Abstract（参考訳）: 決定木(Decision Tree)は、機械学習文学において最も人気のある分類法の一つである。 最も一般的な決定木学習アルゴリズムはデータをバッチとして扱うが、データストリームから決定木を構築するために多くのアルゴリズムが提案されている。 標準的なトレーニング戦略では、リーフノードを分割にすることで、現在のツリーを拡大する。 ここでは通常、各葉にカウンタを保持して、最適な分割を判断し、分割を行うかどうかを判断します。 本稿では,スパースなバイナリ機能とバイナリクラスを扱う場合の最適分割探索の高速化に焦点をあてる。 我々は、ほぼ最適な情報ゲインまたはGiniインデックスを持つ分割を見つけることに重点を置いている。 どちらの場合も最適な分割は$O(d)$ timeで行うことができ、$d$は機能の数である。 我々は,不動化$O(α^{-1}(1 + m\log d) \log \log n)$ timeにおいて条件付きエントロピーを使用する場合,$(1 + α)$近似を求めるアルゴリズムを提案する。 同様に、Gini 指数に対して、amortized $O(α^{-1} + m \log d)$ time で $(1 + α)$ approximation を達成する。 我々のアプローチは、$m \ll d$のスパースデータに対して有益である。 我々の実験では、ほぼ最適分裂はベースラインよりも効率的に、理論近似の保証を上回ります。

関連論文リスト

• Finite Sample Complexity Analysis of Binary Segmentation [2.474754293747645]
  与えられた有限$N$,$K$,および最小セグメント長パラメータに対する二分分割の時間と空間の複雑さを解析するための新しい手法について述べる。 実データについて実証的な分析を行い、二分法は実際は最適速度に近いことが多いことを示唆する。
  論文  参考訳（メタデータ） (2024-10-11T09:26:29Z)
• Differentially Private Kernel Density Estimation [11.526850085349155]
  我々は、カーネル密度推定(KDE)のための洗練された微分プライベート(DP)データ構造を導入する。 類似関数 $f$ とプライベートデータセット $X サブセット mathbbRd$ が与えられた場合、我々のゴールは、任意のクエリ $yinmathbbRd$ に対して、X f(x, y)$ の $sum_x を微分プライベートな方法で近似するように$X$ を前処理することである。
  論文  参考訳（メタデータ） (2024-09-03T08:01:19Z)
• 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)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• 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)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Systematically improving existing k-means initialization algorithms at nearly no cost, by pairwise-nearest-neighbor smoothing [1.2570180539670577]
  PNN-smoothingと呼ばれる$k$-meansクラスタリングアルゴリズムを初期化するメタメソッドを提案する。 与えられたデータセットを$J$のランダムなサブセットに分割し、各データセットを個別にクラスタリングし、結果のクラスタリングをペアワイズ・アネレス・ニーバーメソッドとマージする。
  論文  参考訳（メタデータ） (2022-02-08T15:56:30Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)

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

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