⁉
Selbsttestfragen

Nachfolgende Fragen eigenen sich zur Prüfungsvorbereitung mittels Active Recall gedacht und eine Ergänzung zu Karteikarten.
Offizielle Fragen sind mit 🧠 markiert. Probeklausurfragen mit einem 🦧. Fragen der University of Stanford mit 🧑‍🚒. Eigene Fragen haben keine Markierung.
Weitere interessante Fragen finden sich auch bei den Selbsttestfragen zu Adv. ML.
Linear Regression
Under which assumptions is the least-squares objective from linear regression equivalent to a maximum likelihood objective?🦧
Gaussian likelihood with linear mean and constant noise.
What is the role of the lambda factor in the objective of ridge regression and how is it determined? 🦧
$$\lambda$ controls the degree of penalization. It is determined through cross-validation.
Linear Classification
Write down the objective of linear binary logistic regression. The samples are given by xix_{i}xi​
 and the labels by ci∈{0,1}c_{i} \in\{0,1\}ci​∈{0,1}
. How is p(ci∣xi)p\left(c_{i} \mid \boldsymbol{x}_{i}\right)p(ci​∣xi​)
 assumed to be distributed in binary logistic regression?🦧
​argmax⁡w∑i=1Ncilog⁡(σ(wTxi))+(1−ci)log⁡(1−σ(wTxi))\operatorname{argmax}_{\boldsymbol{w}} \sum_{i=1}^{N} c_{i} \log \left(\sigma\left(\boldsymbol{w}^{T} \boldsymbol{x}_{i}\right)\right)+\left(1-c_{i}\right) \log \left(1-\sigma\left(\boldsymbol{w}^{T} \boldsymbol{x}_{i}\right)\right)argmaxw​∑i=1N​ci​log(σ(wTxi​))+(1−ci​)log(1−σ(wTxi​))
​
Logistic regression assumes p(ci∣xi)p\left(c_{i} \mid x_{i}\right)p(ci​∣xi​)
to be Bernoulli distributed.
Explain the difference between generative and discriminative classification? Which is usually easier? 🦧
In generative classification we model the data and use Bayes rule to obtain the class-posterior. In discriminative classification, the class-posterior is directly modelled. Discriminative classification is usually easier.
Define the Bernoulli likelihood of linear logistic regression for a single sample xxx
 and label y∈{0,1}y \in \{0,1\}y∈{0,1}
.
​p(y∣x)=σ(wTx+b)y(1−σ(wTx+b))1−yp(y \mid x)=\sigma\left(\boldsymbol{w}^{T} \boldsymbol{x}+b\right)^{y}\left(1-\sigma\left(\boldsymbol{w}^{T} \boldsymbol{x}+b\right)\right)^{1-y}p(y∣x)=σ(wTx+b)y(1−σ(wTx+b))1−y
​
Model Selection
Why is it a bad idea to evaluate your algorithm on the training set? 🧠
It's important to use unseen data when evaluating an algorithm to prevent overfitting.
One would have zero empirical risk but a very high true risk.
In the worst case an algorithm could learn the data by heart, perform well during testing and training but perform poorly on real unseen data.
What is the difference between true and empirical risk? 🧠
True risk is the performance on a random test point (x,y)(x,y)(x,y)
. True risk is unknown.
Empirical risk is the performance on the training set. Empirical risk can be evaluated using training samples.
The true risk can be decomposed in which parts?🧠
The true risk can be decomposed into:
​EDn[Ex,y[(f^Dn(x)−f^∗(x))2]]⏟Variance +Ex,y[(f^∗(x)−f(x))2]⏟Bias 2+σ2⏟noise \underbrace{\mathbb{E}_{D_{n}}\left[\mathbb{E}_{x, y}\left[\left(\hat{f}_{D_{n}}(x)-\hat{f}_{*}(x)\right)^{2}\right]\right]}_{\text {Variance }}+\underbrace{\mathbb{E}_{x, y}\left[\left(\hat{f}_{*}(x)-f(x)\right)^{2}\right]}_{\text {Bias }^{2}}+\underbrace{\sigma^{2}}_{\text {noise }}Variance EDn​​[Ex,y​[(f^​Dn​​(x)−f^​∗​(x))2]]​​+Bias 2Ex,y​[(f^​∗​(x)−f(x))2]​​+noise σ2​​
​
How is the bias and the variance of a learning algorithm defined and how do they contribute to the true risk?🧠
Variance:
​EDn[Ex,y[(f^Dn(x)−f^∗(x))2]]\mathbb{E}_{D_{n}}\left[\mathbb{E}_{x, y}\left[\left(\hat{f}_{D_{n}}(\boldsymbol{x})-\hat{f}_{*}(\boldsymbol{x})\right)^{2}\right]\right]EDn​​[Ex,y​[(f^​Dn​​(x)−f^​∗​(x))2]]
​
Variance is the difference between the estimates and the "best" estimates. Error depends on the number of data points that are available for training. It accounts for the limitations in the training data set.
Bias:
​Ex,y[(f^∗(x)−f(x))2]\mathbb{E}_{x, y}\left[\left(\hat{f}_{*}(\boldsymbol{x})-f(\boldsymbol{x})\right)^{2}\right]Ex,y​[(f^​∗​(x)−f(x))2]
​
Bias is the difference between the true function and the "best" estimate of the model.
Bias, variance, and noise sum up to the true risk.
What is the advantage/disadvantage of k-fold CV vs. the Hold-out method?🧠
k-Fold CV uses the entire data set for training, as the kkk
-th fold is used for testing and the remaining folds are used for training. This is less wasteful compared to the Hold-Out-method, where a certain percentage of the data is exclusively reserved for testing.
On the other hand, is k-Fold CV more computationally expensive as it requires kkk
 iterations to train the model. It also leads to more stable results though. In comparison, the Hold-out-method is less computationally expensive, as it requires only one run.
What is problematic about the hold-out method is, that unlucky splits might give misleading results.
Why does it make sense to penalize the norm of the weight vector?🧠
Applying a penalty to large weight vectors helps to keep the parameters small. Which leads to a smoother function.
Also, the complexity of the model is limited.
The larger λ\lambdaλ
, the less complex the final model will be.
Which norm can we use and what are the different effects?
​ℓ1\ell_1ℓ1​
 penalty:
​penalty⁡(θ)=∥θ∥1=∑d∣θd∣\operatorname{penalty}(\boldsymbol{\theta})=\|\boldsymbol{\theta}\|_{1}=\sum_{d}\left|\theta_{d}\right|penalty(θ)=∥θ∥1​=∑d​∣θd​∣
​
Introduces sparse solutions, which means some parameters can be 0. Suitable for feature selection.
Hard to optimize.
​ℓ2\ell_2ℓ2​
 penalty:
​penalty⁡(θ)=∥θ∥2=∑dθd2\operatorname{penalty}(\boldsymbol{\theta})=\|\boldsymbol{\theta}\|_{2}=\sum_{d} \theta_{d}^{2}penalty(θ)=∥θ∥2​=∑d​θd2​
​
Redundant parameters will be close to 0, but never 0.
Easy to optimize.
What is the effect of early stopping?🧠
Early stopping prevents overfitting, as model is not trained to the smallest training error.
Further more, the model's complexity is limited. E. g. with Boosting approaches, one doesn't learn overly complicated trees.
Give examples how to influence the model-complexity of at least 3 different algorithms.🦧
Neural networks: Add/remove neurons or entire layers
K-NN: Increasing k decreases model complexity
Trees and forests: Increasing depth increases complexity
Generalized linear methods: Choose larger function class as feature mapping
Kernel methods: Use kernel with higher dimensional underlying feature space
Mixture models: Use more mixture compenents
Nearest neighbour Algorithms, Trees, and Forests
What we mean with non-parametric / instance-based machine learning algorithms?🧠
Non-parametric ML algorithms are algorithms, that do not learn a parametric model, but store all the training data and use the training data to make predictions.
Examples include the kkk
-nearest neighbour algorithm and the Gaussian processes.
How does kkk
-Nearest neighbour works?🧠
To classify a new input vector xxx
, we examine the kkk
closest training data points to xxx
(that lie within a hypersphere).
We assign the class that is most frequent among those neighbours to the query point xxx
.
Why is it hard to use for high-dimensional data?🧠
​kkk
-Nearest neighbour is built around a distant-based measure. However, in a very high-dimensional space, most points are equally far apart from each other.
So the neighbourhood becomes large.
How to search for nearest neighbours efficiently?🧠
It's convenient to use a KD-tree as the data structure. The KD tree is balanced and performs binary splits on the feature space.
Searching goes like this:
Find region containing x\boldsymbol{x}x
. Navigate starting from the root node to the child node containing x\boldsymbol{x}x
.
Save region point x∗=x0\boldsymbol{x}^{*} = \boldsymbol{x}_{0}x∗=x0​
 as current best.
Move up tree and recursively search regions intersecting hypersphere S(x,∥x−x∗∥)S\left(\boldsymbol{x},\left\|\boldsymbol{x}-\boldsymbol{x}^{*}\right\|\right)S(x,∥x−x∗∥)
.
Update x∗\boldsymbol{x}^{*}x∗
 if new nearest neighbour has been found.
What is a binary regression/decision tree?🧠
A binary decision tree is a tree that performs a binary split at each node. The predictor space is segmented into smaller regions.
In case of regression trees the predicted value at a node is the average response variable of all observations within this node.
What are useful splitting criterions?🧠
For regression trees:
Minimum residual sum of squares: RSS=∑left (yi−yˉL)2+∑right (yi−yˉR)2\mathrm{RSS}=\sum_{\text {left }}\left(y_{i}-\bar{y}_{L}\right)^{2}+\sum_{\text {right }}\left(y_{i}-\bar{y}_{R}\right)^{2}RSS=∑left ​(yi​−yˉ​L​)2+∑right ​(yi​−yˉ​R​)2
​
For classification trees:
Information gain / Minimum entropy: NLH(pL)+NRH(pR)N_{L} H\left(p_{\mathrm{L}}\right)+N_{R} H\left(p_{\mathrm{R}}\right)NL​H(pL​)+NR​H(pR​)
​
How can we influence the model complexity of a tree?🧠
One can limit the depth of the tree or limit the minimum number of samples that must be present within one node.
Another way is to apply pruning to a decision tree, which refers to cutting back a fully grown tree.
Why is it useful to use multiple trees and randomization?🧠
Decision Trees are prone to overfitting. That's why we should learn several trees to increase variability.
By randomizing the features, using bootstrap samples of the data and combining the trees (random forest) or learning several trees on bootstrap samples (bagging) one can prevent trees from overfitting.
Name at least two advantages and two disadvantages of decision trees. 🦧
Advantages:
Easy to interpret (if they are small)
Computationally efficient. They are quick to fit, even for large problems.
Disadvantage:
Other ML methods such as NN achieve a better accuracy.
Suffer from instability, if we change the data, ever-so-slightly trees can change a lot.
Which data structure is usually used to efficiently implement k-Nearest neighbors? Name the main steps in building that data structure.🦧
KD-Trees are commonly used.
Building the tree:
choose dimension (e. g. longest hyper-rectangle)
Choose median as a pivot
Split node according to the chosen pivot and dimension.
Clustering
How is the clustering problem defined?🧠
Clustering tries to find a natural grouping within the data.
One tries to maximize the intra-cluster similarity and minimize the inter-cluster similarity.
Why is it called 'unsupervised'?🧠
It's called unsupervised, as the data is unlabelled. There is no supervisor, that tells us in advance to which cluster a training data point belongs. Hence, unsupervised. The structure is actually learned from the data.
How do hierarchical clustering methods work? 🧠
Init-phase: Each of the nnn
samples becomes a cluster itself
Iterate-phase:
1.Find closest clusters and merge them
2.Proceed until we have a single cluster
What is the rule of the cluster-2-cluster distance and which distances can we use?🧠
So-called cluster linkage types define the distance between two clusters. Commonly used are
Single linkage
Complete linkage
Average linkage
Centroid linkage
How does the kkk
-mean algorithm work? What are the two main steps?🧠
The two main steps are the assignment and adjustment step.
Assignment step:
Assign each sample to its closest centroid zn=arg⁡min⁡k∥ck−xn∥2z_{n}=\arg \min_{k}\left\|\boldsymbol{c}_{k}-\boldsymbol{x}_{n}\right\|^{2}zn​=argmink​∥ck​−xn​∥2
​
Adjustment Step:
Adjust the centroids to be the means of the samples assigned to them: ck=1∣Xk∣∑xi∈Xkxi,Xk={xn∣zn=k}c_{k}=\frac{1}{\left|X_{k}\right|} \sum_{\boldsymbol{x}_{i} \in X_{k}} \boldsymbol{x}_{i}, \quad X_{k}=\left\{\boldsymbol{x}_{n} \mid z_{n}=k\right\}ck​=∣Xk​∣1​∑xi​∈Xk​​xi​,Xk​={xn​∣zn​=k}
​
Why does the algorithm converge? What is it minimizing?🧠
​kkk
-means minimizes the Sum of Squared Distances (SSD). By checking, if a cluster centroids exists, that is closer to a point than its current cluster centroid the SSD is reduced. If no closer cluster centre exists and the SSD remains constant.
SSD is defined as SSD⁡(C;D)=∑i=1nd(xi,c(xi))2\operatorname{SSD}(C ; \mathcal{D})=\sum_{i=1}^{n} d\left(\boldsymbol{x}_{i}, c\left(\boldsymbol{x}_{i}\right)\right)^{2}SSD(C;D)=∑i=1n​d(xi​,c(xi​))2
​
Does kkk
-means find a global minimum of the objective?🧠
No, generally it doesn't. Finding a global minimum is a NP-hard problem. One would have to check all assignments to find the global best solution.
Moreover, the result of kkk
-means is heavily dependent on the initialization.
Dimensionality Reduction
What does dimensionality reduction mean?🧠
Dimensionality reduction refers to projecting an original data point xi∈RD\boldsymbol{x}_{i} \in \mathbb{R}^{D}xi​∈RD
into a lower dimensional representation zi∈RM\boldsymbol{z}_{i} \in \mathbb{R}^{M}zi​∈RM
through a mapping xi→zi\boldsymbol{x}_{i} \rightarrow \boldsymbol{z}_{i}xi​→zi​
.
If the mapping is linear it can be represented as a function:zi=Wxi, with W∈RM×D\boldsymbol{z}_{i}=\boldsymbol{W} \boldsymbol{x}_{i}, \text { with } \boldsymbol{W} \in \mathbb{R}^{M \times D}zi​=Wxi​, with W∈RM×D
.
What is PCA? 🧠
PCA is an approach for dimensionality reduction.
PCA finds a low-dimensional representation of the data set that captures as much variance as possible. PCA seeks to find a smaller number of dimensions, where each dimension is a linear combination of the features.
The first principal component is a set of features X1,X2,…,XpX_{1}, X_{2}, \ldots, X_{p}X1​,X2​,…,Xp​
 is the normalized linear combination of the features with Z1=ϕ11X1+ϕ21X2+…+ϕp1XpZ_{1}=\phi_{11} X_{1}+\phi_{21} X_{2}+\ldots+\phi_{p 1} X_{p}Z1​=ϕ11​X1​+ϕ21​X2​+…+ϕp1​Xp​
. ϕ1=(ϕ11ϕ21…ϕp1)T\phi_{1}=\left(\begin{array}{llll} \phi_{11} & \phi_{21} & \ldots & \phi_{p 1} \end{array}\right)^{T}ϕ1​=(ϕ11​​ϕ21​​…​ϕp1​​)T
 are the principal component loading vector. (James et. al p. 375)
What are three things that it does?🧠
PCA maximizes variance of the projection
PCA minimizes the error of the reconstruction
PCA projects the data into a linear subspace
What are the roles of the Eigenvectors and Eigenvalues in PCA?🧠
Eigenvectors point to the directions of largest variance
Largest Eigenvalues give the values of the largest variance
Can you describe applications of PCA?🧠
Find a natural coordinate system for the data
Transform into a lower-dimensional representation
Common pre-processing technique
Why should each dimension have a unit variance / be normalized?
Doing a PCA is a variance maximizing exercise. Therefore, if features have a different variance, features with the greatest variance will be loaded the most. To give the features the greatest weight, that explain most of the variance, data should be normalized first.
Density Estimation and Expectation Maximization
What are parametric methods and how to obtain their parameters?🧠
Parametric models are models, where we assume a certain underlying probability distribution. The no. of parameters is fixed. (see also here.)
How many parameters have non-parametric methods?🧠
non-parametric models derive the probability density from the data and don't assume a parametric models. Thus, don't require parameters to specify the model.
However, they can have hyperparameters such as the bin count in a histogram, which depend on the concrete method.
What are mixture models?🧠
Mixture models create a complex distribution by combining simple ones.
They have the following parameters θ={π1,μ1,Σ1,…,πK,μK,ΣK}\boldsymbol{\theta}=\left\{\pi_{1}, \boldsymbol{\mu}_{1}, \boldsymbol{\Sigma}_{1}, \ldots, \pi_{K}, \boldsymbol{\mu}_{K}, \boldsymbol{\Sigma}_{K}\right\}θ={π1​,μ1​,Σ1​,…,πK​,μK​,ΣK​}
, where π\piπ
stands for the responsibility or contribution of each distribution to the final mixture. μK\mu_KμK​
and ΣK\Sigma_KΣK​
describe the Gaussian distribution of the kkk
th component.
Should gradient methods be used for training mixture models?🧠
No, gradient descent shouldn't be used to train mixture models, as optimizing the likelihood of a sum is problematic. Convergence will be slow.
Should use Expectation Maximization instead.
How does the EM algorithm work?🧠
The EM algorithm is an iterative algorithm for estimating latent variable models consisting of two steps. The first step is the Expectation step.
The E step maximizes the lower bound with respect to some arbitrary distribution q(z)q(z)q(z)
of the latent variable zzz
, by minimizing / vanishing the Kullback Leibler distance of q(z)q(z)q(z)
. The lower bound is tight, as the marginal likelihood equals the lower bound.
In the second step, the M step the lower bound is maximized with respect to θ\boldsymbol{\theta}θ
 to obtain a new parameter estimate θnew\boldsymbol{\theta}^{\text{new}}θnew
. As qqq
is estimated using the old parameters of θ\boldsymbol{\theta}θ
, the KL will be larger than zero and the overall marginal likelihood increases.
What is the biggest problem of mixture models?🧠
Mixture models assume that the data can be modelled through a combination of parametric distributions e. g. Gaussians.
How does EM decomposes the marginal likelihood?🧠
​log⁡p(x∣θ)z=∑zq(z)log⁡p(x,z∣θ)q(z)+∑zq(z)log⁡q(z)p(z∣x)\log p(\boldsymbol{x} \mid \boldsymbol{\theta})_{z}=\sum_{z} q(z) \log \frac{p(\boldsymbol{x}, z \mid \boldsymbol{\theta})}{q(z)}+\sum_{z} q(z) \log \frac{q(z)}{p(z \mid x)}logp(x∣θ)z​=∑z​q(z)logq(z)p(x,z∣θ)​+∑z​q(z)logp(z∣x)q(z)​
​
Why does EM always improve the lower bound?🧠
In the E-Step the KL is minimized to zero, while the log-likelihood remains unchanged, hence the lower bound has to increase. This is due to the fact, that the lower bound is the difference between the unchanged marginal likelihood and the KL.
In the M-Step the lower bound also increases, unless it's already at the maximum, as the new parameter set has to be at least as good as the old parameter estimate.
Why does EM always improve the marginal likelihood?🧠
Marginal log-likelihood is always improved in the maximization step, as the lower bound is maximized with respect to θ\thetaθ
 to give some new θnew\theta^{\text{new}}θnew
.That is, the L\mathcal{L}L
will go up. But as qqq
is determined with the old parameters, it will be different to the new posterior distribution of ppp
. Hence, the KL will be non-zero or positive. So the sum of both terms will be greater than before.
Why can we optimize each mixture component independently with EM?🧠
We can separately update the single components and coefficients in the M step, as the objective of the lower bound is additive. (p. 43)
TODO: Get a better understanding.
Why do we need sampling for continuous latent variables?🧠
Typically it is not feasible to compute the integral in the Maximization step with continuous latent variables, as no analytical solutions exist for the integral (see slide 55 f.)
Instead an MC estimation is used to calculate the lower bound.
Why is a neural network considered a parametric model?
Deep learning models are generally parametric. Most often, they have a huge number of parameters, one for each weight that is tuned during training. (see here.)
What is the link between Entropy and Kullback-Leiber divergence?
KL(p∥q)=−∫p(x)ln⁡q(x)dx−(−∫p(x)ln⁡p(x)dx)=−∫p(x)ln⁡{q(x)p(x)}dx\begin{aligned} \mathrm{KL}(p \| q) &=-\int p(\mathbf{x}) \ln q(\mathbf{x}) \mathrm{d} \mathbf{x}-\left(-\int p(\mathbf{x}) \ln p(\mathbf{x}) \mathrm{d} \mathbf{x}\right) \\ &=-\int p(\mathbf{x}) \ln \left\{\frac{q(\mathbf{x})}{p(\mathbf{x})}\right\} \mathrm{d} \mathbf{x} \end{aligned}KL(p∥q)​=−∫p(x)lnq(x)dx−(−∫p(x)lnp(x)dx)=−∫p(x)ln{p(x)q(x)​}dx​
(see Bishop p. 55)
How does the Variational Bayes algorithm improve on the Expectation Maximization algorithm?
The EM-algorithm assumes that the Kullback-Leiber distance can be set to zero.
This is however not possible for complex latent variable models. Variational Bayes models solve this issue by allowing the KL to be greater than 0 after the E-step.
What is the EM algorithm for?
Finding the maximum likelihood solutions of a probabilistic model with latent variables
Why is it a lower bound?
Since Since KL(q∥p)≥0\mathrm{KL}(q \| p) \geq 0KL(q∥p)≥0
 it follow that L(q,θ)≤log⁡p(x∣θ)\mathcal{L}(q, \boldsymbol{\theta}) \leq \log p(\boldsymbol{x} \mid \boldsymbol{\theta})L(q,θ)≤logp(x∣θ)
.
What are weaknesses of the EM algorithm?
EM is sensitive to initialization.
Often times kkk
-nearest neighbour is used for initialization.
How parametric and non-parametric models compare? What are their advantages/drawbacks?
Parametric models
Friendly analytic properties (+)
Simple (+)
Small memory requirements (+)
Fast (+)
Limited representation (-)
Non-parametric models
Very general (+)
Suffer from curse of dimensionality (-)
Large memory requirements (-)
Slow (-)
What is the difference between kernel density estimation and kkk
-nearest neighbor?
Both approaches allow to calculate the probability that a point falls into a region.
Kernel density estimation
Fix VVV
 (Volume) and determine KKK
 (the no. of data points KKK
 in fixed hypercube)
​kkk
-nearest neighbour estimation
Fix KKK
(no. samples in Region) and determine size of Sphere VVV
.
First, we increase the size of the hypersphere until KKK
points lie inside.
Show that the Kullback-Leibler distance is ...
(Whiteboard)
What are the convergence properties of EM?
EM improves the lower bound L(qnew ,θnew )≥L(qold ,θold )\mathcal{L}\left(q_{\text {new }}, \boldsymbol{\theta}_{\text {new }}\right) \geq \mathcal{L}\left(q_{\text {old }}, \boldsymbol{\theta}_{\text {old }}\right)L(qnew ​,θnew ​)≥L(qold ​,θold ​)
​
E-Step affects KL, so lower bound has to go up.
M-Step maximizes lower bound
EM improves the marginal likelihood log⁡p(x∣θnew)≥log⁡p(x∣θold )\log p\left(\boldsymbol{x} \mid \boldsymbol{\theta}_{\mathrm{new}}\right) \geq \log p\left(\boldsymbol{x} \mid \boldsymbol{\theta}_{\text {old }}\right)logp(x∣θnew​)≥logp(x∣θold ​)
​
E-Step leaves marginal likelihood unaffected
M-Step increases, as lower bound and KL increase
What is the advantage of EM over kkk
-means?
EM is harder to learn than k-means but it also gives variances and densities
What are the advantages of PPCA over the PCA? What are its drawbacks?
PCA is a one-step solution (only eigenvalue decomposition)
PCA is very fast
PPCA is good if we need densities
PPCA helps to understand EM and complex dimensionality reduction methods.
Why do we need the Expectation step at all, if the Maximization steps, increases the likelihood?
The expectation step is necessary to estimate the distribution of the latent variables by using the old parameters and the observed data x\boldsymbol{x}x
. So we try to estimate the missing data.
In the M step the generated (complete data) is used to generate new parameter estimates for θ\boldsymbol{\theta}θ
.
If there wasn't an E-Step it just wouldn't be possible.
Kernel methods
What is the definition of a kernel and its relation to an underlying feature space?🧠
Let ϕ:X→Rd\phi: \mathcal{X} \rightarrow \mathbb{R}^{d}ϕ:X→Rd
 be an arbitrary feature function, then k(x,x′)=⟨ϕ(x),ϕ(x′)⟩k\left(\boldsymbol{x}, \boldsymbol{x}^{\prime}\right)=\left\langle\phi(\boldsymbol{x}), \boldsymbol{\phi}\left(\boldsymbol{x}^{\prime}\right)\right\ranglek(x,x′)=⟨ϕ(x),ϕ(x′)⟩
 defines a positive definite kernel.
Why are kernels more powerful than traditional feature-based methods?🧠
Traditional feature-based methods require working in the higher-dimensional feature space, while kernel-based methods do not.
Especially, with kernels we can map data $x$ to an infinite dimensional feature space. These features never have to be represented explicitly, as long as we can evaluate the inner product of two feature vectors.
Leads to more powerful representations than traditional feature models.
What do we mean by the kernel trick?🧠
Kernel methods allow to calculate the dot product in a high-dimensional feature space without ever computing the mapping ϕ\phiϕ
 of the data in that space. Instead of applying the transformations of ϕ(x)\phi (x)ϕ(x)
explicitly, the computation is done in the lower-dimensional feature space by replacing the inner product with a function.
How do we apply the kernel trick to ridge regression?🧠
The ridge solution is given by: wridge ∗=(ΦTΦ+λI)−1⏟d×d matrix inversion ΦTy\boldsymbol{w}_{\text {ridge }}^{*}=\underbrace{\left(\Phi^{T} \Phi+\lambda \boldsymbol{I}\right)^{-1}}_{d \times d \text { matrix inversion }} \boldsymbol{\Phi}^{T} \boldsymbol{y}wridge ∗​=d×d matrix inversion (ΦTΦ+λI)−1​​ΦTy
​
By applying the "searle set of identies" ( (I+AB)−1A=A(I+BA)−1)(\boldsymbol{I}+\boldsymbol{A} \boldsymbol{B})^{-1} \boldsymbol{A}=\boldsymbol{A}(\boldsymbol{I}+\boldsymbol{B} \boldsymbol{A})^{-1})(I+AB)−1A=A(I+BA)−1)
 we get:
​w∗=(ΦTΦ+λI)−1⏟d×d matrix inversion ΦTy=ΦT(ΦΦT+λI)−1⏟N×N matrix inversion y\boldsymbol{w}^{*}=\underbrace{\left(\boldsymbol{\Phi}^{T} \boldsymbol{\Phi}+\lambda \boldsymbol{I}\right)^{-1}}_{d \times d \text { matrix inversion }} \boldsymbol{\Phi}^{T} \boldsymbol{y}=\boldsymbol{\Phi}^{T} \underbrace{\left(\Phi \Phi^{T}+\lambda \boldsymbol{I}\right)^{-1}}_{N \times N \text { matrix inversion }} \boldsymbol{y}w∗=d×d matrix inversion (ΦTΦ+λI)−1​​ΦTy=ΦTN×N matrix inversion (ΦΦT+λI)−1​​y
​
The kernelized version is then given by: w∗=ΦT(K+λI)−1y⏟α=ΦTα\boldsymbol{w}^{*}=\boldsymbol{\Phi}^{T} \underbrace{(\boldsymbol{K}+\lambda \boldsymbol{I})^{-1} \boldsymbol{y}}_{\alpha}=\mathbf{\Phi}^{T} \boldsymbol{\alpha}w∗=ΦTα(K+λI)−1y​​=ΦTα
​
How do we compute with infinite dimensional vectors?🧠
Instead of inverting a d×dd \times dd×d
 matrix, we invert a N×NN \times NN×N
 matrix, which is beneficial if ddd
 is infinite dimensional.
Still, w∗∈Rd\boldsymbol{w}^{*} \in \mathbb{R}^{d}w∗∈Rd
 is potentially infinite dimensional and can not be represented. However, we can evaluate a function fff
 that is specified by w∗\boldsymbol{w}^{*}w∗
:
f(x)=ϕ(x)Tw∗=fϕ(x)TΦTα=k(x)Tα=∑iαik(xi,x)f(\boldsymbol{x})=\boldsymbol{\phi}(\boldsymbol{x})^{T} \boldsymbol{w}^{*}=f \boldsymbol{\phi}(\boldsymbol{x})^{T} \boldsymbol{\Phi}^{T} \boldsymbol{\alpha}=\boldsymbol{k}(\boldsymbol{x})^{T} \boldsymbol{\alpha}=\sum_{i} \alpha_{i} k\left(\boldsymbol{x}_{i}, \boldsymbol{x}\right)f(x)=ϕ(x)Tw∗=fϕ(x)TΦTα=k(x)Tα=i∑​αi​k(xi​,x)
with the kernel vector k(x∗)=[k(x1,x∗)⋮k(xN,x∗)]=[(ϕ(x1)Tϕ(x∗)⋮(xN)Tϕ(x∗)]=ΦXϕ(x∗)\boldsymbol{k}\left(\boldsymbol{x}^{*}\right)=\left[\begin{array}{c}k\left(\boldsymbol{x}_{1}, \boldsymbol{x}^{*}\right) \\ \vdots \\ k\left(\boldsymbol{x}_{N}, \boldsymbol{x}^{*}\right)\end{array}\right]=\left[\begin{array}{c}\left(\phi\left(\boldsymbol{x}_{1}\right)^{T} \phi\left(x^{*}\right)\right. \\ \vdots\left(\boldsymbol{x}_{N}\right)^{T} \phi\left(x^{*}\right)\end{array}\right]=\boldsymbol{\Phi}_{X} \boldsymbol{\phi}\left(\boldsymbol{x}^{*}\right)k(x∗)=⎣⎡​k(x1​,x∗)⋮k(xN​,x∗)​⎦⎤​=⎣⎡​(ϕ(x1​)Tϕ(x∗)⋮(xN​)Tϕ(x∗)​⎦⎤​=ΦX​ϕ(x∗)
.
What are the hyper-parameters of a kernel and how can we optimize them?🧠
For the RBF kernel the bandwidth σ\sigmaσ
 is a hyper-parameter. Choosing it is a model-selection problem, that can be solved via cross-validation.
Study the kernel properties where is symmetry relevant? Where and why is positive definiteness of matrix important?
Inner products are symmetric and strictly positive definite. (see here.) Thus, a function substituting the product aka kernel has to fulfil the same properties.
What is the impact of changing σ\sigmaσ
 in an RBF kernel?
Recall the RBF kernel is given by k(x,y)=exp⁡(−∥x−y∥22σ2)k(\boldsymbol{x}, \boldsymbol{y})=\exp \left(-\frac{\|\boldsymbol{x}-\boldsymbol{y}\|^{2}}{2 \sigma^{2}}\right)k(x,y)=exp(−2σ2∥x−y∥2​)
.
If the distance between x−y\boldsymbol{x}- \boldsymbol{y}x−y
is large, exp⁡\expexp
will be small, this means training observations x\boldsymbol{x}x
will hardly play any role in the prediction of test observation y\boldsymbol{y}y
.
The σ\sigmaσ
now controls the width of the neighbourhood or the variance of the Gaussian density.
What is the actual gain from using polynomial kernels?
By using a polynomial kernel with d>1d>1d>1
one gets a more flexible decision boundary. This is comparable to fitting e. g. a classifier in a higher dimensional feature space.
What is the purpose of the kernel matrix?
A kernel matrix is built by evaluating the kernel on all pairs and any set inputs. So it stores the similarities of all samples.
​[K]ij=ϕ(xi)Tϕ(xj)=k(xi,xj)[\boldsymbol{K}]_{i j}=\boldsymbol{\phi}\left(\boldsymbol{x}_{i}\right)^{T} \boldsymbol{\phi}\left(\boldsymbol{x}_{j}\right)=k\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)[K]ij​=ϕ(xi​)Tϕ(xj​)=k(xi​,xj​)
​
Proof that a positive definite Kernel is symmetric.
​k(x,x′)=⟨ϕ(x),ϕ(x′)⟩=⟨ϕ(x′),ϕ(x)⟩=k(x′,x)k\left(\boldsymbol{x}, \boldsymbol{x}^{\prime}\right)=\left\langle\boldsymbol{\phi}(\boldsymbol{x}), \boldsymbol{\phi}\left(\boldsymbol{x}^{\prime}\right)\right\rangle = \left\langle\boldsymbol{\phi}(\boldsymbol{x}^{\prime}), \boldsymbol{\phi}\left(\boldsymbol{x}\right)\right\rangle = k\left(\boldsymbol{x}^{\prime}, \boldsymbol{x}\right)k(x,x′)=⟨ϕ(x),ϕ(x′)⟩=⟨ϕ(x′),ϕ(x)⟩=k(x′,x)
​
Proof that the Euclidean distance is a distance measure fulfilling all criteria for a distance measure.
SVMs
Why is it good to use a maximum margin objective for classification?🧠
The maximum margin objective is good for classification, as it tries to find the hyperplane that gives the greatest minimum distance to the closest observations.
The intuition is, that if less observations next to the decision boundary, the results are less uncertain.
How can we define the margin as an optimization problem?
It can be formulated as:
​argmax⁡w2∥w∥, s.t. wTxi+b{≥+1, falls yi=+1≤−1, falls yi=−1\begin{aligned} \operatorname{argmax}_{\mathbf{w}} & \frac{2}{\|\mathbf{w}\|}, \\ \text { s.t. } & \mathbf{w}^{T} \mathbf{x}_{i}+b\left\{\begin{array}{l} \geq+1, \quad \text { falls } y_{i}=+1 \\ \leq-1, \quad \text { falls } y_{i}=-1 \end{array}\right. \end{aligned}argmaxw​ s.t. ​∥w∥2​,wTxi​+b{≥+1, falls yi​=+1≤−1, falls yi​=−1​​
​
What are slack variables and how can they be used to get a 'soft' margin?🧠
A ''soft' margin is the concept of a hyperplane, where almost all observations are separated correctly. This is done through so called slack variables ξi\xi_iξi​
, that allow violating the margin. We use slack variables ξi≥0\xi_i \geq 0ξi​≥0
 and allow for margin violations: yi(wTxi+b)≥1−ξiy_{i}\left(\mathbf{w}^{T} \mathbf{x}_{i}+b\right) \geq 1-\xi_{i}yi​(wTxi​+b)≥1−ξi​
.
How is the hinge loss defined?🧠
​argmin⁡wλ∥w∥2⏟regularization +∑i=1Nmax⁡(0,1−yif(xi))⏟data loss , with λ=1C\operatorname{argmin}_{\mathbf{w}} \lambda \underbrace{\|\mathbf{w}\|^{2}}_{\text {regularization }}+\underbrace{\sum_{i=1}^{N} \max \left(0,1-y_{i} f\left(\boldsymbol{x}_{i}\right)\right)}_{\text {data loss }}, \quad \text { with } \lambda=\frac{1}{C}argminw​λregularization ∥w∥2​​+data loss i=1∑N​max(0,1−yi​f(xi​))​​, with λ=C1​
​
What is the relation between the slack variables and the hinge loss?🧠
If ξi\xi_iξi​
is >1>1>1
, the point lies outside the margin, but doesn't contribute to the loss.
If ξi\xi_iξi​
is 0≤ξi≤10 \leq \xi_{i} \leq 10≤ξi​≤1
, it violates the margin and contributes to the loss.
If ξi\xi_iξi​
is 000
, it's a support vector.
What are advantages and disadvantages in comparison to logistic regression?🧠
Logistic regression doesn't allow for margin valuations. SVMs however, allow some observations to lie on the wrong side of the margin through the notion of slack variables.
Logistic regression returns probabilities. SVMs do not.
Logistic regression is more sensitive to outliers, whereas SVMs find a more balanced decision boundary.
What is the difference between gradients and sub-gradients?🧠
In order to calculate the gradient of a function, the function has to be differentiable.
To calculate sub-gradients the function has to be convex, but not necessarily differentiable.