言語処理学会 第21回年次大会 発表論文集 (2015年3月)

質問応答による会話的適合フィードバック
加藤 誠 †田中 克己 †山本 光穂 ‡† 京都大学大学院情報学研究科‡ デンソーアイティーラボラトリ†{kato, tanaka}@dl.kuis.kyoto-u.ac.jp‡miyamamoto@d-itlab.co.jp

1

はじめに同提案手法をレストラン検索タスクを用いて評価実験をした結果について報告する．

スマートフォンやタブレットの普及により，音声を入力とし音声により検索結果を返す，音声検索システ
ムの需要が高まっている [7]．その理由として，音声検索は物理的な操作を必要とせず，他の行動をしながらでも可能であるため，モバイル機器を用いた検索方法として適しているからである．
一方で，音声検索にはいくつかの課題が残っている．
第一に，音声クエリはデスクトップ環境で入力されたクエリよりも平均的に短いことから正確にユーザの意図を反映できていない可能性が高い事 [11], 第二に，現在の検索エンジンが備えている，クエリ補完やクエリ推薦などの機能が音声では利用できない事，第三に，モバイル機器の画面サイズの制約や，何らかの別の行動を行いながら検索結果を閲覧する場合が多いことから，検索結果の閲覧が制限される事が挙げられる．これら 3 つの問題が存在するため，音声検索には，短いクエリに対して，物理的な操作 (例えばスクロールやクリック，タッチ等) を必要とせずに，上位数件のうちに適合結果を表示する，という大きな課題の達成が求められている．
そこで本論文はこれらの課題を解決する新しい対話的検索システム，会話的適合フィードバック (CRF)システムを提案する．CRF システムは与えられたクエリに対して質問を生成し，ユーザから得られた回答によって自動的にクエリを修正する．この仕組みによって，ユーザは検索結果や推薦クエリを見ることなく対話的にクエリ修正を行うことができる．CRF はユー
ザは画面を注視したりタッチすることなく，短いクエリを修正することで，より上位に適合した結果を得ることが可能になることから，先に挙げた 3 つの音声検索における問題を解決している
CRF を実現するための主な課題の 1 つとして，与えられたクエリに対して「良い」質問を生成することが挙げられる．質問の質は質問への回答によって行われるクエリ修正の効果によって測ることが可能であり，さらにクエリ修正後の検索結果から得られる利得によって近似することが可能である．言い換えれば，取り組むべき課題は高い利得を持つ可能性を最大化するような質問を発見する事である．
本論文では，質問応答を確率的にモデル化し，質問への回答可能確率，回答確率，検索結果利得の期待値に基づき質問を生成する手法について報告する．また，

2

関連研究

本節では対話システムや対話的情報検索システムの手法を含む関連研究について述べる．最も関係のある研究として，Misu と Kawahara によって提案された，対話システムと情報検索 (IR) システムの統合に関する研究が挙げられる [8]．彼らの対話戦略では，与えられたクエリに対して質問を与えることで明瞭化を行い，得られる検索結果の情報量の増分によって質問を選択する．CRF とは異なり，彼らのモデルにはユーザとシステム間の対話は含まれておらず，ブーリアンモデルによる検索を前提としている．
対話システムに対する最も最近の統計的モデルの 1
つとして部分観測マルコフ決定過程 (POMDP) が挙げられる [12]．MDP とは異なり，POMDP では現在の状態を完全に観測することはできない．代わりに，現在の状態を推定するために，現在の状態に依存する観測値を用いることができる．POMDP が対話戦略の学習に用いられる際には，行動 a がシステムの発話に，状態 s がユーザの状態（もしくは目的）やシステムへの応答意図に，そして，ユーザの曖昧な発話が観測値 o に対応付けられる [12]．
IR ではセッション検索の研究において POMDP が用いられるようになってきている．Jin，Sloan，Wang
は複数の検索結果ページでの検索精度を最大化するために，新しい適合フィードバックの方法を提案している [6]．彼らは文書（質問ではない）へのユーザのフィードバックと利得の期待値をモデル化することで，強化学習に基づき最適なランキング方法の決定を行っている．

3

会話的適合フィードバック

本節では会話的適合フィードバック (CRF) システ
ムを提案する．さらに，CRF における質問応答の確率的モデルも提案する．

― 776 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

上記の確率モデルの主な目的は最も効果的な質問 Qtを選択することであり，すなわち，質問 Qt が与えられたときにユーザが利得 ut を得られる確率をもっとも最大化する Q を選択することである．同利得 ut を最大化するような質問については以下の式で表される:

q Chinese
you like
Q1 Do
spicy foods?

a1

Yes

Q2
User

a2

CRF

3000 JPY

Q3

Q∗t

What isyour budget?

?

図 1: CRF の動作

3.1

システム動作

ユーザは単語集合である初期クエリ q を CRF に入力として与える．初期クエリ q に対して，CRF は質問Q をユーザに与える．質問 Q は質問集合 Q の中から任意のアルゴリズムによって選択される．質問 Q が与えられると，ユーザは回答 a ∈ AQ を返すことができる（AQ は質問 Q の回答候補である）．もしユーザが質問Q に答えられない場合には，別の質問が与えられ，質問 Q に対する回答は空として記録される．ユーザが回答を止めるまで質問応答は繰り返される．計 t 回の質問応答の結果，質問列 Qt = (Q1 , Q2 , . . . , Qt ) が CRFにより生成され，回答列 at = (a1 , a2 , . . . , at ) がユーザによって提供される．回答列 at に対して，CRF は初期クエリを拡張することで新規のクエリ qat = e(q, at )を生成する．ただし，e はクエリ拡張関数であり，初期クエリと回答列を受け取り拡張された初期クエリを出力する．システムはランキング関数 f (qat , d)（d ∈ Dであり D は全文書集合）の降順で文書集合 D をユーザに提示する．CRF の動作を図 1 に示す．
次の小節では質問応答を確率的にモデル化し，何が「良い」質問であるかを明確にする．

3.2

モデル

≃arg max E[Ut |at−1 , Qt ],=arg max P (yt = 1|Qt )

Qt ∈Q

Qt ∈Q

∑

ただし．UT は累積利得．また E[Ut |at−1 , Qt ] は期待累積利得である．この式は直感的に言えば，答えやすく，結果的に利得が高くなりそうな質問が最も効果的であることを示している．また，回答可能確率 P (yt |Qt ) と回答確率 P (at |Qt )，および，期待利得 E[ut |at ] が推定できれば解くことができることを示している．以下の小節ではこれらの確率および期待値を推定する手法について述べる．

3.2.1

回答可能確率の推定

我々はユーザの回答可能性履歴を用いることによって，各個人の回答可能性確率を推定する方法を提案する．この手法の考えは協調フィルタリングに似ており，似たような質問に回答できるユーザは違う似たような質問にも回答できる事を仮定している．
具体的な回答可能確率の導出方法は，まず，アンケート等を通じて集めた質問集合の回答履歴を利用して各クラスターにおける回答可能確率を求める．次に，特定のユーザの質問履歴を利用して，質問がどのクラスタに属するかを推定した上で回答可能確率を推定する．ユー
ザの回答履歴を ht = (Qt , yt ) ( yt = (y1 , . . . , yt )), とした場合，回答可能確率は以下の式で表される:
P (y|Q, ht , µ, θ) =∑P (y|µzQ )P (z|ht , µ, θ),

1. ユーザが初期クエリ q を CRF に与える；
2. 以下のプロセスをユーザが回答を止めるまで繰り返す：(a) ユーザは CRF からの t 番目の質問 Qt に確率 P (yt |Qt ) で回答することができる（yt はQt への回答可能性を表す二値変数）；(b) もし質問 Qt が回答可能（yt = 1）ならば，i. ユーザは質問 Qt に対して確率 P (at |Qt )で回答 at ∈ AQt を行う；
ii. ユーザは初期クエリ q と回答列 at =(a1 , . . . , at ) に対して得られた検索結果
から確率 P (ut |at ) で利得 ut を得られる；(c) もし質問 Qt が回答不可能（yt = 0）ならば，ユーザは利得を得ることができない．
3. 計 T 回の質問応答の後，CRF はユーザに質問するのを止める．

(2)z

ただし，P (z|ht , µ, θ) は，ht におけるユーザがクラスター z に属する確率を示しており，同値はベイズ定理によって以下のように展開する事ができる:
P (z|ht , µ, θ) = P (yt |Qt , z, µ)P (z|θ)/

質問応答はユーザと CRF システム間の確率的なやり取りとしてモデル化することができる：

P (at |Qt )E[ut |at(1)],at ∈AQt∑

P (yt |Qt , z ′ , µ)P (z ′ |θ),(3)z′

ただし，∏t
P (yt |Qt , z, µ) = i=1 P (yi |µzQi ) は，回答可能 yi が与えられた Qi ,z に対して条件付きで独立していると仮定している．なお，式 (2) における確率推定モデルは混合ベルヌーイ分布によるものである．µ と θ については EM アルゴリズムを利用して推定する．

3.2.2

回答確率の推定

回答確率の推定においては，以下の仮定に基づき求める手法を取る:もしユーザにとって適合率が高いドキュメントを予測することができれば，質問に対する回答は適合率が高いドキュメントに関連するものになる．
同仮定に基づき，初期クエリを q ，回答列を at ，質問を Q とした場合，回答 a と回答する確率は以下の式で表される．
∑P (a|q, at , Q) =P (a|Q, d)P (d|qat ),(4)d∈D― 777 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

ただし，D はドキュメント集合，拡張クエリ qat は回
答列 at と初期クエリ q を入力とする拡張クエリ関数
e(q, at ) によって導出する．式 (4) における P (d|q) の導出は確率的言語モデルに基づく順位付きドキュメン
ト検索モデルを利用する [1, 9]．
一方，P (a|Q, d) についてはベイズの定理に基づき0.6

P (d|Q, a)P (a|Q), (5)期待利得の推定

期待利得 E[ut |at ] においては，初期クエリ q と回答
列 at を用い qat を導出した後に，各ドキュメントに対する適合率 P (d|q) を推定することによって導出する手法を取る．なお，適合率の導出は，任意の評価指標を利用することができる。
簡易的な評価指標としては，二値成功度 (BS)@Nを利用する手法が挙げられる．同手法は上位 N 件中に適合するドキュメントが存在した場合は BS = 1とし，それ以外の場合はBS = 0 とする手法であり，∑N
EBS [ut |at ] = r=1 P (dr |qat ) と定義する．ただし drは f (qat , d) によって r 位にランク付けされたドキュメントである．
他の手法としては，クエリ性能予測を利用する方法が挙げられる. 我々は検索結果のランキングスコアーの標準偏差に基づきをクエリ性能の予測を行う手法を利用した [3]:

0.3

0.2

4.1

実験手順

1 http://tabelog.com/

46810させた上で，各セッション毎に得られた検索結果を評価指標を利用して評価した．
評 価 指 標 に つ い て は DCG[4],Qmeasure [10],ERR [2] を 利 用 し た ．ま た ，セッション 系 の 評 価 指 標 と し て nsDCG [5]，お よ び ，Q-measure と ERR をセッション対応させた上で利用した．

4.2

比較手法

NextPage 初期クエリの入力後，システムからの質問を考慮せずひたすら適合するドキュメントが発見されるまで 10 件づつ検索結果を閲覧する手法である．“next page” をクリックするユーザをシミュレートしたモデルであり，ベースラインモデルとする.
QueryRef クエリ修正．ユーザが入力した初期クエリに適合するドキュメント集合から言語モデルに基づき，次のセッションに対するクエリを追加する．ベースラインモデルとする．
HighAns 回答確率が最も高い質問を提示するモデル．我々の提案フレームワークにおけるベースラインモデルである．
CRF 提案するモデル．期待利得の算出方法に二値成功度を利用するモデルを (CRFBS )．クエリ性
能予測を利用したモデルを (CRFQPP ) とする．
Oracle 回答確率，回答可能確率，期待利得の推定において理想値を与えたモデル (各推定のみにおいて理想値を与えた場合をそれぞれ Oracle-y,Oracle-a, Oracle-u とする)．

(6)

提案手法の評価については，レストラン検索タスクを用いて行った．検索タスクで利用したレストランに関するドキュメント集合 D は食べログ 1 から収集した (4695 件). 検索意図に対する初期クエリ q ，質問集合 Q，質問 Q に対する回答可能性，質問 Q への回答
AQ をアンケートに基づき収集した. 件数は検索意図50 件，初期クエリ q は各検索意図に対して平均 89.21件，質問 Q は 50 件，質問 Q に対する回答 AQ は各質
問 Q に対して平均 2.78 件である. 同上のデータを利用し，確率モデルに基づき行動する仮想ユーザを作成した後，同仮想ユーザを通じ CRF を利用し対話検索

2

図 2: 評価結果 (nDCG@10)

ただし，Dx は最上位のランキングスコアに対して¯x%∑ 以上のスコアを持つドキュメント集合であり，f =d∈Dx f (qat , d)/|Dx | である．

実験0

# of Q&Asx4

0.5

0.4と展開した上で，P (a|Q, d) については同様にドキュ
メント検索モデルを利用し推定する手法を取る．またP (a|Q) については，アンケートに基づき収集したデー
タ集合 (4.1 節参照) を利用し最尤法にて推定する手法を取る．

vu∑ ()2u 1
EQPP [ut |at ] = t
f (qat , d) − f¯ ,|Dx | d∈DOracle-yOracle-aOracle-u
Oracle

0.7

a∈AQ

3.2.3

CRFQPP

0.8

nDCG@10

P (a|Q, d) = P (d|Q, a)P (a|Q)/∑CRFBS

NextPage
QueryRef
HighAns5

実験結果

図 2 に nDCG@10 で評価した結果について示す．oracle においては，Oracle-y がもっとも上位の結果を示し，次いで Oracle，Oracle-a， Oracle-u という順位であった．Oracle-y が Oracle を nDCG の結果において上回った理由としては，1) 今回のテストセッ
トにおいて大部分の質問が回答可能であったこと，2)シミュレーションベースの評価は，確率が確定的では― 778 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.

表 1: 評価結果 (nsDCG@10, nsERR@10， nsQ (T =10)). (() 内は平均値の標準誤差)
MethodnsDCG@10

nsERR@10

nsQ

NextPage
QueryRef
HighAns0.308 (0.0272)
0.343 (0.0227)
0.326 (0.0267)

0.420 (0.0369)
0.475 (0.0296)
0.448 (0.0340)

0.395 (0.0306)
0.322 (0.0247)
0.501 (0.0271)

CRFBS
CRFQPP

0.337 (0.0238)
0.362 (0.0235)

0.477 (0.0330)
0.496 (0.0304)

0.511 (0.0274)
0.534 (0.0265)

Oracle-yOracle-aOracle-u
Oracle0.587 (0.0167)
0.496 (0.0191)
0.382 (0.0206)
0.563 (0.0170)

0.749 (0.0190)
0.683 (0.0233)
0.517 (0.0271)
0.746 (0.0199)

0.628 (0.0191)
0.607 (0.0199)
0.611 (0.0198)
0.647 (0.0188)[1] Adam Berger and John Laﬀerty. Information
retrieval as statistical translation. In SIGIR, pp.
222–229, 1999.
[2] Olivier Chapelle, Donald Metlzer, Ya Zhang,and Pierre Grinspan. Expected reciprocal rankfor graded relevance. In CIKM, pp. 621–630,
2009.
[3] Ronan Cummins, Joemon Jose, and Colm
O’Riordan. Improved query performance prediction using standard deviation. In SIGIR, pp.
1089–1090, 2011.

なかったこと，等があげられる．その結果，Oracle においては期待利得が高いが回答可能確率が低い質問を避ける場合においても，Oracle-y においてはより積極的に質問を提示したと考えられる．Oracle 以外の手法においては，CRFQPP が一番良い結果を示した．
また，セッションを考慮した評価指標である nsDCG，nsERR， nsQ (T = 10) を表 1 に示す．一元配置分
散分析による反復評価によると，F (8, 392) = 96.0,
p < 0.01, と η 2 = 0.297 となることから，nsDCG の結果に有意差があることが確認できる．また，我々はテューキーの範囲検定を実施し，その結果 α = 0.05という結果を得た．これゆえ，nsDCG において次の結果に対するペア {Oracle-y ， Oracle-a， Oracle}と {NextPage， QueryRef， HighAns，CRFBS ，CRFQPP ， Oracle-u} に対して有意差を認められた．
これらの結果から，私たちは提案フレームワークがベースラインよりも有意に優れた性能を達成している
事，特に期待利得の推定が我々の提案手法における性能改善に寄与することが確認された．

6

参考文献

おわりに

本論文では，与えられたクエリに対して質問を生成し，その質問への回答を元にクエリを自動的に修正する，CRF という対話的検索システムを提案した．我々は CRF の実現のために最も重要な課題である効果的な質問生成に，質問回答を確率的モデルによって扱う枠組みを構築することで取り組んだ．また，我々は上記の枠組みに従い，質問選択問題を CRF を用いたユーザの期待利得の最大化問題として定式化した．また，我々はシミュレーションによる実験を行い，オラクルデータを用いた提案手法はベースライン手法よりも統計的有意に高い性能を示すことを明らかにした．さらに，推定手法と共に提案手法を用いた場合には，ある程度，高い性能を得られることを示すとともに，CRFの有効性を高めるためには期待利得の推定が最も重要な課題であることを明らかにした．今後の研究課題として，長期に渡る期待利得を考慮する方法の開発，質問の自動生成，一般的な Web 検索への応用を検討している．

[4] Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain-based evaluation of IR techniques.
ACM TOIS, Vol. 20, No. 4, pp. 422–446, 2002.
[5] Kalervo Järvelin, Susan L. Price, Lois M. L.
Delcambre, and Marianne Lykke Nielsen. Discounted cumulated gain based evaluation ofmultiple-query ir sessions. In ECIR, pp. 4–15,2008.
[6] Xiaoran Jin, Marc Sloan, and Jun Wang. Interactive exploratory search for multi page searchresults. In WWW, pp. 655–666, 2013.
[7] Jason Kincaid.
Google:25% of queriesfrom android 2.0 devices use voicesearch.
Retrieved July 18, 2014, fromhttp://techcrunch.com/2010/08/12/googles-hugobarra-25-of-android-queriesare-voice-based/.
[8] Teruhisa Misu and Tatsuya Kawahara. Speechbased information retrieval system with clarification dialogue strategy. In HLT/EMNLP, pp.
1003–1010, 2005.
[9] Jay M Ponte and W Bruce Croft. A language
modeling approach to information retrieval. In
SIGIR, pp. 275–281, 1998.
[10] Tetsuya Sakai. On the reliability of information
retrieval metrics based on graded relevance. Information processing & management, Vol. 43,No. 2, pp. 531–548, 2007.
[11] Johan Schalkwyk, Doug Beeferman, FrançoiseBeaufays, Bill Byrne, Ciprian Chelba, Mike Cohen, Maryam Kamvar, and Brian Strope. “Yourword is my command”: Google search by voice:A case study. In Advances in Speech Recognition, pp. 61–90. Springer, 2010.
[12] Jason D. Williams and Steve Young. Partiallyobservable markov decision processes for spoken
dialog systems. Computer Speech & Language,
2007.

― 779 ―

Copyright(C) 2015 The Association for Natural Language Processing.
All Rights Reserved.