12

Reducing the kernel width $\sigma_m$ will usually reduce the condition number. However, kernel matrices can become singular, or close to singular, for any basis function or point distribution, provided the basis functions overlap. The reason for this is actually quite simple: The kernel matrix $K$ is singular when its determinant $\det(K)$ is zero. ...


7

You've identiifed the key problem. Certainly the primal can be solved directly by, say, a quadratic programming solver. But typical QP solvers often don't scale well to large problem sizes. A projected gradient method can often scale to significantly larger problems---but only if the derivatives and projections are simple to compute. As I will show, the dual ...


6

If I understand the link of hardmath correctly, a "support vector machine" in its most simple form is just a glorious name for a linear function $f(x)=b^Tx+b_0$ dividing the space into two half spaces according to the sign of the values. And separating two given sets (with disjoint convex hulls for existence of a separating hyperplane). The original ...


4

A couple of suggestions: Choose $\sigma \sim$ the average distance | random $x$ - nearest $x_i$. (A cheap approximation for $N$ points uniformly distributed in the unit cube in $\mathbb{R}^d, d\ 2 .. 5$, is 0.5 / $N^{1/d}$.) We want $\phi( |x - x_i| )$ to be large for $x_i$ near $x$, small for background noise; plot that for a few random $x$. Shift $K$ ...


3

Sounds too simple so maybe I've misunderstood you, but they have binary variables, hence obviously a nonconvex problem (a binary variable is either 0 or 1, which is a nonconvex set)


2

Just some quick ideas from someone who works in the realm of feature extraction in physical systems modeling such as this: you want to find the simplest and strongest differentiating characteristics of the different behaviors you're interested in classifying. First, though: do you know in advance the full extent of behaviors you wish to classify? If not, ...


2

In machine learning, there are two types of problems (there are more, but start with 2) -- supervised and unsupervised. SVM (also logistic regression, etc) is part of supervised learning where you are given two datasets. One with predictors and known desired output (blue/red) called training set, another one with only predictors. Your task is to learn the ...


2

You have two classes of points. Instead of managing them in two sets, one just assigns each point in the first class the value $-1$ and in the second class the value $+1$. So in fact you have point-value pairs $(x_i,y_i)$. To classify future points in a consistent way you now want to construct a function $f(x)$ that has not exactly $f(x_i)=y_i$ as in ...


2

Intuitively for the Gaussian kernel: The decision function of the max-margin task for the two classes $\{-1,1\}$ is the following $f_w(x) = \mbox{sign}(\langle x, w\rangle +b)$ That is when you want to classify a new observation $x$ you calculate the inner product of $x$ and the parameter vector $w$ and decide for the class according to the sign of the ...


2

They are simply referring to the fact that the kernel matrix itself is a central quantity in the algorithm. The problem is that it is $O(n^2)$ in size, where $n$ is the number of points being examined. So the storage and computational requirements surrounding the kernel matrix rapidly become impractical as $n$ gets large.


1

I believe VW has a bug with loss_function=hinge. I always see that the first iteration of bfgs showing derivative = 0 issue. For sgd it didn't seem to report this anomaly but I tend not to trust it. Presumably the error is caused by the nondifferentiability of the hinge loss function (logistic and least square are both smooth).


1

Disclaimer: Most of my optimization-related work has been done in nonconvex optimization, and I have no training in Support Vector Machines (SVM) whatsoever. Based on what I can tell from reading Wikipedia and my optimization background, my guess is that they chose to replace the original nonconvex objective with an upper bound to formulate a convex ...


1

I would guess that the main reason for solving the max margin task in the dual is that the dual formulation permits the use of kernel functions. And therefore it is easy to transfer the input points implicitly to some other feature space where the two classes are separable. In your above formulated task (hard margin) there exits only a solution if the two ...


Only top voted, non community-wiki answers of a minimum length are eligible