Coursera Machine Learning Course ノート

概要

CourseraのMachine Learning Courseを修了したので、受講しながら取っていたメモをここに記録しておこうと思います。
数式等は別途ノートを取っていたので、話しながら取ったメモ程度の内容となります。
※ 正確でない場合もあるのでそこはご了承ください。

Coursera ML. week 2.

Multivariate Linear Regression

• feature scalingのやり方
• 学習率αを大きくする場合、小さくする場合
• 正規方程式を使うべきか否か

Gradient Descent in Practice I - Feature Scaling

feature scalingの
featureの選択方法について。

特徴間でスケールが違いすぎると、最小値の探索に時間がかかる。
ng氏だと、大きくて -3 <= x <= 3。小さくて -1/3 <= x <= 1/3
という基準でやっているらしい。これに近かったら気にしないとのこと。

こういうときにfeature scalingの出番。

方法の1つはmaxで割ること。
理想的には全部の特徴を
-1 <= xi <= 1
に収めればよい。

もう1つの方法「Mean Normalization」を使えば、データの平均が0に近くなるように調整できる。

Gradient Descent in Practice II - Learning Rate

学習率αの選定について。
デバッグ法と、うまくいっているかどうかの確認方法。

ng氏は100回の繰り返しごとに得られたθを記録して、グラフにしてみているらしい。
より正確には、得られたθをコスト関数に入力した値をプロットしている。

自動収束判定もできる。
J(θ)が100回のイテレーションで0.001以上変化したら続けて、これ以下ならもう変化が止まったと見て打ち切る、とか。

ただ、閾値の選定が難しいので、プロットをみるのが確実。
ng氏もそうしている。

Features and Polynomial Regression

多項式回帰。
featureは自分で好きに決める。
多項式回帰ではfeature scalingがより重要。
3乗が効いてきたりするので。

hθ(x) = θ0 + x1θ1 + √x2θ2
というモデルがあったとして、xの取り得る範囲が0 ~ 1000とすると、
hθ(x) = θ0 + x1θ1 /　1000 + √x2θ2 / √1000
というようにしてθの係数が0~1になるようにしたほうがよい。

-> もっとも、自動的にモデルを選択するアルゴリズムもある。

Normal Equation

正規方程式。
1ステップで解析的に解く方法。
feature scalingは必要ない。

最急降下法と比較する。

最急降下法

• 学習率αを選定する必要がある。「Learning Rate」の回でもやったが、うまくいくかどうかは基本的にプロットを見ながら何回か試す必要がある。これが面倒。
• 沢山計算を繰り返す。
• 特徴数が多くなっても高速に動作させられる。

正規方程式

• 学習率αを選定する必要がない。
• 実装がシンプル。
• 繰り返しがなく、 基本的に実行すればうまくいっているか観察せずとも答えが出るので楽。
• 特徴数が多くなると逆行列を求めるのに非常に時間がかかる。特徴数をnとすると、大体O(n^3)のコストがかかる。具体的には、nが1000なら問題ない。ng氏はこれくらいなら正規方程式を使う。10000くらいから迷い始める。100000なら最急降下法を選ぶ、とのこと。ただし、ロジスティック回帰など正規方程式が使えない場合がある。

Normal Equation Noninvertibility

正規方程式と非可逆性。
逆行列が存在しない場合があるけど、稀だし、擬似逆行列が使える。

擬似逆行列を使う必要があるのは、主に非可逆な転置行列がある場合

• 特徴同士が線形に依存している場合。例えば、x1: サイズ(m), x2: サイズ(feet) のような場合
• m < nの場合。つまり、トレーニングセットが少なすぎて、特徴の数以下になってしまう場合。-> うまくいく場合もあるが、正規化や不要な特徴を削除したほうがよい。

Octave/Matlab Tutorial

Basic Operations

Octaveでプロトタイピングするのがおすすめ。他の言語は開発に時間がかかるので検証に適さない。

Control Statements: for, while, if statement

Octaveの制御文とモジュールの話。
内容は別でまとめた。

Vectorization

hθ(x) = Σn, j= 0, θjxj -> ベクトル化 -> θ^Tx
内積とみなせる。
もっと洗練された例、というのが難しい。

Programming Exercise 1: Linear Regression

• ex1.m, ex1multi.mは変更する必要なし

• 人口と収益のデータを持っている。
• ex1data1.txt
• 1列目: 人口, 2列目: 収益, (マイナスは損失)

Coursera ML. week 3.

Classification

ロジスティック回帰を使った分類問題。
例: スパムメールの分類
0, 1に分類する場合、見分けたい方を1にすることが多い。
0: negative class, 1: positive class.

字幕がよくわからなかったが、{0, 1}を分類する問題において、0.51が1に分類されちゃうことあるから微妙なときもあるようね、というような話をしてる?

Hypothesis Representation

0 <= hθ(x) <= 1
hθ(x) = g(θ^T x)

g(z)はシグモイド関数, ロジスティック関数と呼ばれる。
これがロジスティック回帰の語源。
g(z) = 1 / (1 + e^-z)

->
g(z) = 1 / (1 + e ^ -(θ^T x))x

分類問題では
hθ(x): xに対してy = 1になる確率
例えば、
hθ(x): 0.7 -> 70%の確率で1に分類される。
P(y = 1 | x;θ )と書く。

Decision Boundary

ロジスティック回帰の続き。
予測は
y = 1: hθ(x) >= 0.5
y = 0: hθ(x) < 0.5
とする。
※ 0.5の場合はy = 1, 0どちらでもよい。
hθ(x)はシグモイド関数

シグモイド関数はz >= 0のときg(z) >= 0.5となるので、
g(θ^Tx) >= 0.5というのは、つまりθ^Tx >= 0ということになる。

Cost Function

ロジスティック回帰のCost Functionについて。
Cost(hθ(x), y) =
y = 1: -log(hθ(x))
y = 0: -log(1 - hθ(x))

予測結果において、y = 1の確率がほぼ0%なのに実際のyが1だった場合、学習アルゴリズムへのペナルティは∞に近い値になる、という設計になっている。

Multiclass Classification: One-vs-all

マルチクラス分類器。
One-vs-allという戦略で分類できる。
a, b, cとクラスがあったとする。
b, cを同じクラスのトレーニングセットとして、aと2クラスで分類する。
これを繰り返す。
その中で最も高い確率を選ぶ。

The Problem of Overfitting

線形回帰、ロジスティック回帰はオーバーフィッティングを起こす場合がある。
オーバーフィッティング: 学習精度が悪くなる問題
正規化により回避できる場合がある。

• アンダーフィッティング(ハイバイアスを持つ)
  -> トレーニングデータに合致していない。
  予測に対してバイアスを持ち続けて誤差が積み重なる。

• オーバーフィッティング(ハイバリアンスを持つ)
  複雑な曲線(高次元な多項式)で境界を表現しすぎるあまり、仮説には適合するけど変化しすぎるモデルになる。
  仮説がトレーニングセットに適合しすぎたときに起きる。

対策

• 特徴を減らす。
  • 手作業でモデルセレクション
  • 自動でアルゴリズムが選定
• 正規化
  • 全部の特徴を使う。
  • 詳細はあとのセクションで。

ジャストライト: 丁度適合するモデルをcourseraではこう呼ぶ

Cost Function

正規化: パラメータをシンプルにする。不要なパラメータにペナルティを与える。

Coursera. ML. Week. 4

Neural Network

Non-linear Hypotheses

• ロジスティック回帰ではfeatureが2つくらいまでならうまくいく。x^2の項がfeatureの分だけ必要になる。nがfeatureの数だとすると、O(n^2)で項が増える。-> 計算コストが高くつく。x^3の項を含めると、項の総数はO(n^3)になるので現実的では無い。

Neurons and the Brain

• 1980-1990によく使われていた。計算量が多くて無理だったが、最近コンピュータが発達したのとアルゴリズムが発達してうまく学習できるようになった。
• グレースケールカメラの出力を電流値にして、それを舌につけた電極に繋げると、10分くらいで人は学習する。どんなセンサーからでも脳は学習する。-> つまり、学習の方法はシンプルで、1つの方法だけでやってるのではという仮説がある。

Model Representation I

• ニューラルネットワークのモデルの表現について
• ニューロンのネットワークをモデルにしている。
• ニューロン
  • 入口のワイヤから入力を受ける。
  • 出力のワイヤにメッセージを流す。
  • 僅かな電気信号によって信号を伝える。スパイクと呼ばれる。
  • axonが計算をする。
• Activation function: 活性化関数 -> シグモイド関数
• Weights: θのこと

Model Representation II

• モデルの計算をvectorizeして効率的に計算する方法
• forward propagationでAND, ORの学習。

Coursera. week 5. Neual Network 2

Cost Function

• 出力ユニットが3つ以上の場合、出力レイヤーの数 = クラス数となる。2クラスの分類問題だと、出力ユニットは1つでよい。
• 正規化について、バイアスユニットの分は足さないのが慣習。足しても別にうまくいくと思うけど、とのこと。

Implementation Note: Unrolling Parameters

• アンロール(展開)について。行列 -> ベクトルに変換する方法。
• 複数の行列の要素を並べてベクトルにする -> reshapeで取り出す。
  V = [T1(:), T2(:)]
  reshape(V(10:20), 5, 2))

Gradient Checking

• バックプロパゲーション等のアルゴリズムの実装はバグが入り込みやすく、気づきにくい。
• Gradient Checkingを行うことで、これに気づくことが可能。ng氏も毎回やるとのこと。
• Gradient Checkingとは、数値微分した傾きとバックプロパゲーションにより得られた傾きを比較し、近いかどうかをチェックすること。
• 数値微分は(J(θ+ε) - J(θ-ε)) / 2ε の式で求める。
• εは10^-4くらいをng氏は採用する。小さすぎると数値計算上のエラーがおきやすいので。
• トレーニングの前にやる。バックプロパゲーションと比較すると遅すぎるのでトレーニングのコードには入れないように。
  epsilon = 1e-4;
  for i = 1:n,
  thetaPlus = theta;
  thetaPlus(i) += epsilon;
  thetaMinus = theta;
  thetaMinus(i) -= epsilon;
  gradApprox(i) = (J(thetaPlus) - J(thetaMinus))/(2*epsilon)
  end;

Random Initialization

• 最急降下法の初期値はどう決めればよいか。ゼロ行列でよい?
• ロジスティック回帰ではゼロ行列でもうまくいくが、ニューラルネットだとうまくいかない。
• 各ユニットのシータが同じ値の場合、ユニット同士で同じ計算をすることになるので、2つ存在する意味がなくなる。対称ウェイト問題という。そこで、ランダムな値で初期化する。
• θは-εからεの範囲でランダムな行列にする。R x 2ε - εとするとこの範囲に収まる。

Putting It Together

• ネットワークアーキテクチャの選び方。ユニットの数、レイヤーの数。
• 入力ユニット、出力ユニットの数はデータ数、クラス数で決まる。
• 基本は、隠れ層1つ。2つ以上ある場合、ユニット数は同じにする。隠れ層は多いほどよいが、ユニット数が多いほど計算量は多くなる。
• ユニットの数は入力のfeature x 1-4くらいがよいとされている。
• Neural Networkの手順
  1. ランダム行列でウェイトθを初期化
  2. フォワードプロパゲーションを実装
  3. コスト関数の実装
  4. 偏微分を計算するためにバックプロパゲーションの実装
  5. グラディエントチェッキングでバックプロパゲーションの実装を確認
  6. 最急降下法などでθの最小化を行う。非凸関数なので、局所解に陥る可能性はあるが、最急降下法などのアルゴリズムではグローバル最小でなくても大体良い結果を得られる。

Autonomous Driving

• 自動運転について。

Coursera Week 6.

Deciding What to Try Next

より精度を上げるにはどうするか。

• 1つはデータを多くする。
• featureをs増やす
• lambdaを増やす、減らす。
  -> 意味がない場合がある。もっと楽にやる方法がある。
  featureのうち、どれが機能しているのか診断する方法がある。
  開発するのは大変で時間がかかるけど。

Evaluating a Hypothesis

オーバーフィッティングを見抜く方法。
データをトレーニングセットとテストセットの2つに分ける。
例えば、70%をトレーニング、30%をテストに使う。
順番に並んでいる場合はシャッフルしてから選んだほうがよい。

• 分類問題の誤差判定
  正解した個数と誤判断した割合を出せば良い。

Model Selection and Train/Validation/Test Sets

featureの選び方、多項式の項の選び方。

モデルを複数作成してそれぞれのθを求める。
テストにかけて、パフォーマンスを計測していく。
計測結果の中から最も精度のよいものを選ぶと何が起こるか。
テストセットに対してうまく振る舞うモデルができる。
しかし、本当に知りたいことは新しいデータセットに対する反応。

そこでどうするか。

データを3つに分割する。

• トレーニングセット
• クロスバリデーション(CV)セット
• テストセット
  典型的な比率はトレーニング60, CV20, テスト20。

モデルの評価はクロスバリデーションのセットで評価する。
結果の中から最も精度のよいモデルを選択する。
最後に、テストセットにモデルを適用して、汎化性能を計測する。

Diagnosing Bias vs. Variance

結果が良くない場合、大体バイアスが高すぎるか分散が高すぎる。つまり、オーバーフィットしているかアンダーフィットしているか。
このどちらが原因なのか見極めるのが重要。

まずはおさらい。

あまりにシンプルすぎる仮説だとアンダーフィットする。単純にデータと曲線の境界
が遠くなる。一方トレーニングデータに適合しすぎるとオーバーフィットが起きる。
これらは一般的に、以下の2つの問題として扱われる。

• 高バイアス問題 (High Bias)
  アンダーフィットしている状態。
  仮説がシンプルすぎて、トレーニング誤差も大きく、クロスバリデーション誤差も大きい。
  仮説に対して大きなバイアスを持ちすぎている、という意味。

• 高分散問題 (Hight Variance)
  オーバーフィットしている状態。
  トレーニング誤差は小さいのに、クロスバリデーション誤差が大きい状態。

Regularization and Bias/Variance

正規化パラメータλの選び方について。
λ = 0(正規化無し)から順に試す。
0, 0.01, 0.02, 0.04, 0.08 ... 10
λは順に2倍にしていく。
それぞれのモデルにおけるクロスバリデーション誤差を計測し、最も低いものを選ぶ。

Learning Curves

学習曲線: トレーニングエラー、クロスバリデーションエラーの平均二乗誤差をプロットしたもの。横軸がトレーニングセットのサイズ(数)で縦軸が誤差。

トレーニングセットを増やすと、当然誤差の平均は大きくなる。(例えば、トレーニングが1つの場合、フィットさせることは簡単。)一方、クロスバリデーション誤差は多くのデータで学習させたほうが基本的には少なくなっていく。ところが、高バイアス状態や高分散状態の場合、以下のような特徴が見られるので、これらの問題に陥っているかどうかが判断できる。

• 高バイアス状態の場合 (次数が少なすぎる場合)
  データを増やしてもクロスバリデーション誤差は対して変わらない。すぐに収束してしまう。例えば、次数が1(直線)の場合、傾きはある程度すぐに決まってしまうが、曲線で表現できない以上、誤差は消えない。つまり、高バイアス状態ではトレーニングセットを増やしたところで意味がない。

• 高分散状態の場合
  グラフにすると、クロスバリデーション誤差とトレーニングエラーの間に差が開いていることがわかる。データを増やすことでクロスバリデーションエラーは徐々に下がり、トレーニングエラーは徐々にあがる。データを増やす価値がある状態。

Deciding What to Do Next Revisited

高分散状態ではデータを増やすことやfeatureを減らすことが精度の向上につながる。λを増やすことも効果が期待できる。

高バイアス状態は仮説がシンプルすぎるために起きていると考えられるので、データを増やしてもfeatureを減らしても精度の向上にはつながらないが、featureを追加したり、次数を追加するのは効果が期待できる。また、λを減らすのも効果が期待できる。

ネットワーク構造の選び方について。
まずは計算量の少ない小さなネットワークで試してみる。
小さなというのは、隠れ層が1つでユニットも少ないようなネットワークのこと。当然この状態はアンダーフィットしやすい。
大きなネットワークを用いるとオーバーフィットしやすくなるが、正規化で対応できる可能性がある。
通常、大きめなネットワークに正規化を適用するのが精度がでやすいが、計算量は高く付く。

Prioritizing What to Work On

機械学習の戦略について。
何にプライオリティをつけるか。

スパム分類の例

• 単語集を作成し、メールの本文にそれらの単語が含まれるかどうか{0,1}のラベルを付けていく。{alpha: 0, bravo: 1, charlie: 0}など。
• この単語集がfeatureとなる。通常、10,000 - 50,000単語くらいに設定する。
• featureの単語の選び方について。トレーニングセット頻出単語を頻度順に並べて、上位10,000単語などのように選択する。
• スパムのデータを効率よく集めるには、ハニーポットという方法がある。偽のアドレスを用意して、スパマーに掴ませて、色々なスパムを送ってもらうという方法。
• これまで見てきたように、単純にデータを増やしても精度が上がらない場合がある。スパム分類においてよりよいfeatureの例としては、メールヘッダを使うこと。どういう経路で届いたのかなど。あとは、単語の大文字小文字、「!」の頻度など。
• スパマーは「watches」がスパム分類の特徴に引っかかると思った場合、「w4tches」という単語に変えるなど、かいくぐる方法を使ってくる。

ng氏の体験談。スパム分類をかなり長くやっていたが、上記のような状況において、どの特徴に時間をかければよいか判断するのは今でも尚難しい。この内のランダムなどれかに固執するチームはよくある。
ではどうすればよいか。
エラー分析を行うのがよい。

Error Analysis

効率的に精度を高めるための取り組み方について。
最初は何が精度を上げるために必要なfeatureなのか分からないので、まずは学習曲線をプロットできるような適当なプログラムを書くことから始めたほうがよい。この段階で良いコードを書こうとしない。
エラーを分析するため、誤分類したデータセットを人力で観察していき、誤分類のパターンを洗い出す。頻度の高い誤分類パターンから対応していけばよい。
スパム分類のケースだと、単語の語幹をfeatureとして扱う場合がある。これをstemmingという。このfeatureを使うかどうかは、実際にやってみるしかない。featureあり、無しの両方で学習してクロスバリデーション誤差を計測して比較する。

Error Metrics for Skewed Classes

クロスバリデーション誤差を利用する際の問題点について。
分類するクラスのケースが極端に少ない(0.5%等)ケースにおいて、99%の精度で分類するというのが果たして良い精度と言えるのかという話。この場合、y=0のように極端に多いほうのクラスに分類しておくだけで99.5%の精度になるので。このような極端なクラスをskewed classと呼ぶ。
こういう場合、Precision/Recall Rateという評価指標を導入するのがよい。

正解したかどうか: True / False
予想したクラス: Positive / Negative

予想がPositiveで正解 -> True Positive Case
予想がNegativeで正解 -> True Negative Case
予想がPositiveで誤判断 -> False Positive Case

• Precision (精度)
  Positiveと予想した数の内、実際にPositiveの数。
  True Positive / Predicted Positive
  = TruePositive / (True Positive + False Positive)

• Recall (再現率)
  テストセット(CVセット)のうち、予想が正解した割合。
  True Positive / Actual Positive
  = True Positive / (True Positive + False Negative)
  (True Positive: Positiveと判断して正解したデータ。つまり実際にもPositive。False Negative: Negativeと判断して誤判断だったデータ。つまり、実際にはPositive。この2つを足すと、実際にはPositiveだった総数になる。)

Trading Off Precision and Recall

分類の基準を変えることで、Precision重視にするかRecall重視にするかを決定することが可能。
0.5 > yという基準を以下のように変更した場合を考える。

• 0.7 > y
  Precisionが上がるが、Recallが下がる。
  確実にPositiveといえる場合のみPositiveと判断するが、その代わり取りこぼしも増える。

• 0.3 > y
  Precisionが下がるが、Recallが上がる。
  Positiveと判断することが増えるため取りこぼしが少なくなるが、精度は悪くなる。

PrecisionとRecallのトレードオフがある中で、アルゴリズムをどう評価するか。Fスコア(F1スコア)という指標が存在する。

F = 2PR / (P + R)

分子は積で、PとRの両方が大きくないとスコアが大きくならないようになっている。
よって、常にy=1を返すような場合、Rは大きいがPが0となり、Fスコアは0となる。

Fスコアが大きくなるにyのしきい値を最適化することは良い分類器を作る合理的な方法といえる。

Data For Machine Learning

どれだけのデータを使えばよいか。
「Banko and Brill, 2001」によると、アルゴリズム毎にデータ数を変えて機械学習を行ったところ、精度はアルゴリズムによって多少異なるが、データが多ければ多いほど精度がよくなるという傾向があった。つまり、アルゴリズムを良くしたところで、データ量にはかなわないということを意味する。
機械学習の世界では、良いアルゴリズムより多くのデータ、と言われる。
とはいえ、これは問題による。
以下の2つのケースを考える。

1. 英文の途中の単語の穴埋め
2. 住宅の価格の予想
   1であれば、英語に詳しい人が文を読むだけで単語を埋められる。これに対し、2は専門家に対して住宅のサイズだけを伝えても価格は予想できない。つまり、featureが根本的に足りていない。
   このことから、どのようなケースであればデータを増やす価値があるかというと、専門家がfeatureから実際にデータを人力で予想できる状況であることが条件となる。

Coursera ML. week 7.

Optimization Objective

SVMについて。
適用するアルゴリズムの種類より、データ量、正規化パラメータ、featureの選択のほうが重要なことが多い。
人気の教師あり学習アルゴリズム。株の取引等にも利用される。
内容はロジスティック回帰と似ている。

ロジスティック回帰ではA + λBと、Aをなるべく最小化し、λによりパラメータの値を小さく保つことを目的とした。λを大きくした場合、Bに重み付けをすることになる。
SVMではCA + Bという式を使う。Cはコンベンションで、この値によりAに重み付けしている。
ロジスティック回帰ではAを最適化するが、ロジスティック回帰ではBを最適化する。
SVMのCはロジスティック回帰でいうところのλのような働きをするので、結果としてどちらも同じ最適解を導くことになる。(Cが1/λのとき同じθとなる)

Large Margin Intuition

SVMは大きなマージンの分類器といわれる。
マージンというのは、決定境界からトレーニングセットへの距離のことで、データに対してぎりぎりの決定境界を引きずらくなるため、よりロバストに振る舞う。

Mathematics Behind Large Margin Classification

SVMの背後にある数学についての解説。(optionalとのこと)
SVMはθのノルム(長さ)の2乗を最小化しようと試みる。

Kernels I

カーネルについて。
多項式以外でよりよいfeatureはないか考える。
h(θ) = θ0x0 + θ1x1 + θ2x2 + ...
ではなく、
h(θ) = θ0f0 + θ1f1 + θ2f2 + ...
として、
f1 = similarity(x, l1) = exp(- ||x-l1||^2 / 2σ^2)
f2 = ...
とする。
例えば、
x = l1の時(xとl1が近い時)、f1 = exp(-0) = 1となる。
逆にxとl1が遠い時、、f1 = exp(-(大きな数)^2 / 2σ^2)となり、0に近くなる。
よって、f1,f2,f3..はl(ランドマーク)とxの近さ(類似度)を計算することになる。
n = 2のとき、f1を高さ、x1, x2を水平方向の軸として、f1の分布を3次元空間にプロットすると、f1はl(l1,l2)を頂点として山なりの分布になる。
σを小さく(1 -> 0.5)した場合、山の斜面は急勾配になり、分布はスパイク状になる。 逆にσを大きくすると、緩やかな山なりの分布となる。

Using An SVM

SVMを利用する手順について。
SVMのアルゴリズムはlibsvm, liblinear等のライブラリを利用するのがよい。
実装時に実際にやることは以下の通り。

• Cを選択する
• カーネルを選択する

カーネルを利用しない場合もあり、これは線形カーネルと呼ばれる。
線形カーネル: θ^Tx > 0
= θ0x0 + θ1x1 + θ2x2 + ...
線形カーネルはfeatureの数が多いがトレーニングセットが少ない場合でも利用できる。この場合、線形カーネルを利用しないとトレーニングセットが少なすぎてoverfitしやすいので。

ガウシアンカーネルを利用する場合、σ^2を選ぶ必要がある。
σ^2が大きければ高バイアス、低バリアンスになりやすく、σが小さければその逆になる。
また、ガウシアンカーネルを利用する前にはfeature scalingが必要になる。

カーネルは何でもよいというわけではなく、Mercerの定理を満たしていないと機能しない。
この定理を満たしているのはガウシアンカーネル、線形カーネルだけでなく、いくつか存在する。
一つは多項式カーネル(Polynormal Kernel)。

マルチクラス分類について。
ロジスティック回帰と同様に1 vs allでよい。

アルゴリズムの選定について。
n = 10000, m = 10..1000 : ロジスティック回帰、カーネル無しのSVM
n = 1-1000, m = 1-10000: ガウシアンカーネル
n = 1-1000, m = 50000 - 1000000+ : ガウシアンカーネルは遅いので、カーネル無しのSVMか、featureの数を手動で増やしてロジスティック回帰。

SVMはトレーニングセットが巨大でなければ、ロジスティック回帰より良く振る舞う場合がある。
また、凸関数になることが知られており、実装が正しければグローバル最適な値を算出する。

Coursera ML. week 8.

Unsupervised Learning: Introduction

教師無し学習について。
学習にあたってラベルが必要ない。
クラスタリングが一つの例で、SNSコミュニティの分析等に利用される。

K-Means Algorithm

クラスタリングの代表例「K-meansアルゴリズム」について。
データの重心に分類したいクラス数分の基準点を配置する。各データは基準点に近いクラスタに分類される。分類するたびに重心を再計算する。これを落ち着くまで繰り返す。

K: クラスタの数
トレーニングセット: { x1, x2, x3, ... xm}
クラスタの重心: u1, u2, ... uK
ci: xiが現在所属しているクラスタのインデックス

アルゴリズム

u1,u2...uKの初期化

Repeat {

// クラスタ割り振り (目的関数の最小化)
for i = 1 to m
ci = min k || xi - uk || ^2
end

// 重心の移動
for k = 1 to K
uk = クラスタkに属する点の重心
end

}

k-meansの応用例。
Tシャツのサイズ決めの例。Weight, Heightの軸にプロットした点をS,M,Lの3つにクラスタリングする。この結果を元に、ユーザーからWeight, Heightが与えられた際に最適なサイズを提供するということができる。

K-Means Algorithm

k-meansにおける目的関数について。
目的関数を知ることは以下の点で有用。

• デバッグ時に正しく実行できているか確認できる。
• 局所最適を避ける方法を理解する。

目的関数 (Distortion)
J(c1,c2,..,cm, u1,u2,...,uk) = 1/m Σm i=1 ||xi - uci || ^2

Random Initialization

k-meansの初期化について。
K(クラスタ数) < m(データ数)である必要がある。

初期化の方法。
データからK個の点をランダムに取り出して、そこにクラスタの重心を置く。
初期化時のクラスタ重心の配置によって k-meansは局所最適解に落ち着きうるので、何度か実行するのがよい。
例えば、以下のように実行する。

For i = 1 to 100 {
ランダムに初期化
k-meansの実行
コスト関数の計算
}
最小のコストを選択する。

Kが2 - 10くらいの少ないときは違いが出やすい。
Kが数百以上のときは違いが出にくい。

Choosing the Number of Clusters

Kの選び方。
可視化の結果を見て手動で決めるのが一般的。
クラスタがいくつあるのかというのは正解が曖昧であり、人によって解釈が異なるので、自動で選択する方法は基本的に無い。
例えば、Tシャツのサイズを3つにするか5つにするか選択する際、マーケティング的な観点で選ぶほうが適切、という場合がある。

エルボー法について。
Kを変化させてクラスタリングを実行し、Distortion(コスト)をプロットしていく。すると、プロットした曲線が人の腕のような形になり、腕でいう肘の部分が見つかることがある。そのような急激な変化があった点のKを選択する、という方法。
しかし、場合によっては急激な変化が起きない場合がある。その場合はエルボー法は機能しない。もし機能するようであれば、Kを選択するための合理的な理由になる。

Principal Component Analysis Problem Formulation

次元削減について。
教師なし学習の一つ。
データ圧縮に利用する。

例えば、featureとしてx1(cm), x2(インチ)があった場合、明らかに冗長なfeatureとなるので、1つにまとめられる。別の例として、パイロットのスキルと飛行をどれくらい楽しんだか等、相関があるものも1つにまとめられる。
このような例を数百規模のfeatureのセットが何セットか与えられた際に、1つ1つ検証するのは無理なので、自動的にまとめることで無駄なfeatureを削減できると便利。無駄なfeatureを無くすと学習時の計算コストも下げることになる。

削減をどうやるかというと、例えば2次元のデータであれば、それを1次元の軸上に射影することで実現する。

Motivation II: Visualization

次元削減はデータ可視化に使える。
例えば50個のfeatureを2次元のベクトルで表すなど。
2Dにすればグラフにプロットできるので。

Principal Component Analysis Problem Formulation

主成分分析(PCA)について。
射影誤差(2乗差)を最小化するのがPCA。

3D -> 2Dの例だと、
3D空間にプロットされた点をu1, u2で表される平面に射影する。各点をu1,u2成分で表せるようなu1,u2を探す。

線形回帰と似てるけどやることが違う。
線形回帰では直線とデータ点との垂直誤差を取るが、PCAでは直線とデータ点の距離を取る。2Dの例だと、直線に対して法線上にデータ点が来るように距離を取るイメージ。

Principal Component Analysis Algorithm

PCAアルゴリズムについて。

まず、平均標準化(mean normalization)を行う。
データによってはfeature scalingも必要になる。
featureの平均値が0になるように、xj := xj - ujとする。
ちなみに、数学的な証明はかなり大変とのこと。

n次元からk次元へとデータを削減する場合を考える。
共分散行列Σを計算する。
octaveなら以下の式で得られる。(svd: Singular Valude Decomposition(特異値分解))
// 特異値分解する場合
[U,S,V] = svd(Sigma)

// 固有ベクトルを求める場合
eig(Sigma)

共分散行列
Σ = (1/m) Σi=1:n x(i)x(i)^T

Choosing the Number of Principal Components

PCAはn次元をk次元に圧縮する。
kは主成分の数、総数と呼ばれる。

PCA: 二乗射影誤差の平均を取る。
多くのデータにおいてfeature同士が相関を持っているから圧縮することが可能。

求め方

for i = 1 : n
if (二乗射影誤差の平均 / 分散) < 0.01
k = i, break
end
end

Advice for Applying PCA

トレーニングセットをPCAで圧縮し、
(x(非圧縮), y)
->
(z(圧縮済み), y)
としたデータセットを作成。
この圧縮済みのデータセットをトレーニングする方法で学習速度の向上が期待できる。
※ PCA圧縮(x->z)のマッピングを探す際に利用するデータにはクロスバリデーションセット、テストセットを含まないようにする。

使用する際の注意。
featureの数を減らせるからといって、オーバーフィットを防ぐために利用するのはよくない。オーバーフィットに対応するなら正規化がベター。
PCAの圧縮では貴重なfeatureを捨て去る危険がある。

• トレーニングのスピードアップのためにPCAを使うのはおｋ
• オーバーフィットを防ぐために利用するのはNG。正規化のほうがうまくいく。
• 最初からPCAを導入するのはよくない。一旦オリジナルデータでトレーニングさせる。あまりに遅すぎたり容量を取りすぎて実行できない場合にPCAを導入する。PCA無しでうまくいくケースも多い。

Coursera week 9.

Problem Motivation

アノマリー検出について。
割とよく使われる。教師なし学習だが、教師あり学習と似ている。

航空機のエンジンのテストの話。
テストfeature {x1,x2...}の結果から、何か異常がないか判断する。
通常の範囲から外れた結果はアノマリーとして扱う。
通常範囲に収まる結果はnormalとして扱う。

p(Xtest) < Σ: flag anomaly
p(Xtest) >= Σ: OK

応用例1
webサイトのユーザーのアクティビティから奇妙な行動をとっているユーザーを探し出す。詐欺などに利用しているかどうかを判断し、身分証の提出を促すなど。
feature例

• ログイン頻度
• ページの総数
• フォーラムに投稿したポストの総数

応用例2
データセンターでそれぞれのマシンの負荷が高くなる確率を検出したり、サーバーが落ちそうな気配を察知したり。
feature例

• メモリの使用量
• CPU負荷
• NWトラフィック量

Gaussian Distribution

ガウス分布(正規分布)について。
σ: 標準偏差
σ^2: 分散。平均との二乗誤差の平均
μ: 分布の中心。データの平均値
ガウス分布に沿ったデータが与えられた際に、μとσがわからなくても上記のように推定することが可能。

Algorithm

アノマリー検出のアルゴリズムについて。
トレーニングセット: {x1, x2 ... xm}
p(x) = p(x1; u1, σ1^2)p(x2 ; u2, σ2^2 ) ... p(xn ; un, σn^2 )
-> Π(n, j=1) p(xj; uj, σj^2)

Π: 積を取る, (Σが和を取るのに対し、Πは積を取る)

Anomaly Detection Algorithm.

1. featureを選ぶ。ユーザーの行動など。
2. パラメータフィッティングにより、uj,σ^2を推計する。
3. p(x)を計算する。Π(n, j=1) 1/(√(2π)σj) exp(-(xj-uj)^2/(2σj^2))
4. p(x) < εの場合、アノマリーとする。

視覚的なイメージとしては、featureごとの確率分布(正規分布)の山をかけ合わせて、山の高さが低いような部分をanomalyとする。

Developing and Evaluating an Anomaly Detection System

評価について。
結果を評価することがアノマリー検出の精度を向上させるためのfeatureを選ぶ基準になる。
y = 0: normal
y = 1: anomalous
ラベルなしのトレーニングセット: {x1, x2...xm}
クロスバリデーションセット: {(xcv1, ycv1), ... }
テストセット

例
10000個のエンジン (y=0)
20個の欠陥エンジン (y=1)

内訳
トレーニングセット: 6000 (60%)
CV: good 2000 (20%), anomalous 10
Test: good 2000 (20%), anomalous 10

y = 1: p(x) < ε -> anomaly
y = 0: p(x) >= ε -> normal

評価
Recall rate
F1 score

1. ラベルなしデータセットにパラメータをフィットさせる。
2. F1ScoreやPrecision/Recall rateで評価する。(true, falseのデータ量に差がある場合が多いので)
3. εを選択する。

Anomaly Detection vs. Supervised Learning

アノマリー検出と教師あり学習のどちらを使ったらよいか。

アノマリー検出

• 異常値(y = 1)のサンプルが少なく(0-20)、大量に正常値(y = 0)のサンプルがある場合
• サンプルが正規分布に従う場合
• 適用例: 詐欺行為の検出等に向いているが、あまりに例が多ければ教師あり学習にするのもあり。他には、工業製品において欠陥品のサンプルが少なすぎる場合などはアノマリー検出を使うのがよい。

教師あり学習

• 正常値、異常値が両方とも大量に存在する場合
• 分類しようとしているものがトレーニングセットに存在しているデータと大体近いようなものの場合
• 適用例: 天気予報、スパム分類など、陰性・陽性ともに大量にサンプルが手に入る場合

Choosing What Features to Use

何のfeatureを選ぶかが重要。
正規分布に従っていたほうがよいが、ちゃんと従ってなくてもうまく機能することが多い。
ヒストグラムが対称的な山なりなら正規分布と思って良い。
山のピークが片方によっていたりする場合、少し使うのをためらう。このような場合でも大体機能するが、ng氏は正規分布に近くなるように変換をかけたりもする。変換をかけてうまく正規分布に近づけば、そのほうが精度は高くなる。

変換の例としては、log(x)等がある。
あるいは、log(x + C)やx^1/n など。
ヒストグラムを見て判断する。

featureをどのように見つけるか。
誤差分析がよい。
つまり、学習してみて、うまく振り分けられていないデータを観察してfeatureを増やしていく。

Multivariate Gaussian Distribution

アノマリー検出の拡張の一つ、多変量ガウス分布について。
利用することにより、これまでのアルゴリズムで捉えられないようなケースも検出できる場合がある。

2次元の値を持つfeatureがあるとすると、feature毎にガウス分布が得られる。例えば、それぞれの分布内にプロットしても問題なさそうなのに、2次元空間にプロットすると明らかにアノマリーという場合がある。
二次元空間上の分布の中心を分布の円の中心として考える。

u: Rn -> ベクトル
Σ: R(n, n) -> 共分散行列

p(x;u,Σ) = 1/((2π)^(n/2)det(Σ)^(1/2)) exp(-(1/2)(x-u)^(T)Σ^(-1)(x-u))

Σ: 単位行列。対角成分が各featureに対応する。成分が1より大きくなると分布の山が平坦になり、小さくなると分布の山がスパイク上になる。

μ: 分布の中心。featureがn個なら要素数nのベクトル。

Anomaly Detection using the Multivariate Gaussian Distribution

多変量ガウス分布を用いたアルゴリズム。
やることはガウス分布の場合と同じでp(x)の式が行列式を含んだものに変わる。
共分散行列Σは対角成分以外0でなくてはならない。

使い分けについて。
ガウス分布のほうが基本的にはよく使われる。
多変量ガウス分布はfeature間の関係を捕捉できる利点がある。
例えば、feature {x1, x2}が特定の組み合わせとなった場合のみ異常値として検出したい場合など。

これをガウス分布でやるには、追加のfeatureが必要となる。(例えばx3 = x1 / x2など)。多変量ガウス分布では、追加のfeatureが必要ない。
ガウス分布はn=10000, n=100000くらいの範囲でうまく機能する。
多変量ガウス分布は計算量が大きくなるのでスケールしにくい。

また、多変量ガウス分布は数学的な制約がでる。当然、m > nでないといけないし、Σが特異行列(非可逆)の場合はうまくいかない。特異行列の原因はfeatureが冗長な場合があるので、その場合はfeatureをチェックして無駄なものは取り除くようにする。冗長というのは、線形従属しているということ。もっとも、これに遭遇する機会は少ないのであまり気にしなくて良いとのこと。

Problem Formulation

レコメンダーシステムについて。
レコメンダーシステムは機械学習の重要な適用例の1つ。
機械学習の中にはfeatureを自動で学習できる例が存在するが、レコメンダーシステムはそのうちの一つ。

定式化する。
映画のレーティングについて考える。
ユーザーが映画の評価を1-5の間で評価するとする。

nu: number of users. ユーザー数
nm: number of movies: 映画の数
r(i,j): ユーザーjが映画iをレーティングしたかどうか。(0,1)
y(i,j): ユーザーjが映画iを評価したレーティング。(0-5)

上記のデータから、まだユーザーがレーティングしていない映画について、レーティングが0-5のどれに該当するか予測するという問題。

Content Based Recommendations

コンテンツベースのレコメンデーションについて。

feature{x1, x2}があるとする。
x1: romance (どのくらいロマンス映画か)
x2: action (どのくらいアクション映画か)

やり方の一つは、レーティングを線形回帰問題として扱うこと。
ユーザーjに対してパラメータベクトルのシータjを学習する。

ユーザー1: θ1
ユーザー2: θ2
...

映画1: x1
映画2: x2
...

例:
映画3: x3 = [1, 0.99, 0]
ユーザー1: θ1 = [0, 5, 0]

学習されたθを元に内積を取る。
(θ1^T)x3 = 5 * 0.99 = 4.95
よって、ユーザー1の映画3へのレーティングは4.95と予測される。

この方法は、各ユーザー毎に線形回帰を行うモデルとなる。

ここでもう一つ記法を追加する。
mj: 映画jをレーティングしたユーザー数

θjを学習するにはどうすればよいか。
基本的には線形回帰の問題。

minθj 1/2 (Σ(i:r(i,j)=1)((θj^T)xi - y(i,j))^2) + λ/2Σk=1:n(θkj)^2

最急降下法で最小化問題を解く。

線形回帰問題への最急降下法の適用時とほぼ一緒。違いは係数(1/m)の部分。

コンテンツベースの方法では、映画ごとのロマンティック度合いとかアクション度合いが与えられていることが前提となる。しかし、実際にはこのようなfeatureが用意されていることはあまり無いため、これを集められるかというのが問題となる。
次回は別のアプローチを紹介する。

Collaborative Filtering

協調フィルタリングについて。
フィーチャーラーニングを利用する。アルゴリズムがfeature自体を学習する方法。

コンテンツベースのレコメンデーションでは、ロマンティック度合いなどのfeatureが与えられているものと仮定して学習した。
それに対し、今回はfeatureがわからないものとして進めていく。

(θx - y)の二乗誤差を最小化するようなfeature:xを求めたい。
これまでの線形回帰のように、θを求めるのではなく、xを求める。

鶏と卵の問題。
ユーザーがレーティングθを提供してくれれば、そこからfeature:xを求められる。
映画毎のfeature:xがわかっていれば、そこからθを求められる。

そこで、まずはθをランダムに初期化してxを求める。その先は、ユーザーがθを提供される度にxを改善する、というように、θ->x->θ->x->...と改善を繰り返していく。これにより、ユーザーが協調(Collaborate)して精度が向上していくというサイクルが出来上がる。

Collaborative Filtering Algorithm

協調フィルタリングのアルゴリズムについて。
前の章では、θの最小化とxの最小化を行ったり来たりすることで最適化していく、という話だったが、この2つを同時に最適化する方法がある。

xとθを単に同時に最小化するが、この時、これまでやってきたようなx0=1, θ0=1という要素は必要ない。なぜなら、両方同時に学習するため、勝手にx0=1, θ0=1というセットと同じ意味になるよう学習されるから。(これまではどちらかを固定していたため、もう片方が=1となるよう合わせる必要があった。)

アルゴリズム

1. x, θをランダムに初期化する。
2. 最急降下法により、x, θを同時に最小化する。
3. (θ^T)xで予測する。

Vectorization: Low Rank Matrix Factorization

協調フィルタリングのベクタライズと協調フィルタリングの応用例について。

応用例の一つに、ユーザーが最近見た商品から関連する商品を探すというものがある。
先程の映画の例だと、協調フィルタリングが予測する結果は以下のような行列になる。
|ユーザー1の映画1に対する評価(0-5), ユーザー2の映画1に対する評価(0-5)..|
|ユーザー1の映画2に対する評価(0-5), ユーザー2の映画2に対する評価(0-5)..|

n: ユーザー数
m: 映画の数
とすると、出力はmnの行列。

ベクタライズすると、予測する行列は(X^T)θで表される。
協調フィルタリングには別名があり、「低ランク行列分解(Low Rank Matrix Factorization)」と呼ばれる。

協調フィルタリングを行うことでxを学習することができるということは、問題にとってどういう特徴が重要なのかが判断されるということ。これらの特徴は人間にとっては理解できない場合もある。

映画iに関連した映画jを探したい。
その場合、||xi - xj||が小さいものを探せば良い。
映画のもつfeature間の距離が小さい映画を探せば、それが関連する映画となる。

Implementational Detail: Mean Normalization

平均標準化(Mean Normalization)について。
アルゴリズムを良くする場合がある。

映画の例において、例えば、まだ1つも映画をレーティングしていないユーザーがいるとする。これまでのアルゴリズムでは、正規化項などの影響もあり、このユーザーのレーティングの予測値は全ての映画に対して0になってしまう。しかし、多くのユーザーが5や4の高評価を付けている映画があった場合、このユーザーも実際には高評価をつける可能性が高く、0という予測値は正しいのか怪しい。また、全映画の予測値が0だと、このユーザーに推薦する映画が無くなってしまう。
平均標準化はこの問題を解決する。

どうするかというと、トレーニングデータの全ての要素から全映画の平均値を引き、平均値が0になるようにする。予測値には引いた分を足し戻す。このようにすると、まだレーティングをしていないユーザーについては映画に平均値を付けたということになり、映画の平均値が予測される。
これは1つもレーティングしていないユーザーにのみ有効と考えられる。1つでも映画をレーティングしている場合、他のレーティングしていない映画についてはレーティングする価値が無かったと判断している場合があるので。

Coursera week 10.

Learning With Large Datasets

大規模スケールの機械学習について。
ここ最近の機械学習では扱うデータ量が増えたことで精度が上がった。

大量のデータを扱う場合の問題点について。
まず、計算量的な問題がある。
例えば、1億のデータを扱う場合、最急降下法では1ステップで1億個の和を取る必要がある。そこで、微分項の計算を効率的に行う必要がある。
まずは1000個とか、その程度のデータで済まないか試すのがよい。
その際、学習曲線をプロットしてみてチェックする。
ハイバイアスな傾向があればデータを1億に増やしても対して精度が変わらないはず。
その場合、featureを足したり、隠れ層を増やすことを検討する。

week 10では、確率的な最急降下法とMap Reduceについて学ぶ。

Stochastic Gradient Descent

これまで紹介した最急降下法の問題点はmが大きいときに微分項を計算するコストが高いこと。全部の和を取るので。
このアルゴリズムにはバッチ最急降下法と名前がついている。一度に全てのデータを見るので。
計算量について。レコード量を全てメモリに読み込む必要があるのでコストが高い。
しかもそれをやっても1ステップ計算が進むだけ。

もっとスケールするアルゴリズム「確率的最急降下法」を紹介する。
最急降下法のJについて考えると、これはコストの平均を取っている。
そこで以下のようにする。

1. ランダムにデータを並び替える。
2. バッチ最急降下法と同様、1...mまでコストを計算していく。
3. トレーニングセットを1つ読み込む度にパラメータθをアップデートしていく。

バッチ最急降下法では全てのデータをスキャンしてからようやくパラメータをアップデートするが、このアルゴリズムでは毎回パラメータをアップデートする。
バッチ最急降下法では、グローバル最小に向かってまっすぐ進むが、このアルゴリズムではまっすぐは進まない。ジグザグと遠回りしながらグローバル最小に向かう。そして、最終的にはグローバル最小値の周辺をウロウロする。グローバル最小近くの値でも実用上これで問題ない。
確率的最急降下法では、1-10回程度トレーニングセットをスキャンする。

Mini-Batch Gradient Descent

ミニバッチ最急降下法について。これは確率的最急降下法より早くなる場合がある。
ミニバッチ最急降下法はバッチ最急降下法と確率的最急降下法の間に位置する。
各イテレーションでb個のサンプルをスキャンする。
バッチサイズは2-100くらいの間。特に10くらいが典型的。
例えば、10個スキャンしたらパラメータをアップデートする、などのようにする。
並列化する手段があるのが利点。
1回目: i: 1-10,
2回目: 1: 2-11,
...
とやる。

Stochastic Gradient Descent Convergence

バグと収束判定を確認する方法と学習率αを決める方法。
これまではコストファンクションがイテレーション毎に減ることを確かめていた。
ところが、これは和を取るので遅い。
そこで、確率的最急降下法では、θのアップデートの直前に、過去1000手本におけるコストの平均を取ってプロットする。これを見て収束しているか判定する。
1000ではなく5000に増やせば、プロットする線はより綺麗になるが、遅くなる。
コストが増加する傾向があれば、αを小さくする。
α = const1 / (iterationNumber + const2)
const1, const2: 定数。その時その時調整する。
iterationNumber: その回でのイテレーションの回数(ステップ毎にインクリメントされる。)
確率的最急降下法では、αについて上記のように取ると、グローバル最小付近であまりふらふらせずに最小値付近にとどまるようになる。繰り返す度に徐々にαが小さくなるので。
ただし、この方法だとconst1, const2をうまく調整する必要があるし、別にグローバル最小付近でふらついた結果を利用しても大体うまくいくので、基本あまりやらない。が、これを使う人もいるのでお好み。

Online Learning

オンライン学習について。
ストリームデータが流れ続けていて、そこから学習する方法。
配達サービスの例。ユーザーがAからBまで配達する。
このようなwebサイトを運営しているとして、ユーザーが仕事を求めてやってくるが、それに対してその時々の最適な価格を提供したい。
こちらはユーザーの特徴と配達の価格を知っていて、ユーザーに配達させるのがゴール。この時、なるべく高い確率でユーザーに配達サービスを提供するような価格が知りたい。
これに対し、ロジスティック回帰を使うとする。
Repeat {
Get (x, y) from user.
Update θ using (x, y)
θ := θj - α(hθ(x) - y)xj (j=0,...,n)
}

これまでは、(xi, yi)とトレーニングセットの数分処理するようにしていたが、オンライン学習では受け取ったトレーニングデータ1つを処理してパラメータを更新したら捨てる、ということを繰り返すので、(x, y)としている。

オンライン学習の利点。ユーザーの嗜好に適応できる。
その時期その時期の経済状況や好みの変換に対応して学習できるので。

もう一つ応用例。
商品検索について。ユーザーが買ってくれそうな商品を表示する。
クリックする確率。featureは商品の特徴。
Click Through Rate (CTR)と呼ばれる。
ユーザーが検索して結果を10個返すとする。ユーザーがある商品をクリックした場合、そのデータを元に学習していく。

以上がオンライン学習。
これは最急降下法とよく似ていて、違うところは既存の固定されたトレーニングセットを利用するかストリームデータを利用するかというところ。

Map Reduce and Data Parallelism

いくつかの機械学習アルゴリズムは1つのコンピュータで実行するには計算量が高くつきすぎる。そこで、並列実行するための「Map Reduce(Jeff Dean, Sanjay Gimawat)」を紹介する。
m = 400とし、あるトレーニングセットが(x1,y1)...(xm,ym)まであるとする。
4台のマシンでトレーニングを行う場合、1台目のコンピュータでは最初の100を処理する。2台目のコンピュータでは101-200までを処理する。3台目では...とやっていく。
全てのコンピュータで処理が終わったら、マスターコンピュータに結果を戻し、それぞれの結果を足す。

１つのコンピュータでMap Reduceを行う場合もある。複数コアのコンピュータであれば、コア毎に計算を分けることで並列化が可能。ただし、数値計算ライブラリの中には自動的に複数コアを使う場合がある。

Map Reduceの1つの実装例は「Hadoop」。

Coursera week 11.

Problem Description and Pipeline

OCRについて。
まず、画像中のどこにテキストがあるか探す。次に、テキストを画像から抽出する。
カーナビ等にも応用される。

OCRのパイプラインは以下のようになる。

1. テキスト検出
2. 文字分割
3. 文字分類

パイプラインのモジュール間の区切りはパフォーマンスに影響する。
分ければ分担作業することもできるので、その意味でも。

Sliding Windows

スライディングウィンドウ分類器について。

歩行者検出の例。歩行者のアスペクト比は大体同じようになる。
一定のサイズの歩行者画像イメージを集める。(y=1)
陰影や建物などの画像イメージを集める。(y=0)
この2種類で教師あり学習を行う。
学習データを利用してどうするかというと、検出対称の画像の左上から、トレーニングに利用したサイズと同サイズでウィンドウを移動させていき、歩行者かそれ以外か(y=0,1)分類していく。これがスライディングウィンドウ分類器。1週したら、次はもう少しウィンドウのサイズを大きくしてまたスライディングさせていく。この時、分類器にかける際にはトレーニングセットと同じサイズに縮小するようにする。

では、テキスト検出ではどうするか。
テキスト検出においても歩行者と同様にスライディングウィンドウにより検出できる。検出した領域同士、連続している領域はつなげていき、アスペクト比が文字列らしく横長なもののみ残すようにする。

次に、文字分割について。
この部分においても教師あり学習が使える。
文字が1つの画像に2文字存在している画像を(y=1)とする。
文字が画像の真ん中にある画像を(y=0)とする。
このデータセットを教師あり学習し、分類器を用いてy=1の位置(文字間の位置)を1Dスライディングウィンドウにより探していく。

最後に、文字の分類はこれまでやったように、教師あり学習すればよい。

Getting Lots of Data and Artificial Data

低バイアス状態でデータを沢山学習させたいが、どのように取得すればよいか。
1つは生成すること。

PhotoOCRの文字分類について。
フォントライブラリがweb上に何千とあるのでこれを利用する。
適当な背景画像を沢山用意し、そこにフォントを重ねる。違和感を無くすためにブラーをかけてもよい。あるいは、アフィン変換をかけて文字を少し回転させるのもよい。このようにして生成した画像を大量に学習できる。

もう一つのやり方は教師画像に対して歪みを与えることで、1つのデータを複数に増やすこと。この歪みは問題によってどのように与えればよいか異なる。例えば、スピーチの認識では、バックにビープ音を合成したり、ノイズを加えたりする。ちなみに画像の場合でもノイズを乗せるのは有効な場合がある。

これらの方法をやるにあたっては低バイアスな分類器であるか先に確認すること。
それから、最も避けるべきことは、時間をかけてデータを真面目に収集しても対して精度があがらないという状態。
2-3日で10倍のデータを作り出すことができれば大きく精度が上がるかもしれない。

まとめると、1つはスクラッチで人工データを作る方法。2つ目は元のデータを加工する方法を紹介した。
データを集める前に、ラベル付けにかかる時間も調べたほうがよい。1つ辺りどれくらいかかるか。大変なラベリング作業よりも、データを生成したほうが効率がよい場合がある。

Ceiling Analysis: What Part of the Pipeline to Work on Next

シーリング(天井)分析について。
機械学習において重要なことは時間。データ集めに無駄な時間を使わないこと。

PhotoOCRの例。
パイプライン中のどの工程に時間を使うべきか。
それぞれの工程においての精度を測定できると良い。
各モジュール毎に、完璧なデータを一つ前の工程からモジュールに流してみて、その度に"全体の"精度を測定していく。これをやることで、そのモジュールが仮に完璧だった場合における全体の精度がわかる。
単体の精度が高いモジュールを改善しても全体に大きな影響は与えない。単体の精度が低いモジュールに時間をかけたほうがよい。

パイプラインの例

1. カメラから画像の取得
2. 背景除去
3. 顔認識
4. 顔パーツ検出
   1. 目検出
   2. 鼻検出
   3. 口検出
5. ロジスティック回帰
6. ラベル

この場合のシーリング分析は以下のようになる。

全体: 85%
背景除去: 85.1%
顔認識: 91%
顔パーツ検出
1. 目: 95%
2. 鼻: 96%
3. 口: 97%

結果の見方について。
例えば、背景除去が100%の出来だとした場合の全体の精度は85.1%となっている。つまり、背景除去を完璧にしたところで、85%->85.1%にしかならない。よって、この場合、背景除去に時間をかけても全体の精度はほとんど向上しないので、ここに時間を使うべきではないということになる。

直感ではなく、シーリング分析をやるほうがよい。