2
$\begingroup$

Question

I am performing least squares fitting using an objective function of the form $f(\mathbf{x})$ where $\mathbf{x}$ is a vector of parameters containing around 20 elements.

The model function is somewhat expensive to evaluate so I am exploring options for reducing the number of parameters in the model. Are there standard approaches algorithms to tackle this problem?

Current approach

After least squares has completed I calculate the covarience matrix $c$ using the Jacobian $\mathbf{J}$ at the solution point $\mathbf{x}_s$,

$$ c = \left(\mathbf{J}^T\mathbf{J}\right)^{-1} $$

By comparing the relative strength of diagonal contributions to this matrix I then calculate a 'dependency' vector for each parameter,

$$ \mathbf{d} = 1 - \frac{1}{\textrm{diag}(c)\textrm{diag}(c^{-1})}. $$

The closer the element in $\mathbf{d}$ is to zero the more dependence the corresponding parameter has on the least squares solution. For example, I arrive at values shown in the radar plot below,

enter image description here

This shows some key parameters (the ones tipping towards zero), but many parameters that are close to edge. I think these are candidates for reduction. Either don't include them in the model or fix there values.

The problem is don't know a priori which parameters will be the ones to include and the ones to reduce. I therefore need to come up with an algorithm that dynamically turns parameters on and off. I was going to use the dependency vector to help with this. But I'm sure I'm not the first to have this problem and would like some advice before re-inventing the wheel.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you can make a matrix whose columns are the factors that get multiplied by parameter then you can use something like "Variable Importance" with a "random forest" to determine which are less informative. If you have non-informative parameters this is a decent way to find them and reduce the complexity of the model. If you were using "R" I would suggest using this with "glmulti" to automate the parameter activation. $\endgroup$
    – EngrStudent
    Sep 28, 2015 at 20:43
  • 1
    $\begingroup$ For parameter reduction, you could take a look at Paul Constantine's work on Active Subspaces. Typically, active subspaces aren't found dynamically, but I suppose you could adapt his work if you wanted to implement that capability. (He may have already done so, since I haven't kept up with his work, but I think it's interesting.) $\endgroup$
    – Geoff Oxberry
    Sep 29, 2015 at 0:23
  • 2
    $\begingroup$ I agree with @GeoffOxberry! :) Try this first: Draw random samples of x. For each sample, compute the gradient of your objective function. Put all these gradient vectors into a matrix and compute its SVD. If you see a large gap in the singular vectors, then you might have an exploitable active subspace. If not, you might need a different tool. $\endgroup$
    – Paul G. Constantine
    Sep 29, 2015 at 21:33
  • $\begingroup$ @EngrStudent thanks for the data science tips. I took a look and there are a whole host of options here. $\endgroup$
    – boyfarrell
    Sep 30, 2015 at 7:22
  • 1
    $\begingroup$ @GeoffOxberry thanks for whispering the correct incantations to make Paul appear $\endgroup$
    – boyfarrell
    Sep 30, 2015 at 7:23

1 Answer 1

Reset to default
3
$\begingroup$

I'll add a real response here, following the comment I just left. As @GeoffOxberry suggests, you might be able to use active subspaces to, in essence, preprocess your objective function and eliminate (linear combinations of) variables. Try the following first. Randomly sample your variables according to some density. One reasonable choice would be to sample according to a Gaussian that is relatively large in a region that may contain the optimum. (Make sure $f$ is well-defined for each sample!) Call these samples $\mathbf{x}_j$ with $j=1,\dots,N$. With 20 variables, I'd say try 40-100 samples, if you can. For each $\mathbf{x}_j$, compute the gradient, $$ \nabla f_j \;=\; \nabla f(\mathbf{x}_j) \;\in\; \mathbb{R}^{20}. $$ Put all these gradient vectors into a matrix $$ \mathbf{G} \;=\; \frac{1}{\sqrt{N}}\begin{bmatrix} \nabla f_1 & \cdots & \nabla f_N \end{bmatrix} \;\in\; \mathbb{R}^{20\times N}, $$ and compute its SVD, $\mathbf{G}=\mathbf{U}\Sigma\mathbf{V}^T$. Look for gaps in the singular values. If you have a big gap in the singular values, then you might have an exploitable active subspace.

If the first singular value is much larger than the others, make a plot of $\mathbf{u}_1^T\mathbf{x}_j$ versus $f(\mathbf{x}_j)$, where $\mathbf{u}_1$ is the first left singular vector. Statisticians call this a summary plot. The plot might show some interesting and exploitable characteristics of $f$ that may help the optimization. Or it might not.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.