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

はじめに

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

\(MDP\)マルコフ決定過程

マルコフ決定過程\((Markov \space Decision \space Process=MDP)\)は、状態遷移が確率的に生じる動的システム(確率システム)の確率モデルであり、状態遷移がマルコフ性を満たすものをいう。マルコフ性とは状態\(s_{t+1}\)への遷移がそのときの状態と行動\((s_t,a_t)\)のみに依存するが、それ以前の状態や行動\((s_{t-1},a_{t-1})\)には関係ないこと。強化学習で時系列状態遷移の表現を簡略するマルコフ決定過程\(MDP\)を用いると、累積報酬\(r\)を最大化することを\(MDP\)が適用した価値関数を求めることに変わる。状態価値関数と状態-行動価値関数はベルマン方程式\((Bellman \space 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)までを利用して累積報酬を最大化する方策を求めるには、方策反復法\((Policy \space Iteration)\)、価値反復法\((Value \space 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翔・電子部品ストア

機械学習の9、教師なしk平均法

はじめに

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

非階層クラスター分析とは異なる性質のものが混ざり合った集団から、互いに似た性質を持つものを集めてクラスターを作る方法である。ただし、予めいくつのクラスターに分けるかは先に決める必要がある。k平均法(k-means)は非階層クラスター分析の一つで、クラスターの平均(Means)を用いて、あらかじめ決められたクラスター数k個に分類する方法である。

k-means

1、全てのサンプルに最も近いクラスタセンタを探る→2、クラスタ平均値(Mean)でクラスタセンタを更新する→再度1を実行する→再度2を実行する、クラスタセンタが変わらないまで1の実行を繰り返す。

実装

複数のポイントを4クラスタに配属する。

k_means_test
k_means_test

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

実行

centroids:
[[-2.46149268 -0.60273756]
 [-0.57051504 -3.25574076]
 [ 2.85356363  0.16031334]
 [-3.54201389 -3.13476225]]
centroids:
[[-2.46650438  2.55882843]
 [ 2.12143555 -3.58637036]
 [ 2.8287018   1.4343227 ]
 [-3.59385056 -2.94282822]]
centroids:
[[-2.46154315  2.78737555]
 [ 2.54173689 -3.11892933]
 [ 2.71502526  2.5965363 ]
 [-3.53973889 -2.89384326]]
centroids:
[[-2.46154315  2.78737555]
 [ 2.65077367 -2.79019029]
 [ 2.6265299   3.10868015]
 [-3.53973889 -2.89384326]]

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

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

機械学習の8、決定木

はじめに

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

決定木は回帰問題に関するアルゴリズムを実現する。決定木には回帰木(Regression Tree)とモデル木(Model Tree)が含まれる。過学習を防ぐために事前剪定(Pre-Pruning)と、決定木の構築後の剪定即ち事後剪定(Post-Pruning)が導入される。最後に、回帰木と標準線形回帰を比較する。

決定木のデータ分割用の特徴量を選択する一般的な方法としてはID3、C4.5、C5.0、CARTアルゴリズムがある。この記事では、主にCARTアルゴリズムを使用する。

CART

CART(Classification And Regression Tree)は決定木アルゴリズムで、2分再帰分割の手法である。分割方法は最小距離ベースのGini係数推定関数を使用して、現在のデータセットを2つのサブセットに分割して2つのサブ木ができてしまう。よってCARTアルゴリズムによって生成される決定木は単純な2分木である。目的変数がカテゴリ変数のときは回帰木(Regression Tree)だが、目的変数が連続数値変数ならモデル木(Model Tree)が得られる。

分割用特徴量と最適な分割点

決定木を使用して回帰問題を解くには、サブ木を生成する分割点としてある特徴量およびその特徴量の値を選択する必要がある。選択基準は分割されたデータの2つの部分に最高の純度を持たせる。離散データの場合、分割されたデータの2つの部分にGini不純物の変化が所定値以下の際の特徴量と分割点を決める。連続変数の場合、データの分散を最小化する最小2乗残差を計算して得られた特徴量と分割点を決める。直感的に理解は分割されたデータの2つの部分に最も近い値を持たせるという。これで以下分割終了条件を満たすまでにデータを分割する。

分割終了条件

・ノード内すべての目的変数の値は同じで、さらに分割する必要はなくこの値を返す。
・木の深さが事前に指定値に達した。
・不純度は指定値よりも小さい、つまりさらに分割必要ない。
・ノード内のデータ量が指定値より少ない。

実装

・5箇所に集まる離散ポイントの回帰木を作成する。
・線状、連続するように見えるポイントのモデル木を作成する。
・モデル木を作成して線形回帰の結果を比較する。
ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/decision_tree

結果

回帰木

regression_tree
regression_tree

ノード・葉っぱ

regression_tree: {'feat_idx': 0, 'feat_val': 0.400158, 'left': {'feat_idx': 0, 'feat_val': 0.208197, 'left': -0.023838155555555553, 'right': 1.0289583666666666}, 'right': {'feat_idx': 0, 'feat_val': 0.609483, 'left': 1.980035071428571, 'right': {'feat_idx': 0, 'feat_val': 0.816742, 'left': 2.9836209534883724, 'right': 3.9871632}}}

モデル木

model_tree
model_tree

ノード・葉っぱ

mode_tree: {'feat_idx': 0, 'feat_val': 0.304401, 'left': matrix([[3.46877936],
        [1.18521743]]), 'right': matrix([[1.69855694e-03],
        [1.19647739e+01]])}

モデル木と、ノード・葉っぱから見ると、特徴量=0.304401を境目とした2段の直線が分かる。

回帰木と線形回帰の比較

compare_regressionTree_with_lineRegressio
赤:線形回帰 緑:回帰木

相関係数

linear regression correlation coefficient: 0.9434684235674755
regression tree correlation coefficient: 0.9780307932704089

図、相関係数から見ると線形回帰のほうと比べて回帰木のほうがサンプルポイントに良く相関するのが分かる。

参考文献

[1] PeterHarrington. Machine Learning in Action.

2+

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

機械学習の7、回帰

はじめに

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

回帰は分類と同じく予測プロセスで、分類との違いは回帰で予測される変数が連続的であるのに対して、分類では離散的だという。回帰は統計学で最も有用なツールである。

線形回帰

線形回帰(Linear Regression)は入力\(X\)に定数\(\boldsymbol{w}\)を乗算して出力\(\boldsymbol{y}\)を得ることができる。これには当てはまらないと他に非線形回帰と呼ばれるのがある。\(\boldsymbol{w}\)の推定値\(\hat{\boldsymbol{w}}\)は最小2乗法(Least Squares Method)から求められて、\(\boldsymbol{w}\)として使われる。
$$ \boldsymbol{y} = X^T\boldsymbol{w} \\ \hat{\boldsymbol{w}} = (X^TX)^{-1}X^T \boldsymbol{y} $$
しかし線形回帰の\(\hat{\boldsymbol{w}}\)は最小2乗の合計から求めた結果で場合により良い結果を予測できなくつまり未学習(Underfitting)となってしまう。以下重み付きで予測誤差を減らそうとする。

重み付き線形回帰

重み付き線形回帰(Locally Weightedlinear RegRession、LWLR)は、より近いポイントが重みをもつようになると予測の正確さが高まる。\(\hat{\boldsymbol{w}}\)は以下のように求める。
$$ \hat{\boldsymbol{w}} = (X^TWX)^{-1}X^TW \boldsymbol{y} $$ガウシアンカーネル関数を用いる場合、 $$ \boldsymbol{w}[i,i] = exp({\frac{|x_i-x|}{-2k^2}}) \\ \boldsymbol{w}[i,j] = 0, \space i \ne j$$
しかし標本数は特徴量より少ない場合、上式の逆行列が求められなく差分を補足してリッジ(Ridge)回帰となる。

リッジ(Ridge)回帰

$$ \hat{\boldsymbol{w}} = (X^TWX+\lambda I)^{-1}X^TW \boldsymbol{y} $$
と同時に、相関している特徴量が存在の可能性あるので、交差検証(Cross Classification)を通して最適の\(\lambda\)を決める。また特徴量を減少(Shrinkage)する方法がある。以下拘束条件を追加するラッソ回帰がある。

ラッソ(Lasso)回帰

$$\sum_{k=1}^n|\boldsymbol{w}_k| \le \lambda $$リッジ(Ridge)回帰、ラッソ(Lasso)回帰より、以下に簡単の方法がある。

前向き段階的回帰

前向き段階的回帰(Forward Stagewise Regression)はラッソ回帰に似てて近い結果が得られる。最初はすべての重みが0に設定されて、各ステップで少しづつ重みの増減を行う。

実装

前向き段階的回帰でポイントグループの回帰係数を求めてみよう。
ソースコード
https://github.com/soarbear/Machine_Learning/tree/master/regression

結果

[[0.    0.    0.    0.001 0.    0.    0.    0.   ]]
[[0.    0.    0.    0.002 0.    0.    0.    0.   ]]
[[0.    0.    0.    0.003 0.    0.    0.    0.   ]]
...
[[ 0.044 -0.011  0.12   0.022  2.023 -0.963 -0.105  0.187]]
[[ 0.043 -0.011  0.12   0.022  2.023 -0.963 -0.105  0.187]]
[[ 0.044 -0.011  0.12   0.022  2.023 -0.963 -0.105  0.187]]

参考文献

[1] PeterHarrington. Machine Learning in Action.

1+

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