ニューラルネットワークが幅を効かせている昨今、線形モデルちゃんの地位は非常に低いです。
これはいけない。
「じゃあお前ら重回帰の最適化アルゴリズムわかんの？？？」
もちろん、モデルの表現力的な限界はあるわけですが、単純なモデルがゆえに解釈性・説明性が高く、まだまだ使い道のあるモデルと思います。それだけでなく、線形回帰モデルには、行列計算、最小二乗法、勾配法による最適化など、機械学習技術を学んでいく上でコアとなる要素が多く含まれています。
このように、機械学習の入門として最適なモデルなので、さらっと説明できるようになっておきましょう！
今回は、損失関数を微分して解析的にパラメータを求める方法について説明します。
定義式
目的変数\( y_i \)を、説明変数\( x_i = (x_1, \cdots, x_d) \)とパラメータ\(\ \theta = (\theta_1, \cdots, \theta_d) \)を用いて以下の関数\( f(x_i) \)で近似します((定数項が必要なので\( x_1 = 1 \)とします))。
\( f(x_i) = \sum_{j=1}^{d} \theta_j x_{i,j} \)
このように、パラメータの線形結合で近似するモデルを線形モデルと呼びます。
\( d \)は1つのデータ点の次元数、データ点の数は\( n \)としてます。
データ点全体を表す行列は\( X \)は\( n \)行\( d \)列になります。
よくある間違い
\( f(x_i) \)で\( y_i \)を近似しているので、理想的には行列表記で\( y = X \theta \)になります。さて、前前節の見出しの通りですが、ここから先は人類の99%は解き方がわかりません((大学進学率、文理比率、学生時代の怠惰などを勘案した結果))。
今回求めたいのは\( \theta \)なので、ギリギリ逆行列を知っている人は、「なんだ〜、\( \theta = X^{-1}y \)じゃないですか〜、Q☆E☆D☆」と思うかもしれないですが、全然違います。
逆行列は結構闇で、全部語るとこの記事には収まらないですが、必ず求められるわけではないということは覚えておく必要があります。
実は、もとの行列が正方行列(\( n \)行\(n\)列)であり、かつ、機械学習的にいうとすべてのデータ点同士が線形独立である場合にのみ、逆行列は計算できます。
しかし、そもそも正方行列であるという条件が、通常の機械学習に用いるデータで満たされることはないです。
だって、データ数\( n \)と特徴量の次元数\( d \)が一緒になることなんてありえないでしょ！
機械学習では、基本的には\( n > d \)だと思います。
\( y = X \theta \)は、高校数学の範囲でいう、多元連立一次方程式になります。
この場合、方程式の数\( n \)が、未知数の数\( d \)より多いため、すべての方程式を満たす解が見つからない場合があります（解なし、不能）。
高校数学では、二元連立一次方程式の解は二次元平面上の直線同士の交点として説明されます。
2つの直線の交点は必ず求まりますが、たまにクセ者の問題で3つ以上の直線が出て、交点が求まらない問題を見たことがあるかと思います((もちろん答えは「解なし」))。
一般的な機械学習の問題もこのパターンで、先程の\( y = X \theta \)も多くの場合、解なしになります。
つまり、すべてのデータ点について\( y = X \theta \)をぴったり成り立たせるパラメータ\(\ \theta = (\theta_1, \cdots, \theta_d) \)なんて存在しない、ということになります。
逆に、\( n < d \)の場合は、方程式の数\( n \)より未知数の数\( d \)のほうが多いということになりますので解が定まらず（不定）、また別の条件を付け加えて解くことになりますが、今回は省略。
損失関数
さて、じゃあぴったり満たす解が求まらないとするとどうするか。これには次善策があって、ずばりジャストは諦めて、近い値を求めます。
つまり、\( X \theta - y = 0\)になるのは無理だってわかったから、\( X \theta - y = 0.01\)とか、せめて近い値にしてくれ〜、誤差を少なくしてくれ〜ということです。
「ええーそんな適当でええんかい」と思うかもしれませんが、これが工学のよいところで実用上使えるレベルの値が求まればいいという考え方です。
そもそも、最初の定義式のところで「\( y_i \)を\( f(x_i) \)で近似します」とはっきり述べているので、端っから厳密解を求めるつもりなんてないんですね。
以上をまとめると、すべてのデータ点に対する誤差\( X \theta - y \)が最小となるようなパラメータ\(\ \theta \)を求めればよいうということがわかります。
そうすると誤差は以下の式で表されます。
\( L(\theta) = \frac{1}{2} \| X \theta - y \|^2 \)
プラスマイナスをそのまま足し合わせると打ち消し合ってしまうので、2乗しています。また、ベクトルの2乗なので絶対値がつきます。
これは平均二乗誤差（MSE, Mean Squared Error）と呼ばれます。
また、\( L(\theta) \)を一般的に損失関数と呼びます。
解き方
損失関数\( L(\theta) \)の最小値、つまり\( X \theta - y \)ができるだけ小さくなるような\( \theta \)を求めたいです。こういうときは、損失関数\( L(\theta) \)を\( \theta \)で微分し、傾きが0になる点を求めます。
\( \frac{\partial L(\theta)}{\partial \theta} = 0 \)
微分計算自体は、合成関数の微分、および絶対値の中身は\( \theta \)に関する一次式の微分と同様に扱えます。
ついでにその後の式変形もやってしまうと
\( \frac{\partial L(\theta)}{\partial \theta} = X^T X \theta - X^T y = 0 \)
\( X^T X \theta = X^T y \)
\( \theta = (X^T X)^{-1} X^T y \)
\( X^T X \theta = X^T y \)
\( \theta = (X^T X)^{-1} X^T y \)
となります。
よくある間違いであげた\( \theta = X^{-1}y \)とはそもそも別の式なんですね。
結局逆行列を計算してますが、\( (X^T X) \)は\( d \times n \)行列と\( n \times d \)行列の積で\( d \times d \)行列になっているので、正方行列であり、逆行列が定義できます。
後半の\( X^T y \)に関しても、\( d \times n \)行列と\( n \)次元ベクトルの積なので、\( d \)次元ベクトルになります。
したがって\( d \)次元の\( \theta \)が求まります。
計算量
コンピュータによる計算では、計算量というものを考慮する必要があります。読んで字のごとく、あるひとまとまりの計算（例えば行列同士の掛け算など）をするのに、どれだけの回数、計算（スカラー値に対する足し算や掛け算などの基本演算）をする必要があるのかを表す指標です。
行列の掛け算の場合、前の行列の行ベクトルと、後ろの行列の列ベクトルの内積を総当りで求める必要があります。
なので\( d \times n \)行列と\( n \times d \)行列の積では、\( d \times d \)回の内積計算が必要です。
また、内積計算自体も\( n \)個の要素同士を掛け算する必要があるため、全体で\( O(nd^2) \)の計算量が必要になります((計算量はランダウの記号を用いて表します))。
一般に\( O(n) \)だと線形時間で解けるためよいとされており、ひとつの変数に2乗、3乗とついてしまうと計算量が爆発的に増えてしまうため時間のかかるアルゴリズムとされます。
一般の機械学習では、\( n > d \)が多いはずなので、線形回帰モデルのケースでは、それほど致命的にならなそうです。
ただし、データによっては\( d \)が大きい場合もあるので、その際は別の解き方（次回）のほうが速い場合もあります。
0 件のコメント:
コメントを投稿