論文の概要: Finding Decision Tree Splits in Streaming and Massively Parallel Models

• arxiv url: http://arxiv.org/abs/2403.19867v3
• Date: Sat, 28 Sep 2024 08:50:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:00:45.123180
• Title: Finding Decision Tree Splits in Streaming and Massively Parallel Models
• Title（参考訳）: ストリームおよび大規模並列モデルにおける決定木分割の探索
• Authors: Huy Pham, Hoang Ta, Hoa T. Vu,
• Abstract要約: 観測データのストリームが与えられた場合、目標はデータを2つのセットに分割する最適な$j$を見つけることである。 これらの問題に対してサブ線形空間と少数のパスを使用する高速ストリーミングアルゴリズムを提供する。 これらのアルゴリズムは、超並列計算モデルにも拡張することができる。
• 参考スコア（独自算出の注目度）: 1.3654846342364308
• License:
• Abstract: In this work, we provide data stream algorithms that compute optimal splits in decision tree learning. In particular, given a data stream of observations $x_i$ and their labels $y_i$, the goal is to find the optimal split $j$ that divides the data into two sets such that the mean squared error (for regression) or misclassification rate and Gini impurity (for classification) is minimized. We provide several fast streaming algorithms that use sublinear space and a small number of passes for these problems. These algorithms can also be extended to the massively parallel computation model. Our work, while not directly comparable, complements the seminal work of Domingos-Hulten (KDD 2000) and Hulten-Spencer-Domingos (KDD 2001).
• Abstract（参考訳）: 本研究では,決定木学習における最適分割を計算するためのデータストリームアルゴリズムを提案する。 特に、観測データストリームの$x_i$とそのラベル$y_i$が与えられた場合、目標は、データを2つのセットに分割する最適な$j$を見つけ、平均二乗誤差(回帰)または誤分類率とGini不純物(分類)を最小化することである。 これらの問題に対してサブ線形空間と少数のパスを使用する高速ストリーミングアルゴリズムを提供する。 これらのアルゴリズムは、超並列計算モデルにも拡張することができる。 我々の研究は直接的に比較するものではないが、ドミンゴス=ハルテン(KDD 2000)とハルテン=スペンサー=ドミンゴス(KDD 2001)を補完するものである。

関連論文リスト

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Differentially Private Clustering in Data Streams [65.78882209673885]
  オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。 我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
  論文  参考訳（メタデータ） (2023-07-14T16:11:22Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• 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)
• Partial Wasserstein Covering [10.52782170493037]
  我々は、大規模なデータセットをエミュレートする目的で、部分的なWassersteinと呼ばれる一般的なタスクについて検討する。 この問題をワッサーシュタイン偏微分を目的関数とする離散最適化問題としてモデル化する。 我々は、シーンデータセットの駆動を含む部分的なワッサースタインの発散の観点から、2つのデータセットを効率的に作成できることを示します。
  論文  参考訳（メタデータ） (2021-06-02T01:48:41Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• How to Solve Fair $k$-Center in Massive Data Models [5.3283669037198615]
  我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。 主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
  論文  参考訳（メタデータ） (2020-02-18T16:11:40Z)
• A Deterministic Streaming Sketch for Ridge Regression [15.256452294422294]
  リッジ回帰を推定するための決定論的空間効率アルゴリズムを提案する。 これは、ソリューションエラーが保証された最初の$o(d2)$空間決定論的ストリーミングアルゴリズムである。 合成データセットと実世界のデータセットのランダムなスケッチアルゴリズムと比較して、我々のアルゴリズムは空間と類似時間が少なくて経験的誤差が少ない。
  論文  参考訳（メタデータ） (2020-02-05T22:08:29Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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