ここでは機械学習でよく扱うことになるデータである疎行列について解説します。具体的には以下の点を学ぶことができます。

当ページで学べること

疎行列とは何か
機械学習で疎行列を扱う時の問題点
機械学習の各分野で見られる疎行列の例
Python で疎行列を扱うときによく使う関数

疎行列とは

行列のほとんどの要素が 0 のもののことを「疎行列」と言います。たとえば、以下は \(3 \times 6\) の疎行列です。

\[
A=
\begin{pmatrix}
1 & 0 & 0 & 2 & 0 & 0 \\
0 & 2 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\]

機械学習では何千、何万次元もの巨大な疎行列データを扱うことが多々あるため、疎行列の特性を知っておくことはとても重要です。

なお、疎行列を扱う際は「過疎度」という指標が使われる時があります。これは以下の計算式で求められる指標です。

\[
{\small 過疎度}
=
\dfrac
{{\small 値が \ } 0 { \ \small の要素の数}}
{\small 全要素の数}
\]

上の行列の例では全部で 18 個の要素中で 13 個の要素が 0 なので \(13 \div 18 \approx 0.722\) になり、過疎度は約 \(72 \%\) であることがわかります。

機械学習における疎行列の問題点

疎行列は機械学習において非常によく目にするものですが、これをそのまま扱うのには非常に大きな問題があります。それが、空間計算量と時間計算量の問題です。

空間計算量 “Space Complexity”

大きな行列は多くのメモリを使います。そして機械学習の実務上で目にする最も大きな行列は、要素のほとんどがゼロである疎行列です。

例としては、ウェブサイト間のリンクを示したリンク行列は非常に大きな疎行列になります。一冊の本の中で、広辞苑に乗っている全単語のうち、いくつが使われたかを示すような単語行列も、リンク行列よりは小さいですが、それでも大きな疎行列になります。

このような疎行列において、値が 0 の要素にも、いちいち 32ビット（時には64ビット）が浪費されます。値が 0 の要素は全く情報を含んでいないわけなので、これは完全にメモリーの無駄遣いになります。

時間計算量 “Time Complexity”

非常に大きな疎行列をメモリに格納できたとして、この疎行列を使って演算を実行したいとします。この場合、まったく情報のない 0 同士の演算処理に非常に多くの時間が浪費されてしまうことになります。もちろん疎行列のサイズが大きくなればなるほど、この時間の浪費問題は大きくなります。

機械学習においてよく見られる疎行列

機械学習の応用において疎行列は何回も現れます。ここではどういうときに疎行列を目にするのかを具体的に紹介します。

データにおける疎行列

疎行列はある種類のデータでよく見られます。特に、何らかの活動回数のカウントや何らかの事象の発生回数などです。たとえば次のようなものがあります。

ユーザーが映画リストの中にある映画を見たか見ていないか
ユーザーが商品リストの中にある商品を買ったか買っていないか
ユーザーが楽曲リストの中の曲を聴いたことがある回数

データの準備 “data preparation” における疎行列

疎行列は、データの準備において使われるエンコーディング・スキームでも現れます。たとえば以下のようなものがあります。

ワンホット・エンコーディング：カテゴリカル・データをバイナリ・ベクトルとして表すために使われる
カウント・エンコーディング：ドキュメントのボキャブラリの中の単語の頻度を表すために使われる
TF-IDFエンコーディング：ボキャブラリの中の単語頻度スコアの正規化のために使われる

機械学習のその他の分野における疎行列

機械学習におけるいくつかの学問分野は、疎行列に直接的に取り組む必要があります。なぜなら、インプットデータがほとんど既に疎行列だからです。例えば以下の分野です。

自然言語処理：テキストドキュメントを扱うとき
レコメンダシステム：全商品カタログ内の商品を扱う時
コンピュータ・ビジョン：画像が多くの黒ピクセルを含んでいるとき

疎行列の問題点の解決策

それでは以上のような疎行列を扱うときはどうすれば良いのでしょうか。代表的な解決策は、過疎行列を異なるデータ構造で表すことです。具体的には、値がゼロの要素は無視して、ゼロ以外の要素のみを扱えるように工夫するということです。たとえば以下の 3 つのデータ構造が、この目的のために一般的に使われます。

辞書のキー：疎行列におけるゼロ以外の要素の行と列をペアにして辞書のキーとして保管します。そして値は辞書の値として保管します。
リストのリスト：行列のそれぞれの行をリストとして保管します。そして値がゼロ以外の列のインデックスとその値はタプルで保管します。
座標リスト：行のインデックス、列のインデックス、値の 3 つを 1 つのタプルとして保管します。

さらに効率的な演算を行うのに適した以下のデータ構造も開発されています。これらについては興味がある場合は、別途調べてみると良いでしょう。

圧縮 Sparse Row
圧縮 Sparse Column

Pythonで疎行列を扱うためによく使う関数

Python では SciPy ライブラリで疎行列を扱うためのツールが提供されています。そしてほとんどの SciPy の線形代数の関数は、NumPy の配列に対して使えます。例えば、NumPyに保管した疎行列は、csr_matrix() 関数によって、CSR形式で表すことができます。そして to_dense() 関数で、それを疎行列に戻すことができます。

In [1]:

# NumPy と SciPy のインポート
import numpy as np
from scipy.sparse import csr_matrix

# 行列を定義
A = np.array([
    [1,0,0,1,0,0],
    [0,0,2,0,0,1],
    [0,0,0,2,0,0]])
print(A)

[[1 0 0 1 0 0]
 [0 0 2 0 0 1]
 [0 0 0 2 0 0]]

In [2]:

# CSR　表記に変換
S = csr_matrix(A)
print(S)

  (0, 0)	1
  (0, 3)	1
  (1, 2)	2
  (1, 5)	1
  (2, 3)	2

In [3]:

# 再行列化
B = S.todense()
print(B)

[[1 0 0 1 0 0]
 [0 0 2 0 0 1]
 [0 0 0 2 0 0]]

プログラマーのための線形代数