1
$\begingroup$

Assume I have $N$ examples of datapoints with $d$ features each and I want to sample $n$ times from $N$ through a sampling function $s$, where $n \ll N$ and $d$ is the same for each datapoint.

Further assume that $s$ selects datapoints such that each new sample must have the maximum distance to the previous sample in feature space. If my goal is to maximally reduce entropy, i.e. learn the most about $N$ by sampling $n$ times, is the sampling function $s$ the best way to guarantee that? Or are there exceptions when choosing the sample that has the maximum distance to previous one in feature space might not be a good idea?

If my question is not well-defined, I appreciate any suggestion for corrections.

$\endgroup$
1
  • 1
    $\begingroup$ The underlying idea should be to estimate the probability distribution of the remaining samples (or it could be something else, say a classifier if you are interested in building a classifier using those samples) and then sample the point at which you are most uncertain. Even though that is a greedy strategy, it works well in practice and under certain problem structure you can also guarantee some optimality results. $\endgroup$
    – sudeep5221
    Dec 4, 2022 at 17:11

1 Answer 1

Reset to default
0
$\begingroup$

Described as you did, the sampling function can end up being deterministic. For example, suppose your $N$ samples are taken as a subspace of $\{0, 1\}^d$, containing the vectors $u=(0, 0, \dots, 0)^T$ and $v=(1, 1, \dots, 1)^T$. Then, if your first sample is $u$, and the distance is the Hamming distance, your function $s$ will sample $u, v, u, v, \dots$, which is deterministic.

Also, I am not exactly sure what you are trying to do. Are you sampling? If not, what are you trying to learn from the $N$ points? If you have no prior information about the $N$ elements, sampling uniformly at random might be the best thing, but I am not entirely sure it is your goal.

$\endgroup$
3
  • $\begingroup$ I see, you are right. It wouldn't be called sampling anymore if it's a deterministic process. My goal is to find the best deterministic strategy to gather n samples in order to train a statistical classification algorithm based on the data I gathered. In other words, I want to cover the feature-space well enough by selecting the most informative data points. $\endgroup$
    – postnubilaphoebus
    Dec 4, 2022 at 16:18
  • $\begingroup$ I am still not sure what you mean. Are you doing unsupervised learning and trying to find patterns in the data (do the points form clusters, ...?). Or are you assuming your datapoints come with labels? Then your task would be to learn how to predict labels, so that when given a new datapoint you can make a prediction. In that case, it would be supervised learning. $\endgroup$
    – adrien_vdb
    Dec 5, 2022 at 7:02
  • $\begingroup$ It is called "active learning" and the idea is to work with as few labels as possible. In the outset, all data are unlabeled. Then, you learn in cycles, where, at the beginning of each cycle, you query an expert for some labels. The goal is to choose the right datapoints from which the classification algorithm will learn the most. There are many strategies to do so, but I was mainly wondering why the greedy strategy for the deterministic sampling function is the best. $\endgroup$
    – postnubilaphoebus
    Dec 5, 2022 at 8:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .