2
$\begingroup$

In Support Vector Regression, the following dual optimization problem is solved with respect to $\alpha_i$ and $\alpha_i^*$:

\begin{equation} \begin{aligned} & \text{maximize} && \begin{cases} -\frac{1}{2}\sum_{i,j = 1}^{j}(\alpha_j - \alpha_j^*)x_i,x_j \\ -\epsilon \sum_{i = 1}^{l}(\alpha_i + \alpha_i^*) + \sum_{i = 1}^{l} y_i (\alpha_i - \alpha_i^*) \end{cases} \\ & \text{subject to} && \begin{cases} \sum_{1}^{l} (\alpha_i - \alpha_i^*) = 0\\ \alpha_i, \alpha_i^* \in [0, C] \end{cases} \end{aligned} \label{dual_lin_opt} \end{equation}

In case of a linear SVR, the final form of the approximated function is

\begin{equation} f(x) = \sum_{i = 1}^{l}(\alpha_i - \alpha_i^*)x_ix + b. \label{sv_exp_lin} \end{equation}

I want to understand how $b$ is derived in this context. As the problem of SVR is usually stated, it seems that $b$ is a constant term but in papers that explain the derivation, $b$ seems to be different for every observation. For instance, in Smola (2003) $b$ is

\begin{equation} \max\{-\epsilon + y_i - \omega x_i | \alpha_i < C \text{ or } \alpha_i^* > 0 \} \le b \le \min\{-\epsilon + y_i - \omega x_i | \alpha_i > 0 \text{ or } \alpha_i^* < C\} \end{equation}

And it is stated that the inquelities become equalities for some $\alpha_i$ or $\alpha_i^*$ $\in (0, C)$. But that means $b$ differs for every observation because it depends on the index $i$ of the observation. However, I have never seen the formula for SVR with $b_i$. So, is $b$ constant or not?

$\endgroup$
1
$\begingroup$

$b$ is defined as being a single constant for the model. If it needed to be defined for every training point, then you'd need some separate way to pick a $b$ for the test point.

The bounds you gave for $b$ are \begin{equation} \max_i\{-\epsilon + y_i - \omega x_i | \alpha_i < C \text{ or } \alpha_i^* > 0 \} \le b \le \min_i\{-\epsilon + y_i - \omega x_i | \alpha_i > 0 \text{ or } \alpha_i^* < C\} ,\end{equation} otherwise what would the max and min be over? Since both bounds are tight for certain $i$, that constrains $b$ to be a single value.

$\endgroup$
  • $\begingroup$ I didn't recognize that it is the maximum and minimum over all $i$s. I thought it corresponds to the $\alpha_i$ or $\alpha_i^*$ that min./max. the value of the set. Can you recommend a paper or book that goes into more detail of the derivation of $b$ and proves your final statement? $\endgroup$ – random_guy Oct 17 '16 at 11:16
  • $\begingroup$ Yeah, $b$ fitting is done after the $\alpha$s are fit. I believe Scholkopf and Smola's book Learning with Kernels has more details here, but my copy is currently across an ocean and I can't easily check. If you follow citations from the tutorial you linked you might find a derivation; alternatively, depending on your C++ skills the libsvm source is reasonably understandable if you just want to check that a good implementation of the algorithm does it that way. $\endgroup$ – Dougal Oct 17 '16 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.