1

I at the moment trying to understand how SVM works with the help of this paper

The paper itself explains things pretty well, but there is an alfa term, which doesn't seem to be documented anywhere? could any of elaborate on what it means? and what effect it has?

The alfa terms is first seen in equation (1)

Snippet from paper

Lamda
  • 117

2 Answers2

1

$c$ (resp. $d$) is a point on the convex hull of the points in Class 1 (resp. Class 2). Therefore, $c$ (resp. $d$) can be represented as a convex combination of the points in Class 1 (resp. Class 2). More specifically, $$ c = \sum_{y_i \in \text{ Class 1}} \alpha_i x_i\quad \text{ for some }\quad \sum_{y_i \in \text{ Class 1}}\alpha_i = 1\quad \text{ and } \quad \alpha_i \geq 0 $$ and $$ d = \sum_{y_i \in \text{ Class 2}} \alpha_i x_i\quad \text{ for some }\quad \sum_{y_i \in \text{ Class 2}}\alpha_i = 1\quad \text{ and } \quad \alpha_i \geq 0 $$

PSPACEhard
  • 10,283
  • I am not sure.. I just made a quick Wiki search, and the formula (The summation) reminds of how convex hull is defined, rather a specific point in on the convex hull.. – Lamda Jun 02 '16 at 11:50
  • @Lamda Yes. The convex hull of a set is defined as the convex combination of all points in the set. Therefore, a point on the convex hull can be represented as a convex combination of points in the set for some $\alpha$. In the paper, they want to find $c$ and $d$ that are closest. Therefore, we have to find corresponding $\alpha$ such that $c$ and $d$ are closest. – PSPACEhard Jun 02 '16 at 11:53
  • but why is alfa constrained? – Lamda Jun 02 '16 at 12:02
  • @Lamda Given a set of points $S = {x_1, \cdots, x_n}$, a point $y$ is a convex combination of $x_1$, $\cdots$, $x_n$ if $y$ can be written as the following form: $$y = \sum_i \alpha_ix_i$$ for some $\alpha$ that $\sum_i \alpha_i = 1$ and $\alpha_i \geq 0$. – PSPACEhard Jun 02 '16 at 12:04
0

$\alpha$ is the vector of coefficients $\alpha_i$. The goal of the quadratic program is to find the vector $\alpha$ (and thus the coefficients $\alpha_i$) satisfying the constraints which minimize the quantity.

Ben Grossmann
  • 225,327
  • I am not sure if i understand the $\alpha$ term. $x_i$ is each data point, data point being a vector of features, and how is $\alpha$ related to that? – Lamda Jun 02 '16 at 11:29
  • The data points $x_i$ are used to build a function on the variables $\alpha_i$. The goal of the quadratic program is to minimize that function. – Ben Grossmann Jun 02 '16 at 11:34
  • Geometrically, we can say that for each $\alpha$ satisfying $\alpha_i \geq 0$ and $\sum \alpha_i = 1$, $\sum \alpha_i x_i$ is a point in the convex hull. – Ben Grossmann Jun 02 '16 at 11:36