論文の概要: Mixed-Integer Programming for Change-point Detection

• arxiv url: http://arxiv.org/abs/2602.11947v1
• Date: Thu, 12 Feb 2026 13:43:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-13 21:07:25.847364
• Title: Mixed-Integer Programming for Change-point Detection
• Title（参考訳）: 変化点検出のための混合整数計画法
• Authors: Apoorva Narula, Santanu S. Dey, Yao Xie,
• Abstract要約: オフライン複数変更点検出のためのMIP(Mixed-integer Programming)アプローチを提案する。 この枠組みを, (i) 多次元PWLモデルと (ii) わずかな変化点検出という, 活発な研究関心の2つの設定に拡張する。
• 参考スコア（独自算出の注目度）: 8.644610122423993
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a new mixed-integer programming (MIP) approach for offline multiple change-point detection by casting the problem as a globally optimal piecewise linear (PWL) fitting problem. Our main contribution is a family of strengthened MIP formulations whose linear programming (LP) relaxations admit integral projections onto the segment assignment variables, which encode the segment membership of each data point. This property yields provably tighter relaxations than existing formulations for offline multiple change-point detection. We further extend the framework to two settings of active research interest: (i) multidimensional PWL models with shared change-points, and (ii) sparse change-point detection, where only a subset of dimensions undergo structural change. Extensive computational experiments on benchmark real-world datasets demonstrate that the proposed formulations achieve reductions in solution times under both $\ell_1$ and $\ell_2$ loss functions in comparison to the state-of-the-art.
• Abstract（参考訳）: 本稿では,この問題を大域的最適ピースワイドリニア(PWL)フィッティング問題としてキャストすることで,オフライン複数変更点検出のためのMIP(Mixed-integer Programming)アプローチを提案する。 我々の主な貢献は、線形プログラミング(LP)緩和が各データポイントのセグメントメンバシップを符号化するセグメント割り当て変数への積分射影を許容する強化されたMIP定式化のファミリーである。 この性質は、オフラインの多重変更点検出のための既存の定式化よりも確実に緩和する。 我々はさらに、この枠組みを活発な研究関心の2つの設定に拡張する。 (i)共有変化点をもつ多次元PWLモデル、及び (ii) わずかな変化点検出であって, 寸法のサブセットのみが構造変化を受ける場合。 ベンチマーク実世界のデータセットに対する大規模な計算実験により、提案された定式化は、最先端のものと比べ、$\ell_1$と$\ell_2$損失関数の両方で解時間の減少を達成することを示した。

関連論文リスト

• Tightening the mixed integer linear formulation for the piecewise linear approximation in general dimensions [4.566850249315913]
  本稿では,任意の次元のデータセットの連続分数線形(CPWL)近似に対する混合整数プログラミング(MILP)の定式化について述べる。
  論文  参考訳（メタデータ） (2025-08-13T00:00:09Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  部分重なり合う点集合を整列する新しい大域的最適化手法を提案する。 本手法は非剛性変形, 位置雑音, 外れ値に優れた強靭性を示す。 2次元および3次元合成および実世界のデータを用いた実験により,本手法は最先端の手法と比較して,外れ値に対して優れた強靭性を示すことが示された。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Sample Complexity Characterization for Linear Contextual MDPs [67.79455646673762]
  文脈決定プロセス(CMDP)は、遷移カーネルと報酬関数がコンテキスト変数によってインデックス付けされた異なるMDPで時間とともに変化できる強化学習のクラスを記述する。 CMDPは、時間とともに変化する環境で多くの現実世界のアプリケーションをモデル化するための重要なフレームワークとして機能する。 CMDPを2つの線形関数近似モデルで検討する: 文脈変化表現とすべての文脈に対する共通線形重み付きモデルIと、すべての文脈に対する共通表現と文脈変化線形重み付きモデルIIである。
  論文  参考訳（メタデータ） (2024-02-05T03:25:04Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  非剛体形状の正確なスパース対応を生成するための新しい混合整数プログラミング(MIP)法を提案する。 いくつかの挑戦的な3Dデータセットに対して,スパースな非剛性マッチングの最先端結果を示す。
  論文  参考訳（メタデータ） (2023-08-16T14:25:30Z)
• Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
  本稿では,線形制約付き混合変数問題の解法として,新しいサロゲートに基づく大域的最適化アルゴリズムを提案する。 提案手法は, 目的関数の断片的なアフィンサロゲートを, 実現可能なサンプル上に構築することに基づいている。 この2つのアルゴリズムは、制約なしおよび制約付き混合変数ベンチマーク問題に対して評価される。
  論文  参考訳（メタデータ） (2023-02-09T15:04:35Z)
• Robust Multi-view Registration of Point Sets with Laplacian Mixture Model [25.865100974015412]
  重み付きラプラシアン分布に基づいて複数の点集合を整列させる新しい確率的生成法を提案する。 本稿では,提案手法の利点を,ベンチマークの挑戦的データセットに対する最先端手法と比較することによって示す。
  論文  参考訳（メタデータ） (2021-10-26T14:49:09Z)
• InverseForm: A Loss Function for Structured Boundary-Aware Segmentation [80.39674800972182]
  逆変換ネットワークを用いたセマンティックセグメンテーションのための新しい境界認識損失項を提案する。 このプラグイン損失項は境界変換の捕捉におけるクロスエントロピー損失を補完する。 室内および屋外のセグメンテーションベンチマークにおける損失関数の定量的および定性的効果を解析した。
  論文  参考訳（メタデータ） (2021-04-06T18:52:45Z)
• Compositional ADAM: An Adaptive Compositional Solver [69.31447856853833]
  C-ADAMは、期待値の非線形機能ネストを含む構成問題に対する最初の適応的解法である。 C-ADAM は $mathcalO(delta-2.25)$ の定常点に収束し、$delta$ は精度パラメータであることを示す。
  論文  参考訳（メタデータ） (2020-02-10T14:00:45Z)

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

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