$\newcommand{\Reals}{\mathbb{R}} \newcommand{\Nats}{\mathbb{N}} \newcommand{\PDK}{{k}} \newcommand{\IS}{\mathcal{X}} \newcommand{\FM}{\Phi} \newcommand{\Gram}{G} \newcommand{\RKHS}{\mathcal{H}} \newcommand{\prodDot}[2]{\left\langle#1,#2\right\rangle} \DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max}$

Tutorial on modern kernel methods

Ingmar Schuster

(Zalando Research)

Overview¶

• Introduction
• Feature engineering and two simple classification algorithms
• Kernels and feature space
• Applications
  • mean embedding, conditional mean embedding and operators
  • Training GANs
  • Regression with uncertainty estimates
• Conclusion and outlook

Introduction¶

Kernel methods¶

• Support Vector Machines (SVMs) are a staple for classification
• Gaussian Processes (GPs) very popular for regression
• kernel mean embedding of distributions/conditional distributions
• recent techniques for representation learning/unsupervised learning
  • Deep Gaussian Processes
  • Compositional Kernel Machines
• very elegant mathematics

Gaussian Processes¶

• model for functions/continuous output
• for new input returns predicted output and uncertainty

Support Vector Machines¶

• model for classification
• map data nonlinearly to higher dimensionsal space
• separate points of different classes using a plane (i.e. linearly)

Feature engineering and two classification algorithms¶

Feature engineering in Machine Learning¶

• feature engineering: map data to features with function $\FM:\IS\to \RKHS$
  • handle nonlinear relations with linear methods ($\FM$ nonlinear)
  • handle non-numerical data (e.g. text)

Working in Feature Space¶

• want Feature Space $\RKHS$ (the codomain of $\FM$) to be vector space to get nice mathematical structure
• definition of inner products induces norms and possibility to measure angles
• can use linear algebra in $\RKHS$ to solve ML problems
  • inner products
  • angles
  • norms
  • distances
• induces nonlinear operations on the Input Space (domain of $\FM$)

Two simple classification algorithms¶

• given data points from mixture of two distributions with densities $p_0,p_1$: $$x_i \sim 0.5 p_0 + 0.5 p_1$$ and label $l_i = 0$ if $x_i$ generated by $p_0$, $l_i = 1$ otherwise

Classification using inner products in Feature Space¶

• compute mean feature space embedding $$\mu_{0} = \frac{1}{N_0} \sum_{l_i = 0} \FM(x_i) ~~~~~~~~ \mu_{1} = \frac{1}{N_1} \sum_{l_i = 1} \FM(x_i)$$
• assign test point to most similar class in terms of inner product between point and mean embedding $\prodDot{\FM(x)}{\mu_c}$ $$f_d(x) = \argmax_{c\in\{0,~1\}} \prodDot{\FM(x)}{\mu_c}$$ (remember in $\Reals^2$ canonically: $\prodDot{a}{b} = a_1 b_1+a_2 b_2 $)

Classification using density estimation¶

• estimate density for each class by centering a gaussian, taking mixture as estimate $$\widehat{p}_0 = \frac{1}{N_0} \sum_{l_i = 0} \mathcal{N}(\cdot; x_i,\Sigma) ~~~~~~~~ \widehat{p}_1 = \frac{1}{N_1} \sum_{l_i = 1} \mathcal{N}(\cdot; x_i,\Sigma)$$

Classification using density estimation¶

• estimate density for each class by centering a gaussian, taking mixture as estimate $$\widehat{p}_0 = \frac{1}{N_0} \sum_{l_i = 0} \mathcal{N}(\cdot; x_i,\Sigma) ~~~~~~~~ \widehat{p}_1 = \frac{1}{N_1} \sum_{l_i = 1} \mathcal{N}(\cdot; x_i,\Sigma)$$
• assign test point $x$ to class $c$ that gives highest value for $\widehat{p}_c(x)$
• $\widehat{p}_c$ is known as a kernel density estimate (KDE)
• different but overlapping notion of 'kernel'
• classification algorithm known as Parzen windows classification

For a certain feature map and inner product, both algorithms are the same!

Kernels and feature space¶

Positive definite functions and feature spaces¶

• let $\PDK:\IS\times\IS \to \Reals$, called a kernel
  • if $\PDK$ is a symmetric and positive semi definite (psd)
  • then there exists $\FM: \IS \to \RKHS$ to a hilbert space $\RKHS$ such that $$\PDK(x_i, x_j) = \prodDot{\FM(x_i)}{\FM(x_j)}_\RKHS$$ i.e. $\PDK$ computes inner product after mapping to some $\RKHS$

Gram matrix (1)¶

• If all matrices $$\Gram_{X}=\begin{bmatrix} \PDK(x_1, x_1) & \dots & \PDK(x_1, x_N)\\ \PDK(x_2, x_1) & \ddots & \vdots\\ \vdots & & \vdots\\ \PDK(x_N, x_1) & \dots & \PDK(x_N, x_N) \end{bmatrix}$$ are symmetric positive semidefinite, then $\PDK$ is a psd kernel
• called a gram matrix

Gram matrix (2)¶

• sometimes mixed gram matrices are needed $$\Gram_{XY} = \begin{bmatrix} \PDK(x_1, y_1) & \PDK(x_1, y_2) & \dots & \PDK(x_1, y_M)\\ \PDK(x_2, y_1) & \ddots & &\vdots\\ \vdots & & &\vdots\\ \PDK(x_N, y_1) & \dots & &\PDK(x_N, y_M) \end{bmatrix} $$

Examples of psd kernels¶

• Linear $\PDK_L(x,x') = \prodDot{x}{x'} = x_1 x'_1 + x_2 x'_2+ \dots$
• Gaussian $\PDK_G(x,x') = \exp({-{ 0.5}(x-x' )^{\top }\Sigma ^{-1}(x-x' )})$

PSD kernels¶

• easy to construct $\PDK$ given $\FM$: $\PDK(x_i, x_j) = \prodDot{\FM(x_i)}{\FM(x_j)}$
• construction for $\FM$ given $\PDK$ not trivial but still elementary
• given $\FM$ and inner product in feature space we
  • can endow space with norm induced by the inner product $$\|g\|_\RKHS = \sqrt{\prodDot{g}{g}}_\RKHS~~~\textrm{for}~g \in \RKHS$$
  • can measure angles in the new space $$\prodDot{g}{f}_\RKHS = \cos(\angle[g,f])~\|g\|_\RKHS ~\|f\|_\RKHS$$

Construction of the canonical feature map (Aronszajn map)¶

Plan

• construction of $\FM$ from $\PDK$
• definition of inner product in new space $\RKHS$ such that in fact $\PDK(x,x') = \prodDot{\FM(x)}{\FM(x)}$
• feature for each $x \in \IS$ will be a function from $\IS$ to $\Reals$ $$\FM:\IS \to \Reals^\IS$$

Canonical feature map (Aronszajn map)¶

• pick $\FM(x) = \PDK(\cdot, x)$

  • Linear kernel: $\FM_L(x) = \prodDot{\cdot}{x}$
  • Gaussian kernel: $\FM_G(x) = \exp\left(-0.5{\|\cdot -x \|^2}/{\sigma^2}\right)$.

• let linear combinations of features also be in $\RKHS$ $$f(\cdot)=\sum_{i=1}^m a_i \PDK(\cdot, x_i) \in \RKHS$$ for $a_i \in \Reals$

• $\RKHS$ a vector space over $\Reals$ : if $f(\cdot)$ and $g(\cdot)$ functions from $\IS$ to $\Reals$, so are $a~f(\cdot)$ for $a \in \Reals, f(\cdot)+g(\cdot)$

Canonical inner product (1)¶

• for $f(\cdot)=\sum_{i=1}^m a_i \PDK(\cdot, x_i) \in \RKHS$ and $g(\cdot)=\sum_{j=1}^{m'} b_j \PDK(\cdot, x'_j) \in \RKHS$ define inner product $$\prodDot{f}{g} = \sum_{i=1}^m \sum_{j=1}^{m'} b_j a_i \PDK(x'_j, x_i)$$
• In particular $\prodDot{ \PDK(\cdot,x)}{ \PDK(\cdot,x')}=\PDK(x,x')$ (reproducing property of kernel in its $\RKHS$)

Canonical inner product (2)¶

• $\RKHS$ a hilbert space with this inner product, as it is
  • positive definite
  • linear in its first argument
  • symmetric
  • complete
• $\RKHS$ called Reproducing Kernel Hilbert Space (RKHS).

Equivalence of classification algorithms¶

• Recall mean canonical feature and kernel density estimate $$\widehat{p}_0 = \frac{1}{N_0} \sum_{l_i = 0} \mathcal{N}(\cdot; x_i,\Sigma) ~~~~~~~~ \mu_{0} = \frac{1}{N_0} \sum_{l_i = 0} \PDK(\cdot, x_i)$$
• observe $$\frac{1}{N_0} \sum_{l_i = 0} \mathcal{N}(x^*; x_i,\Sigma) = \prodDot{\frac{1}{N_0} \sum_{l_i = 0} \PDK(\cdot, x_i)}{\PDK(\cdot, x^*)}$$ if $\PDK$ is Gaussian density with covariance $\Sigma$
• kernel mean and Parzen windows classification are equivalent!

Lets look at example classification output

Applications¶

Kernel mean embedding¶

• mean feature with canonical feature map $\frac{1}{N} \sum_{i = 1}^N \FM(x_i) = \frac{1}{N} \sum_{i = 1}^N \PDK(x_i, \cdot)$
• this the estimate of the kernel mean embedding of the distribution/density $\rho$ of $x_i$ $$\mu_\rho(\cdot) = \int \PDK(x,\cdot) \mathrm{d}\rho(x)$$
• using this we can define a distance between distributions $\rho, q$ as $$\mathrm{MMD}(\rho, q)^2 = \|\mu_\rho - \mu_q \|^2_\RKHS$$ called the maximum mean discrepancy (MMD)
• Has been used as the critic in generative adversial networks (i.e. generative network as usual, MMD as drop-in for discriminator)

Conditional mean embedding (1)¶

• we can define operators on RKHSs
• these are maps from RKHS elements to RKHS elements (i.e. mapping between functionals)
• one such operator is the conditional mean embedding $\mathcal{D}_{Y|X}$
  • given the embedding of the input variables distribution, returns the embedding of the output variables distribution
• Regression with uncertainty estimate

Conditional mean embedding (2)¶

An example

Conditional mean embedding (3)¶

• closed form estimate given samples from input and output $$\begin{bmatrix}\PDK_Y(y_1, \cdot),& \dots &, \PDK_Y(y_N, \cdot)\end{bmatrix} \Gram_X^{-1} \begin{bmatrix}\PDK_X(x_1, \cdot)\\ \vdots \\ \PDK_X(x_N, \cdot)\end{bmatrix}$$

• closed form estimate of output embedding for new input $x^*$

$$\prodDot{\mathcal{D}_{Y|X}}{\PDK(x^*,\cdot)} = \begin{bmatrix}\PDK_Y(y_1, \cdot),& \dots &, \PDK_Y(y_N, \cdot)\end{bmatrix} \Gram_X^{-1} \begin{bmatrix}\PDK_X(x_1, x^*)\\ \vdots \\ \PDK_X(x_N, x^*)\end{bmatrix}$$

Conditional mean embedding (4)¶

• Similar to Gaussian processes, but output distribution more flexible
  • mixture of Gaussians, Laplace, distributions on discrete objects
  • multimodality can be represented
  • multidimensional output
  • output can be combination of e.g. string and reals
• Conditional mean embedding was used to construct Kernel Bayes Rule, enabling closed form Bayesian inference
• other types of operators have been derived (see Stefan Klus' talk next week)

Conclusion and Outlook¶

Conclusion and Outlook¶

• kernels implicitly compute inner products in well-behaved vector spaces
• use angles, norms, distances in these for ML algorithms
• successful models in ML build on PSD kernels
  • kernel induced covariance structure (Gaussian Processes)
  • kernel embedding of probability distributions
    • measuring distance between distributions
  • kernel embedding of conditional probability distributions

Get slides at ingmarschuster.com