COUSERA Machine Learning Week03

ソフトウェアエンジニアが Cousera の機械学習コーシ（3週目）に参加して学んだことをメモ代わりに共有します。今回から分類の問題を解いていきます。分類問題が分かると色々応用ができそうでテンションが上りました。

Photo by Joshua Reddekopp on Unsplash

2週目の記事もあるので良かったら読んでみてください。

COUSERA Machine Learning Week02

Classification and Representation

この章では分類問題についてと、その解法の導入を説明します。

Classification

先週までは、機械学習を使って回帰問題を解いてきました。今週からは、教師あり学習の分類問題を扱って行きます。第一週でも説明しましたが、分類問題は O（まる） X（ばつ）のような結果を持つ機械学習の問題です。この O（まる） X（ばつ）を y の 1 と 0 に当てはめて、数学として扱います。ここで、前回までのように線形回帰を使って、0.5 を境界線として、1 と 0 を判定するというような方法も考えられます。しかし、これはデータセット（x 軸）の幅が大きくなればなるほど、精度が悪くなってしまいます。なので、分類問題の問題では、ロジスティック回帰（Logistic regression）という解法を使って解きます。以降は、簡略化のために、1 と 0 のみを判定する分類問題（Binary classification problem）を扱います。

最後にこの節のサマリーを載せておきます。

To attempt classification, one method is to use linear regression and map all predictions greater than 0.5 as a 1 and all less than 0.5 as a 0. However, this method doesn’t work well because classification is not actually a linear function.

The classification problem is just like the regression problem, except that the values we now want to predict take on only a small number of discrete values. For now, we will focus on the binary classification problem in which y can take on only two values, 0 and 1. (Most of what we say here will also generalize to the multiple-class case.) For instance, if we are trying to build a spam classifier for email, then (i) may be some features of a piece of email, and y may be 1 if it is a piece of spam mail, and 0 otherwise. Hence, y∈{0,1}. 0 is also called the negative class, and 1 the positive class, and they are sometimes also denoted by the symbols “-” and “+.” Given x(i), the corresponding y(i) is also called the label for the training example.

Hypothesis Representation

この節では、ロジスティック回帰に使われるモデルを説明します。下記がロジスティック回帰のモデルです。

基本的には線形回帰の時のモデルと似ていますが、g(z) て定義されている関数が追加されています。この g(z) の関数の形が下記のです。この関数は、sigmoid 関数やロジスティック関数と呼ばれています。

この g(z) は負の側に無限に 小さくなっていく場合は 0 に近づき、正の側に無限に 大きくなっていく場合は1に近づく特性を持っています。この特性を活かして、0 から 1 の値を導出し、確率で 0 と 1 を判定するのが分類問題の解き方です。

最後にこの節のサマリーを載せておきます。

We could approach the classification problem ignoring the fact that y is discrete-valued, and use our old linear regression algorithm to try to predict y given x. However, it is easy to construct examples where this method performs very poorly. Intuitively, it also doesn’t make sense for hθ​(x) to take values larger than 1 or smaller than 0 when we know that y ∈ {0, 1}. To fix this, let’s change the form for our hypotheses hθ​(x) to satisfy 0≤hθ​(x)≤1. This is accomplished by plugging θTx into the Logistic Function.

Our new form uses the “Sigmoid Function,” also called the “Logistic Function”:

The following image shows us what the sigmoid function looks like:

The function g(z), shown here, maps any real number to the (0, 1) interval, making it useful for transforming an arbitrary-valued function into a function better suited for classification.

hθ​(x) will give us the probability that our output is 1. For example, hθ​(x)=0.7 gives us a probability of 70% that our output is 1. Our probability that our prediction is 0 is just the complement of our probability that it is 1 (e.g. if probability that it is 1 is 70%, then the probability that it is 0 is 30%).

Decision Boundary

この節では、決定境界（Decision boundary）について説明します。決定境界とは、ロジスティック回帰の結果を、0 と判定するか、1 と判定するかかの境界線のことです。

まずは、ロジスティック回帰のモデルは 0 < h(x) <1 の範囲内の値であるから、h(x) が 0.5 以上の場合は y=1 と判定し、h(x) が 0.5 未満の場合は y=0 と判定します。そして、前節で説明した通り、ロジスティック関数 g(z) は z が正の値か負の値かで、その結果が 0.5 以上になるか、未満になるかが別れます。

z の値は上記のように定義されているので、決定境界の数式は下記のように表すことができます。

最後にこの節のサマリーを載せておきます。

In order to get our discrete 0 or 1 classification, we can translate the output of the hypothesis function as follows:

The way our logistic function g behaves is that when its input is greater than or equal to zero, its output is greater than or equal to 0.5:

Remember.

So if our input to g is θTX, then that means:

From these statements we can now say:

The decision boundary is the line that separates the area where y = 0 and where y = 1. It is created by our hypothesis function.

Logistic Regression Model

この章では、ロジスティック回帰をどのように評価して、解いていくかを説明します。

Cost Function

この節では、ロジスティック回帰で使うコスト関数について説明します。線形回帰で使ったコスト関数を、ロジスティック回帰で使うと、下記のようなグラフになります。（めっちゃ雑ですが。。。）

このグラフの場合、最急降下法を使うとどの極小値になるか分からず、グローバルな極小値へ収束する保証が出来ません。このことから、コスト関数は凸関数（convex）である必要が分かります。なので、ロジスティック回帰のコスト関数を、凸関数にするために、下記のようにコスト関数を書き直します。

これは、下記のようなグラフになります。

グラフの勾配一定に小さくなるのが分かるので、これで最急降下法をつかて、θ を特定することができることが分かります。

最後にこの節のサマリーを載せておきます。

We cannot use the same cost function that we use for linear regression because the Logistic Function will cause the output to be wavy, causing many local optima. In other words, it will not be a convex function.
Instead, our cost function for logistic regression looks like:

When y = 1, we get the following plot for J(θ) vs hθ​(x):

Similarly, when y = 0, we get the following plot for J(θ) vs hθ​(x):

If our correct answer ‘y’ is 0, then the cost function will be 0 if our hypothesis function also outputs 0. If our hypothesis approaches 1, then the cost function will approach infinity.

If our correct answer ‘y’ is 1, then the cost function will be 0 if our hypothesis function outputs 1. If our hypothesis approaches 0, then the cost function will approach infinity.

Note that writing the cost function in this way guarantees that J(θ) is convex for logistic regression.

Simplified Cost Function and Gradient Descent

この節ではロジスティック回帰で θ を求めるために、最急降下法を導入します。まずは、前節でコスト関数が下記の数式で表されました。

y が常に 0 か 1 しか取らないということを利用して、この数式は下記の数式に書き換えることが出来ます。

この J(θ) に対して、最急降下法を適用させます。すると、先週の線形回帰の時に導出した数式と同じものが得られます。

授業内でもこの数式の導出する際の数学的な証明は省かれています。なので、僕も正しくこの数式の真価は理解できていません。ただ、最尤推定量という手法が用いられているようです。詳しい説明は下記の記事に譲ります。

最尤推定量とは？初めての人にもわかる解説 | AVILEN AI Trend

これだけ見ると、線形回帰とロジスティック回帰の最急降下法は全く同じに見えます。しかし、モデル(h(θ)) が異なるので、実際に解く数式は下記のようになります。また、ロジスティック回帰でも線形回帰と同様にフューチャースケーリングを使って、最急降下法の計算を早くすることが出来ます。

最後にこの節のサマリーを載せておきます。

We can compress our cost function’s two conditional cases into one case:

Cost(hθ​(x),y)=−ylog(hθ​(x))−(1−y)log(1−hθ​(x))

Notice that when y is equal to 1, then the second term (1−y)log(1−hθ​(x)) will be zero and will not affect the result. If y is equal to 0, then the first term −ylog(hθ​(x)) will be zero and will not affect the result.

We can fully write out our entire cost function as follows

A vectorized implementation is:

Gradient Descent
Remember that the general form of gradient descent is:

We can work out the derivative part using calculus to get:

Notice that this algorithm is identical to the one we used in linear regression. We still have to simultaneously update all values in theta.

A vectorized implementation is:

θ:=θ−α/m * XT(g(Xθ)−y​)

Advanced Optimization

この節では、最急降下法以外で θ を求める方法を説明します。最急降下法以外にも、共役勾配法、BFGS、そして L-BFGSなどの洗練された最適化アルゴリズムがあります。これら3つのアルゴリズムには多くの利点があります。一つには、これらのアルゴリズムはどれも学習率を自分で選ぶ必要がない点です。これらのアルゴリズムの中で、学習率を最適化してくれます。そのことにより、別の利点も得られます。それは、多くの場合で最急降下法よりもはるかに速く収束します。しかし、もちろん欠点もあります。主な欠点は勾配降下法よりもずっと複雑であることです。

なので、数値計算のエキスパートでも無い限りは、共役勾配法、L-BFGS，BFGSのアルゴリズムを 自前で実装すべきではないです。行列計算の時と同様に、これらのアルゴリズムも同様にソフトウェアライブラリを使うべきです。

Octave には fminunc という関数が用意されていて、これが難解なアルゴリズムをラップしてくれています。授業内でも、Andrew 氏が言及していますが、多くの場合で、アルゴリズムの内部ループが何をしているのか理解しないでも出来る計算処理を終わらせることが出来ます。おそらく、重要なのは、数学的に計算を理解することではなくて、それぞれの処理が何を行っているのかを理解することだと思います。

Octave 上で下記のようにコードを書くと、 fminunc を実行できます。一つはコスト関数の値と各 θ に対する偏微分の値を返す関数。もう一つは、実際に fminunc を実行する関数です。

最後にこの節のサマリーを載せておきます。

“Conjugate gradient”, “BFGS”, and “L-BFGS” are more sophisticated, faster ways to optimize θ that can be used instead of gradient descent. We suggest that you should not write these more sophisticated algorithms yourself (unless you are an expert in numerical computing) but use the libraries instead, as they’re already tested and highly optimized. Octave provides them.

We first need to provide a function that evaluates the following two functions for a given input value θ:

We can write a single function that returns both of these:

Then we can use octave’s “fminunc()” optimization algorithm along with the “optimset()” function that creates an object containing the options we want to send to “fminunc()”.

We give to the function “fminunc()” our cost function, our initial vector of theta values, and the “options” object that we created beforehand.

Multiclass Classification

この章では、0 と 1 だけでない分類問題の解き方を説明します。

One-vs-all

複数の分類問題ですが、基本的には2クラス分類問題の時の解法を応用して解くことが出来ます。それが、one vs all 分類と呼ばれるアルゴリズムです。このアルゴリズムでやる事は、トレーニングセットを持ってきて、これを三つの異なる、二択問題に変換する事です。つまり、三つの別個の 2クラス分類問題に変換します。

例えば、上記の3つのクラスに分類したいとします。そうすると、「Class 1 とそれ以外」、「Class 2とそれ以外」、「Class 3とそれ以外」の3つの2クラス分類問題として解きます。そして、得られた hθ(x) で最も確率が高いものをその x に対する分類とします。

最後にこの節のサマリーを載せておきます。

Now we will approach the classification of data when we have more than two categories. Instead of y = {0,1} we will expand our definition so that y = {0,1…n}.

Since y = {0,1…n}, we divide our problem into n+1 (+1 because the index starts at 0) binary classification problems; in each one, we predict the probability that ‘y’ is a member of one of our classes.

We are basically choosing one class and then lumping all the others into a single second class. We do this repeatedly, applying binary logistic regression to each case, and then use the hypothesis that returned the highest value as our prediction.

The following image shows how one could classify 3 classes:

To summarize:
Train a logistic regression classifier hθ​(x) for each class to predict the probability that y = i .To make a prediction on a new x, pick the class that maximizes hθ​(x)

Solving the Problem of Overfitting

この章では、オーバーフィッティングと呼ばれる問題を説明し、それの回避方法を説明します。

The Problem of Overfitting

この節では、オーバーフィッティングが何なのかというものを説明します。

上記のような家の特徴量と価格のデータセットがあったとします。この3つのモデル（グラフ）では、一番左のモデルは精度がイマイチであることが分かります。この精度がイマイチである状態を「アンダーフィッティング」または「ハイバイアスを持つ」とい言います。次に、真ん中はおそらく精度の良いモデルであると言えます。最後に、一番右のモデルはデータセットを全て満たすモデルになっています。しかし、特徴量にもよりますが、おそらく予測するモデルとしては不適切である言えます。例えば、横軸が平米数だとすると、平米数が 0 の時が、一番価格が高いことを表しています。これは明らかに間違いであると言えます。このように、トレーニングのデータセットには完璧に適合するが、予測するためには最適でないモデルを「オーバーフィッティング」と言います。一般的、多項式や特徴量が多いほどオーバーフィッティングになりやすいです。このオーバーフィッティングを避けるためには主に2つの方法があります。それが、「特徴量を減らす」と「パラメーターを正則化する」の2つです。次節で正規化について詳しく説明します。

最後にこの節のサマリーを載せておきます。

Consider the problem of predicting y from x ∈ R. The leftmost figure below shows the result of fitting a y = θ0​+θ1​x to a dataset. We see that the data doesn’t really lie on straight line, and so the fit is not very good.

Instead, if we had added an extra feature x² , and fit y = θ0​+θ1​x+θ2x² , then we obtain a slightly better fit to the data (See middle figure). Naively, it might seem that the more features we add, the better. However, there is also a danger in adding too many features: The rightmost figure is the result of fitting a 5th order polynomial y = ∑j=05​θj​xj. We see that even though the fitted curve passes through the data perfectly, we would not expect this to be a very good predictor of, say, housing prices (y) for different living areas (x). Without formally defining what these terms mean, we’ll say the figure on the left shows an instance of underfitting — in which the data clearly shows structure not captured by the model — and the figure on the right is an example of overfitting.

Underfitting, or high bias, is when the form of our hypothesis function h maps poorly to the trend of the data. It is usually caused by a function that is too simple or uses too few features. At the other extreme, overfitting, or high variance, is caused by a hypothesis function that fits the available data but does not generalize well to predict new data. It is usually caused by a complicated function that creates a lot of unnecessary curves and angles unrelated to the data.

This terminology is applied to both linear and logistic regression. There are two main options to address the issue of overfitting:

1) Reduce the number of features:
- Manually select which features to keep.
- Use a model selection algorithm (studied later in the course).

2) Regularization
- Keep all the features, but reduce the magnitude of parameters θj
- Regularization works well when we have a lot of slightly useful features.

Cost Function

この節では、正則化について説明します。前節で、オーバーフィッティングについて説明しました。そのオーバーフィッティングを避けるために使うのが正則化と言われる手法です。正則化をざっくり説明すると、モデルをシンプルにするということです。詳しい説明は下記の記事に譲ります。

機械学習における正則化の意味を分かりやすく説明する - Qiita

具体的に何をしているかというと、各パラメーターの二乗に正則化パラメーターと呼ばれるλを掛けて足し込んだコスト関数を計算します。それが下記の数式です。

このようにすることで、各パラメーターの影響度をあえて小さくしています。そうすることによって、極端なグラフの凸凹を減らし、モデルをシンプルに保つ働きをします。

あと、全然関係ないですが、正規化と正則化は異なるので注意したほうが良いです。僕はこれが別々のものだと気づかずにググっても、ピンとくるものに出会えませんでした。

正規化(Normalization)と正則化(Regularization) - Qiita

最後にこの節のサマリーを載せておきます。

If we have overfitting from our hypothesis function, we can reduce the weight that some of the terms in our function carry by increasing their cost.

Say we wanted to make the following function more quadratic:

θ0​+θ1​x+θ2​x²+θ3​x³+θ4​x⁴

We’ll want to eliminate the influence of θ3​x³ and θ4​x⁴ . Without actually getting rid of these features or changing the form of our hypothesis, we can instead modify our cost function:

We’ve added two extra terms at the end to inflate the cost of θ3​ and θ4​. Now, in order for the cost function to get close to zero, we will have to reduce the values of θ3​ and θ4​ to near zero. This will in turn greatly reduce the values of θ3​x³ and θ4​x⁴ in our hypothesis function. As a result, we see that the new hypothesis (depicted by the pink curve) looks like a quadratic function but fits the data better due to the extra small terms θ3​x³ and θ4​x⁴.

We could also regularize all of our theta parameters in a single summation as:

The λ, or lambda, is the regularization parameter. It determines how much the costs of our theta parameters are inflated.

Using the above cost function with the extra summation, we can smooth the output of our hypothesis function to reduce overfitting. If lambda is chosen to be too large, it may smooth out the function too much and cause underfitting. Hence, what would happen if λ=0 or is too small ?

Regularized Linear Regression

この節では、ロジスティック回帰の説明をする前に、線形回帰の最急降下法と正規方程式に、正則化を適用させる方法を説明します。

正則化では j=0 の θ には正則化パラメーターを掛けません。なので、最急降下法の場合は、j=0 の場合分けが必要です。その結果の数式が下記です。

このように書き表すことができ、j が 0 でない場合の数式を θj で項をまとめると、下記の数式を得ることが出来ます。

この数式は直感的に面白いことを表しています。それは、1−αλ/m​ の項が 1 より小さい値になることに起因します。α が十分に小さく、m が十分に大きいと、この項は 0.99 のような値を取ることが出来ます。そうすると、代入が繰り返されるうちに、θj は徐々に小さい値になります。これが、正則化の目的をよく表していると言えます。正則化は、各パラメーターにペナルティーを与え、パラメーターの影響度を下げることで、モデルをシンプルに保っています。このパラメーターの影響度を下げるということが、まさに 1−αλ/m​ の項が表現していると言えます。

一方、正規方程式で正則化を用いる場合は下記の数式になります。

λL の行列を足し込んで逆行列を得ると、正則化を用いた正規方程式を得られます。これは証明が難しく授業内でも省かれてしまいましたが、とてもおもしろい特性を持っているようです。それは、正規化パラメータ λ が 0 より大きい（イコールを含まない）場合は、この X^TX + λL の行列は必ず逆行列を持つようになるらしいです。下記に、正規方程式と正則化について説明しているリンクを共有しておきます。（僕はなんとなく程度にしかやっていることは理解できてないです）

最後にこの節のサマリーを載せておきます。

We can apply regularization to both linear regression and logistic regression. We will approach linear regression first.

Gradient Descent
We will modify our gradient descent function to separate out θ0​ from the rest of the parameters because we do not want to penalize θ0​

The term λ/m​*θj​ performs our regularization. With some manipulation our update rule can also be represented as:

The first term in the above equation, 1−αλ/m​ will always be less than 1. Intuitively you can see it as reducing the value of θj​ by some amount on every update. Notice that the second term is now exactly the same as it was before.

Normal Equation
Now let’s approach regularization using the alternate method of the non-iterative normal equation.

To add in regularization, the equation is the same as our original, except that we add another term inside the parentheses:

L is a matrix with 0 at the top left and 1’s down the diagonal, with 0’s everywhere else. It should have dimension (n+1)×(n+1). Intuitively, this is the identity matrix (though we are not including x0​), multiplied with a single real number λ.

Recall that if m < n, then X^TX is non-invertible. However, when we add the term λ⋅L, then X^TX + λ⋅L becomes invertible.

Regularized Logistic Regression

この節では、ロジスティック回帰へ正則化を適用させる方法を説明します。最急降下法を使う場合は、前節で説明した線形回帰の時と同じで、j=0 とそれ以外で数式を分けて行います。もちろん、モデル（h(x)）が異なるので、当てはめる数式は全く同じという訳ではありません。

次に、同様に fminunc を使う場合も j=0 とそれ以外で数式を分けて行います。ここら辺は場合分けがある程度に覚えておいて、後は課題の数式とプログラミングを見るほうが良いかもしれません。

最後にこの節のサマリーを載せておきます。

We can regularize logistic regression in a similar way that we regularize linear regression. As a result, we can avoid overfitting. The following image shows how the regularized function, displayed by the pink line, is less likely to overfit than the non-regularized function represented by the blue line:

Cost Function
Recall that our cost function for logistic regression was:

We can regularize this equation by adding a term to the end:

The second sum, ∑j=1n​θj²​ means to explicitly exclude the bias term, θ0​. I.e. the θ vector is indexed from 0 to n (holding n+1 values, θ0​ through θn​), and this sum explicitly skips θ0​, by running from 1 to n, skipping 0. Thus, when computing the equation, we should continuously update the two following equations:

最後に今週の分の宿題のコードを載せておきます。行列の計算には慣れてきたけど、図のプロットが難しいと感じています。

atsss/cousera_ml

4週目の記事もあるので良かったら読んでみてください。

COUSERA Machine Learning Week04