(57)【要約】【課題】ハードウェア・アクセラレータ全体での行列因数分解の並列化のためのコンピュータ実装方法、システム、コンピュータ・プログラム製品を提供する。【解決手段】行列因数分解をハードウェア・アクセラレータ全体で並列化するためのコンピュータ実装方法が、評価行列Ｒを受信することを含む。行列ＸがＲの行列因数分解において計算され、Ｒ≒Ｘ・ΘＴである。Ｘの計算は、変数ｐの第１の値および変数ｑの第２の値を選択することと、ΘＴを列を単位としてΘＴのｐ個パーティションに分割することと、Ｘを行を単位としてＸのｑ個のパーティションに分割することと、Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することとを含む。Ｘを計算することが、ΘＴの対応するパーティション、およびアクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、複数のアクセラレータの各アクセラレータにコピーすることをさらに含む。Ｘの計算は、複数のアクセラレータによって、Ｘの現在のパーティションの複数の部分解を計算することと、複数の部分解をＸの現在のパーティションの解に集約することとをさらに含む。【選択図】図３
2018535478.tif 000002
【特許請求の範囲】
【請求項１】
ハードウェア・アクセラレータ全体で行列因数分解を並列化するためのコンピュータ実装方法であって、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を含み、前記行列Ｘを前記計算することが、行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを前記計算することが、
ΘＴを列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘを行を単位としてＸのｑ個のパーティションに分割することと、
Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を含む、コンピュータ実装方法。
【請求項２】
前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算することをさらに含み、前記行列ΘＴを前記計算することがＸに基づき、前記行列ΘＴを前記計算することが、
ＸＴを列を単位としてＸＴのｐ個のパーティションに分割することと、
Θを行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴを行および列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を含む、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記行列Ｘを前記計算することと、前記行列ΘＴを前記計算することとを、終了条件が満たされるまで反復することをさらに含む、請求項２に記載のコンピュータ実装方法。
【請求項４】
前記Ｘの複数の部分解を前記計算することが並列スレッドによって実行される、請求項１に記載のコンピュータ実装方法。
【請求項５】
前記複数のアクセラレータがグラフィック処理装置である、請求項１に記載のコンピュータ実装方法。
【請求項６】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、前記複数のアクセラレータのメモリ容量に基づく、請求項１に記載のコンピュータ実装方法。
【請求項７】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、
【数１】
2018535478.tif 000026
となるように前記第１および第２の値を選択することを含み、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項６に記載のコンピュータ実装方法。
【請求項８】
前記ｐの第１の値が、
【数２】
2018535478.tif 000027
となるように選択され、
前記ｑの第２の値が、
【数３】
2018535478.tif 000028
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項７に記載のコンピュータ実装方法。
【請求項９】
ＸおよびΘＴに基づいてユーザへのアイテムの１つまたは複数の推薦を決定することをさらに含む、請求項１に記載の方法。
【請求項１０】
行列因数分解を実行するためのシステムであって、
メモリと、
複数のアクセラレータと、
前記メモリに通信可能に結合された１つまたは複数のコンピュータ・プロセッサとを備え、前記１つまたは複数のコンピュータ・プロセッサが、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を実行するように構成され、前記行列Ｘを前記計算することが行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを計算するために、前記１つまたは複数のコンピュータ・プロセッサが、
ΘＴを列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘを行を単位としてＸのｑ個のパーティションに分割することと、
Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を実行するようにさらに構成される、システム。
【請求項１１】
前記１つまたは複数のコンピュータ・プロセッサが、前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算するようにさらに構成され、前記行列ΘＴの前記計算がＸに基づき、前記行列ΘＴを計算するために、前記１つまたは複数のコンピュータ・プロセッサが、
ＸＴを列を単位としてＸＴのｐ個のパーティションに分割することと、
Θを行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴを行および列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を実行するようにさらに構成される、請求項１０に記載のシステム。
【請求項１２】
前記１つまたは複数のコンピュータ・プロセッサが、前記行列Ｘの前記計算および前記行列ΘＴの前記計算を終了条件が満たされるまで反復するようにさらに構成される、請求項１１に記載のシステム。
【請求項１３】
前記１つまたは複数のコンピュータ・プロセッサが、並列スレッドを使用して前記Ｘの複数の部分解を計算するようにさらに構成される、請求項１０に記載のシステム。
【請求項１４】
前記複数のアクセラレータがグラフィック処理装置である、請求項１０に記載のシステム。
【請求項１５】
前記１つまたは複数のコンピュータ・プロセッサが、前記複数のアクセラレータのメモリ容量に基づいて前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を選択するようにさらに構成される、請求項１０に記載のシステム。
【請求項１６】
前記１つまたは複数のコンピュータ・プロセッサが、
【数４】
2018535478.tif 000029
となるように前記第１および第２の値を選択することによって前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を選択するようにさらに構成され、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項１５に記載のシステム。
【請求項１７】
前記ｐの第１の値が、
【数５】
2018535478.tif 000030
となるように選択され、
前記ｑの第２の値が、
【数６】
2018535478.tif 000031
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項１６に記載のシステム。
【請求項１８】
行列因数分解をハードウェア・アクセラレータ全体で並列化するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、具現化されたプログラム命令を含んでいるコンピュータ可読記憶媒体を備え、プロセッサによって実行可能な前記プログラム命令が、前記プロセッサに、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を備える方法を実行させ、前記行列Ｘを前記計算することが、行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを前記計算することが、
ΘＴを列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘを行を単位としてＸのｑ個のパーティションに分割することと、
Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を含む、コンピュータ・プログラム製品。
【請求項１９】
前記方法が、前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算することをさらに含み、前記行列ΘＴを前記計算することがＸに基づき、前記行列ΘＴを前記計算することが、
ＸＴを列を単位としてＸＴのｐ個のパーティションに分割することと、
Θを行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴを行および列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を含む、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
前記方法が、前記行列Ｘを前記計算することと、前記行列ΘＴを前記計算することとを、終了条件が満たされるまで反復することをさらに含む、請求項１９に記載のコンピュータ・プログラム製品。
【請求項２１】
前記Ｘの複数の部分解を前記計算することが並列スレッドによって実行される、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２２】
前記複数のアクセラレータがグラフィック処理装置である、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２３】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、前記複数のアクセラレータのメモリ容量に基づく、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２４】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、
【数７】
2018535478.tif 000032
となるように前記第１および第２の値を選択することを含み、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項２３に記載のコンピュータ・プログラム製品。
【請求項２５】
前記ｐの第１の値が、
【数８】
2018535478.tif 000033
となるように選択され、
前記ｑの第１の値が、
【数９】
2018535478.tif 000034
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項２４に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は行列因数分解に関し、さらに具体的には、ハードウェア・アクセラレータ全体での行列因数分解の並列化に関する。
【背景技術】
【０００２】
行列因数分解（行列補完とも呼ばれる）は、観測から潜在的特徴を導き出すための強力なアルゴリズムである。行列因数分解の一般的な形態は、次のとおりである。観測されたエントリを一部に含み、一部に含まない観測行列Ｒが与えられたとき、Ｒは、Ｒ≒Ｘ・ΘＴの形態で、２つの高密度の低ランク行列ＸおよびΘＴ（すなわち、Θの転置）の積によって近似することができる。
【０００３】
行列因数分解は、Ｒがアイテムのユーザの評価を記録する評価行列（すなわち、ユーザ・アイテム間行列）である推薦システムで広く使用されている。電子商取引、デジタル・コンテンツのストリーミング、および検索エンジン広告を含むインターネット・アプリケーションにおいて推薦が広く浸透しており、行列因数分解は、協調フィルタリングのための最適な方法の１つであると見なされている。近年、テキスト・マイニングにおいて、単語の隠れた特徴を導き出すためにも、行列因数分解が適用されている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
行列因数分解の幅広い適用および多用途性を考えると、効率的な実装が重要になる。
【課題を解決するための手段】
【０００５】
本開示の一実施形態によれば、コンピュータ実装方法は、評価行列Ｒを受信することを含む。行列Ｘは、Ｒの行列因数分解において計算され、Ｘの計算は行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴである。さらに、行列Ｘの計算は、変数ｐの第１の値および変数ｑの第２の値を選択することと、ΘＴを列を単位としてΘＴのｐ個パーティションに分割することと、Ｘを行を単位としてＸのｑ個のパーティションに分割することと、Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することとを含む。行列Ｘの計算は、ΘＴの対応するパーティション、およびアクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、複数のアクセラレータの各アクセラレータにコピーすることをさらに含む。行列Ｘの計算は、複数のアクセラレータによって、Ｘの現在のパーティションの複数の部分解を計算することと、複数の部分解をＸの現在のパーティションの解に集約することとをさらに含む。
【０００６】
別の実施形態では、システムは、メモリ、およびメモリに通信可能に結合された１つまたは複数のコンピュータ・プロセッサを含む。１つまたは複数のコンピュータ・プロセッサは、評価行列Ｒを受信するように構成される。１つまたは複数のコンピュータ・プロセッサは、Ｒの行列因数分解において行列Ｘを計算するようにさらに構成され、行列Ｘの計算は行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴである。行列Ｘを計算するために、１つまたは複数のコンピュータ・プロセッサが、変数ｐの第１の値および変数ｑの第２の値を選択することと、ΘＴを列を単位としてΘＴのｐ個のパーティションに分割することと、Ｘを行を単位としてＸのｑ個のパーティションに分割することと、Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することとを実行するようにさらに構成される。行列Ｘを計算するために、１つまたは複数のコンピュータ・プロセッサが、ΘＴの対応するパーティション、およびアクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、複数のアクセラレータの各アクセラレータにコピーするようにさらに構成される。行列Ｘを計算するために、１つまたは複数のコンピュータ・プロセッサが、複数のアクセラレータで、Ｘの現在のパーティションの複数の部分解を計算することと、複数の部分解をＸの現在のパーティションの解に集約することとを実行するようにさらに構成される。
【０００７】
さらに別の実施形態では、行列因数分解のためのコンピュータ・プログラム製品が、具現化されたプログラム命令を含んでいるコンピュータ可読記憶媒体を含む。これらのプログラム命令は、プロセッサによって実行可能であり、プロセッサに方法を実行させる。この方法は、評価行列Ｒを受信することを含む。さらに、この方法によれば、行列Ｘは、Ｒの行列因数分解において計算され、Ｘの計算は行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴである。行列Ｘの計算は、変数ｐの第１の値および変数ｑの第２の値を選択することと、ΘＴを列を単位としてΘＴのｐ個パーティションに分割することと、Ｘを行を単位としてＸのｑ個のパーティションに分割することと、Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することとを含む。行列Ｘの計算は、ΘＴの対応するパーティション、およびアクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、複数のアクセラレータの各アクセラレータにコピーすることをさらに含む。行列Ｘの計算は、複数のアクセラレータによって、Ｘの現在のパーティションの複数の部分解を計算することと、複数の部分解をＸの現在のパーティションの解に集約することとをさらに含む。
【０００８】
その他の特徴および長所が、本発明の手法によって実現される。本発明のその他の実施形態および態様は、本明細書において詳細に説明され、請求される発明の一部と見なされる。本発明を長所および特徴と共によく理解するために、説明および図面を参照すること。
【０００９】
本発明と見なされる対象は、本明細書の最後にある特許請求の範囲において具体的に指摘され、明確に請求される。本発明の前述およびその他の特徴、および長所は、添付の図面と併せて行われる以下の詳細な説明から明らかになる。
【図面の簡単な説明】
【００１０】
【図１】本開示の一部の実施形態に記載された行列因数分解システムの図である。
【図２】本開示の一部の実施形態に記載された、行列因数分解を実行するための方法のフロー図である。
【図３】本開示の一部の実施形態に記載された行列因数分解システムの第２の図である。
【図４】本開示の一部の実施形態に記載された、行列因数分解システムの一部または全部の態様を実装するためのコンピュータ・システムのブロック図である。
【発明を実施するための形態】
【００１１】
行列因数分解処理の技術的課題は、規模および速度という２つの主要な側面にある。
【００１２】
多くの既存の手法は、約５０万人のユーザ、２万個のアイテム、および１億個の評価を含むＮｅｔｆｌｉｘ（Ｒ）の動画の推薦などの、中規模の問題を対象にしているが、産業規模の推薦問題は、そのような中規模の問題よりも２桁大きい規模に発展している。例えば、Ｆａｃｅｂｏｏｋ（Ｒ）の推薦は、１０億人のユーザ、１００万個のアイテム、および１０００億個の評価を含んでいる。非従来型のシステムは、この規模の推薦問題を効率的に処理することができる。
【００１３】
速度に関しては、推薦が変化または傾向に素早く適応する必要がある多くのオンライン・アプリケーションにおいて、行列因数分解が使用される。十分な速度を達成するために、一部の従来手法は、管理が複雑になる大規模な（例えば、５０ノードの）分散クラスターを必要とし、依然として最適な性能に達しない場合がある。
【００１４】
グラフィック処理装置（ＧＰＵ：graphics processing units）上に大規模な行列因数分解を実装することには、多くの課題がある。例えば、中央処理装置（ＣＰＵ：central processing units）に基づく多くの行列因数分解方法は、入力評価行列をブロックにスプリット（split）し、高度なブロック・スケジューリングを使用して更新の競合を防ぐ、確率的勾配降下法（ＳＧＤ：stochastic gradient descent）を使用する。従来手法は、スプリットされた行列を数十個のＣＰＵコア上で並列化することができるが、これらの手法をＧＰＵ上の数千個のコアに拡大するには、かなりの労力を必要とする。さらに、行列因数分解は本質的に疎であり、メモリによって制限され、ＧＰＵの計算能力を利用することを困難にする。さらに、ＧＰＵ上の大規模な行列因数分解は、ＧＰＵのメモリおよび相互接続の帯域幅によって制限される。
【００１５】
図１は、本開示の一部の実施形態に従う、行列因数分解システム１００の図である。一部の実施形態では、行列Ｒが評価行列（すなわち、ユーザ・アイテム間行列）であり、各Ｒ（ｉｊ）はユーザｉのアイテムｊの評価である。行列Ｒは、ｍ人のユーザとｎ個のアイテムを表すｍ×ｎ行列であってよい。図示されているように、行列因数分解システム１００は、行列因数分解によってＲを行列ＸおよびΘＴに分解することができ、Ｒ≒Ｘ・ΘＴとなるように、Ｘはｍ×ｆ行列であり、ΘＴはｆ×ｎ行列である。さらに、
【数１】
2018535478.tif 000003
はＸのｕ番目の行を示し、ｘｕはその転置であり、θｖはΘＴのｖ番目の列を示し、
【数２】
2018535478.tif 000004
はその転置である。当業者は、評価行列Ｒに基づいて、得られたＸおよびΘＴを使用して、アイテムの推薦をユーザに提供する方法を理解するであろう。
【００１６】
本明細書における行列因数分解システム１００の一部の実施形態は、広く使用されている確率的勾配降下法（ＳＧＤ）を交互最小二乗（ＡＬＳ：alternating least squares）アルゴリズムに置き換える。一般に、ＡＬＳは計算コストがＳＧＤよりも高いが、本質的に並列であり、したがって行列因数分解システム１００の一部の実施形態で非常に多くの（例えば、数千個の）ＧＰＵコアを利用することを可能にする。本開示では全体を通じてＧＰＵの使用に言及しているが、当業者は、ＧＰＵの代わりにその他のハードウェア・アクセラレータが使用されてよいということを理解するであろう。したがって、本開示においてＧＰＵが言及された場合、何らかのその他のハードウェア・アクセラレータが代用されてよいということが理解されるであろう。
【００１７】
ｒｕｖ（行列Ｒの位置（ｕ，ｖ）でのゼロ以外の要素）が与えられた場合、行列因数分解は、過剰適合を防ぐために重み付きλ正則化（weighted-λ-regularization）を使用して、次のコスト関数を最小化しようとすることができ、
【数３】
2018535478.tif 000005
および
【数４】
2018535478.tif 000006
は、ユーザｕおよびアイテムｖに関する評価の総数をそれぞれ示す。
【００１８】
【数５】
2018535478.tif 000007
【００１９】
行列因数分解システム１００は、ＡＬＳのアプローチを使用することができ、したがって、まずΘを固定したままＸを決定し、次にＸを固定したままΘを決定する。次式を考慮する。
【００２０】
【数６】
2018535478.tif 000008
この式から、次式が得られる。
【００２１】
【数７】
2018535478.tif 000009
【００２２】
【数８】
2018535478.tif 000010
【００２３】
行列因数分解システム１００の一部の実施形態では、ｘｕおよびθｖを更新するために次の解を使用できる。
【００２４】
【数９】
2018535478.tif 000011
（ｕ＝1、2、．．．ｍ）
【００２５】
【数１０】
2018535478.tif 000012
（ｕ＝1、2、．．．ｎ）
【００２６】
上の２つの式は、本明細書では解方程式と呼ばれる。
【００２７】
これらの解方程式によって、行列因数分解システム１００は、ＡＬＳアルゴリズムを使用してＸおよびΘを交互に更新することができる。経験的に、ＡＬＳは通常、５〜２０回の完全な反復で収束し、完全な反復はそれぞれ、Ｘの更新とΘの更新の両方を含む。
【００２８】
変数ｍ、ｎ、Ｎｚ、およびｆが大きくなるにつれて（Ｎｚは、行列Ｒ内のゼロ以外の要素の数）、ＡＬＳは１つのＧＰＵのメモリ容量によって制限されるようになる。既存のＣＰＵのアプローチは、このメモリ容量の問題に部分的にのみ対処する。そのような手法の１つは、並列ＡＬＳ（ＰＡＬＳ：parallel ALS）と呼ばれ、行を単位としてＸおよびＲを分割し、ΘＴを複製することによって各パーティションを並列に解く。ただし、このモデル並列性（model parallelism）は、ΘＴが小さい場合にのみ実現可能である。別のＣＰＵのアプローチであるＡｐａｃｈｅ  Ｓｐａｒｋ（ＳｐａｒｋＡＬＳ）のＡＬＳの実装は、行を単位としてＸおよびＲを分割し、その後、Ｘの各パーティションを並列に解く。この実装のＰＡＬＳへの改良は、ΘＴを複製する代わりに、ＳｐａｒｋＡＬＳが、ΘＴを重複するパーティションにスプリットするということであり、ΘＴの各パーティションは、Ｘの適用可能なパーティション内のすべてのｘｕに必要なθｖ列のみを含む。
【００２９】
ただし、ＳｐａｒｋＡＬＳにはいくつかの欠陥がある。例えば、ΘＴのパーティションをＸのパーティションから生成することは、時間のかかるグラフ分割タスクである。ΘＴの各パーティションをＸのパーティションに転送することは、特にＮｚがｍよりも非常に大きい場合、大量のネットワーク・トラフィックを伴う。さらに、ΘＴのパーティションは、特にＮｚがｍよりも非常に大きい場合、１つのノードに収まるにはまだ大きすぎる場合がある。
【００３０】
これに対して、この行列因数分解システム１００の一部の実施形態は、１つのＧＰＵの性能を向上するために、メモリ・アクセスを改善し、大きいデータ・セットを処理するために、複数のＧＰＵにおいてＡＬＳをさらに並列化する。
【００３１】
分散機械学習では、モデル並列性（例えば、行列因数分解でＸおよびΘを解くことにおける並列性）が、複数の学習機（learner）間でパラメータを分割し、各学習機がパラメータのサブセットを学習し、一方、データ並列性（data parallelism）（例えば、行列因数分解でのＲにおける並列性）が、トレーニング・データを複数の学習機間で分割し、各学習機がその部分的観測からのすべてのパラメータを学習する。行列因数分解システム１００の一部の実施形態は、これらの２つの方式を結合することができ、モデル・パラメータとトレーニング・データの両方が大きい場合に、良好な結果を実現する。
【００３２】
一部の実施形態によれば、左側エルミート行列（left-hand Hermitian matrix）Ａｕおよび右側エルミート行列（right-hand Hermitian matrix）Ｂｕが、次のように定義される。
【００３３】
【数１１】
2018535478.tif 000013
【００３４】
【数１２】
2018535478.tif 000014
【００３５】
行列因数分解システム１００の一部の実施形態では、モデル並列性が、１つのパーティションＸ（ｊ）（１≦ｊ≦ｑ）内のすべてのＡｕ（段落２１において定義される）が同じＧＰＵ上で計算されることを定める。したがって、一部の実施形態では、ΘＴのサブセットがＣＰＵのメモリからその特定のＧＰＵに転送される。さらに、行列因数分解システム１００のデータ並列化のアプローチは、各エルミート行列Ａｕの計算を複数のＧＰＵ間で分散することができる。すべてのθｖを１つのＧＰＵに転送する代わりに、行列因数分解システム１００は、下でより詳細に説明されているように、局所的なθｖを使用して各ＧＰＵ上で局所的なＡｕを計算することができ、後で局所的なＡｕを縮小する（または、集約する）ことができる。
【００３６】
各エルミート行列Ａｕは、データ並列性の形態で、次のように計算されてよい。
【００３７】
【数１３】
2018535478.tif 000015
【００３８】
このアプローチは、Θに基づいてＸを更新するための下のアルゴリズムにおいて示され、行列因数分解システム１００の一部の実施形態によって実行される。
【００３９】
【表１】
2018535478.tif 000016
【００４０】
上のアルゴリズムは、Θに基づいてＸについて解く。ただし、当業者は、Ｘに基づいてΘについて解くようにこのアルゴリズムを適応させる方法を理解するであろう。一部の実施形態では、行列因数分解システム１００の完全な反復はそれぞれ、上に従ってΘに基づいてＸについて解いてから、Ｘに基づいてΘについて解くか、またはＸに基づいてΘについて解いてから、Θに基づいてＸについて解くことを含むことができる。これらの完全な反復は、終了条件が満たされるまで、繰り返し実行されてよい。例えば、完全な反復は、ＸおよびΘの値が収束したとき、または完全な反復のしきい値回数が実行されたときに、終了することができる。
【００４１】
図２は、本開示の一部の実施形態に従って、上のアルゴリズムに基づいて行列因数分解を実行するための方法２００のフロー図である。
【００４２】
ブロック２０５で、この方法２００においてデータを分割するために、変数ｐおよびｑの値が選択されてよい。これらの変数の選択については、下で詳細に説明される。
【００４３】
ブロック２１０で、行列ΘＴが列を単位としてｐ個のパーティションに分割（すなわち、スプリット）されてよい。一部の実施形態では、この分割の前に、ΘＴが初期化されてよい。例えば、ΘＴの各要素が、−０．５〜０．５の範囲内の数値などの、小さいランダムな数値に設定されてよいが、これに限定されない。ブロック２１５で、行列Ｘが、行を単位としてｑ個のパーティションに分割されてよい。ブロック２２０で、評価行列Ｒが、行および列を単位として、ＸおよびΘＴの分割方式に従って、ｐ＊ｑ個のパーティションに分割されてよい。ブロック２１０〜２２０は、上で示されたアルゴリズムの２〜４行目に対応する。
【００４４】
ブロック２２５で、ΘＴの各パーティションが対応するＧＰＵにコピーされてよい。さらに具体的には、１≦ｉ≦ｐのｉごとに、ΘＴのｉ番目のパーティション（ΘＴ（ｉ）で示される）がＧＰＵｉにコピーされてよい。このブロック２２５は、上のアルゴリズムの５〜７行目に対応する。
【００４５】
反復ループを説明する以下の各ブロックでは、反復変数ｉおよびｊが使用され、これらの変数は両方とも１から開始される。ただし、反復ループを実装するその他の手段が使用されてもよいということが理解されるであろう。
【００４６】
ブロック２３０で、Ｘのｊ番目のパーティション（Ｘ（ｊ）と呼ばれる）が、外側のループの反復のために選択されてよい。この外側のループは、Ｘのパーティションごとに実行されてよい。一部の実施形態では、この外側のループは、並列化されたループではなく、逐次ループであってよい。ただし、一部の他の実施形態では、ΘＴのパーティションよりも多いＧＰＵを前提とした場合（すなわち、ＧＰＵの数がｐよりも多い場合）、この外側のループが並列化されてよい。１回の反復のためのＸのパーティションのこの選択は、上のアルゴリズムの８行目に対応する。
【００４７】
ブロック２３５で、ΘＴのｐ個のパーティションにわたる内側のループが並列化されてよい。複数のスレッドが使用されてよく、各スレッドがそれに割り当てられた反復を実行する。一部の実施形態では、ｐ個のスレッドが並列化に使用されてよく、各スレッドｉがパーティションΘＴ（ｉ）に割り当てられ、対応するＧＰＵｉを使用する。ただし、各スレッドが対応するＧＰＵ上で反復を実行できるほど十分な数のＧＰＵが存在しない場合（すなわち、ＧＰＵの数がｐよりも少ない場合）、この内側のループは、少なくとも一部において、逐次ループとして実装されてよい。この並列化は、上のアルゴリズムの９行目に対応する。
【００４８】
ブロック２３８で、ΘＴの各パーティションに対応するＲのパーティションが、ΘＴのそのパーティションに対応するＧＰＵにコピーされてよい。例えば、各Ｒ（ｉｊ）が対応するＧＰＵｉにコピーされてよい。このブロック２３８は、上のアルゴリズムの１０行目に対応する。
【００４９】
ブロック２４０で、ΘＴの各パーティションに対応するＧＰＵが、Ｘの選択されたパーティションの行ごとに局所的なＡｕを計算できる。具体的には、Ｘの選択されたパーティション内の行ｘｕごとに、各ＧＰＵｉが、ΘＴ（ｉ）およびＲ（ｉｊ）に基づいて局所的な左側エルミートＡｕを計算できる。この計算は、次式に従って実行されてよい。
【００５０】
【数１４】
2018535478.tif 000017
ＧＰＵは、次式に従って、局所的な右側エルミート行列をさらに計算できる。
【００５１】
【数１５】
2018535478.tif 000018
ＧＰＵｉ上の
【数１６】
2018535478.tif 000019
および
【数１７】
2018535478.tif 000020
の各集合は、本明細書では（Ａ（ｉｊ）、Ｂ（ｉｊ））として示され、ブロック２４０のこれらの計算は、上のアルゴリズムの１１行目に対応する。
【００５２】
上のアルゴリズムの１２行目に対応するブロック２４５で、内側のループの反復を実行するさまざまな並列スレッドが同期されてよい。言い換えると、ブロック２５０に進む前に、行列因数分解システム１００が、すべてのスレッドが上の処理を完了するのを待機することができる。
【００５３】
ブロック２５０で、各ＧＰＵｉにおいて、Ａ（ｉｊ）およびＢ（ｉｊ）がＸ（ｊ）の行を単位として（例えば均等に）分割されてよい。例えば、ＧＰＵｉ上のＡ（ｉｊ）がｐ個の部分
【数１８】
2018535478.tif 000021
に均等に分割されてよく、Ｂ（ｉｊ）が
【数１９】
2018535478.tif 000022
に均等に分割されてよい。ブロック２５０は、上のアルゴリズムの１３〜１４行目に対応する。
【００５４】
ブロック２５５で、ｐ個のＧＰＵにまたがるｐ個のＡ（ｉｊ）、およびｐ個のＢ（ｉｊ）が、全体的なＡ（ｊ）およびＢ（ｊ）に並列に縮小されてよい。各ＧＰＵｉは、各Ａ（ｋｊ）（１≦ｋ≦ｐ）のパーティションｉの縮小を実行できる。このブロック２５５は、上のアルゴリズムの１５〜１６行目に対応する。
【００５５】
ブロック２６０で、ｐ個のパーティションがｐ個のＧＰＵ上で同時に解かれてよい。具体的には、例えば各ＧＰＵｉは、そのＧＰＵｉがブロック２５５で縮小した局所的なパーティション
【数２０】
2018535478.tif 000023
を解くことができる。言い換えると、解方程式によって説明されたように、Ｘ（ｊ）の部分解の計算が各ＧＰＵ上で実行されてよい。
【００５６】
ブロック２６３で、これらの部分解が集約されて、Ｘ（ｊ）について解くことができる。
【００５７】
判定ブロック２６５で、ｊ＜ｑであるかどうかが決定されてよく、ｊ＜ｑであることは、選択されるべきその他のＸ（ｊ）が残っていることを示す。ｊ＜ｑである場合、ブロック２７０でｊがインクリメントされてよく、方法２００はブロック２３０に戻ることができる。
【００５８】
ブロック２１０〜２７０は、ΘＴに基づいてＸを更新する。ただし、前述したように、これは完全な反復の一部に過ぎず、Ｘに基づいてΘＴを更新することをさらに含むことができる。したがって、ブロック２７５で、Ｘに基づいてΘＴが更新されてよい。当業者は、上のアルゴリズムおよび方法２００を適用し、Ｘに基づいてΘＴを更新する方法を理解するであろう。ただし、これらの処理は、ＸＴを列を単位としてＸＴのｐ個のパーティションに分割し、Θを行を単位としてΘのｑ個のパーティションに分割し、ＲＴを行および列を単位としてＲＴのｐ＊ｑ個のパーティションに分割し、ＸＴの対応するパーティションを各アクセラレータにコピーし、アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを各アクセラレータにコピーし、アクセラレータによって、Θの現在のパーティションの部分解のセットを計算し、Θの現在のパーティションの部分解をΘの現在のパーティションの解に集約するというように、要約することができる。
【００５９】
判定ブロック２８０で、終了条件が満たされているかどうかが決定されてよい。終了条件が満たされていない場合、方法２００はブロック２１０に戻り、別の完全な反復を実行することができる。しかし、終了条件が満たされている場合、方法２００は、ＸおよびΘＴについて解かれた状態で終了することができる。
【００６０】
図３は、本開示の一部の実施形態に従って、前述されたアルゴリズムおよび方法２００を示す、行列因数分解システム１００の第２の図である。図示されたように、一部の実施形態では、ΘＴが均等に垂直方向に分割されてよく、ＧＰＵなどのｐ個のアクセラレータ３１０にまたがって記憶されてよい。Ｘは、均等に水平方向に分割され、複数のバッチに分けて解かれてよく、したがってモデル並列性を実現する。Ｘの各バッチは、ｐ個のアクセラレータ３１０にまたがって並列に解かれてよく、したがってデータ並列性を実現する。
【００６１】
上で説明されたように、変数ｐおよびｑの値は、Ｘ、ΘＴ、およびＲがどのように分割されるかを決定することができる。したがって、分割する前に、ｐおよびｑの値が選択されてよく、この選択は、上の方法２００のブロック２０５で行われてよい。
【００６２】
上の説明に従って、一部の実施形態では、１つのＧＰＵがＸ（ｊ）、ΘＴ（ｉ）、Ｒ（ｉｊ）、Ａ（ｊ）、およびＢ（ｊ）を保持する。したがって、一部の実施形態では、ｐおよびｑの選択は次の式に従い、ＣはＧＰＵのメモリ容量であり、εはゼロ以上の雑多な小さい変数のために割り当てられる余裕空間（headroom space）である。
【００６３】
【数２１】
2018535478.tif 000024
実例を挙げると、容量Ｃは１２ＧＢ、εは５００ＭＢであってよい。
【００６４】
一部の実施形態では、ｐは
【数２２】
2018535478.tif 000025
となるように選択されてよく、上の式を満たす最小のｑが選択されてよい。
【００６５】
一部の実施形態では、ｐに１の値が割り当てられてよく、その場合、Ｘが１つのＧＰＵ上で逐次的な複数のバッチに分けて解かれてよい。ｑ＞１およびｐ＝１である場合、一部の実施形態では、すでにＸをさらに分割する必要がないため、ｑをそれ以上増やす必要がない。
【００６６】
一部の実施形態では、１つまたは複数の自動化されたリソース・マネージャ、または人であるリソース・マネージャが、リソースの可用性およびコスト制約を管理することができ、行列因数分解システム１００が、ｐおよびｑの値を決定するために、それらのリソース・マネージャと通信することができる。その結果、ｐおよびｑは、コスト制約またはリソースの可用性あるいはその両方に、少なくとも部分的に基づくことができる。
【００６７】
図４に、一部の実施形態に従って、行列因数分解システム１００または方法２００の実装において使用するためのコンピュータ・システム４００のブロック図を示す。本明細書に記載された行列因数分解システム１００および方法２００は、ハードウェア、ソフトウェア（例えばファームウェア）、またはハードウェアとソフトウェアの組み合わせにおいて実装されてよい。一部の実施形態では、記載された方法は、少なくとも一部においてハードウェアに実装されてよく、パーソナル・コンピュータ、ワークステーション、マイクロコンピュータ、またはメインフレーム・コンピュータなどの、専用または汎用コンピュータ・システム４００のマイクロプロセッサの一部であってよい。
【００６８】
一部の実施形態では、図４に示されているように、コンピュータ・システム４００は、プロセッサ４０５、メモリ・コントローラ４１５に結合されたメモリ４１０、および１つまたは複数の入力デバイス４４５、またはローカルＩ／Ｏコントローラ４３５を介して通信可能に結合された周辺機器などの出力デバイス４４０、あるいはこれらの組み合わせを含む。これらのデバイス４４０および４４５は、例えば、プリンタ、スキャナ、マイクロホンなどを含むことができる。従来のキーボード４５０およびマウス４５５などの入力デバイスは、Ｉ／Ｏコントローラ４３５に結合されてよい。Ｉ／Ｏコントローラ４３５は、例えば、１つまたは複数のバスあるいは従来技術において知られたその他の有線接続または無線接続であってよい。Ｉ／Ｏコントローラ４３５は、簡単にするために省略されている、通信を可能にするためのコントローラ、バッファ（キャッシュ）、ドライバ、リピータ、およびレシーバなどのその他の要素を含むことができる。
【００６９】
Ｉ／Ｏデバイス４４０、４４５は、例えばディスク・ストレージおよびテープ・ストレージ、ネットワーク・インターフェイス・カード（ＮＩＣ：network interface card）または変調器／復調器（他のファイル、デバイス、システム、またはネットワークにアクセスするため）、無線周波（ＲＦ：radio frequency）またはその他のトランシーバ、電話インターフェイス、ブリッジ、ルータなどの、入力および出力の両方と通信するデバイスをさらに含むことができる。
【００７０】
プロセッサ４０５は、ハードウェア命令またはソフトウェア、具体的には、メモリ４１０に記憶されたハードウェア命令またはソフトウェアを実行するためのハードウェア・デバイスである。プロセッサ４０５は、カスタムメイドであるか、または市販されたプロセッサ、中央処理装置（ＣＰＵ）、コンピュータ・システム４００に関連付けられた複数のプロセッサ間の補助プロセッサ、（マイクロチップまたはチップ・セットの形態での）半導体ベースのマイクロプロセッサ、マクロプロセッサ、または命令を実行するためのその他のデバイスであってよい。プロセッサ４０５はキャッシュ４７０を含み、キャッシュ４７０は、実行可能命令のフェッチを高速化するための命令キャッシュ、データのフェッチおよび記憶を高速化するためのデータ・キャッシュ、および実行可能命令とデータの両方のための仮想アドレスから物理アドレスへの変換を高速化するために使用されるトランスレーション・ルックアサイド・バッファ（ＴＬＢ：translation lookaside buffer）を含むことができるが、これらに限定されない。キャッシュ４７０は、さらに多くのキャッシュ・レベル（Ｌ１、Ｌ２など）の階層として構造化されてよい。
【００７１】
メモリ４１０は、揮発性メモリ素子（例えば、ＤＲＡＭ、ＳＲＡＭ、ＳＤＲＡＭなどのランダム・アクセス・メモリ（ＲＡＭ：random access memory））および不揮発性メモリ素子（例えば、ＲＯＭ、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ：erasable programmable read only memory）、電子的消去可能プログラマブル読み取り専用メモリ（ＥＥＰＲＯＭ：electronically erasable programmable read only memory）、プログラマブル読み取り専用メモリ（ＰＲＯＭ：programmable read only memory）、テープ、コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：compact disc read only memory）、ディスク、フロッピー（Ｒ）・ディスク、カートリッジ、カセットなど）のうちの１つまたは組み合わせを含むことができる。さらに、メモリ４１０は電子、磁気、光、またはその他の種類のストレージ媒体を組み込むことができる。メモリ４１０が分散アーキテクチャを有することができ、分散アーキテクチャでは、さまざまなコンポーネントが互いに遠く離れた位置にあるが、プロセッサ４０５によってアクセスされてよいということに留意する。
【００７２】
メモリ４１０内の命令は、１つまたは複数の別々のプログラムを含むことができ、それらの各プログラムは、論理的機能を実装するための実行可能命令の順序付けられたリストを備える。図４の例では、メモリ４１０内の命令は、適切なオペレーティング・システム（ＯＳ：operating system）４１１を含む。オペレーティング・システム４１１は、基本的に他のコンピュータ・プログラムの実行を制御することができ、スケジューリング、入出力制御、ファイルおよびデータの管理、メモリ管理、ならびに通信制御および関連するサービスを提供する。
【００７３】
例えば、プロセッサ４０５の命令またはその他の取り出し可能な情報を含む追加データが、ストレージ４２０に記憶されてよく、ストレージ４２０はハード・ディスク・ドライブまたは半導体ドライブなどのストレージ・デバイスであってよい。メモリ４１０またはストレージ４２０に記憶される命令は、プロセッサが本開示の行列因数分解システム１００および方法２００の１つまたは複数の態様を実行できるようにする命令を含むことができる。
【００７４】
コンピュータ・システム４００は、ディスプレイ４３０に結合されたディスプレイ・コントローラ４２５をさらに含むことができる。一部の実施形態では、コンピュータ・システム４００は、ネットワーク４６５に結合するためのネットワーク・インターフェイス４６０をさらに含むことができる。ネットワーク４６５は、コンピュータ・システム４００と、外部サーバ、クライアントなどとの間での、ブロードバンド接続を介した通信用のＩＰベースのネットワークであってよい。ネットワーク４６５は、コンピュータ・システム４００と外部システムの間で、データを送受信する。一部の実施形態では、ネットワーク４６５は、サービス・プロバイダによって管理された管理ＩＰネットワークであってよい。ネットワーク４６５は、例えば、ＷｉＦｉ、ＷｉＭａｘなどの無線プロトコルおよび無線技術を使用する、無線方式で実装されてよい。ネットワーク４６５は、ローカル・エリア・ネットワーク、広域ネットワーク、メトロポリタン・エリア・ネットワーク、インターネット、またはその他の類似する種類のネットワーク環境などの、パケット交換ネットワークであってもよい。ネットワーク４６５は、固定無線ネットワーク、無線ローカル・エリア・ネットワーク（ＬＡＮ：local area network）、無線広域ネットワーク（ＷＡＮ：wide area network）、パーソナル・エリア・ネットワーク（ＰＡＮ：personal area network）、仮想プライベート・ネットワーク（ＶＰＮ：virtual private network）、イントラネット、またはその他の適切なネットワーク・システムであってよく、信号を送受信するための機器を含むことができる。
【００７５】
本開示に従う行列因数分解システム１００および方法２００は、コンピュータ・プログラム製品内または図４に示されているようなコンピュータ・システム４００内に全体的または部分的に具現化されてよい
【００７６】
一部の実施形態の技術的効果および利点は、行列因数分解で非常に多くのＧＰＵコアを利用できるようにすることを含む。さらに、一部の実施形態は、非連続メモリ・アクセスを削減すること、ホットスポットの変数（hotspot variables）をより高速なメモリ内に保持すること、およびレジスタを積極的に使用することを含めて、１つのＧＰＵのルーフライン性能（roofline performance）に近づくように、ＡＬＳにおけるメモリ・アクセスを改善する。さらに、一部の実施形態は、ＡＬＳにおいてデータ並列性をモデル並列性と結合し、革新的な並列縮小方法（parallel reduce method）を適用して、複数のＧＰＵを効率的に同時に利用する。
【００７７】
本明細書で使用される用語は、特定の実施形態を説明することのみを目的としており、本発明を限定することを意図していない。本明細書で使用される単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、特に明示的に示されない限り、複数形も含むことが意図されている。「備える（ｃｏｍｐｒｉｓｅ）」または「備えている（ｃｏｍｐｒｉｓｉｎｇ）」あるいはその両方の用語は、本明細書で使用される場合、記載された機能、整数、ステップ、処理、要素、またはコンポーネント、あるいはこれらの組み合わせの存在を示すが、１つまたは複数のその他の機能、整数、ステップ、処理、要素、コンポーネント、またはこれらのグループ、あるいはこれらの組み合わせの存在または追加を除外していないということが、さらに理解されるであろう。
【００７８】
添付の特許請求の範囲内のすべてのミーンズまたはステップ・プラス・ファンクション要素の対応する構造、材料、動作、および均等なものは、具体的に請求されるその他の請求された要素と組み合わせて機能を実行するための任意の構造、材料、または動作を含むことが意図されている。本発明の説明は、例示および説明の目的で提示されているが、網羅的であることは意図されておらず、開示された形態での発明に限定されない。本発明の範囲および思想を逸脱することなく多くの変更および変形が可能であることは、当業者にとって明らかである。本発明の原理および実際的な適用を最も適切に説明するため、およびその他の当業者が、企図されている特定の用途に適しているようなさまざまな変更を伴う多様な実施形態に関して、本発明を理解できるようにするために、実施形態が選択されて説明された。
【００７９】
本発明は、システム、方法、またはコンピュータ・プログラム製品、あるいはこれらの組み合わせであってよい。コンピュータ・プログラム製品は、プロセッサに本発明の態様を実行させるためのコンピュータ可読プログラム命令を含んでいるコンピュータ可読記憶媒体を含むことができる。
【００８０】
コンピュータ可読記憶媒体は、命令実行デバイスによって使用するための命令を保持および記憶できる有形のデバイスにすることができる。コンピュータ可読記憶媒体は、例えば、電子ストレージ・デバイス、磁気ストレージ・デバイス、光ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、またはこれらの任意の適切な組み合わせであってよいが、これらに限定されない。コンピュータ可読記憶媒体のさらに具体的な例の非網羅的リストは、ポータブル・フロッピー（Ｒ）・ディスク、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ：random access memory）、読み取り専用メモリ（ＲＯＭ：read-only memory）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭ：erasable programmable read-only memoryまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ：static random access memory）、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：compact disc read-only memory）、デジタル多用途ディスク（ＤＶＤ：digital versatile disk）、メモリ・スティック、フロッピー（Ｒ）・ディスク、パンチカードまたは命令が記録されている溝の中の隆起構造などの機械的にエンコードされるデバイス、およびこれらの任意の適切な組み合わせを含む。本明細書において使用されているコンピュータ可読記憶媒体は、本質的に、電波またはその他の自由に伝搬する電磁波、導波管またはその他の送信媒体（例えば、光ファイバ・ケーブルを通過する光パルス）を伝搬する電磁波、あるいはワイヤを介して送信される電気信号などの一時的信号そのものであると解釈されるべきではない。
【００８１】
本明細書に記載されたコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から各コンピューティング・デバイス／処理デバイスへ、またはネットワーク（例えば、インターネット、ローカル・エリア・ネットワーク、広域ネットワーク、または無線ネットワーク、あるいはこれらの組み合わせ）を介して外部コンピュータまたは外部ストレージ・デバイスへダウンロードすることができる。このネットワークは、銅伝送ケーブル、光伝送ファイバ、無線送信、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバ、あるいはこれらの組み合わせを備えてもよい。各コンピューティング・デバイス／処理デバイス内のネットワーク・アダプタ・カードまたはネットワーク・インターフェイスは、コンピュータ可読プログラム命令をネットワークから受信し、それらのコンピュータ可読プログラム命令を各コンピューティング・デバイス／処理デバイス内のコンピュータ可読記憶媒体に記憶するために転送する。
【００８２】
本発明の処理を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ：instruction-set-architecture）命令、マシン命令、マシン依存命令、マイクロコード、ファームウェア命令、状態設定データ、あるいは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋などのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同様のプログラミング言語などの従来の手続き型プログラミング言語を含む１つまたは複数のプログラミング言語の任意の組み合わせで記述されたソース・コードまたはオブジェクト・コードであってよい。コンピュータ可読プログラム命令は、ユーザのコンピュータ上で全体的に実行すること、ユーザのコンピュータ上で部分的に実行すること、スタンドアロン・ソフトウェア・パッケージとして実行すること、ユーザのコンピュータ上およびリモート・コンピュータ上でそれぞれ部分的に実行すること、あるいはリモート・コンピュータ上またはサーバ上で全体的に実行することができる。後者のシナリオでは、リモート・コンピュータを、ローカル・エリア・ネットワーク（ＬＡＮ：local area network）または広域ネットワーク（ＷＡＮ：wide area network）を含む任意の種類のネットワークを介してユーザのコンピュータに接続することができ、または接続を、（例えば、インターネット・サービス・プロバイダを使用してインターネットを介して）外部コンピュータに対して行うことができる。一部の実施形態では、本発明の態様を実行するために、例えばプログラマブル論理回路、フィールドプログラマブル・ゲート・アレイ（ＦＰＧＡ：field-programmable gate arrays）、またはプログラマブル・ロジック・アレイ（ＰＬＡ：programmable logic arrays）を含む電子回路は、コンピュータ可読プログラム命令の状態情報を利用することによって、電子回路をカスタマイズするためのコンピュータ可読プログラム命令を実行できる。
【００８３】
本発明の態様は、本明細書において、本発明の実施形態に記載された方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して説明される。フローチャート図またはブロック図あるいはその両方の各ブロック、ならびにフローチャート図またはブロック図あるいはその両方に含まれるブロックの組み合わせは、コンピュータ可読プログラム命令によって実装できるということが理解されるであろう。
【００８４】
これらのコンピュータ可読プログラム命令は、コンピュータまたはその他のプログラム可能なデータ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実施する手段を作り出すように、汎用コンピュータ、専用コンピュータ、または他のプログラム可能なデータ処理装置のプロセッサに提供されてマシンを作り出すものであってよい。これらのコンピュータ可読プログラム命令は、命令が記憶されたコンピュータ可読記憶媒体がフローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作の態様を実施する命令を含んでいる製品を備えるように、コンピュータ可読記憶媒体に記憶され、コンピュータ、プログラム可能なデータ処理装置、または他のデバイス、あるいはこれらの組み合わせに特定の方式で機能するように指示できるものであってもよい。
【００８５】
コンピュータ可読プログラム命令は、コンピュータ上、その他のプログラム可能な装置上、またはその他のデバイス上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実施するように、コンピュータ実装プロセスを生成すべく、コンピュータ、その他のプログラム可能なデータ処理装置、またはその他のデバイスにロードされ、コンピュータ上、その他のプログラム可能な装置上、またはその他のデバイス上で一連の動作可能なステップを実行させるものであってもよい。
【００８６】
図内のフローチャートおよびブロック図は、本発明のさまざまな実施形態に記載されているシステム、方法、およびコンピュータ・プログラム製品の可能な実装のアーキテクチャ、機能、および処理を示す。これに関連して、フローチャートまたはブロック図内の各ブロックは、指定された論理機能を実装するための１つまたは複数の実行可能な命令を備える、命令のモジュール、セグメント、または部分を表すことができる。一部の代替の実装では、ブロックに示された機能は、図に示された順序とは異なる順序で発生することができる。例えば、連続して示された２つのブロックは、実際には、含まれている機能に応じて、実質的に同時に実行されるか、または場合によっては逆の順序で実行されてもよい。ブロック図またはフローチャート図あるいはその両方の各ブロック、ならびにブロック図またはフローチャート図あるいはその両方に含まれるブロックの組み合わせは、指定された機能または動作を実行するか、または専用ハードウェアとコンピュータ命令の組み合わせを実行する専用ハードウェアベースのシステムによって実装できるということにも留意する。
【００８７】
本発明のさまざまな実施形態の説明は、例示の目的で提示されているが、網羅的であることは意図されておらず、開示された実施形態に限定されない。説明された実施形態の範囲を逸脱することなく多くの変更および変形が可能であることは、当業者にとって明らかである。本明細書で使用された用語は、実施形態の原理、実際の適用、または市場で見られる技術を越える技術的改良を最も適切に説明するため、または他の当業者が本明細書で開示された実施形態を理解できるようにするために選択されている。
【図１】
2018535478.tif 000035
【図２】
2018535478.tif 000036
【図３】
2018535478.tif 000037
【図４】
2018535478.tif 000038
【手続補正書】
【提出日】平成30年5月22日(2018.5.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のハードウェア・アクセラレータで行列因数分解を並列化するためのコンピュータ実装方法であって、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を含み、前記行列Ｘを前記計算することが、行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを前記計算することが、
ΘＴをその列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘをその行を単位としてＸのｑ個のパーティションに分割することと、
Ｒをその行およびその列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を含む、コンピュータ実装方法。
【請求項２】
前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算することをさらに含み、前記行列ΘＴを前記計算することがＸに基づき、前記行列ΘＴを前記計算することが、
ＸＴをその列を単位としてＸＴのｐ個のパーティションに分割することと、
Θをその行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴをその行およびその列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を含む、請求項１に記載の方法。
【請求項３】
前記行列Ｘを前記計算することと、前記行列ΘＴを前記計算することとを、終了条件が満たされるまで反復することをさらに含む、請求項２に記載の方法。
【請求項４】
前記Ｘの複数の部分解を前記計算することが並列スレッドによって実行される、請求項１乃至３のいずれかに記載の方法。
【請求項５】
前記複数のアクセラレータが複数のグラフィック処理装置である、請求項１乃至４のいずれかに記載の方法。
【請求項６】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、前記複数のアクセラレータのメモリ容量に基づく、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、
【数１】
2018535478.tif 000039
となるように前記第１および第２の値を選択することを含み、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項６に記載の方法。
【請求項８】
前記ｐの第１の値が、
【数２】
2018535478.tif 000040
となるように選択され、
前記ｑの第２の値が、
【数３】
2018535478.tif 000041
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項７に記載の方法。
【請求項９】
ＸおよびΘＴに基づいてユーザへのアイテムの１つまたは複数の推薦を決定することをさらに含む、請求項１乃至８のいずれかに記載の方法。
【請求項１０】
行列因数分解を実行するためのシステムであって、
メモリと、
複数のアクセラレータと、
前記メモリに通信可能に結合された１つまたは複数のコンピュータ・プロセッサとを備え、前記１つまたは複数のコンピュータ・プロセッサが、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を実行するように構成され、前記行列Ｘを前記計算することが行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを計算するために、前記１つまたは複数のコンピュータ・プロセッサが、
ΘＴをその列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘをその行を単位としてＸのｑ個のパーティションに分割することと、
Ｒをその行およびその列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を実行するようにさらに構成される、システム。
【請求項１１】
前記１つまたは複数のコンピュータ・プロセッサが、前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算するようにさらに構成され、前記行列ΘＴの前記計算がＸに基づき、前記行列ΘＴを計算するために、前記１つまたは複数のコンピュータ・プロセッサが、
ＸＴをその列を単位としてＸＴのｐ個のパーティションに分割することと、
Θをその行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴをその行およびその列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を実行するようにさらに構成される、請求項１０に記載のシステム。
【請求項１２】
前記１つまたは複数のコンピュータ・プロセッサが、前記行列Ｘの前記計算および前記行列ΘＴの前記計算を終了条件が満たされるまで反復するようにさらに構成される、請求項１１に記載のシステム。
【請求項１３】
前記１つまたは複数のコンピュータ・プロセッサが、並列スレッドを使用して前記Ｘの複数の部分解を計算するようにさらに構成される、請求項１０乃至１２のいずれかに記載のシステム。
【請求項１４】
前記複数のアクセラレータが複数のグラフィック処理装置である、請求項１０乃至１３のいずれかに記載のシステム。
【請求項１５】
前記１つまたは複数のコンピュータ・プロセッサが、前記複数のアクセラレータのメモリ容量に基づいて前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を選択するようにさらに構成される、請求項１０乃至１４のいずれかに記載のシステム。
【請求項１６】
前記１つまたは複数のコンピュータ・プロセッサが、
【数４】
2018535478.tif 000042
となるように前記第１および第２の値を選択することによって前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を選択するようにさらに構成され、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項１５に記載のシステム。
【請求項１７】
前記ｐの第１の値が、
【数５】
2018535478.tif 000043
となるように選択され、
前記ｑの第２の値が、
【数６】
2018535478.tif 000044
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項１６に記載のシステム。
【請求項１８】
行列因数分解を複数のハードウェア・アクセラレータで並列化するためのコンピュータ・プログラムであって、コンピュータに実行されることで、前記コンピュータに、
評価行列Ｒを受信することと、
変数ｐの第１の値および変数ｑの第２の値を選択することと、
Ｒの行列因数分解において行列Ｘを計算することと
を備える方法を実行させ、前記行列Ｘを前記計算することが、行列ΘＴに基づき、Ｒ≒Ｘ・ΘＴであり、前記行列Ｘを前記計算することが、
ΘＴを列を単位としてΘＴのｐ個のパーティションに分割することと、
Ｘを行を単位としてＸのｑ個のパーティションに分割することと、
Ｒを行および列を単位としてＲのｐ＊ｑ個のパーティションに分割することと、
ΘＴの対応するパーティションを複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつＸの現在のパーティションに対応するＲのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Ｘの現在のパーティションの複数の部分解を計算することと、
前記Ｘの現在のパーティションの前記複数の部分解を前記Ｘの現在のパーティションの解に集約することと
を含む、コンピュータ・プログラム。
【請求項１９】
前記方法が、前記行列Ｒの前記行列因数分解の前記行列ΘＴを計算することをさらに含み、前記行列ΘＴを前記計算することがＸに基づき、前記行列ΘＴを前記計算することが、
ＸＴをその列を単位としてＸＴのｐ個のパーティションに分割することと、
Θをその行を単位としてΘのｑ個のパーティションに分割することと、
ＲＴをその行およびその列を単位としてＲＴのｐ＊ｑ個のパーティションに分割することと、
ＸＴの対応するパーティションを前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記アクセラレータに対応し、かつΘの現在のパーティションに対応するＲＴのパーティションを、前記複数のアクセラレータの各アクセラレータにコピーすることと、
前記複数のアクセラレータによって、前記Θの現在のパーティションの複数の部分解を計算することと、
前記Θの現在のパーティションの前記複数の部分解を前記Θの現在のパーティションの解に集約することと
を含む、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
前記方法が、前記行列Ｘを前記計算することと、前記行列ΘＴを前記計算することとを、終了条件が満たされるまで反復することをさらに含む、請求項１９に記載のコンピュータ・プログラム。
【請求項２１】
前記Ｘの複数の部分解を前記計算することが並列スレッドによって実行される、請求項１８乃至２０のいずれかに記載のコンピュータ・プログラム。
【請求項２２】
前記複数のアクセラレータがグラフィック処理装置である、請求項１８乃至２１のいずれかに記載のコンピュータ・プログラム。
【請求項２３】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、前記複数のアクセラレータのメモリ容量に基づく、請求項１８乃至２２のいずれかに記載のコンピュータ・プログラム。
【請求項２４】
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値を前記選択することが、
【数７】
2018535478.tif 000045
となるように前記第１および第２の値を選択することを含み、Ｘがｍ×ｆ行列であり、ΘＴがｆ×ｎ行列であり、Ｒ（ｉｊ）がＲのパーティションのサイズであり、εが割り当てられる追加空間である、請求項２３に記載のコンピュータ・プログラム。
【請求項２５】
前記ｐの第１の値が、
【数８】
2018535478.tif 000046
となるように選択され、
前記ｑの第１の値が、
【数９】
2018535478.tif 000047
となる最小値になるように選択され、
前記変数ｐの前記第１の値および前記変数ｑの前記第２の値が、コスト制約およびリソースの可用性のうちの少なくとも１つに基づく、請求項２４に記載のコンピュータ・プログラム。
【国際調査報告】
2018535478.tif 000048
2018535478.tif 000049