Web開発におけるコンピュータサイエンス - 機械学習編1

はてな教科書

この教科書は、はてなサマーインターンの講義資料として作成されたものです: https://github.com/hatena/Hatena-Textbook

この章では機械学習について、Webサービスの開発で必要とされる知識を中心に、とくに自然言語処理にフォーカスしながら解説します。

\def\bm#1{\boldsymbol{#1}} \def\set#1{\{#1\}}

Webサービス開発と機械学習

Webサービスで提供したい機能の中には、必ずしも100%の精度でなくてもいい代わりに、闇雲に実装したのでは実現が困難なものがあります。たとえば以下のようなものです。

  • カテゴリ自動判別
    • ユーザのポストした内容を自動的に分類するような機能
  • スパムフィルター
    • ポストされた内容がスパムかどうか判別する機能
  • トピック自動抽出
    • ポストされた複数の内容のうち似通った話題のクラスタを見つける機能
  • 異常値検出
    • 不正アクセスを自動検出する機能
    • サーバの異常動作を検出する機能

ここで挙げた機能はどれも、過去のデータの蓄積を使って将来やってくるデータに対して判断を下すものです。このような機能を実装する場合には機械学習を用いるとうまくいく場合があります。

実現困難な機能の例

まずは機械学習なしで闇雲に実装していったとき、どんな困難があるか見てみましょう。例として、ブログのようにユーザが自由に文章をポストできるサービスで、ポストされた内容がどの地域と関連が深いか自動的に判別する機能を実装する場合を考えてみます。

闇雲な実装

まずは安易に、ポスト内容のテキストに特定の語を含んでいるか、if文で確かめていくことにしましょう。判別対象の地域はさまざま考えられますが、まずは京都に関するものかどうか確かめる処理を書いていくことにしましょう。

sub is_about_kyoto {
  my ($text) = @_;

  return 1 if $text =~ /京都/;
  return 1 if $text =~ /烏丸御池/;
  ...

  return;
}

sub detect_location {
  my ($text) = @_;
  return 'kyoto' if is_about_kyoto($text);
  return 'unknown';
}

これでうまくいくでしょうか? 実は全くダメで、$textに東京都という文字列を含んでいて東京のことについて書かれていた場合にも京都の内容だと誤判定されてしまいます。以下のように書き換えたらもう少しうまくいきそうです。

return 1 if $text =~ /烏丸御池/;
return 0 if $text =~ /東京都/;
return 1 if $text =~ /京都/;

京都という文字列の出現を確かめる前に東京都という文字列が出現しないことを確かめています。ここで注意が必要なのは烏丸御池を東京都より先に持ってきている点です。いくら東京都と書いてあったとしても、烏丸御池と書いてあればそれはほぼ間違いなく京都の烏丸御池についても言及しているはずだと思えるので、優先順位を上げています。

この調子で、いまあるデータに対してはだいたい間違いなく判別できそうなアルゴリズムを実装できたとします。さて、この機能をプロダクトに投入してしばらくすると、巷では福岡県の京都(みやこ)郡について少し話題になりました。残念ながらこれまでのロジックでは京都郡の話題は福岡ではなく京都の話題と判定されてしまいました。このままではまずいので、機能の改修に着手しましょう。

東京都の場合と同じく以下のようにルールを追加すればよいでしょうか?

return 0 if $text =~ /京都郡/;
return 1 if $text =~ /京都/;

これでサンプルデータを検証してみたところ、実際には

京都(みやこ)郡○×町にある ... 打ち合わせがおわって博多駅で ...

というように、京都と郡が隣接していない場合も多いことがわかりました。そもそも郡が出てきたら京都の話題ではないということにしたらよいでしょうか?

return 0 if $text =~ /郡/;
return 1 if $text =~ /京都/;

検証の結果、今度は京都府相楽(そうらく)郡の話題が京都の話題として検出できなくなってしまったことがわかりました。直接的に京都郡を除くのではなく、先に福岡に関する話題かどうかを判別したらどうでしょうか?

sub is_about_fukuoka {
  my ($text) = @_;

  return 1 if $text =~ /博多/;
  ...

  return;
}

sub is_about_kyoto {
  my ($text) = @_;

  return 1 if $text =~ /烏丸御池/;
  return 0 if $text =~ /東京都/;
  return 1 if $text =~ /京都/;
  ...

  return;
}

sub detect_location {
  my ($text) = @_;
  return 'fukuoka' if is_about_fukuoka($text);
  return 'kyoto' if is_about_kyoto($text);
  return 'unknown';
}

検証の結果、これでは「博多長浜ラーメンみよし」(京都市中京区)の話題が福岡の話題と判定されてしまうことがわかりました。闇雲な実装のままでは、新しい種類の誤判定に出会う度に、こちらを立てればあちらが立たずで、微妙な調整を繰り返すことになります。

もう少しましな実装

京都の話題かどうかは、入力テキストに含まれる複数の語を総合的に考慮する必要がありそうです。そこで、含まれている語がどれくらいその地域らしさを表しているかの重要度(重み)を計算して、重要度の合計をスコアとして地域性を判別することにしましょう。京都らしい語ではスコアを加算して、京都らしくない語ではスコアを減算していき、最終的なスコアの正負で京都の話題かどうかを判別します。

sub kyoto_score {
  my ($text) = @_;

  my $score = 0;
  $score += 50 if $text =~ /烏丸御池/;
  $score += 30 if $text =~ /京都/;
  $score -= 30 if $text =~ /東京都/;
  $score -= 50 if $text =~ /京都郡/;
  $score -= 30 if $text =~ /博多/;
  $score += 10 if $text =~ /ラーメン/;
  ...

  return $score;
}

sub detect_location {
  my ($text) = @_;
  return 'kyoto' if kyoto_score($text) > 0;
  return 'unknown';
}

あとは検証用のサンプルデータが正しく判別されるように各語の重要度の値を調整していけばよさそうです。とはいえ、手で調整する内容が、複雑な条件から重要度の値に変わっただけで、いずれにせよ最適な条件を見つけるのは難しいでしょう。とくに判断基準となる語の種類が何万にもなってしまったとき、いったいどうやって重要度を調整していけばよいでしょうか?

機械学習によるパラメータ決定

前節の例でやろうとしていたことは、i番目の語が文書中に出現するかどうかをx_i \in \set{1, 0} (x_iは1または0)で表したときに、加算すべき重要度w_iを使って

\displaystyle \sum_i w_ix_i

の正負によって、文書が特定地域の話題についてのものであるか判別するということでした。あとはサンプルデータをできるだけ正しく判別できるようなパラメータw_iの値を見つけるという一種の最適化問題を解くことができれば、地域判別のアルゴリズムが完成します。

機械学習を用いると、まさにこのような、過去のデータから最適なパラメータを推定するという問題を解くことができます。以下のように、サンプルデータが単語ごとに区切ってあり、それぞれ京都の話題かどうかをis_kyotoの値で示してあるとすると、機械学習エンジン$kyoto_engineのtrainメソッドによって各語に付与すべき重要度が求まるイメージです。

my $kyto_engine = ...
my $weights = {};

sub update_weights {
  # サンプルデータ
  # { words => [
  #     '烏丸御池' => 1,
  #     'の' => 1,
  #     '交差点' => 1,
  #     'を' => 1,
  #     '長刀鉾' => 1,
  #     'が" => 1,
  #     '通る' => 1,
  #     'と' => 1,
  #     ...
  #   ],
  #   is_kyoto => 1,
  # },
  # { words => [
  #     '京都' => 1,
  #     '(みやこ)' => 1,
  #     '郡' => 1,
  #     '○×町' => 1,
  #     'に' => 1,
  #     'ある' => 1,
  #     ...
  #     '打ち合わせ' => 1,
  #     'が' => 1,
  #     'おわっ' => 1,
  #     'て' => 1,
  #     '博多駅' => 1,
  #     'で' => 1,
  #     ...
  #   is_kyoto => 0,
  # },
  # ...
  my @data = @_

  $weights = $kyoto_engine->train(@data);
  # { 'ラーメン" => 10,
  #   '京都' => 30,
  #   '京都郡' => -50,
  #   '博多' => -30,
  #   '東京都' => -30,
  #   '烏丸御池' => 50,
  #   ...
  # }
}

sub kyoto_score {
  my ($text) = @_;
  my $score = 0;
  for my $pair (pairs %$weights) {
    my ($word, $weight) = @$pair;
    $score += $weight if $text =~ /$word/;
  }
  return $score;
}

sub detect_location {
  my ($text) = @_;
  return 'kyoto' if kyoto_score($text) > 0;
  return 'unknown';
}

このようにして得られたdetect_locationメソッドは、ユーザが新たにポストした内容を正しく判別できるでしょうか? 実は必ずしもそうとは言えません。

今回の例では、「特定地域の話題かどうかは、文書中の語の出現に付与した重要度の和(線形和)で決まる」という仮説を置きました。まず、ターゲットとしている文書集合の傾向と地域判別という問題に対してこの仮説が適しているかどうか、という懸念があります。もし適していなかった場合、trainメソッドによる学習結果のパラメータは、サンプルデータの判別に対しても十分な精度が出ないでしょう。

仮にサンプルデータの判別はうまくいっているとしても、未知の入力に対してもうまくいくという保証はありません。サンプルが少なすぎたり、サンプルの傾向に過剰に適応して過学習状態になってしまっていると、未知の入力を正しく判別できません。

この後の章では、他に取りうる仮説の選択肢や、学習結果の評価のしかたについても見ていきましょう。

分類問題のための機械学習手法

まずは前の章で挙げた具体例と同じ、(二値)分類問題のための具体的な手法を見てみましょう。機械学習の手法はさまざまありますが、一例としてパーセプトロンによる方法を見てみます。

パーセプトロン

判別アルゴリズム

パーセプトロンは、入力に対して重みづけをして和をとり、その正負で判別するというモデルです。ちょうど前の章で説明した「線形和で決まる」という仮説を使うものの一例です。

http://cdn-ak.f.st-hatena.com/images/fotolife/t/tarao/20160822/20160822155849.png

上図のように、各入力に対して重みを掛けて和をとったもの(線形和)の正負で判別するというアルゴリズムです。式で表すと以下のようになります。

f(\bm{x}) = \begin{cases}
 1 & \text{ if \(\bm{w} \cdot \bm{x} > 0 \)}  \\
-1 & \text{ otherwise } \\
\end{cases}
  • f : 判別アルゴリズム(正負で判別結果を表す)
  • \bm{x} : 入力の特徴量のベクトル
  • \bm{w} : 重みベクトル

判別対象は、たとえばi番目の語が出現しているかどうかのように、対象の特徴量x_iを集めたベクトル\bm{x}で表現します。その各x_iに、学習された重みw_iを掛けて、iについて足し合わせたもの(つまりw_iのベクトル\bm{w}と、ベクトル\bm{x}の内積)の正負で判別しようというわけです。

たとえば、(ラーメン, 京都, 京都郡, 博多, 東京都, ...)という単語の集合があったとして、学習された重みが\bm{w} = (10, 30, -50, -30, -30, \ldots)のとき、判別対象の文書「京都のラーメン」は単語の出現ベクトル\bm{x} = (1, 1, 0, 0, 0, \ldots)として表現できます。判別アルゴリズムに入力するとf(\bm{x}) = 10 \cdot 1 + 30 \cdot 1 = 40 > 0なので結果は1ということになります。

学習アルゴリズムでは、\bm{w}の値として正負の判別が正しくなるようなものを求めることになります。これはつまりy = \bm{w}\cdot\bm{x}が入力ベクトル空間を2つの領域に分割する超平面だとおもったとき、正負の判別が同じになるべき点が同じ側の領域に属するようにする、ということです。このときy = \bm{w}\cdot\bm{x}のままでは原点を通るような超平面にしかなりえないので、実際の入力とは無関係な固定値の項(ふつうx_0 = 1にする)を与えて、この項に対する重みw_0も学習することによって任意の超平面を表せるようにします(そして\bm{x}や\bm{w}にはx_0やw_0も含んでいるものとして扱います)。このようなw_0 x_0をバイアス項と呼びます。バイアス項はy=\bm{w}\cdot\bm{x}のグラフのy切片になっています。

学習アルゴリズム

パーセプトロンの学習アルゴリズムでは、まず適当な重み\bm{w}を決めて、サンプルデータを正しく判別できるように\bm{w}の値を更新していきます。現在の重みの値でうまく判別できた場合はとくになにもせず、判別に失敗したサンプルがあった場合にはそのサンプルを使ってフィードバックをかけていくという方法です。

あるサンプル\bm{x}の正しい判別結果がy \in \set{1, -1}だとすると、y \cdot f(\bm{x})の値は、\bm{x}を正しく判別できれば1に、間違えば-1になります。y=1で間違えたときは\bm{w} \cdot \bm{x}がもっと大きい方がより正解に近づくはずです。y=-1で間違えたときは\bm{w} \cdot \bm{x}がもっと小さい方がより正解に近づくはずです。そのためには、\bm{w}のうち\bm{x}と掛けたときに寄与する要素に関してyの符号に応じて足したり引いたりすればよいでしょう。

\bm{w} \leftarrow h(\bm{x}, y, \bm{w})

h(\bm{x}, y, \bm{w}) = \begin{cases}
\bm{w}           & \text{ if \(y \cdot f(\bm{x}) > 0\)} \\
\bm{w} + y\bm{x} & \text{ otherwise } \\
\end{cases}

これを何度も繰り返すことでよい\bm{w}を得るというのがパーセプトロンの学習アルゴリズムです。

非常に簡単なしくみですが、それゆえ欠点もあります。パーセプトロンはそもそも「線形和で決まる」という仮説を置いていて、この仮説の下ではうまくいきます。より専門的な言い方をすると、パーセプトロンのアルゴリズムは線形分離可能な場合には最適値に収束していくことが知られています。しかし、線形分離不可能な場合、つまり「線形和で決まる」仮説が成り立たない場合にはうまくいきません。

仮説が成り立つ場合でも、重みを更新する際に入力\bm{x}の値をそのまま使ってしまうと更新幅が大きくなりすぎて、いい値に収束しないかもしれません。このために、実用的には\bm{w}+y\bm{x}ではなく学習率\etaを用いた\bm{w}+{\eta}y\bm{x}でフィードバックをかけることがあります。この\etaの値としては0.1や0.3といった1未満の固定値を用いるのが一般的です。

特徴量のとり方

形態素解析

ここまでの例でも、判別対象の入力として、単語集合中のi番目の語が文書中に出現しているか、という指標を用いてきました。このような指標を用いるためには、文書中から単語を切り出す操作が必要になります。とくに日本語の文章から単語を切り出すには、どこが語の切れ目なのかを判断する必要があります。また、日本語に限らず、活用語は原形にする、接尾辞は取り除くなどした方が扱いやすくなります。

このように、活用なども考慮しつつ語を切り出していく処理を形態素解析と言います。入力文書から機械学習に使える特徴量を得るには、前処理として形態素解析しておくのが一般的です。実際に形態素解析するにはそのためのツール、ライブラリを使うとよいでしょう。以下はよく使われるライブラリです。

量をともなう特徴

「単語が出現しているかどうか」というのは値が1もしくは0の特徴量でしたが、機械学習で使える特徴量は一般にはどんな値をとってもかまいません。たとえば、単語の出現回数を使った方がよい結果が得られる可能性もあります。

単語に限らず、文書の長さ、段落の数、書いた人の年齢など、わかっている情報はなんでも特徴量として用いることができます。もちろん判別基準として役に立たない特徴量もあるので、特徴量がたくさんあれば精度が上がるというものではありませんが、全く種類の異なる特徴量を使うことを躊躇する必要はありません。

ただし、異なる種類の特徴量がとりうる値の範囲が全く異なる場合は注意が必要です。たとえばいくつかの単語の出現回数とともに、文書の長さ(文字数)を特徴量として使うとしましょう。単語の出現回数は1回とか3回とか、せいぜい100回とかそのくらいでしょう。それに対して文書の長さはそれよりもずっと大きい1000とか2000とか、10000とかになるでしょう。こうなると、学習においても判別時の計算においても、文書の長さが結果に与える影響が著しく大きくなってしまい、うまく学習できないか、学習効率が悪くなります。

このような状況を避けるには、特徴量を変換して一定の範囲におさまるように調整しておきます。具体的には、ある特徴量x_iに以下のような変換を施します。

  • 正規化(normalization) : \displaystyle x_i \leftarrow \frac{x_i - m_i}{M_i - m_i}
    • m_i : 特徴x_iの最小値
    • M_i : 特徴x_iの最大値
    • 0から1の範囲におさまるように変換
  • 標準化(standardization) : \displaystyle x_i \leftarrow \frac{x_i - \mu_i}{\sigma_i}
    • \mu_i : 特徴x_iの平均値
    • \sigma_i : 特徴x_iの標準偏差
    • 標準正規分布に従うように変換

組み合わせ特徴量

ここまでは「入力の線形和で決まる」というモデルを見てきました。実は、モデルは線形なままでもちょっとした工夫で非線形な特徴も扱うことができます。

たとえば、単語a, bが出現するかどうかをそれぞれx_a, x_b \in \set{1, 0}で表現しているときに、aとb両方とも出現する場合を考慮に入れた方が、精度よく判別できそうだということになったとします。線形和のモデルそのままではこれは扱えません。そこで、以下のような特徴量x_{ab}を加えてみましょう。

\displaystyle x_{ab} := x_a x_b

このx_{ab}はやはり\set{1, 0}の値をとり、aとbが両方出現したときだけ1になります。このようなx_{ab}を加えた特徴量の線形和は

\displaystyle w_a x_a + w_b x_b  + w_{ab} x_{ab} + \cdots

のようになるので、もし特徴量x_{ab}が精度に大きく寄与するならばw_{ab}の絶対値が大きくなるように学習される、という寸法です。この式を元々の特徴量で表すと

\displaystyle w_a x_a + w_b x_b  + w_{ab} x_a x_b + \cdots

となり、確かに元々の特徴量に対して非線形になっていますね。

このようにして、元々の特徴量から計算できる別の特徴量を加えることで、任意の多項式が扱えることがわかります。さらに、和と積で表せるものだけでなく、たとえば元々の特徴量の対数(log)をとったものなども有用な場合があります。必要に応じてうまい特徴量を見つけましょう。

モデル

いったんここまでの話を整理しておきましょう。分類問題を機械学習で扱う際にはデータとして特徴量と正解のラベルの組(\bm{x}, y)が(複数)与えられます。「なにか賢い箱」があって、そこへデータを入力します。

\displaystyle \text{(賢い箱)} \leftarrow (\bm{x}, y)

この箱は特徴量\bm{x}だけを与えるとy'を出力します。

\displaystyle \bm{x} \overset{\text{入力}}{\longrightarrow} \text{(賢い箱)} \overset{\text{出力}}{\longrightarrow} y'

このときにy'に期待することはyの値に十分近いものになっていることです。けっきょくこの「賢い箱」はあらかじめ与えられたくさんの(\bm{x}, y)の関係を学習することで、できるだけyに近い予測値y'を出力することです。機械学習は、この「賢い箱」が既知の特徴量に対して正しい予測を与えるならば、未知の特徴量に対しても正しい予測を与えるという期待に基づいているということです。

このような「賢い箱」のふるまいを数学的に表現したものをモデルと言います。パーセプトロンは分類問題のためのモデルの一つです。

モデルは内部にいくつか(ときには数千以上)のパラメータ\bm{w}を持っていて、学習のフェーズではこの\bm{w}の値を更新します。

\displaystyle \bm{w} \leftarrow \text{パラメータ更新} \; h(\bm{x}, y, \bm{w}) \leftarrow (\bm{x}, y)

そして予測フェーズでは現在得られているパラメータ\bm{w}を用いて結果を出力します。

\displaystyle \bm{x} \rightarrow \text{予測} \; f(\bm{x}, \bm{w}) \rightarrow y'

機械学習の種類

教師あり学習

  • なんらかの正解を与えて学習させるという問題設定
    1. カテゴリのような質的変数 (qualitative variable)を予測する分類 (classification)
    2. 数値のような量的変数 (quantitative variable)を予測する回帰 (regression)
  • 機械学習アルゴリズムに予測させるために与える入力のことを特徴量 (feature) という
    • 統計の世界では説明変数 (explanatory variable)とも (逆に予測する対象を 目的変数 (target variable)という)
    • 自然言語処理(NLP)の世界では素性 (feature)といわれることが多い

分類 (質的変数の予測)

  • あらかじめクラス (class)もしくはカテゴリ (category)が決められている
  • 与えられたデータが、どれに含まれるかを予測する問題設定
  • 問題例
    • メールのスパムフィルタ (NLPの文書分類タスク)
      • メールの本文やヘッダの情報からメールがスパムかハムかを判定する
      • データセットの例 (英語)
    • 手書き数字認識 (画像処理)
      • 数字が書かれた画像から、その数字(0から9までのどれか)を判定する
      • データセットの例
  • 参考: 機械学習の分類の話 - Jupyter Notebook Viewer
  • 手法の例
    • パーセプトロン
    • ロジスティック回帰
    • サポートベクターマシン (SVM)
    • k近傍法
    • 決定木

回帰 (量的変数の予測)

  • データと予測したい値を関数の入力と出力に見立てて、特定の形の関数を既知の入出力にうまく当てはめる問題
    • 関数の形をモデルという
  • 問題例
    • 住宅の値段を予測する
      • データセットの例
        • Housing Data Set (ボストン近郊での、地域ごとの平均住宅価格)
    • 株価予測 (時系列解析)
  • 手法の例
    • 線形回帰
    • ニューラルネットワーク

教師あり学習でのデータセット

  • データセット: データ(事例)の集合、くらいの意味
    • 一つ一つの処理対象のデータは事例 (instance)という
    • メールのスパム判定なら1通のメールが、手書き数字認識なら1枚の画像が事例
    • NLPでは対象のデータセットのことをコーパス (corpus)と呼ぶこともある
  • 各データにはクラスラベル (class label)(もしくは単にラベル (label))がついている
    • ニューラルネットワーク界隈では教師信号ともいう
    • データを1つ与えたときに、アルゴリズムが出力すべきもの(カテゴリ、もしくは実数値、整数値など)

教師なし学習

  • 明示的な正解(ラベル)が与えられない問題設定
    1. クラスタリング: データを(未知の)グループに分ける
    2. 次元削減(次元圧縮): データの特徴量の次元を下げる
    3. 頻出パターンマイニング: データから法則性を見つける
    4. 異常値検出: データから統計的な外れ値を見つける

クラスタリング

次元削減(次元圧縮)

  • 高次元のデータを低次元に変換する(重要な基底だけが残る)
  • 応用例

頻出パターンマイニング

  • いわゆるデータマイニングの一種
    • 相関ルール分析: よく一緒に買われる商品(バスケット分析)

異常値検出

  • データ全体に統計モデルをあてはめて、そのモデルで稀にしか起きない事象を検出する
  • 応用例
    • 不正アクセスの検出
    • サーバの異常動作の検出

アルゴリズムの評価

機械学習を用いても、その学習結果が未知のデータに対して正しい結果を出すものになっている保証はありません。むしろ、正しい結果を出せるように、データの与え方やモデルを調整していくのが肝です。この章では学習結果の評価と、どういった改善をすればいいかのヒントを見ていきましょう。

学習結果を評価する基本的な方法は、学習結果のパラメータを用いてアルゴリズムを既知のデータに対して走らせ、正しい答えを出すか、誤差がどれくらいかを測定することです。誤差は分類の場合は正しく分類できなかったデータの割合(誤り率)、回帰の場合は二乗誤差などを用いるとよいでしょう。

訓練データとテストデータ

学習に用いたデータ(訓練データ)の誤差を測っても、未知のデータに対してどれくらいの性能が発揮されるのかわかりません。そこで、既知のデータを訓練データとテストデータに分けて、学習に用いるのは訓練データの方だけにするのが一般的です。

訓練データ、テストデータともに誤差が小さい方が学習がうまくいったことになりますが、ふつうは訓練データの誤差の方がテストデータの誤差より小さくなります。それぞれの誤差が大きく出たときに考えられる原因は以下の通りです。

  • 訓練データの誤差が大きいとき
    • データの数が不足している
    • 特徴量の数が不足している
    • モデルが適切でない
  • テストデータの誤差が大きいとき
    • データの数が不足している
    • 特徴量の数が不足している
    • 過学習してしまった

たとえば、訓練データとして与えられたものは正確に記憶して与えられた通りの結果を返し、それ以外のデータに対しては常に1を返す、というアルゴリズムを実装することは可能です。この場合、訓練データの誤差は0になりますが、テストデータに対してはあまりいい結果が得られないでしょう。テストデータ(未知のデータ)に対しての誤差(汎化誤差という)が少ないモデルは「汎化性能が高い」と言い、機械学習アルゴリズムの目的は汎化性能の高いモデルとそのパラメータの獲得ということになります。

学習曲線による分析

もう少し細かく分析するには、データ数を増やしていったときの誤差をプロットしていくとよいでしょう。データ数を横軸に、訓練データとテストデータの誤差を縦軸にプロットしたグラフ(学習曲線)の形によって、どういう原因で精度が出ていないかがわかります。(あるいは、誤り率の代わりに精度をプロットしても、グラフが上下逆さになるだけで同じ分析が可能です。)

学習曲線は典型的には右のような形になります。データが増えると訓練データに完全にフィットする学習が難しくなるため訓練データの誤差は上昇しますが、さらに増えると訓練データのバリエーションも減ってくるため上げ止まります。テストデータの誤差は訓練すればするほど下がっていきますが、ある程度のところで下げ止まります。

理想的な形は、訓練データの誤差が低いところで一定の値に収束し、テストデータの誤差がそれよりもほんの少しだけ高い値に収束している状態です。この場合、学習はうまくいっていて、未知のデータに対しても高精度な結果を出せることが期待できます。

学習が不十分な場合、学習曲線のグラフの形が以下の3つのどれに分類されるかで、改善すべきポイントがわかります。

一番大きなデータ数でもまだグラフの傾きが大きいとき

  • 原因
    • データの数が不足
  • 改善策
    • データの数を増やす
    • 訓練データの誤差が大きい場合は高バイアスの場合も参照

十分にデータの数が揃わないうちは誤差が収束していきません。

高バイアス : 訓練データの誤差が大きいとき

  • 原因
    • 学習結果が訓練データに対してアンダーフィット
      • 特徴量が不足している
      • そもそもモデルが適切でない
  • 改善策
    • 特徴量を増やす
    • モデルの見直し

高バイアスなグラフになっている場合、学習が不十分なのでより効果的な特徴量を見つけるか、モデルを見直す必要があります。

高バリアンス : テストデータと訓練データの誤差のひらきが大きいとき

  • 原因
    • 学習結果が訓練データに対してオーバーフィット (過学習状態)
  • 改善策
    • 訓練データを増やす
    • 正則化する

一般に、高バイアスが是正されると相対的に高バリアンスな状態となり、高バリアンスが是正されると相対的に高バイアスな状態になります。

適合率と再現率

二値分類問題においてデータ中の正例(ラベルが+1のもの)と負例(ラベルが-1のもの)の数に偏りがある場合、単純な誤り率を用いた学習曲線の分析はうまくいかなくなる場合があります。たとえば、1000件のデータの中に正例が3件しかない場合、常にNoと答えるアルゴリズムの誤り率は0.3%になり、一見精度がよさそうということになってしまいます。

このような場合に備えて、単純な誤り率ではなく適合率と再現率を考えましょう。

適合率

アルゴリズムが正と判定したもののうち、実際に正例だったものの割合を適合率と言います。偽陽性(false positive)の少なさを意味します。

\displaystyle \text{Precision} = \frac{tp}{tp + fp}
  • tp : 判定結果も実際のデータも正だった数 (true positive)
  • fp : 判定結果は正だが実際のデータは負だった数 (false positive)
  • tp + fp : アルゴリズムが正と判定した数

再現率

データ中の正例のうちで、アルゴリズムが正と判定したものの割合を再現率と言います。偽陰性(false negative)の少なさを意味します。

\displaystyle \text{Recall} = \frac{tp}{tp + fn}
  • tp : 判定結果も実際のデータも正だった数 (true positive)
  • fn : 判定結果は負だが実際のデータは正だった数 (false negative)
  • tp + fn : 実際のデータの正例の数

F値

適合率と再現率はふつうトレードオフの関係にあり、どちらかを上げるようにチューニングするともう片方は下がる傾向にあります。このため、学習曲線による分析の際に誤り率の代わりに適合率または再現率(の逆数)を使ったとしてもうまくいかないでしょう。

そこで、適合率と再現率どちらもよければ高くなり、どちらかが低ければ低くなるような指標を用いればよいでしょう。このような性質のものとしてよく知られているものにF値があります。

\displaystyle F_1 = 2\cdot\frac{\text{precision}\cdot\text{recall}}{\text{precision}+\text{recall}}

この値の逆数を誤り率の代わりに用いれば、偏りのあるデータに対しても適切な分析・チューニングが可能となります。

場合によっては再現率は多少犠牲にしてでも適合率を優先したいこともあるでしょう。そういう場合には適合率が優先されるような指標をうまく定義してチューニングしましょう。

課題

0. リポジトリとデータの準備 (必須)

  1. 課題用の雛形perl-Intern-Machine-Learning (Perl版)もしくはscala-Intern-Machine-Learning (Scala版)をforkして手元にgit cloneしてください
  2. UCI Machine Learning RepositoryのIris Data Setからアヤメ種類とその種類の個体がもつ特徴のデータをダウンロードして、iris.dataとして保存してください
    • データはCSV形式で1行が1個体に対応します
    • 各行のフィールドは左から順に萼片(がくへん)の長さ、幅、花弁の長さ、幅、アヤメの種類となっています (幅や長さの単位はcmです)
    • アヤメの種類はIris-setosa, Iris-versicolor, Iris-virginicaのいずれかです
    • データはぜんぶで150行(150個体分)あり、各種類ごとに50件ずつです

  3. iris.dataの行をランダムな順序に入れ替え、100件を訓練データiris.training.data、50件をテストデータiris.test.dataとして保存してください

    • shufコマンド(Mac OS Xの場合はbrew install coreutilsした上でgshuf)を使うとランダムな順序に並べ替えることができます

    $ shuf iris.data > iris.shuf.data
$ head -n 100 iris.shuf.data > iris.training.data
$ tail -n 50 iris.shuf.data > iris.test.data

1. F値の計算 (必須)

  • Intern::ML::Evaluation::F1(Perl版)もしくはintern.ml.evaluation.F1(Scala版)のaddメソッドおよびaccuracyメソッドを実装してください
    • addには、ある判別対象に対する判別アルゴリズムによる結果のラベルと、その対象の正解ラベルが渡されます
    • ラベルはIntern::ML::Model::Label(Perl版)もしくはintern.ml.types.Label(Scala版)のインスタンスです
    • accuracyは、これまでにaddされた判別結果のF値(F_1)を計算して返すようにしてください
  • (ヒント) 正しく実装できていればscript/run f1コマンドがおよそ0.545455の値を出力するはずです

2. パーセプトロンの実装 (必須)

  • Intern::ML::Classification::Perceptron(Perl版)もしくはintern.ml.classification.Perceptron(Scala版)のtrainメソッド(学習アルゴリズム)およびpredictメソッド(判別アルゴリズム)を実装してください
    • trainメソッドには学習すべきデータがリストで渡されます
      • (Perl版) リストの各要素はfeaturesに特徴量の配列リファレンスを、labelに教師ラベル(Intern::ML::Model::Labelのインスタンス)をもつハッシュリファレンスです
      • (Scala版) リストの各要素は特徴量のリストと教師ラベルの組です
    • predictメソッドには1件の判別対象が、特徴量のリストとして渡されます
  • (ヒント) うまく実装できていればscript/run iris iris.training.data iris.test.dataを実行することで1.0に近い値が2つ出力されます
    • 値は訓練データのF値とテストデータのF値です
    • これは、Iris-setosaをPositive、それ以外をNegativeとして二値分類した結果です

3. 学習曲線の表示 (必須)

  • script/iterate 100 iris iris.training.data iris.test.data > iris.learning-curve.pltを実行して学習曲線のデータを出力してください (iris.learning-curve.pltはリポジトリに含めてください)
  • (ヒント) script/iterate 100 iris iris.training.data iris.test.data | script/plotとすると学習曲線のグラフを表示できます
    • ただし表示にはgnuplotが必要です

4. 多値分類器の実装 (オプショナル)

  • script/run irisコマンド(Intern::ML::CLI::Iris(Perl版)もしくはintern.ml.cli.Iris(Scala版))を参考に、アヤメを3つの種類のいずれかに分類するコマンドscript/run irismultiを実装してください
  • コマンドの入出力形式は任意です
  • (ヒント) 二値分類器の実装方法しか解説していませんが、Iris-setosaとそれ以外を区別する分類器(2.で実装したもの)、Iris-versicolorとそれ以外を区別する分類器、Iris-virginicaとそれ以外を区別する分類器をべつべつに実装して、3つの結果をうまい具合に統合する、という方法で三値分類器を実装することができます(1-vs.-allなどと呼ばれる方法)
  • (ヒント) アヤメの種類の中にはそのままの特徴量では線形分離可能でないものも含まれているので、綺麗に分類するには以下のいずれかの対応が必要でしょう
    • パーセプトロン以外の方法を使う
    • データを前処理して組み合わせ特徴量を使う