サジェスチョンクエリ抽出装置及び方法、並びにプログラム
【課題】ジェネリックパターンの存在に起因して生ずる意味ドリフトを抑制し、サジェスチョンクエリの抽出の精度の向上を図ること。
【解決手段】インスタンスパターン行列生成部６２のうち、正規化自己相互情報量演算部７１は、インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する。エッジカット部７２は、正規化自己相互情報量の値が閾値ｔｈ以下である要素のエッジを削除する。正規化ラプラシアン行列演算部６３は、このようなインスタンスパターン行列生成部６２によって生成されたインスタンスパターン行列を用いて、正規化ラプラシアン行列を演算し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。
【解決手段】インスタンスパターン行列生成部６２のうち、正規化自己相互情報量演算部７１は、インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する。エッジカット部７２は、正規化自己相互情報量の値が閾値ｔｈ以下である要素のエッジを削除する。正規化ラプラシアン行列演算部６３は、このようなインスタンスパターン行列生成部６２によって生成されたインスタンスパターン行列を用いて、正規化ラプラシアン行列を演算し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サジェスチョンクエリ抽出装置及び方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来のＷｅｂページ検索では、ユーザによりクエリが入力されると、Ｗｅｂページ上の検索エンジンによって、複数のＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）を含む検索結果がユーザに提示される。
【０００３】
さらに、近年のＷｅｂページ検索では、検索結果の提示のみならず、入力されたクエリと関連するクエリが、代替クエリの候補として示唆される。このようなＷｅｂページ検索において代替クエリの候補として示唆されるクエリは、「サジェスチョンクエリ」と呼ばれている。
【０００４】
一般的には、サジェスチョンクエリとして、クエリと構成要素（単語ならば語形）が類似するクエリが提示される。例えば、ユーザが、クエリとして「ホテル」と入力すべきところを誤って「ホデル」と入力してしまった場合、サジェスチョンクエリとして一般的に「ホテル」がユーザに提示される。このようなスペルミスを修正するものもサジェスチョンクエリの一種として捉えることができる。
【０００５】
さらに、クエリと構成要素は非類似であるが、当該クエリと意味が類似するクエリ、例えばクエリが単語ならばいわゆる同義語や類義語についても、サジェスチョンクエリとして提示できれば、ユーザにとって便宜である。例えば上述の例でいえば、さらに「旅館」や「宿屋」といった「ホテル」の類義語についても、サジェスチョンクエリとして提示できれば、ユーザにとって便宜である。
【０００６】
このようなクエリと意味が類似するクエリ（同義語や類義語等）をサジェスチョンクエリとして適切に抽出すべく、本発明者らは、検索クリックスルーログを用いたラベル伝播手法による意味カテゴリの獲得に関する技術を既に提案している（非特許文献１参照）。
【０００７】
ここで、検索クリックスルーとは、ユーザが、クエリを入力した際に、検索エンジンが返す検索結果により示されるスニペット（当該クエリにヒットしたＷｅｂページのタイトル、当該クエリにヒットしたＷｅｂページのＵＲＬ、当該クエリを含むＷｅｂページの一部の断片等で構成されるリスト）をみて、当該Ｗｅｂページの一をクリック（選択）することをいう。
【０００８】
このような検索クリックスルーは、ユーザの意図を直接表していると考えられる。即ち、２以上のクエリの構成要素（語形等）が非類似であっても、同一のＷｅｂページに到達するものは、同じ意図で入力されたクエリである可能性が高いもの同士であると考えられる。特に、同一のＷｅｂページに到達する２以上のクエリは、同義語であることが多いと考えられる。従って、クエリと、クリック（選択）されたＷｅｂページのＵＲＬ（クリック先ＵＲＬ）とを関連付けて記憶した検索クリックスルーログを用いることによって、ユーザにより入力されたクエリに対して、意味が類似するクエリ（同義語や類義語等）をサジェスチョンクエリとして適切に抽出することが可能になる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】小町守、牧本信平、内海慶、颯々野学、“Ｗｅｂページ検索ログを用いたラベル伝播による意味カテゴリ獲得”、研究報告音声言語情報処理（ＳＬＰ）、第２００９−ＳＬＰ−７６巻、第９号、１乃至６ページ、２００９年５月４日
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、検索クリックスルーログの中には、非常に多くのクエリと共起してしまうクリック先ＵＲＬ、即ちいわゆるジェネリックパターンが存在する。このため、意味の類似度が本来低いクエリ同士が、ジェネリックパターンを介して、意味の類似度が本来よりも高いと評価される、といった現象が生ずる。
【００１１】
このような現象が生ずると、いわゆる意味ドリフトが発生して、サジェスチョンクエリの抽出の精度が悪化する。この点、非特許文献１によれば、ラベル伝播手法において、インスタンススコアベクトルは、シードのラベルとグラフ構造どちらを重視するかというパラメータα∈（０，１）を持ち、パラメータαが０に近づけばシードのラベルに偏った結果となり、パラメータαが１に近づけばラベルなしデータから作成されるグラフ構造を考慮した結果となる、とされている。このパラメータαを調整することにより、ある程度は意味ドリフトの発生を抑制することが可能である。しかしながら、あるクエリがジェネリックパターンを含むごく少数のクリック先ＵＲＬのみと共起するような場合には、パラメータαを調整したとしても意味ドリフトの発生を抑制することはできない。
【００１２】
そこで、本発明は、インスタンススコアベクトルのパラメータαの調整によることなくジェネリックパターンの存在に起因して生ずる意味ドリフトを抑制することによって、サジェスチョンクエリの抽出の精度を向上させる、サジェスチョンクエリ抽出装置及び方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、具体的には以下のようなものを提供する。
【００１４】
（１） クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計手段と、
前記頻度集計手段により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成手段と、
前記インスタンスパターン行列生成手段により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算手段と、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算手段により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信手段と、
を備え、
前記インスタンスパターン行列演算手段は、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算手段と、
前記正規化自己相互情報量演算手段により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除手段と、
を有するサジェスチョンクエリ抽出装置。
【００１５】
本発明のこのような構成によれば、正規化ラプラシアン行列は、検索クリックスルーログに基づくインスタンスパターン行列を用いて作成される。このインスタンスパターン行列の各要素として、正規化自己相互情報量が採用されるため、いわゆるジェネリックパターンによる影響を抑制し、ラベル伝播手法におけるラベルの伝播の強度が適切に決定される。従って、このような正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して本来よりも類似度が高いと評価される、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を高めることが可能になる。
【００１６】
（２） 前記クエリを複数含む言語資源ＤＢに基づいて、尤度算出言語モデルを作成する尤度算出言語モデル作成手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記尤度算出言語モデル作成手段により作成された尤度算出言語モデルに基づいて、尤度を、クエリらしさを示す尤度スコアとして演算する尤度スコア演算手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記類似度に加えてさらに、前記尤度スコア演算手段により演算された前記尤度スコアに基づいて、リランキングするリランキング手段と、
をさらに備え、
前記サジェスチョンクエリ送信手段は、前記リランキング手段によるリランキングの結果に従って、前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する、
（１）に記載のサジェスチョンクエリ抽出装置。
【００１７】
本発明のこのような構成によれば、尤度スコアに基づいてリランキングされた結果が用いられて、サジェスチョンクエリが抽出されるので、サジェスチョンクエリの抽出の精度がさらに向上する。
【００１８】
なお、尤度スコアの演算に際して、言語資源ＤＢ及び尤度算出言語モデルとしては、文字や単語の分布に基づいてどのような文字或いは単語がクエリとして生成され易いかが演算可能なものであれば足り、様々なものが採用可能である。具体的には、文字ベースの言語資源ＤＢに基づく文字Ｎｇｒａｍ言語モデル、単語ベースの言語資源ＤＢに基づくｗｏｒｄＮｇｒａｍ言語モデル等、様々なものを採用することができる。
また、尤度は、文字或いは単語の出現頻度等の確率分布を用いて表現することができるが、運用上は浮動小数点演算におけるアンダーフローを防ぐ観点から、自然対数尤度が好適に採用される。
【００１９】
さらに、本発明では、（１）に係る装置に対応する方法及びプログラムを提供する。これにより、（１）と同様の効果が期待できる。
【発明の効果】
【００２０】
本発明によれば、ジェネリックパターンの存在に起因して生ずる意味ドリフトを抑制することによって、サジェスチョンクエリの抽出の精度を向上させることができる。
【図面の簡単な説明】
【００２１】
【図１】本発明に係るサジェスチョンクエリ抽出装置を含む情報処理システムの一実施の形態の機能的構成を示す機能ブロック図である。
【図２】図１のサジェスチョンクエリ抽出装置の関連クエリ抽出部に採用されているラベル伝播手法を説明する図である。
【図３】正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を説明する図である。
【図４】図１のサジェスチョンクエリ抽出装置のうち、正規化ラプラシアン行列をカーネルとして生成するための準備部の機能的構成の詳細を示す機能ブロック図である。
【図５】図１のサジェスチョンクエリ抽出装置が実行するサジェスチョンクエリ抽出処理を例示するすフローチャートである。
【図６】図５のサジェスチョンクエリ抽出処理のうち正規化ラプラシアン行列作成処理を例示するすフローチャートである。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について説明する。なお、これはあくまでも一例であって、本発明の技術的範囲はこれに限られるものではない。
【００２３】
本実施形態は、コンピュータ及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備える、ハードウェア及び該ハードウェアを制御するソフトウェアによって構成される。
【００２４】
上記ハードウェアには、制御部としてのＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の他、記憶部、通信装置、表示装置及び入力装置が含まれる。記憶部としては、例えば、メモリ（ＲＡＭ：Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＲＯＭ：Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ等）、ハードディスクドライブ（ＨＤＤ：Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）及び光ディスク（ＣＤ：Ｃｏｍｐａｃｔ Ｄｉｓｋ、ＤＶＤ：Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ等）ドライブが挙げられる。通信装置としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示装置としては、例えば、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイが挙げられる。入力装置としては、例えば、キーボード及びポインティング・デバイス（マウス、トラッキングボール等）が挙げられる。
【００２５】
上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部により記憶され、制御部により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信回線を介して配布されることも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布されることも可能である。
【００２６】
図１は、本発明に係るサジェスチョンクエリ抽出装置を含む情報処理システムの一実施の形態の機能的構成を示す機能ブロック図である。
【００２７】
情報処理システムは、サジェスチョンクエリ抽出装置１１と、ユーザ端末１２とが相互に接続されることによって構成されている。
【００２８】
なお、サジェスチョンクエリ抽出装置１１とユーザ端末１２との接続の形態は特に限定されないが、本実施形態では図示せぬインターネットを介してサジェスチョンクエリ抽出装置１１とユーザ端末１２とが接続されているものとする。また、ユーザ端末１２は、実際には複数台存在し得るが、ここでは説明の便宜上１台であるものとする。
【００２９】
サジェスチョンクエリ抽出装置１１は、主処理部２１と、準備部２２，２３とを備えている。
【００３０】
主処理部２１は、ユーザ端末１２から入力されるクエリ（以下、「入力クエリ」と呼ぶ）に基づいて、サジェスチョンクエリを抽出して、ユーザ端末１２に送信する。このため、主処理部２１は、関連クエリ抽出部３１と、尤度スコア演算部３２と、クエリリストリランキング部３３と、サジェスチョンクエリ送信部３４とを備えている。
【００３１】
関連クエリ抽出部３１は、入力クエリと関連する１以上のクエリ（以下、「関連クエリ」と呼ぶ）を抽出してリスト化する。このような１以上の関連クエリを含むリストを、以下、「関連クエリリスト」と呼ぶ。
【００３２】
関連クエリ抽出部３１による関連クエリの抽出手法として、本実施形態では、正規化ラプラシンアン行列をカーネルとして用いるラベル伝播手法に従って、入力クエリをシードとした場合におけるクエリ同士の意味の類似度を演算し、当該類似度に基づいて関連クエリを抽出する、といった手法が採用されている。なお、正規化ラプラシア行列やラベル伝播手法の詳細については後述する。
【００３３】
この場合、関連クエリ抽出部３１は、意味の類似度に基づいて、１以上の関連クエリの各々に対する順位付け（ランキング）を行うこともできる。ここで、意味の類似度の高低を示す値を以下「類似度スコア」と呼ぶものとすると、１以上の関連クエリの各々は、類似度スコアが付加された上で、ランキング順にソートされてリスト化される。このようにして、類似度スコア付の関連クエリリストが生成されて、関連クエリリスト保持部３５に保持される。
【００３４】
尤度スコア演算部３２は、関連クエリリストに含まれる１以上の関連クエリの各々について、文字Ｎｇｒａｍ言語モデルに基づいて、自然対数尤度を、クエリらしさを示す尤度スコアとして演算する。なお、文字Ｎｇｒａｍ言語モデル等の詳細については後述する。
【００３５】
尤度スコア演算部３２により演算された各尤度スコアは、各関連クエリと対応付けられて、関連クエリリストに付加される。即ち、尤度スコア及び類似度スコア付きの関連クエリリストが作成され、関連クエリリスト保持部３５に保持される。
【００３６】
クエリリストリランキング部３３は、関連クエリリストに含まれる１以上の関連クエリの各々について、類似度スコアと尤度スコアの対数の和をそれぞれ演算し、各演算結果に基づいて、１以上の関連クエリのリランキング（再順位付け）を行う。そして、尤度スコア及び類似度スコア付きの関連クエリリストにおいて、１以上の関連クエリの各々が、リランキング順に再ソートされる。
【００３７】
サジェスチョンクエリ送信部３４は、リランキング後の再ソートされた関連クエリリストから、高順位の関連クエリを優先的にサジェスチョンクエリとして抽出して、ユーザ端末１２に送信する。
【００３８】
関連クエリリスト保持部３５は、上述の如く、類似度スコア付きの関連クエリリストや、尤度スコア及び類似度スコア付きの関連クエリリストを保持する。なお、類似度スコア付きの関連クエリリストと、尤度スコア及び類似度スコア付きの関連クエリリストとは、別々のリストとして保持してもよいが、１つのリストとして保持してもよい。ここで、１つのリストとして保持するとは、類似度スコア付きの関連クエリリストに対して、尤度スコアを格納する項目を関連クエリ毎に追加することによって、尤度スコア及び類似度スコア付きの関連クエリリストとして保持することを意味する。
【００３９】
以上、サジェスチョンクエリ抽出装置１１の主処理部２１の機能的構成の概略について説明した。さらに以下、図２及び図３を参照して、主処理部２１のうち、特に関連クエリ抽出部３１の詳細について説明する。
【００４０】
図２は、関連クエリ抽出部３１に採用されているラベル伝播手法を説明する図であって、シードクエリが旅行に関するものである場合におけるラベルの伝播の様子を示す図である。
【００４１】
図２において、左側の丸印によって示されるノードは、クエリ（図２の例では単語のみ）を示している。右側の丸印によって示されるノードは、左側のクエリと共起するパターンを示している。このように、図２に示すグラフは、左側のノードがクエリとなっており、右側のノードがそのクエリと共起するパターンとなっている２部グラフである。当該グラフにおいて、左右のノードを結ぶ線の強さ（図中、太い直線が最も強く、以下、線が細くなるほど、さらに、点線の線部の長さが短くなる程弱くなっていく）が、当該左右のノード間の共起の度合を示している。なお、左右のノードを結ぶ線は、「エッジ」とも呼ばれている。また、各ノードの濃さ（図中丸印内の色の濃さ）が、シードクエリとの関連の強さを表わしている。
【００４２】
ここで、パターンとして示されるＵＲＬ（実際には、「ｈｔｔｐ：／／・・・」といったＵＲＬ）は、クリック先ＵＲＬを意味している。即ち、本実施形態では、シードクエリとの関連の強さの演算に関する学習を高精度に行うべく、パターンとして、従来用いられていたクエリログのみならず、検索クリックスルーログも採用されている。
【００４３】
図２において、左上のノードが、シードクエリとしての単語（以下、「シード単語」と呼ぶ）「航空会社Ａ」であり、所定のラベルが付されているものとする。この場合、シード単語「航空会社Ａ」に付されたラベルが、当該シード単語「航空会社Ａ」と共起の度合いが強いパターン「ＵＲＬ：中部発」に伝搬する。ここで、パターン「ＵＲＬ：中部発」とは、飛行機の発着場所が日本国の中部空港であるという内容を含むＷｅｂページがクリック先ＵＲＬであることを示すものとする。このようなパターン「ＵＲＬ：中部発」は、シードクエリとの関連が強いとして、シード単語「航空会社Ａ」に付されていたラベルが伝播される。
【００４４】
一方、パターン「ＵＲＬ：ツアー」は、歌手Ｂがコマーシャルの出演者として起用された所定のツアーを紹介するＷｅｂページがクリック先ＵＲＬであることを示すものとする。この場合、パターン「ＵＲＬ：ツアー」は、単語「歌手Ｂ」というシードクエリとは異なるクエリとも共起するため、比較的中立なパターンである。
【００４５】
単語「旅行会社Ｃ」は、パターン「ＵＲＬ：中部発」及びパターン「ＵＲＬ：ツアー」をシード単語「航空会社Ａ」と共有しているため、当該シード単語「航空会社Ａ」に付されていたラベルが伝播される。このようにしてラベルが伝播された単語「旅行会社Ｃ」は、シードクエリとの関連が強い単語として分類されることになる。
【００４６】
このように、ラベル伝播手法とは、シードとして与えるノードに付されたラベルを、隣接ノードに順次伝播していく手法をいう。ラベル伝播手法では、最適なラベルは、ラベル伝播のプロセスが収束した状態におけるラベルとして与えられる。
【００４７】
本実施形態では、このようなラベル伝播手法として、正規化ラプラシアン行列をカーネルとして用いる手法が採用されている。そこで、以下、図３を参照して、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法について説明する。
【００４８】
図３は、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を説明する図である。
【００４９】
図３に示すように、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法では、入力として、シードインスタンスベクトルＦ（０）と、インスタンス類似度行列Ａとが与えられる。また、学習におけるｔステップ目（ｔは１以上の整数値）の出力としては、インスタンススコアベクトルＦ（ｔ）が得られる。
【００５０】
ここで、あらゆるインスタンスの集合をχと表わすものとする。インスタンスとは、図２における左側のノード、即ちクエリ（単語等）を意味する。あるシードクエリとの関連の強さについて学習する場合、例えば図２の例ではシードクエリが関係する旅行との関連の強さについて学習する場合、ｔステップ目に出力されるインスタンススコアベクトルＦ（ｔ）は、集合χの要素数｜χ｜を次元数とするベクトルとして表わされる。インスタンススコアベクトルＦ（ｔ）のｉ番目（ｉは、１乃至｜χ｜の範囲内の整数値）の次元の要素値としては、集合χのインスタンスｘｉが、どの程度シードクエリと関連があるのか（図２の例では、どの程度旅行との関連があるのか）を示すスコアが採用される。即ち、集合χのインスタンスｘｉの当該シードクエリとの関連の度合を示すスコアが、インスタンススコアベクトルＦ（ｔ）のｉ番目の次元の要素値になる。
【００５１】
従って、あるシードクエリとの関連の強さについて学習する場合において、入力として与えられるシードインスタンスベクトルＦ（０）とは、次のような要素値を有するベクトルとなる。即ち、シードインスタンスベクトルＦ（０）においては、シードとして与えられるインスタンス（図１の関連クエリ抽出部３１にとっては入力クエリ）の集合に、インスタンスｘｉが含まれる場合、ｉ番目の次元の要素値が「１」となり、それ以外の次元の要素値が「０」となる。
【００５２】
また、入力として与えられるインスタンス類似度行列Ａは、インスタンスパターン行列Ｗを用いて、次の式（１）により演算される。
【数１】
・・・（１）
インスタンスパターン行列Ｗとは、例えば、インスタンスｘｉとパターンｐｊの関連性を示す値（従来は単純な共起回数であり、本実施形態では後述する正規化自己相互情報量）をｉ行ｊ列の要素値として有する行列をいう。ここで、従来においては、インスタンスパターン行列Ｗは、次の式（２）によって正規化された上で、式（１）に代入されていた。
【数２】
・・・（２）
ここで、行列Ｄ（Ｎ）は、次の式（３）によって定まる行列Ｎの次数対角行列をいう。
【数３】
・・・（３）
【００５３】
あるシードクエリとの関連の強さについて学習をする場合、シードインスタンスベクトルＦ（０）及びインスタンス類似度行列Ａが入力として与えられて、図３の手順に従った処理が実行されることで、インスタンスベクトルＦ（ｔ）が出力される。
【００５４】
即ち、図３の手順のステップＳ１に示すように、次の式（４）に示す正規化ラプラシアン行列Ｌが作成される。
【数４】
・・・（４）
なお、本実施形態では、後述するように、正規化ラプラシアン行列Ｌは、図１の正規化ラプラシアン行列作成部４２によって作成されて、正規化ラプラシアン行列保持部４３に保持される。
【００５５】
次に、図３の手順のステップＳ２に示すように、ｔステップの演算結果を用いるｔ＋１ステップのインスタンスベクトルＦ（ｔ＋１）を式（５）の演算により求めるといった処理が、ｔが１ずつインクリメントされる毎に繰り返し実行される。そして、収束された段階における式（５）の演算結果が、ｔ＝ｔ＋１としてインクリメントされた後、インスタンスベクトルＦ（ｔ）として出力される。
【数５】
・・・（５）
【００５６】
このようにして出力されたインスタンスベクトルＦ（ｔ）は、シードとして与えられたインスタンスに対して、意味の類似度順にインスタンス（クエリ）が整列したベクトルになっている。
【００５７】
従って、関連クエリ抽出部３１（図１）は、ユーザ端末１２から供給された入力クエリをシードとして、上述のステップＳ１及びＳ２の処理を実行してインスタンスベクトルＦ（ｔ）を演算することで、関連クエリを抽出することができる。即ち、関連クエリ抽出部３１は、当該インスタンスベクトルＦ（ｔ）に基づいて、入力クエリに対する意味の類似度が上位１乃至Ｋ番目（Ｋは１以上の整数値）のインスタンス、即ち、１乃至Ｋ次元の各要素に対応するインスタンスを、Ｋ個の関連クエリとしてそれぞれ抽出することができる。
【００５８】
この場合、インスタンスベクトルＦ（ｔ）の１乃至Ｋ次元の各要素値が、Ｋ個の関連クエリの各々に対して付加される類似度スコアとして採用される。即ち、上述のステップＳ２における式（５）の繰り返し演算とは、各インスタンス（各クエリ）について、類似度スコアに基づくランキング（順位付け）を行い、ランキングの結果順にソートすることと等価である。従って、関連クエリ抽出部３１は、インスタンスベクトルＦ（ｔ）の１乃至Ｋ次元の各要素を抽出することによって、類似度スコア付きの関連クエリリストを作成することができる。
【００５９】
なお、式（５）において、パラメータαは、シードのラベルとグラフ構造とのうち何れを重視するラベル伝播手法であるのかを示すパラメータであって、０乃至１の範囲内で可変する。即ち、パラメータαが０に近付くほど、シードのラベルに偏った結果となり、αが１に近付くほど、ラベルなしデータ（インスタンス）から作成されるグラフ構造を考慮した結果となる。
【００６０】
また、２つのシードクエリとの関連の強さについて学習する場合には、シードとして与えられるインスタンスの各々に対して「１」または「−１」の値が与えられることによって、シードインスタンスベクトルＦ（０）が作成される。そして、最終的なスコアｙｉの符号の正負によって、インスタンスｘｉのラベルが決定される。さらに、３以上のｎ個のシードクエリとの関連の強さについて学習する場合には、シードとしてはベクトルではなくｎ次元の行列が作成されて、ラベル付けが行われる。
【００６１】
次に、図４を参照して、このようなラベル伝播手法においてカーネルとして用いられる正規化ラプラシアン行列の作成手法について説明する。
【００６２】
図４は、図１のサジェスチョンクエリ抽出装置１１のうち、正規化ラプラシアン行列をカーネルとして生成するための準備部２２の機能的構成の詳細を示す機能ブロック図である。
【００６３】
準備部２２は、クリックスルーログＤＢ４１と、正規化ラプラシアン行列作成部４２と、正規化ラプラシアン行列保持部４３とを備えている。
【００６４】
クリックスルーログＤＢ４１は、検索クリックスルーログを記憶している。即ち、クリックスルーログＤＢ４１は、クエリに対する検索結果のクリック先示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数記憶している。
【００６５】
正規化ラプラシアン行列作成部４２は、共起頻度集計部６１と、インスタンスパターン行列生成部６２と、正規化ラプラシアン行列演算部６３とを備えている。
【００６６】
共起頻度集計部６１は、検索クリックスルーログをクリックスルーログＤＢ４１から参照して、各々のクエリについて、関連付けられたクリック先ＵＲＬの数を集計する。ここで、共起頻度集計部６１により集計されたクリック先ＵＲＬの数は、上述の集合χにおけるインスタンスｘｉとしてのクエリと、パターンｐｊとしてのクリック先ＵＲＬの共起回数ｗｉｊに相当する。そこで、共起頻度集計部６１により集計されたクリック先ＵＲＬの数を、以下、「共起頻度」と呼ぶ。
【００６７】
インスタンスパターン行列生成部６２は、共起頻度集計部６１により集計された共起頻度に基づいて、インスタンス（クエリ）とパターン（クリック先ＵＲＬ）の関連を示すインスタンスパターン行列を演算する。
【００６８】
正規化ラプラシアン行列演算部６３は、当該インスタンスパターン行列を用いて、上述した式（４）を演算することで、正規化ラプラシアン行列を演算する。
【００６９】
正規化ラプラシアン行列保持部４３は、正規化ラプラシアン行列作成部４２により作成された正規化ラプラシアン行列を、カーネルとして保持する。
【００７０】
なお、正規化ラプラシアン行列に必要なインスタンス類似度行列Ａは、上述の如く式（１）に従って演算されるが、非常に大規模な行列であるため、記憶容量が非常に大きくなる場合がある。このような場合には、正規化ラプラシアン行列保持部４３が、インスタンスパターン行列Ｗ及びその転置行列ＷＴのみを保持し、正規化ラプラシアン行列演算部６３が、式（１）を毎回演算することによって、記憶容量を削減することができる。インスタンス類似度行列Ａが密行列であるのに対して、インスタンスパターン行列Ｗは疎行列であるからである。
【００７１】
さらに、以下、正規化ラプラシアン行列をカーネルとして作成するために必要なインスタンスパターン行列について説明する。
【００７２】
［背景技術］の欄でも上述したように、クリック先ＵＲＬの中には、非常に多くのクエリと共起してしまうジェネリックパターンが存在する。このため、意味の類似度が低いクエリ同士がジェネリックパターンを介して本来よりも類似度が高いと評価されてしまう、といった現象が従来生じていた。
【００７３】
換言すると、ラベル伝播手法においては、伝播元のインスタンス（クエリ）から、それと共通するパターン（クリック先ＵＲＬ）を持つ伝播先のインスタンスに対してラベルが伝搬される。この場合、伝播の強さは、伝播先のインスタンスからの伝播の広がりが考慮される。このため、従来のラベル伝播手法には、次のような第１の特徴及び第２の特徴が存在した。即ち、第１の特徴とは、伝播先のインスタンスが大量のパターンを持っているような場合には伝播が弱くなる、といった特徴である。また、第２の特徴とは、伝播先のインスタンスが少量のパターンしか持たない場合には強く伝搬する、といった特徴である。第２の特徴が顕著に表れた例としては、伝播先のインスタンスが、１つのパターンしか持たず、伝播元のインスタンスとそのパターンのみで繋がっている場合である。このような場合には、伝播先のインスタンスが、１つのジェネリックパターンのみを持つような場合であっても、強く伝搬されてしまうことになる。強く伝搬されるということは、たとえジェネリックパターン１つのみで繋がる伝播元と伝播先のインスタンス同士であっても、即ち意味の類似度が本来低いインスタンス同士であっても、意味の類似度が本来より高いと評価されてしまうことを意味する。
【００７４】
ここで、従来のラベル伝播手法の第２の特徴、即ち、伝播先のインスタンスが少量のパターンしか持たない場合には強く伝搬するという特徴は、インスタンスパターン行列Ｗの正規化処理に起因して生ずる。
【００７５】
即ち、従来においては、上述した式（２）に示すように、次数対角行列の逆行列Ｄ−１（Ｗ）が、インスタンスパターン行列Ｗの左側に掛けられることで、当該インスタンスパターン行列Ｗが正規化されていた。具体的には、インスタンスパターン行列Ｗの各行は、各インスタンス（各クエリ）に対応しており、所定行の各要素値は、対応するインスタンスと各パターン（クリック先ＵＲＬ）との共起回数（クリックされた回数）に基づく値である。このような各インスタンスに対応する各行において、各要素値の総和がそれぞれ「１」になるように正規化されていた。
【００７６】
このため、従来においては、多くのパターンと共起するインスタンスに対応する行については、各要素値は小さくなっていた。また、共起するパターンの分布に偏りがあるインスタンスに対応する行については、偏って共起するパターンに対応する要素値が大きくなっていた。
【００７７】
一方で、従来においては、共起するパターンが少数のインスタンスに対応する行については、各要素値は大きくなっていた。極端な例を挙げると、共起するパターンが１つしか存在しない場合には、当該パターンに対応する要素値は必ず「１」になっていた。このように要素値が必ず「１」になることは、当該パターンがジェネリックパターンであったとしても何ら変わらない。
【００７８】
このように、式（２）によって正規化された従来のインスタンスパターン行列Ｗは、ジェネリックパターン以外に共起するパターンをほとんど持たないインスタンスに対応する行であって、当該ジェネリックパターンに対応する要素値が「１」に近くなっている行を有している。従来、このような式（２）によって正規化されたインスタンスパターン行列Ｗからラプラシアン行列Ｌが作成され、当該ラプラシアン行列Ｌを用いるラベル伝播手法に従って学習が行われていた。その結果、ジェネリックパターン以外に共起するパターン（クリック先ＵＲＬ）をほとんど持たないインスタンス（クエリ）が、シードとして与えられたインスタンス（シードのクエリ）との意味の類似度が高くなってしまう傾向にあった。即ち、ジェネリックパターン以外に共起するパターンをほとんど持たないインスタンスと、シードとして与えられたインスタンスとは、意味の類似度が本来低いクエリ同士に該当する。このような意味の類似度が本来低いクエリ同士が、ジェネリックパターンを介して、意味の類似度が本来よりも高いと評価されてしまう、といった現象が生じてしまう傾向にあった。
【００７９】
そこで、このような現象が生ずることを抑制すべく、図４に示すように、本実施形態のインスタンスパターン行列生成部６２は、正規化自己相互情報量演算部７１と、エッジカット部７２とを備えている。
【００８０】
正規化自己相互情報量演算部７１は、インスタンスパターン行列Ｗの各要素値として、正規化自己相互情報量（ＮＰＭＩ：Ｎｏｒｍａｌｉｚｅｄ Ｐｏｉｎｔｗｉｓｅ Ｍｕｔｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ）を演算する。以下、この正規化自己相互情報量について説明する。
【００８１】
正規化される前の自己相互情報量（ＰＭＩ：Ｐｏｉｎｔｗｉｓｅ Ｍｕｔｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ）は、次の式（６）により示される。
【数６】
・・・（６）
式（６）において、ｉ（ｘ，ｐ）が、インスタンスｘとパターンｐとの自己相互情報量を示している。即ち、式（６）の右辺において、インスタンスｘとパターンｐとが互いに独立であると仮定して求めた確率分布がｐ（ｘ）ｐ（ｐ）であり、実際に観測された確率分布がｐ（ｘ，ｐ）である。式（６）の右辺に示すように、これらの２つの確率分布の情報量の差が自己相互情報量ｉ（ｘ，ｐ）として求められる。
【００８２】
ここで、自己相互情報量ｉ（ｘ，ｐ）の値として取り得る範囲は［−∞乃至＋∞］であり、２つの確率分布が一致する際には自己相互情報量ｉ（ｘ，ｐ）は０になる。従って、自己相互情報量ｉ（ｘ，ｐ）をそのままインスタンスパターン行列Ｗの各要素値として採用すると、従来の共起回数を要素値としていた場合に「０」となっていた要素値が、全て「−∞」となってしまい、演算が不可能になってしまう。そこで、本実施形態では、次の式（７）に示すように、自己相互情報量ｉ（ｘ，ｐ）が正規化され、その結果得られる正規化自己相互情報量ｉｎ（ｘ，ｐ）が、原則、インスタンスパターン行列Ｗの各要素値として採用される。
【数７】
・・・（７）
【００８３】
式（７）に示すように、正規化自己相互情報量ｉｎ（ｘ，ｐ）は、自己相互情報量ｉ（ｘ，ｐ）が（−ｌｎｐ（ｘ，ｐ））で除算されることによって正規化されたものであり、その値が取り得る範囲は［−１乃至＋１］となる。確率分布ｐ（ｘ，ｐ）が０のとき、正規化自己相互情報量ｉｎ（ｘ，ｐ）は−１になる。また、確率分布ｐ（ｘ），ｐ（ｐ）が相互に独立の場合には、正規化自己相互情報量ｉｎ（ｘ，ｐ）は０になる。そして、インスタンスｘとパターンｐとが互いに共起する場合には、正規化自己相互情報量ｉｎ（ｘ，ｐ）は１になる。
【００８４】
本実施形態では、図４のインスタンスパターン行列生成部６２の正規化自己相互情報量演算部７１が、式（７）に従って、インスタンスパターン行列Ｗの各要素毎に、正規化自己相互情報量ｉｎ（ｘ，ｐ）を演算する。
【００８５】
しかしながら、インスタンスパターン行列Ｗの各要素値として何れも、式（７）の正規化自己相互情報量ｉｎ（ｘ，ｐ）を採用すると、半正定値性が崩れるために、正規化ラプラシアン行列を用いたラベル伝播手法の適用が不可能になる。そこで、本実施形態では、次の式（８）に従って、インスタンスパターン行列Ｗの各要素値ｗ（ｘ，ｐ）が演算される。
【数８】
・・・（８）
式（８）において、右辺の［α］ｔｈは、閾値ｔｈ以下の場合、入力値αを削除し（入力値αを入力としてはみずに、出力せず）、閾値ｔｈを超えている場合、入力値αをそのまま出力する関数を意味している。ここで、閾値ｔｈは、半正定値性を満足させるために０以上の値である必要がある。
【００８６】
例えば閾値ｔｈが０の場合には、式（８）の右辺は、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるときには、当該負の値はみないということを意味している。即ち、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるということは、インスタンスｘとパターンｐとの間に負の相関があるということであり、この組み合わせは発生しにくいことを表しているため、みないということである。
【００８７】
ラベル伝播手法の観点で換言すると、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるということは、インスタンスｘとパターンｐとはエッジが張られにくいことを意味している。即ち、図２の例でいうと、インスタンスｘを示す左側のノードと、パターンｐを示す右側のノードとを結ぶ線（エッジ）の強さが弱いということを意味している。ここで、正規化自己相互情報量ｉｎ（ｘ，ｐ）を用いる意義は、ラベルを伝搬させる強さが適切に決定される点にある。従って、エッジの張り方は直接観測したデータから決定されるため、負の値の正規化自己相互情報量ｉｎ（ｘ，ｐ）を削除しても、即ちエッジを削除しても、ラベルの伝搬の強さを適切にするという点で特に問題とならない。また、正規化自己相互情報量ｉｎ（ｘ，ｐ）が０となる要素については、インスタンスｘとパターンｐとは互いに独立であると判断できるので、エッジを削除しても、ラベルの伝搬の強さを適切にするという点で特に問題とならない。
【００８８】
本実施形態では、図４のインスタンスパターン行列生成部６２のエッジカット部７２が、このような式（８）を演算することによって、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈ以下の要素におけるエッジを削除する。即ち、インスタンスパターン行列Ｗの各要素のうち、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈを超える要素については、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値がそのまま要素値として採用される。これに対して、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈ以下の要素については、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値は要素値として採用されず、例えば所定の固定値が採用される。
【００８９】
なお、上述したように、エッジを削除する基準となる閾値ｔｈは、半正定値性を満足させる必要があるため、負値は採用できないが、０を採用する必要は特になく、１以下の任意の正値を採用することができる。
【００９０】
このように、本実施形態では、上述した正規化自己相互情報量演算部７１及びエッジカット部７２を含むインスタンスパターン行列生成部６２が、式（７）及び式（８）に従ってインスタンスパターン行列Ｗを演算して、正規化ラプラシアン行列演算部６３に供給する。当該インスタンスパターン行列Ｗの各要素は、原則として（閾値ｔｈを超えているものは）、正規化自己相互情報量が採用されているため、ラベル伝播手法におけるラベルの伝播の強度を適切に決定することができる。
【００９１】
正規化ラプラシアン行列演算部６３は、当該インスタンスパターン行列Ｗを用いて上述した式（１）を演算することによって、インスタンス類似度行列Ａを演算する。そして、正規化ラプラシアン行列演算部６３は、このインスタンス類似度行列Ａを用いて式（４）を演算することで、正規化ラプラシアン行列Ｌを演算し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。
【００９２】
以上説明したように、本実施形態の正規化ラプラシアン行列作成部４２により作成された正規化ラプラシアン行列Ｌをカーネルとして用いて、ラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して意味の類似度が本来よりも高いと評価されてしまう、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を高めることが可能になる。
【００９３】
以上、図１のサジェスチョンクエリ抽出装置１１のうち、正規化ラプラシアン行列Ｌをカーネルとして作成する準備部２２について説明した。
次に、図１のサジェスチョンクエリ抽出装置１１のうち、尤度算出言語モデルを作成する準備部２３について説明する。
【００９４】
準備部２３は、言語資源ＤＢ５１と、尤度算出言語モデル作成部５２と、尤度算出言語モデル保持部５３と、を備えている。なお、言語資源ＤＢ５１、尤度算出言語モデル作成部５２及び尤度算出言語モデル保持部５３としては、具体的には、文字や単語の分布に基づいてどのような文字或いは単語がクエリとして生成され易いかが演算可能なものであれば足り、様々なものが採用可能である。例えば、文字ベースの言語資源ＤＢに基づく文字Ｎｇｒａｍ言語モデル、単語ベースの言語資源ＤＢに基づくｗｏｒｄＮｇｒａｍ言語モデル等、様々なものを採用することができる。以下、これらの一例を取り上げて説明を続ける。
【００９５】
言語資源ＤＢ５１は、これまでにクエリとして用いられた多数のクエリのログ、即ちいわゆるクエリログを記憶している。
【００９６】
尤度算出言語モデル作成部５２は、言語資源ＤＢ５１に記憶されたクエリログに基づいて、尤度算出言語モデルを作成する。即ち、尤度算出言語モデル作成部５２は、クエリとしての文字或いは単語ｗを、ｗ＝｛ｘ［１］，ｘ［２］，・・・，ｘ［ｎ］｝という文字或いは単語の並びと把握して、自然対数尤度を演算することによって、尤度算出言語モデルを作成する。
【００９７】
より具体的には、例えば、尤度算出言語モデル作成部５２は、
ｌｎＰ（ｗ）
＝ΣｌｎＰ（ｘ［ｉ］｜｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ−１］｝）
＝Σ｛ｌｎ（ｆｒｅｑ（｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ］｝））−ｌｎ（ｆｒｅｑ（｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ−１］｝））｝
の式に従って、自然対数尤度を計算する。
なお、この実施形態では自然対数尤度を計算しているが、あくまで一例であって、クエリらしさを表現可能な様々なものが採用可能である。
【００９８】
尤度算出言語モデル保持部５３は、尤度算出言語モデル作成部５２により作成された文字Ｎｇｒａｍ言語モデルを保持する。
【００９９】
以上、図１を参照して、本発明に係るサジェスチョンクエリ提供システムの一実施の形態の機能的構成について説明した。
次に、このようなサジェスチョンクエリ提供処理システムのうち、サジェスチョンクエリ抽出装置１１が実行する一連の処理（以下、「サジェスチョンクエリ抽出処理」と称する）の流れについて説明する。
【０１００】
図５は、サジェスチョンクエリ抽出処理を例示するすフローチャートである。
【０１０１】
ステップＳ１１において、図１の正規化ラプラシアン行列作成部４２は、正規化ラプラシアン行列保持部４３を参照して、正規化ラプラシアン行列が作成済であるか否かを判定する。
【０１０２】
正規化ラプラシアン行列が作成済みの場合、ステップＳ１１においてＹＥＳであると判定されて、処理はステップＳ１３に進む。なお、ステップＳ１３以降の処理については後述する。
【０１０３】
これに対して、正規化ラプラシアン行列が未作成の場合、ステップＳ１１においてＮＯであると判定されて、処理はステップＳ１２に進む。
ステップＳ１２において、正規化ラプラシアン行列作成部４２は、正規化ラプラシアン行列を作成し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。なお、このようなステップＳ１２の処理を、以下、「正規化ラプラシアン行列作成処理」と呼ぶ。正規化ラプラシアン行列作成処理の詳細については、図６を参照して後述する。
ステップＳ１２の正規化ラプラシアン行列作成処理が実行されると、処理はステップＳ１３に進む。
【０１０４】
ステップＳ１３において、尤度算出言語モデル作成部５２は、尤度算出言語モデル保持部５３を参照して、尤度算出言語モデルが作成済であるか否かを判定する。
【０１０５】
尤度算出言語モデルが作成済みの場合、ステップＳ１３においてＹＥＳであると判定されて、処理はステップＳ１５に進む。なお、ステップＳ１５以降の処理については後述する。
【０１０６】
これに対して、尤度算出言語モデルが未作成の場合、ステップＳ１３においてＮＯであると判定されて、処理はステップＳ１４に進む。
ステップＳ１４において、尤度算出言語モデル作成部５２は、尤度算出言語モデルを作成し、尤度算出言語モデル保持部５３に保持させる。これにより、処理はステップＳ１５に進む。
【０１０７】
ステップＳ１５において、関連クエリ抽出部３１は、ユーザ端末１２から入力クエリが供給されたか否かを判定する。
ユーザ端末１２から入力クエリが供給されてこない場合、ステップＳ１５においてＮＯであると判定されて、処理はステップＳ１５に再度戻される。即ち、ユーザ端末１２から入力クエリが供給されてくるまでの間、ステップＳ１５の判定処理が繰り返し実行されることで、サジェスチョンクエリ抽出処理が待機状態になる。
その後、ユーザ端末１２から入力クエリが供給されてくると、ステップＳ１５においてＹＥＳであると判定されて、処理はステップＳ１６に進む。
【０１０８】
ステップＳ１６において、関連クエリ抽出部３１は、類似度スコア付きの関連クエリリストを作成する。即ち、関連クエリ抽出部３１は、ステップＳ１２の処理で作成された正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、入力クエリをシードとした場合におけるクエリ同士の意味の類似度スコアを演算する。そして、関連クエリ抽出部３１は、類似度スコアが高いクエリを優先して、当該類似度スコア付きの関連クエリとして抽出し、これらを類似度スコアに基づくランキング順にソートすることによって、類似度スコア付き関連クエリリストを作成する。
【０１０９】
ステップＳ１７において、尤度スコア演算部３２は、ステップＳ１６の処理で作成された関連クエリリストに含まれる１以上の関連クエリの各々について、尤度スコアを演算し、関連クエリリストに付加する。即ち、尤度スコア演算部３２は、ステップＳ１４の処理で作成された文字Ｎｇｒａｍ言語モデルに基づいて、自然対数尤度を、クエリらしさを示す尤度スコアとして演算する。そして、尤度スコア演算部３２は、尤度スコア及び類似度スコア付きの関連クエリリストを作成する。
【０１１０】
ステップＳ１８において、クエリリストリランキング部３３は、関連クエリリストに含まれる１以上の関連クエリの各々について、類似度スコアと尤度スコアの対数の和をそれぞれ演算し、各演算結果に基づいて、１以上の関連クエリのリランキング（再順位付け）を行う。その結果、尤度スコア及び類似度スコア付きの関連クエリリストにおいて、１以上の関連クエリの各々が、リランキング順に再ソートされる。
【０１１１】
ステップＳ１９において、サジェスチョンクエリ送信部３４は、リランキング後の再ソートされた関連クエリリストから、リランキングの結果高順位となっている幾つかの関連クエリを優先して、サジェスチョンクエリとして抽出して、ユーザ端末１２に送信する。これにより、サジェスチョンクエリ抽出処理は終了となる。
【０１１２】
なお、ステップＳ１５乃至Ｓ１９の処理は、正規化ラプラシアン行列及び尤度算出言語モデルが作成済みの状態であれば実行可能である。従って、ステップＳ１５の処理の開始タイミングは、ステップＳ１１乃至Ｓ１４の処理の終了後であれば足りる。即ち、ステップＳ１１乃至Ｓ１４の処理の終了後、時間的に連続して即座に、ステップＳ１５の処理が開始される必要は特になく、時間的に離間して、ステップＳ１５の処理が開始されてもよい。
【０１１３】
換言すると、図１のサジェスチョンクエリ抽出装置に１１において、主処理部２１、準備部２２、及び、準備部２３の各々は、相互に独立かつ並行して処理を実行することができる。従って、例えば準備部２２は、サジェスチョンクエリ抽出処理とは独立して、正規化ラプラシアン行列保持部４３に保持されている正規化ラプラシアン行列を適宜更新しても構わない。同様に、例えば準備部２３は、サジェスチョンクエリ抽出処理とは独立して、尤度算出言語モデル保持部５３に保持されている尤度算出言語モデルを適宜更新しても構わない。
【０１１４】
次に、図５のサジェスチョンクエリ抽出処理のうち、ステップＳ１２の正規化ラプラシアン行列作成処理の流れについて説明する。
【０１１５】
図６は、正規化ラプラシアン行列作成処理を例示するすフローチャートである。
【０１１６】
ステップＳ３１において、図４の正規化ラプラシアン行列作成部４２の共起頻度集計部６１は、検索クリックスルーログに基づいて、共起頻度を集計する。即ち、共起頻度集計部６１は、検索クリックスルーログをクリックスルーログＤＢ４１から参照して、各々のクエリについて、関連付けられたクリック先ＵＲＬ（検索クリックスロー）の数を、共起頻度として集計する。
【０１１７】
ステップＳ３２において、インスタンスパターン行列生成部６２は、ステップＳ３１の処理で集計された共起頻度に基づいて、インスタンスパターン行列Ｗを生成する。
【０１１８】
具体的には、インスタンスパターン行列生成部６２の正規化自己相互情報量演算部７１は、インスタンスパターン行列Ｗの各要素毎に、上述した式（７）に従って、正規化自己相互情報量ｉｎ（ｘ，ｐ）をそれぞれ演算する。次に、エッジカット部７２は、上述した式（８）に従って、インスタンスパターン行列Ｗの各要素毎に演算された正規化自己相互情報量ｉｎ（ｘ，ｐ）のうち、閾値ｔｈ（例えばｔｈ＝０）以下の要素を削除する。これにより、削除された要素におけるインスタンスｘとパターンｐとのエッジが削除される。このようにして、インスタンスパターン行列Ｗが演算されると、処理はステップＳ３３に進む。
【０１１９】
ステップＳ３３において、正規化ラプラシアン行列演算部６３は、ステップＳ３２の処理で演算されたインスタンスパターン行列Ｗを式（１）に代入して、インスタンス類似度行列Ａを演算し、そのインスタンス類似度行列Ａを式（４）に代入して、正規化ラプラシアン行列Ｌを演算する。
【０１２０】
演算された正規化ラプラシアン行列Ｌは、正規化ラプラシアン行列保持部４３に保持される。これにより、正規化ラプラシアン行列作成処理は終了する。即ち、図５のステップＳ１２の処理が終了し、処理はステップＳ１３に進む。
【０１２１】
このように、正規化ラプラシアン行列Ｌは、正規化ラプラシアン行列作成処理により、検索クリックスルーログに基づくインスタンスパターン行列Ｗを用いて作成される。このインスタンスパターン行列Ｗの各要素は、原則として、正規化自己相互情報量が採用されるため、ラベル伝播手法におけるラベルの伝播の強度が適切に決定される。
【０１２２】
従って、このような正規化ラプラシアン行列Ｌをカーネルとして用いるラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して類似度が本来よりも高いと評価される、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を向上させることが可能になる。
【０１２３】
なお、上述したように、図１のサジェスチョンクエリ抽出装置に１１において、主処理部２１、準備部２２、及び、準備部２３の各々は、相互に独立かつ並行して処理を実行することができる。従って、図５の正規化ラプラシアン行列作成処理は、サジェスチョンクエリ抽出処理内のステップＳ１２の処理としてのみならず、サジェスチョンクエリ抽出処理とは独立した処理として、実行可能である。例えば、正規化ラプラシアン行列保持部４３に保持されている正規化ラプラシアン行列Ｌを更新する場合にも、正規化ラプラシアン行列作成処理を実行することが可能である。
【０１２４】
以上、本発明の実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更又は改良を加えることができる。そのような変更又は改良を加えた形態も本発明の技術的範囲に含まれる。
【０１２５】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、その順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的或いは個別に実行される処理をも含むものである。
【０１２６】
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
【符号の説明】
【０１２７】
１１ サジェスチョンクエリ抽出装置
１２ ユーザ端末
２１ 主処理部
２２ 準備部
２３ 準備部
３１ 関連クエリ抽出部
３２ 尤度スコア演算部
３３ クエリリストリランキング部
３４ サジェスチョンクエリ送信部
４１ クリックスルーログＤＢ
４２ 正規化ラプラシアン行列作成部
４３ 正規化ラプラシアン行列保持部
５１ 言語資源ＤＢ
５２ 尤度算出言語モデル作成部
５３ 尤度算出言語モデル保持部
６１ 共起頻度集計部
６２ インスタンスパターン行列生成部
６３ 正規化ラプラシアン行列演算部
７１ 正規化自己相互情報量演算部
７２ エッジカット部
【技術分野】
【０００１】
本発明は、サジェスチョンクエリ抽出装置及び方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来のＷｅｂページ検索では、ユーザによりクエリが入力されると、Ｗｅｂページ上の検索エンジンによって、複数のＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）を含む検索結果がユーザに提示される。
【０００３】
さらに、近年のＷｅｂページ検索では、検索結果の提示のみならず、入力されたクエリと関連するクエリが、代替クエリの候補として示唆される。このようなＷｅｂページ検索において代替クエリの候補として示唆されるクエリは、「サジェスチョンクエリ」と呼ばれている。
【０００４】
一般的には、サジェスチョンクエリとして、クエリと構成要素（単語ならば語形）が類似するクエリが提示される。例えば、ユーザが、クエリとして「ホテル」と入力すべきところを誤って「ホデル」と入力してしまった場合、サジェスチョンクエリとして一般的に「ホテル」がユーザに提示される。このようなスペルミスを修正するものもサジェスチョンクエリの一種として捉えることができる。
【０００５】
さらに、クエリと構成要素は非類似であるが、当該クエリと意味が類似するクエリ、例えばクエリが単語ならばいわゆる同義語や類義語についても、サジェスチョンクエリとして提示できれば、ユーザにとって便宜である。例えば上述の例でいえば、さらに「旅館」や「宿屋」といった「ホテル」の類義語についても、サジェスチョンクエリとして提示できれば、ユーザにとって便宜である。
【０００６】
このようなクエリと意味が類似するクエリ（同義語や類義語等）をサジェスチョンクエリとして適切に抽出すべく、本発明者らは、検索クリックスルーログを用いたラベル伝播手法による意味カテゴリの獲得に関する技術を既に提案している（非特許文献１参照）。
【０００７】
ここで、検索クリックスルーとは、ユーザが、クエリを入力した際に、検索エンジンが返す検索結果により示されるスニペット（当該クエリにヒットしたＷｅｂページのタイトル、当該クエリにヒットしたＷｅｂページのＵＲＬ、当該クエリを含むＷｅｂページの一部の断片等で構成されるリスト）をみて、当該Ｗｅｂページの一をクリック（選択）することをいう。
【０００８】
このような検索クリックスルーは、ユーザの意図を直接表していると考えられる。即ち、２以上のクエリの構成要素（語形等）が非類似であっても、同一のＷｅｂページに到達するものは、同じ意図で入力されたクエリである可能性が高いもの同士であると考えられる。特に、同一のＷｅｂページに到達する２以上のクエリは、同義語であることが多いと考えられる。従って、クエリと、クリック（選択）されたＷｅｂページのＵＲＬ（クリック先ＵＲＬ）とを関連付けて記憶した検索クリックスルーログを用いることによって、ユーザにより入力されたクエリに対して、意味が類似するクエリ（同義語や類義語等）をサジェスチョンクエリとして適切に抽出することが可能になる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】小町守、牧本信平、内海慶、颯々野学、“Ｗｅｂページ検索ログを用いたラベル伝播による意味カテゴリ獲得”、研究報告音声言語情報処理（ＳＬＰ）、第２００９−ＳＬＰ−７６巻、第９号、１乃至６ページ、２００９年５月４日
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、検索クリックスルーログの中には、非常に多くのクエリと共起してしまうクリック先ＵＲＬ、即ちいわゆるジェネリックパターンが存在する。このため、意味の類似度が本来低いクエリ同士が、ジェネリックパターンを介して、意味の類似度が本来よりも高いと評価される、といった現象が生ずる。
【００１１】
このような現象が生ずると、いわゆる意味ドリフトが発生して、サジェスチョンクエリの抽出の精度が悪化する。この点、非特許文献１によれば、ラベル伝播手法において、インスタンススコアベクトルは、シードのラベルとグラフ構造どちらを重視するかというパラメータα∈（０，１）を持ち、パラメータαが０に近づけばシードのラベルに偏った結果となり、パラメータαが１に近づけばラベルなしデータから作成されるグラフ構造を考慮した結果となる、とされている。このパラメータαを調整することにより、ある程度は意味ドリフトの発生を抑制することが可能である。しかしながら、あるクエリがジェネリックパターンを含むごく少数のクリック先ＵＲＬのみと共起するような場合には、パラメータαを調整したとしても意味ドリフトの発生を抑制することはできない。
【００１２】
そこで、本発明は、インスタンススコアベクトルのパラメータαの調整によることなくジェネリックパターンの存在に起因して生ずる意味ドリフトを抑制することによって、サジェスチョンクエリの抽出の精度を向上させる、サジェスチョンクエリ抽出装置及び方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、具体的には以下のようなものを提供する。
【００１４】
（１） クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計手段と、
前記頻度集計手段により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成手段と、
前記インスタンスパターン行列生成手段により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算手段と、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算手段により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信手段と、
を備え、
前記インスタンスパターン行列演算手段は、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算手段と、
前記正規化自己相互情報量演算手段により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除手段と、
を有するサジェスチョンクエリ抽出装置。
【００１５】
本発明のこのような構成によれば、正規化ラプラシアン行列は、検索クリックスルーログに基づくインスタンスパターン行列を用いて作成される。このインスタンスパターン行列の各要素として、正規化自己相互情報量が採用されるため、いわゆるジェネリックパターンによる影響を抑制し、ラベル伝播手法におけるラベルの伝播の強度が適切に決定される。従って、このような正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して本来よりも類似度が高いと評価される、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を高めることが可能になる。
【００１６】
（２） 前記クエリを複数含む言語資源ＤＢに基づいて、尤度算出言語モデルを作成する尤度算出言語モデル作成手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記尤度算出言語モデル作成手段により作成された尤度算出言語モデルに基づいて、尤度を、クエリらしさを示す尤度スコアとして演算する尤度スコア演算手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記類似度に加えてさらに、前記尤度スコア演算手段により演算された前記尤度スコアに基づいて、リランキングするリランキング手段と、
をさらに備え、
前記サジェスチョンクエリ送信手段は、前記リランキング手段によるリランキングの結果に従って、前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する、
（１）に記載のサジェスチョンクエリ抽出装置。
【００１７】
本発明のこのような構成によれば、尤度スコアに基づいてリランキングされた結果が用いられて、サジェスチョンクエリが抽出されるので、サジェスチョンクエリの抽出の精度がさらに向上する。
【００１８】
なお、尤度スコアの演算に際して、言語資源ＤＢ及び尤度算出言語モデルとしては、文字や単語の分布に基づいてどのような文字或いは単語がクエリとして生成され易いかが演算可能なものであれば足り、様々なものが採用可能である。具体的には、文字ベースの言語資源ＤＢに基づく文字Ｎｇｒａｍ言語モデル、単語ベースの言語資源ＤＢに基づくｗｏｒｄＮｇｒａｍ言語モデル等、様々なものを採用することができる。
また、尤度は、文字或いは単語の出現頻度等の確率分布を用いて表現することができるが、運用上は浮動小数点演算におけるアンダーフローを防ぐ観点から、自然対数尤度が好適に採用される。
【００１９】
さらに、本発明では、（１）に係る装置に対応する方法及びプログラムを提供する。これにより、（１）と同様の効果が期待できる。
【発明の効果】
【００２０】
本発明によれば、ジェネリックパターンの存在に起因して生ずる意味ドリフトを抑制することによって、サジェスチョンクエリの抽出の精度を向上させることができる。
【図面の簡単な説明】
【００２１】
【図１】本発明に係るサジェスチョンクエリ抽出装置を含む情報処理システムの一実施の形態の機能的構成を示す機能ブロック図である。
【図２】図１のサジェスチョンクエリ抽出装置の関連クエリ抽出部に採用されているラベル伝播手法を説明する図である。
【図３】正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を説明する図である。
【図４】図１のサジェスチョンクエリ抽出装置のうち、正規化ラプラシアン行列をカーネルとして生成するための準備部の機能的構成の詳細を示す機能ブロック図である。
【図５】図１のサジェスチョンクエリ抽出装置が実行するサジェスチョンクエリ抽出処理を例示するすフローチャートである。
【図６】図５のサジェスチョンクエリ抽出処理のうち正規化ラプラシアン行列作成処理を例示するすフローチャートである。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について説明する。なお、これはあくまでも一例であって、本発明の技術的範囲はこれに限られるものではない。
【００２３】
本実施形態は、コンピュータ及びその周辺装置に適用される。本実施形態における各部は、コンピュータ及びその周辺装置が備える、ハードウェア及び該ハードウェアを制御するソフトウェアによって構成される。
【００２４】
上記ハードウェアには、制御部としてのＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）の他、記憶部、通信装置、表示装置及び入力装置が含まれる。記憶部としては、例えば、メモリ（ＲＡＭ：Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ＲＯＭ：Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ等）、ハードディスクドライブ（ＨＤＤ：Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）及び光ディスク（ＣＤ：Ｃｏｍｐａｃｔ Ｄｉｓｋ、ＤＶＤ：Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ等）ドライブが挙げられる。通信装置としては、例えば、各種有線及び無線インターフェース装置が挙げられる。表示装置としては、例えば、液晶ディスプレイ、プラズマディスプレイ等の各種ディスプレイが挙げられる。入力装置としては、例えば、キーボード及びポインティング・デバイス（マウス、トラッキングボール等）が挙げられる。
【００２５】
上記ソフトウェアには、上記ハードウェアを制御するコンピュータ・プログラムやデータが含まれる。コンピュータ・プログラムやデータは、記憶部により記憶され、制御部により適宜実行、参照される。また、コンピュータ・プログラムやデータは、通信回線を介して配布されることも可能であり、ＣＤ−ＲＯＭ等のコンピュータ可読媒体に記録して配布されることも可能である。
【００２６】
図１は、本発明に係るサジェスチョンクエリ抽出装置を含む情報処理システムの一実施の形態の機能的構成を示す機能ブロック図である。
【００２７】
情報処理システムは、サジェスチョンクエリ抽出装置１１と、ユーザ端末１２とが相互に接続されることによって構成されている。
【００２８】
なお、サジェスチョンクエリ抽出装置１１とユーザ端末１２との接続の形態は特に限定されないが、本実施形態では図示せぬインターネットを介してサジェスチョンクエリ抽出装置１１とユーザ端末１２とが接続されているものとする。また、ユーザ端末１２は、実際には複数台存在し得るが、ここでは説明の便宜上１台であるものとする。
【００２９】
サジェスチョンクエリ抽出装置１１は、主処理部２１と、準備部２２，２３とを備えている。
【００３０】
主処理部２１は、ユーザ端末１２から入力されるクエリ（以下、「入力クエリ」と呼ぶ）に基づいて、サジェスチョンクエリを抽出して、ユーザ端末１２に送信する。このため、主処理部２１は、関連クエリ抽出部３１と、尤度スコア演算部３２と、クエリリストリランキング部３３と、サジェスチョンクエリ送信部３４とを備えている。
【００３１】
関連クエリ抽出部３１は、入力クエリと関連する１以上のクエリ（以下、「関連クエリ」と呼ぶ）を抽出してリスト化する。このような１以上の関連クエリを含むリストを、以下、「関連クエリリスト」と呼ぶ。
【００３２】
関連クエリ抽出部３１による関連クエリの抽出手法として、本実施形態では、正規化ラプラシンアン行列をカーネルとして用いるラベル伝播手法に従って、入力クエリをシードとした場合におけるクエリ同士の意味の類似度を演算し、当該類似度に基づいて関連クエリを抽出する、といった手法が採用されている。なお、正規化ラプラシア行列やラベル伝播手法の詳細については後述する。
【００３３】
この場合、関連クエリ抽出部３１は、意味の類似度に基づいて、１以上の関連クエリの各々に対する順位付け（ランキング）を行うこともできる。ここで、意味の類似度の高低を示す値を以下「類似度スコア」と呼ぶものとすると、１以上の関連クエリの各々は、類似度スコアが付加された上で、ランキング順にソートされてリスト化される。このようにして、類似度スコア付の関連クエリリストが生成されて、関連クエリリスト保持部３５に保持される。
【００３４】
尤度スコア演算部３２は、関連クエリリストに含まれる１以上の関連クエリの各々について、文字Ｎｇｒａｍ言語モデルに基づいて、自然対数尤度を、クエリらしさを示す尤度スコアとして演算する。なお、文字Ｎｇｒａｍ言語モデル等の詳細については後述する。
【００３５】
尤度スコア演算部３２により演算された各尤度スコアは、各関連クエリと対応付けられて、関連クエリリストに付加される。即ち、尤度スコア及び類似度スコア付きの関連クエリリストが作成され、関連クエリリスト保持部３５に保持される。
【００３６】
クエリリストリランキング部３３は、関連クエリリストに含まれる１以上の関連クエリの各々について、類似度スコアと尤度スコアの対数の和をそれぞれ演算し、各演算結果に基づいて、１以上の関連クエリのリランキング（再順位付け）を行う。そして、尤度スコア及び類似度スコア付きの関連クエリリストにおいて、１以上の関連クエリの各々が、リランキング順に再ソートされる。
【００３７】
サジェスチョンクエリ送信部３４は、リランキング後の再ソートされた関連クエリリストから、高順位の関連クエリを優先的にサジェスチョンクエリとして抽出して、ユーザ端末１２に送信する。
【００３８】
関連クエリリスト保持部３５は、上述の如く、類似度スコア付きの関連クエリリストや、尤度スコア及び類似度スコア付きの関連クエリリストを保持する。なお、類似度スコア付きの関連クエリリストと、尤度スコア及び類似度スコア付きの関連クエリリストとは、別々のリストとして保持してもよいが、１つのリストとして保持してもよい。ここで、１つのリストとして保持するとは、類似度スコア付きの関連クエリリストに対して、尤度スコアを格納する項目を関連クエリ毎に追加することによって、尤度スコア及び類似度スコア付きの関連クエリリストとして保持することを意味する。
【００３９】
以上、サジェスチョンクエリ抽出装置１１の主処理部２１の機能的構成の概略について説明した。さらに以下、図２及び図３を参照して、主処理部２１のうち、特に関連クエリ抽出部３１の詳細について説明する。
【００４０】
図２は、関連クエリ抽出部３１に採用されているラベル伝播手法を説明する図であって、シードクエリが旅行に関するものである場合におけるラベルの伝播の様子を示す図である。
【００４１】
図２において、左側の丸印によって示されるノードは、クエリ（図２の例では単語のみ）を示している。右側の丸印によって示されるノードは、左側のクエリと共起するパターンを示している。このように、図２に示すグラフは、左側のノードがクエリとなっており、右側のノードがそのクエリと共起するパターンとなっている２部グラフである。当該グラフにおいて、左右のノードを結ぶ線の強さ（図中、太い直線が最も強く、以下、線が細くなるほど、さらに、点線の線部の長さが短くなる程弱くなっていく）が、当該左右のノード間の共起の度合を示している。なお、左右のノードを結ぶ線は、「エッジ」とも呼ばれている。また、各ノードの濃さ（図中丸印内の色の濃さ）が、シードクエリとの関連の強さを表わしている。
【００４２】
ここで、パターンとして示されるＵＲＬ（実際には、「ｈｔｔｐ：／／・・・」といったＵＲＬ）は、クリック先ＵＲＬを意味している。即ち、本実施形態では、シードクエリとの関連の強さの演算に関する学習を高精度に行うべく、パターンとして、従来用いられていたクエリログのみならず、検索クリックスルーログも採用されている。
【００４３】
図２において、左上のノードが、シードクエリとしての単語（以下、「シード単語」と呼ぶ）「航空会社Ａ」であり、所定のラベルが付されているものとする。この場合、シード単語「航空会社Ａ」に付されたラベルが、当該シード単語「航空会社Ａ」と共起の度合いが強いパターン「ＵＲＬ：中部発」に伝搬する。ここで、パターン「ＵＲＬ：中部発」とは、飛行機の発着場所が日本国の中部空港であるという内容を含むＷｅｂページがクリック先ＵＲＬであることを示すものとする。このようなパターン「ＵＲＬ：中部発」は、シードクエリとの関連が強いとして、シード単語「航空会社Ａ」に付されていたラベルが伝播される。
【００４４】
一方、パターン「ＵＲＬ：ツアー」は、歌手Ｂがコマーシャルの出演者として起用された所定のツアーを紹介するＷｅｂページがクリック先ＵＲＬであることを示すものとする。この場合、パターン「ＵＲＬ：ツアー」は、単語「歌手Ｂ」というシードクエリとは異なるクエリとも共起するため、比較的中立なパターンである。
【００４５】
単語「旅行会社Ｃ」は、パターン「ＵＲＬ：中部発」及びパターン「ＵＲＬ：ツアー」をシード単語「航空会社Ａ」と共有しているため、当該シード単語「航空会社Ａ」に付されていたラベルが伝播される。このようにしてラベルが伝播された単語「旅行会社Ｃ」は、シードクエリとの関連が強い単語として分類されることになる。
【００４６】
このように、ラベル伝播手法とは、シードとして与えるノードに付されたラベルを、隣接ノードに順次伝播していく手法をいう。ラベル伝播手法では、最適なラベルは、ラベル伝播のプロセスが収束した状態におけるラベルとして与えられる。
【００４７】
本実施形態では、このようなラベル伝播手法として、正規化ラプラシアン行列をカーネルとして用いる手法が採用されている。そこで、以下、図３を参照して、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法について説明する。
【００４８】
図３は、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法を説明する図である。
【００４９】
図３に示すように、正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法では、入力として、シードインスタンスベクトルＦ（０）と、インスタンス類似度行列Ａとが与えられる。また、学習におけるｔステップ目（ｔは１以上の整数値）の出力としては、インスタンススコアベクトルＦ（ｔ）が得られる。
【００５０】
ここで、あらゆるインスタンスの集合をχと表わすものとする。インスタンスとは、図２における左側のノード、即ちクエリ（単語等）を意味する。あるシードクエリとの関連の強さについて学習する場合、例えば図２の例ではシードクエリが関係する旅行との関連の強さについて学習する場合、ｔステップ目に出力されるインスタンススコアベクトルＦ（ｔ）は、集合χの要素数｜χ｜を次元数とするベクトルとして表わされる。インスタンススコアベクトルＦ（ｔ）のｉ番目（ｉは、１乃至｜χ｜の範囲内の整数値）の次元の要素値としては、集合χのインスタンスｘｉが、どの程度シードクエリと関連があるのか（図２の例では、どの程度旅行との関連があるのか）を示すスコアが採用される。即ち、集合χのインスタンスｘｉの当該シードクエリとの関連の度合を示すスコアが、インスタンススコアベクトルＦ（ｔ）のｉ番目の次元の要素値になる。
【００５１】
従って、あるシードクエリとの関連の強さについて学習する場合において、入力として与えられるシードインスタンスベクトルＦ（０）とは、次のような要素値を有するベクトルとなる。即ち、シードインスタンスベクトルＦ（０）においては、シードとして与えられるインスタンス（図１の関連クエリ抽出部３１にとっては入力クエリ）の集合に、インスタンスｘｉが含まれる場合、ｉ番目の次元の要素値が「１」となり、それ以外の次元の要素値が「０」となる。
【００５２】
また、入力として与えられるインスタンス類似度行列Ａは、インスタンスパターン行列Ｗを用いて、次の式（１）により演算される。
【数１】
・・・（１）
インスタンスパターン行列Ｗとは、例えば、インスタンスｘｉとパターンｐｊの関連性を示す値（従来は単純な共起回数であり、本実施形態では後述する正規化自己相互情報量）をｉ行ｊ列の要素値として有する行列をいう。ここで、従来においては、インスタンスパターン行列Ｗは、次の式（２）によって正規化された上で、式（１）に代入されていた。
【数２】
・・・（２）
ここで、行列Ｄ（Ｎ）は、次の式（３）によって定まる行列Ｎの次数対角行列をいう。
【数３】
・・・（３）
【００５３】
あるシードクエリとの関連の強さについて学習をする場合、シードインスタンスベクトルＦ（０）及びインスタンス類似度行列Ａが入力として与えられて、図３の手順に従った処理が実行されることで、インスタンスベクトルＦ（ｔ）が出力される。
【００５４】
即ち、図３の手順のステップＳ１に示すように、次の式（４）に示す正規化ラプラシアン行列Ｌが作成される。
【数４】
・・・（４）
なお、本実施形態では、後述するように、正規化ラプラシアン行列Ｌは、図１の正規化ラプラシアン行列作成部４２によって作成されて、正規化ラプラシアン行列保持部４３に保持される。
【００５５】
次に、図３の手順のステップＳ２に示すように、ｔステップの演算結果を用いるｔ＋１ステップのインスタンスベクトルＦ（ｔ＋１）を式（５）の演算により求めるといった処理が、ｔが１ずつインクリメントされる毎に繰り返し実行される。そして、収束された段階における式（５）の演算結果が、ｔ＝ｔ＋１としてインクリメントされた後、インスタンスベクトルＦ（ｔ）として出力される。
【数５】
・・・（５）
【００５６】
このようにして出力されたインスタンスベクトルＦ（ｔ）は、シードとして与えられたインスタンスに対して、意味の類似度順にインスタンス（クエリ）が整列したベクトルになっている。
【００５７】
従って、関連クエリ抽出部３１（図１）は、ユーザ端末１２から供給された入力クエリをシードとして、上述のステップＳ１及びＳ２の処理を実行してインスタンスベクトルＦ（ｔ）を演算することで、関連クエリを抽出することができる。即ち、関連クエリ抽出部３１は、当該インスタンスベクトルＦ（ｔ）に基づいて、入力クエリに対する意味の類似度が上位１乃至Ｋ番目（Ｋは１以上の整数値）のインスタンス、即ち、１乃至Ｋ次元の各要素に対応するインスタンスを、Ｋ個の関連クエリとしてそれぞれ抽出することができる。
【００５８】
この場合、インスタンスベクトルＦ（ｔ）の１乃至Ｋ次元の各要素値が、Ｋ個の関連クエリの各々に対して付加される類似度スコアとして採用される。即ち、上述のステップＳ２における式（５）の繰り返し演算とは、各インスタンス（各クエリ）について、類似度スコアに基づくランキング（順位付け）を行い、ランキングの結果順にソートすることと等価である。従って、関連クエリ抽出部３１は、インスタンスベクトルＦ（ｔ）の１乃至Ｋ次元の各要素を抽出することによって、類似度スコア付きの関連クエリリストを作成することができる。
【００５９】
なお、式（５）において、パラメータαは、シードのラベルとグラフ構造とのうち何れを重視するラベル伝播手法であるのかを示すパラメータであって、０乃至１の範囲内で可変する。即ち、パラメータαが０に近付くほど、シードのラベルに偏った結果となり、αが１に近付くほど、ラベルなしデータ（インスタンス）から作成されるグラフ構造を考慮した結果となる。
【００６０】
また、２つのシードクエリとの関連の強さについて学習する場合には、シードとして与えられるインスタンスの各々に対して「１」または「−１」の値が与えられることによって、シードインスタンスベクトルＦ（０）が作成される。そして、最終的なスコアｙｉの符号の正負によって、インスタンスｘｉのラベルが決定される。さらに、３以上のｎ個のシードクエリとの関連の強さについて学習する場合には、シードとしてはベクトルではなくｎ次元の行列が作成されて、ラベル付けが行われる。
【００６１】
次に、図４を参照して、このようなラベル伝播手法においてカーネルとして用いられる正規化ラプラシアン行列の作成手法について説明する。
【００６２】
図４は、図１のサジェスチョンクエリ抽出装置１１のうち、正規化ラプラシアン行列をカーネルとして生成するための準備部２２の機能的構成の詳細を示す機能ブロック図である。
【００６３】
準備部２２は、クリックスルーログＤＢ４１と、正規化ラプラシアン行列作成部４２と、正規化ラプラシアン行列保持部４３とを備えている。
【００６４】
クリックスルーログＤＢ４１は、検索クリックスルーログを記憶している。即ち、クリックスルーログＤＢ４１は、クエリに対する検索結果のクリック先示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数記憶している。
【００６５】
正規化ラプラシアン行列作成部４２は、共起頻度集計部６１と、インスタンスパターン行列生成部６２と、正規化ラプラシアン行列演算部６３とを備えている。
【００６６】
共起頻度集計部６１は、検索クリックスルーログをクリックスルーログＤＢ４１から参照して、各々のクエリについて、関連付けられたクリック先ＵＲＬの数を集計する。ここで、共起頻度集計部６１により集計されたクリック先ＵＲＬの数は、上述の集合χにおけるインスタンスｘｉとしてのクエリと、パターンｐｊとしてのクリック先ＵＲＬの共起回数ｗｉｊに相当する。そこで、共起頻度集計部６１により集計されたクリック先ＵＲＬの数を、以下、「共起頻度」と呼ぶ。
【００６７】
インスタンスパターン行列生成部６２は、共起頻度集計部６１により集計された共起頻度に基づいて、インスタンス（クエリ）とパターン（クリック先ＵＲＬ）の関連を示すインスタンスパターン行列を演算する。
【００６８】
正規化ラプラシアン行列演算部６３は、当該インスタンスパターン行列を用いて、上述した式（４）を演算することで、正規化ラプラシアン行列を演算する。
【００６９】
正規化ラプラシアン行列保持部４３は、正規化ラプラシアン行列作成部４２により作成された正規化ラプラシアン行列を、カーネルとして保持する。
【００７０】
なお、正規化ラプラシアン行列に必要なインスタンス類似度行列Ａは、上述の如く式（１）に従って演算されるが、非常に大規模な行列であるため、記憶容量が非常に大きくなる場合がある。このような場合には、正規化ラプラシアン行列保持部４３が、インスタンスパターン行列Ｗ及びその転置行列ＷＴのみを保持し、正規化ラプラシアン行列演算部６３が、式（１）を毎回演算することによって、記憶容量を削減することができる。インスタンス類似度行列Ａが密行列であるのに対して、インスタンスパターン行列Ｗは疎行列であるからである。
【００７１】
さらに、以下、正規化ラプラシアン行列をカーネルとして作成するために必要なインスタンスパターン行列について説明する。
【００７２】
［背景技術］の欄でも上述したように、クリック先ＵＲＬの中には、非常に多くのクエリと共起してしまうジェネリックパターンが存在する。このため、意味の類似度が低いクエリ同士がジェネリックパターンを介して本来よりも類似度が高いと評価されてしまう、といった現象が従来生じていた。
【００７３】
換言すると、ラベル伝播手法においては、伝播元のインスタンス（クエリ）から、それと共通するパターン（クリック先ＵＲＬ）を持つ伝播先のインスタンスに対してラベルが伝搬される。この場合、伝播の強さは、伝播先のインスタンスからの伝播の広がりが考慮される。このため、従来のラベル伝播手法には、次のような第１の特徴及び第２の特徴が存在した。即ち、第１の特徴とは、伝播先のインスタンスが大量のパターンを持っているような場合には伝播が弱くなる、といった特徴である。また、第２の特徴とは、伝播先のインスタンスが少量のパターンしか持たない場合には強く伝搬する、といった特徴である。第２の特徴が顕著に表れた例としては、伝播先のインスタンスが、１つのパターンしか持たず、伝播元のインスタンスとそのパターンのみで繋がっている場合である。このような場合には、伝播先のインスタンスが、１つのジェネリックパターンのみを持つような場合であっても、強く伝搬されてしまうことになる。強く伝搬されるということは、たとえジェネリックパターン１つのみで繋がる伝播元と伝播先のインスタンス同士であっても、即ち意味の類似度が本来低いインスタンス同士であっても、意味の類似度が本来より高いと評価されてしまうことを意味する。
【００７４】
ここで、従来のラベル伝播手法の第２の特徴、即ち、伝播先のインスタンスが少量のパターンしか持たない場合には強く伝搬するという特徴は、インスタンスパターン行列Ｗの正規化処理に起因して生ずる。
【００７５】
即ち、従来においては、上述した式（２）に示すように、次数対角行列の逆行列Ｄ−１（Ｗ）が、インスタンスパターン行列Ｗの左側に掛けられることで、当該インスタンスパターン行列Ｗが正規化されていた。具体的には、インスタンスパターン行列Ｗの各行は、各インスタンス（各クエリ）に対応しており、所定行の各要素値は、対応するインスタンスと各パターン（クリック先ＵＲＬ）との共起回数（クリックされた回数）に基づく値である。このような各インスタンスに対応する各行において、各要素値の総和がそれぞれ「１」になるように正規化されていた。
【００７６】
このため、従来においては、多くのパターンと共起するインスタンスに対応する行については、各要素値は小さくなっていた。また、共起するパターンの分布に偏りがあるインスタンスに対応する行については、偏って共起するパターンに対応する要素値が大きくなっていた。
【００７７】
一方で、従来においては、共起するパターンが少数のインスタンスに対応する行については、各要素値は大きくなっていた。極端な例を挙げると、共起するパターンが１つしか存在しない場合には、当該パターンに対応する要素値は必ず「１」になっていた。このように要素値が必ず「１」になることは、当該パターンがジェネリックパターンであったとしても何ら変わらない。
【００７８】
このように、式（２）によって正規化された従来のインスタンスパターン行列Ｗは、ジェネリックパターン以外に共起するパターンをほとんど持たないインスタンスに対応する行であって、当該ジェネリックパターンに対応する要素値が「１」に近くなっている行を有している。従来、このような式（２）によって正規化されたインスタンスパターン行列Ｗからラプラシアン行列Ｌが作成され、当該ラプラシアン行列Ｌを用いるラベル伝播手法に従って学習が行われていた。その結果、ジェネリックパターン以外に共起するパターン（クリック先ＵＲＬ）をほとんど持たないインスタンス（クエリ）が、シードとして与えられたインスタンス（シードのクエリ）との意味の類似度が高くなってしまう傾向にあった。即ち、ジェネリックパターン以外に共起するパターンをほとんど持たないインスタンスと、シードとして与えられたインスタンスとは、意味の類似度が本来低いクエリ同士に該当する。このような意味の類似度が本来低いクエリ同士が、ジェネリックパターンを介して、意味の類似度が本来よりも高いと評価されてしまう、といった現象が生じてしまう傾向にあった。
【００７９】
そこで、このような現象が生ずることを抑制すべく、図４に示すように、本実施形態のインスタンスパターン行列生成部６２は、正規化自己相互情報量演算部７１と、エッジカット部７２とを備えている。
【００８０】
正規化自己相互情報量演算部７１は、インスタンスパターン行列Ｗの各要素値として、正規化自己相互情報量（ＮＰＭＩ：Ｎｏｒｍａｌｉｚｅｄ Ｐｏｉｎｔｗｉｓｅ Ｍｕｔｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ）を演算する。以下、この正規化自己相互情報量について説明する。
【００８１】
正規化される前の自己相互情報量（ＰＭＩ：Ｐｏｉｎｔｗｉｓｅ Ｍｕｔｕａｌ Ｉｎｆｏｒｍａｔｉｏｎ）は、次の式（６）により示される。
【数６】
・・・（６）
式（６）において、ｉ（ｘ，ｐ）が、インスタンスｘとパターンｐとの自己相互情報量を示している。即ち、式（６）の右辺において、インスタンスｘとパターンｐとが互いに独立であると仮定して求めた確率分布がｐ（ｘ）ｐ（ｐ）であり、実際に観測された確率分布がｐ（ｘ，ｐ）である。式（６）の右辺に示すように、これらの２つの確率分布の情報量の差が自己相互情報量ｉ（ｘ，ｐ）として求められる。
【００８２】
ここで、自己相互情報量ｉ（ｘ，ｐ）の値として取り得る範囲は［−∞乃至＋∞］であり、２つの確率分布が一致する際には自己相互情報量ｉ（ｘ，ｐ）は０になる。従って、自己相互情報量ｉ（ｘ，ｐ）をそのままインスタンスパターン行列Ｗの各要素値として採用すると、従来の共起回数を要素値としていた場合に「０」となっていた要素値が、全て「−∞」となってしまい、演算が不可能になってしまう。そこで、本実施形態では、次の式（７）に示すように、自己相互情報量ｉ（ｘ，ｐ）が正規化され、その結果得られる正規化自己相互情報量ｉｎ（ｘ，ｐ）が、原則、インスタンスパターン行列Ｗの各要素値として採用される。
【数７】
・・・（７）
【００８３】
式（７）に示すように、正規化自己相互情報量ｉｎ（ｘ，ｐ）は、自己相互情報量ｉ（ｘ，ｐ）が（−ｌｎｐ（ｘ，ｐ））で除算されることによって正規化されたものであり、その値が取り得る範囲は［−１乃至＋１］となる。確率分布ｐ（ｘ，ｐ）が０のとき、正規化自己相互情報量ｉｎ（ｘ，ｐ）は−１になる。また、確率分布ｐ（ｘ），ｐ（ｐ）が相互に独立の場合には、正規化自己相互情報量ｉｎ（ｘ，ｐ）は０になる。そして、インスタンスｘとパターンｐとが互いに共起する場合には、正規化自己相互情報量ｉｎ（ｘ，ｐ）は１になる。
【００８４】
本実施形態では、図４のインスタンスパターン行列生成部６２の正規化自己相互情報量演算部７１が、式（７）に従って、インスタンスパターン行列Ｗの各要素毎に、正規化自己相互情報量ｉｎ（ｘ，ｐ）を演算する。
【００８５】
しかしながら、インスタンスパターン行列Ｗの各要素値として何れも、式（７）の正規化自己相互情報量ｉｎ（ｘ，ｐ）を採用すると、半正定値性が崩れるために、正規化ラプラシアン行列を用いたラベル伝播手法の適用が不可能になる。そこで、本実施形態では、次の式（８）に従って、インスタンスパターン行列Ｗの各要素値ｗ（ｘ，ｐ）が演算される。
【数８】
・・・（８）
式（８）において、右辺の［α］ｔｈは、閾値ｔｈ以下の場合、入力値αを削除し（入力値αを入力としてはみずに、出力せず）、閾値ｔｈを超えている場合、入力値αをそのまま出力する関数を意味している。ここで、閾値ｔｈは、半正定値性を満足させるために０以上の値である必要がある。
【００８６】
例えば閾値ｔｈが０の場合には、式（８）の右辺は、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるときには、当該負の値はみないということを意味している。即ち、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるということは、インスタンスｘとパターンｐとの間に負の相関があるということであり、この組み合わせは発生しにくいことを表しているため、みないということである。
【００８７】
ラベル伝播手法の観点で換言すると、正規化自己相互情報量ｉｎ（ｘ，ｐ）が負の値であるということは、インスタンスｘとパターンｐとはエッジが張られにくいことを意味している。即ち、図２の例でいうと、インスタンスｘを示す左側のノードと、パターンｐを示す右側のノードとを結ぶ線（エッジ）の強さが弱いということを意味している。ここで、正規化自己相互情報量ｉｎ（ｘ，ｐ）を用いる意義は、ラベルを伝搬させる強さが適切に決定される点にある。従って、エッジの張り方は直接観測したデータから決定されるため、負の値の正規化自己相互情報量ｉｎ（ｘ，ｐ）を削除しても、即ちエッジを削除しても、ラベルの伝搬の強さを適切にするという点で特に問題とならない。また、正規化自己相互情報量ｉｎ（ｘ，ｐ）が０となる要素については、インスタンスｘとパターンｐとは互いに独立であると判断できるので、エッジを削除しても、ラベルの伝搬の強さを適切にするという点で特に問題とならない。
【００８８】
本実施形態では、図４のインスタンスパターン行列生成部６２のエッジカット部７２が、このような式（８）を演算することによって、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈ以下の要素におけるエッジを削除する。即ち、インスタンスパターン行列Ｗの各要素のうち、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈを超える要素については、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値がそのまま要素値として採用される。これに対して、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値が閾値ｔｈ以下の要素については、正規化自己相互情報量ｉｎ（ｘ，ｐ）の値は要素値として採用されず、例えば所定の固定値が採用される。
【００８９】
なお、上述したように、エッジを削除する基準となる閾値ｔｈは、半正定値性を満足させる必要があるため、負値は採用できないが、０を採用する必要は特になく、１以下の任意の正値を採用することができる。
【００９０】
このように、本実施形態では、上述した正規化自己相互情報量演算部７１及びエッジカット部７２を含むインスタンスパターン行列生成部６２が、式（７）及び式（８）に従ってインスタンスパターン行列Ｗを演算して、正規化ラプラシアン行列演算部６３に供給する。当該インスタンスパターン行列Ｗの各要素は、原則として（閾値ｔｈを超えているものは）、正規化自己相互情報量が採用されているため、ラベル伝播手法におけるラベルの伝播の強度を適切に決定することができる。
【００９１】
正規化ラプラシアン行列演算部６３は、当該インスタンスパターン行列Ｗを用いて上述した式（１）を演算することによって、インスタンス類似度行列Ａを演算する。そして、正規化ラプラシアン行列演算部６３は、このインスタンス類似度行列Ａを用いて式（４）を演算することで、正規化ラプラシアン行列Ｌを演算し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。
【００９２】
以上説明したように、本実施形態の正規化ラプラシアン行列作成部４２により作成された正規化ラプラシアン行列Ｌをカーネルとして用いて、ラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して意味の類似度が本来よりも高いと評価されてしまう、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を高めることが可能になる。
【００９３】
以上、図１のサジェスチョンクエリ抽出装置１１のうち、正規化ラプラシアン行列Ｌをカーネルとして作成する準備部２２について説明した。
次に、図１のサジェスチョンクエリ抽出装置１１のうち、尤度算出言語モデルを作成する準備部２３について説明する。
【００９４】
準備部２３は、言語資源ＤＢ５１と、尤度算出言語モデル作成部５２と、尤度算出言語モデル保持部５３と、を備えている。なお、言語資源ＤＢ５１、尤度算出言語モデル作成部５２及び尤度算出言語モデル保持部５３としては、具体的には、文字や単語の分布に基づいてどのような文字或いは単語がクエリとして生成され易いかが演算可能なものであれば足り、様々なものが採用可能である。例えば、文字ベースの言語資源ＤＢに基づく文字Ｎｇｒａｍ言語モデル、単語ベースの言語資源ＤＢに基づくｗｏｒｄＮｇｒａｍ言語モデル等、様々なものを採用することができる。以下、これらの一例を取り上げて説明を続ける。
【００９５】
言語資源ＤＢ５１は、これまでにクエリとして用いられた多数のクエリのログ、即ちいわゆるクエリログを記憶している。
【００９６】
尤度算出言語モデル作成部５２は、言語資源ＤＢ５１に記憶されたクエリログに基づいて、尤度算出言語モデルを作成する。即ち、尤度算出言語モデル作成部５２は、クエリとしての文字或いは単語ｗを、ｗ＝｛ｘ［１］，ｘ［２］，・・・，ｘ［ｎ］｝という文字或いは単語の並びと把握して、自然対数尤度を演算することによって、尤度算出言語モデルを作成する。
【００９７】
より具体的には、例えば、尤度算出言語モデル作成部５２は、
ｌｎＰ（ｗ）
＝ΣｌｎＰ（ｘ［ｉ］｜｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ−１］｝）
＝Σ｛ｌｎ（ｆｒｅｑ（｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ］｝））−ｌｎ（ｆｒｅｑ（｛ｘ［ｉ−Ｎ＋１］，．．．，ｘ［ｉ−１］｝））｝
の式に従って、自然対数尤度を計算する。
なお、この実施形態では自然対数尤度を計算しているが、あくまで一例であって、クエリらしさを表現可能な様々なものが採用可能である。
【００９８】
尤度算出言語モデル保持部５３は、尤度算出言語モデル作成部５２により作成された文字Ｎｇｒａｍ言語モデルを保持する。
【００９９】
以上、図１を参照して、本発明に係るサジェスチョンクエリ提供システムの一実施の形態の機能的構成について説明した。
次に、このようなサジェスチョンクエリ提供処理システムのうち、サジェスチョンクエリ抽出装置１１が実行する一連の処理（以下、「サジェスチョンクエリ抽出処理」と称する）の流れについて説明する。
【０１００】
図５は、サジェスチョンクエリ抽出処理を例示するすフローチャートである。
【０１０１】
ステップＳ１１において、図１の正規化ラプラシアン行列作成部４２は、正規化ラプラシアン行列保持部４３を参照して、正規化ラプラシアン行列が作成済であるか否かを判定する。
【０１０２】
正規化ラプラシアン行列が作成済みの場合、ステップＳ１１においてＹＥＳであると判定されて、処理はステップＳ１３に進む。なお、ステップＳ１３以降の処理については後述する。
【０１０３】
これに対して、正規化ラプラシアン行列が未作成の場合、ステップＳ１１においてＮＯであると判定されて、処理はステップＳ１２に進む。
ステップＳ１２において、正規化ラプラシアン行列作成部４２は、正規化ラプラシアン行列を作成し、カーネルとして正規化ラプラシアン行列保持部４３に保持させる。なお、このようなステップＳ１２の処理を、以下、「正規化ラプラシアン行列作成処理」と呼ぶ。正規化ラプラシアン行列作成処理の詳細については、図６を参照して後述する。
ステップＳ１２の正規化ラプラシアン行列作成処理が実行されると、処理はステップＳ１３に進む。
【０１０４】
ステップＳ１３において、尤度算出言語モデル作成部５２は、尤度算出言語モデル保持部５３を参照して、尤度算出言語モデルが作成済であるか否かを判定する。
【０１０５】
尤度算出言語モデルが作成済みの場合、ステップＳ１３においてＹＥＳであると判定されて、処理はステップＳ１５に進む。なお、ステップＳ１５以降の処理については後述する。
【０１０６】
これに対して、尤度算出言語モデルが未作成の場合、ステップＳ１３においてＮＯであると判定されて、処理はステップＳ１４に進む。
ステップＳ１４において、尤度算出言語モデル作成部５２は、尤度算出言語モデルを作成し、尤度算出言語モデル保持部５３に保持させる。これにより、処理はステップＳ１５に進む。
【０１０７】
ステップＳ１５において、関連クエリ抽出部３１は、ユーザ端末１２から入力クエリが供給されたか否かを判定する。
ユーザ端末１２から入力クエリが供給されてこない場合、ステップＳ１５においてＮＯであると判定されて、処理はステップＳ１５に再度戻される。即ち、ユーザ端末１２から入力クエリが供給されてくるまでの間、ステップＳ１５の判定処理が繰り返し実行されることで、サジェスチョンクエリ抽出処理が待機状態になる。
その後、ユーザ端末１２から入力クエリが供給されてくると、ステップＳ１５においてＹＥＳであると判定されて、処理はステップＳ１６に進む。
【０１０８】
ステップＳ１６において、関連クエリ抽出部３１は、類似度スコア付きの関連クエリリストを作成する。即ち、関連クエリ抽出部３１は、ステップＳ１２の処理で作成された正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、入力クエリをシードとした場合におけるクエリ同士の意味の類似度スコアを演算する。そして、関連クエリ抽出部３１は、類似度スコアが高いクエリを優先して、当該類似度スコア付きの関連クエリとして抽出し、これらを類似度スコアに基づくランキング順にソートすることによって、類似度スコア付き関連クエリリストを作成する。
【０１０９】
ステップＳ１７において、尤度スコア演算部３２は、ステップＳ１６の処理で作成された関連クエリリストに含まれる１以上の関連クエリの各々について、尤度スコアを演算し、関連クエリリストに付加する。即ち、尤度スコア演算部３２は、ステップＳ１４の処理で作成された文字Ｎｇｒａｍ言語モデルに基づいて、自然対数尤度を、クエリらしさを示す尤度スコアとして演算する。そして、尤度スコア演算部３２は、尤度スコア及び類似度スコア付きの関連クエリリストを作成する。
【０１１０】
ステップＳ１８において、クエリリストリランキング部３３は、関連クエリリストに含まれる１以上の関連クエリの各々について、類似度スコアと尤度スコアの対数の和をそれぞれ演算し、各演算結果に基づいて、１以上の関連クエリのリランキング（再順位付け）を行う。その結果、尤度スコア及び類似度スコア付きの関連クエリリストにおいて、１以上の関連クエリの各々が、リランキング順に再ソートされる。
【０１１１】
ステップＳ１９において、サジェスチョンクエリ送信部３４は、リランキング後の再ソートされた関連クエリリストから、リランキングの結果高順位となっている幾つかの関連クエリを優先して、サジェスチョンクエリとして抽出して、ユーザ端末１２に送信する。これにより、サジェスチョンクエリ抽出処理は終了となる。
【０１１２】
なお、ステップＳ１５乃至Ｓ１９の処理は、正規化ラプラシアン行列及び尤度算出言語モデルが作成済みの状態であれば実行可能である。従って、ステップＳ１５の処理の開始タイミングは、ステップＳ１１乃至Ｓ１４の処理の終了後であれば足りる。即ち、ステップＳ１１乃至Ｓ１４の処理の終了後、時間的に連続して即座に、ステップＳ１５の処理が開始される必要は特になく、時間的に離間して、ステップＳ１５の処理が開始されてもよい。
【０１１３】
換言すると、図１のサジェスチョンクエリ抽出装置に１１において、主処理部２１、準備部２２、及び、準備部２３の各々は、相互に独立かつ並行して処理を実行することができる。従って、例えば準備部２２は、サジェスチョンクエリ抽出処理とは独立して、正規化ラプラシアン行列保持部４３に保持されている正規化ラプラシアン行列を適宜更新しても構わない。同様に、例えば準備部２３は、サジェスチョンクエリ抽出処理とは独立して、尤度算出言語モデル保持部５３に保持されている尤度算出言語モデルを適宜更新しても構わない。
【０１１４】
次に、図５のサジェスチョンクエリ抽出処理のうち、ステップＳ１２の正規化ラプラシアン行列作成処理の流れについて説明する。
【０１１５】
図６は、正規化ラプラシアン行列作成処理を例示するすフローチャートである。
【０１１６】
ステップＳ３１において、図４の正規化ラプラシアン行列作成部４２の共起頻度集計部６１は、検索クリックスルーログに基づいて、共起頻度を集計する。即ち、共起頻度集計部６１は、検索クリックスルーログをクリックスルーログＤＢ４１から参照して、各々のクエリについて、関連付けられたクリック先ＵＲＬ（検索クリックスロー）の数を、共起頻度として集計する。
【０１１７】
ステップＳ３２において、インスタンスパターン行列生成部６２は、ステップＳ３１の処理で集計された共起頻度に基づいて、インスタンスパターン行列Ｗを生成する。
【０１１８】
具体的には、インスタンスパターン行列生成部６２の正規化自己相互情報量演算部７１は、インスタンスパターン行列Ｗの各要素毎に、上述した式（７）に従って、正規化自己相互情報量ｉｎ（ｘ，ｐ）をそれぞれ演算する。次に、エッジカット部７２は、上述した式（８）に従って、インスタンスパターン行列Ｗの各要素毎に演算された正規化自己相互情報量ｉｎ（ｘ，ｐ）のうち、閾値ｔｈ（例えばｔｈ＝０）以下の要素を削除する。これにより、削除された要素におけるインスタンスｘとパターンｐとのエッジが削除される。このようにして、インスタンスパターン行列Ｗが演算されると、処理はステップＳ３３に進む。
【０１１９】
ステップＳ３３において、正規化ラプラシアン行列演算部６３は、ステップＳ３２の処理で演算されたインスタンスパターン行列Ｗを式（１）に代入して、インスタンス類似度行列Ａを演算し、そのインスタンス類似度行列Ａを式（４）に代入して、正規化ラプラシアン行列Ｌを演算する。
【０１２０】
演算された正規化ラプラシアン行列Ｌは、正規化ラプラシアン行列保持部４３に保持される。これにより、正規化ラプラシアン行列作成処理は終了する。即ち、図５のステップＳ１２の処理が終了し、処理はステップＳ１３に進む。
【０１２１】
このように、正規化ラプラシアン行列Ｌは、正規化ラプラシアン行列作成処理により、検索クリックスルーログに基づくインスタンスパターン行列Ｗを用いて作成される。このインスタンスパターン行列Ｗの各要素は、原則として、正規化自己相互情報量が採用されるため、ラベル伝播手法におけるラベルの伝播の強度が適切に決定される。
【０１２２】
従って、このような正規化ラプラシアン行列Ｌをカーネルとして用いるラベル伝播手法を適用することで、意味の類似度が本来低いクエリ同士がジェネリックパターンを介して類似度が本来よりも高いと評価される、といった現象の発生頻度を抑制することができる。その結果、意味ドリフトが抑制されて、関連クエリの抽出の精度、即ち、サジェスチョンクエリの抽出の精度を向上させることが可能になる。
【０１２３】
なお、上述したように、図１のサジェスチョンクエリ抽出装置に１１において、主処理部２１、準備部２２、及び、準備部２３の各々は、相互に独立かつ並行して処理を実行することができる。従って、図５の正規化ラプラシアン行列作成処理は、サジェスチョンクエリ抽出処理内のステップＳ１２の処理としてのみならず、サジェスチョンクエリ抽出処理とは独立した処理として、実行可能である。例えば、正規化ラプラシアン行列保持部４３に保持されている正規化ラプラシアン行列Ｌを更新する場合にも、正規化ラプラシアン行列作成処理を実行することが可能である。
【０１２４】
以上、本発明の実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更又は改良を加えることができる。そのような変更又は改良を加えた形態も本発明の技術的範囲に含まれる。
【０１２５】
なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、その順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的或いは個別に実行される処理をも含むものである。
【０１２６】
また、本明細書において、システムとは、複数の装置や処理部により構成される装置全体を表すものである。
【符号の説明】
【０１２７】
１１ サジェスチョンクエリ抽出装置
１２ ユーザ端末
２１ 主処理部
２２ 準備部
２３ 準備部
３１ 関連クエリ抽出部
３２ 尤度スコア演算部
３３ クエリリストリランキング部
３４ サジェスチョンクエリ送信部
４１ クリックスルーログＤＢ
４２ 正規化ラプラシアン行列作成部
４３ 正規化ラプラシアン行列保持部
５１ 言語資源ＤＢ
５２ 尤度算出言語モデル作成部
５３ 尤度算出言語モデル保持部
６１ 共起頻度集計部
６２ インスタンスパターン行列生成部
６３ 正規化ラプラシアン行列演算部
７１ 正規化自己相互情報量演算部
７２ エッジカット部
【特許請求の範囲】
【請求項１】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計手段と、
前記頻度集計手段により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成手段と、
前記インスタンスパターン行列生成手段により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算手段と、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算手段により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合におけるクエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信手段と、
を備え、
前記インスタンスパターン行列演算手段は、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算手段と、
前記正規化自己相互情報量演算手段により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除手段と、
を有するサジェスチョンクエリ抽出装置。
【請求項２】
前記クエリを複数含む言語資源ＤＢに基づいて、尤度算出言語モデルを作成する尤度算出言語モデル作成手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記尤度算出言語モデル作成手段により作成された尤度算出言語モデルに基づいて、尤度を、クエリらしさを示す尤度スコアとして演算する尤度スコア演算手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記類似度に加えてさらに、前記尤度スコア演算手段により演算された前記尤度スコアに基づいて、リランキングするリランキング手段と、
をさらに備え、
前記サジェスチョンクエリ送信手段は、前記リランキング手段によるリランキングの結果に従って、前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する、
請求項１に記載のサジェスチョンクエリ抽出装置。
【請求項３】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置が実行するサジェスチョンクエリ抽出方法であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計ステップと、
前記頻度集計ステップの処理により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成ステップと、
前記インスタンスパターン行列生成ステップの処理により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算ステップと、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算ステップの処理により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出ステップと、
前記関連クエリ抽出ステップの処理により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信ステップと、
を含み、
前記インスタンスパターン行列演算ステップは、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算ステップと、
前記正規化自己相互情報量演算ステップの処理により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除ステップと、
を含むサジェスチョンクエリ抽出方法。
【請求項４】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置を制御するコンピュータに、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計ステップと、
前記頻度集計ステップの処理により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成ステップと、
前記インスタンスパターン行列生成ステップの処理により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算ステップと、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算ステップの処理により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出ステップと、
前記関連クエリ抽出ステップの処理により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する制御を実行するサジェスチョンクエリ送信制御ステップと、
を含み、
前記インスタンスパターン行列演算ステップは、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算ステップと、
前記正規化自己相互情報量演算ステップの処理により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除ステップと、
を含む制御処理を実行させるプログラム。
【請求項１】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計手段と、
前記頻度集計手段により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成手段と、
前記インスタンスパターン行列生成手段により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算手段と、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算手段により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合におけるクエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信手段と、
を備え、
前記インスタンスパターン行列演算手段は、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算手段と、
前記正規化自己相互情報量演算手段により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除手段と、
を有するサジェスチョンクエリ抽出装置。
【請求項２】
前記クエリを複数含む言語資源ＤＢに基づいて、尤度算出言語モデルを作成する尤度算出言語モデル作成手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記尤度算出言語モデル作成手段により作成された尤度算出言語モデルに基づいて、尤度を、クエリらしさを示す尤度スコアとして演算する尤度スコア演算手段と、
前記関連クエリ抽出手段により抽出された前記関連クエリについて、前記類似度に加えてさらに、前記尤度スコア演算手段により演算された前記尤度スコアに基づいて、リランキングするリランキング手段と、
をさらに備え、
前記サジェスチョンクエリ送信手段は、前記リランキング手段によるリランキングの結果に従って、前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する、
請求項１に記載のサジェスチョンクエリ抽出装置。
【請求項３】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置が実行するサジェスチョンクエリ抽出方法であって、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計ステップと、
前記頻度集計ステップの処理により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成ステップと、
前記インスタンスパターン行列生成ステップの処理により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算ステップと、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算ステップの処理により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出ステップと、
前記関連クエリ抽出ステップの処理により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信するサジェスチョンクエリ送信ステップと、
を含み、
前記インスタンスパターン行列演算ステップは、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算ステップと、
前記正規化自己相互情報量演算ステップの処理により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除ステップと、
を含むサジェスチョンクエリ抽出方法。
【請求項４】
クエリに対する検索結果のクリック先を示すクリック先ＵＲＬと、当該クエリとが関連付けられた履歴情報を複数含むクリックスルーログに基づいて、ユーザ端末から新たなクエリとして入力される入力クエリに対して、意味の類似するサジェスチョンクエリを抽出するサジェスチョンクエリ抽出装置を制御するコンピュータに、
前記クリックスルーログを参照して、各々の前記クエリについて、関連付けられた前記クリック先ＵＲＬの数を、共起頻度として集計する頻度集計ステップと、
前記頻度集計ステップの処理により集計された前記共起頻度に基づいて、インスタンスとしての前記クエリと、パターンとしての前記クリック先ＵＲＬとの関連を示すインスタンスパターン行列を生成するインスタンスパターン行列生成ステップと、
前記インスタンスパターン行列生成ステップの処理により生成されたインスタンスパターン行列に基づいて、前記インスタンスとしての前記クエリと共起クエリとの関連を示す正規化ラプラシアン行列をカーネルとして演算する正規化ラプラシアン行列演算ステップと、
前記ユーザ端末から前記入力クエリを受け付けたことに応じて、前記正規化ラプラシアン行列演算ステップの処理により演算された前記正規化ラプラシアン行列をカーネルとして用いるラベル伝播手法に従って、前記入力クエリをシードとした場合における、クエリ同士の意味の類似度スコアを演算し、前記類似度スコアが高いクエリを優先して関連クエリとして抽出する関連クエリ抽出ステップと、
前記関連クエリ抽出ステップの処理により抽出された前記関連クエリの中から、前記類似度スコアに基づくランキングに従って、前記入力クエリに対する前記サジェスチョンクエリを抽出して、前記ユーザ端末に送信する制御を実行するサジェスチョンクエリ送信制御ステップと、
を含み、
前記インスタンスパターン行列演算ステップは、
前記インスタンスパターン行列の各要素毎に、正規化自己相互情報量を演算する正規化自己相互情報量演算ステップと、
前記正規化自己相互情報量演算ステップの処理により各要素毎に演算された各々の前記正規化自己相互情報量のうち、所定の閾値以下の正規化自己相互情報量を持つ要素を削除することによって、当該要素におけるインスタンスとパターンとを結ぶエッジを削除するエッジ削除ステップと、
を含む制御処理を実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１２−７９０２９（Ｐ２０１２−７９０２９Ａ）
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願番号】特願２０１０−２２２７８９（Ｐ２０１０−２２２７８９）
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
【公開日】平成２４年４月１９日（２０１２．４．１９）
【国際特許分類】
【出願日】平成２２年９月３０日（２０１０．９．３０）
【出願人】（５００２５７３００）ヤフー株式会社 (1,128)
【Ｆターム（参考）】
[ Back to top ]