Technical Note - RANSAC
RANSAC とは
= RANdom SAmple Consensus.
外れ値を含むデータから、外れ値の影響を除外して数学モデルのパラメータを学習する手法。
流れ
- 全データサンプル \(n\) 件のうち \(m\) 件をランダムに抽出（非復元抽出）
- 抽出したサンプルを使い、仮モデル \(C_1\) を学習
- 全データサンプルにおいて、\(C_1\) による予測値と実際のデータとの差が \(t\) 以下であるものを全て選び「正常値」とする
- 正常値が少なすぎる（閾値を決めておく）場合は1に戻る
- 全ての正常値を用いてモデル \(C_2\) を学習
- 全ての正常値に対して、平均二乗誤差などの指標を用いて \(C_2\) の性能を評価
- 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\) の関係を以下に示す。
実装
最小二乗法による多項式関数への回帰問題を想定。
コード
最小二乗法：
RANSAC：
動作確認
シンプルな最小二乗法と RANSAC の結果を比較。
