ヒューマンコンピュータインタラクション特論
第5回

情報理工学部門

複合情報工学分野

Human-Computer Interaction (HCI) 研究室
小野哲雄（8-12室）
tono@ist.hokudai.ac.jp

授業計画 (予定)
1. 10/1(火) 4限 (小野) HCI入門
2. 10/4(金) 3限 (小野) HCI概論
3. 10/8(火) 4限：[休講]4. 10/11(金) 3限 (小野) HCI概論(2) ＃論文発表の説明
5. 10/15(火) 4限 (小野) HCIの構成原理と構成方法(1) ＃登録開始
6. 10/25(金) 3限 (小野) HCIの構成原理と構成方法(2)7. 10/31(木) 4限 <- 火曜授業 (小野) [論文発表1(1)]8. 11/1(金) 3限 (小野) [論文発表1(2)]9. 11/5(火) 4限 (小野) ヒューマンロボットインタラクション(HRI) ＃説明
10. 11/8(金) 3限 (小野) ヒューマンエージェントインタラクション(HAI) #登録
11. 11/12(火) 4限 (小野) Predicting Human Decision-Making (1)12. 11/15(金) 3限 (小野) Predicting Human Decision-Making (2)13. 11/19(火) 4限 (坂本) HCIにおける実験と評価(1)
14. 11/22(金) 3限 (坂本) HCIにおける実験と評価(2)
15. 11/26(火) 4限 (小野) [論文発表2(1)]16. 11/29(金) 3限 (小野) [論文発表2(2)]2HCIの構成原理と構成方法（2）
インタフェースの手法：
入力(認識)・出力3

講義の概要（１）：HCI全般
次世代インタフェース
HCIの構成原理・方法

人のインタフェース特性
HCIの構成原理と構成方法
実験と評価

ハードウェアインタフェース
HCIの構成原理・方法

インタフェースの手法

インタフェースの評価
実験と評価

インタラクションデザイン

参考：ヒューマンコンピュータ
インタラクション入門、椎尾、
2010“Designing Interactions”

4

講義の概要（２）：HRIとHAI
HRI

Human-Robot Interaction

Human-Agent Interaction
HAI

対象をロボットに限定

対象は人工物（限定なし）

HCIとの相違点：人と「エージェント」のインタラクションデザインを研究
HCIとの共通点：人を含む「開放系」を研究の対象とする

5

前回：HCIの構成原理と構成方法 (1)‒

インタフェースの手法：入力・出力
出力インタフェースの手法••

従来の出力デバイス、Virtual Reality、Augmented
Reality
特徴
‒
‒
‒

‒

理論的なアプローチがしづらい→正解がみつけづらい製作（試作）のコストが高い
応用先は多い（特に、エンタテインメント系）

入力インタフェースの手法••••

深層学習 (CNN)
識別(SVM)
認識アルゴリズム (DPマッチング、隠れマルコフ
モデル
部分観測マルコフ決定過程 (POMDP）

HCIの構成原理と構成方法 (2)HCIと機械学習
CNN

7

HCIにおける機械学習とは？(1)‒

機械学習の分類 (荒木 14)

OpenPose9

人物の姿勢推定‒

モーションキャプチャを用いた動作計測

OpenPose (2016)

OpenPose (1)
‒

論文情報
•
•
•

‒

“Realtime Multi-Person 2D Pose Estimation
using Part Aﬃnity Fields”
Zhe Cao Tomas Simon Shih-En Wei Yaser
Sheikh (CMU)
CVPR 2017

概要
•
•
•
•
•

身体部位の関係性 (part affinity) を活かした、
リアルタイムの2D姿勢推定(pose estimation)
CNNの組み合わせで画像内の人物姿勢の推定
NP-hard問題を緩和法(relaxation)を用いて解く
top-downアプローチではなく、bottom-upア
プローチ
実時間処理可能OpenPose (2)‒姿勢推定の難しさ•

複数人写っている2D画像中の各人の身体部位の
位置を検知
困難な点

•

–
–
–

‒

人数、スケールが不定
人同士のインタラクション(occlusionによる干渉)
人数に比例して計算量増加

従来手法
•
•

top-downアプローチ：人の検知を行い、その後、個人の姿勢推定問題点üü

画像内の人の検知に失敗すると、姿勢推定できない
人数に比例して計算量増大

OpenPose (3)
‒

提案手法
•

画像中の身体部位の位置のみではなく、部位間の関連度(aﬃnity)もエンコードする
一度に画像全体の中の複数人に対して姿勢推定を行うbottom-upアプローチ → 推定の精度・速度の
改善

•

‒

提案手法のポイント••‒

エンコーディングを学習するCNNユニットのス
テージを繰り返す
身体部位の位置、部位間の関連度のエンコーディン
グを共通で学習するアーキテクチャ

技術・発想の違い•

斬新な発想、価値の高いソースを公開 → 破壊的！

OpenPose (4)‒処理手順a) 入力画像b) 各チャンネルで部位の位置をエンコードc) 部位間の関連度のエンコード：位置情報＋向き
情報を含んだ表現＝Part Aﬃnity Fieldsd) 各部位のつなぎ合わせ部分を2Dベクトルでエンコードできるフィルタを学習e) 姿勢推定完了

OpenPose (5)‒提案アーキテクチャ
•
•
•
•
•

Branch1：(b) confidence mapの予測
Branch2：(c) part aﬃnity fieldsの予測同じBranch1, 2を持つユニットを繰り返す(Stage1〜6)
各Stageの入力は、1つ前のStageにおけるBranch1, 2,
Fを連結したもの
Stageごとに誤差を計算

c
特徴ベクトル

OpenPose (6)‒Stageを重ねるごとで精度が上がる
•
•

右手首検知

右上腕検知

上：(b) confidence map. 右手首検知のチャネル.
Stageを重ねるごとに右手首のconfidenceが上がる下：c) part aﬃnity field. 右上腕の流れをエンコード
するチャネル. Stageを重ねるごとに右上腕の確からしさが上がるOpenPose (7)‒各部位のつながりの確からしさの最大化••検知された部位(part confidence map)を、つながり(part aﬃnity fields)の確からしさを最大化するよ
うに組み合わせる
組み合わせ問題は、網羅的に計算するとNP-Hardな問題となるため、以下の緩和法を導入(1) 各部位につながる部位の事前情報を与える(例. 右肩とつながるのは、首と右肘のみ)(2) 隣り合う部位のみをみて、part affinity fieldsの確からしさを最大化するように組み合わせる
(1)

(2)

OpenPose (8)‒アーキテクチャの定式化：誤差関数、目的関数•

誤差関数

各部位 J, 各つながり C

Pでのアノテーションがあるかどうかで 0 or 1

Stage tにおけるPart confidence map S
予測値

正解値

Stage tにおけるPart affinity field L
各場所 P

•

全体の目的関数：全ステージの足し合わせOpenPose (9)‒アーキテクチャの定式化•••

Part confidence mapの計算手法
Part aﬃnity fieldsの計算手法
部位間マッチングの計算手法(論文参照)

OpenPose (10)‒

実験結果：MPII Multi-Person Dataset••

精度(mAP)：従来の手法DeeperCutを8.5%上回る
速度(inference time)：6桁高速化

OpenPose (11)‒

実験結果：人数による速度変化••

top-downアプローチ：人数が増えると急激に増加
bottom-upアプローチ：ほとんど変化なし

OpenPose (12)‒

本論文のポイント•••–部位の位置と方向の両方を符号化して表現
部位検出と関連度を学習するアーキテクチャ
人の数が増えても計算量抑え、十分な精度

HCIの観点から––ある文脈における人物理解において、複数人物の姿勢推定は重要！
3次元は無理なのかな？

DensePose

24

DesePose (2018)
‒

論文
•
•

‒

“DensePose: Dense Human Pose Estimation
In TheWild”
Rıza Alp Guler, Natalia Neverova, Iasonas
Kokkinos (INRIA, Facebook), CVPR 2018

概要•

2Dの群衆動画から人間の姿勢を推定し、身体のテクチャも貼ってくれるCNNを用いたシステム‒‒提案手法では、Mask-RCNNをベースにした
DensePose-RCNNアーキテクチャを用いて、人体の領域を検出し、パーツ上の3Dサーフェスモデルに対応する点を推定
つまり、複数人が密集した2D画像から人体それぞれの3Dモデルを計算し、画像ピクセルを人体のサーフェス
座標に関連付けることができる

DensePose

HCIと機械学習
SVM

27

HCIにおける機械学習とは？(1)‒

機械学習の分類 (荒木 14)

SVM

SVMの応用事例（１）“Touch & Activate: Adding Interactivity to Existing Objects Using
Active Acoustic Sensing”,
Makoto Ono, Buntarou Shizuki, Jiro Tanaka, UIST2013.

29

SVMの応用事例（２）– “Designing Interactions”を確認しよう！

サポートベクターマシンとは？（１）– サポートベクタ－マシン（support vector
machine: SVM）：••

学習の分類：「教師あり」・「識別」問題
特徴：– 線形モデルを使って、学習データに特化し過ぎな
いような識別面を求める
Cf. ニューラルネットワークによる学習：
非線形のモデル、過学習・局所最適解に陥る問題あり–線形で識別できないデータ：»»

誤識別に対するペナルティ
高次元の空間で線形識別を適用
31

サポートベクターマシンとは？（２）– データを識別する直線は無数に存在する

32

サポートベクターマシンとは？（２）– 以下の場合、右図の識別境界線の方が、未知データに対してよい結果が得られる？

マージン

マージン
33

サポートベクターマシンとは？（２）– SVM：学習データからのマージンが最大となる
識別境界線（識別超平面）を求める手法

マージン

マージン
34

マージン最大化のための定式化（１）–

学習データが線形分離可能で、マージンが最大となる識別面（2値
分類問題に限定．正解情報の値を正例 1、負例 -1）{( xi , yi )},
–
重み（パラ
メータ）

–

–

i = 1,..., N ,yi = 1または − 1

識別面は平面なので、特徴空間上では式(1)で表現（ w, x はd次元のベクトル）w ⋅ x + w0 = 0(1)| w ⋅ x + w0 |Dist ( xi ) =|| w ||(2)

i 番目のデータ xi とこの識別面の距離 Dist ( xi ) は式(2)で表現

式(1)の右辺は0なので、左辺を定数倍して識別面に最も近いデー
タを識別面の式に代入し、その絶対値を1になるように重みを調整

min | w ⋅ x + w0 |= 1

i =1,..., N

識別面に最も近いデータ(3)35

マージン最大化のための定式化（２）–––正例、負例の
両方を表す
制約の式

–
–

式(2)、(3)より、学習パターンと識別面との最小距離は以下となる| w ⋅ x + w0 |min Dist ( xi ) = mini =1,..., Ni −1,..., N|| w ||
1=
式(3)より|| w ||

式(2)より(4)

式(4)がマージンを表すので、マージンを最大にする識別面を求め2る問題は、 || w || （もしくは || w || ）を最小化する問題
w = 0 は解にならないので、すべての学習データを識別できる式(5)の条件を付加

yi (w ⋅ x + w0 ) ≥ 1,

i = 1,..., N(5)

式(5)の制約下での || w || 2 の最小問題を解く
微分を利用して極値を求めて最小解を導くので、乗数1/2を付ける

1
min || w || 22
条件：yi ( w ⋅ xi + w0 ) ≥ 1,

(6)
i = i,..., N

(7 )

36

ある束縛条件のもとで最適化を行う方法

マージンを最大とする識別面の計算（１）–––ラグランジュの未定乗数法を用いて、上記の定式化の問題を解決
具体的には、 g ( x) = 0 という条件の下で、 f (x) の最小値（あるいは最大値）を求める問題は、 L(x, λ ) = f (x) + λg (x) （ただし、 λ はラグランジュ乗数）というラグランジュ関数を導入し、この関数の極値を求める
ラグランジュ関数の x に関する偏微分を0とすると以下の式となる∂f (x)∂g (x)= −λ∂x∂x
最小解で制約と等高線は接する(8)∂f (x)∂g (x)
= −λ
∂x
∂x

制約
制約がない
ときの最小値大

f (x) = 定数

g ( x) = 0

37

マージンを最大とする識別面の計算（２）––ラグランジュの未定乗数法を不等式制約条件で用いる
式(6)、(7)の制約付きの最小化問題は、ラグランジュ乗数 α iを導入して、以下の関数 L の最小値を求める問題となる

N
1
L(w, w0 , α ) = || w || 2 −∑ α i ( yi ( w ⋅ xi + w0 ) − 1)2i =1–
最小値では L の勾配が0になるので、以下の式が成り立つ
N
∂L
=0 ⇒
w = ∑α i yi = 0
(10)
∂w0
i =1
N
∂L
=0 ⇒
w = ∑ α i yi x i = 0
(11)
∂w
i =1

–

(9)

これを式(9)に代入して以下の式を得る
N
1 N
L(α ) = − ∑α iα j yi y j xTi x j − ∑α i
2 i , j =1
i =1

(12)

38

識別面を決めるのに寄与している学習データ

マージンを最大とする識別面の計算（３）–

式(12)を（数値計算ソフトウェアにより）解くと、 α i ≠ 0 となるのはサポートベクタ－に対応するもののみで、ほとんどは α i = 0 となる．
この α i を式(11)に代入して wを得る
N

w = ∑ α i yi x i

(13)

i =1

–

また、 w0は、x + 、x − をそれぞれ正例、負例に属するサポートベク
タ－とすると、以下の式で求められる

1
w0 = − (w ⋅ x + + w ⋅ x − )
2
–

(14)

以上の方法で、学習データが線形分離可能な場合には、マージンを最大にする決定境界を求めることができる

マージンを最大化する決定境界

1
min || w || 22
条件：yi ( w ⋅ xi + w0 ) ≥ 1,

(6)
i = i,..., N

(7 )

39

ソフトマージンによる誤識別データの吸収––

学習データが線形分離可能でない場合
間違ったデータがあってもよいが、それらが識別面からあまり離れていないこと
式(7)の制約を緩める変数（スラック変数） ξ i (≥ 0) を導入して、i 番目のデータが制約を満たしていない程度を示す

yi (w ⋅ xi + w0 ) ≥ 1 − ξi ,–i = i,..., Nξ i は制約を満たさない程度なので、小さい方が望ましい．この値を、マージン最大化の式(6)(7)に加える

N1
min || w || 2 +C ∑ ξi
2
i =1
条件：yi ( w ⋅ xi + w0 ) ≥ 1 − ξi , i = 1,..., N ,

–

(15)

(16)

ξi ≥ 0 (17)

ここで、 C は制約を満たさないデータをどの程度の重みで組み込む
か？
大きければ影響大、小さければ無視する振る舞い
40

重要！

カーネル関数を用いたSVM–––

特徴空間の次元 d が大きい場合、線形識別面が存在する可能性大
この性質を使い、低次元の特徴ベクトルを高次元に写像し、線形分類の可能性を高める
高次元空間上でSVMを使って識別超平面を求める
ポイント：もとの空間におけるデータ間の距離関係を保存するような非線形写像を見つけること
カーネル関数（カーネルトリック）
2次元 ⇒ 線形分離は不可能

3次元 ⇒ 線形識別面で分離可能 41

HCIと機械学習
部分観測マルコフ決定過程

42

応用事例：近年の音声対話システム‒‒‒

対話状況認識（会話シーン分析、マルチモーダルセンシング・フュージョン）
自然言語による多人数対話
対話制御（部分観測マルコフ決定過程）

Situated Interaction project (MSR)

43

Situated Interaction (Microsoft Research)44

応用事例：Human Computation‒–

現時点での情報技術の限界：••

文字認識：崩れた文字は認識できない
機械翻訳：翻訳された文の質が低い•

クラウドソーシング（Crowdsourcing）：

に
y
p
p
a
H
！
が
る
な
みん 解決すを
題
HCIにおける新しいアプローチ：
問‒•

不特定多数の人の寄与を募り、必要とするサービス、
アイデア、またはコンテンツを取得するプロセス

ヒューマンコンピュテーション（Human
Computation）:‒

人間とコンピュータどちらが欠けても解答することが不可能な問題に対し、人間の知能と計算機を組み合わせて解く手法Dr. Luis von Ahnの研究のまとめ:“一石二鳥”手法–

reCAPTCHA：CAPTCHA：ウェブサイトの制限エリアへアクセスを試みるボットの排除＋OCRで認識の難しい文字を課題として紙の本のデジタル化に活かすシステム
•

具体例：
‒
‒

–

ニューヨーク・タイムズの記事アーカイブの電子化
Googleブックスの書籍電子化

Duolingo：
無料の言語学習、及びクラウドソーシング翻訳用プ
ラットフォーム
利用者がコースを受講 → その結果をウェブサイト
やその他の文書の翻訳に使用認識アルゴリズム(1)：DPマッチングによる手書き文字認識47

手書き文字認識とは？
‒認識可能な手書き入力を受け取るコンピュータの機能••

オフライン手書き文字認識（例：郵便番号、OCR）
オンライン手書き文字認識（例：タブレット、タッチパネル）

動的計画法(Dynamic Programming)とは？
・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

49

・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

50・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

51

・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

52

・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

53

・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

54

・単純な動的計画法の例：左下隅から右上隅に至る数値の総和が最小の経路を求める

55

・最適経路決定：トレースバック（traceback）（トレースバックするまで最適経路は決まらない）56

・最適経路の決定！

57

・トレースバックするためには、バックポインタをすべて記憶する必要がある
メモリ消費58

動的計画法とは？
‒

動的計画法の考え方：•‒

最適性原理に基づき、決定すべきN個の最適決定を順次行うことによって問題全体の最適解を模索

最適性原理（Principle of Optimality）• A→C (上): ある問題の最適経路• B：最適経路の通過点• B→C (下): 部分最適経路とすると 矛盾
つまり、最適経路は部分最適経路を含まなくてはならない
最適性原理

59

DPマッチング：音声認識‒‒

動的計画法を利用した、長さが異なるパターン間のマッチ
ング法
全体としての距離が最小となるような対応づけをする

入力パターンと標準パターン
を伸縮しながらマッチング

弾性マッチング

60

DPマッチングの事例(1)•

インタラクティブシステム 時間的に変化する入力パターンを認識する必要あり

61

DPマッチングの事例 (2)•DPマッチング：セグメントの系列A、Bの間のマッチ
ングの度合いを効率的に計算するアルゴリズム‒

各セグメントの間の遷移をどう順序づけるのか？
マッチングの可能性

62

DPマッチングの事例(3)•DPマッチング：‒‒‒

与えられた系列A、Bに対する格子点(1, 1)から
(m, n)までの経路の中の、コスト最少のものを効率よく探すためのアルゴリズム
効率化は、各格子点に至る最少経路のコストを記憶しておけば、いちいちすべての経路のコストを計算する必要がないことに注目
DPマッチングでは、マッチングの度合いを計算する関数の選定方法や知識ベースに蓄える系列集
合の選定方法は任意
この部分をマルコフ確率の理論に基づかせると「隠れマルコフモデル」
63

DPマッチングの形式化(1)：変数定義– テンプレート系列： A(ai ) = a1 , a2 , a3 ,…, aI– 入力系例： B(bi ) = b1 , b2 , b3 ,…, aJ ( I ≠ J )– 対応変換関数： F = c(1),…, c(k ),…, c( K )c(k ) = (i(k ), j (k )) i, j 平面でとる経路– 特徴ベクトル間距離： d (c(k )) = d (ai ( k ) , b j ( k ) )F上各点での特徴ベクトル間の距離– F 上の各点の間の距離： w(k ) = c(k ) と c(k + 1)の間の距離
– A, Bの間の距離： D( A, B)

DPマッチングの形式化(2)：系列間の距離

DPマッチングの形式化(3)：経路制限

DPマッチングの形式化(4)：荷重係数

DPマッチングの形式化(5)：応用1

DPマッチングの形式化(5)：応用2

DPマッチングの形式化(6)：問題

DPマッチング：まとめ
•

要件：
‒
‒
‒

•

特徴ベクトル間の距離が定義されていること
格子点間の移動コスト：探索空間における格子点間の移動コストが定義されていること
包含性：探索空間において、全体問題の最小解を与える経路が部分問題の最小解を与える
経路を含んでいること

要点：
‒
‒
‒

再帰的に部分最適化問題へ帰着できる
前向き経路探索で最小累積距離が得られる
後向き経路追跡（トレースバック）により最
適経路決定

71

認識アルゴリズム(2)：隠れマルコフモデルによる音声認識72

アルゴリズムはどのように使われるのか？
•

音声認識の場合：
Ø 隠れマルコフモデル（HMM）
Ø （DPマッチングも）

音声認識

文章認識

文節認識

単語認識

構文意味解析

HMM類似度判定

単語候補抽出

確率・類似度計算

単語検出

ベクトル量子化
短時間スペクトル抽出

音
素
パ
タ
ー
ン
照
合

音節認識

音素認識

パターン照合

音素パター
ン照合

単語パターン照合（時間軸整合）

ホルマ
ント分析

線形照合

非線形照合

単純
マッチング

DPマッチング

音素
識別73隠れマルコフモデルの応用（1）•単語/品詞の隠れマルコフ・モデル–

例文： time flies like an arrow.

74

隠れマルコフモデルの応用（2）•単語/品詞の隠れマルコフ・モデル–

5通りの構文解釈が可能な文： time flies like an arrow.
•
•
•
•
•

S[ NP/Time VP[ VP/flies PP[ PREP/like NP[ DET/an N/arrow ] ] ] ]S[ VP/Time NP[ NP/flies PP[ PREP/like NP[ DET/an N/arrow ] ] ] ]S[ NP[ ADJ/Time NP/flies ] VP[ V/like NP[ DET/an N/arrow ] ] ]S[ NP[ NP/Time NP/flies ] VP[ V/like NP[ DET/an N/arrow ] ] ]S[ VP[ V/Time NP/flies ] PP[ PREP/like NP[ DET/an N/arrow ] ] ]75

隠れマルコフモデルの事例(1)•

隠れマルコフモデル：–

いくつかの状態を確率的に遷移するマルコフモデルを用いて系列を生成する情報源モデルを表現し、それを使って系列の認識を行う
P([A, D, F]|S1→S2→S3) = 0.6×0.5×0.7×0.7×0.1×0.5

76

隠れマルコフモデルの事例(2)シンボルの系列が生成される確率を計算するためには、与えられた系列の部分系列を生成しうる状
態遷移にそって生起確率を計算し、それを加算す
ればよい
[A]

[A, C][A, C, D]

S1

S1

0.3

0.027

S1

S2
0.042

[A, C, D, F]

0.0

S2

S2

0.03974

0.0

S3

S3

0.000420.002071

77

隠れマルコフモデルの事例(3)•

HMMモデルを使った系列パターン認識–

与えられたHMMモデルとシンボル系列から、その系列を生成するもっとも確からしいHMM中の状態列とその確率を計算する
素朴なアルゴリズム（前向きアルゴリズム）：O(M n)–•

第1シンボルを出力するすべての状態列を求め、次に残った出力列を生成する確からしい確率を求め、、、

マルコフ性を利用 ⇒ ビタビアルゴリズム：O(bMn)–•ある状態に至るまでのすべての可能な状態列を求める必要はなく、そこに至るもっとも確からしい状態列のみ記憶しておけばよい78

隠れマルコフモデルの事例(4)•ビタビアルゴリズム–

各状態に至る確率最大値を与える遷移だけを求める
最適状態遷移系例の計算[A]
0.6,0.5

S1[A, C, D][A, C]
0.3,0.3

0.3

0.3,0.0S1
0.027[A, C, D, F]

S1
0.0

0.7,0.7

0.7,0.2

S2
0.042

0.9,0.7 S2
0.9,0.0
0.03974S2
0.0

0.1,0.5

0.1,0.1

S3
0.00042

0.4,0.5

S3
0.002071

79

隠れマルコフモデルの形式化(1)•マルコフ連鎖（確率過程）– 状態の集合 S = {s0 ,..., sm−1} に値をとる確率過程の状態時系列 X = X ,..., X において
1n

P( X t = a0 ) = P( X t = a0 | X t −1 = a1 ,..., X t −k = ak )と書けるとき、この確率過程をk次マルコフ連鎖と呼ぶ•

マルコフモデル（確率モデル）–

マルコフ連鎖の状態時系列そのものを信号列とみなしたとき、この確率情報源をマルコフモデルと呼ぶ隠れマルコフモデルの形式化(2)•

遷移確率（行列）

aij = P( X t = s j | X t −1 = s j )••時刻0の各状態の確率（初期状態分布）を与える代わりに、時刻0の初期状態 s0 を考える
状態列 x = x1 ,..., xT が観測される確率T −1

p( x) = a0 x1 ∏ a xt xt +1
t =1

隠れマルコフモデルの形式化(3)• M = ( S , Σ, A, B)
–
–
–
–
–
–
–

S = {s0 ,..., sm−1}
状態の集合：
出力記号の集合： Σ = {c1 ,..., cd }A = {aij }状態遷移確率：E = {e( si , ck ) = ei (ck ) = eik }出力確率：
状態遷移は1次マルコフ過程
状態は直接観測できず、出力記号が観測可能
観測記号列 x = x1 ,..., xT に対する状態列 π = π1 ,...,π T
T −1p(π , x) = a0π 1 ∏ e(π t , xt )aπ tπ t +1
t =1

隠れマルコフモデルの形式化(4)– ビタビアルゴリズム（状態列の推定）••

出力記号列と状態列の同時確率の最大化
π * = arg max π P( x, π )ビタビ変数 vk (t )時刻tまでの観測部分列 x(1,t ) = x1 … xtと時刻tまでの状態部分列 x(1,t ) = π 1 …π t の同時確率で
π t = sk である場合の最大確率以下の漸化式が成り立つ

vl (t + 1) = el ( xt +1 ) max k (vk (t )akl )DPマッチングとの類似点•

DPマッチング：–––

与えられた系列A、Bに対する格子点(1, 1)から
(m, n)までの経路の中の、コスト最少のものを効率よく探すためのアルゴリズム
効率化は、各格子点に至る最少経路のコストを記憶しておけば、いちいちすべての経路のコストを計算する必要がないことに注目
DPマッチングでは、マッチングの度合いを計算する関数の選定方法や知識ベースに蓄える系
列集合の選定方法は任意 ⇒ この部分をマ
ルコフ確率の理論に基づかせると「隠れマルコ
フモデル」

84

隠れマルコフモデルの応用（1）•単語/品詞の隠れマルコフ・モデル–

例文： time flies like an arrow.

85

隠れマルコフモデルの応用（2）•単語/品詞の隠れマルコフ・モデル–

5通りの構文解釈が可能な文： time flies like an arrow.
•
•
•
•
•

S[ NP/Time VP[ VP/flies PP[ PREP/like NP[ DET/an N/arrow ] ] ] ]S[ VP/Time NP[ NP/flies PP[ PREP/like NP[ DET/an N/arrow ] ] ] ]S[ NP[ ADJ/Time NP/flies ] VP[ V/like NP[ DET/an N/arrow ] ] ]S[ NP[ NP/Time NP/flies ] VP[ V/like NP[ DET/an N/arrow ] ] ]S[ VP[ V/Time NP/flies ] PP[ PREP/like NP[ DET/an N/arrow ] ] ]86

今日の講義のまとめ‒

HCIの構成原理と構成方法 (2)HCIと機械学習
• CNN
‒
‒

•

SVM
‒

•

Touch & Activate

認識アルゴリズム‒•

OpenPose
DensePose

DPマッチング、隠れマルコフモデル

部分観測マルコフ決定過程‒

Situated Interaction (対話エージェント)

おわり88