catalinaの備忘録

ソフトウェアやハードウェアの備忘録。後で逆引きできるように。

機械学習における回帰と分類について考える

雑記

暑かったり寒かったりと体調を崩しやすい時期ですね。かたりぃなです。 機械学習について勉強していますが、まずは基礎的な問題として分類と回帰について考えてみます。 wikipediaや以前買った書籍(PRML)を見ても理論の大半は数式で表されていましたが、ここではできるだけ言葉で整理します。 自分の言葉で表現することによって数式の厳密性は失われますが、私自身の理解を深めることになると思っています。 特に自分自身が経験してきた仕事の内容で比喩することで考えを整理していくきっかけになると思います。 (そもそも本の内容をただコピペしてしまうと著作権的にも問題になりますし。)

回帰と分類

教師あり学習 - Wikipedia

教師あり学習における回帰と分類はそれぞれ以下のように解釈できます。

入力値と出力値のペアが与えられたとき、この入出力の間にある変換を求めることです。 出力値が連続な場合は回帰、離散値の場合は分類になります。 そしてこの変換を求めることが学習になります。

とは言っても抽象的でつかみづらいので実際の例をもとにもう少し概念を掘り下げてみます。

回帰

組み込みソフトウェアの開発現場での話ですが、あの分野では性能や品質が重視されます。 その背景には

  • ソフトウェアのアップデートが簡単にはできない
  • 性能要件を満たさないと製品として世に出すことができない
  • 不具合が起きた分野によってはリコールや訴訟、そしてブランドイメージの低下などの大きな被害となりうる

などがあります。 インターネットに接続されている機器であればネット経由でのバージョンアップによる修正という余地はありますが、バージョンアップ対象のモジュールによってはアップデート自体がリスクとなりうるケースもあります。 具体的な例として、カーネル本体やファイルシステム、周辺機器のデバイスドライバなどをアップデートするには相応のリスクが伴います。 (アップデート中に電源を切られると、ユーザーランド上のアプリケーションならやり直せますが、カーネルやファイルシステムなんかをアップデート中にそんなことされてしまうと、何が起きるかわからない)

私が回帰による分析というものに初めて触れたのがこの品質周りの課題について調べている時でした。 ソフトウェアのバグを取り除いていったとしても、一般にハードウェアは経年劣化というものがついてまわります。 物理的な動作が含まれるハードウェアはもちろんですし、外見上は物理的な動作を含まないように見えるデバイスも劣化が進みます。 フラッシュメモリなどの書き込み回数の上限などがその一例ともいえます。

このような劣化の要因・品質特性を調べるとき、劣化による影響がどのように現れるのかを考えると

  • 劣化の原因は何か
  • 劣化すると何がおきるのか
  • 劣化の速度はどれくらいなのか
  • 工場出荷時の品質はどのくらいのものなのか

などがすぐ思いつきます。 これを分析する最も基本的なものが線形回帰による分析です。回帰直線などを求めるアルゴリズムとしては最小二乗法などが有名です。

話を簡単にするために、上記の品質の例をY=aX+b　という中学数学で習う比例のグラフにあてはめられるという前提のもとで考えることにします。 劣化の要因は経年劣化であるとします。すると工場出荷時の品質が切片bであり、劣化の速度が傾きaとして表現できます。また劣化の要因は経年劣化なので機器の実稼働時間とします。 すると、

ある期間稼働した時点での品質(Y)＝ 劣化の速度(a) x 実稼働時間(X) + 出荷時の品質(b)

となります。 あとはどのくらい劣化したら品質を保てなくなるのか(摩耗劣化であれば、機器から異音がし始める時期など)を推測できます。 これで品質特性がわかった！とはできないのが世の中というものです。 実際にこれをそのまま使ってしまった場合の問題点として

  • 関係(この例ではY=aX+b)の前提が無いことが多い(測定して分析するまではどのような式が近似に適しているかわからない)
  • 影響している要因(品質工学でいう因子、今回の例では経年劣化)が何であるのかが不明であること

があります。それぞれの問題点について個別に考えていきます。 まずは式そのものについて考えると、例えばY=aX2+bという特性かもしれないし、もっと複雑な次数で表される特性かもしれません。 品質特性についてはバスタブ曲線と呼ばれるグラフ形状が有名です。

影響している要因について、実際には稼働時間ではなくて電源ON/OFF回数が影響していた場合などが考えられます。 要因(品質工学的に因子と呼ばれる)特定するには、デバイスのデータシートにそれら示されていることもありますが、データシート記載の実験環境と実運用環境は往々にして異なるので、そういったものに関してはリスクとコストを天秤にかけたうえで実験・測定する必要があります。 しかしながら、劣化に関する実験と測定を行うには多大な時間がかかります。これは摩耗劣化の例でわかるかと思います。

こういった要因を考えるのは非常に難しいもので、実際に測定してみないと何が影響しているか判断しづらい場面というものが多々あります。システムが複雑化している最近のデジタル家電なんか特にそうです。 こういった難しさというものはタグチメソッドの田口玄一氏の有名な言葉「技術者の最大欠陥は何が起きるのかわからないと手を打てないということだ」でよく表されるものだと思います。

話が発散しそうなのでここで回帰とは何かをもう一度整理すると、

  • 関係Y=aX+bなどを求めること(そもそもこの式自体を求めることも含めて)が回帰である
  • 求めた式を使って予測することが回帰からの推論である(何年後くらいに壊れることが予想されるか)

と理解できます。 製品の品質という課題については品質工学(タグチメソッドや実験計画法など)の分野になるのでここで終わります。 ここまでの考えをもとに機械学習の観点から見てみると、

  • 上記の式の右辺にあたるもの(関数)を求めることが学習である(Y=3X+2であるなど)
  • 求めた関数を使って予測を行うことが推論である(Y=3X+2という学習結果があれば、未知の値Xが与えられても目的変数Yを求められる)

といえます。 機械学習の分野で学習(学習段階)と決定(推論段階)が分けて考えられている理由も納得できました。

分類

回帰における目的変数Yが離散的な場合が分類と呼ばれる問題です。 といっても抽象的すぎるので、具体例で考えます。

身近な例ではゲームにおける当たり判定が分類問題として扱うことができます。 話を簡単にするために2Dゲームの矩形で考えます。 当たり判定の基本となるアルゴリズムは矩形と矩形の重なった領域があるかどうかです。 重なった領域があればヒット、なければノーヒットです。 ここで目的変数Yが「当たった、当たっていない」であり、離散値は２値でヒット、ノーヒット(プログラム的表現するならばbool値)です。

単純なゲームであればすべての矩形の当たり判定をチェックすることで目的は十分に達成できます。 しかしCAVE(怒首領蜂など)や東方などに代表される弾幕シューティングのように、判定を行う対象物が数百とか数千の敵弾といったことになると少し工夫する必要が出てきます。 画面上にある数千の弾丸すべてを毎映像フレームごとにチェックするのは厳しいでしょう。スマホやタブレットのCPUなどでは尚のことです。 私がこの問題について考えていた当初はもっと貧弱なCPU環境でした(Pentium-133MHz、SSEはおろかMMXもない時代)。

限られたCPUやメモリ資源の中でこの問題を解決するには、全部の当たり判定を総当たりで処理していくのではなく「当たっているかもしれない」対象物を絞り込みができればよさそうです(そもそも計算する必要すらなくなる)。 これはパターン認識や機械学習の分野からみると、ブースティングの一例として考えられます。 ブースティングの基本的な考え方は「弱い識別機をたくさんくっつけて(カスケードして)強い識別機をつくれないだろうか」といったもので、 顔認識で有名なhaar-like分類器などがこれに該当します。

話を戻して、弾幕の当たり判定を弱い識別機で効率よくやるにはどうするか考えてみます。 具体例として、画面サイズは1600x1200, 弾丸の判定は2x2ドット, 自機の食らい判定は4x4ドット、画面上の敵弾の数は10000の一様分布としてみます。 総当たりで計算すると10000回の矩形判定をすることになって大変なので、まずは弱い識別機でふるいにかけます。 やり方は色々ありますが、ここでは画面全体から分割して考えることにします。 まず画面全体に対して自機の位置が右下隅に追い詰められているとしてp(1500,1100)にいるとしたとき、まず左半分にある弾丸には当たるわけがないので、 敵弾のX座標値が800以下のものは処理しないことにします。これで判定対象は1/2にまで減りました。 Y座標についても同様にして、判定対象はさらに1/2になります。 こうすることで、画面全体の10000個だったものを1/4、つまり2500個にまで絞り込むことができました。 これを必要な限り繰り返すことで、当たり判定を行う候補を絞り込んでいきます。 ポイントは、最初に大きなふるいにかけるので、自機から遠い弾丸にほど早い段階で判定から取り除かれることになります。

と言ってもこの例ではさほど高速化はできません。 もともとが矩形同士の当たり判定という単純な処理なので、絞り込む段階でやっている判定内容は、詳細な当たり判定チェックと同等になってしまうからです。

機械学習から少しそれますが、せっかく振り返ったので書いてみます。 じゃあ、どうやったら高速に処理できるか考えていた当初の記憶を振り返ってみると、分岐予測が外れたときのペナルティが大きすぎるので、できるだけ分岐処理(C/C++でいうif)を行わないのが理想でした。 結論としては、画面上をマスで分割(16x16とか)して、どこのマスに入っているかを弾丸の移動段階であらかじめ求めておき、当たり判定の段階では自機の入っているマスの弾丸のみ当たり判定を行うといったものでした。 たとえば1600x1200の画面を16x16のマスに区切ると、100x75個のマスで画面上を表現できるので、所属するマスを決める処理自体は分岐予測も除算も使わずに記述できるというわけですね。 たとえばこんな風に。(xpos,yposともに16bit幅という前提で書いてます。)

x_index = (xpos & 0xFF00) >> 8;
y_index = (ypos & 0xFF00) >> 8;
table[x_index][y_index] = ごにょごにょ;

マスのサイズを16x16にしたのはここでの演算を高速にするためのもので、マスクとシフトだけで済ませられます。 機種依存していいなら上記のコードよりもさらに早くxposとyposの上位8bitをテーブル参照のインデックスとして使うだけで済みます。(x86アセンブラ的にやるとahかalレジスタ読むだけで済んでいた気がします) あとは自機が所属するマスを求めて、そこのマスに入っている弾丸とだけ当たってるかどうか調べれば済みます。 自機がマスを跨いでいると面倒だった記憶があります。(とはいっても、この例では最大4マスチェックすれば済みますが)

このマスに区切って考えるという方法は2Dゲームの例では非常に有効ですが、機械学習という観点からは次元の呪いという問題にハマることになります。 機械学習では入力データは2Dゲームの例よりももっと次元数が高くなる(たとえば16x16pixelを256次元のベクトルデータとして扱うなど)ので、この方法をそのまま使うことは現実的でなくなってしまいます。

感想と展望

よくよく考えるとこのエントリ自体が回帰分析の一種として考えられそうです。 回帰分析をしていた当時は諸事情もあって限られた範囲内での分析しか行えませんでしたが、今やるとしたらもっと色々試せる気がします。 具体的には

  • 統計結果がある分布に従うことがわかったとき、出荷台数をもとに数年後の修理台数やコストを予測する
  • 予測されるコストをもとに品質保証にかけるコストとのトレードオフを算出する

などがありそうです。

話ついでに。PRMLの下巻買ってみました。 上巻よりさらに手ごわくなった内容ですが色々と興味深い内容ですので、色々試しつつも整理していきたいと思います。 上下巻を比較すると上巻が基礎理論、下巻が実用に向けてのさらに発展した内容＋実例といった内容です。

なんか長くなってしまったので今回はこれくらいで。