5
$\begingroup$

Given pairs $(x_i, y_i), x_i \in R^n , y_i \in R$ we want to solve minimization problem (logistic regression):$\min \frac{1}{2} ||w||^2 + \sum_i^{i=m}\log(1+\exp(-y w\cdot x_i))$. How to do that? I know the dual form is: $ \min_{\alpha} D(\alpha)= \frac{1}{2}\sum_{i, j}\alpha_i \alpha_j y_i y_j x_i \cdot x_j + \sum_i\alpha_i \log(\alpha_i) + (C-\alpha_i)\log(C-\alpha_i)$, subject to: $0\le \alpha_i\le C$. How to get dual?

$\endgroup$
  • $\begingroup$ What are you precisely asking about? Is this a homework? $\endgroup$ – user88 May 24 '12 at 12:48
  • $\begingroup$ This is really a mathematical question, but it needs improving before it can be migrated. First, what kind of "dual" do you seek? Second, what is $w$? Third, why doesn't $w$ appear in your putative dual form? Fourth, there are some typos; e.g., $y$ needs to be $y_i$. Fifth, this does not appear to be any form of logistic regression (perhaps because of the typos): what exactly is the connection? $\endgroup$ – whuber May 24 '12 at 14:40
  • $\begingroup$ @whuber, there are typos, but why do you say it's not a form of LR? $\endgroup$ – Pardis May 24 '12 at 15:26
  • $\begingroup$ @Pardis I might be able to see a connection once the argument of $\exp$ is clarified. In its current form it does not appear to be related to a log probability. $\endgroup$ – whuber May 24 '12 at 15:33
  • $\begingroup$ I added the explanation to my answer below. $\endgroup$ – Pardis May 24 '12 at 15:56
4
$\begingroup$

Tom Minka gives the derivation in this excellent paper "A comparison of numerical optimizers for logistic regression" pdf, section 9

$\endgroup$
  • $\begingroup$ While this is good material, this is not an answer imo, more like a comment. $\endgroup$ – Firebug Jul 22 '16 at 20:01
  • $\begingroup$ This is four years old. At this point, we could probably just leave it, unless the link is dead. $\endgroup$ – gung Jul 22 '16 at 20:38
  • $\begingroup$ Welcome to the site. We are trying to build a permanent repository of high-quality statistical information in the form of questions & answers. Thus, we're wary of link-only answers, due to linkrot. Can you post a full citation & a summary of the information at the link, in case it goes dead? $\endgroup$ – gung Jul 22 '16 at 20:39
  • $\begingroup$ Link does not point to where it was supposed to, please fix. $\endgroup$ – Firebug Apr 25 '17 at 13:39
  • $\begingroup$ @Firebug , I have edited it; waiting for peer review; in a meantime, here's the link, section 9; paper name is "A comparison of numerical optimizers for logistic regression" $\endgroup$ – MInner May 11 '17 at 23:06
2
$\begingroup$

LIBLINEAR supports $\ell_2$-regularized logistic regression. According to the authors, the package implements the "trust region Newton method". Here, you can find the slides to learn more, but note that it is not based on the dual formulation.

@whuber I am explaining here, because there wasn't space in the comments...

As you know, in logistic regression, the response data are chosen to be realizations of a Bernoulli random variable $Y$. In this GLM, the conditional expectation is, \begin{equation} \mathbb{E}(Y|X) = \sigma\big(\mathbf{w}^\mathsf{T}\mathbf{x}\big) \end{equation} where $\sigma(z)$ is the logistic function \begin{equation} \sigma(z) = \frac{1}{1+ \exp(-z)}. \end{equation}

Here's the likelihood \begin{equation} \begin{aligned} \mathcal{L}(\mathbf{w}) = \operatorname{p}(\mathbf{y}|\mathbf{X};\mathbf{w}) &= \prod_{i=1}^n \operatorname{p}(y_i|\mathbf{x}_i;\mathbf{w})\\ &= \prod_{i=1}^n \sigma\big(\mathbf{w}^\mathsf{T}\mathbf{x}_i\big)^{y_i}\big(1-\sigma(\mathbf{w}^\mathsf{T}\mathbf{x}_i)\big)^{1-y_i}. \end{aligned} \end{equation} and the negative log-likelihood becomes \begin{align} -\ell(\mathbf{w}) = -\log \mathcal{L}(\mathbf{w}) &= -\sum_{i=1}^{n} \log \operatorname{p}(y_i| \mathbf{x}_i;\mathbf{w})\\ &= -\sum_{i=1}^{n} \log\sigma\big(y_i \mathbf{w}^\mathsf{T}\mathbf{x}_i\big)\\ &= \sum_{i=1}^{n} \log\big(1+ \exp\big(-y_i\mathbf{w}^\mathsf{T}\mathbf{x}_i\big)\big) \end{align} where the last equation follows because $y_i \in \{-1,1\}$.

The $\ell_2$-regularization term is the result of MAP estimation of the parameters with a Gaussian prior.

$\endgroup$
  • $\begingroup$ I am sorry, but didn't OP ask us how to get the dual form? $\endgroup$ – d_ijk_stra Jul 27 '12 at 4:37
  • $\begingroup$ that's true, I was answering the related question that came up in the comments above; additionally, I thought that the OP's main question was how to solve the $\ell_2$-regularized problem not how to obtain the dual formulation $\endgroup$ – Pardis Aug 7 '12 at 16:58
  • $\begingroup$ @user1149913 seems to give a good answer to that part $\endgroup$ – Pardis Aug 7 '12 at 17:02
0
$\begingroup$

Why not just take partial derivative of minimization function with respect to unknown parameters? You can find a lot of material on the web.

$\endgroup$
0
$\begingroup$

Use the lower bound of the convex function $\log(1+x)$: $$ \log (1+x) \ge \log(1+x_1) +(x-x_1)*(`d(\log(1+x_1))` ) $$ where $d(f)$ is the differentiation of $f$.

Note that the factor of $x$ on the right is your dual variable, which is in between $[0,1]$; now the problem is quadratic in $w$ and can be solved.

$\endgroup$
  • $\begingroup$ Welcome to the site, @Ashwini. I took the liberty of using CV's $\LaTeX$ markup features to make your post more readable. Please make sure it still says what you want it to. $\endgroup$ – gung Mar 27 '13 at 23:38

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.