論文の概要: Near-optimal Linear Predictive Clustering in Non-separable Spaces via Mixed Integer Programming and Quadratic Pseudo-Boolean Reductions

• arxiv url: http://arxiv.org/abs/2511.10809v2
• Date: Mon, 17 Nov 2025 02:13:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:22.586028
• Title: Near-optimal Linear Predictive Clustering in Non-separable Spaces via Mixed Integer Programming and Quadratic Pseudo-Boolean Reductions
• Title（参考訳）: 混合整数計画法と擬似擬似ブール還元による非分離空間における準最適線形予測クラスタリング
• Authors: Jiazhou Liang, Hassan Khurram, Scott Sanner,
• Abstract要約: 線形予測クラスタリング(LPC)は、特徴変数と対象変数の間の共有線形関係に基づいてサンプルを分割する。 LPCで一般的に使用されるグレディ最適化法はクラスタリングと線形回帰を交互に行うが、大域的最適性は欠いている。 この研究は、LPCのグローバル最適化の効率を改善する2つの新しいアプローチを導入するために、制約付き最適化パラダイムに基づいている。
• 参考スコア（独自算出の注目度）: 21.80447518126464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Linear Predictive Clustering (LPC) partitions samples based on shared linear relationships between feature and target variables, with numerous applications including marketing, medicine, and education. Greedy optimization methods, commonly used for LPC, alternate between clustering and linear regression but lack global optimality. While effective for separable clusters, they struggle in non-separable settings where clusters overlap in feature space. In an alternative constrained optimization paradigm, Bertsimas and Shioda (2007) formulated LPC as a Mixed-Integer Program (MIP), ensuring global optimality regardless of separability but suffering from poor scalability. This work builds on the constrained optimization paradigm to introduce two novel approaches that improve the efficiency of global optimization for LPC. By leveraging key theoretical properties of separability, we derive near-optimal approximations with provable error bounds, significantly reducing the MIP formulation's complexity and improving scalability. Additionally, we can further approximate LPC as a Quadratic Pseudo-Boolean Optimization (QPBO) problem, achieving substantial computational improvements in some settings. Comparative analyses on synthetic and real-world datasets demonstrate that our methods consistently achieve near-optimal solutions with substantially lower regression errors than greedy optimization while exhibiting superior scalability over existing MIP formulations.
• Abstract（参考訳）: 線形予測クラスタリング(LPC)は、特徴変数と対象変数の共用線形関係に基づくサンプルを分割する。 LPCで一般的に使用されるグレディ最適化法はクラスタリングと線形回帰を交互に行うが、大域的最適性は欠いている。 分離可能なクラスタには有効だが、クラスタが機能空間に重複する非分離可能な設定では苦労する。 代替の制約最適化パラダイムとして、BertsimasとShioda (2007)はLPCをMIP(Mixed-Integer Program)として定式化した。 この研究は、LPCのグローバル最適化の効率を改善する2つの新しいアプローチを導入するために、制約付き最適化パラダイムに基づいている。 分離性の重要な理論的特性を利用することで、証明可能な誤差境界を持つ近似近似を導出し、MIPの複雑性を著しく低減し、スケーラビリティを向上させる。 さらに、LPCを擬似擬似擬似ブール最適化(QPBO)問題として近似し、いくつかの設定で相当な計算改善を達成できる。 合成および実世界のデータセットの比較分析により,我々の手法は,既存のMIP定式化よりも優れたスケーラビリティを示しながら,グレディ最適化よりもかなり低い回帰誤差のほぼ最適解を一貫して達成していることが示された。

関連論文リスト

• Pareto Multi-Objective Alignment for Language Models [7.9051473654430655]
  大規模言語モデル(LLM)は、複数の、しばしば矛盾する、目的の慎重なバランスを必要とする現実世界のアプリケーションに、ますます多くデプロイされている。 LLMにおける多目的アライメント(MOA)を明示的に設計するアルゴリズムを提案する。 PAMAは、マルチオブジェクトRLHFをクローズドフォームソリューションで凸最適化に変換し、スケーラビリティを大幅に向上させる。
  論文  参考訳（メタデータ） (2025-08-11T08:54:14Z)
• Leveraging Robust Optimization for LLM Alignment under Distribution Shifts [51.74394601039711]
  人間の値に整合した出力を生成するために、大規模言語モデルを操る上で、優先順位アライメント手法はますます重要になっている。 このようなシフトに拘わらず、好みのアライメントを改善する新しい分布対応最適化フレームワークを提案する。
  論文  参考訳（メタデータ） (2025-04-08T09:14:38Z)
• Scalable Min-Max Optimization via Primal-Dual Exact Pareto Optimization [66.51747366239299]
  拡張ラグランジアンに基づくmin-max問題のスムーズな変種を提案する。 提案アルゴリズムは, 段階的戦略よりも目的数で拡張性が高い。
  論文  参考訳（メタデータ） (2025-03-16T11:05:51Z)
• Preference-Optimized Pareto Set Learning for Blackbox Optimization [1.9628841617148691]
  すべての目的を同時に最適化できる単一のソリューションはありません。 典型的なMOO問題では、目的間の好みを交換する最適解(パレート集合)を見つけることが目的である。 我々の定式化は、例えば微分可能なクロスエントロピー法によって解決できる二段階最適化問題につながる。
  論文  参考訳（メタデータ） (2024-08-19T13:23:07Z)
• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas と Ozturk (2023) は、ブラックボックスのグローバル最適化問題を解決する方法として OCTHaGOn を提案した。 我々は、他のMIO表現可能なMLモデルを用いて、元の問題を近似することで、このアプローチの拡張を提供する。 多くの場合において、ソリューションの実現可能性と最適性の改善を示す。
  論文  参考訳（メタデータ） (2023-11-03T06:33:38Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。 既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。 これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
  論文  参考訳（メタデータ） (2022-08-02T01:49:31Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。 このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。 提案手法の順序の順序による時間収束を,総じて低減する。
  論文  参考訳（メタデータ） (2020-05-21T20:59:11Z)

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

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