## 5 Methods
### Support Vector Regression  
The basic idea of \(\epsilon\)-SVR is finding the flattest function \(f(x)\) whose deviation from the training data is not larger than a given parameter \(\epsilon\). In case of a linear function  
\[f(x)=\langle w,x\rangle+b \tag{34}\]  
where \(\langle\cdot,\cdot\rangle\) denotes the dot product, the resulting optimization problem is given by:  
\[ \begin{array}{llll}\text{minimize}&\frac{1}{2}\parallel w\parallel^{2}\\ \text{subject to}&\begin{cases}y_{i}-\langle w,x_{i}\rangle-b&\leq&\epsilon \\ \langle w,x_{i}\rangle+b-y_{i}&\leq&\epsilon\end{cases}\end{array}  \tag{35}\]  
Here, the flatness is defined as norm of the parameter vector, \(\|w\|^{2}=\langle w,w\rangle\). The constraints mean, that training data with an error smaller than \(\epsilon\) is not taken into account while errors larger than \(\epsilon\) are not acceptable [38; 39]. However, depending on the type of function, it is not always feasible to find a function that keeps the deviation small enough for all training data. Under certain circumstances, this function does not exist. Therefore, the margin can be softened depending on the training data by using slack variables \(\xi_{i}\) and \(\xi_{i}^{*}\) which belong to a positive or negative error, respectively:  
\[\text{minimize}\quad\frac{1}{2}\parallel w\parallel^{2}+C\sum_{i=1}^{t}\left( \xi_{i}+\xi_{i}^{*}\right)\]  
\[\text{subject to}\quad \begin{Bmatrix}y_{i}-\langle w,x_{i}\rangle-b&\leq&e+\xi_{ i}\\ \langle w,x_{i}\rangle+b-y_{i}&\leq&e+\xi_{i}^{*}\\ \xi_{i},\xi_{i}^{*}&\geq&0\end{Bmatrix}  \tag{36}\]  
The margin is extended by the slack variables, so that deviations larger than \(\epsilon\) are now acceptable, but penalized. Figure 21 illustrates the development of the penalty. As long as the deviation is within the \(\epsilon\) margin, no penalty is applied. If the deviation becomes larger than \(\epsilon\), the penalty increases with a slope defined by the parameter \(C\). Thus, there is a trade-off between the flatness of the resulting function and the size of the remaining deviation that can be set by constant \(C\). This trade-off is especially important, as flatter functions tend to be more robust to unseen data. Lagrange multipliers can be used to find the extremum of a (optimization) function \(f(x)\) with constraints \(g(x)\). Essentially, at the point of extremum, the gradients of \(f(x)\) and \(g(x)\) need to point in the same direction. Otherwise, it would be possible to increase or decrease the value of \(f(x)\) by moving along \(g(x)\). However, while the gradient vectors have to point in the same direction, they do not necessarily have the same length. Therefore, the Lagrange multiplier \(\lambda\) is added to the gradient of \(g(x)\) in order to re-scale its vector length. The resulting constraint for an extremum of \(f(x)\) at \(g(x)\) is  
\[\
abla f(x)=\lambda\
abla g(x). \tag{37}\]  
Applied to Equation (36) \(f(x)-\lambda g(x)\) gives the so-called Lagrangian:  
\[L:=\frac{1}{2}\parallel w\parallel^{2}+C\sum_{i=1}^{t}(\xi_{i}+ \xi_{i}^{*})-\sum_{i=1}^{t}(\eta_{i}\xi_{i}+\eta_{i}^{*}\xi_{i}^{*})+\\ -\sum_{i=1}^{t}\alpha_{i}(\epsilon+\xi_{i}-y_{i}+\langle w,x_{i} \rangle+b)+-\sum_{i=1}^{t}\alpha_{i}^{*}(\epsilon+\xi_{i}^{*}+y_{i}-\langle w,x_{i}\rangle-b) \tag{38}\]  
where \(\eta_{i}\), \(\eta_{i}^{*}\), \(\alpha_{i}\), and \(\alpha_{i}^{*}\) represent the Lagrange multipliers. According to the saddle point condition of Equation (37), the partial derivatives of \(L\) with respect to \(\omega\), \(b\), \(\xi_{i}\), and \(\xi_{i}^{*}\) have to be zero:  
\[\frac{\partial L}{\partial b}=\sum_{i=1}^{t}(\alpha_{i}^{*}-\alpha_{i})=0 \tag{39}\]  
\[\frac{\partial L}{\partial\omega}=\omega-\sum_{i=1}^{t}(\alpha_{i}-\alpha_{i} ^{*})x_{i}=0 \tag{40}\]  
\[\frac{\partial L}{\partial\xi_{i}}=C-\alpha_{i}-\eta_{i}=0 \tag{41}\]  
Figure 21: Penalization of training data with a deviation larger as \(\epsilon\).