(57)【特許請求の範囲】
【請求項１】
1つまたは複数の文書プロセッサおよび複数の行列プロセッサを使用して、1組の1つまたは複数の文書からワード-トピック行列を抽出するステップであって、前記ワード-トピック行列が、前記1組の1つまたは複数の文書の複数のトピックを含み、
前記トピックの各々が、少なくとも部分的に、ワードセットの1つまたは複数のワードによって定義され、前記1つまたは複数のワードの各々が、それぞれの確率に関連付けられ、前記ワードセットが、前記1組の1つまたは複数の文書のワードインデックスからのワードを含み、
前記ワード-トピック行列が、少なくとも部分的に、前記1つまたは複数のトピックに対応する第1の次元および前記ワードセットに対応する第2の次元によって定義され、
前記ワードセット内のワードが、
前記ワードが存在する文書プロセッサの数を決定することにより、前記ワードセット内の各ワードについての重みを決定するステップと、
前記複数の行列プロセッサの各々についての負荷を決定するステップと、
前記ワードの重みに従って前記ワードセット内の前記ワードをソートするステップと、
最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てるステップと、
により前記複数の行列プロセッサに割り当てられ、
前記行列プロセッサが、
前記ワードセットの第1のサブセットに対応する前記ワード-トピック行列の第1の部分を記憶および処理するようにプログラムされた第1の行列プロセッサと、
前記ワードセットの第2のサブセットに対応する前記ワード-トピック行列の第2の部分を記憶および処理するようにプログラムされた第2の行列プロセッサであって、前記ワードセットの前記第2のサブセットが、前記第1のサブセットと異なる、第2の行列プロセッサと
を含み、
前記1つまたは複数の文書プロセッサの各々が、トピック抽出操作を、行列交換操作と並列して、実行するようにプログラムされ、
前記トピック抽出操作が、前記第1の行列プロセッサにおいて記憶された前記ワード-トピック行列の前記第1の部分を使用して、1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることを含み、
前記行列交換操作が、
1つまたは複数の第2のトピックについて前記1組の1つまたは複数の文書をサンプリングする際に使用される前記ワード-トピック行列の前記第2の部分を、前記第2の行列プロセッサからフェッチすること、あるいは
少なくとも1つの第2のトピックを抽出したときに、前記抽出された第2のトピックが前記第2のサブセット内のワードに一致したならば、前記抽出された第2のトピックを使用して前記ワード-トピック行列の前記第2の部分を更新するように前記第2の行列プロセッサに要求すること
のうちの少なくとも一方を含む、
ステップを含む方法。
【請求項２】
前記1つまたは複数の文書プロセッサが、複数のプロセッサを含み、
前記方法が、
前記ワードセット内のワードを巡回待ち行列として組織するステップと、
前記巡回待ち行列の第1の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第1の文書プロセッサを構成するステップと、
前記巡回待ち行列の第2の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第2の文書プロセッサを構成するステップであって、前記第1の位置が、前記第2の位置と異なる、ステップと
をさらに含む、請求項1に記載の方法。
【請求項３】
前記複数の行列プロセッサの前記各々についての前記負荷を決定するステップが、前記行列プロセッサ上のワードの重みの合計を決定するステップを含む、請求項1に記載の方法。
【請求項４】
第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するように、前記1つまたは複数の文書プロセッサの各々を構成するステップであって、前記第1のワードバンドルが、前記ワードセットの前記第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの前記第2のサブセットに対応する、ステップ
をさらに含む、請求項1に記載の方法。
【請求項５】
1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることが、前記1組の1つまたは複数の文書に対してギブスサンプリングを実行することを含む、請求項1に記載の方法。
【請求項６】
1つまたは複数の文書プロセッサおよび複数の行列プロセッサを備え、
前記1つまたは複数の文書プロセッサおよび前記複数の行列プロセッサを使用して、1組の1つまたは複数の文書からワード-トピック行列を抽出することであって、前記ワード-トピック行列が、前記1組の1つまたは複数の文書の複数のトピックを含み、
前記トピックの各々が、少なくとも部分的に、ワードセットの1つまたは複数のワードによって定義され、前記1つまたは複数のワードの各々が、確率に関連付けられ、前記ワードセットが、前記1組の1つまたは複数の文書のワードインデックスに属するワードを含み、
前記ワード-トピック行列が、少なくとも部分的に、前記1つまたは複数のトピックに対応する第1の次元および前記ワードセットに対応する第2の次元によって定義され、
前記ワードセット内のワードが、
前記ワードが存在する文書プロセッサの数を決定することにより、前記ワードセット内の各ワードについての重みを決定し、
前記複数の行列プロセッサの各々についての負荷を決定し、
前記ワードの重みに従って前記ワードセット内の前記ワードをソートし、
最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てる、
ことにより前記複数の行列プロセッサに割り当てられ、
前記行列プロセッサが、
前記ワードセットの第1のサブセットに対応する前記ワード-トピック行列の第1の部分を記憶および処理するようにプログラムされた第1の行列プロセッサと、
前記ワードセットの第2のサブセットに対応する前記ワード-トピック行列の第2の部分を記憶および処理するようにプログラムされた第2の行列プロセッサと
を含み、
前記1つまたは複数の文書プロセッサの各々が、トピック抽出操作および行列交換操作を実行するようにプログラムされ、前記トピック抽出操作が、前記行列交換操作と並列して実行され、
前記トピック抽出操作が、前記第1の行列プロセッサにおいて記憶された前記ワード-トピック行列の前記第1の部分を使用して、1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることを含み、
前記行列交換操作が、
1つまたは複数の第2のトピックについて前記1組の1つまたは複数の文書をサンプリングする際に使用される前記ワード-トピック行列の前記第2の部分を、前記第2の行列プロセッサからフェッチすること、あるいは
少なくとも1つの第2のトピックを抽出したときに、前記抽出された第2のトピックが前記第2のサブセット内のワードに一致したならば、前記抽出された第2のトピックを使用して前記ワード-トピック行列の前記第2の部分を更新するように前記第2の行列プロセッサに要求すること
のうちの少なくとも一方を含む、
抽出すること
を含む操作を実行するように構成された
システム。
【請求項７】
前記1つまたは複数の文書プロセッサが、複数のプロセッサを含み、
前記操作が、
前記ワードセット内のワードを巡回待ち行列として組織することと、
前記巡回待ち行列の第1の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第1の文書プロセッサを構成することと、
前記巡回待ち行列の第2の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第2の文書プロセッサを構成することであって、前記第1の位置が、前記第2の位置と異なる、構成することと
をさらに含む、請求項6に記載のシステム。
【請求項８】
前記複数の行列プロセッサの前記各々についての前記負荷を決定することが、前記行列プロセッサ上のワードの重みの合計を決定することを含む、請求項6に記載のシステム。
【請求項９】
プログラムが記録された記録媒体であって、1つまたは複数の文書プロセッサおよび複数の行列プロセッサに、
1組の1つまたは複数の文書からワード-トピック行列を抽出することであって、前記ワード-トピック行列が、前記1組の1つまたは複数の文書の複数のトピックを含み、
前記トピックの各々が、少なくとも部分的に、ワードセットの1つまたは複数のワードによって定義され、前記1つまたは複数のワードの各々が、確率に関連付けられ、前記ワードセットが、前記1組の1つまたは複数の文書のワードインデックスから生成され、
前記ワード-トピック行列が、少なくとも部分的に、前記1つまたは複数のトピックに対応する第1の次元および前記ワードセットに対応する第2の次元によって定義され、
前記ワードセット内のワードが、
前記ワードが存在する文書プロセッサの数を決定することにより、前記ワードセット内の各ワードについての重みを決定し、
前記複数の行列プロセッサの各々についての負荷を決定し、
前記ワードの重みに従って前記ワードセット内の前記ワードをソートし、
最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てる、
ことにより前記複数の行列プロセッサに割り当てられ、
前記行列プロセッサが、
前記ワードセットの第1のサブセットに対応する前記ワード-トピック行列の第1の部分を記憶および処理するようにプログラムされた第1の行列プロセッサと、
前記ワードセットの第2のサブセットに対応する前記ワード-トピック行列の第2の部分を記憶および処理するようにプログラムされた第2の行列プロセッサと
を含み、
前記1つまたは複数の文書プロセッサの各々が、トピック抽出操作および行列交換操作を実行するようにプログラムされ、前記トピック抽出操作が、前記行列交換操作と並列して実行され、
前記トピック抽出操作が、前記第1の行列プロセッサにおいて記憶された前記ワード-トピック行列の前記第1の部分を使用して、1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることを含み、
前記行列交換操作が、
1つまたは複数の第2のトピックについて前記1組の1つまたは複数の文書をサンプリングする際に使用される前記ワード-トピック行列の前記第2の部分を、前記第2の行列プロセッサからフェッチすること、あるいは
少なくとも1つの第2のトピックを抽出したときに、前記抽出された第2のトピックが前記第2のサブセット内のワードに一致したならば、前記抽出された第2のトピックを使用して前記ワード-トピック行列の前記第2の部分を更新するように前記第2の行列プロセッサに要求すること
のうちの少なくとも一方を含む、
抽出すること
を含む操作を実行させるように動作可能なプログラムが記録された記録媒体。
【請求項１０】
前記1つまたは複数の文書プロセッサが、複数のプロセッサを含み、
前記操作が、
前記ワードセット内のワードを巡回待ち行列として組織することと、
前記巡回待ち行列の第1の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第1の文書プロセッサを構成することと、
前記巡回待ち行列の第2の位置のワードを使用してトピック抽出操作を実行し始めるように、前記複数の文書プロセッサの第2の文書プロセッサを構成することであって、前記第1の位置が、前記第2の位置と異なる、構成することと
をさらに含む、請求項9に記載の記録媒体。
【請求項１１】
前記複数の行列プロセッサの前記各々についての前記負荷を決定することが、前記行列プロセッサ上のワードの重みの合計を決定することを含む、請求項9に記載の記録媒体。
【請求項１２】
前記操作が、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するように、前記1つまたは複数の文書プロセッサの各々を構成することであって、前記第1のワードバンドルが、前記ワードセットの前記第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの前記第2のサブセットに対応することをさらに含む、請求項9に記載の記録媒体。
【請求項１３】
1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることが、前記1組の1つまたは複数の文書に対してギブスサンプリングを実行することを含む、請求項9に記載の記録媒体。
【請求項１４】
1つまたは複数のコンピュータによって実行される方法であって、
ワード-トピック行列の第1の部分を第1の行列プロセッサに割り当てるステップであって、前記ワード-トピック行列が、1組の1つまたは複数の文書の複数のトピックを含み、各トピックが、ワードセットの1つまたは複数のワードを含み、前記1つまたは複数のワードの各々が、それぞれの確率に関連付けられ、前記ワードセットが、前記1組の1つまたは複数の文書のワードインデックスに属するワードを含む、ステップと、
前記ワード-トピック行列の第2の部分を第2の行列プロセッサに割り当てるステップであって、前記ワード-トピック行列の前記第2の部分が、前記ワード-トピック行列の前記第1の部分と異なる、ステップであって、
前記ワードセット内のワードが、
前記ワードが存在する文書プロセッサの数を決定することにより、前記ワードセット内の各ワードについての重みを決定するステップと、
前記複数の行列プロセッサの各々についての負荷を決定するステップと、
前記ワードの重みに従って前記ワードセット内の前記ワードをソートするステップと、
最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てるステップと、
により前記複数の行列プロセッサに割り当てられる、ステップと、
文書プロセッサにおいて、トピック抽出操作を実行するステップであって、前記トピック抽出操作が、前記第1の行列プロセッサにおいて記憶された前記ワード-トピック行列の前記第1の部分を使用して、1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることを含む、ステップと、
前記文書プロセッサにおいて、前記トピック抽出操作を実行するのと並列して、行列交換操作を実行するステップであって、前記行列交換操作が、
1つまたは複数の第2のトピックについて前記1組の1つまたは複数の文書をサンプリングする際に使用される前記ワード-トピック行列の前記第2の部分を、前記第2の行列プロセッサからフェッチすること、あるいは
少なくとも1つの第2のトピックを抽出したときに、前記抽出された第2のトピックが第2のサブセット内のワードに一致したならば、前記抽出された第2のトピックを使用して前記ワード-トピック行列の前記第2の部分を更新するように前記第2の行列プロセッサに要求すること
のうちの少なくとも一方を含む、ステップと
を含む方法。
【請求項１５】
前記文書プロセッサにおいて、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するステップであって、前記第1のワードバンドルが、前記ワードセットの第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの第2のサブセットに対応する、ステップ
をさらに含む、請求項14に記載の方法。
【請求項１６】
1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることが、前記1組の1つまたは複数の文書に対してギブスサンプリングを実行することを含む、請求項14に記載の方法。
【請求項１７】
プログラムが記録された記録媒体であって、1つまたは複数のコンピュータに、
ワード-トピック行列の第1の部分を第1の行列プロセッサに割り当てることであって、前記ワード-トピック行列が、1組の1つまたは複数の文書の複数のトピックを含み、各トピックが、ワードセットの1つまたは複数のワードを含み、前記1つまたは複数のワードの各々が、それぞれの確率に関連付けられ、前記ワードセットが、前記1組の1つまたは複数の文書のワードインデックスに属するワードを含む、割り当てることと、
前記ワード-トピック行列の第2の部分を第2の行列プロセッサに割り当てることであって、前記ワード-トピック行列の前記第2の部分が、前記ワード-トピック行列の前記第1の部分と異なる、割り当てることであって、
前記ワードセット内のワードが、
前記ワードが存在する文書プロセッサの数を決定することにより、前記ワードセット内の各ワードについての重みを決定し、
前記複数の行列プロセッサの各々についての負荷を決定し、
前記ワードの重みに従って前記ワードセット内の前記ワードをソートし、
最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てる、
ことにより前記複数の行列プロセッサに割り当てられることと、
文書プロセッサにおいて、トピック抽出操作を実行することであって、前記トピック抽出操作が、前記第1の行列プロセッサにおいて記憶された前記ワード-トピック行列の前記第1の部分を使用して、1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることを含む、実行することと、
前記文書プロセッサにおいて、前記トピック抽出操作を実行するのと並列して、行列交換操作を実行することであって、前記行列交換操作が、
1つまたは複数の第2のトピックについて前記1組の1つまたは複数の文書をサンプリングする際に使用される前記ワード-トピック行列の前記第2の部分を、前記第2の行列プロセッサからフェッチすること、あるいは
少なくとも1つの第2のトピックを抽出したときに、前記抽出された第2のトピックが第2のサブセット内のワードに一致したならば、前記抽出された第2のトピックを使用して前記ワード-トピック行列の前記第2の部分を更新するように前記第2の行列プロセッサに要求すること
のうちの少なくとも一方を含む、実行することと
を含む操作を実行させるように動作可能なプログラムが記録された記録媒体。
【請求項１８】
前記操作が、
前記文書プロセッサにおいて、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行することであって、前記第1のワードバンドルが、前記ワードセットの第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの第2のサブセットに対応する、実行すること
をさらに含む、請求項17に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、文書処理に関する。
【背景技術】
【０００２】
電子文書は、1つまたは複数のトピックを有することができる。コンピュータは、トピックモデルとして知られる統計モデルの一タイプを使用して、電子文書から1つまたは複数のトピックを自動的に抽出することができる。例示的なトピックモデルは、潜在的ディリクレ配分法(LDA:latent Dirichlet allocation)である。LDAによれば、トピックは、ワードの確率分布である。例えば、ワードtabby、purr、およびkittenに関連する指定された確率分布を有するトピックは、「cat」に関するトピックとすることができる。コンピュータは、例えば、文書内に含まれるワードtabby、purr、およびkittenの各々についての確率分布の計算を含む、電子文書の解析を行うことができる。計算された確率分布は、電子文書がトピック「cat」に関連する尤度を示すことができる。トピックは、抽象的である。ワード「cat」は、抽象的なトピックの任意のラベルである。
【０００３】
LDAでは、各文書は、K個のトピックの混合としてモデル化され、各トピックkは、W語のボキャブラリ(W-word vocabulary)上における多項分布φkである。任意の文書djについて、そのトピック混合θjは、ディリクレ事前分布(Dirichlet prior)をパラメータαとして用いて引き出された確率分布である。dj内の第iの各ワードxijについて、トピックzij=kは、θjから引き出され、ワードxijは、φkから引き出される。したがって、LDAの場合の生成操作は、
θj〜Dir(α)、φk〜Dir(β)、zij=k〜θj、xij〜φk    (1)
によって与えられ、ここで、Dir(*)は、ディリクレ分布を表し、αおよびβは各々、ディリクレ事前分布である。
【発明の概要】
【課題を解決するための手段】
【０００４】
拡張された並列潜在的ディリクレ配分法(PLDA+:enhanced parallel latent Dirichlet allocation)システムおよび方法について説明する。PLDA+システムは、複数の文書からトピックを生成するように構成された複数のプロセッサからなるシステムである。複数のプロセッサは、文書プロセッサおよび行列プロセッサの2つのタイプとして指定される。この文脈において、「プロセッサ」という用語は、場合に応じて、文書プロセッサまたは行列プロセッサによって実行される、以下で説明するアクションを実行するように構成されたコンピュータを指す。コンピュータは、コンピュータ上にインストールされた、動作したときにアクションをシステムに実行させる、ソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せを有することによって、アクションを実行するように構成することができる。同様に、1つまたは複数のコンピュータプログラムは、1つまたは複数のコンピュータによって実行されたときにアクションをコンピュータに実行させる命令を含むことによって、特定のアクションを実行するように構成することができる。
【０００５】
文書は、文書プロセッサの間に分散される。生成されたトピックは、行列プロセッサの間に分散される。文書プロセッサおよび行列プロセッサにおいて実行されるタスクは、計算バウンド(computation-bound)なタスクおよび通信バウンド(communication-bound)なタスクの2つのタイプのタスクに分離される。計算バウンドなタスクは、CPU集約的なタスクであり、通信バウンドなタスクは、ネットワーク集約的なタスクである。計算バウンドなタスクおよび通信バウンドなタスクが、プロセッサ間に平衡して分散され、並列的に実行されるように、データ配置戦略およびパイプライン戦略が利用される。
【０００６】
一般に、本明細書で説明される本発明の一態様は、1つまたは複数の文書プロセッサおよび複数の行列プロセッサを使用して、1組の1つまたは複数の文書からワード-トピック行列(word-topic matrix)を抽出することを含む操作において具体化することができる。ワード-トピック行列は、1組の1つまたは複数の文書の複数のトピックを含む。トピックの各々は、少なくとも部分的に、ワードセット(word set)の1つまたは複数のワードによって定義される。1つまたは複数のワードの各々は、確率に関連付けられる。ワードセットは、1組の1つまたは複数の文書のワードインデックス(word index)から生成される。ワード-トピック行列は、少なくとも部分的に、1つまたは複数のトピックに対応する第1の次元およびワードセットに対応する第2の次元によって定義される。
【０００７】
行列プロセッサは、少なくとも、第1の行列プロセッサおよび第2の行列プロセッサを含む。第1の行列プロセッサは、ワードセットの第1のサブセットに対応するワード-トピック行列の第1の部分を記憶および処理するように構成される。第2の行列プロセッサは、ワードセットの第2のサブセットに対応するワード-トピック行列の第2の部分を記憶および処理するように構成される。
【０００８】
1つまたは複数の文書プロセッサの各々は、トピック抽出(topic extraction)操作および行列交換(matrix exchange)操作を実行するように構成される。トピック抽出操作は、第1の行列プロセッサにおいて記憶されたワード-トピック行列の第1の部分を使用して、1つまたは複数の第1のトピックについて1組の1つまたは複数の文書をサンプリングすることを含む。第1のトピックは、1組の1つまたは複数の文書の複数のトピックの少なくとも一部を含むことができる。行列交換操作は、フェッチ操作または更新操作の少なくとも一方を含む。フェッチ操作は、1つまたは複数の第2のトピックについて1組の1つまたは複数の文書をサンプリングする際に使用されるワード-トピック行列の第2の部分を、第2の行列プロセッサからフェッチすることを含む。第2のトピックは、1組の1つまたは複数の文書の複数のトピックの少なくとも一部を含むことができ、第1のトピックと同じであること、または異なることができる。更新操作は、少なくとも1つの第2のトピックを抽出したときに、抽出された第2のトピックが第2のサブセット内のワードに一致したならば、抽出された第2のトピックを使用してワード-トピック行列の第2の部分を更新するように第2の行列プロセッサに要求することを含む。
【０００９】
これらおよび他の実施形態は、任意選択で、以下の特徴の1つまたは複数を含むことができる。操作は、ワードセット内のワードを巡回待ち行列(circular queue)として組織することをさらに含む。1つまたは複数の文書プロセッサは、複数のプロセッサを含む。操作は、待ち行列の第1の位置のワードを使用してトピック抽出操作を実行し始めるように、複数の文書プロセッサの第1の文書プロセッサを構成することと、待ち行列の第2の位置のワードを使用してトピック抽出操作を実行し始めるように、複数の文書プロセッサの第2の文書プロセッサを構成することとをさらに含み、第1の位置は、第2の位置と異なる。
【００１０】
操作は、加重ラウンドロビンスケジュール(weighted round robin schedule)に従って、ワードセット内のワードを複数の行列プロセッサに割り当てることをさらに含むことができる。加重ラウンドロビンスケジュールに従ってワードを割り当てることは、ワードセット内の各ワードについての重みを決定することと、複数の行列プロセッサの各々についての負荷を決定することと、ワードの重みに従ってワードセット内のワードをソートすることと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てることとを含むことができる。ワードセット内の各ワードについての重みを決定することは、ワードが存在する文書プロセッサの数を決定することを含むことができる。複数の行列プロセッサの各々についての負荷を決定することは、行列プロセッサ上のワードの重みの合計を決定することを含むことができる。
【００１１】
操作は、第1のワードバンドル(word bundle)および第2のワードバンドルに基づいてトピック抽出操作を実行するように、1つまたは複数の文書プロセッサの各々を構成することをさらに含むことができる。第1のワードバンドルは、ワードセットの第1のサブセットに対応することができる。第2のワードバンドルは、ワードセットの第2のサブセットに対応することができる。1つまたは複数の第1のトピックについて1組の1つまたは複数の文書をサンプリングすることは、1組の1つまたは複数の文書に対してギブスサンプリング(Gibbs sampling)を実行することを含む。
【００１２】
本明細書で説明される本発明の別の態様は、ワード-トピック行列の第1の部分を第1の行列プロセッサに割り当てることを含む操作において具体化することができる。ワード-トピック行列は、1組の1つまたは複数の文書の複数のトピックを含む。各トピックは、ワードセットの1つまたは複数のワードを含む。1つまたは複数のワードの各々は、それぞれの確率に関連付けられる。ワードセットは、1組の1つまたは複数の文書のワードインデックスに属するワードを含む。操作は、ワード-トピック行列の第2の部分を第2の行列プロセッサに割り当てることを含む。ワード-トピック行列の第2の部分は、ワード-トピック行列の第1の部分と異なる。操作は、文書プロセッサにおいて、トピック抽出操作を実行することを含む。トピック抽出操作は、第1の行列プロセッサにおいて記憶されたワード-トピック行列の第1の部分を使用して、1つまたは複数の第1のトピックについて1組の1つまたは複数の文書をサンプリングすることを含む。操作は、文書プロセッサにおいて、トピック抽出操作を実行するのと並列して、行列交換操作を実行することを含む。行列交換操作は、フェッチ操作または更新操作の少なくとも一方を含む。フェッチ操作は、1つまたは複数の第2のトピックについて1組の1つまたは複数の文書をサンプリングする際に使用されるワード-トピック行列の第2の部分を、第2の行列プロセッサからフェッチすることを含む。更新操作は、少なくとも1つの第2のトピックを抽出したときに、抽出された第2のトピックが第2のサブセット内のワードに一致したならば、抽出された第2のトピックを使用してワード-トピック行列の第2の部分を更新するように第2の行列プロセッサに要求することを含む。
【００１３】
本明細書で説明される技法は、従来の並列潜在的ディリクレ配分法(PLDA)の通信ボトルネックを低減することができる。より具体的には、PLDAの性能を向上させるために、計算バウンドなタスクおよび通信バウンドなタスクが、並列的に実行される。並列処理において、計算バウンドなタスクは、通信バウンドなタスクの処理時間がトピック生成の処理時間全体に著しく寄与しないように、通信バウンドなタスクをマスクする。加えて、本明細書で説明される技法は、複数のプロセッサの間における柔軟な負荷平衡を可能にし、性能をさらに高める。加えて、PLDAを含む従来のトピック抽出方法は、しばしば、各プロセッサのメモリ内にすべてのワード-トピックカウントを維持する。本明細書で説明される技法は、ワード-トピック行列を複数の行列プロセッサに分散させ、各プロセッサにおけるメモリ要件を低減する。
【００１４】
本明細書で説明される本発明の実施形態の詳細が、添付の図面および以下の説明において説明される。本発明の他の特徴、態様、および利点は、説明、図面、および特許請求の範囲から明らかになる。
【図面の簡単な説明】
【００１５】
【図１Ａ】PLDA技術を使用して文書からトピックを抽出するための例示的なプロセッサを示すブロック図である。
【図１Ｂ】例示的なPLDA+システムを示すブロック図である。
【図２】データ配置技法の例示的なトピック分布パターンを示すブロック図である。
【図３Ａ】処理パイプライン技法の例示的なイベントシーケンスを示す図である。
【図３Ｂ】処理パイプライン技法の例示的なイベントシーケンスを示す図である。
【図４】PLDA+システムにおける例示的なワードバンドリング技法を示す図である。
【図５Ａ】PLDA+システムの様々なプロセッサにおけるデータ配置を示すブロック図である。
【図５Ｂ】PLDA+システムの様々なプロセッサにおけるデータ配置を示すブロック図である。
【図６】例示的なPLDA+手順を示すフローチャートである。
【図７】パイプラインベースのギブスサンプリングを実行するための例示的な手順を示すフローチャートである。
【図８】PLDA+の通信方式を示すブロック図である。
【図９】PLDA+システムにおいてプロセッサを文書プロセッサまたは行列プロセッサとして指定する技法を示すブロック図である。
【発明を実施するための形態】
【００１６】
様々な図面における同様の参照番号および記号は、同様の要素を指示する。
【００１７】
図1Aは、PLDA+技術を使用して文書からトピックを抽出するための例示的なプロセッサを示すブロック図である。PLDA+では、文書からトピックを抽出するために、複数のプロセッサが利用される。プロセッサ102は、複数のプロセッサのうちの代表的なプロセッサである。
【００１８】
トピック抽出操作では、トピックは、1つまたは複数のワード-トピック行列として表される。従来のPLDA技術は、複数のプロセッサを利用して、文書からトピックを抽出する場合、一般に2つの特性を有する。各プロセッサは、完全なワード-トピック行列を維持する。各プロセッサは、完全なワード-トピック行列を他のプロセッサに送り、他のプロセッサから受け取る。それと比較して、PLDA+では、文書およびワード-トピック行列は、複数のプロセッサに分散される。分散された行列は、行列交換操作において、プロセッサ間で同期が取られる。PLDA+におけるトピック抽出操作および行列交換操作は、並列的に実行され、したがって、計算および通信効率を、操作が直列的に実行される従来のPLDA技術よりも向上させる。
【００１９】
プロセッサ102は、D個の文書からトピックを抽出するように構成され、ここで、Dは任意の数を表す。D個の文書は、P個のプロセッサ上に分散される。プロセッサ102は、P個のプロセッサの1つであり、約D/P個の文書を維持する。D個の文書は、文書内のワードのボキャブラリに対応する。ボキャブラリは、W個のワードを含む。プロセッサ102は、D/P個の文書とW個のワードとの間の対応を表す行列104を記憶する。行列104は、(D/P)×W行列である。
【００２０】
プロセッサ102は、ワード-トピック行列106も記憶する。ワード-トピック行列106は、K個のトピックとW語のボキャブラリとの間の対応を表す行列である。ワード-トピック行列106は、1つの次元をトピックとし、別の次元をワードとする、K×W行列である。ワード-トピック行列106内の各要素は、対応するトピックにおけるワードのカウントを表すことができる。ワード-トピック行列106は、D/P個の文書上でギブスサンプリングを複数回反復することによって構成することができる。
【００２１】
ギブスサンプリングの各反復の後、ローカルなワード-トピック行列をグローバルに同期させる。ローカルなワード-トピック行列は、プロセッサ102にローカルに記憶されたワード-トピック行列106を含む。ワード-トピック行列106は、ワード-トピック行列106を他のプロセッサ上に記憶された行列と同期させた場合に、グローバルに同期する。
【００２２】
図1Bは、例示的なPLDA+システム110を示すブロック図である。PLDA+システム110では、データ配置および処理パイプライン技法を利用して、分散処理の性能を従来のPLDAよりも高める。
【００２３】
俯瞰的には、PLDA+システム110は、文書からトピックを抽出するために、様々なプロセッサに部分的に分散された複数の行列を維持する。複数の行列は、ワード-トピック行列および文書-トピック行列(document-topic matrix)を含む。ワード-トピック行列は、ワード-トピックカウント行列(word-topic count matrix)とも呼ばれ、Cwordによって表される。ワード-トピック行列は、複数の要素を有するデータ構造であり、各要素Cwkは、トピックkに割り当てられるワードwの数である。文書-トピック行列は、文書-トピックカウント行列(document-topic count matrix)とも呼ばれ、Cdocによって表される。文書-トピック行列は、複数の要素を有するデータ構造であり、各要素Ckjは、文書djに割り当てられるトピックkの数である。加えて、PLDA+システム110は、トピックカウントベクトル(topic count vector)Ctopicを維持し、その各要素Ckは、文書コレクションにおけるトピックkの割り当ての数である。zijが(文書djにおける第iのワードである)ワードxijについてのトピック割り当てを表すとし、1つの変数zij以外のすべての変数の現在の状態を与えた場合、zijの条件付き確率は、
【００２４】
【数１】
0005615991.tif 000002
【００２５】
であり、ここで、-ijは、対応するワードがカウントから除外されることを表し、αおよびβは各々、ディリクレ事前分布である。式(2)から引き出される新しいトピックをzijに割り当てる場合はいつでも、Cword、Cdoc、およびCtopicが更新される。マルコフ連鎖(Markov chain)をトレーニングするのに十分なサンプリング反復の後、θおよびφが、以下のように推定され、
【００２６】
【数２】
0005615991.tif 000003
【００２７】
ここで、θkjは、文書jを与えた場合のトピックkの確率を表し、φwkは、トピックkを与えた場合のワードwの確率を表す。
【００２８】
PLDA+システム110は、文書プロセッサ(Pd個のプロセッサ)および行列プロセッサ(Pw個のプロセッサ)の2つのタイプのプロセッサを含む。文書プロセッサは、文書の維持、ギブスサンプリング操作の実行、および通信操作を含むタスクを実行できるプロセッサである。D個の文書は、|Pd|個の文書プロセッサ上に分散される。文書プロセッサ112は、|Pd|個のプロセッサの1つである。文書プロセッサ112は、約D/|Pd|個の文書を維持する。文書プロセッサ112は、ワード-文書行列(word-document matrix)116を維持する。ワード-文書行列116は、文書プロセッサ112のD/|Pd|個の文書とD個の文書のW語のボキャブラリとの間の対応を表す行列である。ワード-文書行列116は、(D/|Pd|)×W行列である。
【００２９】
行列プロセッサは、その各々が、W×Kワード-トピック行列の一部の維持を含むタスクを実行できるプロセッサである。W×Kワード-トピック行列は、|Pw|個の行列プロセッサの間に分散される。各行列プロセッサには、W語のボキャブラリのサブセットが割り当てられる。行列プロセッサ114は、部分的なワード-トピック行列118を記憶する。部分的なワード-トピック行列118は、行列プロセッサ114に割り当てられたボキャブラリのサブセットに対応する、W×Kワード-トピック行列の一部を含む。部分的なワード-トピック行列118のワード次元は、ボキャブラリのサブセットに対応する。ワード次元の大きさは、Wおよび行列プロセッサの数である|Pw|の値によって決定される。部分的なワード-トピック行列118のトピック次元は、K個のトピックに対応する。したがって、部分的なワード-トピック行列118は、(W/|Pw|)×K行列である。
【００３０】
文書プロセッサ112は、反復的にギブスサンプリングを実行する。ギブスサンプリングの各反復の間、文書プロセッサ112は、以下の3つのステージを含むトピック発見操作において、新しいトピックをワードに割り当てる。(1)文書プロセッサ112は、行列プロセッサ114からワードのトピック分布をフェッチする。(2)文書プロセッサ112は、ギブスサンプリングを実行し、新しいトピックをワードに割り当てる。(3)文書プロセッサ112は、ワードを維持する行列プロセッサ(行列プロセッサ114または別の行列プロセッサ)を更新する。
【００３１】
図2は、データ配置技法の例示的なトピック分布パターンを示すブロック図である。文書プロセッサ202(Pd0)は、1つまたは複数のトピックを1つまたは複数のワードの各々に割り当てる。文書プロセッサ202は、行列プロセッサ204によって維持される部分的なワード-トピック行列を同期させるために、行列プロセッサ204と通信する。行列プロセッサ204は、行列プロセッサ204に割り当てられたワードのサブセット内のワードに文書プロセッサ202によって割り当てられたトピックを使用して、行列プロセッサ204によって維持される部分的なワード-トピック行列を更新する。
【００３２】
文書プロセッサ206、208、210は、フェッチ操作を通して、行列プロセッサ204と通信する。文書プロセッサ206、208、210の各々は、完全なK×Wワード-トピック行列ではなく、行列プロセッサ204に記憶された部分的なワード-トピック行列をフェッチする。したがって、更新された部分的なワード-トピック行列が、文書プロセッサ206、208、210に伝搬する。
【００３３】
図3Aおよび図3Bは、処理パイプライン技法の例示的なイベントシーケンスを示す図である。示されるように、PLDA+システムでは、複数の操作が並列的に実行され、それによって、全体的な性能を従来のPLDAシステムよりも高める。図3Aおよび図3Bの各々は、4つのワードw1、w2、w3、およびw4についてのギブスサンプリングのイベントシーケンスを表している。図3Aおよび図3Bでは、文字「F」が記されたボックスは、フェッチ操作を表し、文字「U」が記されたボックスは、更新操作を表し、文字「S」が記されたボックスは、ギブスサンプリング操作を表す。
【００３４】
図3Aは、サンプリング時間Tsがフェッチ時間Tfと更新時間Tuの合計以上である(Ts≧Tf+Tu)例示的な場合を示している。サンプリング時間Tsは、プロセッサが、計算バウンドなタスクであるギブスサンプリングのタスクを実行するのに要する時間である。フェッチ時間Tfは、プロセッサが、トピック分布をフェッチするのに要する時間である。更新時間Tuは、プロセッサが、トピック分布を更新するのに要する時間である。トピック分布のフェッチおよび更新は、通信バウンドなタスクである。
【００３５】
示される例では、PLDA+システムは、第1のフェッチ操作302から開始し、文書プロセッサは、行列プロセッサからワードw1のトピック分布をフェッチする。その後、文書プロセッサは、ワードw1に対して第1のギブスサンプリング操作304を実行する。第1のギブスサンプリング操作304と並列して、文書プロセッサは、第2のフェッチ操作306を実行し、文書プロセッサは、ワードw2のトピック分布をフェッチする。
【００３６】
文書プロセッサがワードw1に対する第1のギブスサンプリング操作304を終了した後、文書プロセッサは、第1の更新操作308を実行し、文書プロセッサは、行列プロセッサにおけるw1のトピック分布を更新する。トピック分布w1の更新は、行列プロセッサに更新要求を送ることを含む。更新要求は、第1のギブスサンプリング操作304の結果を含むことができる。
【００３７】
文書プロセッサが第1のギブスサンプリング操作304を終了した後、文書プロセッサは、ワードw2に対して第2のギブスサンプリング操作310を実行し、第2の操作310は、w1のトピック分布の更新と並列して実行される。2つの操作は、一方の操作が実行される時間が、他方の操作が実行される時間とある程度オーバラップする場合、並列して行われるものとして説明される。文書プロセッサが第1の更新操作308を終了した後、文書プロセッサは、第3のフェッチ操作312を実行して、ワードw3のトピック分布をフェッチする。文書プロセッサは、第2のギブスサンプリング操作310と並列して、第3のフェッチ操作312を実行する。文書プロセッサは、同様に、第3のワードw3に対する第3のギブスサンプリング操作316、第4のフェッチ操作318、第3の更新操作320、第4のギブスサンプリング操作322、および第4の更新操作324を実行する。Ts≧Tf+Tuである場合、PLDA+システムがW個のワードを処理するための合計時間は、W*Ts+Tf+Tuである。
【００３８】
図3Bは、サンプリング時間Tsがフェッチ時間Tfと更新時間Tuの合計未満である(Ts<Tf+Tu)例示的な場合を示している。示される例では、PLDA+システムは、第1のフェッチ操作332から開始し、文書プロセッサは、ワードw1のトピック分布をフェッチする。その後、文書プロセッサは、ワードw1に対して第1のギブスサンプリング操作334を実行する。第1のギブスサンプリング操作334と並列して、文書プロセッサは、第2のフェッチ操作336を実行し、文書プロセッサは、ワードw2のトピック分布をフェッチする。
【００３９】
文書プロセッサがワードw1に対する第1のギブスサンプリング操作334を終了した後、文書プロセッサは、第1の更新操作338を実行し、文書プロセッサは、w1のトピック分布を更新する。それと並列して、文書プロセッサが第1のギブスサンプリング操作334を終了した後直ちに、文書プロセッサは、ワードw2に対して第2のギブスサンプリング操作340を実行する。
【００４０】
Ts<Tf+Tuである場合、文書プロセッサは、第2のギブスサンプリング操作340を終了した後、第2の更新操作342を実行する。その後、文書プロセッサは、第3のフェッチ操作346を実行し、文書プロセッサは、ワードw3のトピック分布をフェッチする。その後、文書プロセッサは、第3のギブスサンプリング操作348を実行し、それと並列して、第4のフェッチ操作350を実行し、文書プロセッサは、ワードw4のトピック分布をフェッチする。第3のギブスサンプリング操作348を終了した後、文書プロセッサは、第3の更新操作352および第4のギブスサンプリング操作354を実行する。最後に、文書プロセッサは、第4の更新操作356を実行する。Ts<Tf+Tuである場合、PLDA+システムがW個のワードを処理するための合計時間は、W*Ts+Tf+Tuよりも大きい。
【００４１】
いくつかの実施では、ギブスサンプリング操作、フェッチ操作、および更新操作は、可能な限りTs≧Tf+Tuであるようにスケジュールされる。スケジューリングは、可能な限りTs≧Tf+Tuとなることを保証するために、ワードバンドリング技法および低待ち時間通信スケジューリング技法を使用する。ワードバンドリングを使用する場合、ギブスサンプリング操作は、Tsが十分に長いことを保証するようなワードのグループに対して実行される。低待ち時間通信スケジューリングの下では、通信バウンドなタスクは、計算バウンドなタスクの通信バウンドなタスクによる遅延が最小限に抑えられるようにスケジュールされる。ワードバンドリング技法および低待ち時間通信スケジューリングは、以下でさらに詳細に説明される。
【００４２】
図4は、PLDA+システムにおける例示的なワードバンドリング技法を示す図である。便宜的に、ワードバンドリング技法は、4つの文書プロセッサPd0からPd3に関連して説明される。
【００４３】
文書プロセッサPd0からPd3は、ワード順402a〜402dで、ギブスサンプリングを実行することができる。文書プロセッサの文書において数回発生するワードは、ループして処理される。さらに、頻繁に発生しないワードは、Tsが十分に長いことを保証するために、頻繁に発生するワードとバンドルされる。Tf+Tuの値が分かっている場合、各ギブスサンプリングバンドルにおいて処理されるワード発生のカウントを決定することができる。直前のギブスサンプリングタスクが完了する時間までにフェッチが完了し、したがって、待ち時間の追加が回避される、確率を最大化するために、ワードは、Tf+TuがTsよりも短くなるようにバンドルされる。
【００４４】
文書プロセッサPd0からPd3の各々は、文書プロセッサに分散される文書に対するワードインデックスを作成する。インデックス内のワードは、巡回待ち行列410に組織される。文書プロセッサPd0からPd3は、巡回待ち行列410を周回することによって、ギブスサンプリング操作を実行する。複数の文書プロセッサによる同じワードに対する同時アクセスを回避するため、文書プロセッサの各々は、他の文書プロセッサの開始位置とは異なる開始位置において開始するようにスケジュールされる。例えば、ワードw0からw7を含む巡回待ち行列410において、文書プロセッサPd0は、ワードw0から第1のワードを開始することができ、文書プロセッサPd1は、ワードw2から第1のワードを開始することができ、文書プロセッサPd2は、ワードw4から第1のワードを開始することができ、文書プロセッサPd3は、ワードw6から第1のワードを開始することができる。
【００４５】
巡回待ち行列410内の異なる位置において開始するように異なる文書プロセッサをスケジュールすることに加えて、部分的なワード-トピック行列を行列プロセッサ上に巡回的に分散させる。部分的なワード-トピック行列の巡回的な分散は、通信タスクが文書プロセッサにおいて実行されるときに、複数の行列プロセッサではなく、対応する行列プロセッサによって通信タスクにサービスできることを保証する。
【００４６】
図5Aおよび図5Bは、PLDA+システムの様々なプロセッサにおけるデータ配置を示すブロック図である。図5Aは、行列プロセッサにおけるワード配置を示している。行列プロセッサ506は、文書プロセッサからのフェッチ要求および更新要求に応答するように構成される。W×Kワード-トピック行列502は、ワードに従って複数の行列プロセッサに分散される。分散後、各行列プロセッサは、約W/|Pw|個のワードをワードのトピック分布とともに維持する。行列プロセッサ506は、W/|Pw|個のワードをワードのトピック分布とともに、(W/|Pw|)×K行列504として記憶することができる。
【００４７】
ワード分散を利用して、空間負荷平衡(spatial load balancing)を達成することができる。行列プロセッサ506および他の行列プロセッサを各々使用して、ギブスサンプリングの反復において、ほぼ同数の要求を処理することができる。
【００４８】
W×Kワード-トピック行列502を複数の行列プロセッサに分散させる場合、PLDA+システムは、ワード重みデータ構造および作業負荷データ構造の2つのデータ構造を維持する。ワード重みデータ構造は、ワード重みを記憶するデータ構造である。ワードWiが存在する文書プロセッサの数は、ワードの重みでもあり、miによって表される。W個のワードの場合、PLDA+システムは、ベクトル
【００４９】
【数３】
0005615991.tif 000004
【００５０】
を維持する。作業負荷データ構造は、行列プロセッサ506および他の各行列プロセッサの作業負荷についての情報を含むデータ構造である。行列プロセッサ506の作業負荷は、行列プロセッサ506上のすべてのワードの重みの合計として定義される。行列プロセッサPwiの作業負荷は、liによって表される。作業負荷データ構造は、
【００５１】
【数４】
0005615991.tif 000005
【００５２】
によって表されるベクトルを含む。
【００５３】
いくつかの実施では、ワードは、独立かつ一様に、ランダムに行列プロセッサ上に分散される。いくつかの実施では、加重ラウンドロビンワード配置を使用することができる。加重ラウンドロビンワード配置では、ワードは、ワードの重みによって昇順または降順にソートされる。行列プロセッサの中で行列プロセッサ506が最小の作業負荷を有する場合、W語のボキャブラリの中で最大の重みを有するワード(例えば、ワードWi)が、行列プロセッサ506に配置される。その後、行列プロセッサ506の作業負荷が更新される。選択操作、配置操作、および更新操作は、すべてのワードが配置されるまで繰り返される。
【００５４】
PLDA+システムが、ワードをワードのトピック分布とともに行列プロセッサ506上に配置した後、行列プロセッサ506は、文書プロセッサから初期ワード-トピックカウントを受け取ることによって、担当するワード-トピックカウント行列
【００５５】
【数５】
0005615991.tif 000006
【００５６】
を作成する。その後、行列プロセッサ506は、文書プロセッサからの要求を処理し始める。文書プロセッサからの要求は、3つのタイプを有することができる。
-  fetch(wi,pw,pd):文書プロセッサpdによるワードwのトピック分布のフェッチを求める要求。この要求に対して、行列プロセッサpwは、wのトピック分布Cw|pwを返し、これは、ギブスサンプリングのために、式(2)において、
【００５７】
【数６】
0005615991.tif 000007
【００５８】
として使用される。
【００５９】
【数７】
0005615991.tif 000008
【００６０】
:pdにおける更新情報
【００６１】
【数８】
0005615991.tif 000009
【００６２】
を使用して、ワードwのトピック分布の更新を求める要求。行列プロセッサpwは、
【００６３】
【数９】
0005615991.tif 000010
【００６４】
を使用して、wのトピック分布を更新する。更新情報
【００６５】
【数１０】
0005615991.tif 000011
【００６６】
は、ギブスサンプリングの結果を含む。
-  fetch(pw,pd):pdによる行列プロセッサpwにおけるトピックカウント全部のフェッチを求める要求。行列プロセッサpwは、pwにおけるすべてのワードのトピック分布を、ベクトル
【００６７】
【数１１】
0005615991.tif 000012
【００６８】
としてまとめ合わせる。pdによって各行列プロセッサからすべての
【００６９】
【数１２】
0005615991.tif 000013
【００７０】
がフェッチされた後、それらは、まとめ合わされて、ギブスサンプリングのために、式(2)において、
【００７１】
【数１３】
0005615991.tif 000014
【００７２】
として使用される。
【００７３】
文書プロセッサからの要求を(アルゴリズム内ではpwと呼ばれる)行列プロセッサ506において処理するための例示的なアルゴリズムが、以下のList 1に示されている。
【００７４】
【数１４】
0005615991.tif 000015
【００７５】
いくつかの実施では、文書プロセッサのギブスサンプリング中に、すべての行列プロセッサからトピックカウント全部をフェッチするための最大間隔intermaxの値は、ボキャブラリ内のワードの数に等しく設定される。
【００７６】
行列プロセッサ506は、行列プロセッサ506が維持を担当するワードに関するすべての要求を処理する。要求がタイムリにサービスされることを保証するため、PLDA+システムは、要求デッドラインによって要求がソートされる優先順位方式を利用する。優先順位方式におけるローカルなワード処理順位に従って、文書プロセッサは、文書プロセッサから送られるフェッチ要求の通信完了デッドラインを設定することができる。通信完了デッドラインは、それを超えた場合は要求を無視できる時間限界である。通信完了デッドラインは、様々な時間単位によって表すことができる。文書プロセッサが要求を行列プロセッサに送るとき、デッドラインが要求ヘッダ内に設定される。行列プロセッサ506は、待っている要求のデッドラインに基づいて、待っている要求にサービスする。
【００７７】
図5Bは、文書プロセッサにおける文書配置を示している。ワード-文書行列510は、ワードと文書との間のマッピングを表すために使用される。ワード-文書行列510は、1つのワードから1つまたは複数の文書を識別するために使用できる逆インデックスである。
【００７８】
ワード-文書行列510は、複数の文書プロセッサの間に部分的に分散させることができる。ワード-文書行列510の一部512は、D/|Pd|個の文書およびW個のワードを含むことができる。文書プロセッサ516は、一部512に対応する部分的な文書-ワード行列514を記憶することができる。部分的な文書-ワード行列514は、(D/|Pd|)×W行列である。
【００７９】
図6は、例示的なPLDA+手順600を示すフローチャートである。PLDA+システムは、1つまたは複数の文書プロセッサ上にD個の文書を割り当てる(602)。PLDA+システムは、文書を文書プロセッサに平衡するように割り当てる。これは、ランダム文書割り当てを利用することによって達成される。各文書プロセッサには、約D/|Pd|個の文書が割り当てられる。この割り当てステージの時間計算量は、O(D)である。
【００８０】
PLDA+システムは、各文書プロセッサの文書に対する逆インデックスを構成する(603)。逆インデックスは、ワードに基づいたインデックスである。各ワードwについてのインデックス構造は、
w→{(d1,z1),(d1,z2),(d2,z1)…}  (4)
である。
【００８１】
ワードwが文書d1内でn回発生する場合、n個のエントリが存在する。いくつかの実施では、PLDA+システムは、d1内におけるワードwのすべての発生を、1つのエントリ(d1,{z1,z2})として記録する。
【００８２】
PLDA+システムは、ボキャブラリ内のワードを、ギブスサンプリングのために、ワードバンドルにグループ化する(604)。ワードをワードバンドルにグループ化することで、ギブスサンプリング操作の持続時間が、通信操作をマスクするのに十分な長さになることを保証することができる。ギブスサンプリング操作の持続時間は、通信タスクをギブスサンプリング操作の持続時間内に完了できる場合に、通信操作をマスクするのに十分な長さである。ワードが文書プロセッサにおいて1回しか発生しない場合、そのワードに対するギブスサンプリングの実行は、そのワードのトピック分布をフェッチおよび更新するのに必要な時間よりもはるかに短い時間しかかからず、マスクにはならない。
【００８３】
マスクを確実に行えるように、PLDA+システムは、複数のワードを組み合わせてワードバンドルとし、ギブスサンプリング時間のより長い持続時間によって、通信時間をマスクできるようにする。ワードバンドル内のすべてのワードは、同じ行列プロセッサに配置され、そのため、1つの要求で、ワードバンドル内のすべてのワードについてのトピック分布をフェッチすることができる。
【００８４】
文書プロセッサのために、PLDA+システムは、ワードの行列プロセッサに従ってワードをバンドルする。PLDA+システムは、同じ行列プロセッサに配置されるワードを、ワードが発生する回数に基づいて、降順にソートする。その後、PLDA+システムは、順序付けられたワードリストを作成する。その後、PLDA+システムは、高頻度のワードをワードリストの先頭から、1つまたは複数の低頻度のワードをワードリストの末尾から反復的に選択する。PLDA+システムは、選択された高頻度のワードおよび選択された1つまたは複数の低頻度のワードをグループ化してワードバンドルにする。ワードバンドルはそのように構成され、行列プロセッサは、トピック分布のフェッチを求める要求に応答して、ワードバンドル内のすべてのワードを返す。
【００８５】
PLDA+システムは、通信ボトルネックを最低限に抑えるように、ワードバンドルをスケジュールする(606)。いくつかの実施では、PLDA+システムは、ランダムスケジューリング方式に従って、ワードバンドルをスケジュールする。ランダムスケジューリング方式では、ボキャブラリ内のワードは、巡回待ち行列内に記憶される。ギブスサンプリング中、ワードは、この待ち行列から、時計回りまたは反時計回り順に選択される。各文書プロセッサは、同じ行列プロセッサへの同時アクセスを回避するために、巡回待ち行列の異なるオフセットから開始する。ボトルネックは、いくつかの行列プロセッサにおいて、複数の要求が同時に到着した場合に形成される可能性がある。したがって、いくつかの文書プロセッサは、ギブスサンプリングを開始できるようになる前に、応答を待つ必要があることがある。待ちを短縮するため、PLDA+システムは、図4Aを参照して説明したように、各要求内にデッドラインを登録する。行列プロセッサは、要求のデッドラインに従って、要求を処理する。行列プロセッサは、要求のデッドラインが過ぎてしまった場合、要求を廃棄することができる。ギブスサンプリングの確率的性質のため、ギブスサンプリングのラウンドに時折失敗しても、全体的な性能に影響は及ばない。
【００８６】
PLDA+システムは、終了条件が満たされるまで、パイプラインベースのギブスサンプリングを反復的に実行する(608)。ステージ603において作成された逆インデックスを使用して、文書プロセッサがワードwのトピック分布を行列プロセッサからフェッチした後に毎回、文書プロセッサは、その文書プロセッサにおけるwのすべての事例に対してギブスサンプリングを実行する。ギブスサンプリングの後、文書プロセッサは、更新された情報を対応する行列プロセッサに送り返す。
【００８７】
文書プロセッサにおいてワードが複数回発生する場合、フェッチで1つ、更新で1つの、2つの通信タスクが実行される。式(2)に示されるように、文書dj内の与えられたワードxij=wに対して新しいトピックを計算し、割り当てるために、PLDA+システムは、ワードwについてのワード-トピック分布
【００８８】
【数１５】
0005615991.tif 000016
【００８９】
、トピックカウントベクトルCtopic、および文書djについての文書-トピック分布
【００９０】
【数１６】
0005615991.tif 000017
【００９１】
を獲得する。文書プロセッサは、文書-トピック分布
【００９２】
【数１７】
0005615991.tif 000018
【００９３】
を維持する。行列プロセッサは、最新のワード-トピック分布
【００９４】
【数１８】
0005615991.tif 000019
【００９５】
を維持する。PLDA+システムは、すべての行列プロセッサにわたるグローバルなトピックカウントベクトルCtopicを収集する。文書内のwに対して新しいトピックを割り当てる前に、文書プロセッサは、行列プロセッサに
【００９６】
【数１９】
0005615991.tif 000020
【００９７】
およびCtopicを要求する。
【００９８】
【数２０】
0005615991.tif 000021
【００９９】
およびCtopicをフェッチした後、文書プロセッサは、ギブスサンプリングを実行し、wの発生に対して新しいトピックを割り当てる。その後、文書プロセッサは、ワードwの更新されたトピック分布を、担当する行列プロセッサに返す。
【０１００】
文書プロセッサは、異なる処理スピードを有することができる。PLDA+システムでは、高速の文書プロセッサは、低速の文書プロセッサを待つ必要なしに、パイプラインベースのギブスサンプリングの次のラウンドを開始することができる。パイプラインベースのギブスサンプリングのさらなる詳細が、図7を参照して以下で説明される。
【０１０１】
図7は、パイプラインベースのギブスサンプリングを実行するための例示的な手順を示すフローチャートである。文書プロセッサpdが、ギブスサンプリングのために、トピックカウント全部をフェッチする(702)。文書プロセッサpdは、トピック分布全部Ctopicをフェッチする。ステージ702において、文書プロセッサpdは、1つまたは複数のフェッチ要求fetch(pw,pd)を各行列プロセッサにサブミットする。文書プロセッサpdは、トピックカウント全部
【０１０２】
【数２１】
0005615991.tif 000022
【０１０３】
、pw∈{0,...,|Pw|-1}を含む応答を行列プロセッサから受け取る。文書プロセッサpdは、各行列プロセッサからのトピックカウント全部を、以下の式を使用して、合計することによって、Ctopicを獲得する。
【０１０４】
【数２２】
0005615991.tif 000023
【０１０５】
文書プロセッサpdは、F個のワードバンドルを選択し(704)、ワードのトピック分布をフェッチするために、F個のワードバンドルをスレッドプール(thread pool)内に置く。文書プロセッサは、1つまたは複数のフェッチ要求を行列プロセッサにサブミットする。F個のワードバンドルの各々が、フェッチ要求に対応する。文書プロセッサpdは、要求に対する応答を行列プロセッサから受け取る。応答は、トピック分布を含む。応答内のトピック分布は、待ち行列内に記憶される。スレッドプールは、要求を送り、返された応答を並列的に処理することができる。複数の要求を同時に送ることができる。同時に送られる要求には、同じデッドラインを割り当てることができる。
【０１０６】
文書プロセッサpdは、ギブスサンプリングを実行するために、待ち行列からワードのトピック分布を選択する(706)。フェッチ要求に対する応答が行列プロセッサから返された後、文書プロセッサpdは、直ちにギブスサンプリングを開始することができる。いくつかの実施では、プリフェッチ(pre-fetch)要求の数は、Fに等しい。Fの値は、待ち行列Qpdがギブスサンプリングを待っているワードのトピック分布を常に返す確率を最大化するように設定される。いくつかの実施では、Fは、スレッドプール内のスレッドの数よりも大きくなるように設定される。
【０１０７】
文書プロセッサpdは、更新されたトピック分布を文書プロセッサpdのスレッドプール内に入れる(708)。文書プロセッサpdのスレッドプールは、1つまたは複数の更新要求を行列プロセッサに送る。文書プロセッサpdは、新しいワードバンドルを選択し(710)、新しいワードバンドルをスレッドプール内に置く。文書プロセッサは、更新条件が満たされているかどうかを判定する(712)。更新条件が満たされていない場合、文書プロセッサpdは、ステージ706に進み、別のワードに対するギブスサンプリングを開始する。更新条件が満たされている場合、文書プロセッサは、新しいトピックカウント全部をフェッチする(714)。
【０１０８】
図8は、PLDA+の通信方式を示すブロック図である。文書プロセッサ802は、要求サブシステム804を含む。要求サブシステム804は、1つまたは複数のフェッチ要求806を生成するように構成される。フェッチ要求806の各々は、複数のワードw1、w2、...、wnを含むワードバンドルを含む。フェッチ要求806は、スレッドプール808内に入れられる。スレッドプール808は、フェッチ要求806を行列プロセッサ810a、810b、810cに送る。行列プロセッサ810a、810b、810cは、ワードバンドル内のワードについてのトピック分布812を返す。
【０１０９】
スレッドプール808は、いくつかのビジーな行列プロセッサによるブロッキングを防止するために使用することができる。スレッドプール808内に保持することが許可されるスレッドの最大数を表すスレッドキャップ値(thread cap value)Rは、行列プロセッサ810a、810b、810cに送ることができる並列要求の数の上限を定める。Rの値は、ネットワーク環境によって決定することができる。Rの値の設定は、ギブスサンプリング中に経験的に調整することができる。反復中の待ち時間が長い場合、次の反復において、Rの値を増やすことができる。いくつかの実施では、図7を参照して説明したような、ワードバンドルの数Fは、Rの値と比例するように設定される。例えば、いくつかの実施では、Fは、Rの値の2倍に設定される。
【０１１０】
文書プロセッサ802は、トピック分布サブシステム814を含む。トピック分布サブシステム814は、トピック分布812を待ち行列に入れる。トピック分布サブシステム814は、ギブスサンプリングのために、待ち行列の先頭からトピック分布を取り出す。
【０１１１】
文書プロセッサ802は、ギブスサンプリングサブシステム816を含む。ギブスサンプリングサブシステム816は、ギブスサンプリングを実行し、トピック分布812を更新し、更新されたトピック分布818を生成するように構成される。更新されたトピック分布818は、1つまたは複数の更新要求に入れられ、スレッドプール808にサブミットされる。スレッドプール808は、更新要求を行列プロセッサ810a、810b、810cに送る。
【０１１２】
図9は、PLDA+システムにおいて、プロセッサを文書プロセッサまたは行列プロセッサとして指定する技法を示すブロック図である。PLDA+システムは、複数のプロセッサ902を含む。プロセッサ902の1つまたは複数は、文書プロセッサ904として指定される。プロセッサ902の残りは、行列プロセッサ906として指定される。文書プロセッサ904に対する行列プロセッサ906の数の比率γ=|Pw|/|Pd|は、ギブスサンプリングの平均時間およびワード-トピック行列の通信の平均時間に基づいて、計算することができる。全データセットに対するギブスサンプリングの合計時間をTsとした場合、すべてのワードのトピック分布を1つのプロセッサから別のプロセッサに転送する通信時間をTtとする。文書プロセッサ904について、サンプリング時間は、Ts/|Pd|である。ワードのトピック分布は、行列プロセッサ906に同時に転送される。転送時間は、Tt/|Pw|である。ギブスサンプリング操作は、以下の条件、
【０１１３】
【数２３】
0005615991.tif 000024
【０１１４】
の下で、フェッチ操作および更新操作をマスクする。
【０１１５】
【数２４】
0005615991.tif 000025
【０１１６】
であるとき、ただし、
【０１１７】
【数２５】
0005615991.tif 000026
【０１１８】
がワードのすべての事例についての平均サンプリング時間であり、かつ
【０１１９】
【数２６】
0005615991.tif 000027
【０１２０】
であるとき、ただし、
【０１２１】
【数２７】
0005615991.tif 000028
【０１２２】
および
【０１２３】
【数２８】
0005615991.tif 000029
【０１２４】
が、ワードについての平均フェッチ時間および平均更新時間とするならば、文書プロセッサ904に対する行列プロセッサ906の数の比率は、
【０１２５】
【数２９】
0005615991.tif 000030
【０１２６】
のように決定することができ、ここで、
【０１２７】
【数３０】
0005615991.tif 000031
【０１２８】
および
【０１２９】
【数３１】
0005615991.tif 000032
【０１３０】
は、小さなデータセットに対してPLDA+を実行することによって獲得することができ、その後、経験的に適切なγ値を設定することができる。
【０１３１】
本明細書で説明された本発明の実施形態および操作は、デジタル電子回路で、または本明細書で開示された構造およびそれらの構造的均等物を含む、コンピュータソフトウェア、ファームウェア、またはハードウェアで、あるいはそれらの1つまたは複数の組合せで実施することができる。本明細書で説明された本発明の実施形態は、1つまたは複数のコンピュータプログラムとして、すなわち、データ処理装置によって実行するための、またはデータ処理装置の動作を制御するための、コンピュータ記憶媒体上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして、実施することができる。代替として、または加えて、プログラム命令は、例えば、機械生成の電気、光、または電磁気信号など、人工的に生成される伝搬信号上に符号化することができ、人工的に生成される伝搬信号は、適切な受信機装置に送信し、データ処理装置によって実行するために、情報を符号化するために生成される。コンピュータ記憶媒体は、コンピュータ可読記憶デバイス、コンピュータ可読記憶基板、ランダムもしくはシリアルアクセスされるメモリアレイもしくはデバイス、またはそれらの1つまたは複数の組合せとすることができ、あるいはそれらに含めることができる。さらに、コンピュータ記憶媒体は、伝搬信号ではないが、コンピュータ記憶媒体は、人工的に生成される伝搬信号内に符号化されるコンピュータプログラム命令の送信元または送信先とすることができる。コンピュータ記憶媒体は、また、1つまたは複数の別個の物理的構成要素もしくは媒体(例えば、複数のCD、ディスク、もしくは他の記憶デバイス)とすることができ、あるいはそれらに含めることができる。
【０１３２】
本明細書で説明された操作は、1つまたは複数のコンピュータ可読記憶デバイス上に記憶された、あるいは他のソースから受け取ったデータに対してデータ処理装置によって実行される操作として実施することができる。
【０１３３】
「データ処理装置」という用語は、データを処理するためのすべての種類の装置、デバイス、および機械を包含し、例えば、プログラム可能処理ユニット、コンピュータ、システムオンチップ、パーソナルコンピュータシステム、デスクトップコンピュータ、ラップトップ、ノートブック、ネットブックコンピュータ、メインフレームコンピュータシステム、ハンドヘルドコンピュータ、ワークステーション、ネットワークコンピュータ、アプリケーションサーバ、記憶デバイス、カメラ、ビデオカメラ、セットトップボックス、モバイルデバイス、ビデオゲーム機、ハンドヘルドビデオゲームデバイスなどの消費家電デバイス、スイッチ、モデム、ルータなどの周辺デバイス、または一般に任意のタイプのコンピューティングもしくは電子デバイス、あるいは上記のうちの複数のもの、または上記のものの組合せを含む。装置は、例えば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)などの、専用論理回路を含むことができる。装置は、ハードウェアに加えて、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、クロスプラットフォームランタイム環境、仮想マシン、あるいはそれらの1つまたは複数の組合せを構成するコードなど、問題となるコンピュータプログラムのための実行環境を生成するコードも含むことができる。装置および実行環境は、ウェブサービス、分散コンピューティングおよびグリッドコンピューティングインフラストラクチャなど、様々な異なるコンピューティングモデルインフラストラクチャを実現することができる。
【０１３４】
(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる)コンピュータプログラムは、コンパイラ言語またはインタプリタ言語、宣言型言語または手続型言語を含む、任意の形式のプログラミング言語で書くことができ、スタンドアロンプログラムの形態、またはモジュール、コンポーネント、サブルーチン、オブジェクト、もしくはコンピューティング環境で使用するのに適した他のユニットの形態を含む、任意の形態で配備することができる。コンピュータプログラムは、その必要はないが、ファイルシステム内のファイルに対応することができる。プログラムは、他のプログラムもしくはデータを保持するファイルの一部に(例えば、マークアップ言語文書内に記憶された1つまたは複数のスクリプト)、問題となるプログラム専用の単一のファイル内に、または複数の調整されたファイル(例えば、1つまたは複数のモジュール、サブプログラム、またはコードの一部を記憶するファイル)内に記憶することができる。コンピュータプログラムは、1つのコンピュータ上で、または1つのサイトに配置された、もしくは複数のサイト間に分散され、通信ネットワークによって相互接続された、複数のコンピュータ上で実行するように配備することができる。
【０１３５】
本明細書で説明されたプロセスおよび論理フローは、入力データに操作を施し、出力を生成することによって、アクションを実行するために、1つまたは複数のコンピュータプログラムを実行する、1つまたは複数のプログラム可能処理ユニットによって実行することができる。プロセスおよび論理フローは、例えば、FPGA(フィールドプログラマブルゲートアレイ)またはASIC(特定用途向け集積回路)などの、専用論理回路によって実行することもでき、装置は、専用論理回路として実施することもできる。
【０１３６】
コンピュータプログラムの実行に適した処理ユニットは、例えば、汎用および専用マイクロプロセッサの両方、ならびに任意の種類のデジタルコンピュータのいずれか1つまたは複数の処理ユニットを含む。一般に、処理ユニットは、リードオンリメモリもしくはランダムアクセスメモリまたは両方から命令およびデータを受け取る。コンピュータの必須要素は、命令に従ってアクションを実行するための処理ユニットと、命令およびデータを記憶するための1つまたは複数のメモリデバイスである。一般に、コンピュータは、例えば、磁気ディスク、光磁気ディスク、または光ディスクなど、データを記憶するための1つまたは複数の大容量記憶デバイスも含み、あるいは1つまたは複数の大容量記憶デバイスからデータを受け取ること、もしくはそれらにデータを転送すること、またはその両方を行うように動作可能に結合されもする。しかし、コンピュータは、そのようなデバイスを有する必要はない。さらに、コンピュータは、例えば、ほんのいくつかの名前を挙げれば、モバイル電話、携帯情報端末(PDA)、モバイルオーディオもしくはビデオプレーヤ、ゲーム機、全地球測位システム(GPS)受信機、ネットワークルーティングデバイス、またはポータブル記憶デバイス(例えば、ユニバーサルシリアルバス(USB)フラッシュドライブ)などの、別のデバイス内に埋め込むことができる。コンピュータプログラム命令およびデータを記憶するのに適したデバイスは、例として、例えば、EPROM、EEPROM、およびフラッシュメモリデバイスなどの、半導体メモリデバイス、例えば、内蔵ハードディスクまたは着脱可能ディスクなどの、磁気ディスク、光磁気ディスク、ならびにCD-ROMおよびDVD-ROMディスクを始めとする、すべての形態の不揮発性メモリ、媒体、およびメモリデバイスを含む。処理ユニットおよびメモリは、専用論理回路によって補うこと、または専用論理回路内に組み込むことができる。
【０１３７】
ユーザとの対話を提供するため、本明細書で説明された本発明の実施形態は、ユーザに情報を表示するための、例えばCRT(ブラウン管)またはLCD(液晶表示)モニタなどの表示デバイスと、ユーザがそれによってコンピュータに入力を提供できる、キーボードおよび例えばマウスまたはトラックボールなどのポインティングデバイスとを有するコンピュータ上で実施することができる。同様に、ユーザとの対話を提供するために、他の種類のデバイスを使用することもでき、例えば、ユーザに提供されるフィードバックは、例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバックなど、任意の形態の感覚フィードバックとすることができ、ユーザからの入力は、音響、音声、または触覚入力を含む、任意の形態で受け取ることができる。加えて、コンピュータは、ユーザによって使用されるデバイスに文書を送ること、およびデバイスから文書を受け取ることによって、例えば、ウェブブラウザから受け取った要求に応答して、ユーザのクライアントデバイス上のウェブブラウザにウェブページを送ることによって、ユーザと対話することができる。
【０１３８】
本明細書で説明された本発明の実施形態は、例えば、データサーバとして、バックエンド構成要素を含み、あるいは例えば、アプリケーションサーバなどの、ミドルウェア構成要素を含み、あるいは例えば、ユーザが本明細書で説明された本発明の実施とそれを通して対話できるグラフィカルユーザインタフェースもしくはウェブブラウザを有するクライアントコンピュータ、または例えばネットワークルータなどのルーティングデバイスなどの、フロントエンド構成要素を含み、あるいは1つまたは複数のそのようなバックエンド、ミドルウェア、またはフロントエンド構成要素の任意の組合せを含む、コンピューティングシステムにおいて実施することができる。システムの構成要素は、例えば、通信ネットワークなど、任意の形態または媒体のデジタルデータ通信によって相互接続することができる。通信ネットワークの例は、ローカルエリアネットワーク(「LAN」)およびワイドエリアネットワーク(「WAN」)、インタネットワーク(例えば、インターネット)、ならびにピアツーピアネットワーク(例えば、アドホックピアツーピアネットワーク)を含む。
【０１３９】
コンピューティングシステムは、クライアントおよびサーバを含むことができる。クライアントとサーバは、一般に互いに離れた場所にあり、一般に通信ネットワークを介して対話する。クライアントとサーバの関係は、それぞれのコンピュータ上で動作する、互いにクライアント-サーバ関係を有するコンピュータプログラムによって生じる。いくつかの実施形態では、サーバは、(例えば、クライアントデバイスと対話するユーザにデータを表示し、ユーザからユーザ入力を受け取る目的で)データ(例えば、HTMLページ)をクライアントデバイスに送る。クライアントデバイスにおいて生成されたデータ(例えば、ユーザ対話の結果)は、サーバにおいてクライアントデバイスから受け取ることができる。
【０１４０】
電子文書(簡潔にするため、単純に文書と呼ぶ)は、その必要はないが、ファイルに対応することができる。文書は、他の文書を保持するファイルの一部に、問題となる文書専用の単一のファイル内に、または複数の調整されたファイル内に記憶することができる。
【０１４１】
本明細書は、多くの具体的な実施詳細を含むが、これらは、いかなる発明または特許請求され得るものの範囲に対する限定とも解釈すべきではなく、むしろ、特定の発明の特定の実施形態に固有の特徴の説明と解釈すべきである。本明細書において別々の実施形態との関連で説明されたいくつかの特徴は、単一の実施形態において組み合わせて実施することもできる。反対に、単一の実施形態との関連で説明された様々な特徴は、複数の実施形態において別々に、または任意の適切なサブコンビネーションで実施することもできる。さらに、特徴は、いくつかの組合せで機能するものとして上では説明することができ、最初はそのように主張することさえできるが、主張された組合せの中の1つまたは複数の特徴は、場合によっては、組合せから除外することができ、主張された組合せは、サブコンビネーションまたはサブコンビネーションの変形を指示することができる。
【０１４２】
同様に、図面では動作が特定の順序で示されるが、これによって、示された特定の順序もしくは順次的順序でそのような動作を実行すること、または示されたすべての動作を実行することが、所望の結果を達成するために必要であると理解すべきではない。状況によっては、マルチタスキングおよび並列処理が有利であり得る。さらに、上で説明された実施形態では、様々なシステム構成要素が分離しているが、すべての実施形態においてそのような分離が必要であると理解すべきではなく、説明されたプログラム構成要素およびシステムは、一般に、単一のソフトウェア製品内に一緒に統合でき、または複数のソフトウェア製品内にパッケージ化できることを理解されたい。
【０１４３】
このように、本発明の特定の実施形態が説明された。以下の特許請求の範囲内には、他の実施形態も存在する。場合によっては、特許請求の範囲において列挙されるアクションは、異なる順序で実行することができ、それでも望ましい結果を達成することができる。加えて、添付の図面に示されたプロセスは、所望の結果を達成するために、必ずしも示された特定の順序または順次的順序を必要とするわけではない。特定の実装形態においては、マルチタスキングおよび並列処理が有利であり得る。
【符号の説明】
【０１４４】
102  プロセッサ
104  行列
106  ワード-トピック行列
110  PLDA+システム
112  文書プロセッサ
114  行列プロセッサ
116  ワード-文書行列
118  部分的なワード-トピック行列
202  文書プロセッサ
204  行列プロセッサ
206  文書プロセッサ
208  文書プロセッサ
210  文書プロセッサ
302  第1のフェッチ操作
304  第1のギブスサンプリング操作
306  第2のフェッチ操作
308  第1の更新操作
310  第2のギブスサンプリング操作
312  第3のフェッチ操作
316  第3のギブスサンプリング操作
318  第4のフェッチ操作
320  第3の更新操作
322  第4のギブスサンプリング操作
324  第4の更新操作
332  第1のフェッチ操作
334  第1のギブスサンプリング操作
336  第2のフェッチ操作
338  第1の更新操作
340  第2のギブスサンプリング操作
342  第2の更新操作
346  第3のフェッチ操作
348  第3のギブスサンプリング操作
350  第4のフェッチ操作
352  第3の更新操作
354  第4のギブスサンプリング操作
356  第4の更新操作
402a  ワード順
402b  ワード順
402c  ワード順
402d  ワード順
410  巡回待ち行列
502  W×Kワード-トピック行列
504  (W/|Pw|)×K行列
506  行列プロセッサ
510  ワード-文書行列
512  ワード-文書行列の一部
514  部分的な文書-ワード行列
516  文書プロセッサ
802  文書プロセッサ
804  要求サブシステム
806  フェッチ要求
808  スレッドプール
810a  行列プロセッサ
810b  行列プロセッサ
810c  行列プロセッサ
812  トピック分布
814  トピック分布サブシステム
816  ギブスサンプリングサブシステム
818  更新されたトピック分布
902  プロセッサ
904  文書プロセッサ
906  行列プロセッサ
【図１Ａ】
0005615991.tif 000033
【図１Ｂ】
0005615991.tif 000034
【図２】
0005615991.tif 000035
【図３Ａ】
0005615991.tif 000036
【図３Ｂ】
0005615991.tif 000037
【図４】
0005615991.tif 000038
【図５Ａ】
0005615991.tif 000039
【図５Ｂ】
0005615991.tif 000040
【図６】
0005615991.tif 000041
【図７】
0005615991.tif 000042
【図８】
0005615991.tif 000043
【図９】
0005615991.tif 000044