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

• arxiv url: http://arxiv.org/abs/2505.12460v2
• Date: Sun, 05 Oct 2025 18:46:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 14:28:09.78213
• Title: A Case for Library-Level k-Means Binning in Histogram Gradient-Boosted Trees
• Title（参考訳）: ヒストグラム勾配発芽木に結合したライブラリーレベルk平均の1例
• Authors: Asher Labovich,
• Abstract要約: 量子ビン化を$k$-means離散化器に置き換える新しい手法を考える。 我々はこのスワップを、33のOpenMLデータセット上で量子化と均一なビンニングに対してテストする。
• 参考スコア（独自算出の注目度）: 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\log N)$ to $O(N)$ by aggregating gradients into fixed-size bins. 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 consider a novel approach that replaces quantile binning with a $k$-means discretizer initialized with quantile bins, and justify the swap with a proof showing how, for any $L$-Lipschitz function, k-means maximizes the worst-case explained variance of Y obtained when treating all values in a given bin as equivalent. We test this swap against quantile and uniform binning on 33 OpenML datasets 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 three 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 exhaustive (no-binning) 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$ 3.5s per feature to bin 10M rows on one Apple M1 thread).
• Abstract（参考訳）: 現代のグラディエントブースト決定木(GBDT)はヒストグラムベースのビンニングにより分割探索を加速し、勾配を固定サイズのビンに集約することで複雑さを$O(N\log N)$から$O(N)$に減らす。 しかし、データポイントをビン間で均等に分配するように設計された主要な量子ビンニング戦略は、予測性能を高める重要な境界値を見落としてしまう可能性がある。 本研究では、量子ビン化を量子ビンで初期化された$k$-means離散化器に置き換える新しいアプローチを検討し、任意の$L$-Lipschitz関数に対して、k-meansが与えられたビン内のすべての値を等価として扱う際に得られるYの最悪のケース説明分散を最大化することを示す証明でスワップを正当化する。 我々はこのスワップを、33のOpenMLデータセットと、モダリティ、スキュー、ビン予算を制御する合成物で、量子化と均一なビンニングに対してテストする。 18の回帰データセット全体では、k平均は5%レベルで統計的に有意な損失を示さず、最も顕著なのは、k平均の相反位(MRR)がわずかに低い(0.65対0.72)にもかかわらず、特に歪んだデータセットに対して55%のMSE低下で3件で勝利したことである。 15の分類データセットでは、2つの手法は統計的に結びついており(MRR 0.70 vs 0.68)、ギャップは$\leq$0.2 ppである。 合成実験は、常に大きなMSEゲイン(典型的には20%から90%まで上昇する)を確認している。 k-平均は、余分なカットがほとんど値を加えないときに、徹底的な(結合しない)分割と同じ誤差を保ちながら、量子的見落としのキースプリットポイントを回復する。 そのため、特にレグレッションタスクや32-64-bin GPUレギュレーションのような厳格な予算設定において、組み込みのbin_method=k-meansフラグを提唱します。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
  論文  参考訳（メタデータ） (2025-06-01T09:34:52Z)
• 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)
• Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds [34.37963000493442]
  本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-14T12:58:46Z)
• 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)

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

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