JP2000305932A - 関連語提示を伴う文書検索方法と文書検索装置ならびにプログラムを記録した記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 有効にユーザの検索支援を行いながら、かつ
対話回数の増加に伴うユーザの負担をできる限り少なく
することが可能になる文書検索方法と文書検索装置を提
供する。 【解決手段】 文書検索装置１０は、検索木作成部１０
０と、関連語・検索文書提示候補決定部２００とを備
え、検索木作成部１００は、キーワードが与えられると
ユーザの評価に多項分布を仮定した検索木を出力し、関
連語・検索文書提示候補決定部２００は、検索木が与え
られるとユーザの検索結果の評価をべイズ基準のもとで
最大化するような関連語および検索文書の提示の仕方を
選定してキーワードに対する最適な関連語または検索文
書を出力し、出力した関連語または検索文書に対するユ
ーザの評価が入力されると、ユーザが満足あるいは満足
せずに検索を終了するまで、繰り返しその評価を踏まえ
た最適な関連語または検索文書を出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、関連語提示を伴う
文書検索方法と文書検索装置とに関し、特に文書検索シ
ステムが提示する関連語および検索文書に対するユーザ
の評価に多項分布を仮定したもとで、ユーザが検索結果
に満足して検索を終了した場合に生ずる正の収益からユ
ーザが検索結果に満足せずに検索を終了した場合に生ず
る負の収益を差し引いた残りの収益をべイズ基準のもと
で最大化するような関連語および検索文書の提示の仕方
を出力する関連語提示を伴う文書検索方法に関する。

【０００２】

【従来の技術】近年、パソコン等の普及に伴い文書デー
タベースにおける文書検索やＷｅｂのサーチエンジン
等，様々な文書検索方法が開発されている。しかし、一
般のユーザにとって自分の欲しい文書を示す的確なキー
ワードを指定することは容易ではない。そこで、従来か
らユーザの指定したキーワードに対して関連語を提示す
ることによって、ユーザの検索支援を行うような方法が
開発されてきた。従来方法には、検索対象の文書データ
ベースの統計情報を用いて各単語とユーザによるキーワ
ードの関連度を調べ、関連度の高い単語を関連語として
提示する方法（井上等、“追加検索語候補提示に関する
一考察”、情報処理学会第５５回全国大会、３−７６
（１９９７）。）や、名詞が人手によって意味的に分類
されたシソーラスを用いて、シソーラス上でキーワード
に近い単語を関連語として提示する方法（太田等、“Ｅ
ＤＲ電子化辞書を用いたクエリー拡張による検索支援”
言語処理学会第３回年次大会発表論文集、ｐｐ．３７３
−３７６（１９９７）。）などがある。

【０００３】ここでは、上記従来方法の内、前者の文書
データベースの統計情報を用いる方法の概要を従来方法
の概要として以下にまとめる。図７にその動作原理を示
す。ユーザによってキーワードが入力されると、キーワ
ードと文書データベース中の各単語との関連度を算出す
る（ステップ９０）。次に、関連度の高い上位Ｎ単語を
関連語に決定し（ステップ９２）、最後に関連語を出力
する。

【０００４】なお、キーワードｋｅｙｗｏｒｄと単語ｗ
の関連度Ｉ（Ｋｅｙｗｏｒｄ，ｗ）は次式で与えられ
る。

【０００５】

【数１】 但し，ｐ（ｋｅｙｗｏｒｄ）、ｐ（ｗ）はぞれぞれｋｅ
ｙｗｏｒｄ、ｗの生起確率、Ｐｄ（ｋｅｙｗｏｒｄ，
ｗ）は幅がｄ語の窓の中におけるｋｅｙｗｏｒｄ、ｗの
同時生起確率を示し、対数の底は２である。

【０００６】

【発明が解決しようとする課題】しかし、従来方法に関
してはいくつかの問題点が挙げられる。第１に、従来方
法では単にユーザーの提示したキーワードと関連度の高
い単語、または意味的に近い単語が関連語として提示さ
れているが、これでは必ずしもユーザの検索支援につな
がるとは限らない。つまり、「ユーザの欲しい文書がユ
ーザの入力したキーワードと関連度の高い単語、または
意味的に近い単語を合んでいる」という仮定が成立しな
い場合には有効ではない。

【０００７】第２に、従来方法ではユーザの負荷が考慮
されていない。仮に上記「ユーザの欲しい文書がユーザ
の入力したキーワードと関連度の高い単語、または意味
的に近い単語を含んでいる」という仮定が成立している
場合でも、単に関連度の高い、または意味的に近い単語
を関連語として提示しているだけでは、ユーザの欲しい
文書に到達するまでの文書検索システムとユーザとの対
話回数は少なくならない。

【０００８】本発明の目的は、上記問題点を踏まえた上
で、有効にユーザの検索支援を行いながら、かつ対話回
数の増加に伴うユーザの負担をできる限り少なくするこ
とが可能になる文書検索方法を提供することである。

【０００９】

【課題を解決するための手段】本発明の関連語提示を伴
う文書検索方法は、文書データベースにおける関連語提
示を伴う文書検索方法であって、ユーザからキーワード
が入力されると、そのキーワードに対する関連語および
検索文書の提示の仕方を全列挙した検索木を作成するス
テップと、その検索木を解析してユーザが満足あるいは
満足しないことによって生ずる正または負の収益から成
る収益をべイズ基準のもとで最大化する関連語および検
索文書の提示の仕方を選定するステップと、選定された
関連語および検索文書の提示の仕方に従って、ユーザか
ら入力されたキーワードや、さらに既に提示された関連
語や検索文書に対してユーザが入力した評価が存在する
場合にはその評価に対応して、最適な関連語および検索
文書のいずれかを決定するステップと、決定した関連語
および検索文書のいずれかをユーザに提示するステップ
と、提示された関連語および検索文書に対するユーザの
評価を入力するステップと、ユーザが満足あるいは満足
せずに検索を終了するまで、繰り返し、その評価に対応
して最適な関連語および検索文書のいずれかを決定して
ユーザに提示するステップと、を有する。

【００１０】キーワードに対する関連語および検索文書
の提示の仕方を全列挙した検索木を作成するステップ
は、キーワードが入力されると、そのキーワードによっ
て定まる初期状態をルートとし、可能な全ての系列を枝
でつながるノードと葉として持つような検索木を作成す
るステップと、各ノードについて、遷移確率分布を支配
する未知連続パラメータの事前確率密度関数を示すべー
タ分布のパラメータを用いて事後分布を算出して、検索
木を完成するステップと、最適な関連語および検索文書
のいずれかを決定するステップは、完成した検索木か
ら、ユーザが入力したキーワードに基づいて、過去ユー
ザに提示した関連語および検索文書に対するユーザの評
価に多項分布を仮定したもとで、ユーザが検索結果に満
足して検索を終了した場合に生ずる正の収益からユーザ
が検索結果に満足せずに検索を終了した場合に生ずる負
の収益を差し引いた残りの収益をべイズ基準のもとで最
大化するような関連語および検索文書の最適な提示の仕
方を選定し、既に提示された関連語や検索文書に対して
ユーザが入力した評価が存在する場合にはその評価に対
応した最適な提示の仕方を選定するステップと、選定さ
れた最適な提示の仕方に従って関連語および検索文書の
いずれかの提示候補を決定するステップと、を有するこ
とが好ましい。

【００１１】ユーザが検索結果に満足して検索を終了し
た場合に生ずる正の収益は、ユーザとの対話回数の増加
に伴って正の収益の絶対値が減少し、ユーザが検索結果
に満足せずに検索を終了した場合に生ずる負の収益は、
ユーザとの対話回数の増加に伴って負の収益の絶対値が
増大してもよい。

【００１２】本発明の関連語提示を伴う文書検索装置
は、文書データベースにおける関連語提示を伴う文書検
索装置であって、文書検索装置は、キーワードが与えら
れると検索木を出力する検索木作成部と、最適な関連語
および検索文書のいずれかを出力する関連語・検索文書
提示候補決定部とを備え、関連語・検索文書提示候補決
定部は、検索木が与えられると最適な関連語および検索
文書の提示の仕方を選定してキーワードに対する最適な
関連語および検索文書のいずれかを出力し、出力した関
連語および検索文書のいずれかに対するユーザの評価が
入力されると、ユーザが満足あるいは満足せずに検索を
終了するまで、繰り返しその評価を踏まえた最適な関連
語および検索文書のいずれかを出力する。

【００１３】検索木作成部は、検索木を作成する検索木
展開器と、べータ分布のパラメータを用いて事後分布を
算出する事後分布算出器と、べータ分布のパラメータを
格納するベータ分布パラメータテーブルとを備え、検索
木展開器は、キーワードが入力されると、そのキーワー
ドによって定まる初期状態をルートとし、可能な全ての
系列を枝でつながるノードと葉として持つような検索木
を作成し、事後分布算出器は、各ノードについて、遷移
確率分布を支配する連続パラメータの事前確率密度関数
を示すべータ分布のパラメータを用いて事後分布を算出
して検索木展開器に検索木を完成させ、ベータ分布パラ
メータテーブルは、連続パラメータの事前確率密度関数
を示すべータ分布のパラメータを格納し、関連語・検索
文書提示候補決定部は、関連語および検索文書の最適な
提示の仕方を選定する検索木解析器と、関連語および検
索文書の最適な提示の仕方を格納する関連語・検索文書
提示候補テーブルと、関連語および検索文書の最適な提
示の仕方から、提示する関連語および検索文書のいずれ
かを決定してユーザに提示する関連語・検索文書提示候
補決定器とを備え、検索木解析器は、完成した検索木か
ら、ベイズ期待効用関数を最大化するような関連語およ
び検索文書の最適な提示の仕方を選定し、既に提示され
た関連語や検索文書に対してユーザから入力した評価が
存在する場合にはその評価に対応して最適な提示の仕方
を選定し、関連語・検索文書提示候補テーブルは、関連
語および検索文書と関連語および検索文書の最適な提示
の仕方を格納し、関連語・検索文書提示候補決定器は、
関連語・検索文書提示候補テーブルに格納された関連語
および検索文書の最適な提示の仕方から、提示する関連
語および検索文書のいずれかを決定してユーザに提示す
ることを、ユーザが満足あるいは満足せずに検索を終了
するまで繰り返すことが好ましい。

【００１４】記録媒体を備え、各制御部の動作は、記録
媒体に記録された関連語提示を伴う文書検索プログラム
により制御できてもよい。

【００１５】本発明のプログラムを記録した記録媒体
は、ユーザから入力されたキーワードに基づき、関連語
および検索文書の最適な提示の仕方を選定し、ユーザか
ら入力した評価を参照して関連語および検索文書を検索
して出力するための制御プログラムを記録する。

【００１６】文書検索システムが提示する関連語および
検索文書に対するユーザの評価に多項分布を仮定し、ユ
ーザが検索結果に満足して検索を終了した場合に生ずる
対話回数の増加に伴って減少する正の収益、およびユー
ザが検索結果に満足せずに検索を終了した場合に生ずる
対話回数の増加に伴って増大する負の収益を導入し、正
の収益から負の収益を差し引いた残りを収益として定義
し、その収益をべイズ基準（繁桝、“ベイズ統計入
門”、東京大学出版会（１９８５）。）のもとで最大化
するような関連語および検索文書の提示の仕方を出力す
る。

【００１７】このような構成とすることによって、本発
明の関連語提示を伴う文書検索方法は、第１に、ユーザ
が満足して検索を終了した場合に生ずる正の収益からユ
ーザが満足せずに検索を終了した場合に生ずる負の収益
を差し引いた残りの収益をべイズ基準のもとで最大化す
る関連語および検索文書を提示するので、単に関連度の
高いまたは意味的に近い関連語を提示する従来方法とは
異なり、有効にユーザの検索支援を行うことができる。

【００１８】第２に、検索が長引いた場合、すなわちユ
ーザと文書検索システムの対話回数の増加に伴い、ユー
ザが満足した場合であれば正の収益の絶対値が減少し、
ユーザが満足しなかった場合であれば負の収益の絶対値
が増大するので、収益をべイズ基準のもとで最大化する
ことにより対話回数の増加に伴うユーザの負担をできる
限り少なくすることができる。

【００１９】

【発明の実施の形態】図１は本発明の関連語提示を伴う
文書検索装置を説明するための原理構成図であり、図２
は本発明の関連語提示を伴う文書検索方法の原理を説明
するためのフローチャートである。

【００２０】本発明の関連語提示を伴う文書検索方法
は、キーワードを入力データとして与えられると、関連
語および検索文書の全ての提示の仕方の中から、ユーザ
が満足あるいは満足しないことによって生ずる正および
負の収益から成る収益をべイズ基準のもとで最大化する
関連語および検索文書の提示の仕方を選定する方法であ
る。

【００２１】本発明の関連語提示を伴う文書検索装置
は、検索木作成部１００と関連語・検索文書提示候補決
定部２００とを備える。

【００２２】検索木作成部１００は、キーワードが与え
られると検索木を出力し、関連語・検索文書提示候補決
定部２００は、検索木が与えられると最適な関連語およ
び検索文書の提示の仕方を選定してキーワードに対する
最適な関連語および検索文書のいずれかを出力し、以後
ユーザが満足あるいは満足せずに検索を終了するまで、
出力した関連語および検索文書のいずれかに対するユー
ザの評価が入力されると、その評価を踏まえた最適な関
連語および検索文書のいずれかを出力することを繰り返
す。

【００２３】ここで、検索木は、関連語および検索文書
の提示の仕方を全列挙しており、具体的にはキーワード
に対応するルートをノードの始点とし、１本の枝と複数
の枝の分岐点であるノードが階層的に配置され、枝の最
終点を葉とする木の構成となっており、ノードはどのよ
うなキーワードが指定されたか、それまでにどのような
関連語や検索文書が提示され、どのように評価されたな
どの状態を示し、枝は関連語の提示または検索文書の提
示などの選択された行動を示す。ルートは初期状態、即
ちキーワードのみ指定された状態を示す。ルートでは、
全ての関連語の提示（要はまだ提示されていない単語の
全組合わせ）および全ての検索文書の提示（要はまだ提
示されていない文書の全組合わせ）の数の行動を全て考
慮する。即ちそれぞれの行動に対して、ユーザの評価の
全組合わせを列挙して深さ１のノードを作る。検索木に
対してこれを繰り返すことによって、ルートから全ての
葉に至る全ての提示の仕方、および全てのユーザの評価
の組み合わせが列挙される。

【００２４】図２のフローチャートを参照して、本発明
の原理を説明する。本発明の関連語提示を伴う文書検索
方法は、ユーザがキーワードを入力するステップ１０
と、関連語および検索文書の提示の仕方を全列挙した検
索木を作成するステップ２０と、検索木を解析してユー
ザが満足あるいは満足しないことによって生ずる正また
は負の収益から成る収益をべイズ基準のもとで最大化す
る関連語および検索文書の提示の仕方を選定するステッ
プ３０と、ユーザの入力したキーワードや、ステップ５
０によってユーザに提示された関連語や検索文書に対し
てステップ６０でユーザが入力する評価に対応して最適
な関連語または検索文書を決定するステップ４０と、関
連語または検索文書を提示するステップ５０と、提示さ
れた関連語または検索文書に対する評価をユーザが入力
するステップ６０とからなる。

【００２５】図３は本発明による関連語提示を伴う文書
検索装置の第１の実施の形態の構成図である。同図に示
すごとく、本発明の関連語提示を伴う文書検索装置は、
検索木作成部１００と、関連語・検索文書提示候補決定
部２００とからなる。検索木作成部１００は、検索木展
開器１１０と、事後分布算出器１２０と、ベータ分布パ
ラメータテーブル１３０とからなる。関連語・検索文書
提示候補決定部２００は、検索木解析器２１０と、関連
語・検索文書提示候補テーブル２２０と、関連語・検索
文書提示候補決定器２３０とからなる。

【００２６】各部の説明に入る前に、ユーザと文書検索
システムとのやりとりの概要説明、およびいくつかの定
義を行う。なお、本発明では、関連語を伴う文書検索を
マルコフ決定過程（森村等、“マルコフ解析”、日科技
連（１９７９）。）を用いて定式化している。

【００２７】ユーザと文書検索システムのやりとりの概
要説明は以下の通りである。 １）ユーザがＭ_l 個のキーワードを指定することによ
り、初期状態（０時点の状態）ｘ₀ が定まる。ｘ₀ ∈
Ｓ．Ｓは状態の全集合。 ２）文書検索システムは選択されたＭ₂ 個の関連語また
はＭ₃ 個の検索文書を提示する。これは行動ａ_i の選択
に相当する。 ３）ユーザは各関連語または各検索文書に対して、受理
か拒否を答える。あるいは、検索結果に満足して検索を
終了するか、不満を抱いて検索を終了する。（時点が１
進む。） ４）Ｍ₀ 時点は、このシステムの許しているユーザとの
やり取りの反復回数の最大値であり、Ｍ₀ 時点に至る
か、ユーザが検索結果に満足して検索を終了するか、不
満を抱いて検索を終了するまで上記２）と３）を繰り返
す（ユーザは遅くともＭ₀ −１時点では検索結果に対し
て満足か不満足の判定を下す。）。ここでＭ ₀ は、一度
の検索のオーダーに対してこのシステムの許しているユ
ーザとのやり取りの反復回数の最大値である。

【００２８】ここで、以下のような定義を行う。 １）ＫＥＹ：ユーザがキーワードとして指定する可能性
のある単語の集合。 ２）ＤＢ：文書データベース中の各文書に含まれる単語
の集合。ＤＢ⊆ＫＥＹ。 ３）ｗ_i ：単語。ｗ_i ∈ＫＥＹ． ４）ＤＯＣ：文書データベース中の文書集合。 ５）ｓ_i ：状態。ｓ_i ∈Ｓ．

【００２９】

【数２】 各状態は、単語と文書に関するべクトルで表現され、ど
の単語がキーワードとしてユーザによって入力され、ど
の単語とどの文書が既にユーザに提示されてどのような
評価をユーザから受けているかを示す。状態ベクトルの
第１要素から第|ＤＢ| 要素はＤＢ中の各単語に対応
し、第 |ＤＢ| ＋１要素から第 |ＫＥＹ|要素はＫＥＹ
中の単語でＤＢ中には存在しない各単語に対応し、第 |
ＫＥＹ| ＋１要素から第 |ＫＥＹ| ＋ |ＤＯＣ| 要素は
ＤＯＣ中の各文書に対応する。

【００３０】

【数３】 但し、ｓ₁ とｓ _|S| はそれぞれユーザが検索結果に満
足して検索を終了した場合の吸収状態と、ユーザが検索
結果に満足せずに検索を終了した場合の吸収状態を示
し、特にべクトル表現では表現しない。 ６）ａ_i ：行動。ａ_i ∈Ａ．関連語の提示（一度にＭ₂
個）および検索文書の提示（一度にＭ₃ 個）に対応。但
し、一度に選択される行動は、関連語を提示するか、検
索文書を提示するかのどちらか片方のみ。Ａは行動の全
集合。

【００３１】

【数４】 但し、

【００３２】

【数５】 ７）Ｓ（ｓ_i ，ａ_k ）：状態ｓ_i で行動ａ_k を選択した
ときに、遷移可能な状態の集合。つまり、状態ｓ_i で行
動ａ_k という関連語または検索文書の提示を行った場合
のユーザの評価によって生ずる遷移後の状態の集合。Ｓ
（ｓ_i ，ａ_k ）⊆Ｓ．

【００３３】

【数６】 ８）Ａ（ｓ_i ）：状態ｓ_i において選択可能な行動の集
合。つまり、状態ｓ_i において考えられる関連語および
検索文書の提示の全候補。

【００３４】

【数７】 ９）ｒ（ｓ_i ，ａ_k 、ｓ_j ）：状態ｓ_i において行動ａ
_k を選択したもとで状態ｓ_j に遷移した場合の収益。

【００３５】

【数８】 但し、Ｒ_l は∞＞Ｒ_l ＞０でユーザが検索結果に満足し
て検索を終了した場合の正の収益を示し、Ｒ₂ は−∞＜
Ｒ₂ ＜０でユーザが検索結果に満足せずに検索を終了し
た場合の負の収益を示す。収益は、ｓ₁ かｓ _|S| の吸
収状態に遷移したとき、つまりユーザが検索を終了した
ときのみ生ずる。 １０）ｘ_t ：ｔ時点の状態。ｘ_t ∈Ｓ。 １１）ｙ_t ：ｔ時点の行動。ｙ_t ∈Ｓ。 １２）α₁ ：割引率。０＜α₁ ≦１．ｔ時点の遷移でユ
ーザが満足して検索を終了した場合の正の収益をα₁ ^t
Ｒ_l で評価する。ユーザを満足させるために時間がかか
れば、その時間分、収益が割り引かれる。 １３）α₂ ：増大率。１≦α₂ ＜∞．ｔ時点の遷移でユ
ーザが満足せずに検索を終了した場合の負の収益をα₂
^t Ｒ₂ で評価する。時間をかけたにもかかわらず、ユー
ザを満足させられなかつた場合には、その時間分、負の
収益が増大する。 １４）ｘ（ｙｘ）ⁿ ：系列ｘ₀ ｙ₀ ｘ₁ ｙ₁ ｘ₂ …ｙ
_n-1 ｘ_n を示す。（状態ｘ ₀ で行動ｙ₀ を選択し状態ｘ
₁ ヘ遷移し、さらに状態ｘ₁ で行動ｙ₁ を選択し状態ｘ
₂ ヘ遷移し、・・・、状態ｘ_n-1 で行動ｙ_n-1 を選択し
状態ｘ_n ヘ遷移したことを示す。） １５）θ：遷移確率分布を支配する連続パラメータ。θ
∈Θ。但し、真のパラメータθ^* は未知。Θはパラメー
タθの全集合。 １６）ｐ（θ）：パラメータθの事前確率密度関数。 １７）ｐ〔θ| ｘ（ｙｘ）ⁿ 〕：ｘ（ｙｘ）ⁿ という遷
移を観測した場合の、パラメータθの事後確率密度関
数。 １８）ｐ（ｓ_j | ｓ_i ，ａ_k 、θ）：パラメータθによ
つて支配された遷移確率分布において、状態ｓ_i で行動
ａ_k を選択したという条件のもとで、状態ｓ_j ヘ遷移す
る確率。つまり、ユーザが文書を検索している途中のあ
る状態ｓ_jで、行動ａ_k という関連語または検索文書の
提示を受けたときに、ユーザがどのような評価を下すか
を示す確率分布。 １９）

【００３６】

【数９】 ：ｘ（ｙｘ）ⁿ という遷移を観測した場合の、遷移確率
ｐ（ｓ_j | ｓ_i ，ａ_k ，θ）のパラメータθの事後確率
ｐ〔θ| ｘ（ｙｘ）ⁿ 〕による加重平均。

【００３７】

【数１０】 パラメータθの事前分布にベ−タ分布（鈴木、“統計
学”、朝倉書店（１９８７）。）が仮定される場合に
は、遷移確率の加重平均は以下のように計算される。

【００３８】

【数１１】 但し、ｃｏｕｎｔ〔ｓ_j | ｓ_i ，ａ_k ，ｘ（ｙｘ）
ⁿ 〕は系列ｘ（ｙｘ）ⁿ 中で状態ｓ_i において行動ａ
_k を選択したもとで状態ｓ_j ヘ遷移した回数、β（ｓ_j
| ｓ_i ，ａ_k ）はべ−タ分布のパラメータを示す。 ２０）π〔ｘ（ｙｘ）ⁿ 〕：政策。ｘ（ｙｘ）ⁿ という
遷移を経て状態ｘ_n に至つた時に、状態ｘ_n において選
択するべき行動を決定する関数。関連語および検索文書
の提示の仕方に相当する。π∈Π． ２１）ＸＹ（ｘ₀ ）：初期状態ｘ₀ から吸収状態ｓ₁ ま
たはｓ _|S| ヘ至る全系列による集合。

【００３９】

【数１２】 ２２）ＸＹ（ｘ₀ ，π）：政策πを用いて、初期状態ｘ
₀ から吸収状態ｓ₁ またはｓ _|S| ヘ至る全系列による
集合。ＸＹ（ｘ₀ ，π）⊆ＸＹ（ｘ₀ ）．

【００４０】

【数１３】 ２３）ｕ〔ｘ（ｙｘ）ⁿ ，π，θ〕：効用関数（繁桝、
“ベイズ統計入門”、東京大学出版会（１９８
５）。）。遷移確率を支配するパラメータがθであつた
場合に、政策πを用いて、ｘ（ｙｘ）ⁿ と遷移したとき
に得られる収益を示す関数。

【００４１】

【数１４】 また、効用関数の値は実際にはパラメータθゃ政策πに
依らずに、系列ｘ（ｙｘ）ⁿ によつて定まるので、ｕ’
〔ｘ（ｙｘ）ⁿ 〕＝ｕ〔ｘ（ｙｘ）ⁿ ，π，θ）と置く
ことができる・

【００４２】

【数１５】 ２４）

【００４３】

【数１６】 ：期待効用関数。遷移確率を支配するパラメータがθで
あった場合に、政策πを用いたときに得られる期待収益
を示す関数。

【００４４】

【数１７】 ２５）

【００４５】

【数１８】 ：ベイズ期待効用関数。パラメータの事前分布がｐ
（θ）であつた場合に、政策πを用いたときに得られる
期待収益を示す関数。

【００４６】

【数１９】 ２６）ＢＤ〔ｐ（θ）〕：ベイズ決定。パラメータの事
前分布がｐ（θ）であつた場合に、ベイズ期待効用関数
を最大化するような政策。つまり、関連語および検索文
書の最適な提示の仕方である。

【００４７】

【数２０】

【００４８】次に図４に示された検索木作成部１００の
動作フローチャートを参照して、検索木作成部１００の
動作を説明する。まず、検索木展開器１１０にキーワー
ドが入力される（ステップ７０）。キーワードが入力さ
れると、検索木展開器１１０はキーワードによって定ま
る初期状態（０時点の状態）ｘ₀ 〔（２）式および
（３）式参照〕をルートとし、可能な全ての系列ｘ（ｙ
ｘ）ⁿ （ｎ≦Ｍ₀ −１）をノードとして持つような検索
木を作成し、各ノードについて事後分布算出器１２０ヘ
ノード情報を送ると共に事後分布算出器１２０から遷移
確率ｐ（ｓ_j | ｓ_i ，ａ_k ，θ）を支配する未知パラメ
ータθの事後確率分布ｐ〔θ|ｘ（ｙｘ）ⁿ 〕の情報を
受け取り、検索木を完成する（ステップ７２）。なお、
事後分布算出器１２０は検索木展開器１１０からノード
情報を受け取ると、ｃｏｕｎｔ（ｓ_j | ｓ_i ，ａ_k ，ｘ
（ｙｘ）ⁿ ）を算出し、事後確率分布ｐ〔θ|ｘ（ｙ
ｘ）ⁿ 〕の情報として、べ−タ分布パラメータテーブ
ル１３０に格納されているパラメータθの事前確率ｐ
（θ）を示すべータ分布のパラメータβ（ｓ_j | ｓ_i ，
ａ_k ）とｃｏｕｎｔ（ｓ_j | ｓ_i ，ａ_k ，ｘ（ｙ
ｘ）ⁿ ）とを検索木展開器１１０ヘ送る。検索木の完成
後、検索木展開器１１０は検索木を出力する（ステップ
７４）。

【００４９】図５に示された関連語・検索文書提示候補
決定部２００の動作フローチャートを参照して、関連語
・検索文書提示候補決定部２００の動作を説明する。ま
ず、検索木解析器２１０に検索木が入力される（ステッ
プ８０）。検索木が入力されると、（１７）式を満足す
るような政策を算出し、算出された最適な政策を関連語
・検索文書提示候補テーブル２２０に送る（ステップ８
２）。（１７）式を満足する政策の算出の仕方について
補足を加える。（１７）式のべイズ決定は次式のように
書き下すことができる。

【００５０】

【数２１】 （１８）式のべイズ決定は、ＤＰ（動的計画法）（森村
等、”マルコフ解析”、日科技連（１９７９）。）によ
ってＭ₀ −１時点の決定から０時点の決定ヘと溯ってい
くことによって、逐次的に求めることができる。∀ｘ
（ｙｘ）ⁿ ∈ＸＹ（ｘ₀ ）である系列の各状態ｘ_t （０
≦ｔ≦ｎ−１．）における決定は以下のように算出され
る。ｔ＝Ｍ₀ −１のとき、

【００５１】

【数２２】 ｔ＝Ｍ₀ −２のとき、

【００５２】

【数２３】 但し、

【００５３】

【数２４】 ０≦ｔ≦Ｍ₀ −３のとき、

【００５４】

【数２５】 但し，

【００５５】

【数２６】 検索木解析器２１０が最適な政策を算出し終えると、関
連語・検索文書提示候補決定器２３０は関連語・検索文
書提示候補テーブルの政策を見てキーワード（初期状
態）に対する最適な関連語または検索文書を決定し（ス
テップ８４）、出力する（ステップ８６）。ユーザは提
示された各関連語または各検索文書に対して受理または
拒否の評価を入力するか、検索結果に満足あるいは満足
せずに検索を終了することを入力する（ステップ８８）
ステップ８８において検索が終了していない場合には、
ユーザの入力した関連語または検索文書に対する評価を
踏まえた次時点の状態に対してステップ８４から繰り返
す。

【００５６】次に、本発明の第２の実施の形態の関連語
提示を伴う文書検索方法と検索装置について図面を参照
して説明する。図６は本発明の第２の実施の形態の関連
語提示を伴う文書検索装置の模式的ブロック構成図であ
る。

【００５７】図６は、本発明の文書検索装置２０を、装
置を構成するコンピュータとして示したものであり、コ
ンピュータはモデム、キーボード、ポインティングデバ
イス等の入力部３０、モデム、プリンタ、ディスプレイ
等の出力部４０、データ処理装置５０、記憶部６０およ
び記録媒体７０を備え、データ処理装置５０はデータ処
理装置５０の各部を制御する制御部５１を有する。記録
媒体７０には各部の動作を制御できる本発明の関連語提
示を伴う文書検索システム制御プログラムが記録されて
おり、ＦＤ，ＣＤ−ＲＯＭ、半導体メモリ等が用いられ
る。

【００５８】関連語提示を伴う文書検索方法や検索装置
の構成は第１の実施の形態と同じなので説明を省略す
る。

【００５９】ユーザから入力されたキーワードに基づ
き、関連語および検索文書の最適な提示の仕方を選定
し、ユーザから入力した評価を参照して関連語および検
索文書を検索して出力するための制御プログラムは記録
媒体７０からデータ処理装置５０の制御部５１に読み込
まれデータ処理装置５０の動作を制御する。データ処理
装置５０は制御プログラムの制御により以下の処理を実
行する。

【００６０】即ち、キーワードが入力されると、そのキ
ーワードによって定まる初期状態をルートとし、可能な
全ての系列を枝でつながるノードと葉として持つような
検索木を作成する処理と、各ノードについて、遷移確率
分布を支配する連続パラメータの事前確率密度関数を示
すべータ分布のパラメータを用いて事後分布を算出し
て、検索木を完成する処理と、完成した検索木から、ベ
イズ期待効用関数を最大化するような関連語および検索
文書の最適な提示の仕方を選定し、既に提示された関連
語や検索文書に対してユーザが入力した評価が存在する
場合にはその評価に対応して最適な提示の仕方を選定
し、関連語や検索文書の提示候補を決定してユーザに提
示することを繰り返す処理とを実行する。

【００６１】

【発明の効果】上述のように、本発明によれば、文書検
索システムが提示する関連語および検索文書に対するユ
ーザの評価に多項分布を仮定し、ユーザが検索結果に満
足して検索を終了した場合に生ずる対話回数の増加に伴
って減少する正の収益、およびユーザが検索結果に満足
せずに検索を終了した場合に生ずる対話回数の増加に伴
って増大する負の収益を導入し、正の収益から負の収益
を差し引いた残りを収益として導入することによって、
関連語提示を伴う文書検索を未知パラメータを含むマル
コフ決定過程で定式化し、収益をべイズ基準のもとで最
大化するように関連語および検索文書の提示候補を決定
しているので、ユーザが入力したキーワードから欲しい
文書ヘユーザを導くという点に関して有効にユーザの検
索支援を行いながら、かつ対話回数の増加に伴うユーザ
の負担をできる限り少なくすることが可能になる。

【図面の簡単な説明】

【図１】本発明の関連語提示を伴う文書検索装置を説明
するための原理構成図である。

【図２】本発明の関連語提示を伴う文書検索方法の原理
を説明するためのフローチャートである。

【図３】本発明による関連語提示を伴う文書検索装置の
第１の実施の形態の構成図である。

【図４】本発明の第１の実施の形態による検索木作成部
の動作フローチャートである。

【図５】本発明の第１の実施の形態による関連語・検索
文書提示候補決定部の動作フローチャートである。

【図６】本発明の第２の実施の形態の関連語提示を伴う
文書検索装置の構成図である。

【図７】従来方法による文書検索のための関連語提示方
法の動作原理説明図である。

【符号の説明】

１０、２０ 文書検索装置 ３０ 入力部 ４０ 出力部 ５０ データ処理装置 ６０ 記憶部 ７０ 記録媒体 １００ 検索木作成部 １１０、６１０ 検索木展開器 １２０、６２０ 事後分布算出器 １３０、６３０ データ分布パラメータテーブル ２００ 関連語・検索文書提示候補決定部 ２１０、７１０ 検索木解析器 ２２０、７２０ 関連語・検索文書提示候補テーブル ２３０、７３０ 関連語・検索文書提示候補決定器 Ｓ１０〜Ｓ６０、Ｓ７０〜Ｓ７４、Ｓ８０〜Ｓ８８、Ｓ
９０〜Ｓ９２ ステップ

Claims (7)

【特許請求の範囲】
1. 【請求項１】 文書データベースにおける関連語提示を
   伴う文書検索方法であって、 ユーザからキーワードが入力されると、該キーワードに
   対する関連語および検索文書の提示の仕方を全列挙した
   検索木を作成するステップと、 該検索木を解析して前記ユーザが満足あるいは満足しな
   いことによって生ずる正または負の収益から成る収益を
   べイズ基準のもとで最大化する関連語および検索文書の
   提示の仕方を選定するステップと、 選定された関連語および検索文書の提示の仕方に従っ
   て、前記ユーザから入力された前記キーワードや、さら
   に既に提示された関連語や検索文書に対して前記ユーザ
   が入力した評価が存在する場合には該評価に対応して、
   最適な関連語および検索文書のいずれかを決定するステ
   ップと、 決定した前記関連語および前記検索文書のいずれかを前
   記ユーザに提示するステップと、 提示された前記関連語および前記検索文書に対する前記
   ユーザの評価を入力するステップと、 前記ユーザが満足あるいは満足せずに検索を終了するま
   で、繰り返し、該評価に対応して最適な関連語および検
   索文書のいずれかを決定して前記ユーザに提示するステ
   ップと、を有することを特徴とする関連語提示を伴う文
   書検索方法。
2. 【請求項２】 前記キーワードに対する関連語および検
   索文書の提示の仕方を全列挙した検索木を作成する前記
   ステップは、 前記キーワードが入力されると、該キーワードによって
   定まる初期状態をルートとし、可能な全ての系列を枝で
   つながるノードと葉として持つような検索木を作成する
   ステップと、 各前記ノードについて、遷移確率分布を支配する未知連
   続パラメータの事前確率密度関数を示すべータ分布のパ
   ラメータを用いて事後分布を算出して、前記検索木を完
   成するステップと、 最適な関連語および検索文書のいずれかを決定する前記
   ステップは、 完成した前記検索木から、前記ユーザが入力したキーワ
   ードに基づいて、過去ユーザに提示した関連語および検
   索文書に対するユーザの評価に多項分布を仮定したもと
   で、ユーザが検索結果に満足して検索を終了した場合に
   生ずる正の収益からユーザが検索結果に満足せずに検索
   を終了した場合に生ずる負の収益を差し引いた残りの収
   益をべイズ基準のもとで最大化するような関連語および
   検索文書の最適な提示の仕方を選定し、既に提示された
   関連語や検索文書に対して前記ユーザが入力した評価が
   存在する場合には該評価に対応した最適な提示の仕方を
   選定するステップと、 選定された最適な提示の仕方に従って関連語および検索
   文書のいずれかの提示候補を決定するステップと、を有
   する請求項１に記載の関連語提示を伴う文書検索方法。
3. 【請求項３】 前記ユーザが検索結果に満足して検索を
   終了した場合に生ずる前記正の収益は、前記ユーザとの
   対話回数の増加に伴って正の収益の絶対値が減少し、 前記ユーザが検索結果に満足せずに検索を終了した場合
   に生ずる前記負の収益は、前記ユーザとの対話回数の増
   加に伴って負の収益の絶対値が増大する、請求項２に記
   載の関連語提示を伴う文書検索方法。
4. 【請求項４】 文書データベースにおける関連語提示を
   伴う文書検索装置であって、 前記文書検索装置は、キーワードが与えられると検索木
   を出力する検索木作成部と、最適な関連語および検索文
   書のいずれかを出力する関連語・検索文書提示候補決定
   部とを備え、 関連語・検索文書提示候補決定部は、前記検索木が与え
   られると最適な関連語および検索文書の提示の仕方を選
   定して前記キーワードに対する最適な関連語および検索
   文書のいずれかを出力し、出力した関連語および検索文
   書のいずれかに対するユーザの評価が入力されると、ユ
   ーザが満足あるいは満足せずに検索を終了するまで、繰
   り返しその評価を踏まえた最適な関連語および検索文書
   のいずれかを出力する、ことを特徴とする関連語提示を
   伴う文書検索装置。
5. 【請求項５】 前記検索木作成部は、検索木を作成する
   検索木展開器と、べータ分布のパラメータを用いて事後
   分布を算出する事後分布算出器と、べータ分布のパラメ
   ータを格納するベータ分布パラメータテーブルとを備
   え、 前記検索木展開器は、前記キーワードが入力されると、
   該キーワードによって定まる初期状態をルートとし、可
   能な全ての系列を枝でつながるノードと葉として持つよ
   うな検索木を作成し、 前記事後分布算出器は、各前記ノードについて、遷移確
   率分布を支配する連続パラメータの事前確率密度関数を
   示すべータ分布のパラメータを用いて事後分布を算出し
   て前記検索木展開器に前記検索木を完成させ、 ベータ分布パラメータテーブルは、連続パラメータの事
   前確率密度関数を示すべータ分布のパラメータを格納
   し、 前記関連語・検索文書提示候補決定部は、関連語および
   検索文書の最適な提示の仕方を選定する検索木解析器
   と、関連語および検索文書の最適な提示の仕方を格納す
   る関連語・検索文書提示候補テーブルと、関連語および
   検索文書の最適な提示の仕方から、提示する関連語およ
   び検索文書のいずれかを決定して前記ユーザに提示する
   関連語・検索文書提示候補決定器とを備え、 前記検索木解析器は、完成した前記検索木から、ベイズ
   期待効用関数を最大化するような関連語および検索文書
   の最適な提示の仕方を選定し、既に提示された関連語や
   検索文書に対して前記ユーザから入力した評価が存在す
   る場合には該評価に対応して最適な提示の仕方を選定
   し、 前記関連語・検索文書提示候補テーブルは、関連語およ
   び検索文書と関連語および検索文書の最適な提示の仕方
   を格納し、 前記関連語・検索文書提示候補決定器は、前記関連語・
   検索文書提示候補テーブルに格納された関連語および検
   索文書の最適な提示の仕方から、提示する関連語および
   検索文書のいずれかを決定して前記ユーザに提示するこ
   とを、ユーザが満足あるいは満足せずに検索を終了する
   まで繰り返す、請求項４に記載の関連語提示を伴う文書
   検索装置。
6. 【請求項６】 記録媒体を備え、前記各制御部の動作
   は、記録媒体に記録された関連語提示を伴う文書検索プ
   ログラムにより制御できる、請求項５に記載の関連語提
   示を伴う文書検索装置。
7. 【請求項７】 ユーザから入力されたキーワードに基づ
   き、関連語および検索文書の最適な提示の仕方を選定
   し、前記ユーザから入力した評価を参照して関連語およ
   び検索文書を検索して出力するための制御プログラムを
   記録した記録媒体であって、 前記キーワードが入力されると、該キーワードによって
   定まる初期状態をルートとし、可能な全ての系列を枝で
   つながるノードと葉として持つような検索木を作成する
   手順と、 各前記ノードについて、遷移確率分布を支配する連続パ
   ラメータの事前確率密度関数を示すべータ分布のパラメ
   ータを用いて事後分布を算出して、検索木を完成する手
   順と、 完成した前記検索木から、ベイズ期待効用関数を最大化
   するような関連語および検索文書の最適な提示の仕方を
   選定し、既に提示された関連語や検索文書に対して前記
   ユーザが入力した評価が存在する場合には該評価に対応
   して最適な提示の仕方を選定し、関連語および検索文書
   のいずれかの提示候補を決定してユーザに提示すること
   を繰り返す手順と、を実行させるためのプログラムを記
   録した機械読み取り可能な記録媒体。