RANSAC とは

RANdom SAmple Consensus.
外れ値を含むデータから、外れ値の影響を除外して数学モデルのパラメータを学習する手法。

流れ

  1. 全データサンプル \(n\) 件のうち \(m\) 件をランダムに抽出(非復元抽出)
  2. 抽出したサンプルを使い、仮モデル \(C_1\) を学習
  3. 全データサンプルにおいて、\(C_1\) による予測値と実際のデータとの差が \(t\) 以下であるものを全て選び「正常値」とする
    • 正常値が少なすぎる(閾値を決めておく)場合は1に戻る
  4. 全ての正常値を用いてモデル \(C_2\) を学習
  5. 全ての正常値に対して、平均二乗誤差などの指標を用いて \(C_2\) の性能を評価
  6. 1〜5を \(k\) 回繰り返し、得られた \(C_2\) のうち最も性能の良いモデルを最終結果とする

\(m\), \(k\) の決め方

ランダム抽出件数 \(m\)

\(m\) がなるべく小さい方が、抽出したサンプルに外れ値が紛れ込みにくくなる。
最低限、モデルの自由度以上の値に設定すれば良い。

例えば二次関数であれば、\(y = a_0 + a_1 x + a_2 x^2\) の係数 \(a_0, a_1, a_2\) の3つを決めれば良いので自由度は3。

繰り返し回数 \(k\)

1回のランダム抽出件数 \(m\) が、全データ件数 \(n\) よりも十分小さい(\(m \ll n\))とする。

全データサンプル内の外れ値の割合を \(r_{\rm out}\) とすると、1回のランダムサンプリングにおいて抽出した \(m\) 件に外れ値が含まれない確率は、

\[\begin{eqnarray} \cfrac{ {}_{n(1-r_{\rm out})} C_m}{ {}_n C_m} &=& \cfrac{n(1-r_{\rm out}) \{n(1-r_{\rm out})-1\} \cdots \{n(1-r_{\rm out})-m+1)\}}{n (n-1) \cdots (n-m+1)} \\ &\simeq& \cfrac{\{n(1-r_{\rm out})\}^m}{n^m} \\ &=& (1 - r_{\rm out})^m \end{eqnarray}\]

逆に外れ値が含まれる確率は

\[1 - (1 - r_{\rm out})^m\]

よって、\(k\) 回のランダムサンプリングにおいて「少なくとも1回は外れ値が含まれない」確率は、

\[1 - ( 1 - (1 - r_{\rm out})^m )^k\]

この確率をなるべく高くしたい。\(p_0\) 以上という条件を課すと、

\[\begin{eqnarray} &p_0 \le 1 - \{ 1 - (1 - r_{\rm out})^m \}^k \\ \Longleftrightarrow\ & \{ 1 - (1 - r_{\rm out})^m \}^k \le 1 - p_0 \\ \Longleftrightarrow\ & k \log \{ 1 - (1 - r_{\rm out})^m \} \le \log (1 - p_0) \end{eqnarray}\]

対数の中は1より小さいから、対数は負になる。よって

\[k \ge \cfrac{\log (1 - p_0)}{\log \{ 1 - (1 - r_{\rm out})^m \}}\]

\(p_0\) が大きい方が外れ値を含まない確率が大きくなるが、大きくしすぎると必要な試行回数 \(k\) も跳ね上がる。

パラメータ \(r_{\rm out}, m\) を色々変えたときの \(p_0\) と \(k\) の関係を以下に示す。

Optimal k

実装

最小二乗法による多項式関数への回帰問題を想定。

コード

最小二乗法:

RANSAC:

動作確認

シンプルな最小二乗法と RANSAC の結果を比較。

RANSAC