02.2 Два преобразования подряд

Произведение возникает из композиции функций

Пусть сначала применяется $B$ , затем $A$ :

z=Bx, \qquad y=Az=A(Bx).

Хотим заменить два последовательных оператора одним $C$ , чтобы $y=Cx$ . Подставим

z_r=\sum_{j=1}^{n}B_{rj}x_j

в формулу для $y_i$ :

y_i=\sum_{r=1}^{k}A_{ir}z_r =\sum_{r=1}^{k}A_{ir}\sum_{j=1}^{n}B_{rj}x_j =\sum_{j=1}^{n}\left(\sum_{r=1}^{k}A_{ir}B_{rj}\right)x_j.

Следовательно,

A\in\mathbb R^{m\times k}, \quad B\in\mathbb R^{k\times n}, \quad C=AB\in\mathbb R^{m\times n}, \quad C_{ij}=\sum_{r=1}^{k}A_{ir}B_{rj}.

Внутренняя размерность $k$ должна совпасть, потому что она перечисляет компоненты промежуточного вектора $z$ . Внешние размеры $m,n$ остаются размерами итогового оператора.

Row-column trace без скрытого шага

Возьмём

A=\begin{bmatrix}2&1\\0&1\end{bmatrix}, \qquad B=\begin{bmatrix}0&-1\\1&0\end{bmatrix}.

Каждая ячейка $AB$ является dot строки $A$ и столбца $B$ :

AB=\begin{bmatrix} 2\cdot0+1\cdot1 & 2\cdot(-1)+1\cdot0\\ 0\cdot0+1\cdot1 & 0\cdot(-1)+1\cdot0 \end{bmatrix} =\begin{bmatrix}1&-2\\1&0\end{bmatrix}.

Например, элемент $(0,1)$ равен $-2$ , а не произведению $A_{01}B_{01}=-1$ . Покомпонентное произведение Адамара и matmul являются разными операциями даже для одинаковых shapes.

Порядок операторов читается справа налево

В выражении $(AB)x$ первым действует $B$ . При $x=[1,2]^T$ :

Bx=[-2,1]^T, \qquad A(Bx)=[-3,1]^T.

Обратный порядок даёт

BA=\begin{bmatrix}0&-1\\2&1\end{bmatrix}, \qquad BAx=[-2,4]^T.

Значит, $AB\ne BA$ . Геометрически «сначала повернуть, затем выполнить shear/scale» обычно не равно «сначала деформировать, затем повернуть».

Ассоциативность не означает коммутативность

При совместимых shapes

A(BC)=(AB)C.

Обе стороны описывают одну композицию трёх функций в одном порядке. Скобки меняют только то, какое промежуточное произведение вычисляется первым. Для размеров $[m,k][k,n][n,p]$ стоимость может заметно отличаться:

\operatorname{cost}((AB)C)\sim mkn+mnp, \qquad \operatorname{cost}(A(BC))\sim knp+mkp.

В точной арифметике результаты равны. В floating-point изменение порядка суммирования может дать небольшое расхождение округления. Это не отменяет алгебраическую ассоциативность, но требует допуска при численном сравнении.

Identity удовлетворяет $AI=IA=A$ . Нулевая матрица подходящего shape уничтожает результат. Транспонирование обращает порядок:

(AB)^T=B^TA^T.

Последнее равенство можно проверить по индексам и оно станет важным для backward pass.

Прямой алгоритм произведения $[m,k]\times[k,n]$ требует $mkn$ умножений. Параллельное устройство меняет организацию вычислений и движение данных, но не формулу ячейки. В лаборатории выбирайте одну ячейку trace и проверяйте два произведения до сравнения полных $AB$ и $BA$ .