# When is logistic regression solved in closed form?

Take $x \in \{0,1\}^d$ and $y \in \{0,1\}$ and suppose we model the task of predicting y given x using logistic regression. When can logistic regression coefficients be written in closed form?

One example is when we use a saturated model.

That is, define $P(y|x) \propto \exp(\sum_i w_i f_i(x_i))$, where $i$ indexes sets in the power-set of $\{x_1,\ldots,x_d\}$, and $f_i$ returns 1 if all variables in the $i$'th set are 1, and 0 otherwise. Then you can express each $w_i$ in this logistic regression model as a logarithm of a rational function of statistics of the data.

Are there other interesting examples when closed form exists?

-
Till we have latex support, could you please avoid using latex. It is hard to make out what you are saying. See this meta thread: meta.stats.stackexchange.com/questions/5/… – user28 Jul 28 '10 at 23:03
Could you put $signs around the LaTex? It now will be rendered. – Peter Smit Jul 30 '10 at 7:04 cool, mostly works, although \{ is not recognized and \ldots looks strange – Yaroslav Bulatov Jul 30 '10 at 18:43 mostly worked here on firefox/Linux. the subscript 1 on x1,...,xd didnt appear as a subscript but the others did. The issues with formatting are minor, mostly the latex appears higher than other characters in the line. – user87 Jul 30 '10 at 19:52 I assume you mean "when are the MLEs of the parameters in closed form?" – Glen_b Aug 23 '10 at 0:43 show 2 more comments ## 2 Answers As kjetil b halvorsen pointed out, it is, in its own way, a miracle that the linear regresion admits an analytical solution. And this is so only by virtue of linearity of the problem (with respect to the parameters). In OLS, you have $$\sum_i (y_i - x_i' \beta)^2 \to \min_\beta,$$ which has the first order conditions $$-2 \sum_i (y_i - x_i'\beta) x_i = 0$$ For a problem with$p$variables (including constant, if needed -- there are some regression through the origin problems, too), this is a system with$p$equations and$p$unknowns. Most importantly, it is a linear system, so you can find a solution using the standard linear algebra theory and practice. This system will have a solution with probability 1 unless you have perfectly collinear variables. Now, with logistic regression, things aren't that easy anymore. Writing down the log-likelihood function, $$l(y;x,\beta) = \sum_i y_i \ln p_i + (1-y_i) \ln(1-p_i), \quad p_i = (1+\exp(-\theta_i))^{-1}, \quad \theta_i = x_i' \beta,$$ and taking its derivative to find the MLE, we get $$\frac{\partial l}{\partial \beta'} = \sum_i \frac{{\rm d}p_i}{{\rm d}\theta}\Bigl( \frac{y_i}{p_i} - \frac{1-y_i}{1-p_i} \Bigr)x_i = \sum_i \Bigl[y_i-\frac1{1+\exp(x_i'\beta)}\Bigr]x_i$$ The parameters$\beta$enter this in a very nonlinear way: for each$i$, there's a nonlinear function, and they are added together. There is no analytical solution (except probably in a trivial situation with two observations, or something like that), and you have to use nonlinear optimization methods to find the estimates$\hat\beta$. A somewhat deeper look into the problem (taking the second derivative) reveals that this is a convex optimization problem of finding a maximum of a concave function (a glorified multivariate parabola), so either one exists, and any reasonable algorithm should be finding it rather quickly, or things blow off to infinity. The latter does happen to logistic regression when${\rm Prob}[Y_i=1|x_i'\beta > c] = 1$for some$c$, i.e., you have a perfect prediction. This is a rather unpleasant artifact: you would think that when you have a perfect prediction, the model works perfectly, but curiously enough, it is the other way round. - the question is why your last equation is not solvable. is it due to the logistic function's inverse diverging at 0 and 1, or is this due to the nonlinearity in general? – eyaler Sep 20 '12 at 12:17 (+1) Regarding your last paragraph: From a mathematical perspective it does work "perfectly" in the sense that an MLE will yield a perfect separating hyperplane. Whether your numerical algorithm behaves sensibly in that circumstance is a separate matter. Laplace smoothing is often used in such situations. – cardinal Sep 20 '12 at 13:27 @eyaler, I would say this is due to nonlinearity in general. My understanding is that there is a limited set of circumstances when this can be solved, although I don't know what these circumstances are. – StasK Sep 21 '12 at 3:54 This post was originally intended as a long comment rather than a complete answer to the question at hand. From the question, it's a little unclear if the interest lies only in the binary case or, perhaps, in more general cases where they may be continuous or take on other discrete values. One example that doesn't quite answer the question, but is related, and which I like, deals with item-preference rankings obtained via paired comparisons. The Bradley–Terry model can be expressed as a logistic regression where $$\mathrm{logit}( \Pr(Y_{ij} = 1) ) = \alpha_i - \alpha_j ,$$ and$\alpha_i$is an "affinity", "popularity", or "strength" parameter of item$i$with$Y_{ij} = 1$indicating item$i$was preferred over item$j$in a paired comparison. If a full round-robin of comparisons is performed (i.e., a pairwise preference is recorded for each unordered$(i,j)$pair), then it turns out that the rank order of the MLEs$\hat{\alpha}_i$correspond to the rank order of$S_i = \sum_{j \neq i} Y_{ij}\$, the sum total of times each object was preferred over another.

To interpret this, imagine a full round-robin tournament in your favorite competitive sport. Then, this result says that the Bradley–Terry model ranks the players/teams according to their winning percentage. Whether this is an encouraging or disappointing result depends on your point of view, I suppose.

NB This rank-ordering result does not hold, in general, when a full round-robin is not played.

-
I was interested in binary because it was easiest to analyze. I have found a very broad sufficient condition in works of Lauritzen -- you get closed form if a corresponding log-linear model is decomposable – Yaroslav Bulatov Jan 29 '11 at 22:16