6
$\begingroup$

I have a vector of desired values that I want to fit based in some generated predictors. The tricky part is that I wish to have the explicit formula. For example, giving the below input I would like to get the following formula

Input:

Y=[1,2,3,6,7]
X=[1,2,3,4,5;0,0,0,1,1]

Output:

Transf={'multiply',1,'transform',linear;...
'multiply',2,'transform',linear}

Y=Transf(X) %which would be equal to: Y=1*X(1,:)+2*X(2,:)

This is a not so complicated linear regression. but generalizing it could give, log transforms, sin, cosin, roots, exponents.

What software could I start with? Or how might I implement this?

Improve this question
$\endgroup$
  • $\begingroup$ Could you clarify what it is that you mean by "explicit formula to access to what extent it makes sense"? Makes sense in what way? And what is it that you want to generalize to give logs, exponentials, etc? $\endgroup$ – rocinante Mar 4 '15 at 20:18
  • $\begingroup$ @rocinante I edited the question. I hope is more clear now. $\endgroup$ – ASantosRibeiro Mar 4 '15 at 20:28
  • 4
    $\begingroup$ Did you see Eureqa? $\endgroup$ – Aksakal Mar 4 '15 at 20:41
  • 3
    $\begingroup$ @Aksakal I did not known it existed as I had not been able to formulate the search. It seems it is called symbolic regression. I will try it and come back to this point if it makes sense. $\endgroup$ – ASantosRibeiro Mar 4 '15 at 20:45
  • 2
    $\begingroup$ @Aksakal apparently some progress has been made towards a free alternative: scicomp.stackexchange.com/questions/14818/… $\endgroup$ – shadowtalker Mar 4 '15 at 23:49
7
$\begingroup$

In addition to nice answer by @DankMasterDan (+1), I would like to share further information on the topic. It seems that an approach that you're looking for is symbolic regression. It seems to be closely associated with and usually is implemented via evolutionary algorithms, such as the most popular genetic programming (GP). However, other approaches are also proposed, especially in relation to analytical models of physical systems. For example, see a paper by Shmidt and Lipson (2009), published in Science. By the way, this small open source Java-based project presents an implementation of the above-mentioned approach.

In terms of software, available for symbolic regression, before I concentrate on my favorite open source solutions, I'd like to mention that Eureqa is definitely an interesting product, which has grown from an open source project. However it is quite expensive, as many commercial statistical or machine learning solutions, available on the market today.

I will start a brief review of open source solutions with a hybrid solution GPTIPS, which is an open source plug-in software for commercial MATLAB. It is referred to by authors as a "symbolic data mining platform for MATLAB".

Now, turning to a full open source software, we can find several IMHO very interesting solutions. A well-known language-agnostic (but still Python-based) system SageMath offers symbolic regression functionality via SymPy Python library, which can also be used independently as well. Another very interesting comprehensive open source software system is .NET-based HeuristicLab. While HeuristicLab is labeled "a framework for heuristic and evolutionary algorithms", it offers a much wider range of functionality beyond symbolic computations and evolutionary/GP solutions.

In addition to already-mentioned SymPy libarary, Python ecosystem offers DEAP open source project, where DEAP abbreviation refers to Distributed Evolutionary Algorithms in Python.

My brief analysis of open source software for symbolic regression and related solutions would be incomplete without mentioning what my favorite R ecosystem offers in that regard. An interesting R package for GP and symbolic regression is rgp (available on CRAN), which is referred to as "R genetic programming framework" (RGP). The RGP package is a part of a larger set of open source tools for symbolic computation in R, developed under the umbrella of a larger Rsymbolic project. There are also several optimization-focused GP packages (http://cran.r-project.org/web/views/Optimization.html), however it is highly unlikely that they offer symbolic regression functionality out-of-the-box, as RGP package does.

References

Schmidt, M., & Lipson, H. (2009). Distilling free-form natural laws from experimental data. Science, 324(5923), 81–85. doi:10.1126/science.1165893 Retrieved from http://creativemachines.cornell.edu/sites/default/files/Science09_Schmidt.pdf

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ this answer provides a good overview of the solutions to the problem above. I did tried Eureqa which is definitely a solution for my problem (yet did not really gave what I wished). As I am a MATLAB programmer I will try the GPTIPS to see whether I have more flexibility in defining constraints $\endgroup$ – ASantosRibeiro Mar 5 '15 at 10:38
  • $\begingroup$ @ASantosRibeiro: I'm glad you liked my answer and found it helpful. Good luck with GPTIPS! $\endgroup$ – Aleksandr Blekh Mar 5 '15 at 11:27
2
$\begingroup$

It sounds like your goal is to find an arbitrary function g(:) such that y=g(x).

The answer to your question depends on what you mean by explicit. Specifically, you should note that there are an infinite number of ways to specify any function g(:), for example g(x)=x on -1

If by 'explicit' you mean find a a g*(:) which is functionally equivalent to g(x) - ie gives the same output of g(x) for all values of x then yes, there are many ML algorithms which can do this for arbitrary functions g(:). These algorithms could give you perfect predictive power from x to y, albeit at the possible expense of overfitting the data. They include SVM with RBF kernels and decision trees (ie any algorithm w/ infinite VK dimension).

However, if by explicit you mean the SIMPLEST g(:) which describes y=g(x), then things get much more complicated because simplicity/sparsity/complexity is a human notion which can only be quantified very clumsily. For example, in theory, SVM regression w/ rbf kernel could perfectly fit y=sin(x), but it wouldn't output g=sin(:) but rather an uninterpretable series of coefficients, and you would have to do the work to piece them together into 'sin(x)'.

Now done with that theoretical mumbo-jumbo, I think a good way of getting started is to fit the the data with a taylor expansion as this is at least somewhat interpretable.

Good luck, hope this helps!

Improve this answer
$\endgroup$
  • $\begingroup$ definitely a number of functions will be able to match y. yet, if one constrains the length of the solution less options will be available. what i meant is what is described as symbolic regression. $\endgroup$ – ASantosRibeiro Mar 5 '15 at 10:34
2
$\begingroup$

I strongly prefer Mathematica for such tasks. Given data of the form $mydata = \{ \{ x_1, y_1 \}, \{ x_2, y_2 \}, ... \}$, one searches for the unknown parameters such as $a$, $b$, $c$, and $d$ in a non-linear function of your choice in this way:

NonlinearModelFit[mydata, {a + b x + c x^2 + d Sin[x]}, {a, b, c, d}, x]

The symbolic output is 

FittedModel[2.8 + 1.075 x + .292 x^2 + 4.9 Sin[x]]

A plot of that nonlinear model and the data looks like this:

enter image description here

You can put in as many basis functions as you like, and some may be "fit" with $0$ coefficients and such. Of course, too, you need more data points than free parameters for your fit to be meaningful.

Improve this answer
$\endgroup$
  • $\begingroup$ Mathematica is definitely a nice piece of software. However, it's rather expensive. For those, who can't afford it, is cost-conscious or simply prefer open source solutions :-), SageMath, which, among other options, I've mentioned in my answer, seems to be a reasonable alternative. $\endgroup$ – Aleksandr Blekh Mar 5 '15 at 3:47
  • 1
    $\begingroup$ The student version of Mathematica isn't too expensive. My view is that if a software tool makes you 10% more efficient than another (and Mathematica makes me 50% more efficient than other tools), then it is worth it. But of course, everyone has different values and desires. $\endgroup$ – David G. Stork Mar 5 '15 at 3:56
  • $\begingroup$ I don't pay much attention to student versions of software, as their lower prices are just a fast road to a vendor lock-in. However, I understand your point and agree with you on this. Sometimes, it makes sense to prefer less open solutions, if they offer enough benefits versus alternatives. $\endgroup$ – Aleksandr Blekh Mar 5 '15 at 4:07
  • $\begingroup$ I think this is solution misleads the reader. Any routines that solves a non-linear least-squares curve fitting problem will do. We did not discover anything; eg. why not use log(x) or x^3. We simply defined a small optimization problem to solve, R 's nls would do the same, MATLAB's lsqnonlin would do the same, scipy's curve_fit would do the same. No formula discovery here... $\endgroup$ – usεr11852 Mar 5 '15 at 4:08
  • 1
    $\begingroup$ One always approaches such a problem with a prior (explicit or implicit) about the basis functions one wishes to consider. Are you really accepting as candidates Ackerman's function, or Hypergeometric function, the inverse of the Jacobi Elliptic Function, the derivative of the even Mathieu function, and so on? Even genetic programming methods require the modeler to provide a set of basis functions. In the approach I outlined, you can specify a larger set than will ultimately be found, and hence is hardly "trivial" at all. In fact, it is the technique used by experts. $\endgroup$ – David G. Stork Mar 5 '15 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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