0
$\begingroup$

Hello i am reading the book the elements of statistical learning by hastie tibshirani and friedman https://statweb.stanford.edu/~tibs/ElemStatLearn/printings/ESLII_print10.pdf. I am stuck at the page 131 and the equation 4.42. I dont unterstand, to calculate the parameter Beta we can build the sum as written in 4.42 but instead we are calculate the parameter iterative.

$\endgroup$
0
$\begingroup$

For context, we are looking at the perceptron algorithm, where we want to find $(\beta,\beta_0)$ such that: $$ \beta,\beta_0 = \underset{\beta,\beta_0}{ \text{argmin } } D(\beta,\beta_0) = \underset{\beta,\beta_0}{ \text{argmin } } -\sum_{i\in\mathcal{M}} y_i\left( x_i^T\beta + \beta_0 \right) $$ where $\mathcal{M}$ is the index set of misclassified points. (Note that $x_i^T\beta + \beta_0<0$ for $i\in\mathcal{M}$ ). So we can use stochastic gradient descent: $$ (\beta,\beta_0) \leftarrow (\beta,\beta_0) + \gamma(y_ix_i,y_i) $$ where $(y_ix_i,y_i)=\nabla D$ with learning rate $\gamma$.

Notice it is not obvious how to calculate $\tilde{\beta}=(\beta,\beta_0)$ in closed form (i.e. not iteratively). That's because there are many $\tilde{\beta}$ that can satisfy this criterion. Any separating plane gives $D=0$, but there can be many ways to achieve a separating plane.

Because of this, there can be no "direct calculation". Notice that random restarts of the algorithm will give different, but equally valid, results. Thus, we are using stochastic gradient descent.

Using other algorithms, like least squares or LDA, can give a unique solution which you could compute non-iteratively. Maybe better is Vapnik's linear SVM, which has a unique solution, though it is often determined iteratively too, because it adds additional constraints to the perceptron problem.

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