5
$\begingroup$

I am currently reading a paper stating the following regression problem $$\text{min} \sum_{i=1}^N ||\beta\cdot x_i-y_i||\\ \text{subject to} \sum_{j=2}^M ||\beta_{j}-\beta_{j-1}|| \leq S $$ for vectors $x_1,\dots,x_N, \beta \in \mathbb{R}^n, y_i \in \mathbb{R}$. This is a slightly changed version of the fused lasso loss for a regression problem. The authors state, this poblem can be solved via maximum likelihood estimation. I would have used quadratic program solvers instead but they are slower of course. Are there closed form solutions (from MLE) for this kind of problem?

$\endgroup$
5
  • $\begingroup$ Do you have a reference to the paper? $\endgroup$ Aug 28, 2018 at 15:59
  • $\begingroup$ people.cs.vt.edu/gangwang/ccs18.pdf The mentioned paragraph on the computation is directly below equation (7) $\endgroup$ Aug 28, 2018 at 16:15
  • $\begingroup$ This is actually related to the penalty used by P-splines, see projecteuclid.org/download/pdf_1/euclid.ss/1038425655 (Eilers and Marx, Flexible Smoothing with B-splines and Penalties). $\endgroup$
    – jbowman
    Aug 28, 2018 at 16:30
  • $\begingroup$ The regression problem you present defines an estimator based on a loss function that is being minimized. Meanwhile, maximum likelihood (ML) defines an estimator based on maximizing the likelihood. I do not think the two can ever coincide since ML would never yield a penalized solution such as this one. ML is not even an method for calculating parameter estimates, unlike quadratic solvers, gradient descent, Newton-Raphson etc. (I have a problem finding the right term for all of these; optimization methods, maybe?). ML tells you what you are looking for but not how to calculate it mechanically. $\endgroup$ Sep 16, 2018 at 8:38
  • $\begingroup$ Therefore, I am not sure whether the current formulation of the question quite makes sense. $\endgroup$ Sep 16, 2018 at 8:40

2 Answers 2

1
$\begingroup$

How about transforming to the vectors as following:

$$z_j = \sum_{i=j}^{N} x_i $$

where the index refers to the index of the regressors.

then

$$\beta^\star \cdot z = \beta \cdot x$$

for

$$\beta_j = \sum_{i=1}^{j} \beta_i^\star \quad \text{ or (when $i \geq 2$)} \quad \beta^\star_i = \beta_i-\beta_{i-1}$$

Now you just have to solve the problem for $z$ (instead of $x$) with the easier constraint $ \sum_{i=2}^M ||\beta^\star_{i}|| \leq S$.

This turns into ridge regression (where $\Gamma_{11} = 0$ in the Tikhonov regularization matrix) when we assume $\Vert \cdot \Vert$ is the quadratic norm, in which case there is a closed solution. Otherwise for Lasso there is a good algorithm to solve it.


Schematic example for $\beta^\star \cdot z = \beta \cdot x$ using three variables:

$\begin{array}{ccccccc} \beta_1^\star z_1 &=& \beta_1^\star x_1 & + & \beta_1^\star x_2 &+& \beta_1^\star x_3 \\ \beta_2^\star z_2 &=& & & \beta_2^\star x_2 &+& \beta_2^\star x_3 \\ \beta_3^\star z_3 &=& & & && \beta_3^\star x_3 \\ & & \vert\vert & & \vert\vert & & \vert\vert \\ & & \beta_1 x_1 & & \beta_2 x_2 & & \beta_3 x_3 \\ \end{array} $


To avoid confusion about indices

The article speaks of the cost function

$$L(f(\mathbf{x}),y) = \sum_{i=1}^N \Vert \boldsymbol\beta \mathbf{x_i} -y_i \Vert$$

with $x_i$ a sample $i$ represented by a row vector $(x_1, x_2, \cdots, x_M)^T$ of different features. This can be simplified to a matrix notation using $X = ((x_1, x_2, \cdots, x_M)^T)_i$ where each column of X is a vector of the same feature for different samples $i$.

$$L(f(\mathbf{x}),\mathbf{y}) = \Vert \mathbf{X} \boldsymbol\beta^T -\mathbf{y} \Vert$$

when I speak about the index of the regressors I mean the column index of the matrix $X$ (this adding the columns of $X$ is equivalent to adding the entries in the row vectors $\mathbf{x_i}$)

see also https://en.wikipedia.org/wiki/Design_matrix

$\endgroup$
7
  • $\begingroup$ I don't think this is correct. Firstly, I am not sure if your transformation works and even if it works you will solve a regression problem with ridge loss in the end, i.e. your parameters $\beta$ will not have a form such that neighbor parameters are as close as $S$ to each other. $\endgroup$ Aug 28, 2018 at 13:58
  • $\begingroup$ I changed the the transformation (which was indeed in error). The $\beta^\star$ will indeed not be necessarily close to each other. Instead the $\beta^\star$ will be as small as possible such that the neighbors in $\beta_j=\sum_{i=1}^j \beta_i^\star$ will be as close as possible. $\endgroup$ Aug 28, 2018 at 14:01
  • $\begingroup$ In your transformation $z_j = \sum_{i=j}^N x_i$ , is $x_i$ the $i$-th vector from the training set (as introduced in question) or the $i$-th entry of some vector $x$? $\endgroup$ Aug 28, 2018 at 14:44
  • $\begingroup$ It refers to the i-th vector $\endgroup$ Aug 28, 2018 at 14:56
  • $\begingroup$ I think it should refer to the i-th entry. Only then is the transformation correct. $\endgroup$ Aug 28, 2018 at 16:25
0
$\begingroup$

After some research I have found out that there is no closed form solution for this problem (and therefore no MLE in particular). A (fast) solution for this problem has been proposed via solution paths, the algorithm can be found here.

$\endgroup$

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.