-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathatomic-learning-graph.opml
More file actions
48 lines (48 loc) · 211 KB
/
Copy pathatomic-learning-graph.opml
File metadata and controls
48 lines (48 loc) · 211 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
<?xml version="1.0" encoding="UTF-8"?>
<opml version="2.0">
<head>
<title>Atomic Learning Graph</title>
</head>
<body>
<outline text="Atomic Learning Graph" _note="Open this course in Tinderbox, choose Concepts in Map view, and follow the connected concept notes in learning order." ALGKind="course" ALGFormatVersion="2" ALGGoalId="self-attention" ALGPresentation="styled-one-shot" Color="#264653" Shape="rounded" Badge="point.3.connected.trianglepath.dotted" Width="8" Height="3">
<outline text="Prototypes" ALGKind="container" Prototype="ALG Container" Color="#264653" Shape="rounded" Badge="folder" Width="7" Height="3" BorderColor="#264653" Xpos="32" Ypos="0" ALGXpos="32" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}">
<outline text="ALG Concept" _note="Presentation prototype for grounded learning concepts." ALGKind="prototype" IsPrototype="true" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="0" Ypos="0" ALGXpos="0" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="ALG Goal" _note="Presentation prototype for the selected learning goal." ALGKind="prototype" IsPrototype="true" Prototype="ALG Concept" Color="#E76F51" Shape="rounded" Badge="star" Width="5" Height="2.5" BorderColor="#264653" Xpos="6.5" Ypos="0" ALGXpos="6.5" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="ALG Source" _note="Presentation prototype for licensed source records." ALGKind="prototype" IsPrototype="true" Color="#7CB7C9" Shape="rounded" Badge="doc.text" Width="6" Height="2.5" BorderColor="#264653" Xpos="13" Ypos="0" ALGXpos="13" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="ALG Edge" _note="Presentation prototype for canonical relationship records." ALGKind="prototype" IsPrototype="true" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="19.5" Ypos="0" ALGXpos="19.5" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="ALG Guide" _note="Presentation prototype for explanatory guide notes." ALGKind="prototype" IsPrototype="true" Color="#8E7DBE" Shape="rounded" Badge="info.circle" Width="7" Height="3" BorderColor="#264653" Xpos="26" Ypos="0" ALGXpos="26" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="ALG Container" _note="Presentation prototype for course containers." ALGKind="prototype" IsPrototype="true" Color="#264653" Shape="rounded" Badge="folder" Width="7" Height="3" BorderColor="#264653" Xpos="32.5" Ypos="0" ALGXpos="32.5" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
</outline>
<outline text="Read Me" _note="Atomic Learning Graph for Tinderbox This is a ready-to-use visual course. Double-click atomic-learning-graph.tbx to open it in Tinderbox, then open Concepts in Map view and follow the connected notes. To use the portable copy instead, open atomic-learning-graph.opml in Tinderbox once; its map and styling are applied during import. Open Concepts in Map view to explore the course. Note names are human-facing titles; ALGId retains each stable graph key. Sources retain the complete licensed source text. Edges retain every canonical relation from data/graph.json. This OPML is a deterministic, offline, presentation-ready projection of the committed graph. Its opinionated prototypes, colors, badges, dimensions, and prerequisite-layer layout are applied by Tinderbox during the same import. It makes no model or network call and is never an authority over data/graph.json." ALGKind="readme" Prototype="ALG Guide" Color="#8E7DBE" Shape="rounded" Badge="info.circle" Width="7" Height="3" BorderColor="#264653" Xpos="0" Ypos="0" ALGXpos="0" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}"/>
<outline text="Concepts" ALGKind="container" Prototype="ALG Container" Color="#264653" Shape="rounded" Badge="folder" Width="7" Height="3" BorderColor="#264653" Xpos="8" Ypos="0" ALGXpos="8" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}">
<outline text="Vectors" _note="A vector is a fixed-length array whose elements are scalars. Lesson: Keeping a Fixed List of Numbers Together Step 1 (core) A vector lets you keep several related real-world measurements together, such as a person’s income and employment length. Source: d2l-linear-algebra Quoted passage: When vectors represent examples from real-world datasets, their values hold some real-world significance. Step 2 (core) A vector is a list with a set number of slots, and each slot holds one ordinary number, called a scalar. Source: d2l-linear-algebra Quoted passage: For current purposes, you can think of a vector as a fixed-length array of scalars. Step 3 (core) Take the vector [4, 7, 2]. It has three elements, and its second element is 7, so we can write x₂ = 7. Source: d2l-linear-algebra Quoted passage: For example, $x_2$ denotes the second element of $\mathbf{x}$. Step 4 (deep) Picture a vector as a card with labeled boxes: one box might hold income, another employment length, and another the number of earlier loan defaults. Source: d2l-linear-algebra Quoted passage: For example, if we were training a model to predict the risk of a loan defaulting, we might associate each applicant with a vector whose components correspond to quantities like their income, length of employment, or number of previous defaults. Step 5 (core) Precisely, bold x means the whole vector, while x₁ through xₙ mean its individual numbers; n is the vector’s fixed number of elements. Source: d2l-linear-algebra Quoted passage: Here $x_1, \ldots, x_n$ are elements of the vector. Concept source receipt Source: d2l-linear-algebra For current purposes, you can think of a vector as a fixed-length array of scalars. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="vectors" ALGTitle="Vectors" ALGSourceId="d2l-linear-algebra" ALGQuotedText="For current purposes, you can think of a vector as a fixed-length array of scalars." ALGTags="linear algebra;vectors" ALGPrerequisites="" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="A vector is a fixed-length array whose elements are scalars. Lesson: Keeping a Fixed List of Numbers Together Step 1 (core) A vector lets you keep several related real-world measurements together, such as a person’s income and employment length. Source: d2l-linear-algebra Quoted passage: When vectors represent examples from real-world datasets, their values hold some real-world significance. Step 2 (core) A vector is a list with a set number of slots, and each slot holds one ordinary number, called a scalar. Source: d2l-linear-algebra Quoted passage: For current purposes, you can think of a vector as a fixed-length array of scalars. Step 3 (core) Take the vector [4, 7, 2]. It has three elements, and its second element is 7, so we can write x₂ = 7. Source: d2l-linear-algebra Quoted passage: For example, $x_2$ denotes the second element of $\mathbf{x}$. Step 4 (deep) Picture a vector as a card with labeled boxes: one box might hold income, another employment length, and another the number of earlier loan defaults. Source: d2l-linear-algebra Quoted passage: For example, if we were training a model to predict the risk of a loan defaulting, we might associate each applicant with a vector whose components correspond to quantities like their income, length of employment, or number of previous defaults. Step 5 (core) Precisely, bold x means the whole vector, while x₁ through xₙ mean its individual numbers; n is the vector’s fixed number of elements. Source: d2l-linear-algebra Quoted passage: Here $x_1, \ldots, x_n$ are elements of the vector. Concept source receipt Source: d2l-linear-algebra For current purposes, you can think of a vector as a fixed-length array of scalars. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="2" Ypos="5" ALGXpos="2" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;linkTo(find($ALGKind=="concept" & $ALGId=="dot-product"),"prereq");linkTo(find($ALGKind=="concept" & $ALGId=="vector-norm"),"prereq");$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Dot Product" _note="The dot product sums the products of corresponding elements in two vectors. Lesson: Pair, Multiply, Then Add Step 1 (core) A dot product lets you combine two matching lists of numbers into one number, and it is useful in many different settings. Source: d2l-linear-algebra Quoted passage: Dot products are useful in a wide range of contexts. Step 2 (core) A dot product pairs numbers in the same position, multiplies each pair, and then adds all the results. Source: d2l-linear-algebra Quoted passage: The dot product of two vectors is a sum over the products of the elements at the same position Step 3 (core) For the vectors [2, 3] and [4, 5], multiply matching numbers: 2 × 4 = 8 and 3 × 5 = 15. Then add: 8 + 15 = 23, so the dot product is 23. Source: d2l-linear-algebra Quoted passage: we can calculate the dot product of two vectors by performing an elementwise multiplication followed by a sum Step 4 (deep) Think of a dot product as a weighted score: one list holds values, while the matching list holds weights--numbers showing how much each value counts. Source: d2l-linear-algebra Quoted passage: the weighted sum of the values in $\mathbf{x}$ according to the weights $\mathbf{w}$ could be expressed as the dot product $\mathbf{x}^\top \mathbf{w}$. Step 5 (core) Precisely, let x and y name two vectors with d positions, and let xᵢ and yᵢ mean the numbers at position i. Their dot product is xᵀy = ∑ᵢ₌₁ᵈ xᵢyᵢ, meaning multiply the matching numbers from position 1 through position d and add those products. Source: d2l-linear-algebra Quoted passage: Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. Step 6 (deep) A matrix–vector product uses this idea repeatedly: each output number is the dot product of one matrix row and the input vector. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Concept source receipt Source: d2l-linear-algebra Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="dot-product" ALGTitle="Dot Product" ALGSourceId="d2l-linear-algebra" ALGQuotedText="Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$." ALGTags="dot product;linear algebra" ALGPrerequisites="vectors" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="The dot product sums the products of corresponding elements in two vectors. Lesson: Pair, Multiply, Then Add Step 1 (core) A dot product lets you combine two matching lists of numbers into one number, and it is useful in many different settings. Source: d2l-linear-algebra Quoted passage: Dot products are useful in a wide range of contexts. Step 2 (core) A dot product pairs numbers in the same position, multiplies each pair, and then adds all the results. Source: d2l-linear-algebra Quoted passage: The dot product of two vectors is a sum over the products of the elements at the same position Step 3 (core) For the vectors [2, 3] and [4, 5], multiply matching numbers: 2 × 4 = 8 and 3 × 5 = 15. Then add: 8 + 15 = 23, so the dot product is 23. Source: d2l-linear-algebra Quoted passage: we can calculate the dot product of two vectors by performing an elementwise multiplication followed by a sum Step 4 (deep) Think of a dot product as a weighted score: one list holds values, while the matching list holds weights—numbers showing how much each value counts. Source: d2l-linear-algebra Quoted passage: the weighted sum of the values in $\mathbf{x}$ according to the weights $\mathbf{w}$ could be expressed as the dot product $\mathbf{x}^\top \mathbf{w}$. Step 5 (core) Precisely, let x and y name two vectors with d positions, and let xᵢ and yᵢ mean the numbers at position i. Their dot product is xᵀy = ∑ᵢ₌₁ᵈ xᵢyᵢ, meaning multiply the matching numbers from position 1 through position d and add those products. Source: d2l-linear-algebra Quoted passage: Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. Step 6 (deep) A matrix–vector product uses this idea repeatedly: each output number is the dot product of one matrix row and the input vector. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Concept source receipt Source: d2l-linear-algebra Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="8" Ypos="5" ALGXpos="8" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;linkTo(find($ALGKind=="concept" & $ALGId=="matrix-vector-product"),"prereq");linkTo(find($ALGKind=="concept" & $ALGId=="softmax"),"prereq");$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Matrix–Vector Product" _note="A matrix–vector product produces a vector whose elements are dot products between matrix rows and the input vector. Lesson: Turning Matrix Rows into a New Number List Step 1 (core) This operation lets you turn one vector into another vector, possibly with a different length. Source: d2l-linear-algebra Quoted passage: We can think of multiplication with a matrix $\mathbf{A}\in \mathbb{R}^{m \times n}$ as a transformation that projects vectors from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$. Step 2 (core) A matrix is a rectangle of numbers. To multiply it by a vector, take the dot product of each horizontal line, called a row, with the vector; those answers form the new vector. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 3 (core) Try the matrix with rows [2, 1] and [3, 4], and the vector [5, 2]. The first answer is 2×5 + 1×2 = 12, and the second is 3×5 + 4×2 = 23, so the result is [12, 23]. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 4 (deep) Picture each row as a separate worker doing the same job with the input vector; each worker produces one number for the output vector. Source: d2l-linear-algebra Quoted passage: whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 5 (core) Formally, let the matrix be $\mathbf{A}$, the input vector be $\mathbf{x}$, and the number of rows be $m$. Then $\mathbf{A}\mathbf{x}$ is a vector with $m$ numbers, and output number $i$ is the dot product of row $i$ with $\mathbf{x}$. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Concept source receipt Source: d2l-linear-algebra The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$: $$ \mathbf{A}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{x} \\ \mathbf{a}^\top_{2} \mathbf{x} \\ \vdots\\ \mathbf{a}^\top_{m} \mathbf{x}\\ \end{bmatrix}. $$ Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="matrix-vector-product" ALGTitle="Matrix–Vector Product" ALGSourceId="d2l-linear-algebra" ALGQuotedText="The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$: $$ \mathbf{A}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{x} \\ \mathbf{a}^\top_{2} \mathbf{x} \\ \vdots\\ \mathbf{a}^\top_{m} \mathbf{x}\\ \end{bmatrix}. $$" ALGTags="linear algebra;matrix-vector multiplication" ALGPrerequisites="dot-product" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="A matrix–vector product produces a vector whose elements are dot products between matrix rows and the input vector. Lesson: Turning Matrix Rows into a New Number List Step 1 (core) This operation lets you turn one vector into another vector, possibly with a different length. Source: d2l-linear-algebra Quoted passage: We can think of multiplication with a matrix $\mathbf{A}\in \mathbb{R}^{m \times n}$ as a transformation that projects vectors from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$. Step 2 (core) A matrix is a rectangle of numbers. To multiply it by a vector, take the dot product of each horizontal line, called a row, with the vector; those answers form the new vector. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 3 (core) Try the matrix with rows [2, 1] and [3, 4], and the vector [5, 2]. The first answer is 2×5 + 1×2 = 12, and the second is 3×5 + 4×2 = 23, so the result is [12, 23]. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 4 (deep) Picture each row as a separate worker doing the same job with the input vector; each worker produces one number for the output vector. Source: d2l-linear-algebra Quoted passage: whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Step 5 (core) Formally, let the matrix be $\mathbf{A}$, the input vector be $\mathbf{x}$, and the number of rows be $m$. Then $\mathbf{A}\mathbf{x}$ is a vector with $m$ numbers, and output number $i$ is the dot product of row $i$ with $\mathbf{x}$. Source: d2l-linear-algebra Quoted passage: The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$ Concept source receipt Source: d2l-linear-algebra The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$: $$ \mathbf{A}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{x} \\ \mathbf{a}^\top_{2} \mathbf{x} \\ \vdots\\ \mathbf{a}^\top_{m} \mathbf{x}\\ \end{bmatrix}. $$ Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="14" Ypos="5" ALGXpos="14" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Softmax" _note="Softmax converts model outputs into a normalized probability distribution by exponentiating and dividing by the sum. Lesson: Turning Scores into Chances That Add to One Step 1 (core) Softmax lets you turn a group of raw scores into chances that add up to 1. Source: d2l-softmax-regression Quoted passage: Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Step 2 (core) For each score, softmax first calculates exp(score)--meaning about 2.718 raised to that score--and then divides the result by the total of all such results. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 3 (core) Try scores 0 and 0: exp(0) = 1 for each, their total is 1 + 1 = 2, and softmax gives 1 ÷ 2 = 0.5 for each. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 4 (deep) Picture dividing a whole pie: each transformed score gets a slice equal to its part of the shared total. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 5 (core) Precisely, if o_i means score i, then its softmax result is ŷ_i = exp(o_i) ÷ Σ_j exp(o_j), where Σ_j means “add the transformed results for every score.” Source: d2l-softmax-regression Quoted passage: Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Concept source receipt Source: d2l-softmax-regression Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="softmax" ALGTitle="Softmax" ALGSourceId="d2l-softmax-regression" ALGQuotedText="Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$" ALGTags="classification;probabilities;softmax" ALGPrerequisites="dot-product" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="Softmax converts model outputs into a normalized probability distribution by exponentiating and dividing by the sum. Lesson: Turning Scores into Chances That Add to One Step 1 (core) Softmax lets you turn a group of raw scores into chances that add up to 1. Source: d2l-softmax-regression Quoted passage: Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Step 2 (core) For each score, softmax first calculates exp(score)—meaning about 2.718 raised to that score—and then divides the result by the total of all such results. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 3 (core) Try scores 0 and 0: exp(0) = 1 for each, their total is 1 + 1 = 2, and softmax gives 1 ÷ 2 = 0.5 for each. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 4 (deep) Picture dividing a whole pie: each transformed score gets a slice equal to its part of the shared total. Source: d2l-softmax-regression Quoted passage: \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)} Step 5 (core) Precisely, if o_i means score i, then its softmax result is ŷ_i = exp(o_i) ÷ Σ_j exp(o_j), where Σ_j means “add the transformed results for every score.” Source: d2l-softmax-regression Quoted passage: Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Concept source receipt Source: d2l-softmax-regression Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="14" Ypos="8.5" ALGXpos="14" ALGYpos="8.5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;linkTo(find($ALGKind=="concept" & $ALGId=="qkv"),"prereq");linkTo(find($ALGKind=="concept" & $ALGId=="softmax-ordering"),"prereq");$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Queries, Keys, and Values" _note="Attention uses a query to determine compatibility with keys associated with stored values. Lesson: Matching a Request to Stored Information Step 1 (core) A short request can guide attention over a large set of stored keys and values. Source: d2l-queries-keys-values Quoted passage: the actual "code" for executing on the set of keys and values, namely the query, can be quite concise, even though the space to operate on is significant. Step 2 (core) A query is the request being matched, keys are the items it is compared with, and values are the stored information that attention mixes based on those matches. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Step 3 (core) Suppose two values are 8 and 4, and matching gives them weights of 1/4 and 3/4. Their weighted mix is (1/4 × 8) + (3/4 × 4) = 2 + 3 = 5. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Step 4 (deep) Picture asking a librarian a question: the query is your question, the keys act like book labels, and a larger weight can be viewed as selecting more relevant information. Source: d2l-queries-keys-values Quoted passage: In this case we might interpret large weights as a way for the model to select components of relevance. Step 5 (core) Precisely, the query is written $\mathbf{q}$, each key is $\mathbf{k}_\mathit{i}$, and each value is $\mathbf{v}_\mathit{i}$; attention pooling forms a linear combination, meaning it multiplies each value by its weight and adds the results. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Concept source receipt Source: d2l-queries-keys-values The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="qkv" ALGTitle="Queries, Keys, and Values" ALGSourceId="d2l-queries-keys-values" ALGQuotedText="The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$." ALGTags="attention;keys;queries;values" ALGPrerequisites="softmax" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="Attention uses a query to determine compatibility with keys associated with stored values. Lesson: Matching a Request to Stored Information Step 1 (core) A short request can guide attention over a large set of stored keys and values. Source: d2l-queries-keys-values Quoted passage: the actual "code" for executing on the set of keys and values, namely the query, can be quite concise, even though the space to operate on is significant. Step 2 (core) A query is the request being matched, keys are the items it is compared with, and values are the stored information that attention mixes based on those matches. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Step 3 (core) Suppose two values are 8 and 4, and matching gives them weights of 1/4 and 3/4. Their weighted mix is (1/4 × 8) + (3/4 × 4) = 2 + 3 = 5. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Step 4 (deep) Picture asking a librarian a question: the query is your question, the keys act like book labels, and a larger weight can be viewed as selecting more relevant information. Source: d2l-queries-keys-values Quoted passage: In this case we might interpret large weights as a way for the model to select components of relevance. Step 5 (core) Precisely, the query is written $\mathbf{q}$, each key is $\mathbf{k}_\mathit{i}$, and each value is $\mathbf{v}_\mathit{i}$; attention pooling forms a linear combination, meaning it multiplies each value by its weight and adds the results. Source: d2l-queries-keys-values Quoted passage: The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Concept source receipt Source: d2l-queries-keys-values The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="20" Ypos="5" ALGXpos="20" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;linkTo(find($ALGKind=="concept" & $ALGId=="attention-pooling"),"prereq");linkTo(find($ALGKind=="concept" & $ALGId=="self-attention"),"prereq");$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Attention Pooling" _note="Attention pooling generates a linear combination of values in a key–value database. Lesson: Blending Stored Answers by Relevance Step 1 (core) Attention pooling lets you blend stored values into one useful result. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 2 (core) It makes a linear combination: multiply each stored value by its weight, meaning its assigned share, and then add the results. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 3 (core) Suppose the stored values are 10 and 20, with weights 0.25 and 0.75. The pooled result is 0.25 × 10 + 0.75 × 20 = 2.5 + 15 = 17.5. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 4 (deep) Picture mixing drinks: when every stored value gets the same-sized scoop, attention pooling simply finds their average. Source: d2l-queries-keys-values Quoted passage: All weights are equal, i.e., $\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{1}{m}$ for all $i$. This amounts to averaging across the entire database, also called average pooling in deep learning. Step 5 (core) In the most common deep-learning version, every weight is zero or greater, and all the weights add up to 1. Source: d2l-queries-keys-values Quoted passage: The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ form a convex combination, i.e., $\sum_i \alpha(\mathbf{q}, \mathbf{k}_i) = 1$ and $\alpha(\mathbf{q}, \mathbf{k}_i) \geq 0$ for all $i$. This is the most common setting in deep learning. Concept source receipt Source: d2l-queries-keys-values As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="attention-pooling" ALGTitle="Attention Pooling" ALGSourceId="d2l-queries-keys-values" ALGQuotedText="As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database." ALGTags="attention;pooling" ALGPrerequisites="qkv" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="Attention pooling generates a linear combination of values in a key–value database. Lesson: Blending Stored Answers by Relevance Step 1 (core) Attention pooling lets you blend stored values into one useful result. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 2 (core) It makes a linear combination: multiply each stored value by its weight, meaning its assigned share, and then add the results. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 3 (core) Suppose the stored values are 10 and 20, with weights 0.25 and 0.75. The pooled result is 0.25 × 10 + 0.75 × 20 = 2.5 + 15 = 17.5. Source: d2l-queries-keys-values Quoted passage: As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Step 4 (deep) Picture mixing drinks: when every stored value gets the same-sized scoop, attention pooling simply finds their average. Source: d2l-queries-keys-values Quoted passage: All weights are equal, i.e., $\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{1}{m}$ for all $i$. This amounts to averaging across the entire database, also called average pooling in deep learning. Step 5 (core) In the most common deep-learning version, every weight is zero or greater, and all the weights add up to 1. Source: d2l-queries-keys-values Quoted passage: The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ form a convex combination, i.e., $\sum_i \alpha(\mathbf{q}, \mathbf{k}_i) = 1$ and $\alpha(\mathbf{q}, \mathbf{k}_i) \geq 0$ for all $i$. This is the most common setting in deep learning. Concept source receipt Source: d2l-queries-keys-values As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="26" Ypos="5" ALGXpos="26" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Self-Attention" _note="Self-attention lets every token attend to every other token in the same sequence. Lesson: Each Item Looks Across Its Own Sequence Step 1 (core) Self-attention lets each token--one item in a sequence, such as a word--use information from every other token in that sequence. Source: d2l-self-attention Quoted passage: Because every token is attending to each other token Step 2 (core) It is called “self-attention” because the tokens attend to, or consider, other tokens from their own sequence when producing results. Source: d2l-self-attention Quoted passage: such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . Step 3 (core) Suppose three tokens have the simple number values 2, 4, and 6. The first token might pay 50% attention to itself, 30% to the second, and 20% to the third: 0.5 × 2 + 0.3 × 4 + 0.2 × 6 = 1 + 1.2 + 1.2 = 3.4. A different token, with different attention weights, gets a different result -- that is what makes it attention, not averaging. Source: d2l-self-attention Quoted passage: its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ according to the definition of attention pooling in . Step 4 (deep) Picture a group discussion where every person can listen to every other person before giving an answer; likewise, every token can attend to every other token. Source: d2l-self-attention Quoted passage: every token is attending to each other token Step 5 (core) Precisely, if the inputs are numbered x₁ through xₙ, self-attention produces equally many outputs, y₁ through yₙ; each output yᵢ is made by a rule f that can use xᵢ and all input pairs from x₁ through xₙ. Source: d2l-self-attention Quoted passage: Given a sequence of input tokens $\mathbf{x}_1, \ldots, \mathbf{x}_n$ where any $\mathbf{x}_i \in \mathbb{R}^d$ ($1 \leq i \leq n$), its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ Step 6 (deep) Self-attention can also use added information about where each token appears in the sequence. Source: d2l-self-attention Quoted passage: we will discuss sequence encoding using self-attention, including using additional information for the sequence order. Concept source receipt Source: d2l-self-attention Because every token is attending to each other token (unlike the case where decoder steps attend to encoder steps), such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="self-attention" ALGTitle="Self-Attention" ALGSourceId="d2l-self-attention" ALGQuotedText="Because every token is attending to each other token (unlike the case where decoder steps attend to encoder steps), such architectures are typically described as self-attention models , and elsewhere described as intra-attention model ." ALGTags="attention;self-attention;sequences" ALGPrerequisites="qkv" ALGMethods="" ALGRelated="" ALGIsGoal="true" ALGExactText="Self-attention lets every token attend to every other token in the same sequence. Lesson: Each Item Looks Across Its Own Sequence Step 1 (core) Self-attention lets each token—one item in a sequence, such as a word—use information from every other token in that sequence. Source: d2l-self-attention Quoted passage: Because every token is attending to each other token Step 2 (core) It is called “self-attention” because the tokens attend to, or consider, other tokens from their own sequence when producing results. Source: d2l-self-attention Quoted passage: such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . Step 3 (core) Suppose three tokens have the simple number values 2, 4, and 6. The first token might pay 50% attention to itself, 30% to the second, and 20% to the third: 0.5 × 2 + 0.3 × 4 + 0.2 × 6 = 1 + 1.2 + 1.2 = 3.4. A different token, with different attention weights, gets a different result — that is what makes it attention, not averaging. Source: d2l-self-attention Quoted passage: its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ according to the definition of attention pooling in . Step 4 (deep) Picture a group discussion where every person can listen to every other person before giving an answer; likewise, every token can attend to every other token. Source: d2l-self-attention Quoted passage: every token is attending to each other token Step 5 (core) Precisely, if the inputs are numbered x₁ through xₙ, self-attention produces equally many outputs, y₁ through yₙ; each output yᵢ is made by a rule f that can use xᵢ and all input pairs from x₁ through xₙ. Source: d2l-self-attention Quoted passage: Given a sequence of input tokens $\mathbf{x}_1, \ldots, \mathbf{x}_n$ where any $\mathbf{x}_i \in \mathbb{R}^d$ ($1 \leq i \leq n$), its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ Step 6 (deep) Self-attention can also use added information about where each token appears in the sequence. Source: d2l-self-attention Quoted passage: we will discuss sequence encoding using self-attention, including using additional information for the sequence order. Concept source receipt Source: d2l-self-attention Because every token is attending to each other token (unlike the case where decoder steps attend to encoder steps), such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Goal" Color="#E76F51" Shape="rounded" Badge="star" Width="5" Height="2.5" BorderColor="#264653" Xpos="26" Ypos="8.5" ALGXpos="26" ALGYpos="8.5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;linkTo(find($ALGKind=="concept" & $ALGId=="positional-encoding"),"prereq");$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Positional Encoding" _note="Positional encodings provide token-order information to models as additional token-associated inputs. Lesson: Giving Each Token Its Place in Line Step 1 (core) Positional encoding helps a model keep track of the order of tokens, where a token is one piece of a sequence, such as a word. Source: d2l-self-attention Quoted passage: The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. Step 2 (core) A positional encoding is extra position information attached to each token. It may be learned during training or fixed ahead of time. Source: d2l-self-attention Quoted passage: These inputs are called positional encodings, and they can either be learned or fixed a priori. Step 3 (core) Suppose a token has the number-list [4, 2], and its position has the number-list [1, 3]. Add matching entries: [4 + 1, 2 + 3] = [5, 5]. Source: d2l-self-attention Quoted passage: The positional encoding outputs $\mathbf{X} + \mathbf{P}$ Step 4 (deep) Picture a seating chart: each row marks one place in the sequence, while each column stores one kind of position number. Source: d2l-self-attention Quoted passage: In the positional embedding matrix $\mathbf{P}$, rows correspond to positions within a sequence and columns represent different positional encoding dimensions. Step 5 (core) Precisely, let X be the grid of token numbers and P be an equally shaped grid of position numbers. The model receives X + P, found by adding numbers in matching places. Source: d2l-self-attention Quoted passage: The positional encoding outputs $\mathbf{X} + \mathbf{P}$ using a positional embedding matrix $\mathbf{P} \in \mathbb{R}^{n \times d}$ of the same shape Concept source receipt Source: d2l-self-attention The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="positional-encoding" ALGTitle="Positional Encoding" ALGSourceId="d2l-self-attention" ALGQuotedText="The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token." ALGTags="positional encoding;self-attention;sequence order" ALGPrerequisites="self-attention" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="Positional encodings provide token-order information to models as additional token-associated inputs. Lesson: Giving Each Token Its Place in Line Step 1 (core) Positional encoding helps a model keep track of the order of tokens, where a token is one piece of a sequence, such as a word. Source: d2l-self-attention Quoted passage: The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. Step 2 (core) A positional encoding is extra position information attached to each token. It may be learned during training or fixed ahead of time. Source: d2l-self-attention Quoted passage: These inputs are called positional encodings, and they can either be learned or fixed a priori. Step 3 (core) Suppose a token has the number-list [4, 2], and its position has the number-list [1, 3]. Add matching entries: [4 + 1, 2 + 3] = [5, 5]. Source: d2l-self-attention Quoted passage: The positional encoding outputs $\mathbf{X} + \mathbf{P}$ Step 4 (deep) Picture a seating chart: each row marks one place in the sequence, while each column stores one kind of position number. Source: d2l-self-attention Quoted passage: In the positional embedding matrix $\mathbf{P}$, rows correspond to positions within a sequence and columns represent different positional encoding dimensions. Step 5 (core) Precisely, let X be the grid of token numbers and P be an equally shaped grid of position numbers. The model receives X + P, found by adding numbers in matching places. Source: d2l-self-attention Quoted passage: The positional encoding outputs $\mathbf{X} + \mathbf{P}$ using a positional embedding matrix $\mathbf{P} \in \mathbb{R}^{n \times d}$ of the same shape Concept source receipt Source: d2l-self-attention The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="32" Ypos="5" ALGXpos="32" ALGYpos="5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Softmax Preserves Ordering" _note="Softmax preserves the ordering of its inputs, so the largest input identifies the highest-probability class. Lesson: The Biggest Score Stays the Winner Step 1 (core) You can find which category gets the highest probability without doing the softmax calculation. Source: d2l-softmax-regression Quoted passage: we do not need to compute the softmax to determine which class has been assigned the highest probability. Step 2 (core) Softmax turns scores into probabilities, and it preserves their ordering: a bigger score still leads to a bigger probability. Source: d2l-softmax-regression Quoted passage: the softmax operation preserves the ordering among its arguments Step 3 (core) Suppose three categories have scores 2, 5, and 1. Since 5 > 2 > 1, the second category will have the highest probability after softmax; you do not need to calculate the probabilities. Source: d2l-softmax-regression Quoted passage: because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Step 4 (deep) Picture a race in which softmax changes everyone’s finish time but not their finishing order. The score in first place remains the probability in first place. Source: d2l-softmax-regression Quoted passage: the softmax operation preserves the ordering among its arguments Step 5 (core) Formally, “argmax” means the position of the largest number, ŷⱼ is category j’s probability, and oⱼ is its original score. The equation says that the largest probability and the largest original score occur at the same position. Source: d2l-softmax-regression Quoted passage: Thus, $$ \operatorname*{argmax}_j \hat y_j = \operatorname*{argmax}_j o_j. $$ Concept source receipt Source: d2l-softmax-regression Moreover, because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="softmax-ordering" ALGTitle="Softmax Preserves Ordering" ALGSourceId="d2l-softmax-regression" ALGQuotedText="Moreover, because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability." ALGTags="classification;ordering;softmax" ALGPrerequisites="softmax" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="Softmax preserves the ordering of its inputs, so the largest input identifies the highest-probability class. Lesson: The Biggest Score Stays the Winner Step 1 (core) You can find which category gets the highest probability without doing the softmax calculation. Source: d2l-softmax-regression Quoted passage: we do not need to compute the softmax to determine which class has been assigned the highest probability. Step 2 (core) Softmax turns scores into probabilities, and it preserves their ordering: a bigger score still leads to a bigger probability. Source: d2l-softmax-regression Quoted passage: the softmax operation preserves the ordering among its arguments Step 3 (core) Suppose three categories have scores 2, 5, and 1. Since 5 > 2 > 1, the second category will have the highest probability after softmax; you do not need to calculate the probabilities. Source: d2l-softmax-regression Quoted passage: because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Step 4 (deep) Picture a race in which softmax changes everyone’s finish time but not their finishing order. The score in first place remains the probability in first place. Source: d2l-softmax-regression Quoted passage: the softmax operation preserves the ordering among its arguments Step 5 (core) Formally, “argmax” means the position of the largest number, ŷⱼ is category j’s probability, and oⱼ is its original score. The equation says that the largest probability and the largest original score occur at the same position. Source: d2l-softmax-regression Quoted passage: Thus, $$ \operatorname*{argmax}_j \hat y_j = \operatorname*{argmax}_j o_j. $$ Concept source receipt Source: d2l-softmax-regression Moreover, because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="20" Ypos="8.5" ALGXpos="20" ALGYpos="8.5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
<outline text="Vector Norm" _note="A vector norm measures the magnitude or size of a vector. Lesson: Turning a Number List into Its Length Step 1 (core) A norm gives you one number that tells you how big a vector is. Source: d2l-linear-algebra Quoted passage: Informally, the norm of a vector tells us how big it is. Step 2 (core) A norm is a rule that takes a vector--a fixed list of numbers--and returns a scalar, meaning one ordinary number. Source: d2l-linear-algebra Quoted passage: A norm is a function $\| \cdot \|$ that maps a vector to a scalar Step 3 (core) For the vector [3, 4], square each number, add, and take the square root: 3² + 4² = 9 + 16 = 25, and √25 = 5. So its ℓ₂ norm is 5. Source: d2l-linear-algebra Quoted passage: The Euclidean norm that we all learned in elementary school geometry when calculating the hypotenuse of a right triangle is the square root of the sum of squares of a vector's elements. Step 4 (deep) Picture walking 3 blocks east and 4 blocks north: the ℓ₂ norm is like the straight-line length from where you started to where you ended. Source: d2l-linear-algebra Quoted passage: For instance, the $\ell_2$ norm measures the (Euclidean) length of a vector. Step 5 (core) Precisely, if xᵢ means the number in position i and n means how many numbers there are, then ‖x‖₂ means: square all n numbers, add the squares, and take the square root. Source: d2l-linear-algebra Quoted passage: Formally, this is called the $\ell_2$ norm and expressed as ($$\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2}.$$) Concept source receipt Source: d2l-linear-algebra Informally, the norm of a vector tells us how big it is. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." ALGKind="concept" ALGId="vector-norm" ALGTitle="Vector Norm" ALGSourceId="d2l-linear-algebra" ALGQuotedText="Informally, the norm of a vector tells us how big it is." ALGTags="linear algebra;norms" ALGPrerequisites="vectors" ALGMethods="" ALGRelated="" ALGIsGoal="false" ALGExactText="A vector norm measures the magnitude or size of a vector. Lesson: Turning a Number List into Its Length Step 1 (core) A norm gives you one number that tells you how big a vector is. Source: d2l-linear-algebra Quoted passage: Informally, the norm of a vector tells us how big it is. Step 2 (core) A norm is a rule that takes a vector—a fixed list of numbers—and returns a scalar, meaning one ordinary number. Source: d2l-linear-algebra Quoted passage: A norm is a function $\| \cdot \|$ that maps a vector to a scalar Step 3 (core) For the vector [3, 4], square each number, add, and take the square root: 3² + 4² = 9 + 16 = 25, and √25 = 5. So its ℓ₂ norm is 5. Source: d2l-linear-algebra Quoted passage: The Euclidean norm that we all learned in elementary school geometry when calculating the hypotenuse of a right triangle is the square root of the sum of squares of a vector's elements. Step 4 (deep) Picture walking 3 blocks east and 4 blocks north: the ℓ₂ norm is like the straight-line length from where you started to where you ended. Source: d2l-linear-algebra Quoted passage: For instance, the $\ell_2$ norm measures the (Euclidean) length of a vector. Step 5 (core) Precisely, if xᵢ means the number in position i and n means how many numbers there are, then ‖x‖₂ means: square all n numbers, add the squares, and take the square root. Source: d2l-linear-algebra Quoted passage: Formally, this is called the $\ell_2$ norm and expressed as ($$\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2}.$$) Concept source receipt Source: d2l-linear-algebra Informally, the norm of a vector tells us how big it is. Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/)." Prototype="ALG Concept" Color="#E9C46A" Shape="rounded" Badge="book" Width="5" Height="2.5" BorderColor="#264653" Xpos="8" Ypos="8.5" ALGXpos="8" ALGYpos="8.5" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGSourceId;ALGKind;ALGIsGoal"/>
</outline>
<outline text="Sources" ALGKind="container" Prototype="ALG Container" Color="#264653" Shape="rounded" Badge="folder" Width="7" Height="3" BorderColor="#264653" Xpos="16" Ypos="0" ALGXpos="16" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}">
<outline text="Dive into Deep Learning — 2.3 Linear Algebra" _note="Dive into Deep Learning -- 2.3 Linear Algebra Source ID: d2l-linear-algebra Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_preliminaries/linear-algebra.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Linear Algebra By now, we can load datasets into tensors and manipulate these tensors with basic mathematical operations. To start building sophisticated models, we will also need a few tools from linear algebra. This section offers a gentle introduction to the most essential concepts, starting from scalar arithmetic and ramping up to matrix multiplication. ## Scalars Most everyday mathematics consists of manipulating numbers one at a time. Formally, we call these values scalars. For example, the temperature in Palo Alto is a balmy $72$ degrees Fahrenheit. If you wanted to convert the temperature to Celsius you would evaluate the expression $c = \frac{5}{9}(f - 32)$, setting $f$ to $72$. In this equation, the values $5$, $9$, and $32$ are constant scalars. The variables $c$ and $f$ in general represent unknown scalars. We denote scalars by ordinary lower-cased letters (e.g., $x$, $y$, and $z$) and the space of all (continuous) real-valued scalars by $\mathbb{R}$. For expedience, we will skip past rigorous definitions of spaces: just remember that the expression $x \in \mathbb{R}$ is a formal way to say that $x$ is a real-valued scalar. The symbol $\in$ (pronounced "in") denotes membership in a set. For example, $x, y \in \{0, 1\}$ indicates that $x$ and $y$ are variables that can only take values $0$ or $1$. (Scalars are implemented as tensors that contain only one element.) Below, we assign two scalars and perform the familiar addition, multiplication, division, and exponentiation operations. ## Vectors For current purposes, you can think of a vector as a fixed-length array of scalars. As with their code counterparts, we call these scalars the elements of the vector (synonyms include entries and components). When vectors represent examples from real-world datasets, their values hold some real-world significance. For example, if we were training a model to predict the risk of a loan defaulting, we might associate each applicant with a vector whose components correspond to quantities like their income, length of employment, or number of previous defaults. If we were studying the risk of heart attack, each vector might represent a patient and its components might correspond to their most recent vital signs, cholesterol levels, minutes of exercise per day, etc. We denote vectors by bold lowercase letters, (e.g., $\mathbf{x}$, $\mathbf{y}$, and $\mathbf{z}$). Vectors are implemented as $1^{\textrm{st}}$-order tensors. In general, such tensors can have arbitrary lengths, subject to memory limitations. Caution: in Python, as in most programming languages, vector indices start at $0$, also known as zero-based indexing, whereas in linear algebra subscripts begin at $1$ (one-based indexing). We can refer to an element of a vector by using a subscript. For example, $x_2$ denotes the second element of $\mathbf{x}$. Since $x_2$ is a scalar, we do not bold it. By default, we visualize vectors by stacking their elements vertically. $$\mathbf{x} =\begin{bmatrix}x_{1} \\ \vdots \\x_{n}\end{bmatrix},$$ Here $x_1, \ldots, x_n$ are elements of the vector. Later on, we will distinguish between such column vectors and row vectors whose elements are stacked horizontally. Recall that we access a tensor's elements via indexing. To indicate that a vector contains $n$ elements, we write $\mathbf{x} \in \mathbb{R}^n$. Formally, we call $n$ the dimensionality of the vector. In code, this corresponds to the tensor's length, accessible via Python's built-in len function. We can also access the length via the shape attribute. The shape is a tuple that indicates a tensor's length along each axis. (Tensors with just one axis have shapes with just one element.) Oftentimes, the word "dimension" gets overloaded to mean both the number of axes and the length along a particular axis. To avoid this confusion, we use order to refer to the number of axes and dimensionality exclusively to refer to the number of components. ## Matrices Just as scalars are $0^{\textrm{th}}$-order tensors and vectors are $1^{\textrm{st}}$-order tensors, matrices are $2^{\textrm{nd}}$-order tensors. We denote matrices by bold capital letters (e.g., $\mathbf{X}$, $\mathbf{Y}$, and $\mathbf{Z}$), and represent them in code by tensors with two axes. The expression $\mathbf{A} \in \mathbb{R}^{m \times n}$ indicates that a matrix $\mathbf{A}$ contains $m \times n$ real-valued scalars, arranged as $m$ rows and $n$ columns. When $m = n$, we say that a matrix is square. Visually, we can illustrate any matrix as a table. To refer to an individual element, we subscript both the row and column indices, e.g., $a_{ij}$ is the value that belongs to $\mathbf{A}$'s $i^{\textrm{th}}$ row and $j^{\textrm{th}}$ column: $$\mathbf{A}=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{bmatrix}.$$ In code, we represent a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ by a $2^{\textrm{nd}}$-order tensor with shape ($m$, $n$). We can convert any appropriately sized $m \times n$ tensor into an $m \times n$ matrix by passing the desired shape to reshape: Sometimes we want to flip the axes. When we exchange a matrix's rows and columns, the result is called its transpose. Formally, we signify a matrix $\mathbf{A}$'s transpose by $\mathbf{A}^\top$ and if $\mathbf{B} = \mathbf{A}^\top$, then $b_{ij} = a_{ji}$ for all $i$ and $j$. Thus, the transpose of an $m \times n$ matrix is an $n \times m$ matrix: $$ \mathbf{A}^\top = \begin{bmatrix} a_{11} & a_{21} & \dots & a_{m1} \\ a_{12} & a_{22} & \dots & a_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \dots & a_{mn} \end{bmatrix}. $$ In code, we can access any (matrix's transpose) as follows: Symmetric matrices are the subset of square matrices that are equal to their own transposes: $\mathbf{A} = \mathbf{A}^\top$. The following matrix is symmetric: Matrices are useful for representing datasets. Typically, rows correspond to individual records and columns correspond to distinct attributes. ## Tensors While you can go far in your machine learning journey with only scalars, vectors, and matrices, eventually you may need to work with higher-order tensors. Tensors (give us a generic way of describing extensions to $n^{\textrm{th}}$-order arrays.) We call software objects of the tensor class "tensors" precisely because they too can have arbitrary numbers of axes. While it may be confusing to use the word tensor for both the mathematical object and its realization in code, our meaning should usually be clear from context. We denote general tensors by capital letters with a special font face (e.g., $\mathsf{X}$, $\mathsf{Y}$, and $\mathsf{Z}$) and their indexing mechanism (e.g., $x_{ijk}$ and $[\mathsf{X}]_{1, 2i-1, 3}$) follows naturally from that of matrices. Tensors will become more important when we start working with images. Each image arrives as a $3^{\textrm{rd}}$-order tensor with axes corresponding to the height, width, and channel. At each spatial location, the intensities of each color (red, green, and blue) are stacked along the channel. Furthermore, a collection of images is represented in code by a $4^{\textrm{th}}$-order tensor, where distinct images are indexed along the first axis. Higher-order tensors are constructed, as were vectors and matrices, by growing the number of shape components. ## Basic Properties of Tensor Arithmetic Scalars, vectors, matrices, and higher-order tensors all have some handy properties. For example, elementwise operations produce outputs that have the same shape as their operands. The elementwise product of two matrices is called their Hadamard product (denoted $\odot$). We can spell out the entries of the Hadamard product of two matrices $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m \times n}$: $$ \mathbf{A} \odot \mathbf{B} = \begin{bmatrix} a_{11} b_{11} & a_{12} b_{12} & \dots & a_{1n} b_{1n} \\ a_{21} b_{21} & a_{22} b_{22} & \dots & a_{2n} b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} b_{m1} & a_{m2} b_{m2} & \dots & a_{mn} b_{mn} \end{bmatrix}. $$ Adding or multiplying a scalar and a tensor produces a result with the same shape as the original tensor. Here, each element of the tensor is added to (or multiplied by) the scalar. ## Reduction Often, we wish to calculate the sum of a tensor's elements. To express the sum of the elements in a vector $\mathbf{x}$ of length $n$, we write $\sum_{i=1}^n x_i$. There is a simple function for it: To express sums over the elements of tensors of arbitrary shape, we simply sum over all its axes. For example, the sum of the elements of an $m \times n$ matrix $\mathbf{A}$ could be written $\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}$. By default, invoking the sum function reduces a tensor along all of its axes, eventually producing a scalar. Our libraries also allow us to specify the axes along which the tensor should be reduced. To sum over all elements along the rows (axis 0), we specify axis=0 in sum. Since the input matrix reduces along axis 0 to generate the output vector, this axis is missing from the shape of the output. Specifying axis=1 will reduce the column dimension (axis 1) by summing up elements of all the columns. Reducing a matrix along both rows and columns via summation is equivalent to summing up all the elements of the matrix. A related quantity is the mean, also called the average. We calculate the mean by dividing the sum by the total number of elements. Because computing the mean is so common, it gets a dedicated library function that works analogously to sum. Likewise, the function for calculating the mean can also reduce a tensor along specific axes. ## Non-Reduction Sum Sometimes it can be useful to keep the number of axes unchanged when invoking the function for calculating the sum or mean. This matters when we want to use the broadcast mechanism. For instance, since sum_A keeps its two axes after summing each row, we can (divide A by sum_A with broadcasting) to create a matrix where each row sums up to $1$. If we want to calculate the cumulative sum of elements of A along some axis, say axis=0 (row by row), we can call the cumsum function. By design, this function does not reduce the input tensor along any axis. ## Dot Products So far, we have only performed elementwise operations, sums, and averages. And if this was all we could do, linear algebra would not deserve its own section. Fortunately, this is where things get more interesting. One of the most fundamental operations is the dot product. Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. The dot product of two vectors is a sum over the products of the elements at the same position Equivalently, (we can calculate the dot product of two vectors by performing an elementwise multiplication followed by a sum:) Dot products are useful in a wide range of contexts. For example, given some set of values, denoted by a vector $\mathbf{x} \in \mathbb{R}^n$, and a set of weights, denoted by $\mathbf{w} \in \mathbb{R}^n$, the weighted sum of the values in $\mathbf{x}$ according to the weights $\mathbf{w}$ could be expressed as the dot product $\mathbf{x}^\top \mathbf{w}$. When the weights are nonnegative and sum to $1$, i.e., $\left(\sum_{i=1}^{n} {w_i} = 1\right)$, the dot product expresses a weighted average. After normalizing two vectors to have unit length, the dot products express the cosine of the angle between them. Later in this section, we will formally introduce this notion of length. ## Matrix--Vector Products Now that we know how to calculate dot products, we can begin to understand the product between an $m \times n$ matrix $\mathbf{A}$ and an $n$-dimensional vector $\mathbf{x}$. To start off, we visualize our matrix in terms of its row vectors $$\mathbf{A}= \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix},$$ where each $\mathbf{a}^\top_{i} \in \mathbb{R}^n$ is a row vector representing the $i^\textrm{th}$ row of the matrix $\mathbf{A}$. The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$: $$ \mathbf{A}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{x} \\ \mathbf{a}^\top_{2} \mathbf{x} \\ \vdots\\ \mathbf{a}^\top_{m} \mathbf{x}\\ \end{bmatrix}. $$ We can think of multiplication with a matrix $\mathbf{A}\in \mathbb{R}^{m \times n}$ as a transformation that projects vectors from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$. These transformations are remarkably useful. For example, we can represent rotations as multiplications by certain square matrices. Matrix--vector products also describe the key calculation involved in computing the outputs of each layer in a neural network given the outputs from the previous layer. :begin_tab:mxnet To express a matrix--vector product in code, we use the same dot function. The operation is inferred based on the type of the arguments. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). :end_tab: :begin_tab:pytorch To express a matrix--vector product in code, we use the mv function. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). Python has a convenience operator @ that can execute both matrix--vector and matrix--matrix products (depending on its arguments). Thus we can write A@x. :end_tab: :begin_tab:tensorflow To express a matrix--vector product in code, we use the matvec function. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). :end_tab: ## Matrix--Matrix Multiplication Once you have gotten the hang of dot products and matrix--vector products, then matrix--matrix multiplication should be straightforward. Say that we have two matrices $\mathbf{A} \in \mathbb{R}^{n \times k}$ and $\mathbf{B} \in \mathbb{R}^{k \times m}$: $$\mathbf{A}=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1k} \\ a_{21} & a_{22} & \cdots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nk} \\ \end{bmatrix},\quad \mathbf{B}=\begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1m} \\ b_{21} & b_{22} & \cdots & b_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ b_{k1} & b_{k2} & \cdots & b_{km} \\ \end{bmatrix}.$$ Let $\mathbf{a}^\top_{i} \in \mathbb{R}^k$ denote the row vector representing the $i^\textrm{th}$ row of the matrix $\mathbf{A}$ and let $\mathbf{b}_{j} \in \mathbb{R}^k$ denote the column vector from the $j^\textrm{th}$ column of the matrix $\mathbf{B}$: $$\mathbf{A}= \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_n \\ \end{bmatrix}, \quad \mathbf{B}=\begin{bmatrix} \mathbf{b}_{1} & \mathbf{b}_{2} & \cdots & \mathbf{b}_{m} \\ \end{bmatrix}. $$ To form the matrix product $\mathbf{C} \in \mathbb{R}^{n \times m}$, we simply compute each element $c_{ij}$ as the dot product between the $i^{\textrm{th}}$ row of $\mathbf{A}$ and the $j^{\textrm{th}}$ column of $\mathbf{B}$, i.e., $\mathbf{a}^\top_i \mathbf{b}_j$: $$\mathbf{C} = \mathbf{AB} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_n \\ \end{bmatrix} \begin{bmatrix} \mathbf{b}_{1} & \mathbf{b}_{2} & \cdots & \mathbf{b}_{m} \\ \end{bmatrix} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{b}_1 & \mathbf{a}^\top_{1}\mathbf{b}_2& \cdots & \mathbf{a}^\top_{1} \mathbf{b}_m \\ \mathbf{a}^\top_{2}\mathbf{b}_1 & \mathbf{a}^\top_{2} \mathbf{b}_2 & \cdots & \mathbf{a}^\top_{2} \mathbf{b}_m \\ \vdots & \vdots & \ddots &\vdots\\ \mathbf{a}^\top_{n} \mathbf{b}_1 & \mathbf{a}^\top_{n}\mathbf{b}_2& \cdots& \mathbf{a}^\top_{n} \mathbf{b}_m \end{bmatrix}. $$ We can think of the matrix--matrix multiplication $\mathbf{AB}$ as performing $m$ matrix--vector products or $m \times n$ dot products and stitching the results together to form an $n \times m$ matrix. In the following snippet, we perform matrix multiplication on A and B. Here, A is a matrix with two rows and three columns, and B is a matrix with three rows and four columns. After multiplication, we obtain a matrix with two rows and four columns. The term matrix--matrix multiplication is often simplified to matrix multiplication, and should not be confused with the Hadamard product. ## Norms Some of the most useful operators in linear algebra are norms. Informally, the norm of a vector tells us how big it is. For instance, the $\ell_2$ norm measures the (Euclidean) length of a vector. Here, we are employing a notion of size that concerns the magnitude of a vector's components (not its dimensionality). A norm is a function $\| \cdot \|$ that maps a vector to a scalar and satisfies the following three properties: 1. Given any vector $\mathbf{x}$, if we scale (all elements of) the vector by a scalar $\alpha \in \mathbb{R}$, its norm scales accordingly: $$\|\alpha \mathbf{x}\| = |\alpha| \|\mathbf{x}\|.$$ 2. For any vectors $\mathbf{x}$ and $\mathbf{y}$: norms satisfy the triangle inequality: $$\|\mathbf{x} + \mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|.$$ 3. The norm of a vector is nonnegative and it only vanishes if the vector is zero: $$\|\mathbf{x}\| > 0 \textrm{ for all } \mathbf{x} \neq 0.$$ Many functions are valid norms and different norms encode different notions of size. The Euclidean norm that we all learned in elementary school geometry when calculating the hypotenuse of a right triangle is the square root of the sum of squares of a vector's elements. Formally, this is called the $\ell_2$ norm and expressed as ($$\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2}.$$) The method norm calculates the $\ell_2$ norm. The $\ell_1$ norm is also common and the associated measure is called the Manhattan distance. By definition, the $\ell_1$ norm sums the absolute values of a vector's elements: ($$\|\mathbf{x}\|_1 = \sum_{i=1}^n \left|x_i \right|.$$) Compared to the $\ell_2$ norm, it is less sensitive to outliers. To compute the $\ell_1$ norm, we compose the absolute value with the sum operation. Both the $\ell_2$ and $\ell_1$ norms are special cases of the more general $\ell_p$ norms: $$\|\mathbf{x}\|_p = \left(\sum_{i=1}^n \left|x_i \right|^p \right)^{1/p}.$$ In the case of matrices, matters are more complicated. After all, matrices can be viewed both as collections of individual entries and as objects that operate on vectors and transform them into other vectors. For instance, we can ask by how much longer the matrix--vector product $\mathbf{X} \mathbf{v}$ could be relative to $\mathbf{v}$. This line of thought leads to what is called the spectral norm. For now, we introduce the Frobenius norm, which is much easier to compute and defined as the square root of the sum of the squares of a matrix's elements: $$\|\mathbf{X}\|_\textrm{F} = \sqrt{\sum_{i=1}^m \sum_{j=1}^n x_{ij}^2}.$$ The Frobenius norm behaves as if it were an $\ell_2$ norm of a matrix-shaped vector. Invoking the following function will calculate the Frobenius norm of a matrix. While we do not want to get too far ahead of ourselves, we already can plant some intuition about why these concepts are useful. In deep learning, we are often trying to solve optimization problems: maximize the probability assigned to observed data; maximize the revenue associated with a recommender model; minimize the distance between predictions and the ground truth observations; minimize the distance between representations of photos of the same person while maximizing the distance between representations of photos of different people. These distances, which constitute the objectives of deep learning algorithms, are often expressed as norms. ## Discussion In this section, we have reviewed all the linear algebra that you will need to understand a significant chunk of modern deep learning. There is a lot more to linear algebra, though, and much of it is useful for machine learning. For example, matrices can be decomposed into factors, and these decompositions can reveal low-dimensional structure in real-world datasets. There are entire subfields of machine learning that focus on using matrix decompositions and their generalizations to high-order tensors to discover structure in datasets and solve prediction problems. But this book focuses on deep learning. And we believe you will be more inclined to learn more mathematics once you have gotten your hands dirty applying machine learning to real datasets. So while we reserve the right to introduce more mathematics later on, we wrap up this section here. If you are eager to learn more linear algebra, there are many excellent books and online resources. For a more advanced crash course, consider checking out , , and . To recap: Scalars, vectors, matrices, and tensors are the basic mathematical objects used in linear algebra and have zero, one, two, and an arbitrary number of axes, respectively. Tensors can be sliced or reduced along specified axes via indexing, or operations such as sum and mean, respectively. Elementwise products are called Hadamard products. By contrast, dot products, matrix--vector products, and matrix--matrix products are not elementwise operations and in general return objects having shapes that are different from the the operands. Compared to Hadamard products, matrix--matrix products take considerably longer to compute (cubic rather than quadratic time). Norms capture various notions of the magnitude of a vector (or matrix), and are commonly applied to the difference of two vectors to measure their distance apart. Common vector norms include the $\ell_1$ and $\ell_2$ norms, and common matrix norms include the spectral and Frobenius norms. ## Exercises 1. Prove that the transpose of the transpose of a matrix is the matrix itself: $(\mathbf{A}^\top)^\top = \mathbf{A}$. 1. Given two matrices $\mathbf{A}$ and $\mathbf{B}$, show that sum and transposition commute: $\mathbf{A}^\top + \mathbf{B}^\top = (\mathbf{A} + \mathbf{B})^\top$. 1. Given any square matrix $\mathbf{A}$, is $\mathbf{A} + \mathbf{A}^\top$ always symmetric? Can you prove the result by using only the results of the previous two exercises? 1. We defined the tensor X of shape (2, 3, 4) in this section. What is the output of len(X)? Write your answer without implementing any code, then check your answer using code. 1. For a tensor X of arbitrary shape, does len(X) always correspond to the length of a certain axis of X? What is that axis? 1. Run A / A.sum(axis=1) and see what happens. Can you analyze the results? 1. When traveling between two points in downtown Manhattan, what is the distance that you need to cover in terms of the coordinates, i.e., in terms of avenues and streets? Can you travel diagonally? 1. Consider a tensor of shape (2, 3, 4). What are the shapes of the summation outputs along axes 0, 1, and 2? 1. Feed a tensor with three or more axes to the linalg.norm function and observe its output. What does this function compute for tensors of arbitrary shape? 1. Consider three large matrices, say $\mathbf{A} \in \mathbb{R}^{2^{10} \times 2^{16}}$, $\mathbf{B} \in \mathbb{R}^{2^{16} \times 2^{5}}$ and $\mathbf{C} \in \mathbb{R}^{2^{5} \times 2^{14}}$, initialized with Gaussian random variables. You want to compute the product $\mathbf{A} \mathbf{B} \mathbf{C}$. Is there any difference in memory footprint and speed, depending on whether you compute $(\mathbf{A} \mathbf{B}) \mathbf{C}$ or $\mathbf{A} (\mathbf{B} \mathbf{C})$. Why? 1. Consider three large matrices, say $\mathbf{A} \in \mathbb{R}^{2^{10} \times 2^{16}}$, $\mathbf{B} \in \mathbb{R}^{2^{16} \times 2^{5}}$ and $\mathbf{C} \in \mathbb{R}^{2^{5} \times 2^{16}}$. Is there any difference in speed depending on whether you compute $\mathbf{A} \mathbf{B}$ or $\mathbf{A} \mathbf{C}^\top$? Why? What changes if you initialize $\mathbf{C} = \mathbf{B}^\top$ without cloning memory? Why? 1. Consider three matrices, say $\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathbb{R}^{100 \times 200}$. Construct a tensor with three axes by stacking $[\mathbf{A}, \mathbf{B}, \mathbf{C}]$. What is the dimensionality? Slice out the second coordinate of the third axis to recover $\mathbf{B}$. Check that your answer is correct. :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " ALGKind="source" ALGId="d2l-linear-algebra" ALGTitle="Dive into Deep Learning — 2.3 Linear Algebra" ALGAuthor="Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola" ALGLicense="CC-BY-SA-4.0" ALGLicenseDeed="https://creativecommons.org/licenses/by-sa/4.0/" ALGURL="https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_preliminaries/linear-algebra.md" ALGExactText="Dive into Deep Learning — 2.3 Linear Algebra Source ID: d2l-linear-algebra Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_preliminaries/linear-algebra.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 2.3 Linear Algebra by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Linear Algebra By now, we can load datasets into tensors and manipulate these tensors with basic mathematical operations. To start building sophisticated models, we will also need a few tools from linear algebra. This section offers a gentle introduction to the most essential concepts, starting from scalar arithmetic and ramping up to matrix multiplication. ## Scalars Most everyday mathematics consists of manipulating numbers one at a time. Formally, we call these values scalars. For example, the temperature in Palo Alto is a balmy $72$ degrees Fahrenheit. If you wanted to convert the temperature to Celsius you would evaluate the expression $c = \frac{5}{9}(f - 32)$, setting $f$ to $72$. In this equation, the values $5$, $9$, and $32$ are constant scalars. The variables $c$ and $f$ in general represent unknown scalars. We denote scalars by ordinary lower-cased letters (e.g., $x$, $y$, and $z$) and the space of all (continuous) real-valued scalars by $\mathbb{R}$. For expedience, we will skip past rigorous definitions of spaces: just remember that the expression $x \in \mathbb{R}$ is a formal way to say that $x$ is a real-valued scalar. The symbol $\in$ (pronounced "in") denotes membership in a set. For example, $x, y \in \{0, 1\}$ indicates that $x$ and $y$ are variables that can only take values $0$ or $1$. (Scalars are implemented as tensors that contain only one element.) Below, we assign two scalars and perform the familiar addition, multiplication, division, and exponentiation operations. ## Vectors For current purposes, you can think of a vector as a fixed-length array of scalars. As with their code counterparts, we call these scalars the elements of the vector (synonyms include entries and components). When vectors represent examples from real-world datasets, their values hold some real-world significance. For example, if we were training a model to predict the risk of a loan defaulting, we might associate each applicant with a vector whose components correspond to quantities like their income, length of employment, or number of previous defaults. If we were studying the risk of heart attack, each vector might represent a patient and its components might correspond to their most recent vital signs, cholesterol levels, minutes of exercise per day, etc. We denote vectors by bold lowercase letters, (e.g., $\mathbf{x}$, $\mathbf{y}$, and $\mathbf{z}$). Vectors are implemented as $1^{\textrm{st}}$-order tensors. In general, such tensors can have arbitrary lengths, subject to memory limitations. Caution: in Python, as in most programming languages, vector indices start at $0$, also known as zero-based indexing, whereas in linear algebra subscripts begin at $1$ (one-based indexing). We can refer to an element of a vector by using a subscript. For example, $x_2$ denotes the second element of $\mathbf{x}$. Since $x_2$ is a scalar, we do not bold it. By default, we visualize vectors by stacking their elements vertically. $$\mathbf{x} =\begin{bmatrix}x_{1} \\ \vdots \\x_{n}\end{bmatrix},$$ Here $x_1, \ldots, x_n$ are elements of the vector. Later on, we will distinguish between such column vectors and row vectors whose elements are stacked horizontally. Recall that we access a tensor's elements via indexing. To indicate that a vector contains $n$ elements, we write $\mathbf{x} \in \mathbb{R}^n$. Formally, we call $n$ the dimensionality of the vector. In code, this corresponds to the tensor's length, accessible via Python's built-in len function. We can also access the length via the shape attribute. The shape is a tuple that indicates a tensor's length along each axis. (Tensors with just one axis have shapes with just one element.) Oftentimes, the word "dimension" gets overloaded to mean both the number of axes and the length along a particular axis. To avoid this confusion, we use order to refer to the number of axes and dimensionality exclusively to refer to the number of components. ## Matrices Just as scalars are $0^{\textrm{th}}$-order tensors and vectors are $1^{\textrm{st}}$-order tensors, matrices are $2^{\textrm{nd}}$-order tensors. We denote matrices by bold capital letters (e.g., $\mathbf{X}$, $\mathbf{Y}$, and $\mathbf{Z}$), and represent them in code by tensors with two axes. The expression $\mathbf{A} \in \mathbb{R}^{m \times n}$ indicates that a matrix $\mathbf{A}$ contains $m \times n$ real-valued scalars, arranged as $m$ rows and $n$ columns. When $m = n$, we say that a matrix is square. Visually, we can illustrate any matrix as a table. To refer to an individual element, we subscript both the row and column indices, e.g., $a_{ij}$ is the value that belongs to $\mathbf{A}$'s $i^{\textrm{th}}$ row and $j^{\textrm{th}}$ column: $$\mathbf{A}=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{bmatrix}.$$ In code, we represent a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ by a $2^{\textrm{nd}}$-order tensor with shape ($m$, $n$). We can convert any appropriately sized $m \times n$ tensor into an $m \times n$ matrix by passing the desired shape to reshape: Sometimes we want to flip the axes. When we exchange a matrix's rows and columns, the result is called its transpose. Formally, we signify a matrix $\mathbf{A}$'s transpose by $\mathbf{A}^\top$ and if $\mathbf{B} = \mathbf{A}^\top$, then $b_{ij} = a_{ji}$ for all $i$ and $j$. Thus, the transpose of an $m \times n$ matrix is an $n \times m$ matrix: $$ \mathbf{A}^\top = \begin{bmatrix} a_{11} & a_{21} & \dots & a_{m1} \\ a_{12} & a_{22} & \dots & a_{m2} \\ \vdots & \vdots & \ddots & \vdots \\ a_{1n} & a_{2n} & \dots & a_{mn} \end{bmatrix}. $$ In code, we can access any (matrix's transpose) as follows: Symmetric matrices are the subset of square matrices that are equal to their own transposes: $\mathbf{A} = \mathbf{A}^\top$. The following matrix is symmetric: Matrices are useful for representing datasets. Typically, rows correspond to individual records and columns correspond to distinct attributes. ## Tensors While you can go far in your machine learning journey with only scalars, vectors, and matrices, eventually you may need to work with higher-order tensors. Tensors (give us a generic way of describing extensions to $n^{\textrm{th}}$-order arrays.) We call software objects of the tensor class "tensors" precisely because they too can have arbitrary numbers of axes. While it may be confusing to use the word tensor for both the mathematical object and its realization in code, our meaning should usually be clear from context. We denote general tensors by capital letters with a special font face (e.g., $\mathsf{X}$, $\mathsf{Y}$, and $\mathsf{Z}$) and their indexing mechanism (e.g., $x_{ijk}$ and $[\mathsf{X}]_{1, 2i-1, 3}$) follows naturally from that of matrices. Tensors will become more important when we start working with images. Each image arrives as a $3^{\textrm{rd}}$-order tensor with axes corresponding to the height, width, and channel. At each spatial location, the intensities of each color (red, green, and blue) are stacked along the channel. Furthermore, a collection of images is represented in code by a $4^{\textrm{th}}$-order tensor, where distinct images are indexed along the first axis. Higher-order tensors are constructed, as were vectors and matrices, by growing the number of shape components. ## Basic Properties of Tensor Arithmetic Scalars, vectors, matrices, and higher-order tensors all have some handy properties. For example, elementwise operations produce outputs that have the same shape as their operands. The elementwise product of two matrices is called their Hadamard product (denoted $\odot$). We can spell out the entries of the Hadamard product of two matrices $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{m \times n}$: $$ \mathbf{A} \odot \mathbf{B} = \begin{bmatrix} a_{11} b_{11} & a_{12} b_{12} & \dots & a_{1n} b_{1n} \\ a_{21} b_{21} & a_{22} b_{22} & \dots & a_{2n} b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} b_{m1} & a_{m2} b_{m2} & \dots & a_{mn} b_{mn} \end{bmatrix}. $$ Adding or multiplying a scalar and a tensor produces a result with the same shape as the original tensor. Here, each element of the tensor is added to (or multiplied by) the scalar. ## Reduction Often, we wish to calculate the sum of a tensor's elements. To express the sum of the elements in a vector $\mathbf{x}$ of length $n$, we write $\sum_{i=1}^n x_i$. There is a simple function for it: To express sums over the elements of tensors of arbitrary shape, we simply sum over all its axes. For example, the sum of the elements of an $m \times n$ matrix $\mathbf{A}$ could be written $\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}$. By default, invoking the sum function reduces a tensor along all of its axes, eventually producing a scalar. Our libraries also allow us to specify the axes along which the tensor should be reduced. To sum over all elements along the rows (axis 0), we specify axis=0 in sum. Since the input matrix reduces along axis 0 to generate the output vector, this axis is missing from the shape of the output. Specifying axis=1 will reduce the column dimension (axis 1) by summing up elements of all the columns. Reducing a matrix along both rows and columns via summation is equivalent to summing up all the elements of the matrix. A related quantity is the mean, also called the average. We calculate the mean by dividing the sum by the total number of elements. Because computing the mean is so common, it gets a dedicated library function that works analogously to sum. Likewise, the function for calculating the mean can also reduce a tensor along specific axes. ## Non-Reduction Sum Sometimes it can be useful to keep the number of axes unchanged when invoking the function for calculating the sum or mean. This matters when we want to use the broadcast mechanism. For instance, since sum_A keeps its two axes after summing each row, we can (divide A by sum_A with broadcasting) to create a matrix where each row sums up to $1$. If we want to calculate the cumulative sum of elements of A along some axis, say axis=0 (row by row), we can call the cumsum function. By design, this function does not reduce the input tensor along any axis. ## Dot Products So far, we have only performed elementwise operations, sums, and averages. And if this was all we could do, linear algebra would not deserve its own section. Fortunately, this is where things get more interesting. One of the most fundamental operations is the dot product. Given two vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^d$, their dot product $\mathbf{x}^\top \mathbf{y}$ (also known as inner product, $\langle \mathbf{x}, \mathbf{y} \rangle$) is a sum over the products of the elements at the same position: $\mathbf{x}^\top \mathbf{y} = \sum_{i=1}^{d} x_i y_i$. The dot product of two vectors is a sum over the products of the elements at the same position Equivalently, (we can calculate the dot product of two vectors by performing an elementwise multiplication followed by a sum:) Dot products are useful in a wide range of contexts. For example, given some set of values, denoted by a vector $\mathbf{x} \in \mathbb{R}^n$, and a set of weights, denoted by $\mathbf{w} \in \mathbb{R}^n$, the weighted sum of the values in $\mathbf{x}$ according to the weights $\mathbf{w}$ could be expressed as the dot product $\mathbf{x}^\top \mathbf{w}$. When the weights are nonnegative and sum to $1$, i.e., $\left(\sum_{i=1}^{n} {w_i} = 1\right)$, the dot product expresses a weighted average. After normalizing two vectors to have unit length, the dot products express the cosine of the angle between them. Later in this section, we will formally introduce this notion of length. ## Matrix--Vector Products Now that we know how to calculate dot products, we can begin to understand the product between an $m \times n$ matrix $\mathbf{A}$ and an $n$-dimensional vector $\mathbf{x}$. To start off, we visualize our matrix in terms of its row vectors $$\mathbf{A}= \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix},$$ where each $\mathbf{a}^\top_{i} \in \mathbb{R}^n$ is a row vector representing the $i^\textrm{th}$ row of the matrix $\mathbf{A}$. The matrix--vector product $\mathbf{A}\mathbf{x}$ is simply a column vector of length $m$, whose $i^\textrm{th}$ element is the dot product $\mathbf{a}^\top_i \mathbf{x}$: $$ \mathbf{A}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_m \\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{x} \\ \mathbf{a}^\top_{2} \mathbf{x} \\ \vdots\\ \mathbf{a}^\top_{m} \mathbf{x}\\ \end{bmatrix}. $$ We can think of multiplication with a matrix $\mathbf{A}\in \mathbb{R}^{m \times n}$ as a transformation that projects vectors from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$. These transformations are remarkably useful. For example, we can represent rotations as multiplications by certain square matrices. Matrix--vector products also describe the key calculation involved in computing the outputs of each layer in a neural network given the outputs from the previous layer. :begin_tab:mxnet To express a matrix--vector product in code, we use the same dot function. The operation is inferred based on the type of the arguments. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). :end_tab: :begin_tab:pytorch To express a matrix--vector product in code, we use the mv function. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). Python has a convenience operator @ that can execute both matrix--vector and matrix--matrix products (depending on its arguments). Thus we can write A@x. :end_tab: :begin_tab:tensorflow To express a matrix--vector product in code, we use the matvec function. Note that the column dimension of A (its length along axis 1) must be the same as the dimension of x (its length). :end_tab: ## Matrix--Matrix Multiplication Once you have gotten the hang of dot products and matrix--vector products, then matrix--matrix multiplication should be straightforward. Say that we have two matrices $\mathbf{A} \in \mathbb{R}^{n \times k}$ and $\mathbf{B} \in \mathbb{R}^{k \times m}$: $$\mathbf{A}=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1k} \\ a_{21} & a_{22} & \cdots & a_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nk} \\ \end{bmatrix},\quad \mathbf{B}=\begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1m} \\ b_{21} & b_{22} & \cdots & b_{2m} \\ \vdots & \vdots & \ddots & \vdots \\ b_{k1} & b_{k2} & \cdots & b_{km} \\ \end{bmatrix}.$$ Let $\mathbf{a}^\top_{i} \in \mathbb{R}^k$ denote the row vector representing the $i^\textrm{th}$ row of the matrix $\mathbf{A}$ and let $\mathbf{b}_{j} \in \mathbb{R}^k$ denote the column vector from the $j^\textrm{th}$ column of the matrix $\mathbf{B}$: $$\mathbf{A}= \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_n \\ \end{bmatrix}, \quad \mathbf{B}=\begin{bmatrix} \mathbf{b}_{1} & \mathbf{b}_{2} & \cdots & \mathbf{b}_{m} \\ \end{bmatrix}. $$ To form the matrix product $\mathbf{C} \in \mathbb{R}^{n \times m}$, we simply compute each element $c_{ij}$ as the dot product between the $i^{\textrm{th}}$ row of $\mathbf{A}$ and the $j^{\textrm{th}}$ column of $\mathbf{B}$, i.e., $\mathbf{a}^\top_i \mathbf{b}_j$: $$\mathbf{C} = \mathbf{AB} = \begin{bmatrix} \mathbf{a}^\top_{1} \\ \mathbf{a}^\top_{2} \\ \vdots \\ \mathbf{a}^\top_n \\ \end{bmatrix} \begin{bmatrix} \mathbf{b}_{1} & \mathbf{b}_{2} & \cdots & \mathbf{b}_{m} \\ \end{bmatrix} = \begin{bmatrix} \mathbf{a}^\top_{1} \mathbf{b}_1 & \mathbf{a}^\top_{1}\mathbf{b}_2& \cdots & \mathbf{a}^\top_{1} \mathbf{b}_m \\ \mathbf{a}^\top_{2}\mathbf{b}_1 & \mathbf{a}^\top_{2} \mathbf{b}_2 & \cdots & \mathbf{a}^\top_{2} \mathbf{b}_m \\ \vdots & \vdots & \ddots &\vdots\\ \mathbf{a}^\top_{n} \mathbf{b}_1 & \mathbf{a}^\top_{n}\mathbf{b}_2& \cdots& \mathbf{a}^\top_{n} \mathbf{b}_m \end{bmatrix}. $$ We can think of the matrix--matrix multiplication $\mathbf{AB}$ as performing $m$ matrix--vector products or $m \times n$ dot products and stitching the results together to form an $n \times m$ matrix. In the following snippet, we perform matrix multiplication on A and B. Here, A is a matrix with two rows and three columns, and B is a matrix with three rows and four columns. After multiplication, we obtain a matrix with two rows and four columns. The term matrix--matrix multiplication is often simplified to matrix multiplication, and should not be confused with the Hadamard product. ## Norms Some of the most useful operators in linear algebra are norms. Informally, the norm of a vector tells us how big it is. For instance, the $\ell_2$ norm measures the (Euclidean) length of a vector. Here, we are employing a notion of size that concerns the magnitude of a vector's components (not its dimensionality). A norm is a function $\| \cdot \|$ that maps a vector to a scalar and satisfies the following three properties: 1. Given any vector $\mathbf{x}$, if we scale (all elements of) the vector by a scalar $\alpha \in \mathbb{R}$, its norm scales accordingly: $$\|\alpha \mathbf{x}\| = |\alpha| \|\mathbf{x}\|.$$ 2. For any vectors $\mathbf{x}$ and $\mathbf{y}$: norms satisfy the triangle inequality: $$\|\mathbf{x} + \mathbf{y}\| \leq \|\mathbf{x}\| + \|\mathbf{y}\|.$$ 3. The norm of a vector is nonnegative and it only vanishes if the vector is zero: $$\|\mathbf{x}\| > 0 \textrm{ for all } \mathbf{x} \neq 0.$$ Many functions are valid norms and different norms encode different notions of size. The Euclidean norm that we all learned in elementary school geometry when calculating the hypotenuse of a right triangle is the square root of the sum of squares of a vector's elements. Formally, this is called the $\ell_2$ norm and expressed as ($$\|\mathbf{x}\|_2 = \sqrt{\sum_{i=1}^n x_i^2}.$$) The method norm calculates the $\ell_2$ norm. The $\ell_1$ norm is also common and the associated measure is called the Manhattan distance. By definition, the $\ell_1$ norm sums the absolute values of a vector's elements: ($$\|\mathbf{x}\|_1 = \sum_{i=1}^n \left|x_i \right|.$$) Compared to the $\ell_2$ norm, it is less sensitive to outliers. To compute the $\ell_1$ norm, we compose the absolute value with the sum operation. Both the $\ell_2$ and $\ell_1$ norms are special cases of the more general $\ell_p$ norms: $$\|\mathbf{x}\|_p = \left(\sum_{i=1}^n \left|x_i \right|^p \right)^{1/p}.$$ In the case of matrices, matters are more complicated. After all, matrices can be viewed both as collections of individual entries and as objects that operate on vectors and transform them into other vectors. For instance, we can ask by how much longer the matrix--vector product $\mathbf{X} \mathbf{v}$ could be relative to $\mathbf{v}$. This line of thought leads to what is called the spectral norm. For now, we introduce the Frobenius norm, which is much easier to compute and defined as the square root of the sum of the squares of a matrix's elements: $$\|\mathbf{X}\|_\textrm{F} = \sqrt{\sum_{i=1}^m \sum_{j=1}^n x_{ij}^2}.$$ The Frobenius norm behaves as if it were an $\ell_2$ norm of a matrix-shaped vector. Invoking the following function will calculate the Frobenius norm of a matrix. While we do not want to get too far ahead of ourselves, we already can plant some intuition about why these concepts are useful. In deep learning, we are often trying to solve optimization problems: maximize the probability assigned to observed data; maximize the revenue associated with a recommender model; minimize the distance between predictions and the ground truth observations; minimize the distance between representations of photos of the same person while maximizing the distance between representations of photos of different people. These distances, which constitute the objectives of deep learning algorithms, are often expressed as norms. ## Discussion In this section, we have reviewed all the linear algebra that you will need to understand a significant chunk of modern deep learning. There is a lot more to linear algebra, though, and much of it is useful for machine learning. For example, matrices can be decomposed into factors, and these decompositions can reveal low-dimensional structure in real-world datasets. There are entire subfields of machine learning that focus on using matrix decompositions and their generalizations to high-order tensors to discover structure in datasets and solve prediction problems. But this book focuses on deep learning. And we believe you will be more inclined to learn more mathematics once you have gotten your hands dirty applying machine learning to real datasets. So while we reserve the right to introduce more mathematics later on, we wrap up this section here. If you are eager to learn more linear algebra, there are many excellent books and online resources. For a more advanced crash course, consider checking out , , and . To recap: Scalars, vectors, matrices, and tensors are the basic mathematical objects used in linear algebra and have zero, one, two, and an arbitrary number of axes, respectively. Tensors can be sliced or reduced along specified axes via indexing, or operations such as sum and mean, respectively. Elementwise products are called Hadamard products. By contrast, dot products, matrix--vector products, and matrix--matrix products are not elementwise operations and in general return objects having shapes that are different from the the operands. Compared to Hadamard products, matrix--matrix products take considerably longer to compute (cubic rather than quadratic time). Norms capture various notions of the magnitude of a vector (or matrix), and are commonly applied to the difference of two vectors to measure their distance apart. Common vector norms include the $\ell_1$ and $\ell_2$ norms, and common matrix norms include the spectral and Frobenius norms. ## Exercises 1. Prove that the transpose of the transpose of a matrix is the matrix itself: $(\mathbf{A}^\top)^\top = \mathbf{A}$. 1. Given two matrices $\mathbf{A}$ and $\mathbf{B}$, show that sum and transposition commute: $\mathbf{A}^\top + \mathbf{B}^\top = (\mathbf{A} + \mathbf{B})^\top$. 1. Given any square matrix $\mathbf{A}$, is $\mathbf{A} + \mathbf{A}^\top$ always symmetric? Can you prove the result by using only the results of the previous two exercises? 1. We defined the tensor X of shape (2, 3, 4) in this section. What is the output of len(X)? Write your answer without implementing any code, then check your answer using code. 1. For a tensor X of arbitrary shape, does len(X) always correspond to the length of a certain axis of X? What is that axis? 1. Run A / A.sum(axis=1) and see what happens. Can you analyze the results? 1. When traveling between two points in downtown Manhattan, what is the distance that you need to cover in terms of the coordinates, i.e., in terms of avenues and streets? Can you travel diagonally? 1. Consider a tensor of shape (2, 3, 4). What are the shapes of the summation outputs along axes 0, 1, and 2? 1. Feed a tensor with three or more axes to the linalg.norm function and observe its output. What does this function compute for tensors of arbitrary shape? 1. Consider three large matrices, say $\mathbf{A} \in \mathbb{R}^{2^{10} \times 2^{16}}$, $\mathbf{B} \in \mathbb{R}^{2^{16} \times 2^{5}}$ and $\mathbf{C} \in \mathbb{R}^{2^{5} \times 2^{14}}$, initialized with Gaussian random variables. You want to compute the product $\mathbf{A} \mathbf{B} \mathbf{C}$. Is there any difference in memory footprint and speed, depending on whether you compute $(\mathbf{A} \mathbf{B}) \mathbf{C}$ or $\mathbf{A} (\mathbf{B} \mathbf{C})$. Why? 1. Consider three large matrices, say $\mathbf{A} \in \mathbb{R}^{2^{10} \times 2^{16}}$, $\mathbf{B} \in \mathbb{R}^{2^{16} \times 2^{5}}$ and $\mathbf{C} \in \mathbb{R}^{2^{5} \times 2^{16}}$. Is there any difference in speed depending on whether you compute $\mathbf{A} \mathbf{B}$ or $\mathbf{A} \mathbf{C}^\top$? Why? What changes if you initialize $\mathbf{C} = \mathbf{B}^\top$ without cloning memory? Why? 1. Consider three matrices, say $\mathbf{A}, \mathbf{B}, \mathbf{C} \in \mathbb{R}^{100 \times 200}$. Construct a tensor with three axes by stacking $[\mathbf{A}, \mathbf{B}, \mathbf{C}]$. What is the dimensionality? Slice out the second coordinate of the third axis to recover $\mathbf{B}$. Check that your answer is correct. :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " Prototype="ALG Source" Color="#7CB7C9" Shape="rounded" Badge="doc.text" Width="6" Height="2.5" BorderColor="#264653" Xpos="0" Ypos="4" ALGXpos="0" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGLicense;ALGURL"/>
<outline text="Dive into Deep Learning — 11.1 Queries, Keys, and Values" _note="Dive into Deep Learning -- 11.1 Queries, Keys, and Values Source ID: d2l-queries-keys-values Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/queries-keys-values.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Queries, Keys, and Values So far all the networks we have reviewed crucially relied on the input being of a well-defined size. For instance, the images in ImageNet are of size $224 \times 224$ pixels and CNNs are specifically tuned to this size. Even in natural language processing the input size for RNNs is well defined and fixed. Variable size is addressed by sequentially processing one token at a time, or by specially designed convolution kernels . This approach can lead to significant problems when the input is truly of varying size with varying information content, such as in in the transformation of text . In particular, for long sequences it becomes quite difficult to keep track of everything that has already been generated or even viewed by the network. Even explicit tracking heuristics such as proposed by only offer limited benefit. Compare this to databases. In their simplest form they are collections of keys ($k$) and values ($v$). For instance, our database $\mathcal{D}$ might consist of tuples \{("Zhang", "Aston"), ("Lipton", "Zachary"), ("Li", "Mu"), ("Smola", "Alex"), ("Hu", "Rachel"), ("Werness", "Brent")\} with the last name being the key and the first name being the value. We can operate on $\mathcal{D}$, for instance with the exact query ($q$) for "Li" which would return the value "Mu". If ("Li", "Mu") was not a record in $\mathcal{D}$, there would be no valid answer. If we also allowed for approximate matches, we would retrieve ("Lipton", "Zachary") instead. This quite simple and trivial example nonetheless teaches us a number of useful things: We can design queries $q$ that operate on ($k$,$v$) pairs in such a manner as to be valid regardless of the database size. The same query can receive different answers, according to the contents of the database. The "code" being executed for operating on a large state space (the database) can be quite simple (e.g., exact match, approximate match, top-$k$). There is no need to compress or simplify the database to make the operations effective. Clearly we would not have introduced a simple database here if it wasn't for the purpose of explaining deep learning. Indeed, this leads to one of the most exciting concepts introduced in deep learning in the past decade: the attention mechanism . We will cover the specifics of its application to machine translation later. For now, simply consider the following: denote by $\mathcal{D} \stackrel{\textrm{def}}{=} \{(\mathbf{k}_1, \mathbf{v}_1), \ldots (\mathbf{k}_m, \mathbf{v}_m)\}$ a database of $m$ tuples of keys and values. Moreover, denote by $\mathbf{q}$ a query. Then we can define the attention over $\mathcal{D}$ as $$\textrm{Attention}(\mathbf{q}, \mathcal{D}) \stackrel{\textrm{def}}{=} \sum_{i=1}^m \alpha(\mathbf{q}, \mathbf{k}_i) \mathbf{v}_i,$$ where $\alpha(\mathbf{q}, \mathbf{k}_i) \in \mathbb{R}$ ($i = 1, \ldots, m$) are scalar attention weights. The operation itself is typically referred to as attention pooling. The name attention derives from the fact that the operation pays particular attention to the terms for which the weight $\alpha$ is significant (i.e., large). As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. In fact, this contains the above example as a special case where all but one weight is zero. We have a number of special cases: The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ are nonnegative. In this case the output of the attention mechanism is contained in the convex cone spanned by the values $\mathbf{v}_i$. The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ form a convex combination, i.e., $\sum_i \alpha(\mathbf{q}, \mathbf{k}_i) = 1$ and $\alpha(\mathbf{q}, \mathbf{k}_i) \geq 0$ for all $i$. This is the most common setting in deep learning. Exactly one of the weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ is $1$, while all others are $0$. This is akin to a traditional database query. All weights are equal, i.e., $\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{1}{m}$ for all $i$. This amounts to averaging across the entire database, also called average pooling in deep learning. A common strategy for ensuring that the weights sum up to $1$ is to normalize them via $$\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{\alpha(\mathbf{q}, \mathbf{k}_i)}{{\sum_j} \alpha(\mathbf{q}, \mathbf{k}_j)}.$$ In particular, to ensure that the weights are also nonnegative, one can resort to exponentiation. This means that we can now pick any function $a(\mathbf{q}, \mathbf{k})$ and then apply the softmax operation used for multinomial models to it via $$\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{\exp(a(\mathbf{q}, \mathbf{k}_i))}{\sum_j \exp(a(\mathbf{q}, \mathbf{k}_j))}. $$ This operation is readily available in all deep learning frameworks. It is differentiable and its gradient never vanishes, all of which are desirable properties in a model. Note though, the attention mechanism introduced above is not the only option. For instance, we can design a non-differentiable attention model that can be trained using reinforcement learning methods . As one would expect, training such a model is quite complex. Consequently the bulk of modern attention research follows the framework outlined in . We thus focus our exposition on this family of differentiable mechanisms. The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. What is quite remarkable is that the actual "code" for executing on the set of keys and values, namely the query, can be quite concise, even though the space to operate on is significant. This is a desirable property for a network layer as it does not require too many parameters to learn. Just as convenient is the fact that attention can operate on arbitrarily large databases without the need to change the way the attention pooling operation is performed. ## Visualization One of the benefits of the attention mechanism is that it can be quite intuitive, particularly when the weights are nonnegative and sum to $1$. In this case we might interpret large weights as a way for the model to select components of relevance. While this is a good intuition, it is important to remember that it is just that, an intuition. Regardless, we may want to visualize its effect on the given set of keys when applying a variety of different queries. This function will come in handy later. We thus define the show_heatmaps function. Note that it does not take a matrix (of attention weights) as its input but rather a tensor with four axes, allowing for an array of different queries and weights. Consequently the input matrices has the shape (number of rows for display, number of columns for display, number of queries, number of keys). This will come in handy later on when we want to visualize the workings that are to design Transformers. As a quick sanity check let's visualize the identity matrix, representing a case where the attention weight is $1$ only when the query and the key are the same. ## Summary The attention mechanism allows us to aggregate data from many (key, value) pairs. So far our discussion was quite abstract, simply describing a way to pool data. We have not explained yet where those mysterious queries, keys, and values might arise from. Some intuition might help here: for instance, in a regression setting, the query might correspond to the location where the regression should be carried out. The keys are the locations where past data was observed and the values are the (regression) values themselves. This is the so-called Nadaraya--Watson estimator that we will be studying in the next section. By design, the attention mechanism provides a differentiable means of control by which a neural network can select elements from a set and to construct an associated weighted sum over representations. ## Exercises 1. Suppose that you wanted to reimplement approximate (key, query) matches as used in classical databases, which attention function would you pick? 1. Suppose that the attention function is given by $a(\mathbf{q}, \mathbf{k}_i) = \mathbf{q}^\top \mathbf{k}_i$ and that $\mathbf{k}_i = \mathbf{v}_i$ for $i = 1, \ldots, m$. Denote by $p(\mathbf{k}_i; \mathbf{q})$ the probability distribution over keys when using the softmax normalization in . Prove that $\nabla_{\mathbf{q}} \mathop{\textrm{Attention}}(\mathbf{q}, \mathcal{D}) = \textrm{Cov}_{p(\mathbf{k}_i; \mathbf{q})}[\mathbf{k}_i]$. 1. Design a differentiable search engine using the attention mechanism. 1. Review the design of the Squeeze and Excitation Networks and interpret them through the lens of the attention mechanism. :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " ALGKind="source" ALGId="d2l-queries-keys-values" ALGTitle="Dive into Deep Learning — 11.1 Queries, Keys, and Values" ALGAuthor="Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola" ALGLicense="CC-BY-SA-4.0" ALGLicenseDeed="https://creativecommons.org/licenses/by-sa/4.0/" ALGURL="https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/queries-keys-values.md" ALGExactText="Dive into Deep Learning — 11.1 Queries, Keys, and Values Source ID: d2l-queries-keys-values Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/queries-keys-values.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.1 Queries, Keys, and Values by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Queries, Keys, and Values So far all the networks we have reviewed crucially relied on the input being of a well-defined size. For instance, the images in ImageNet are of size $224 \times 224$ pixels and CNNs are specifically tuned to this size. Even in natural language processing the input size for RNNs is well defined and fixed. Variable size is addressed by sequentially processing one token at a time, or by specially designed convolution kernels . This approach can lead to significant problems when the input is truly of varying size with varying information content, such as in in the transformation of text . In particular, for long sequences it becomes quite difficult to keep track of everything that has already been generated or even viewed by the network. Even explicit tracking heuristics such as proposed by only offer limited benefit. Compare this to databases. In their simplest form they are collections of keys ($k$) and values ($v$). For instance, our database $\mathcal{D}$ might consist of tuples \{("Zhang", "Aston"), ("Lipton", "Zachary"), ("Li", "Mu"), ("Smola", "Alex"), ("Hu", "Rachel"), ("Werness", "Brent")\} with the last name being the key and the first name being the value. We can operate on $\mathcal{D}$, for instance with the exact query ($q$) for "Li" which would return the value "Mu". If ("Li", "Mu") was not a record in $\mathcal{D}$, there would be no valid answer. If we also allowed for approximate matches, we would retrieve ("Lipton", "Zachary") instead. This quite simple and trivial example nonetheless teaches us a number of useful things: We can design queries $q$ that operate on ($k$,$v$) pairs in such a manner as to be valid regardless of the database size. The same query can receive different answers, according to the contents of the database. The "code" being executed for operating on a large state space (the database) can be quite simple (e.g., exact match, approximate match, top-$k$). There is no need to compress or simplify the database to make the operations effective. Clearly we would not have introduced a simple database here if it wasn't for the purpose of explaining deep learning. Indeed, this leads to one of the most exciting concepts introduced in deep learning in the past decade: the attention mechanism . We will cover the specifics of its application to machine translation later. For now, simply consider the following: denote by $\mathcal{D} \stackrel{\textrm{def}}{=} \{(\mathbf{k}_1, \mathbf{v}_1), \ldots (\mathbf{k}_m, \mathbf{v}_m)\}$ a database of $m$ tuples of keys and values. Moreover, denote by $\mathbf{q}$ a query. Then we can define the attention over $\mathcal{D}$ as $$\textrm{Attention}(\mathbf{q}, \mathcal{D}) \stackrel{\textrm{def}}{=} \sum_{i=1}^m \alpha(\mathbf{q}, \mathbf{k}_i) \mathbf{v}_i,$$ where $\alpha(\mathbf{q}, \mathbf{k}_i) \in \mathbb{R}$ ($i = 1, \ldots, m$) are scalar attention weights. The operation itself is typically referred to as attention pooling. The name attention derives from the fact that the operation pays particular attention to the terms for which the weight $\alpha$ is significant (i.e., large). As such, the attention over $\mathcal{D}$ generates a linear combination of values contained in the database. In fact, this contains the above example as a special case where all but one weight is zero. We have a number of special cases: The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ are nonnegative. In this case the output of the attention mechanism is contained in the convex cone spanned by the values $\mathbf{v}_i$. The weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ form a convex combination, i.e., $\sum_i \alpha(\mathbf{q}, \mathbf{k}_i) = 1$ and $\alpha(\mathbf{q}, \mathbf{k}_i) \geq 0$ for all $i$. This is the most common setting in deep learning. Exactly one of the weights $\alpha(\mathbf{q}, \mathbf{k}_i)$ is $1$, while all others are $0$. This is akin to a traditional database query. All weights are equal, i.e., $\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{1}{m}$ for all $i$. This amounts to averaging across the entire database, also called average pooling in deep learning. A common strategy for ensuring that the weights sum up to $1$ is to normalize them via $$\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{\alpha(\mathbf{q}, \mathbf{k}_i)}{{\sum_j} \alpha(\mathbf{q}, \mathbf{k}_j)}.$$ In particular, to ensure that the weights are also nonnegative, one can resort to exponentiation. This means that we can now pick any function $a(\mathbf{q}, \mathbf{k})$ and then apply the softmax operation used for multinomial models to it via $$\alpha(\mathbf{q}, \mathbf{k}_i) = \frac{\exp(a(\mathbf{q}, \mathbf{k}_i))}{\sum_j \exp(a(\mathbf{q}, \mathbf{k}_j))}. $$ This operation is readily available in all deep learning frameworks. It is differentiable and its gradient never vanishes, all of which are desirable properties in a model. Note though, the attention mechanism introduced above is not the only option. For instance, we can design a non-differentiable attention model that can be trained using reinforcement learning methods . As one would expect, training such a model is quite complex. Consequently the bulk of modern attention research follows the framework outlined in . We thus focus our exposition on this family of differentiable mechanisms. The attention mechanism computes a linear combination over values $\mathbf{v}_\mathit{i}$ via attention pooling, where weights are derived according to the compatibility between a query $\mathbf{q}$ and keys $\mathbf{k}_\mathit{i}$. What is quite remarkable is that the actual "code" for executing on the set of keys and values, namely the query, can be quite concise, even though the space to operate on is significant. This is a desirable property for a network layer as it does not require too many parameters to learn. Just as convenient is the fact that attention can operate on arbitrarily large databases without the need to change the way the attention pooling operation is performed. ## Visualization One of the benefits of the attention mechanism is that it can be quite intuitive, particularly when the weights are nonnegative and sum to $1$. In this case we might interpret large weights as a way for the model to select components of relevance. While this is a good intuition, it is important to remember that it is just that, an intuition. Regardless, we may want to visualize its effect on the given set of keys when applying a variety of different queries. This function will come in handy later. We thus define the show_heatmaps function. Note that it does not take a matrix (of attention weights) as its input but rather a tensor with four axes, allowing for an array of different queries and weights. Consequently the input matrices has the shape (number of rows for display, number of columns for display, number of queries, number of keys). This will come in handy later on when we want to visualize the workings that are to design Transformers. As a quick sanity check let's visualize the identity matrix, representing a case where the attention weight is $1$ only when the query and the key are the same. ## Summary The attention mechanism allows us to aggregate data from many (key, value) pairs. So far our discussion was quite abstract, simply describing a way to pool data. We have not explained yet where those mysterious queries, keys, and values might arise from. Some intuition might help here: for instance, in a regression setting, the query might correspond to the location where the regression should be carried out. The keys are the locations where past data was observed and the values are the (regression) values themselves. This is the so-called Nadaraya--Watson estimator that we will be studying in the next section. By design, the attention mechanism provides a differentiable means of control by which a neural network can select elements from a set and to construct an associated weighted sum over representations. ## Exercises 1. Suppose that you wanted to reimplement approximate (key, query) matches as used in classical databases, which attention function would you pick? 1. Suppose that the attention function is given by $a(\mathbf{q}, \mathbf{k}_i) = \mathbf{q}^\top \mathbf{k}_i$ and that $\mathbf{k}_i = \mathbf{v}_i$ for $i = 1, \ldots, m$. Denote by $p(\mathbf{k}_i; \mathbf{q})$ the probability distribution over keys when using the softmax normalization in . Prove that $\nabla_{\mathbf{q}} \mathop{\textrm{Attention}}(\mathbf{q}, \mathcal{D}) = \textrm{Cov}_{p(\mathbf{k}_i; \mathbf{q})}[\mathbf{k}_i]$. 1. Design a differentiable search engine using the attention mechanism. 1. Review the design of the Squeeze and Excitation Networks and interpret them through the lens of the attention mechanism. :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " Prototype="ALG Source" Color="#7CB7C9" Shape="rounded" Badge="doc.text" Width="6" Height="2.5" BorderColor="#264653" Xpos="6.5" Ypos="4" ALGXpos="6.5" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGLicense;ALGURL"/>
<outline text="Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding" _note="Dive into Deep Learning -- 11.6 Self-Attention and Positional Encoding Source ID: d2l-self-attention Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/self-attention-and-positional-encoding.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Self-Attention and Positional Encoding In deep learning, we often use CNNs or RNNs to encode sequences. Now with attention mechanisms in mind, imagine feeding a sequence of tokens into an attention mechanism such that at every step, each token has its own query, keys, and values. Here, when computing the value of a token's representation at the next layer, the token can attend (via its query vector) to any other's token (matching based on their key vectors). Using the full set of query-key compatibility scores, we can compute, for each token, a representation by building the appropriate weighted sum over the other tokens. Because every token is attending to each other token (unlike the case where decoder steps attend to encoder steps), such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . In this section, we will discuss sequence encoding using self-attention, including using additional information for the sequence order. ## Self-Attention Given a sequence of input tokens $\mathbf{x}_1, \ldots, \mathbf{x}_n$ where any $\mathbf{x}_i \in \mathbb{R}^d$ ($1 \leq i \leq n$), its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ according to the definition of attention pooling in . Using multi-head attention, the following code snippet computes the self-attention of a tensor with shape (batch size, number of time steps or sequence length in tokens, $d$). The output tensor has the same shape. ## Comparing CNNs, RNNs, and Self-Attention Let's compare architectures for mapping a sequence of $n$ tokens to another one of equal length, where each input or output token is represented by a $d$-dimensional vector. Specifically, we will consider CNNs, RNNs, and self-attention. We will compare their computational complexity, sequential operations, and maximum path lengths. Note that sequential operations prevent parallel computation, while a shorter path between any combination of sequence positions makes it easier to learn long-range dependencies within the sequence . Comparing CNN (padding tokens are omitted), RNN, and self-attention architectures. Let's regard any text sequence as a "one-dimensional image". Similarly, one-dimensional CNNs can process local features such as $n$-grams in text. Given a sequence of length $n$, consider a convolutional layer whose kernel size is $k$, and whose numbers of input and output channels are both $d$. The computational complexity of the convolutional layer is $\mathcal{O}(knd^2)$. As shows, CNNs are hierarchical, so there are $\mathcal{O}(1)$ sequential operations and the maximum path length is $\mathcal{O}(n/k)$. For example, $\mathbf{x}_1$ and $\mathbf{x}_5$ are within the receptive field of a two-layer CNN with kernel size 3 in . When updating the hidden state of RNNs, multiplication of the $d \times d$ weight matrix and the $d$-dimensional hidden state has a computational complexity of $\mathcal{O}(d^2)$. Since the sequence length is $n$, the computational complexity of the recurrent layer is $\mathcal{O}(nd^2)$. According to , there are $\mathcal{O}(n)$ sequential operations that cannot be parallelized and the maximum path length is also $\mathcal{O}(n)$. In self-attention, the queries, keys, and values are all $n \times d$ matrices. Consider the scaled dot product attention in , where an $n \times d$ matrix is multiplied by a $d \times n$ matrix, then the output $n \times n$ matrix is multiplied by an $n \times d$ matrix. As a result, the self-attention has a $\mathcal{O}(n^2d)$ computational complexity. As we can see from , each token is directly connected to any other token via self-attention. Therefore, computation can be parallel with $\mathcal{O}(1)$ sequential operations and the maximum path length is also $\mathcal{O}(1)$. All in all, both CNNs and self-attention enjoy parallel computation and self-attention has the shortest maximum path length. However, the quadratic computational complexity with respect to the sequence length makes self-attention prohibitively slow for very long sequences. ## Positional Encoding Unlike RNNs, which recurrently process tokens of a sequence one-by-one, self-attention ditches sequential operations in favor of parallel computation. Note that self-attention by itself does not preserve the order of the sequence. What do we do if it really matters that the model knows in which order the input sequence arrived? The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. These inputs are called positional encodings, and they can either be learned or fixed a priori. We now describe a simple scheme for fixed positional encodings based on sine and cosine functions . Suppose that the input representation $\mathbf{X} \in \mathbb{R}^{n \times d}$ contains the $d$-dimensional embeddings for $n$ tokens of a sequence. The positional encoding outputs $\mathbf{X} + \mathbf{P}$ using a positional embedding matrix $\mathbf{P} \in \mathbb{R}^{n \times d}$ of the same shape, whose element on the $i^\textrm{th}$ row and the $(2j)^\textrm{th}$ or the $(2j + 1)^\textrm{th}$ column is $$\begin{aligned} p_{i, 2j} &= \sin\left(\frac{i}{10000^{2j/d}}\right),\\p_{i, 2j+1} &= \cos\left(\frac{i}{10000^{2j/d}}\right).\end{aligned}$$ At first glance, this trigonometric function design looks weird. Before we give explanations of this design, let's first implement it in the following PositionalEncoding class. In the positional embedding matrix $\mathbf{P}$, rows correspond to positions within a sequence and columns represent different positional encoding dimensions. In the example below, we can see that the $6^{\textrm{th}}$ and the $7^{\textrm{th}}$ columns of the positional embedding matrix have a higher frequency than the $8^{\textrm{th}}$ and the $9^{\textrm{th}}$ columns. The offset between the $6^{\textrm{th}}$ and the $7^{\textrm{th}}$ (same for the $8^{\textrm{th}}$ and the $9^{\textrm{th}}$) columns is due to the alternation of sine and cosine functions. ### Absolute Positional Information To see how the monotonically decreased frequency along the encoding dimension relates to absolute positional information, let's print out the binary representations of $0, 1, \ldots, 7$. As we can see, the lowest bit, the second-lowest bit, and the third-lowest bit alternate on every number, every two numbers, and every four numbers, respectively. In binary representations, a higher bit has a lower frequency than a lower bit. Similarly, as demonstrated in the heat map below, the positional encoding decreases frequencies along the encoding dimension by using trigonometric functions. Since the outputs are float numbers, such continuous representations are more space-efficient than binary representations. ### Relative Positional Information Besides capturing absolute positional information, the above positional encoding also allows a model to easily learn to attend by relative positions. This is because for any fixed position offset $\delta$, the positional encoding at position $i + \delta$ can be represented by a linear projection of that at position $i$. This projection can be explained mathematically. Denoting $\omega_j = 1/10000^{2j/d}$, any pair of $(p_{i, 2j}, p_{i, 2j+1})$ in can be linearly projected to $(p_{i+\delta, 2j}, p_{i+\delta, 2j+1})$ for any fixed offset $\delta$: $$\begin{aligned} \begin{bmatrix} \cos(\delta \omega_j) & \sin(\delta \omega_j) \\ -\sin(\delta \omega_j) & \cos(\delta \omega_j) \\ \end{bmatrix} \begin{bmatrix} p_{i, 2j} \\ p_{i, 2j+1} \\ \end{bmatrix} =&\begin{bmatrix} \cos(\delta \omega_j) \sin(i \omega_j) + \sin(\delta \omega_j) \cos(i \omega_j) \\ -\sin(\delta \omega_j) \sin(i \omega_j) + \cos(\delta \omega_j) \cos(i \omega_j) \\ \end{bmatrix}\\ =&\begin{bmatrix} \sin\left((i+\delta) \omega_j\right) \\ \cos\left((i+\delta) \omega_j\right) \\ \end{bmatrix}\\ =& \begin{bmatrix} p_{i+\delta, 2j} \\ p_{i+\delta, 2j+1} \\ \end{bmatrix}, \end{aligned}$$ where the $2\times 2$ projection matrix does not depend on any position index $i$. ## Summary In self-attention, the queries, keys, and values all come from the same place. Both CNNs and self-attention enjoy parallel computation and self-attention has the shortest maximum path length. However, the quadratic computational complexity with respect to the sequence length makes self-attention prohibitively slow for very long sequences. To use the sequence order information, we can inject absolute or relative positional information by adding positional encoding to the input representations. ## Exercises 1. Suppose that we design a deep architecture to represent a sequence by stacking self-attention layers with positional encoding. What could the possible issues be? 1. Can you design a learnable positional encoding method? 1. Can we assign different learned embeddings according to different offsets between queries and keys that are compared in self-attention? Hint: you may refer to relative position embeddings . :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " ALGKind="source" ALGId="d2l-self-attention" ALGTitle="Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding" ALGAuthor="Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola" ALGLicense="CC-BY-SA-4.0" ALGLicenseDeed="https://creativecommons.org/licenses/by-sa/4.0/" ALGURL="https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/self-attention-and-positional-encoding.md" ALGExactText="Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding Source ID: d2l-self-attention Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_attention-mechanisms-and-transformers/self-attention-and-positional-encoding.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 11.6 Self-Attention and Positional Encoding by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Self-Attention and Positional Encoding In deep learning, we often use CNNs or RNNs to encode sequences. Now with attention mechanisms in mind, imagine feeding a sequence of tokens into an attention mechanism such that at every step, each token has its own query, keys, and values. Here, when computing the value of a token's representation at the next layer, the token can attend (via its query vector) to any other's token (matching based on their key vectors). Using the full set of query-key compatibility scores, we can compute, for each token, a representation by building the appropriate weighted sum over the other tokens. Because every token is attending to each other token (unlike the case where decoder steps attend to encoder steps), such architectures are typically described as self-attention models , and elsewhere described as intra-attention model . In this section, we will discuss sequence encoding using self-attention, including using additional information for the sequence order. ## Self-Attention Given a sequence of input tokens $\mathbf{x}_1, \ldots, \mathbf{x}_n$ where any $\mathbf{x}_i \in \mathbb{R}^d$ ($1 \leq i \leq n$), its self-attention outputs a sequence of the same length $\mathbf{y}_1, \ldots, \mathbf{y}_n$, where $$\mathbf{y}_i = f(\mathbf{x}_i, (\mathbf{x}_1, \mathbf{x}_1), \ldots, (\mathbf{x}_n, \mathbf{x}_n)) \in \mathbb{R}^d$$ according to the definition of attention pooling in . Using multi-head attention, the following code snippet computes the self-attention of a tensor with shape (batch size, number of time steps or sequence length in tokens, $d$). The output tensor has the same shape. ## Comparing CNNs, RNNs, and Self-Attention Let's compare architectures for mapping a sequence of $n$ tokens to another one of equal length, where each input or output token is represented by a $d$-dimensional vector. Specifically, we will consider CNNs, RNNs, and self-attention. We will compare their computational complexity, sequential operations, and maximum path lengths. Note that sequential operations prevent parallel computation, while a shorter path between any combination of sequence positions makes it easier to learn long-range dependencies within the sequence . Comparing CNN (padding tokens are omitted), RNN, and self-attention architectures. Let's regard any text sequence as a "one-dimensional image". Similarly, one-dimensional CNNs can process local features such as $n$-grams in text. Given a sequence of length $n$, consider a convolutional layer whose kernel size is $k$, and whose numbers of input and output channels are both $d$. The computational complexity of the convolutional layer is $\mathcal{O}(knd^2)$. As shows, CNNs are hierarchical, so there are $\mathcal{O}(1)$ sequential operations and the maximum path length is $\mathcal{O}(n/k)$. For example, $\mathbf{x}_1$ and $\mathbf{x}_5$ are within the receptive field of a two-layer CNN with kernel size 3 in . When updating the hidden state of RNNs, multiplication of the $d \times d$ weight matrix and the $d$-dimensional hidden state has a computational complexity of $\mathcal{O}(d^2)$. Since the sequence length is $n$, the computational complexity of the recurrent layer is $\mathcal{O}(nd^2)$. According to , there are $\mathcal{O}(n)$ sequential operations that cannot be parallelized and the maximum path length is also $\mathcal{O}(n)$. In self-attention, the queries, keys, and values are all $n \times d$ matrices. Consider the scaled dot product attention in , where an $n \times d$ matrix is multiplied by a $d \times n$ matrix, then the output $n \times n$ matrix is multiplied by an $n \times d$ matrix. As a result, the self-attention has a $\mathcal{O}(n^2d)$ computational complexity. As we can see from , each token is directly connected to any other token via self-attention. Therefore, computation can be parallel with $\mathcal{O}(1)$ sequential operations and the maximum path length is also $\mathcal{O}(1)$. All in all, both CNNs and self-attention enjoy parallel computation and self-attention has the shortest maximum path length. However, the quadratic computational complexity with respect to the sequence length makes self-attention prohibitively slow for very long sequences. ## Positional Encoding Unlike RNNs, which recurrently process tokens of a sequence one-by-one, self-attention ditches sequential operations in favor of parallel computation. Note that self-attention by itself does not preserve the order of the sequence. What do we do if it really matters that the model knows in which order the input sequence arrived? The dominant approach for preserving information about the order of tokens is to represent this to the model as an additional input associated with each token. These inputs are called positional encodings, and they can either be learned or fixed a priori. We now describe a simple scheme for fixed positional encodings based on sine and cosine functions . Suppose that the input representation $\mathbf{X} \in \mathbb{R}^{n \times d}$ contains the $d$-dimensional embeddings for $n$ tokens of a sequence. The positional encoding outputs $\mathbf{X} + \mathbf{P}$ using a positional embedding matrix $\mathbf{P} \in \mathbb{R}^{n \times d}$ of the same shape, whose element on the $i^\textrm{th}$ row and the $(2j)^\textrm{th}$ or the $(2j + 1)^\textrm{th}$ column is $$\begin{aligned} p_{i, 2j} &= \sin\left(\frac{i}{10000^{2j/d}}\right),\\p_{i, 2j+1} &= \cos\left(\frac{i}{10000^{2j/d}}\right).\end{aligned}$$ At first glance, this trigonometric function design looks weird. Before we give explanations of this design, let's first implement it in the following PositionalEncoding class. In the positional embedding matrix $\mathbf{P}$, rows correspond to positions within a sequence and columns represent different positional encoding dimensions. In the example below, we can see that the $6^{\textrm{th}}$ and the $7^{\textrm{th}}$ columns of the positional embedding matrix have a higher frequency than the $8^{\textrm{th}}$ and the $9^{\textrm{th}}$ columns. The offset between the $6^{\textrm{th}}$ and the $7^{\textrm{th}}$ (same for the $8^{\textrm{th}}$ and the $9^{\textrm{th}}$) columns is due to the alternation of sine and cosine functions. ### Absolute Positional Information To see how the monotonically decreased frequency along the encoding dimension relates to absolute positional information, let's print out the binary representations of $0, 1, \ldots, 7$. As we can see, the lowest bit, the second-lowest bit, and the third-lowest bit alternate on every number, every two numbers, and every four numbers, respectively. In binary representations, a higher bit has a lower frequency than a lower bit. Similarly, as demonstrated in the heat map below, the positional encoding decreases frequencies along the encoding dimension by using trigonometric functions. Since the outputs are float numbers, such continuous representations are more space-efficient than binary representations. ### Relative Positional Information Besides capturing absolute positional information, the above positional encoding also allows a model to easily learn to attend by relative positions. This is because for any fixed position offset $\delta$, the positional encoding at position $i + \delta$ can be represented by a linear projection of that at position $i$. This projection can be explained mathematically. Denoting $\omega_j = 1/10000^{2j/d}$, any pair of $(p_{i, 2j}, p_{i, 2j+1})$ in can be linearly projected to $(p_{i+\delta, 2j}, p_{i+\delta, 2j+1})$ for any fixed offset $\delta$: $$\begin{aligned} \begin{bmatrix} \cos(\delta \omega_j) & \sin(\delta \omega_j) \\ -\sin(\delta \omega_j) & \cos(\delta \omega_j) \\ \end{bmatrix} \begin{bmatrix} p_{i, 2j} \\ p_{i, 2j+1} \\ \end{bmatrix} =&\begin{bmatrix} \cos(\delta \omega_j) \sin(i \omega_j) + \sin(\delta \omega_j) \cos(i \omega_j) \\ -\sin(\delta \omega_j) \sin(i \omega_j) + \cos(\delta \omega_j) \cos(i \omega_j) \\ \end{bmatrix}\\ =&\begin{bmatrix} \sin\left((i+\delta) \omega_j\right) \\ \cos\left((i+\delta) \omega_j\right) \\ \end{bmatrix}\\ =& \begin{bmatrix} p_{i+\delta, 2j} \\ p_{i+\delta, 2j+1} \\ \end{bmatrix}, \end{aligned}$$ where the $2\times 2$ projection matrix does not depend on any position index $i$. ## Summary In self-attention, the queries, keys, and values all come from the same place. Both CNNs and self-attention enjoy parallel computation and self-attention has the shortest maximum path length. However, the quadratic computational complexity with respect to the sequence length makes self-attention prohibitively slow for very long sequences. To use the sequence order information, we can inject absolute or relative positional information by adding positional encoding to the input representations. ## Exercises 1. Suppose that we design a deep architecture to represent a sequence by stacking self-attention layers with positional encoding. What could the possible issues be? 1. Can you design a learnable positional encoding method? 1. Can we assign different learned embeddings according to different offsets between queries and keys that are compared in self-attention? Hint: you may refer to relative position embeddings . :begin_tab:mxnet Discussions :end_tab: :begin_tab:pytorch Discussions :end_tab: :begin_tab:tensorflow Discussions :end_tab: :begin_tab:jax Discussions :end_tab: " Prototype="ALG Source" Color="#7CB7C9" Shape="rounded" Badge="doc.text" Width="6" Height="2.5" BorderColor="#264653" Xpos="13" Ypos="4" ALGXpos="13" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGLicense;ALGURL"/>
<outline text="Dive into Deep Learning — 4.1 Softmax Regression" _note="Dive into Deep Learning -- 4.1 Softmax Regression Source ID: d2l-softmax-regression Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_linear-classification/softmax-regression.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning -- 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Softmax Regression In , we introduced linear regression, working through implementations from scratch in and again using high-level APIs of a deep learning framework in to do the heavy lifting. Regression is the hammer we reach for when we want to answer how much? or how many? questions. If you want to predict the number of dollars (price) at which a house will be sold, or the number of wins a baseball team might have, or the number of days that a patient will remain hospitalized before being discharged, then you are probably looking for a regression model. However, even within regression models, there are important distinctions. For instance, the price of a house will never be negative and changes might often be relative to its baseline price. As such, it might be more effective to regress on the logarithm of the price. Likewise, the number of days a patient spends in hospital is a discrete nonnegative random variable. As such, least mean squares might not be an ideal approach either. This sort of time-to-event modeling comes with a host of other complications that are dealt with in a specialized subfield called survival modeling. The point here is not to overwhelm you but just to let you know that there is a lot more to estimation than simply minimizing squared errors. And more broadly, there is a lot more to supervised learning than regression. In this section, we focus on classification problems where we put aside how much? questions and instead focus on which category? questions. Does this email belong in the spam folder or the inbox? Is this customer more likely to sign up or not to sign up for a subscription service? Does this image depict a donkey, a dog, a cat, or a rooster? Which movie is Aston most likely to watch next? Which section of the book are you going to read next? Colloquially, machine learning practitioners overload the word classification to describe two subtly different problems: (i) those where we are interested only in hard assignments of examples to categories (classes); and (ii) those where we wish to make soft assignments, i.e., to assess the probability that each category applies. The distinction tends to get blurred, in part, because often, even when we only care about hard assignments, we still use models that make soft assignments. Even more, there are cases where more than one label might be true. For instance, a news article might simultaneously cover the topics of entertainment, business, and space flight, but not the topics of medicine or sports. Thus, categorizing it into one of the above categories on their own would not be very useful. This problem is commonly known as multi-label classification. See for an overview and for an effective algorithm when tagging images. ## Classification To get our feet wet, let's start with a simple image classification problem. Here, each input consists of a $2\times2$ grayscale image. We can represent each pixel value with a single scalar, giving us four features $x_1, x_2, x_3, x_4$. Further, let's assume that each image belongs to one among the categories "cat", "chicken", and "dog". Next, we have to choose how to represent the labels. We have two obvious choices. Perhaps the most natural impulse would be to choose $y \in \{1, 2, 3\}$, where the integers represent $\{\textrm{dog}, \textrm{cat}, \textrm{chicken}\}$ respectively. This is a great way of storing such information on a computer. If the categories had some natural ordering among them, say if we were trying to predict $\{\textrm{baby}, \textrm{toddler}, \textrm{adolescent}, \textrm{young adult}, \textrm{adult}, \textrm{geriatric}\}$, then it might even make sense to cast this as an ordinal regression problem and keep the labels in this format. See for an overview of different types of ranking loss functions and for a Bayesian approach that addresses responses with more than one mode. In general, classification problems do not come with natural orderings among the classes. Fortunately, statisticians long ago invented a simple way to represent categorical data: the one-hot encoding. A one-hot encoding is a vector with as many components as we have categories. The component corresponding to a particular instance's category is set to 1 and all other components are set to 0. In our case, a label $y$ would be a three-dimensional vector, with $(1, 0, 0)$ corresponding to "cat", $(0, 1, 0)$ to "chicken", and $(0, 0, 1)$ to "dog": $$y \in \{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}.$$ ### Linear Model In order to estimate the conditional probabilities associated with all the possible classes, we need a model with multiple outputs, one per class. To address classification with linear models, we will need as many affine functions as we have outputs. Strictly speaking, we only need one fewer, since the final category has to be the difference between $1$ and the sum of the other categories, but for reasons of symmetry we use a slightly redundant parametrization. Each output corresponds to its own affine function. In our case, since we have 4 features and 3 possible output categories, we need 12 scalars to represent the weights ($w$ with subscripts), and 3 scalars to represent the biases ($b$ with subscripts). This yields: $$ \begin{aligned} o_1 &= x_1 w_{11} + x_2 w_{12} + x_3 w_{13} + x_4 w_{14} + b_1,\\ o_2 &= x_1 w_{21} + x_2 w_{22} + x_3 w_{23} + x_4 w_{24} + b_2,\\ o_3 &= x_1 w_{31} + x_2 w_{32} + x_3 w_{33} + x_4 w_{34} + b_3. \end{aligned} $$ The corresponding neural network diagram is shown in . Just as in linear regression, we use a single-layer neural network. And since the calculation of each output, $o_1, o_2$, and $o_3$, depends on every input, $x_1$, $x_2$, $x_3$, and $x_4$, the output layer can also be described as a fully connected layer. Softmax regression is a single-layer neural network. For a more concise notation we use vectors and matrices: $\mathbf{o} = \mathbf{W} \mathbf{x} + \mathbf{b}$ is much better suited for mathematics and code. Note that we have gathered all of our weights into a $3 \times 4$ matrix and all biases $\mathbf{b} \in \mathbb{R}^3$ in a vector. ### The Softmax Assuming a suitable loss function, we could try, directly, to minimize the difference between $\mathbf{o}$ and the labels $\mathbf{y}$. While it turns out that treating classification as a vector-valued regression problem works surprisingly well, it is nonetheless unsatisfactory in the following ways: There is no guarantee that the outputs $o_i$ sum up to $1$ in the way we expect probabilities to behave. There is no guarantee that the outputs $o_i$ are even nonnegative, even if their outputs sum up to $1$, or that they do not exceed $1$. Both aspects render the estimation problem difficult to solve and the solution very brittle to outliers. For instance, if we assume that there is a positive linear dependency between the number of bedrooms and the likelihood that someone will buy a house, the probability might exceed $1$ when it comes to buying a mansion! As such, we need a mechanism to "squish" the outputs. There are many ways we might accomplish this goal. For instance, we could assume that the outputs $\mathbf{o}$ are corrupted versions of $\mathbf{y}$, where the corruption occurs by means of adding noise $\boldsymbol{\epsilon}$ drawn from a normal distribution. In other words, $\mathbf{y} = \mathbf{o} + \boldsymbol{\epsilon}$, where $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$. This is the so-called probit model, first introduced by . While appealing, it does not work quite as well nor lead to a particularly nice optimization problem, when compared to the softmax. Another way to accomplish this goal (and to ensure nonnegativity) is to use an exponential function $P(y = i) \propto \exp o_i$. This does indeed satisfy the requirement that the conditional class probability increases with increasing $o_i$, it is monotonic, and all probabilities are nonnegative. We can then transform these values so that they add up to $1$ by dividing each by their sum. This process is called normalization. Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Note that the largest coordinate of $\mathbf{o}$ corresponds to the most likely class according to $\hat{\mathbf{y}}$. Moreover, because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Thus, $$ \operatorname*{argmax}_j \hat y_j = \operatorname*{argmax}_j o_j. $$ The idea of a softmax dates back to , who adapted ideas from physics. Dating even further back, Boltzmann, the father of modern statistical physics, used this trick to model a distribution over energy states in gas molecules. In particular, he discovered that the prevalence of a state of energy in a thermodynamic ensemble, such as the molecules in a gas, is proportional to $\exp(-E/kT)$. Here, $E$ is the energy of a state, $T$ is the temperature, and $k$ is the Boltzmann constant. When statisticians talk about increasing or decreasing the "temperature" of a statistical system, they refer to changing $T$ in order to favor lower or higher energy states. Following Gibbs' idea, energy equates to error. Energy-based models use this point of view when describing problems in deep learning. ### Vectorization To improve computational efficiency, we vectorize calculations in minibatches of data. Assume that we are given a minibatch $\mathbf{X} \in \mathbb{R}^{n \times d}$ of $n$ examples with dimensionality (number of inputs) $d$. Moreover, assume that we have $q$ categories in the output. Then the weights satisfy $\mathbf{W} \in \mathbb{R}^{d \times q}$ and the bias satisfies $\mathbf{b} \in \mathbb{R}^{1\times q}$. $$ \begin{aligned} \mathbf{O} &= \mathbf{X} \mathbf{W} + \mathbf{b}, \\ \hat{\mathbf{Y}} & = \mathrm{softmax}(\mathbf{O}). \end{aligned} $$ This accelerates the dominant operation into a matrix--matrix product $\mathbf{X} \mathbf{W}$. Moreover, since each row in $\mathbf{X}$ represents a data example, the softmax operation itself can be computed rowwise: for each row of $\mathbf{O}$, exponentiate all entries and then normalize them by the sum. Note, though, that care must be taken to avoid exponentiating and taking logarithms of large numbers, since this can cause numerical overflow or underflow. Deep learning frameworks take care of this automatically. ## Loss Function Now that we have a mapping from features $\mathbf{x}$ to probabilities $\mathbf{\hat{y}}$, we need a way to optimize the accuracy of this mapping. We will rely on maximum likelihood estimation, the very same method that we encountered when providing a probabilistic justification for the mean squared error loss in . ### Log-Likelihood The softmax function gives us a vector $\hat{\mathbf{y}}$, which we can interpret as the (estimated) conditional probabilities of each class, given any input $\mathbf{x}$, such as $\hat{y}_1$ = $P(y=\textrm{cat} \mid \mathbf{x})$. In the following we assume that for a dataset with features $\mathbf{X}$ the labels $\mathbf{Y}$ are represented using a one-hot encoding label vector. We can compare the estimates with reality by checking how probable the actual classes are according to our model, given the features: $$ P(\mathbf{Y} \mid \mathbf{X}) = \prod_{i=1}^n P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}). $$ We are allowed to use the factorization since we assume that each label is drawn independently from its respective distribution $P(\mathbf{y}\mid\mathbf{x}^{(i)})$. Since maximizing the product of terms is awkward, we take the negative logarithm to obtain the equivalent problem of minimizing the negative log-likelihood: $$ -\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i=1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i=1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}), $$ where for any pair of label $\mathbf{y}$ and model prediction $\hat{\mathbf{y}}$ over $q$ classes, the loss function $l$ is $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j. $$ For reasons explained later on, the loss function in is commonly called the cross-entropy loss. Since $\mathbf{y}$ is a one-hot vector of length $q$, the sum over all its coordinates $j$ vanishes for all but one term. Note that the loss $l(\mathbf{y}, \hat{\mathbf{y}})$ is bounded from below by $0$ whenever $\hat{\mathbf{y}}$ is a probability vector: no single entry is larger than $1$, hence their negative logarithm cannot be lower than $0$; $l(\mathbf{y}, \hat{\mathbf{y}}) = 0$ only if we predict the actual label with certainty. This can never happen for any finite setting of the weights because taking a softmax output towards $1$ requires taking the corresponding input $o_i$ to infinity (or all other outputs $o_j$ for $j \neq i$ to negative infinity). Even if our model could assign an output probability of $0$, any error made when assigning such high confidence would incur infinite loss ($-\log 0 = \infty$). ### Softmax and Cross-Entropy Loss Since the softmax function and the corresponding cross-entropy loss are so common, it is worth understanding a bit better how they are computed. Plugging into the definition of the loss in and using the definition of the softmax we obtain $$ \begin{aligned} l(\mathbf{y}, \hat{\mathbf{y}}) &= - \sum_{j=1}^q y_j \log \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} \\ &= \sum_{j=1}^q y_j \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j \\ &= \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j. \end{aligned} $$ To understand a bit better what is going on, consider the derivative with respect to any logit $o_j$. We get $$ \partial_{o_j} l(\mathbf{y}, \hat{\mathbf{y}}) = \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} - y_j = \mathrm{softmax}(\mathbf{o})_j - y_j. $$ In other words, the derivative is the difference between the probability assigned by our model, as expressed by the softmax operation, and what actually happened, as expressed by elements in the one-hot label vector. In this sense, it is very similar to what we saw in regression, where the gradient was the difference between the observation $y$ and estimate $\hat{y}$. This is not a coincidence. In any exponential family model, the gradients of the log-likelihood are given by precisely this term. This fact makes computing gradients easy in practice. Now consider the case where we observe not just a single outcome but an entire distribution over outcomes. We can use the same representation as before for the label $\mathbf{y}$. The only difference is that rather than a vector containing only binary entries, say $(0, 0, 1)$, we now have a generic probability vector, say $(0.1, 0.2, 0.7)$. The math that we used previously to define the loss $l$ in still works well, just that the interpretation is slightly more general. It is the expected value of the loss for a distribution over labels. This loss is called the cross-entropy loss and it is one of the most commonly used losses for classification problems. We can demystify the name by introducing just the basics of information theory. In a nutshell, it measures the number of bits needed to encode what we see, $\mathbf{y}$, relative to what we predict that should happen, $\hat{\mathbf{y}}$. We provide a very basic explanation in the following. For further details on information theory see or . ## Information Theory Basics Many deep learning papers use intuition and terms from information theory. To make sense of them, we need some common language. This is a survival guide. Information theory deals with the problem of encoding, decoding, transmitting, and manipulating information (also known as data). ### Entropy The central idea in information theory is to quantify the amount of information contained in data. This places a limit on our ability to compress data. For a distribution $P$ its entropy, $H[P]$, is defined as: $$H[P] = \sum_j - P(j) \log P(j).$$ One of the fundamental theorems of information theory states that in order to encode data drawn randomly from the distribution $P$, we need at least $H[P]$ "nats" to encode it . If you wonder what a "nat" is, it is the equivalent of bit but when using a code with base $e$ rather than one with base 2. Thus, one nat is $\frac{1}{\log(2)} \approx 1.44$ bit. ### Surprisal You might be wondering what compression has to do with prediction. Imagine that we have a stream of data that we want to compress. If it is always easy for us to predict the next token, then this data is easy to compress. Take the extreme example where every token in the stream always takes the same value. That is a very boring data stream! And not only it is boring, but it is also easy to predict. Because the tokens are always the same, we do not have to transmit any information to communicate the contents of the stream. Easy to predict, easy to compress. However if we cannot perfectly predict every event, then we might sometimes be surprised. Our surprise is greater when an event is assigned lower probability. Claude Shannon settled on $\log \frac{1}{P(j)} = -\log P(j)$ to quantify one's surprisal at observing an event $j$ having assigned it a (subjective) probability $P(j)$. The entropy defined in is then the expected surprisal when one assigned the correct probabilities that truly match the data-generating process. ### Cross-Entropy Revisited So if entropy is the level of surprise experienced by someone who knows the true probability, then you might be wondering, what is cross-entropy? The cross-entropy from $P$ to $Q$, denoted $H(P, Q)$, is the expected surprisal of an observer with subjective probabilities $Q$ upon seeing data that was actually generated according to probabilities $P$. This is given by $H(P, Q) \stackrel{\textrm{def}}{=} \sum_j - P(j) \log Q(j)$. The lowest possible cross-entropy is achieved when $P=Q$. In this case, the cross-entropy from $P$ to $Q$ is $H(P, P)= H(P)$. In short, we can think of the cross-entropy classification objective in two ways: (i) as maximizing the likelihood of the observed data; and (ii) as minimizing our surprisal (and thus the number of bits) required to communicate the labels. ## Summary and Discussion In this section, we encountered the first nontrivial loss function, allowing us to optimize over discrete output spaces. Key in its design was that we took a probabilistic approach, treating discrete categories as instances of draws from a probability distribution. As a side effect, we encountered the softmax, a convenient activation function that transforms outputs of an ordinary neural network layer into valid discrete probability distributions. We saw that the derivative of the cross-entropy loss when combined with softmax behaves very similarly to the derivative of squared error; namely by taking the difference between the expected behavior and its prediction. And, while we were only able to scratch the very surface of it, we encountered exciting connections to statistical physics and information theory. While this is enough to get you on your way, and hopefully enough to whet your appetite, we hardly dived deep here. Among other things, we skipped over computational considerations. Specifically, for any fully connected layer with $d$ inputs and $q$ outputs, the parametrization and computational cost is $\mathcal{O}(dq)$, which can be prohibitively high in practice. Fortunately, this cost of transforming $d$ inputs into $q$ outputs can be reduced through approximation and compression. For instance Deep Fried Convnets uses a combination of permutations, Fourier transforms, and scaling to reduce the cost from quadratic to log-linear. Similar techniques work for more advanced structural matrix approximations . Lastly, we can use quaternion-like decompositions to reduce the cost to $\mathcal{O}(\frac{dq}{n})$, again if we are willing to trade off a small amount of accuracy for computational and storage cost based on a compression factor $n$. This is an active area of research. What makes it challenging is that we do not necessarily strive for the most compact representation or the smallest number of floating point operations but rather for the solution that can be executed most efficiently on modern GPUs. ## Exercises 1. We can explore the connection between exponential families and softmax in some more depth. 1. Compute the second derivative of the cross-entropy loss $l(\mathbf{y},\hat{\mathbf{y}})$ for softmax. 1. Compute the variance of the distribution given by $\mathrm{softmax}(\mathbf{o})$ and show that it matches the second derivative computed above. 1. Assume that we have three classes which occur with equal probability, i.e., the probability vector is $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$. 1. What is the problem if we try to design a binary code for it? 1. Can you design a better code? Hint: what happens if we try to encode two independent observations? What if we encode $n$ observations jointly? 1. When encoding signals transmitted over a physical wire, engineers do not always use binary codes. For instance, PAM-3 uses three signal levels $\{-1, 0, 1\}$ as opposed to two levels $\{0, 1\}$. How many ternary units do you need to transmit an integer in the range $\{0, \ldots, 7\}$? Why might this be a better idea in terms of electronics? 1. The Bradley--Terry model uses a logistic model to capture preferences. For a user to choose between apples and oranges one assumes scores $o_{\textrm{apple}}$ and $o_{\textrm{orange}}$. Our requirements are that larger scores should lead to a higher likelihood in choosing the associated item and that the item with the largest score is the most likely one to be chosen . 1. Prove that softmax satisfies this requirement. 1. What happens if you want to allow for a default option of choosing neither apples nor oranges? Hint: now the user has three choices. 1. Softmax gets its name from the following mapping: $\textrm{RealSoftMax}(a, b) = \log (\exp(a) + \exp(b))$. 1. Prove that $\textrm{RealSoftMax}(a, b) > \mathrm{max}(a, b)$. 1. How small can you make the difference between both functions? Hint: without loss of generality you can set $b = 0$ and $a \geq b$. 1. Prove that this holds for $\lambda^{-1} \textrm{RealSoftMax}(\lambda a, \lambda b)$, provided that $\lambda > 0$. 1. Show that for $\lambda \to \infty$ we have $\lambda^{-1} \textrm{RealSoftMax}(\lambda a, \lambda b) \to \mathrm{max}(a, b)$. 1. Construct an analogous softmin function. 1. Extend this to more than two numbers. 1. The function $g(\mathbf{x}) \stackrel{\textrm{def}}{=} \log \sum_i \exp x_i$ is sometimes also referred to as the log-partition function). 1. Prove that the function is convex. Hint: to do so, use the fact that the first derivative amounts to the probabilities from the softmax function and show that the second derivative is the variance. 1. Show that $g$ is translation invariant, i.e., $g(\mathbf{x} + b) = g(\mathbf{x})$. 1. What happens if some of the coordinates $x_i$ are very large? What happens if they're all very small? 1. Show that if we choose $b = \mathrm{max}_i x_i$ we end up with a numerically stable implementation. 1. Assume that we have some probability distribution $P$. Suppose we pick another distribution $Q$ with $Q(i) \propto P(i)^\alpha$ for $\alpha > 0$. 1. Which choice of $\alpha$ corresponds to doubling the temperature? Which choice corresponds to halving it? 1. What happens if we let the temperature approach $0$? 1. What happens if we let the temperature approach $\infty$? Discussions " ALGKind="source" ALGId="d2l-softmax-regression" ALGTitle="Dive into Deep Learning — 4.1 Softmax Regression" ALGAuthor="Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola" ALGLicense="CC-BY-SA-4.0" ALGLicenseDeed="https://creativecommons.org/licenses/by-sa/4.0/" ALGURL="https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_linear-classification/softmax-regression.md" ALGExactText="Dive into Deep Learning — 4.1 Softmax Regression Source ID: d2l-softmax-regression Author: Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola License: CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/) URL: https://github.com/d2l-ai/d2l-en/blob/b2e2ae30898a9d0126a9699ae7e441de3e272715/chapter_linear-classification/softmax-regression.md Modification notice: Adapted (translated to plain English; atomized into concept lessons) from Dive into Deep Learning — 4.1 Softmax Regression by Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola, CC-BY-SA-4.0 (https://creativecommons.org/licenses/by-sa/4.0/). Source text # Softmax Regression In , we introduced linear regression, working through implementations from scratch in and again using high-level APIs of a deep learning framework in to do the heavy lifting. Regression is the hammer we reach for when we want to answer how much? or how many? questions. If you want to predict the number of dollars (price) at which a house will be sold, or the number of wins a baseball team might have, or the number of days that a patient will remain hospitalized before being discharged, then you are probably looking for a regression model. However, even within regression models, there are important distinctions. For instance, the price of a house will never be negative and changes might often be relative to its baseline price. As such, it might be more effective to regress on the logarithm of the price. Likewise, the number of days a patient spends in hospital is a discrete nonnegative random variable. As such, least mean squares might not be an ideal approach either. This sort of time-to-event modeling comes with a host of other complications that are dealt with in a specialized subfield called survival modeling. The point here is not to overwhelm you but just to let you know that there is a lot more to estimation than simply minimizing squared errors. And more broadly, there is a lot more to supervised learning than regression. In this section, we focus on classification problems where we put aside how much? questions and instead focus on which category? questions. Does this email belong in the spam folder or the inbox? Is this customer more likely to sign up or not to sign up for a subscription service? Does this image depict a donkey, a dog, a cat, or a rooster? Which movie is Aston most likely to watch next? Which section of the book are you going to read next? Colloquially, machine learning practitioners overload the word classification to describe two subtly different problems: (i) those where we are interested only in hard assignments of examples to categories (classes); and (ii) those where we wish to make soft assignments, i.e., to assess the probability that each category applies. The distinction tends to get blurred, in part, because often, even when we only care about hard assignments, we still use models that make soft assignments. Even more, there are cases where more than one label might be true. For instance, a news article might simultaneously cover the topics of entertainment, business, and space flight, but not the topics of medicine or sports. Thus, categorizing it into one of the above categories on their own would not be very useful. This problem is commonly known as multi-label classification. See for an overview and for an effective algorithm when tagging images. ## Classification To get our feet wet, let's start with a simple image classification problem. Here, each input consists of a $2\times2$ grayscale image. We can represent each pixel value with a single scalar, giving us four features $x_1, x_2, x_3, x_4$. Further, let's assume that each image belongs to one among the categories "cat", "chicken", and "dog". Next, we have to choose how to represent the labels. We have two obvious choices. Perhaps the most natural impulse would be to choose $y \in \{1, 2, 3\}$, where the integers represent $\{\textrm{dog}, \textrm{cat}, \textrm{chicken}\}$ respectively. This is a great way of storing such information on a computer. If the categories had some natural ordering among them, say if we were trying to predict $\{\textrm{baby}, \textrm{toddler}, \textrm{adolescent}, \textrm{young adult}, \textrm{adult}, \textrm{geriatric}\}$, then it might even make sense to cast this as an ordinal regression problem and keep the labels in this format. See for an overview of different types of ranking loss functions and for a Bayesian approach that addresses responses with more than one mode. In general, classification problems do not come with natural orderings among the classes. Fortunately, statisticians long ago invented a simple way to represent categorical data: the one-hot encoding. A one-hot encoding is a vector with as many components as we have categories. The component corresponding to a particular instance's category is set to 1 and all other components are set to 0. In our case, a label $y$ would be a three-dimensional vector, with $(1, 0, 0)$ corresponding to "cat", $(0, 1, 0)$ to "chicken", and $(0, 0, 1)$ to "dog": $$y \in \{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}.$$ ### Linear Model In order to estimate the conditional probabilities associated with all the possible classes, we need a model with multiple outputs, one per class. To address classification with linear models, we will need as many affine functions as we have outputs. Strictly speaking, we only need one fewer, since the final category has to be the difference between $1$ and the sum of the other categories, but for reasons of symmetry we use a slightly redundant parametrization. Each output corresponds to its own affine function. In our case, since we have 4 features and 3 possible output categories, we need 12 scalars to represent the weights ($w$ with subscripts), and 3 scalars to represent the biases ($b$ with subscripts). This yields: $$ \begin{aligned} o_1 &= x_1 w_{11} + x_2 w_{12} + x_3 w_{13} + x_4 w_{14} + b_1,\\ o_2 &= x_1 w_{21} + x_2 w_{22} + x_3 w_{23} + x_4 w_{24} + b_2,\\ o_3 &= x_1 w_{31} + x_2 w_{32} + x_3 w_{33} + x_4 w_{34} + b_3. \end{aligned} $$ The corresponding neural network diagram is shown in . Just as in linear regression, we use a single-layer neural network. And since the calculation of each output, $o_1, o_2$, and $o_3$, depends on every input, $x_1$, $x_2$, $x_3$, and $x_4$, the output layer can also be described as a fully connected layer. Softmax regression is a single-layer neural network. For a more concise notation we use vectors and matrices: $\mathbf{o} = \mathbf{W} \mathbf{x} + \mathbf{b}$ is much better suited for mathematics and code. Note that we have gathered all of our weights into a $3 \times 4$ matrix and all biases $\mathbf{b} \in \mathbb{R}^3$ in a vector. ### The Softmax Assuming a suitable loss function, we could try, directly, to minimize the difference between $\mathbf{o}$ and the labels $\mathbf{y}$. While it turns out that treating classification as a vector-valued regression problem works surprisingly well, it is nonetheless unsatisfactory in the following ways: There is no guarantee that the outputs $o_i$ sum up to $1$ in the way we expect probabilities to behave. There is no guarantee that the outputs $o_i$ are even nonnegative, even if their outputs sum up to $1$, or that they do not exceed $1$. Both aspects render the estimation problem difficult to solve and the solution very brittle to outliers. For instance, if we assume that there is a positive linear dependency between the number of bedrooms and the likelihood that someone will buy a house, the probability might exceed $1$ when it comes to buying a mansion! As such, we need a mechanism to "squish" the outputs. There are many ways we might accomplish this goal. For instance, we could assume that the outputs $\mathbf{o}$ are corrupted versions of $\mathbf{y}$, where the corruption occurs by means of adding noise $\boldsymbol{\epsilon}$ drawn from a normal distribution. In other words, $\mathbf{y} = \mathbf{o} + \boldsymbol{\epsilon}$, where $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$. This is the so-called probit model, first introduced by . While appealing, it does not work quite as well nor lead to a particularly nice optimization problem, when compared to the softmax. Another way to accomplish this goal (and to ensure nonnegativity) is to use an exponential function $P(y = i) \propto \exp o_i$. This does indeed satisfy the requirement that the conditional class probability increases with increasing $o_i$, it is monotonic, and all probabilities are nonnegative. We can then transform these values so that they add up to $1$ by dividing each by their sum. This process is called normalization. Putting these two pieces together gives us the softmax function: $$\hat{\mathbf{y}} = \mathrm{softmax}(\mathbf{o}) \quad \textrm{where}\quad \hat{y}_i = \frac{\exp(o_i)}{\sum_j \exp(o_j)}.$$ Note that the largest coordinate of $\mathbf{o}$ corresponds to the most likely class according to $\hat{\mathbf{y}}$. Moreover, because the softmax operation preserves the ordering among its arguments, we do not need to compute the softmax to determine which class has been assigned the highest probability. Thus, $$ \operatorname*{argmax}_j \hat y_j = \operatorname*{argmax}_j o_j. $$ The idea of a softmax dates back to , who adapted ideas from physics. Dating even further back, Boltzmann, the father of modern statistical physics, used this trick to model a distribution over energy states in gas molecules. In particular, he discovered that the prevalence of a state of energy in a thermodynamic ensemble, such as the molecules in a gas, is proportional to $\exp(-E/kT)$. Here, $E$ is the energy of a state, $T$ is the temperature, and $k$ is the Boltzmann constant. When statisticians talk about increasing or decreasing the "temperature" of a statistical system, they refer to changing $T$ in order to favor lower or higher energy states. Following Gibbs' idea, energy equates to error. Energy-based models use this point of view when describing problems in deep learning. ### Vectorization To improve computational efficiency, we vectorize calculations in minibatches of data. Assume that we are given a minibatch $\mathbf{X} \in \mathbb{R}^{n \times d}$ of $n$ examples with dimensionality (number of inputs) $d$. Moreover, assume that we have $q$ categories in the output. Then the weights satisfy $\mathbf{W} \in \mathbb{R}^{d \times q}$ and the bias satisfies $\mathbf{b} \in \mathbb{R}^{1\times q}$. $$ \begin{aligned} \mathbf{O} &= \mathbf{X} \mathbf{W} + \mathbf{b}, \\ \hat{\mathbf{Y}} & = \mathrm{softmax}(\mathbf{O}). \end{aligned} $$ This accelerates the dominant operation into a matrix--matrix product $\mathbf{X} \mathbf{W}$. Moreover, since each row in $\mathbf{X}$ represents a data example, the softmax operation itself can be computed rowwise: for each row of $\mathbf{O}$, exponentiate all entries and then normalize them by the sum. Note, though, that care must be taken to avoid exponentiating and taking logarithms of large numbers, since this can cause numerical overflow or underflow. Deep learning frameworks take care of this automatically. ## Loss Function Now that we have a mapping from features $\mathbf{x}$ to probabilities $\mathbf{\hat{y}}$, we need a way to optimize the accuracy of this mapping. We will rely on maximum likelihood estimation, the very same method that we encountered when providing a probabilistic justification for the mean squared error loss in . ### Log-Likelihood The softmax function gives us a vector $\hat{\mathbf{y}}$, which we can interpret as the (estimated) conditional probabilities of each class, given any input $\mathbf{x}$, such as $\hat{y}_1$ = $P(y=\textrm{cat} \mid \mathbf{x})$. In the following we assume that for a dataset with features $\mathbf{X}$ the labels $\mathbf{Y}$ are represented using a one-hot encoding label vector. We can compare the estimates with reality by checking how probable the actual classes are according to our model, given the features: $$ P(\mathbf{Y} \mid \mathbf{X}) = \prod_{i=1}^n P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}). $$ We are allowed to use the factorization since we assume that each label is drawn independently from its respective distribution $P(\mathbf{y}\mid\mathbf{x}^{(i)})$. Since maximizing the product of terms is awkward, we take the negative logarithm to obtain the equivalent problem of minimizing the negative log-likelihood: $$ -\log P(\mathbf{Y} \mid \mathbf{X}) = \sum_{i=1}^n -\log P(\mathbf{y}^{(i)} \mid \mathbf{x}^{(i)}) = \sum_{i=1}^n l(\mathbf{y}^{(i)}, \hat{\mathbf{y}}^{(i)}), $$ where for any pair of label $\mathbf{y}$ and model prediction $\hat{\mathbf{y}}$ over $q$ classes, the loss function $l$ is $$ l(\mathbf{y}, \hat{\mathbf{y}}) = - \sum_{j=1}^q y_j \log \hat{y}_j. $$ For reasons explained later on, the loss function in is commonly called the cross-entropy loss. Since $\mathbf{y}$ is a one-hot vector of length $q$, the sum over all its coordinates $j$ vanishes for all but one term. Note that the loss $l(\mathbf{y}, \hat{\mathbf{y}})$ is bounded from below by $0$ whenever $\hat{\mathbf{y}}$ is a probability vector: no single entry is larger than $1$, hence their negative logarithm cannot be lower than $0$; $l(\mathbf{y}, \hat{\mathbf{y}}) = 0$ only if we predict the actual label with certainty. This can never happen for any finite setting of the weights because taking a softmax output towards $1$ requires taking the corresponding input $o_i$ to infinity (or all other outputs $o_j$ for $j \neq i$ to negative infinity). Even if our model could assign an output probability of $0$, any error made when assigning such high confidence would incur infinite loss ($-\log 0 = \infty$). ### Softmax and Cross-Entropy Loss Since the softmax function and the corresponding cross-entropy loss are so common, it is worth understanding a bit better how they are computed. Plugging into the definition of the loss in and using the definition of the softmax we obtain $$ \begin{aligned} l(\mathbf{y}, \hat{\mathbf{y}}) &= - \sum_{j=1}^q y_j \log \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} \\ &= \sum_{j=1}^q y_j \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j \\ &= \log \sum_{k=1}^q \exp(o_k) - \sum_{j=1}^q y_j o_j. \end{aligned} $$ To understand a bit better what is going on, consider the derivative with respect to any logit $o_j$. We get $$ \partial_{o_j} l(\mathbf{y}, \hat{\mathbf{y}}) = \frac{\exp(o_j)}{\sum_{k=1}^q \exp(o_k)} - y_j = \mathrm{softmax}(\mathbf{o})_j - y_j. $$ In other words, the derivative is the difference between the probability assigned by our model, as expressed by the softmax operation, and what actually happened, as expressed by elements in the one-hot label vector. In this sense, it is very similar to what we saw in regression, where the gradient was the difference between the observation $y$ and estimate $\hat{y}$. This is not a coincidence. In any exponential family model, the gradients of the log-likelihood are given by precisely this term. This fact makes computing gradients easy in practice. Now consider the case where we observe not just a single outcome but an entire distribution over outcomes. We can use the same representation as before for the label $\mathbf{y}$. The only difference is that rather than a vector containing only binary entries, say $(0, 0, 1)$, we now have a generic probability vector, say $(0.1, 0.2, 0.7)$. The math that we used previously to define the loss $l$ in still works well, just that the interpretation is slightly more general. It is the expected value of the loss for a distribution over labels. This loss is called the cross-entropy loss and it is one of the most commonly used losses for classification problems. We can demystify the name by introducing just the basics of information theory. In a nutshell, it measures the number of bits needed to encode what we see, $\mathbf{y}$, relative to what we predict that should happen, $\hat{\mathbf{y}}$. We provide a very basic explanation in the following. For further details on information theory see or . ## Information Theory Basics Many deep learning papers use intuition and terms from information theory. To make sense of them, we need some common language. This is a survival guide. Information theory deals with the problem of encoding, decoding, transmitting, and manipulating information (also known as data). ### Entropy The central idea in information theory is to quantify the amount of information contained in data. This places a limit on our ability to compress data. For a distribution $P$ its entropy, $H[P]$, is defined as: $$H[P] = \sum_j - P(j) \log P(j).$$ One of the fundamental theorems of information theory states that in order to encode data drawn randomly from the distribution $P$, we need at least $H[P]$ "nats" to encode it . If you wonder what a "nat" is, it is the equivalent of bit but when using a code with base $e$ rather than one with base 2. Thus, one nat is $\frac{1}{\log(2)} \approx 1.44$ bit. ### Surprisal You might be wondering what compression has to do with prediction. Imagine that we have a stream of data that we want to compress. If it is always easy for us to predict the next token, then this data is easy to compress. Take the extreme example where every token in the stream always takes the same value. That is a very boring data stream! And not only it is boring, but it is also easy to predict. Because the tokens are always the same, we do not have to transmit any information to communicate the contents of the stream. Easy to predict, easy to compress. However if we cannot perfectly predict every event, then we might sometimes be surprised. Our surprise is greater when an event is assigned lower probability. Claude Shannon settled on $\log \frac{1}{P(j)} = -\log P(j)$ to quantify one's surprisal at observing an event $j$ having assigned it a (subjective) probability $P(j)$. The entropy defined in is then the expected surprisal when one assigned the correct probabilities that truly match the data-generating process. ### Cross-Entropy Revisited So if entropy is the level of surprise experienced by someone who knows the true probability, then you might be wondering, what is cross-entropy? The cross-entropy from $P$ to $Q$, denoted $H(P, Q)$, is the expected surprisal of an observer with subjective probabilities $Q$ upon seeing data that was actually generated according to probabilities $P$. This is given by $H(P, Q) \stackrel{\textrm{def}}{=} \sum_j - P(j) \log Q(j)$. The lowest possible cross-entropy is achieved when $P=Q$. In this case, the cross-entropy from $P$ to $Q$ is $H(P, P)= H(P)$. In short, we can think of the cross-entropy classification objective in two ways: (i) as maximizing the likelihood of the observed data; and (ii) as minimizing our surprisal (and thus the number of bits) required to communicate the labels. ## Summary and Discussion In this section, we encountered the first nontrivial loss function, allowing us to optimize over discrete output spaces. Key in its design was that we took a probabilistic approach, treating discrete categories as instances of draws from a probability distribution. As a side effect, we encountered the softmax, a convenient activation function that transforms outputs of an ordinary neural network layer into valid discrete probability distributions. We saw that the derivative of the cross-entropy loss when combined with softmax behaves very similarly to the derivative of squared error; namely by taking the difference between the expected behavior and its prediction. And, while we were only able to scratch the very surface of it, we encountered exciting connections to statistical physics and information theory. While this is enough to get you on your way, and hopefully enough to whet your appetite, we hardly dived deep here. Among other things, we skipped over computational considerations. Specifically, for any fully connected layer with $d$ inputs and $q$ outputs, the parametrization and computational cost is $\mathcal{O}(dq)$, which can be prohibitively high in practice. Fortunately, this cost of transforming $d$ inputs into $q$ outputs can be reduced through approximation and compression. For instance Deep Fried Convnets uses a combination of permutations, Fourier transforms, and scaling to reduce the cost from quadratic to log-linear. Similar techniques work for more advanced structural matrix approximations . Lastly, we can use quaternion-like decompositions to reduce the cost to $\mathcal{O}(\frac{dq}{n})$, again if we are willing to trade off a small amount of accuracy for computational and storage cost based on a compression factor $n$. This is an active area of research. What makes it challenging is that we do not necessarily strive for the most compact representation or the smallest number of floating point operations but rather for the solution that can be executed most efficiently on modern GPUs. ## Exercises 1. We can explore the connection between exponential families and softmax in some more depth. 1. Compute the second derivative of the cross-entropy loss $l(\mathbf{y},\hat{\mathbf{y}})$ for softmax. 1. Compute the variance of the distribution given by $\mathrm{softmax}(\mathbf{o})$ and show that it matches the second derivative computed above. 1. Assume that we have three classes which occur with equal probability, i.e., the probability vector is $(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})$. 1. What is the problem if we try to design a binary code for it? 1. Can you design a better code? Hint: what happens if we try to encode two independent observations? What if we encode $n$ observations jointly? 1. When encoding signals transmitted over a physical wire, engineers do not always use binary codes. For instance, PAM-3 uses three signal levels $\{-1, 0, 1\}$ as opposed to two levels $\{0, 1\}$. How many ternary units do you need to transmit an integer in the range $\{0, \ldots, 7\}$? Why might this be a better idea in terms of electronics? 1. The Bradley--Terry model uses a logistic model to capture preferences. For a user to choose between apples and oranges one assumes scores $o_{\textrm{apple}}$ and $o_{\textrm{orange}}$. Our requirements are that larger scores should lead to a higher likelihood in choosing the associated item and that the item with the largest score is the most likely one to be chosen . 1. Prove that softmax satisfies this requirement. 1. What happens if you want to allow for a default option of choosing neither apples nor oranges? Hint: now the user has three choices. 1. Softmax gets its name from the following mapping: $\textrm{RealSoftMax}(a, b) = \log (\exp(a) + \exp(b))$. 1. Prove that $\textrm{RealSoftMax}(a, b) > \mathrm{max}(a, b)$. 1. How small can you make the difference between both functions? Hint: without loss of generality you can set $b = 0$ and $a \geq b$. 1. Prove that this holds for $\lambda^{-1} \textrm{RealSoftMax}(\lambda a, \lambda b)$, provided that $\lambda > 0$. 1. Show that for $\lambda \to \infty$ we have $\lambda^{-1} \textrm{RealSoftMax}(\lambda a, \lambda b) \to \mathrm{max}(a, b)$. 1. Construct an analogous softmin function. 1. Extend this to more than two numbers. 1. The function $g(\mathbf{x}) \stackrel{\textrm{def}}{=} \log \sum_i \exp x_i$ is sometimes also referred to as the log-partition function). 1. Prove that the function is convex. Hint: to do so, use the fact that the first derivative amounts to the probabilities from the softmax function and show that the second derivative is the variance. 1. Show that $g$ is translation invariant, i.e., $g(\mathbf{x} + b) = g(\mathbf{x})$. 1. What happens if some of the coordinates $x_i$ are very large? What happens if they're all very small? 1. Show that if we choose $b = \mathrm{max}_i x_i$ we end up with a numerically stable implementation. 1. Assume that we have some probability distribution $P$. Suppose we pick another distribution $Q$ with $Q(i) \propto P(i)^\alpha$ for $\alpha > 0$. 1. Which choice of $\alpha$ corresponds to doubling the temperature? Which choice corresponds to halving it? 1. What happens if we let the temperature approach $0$? 1. What happens if we let the temperature approach $\infty$? Discussions " Prototype="ALG Source" Color="#7CB7C9" Shape="rounded" Badge="doc.text" Width="6" Height="2.5" BorderColor="#264653" Xpos="19.5" Ypos="4" ALGXpos="19.5" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGId;ALGLicense;ALGURL"/>
</outline>
<outline text="Edges" ALGKind="container" Prototype="ALG Container" Color="#264653" Shape="rounded" Badge="folder" Width="7" Height="3" BorderColor="#264653" Xpos="24" Ypos="0" ALGXpos="24" ALGYpos="0" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}">
<outline text="prereq: dot-product → matrix-vector-product" _note="Canonical prereq edge from dot-product to matrix-vector-product." ALGKind="edge" ALGFrom="dot-product" ALGTo="matrix-vector-product" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="0" Ypos="4" ALGXpos="0" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: dot-product → softmax" _note="Canonical prereq edge from dot-product to softmax." ALGKind="edge" ALGFrom="dot-product" ALGTo="softmax" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="6.5" Ypos="4" ALGXpos="6.5" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: qkv → attention-pooling" _note="Canonical prereq edge from qkv to attention-pooling." ALGKind="edge" ALGFrom="qkv" ALGTo="attention-pooling" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="13" Ypos="4" ALGXpos="13" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: qkv → self-attention" _note="Canonical prereq edge from qkv to self-attention." ALGKind="edge" ALGFrom="qkv" ALGTo="self-attention" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="19.5" Ypos="4" ALGXpos="19.5" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: self-attention → positional-encoding" _note="Canonical prereq edge from self-attention to positional-encoding." ALGKind="edge" ALGFrom="self-attention" ALGTo="positional-encoding" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="26" Ypos="4" ALGXpos="26" ALGYpos="4" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: softmax → qkv" _note="Canonical prereq edge from softmax to qkv." ALGKind="edge" ALGFrom="softmax" ALGTo="qkv" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="0" Ypos="6" ALGXpos="0" ALGYpos="6" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: softmax → softmax-ordering" _note="Canonical prereq edge from softmax to softmax-ordering." ALGKind="edge" ALGFrom="softmax" ALGTo="softmax-ordering" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="6.5" Ypos="6" ALGXpos="6.5" ALGYpos="6" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: vectors → dot-product" _note="Canonical prereq edge from vectors to dot-product." ALGKind="edge" ALGFrom="vectors" ALGTo="dot-product" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="13" Ypos="6" ALGXpos="13" ALGYpos="6" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
<outline text="prereq: vectors → vector-norm" _note="Canonical prereq edge from vectors to vector-norm." ALGKind="edge" ALGFrom="vectors" ALGTo="vector-norm" ALGEdgeType="prereq" Prototype="ALG Edge" Color="#9AA5B1" Shape="rounded" Badge="arrow.right" Width="6" Height="1.5" BorderColor="#264653" Xpos="19.5" Ypos="6" ALGXpos="19.5" ALGYpos="6" Rule="if($ChildCount("/Atomic Learning Graph/Concepts")==10){$Xpos=$ALGXpos;$Ypos=$ALGYpos;$Rule=""}" DisplayedAttributes="ALGFrom;ALGTo;ALGEdgeType"/>
</outline>
</outline>
</body>
</opml>