論文の概要: On the Fundamental Limits of Exact Inference in Structured Prediction
- arxiv url: http://arxiv.org/abs/2102.08895v1
- Date: Wed, 17 Feb 2021 17:44:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-18 14:46:42.606383
- Title: On the Fundamental Limits of Exact Inference in Structured Prediction
- Title（参考訳）: 構造予測における厳密推論の基本限界について
- Authors: Hanbyul Lee and Kevin Bello and Jean Honorio
- Abstract要約: 推論は構造化予測の主要なタスクであり、自然にグラフでモデル化される。
正確な推論の目標は、各ノードの未知の真のラベルを正確に復元することである。
基礎的な限界と計算可能なbello と honorio の手法の性能との間にはギャップが存在することを示した。
- 参考スコア（独自算出の注目度）: 34.978150480870696
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inference is a main task in structured prediction and it is naturally modeled
with a graph. In the context of Markov random fields, noisy observations
corresponding to nodes and edges are usually involved, and the goal of exact
inference is to recover the unknown true label for each node precisely. The
focus of this paper is on the fundamental limits of exact recovery irrespective
of computational efficiency, assuming the generative process proposed by
Globerson et al. (2015). We derive the necessary condition for any algorithm
and the sufficient condition for maximum likelihood estimation to achieve exact
recovery with high probability, and reveal that the sufficient and necessary
conditions are tight up to a logarithmic factor for a wide range of graphs.
Finally, we show that there exists a gap between the fundamental limits and the
performance of the computationally tractable method of Bello and Honorio
(2019), which implies the need for further development of algorithms for exact
inference.
- Abstract（参考訳）: 推論は構造化予測の主要なタスクであり、自然にグラフでモデル化される。
Markovのランダムフィールドの文脈では、ノードとエッジに対応する騒々しい観測は通常関与しており、正確な推論の目標は、各ノードの未知の真のラベルを正確に回復することです。
本論文では,Globersonらによって提案された生成過程を仮定し,計算効率に関係なく正確な回復の基本的な限界に焦点をあてる。
(2015).
アルゴリズムに必要な条件と最大確率推定のための十分な条件を導き出し、高い確率で正確な回復を達成し、十分な条件と必要な条件が広範囲のグラフの対数係数までタイトであることを明らかにします。
最後に,bello と honorio (2019) の計算可能な手法の基本的な限界と性能の間にはギャップがあることを示し,正確な推論のためのアルゴリズムのさらなる開発の必要性を示唆する。
関連論文リスト
- Inference for an Algorithmic Fairness-Accuracy Frontier [0.9147443443422864]
We provide a consistent estimator for a theoretical fairness-accuracy frontier forward by Liang, Lu and Mu (2023)
フェアネス文学で注目されている仮説を検証するための推論手法を提案する。
サンプルサイズが大きくなるにつれて, 推定された支持関数が密なプロセスに収束することを示す。
論文 参考訳（メタデータ） (2024-02-14T00:56:09Z) - Structural Estimation of Markov Decision Processes in High-Dimensional
State Space with Finite-Time Guarantees [39.287388288477096]
本研究では,実施行動と訪問状態の観測可能な履歴に基づいて,人間エージェントによる動的決定の構造モデルの推定作業を検討する。
この問題には固有のネスト構造があり、内部問題では与えられた報酬関数に対する最適ポリシーが特定され、外部問題では適合度の測定が最大化される。
本研究では,高次元状態空間を扱うための有限時間保証付き単一ループ推定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-04T00:11:38Z) - Structured Optimal Variational Inference for Dynamic Latent Space Models [16.531262817315696]
動的ネットワークの潜在空間モデルについて検討し、その目的は、ペアの内積と潜在位置のインターセプトを推定することである。
後部推論と計算スケーラビリティのバランスをとるために、構造的平均場変動推論フレームワークを検討する。
論文 参考訳（メタデータ） (2022-09-29T22:10:42Z) - Confidence Adaptive Anytime Pixel-Level Recognition [86.75784498879354]
任意の時間推論は、いつでも停止される可能性のある予測の進行を行うモデルを必要とする。
我々は,任意のピクセルレベルの認識に対して,最初の統一とエンドツーエンドのモデルアプローチを提案する。
論文 参考訳（メタデータ） (2021-04-01T20:01:57Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳（メタデータ） (2020-03-06T16:17:24Z) - A General Framework for Consistent Structured Prediction with Implicit
Loss Embeddings [113.15416137912399]
構造化予測のための理論的・アルゴリズム的な枠組みを提案し,解析する。
問題に対して適切な幾何を暗黙的に定義する、損失関数の大規模なクラスについて検討する。
出力空間を無限の濃度で扱うとき、推定子の適切な暗黙の定式化が重要であることが示される。
論文 参考訳（メタデータ） (2020-02-13T10:30:04Z) - Polynomial-Time Exact MAP Inference on Discrete Models with Global
Dependencies [83.05591911173332]
ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。
本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
論文 参考訳（メタデータ） (2019-12-27T13:30:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。