論文の概要: Graph cuts always find a global optimum for Potts models (with a catch)

• arxiv url: http://arxiv.org/abs/2011.03639v2
• Date: Tue, 15 Jun 2021 01:33:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-28 22:08:12.391499
• Title: Graph cuts always find a global optimum for Potts models (with a catch)
• Title（参考訳）: グラフカットは、常に(キャッチ付きで)Pottsモデルのグローバルな最適化を見つける
• Authors: Hunter Lang, David Sontag, Aravindan Vijayaraghavan
• Abstract要約: MAP推論のための$alpha$-expansionアルゴリズムは、常にポッツ対ポテンシャルを持つマルコフランダム場に対して、大域的に最適な代入を返すことを証明している。 拡張移動に関するすべての局所ミニマは、問題のわずかに摂動されたバージョンに対する大域的ミニマである。
• 参考スコア（独自算出の注目度）: 17.03788288165262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that the $\alpha$-expansion algorithm for MAP inference always returns a globally optimal assignment for Markov Random Fields with Potts pairwise potentials, with a catch: the returned assignment is only guaranteed to be optimal for an instance within a small perturbation of the original problem instance. In other words, all local minima with respect to expansion moves are global minima to slightly perturbed versions of the problem. On "real-world" instances, MAP assignments of small perturbations of the problem should be very similar to the MAP assignment(s) of the original problem instance. We design an algorithm that can certify whether this is the case in practice. On several MAP inference problem instances from computer vision, this algorithm certifies that MAP solutions to all of these perturbations are very close to solutions of the original instance. These results taken together give a cohesive explanation for the good performance of "graph cuts" algorithms in practice. Every local expansion minimum is a global minimum in a small perturbation of the problem, and all of these global minima are close to the original solution.
• Abstract（参考訳）: MAP推論のための$\alpha$-expansionアルゴリズムは、常にポッツ対ポテンシャルを持つマルコフ確率場に対する大域的最適代入を返すことを証明している。 言い換えれば、拡張移動に関するすべての局所的ミニマは、問題のわずかに摂動したバージョンに対するグローバルなミニマである。 実世界の」インスタンスでは、問題の小さな摂動のMAP代入は、元の問題インスタンスのMAP代入と非常によく似ているはずである。 これが現実のケースであるかどうかを証明できるアルゴリズムを設計。 コンピュータビジョンからのMAP推論問題インスタンスでは、これらの摂動に対するMAP解が元のインスタンスの解に非常に近いことを証明している。 これらの結果は、実際に「グラフカット」アルゴリズムの優れた性能を示す結合的な説明を与える。 すべての局所展開最小は問題の小さな摂動における大域的最小であり、これらの大域的ミニマはすべて元の解に近くなる。

関連論文リスト

• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。 本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。 提案手法の有効性を4つの標準ベンチマークで示す。
  論文  参考訳（メタデータ） (2024-07-10T16:51:32Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。 本稿では,2種類のミニマックスアルゴリズムを提案する。 そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
  論文  参考訳（メタデータ） (2023-02-08T01:42:45Z)
• Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Rate [14.191310794366075]
  本稿では,機械学習における多種多様な応用を見出した低ランク行列最適化について述べる。 雑音モデルが任意である一般目的関数に対するランダムな汚職に対処できるフレームワークを開発する。 RIP定数が1/3$以上である場合、地平線付近の局所領域における問題の急激な局所最小値の幾何学を特徴付ける。
  論文  参考訳（メタデータ） (2022-03-08T07:44:47Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• Extensions of Karger's Algorithm: Why They Fail in Theory and How They Are Useful in Practice [17.801124377461953]
  カーガーのアルゴリズムが他のカット問題に対してうまく一般化できるかどうかを考察する。 本稿では,シードセグメンテーション/グラフベース半教師付き学習のための簡単なアルゴリズムを提案する。 新しいアルゴリズムは線形実行時を持ち、与えられた種/クラスに属するサンプルの後方確率と解釈できるポテンシャルを与える。
  論文  参考訳（メタデータ） (2021-10-05T07:46:28Z)
• Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
  非使用最適化は、現代の機械学習においてユビキタスである。 機械学習問題の場合、厳格に定式化します。 我々はこの現象の統一的な説明を仮定する。
  論文  参考訳（メタデータ） (2021-03-24T19:34:11Z)
• Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm [19.987509826212115]
  本稿では,パスグラフ上の集合的グラフィカルモデル(CGM)に対するMAP推論の新しい手法を提案する。 まず、MAP推論問題を(非線形)最小コストフロー問題として定式化できることを示す。 提案手法では,dcaの重要なサブルーチンを最小凸コストフローアルゴリズムにより効率的に計算できる。
  論文  参考訳（メタデータ） (2021-02-18T07:28:18Z)
• Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
  局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。 提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
  論文  参考訳（メタデータ） (2020-12-04T15:46:30Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• Robust estimation via generalized quasi-gradients [28.292300073453877]
  最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。 我々は「一般化された準次数」の存在を識別する 一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-05-28T15:14:33Z)

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

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