logistic regression. How to get dual function?

Question

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?

Answer 1

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.

Answer 2

Tom Minka gives the derivation in this excellent paper: http://research.microsoft.com/en-us/um/people/minka/papers/logreg/minka-logreg.pdf

Answer 3

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

Answer 4

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.