【わかりやすく】RANSAC(Random Sample Consensus)とは：アルゴリズム、最小二乗法との違い、読み方

RANSACとは：ロバスト推定
アルゴリズム
アルゴリズムのお気持ち
最小二乗法との違い
RANSACの読み方
ゆるふわ理解をしたい人向け参考資料
あわせて読みたい

RANSACとは：ロバスト推定

RANSACは外れ値を含む回帰問題などに使う。

通常の最小二乗法だと結果が外れ値に引っ張られてしまい、サンプルが本来持っている特徴を表現できない。

このように外れ値を含む場合の回帰に使うロバスト推定には、色々なアルゴリズムがあるようだが、その一つがRANSAC。

「ロバスト」は「頑健な」という意味で、今の文脈では「外れ値に引っ張られずに安定した結果を返す」というような意味である。

アルゴリズム

方法としては、データから一部をランダムに抽出してモデルをフィットさせ、そのモデルのフィット具合で外れ値と正常データを区別するイメージだ。

アルゴリズムの概要は以下。

データから一部をランダムにサンプル抽出する
サンプルに対してモデルをフィットさせ、パラメーターを推定
手順1で抽出されなかったデータ１つ１つに対して、モデルの当てはまりを確認
データ１つ１つに対してモデルの誤差が事前に設定した水準以内であれば、「このデータは外れ値ではない」と判断し、手順2の教師データに追加する
手順4をサンプル以外の全データに行った結果、教師データの要素数が閾値を超えていれば、手順4のデータ追加後の教師データ全体に対してモデルをフィットさせ、当てはまりを確認
手順1～手順5を規定の回数だけ繰り返し、手順5の当てはまりが最良のパラメーターを最終結果とする

アルゴリズムのお気持ち

ポイントは、なんとかして外れ値を除去して正常データだけで回帰しよう、という点である。そのために、データの全てをパラメーター推定に使うのではなく、一部だけを使う。

一部のデータにフィットさせた結果が、教師データ以外のデータにも当てはまっているなら、そのデータは外れ値ではないとみなして教師データに加える。このようにして「外れ値ではないと思われるデータ」を抽出し、それら全体にモデルをフィットさせる。

以上の処理を繰り返し、当てはまりが最も良かった教師データが「正常データ全体」とみなして、それにモデルをフィットさせた結果を出力する。

しかし方法としてはかなり試行錯誤的なので効率が悪いため、計算高速化のための改善版アルゴリズムがあれこれ提案されているようだ。

最小二乗法との違い

アルゴリズムを見れば、最小二乗法との違いは明らかだが、違いとしては次の通り。

最小二乗法では（外れ値を含む）全てのデータを使ってパラメーター推定するが、RANSACでは全データから一部を抽出して当てはまりを調べる、という試行錯誤を繰り返す
最小二乗法では正常データと外れ値を区別しようとしないが、RANSACでは正常データと外れ値を区別しようと試行錯誤し、最後は「正常データと思われるデータ」のみでパラメーター推定する