1
$\begingroup$

I'm trying to frame the perceptron in terms of familiar optimization concepts but haven't found a nice explanation of the perceptron's dual form.

We can phrase the primal problem as \begin{equation} \begin{aligned} & \underset{w \in \mathbb{R}^d}{\text{minimize}} && J(w) = \frac{1}{N}\sum_{i=1}^N l(w,x_i) = \frac{1}{N}\sum_{i=1}^N -y_i \times [w \cdot x_i]_+ \\ \end{aligned} \end{equation} for $S = \{(x_i, y_i)\}_{i=1}^N$ with $x_i \in \mathbb{R}^d$, $y_i \in \{\pm 1\}$ and $[a]_+ = \max\{a,0\}$. Note that $l(w,x)$ is the hinge loss, a convex relaxation of the $0/1$ loss.

To minimize $J(w)$, we can use (sub)gradient descent. For $y_i \times w\cdot x_i < 0$ (we've made an error), we have a nonzero (negative) gradient. For $y_i \times w \cdot x_i > 0$ (we've correctly classified), we have a zero gradient. At the kink (i.e., when $w \cdot x_i=0)$ we can choose any subgradient between zero and $-y_i x_i$. In particular, we can use $$ \partial_wJ(w) = -(y_i \, x_i)\, \mathbb{1}\{y_i \times (w \cdot x_i) \leq 0\} $$ and the subgradient descent update $w^{(t+1)} = w^{(t)} - \partial_wJ(w)$ to recover the standard perceptron rule (note that the standard perceptron rule is subgradient descent with a fixed step size).

However, we might want to introduce nonlinearity into our model to make it more expressive. If we can write $J(w)$ only involving inner products of the $x_i$s, then we can use the "kernel trick" to map the $x_i$s to a richer space (a RKHS) space. To do so, we first consider the "dual" form of the problem.

Various sets of notes say that we can express $w \in \mathbb{R}^d$ as a sum of the training examples, i.e., $w = \sum_{i=1}^N \alpha_i y_i x_i$, but none are explicit about why; they just list the update procedure for the "dual" form.

I guess we can see that initializing $w^{(0)} = 0$, gradient descent a gives linear combinations of the training examples, but this isn't satisfying. I feel that the Representer theorem is at play somehow, but I don't see the RKHS.

So, what's the dual problem to $\min_w J(w)$? Naively taking the dual of $\min_w J(w)$ doesn't give anything interesting, so I feel that there must be some constraint or reformulation that gives the meaningful dual update procedure. How can we see this?

$\endgroup$
  • $\begingroup$ The notes you linked to lead up to support vector machines. I think that if you look in a textbook on machine learning or data mining, you may find a satisfactory discussion of "dual form" of the problem. $\endgroup$ – mjw May 26 at 5:54

Your Answer

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

Browse other questions tagged or ask your own question.