機械学習の13、SVD特異値分解

はじめに

本文には、大文字表現=行列/マトリクス、\(\boldsymbol{bold}\)小文字表現=ベクトル\(R^d\)、普通小文字表現=スカラー\(R\) と記す。

SVD(Singular Value Decomposition)は機械学習の分野で広く使用されているアルゴリズムで、次元削減アルゴリズムの特徴分解だけでなく、推薦システム(Recommender System)や自然言語処理(Nature Language Process)にも使用される。

原理

SVDは前述した特徴分解同じく行列を分解するが、SVDは分解する行列が正方行列にする必要ない。行列Aの形状が\(m×n\)であると仮定すると、行列AのSVDを次のように定義する。
$$ A = UΣV^T $$
ただし、\(U\)は\(m×m\)の行列\((u_1, u_2,…, u_m)\)、\(Σ\)は\(m×n\)の行列、主対角線上の要素を除く全ての要素が実数ゼロ\(0\)であり、主対角線上の各要素は特異値(Singular Value)という、\(V\)は\(n×n\)行列\((v_1, v_2,…, v_n)\)。

\(A\)の転置\(A^T\)と\(A\)を行列で乗算すると、\(n×n\)の正方行列\(A^T A\)が得られる。\(A^T A\)は正方行列であるため、特徴の分解を実行でき、得られた固有値と固有ベクトルは次の式を満たす。
$$ (A^T A)\boldsymbol{v_i}=λ_i\boldsymbol{v_i} $$
これで行列\(A^T A\)の\(n\)個の固有値と対応する\(n\)個の固有ベクトル\(v_i\)を取得できる。

\(A\)と\(A\)の転置\(A^T\)を行列で乗算すると、\(m×m\)の正方行列\(AA^T\)が得られる。\(AA^T\)は正方行列であるため、特徴の分解を実行でき、得られた固有値と固有ベクトルは次の式を満たす。
$$ (AA^T) \boldsymbol{u_i}=λ_i\boldsymbol{u_i} $$
これで行列\(AA^T\)の\(m\)個の固有値と対応する\(m\)個の固有ベクトル\(u_i\)を取得できる。

\(Σ\)は対角線上の特異値を除いて全て\(0\)で、各特異値\(σ_i\)を見つけるだけで\(Σ\)が求められる。
$$ \sigma_i = \sqrt{λ_i} $$

各特異値\(σ_i\)のうち、比較的大きいほう(主成分)とそれに対応する特異ベクトル\(u_i, v_i\)を\(k\)個\((k << n)\)残すとAの次元を削減する。
$$ A_{m×n}=U_{m×m}Σ_{m×n}V^T_{n×n} ≈ U_{m×k}Σ_{k×k}V^T_{k×n} $$

実装

以下行列dataSetに対して、SVDアルゴリズムで\((U, \Sigma, V^T)\)を求めて、5次元→3次元つまり2次元を削減してが新しい\(\Sigma\)で\((U* \Sigma*V^T)\)が元の行列dataSetに戻せるかを確かめる。

from numpy import *
def loadExData():
    return[[0, 0, 0, 2, 2],
           [0, 0, 0, 3, 3],
           [0, 0, 0, 1, 1],
           [1, 1, 1, 0, 0],
           [2, 2, 2, 0, 0],
           [5, 5, 5, 0, 0],
           [1, 1, 1, 0, 0]]
dataSet = loadExData()
U, Sigma, VT = linalg.svd(dataSet)
print(f'dataSet:\n{dataSet}')
print(f'U:\n{U}\nSigma:\n{Sigma}\nVT:\n{VT}')
// 小さいSigmaを0にする(削除)
Sig3 = mat([[Sigma[0], 0, 0], [0, Sigma[1], 0], [0, 0, Sigma[2]]])
print(f'U[:,:3] * Sig3 * VT[:3,:]:\n{U[:,:3] * Sig3 * VT[:3,:]}')

ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/svd

結果

\((U* \Sigma*V^T)\)は元のdataSetとほぼ同じ行列だと分かる。

dataSet:
[[0, 0, 0, 2, 2], [0, 0, 0, 3, 3], [0, 0, 0, 1, 1], [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]]
U:
[[-2.22044605e-16  5.34522484e-01  8.41641151e-01 -1.37443101e-02
  -7.57428665e-02 -1.11022302e-16  1.38777878e-17]
 [ 0.00000000e+00  8.01783726e-01 -4.92426901e-01 -2.47257115e-01
   2.31349353e-01  3.15719673e-16 -2.77555756e-17]
 [ 0.00000000e+00  2.67261242e-01 -2.06001597e-01  7.69259966e-01
  -5.42562325e-01 -7.55450741e-16  1.09551769e-16]
 [-1.79605302e-01  2.77555756e-17 -3.00520660e-02 -2.15935735e-01
  -2.94749442e-01  9.05439185e-01 -1.16246358e-01]
 [-3.59210604e-01  5.55111512e-17 -6.01041319e-02 -4.31871470e-01
  -5.89498885e-01 -4.19124526e-01 -3.97074256e-01]
 [-8.98026510e-01  0.00000000e+00  3.60624791e-02  2.59122882e-01
   3.53699331e-01  5.40010673e-16 -6.71525577e-17]
 [-1.79605302e-01  2.77555756e-17 -3.00520660e-02 -2.15935735e-01
  -2.94749442e-01 -6.71901321e-02  9.10394870e-01]]
Sigma:
[9.64365076e+00 5.29150262e+00 8.36478329e-16 6.91811207e-17
 1.11917251e-33]
VT:
[[-5.77350269e-01 -5.77350269e-01 -5.77350269e-01  0.00000000e+00
   0.00000000e+00]
 [-2.46566547e-16  1.23283273e-16  1.23283273e-16  7.07106781e-01
   7.07106781e-01]
 [-7.01908483e-01 -1.02844064e-02  7.12192890e-01 -2.22044605e-16
  -1.66533454e-16]
 [-4.17122461e-01  8.16431808e-01 -3.99309347e-01  0.00000000e+00
  -1.11022302e-16]
 [-0.00000000e+00 -1.96261557e-16  1.96261557e-16  7.07106781e-01
  -7.07106781e-01]]
U[:,:3] * Sig3 * VT[:3,:]:
[[ 4.47427211e-17  1.57774942e-15  2.08638397e-15  2.00000000e+00
   2.00000000e+00]
 [-7.56974048e-16  5.27282824e-16  2.29691224e-16  3.00000000e+00
   3.00000000e+00]
 [-2.27747782e-16  1.76121044e-16  5.16267387e-17  1.00000000e+00
   1.00000000e+00]
 [ 1.00000000e+00  1.00000000e+00  1.00000000e+00  1.03851855e-16
   1.03851855e-16]
 [ 2.00000000e+00  2.00000000e+00  2.00000000e+00  2.07703709e-16
   2.07703709e-16]
 [ 5.00000000e+00  5.00000000e+00  5.00000000e+00 -6.69808260e-33
  -5.02356195e-33]
 [ 1.00000000e+00  1.00000000e+00  1.00000000e+00  1.03851855e-16
   1.03851855e-16]]

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア

機械学習の12、PCA主成分分析

はじめに

液晶画面に数百万画素で写された山の映像が目に入る途端に、脳が3次元の山にイメージするので、つまり多次元(数百万画素)のデータを主成分の3次元に削減(圧縮)すると考えられる。PCA(Principle Component Analysis)主成分分析は最も広く使用されている次元を削減するアルゴリズムで、\(n\)次元の特徴を\(m\)次元にマッピングすることである。主成分とも呼ばれるのは元のn次元の特徴から再構築された\(m\)次元の特徴である。そのうち最初の新しい座標軸の選択は元のデータで最大の分散を持つ方向であり、2番目の新しい座標軸の選択はこの座標軸における分散を最大化してかつ最初の座標軸と直交する座標軸であり、3番目の座標軸の選択はこの座標軸における分散を最大化してかつこれまで2つの軸と直交する座標軸であり、類推によってこのような座標軸を\(n\)個取得できる。殆どの分散が最初の軸\(m\)個に含まれて、後続の軸が騒音や相関などによりこれらの分散はゼロに近いことがわかる。従って残りの軸\((n-m)\)個を無視して最初の軸\(m\)個のみを残すと\(n\)次元の特徴をもつデータを\(m\)次元特徴空間に変換する。これで次元削減処理を実現することに相当する。

手順

・データの標準化、つまりデータからその特徴の平均値を差し引く
・共分散行列を計算
・共分散行列の固有値と固有ベクトルを計算
・固有値を大→小にソート
・最大の特徴ベクトルを保持
・データを特徴ベクトルによって構築された新しい空間に変換

実装

2次元のデータ6組\((-1, 1), (-2, -1), (-3, -2), (1, 1), (2, 1), (3, 2)\)の主成分を求める。

# Python PCA
import numpy as np
def pca(X,k):#k is remained components
  # Calculate mean of each feature
  n_samples, n_features = X.shape
  mean=np.array([np.mean(X[:,i]) for i in range(n_features)])
  # Calculate normalization
  norm_X = X - mean
  # Calculate cov matrix
  cov_matrix = np.dot(np.transpose(norm_X), norm_X)
  # Calculate eigen vectors and eigen values
  eig_val, eig_vec = np.linalg.eig(cov_matrix)
  eig_pairs = [(np.abs(eig_val[i]), eig_vec[:,i]) for i in range(n_features)]
  # Sort eig_vec based on eig_val from big to small
  eig_pairs.sort(reverse=True)
  # Select the top k eig_vec
  feature = np.array([ele[1] for ele in eig_pairs[:k]])
  # Get new data
  data = np.dot(norm_X, np.transpose(feature))
  return data
X = np.array([[-1, 1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
print(pca(X,1))

ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/pca

結果

[[-0.50917706]
 [-2.40151069]
 [-3.7751606 ]
 [ 1.20075534]
 [ 2.05572155]
 [ 3.42937146]]

以下はsklearnを用いる例で、ソースは短くなるが結果の符号が逆になる。

# PCA with sklearn
from sklearn.decomposition import PCA
import numpy as np
X = np.array([[-1, 1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca=PCA(n_components=1)
pca.fit(X)
print(pca.transform(X))

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア

機械学習の11、FP-growth

はじめに

頻出パターンをマイニングするためのアルゴリズムとして、Aprioriアルゴリズムはデータセットを複数回スキャンする必要があり、I/Oは大きなボトルネックとなる。この問題を解決するために、FP-TreeアルゴリズムまたはFP-Growthアルゴリズムとも呼ばれる手法を用いる。またFP-Treeアルゴリズムでは並列計算の手法も施して大量のデータマイニングに対応可能となる。

アルゴリズム

概要

まずは下記例のdataSetのように、Aはデータセットからカントして計8回出現したため、最初の位置に配置されるようにヘッダテーブル(Header Table)をまとめる。それからアイテムをFP-Treeにマッピングする。ヘッダテーブルにあるアイテムはFP-Treeに指して紐付けられる。最後にヘッダテーブルの下のアイテムから上への順でマイニングして、頻出アイテムセットを取得する流れになる。

miniSupport = 2 
step1 dataSet:  
[['A', 'B', 'C', 'E', 'F', 'O'], 
 ['A', 'C', 'G'], ['E', 'I'], 
 ['A', 'C', 'D', 'E', 'G'], 
 ['A', 'C', 'E', 'G', 'L'], 
 ['E', 'J'], 
 ['A', 'B', 'C', 'E', 'F', 'P'], 
 ['A', 'C', 'D'], 
 ['A', 'C', 'E', 'G', 'M'], 
 ['A', 'C', 'E', 'G', 'N']]
step2 sorted dataset:  {frozenset({'F', 'C', 'O', 'A', 'E', 'B'}): 1, frozenset({'A', 'G', 'C'}): 1, frozenset({'E', 'I'}): 1, frozenset({'C', 'D', 'A', 'G', 'E'}): 1, frozenset({'C', 'A', 'G', 'L', 'E'}): 1, frozenset({'J', 'E'}): 1, frozenset({'F', 'C', 'P', 'A', 'E', 'B'}): 1, frozenset({'A', 'D', 'C'}): 1, frozenset({'C', 'M', 'A', 'G', 'E'}): 1, frozenset({'C', 'N', 'A', 'G', 'E'}): 1}
step3 headerTable:  {'F': [2, <__main__.treeNode object at 0x7f4bcea88240>], 'C': [8, <__main__.treeNode object at 0x7f4bcea88f28>], 'A': [8, <__main__.treeNode object at 0x7f4bcea882b0>], 'E': [8, <__main__.treeNode object at 0x7f4bcea882e8>], 'B': [2, <__main__.treeNode object at 0x7f4bcea88ef0>], 'G': [5, <__main__.treeNode object at 0x7f4bcea88390>], 'D': [2, <__main__.treeNode object at 0x7f4bcea88470>]}
conditional tree for:  {'B'}

ヘッダテーブルの作成

下記Header Tableのようにヘッダテーブルをまとめる。

step3 headerTable:  {'A': 8, 'C': 8, 'E': 8, 'G': 5, 'B': 2, 'D': 2, 'F': 2}

FP-Treeの作成

下記FP-TreeのようにFP木をまとめる。

step3 FP-Tree: 
   Null Set : 1
     A : 8
       C : 8
         E : 6
           B : 2
             F : 2
           G : 4
             D : 1
         G : 1
         D : 1
     E : 2

FP-Treeのマイニング

ヘッダテーブルの下のアイテムから上への順でマイニングする。ヘッダテーブルのアイテムに対して、条件パターンベース(Conditional Pattern Base)をまとめて条件FP-Tree(Conditional FP-Tree)を得られる。また頻出度が少ないノードを削除する。この方法で頻出パターンをマイニングする。

step4 conditional tree for:  {'B'}
   Null Set : 1
     A : 2
       C : 2
         E : 2
step4 conditional tree for:  {'C', 'B'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'E', 'B'}
   Null Set : 1
     A : 2
       C : 2
step4 conditional tree for:  {'C', 'E', 'B'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'C'}
   Null Set : 1
     A : 8
step4 conditional tree for:  {'D'}
   Null Set : 1
     A : 2
       C : 2
step4 conditional tree for:  {'C', 'D'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'E'}
   Null Set : 1
     A : 6
       C : 6
step4 conditional tree for:  {'C', 'E'}
   Null Set : 1
     A : 6
step4 conditional tree for:  {'F'}
   Null Set : 1
     A : 2
       B : 2
         C : 2
           E : 2
step4 conditional tree for:  {'F', 'B'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'F', 'C'}
   Null Set : 1
     A : 2
       B : 2
step4 conditional tree for:  {'F', 'B', 'C'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'F', 'E'}
   Null Set : 1
     A : 2
       B : 2
         C : 2
step4 conditional tree for:  {'F', 'E', 'B'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'F', 'E', 'C'}
   Null Set : 1
     A : 2
       B : 2
step4 conditional tree for:  {'F', 'E', 'B', 'C'}
   Null Set : 1
     A : 2
step4 conditional tree for:  {'G'}
   Null Set : 1
     A : 5
       C : 5
         E : 4
step4 conditional tree for:  {'C', 'G'}
   Null Set : 1
     A : 5
step4 conditional tree for:  {'G', 'E'}
   Null Set : 1
     A : 4
       C : 4
step4 conditional tree for:  {'C', 'G', 'E'}
   Null Set : 1
     A : 4
step4&5 frequentItemList:  [{'A'}, {'B'}, {'A', 'B'}, {'C', 'B'}, {'C', 'B', 'A'}, {'E', 'B'}, {'A', 'E', 'B'}, {'C', 'E', 'B'}, {'C', 'E', 'B', 'A'}, {'C'}, {'C', 'A'}, {'D'}, {'A', 'D'}, {'C', 'D'}, {'C', 'A', 'D'}, {'E'}, {'A', 'E'}, {'C', 'E'}, {'C', 'E', 'A'}, {'F'}, {'F', 'A'}, {'F', 'B'}, {'F', 'B', 'A'}, {'F', 'C'}, {'F', 'A', 'C'}, {'F', 'B', 'C'}, {'F', 'B', 'A', 'C'}, {'F', 'E'}, {'F', 'E', 'A'}, {'F', 'E', 'B'}, {'F', 'E', 'B', 'A'}, {'F', 'E', 'C'}, {'F', 'E', 'A', 'C'}, {'F', 'E', 'B', 'C'}, {'F', 'C', 'A', 'E', 'B'}, {'G'}, {'A', 'G'}, {'C', 'G'}, {'C', 'G', 'A'}, {'G', 'E'}, {'A', 'G', 'E'}, {'C', 'G', 'E'}, {'C', 'G', 'E', 'A'}]

手順のまとめ

1・データセット(Data Set)をスキャンして、すべての1アイテムのカウントを取得する。次に、サポート度がしきい値(miniSupport例えば=2)より低いアイテム(非頻出アイテム)を削除して、ヘッダーテーブル(Header Table)に1アイテムを入れて、サポート度の降順(Sort 大→小)に並べる。

2・データセットを再度スキャンして、サブセット(トランザクションセット)毎に非頻出アイテムを除外して、サポートの降順(大→小)に並べて用意しておく。

3・上記用意したサブセットを読み取って、FP-Treeに挿入する。ソートされた順序で最初ソートされたノードは親ノード(Parent Node)で、あとにソートされたノードは子ノード(Child Node)にする。共通の親ノードが存在する場合、対応する共通の親ノードのカウントは1つ増やす。挿入後、新しいノードが生成される場合、ヘッダーテーブルに対応するノードは、ノードリスト(Node List)を介して新しいノードにリンク(Node Link)される。すべてのデータがFPツリーに挿入されるまで、FP-Treeを作成する。

4・ヘッダーテーブルの一番下のアイテムから上へ条件付きパターンベース(Conditional Pattern Base)を見つける。条件付きパターンベースからの再帰マイニングによって、ヘッダーテーブルアイテムの頻出アイテムセット(Frequent Item Set)を取得する。

5・頻出アイテムセット内のアイテム数が制限されていない場合、ステップ4を繰り返して、すべての頻出アイテムセットを取得する。それ以外の場合、アイテム数の要件を満たす頻出アイテムセットのみを取得する。

ソースコード

以下Peter氏が作成したソースコードをご参照ください。
https://github.com/pbharrin/machinelearninginaction3x/tree/master/Ch12

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア

深層強化学習の0、MDPマルコフ決定過程

はじめに

教師あり学習(Supervised Learning)は入力に正しい出力を与える学習に対して、強化学習(Reinforcement Learning)は、試行錯誤を通じて環境に適応する学習である。強化学習メカニズムは、エージェント(Agent)例えばニューラルネットワークが取得する累積報酬(Reward)\(r\)を最大化するための状態(State)\(s\)から行動(Action)\(a\)への方策(Policy)\(\pi\)を獲得する。強化学習に少ない学習データでタスクの遂行と深層学習に連携することから期待が寄せられる。

MDPマルコフ決定過程

マルコフ決定過程(Markov Decision Process)は、状態遷移が確率的に生じる動的システム(確率システム)の確率モデルであり、状態遷移がマルコフ性を満たすものをいう。マルコフ性とは状態\(s_{t+1}\)への遷移がそのときの状態と行動\((s_t,a_t)\)のみに依存するが、それ以前の状態や行動\((s_{t-1},a_{t-1})…\)には関係ないこと。強化学習で時系列状態遷移の表現を簡略するマルコフ決定過程MDPを用いると、累積報酬(Reward)を最大化することをMDPが適用した価値関数を求めることに変わる。状態価値関数と状態-行動価値関数はベルマン方程式(Bellman Euqation)による表現がある。

状態価値関数

MDP状態価値関数、状態-行動価値関数
図1-MDP状態価値関数、状態-行動価値関数

図1から、次式の状態価値関数のベルマン方程式がまとまる。つまり状態価値\(v\)は割引(減衰)\(\gamma\)を考慮した報酬\(r\)の総和となる。
$$\small v_π(s_t)=\sum_{a_t} π(a_t|s_t) \sum_{s_{t+1}} p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+\gamma v_{\pi} (s_{t+1})]\space \space (1) $$
状態価値関数だけでは最適な方策(行動)が分からないので、状態-行動価値関数なら方策(行動)が分かる。

状態-行動価値関数

図1から、次式の行動価値関数がまとまる。つまり状態-行動価値\(q\)は割引(減衰)\(\gamma\)を考慮した報酬\(r\)の総和となる。
$$\scriptsize q_π(s_t,a_t)= \sum_{s_{t+1}} p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+ \gamma \sum_{a_{t+1}}π(a_{t+1}|s_{t+1})q_π(s_{t+1},a_{t+1})]\space \space (2) $$
図1から、状態価値関数と状態-行動価値関数の相互関係が分かる。

相互関係

$$v_π(s_t)=\sum_{a_t}π(a_t|s_t)q_π(s_t,a_t) \space \space (3) \\ \small
q_π(s_t,a_t)=\sum_{s_{t+1}}p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+\gamma v_π(s_{t+1})] \space \space(4)
$$
式(1)~(4)までを利用して累積報酬(Reward)を最大化する方策を求めるには、方策反復法(Policy Iteration)、価値反復法(Value Iteration)、Q計画法(Q-Planning)などがある。

方策反復法

全ての状態の報酬が変わらないほどまで、\(T\)回繰り返す。
$$\scriptsize v_{\pi}^{T}(s_t)=\sum_{a_t} π(a_t|s_t) \sum_{s_{t+1}} p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+\gamma v_{\pi}^{T-1} (s_{t+1})]\space \space (5) $$
全ての状態の報酬から最大の報酬を招く方策は最適方策\(\pi_*^{T+1}(s)\)である。
$$\small \pi_*^{T+1}(s)=\underset{a}{\operatorname{argmax}} \sum_{s_{t+1}}p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+\gamma v_π^T (s_{t+1})] \space \space(6) $$
なお最適方策\(\pi_*^{T+1}(s)\)を最大報酬\(v_*^{T+1}(s)\)に書き換えて価値反復法を表す(7)式となる。

価値反復法

$$\small v_*^{T+1}(s)=\underset{a}{\operatorname{max}}\sum_{s_{t+1}}p(s_{t+1}|s_t,a_t)[r_{a_t}^{s_{t+1}}+\gamma v_π^T (s_{t+1})] \space \space(7) $$

実装

図2に格子4つ中の3つの最適方策を価値反復法の例として実装する。

MDP_value_iteration
図2、MDP価値反復法の例

#
# Title: The best policy calculated with MDP value itertation method
# Author: T.Yanagi
#
import numpy as np
import copy
#
# 価値反復法で3状態x2行動のMDPマルコフ決定過程を解く
#
def value_iteration():

  # 行動の条件確率p[s(t+1)|s(t),a(t)]の設定
  p = [0.5, 0.5, 0.5]

  # 割引率γの設定
  gamma = 0.90
  
  # ループ終了判定基準係数の設定
  epsilon = 0.001

  # 報酬値r[s]の設定
  r = [0.5, 0.5, 0.5, 1.0, 0.0]
  
  # 価値関数r[s]の初期化
  v = [0.0, 0.0, 0.0, 0.0, 0.0]
  v_new = copy.copy(v)

  # 状態-行動価値関数q(s,a)の初期化
  q = np.zeros((3, 2))

  # 方策分布(pi(s))の初期化
  pi = [0.5, 0.5, 0.5]

  # 状態s(t+1)の初期化 3x2
  s_t1 = np.zeros((3, 2))
  s_t1[0, 0] = 2 # up
  s_t1[0, 1] = 1 # right
  s_t1[1, 0] = 3 # up
  s_t1[1, 1] = 4 # right(out)
  s_t1[2, 0] = 4 # up(out)
  s_t1[2, 1] = 3 # right

  iteration = 0
  # 価値反復法の計算
  while True:
    delta = 0.0
    for i in range(3):

      # 行動価値関数を計算
      q[i, 0] = p[i] * (r[int(s_t1[i,0])] + gamma * v[int(s_t1[i,0])])
      q[i, 1] = (1.0 - p[i]) * (r[int(s_t1[i,1])] + gamma * v[int(s_t1[i,1])])

      # 行動価値関数のもとで greedy に方策を改善
      if q[i, 0] > q[i, 1]:
        pi[i] = 1
      elif q[i, 0] == q[i, 1]:
        pi[i] = 0.5
      else:
        pi[i] = 0

    # 改善された方策のもとで価値関数を計算
    v_new = np.append(np.max(q, axis=-1), [0.0, 0.0])

    # 現ステップの価値関数と方策を表示
    print(f'iteration: {iteration}, value: {v_new[:3]} policy: {pi}')
    
    delta = max(delta, abs(np.min(v_new[:3] - v[:3])))
    # 計算された価値関数 v_new が前ステップの値 v を改善しなければ終了
    if delta <= epsilon * (1 - gamma) / gamma:
      # 最適方策を返す
      return pi
    
    # 価値関数を更新
    v = copy.copy(v_new)
    iteration += 1
  
#
# main()
#
if __name__ == '__main__':
  
  # 価値反復法最適方策を探る
  pi = value_iteration()

  # 行動方向表示の初期化
  direction = ['','','']

  # 最適方策を表示
  for i in range(3):
    if pi[i] == 1.0:
      direction[i] = '^'
    elif pi[i] == 0.5:
      direction[i] = 'L'
    else:
      direction[i] = '>'
  print(f'{direction[2]} 0\n{direction[0]} {direction[1]}')

ソースコード
https://github.com/soarbear/Reinforcement_Learning

実行

以下の結果は図2の右にある結果の部分に合致するのを分かる。

iteration: 0, value: [0.25 0.5  0.5 ] policy: [0.5, 1, 0]
iteration: 1, value: [0.475 0.5   0.5  ] policy: [0.5, 1, 0]
> 0
L ^

参考文献

[1]現場で使える!Python深層強化学習入門、翔泳社
[2]Reinforcement Learning: An Introduction. by Richard S.Sutton, Andrew G.Barto.

2+

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア

機械学習の10、Aprioriアルゴリズム

はじめに

スーパーでは、おむつとワインと同時に売れそうだから数多くの商品からおむつとワインが何らかの関連性があるとは。お父さんが子供用品を買うときに自分のご褒美にワインを買ってしまうと考えられる。アメリカ大統領の当選の予想には選挙イベント用のグッズの販売数が多いほうが当選されてしまうのもグッズと当選が強く相関すると考えられる。以上のことから、ビッグデータからアイテムの頻出度(出現頻度)を数えて頻出アイテム集合を検出して、頻出アイテム集合から相関ルールを検出するのは画期的なスーパーでは、おむつとワインと同時に売れそうだから数多くの商品からおむつとワインが何らかの関連性があるとは。お父さんが子供用品を買うときに自分のご褒美にワインを買ってしまうと考えられる。アメリカ大統領の当選の予想には選挙イベント用のグッズの販売数が多いほうが当選されてしまうのもグッズと当選が強く相関すると考えられる。以上のことから、ビッグデータからアイテムの頻出度(出現頻度)を数えて頻出アイテム集合を検出して、頻出アイテム集合から相関ルールを検出するのは画期的なアプリオリ(Apriori)アルゴリズムである。例えばトランザクション数=4、\(\small [(1,3,4),(2,3,5),(1,2,3,5),(2,5)]\)のトランザクション集合(買上げリスト4本と思って良い)にアプリオリ・アルゴリズムを適用すると、次式の頻出ルールで頻出度、相関ルール\(x → y\)で確信度を計算する。
$$ \small 頻出度(x)= \frac{xを含むトランザクション数}{トランザクション数} \\
\small 頻出度(1)= \frac{2}{4} = 50\% \\
\small 頻出度(x,y)= \frac{xとyを含むトランザクション数}{トランザクション数} \\
\small 頻出度(1,3)= \frac{2}{4} = 50\% \\
\small 確信度(x,y)= \frac{xとyを含むトランザクション数}{xを含むトランザクション数} \\
\small 確信度(1,3)= \frac{2}{2} = 100\% \\ \small 確信度(2,3)= \frac{2}{3} = 67\% $$
これで頻出度の閾値(最小頻出度)と確信度の閾値(最小確信度)を決めると、以下Aprioriアルゴリズムの処理手順で閾値以上の相関ルールが見出すことになる。
※ トランザクションの由来は、スーパーで1回ずつの買い物(取引)から得たデータなので、例えば(1,3,4)は1回の買い物から、数字化したデータ、1-おむつ、3-ワイン、4-たまごを表す。

頻出アイテム集合を検出手順】最初に1個の要素からなる候補集合C1を生成して、頻出度が閾値以上であるという条件でふるい分けして、頻出アイテム集合L1を作り出す。次に、頻出アイテム集合L1の要素を組み合わせて2個要素からなる候補集合C2を生成して、頻出度が閾値以上であるという条件でふるい分けして、頻出アイテム集合L2を作り出す…繰り返す。

相関ルールを検出手順】頻出アイテム集合L2から、次に確信度が閾値以上であるとの条件で相関ルールを検出する。次に、頻出アイテム集合L3から…繰り返す。

実装

\(\small [(1,3,4),(2,3,5),(1,2,3,5),(2,5)]\)から決まった頻出度、確信度で相関ルールを検出する。アプリオリ・アルゴリズムでは検出することができると分かる。

ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/apriori

実行

最小頻出度(minSupport): 0.5, 最小確信度(minConfidence): 0.5

[main] minSupport: 0.5, Lk: [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
suppDataList: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
[calcConf] frozenset({3})--> frozenset({2}), conf: 0.67
[calcConf] frozenset({2})--> frozenset({3}), conf: 0.67
[calcConf] frozenset({5})--> frozenset({3}), conf: 0.67
[calcConf] frozenset({3})--> frozenset({5}), conf: 0.67
[calcConf] frozenset({5})--> frozenset({2}), conf: 1.00
[calcConf] frozenset({2})--> frozenset({5}), conf: 1.00
[calcConf] frozenset({3})--> frozenset({1}), conf: 0.67
[calcConf] frozenset({1})--> frozenset({3}), conf: 1.00
[calcConf] frozenset({5})--> frozenset({2, 3}), conf: 0.67
[calcConf] frozenset({3})--> frozenset({2, 5}), conf: 0.67
[calcConf] frozenset({2})--> frozenset({3, 5}), conf: 0.67
[main] minConfidence: 0.5
ruleList: [(frozenset({3}), frozenset({2}), 0.67), (frozenset({2}), frozenset({3}), 0.67), (frozenset({5}), frozenset({3}), 0.67), (frozenset({3}), frozenset({5}), 0.67), (frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({3}), frozenset({1}), 0.67), (frozenset({1}), frozenset({3}), 1.0), (frozenset({5}), frozenset({2, 3}), 0.67), (frozenset({3}), frozenset({2, 5}), 0.67), (frozenset({2}), frozenset({3, 5}), 0.67)]

最小頻出度(minSupport): 0.5, 最小確信度(minConfidence): 0.7

[main] minSupport: 0.5, Lk: [[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
suppDataList: {frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
[calcConf] frozenset({5})--> frozenset({2}), conf: 1.00
[calcConf] frozenset({2})--> frozenset({5}), conf: 1.00
[calcConf] frozenset({1})--> frozenset({3}), conf: 1.00
[main] minConfidence: 0.7
ruleList: [(frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({1}), frozenset({3}), 1.0)]

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

ロボット・ドローン部品お探しなら
ROBOT翔・電子部品ストア