CS3264: Mathematical Prerequisites

Summary of Key Ideas

These notes review the mathematics you will need, using small examples that do not require any previous knowledge of machine learning. Start here if you are unfamiliar with the notation or would like to refresh the underlying ideas.

Most of the mathematics serves a few purposes. Algebra lets us read and rearrange equations. Vectors and matrices organise several numbers and calculations together. Probability describes uncertain outcomes, while averages and measures of spread help us summarise them. Calculus and optimisation describe how a function changes and how to find values that make it small or large.

The review is organised into four parts: Basics, Linear Algebra, Probability, and Calculus and Optimisation. Work through the examples in order when a topic is new to you. The final course map is only a preview of where these tools are used; the lectures will introduce the machine learning concepts themselves.

The main aim is to understand what an equation says and why each step is valid. Ask: What is fixed? What can change? What does each symbol mean? Which rule allows the next step?

Learning Objectives

After working through these notes, you should be able to:

• read indices, sums, products, sets, and common mathematical notation
• rearrange simple equations and use exponential and logarithm rules
• calculate dot products and matrix products, check their dimensions, and interpret the normal equations
• distinguish joint, conditional, and marginal probabilities, and use Bayes' rule
• recognise Bernoulli, categorical, and Gaussian distributions
• calculate and interpret expectation, variance, and covariance
• explain independence, conditional independence, and the iid assumption
• use partial derivatives and the chain rule to calculate a gradient
• distinguish a minimum value from the input that achieves it, and perform a gradient-descent step
• solve a simple equality-constrained problem using a Lagrangian
• read a probability bound and rearrange it to find a sufficient sample size.

What should you remember? Make the short rules familiar: dot products, matrix dimensions, log rules, the chain rule, the sum and product rules of probability, Bayes' rule, and the definitions of expectation and variance.

What should you understand? Practise explaining and reproducing the worked examples. You should be able to say why a calculation works and when its assumptions apply. For longer expressions, such as a probability bound, start by identifying what every quantity means. You do not need to learn the machine learning methods before beginning the lectures.

Basics

Mathematical Notation and Reading Equations

A scalar is one number, a vector is an ordered collection of numbers, and a matrix is a rectangular table of numbers. Bold lowercase letters usually denote vectors, such as \mathbf{x}; bold uppercase letters usually denote matrices, such as \mathbf{A}. We will explain their operations in the linear algebra section.

Notation sometimes varies between sources. Read the definitions around an equation, and please ask if a symbol is unclear. The following conventions are useful starting points.

A subscript usually labels an entry rather than an operation. If x_1=2, x_2=5, and x_3=8, then x_2 means the second value, which is 5. For a table, x_{nm} can mean entry m of row n. Some sources write this as x_n^m, with the superscript acting as an index. In an expression such as x^2, however, it usually means a power. The definition determines which interpretation applies.

Read an equation from its smaller pieces outward. For example,

\[r=\frac{(2-5)^2+(8-5)^2}{2} =\frac{9+9}{2}=9.\]

We subtract 5 from each number, square both differences, add them, and divide by two. This is the average squared distance of the two numbers from 5.

An equality = says two quantities are equal. An approximation \approx says they are close. A proportionality \propto leaves out a common multiplicative factor: if quantities are proportional to 2 and 3 and must add to one, they are 2/5 and 3/5. Proportionality does not mean “equal up to an additive constant”.

Symbols can have different meanings in different settings. For example, E(x) may simply be the name of a function, whereas \mathbb{E}[X] denotes an expectation, which we will define later. Different styles help distinguish these meanings, but the surrounding definitions are still important.

Sets, Indicators, Sums and Products

A set is a collection of elements. For S=\{1,2,3,4\}, the expression 2\in S means that 2 belongs to the set, and |S|=4 gives its number of elements. Around a scalar, the same vertical bars denote absolute value: |-3|=3.

The union A\cup B contains elements in either set or both. The intersection A\cap B contains elements in both. For A=\{1,2\} and B=\{2,3\},

\[A\cup B=\{1,2,3\}, \qquad A\cap B=\{2\}.\]

The symbol \forall means “for every”, and \exists means “there exists at least one”. For example, \forall x\in S:\ x>0 is true, and \exists x\in S:\ x>3 is also true. A statement about every element fails as soon as one element fails it.

A sum adds indexed terms, while a product multiplies them:

\[\sum_{i=1}^{3}a_i=a_1+a_2+a_3, \qquad \prod_{i=1}^{3}a_i=a_1a_2a_3.\]

If the values are 2,3,4, the sum is 9 and the product is 24. The letter i is a temporary index; replacing it consistently with j does not change the result. A double sum such as \sum_i\sum_j a_{ij} adds entries across both indices, for example all entries of a table.

An indicator function turns a statement into zero or one:

\[\mathbb{1}[A]= \begin{cases} 1,&\text{if }A\text{ is true},\\ 0,&\text{if }A\text{ is false}. \end{cases}\]

Suppose a_1=2, a_2=5, and a_3=8. Then

\[\sum_{i=1}^{3}\mathbb{1}[a_i>3]=0+1+1=2\]

counts how many values exceed 3. Dividing by three gives the fraction that satisfy the condition. An indicator can also select terms:

\[\sum_{i:a_i>3}a_i =\sum_{i=1}^{3}\mathbb{1}[a_i>3]a_i =0(2)+1(5)+1(8)=13.\]

The expression under the first sum means “include only indices for which a_i>3”.

Algebra You Will Use

Many derivations use ordinary expansion, factorisation, and rearrangement. Two useful identities are

\[(a-b)^2=a^2-2ab+b^2, \qquad (a+b)^2=a^2+2ab+b^2.\]

For example, (x-3)^2=x^2-6x+9. The middle term is needed: squaring a difference is not the same as subtracting the squares.

You can move a factor outside a sum if it does not depend on the summation index. For a constant c,

\[\sum_{i=1}^{N}ca_i=c\sum_{i=1}^{N}a_i, \qquad \sum_{i=1}^{N}c=Nc.\]

For example, suppose we want a number m for which the differences from 2,5,8 add to zero:

\[(2-m)+(5-m)+(8-m)=0 \quad\Longrightarrow\quad 15-3m=0 \quad\Longrightarrow\quad m=5.\]

For arbitrary numbers a_1,\ldots,a_N, the same steps give

\[\sum_{i=1}^{N}(a_i-m)=0 \quad\Longrightarrow\quad \sum_{i=1}^{N}a_i-Nm=0 \quad\Longrightarrow\quad m=\frac{1}{N}\sum_{i=1}^{N}a_i.\]

Here m is fixed as we move through the index i, even though it is the unknown we want to find. This distinction between “constant with respect to an index” and “already known” is useful throughout mathematics.

Functions, Exponentials and Logarithms

A function maps an input to an output. For example, f(x)=2x+1 gives f(3)=7. A parameter is a number that specifies which function we use. In f(x;a)=ax+1, the semicolon separates the input x from the parameter a. Fixing a=2 gives the previous function.

A composition applies one function after another. If g(x)=2x+1 and h(u)=u^2, then

\[h(g(x))=(2x+1)^2.\]

At x=3, we first obtain 7 and then square it to obtain 49.

The exponential function e^a, also written \exp(a), is positive for every real a. The number e is approximately 2.718. The natural logarithm \log a or \ln a is its inverse and is defined for a>0. We use natural logarithms in these notes. The main rules are

\[\begin{aligned} e^{a+b}&=e^ae^b, & e^{-a}&=\frac{1}{e^a},\\ \log(ab)&=\log a+\log b, & \log(a/b)&=\log a-\log b,\\ \log(a^r)&=r\log a, & \log(e^a)&=a. \end{aligned}\]

The log identities involving a and b require positive arguments. For example, \log(2\times3)=\log2+\log3. But \log(2+3) is generally not \log2+\log3.

For positive numbers a_i, a log changes a product into a sum:

\[\log\left(\prod_{i=1}^{N}a_i\right) =\sum_{i=1}^{N}\log a_i.\]

Logarithms are strictly increasing: if a>b>0, then \log a>\log b. Taking logs therefore preserves which of several positive numbers is largest. This will be useful when we compare positive-valued functions.

Two functions built from exponentials deserve a first introduction. The sigmoid maps a real number to a value strictly between zero and one:

\[\sigma(a)=\frac{1}{1+e^{-a}}.\]

For example, \sigma(0)=1/2, \sigma(\log3)=3/4, and \sigma(-\log3)=1/4. Increasing the input increases the output, which approaches one for large positive inputs and zero for large negative inputs. At this stage, it is simply a useful way to turn an unrestricted number into a bounded one.

If y=\sigma(a), rearranging gives

\[\frac{1-y}{y}=e^{-a} \quad\Longrightarrow\quad \frac{y}{1-y}=e^a \quad\Longrightarrow\quad \log\frac{y}{1-y}=a.\]

If y is a probability, the ratio y/(1-y) is called the odds, and its logarithm is the log-odds. For y=3/4, the odds are 3: the event is three times as likely to occur as not to occur.

The softmax function takes several real numbers and produces positive numbers that sum to one:

\[y_k=\frac{e^{a_k}}{\sum_{j=1}^{K}e^{a_j}}.\]

For inputs (0,\log2,\log3), the exponentials are (1,2,3). Dividing each by their total gives (1/6,2/6,3/6). This division is called normalisation. Larger inputs receive larger shares of the total, so the result can represent probabilities over alternatives.

Adding the same constant c to every input leaves these shares unchanged: every exponential is multiplied by e^c, which cancels between numerator and denominator. Understand the two steps—make the values positive, then divide by their total—rather than treating softmax as an unexplained formula.

Linear Algebra

Vectors and Matrices

Unless stated otherwise, vectors are column vectors. For example, \mathbf{x}=[3,4]^{\top} is a short way of writing the column with entries 3 and 4. The transpose, written \top, swaps rows and columns. If \mathbf{x} is M\times1, then \mathbf{x}^{\top} is 1\times M.

Vector addition and multiplication by a scalar act on each entry. For example,

\[\begin{bmatrix}1\\2\end{bmatrix} +2\begin{bmatrix}3\\4\end{bmatrix} =\begin{bmatrix}7\\10\end{bmatrix}.\]

The dot product multiplies matching entries and adds them:

\[\mathbf{w}^{\top}\mathbf{x}=\sum_{m=1}^{M}w_mx_m.\]

For \mathbf{w}=[2,-1]^{\top} and \mathbf{x}=[3,4]^{\top}, it is 2(3)-1(4)=2. The result is one number. For another interpretation, quantities [2,3]^{\top} and prices [4,5]^{\top} give a total cost of 2(4)+3(5)=23 through a dot product.

The Euclidean norm is a vector's length:

\[\|\mathbf{x}\|_2=\sqrt{\sum_mx_m^2}, \qquad \|\mathbf{x}\|_2^2=\mathbf{x}^{\top}\mathbf{x}.\]

For [3,4]^{\top}, the norm is 5 and the squared norm is 25. The distance between two vectors is the norm of their difference. Two nonzero vectors with dot product zero are perpendicular, or orthogonal. For example, [1,1]^{\top} and [1,-1]^{\top} have dot product zero.

Matrix multiplication is built from dot products. If \mathbf{A} is r\times s and \mathbf{B} is s\times q, then \mathbf{A}\mathbf{B} is r\times q, with

\[(\mathbf{A}\mathbf{B})_{ij}=\sum_{k=1}^{s}A_{ik}B_{kj}.\]

The inner dimensions must match. Each entry comes from a row of the first matrix and a column of the second. For example,

\[\begin{bmatrix}1&2\\3&4\end{bmatrix} \begin{bmatrix}5\\6\end{bmatrix} =\begin{bmatrix}1(5)+2(6)\\3(5)+4(6)\end{bmatrix} =\begin{bmatrix}17\\39\end{bmatrix}.\]

Multiplication is generally not entry by entry, and \mathbf{A}\mathbf{B} need not equal \mathbf{B}\mathbf{A}. Useful transpose rules are

\[(\mathbf{A}\mathbf{B})^{\top}=\mathbf{B}^{\top}\mathbf{A}^{\top}, \qquad (\mathbf{A}^{\top})^{\top}=\mathbf{A}.\]

Notice the reversed order in the first rule. Also distinguish the scalar \mathbf{x}^{\top}\mathbf{x} from the outer product \mathbf{x}\mathbf{x}^{\top}. For \mathbf{x}=[3,4]^{\top}, the outer product is

\[\mathbf{x}\mathbf{x}^{\top} =\begin{bmatrix}9&12\\12&16\end{bmatrix}.\]

A linear combination multiplies vectors by scalars and adds them. In two dimensions, the standard basis vectors \mathbf{e}_1=[1,0]^{\top} and \mathbf{e}_2=[0,1]^{\top} give

\[\begin{bmatrix}a\\b\end{bmatrix} =a\mathbf{e}_1+b\mathbf{e}_2.\]

The span of some vectors is the collection of all their linear combinations. The vectors are linearly independent if no vector in the collection can be written as a combination of the others. An independent collection that spans a space is a basis for that space. For example, [1,0]^{\top} and [2,0]^{\top} cannot form a basis for the plane: both point along the same line.

We can also build functions from simpler functions. Choosing 1,x,x^2 as ingredients gives

\[\boldsymbol{\phi}(x)=\begin{bmatrix}1\\x\\x^2\end{bmatrix}, \qquad f(x)=\mathbf{w}^{\top}\boldsymbol{\phi}(x) =w_0+w_1x+w_2x^2.\]

The entries of \boldsymbol{\phi}(x) are called features, and the chosen functions are often called basis functions. For x=2, the features are [1,2,4]^{\top}. Weights [1,3,2]^{\top} then give 1+6+8=15. This function can curve as x changes, but each weight enters linearly. Unlike coordinate basis vectors, chosen feature functions do not guarantee independent columns when evaluated at a particular collection of inputs.

Solving Linear Equations and Least Squares

A matrix equation is a compact way to write several linear equations. For example,

\[\begin{bmatrix}1&1\\1&-1\end{bmatrix} \begin{bmatrix}u\\v\end{bmatrix} =\begin{bmatrix}6\\2\end{bmatrix}\]

means u+v=6 and u-v=2. Adding these equations gives u=4, and substituting back gives v=2.

The identity matrix \mathbf{I} leaves a vector unchanged. A square matrix \mathbf{A} has an inverse \mathbf{A}^{-1} when

\[\mathbf{A}^{-1}\mathbf{A}=\mathbf{A}\mathbf{A}^{-1}=\mathbf{I}.\]

If this inverse exists, \mathbf{A}\mathbf{w}=\mathbf{b} has the solution \mathbf{w}=\mathbf{A}^{-1}\mathbf{b}. An inverse is not formed by taking the reciprocal of each entry. Some matrices have no inverse. For example, equations u+v=2 and 2u+2v=4 repeat the same information; many pairs satisfy them, so their coefficient matrix cannot have an inverse.

Sometimes several equations cannot all hold exactly. Imagine three measurements of the same length: 2, 3, and 4. We want one number w to represent them, but w cannot equal all three. A natural choice is to minimise the sum of squared differences:

\[E(w)=(w-2)^2+(w-3)^2+(w-4)^2 =3(w-3)^2+2.\]

The final expression is smallest at w=3, since a square cannot be negative. This procedure is called least squares.

For a general system \mathbf{A}\mathbf{w}\approx\mathbf{b}, least squares minimises \|\mathbf{A}\mathbf{w}-\mathbf{b}\|_2^2. The difference \mathbf{b}-\mathbf{A}\mathbf{w} is the residual. Since \mathbf{A}\mathbf{w} is a linear combination of the columns of \mathbf{A}, we seek the point in their span closest to \mathbf{b}. At that closest point, the residual is orthogonal to every column. Thus,

\[\mathbf{A}^{\top}(\mathbf{b}-\mathbf{A}\mathbf{w})=\mathbf{0} \quad\Longrightarrow\quad \boxed{\mathbf{A}^{\top}\mathbf{A}\mathbf{w}=\mathbf{A}^{\top}\mathbf{b}.}\]

These are the normal equations. For the three measurements, \mathbf{A}=[1,1,1]^{\top} and \mathbf{b}=[2,3,4]^{\top}. Then \mathbf{A}^{\top}\mathbf{A}=3 and \mathbf{A}^{\top}\mathbf{b}=9, giving 3w=9 and w=3 again.

If \mathbf{A} has N rows and M columns, the normal equations have an M\times M matrix on the left and a vector of length M on the right. When the columns of \mathbf{A} are linearly independent,

\[\mathbf{w}=(\mathbf{A}^{\top}\mathbf{A})^{-1}\mathbf{A}^{\top}\mathbf{b}.\]

The inverse requires that independence condition. Duplicate columns, or more columns than rows, make it fail. A least-squares solution still exists, but its coefficients need not be unique. Understand the normal equations as a system to solve; an inverse is one way to express its solution when it exists.

Probability

Probability Basics

A probability lies between zero and one and describes how likely an event is. An event is a set of possible outcomes. For a fair six-sided die, the event “roll an even number” is \{2,4,6\} and has probability 3/6=1/2. Write P(A) or \Pr(A) for the probability of event A. Its complement, meaning “A does not occur”, has probability 1-P(A).

A joint probability describes events occurring together. A conditional probability describes one event given that another has occurred:

\[P(A\mid B)=\frac{P(A\cap B)}{P(B)}, \qquad P(B)>0.\]

For example, let A mean “the die shows an even number” and B mean “the die shows a number above three”. Once B is known, the possible outcomes are 4,5,6. Two of these are even, so P(A\mid B)=2/3, whereas P(A)=1/2.

Rearranging the conditional-probability definition gives the product rule:

\[P(A\cap B)=P(A\mid B)P(B).\]

In our example, this is (2/3)(1/2)=1/3, the probability of rolling 4 or 6. The product rule is always valid when the conditional is defined; it does not require independence.

The sum rule adds over alternatives. If B_1,\ldots,B_K are mutually exclusive and cover all possibilities, then

\[P(A)=\sum_{k=1}^{K}P(A\cap B_k) =\sum_{k=1}^{K}P(A\mid B_k)P(B_k).\]

For example, suppose we choose bag 1 with probability 1/3 and bag 2 with probability 2/3. Bag 1 contains three red balls and one blue ball; bag 2 contains one red ball and three blue balls. We draw a ball uniformly from the chosen bag. If R means “the ball is red”, then

\[P(R)=\frac{3}{4}\frac{1}{3}+\frac{1}{4}\frac{2}{3} =\frac{1}{4}+\frac{1}{6}=\frac{5}{12}.\]

We accounted for both ways a red ball can be drawn. Adding over the bag choice leaves the probability of the colour alone. This is called marginalisation.

Writing the joint probability in the two possible orders gives Bayes' rule:

\[P(B\mid A)=\frac{P(A\mid B)P(B)}{P(A)}, \qquad P(A)>0.\]

If the ball is red, the probability that we chose bag 1 is therefore

\[P(B_1\mid R) =\frac{P(R\mid B_1)P(B_1)}{P(R)} =\frac{(3/4)(1/3)}{5/12}=\frac{3}{5}.\]

The chance of bag 1 was 1/3 before seeing the colour; it becomes 3/5 after seeing red. The first is a prior probability and the second is a posterior probability. The factor P(R\mid B_1) describes how well bag 1 explains the observation and is called a likelihood when comparing bag choices. Notice that P(B_1\mid R) and P(R\mid B_1) answer different questions.

Two events are independent if

\[P(A\cap B)=P(A)P(B).\]

Knowing that one occurred then does not change the probability of the other, whenever the conditional probability is defined. Two independent fair coin tosses give P(\text{both heads})=(1/2)(1/2)=1/4. Merely having two outcomes does not make them independent; the experimental setup matters.

Conditional independence means independence after some information is specified. Return to the bags. Choose one bag, draw a ball, replace it, mix, and draw again. If the bag is known, the two draws are independent. Writing R_1 and R_2 for red on the two draws,

\[P(R_1\cap R_2\mid B_k) =P(R_1\mid B_k)P(R_2\mid B_k).\]

If the bag is unknown, the first draw gives information about which bag was chosen, and therefore about the second draw. The draws need not be independent overall even though they are independent conditional on the bag. Replacing the ball matters: without replacement, even a known bag changes composition after the first draw.

The abbreviation iid means independent and identically distributed. Repeated independent flips of the same coin, with an unchanged chance of heads, are iid. Different flips need not produce the same outcome; they follow the same probability rule. Independent flips of coins with different chances of heads would not be identically distributed.

Random Variables and Common Distributions

A random variable assigns a number to an uncertain outcome. Let Z be the number shown by a die, or let Z=1 for heads and Z=0 for tails. Uppercase letters often name random variables, and lowercase letters name particular values. The notation Z\sim p means that Z has distribution p.

For a discrete variable, a probability mass function assigns probabilities to individual values. These probabilities sum to one. For example, a fair die has P(Z=z)=1/6 for each z\in\{1,\ldots,6\}.

For a continuous variable, such as a length measurement, a density p(z) describes probabilities through areas:

\[P(a<Z<b)=\int_a^b p(z)\,dz, \qquad \int_{-\infty}^{\infty}p(z)\,dz=1.\]

An integral is a continuous version of adding contributions over possible values. The dz indicates the variable being integrated. For a variable with a density, one exact value has probability zero, although intervals can have positive probability. The density height can exceed one; the total area, not the height, must equal one.

For variables, the product and sum rules are often written more compactly as

\[p(u,v)=p(u\mid v)p(v), \qquad p(u)=\sum_v p(u,v).\]

Here the sum ranges over all values of a discrete variable V. For continuous V, use p(u)=\int p(u,v)\,dv instead. This is the same marginalisation idea as adding over the two bags.

The Bernoulli distribution describes one binary outcome Z\in\{0,1\}. Its parameter \mu is the probability of outcome one:

\[P(Z=z)=\mu^z(1-\mu)^{1-z}, \qquad P(Z=1)=\mu, \quad P(Z=0)=1-\mu.\]

For 0<\mu<1, the exponents act as switches. Substituting z=1 leaves \mu; substituting z=0 leaves 1-\mu. For a coin with chance of heads 0.7, these probabilities are 0.7 and 0.3. The endpoint cases \mu=0 and \mu=1 mean deterministic outcomes.

The categorical distribution describes one outcome among K alternatives. A spinner with red, green, and blue outcomes might have probabilities (0.2,0.5,0.3). In general, P(Z=k)=\mu_k, where \mu_k\geq0 and \sum_k\mu_k=1.

A one-hot vector records the outcome using one entry equal to one and all others zero. Green, the second colour, becomes \mathbf{t}=[0,1,0]^{\top}. For positive probabilities, the compact expression

\[p(\mathbf{t})=\prod_{k=1}^{K}\mu_k^{t_k}\]

selects the probability of the observed outcome. For green, it gives 0.2^0\,0.5^1\,0.3^0=0.5. You can always return to “the probability of colour k is \mu_k” if the vector form is unfamiliar.

The Gaussian, or normal, distribution describes a continuous value with a bell-shaped density:

\[p(z)=\mathcal{N}(z\mid\mu,\sigma^2) =\frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(z-\mu)^2}{2\sigma^2}\right), \qquad \sigma^2>0.\]

The mean \mu locates its centre. The standard deviation \sigma describes its spread, and \sigma^2 is its variance; we define these measures more precisely next. For example, repeated measurements of a length might be approximately Gaussian, centred at 10 centimetres with standard deviation 0.2 centimetres. A value of 10.2 is one standard deviation above the mean.

The squared distance in the exponent makes values farther from the centre less likely. The factor in front makes the total area one. Precision means inverse variance, so \beta=1/\sigma^2 is another way to describe spread: larger precision means smaller spread. Understand the parts of the density before trying to memorise the complete expression.

Expectation, Variance and Covariance

An expectation is a probability-weighted average. For a discrete random variable,

\[\mathbb{E}[Z]=\sum_z zP(Z=z), \qquad \mathbb{E}[g(Z)]=\sum_z g(z)P(Z=z).\]

For a continuous variable, replace the sum by an integral:

\[\mathbb{E}[g(Z)]=\int g(z)p(z)\,dz.\]

A fair die has expected value (1+2+3+4+5+6)/6=3.5. The expectation need not be a possible outcome. For a coin coded as one for heads and zero for tails, with chance of heads 0.7, the expectation is 1(0.7)+0(0.3)=0.7.

A sample average N^{-1}\sum_i z_i averages values actually observed. An expectation averages over the underlying probability distribution. Ten die rolls can average to 4 even though the expectation for a fair die is 3.5. A finite sample average is an estimate, not an exact population quantity.

Linearity of expectation says

\[\mathbb{E}[aU+bV+c] =a\mathbb{E}[U]+b\mathbb{E}[V]+c\]

for fixed constants, provided the expectations exist. Independence is not needed. For instance, \mathbb{E}[2Z+1]=2(3.5)+1=8 for the fair die. In contrast, \mathbb{E}[UV]=\mathbb{E}[U]\mathbb{E}[V] is not generally valid; independence is one sufficient condition.

The variance measures average squared distance from the mean:

\[\operatorname{Var}(Z) =\mathbb{E}[(Z-\mathbb{E}[Z])^2] =\mathbb{E}[Z^2]-(\mathbb{E}[Z])^2.\]

Suppose Z takes the values 2 and 4, each with probability 1/2. Its mean is 3, so

\[\operatorname{Var}(Z) =\tfrac12(2-3)^2+\tfrac12(4-3)^2=1.\]

Standard deviation is the square root of variance, so it is also 1 in this example. If Z is measured in centimetres, variance has units of squared centimetres and standard deviation has units of centimetres. For a Bernoulli variable, Z^2=Z, giving variance \mu-\mu^2=\mu(1-\mu).

For observed numbers, their average squared distance from the sample mean is N^{-1}\sum_i(z_i-\bar{z})^2. You may also encounter the sample-variance formula with denominator N-1. When estimating a population variance from iid observations, that denominator corrects the downward bias caused by estimating the mean from the same data. The formulas serve different purposes; always check which quantity is being calculated.

The covariance between two variables is

\[\operatorname{Cov}(U,V) =\mathbb{E}[(U-\mathbb{E}[U])(V-\mathbb{E}[V])].\]

Positive covariance means their deviations from their means tend to have the same sign; negative covariance means they tend to have opposite signs. For a simple example, let U be equally likely to be -1 or 1, and let V=2U. Both means are zero, and UV=2 in either case, so their covariance is 2. If instead V=-2U, their covariance is -2.

Independence implies zero covariance when second moments exist. Zero covariance alone does not generally imply independence: it rules out one particular measure of association, not every possible relationship.

For a random vector \mathbf{Z} with mean \boldsymbol{\mu}, collect covariances into a matrix:

\[\boldsymbol{\Sigma} =\mathbb{E}[(\mathbf{Z}-\boldsymbol{\mu})(\mathbf{Z}-\boldsymbol{\mu})^{\top}], \qquad \Sigma_{ij}=\operatorname{Cov}(Z_i,Z_j).\]

The diagonal entries are variances; the off-diagonal entries are covariances. For example,

\[\boldsymbol{\Sigma}=\begin{bmatrix}1&0\\0&4\end{bmatrix}\]

describes two coordinates with variances one and four and covariance zero. A multivariate Gaussian is a Gaussian distribution for a vector, specified by a mean vector and covariance matrix. For this particular family, a diagonal covariance means independent coordinates. Its full density is not needed to understand these ideas.

Pay attention to what an expectation averages over. The expression \mathbb{E}[Z] for a die averages all six outcomes. The conditional expectation \mathbb{E}[Z\mid Z>3] averages only 4,5,6, and is therefore 5.

One final identity is useful. Write m=\mathbb{E}[Z] and let c be a fixed number. Add and subtract m inside the square:

\[\begin{aligned} \mathbb{E}[(Z-c)^2] &=\mathbb{E}[((Z-m)+(m-c))^2]\\ &=\mathbb{E}[(Z-m)^2]+(m-c)^2 +2(m-c)\mathbb{E}[Z-m]\\ &=\operatorname{Var}(Z)+(m-c)^2. \end{aligned}\]

The cross term vanishes because \mathbb{E}[Z-m]=0. For the equally likely values 2 and 4, take c=0: the left side is 10, and the right side is 1+3^2=10. Practise the expansion and the averaging step separately.

An indicator is itself a binary random variable when its statement depends on a random outcome. Consequently,

\[\mathbb{E}[\mathbb{1}[A]]=1P(A)+0(1-P(A))=P(A).\]

For example, the average of indicators for heads is the observed fraction of heads, while the expectation of one such indicator is the coin's true probability of heads.

Basic Probability Bounds

An upper bound gives a value that a quantity cannot exceed. It need not equal that quantity. For events B_1,\ldots,B_J, the union bound says

\[P\left(\bigcup_{j=1}^{J}B_j\right) \leq\sum_{j=1}^{J}P(B_j).\]

Suppose each of three lamps has probability at most 0.01 of failing during an evening. The probability that at least one fails is at most 0.03. Adding the individual probabilities may count occasions with several failures more than once, so it gives an upper bound. The events need not be independent for this rule to hold.

Another kind of bound concerns sample averages. Flip a coin independently N times and let Z_i be one for heads and zero for tails. If its true chance of heads is \mu, then \mathbb{E}[Z_i]=\mu. The observed fraction of heads is \bar{Z}=N^{-1}\sum_i Z_i.

Hoeffding's inequality states that, for iid variables in [0,1] with common mean \mu,

\[P(|\bar{Z}-\mu|>\varepsilon) \leq2e^{-2N\varepsilon^2}, \qquad \varepsilon>0.\]

The left side is the chance that the observed average differs from the true mean by more than the tolerance \varepsilon. The coin example satisfies the conditions because its indicators are independent, follow the same distribution, and lie in [0,1]. We state the inequality here without proving it; the main tasks are to understand its assumptions and work with its algebra.

Now suppose we have J coins, chosen before the experiment, and flip each one independently N times. The coins can have different true probabilities of heads. Call coin j's estimate “bad” if it differs from its true probability by more than \varepsilon. Hoeffding bounds the bad event for each coin, and the union bound gives

\[P(\text{at least one bad estimate}) \leq2J e^{-2N\varepsilon^2}.\]

The union-bound step does not require independence between different coins' bad events. It is the repeated observations for each coin that must meet Hoeffding's assumptions.

Suppose we want the chance of any bad estimate to be at most \delta, where 0<\delta<1. It is sufficient that

\[2J e^{-2N\varepsilon^2}\leq\delta.\]

Solve for N one step at a time:

\[\begin{aligned} e^{-2N\varepsilon^2}&\leq\frac{\delta}{2J},\\ -2N\varepsilon^2&\leq\log\frac{\delta}{2J},\\ 2N\varepsilon^2&\geq\log\frac{2J}{\delta},\\ N&\geq\frac{1}{2\varepsilon^2}\log\frac{2J}{\delta}. \end{aligned}\]

Taking logs preserves the inequality because log is increasing. Multiplying by -1 reverses its direction, and -\log(\delta/(2J))=\log(2J/\delta). The final division is by the positive number 2\varepsilon^2.

For J=10 coins, tolerance \varepsilon=0.1, and failure probability \delta=0.05, the expression gives N\geq299.57\ldots. Thus, 300 flips per coin suffice for this bound. With probability at least 0.95, every observed fraction is within 0.1 of its coin's true probability. This does not say the coins have probability of heads at most 0.1.

We can instead choose a tolerance for given N,J,\delta:

\[\varepsilon=\sqrt{\frac{\log(2J/\delta)}{2N}}.\]

More observations reduce the bound, while controlling more estimates at once increases it. An upper bound can be loose; if a probability bound exceeds one, the trivial bound of one is more informative.

A second useful exponential inequality is 1-u\leq e^{-u} for 0\leq u\leq1. For a coin with chance of heads q, independence gives

\[P(\text{no heads in }N\text{ flips}) =(1-q)^N\leq e^{-Nq}.\]

For q>0, requiring e^{-Nq}\leq\delta gives N\geq\log(1/\delta)/q. This uses the same log and inequality rules. Focus on those steps and on why independence justifies the original product.

Calculus and Optimisation

Derivatives and Gradients

A derivative measures a function's local rate of change. For f(x)=x^2, the derivative is f'(x)=2x. At x=3, the slope is 6: a small increase \Delta x changes the output by approximately 6\Delta x. For example, 3.01^2-3^2=0.0601, close to 6(0.01)=0.06.

The basic rules we use are

\[\frac{d}{dx}c=0, \qquad \frac{d}{dx}x^r=rx^{r-1}, \qquad \frac{d}{dx}e^x=e^x, \qquad \frac{d}{dx}\log x=\frac{1}{x}.\]

The log rule requires x>0, and the power rule applies where the expression is defined and differentiable. Derivatives distribute over sums, and constant factors can be taken outside. Thus the derivative of 3x^2+2x+7 is 6x+2.

A partial derivative changes one variable while holding the others fixed. For

\[f(u,v)=u^2+3uv+2v^2,\]

we obtain

\[\frac{\partial f}{\partial u}=2u+3v, \qquad \frac{\partial f}{\partial v}=3u+4v.\]

When differentiating with respect to u, the term 2v^2 is constant and has derivative zero. When differentiating with respect to v, the term u^2 is constant instead. The symbol \partial reminds us that other variables are being held fixed.

The chain rule differentiates a composition. If y=h(a) and a=g(x), then

\[\frac{dy}{dx}=\frac{dy}{da}\frac{da}{dx}.\]

For y=(3x+1)^2, let a=3x+1. The outer derivative is dy/da=2a and the inner derivative is da/dx=3, so

\[\frac{dy}{dx}=2(3x+1)\times3=6(3x+1).\]

Forgetting the inner derivative would give the wrong answer. The same rule works with partial derivatives when an intermediate quantity depends on several variables.

The gradient collects the partial derivatives into one column vector. If \mathbf{w}=[w_1,\ldots,w_M]^{\top}, then

\[\nabla_{\mathbf{w}}f =\begin{bmatrix} \partial f/\partial w_1\\ \vdots\\ \partial f/\partial w_M \end{bmatrix}.\]

For the earlier function f(u,v), its gradient at (u,v)=(1,2) is [8,11]^{\top}. The first entry measures the change from moving u; the second measures the change from moving v. For a simple squared length,

\[f(\mathbf{w})=\frac12\|\mathbf{w}\|_2^2 =\frac12\sum_m w_m^2 \quad\Longrightarrow\quad \nabla_{\mathbf{w}}f=\mathbf{w}.\]

You can derive vector gradients one entry at a time rather than memorising a large table of matrix derivatives.

The sigmoid from the Basics section provides another chain-rule example. Write \sigma(a)=(1+e^{-a})^{-1}. Then

\[\sigma'(a) =-(1+e^{-a})^{-2}(-e^{-a}) =\frac{e^{-a}}{(1+e^{-a})^2} =\sigma(a)(1-\sigma(a)).\]

The two negative signs cancel. The final equality follows because 1-\sigma(a)=e^{-a}/(1+e^{-a}). At a=0, the derivative is (1/2)(1/2)=1/4. Remember this compact derivative, but also understand how to obtain it from the chain rule.

A second derivative measures how the slope changes. The functions x^2 and 10x^2 have second derivatives 2 and 20, respectively; the latter bends more sharply. For several variables, the matrix of second partial derivatives is called the Hessian. You only need this basic meaning of curvature here.

Optimisation, argmin/argmax and Gradient Descent

Optimisation means finding inputs that make a chosen function small or large. The function being optimised is called the objective. The notation \min returns the smallest objective value, while \operatorname*{arg\,min} returns an input that achieves it.

For example, if J(w)=(w-3)^2+2, then

\[\min_w J(w)=2, \qquad \operatorname*{arg\,min}_w J(w)=3.\]

Similarly, \max returns the largest value and \operatorname*{arg\,max} an input that achieves it. There may be several optimisers. An optimum may also fail to be attained: e^{-w} approaches zero as w grows, but never equals zero for any finite w.

For a differentiable function, an unconstrained local minimum in the interior of its domain has zero gradient. But a zero derivative does not by itself prove a minimum. At zero, -x^2 has a maximum, while x^3 has neither a minimum nor a maximum. For a differentiable convex function, a zero gradient does give a global minimum. A convex function has the property that the line segment joining two points on its graph lies on or above the graph; x^2 is a familiar bowl-shaped example.

Gradient descent searches for a minimum by taking repeated steps:

\[\mathbf{w}^{(s+1)} =\mathbf{w}^{(s)}-\eta\nabla_{\mathbf{w}}J(\mathbf{w}^{(s)}), \qquad \eta>0.\]

Here s labels the iteration, rather than a power, and \eta is the step size, also called the learning rate. Where the gradient is nonzero, its negative points in a direction of local decrease. The gradient is evaluated at the current point before calculating the next one.

For J(w)=(w-3)^2/2, the derivative is w-3. Starting at w^{(0)}=0 with \eta=0.1 gives

\[w^{(1)}=0-0.1(-3)=0.3, \qquad w^{(2)}=0.3-0.1(-2.7)=0.57.\]

Both steps move towards the minimum at three. A step that is too large can increase the objective: from zero, taking \eta=3 jumps to nine and increases J from 4.5 to 18. A local direction of improvement is not a guarantee for an arbitrarily large step.

Scaling or Adding a Constant to the Objective

Adding a constant independent of the variable being optimised does not change the minimiser. Neither does multiplying the whole objective by a positive constant. For example,

\[f(w)=(w-3)^2, \qquad g(w)=2(w-3)^2+7\]

both have minimiser w=3, although their minimum values are zero and seven. Multiplying by a negative number reverses the ordering and changes a minimisation problem into a maximisation problem.

“Constant” depends on which variables can change. In F(u,v)=(u-3)^2+v^2, the term v^2 is constant if we optimise only u and hold v fixed. If we optimise both u and v, it is not constant and must be kept.

Scaling only part of an objective can change the answer. For example,

\[f(w)=(w-2)^2+w^2, \qquad g(w)=2(w-2)^2+w^2\]

have minimisers 1 and 4/3, respectively. You can check these by differentiating. The extra factor changes the balance between the two terms. To preserve the same minimiser by scaling, scale the entire objective together.

A strictly increasing transformation also preserves which input gives the largest value. For the positive function q(w)=e^{-(w-2)^2},

\[\operatorname*{arg\,max}_w q(w) =\operatorname*{arg\,max}_w\log q(w) =\operatorname*{arg\,min}_w[-\log q(w)] =2.\]

The functions have different output values, but they select the same input. This is why distinguishing an optimum value from its location matters.

Constraints and Lagrange Multipliers

A constraint limits the values we are allowed to choose. Suppose we want to minimise

\[f(u,v)=u^2+v^2 \qquad\text{subject to}\qquad u+v=6.\]

Without the constraint, the minimum is at (0,0). That point is not allowed because its coordinates do not add to six. The allowed, or feasible, points lie on the line u+v=6.

For an equality constraint, a useful method introduces an extra unknown called a Lagrange multiplier. Write the constraint as u+v-6=0 and form the Lagrangian:

\[\mathcal{J}(u,v,\lambda) =u^2+v^2+\lambda(u+v-6).\]

Differentiate with respect to all three variables and set the derivatives to zero:

\[\frac{\partial\mathcal{J}}{\partial u}=2u+\lambda=0, \qquad \frac{\partial\mathcal{J}}{\partial v}=2v+\lambda=0, \qquad \frac{\partial\mathcal{J}}{\partial\lambda}=u+v-6=0.\]

The first two equations imply u=v. The third then gives u=v=3, and \lambda=-6. The candidate satisfies the constraint and has objective value 18.

We should still check that it is a minimum. Substituting v=6-u into the objective gives

\[u^2+(6-u)^2=2(u-3)^2+18.\]

This is at least 18 for every feasible point, so (3,3) is indeed the constrained minimum.

The general construction for minimising f(\boldsymbol{\theta}) subject to g(\boldsymbol{\theta})=0 is

\[\mathcal{J}(\boldsymbol{\theta},\lambda) =f(\boldsymbol{\theta})+\lambda g(\boldsymbol{\theta}).\]

For differentiable functions, at a constrained optimum where \nabla g\neq\mathbf{0}, the necessary equations are

\[\nabla f+\lambda\nabla g=\mathbf{0}, \qquad g(\boldsymbol{\theta})=0.\]

Geometrically, the objective cannot decrease by moving along the constraint at the optimum. Its gradient is perpendicular to those allowed directions. The multiplier makes the objective gradient and constraint gradient balance.

The multiplier is solved for together with the original variables; it is not an extra setting we choose beforehand. These equations identify stationary candidates, so feasibility and minimum checks still matter. We are not minimising the Lagrangian freely over all its variables. If a problem also has inequalities, such as nonnegative probabilities, its boundary needs separate attention; the equality equations alone do not handle every such case.

How These Pieces Will Be Used in CS3264

This table is a preview of the lectures, not additional prerequisite knowledge. The lectures will introduce the named methods and explain how the mathematical tools fit together.

Being able to work through the simple examples in these notes is the preparation you need. You are not expected to derive the lecture methods in advance.

Summary / quick reference

Keep these short rules readily available from memory.

Understand and practise the calculations. Try computing a dot product and checking the dimensions of a matrix product. Reproduce the bag calculation using Bayes' rule, find the variance of a two-outcome variable, differentiate (3x+1)^2, take a gradient-descent step, and solve the constraint u+v=6. For the sample-size bound, practise the log and inequality steps with the starting bound in front of you.

Read longer formulas through their ingredients. Understand that a Gaussian has a centre and spread, that the normal equations describe a least-squares solution, and that a bound has assumptions as well as an algebraic form. Begin with these meanings rather than memorising long expressions without context.

When you get stuck, identify the indices, check the dimensions, mark what is fixed, and name the rule used in the next step. These habits will make the new mathematics in the lectures easier to follow.