Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ might or might not be in $T$.

No (known, or practical) algorithm can determine if an element $s \in S$ is in the target set: a human being must give the final word (ie, it is subjective). It is estimated that $T$ has about 30000-35000 elements. I already know $T_1$, a first approximation of $T$, with about 25000 elements. I also already know some thousands of elements of $S$ that are certainly not in $T$.

What I want is a way to approximate $T$ as closely as possible, and present only those elements to a human being. Also, for each new element of $S$, I want to determine if it has high probability of being in $T$ -- and present only those with high probability to a human being.

Now, I describe what I can use to try to approximate $T$.

Each integer $s \in S$ has some labels associated. These can be represented as subsets $L_i \subset S, \forall i \in \{1, ..., n\}$ ($n$ is about 250). These subsets are known, determined by algorithms (ie, I have functions $l_i \to \{in,out\}$ such that $l_i(s) = in \iff s \in L_i$).

Some label algorithms are very fast, some are slow. Anyways, these labels (ie, the sets $L_i$) have already been determined. Some of these labels contain very few (1-100) elements, some contain a lot (100000-150000). Many labels are independent, some are closely related (ie, I know that some labels are subsets of others, I know that some are disjoint, etc).

So, given this framework, what kind of algorithms can I use to approximate $T$? They can be interactive, ie, they could get better after each new approximation of $T$, if this makes the problem easier.

I thought about using a genetic algorithm to determine which labels, when intersected, give good approximations of $T$. However, this can get slow, with a naïve intersection algorithm (ie, suppose $L_1, L_2, L_3$ are to be intersected; if they are all "big" (50000-150000), it can be quite time consuming to calculate the intersection! -- now, imagine a gene that would require to intersect, say, 50 labels...).

How can I speed this, without sacrificing too much the precision?

  • $\begingroup$ Is there any connection between the labels and $T$? (I assume there is). That is - if two integers have the same labels, must the both be either in $T$ or both not in $T$? $\endgroup$ – Shaull Feb 27 '13 at 6:33
  • $\begingroup$ Unfortunately, there's no such connection: for two integers with exactly the same labels, you can have one in $T$ and one not in $T$! Just to reinforce, there's no "automatic" way to tell if an integer is in $T$ or not; only a human being is able to tell. This whole idea of "labels" is to somehow approximate $T$. $\endgroup$ – Bruno Reis Feb 27 '13 at 6:45
  • 1
    $\begingroup$ So what's the point of the labels? You're saying that you are trying to learn an arbitrary distribution without any constraints, and that your hypothesis class is $2^{\mathbb{N}}$, essentially? $\endgroup$ – Shaull Feb 27 '13 at 6:48
  • $\begingroup$ The point of the labels is that, for some sets of labels, integers in the intersection of those labels have a very high probability of being in $T$. The idea is to "approximate" $T$ through sets of labels. Also, note that my universe is not the naturals, but a finite set of integer $S$, with about 200000 elements, as you can see in the first sentence of the question. $\endgroup$ – Bruno Reis Feb 27 '13 at 6:52
  • 2
    $\begingroup$ I suggest you fully define the problem and edit the original post: Of course the set is always finite, but is it bounded? What do you mean by "slowly"? What exactly is the relation between the labels and $T$? Are we given some probability distribution that tells us, for two sets of labels, what is the probability that they are in the same set? Once the problem is well defined, you are more likely to get a good answer. $\endgroup$ – Shaull Feb 27 '13 at 7:56

Your Answer

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

Browse other questions tagged or ask your own question.