読者です 読者をやめる 読者になる 読者になる

ひだまりソケットは壊れない

ソフトウェア開発に関する話を書きます。 最近は主に Android アプリ、Windows アプリ (UWP アプリ)、Java 関係です。

まじめなことを書くつもりでやっています。 適当なことは 「一角獣は夜に啼く」 に書いています。

読んだ: 集合知プログラミング

書籍 レビュー 書評 アルゴリズム

ユーザーへの推薦やカテゴリ分類、いわゆるデータマイニングに興味があったので読みました。

集合知プログラミング

集合知プログラミング

本書では集合知について次のように書かれています。

人々は集合知という言葉を長い間使い続けてきた。 それは新たなコミュニケーション技術の到来とともに、ますます人気と重要性を増して来ている。 集合知という表現は、集団の意識や超常現象を想起させるが、技術者がこの表現を使う場合は、今までにない知性を生み出すために、集団の振る舞い、嗜好、アイデアを結びつけることを指す。

『集合知プログラミング』 1.1 節 「集合知とは何か?」

本書は、何らかの集団 (例えば web ページの集合) を分類したり、集団の中から特定のユーザーに推薦すべきものを決定したり、集団から検索したり、といったことについて基本的な手法を述べるものです。 特に web サービス上に存在する集団に対して適用されることが念頭に置かれた説明が多く、web サービス開発に携わっている人であれば応用できる箇所を具体的に連想しながら読み進めていくことができると思います。

内容的には初心者向けという感じですので、本書を読むにあたって統計や機械学習についての基礎的な知識を持っている必要はありません。

内容紹介

1 章は序章で、「集合知とは何か」 というような話や、機械学習についてや学習アルゴリズムについて書かれています。

2 章から 11 章までは、具体的な問題を設定し、それを解決するために種々のアルゴリズムが紹介されます。 実際のコードも豊富に用意されていて、全体的に理解しやすい内容になっています。 ちなみにコードは Python で書かれています。

12 章では、本書で紹介されているアルゴリズムがまとめられています。

アルゴリズムまとめ

12 章では、本書で出てきたアルゴリズム一覧がまとめられています。 ここでも、簡単にアルゴリズムをまとめておきます。

ベイジアン分類器

ベイジアン分類器は、特徴のリスト (例えば文書中に頻出する単語のリスト、など、対象となる項目に含まれるか否か簡単に判別できるもの) を抽出できる項目の集合に対して作用させることができるものです。 本書では、スパムフィルタリングや、カテゴリ分類などの文書分類システムを作成するという文脈で紹介されていました。

ベイジアン分類器の長所は、トレーニングの速度と巨大なデータセットに対する問い合わせの速度が速いことです。 また、学習結果の解釈も容易という点も利点です。 トレーニングの際には過去のトレーニングデータを必要としません。 欠点としては、複数の特徴の組み合わせを元に分類する、ということができないことです (特徴はそれぞれ独立している)。

決定木による分類器

yes/no で答えられる質問がノードになっていて、末端に項目の集合がある、というような二分木を決定木といいます。 末端の項目の集合がなんらかのグループであるように決定木を作れば、その決定木を使って項目の分類ができます。 「アキネイター」 なんかは末端の項目数が 1 であるような決定木という感じがしますね (内部的にどうなってるのかわかんないですが)。

決定木を作る時は、各ノードの質問を何にするかを決定する方法が重要になります。 質問による集団の分割で情報量が最も多くなるように、各ノードの質問を決めていきます。 (分割前のエントロピーから分割後の 2 つの集団の各エントロピーの合計を引くことで、情報ゲインを計算する。)

決定木の利点として大きなものは、学習済みの決定木を使うことが容易なことです。 決定木を図にしてしまえば、人が見るだけで新しい項目がどこに分類されるのかすぐにわかります。 また、入力データとして数値を使用することもできます。

新たに項目を追加して決定木を作り直したい場合は、過去のトレーニングの結果に追加するというようなことはできず、すべての項目を対象にして決定木を一から作り直す必要があります。

ニューラルネットワーク

ニューラルネットワークは、分類器にも応用できますし、数値を予測する問題に適用することもできます。

ニューラルネットワークは、複数の入力 (例えば web ページを検索するためのキーワードのリスト) があった場合に、重みづけされた複数の項目 (例えば web ページの検索結果の URL 一覧) を出力するというものです。 入力と出力の間には 1 つ以上の隠れニューロン層があることが 「ニューラルネットワーク」 という名前の由来だそうです。 (言葉で書かれていてもわかりづらいと思いますが、図で表すとわかりやすいので気になる人は適当に調べてください。)

入力と出力の間に隠れ層が存在する、というのが重要で、入力と出力が直接的ではなく間接的に結び付いていることで、「入力の組み合わせ」 というものに対応できるようになっています。

利点としては、入力として 1 か 0 の値 (存在するかどうか) だけでなく、任意の数値をとることができるという点や、トレーニングを継続的に行うことができるという点があります (既にある決定木に新しいトレーニングデータを追加するさいに一からやり直す、というような決定木のようなことはする必要がない)。 欠点としては、入力から出力に至る流れが複雑で、(ベイジアン分類器や決定木と比べて) 解釈が困難である、という点があります。 ネットワークのサイズやトレーニング率を決める確固たるルールがないことも欠点としてあるようです。

サポートベクトルマシン (SVM)

『多分、本書でカバーする手法の中でもっとも洗練されたものだろう』 と書かれています。

SVM は、多次元空間上に分布する対象項目を分類するための超平面を探す、というものですが、最終的に導き出される超平面はマージン最大のものになっているという点が特徴です。 超平面を探した後は、新しい項目について超平面のどちらに属しているかを調べることで分類を行います。

計算にはドット積が使われるのですが、その際にカーネルトリックという技術が使われます。 詳細は割愛。

利点としては、非常にパワフルな分類器で、正しいパラメータを与えることで、本書で紹介されている他の手法と同等程度かそれ以上にうまく動作するという点があります。 また、分類の際には超平面のどちら側に点があるかを調べるだけなので、新たな観測値の分類が高速であるということがあります。 欠点としては、最良のカーネル変換関数とそのパラメータが、データセットごとに異なっているので、毎回それらを探す必要があるということがあります。 また、ニューラルネットワークと同様に、ブラックボックス的な技術ということもあります。 データが高次元で扱われるため、実際にどうやって分類されているかを解釈することは難しいです。

決定木のような他の手法は、小さなデータセットに対しても興味深い情報を生み出しますが、SVM は一般的に巨大なデータセットに対して非常に有効な手法です。

K 近傍法

特定の商品の価格がどの程度になるのかを予想するための手法として、本書では K 近傍法が紹介されていました。

価格を知りたい商品と、既に価格を知っている商品とで似ている度合いを調べ、最も似ている K 個の商品の価格の平均 (あるいは重みづけ平均) を取ることで対象の商品の価格を予想する、という感じの手法です。

似ている度合いの計算などには込み入った関数が使われるものの、解釈が容易です。 データが変わっても再トレーニングする必要はありません。 ここら辺は K 近傍法の利点です。

欠点としては、予測を立てるためにすべてのトレーニングデータが必要で、数百万もあるような巨大なデータセットを使う場合は、スペースが必要というだけでなく実行時間の問題となります。 また、特徴ごとの重み (縮尺係数) を決定するのに長い時間がかかることがあることも欠点のひとつです。

クラスタリング

クラスタリングの教師無し学習の技術として、本書では階層的クラスタリングと K 平均法クラスタリングが紹介されています。

階層的クラスタリングは、それぞれの項目が 1 つのクラスタに属している状態から開始し、クラスタの中心位置 (そのクラスタに含まれる項目すべての平均) が最も近い 2 つのクラスタをマージして新たなクラスタを作る、ということを繰り返してクラスタリングしていきます。 結果としては項目のツリーができあがります。

K 平均法クラスタリングは、予めグループ数を決めておき (グループ数を K とする)、項目の集団が属するの空間中に適当に K 個の点を配置して、それらの点を (項目との距離を使って移動位置を決めて) 動かすということを繰り返していきます。 最終的に、これらの点がクラスタの中心となります。

多次元尺度構成法

これも教師無し学習の技術です。 予測を行うのではなく、さまざまな項目がどのように関係しているかを理解するための助けをします。

多次元空間上で表現されるデータセットの項目間の距離をできるだけ保ったまま、より低次元の空間でデータセットを表現する (例えば画面上で表現するために 2 次元にする)、というものです。

非負値行列因子分解 (NMF: non-negative matrix factorization)

非負値行列というのは、非負値のみからなる行列です。 そのような行列を因子分解するというのが非負値行列因子分解です。 (そのまんまですね。)

で、これが何かというと、例えば各行が項目 (例えばブログ記事) を表していて、各列が何らかの実データ (例えば文書中に頻出する単語の個数) を表していると行列が存在する場合、それを因子分解することで特徴の行列と重みの行列が得られる、という感じで使うことができます。

NMF 自体は、もともと画像処理の分野で有名になったものみたいですね。

最適化

旅費と空港での待ち時間を最適な感じにするように旅行の行程を決定する、とか、学生の部屋割りを最適にする、とか、そういう問題の最適化の手法として、模擬アニーリングと遺伝アルゴリズムが紹介されています。 何をもって最適とみなすかは、こちらが与えたコスト関数により決定されます。 (コスト関数の出力が最小になるものが最適。)

このような最適化の問題で困難なのは、パラメータを少しずつ変化させていって最小になるところを探す、というような方法だと、局所最小にいたりはするものの大域最小にいたらないことがあることです。

模擬アニーリングは、ランダムに推測した解からスタートして、ランダムな方向、小さな距離にパラメータを移した類似解のコストを計算して解を改善していく、というものです。 コストが高いうちは、移動先のコストの方が高くても一定の確率でそれを新しい解とします。 コストが小さくなっていくにしたがって、移動前よりも高いコストの解を採用する確率は小さくなっていきます。 これは、物理学における合金の冷却に触発されたアルゴリズムらしいです。

もうひとつの遺伝アルゴリズムの方は、個体群と呼ばれる複数の無作為解からスタートし、個体群中のいくつかの良い解を選択し、それらを元に突然変異させた個体や、組み合わせ交叉させた個体を生み出し、それらを次の世代の個体群とする、ということを繰り返していくものです。 世代を重ねることで改善されていきます。

感想

集合知」 という言葉は数年前の流行言葉という印象があって、使われる場面によっては非常に夢見がちな何かであったりすることもあると思うのですが、当然ながら本書はエンジニアリングのための地に足のついた書籍です。 Web サービスを開発していると、ユーザーに対して推薦を行いたいということや文書などをカテゴリ分類したいということがよくあると思うのですが、そういったことを行うための手法について初心者向けに書かれていますし、問題設定も 「web サービスを使用する」 ことを前提にしたものが多いですので、web サービスに関わる人にとってはわかりやすいしとっつきやすいと思います。

「ユーザーへの推薦をしたい」 とか 「カテゴリ分類したい」 とかそういうことを思ってるけど具体的にどこから手を付けたらいいかわからない、というような人がまずは読んでみる本として適していると思いました。 数式などのアルゴリズム部分の詳細まではそんなに立ち入っていない (全然ないわけではないですが) ので、そういう詳しい部分については別の書籍や論文などを追っていけばよいでしょう。

非常にためになったし読んで良かったです。

集合知プログラミング

集合知プログラミング