パーティクルのセットを変換するための方法、およびパーティクルの出力セットを生成する方法
本発明の実施の形態は、情報検索システムにおいて用いるのに適した単語のセットを表すパーティクルの出力セットにおいて、パーティクルのセットを変換するためのシステムおよび方法を開示する。本方法は、パーティクルのセット内の各パーティクルについて、パーティクルの一部分の組合せを生成し、パーティクルのセット内のパーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの部分と置き換える。例えば、本方法は、パーティクルのセット内の各パーティクルのMEDを求め、各パーティクルのMEDの和としてパーティクルのセットの総MEDを求め、次に、該パーティクルのセットの総MEDを最大にする組合せを求める。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、包括的には情報検索に関し、特に、パーティクル間の編集距離の最大化を用いてパーティクルのセットを変換することに関する。
【背景技術】
【0002】
情報検索(IR)システムは、通常、地理的関心地点(points of interest:POI)、または音楽アルバムの題名のようなアイテムの大規模なリストを含む。リストは、インデックスによってアクセスされる。インデックスに対する入力は、ユーザーによって供給されるクエリである。クエリに応答して、IRシステムは、該クエリに最も一致した結果リストを生成する。この結果リストは、様々な要因に従って順序付けすることができる。結果リスト、インデックス、クエリ、および結果リストは、通常、単語によって表される。入力リスト、クエリ、および結果リストは、テキストによるものであるか、または発話によるものである。
【0003】
発話によるクエリは、ユーザーがキーボードを使用することができない環境、例えば、運転中、またはユーザーインタフェースがマイクロフォンを含む環境において用いられる。これらの環境では、自動音声認識装置(ASR)を用いて発話を単語に変換する。
【0004】
ASRは、2つの基本データ構造、単語の発音辞書および単語の言語モデルを用いる。一般に、IRシステムは、単語を音素として音声的に表す。例えば、RESTAURANTは「R EH S T R AA N T」として表される。音素は、特定の言語における音の基本単位を指す。音素は、強勢符号、音節境界、および単語がどのように発音されるかを示す他の表記を含むことができる。
【0005】
言語モデルは、語順の確率を記述し、ASRによって、正しい単語仮説のための探索を制約するのに用いられる。言語モデルは、nグラム(n-gram)とすることができる。nグラムが二重字(bigram)である場合、二重字によってP(「BELL」|「TACO」)のような確率がリストされる。これは、単語「TACO」の後に単語「BELL」が続く確率である。言語モデルは、有限状態文法とすることもでき、ここで、文法の状態は、各状態において現れる可能性がある単語を表し、状態間の遷移は、1つの状態から別の状態に向かう確率を表す。
【0006】
単語ベースのIRには、2つの主な問題が存在する。
【0007】
第1に、IRに重要な単語は、通常、頻度の低い識別語である。例えば、アイテムPOI「MJ’S RESTAURANT」において、重要な識別語は「MJ’S」である。多くの場合、これらの識別語は、他の言語からの固有名詞である。例えば、アイテム「AASHIANI RESTAURANT」内の単語「AASHIANI」は、ヒンディー語からのものである。これらの識別語の別の現れ方は、「GREENHOUSE」のように、組み合わせを通じたものである。単語の語根を変更することによって、語彙のサイズも増大する。通例、頻度が低いが重要である識別語の数は、非常に多い。
【0008】
加えて、重要な識別語は、多くの場合に、言語モデルによって誤って発音されるか、または不十分に表現される。nグラムに関する正確な統計も通例入手可能でない。したがって、重要で頻度の低い単語を認識する確率が低く、単語配列が多くの場合に不正確である。これによって、IRシステムによる再現性能が不十分なものとなる。
【0009】
第2に、単語ベースのIRシステムに対する計算負荷は、リストおよびインデックスのサイズとともに増大し、システムの性能は、リアルタイム検索を許容できないものになる。
【発明の概要】
【0010】
本発明の実施の形態は、パーティクルによって表される、情報検索(IR)データベース内のアイテムを検索する方法を提供する。一意のパーティクルの数は、一意の単語の数よりもはるかに小さく、例えば、少なくとも一桁小さい。これによって、自動音声認識(ASR)システムの性能が改善し、認識時間が50%程度減少することになる。驚くべきことに、単語数と比較して、パーティクル数が劇的に減少し、スループットも同様に増大するにもかかわらず、再現率によって測定されるIRシステムの性能は、2%程度改善する。
【0011】
本発明の実施の形態は、情報検索(IR)システムの動作のために、単語のセットを、可能な限り互いに異なるパーティクルを用いて表すことが有利であるという認識に基づいている。例えば、可能な限り互いに異なるパーティクルを有することによって、ASR中の正確な認識が可能になる。さらに、実施の形態は、パーティクル間の差を、編集距離を用いて測定することができるという更なる認識に基づいている。
【0012】
本発明の1つの実施の形態は、パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法を開示する。アイテムのセットは、情報検索システムにおいて用いるのに適した単語のセットを表す。本方法は、パーティクルのセット内の各パーティクルについて、パーティクルの一部分の組合せを生成し、パーティクルのセット内のパーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの部分と置き換える。例えば、本方法は、パーティクルのセット内の各パーティクルのMEDを求め、各パーティクルのMEDの和としてパーティクルのセットの総MEDを求め、次に、該パーティクルのセットの総MEDを最大にする組合せを求める。
【0013】
別の実施の形態は、単語のセットを表すパーティクルの出力セットを生成する方法であって、単語のセットからパーティクルのセットを求めるステップと、パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、パーティクルのセット内のパーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの一部分と置き換えるステップと、パーティクルのセット内の各パーティクルについて生成することと置き換えることとを反復して、パーティクルの出力セットを生成する、反復するステップと、を含み、本方法のステップは、プロセッサによって実行される、単語のセットを表すパーティクルの出力セットを生成する方法を開示する。
【0014】
さらに別の実施の形態は、単語のセットを表すパーティクルの出力セットにおいてパーティクルのセットを変換するためのシステムであって、パーティクルのセット内の各パーティクルについて、該パーティクルのセットの総最小編集距離(MED)を最大にするパーティクルの一部分の組合せを求めるように構成された変換モジュールと、パーティクルのセット内のパーティクルを組合せの一部分と置き換えるように構成されたプロセッサと、を備える、単語のセットを表すパーティクルの出力セットにおいてパーティクルのセットを変換するためのシステムを開示する。
【0015】
この実施の形態の1つの変形形態は、パーティクルのセット内の各パーティクルのMEDを求める手段と、パーティクルのセットの総MEDを求める手段と、パーティクルのセットの総MEDを最大にする組合せを求める手段と、を備える。
【図面の簡単な説明】
【0016】
【図1】本発明の実施の形態による情報検索システムのブロック図である。
【図2A】単語の観点から書かれた関心アイテムのインデックスの表である。
【図2B】インデックスからの単語の発音辞書の表である。
【図3】本発明の実施の形態による単語からパーティクルへのマッピングの一例の表である。
【図4】本発明の実施の形態による、パーティクルの観点から書かれた関心アイテムのインデックスの一例の表である。
【図5】パーティクルの発音辞書の表である。
【図6】本発明の1つの実施の形態による、パーティクルの出力セットにおいてパーティクルのセットを変換するための方法のブロック図である。
【図7】本発明の1つの実施の形態による、パーティクルを、該パーティクルの接頭部および接尾部と置き換えるための方法のブロック図である。
【図8】パーティクルの変換を示す表である。
【図9】パーティクルの変換を示す表である。
【図10】パーティクルの変換を示す表である。
【図11】パーティクルの変換を示す表である。
【発明を実施するための形態】
【0017】
図1に示すように、本発明の実施の形態は、情報検索(IR)システム100においてデータベースからアイテムを検索する方法を提供する。本方法のステップは、当該技術分野において既知のプロセッサにおいて動作する。プロセッサは、メモリおよびI/Oインタフェースを備える。
【0018】
IRシステムは、単語によって表されるアイテムリスト101を備える。単語ベースのリスト101から、パーティクルによって表されるアイテムリスト102を生成する(110)。単語ベースのリスト内のアイテムとパーティクルベースのリスト内のアイテムとの間の対応は、1対1、または単語の代替的な発音が可能であるときには1対多とすることができる。
【0019】
パーティクルは、音声認識の分野において既知である。本明細書において定義されるように、「パーティクル」は、連結された音素配列を表す。一連のパーティクルは、単語の音素配列を表す。Whittaker他著「Particle-based language modelling」(International Conference on Speech and Language Processing (ICSLP), 2000)を参照されたい。
【0020】
これまで、パーティクルは、自動音声認識(ASR)システムにおいて単語を認識するためにしか用いられてこなかった。対照的に、本発明は、パーティクルを用いて情報検索(IR)を実行する。
【0021】
リスト102にインデクサー120を適用してパーティクルベースのインデックス121を作成する。アイテムを検索するために、ユーザー104からパーティクルベースのクエリ103が取得される。クエリは、ASRを用いてテキスト内の単語または発話から導出することができる。
【0022】
クエリ103を用いて、パーティクルベースのリスト102から構築されたインデックス121を調べる。クエリ103に応答する出力は、パーティクルベースのリスト102内の最も一致するアイテムに対応する、単語ベースのリスト101からのアイテムの結果リスト130である。
【0023】
パーティクルベースのリスト102を生成するために、前処理ステップにおいて、リスト101内の一意の単語のセット149を保持する。単語ベースのセット149を一意のパーティクルのセット151に変換する。パーティクルベースのセット151を取得した後、リスト101内のアイテムに関する単語を対応するパーティクルベースのアイテムに変換して、パーティクルベースのリスト102を生成する(110)ことができる。
【0024】
図2Aは、本発明の単語ベースのアイテムリスト101の詳細を示している。アイテムは、地理的関心地点であり、各ID201は、アイテム202を一意に識別する。
【0025】
図2Bは、単語211および対応する音素212を示している。幾つかの単語、例えば「HOUSES」は、代替的な発音を有し得る。図3は、単語301および対応するパーティクル302を示している。
【0026】
単語ベースのリスト内のアイテムが複数の発音を有する場合、全ての単語について、パーティクルへの全ての可能性のある分割のデカルト積が形成され、パーティクルベースのリスト内に列挙される。例えば、AASHIANIが「AA_SH_IY AA_N_IY」としてまたは「AA_SH Y_AE_N_IH」としてパーティクルに分割することができ、RESTAURANTが「R_E_S_T_R_AA_N_T」としてまたは「R_E_S_T_ER_R_AA_N_T」としてパーティクルに分割することができる場合、全ての可能性のある分割:
AA_SH_IY AA_N_IY R_E_S_T_R_AA_N_T、
AA_SH_IY AA_N_IY R_E_S_T_ER_R_AA_N_T、
AA_SH Y_AE_N_IH R_E_S_T_R_AA_N_T、および
AA_SH Y_AE_N_IH R_E_S_T_ER_AA_N_T
が、パーティクルベースのインデックス内に列挙される。
【0027】
図4は、パーティクルベースのリスト102の詳細を示し、該リストは、アイテム402ごとに一意のID401を含む。
【0028】
図5は、ASRによって使用することができる発音辞書を示し、該発音辞書は、パーティクル501および対応する音素502を含む。
【0029】
本発明の言語モデルは、パーティクル、例えば、パーティクルnグラムに対する統計を含むnグラム言語モデルを含む。
【0030】
パーティクルの変換
本発明の実施の形態は、情報検索(IR)システムの動作のために、単語のセットを、可能な限り互いに異なるパーティクルを用いて表すことが有利であるという認識に基づいている。例えば、可能な限り互いに異なるパーティクルを有することによって、ASR中の正確な認識が可能になる。さらに、実施の形態は、パーティクル間の差を編集距離を用いて測定することができるという更なる認識に基づいている。
【0031】
したがって、実施の形態は、パーティクルの出力セットにおいて、アイテムのセット660を変換する。本発明の様々な実施の形態において、アイテムのセットは、IRシステムにおいて用いるのに適した単語のセットを表す。例えば、1つの実施の形態は、単語のセット内の各単語について、該単語の複数のパーティクルへの全ての可能な分割を求め、単語のセットから導出された一意のパーティクルからアイテムのセットを形成する。他の実施の形態では、アイテムのセット内のアイテムは、単語のセット、単語のセットから導出された音声ストリングのセット、単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される。
【0032】
図8は、パーティクルのセットの一例を示している。セット内の各パーティクルについて、最小編集距離(MED)810が求められる。MEDは、全ての他のパーティクルに対するそのパーティクルの最も小さい編集距離である。また、パーティクルのセットの総MED820が各パーティクルのMEDの和として求められる。
【0033】
図6は、パーティクルの出力セット615においてパーティクルのセット610を変換するための方法600のブロック図を示している。1つの実施の形態において、パーティクルのセットは、アイテムのセットの少なくとも一部分によって形成される。本方法のステップは、当該技術分野において既知のように、プロセッサ601によって実行される。
【0034】
変換モジュール602は、パーティクルのセット内のパーティクル620の一部分の組合せ635を生成する(630)。例えば、1つの実施の形態では、組合せは、2つの部分、すなわち、パーティクルの接頭部および接尾部のみを含む。加えて、組合せ635は、パーティクルの全ての可能な組合せである。代替の実施の形態では、組合せは、3つ以上の部分を含む。
【0035】
パーティクル620は、パーティクルのセット内で、該パーティクルのセットの総最小編集距離(MED)を最大にする(640)組合せの一部分645と置き換えられる(650)。変換は、パーティクルのセット内の全てのパーティクルについて反復され、これによって、パーティクルの出力セットにおいてパーティクルのセットを変換する。
【0036】
図7は、パーティクル710を該パーティクルの接頭部および接尾部715と置き換える(700)一例を示している。パーティクルは、パーティクルのセットから取り除かれ(720)、組合せの一部分、すなわち、接頭部および接尾部がパーティクルのセットに加えられる(730)。次に、パーティクルのセット内の各パーティクルについてMEDが求められ(740)、MEDが合算され、パーティクルのセットの総MED755が求められる(750)。
【0037】
置き換えは、パーティクルの全ての組合せについて繰り返される。具体的には、組合せの一部分がパーティクルのセットから取り除かれ、パーティクルの別の組合せの一部分と置き換えられ、該別の組合せの一部分を用いてMEDおよび総MEDが求められる。最後に、総MEDの最大値に対応する組合せの一部分がパーティクルのセットに加えられる。
【0038】
1つの実施の形態は、パーティクルのセット内の一意のパーティクルのみを保持する。組合せの一部分がパーティクルのセット内のパーティクルと同一である例では、この部分は、セットに加えられない。
【0039】
変換中、パーティクルのセット、したがってパーティクルの出力セットは、単語のセットに従ってインデックス付けされる。例えば、1つの実施の形態は、アイテムのセットと単語のセットとの間でインデックスのインデックスマップを作成する。インデックスマップは、複数のパーティクルへの単語の分割を追跡する。変換中、インデックスマップは、パーティクルに置き換わるパーティクルの一部分をインデックス付けするツリーマップとなる。
【0040】
図9〜図11は、図8に示すパーティクルのセット810からのパーティクル「abcd」830の変換の例を示している。パーティクル「abcd」の全ての可能な2つの部分の組合せは、図9に示すように「a」+「bcd」と、図10に示すように「ab」+「cd」と、図11に示すように「abc」+「d」とである。各組合せについて、変換モジュールは各パーティクルのMEDと、全体セットの総MED値とを求める。組合せの一部分「a」+「bcd」が総MEDを最大にするので、総MEDの値は7に等しく、その組合せの一部分がパーティクル「abcd」を置き換える。
【技術分野】
【0001】
本発明は、包括的には情報検索に関し、特に、パーティクル間の編集距離の最大化を用いてパーティクルのセットを変換することに関する。
【背景技術】
【0002】
情報検索(IR)システムは、通常、地理的関心地点(points of interest:POI)、または音楽アルバムの題名のようなアイテムの大規模なリストを含む。リストは、インデックスによってアクセスされる。インデックスに対する入力は、ユーザーによって供給されるクエリである。クエリに応答して、IRシステムは、該クエリに最も一致した結果リストを生成する。この結果リストは、様々な要因に従って順序付けすることができる。結果リスト、インデックス、クエリ、および結果リストは、通常、単語によって表される。入力リスト、クエリ、および結果リストは、テキストによるものであるか、または発話によるものである。
【0003】
発話によるクエリは、ユーザーがキーボードを使用することができない環境、例えば、運転中、またはユーザーインタフェースがマイクロフォンを含む環境において用いられる。これらの環境では、自動音声認識装置(ASR)を用いて発話を単語に変換する。
【0004】
ASRは、2つの基本データ構造、単語の発音辞書および単語の言語モデルを用いる。一般に、IRシステムは、単語を音素として音声的に表す。例えば、RESTAURANTは「R EH S T R AA N T」として表される。音素は、特定の言語における音の基本単位を指す。音素は、強勢符号、音節境界、および単語がどのように発音されるかを示す他の表記を含むことができる。
【0005】
言語モデルは、語順の確率を記述し、ASRによって、正しい単語仮説のための探索を制約するのに用いられる。言語モデルは、nグラム(n-gram)とすることができる。nグラムが二重字(bigram)である場合、二重字によってP(「BELL」|「TACO」)のような確率がリストされる。これは、単語「TACO」の後に単語「BELL」が続く確率である。言語モデルは、有限状態文法とすることもでき、ここで、文法の状態は、各状態において現れる可能性がある単語を表し、状態間の遷移は、1つの状態から別の状態に向かう確率を表す。
【0006】
単語ベースのIRには、2つの主な問題が存在する。
【0007】
第1に、IRに重要な単語は、通常、頻度の低い識別語である。例えば、アイテムPOI「MJ’S RESTAURANT」において、重要な識別語は「MJ’S」である。多くの場合、これらの識別語は、他の言語からの固有名詞である。例えば、アイテム「AASHIANI RESTAURANT」内の単語「AASHIANI」は、ヒンディー語からのものである。これらの識別語の別の現れ方は、「GREENHOUSE」のように、組み合わせを通じたものである。単語の語根を変更することによって、語彙のサイズも増大する。通例、頻度が低いが重要である識別語の数は、非常に多い。
【0008】
加えて、重要な識別語は、多くの場合に、言語モデルによって誤って発音されるか、または不十分に表現される。nグラムに関する正確な統計も通例入手可能でない。したがって、重要で頻度の低い単語を認識する確率が低く、単語配列が多くの場合に不正確である。これによって、IRシステムによる再現性能が不十分なものとなる。
【0009】
第2に、単語ベースのIRシステムに対する計算負荷は、リストおよびインデックスのサイズとともに増大し、システムの性能は、リアルタイム検索を許容できないものになる。
【発明の概要】
【0010】
本発明の実施の形態は、パーティクルによって表される、情報検索(IR)データベース内のアイテムを検索する方法を提供する。一意のパーティクルの数は、一意の単語の数よりもはるかに小さく、例えば、少なくとも一桁小さい。これによって、自動音声認識(ASR)システムの性能が改善し、認識時間が50%程度減少することになる。驚くべきことに、単語数と比較して、パーティクル数が劇的に減少し、スループットも同様に増大するにもかかわらず、再現率によって測定されるIRシステムの性能は、2%程度改善する。
【0011】
本発明の実施の形態は、情報検索(IR)システムの動作のために、単語のセットを、可能な限り互いに異なるパーティクルを用いて表すことが有利であるという認識に基づいている。例えば、可能な限り互いに異なるパーティクルを有することによって、ASR中の正確な認識が可能になる。さらに、実施の形態は、パーティクル間の差を、編集距離を用いて測定することができるという更なる認識に基づいている。
【0012】
本発明の1つの実施の形態は、パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法を開示する。アイテムのセットは、情報検索システムにおいて用いるのに適した単語のセットを表す。本方法は、パーティクルのセット内の各パーティクルについて、パーティクルの一部分の組合せを生成し、パーティクルのセット内のパーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの部分と置き換える。例えば、本方法は、パーティクルのセット内の各パーティクルのMEDを求め、各パーティクルのMEDの和としてパーティクルのセットの総MEDを求め、次に、該パーティクルのセットの総MEDを最大にする組合せを求める。
【0013】
別の実施の形態は、単語のセットを表すパーティクルの出力セットを生成する方法であって、単語のセットからパーティクルのセットを求めるステップと、パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、パーティクルのセット内のパーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの一部分と置き換えるステップと、パーティクルのセット内の各パーティクルについて生成することと置き換えることとを反復して、パーティクルの出力セットを生成する、反復するステップと、を含み、本方法のステップは、プロセッサによって実行される、単語のセットを表すパーティクルの出力セットを生成する方法を開示する。
【0014】
さらに別の実施の形態は、単語のセットを表すパーティクルの出力セットにおいてパーティクルのセットを変換するためのシステムであって、パーティクルのセット内の各パーティクルについて、該パーティクルのセットの総最小編集距離(MED)を最大にするパーティクルの一部分の組合せを求めるように構成された変換モジュールと、パーティクルのセット内のパーティクルを組合せの一部分と置き換えるように構成されたプロセッサと、を備える、単語のセットを表すパーティクルの出力セットにおいてパーティクルのセットを変換するためのシステムを開示する。
【0015】
この実施の形態の1つの変形形態は、パーティクルのセット内の各パーティクルのMEDを求める手段と、パーティクルのセットの総MEDを求める手段と、パーティクルのセットの総MEDを最大にする組合せを求める手段と、を備える。
【図面の簡単な説明】
【0016】
【図1】本発明の実施の形態による情報検索システムのブロック図である。
【図2A】単語の観点から書かれた関心アイテムのインデックスの表である。
【図2B】インデックスからの単語の発音辞書の表である。
【図3】本発明の実施の形態による単語からパーティクルへのマッピングの一例の表である。
【図4】本発明の実施の形態による、パーティクルの観点から書かれた関心アイテムのインデックスの一例の表である。
【図5】パーティクルの発音辞書の表である。
【図6】本発明の1つの実施の形態による、パーティクルの出力セットにおいてパーティクルのセットを変換するための方法のブロック図である。
【図7】本発明の1つの実施の形態による、パーティクルを、該パーティクルの接頭部および接尾部と置き換えるための方法のブロック図である。
【図8】パーティクルの変換を示す表である。
【図9】パーティクルの変換を示す表である。
【図10】パーティクルの変換を示す表である。
【図11】パーティクルの変換を示す表である。
【発明を実施するための形態】
【0017】
図1に示すように、本発明の実施の形態は、情報検索(IR)システム100においてデータベースからアイテムを検索する方法を提供する。本方法のステップは、当該技術分野において既知のプロセッサにおいて動作する。プロセッサは、メモリおよびI/Oインタフェースを備える。
【0018】
IRシステムは、単語によって表されるアイテムリスト101を備える。単語ベースのリスト101から、パーティクルによって表されるアイテムリスト102を生成する(110)。単語ベースのリスト内のアイテムとパーティクルベースのリスト内のアイテムとの間の対応は、1対1、または単語の代替的な発音が可能であるときには1対多とすることができる。
【0019】
パーティクルは、音声認識の分野において既知である。本明細書において定義されるように、「パーティクル」は、連結された音素配列を表す。一連のパーティクルは、単語の音素配列を表す。Whittaker他著「Particle-based language modelling」(International Conference on Speech and Language Processing (ICSLP), 2000)を参照されたい。
【0020】
これまで、パーティクルは、自動音声認識(ASR)システムにおいて単語を認識するためにしか用いられてこなかった。対照的に、本発明は、パーティクルを用いて情報検索(IR)を実行する。
【0021】
リスト102にインデクサー120を適用してパーティクルベースのインデックス121を作成する。アイテムを検索するために、ユーザー104からパーティクルベースのクエリ103が取得される。クエリは、ASRを用いてテキスト内の単語または発話から導出することができる。
【0022】
クエリ103を用いて、パーティクルベースのリスト102から構築されたインデックス121を調べる。クエリ103に応答する出力は、パーティクルベースのリスト102内の最も一致するアイテムに対応する、単語ベースのリスト101からのアイテムの結果リスト130である。
【0023】
パーティクルベースのリスト102を生成するために、前処理ステップにおいて、リスト101内の一意の単語のセット149を保持する。単語ベースのセット149を一意のパーティクルのセット151に変換する。パーティクルベースのセット151を取得した後、リスト101内のアイテムに関する単語を対応するパーティクルベースのアイテムに変換して、パーティクルベースのリスト102を生成する(110)ことができる。
【0024】
図2Aは、本発明の単語ベースのアイテムリスト101の詳細を示している。アイテムは、地理的関心地点であり、各ID201は、アイテム202を一意に識別する。
【0025】
図2Bは、単語211および対応する音素212を示している。幾つかの単語、例えば「HOUSES」は、代替的な発音を有し得る。図3は、単語301および対応するパーティクル302を示している。
【0026】
単語ベースのリスト内のアイテムが複数の発音を有する場合、全ての単語について、パーティクルへの全ての可能性のある分割のデカルト積が形成され、パーティクルベースのリスト内に列挙される。例えば、AASHIANIが「AA_SH_IY AA_N_IY」としてまたは「AA_SH Y_AE_N_IH」としてパーティクルに分割することができ、RESTAURANTが「R_E_S_T_R_AA_N_T」としてまたは「R_E_S_T_ER_R_AA_N_T」としてパーティクルに分割することができる場合、全ての可能性のある分割:
AA_SH_IY AA_N_IY R_E_S_T_R_AA_N_T、
AA_SH_IY AA_N_IY R_E_S_T_ER_R_AA_N_T、
AA_SH Y_AE_N_IH R_E_S_T_R_AA_N_T、および
AA_SH Y_AE_N_IH R_E_S_T_ER_AA_N_T
が、パーティクルベースのインデックス内に列挙される。
【0027】
図4は、パーティクルベースのリスト102の詳細を示し、該リストは、アイテム402ごとに一意のID401を含む。
【0028】
図5は、ASRによって使用することができる発音辞書を示し、該発音辞書は、パーティクル501および対応する音素502を含む。
【0029】
本発明の言語モデルは、パーティクル、例えば、パーティクルnグラムに対する統計を含むnグラム言語モデルを含む。
【0030】
パーティクルの変換
本発明の実施の形態は、情報検索(IR)システムの動作のために、単語のセットを、可能な限り互いに異なるパーティクルを用いて表すことが有利であるという認識に基づいている。例えば、可能な限り互いに異なるパーティクルを有することによって、ASR中の正確な認識が可能になる。さらに、実施の形態は、パーティクル間の差を編集距離を用いて測定することができるという更なる認識に基づいている。
【0031】
したがって、実施の形態は、パーティクルの出力セットにおいて、アイテムのセット660を変換する。本発明の様々な実施の形態において、アイテムのセットは、IRシステムにおいて用いるのに適した単語のセットを表す。例えば、1つの実施の形態は、単語のセット内の各単語について、該単語の複数のパーティクルへの全ての可能な分割を求め、単語のセットから導出された一意のパーティクルからアイテムのセットを形成する。他の実施の形態では、アイテムのセット内のアイテムは、単語のセット、単語のセットから導出された音声ストリングのセット、単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される。
【0032】
図8は、パーティクルのセットの一例を示している。セット内の各パーティクルについて、最小編集距離(MED)810が求められる。MEDは、全ての他のパーティクルに対するそのパーティクルの最も小さい編集距離である。また、パーティクルのセットの総MED820が各パーティクルのMEDの和として求められる。
【0033】
図6は、パーティクルの出力セット615においてパーティクルのセット610を変換するための方法600のブロック図を示している。1つの実施の形態において、パーティクルのセットは、アイテムのセットの少なくとも一部分によって形成される。本方法のステップは、当該技術分野において既知のように、プロセッサ601によって実行される。
【0034】
変換モジュール602は、パーティクルのセット内のパーティクル620の一部分の組合せ635を生成する(630)。例えば、1つの実施の形態では、組合せは、2つの部分、すなわち、パーティクルの接頭部および接尾部のみを含む。加えて、組合せ635は、パーティクルの全ての可能な組合せである。代替の実施の形態では、組合せは、3つ以上の部分を含む。
【0035】
パーティクル620は、パーティクルのセット内で、該パーティクルのセットの総最小編集距離(MED)を最大にする(640)組合せの一部分645と置き換えられる(650)。変換は、パーティクルのセット内の全てのパーティクルについて反復され、これによって、パーティクルの出力セットにおいてパーティクルのセットを変換する。
【0036】
図7は、パーティクル710を該パーティクルの接頭部および接尾部715と置き換える(700)一例を示している。パーティクルは、パーティクルのセットから取り除かれ(720)、組合せの一部分、すなわち、接頭部および接尾部がパーティクルのセットに加えられる(730)。次に、パーティクルのセット内の各パーティクルについてMEDが求められ(740)、MEDが合算され、パーティクルのセットの総MED755が求められる(750)。
【0037】
置き換えは、パーティクルの全ての組合せについて繰り返される。具体的には、組合せの一部分がパーティクルのセットから取り除かれ、パーティクルの別の組合せの一部分と置き換えられ、該別の組合せの一部分を用いてMEDおよび総MEDが求められる。最後に、総MEDの最大値に対応する組合せの一部分がパーティクルのセットに加えられる。
【0038】
1つの実施の形態は、パーティクルのセット内の一意のパーティクルのみを保持する。組合せの一部分がパーティクルのセット内のパーティクルと同一である例では、この部分は、セットに加えられない。
【0039】
変換中、パーティクルのセット、したがってパーティクルの出力セットは、単語のセットに従ってインデックス付けされる。例えば、1つの実施の形態は、アイテムのセットと単語のセットとの間でインデックスのインデックスマップを作成する。インデックスマップは、複数のパーティクルへの単語の分割を追跡する。変換中、インデックスマップは、パーティクルに置き換わるパーティクルの一部分をインデックス付けするツリーマップとなる。
【0040】
図9〜図11は、図8に示すパーティクルのセット810からのパーティクル「abcd」830の変換の例を示している。パーティクル「abcd」の全ての可能な2つの部分の組合せは、図9に示すように「a」+「bcd」と、図10に示すように「ab」+「cd」と、図11に示すように「abc」+「d」とである。各組合せについて、変換モジュールは各パーティクルのMEDと、全体セットの総MED値とを求める。組合せの一部分「a」+「bcd」が総MEDを最大にするので、総MEDの値は7に等しく、その組合せの一部分がパーティクル「abcd」を置き換える。
【特許請求の範囲】
【請求項1】
パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法であって、該アイテムのセットは、情報検索システムにおいて用いるのに適した単語のセットを表し、該方法は、前記パーティクルのセット内の各パーティクルについて、
前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、
前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの前記一部分と置き換え、前記パーティクルの出力セットにおいて前記パーティクルのセットを変換する、置き換えるステップと、
一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、
単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、
前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップと
を含み、該方法の前記ステップは、プロセッサによって実行される、パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法。
【請求項2】
前記パーティクルのセットの前記総MEDを最大にする前記組合せを求めるステップをさらに含む請求項1に記載の方法。
【請求項3】
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
各パーティクルの前記MEDの和として前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項1に記載の方法。
【請求項4】
前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、
前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップと
をさらに含む請求項3に記載の方法。
【請求項5】
前記置き換えるステップは、
前記パーティクルのセットから前記パーティクルを取り除くステップと、
前記組合せの前記一部分を前記パーティクルのセットに加えるステップと、
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項1に記載の方法。
【請求項6】
前記パーティクルのセットから前記組合せの前記一部分を取り除くステップ
をさらに含む請求項1に記載の方法。
【請求項7】
前記置き換えるステップは、
前記パーティクルのセットから前記パーティクルを取り除くステップと、
各組合せについて、該組合せの各部分のMEDと、前記パーティクルのセットの前記総MEDとを求めるステップであって、該総MEDは前記組合せの前記一部分の前記MEDを含む、求めるステップと、
前記組合せの前記一部分を前記総MEDの最大値に対応する前記パーティクルのセットに加えるステップと
をさらに含む請求項1に記載の方法。
【請求項8】
前記組合せは、前記パーティクルの接頭部および接尾部を含み、前記生成するステップは、
接頭部および接尾部の全ての可能な組合せを生成するステップ、
をさらに含む請求項1に記載の方法。
【請求項9】
前記単語のセット内の各単語について、パーティクルが一意になるような該パーティクルへの前記単語の全ての可能な分割を求めるステップと、
前記パーティクルから前記アイテムのセットを形成するステップと
をさらに含む請求項1に記載の方法。
【請求項10】
アイテムのセットと単語のセットとの間をインデックス付けするインデックスマップを用いて、前記アイテムのセットに基づいて前記パーティクルの出力セットをインデックス付けするステップ
をさらに含む請求項1に記載の方法。
【請求項11】
ユーザーからクエリを取得するステップと、
前記パーティクルベースのインデックスを用いて前記アイテムのセットにアクセスするステップであって、前記クエリに最も一致する対応するアイテムを求める、アクセスするステップと、
前記ユーザーに対し、結果リストとして前記対応するアイテムを出力するステップと
をさらに含む請求項1に記載の方法。
【請求項12】
前記アイテムのセット内のアイテムは、前記単語のセット、該単語のセットから導出された音声ストリングのセット、前記単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される請求項1に記載の方法。
【請求項13】
単語のセットを表すパーティクルの出力セットを生成する方法であって、
前記単語のセットからパーティクルのセットを求めるステップと、
前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、
前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの前記一部分と置き換えるステップと、
一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、
単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、
前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップと、
前記パーティクルのセット内の各パーティクルについて前記生成するステップと前記置き換えるステップとを反復して、前記パーティクルの出力セットを生成する、反復するステップと
を含み、該方法の前記ステップは、プロセッサによって実行される、単語のセットを表すパーティクルの出力セットを生成する方法。
【請求項14】
前記求めるステップは、
前記単語のセット内の各単語を複数のパーティクルに分割するステップと、
前記パーティクルのセット内の全てのパーティクルが一意となるように、該パーティクルのセットに入れる前記パーティクルを選択するステップと
をさらに含む請求項13に記載の方法。
【請求項15】
前記求めるステップは、
前記単語のセット内の各単語の音声ストリングを求めるステップと、
前記音声ストリングに基づいて前記パーティクルのセットを形成するステップと
をさらに含む請求項13に記載の方法。
【請求項16】
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
各パーティクルの和として前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項13に記載の方法。
【請求項17】
前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、
前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップと
をさらに含む請求項13に記載の方法。
【請求項1】
パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法であって、該アイテムのセットは、情報検索システムにおいて用いるのに適した単語のセットを表し、該方法は、前記パーティクルのセット内の各パーティクルについて、
前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、
前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの前記一部分と置き換え、前記パーティクルの出力セットにおいて前記パーティクルのセットを変換する、置き換えるステップと、
一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、
単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、
前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップと
を含み、該方法の前記ステップは、プロセッサによって実行される、パーティクルの出力セットにおいて、アイテムのセットの少なくとも一部分によって形成されるパーティクルのセットを変換するための方法。
【請求項2】
前記パーティクルのセットの前記総MEDを最大にする前記組合せを求めるステップをさらに含む請求項1に記載の方法。
【請求項3】
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
各パーティクルの前記MEDの和として前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項1に記載の方法。
【請求項4】
前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、
前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップと
をさらに含む請求項3に記載の方法。
【請求項5】
前記置き換えるステップは、
前記パーティクルのセットから前記パーティクルを取り除くステップと、
前記組合せの前記一部分を前記パーティクルのセットに加えるステップと、
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項1に記載の方法。
【請求項6】
前記パーティクルのセットから前記組合せの前記一部分を取り除くステップ
をさらに含む請求項1に記載の方法。
【請求項7】
前記置き換えるステップは、
前記パーティクルのセットから前記パーティクルを取り除くステップと、
各組合せについて、該組合せの各部分のMEDと、前記パーティクルのセットの前記総MEDとを求めるステップであって、該総MEDは前記組合せの前記一部分の前記MEDを含む、求めるステップと、
前記組合せの前記一部分を前記総MEDの最大値に対応する前記パーティクルのセットに加えるステップと
をさらに含む請求項1に記載の方法。
【請求項8】
前記組合せは、前記パーティクルの接頭部および接尾部を含み、前記生成するステップは、
接頭部および接尾部の全ての可能な組合せを生成するステップ、
をさらに含む請求項1に記載の方法。
【請求項9】
前記単語のセット内の各単語について、パーティクルが一意になるような該パーティクルへの前記単語の全ての可能な分割を求めるステップと、
前記パーティクルから前記アイテムのセットを形成するステップと
をさらに含む請求項1に記載の方法。
【請求項10】
アイテムのセットと単語のセットとの間をインデックス付けするインデックスマップを用いて、前記アイテムのセットに基づいて前記パーティクルの出力セットをインデックス付けするステップ
をさらに含む請求項1に記載の方法。
【請求項11】
ユーザーからクエリを取得するステップと、
前記パーティクルベースのインデックスを用いて前記アイテムのセットにアクセスするステップであって、前記クエリに最も一致する対応するアイテムを求める、アクセスするステップと、
前記ユーザーに対し、結果リストとして前記対応するアイテムを出力するステップと
をさらに含む請求項1に記載の方法。
【請求項12】
前記アイテムのセット内のアイテムは、前記単語のセット、該単語のセットから導出された音声ストリングのセット、前記単語のセットから導出されたパーティクルのセット、およびそれらの組合せのうちの少なくとも1つから選択される請求項1に記載の方法。
【請求項13】
単語のセットを表すパーティクルの出力セットを生成する方法であって、
前記単語のセットからパーティクルのセットを求めるステップと、
前記パーティクルのセット内のパーティクルの一部分の組合せを生成するステップと、
前記パーティクルのセット内の前記パーティクルを、該パーティクルのセットの総最小編集距離(MED)を最大にする組合せの前記一部分と置き換えるステップと、
一意の単語ベースのセットをパーティクルベースのセットに変換するステップと、
単語のセットを前記パーティクルベースのセットに基づく対応するアイテムのセットに変換するステップと、
前記アイテムのセットをインデックス付けするステップであって、パーティクルベースのインデックスを生成する、インデックス付けするステップと、
前記パーティクルのセット内の各パーティクルについて前記生成するステップと前記置き換えるステップとを反復して、前記パーティクルの出力セットを生成する、反復するステップと
を含み、該方法の前記ステップは、プロセッサによって実行される、単語のセットを表すパーティクルの出力セットを生成する方法。
【請求項14】
前記求めるステップは、
前記単語のセット内の各単語を複数のパーティクルに分割するステップと、
前記パーティクルのセット内の全てのパーティクルが一意となるように、該パーティクルのセットに入れる前記パーティクルを選択するステップと
をさらに含む請求項13に記載の方法。
【請求項15】
前記求めるステップは、
前記単語のセット内の各単語の音声ストリングを求めるステップと、
前記音声ストリングに基づいて前記パーティクルのセットを形成するステップと
をさらに含む請求項13に記載の方法。
【請求項16】
前記パーティクルのセット内の各パーティクルのMEDを求めるステップと、
各パーティクルの和として前記パーティクルのセットの前記総MEDを求めるステップと
をさらに含む請求項13に記載の方法。
【請求項17】
前記パーティクルと、前記パーティクルのセット内の全ての他のパーティクルとの間の編集距離を求めるステップと、
前記パーティクルの前記MEDとして最も小さい編集距離を選択するステップと
をさらに含む請求項13に記載の方法。
【図1】
【図2A】
【図2B】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2A】
【図2B】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公表番号】特表2013−517540(P2013−517540A)
【公表日】平成25年5月16日(2013.5.16)
【国際特許分類】
【出願番号】特願2012−533154(P2012−533154)
【出願日】平成23年3月22日(2011.3.22)
【国際出願番号】PCT/JP2011/057520
【国際公開番号】WO2011/122515
【国際公開日】平成23年10月6日(2011.10.6)
【出願人】(597067574)ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
【公表日】平成25年5月16日(2013.5.16)
【国際特許分類】
【出願日】平成23年3月22日(2011.3.22)
【国際出願番号】PCT/JP2011/057520
【国際公開番号】WO2011/122515
【国際公開日】平成23年10月6日(2011.10.6)
【出願人】(597067574)ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】201 BROADWAY, CAMBRIDGE, MASSACHUSETTS 02139, U.S.A.
[ Back to top ]