論 文 - 京都大学

ソフトウェアエージェントとその応用論文特集
論 文
キャッシュを用いた漸次的 PDFA 学習と対話型エージェントへの適用
昌之† ∗
岡本
Gradual Probabilistic DFA Learning with Caching for Conversational Agents
Masayuki OKAMOTO†∗
あらまし 本論文の目的は有限状態機械を用いたタスク指向対話モデルを漸次的に構築するための構築コスト
削減手法の提案である．タスク指向の対話エージェント構築においては，対話事例を収集しつつ徐々にエージェ
ントを構築する手法が利用可能である．対話エージェントを構成する対話モデルとして有限状態機械を利用する
場合，状態マージング手法を用いた確率決定性有限オートマトンの学習アルゴリズムが利用可能であるが，これ
らのアルゴリズムでは事例が増えるごとに学習をやり直す必要がある．我々は，マージング履歴をキャッシュす
ることで事例増加時の再計算コストを減らす手法を提案し，合計 110 の観光案内に関する対話事例を用いて同値
性の確認回数と学習後のモデルを評価した．その結果，同値性の変化した箇所だけ再計算する方式により，結果
のモデルの状態数と再計算コストの減少量との間には学習パラメータによるトレードオフが存在するものの，も
とのアルゴリズムと比べてほとんど対話モデルの質を変えることなく同値性の確認回数を合計 33.0%削減した．
また，実際の対話エージェントへ適用することで，対話事例収集のコストを大きく変えないことを確認した．
キーワード 対話モデル，確率決定性有限オートマトン，状態マージング法，漸次的学習，対話型エージェント
般に，対話モデルを学習する前に一度に大量のコーパ
1. ま え が き
スを収集するのはコストがかかる作業であるが，事例
本論文の目的は有限状態機械を用いたタスク指向の
が少ない状態から対話モデルを用いたシステムの推論
対話モデルを漸次的に構築するためのコスト削減手法
を積極的に学習・利用することで収集自体の負荷を下
の提案である．
げることができる．対話事例の収集を効率的に行いな
テキストや音声を用いたタスク指向の対話型エージェ
がらエージェントを構築する手法として，我々はシス
ント，対話システムは数多く作られているが，近年，
テムになりすました人間 (wizard) がユーザと対話す
Web 上の対話型エージェント（例えば，Extempo（注 1）
る Wizard of Oz (WOZ) 法 [2] とシステムによる推論
のような音
を組み合わせることで，対話事例収集と対話モデル学
声対話のための規格が作られるなど，広く対話型エー
習を繰り返しながら対話エージェントを構築する手法
ジェントが利用しやすい環境が作られつつある．
を提案している [9]．このように事例が少しずつ増え学
（注 2）
や Artificial Life
（注 3）
）や，VoiceXML
これらのエージェントにおいては，その対話モデル
習が繰り返される状況では，事例収集のコストを減ら
の構造として有限状態機械 (Finite State Machine :
すとともに，学習にかかる時間を減らすための漸次的
FSM) を用いたものが多く提案されている（ [1]，[10]
な手法が必要とされる．本論文では，収集された事例
など）．これらは基本的に特定の用途に限定されてい
が断続的に増加する状況で，対話事例収集及び対話モ
るため，FSM も作り込みになることがほとんどであ
デル学習にかかるコストを減らすことを試みる．
るが，対話のシナリオが変更される場合や，種々の応
事例からの FSM の学習には，決定性有限状態オー
用に利用可能なシステムを開発するためには，対話事
トマトン (Deterministic Finite-state Automaton :
例から FSM の構造を学習できることが望ましい．一
DFA) の学習アルゴリズムが適用可能である．ここで，
学習データとして対話事例を用いる場合，
（１）正例
†
京都大学大学院情報学研究科社会情報学専攻，京都市
Department of Social Informatics, Kyoto University, Yoshida
Hommachi, Sakyo-ku, Kyoto-shi, 606-8501 Japan
∗
現在，(株) 東芝．
524
（注 1）：http://www.extempo.com/
（注 2）：http://www.artificial-life.com/
（注 3）：http://www.voicexml.org/
電子情報通信学会論文誌 D–I Vol. J86–D–I No. 8 pp. 524–531 2003 年 8 月
論文／キャッシュを用いた漸次的 PDFA 学習と対話型エージェントへの適用
となる学習データは得られるが，負例は得られない，
a[1]
1
a[1]
（２）学習データに誤りが含まれる，
（３）学習データの
[1,0]
0
断続的な増加，の問題が生じ得る．
（１），
（２）だけを考
b[4]
[5,0]
a[2]
4
6
a[2]
[2,2]
[2,0]
2
[4,0]
える場合，重みを含む構造，つまり確率決定性有限状
3
[1,1]
a[1]
b[2]
5 b[1]
7
[1,1]
[2,0]
態オートマトン (Probabilistic Deterministic Finite-
8
[1,1]
state Automaton : PDFA) が用いられる．PDFA を
図 1 PTA の例
Fig. 1 Example of PTA.
学習するアルゴリズムとして，状態マージング法を用
いるサイクリックなオートマトン学習アルゴリズムの
ALERGIA [4] や，ALERGIA をもとに，状態マージ
は，m が入力系列がその状態を通過した回数（これを
ングを行うための判定基準に Kullback-Leibler 距離
c(s) とする）を，n がその状態で入力系列が終了した
を用いることでより良い学習結果を得られる MDI [11]
回数（これを c(s, #) とする）を表す．２重丸はその
が提案されている．
状態が受理状態であることを表す．また，遷移の上の
しかし，これらのアルゴリズムでは（３），つまり
文字 a[l] は，シンボル a が l 回通過したことを示す
断続的に増加する対話事例から対話モデルを構築する
（これを c(s, a) とする）．各状態の番号は，その状態に
場合には，事例の増加に伴ってそのつどすべての計算
至る入力シンボル列の辞書式幅優先の順序（注 4）に従っ
を再び行うことが必要となる．したがって，再計算の
て付与される．状態マージング法による PDFA の学
コストを減らす手法が望まれる．
習では，最初に学習データだけを受理することのでき
本論文では，状態マージング手法を用いたアルゴリ
ズムで学習データが増えたときに再計算が必要となる
る PTA を作り，適当な 2 状態をマージしていくこと
により，徐々に一般的なモデルが構成される．
要件について考察し，状態マージングを行った履歴を
また，二つの PDFA A = (Q, Σ, δ, q0 , γ)，A0 =
キャッシュすることで学習データ増加時の計算コスト
(Q0 , Σ0 , δ 0 , q00 , γ 0 ) に対する Kullback-Leibler 距離 (あ
を減らす漸次的学習アルゴリズム [8] を提案する．ま
た，MDI をもとにした漸次的学習アルゴリズムを用
るいは相対エントロピー) を D(A||A0 ) と表す．ここ
で，文献 [3] によると， D(A||A0 ) は
いて，事例が断続的に増えた場合の計算コストの減少
D(A||A0 )
量を評価するとともに，学習結果の対話モデルの質を
確率的な側面，及び実際の対話エージェントに組み込
まれたモデルとしての側面から評価する．
=
X X
X
cij γ(qi , a) log
qi ∈Q q 0 ∈Q0 a∈Σ∪{#}
γ(qi , a)
γ 0 (qj0 , a)
j
2. 準
備
(1)
確率決定性有限オートマトン (Probabilistic DFA :
と表せる．ここで，cij は A における A の状態 qi 及
PDFA) は５項組 (Q, Σ, δ, q0 , γ) で定義される．ここ
び A0 の状態 qj0 に共通するプレフィックスの集合の A
で，Q は有限の状態の集合を，Σ は有限の入力シンボ
における確率を表す．
ルの集合を，δ は Q × Σ → Q の状態遷移関数を，q0
は初期状態を，γ は Q × (Σ ∪ {#}) → [0, 1] の遷移確
率関数（ある状態からの遷移，あるいはその状態で系
3. PDFA 学習アルゴリズム
本章では，辞書式幅優先の順序による状態マージン
列が終了する確率．# は系列の終了を表すシンボル）
グ法を用いた多項式時間の PDFA 学習アルゴリズム
を表す．
の一般的な手法について述べる．
ここで，遷移確率の要件 [7] から，各状態 q につい
て
P
γ(q, a) = 1 が成り立つ．
a∈Σ∪{#}
3. 1 状態マージング法
ある 2 状態 s1 と s2 をマージすることは，PTA に
PDFA のうち，特に初期状態を根とする樹状に構成
おいてそれぞれの状態を根とする二つの subtree を重
されるオートマトンを Prefix Tree Acceptor (PTA)
ねることに相当する（図 2）．状態のマージングは手
と呼ぶ．例えば，入力として {aa, baa, baa, bba, bbb}
がある場合，PTA は図 1 のようになる．ここで，丸
の中の数字は状態 s の番号を，丸の下の数字 [m, n]
（注 4）：例えば入力シンボルの集合が {λ, a, b} (λ は空シンボル) であ
る場合，λ < a < b < aa < ab < ba < bb < aaa < · · · のような順
序を表す．
525
電子情報通信学会論文誌 ’103/8 Vol. J86–D–I No. 8
S㪈
S㪉
Fig. 2
図 2 2 状態のマージングの直感的な説明
Intuitive expression of merging two states.
input: PDFA A，状態 s1 , s2 (s1 < s2 )
output: マージされた PDFA
begin
c(s1 ) ← c(s1 ) + c(s2 )
c(s1 , a) ← c(s1 , a) + c(s2 , a), ∀a ∈ Σ ∪ {#}
if 各 a ∈ Σ について δ(s1 , a)，δ(s2 , a) が両方存在 then
// subtree の重なる箇所を再帰的にマージ
merge(A, δ(s1 , a), δ(s2 , a))
end if
A ← A − {s2 }
return A
end
図 3 merge 手続き
Fig. 3 Procedure merge.
続き merge(A, s1 , s2 ) によって行う（図 3）．これは，
状態 s1 に状態 s2 を包含させることに相当する．こ
のとき，マージ後の状態のシンボル a による遷移確
input: 正例 I+ , マージングの判定に用いるパラメータ α
output: PDFA
begin
// n は P T A(I+ ) の状態数
// s0 , s1 , · · · , sn−1 は I+ の全てのプレフィクスを
// 辞書式幅優先順序でソートし，順番に入力した時の
// 状態に対応
S ← {s0 , s1 , · · · , sn−1 }
A ← P T A(I+ )
for i = 1 to n − 1
for j = 0 to i − 1
(必要な前処理)
· · · · · ·(A)
if 同値性が確認される then
· · · · · ·(B)
A ← merge(A, sj , si )
break
end if
end for
end for
return A
end
図 4 辞書式幅優先順序を用いたアルゴリズムの一般形
Fig. 4 General form of algorithm by lexicographic
breadth-first order.
∀a ∈ Σ ∪ {#}
compatible(δ(si , a), δ(sj , a), αH ) = true, ∀a ∈ Σ
率は {c(s1 , a) + c(s2 , a)}/{c(s1 ) + c(s2 )} となる．ま
ここで，一方の a による遷移が存在しないなど，次状
た，例えば図 1 において状態 1 と状態 3 をマージし
態が定義されていない場合は，入力系列が 0 回である
た場合の状態 1 から状態 3 へのシンボル a による遷
として計算を行う．このとき，第１式左辺で
移のように，この手法ではループも構成される．
箇所は 0 を仮定して計算を行う．
0
0
となる
また，MDI では， (A) として
3. 2 アルゴリズムの一般形
状態マージングの判定を辞書式幅優先の順序で行う
アルゴリズムの一般形を図 4 に示す．アルゴリズムの
精度は図 4 において，二つの状態をマージするのに必
要な同値性の基準 (B) を変えることにより変わる．必
要であれば，(B) のために必要な前処理 (A) を行う．
ALERGIA では，(A) はなく，(B) の判定条件とし
A0 ← merge(A, sj , si )
を用い，(B) の判定条件として
D(P T A(I+)||A0 ) − D(P T A(I+)||A)
< αM
|A| − |A0 |
(2)
て compatible(si , sj , αH ) を用いる．これは，Hoeffd-
ing 境界 [5] が si ，sj の共通のサフィックスについて
を用いる．ここで，A0 は実際にマージングを行った
成り立つ，つまり 2 状態からのそれぞれのシンボルに
場合に作られる PDFA であり，|A|，|A0 | はそれぞれ
よる遷移確率が近いときに true，つまり同値となる．
A，A0 の 状態数，αM はパラメータである．つまり，
αH はパラメータである．この条件は以下の 2 式で表
マージング後の PDFA がマージング前の PDFA と比
せる．
べてマージされた状態当りの相対エントロピーの増加
量が一定以下の場合に同値であるとみなされる．
¯
¯
¯ c(si , a) c(sj , a) ¯
¯
¯
−
¯ c(si )
c(sj ) ¯
Ã
r
1
2
1
1
p
<
ln
+p
2
526
αH
c(si )
c(sj )
4. 漸次的学習
!
前章で述べたアルゴリズムは，学習データがあらか
,
じめすべて集まっている状態を想定しているため，学
習データが断続的に増える場合，そのつどすべての
論文／キャッシュを用いた漸次的 PDFA 学習と対話型エージェントへの適用
データを再計算する必要がある．
本章では，これまでにマージした状態の組と再計算
の必要な状態を管理することにより，学習データが増
えたときのマージを行うかどうかの判定についての計
算量を減らすことを試みる．
4. 1 変更される可能性のある状態をすべて管理す
る手法
PDFA の学習アルゴリズムを漸次的な学習に拡張す
め学習結果は変わらない．
追加の入力とその初期値としては，前回の学習で
マージした状態の組の集合
M ← {(s01 , s02 ), (s11 , s12 ), · · · , (sm1 , sm2 )}
及び再計算の必要な状態の集合
R ← {sr1 , sr2 , · · · , srm }
るためには，前回のアルゴリズム適用結果と比べて，
がある．ここで，(sk1 , sk2 ) は前回の学習でアルゴリズ
PTA の更新箇所，及び同値性の確認時に計算結果が
ムから直接呼び出されたすべての merge(A, sk1 , sk2 )
変わる可能性のある箇所を管理して，必要な箇所だけ
に対応し，srk は，追加した正例のすべてのプレフィッ
を計算すればよい．
クスを入力としたときの遷移先である各状態である．
ここで，前回マージ可能であった状態が今回はマー
ジできなくなる場合や，その逆の場合のように，ある
状態の同値性に変化が起こったときに，連動して同値
性が変わる可能性のある状態は以下のものである．
（ 1 ） PTA 上で，その状態を根とする subtree に
対応する状態
（ 2 ） PTA 上で，根からその状態までを通過する
すべての状態（その状態から根までの predecessor す
べて）に対応する状態
（ 3 ） これまでその状態にマージされた全ての状態
について，
（１），
（２）を適用したもの
次に，同値性の確認と確認後の処理に関する変更内
容としては，
• 確認する状態の組がどちらも R に含まれない
場合は，前回と同じ結果なので M に含まれていれば
マージし，含まれていなければなにも行わない．
• 少なくとも一つの状態が R に含まれる場合は，
確認を行う．
– 同値の場合はマージを行う．その後，マージし
た二つの状態の effect(s) を計算し，その結果得られ
る状態の集合とマージした状態をすべて R に加える．
– 同値でなく，かつ状態の組が M に含まれる場
上記の範囲を図 5 に示す．また，状態 s の同値性が変
合，つまり再計算の結果マージできなくなった場合は，
わったとき，再計算が必要となる状態の集合を得る手
二つの状態，及び 2 つの状態の effect(s) をすべて R
続きを effect(s) とする．PDFA 学習アルゴリズムを
に加える．
漸次的学習アルゴリズムに変更するための一般的な変
更内容は以下のとおりである．
ただし，MDI を用いた場合，事例を追加したときに
– 同値でなく，かつ状態の組が M に含まれない
場合は，その組については変化がないので何も処理を
行わない．
PTA の初期状態が必ず更新されるため，同値性の判定
つまり，この変更は，再計算の必要な集合内の状態
にも用いられる式 (1) 中の cij も更新される．したがっ
を含む同値性の判定に対して，前回と同値性が変わら
て，M に含まれる，前回同値と判断された状態の組は
ない場合には，前回の結果に従い，前回と同値性が変
事例の追加後にも同値であるとは限らず，式 (2) で示
わった場合，再計算の必要な集合を更新後，今回の判
される判定条件を（今回の PTA を用いた結果ではな
定結果に従うことに相当する．
く）前回の PTA で近似したものとなる．ALERGIA
上記の再計算リストの更新を図 3 のマージ手続き，
の場合は，同値性の確認で PTA の参照は行わないた
図 4 のアルゴリズムに適用したものをそれぞれ図 6，
図 7 に示す．
4. 2 同値性が変更された状態だけを管理する手法
前述のアルゴリズムでは，根に近い状態を含む，前
回と異なるマージングが発生した場合に，多くの状態
について計算が必要になるため，もとのアルゴリズム
と比べて比較の回数がそれほど減少しないと考えられ
Fig. 5
図 5 再計算の必要となる状態の範囲
Range of states which need recomputation
る．ここで，学習データが断続的に増える状況におい
ては，更新が様々な箇所で発生するため，必ずしも結
527
電子情報通信学会論文誌 ’103/8 Vol. J86–D–I No. 8
input: PDFA A，状態 s1 , s2 (s1 < s2 )
//これまでにマージした状態の組の集合
M ← {(s01 , s02 ), (s11 , s12 ), · · · , (sm1 , sm2 )}
//再計算の必要な状態の集合
R ← {sr1 , sr2 , · · · , srm }
output: merged PDFA
begin
c(s1 ) ← c(s1 ) + c(s2 )
c(s1 , a) ← c(s1 , a) + c(s2 , a), ∀a ∈ Σ ∪ {#}
if s2 ∈ R then
// マージされる状態 s2 再計算の必要な集合に入っていた
//ので，s2 を包含する状態 s1 を含める
R ← R ∪ {s1 }
end if
R ← R − {s2 }
(s1 , s2 ) 以外の組 (sk , s2 ) を M から削除
if 各 a ∈ Σ について，δ(s1 , a)，δ(s2 , a) が両方存在 then
// subtree の重なる箇所を再帰的にマージ
merge(A, δ(s1 , a), δ(s2 , a), M, R)
end if
A ← A − {s2 }
return A
end
図 6 再計算集合の更新を含む gradual merge 手続き
Fig. 6 Procedure gradual merge with renewal of recomputation set
果の変わる可能性のある状態をすべて管理しなくても，
事例の増加に従って最終的にほぼ同程度の学習結果が
得られると考えられる．
同値性が変更された状態だけを管理するアルゴリズ
ムの記述は図 7 において (∗) と (∗∗) の 2 行を除いた
ものとなる．
5. 評 価 実 験
input: 正例 I+ (追加分を含む), 同値性確認のパラメータ α
//これまでにマージした状態の組の順序リスト
M ← {(s01 , s02 ), (s11 , s12 ), · · · , (sm1 , sm2 )}
// 再計算の必要な状態の集合
// 追加した正例の全てのプレフィクスを
// 入力としたときの遷移先となる状態
R ← {sr1 , sr2 , · · · , srm }
output: PDFA
begin
// n は P T A(I+ ) の状態数
// s0 , s1 , · · · , sn−1 は I+ の全てのプレフィクスを辞書式
// 幅優先順序でソートし，順番に入力した時の状態に対応
S ← {s0 , s1 , · · · , sn−1 }
A ← P T A(I+ )
for i = 1 to n − 1
for j = 0 to i − 1
if si ∈ R または sj ∈ R then
(必要な前処理)
· · · · · ·(A)
if 同値性が確認される then
· · · · · ·(B)
A ← gradual merge(A, sj , si , M, R)
R ← R ∪ effect(si ) ∪ effect(sj )
· · · · · · (∗)
break
else
if (sj , si ) ∈ M then
M ← M − {(sj , si )}
R ← R ∪ {si , sj } ∪ effect(si ) ∪ effect(sj )
· · · · · · (∗∗)
end if
end if
else if (sj , si ) ∈ M then
A ← merge(A, sj , si ) // 通常のマージ
break
end if
end for
end for
return A
end
図 7 漸次的な辞書式幅優先アルゴリズムの一般形
Fig. 7 The general form of gradual algorithm by lexicographic breadth-first order.
本章では，提案手法の効果を確認するために，対話
例から MDI と MDI を漸次的に拡張したアルゴリズ
ムを用いて対話モデルを学習し，それぞれの結果に対
ジェントが提案した観光スポットを紹介する．交通手
して（１）各アルゴリズムについての同値性の確認回
段や入場料など観光スポットについてユーザが質問す
数の比較，
（２）学習されたモデルの確率的な評価，及
る場合にはそれに答える．このようなやり取りを繰り
び（３）学習されたモデルを実際の対話エージェント
返した後，ユーザからの要求がなくなれば案内を終了
に適用した場合の評価，を行った．
するという比較的単純な対話が行われる．この対話ロ
評価用のデータには京都の観光案内に関する対話
データを用いた．このデータは，WOZ 法を用いて京
グに用いた発話タグの種類を表 1 に示す．ここでは，
得られた対話データのうち，100 対話（エージェント
都市内の大学生とインタフェースエージェントが対話
発話 2198 発話，ユーザ発話 799 発話）を学習データ
したログのうち，案内に関する発話に発話の意味を発
として，PDFA 学習アルゴリズム，effect(s) を含む必
話タグとして付与したものである．発話タグを入力シ
要な再計算すべてを行う漸次的学習アルゴリズム（こ
ンボルとして PDFA を構成した場合，その学習結果
れをアルゴリズム (a) とする），及び effect(s) を含ま
は対話システムで利用可能な対話モデルとなる．この
ず同値性の変更箇所だけを再計算する漸次的学習アル
タスクでは，エージェントは最初に自己紹介を行い，
ゴリズム（これをアルゴリズム (b) とする）の 3 種類
その後ユーザが要求した観光スポット，あるいはエー
について，学習時における状態マージングの判定回数
528
論文／キャッシュを用いた漸次的 PDFA 学習と対話型エージェントへの適用
表 1 対話例に用いた発話タグ
Utterance tags for example dialogues.
ユーザの発話タグ
挨拶
相槌
観光スポットの要求
観光スポット紹介の拒否
観光スポットへの質問
エージェントの発話タグ
紹介開始の挨拶
紹介終了の挨拶
自己紹介
観光スポットの説明
観光スポットの提案
観光スポット紹介不可
観光スポットへの質問の回答
他の観光スポットへの誘導
紹介終了への誘導
8000
MDI
(a)
(b)
7000
ห୯ᕈ䈱್ቯ࿁ᢙ
Table 1
6000
5000
4000
3000
2000
1000
0
0
20
40
60
80
ቇ⠌䈚䈢ኻ⹤ᢙ
(1) Count for each learning process.
100
と，学習結果となる対話モデルの質の比較とを行った．
評価対象のアルゴリズムには，MDI を用い，学習
のパラメータには αM = 0.03 を用いた．これは，学
習データをすべて用いたときに，学習結果がほぼ一定
になるまでの経過を確認できる値となっている．また，
ห୯ᕈ䈱್ቯ࿁ᢙ䋨⚥⸘䋩
300000
250000
200000
150000
100000
50000
0
WOZ 法によって収集されるデータは人間の確認を通
0
20
40
60
ቇ⠌䈚䈢ኻ⹤ᢙ
じて対話の質がある程度そろっているため，100 対話
(2) Total.
でも評価可能な分量となっている．
5. 1 同値性の確認回数
図 8 同値性の確認回数の比較
Comparison of the count of compatibility
checks.
Fig. 8
学習中の，同値性の確認回数の比較を図 8 に示す．
いことがわかる．これは，PTA で根に近い場所にあ
る状態についてマージを行った場合，ほとんどすべて
の状態が effect(s) に含まれてしまうため，結果とし
てそのまま計算を行う場合と変わらないからである．
それに対し，アルゴリズム (b) では，平均で 21.3%，
累計で MDI より 33.0%少ない確認回数となった．
ቇ⠌ᓟ䈱ኻ⹤䊝䊂䊦䈱⁁ᘒᢙ
また，学習結果の状態数の推移を図 9 に示す．図 8 よ
り，アルゴリズム (a) によるコスト削減の効果は小さ
140
MDI
(a)
(b)
120
100
80
60
40
20
0
0
本評価において 対 話 モ デル 学 習 に かか る 実 際の
CPU 時間は，CPU が Athron XP 1800+，メモリが
512MByte，OS が Windows 2000 Professional とい
80
MDI
(a)
(b)
100
Fig. 9
20
40
60
ቇ⠌䈚䈢ኻ⹤ᢙ
80
100
図 9 状態数の比較
Comparison of the number of states.
う環境の Java プログラムにおいて，各回の学習に要
する時間はもとの MDI アルゴリズムで最大 66.8 秒と
ム (b) の効果は低くなる．言い換えると，学習結果の
なった．同じ環境でアルゴリズム (b) を用いた場合，
状態数と再計算コストの減少量はパラメータ αM に
各回の学習において平均 21.6%の計算時間を削減して
よるトレードオフの関係にある．例えば，αM = 0.1
おり，同値性確認の計算の削減量を損なわない結果で
と大きくすると，(b) による同値性の確認回数の減少
あるといえる．
量は 11.1%となり，逆に αM = 0.01 と小さくすると，
図 9 と合わせると，学習結果の状態数が多い場合に
は，全状態における再計算の必要な状態の割合が少な
くなるため (b) による再計算の減少量が大きくなるの
に対し，学習結果の状態数が少ない場合には学習の初
期の段階でほとんどの状態がマージされ，再計算の必
要な状態の割合が大きくなる．その結果，アルゴリズ
減少量は 57.0%となる．
5. 2 パープレキシティ
対話モデルの確率的な比較にはテストセットパープ
レキシティを用いた．
PDFA に対して n 個の入力系列 S = {s1 , · · · , sn }
（各 sk は mk 個のシンボル列 xk1 · · · xkmk からなる）
529
電子情報通信学会論文誌 ’103/8 Vol. J86–D–I No. 8
が与えられたとき，入力系列中のシンボル当たりの対
を行った．このシステムは，ユーザ用のクライアント，
数ゆう度は
wizard 用のクライアント，及び推論エンジンからな
る．システム全体は次のように動作する．
n mi
1 XX
log P (xij |qji )
||S||
（ 1 ） ユーザが発話を入力すると，システムは対話
例から，現在の状態から遷移可能な発話タグをもつ
i=1 j=1
と表される．ここで，P (xij |qji ) は状態 qji において系
列 si 中の i 番目のシンボル
xij
が入力される確率（重
み）である．また，||S|| は全系列に含まれる入力シン
ボルの数である．それぞれの i に対して，状態 q1i は
初期状態を表す．
このとき，PDFA のパープレキシティは P P = 2LL
と表される．ただし，P (xij |qji ) として，PDFA の遷
移確率
δ(qji , xij )
だけを用いた場合，受理できない遷
移が生じた場合にパープレキシティが測定できないの
で，学習データにおけるシンボルの単純な出現確率
(unigram) を併用した値を用いる．つまり，全入力に
対するシンボル x の出現確率を P (x) とすると，パラ
メータ β (0 <
=β<
= 1) を用いて
β = 0.5 を用いた．
学習データとは別の 10 対話をテストデータとして
用い，もとの MDI アルゴリズムと，2 種類の漸次的
アルゴリズムについてそれぞれパープレキシティを計
算した結果を図 10 に示す．図 10 より，もとの MDI
の学習において再計算箇所が大きく変わる場合には，
アルゴリズム (b) の再計算がすべて更新されないため
差が現れるが，それ以外では大きな差は見られない．
5. 3 対話型エージェントへの適用
また，我々は学習された対話モデルを実際に WOZ
法による対話エージェント [9] に適用した場合の比較
30
MDI
(a)
(b)
25
䊌䊷䊒䊧䉨䉲䊁䉞
ワードベクトルの内積を用いて類似度を計算し，スコ
アの高い数発話が wizard に応答候補として渡される．
（ 2 ） wizard が候補から一つを選ぶと，その発話と
発話タグが用いられる．もし適切な候補がない場合に
は，wizard はあらかじめ用意された発話の一覧から選
択，あるいは自分で発話を入力し，発話タグを付与す
る．最終的に，発話タグを用いて状態遷移が行われる．
（ 3 ） いずれの場合も，wizard 用のクライアントか
ら送られる発話はエージェントによる応答としてユー
ザに伝わる．
我々はこのシステムを用いて，もとの MDI で学習
ルとを比較した．図 11 はテストデータとしてそれぞ
と表される値を用いる．ここでは，文献 [11] と同様に
20
15
10
5
れ同じ 5 対話の組（エージェント発話 114 発話，ユー
ザ発話 79 発話）を入力した場合の，ユーザの入力発
話に対する応答に wizard が介入した割合を示す．横
軸は学習した対話数（1，20，60，100 対話）を表し，
縦軸はシステムの推論結果を wizard が修正した割合
を表す．図 11 では，もとの MDI とアルゴリズム (b)
について，それぞれシステムが一つだけ候補を推論す
る場合と，二つの候補のうちどちらかが正しければ良
いとする場合の合計 4 通りのグラフが描かれている．
図 11 より，アルゴリズム (b) を用いた場合の wizard
の介入割合はもとの MDI と比べて，ほぼ同等の割合
となっている．つまり学習された対話モデルの質はほ
0.6
20
40
60
ቇ⠌䈚䈢ኻ⹤ᢙ
80
㪤㪛㪠㩷㪈⇟⋡䈱୥⵬䈱䉂
㪤㪛㪠㩷㪉⇟⋡䈱୥⵬䉁䈪⸵ኈ
㩿㪹㪀㩷㪈⇟⋡䈱୥⵬䈱䉂
㩿㪹㪀㩷㪉⇟⋡䈱୥⵬䉁䈪⸵ኈ
0.5
0.4
0.3
0.2
0.1
0
0
図 10 パープレキシティの比較
Fig. 10 Comparison of perplexities.
530
らなる組を見つける．候補となる組に対して，キー
した対話モデルとアルゴリズム (b) を用いた対話モデ
P (xij |qji ) = βδ(qji , xij ) + (1 − β)P (xij )
0
ユーザ発話とその発話に対するエージェントの応答か
䊡䊷䉱⊒⹤䈻䈱ᔕ╵䈮㑐䈜䉎
㩷㩷㩷㩷㩷㩷㩷㩷㩷㫎㫀㫑㪸㫉㪻䈱੺౉ഀว
LL = −
100
Fig. 11
0
20
40
60
ቇ⠌䈚䈢ኻ⹤ᢙ
80
100
図 11 実際の対話例を用いた比較
Comparison with actual example dialogues.
論文／キャッシュを用いた漸次的 PDFA 学習と対話型エージェントへの適用
とんど変わらない．個別の対話を見た場合も，最大で
けて行われました．対話データには新エネルギー・産
6.3%結果の悪くなる事例があったが，これは対話事例
業技術総合開発機構「シニア支援システムの開発」プ
一つにつき 1 発話分に相当し，人間にとっての収集コ
ロジェクトにおいて収集された対話ログを用いました．
ストとしてはほとんど変わらないものである．
全体的な傾向としては，候補を一つしか推論しない
場合には 100 対話学習した場合で推論結果はほぼ一定
文
[1]
for a speech-to-speech translation system,” Proc.
EACL-95, pp.188–193, 1995.
比較的単純なものであるため典型的な対話の流れは学
[2]
no.1, pp.81–99, 1991.
[3]
R. Carrasco, “Accurate computation of the relative entropy between stochastic regular grammars,”
義的に利用される場合に適切な応答を絞り込めない場
Theoretical Informatics and Applications, vol.31,
合が増えることが挙げられる．二つまで候補を認める
場合には更に結果が良くなり，wizard の介入割合が
N.M. Fraser and G.N. Gilbert, “Simulating speech
systems,” Computer Speech and Language, vol.5,
事例を追加することによる特徴としては，相槌や質
問の言い回しへ対処能力が上がる反面，同じ単語が多
J. Alexandersson, E. Maier, and N. Reithinger, “A robust and efficient three-layered dialogue component
となっている．これは，今回の評価で用いたタスクは
習されていることを示している．
献
pp.437–444, 1997.
[4]
R.C. Carrasco and J. Oncina, “Learning stochas-
17.9%程度まで下がっているが，これは話題の扱いや
tic regular grammars by means of a state merg-
キーワード処理の改善により，対話型エージェントの
ing method,” in Grammatical Inference and Applications, LNAI 862, ed. R.C. Carrasco and J. Oncina,
質が向上する余地があることを示唆している．
前節の結果と合わせると，アルゴリズム (a) ではそ
pp.139–152, Springer-Verlag, 1994.
[5]
bounded random variables,” J. American Statistical
れほど効果がないのに対し，アルゴリズム (b) では学
習結果の質を下げずに判定回数を減らすことに貢献し
ているといえる．
6. む す び
本論文では，対話事例収集と対話モデル学習の繰り
Association, vol.58, pp.13–30, 1963.
[6]
T. Ishida, “Digital city kyoto,” Commun. ACM,
[7]
D. Jubhrafsky and J.H. Martin, Speech and Lan-
[8]
M. Okamoto, “Incremental PDFA learning for con-
vol.45, no.7, pp.76–81, 2002.
guage Processing, Prentice-Hall, 2000.
versational agents,” Proc. IEEE Int. Workshop on
返しによるタスク指向対話エージェントの構築におけ
る対話モデル学習のコストを減らすために，マージン
Knowledge Media Networking, pp.161–166, 2002.
[9]
pp.293–300, 2002.
[10]
後のモデルを評価した．観光案内に関する対話事例を
ドオフが存在するものの，同値性の変化した状態だ
けキャッシュする方式を用いることで対話モデルの質
をほとんど変えることなく同値性の確認回数を合計
A. Stent, J. Dowding, J.M. Gawron, E.O. Bratt and
R. Moore, “The CommandTalk spoken dialogue system,” Proc. ACL-99, pp.183–190, 1999.
用いた評価より，結果のモデルの状態数と再計算コス
トの減少量との間には学習パラメータによるトレー
岡本昌之, 山中信敏, “Wizard of Oz 法を用いた対話型
Web エージェントの構築,” 人工知能誌, vol.17, no.3,
グ履歴をキャッシュすることで事例増加時の再計算コ
ストを減らす手法を提案し，同値性の確認回数と学習
W. Hoeffding, “Probability inequalities for sums of
[11]
F. Thollard, P. Dupont and C. de la Higuera, “Probabilistic DFA inference using Kullback-Leibler divergence and minimality,” Proc. ICML-2000, pp.975–
982, 2000.
（平成 14 年 9 月 2 日受付，15 年 1 月 14 日再受付）
33.0%削減した．また，実際の対話エージェントへ適
用し，対話事例収集のコストを大きく変えないことを
確認した．今後は，提案手法を用いて実際にディジタ
ルシティ [6] で利用可能な対話型エージェントを構築
する予定である．
謝辞
岡本
昌之
平 10 京大・工・情報工学卒．平 11 同大
本研究を進めるにあたり，数々の有益な助言
大学院情報学研究科社会情報学専攻修士課
を頂いた京都大学大学院情報学研究科社会情報学専攻
程了，平 15 同大学院博士後期課程了．同
の石田亨教授に感謝します．また，本研究は科学技術
振興事業団戦略的基礎研究推進事業「デジタルシティ
のユニバーサルデザイン」プロジェクトから援助を受
年，
（株）東芝に入社．博士（情報）．対話
型エージェント，機械学習，コミュニケー
ション支援システムに興味を持つ．情報処
理学会，人工知能学会，ACM 各会員．
531