Repository navigation
Expand file tree
/
Copy pathtransformers.typ
More file actions
477 lines (433 loc) · 20.4 KB
/
Copy pathtransformers.typ
File metadata and controls
477 lines (433 loc) · 20.4 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
// =============================================================================
// Monograph Outline: Modern Deep Learning: A Short Course
//
// 4. Attention and Transformers
// - Permutation Equivariance and Set Operations
// - Scaled Dot-Product Attention
// - Normalization and Residual Connections
// - Gated Feed-Forward Networks
// - Representation Rank and Residual Dynamics
//
// 5. Autoregressive Sequence Models
// - Joint Density Factorization
// - Discrete Vocabularies and Token Embeddings
// - Causal Masking
// - Rotary Position Embeddings
// - Key-Value Cache and Generation Dynamics
// - Stochastic Decoding and Temperature Scaling
//
// 6. In-Context Learning and Prior-Data Fitted Networks
// - In-Context Conditioning as Bayesian Inference
// - Prior-Data Fitted Networks
// - In-Context Gradient Steps and Activation Dynamics
// =============================================================================
#set page(paper: "a5", margin: (x: 18mm, top: 22mm, bottom: 20mm), numbering: "1")
#set text(font: "Concrete Math")
#set par(justify: true, leading: 0.65em)
#show heading.where(level: 1): it => counter(math.equation).update(0) + it
#show heading.where(level: 1): set text(13pt)
#show heading.where(level: 2): set text(11pt)
#show heading: set block(above: 1.8em, below: 1.2em)
#show math.equation: set text(font: "Concrete Math")
#set math.equation(
numbering: n => ("(" + str(counter(heading).get().first()) + "." + str(n) + ")"),
supplement: none,
)
#set heading(
numbering: (..n) => (
(if n.pos().len() == 1 { "§ " } else { "" }) + n.pos().map(str).join(".") + "."
),
supplement: none,
)
#show ref: it => {
let el = it.element
if el != none and el.func() == heading {
let num = counter(heading).at(el.location())
let s = (if num.len() == 1 { "§ " } else { "" }) + num.map(str).join(".")
link(el.location(), s)
} else {
it
}
}
#align(center)[
#text(16pt, strong("Modern Deep Learning: A Short Course")) \
#v(0.5em)
Bartosz Hanc
]
#v(0.8em)
#pad(x: 1.2em)[
#set text(9pt)
A self-contained introduction to modern deep learning,
framing supervised and unsupervised learning as maximum likelihood
estimation, developing neural networks as computational graphs trained via
backpropagation, and covering optimization, Transformer architectures,
autoregressive sequence modeling, and in-context learning.
]
#v(0.6em)
#outline()
#pagebreak()
// = Introduction
= Learning as Likelihood Maximization <sec:learning>
Machine learning is fundamentally the task of inferring an unknown probability
distribution from a finite dataset $cal(D)$. Depending on whether the data
contain supervisory signals, we distinguish between two primary settings:
unsupervised and supervised learning.
In the unsupervised case, our dataset consists simply of unlabeled samples
$cal(D) = {bold(x)_1, ..., bold(x)_N}$, where $bold(x)_i in RR^d$. Our goal is
to learn the underlying data distribution---a task that we can broadly
summarize as estimating the data density and/or being able to sample new, unseen
examples $bold(x)$ from this distribution,
$
bold(x) ~ P(dot; bold(theta)) quad.
$
In the supervised case, our dataset consists of input-target pairs
$cal(D) = {(bold(x)_1, y_1), ..., (bold(x)_N, y_N)}$, where
$bold(x)_i in RR^d$ is an input feature vector and $y_i$ is the corresponding
label or target. Our goal is to predict the target $y$ for an unseen input
$bold(x)$.
Both learning paradigms can be framed as likelihood maximization. Assuming the
samples in our training set are independent and identically distributed
(i.i.d.), the joint probability of observing the dataset under a model
parameterized by $bold(theta)$ factors as a product over individual examples,
$
P(cal(D); bold(theta)) = product_(i=1)^N P(bold(x)_i; bold(theta))
quad "(unsupervised)"
$
or, in the case of pairs,
$
P(cal(D); bold(theta)) = product_(i=1)^N P(bold(x)_i, y_i; bold(theta))
quad "(supervised)" quad.
$
In the supervised setting, we can factorize the joint distribution of each
pair as
$
P(bold(x)_i, y_i; bold(theta)) =
P(y_i | bold(x)_i; bold(theta)) P(bold(x)_i) quad.
$
When training discriminative models, we assume that the input marginal
distribution $P(bold(x))$ does not depend on the model parameters $bold(theta)$.
Taking the log-likelihood over the dataset $cal(D)$,
$
log P(cal(D); bold(theta)) & = sum_(i=1)^N log P(bold(x)_i, y_i; bold(theta)) \
& = sum_(i=1)^N log P(y_i | bold(x)_i; bold(theta)) \
& quad + underbrace(
sum_(i=1)^N log P(bold(x)_i),
"const. w.r.t." bold(theta)
) quad.
$
Therefore, maximizing the joint log-likelihood over $cal(D)$ with respect to
$bold(theta)$ is mathematically equivalent to maximizing the *conditional*
log-likelihood,
$
bold(theta)^* = arg max_bold(theta) sum_(i=1)^N
log P(y_i | bold(x)_i; bold(theta)) quad.
$
By convention, optimization problems in machine learning are formulated as
minimizations rather than maximizations, and the objective is normalized by the
dataset size $N$ so that its scale remains independent of the number of
training samples. We therefore define the *loss function* as the
sample-averaged negative conditional log-likelihood,
$
L(cal(D); bold(theta)) = - 1 / N sum_(i=1)^N
log P(y_i | bold(x)_i; bold(theta)) quad,
$
(or, in the unsupervised case,
$L(cal(D); bold(theta)) = - 1 / N sum_(i=1)^N log P(bold(x)_i; bold(theta))$).
Finding the maximum likelihood estimate is thus equivalent to minimizing this
loss,
$
bold(theta)^* = arg min_bold(theta) L(cal(D); bold(theta)) quad.
$
For certain simple problems, it is possible to find the minimizer
$bold(theta)^*$ in closed form. In general, however---and especially for deep
neural networks where the loss function is non-linear and high-dimensional---we
must resort to iterative numerical optimization. In such massive parameter
spaces, gradient-free search is rendered intractable by the curse of
dimensionality, making exact gradient information indispensable for pointing
in the direction of steepest descent. The basic gradient descent update rule is
$
bold(theta)_(t+1) = bold(theta)_t - eta (partial L) / (partial bold(theta))
(cal(D); bold(theta)_t) quad,
$
where $eta > 0$ is the learning rate. We will discuss modern variants of
gradient descent used in deep learning later.
We will now derive expressions for the loss functions of typical supervised
learning tasks: regression, binary classification, and multiclass
classification.
- *Regression (Mean Squared Error):* For a standard regression problem where
$bold(x) in RR^d$ and target $y in RR$, we assume a conditional Gaussian
model,
$
y | bold(x) ~ cal(N)(f(bold(x); bold(theta)), sigma^2) quad,
$
where $f(dot; bold(theta)): RR^d -> RR$ is parameterized by $bold(theta)$
(e.g., a neural network). The loss function is therefore
$
L(cal(D); bold(theta), sigma) & = - 1 / N sum_(i=1)^N log {
1 / sqrt(2 pi sigma^2) exp(
- [y_i - f(bold(x)_i; bold(theta))]^2 /
(2sigma^2)
)
} \
& = 1 / (2N sigma^2) sum_(i=1)^N
[y_i - f(bold(x)_i; bold(theta))]^2 \
& quad + 1 / 2 log (2pi sigma^2) quad.
$
Assuming fixed noise variance $sigma^2$, minimizing this loss with respect to
$bold(theta)$ is strictly equivalent to minimizing the Mean Squared Error
(MSE),
$
L_"MSE" (cal(D); bold(theta)) = 1 / (2N) sum_(i=1)^N
[y_i - f(bold(x)_i; bold(theta))]^2 quad,
$
which yields the gradient with respect to $f_i = f(bold(x)_i; bold(theta))$,
$
(partial L_"MSE") / (partial f_i) = 1 / N (f_i - y_i) quad.
$ <eq:grad-mse>
- *Binary Classification (Binary Cross-Entropy):* For a binary classification
problem where $bold(x) in RR^d$ and target label $y in {0, 1}$, we assume a
conditional Bernoulli model,
$
y | bold(x) ~ "Ber"(pi(bold(x); bold(theta))) quad,
$
where $pi(bold(x); bold(theta)) = P(y = 1 | bold(x); bold(theta)) in [0, 1]$.
The loss function (binary cross-entropy) is given by
$
L (cal(D); bold(theta)) & = - 1 / N sum_(i=1)^N log {
pi(bold(x)_i; bold(theta))^(y_i) dot
(1 - pi(bold(x)_i; bold(theta)))^(1 - y_i)
} \
& = - 1 / N sum_(i=1)^N {
y_i log pi(bold(x)_i; bold(theta)) +
(1 - y_i) log [1 - pi(bold(x)_i; bold(theta))]
} quad.
$
To ensure that $pi(bold(x); bold(theta)) in [0, 1]$, we express $pi$ as the
composition of the standard logistic sigmoid function $sigma: RR -> [0, 1]$
and an unconstrained scalar model output $f(bold(x); bold(theta)) in RR$
(called the logit),
$
pi(bold(x); bold(theta)) = sigma(f(bold(x); bold(theta))) =
1 / (1 + exp(-f(bold(x); bold(theta)))) quad.
$
This choice is particularly appealing because
$
(d sigma) / (d z) = sigma(z) dot [1 - sigma(z)]
$
which yields a clean gradient with respect to the logit
$f_i = f(bold(x)_i; bold(theta))$,
$
(partial L_"BCE") / (partial f_i) = 1 / N (pi_i - y_i) quad.
$ <eq:grad-bce>
- *Multiclass Classification (Categorical Cross-Entropy):* For a multiclass
classification problem where $bold(x) in RR^d$ and target label
$y in {1, ..., K}$, we assume a conditional Categorical model,
$
y | bold(x) ~ "Cat"(pi_1 (bold(x); bold(theta)), ...,
pi_K (bold(x); bold(theta))) quad,
$
where $bold(pi)(bold(x); bold(theta)): RR^d -> [0, 1]^K$ satisfies
$sum_(k=1)^K pi_k (bold(x); bold(theta)) = 1$. The loss function (categorical
cross-entropy) is
$
L (cal(D); bold(theta)) & = - 1 / N sum_(i=1)^N log {
product_(k=1)^K pi_k (bold(x)_i; bold(theta))^[y_i = k]
} \
& = - 1 / N sum_(i=1)^N sum_(k=1)^K [y_i = k]
log pi_k (bold(x)_i; bold(theta)) quad,
$
where $[dot]$ denotes the Iverson bracket. Writing the one-hot target
component as $y_(i k) = [y_i = k]$, this becomes
$
L(cal(D); bold(theta)) = - 1 / N sum_(i=1)^N sum_(k=1)^K y_(i k)
log pi_k (bold(x)_i; bold(theta)) quad.
$
To parameterize $bold(pi)$, we map $bold(x)$ to a vector of unnormalized
scores (logits) $bold(f)(bold(x); bold(theta)) in RR^K$ followed by the
softmax function,
$
["softmax"(bold(z))]_k = exp(z_k) / (sum_(j=1)^K exp(z_j)) quad,
$
which for numerical stability is computed as
$
["softmax"(bold(z))]_k = exp(z_k - m) / (sum_(j=1)^K exp(z_j - m)) quad,
$
where $m = max_j z_j$ (ensuring that all exponent arguments are $<= 0$,
avoiding numerical overflow).
This formulation leads to a particularly clean gradient with respect to the
logit $f_(i k) = [bold(f)(bold(x)_i; bold(theta))]_k$,
$
(partial L_"CE") / (partial f_(i k)) = 1 / N (pi_(i k) - y_(i k)) quad,
$ <eq:grad-ce>
where $pi_(i k) = pi_k (bold(x)_i; bold(theta))$.
= Neural Networks
The maximum likelihood formulation reduces learning to minimizing an empirical
loss $L(cal(D); bold(theta))$, but leaves the parameterization of
$bold(f)(bold(x); bold(theta))$ unspecified. While a linear model
$f(bold(x)) = bold(w)^top bold(x) + b$ yields a convex optimization problem,
it cannot separate non-linear data distributions or capture complex manifolds.
Real-world data (such as text or images) require learning rich, hierarchical
feature representations, which deep neural networks achieve via function
composition.
== Multilayer Perceptrons
The artificial neuron originated with the threshold logic unit of McCulloch and
Pitts (1943), extended to learnable weights and biases by Rosenblatt (1958) in
the *perceptron*,
$
f(bold(x)) = sigma(bold(w)^top bold(x) + b) quad.
$
Early models used a discontinuous step activation, famously proven by Minsky
and Papert (1969) to be limited to linearly separable problems (failing even on
XOR). Modern networks overcome this by stacking neurons into *Multi-Layer
Perceptrons* (MLPs) with smooth, non-linear activations $sigma$ (e.g., sigmoid,
$tanh$, or ReLU). An MLP is a direct function composition,
$
f(bold(x)) & = (f_L compose dots.c compose f_1)(bold(x)) \
& = sigma_L (bold(W)_L dots.c sigma_1 (bold(W)_1 bold(x)
+ bold(b)_1) dots.c + bold(b)_L) quad,
$
where each layer computes $f_l (bold(h)_(l-1)) = sigma_l (bold(W)_l
bold(h)_(l-1) + bold(b)_l)$ with $bold(h)_0 = bold(x)$. Smooth activations
render the composition differentiable end-to-end, and such networks act as
universal function approximators (Cybenko, 1989; Hornik, 1991).
== Computational Graph Perspective
Modern architectures (such as Transformers) go beyond strictly sequential
layers by incorporating branching, attention mechanisms, and residual
connections. In general, a neural network is formalized as an *attributed
Directed Acyclic Graph* (DAG) $cal(G) = (cal(V), cal(E))$.
In this graph, directed edges represent data flow: a directed edge $(j, i) in
cal(E)$ indicates that the value $bold(v)_j$ computed at node $j$ is passed as
an input to node $i$. Each node $i in cal(V)$ is characterized by:
- *Predecessors (inputs):* The set of parent nodes $cal(P)_i = {j in cal(V) |
(j, i) in cal(E)}$ whose outputs feed into node $i$. Nodes with no incoming
edges ($cal(P)_i = emptyset$) are the *input nodes*, which receive external
features $bold(x)$.
- *Successors (consumers):* The set of child nodes $cal(N)_i = {k in cal(V) |
(i, k) in cal(E)}$ that consume $bold(v)_i$. Nodes with no outgoing
edges ($cal(N)_i = emptyset$) are the *output nodes*, yielding the model's
predictions $bold(f)(bold(x); bold(theta))$.
- *Local computation:* A differentiable function $bold(f)_i$ parameterized by
local parameters $bold(theta)_i$ (with $bold(theta)_i = emptyset$ for
parameter-free operations), computing the intermediate tensor
(multidimensional array),
$
bold(v)_i = bold(f)_i ({bold(v)_j}_(j in cal(P)_i); bold(theta)_i) quad.
$
- *Local derivatives:* The known partial derivatives of output components with
respect to parameters and parent activations (where $p, q$ denote
multi-indices indexing tensor elements),
$
(partial v_(i, p)) / (partial theta_(i, q)) quad "and" quad
(partial v_(i, p)) / (partial v_(j, q)) quad (j in cal(P)_i) quad.
$
== Forward Propagation
Because the computational graph $cal(G)$ is directed and acyclic, its vertices
admit a *topological ordering*---a permutation of nodes $(v_1, v_2, ...,
v_(|cal(V)|))$ such that for every directed edge $(j, i) in cal(E)$, node $j$
appears before node $i$.
Forward propagation evaluates the nodes sequentially in topological order,
$
bold(v)_i = bold(f)_i ({bold(v)_j}_(j in cal(P)_i); bold(theta)_i) quad.
$
Topological sorting guarantees that whenever a node $i$ is visited, the outputs
$bold(v)_j$ of all its parent nodes $j in cal(P)_i$ have already been computed.
The evaluation begins at the input nodes and terminates at the output nodes
$bold(f)$. The intermediate values $bold(v)_i$ are cached in memory, as they
are required during the backward pass to evaluate the local derivatives.
== Backward Propagation
To optimize the network parameters via gradient descent, we must compute the
gradient of the scalar loss $L$ with respect to the parameters of every node.
Crucially, backward propagation is initialized directly at the network's
output nodes $bold(f)$ using the analytical loss gradients derived in
@sec:learning.
Starting from these known boundary gradients at the output nodes, we traverse
the computational graph in *reverse topological order* back toward the input
nodes. For any internal node $i$, the computation is governed by two chain
rule equations (where $p, q$ denote suitable multi-indices over tensor
elements):
1. *Gradient with respect to intermediate activations:* Because the
activation $v_(i, p)$ can affect the loss $L$ through multiple downstream
paths via successor nodes $j in cal(N)_i$, the total derivative sums over
all child nodes and their components,
$
(partial L) / (partial v_(i, p)) = sum_(j in cal(N)_i) sum_q
(partial L) / (partial v_(j, q)) (partial v_(j, q)) / (partial v_(i, p))
quad.
$
2. *Gradient with respect to node parameters:* The parameters $theta_(i, p)$
influence the loss $L$ exclusively through the node's own output values
$v_(i, q)$,
$
(partial L) / (partial theta_(i, p)) = sum_q
(partial L) / (partial v_(i, q)) (partial v_(i, q)) / (partial theta_(i, p))
quad.
$
In reverse topological order, when visiting node $i$, the incoming gradients
$(partial L) / (partial v_(j, q))$ from all successors $j in cal(N)_i$ have
already been computed. We first evaluate $(partial L) / (partial v_(i, p))$,
and then use it to compute $(partial L) / (partial theta_(i, p))$ and propagate
gradients backward to all predecessors of node $i$.
= Optimization and Initialization <sec:optimization>
While maximum likelihood and backpropagation rest on exact mathematical
principles, initialization and optimization in deep learning rely heavily on
empirical heuristics---designs that have proven effective at scale rather than
deriving from tight theoretical guarantees.
== Weight Initialization
Zero initialization fails due to symmetry, so weights are sampled from
$W_p ~ cal(N)(0, sigma^2)$ (for multi-index $p$) with zero biases. Two main
heuristics are used to set $sigma$:
- *Dimension-scaled (Xavier / He):* Scaling $sigma$ inversely with input width
$d_"in"$---such as $sigma = 1 / sqrt(d_"in")$ (Xavier) or
$sigma = sqrt(2 / d_"in")$ (He, for ReLU)---to keep activation magnitudes
stable across layers.
- *Fixed-scale normal:* Modern normalized architectures (such as Transformers)
typically bypass width-dependent scaling and use a small fixed constant such
as $sigma = 0.02$ (occasionally scaled down with depth $L$, e.g.,
$sigma / sqrt(2 L)$, on output projections).
== Mini-Batch Stochastic Gradient Descent
Computing the exact gradient over all $N$ examples is prohibitive at scale.
*Stochastic Gradient Descent* (SGD) replaces it with a mini-batch estimate
over a random subset $cal(B)_t subset cal(D)$ of size $B = |cal(B)_t| << N$,
$
bold(g)_t = (partial L) / (partial bold(theta)) (cal(B)_t; bold(theta)_t)
quad, quad
bold(theta)_(t+1) = bold(theta)_t - eta bold(g)_t quad.
$
Mini-batching gives an unbiased gradient estimate ($EE[bold(g)_t] =
(partial L) / (partial bold(theta)) (cal(D); bold(theta)_t)$) whose variance
shrinks as $O(1 / B)$, saturates parallel GPU matrix multiplications, and
introduces noise that empirically acts as an implicit regularizer against sharp
minima.
== Adaptive Optimization: Adam and AdamW
Because gradient scales and curvature vary wildly across parameters, a single
learning rate $eta$ in SGD is often inefficient. Modern Transformer training
relies almost universally on *AdamW*, which combines two heuristics: an
exponential moving average (EMA) of gradients (*momentum*, $bold(m)_t$) to
smooth noisy steps, and an EMA of squared gradients ($bold(v)_t$) to normalize
each coordinate by its recent gradient magnitude,
$
bold(m)_t & = beta_1 bold(m)_(t-1) + (1 - beta_1) bold(g)_t quad, \
bold(v)_t & = beta_2 bold(v)_(t-1) + (1 - beta_2) bold(g)_t^2 quad,
$
with bias corrections to offset zero-initialization ($bold(m)_0 = bold(v)_0 =
bold(0)$). Unrolling $bold(m)_t$ gives $bold(m)_t = (1 - beta_1) sum_(i=1)^t
beta_1^(t-i) bold(g)_i$; assuming stationary moments $EE[bold(g)_i] approx
EE[bold(g)]$, the finite geometric series yields
$
EE[bold(m)_t] = EE[bold(g)] (1 - beta_1) sum_(k=0)^(t-1) beta_1^k
= EE[bold(g)] (1 - beta_1^t) quad,
$
and analogously $EE[bold(v)_t] = EE[bold(g)^2] (1 - beta_2^t)$. Dividing out
these factors gives the bias-corrected estimates $hat(bold(m))_t = bold(m)_t /
(1 - beta_1^t)$ and $hat(bold(v))_t = bold(v)_t / (1 - beta_2^t)$, followed by
the decoupled weight-decay update,
$
bold(theta)_(t+1) = (1 - eta lambda) bold(theta)_t -
eta hat(bold(m))_t / (sqrt(hat(bold(v))_t) + epsilon) quad,
$
where $lambda >= 0$ is the weight decay coefficient, $epsilon approx 10^(-8)$,
and typical defaults are $eta approx 10^(-4)$ to $10^(-3)$ (e.g., $3 dot
10^(-4)$, often with warmup and decay), $beta_1 = 0.9$, and $beta_2 = 0.999$
(or $0.95$ for LLMs). Decoupling $-eta lambda bold(theta)_t$ from the gradient
avoids rescaling $L_2$ regularization by $1 / sqrt(hat(bold(v))_t)$.
= Attention and Transformers