Crash course on learning theory, part 2

It might be useful to refresh your memory on the concepts we saw in part 1 (particularly the notions of VC dimension and Rademacher complexity). In this second and last part we will discuss two of the most successful algorithm paradigms in learning: boosting and SVM. Note that just like last time each topic we cover have its own books dedicated to them (see for example the boosting book by Schapire and Freund, and the SVM book by Scholkopf and Smola). Finally we conclude our short tour of the learning’s basics with a simple observation: stable algorithms generalize well.

Boosting

Say that given a distribution $D$ supported on $m$ points $(x_i, y_i)_{i \in [m]}$ one can find (efficiently) a classifier $h \in \mathcal{B}$ such that $L_{D}(h) \leq 1/2 - \gamma$ (here we are in the context of classification with the zero-one loss). Can we “boost” this weak learning algorithm into a strong learning algorithm with $L_{\mu}(A)$ arbitrarily small for $m$ large enough? It turns out that this is possible, and even simple. The idea is to build a linear combination of hypotheses in $\mathcal{B}$ with a greedy procedure. That is at time step $t-1$ our hypothesis is (the sign of) $f_{t-1} = \sum_{s=1}^{t-1} w_s h_s$ , and we are now looking to add $h_{t} \in \mathcal{B}$ with an approriate weight $w_{t} \in \mathbb{R}$ . A natural guess is to optimize over $(w_t, h_t)$ to minimize the training error of $f_t$ on our sample $(x_i, y_i)_{i \in [m]}$ . This might be a difficult computational problem (how do you optimize over $\mathcal{B}$ ?), and furthermore we would like to make use of our efficient weak learning algorithm. The key trick is that $\mathds1\{x < 0\} \leq \exp(-x)$ . More precisely:

$\begin{eqnarray*} L_{\hat{\mu}_m}(f_t) = \frac{1}{m} \sum_{i=1}^m \mathds1\{\mathrm{sign}(f_t(x_i)) \neq y_i\} & \leq & \frac{1}{m} \sum_{i=1}^m \exp( - y_i f_t(x_i) ) \; (=: Z_t / m) \\ & = & \frac{Z_{t-1}}{m} \sum_{i=1}^m D_t(i) \exp( - y_i w_t h_t(x_i) ) , \end{eqnarray*}$

where $D_t(i) = \frac{1}{Z_{t-1}} \exp(- y_i f_{t-1}(i))$ . From this we see that we would like $h_t$ to be a good predictor for the distribution $D_t$ . Thus we can pass $D_t$ to the weak learning algorithm, which in turns gives us $h_t$ with $L_{D_t}(h_t) = \epsilon_t \leq 1/2 - \gamma$ . Thus we now have:

$Z_ t = Z_{t-1} (\epsilon_t \exp(w_t) + (1-\epsilon_t) \exp(-w_t) ).$

Optimizing the above expression one finds that $w_t = \frac{1}{2} \log\left(\frac{1-\epsilon_t}{\epsilon_t}\right)$ leads to (using $\epsilon_t \leq 1/2-\gamma$ )

$Z_t \leq Z_{t-1} \exp(-2 \gamma^2) \leq m \exp(-2 \gamma^2 t) .$

The procedure we just described is called AdaBoost (introduce by Schapire and Freund) and we proved that it satisfies

(1) $\begin{equation*} L_{\hat{\mu}_m}(f_t) \leq \exp(- 2 \gamma^2 t) . \end{equation*}$

In particular we see that our weak learner assumption implies that $\hat{\mu}_m$ is realizable (and in fact realizable with margin $\gamma$ , see next section for the definition of margin) with the hypothesis class:

$\mathcal{H} = \left\{ \mathrm{sign} \left( \sum_{t \in \mathbb{N}} w_t h_t(\cdot) \right) : \forall t \in \mathbb{N}, w_t \in \mathbb{R}, h_t \in \mathcal{B} \right\} .$

This class can be thought of as a neural network with one (infinite size) hidden layer. To realize how expressive $\mathcal{H}$ is compared to $\mathcal{B}$ it’s a useful exercise to think about the very basic case of decision stumps (for which the empirical risk minimization can be implemented very efficiently):

$\mathcal{B} = \{x \mapsto \mathrm{sign}(\theta - x_i), i \in [n], \theta \in \mathbb{R}\} .$

To derive a bound on the true risk $L_{\mu}(f_t)$ of AdaBoost it remains to calculate the VC dimension of the class $\mathcal{H}_t$ where the size of the hidden layer is $t$ . This follows from more general results on the VC dimension of neural networks, and up to logarithmic factors one obtains that $\mathrm{VC}(\mathcal{H}_t)$ is of order $t \times \mathrm{VC}(\mathcal{B})$ . Putting this together with \eqref{eq:empada} we see that when $\gamma$ is a constant, one should run AdaBoost for $t=\Theta(\log(m))$ rounds, and then one gets $L_{\mu}(f_t) \lesssim \sqrt{\frac{\mathrm{VC}(\mathcal{B})}{m}}$ .

Margin

We consider $\mathcal{D}$ to be the set of distributions $\mu$ such that there exists $w^*$ with $\mathbb{P}_{\mu}(Y \langle w^{*} , X \rangle > 0) =1$ (again we are in the context of classification with the zero-one loss, and this assumption means that the data is almost surely realizable). The SVM idea is to search for $w$ with minimal Euclidean norm and such that $Y_i \langle w , X_i \rangle \geq 1, \forall i \in [m]$ . Effectively this is doing empirical risk minimization over the following data dependent hypothesis class (which we write in terms of the set of admissible weight vectors):

$\mathcal{W}_S = \{w \in \mathbb{R}^n : Y_i \langle w , X_i \rangle \geq 1, \forall i \in [m] \; \text{and} \; |w| \leq |w^*|\} .$

The key point is that we can now use the contraction lemma to bound the Rademacher complexity of this class. Indeed replacing the zero-one loss $\mathds1\{\mathrm{sign}(\langle w, x\rangle) \neq y\}$ by the (Lipschitz!) “ramp loss” $\min(1,\max(0,1-y\langle w , x \rangle))$ makes no difference for the optimum $w^*$ , and our estimated weight still has $0$ training error while its true loss is only surestimated. Using the argument from previous sections we see that the Rademacher complexity of our hypothesis class (with respect to the ramp loss) is bounded by $2 |w^*| / \sqrt{m}$ (assuming the examples $X_i$ are normalized to be in the Euclidean ball). Now it is easy to see that the existence of $w^*$ with $|w^*| \leq 1/\gamma$ (and $\mathbb{P}_{\mu}(Y \langle w^{*} , X \rangle \geq 1) =1$ ) exactly corresponds to a geometric margin of $\gamma$ between positive and negative examples (indeed the margin is exactly $\min_i y_i \langle \frac{w^*}{|w^*|} , x \rangle$ ). To summarize we just saw that under the $\gamma$ -margin condition the SVM algorithm has a sample complexity of order $1/ (\gamma \epsilon)^2$ . This suggests that from an estimation perspective one should map the points into a high-dimensional space so that one could hope to have the separability condition (with margin). However this raises computational challenges, as the QP given by the SVM can suddenly look daunting. This is where kernels come into the picture.

Kernels

So let’s go overboard and map the points to an infinite dimensional Hilbert space $\mathcal{H}$ (as we will see in the next subsection this notation will be consistent with $\mathcal{H}$ being the hypothesis class). Denote $\psi$ for this map, and let $K(x,x') = \langle \psi(x), \psi(x') \rangle_{\mathcal{H}}$ be the kernel associated with it. The key point is that we are not using all the dimensions of our Hilbert space in the SVM optimization problem, but rather we are effectively working in the subspace spanned by $\psi(x_1), \hdots, \psi(x_m)$ (this is because we are only working with inner products with those vectors, and we are trying to minimize the norm of the resulting vector). Thus we can restrict our search to $w=\sum_{i=1}^m \alpha_i \psi(x_i)$ (this fact is called Mercer representer theorem and the previous sentence is the proof…). The beauty is that now we only need to compute the Gram matrix $(K(x_i, x_j))_{i, j \in [m]}$ as we only need to consider $\langle w, \psi(x_i)\rangle = \sum_{j=1}^m \alpha_j K(x_j, x_i)$ and $|w|^2 = \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i, x_j)$ . In particular we never need to compute the points $\psi(x_i)$ (which anyway could be infinite dimensional, so we couldn’t really write them down…). Note that the same trick would work with soft SVM (i.e., regularized hinge loss). To drive the point home let’s see an example: $\psi(x) = (\prod_{i \in J} x_i)_{J \subset [n], |J| =k}$ leads to $K(x,x') = (\langle x, x'\rangle)^k$ . I guess it doesn’t get much better than this :). Despite all this beauty, one should note that we now have to manipulate an object of size $m^2$ (the kernel matrix $(K(x_i,x_j))$ ) and in our big data days this can be a disaster. We really want to focus on methods with computational complexity linear in $m$ , and thus one is led to the problem of kernel approximation, which we will explore below. But first let us explore a bit further what kernel SVM is really doing.

RKHS and the inductive bias of kernels

As we just saw in kernel methods the true central element is the kernel $K$ rather than the embedding $\psi$ . In particular since the only thing that matter are inner products $\langle \psi(x), \psi(x') \rangle_{\mathcal{H}}$ we might as well assume that $\psi(x) := K(x,\cdot)$ , and $\mathcal{H}$ is the completion of $\mathrm{Span}(K(x, \cdot), x \in \mathcal{X})$ where the inner product is defined by $\langle K(x, \cdot), K(x', \cdot) \rangle_{\mathcal{H}} = K(x,x')$ (and the definition is extended to $\mathcal{H}$ by linearity). Assuming that $K$ is positive definite (that is Gram matrices built from $K$ are positive definite) one obtains a well-defined Hilbert space $\mathcal{H}$ . Furthermore this Hilbert space has a special property: for any $f \in \mathcal{H}, x \in \mathcal{X}$ , $f(x) = \langle f, K(x, \cdot) \rangle_{\mathcal{H}}$ . In other words $\mathcal{H}$ is a reproducing kernel Hilbert space (RKHS), and in fact any RKHS can be obtained with the above construction (this is a simple consequence of Riesz representation theorem). Now observe that we can rewrite the kernel SVM problem

$\begin{align*} & \mathrm{min}. \; \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i,x_j) \\ & \text{s.t.} \; \alpha \in \mathbb{R}^m \; \text{and} \; \forall j \in [m], y_j \sum_{i=1}^m \alpha_i K(x_i, x_j) \geq 1 , \end{align*}$

$\begin{align*} & \mathrm{min}. \; \|f\|_{\mathcal{H}} \\ & \text{s.t.} \; f \in \mathcal{H} \; \text{and} \; \forall j \in [m], y_j f(x_j) \geq 1 . \end{align*}$

While the first formulation is computationally more effective, the second sheds light on what we are really doing: simply searching the consistent (with margin) hypothesis in $\mathcal{H}$ with smallest norm. In other words, thinking in terms of inductive bias, one should choose a kernel for which the norm $\|\cdot\|_{\mathcal{H}}$ represents the kind of smoothness one expects in the mapping from input to output (more on that next).

It should also be clear now that one can “kernelize” any regularized empirical risk minimization, that is instead of the boring (note that here the loss $\ell$ is defined on $\mathcal{Y} \times \mathbb{R}$ instead of $\mathcal{Y} \times \mathcal{Y}$ )

$\min_{w \in \mathbb{R}^n}. \; \frac1{m} \sum_{i=1}^m \ell(y_i, \langle w, x_i \rangle) + \lambda |w|^2 ,$

one can consider the much more exciting

$\min_{f \in \mathcal{H}}. \; \frac1{m} \sum_{i=1}^m \ell(y_i, f(x_i)) + \lambda \|f\|_{\mathcal{H}}^2 ,$

since this can be equivalently written as

$\min_{\alpha \in \mathbb{R}^m}. \; \frac1{m} \sum_{i=1}^m \ell\left(y_i, \sum_{j=1}^m \alpha_j K(x_j, x_i)\right) + \lambda \sum_{i,j=1}^m \alpha_i \alpha_j K(x_i,x_j) .$

This gives the kernel ridge regression, kernel logistic regression, etc…

Translation invariant kernels and low-pass filtering

We will now investigate a bit further the RKHS that one obtains with translation invariant kernels, that is $K(x,x')=k(x-x')$ . A beautiful theorem of Bochner characterizes the continuous maps $k: \mathbb{R}^n \rightarrow \mathbb{R}$ (with $k(0)=1$ ) for which such a $K$ is a positive definite kernel: it is necessary and sufficient that $k$ is the characteristic function of a probability measure $\mu$ , that is

$k(x) = \int_{\mathbb{R}^n} \exp(i \langle \omega, x \rangle ) d\mu(\omega) .$

An important example in practice is the Gaussian kernel: $K(x,x')=\exp\left( - \frac{|x-x'|^2}{2 \sigma^2}\right)$ (this corresponds to mapping $x$ to the function $\exp\left( - \frac{|x- \cdot |^2}{2 \sigma^2}\right)$ ). One can check that in this case $\mu$ is itself a Gaussian (centered and with covariance $\sigma^{-2} \mathrm{I}_n$ ).

Now let us restrict our attention to the case where $\mu$ has a density $h$ with respect to the Lebesgue measure, that is $\frac{d\mu}{d\omega}=h$ . A standard calculation then shows that

$K(x,x')= \frac{1}{(2\pi)^{n}} \int_{\mathbb{R}^n} \frac{\widehat{K(x, \cdot)}(\omega)\overline{\widehat{K(x, \cdot)}(\omega)}}{h(\omega)} d\omega ,$

which implies in particular

$\| f \|_{\mathcal{H}} = \frac{1}{(2\pi)^{\frac{n}{2}}} \int_{\mathbb{R}^n} \frac{|\widehat{f}(\omega)|^2}{h(\omega)} d\omega .$

Note that for the Gaussian kernel one has $h(\omega)^{-1} \propto \exp\left(\frac{\sigma^2 |\omega|^2}{2}\right)$ , that is the high frequency in $f$ are severely penalized in the RKHS norm. Also note that smaller values of $\sigma$ correspond to less regularization, which is what one would have expected from the feature map representation (indeed the features $\exp\left( - \frac{|x- \cdot |^2}{2 \sigma^2}\right)$ are more localized around the data point $x$ for larger values of $\sigma$ ).

To summarize, SVM with translation invariant kernels correspond to some kind of soft low-pass filtering, where the exact form of the penalization for higher frequency depends on the specific kernel being used (smoother kernels lead to more penalization).

Random features

Let us now come back to computational issues. As we pointed out before, the vanilla kernel method has at least a quadratic cost in the number of data points. A common approach to reduce this cost is to use a low rank approximation of the Gram matrix (indeed thanks to the i.i.d. assumption there is presumably a lot of redundancy in the Gram matrix), or to resort to online algorithms (see for example the forgetron of Dekel, Shalev-Shwartz and Singer). Another idea is to approximate the feature map itself (a priori this doesn’t sound like a good idea, since as we explained above the beauty of kernels is that we avoid computing this feature map). We now describe an elegant and powerful approximation of the feature map (for translation invariant kernels) proposed by Rahimi and Recht which is based on random features.

Let $K$ be a translation invariant kernel and $\mu$ its corresponding probability measure. Let’s rewrite $K$ in a convenient form, using $\cos(\theta-\theta') = \frac{1}{\pi} \int_{0}^{\pi} 2 \cos(\theta + \phi) \cos(\theta'+\phi) d\phi$ and Bochner’s theorem,

$K(x,x') = \mathbb{E}_{\omega \sim \mu} \cos(\langle \omega, x-x' \rangle) = 2 \mathbb{E}_{\omega \sim \mu, \phi \sim \mathrm{unif}([0,\pi])} \cos(\langle \omega, x \rangle + \phi) \cos(\langle \omega, x' \rangle + \phi).$

A simple idea is thus to build the following random feature map: given $\omega_1, \hdots, \omega_d$ and $\phi_1, \hdots, \phi_d$ , i.i.d. draws from respectively $\mu$ and $\mathrm{unif}([0, \pi])$ , let $\Psi: \mathbb{R}^n \rightarrow \mathbb{R}^d$ be defined by $\Psi(x)=(\Psi_1(x), \hdots, \Psi_d(x))$ where

$\Psi_i(x) = \sqrt{\frac{2}{d}} \cos(\langle \omega_i, x \rangle + \phi_i) .$

For $d \gtrsim n / \epsilon^2$ it is an easy exercise to verify that with probability at least $1-\epsilon$ (provided $\mu$ has a second moment at most polynomial in $n$ ) one will have for any $x, x'$ in some compact set (with diameter at most polynomial in $n$ ),

$|K(x,x') - \langle \Psi(x), \Psi(x') \rangle | \leq \epsilon .$

The SVM problem can now be approximated by:

$\begin{align*} & \mathrm{min}. \; |w| \\ & \text{s.t.} \; w \in \mathbb{R}^d \; \text{and} \; y_j \langle w, \Psi(x_j) \geq 1 , \forall j \in [m]. \end{align*}$

This optimization problem is potentially much simpler than the vanilla kernel SVM when $m$ is much bigger than $n$ (essentially $n$ replaces $m$ for most computational aspects of the problem, including space/time complexity of prediction after training).

Stability

We conclude our tour of the basic topics in statistical learning with a different point of view on generalization that was put forward by Bousquet and Elisseeff.

Let’s start with a simple observation. Let $S'=(Z_1', \hdots, Z_m')$ be an independent copy of $S$ , and denote $S^i = (Z_1, \hdots, Z_{i-1}, Z_i', Z_{i+1}, \hdots, Z_m)$ . Then one can write, using the slight abuse of notation $\ell(h, (x,y)) :=\ell(h(x), y)$ ,

$\begin{eqnarray*} \mathbb{E}_S (L_{\mu}(A(S)) - L_{\hat{\mu}_m}(A(S))) & = & \mathbb{E}_{S, S', i \sim \mathrm{unif}([m])} (\ell(A(S), Z_i') - \ell(A(S), Z_i)) \\ & = & \mathbb{E}_{S, S', i \sim \mathrm{unif}([m])} (\ell(A(S^i), Z_i) - \ell(A(S), Z_i)) . \end{eqnarray*}$

This last quantity can be interpreted as a stability notion, and we see that controlling it would in turn control how different is the true risk compared to the empirical risk. Thus stable methods generalize.

We will now show that regularization can be interpreted as a stabilizer. Precisely we show that

$w(S) \in \argmin_{w \in \mathbb{R}} L_{\hat{\mu}_m}(h_w) + \lambda |w|^2 ,$

is $2 / (\lambda m)$ -stable for a convex and $1$ -Lipschitz loss. Denote $f_S(w)$ for the above objective function, then one has

$f_S(w) - f_S(w') = f_{S^i}(w) - f_{S^i}(w') + \frac{\ell(h_w, Z_i) - \ell(h_{w'}, Z_i)}{m} + \frac{\ell(h_{w'}, Z_i') - \ell(h_{w}, Z_i')}{m} ,$

and thus by Lipschitzness

$\begin{eqnarray*} f_S(w(S^i))-f_S(w(S)) & \leq & \frac{\ell(h_{w(S^i)}, Z_i) - \ell(h_{w(S)}, Z_i)}{m} + \frac{\ell(h_{w(S)}, Z_i') - \ell(h_{w(S^i)}, Z_i')}{m} \\ & \leq & \frac{2}{m} |w(S) - w(S^i)| . \end{eqnarray*}$

On the other hand by strong convexity one has

$f_S(w) - f_S(w(S)) \geq \lambda |w-w(S)|^2 ,$

and thus with the above we get $|w(S) - w(S^i)| \leq 2 / (\lambda m)$ which implies (by Lipschitzness)

$\ell(h_{w(S^i)}, Z_i) - \ell(h_{w(S)}, Z_i) \leq \frac{2}{\lambda m} ,$

or in other words regularized empirical risk minimization ( $\mathrm{R-ERM}$ ) is stable. In particular denoting $w^*$ for the minimizer of $w \mapsto L_{\mu}(h_w)$ we have:

$\begin{eqnarray*} L_{\mu}(\mathrm{R-ERM}) & \leq & \mathbb{E}_S L_{\hat{\mu}_m}(\mathrm{R-ERM}) + \frac{2}{\lambda m} \\ & \leq & \mathbb{E}_S L_{\hat{\mu}_m}(w^*) + \lambda |w^*| + \frac{2}{\lambda m} \\ & = & L_{\mu}(w^*) + \lambda |w^*| + \frac{2}{\lambda m} . \end{eqnarray*}$

Assuming $|w^*| \leq 1$ and optimizing over $\lambda$ we recover the bound we obtained previously via Rademacher complexity.

Crash course on learning theory, part 2

Leave a reply

Archives

Categories

Recent Posts

Subscribe to Blog via Email

Meta

Blogroll