論文の概要: Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and
Applications
- arxiv url: http://arxiv.org/abs/2007.15109v3
- Date: Fri, 2 Jul 2021 16:19:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-05 20:53:27.682436
- Title: Outlier-Robust Estimation: Hardness, Minimally Tuned Algorithms, and
Applications
- Title（参考訳）: 外乱推定:硬さ、極小調整アルゴリズムとその応用
- Authors: Pasquale Antonante, Vasileios Tzoumas, Heng Yang, Luca Carlone
- Abstract要約: 本稿では,外乱推定,一般化最大収束(G-MC),一般化最小正方形(G-TLS)の2つの統一式を提案する。
最悪の場合、(概して)外れ値の集合を見つけることは不可能である。
そこで我々は, 降圧器から降圧器を分離する方法を動的に決定する, 降圧器のリジェクションのための最小調整アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 25.222024234900445
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nonlinear estimation in robotics and vision is typically plagued with
outliers due to wrong data association, or to incorrect detections from signal
processing and machine learning methods. This paper introduces two unifying
formulations for outlier-robust estimation, Generalized Maximum Consensus
(G-MC) and Generalized Truncated Least Squares (G-TLS), and investigates
fundamental limits, practical algorithms, and applications. Our first
contribution is a proof that outlier-robust estimation is inapproximable: in
the worst case, it is impossible to (even approximately) find the set of
outliers, even with slower-than-polynomial-time algorithms (particularly,
algorithms running in quasi-polynomial time). As a second contribution, we
review and extend two general-purpose algorithms. The first, Adaptive Trimming
(ADAPT), is combinatorial, and is suitable for G-MC; the second, Graduated
Non-Convexity (GNC), is based on homotopy methods, and is suitable for G-TLS.
We extend ADAPT and GNC to the case where the user does not have prior
knowledge of the inlier-noise statistics (or the statistics may vary over time)
and is unable to guess a reasonable threshold to separate inliers from outliers
(as the one commonly used in RANSAC). We propose the first minimally tuned
algorithms for outlier rejection, that dynamically decide how to separate
inliers from outliers. Our third contribution is an evaluation of the proposed
algorithms on robot perception problems: mesh registration, image-based object
detection (shape alignment), and pose graph optimization. ADAPT and GNC execute
in real-time, are deterministic, outperform RANSAC, and are robust up to 80-90%
outliers. Their minimally tuned versions also compare favorably with the state
of the art, even though they do not rely on a noise bound for the inliers.
- Abstract（参考訳）: ロボット工学と視覚の非線形推定は、通常、誤ったデータ関連付けや、信号処理や機械学習の手法による誤検出によって異常に苦しめられている。
本稿では,外乱推定のための2つの統一的な定式化,一般化最大収束(G-MC)と一般化最小平方(G-TLS)を導入し,基本的限界,実用的アルゴリズム,応用について検討する。
我々の最初の貢献は、アウトリアー・ロバスト推定がほぼ不可能であることの証明である: 最悪の場合、(ほぼ)アウトリアーの集合を見つけることは、時間よりも遅いアルゴリズム(特に、準多項時間で実行されるアルゴリズム)でさえも不可能である。
第2の貢献として,2つの汎用アルゴリズムをレビューし,拡張する。
第1のAdaptive Trimming (ADAPT) は組合せ的であり、G-MCに適しており、第2のDeleced Non-Convexity (GNC) はホモトピー法に基づいており、G-TLSに適している。
ADAPT と GNC は、ユーザがイリヤノイズ統計の事前知識を持っていない場合(あるいは、統計が時間とともに変化する場合)に拡張し、イリヤとイリヤを分離する合理的なしきい値(RANSAC でよく使われるもの)を推測できない場合に拡張する。
外れ値から外れ値を切り離す方法を動的に決定する、外れ値拒否のための最初の最小調整アルゴリズムを提案する。
第3の貢献は、メッシュ登録、画像に基づく物体検出(形状アライメント)、ポーズグラフ最適化といったロボット知覚問題に対するアルゴリズムの評価である。
ADAPTとGNCはリアルタイムで実行され、決定論的であり、RANSACより優れ、80-90%のアウトレイラが堅牢である。
彼らの最小限に調整されたバージョンは、イリヤのノイズに頼らずとも、芸術の状態を好意的に比較している。
関連論文リスト
- Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Outlier-Robust Geometric Perception: A Novel Thresholding-Based Estimator with Intra-Class Variance Maximization [4.3487328134753795]
我々は、新しい汎用ロバストな推定器TIVM(クラス内変動最大化による三値保持)を提案する。
標準的な非最小解法と協調して、幾何学的知覚問題に対する外れ値の除去を効率的に行うことができる。
我々の推定器は、問題の不整合ノイズ統計が完全に未知である場合でも、ほぼ同じレベルのロバスト性を維持することができる。
論文 参考訳（メタデータ） (2022-04-04T08:57:34Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-03-15T13:17:53Z) - Robust Algorithms for GMM Estimation: A Finite Sample Viewpoint [30.839245814393724]
モーメントの一般化法(GMM)
我々はGMM推定器を開発し、一定の$ell$リカバリ保証を$O(sqrtepsilon)$で許容する。
我々のアルゴリズムと仮定は、機器変数の線形回帰とロジスティック回帰に適用できる。
論文 参考訳（メタデータ） (2021-10-06T21:06:22Z) - Efficient Large Scale Inlier Voting for Geometric Vision Problems [3.1231364554255636]
コンピュータビジョンにおける多くの応用において、アウター・リジェクション(英語版)と等価に不整集合最適化(英語版)が重要な要素である。
我々は、$Rd$の「交差」$k$次元曲面に基づいて、外周拒絶に対する効率的で一般的なアルゴリズムを提案する。
本手法は, 複数枚のカメラにおいて, 多数の一致が低い不整合比で発生する問題に対するアプローチの汎用性を示す。
論文 参考訳（メタデータ） (2021-07-25T14:13:07Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Revisiting Robust Model Fitting Using Truncated Loss [19.137291311347788]
様々な2D/3D登録問題に新しいアルゴリズムを適用する。
RANSACと近似MC法を高い外れ値比で上回る。
新しいアルゴリズムは、特に高ノイズや外れ値において、最先端の登録手法と好意的に比較できる。
論文 参考訳（メタデータ） (2020-08-04T14:10:41Z) - Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。
本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
論文 参考訳（メタデータ） (2020-04-09T01:45:05Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。