(57)【要約】【課題】類似するテキストの検索精度を向上させる。【解決手段】テキスト１４の入力を受け付ける。テキスト１４に含まれる第１の単語を抽出し、関連する単語のグループを示す関連語辞書１３を参照して、第１の単語のうち何れかのグループに属する第１の単語に対して当該グループを示す第１のダミー語を割り当てる。第１の単語および第１のダミー語を含む単語集合１６に応じた特徴情報１８を生成する。テキスト１５ａ，１５ｂに対応して記憶された、当該テキストに含まれる第２の単語および何れかの第２の単語が属するグループを示す第２のダミー語を含む単語集合１７ａ，１７ｂに応じた特徴情報１９ａ，１９ｂと、特徴情報１８との間の比較に基づいて、テキスト１４に類似するテキスト１５ａを検索する。【選択図】図１
2020004107.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
第１のテキストの入力を受け付け、
前記第１のテキストに含まれる２以上の第１の単語を抽出し、関連する単語のグループを示す関連語辞書を参照して、前記２以上の第１の単語のうち何れかのグループに属する第１の単語に対して当該グループを示す第１のダミー語を割り当て、
前記２以上の第１の単語および前記第１のダミー語を含む第１の単語集合に応じた第１の特徴情報を生成し、
複数の第２のテキストそれぞれに対応して記憶された、当該第２のテキストに含まれる２以上の第２の単語および何れかの第２の単語が属するグループを示す第２のダミー語を含む第２の単語集合に応じた第２の特徴情報と、前記第１の特徴情報との間の比較に基づいて、前記第１のテキストに類似する第２のテキストを検索する、
類似テキスト検索方法。
【請求項２】
前記第１の特徴情報は、異なる複数のハッシュ関数によって前記第１の単語集合から算出される複数のハッシュ値を含む第１のベクトルであり、
前記第２の特徴情報は、前記複数のハッシュ関数によって前記第２の単語集合から算出される複数のハッシュ値を含む第２のベクトルである、
請求項１記載の類似テキスト検索方法。
【請求項３】
前記複数のハッシュ関数はそれぞれ、単語およびダミー語それぞれに対して一意な値を対応付けた対応関係をもち、入力された単語集合に含まれる単語およびダミー語に対応する値の中で最小の値をハッシュ値として出力する、
請求項２記載の類似テキスト検索方法。
【請求項４】
前記コンピュータが更に、
前記検索された第２のテキストに対応付けられて記憶された第３のテキストを、前記第１のテキストに対する応答として出力する、
請求項１記載の類似テキスト検索方法。
【請求項５】
関連する単語のグループを示す関連語辞書を記憶すると共に、複数の第２のテキストそれぞれに対応して、当該第２のテキストに含まれる２以上の第２の単語および何れかの第２の単語が属するグループを示す第２のダミー語を含む第２の単語集合に応じた第２の特徴情報を記憶する記憶部と、
第１のテキストの入力を受け付け、前記第１のテキストに含まれる２以上の第１の単語を抽出し、前記関連語辞書を参照して前記２以上の第１の単語のうち何れかのグループに属する第１の単語に対して当該グループを示す第１のダミー語を割り当て、前記２以上の第１の単語および前記第１のダミー語を含む第１の単語集合に応じた第１の特徴情報を生成し、前記第２の特徴情報と前記第１の特徴情報との間の比較に基づいて前記第１のテキストに類似する第２のテキストを検索する処理部と、
を有する類似テキスト検索装置。
【請求項６】
コンピュータに、
第１のテキストの入力を受け付け、
前記第１のテキストに含まれる２以上の第１の単語を抽出し、関連する単語のグループを示す関連語辞書を参照して、前記２以上の第１の単語のうち何れかのグループに属する第１の単語に対して当該グループを示す第１のダミー語を割り当て、
前記２以上の第１の単語および前記第１のダミー語を含む第１の単語集合に応じた第１の特徴情報を生成し、
複数の第２のテキストそれぞれに対応して記憶された、当該第２のテキストに含まれる２以上の第２の単語および何れかの第２の単語が属するグループを示す第２のダミー語を含む第２の単語集合に応じた第２の特徴情報と、前記第１の特徴情報との間の比較に基づいて、前記第１のテキストに類似する第２のテキストを検索する、
処理を実行させる類似テキスト検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は類似テキスト検索方法、類似テキスト検索装置および類似テキスト検索プログラムに関する。
【背景技術】
【０００２】
コンピュータによる自然言語処理として、データベースに記憶された保存テキストの中から入力テキストに類似する保存テキストを検索したいことがある。例えば、問い合わせ文のサンプルと当該サンプルに対応する返答文とをデータベースに登録しておき、入力された問い合わせ文に類似するサンプルを検索し、当該類似するサンプルに対応する返答文を出力する対話システムを構築することが考えられる。
【０００３】
入力テキストに類似する保存テキストを検索する方法としては、２つのテキストの間で出現する単語の共通度を評価する方法がある。例えば、以下のような検索方法が考えられる。あるテキストに含まれる単語集合から１つのハッシュ値を算出するハッシュ関数（Min-hash関数と言うことがある）を複数個定義しておく。各ハッシュ関数は、異なる単語に対して異なる値を対応付けた対応関係をもち、ある単語集合に含まれる単語に対応する値のうち最小の値をハッシュ値として出力する。各保存テキストに対して、この複数のハッシュ関数を用いて算出された複数のハッシュ値を列挙したベクトルを予め生成しておく。入力テキストに含まれる単語集合と上記の複数のハッシュ関数から同様にベクトルを算出し、近似するベクトルをもつ保存テキストを選択する。
【０００４】
なお、問い合わせ文に対応する返答文の候補を絞り込む質問回答サーバが提案されている。提案の質問回答サーバは、問い合わせ文から単語を抽出し、抽出した単語を含む複数のコメント文をデータベースから検索し、検索されたコメント文を複数のトピックグループに分類する。質問回答サーバは、トピックグループ毎にコメント文との類似度が閾値以上である返答文の候補をデータベースから抽出する。
【０００５】
また、問い合わせ文に対応する返答文を異なる検索方法を併用して検索する端末装置が提案されている。提案の端末装置は、第１の検索方法によって問い合わせ文に対応する返答文を検索し、検索された第１の返答文を音声で再生する。端末装置は、第１の返答文が再生されている間、第２の検索方法によって問い合わせ文に対応する返答文を検索し、検索された第２の返答文と第１の返答文との類似度が低い場合、第１の返答文の再生が終了した後に追加的に第２の返答文を音声で再生する。
【０００６】
また、コンテンツのハッシュ値を算出するハッシュ関数を学習するハッシュ関数生成装置が提案されている。提案のハッシュ関数生成装置は、複数のコンテンツそれぞれから特徴量を算出する。また、ハッシュ関数生成装置は、各コンテンツに付与された意味ラベルに基づいて、２つのコンテンツの組み合わせ毎に意味ラベルの相関を算出する。ハッシュ関数生成装置は、意味ラベルの相関が高いほど２つのコンテンツそれぞれの特徴量から算出されるハッシュ値が近似するように、ハッシュ関数を学習する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１４−１１２３１６号公報
【特許文献２】特開２０１６−９０９１号公報
【特許文献３】特開２０１６−６６０１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
出現する単語の共通度を評価する検索方法では、内容の類似度が高いにもかかわらず異なる表現が使用されることで単語の共通度が低く評価され、検索漏れが発生することがあるという問題がある。例えば、入力テキストや保存テキストがユーザの発話メッセージである場合、話し言葉は１文が短く表現も多様であることから、入力テキストと保存テキストとの間で共通の単語が出現する確率が全体的に低くなる。その結果、入力テキストに類似する保存テキストの検索精度が低くなりやすい。
【０００９】
１つの側面では、本発明は、類似するテキストの検索精度を向上させる類似テキスト検索方法、類似テキスト検索装置および類似テキスト検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
１つの態様では、コンピュータが実行する類似テキスト検索方法が提供される。第１のテキストの入力を受け付ける。第１のテキストに含まれる２以上の第１の単語を抽出し、関連する単語のグループを示す関連語辞書を参照して、２以上の第１の単語のうち何れかのグループに属する第１の単語に対して当該グループを示す第１のダミー語を割り当てる。２以上の第１の単語および第１のダミー語を含む第１の単語集合に応じた第１の特徴情報を生成する。複数の第２のテキストそれぞれに対応して記憶された、当該第２のテキストに含まれる２以上の第２の単語および何れかの第２の単語が属するグループを示す第２のダミー語を含む第２の単語集合に応じた第２の特徴情報と、第１の特徴情報との間の比較に基づいて、第１のテキストに類似する第２のテキストを検索する。
【００１１】
また、１つの態様では、記憶部と処理部とを有する類似テキスト検索装置が提供される。また、１つの態様では、類似テキスト検索プログラムが提供される。
【発明の効果】
【００１２】
１つの側面では、類似するテキストの検索精度が向上する。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の類似テキスト検索装置の例を説明する図である。
【図２】情報処理装置のハードウェア例を示すブロック図である。
【図３】発話テーブルの例を示す図である。
【図４】ハッシュ関数およびベクトルの例を示す図である。
【図５】探索木の例を示す図である。
【図６】ジャッカール係数の算出例を示す図である。
【図７】類似度の閾値と検索対象発話のヒット数との関係例を示すグラフである。
【図８】関連語テーブルの例を示す図である。
【図９】単語集合からベクトルを算出する例を示す図である。
【図１０】問い合わせ発話に対応する返答発話の選択例を示す図である。
【図１１】情報処理装置の機能例を示すブロック図である。
【図１２】インデックス生成の手順例を示すフローチャートである。
【図１３】インデックス生成の手順例を示すフローチャート（続き）である。
【図１４】発話検索の手順例を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１５】
図１は、第１の実施の形態の類似テキスト検索装置の例を説明する図である。
第１の実施の形態の類似テキスト検索装置１０は、入力されたテキストと類似するテキストをデータベースの中から検索する。類似テキスト検索装置１０は、情報処理装置やコンピュータと呼んでもよい。また、類似テキスト検索装置１０は、ユーザが操作するクライアント装置でもよいし、ネットワーク経由でアクセスされるサーバ装置でもよい。類似テキスト検索装置１０は、ユーザから問い合わせテキストを受け付け返答テキストを出力する対話システムに用いられるものであってもよい。
【００１６】
類似テキスト検索装置１０は、記憶部１１および処理部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の半導体メモリでもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性ストレージでもよい。処理部１２は、例えば、ＣＰＵ（Central Processing Unit）、ＧＰＵ（Graphics Processing Unit）、ＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、処理部１２は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。
【００１７】
記憶部１１は、関連語辞書１３を記憶する。関連語辞書１３は、互いに関連する単語のグループを示すデータである。関連する単語は、類似する意味をもつ単語である。例えば、関連語辞書１３は、「猫」と「にゃんこ」が同一のグループＧ１に属し、「ご飯」と「えさ」が同一のグループＧ２に属することを示す。
【００１８】
また、記憶部１１は、テキスト１５ａ，１５ｂを含む複数のテキスト（第２のテキスト）に対応して、特徴情報１９ａ，１９ｂを含む複数の特徴情報（第２の特徴情報）を記憶する。テキスト１５ａ，１５ｂは、類似テキスト検索装置１０に入力されるテキスト１４（第１のテキスト）と照合すべき検索対象テキストであり、２以上の単語を含む文字列である。特徴情報１９ａ，１９ｂは、検索のためのインデックスとして使用され、テキスト１５ａ，１５ｂから生成される。記憶部１１は、テキスト１５ａ，１５ｂそのものを記憶していてもよいし記憶していなくてもよい。特徴情報１９ａ，１９ｂは、類似テキスト検索装置１０が生成してもよいし他の情報処理装置が生成してもよい。
【００１９】
特徴情報１９ａ，１９ｂを生成する方法については後述する。なお、類似テキスト検索装置１０を対話システムに用いる場合、記憶部１１は、テキスト１５ａ，１５ｂを含む複数のテキストに対応付けて、複数の返答テキスト（第３のテキスト）を記憶してもよい。例えば、ユーザからの問い合わせテキストに最も類似する検索対象テキストが選択されると、選択された検索対象テキストに対応付けられた返答テキストが出力される。
【００２０】
処理部１２は、テキスト１４の入力を受け付ける。テキスト１４は、ユーザから入力される問い合わせテキストであり、２以上の単語を含む文字列である。テキスト１４は、類似テキスト検索装置１０に接続された入力デバイスから入力されてもよいし、他の情報処理装置からネットワーク経由で受信されてもよい。また、類似テキスト検索装置１０に音声信号が入力され、音声認識により音声信号がテキスト１４に変換されてもよい。
【００２１】
処理部１２は、テキスト１４に含まれる２以上の単語を抽出し、抽出した単語を含む単語集合１６を生成する。例えば、処理部１２は、テキスト１４から「にゃんこ」と「えさ」を抽出し、「にゃんこ」と「えさ」を含む単語集合１６を生成する。
【００２２】
また、処理部１２は、関連語辞書１３を参照して、テキスト１４から抽出した単語のうち何れかのグループに属する単語に対して、当該グループを示すダミー語（第１のダミー語）を割り当てる。処理部１２は、割り当てたダミー語を単語集合１６に追加する。ダミー語は、テキスト１４やテキスト１５ａ，１５ｂに使用されない仮想的な単語である。例えば、「にゃんこ」はグループＧ１に属するため、グループＧ１を示すダミー語「Ｇ１」が単語集合１６に追加される。また、「えさ」はグループＧ２に属するため、グループＧ２を示すダミー語「Ｇ２」が単語集合１６に追加される。このとき、元の単語である「にゃんこ」や「えさ」は単語集合１６から削除されずに残される。
【００２３】
処理部１２は、テキスト１４に含まれる元の単語およびダミー語を含む単語集合１６から、テキスト１４のインデックスに相当する特徴情報１８（第１の特徴情報）を生成する。特徴情報１８は、問い合わせテキストと検索対象テキストとの間で出現する単語の共通度を評価するための情報である。特徴情報１８は、例えば、以下のように生成される。
【００２４】
処理部１２は、異なる複数のハッシュ関数を予め用意しておく。処理部１２は、複数のハッシュ関数にそれぞれ単語集合１６を入力し、複数のハッシュ関数から出力された複数のハッシュ値を列挙したベクトルを特徴情報１８として生成する。ハッシュ関数はMin-hash関数であってもよい。例えば、各ハッシュ関数は、単語およびダミー語それぞれに対して一意な値を対応付けた対応関係をもつ。異なるハッシュ関数は異なる対応関係をもつ。ハッシュ関数は、単語集合に含まれる単語およびダミー語に対応する値の中で最小の値をハッシュ値として出力する。例えば、「にゃんこ」、「えさ」、「Ｇ１」および「Ｇ２」を含む単語集合１６から（０，１，２，２，…）といったベクトルが生成される。
【００２５】
テキスト１５ａ，１５ｂからも同様にして特徴情報１９ａ，１９ｂを生成することが可能である。テキスト１５ａに含まれる２以上の単語が抽出され、抽出された単語に対して関連語辞書１３を参照してダミー語（第２のダミー語）が割り当てられ、テキスト１５ａに含まれる元の単語およびダミー語を含む単語集合１７ａが生成される。そして、単語集合１７ａから特徴情報１９ａが生成される。例えば、単語集合１７ａを複数のハッシュ関数に入力することで算出された複数のハッシュ値を列挙したベクトルが生成される。また、テキスト１５ｂに含まれる２以上の単語が抽出され、抽出された単語に対して関連語辞書１３を参照してダミー語が割り当てられ、テキスト１５ｂに含まれる元の単語およびダミー語を含む単語集合１７ｂが生成される。そして、単語集合１７ｂから特徴情報１９ｂが生成される。例えば、単語集合１７ｂを複数のハッシュ関数に入力することで算出された複数のハッシュ値を列挙したベクトルが生成される。
【００２６】
例えば、テキスト１５ａから「猫」と「ご飯」が抽出され、「猫」が属するグループＧ１を示すダミー語「Ｇ１」が追加され、「ご飯」が属するグループＧ２を示すダミー語「Ｇ２」が追加される。そして、「猫」、「ご飯」、「Ｇ１」および「Ｇ２」を含む単語集合１７ａから（０，０，２，２，…）といったベクトルが生成される。また、テキスト１５ｂから「メール」と「会議」が抽出され、「メール」が属するグループＧ３を示すダミー語「Ｇ３」が追加され、「会議」が属するグループＧ４を示すダミー語「Ｇ４」が追加される。そして、「メール」、「会議」、「Ｇ３」および「Ｇ４」を含む単語集合１７ｂから（４，４，５，５，…）といったベクトルが生成される。
【００２７】
処理部１２は、特徴情報１８と特徴情報１９ａ，１９ｂとの間の比較に基づいて、テキスト１５ａ，１５ｂなどの検索対象テキストの中からテキスト１４に類似するテキストを検索する。例えば、処理部１２は、特徴情報１９ａ，１９ｂなどの検索対象テキストに対応する特徴情報の中から特徴情報１８に最も近似する特徴情報を検索する。特徴情報１８がハッシュ値のベクトルである場合、近似する特徴情報は、例えば、一致するハッシュ値の個数が最も多いベクトルである。処理部１２は、所定の近傍探索アルゴリズムによって最も近似する特徴情報を探索してもよい。例えば、処理部１２は、検索対象テキストに対応するベクトルから生成された二分探索用の探索木を記憶部１１に予め記憶しておき、探索木を辿ることで特徴情報１８に最も近似するベクトルを探索してもよい。
【００２８】
例えば、特徴情報１８がベクトル（０，１，２，２，…）であり、特徴情報１９ａがベクトル（０，０，２，２，…）であり、特徴情報１９ｂがベクトル（４，４，５，５，…）であるとする。この場合、特徴情報１８は特徴情報１９ｂよりも特徴情報１９ａに近いため、テキスト１４はテキスト１５ｂよりもテキスト１５ａに類似することになる。
【００２９】
処理部１２は、テキスト１４に類似するテキスト１５ａを出力してもよい。例えば、処理部１２は、類似テキスト検索装置１０に接続されたティスプレイにテキスト１５ａを表示させるなど、出力デバイスにテキスト１５ａを出力してもよいし、他の情報処理装置にテキスト１５ａを送信してもよい。また、処理部１２は、テキスト１５ａに対応付けられた返答テキストを、ディスプレイに表示させるなど出力デバイスに出力してもよいし、他の情報処理装置に送信してもよい。また、処理部１２は、テキスト１５ａに対応付けられた返答テキストを音声信号に変換して音声として再生してもよい。
【００３０】
ここで、テキスト１５ａはテキスト１４に含まれる単語と近い意味をもつ関連語を含んでおり、テキスト１４とテキスト１５ａはある程度類似していると言える。しかし、テキスト１４に含まれる単語とテキスト１５ａに含まれる単語の共通度を単純に評価した場合、共通する単語が存在しないためテキスト１５ａはテキスト１４と類似しないと判定されるおそれがある。また、関連語を単純に同一単語とみなした場合、テキスト１４とテキスト１５ａは使用している表現が異なるにもかかわらず、表現が同一であるテキストと同一視されてしまい、類似度が過大評価されるおそれがある。
【００３１】
これに対して、類似テキスト検索装置１０は、テキスト１４に含まれる元の単語に加えて、元の単語に対応する関連語のグループを示すダミー語を単語集合１６に追加し、単語集合１６から特徴情報１８を生成する。また、テキスト１５ａに含まれる元の単語に加えて、元の単語に対応する関連語のグループを示すダミー語が単語集合１７ａに追加され、単語集合１７ａから特徴情報１９ａが生成される。
【００３２】
よって、テキスト１４に含まれる単語とテキスト１５ａに含まれる単語が同一でなくても、両者の意味的な近さが評価される。また、単語集合１６，１７ａの中に元の単語が残っているため、使用している表現の違いも評価される。すなわち、テキスト１４とテキスト１５ａがある程度類似していることを特徴情報１８，１９ａによって表現することができる。その結果、類似するテキストの検索精度が向上する。また、単語集合１６から生成された特徴情報１８と単語集合１７ａから生成された特徴情報１９ａの間の比較によって類似テキストを検索でき、類似テキスト検索の速度を向上させることができる。
【００３３】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
第２の実施の形態の情報処理装置１００は、ユーザから問い合わせ発話を受け付け、問い合わせ発話に対応する適切な返答発話を出力する対話システムに使用される。情報処理装置１００は、クライアント装置であってもよいしサーバ装置であってもよい。
【００３４】
図２は、情報処理装置のハードウェア例を示すブロック図である。
情報処理装置１００は、バスに接続されたＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。情報処理装置１００は、第１の実施の形態の類似テキスト検索装置１０に対応する。ＣＰＵ１０１は、第１の実施の形態の処理部１２に対応する。ＲＡＭ１０２またはＨＤＤ１０３は、第１の実施の形態の記憶部１１に対応する。
【００３５】
ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、情報処理装置１００は複数のプロセッサを備えてもよい。複数のプロセッサの集合を「マルチプロセッサ」または単に「プロセッサ」と言うことがある。
【００３６】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に使用するデータを一時的に記憶する揮発性の半導体メモリである。なお、情報処理装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。
【００３７】
ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。なお、情報処理装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）など他の種類の記憶装置を備えてもよく、複数の記憶装置を備えてもよい。
【００３８】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、情報処理装置１００に接続されたディスプレイ１０４ａに画像を出力する。ディスプレイ１０４ａとしては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなど、任意の種類のディスプレイを使用することができる。
【００３９】
入力信号処理部１０５は、情報処理装置１００に接続された入力デバイス１０５ａから入力信号を受信する。入力デバイス１０５ａとして、マウス、タッチパネル、タッチパッド、キーボードなど、任意の種類の入力デバイスを使用できる。また、情報処理装置１００に複数の種類の入力デバイスが接続されてもよい。
【００４０】
媒体リーダ１０６は、記録媒体１０６ａに記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１０６ａとして、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体１０６ａから読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００４１】
通信インタフェース１０７は、ネットワーク１０７ａに接続され、ネットワーク１０７ａを介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチやルータなどの有線通信装置に接続される有線通信インタフェースでもよいし、基地局やアクセスポイントに接続される無線通信インタフェースでもよい。
【００４２】
次に、問い合わせ発話から返答発話を決定する方法について説明する。
図３は、発話テーブルの例を示す図である。
情報処理装置１００は、問い合わせと返答のサンプルを多数蓄積したデータベースとして、発話テーブル１４１を保持する。発話テーブル１４１は、発話ＩＤ、検索対象発話および返答発話の項目を含む。発話ＩＤは、検索対象発話を識別する識別子である。
【００４３】
検索対象発話は、問い合わせ発話のサンプルである。検索対象発話は、ユーザが口頭で発することがある文を示す文字列であり、２以上の単語を含むテキストである。検索対象発話は、比較的短い１つの文または少数の文によって構成される。返答発話は、検索対象発話に対応付けられている。ある検索対象発話に類似する問い合わせ発話が入力されたとき、当該検索対象発話に対応付けられた返答発話が出力される。返答発話は、ユーザに対して伝達されることがある文を示す文字列であり、２以上の単語を含むテキストである。返答発話は、比較的短い１つの文または少数の文によって構成される。
【００４４】
例えば、情報処理装置１００は、ユーザが口頭で発した問い合わせ発話を示す音声信号を受信し、音声認識により音声信号をテキストの問い合わせ発話に変換する。情報処理装置１００は、テキストの問い合わせ発話に類似する検索対象発話を判定し、判定した検索対象発話に対応する返答発話を選択する。情報処理装置１００は、テキストの返答発話を音声信号に変換して音声として返答発話を再生する。
【００４５】
次に、問い合わせ発話に類似する検索対象発話を探索する探索方法について説明する。情報処理装置１００は、Min-hash関数を用いて発話間の出現単語の共通度を評価する。
図４は、ハッシュ関数およびベクトルの例を示す図である。
【００４６】
一例として、情報処理装置１００は、問い合わせ発話３１を受け付ける。また、発話テーブル１４１に検索対象発話３２，３３が登録されている。また、情報処理装置１００は、Min-hash関数であるハッシュ関数３４〜３６を保持している。
【００４７】
問い合わせ発話３１は、単語として「大谷」、「ＬＡ」、「盗塁」、「メジャー」、「ボール」および「本塁打」を含む。検索対象発話３２は、単語として「松井」、「ＮＹ」、「三振」、「メジャー」、「ボール」および「本塁打」を含む。検索対象発話３３は、単語として「大谷」、「三振」、「太刀」、「戦国時代」、「関ヶ原」および「切腹」を含む。情報処理装置１００は、問い合わせ発話３１を受け付けたとき、ハッシュ関数３４〜３６を用いて問い合わせ発話３１からベクトル３７を生成する。また、情報処理装置１００は、ハッシュ関数３４〜３６を用いて検索対象発話３２から予めベクトル３８を生成して保持しておく。また、情報処理装置１００は、ハッシュ関数３４〜３６を用いて検索対象発話３３から予めベクトル３９を生成して保持しておく。
【００４８】
ハッシュ関数３４〜３６は、１つの問い合わせ発話または１つの検索対象発話に含まれる１つの単語集合から１つのハッシュ値を算出するMin-hash関数である。ハッシュ関数３４〜３６はそれぞれ、異なる単語に対して異なる整数を対応付けた対応関係をもつ。異なるハッシュ関数は異なる対応関係をもっている。例えば、情報処理装置１００は、検索対象発話３２，３３に出現し得る複数の単語をランダムに整列し、単語の列に対して０，１，２，…と連続する非負整数を割り当てることで、１つのハッシュ関数を生成する。ただし、複数の単語に対して不連続な整数を割り当てるようにしてもよい。
【００４９】
例えば、ハッシュ関数３４は、「メジャー」に整数０、「戦国時代」に整数１、「野球」に整数２を割り当てている。ハッシュ関数３５は、「切腹」に整数０、「歴史」に整数１、「本塁打」に整数２を割り当てている。ハッシュ関数３６は、「ＮＹ」に整数０、「ＬＡ」に整数１、「関ヶ原」に整数２を割り当てている。ハッシュ関数３４〜３６はそれぞれ、単語集合に含まれる２以上の単語に対応する２以上の整数の中から、最小の整数を選択し、選択した最小の整数をハッシュ値として出力する。
【００５０】
ベクトル３７は、問い合わせ発話３１の単語集合をハッシュ関数３４〜３６に入力することで算出された３つのハッシュ値を列挙した整数ベクトルである。問い合わせ発話３１に対して、ハッシュ関数３４は「メジャー」に対応する整数０を出力し、ハッシュ関数３５は「本塁打」に対応する整数２を出力し、ハッシュ関数３６は「ＬＡ」に対応する整数１を出力する。よって、ベクトル３７は（０，２，１）となる。
【００５１】
ベクトル３８は、検索対象発話３２の単語集合をハッシュ関数３４〜３６に入力することで算出された３つのハッシュ値を列挙した整数ベクトルである。検索対象発話３２に対して、ハッシュ関数３４は「メジャー」に対応する整数０を出力し、ハッシュ関数３５は「本塁打」に対応する整数２を出力し、ハッシュ関数３６は「ＮＹ」に対応する整数０を出力する。よって、ベクトル３８は（０，２，０）となる。
【００５２】
ベクトル３９は、検索対象発話３３の単語集合をハッシュ関数３４〜３６に入力することで算出された３つのハッシュ値を列挙した整数ベクトルである。検索対象発話３３に対して、ハッシュ関数３４は「戦国時代」に対応する整数１を出力し、ハッシュ関数３５は「切腹」に対応する整数０を出力し、ハッシュ関数３６は「関ヶ原」に対応する整数２を出力する。よって、ベクトル３８は（１，０，２）となる。
【００５３】
情報処理装置１００は、ベクトル３７とベクトル３８を比較することで、問い合わせ発話３１と検索対象発話３２の類似度を評価することができる。類似度は、ベクトル３７，３８の次元のうち整数が一致する次元の個数で表現される。ここでは、整数が一致しているか否かが重要であり、整数が異なる場合は整数の近さは重要でない。ベクトル３７とベクトル３８の間では、３次元のうち２次元で整数が一致している。同様に、情報処理装置１００は、ベクトル３７とベクトル３９を比較することで、問い合わせ発話３１と検索対象発話３３の類似度を評価することができる。ベクトル３７とベクトル３９の間では、３次元のうち１つの次元でも整数が一致していない。よって、問い合わせ発話３１は、検索対象発話３３よりも検索対象発話３２に類似していると判定できる。
【００５４】
任意のハッシュ関数が１つの問い合わせ発話と１つの検索対象発話に対して同一のハッシュ値を出力する確率は、問い合わせ発話の単語集合と検索対象発話の単語集合の間で共通する単語が出現する割合に一致する。共通する単語の割合をジャッカール係数と言うことがある。よって、異なるハッシュ関数が算出した複数のハッシュ値のうち一致するハッシュ値の割合を、ジャッカール係数の近似値として用いることが可能である。多数の検索対象発話に対応するベクトルを予め算出しておけば、受け付けた問い合わせ発話に類似する検索対象発話を高速に検索することが可能である。
【００５５】
例えば、問い合わせ発話３１と検索対象発話３２の間では、重複を除去した９個の単語（９種類の単語）のうち３個の単語が共通しているため、ジャッカール係数は０．３３となる。また、問い合わせ発話３１と検索対象発話３３の間では、重複を除去した１１個の単語のうち１個の単語が共通しているため、ジャッカール係数は０．０９となる。よって、ベクトル間で一致するハッシュ値の割合はジャッカール係数に近似している。
【００５６】
情報処理装置１００は、多数の検索対象発話に対応する多数のベクトルの中から、問い合わせ発話に対応するベクトルと最も一致度が高い１つのベクトルまたは一致度が高い少数のベクトルを検索できればよい。そこで、情報処理装置１００は、二分探索木を用いた近傍探索によって１つまたは少数のベクトルを探索する。
【００５７】
図５は、探索木の例を示す図である。
情報処理装置１００は、発話テーブル１４１に登録された検索対象発話から生成されたベクトルに基づいて、予め探索木１４２を生成して保持しておく。探索木１４２は、木構造に接続された複数のノードを含む。葉ノード以外の各ノードには２つの子ノードが接続されている。葉ノード以外の各ノードは、ベクトルの中の特定の次元に対する閾値をもつ。入力されたベクトルの中の特定の次元のハッシュ値が閾値以上である場合は右子ノードに進み、特定の次元のハッシュ値が閾値未満である場合は左子ノードに進む。このようにして、探索木１４２をルートノードから葉ノードに向かって辿る。
【００５８】
例えば、図５の例では、ルートノードは１次元目に対する閾値として１０をもつ。このため、１次元目のハッシュ値が１０以上であるベクトルが入力された場合はルートノードから右子ノードに進むことになり、１次元目のハッシュ値が１０未満であるベクトルが入力された場合はルートノードから左子ノードに進むことになる。
【００５９】
探索木１４２の葉ノードは、検索対象発話を指し示す。例えば、葉ノードは、検索対象発話のベクトルと当該検索対象発話を識別する発話ＩＤとを含む。ただし、葉ノードがベクトルを含まなくてもよい。２以上の検索対象発話のベクトルが互いに近似している場合、１つの葉ノードに２以上の検索対象発話が対応付けられることもある。ただし、検索対象発話を効率的に絞り込むため、１つの葉ノードは１つまたは少数の検索対象発話を指し示すことが好ましい。なお、探索木１４２の葉ノードはルートノードからの深さが同一でなくてもよく、探索に全ての次元のハッシュ値が使用されなくてもよい。
【００６０】
次に、問い合わせ発話と検索対象発話が、同一の単語を含まないものの関連する単語を含んでいる場合の問題について説明する。問い合わせ発話および検索対象発話は、話し言葉を用いた短文であるため、同一または類似の事象を多様な単語で表現することができ、問い合わせ発話と検索対象発話の間に同一の単語が出現する確率が全体的に低い。よって、単純に単語の共通度を評価する方法では、関連語を使用する問い合わせ発話と検索対象発話の間の類似度が適切に評価されないという問題がある。
【００６１】
図６は、ジャッカール係数の算出例を示す図である。
（Ａ）問い合わせ発話４１は、単語として「猫」および「ご飯」を含む。検索対象発話４２は、単語として「にゃんこ」および「えさ」を含む。「猫」と「にゃんこ」は類似する意味をもつ関連語であり、「ご飯」と「えさ」は類似する意味をもつ関連語である。しかし、単純に単語の同一性に基づきジャッカール係数を算出すると、問い合わせ発話４１と検索対象発話４２は同一の単語を含まないため、ジャッカール係数が０．００となる。このため、問い合わせ発話４１と検索対象発話４２は類似する内容を表している可能性が高いにもかかわらず、類似度が非常に低く判定されてしまう。
【００６２】
（Ｂ）問い合わせ発話４３は、単語として「猫」および「ご飯」を含む。検索対象発話４４は、単語として「にゃんこ」および「えさ」を含む。ここで、検索対象発話４４の「にゃんこ」は「猫」の関連語であるため、「にゃんこ」を「猫」と同一の単語であるとみなすとする。また、検索対象発話４４の「えさ」は「ご飯」の関連語であるため、「えさ」を「ご飯」と同一の単語であるとみなすとする。すると、問い合わせ発話４３と検索対象発話４４の間のジャッカール係数が１．００と算出される。しかし、問い合わせ発話４３と検索対象発話４４は異なる表現を使用しているため、類似度が過大評価されており、問い合わせ発話４３と同一の表現を使用する他の検索対象発話との区別が困難となる。
【００６３】
そこで、第２の実施の形態では以下のようにして類似度を評価する。
（Ｃ）問い合わせ発話４５は、単語として「猫」および「ご飯」を含む。検索対象発話４６は、単語として「にゃんこ」および「えさ」を含む。「猫」と「にゃんこ」が同一の関連語グループに属し、「ご飯」と「えさ」が同一の関連語グループに属する。
【００６４】
すると、「猫」が属する関連語グループに対応する仮想語ｓ１を問い合わせ発話４５の単語集合に追加し、「ご飯」が属する関連語グループに対応する仮想語ｓ２を問い合わせ発話４５の単語集合に追加する。仮想語は問い合わせ発話や検索対象発話に出現しない仮想的な単語であり、ダミー語やラベルと言うこともできる。「猫」および「ご飯」を残したまま仮想語ｓ１，ｓ２が追加される。また、「にゃんこ」が属する関連語グループに対応する仮想語ｓ１を検索対象発話４６の単語集合に追加し、「えさ」が属する関連語グループに対応する仮想語ｓ２を検索対象発話４６の単語集合に追加する。「にゃんこ」および「えさ」を残したまま仮想語ｓ１，ｓ２が追加される。
【００６５】
仮想語が追加された問い合わせ発話４５の単語集合と、仮想語が追加された検索対象発話４６の単語集合とを比較すると、６種類の単語のうち２種類の単語が共通するため、ジャッカール係数は０．３３と算出される。このように算出したジャッカール係数を、第２の実施の形態では拡張ジャッカール係数と言うことがある。拡張ジャッカール係数は、単語間の関連性（意味の類似性）を無視する場合のジャッカール係数よりも大きくなる。また、単語集合に元の単語を残したまま仮想語を追加するため、拡張ジャッカール係数は、関連語を同一視する場合のジャッカール係数よりも小さくなる。よって、異なる表現を使用する問い合わせ発話と検索対象発話の間の類似性を適切に評価することができる。
【００６６】
情報処理装置１００は、仮想語も独立した単語として取り扱って複数のハッシュ関数を生成しておく。情報処理装置１００は、発話テーブル１４１に登録された検索対象発話から、仮想語を追加した単語集合を生成してハッシュ関数に入力し、仮想語の影響を反映したベクトルを算出する。情報処理装置１００は、仮想語の影響を反映したベクトルから探索木１４２を生成する。問い合わせ発話が入力されると、情報処理装置１００は、問い合わせ発話から、仮想語を追加した単語集合を生成してハッシュ関数に入力し、仮想語の影響を反映したベクトルを算出する。情報処理装置１００は、探索木１４２を用いて、問い合わせ発話のベクトルに近似する検索対象発話のベクトルを探す。このように、情報処理装置１００は、ハッシュ関数と単語集合を拡張することで、関連語を考慮しない探索方法を流用して高速に類似の検索対象発話を検索することができる。
【００６７】
図７は、類似度の閾値と検索対象発話のヒット数との関係例を示すグラフである。
グラフ５０は、問い合わせ発話と検索対象発話の類似度の閾値と、類似度が閾値より大きい検索対象発話の数（ヒット数）との間の関係を示す。類似度は、問い合わせ発話のベクトルと検索対象発話のベクトルの間でハッシュ値が一致する次元の数である。
【００６８】
（Ａ）関連語を考慮せずにベクトルを算出する方法では、問い合わせ発話と各検索対象発話の類似度が全体として低く算出される。よって、類似度の閾値とヒット数との間の関係は曲線５１のようになる。すなわち、類似度の閾値を低く設定してもヒット数が少なくなり、類似する検索対象発話の検索漏れが多くなる。
【００６９】
（Ｂ）関連語を同一視してベクトルを算出する方法では、問い合わせ発話と各検索対象発話の類似度が全体として高く算出される。よって、類似度の閾値とヒット数との間の関係は曲線５２のようになる。すなわち、類似度の閾値を高く設定してもヒット数が多くなり、類似する検索対象発話を効率的に絞り込むことが難しい。
【００７０】
（Ｃ）元の単語を残しつつ関連語グループを示す仮想語を追加してベクトルを算出する方法では、問い合わせ発話と各検索対象発話の類似度が上記２つの方法の中間の値をとる。よって、類似度の閾値とヒット数との間の関係は曲線５３のようになる。仮想語が追加されることで、一致するハッシュ値の個数が若干増える。一方、元の単語が残っているため、一致するハッシュ値の個数が増え過ぎることを抑制できる。その結果、問い合わせ発話に類似する検索対象発話を効率的に絞り込むことができる。
【００７１】
関連語グループは予め定義されている。
図８は、関連語テーブルの例を示す図である。
情報処理装置１００は、関連語テーブル１４３を保持している。関連語テーブル１４３は、関連語辞書と言うこともできる。関連語テーブル１４３は、グループＩＤおよび関連語の項目を含む。グループＩＤは、関連語グループを識別する識別子である。１つ関連語グループに対して１つの仮想語が割り当てられる。関連語の項目には、同一の関連語グループに属する２以上の単語が列挙される。同一の関連語グループに属する単語は、類似する意味として使用されることがある単語である。
【００７２】
「猫」および「にゃんこ」は同一の関連語グループに属する。そこで、例えば、情報処理装置１００は、「猫」および「にゃんこ」に同一の仮想語ｓ１を割り当てる。また、「ご飯」および「えさ」は同一の関連語グループに属する。そこで、例えば、情報処理装置１００は、「ご飯」および「えさ」に同一の仮想語ｓ２を割り当てる。
【００７３】
なお、関連語テーブル１４３に登録されていない単語は、何れの関連語グループにも属さず、関連する他の単語をもたない。後述するように、第２の実施の形態では、関連語が存在しない単語に対しても一意な仮想語を追加してハッシュ値を算出する。これは、関連語が存在しない単語集合からは同一のジャッカール係数と拡張ジャッカール係数とが算出されるようにし、ジャッカール係数と拡張ジャッカール係数の整合性を維持するためである。ただし、関連語が存在しない単語に対して仮想語を割り当てないことも可能である。その場合であっても、拡張ジャッカール係数は、関連語を考慮しない場合のジャッカール係数以上の値をとり、関連語を同一視する場合のジャッカール係数以下の値をとる。
【００７４】
ここで、ジャッカール係数やハッシュ関数の数学的側面について説明する。
第２の実施の形態で使用するハッシュ関数はMin-hash関数であり、単語集合を整数に変換する写像である。複数のハッシュ関数によって近似するベクトルが生成される問い合わせ発話と検索対象発話は、共通する単語の出現割合が高い発話である。一方の発話（例えば、１つの検索対象発話）の単語集合をＡ、他方の発話（例えば、問い合わせ発話）の単語集合をＢとすると、ジャッカール係数は数式（１）のように定義される。単語集合Ａ，Ｂは出現する単語の種類を示し、同じ単語が２回以上出現しても重複カウントしない。
【００７５】
【数１】
2020004107.tif 000003
【００７６】
１つのハッシュ関数のハッシュ値が２つのベクトルの間で一致している場合、当該ハッシュ値に対応する単語が両方の発話に出現している。一致していない場合、小さい方のハッシュ値に対応する単語が一方の発話にのみ出現している。前述のように、１つのハッシュ関数のハッシュ値が一致する確率はジャッカール係数に等しいため、複数のハッシュ関数についての一致割合によってジャッカール係数を近似できる。単語集合Ａ，Ｂに含まれる単語の数に依存しない所定回数のハッシュ値計算によって近似値が得られる。
【００７７】
ｎを検索対象発話の数、ｍを発話１つ当たりの平均の単語数、ｋをハッシュ関数の数とする。すると、予め検索対象発話のベクトルを計算する計算量はＯ（ｋｍｎ）となる。１つの問い合わせ発話のベクトルを計算する計算量はＯ（ｋｍ）となり、このベクトルを用いた近傍探索の計算コストはＯ（ｌｏｇ（ｎ））となる。ハッシュ関数は予めランダムにｋ個生成される。ｋをＯ（ｌｏｇ（ｎ））とすると、異なる検索対象発話から同一のハッシュ値が算出される衝突確率を十分に小さくすることができる。
【００７８】
これに対して、ジャッカール係数とハッシュ関数を拡張する。単語集合Ａ，Ｂの中に関連語が存在しない場合、拡張ジャッカール係数はジャッカール係数に等しい。関連語が存在する場合、拡張ジャッカール係数は、関連語を異なる単語とみなした際のジャッカール係数よりも大きく、関連語を同一単語とみなした際のジャッカール係数よりも小さい。ハッシュ値の一致確率が拡張ジャッカール係数に等しくなるように、単語集合Ａ，Ｂに仮想語を追加すると共に、仮想語に対しても整数を割り当てるようハッシュ関数を拡張する。
【００７９】
検索対象発話に出現し得る単語の集合をＷとし、単語集合Ｗに含まれない仮想語の集合をＷ’とする。単語集合Ｗに属する任意の単語ａに対して、仮想語集合Ｗ’に属する一意な仮想語ｓｉが割り当てられる。同一の関連語グループに属する単語に対しては同一の仮想語が割り当てられる。何れの関連語グループにも属さない単語に対しては、他の単語に対して使用されない仮想語が割り当てられる。数式（２）に示す関数ｆはＷからＷ×Ｗ’への写像であり、１つの単語から当該単語と仮想語の組を返す。
【００８０】
【数２】
2020004107.tif 000004
【００８１】
拡張ジャッカール係数Ｊ’は、ジャッカール係数Ｊの定義および関数ｆを用いて数式（３）のように定義される。関数ｆによって、単語集合Ａに含まれる各単語に対応する仮想語が単語集合Ａに挿入され、単語集合Ｂに含まれる各単語に対応する仮想語が単語集合Ｂに挿入される。そして、仮想語を挿入した単語集合に対してジャッカール係数Ｊを算出したものが拡張ジャッカール係数Ｊ’となる。元の単語集合Ａ，Ｂに関連語が含まれない場合、Ｊ’（Ａ，Ｂ）＝Ｊ（Ａ，Ｂ）である。
【００８２】
【数３】
2020004107.tif 000005
【００８３】
ハッシュ関数を拡張するにあたり、ハッシュ関数毎に数式（４）のように関数ｈ’を定義する。関数ｈは、単語集合Ｗに属する単語ａを整数ｎに変換するものであり、拡張前のハッシュ関数で使用される。整数の集合をＮとすると、関数ｈはＷからＮへの写像である。関数ｈ’は、単語集合Ｗに属する単語ａまたは仮想語集合Ｗ’に属する仮想語ａを整数ｎに変換するものであり、拡張後のハッシュ関数で使用される。ｎを整数集合Ｎの中の任意の整数とし、Ｎ’＝｛ｎ＋ｍａｘＮ＋１｝とすると、関数ｈ’はＷ∪Ｗ’からＮ∪Ｎ’への写像である。整数集合Ｎ’は、関数ｈの値域である整数集合Ｎを２倍に拡張したときの拡張部分を示している。これは、仮想語集合Ｗ’のサイズは単語集合Ｗのサイズ以下であるためである。関数ｅは、仮想語集合Ｗ’に属する仮想語ａを単語集合Ｗに属する単語に変換するものであり、Ｗ’からＷへの単射である。関数ｇは、単語または仮想語と整数との対応関係を入れ替えるものであり、Ｎ∪Ｎ’からＮ∪Ｎ’への全単射である。
【００８４】
【数４】
2020004107.tif 000006
【００８５】
すなわち、情報処理装置１００は、ハッシュ関数を拡張するにあたり、既存の単語に割り当てられた整数よりも大きい整数を仮想語に割り当てる。仮想語に割り当てる整数は関数ｅ，ｈを用いて決定される。ある仮想語ａから関数ｅによって一意な既存の単語が選択され、関数ｈによってその単語に対応付けられた整数ｈ（ｅ（ａ））に、関数ｈの値域の最大値ｍａｘＮと１を加えたものが、仮想語ａに割り当てられる。そして、情報処理装置１００は、既存の単語と整数との対応関係および仮想語と整数との対応関係を、関数ｇによってシャッフルして新たな対応関係を生成する。
【００８６】
なお、関数ｅは、入力された仮想語から、当該仮想語が示す関連語グループに属する１つの単語を選択するものであってもよいし、単語集合Ｗに属する単語をランダムに選択するものであってもよい。また、割り当てる整数を入れ替える関数ｇは、ランダムに生成してもよい。また、関数ｅや関数ｇは、複数のハッシュ関数の間で共通に使用してもよいし、ハッシュ関数毎にランダムに生成するようにしてもよい。
【００８７】
上記の関数ｈ’から、数式（５）のように拡張後のハッシュ関数Ｈ’が定義される。ハッシュ関数Ｈ’は、ｆ（Ａ）に含まれる単語および仮想語それぞれに対応する整数を関数ｈ’によって算出し、その中から最小の整数を選択するものである。なお、関数ｈ’の定義域のサイズは関数ｈの定義域のサイズの高々２倍である。関数ｈ’の値域を１桁大きくするか、または、ハッシュ関数の数ｋを１つ増やすことで、ハッシュ関数Ｈ’のもとでハッシュ値が衝突する確率を元のハッシュ関数と同等に維持することができる。
【００８８】
【数５】
2020004107.tif 000007
【００８９】
次に、仮想語を考慮したベクトルの算出例を説明する。
図９は、単語集合からベクトルを算出する例を示す図である。
表６０は、単語集合Ａに対応するベクトルと単語集合Ｂに対応するベクトルを算出して比較する過程を示している。単語集合Ａは「猫」と「ご飯」を含み、更に仮想語「ｓ１」と「ｓ２」が挿入されている。単語集合Ｂは「にゃんこ」と「えさ」を含み、更に仮想語「ｓ１」と「ｓ２」が挿入されている。また、単語および仮想語と整数との対応関係が異なる１２個のハッシュ関数が定義されており、１２個のハッシュ値を列挙したものが、単語集合Ａに対応するベクトルおよび単語集合Ｂに対応するベクトルになる。
【００９０】
ハッシュ関数Ｈ’１で使用される関数ｈ’１は、「猫」に０、「ご飯」に１、「にゃんこ」に２、「えさ」に３、「ｓ１」に４、「ｓ２」に５を割り当てている。よって、単語集合Ａに対するハッシュ値は「猫」に対応する０になり、単語集合Ｂに対するハッシュ値は「にゃんこ」に対応する２になる。また、ハッシュ関数Ｈ’２で使用される関数ｈ’２は、「猫」に１、「ご飯」に０、「にゃんこ」に５、「えさ」に４、「ｓ１」に３、「ｓ２」に２を割り当てている。よって、単語集合Ａに対するハッシュ値は「ご飯」に対応する０になり、単語集合Ｂに対するハッシュ値は「ｓ２」に対応する２になる。
【００９１】
また、ハッシュ関数Ｈ’５で使用される関数ｈ’５は、「猫」に２、「ご飯」に３、「にゃんこ」に４、「えさ」に５、「ｓ１」に０、「ｓ２」に１を割り当てている。よって、単語集合Ａに対するハッシュ値は「ｓ１」に対応する０になり、単語集合Ｂに対するハッシュ値は「ｓ１」に対応する０になる。このようにして、単語集合Ａからはベクトル（０，０，２，２，０，０，０，１，１，０，０，０）が算出される。単語集合Ｂからはベクトル（２，２，０，０，０，０，１，０，０，０，０，１）が算出される。
【００９２】
元の単語集合Ａ，Ｂの間には共通する単語が存在しないものの、１２個のハッシュ関数のうちハッシュ関数Ｈ’５，Ｈ’６，Ｈ’１０，Ｈ’１１のハッシュ値が一致しており、ハッシュ値の一致割合が０．３３になっている。仮に、仮想語を使用しない場合はハッシュ値の一致割合が０．００になる。よって、発話の類似性を適切に評価することができる。
【００９３】
図１０は、問い合わせ発話に対応する返答発話の選択例を示す図である。
前述のように、情報処理装置１００は、蓄積された検索対象発話の中から問い合わせ発話に最も類似する検索対象発話を選択し、選択した検索対象発話に対応する返答発話を出力する。一例として、検索対象発話７１〜７３が蓄積されている。
【００９４】
検索対象発話７１は「メールを調べて」というメッセージであり、検索対象発話７２は「スケジュールの調整」というメッセージであり、検索対象発話７３は「打ち合わせを調整したい」というメッセージである。情報処理装置１００は予め、検索対象発話７１からベクトル７４を生成し、検索対象発話７２からベクトル７５を生成し、検索対象発話７３からベクトル７６を生成しておく。ベクトル７４は（０，０，１，１，２，２，…）という整数の列であり、ベクトル７５は（２，２，０，０，１，１，…）という整数の列であり、ベクトル７５は（１，２，２，２，１，１，…）という整数の列である。
【００９５】
情報処理装置１００は、問い合わせ発話７７を受け付ける。問い合わせ発話７７は、「会議を調整したい」というメッセージである。情報処理装置１００は、問い合わせ発話７７からベクトル７８を生成する。ベクトル７８は、（１，１，２，２，１，１，…）という整数の列である。ベクトル７４〜７６のうちベクトル７８に最も近似するものはベクトル７６である。そこで、情報処理装置１００は、検索対象発話７３を選択し、検索対象発話７３に対応する返答発話７９を出力する。返答発話７９は、問い合わせ発話７７に対する応答であり、「スケジュールを調整します」というメッセージである。「会議」と「打ち合わせ」が類似する意味をもつ関連語であることが予め登録されていれば、情報処理装置１００は、検索対象発話７３が問い合わせ発話７７に類似すると判定できる。
【００９６】
なお、探索木１４２の葉ノードに単一の検索対象発話が対応付けられている場合など、ベクトルを用いた近傍探索によって単一の検索対象発話が検索された場合、情報処理装置１００は当該検索対象発話に対応する返答発話を出力すればよい。一方、探索木１４２の葉ノードに２以上の検索対象発話が対応付けられている場合など、ベクトルを用いた近傍探索によって２以上の検索対象発話が検索された場合、情報処理装置１００は何らかの方法で検索対象発話を１つに絞り込むことが考えられる。例えば、情報処理装置１００は、ベクトルを用いた簡易的な類似判定とは異なる詳細分析により検索対象発話を絞り込む。
【００９７】
次に、情報処理装置１００の機能および処理手順について説明する。
図１１は、情報処理装置の機能例を示すブロック図である。
情報処理装置１００は、発話データベース１２１、関連語記憶部１２２、ハッシュ関数記憶部１２３およびインデックス記憶部１２４を有する。これらの記憶部は、例えば、ＲＡＭ１０２またはＨＤＤ１０３の記憶領域を用いて実現される。また、情報処理装置１００は、ハッシュ関数生成部１３１、インデックス生成部１３２、問い合わせ受信部１３３、ハッシュ値算出部１３４、検索部１３５および返答出力部１３６を有する。これらの処理部は、例えば、ＣＰＵ１０１が実行するプログラムを用いて実現される。
【００９８】
発話データベース１２１は、複数の検索対象発話とそれに対応する複数の返答発話とが登録された発話テーブル１４１を記憶する。検索対象発話と返答発話の組は、事前に登録されていてもよいし、情報処理装置１００を使用するユーザとの対話を通じて追加されてもよいし、ネットワークから自動的に収集されてもよい。
【００９９】
関連語記憶部１２２は、関連語グループを示す関連語テーブル１４３を記憶する。関連語グループは、事前に登録されていてもよいし、情報処理装置１００を使用するユーザとの対話を通じて追加されてもよいし、ネットワークから自動的に収集されてもよい。
【０１００】
ハッシュ関数記憶部１２３は、異なる複数のハッシュ関数を記憶する。各ハッシュ関数は、検索対象発話に出現し得る単語および検索対象発話に出現しない仮想語それぞれに対して一意な整数を対応付ける対応関係をもち、単語集合を受け付けて１つのハッシュ値を出力する。異なるハッシュ関数は異なる対応関係をもつ。
【０１０１】
インデックス記憶部１２４は、問い合わせ発話に類似する検索対象発話を検索するためのインデックスとして探索木１４２を記憶する。探索木１４２は、複数のハッシュ関数を用いて検索対象発話から算出されたベクトルに基づいて生成される。
【０１０２】
ハッシュ関数生成部１３１は、発話データベース１２１に記憶された検索対象発話と関連語記憶部１２２に記憶された関連語テーブル１４３に基づいて、複数のハッシュ関数を生成し、生成した複数のハッシュ関数をハッシュ関数記憶部１２３に格納する。
【０１０３】
まず、ハッシュ関数生成部１３１は、検索対象発話で使用されている単語を抽出し、抽出した単語をランダムに整列して拡張前のハッシュ関数を生成する。また、ハッシュ関数生成部１３１は、関連語テーブル１４３に登録された関連語グループと関連語をもたない単語に対して仮想語を割り当てる。ハッシュ関数生成部１３１は、仮想語に対しても整数が割り当てられるようにハッシュ関数を拡張する。
【０１０４】
インデックス生成部１３２は、発話データベース１２１に記憶された検索対象発話とハッシュ関数記憶部１２３に記憶されたハッシュ関数に基づいて、探索木１４２を生成し、生成した探索木１４２をインデックス記憶部１２４に格納する。
【０１０５】
まず、インデックス生成部１３２は、検索対象発話毎に単語集合を抽出し、各単語に対応する仮想語を単語集合に追加する。インデックス生成部１３２は、仮想語を追加した単語集合を複数のハッシュ関数それぞれに入力して、ハッシュ値のベクトルを算出する。インデックス生成部１３２は、複数の検索対象発話に対応する複数のベクトルを効率的に検索できるように探索木１４２を生成する。例えば、インデックス生成部１３２は、ベクトルの中の１つの次元に着目し、ベクトルの集合が二分割されるように当該次元のハッシュ値の閾値を決定することを繰り返す。インデックス生成部１３２は、探索木１４２の葉ノードにはできる限り単一のベクトルが対応付けられるように中間ノードを生成する。
【０１０６】
問い合わせ受信部１３３は、問い合わせ発話を受信する。問い合わせ受信部１３３は、ユーザから文字列として入力された問い合わせ発話を受信してもよいし、ユーザが口頭で発した問い合わせ発話の音声信号を文字列に変換してもよい。また、問い合わせ受信部１３３は、他の情報処理装置から文字列または音声信号を受信してもよい。
【０１０７】
ハッシュ値算出部１３４は、ハッシュ関数記憶部１２３に記憶された複数のハッシュ関数に基づいて、問い合わせ発話に対応するベクトルを生成する。まず、ハッシュ値算出部１３４は、問い合わせ発話から単語集合を抽出し、各単語に対応する仮想語を単語集合に追加する。ハッシュ値算出部１３４は、仮想語を追加した単語集合を複数のハッシュ関数それぞれに入力して、ハッシュ値のベクトルを算出する。
【０１０８】
検索部１３５は、インデックス記憶部１２４に記憶された探索木１４２と問い合わせ発話のベクトルに基づいて、近傍探索により問い合わせ発話に最も類似する検索対象発話を検索する。問い合わせ発話に最も類似する検索対象発話は、ベクトル同士を比較したときにハッシュ値が一致する次元が最も多い検索対象発話である。検索部１３５は、問い合わせ発話のベクトルの中の特定の次元のハッシュ値と閾値とを比較しながら、探索木１４２をルートノードから葉ノードに向かって辿り、特定の葉ノードに到達する。検索部１３５は、到達した葉ノードに対応する検索対象発話を選択する。なお、到達した葉ノードに２以上の検索対象発話が対応付けられている場合、すなわち、探索木１４２では検索対象発話を１つに絞り込めない場合、他の方法で検索対象発話を１つ選択する。
【０１０９】
返答出力部１３６は、選択された検索対象発話に対応付けられた返答発話を出力する。返答出力部１３６は、返答発話の文字列をディスプレイ１０４ａに表示してもよいし、返答発話を音声信号に変換してスピーカーにより音声を再生してもよい。また、返答出力部１３６は、他の情報処理装置に文字列または音声信号を送信してもよい。
【０１１０】
図１２は、インデックス生成の手順例を示すフローチャートである。
（Ｓ１０）ハッシュ関数生成部１３１は、発話テーブル１４１に登録された複数の検索対象発話に含まれる単語を収集して単語集合Ｗを抽出する。
【０１１１】
（Ｓ１１）ハッシュ関数生成部１３１は、単語集合Ｗに含まれる単語をランダムに整列し、単語の列の先頭から末尾に向かって整数を小さい順に割り当てる。ハッシュ関数生成部１３１は、これをｋ回繰り返してｋ個のハッシュ関数Ｈを生成する。
【０１１２】
（Ｓ１２）ハッシュ関数生成部１３１は、単語集合Ｗに含まれる単語ｗを１つ選択し、選択した単語ｗに対応するフラグｆｗを０に初期化する。
（Ｓ１３）ハッシュ関数生成部１３１は、ステップＳ１２で選択した単語ｗを関連語テーブル１４３から検索し、単語ｗが何れかの関連語グループに属するか、すなわち、単語ｗに類似する意味をもつ関連語が存在するか判断する。関連語がある場合はステップＳ１４に進み、関連語がない場合はステップＳ１５に進む。
【０１１３】
（Ｓ１４）ハッシュ関数生成部１３１は、フラグｆｗを１に更新する。
（Ｓ１５）ハッシュ関数生成部１３１は、単語集合Ｗの中にステップＳ１２でまだ選択していない単語ｗがあるか判断する。未選択の単語ｗがある場合はステップＳ１２に進み、未選択の単語ｗがない場合はステップＳ１６に進む。
【０１１４】
（Ｓ１６）ハッシュ関数生成部１３１は、関連語テーブル１４３に登録された関連語グループそれぞれに対して一意な仮想語ｓを割り当てる。また、ハッシュ関数生成部１３１は、ｆｗ＝０である単語それぞれに対して一意な仮想語ｓを割り当てる。ここで割り当てる仮想語ｓは、単語集合Ｗに含まれないダミー語ないしラベルであり、関連語グループおよびｆｗ＝０である単語の間で重複しない。仮想語ｓは「ｓ１」のような記号でもよい。
【０１１５】
（Ｓ１７）ハッシュ関数生成部１３１は、ステップＳ１１で生成したｋ個のハッシュ関数Ｈの中から１つのハッシュ関数Ｈを選択する。
（Ｓ１８）ハッシュ関数生成部１３１は、単語集合Ｗから単語ｗを１つ選択する。
【０１１６】
（Ｓ１９）ハッシュ関数生成部１３１は、ステップＳ１７で選択したハッシュ関数Ｈにおいて、ステップＳ１８で選択した単語ｗに対応付けられている整数ｈ（ｗ）を特定する。そして、ハッシュ関数生成部１３１は、シャッフル用の所定の関数ｇを用いて、単語ｗに対応付ける新たな整数ｈ’（ｗ）＝ｇ（ｈ（ｗ））を算出する。
【０１１７】
（Ｓ２０）ハッシュ関数生成部１３１は、単語集合Ｗの中にステップＳ１８でまだ選択していない単語ｗがあるか判断する。未選択の単語ｗがある場合はステップＳ１８に進み、未選択の単語ｗがない場合はステップＳ２１に進む。
【０１１８】
図１３は、インデックス生成の手順例を示すフローチャート（続き）である。
（Ｓ２１）ハッシュ関数生成部１３１は、ステップＳ１６で割り当てた仮想語の集合（仮想語集合Ｗ’）の中から仮想語ｓを１つ選択する。
【０１１９】
（Ｓ２２）ハッシュ関数生成部１３１は、仮想語を既出の単語に変換する所定の関数ｅを用いて、ステップＳ２１で選択した仮想語ｓに対応する単語ｅ（ｓ）を特定する。単語ｅ（ｓ）は、仮想語ｓに対応する関連語グループの中の１つの単語または仮想語ｓに対応する単一の単語でもよく、単語集合Ｗの中からランダムに選択されたものでもよい。ハッシュ関数生成部１３１は、ステップＳ１７で選択したハッシュ関数Ｈにおいて、単語ｅ（ｓ）に対応付けられている整数ｈ（ｅ（ｓ））を特定する。ハッシュ関数生成部１３１は、シャッフル用の所定の関数ｇを用いて、仮想語ｓに対応付ける新たな整数ｈ’（ｓ）＝ｇ（ｈ（ｅ（ｓ））＋ｍａｘＮ＋１）を算出する。なお、ｍａｘＮはハッシュ関数Ｈが出力し得るハッシュ値（値域）の最大値である。
【０１２０】
（Ｓ２３）ハッシュ関数生成部１３１は、仮想語集合Ｗ’の中にステップＳ２１でまだ選択していない仮想語ｓがあるか判断する。未選択の仮想語ｓがある場合はステップＳ２１に進み、未選択の仮想語ｓがない場合はステップＳ２４に進む。
【０１２１】
（Ｓ２４）ハッシュ関数生成部１３１は、ステップＳ１９，Ｓ２２の結果から、ステップＳ１７で選択したハッシュ関数Ｈに対応する拡張後のハッシュ関数Ｈ’を決定する。
（Ｓ２５）ハッシュ関数生成部１３１は、ステップＳ１７でまだ選択していないハッシュ関数Ｈがあるか判断する。未選択のハッシュ関数Ｈがある場合はステップＳ１７に進み、未選択のハッシュ関数Ｈがない場合はステップＳ２６に進む。
【０１２２】
（Ｓ２６）インデックス生成部１３２は、発話テーブル１４１に登録された複数の検索対象発話の中から検索対象発話を１つ選択する。
（Ｓ２７）インデックス生成部１３２は、ステップＳ２６で選択した検索対象発話に含まれる単語を抽出し、抽出した単語の集合である単語集合Ａを生成する。
【０１２３】
（Ｓ２８）インデックス生成部１３２は、単語集合Ａに含まれる単語それぞれに対応する仮想語を判定し、判定した仮想語を単語集合Ａに追加する。何れかの関連語グループに属する単語には、当該関連語グループに対してステップＳ１６で割り当てられた仮想語が追加される。何れの関連語グループにも属さない単語（関連語がない単語）には、当該単語に対してステップＳ１６で割り当てられた仮想語が追加される。
【０１２４】
（Ｓ２９）インデックス生成部１３２は、仮想語を追加した単語集合Ａを、ステップＳ２４で決定された複数のハッシュ関数Ｈ’にそれぞれ入力し、複数のハッシュ値を求める。各ハッシュ関数Ｈ’は、単語集合Ａに含まれる元の単語および仮想語それぞれに対応する整数を判定し、最小の整数をハッシュ値として出力する。インデックス生成部１３２は、複数のハッシュ値を列挙したベクトルを算出する。
【０１２５】
（Ｓ３０）インデックス生成部１３２は、ステップＳ２６でまだ選択していない検索対象発話があるか判断する。未選択の検索対象発話がある場合はステップＳ２６に進み、未選択の検索対象発話がない場合はステップＳ３１に進む。
【０１２６】
（Ｓ３１）インデックス生成部１３２は、ステップＳ２９で算出した複数のベクトルから、検索対象発話のインデックスとしての探索木１４２を生成する。
図１４は、発話検索の手順例を示すフローチャートである。
【０１２７】
（Ｓ４０）問い合わせ受信部１３３は、問い合わせ発話を受信する。
（Ｓ４１）ハッシュ値算出部１３４は、ステップＳ４０で受信した問い合わせ発話に含まれる単語を抽出し、抽出した単語の集合である単語集合Ｂを生成する。
【０１２８】
（Ｓ４２）ハッシュ値算出部１３４は、単語集合Ｂに含まれる単語それぞれに対応する仮想語を判定し、判定した仮想語を単語集合Ｂに追加する。何れかの関連語グループに属する単語には、当該関連語グループに対してステップＳ１６で割り当てられた仮想語が追加される。何れの関連語グループにも属さない単語（関連語がない単語）には、当該単語に対してステップＳ１６で割り当てられた仮想語が追加される。
【０１２９】
（Ｓ４３）ハッシュ値算出部１３４は、仮想語を追加した単語集合Ｂを、ステップＳ２４で決定された複数のハッシュ関数Ｈ’にそれぞれ入力し、複数のハッシュ値を求める。各ハッシュ関数Ｈ’は、単語集合Ｂに含まれる元の単語および仮想語それぞれに対応する整数を判定し、最小の整数をハッシュ値として出力する。ハッシュ値算出部１３４は、複数のハッシュ値を列挙したベクトルを算出する。
【０１３０】
（Ｓ４４）検索部１３５は、ステップＳ３１で生成された探索木１４２とステップＳ４３で算出されたベクトルとを照合して、最も類似する検索対象発話を判定する。
（Ｓ４５）返答出力部１３６は、発話テーブル１４１からステップＳ４４の検索対象発話に対応付けられた返答発話を取得し、取得した返答発話を出力する。
【０１３１】
第２の実施の形態の情報処理装置１００によれば、対話システムを実現するために、問い合わせ発話に類似する検索対象発話がデータベースの中から検索される。このとき、各発話に含まれる単語集合から複数のMin-hash関数によりハッシュ値のベクトルが算出され、ベクトル同士の近さによって発話の類似度が評価される。よって、多数の検索対象発話の中から問い合わせ発話に類似するものを高速に検索することができる。
【０１３２】
また、関連語グループを示す関連語辞書を参照して、単語集合に含まれる元の単語を残したまま、当該単語が属する関連語グループを示す仮想語が単語集合に追加される。また、元の単語と仮想語とに異なる整数が割り当てられるように複数のMin-hash関数が拡張される。そして、仮想語を追加した単語集合と拡張した複数のMin-hash関数によりベクトルが算出される。これにより、問い合わせ発話と検索対象発話が同一の単語を含まないものの近い意味をもつ関連語を含む場合に、両者の類似度を適切に評価することができる。
【０１３３】
例えば、単語間の意味の近さを無視する場合よりも類似度が高く評価され、関連語を同一視する場合よりも類似度が低く評価される。その結果、異なる表現を使用する問い合わせ発話と検索対象発話の類似度を適切に評価することができ、問い合わせ発話に類似する検索対象発話を効率的に絞り込むことが可能となる。また、Min-hash関数のハッシュ値のベクトルを使用するため、検索の高速性を維持することができる。
【符号の説明】
【０１３４】
１０  類似テキスト検索装置
１１  記憶部
１２  処理部
１３  関連語辞書
１４，１５ａ，１５ｂ  テキスト
１６，１７ａ，１７ｂ  単語集合
１８，１９ａ，１９ｂ  特徴情報
【図１】
2020004107.tif 000008
【図２】
2020004107.tif 000009
【図３】
2020004107.tif 000010
【図４】
2020004107.tif 000011
【図５】
2020004107.tif 000012
【図６】
2020004107.tif 000013
【図７】
2020004107.tif 000014
【図８】
2020004107.tif 000015
【図９】
2020004107.tif 000016
【図１０】
2020004107.tif 000017
【図１１】
2020004107.tif 000018
【図１２】
2020004107.tif 000019
【図１３】
2020004107.tif 000020
【図１４】
2020004107.tif 000021