w - 長井研究室

http://apple.ee.uec.ac.jp/isyslab
ロボット情報工学特論 no.8
Advanced Information Engineering for Robotics no.08
第８回：パターン認識と機械学習１～パターン認識～
電気通信大学大学院
情報理工学研究科
知能機械工学専攻
長井隆行
http://apple.ee.uec.ac.jp/isyslab
Outline
認識とは何か？
 パターン認識の手法
 最近傍法
 単純パーセプトロン
 ニューラルネットワーク
 サポートベクターマシン
 強化学習
 決定木
 アンサンブル学習

2
http://apple.ee.uec.ac.jp/isyslab
信号を認識するとはどういうことか？

事前に登録したものの中で最も近い信号（パターン）を探すこと



パターン認識、パターン識別、パターン分類、パターンマッチング
パターン⇔ラベル
予め用意したパターンの辞書と比較
入力と最も近いパターンを判別結果とする

「近さの基準をどうするか？」が大変重要
入力
システム
出力
認識物体
物体画像
識別辞書
3
http://apple.ee.uec.ac.jp/isyslab
パターン認識の流れ
入力信号（パターン）
 一般的な認識システム
前処理
特徴抽出部
識別演算部
出力
認識
信号処理部
ノイズ除去など
周波数情報
エッジ情報
色情報
面積
・・・
識別辞書
識別部
学習
4
http://apple.ee.uec.ac.jp/isyslab
特徴ベクトルと特徴空間
原信号から識別するために必要な本質的な情報
を抽出する ⇒ 特徴量（特徴ベクトル）
 特徴ベクトルによって張られる空間を特徴空間と
呼ぶ
 特徴ベクトルの次元数は高い方が情報量が多く
なる（可能性がある）ため識別しやすくなる（可能
性がある）
 次元数を増やすと必要とされる学習サンプルの数
が指数関数的に増大する ⇒ 次元の呪い

5
http://apple.ee.uec.ac.jp/isyslab
最近傍法(Nearest Neighbor:NN)
例えば部屋に入ってきた人が男性か女性かを判別（認識）しよう
とすると・・・
髪の毛の長さ

赤い四角が女性のデータ
青い丸が男性のデータ
三角は男性か女性か？
背の高さ


注）どのような特徴ベクトル
を使うかは別の問題
全ての可能なパターンを辞書に登録しておくことは現実的ではな
い（全世界の全ての人の情報をもつことはほぼ不可能）
代表的なパターン（プロトタイプ）のみ登録し、そのどれに近いか
で判別を行う
6
http://apple.ee.uec.ac.jp/isyslab
k最近傍法(k-Nearest Neighbor:NN)
 入力パターンに近いk個の情報を使って判断する
 多数決で決める
女性：1、男性：2
髪の毛の長さ
女性：3、男性：0
女性：0、男性：3
k=3の場合
背の高さ
7
http://apple.ee.uec.ac.jp/isyslab
識別境界と学習
プロトタイプが決まると特徴空間（平面）での識別境
界が一意に決まる
 プロトタイプが少ないほど識別の精度が悪くなる（可
能性が高い）
 プロトタイプが多いと計算が大変


どのようにプロトタイプを決めればよい？
⇒学習！
基本的に学習とは識別するためのパラメータを設定して
学習用のデータを使ってそのパラメータを計算することに相当する
8
http://apple.ee.uec.ac.jp/isyslab
男女を分ける例
髪の毛の長さ
髪の毛の長さ
NN法においてプロトタイプの数や位置を変化させると・・・
背の高さ
髪の毛の長さ
背の高さ
髪の毛の長さ

背の高さ
背の高さ
一本の直線で分離できる（線形分離可能）
9
http://apple.ee.uec.ac.jp/isyslab
単純パーセプトロン

線形分離可能であるなら直線のパラメータを求めればよい（学習）
サンプルができるだけ正しく分類できるようにパラメータを求める
x1
w0 x0  w1 x1  w2  0
髪の毛の長さ

x0
背の高さ
線形識別関数
 0 : 男性
f ( x; w )  w x  
 0 : 女性
T
 w0 
 x0 
w   w1  x   x1 
 
 w2 
 1 
入力
x0
x1
1
wT x  0
重み
w0
w1
出力

w2
10
http://apple.ee.uec.ac.jp/isyslab
学習と評価関数

パラメータを求めるために「そのパラメータがどれだけよい仕事を
するか」を評価するための評価関数を定める
パラメータを求める（学習）とはその評価関数の最小化問題である
( xi , bi )  (145,50,1)
x1
直線を動かすと評価関数の
値が変化する
髪の毛の長さ

x0
背の高さ
J ( w )   ( w T xi  bi ) 2
i
 1 : 男性
f ( x; w )  w x  b  
 1 : 女性
T
ラベル
wについてJを最小化
11
http://apple.ee.uec.ac.jp/isyslab
学習方法その１
 閉じた解（Closed-from
solution）
ここでの問題は arg min J ( w )
w
J ( w )   ( w T xi  bi ) 2  ( Xw  b)T ( Xw  b)
i
 w T X T Xw  2bT Xw  bT b
２次形式の最小化なので
J ( w )
 2 X T Xw  2 X T b  0
w
1
w  (X X) X b
T
T
 x0T 


X   
 x TN 1 


入力信号
（特徴量）
 b0 
b    
bN 1 
正解ラベル
N個の学習サンプル
12
http://apple.ee.uec.ac.jp/isyslab
学習方法その２
 最急降下法を使う
 初期値から誤差が減少する方向に徐々に動
かすことで解を求める
（１）wに初期値を与える w0
（２） wを更新する
J ( w )
wk  wk 1  
w w  wk 1
（３）収束しなければ（２）へ戻る
13
http://apple.ee.uec.ac.jp/isyslab
単純パーセプトロンの限界


問題が常に線形分離可能とは限らない（可能性が高い）
複雑な問題に対処するためには非線形な識別関数が必要
入力1
パターン1
0
0
0
パターン2
0
1
1
パターン3
1
0
1
パターン4
1
1
0
(1,0)
XOR問題
入力2 出力
(0,0)
(1,1)
(0,1)
14
http://apple.ee.uec.ac.jp/isyslab
ニューラルネットワーク
ニューラルネットワーク（神経回路網）
 非線形な識別境界
 パーセプトロンの限界をとり除く
 優れた学習方法（誤差逆伝播法:BP）

o pi wij net pj
o pj
ユニット i
ユニット j
入力層
中間層
重み
出力層
 
非線形関数
（シグモイド関数） 15
http://apple.ee.uec.ac.jp/isyslab
順伝播
 ニューラルネットワークの出力計算
o pi
wij net pj
ユニット i
o pj
ユニット j
net pj   wij o pi
i
o pj  f j (net pj )
これを繰り返すことで出力が計算される
重み
シグモイド関数
1
f ( x) 
1  e x
f ( x)  f ( x)(1  f ( x))
16
http://apple.ee.uec.ac.jp/isyslab
学習方法（逆誤差伝播法）


所望の出力との2乗誤差を最小とする重みを求める
最急降下法を使う
1
Ep 
net pj
net pk
o pi wij o pj w jk o pk
2
2
(
t

o
)
 pj pj
j
wij  wij   p wij
E p
wij


E p
net pj
 p wij  
E p net pj
net pjはsigmoidを通す前の出力
net pj
wij
net pj wij
  pj  
：誤差（評価）関数
E p o pj
o pj net pj
次のページ
E p
：重みの更新
wij


wij
w o
o pj
net pj
ij
pi
 o pi
i
 f j(net pj )
17
http://apple.ee.uec.ac.jp/isyslab
学習方法（逆誤差伝播法）続き

出力層と中間層で場合分け
E p
o pj
E p
o pj

k
 (t pj  o pj )

k
：出力層
E p net pk
net pk o pj
E p
net pk

k
w jk    pk w jk
k
E p
net pk

w jk o pj

o pj j
：中間層
後ろから逆向きに誤差情報を伝播している形になっている
18
http://apple.ee.uec.ac.jp/isyslab
非線形写像
 非線形識別関数の近似問題
 高次元空間に写像することで線形分離可能とする
 非線形写像
もとの変数
x1

xN
xi

分離できない
高次元ベクトル空間（無限次元でもOK）
( x1 )


( x N )
変換後のデータに
線形の手法を用いる
非線形相関などが
考慮できる
( xi )
高次元空間
分離できる
19
http://apple.ee.uec.ac.jp/isyslab
高次元空間におけるパターン識別

パーセプトロンにおけるカーネル法の利用
高次元空間であれば線形分離可能
⇒単純パーセプトロンが使える


高次元空間上でのパーセプトロンの計算
特徴量の次元が非常に高い（もしくは無限次元）
 計算が大変（もしくは不可能）
⇒カーネルトリックを使う

高次元空間
1 ( xi )
入力

xi
非線形写像
 2 ( xi )

  ( xi )
重み
w1
w2
出力


w
内積計算
無限次元では計算できない
20
http://apple.ee.uec.ac.jp/isyslab
カーネル法（カーネルトリック）

高次元空間で内積を計算したい
⇒パーセプトロンは重みと入力の内積計算が基本
 むしろ内積さえ計算できれば写像された特徴自体の計算は
必要ない
(x)、( ) それぞれは必要なくそれらの内積 ( x)  ( ) が計算できればOK
変換  を与える代わりに内積が ( x)  ( )  K ( x,  ) と計算できる
ようなカーネル関数 K ( x,  ) を与える
高次元ベクトル空間と非線形変換は自然に定まる
K ( x,  )
データ x と  の類似度を規定している
21
http://apple.ee.uec.ac.jp/isyslab
カーネルの条件
 カーネルとして使える条件
対称性と正定値性を満たせばよい
K ( x, y)  K ( y, x)
任意の点 x1 ,, xn と実数 1 ,,  nに対して
対称性
n
   K ( x, y )  0
i , j 1
i
j
正定値性
 正定値カーネルの例
線形カーネル： K ( x, y)  xT y

（ユークリッド内積）
ガウスカーネル： K ( x, y)  exp  x  y /  2
多項式カーネル： K ( x, y)  (c  xT y) d
2

(  0)
(c  0, d  N )
22
http://apple.ee.uec.ac.jp/isyslab
サポートベクターマシン（SVM）

カーネルトリックの利用
 線形分離が可能な高次元特徴空間へ写像
 識別にパーセプトロンの考え方が使える！

識別超平面におけるマージンを考慮する
 パーセプトロンでは識別できればよかった
 識別できる超平面は無限に存在する

その中から最も良いものを選ぶには？
⇒識別し易さを考慮する
⇒汎化性能を向上
23
http://apple.ee.uec.ac.jp/isyslab
マージン最大化
 どのような境界線がいいのか？
サポートベクトル
色々な境界が考えられる
1
2
1
xi
2
このマージンを最大とする超平面を求める
24
http://apple.ee.uec.ac.jp/isyslab
SVMの学習定式化
 問題の定式化（主問題）
g ( x)  0
1
2
g ( x)  1
g ( x)  0
g ( x)  1
xi
g ( x)  1
| g ( xi ) |
w
 1 if xi  1
g ( xi )  w xi  b
 1 if xi   2
t
最小化
制約条件
g ( x)  1
1
2
1
w
1
w
 1  g ( x)  1
yi (wt xi  b)  1  0 ：条件
1 2 n
1 2
LP ( w, b,  )  w   i [ yi ( wt xi  b)  1]
G ( w)  w
2
i 1
2
n
L n
L
ラグランジュ
t
 w   i yi xi  0
  i yi  0
yi (w xi  b)  1  0
w
i 1
未定乗数法 b i 1
25
http://apple.ee.uec.ac.jp/isyslab
SVMの学習双対問題
n
1 2 n
LP ( w, b,  )  w   i [ yi ( wt xi  b)  1]
2
i 1
 双対問題
w   i yi xi
i 1
L n
  i yi  0
b i 1
n
n
n
1 2 n
1 2
t
t
F ( )  w   i [ yi ( w xi  b)  1]  w  w  i yi xi  b i yi   i
2
2
i 1
i 1
i 1
i 1
n
n
1 2
1 2
t
 w  w w  0   i   i  w
2
2
i 1
i 1
条件
最大化
n
1
F (i )  i   i  j yi y j xit x j
2 i , j 1
n
 y
i 1
i
i
0
i  0
26
http://apple.ee.uec.ac.jp/isyslab
応用例
 Bag
of featuresの識別による一般物体認識
27
http://apple.ee.uec.ac.jp/isyslab
強化学習
動物の学習機構を真似る！
 古典的条件付け（条件反射：パブロフの犬）
 オペランド条件付け


自発的に行ったある反応に対して強化子（褒美）または罰子（罰）が与
えられることによって、その反応の生起頻度が増加または減少すること
教師なし学習（常に学習サンプルと正解ラベルが対で与えられ
るわけではない）
 ある状態になると報酬（負の場合もある）が与えられる
 将来的な報酬を最大にするように行動を選択する（学習する）
 試行錯誤による学習

28
http://apple.ee.uec.ac.jp/isyslab
強化学習
状態の観測
状態遷移
環境
状態
報酬
行動の選択
行動
行動の実行と状態遷移
エージェント（学習者）
政策(policy)
報酬関数(reward function)
価値関数(value function)
状態と報酬の観測
パラメータの更新
No
終了条件を満たすか？
Yes
学習手順の例
試行の終了
29
http://apple.ee.uec.ac.jp/isyslab
強化学習の要素

方策
 状態sと行動aの関数p


(s, a)
p (s, a)は状態sで行動aを選択する確率を表している
報酬関数
 良い悪いの基準となる関数
 報酬が高いほどその状態が望ましい
 最終的に得られる報酬の総和を最大化することが目的

価値関数
 大局的なその状態の望ましさを表す
⇔報酬関数は即時的・局所的な望ましさを表している
 状態価値関数
 行動価値関数
30
http://apple.ee.uec.ac.jp/isyslab
マルコフ決定過程（MDP）

確率変数：X
 Xが取る値の確率が確率分布で規定されている
 時刻tにおけるXの値の系列{Xt}は確率過程

XtがXt-1のみによって決まる確率過程
 マルコフ過程（マルコフ性）

状態遷移確率が時間と共に変化しないマルコフ過程
 マルコフ決定過程
 有限MDP
(行動と状態が有限)
報酬r
行動a
状態s
状態s’
1ステップ前以前のことは関係がない！
31
http://apple.ee.uec.ac.jp/isyslab
問題設定



具体的な問題を考える
チンパンジーにボタンを押させる
ルール





電球がついていない場合はR（赤）のボタンを押すと電球がつく
電球がついている場合にR（赤）のボタンを押すと電球が消える
電球がついている場合はB（青）のボタンを押すと食べ物がもらえる
電球がついていない場合にB（青）のボタンを押しても何も起こらない
おなかがすいた時にどのように行動するべきかを学習するには？
食べ物
R
B
32
http://apple.ee.uec.ac.jp/isyslab
Q学習
状態と行動（状態・行動空間）を考える
 行動

 Rボタンを押す（R-Push）

Bボタンを押す（B-Push）
状態
 電球がついている(On)
電球がついていない(Off)
行動a
Q値
Q(s, a)
状態s
R-Push B-Push
On
？
？
Off
？
？
33
http://apple.ee.uec.ac.jp/isyslab
政策

ランダム手法


グリーディー手法


グリーディ－手法と同様に選択するが確率eでランダムな行動を選択する
ルーレット選択


常に価値が最大となる行動のみ選択する
eグリーディー手法


全ての行動をランダムに選択する
行動価値関数Q(s,a)の大きさに比例した確率で行動を選択する
ソフトマックス行動選択手法

Gibbs分布に従って行動を選択する（温度パラメータによってグリーディー
手法とランダム手法のバランスを取る）
現在の価値関数が最適である保証がないことに注意
34
http://apple.ee.uec.ac.jp/isyslab
Q学習でのQ値の更新
Q学習では以下の式に従ってQ値を更新していく
 MDPでは全状態で全ての行動を十分な数だけ選択す
るとQ値は最適値に収束することが保証されている
 収束後はグリーディー手法で行動するのが最適



Q( st , at )  (1   )Q( st , at )   rt 1   max Q( st 1 , a)
a


状態 st で行動 at を選択した際に状態が st 1 に遷移
rt 1は行動した際に得られた報酬
max Q( st 1 , a) は次状態で選択可能な行動のQ値の最大
a
 は割引率

ただし
 (t )  
t 0

2

(
t
)


t 0
35
http://apple.ee.uec.ac.jp/isyslab
MATLABでシミュレーション
MaxNumEpisode=100; %試行回数の最大値
alpha=0.3;
%学習係数
gamma=0.9;
%割引率
epsilon=10;
%epsilon-greedy法
NumState=2;
%状態の数
NumAction=2;
%行動の数
%Qテーブルの初期化
Qtable=zeros(NumState,NumAction);
CurrentState=1;
%現在の状態
CurrentAction=1;
%現在の行動



eグリーディー手法で探索
１０%の確率でランダムな行動をとる
食べ物を得ると報酬10が与えられる
QlearningMain.m
%最大回数繰り返す
for i=0:MaxNumEpisode
%行動の選択（epsilon-greedy法）
CurrentAction=SelectAction(Qtable, CurrentState, epsilon);
%行動をする（報酬と新しい状態へ遷移）
[reward, newState]=DoAction(CurrentState, CurrentAction);
%新しい状態での最大Q値
QvalueMax=max(Qtable(newState,:));
%Q値の更新
Qtable(CurrentState,CurrentAction)...
=(1-alpha)*Qtable(CurrentState,CurrentAction)+alpha*(reward+gamma*QvalueMax);
%状態を更新
CurrentState=newState;
end
36
http://apple.ee.uec.ac.jp/isyslab
MATLABでシミュレーション続き
function [reward, newState]=DoAction(CurrentState, CurrentAction)
%行動した場合の新しい状態と報酬
%
newStateTable=[2 1;1 1];
rewardTable=[0 0;0 10];
newState=newStateTable(CurrentState, CurrentAction);
reward=rewardTable(CurrentState, CurrentAction);
関数
DoAction.m
function CurrentAction=SelectAction(Qtable, CurrentState, epsilon)
%行動の選択関数
%epsilon-greedy法
%
%乱数
randValue=ceil(100*rand(1,1));
if(randValue<epsilon)
CurrentAction = ceil(size(Qtable,2)*rand(1,1));
else
[maxval, CurrentAction]=max(Qtable(CurrentState,:));
end
SelectAction.m
37
http://apple.ee.uec.ac.jp/isyslab
MATLABでシミュレーション続き
 Q値の変化
ボタンRを押す
ボタンBを押す
e  30
状態１における行動
状態２における行動
e  95
状態１における行動
状態２における行動
38
http://apple.ee.uec.ac.jp/isyslab
部分観測マルコフ決定過程
状態遷移
状態は直接的に観測できるわけではない
⇒状態が部分観測
状態
環境
報酬
行動
POMDP上での動作
1.
2.
3.
4.
状態sの確率分布に従って行動aを生成
エージェント（学習者）
状態の推定値を行動によって変更
ユーザが行動する
エージェントは観測値を観測し、その値に従って状態の分布を推定
39
http://apple.ee.uec.ac.jp/isyslab
ＰＯＭＤＰを用いた対話制御







ルールを設計者が決める必要がある
音声認識の精度を考慮することが困難
ユーザモデルを考慮することが困難
ルールを学習する
音声認識の精度に応じて方策
が変わる
ユーザに適応して学習すること
が可能
大量の学習データが必要
40

Download Report