(57)【要約】【課題】行列の各行又は各列を連長圧縮する際の圧縮率を向上させる。【解決手段】行列圧縮装置２０００は、対象行列取得部２０２０、置換部２０４０、及び圧縮部２０６０を有する。対象行列取得部２０２０は、複数の要素を有する対象行列を取得する。置換部２０４０は、対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又は列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの代表値に置き換える。圧縮部２０６０は、置換部２０４０によって変換された対象行列を行方向又は列方向について連長圧縮する。【選択図】図１
2015118455.tif 000002
【特許請求の範囲】
【請求項１】
複数の要素を有する対象行列を取得する対象行列取得手段と、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換手段と、
前記置換手段によって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮手段と、
を有する行列圧縮装置。
【請求項２】
前記置換手段は、前記対象行列の行又は列ごとにその行又はその列に含まれる要素を複数のグループに分け、前記グループごとにそのグループに含まれる要素に基づいて前記代表値を算出し、各要素をその要素が属する前記グループについて算出した前記代表値で置き換える請求項１に記載の行列圧縮装置。
【請求項３】
前記置換手段は、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素の値域を所定幅で分割した部分値域を算出し、各部分値域を前記グループとする請求項２に記載の行列圧縮装置。
【請求項４】
前記圧縮手段が対象行列を連長圧縮する前に、前記圧縮手段が行方向に連長圧縮を行う場合は前記対象行列の列をソートし、前記圧縮手段が列方向に連長圧縮を行う場合は前記対象行列の行をソートするソート手段を有する請求項１乃至３いずれか一項に記載の行列圧縮装置。
【請求項５】
前記ソート手段は、前記対象行列の行又は列を１つの単語とみなした場合に各行又は各列が辞書順に並ぶように、前記対象行列の行又は列をソートする請求項４に記載の行列圧縮装置。
【請求項６】
前記ソート手段は、
前記圧縮手段が前記対象行列を行方向について連長圧縮する場合、前記対象行列の行ごとに優先度を算出し、各列の比較を、優先度が高い行に位置する要素から順に行うことで、列をソートし、
前記圧縮手段が前記対象行列を列方向に連長圧縮する場合、前記対象行列の列ごとに優先度を算出し、各行の比較を、優先度が高い列に位置する要素から順に行うことで、行をソートする、
請求項４に記載の行列圧縮装置。
【請求項７】
前記圧縮手段が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を取得する圧縮方向取得手段を有し、
前記置換手段は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮手段は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する請求項１乃至６いずれか一項に記載の行列圧縮装置。
【請求項８】
前記圧縮手段が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を決定する圧縮方向決定手段を有し、
前記置換手段は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮手段は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する請求項１乃至６いずれか一項に記載の行列圧縮装置。
【請求項９】
コンピュータによって実行される制御方法であって、
複数の要素を有する対象行列を取得する対象行列取得ステップと、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換ステップと、
前記置換ステップによって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮ステップと、
を有する制御方法。
【請求項１０】
コンピュータに、
複数の要素を有する対象行列を取得する対象行列取得機能と、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換機能と、
前記置換機能によって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮機能と、
を持たせるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列圧縮装置、制御方法、及びプログラムに関する。
【背景技術】
【０００２】
行列計算は、数値計算、データマイニング、機械学習をはじめとする種々の分野で利用される。行列計算の対象となる行列のサイズは、計算資源の発展に伴い大きくなってきている。このような大きな行列は、コンピュータの記憶領域を圧迫する。また、このような大きな行列を対象として行う行列計算は、長い時間を要する。そこで、大きな行列を扱う際に、行列を格納するために必要な記憶容量を削減すること、及び行列計算にかかる時間を削減することが求められている。
【０００３】
これに対し、行列を圧縮することで行列のサイズを小さくする技術が提案されている。行列のサイズを小さくすることで、行列計算の速度向上や、行列を記憶するために必要な記憶容量の削減といった効果が得られる。この技術の一例は、例えば非特許文献１に記載されている。
【０００４】
行列を圧縮する方法の１つとして、連長圧縮が挙げられる。連長圧縮は、データ列を「データの値、その値が連続する回数」の組み合わせを用いて表現することで、データ列のサイズを小さくする方法である。例えば、「ＡＡＡＢＢＣＣＣＣ」というデータ列があるとする。ここで、各アルファベットは１つのデータを表しているとする。このデータ列を連長圧縮すると、「Ａ３Ｂ２Ｃ４」というデータ列となる。行列の各行又は各列を連長圧縮することで、行列のサイズを小さくすることができる。
【０００５】
さらに、特許文献１は、行列の各列を連長圧縮する際に、連長圧縮をする前に行列の行をソートすることで連長圧縮の効率を高める方法を開示している。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特表２００９−５１７７８２号公報
【非特許文献】
【０００７】
【非特許文献１】S. Rendle、「Scaling factorization machines to relational data」、Proceedings of Very Large Data Bases Endowment、Volume 6、Issue 5、pp.337-348、２０１３年３月
【非特許文献２】J. MacQueen、「Some methods for classification and analysis of multivariate observations」、Proceedings of Fifth Berkeley Symposium on Mathematical Statistics and Probability、１９６７年
【非特許文献３】J. H. Friedman, T. Hastie, and R. Tibshirani、「Regularization paths for generalized linear models via coordinate descent」、Journal of Statistical Software、Volume 33、Issue 1、pp.1-22、２０１０年１月
【非特許文献４】L. Bottou and O. Bousquet、「The tradeoffs of large scale learning」、Advances in Neural Information Processing Systems、２００８年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
データ列を連長圧縮する場合、データ列の中で同一の値が連続していないと圧縮率が低い。特許文献１は行列の行をソートしてから各列を連長圧縮することで連長圧縮の圧縮率を高めているものの、各列が同一の要素をほとんど有していない場合などにおいては効果が小さい。
【０００９】
本発明は、以上の課題に鑑みてなされたものである。本発明の目的は、行列の各行又は各列を連長圧縮する際の圧縮率を向上させる技術を提供することである。
【課題を解決するための手段】
【００１０】
本発明が提供する行列圧縮装置は、複数の要素を有する対象行列を取得する対象行列取得手段と、前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換手段と、前記置換手段によって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮手段と、を有する。
【００１１】
本発明が提供する制御方法は、コンピュータによって実行される。当該制御方法は、複数の要素を有する対象行列を取得する対象行列取得ステップと、前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換ステップと、前記置換ステップによって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮ステップと、を有する。
【００１２】
本発明が提供するプログラムは、コンピュータに、本発明が提供する行列圧縮装置の各機能構成部によって実現される機能を持たせる。
【発明の効果】
【００１３】
本発明によれば、行列の各行又は各列を連長圧縮する際の圧縮率を向上させる技術が提供される。
【図面の簡単な説明】
【００１４】
【図１】実施形態１に係る行列圧縮装置を例示するブロック図である。
【図２】対象行列の行に含まれる要素を代表値で置換する例を示す図である。
【図３】行列圧縮装置のハードウエア構成を例示するブロック図である。
【図４】実施形態１の行列圧縮装置において実行される処理の流れを例示するフローチャートである。
【図５】グルーピング方法１を用いたグループ分けを例示する図である。
【図６】図５に示した行 i について、同一の部分値域に含まれており、かつ隣接している要素のみを同一のグループに分ける処理を例示する図である。
【図７】実施形態３に係る行列圧縮装置を例示するブロック図である。
【図８】ソート方法１において２つの行を比較する処理を例示する図である。
【図９】ソート方法１の具体例を示す図である。
【図１０】ソート方法２において２つの行を比較する処理を例示する図である。
【図１１】ソート方法２の具体例を示す図である。
【図１２】実施形態３の行列圧縮装置において実行される処理の流れを例示するフローチャートである。
【図１３】実施形態４に係る行列圧縮装置を例示するブロック図である。
【図１４】圧縮方向格納部と通信可能に接続されている行列圧縮装置を例示するブロック図である。
【図１５】圧縮方向格納部に格納されている情報をテーブル形式で例示する図である。
【図１６】実施形態４の行列圧縮装置において実行される処理の流れを例示するフローチャートである。
【図１７】実施形態５に係る行列圧縮装置を例示するブロック図である。
【図１８】実施形態５の行列圧縮装置において実行される処理の流れを例示するフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００１６】
［実施形態１］
図１は、実施形態１に係る行列圧縮装置２０００を例示するブロック図である。図１において、矢印は情報の流れを表している。さらに、図１において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００１７】
行列圧縮装置２０００は、対象行列取得部２０２０、置換部２０４０、及び圧縮部２０６０を有する。以下、それぞれについて説明する。
【００１８】
＜対象行列取得部２０２０＞
対象行列取得部２０２０は、複数の要素を有する対象行列を取得する。ここで、対象行列が示す要素は、数値であってもよいし、文字であってもよい。
【００１９】
対象行列取得部２０２０が対象行列を取得する方法は様々である。例えば対象行列取得部２０２０は、外部の装置から入力される対象行列を取得する。その他にも例えば、対象行列取得部２０２０は、手動で入力される対象行列を取得する。さらに対象行列取得部２０２０は、外部の装置にアクセスして、対象行列を取得してもよい。
【００２０】
＜置換部２０４０＞
置換部２０４０は、対象行列の行又は列ごとに代表値を算出し、その代表値を用いて要素の置き換えを行う。対象行列が行について代表値を算出する場合、置換部２０４０は、各行に含まれる要素を用いて、その行に含まれる要素の数より少ない個数の代表値を算出する。そして、置換部２０４０は、各行に含まれる各要素の値を、その行について算出した代表値のいずれかで置き換える。一方、対象行列が列について代表値を算出する場合、置換部２０４０は、各列に含まれる要素を用いて、その列に含まれる要素の数より少ない個数の代表値を算出する。そして、置換部２０４０は、各列に含まれる各要素の値を、その列について算出した代表値のいずれかで置き換える。
【００２１】
＜圧縮部２０６０＞
圧縮部２０６０は、置換部２０４０によって置換が行われた対象行列を行方向又は列方向について連長圧縮を行う。置換部２０４０が対象行列の各行について代表値を算出する場合、圧縮部２０６０は各行を連長圧縮する。一方、置換部２０４０が対象行列の各列について代表値を算出する場合、圧縮部２０６０は各列を連長圧縮する。
【００２２】
圧縮部２０６０が連長圧縮を行う方向（以下、圧縮方向）は、予め固定されていてもよい。また、圧縮部２０６０は、圧縮方向を取得したり決定したりする機能を有していてもよい。
【００２３】
図２は、対象行列の行に含まれる要素を代表値で置換する例を示す図である。図２の対象行列において、置換前の行 i は「1.9, 2.0, 2.1, 0.9, 1.1」という行である。このままでは、行 i には連長圧縮できる箇所がないため、圧縮部２０６０を動作させても行 i のサイズは小さくならない。そこで、例えば置換部２０４０は、行 i の代表値として、2.0 と 1.0 を算出する。そして、置換部２０４０は、行 i の各要素を上記２つの代表値のいずれかで置き換えることで、例えば行 i を「2.0, 2.0, 2.0, 1.0, 1.0」に変換する。これにより、圧縮部２０６０は、行 i を「(2.0, 3), (1.0, 2)」に連長圧縮することができ、行 i の要素数が削減される。
【００２４】
＜ハードウエア構成＞
行列圧縮装置２０００が有する各機能構成部は、例えば、個々に又は複数組み合わせられた状態で、少なくとも１つのハードウエア構成要素として実現される。その他にも例えば、各機能構成部は、少なくとも１つのソフトウエア構成要素として実現される。その他にも例えば、各機能構成部は、ハードウエア構成要素とソフトウエア構成要素の組み合わせにより実現される。
【００２５】
図３は、行列圧縮装置２０００のハードウエア構成を例示するブロック図である。図３において、行列圧縮装置２０００は、バス１０２０、プロセッサ１０４０、メモリ１０６０、及びストレージ１０８０を有する。
【００２６】
バス１０２０は、プロセッサ１０４０、メモリ１０６０、及びストレージ１０８０が、相互にデータを送受信するためのデータ伝送路である。プロセッサ１０４０は、例えば CPU (Central Processing Unit) や GPU (Graphics Processing Unit) などの演算処理装置である。メモリ１０６０は、例えば RAM (Random Access Memory) や ROM (Read Only Memory) などのメモリである。ストレージ１０８０は、例えばハードディスク、SSD (Solid State Drive)、又はメモリカードなどの記憶装置である。また、ストレージ１０８０は、RAM や ROM 等のメモリであってもよい。
【００２７】
対象行列取得モジュール１２２０は、行列圧縮装置２０００に、対象行列取得部２０２０の機能を持たせるためのプログラムである。プロセッサ１０４０は、対象行列取得モジュール１２２０を実行することで、対象行列取得部２０２０の機能を実現する。
【００２８】
置換モジュール１２４０は、行列圧縮装置２０００に、置換部２０４０の機能を持たせるためのプログラムである。プロセッサ１０４０は、置換モジュール１２４０を実行することで、置換部２０４０の機能を実現する。
【００２９】
圧縮モジュール１２６０は、行列圧縮装置２０００に、圧縮部２０６０の機能を持たせるためのプログラムである。プロセッサ１０４０は、圧縮モジュール１２６０を実行することで、圧縮部２０６０の機能を実現する。
【００３０】
例えばプロセッサ１０４０は、上記各モジュールをメモリ１０６０上に読み出して実行する。ただし、プロセッサ１０４０は、上記各モジュールを、メモリ１０６０上に読み出さずに実行してもよい。
【００３１】
ストレージ１０８０は、上記各モジュールを格納する。
【００３２】
行列圧縮装置２０００のハードウエア構成は、図３に示した構成に限定されない。例えば、各モジュールはメモリ１０６０に格納されてもよい。この場合、行列圧縮装置２０００は、ストレージ１０８０を備えていなくてもよい。
【００３３】
＜処理の流れ＞
図４は、実施形態１の行列圧縮装置２０００において実行される処理の流れを例示するフローチャートである。図４は、圧縮部２０６０が行方向について連長圧縮を行う場合の処理の流れを示している。
【００３４】
ステップＳ１０２において、対象行列取得部２０２０は対象行列を取得する。ステップＳ１０４からＳ１１０は、対象行列の各行について実行されるループ処理Ａである。ステップＳ１０４において、置換部２０４０は、i < N が満たされているか否かを判定する。ここで、i は行番号であり、N は対象行列の行数である。i の初期値は 0 である。i < N が満たされている場合、図４の処理はステップＳ１０６に進む。一方、i < N が満たされていない場合、図４の処理はステップＳ１１２に進む。
【００３５】
ステップＳ１０６において、置換部２０４０は、i 番目の行に含まれる要素を用いて、i 番目の行の代表値を算出する。ここで算出される代表値の個数は、i 番目の行に含まれる要素の数より少ない。ステップＳ１０８において、置換部２０４０は、i 番目の行に含まれる各要素を、ステップＳ１０６で算出した代表値のいずれかで置き換える。ステップＳ１１０はループ処理Ａの終端である。ステップＳ１１０において、図４の処理は図１１４に進む。なお、ステップＳ１１０からステップＳ１０４に進んだ場合、ステップＳ１０４において置換部２０４０は、i に 1 を加算し、その後に、i < N が満たされているか否かの判定を行う。
【００３６】
ステップＳ１１２において、圧縮部２０６０は、各行を連長圧縮する。
【００３７】
なお、図４に示す処理の流れは例示であり、同様の結果が得られる範囲で処理の流れを変更してもよい。例えば、ステップＳ１１２を実行する代わりに、ステップＳ１０８と１１０の間において、行 i の各要素を代表値のいずれかで置き換える処理を行うようにしてもよい。
【００３８】
圧縮部２０６０が列方向について連長圧縮を行う場合の処理は、図４において「行」を「列」に置き換えることで実現できる。
【００３９】
＜作用・効果＞
本願発明によれば、対象行列の各行又は各列の要素が、その行又はその列の要素の数より少ない個数の代表値のいずれかによって置換される。したがって、対象行列の各行又は各列において、同一の値の要素が連続する確率が高くなる。よって、対象行列の行又は列を連長圧縮する際の圧縮率が向上する。
【００４０】
行列計算によっては、対象行列の要素をその要素と近い値に置き換えても、計算結果に与える影響が小さかったり、計算結果に与える影響がなかったりする。例えば、対象行列の要素は小数点以下１桁まで表されている場合でも、対象行列を利用する計算によっては、小数点以下１桁までの精度は求められておらず、要素を整数で近似してもよい場合などがある。また、行列計算を利用する状況によっては、計算の精度が多少下がることは問題ないものの、計算時間が長くなることや使用する記憶領域が多いことは許容できない場合もある。行列圧縮装置２０００は、これらの場合に特に好適に用いることができる。
【００４１】
[実施形態２]
実施形態２に係る行列圧縮装置２０００は、実施形態１に係る行列圧縮装置２０００と同様に、図１で表される。
【００４２】
実施形態２の置換部２０４０は、対象行列の行又は列ごとに、その行又はその列に含まれる要素を複数のグループに分ける。そして、置換部２０４０は、グループごとに、そのグループに含まれる要素に基づいて代表値を算出する。さらに、置換部２０４０は、各要素をその要素が属するグループについて算出した代表値で置き換える。対象行列が行について代表値を算出する場合、置換部２０４０は、行ごとに、その行に含まれる要素を複数のグループに分ける。一方、対象行列が列について代表値を算出する場合、置換部２０４０は、列ごとに、その列に含まれる要素を複数のグループに分ける。
【００４３】
例えば置換部２０４０は、グループに含まれる要素の統計値を、そのグループの代表値として算出する。また例えば、置換部２０４０は、グループに含まれる要素の中から１つを選択し、その要素の値を代表値としてもよい。この場合、この１つの要素は、グループに含まれる要素の中からランダムに選択されてもよいし、行番号又は列番号が最も小さい又は大きいなどの条件で選択されてもよい。
【００４４】
＜グルーピング方法１＞
例えば置換部２０４０は、行又は列に含まれる要素の値域を所定幅で分割した値域（以下、部分値域）を１つのグループとする。例えば置換部２０４０は、ある行に含まれる要素をグループに分ける場合、その行に含まれる要素の値域を算出する。そして、置換部２０４０は、その値域を所定幅で分割することで、その行を複数の部分値域に分ける。そして、各部分値域を１つのグループとする。なお、上記所定幅は、全ての行で共通であってもよいし、行ごとに定められていてもよい。また、置換部２０４０は、行に含まれる値域を所定数のグループに分割してもよい。この場合、この所定数は全ての行で共通であってもよいし、行ごとに定められていてもよい。
【００４５】
なお、置換部２０４０が算出する値域は、行又は列に含まれる要素の値域を含んでいればよく、行又は列に含まれる要素の値域より広い範囲であってもよい。例えば、ある行に「51, 55, 59」という３つの要素が含まれているとする。この場合、置換部２０４０は、この行の値域を [51, 59] と算出してもよいし、例えば [50, 60] などのように広い範囲として算出してもよい。
【００４６】
上述した方法は、置換部２０４０が各列をグループに分ける場合についても同様である。
【００４７】
具体例を用いて、置換部２０４０の動作を説明する。図５は、グルーピング方法１を用いてグループ分けを行う処理を概念的に示す図である。図５に示す例において、置換部２０４０は、行 i の値域を分割するための基準値β及び所定幅σを取得する。そして、置換部２０４０は、行の値域を [β, β+δ)、[β+σ, β+2δ)、[β+2σ, β+3δ)、・・・という部分値域に分割する。
【００４８】
置換部２０４０が、「62.5, 63.0, 64.5, 72.5, 64.7」という行 i について要素の置換を行うとする。ここで、β=60.0、σ＝5.0 であるとする。まず、置換部２０４０は、行 i の要素の値域として、[60.0, 70.0] を算出する。そして、置換部２０４０は、この値域を、[60.0, 65.0)、[65.0, 70.0), [70.0, 75.0] という３つの部分値域に分ける。置換部２０４０は、同一の部分値域に含まれる要素を同一のグループに分ける。ここで、[60.0, 65.0) に含まれる要素のグループを G1、[65.0, 70.0) に含まれる要素のグループを G2、[70.0, 75.0] に含まれる要素のグループを G3 と表記する。
【００４９】
そして、置換部２０４０は、各グループに含まれる要素の平均値を、そのグループの代表値として算出する。例えば、グループ G1 に含まれる要素は、62.5, 63.0, 64.5, 64.7の４つである。そこで、置換部２０４０は、グループ G1 の代表値として、63.7 を算出する。また、グループ G2 には要素が含まれないため、置換部２０４０は、グループ G2 の代表値を算出しない。さらに、グループ G3 に含まれる要素は 72.5 のみであるため、置換部２０４０は、グループ G3 の代表値を 72.5 とする。以上により、置換部２０４０は、行 i を、「63.7, 63.7, 63.7, 72.5, 63.7」に置換する。
【００５０】
なお、置換部２０４０は、同一の部分値域に含まれており、かつ隣接している要素のみを、同一のグループに含めるようにしてもよい。図６は、図５に示した行 i について、同一の部分値域に含まれており、かつ隣接している要素のみを同一のグループに分ける処理を概念的に示す図である。例えば置換部２０４０は、行 i の先頭から順に要素をグループに分けていく。１番目の要素である 62.5 は、[60.0, 65.0) に含まれる。そこで置換部２０４０は、２番目以降の要素が [60.0, 65.0) に含まれるかを順次判定していき、[60.0, 65.0) に含まれない要素が見つかるまで、各要素をグループ G1 の要素としていく。この例では、４番目の要素である 72.5 が [60.0, 65.0) に含まれないため、１番目から３番目までの要素をグループ G1 の要素とする。
【００５１】
ここで、５番目の要素である 64.7 は、１番目から３番目の要素と同様に [60.0, 65.0) に含まれている。しかし、上述のように、同一の部分値域に属し、かつ隣接している要素のみを同一のグループに分けるため、５番目の要素はグループ G1 の要素にはならない。その結果、図７では、行 i の要素をグループに分けた結果が、図５の場合と異なる。そのため、置換部２０４０が各グループについて算出する代表値も異なる。その結果、図７において置換部２０４０が行i の各要素を代表値で置換した結果は、図５の場合と異なる。
【００５２】
行又は列に含まれる要素の値域を所定幅で分割する方法を用いる場合、適切な所定幅を設定することで、代表値が元の要素の値から乖離する程度を意図した範囲に収めることが容易となる。例えば所定幅を 5 とし、代表値としてグループに含まれる要素の統計値を利用する場合、代表値と元の要素の値との差を 5 以下にすることができる。
【００５３】
なお、隣接している要素のみを同一のグループに分けるようにした方が、代表値と元の要素の値との乖離は小さくなる。また、連長圧縮は隣接している要素について行われるため、隣接している要素のみを同一のグループに分けるようにしても、連長圧縮の圧縮率には影響しない。一方、隣接しているか否かに関わらず同じ部分値域に属している要素を同一のグループに分ける方法の方には、グループ分けの処理が単純であるため、グループ分けにかかる時間が比較的短いという利点がある。
【００５４】
＜グルーピング方法２＞
置換部２０４０が各行又は各列の要素をグループに分ける別の方法として、k-means クラスタリングを利用する方法がある。k-means クラスタリングを行うと、k 個のクラスタが生成される。置換部２０４０は、生成された各クラスタを１つのグループとする。ここで、k-means クラスタリングは既知の技術であるため、k-means クラスタリングに関する詳細な説明は省略する。例えば k-means クラスタリングの具体的な方法は、非特許文献２に記載されている。
【００５５】
ある行に含まれる要素を複数のグループに分ける場合、置換部２０４０は、その行に含まれる要素を k-means クラスタリングでクラスタリングする。同様に、ある列に含まれる要素を複数のグループに分ける場合、置換部２０４０は、その列に含まれる要素を k-means クラスタリングでクラスタリングする。
【００５６】
置換部２０４０がクラスタ数を決定する方法は様々である。例えば置換部２０４０は、クラスタ数を取得し、取得したクラスタ数を用いる。置換部２０４０がクラスタ数を取得する方法は様々である。例えば置換部２０４０は、外部の装置から入力されるクラスタ数を取得する。その他にも例えば、置換部２０４０は、手動で入力されるクラスタ数を取得する。さらに置換部２０４０は、外部の装置にアクセスして、クラスタ数を取得してもよい。
【００５７】
その他にも例えば、置換部２０４０は、対象行列の行又は列に含まれる要素の数に基づいて、クラスタ数を決定してもよい。例えば置換部２０４０は、対象行列の行に含まれる要素の数の所定割合の値を計算し、この値をクラスタ数とする。例えば、所定割合を 1/3 とし、ある行に含まれる要素の数が 9 個であるとする。この場合、置換部２０４０は、クラスタ数を 9 × 1/3 = 3 とする。なお、置換部２０４０がこの所定割合を取得する方法は、上述したクラスタ数を取得する方法と同様である。
【００５８】
なお、クラスタ数は全ての行又は列に共通であってもよいし、行又は列ごとに異なっていてもよい。
【００５９】
k-means クラスタリングを用いて行又は列の要素をグループに分ける場合、行列に含まれる要素の値を考慮せずにグループの数を決定できるという利点がある。これにより、例えばグループの数を、圧縮された対象行列を利用する計算の計算時間をどの程度削減したいか又は圧縮された対象行列のサイズをどの程度削減したいかという連長圧縮の圧縮率向上に対する要望と、圧縮された対象行列を利用する計算に求められる精度とのトレードオフを考慮した上で決定することができる。
【００６０】
[実施形態３]
図７は、実施形態３に係る行列圧縮装置２０００を例示するブロック図である。図７において、矢印は情報の流れを表している。さらに、図７において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００６１】
実施形態３の行列圧縮装置２０００は、ソート部２０７０をさらに有する。ソート部２０７０は、圧縮部２０６０が対象行列を連長圧縮する前に、対象行列の行又は列をソートする。具体的には、置換部２０４０は、圧縮部２０６０が行方向について連長圧縮を行う場合は対象行列の列をソートする。一方、置換部２０４０は、圧縮部２０６０が列方向について連長圧縮を行う場合は対象行列の行をソートする。なお、ソート部２０７０は、置換部２０４０が動作する前に動作してもよいし、置換部２０４０が動作した後に動作してもよい。
【００６２】
実施形態３の行列圧縮装置２０００によれば、対象行列の行又は列をソートするため、列方向又は行方向において同一の要素が連続する確率が高くなる。そのため、連長圧縮の圧縮率が確率的に向上する。
【００６３】
なお、行列を利用した計算においては、行又は列の順序を入れ替えても、計算結果に影響を与えない場合がある。例えば機械学習において教師データの集合を行列で表しており、かつ各行が独立した教師データである場合、行の順序を入れ替えて学習を実行しても学習の結果に影響を与えないことが多い。実施形態３の行列圧縮装置２０００は、このように行列の行又は列の順序を入れ替えてもその行列を利用した計算の結果に影響を与えない場合に利用されることが好適である。
【００６４】
＜ソート方法１＞
例えばソート部２０７０は、対象行列の行又は列を１つの単語とみなした場合に行又は列が辞書順に並ぶように、対象行列の行又は列をソートする。この方法を、ソート方法１と表記する。対象行列の行をソートする場合、ソート部２０７０は、各行を１つの単語とみなした場合に行が辞書順に並ぶように、行をソートする。一方、対象行列の列をソートする場合、ソート部２０７０は、各列を１つの単語とみなした場合に列が辞書順に並ぶように、列をソートする。このソート方法は、「辞書式ソート」などの呼び方で知られている。
【００６５】
図８は、ソート方法１において２つの行を比較する処理を例示する図である。図８における N は、対象行列の列数を表している。このように、ソート方法１では、２つの行を先頭の要素から順に比較していく。
【００６６】
図９は、ソート方法１を利用する場合の具体例を示す図である。図９において、圧縮方向は列方向である。また、対象行列 a-1 は、置換部２０４０によって各列の要素を代表値に置き換えたものである。
【００６７】
対象行列 a-2 は、圧縮部２０６０が対象行列 a-1 を連長圧縮することで得られる行列である。一方、対象行列 a-4 は、圧縮部２０６０が対象行列 a-3 を連長圧縮することで得られる行列である。対象行列 a-3 は、ソート部２０７０がソート方法１で対象行列 a-1 をソートしたものである。対象行列 a-2 と対象行列 a-4 を比較すると、点線で囲った部分において連長圧縮の圧縮率が向上している。
【００６８】
このように、ソート部２０７０がソート方法１で対象行列をソートしてから圧縮部２０６０が連長圧縮を行うことで、連長圧縮の圧縮率が向上する。
【００６９】
＜ソート方法２＞
その他にも例えば、ソート部２０７０は、以下に示す方法で対象行列の行又は列をソートしてもよい。以下に示す方法を、ソート方法２と表記する。まず、ソート部２０７０は、対象行列の行又は列ごとに優先度を算出する。ここで、ソート部２０７０は、行をソートする場合は各列の優先度を算出し、列をソートする場合は各行の優先度を算出する。そして、ソート部２０７０は、行をソートする場合、各行の比較を、優先度が高い列に位置する要素から順に行うことで、行をソートする。また、ソート部２０７０は、列をソートする場合、各列の比較を、優先度が高い行に位置する要素から順に行うことで、列をソートする。
【００７０】
図１０は、ソート方法２において２つの行を比較する処理を例示する図である。図１０における N は、図８の場合と同様に、対象行列の列数を表す。また、prioritized_column_index は、列番号を列の優先度順に並べた配列である。そのため、j には優先度順に列番号が代入される。よって、行の大小比較をその行における小さい列番号の要素（単語の先頭）から順に比較することで行うソート方法１と異なり、ソート方法２における行の大小比較は、その行における優先度が高い列番号の要素から順に行われる。
【００７１】
ソート部２０７０は、値が同一である要素を多く含む行又は列ほど優先度を高くすることが好ましい。例えばソート部２０７０は、対象行列の各行又は各列の濃度（Cardinality）を用いて、各行又は各列の優先度を算出する。ここで、行又は列の濃度は、その行又は列に含まれる要素の集合から重複する要素を排除した集合における要素の数で表される。例えば、ある行が「1, 2, 2, 3, 3, 4」である場合、この行の要素から重複を排除した集合は「1, 2, 3, 4」である。よって、この行の濃度は４である。
【００７２】
同一の要素数からなる行又は列を比較した場合、濃度が小さい行又は列の方が、重複している要素の数が多い。そこで、例えばソート部２０７０は、その行又は列の濃度の逆数（１／濃度）を算出し、その値をその行又は列の優先度とする。こうすると、行又は列の優先度が高いことは、その行又は列が重複している要素を多く含むことを意味するようになる。
【００７３】
図１１は、ソート方法１を利用して行をソートしてから連長圧縮を行う場合と、ソート方法２を利用して行をソートしてから連長圧縮を行う場合とを具体的に比較する図である。図１１において、圧縮方向は列方向である。また、対象行列 b-1 は、置換部２０４０によって各列の要素を代表値に置き換えたものである。
【００７４】
対象行列 b-3 は、圧縮部２０６０が対象行列 b-2 を連長圧縮することで得られる行列である。ここで、対象行列 b-2 は、ソート部２０７０がソート方法１で対象行列 b-1 をソートしたものである。対象行列 b-2 において列方向について連長圧縮できる箇所はないため、対象行列 b-2 と b-3 の内容は同じである。
【００７５】
一方、対象行列 b-5 は、圧縮部２０６０が対象行列 b-4 を連長圧縮することで得られる行列である。対象行列 b-4 は、ソート部２０７０がソート方法２で対象行列 b-1 をソートしたものである。ここで、１／濃度を優先度の値としている。そのため、対象行列 b-4 において列を優先度が高い順に並べると、列３、列２、列１の順になる。よって、ソート部２０７０は、各行の比較を、列３に位置する要素、列２に位置する要素、列１に位置する要素という順で行う。これにより、列３において重複する要素が、優先的に揃う結果となる。
【００７６】
対象行列 b-3 と対象行列 b-5 を比較すると、対象行列 b-5 の方が連長圧縮の圧縮率が高い。このように、ソート方法２で対象行列をソートした方が、ソート方法１で対象行列をソートするよりも連長圧縮の圧縮率が向上する場合がある。
【００７７】
ソート方法２に示したソート方法は、ソート方法１で示した辞書式ソートと比較して、連長圧縮の圧縮率が高くなる確率が高いという利点がある。一方、辞書式ソートを利用するソート方法１には、優先度の算出を行う必要がないため、ソートに要する時間が短いという利点がある。
【００７８】
＜処理の流れ＞
図１２は、実施形態４の行列圧縮装置２０００において実行される処理の流れを例示するフローチャートである。図１２で例示されているのは、対象行列を行について連長圧縮する場合の処理の流れである。なお、図１２のステップＳ１０２とステップＳ１０４は、図４のステップＳ１０２及びＳ１０４と同様の処理である。
【００７９】
ステップＳ１０２が実行された後、ステップＳ２０２において、ソート部２０７０は対象行列の列をソートする。そして、ステップＳ２０４において、置換部２０４０は、各行について代表値を算出し、各行の要素をその行について算出した代表値のいずれかで置き換える。ここで、ステップＳ２０４の処理は、図４のステップＳ１０４からステップＳ１１０で行われる処理と同様の処理である。
【００８０】
行列圧縮装置２０００が列を連長圧縮する場合の処理は、図１２において「列」を「行」と置き換え、かつ「行」を「列」と置き換えることで実現できる。
【００８１】
[実施形態４]
図１３は、実施形態４に係る行列圧縮装置２０００を例示するブロック図である。図１３において、矢印は情報の流れを表している。さらに、図１３において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００８２】
実施形態４の行列圧縮装置２０００は、圧縮方向取得部２０８０を有する。圧縮方向取得部２０８０は圧縮方向を取得する。圧縮方向は、行方向又は列方向のいずれかを表す。
【００８３】
実施形態４の圧縮部２０６０は、圧縮方向が行方向を示している場合、対象行列の各行を連長圧縮する。一方、圧縮部２０６０は、圧縮方向が列方向を示している場合、対象行列の各列を連長圧縮する。
【００８４】
なお、実施形態４の行列圧縮装置２０００がソート部２０７０を有する場合、ソート部２０７０は、圧縮方向が行方向であるときは列をソートし、圧縮方向が列方向であるときは行をソートする。
【００８５】
圧縮方向取得部２０８０が圧縮方向を取得する方法は様々である。例えば圧縮方向取得部２０８０は、外部の装置から入力される圧縮方向を取得する。その他にも例えば、圧縮方向取得部２０８０は、手動で入力される圧縮方向を取得する。さらに圧縮方向取得部２０８０は、外部の装置にアクセスして、圧縮方向を取得してもよい。
【００８６】
例えば圧縮方向取得部２０８０は、以下のように圧縮方向を取得する。まず、圧縮方向取得部２０８０は、対象行列を対象とする計算の方式を特定する情報を取得する。この情報を、計算方式情報と表記する。圧縮方向取得部２０８０は、この計算方式情報に対応する圧縮方向を取得する。この場合、行列圧縮装置２０００は、圧縮方向格納部１０と通信可能に接続されている。例えば圧縮方向格納部１０は、複数の計算方式名それぞれに対応付けて圧縮方向を格納している。図１４は、圧縮方向格納部１０と通信可能に接続されている行列圧縮装置２０００を例示するブロック図である。圧縮方向取得部２０８０は、この圧縮方向格納部１０から、方式特定情報が示す計算方式名に対応する圧縮方向を取得する。なお、方式特定情報は、計算方式名の代わりに、各計算方式に割り当てられた ID などを示していてもよい。
【００８７】
図１５は、圧縮方向格納部１０に格納されている情報をテーブル形式で例示する図である。このテーブルを、圧縮情報テーブル１００と表記する。圧縮情報テーブル１００は、計算方式名１０２に対応付けて圧縮方向１０４を示す。圧縮情報テーブル１００の１行目のレコードに示されている CD（Coordinate Descent）法は、主に列方向のアクセスを行う計算であることが知られている。CD 法は、例えば非特許文献３に記載されている。そのため、圧縮情報テーブル１００の１行目のレコードは、CD 法に対応する圧縮方向として「列方向」を示している。
【００８８】
一方、圧縮情報テーブル１００の２行目に示されている SGD（Stochastic Gradient Descent）法は、主に行方向のアクセスを行う計算であることが知られている。SGD 法は、例えば非特許文献４に記載されている。そのため、圧縮情報テーブル１００の２行目のレコードは、SGD 法に対応する圧縮方向として「行方向」を示している。
【００８９】
＜処理の流れ＞
図１６は、実施形態４の行列圧縮装置２０００において実行される処理の流れを例示するフローチャートである。ステップＳ３０２において、対象行列取得部２０２０は、対象行列を取得する。ステップＳ３０４において、圧縮方向取得部２０８０は、圧縮方向を取得する。ステップＳ３０６において、行列圧縮装置２０００は、圧縮方向が行方向を示すか否かを判定する。圧縮方向が行方向を示す場合（ステップＳ３０６：ＹＥＳ）、図１６の処理はステップＳ３０８に進む。一方、圧縮方向が行方向を示さない場合（ステップＳ３０６：ＮＯ）、図１６の処理はステップＳ３１２に進む。
【００９０】
ステップＳ３０８及びＳ３１０は、行方向について連長圧縮を行う場合の処理である。ステップＳ３０８において、置換部２０４０は、各行について代表値を算出し、各行の要素をその行について算出した代表値のいずれかで置き換える。ステップＳ３１０において、圧縮部２０６０は、対象行列の各行を連長圧縮する。
【００９１】
一方、ステップＳ３１２及びＳ３１４は、列方向について連長圧縮を行う場合の処理である。ステップＳ３１２において、置換部２０４０は、各列について代表値を算出し、各列の要素をその列について算出した代表値のいずれかで置き換える。ステップＳ３１４において、圧縮部２０６０は、対象行列の各列を連長圧縮する。
【００９２】
＜作用・効果＞
本実施形態によれば、行列圧縮装置２０００に対して、連長圧縮を行う方向を指定することができる。そのため、連長圧縮の方向が固定されている場合と比較し、行列圧縮装置２０００の利便性が高くなる。
【００９３】
[実施形態５]
図１７は、実施形態５に係る行列圧縮装置２０００を例示するブロック図である。図１７において、矢印は情報の流れを表している。さらに、図１７において、各ブロックは、ハードウエア単位の構成ではなく、機能単位の構成を表している。
【００９４】
実施形態５の行列圧縮装置２０００は、圧縮方向決定部２１００を有する。圧縮方向決定部２１００は、圧縮部２０６０が連長圧縮を行う圧縮方向を決定する。
【００９５】
なお、実施形態５の行列圧縮装置２０００がソート部２０７０を有する場合、ソート部２０７０は、圧縮方向が行方向であるときは列をソートし、圧縮方向が列方向であるときは行をソートする。
【００９６】
例えば圧縮方向決定部２１００は、対象行列を対象として行われる計算の内容を表す情報を取得し、この情報に基づいて圧縮方向を決定する。以下、この情報を計算内容情報と表記する。例えば計算内容情報は、対象行列を対象として行われる計算の内容を表す数式やプログラムなどを示す。
【００９７】
例えば圧縮方向決定部２１００は、計算内容情報が示す数式やプログラムなどを解析することで、この数式やプログラムなどが対象行列を行方向にアクセスする回数と列方向にアクセスする回数を算出する。そして、圧縮方向決定部２１００は、行方向のアクセスが列方向のアクセスより多い場合は圧縮方向を行方向とし、列方向のアクセスが行方向のアクセスより多い場合は圧縮方向を列方向とする。
【００９８】
例えば、圧縮方向決定部２１００が、対象行列を対象とする計算を表す数式として、以下の数式（１）を取得したとする。数式（１）において、xik は、対象行列の i 列目かつ k 行目の要素を表す。数式（１）は、ある列 i に含まれる要素を足し合わせる計算を表すため、列方向へのアクセスが多い。そのため、圧縮方向決定部２１００は、圧縮方向を行方向に決定する。
【数１】
2015118455.tif 000003
【００９９】
一方、圧縮方向決定部２１００が上記の数式（２）を取得したとする。数式（２）において、xkj は、対象行列の k 列目かつ j 行目の要素を表す。数式（２）は、ある行 j に含まれる要素を足し合わせる計算を表すため、行方向へのアクセスが多い。そのため、圧縮方向決定部２１００は、圧縮方向を行方向に決定する。
【０１００】
＜処理の流れ＞
図１８は、実施形態５の行列圧縮装置２０００において実行される処理の流れを例示するフローチャートである。図１８のフローチャートは、図１６のフローチャートにおけるステップＳ３０４の代わりにステップＳ４０２を有する点以外は、図１６のフローチャートと同じである。ステップＳ４０２において、圧縮方向決定部２１００は、圧縮方向を決定する。
【０１０１】
＜作用・効果＞
本実施形態によれば、行列圧縮装置２０００によって圧縮方向の決定が行われるため、行列圧縮装置２０００に対して圧縮方向を指定する場合と比較し、行列圧縮装置２０００の利便性が高くなる。
【０１０２】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【０１０３】
例えば、圧縮部２０６０は、行方向又は列方向のいずれか一方向についてのみしか連長圧縮を行えなくてもよい。例えば、圧縮部２０６０が、行方向のみに連長圧縮を行うとする。この場合に列方向に連長圧縮を行いたい場合、対象行列を転置してから圧縮部２０６０に入力し、圧縮部２０６０によって圧縮された対象行列を再度転置することで、対象行列を行方向について連長圧縮したことと同様の効果を得ることができる。対象行列を転置する機能は、行列圧縮装置２０００の内部に設けられてもよいし、外部に設けられてもよい。ソート部２０７０についても同様のことを行えば、ソート部２０７０は、行方向又は列方向のいずれか一方向についてのみしかソートを行えなくてもよい。
【０１０４】
以下、参考形態の例を付記する。
１．  複数の要素を有する対象行列を取得する対象行列取得手段と、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換手段と、
前記置換手段によって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮手段と、
を有する行列圧縮装置。
２．  前記置換手段は、前記対象行列の行又は列ごとにその行又はその列に含まれる要素を複数のグループに分け、前記グループごとにそのグループに含まれる要素に基づいて前記代表値を算出し、各要素をその要素が属する前記グループについて算出した前記代表値で置き換える１．に記載の行列圧縮装置。
３．  前記置換手段は、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素の値域を所定幅で分割した部分値域を算出し、各部分値域を前記グループとする２．に記載の行列圧縮装置。
４．  前記置換手段は、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素に対して k-means クラスタリングを行うことで、その行又はその列に含まれる要素を複数のグループに分ける２．に記載の行列圧縮装置。
５．  前記圧縮手段が対象行列を連長圧縮する前に、前記圧縮手段が行方向に連長圧縮を行う場合は前記対象行列の列をソートし、前記圧縮手段が列方向に連長圧縮を行う場合は前記対象行列の行をソートするソート手段を有する請求項１乃至４いずれか一項に記載の行列圧縮装置。
６．  前記ソート手段は、前記対象行列の行又は列を１つの単語とみなした場合に各行又は各列が辞書順に並ぶように、前記対象行列の行又は列をソートする５．に記載の行列圧縮装置。
７．  前記ソート手段は、
前記圧縮手段が前記対象行列を行方向について連長圧縮する場合、前記対象行列の行ごとに優先度を算出し、各列の比較を、優先度が高い行に位置する要素から順に行うことで、列をソートし、
前記圧縮手段が前記対象行列を列方向に連長圧縮する場合、前記対象行列の列ごとに優先度を算出し、各行の比較を、優先度が高い列に位置する要素から順に行うことで、行をソートする、
５．に記載の行列圧縮装置。
８．  前記ソート手段は、重複している要素の数が多い行又は列ほど高い優先度を算出する７．に記載の行列圧縮装置。
９．  前記圧縮手段が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を取得する圧縮方向取得手段を有し、
前記置換手段は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮手段は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する１．乃至８．いずれか一項に記載の行列圧縮装置。
１０．  前記圧縮方向取得手段は、
前記対象行列を対象に行われる計算の方式を表す情報である計算方式情報を取得し、
前記計算方式情報と前記圧縮方向とを対応づけて格納している圧縮方向格納手段から、取得した前記計算方式情報に対応する前記圧縮方向を取得する、
９．に記載の行列圧縮装置。
１１．  前記圧縮手段が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を決定する圧縮方向決定手段を有し、
前記置換手段は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮手段は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する１．乃至８．いずれか一項に記載の行列圧縮装置。
１２．  前記圧縮方向決定手段は、前記対象行列を対象に行われる計算の内容を表す情報である計算内容情報を取得し、その計算内容情報に基づいて前記圧縮方向を決定する１１．に記載の行列圧縮装置。
１３．  コンピュータによって実行される制御方法であって、
複数の要素を有する対象行列を取得する対象行列取得ステップと、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換ステップと、
前記置換ステップによって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮ステップと、
を有する制御方法。
１４．  前記置換ステップは、前記対象行列の行又は列ごとにその行又はその列に含まれる要素を複数のグループに分け、前記グループごとにそのグループに含まれる要素に基づいて前記代表値を算出し、各要素をその要素が属する前記グループについて算出した前記代表値で置き換える１３．に記載の制御方法。
１５．  前記置換ステップは、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素の値域を所定幅で分割した部分値域を算出し、各部分値域を前記グループとする１４．に記載の制御方法。
１６．  前記置換ステップは、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素に対して k-means クラスタリングを行うことで、その行又はその列に含まれる要素を複数のグループに分ける１４．に記載の制御方法。
１７．  前記圧縮ステップが対象行列を連長圧縮する前に、前記圧縮ステップが行方向に連長圧縮を行う場合は前記対象行列の列をソートし、前記圧縮ステップが列方向に連長圧縮を行う場合は前記対象行列の行をソートするソートステップを有する１３．乃至１６．いずれか一項に記載の制御方法。
１８．  前記ソートステップは、前記対象行列の行又は列を１つの単語とみなした場合に各行又は各列が辞書順に並ぶように、前記対象行列の行又は列をソートする１７．に記載の制御方法。
１９．  前記ソートステップは、
前記圧縮ステップが前記対象行列を行方向について連長圧縮する場合、前記対象行列の行ごとに優先度を算出し、各列の比較を、優先度が高い行に位置する要素から順に行うことで、列をソートし、
前記圧縮ステップが前記対象行列を列方向に連長圧縮する場合、前記対象行列の列ごとに優先度を算出し、各行の比較を、優先度が高い列に位置する要素から順に行うことで、行をソートする、
１７．に記載の制御方法。
２０．  前記ソートステップは、重複している要素の数が多い行又は列ほど高い優先度を算出する１９．に記載の制御方法。
２１．  前記圧縮ステップが行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を取得する圧縮方向取得ステップを有し、
前記置換ステップは、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮ステップは、前記圧縮方向が表す方向について前記対象行列を連長圧縮する１３．乃至２０．いずれか一項に記載の制御方法。
２２．  前記圧縮方向取得ステップは、
前記対象行列を対象に行われる計算の方式を表す情報である計算方式情報を取得し、
前記計算方式情報と前記圧縮方向とを対応づけて格納している圧縮方向格納手段から、取得した前記計算方式情報に対応する前記圧縮方向を取得する、
２１．に記載の制御方法。
２３．  前記圧縮ステップが行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を決定する圧縮方向決定ステップを有し、
前記置換ステップは、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮ステップは、前記圧縮方向が表す方向について前記対象行列を連長圧縮する１３．乃至２０．いずれか一項に記載の制御方法。
２４．  前記圧縮方向決定ステップは、前記対象行列を対象に行われる計算の内容を表す情報である計算内容情報を取得し、その計算内容情報に基づいて前記圧縮方向を決定する２３．に記載の制御方法。
２５．  コンピュータに、
複数の要素を有する対象行列を取得する対象行列取得機能と、
前記対象行列の行又は列ごとに、その行又はその列に含まれる各要素の値を用いてその行又はその列に含まれる要素の数より少ない個数の代表値を算出し、その行又はその列に含まれる各要素の値をいずれかの前記代表値に置き換える置換機能と、
前記置換機能によって変換された前記対象行列を行方向又は列方向について連長圧縮する圧縮機能と、
を持たせるプログラム。
２６．  前記置換機能は、前記対象行列の行又は列ごとにその行又はその列に含まれる要素を複数のグループに分け、前記グループごとにそのグループに含まれる要素に基づいて前記代表値を算出し、各要素をその要素が属する前記グループについて算出した前記代表値で置き換える２５．に記載のプログラム。
２７．  前記置換機能は、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素の値域を所定幅で分割した部分値域を算出し、各部分値域を前記グループとする２６．に記載のプログラム。
２８．  前記置換機能は、前記対象行列の行又は列ごとに、その行又はその列に含まれる要素に対して k-means クラスタリングを行うことで、その行又はその列に含まれる要素を複数のグループに分ける２６．に記載のプログラム。
２９．  前記圧縮機能が対象行列を連長圧縮する前に、前記圧縮機能が行方向に連長圧縮を行う場合は前記対象行列の列をソートし、前記圧縮機能が列方向に連長圧縮を行う場合は前記対象行列の行をソートするソート機能を有する２５．乃至２８．いずれか一項に記載のプログラム。
３０．  前記ソート機能は、前記対象行列の行又は列を１つの単語とみなした場合に各行又は各列が辞書順に並ぶように、前記対象行列の行又は列をソートする２９．に記載のプログラム。
３１．  前記ソート機能は、
前記圧縮機能が前記対象行列を行方向について連長圧縮する場合、前記対象行列の行ごとに優先度を算出し、各列の比較を、優先度が高い行に位置する要素から順に行うことで、列をソートし、
前記圧縮機能が前記対象行列を列方向に連長圧縮する場合、前記対象行列の列ごとに優先度を算出し、各行の比較を、優先度が高い列に位置する要素から順に行うことで、行をソートする、
２９．に記載のプログラム。
３２．  前記ソート機能は、重複している要素の数が多い行又は列ほど高い優先度を算出する３１．に記載のプログラム。
３３．  前記コンピュータに、前記圧縮機能が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を取得する圧縮方向取得機能を持たせ、
前記置換機能は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮機能は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する２５．乃至３２．いずれか一項に記載のプログラム。
３４．  前記圧縮方向取得機能は、
前記対象行列を対象に行われる計算の方式を表す情報である計算方式情報を取得し、
前記計算方式情報と前記圧縮方向とを対応づけて格納している圧縮方向格納手段から、取得した前記計算方式情報に対応する前記圧縮方向を取得する、
３３．に記載のプログラム。
３５．  前記圧縮機能が行方向と列方向のどちらについて連長圧縮を行うかを表す圧縮方向を決定する圧縮方向決定機能を有し、
前記置換機能は、前記圧縮方向が行方向を表す場合、前記対象行列の行ごとにその行に含まれる要素の数より少ない個数の代表値を算出し、前記圧縮方向が列方向を表す場合、前記対象行列の列ごとにその列に含まれる要素の数より少ない個数の代表値を算出し、
前記圧縮機能は、前記圧縮方向が表す方向について前記対象行列を連長圧縮する２５．乃至３２．いずれか一項に記載のプログラム。
３６．  前記圧縮方向決定機能は、前記対象行列を対象に行われる計算の内容を表す情報である計算内容情報を取得し、その計算内容情報に基づいて前記圧縮方向を決定する３５．に記載のプログラム。
【符号の説明】
【０１０５】
１０ 圧縮方向格納部
１００ 圧縮情報テーブル
１０２ 計算方式名
１０４ 圧縮方向
１０２０ バス
１０４０ プロセッサ
１０６０ メモリ
１０８０ ストレージ
１２２０ 対象行列取得モジュール
１２４０ 置換モジュール
１２６０ 圧縮モジュール
２０００ 行列圧縮装置
２０２０ 対象行列取得部
２０４０ 置換部
２０６０ 圧縮部
２０７０ ソート部
２０８０ 圧縮方向取得部
２１００ 圧縮方向決定部
【図１】
2015118455.tif 000004
【図２】
2015118455.tif 000005
【図３】
2015118455.tif 000006
【図４】
2015118455.tif 000007
【図５】
2015118455.tif 000008
【図６】
2015118455.tif 000009
【図７】
2015118455.tif 000010
【図８】
2015118455.tif 000011
【図９】
2015118455.tif 000012
【図１０】
2015118455.tif 000013
【図１１】
2015118455.tif 000014
【図１２】
2015118455.tif 000015
【図１３】
2015118455.tif 000016
【図１４】
2015118455.tif 000017
【図１５】
2015118455.tif 000018
【図１６】
2015118455.tif 000019
【図１７】
2015118455.tif 000020
【図１８】
2015118455.tif 000021