Minimization of covariance matrix in nonlinear optimization

Post Reply New Topic

Let's see where that goes.
A very special topic in optimization.

Optimization is a mathematical process
that tries to make fit measurement data with models' equations
The models contain unknown parameters that you want to determine as exact as possible.

The errors of that parameters are calculated with the covariance matrix.

When the covariance matrix contains small values the errors in the parameters are small (variance, the diagonal)
or the dependence of one parameter of the other is small (non diagonal elements)

Logical conclusion: when you can achieve that this matrix contains small values you have a good result.
Normally you achieve this by keeping the experimental errors of measurement data as small as possible.

But there is also another contribution:

The errors of experimental values usually depends on the range of external (ordinate) values (like temperature, time and such)
and there will be especially well suited measurement points that contain more valuable information than others,
because ... either their errors are very small or
more generally when a particular measurement point is chosen, the covariance matrix values are smaller than for others

The idea is to choose a set of measurement points for which the information content for parameter determination is maximal

In other words you can choose the measurement points (including the experimental error to expect for those points) by minimization of the covariance matrix.

One intuitive example (linear)

when you are trying to find the parameters of a straight line, you would want to measure points that are spaced furthest from each other apart
and you want to include the ends in particular.
If you would include a bunch of points that are close to each other you would get a scatter of points that would result in a big error for the line



That kind of thing I would love to investigate because it is quite universal and I know I can do it.
But I know also that where ever I work people are going to hate this,
because they dont understand it
(or those who do wouldnt waste there time on it, because it is not within their scope, their area)
They use to be caught in their own area kind of thinking.

Any mathematicians or physicists (or others) here, that are interested in that?
I planned to use this for either EIS (electrochemical impedance spectroscopy)
or for Gibbs energy models with Redlich Kister type of excess Gibbs energy
Including some experimental data, maybe.


My background is material science/chemistry but I have used a lot of optimization (Levenberg Marquardt in particular) to fit experimental data to models.
And I am simulating also quite a lot. Diffusion convection semianalytical in 1D

Some time I had that idea to optimize not only the parameters but also the experiments

Might be that it is very demanding because of numerical limitations, but who knows

Unfortunately I am not a mathematician so I dont know is there already something like this out there.

Any comments? I guess this question is either really too weird, or eventually there are aspies here that get the point what I mean
and I hope are interested and can provide me with some background information

This is really a very good example about how it is not supposed to be done Completely useless

Huh?

The Best Square is the Least Square.

ruveyn

I like squares, too. And least squares is involved here, too. You're damn right.


To explain a little more

The sense is, where to put the points on a line (a line that doesn't have to be straight
or could be also a surface) to get the parameter errors resulting from the fitting smallest

The errors in the parameter determination depends on this matrix, the variance covariance matrix.
Making its numbers small (by any means) will also make the results better.

It is derived from the derivative of the function to fit by its parameters (jacobian) and can be calculated quite easily.

See for example http://en.wikipedia.org/wiki/Levenberg–Marquardt_algorithm

The covariance matrix is in that language JT*J*S(beta)/(number of parameters - number of measurement points)
S=sum of squares (of errors), beta the parameters and J the jacobian. T is a sign for matrix transpose

That thing is the jacobian
http://en.wikipedia.org/wiki/Jacobian_m ... eterminant

where xi are the parameters and m the point of the function to fit (time temp or f) differentiated by the parameter.
For each parameter one column, for each datapoint one row.


The common is to reduce the sum of squares S(beta) by reducing measurement errors.
But also JT*J has an influence. You can choose different datapoints=f(temperature time frequency).
My idea is to make the best possible choice here

So, in this case this is putting the points on the line in right place(measuring results for the right temperatures, times, frequencies).
Thats the whole idea. This you get from the simple example + a little imagination:

Try to put a straight line through a circular cloud of points and you will see it doesn't work out (the line can go into any direction).
If you take a "long" cloud of points you get much better results, even with the same sum of squares (the line is much more clearly defined)

Sad that there is no picture upload here, I would have used it.

Anything clearer?

You can place a picture on your own blog / website, upload to imgur or find one from Google etc, and paste the URL in here.

There are some biological experiments that optimize the data, creating large numbers of hybrid organisms with combinations of mutations. There are experiments in pharmacology that create and test many (thousands) of candidate compounds simultaneously. They aim to minimize non-useful outcomes prior to analysis.

I recently used a method for estimating future demand where the final state was unknown, but used the best guess as a weighted data point, a magnetic point in the optimization. The estimated future demand would tend towards the guess until sufficient real data over-rode this magnetic point. The outcome was a smooth change in estimated demand that was more acceptable to real sales managers than the wild variations of a strict optimization process.

My personal favourite algorithm is Simplex http://en.wikipedia.org/wiki/Simplex_algorithm which resembles the grazing-path of some organisms:

WP FAQ (item 12): http://www.wrongplanet.net/postt32554.html and also the longer explanation a few posts from the end of the thread.

Hei thx, I will answer separately to this, because this will be a bit longer I guess.



Hi, thx for your input.

-----------------

Here comes the picture (generated by MATLAB) about the simple example

[img][800:420]http://img801.imageshack.us/img801/6487/examplese.png[/img]

Uploaded with ImageShack.us

Original equation y=0.3*x
200 points, random noise (uniform distribution) : x+-0.05 y+-0.05 (exactly the same noise for both "clouds")

"Clowd"(left) y=a*x+b a=0.3253+-0.0748 b=-0.0118+-0.0374

"Long Clowd"(right) y=a*x+b a=0.3004+-0.0073 b=0.0006+-0.0042

red line: fit
black lines: +-1 sigma confidence interval

Well, obviously extrapolation is quite bad, nothing really new.



But if you have a nonlinear function(extrapolation is still bad) then this can be really useful not to measure points that are not so relevant.
This can also involve experimental errors (avoiding regions for which measurement has high errors)
And finding the actual best points to measure by changing the ordinates (x values)

If you measure one by one then you could proceed the following:
1) measure a few points
2) optimize with error based weighting
repeat
I) minimize covariance matrix by choosing right new inserted x value,
predict y and y errors by neightbour points (by equation that you fit to)
there could be some predictive optimization here as well
II) measure 1 point (and evtl optimize the real problem)
until good

Or
1) You know the equation
2) You know the measurement errors in X and Y and roughly the values that you are going to measure (y1..yN, abscissa), or the parameters are roughly known
3) minimize the covariance matrix by changing all N ordinates (x1..XN)

Last edited by onks on 03 Sep 2012, 4:53 pm, edited 1 time in total.

Is this like estimating from real data an extrapolated point, for which you assign the error as a weighting in a second model?
So to say "extrapolated error propagation" to another model? The best guess cant come from within the same model, or could it?



Seems like Simplex does a good job, although I am not so into its theory. My favourite is Levenberg Marquard.
But what I dont like are the numerical problems that arise from inverting the hessian approximated by the jacobian (or solving the linear equation systems, near singular matrix).
Bad are also non analytical jacobians, because they are inacurate.

Then I like separable nonlinear least squares, where the linear factors are determined from a linear equation system.

Many optimization tools have silly stopping conditions. They stop before the optimum can be found. E.G. when parameters change is small.
But actually you can be still quite far away from the optimum and just at a very sloppy plateau.
If you would have a better stopping criteria choice then you could maybe get the solution better.

If you program it by yourself then you can do it.

The time that you might loose by inefficient trails are nothing compared to gained precision, because my problems have really small amount of parameters.

My former colleague used multiple precision to solve numerical issues during optimization. And concluded that for his problem 1024 numbers are needed to be precise and fastest.

Do you get the idea about minimizing the covariance matrix?

And do you have any clue if anybody has tried something like this before?

Yes, the best guess must come from a separate source. In the model I described, the best guess is a combination of historical data for previous products and intuition. The resources to produce and promote the product are of the order of a million dollars, but the profit or loss is of the order of thousands. Strict optimization would direct sales staff to dedicate additional millions in resources or cancel the product on a moment-by-moment basis, at least in the early stages.



Whatever metric you choose to minimize, the outcome will minimize the covariance matrix. Some methods will do so more directly, others less directly. I have seen simulated annealing applied to minimizing the area of silicon used to place integrated circuitry without calculating any other metric than total and unused area.

Take a look at candidate compound screening methodologies, like http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2242414/

Interesting. Quite demanding. So you have to basically do everything to find the minimum. Otherwise you are quite at risk that you overestimate/underestimate something.
One good thing is of course that also the market doesn't always go the way "to the minimum". So if there is some plateaus there, then it is not likely that the market will spend dangling around there very long for finding again a further away minimum.

Probably also the way there is quite important, not only where the minimum actually is. Market is far from equilibrium positions and the number of trials is much smaller than in thermodynamics.

What about a kinetic approach (rate based proceeding into meta stable states that last for long time)?

This is not a directly obvious argumentation type, but probably you can relate it.
Simplex seems almost ideal for it. Doesn't it branch out and return every now and then?

Do you like monte carlo based optimization (I have seen it work in Excel and it worked)? Or do you have too many variables to try out everything?

You have a really demanding thing there under work... .And I guess that's why you like it.
Quite a responsibility, though.
And all your models are more or less empiric. Interesting and frightening sometimes as well, I think.

So, what really intersts me also is, whether this methods works well.
Or did you also sometimes also have real problems that the reality behaving totally different than what you expected
without that your risk analysis was capable of estimating the risk adequately and your company ran into a severe loss?



Thx for that tip. Took a glimpse on the article. It is about optimizing protein structures. And there, I know, global optimization is needed.
That is a really good point I have to also think about. (That there might be many minima). Haven't yet dug deep into this article, though.

Yeah of course you will also minimize the covariance matrix by minimization.
Because, if you minimize the square of errors, you also minimize the "scaling part" of the covariance matrix.
The nearer you are the minimum, the smaller the parameter error, as well.

But this counts only for a certain set of ordinates and parameters

cov=(JTJ)^-1*SS/degree of freedom,

right (for levenberg marquardt)?

I want to also minimize the matrix part (JTJ) of the covariance matrix by choosing the right ordinates and not only the sum of squares
JTJ depends on the choice of parameters(p1..pM) and ordinates(t1..tN):

J=

df(p,t1)... df(p,t1)
dp1.........dpM

df(p,t2)... df(p,t2)
dp1.........dpM
. .
. .
. .
df(p,tN)... df(p,tN)
dp1.........dpM

P.S. The jacobian looks a bit weird, just difficult to draw df/dpi is just the derivative of f in pi's direction

Last edited by onks on 11 Sep 2012, 1:34 am, edited 1 time in total.

Ok now I figured out a very important detail, which went wrong before.

And that is that usually only errors in the abscissa (y values) are considered which means that usually we have the following system

case 1:

x=x*
y=y*+random error

where *x/*y represents the true values without error

In reality, however, we have a system that is

case 2:

x=x*+random error
y=y*+random error


Case 1 is solved by the common least square methods, where only the error in y is minimized, to find a minimum of S





where it is assumed that x is error free, which is however normally not the case.

Now, this puzzles me because, how many people just use this assumption without hesitating and calculate the simple linear regression type of results???

Case 2 is really different, because there you also minimize the error in the ordinate (x) on top of the errors in the abscissa (y), this is called deming regression
copied a few equations from the wikipedia article (for the simple linear case, though)







So my example I showed here was wrongly analysed, I'll have to correct it.

But still I think there is some advantage in a method, where you can choose data points ordinate(s) such that your results are best (by for example minimizing also the covariance matrix's matrix part)

Would a weighted optimization work? The weighting is often a simple function like y or log(y), but it can be any other function of y, or any other available data related to the points.

Have you used the R statistics language and environment? (http://www.r-project.org/) R runs in a nice interactive shell in Windows or in a variety of hosts like Gedit in Linux. It is free and the source code is open, so you can find a wide range of optimization and non-linear regression routines written in R and modify them. Most of the routines I have used return the fitted parameters, but also a massive collection of data to inspect the results that are not available in most statistics packages.