論文の概要: Extensions of Karger's Algorithm: Why They Fail in Theory and How They
Are Useful in Practice
- arxiv url: http://arxiv.org/abs/2110.02750v1
- Date: Tue, 5 Oct 2021 07:46:28 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-07 14:44:47.615868
- Title: Extensions of Karger's Algorithm: Why They Fail in Theory and How They
Are Useful in Practice
- Title（参考訳）: Kargerのアルゴリズムの拡張:なぜ理論に失敗したのか、実際どのように役立つのか
- Authors: Erik Jenner, Enrique Fita Sanmart\'in, Fred A. Hamprecht
- Abstract要約: カーガーのアルゴリズムが他のカット問題に対してうまく一般化できるかどうかを考察する。
本稿では,シードセグメンテーション/グラフベース半教師付き学習のための簡単なアルゴリズムを提案する。
新しいアルゴリズムは線形実行時を持ち、与えられた種/クラスに属するサンプルの後方確率と解釈できるポテンシャルを与える。
- 参考スコア（独自算出の注目度）: 17.801124377461953
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimum graph cut and minimum $s$-$t$-cut problems are important
primitives in the modeling of combinatorial problems in computer science,
including in computer vision and machine learning. Some of the most efficient
algorithms for finding global minimum cuts are randomized algorithms based on
Karger's groundbreaking contraction algorithm. Here, we study whether Karger's
algorithm can be successfully generalized to other cut problems. We first prove
that a wide class of natural generalizations of Karger's algorithm cannot
efficiently solve the $s$-$t$-mincut or the normalized cut problem to
optimality. However, we then present a simple new algorithm for seeded
segmentation / graph-based semi-supervised learning that is closely based on
Karger's original algorithm, showing that for these problems, extensions of
Karger's algorithm can be useful. The new algorithm has linear asymptotic
runtime and yields a potential that can be interpreted as the posterior
probability of a sample belonging to a given seed / class. We clarify its
relation to the random walker algorithm / harmonic energy minimization in terms
of distributions over spanning forests. On classical problems from seeded image
segmentation and graph-based semi-supervised learning on image data, the method
performs at least as well as the random walker / harmonic energy minimization /
Gaussian processes.
- Abstract（参考訳）: 最小グラフカットと最小$s$-$t$-cut問題は、コンピュータビジョンや機械学習を含む計算機科学における組合せ問題のモデリングにおいて重要なプリミティブである。
グローバル最小カットを見つけるための最も効率的なアルゴリズムは、カーガーの画期的な縮小アルゴリズムに基づくランダム化アルゴリズムである。
本稿では,カーガーのアルゴリズムが他のカット問題に対してうまく一般化できるかどうかを考察する。
まず、カルガーのアルゴリズムの幅広い自然な一般化は、最適性のために$s$-$t$-mincut や正規化カット問題を効率的に解くことができないことを証明した。
しかし,これらの問題に対して,カルガーのアルゴリズムの拡張が有効であることを示すために,seed segmentation / graph-based semi-supervised learningのための単純な新しいアルゴリズムを提案する。
この新しいアルゴリズムは線形漸近ランタイムを持ち、与えられた種/クラスに属するサンプルの後方確率として解釈できるポテンシャルを持つ。
森林分布におけるランダムウォーカアルゴリズムと調和エネルギーの最小化の関係を明らかにする。
画像データ上でのシード画像分割やグラフに基づく半教師付き学習といった古典的な問題に対して、この手法は少なくともランダムウォーカー/ハーモニックエネルギー最小化/ガウス過程を実行する。
関連論文リスト
- More on greedy construction heuristics for the MAX-CUT problem [8.148355685823521]
この図は, 最大カット問題に対して, 主なグリーディを分類するのに有効であることを示す。
SG(Sahni-Gonzalez)アルゴリズムの全てのバージョンはプリム類に分類される。
様々なエッジ・コントラクション(EC)アルゴリズムはKruskalクラスに属する。
論文 参考訳（メタデータ） (2023-12-18T02:52:04Z) - Learning Arithmetic Formulas in the Presence of Noise: A General
Framework and Applications to Unsupervised Learning [4.10375234787249]
教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。
我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2023-11-13T12:26:25Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Efficient and Local Parallel Random Walks [21.29022677162416]
ランダムウォークは、多くの機械学習アルゴリズムで使用される基本的なプリミティブである。
ランダムウォークを効率的に局所的に構築することで,この制限を克服するアルゴリズムを提案する。
本手法はメモリとラウンド効率の両方で,特に並列局所クラスタリングアルゴリズムを効率よく実現している。
論文 参考訳（メタデータ） (2021-12-01T17:06:11Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Community detection using fast low-cardinality semidefinite programming [94.4878715085334]
局所的な更新を一般化し、ライデン-k-カットから導かれる半定緩和を最大化する、新しい低カルチナリティアルゴリズムを提案する。
提案アルゴリズムはスケーラビリティが高く,最先端のアルゴリズムより優れ,実時間では性能が向上し,追加コストがほとんどない。
論文 参考訳（メタデータ） (2020-12-04T15:46:30Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。