TransWikia.com

What method/algorithm for constrained multi-target regression

Data Science Asked by Frank Schaufelberger on May 20, 2021

I am working with three dimensional measurement data and want to model them using a multivariate linear regression.
I have already implemented a simple gradient descent algorithm to solve the classic regression problem

$y = beta_0 + beta_1x_1 + beta_2x_2 + beta_3x_3.$

However my ultimate goal is to fit three target variables with a hard condition:

$y_1 = beta_{10} + beta_{11}x_1 + beta_{12}x_2 + beta_{13}x_3,
y_2 = beta_{20} + beta_{12}x_1 + beta_{22}x_2 + beta_{23}x_3,
y_3 = beta_{30} + beta_{31}x_1 + beta_{32}x_2 + beta_{33}x_3,
text{subject to }beta_{11}+beta_{22}+beta_{33}=0.$

Or in other words

$underline{y} = underline{underline{B}}cdotunderline{x} + underline{beta_0},
text{subject to } mathrm{tr}(underline{underline{B}})=0.$

I’ve searched high and low for multi-target or multi-output regression methods but I could not find out how I would possibly go on to implement a hard condition into them. Happy for any kind of recommendations, even just keywords for further research.

One Answer

After some further research and inspiration I have figured out the following method:

I am using the vector notation of my problem with $underline{y}=begin{pmatrix}y_1y_2y_3end{pmatrix},~underline{x}=begin{pmatrix}1x_1x_2x_3end{pmatrix},~underline{underline{B}}=begin{pmatrix}beta_{10}&beta_{11}&beta_{12}&beta_{13} beta_{20}&beta_{21}&beta_{22}&beta_{23} beta_{30}&beta_{31}&beta_{32}&beta_{33} end{pmatrix}$ This results in the optimisation problem with $N$ examples

$underline{underline{hat{B}}}=underset{beta in C}{operatorname{argmin}}L(underline{underline{B}})=underset{beta in C}{operatorname{argmin}}sum_{i=1}^{N}lVert underline{y}_i - underline{underline{B}}cdotunderline{x}_i rVert^2,~~~~text{with}~~~~C= lbrace underline{underline{B}}in mathbb{R}^{3times4} mid beta_{11}+beta_{22}+beta_{33}=0rbrace$

For solving this, I am using projected gradient descent where $underline{underline{B}}$ for every iteration is projecet onto $C$. Normally the Projection operator would require another optimisation process $operatorname{proj}_C(x)=operatorname{argmin}_u biglbrace chi_C(u) + frac{1}{2}lVert u-xrVert^2bigrbrace$ with $chi_C$ the characteristic function.

Now comes the neat part: Since the constraint $C$ describes a flat subspace in a 12-dimensional vector space, the projection can be described as a simple linear map.

Using a reduced version of $underline{beta}=begin{pmatrix}beta_{11}beta_{22}beta_{33}end{pmatrix}$ (in the projection step $underline{underline{B}}$ will be flattened to a vector to avoid working with 3D tensors), the projection $underline{beta}'=operatorname{proj}_C(underline{beta})$ can be represented as

$underline{beta}' = underline{underline{P}}cdotunderline{beta}~~~~text{with}~~~~ underline{underline{P}}=frac{1}{3}begin{pmatrix}2&-1&-1-1&2&-1-1&-1&2end{pmatrix}$

The vector $underline{beta}$ and projection map $underline{underline{P}}$ can then be arbitrarily augmented with the remaining entries of $underline{underline{B}}$, as they will not be affected by the projection.

With the above method, my constrained gradient descent is only slightly more expensive than a usual gradient descent method by computing one extra linear operation for each iteration.

The results I have obtained so far with the method seem promising

Correct answer by Frank Schaufelberger on May 20, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP