最小二乗法

最小二乗法とは何か

最小二乗法(least-squares)は、最適化問題の一種です。ボイド(Boyd)とヴァンデンバーグ(Vandenberghe)による凸最適化の教科書 Convex Optimization では、最小二乗問題を次のような問題として定義しています。

• 制約が無い(変数の取りうる値に条件を付けない)最適化問題である
• 最小にしたい量(目的関数)は、いくつかの項を二乗して足し合わせたものである
• それぞれの項は、変数の線形結合(変数にそれぞれ係数を掛けて足したもの)から目標値を引いたもの、という形をしている

つまり、変数をうまく選んで、各項の線形結合を目標値にできるだけ近づけることを目指します。近さの測り方として、差をそのまま足すのではなく、差を二乗してから足し合わせる点が名前の由来です。二乗するので、プラス方向のずれもマイナス方向のずれも同じように大きさとして数えられます。

行列とベクトルで見た形

教科書では、この問題を行列とベクトルで整理しています。

• 行列Aの各行は、それぞれの項の係数を並べたベクトル(係数ベクトル)である
• ベクトルxが最適化の変数、つまり求めたい値である
• 行列Aは、列の数より行の数が多い

行の数は項の数、列の数は変数の数に当たります。行が列より多いということは、求めたい変数の数よりも、近づけたい目標(項)の数のほうが多い状況を表しています。すべての目標をぴったり満たすことは一般にできないので、差の二乗の合計が最も小さくなるところを答えとして選ぶ、という考え方になります。

解き方: 連立一次方程式に帰着する

最小二乗問題の大きな特徴は、解くことが連立一次方程式を解くことに帰着できる点です。そのため、解を式の形で直接書き表せる解析的な解が存在します。教科書が示す解は、言葉で言えば次のとおりです。

• 行列Aの転置とA自身との積をつくり、その逆行列を求める
• 行列Aの転置と、目標値を並べたベクトルbとの積をつくる
• 前者の逆行列に後者を掛けたものが解xになる

このように、繰り返し少しずつ答えに近づけるのではなく、決まった手順の計算で答えが一つ求まります。

計算の信頼性と速さ

教科書は、最小二乗問題には高い精度で、非常に高い信頼性をもって解ける優れたアルゴリズムとソフトウェアの実装がそろっていると述べています。

計算にかかる時間についても見通しが立ちます。所要時間はおおよそ、変数の数の二乗に項の数を掛けたものに比例し、その比例の定数も分かっています。変数の数が増えると時間は二乗で増え、項の数が増えると比例して増える、ということです。教科書の執筆当時のデスクトップコンピュータでも、変数が数百、項が数千ある問題を数秒で解けると紹介されています。

特別な構造を使うとさらに大きな問題も解ける

行列Aが特別な構造を持っている場合、それを利用すると、さらに大きな最小二乗問題も解けることが多いとされています。例として挙げられているのが疎な行列です。

疎な行列とは、成分の総数に比べて、ゼロでない成分がずっと少ない行列のことです。ほとんどの成分がゼロであれば、その性質を利用することで、通常はかなり速く最小二乗問題を解けます。

ほかの考え方との関係

変数(パラメータ)の値をデータに当てはめる考え方は最小二乗法だけではなく、たとえば最尤法のような別の考え方もあります。最小二乗法は、差の二乗の合計を最小にするという目的のはっきりした問題設定と、連立一次方程式に帰着して確実に解けるという扱いやすさを持つ点が特徴です。