# Machine learning with partially defined labelling using existential quantifiers

I apologize for a vague title, but I know only the basic machine learning jargon. Let's assume that we have domain set $X$ and label set $L = \left\{0, 1\right\}$, but the labelling function $f$ is only partially defined by function $g:P→L$, where:

(1) $P$ is a partition of $X$

(2) $\it g(p) = 0 ⟹ \forall x \in p: f(x) = 0$

(3) $\it g(p) = 1 ⟹ \exists x \in p: f(x) = 1$

The meaning of function $g$ is that for some elements of $P$ all members have label $0$ and for remaining elements of $P$ at least one member has label $1$, but we don't know which is $1$ and which is $0$.

For example: we have boxes of apples with possibly different number of apples in each box. We know which boxes have all good apples (apple with label $0$) and remaining boxes have at least one bad apple (apple with label $1$), but we don't know which ones are bad or good.

Is there a machine learning technique to deal with such partially defined labelling?

EDIT

Let's assume that in boxes of apples example above, a classifier we looking for is: good apples are green and hard, bad apples are brown and soft. As a model of an apple, my lucky guess is a 4-d feature vector with color, hardness, weight and size components. All of the apples are observable, so we can calculate the feature vector for each of them. We know labels for all apples in "good" boxes, but have only an existential statement about labels of apples in "bad" boxes.

After measuring all apples, I look for clusters of feature vectors or run some unsupervised learning algorithm. I will discover 2 distinct classes: (green, hard, _, _) and (brown, soft, _, _). These classes will also satisfy conditions (2) and (3) above, so I will accept (green, hard) vs. (brown, soft) as a correct classifier.

With this procedure in mind, let me rephrase my question. Assuming my guess of feature vector is correct, so in about 10-d vector there are enough significant features for correct classification, the partition set $P$ has 1K elements and the domain set $X$ has 100K elements, what is the correct machine learning technique to use?

• en.wikipedia.org/wiki/Semi-supervised_learning – Emre Mar 1 '17 at 16:07
• @PaulJurczak What exactly do you have in the dataset that you want to learn from? In machine learning, there is always the ground truth, e.g. a training set where you know how many boxes with how many good and bad apples. – horaceT Mar 1 '17 at 18:47
• @horaceT The boxes with apples are precise analogy of my problem. The ground truth is only partially defined, which makes it different from standard textbook case and that is why I'm asking this question. – Paul Jurczak Mar 2 '17 at 9:53
• @PaulJurczak To learn anything with a model, you got to have the ground truth. In your case let's suppose by magic you come up with a model. How do you know it's any good if the content of the boxes are unobserved, or unobservable? – horaceT Mar 2 '17 at 13:43
• What you are looking for might be possible, but it will probably depend on the specifics of your particular situation. Can you edit the question to tell us more? What is the learning task like? What kind of models are you looking for, for $f$? (I suspect you will have domain knowledge about what class of hypotheses for $f$ make sense.) Or, to put it another way, what kind of classifier might you use for $f$ if you had labelled instances? Also, what does the feature space look like? How large is $X$ and $P$? What do those sets "look like"? (what structure do they have?) – D.W. Mar 3 '17 at 6:14

It's probably possible. I'll suggest a few plausibly-practical methods, starting from very crude (but probably not super-effective) to more complex (might be more effective but might be computationally expensive). I expect that many of these approaches might be relatively slow to train the classifier but doable and worth a try. But first, let me try to formalize the problem more precisely.

## Theory

In machine learning it's often helpful to formulate your problem by identifying a loss function. Then you can formulate your problem as finding $f$ that minimizes the loss function. In your case, I think a natural loss function would be that $L(f,g)$ counts the number of partitions $p$ such that conditions (2) or (3) are violated. You could of course add a regularization term as well.

Once you've defined a loss function, your problem becomes: given $g$, find $f \in \mathcal{H}$ that minimizes $L(f,g)$, where $\mathcal{H}$ is the hypothesis space (the space of valid/legal models).

Let's start with a theoretical thought experiment. Suppose you didn't care about the computational time to train a classifier, and just want to find a valid classifier $f$. Let $\mathcal{H}$ be the hypothesis space, i.e., the set of allowable functions. (For instance, for a linear SVM, $\mathcal{H}$ would be the set of SVM weights -- i.e., the set of linear decision boundaries.) If you didn't care about computational time, you could just enumerate all $f$ to find one that minimizes $L(f,g)$ -- so this proves that the problem is well-defined.

More generally, suppose we have a space of classifiers $f$ that output probabilities instead of hard labels (think: logistic regression). Then we can define a loss function based on the cross-entropy loss:

$$L(f,g) = \sum_{p : g(p)=0} \max \{-\log(1-f(x)) : x \in p\} + \sum_{p : g(p)=1} \min \{-\log(f(x)) : x \in p\}$$

You could add a regularization term here, too.

Of course, other loss functions are possible as well; but the point is that once you have a loss function, then classification becomes well-defined as an optimization problem.

## Plausible method: one-class classifier

One crude approach is to use a one-class classifier. For each partition $p$ such that $g(p)=0$, you obtain many instances $x$ where you want to have $f(x)=0$. So, you could add each one of those to a training set, and then train a one-class classifier on it.

This is simple and easy to implement. However, I suspect its accuracy might be low.

## Plausible method: active learning

Suppose you have a way to obtain labelled instances if you need, through manual training. In particular: let's assume that given a partition $p$, if you really needed to, you could construct hard labels for instances $x \in p$, and specifically, if $g(p)=1$, you could find an instance $x \in p$ that should receive the label $1$. This manual-labelling process might be difficult and tedious and time-consuming/expensive, so not feasible to do on a large scale, but let's suppose you could do it on a small scale if needed.

Then you could use active learning:

1. Let $f$ be an arbitrary classifier (maybe trained using a one-class classifier). Let $T$ be an initial training set, initially empty.

2. Repeat until convergence:

a. Pick a partition $p$ such that $f(x)$ is wrong for some $x \in p$.

b. If $g(p)=0$, add find $x \in p$ such that $f(x)=1$, and add $(x,0)$ to $T$.

c. If $g(p)=1$, use the manual-labelling process to find some $x \in p$ that should be labelled $1$ and add $(x,1)$ to $T$.

d. Train a new boolean classifier $f$ using standard supervised learning methods on the training set $T$.

There are various optimizations you could use to break ties in step 2c (in hopes of reducing the amount of manual labelling); e.g., if you're using the cross-entropy loss defined above, you could choose the $p$ that contributes the most to the total loss for $f$. Or, you could choose the $p$ that is most "different" from all previously considered $p$ with $g(p)=1$. Or, you might be able to adapt other active learning methods.

This might work. However, it does require the ability to do some manual labelling of individual instances, which is more than you promised us in the original problem statement.

## Plausible approach: direct optimization

Another possible approach would be to choose a differentiable classifier, and the optimize the (cross-entropy) loss $L(f,g)$ defined above directly using gradient descent. For instance, you could choose $f$ to be a logistic regression or neural network classifier, as these are differentiable. Now, you can compute the gradient of $L(f_\theta,g)$ with respect to the parameters $\theta$ of the model (e.g., for logistic regression, $\theta$ are the weights) and then apply gradient descent to find the model parameters $\theta$ that minimize $L(f_\theta,g)$.

This may get a little messy, as loss function $L$ contains $\min$ and $\max$ functions, which have points where they are non-differentiable. If you don't do anything special, this can cause oscillation around the non-differentiable boundary. One possible trick is to replace each $\min$ by a softened version of the min, and replace each $\max$ by a softened version of the max, so that the loss function becomes differentiable.

Alternatively, you could adjust ordinary gradient descent to behave well around them. One standard technique is to reduce the step size when you get near the boundary to avoid stepping across the boundary, or to use projected gradient descent. Thus, if we have a term

$$\ell(\theta) = \min(\ell_1(\theta),\ell_2(\theta))$$

and we compute the gradient $\nabla \ell(\theta)$, the gradient will be based on whichever of $\ell_1(\theta),\ell_2(\theta)$ is smaller for this particular value of $\theta$. Suppose the gradient is $g = \nabla \ell(\theta)$. Ordinary gradient descent would take a step in the direction $g$, say adjusting $\theta$ to $\theta - \lambda \cdot g$ for some small constant $\lambda$. You could additionally require that the step avoid crossing the boundary line $\ell_1(\theta)=\ell_2(\theta)$. For instance, if $\ell_1(\theta)<\ell_2(\theta)$ for this particular value of $\theta$, we'll have $g = \nabla \ell(\theta) = \nabla \ell_1(\theta)$. So, take a step $- \lambda' \cdot g$, but constrain $\lambda'$ to be in the range $0 \le \lambda' \le \lambda$ and to satisfy $\ell_1(\theta - \lambda' \cdot g) \le \ell_2(\theta - \lambda' \cdot g)$ -- i.e., don't step across the other side of the discontinuity.

Note that using ordinary gradient descent will probably be very slow, as each evaluation of the loss function requires evaluating $f$ on every point in $X$: $O(|X|)$ time. You'll probably do better by using stochastic gradient descent: in each iteration, pick a single partition $p$, compute the gradient of the term in $L(f,g)$ for $p$, and move in the direction of that gradient. Or, pick a minibatch of 20 partitions $p$ and compute the gradient of the sum of those 20 terms.

## Plausible method: boosting

Another reasonable method would be to use boosting with a very simple classifier, such as a decision stump.

A decision stump is a decision tree with a single level: you pick one feature, compare it to some threshold, and make a binary decision based on whether the value of that feature is above or below the threshold. Decision stumps are convenient because you can enumerate all candidate stumps -- all possible combinations of a feature and a threshold -- and evaluate the loss function for each. (In practice, as an optimization, we don't enumerate all possible stumps. Rather, for a particular feature, we randomly pick 100 candidate thresholds by sampling 100 times from the training set, and we compute the loss for each candidate threshold; we do this for each feature, and take the best overall combination.)

You could use AdaBoost directly with decision stumps and minimize the loss function defined above, and you might get a reasonable classifier.

For even better results, you could use gradient boosting. This is a slight generalization where each leaf of each stump outputs a continuous value rather than a boolean; the classifier's output is obtained by summing the value from each stump, and then checking whether the sum is positive or negative. The general methodology can be applied with any differentiable loss function, so you could apply that methodology to the cross-entropy loss function defined above.

## Plausible method: incremental optimization

Here's another approach that can be applied to classifiers that aren't differentiable. In my algorithm, I will maintain a tentative training set $T \subseteq X \times \{0,1\}$ that assigns a tentative label to some of the elements of $X$. The training set $T$ will evolve throughout the algorithm, but it will always remain consistent with $g$, defined as follows:

We say that $T$ is consistent with $g$ if, (a) for every $p$ such that $g(p)=0$, we have $(x,0) \in T$ for all $x \in p$, and (b) for every $p$ such that $g(p)=1$, there exists at least one $x \in p$ such that $(x,1) \in T$.

The training set $T$ specifies one possible labelling that would be consistent with $g$. It's not necessarily the right one; it's just one possibility.

At each step, the algorithm uses $T$ as labels to train a classifier $f$ using standard supervised learning methods and computes $f$'s loss on $T$, then adjusts $T$ to reduce the loss of $f$ on $T$. Define $\text{train}(T)$ to be the classifier $f$ obtained by training on the training set $T$, using some boolean classifier of your choice. Here is the algorithm:

1. Set $T$ to be any training set that is consistent with $g$. Compute $f := \text{train}(T)$ and $\ell = L(f,g)$.

2. Repeat until convergence:

a. Enumerate all training sets $T'$ that differ from $T$ in only one element yet remains consistent with $g$, and for each train a classifier and compute the loss. Pick the $T'$ that minimizes $L(\text{train}(T'),g)$.

b. Set $T := T'$.

Step 2a can be done by enumerating all partitions $p$ such that $g(p)=1$. Suppose $T$ includes $(x,1)$ where $x \in p$. Then enumerate all $x' \in p$ and consider $T' = T \setminus \{(x,1)\} \cup \{(x',1)\}$. There are at most $|X|$ such possibilities, and you have to train the classifier on each, so each iteration of the loop might be pretty slow... but one could hope that it will eventually converge on a reasonable solution.

Basically, this tried to maintain some tentative labels that are consistent with your $g$, and that also are consistent with the regularity conditions imposed by the classifier $f$ (e.g., linear separability, or whatever), incrementally adjusting it at each step of the iteration.

For your particular parameter values ($|X|=10^5$, $|P|=10^3$), I suspect this will be too slow. But you could try experimenting with the approach for scaled-down versions of your problem, with a smaller feature space ($|X|$ is smaller) and see if it seems to lead to useful results.

If this algorithm gives useful results, there many heuristics and optimizations you could use to speed up convergence:

• You could probably make a smarter choice for the initial value of $T$ and speed up convergence, by applying a one-class classifier to the set of 0-labelled instances (since the instances of the form $(x,0) \in T$ never change throughout the algorithm) and using that to choose tentative initial label.

• You could use something akin to stochastic gradient descent to speed convergence: in step 2a, pick a single $p$ (or a small minibatch of $p$'s) and consider just training sets $T'$ that differ from $T$ only in $p$ (but not in other partitions.

• You could try using an online/incremental training method for training $f$. Since $T'$ is so similar to $T$, rather than training a new classifier from scratch, you might be able to reuse much of the effort from training on $T$ to more quickly compute $\text{train}(T')$ given $\text{train}(T)$.

• Depending on the nature of the feature space and the partition function, you might be able to solve the following problem more efficiently than brute force: given a training set $T$ and a partition $p$ such that $g(p)=1$ and an $x \in p$ such that $(x,1) \in T$, find some $x' \in p$ such that minimizes the loss when training on $T' = T \setminus \{(x,1)\} \cup \{(x',1)\}$. For instance, with logistic regression, you might be able to train a classifier $f_0$ on $T \setminus \{(x,1)\}$, then classify each $x' \in p$ using $f_0$ and rank them by the probability score that logistic regression outputs. This is a heuristic and not guaranteed to find the optimal $x'$, but it's also a lot more efficient than enumerating all candidates for $T'$ and training a classifier on each.

## A useful subroutine

Many of the above schemes require solving the following subproblem:

Given a partition $p$ and a classifier $f$, find $x \in p$ such that $f(x)=1$, or report that none exists.

If the classifier outputs confidence/probability scores, then the subproblem is:

Given a partition $p$ and a classifier $f$, find $x \in p$ that maximizes $f(x)$.

The naive way to solve this subproblem is to enumerate all $x \in p$. Depending on the particular classifier you choose and the structure of the partitions, there may be more efficient algorithms.

For instance, if we have a linear classifier, maximizing $f(x)$ becomes equivalent to maximizing $x \cdot w$ for some known vector $w$. If $p$ has a simple structure, there might be faster ways to solve this optimization problem. For instance, if $p$ is a convex region defined by linear inequalities, you can maximize $x \cdot w$ subject to $x \in p$ using linear programming.

And you can use a fast algorithm for this subproblem to speed up the training process, for many of the methods sketched above. Whether that is possible will depend on the specific type of classifier you choose and the structure of the partitions, but if you're trying to do this in practice, I recommend you ask a separate question about how to solve this subproblem for the particular type of classifier and partition structure that arises in your application -- that might enable significant computational optimizations.