エンジニアのtetsuです。
pythonで機械学習に取り組んでいる方々はNumPyを用いてベクトルや行列の演算をする機会が多いと思います。ベクトル、行列の演算はNumPyの中で利用されているBLAS（Basic Linear Algebra Subprograms）を意識しないと本来のパフォーマンスを出すことができないため、注意が必要です。今回は簡単にですが、行列積を活かした高速化の話をします。
なお、本記事で使用されているpythonのバージョンは3.6.1、NumPyとSciPyのバージョンはそれぞれ1.3.1、0.19.1となっています。
BLASについて
BLASは行列・ベクトルの演算をおこなう線形代数ライブラリのことを指します。BLASの実装は1つではなく、色々な実装のBLASが存在します。例えば、OpenBLAS、ATLAS、Intel MKLなどがあります。BLASで定義される演算にはLevel 1 BLAS、Level 2 BLAS、Level 3 BLASという分類があり、それぞれベクトルとベクトルの演算、行列とベクトルの演算、行列と行列の演算を扱っています。
BLASを使うときに留意するべきこととして、キャッシュヒットなどの違いによって、より高いLevelのBLASを利用したほうが効率よく計算できるという点が挙げられます。例えば、Level 1 BLASのベクトル演算のみを使った計算がLevel 3 BLASの行列演算を使って置き換えられるならば、そうしたほうが高速になります。このことを次の実験によりみていきましょう。
行列積の計算時間比較
実数の正方行列
の行列積
を色々な計算方法によっておこない、それぞれの計算時間をみていきます。比較した計算方法は以下のとおりです。行列
は乱数で生成されています。
- ベクトルの内積を使用（Level 1 BLAS）
1234C1 = numpy.zeros([1000, 1000], dtype=np.float64)for i in range(1000):for j in range(1000):C1[i, j] = numpy.dot(A[i, :], B[:, j]) - 行列ベクトル積を使用（Level 2 BLAS）
123C2 = numpy.zeros([1000, 1000], dtype=np.float64)for i in range(1000):C2[i, :] = numpy.dot(A[i, :], B) - 行列行列積を使用（Level 3 BLAS）
1C3 = numpy.dot(A, B)
上記のコードを7回実行した場合の平均実行時間は以下のようになりました。
| 計算方法 | 計算時間[ms] |
|---|---|
| ベクトルの内積（Level 1 BLAS） |  |
| 行列ベクトル積（Level 2 BLAS） |  |
| 行列行列積（Level 3 BLAS） |  |
計算時間をみると上から順に1桁程度高速化されており、行列行列積の演算を利用したほうが良いということがわかります。なお、それぞれの計算方法でそれほど精度が変わらないことは計算結果のフロベニウスノルムを計算することで確認できます（フロベニウスノルムは行列の各要素の二乗和の平方根です）。
|
1 2 |
print(numpy.linalg.norm(C1 - C2, "fro")) # output: 8.61413204129e-11 print(numpy.linalg.norm(C1 - C3, "fro")) # output: 5.89514214983e-11 |
cosine類似度の高速化の例
cosine類似度の計算を行列行列積を用いて高速化する例をここで示したいと思います。cosine類似度は2つのベクトル
に対して次のように定義されます。
cosine類似度を計算するための最も簡単な方法はSciPyのscipy.spatial.distance.cosineを使うことかと思います。例えば行列
と行列
のすべての行ベクトル同士のcosine類似度を計算させるときにはfor文を使って次のように計算できます。
|
1 2 3 4 5 |
from scipy.spatial.distance import cosine cos_sim = numpy.zeros([1000, 1000], dtype=numpy.float64) for i in range(1000): for j in range(1000): cos_sim[i, j] = cosine(A[i, :], B[j, :]) |
上記のコードはfor文を使わずに行列行列積を用いて次のように置き換えることができます。
|
1 2 3 |
normA = numpy.sqrt(numpy.sum(A * A, axis=1)) normB = numpy.sqrt(numpy.sum(B * B, axis=1)) cos_sim = 1 - numpy.dot(A / normA.reshape(-1, 1), (B / normB.reshape(-1, 1)).T) |
平均計算時間は次のように大きく差がでました。桁違いの速さです。ただしSciPyのcosine類似度の場合には計算のたびにベクトルの正規化がおこなわれており（cosine類似度の式の分母の部分）、その分も含まれています。
| 計算方法 | 計算時間[ms] |
|---|---|
| SciPyのcosine類似度（Level 1 BLAS） |  |
| 行列行列積を使用（Level 3 BLAS） |  |
さいごに
今回はベクトルの内積や行列ベクトル積を行列行列積（Level 3 BLAS）で置き換えることで高速化される例を紹介しました。
遅いと感じている計算がある場合には、行列行列積への置き換えをしてみると見違えるほど速くなるかもしれません。簡単にできるため、置き換えが可能な場合にはぜひ試していただきたいです。