1
$\begingroup$

In case of linear kernel, how to interpret the weights in the formulations of nu-SVR?

I am using nu-SVR to estimate the parameters in GARCH(1,1) model:$ \sigma_t^2 = \omega + \alpha y_{t-1}^2 + \beta\sigma_{t-1}^2$

To get parameters: $\omega$, $\alpha$ and $\beta$, I fit data with python sklearn.svm.SVR.

As stated in the documentation,

coef_: Weights assigned to the features (coefficients in the primal problem). This is only available in the case of a linear kernel. coef_ is readonly property derived from dual_coef_ and support_vectors_.

intercept_: Constants in decision function.

According to New Support Vector Algorithms and LIBSVM documentation:

$$ \begin{aligned} \begin{gathered} \textrm{minimize } \frac{1}{2}\parallel\omega\parallel^2 + C(\nu\varepsilon + \frac{1}{l}\sum_{i=1}^l)(\zeta_i + \zeta_i^*)\\\textrm {subject to } \begin{cases} y_i-\langle \omega, x_i \rangle -b \leq \varepsilon + \zeta_i^*,\\ \langle\omega, x_i \rangle +b -y_i \leq \varepsilon+ \zeta_i, \\ \zeta_i,\zeta_i^* \geq 0, i=1,...,l, \varepsilon \geq 0 \end{cases} \end{gathered} \end{aligned} $$

The approximate function is: $$ f(x) = \sum_{i=1}^l (\alpha_i^* - \alpha_i)k(\textbf{x}_i,\textbf{x})+b $$

My questions are: What is the primal problem mentioned in the documentation? In case of linear kernel, how to derive the coefficients if two features are given? What is the decision function and how to derive the intercept?

$\endgroup$

1 Answer 1

1
$\begingroup$

In case of linear functions $f$, given training data $\lbrace (\mathbf{x}_{1}, y_{1}), ..., (\mathbf{x}_{l}, y_{l}) \rbrace$ where $\mathbf{x}$ is a feature vector and $y$ is target variable, our goal is to find a function: $$ f(x) = \mathbf{w} \cdot \mathbf{x} + b $$ that approximates the target variable $y$. Using $\nu$-SVR the goal is to control both training error and model complexity by minimizing the so called primal objective function that you found in LIBSVM documentation: $$ \frac{1}{2} \mathbf{w}^T \cdot \mathbf{w} + C \left( \nu\epsilon + \frac{1}{l}\sum_{i=1}^l (\xi_i + \xi_i^*) \right) $$ with respect to primal parameters $\mathbf{w}, b, \xi, \xi^*, \epsilon$ and subject to constraints that you have already written. This optimization problem is called the primal problem.

LIBSVM solves the primal problem computationally more efficient (especially in non-linear setting) in its dual formulation, where the goal is to maximize the dual objective function with respect to dual parameters: $\alpha, \alpha^{*}$. And LIBSVM returns the (dual) approximate function that you have also written: $$ f(x) = \sum_{i=1}^{l} (\alpha_{i}^{*} - \alpha_{i})K(\mathbf{x}_{i}, \mathbf{x}) + b $$ where $\mathbf{x}_{i}, i = 1, ..., l$ are called the support vectors. Using linear kernel: $$ K(\mathbf{x}_{i}, \mathbf{x}) = \mathbf{x}_{i}^{T} \cdot \mathbf{x}, $$ the approximate function is simply: $$ f(x) = \sum_{i=1}^{l} (\alpha_{i}^{*} - \alpha_{i}) \mathbf{x}_{i} \cdot \mathbf{x} + b $$ so to derive the primal parameters or weights $\mathbf{w}$ from dual parameters $\alpha, \alpha^{*}$ we only need to multiply dual parameters with support vectors $x_{i}$: $$ \mathbf{w} = \sum_{i=1}^{l} (\alpha_{i}^{*} - \alpha_{i}) \mathbf{x}_{i}. $$

After computing $\mathbf{w}$, one way of computing the intercept $b$ is from the overdetermined system of equations: $$ b = y_{i} - \mathbf{w} \cdot \mathbf{x_i} \pm \epsilon \qquad \text{for} \quad \alpha_i, \alpha_i^{*} \in (0, C) $$ another way is to compute it as a by product of optimization process in the context of interior point optimization, see Section 5 in A tutorial on support vector regression; Smola:2004. You can probably find in documentation of LIBSVM in what way LIBSVM computes $b$.

In case of estimating GARCH(1,1) parameters, the feature vector $\mathbf{x}$ becomes $[y_{t-1}^{2}, \sigma_{t-1}^{2}]$ and target $y$ becomes $\sigma_{t}^{2}.$ By running $\nu$-SVR optimization process you compute weights $\omega$ that are estimates of parameters $\alpha$ and $\beta$ and you also compute intercept $b$ that is an estimate of $\omega$ in GARCH(1,1) process.

Using python:

import numpy as np
from sklearn.svm import NuSVR

we want to find GARCH parameters:

omega, alpha, beta = .1, .2, .3

Lets first simulate GARCH(1, 1) process

n = 1000 # number of training data 
sigma2 = np.zeros(n)
y = np.zeros(n)
z = np.random.normal(0, 1, n)
sigma2[0] = np.abs(np.random.normal(0, 1, 1))
y[0] = sigma2[0] * z[0]
for t in range(1, n):
    sigma2[t] = omega + alpha * y[t - 1]**2 + beta * sigma2[t - 1]
    y[t] = np.sqrt(sigma2[t]) * z[t]

y2 = y * y

And fit $\nu$-SVR model:

target_y = sigma2[1:n]
features_X = np.vstack( (y2[0:(n-1)], sigma2[0:(n-1)]) ).T

clf = NuSVR(C=10.0, nu=0.1, kernel='linear', gamma='auto')
fit = clf.fit(features_X, target_y)

Now to get the intercept omega

fit.intercept_ # = array([0.09999925])

To get primal parameters or weights $w$ we can use what you found in the scikit-learn documentation on svm-regression:

fit.coef_ # = array([[0.20000078, 0.30000197]])

or using the derivation I described above, we can get the same result by multiplying dual coefficients with support vectors $(\alpha_{i}^{*} - \alpha_{i}) \cdot x_{i}$:

fit.dual_coef_.dot(fit.support_vectors_) # = array([[0.20000078, 0.30000197]])
$\endgroup$
4
  • $\begingroup$ Hi, thank you for the answer again. For the second half of my question, is it possible to derive the parameters of GARCH(1,1) from the approximate function? $\endgroup$
    – yao
    Dec 16, 2019 at 10:43
  • $\begingroup$ The result of $\nu$-SVR by running LIBSVM is not only black box approximate function $f(x)$, but also estimated (dual) parameters $\alpha_{i}$, $\alpha_{i}^{*}$, $b$ and selected feature vectors $x_{i}$ called support vectors, since this is how the approximate function is defined and computed. So you don't need to and should not try to derive parameters of GARCH(1,1) process from $f(x)$ alone, but use instead estimated (dual) parameters to compute estimates of parameters for GARCH(1,1) process as I described in my answer. $\endgroup$ Dec 17, 2019 at 23:16
  • $\begingroup$ I added the derivation of intercept $b$ and elaborated on the estimation of the parameters in GARCH(1,1) process. $\endgroup$ Dec 17, 2019 at 23:17
  • $\begingroup$ It really helps me to understand! Thank you! $\endgroup$
    – yao
    Dec 18, 2019 at 15:09

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