Title: Andrew Ng Coursera

Q: Machine learning
A: Field of study that gives computers the ability to learn without being explicitly programmed

Q: Supervised learning
A: Learns input to output (\(X\mapsto Y\)) mappings from a sample set of labelled examples.
Can be partitioned into regression (real-valued \(Y\)) and classification (categorical \(Y\)) problems

Q: Unsupervised learning
A: Algorithms that find structures or patterns in unlabelled data, e.g. clustering, anomaly detection, dimensionality reduction

Q: Supervised Learning model
A: In a supervised learning problem, the model \(f\) is the function which maps feature vectors to predictions, i.e. \(\hat{y}=f(\mathbf{x})\) where \(\mathbf{x}\) is a feature vector and \(\hat{y} \) is the prediction

Q: Gradient descent
A: At each step, we update the parameters \(w\) by
\[\mathbf{w} \mapsto \mathbf{w} - \alpha \nabla_{\mathbf{w}}J\]where \(\alpha\) is the learning rate, \(J(\mathbf{w})\) is the cost function and repeat until convergence.

Q: Batch learning
A: Batch learning is a learning process where the cost function \(J(\mathbf{w}) \) is a function of the entire training set, e.g. mean squared error:
\[J(\mathbf{w}) = \frac{1}{2m}\sum_{i=1}^m |y - \hat{y}|^2.\]

Q: Normal equation
A: Linear regression with squared-error cost has the closed form solution
\[\begin{align*} J(\boldsymbol{\beta}) &= |Y - X\boldsymbol{\beta} |^2\\ \frac{\partial J}{\partial\boldsymbol{\beta}}(\hat{\boldsymbol{\beta}}) &= -2X^T(Y - X\hat{\boldsymbol{\beta}})\\ &= 0\\ X^TY &= X^TX\hat{\boldsymbol{\beta}}\\ \hat{\boldsymbol{\beta}} &= (X^TX)^{-1}X^TY. \end{align*}\]

Q: Feature scaling
A: We can standardise the features by
\[x\mapsto \frac{x - \mu(x)}{\sigma(x)}\]or normalise the features by
\[x\mapsto \frac{x - \mu(x)}{\max(x) - \min(x)}\]
so that training steps will make similar progress in fitting all of the weights.

Q: Learning curve
A: A plot of the loss function after iterations of learning. Whenn the curve levels off we declare convergence. If the curve increases then our learning rate may be too large.

Q: Feature engineering
A: Using intuition to design new features by transforming or combining original features

Q: Polynomial regression
A: A regression model where features are raised to powers, including fractional powers

Q: Logistic regression
A: For a Bernoulli distribution\(X\sim\mathrm{Bin}(1, p)\) we fit a linear model for the log-odds (aka logit function)
\[\eta = \boldsymbol\beta\cdot \mathbf{x}=\log\left(\frac{p}{1-p}\right)\]so-named because
\[p = \sigma(\eta) = \frac{1}{1+e^{-\eta}}\]is the logistic function.

Q: Decision boundary
A: In classification problems, we define \(\boldsymbol\beta\cdot\mathbf{x}=0 \) as the decision boundary. Assuming a sigmoid function \(p=\sigma(\boldsymbol\beta\cdot\mathbf{x})\), this is the boundary between samples which the model assigns to the positive class vs. the negative class.

Q: Logistic loss function
A: For a binary output \(y\) we define the logistic loss function
\[\begin{align*} L(y, \hat{y}) &= -y\log(\hat{y}) - (1-y)\log(1-\hat{y}) \\ &= \begin{cases} -\log(\hat{y}) \quad &\text{if } y=1 \\ -\log(1-\hat{y}) \quad &\text{if } y=0. \end{cases} \end{align*}\]

Q: Logistic sigmoid function
A: The function
\[\sigma(\eta) = \frac{1}{1+e^{-\eta}}\]has the nice property of mapping the real line to the unit interval.

Q: Derivative of logistic function
A: The logistic sigmoid function has the neat derivative
\[\sigma'(\eta) = \frac{e^{-\eta}}{(1+e^{-\eta})^2} = \sigma(1-\sigma).\]

Q: Feature selection
A: Taking a subset of the features to reduce overfitting

Q: Regularisation
A: Encouraging the learning process to reduce the impact of each feature

Q: Solutions to overfitting
A: 1. More data
2. Feature selection
3. Regularization

Q: Layer
A: A collection of neurons with similar input features. They can be partioned into three types: input layer, hidden layer and output layer.

Q: Activation
A: The logistic output of a neuron

Q: ReLU
A: Rectified Linear Unit is the activation function \(\max(0, z)\) which is the most common for hidden layers because it is only flat in one region so it is good for learning

Q: Linear activation
A: This is another name for not using an activation function, useful for real-valued output

Q: Forward propagation equation
A: To propagate activations forward in a neural network, we use the following
\[\begin{align*} a^{l}_j &= \sigma\left( \sum_k w^{l}_{jk} a^{l-1}_k + b^l_j \right)\\ \mathbf{a}^{l} &= \sigma(W^l \mathbf{a}^{l-1}+\mathbf{b}^l). \end{align*}\]

Q: Softmax activation
A: For sparse categorical output layers we use the activation function
\[a_i = \frac{e^{z_i}}{\sum_j e^{z_j}}.\]

Q: Cross-entropy loss for softmax
A: For softmax activation, we use loss function
\[\text{loss}(\mathbf{a}, \mathbf{y}) = \begin{cases} -\log a_0 \quad \text{if } y=0 \\ \cdots \\ -\log a_i \quad \text{if } y=i \end{cases}\]

Q: Multilabel classification
A: When there are multiple output labels which are not mutually exclusive, we use logistic activation in the output layer

Q: Multiclass classification
A: When there are multiple mutually exclusive labels, we use softmax activation in the output layer

Q: Dense layer
A: Each neuron takes every activation in the previous layer as an input.
Also known as Fully Connected (FC).

Q: Convolutional neural networks
A: A layer which only uses activation from a region of an image

Q: Data augmentation
A: Artificially increasing the size of the training data by creating new data through perturbing the raw training data

Q: Data synthesis
A: Creating fake training data from scratch to increase the sample size

Q: Transfer learning
A: If we lack sufficient training data for a particular task, we may begin with supervised pre-training on a different larger dataset with the same features but different outputs and then fine-tuning the network by either:
1. take the pre-trained network's hidden layers as fixed and re-train the output layer
2. re-train the whole network using the pre-trained weights as initial values.

Q: Precision
A: We define precision as
\[\text{precision} = \frac{\text{# true positives}}{\text{# true positives} + \text{# false positives}}.\]This is closely related to specificity, but expressed as a posterior: conditional on a positive, do we believe it is true?

Q: Recall
A: We define recall, or sensitivity, as
\[\text{recall} = \frac{\text{\# true positives}}{\text{\# actual positives}} = 1 - \text{Type 2 Error rate}, \]i.e. how likely is the classifier to deliver a true positive to a sample from the positive class?

Q: Specificity
A: We define
\[\text{specificity} = \frac{\text{\# true negatives}}{\text{\# true negatives} + \text{\# false positives}} = 1 - \text{Type 1 Error rate},\]i.e. how likely is the classifier to label a sample from the negative class a true negative.

Q: Effect of increasing thresholds on precision/recall
A: Higher thresholds for a binary classifier give a higher precision (as there are fewer false positives) and lower recall (as there are fewer true positives).

Q: F1 score
A: For a binary classifier of precision \(p\) and recall \(r\) we define the combined metrice called the F1 score as their harmonic mean:
\[F_1 = \frac{1}{\frac{1}{2}\left(\frac{1}{p} + \frac{1}{r}\right)} = \frac{2pr}{p + r}.\]This is the smallest of the three Pythagorean means and really emphasises small values.

Q: Information gain
A: Reduction in entropy from adding a split to a decision tree
\[\text{gain} = H(p_1^\text{root}) - \left(w^L H(p_1^L) + w^RH(p_1^R)\right).\]

Q: Decision tree learning
A: Iterate through every feature and every threshold, then pick the split with the greatest information gain. Stopping criteria are
- When a node is 100% one class
- Maximum depth
- Information gain from additional splits is less than threshold
- Number of examples in node is less than threshold.

Q: One hot encoding
A: We can convert a multi-class categorical feature with multiple binary features, e.g. for decision tree learning

Q: Regression trees
A: We take the arithmetic mean of the output variable at each leaf and minimise the weighted-averaged variance in the leaves at each split.

Q: Tree ensemble
A: Majority vote wins

Q: Bagging
A: Given a training set of size \(m\), for \(b = 1 \text{ to } B\): we sample with replacement a training set of size \(m\) and fit a model.

Q: Random forest algorithm
A: An ensemble of trees where we sample \(\frac{1}{\sqrt{n}}\) of the features at each split.

Q: Boosting
A: During bagging, we increase the probability that the next classifier will sample from misclassified examples from the previous tree

Q: Decision trees vs. neural networks
A: - Neural networks work better on unstructured data like images, audio, text
- Decision trees are faster
- Small trees are interpretable

Q: K-means clustering
A: Initialise \(K\) cluster centroids \(\boldsymbol{\mu}_1, \boldsymbol{\mu}_2,\ldots \boldsymbol{\mu}_K \) by randomly sampling \(K\) points. Then update the centroids as follows
\[\begin{align*} c^{(i)} &:= \arg\min_k \| \mathbf{x}^{(i)} - \boldsymbol{\mu}_k\| \quad && 1\leq i \leq k \\ \boldsymbol{\mu}_k' &:= \frac{1}{\#\{ i | c^{(i)} = k\}} \sum_{i | c^{(i)} = k} \mathbf{x} \quad && 1 \leq k \leq K. \end{align*}\]The cost function minimised by \(K\)-means is the distortion function
\[J(\mathbf{x}_1, \ldots \mathbf{x}_m, \boldsymbol\mu_1, \ldots \boldsymbol\mu_K) = \sum_{i=1}^m \|\mathbf{x}_i - \boldsymbol\mu_{c^{(i)}}\|^2.\]We can then take the optimal clusters over many random initialisations.
We pick the value of \(K\) based on our use case.

Q: Distortion function
A: The cost function minimised by K-means is
\[J(\mathbf{x}_1, \ldots \mathbf{x}_m, \boldsymbol\mu_1, \ldots \boldsymbol\mu_K) = \sum_{i=1}^m \|\mathbf{x}_i - \boldsymbol\mu_{c^{(i)}}\|^2.\]

Q: Elbow method
A: Picking the value of \(K\) for \(K\)-means by plotting the cost function against \(K\) and taking the point where it starts to flatten.

Q: Density estimation
A: Assuming features are designed to approximate independent normal random variables, we fit parameters
\[\begin{align*} \mu_j &= \frac{1}{m}\sum_{i=1}^m x_j^{(i)} \\ \sigma_j^2 &= \frac{1}{m}\sum_{i=1}^m (x_j^{(i)} - \mu_j)^2 \end{align*}\]and then compute the Gaussian density \(p(\mathbf{x}) \) for a sample, declaring it anomalous if \(p(\mathbf{x}) < \varepsilon.\) We can tune \(\varepsilon\) using a validation set. This is better than supervised learning for detecting unprecedented anomalies.

Q: Collaborative filtering
A: Without features to learn a recommender model per user, we can learn an \(n\) dimensional embedding by minimising
\[J(w, b, x) = \frac{1}{2}\sum_{i, j: \text{user $j$ has rated item $i$}} L(\mathbf{w}^{(j)},\mathbf{x}^{(i)}, b^{(j)}, y^{(i, j)}) + \frac{\lambda}{2}\sum_{j=1}^{n_u} \sum_{k=1}^n |w_k^{(j)}|^2 + \frac{\lambda}{2}\sum_{i=1}^{n_m} \sum_{k=1}^n |x_k^{(i)}|^2\]using gradient descent where
\[L(\mathbf{w}, \mathbf{x}, b, y) = (\mathbf{w} \cdot \mathbf{x} + b - y)^2\]is the squared error for real-valued ratings or
\[L(\mathbf{w}, \mathbf{x}, b, y) = -y \log \sigma(\mathbf{w} \cdot \mathbf{x} + b) - (1-y)\log\left(1-\sigma(\mathbf{w} \cdot \mathbf{x} + b)\right)\]is the binary cross-entropy loss.

Q: Content-based filtering
A: Given user features and item features, we can fit a recommender network which maps user features \(\mathbf{x}_u\mapsto \mathbf{v}_u\) and item features \(\mathbf{x}_m\mapsto \mathbf{v}_m\) to vectors of the same length and then minimising
\[J = \sum_{i, j: \text{user $j$ has rated item $i$}} L(\mathbf{v}_u^{(j)} \cdot\mathbf{v}_m^{(i)}, y^{(i, j)}) \]using backpropagation.

Q: Retrieval and ranking
A: For recommending from a large catalogue, we can
1. Generate a large list of plausible candidates based on similarity to user's other liked items or most liked items in the catalogue
2. Remove duplicates and already seen items
3. Rank using neural network model.

Q: Return
A: Discounted expected reward \(J(\pi_\theta)=\mathbb{E}[R(\tau)]\)

Q: Policy
A: A policy \(\pi\) is a mapping from the state space to the action space

Q: Markov Decision Process
A: In an MDP, the probability distribution of the future state conditional on the present state is the same whether or not we also condition on the history.

Q: Bellman equation
A: Bellman equation says
\[Q(s, a) = R(s) + \gamma\mathbb{E}\left[\max_{a'}Q(s', a')\right]\]where \(Q\) is the state-value function.

Q: DQN algorithm
A: The Deep Neural Network approach to learn the state-value function \(Q\) is as follows:
Initialise a neural network to fit \(Q(s, a).\) Start taking actions using an \(\boldsymbol\varepsilon\)-greedy policy: use our estimate of \(Q\) in the Bellman equation with probability \(1-\varepsilon\), otherwise act randomly, and collect a set of \(m\) tuples \((s, a, R(s), s').\)
Train new weights for \(Q^*\) using the Bellman equation
\[Q^*(s, a) = R(s) + \gamma\mathbb{E}\left[\max_{a'}Q(s', a')\right].
\]
We apply a soft update to \(Q:= (1-\delta)Q + \delta Q^*\). This helps to reduce maximisation bias.
It helps to include a neuron in the final hidden layer for each action in the space to better compute this maximum.

Q: Mini-batching
A: Computing the cost function for a different subset of the training data at each step during learning