1
$\begingroup$

My goal is to hit all of my 'targets' through a random variable $Y : [0,1] \rightarrow \mathbb{R}$. An explicit form of $Y$ is unknown but I am able to take a sample point as pass it to $Y$ and get its output.

Specifically, I am initially sampling points uniformly on $[0,1]$. For each sampled point $x_j$ I can compute $Y(x_j)$ easily (and repeated evaluations of the same $x_j$ will give the same output). I also know that outputs should be close with respect to input: $\mathbb{P}[Y(x_i) = Y(x_j)]$ should be roughly proportional to $|x_i - x_j|$.

Suppose $\{ T_j : 1 \leq j \leq m\}$ are my targets. I know that my random variable will necessarily map to one of these targets: $Y(x) = T_j$ for some $j$ and every $x \in [0,1]$. I want to sample until all my targets have been achieved in the sense that $\{ T_1, \dots, T_m \} \subseteq \{ Y(x_1), \dots, Y(x_n)\}$. Once I know of one point $x_j$ that maps to $T_k$, I no longer care about any future sampled point that also maps to $T_k$. Further, the labels of the targets are arbitrary; for example $T_1$ is no closer or further from $T_2$ than it is from $T_{126}$.

In order to minimize $n$, I want to bias my sampling so that successive samples are 'far away' from the values that were successful, for example if $Y(x_1) = T_1$, I want to actively avoid the region around $x_1$ since it is likely that nearby points also map to $T_1$. An idea I had regarding this is to do a sort of reverse kernel density estimate, whereby I can create a density $f$ based on the first point that hits a target and sample from a normalized version of $\max(1 - f, 0)$.

I'm not super familiar with sampling techniques, so if anyone can direct me to some theory that can do what I am seeking it would be greatly appreciated. I am also open to totally different methods of solving my problem.

$\endgroup$
10
  • $\begingroup$ The problem doesn't quite make sense yet. What's the relationship between the value of $X(x)$ (which, by the way, would be much clearer as $f(x)$) and whether or not a particular $x$ value is in $T$? Are the $T$ the local maxima of $X(x)$, or something? $\endgroup$
    – Eoin
    Mar 6, 2022 at 22:48
  • $\begingroup$ It's also not clear what "achieving a target" or "success" mean here. $\endgroup$
    – Eoin
    Mar 6, 2022 at 22:52
  • $\begingroup$ Depending on what you're actually trying to do, the solution may be to look at applications of Gaussian Processes to reinforcement learning, e.g. gdmarmerola.github.io/ts-for-bayesian-optim $\endgroup$
    – Eoin
    Mar 6, 2022 at 22:53
  • $\begingroup$ Thanks for the resource. I agree that my question is somewhat broad and perhaps ill-posed. There is no 'hard' relationship between $X(x)$ and $T$. The exact relationship is highly sensitive to the input. The only knowledge I know is that for values in a neighborhood of $x$, $X$ will map them to the same target with some high but unknown. $\endgroup$
    – Bryden C
    Mar 6, 2022 at 23:00
  • $\begingroup$ So each time you evaluate $X(x)$, it tells you which of the targets that value of $x$ is closest to? $\endgroup$
    – Eoin
    Mar 6, 2022 at 23:02

1 Answer 1

1
$\begingroup$

Begin with uniform distribution $U_0$ on $[0,1]$.

Define a suitable value for $0 < \epsilon <1 $, and $0 < \alpha < 1$.

randomly choose $x_1$, $x_2$ .. until you hit a target.

If from $x_i$ you hit a target, just decrease the probability density by alpha on $[x_i - \epsilon, x_i + \epsilon] \cap [0,1]$ and increase every where else in $[0,1]$ so that you still have a total probability of one. The new probability is $U_1$.

Pick other $x_i$ under $U_1$, and repeat until you hit a target. Following the same plan, you'll get $U_2$, and so on.

Little by little, your probability will concentrate on places where you did'nt found a $x$ that leads to a target. But you may still, with a lower probability pick a $x$ near one other that leads to a taget. If you really want to avoid that, then choose $\alpha = 1$.

By experiment, you will be able to tune $\epsilon$ and $\alpha$ so that you hit the greatest number of target in the shortest time (I suppose this is what you want to do).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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