아인슈타인 합계를 최적으로 컴파일

Question

Einstein summation은 numpy, torch, tensorflow 등과 같은 텐서 라이브러리에서 발견 된 텐서 연산을 표현하는 편리한 방법입니다.

유연성 덕분에 3 개의 행렬의 곱을 나타낼 수 있습니다. $X$, $Y$, $Z$ 차원의 $(a,b)$, $(b,c)$, $(c,d)$ 같이

X.Y.Z = einsum('ab,bc,cd->ad',X,Y,Z)

그러나 위의 내용은 다음과 같이 컴파일됩니다.

for a_ in range(a):
  for d_ in range(d):
     res[a_,d_] = 0
     for b_ in range(b):
        for c_ in range(c):
           res[a_,d_] += X[a_,b_] * Y[b_,c_] * Z[c_, d_]

이 기본은 단순히 다음을 수행 할 때 행렬의 크기가 2 차입니다.

einsum('ac,cd->ad',einsum('ab,bc'->'ac', X, Y), Z)

단지 입방체 일 것입니다.

einsum수행 할 더 스마트 한 구현을 상상할 수있는 대략 세 가지 수준의 최적화가 있습니다 .

1. 텐서의 아인 섬 분해 $(x_1, \ldots, x_n)$ 텐서 쌍의 einsum으로 $x_1, x_2$, $e(x_1, x_2), x_3$등 계산 시간을 최적화합니다.

2. 연관성 (해당되는 경우)에 의존하여 해당 쌍을 신중하게 선택하고 (이는 고전적인 동적 프로그래밍 문제) 적절한 중간 텐서를 구성합니다.

3. 특정 텐서 계산을위한 Strassen과 유사한 공식 알아보기

3은 분명히 도달 할 수없는 것처럼 보이지만 1과 2는 합리적으로 간단한 알고리즘으로 정확하게 달성 할 수있는 것처럼 보입니다. 이러한 알고리즘은 일반적인 아인슈타인 합계로 알려져 있습니까? 그들은 연구 되었습니까?

Answer 1

최적의 수축 차수를 찾는 일반적인 문제는 NP-hard [1] 인 것 같습니다. 수축 순서를 대략적으로 최적화하고 관련 참조를 포함하는 최근 논문은 [2]입니다.

[1] Chi-Chung, Lam, P. Sadayappan 및 Rephael Wenger. "병렬 실행을위한 감소로 다차원 루프 클래스 최적화" 병렬 처리 편지 7.02 (1997) : 157-168.

[2] 쉰들러, 프랭크, 아담 저민. "텐서 네트워크 축소 순서를위한 알고리즘." 기계 학습 : 과학 및 기술 (2020).