행렬 곱의 Trace를 빠르게 계산

문제점



기계 학습 알고리즘을 구현할 때 두 행렬 $A, B\in\mathbb{R}^{n\times m}$ 곱의 Trace$\mathrm{Tr}(A\cdot B^T)$ 를 계산하는 장면이 자주 있지만, 정의대로 numpy trace 를 사용하면 매우 느리고 곤란하다.

결론



SparseMatrix를 사용하지 않는다면
np.einsum('ij,ij->', A, B)

빠르고 빠르고 SparseMatrix에도 대응하고 싶다면
np.sum(A * B)

비교적 빠르다!

기법 소개



주로 4패턴의 계산방법이 있다(그 밖에도 있으면 코멘트해 주세요).

A. 정의대로


np.trace(A @ B.T)

B. 요소 곱의 합


np.sum(A * B)

C. 숨겨진 함수 inner1d로 계산


from numpy.core.umath_tests import inner1d

np.sum(inner1d(A, B))

다만, 이 inner1d 는 numpy 내부에서 사용되고 있는 함수이므로 추천 되고 있지 않는 것 같습니다 (참조 3).

D. B.를 아인슈타인의 축약기법으로 쓸 수 있는 einsum으로 쓴다


np.einsum('ij,ij->', A, B)

아인슈타인의 축약 기법을 모르는 분은 참고 1.을 참조하십시오. 매우 자세히 정리하고 있습니다. 다만, 이 쓰는 방법은 numpy array만으로 scipy의 SparseMatrix에는 구현되어 있지 않습니다. 다만, 구현하는 움직임은 있는 것 같습니다(참조 4).

실험



환경


  • Python 3.6.6::Anaconda custom (64-bit)
  • numpy: 1.15.3

  • 결과



    제대로 같은 결과가 될지 확인.



    속도를 %timeit로 측정하고 비교.



    D가 압승! 정의대로 계산하는 것보다 10배 정도 빠르다! ! 다만, 위에서 언급했듯이 einsum 는 SparseMatrix 에서는 사용할 수 없기 때문에, 소행렬을 취급할 때에는 B 를 사용하는 것이 좋다고 하는 결론이 되었습니다. B도 정의대로 계산하는 것보다 6배 정도 빠르고, 확실한 결과가 되었습니다.

    여담



    행렬의 전치 마크 $T$를 오른쪽 어깨에 쓰는 파와 왼쪽 어깨에 쓰는 파로 유파가 나뉘어 논문을 읽고 혼란한다. 그렇죠?

    참고


  • 【einsum】아인슈타인의 축약 기법과 같이 사용할 수 있는 numpy의 함수. 성능과 사용법을 해설.
  • What is the best way to compute the trace of a matrix product in numpy?
  • Replacement for numpy.core.umath_tests.inner1d? #10815
  • einsum implementation
  • 좋은 웹페이지 즐겨찾기