0
$\begingroup$

At page 348 - Chapter 10.6 in The Elements of Statistical Learning (12th printing -2007), the logistic model for K-class classification is expressed as: $p_k(x)={exp(f_k(x))\over \sum_{l=1}^{K}exp(f_l(x))}$. Then, the book states that "There is a redundancy in the functions $f_k(x)$, since adding an arbitrary $h(x)$ to each leaves the model unchanged". Thus the constraint $\sum_{k=1}^{K}f_l(x) = 0$ is imposed to eliminate the redundancy.

Why does imposing this constraint help to eliminate the redundancy?

$\endgroup$

1 Answer 1

1
$\begingroup$

It is because you only need to provide a linear combination of the inputs, $f_k(x)$, for all but one of the classes, and the $f_k(x)$ for the remaining class can be inferred from the constraint (as they all have to sum to zero). This is a very worthwhile saving if you are fitting the model using IRWLS as it involves inverting the Hessian matrix, which is $\mathcal{O}(d^3K^3)$, where $d$ is the number of inputs, and it effectively reduces $K$ by one.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. My concern is if we impose this constraint, does it have any effect on the multinomial model? Given that $\sum p_k(x) = 1$, hence, there has been already a constraint on the $\{f_k(x)\}_1 ^ K$ $\endgroup$
    – Hunglk
    Jan 2, 2022 at 17:28
  • $\begingroup$ No, I don't believe so, at least unless the model is regularised. The sum of probabilities being one does not apply a constraint on the $\{f_k(x)\}_1^K$. If you add a h(x) to all of the $f_k(x)$, then that is equal to multiplying the $\exp\{f_k(x)\}$ by $\exp\{h(x)\}$, which cancels when you perform the division in the softmax function, so the trick is just exploiting that second redundancy. $\endgroup$ Jan 2, 2022 at 17:38
  • $\begingroup$ Then, is the constraint $\sum k_1 ^ K f_k(x)$ play a role as $h(x)$? $\endgroup$
    – Hunglk
    Jan 2, 2022 at 17:59
  • 1
    $\begingroup$ As you can add an arbitrary h(x), then you can make the sum $\sum_{k=1}^Kf_k(x)$ be anything you like, so you may as well make it zero, in which case $f_K(x) = \sum_{k=1}^{K-1}f_k(x)$ $\endgroup$ Jan 2, 2022 at 18:05
  • 1
    $\begingroup$ It is clear now, thank you very much for your help. $\endgroup$
    – Hunglk
    Jan 2, 2022 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.