# logistic regression. How to get dual function?

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?

-
What are you precisely asking about? Is this a homework? –  mbq May 24 '12 at 12:48
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? –  whuber May 24 '12 at 14:40
@whuber, there are typos, but why do you say it's not a form of LR? –  Pardis May 24 '12 at 15:26
@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. –  whuber May 24 '12 at 15:33
I added the explanation to my answer below. –  Pardis May 24 '12 at 15:56

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, $$\mathbb{E}(Y|X) = \sigma\big(\mathbf{w}^\mathsf{T}\mathbf{x}\big)$$ where $\sigma(z)$ is the logistic function $$\sigma(z) = \frac{1}{1+ \exp(-z)}.$$

Here's the likelihood \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} 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.

-
I am sorry, but didn't OP ask us how to get the dual form? –  d_ijk_stra Jul 27 '12 at 4:37
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 –  Pardis Aug 7 '12 at 16:58
@user1149913 seems to give a good answer to that part –  Pardis Aug 7 '12 at 17:02
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.
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. –  gung Mar 27 at 23:38