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?
5
-
$\begingroup$ Do you have a reference to the paper? $\endgroup$– Sextus EmpiricusCommented 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$– AlexConfusedCommented 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$– jbowmanCommented 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$– Richard HardyCommented Sep 16, 2018 at 8:38
-
$\begingroup$ Therefore, I am not sure whether the current formulation of the question quite makes sense. $\endgroup$– Richard HardyCommented Sep 16, 2018 at 8:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
7
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}$)
answered Aug 28, 2018 at 13:33
-
$\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$ Commented 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$ Commented 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$ Commented Aug 28, 2018 at 14:44
-
$\begingroup$ It refers to the i-th vector $\endgroup$ Commented Aug 28, 2018 at 14:56
-
$\begingroup$ I think it should refer to the i-th entry. Only then is the transformation correct. $\endgroup$ Commented Aug 28, 2018 at 16:25
$\begingroup$
$\endgroup$
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.