Allow LevenbergMarquardt Optimizer to use Generics (Lists)

[kicOLD]

In todays programming the number of measurements is not allways known upfront. Therefore people will use Lists. To avoid cast and copy tasks it would be cool to provide a gerneric optimizer supporting lists. Also I would like to reuse the same optimizer whenever new data arrives with minimum of cost (i.e. restarting threads etc.). And I it is useful to know the error for the best fit, so I added a getter method for it.

Maybe you would like to merge this class.

Cheers KIC

PS Maintaining should be an easy one sice the task is only to replace targetValues[index] by targetValus.get(index).doubleValue() - which could be done by find and replace.

[cfries]

Thank you for that. I see the following issues with the class/implementation:

Code duplication: There is a huge amount of code duplication which should be avoided. The code duplication is a problem also because improvements of the internal LM algorithm now have to be copied to the LM. Of course, an option is to drop the original class, but the use of List<T> introduces a bigger performance hit (see below), hence I would like to keep the original double[]-version (at least for a while). Apart from some aspects as the reuse of the thread pool (I will comment on that below), it is possible to implement your class much more concise, e.g. like

LevenbergMarquardtGeneric<T extends Number> extends LevenbergMarquardt

and just add constructor and setters which convert from List<T> to double[]. This would remove the requirement to „maintain“ the two implementations in sync (maintaining the sync manually is a no-go).

Pseudo Genericity: A main feature of your code is the generic type T extends Number. However, the Levenberg Marquardt algorithm does not work for T being an integer type. The only possible types for T for which the solver works are T = Float and T = Double. Internally your code uses a Number.doubleValue() to convert to double (that is, the use of the generic type is restricted to the constructor arguments). Using T = Float would actually be a performance loss. Note that the object function setValues still operates on double[], because it would not make sense to have it operate on an integer vector (being non-differentiable). Given that the generic type is only used at construction, that could be provided by suitable constructors (a single additional constructor with List<Number> arguments).

Performance: You use List<T> in the internal data model. An internal conversion from List<T> to double[] in every iteration (!) will likely result in a huge performance hit. It would be much better to just add support for the List type on the constructor level (see Code duplication above). Note that from the documentation of List, we have that List may perform poor when using get(int index):

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation. Source: http://docs.oracle.com/javase/7/docs/api/java/util/List.html

Reuse of the Optimier: The reuse method is dangerous since in future version it may happen that a developer forgets to reset an internal state (like the current error) of the solver. For that reason I prefer to just create a new solver with a clean state. This would limit the „re-initialization“ code to the clone() method - which is much better practice. From an optimization point of view the use case of reusability is to use the previous bestParameters as initial guess. Hence this can be achieved by one line

LevenbergMarquardt newOptimizer = optimizer.clone();
newOptimizer.setInitialValues(optimizer.getBestFitParameters());

So picking up your suggestion of a re-use, I implemented that clone method (just a few line) to achieve that (hope that suits you).

Reuse of the Thread Pool: This is a good point. Reuse of the thread pool was already part of an earlier version of that class e.g. in the Java 8 version the implementation used the Java 8 streams and the commonPool(). However, I removed the feature from the Java 6 and Java 8 version because there may be situations where you do not like to use the same pool. There may be issues (e.g. with blocking operations). For the time being I believe that a good compromise would be to offer the option to set the thread pool on the constructor level, i.e., allow the use of an externally provided ExecutorService. Hence the user may set it to a shared pool if he likes. I will rather go for that option in the LevenbergMarquardt class.

Reuse with modified target value I understand that you have a special use case, where you would like to add new target values by reusing it. Thanks for suggesting this. I have that use case too and I would suggest to focus on the that use case: Since I favor a more modern Scala-like object-functional programming paradigm I would prefer to keep the optimizer immutable (except for a builder like use of setters upon initialization) and add a single method

getCloneWithNewTargetValues(double[] newTargetValues, double[] newWeights)

which reuses the previous best point as initial guess. Would that suit you too? We could then just provide a convenient wrapper method

getCloneWithNewTargetValues(List<Number> newTargetValues, List<Number> newWeights)

making the conversion from List<Number> to double[].

Next I have the question if you also require a clone with new parameters (i.e. new initial values, where you change the number of parameters from n1 to n2 (n2 > n1). This is a completely different thing, since it requires a mapping from the previous parameters to the new parameters. I believe that such a mapping should be done outside, since it depends a slot on the specific use case. (I do such a mapping in the Solver class of the curve calibration).

If the changes to the original class do not suit you, I would prefer to implement improvements by extending or wrapping (instead of code duplication).

I am sorry if my answer looks like criticism, but in fact I really appreciate your suggestion (especially the one with re-constructing with new target values). As the length of my answer indicates, I thought about that. I believe that there might be a cleaner way to achieve that. Please check revision 1157 or later of the LM solver. It contains the clone and the getCloneWithNetTargetValues-method.*

[kicOLD]

Pseudo Genericity: A main feature of your code is the generic type T extends Number. However,
the Levenberg Marquardt algorithm does not work for T being an integer type. The only possible types for T for which the solver works are T = Float and T = Double.

And every class which extends Number which is the case for my measurement class.

Reuse with modified target value

Ideally the last best fit is the new initial value. Imagine that I have measurements tick by tick, for every new value in a linked list, I just remove the oldest value and do a new fit. the propability that the new fitted parameters are near by the last best fit is very high.

D’accord with any other point.

[kicOLD]

Two things I would ask you to do please:

1.) I really would like to see List of Number since Double is final and Number is not. So many classes can extend Number. Maybe you mention the call of Number#doubleValue() in the javadoc so anyone knows what is going on there and if one can have a performance issue.

And as you can see in the java source, using Double#doubleValue() is doing exactly what "ArrayUtils.toPrimitive()" does:

http://grepcode.com/file/repo1.maven.org/maven2/commons-lang/commons-lang/2.3/org/apache/commons/lang/ArrayUtils.java#ArrayUtils.toPrimitive%28java.lang.Double[]%29

And here is what the Double#doubleValue() method does: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/Double.java#Double.doubleValue%28%29

In fact that is the same as unboxing.

2.) I am not sure if this is really the most optimized way of converting a List to an Array of primitives

clonedOptimizer.targetValues = ArrayUtils.toPrimitive(newTargetVaues.toArray(new Double[0]));;
}

Since you loop and allocate memory twice for the whole list. First you allocate ram for a Double Array and then for a double Array and loop each iterable. It would much be more efficient to loop and convert by yourself:

clonedOptimizer.targetValues = new double[newTargetVaues.size()];
int i=0;
for (Number n : newTargetVaues) clonedOptimizer.targetValues[i++] = n.doubleValue() // see 1.) why it is ok to use doubleValue
}

Thank you very much.

PS You do not have a constructor for List, is it safe to use "new LevenbergMarquardt(4).getCloneWithModifiedTargetValues(...)" ?

[cfries]

Dear Christian.

Thanks for getting back. Please excuse the delayed reply.

I added a constructor which consumes List in place of double[] and the getCloneWithModifiedData now accepts List instead of List.

I also changed the conversion from List to double[] to s.th. which might be a bit more efficient - as you suggested.

I hope this suits you. Thank you for your contribution.

Best Christian

• I assume that was clear, but my biggest concern with the original pull request was the use of List to double[] conversion in every iteration. I am fine with the use of List on the constructor level. In case you really need the objective function in a List version that could be implemented with an anonymous class deriving from the LM solver - if that is OK for you.