Tensor Network와 수축 순서

연결 그림을 합산 식으로 읽기

텐서 네트워크의 노드는 배열이고 선은 지표입니다. 두 노드를 연결하는 지표는 합산하고, 연결되지 않은 다리는 최종 배열의 축으로 남깁니다. 그림의 공간적 거리는 값의 크기를 뜻하지 않습니다. 연결과 차원 표기가 연산을 결정합니다.

A의 shape는 n×m, B는 m×p, C는 p×q입니다. 출력은 n×q입니다. j와 k는 자유 지표가 아니므로 출력 축에 남지 않습니다. 반복 지표가 어떤 두 축을 묶는지 먼저 확인하세요.

같은 값에 이르는 두 경로

실수의 정확한 산술에서는 결합법칙으로 두 수축 순서가 같습니다. 하지만 중간 배열과 필요한 연산량은 달라집니다. 실습은 두 경로를 실제로 계산하고 마지막 표에서 각각의 값을 비교합니다.

왼쪽 경로는 n×p 중간 배열을 만들고, 오른쪽 경로는 m×q 중간 배열을 만듭니다. 중간 배열을 따로 두지 않는 구현도 가능하지만, 여기서는 표준 밀집 행렬곱으로 비용을 셉니다.

곱셈 횟수를 직접 세기

행렬곱 (n×m)(m×p)는 출력 np개마다 m번의 스칼라 곱셈을 합니다. 같은 계산을 두 단계에 적용하면 다음 식을 얻습니다.

기준 n=2,m=3,p=4,q=2에서 왼쪽은 40회, 오른쪽은 36회입니다. 중간 원소 수는 각각 8개와 6개입니다. n=4,m=2,p=1,q=4로 바꾸면 왼쪽이 24회, 오른쪽이 40회로 유리한 순서가 바뀝니다. 한 방향을 언제나 정답으로 외우면 안 됩니다.

AI와 계산 시스템에서의 의미

attention, 다중 선형층, 텐서 네트워크의 계산 계획에서는 최종 수학식 외에도 수축 순서가 중요합니다. 많은 노드에서는 가능한 순서가 빠르게 늘어납니다. 이 예제는 세 행렬에 한정되며 일반 네트워크의 최적 경로 탐색기를 구현하지 않습니다.

여기서 표시하는 비용은 스칼라 곱셈 횟수입니다. GPU 실행 시간, 메모리 대역폭, 병렬화, 커널 호출은 측정하지 않습니다. 일반 부동소수점에서는 결합 순서에 따라 반올림도 달라질 수 있습니다. 현재 작은 정수 예제는 정확하게 표현할 수 있는 범위라 두 출력의 차이가 0입니다.

확인 문제

1. 중간 배열 크기만 같으면 비용도 같은가요? 아닙니다. 다른 차원도 곱셈 수에 들어갑니다.
2. 모든 차원이 1이면? 두 경로 모두 곱셈 2회입니다.
3. 어떤 지표가 출력으로 남나요? 한 번 등장하는 자유 지표 i와 l입니다.

추가 읽기: Kolda–Bader, Tensor Decompositions and Applications. 본문의 작은 배열·복원·비용 예제는 직접 구성했습니다.