(57)【要約】    情報処理装置（２０００）は、複数のデータ（１０）を取得する。情報処理装置（２０００）は、各データ（１０）が第１基準による分類において属するグループを表す第１行列（２０）を生成する。情報処理装置（２０００）は、各データ（１０）が第２基準による分類において属するグループを表す第２行列（３０）を生成する。情報処理装置（２０００）は、第１行列（２０）と第２行列（３０）とについてスカラー積を算出することで、第１基準のグループと第２基準のグループの各組み合わせについて、その組み合わせに含まれるデータ（１０）の個数を算出する。
2019151015.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータを取得する取得手段と、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成手段と、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成手段と、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出手段と、を有する情報処理装置。
【請求項２】
前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出手段は、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、請求項１に記載の情報処理装置。
【請求項３】
前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出手段は、前記第１行列と前記第２行列とのスカラー積を算出する、請求項１に記載の情報処理装置。
【請求項４】
前記第１行列と前記第２行列の各要素は、複数のビットで表される整数であり、
前記第１行列において同一の行のビットは、その行に対応するデータが属する前記第１基準のグループに対応するビットのみが１であって他のビットが０であり、
前記第２行列において同一の行のビットは、その行に対応するデータが属する前記第２基準のグループに対応するビットのみが１であって他のビットが０であり、
前記積算出手段による前記スカラー積の算出は、前記第１行列と前記第２行列の互いに対応する要素について、同じ順位のビット同士の論理積を算出することで整数を算出し、前記算出した整数において値が１であるビットの数を積算する処理を含む、請求項３に記載の情報処理装置。
【請求項５】
SIMD（Single Instruction Multiple Data）型プロセッサを有し、
前記 SIMD 型プロセッサを用いて、前記第１行列の生成の並列処理、前記第２行列の生成の並列処理、及び前記スカラー積の算出の並列処理のうちの少なくとも１つを実行する、請求項１乃至４いずれか一項に記載の情報処理装置。
【請求項６】
前記データは、機械学習においてモデルの学習に利用する学習サンプルである、請求項１乃至５いずれか一項に記載の情報処理装置。
【請求項７】
コンピュータによって実行される制御方法であって、
複数のデータを取得する取得ステップと、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成ステップと、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成ステップと、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出ステップと、を有する制御方法。
【請求項８】
前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、請求項７に記載の制御方法。
【請求項９】
前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列と前記第２行列とのスカラー積を算出する、請求項７に記載の制御方法。
【請求項１０】
前記第１行列と前記第２行列の各要素は、複数のビットで表される整数であり、
前記第１行列において同一の行のビットは、その行に対応するデータが属する前記第１基準のグループに対応するビットのみが１であって他のビットが０であり、
前記第２行列において同一の行のビットは、その行に対応するデータが属する前記第２基準のグループに対応するビットのみが１であって他のビットが０であり、
前記積算出ステップにおける前記スカラー積の算出は、前記第１行列と前記第２行列の互いに対応する要素について、同じ順位のビット同士の論理積を算出することで整数を算出し、前記算出した整数において値が１であるビットの数を積算する処理を含む、請求項９に記載の制御方法。
【請求項１１】
SIMD（Single Instruction Multiple Data）型プロセッサを有し、
前記 SIMD 型プロセッサを用いて、前記第１行列の生成の並列処理、前記第２行列の生成の並列処理、及び前記スカラー積の算出の並列処理のうちの少なくとも１つを実行する、請求項７乃至１０いずれか一項に記載の制御方法。
【請求項１２】
前記データは、機械学習においてモデルの学習に利用する学習サンプルである、請求項７乃至１１いずれか一項に記載の制御方法。
【請求項１３】
請求項７乃至１２いずれか一項に記載の制御方法の各ステップをコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は並列処理に関する。
【背景技術】
【０００２】
大量のデータを高速に処理することが求められている。データ処理を高速化する手法の一つに、処理の並列化がある。例えば、複数のデータを独立して操作できる繰り返し処理は、展開して並列処理することが可能である。【０００３】
データを並列に処理する技術を開示する文献として、例えば特許文献１がある。特許文献１は SIMD（Single Instruction Multiple Data）型プロセッサの発明について開示している。SIMD とは、ひとつの命令を複数のデータに対して一斉に実行することで処理を高速化する並列処理の一形態である。SIMD 型プロセッサの例としては、GPU（Graphics Processing Unit）が挙げられる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１５−１９１４６３号公報
【非特許文献】
【０００５】
【非特許文献１】Toby Segaran、「集合知プログラミング」、オライリー・ジャパン、2008年7月23日、pp. 155-180
【発明の概要】
【発明が解決しようとする課題】
【０００６】
データ処理プログラムを高速に実行するためには、その中に含まれる処理をできるだけ多く並列化することが好ましい。しかしながら、データ処理の中には並列化が難しいものもある。例えば、ひとつの繰り返し処理の中で、先に処理するデータの演算結果を、後に処理するデータの演算が使用するような処理は、並列化が難しい。特許文献１は、データ処理プログラムを並列化する手法については言及していない。【０００７】
本発明は、上記の課題に鑑みてなされたものであり、その目的の一つは、データ処理を並列化する新たな技術を提供することである。
【課題を解決するための手段】
【０００８】
本発明の情報処理装置は、１）複数のデータを取得する取得手段と、２）各データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成手段と、３）各データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成手段と、４）第１行列と第２行列に関するスカラー積を計算することで、第１基準のグループと第２基準のグループとの組み合わせごとに、その組み合わせに属するデータの個数を算出する積算出手段と、を有する。【０００９】
本発明の制御方法は、コンピュータによって実行される。当該制御方法は、１）複数のデータを取得する取得ステップと、２）各データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成ステップと、３）各データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成ステップと、４）第１行列と第２行列に関するスカラー積を計算することで、第１基準のグループと第２基準のグループとの組み合わせごとに、その組み合わせに属するデータの個数を算出する積算出ステップと、を有する。【００１０】
本発明のプログラムは、コンピュータに、本発明の制御方法が有する各ステップを実行させる。
【発明の効果】
【００１１】
本発明によれば、データ処理を並列化する新たな技術が提供される。
【図面の簡単な説明】
【００１２】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００１３】
【図１】実施形態１の情報処理装置が行う処理を概念的に示す図である。
【図２】情報処理装置によって生成される行列を例示する図である。
【図３】第１行列と第２行列とのスカラー積を算出する様子を例示する図である。
【図４】実施形態１の情報処理装置の機能構成を例示する図である。
【図５】情報処理装置を実現するための計算機を例示する図である。
【図６】実施形態１の情報処理装置によって実行される処理の流れを例示するフローチャートである。
【図７】第１行列を生成する処理の流れを例示するフローチャートである。
【図８】第２行列を生成する処理の流れを例示するフローチャートである。
【図９】第１行列と第２行列の積を算出する方法のバリエーションを例示する図である。
【図１０】第１行列と第２行列の積を算出する方法のバリエーションを例示する図である。
【図１１】第１行列と第２行列の積を算出する方法のバリエーションを例示する図である。
【図１２】決定木を例示する図である。
【図１３】C[S[k],L[j]] を示す結果行列４０の算出を例示する図である。
【図１４】複数の分割パターンについてまとめて生成された第１行列を例示する図である。
【図１５】１つの結果行列４０で複数の分割パターンについて C[S[p][k],L[j]] が示される様子を例示する図である。
【図１６】ビットベクトル整数配列 V1 として実現された第１行列と、整数配列 I1 として実現された第１行列との対応関係を例示する図である。
【図１７】ビット演算を利用して第１行列と第２行列の積を実現する方法を例示する図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。また、特に説明する場合を除き、各ブロック図において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００１５】
［実施形態１］
＜概要＞
図１は、本実施形態の情報処理装置（図４に示す情報処理装置２０００）が行う処理を概念的に示す図である。情報処理装置２０００は、複数のデータ１０を取得する。例えばデータ１０は、機械学習で学習の対象とする学習データである。
【００１６】
各データ１０は、２つの異なる基準で分類することができる。以下、２つの異なる基準をそれぞれ、第１基準と第２基準と呼ぶ。図１では、第１基準により、データ１０（d1 から d5）が、グループ g11 と g12の２つに分けられている。また、第２基準により、データ１０が、グループ g21 と g22 の２つに分けられている。
【００１７】
情報処理装置２０００は、第１基準のグループと第２基準のグループの各組み合わせについて、その組み合わせに含まれるデータ１０の個数を算出する。例えば図１の例では、第１基準のグループと第２基準のグループの組み合わせとして、１）g11 と g21、２）g11 と g22、３）g12 と g21、４）g12 と g22 という４つの組み合わせがある。そして、これらの各組み合わせに含まれるデータ１０の個数はそれぞれ、１個、１個、２個、１個である。
【００１８】
情報処理装置２０００は、前述した第１グループと第２グループの各組み合わせに含まれるデータ１０の個数を算出する処理を行列演算として実現する。こうすることで、並列処理が可能となる。まず情報処理装置２０００は、各データ１０が第１基準のどのグループに属するかを表す行列（以下、第１行列）を生成する。図２は情報処理装置２０００によって生成される行列を例示する図である。第１行列２０の各列は、それぞれ異なる第１基準のグループに対応する。図２において、第１行列２０は２つの列を有している。第１列は、データ１０が第１基準のグループ g11 に属するか否かを示す列である。第２列は、データ１０が第１基準のグループ g12 に属するか否かを示す列である。
【００１９】
第１行列２０の各行は、それぞれ異なるデータ１０について、データ１０が属する第１基準のグループを示す。具体的には、第１行列２０の行は、いずれか１つの列についてのみ１を示し、他の列については０を示すことで、値が１の列に対応する第１基準のグループにデータ１０が属していることを表す。例えば第１行列２０の１行目は、第１列の値が１であり、第２列の値が０である。そのため、第１行列２０の第１目は、１番目のデータ１０（データ d1）が、第１基準のグループ g11 に属していることを表している。同様に、情報処理装置２０００は、各データ１０が第２基準のどのグループに属するかを表す行列（以下、第２行列３０）を生成する。
【００２０】
そして情報処理装置２０００は、第１行列２０と第２行列３０とのスカラー積を算出する。図３は、第１行列２０と第２行列３０とのスカラー積を算出する様子を例示する図である。図３において、情報処理装置２０００は、第１行列２０の転置行列に対して、第２行列３０を掛け合わせている。符号４０は、このスカラー積の結果として生成される結果行列４０を表している。以下で説明するように、結果行列４０の各要素は、第１基準のグループと第２基準のグループの各組み合わせに属するデータ１０の個数を表している。
【００２１】
以下の数式（１）は、第１行列の転置行列の第ｉ行と第２行列の第ｊ列の積 pijを表している。pijは、結果行列４０のｉ行ｊ列の値となる。
【数１】
2019151015.tif 000003
なお、f'ik は第１行列２０の転置行列のｉ行ｋ列の値であり、skj は第２行列３０のｋ行ｊ列の値である。
【００２２】
第１行列２０の転置行列のｉ行ｋ列と、第２行列３０のｋ行ｊ列との積は、これらの双方が１の場合のみ１となる。ここで、第１行列２０の転置行列のｉ行ｋ列は、第１行列２０のｋ行ｉ列に相当する。そのため、第１行列２０の転置行列のｉ行ｋ列が１であることは、ｋ番目のデータ１０が、第１基準のｉ番目のグループに属することを意味する。一方、第２行列のｋ行ｊ列が１であることは、ｋ番目のデータ１０が、第２基準のｊ番目のグループに属することを意味する。以上のことから、第１行列２０の転置行列のｉ行ｋ列と、第２行列３０のｋ行ｊ列との積は、ｋ番目のデータ１０が、第１基準のi番目のグループに属し、なおかつ第２基準のｊ番目のグループに属する場合においてのみ１となる。よって、数式（１）により、第１基準のi番目のグループに属し、なおかつ第２基準のｊ番目に属するデータ１０の個数を算出することができる。
【００２３】
以上のことから、第１行列２０の転置行列と第２行列３０との積を算出することで、その結果として得られる結果行列４０により、第１基準のグループと第２基準のグループの各組み合わせについて、その組み合わせに含まれるデータ１０の個数を得ることができる（図３参照）。
【００２４】
なお、詳しくは後述するが、第１行列２０と第２行列３０の積を算出する方法は、第１行列２０の転置行列に第２行列３０を掛け合わせる方法に限定されない。
【００２５】
また、第１行列２０と第２行列３０に設定する値は、０と１に限定されない。例えば、位数の十分大きい適当な環を考えて、０の代わりにゼロ因子を、１の代わりに単位元等の適当な非ゼロ因子を用いてもよい。第１行列２０と第２行列３０に設定する値を０と１以外にする具体的なケースについては後述する。
【００２６】
＜作用・効果＞
本実施形態の情報処理装置２０００は、第１基準によってデータ１０を分類した第１グループと、第２基準によってデータ１０を分類した第２グループとの組み合わせについて、各組み合わせに属するデータ１０の数を算出する。一般的に、複数のグループそれぞれに属するデータの個数を算出する処理は、カウンタ変数を利用した数え上げ処理によって実現される。具体的には、グループごとにカウンタ変数を用意した上で、「データがどのグループに属しているかを判定し、属していると判定されたグループのカウンタ変数に１を加算する」という繰り返し処理を各データについて実行する。
【００２７】
このようにカウンタ変数を更新する繰り返し処理を展開して並列化すると、複数のプロセスやスレッドでカウンタ変数を共有することになる。そのため、複数のプロセス等が同時にカウンタ変数を更新しようとしてデータの不整合が発生してしまう可能性があり、単純な展開による並列化はできない。
【００２８】
このようにカウンタ変数を利用してグループに属するデータの個数を算出する処理を並列化する方法の１つとして、カウンタ変数へのアクセスで排他制御を行う方法がある。しかしながらこの方法では、一度に１つのプロセス等しかカウンタ変数にアクセスできないため、データ処理に要する時間を削減する効果が小さくなってしまう。
【００２９】
この点、後述するように、本実施形態の情報処理装置２０００が実行する処理は、排他制御を行うことなく並列化が可能である。そのため、情報処理装置２０００によれば、データ処理に要する時間を大きく削減することができる。
【００３０】
カウンタ変数を利用してグループに属するデータの個数を算出する処理を並列化する別の方法として、プロセス等ごとに別々のカウンタ変数を設けることにより、カウンタ変数を共有しないようにする方法も考えられる。しかしながらこの方法では、並列数を増やすほどカウンタ変数の数も増やす必要があり、メモリやストレージデバイスといった記憶領域の消費量が多くなってしまう。
【００３１】
この点、本実施形態の情報処理装置２０００では、プロセス等ごとにカウンタ変数を用意するという必要がない。そのため、上述の方法よりも記憶領域の消費量を少なくすることができる。
【００３２】
以下、本実施形態の情報処理装置２０００についてさらに詳細に説明する。
【００３３】
＜情報処理装置２０００の機能構成の例＞
図４は、実施形態１の情報処理装置２０００の機能構成を例示する図である。情報処理装置２０００は、取得部２０２０、第１行列生成部２０４０、第２行列生成部２０６０、及び積算出部２０８０を有する。取得部２０２０は複数のデータ１０を取得する。第１行列生成部２０４０は第１行列２０を生成する。第１行列２０は、各データ１０が第１基準の分類においていずれのグループに属するかを表す。第２行列生成部２０６０は第２行列３０を生成する。第２行列３０は、各データ１０が第２基準の分類においていずれのグループに属するかを表す。積算出部２０８０は、第１行列２０と第２行列３０の積を計算することで、第１基準のグループと第２基準のグループとの組み合わせごとに、属するデータ１０の個数を算出する。
【００３４】
＜情報処理装置２０００のハードウエア構成＞
情報処理装置２０００の各機能構成部は、各機能構成部を実現するハードウエア（例：ハードワイヤードされた電子回路など）で実現されてもよいし、ハードウエアとソフトウエアとの組み合わせ（例：電子回路とそれを制御するプログラムの組み合わせなど）で実現されてもよい。以下、情報処理装置２０００の各機能構成部がハードウエアとソフトウエアとの組み合わせで実現される場合について、さらに説明する。
【００３５】
図５は、情報処理装置２０００を実現するための計算機１０００を例示する図である。計算機１０００は任意の計算機である。例えば計算機１０００は、Personal Computer（PC）やサーバマシンなどである。計算機１０００は、情報処理装置２０００を実現するために設計された専用の計算機であってもよいし、汎用の計算機であってもよい。
【００３６】
計算機１０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、及び入出力インタフェース１１００を有する。バス１０２０は、プロセッサ１０４０、メモリ１０６０、ストレージデバイス１０８０、及び入出力インタフェース１１００が、相互にデータを送受信するためのデータ伝送路である。ただし、プロセッサ１０４０などを互いに接続する方法は、バス接続に限定されない。
【００３７】
プロセッサ１０４０は、CPU（Central Processing Unit）、FPGA（Field-Programmable Gate Array）、GPU（Graphics Processing Unit）などの種々のプロセッサである。ここで情報処理装置２０００は、データ処理の並列処理を行う。並列処理を実現する方法の一つとして、GPU などの SIMD 型プロセッサを利用する方法がある。情報処理装置２０００が SIMD 型プロセッサを利用して並列処理を行う場合、プロセッサ１０４０を SIMD 型プロセッサとしてもよいし、プロセッサ１０４０とは別のプロセッサとして SIMD 型プロセッサを設けてもよい。後者の場合、例えば情報処理装置２０００は、並列処理が可能な演算を SIMD 型プロセッサに実行させ、それ以外の演算をプロセッサ１０４０に実行させる。
【００３８】
なお、並列処理を実現する方法は、SIMD 型プロセッサを利用する方法に限定されない。例えば、プロセッサコア間並列や計算機間並列などの形態で並列処理を実現してもよい。そのため、情報処理装置２０００は必ずしも SIMD 型プロセッサを有する必要はない。
【００３９】
メモリ１０６０は、RAM（Random Access Memory）などを用いて実現される主記憶装置である。ストレージデバイス１０８０は、ハードディスク、SSD（Solid State Drive）、メモリカード、又は ROM（Read Only Memory）などを用いて実現される補助記憶装置である。
【００４０】
入出力インタフェース１１００は、計算機１０００と入出力デバイスとを接続するためのインタフェースである。例えば入出力インタフェース１１００には、キーボードなどの入力装置や、ディスプレイ装置などの出力装置が接続される。
【００４１】
ストレージデバイス１０８０は、情報処理装置２０００の各機能構成部を実現するプログラムモジュールを記憶している。プロセッサ１０４０は、これら各プログラムモジュールをメモリ１０６０に読み出して実行することで、各プログラムモジュールに対応する機能を実現する。
【００４２】
＜処理の流れ＞
図６は、実施形態１の情報処理装置２０００によって実行される処理の流れを例示するフローチャートである。取得部２０２０はデータ１０を取得する（Ｓ１０２）。第１行列生成部２０４０は第１行列２０を生成する（Ｓ１０４）。第２行列生成部２０６０は第２行列３０を生成する（Ｓ１０６）。積算出部２０８０は第１行列と第２行列の積を算出する（Ｓ１０８）。ここで、第１行列２０の生成と第２行列３０の生成は、必ずしもこの順に行われる必要はない。また、これらの処理は並列で実行されてもよい。
【００４３】
＜データ１０の取得：Ｓ１０２＞
取得部２０２０はデータ１０を取得する（Ｓ１０２）。ここで、情報処理装置２０００がデータ１０を取得する方法は様々である。例えば取得部２０２０は、データ１０が記憶されている記憶装置からデータ１０を取得する。データ１０が記憶されている記憶装置は、情報処理装置２０００の内部に設けられていてもよいし、外部に設けられていてもよい。その他にも例えば、取得部２０２０は、他の装置によって送信されるデータ１０を受信することで、データ１０を取得してもよい。
【００４４】
＜第１行列２０の生成：Ｓ１０４＞
第１行列生成部２０４０は第１行列２０を生成する。前述したように第１行列２０は、各データ１０が第１基準のいずれのグループに属するかを表す行列である。例えば第１行列生成部２０４０は、以下で説明する流れで第１行列２０を生成する。
【００４５】
図７は、第１行列２０を生成する処理の流れを例示するフローチャートである。第１行列生成部２０４０は、グループ番号ｋを０に初期化する（Ｓ２０２）。Ｓ２０４からＳ２２０は、各グループ g1[k] について行われるループ処理Ａである。Ｓ２０４において、第１行列生成部２０４０は、グループ番号ｋの値が第１基準のグループの総数 Ng1 未満であるか否かを判定する。k が Ng1 未満である場合、図７の処理はＳ２０５に進む。一方、k が Ng1 以上である場合、図７の処理は終了する。
【００４６】
Ｓ２０５において、第１行列生成部２０４０は、データ番号ｉを０に初期化する。Ｓ２０６から２１６は、データ１０の順列 D に含まれる各データ１０について行われるループ処理Ｂである。Ｓ２０６において、第１行列生成部２０４０は、データ番号ｉがデータ１０の個数 Nd 未満であるか否かを判定する。i が Nd 未満である場合、図７の処理はＳ２０８に進む。一方、i が Nd 以上である場合、図７の処理は２１８に進む。
【００４７】
Ｓ２０８において、第１行列生成部２０４０は、ｉ番目のデータ１０である D[i] が、第１基準の k 番目のグループである g1[k] に含まれるか否かを判定する。D[i] が g1[k] に含まれる場合（Ｓ２０８：ＹＥＳ）、第１行列生成部２０４０は、第１行列２０の i 行 k 列の値である f[i][k] に１を設定する（Ｓ２１０）。一方、D[i] が g1[k] に含まれない場合（Ｓ２０８：ＮＯ）、第１行列生成部２０４０は、f[i][k] に０を設定する（Ｓ２１２）。
【００４８】
Ｓ２１４において、第１行列生成部２０４０は i に１を加算する。Ｓ２１６はループ処理Ｂの終端であるため、図７の処理はＳ２１６からＳ２０６に進む。
【００４９】
Ｓ２１８において、第１行列生成部２０４０は k に１を加算する。Ｓ２２０はループ処理Ａの終端であるため、図７の処理はＳ２１８からＳ２０４に進む。
【００５０】
ここで、ループ処理Ｂ（Ｓ２０６からＳ２１６）には、共有変数へアクセスする処理が存在しないため、排他制御を行うことなく並列化が可能である。よってループ処理Ｂは、展開して並列処理することにより、高速に実行することができる。
【００５１】
＜＜コンピュータプログラムにおける行列の表現方法について＞＞
ここで、コンピュータプログラムで行列を表現する場合、数値を格納できる型の変数（例えば整数型やフロート型の変数）の２次元配列を用意し、行列の各要素を配列の各要素に対応させる。例えば情報処理装置２０００は、２次元配列 f[][] を用意し、第１行列２０のｉ行ｊ列の値を f[i][j] に格納する。すなわち、第１行列２０の要素一つにつき、変数を一つ用意する。その結果、プロセッサでは、行列の要素一つにつき、一つのレジスタが使用される。
【００５２】
しかしながら、必ずしも行列の要素一つにつき変数を一つ用意する必要はない。すなわち、行列の複数の要素を一つの変数に対応させてもよい。行列の複数の要素を一つの変数に対応させるケースの具体的な実現方法は、第２の実施形態として説明する。
【００５３】
＜第２行列３０の生成：Ｓ１０６＞
第２行列生成部２０６０は第２行列３０を生成する。ここで、第２行列３０の生成方法は、第１行列２０の生成方法と同様である。図８は、第２行列３０を生成する処理の流れを例示するフローチャートである。図８において、g2[k] は第２基準のｋ番目のグループを表し、Ng2 は第２基準のグループの総数を表し、s[i][k] は第２行列３０のｉ行ｋ列の値を表す。
【００５４】
ここで、図７のループ処理Ｂと同様に、図８のループ処理Ｄ（Ｓ３０６から３２１６）内の処理は、排他制御を行うことなく並列化が可能である。よってループ処理Ｄは、展開して並列処理することにより、高速に実行することができる。
【００５５】
＜積の算出：Ｓ１０８＞
積算出部２０８０は、第１行列２０と第２行列３０の積を算出することで、結果行列４０を得る（Ｓ１０８）。結果行列４０は、第１基準のグループと第２基準のグループとの各組み合わせについて、その組み合わせに含まれるデータ１０の個数を示す（図３参照）。
【００５６】
第１行列２０と第２行列３０の積を算出する方法は、第１行列２０と第２行列３０の構成に依存する。図９から図１１は、第１行列２０と第２行列３０の積を算出する方法のバリエーションを例示する図である。図９では、第１行列２０の各行がそれぞれ異なるデータ１０に関する情報を示し、なおかつ第２行列３０の各行がそれぞれ異なるデータ１０に関する情報を示している。この場合、積算出部２０８０は、左から掛ける行列を転置する。例えば図９では、第１行列２０が左側であるため、第１行列２０の転置行列を生成し、第１行列２０の転置行列に右から第２行列３０を掛ける。ただし、第２行列３０を左側にし、第２行列３０の転置行列に右から第１行列２０を掛けるようにしてもよい。
【００５７】
図１０では、第１行列２０の各列がそれぞれ異なるデータ１０に関する情報を示し、なおかつ第２行列３０の各列がそれぞれ異なるデータ１０に関する情報を示している。この場合、右側の行列を転置する。図１０では、右側にある第２行列３０を転置している。
【００５８】
図１１では、第１行列２０の各列がそれぞれ異なるデータ１０に関する情報を示し、なおかつ第２行列３０の各行がそれぞれ異なるデータ１０に関する情報を示している。すなわち、図１１の第１行列２０の構成は、図９における転置後の第１行列２０の構成と同じである。この場合、第１行列２０や第２行列３０を転置する必要はなく、第１行列２０の右から第２行列３０を掛けることで、第１行列２０と第２行列３０との積を算出することができる。
【００５９】
＜並列処理の具体的な方法＞
情報処理装置２０００は、第１行列２０と第２行列３０の積を算出する処理の少なくとも一部を並列処理する。例えば、数式（１）で示した行列の要素間の積「f'[i][k]*s[k][j]」を１つ以上並列に実行する。なお、この積の計算は全ての i, j, k についてそれぞれ独立であるため、例えば情報処理装置２０００は、i, j, k の全組み合わせについて積「f'[i][k]*s[k][j]」を並列に実行してもよい。また、数式（１）に示すように、この積の計算の結果は、i, j の組み合わせごとに積算される。そこで例えば、情報処理装置２０００は、i, j の複数の組み合わせそれぞれについて行われる積の計算を並列処理してもよい。
【００６０】
また前述したように、情報処理装置２０００は、第１行列２０の生成におけるループ処理Ｂを並列処理したり、第２行列３０の生成におけるループ処理Ｄを並列処理したりしてもよい。なお、繰り返し処理を並列化する具体的な手法には、既存の手法を利用することができる。例えばこのような繰り返し処理は、コンパイラによって並列処理に展開することができる。
【００６１】
＜利用例＞
情報処理装置２０００についてさらに具体的な説明をするために、情報処理装置２０００の利用例について説明する。なお、以下で説明するのはあくまで情報処理装置２０００の活用方法の一例であり、情報処理装置２０００の活用範囲を限定するものではない。
【００６２】
本利用例では、決定木モデルを利用した機械学習を行う。データ１０は、１つ以上の属性データの列にラベルが付された学習サンプルである。属性は、予測の根拠として利用する情報であり、特徴量や説明変数などとも呼ばれる。ラベルとは、学習サンプルを学習済みのモデルに入力した場合に出力されるべきデータを表す。
【００６３】
図１２は、決定木を例示する図である。この決定木は、複数のサービスクラスが用意されているウェブサービスにおいて、新規のユーザが一定の使用期間後に選択するサービスについて予測するモデルである。サービスクラスとしてプラチナ、ゴールド、ベーシックが用意されているため、ユーザには、１）プラチナで契約、２）ゴールドで契約、３）ベーシックで契約、４）契約しないという４つの選択肢がある。
【００６４】
決定木モデルの生成に利用される学習サンプル（データ１０）は、既に上記選択が行われたユーザに関するデータであり、ユーザに関する情報や使用期間中のユーザの行動を属性データとして示し、ユーザが行った選択を正解ラベルとして示す。
【００６５】
決定木学習のアルゴリズムには様々なものが存在する。例えば、古典的な決定木学習アルゴリズムの一例が非特許文献１に記載されている。決定木を構築するための中核となる処理は、学習サンプル群を、重複も漏れもない部分学習データからなるグループに分割し、その分割の良し悪しを評価する処理である。分割の良し悪しは、分割前の学習サンプル群と、分割後の部分学習サンプル群に、どのラベルがどれだけ含まれているかによって決まる。
【００６６】
ここで、学習サンプル群を分割する良し悪しを評価する基準は、「学習サンプル群を或る属性データの或る閾値でグループに分割した場合に、その分割の前後で情報利得が最も大きくなる分割が最良の分割である」というものである。情報利得とは確率分布の差異を計る尺度である。
【００６７】
学習サンプル群 S を K 個の学習サンプル群 {S[1], S[2], ... , S[K]} に分割する場合、すなわち K 分木（K-ary Tree）を構築する場合を考える。学習サンプル群に含まれる「ラベルの不純度」を計算する何らかの関数 F を用いれば、情報利得 D は以下の数式（２）で表される。
【数２】
2019151015.tif 000004
N[k] は、学習サンプル群 S[k] に含まれる学習データの個数を表す。N は、学習サンプルの総数を表す。
【００６８】
数式（２）の右辺における第一項は、分割前の学習サンプル群に含まれるラベルの不純度であり、第二項の総和は、分割後の各々の学習サンプル群に含まれるラベルの不純度の加重平均である。なお、情報利得 D がゼロ以下の値となる場合は、学習サンプル群をそれ以上分割できないことを意味する。
【００６９】
ラベルの不純度とは、学習データに含まれるラベルの種類と出現数によって定まる指標であり、実際の計算にはジニ不純度や情報エントロピーと呼ばれる尺度が用いられる。
【００７０】
例えば、N 個の学習サンプルからなる学習サンプル群 S に対して M 種類のラベルがあり、j 番目のラベル L[j] の出現数が C[S, L[j]]（1≦j≦M）であるとする。このとき、学習サンプル群 S のジニ不純度 G(S) は数式（３）で表される。また、情報エントロピー H(S) は数式（４）で表される。
【数３】
2019151015.tif 000005
【数４】
2019151015.tif 000006
【００７１】
各ラベルの出現数 C[S,L[j]] は、一般的には、学習サンプル群 S に含まれる学習サンプル全体に渡る繰り返し処理によって数え上げる必要がある。古典的には、決定木のノードをひとつ構築する度に、学習データに含まれるすべての属性とすべての閾値の組み合わせを試行して最良の分割を見つけ出す必要がある。そのため、ラベルの出現数を数え上げる処理は、決定木に新たにノードを追加する度に、そして属性と閾値の組み合わせが変化する度に、毎回行う必要がある頻出処理である。
【００７２】
一般に、ラベル出現数の数え上げは、カウンタ変数を用意し、数え上げ対象のラベルが出現する度にそのカウンタ変数を更新していくという繰り返し処理によって実現される。しかしながら前述したように、カウンタ変数を数え上げる処理は単純に並列化することが難しく、排他制御等が必要となる。
【００７３】
ここで、数式（２）の右辺に含まれるラベル不純度 F(S[k]) は、属性データを閾値で分割することで生成される各学習サンプル群 S[k] について算出される。そのため、ラベル不純度 F(S[k]) の算出における j 番目のラベル L[j] の個数は、C[S[k],L[j]] と表すことができる。情報利得 D を算出するには、C[S[k],L[j]] を全ての k と j の組み合わせについて算出する必要がある。
【００７４】
C[S[k],L[j]] は、１）属性データを閾値で分割するという第１の基準で分けられたグループにおいて k 番目のグループ S[k] に属し、なおかつ２）ラベルという第２の基準で分けられたグループにおいて j 番目のグループ L[j] に属するという条件を満たす学習サンプルの数であるといえる。したがって、C[S[k],L[j]] を全ての k と j の組み合わせについて算出することは、１）属性データを閾値で分割するという第１の基準で分けられたグループ S[k] と、２）ラベルという第２の基準で分けられたグループ L[j] との各組み合わせに含まれる学習サンプルの数を算出することに等しい。よって、C[S[k],L[j]] を全ての k と j の組み合わせについて算出する処理は、情報処理装置２０００において、上記１）の各グループ S[k] に属する学習サンプルの数を第１行列２０で表し、上記２）の各グループ L[j] に属する学習サンプルの数を第２行列３０で表し、これらの行列の積を算出して結果行列４０を得ることで実現できる。
【００７５】
そこで情報処理装置２０００は、各学習サンプルがどの学習サンプル群 S[k] に含まれるかを表す行列を、第１行列２０として生成する。また、情報処理装置２０００は、各学習サンプルにどのラベル L[j] が付されているかを表す行列を、第２行列３０として生成する。そして情報処理装置２０００は、このようにして生成した第１行列２０と第２行列３０の積を算出する。その結果、k と j の全組み合わせについての C[s[k],L[j]] を示す結果行列４０が生成される。図１３は、C[S[k],L[j]] を示す結果行列４０の算出を例示する図である。図１３では、第１行列２０の転置行列と第２行列３０のスカラー積を算出することにより、学習サンプル群 S[k] に属しなおかつラベル L[j] が付されているデータ１０の個数をｋ行ｊ列に示す結果行列４０が生成されている。
【００７６】
このように、情報処理装置２０００によれば、決定木の学習における情報利得 D の算出で必要となるラベルの出現数の算出が、行列演算として実現される。そのため、ラベル出現数の算出を高速に並列処理できるようになる。よって、決定木の学習を高速化することができる。
【００７７】
＜＜非ゼロ因子を利用するケースについて＞＞
数式（３）や数式（４）から、本利用例では、各ラベルの出現数 C[S,L[j]] が学習サンプルの総数 N で除算される。ここで、C[S,L[j]] の算出に利用する第１行列２０と第２行列３０のいずれかにおいて、値１を値 1/N に置き換えれば、第１行列２０と第２行列３０の積として算出される結果行列４０の各要素は、各ラベルの出現数を N で除算した値となる。このように、結果行列４０の各要素を同じ値 N で除算することが予定されている場合、情報処理装置２０００は、結果行列４０の各要素を N で除算する代わりに、第１行列２０と第２行列３０のいずれかにおいて値１の代わりに値 1/N を設定するようにしてもよい。こうすることで除算を省略することができる。
【００７８】
＜＜学習サンプルやラベルの省略について＞＞
決定木を構築する過程においては、一部の属性、閾値、ラベル、又は学習サンプルを考慮から除外する場合がある。そこで、情報処理装置２０００は、一部の学習サンプル群を除外した上で第１行列２０を生成したり、一部のラベルを除外した上で第２行列３０を生成したりしてもよい。
【００７９】
＜＜複数の分割パターンの一括処理＞＞
最適な分割を決定するためには、全ての分割パターンそれぞれについて情報利得 D を算出する必要がある。或る分割パターン p における情報利得を D[p] と表記し、分割パターン p で生成される k 番目の学習サンプル群を S[p][k]と表記するとする。全ての分割パターンについて情報利得を算出するためには、分割パターン p ごとに、全ての k、j の組み合わせで C[S[p][k],L[j]] を算出する必要がある。
【００８０】
情報処理装置２０００は、複数の（例えば全ての）分割パターン p について C[S[p][k],L[j]] を算出する処理を、一回の積の演算で実現してもよい。具体的には、前述した例では１つの分割パターンについて生成していた第１行列２０を、複数の分割パターンについてまとめて生成することで実現できる。
【００８１】
図１４は、複数の分割パターンについてまとめて生成された第１行列２０を例示する図である。図１４の第１行列２０は、複数の分割パターンそれぞれで生成される学習サンプル群について、各学習サンプルがどの学習サンプルに属しているかを示す。学習サンプルは、複数の分割パターンそれぞれにおいて、いずれかの学習サンプル群に属することとなる。
【００８２】
情報処理装置２０００は、このようにして生成した第１行列２０と第２行列３０との積を算出する。こうすることで、複数の分割パターンにおける k、j の全組み合わせについて C[S[p][k],[j]] を示す１つの結果行列４０が生成される。図１５は、１つの結果行列４０で複数の分割パターンについて C[S[p][k],L[j]] が示される様子を例示する図である。
【００８３】
なお、必ずしも全ての分割パターンについて C[S[p][k],L[j]] をまとめて算出する必要はなく、２つ以上の任意の数の分割パターンについて C[S[p][k],L[j]] をまとめて算出するようにしてもよい。例えば、最適な分割パターンとはならないことが他の方法で判断できた分割パターンについては、第１行列２０に含めないようにするといったことが考えられる。
【００８４】
［実施形態２］
＜概要＞
前述したように、コンピュータプログラムでは行列を二次元配列として表すことで、行列の要素一つにつき一つの変数を割り当てることが一般的である。これに対し、実施形態２の情報処理装置２０００では、第１行列２０や第２行列３０の複数の要素につき一つの変数を割り当てる。第１行列２０や第２行列３０の各要素がとりうる値は、ゼロ因子と非ゼロ因子のいずれかである。そのため、行列の要素一つにつき１ビットを用意すれば足りる。
【００８５】
そこで本実施形態の情報処理装置２０００は、第１行列２０と第２行列３０の要素一つにつき１ビットを割り当てる。具体的には、情報処理装置２０００は、行列を整数の２次元配列として実現し、１つの整数を構成する複数のビットに、行列の異なる要素を割り当てる。以下、各ビットに行列の異なる要素が割り当てられた整数をビットベクトル整数と呼び、ビットベクトル整数の配列をビットベクトル整数配列と呼ぶ。また、整数の二次元配列の各要素に行列の要素を１つずつ割り当てたものを、整数配列と呼ぶ。
【００８６】
図１６は、ビットベクトル整数配列 V1 として実現された第１行列２０と、整数配列 I1 として実現された第１行列２０との対応関係を例示する図である。図１６において、ビットベクトル整数のサイズは T ビットである。ビットベクトル整数配列 V1 の先頭の要素 V1[0][0] の各ビットには、整数配列 I1 のI1[0][0] から I1[0][T-1] の値が格納される。また、V[i][j] の各ビットには、I1[i][T*(j-1)] から I1[i][T*j-1] の値が格納される。なお、図１６において、ビットベクトル整数配列 V1 と整数配列 I1 はいずれも、列方向にそれぞれ異なるデータ１０についての情報を示し、行方向にそれぞれ異なるグループについての情報を示している。
【００８７】
実施形態２の情報処理装置２０００は、第１行列２０と第２行列３０をそれぞれビットベクトル整数配列として実現し、ビット演算を利用してこれらの積を実現する。図１７は、ビット演算を利用して第１行列２０と第２行列３０の積を実現する方法を例示する図である。図１７に示すように、第１基準のｉ番目のグループ g1[i] に属し、なおかつ第２基準のｊ番目のグループ g2[j] に属するデータ１０の個数 C[i][j] の算出は、第１行列２０と第２行列３０との間で対応するビットベクトル整数同士で演算を行い、その結果を足し合わせることで実現できる。そして、ビットベクトル整数同士の演算は、第１行列２０のビットベクトル整数と第２行列３０のビットベクトル整数とについて、１）対応するビットごとの論理積を算出し、２）その結果として得られるビットベクトル整数において値が１のビットを数え上げるという２つの処理で実現することができる。２）の演算は、population count や bitcount などと呼ばれる。
【００８８】
ここで、１）の演算は、多くのプロセッサにおいて、単一命令で実現できる。また、２）の演算についても、これを単一命令で実現するプロセッサが存在する。よって、１）の演算や２）の演算を単一命令で実現するプロセッサを利用することにより、C[i][j] の算出を高速に実現できる。なお、２）の演算については、プロセッサにおいて単一命令で実現されていない場合であっても、分割統治法などの既知のアルゴリズムを利用することで、高速に実行することが可能である。
【００８９】
さらに、第１行列２０と第２行列３０の間で行われるビットベクトル整数同士の演算は、いずれも独立して実行可能である。そのため、ビットベクトル整数同士の演算を並列処理することにより、C[i][j] の算出を高速に実現できる。
【００９０】
＜機能構成の例＞
実施形態２の情報処理装置２０００の機能構成は、例えば実施形態の情報処理装置２０００の機能構成と同様に、図４で表される。実施形態２の情報処理装置２０００は、特に言及される点を除き、実施形態１の情報処理装置２０００と同様の機能を有する。
【００９１】
＜ハードウエア構成の例＞
実施形態２の情報処理装置２０００のハードウエア構成は、例えば実施形態１の情報処理装置２０００のハードウエア構成と同様に、図５で表される。ただし、実施形態２の情報処理装置２０００を実現するコンピュータ１０００のストレージデバイス１０８０には、実施形態２の情報処理装置２０００の各機能を実現するプログラムモジュールが格納される。
【００９２】
＜処理の流れ＞
実施形態２の情報処理装置２０００が行う処理の全体的な流れは、実施形態１の情報処理装置２０００の場合と同様に、例えば図６で表される。
【００９３】
＜第１行列２０の生成方法＞
本実施形態の第１行列生成部２０４０は、ビットベクトル整数の配列として第１行列２０を生成する。以下、ビットベクトル整数配列として実現される第１行列２０を「第１ビットベクトル整数配列 V1」と表記し、整数配列として実現される第１行列２０を「第１整数配列 I1」と表記する。V1 と I1 との対応関係は図１６に示した通りである。
【００９４】
ここで、図１６の例において、ビットベクトル整数の後方（ｔの値が大きくなる方）を上位として扱うとする。この場合、V1[i][j] の値、すなわち V1[i][j] の各ビットに対して対応する第１整数配列の値を格納することで得られる整数の値は、以下の数式（５）によって算出することができる。なお、ビットベクトル整数の前方（ｔの値が小さくなる方）を上位として扱う場合、指数を t から T-1-t に変更すればよい。
【数５】
2019151015.tif 000007
【００９５】
なお、第１基準のグループの総数が T の倍数でないこともある。この場合、例えば第１行列生成部２０４０は、第１ビットベクトル整数配列の各行の最終列についてゼロパディングを行う。
【００９６】
＜第２行列３０の生成方法＞
第２行列生成部２０６０は、第２行列３０をビットベクトル整数配列として生成する。以下、整数配列として実現した第２行列３０を第２整数配列 I2 とも表記し、ビットベクトル整数配列として実現した第２行列３０を第２ビットベクトル整数配列 V2 とも表記する。
【００９７】
第２行列３０をビットベクトル整数配列として生成する方法は、第１行列２０をビットベクトル整数配列として生成する方法と同様である。以下の数式（６）は、第２整数配列 I2 と第２ビットベクトル整数配列 V2 との対応関係を表している。
【数６】
2019151015.tif 000008
【００９８】
＜結果行列４０の生成方法＞
積算出部２０８０は、ビットベクトル整数配列として実現した第１行列２０と、ビットベクトル整数配列として実現した第２行列３０との積、すなわち第１ビットベクトル整数配列と第２ビットベクトル整数配列との積を算出することで、結果行列４０を生成する。
【００９９】
図１７を用いて説明したように、第１行列２０と第２行列３０の積の計算は、対応するビットベクトル整数同士において、１）対応するビット同士の論理積を算出することで１つの整数を算出し、２）算出された整数について１のビットを数え上げるという処理で実現される。具体的には、第１基準のｉ番目のグループに属し、なおかつ第２基準のｊ番目のグループに属するデータ１０の数 C[i][j] は、以下の数式（７）で算出される。
【数７】
2019151015.tif 000009
ここで、& は両オペランドの対応するビット間で論理積を演算し、その結果得られるビットの並びで定まる整数を出力する演算子である。また、popcount(x) は、整数 x を構成するビットについて１の総数を算出する関数である。
【０１００】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１０１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
１．  複数のデータを取得する取得手段と、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成手段と、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成手段と、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出手段と、を有する情報処理装置。
２．  前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出手段は、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、１．に記載の情報処理装置。
３．  前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出手段は、前記第１行列と前記第２行列とのスカラー積を算出する、１．に記載の情報処理装置。
４．  前記第１行列と前記第２行列の各要素は、複数のビットで表される整数であり、
前記第１行列において同一の行のビットは、その行に対応するデータが属する前記第１基準のグループに対応するビットのみが１であって他のビットが０であり、
前記第２行列において同一の行のビットは、その行に対応するデータが属する前記第２基準のグループに対応するビットのみが１であって他のビットが０であり、
前記積算出手段による前記スカラー積の算出は、前記第１行列と前記第２行列の互いに対応する要素について、同じ順位のビット同士の論理積を算出することで整数を算出し、前記算出した整数において値が１であるビットの数を積算する処理を含む、３．に記載の情報処理装置。
５．  SIMD（Single Instruction Multiple Data）型プロセッサを有し、
前記 SIMD 型プロセッサを用いて、前記第１行列の生成の並列処理、前記第２行列の生成の並列処理、及び前記スカラー積の算出の並列処理のうちの少なくとも１つを実行する、１．乃至４．いずれか一つに記載の情報処理装置。
６．  前記データは、機械学習においてモデルの学習に利用する学習サンプルである、１．乃至５．いずれか一つに記載の情報処理装置。
【０１０２】
７．  コンピュータによって実行される制御方法であって、
複数のデータを取得する取得ステップと、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成ステップと、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成ステップと、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出ステップと、を有する制御方法。
８．  前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、７．に記載の制御方法。
９．  前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列と前記第２行列とのスカラー積を算出する、７．に記載の制御方法。
１０．  前記第１行列と前記第２行列の各要素は、複数のビットで表される整数であり、
前記第１行列において同一の行のビットは、その行に対応するデータが属する前記第１基準のグループに対応するビットのみが１であって他のビットが０であり、
前記第２行列において同一の行のビットは、その行に対応するデータが属する前記第２基準のグループに対応するビットのみが１であって他のビットが０であり、
前記積算出ステップにおける前記スカラー積の算出は、前記第１行列と前記第２行列の互いに対応する要素について、同じ順位のビット同士の論理積を算出することで整数を算出し、前記算出した整数において値が１であるビットの数を積算する処理を含む、９．に記載の制御方法。
１１．  SIMD（Single Instruction Multiple Data）型プロセッサを有し、
前記 SIMD 型プロセッサを用いて、前記第１行列の生成の並列処理、前記第２行列の生成の並列処理、及び前記スカラー積の算出の並列処理のうちの少なくとも１つを実行する、７．乃至１０．いずれか一つに記載の制御方法。
１２．  前記データは、機械学習においてモデルの学習に利用する学習サンプルである、７．乃至１１．いずれか一つに記載の制御方法。
【０１０３】
１３．  ７．乃至１２．いずれか一つに記載の制御方法の各ステップをコンピュータに実行させるプログラム。
【０１０４】
この出願は、２０１８年１月３１日に出願された日本出願特願２０１８−０１５５９８号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2019151015.tif 000010
【図２】
2019151015.tif 000011
【図３】
2019151015.tif 000012
【図４】
2019151015.tif 000013
【図５】
2019151015.tif 000014
【図６】
2019151015.tif 000015
【図７】
2019151015.tif 000016
【図８】
2019151015.tif 000017
【図９】
2019151015.tif 000018
【図１０】
2019151015.tif 000019
【図１１】
2019151015.tif 000020
【図１２】
2019151015.tif 000021
【図１３】
2019151015.tif 000022
【図１４】
2019151015.tif 000023
【図１５】
2019151015.tif 000024
【図１６】
2019151015.tif 000025
【図１７】
2019151015.tif 000026
【手続補正書】
【提出日】令和2年7月10日(2020.7.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のデータを取得する取得手段と、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成手段と、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成手段と、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出手段と、を有する情報処理装置。
【請求項２】
前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出手段は、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、請求項１に記載の情報処理装置。
【請求項３】
前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出手段は、前記第１行列と前記第２行列とのスカラー積を算出する、請求項１に記載の情報処理装置。
【請求項４】
前記第１行列と前記第２行列の各要素は、複数のビットで表される整数であり、
前記第１行列において同一の行のビットは、その行に対応するデータが属する前記第１基準のグループに対応するビットのみが１であって他のビットが０であり、
前記第２行列において同一の行のビットは、その行に対応するデータが属する前記第２基準のグループに対応するビットのみが１であって他のビットが０であり、
前記積算出手段による前記スカラー積の算出は、前記第１行列と前記第２行列の互いに対応する要素について、同じ順位のビット同士の論理積を算出することで整数を算出し、前記算出した整数において値が１であるビットの数を積算する処理を含む、請求項３に記載の情報処理装置。
【請求項５】
SIMD（Single Instruction Multiple Data）型プロセッサを有し、
前記 SIMD 型プロセッサを用いて、前記第１行列の生成の並列処理、前記第２行列の生成の並列処理、及び前記スカラー積の算出の並列処理のうちの少なくとも１つを実行する、請求項１乃至４いずれか一項に記載の情報処理装置。
【請求項６】
前記データは、機械学習においてモデルの学習に利用する学習サンプルである、請求項１乃至５いずれか一項に記載の情報処理装置。
【請求項７】
コンピュータによって実行される制御方法であって、
複数のデータを取得する取得ステップと、
各前記データが第１基準の分類においていずれのグループに属するかを表す第１行列を生成する第１行列生成ステップと、
各前記データが第２基準の分類においていずれのグループに属するかを表す第２行列を生成する第２行列生成ステップと、
前記第１行列と前記第２行列に関するスカラー積を計算することで、前記第１基準のグループと前記第２基準のグループとの組み合わせごとに、その組み合わせに属する前記データの個数を算出する積算出ステップと、を有する制御方法。
【請求項８】
前記第１行列の各列は、それぞれ異なる１つの前記第１基準のグループに対応しており、
前記第１行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる１つの前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる１つの前記データについて、前記データが属する前記第２基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列の転置行列と前記第２行列とのスカラー積を算出する、請求項７に記載の制御方法。
【請求項９】
前記第１行列の各行は、それぞれ異なる前記第１基準のグループに対応しており、
前記第１行列の各列は、それぞれ異なる前記データについて、前記データが属する前記第１基準のグループに対応する列のみに非ゼロ因子を示して他の列にゼロ因子を示し、
前記第２行列の各列は、それぞれ異なる前記第２基準のグループに対応しており、
前記第２行列の各行は、それぞれ異なる前記データについて、前記データが属する前記第２基準のグループに対応する行のみに非ゼロ因子を示して他の行にゼロ因子を示し、
前記積算出ステップにおいて、前記第１行列と前記第２行列とのスカラー積を算出する、請求項７に記載の制御方法。
【請求項１０】
前記データは、機械学習においてモデルの学習に利用する学習サンプルである、請求項７乃至９いずれか一項に記載の制御方法。
【国際調査報告】
2019151015.tif 000027
2019151015.tif 000028