0
$\begingroup$

I want to minimise a real-valued cost function for a single-layer perceptron which has a parameter vector $w \in \mathbb{R}^N$.

The cost function is $$ c(w) = \sum_{\{p: \, y_p \cdot \langle w, x_p \rangle \leq 0\}} y_p \cdot \langle w, x_p \rangle $$ My goal is to find $w \neq 0$ such that minimises $c(w)$ for a fixed set of possible input tuples $\{(x_p,y_p)\}_{p=1}^M$, were $x_p \in \mathbb{R}^N$, $y_p \in \mathbb{R}$.

If I want to find its minimums, I have to compute it's gradient with respect to $w$, but how can I compute it if $w$ appears in the sum's constraint!?

However, since for any given $w$ the set of indexes $p$ for the sum is fixed, I think I can ignore that constraint to compute the gradient and just write: $$\nabla_w c(w) = \sum_{\{p: \, y_p \cdot \langle w, x_p \rangle \leq 0\}} y_p \cdot x_p $$ and find the minimum using gradient descent.

I'd like to get some feedback, if this idea works in my problem and/or in general , and maybe some materials (books or links are appreciated!) I can check about this.

This problem is related to backpropagation and Rosenblat's Delta Rule, which I should be able to derive from the solution.

$\endgroup$
  • $\begingroup$ This is a linear programming problem. If $w$ is in the admissible region then yes you can compute the gradient ignoring the constraint. But during the gradient descent, you need to be careful with the case $w$ admissible but $w-\eta \nabla w$ not admissible. This is why we often use some projection of the gradient. neos-guide.org/content/gradient-projection-methods $\endgroup$ – reuns May 13 '17 at 13:19
0
$\begingroup$

(Not an answer, only a long comment). I think that your argument is not correct. Namely, you can write your function as $$ c(w) = \sum_{p=1}^M \psi_p(w), \qquad \psi_p(w) := \min\{0, y_p \langle w, x_p\rangle\}. $$ At points where $y_p \langle w, x_p\rangle\neq 0$ for every $p$, every $\psi_p$ is differentiable and the gradient of $c$ can be computed by your formula.

On the other hand, if $y_p \langle w, x_p\rangle = 0$ for some $p$, then the corresponding function $\psi_p$ is not differentiable. Anyway, you can compute the generalized gradient $\partial \psi_p(w)$ and try to work using it.

$\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.