論文の概要: A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees

• arxiv url: http://arxiv.org/abs/2505.12460v1
• Date: Sun, 18 May 2025 15:28:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.248782
• Title: A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees
• Title（参考訳）: ヒストグラム勾配発芽木に結合したライブラリーレベルk平均の1例
• Authors: Asher Labovich,
• Abstract要約: そこで本研究では,k平均離散化器を量子化器に置き換えることを提案する。 我々は、このスワップを33のOpenMLタスクに加えて、モダリティ、スキュー、ビンの予算を管理するシンセサイザーでテストする。 k-平均は、余分なカットがほとんど値を加えないときの正確な分割と同等の誤差を保ちながら、定量化の見落としとなる重要な分割点を回復する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Modern gradient-boosted decision trees (GBDTs) accelerate split finding with histogram-based binning, which reduces complexity from O(N) to O(B) given a fixed bin budget B. However, the predominant quantile binning strategy-designed to distribute data points evenly among bins-may overlook critical boundary values that could enhance predictive performance. In this work, we propose replacing quantile binning with a k-means discretizer initialized with quantile bins. We test this swap on 33 OpenML tasks plus synthetics that control for modality, skew, and bin budget. Across 18 regression datasets, k-means shows no statistically significant losses at the 5% level and wins in four cases-most strikingly a 55% MSE drop on one particularly skewed dataset-even though k-means' mean reciprocal rank (MRR) is slightly lower (0.65 vs 0.72). On the 15 classification datasets the two methods are statistically tied (MRR 0.70 vs 0.68) with gaps $\leq$0.2 pp. Synthetic experiments confirm consistently large MSE gains-typically >20% and rising to 90% as outlier magnitude increases or bin budget drops. We find that k-means keeps error on par with exact splitting when extra cuts add little value, yet still recovers key split points that quantile overlooks. As such, we advocate for a built-in bin_method=k-means flag, especially in regression tasks and in tight-budget settings such as the 32-64-bin GPU regime-because it is a "safe default" with large upside, yet adds only a one-off, cacheable overhead ($\approx$ 2s to bin 10M rows on one core).
• Abstract（参考訳）: 最新の勾配ブースト決定木 (GBDT) は, O(N) から O(B) への複雑性を減少させるヒストグラムベースのビンニングにより, 分割探索を加速する。 本研究では,量子ビンを初期化したk平均離散化器に置き換えることを提案する。 我々は、このスワップを33のOpenMLタスクに加えて、モダリティ、スキュー、ビンの予算を管理するシンセサイザーでテストする。 18の回帰データセット全体では、k平均は5%レベルで統計的に有意な損失を示さず、k平均の相反位(MRR)がわずかに低い(0.65対0.72)にもかかわらず、4つのケースで最も顕著に55%のMSE低下を達成している。 15の分類データセットでは、2つの手法は統計的に結びついており(MRR 0.70 vs 0.68)、ギャップは$\leq$0.2 ppである。 合成実験は、常に大きなMSEゲインが20%以上上昇し、アウトリーチ等級が増大したり、ビンの予算が低下するにつれて90%に上昇することを確認した。 k-平均は、余分なカットがほとんど値を加えないときの正確な分割と同等の誤差を保ちながら、定量化の見落としとなる重要な分割点を回復する。 ですから,特にレグレッションタスクや32-64-bin GPUレシスタンスのような厳格な予算設定では,大きなアップサイドで“セーフデフォルト”であると同時に,ワンオフでキャッシュ可能なオーバーヘッド(bin 10M行に対して2s$\approx)のみを追加するため,組み込みのbin_method=k-meansフラグを推奨しています。

関連論文リスト

• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  本稿では, コントラスト損失計算を任意の小ブロックに分割するタイルベースの戦略を提案する。 分散システムの階層構造を活用するためのマルチレベルタイリング戦略も導入する。 SOTAメモリ効率のソリューションと比較すると、同等の速度を維持しながら、メモリの2桁の削減を実現している。
  論文  参考訳（メタデータ） (2024-10-22T17:59:30Z)
• Geometric Median (GM) Matching for Robust Data Pruning [29.458270105150564]
  本稿では,雑音のあるデータセットの幾何的中央値に近似した$k$-subsetを求める群れ型グリードアルゴリズムを提案する。 いくつかの人気のあるディープラーニングベンチマークに対する実験は、$gm$ Matchingが従来よりも一貫して改善されていることを示している。
  論文  参考訳（メタデータ） (2024-06-25T00:02:01Z)
• Outlier Suppression: Pushing the Limit of Low-bit Transformer Language Models [57.933500846742234]
  最近の研究は、構造化された外れ値が量子化性能の重要なボトルネックであることを認識している。 本稿では,Gamma Migration と Token-Wise Clipping の2つのコンポーネントを含む外部抑制フレームワークを提案する。 このフレームワークは、アウトレイラを効果的に抑制し、プラグアンドプレイモードで使用することができる。
  論文  参考訳（メタデータ） (2022-09-27T12:05:59Z)
• Reducing Variance in Temporal-Difference Value Estimation via Ensemble of Deep Networks [109.59988683444986]
  MeanQは単純なアンサンブル法であり、ターゲット値をアンサンブル平均として推定する。 本稿では,Atari Learning Environmentベンチマークを用いた実験において,MeanQが顕著なサンプル効率を示すことを示す。
  論文  参考訳（メタデータ） (2022-09-16T01:47:36Z)
• The Lepto-Variance of Stock Returns [0.0]
  Regression Treeは、特定の特徴を使ってサンプルをソートし、ノードから子供への最大分散還元を生成する分割点を見つける。 私たちのキーとなる観察は、(MSEドロップの観点で)最適な要素は、常にターゲット自身であり、これがターゲットを最も明確に分離していることです。 1ビットと2ビットのRTをベースとしたレプト構造解析を行い、IBM株の日次リターンを実証する。
  論文  参考訳（メタデータ） (2022-06-29T04:15:35Z)
• Minimum mean-squared error estimation with bandit feedback [10.660855209170586]
  平均二乗誤差 (MSE) の意味で, 逐次的に推定を学習する問題を考察する。 2つのMSE推定器を提案し,その濃度特性を解析した。
  論文  参考訳（メタデータ） (2022-03-31T05:33:32Z)
• Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogates [0.0]
  提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。 非テンション依存データ設定の下で, 各種手法の収束点を求める。
  論文  参考訳（メタデータ） (2022-01-05T15:17:35Z)
• Consistent Structured Prediction with Max-Min Margin Markov Networks [84.60515484036239]
  二項分類のためのマックスマージン法は、最大マージンマルコフネットワーク(M3N$)の名前で構造化予測設定まで拡張されている。 我々は、学習問題を"max-min"マージンの定式化で定義し、結果のメソッドmax-minマージンマルコフネットワーク(M4N$)を命名することで、そのような制限を克服する。 マルチクラス分類,順序回帰,シーケンス予測,ランキング実験により,提案手法の有効性が示された。
  論文  参考訳（メタデータ） (2020-07-02T10:48:42Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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