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に記載の方法。前記加重ラウンドロビンスケジュールに従って前記ワードを割り当てるステップが、前記ワードセット内の各ワードについての重みを決定するステップと、前記複数の行列プロセッサの各々についての負荷を決定するステップと、前記ワードの重みに従って前記ワードセット内の前記ワードをソートするステップと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てるステップとを含む、請求項3に記載の方法。前記ワードセット内の前記各ワードについての前記重みを決定するステップが、前記ワードが存在する文書プロセッサの数を決定するステップを含む、請求項4に記載の方法。前記複数の行列プロセッサの前記各々についての前記負荷を決定するステップが、前記行列プロセッサ上のワードの重みの合計を決定するステップを含む、請求項5に記載の方法。第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の位置と異なる、構成することとをさらに含む、請求項9に記載のシステム。前記操作が、加重ラウンドロビンスケジュールに従って、前記ワードセット内のワードを前記複数の行列プロセッサに割り当てることをさらに含む、請求項9に記載のシステム。前記加重ラウンドロビンスケジュールに従って前記ワードを割り当てることが、前記ワードセット内の各ワードについての重みを決定することと、前記複数の行列プロセッサの各々についての負荷を決定することと、前記ワードの重みに従って前記ワードセット内の前記ワードをソートすることと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てることとを含む、請求項11に記載のシステム。前記ワードセット内の前記各ワードについての前記重みを決定することが、前記ワードが存在する文書プロセッサの数を決定することを含む、請求項12に記載のシステム。前記複数の行列プロセッサの前記各々についての前記負荷を決定することが、前記行列プロセッサ上のワードの重みの合計を決定することを含む、請求項13に記載のシステム。コンピュータ可読記憶デバイス上に符号化されるコンピュータプログラム製品であって、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の位置と異なる、構成することとをさらに含む、請求項15に記載の製品。前記操作が、加重ラウンドロビンスケジュールに従って、前記ワードセット内のワードを前記複数の行列プロセッサに割り当てることをさらに含む、請求項15に記載の製品。前記加重ラウンドロビンスケジュールに従って前記ワードを割り当てることが、前記ワードセット内の各ワードについての重みを決定することと、前記複数の行列プロセッサの各々についての負荷を決定することと、前記ワードの重みに従って前記ワードセット内の前記ワードをソートすることと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てることとを含む、請求項17に記載の製品。前記ワードセット内の前記各ワードについての前記重みを決定することが、前記ワードが存在する文書プロセッサの数を決定することを含む、請求項18に記載の製品。前記複数の行列プロセッサの前記各々についての前記負荷を決定することが、前記行列プロセッサ上のワードの重みの合計を決定することを含む、請求項19に記載の製品。前記操作が、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するように、前記1つまたは複数の文書プロセッサの各々を構成することであって、前記第1のワードバンドルが、前記ワードセットの前記第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの前記第2のサブセットに対応することをさらに含む、請求項15に記載の製品。1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることが、前記1組の1つまたは複数の文書に対してギブスサンプリングを実行することを含む、請求項15に記載の製品。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の行列プロセッサに要求することのうちの少なくとも一方を含む、ステップとを含む方法。加重ラウンドロビンスケジュールに従って、前記ワードセット内のワードを前記複数の行列プロセッサに割り当てるステップをさらに含む、請求項23に記載の方法。前記加重ラウンドロビンスケジュールに従って前記ワードを割り当てるステップが、前記ワードセット内の各ワードについての重みを決定するステップと、前記第1の行列プロセッサについての負荷および前記第2の行列プロセッサについての負荷を決定するステップと、前記ワードの重みに従って前記ワードセット内の前記ワードをソートするステップと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てるステップとを含む、請求項24に記載の方法。前記ワードセット内の前記各ワードについての前記重みを決定するステップが、前記ワードが存在する文書プロセッサの数を決定するステップを含む、請求項25に記載の方法。前記文書プロセッサにおいて、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するステップであって、前記第1のワードバンドルが、前記ワードセットの第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの第2のサブセットに対応する、ステップをさらに含む、請求項23に記載の方法。1つまたは複数の第1のトピックについて前記1組の1つまたは複数の文書をサンプリングすることが、前記1組の1つまたは複数の文書に対してギブスサンプリングを実行することを含む、請求項23に記載の方法。非一時的なコンピュータ可読記憶デバイス上に記憶されるコンピュータプログラム製品であって、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の行列プロセッサに要求することのうちの少なくとも一方を含む、実行することとを含む操作を実行させるように動作可能な製品。前記操作が、加重ラウンドロビンスケジュールに従って、前記ワードセット内のワードを前記複数の行列プロセッサに割り当てることをさらに含む、請求項29に記載の製品。前記加重ラウンドロビンスケジュールに従って前記ワードを割り当てることが、前記ワードセット内の各ワードについての重みを決定することと、前記第1の行列プロセッサについての負荷および前記第2の行列プロセッサについての負荷を決定することと、前記ワードの重みに従って前記ワードセット内の前記ワードをソートすることと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てることとを含む、請求項30に記載の製品。前記ワードセット内の前記各ワードについての前記重みを決定することが、前記ワードが存在する文書プロセッサの数を決定することを含む、請求項31に記載の製品。前記操作が、前記文書プロセッサにおいて、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行することであって、前記第1のワードバンドルが、前記ワードセットの第1のサブセットに対応し、前記第2のワードバンドルが、前記ワードセットの第2のサブセットに対応する、実行することをさらに含む、請求項29に記載の製品。拡張された並列潜在的ディリクレ配分法システムおよび方法について説明する。PLDAシステムは、複数の文書からトピックを生成するように構成された複数のプロセッサからなるシステムである。複数のプロセッサは、文書プロセッサおよび行列プロセッサの2つのタイプとして指定される。この文脈において、プロセッサという用語は、場合に応じて、文書プロセッサまたは行列プロセッサによって実行される、以下で説明するアクションを実行するように構成されたコンピュータを指す。コンピュータは、コンピュータ上にインストールされた、動作したときにアクションをシステムに実行させる、ソフトウェア、ファームウェア、ハードウェア、またはそれらの組合せを有することによって、アクションを実行するように構成することができる。同様に、1つまたは複数のコンピュータプログラムは、1つまたは複数のコンピュータによって実行されたときにアクションをコンピュータに実行させる命令を含むことによって、特定のアクションを実行するように構成することができる。文書は、文書プロセッサの間に分散される。生成されたトピックは、行列プロセッサの間に分散される。文書プロセッサおよび行列プロセッサにおいて実行されるタスクは、計算バウンドなタスクおよび通信バウンドなタスクの2つのタイプのタスクに分離される。計算バウンドなタスクは、CPU集約的なタスクであり、通信バウンドなタスクは、ネットワーク集約的なタスクである。計算バウンドなタスクおよび通信バウンドなタスクが、プロセッサ間に平衡して分散され、並列的に実行されるように、データ配置戦略およびパイプライン戦略が利用される。一般に、本明細書で説明される本発明の一態様は、1つまたは複数の文書プロセッサおよび複数の行列プロセッサを使用して、1組の1つまたは複数の文書からワードトピック行列を抽出することを含む操作において具体化することができる。ワードトピック行列は、1組の1つまたは複数の文書の複数のトピックを含む。トピックの各々は、少なくとも部分的に、ワードセットの1つまたは複数のワードによって定義される。1つまたは複数のワードの各々は、確率に関連付けられる。ワードセットは、1組の1つまたは複数の文書のワードインデックスから生成される。ワードトピック行列は、少なくとも部分的に、1つまたは複数のトピックに対応する第1の次元およびワードセットに対応する第2の次元によって定義される。行列プロセッサは、少なくとも、第1の行列プロセッサおよび第2の行列プロセッサを含む。第1の行列プロセッサは、ワードセットの第1のサブセットに対応するワードトピック行列の第1の部分を記憶および処理するように構成される。第2の行列プロセッサは、ワードセットの第2のサブセットに対応するワードトピック行列の第2の部分を記憶および処理するように構成される。1つまたは複数の文書プロセッサの各々は、トピック抽出操作および行列交換操作を実行するように構成される。トピック抽出操作は、第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つまたは複数を含むことができる。操作は、ワードセット内のワードを巡回待ち行列として組織することをさらに含む。1つまたは複数の文書プロセッサは、複数のプロセッサを含む。操作は、待ち行列の第1の位置のワードを使用してトピック抽出操作を実行し始めるように、複数の文書プロセッサの第1の文書プロセッサを構成することと、待ち行列の第2の位置のワードを使用してトピック抽出操作を実行し始めるように、複数の文書プロセッサの第2の文書プロセッサを構成することとをさらに含み、第1の位置は、第2の位置と異なる。操作は、加重ラウンドロビンスケジュールに従って、ワードセット内のワードを複数の行列プロセッサに割り当てることをさらに含むことができる。加重ラウンドロビンスケジュールに従ってワードを割り当てることは、ワードセット内の各ワードについての重みを決定することと、複数の行列プロセッサの各々についての負荷を決定することと、ワードの重みに従ってワードセット内のワードをソートすることと、最大の重みを有するワードを最小の負荷を有する行列プロセッサに反復的に割り当てることとを含むことができる。ワードセット内の各ワードについての重みを決定することは、ワードが存在する文書プロセッサの数を決定することを含むことができる。複数の行列プロセッサの各々についての負荷を決定することは、行列プロセッサ上のワードの重みの合計を決定することを含むことができる。操作は、第1のワードバンドルおよび第2のワードバンドルに基づいてトピック抽出操作を実行するように、1つまたは複数の文書プロセッサの各々を構成することをさらに含むことができる。第1のワードバンドルは、ワードセットの第1のサブセットに対応することができる。第2のワードバンドルは、ワードセットの第2のサブセットに対応することができる。1つまたは複数の第1のトピックについて1組の1つまたは複数の文書をサンプリングすることは、1組の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の行列プロセッサに要求することを含む。本明細書で説明される技法は、従来の並列潜在的ディリクレ配分法の通信ボトルネックを低減することができる。より具体的には、PLDAの性能を向上させるために、計算バウンドなタスクおよび通信バウンドなタスクが、並列的に実行される。並列処理において、計算バウンドなタスクは、通信バウンドなタスクの処理時間がトピック生成の処理時間全体に著しく寄与しないように、通信バウンドなタスクをマスクする。加えて、本明細書で説明される技法は、複数のプロセッサの間における柔軟な負荷平衡を可能にし、性能をさらに高める。加えて、PLDAを含む従来のトピック抽出方法は、しばしば、各プロセッサのメモリ内にすべてのワードトピックカウントを維持する。本明細書で説明される技法は、ワードトピック行列を複数の行列プロセッサに分散させ、各プロセッサにおけるメモリ要件を低減する。本明細書で説明される本発明の実施形態の詳細が、添付の図面および以下の説明において説明される。本発明の他の特徴、態様、および利点は、説明、図面、および特許請求の範囲から明らかになる。様々な図面における同様の参照番号および記号は、同様の要素を指示する。図1Aは、PLDA技術を使用して文書からトピックを抽出するための例示的なプロセッサを示すブロック図である。PLDAでは、文書からトピックを抽出するために、複数のプロセッサが利用される。プロセッサ102は、複数のプロセッサのうちの代表的なプロセッサである。トピック抽出操作では、トピックは、1つまたは複数のワードトピック行列として表される。従来のPLDA技術は、複数のプロセッサを利用して、文書からトピックを抽出する場合、一般に2つの特性を有する。各プロセッサは、完全なワードトピック行列を維持する。各プロセッサは、完全なワードトピック行列を他のプロセッサに送り、他のプロセッサから受け取る。それと比較して、PLDAでは、文書およびワードトピック行列は、複数のプロセッサに分散される。分散された行列は、行列交換操作において、プロセッサ間で同期が取られる。PLDAにおけるトピック抽出操作および行列交換操作は、並列的に実行され、したがって、計算および通信効率を、操作が直列的に実行される従来のPLDA技術よりも向上させる。プロセッサ102は、D個の文書からトピックを抽出するように構成され、ここで、Dは任意の数を表す。D個の文書は、P個のプロセッサ上に分散される。プロセッサ102は、P個のプロセッサの1つであり、約DP個の文書を維持する。D個の文書は、文書内のワードのボキャブラリに対応する。ボキャブラリは、W個のワードを含む。プロセッサ102は、DP個の文書とW個のワードとの間の対応を表す行列104を記憶する。行列104は、×W行列である。プロセッサ102は、ワードトピック行列106も記憶する。ワードトピック行列106は、K個のトピックとW語のボキャブラリとの間の対応を表す行列である。ワードトピック行列106は、1つの次元をトピックとし、別の次元をワードとする、K×W行列である。ワードトピック行列106内の各要素は、対応するトピックにおけるワードのカウントを表すことができる。ワードトピック行列106は、DP個の文書上でギブスサンプリングを複数回反復することによって構成することができる。ギブスサンプリングの各反復の後、ローカルなワードトピック行列をグローバルに同期させる。ローカルなワードトピック行列は、プロセッサ102にローカルに記憶されたワードトピック行列106を含む。ワードトピック行列106は、ワードトピック行列106を他のプロセッサ上に記憶された行列と同期させた場合に、グローバルに同期する。図1Bは、例示的なPLDAシステム110を示すブロック図である。PLDAシステム110では、データ配置および処理パイプライン技法を利用して、分散処理の性能を従来のPLDAよりも高める。俯瞰的には、PLDAシステム110は、文書からトピックを抽出するために、様々なプロセッサに部分的に分散された複数の行列を維持する。複数の行列は、ワードトピック行列および文書トピック行列を含む。ワードトピック行列は、ワードトピックカウント行列とも呼ばれ、Cwordによって表される。ワードトピック行列は、複数の要素を有するデータ構造であり、各要素Cwkは、トピックkに割り当てられるワードwの数である。文書トピック行列は、文書トピックカウント行列とも呼ばれ、Cdocによって表される。文書トピック行列は、複数の要素を有するデータ構造であり、各要素Ckjは、文書djに割り当てられるトピックkの数である。加えて、PLDAシステム110は、トピックカウントベクトルCtopicを維持し、その各要素Ckは、文書コレクションにおけるトピックkの割り当ての数である。zijがワードxijについてのトピック割り当てを表すとし、1つの変数zij以外のすべての変数の現在の状態を与えた場合、zijの条件付き確率は、であり、ここで、ijは、対応するワードがカウントから除外されることを表し、αおよびβは各々、ディリクレ事前分布である。式から引き出される新しいトピックをzijに割り当てる場合はいつでも、Cword、Cdoc、およびCtopicが更新される。マルコフ連鎖をトレーニングするのに十分なサンプリング反復の後、θおよびφが、以下のように推定され、ここで、θkjは、文書jを与えた場合のトピックkの確率を表し、φwkは、トピックkを与えた場合のワードwの確率を表す。PLDAシステム110は、文書プロセッサおよび行列プロセッサの2つのタイプのプロセッサを含む。文書プロセッサは、文書の維持、ギブスサンプリング操作の実行、および通信操作を含むタスクを実行できるプロセッサである。D個の文書は、Pd個の文書プロセッサ上に分散される。文書プロセッサ112は、Pd個のプロセッサの1つである。文書プロセッサ112は、約DPd個の文書を維持する。文書プロセッサ112は、ワード文書行列116を維持する。ワード文書行列116は、文書プロセッサ112のDPd個の文書とD個の文書のW語のボキャブラリとの間の対応を表す行列である。ワード文書行列116は、×W行列である。行列プロセッサは、その各々が、W×Kワードトピック行列の一部の維持を含むタスクを実行できるプロセッサである。W×Kワードトピック行列は、Pw個の行列プロセッサの間に分散される。各行列プロセッサには、W語のボキャブラリのサブセットが割り当てられる。行列プロセッサ114は、部分的なワードトピック行列118を記憶する。部分的なワードトピック行列118は、行列プロセッサ114に割り当てられたボキャブラリのサブセットに対応する、W×Kワードトピック行列の一部を含む。部分的なワードトピック行列118のワード次元は、ボキャブラリのサブセットに対応する。ワード次元の大きさは、Wおよび行列プロセッサの数であるPwの値によって決定される。部分的なワードトピック行列118のトピック次元は、K個のトピックに対応する。したがって、部分的なワードトピック行列118は、×K行列である。文書プロセッサ112は、反復的にギブスサンプリングを実行する。ギブスサンプリングの各反復の間、文書プロセッサ112は、以下の3つのステージを含むトピック発見操作において、新しいトピックをワードに割り当てる。文書プロセッサ112は、行列プロセッサ114からワードのトピック分布をフェッチする。文書プロセッサ112は、ギブスサンプリングを実行し、新しいトピックをワードに割り当てる。文書プロセッサ112は、ワードを維持する行列プロセッサを更新する。図2は、データ配置技法の例示的なトピック分布パターンを示すブロック図である。文書プロセッサ202は、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は、プロセッサが、トピック分布を更新するのに要する時間である。トピック分布のフェッチおよび更新は、通信バウンドなタスクである。示される例では、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≧TfTuである場合、PLDAシステムがW個のワードを処理するための合計時間は、WTsTfTuである。図3Bは、サンプリング時間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を実行する。TsTfTuである場合、文書プロセッサは、第2のギブスサンプリング操作340を終了した後、第2の更新操作342を実行する。その後、文書プロセッサは、第3のフェッチ操作346を実行し、文書プロセッサは、ワードw3のトピック分布をフェッチする。その後、文書プロセッサは、第3のギブスサンプリング操作348を実行し、それと並列して、第4のフェッチ操作350を実行し、文書プロセッサは、ワードw4のトピック分布をフェッチする。第3のギブスサンプリング操作348を終了した後、文書プロセッサは、第3の更新操作352および第4のギブスサンプリング操作354を実行する。最後に、文書プロセッサは、第4の更新操作356を実行する。TsTfTuである場合、PLDAシステムがW個のワードを処理するための合計時間は、WTsTfTuよりも大きい。いくつかの実施では、ギブスサンプリング操作、フェッチ操作、および更新操作は、可能な限りTs≧TfTuであるようにスケジュールされる。スケジューリングは、可能な限りTs≧TfTuとなることを保証するために、ワードバンドリング技法および低待ち時間通信スケジューリング技法を使用する。ワードバンドリングを使用する場合、ギブスサンプリング操作は、Tsが十分に長いことを保証するようなワードのグループに対して実行される。低待ち時間通信スケジューリングの下では、通信バウンドなタスクは、計算バウンドなタスクの通信バウンドなタスクによる遅延が最小限に抑えられるようにスケジュールされる。ワードバンドリング技法および低待ち時間通信スケジューリングは、以下でさらに詳細に説明される。図4は、PLDAシステムにおける例示的なワードバンドリング技法を示す図である。便宜的に、ワードバンドリング技法は、4つの文書プロセッサPd0からPd3に関連して説明される。文書プロセッサPd0からPd3は、ワード順402a~402dで、ギブスサンプリングを実行することができる。文書プロセッサの文書において数回発生するワードは、ループして処理される。さらに、頻繁に発生しないワードは、Tsが十分に長いことを保証するために、頻繁に発生するワードとバンドルされる。TfTuの値が分かっている場合、各ギブスサンプリングバンドルにおいて処理されるワード発生のカウントを決定することができる。直前のギブスサンプリングタスクが完了する時間までにフェッチが完了し、したがって、待ち時間の追加が回避される、確率を最大化するために、ワードは、TfTuが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は、ワードに従って複数の行列プロセッサに分散される。分散後、各行列プロセッサは、約WPw個のワードをワードのトピック分布とともに維持する。行列プロセッサ506は、WPw個のワードをワードのトピック分布とともに、×K行列504として記憶することができる。ワード分散を利用して、空間負荷平衡を達成することができる。行列プロセッサ506および他の行列プロセッサを各々使用して、ギブスサンプリングの反復において、ほぼ同数の要求を処理することができる。W×Kワードトピック行列502を複数の行列プロセッサに分散させる場合、PLDAシステムは、ワード重みデータ構造および作業負荷データ構造の2つのデータ構造を維持する。ワード重みデータ構造は、ワード重みを記憶するデータ構造である。ワードWiが存在する文書プロセッサの数は、ワードの重みでもあり、miによって表される。W個のワードの場合、PLDAシステムは、ベクトルを維持する。作業負荷データ構造は、行列プロセッサ506および他の各行列プロセッサの作業負荷についての情報を含むデータ構造である。行列プロセッサ506の作業負荷は、行列プロセッサ506上のすべてのワードの重みの合計として定義される。行列プロセッサPwiの作業負荷は、liによって表される。作業負荷データ構造は、によって表されるベクトルを含む。いくつかの実施では、ワードは、独立かつ一様に、ランダムに行列プロセッサ上に分散される。いくつかの実施では、加重ラウンドロビンワード配置を使用することができる。加重ラウンドロビンワード配置では、ワードは、ワードの重みによって昇順または降順にソートされる。行列プロセッサの中で行列プロセッサ506が最小の作業負荷を有する場合、W語のボキャブラリの中で最大の重みを有するワードが、行列プロセッサ506に配置される。その後、行列プロセッサ506の作業負荷が更新される。選択操作、配置操作、および更新操作は、すべてのワードが配置されるまで繰り返される。PLDAシステムが、ワードをワードのトピック分布とともに行列プロセッサ506上に配置した後、行列プロセッサ506は、文書プロセッサから初期ワードトピックカウントを受け取ることによって、担当するワードトピックカウント行列を作成する。その後、行列プロセッサ506は、文書プロセッサからの要求を処理し始める。文書プロセッサからの要求は、3つのタイプを有することができる。fetch文書プロセッサpdによるワードwのトピック分布のフェッチを求める要求。この要求に対して、行列プロセッサpwは、wのトピック分布Cwpwを返し、これは、ギブスサンプリングのために、式において、として使用される。pdにおける更新情報を使用して、ワードwのトピック分布の更新を求める要求。行列プロセッサpwは、を使用して、wのトピック分布を更新する。更新情報は、ギブスサンプリングの結果を含む。fetchpdによる行列プロセッサpwにおけるトピックカウント全部のフェッチを求める要求。行列プロセッサpwは、pwにおけるすべてのワードのトピック分布を、ベクトルとしてまとめ合わせる。pdによって各行列プロセッサからすべてのがフェッチされた後、それらは、まとめ合わされて、ギブスサンプリングのために、式において、として使用される。文書プロセッサからの要求を行列プロセッサ506において処理するための例示的なアルゴリズムが、以下のList1に示されている。いくつかの実施では、文書プロセッサのギブスサンプリング中に、すべての行列プロセッサからトピックカウント全部をフェッチするための最大間隔intermaxの値は、ボキャブラリ内のワードの数に等しく設定される。行列プロセッサ506は、行列プロセッサ506が維持を担当するワードに関するすべての要求を処理する。要求がタイムリにサービスされることを保証するため、PLDAシステムは、要求デッドラインによって要求がソートされる優先順位方式を利用する。優先順位方式におけるローカルなワード処理順位に従って、文書プロセッサは、文書プロセッサから送られるフェッチ要求の通信完了デッドラインを設定することができる。通信完了デッドラインは、それを超えた場合は要求を無視できる時間限界である。通信完了デッドラインは、様々な時間単位によって表すことができる。文書プロセッサが要求を行列プロセッサに送るとき、デッドラインが要求ヘッダ内に設定される。行列プロセッサ506は、待っている要求のデッドラインに基づいて、待っている要求にサービスする。図5Bは、文書プロセッサにおける文書配置を示している。ワード文書行列510は、ワードと文書との間のマッピングを表すために使用される。ワード文書行列510は、1つのワードから1つまたは複数の文書を識別するために使用できる逆インデックスである。ワード文書行列510は、複数の文書プロセッサの間に部分的に分散させることができる。ワード文書行列510の一部512は、DPd個の文書およびW個のワードを含むことができる。文書プロセッサ516は、一部512に対応する部分的な文書ワード行列514を記憶することができる。部分的な文書ワード行列514は、×W行列である。図6は、例示的なPLDA手順600を示すフローチャートである。PLDAシステムは、1つまたは複数の文書プロセッサ上にD個の文書を割り当てる。PLDAシステムは、文書を文書プロセッサに平衡するように割り当てる。これは、ランダム文書割り当てを利用することによって達成される。各文書プロセッサには、約DPd個の文書が割り当てられる。この割り当てステージの時間計算量は、Oである。PLDAシステムは、各文書プロセッサの文書に対する逆インデックスを構成する。逆インデックスは、ワードに基づいたインデックスである。各ワードwについてのインデックス構造は、w→...である。ワードwが文書d1内でn回発生する場合、n個のエントリが存在する。いくつかの実施では、PLDAシステムは、d1内におけるワードwのすべての発生を、1つのエントリとして記録する。PLDAシステムは、ボキャブラリ内のワードを、ギブスサンプリングのために、ワードバンドルにグループ化する。ワードをワードバンドルにグループ化することで、ギブスサンプリング操作の持続時間が、通信操作をマスクするのに十分な長さになることを保証することができる。ギブスサンプリング操作の持続時間は、通信タスクをギブスサンプリング操作の持続時間内に完了できる場合に、通信操作をマスクするのに十分な長さである。ワードが文書プロセッサにおいて1回しか発生しない場合、そのワードに対するギブスサンプリングの実行は、そのワードのトピック分布をフェッチおよび更新するのに必要な時間よりもはるかに短い時間しかかからず、マスクにはならない。マスクを確実に行えるように、PLDAシステムは、複数のワードを組み合わせてワードバンドルとし、ギブスサンプリング時間のより長い持続時間によって、通信時間をマスクできるようにする。ワードバンドル内のすべてのワードは、同じ行列プロセッサに配置され、そのため、1つの要求で、ワードバンドル内のすべてのワードについてのトピック分布をフェッチすることができる。文書プロセッサのために、PLDAシステムは、ワードの行列プロセッサに従ってワードをバンドルする。PLDAシステムは、同じ行列プロセッサに配置されるワードを、ワードが発生する回数に基づいて、降順にソートする。その後、PLDAシステムは、順序付けられたワードリストを作成する。その後、PLDAシステムは、高頻度のワードをワードリストの先頭から、1つまたは複数の低頻度のワードをワードリストの末尾から反復的に選択する。PLDAシステムは、選択された高頻度のワードおよび選択された1つまたは複数の低頻度のワードをグループ化してワードバンドルにする。ワードバンドルはそのように構成され、行列プロセッサは、トピック分布のフェッチを求める要求に応答して、ワードバンドル内のすべてのワードを返す。PLDAシステムは、通信ボトルネックを最低限に抑えるように、ワードバンドルをスケジュールする。いくつかの実施では、PLDAシステムは、ランダムスケジューリング方式に従って、ワードバンドルをスケジュールする。ランダムスケジューリング方式では、ボキャブラリ内のワードは、巡回待ち行列内に記憶される。ギブスサンプリング中、ワードは、この待ち行列から、時計回りまたは反時計回り順に選択される。各文書プロセッサは、同じ行列プロセッサへの同時アクセスを回避するために、巡回待ち行列の異なるオフセットから開始する。ボトルネックは、いくつかの行列プロセッサにおいて、複数の要求が同時に到着した場合に形成される可能性がある。したがって、いくつかの文書プロセッサは、ギブスサンプリングを開始できるようになる前に、応答を待つ必要があることがある。待ちを短縮するため、PLDAシステムは、図4Aを参照して説明したように、各要求内にデッドラインを登録する。行列プロセッサは、要求のデッドラインに従って、要求を処理する。行列プロセッサは、要求のデッドラインが過ぎてしまった場合、要求を廃棄することができる。ギブスサンプリングの確率的性質のため、ギブスサンプリングのラウンドに時折失敗しても、全体的な性能に影響は及ばない。PLDAシステムは、終了条件が満たされるまで、パイプラインベースのギブスサンプリングを反復的に実行する。ステージ603において作成された逆インデックスを使用して、文書プロセッサがワードwのトピック分布を行列プロセッサからフェッチした後に毎回、文書プロセッサは、その文書プロセッサにおけるwのすべての事例に対してギブスサンプリングを実行する。ギブスサンプリングの後、文書プロセッサは、更新された情報を対応する行列プロセッサに送り返す。文書プロセッサにおいてワードが複数回発生する場合、フェッチで1つ、更新で1つの、2つの通信タスクが実行される。式に示されるように、文書dj内の与えられたワードxijwに対して新しいトピックを計算し、割り当てるために、PLDAシステムは、ワードwについてのワードトピック分布、トピックカウントベクトルCtopic、および文書djについての文書トピック分布を獲得する。文書プロセッサは、文書トピック分布を維持する。行列プロセッサは、最新のワードトピック分布を維持する。PLDAシステムは、すべての行列プロセッサにわたるグローバルなトピックカウントベクトルCtopicを収集する。文書内のwに対して新しいトピックを割り当てる前に、文書プロセッサは、行列プロセッサにおよびCtopicを要求する。およびCtopicをフェッチした後、文書プロセッサは、ギブスサンプリングを実行し、wの発生に対して新しいトピックを割り当てる。その後、文書プロセッサは、ワードwの更新されたトピック分布を、担当する行列プロセッサに返す。文書プロセッサは、異なる処理スピードを有することができる。PLDAシステムでは、高速の文書プロセッサは、低速の文書プロセッサを待つ必要なしに、パイプラインベースのギブスサンプリングの次のラウンドを開始することができる。パイプラインベースのギブスサンプリングのさらなる詳細が、図7を参照して以下で説明される。図7は、パイプラインベースのギブスサンプリングを実行するための例示的な手順を示すフローチャートである。文書プロセッサpdが、ギブスサンプリングのために、トピックカウント全部をフェッチする。文書プロセッサpdは、トピック分布全部Ctopicをフェッチする。ステージ702において、文書プロセッサpdは、1つまたは複数のフェッチ要求fetchを各行列プロセッサにサブミットする。文書プロセッサpdは、トピックカウント全部、pw∈0Pw1を含む応答を行列プロセッサから受け取る。文書プロセッサpdは、各行列プロセッサからのトピックカウント全部を、以下の式を使用して、合計することによって、Ctopicを獲得する。文書プロセッサpdは、F個のワードバンドルを選択し、ワードのトピック分布をフェッチするために、F個のワードバンドルをスレッドプール内に置く。文書プロセッサは、1つまたは複数のフェッチ要求を行列プロセッサにサブミットする。F個のワードバンドルの各々が、フェッチ要求に対応する。文書プロセッサpdは、要求に対する応答を行列プロセッサから受け取る。応答は、トピック分布を含む。応答内のトピック分布は、待ち行列内に記憶される。スレッドプールは、要求を送り、返された応答を並列的に処理することができる。複数の要求を同時に送ることができる。同時に送られる要求には、同じデッドラインを割り当てることができる。文書プロセッサpdは、ギブスサンプリングを実行するために、待ち行列からワードのトピック分布を選択する。フェッチ要求に対する応答が行列プロセッサから返された後、文書プロセッサpdは、直ちにギブスサンプリングを開始することができる。いくつかの実施では、プリフェッチ要求の数は、Fに等しい。Fの値は、待ち行列Qpdがギブスサンプリングを待っているワードのトピック分布を常に返す確率を最大化するように設定される。いくつかの実施では、Fは、スレッドプール内のスレッドの数よりも大きくなるように設定される。文書プロセッサpdは、更新されたトピック分布を文書プロセッサpdのスレッドプール内に入れる。文書プロセッサpdのスレッドプールは、1つまたは複数の更新要求を行列プロセッサに送る。文書プロセッサpdは、新しいワードバンドルを選択し、新しいワードバンドルをスレッドプール内に置く。文書プロセッサは、更新条件が満たされているかどうかを判定する。更新条件が満たされていない場合、文書プロセッサpdは、ステージ706に進み、別のワードに対するギブスサンプリングを開始する。更新条件が満たされている場合、文書プロセッサは、新しいトピックカウント全部をフェッチする。図8は、PLDAの通信方式を示すブロック図である。文書プロセッサ802は、要求サブシステム804を含む。要求サブシステム804は、1つまたは複数のフェッチ要求806を生成するように構成される。フェッチ要求806の各々は、複数のワードw1、w2、、wnを含むワードバンドルを含む。フェッチ要求806は、スレッドプール808内に入れられる。スレッドプール808は、フェッチ要求806を行列プロセッサ810a、810b、810cに送る。行列プロセッサ810a、810b、810cは、ワードバンドル内のワードについてのトピック分布812を返す。スレッドプール808は、いくつかのビジーな行列プロセッサによるブロッキングを防止するために使用することができる。スレッドプール808内に保持することが許可されるスレッドの最大数を表すスレッドキャップ値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の数の比率γPwPdは、ギブスサンプリングの平均時間およびワードトピック行列の通信の平均時間に基づいて、計算することができる。全データセットに対するギブスサンプリングの合計時間をTsとした場合、すべてのワードのトピック分布を1つのプロセッサから別のプロセッサに転送する通信時間をTtとする。文書プロセッサ904について、サンプリング時間は、TsPdである。ワードのトピック分布は、行列プロセッサ906に同時に転送される。転送時間は、TtPwである。ギブスサンプリング操作は、以下の条件、の下で、フェッチ操作および更新操作をマスクする。であるとき、ただし、がワードのすべての事例についての平均サンプリング時間であり、かつであるとき、ただし、およびが、ワードについての平均フェッチ時間および平均更新時間とするならば、文書プロセッサ904に対する行列プロセッサ906の数の比率は、のように決定することができ、ここで、およびは、小さなデータセットに対してPLDAを実行することによって獲得することができ、その後、経験的に適切なγ値を設定することができる。本明細書で説明された本発明の実施形態および操作は、デジタル電子回路で、または本明細書で開示された構造およびそれらの構造的均等物を含む、コンピュータソフトウェア、ファームウェア、またはハードウェアで、あるいはそれらの1つまたは複数の組合せで実施することができる。本明細書で説明された本発明の実施形態は、1つまたは複数のコンピュータプログラムとして、すなわち、データ処理装置によって実行するための、またはデータ処理装置の動作を制御するための、コンピュータ記憶媒体上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして、実施することができる。代替として、または加えて、プログラム命令は、例えば、機械生成の電気、光、または電磁気信号など、人工的に生成される伝搬信号上に符号化することができ、人工的に生成される伝搬信号は、適切な受信機装置に送信し、データ処理装置によって実行するために、情報を符号化するために生成される。コンピュータ記憶媒体は、コンピュータ可読記憶デバイス、コンピュータ可読記憶基板、ランダムもしくはシリアルアクセスされるメモリアレイもしくはデバイス、またはそれらの1つまたは複数の組合せとすることができ、あるいはそれらに含めることができる。さらに、コンピュータ記憶媒体は、伝搬信号ではないが、コンピュータ記憶媒体は、人工的に生成される伝搬信号内に符号化されるコンピュータプログラム命令の送信元または送信先とすることができる。コンピュータ記憶媒体は、また、1つまたは複数の別個の物理的構成要素もしくは媒体とすることができ、あるいはそれらに含めることができる。本明細書で説明された操作は、1つまたは複数のコンピュータ可読記憶デバイス上に記憶された、あるいは他のソースから受け取ったデータに対してデータ処理装置によって実行される操作として実施することができる。データ処理装置という用語は、データを処理するためのすべての種類の装置、デバイス、および機械を包含し、例えば、プログラム可能処理ユニット、コンピュータ、システムオンチップ、パーソナルコンピュータシステム、デスクトップコンピュータ、ラップトップ、ノートブック、ネットブックコンピュータ、メインフレームコンピュータシステム、ハンドヘルドコンピュータ、ワークステーション、ネットワークコンピュータ、アプリケーションサーバ、記憶デバイス、カメラ、ビデオカメラ、セットトップボックス、モバイルデバイス、ビデオゲーム機、ハンドヘルドビデオゲームデバイスなどの消費家電デバイス、スイッチ、モデム、ルータなどの周辺デバイス、または一般に任意のタイプのコンピューティングもしくは電子デバイス、あるいは上記のうちの複数のもの、または上記のものの組合せを含む。装置は、例えば、FPGAまたはASICなどの、専用論理回路を含むことができる。装置は、ハードウェアに加えて、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、クロスプラットフォームランタイム環境、仮想マシン、あるいはそれらの1つまたは複数の組合せを構成するコードなど、問題となるコンピュータプログラムのための実行環境を生成するコードも含むことができる。装置および実行環境は、ウェブサービス、分散コンピューティングおよびグリッドコンピューティングインフラストラクチャなど、様々な異なるコンピューティングモデルインフラストラクチャを実現することができる。コンピュータプログラムは、コンパイラ言語またはインタプリタ言語、宣言型言語または手続型言語を含む、任意の形式のプログラミング言語で書くことができ、スタンドアロンプログラムの形態、またはモジュール、コンポーネント、サブルーチン、オブジェクト、もしくはコンピューティング環境で使用するのに適した他のユニットの形態を含む、任意の形態で配備することができる。コンピュータプログラムは、その必要はないが、ファイルシステム内のファイルに対応することができる。プログラムは、他のプログラムもしくはデータを保持するファイルの一部に、問題となるプログラム専用の単一のファイル内に、または複数の調整されたファイル内に記憶することができる。コンピュータプログラムは、1つのコンピュータ上で、または1つのサイトに配置された、もしくは複数のサイト間に分散され、通信ネットワークによって相互接続された、複数のコンピュータ上で実行するように配備することができる。本明細書で説明されたプロセスおよび論理フローは、入力データに操作を施し、出力を生成することによって、アクションを実行するために、1つまたは複数のコンピュータプログラムを実行する、1つまたは複数のプログラム可能処理ユニットによって実行することができる。プロセスおよび論理フローは、例えば、FPGAまたはASICなどの、専用論理回路によって実行することもでき、装置は、専用論理回路として実施することもできる。コンピュータプログラムの実行に適した処理ユニットは、例えば、汎用および専用マイクロプロセッサの両方、ならびに任意の種類のデジタルコンピュータのいずれか1つまたは複数の処理ユニットを含む。一般に、処理ユニットは、リードオンリメモリもしくはランダムアクセスメモリまたは両方から命令およびデータを受け取る。コンピュータの必須要素は、命令に従ってアクションを実行するための処理ユニットと、命令およびデータを記憶するための1つまたは複数のメモリデバイスである。一般に、コンピュータは、例えば、磁気ディスク、光磁気ディスク、または光ディスクなど、データを記憶するための1つまたは複数の大容量記憶デバイスも含み、あるいは1つまたは複数の大容量記憶デバイスからデータを受け取ること、もしくはそれらにデータを転送すること、またはその両方を行うように動作可能に結合されもする。しかし、コンピュータは、そのようなデバイスを有する必要はない。さらに、コンピュータは、例えば、ほんのいくつかの名前を挙げれば、モバイル電話、携帯情報端末、モバイルオーディオもしくはビデオプレーヤ、ゲーム機、全地球測位システム受信機、ネットワークルーティングデバイス、またはポータブル記憶デバイスフラッシュドライブなどの、別のデバイス内に埋め込むことができる。コンピュータプログラム命令およびデータを記憶するのに適したデバイスは、例として、例えば、EPROM、EEPROM、およびフラッシュメモリデバイスなどの、半導体メモリデバイス、例えば、内蔵ハードディスクまたは着脱可能ディスクなどの、磁気ディスク、光磁気ディスク、ならびにCDROMおよびDVDROMディスクを始めとする、すべての形態の不揮発性メモリ、媒体、およびメモリデバイスを含む。処理ユニットおよびメモリは、専用論理回路によって補うこと、または専用論理回路内に組み込むことができる。ユーザとの対話を提供するため、本明細書で説明された本発明の実施形態は、ユーザに情報を表示するための、例えばCRTまたはLCDモニタなどの表示デバイスと、ユーザがそれによってコンピュータに入力を提供できる、キーボードおよび例えばマウスまたはトラックボールなどのポインティングデバイスとを有するコンピュータ上で実施することができる。同様に、ユーザとの対話を提供するために、他の種類のデバイスを使用することもでき、例えば、ユーザに提供されるフィードバックは、例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバックなど、任意の形態の感覚フィードバックとすることができ、ユーザからの入力は、音響、音声、または触覚入力を含む、任意の形態で受け取ることができる。加えて、コンピュータは、ユーザによって使用されるデバイスに文書を送ること、およびデバイスから文書を受け取ることによって、例えば、ウェブブラウザから受け取った要求に応答して、ユーザのクライアントデバイス上のウェブブラウザにウェブページを送ることによって、ユーザと対話することができる。本明細書で説明された本発明の実施形態は、例えば、データサーバとして、バックエンド構成要素を含み、あるいは例えば、アプリケーションサーバなどの、ミドルウェア構成要素を含み、あるいは例えば、ユーザが本明細書で説明された本発明の実施とそれを通して対話できるグラフィカルユーザインタフェースもしくはウェブブラウザを有するクライアントコンピュータ、または例えばネットワークルータなどのルーティングデバイスなどの、フロントエンド構成要素を含み、あるいは1つまたは複数のそのようなバックエンド、ミドルウェア、またはフロントエンド構成要素の任意の組合せを含む、コンピューティングシステムにおいて実施することができる。システムの構成要素は、例えば、通信ネットワークなど、任意の形態または媒体のデジタルデータ通信によって相互接続することができる。通信ネットワークの例は、ローカルエリアネットワークおよびワイドエリアネットワーク、インタネットワーク、ならびにピアツーピアネットワークを含む。コンピューティングシステムは、クライアントおよびサーバを含むことができる。クライアントとサーバは、一般に互いに離れた場所にあり、一般に通信ネットワークを介して対話する。クライアントとサーバの関係は、それぞれのコンピュータ上で動作する、互いにクライアントサーバ関係を有するコンピュータプログラムによって生じる。いくつかの実施形態では、サーバは、データをクライアントデバイスに送る。クライアントデバイスにおいて生成されたデータは、サーバにおいてクライアントデバイスから受け取ることができる。電子文書は、その必要はないが、ファイルに対応することができる。文書は、他の文書を保持するファイルの一部に、問題となる文書専用の単一のファイル内に、または複数の調整されたファイル内に記憶することができる。本明細書は、多くの具体的な実施詳細を含むが、これらは、いかなる発明または特許請求され得るものの範囲に対する限定とも解釈すべきではなく、むしろ、特定の発明の特定の実施形態に固有の特徴の説明と解釈すべきである。本明細書において別々の実施形態との関連で説明されたいくつかの特徴は、単一の実施形態において組み合わせて実施することもできる。反対に、単一の実施形態との関連で説明された様々な特徴は、複数の実施形態において別々に、または任意の適切なサブコンビネーションで実施することもできる。さらに、特徴は、いくつかの組合せで機能するものとして上では説明することができ、最初はそのように主張することさえできるが、主張された組合せの中の1つまたは複数の特徴は、場合によっては、組合せから除外することができ、主張された組合せは、サブコンビネーションまたはサブコンビネーションの変形を指示することができる。同様に、図面では動作が特定の順序で示されるが、これによって、示された特定の順序もしくは順次的順序でそのような動作を実行すること、または示されたすべての動作を実行することが、所望の結果を達成するために必要であると理解すべきではない。状況によっては、マルチタスキングおよび並列処理が有利であり得る。さらに、上で説明された実施形態では、様々なシステム構成要素が分離しているが、すべての実施形態においてそのような分離が必要であると理解すべきではなく、説明されたプログラム構成要素およびシステムは、一般に、単一のソフトウェア製品内に一緒に統合でき、または複数のソフトウェア製品内にパッケージ化できることを理解されたい。このように、本発明の特定の実施形態が説明された。以下の特許請求の範囲内には、他の実施形態も存在する。場合によっては、特許請求の範囲において列挙されるアクションは、異なる順序で実行することができ、それでも望ましい結果を達成することができる。加えて、添付の図面に示されたプロセスは、所望の結果を達成するために、必ずしも示された特定の順序または順次的順序を必要とするわけではない。特定の実装形態においては、マルチタスキングおよび並列処理が有利であり得る。