ソフトウェアエンジニアが Cousera の機械学習コーシ（1週目）に参加して学んだことをメモ代わりに共有します。今回は機械学習の導入の授業でした。改めてなんとなく理解していた機械学習を、体系的に学べるのでワクワクしました。ほとんど数学です。
introduction
下記のオンライン授業を受けた内容です。無料なので興味がある人は受けてみると良いと思います。
What is Machine Learning?
硬い話になりますが、機械学習には主に2つの定義があります。一つは「機械学習をコンピュータに明示的にプログラムすることなく学習する能力を与える研究分野」です。もう一つは、「コンピュータ・プログラムは、ある課題 T について、 ある性能基準 P に基づき、もし T についての性能が基準 P で測定して、経験 E と共に改善している場合に、 経験 E から学習したと言うことが出来る」です。後者は少しわかりにくいので、の「 Gmail のスパム判定」を具体例として示します。「電子メールをスパムと非スパムに仕分ける」が課題 T 。「ユーザーがスパムと非スパムにラベル分けするのを見る」は経験 E 。「正しく分類された電子メールの比率」は 性能基準 P となります。
また、機械学習とは後述の4つに分類できます。「教師あり学習」、「 教師なし学習」、「 強化学習」、「 レコメンダーシステム」です。特に「教師あり学習」、「 教師なし学習」が重要で、本コースでもこの2つを重点的に学びます。
最後にこの節のサマリーを載せておきます。
Two definitions of Machine Learning are offered.
Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition.
Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.”
Example: playing checkers.
E = the experience of playing many games of checkers
T = the task of playing checkers.
P = the probability that the program will win the next game.In general, any machine learning problem can be assigned to one of two broad classifications: Supervised learning and Unsupervised learning.
Supervised Learning
この節では「教師あり学習」が何かを説明します。「教師あり学習」という言葉の由来は、アルゴリズムに与えたデータセットには 「正しい答え」が与えられていたことにあります。
「教師あり学習」の一つに、回帰問題(regression problem)と呼ばれるものがあります。回帰という言葉は、一種の連続値的な属性の値を 予測しようとしていることを指しています。回帰を使う場合に重要なのは、目的とする結果が連続値の予測であるということです。また、「教師あり学習」には、分類問題(classification problem)のと呼ばれるものもあります。 分類という言葉は、目的とする結果が離散値の予測であるということです。「0 か 1」や「悪性か良性」であることを指します。連続値と離散値の違いの説明は下記の記事に譲ります。
最後にこの節のサマリーを載せておきます。
In supervised learning, we are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output.
Supervised learning problems are categorized into “regression” and “classification” problems. In a regression problem, we are trying to predict results within a continuous output, meaning that we are trying to map input variables to some continuous function. In a classification problem, we are instead trying to predict results in a discrete output. In other words, we are trying to map input variables into discrete categories.
Example 1:
Given data about the size of houses on the real estate market, try to predict their price. Price as a function of size is a continuous output, so this is a regression problem.
We could turn this example into a classification problem by instead making our output about whether the house “sells for more or less than the asking price.” Here we are classifying the houses based on price into two discrete categories.Example 2:
(a) Regression — Given a picture of a person, we have to predict their age on the basis of the given picture
(b) Classification — Given a patient with a tumor, we have to predict whether the tumor is malignant or benign.
Unsupervised Learning
この節では「教師なし学習」が何かを説明します。「教師なし学習」で与えられるデータは、ラベル付けされていないか、全て同じ ラベルか、あるいはラベルがそもそもありません。「教師なし学習」のアルゴリズムは こうしたデータを二つの別々のクラスターに分けたりします。簡単に説明すると、データセット内のサンプルに対して正解を与えていないため これは「教師なし学習」です。
「教師なし学習」の殆どはクラスタリングアルゴリズムと呼ばれものに分類されます。読んで字のごとくクラスターに分けてくれます。また、別のものとして、カクテルパーティーアルゴリズムというものもあります。これは簡単に説明すると、重複している音声を分離して、聞こえやすくしてくれます。下記にカクテルパーティーアルゴリズムの例を示しておきます。
最後にこの節のサマリーを載せておきます。
Unsupervised learning allows us to approach problems with little or no idea what our results should look like. We can derive structure from data where we don’t necessarily know the effect of the variables.
We can derive this structure by clustering the data based on relationships among the variables in the data.
With unsupervised learning there is no feedback based on the prediction results.
Example:Clustering: Take a collection of 1,000,000 different genes, and find a way to automatically group these genes into groups that are somehow similar or related by different variables, such as lifespan, location, roles, and so on.
Non-clustering: The “Cocktail Party Algorithm”, allows you to find structure in a chaotic environment. (i.e. identifying individual voices and music from a mesh of sounds at a cocktail party https://en.wikipedia.org/wiki/Cocktail_party_effect).
Model and Cost Function
ここから徐々に数学的な内容に変わっていきます。
model
モデルとはインプットを計算してアウトプットへ変換してくれる関数のことです。慣例的に Hypothesis の頭文字を使って h(x) で表現されます。この h(x) を導き出すためにデータセットを使います。ここでデータセットに関する変数を定義します。まず、m はデータセットの数を表します。次に x は入力変数を表します。これはよく 特徴とも言われます。最後に y は予測する出力変数、目標変数を表します。
h(x) は高次関数であったり、複数の変数を持つことが考えられます。しかし、簡略化のために以降この記事では、一つの変数かつ線形回帰である単回帰（Univariate linear regression）であることを想定して話を進めます。単回帰は下記の等式で表すことができます。
h(x) = θ0 + θ1*x
最初に 線形関数に当てはめ、いずれはこれを発展させてもっと複雑な モデル、もっと複雑な学習アルゴリズムにしていきます。
最後にこの節のサマリーを載せておきます。
To establish notation for future use, we’ll use x(i) to denote the “input” variables (living area in this example), also called input features, and y(i) to denote the “output” or target variable that we are trying to predict (price). A pair (x(i),y(i)) is called a training example, and the dataset that we’ll be using to learn — a list of m training examples (x(i),y(i));i=1,…,m — is called a training set. Note that the superscript “(i)” in the notation is simply an index into the training set, and has nothing to do with exponentiation. We will also use X to denote the space of input values, and Y to denote the space of output values. In this example, X = Y = ℝ.
To describe the supervised learning problem slightly more formally, our goal is, given a training set, to learn a function h : X → Y so that h(x) is a “good” predictor for the corresponding value of y. For historical reasons, this function h is called a hypothesis. Seen pictorially, the process is therefore like this:
When the target variable that we’re trying to predict is continuous, such as in our housing example, we call the learning problem a regression problem. When y can take on only a small number of discrete values (such as if, given the living area, we wanted to predict if a dwelling is a house or an apartment, say), we call it a classification problem.
Cost Function
モデルの評価には、目的関数というものを定義します。これは、 データに対し、どのように最適な直線を当てはめるか算出する為に役に立ちます。一般的に線形回帰の目的関数は、i = 1 から m までの差の二乗の総和を行った関数を使います。この目的関数は、二乗誤差関数（Square error function）と呼ばれたり、時には、 二乗誤差目的関数と呼ばれることもあります。
今回は平均二乗誤差を使っています。更に計算の簡略化のために 1/2 をかけています。結局最小値を探せば良いので、どんな定数を掛け合わせてもθ0, θ1 には影響が出ません。平均二乗誤差については下記の記事に説明を譲ります。
この状態で出てきている線形回帰に関する数式を整理しておきます。
最後にこの節のサマリーを載せておきます。
We can measure the accuracy of our hypothesis function by using a cost function. This takes an average difference (actually a fancier version of an average) of all the results of the hypothesis with inputs from x’s and the actual output y’s.
This function is otherwise called the “Squared error function”, or “Mean squared error”. The mean is halved (1/2) as a convenience for the computation of the gradient descent, as the derivative term of the square function will cancel out the 1/2 term. The following image summarizes what the cost function does:
Parameter Learning
数学的な局所的最小値や微分など懐かしい言葉たくさん出てきます。
Gradient Descent
この節では、目的関数 J を最小化する、最急降下法(Gradient Descent)というアルゴリズムについて説明します。最急降下法はより汎用的なアルゴリズムで、線形回帰以外でも使われます。実際には機械学習では至るところで使われています。
詳細な説明は上記の記事に譲りますが、簡単に言うとグラフの勾配を利用して、局所的最小値を導き出す方法です。ただ、最急降下法はあくまでも局所的最小値を導き出すだけで、全体の最小値を導き出すだす保証がありません。
ただ、線形回帰の目的関数は、いつも弓形の関数で一つの局所的最小値、つまり全体的の最小値を持つことが分かっています。 これを表す専門用語があって、それは凸型関数(convex)と呼ばれます。
上記の関数が最急降下法アルゴリズムで、この関数が収束するような θ0, θ1 を探し出します。注意点として := は等号ではありません。これの意味はプログラミングで言う代入を表します。また、α は学習率と呼ばれ、大きすぎると値が収束せずに発散していまい、小さすぎると計算に時間がかかります。α 以降の数式は導関数と呼ばれ、偏微分を表します。偏微分については下記の記事に説明を譲ります。
最後にこの節のサマリーを載せておきます。
So we have our hypothesis function and we have a way of measuring how well it fits into the data. Now we need to estimate the parameters in the hypothesis function. That’s where gradient descent comes in.
Imagine that we graph our hypothesis function based on its fields θ0 and θ1 (actually we are graphing the cost function as a function of the parameter estimates). We are not graphing x and y itself, but the parameter range of our hypothesis function and the cost resulting from selecting a particular set of parameters.
We put θ0 on the x axis and θ1 on the y axis, with the cost function on the vertical z axis. The points on our graph will be the result of the cost function using our hypothesis with those specific theta parameters. The graph below depicts such a setup.
We will know that we have succeeded when our cost function is at the very bottom of the pits in our graph, i.e. when its value is the minimum. The red arrows show the minimum points in the graph.
The way we do this is by taking the derivative (the tangential line to a function) of our cost function. The slope of the tangent is the derivative at that point and it will give us a direction to move towards. We make steps down the cost function in the direction with the steepest descent. The size of each step is determined by the parameter α, which is called the learning rate.
For example, the distance between each ‘star’ in the graph above represents a step determined by our parameter α. A smaller α would result in a smaller step and a larger α results in a larger step. The direction in which the step is taken is determined by the partial derivative of J(θ0,θ1). Depending on where one starts on the graph, one could end up at different points. The image above shows us two different starting points that end up in two different places.
The gradient descent algorithm is:
repeat until convergence:
where
j=0,1 represents the feature index number.
At each iteration j, one should simultaneously update the parameters θ1,θ2,…,θn. Updating a specific parameter prior to calculating another one on the j(th) iteration would yield to a wrong implementation.
Gradient Descent For Linear Regression
今まで導き出した線形回帰の数式と、最急降下法アルゴリズムの数式を組み合わせると、下記の数式を導くことができます。これを解くことで目的の θ0, θ1 を導くことができます。
最後にこの節のサマリーを載せておきます。
When specifically applied to the case of linear regression, a new form of the gradient descent equation can be derived. We can substitute our actual cost function and our actual hypothesis function and modify the equation to :
where m is the size of the training set, θ0 a constant that will be changing simultaneously with θ1 and xi,yi are values of the given training set (data).
The point of all this is that if we start with a guess for our hypothesis and then repeatedly apply these gradient descent equations, our hypothesis will become more and more accurate.
So, this is simply gradient descent on the original cost function J. This method looks at every example in the entire training set on every step, and is called batch gradient descent. Note that, while gradient descent can be susceptible to local minima in general, the optimization problem we have posed here for linear regression has only one global, and no other local, optima; thus gradient descent always converges (assuming the learning rate α is not too large) to the global minimum. Indeed, J is a convex quadratic function. Here is an example of gradient descent as it is run to minimize a quadratic function.
The ellipses shown above are the contours of a quadratic function. Also shown is the trajectory taken by gradient descent, which was initialized at (48,30). The x’s in the figure (joined by straight lines) mark the successive values of θ that gradient descent went through as it converged to its minimum.