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

Содержание и основные понятия

На предыдущей странице: матрица меняет пространство.
Применим одно правило, затем другое. Общая таблица может заменить оба шага, но порядок действий важен.
Сначала поворот, затем растяжение.
Для изменения рисунка включитеJavaScript; расчёт и теория доступны далее.
Произведение возникает из композиции функций
Пусть сначала применяется
B
B
B
, затем
A
A
A
:
z
=
B
x
,
y
=
A
z
=
A
(
B
x
)
.
z=Bx,
\qquad y=Az=A(Bx).
z
=
B
x
,
y
=
A
z
=
A
(
B
x
)
.
Хотим заменить два последовательных оператора одним
C
C
C
, чтобы
y
=
C
x
y=Cx
y
=
C
x
. Подставим
z
r
=
∑
j
=
1
n
B
r
j
x
j
z_r=\sum_{j=1}^{n}B_{rj}x_j
z
r
​
=
j
=
1
∑
n
​
B
r
j
​
x
j
​
в формулу для
y
i
y_i
y
i
​
:
y
i
=
∑
r
=
1
k
A
i
r
z
r
=
∑
r
=
1
k
A
i
r
∑
j
=
1
n
B
r
j
x
j
=
∑
j
=
1
n
(
∑
r
=
1
k
A
i
r
B
r
j
)
x
j
.
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.
y
i
​
=
r
=
1
∑
k
​
A
i
r
​
z
r
​
=
r
=
1
∑
k
​
A
i
r
​
j
=
1
∑
n
​
B
r
j
​
x
j
​
=
j
=
1
∑
n
​
(
r
=
1
∑
k
​
A
i
r
​
B
r
j
​
)
x
j
​
.
Следовательно,
A
∈
R
m
×
k
,
B
∈
R
k
×
n
,
C
=
A
B
∈
R
m
×
n
,
C
i
j
=
∑
r
=
1
k
A
i
r
B
r
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}.
A
∈
R
m
×
k
,
B
∈
R
k
×
n
,
C
=
A
B
∈
R
m
×
n
,
C
ij
​
=
r
=
1
∑
k
​
A
i
r
​
B
r
j
​
.
Внутренняя размерность
k
k
k
должна совпасть, потому что она перечисляет компоненты промежуточного вектора
z
z
z
. Внешние размеры
m
,
n
m,n
m
,
n
остаются размерами итогового оператора.
Row-column trace без скрытого шага
Возьмём
A
=
[
2
1
0
1
]
,
B
=
[
0
−
1
1
0
]
.
A=\begin{bmatrix}2&1\\0&1\end{bmatrix},
\qquad
B=\begin{bmatrix}0&-1\\1&0\end{bmatrix}.
A
=
[
2
0
​
1
1
​
]
,
B
=
[
0
1
​
−
1
0
​
]
.
Каждая ячейка
A
B
AB
A
B
является dot строки
A
A
A
и столбца
B
B
B
:
A
B
=
[
2
⋅
0
+
1
⋅
1
2
⋅
(
−
1
)
+
1
⋅
0
0
⋅
0
+
1
⋅
1
0
⋅
(
−
1
)
+
1
⋅
0
]
=
[
1
−
2
1
0
]
.
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}.
A
B
=
[
2
⋅
0
+
1
⋅
1
0
⋅
0
+
1
⋅
1
​
2
⋅
(
−
1
)
+
1
⋅
0
0
⋅
(
−
1
)
+
1
⋅
0
​
]
=
[
1
1
​
−
2
0
​
]
.
Например, элемент
(
0
,
1
)
(0,1)
(
0
,
1
)
равен
−
2
-2
−
2
, а не произведению
A
01
B
01
=
−
1
A_{01}B_{01}=-1
A
01
​
B
01
​
=
−
1
. Покомпонентное произведение Адамара и matmul являются разными операциями даже для одинаковых shapes.
Порядок операторов читается справа налево
В выражении
(
A
B
)
x
(AB)x
(
A
B
)
x
первым действует
B
B
B
. При
x
=
[
1
,
2
]
T
x=[1,2]^T
x
=
[
1
,
2
]
T
:
B
x
=
[
−
2
,
1
]
T
,
A
(
B
x
)
=
[
−
3
,
1
]
T
.
Bx=[-2,1]^T,
\qquad A(Bx)=[-3,1]^T.
B
x
=
[
−
2
,
1
]
T
,
A
(
B
x
)
=
[
−
3
,
1
]
T
.
Обратный порядок даёт
B
A
=
[
0
−
1
2
1
]
,
B
A
x
=
[
−
2
,
4
]
T
.
BA=\begin{bmatrix}0&-1\\2&1\end{bmatrix},
\qquad BAx=[-2,4]^T.
B
A
=
[
0
2
​
−
1
1
​
]
,
B
A
x
=
[
−
2
,
4
]
T
.
Значит,
A
B
≠
B
A
AB\ne BA
A
B

=
B
A
. Геометрически «сначала повернуть, затем выполнить shear/scale» обычно не равно «сначала деформировать, затем повернуть».
Ассоциативность не означает коммутативность
При совместимых shapes
A
(
B
C
)
=
(
A
B
)
C
.
A(BC)=(AB)C.
A
(
BC
)
=
(
A
B
)
C
.
Обе стороны описывают одну композицию трёх функций в одном порядке. Скобки меняют только то, какое промежуточное произведение вычисляется первым. Для размеров
[
m
,
k
]
[
k
,
n
]
[
n
,
p
]
[m,k][k,n][n,p]
[
m
,
k
]
[
k
,
n
]
[
n
,
p
]
стоимость может заметно отличаться:
cost
⁡
(
(
A
B
)
C
)
∼
m
k
n
+
m
n
p
,
cost
⁡
(
A
(
B
C
)
)
∼
k
n
p
+
m
k
p
.
\operatorname{cost}((AB)C)\sim mkn+mnp,
\qquad
\operatorname{cost}(A(BC))\sim knp+mkp.
cost
((
A
B
)
C
)
∼
mkn
+
mn
p
,
cost
(
A
(
BC
))
∼
kn
p
+
mk
p
.
В точной арифметике результаты равны. В floating-point изменение порядка суммирования может дать небольшое расхождение округления. Это не отменяет алгебраическую ассоциативность, но требует допуска при численном сравнении.
Identity удовлетворяет
A
I
=
I
A
=
A
AI=IA=A
A
I
=
I
A
=
A
. Нулевая матрица подходящего shape уничтожает результат. Транспонирование обращает порядок:
(
A
B
)
T
=
B
T
A
T
.
(AB)^T=B^TA^T.
(
A
B
)
T
=
B
T
A
T
.
Последнее равенство можно проверить по индексам и оно станет важным для backward pass.
Прямой алгоритм произведения
[
m
,
k
]
×
[
k
,
n
]
[m,k]\times[k,n]
[
m
,
k
]
×
[
k
,
n
]
требует
m
k
n
mkn
mkn
умножений. Параллельное устройство меняет организацию вычислений и движение данных, но не формулу ячейки. В лаборатории выбирайте одну ячейку trace и проверяйте два произведения до сравнения полных
A
B
AB
A
B
и
B
A
BA
B
A
.
A, B = [[2, 1], [0, 1]], [[0, -1], [1, 0]]
C = [[sum(A[i][r] * B[r][j] for r in range(2))
for j in range(2)] for i in range(2)]
assert C == [[1, -2], [1, 0]]
Код повторяет только что разобранные операции.
Полный проверяемыйPython-пример главы
доступен отдельным файлом; показанный короткий фрагмент не заменяет его реализацию.
Если поменять порядок, получится другое преобразование. Это важно и для порядка слоёв нейросети.
Когда теряется направление. Как этот вопрос продолжает полученный результат?
Python-примеры главы 02
Академическая база →