MaxCon(最大コンセンサス)

最大コンセンサス(Maximum consensus) は、RANSACが近似的にのみ解いている最適化問題である。残差関数 $r_i(\theta)$ とインライア閾値 $\epsilon$ を持つ観測が与えられたとき、できるだけ多くの観測に一致するモデルを見つける。

最大化される集合がコンセンサス集合(インライア集合)である。基礎行列、ホモグラフィ、カメラ姿勢、点群レジストレーションを「最もインライアが多くなるように」フィットさせることは、すべてこの一つの問題のインスタンスである。

RANSACが物語の終わりではない理由

RANSAC はランダムな最小サンプリングによって最大コンセンサスに取り組む:高い確率で良いコンセンサス集合を返すが、

• ランダム化されている — 同じデータに対する2回の実行が異なる答えを返すことがある。
• 最適性の保証がない — 返されたコンセンサス集合は真の最大値より小さくなり得る。特に外れ値の比率が高い場合、必要なサンプル数が爆発的に増える状況で顕著である。
• 返されるモデルは最小サンプルにフィットされたものなので、洗練されるまでは雑音に敏感である。

最大コンセンサスを適切な最適化問題として研究するということは、決定論的に厳密な最大化解を見つけるには何が必要かを問うことである。

困難さと厳密なアルゴリズム

悪い知らせは根本的なものだ:最大コンセンサスは一般にNP困難である — どの観測部分集合を信頼するかに関する組合せ問題であり、P = NPでない限り、すべてのインスタンスを効率的に解けるアルゴリズムは存在しない。コンセンサスの目的関数も解析的に厄介である:これは $\theta$ の区分的定数の計数関数であり、ほとんどすべての点で勾配がゼロになるため、通常の非線形最適化では直接扱うことができない。

したがって厳密な(大域的に最適な)手法は最悪の場合指数時間のコストを払うが、小規模な問題では実用的になり得る。

• 分枝限定法(BnB):パラメータ空間(例えば回転/並進空間)を再帰的に分割し、これまでに見つかった最良解より達成可能なコンセンサスの上界が悪い分枝を刈り込む。終了時に大域的最適解が保証される。
• アクティブセットに対する木探索:このような問題の最適解が制約の小さな基底によって特徴付けられるという事実を利用し、ベストファースト(A*式)戦略で基底を探索する。
• 混合整数計画法:観測ごとに二値変数 $z_i \in \{0, 1\}$ を導入し、以下を解く。

大きな定数 $M$ を用いて、問題を市販のMIPソルバーに渡す。

有用な再定式化がある:コンセンサスの最大化は、違反された制約の数を最小化すること — $\ell_0$型の目的関数 — と等価である。この視点は、MaxConをそのより扱いやすい代替手法へと結びつける:$\ell_0$ を $\ell_1$ や他の凸損失に緩和すると凸緩和によるアプローチが得られ、ロバストカーネルを凸から再降下型へ徐々に変形させると段階的非凸性(GNC)が得られる。これらは厳密さを多項式時間の実行時間と引き換えにするが、事後的な最適性証明を伴う場合もある。

実践的な地図

SLAMにおける意義

SLAMにおけるすべての幾何推定ステップ — 基礎行列、PnP、ループクロージャ検証、点群レジストレーション — は、内部的には最大コンセンサス問題である。リアルタイムのフロントエンドは今後もRANSAC系ヒューリスティックを使い続けるだろうが、厳密な問題を知っておくことで、何が犠牲になっているかが明確になる:ランダム化されたフロントエンドは知らぬ間に最適でないコンセンサス集合を受け入れる可能性があり、それに基づいた一つの誤ったループクロージャが地図全体を歪めてしまうことがある。これが、証明可能なロバスト推定という研究の方向性(大域的最適な回転探索、TEASER式のレジストレーション、GNCバックエンド)を動機づけている。誤った答えのコストが高いSLAMシステムでは、これらの手法がますます見られるようになっている。

関連ノート

• RANSAC
• PROSAC
• 凸緩和
• M推定量
• TEASER++