行列の積

行列の積は内積を並べた表です。C = AB の成分 C[i][j] は、A の第 i 行と B の第 j 列の内積です。ほかの性質はすべてこの規則から出てきます。A の行と B の列の長さが同じときにだけ積が存在し、(m×n)(n×p) の積には m·n·p 回の掛け算が必要で、BA はたいてい別の表になります。

「行 × 列」という決まりは、初めて見ると適当に決めた約束のように見えます。そうではありません。A の 1 行は 1 つの入力、B の 1 列は 1 組の重みで、その内積は前のレッスンで見たスコアそのものです。行列の積は、そのスコアを一度にすべて計算するだけです。すべての入力をすべての重みと組み合わせ、第 i 行と第 j 列の結果をマス (i, j) に置きます。こう読めば、形の規則を暗記する必要はありません。内積には同じ長さの 2 つの並びが要る、規則が言っているのはそれだけです。

行列の積のしくみ

A を左に、B を答えを書く場所の上に置きます。すると A の第 i 行は横にまっすぐ C の第 i 行へ、B の第 j 列は縦にまっすぐ C の第 j 列へつながります。行と列が交わるマスが C[i][j] で、その値は 2 つの内積です。行と列を同時にたどり、k 番目どうしを掛けて足します。

$$C_{ij} = \sum_{k=0}^{n-1} A_{ik},B_{kj}$$

ここから 3 つのことがわかります。

• 内側のサイズが一致しなければならない。 行には A の列数（n 個）だけ数があり、列には B の行数だけ数があります。2 つの並びを項ごとに組むので、長さが同じでなければなりません。違えば相手のいない数が残り、積は存在しません。
• 外側のサイズが形を決める。 C の行数は A の行数、列数は B の列数です。(m×n)(n×p) は m×p。共通の n は和の中に消えます。
• 順序が効く。 BA は B の行と A の列を組むので、使う並びがまったく違います。形が違うこともあれば、存在しないこともあり、同じ形で存在しても数値はたいてい違います。AB = BA は例外で、B = I（単位行列）や B = A のような特別な組でだけ成り立ちます。

ニューラルネットワークでは、この図の各部に名前があります。入力のバッチを X の各行に、層の重みベクトルを W の各列に並べると、XW にはすべての入力のすべての重みベクトルに対するスコアが、1 マスに 1 回の内積として入ります。これが線形層がバイアスと活性化の前に行う計算です。

行列の積をステップごとに

デフォルトの入力は A (2×3) = [[1, 2, 3], [4, 0, 1]]、B (3×2) = [[2, 1], [1, 0], [3, 2]] です。添字は NumPy や PyTorch と同じく 0 から数えます。

1. 形を確かめる。 A の行は 3 個、B の列も 3 個なので組めます：3 = 3。外側のサイズから C の形は 2×2 で、A の行と B の列が交わる場所に空の 2×2 の表が現れます。
2. 最初のマスをそろえる。 C[0][0] には A の第 0 行 (1, 2, 3) と B の第 0 列 (2, 1, 3) が必要です。両方のコピーがワークベンチに飛び込み、項ごとに組になります。
3. 項ごとに掛ける。 1 × 2 = 2、累計 2。次に 2 × 1 = 2、累計 4。さらに 3 × 3 = 9、累計 13。掛け算カウンタは 3 / 12 を示します。
4. マスに書き込む。 累計が C[0][0] = 13 に入ります。1 マス、1 回の内積。
5. C の残りを埋める。 同じ規則で残りのマスを行の順に埋めます。C[0][1] は第 0 行のまま第 1 列へ：1×1 + 2×0 + 3×2 = 7。C[1][0] = 4×2 + 0×1 + 1×3 = 11。C[1][1] = 4×1 + 0×0 + 1×2 = 6。A の 0 も掛け算 1 回分のコストがかかります。
6. 積を読む。 AB = [[13, 7], [11, 6]]：4 マス × 3 項 = 12 回の掛け算。
7. 順序を入れ替える。 A と B が位置を交換します。B が左へ、A が上へ移り、完成した AB は脇に置かれます。今度は B の行（2 個）と A の列（2 個）が組みます：2 = 2 なので BA は存在し、形は 3×3 です。
8. BA を埋める。 9 マスそれぞれが長さ 2 の内積です：BA = [[6, 4, 7], [1, 2, 3], [11, 6, 11]]、掛け算は 18 回。
9. 比べる。 AB は 2×2 で 12 回、BA は 3×3 で 18 回。同じ 2 つの行列でも、順序を変えると別の表になります。AB ≠ BA。

キャンバスでは、枠で囲まれた 2 本の帯に注目してください。1 本は左の行列の 1 行を横切り、もう 1 本は上の行列の 1 列を縦に貫きます。それぞれの帯から破線のガイドが伸び、両者が出会うマスが計算中のマスです。ステージ上のカウンタは 1 マスごとに n ずつ増え、最後に m·n·p に達します。

計算量

教科書どおりの方法の時間計算量は O(m·n·p) です。m·p 個のマスそれぞれで長さ n の内積を 1 回計算します。n×n の正方行列なら O(n³) で、n を 2 倍にすると仕事量は 8 倍になります。Strassen などのアルゴリズムは掛け算を減らして足し算を増やし、指数を 3 未満に下げますが、実用のライブラリはたいてい素朴な方法を、ハードウェアに合わせたブロック化とベクトル化で動かしています。GPU や TPU がこれを速く計算できるのは、演算がとても規則的だからです。互いに独立した何千もの内積があり、分岐がありません。

積の順序はコストも変えます。デフォルトの入力では AB が 12 回、BA が 18 回です。共通の内側のサイズが 3 から 2 に減る一方で、出力が 4 マスから 9 マスに増えるからです。ABC のような連鎖では、括弧の付け方で答えは変わらなくても総仕事量が変わり、最適な付け方を選ぶのは動的計画法の古典問題です。日常的に使える形にすると「細い側から先に掛ける」です。n×n の行列 A、B とベクトル v では、A(Bv) は掛け算 2n² 回、(AB)v は n³ + n² 回かかります。

境界ケース

• 内側のサイズが合わない。 A (2×3) × B (2×2) は 3 個の行と 2 個の列を組むことになり、3 番目に相手がいないので AB は存在しません。順序を逆にした B (2×2) × A (2×3) は計算でき、2×3 になります。「形状エラー」プリセットで両方を確認できます。
• バッチを層に通す。 X (4×3) × W (3×2) は 4 つの入力 × 2 つのスコアです。WX は 2 = 4 が必要なので失敗します。オペランドの順序を間違えたときに PyTorch が出す mat1 and mat2 shapes cannot be multiplied がこれです。
• 行 × 列と列 × 行。 1×3 の行 × 3×1 の列はただ 1 つの数、つまり内積です（「行 × 列」プリセットでは 13）。同じベクトルを逆の順で掛けると 3×3 の表、すなわち外積になり、掛け算 9 回で足し算はありません。
• 同じ形でも違う。 A = [[1, 2], [3, 4]] と入れ替え行列 B = [[0, 1], [1, 0]] では、AB は A の列を、BA は A の行を入れ替えます。どちらも 2×2 で掛け算 8 回ですが、すべてのマスが異なります。
• 可換な組。 AB と BA が本当に等しい場合（B = I、B = A、あるいは 1×1 どうし）、比較のビートはそのとおりに伝え、違うとは言いません。

よくある間違い

• 成分ごとに掛ける。 NumPy の A * B は成分ごとの掛け算で、形が違ってもブロードキャスト可能なら計算できます。同じ形ならアダマール積です。行列の積は A @ B です。
• 行と行を組む。 A の第 i 行と B の第 j 行から C[i][j] を作ると A·Bᵀ になり、A と B の列数が同じである必要があります。実在する演算です（注意機構の QKᵀ がまさにこれ）が、AB ではありません。
• AB = BA と思い込む。 積の順序を入れ替えると、形がたまたま許しても結果は黙って変わります。数式の順序を守り、転置したいときは明示的に書きましょう。
• 確かめるサイズを間違える。 一致すべきなのは内側のサイズ、つまり A の列数と B の行数です。外側（A の行数と B の列数）を比べてしまうのは、転置 1 つ分ずれたよくあるバグです。
• カウンタを足し算の回数と読む。 長さ n のマスには掛け算が n 回、足し算は n − 1 回しか要りません。キャンバスが数えているのは掛け算で、合計 m·n·p 回です。