2
$\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$
1
  • $\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 '19 at 5:54
1
$\begingroup$

We can derive the dual form by using the Lagrange duality. Briefly, we first formulate the objective function and the constraints of the perceptron, and use that to solve the generalized Lagrangian. Then, via KKT stationary and complementary conditions, we can express $w$ as a linear combination of the training samples $w = \sum_{i=1}^{n} \alpha_i y_i \vec{x_i}$.

For the full derivation and explanation, please see my answer to a similar question here.

$\endgroup$

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.