Title: Math and science / INF ML AI
Tags: information_theory ml dl copyright stats

Idea: Machine Learning Definition (Mitchell, 1997)
Description: A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

Idea: Independence & Conditional Independence
Description: Two random variables, \(X\) and \( Y \) are independent if the occurance of one does not give any information on the likelihood of the other event occuring. In other words, their probability distribution can be expressed as a product of two factors, one only involving \(X\), and one only involving \(Y\):
\[\forall x \in X, y \in Y, \, p(X = x, Y= y) = p(X = x)p(Y = y)\]
Two random variables, x and y are conditionally independentif, given knowledge of the occurance of \(Z\), knowledge of the occurance of \(X\) provides no information on the likeihood of the occurance of \(Y\). This can be expressed as:
\[\forall x \in X, y \in Y, z \in Z, \, p(X = x, Y= y | Z = z) = p(X = x | Z = z)p(Y = y | Z = z)\]
Example: Independent events
x: the number on a rolled dice
y: the number on another rolled dice
Conditionally independent
x: a person's height
y: the person's vocabulary
z: the person's age

Title: Covariance
Q: Let \( (\Omega, \mathrm{F}, \mathbb{P}) \) be a discrete probability space let \( X: \Omega \to S_x \) and \( Y : \Omega \to S_y \), be two random variables, where \( S_x\) and \( S_y \) are finite subsets of \( \mathbb{R} \). Then the covariance of \( X \) and \( Y \) is defined as the mean of the following random variable:
[\[ Z = \;\; ? \; \]]
In terms of \( X \) and \( Y \), the calculation for covariance is thus:
[\[ \mathrm{Cov}[X, Y] = \sum_{?} ? (? - \mathrm{E}[X])(? - \mathrm{E}[Y])) \]]
A: \[ Z = (X - \mathrm{E}[X])(Y - \mathrm{E}[X]) \]; \[ \mathrm{Cov}[X, Y] = \sum_{\omega \in \Omega} p(\omega) (X(\omega) - \mathrm{E}[X])(Y(\omega) - \mathrm{E}[Y])) \]
BackOnlyText: Covariance is a real that gives some sense of how much two variables are linearly related to each other, as well as the scale of these variables. Covariance is a function of a probability space and two random variables.
In it's most reduced form, a random variable that is the product of two other random variables is what fully determines covariance, which can be seen as the mean of this variable. \(X \cdot Y : \Omega \to S_x \times S_y \). Then, covariance is a can be considered a function of this random variable. The expectation can be carried out by summing over the product space, and using the probability \( P(x, y) \) which can be considered syntax for \( \mathbb{P}((X \times Y)^{-1}((x, y)) \), where \( \mathbb{P} \) is the function in \( (\Omega, \mathrm{F}, \mathbb{P} ) \):
\[ \begin{align*} \operatorname{Cov}(X, Y) &= \mathrm{E}[(X - \mathrm{E}[X])(Y - \mathrm{E}[Y])] \\ \operatorname{Cov}(X, Y) &= \sum_{x \in S_x, y \in S_y} P(x, y)(x - \mathrm{E}[X])(y - \mathrm{E}[Y]) \\ \end{align*} \]
Not just two probability distributions
It's important to note how you can't tell if two random variables are independent just by looking at both of their probability distributions. What is important is if there is some relationship between where \(\omega\) is sent by the function \(X\) and where it is sent by \(Y\).
Interpreting the number
High absolute values of the covariance mean that the values change very much and are both far from their respective means at the same time. If the sign of the covariance is positive, then both variables tend to take on high values simultaneously. If the sign is negative, then one variable tends to taken on a relatively high value at the times where the other takes on a relatively low value and visa versa.
Independence and covariance
Two random variables that are independence have zero covariance! :o
This is a “implies” statement, and not a iff statement. (Dependent variables can have zero covariance).
Relation to correlation
The correlation, another measure, normalized the contribution of each variable in order to remove the effect of scale.
Alternative form
Covariance has another form:
\[ \operatorname{Cov}(X, Y) =\mathrm{E}[XY] - \mathrm{E}[X]\mathrm{E}[Y]\]
Some visual reasoning:
Covariance (and many operations on distributions) can be best understood by rooting one's focus on the distribution of a 1D random variable just before an operation such as taking an expectiation. For covariance, this means focusing on the random variable \( (X - \overline{X})(Y - \overline{Y}) \) and it's distribution,  \( F_{(X - \overline{X})(Y - \overline{Y})} \), which is a function \( \mathbb{R} \to \mathbb{R} \); covariance is the mean of this random variable. Start stepping backwards by seeing each value of \( F_{(X - \overline{X})(Y - \overline{Y})} \) as having collected it's weights from the 2D distribution \( F_{(X - \overline{X}, Y - \overline{Y})} \)...notice the comma there! These weights are the result of a sort of cartesian product of the distributions \( F_{X - \overline{X}} \) and \( F_{Y - \overline{Y}} \).
There seems to be a typo in the below image. \( F_{(X,Y)} \) should have domain \( \mathbb{R} \times \mathbb{R} \), not \( \mathbb{R} \).
More than 3 variables
The covariance of a random vector \( x \varepsilon R^n \) is an n x n matrix, such that \( Cov(x)_{i,j} = Cov(x_i, x_j) \). The diagonal elements of the covariance matrix gives the variances of each vector element.

Idea: Bernoulli Distribution
Description: The bernoulli distribution is a distribution over a single binary random variable.
Suppose you perform an experiment with two possible outcomes: either success or failure. Success happens with probability p, while failure happens with probability 1-p. A random variable that takes value 1 in case of success and 0 in case of failure is called a Bernoulli random variable (alternatively, it is said to have a Bernoulli distribution).
Let [$]p \in (0, 1)[/$]. We say that X has a Bernoulli distribution with parameter p if its probability mass function is:
A random variable having a Bernoulli distribution is also called a Bernoulli random variable.
Expected value and variance:
E[X] = p
Var[X] = p(1-p)
A sum of independent Bernoulli random variables is a binomial random variable.

Idea: Logistic sigmoid
Description: [latex]
$\sigma(x) = \frac{1}{1+e^{-x}}$
[/latex]
The logistic sigmoid:
The logistic function is a special case sigmoid function.
A sigmoid function is a mathematical function having an "S" shaped curve (sigmoid curve). A wide variety of sigmoid functions have been used as the activation function of artifical neurons. They are used to produce the [$]\phi[/$] parameter of a Bernoulli distribution.
A collection of sigmoid functions, normalized to have a gradient of 1 at the origin:

Idea: Rectifier and the softplus function
Description: The rectifier is an activation function defined as:
[latex]
$ f(x) = max(0, x)$
[/latex]
where x is the input to a neuron. This is also known as a ramp function and is analogous to half-wave rectification in electrical engineering. This activation function was first introduced to a dynamical network by Hahnloser et al. in a 2000 paper in Nature with strong biological motivations and mathematical justifications. It has been used in convolutional networks more effectively than the widely used logistic sigmoid (which is inspired by probability theory; see logistic regression) and its more practical counterpart, the hyperbolic tangent. The rectifier is, as of 2015, the most popular activation function for deep neural networks.
Plot of the rectifier (blue) and softplus (green) functions:
The softplus function is defined as:
[latex]
$\zeta(x) = log(1+e^x)$
[/latex]
The softplus function is useful for producing the [$]\theta[/$] parameter of a normal distribution because of its range [$](0, \infty)[/$].
The softplus function is named as such, due to it being a "softened" version of:
[latex]
$ x^{+} = max(0, x)$
[/latex]

Idea: Types of machine learning tasks
Description: Classification
The computer is asked to specify which of k categories some input belongs to. The learning algorithm is usually asked to produce a function [$] f: \mathbb{R}^n \rightarrow \{1,...,k\} [/$]. When y = f(x), the model assigns an input described by vector x to a category identified by numeric code y. Another type of algorithm might instead output a probability distribution over classes, instead of just a single result.
Classification with missing inputs
When some of the inputs can be missing, the learning algorithm, instead of defining a single function taking the input vector, it must define a set of functions, one function for each variantion of missing inputs. This type of situation arrises frequently in medical diagnostics, as many medical tests are expensive or invasive. One way to efficiently define all these functions is to learn a probability distribution over all variables, then obtain specific functions my marginalizing out the missing variables. Thus, with n inputs, 2^n functions can be obtained. Many other tasks described below can also be generalized to work with missing inputs.
Regression
The computer is asked to predict a numerical value given some input. To solve this task, the learning algorithm must output a function [$] f: \mathbb{R}^n \rightarrow \mathbb{R}[/$].
Transcription
The machine learning system is asked to observe a relatively unstructured representation of some kind of information and to convert it to discrete textual/binary form. For example, convert an image of text to a sequence of characters; convert a recording of speech to text.
Machine Translation
The input is already a sequence of symbols in some language, and the learning algorithm is asked to convert this into a sequence of symbols in another language. This is commonly applied to natural languages. 5
Structured Output
Structured output tasks are any task where the output is a vector (or any other multi-valued data structure) where there is important relationships between the elements. For example, parsing natural language text into a structure describing its grammar. The category of structured output is broad and subsumes transcription and translation tasks. Other examples include: annotating roads in maps, captioning images. The output of these algorithms is tightly interrelated values (for the caption case, the output must be a valid sentence).
Anomaly detection
The computer sifts through a set of events or objects and flags some of them as being unusual or atypical.
Synthesis and sampling
The machine learning algorithm is asked to generate new examples that are similar to those in the training data. It is useful when generating large volumes of content by hand would be expensive, boring, or require too much time. Examples: video games generating textures for objects and landscapes.
Imputation of missing values
The machine learning algorithm is given an example vector, but with some entries missing. The task is to predict the values of the missing entries.
Denoising
The machine learning algorithm is given a corrupted example (a vector), obtained by an unknown corruption process from a clean example. The algorithm must predict the clean example from the corrupted version. More generally, it must predict the conditional probability distribution p(non-corrupted case | corrupted case).
Density estimation (probability mass function estimation)
The machine learning algorithm must learn the probability density function of the space from which the multi-dimensional examples are drawn from. Knowing the probability distribution can help with solving some of the other problems described above.

Idea: Maximum likelihood estimation (MLE)
Description: Say you have some data. Say you're willing to assume that the data comes from some distribution -- perhaps Gaussian. There are an infinite number of different Gaussians that the data could have come from: different means, different variances. MLE will pick the Gaussian that is "most consistent" with your data (the precise meaning of consistent is explained below).
So say you've got a data set of y = -1,3, and 7. The most consistent Gaussian from which that data could have come has a mean of 3 and a variance of 16. It could have been sampled from some other Gaussian. But one with a mean of 3 and variance of 16 is most consistent with the data in the following sense: the probability of getting the particular y values you observed is greater with this choice of mean and variance, than it is with any other choice.
Moving to regression: instead of the mean being a constant, the mean is a linear function of the data, as specified by the regression equation. So, say you've got data like x = 2,4,10 along with y from before. The mean of that Gaussian is now the fitted regression model X′β^
, where β^=[−1.9,.9]
[remove?]
Moving to GLMs: replace Gaussian with some other distribution (from the exponential family). The mean is now a linear function of the data, as specified by the regression equation, transformed by the link function. So, it's g(X′β)
, where [$]g(x)=e^x/(1+e^x)[/$] for logit (with binomial data).
Reference: http://times.cs.uiuc.edu/course/410/note/mle.pdf

Idea: Entropy
Description: When using variable length encoding to encode a set of tokens, using a shorter code for more common tokens will result in shorter messages on average. The minimum average message length given a distribution of tokens is called the entropy of the distribution.
Codespace and decodability
When designing variable length coding schemes, codes must be designed to be uniquely decodable. For example, if 0 and 01 are both codewords, then it is not clear which code begins the string: 0100111 [or is it?]. One way of making codes uniquely decodable is to assert that no codeword should be the prefix of another codeword. Codes that obey this rule are called prefix codes.
One way to think about this is that every codeword requires a sacrifice from the space of possible codewords. If we take the codeword 01, we lose the ability to use any codewords it's a prefix of. The space lost by using the codeword 01, of length 2, is a quarter of all possible codewords:
Optimum encodings
You can think of having a limited budget to spend on getting short codewords. We pay for one codeword by sacrificing a fraction of possible codewords. Short codewords reduce the average message length be are expensive in using up the available codewords.
The cost of codewords decreases exponentially with the length of the codeword:
(Shown here with natuaral logarithm, instead of base 2. A constant factor can express the difference).
Note that if the cost decays as a (natural) exponential, it is both the height and the area.
A way of arriving at an optimum encoding is to distribute our budget in proportion to how common an event is. So if one event happens 50% of the time, we spend 50% of our budget buying a short codeword for it.
From the decaying exponential above, and the assertion that we will spend p(x) on a codeword for event x, we can state the following:
[latex]
\begin{align}
cost = p(x) \\
cost = \frac{1}{2^{L(x)}} \\
L = log_2(\frac{1}{cost}) \\
L = log_2(\frac{1}{p(x)}) \\
\end{align}
[/latex]
After choosing the codeword length for each word, we can calculate the fundamental limit of how short one can get the average message to communicate events from a particular probability distribution, p. This limit, the average message length using the best possible code, is called the entropy of p, H(p). This average message length is the expected message length:
[$]
H(p) = \sum_x p(x) \log_2(\frac{1}{p(x)})
[/$]
Implications
This average amount of information needed to communicate something has clear implications for compression. It also quantifies uncertainty: If I knew for sure what was going to happen, I wouldn't have to send a message at all; if there's 64 different things that could happen with 50% probability, I need to send 6 bits. The more concentrated the probability, the shorter the average message that can be cleverely crafted. The more uncertain the outcome, the more I learn, on average, when I find out what happened.
Copied from:
http://colah.github.io/posts/2015-09-Visual-Information/#fnref1
Example: Given the messages and frequencies:
One possible encoding is a fixed length encoding:
L(x) is the length of the codeword; p(x) is the probability of each word being sent.
In this case, the average encoding length is 2 bits.
Another possible encoding uses a short codeword for the most common words:
The codeword length chart looks like:
The average encoding length is now a shorted 1.75 bits, the fundamental limit for this distribution. Thus, it is said that the entropy of the distribution = the area of the bars = 1.75 bits.

Title: Cross-Entropy and KL divergence
Consider that we have an encoding scheme for sending codewords from a set \( C \) whose frequencies are given by the probability distribution \( q: C \to \mathbb{R} \). Assume that this scheme achieves the minimum average message length possible. The minimum possible average message length for any such encoding is equal to the entropy of the distribution, given by the equation:
\[ H(q) =\sum_{x \in C} q(x) \log_2(\frac{1}{q(x)}) \]
Here, the syntax presents \( H \) as an operator taking in a distribution over \( C \).
Now, imagine that the same codewords are sent, but the frequency distribution of the codewords is changed to \( p: C \to \mathbb{R} \); the codewords are no longer optimized to the distribution. The new average length is given by the cross-entropy of \( q \) relative to \( p \):
\[ H_q(p) = \sum_{x \in C} p(x) \log_2(\frac{1}{q(x)}) \]
\( H_q(p) \) is also as an operator taking in a distribution over \( C \). Keeping this in mind helps remember the placement of \( q \) and \( p \) in the syntax \( H_q(p) \).
The length of a codeword is still the same (\( \log_2(\frac{1}{q(x)}) \)) , but the probability of the codeword being sent/received has changed to \( p(x) \). The cross-entropy is always larger than the entropy of the original distribution. If we were to then update our encoding to a better \( p \)-optimized encoding, our average message length would decrease from \( H_q(p) \) to \( H(p) \).
KL divergence (a pseudo-difference measure between distributions)
Cross-entropy gives us a way to express how different two probability distributions are; the more different the distributions \( p \) and \( q \) are, the more the cross-entropy of \( q \) with respect to \( p \) will be bigger than the entropy of \( p \).
And the same goes for the cross-entropy of \( p \) with respect to \( q \):
The differences, \( D_q(p) \) and \( D_p(q) \) are called Kullback-Leibler divergences (KL divergence). The KL divergence from \( q \) to \( p \), \( D_q(p) \) is defined as:
\[ D_q(p) = H_q(p) - H(p) \]
In words
The average message length reduction of using a \( q \)-optimized encoding when the transmission distribution is \( p \), then switching to a \( p \)-optimized encoding; this is the KL divergence from \( q \) to \( p \).
BackOnlyText: Distance-like
The KL divergence is like a distance between two distributions; however, the KL divergence is not symmetric: it is possible for \( D_p(q) \neq D_q(p) \), so it is not a true distance measure. Often in machine learning we want one distribution to be close to another. Minimizing the KL divergence is a natural way to minimize the distance between two distributions.
The formulation of KL-divergence
There are two ways of thinking about the change in message length: you have an encoding, then the transmission distribution changes, or the transmission distribution stays the same and you switch encodings. The first situation might suggest a measure of difference like:
\[ (\text{average length of the p-optimized encoding under q}) - (\text{average length of the p-optimized encoding under p}) \]
The KL-divergence represents the second situation (changing encoding with fixed transmission distribution):
(average length of the q-optimized encoding under p) - (average length of the p-optimized encoding under p)
The KL divergence makes more sense when viewed as a calculation, as the summations share the same factor:
\[ \begin{aligned} H_q(p) &= \sum_{x \in C}q(x) \log_2(\frac{1}{p(x)}) - \sum_{x \in C}q(x) \log_2(\frac{1}{q(x)}) \\ &= \sum_{x \in C}q(x) \log_2(\frac{q(x)}{p(x)}) \\ \end{aligned} \]
Compare this to the calculation required for the first formulation:
\[ \sum_{x \in C}q(x) \log_2(\frac{1}{p(x)}) - \sum_{x \in C}p(x) \log_2(\frac{1}{p(x)}) \]
This can't be simplified in the same way as the KL divergence can.
Source: http://colah.github.io/posts/2015-09-Visual-Information/#fnref1

Idea: Incremental average (estimate update)
Description: Statement:
\[ A_n = A_{n-1} + \frac{1}{n}(V_n - A_{n-1}) \]
Alterative form:
\[ \mathrm{NewEstimate} \leftarrow \mathrm{OldEstimate} + \operatorname{StepSize}[\mathrm{NewData} - \mathrm{OldEstimate}] \]
The second form describes updating our estimate of the average by multiplying an error term, \( \mathrm{NewData} - \mathrm{OldEstimate} \), by a weighting factor, \( \mathrm{StepSize} \). \( \mathrm{StepSize} \) is \( \frac{1}{n} \) when all data points are weighted equally.
The average, \( A_{n-1} \) is known for a sequence of \( n-1 \) values, \( V_1, V_2, ..., V_{n-1} \). If the next value, \( V_n \) is included in the sequence, the new average, \( A_{n} \), can be computed by adding the new component of the average, \( \frac{1}{n}V_{n} \), to the old average transfered from an \( n-1 \) denominator to an \( n \) denominator, (\( A_{n-1} - \frac{1}{n}A_{n-1} \)).
The (\( A_{n-1} - \frac{1}{n}A_{n-1} \)) component is easy to understand from an example: the difference between 1/4 and 1/5 is 1/(4*5). If we want to find the total divided by 5, and already have the total divided by 4, we can obtain the former by subtracting the known difference, 1/(4*5), which is the average divided by 4, divided by 5 again.

Idea: Softmax
Description: The name "softmax" originates in contrast to the argmax function (considered a hard-max) which extracts the index of the element having the greatest value.
The argmax function with one-hot encoding:
[$$]
argmax(\begin{bmatrix}0.79 \\ 5.3 \\ -10.8 \end{bmatrix}) = \begin{bmatrix}0 \\ 1 \\ 0 \end{bmatrix}
[/$$]
Compared to the softmax function:
[latex]
\begin{gather*}
softmax(\begin{bmatrix}0.79 \\ 5.3 \\ -10.8 \end{bmatrix}) =
\begin{bmatrix} e^{0.79}/203 \\ e^{5.3}/203 \\ e^{-10.8}/203 \end{bmatrix} = \begin{bmatrix} 0.011 \\ 0.989 \\ 0.000 \end{bmatrix} (3df)
\\
\text{Where } e^{0.79} + e^{5.3} + e^{-10.8} = 202.54
\end{gather*}
[/latex]
[$]e[/$] doesn't need to be the base and a more general form for the function is:
[$]e^{\beta x}[/$] where [$]\beta[/$] can be alterted to effectively change the base. It can be understood from this format how softmax approximates argmax. [$]\text{As } \beta \rightarrow \infty, \sigma(z) \rightarrow argmax(z)[/$]
Benefits of softmax over argmax include:
* softmax is differentiable
* softmax is continuous
* softmax is monotonic
* softmax is positive for all inputs
Properties of softmax:
* invariant under translation. [$]\sigma(\vec{v} + \vec{c})_i =
\frac{e^{\vec{z}_i + c}}
      {\sum_{k=1}^{k=|\vec{z}|}e^{\vec{z}_k + c}} =
\frac{e^{\vec{z}_i} e^c}
      {\sum_{k=1}^{k=|\vec{z}|}e^{\vec{z}_k}e^{c}} =
\sigma(\vec{v})[/$]
* not invariant under scaling.
The sigmoid function is a special case of the softmax function. The sigmoid function is a softmax of 1D input in 2D space where one variable is kept as 0 (e.g. input is points along the x-axis in the (x,y) plane):
[$]sigmoid(x) = \frac{e^x}{e^0 + e^x} = \frac{e^x}{1 + e^x}[/$]. Thus, the softmax activation function is said to generalize the sigmoid activation function to higher dimensions.
History
From Wikipedia:
In machine learning, the term "softmax" is credited to John S. Bridle in two 1989 conference papers, Bridle (1990a):[8] and Bridle (1990b):[3]
We are concerned with feed-forward non-linear networks (multi-layer perceptrons, or MLPs) with multiple outputs. We wish to treat the outputs of the network as probabilities of alternatives (e.g. pattern classes), conditioned on the inputs. We look for appropriate output non-linearities and for appropriate criteria for adaptation of the parameters of the network (e.g. weights). We explain two modifications: probability scoring, which is an alternative to squared error minimisation, and a normalised exponential (softmax) multi-input generalisation of the logistic non-linearity.[9]
For any input, the outputs must all be positive and they must sum to unity. ...
Given a set of unconstrained values, [$]V_{j}(x)[/$], we can ensure both conditions by using a Normalised Exponential transformation:
        [$]Q_{j}(x)=e^{V_{j}(x)}/\sum _{k}e^{V_{k}(x)}[/$]
This transformation can be considered a multi-input generalisation of the logistic, operating on the whole output layer. It preserves the rank order of its input values, and is a differentiable generalisation of the ‘winner-take-all’ operation of picking the maximum value. For this reason we like to refer to it as softmax.
Wikipedia has good coverage of the motivation of the softmax function.

Idea: What is the derivative of negative log MLE (MLE used as a negative cost) when the variables are passed through softmax activations?
Description: The derivative of the cost function is needed for back-propagation.
When the output layer uses a MLE/cross-entropy cost and softmax activation, the derivative of the cost function combined with the activation function simplifies to a very simple expression. This note covers this computation.
Consider the last layer of a neural network shown below:
For the given training example \( x_1 \), the correct category is 2 (out of all categories 0,1 and 2). Only the output corresponding to category 2 is used in the calculation of the loss contributed by the example. The loss is given by:
\[ Loss_{ex_1} = -ln(p_3) = -ln(\frac{e^{f_3}}{e^{f_1} + e^{f_2} + e^{f_3}}) \]
While only the probability for the correct category is used to calculate the loss for the example, the other outputs, \( p_1 \) and \( p_2 \) still affect the loss, as \( p_3 \) depends on these values (all sum to 1).
The partial derivatives will be:
\[ \begin{align*} \frac{\partial L}{\partial f_1} &= p_1 \\ \frac{\partial L}{\partial f_2} &= p_2 \\ \frac{\partial L}{\partial f_3} &= -(1-p_3) = p_3 - 1\end{align*} \]
So if we have output probabilities [0.1, 0.3, 0.6], then the derivative of the loss with respect to last layer's output before applying the softmax activation will be [0.1, 0.3, -0.4].
Derivations
Formulating the derivative of loss wrt different variables is simplified if the log and exponential are canceled at the beginning:
\[ \begin{align*} Loss_{ex_1} = -ln(p_3) &= -ln(\frac{e^{f_3}}{e^{f_1} + e^{f_2} + e^{f_3}}) \\  &= ln(\frac{e^{f_1} + e^{f_2} + e^{f_3}}{e^{f_3}}) \\ &= ln(e^{f_1} + e^{f_2} + e^{f_3}) - ln(e^{f_3}) \\ &= ln(e^{f_1} + e^{f_2} + e^{f_3}) - f_3  \end{align*} \]
From here, the partial derivates are obvious. For example:
\[ \begin{align*} \frac{\partial L}{\partial f_1} &= \frac{\partial}{\partial f_1}(ln(e^{f_1} + e^{f_2} + e^{f_3}) - f_3) \\ &= \frac{\partial}{\partial x}(ln(x)) \frac{\partial}{\partial f_1}(e^{f_1} + e^{f_2} + e^{f_3}) \\ &= \frac{1}{x} e^{f_1} \\ &= \frac{e^{f_1}}{e^{f_1} + e^{f_2} + e^{f_3}} \\ &= p_1 \end{align*} \]
The below image is part of a separate card, but I'm including it here, as it is quite relevant.
Old image:
Some old stuff:
Given the loss (lets just call it L, with the example 1 being implicit), we wish to find: [$]\frac{\partial L}{\partial f_1} \text{, } \frac{\partial L}{\partial f_2} \text{, } \frac{\partial L}{\partial f_3}[/$]. First consider [$]f_1[/$]:
\[ \begin{align*} \frac{\partial L}{\partial f_1} = \frac{\partial}{\partial f_1}(-ln(p_3)) &= (\frac{\partial}{\partial x}(-ln(x)) (\frac{\partial}{\partial y}(\frac{e^{f_3}}{y + e^{f_2} + e^{f_3}}))(\frac{\partial}{\partial f_1}(e^{f_1})) \\ \text{where } x = \frac{e^{f_3}}{y + e^{f_2} + e^{f_3}}, \text{ and } y = e^{f_1} \\ &= (- \frac{1}{x})(\frac{-e^{f_3}}{(y + e^{f_2} + e^{f_3})^2})(e^{f_1}) \\ &= (-\frac{e^{f_1} + e^{f_2} + e^{f_3}}{e^{f_3}})(\frac{-e^{f_3}}{(e^{f_1} + e^{f_2} + e^{f_3})^2})(e^{f_1}) \\ &= \frac{e^{f_1}}{e^{f_1} + e^{f_2} + e^{f_3}} \\ &= p_1 \end{align*} \]
Similarly, [$]\frac{\partial L}{\partial f_2} = p_2[/$]. [$]\frac{\partial L}{\partial f_3}[/$] is calculated as follows:
\[ \begin{align*} \frac{\partial L}{\partial f_3} = \frac{\partial}{\partial f_3}(-ln(p_3)) &= (\frac{\partial}{\partial x}(-ln(x)) (\frac{\partial}{\partial y}(\frac{e^{f_3}}{e^{f_1}+ e^{f_2} + y}))(\frac{\partial}{\partial f_3}(e^{f_3})) \\ \text{where } x = \frac{e^{f_3}}{e^{f_1} + e^{f_2} + y}, \text{ and } y = e^{f_3} \\ &= (- \frac{1}{x})(\frac{1}{e^{f_1} + e^{f_2} + y} - \frac{e^{f_3}}{e^{f_1} + e^{f_2} + y})(e^{f_3}) \\ &= (- \frac{e^{f_1} + e^{f_2} + e^{f_3}}{e^{f_3}})(\frac{1}{e^{f_1} + e^{f_2} + e^{f_3}} - \frac{e^{f_3}}{e^{f_1} + e^{f_2} + e^{f_3}})(e^{f_3}) \\ &= -(1 - \frac{e^{f_3}}{e^{f_1} + e^{f_2} + e^{f_3}}) \\ &= p_3 - 1 \end{align*} \]

Title: Shannon information content
Q: For an ensemble, \( X = (x, A_x, P_x) \), the Shannon information content of an event, \( x \) is defined to be:
\[ h(x) = [...]  \\
\text{Where 'x' may be an outcome: a subset of } A_x \]
It is measured in bits.
A: log_2 \frac{1}{P(x)}
BackOnlyText: The information content of an event/information is equivalent to the factor (represented as the exponent of 2) by which the space of possible outcomes shrinks if it is to be assumed that event/information \( x \) is true.  Can may be helpful for intuition to write \( log(\frac{1}{P(x)}) \) as \( -log(P(x)) \).
The information content comes in this form so that the combination of multiple events/information can be easily related. For example, if an event A causes the set of possible outcomes to shrink by a factor of 4, and another event, event B, causes the set of possible outcomes to shrink further by a factor of 8, then the overall factor of shinkage is 32. The information content as presented here has a multiplicative effect. If we want information content to have the property of additivity in this case, then we can represent the information content as the exponent of some base: \( c^{log_c(4) + log_c(8)} = 32 \). For the Shannon information content, the base is 2. This makes the information content 2 bits and 3 bits respectively for a total of 5 bits: \( 32 = 2^2 + 2^3 \).
Example: If in a class of 32 people it is someones birthday, and I tell you that the person whose birthday it is has blue eyes and 26 out of the 32 people have blue eyes, then the space of possible outcomes has reduced from 32 to 26. This is a factor of \( \frac{32}{26} = 1\frac{1}{4} \).
[latex]
\begin{align}
2^x &= 1.25 \\
x &= log_2(1.25) \\
x &= 0.3219
\end{align}
[/latex]
So the Shannon information content of the information or event "the birthday person has blue eyes" is 0.3219 bits.
If instead there were only 2 people with blue eyes in the class, the space of possible outcomes reduces to 2. This is a reduction by a factor of 16. The Shannon information content is thus 4 bits.

Title: Entropy of an ensemble
The entropy of an ensemble, \( X = (x, A_x, P_x) \), is defined to be the average Shannon information content over all outcomes:
\[ H(X) = \sum_{x \in A_x}P(x) \log \frac{1}{P(x)} \]
Properties of entropy:
- \( H(X) \geq 0 \) with equality iff some outcome has probability 1.
- Entropy is maximized if the probability of outcomes is uniform.
- The Entropy is less than the log of the number of outcomes.
The last two points can be expressed as:
\[H(X) \leq \log(|A_x|) \text{, with equality iff all outcomes have probability } \frac{1}{|A_x|} \]
Proof on the back side.
BackOnlyText: Proof that \( H(X) \leq \log(|A_x|) \):
First note that:
\[ \begin{align*} E[\frac{1}{P(X)}] &= \sum_{i \in A_x} P(i) \frac{1}{P(i)} \\ &= \sum_{i \in A_x} 1 \\ &= |A_x| \\ \end{align*} \]
Now then:
\[ \begin{align*} H(X) &= \sum_{i \in A_x} P(i) \log\frac{1}{P(i)} \\ &= \sum_{i \in A_x}P(i)f(\frac{1}{P(i)}) \\ \end{align*} \]
Where \( f(u) = \log(u) \) is a concave function. Then, Using Jensen's inequality we can say:
\[ \begin{align*} H(X) &= E[f(\frac{1}{P(X)})] \\ &\leq f(E[\frac{1}{P(X)}]) \\ &= \log(|A_x|) \end{align*} \]
Perspectives on entropy:
- If \( X \) is a random variable, we can create another random variable, let's call it \( Y \), by applying a fuction to the outcomes, \( Y = f(X) \). What if this function depended not on the value of the outcome, but on the probability of the outcome? As there is a function P that maps outcomes to probabilities, we could create a random variable \( Y = P(X) \). For Shannon information content and entropy, we create the variable \( Y = \log \frac{1}{P(X)} \). The entropy is the expected value of this random variable.

Idea: Joint entropy of two random variables
Description: For two ensembles, \( X = (x, A_x, P_x) \) and \( Y = (y, A_y, P_y) \), where there may be dependency between \(P_x \) and \(P_y \), the joint entropy of \(X\), \(Y\) is:
\[H(X, Y) = \sum_{x \in A_x} \sum_{y \in A_y} P(x, y)log \frac{1}{P(x, y)} \]
Entropy is additive for independent random variables.
Proof
\[ \begin{align*} H(X, Y) &= \sum_{x \in A_x} \sum_{y \in A_y} P(x)P(y)log\frac{1}{P(x)P(y)} \\ &= \sum_{x \in A_x} \sum_{y \in A_y} P(x)P(y)log\frac{1}{P(x)} +\sum_{x \in A_x} \sum_{y \in A_y} P(x)P(y)log\frac{1}{P(y)} \\ &=\sum_{x \in A_x}P(x)log\frac{1}{P(x)} + \sum_{y \in A_y} P(y)log\frac{1}{P(y)} \text{ (the first sum's terms are independent of y, and the second's independent of x)}\\ &= H(X) + H(Y)\end{align*} \]

Idea: Decomposition of entropy
Description: todo

Idea: Kullback-Leibler divergence and Gibbs' inequality
Description: Relative entropy or Kullback-Leibler divergence from one distribution \( P(x) \) to another \( Q(x) \), both defined over the same alphabet \( A_x \) is:
\[ D_{KL}(P||Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)} \]
The relative entropy satisfies Gibbs' inequality:
\[ D_{KL}(P||Q) \ge 0 \]
With equality only if P = Q.
The relationship is not symmetric under interchange of the distributions P and Q, so \( D_{KL}(P||Q) \ne D_{KL}(Q||P) \), so \( D_{KL} \) is not strictly a distance, dispited it being sometimes called the 'KL distance'.

Idea: Jensen's inequality
Description: If \( f \) is a convex (smile) function and \( X \) is a random variable then:
\[ E[f(X)] \ge f(E[X]) \]
If \( f \) is strictly convex and \( E[f(X)] = f(E[X]) \), then the random variable \( X \) is a constant.
Intuition:
Proof:
Intuition #2
The following is taken from Andrew Ng's notes for CS229:
TODO
Example: Q1: Three squares
Three squares have average area \( \bar{A} = 100 m^2 \). The average of the lengths of their sides is \( \bar{l} = 10 m \). What can be said about the size of the largest of the three squares?
A1:
Let \( x \) be the length of the side of a square, and let the probability of \( x \) be \( \frac{1}{3}, \frac{1}{3}, \frac{1}{3} \) over the three lengths, \( l_1, l_2, l_3 \). Then the information that we have is:
* \( E[X] = 10 \)
* \( E[f(X)] = 100 \text{, where } f(x) = x^2 \)
\( f \) is a strictly convex function and the equality \( E[f(X)] = f(E[X]) \) holds, so by Jensen's equality, \( x \) must be a constant and all three lengths must be equal. So the area of the largest square (and all squares) is \(100 m^2 \).

Title: Kraft inequality
Q: For any uniquely decodable code \( C(X) \) over the binary alphabet \( \{0, 1\} \), the codeword lengths satisfy:
[\[ ? = ? \]]
If a uniquely decodable code satisfies the Kraft inequality with equality, then it is called a [what?].
A: \[ \sum_{i=1}^{I} 2^{-l_i} \leq 1 \text{, where } I = |A_x| \]; complete code
BackOnlyText: The Kraft inequality might be more accurately referred to as the Kraft-McMillan inequality: Kraft proved that if a set of codeword lengths satisfies the inequality, then a prefix code using these lengths must exist. McMillian (1956) proved that that unique decodeability implies that the inequality holds.
Notation background
A binary symbol code \( C \) for an ensemble \( X \) is a mapping from the range of \( x \), \( A_x = \{a_1, ..., a_n\} \), to \( \{0, 1\}^+ \). \( c(x) \) denotes the codeword corresponding to \( x \) and \( l(x) \) will denote its length, with shorthand \( l_i = l(a_i) \).
The extended code \( C^+ \) is a mapping from \( A_x^+ \) to \( \{0,1\}^+ \) obtained by concatenation:
\[ c^+(x_1x_2...x_N) = c(x_1)c(x_2)...c(x_N) \]
A code \( C(X) \) is said to be uniquely decodable iff, under the extended code \( C^+ \), no two distinct strings have the same encoding. So:
\[ \forall x,y \in A_x^+, x \neq y \implies c^+(x) \neq c^+(y) \]
or equivalently:
\[ \forall x,y \in A_x^+, c^+(x) = c^+(y) \implies x = y \]

Title: Symbol codes
A binary symbol code \( C \) for an ensemble a probability space \( (\Omega, \mathcal{A}_x, \mathcal{P}_x) \) is a mapping from the range of events \( \mathcal{A}_x = \{a_1, ..., a_n\} \), to \( \{0, 1\}^+ \). Let \( x \in \mathcal{A}_x \). \( c(x) \) denotes the codeword corresponding to \( x \) and \( l(x) \) will denote its length, with shorthand \( l_i = l(a_i) \).
The extended code, denoted \( C^+ \), is a mapping from \( \mathcal{A}_x^+ \) to \( \{0,1\}^+ \) obtained by concatenation:
\[ c^+(x_1x_2...x_N) = c(x_1)c(x_2)...c(x_N) \]
A code \( C(X) \) is said to be uniquely decodable if, under the extended code \( C^+ \), no two distinct strings have the same encoding. So:
\[ \forall x,y \in \mathcal{A}_x^+, x \neq y \implies c^+(x) \neq c^+(y) \]
or equivalently:
\[ \forall x,y \in \mathcal{A}_x^+, c^+(x) = c^+(y) \implies x = y \]
A symbol code is a prefix code if no codeword is a prefix of any other codeword. A prefix code is also known as a self-punctuating or instantaneous code, as an encoded string can be decoded from left to right without having to look ahead to subsequent codewords. A prefix code is uniquely decodable.
The expected length \( L(C, X) \) of a symbol code \( C \) for ensemble \( X \) is:
\[ L(C,X) = \sum_{x \in \mathcal{A}_x} P(x)l(x) \]
Alternatively written as:
\[ L(C, X) = \sum_{i=1}^{I} p_il_i \]
Where \( I = |\mathcal{A}_x| \)

Title: Logistic regression LED exercise
FrontDescription: Motivating the logistic and softmax output layers through a great exercise.
Back: The mess:
\[
\begin{aligned}
p(x_1, ..., x_n) &= p(x_1 \vert x_2, ..., x_n)p(x_2, ..., x_n) \\
&= p(x_1 \vert x_2, ..., x_n)p(x_2 \vert x_3, ..., x_n)p(x_3, ..., x_n) \\
&= p(x_n) \prod_{i=1}^{n-1} p(x_i \vert x_{i+1}, ..., x_n)
\end{aligned}
\]
The basic idea is that Bayes's rule can be mutated as follows:
\[
\begin{aligned}
P(s=2|x=x)&= \frac{P(x|s=2)P(s=2)}{\sum_{i \in \{2, 3\}} P(x | s = i)P(s = i) } \\
&= \frac{P(x|s = 2)P(s=2)}{P(x | s = 2)P(s = 2) + P(x | x = 3)P(s = 3) } \\
&= \frac{1+\frac{P(x|s=3)P(s = 3)}{P(x|s=2)}} \\
\end{aligned}
\]
an represent \( P(x = x_1 | s_2) \) as a function of the dot product of two vectors, for example:
Let
\( x_1 = \begin{bmatrix}1 & -1 & -1 & -1 & -1 & -1 & -1 \end{bmatrix} \),
which repesents the LED set with only the 1st LED on and we define the vector
\( s_2 = \begin{bmatrix}1 & -1 & 1 & 1 & 1 & 1 & -1\end{bmatrix} \),
then \( x_1 s_2 \) can be related to the number of correct digits like so:
\( C = correctCount = \frac{x_1 s_2 + 7}{2} \)
[What the hell happend below:]
\[
\begin{aligned}
P(s=2|x=x)&=\frac{P(x|s=2)P(s=2)}{\sum_{i \in \{2, 3\}} P(x | s = i)P(s = i) } \\
&=\frac | s = 2)P(s=2)}{P(x | s = 2)P(s = 2) + P(x | x = 3)P(s = 3) } \\
=&\frac1+\frac{P(x|s=3)P(s = 3)}{P(x|s=2)})} \\
\end{aligned}
\]
Thus we see how the probability can be molded into an exponential form, and how Bayes's rule allows for the \( \frac{1}{1 + e^{f(x)}} \) form. With more than two classes, it's easier to express the probability without dividing the numerator and denomitator by the numerator, so we are left with the softmax form as show in the question. Thus, it is easy to see how the softmax and the logistic output units are essentially the same thing: relative probabilities when expresses as exponentials.
A generality
If a random variable has two possible values and you can express the event probabilities as \( \alpha^{-x_1} \) and \( \alpha^{-x_2} \), then you can arrive at an exponential formulation like so:
\[ \frac{\alpha^{-x_1}}{\alpha^{-x_1} + \alpha^{-x_2}} = \frac{1}{1 + \alpha^{-(x_2 - x_1)}} = \frac{1}{1 + e^{-\beta x}} \] Where \(x = x_2 - x_1 \).
Source: MacKay

Title: The urns
Q: Problem statement
There are 11 urns labeled by \( u \in \{0, 1, 2, ... 10\} \), each containing ten balls. Urn \( u \) contains \( u \) black balls and \( 10 -u \) white balls. Fred selects an urn \( u \) uniformly at random and draws \( N \) times with replacement from that urn, obtaining \( n_B \) blacks and \( N-n_B \) whites. Fred's friend, Bill, looks on. If after \( N=10 \) draws \( n_B = 3 \) blacks have been drawn, what is the probability that the urn Fred is using is urn \( u \) from Bill's point of view?
Solution
Firstly, we know how to express the probability distribution of the number of blacks given the urn and the total ball count:
\[ P(n_B | u, N) = \left(\begin{array}{c}N\\ n_B\end{array}\right) f_u^{n_B}(1-f_u)^{N-n_B} \quad \text{(1)}\]
Where we define [\( f_u := ? \)].
Adding the \( u \) dimension creates the joint probability distribution of the random variables \( u \) and \( n_b \), \( P(u, n_B | N) \). It can be written as:
[\[ P(u, n_B | N) = P(?) P(u)\]]
Notices how \( P(u) \) appears, the probability that Fred selects a given urn, which is uniform at \( \frac{1}{11} \) as per the question.
From here, we need Bayes Theorem, which is:
[\[ P(A|B) = \frac{P(A , B)}{P(B)} = \frac{?}{P(B)} \]]
From the joint probability of \( u \) and \( n_B \) we can obtain the conditional distribution of \( u \) given \( n_B \) using Bayes Theorem:
\[ \begin{align*} P(u|n_B, N) &= \frac{P(u, n_B |N)}{P(n_B|N)} \\ &= \frac{P(n_B | u, N)P(u)}{P(n_B|N)} \end{align*} \]
We so far know 2 of the 3 expressions in that quotient. The third, the denominator, \( P(n_B|N) \), is the marginal probability of \( n_B \) which we can obtain using the sum rule:
\[ P(n_B | N) = \sum_u P(u, n_B | N) = \sum_u P(u)P(n_B | u, N) \]
So the conditional probability of \( u \) given \( n_B \) is:
\[ \begin{align*} P(u|n_B, N) &= \frac{P(n_B | u, N) P(u)}{\sum_{u'} P(n_B | u', N)P(u')} \\ &= \frac{P(n_B | u, N) P(u)}{P(n_B| N)} \\ &= \frac{1}{P(n_B|N)} \frac{1}{11} \left(\begin{array}{c}N\\ n_B\end{array}\right) f_u^{n_B}(1-f_u)^{N-n_B} \\ \end{align*} \]
We must calculate and sum all probabilities of the form (1) above, then p the sum by the probabilities from (1) for the given urn.
By the way, the sum for when \( n_B \) is 3 is: \( P(n_B = 3|N=10) = 0.083 \).
Todo: compare this to the bent coin.
A: \( f_u := \frac{u}{10} \); \[ P(u, n_B | N) = P(n_B | u, N) P(u) \]; \[ P(A|B) = \frac{P(A , B)}{P(B)} = \frac{P(B|A)P(A)}{P(B)} \]
Source: David MacKay

Title: How many parameters are needed to describe this distribution?
Text: Consider a distribution consisting of three binary variables which admit the factorisation: \( p(a, b, c) = p(a \mid b)p(b \mid c)p(c) \)
How many parameters are needed to specify distributions of this form?
Note that this is different to the general case where all variables might be dependent: \( p(a, b, c) = p(a \mid b, c)p(b \mid c)p(c) \)
Back: In the case where we have no information about the variable dependency, we need to specify 8-1=7 parameters to define the distribution. There are \( 2^3 = 8 \) possible outcomes, but as the probabilities add to 1, we only need 7 parameters to fully define the distribution.
In the given case, b's value is sufficient to know the distribution of a. So some simplification is possible. A way to think about the situation is to consider 5 coins: \( c, {b_1, b_2}, {a_1, a_2} \). We will flip 3 coins starting with coin \( c \). The outcome of flipping \( c \) determines with coin \( b \) from \( {b_1, b_2} \) will be flipped. The outcome of flipping coin \( b \) determines which coin \( a \) from \( {a_1, a_2} \). As the coins can be represented as bernoilli random variables, they can be described with a single parameter representing the probability of landing heads. As there are 5 coins, we need 5 parameters to fully describe the distribution of the whole system.
Drawing a graph is another way to model this problem.
Source: Bayesian Reasoning and Machine Learning
David Barber
Q 1.6

Title: Belief networks
Q: A belief network (called a Bayesian network by Koller) is a grapical model that represents a distribution of the form
\[ p(x_1, ..., x_D) = \prod_{i=1}^{D} p(x_i \vert pa(x_i)) \\
\text{where } pa(x_i) \text{ represents the parental variables of variable } x_i\]
Parental variables is just a term for the variables that appear as conditional variables for a given variable.
A belief network represents a distribution as a directed graph where the \( i \)^th node corresponds to the factor [...], with directed connections from all [...] nodes to the \( i \)^th node.
According to the rules above, a distribution \( p(x_1, x_2, x_3, x_4) \), one with no independence statements, can be modelled with a cascade graph like so:
A: \( p(x_i \vert pa(x_i)) \); \( pa(x_i) \)
BackOnlyText: Derivation
Without loss of generality, using Bayes' rule the distribution \( p(x_1, ..., x_n) \) can be represented as:
\[
\begin{aligned}
p(x_1, ..., x_n) &= p(x_1 \vert x_2, ..., x_n)p(x_2, ..., x_n) \\
&= p(x_1 \vert x_2, ..., x_n)p(x_2 \vert x_3, ..., x_n)p(x_3, ..., x_n) \\
&= p(x_n) \prod_{i=1}^{n-1} p(x_i \vert x_{i+1}, ..., x_n)
\end{aligned}
\]
More accurately, a belief network represents a set of distributions that have the same dependency relationships, not just a single distribution with speficied probabilities.
Example: Deleting any connection represents the existance of some independence. For example:
Source: Bayesian Reasoning and Machine Learning
David Barber
p38-39

Title: Belief networks: independence
It's not immediately obvious how to interpret the conditional relationships represented by a belief network. For example, consider the networks below.
Network(s) b, c and d represent the distribution:
\[\begin{aligned}
p(x_1, x_2, x_3) &= p(x_1 \vert x_3)p(x_2 \vert x_3)p(x_3) \\
&= p(x_2 \vert x_3)p(x_3 \vert x_1)p(x_1) \\
&= p(x_1 \vert x_3)p(x_3 \vert x_2)p(x_2)
\end{aligned} \]
Network(s) a represent the distribution:
\[
p(x_1, x_2, x_3) = p(x_3 \vert x_1, x_2)p(x_1)p(x_2)
\]
Next, consider conditional independence.
- In a), \( x \) and \( y \) are unconditionally dependent, and conditioned on \( z \) they are independent. Knowing either gives information on the distribution of \( z \), which in turn informs of the others distribution.. \( p(x, y \vert z) = p(x \vert z)p(y \vert z) \)
- In b), \( x \) and \( y \) are unconditionally dependent, and conditioned on \( z \) they are independent. \( p(x, y \vert z) \varpropto p(z \vert x)p(x)p(y \vert z) \)
- In c), \( x \) and \( y \) are unconditionally independent, and conditioned on \( z \) they are dependent. \( p(x, y \vert z) \varpropto p(z \vert x, y)p(x)p(y) \)
- Id d), \( x \) and \( y \) are unconditionally independent, and conditioned on \( z \) or \( w \), are dependent. See book for full equation.
BackOnlyText: Independent but conditionally dependent
Considering a graph like \( A \rightarrow B \leftarrow C \), we have \( A \) and \( C \) being (unconditionally) independent. However, conditioning on \( B \) makes them dependent. Intuitively, whilst we believe the root causes are independent, given the value of the observation, we learn something about the state of both the causes. Another way of viewing this is: the outcome \( B \) requires knowledge of both \( A \) and \( C \) before we have an independent distribution. Thus, if we know \( B \), then the dependecy of \( B \) on \( C \) will change depending on the value of \( A \). Thus, if \( B \) is known, \( C \) is dependent on \( A \).
Tips
So far, the most intuitive way I have found of converting these diagrams into a mental model is to view the arrows into a node A as saying: knowing the inputs to A is sufficient to fix the shape of A's distribution, and all other quantities can change without affecting A's distribution.
When reading the graphs, have the following rules in mind:
- source exists in the conditional of target when expressing \( p(x_1, ..., x_n) \)
- When expressing \( p(x_1, ..., x_n) \) as \( p(x_t \vert dependencies)p(dependencies) \), it can be done as \( p(x_t \vert inputs, outputs)p( inputs, outputs)p(other) \). Where \( p(other) \) accounts for any other connected components in the full graph. (I'm not sure if I have this right).
Source: Bayesian Reasoning and Machine Learning
David Barber
p40-41

Title: Belief networks: independence examples
1 a) Marginalizing over \( C \)  makes \( A \) and \( B \) independent. In other words, \( A \) and \( B \) are (unconditionally) independent \( p(A,B) = p(A)p(B) \). In the absence of any information about the effect of \( C \) we retain this belief.

1 b) Conditioning on \( C \) makes A and B (graphically) dependent \( p(A, B \vert C) \ne p(A \vert C)p(B \vert C) \). Although the causes are a priori independent, knowing the effect \( C \) can tell us something about how the causes colluded to bring about the effect observed.

2. Conditioning on \(  D \), a descendent of a collider \( C \) makes \( A \) and \( B \)  (graphically) dependent. \( p(A, B \vert D) \ne p(A \vert D)p(B \vert D) \)

3 a) \( p(A, B, C) = \) \(p(A \vert C)p(B \vert C)p(C) \). Here there is a 'cause' \( C \) and independent 'effects' \( A \) and \( B \).
3 b) Marginalizing over \( C \) makes \( A \) and \( B \) (graphically) dependent. \( p(A, B) \ne p(A)p(B) \). Although we don't know the 'cause', the 'effects' will nevertheless be dependent.

3 c) Conditioning on \( C \) makes \( A \) and \( B \)  independent. \( p(A, B \vert C) = p(A \vert C)p(B \vert C) \). If you know the 'cause' \( C \), you know everything about how each effect occurs, independent of the other effect. This is also true for reversing the arrow from \( A \) to \( C \)—in this case, \( A \) would 'cause' \( C \) and then \( C \) would 'cause' \( B \). Conditioning on \( C \) blocks the ability of \( A \) to influence \( B \).

Finally, these following graphs all express the same conditional independence assumptions.
Source: Bayesian Reasoning and Machine Learning
David Barber
p42-43

Title: Gaussian distribution
Q: The Gaussian distribution with mean of 0 and standard deviation \( \sigma \) has the form:
\[ \phi(x) = \frac{1}{[...]}e^{-\frac{x^2}{[...]}} \]
A: \sqrt{2\pi}\sigma; 2\sigma^2
BackOnlyText: Imagine a distribution that describes errors in measurements of some unknown quantity. Let's say we make the following assumptions:
1. Small errors are more likely than large errors.
2. For any real, \( v \), the likilihood of errors of magnitude \( v \) and \( -v \) are equal.
3. In the presence of several measurements of some unknown quantity, the most likely value of the quantity being measured is their average.
On the basis of these assumptions, we can conclude:
1. The distribution has a maximum at zero and decreases with increasing distance from zero.
2. The distribution is symmetric (around zero).
3. The maximum likelihood estimate (MLE) of the unknown quantity given some measurements is the mean of the measurements.
Laplace later does away with the 3^rd assumption by using a different assumption: assume that each individual error is the aggregate of a large number of "elementary" errors.
From these assumptions, it can be shown that the distribution obeys the following differential equation:
\[ \frac{\phi'(x)}{\phi(x)} = kx \text{ for some real k} \]
Integrating with respect to x produces:
\[ ln(\phi(x)) = \frac{k}{2}x^2 + c \text{, so } \\
\phi(x) = Ae^{\frac{kx^2}{2}} \]
Assumption 1) imposes that \( k \) must be negative. So we combine with 2 and set \( \frac{k}{2} =  -h^2 \).
The probability distribution must sum to 1. Knowing that:
\[ \int_{\infty}^{\infty}e^{-h^2x^2}dx = \frac{\sqrt{\pi}}{h} \]
It follows that:
\[ \phi(x) = \frac{h}{\sqrt{\pi}}e^{-h^2x^2} \]
Gauss thought of \( h \) as the "precision of the measurement process". We recognize this as the bell curve determined by \( \mu = 0 \) and \( \sigma = \frac{1}{\sqrt{2}h} \):
\[ \phi(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{x^2}{2\sigma^2}} \]

Title: Covariance matrix
Q: Let \( X \) and \( Y \) be two random variables. The covariance between \( X \) and \( Y \) is defined as:
\[\begin{aligned}
Cov[X,Y] &:= E[(X-E[X])(Y-E[Y])] \\
&= [...]
\end{aligned} \]
Let the vector \( Z \) be defined like so: \( Z := \begin{bmatrix} X \\ Y\end{bmatrix} \). Thus, \( Z \) is a vector of random variables.
The covariance matrix for \( Z \) is defined as:
\[ \begin{aligned} Cov[Z] &:= E[(Z - E[Z])(Z - E[Z])^T] \\
&= [...] \\
\end{aligned} \]
Where the expectation is an elementwise operation. The covariance matrix is a result of a matrix multiplication of two vector-like matrices, which produces a 2x2 matrix. (Yes, it is valid!).
A: E[XY] - E[X]E[Y]; \begin{bmatrix} Var(X) & Cov(X, Y) \\ Cov(X, Y) & Var(Y) \end{bmatrix}
BackOnlyText: Matrix interpretation
An intepretation of such a 2x1*1x2 matrix multiplication is:
\[ \begin{aligned} \begin{bmatrix} A \\ B \end{bmatrix} \begin{bmatrix}C & D\end{bmatrix} &= \begin{bmatrix}AC & AD \\ BC & BC \end{bmatrix} \\
&= \begin{bmatrix}C\begin{pmatrix}A \\ B\end{pmatrix} & D\begin{pmatrix}A \\ B \end{pmatrix} \end{bmatrix}
\end{aligned} \]
The first matrix can be considered a transformation matrix which transforms a single dimension into 2 dimensions. \( A \) is the factor by which the input scalar is multiplied by to produce the first output dimension; \( B \) is the same quantity for the second output dimension. The matrix \( \begin{bmatrix} C & D\end{bmatrix} \) can be considered a list of two separate scalars that will be transformed separately.
For the case of \( Z Z^T \), if \( Z \) has \( D \) dimensions, then the output is D vectors combined horizontally into a matrix, where each vector is the original \( Z \) multiplied by one of it's components.
For the 2 dimensional covariance matrix we have:
\[ \begin{aligned}
Cov[Z] &= E[ (Z - E[Z])(Z - E[Z])^T] \\
&= E\left[ \begin{bmatrix}X - \mu_X \\ Y - \mu_Y \end{bmatrix} \begin{bmatrix}X-\mu_X & Y-\mu_Y\end{bmatrix} \right] \\
&= E[\begin{bmatrix}(X - \mu_X) \begin{pmatrix} X - \mu_X \\ Y - \mu_Y\end{pmatrix} & (Y - \mu_Y) \begin{pmatrix} X - \mu_X \\ Y - \mu_Y\end{pmatrix} \end{bmatrix} ] \\
&= \begin{bmatrix} Cov(X, X) & Cov(Y, X) \\ Cov(X, Y) & Cov(Y, Y) \end{bmatrix} \\
&= \begin{bmatrix} Var(X) & Cov(X, Y) \\ Cov(X, Y) & Var(Y) \end{bmatrix}
\end{aligned} \]
The covariance matrix is symmetric, like all matrixes of the form \( X X^T \). Its diagonal is the variances of each random variable.
Random variable interpretation
Covariance is the expected value of the random variable \( Z = (X - \bar{X})(Y - \bar{Y}) \). Imagine the probability mass function of \( X  \) and \( Y \), then \( X - \bar{X} \) and \( Y - \bar{Y} \), then the 2 dimensional \( (X - \bar{X}, Y- \bar{Y}) \), then finally the 1 dimensional \( Z \). The covariance is a single value representing the expectation (product sum) of the value-probabilities of \( Z \).

Title: Multivariate Gaussian distribution
Q: This card derives the general multivariate normal distribution from the standard multivariate normal distribution.
Standard multivariate Gaussian/normal distribution
Let \( (\Omega, \mathrm{F}, \mathbb{P}) \) be a probability space. Let \( X : \Omega \to \mathbb{R}^K \) be a continuous random vector. \( X \) is said to have a standard multivariate normal distribution iff its joint probability density function is:
[\[ f_X(x) = \quad ? \]]
As a vector of random variables
\( X \) can be considered to be a vector of independent random variables, each having a standard normal distribution. The proof of this formulation on the reverse side.
General multivariate
The general multivariate normal distribution is best understood as being the distribution that results from applying a linear transformation to a random variable having a multivariate standard normal distribution.
General multivariate normal distribution
Let \( (\Omega, \mathrm{F}, \mathbb{P}) \) be a probability space, and let \( Z : \Omega \to \mathrm{R}^K \) be a random vector with a multivariate standard normal distribution. Then let \( X = \mu + \Sigma Z \) be another random vector. \( X \) has a distribution \( f_X : \mathbb{R}^K \to \mathbb{R} \) which is a transformed version of \( Z \)'s distribution, \( f_Z : \mathbb{R}^K \to \mathbb{R} \):
[\[ \begin{alignat*}{3}f_X(x) &= \frac{1}{\text{rescaling factor} } \; &&f_z(\text{z in terms of x}) \\
&= \frac{1}{\text{what?} } &&f_z(\Sigma^{-1}(x - \mu)) \\ &= \frac{1}{\text{what?} } &&(\frac{1}{\sqrt{2\pi} })^K e^{\text{what?} } \\ \end{alignat*}\]]
A: \[ f_X(x) = (\frac{1}{\sqrt{2\pi} })^K e^{-\frac{ x^\mathsf{T}x }{2} } \]; \[ \begin{alignat*}{3}f_X(x) &= \frac{1}{\text{rescaling factor} } \; &&f_z(\text{z in terms of x}) \\
&= \frac{1}{|\operatorname{det}(\Sigma )|} &&f_z(\Sigma^{-1}(x - \mu)) \\ &= \frac{1}{|\operatorname{det}(\Sigma )|} &&(\frac{1}{\sqrt{2\pi} })^K e^{\textstyle \frac{(\Sigma^{-1}(x - \mu))^\mathsf{T}(\Sigma^{-1}(x - \mu))}{2} } \\ \end{alignat*}\]
BackOnlyText: Standard multivariate normal as a vector of independent random variables. Proof.
Proof that the above probability density function represents \( K \) independent standard normal random variables. For clarity, only the case when \( K = 3 \) will be highlighted:
\[ \begin{aligned} f_Z(z) &= \frac{1}{   (2\pi)^{ \frac{3}{2} }   } e^{-\frac{z^Tz}{2}} \\
&= \frac{1}{    (2\pi)^{\frac{1}{2}}    } \frac{1}{(2\pi)^{\frac{1}{2}}} \frac{1}{(2\pi)^{\frac{1}{2}}} e^{-\frac{z^Tz}{2}} \\
&= \frac{1}{(2\pi)^{\frac{1}{2}}} \frac{1}{(2\pi)^{\frac{1}{2}}} \frac{1}{(2\pi)^{\frac{1}{2}}} e^{-\frac{z_1^2 + z_2^2 + z_3^3}{2}} \\
&= \frac{1}{\sqrt{2\pi}} \frac{1}{\sqrt{2\pi}} \frac{1}{\sqrt{2\pi}} e^{-\frac{z_1^2}{2}} e^{-\frac{z_2^2}{2}} e^{-\frac{z_3^2}{2}} \\
&= \frac{1}{\sqrt{2\pi}} e^{-\frac{z_1^2}{2}} \frac{1}{\sqrt{2\pi}} e^{-\frac{z_2^2}{2}} \frac{1}{\sqrt{2\pi}} e^{-\frac{z_3^2}{2}} \\&= f(z_1) f(z_2) f(z_3) \end{aligned}\]
Thus, the propability distribution for \( Z \) represents 3 independent random variables having a individual distribution of \( \frac{1}{\sqrt{2\pi}}e^{-\frac{z_i^2}{2}} \) which is the standard normal distribution for a single random variable.
Elementwise conceptualization
The quantity \( [X - \mu] \Sigma^{-1} [X-\mu] \) can be thought of as a component wise operation, sum(\( \frac{[X - \mu ]^2}{\sigma^2} \)), where \( \sigma \) is the column vector of standard deviations. Another alternative is to imagine the component wise methods that would be called in a linear algebra/DL library: accumulate(mult(invert(pow(\( \sigma \), 2)), pow(\( X - \mu \)), 2))).
\(V = \Sigma^{\mathsf{T}} \Sigma \) form. Proof.
The Statlect formulation simplifies the expression. Copy-pasted here:
Dispelling the mystery of the co-variance matrix
Here is a screenshot of some notes on the perspective of a multivariate Gaussian random variable being a composition of two standard normal variables. It tries to dispell some of the mystery about why the co-variance matrix comes up the way it does.
Source: http://cs229.stanford.edu/section/gaussians.pdf
https://www.statlect.com/probability-distributions/multivariate-normal-distribution

Title: The two types of compressors
FrontDescription: There are only two ways in which a purported compressor can compress files. Each makes a trade-off.
Back: Lossy compression
A lossy compression compresses some (possibly all) files, but it maps some files to the same encoding. When decompression if an ambiguous files is encountered, there is no way to know for sure which of the multiple files having that encoding was the original file.
Lossless compression
A lossless compressor maps all files to different encodings; if it shortens some files, it necessarily makes others longer. A good compressor is one where the probability of a file is lengthened is small, while the probability that a file is shortened is large.

Title: Richard–Berry paradox
Q: A paradox highlighting an issue with using description length as a measure of complexity.
Define a specific natural number as "the least natural number that [...]".
A: cannot be described in fewer than 20 words
Back only: If such a number does exist, then we have just described it in 13 words, contradicting its definition. If such a number doesn't exist, then all natural numbers can be described in fewer than 20 words.
Thus, there is a need for the meaning of 'description' to be inspected closely.
Source: M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and ItsApplications.
Chapter 1
p 1

Title: Accuracy, precision, recall
\[ \begin{aligned} \text{accuracy} &= \frac{TP + TN}{TP + TN + FP + FN} \\ \text{precision} &= \frac{TP}{TP + FP} \\ \text{recall} &= \frac{TP}{TP + FN} \\ \end{aligned} \]
Formulated in words
accuracy = \( \frac{ \text{correct} }{ \text{incorrect} } \)
precision = given a positive result, how likely is the true state to be positive; the reliability of a positive result.
recall = how many of the true positives are recoreded as positive. Have we missed many positives?
Pathalogical and benign examples
Are false positives dangerous? Are false negatives dangerous? Poor precision affords many false positives. Poor recall affords many false negatives. If the true/false meaning of any test is reversed, false positives become false negatives and vice versa.
- Poor precision is pathalogical: COVID19 testing where positive represents being free of the virus.
- Poor precision is benign: COVID19 testing, where a positive represents having the virus.
- Poor recall is pathalogical: COVID19 testing, where a positive represents having the virus.
- Poor recall is benign: COVID19 testing where positive represents being free of the virus.
Source: https://towardsdatascience.com/accuracy-precision-recall-or-f1-331fb37c5cb9
Siggraph slides from Andrew Glassner: https://siggraph2020.hubb.me/schedule-builder/sessions/714439

Title: Latent variables in autoencoders
Q: The word 'latent' in 'latent values', 'latent variables' or 'latent vector' when describing the bottleneck of an autoencoder tries to communicate the fact that [...].
A: these values were in the data all along, we just didn't know how to find them
Source: Andrew Glassner section of Siggraph 2020's "Making Machine Learning Work: from Ideas to Production Tools"

Title: Auto-encoder (VAE?) [stub]
Q: In Karol Gregor's talk [6], e is described as [...] that limits the information passed between the encoder and decoder layers (otherwise μ,Σ, being made up of real numbers, would carry an infinite number of bits). Somehow this prevents similar z being decoded into wildly different images, but I don't fully understand the info-theory interpretation quite yet.
So, the second half of the network will be told to draw "some sort of 6, with certain qualities (x,y,z) that are chosen randomly by e?" I'm not sure I understand.
My distribution collapse perspective on e
If the sampling function \( g(\phi, x, \varepsilon) \) was a normal distribution of some sort, without the randomness, the network could learn to set the variance to zero and propagate whatever value the mean is exactly. This might cause the network to take shortcuts and not learn latent variables. So, the e term gives a restriction to the encoder: you must encode in such a way that can still communicate sufficient information despite your output being purturbed in a very specific way. For the random normal case, the encoded has control of this purturbation by controlling \( \sigma \), however, the encoded is penalized as \( \sigma \) gets further from the value 1.0 (to match a standard normal). I wonder what would happen if you didn't let the encoder produce \( \sigma \) at all and had it hard-coded to 1.0?
A: "added noise"
Source: https://blog.evjang.com/2016/06/understanding-and-implementing.html

Title: Color perception
FrontDescription: A nice image of color preception
Source: James Ferwerda, Siggraph 2020

Title: Correlated color temperature (CCT)
Q: Correlated color temperature is a description of light source color in terms of [...] that has the same perceived color.
A: the temperature of a blackbody radiator
Back only: Blackbody radiators are special in that their temperature is sufficient to describe an exact spectrum according to Plank's law.
Source: James Ferwerda, Siggraph 2020

Title: Standard illuminants
Standard illuminants, defined by CIE are common physical illuminants for which CIE has recorded their spectral emission curves.
Some examples of standard illuminants are:
- C
- D50
- D65
- A
- F2
- L
Source: James Ferwerda, Siggraph 2020

Title: Characterizing a surface's "color" properties
Q: The [some fundamental property] of a surface determines what light leaves a surface when illuminated by a given light source. Opaque surfaces can be characterized by a [something that describes the property].
On the back side, there in a figure showing the measurement process. Can you remember what it looks like?
A: reflectance; spectral reflectance function
Source: James Ferwerda, Siggraph 2020

Title: Random number generation in Numpy
Q: TODO: [...]
A: finish

Title: Binomial distribution. A perspective.
Q: If a random variable \( X \) has a binomial distribution with parameters \( n \) and \( p \) then \( X \) is a sum of [# something something] random variables each having a Bernoulli distribution with parameter [#].
A: \( n \) jointly independent; \( p \)
Source: https://www.statlect.com/probability-distributions/binomial-distribution

Title: Chi-squared distribution
Q: David MacKay motivates (in passing) the chi-squared distribution through exercise 2.5.
The solution is on the reverse side. [dummy cloze.]
A: Dummy cloze
BackOnlyText: Recognize that \( z \) is a function of the of a random variable \( n_B \) which is in turn a sum of independent Bernouilli random variables. \( z \) can be thought of as trying to measure how many standard devations away from the mean \( n_B \) is.
The official chi-squared distribution is specific to the case where \( n_B \) is normally distributed with some mean and variance.
Source: http://www.inference.org.uk/itprnn/book.pdf

Title: Covariance matrix and estimation
Q: Yet another card on covariance and covariance matrices.
There is a good card on covariance, which I recap here:
Covariance is a real that gives some sense of how much two variables are linearly related to each other, as well as the scale of these variables. Covariance is a function of a probability space and two random variables. Let \( (\Omega, \mathrm{F}, \mathbb{P}) \) be a discrete probability space let \( X: \Omega \to S_x \) and \( Y : \Omega \to S_y \), be two random variables, where \( S_x\) and \( S_y \) are finite subsets of \( \mathbb{R} \). Then the covariance of \( X \) and \( Y \) is:
[\[ \mathrm{Cov}[X, Y] = \sum_{?} ? (? - \mathrm{E}[X])(? - \mathrm{E}[Y])) \]]
If instead the probability space is continuous, we can still define covariance, we will just employ an integral for the expectation.
The essense of this definition
This definition describes covariance as a function of two random variables, \( X : \Omega \to \mathbb{R} \) and \( Y : \Omega \to \mathbb{R} \). Optionally, this can be expressed as a function of a 2D random variable \( \vb{X} : \Omega \to \mathbb{R}^2 \).
Another perspective is that covariance is the expectation of the random variable \( Z : \Omega \to \mathbb{R} \), \( Z = (X-\mathrm{E}[X])(Y - \mathrm{E}[Y]) \).
Covariance matrix
Just a small step from the previous discussion brings us to the matrix product:
\[ \begin{bmatrix}X-\mathrm{E}[X] \\ Y-\mathrm{E}[Y] \end{bmatrix} \begin{bmatrix}X-\mathrm{E}[X] & Y-\mathrm{E}[Y] \end{bmatrix} = \begin{bmatrix}(X-\mathrm{E}[X])^2 & (X-\mathrm{E}[X])(Y - \mathrm{E}[Y]) \\ (X-\mathrm{E}[X])(Y - \mathrm{E}[Y]) & (Y -\mathrm{E}[Y])^2 \end{bmatrix} \]
The elements of these vectors and matrices are functions/random variables. If we take the elementwise expectation of the matrix above, we arrive at the covariance matrix:
\[ \begin{bmatrix}\mathrm{E}[(X-\mathrm{E}[X])^2] & \mathrm{E}[(X-\mathrm{E}[X])(Y - \mathrm{E}[Y])] \\ \mathrm{E}[(X-\mathrm{E}[X])(Y - \mathrm{E}[Y])] & \mathrm{E}[(Y -\mathrm{E}[Y])^2] \end{bmatrix} = \begin{bmatrix} \mathrm{Var}[X] & \mathrm{Cov}[X,Y] \\ \mathrm{Cov}[X,Y] & \mathrm{Var}[Y] \end{bmatrix} \]
This is a matrix containing 4 real numbers; each expectations over random variables defined on the sample space.
If we make the synatic change to use a multivariate random variable, where \( X \) and \(Y \) are now the vector components \(\vb{x}_1\) and \( \vb{x}_2 \), we arrive at the notation:
\[ \text{Covariance matrix} = \mathrm{E} \left[ (\vb{x} - \overline{\vb{x}})(\vb{x} - \overline{\vb{x}})^T \right] \]
where the expectation of a matrix is defined to be an elementwise application of the 1D expectation operation. It is worth mentioning that we are invoking the definitions of random vectors and matricies, and the expectation of these. These are indeed commonly defined notions, for example, Statlet defines random vectors and random matrices, and also covers them when defining expectation.
Essence of covariance matrix
The covariance matrix is an expectation applied to a matrix of random variables.
If we zoom, we can view the covariance matrix as being the output of an operation which takes in a random vector (function) on a probability space, \(( \Omega, \mathrm{F}, \mathbb{P}) \), and producing a matrix of reals. The operation has an intermediate output taking the form of a random matrix (random vector → random matrix → element-wise expectation). In this sense, the operation is comparable to the expecation or variance operation, it just has a higher dimensional output.
If we were to determine the values (reals) of the covariance matrix, we would need to know \( \mathbb{P} \) and the random vector involved.
Data covariance matrix
When one has some data, it is often said that one can compute the covariance matrix of the data.
There is a little bit of ambiguity as to the exact calculation to run ( \( \frac{1}{n} \) or \( \frac{1}{n-1} \) factor?), and a related ambiguity as to what the matrix represents (an unbiased estimator of the covariance matrix, or a MLE of some model parameter?).
The 1-dimensional data case (which doesn't have any concept of covariance) can motivate the 2+-dimensional case.
1-dimension case
Given some 1D data, we can consider the data to be samples of a random variable \( X : \Omega \to \mathbb{R} \). The best way to conceptualize \( n \) samples is that it is \( n \) draw from sample space \( \Omega \), or 1 draw from \( \Omega^n \), and then the random variable \( X : \Omega \to \mathbb{R} \) is applied to each draw, so that we get \( n \) possibly different values \( X_1, X_2, ..., X_n \).
If the samples are reals, then the random variable \( Z : \mathbb{R}^n \to \mathbb{R} \) defined by \( Z = \frac{1}{n} \sum_{i=1}^{n} X_i \), which redistributes the n-dimensional distribution back to 1D, has an expected value \( \mathrm{E}[Z] \) which is equal to \( \mathrm{E}[X] \), where \( X : \Omega \to \mathbb{R} \), the 1D random variable. In this way, \( Z \) is a non-biased estimator for \( \mathrm{E}[X] \). In this sense, we are estimating the value of the expectation operator applied to the random variable \( X \); we don't need to know anything about the nature of the distribution created by \( X \).
Similarly, the random variable \( W = \frac{1}{n - 1}(X_1 - \mathrm{E}[X])(X_2 - \mathrm{E}[X])...(X_n - \mathrm{E}[X]) \) is an unbiased estimate for the expectation operator applied to the random variable \( (X - \mathrm{E}[X])^2 \) (i.e. the variance operator applied to \( X \)).
The case below is simply the same idea applied to data which itself has more than 1 dimension.
d-dimension case
If each sample is not 1 but \( d \) dimensions, then we must consider a random vector \( X : \Omega \to \mathbb{R}^d \). \( n \) samples of this can be represented by a vector of random vectors: \( n \)-dimensional vector of \( d \)-dimensional vector valued random variables. Like above, we may consider composing new random vectors which project back to \( \mathbb{R} \) and which have an expectation equal to something interesting. For example, we can create \( d \) different random variables which average a single component of the data across all samples: \( Z_j : \mathbb{R}^n \times \mathbb{R}^d \to \mathbb{R}\) defined by \( Z_j(X) = \sum_{i=1}^{n} W_{ji} \), if we assume that \( W \) is a matrix that collects together the random vectors \( X_1, ... X_n \) as columns (data expands horizontally). These random variables have an expectation equal to the mean of the marginalized \( j \) component of the random vector \( X \).
We can also try create estimators for the variance of each component of \( X \) and for the covariance between different components. What is nice is that the factor \( \frac{1}{n-1} \) that we would expect to appear in the estimator of a single 1D component–this factor is also required for estimating covariance between components, for conceptually the same reason.
Matrix calculations
If we have a finite list of \( n \) \( d \)-dimensional data points, we can package them together into a matrix \( \vb{X} \), with each of the \( n \) data points being a \( d \)-element column of the matrix.
\[ \vb{x} = \begin{bmatrix} | & | & | & ... & | \\ x_1 & x_2 & x_3 & ... & x_n \\ | & | & | & ... & | \\ \end{bmatrix} \]
Note on matrix layout
The above data-as-column layout is useful if we wish to consider \( \vb{x'} = \vb{Mx} \) as a transformation matrix \( \vb{M} \) being applied to the data vectors in \( \vb{x} \). If instead we have rows of \( \vb{x} \) representing data points, then \( \vb{xM} \to \vb{x'} \) is a better representation of the transformation operation.
Covariance estimator
From the data we can calculate a sample covariance matrix \( \vb{S} \), defined as:
\[ \vb{S} = \frac{1}{n-1} \sum_{i=1}^{n}(\vb{x_i} - \overline{\vb{x}})(\vb{x_i} - \overline{\vb{x}})^T \]
Where \( \overline{\vb{x}} \) is the data mean:
\[ \overline{\vb{x}} = \frac{1}{n} \sum_{i=1}^{n} \vb{x_i} \]
Sometimes, the data mean is zero, \( \overline{\vb{x}} = 0 \). An we have:
\[ \vb{S} = \frac{1}{n-1} \sum_{i=1}^{n}\vb{x_i} \vb{x_i}^T \]
MLE for normal random variable
If you know that the random variable is a multivariate normal random variable, and you wish to estimate the model parameter \( \Sigma \), then it turns out that the MLE for this is:
\[ \vb{S} = \frac{1}{n} \sum_{i=1}^{n}(\vb{x_i} - \overline{\vb{x}})(\vb{x_i} - \overline{\vb{x}})^T \]
where you can see we have the fraction \( \frac{1}{n} \). Thus, we have a very slight difference between the calculation for finding two conceptually separate quantities:
- a non-biased estimation for the multidimensional random variable's covariance matrix (for any arbitrary random variable)
- the most likely parameterization for a multivariate normal variable which generates the observed samples
A: \[ \mathrm{Cov}[X, Y] = \sum_{\omega \in \Omega} p(\omega) (X(\omega) - \mathrm{E}[X])(Y(\omega) - \mathrm{E}[Y])) \]
BackOnlyText: Important distinction: random vector vs. vector of random variables
Random vector
With a sample space \( \Omega = [0, 1] \), the elements \( X_i \) of a random vector \( X : \Omega \to \mathbb{R}^d \) are each a function \( X_i : \Omega \to \mathbb{R} \) from the sample space. This random vector can be used to represent \( d \)-dimensional data.
Vector of random variables
When we wish to represent \( n \) samples, we are instead dealing with a \( n \)-dimensional sample space \( \Omega = [0, 1]^n \), and a vector of random variables \( [X_1, X_2, X_3,..] \) where each random variable \( X_i : \Omega \to \mathbb{R} \) maps from one of the components of \( \Omega \). These random variables in effect come from different sample spaces. If the samples themselves are \( d \)-dimensional, then the \( n \) samples takes the form of a matrix, or a vector of vector valued random variables.
More on estimator vs multivariate MLE
The wikipedia page has a nice section:
Source: https://en.wikipedia.org/wiki/Estimation_of_covariance_matrices

Title: ELBO via Jensen
FrontDescription: Process
We are interested in evaluating \( \operatorname{P}_{X} \) for some value. Below we consider \( \operatorname{P}_X(x_4) \). If we know the dynamics of \( X \) with respect to some other variable, \( Z \), then we can calculate \( \operatorname{P}_X \) by considering the random variable product/pair \( (X,Z) \). To calculate \( \operatorname{P}_X \), we sum over \( Z \). If instead of knowing \( \operatorname{P}_{(X,Z)} \) we know \( \operatorname{P}_{X|Z} \), then instead of just summing over \( Z \) we need to average over \( Z \) (calculate the expectation). If we are interested in \( \log(\operatorname{P}_X) \), then we can use the concave nature of log along with Jensen's inequality to get an inequality with the log function inside the expectation.
The objects to be visualized:
Alternative
We will view \( P_X \) as a derived random variable by applying a function to another random variable; the function used will be a probability distribution. Start with a random variable \( Z \) for a probability space \( (\Omega, \mathcal{F}, \operatorname{P}) \). Introduce another random variable \( X \) for the same probability space. From these two random variables we will create a new bi-variate random variable \( Y := Z \times X \). We will then create another random variable \( Y_t := Y_{X=t} \), which is simply \( Y \) with the first input fixed to \( t \). We then have the expression:
\[ \begin{align*} \operatorname{P}_X(v) &= \operatorname{E}[Y_v] \\ &= \sum_{\omega \in \Omega} Y(v, Z(\omega))\operatorname{P}(\omega) \\ &= \sum_{z \in \operatorname{Range}(Z) } \operatorname{P}_Z(z) \operatorname{P}_{X|Z}(v, z) \end{align*} \]
This relies on \( \Omega \) being a discrete probability space, as otherwise our \( \operatorname{P} \) is not defined for discrete elements of \( \Omega \).
Another source: https://cscherrer.github.io/post/variational-importance-sampling/
Back: TODO turn into a proper card.
Source: https://chrisorm.github.io/VI-ELBO.html

Title: Monte Carlo Methods
Q: The this card describes Monte Carlo methods in the words of David MacKay. A lot of this card's content is drawn from Chapter 29 of MacKay's book.
Monte Carlo methods. Definition.
Monte Carlo methods is a term for something that utilizes a random number generator to solve one or both of the following problems.
1. Generate [something] from a given [what?]
2. Estimate expectations of functions under this probability distribution. For example, for some function \( \phi \), we want to know:
[\[\int {\dd}^N \vb{x} \;\; ? \;\; \phi(\vb{x}) \]]
The notation used above does a lot of heavy lifting. "\( \mathbb{P}(\vb{x}) \)" suggests a set \( L \subset \mathbb{R}^N \) is the co-domain of an implied random variable \( Y : ? \to L \). \( L \) is also the domain of the function \( \mathbb{P} \) which must have a signature of the form \( \mathbb{P} : L \to \mathbb{R} \). The function \( \phi \) seems to have a signature \( \phi : L \to \mathbb{R} \). It is composed with \( Y \) like \( \phi \circ Y \) and thus, \( \phi \) is a random variable. The composition implies that the domain of \( \phi \) is \( L \). The integration formula further implies either that the co-domain of \( \phi \) must be \( \mathbb{R} \) (alternatively, the integration is syntax is allowing for the interpretation of a vector valued integration which seems a stretch).
The reverse side describes Lake plankton analogy to the above problems. Can you remember the details? The reverse side also rewords the above description in the language of probability distributions.
A: a sequence of samples \( (\vb{x}_i)_{i=1}^{R} \); probability distribution, \( \mathbb{P}(\vb{x}) \).; \[ \int {\dd}^N \vb{x} \; \mathbb{P}(\vb{x}) \phi(\vb{x}) \]
BackOnlyText: Lake plankton analogy
Imagine the task of trying to determine the average plankton concentration of a lake. You are provided with a boat, GPS and a plankton sensor attached to a plumbline. To make this analogy work, we assert that the plankton concentration is vertically uniform. These tools allow you to sample a single 1cm^3 volume of the lake and determine its plankton concentration.
The depth of the lake at position \( \vb{x} = (x, y) \) is given by \( \mathbb{P}^*(\vb{x}) \). The plankton concentration \( \phi(\vb{x}) \) is also function of the position on the lake. The average plankton concentration is then:
\[ \mathrm{E}[\phi] = \frac{1}{Z} \int \dd{x} \dd{y} \; \mathbb{P}^*(\vb{x}) \phi(\vb{x}) \]
Outside of the analogy, the quantity \( \frac{\mathbb{P}*}{Z} = \mathbb{P} \) is the true, normalized probability.
The fact that the depth of the lake is unknown makes it very difficult to calculate \( Z \), and thus, it is very difficult to know how significant a single sample is to the overall calculation. MacKay brought up the example of a lake with narrow deep canyons. This canyon has a large effect on the average concentration; however, it is easy to miss sampling from it altogether. To do a good job of sampling, we must somehow discover the canyons and discover their depth and width relative to the rest of the lake.
Maybe a better analogy is the task of measuring the amount of gold in a gold deposit. Vertical core samples can be taken by pulling out a thin cylindrical sample all the way down to some hard impenetrable rock. The depth of the impenetrable rock is unknown. Trying to infer the total gold deposit from a few samples is a difficult problem that corresponds to the roughly to the second problem (although, it is a bit different).
Monte Carlo methods. More Formal.
An attempt to formulate the ideas using the language of probability spaces might describe Monte Carlo methods as follows.
The two problems that Monte Carlo methods are to solve
Let \( (\Omega, \mathrm{F}, \mathbb{P}) \) be a probability space. Let \( X : \Omega \to \mathbb{R} \) be a random variable. \( \mathbb{P} \) and \( X \) determine the probability distribution \( \mathrm{F}_X : \mathbb{R} \to \mathbb{R} \) of \( X \). In this context, the two problems to be solved are:
1. Generate a sequence of samples \( (\vb{x}_i)_{i=1}^{R} \) (where \( \vb{x}_i \in \mathbb{R}^d \)) such that the samples seem to be drawn from \( \mathrm{F}_X \).
2. To estimate \( \mathrm{E}[X] \) and also estimate \( \mathrm{E}[Y] \) for some random variable \( Y = g(X) \) formed with a function \( g : \mathbb{R}^d \to \mathbb{R}^{d_2} \).
The description of the first problem is discussed in more detail below in Generating a random sequence.
To solve these problems we are allowed to assume the existence of a sequence \( (r_i)_{i=0}^{\infty} \) which represents our access to a random number generator. (TODO: what is the formulation of this sequence in terms of probability spaces and random variables?). A solution to the two problems that utilize this sequence constitutes a Monte Carlo method. What defines a solution is another facet of the situation.
Generating a random sequence
Only in attempting to write the first problem in terms of probability spaces have I realized that it's not obvious how to transition from the ideas of probability spaces to the ideas of generating samples. A lot is glossed over in the words seems to be drawn from. Maybe a better description is to say something like, as \( R \to \infty \), the random variable \( Z : \mathbb{N} \cap [1, R] \to \mathbb{R} \) on the sample space \( \Omega = \mathbb{N} \cap [1, R], \mathrm{F}, \mathbb{P}) \) (with \( \mathbb{P}(\{i\}) = \frac{1}{R} \) and \( \mathrm{F} \) being every subset of \( \Omega \)) has a probability distribution \( \mathrm{F}_X \) that approaches \( \mathrm{F}_X \). This raises more questions about discrete vs. continuous, so I think I'll stop with this thread.
Source: Chapter 29, David MacKay

Title: Importance sampling
Q: Let \( P(x) \) be a distribution which we can evaluate an unnormalized version easily at a point to obtain \( P^*(x) \). \( P(x) = \frac{P^*(x)}{Z} \) where \( Z = \int P^*(x) \dd{x} \). Now propose we have a function \( \phi(x) \) for which we wish to evaluate an expectation. We may proceed with uniform sampling by taking \( R \) samples of a uniform distribution over the domain, \( x_1, x_2, ... x_R \) and calculating an estimate:
[\[ \mathrm{E}[\phi] = \frac{?}{?} \]]
Importance sampling alters this calculation by sampling domain values from a distribution other than the uniform distribution. Let \( Q(x) \) be the sampler distribution. We will sample \( R \) samples from the sampler distribution and estimate the expectation of \( \phi \) like so:
todo
\[ \mathrm{E}[\phi] = \frac{} \]
The sampler distribution has two effects:
1. It focuses where in the domain \( x \) is sampled.
2. It causes the estimation of the normalizing \( Z_P\) constant to be skewed by oversampling some values and undersampling others.
The first effect is beneficial and the second is not. The second effect can be conceptualised  as \( Q(x) \) stretching the domain in some places and shirking it in others. The size of the domain is important as a measure by which we are weighting the \( P^*(x) \) that we are collecting. To counteract the undesired effect of \( Q(x) \), we simply multiply \( P^*(x) \) by \( \frac{1}{Q(x) \). Any part of the domain that is stretch by \( Q(x) \) shrinks the weight given to a \( P^*(x) \) sample by multiplying by the reciprocal amount.
The fact that we multiply \( \phi(x) \) by \( P^*(x) \) fully accounts for the weighting for \( \phi \). The \( \frac{1}{Q(x_0) \) factor is simply to undo the fact that we are going to be sampling point \(x_0 \) excessively according to the value \( Q(x_0) \).
A: \[ \mathrm{E}[\phi] = \frac{\sum_{i=1}^{R} P^*(x_i)\phi(x)}{\sum_{i=1}^{R} P^*(x_i)} \]
BackOnlyText: Efficient integration
Importance sampling is used in rendering. When performing integration, such as calculating the outgoing radiance by integrating incoming radiance, we are aware that light incidenct from the angle of the surface normal will have a large effect (cosine term near 1; the light flux is not stretched over the surface), while light hitting the surface from near perpendicular to the surface normal will have a small effect (cosine term near 0; light flux is spread over the surface). With this knowledge, it is wasteful to sample incident angles uniformly. Having high confidence of the contribution from glancing angles is wasteful as the effect from these angles on the overall sum is minuscule. Therefore, we wish to focus our sampling at the angles that will contribute more. This allows us to approach the true answer quicker with our estimate. Imagine a bell-shaped curve. The x value under the heavy bell center represents the light direction that will have a large impact, and the glancing angles are represented by the thin tails of the curve.
Source: Chapter 29, David MacKay

Title: Jacobian and Hessian
Q: A Jacobian matrix collects all of the first partial derivatives of a function with multiple inputs and multiple outputs. The columns of the Jacobian keep the [input or output?] constant, and the rows keep the [input or output?] constant. So, a function with a Jacobian matrix that is a colomun vector must be a Jacobian for a function with a single [input or output?].
Extending the idea of the Jacobian to second partial derivatives would give us a 3D tensor. A special case is when a function has only 1 output: In this case, the collection of all second partial derivatives can be collected in a 2D matrix. This is what is called the Hessian.
A: input variable; output variables; input
BackOnlyText: Separate this card into two at some point and elaborate.