희소 및 구조화된 데이터에 대한 효율적인 계산을 위한 텐서의 합성(Composition) 표현

우리는 모든 종류의 텐서와 해당 텐서에 대한 연산을 단순한 함수 합성(function compositions)으로 나타내는 새로운 수학적 형식론을 제안합니다. 텐서는 인덱스에서 값으로 가는 함수입니다. 요소별 연산(예: 활성화 함수)은 값에 적용되는 함수와의 합성을 의미하며, 재인덱싱(re-indexing)(예: reshape, 전치(transposition))은 인덱스에 적용되는 함수와의 합성입니다. 그리고 축소(reduction)는 각 인덱스를 여러 인덱스로 매핑하는 인덱스 함수와 축소 연산(예: 곱(product), 합(sum), 최대값(max))을 모두 포함하는 합성입니다. 텐서 스태킹과 결합하여, 이러한 합성들은 가장 흥미로운 종류의 텐서들(예: 밀집(dense) 텐서, 들쭉날쭉한(jagged) 텐서, 모든 종류의 희소성 패턴, 행렬 분해(matrix factorizations))뿐만 아니라, 어떤 종류의 텐서 간에 이루어지는 einsums를 포함하여 현대 텐서 계산 프레임워크에서 사용 가능한 거의 모든 연산의 지연 버전(lazy versions)을 표현할 수 있습니다. 합성 사이의 항등식(identities)을 이용하면 이러한 표현들을 평가하지 않고도 동등한 형태로 재작성할 수 있습니다. 예를 들어, 두 개의 희소 행렬의 곱은 오직 0이 아닌 값들 간의 곱만 계산되도록 재작성될 수 있으며, 이는 희소 문제를 밀집 문제로 변환합니다. 이 대수학(algebra)을 텐서 계산 엔진의 중간 표현(intermediate representation)으로 사용하면, 텐서에 대한 연산을 정의하는 것(예: 희소 텐서 간의 einsum)에서 인덱스 함수에 대한 대수를 정의하는 것으로 초점을 전환하게 됩니다. 이는 코드베이스 복잡도를 $ ext{O}(mn^2)$ (여기서 $m$은 텐서 간의 이진 연산 수이고, $n$은 텐서 유형의 수임)에서 $ ext{O}(m + k^2)$ (여기서 $k$는 인덱스 함수의 유형 수임)로 줄일 수 있습니다. 이 대수학을 기반으로 하는 텐서 계산 프레임워크의 초안 구현이 공개적으로 이용 가능합니다.