推薦システム(レコメンドエンジン)の作成法

あなたが買ったものはBさんも買っています。Bさんが買った他の商品Xはいかがでしょうか?

こうした事をAmazonではよく見かけます。これは推薦エンジンとよばれており、もっと一般的には協調フィルタリングなんて呼ばれたりします。

協調フィルタリング(collaborative filtering)による推薦システムの作り方は意外と簡単です。どうやったらできるのか、その方法を説明します。

アイテムベース

アイテムベースの推薦です。アイテムベースとは、以下のようなことです。

  • Aさんが好きなアイテムXがあるとする。
  • アイテムXと似ているアイテム順に列挙する

つまり、特定のアイテムと似ているアイテムを探します。コレ以外の方補でユーザーベースのがあります。どちらも一長一短がありますが、アイテムが少ない場合にはアイテムベースを用いるといいでしょう。

推薦システム(アイテムベース)

データベースの構造は以下のようになっていると仮定します。

・ pref[ アイテム名 ][ ユーザ名 ] = 類似度

例) ドメストとサンポールの類似度

斎藤、加藤、古澤、田中がドメストとサンポールをそれぞれ評価します。

pref[ 'ドメスト' ] = { ‘斉藤’: 10.29, ‘加藤’: 8.72, ‘古澤’: 7.78 } 
pref[ 'サンポール' ] = { ‘斉藤’: 5.29, ‘加藤’: 5.21, ‘田中: 4.9 }

使っていないユーザーは評価できないので、上のリストには入っていません。上記から「サンポール」と「ドメスト」がどれだけ似ているか判断するにはどうすればいいでしょうか。それは同じ要素に注目するのです。サンポールとドメスト両方を評価しているものに注目すると、斉藤と加藤のみです。(古澤はドメストのみ、田中はサンポールのみ)

アイテムベースで類似度を図るには、共通している項目(斉藤と加藤の評価点)のみに注目します。なお、類似度の算出にはよくピアソン相関が用いられます。出た類似度を用いて推薦システムは構築されます。中にはコサイン積を用いる方法もありますが、単純なベクトルの内積値(コサイン積)よりも、ピアソン相関を好むケースが多く見られます。

共分散を σXY, 標準偏差をσX, σY とおく。このとき{\displaystyle \rho ={\frac {\sigma {XY}}{\sigma {X}\sigma {Y}}}} として書くことができます。以下も全く同じですが、少し具体的に書きます。

r_{xy} = \frac{{\displaystyle \sum_{i = 1}^n (x_i - \overline{x})(y_i - \overline{y})}}{\sqrt{{\displaystyle \sum_{i = 1}^n (x_i - \overline{x})^2}} \sqrt{{\displaystyle \sum_{i = 1}^n (y_i - \overline{y})^2}}} = \frac{s_{xy}}{s_xs_y}

アイテムベースでは一回類似度マトリックスを用意してけば、そのマトリックスのうち、類似度が高いものを返すだけでいいのでとても楽です。

ユーザベース

ユーザベースでは、アイテムベースとは逆の以下のようなデータ構造を用意します。pref[ ユーザ名 ][ アイテム名 ]

pref[ '斉藤' ] = {‘風と共にさりぬ’:3, ‘タイタニック’:2, “冷静と情熱の間':4, “セブン”:2}
pref[ '田中' ] = {‘風と共にさりぬ’:2, ‘タイタニック’:5, “アルマゲドン':1}

映画、「タイタニック」を見ていない人がいたとして、一体自分はどう評価するかをしりたいのです。

こちらも簡単で、手順は以下のとおりです

  • 見ている物同士のアイテムをピアソン相関を用いて類似度を算出する。
  • 自分のタイタニックの評価 = ( 田中との類似度 x タイタニック[ 田中 ] + 斉藤との類似度xタイタニック[ 斉藤 ] ) / (斉藤の類似度+ 田中の類似度)

これが最終的な結果です。類似度の加重平均であるということがわかります。

参考文献

https://www.amazon.co.jp/%E9%9B%86%E5%90%88%E7%9F%A5%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-Toby-Segaran/dp/4873113644

おすすめページ

線形判別分析(LDA)

LDAについて

LDAとはLinear discriminant analysisの略で、日本語では線形判別分析と呼ばれています。コンピュータサイエンスでは様々なところで(例えば画像処理でも顔認識など)よく使われ、とてもポピュラーな技術です。

LDAの目的は「クラス内分散とクラス間分散を最大化する」ということにあります。(補足:クラス内、外分散は英語でwithin, betweenと呼ばれている)。結果として、散布図の空間に超平面を引いてデータ群を分離するのです。(超平面に関してはSVMのコラムを確認ください)

例えば、A、B,Cの3つのクラスがあったとします。目的は、3つのクラスをできるだけ遠くにし(クラス間分散最大)、それぞれのクラス間はできるだけ良くまとまっている(クラス内分散は最小)の集合にする事を目的としています。

Class内では分散を最小化するように平均値に向かって行く操作をし、クラス外ではなるべく離れるように操作するのがLDA

クラス内の分散はなるべく低いほうがいいため、中心(平均、重心)に寄って行きます。クラス間分散はおおきくするため、なるべく遠くへ遠くへ、まんべんなく散らします。

LDAをどうやるかの前に、簡単に予備知識として平均と分散について話した後、具体的な操作を説明することにします。LDAは非常にある意味難しく、分散、平均、擬似行列、PCAなど分かっていなければなりません。一度に覚えようというのは無理なので、じっくりと接して感覚を掴んでください。

平均と分散について

 平均についてはいいとは思いますが、式で説明いたします。以下が平均の式です。全ての数を足しあわせその数で割っているだけの式です。

\mu=\frac{1}{n}\sum_{i=1}^{n}x_i

続いて分散の式ですが、平均からどれだけ散っているか、を表す量です。その散らばり量を表すために、先程求めた平均値との差分をとり、自乗してすべての数の分だけ足しこみます。そして、総数で割ります。(いえば、差分の自乗の平均です)

何故自乗するかというと、平均との差分であるためにマイナスになるケースがあるため、マイナスをなくす目的もそうですが、自乗することで差分が大きい場合にペナルティを与えることが出来ます。分散がどういうものかについて、解るには結構時間がかかります。様々な数字に慣れ親しんで感覚を掴んでいきましょう。(結局はどれだけ散っているか図るためだけの材料です。平均よりも分散が高ければ散っているという感じを受けてください。)

S^2 = \frac{1}{n} \sum_{i=1}{n} (x_i-\mu)^2

分散は平均からの誤差を表しています。データ群は、平均からどれだけ「平均して」はなれているか、という指標です。分散が0なら全然離れていない。平均よりも分散値が大きいなら、結構ばらついているというような、データのまとまり具合がわかります。

LDA

今たくさんのデータがあり、それぞれのデータにはC1とC2のどちらかのラベルがはられていると仮定します。LDAではクラス内分散とクラス間分散を求めなければなりません。まず二つクラスの場合の求め方について説明します。 その後多クラスについて拡張します。

クラス内分散の求め方

今二つクラスがあり、まずは上記式を使ってそれぞれのクラスごとの分散を求めます。ここではその分散の値をss1, ss2とします。そこからクラス内分散を求めるには、単純に

ss_{within} = ss_1 * 0.5 + ss_2 * 0.5

とするだけです。ただし、注意して欲しいのですが、上記の式を使えるのは、ss1 と ss2 の要素数が同じの場合です。(SS1は10個、SS2も10個など)クラス内の要素数が違う場合、重みを等しくおくのは適切ではありません。要素数が違う場合(実際にはこの場合がほとんど)、加重平均で割ります。

正しいクラス内分散(それぞれのクラス内の分散の平均)

weight_1 = w_1*(w_1 + w_2) \\ weight_2 = w_2*(w_1 + w_2)\\ ss_{within}= weight_1 * ss_1 + weight_2 * ss_2\\ 

ss1, ss2はそれぞれクラス内で求めた分散です。クラス内分散が求まりました。意外と簡単です。

クラス間分散の求め方

続いて、クラス間分散を求めます。(クラス同士の離れ具合を計算する。)まず、クラスを全部すっぱ抜いて、要素全ての平均を求めます。これをAVRとします。

これでクラス間分散を求める材料は揃いました。クラスの平均から全体の平均を引算する。(今二つのクラスがありますので、AVR1, AVR2と置きましょう。)

ss_{between} = ( weight_1 \times (AVR_1-AVR)^2 + weight_2 \times (AVR_2 - AVR )^2) 

weight1, weight2についてはクラス内分散を求めたときと同じ値を使います。

判別に用いる、マハラノビス汎距離

判別にはどうすればよいでしょうか?答えはマハラノビス距離を用います。マハラノビス距離で例えばあるxというものがAとBのどちらかに属しているのかということを知るのには以下のような指標を用います。

|(x-A群の平均値)/A群の標準偏差| と |(x-B群の平均値)/B群の標準偏差|

の小さい方に属させるます。つまり、(データを分散によって標準化、これがマハラノビス汎距離の考え方です。)

多クラスにおいてのクラス間分散&クラス内分散の求め方

他クラスの場合を考えます。また線形判別分析を行うために共分散行列として求めます。LDAのおさらいですが、今、特別な空間において、

最もクラス間の分散が高く、そして、クラス内同士の分散が低くなるようにしたい。

これがLDAの本質です。クラスに分類されるある集合が、どのように写像すればクラス間が最小、クラス間が最大になるのかを考えるのです。

LDAを行うためには、クラス内分散の共分散行列を求める必要があります。求めるには、クラスごとに共分散行列を作り、それを足しあわせてクラス数で割ります。共分散の詳しい求め方についてはPCAのコラムを参考にしてください。上記内容を数式で表すと以下になります。

\sum_W = \frac{\sum_{i=1}^C n_i \sum_{x\in C_i} (x-avr_i)(x-avr_i)^T}{\sum_{i=1}^C n_i}

\sum_W の共分散行列を表しています。2クラス問題の時に考えたときのように、分母ですが、2クラスの時と同様、加重平均で割っています。

クラス間分散も同様に求めます。以下のようになります。

\sum_B = \frac{\sum_{x\in C_i} n_i(avr_i-AVR)(avr_i-AVR)^T}{\sum_{i=1}^C n_i}

AVRは全体の平均を表しています。avri は各クラスの平均です。 よく見ると、2クラスの時を拡張しただけであることに気づくと思います。(共分散行列を作るために転置したベクトルをかけているところも違いますが)

Σ_W とΣ_Bが求まれば準備終了です。

以下を最大化したいような行列Aを求める、という事を行います。

ret = \argmax( \frac{A^T \sum_B A}{A^T \sum_WA })

argmax( その値が最大となるような値 )を取ってやります。上記のretはフィッシャーの判別比とも言われます。判別比を最大化できるような行列Aはどうやっても求まるのでしょうか。

なぜそうなるかを話すと、長くなるので端折りますが、結果的には以下に対して、固有値分解を求めれば、求めたいベクトルAが求まります。(導出に関しては、やや話がそれるので詳しくは説明しません。ラグランジュの未定乗数法を使うのですが、気になる方は参考文献[2],[3]をご参照ください)

\sum_W^{-1}\sum_B

ところが \sum_Wの逆行列ですが、ランクが足りなくて求まらない場合があります。その際はランク落ちを考慮するため、擬似逆行列を用います。擬似逆行列とは、ランク落ちなどに対処するため擬似的な逆行列を作成する操作です。

Aが求まればあとは、それを用いるだけです。Aは固有ベクトルとしていくつか出てきます。固有値が高い順に並べます。適当な所で打ち切りにします。 その固有値に対応した固有ベクトルを用いて判別します。

特定のxに対して、出てきた固有ベクトルで変換してやります。そして、その変換したベクトルがそれぞれのクラスのどれに近いかを算出します。算出にはマハラノビス汎距離を用いるのです。

顔画像でLDA

Python2での実装例を紹介します。顔画像を用いてLDAします。左向き、右向き、正面の画像を用意して、他クラス分類を実施します。

def M( array ):
    return numpy.matrix( arrray )
def LDA():
    density_matrix = []
    FACE_X = 64
    FACE_Y = 64
    SIZE = FACE_X * FACE_Y
    class_imgs = [glob.glob( "./left/*.jpg" ), glob.glob( "./front/*.jpg" ), glob.glob( "./right/*.jpg" )]
    # 1st step we calculate each_class_avr, overall_avr,
    class_avrs = []
    avr = numpy.array( [0] * FACE_X * FACE_Y )
    cnt = 0
    for imgs in class_imgs:
        s = numpy.array( [0] * FACE_X * FACE_Y )
        for img_path in imgs:
            data = numpy.array( get_density_vector( img_path, FACE_X, FACE_Y ) )
            s += data
            avr += data
            cnt += 1
        s /= float( len( imgs ) )
        class_avrs.append( s )
    avr /= float( cnt )
    print 'step1 ==> done'
    
    # 2nd. within
    sigma_w = M(numpy.zeros( ( SIZE * SIZE ) ).reshape( (SIZE, SIZE ) ))
    for c_avr, imgs in zip( class_avrs, class_imgs ):
        # class co-matrix
        sigma_wi = M(numpy.zeros( ( SIZE * SIZE ) ).reshape( (SIZE, SIZE ) ))
        for img_path in imgs:
            data = numpy.array( get_density_vector( img_path, FACE_X, FACE_Y ) )
            mat = data - c_avr
            sigma_wi += M(mat.reshape( (len( mat ), 1 ) )) * M(mat)
        sigma_w += sigma_wi / float( len( imgs ) )
    print 'step2 ==> done'
    
    # 2nd between
    sigma_b = M(numpy.zeros( ( SIZE * SIZE ) ).reshape( (SIZE, SIZE ) ))
    for c_avr in class_avrs:
        mat = c_avr - avr
        sigma_b += M(mat.reshape( ( len( mat ), 1 ))) * M(mat)
    
    print 'step3 ==> done'
    print sigma_w.shape
    print sigma_b.shape
    sigma_w_inv = M(numpy.linalg.pinv( sigma_w ) )
    print sigma_w_inv.shape
    print sigma_w * sigma_w_inv
    
    lam, vec = numpy.linalg.eigh( sigma_w_inv * sigma_b )
    ans = zip( lam, vec.T )
    ans.reverse()
    print 'step4 ==> Done'
 

参考文献

  1. https://ja.wikipedia.org/wiki/%E5%88%A4%E5%88%A5%E5%88%86%E6%9E%90
  2. https://axa.biopapyrus.jp/machine-learning/preprocessing/lda.html
  3. https://www.iwanttobeacat.com/entry/2018/05/26/203825

おすすめ記事

  1. 主成分分析(PCA)
  2. 単純ベイズ分類器(Naive Bayes Classifier )
  3. 特異値分解(SVD)

Adaboost

Adaboostは「弱い識別をくり返して、強い識別器を作る」事を目標とた学習アルゴリズムです。

やりたいことは単純で、以下のような関数をつくりたいのです。

 f(x) = \sum w_t * eval_t( 特徴量 ) |ここで t は 1..T

上記式は、ある特徴を評価関数(eval関数)に突っ込み、重み(w)かけ、それを複数回足しあわせた線形和を求めるを表現しています。結果が1に近ければ正解、0に近ければ不正解となります。上記のステップtは、よく論文で1..Tとの表現されてます。このラージTの値は自由に決まります。例えば「識別精度が95%超えたらやめる」というようにしておき、10回目で超えたに96%になったとします。この場合、Tは10となります。

AdaBoostの目標は、各ステップ毎の「w_t」「eval_t()」を算出することです。

Adaboost 学習具体例

まずD1を定義します。

D_1 = \frac{1}{ m}

まだ、Dの存在が何かわからないと思いますが、とりあえず今は気にせず前へ進みます。D2, D3, D4 .. DTと次々と求めていく作業がAdaboostの学習作業となります。D2以下は以下のように表されます。

D_2 = \frac{D_1 * exp( -w_1 * y_i * eval_1( 学習画像_i )}{2}

上記を学習する画像分回します(iがその画像枚数分存在します)。yはPosかNegかのフラグです。Posであれば1, Negであれば-1となっています。ここでw_1が出てきています。これは、以下のように表されます

w_1 =\frac{\frac{log( 1 - ε_1)}{ ε_1}}{2}

ε_1は以下のように表されます。

 ε_1=\sum D_1 * EVAL( eval_1( 学習画像i ) != y_i )

上記式において評価関数が決定されます。なお決定した評価関数(eval_1)はDを求めるときに用いている関数と全く同じです。評価関数は、「学習画像をいれて、正解と一致しているかどうか」を返す事を目的としています。そんな関数は、誰もわかりません。最適な評価関数を決定するためにはGreedy,つまり全探索が行われています。通常、Adaboostの学習は非常に時間がかかりますが、その理由は表関数の決定に膨大な時間がかかるためです。

全探索の結果、εが最小となるような評価関数を決定します。これが全体の流れです。評価関数が決まり、エラーがわかったため、重みが決定することができます。重みと評価関数が決まったため、D2が算出されます。あとはD3でも同じようにくり返していけば結果を得ることができます。

カスケード接続について

Adaboostではよくカスケード接続が用いられます。カスケード接続とは、Adaboostで得た学習を多段の串のように接続して構成していくことです。

一回の学習で99%と目標まで学習を進めていくのではなく、60%程度で学習を打ち止めをします。

そして、またAdaboostで識別機を作ります。これも60%の精度で止めていき…を繰り返し、識別器を団子のように串刺しで横に並べます。コレがカスケード接続です。尚、次の識別器には、通過してしまった40%の失敗データ+新しいデータセットでまた学習をし直していきます。

後段のカスケードの学習はどんどん難しくなっていきます。顔検出などではこうした構造が用いられています。

参考文献

https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%BC%E3%82%B9%E3%83%86%E3%82%A3%E3%83%B3%E3%82%B0

おすすめサイト

投影距離法( Projection distance method )

投影距離法とは

分類するためのアルゴリズムで、例えばある文字はどこのクラスに属しているかなどOCRの分野で使われたりします。画像処理のパターン認識では部分空間法という方法に属する方法です。

投影距離法は意外と知られていません。なかなか面白いアルゴリズムです。実際に手書き文字などのフィールドでは加重方向指数ヒストグラム法と本学習方法を利用して、精度がとても話題になりました。(蛇足ですが加重方向指数ヒストグラム法はHoGというアルゴリズムに酷似していて、個人的にはもっと有名に慣れたのになぁという事を覚えています。機会がこの特徴量はご紹介します。)

さて、投影距離法は感覚的にどういうものかを簡単に説明すると、

「一度ある空間に写像してやる、そのなかで距離が最も近かったものをそのクラスとする」

というものです。

投影距離法理解のため、まずは単純投影距離法を説明し、そのあとに投影距離法を説明します。改良投影距離法というものがありますが、投影距離法の改良版ですので投影距離法さえ押さえておけばあとは比較的スムースに入っていけます。まず、単純投影距離法について簡単に説明します。

単純投影距離法

各クラスの平均と比較して、距離が近いものをそのクラスに属する事にするという方法です。詳しくご説明します。

今クラスが2つあったとして、それぞれのクラスの平均を求めます。それぞれをM1, M2とします。

そして、未知の点Xがあったとして、このクラスがどちらの点に属するのかというのを決めたいとして、それを知るには、XとM1、XとM2の距離のうち短い距離で決定するというものが、単純距離法です。数式で表すと以下になります。

min( abs( X – M1 ), abs( X – M2 ) )

すごい簡単です。各集合(各クラス)の平均値との距離を求めればいいだけですし、直感的にわかり易いと思います。

■投影距離法とは

あるクラスの空間において、そのクラスの空間にある超平面との距離を求め、最小のものそのクラスに属するとする方法です。

具体的にはクラス毎にPCAを行います。例えばクラスが10個あれば10回PCAを行い、各クラス毎に固有ベクトルが求めます。(その際の固有ベクトルの数は任意で、通常寄与率等で決めます。PCAについては、別途参考資料を作成します。)

例えば、あるクラス(C1)において複数の固有ベクトルを得たと仮定します。一つの固有ベクトル(E1)を取り出します。固有ベクトルE1で張られる軸と直交している超平面と、Xの距離、これを投影距離と呼びます。今、超平面の式はわからないので、ある点を超平面を構成している点(A)として仮定し、点Aはクラス全体の平均の点にします。超平面を構成している点Aがあれば、 X と超平面までの距離がわかるのです。(この超平面はE1と直交していることをお忘れずに)

超平面までの距離は三平方の定理により求まります。

まず、AからXまでのベクトル(V1)を求めます。

続いて、V1ベクトルを固有ベクトルで変換し、その超平面上に射影してベクトルV2を求めます。固有ベクトルはその空間を構成している軸(基底ベクトル)ですので、その固有ベクトルの転置とV1かけるだけでと、V2が求まります。(とても説明が難しい。。。)

この2つが出たら、V1とV2のベクトルがあるので、超平面までのベクトルV3が求まります。V3の長さが超平面までの距離となります。まさに三平方の定理です。

このように、空間に変換して求める方法を一般的に部分空間法と呼びます。Projection Distance Methodは一種の部分空間法となります。部分空間法は利点もあれば、欠点もあります。例えばクラスを追加しやすかったり、判定が高速におこなえます。欠点もあり、固有ベクトルで変換したのが必ずしも最適なのか、というそもそも論も言われます。

参考文献

C. -L. Liu, K. Nakashima, H. Sako, and H. Fujisawa, “Handwritten digit
recognition: benchmarking of state-of-the-art techniques,” Pattern
Recognition, vol. 36, pp. 2271-2285, 2003.

おすすめの記事

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

SVM(Supporort Vector Machine)は、

「データセットを二つにちょうど分類できるような線」

を見つける学習機です。2クラスに分類するため2クラス分類専門の学習機です。もちろん工夫すれば他クラス分類が可能かもしれませんが、基本的には2クラスの分類器です。なおSVMの理論は本稿では難しすぎるうえ、かなり長くなるので取り上げません。基本的な概念と実際の使い方について説明します。

2クラス分類器であるSVMは、例えば画像が顔であるかどうかについて、今顔画像(POSITIVE)と、顔でない画像(NEGATIVE)の2つに分けるような直線を求めます。

データが二次元(X,Y)でれば線を、3次元(X,Y,Z)であれば分割できるような平面を引くこと、これがSVMの目的です。次元に併せて線、平面など言い換えは面倒なので、「超平面」と呼ばれています。超平面はある次元において分割できる線や面のようなものです。(多次元ではどういう形をしているのか我々3次元の生き物からは想像ができませんね。)

上図はイメージです。実際には綺麗に切れることはありませんので、ちょっとは混じってしまいます。超平面はなるべく離れるように線をひこうと頑張ります。(ソフトマージン(点線までの距離)といいますが、コレを最大化する)。

なお、SVMで超平面でなく非線形な超平面も扱う方法があります。これを非線形SVMといいます。 非線形SVMは高次元空間に写像して無理やり超平面を引く方法です。

ただ、非線形SVMはあまり有用とは思いません。非線形だとオーバーフィッティング(いわゆる過学習)などの問題も出てきやすくなります。また、経験的にですが線形で結果が出ないものは非線形でも出ません。実際にはほとんどの空間においてですが、線形で十分なのです。

余談ですがサポートベクターとは、混じってしまったベクトルや、ソフトマージンを最大化するために利用するベクトルを指します。(線を引くために参考にするベクトルを指す)

SVMを用いた画像の分類例

SVMを用いて先程の画像を顔画像か、顔画像でないかの2つのグループに分ける方法はどうやるのでしょうか。

まず、画像を1つの配列にします。例えば64x64の画像があるとすると、それを4096次元(64×64=4096)の配列を作ります。

SVMはこの4096次元の空間において、線形にぶった切れる線(超平面)を探してくれます。SVMの学習結果では、4096個の重みの結果が返されます。

SVMからの出力はa_0, a_1, a_2, a_3.. a_nといった係数が出てきます。nは学習した次元数によります。今回の場合は4096個です。これは超平面の方程式を指しているのです。この係数を利用して、計算結果がマイナスであると不正解、プラスであれば正解となります。

SVMを実際に使ってみ

早速SVMを使ってみましょう。線形SVMで説明をします。

liblinearをインストールしてください。これはLibSVMの非線形バージョンです。

http://www.csie.ntu.edu.tw/~cjlin/liblinear/

データセットとして、次のa9aをダウンロードしておきます。

http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/binary/a9a

ダウンロード解凍後、以下のコマンドを叩きます。

make 
./train -v 5 a9a

-v はクロスバリデーションといって、用意した画像を全部学習に使わず、上記例で言えば1/5だけを残して、4/5を学習に使いそれでチェックするということを行うオプションです。n-fold cross vlidationと呼ばれています。たとえば3にすれば、2/3を学習に用いて、1/3をチェックに使うのです。なお、結果としては以下のような内容が帰ってきます。

Cross Validation Accuracy = 84.8131%

クロスバリデーションの精度の結果で、これにより分類精度をチェックできます。

本番で使うときは全部学習に用いたほうがいいのでオプションの指定はしなくて構いません。クロスバリデーションは学習が上手く行ったかなど、確認するときに使います。

本学習では従って引数なしで、

./train a9a

とします。a9a.modelができているのを確認してください。その中のファイルを見ると、重みが並んでいます。(w以降の数字が重みです。)学習に使用した特徴量と、この重みをかけ合わせ、正負により判別を行うことが出来るのです。

おすすめの記事

ランダムフォレスト

ランダムフォレスト とは

ランダムフォレスト とは決定木(後述)を寄せ集めて実現される学習アルゴリズムです。ランダムフォレストを簡潔に表現すれば、「多数決のアルゴリズム」と呼べます。

Random Forest ( ランダムフォレスト、乱数の森のイメージ図)

アルゴリズムは比較的簡単で、決定木を適当に何本か作り、質問を投げかけます。答えた木の多数決により解が決まります。

例えば50本の決定木があったとして、40本の木がある質問に対してYesと答えた場合、この質問の回答はYesとなります。そして回答の正当性は80%で…という結果も得ることができます。ランダムフォレストの良いところは、木の数が確率で返答としても参考にできるところです。

以上のようにランダムフォレスト自体は解りやすいのですが、実装する上では決定木を理解することが必要です。

さて、今回は簡単に決定木のロジックを説明した後、実際にPythonで決定木を実装してランダムフォレストを作ってみます。有名人の顔のDB[2]を使って学習して男女判定のプログラムを作成してみます。

決定木とは

決定木は学習アルゴリズムの1つで、例えば質問してYes、Noで分岐していき、木構造を作成することで完成されます。

「完全に答えが出るまで分岐させ、これ以上分岐できないのであれば、そこで終わり」

というアルゴリズムです。決定木のいいところは、分岐点を見ていくと、何故その判断に至ったのか論理的に理解しやすいところです。たとえば、以下のような決定木のとき、最終的な状態(leaf)はどのような項目(質問)により分類されたか、がわかるのです。

決定木
Fig2. 役員か平社員か早期退職者の決定木の例

上記をみると役職の理由(平社員、管理職)が視覚的にわかります。学習後はこのような木ができて、なぜこうなったのかが理解しやすいのが決定木の良いところなのです。

ところで、決定木には分類木と回帰木という2種類があります。分類木はYes/Noや男女、暑い寒い、など2値をとる、あるいは分類するために用います。一方で回帰木は確率などの数値を取ることが出来ます。画像から年齢をとったり、スポーツ選手の成績から年俸を推定したり、結果が数値で表されるものに使われています。

今回は決定木で最も有名なCARTアルゴリズム(回帰木)を使って説明していきます。

決定木の作り方

「ある集合をなるべく偏りがあるように2つに分断する。」

これをくり返していくことで木を作成していきます。偏りという概念には「情報エントロピー」を使います。

偏りとは、例えばYES、NOという回答が混ざっている状態から、YESとNOの2つの集合に綺麗に分けてやることです。他にも例えば「いちごミルク」から「いちご」と「ミルク」に偏ってわけたい(混ざった状態から、混ざってない状態に戻す)ことを偏りをつくるといいます。

Fig3. 偏りを作る例。質問Yの方が質問Xよりうまく偏りがある。質問Zは完璧ではないものの、結構精度が高く偏りがもとめられる。どれが、偏りが高いかを定量的に表すために情報エントロピーを利用する。

完全に混ざった状態はエントロピーが高い状態(乱雑な状態)であるといいます。逆に偏りがある状態をエントロピーが低い状態(偏った状態)と呼びます。なるべくエントロピーが低く低くなるような分岐状態(偏りがあるような分岐)を作っていくこと、これが決定木をつくる上で重要なことです。

偏るためには質問を用意します。質問は何でも良いですが、自分で用意する必要があります。先の例(Fig.2)であれば、今までの従業員の結果(役職)をもとに、彼らへの質問を用意しておくのです。質問の内容はたくさんあると思います。それこそ性別、勤続年数、宗教、出身地、出身校、目の色、頭髪、身長、体重などなど。(コンプライアンス的に引っかかるものもありますが、)こうした質問を用意しておいて、うまく分けることができたら(偏りを作れたら)良い質問だったということになります。

情報エントロピー

偏ったかどうかという判定に情報エントロピーを使うと言いましたが、それはとても便利だからです。情報エントロピーの数式は次の式となります。

情報エントロピーの式 : -\sum{P\log_2{P}}   (1.1)

Pには数値が0−1までの数値が入ります。

情報エントロピーの値が元の集合の情報エントロピー値より低くならないのであれば、木はそれ以上枝を作りません。

情報エントロピーについて具体例で考える

先の式(1.1)を掘り下げましょう。男女の集合の中から、ある質問をして「男」と分割した時のエントロピーを考えます。決定木では質問の後は必ず2クラスに別れます(グループA, グループBとする)。

グループAに男が存在する割合をP(x)とすれば、グループBに男が存在する割合は必ず1-P(x)となります。(2クラスしかないため)したがって男性側だけの情報エントロピーは、

P(x) * log_2{ P(x) }  (グループAに男:GroupA(男))

(1-P(x)) * log_2{ (1-P(x)) } (グループBに男:GroupB(男))

この2つを足して、マイナスをしたのが、男性側の情報エントロピーです。

さて、男性がうまく分割しても、女性は分割出来ていない場合もあるかもしれません。女性にも男性と全く同じ質問をして、女性側のエントロピーも求めます。グループAに女が存在する割合をP(y)とします。同様に2クラスしかないため1-P(y)がグループBに女性がいる割合です。

P(y) * log_2{ P(y) } (グループAに女:GroupA(女))

(1-P(y)) * log_2{ (1-P(y)) }  (グループBに女:GroupB(女))

最終的にこの4つをすべてを足しこんで、マイナスした値-( GroupA(男)+GroupB(男)+GroupA(女)+GroupB(女) )が結果的な情報エントロピーとなります。(男女別情報エントロピーの合計,のマイナス)

今は男女になりましたが、昨今性別が増えています。性別が増えた場合も同様に足しこんでマイナスをすれば、最終的な情報エントロピーがでます。

上記でlogの底が2であることに注意してくだい。コンピューターで計算する際は変換公式によりlog_2{x}=\frac{log_e{x}}{fog_e{2}}を利用しましょう。

決定木は必ずノードで2つに分割するので、結局その場合のある要素の情報エントロピーは次の式となります。

Entropy = - ( x * \frac{\log_e{x}}{\log_e{2}} + ( 1-x) * \frac{\log_e{1-x}}{\log_e{2} }) (2)

上記の情報エントロピーをGnuPlotで出力すると以下になります。

確率Pが0.5の時に上に凸の山なりのカーブを描きます。(最大値を示します)。0.5はランダムな状態(乱雑な状態)、分割がうまく行かなかったことを表します。ランダムであれば一番高い値となる、これが情報エントロピーです。情報エントロピーは前述の通り、低ければ低いほど偏りがあるという事になるのです。

こうして出来た決定木をあつめて、ランダムフォレストは作成されます。ランダムフォレストを作成する際の注意点は、同じ決定木を作らないようにすることです。質問を違う順番でしたり、パターンを用意したり、様々な試行を行わなければなりません。多数決のアルゴリズムですので、それこそ多種多様な決定木があるほうが良いのです。

Pythonで 決定木 & ランダムフォレスト を実装

長くなってしまいましたが、いよいよPythonで実装してみます。今回は男女画像から男性と女性を判定する決定木を作っていき、それを用いてランダムフォレストを作ります。決定木のアルゴリズムの種類はCARTとします。

データセットが必要なのですが、顔画像のDB[2]からデータをダウンロードしてきます。この後、画像から顔をクロップして男女に分ける必要が有るのですが、既に私がやりましたので次のURLからfemale, maleのtarボールをダウンロードして解凍してください。github

Pythonでの実装の流れは次のようになります。

  1. (下処理)2次元の画像を1次元にlist化する
  2. (本処理)画像の輝度情報(つまり濃淡情報)を使って分割し、一番よく分割できたところを保存する

これだけです。それではまずはリスト化するところを説明します。

顔画像の一次元化

get_pixelsという関数を定義します。これは画像のファイルパスをもらってList化関数です。中ではカラー画像から輝度だけの画像にした後、ヒストグラム平滑化処理を行い、そして少しウィンドウを縮めてクロップしています。ウィンドウを縮める理由は髪の毛等ではなく、なるべく顔のパーツ情報から男女を判定してほしかったためです。

def get_pixels( path, w, h, crop_area = 0.86 ):
    # 画像を開く
    img = Image.open( path )
    #画像サイズの取得
    width, height = img.size
    # マージンの比率を計算
    margin_ratio = (1-crop_area)/2.0
    #スタートの位置を計算
    sx = (width * margin_ratio)
    sy = (height * margin_ratio)
    #輝度画像に変換
    img = img.convert( 'L' )
    # ヒストグラム平坦化処理(いらないかも)
    img = ImageOps.equalize(img) 
    # 画像をクロップする                                                                                                                                                                                                                                    
    img = img.crop((sx, sy, width * crop_area, height*crop_area)).resize( (w, h), Image.BICUBIC )
    # リストにして返す
    return list( img.getdata() )

上記のリストを用いて学習していきます。

学習関数

あるsetをset1, set2に分割した際に、エントロピー(ランダムになっているかどうか)を計算します。ここでいうsetの構造は次のとおりになっているとします。

sets = [ ('M', [127,0,1,1, ....], ('F', [124,0,1,3, ....], ('F', [224,110,11,33, ....],,,,,,, ] 

M, Fが書いてありますが、FemaleかMaleか判定するラベルです。その次の配列はlist化した顔画像の1次元の輝度情報です。さて、前の章で説明したエントリピーの計算は以下のとおりとなります。

def entropy( sets ):
    # log2の関数を定義
    log2 = lambda x: log(x) / log(2)
    # ヒストグラムを取得する。ヒストグラムは頻度分布の事で、今回で言えば'F'と'M'が何個あるか計算する
    def get_histogram( keys, sets ):
        #{ 'F': 0, 'M':0 } という風に初期化
        hist = dict( zip( keys, [0]*len( keys ) ) )
        # keyから頻度分布を作成(1を足していくだけ)
        for s in sets:
            k, _ = s
            hist[ k ] += 1
        return hist
    # ラベルの一覧を取得する。今回は'F'と'M'しか無いので、set([ 'F', 'M'])となる
    unique_keys = set( [ _data[ 0 ] for _data in sets] )
    # ラベルの一覧と、現在のデータを渡して頻度分布を取得する
    histogram = get_histogram( unique_keys, sets )
    # エントロピーの計算
    ent = 0.0
    for k in unique_keys:
        p = histogram[ k ] / len( sets )
        if p != 0:
            ent = ent - p * log2( p )
    return ent

エントロピーの計算方法は先程説明したとおりです。さて、これを用いていよいよ計算していきます。学習部分に関しては次のようになります。

# 輝度リストの中で、idx番目がvalueより高いかどうか判定
# ココの関数の定義によりある種分割が決まるから重要。ココは各々が思いついたアルゴリズムで実装すると良い
def split( sets, idx, value ):
    set1 = []
    set2 = []
    for data in sets:
        label, pixels = data
        if pixels[ idx ] >= value:
            set1.append( data )
        else:
            set2.append( data )
    return [set1, set2]


# sets --> [('M':[輝度リスト]),('F':[輝度リスト]),('M':[輝度リスト]),('F':[輝度リスト]) ....]
# size --> 輝度リストの長さ
def train( sets, size ):
    # 再帰関数として定義される。数が0であればその時点で終了する(分割が出来た)
    if len( sets ) == 0: return 0
    # ステップ数。輝度データをなめていくが、その飛ばしていく数。短いほうが遅くなる
    step = 2
    # 現在のエントロピーを計算する
    current_score = entropy( sets )
    # ゲイン値を使う。ゲイン値高いものが良い分割と判断する
    best_gain     = 0
    best_criteria = None
    best_sets     = None
    # 輝度配列の数だけぶん回し
    for index in range( 0, size, step ):
        for value in range( 256 ): # 輝度値は0-255までなので
            # ある輝度値の条件に依って分割(後述)
            set1, set2 = split( sets, index, value )
            p = float( len( set1 ) ) / len( sets )
            # gain値の計算
            gain = current_score - p * entropy( set1 ) - ( 1 - p ) * entropy( set2 )
            # 良かったgain値を保存
            if gain > best_gain and len( set1 ) > 0 and len( set2 ) > 0:
                best_gain = gain
                best_criteria =( index, value )
                best_sets=( set1, set2 )
    # best_gainが更新されていれば、枝を生やす
    if best_gain > 0:
        ans_index, ans_value = best_criteria
        true_branch = train( best_sets[ 0 ], size )
        false_branch = train( best_sets[ 1 ], size )
        return { True: true_branch, False: false_branch, 'index': ans_index, 'value': ans_value}
    else:
        return {'leaf': sets[0][0] }

エントロピーを使って分割しています。分割後はゲイン値を使って最も良かった分割を保存しておきます。そして、再帰的にドンドン分割していくのです。そして、分割ができなくなったら終わります。(Leafに到達)

ここで、splitという関数がありますが、自分でよく分割できそうだと思うような関数を書いてみましょう。今は単純に[index番目の濃淡値がvalueより高いか] で判断しましたが、画像の前後の上下の値を見たりするなど色々な工夫が出来る余地があります。

さて、これらを使ったmain関数は次のようになります。

import glob
import os
import random
from math import log
from PIL import Image, ImageOps

import uuid
import pickle

# 画像をランダムにサンプリング                                                                                                                                                                                                                                                  
def get_image_files( folder_path, picnum ):
    return random.sample( glob.glob( os.path.join( folder_path, '*.jpg' ) ), picnum )

# female, maleフォルダより50個のファイルを取得する。                                                                                                                                                                                                                            
def main():
    forest = []
    num_tree = 30
    # 木をぶん回す
    for i in range( num_tree ):
        print( f"building tree ... {i+1}/{num_tree}")
        # 何枚の画像をフォルダからピックするか
        num_pick = 150
        female = get_image_files( './female', num_pick )
        male = get_image_files( './male', num_pick )
        # 画像サイズ 32x32にする
        crop_size =32
        sets = []
        # データセット作成                                                                                                                                                                                                                                                      
        sets += [ ('F', get_pixels( path, crop_size, crop_size ) ) for path in female ]
	sets += [ ('M', get_pixels( path, crop_size, crop_size ) ) for path in male ]

        size = 32 * 32
        ret = train( sets, size )
	forest.append( ret )
    pkl_name = f"ret_{uuid.uuid4().hex}_size_{size}_picknum_{num_pick}_treenum_{num_tree}.pkl"
    print( "dumped to --> ", pkl_name )
    with open( pkl_name, 'wb' ) as fd:
        pickle.dump( forest, fd )

これで決定木の学習、及びランダムフォレストの作成は終了です。一本の決定木からは次のようなデータが出てきます。

{True: {True: {True: {‘leaf’: ‘M’}, False: {‘leaf’: ‘F’}, ‘index’: 428, ‘value’: 196}, False: {True: {True: {‘leaf’: ‘M’}, False: {True: {‘leaf’: ‘M’}, False: {‘leaf’: ‘F’}, ‘index’: 552, ‘value’: 162}, ‘index’: 606, ‘value’: 137}, False: {‘leaf’: ‘M’}, ‘index’: 326, ‘value’: 157}, ‘index’: 910, ‘value’: 198}, False: {True: {True: {‘leaf’: ‘F’}, False: {True: {‘leaf’: ‘M’}, False: {True: {‘leaf’: ‘M’}, False: {‘leaf’: ‘F’}, ‘index’: 0, ‘value’: 220}, ‘index’: 78, ‘value’: 102}, ‘index’: 710, ‘value’: 115}, False: {‘leaf’: ‘M’}, ‘index’:212, ‘value’: 92}, ‘index’: 358, ‘value’: 92}

これは、辿るマップを示しています。今回は濃淡配列のindex番目の値がvalueより大きければ、Trueをたどっていき、そうでなければFalseをたどります。これは、split関数で定義した内容と同じである必要があります。最後にLeafに有る値が決定木に依って判定された値です。

注意が必要なのが、今回は画像をCropして、ヒストグラム平滑化処理をしています。検証する画像にも同様の処理をする必要が有ることについて、注意しましょう。

検証

検証用のコードは次のとおりです。

def tree_result( node, data ):
    if 'leaf' in node: return node[ 'leaf' ]
    index = node[ 'index' ]
    value = node[ 'value' ]

    cond = data[ index ] >= value
    return tree_result( node[ cond ], data )

def validation():
    with open( 'ret_a239b96f07d6443c851582866e4b7724_size_1024_picknum_150_treenum_30.pkl', 'rb') as fd:
        forest = pickle.load(fd)
    # print( forest )                                                                                                                                                                                                                                                           
    num_pick = 100
    female = get_image_files( './female', num_pick )
    male = get_image_files( './male', num_pick )

    crop_size =32
    sets = []
    # データセット作成                                                                                                                                                                                                                                                          
    sets += [ ('F', get_pixels( path, crop_size, crop_size ) ) for path in female ]
    sets += [ ('M', get_pixels( path, crop_size, crop_size ) ) for path in male ]


    passed = 0
    failed = 0
    for d in sets:
        count = 0
        label, pixels = d
        for tree in forest:
            ans = tree_result( tree, pixels )
            if label == ans:
                count += 1

        if count > len( forest )/2:
            print( "Passed" )
            passed += 1
        else:
            print( "Failed" )
            failed += 1
    print( 'correct ratio --->', passed / ( passed + failed ) )

上記の通り、validation関数内でpklファイルを指定して読み込みます。今回は、私の方で検証した結果は正答率82%という結果を得ることが出来ました。何もしていない濃淡情報だけでここまで出ました。顔画像のCropも適当です。

回転や縮小に堅牢な特徴量を用いいればもっと精度は向上するでしょう。

さて、ご存知のとおり特徴量を考えるような時代は終わりつつあります。それはGANなどの登場によりコンピューターが自動的に特徴量的なものを学習時に作り出す時代になっているからです。昔はみな回転や縮小に不変な特徴量を考えるのに四苦八苦したものです。

確かに特徴量を考える時代は終わったかもしれませんが、以前顔画像ではなく統計情報を解析したいときなどには未だに強力な武器です。データアナリストをめざすのであればぜひ一度実装して楽しんでみてください。

最後に

実は、決定木ではかならず2分割されると書きましたが、実際にはエントロピーを使うと3分割、4分割も出来ます。ただ、ランダムフォレストを使う場合あまり意味がないものとなるでしょう。解析や判断も複雑になるため、基本的には2分割の決定木を使ったランダムフォレストで十分な精度が出ます。

実は、ランダムフォレストは非常に強力です。これ一本で(何本もありますが)本当に様々なことが出来ます。機械学習の仲間と話しますが、これだけでもいいと思うくらいです。

回帰木は連続した値を扱えるところが素晴らしかったのですが、木を作るのに時間がかかるデメリットやオーバーフィッティングのデメリットがあります。ランダムフォレストをつかえば、何本の木が返答したというような確率を使うことができるので、たとえ分類木を使ったランダムフォレストでも、連続したデータも扱えるようになります。

さぞかし回帰木をつかったランダムフォレストは更に精度が高くなるのでは!?と思うかもしれませんが、実際にはあんまり変わりません。よくよく考えれば、回帰木のランダムフォレストって、重回帰分析の重みの平均みたいなイメージになるのかなぁ、とおもってしまいます。

参考サイト

[1]https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%83%95%E3%82%A9%E3%83%AC%E3%82%B9%E3%83%88

[2]http://vis-www.cs.umass.edu/fddb/index.html

[3]https://axon.cs.byu.edu/~martinez/classes/778/Papers/GP.pdf

おすすめ記事


昨今のAI事情

機械学習に精通しているエンジニア同士で昨今の”AI”という言葉の使われ方についてよく話題になる。AIの誤用が目立つためだ。

1960年末に微分方程式を瞬時に計算するのを人工知能(AI)と呼んだ時代があり、暫くするとそれを人工知能とは呼ばなくなった[1]。2019年、令和時代となった現在、再び方程式を解くプログラムはAIと呼ばれはじめた。最小二乗法で解いて導いたものさえ”AI”と表現する。これはあまりにも酷い。一体何が起きたのか。

AIとは人工知能、考えるコンピューターであるはずだ。ある部分を計算処理するだけのプログラムはAIとは呼べない。全体を理解し処理できて始めてAIとよべる。例えば、人の声を音声理解(自然言語理解)、或いはレシートなどの画像を見せて、コンピューターが”それ”を自動的に判断して”適切な処理”を実施する仕組み、この全体処理でAIと呼ぶ。(厳密にはこれでも弱いくらいだが。。)人間がコンピューターを使って得た結果をひっさげて「これはAIで導き出しました」と言っている姿は、1960年代に戻ってしまったのかと思う。1960年末に微分方程式をといたプログラムをAIと呼んだのは、技術者たちが仕組みを理解せずコンピューターが式を理解して解いたと誤解したためだ。つまりアルゴリズム(仕組み)を知らなかった為で、雑に言えば無知だった。現在、多くの会社がAIというワードを利用するのも、経営陣がコンピューター(サイエンス)を知らなすぎること、無知である事に他ならない。

それにしても何故ここまでにAIというワードがこれほど乱発されるのか。それは顧客の信頼を得たかったり、投資家から資金を調達したいからだ。

AIは完全にマーケティングワードになっている。ライバル会社たちが一斉にAIと言い始めれば、AIという言葉を使わざるを得ない。「あれはAIとは呼べない、インチキだ!」と胸を張って言えば良いようなものだが、経営陣がAIを全く理解していないからしょうがない。見栄えをよくしたい会社や技術に自信がない会社は、なんだか解らない”AI”という言葉をWEBサイト上で乱発する。逆に、例えばPreferred networks社など、機械学習や分析技術に明るい会社ほどAIという言葉はむしろ利用していない。意味を分かっているし、技術にも自信があるからだ。

AIを日本語訳すると”人工知能”だが、「知能」の定義は何か。Webster’s Dictionaryでは知能を次のように定義している

  • 「経験から学ぶ能力や知識を獲得する能力」
  • 「新しい自体が発生したときに迅速かつ適切に対応する能力」
  • 「問題を見極めてこれを解決するために推論を用いること」

AIを謳う会社は、上記の定義を見比べながら自社製品が本当に”知能”をもっているか再考してほしいものだと感じる。

索引:[1]”偉大なる知恵者”の原理と仕組み、応用をさぐる人工知能