0
$\begingroup$

I have a dataset composed of $N$ iid observations ($x_1, x_2, ..., x_N$) and a function $f(x_i,\, i{=}1,..M$) that takes as input a subset of fixed length $M$ of unique elements from the original dataset (where $M{<}N$ and it is known). This function is basically a comparision of two kernel density estimators (one is always fixed, the other is generated with the elements in $M$), where the exact same value is returned for the same input values. I need to find the subset $M^*$ that maximizes $f(x_i)$.

I can think of a few strategies:

  1. Process all the possible subsets of length $M$ that can be created from my $N$ observations, evaluate all of them in $f(x_i)$, and keep the one that gives the maximum value. This is prohibitively time-consuming for even small numbers of $N$ and $M$.
  2. Process only a random subset out of all the possible combinations defined above, keep the one that gives the maximum likelihood value. This is the easiest method, but I'm not sure how large the random subset of combinations should be to get a somewhat meaningful (trustworthy?) answer.
  3. Use some optimization/MCMC algorithm? This is the option that seems more reasonable, but I'm not sure which one is best suited for this task.

Which method would you recommend?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What can you tell us about the function f? Do you have a closed-form representation of f? For any given input combination, will it produce a deterministic, o.e., perfectly repeatable, answer? $\endgroup$
    – Mark L. Stone
    Commented Jun 11, 2018 at 14:53
  • 1
    $\begingroup$ As @Mark indicates, everything depends on $f$. Until you can tell us something about it, there's little one could add except to refer you to a textbook on combinatorial optimization. $\endgroup$
    – whuber ♦
    Commented Jun 11, 2018 at 15:27
  • $\begingroup$ I've added what Mark asked about $f$. $\endgroup$
    – Gabriel
    Commented Jun 11, 2018 at 16:09
  • $\begingroup$ I don't understand the question because the notation is vague: what exactly does "$f(x_i)$" refer to? A value of $f$ at a specified observation? The set of values of $f$ at all observations? The function $f$ itself, where $x_i$ is intended to refer to an arbitrary element of its domain? If $f$ is a KDE, then apparently your notation implies "$f(x_i)$" is function, rather than a number, so what does it mean to maximize it? $\endgroup$
    – whuber ♦
    Commented Jun 11, 2018 at 20:35
  • $\begingroup$ $f(x_i)$ means the function $f$ evaluated using $M$ elements from my dataset. It is a shorter version of the more explicit form shown above: $f(x_i, i=1,..,M)$. Not sure how else to put it. $f$ is not a KDE, but a comparision of two KDEs (one of which is generated using the $x_i, i=1,..,M$; the other one is fixed), hence it is a real number. $\endgroup$
    – Gabriel
    Commented Jun 11, 2018 at 21:09

1 Answer 1

Reset to default
1
$\begingroup$

Do you actually need to find the best subset or do you simply need to find a hopefully good enough one?

If the former you are basically stuck with 1., unless you have some more information about the precise function you have to optimize.

If the latter, you will probably want to go with something like 3. The choices here are many, but a good starting point might well be something as simple as a coordinate ascent method or simulated annealing. Again, this is if you don't have any specific information about the function you're given.

Improve this answer
$\endgroup$

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