7
$\begingroup$

Which general machine-learning methods are there that try to "learn" or interpolate a smooth multivariate function and which get to actually choose the points at which the function is evaluated during the learning process (exploration)?

The idea would be that each function evaluation is more or less costly and the algorithm learns to explore the regions of space where the gain of knowledge is greatest (vs. the cost of evaluating the function). The function may be non-analytic (e.g. with kinks) in the most interesting cases.

My background is physics, and I am sure that such methods exist, but despite some searching I could not find something that is directly relevant, possibly because I do not know the right terms to look for. I only know that more broadly speaking 'reinforcement learning' is the area of AI dealing with exploration and rewards, so maybe the methods I am asking for represent some special case of that.

For clarification, here is an example: You might want to get the phase diagram of a substance, i.e. the density as a function of pressure p and temperature T. So we are dealing with a (mostly) smooth function of two variables (p,T). Its evaluation at any given point (p,T) requires an expensive Monte-Carlo simulation (lots of CPU time; how much even depends on where in the p,T-space you are). The ideal algorithm would judiciously pick points (p,T) at which to evaluate the density, trying to go towards regions where the function has the most salient features (e.g. phase transition lines, i.e. non-analyticities). Then afterwards, when you ask the algorithm for the density at any other point (p,T), it provides the best possible interpolation/extrapolation that it can come up with, given all the information it has acquired during its exploratory phase.

$\endgroup$
  • $\begingroup$ If indeed it turns out this question has not been addressed very much, that would also be a very useful information for me. I can definitely think of many possible applications (in physics, and computational science in general). But given all the effort in 'intelligent agents' that explore some unknown environment, one might hope that people have analyzed situations where this environment is an unknown smooth function (a hilly landscape, so to speak). $\endgroup$ – Florian Marquardt Oct 31 '15 at 21:54
  • $\begingroup$ I just added a typical application example, to clarify. $\endgroup$ – Florian Marquardt Oct 31 '15 at 22:04
  • $\begingroup$ fyi phase transitions you describe are highly discontinuous/ chaotic/ fractal in their (possibly "narrow") "centers" so the idea of this overall being a "smooth function" is possibly quite inaccurate/ misleading. $\endgroup$ – vzn Nov 3 '15 at 0:03
  • $\begingroup$ @vzn: While the microscopic dynamics in a usual many-particle system is indeed chaotic (which is important for thermalization), the resulting average thermodynamical properties are smooth functions of parameters, except when they jump (or have other non-analyticities) at phase transition lines. For example, on the liquid-gas phase transition line in the (p,T) plane, there is a jump in density. $\endgroup$ – Florian Marquardt Nov 3 '15 at 22:21
3
$\begingroup$

I would look into the field of "optimal experimental design" in bayesian inverse problems, particularly the recent work of Alen Alexandrian.

http://arxiv.org/abs/1410.5899

http://www4.ncsu.edu/~aalexan3/research.html

Essentially, one has an inner inverse problem for approximating the function based on point measurements of derived quantities, hosted within an outer optimization problem for choosing the points based on minimizing a combination of the error and the variance.

Furthermore, you don't need to do a full inner-outer solve procedure. Rather, you can use the KKT conditions for the inner problem as the constraint for the outer problem, and formulate a "meta" KKT system for the combined problem.

It is formulated in the language of PDE-constrained inverse problems, but would also apply to simpler situations like your problem (the "PDE" becomes the identity matrix..)

$\endgroup$
  • $\begingroup$ Thank you! From the bit I read, I guess most of optimal experimental design is concerned with stochastic data, so I still would have to understand how this specialises to a deterministic smooth function. $\endgroup$ – Florian Marquardt Nov 1 '15 at 9:08
  • $\begingroup$ It is common to use Bayesian techniques like this even when the true answer is deterministic, by considering one's own uncertainty about the answer as stochastic element. Whether you like using probability like this or not pretty much comes down to whether you are a Bayesian or frequentist; it's a very contentious point among statisticians... Anyways, if this doesn't bother you then I would suggest a gaussian random field with the inverse laplacian as the covariance as the prior, to give higher probability to functions that are smooth. Ie, $\pi_\text{prior} (f) \sim \exp(-f^* \Delta^{-1} f)$. $\endgroup$ – Nick Alger Nov 4 '15 at 2:23
2
$\begingroup$

Active learning is a term used in the machine learning literature for the situation where the learning algorithm is allowed to interactively query the value of the function on certain points. I don't know if there are existing algorithms in the literature for active learning of smooth multivariate functions, but it sounds like that's what you want. You could spend a bit of time with Google Scholar looking for work in this area.

You could also look at optimal experimental design.

$\endgroup$
  • 1
    $\begingroup$ Thank you! Going through the Wikipedia page, I found the Active learning website of Burr Settles, and the associated literature review. From a first reading, I gather the typical examples have a discrete function (labels for classification). So I still need to find something about smooth functions, although maybe that is just a simple variant of what they say (easy to translate for the expert, not so easy for me right now). $\endgroup$ – Florian Marquardt Nov 1 '15 at 9:03
-2
$\begingroup$

genetic algorithms can be used for this purpose. in some cases the fitness function evaluation is somewhat "expensive". part of the difficulty is encoding some kind of measurement of "interesting regions" and this metric would somehow have to quantify measurements over multiple function evaluations ie a single function evaluation is not enough to "notice a trend". ie:

the algorithm learns to explore the regions of space where the gain of knowledge is greatest

and later you call it "finding most salient features". this statement is problematic because it is generally hard to mathematically quantify "where the gain of knowledge is the greatest" or "salient features". one possibility to formalize/ quantify it is to consider "high-entropy vs low-entropy" for which there is a large body of theory.

your problem is also somewhat split along the lines of supervised vs unsupervised learning so thats an area to further analyze wrt your problem.

a recent major case of successful application of ML in physics was the Higgs machine learning challenge and incorporates many of the ideas you mention. in this case particle track behavior is predicted by the ML algorithm and it automatically learns about noise vs signal in the data. winning algorithms generally used decision trees as described in the paper.

$\endgroup$
  • 1
    $\begingroup$ Thank you, but it is unclear to me how what I am asking for can be phrased in terms of a genetic algorithm (even in principle), maybe you can elaborate? $\endgroup$ – Florian Marquardt Nov 2 '15 at 23:01
  • $\begingroup$ dont know what part is unclear. its all implicit in basic genetic algorithm theory as sketched out in the answer/ links (try following some). can elaborate further/ at length in Computer Science Chat. (by the way, some algorithms to "map out" fractals have a similar structure as you describe, eg mandelbrot set visualization etc.) $\endgroup$ – vzn Nov 2 '15 at 23:55

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.