「Coursera – 機械学習コース」の個人的なメモ (Week 1 – 3)

数週間前から、Couseraの機械学習を受講しています。まだ途中です。しばらくしたら忘れかけていたので、少しずつ復習しつつ書き進めていきます。本記事はWeek 1-3についてです。Week 4-はこちら
機械学習でよく使われる共通の?表記について

  • \(m\): 学習サンプルの数
  • \(n\): 特徴量の数
  • \(x\): 入力特徴量(スカラーに限らず)
  • \(y\): 出力特徴量(スカラーに限らず)
  • \(h_\theta(x)\): Hypothesis Function – 結果を予測するための関数
  • \(\theta_i\): パラメータ
  • \(J(\theta)\): コスト関数、目的関数 – 最小化すべき関数。
  • \(\underset{\theta_1, \theta_2}{\rm minimize}J(\theta_1, \theta_2)\): \(J(\theta_1, \theta_2)\)を最小化するための\(\theta_1, \theta_2\)を求める、という意味。

線形回帰

これは、機械学習にかぎらずよく使われるが、

$$
h_\theta(x) = \theta_0 + x\theta_1
$$
$$
J(\theta_0,\theta_1)=\frac{1}{2m}\sum_{i=1}^m \left(h_\theta (x^{(i)}) – y^{(i)}\right)^2
$$

と定義される。誤差の二乗和を最小化すれば良い。より一般化された表記をすると、

$$
h_\theta(x) = \theta^T x
$$
ここで、
$$
\theta = \left(
\begin{array}{c}
\theta_0 \\
\theta_1
\end{array}
\right), \
x = \left(
\begin{array}{c}
x_0 \\
x_1
\end{array}
\right)
$$

ただし\(x_0=1\)と表せる。行列の記法になれることで、高級言語を用いてコーディングするときに遅いforループを回さずに書け、高速にプログラムを動かすことができる。

これを発展させて特徴量を増やしたい場合や、線形でなく多項式近似をする場合でも、
$$x = \left(
\begin{array}{c}
1 \\
x_1 \\
x_2
\end{array}
\right),\
x = \left(
\begin{array}{c}
1 \\
x \\
x^2
\end{array}
\right)
$$
などとするだけでよい。

アルゴリズム

以下2種類のアルゴリズムが紹介されている。

最急降下法

山を下る際に、勾配をとって、勾配を下る方向に勾配に比例した一定距離進む、ということを繰り返し、\(\theta\)を更新してゆく手法。今回定義されているコスト関数\(J\)は凸関数であるため、鞍点や局所解が存在しないため、この手法が使える。式にすると、
$$
\begin{eqnarray}
\theta_j &:=& \theta_j – \alpha \frac{\partial}{\partial \theta_j}J(\theta) \\
&=& \theta_j – \alpha \frac{1}{m}\sum_{i=1}^m \left(h_\theta (x^{(i)}) – y^{(i)}\right)x^{(i)}\\
\end{eqnarray}
$$
となる。想像するとわかるが、解付近で\(\theta_i\)微分値が等方的であれば最適解方向へ向かって値が更新されるが、一方に伸びたような形であると、曲線を描いていく、つまり、最適解への経路が長くなり反復回数が増えてしまう。

この事実からわかることは、学習データの特徴量ごとのオーダーがかけ離れすぎていると、解への収束が遅くなってしまうということである。これは普通の関数のフィッティングにも同じことが言えるので、規格化を最初に行うことが大切、ということである。

さらに、\(\alpha\)は学習率と呼ばれる。式からわかるように、大きいと解へ向かう速度は大きくなるものの、大きすぎると1ステップで解を乗り越えて振動、あるいは発散してしまうことになる。一方、小さすぎると、解へ向かっていくものの、収束に多くのステップが必要とされる。

解析的手法

同様に、今回定義されているコスト関数\(J\)は凸関数であるため、解析的に\(J\)を最小化できる。最小値において\(\frac{\partial J(\theta_i)}{\partial \theta_i}\)がすべての\(i\)に対して\(0\)になるというのをとけばよく、その結果を行列表現すると
$$
\theta = (X^TX)^{-1}X^Ty
$$
となる。ここで、\(X\)は、Design Matrixと呼ばれ、
$$
X = \left(
\begin{array}{c}
x^{(1)} \\
x^{(2)} \\
\vdots \\
x^{(m)}
\end{array}
\right) =
\left(
\begin{array}{cccc}
x_0^{(1)} & x_1^{(1)} & \ldots & x_n^{(1)} \\
x_0^{(2)} & x_1^{(2)} & \ldots & x_n^{(2)}\\
\vdots & \vdots & \ddots & \vdots\\
x_0^{(m)} & x_1^{(m)} & \ldots & x_n^{(m)}
\end{array}
\right)
$$
と定義された行列である。
そもそも厳密解があるのにどうして最急降下法をやって反復させる必要があるの?と思っていたが、実は厳密解をコンピューターで導出する際、学習データ数\(m\)のオーダーが大きい場合、コンピューターで厳密解を求める際、\( (X^TX)^{-1}\)の計算をするのに異常に時間が(\(O(n^3)\)のオーダーで)かかってしまうそうだ。一方で最急降下法は\(m\)が大きくなっても計算量の増加はそこまで大きくない。よって、\(m\)が大きい場合は厳密解が、\(m\)が一定以上のときには、最急降下法が用いられるそうである。

\( (X^TX)^{-1}\)が存在しない場合は、比例関係にある特徴量が存在するということなので、次元削減すればよい。講義ではムーア-ペンローズの擬似逆行列(Octaveではpinv関数)というものが使うことで解決していた。

CG法等

実際はCG法等の行列解法を用いるのが早い。その詳細についてはいつかどこかで記事にするかもしれない。

線形回帰の発展形

線形回帰と同様のアルゴリズムで、多項式回帰等を行えることは上述の通りだが、特徴量(項数・次数含む)を増やせば増やすほど、上図のように、データに対して過剰にフィットされ、コスト関数\(J\)はより小さくできるものの、予測性能を失い本質的な意味を持たなくなってしまう。これを過学習という。これを抑制するには、特徴量をできるだけ減らせば良いが、どれが重要な特徴量かわからなければそれができない。そういうときには、\(J\)を細工して、
$$
J(\theta_0,\theta_1)=\frac{1}{2m}\left[\sum_{i=1}^m \left(h_\theta (x^{(i)}) – y^{(i)}\right)^2 + \lambda\sum_{j=1}^n \theta_j^2\right]
$$

と\(\lambda\sum_{j=1}^n \theta_j^2\)により、\(\theta\)の二乗和が小さいほうが特になるようにすれば、意味のない特徴量の\(\theta\)が\(0\)に近づき意味のある特徴量だけが有効に働くよう、次元削減に似たような効果を発揮する。ここで、\(\theta_0\)は定数項であり、これも最小化してしまうとゼロに近づこうとしてしまい、意味が無いため除外される。この\(\lambda\)は正規化パラメータ(Regularization Parameter)と呼ばれる。正規化パラメータが大きすぎれば、underfittingな状態となってしまい、一方で小さすぎるとoverfittingされるため、適切な値を選択する必要がある。

ロジスティック回帰

ロジスティック回帰は、回帰という名前がついているものの、分類問題の予測を行うものである。ただ、やっていることは線形回帰とあまり変わらない。AとBの2種類の分類を幾つかの特徴量で行うとき、最初に考えられるのはAを0、Bを1として線形回帰を行う、という方法である。しかしそうしてしまうと、直線というのは\([0,1]\)に収まるものではないので正しそうな答えが得られる条件は非常に限られる。そこで、\([0,1]\)に収まる関数に入れてしまえばよいということで、シグモイド関数\(g(x)=\frac{1}{1+e^{-x}}\)を利用し、Hypothesis Functionを
$$
h_\theta(x)=g(\theta^T x)
$$
とすることで対応する。これは、分類問題において1である確率であるとされ、0である確率は\(1-h_\theta(x)\)となる。イメージは分かるが、統計的理由は知らない。今回はそういうものだとしてスルーする。

決定境界

2種分類問題で、決定境界となるのは、確率が\(0.5\)となる線である。その線は、\(h_\theta(x)=\frac{1}{1+e^{-\theta^T x}}=0.5\)の解、つまり\(\theta^T x\)である。\(x\)の0次と1次のみの特徴量を利用する場合は、この決定境界は直線となり、境界線が直線で描ける問題しか解くことができないが、線形回帰の発展のときと同様に、特徴量の二乗も特徴量として追加してあげれば、楕円や円などの境界も描けるようになる。

コスト関数

ロジスティック回帰においてコスト関数をどう定義するかを考える。まず最初に思いつくのは、線形回帰と同様の誤差二乗和\(\sum_i\left(y_i-h_\theta(x_i)\right)^2\)である。
$$
\begin{eqnarray}
&&\sum_{i=1}^m \left(y_i-h_\theta(x_i)\right)^2\\
&&\sum_{i=1}^m = \left(y_i-\frac{1}{1+e^{\theta^Tx_i}}\right)^2
\end{eqnarray}
$$
しかし、

  • この関数は凸関数にならず、局所解をたくさんもつことになってしまい、大域解を得るのは難しくなってしまう
  • \(h_\theta (x)\)を「確率」と解釈するのであれば、ペナルティの与え方がおかしい。(0%と予想したものになった場合のペナルティは無限に発散しないとおかしいのでは?)

といった問題がある。

それらを解決するコスト関数は以下に定義される。

$$
\begin{eqnarray}
J(\theta) = \dfrac{1}{m} \sum_{i=1}^m \mathrm{Cost}(h_\theta(x^{(i)}),y^{(i)})\\
\mathrm{Cost}(h_\theta(x),y) = \begin{cases}
-\log(h_\theta(x)) & \text{if} \ y = 1\\
-\log(1-h_\theta(x)) & \text{if} \ y = 0
\end{cases}
\end{eqnarray}
$$
と表せる。これはどのような関数になっているかをみてみると、

  • \(y=1\)のとき
    • \(h_\theta(x) \to 1\)で\(\mathrm{Cost}(h_\theta(x),y) \to 0\)になる。
    • \(h_\theta(x) \to 0\)で\(\mathrm{Cost}(h_\theta(x),y) \to \infty\)になる。
  • \(y=0\)のとき
    • \(h_\theta(x) \to 0\)で\(\mathrm{Cost}(h_\theta(x),y) \to \infty\)になる。
    • \(h_\theta(x) \to 1\)で\(\mathrm{Cost}(h_\theta(x),y) \to 0\)になる。

完全に異なっていれば(つまり確率が0にも関わらず生じているということなので)無限のペナルティが与えられ、同一であればペナルティがない、というものである。

一つの式にまとめ、行列表現をすると以下のようになる。
$$
J(\theta) = \frac{1}{m} \cdot \left(-y^{T}\log(h)-(1-y)^{T}\log(1-h)\right)
$$
ただし\(h = \frac{1}{1+e^{X \theta}}\)の列ベクトルである。
では実際に最急降下法を行うために微分値を求めてみると、
$$
\frac{1}{m} X^{T} \left(\frac{1}{1+e^{X \theta}} – y\right)
$$
となるので、これを用いて同様に最急降下法を適用すればよい。

時々思うこと

頭で考えたことを書きなぐっているだけなので、論理性も文の流れもなにもありません。ただ残しておくためだけのメモです。

  • 個人的に、ロジスティック回帰における\(h_\theta(x)\)を「確率」と言ってしまうのはどうなの?統計的な根拠なく、「確率」と呼んでいるのか?と思って機械学習をやっている先輩に聞いてみたら、「ベイズ統計をやればわかるよ」と言っていました。こういう細かいことを気にするのは、機械学習の概要を把握し終えてからにしようと思います。
  • そもそも曲線へのフィッティングへのモデルもなくフィッティングして傾向を掴んでも、それが正しいという根拠がないと思う。とはいえ、現象を解明するための物理モデルが作れないほどの複雑系に対してモデル化等到底ムリな場合がある。そうであれば統計解析すれば?とも思う。根拠なく得たフィッティング式になんの意味があるのか、おそらく勉強を進めていけばわかってくることのようにも思う。
  • まだ勉強していないが、画像認識における次元削減なんかがいい例である。個々のピクセルに対する演算に物理的モデルなど適用しようがないが、関数へのフィッティングを繰り返すことで大幅に次元削減ができる。乱数によって作った画像が、自然界に存在するような画像ができる確率を考えれば、自然界に存在するための基底の数など画像のピクセル数に対しては圧倒的に小さくなる。