Fugu-MT 論文翻訳(概要): Finding Decision Tree Splits in Streaming and Massively Parallel Models

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

arxiv url: http://arxiv.org/abs/2403.19867v1
Date: Thu, 28 Mar 2024 22:26:38 GMT
ステータス: 翻訳完了
システム内更新日: 2024-04-01 17:04:07.334514
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: http://creativecommons.org/licenses/by/4.0/
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 point $j$ that divides the data into two sets such that the mean squared error (for regression) or misclassification rate (for classification) is minimized. We provide various 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 and Hulten (KDD 2000).
Abstract（参考訳）: 本研究では,決定木学習における最適分割を計算するためのデータストリームアルゴリズムを提案する。特に、観測用$x_i$とそのラベル$y_i$のデータストリームが与えられた場合、目標は、データを2つのセットに分割する最適な分割点$j$を見つけ、平均二乗誤差(回帰用)または誤分類率(分類用)を最小化することである。これらの問題に対してサブ線形空間と少数のパスを使用する高速ストリーミングアルゴリズムを提供する。これらのアルゴリズムは、超並列計算モデルにも拡張することができる。我々の研究は直接的に比較するものではないが、ドミンゴスとハルテン(KDD 2000)の独創的な研究を補完する。

関連論文リスト

An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-09-30T15:57:14Z)
An improved column-generation-based matheuristic for learning classification trees [9.07661731728456]
決定木は機械学習(ML)における分類問題の解法として高度に解釈可能なモデルである決定木を訓練するための標準的なMLアルゴリズムは高速だが、精度の点で最適木を生成する。 citefirat 2020column氏は、意思決定木を学習するためのカラムジェネレーションベースのアプローチを提案した。
論文参考訳（メタデータ） (2023-08-22T14:43:36Z)
Improved Distribution Matching for Dataset Condensation [91.55972945798531]
本稿では,分布マッチングに基づく新しいデータセット凝縮法を提案する。提案手法は,計算資源の少ない従来の最適化指向手法よりも優れている。
論文参考訳（メタデータ） (2023-07-19T04:07:33Z)
Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文参考訳（メタデータ） (2023-07-14T16:11:22Z)
An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem [4.418462313508022]
インクリメンタルセル(ICE)は,0-1損失分類問題を正確に時間内に解くことができることを示す。この長年の問題に対する、厳格に証明された実用的なアルゴリズムとしては、これが初めてだ。
論文参考訳（メタデータ） (2023-06-21T15:41:34Z)
Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
論文参考訳（メタデータ） (2023-05-31T03:48:49Z)
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)
SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
既存のKRRの実装では、すべてのデータがメインメモリに格納される必要がある。 KRRのストリーミング版であるStreaMRAKを提案する。本稿では,2つの合成問題と2重振り子の軌道予測について紹介する。
論文参考訳（メタデータ） (2021-08-23T21:03:09Z)
Partial Wasserstein Covering [10.52782170493037]
我々は、大規模なデータセットをエミュレートする目的で、部分的なWassersteinと呼ばれる一般的なタスクについて検討する。この問題をワッサーシュタイン偏微分を目的関数とする離散最適化問題としてモデル化する。我々は、シーンデータセットの駆動を含む部分的なワッサースタインの発散の観点から、2つのデータセットを効率的に作成できることを示します。
論文参考訳（メタデータ） (2021-06-02T01:48:41Z)
Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
下流タスクの解決に使用されるデータの表現を評価することの問題点を考察する。本稿では,関心のあるタスクにおける低損失を実現する表現の上に,予測器を学習する複雑性によって表現の質を測定することを提案する。
論文参考訳（メタデータ） (2020-09-15T22:06:58Z)
Sparse learning with CART [18.351254916713305]
二分木を持つ決定木は、分類木と回帰木(CART)の手法を用いて一般的に構築されている。本稿では,CART法を用いて構築した回帰木の統計的特性について検討する。
論文参考訳（メタデータ） (2020-06-07T20:55:52Z)
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)

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