SMO: Optimisation without Gram Matrix Inversion

Sequential Matrix Optimisation

Unlike other optimisation algorithm that utilise gradients and require inversion of the Gram matrix, SMO breaks the optimisation into a sequence of analytically solvable 2-dimensional subproblems also known as decomposition method. This approach eliminates the need for computationally expensive matrix operations. A direct competitor to this could be the interior point methods, that also solves the dual, that has nice theories but it is difficult to implement and uses a lot of memory.

Problem Setup

For the sake of simplicity our problem can be a simple SVM with a Gaussian kernel.

$$K(x_k,x_l)=exp(-\frac{||x_k-x_l||}{2{\sigma }^2})$$

The dual form, derived from setting up the Lagrangian, is shown below:

$$\begin{array}{rl}\underset{\alpha \in {\mathbb{R}}^n}{max}\sum _{i=1}^m{\alpha }_k-\frac{1}{2}\sum _{k=1}^m& \sum _{l=1}^m{\alpha }_k{\alpha }_l{y}_k{y}_{l}K(x_k,x_l)\\ \text{ subject to }0\le {\alpha }_k& \le C\text{ for all k=1,...,m }\\ \sum _{k=1}^m& {\alpha }_k{y}_k=0\end{array}$$

Algorithm

SMO solves the dual problem without matrix inversion by selecting two Lagrange multipliers at a time and solving a reduced QP over that pair. Much of the important part of the algorithm depends on what heuristics is used to select the pair or the working set. There are other heuristiscs from the literature but our case we focus on the heuristics that select the maximal violating pairs where the pair is selected as the one that maximise the violation of the KKT conditions. But first the simplified version, the version where the working pair is selected at random at each iteration is described.

At each iteration, SMO selects a working pair of Lagrange multipliers $({\alpha }_i,{\alpha }_j)$ and holds all other variables fixed. For now the simplified is that you select ${\alpha }_i$ through a iteration loop and sample its pair ${\alpha }_j$ randomly. Recall the dual problem’s equality constraint from our formulation:

$$\sum _{k=1}^m{y}_k{\alpha }_k=0$$

implies that the updates to $({\alpha }_i$\) and $({\alpha }_j)$ must lie along a line of the form:

$$y_i{\alpha }_i+y_j{\alpha }_j=\zeta ,$$

for some constant $(\zeta )$. For clarity this comes from the equality constraint and $\zeta$ is just the rest that is kept fixed as follows:

$$\begin{array}{rl}{y}_i{\alpha }_i+y_j{\alpha }_j& +\sum _{k\ne i,j}{\alpha }_k{y}_k=0\\ y_i{\alpha }_i+y_j{\alpha }_j& =-\sum _{k\ne i,j}{\alpha }_k{y}_k\\ & =\zeta \end{array}$$

Reduced Subproblem

The optimisation over the selected pair reduces to a constrained quadratic minimisation. Here we fixed ${\alpha }_i$ and reduce the problem to one dimension constrained optimisation over ${\alpha }_j$, with ${\alpha }_i$ adjusted according to maintain feasibility.: $$\underset{{\alpha }_j\in [L,H]}{min}\frac{1}{2}\eta {\alpha }_j^2+G{\alpha }_j+\text{const},$$ where:

• $\eta =K(x_i,x_i)+K(x_j,x_j)-2K(x_i,x_j)$ is the second derivative of the reduced objective (1)

• $G$ depends on prediction errors ($G=y_j(E_i-E_j)$) where $(E_k = f(x_k) - y_k$ and $f(x_t)=\sum _{k\ne i,j}{\alpha }_k{y}_{k}K(x_k,x_t)+b+{\alpha }_i{y}_{i}K(x_i,x_t)+{\alpha }_j{y}_{j}K(x_j,x_t)$ (2)

• (L, H) are bounds derived from box constraints and the equality constraint (3)

• The solution is clipped to the interval ([L, H]) (4)

After solving for $({\alpha }_2$, ${\alpha }_1$ is updated to maintain the constraint $(y_1{\alpha }_1+y_2{\alpha }_2=\zeta )$.

(1) and (2)

The result is by substituting $y_i{\alpha }_i+y_j{\alpha }_j=\zeta$ and rearrange it to be ${\alpha }_i=\frac{\zeta -{\alpha }_j{y}_j}{y_i}$ then subtitute into the dual objective function with ${\alpha }_i$.

$$\begin{array}{rl}& {\alpha }_i+{\alpha }_j-\frac{1}{2}({\alpha }_i^{2}K(x_i,x_i)+{\alpha }_j^{2}K(x_j,x_j)+2{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j))\\ & -\sum _{\begin{array}{c}k=1\\ k\ne i,j\end{array}}^n{\alpha }_k{y}_k({\alpha }_i{y}_{i}K(x_i,x_k)+{\alpha }_j{y}_{j}K(x_j,x_k))+\mathrm{const}.\end{array}$$

The full derivation with different notation can be seen in Platt’s paper. But it is just expanding and algebra and after you will get the following linear and quadratic term. Here we drop everything that is not dependent on ${\alpha }_j$ as $const$

$$\begin{array}{c}\underset{\text{Linear Term}}{\underbrace{{\alpha }_j[(1-\frac{y_j}{y_i})+\zeta y_j(K(x_i,x_i)-K(x_i,x_j))+y_j\sum _{k\ne i,j}{\alpha }_k{y}_k(K(x_i,x_k)-K(x_j,x_k))]}}\\ +\\ \underset{\text{Quadratic Term}}{\underbrace{-\frac{1}{2}(K(x_i,x_i)+K(x_j,x_j)-2K(x_i,x_j)){\alpha }_j^2}}\end{array}$$

The linear coefficient $G$ is $[(1-\frac{y_j}{y_i})+\zeta y_j(K(x_i,x_i)-K(x_i,x_j))+y_j\sum _{k\ne i,j}{\alpha }_k{y}_k(K(x_i,x_k)-K(x_j,x_k))]$, however this value in SMO literature is often derived using the form $y_j(E_i-E_j)$.

(3)

The bound $[L,H]$ here just comes from our box constraint in our original formulation $0\le {\alpha }_j\le C$:

• $y_i=y_j,$ $L=max(0,{\alpha }_i+{\alpha }_j-C)$ and $H=min(C,{\alpha }_i+{\alpha }_j)$
• $y_i\ne y_j,$ $L=max(0,{\alpha }_i-{\alpha }_j)$ and $H=min(C,C+{\alpha }_j+{\alpha }_i)$

(4)

The analytical update is as follows:

The unbounded update for ${\alpha }_j$ is:

$${\alpha }_j^{\text{new}}={\alpha }_j^{\text{old}}+\frac{y_j(E_i-E_j)}{\eta }$$ and is then clipped to satisfy the bounds ([L, H]), determined from ${\alpha }_i,{\alpha }_j$ and their respective labels. Having solved for ${\alpha }_j^{new}$ we update

$${\alpha }_i^{new}={\alpha }_i^{old}+y_i{y}_j({\alpha }_j^{old}-{\alpha }_j^{new})$$

Once new values are obtained, the bias term (b) is updated depending on whether either (_i) or (_j) lies strictly inside the interval ((0, C)).

$$b:=\{\begin{array}{ll}{b}_i,& 0<{\alpha }_i<C\\ b_j,& 0<{\alpha }_j<C\\ \frac{b_i+b_j}{2},& \text{otherwise}\end{array}$$

$$b_i=E_i+y_i({\alpha }_i^{\text{new}}-{\alpha }_i^{\text{old}})k(x_i,x_i)+y_j({\alpha }_j^{\text{new, clipped}}-{\alpha }_j^{\text{old}})k(x_i,x_j)+b^{\text{old}}$$

$$b_j=E_j+y_i({\alpha }_i^{\text{new}}-{\alpha }_i^{\text{old}})k(x_j,x_i)+y_j({\alpha }_j^{\text{new, clipped}}-{\alpha }_j^{\text{old}})k(x_j,x_j)+b^{\text{old}}$$

Termination and KKT Conditions

SMO iteration continues until all Lagrange multipliers satisfy the KKT conditions up to a tolerance $ϵ$:

$$\{\begin{array}{ll}{\alpha }_i=0& \Rightarrow y_{i}f(x_i)\ge 1-ϵ\\ 0<{\alpha }_i<C& \Rightarrow y_{i}f(x_i)\approx 1\\ {\alpha }_i=C& \Rightarrow y_{i}f(x_i)\le 1+ϵ\end{array}$$

Heuristic for Working Pair Selection: Maximal Violation

So far the working pair are selected randomly, but to accelerate convergence, we use a heuristic for selecting the working set known as the Maximal Violating Pair (WSS 1). Instead of sampling ${\alpha }_j$ randomly:

1. Choose $({\alpha }_i)$ with the largest KKT violation,
2. Pair it with $({\alpha }_j)$ such that the prediction error difference $(E_i-E_j)$ is maximised.

$$\begin{array}{r}i\in \arg \underset{t\in I_{\text{up}}({\mathit{\alpha }}^k)}{max}-y_t\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_t(1)\\ j\in \arg \underset{t\in I_{\text{low}}({\mathit{\alpha }}^k)}{min}-y_t\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_t(2)\end{array}$$

where:

$$I_{\text{up}}({\mathit{\alpha }}^k)=\{t\mid {\alpha }_t<C,y_t=1\text{ or }{\alpha }_t>0,y_t=-1\},$$ $$I_{\text{low}}({\mathit{\alpha }}^k)=\{t\mid {\alpha }_t<C,y_t=-1\text{ or }{\alpha }_t>0,y_t=1\},$$ $$\mathrm{\nabla }f({\mathit{\alpha }}^k)=Q{\mathit{\alpha }}^k-\mathbf{e},$$ with $(Q)$ as the kernel matrix adjusted by labels where $Q_{ij}=y_i{y}_{j}K(x_i,x_j)$ and $\mathbf{e}$ is a vector of ones. The selected $\{i,j\}$ is also known as the , and for WSS 1 is refered to as the two variable working set.

This heuristic selection ensures that at each iteration we target the most significant KKT violations whicih makes the updates lead to maximal reductions in the dual objective, speeding up convergence compared to just randomly sampling.

It is useful to know that these three are special cases of each other and that $WSS\text{ 1 }\subset WSS\text{ 2 }\subset WSS\text{ 3 }$. So if the theorem concludes for $WSS\text{ 2 }$ and $WSS\text{ 3 }$ it holds in the case of $WSS\text{ 1}$. $M({\alpha }_k)$ is max instead of argmax for $(1)$ and $m({\alpha }_k)$ is min instead of argmin for $(2)$.

For WSS 2 it allows any pair that violates KKT conditon by at least some factor $\sigma \in (0,1]$ of the maximal violation. The pair $({\alpha }_i,{\alpha }_j)$ is seleccted such that

$$y_i\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_i+y_j\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_j\ge \sigma (m({\mathit{\alpha }}^k)-M({\mathit{\alpha }}^k)),$$

For WSS 3 heuristic, the pair $(({\alpha }_i,{\alpha }_j))$ is selected such that:

$$y_i\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_i+y_j\mathrm{\nabla }f({\mathit{\alpha }}^k{)}_j\ge h(m({\mathit{\alpha }}^k)-M({\mathit{\alpha }}^k)),$$

where $(h:[0,\mathrm{\infty })\to [0,\mathrm{\infty }))$ is a function satisfying $(h(x)>0)$ for $(x>0)$, and $(h)$ is locally Lipschitz continuous at 0 with $(h(0)=0)$.