# Classifying objects by set proximity

The project I'm working on has a number of objects arranged in overlapping sets. I need to classify them by whether they have a trait or not, using pre-classified objects that they are connected to (through shared set membership). I.e., the objects within the same set are likely to share whether they have that trait. The training data only consists of whether some objects have the trait or not.

To illustrate by example:

• Green and red circles represent pre-classified objects (with having and not having the trait respectively). White circles are unclassified.
• Objects A, C, D and E are likely to have the trait, and thus should have a positive score, because they are in common sets with other objects which are known to.
• A should have a better score than C because there is more certainty (C's unclassified neighbor might or might not have the trait).
• Similarly, D should have a higher score than A.
• E is likely to have the trait because all of its neighbors are.
• F and G should have a neutral score, because we don't know anything about F, and G has equally conflicting information.

I'm looking to sort all unclassified objects by score (likelihood to have the trait), which in this example would roughly be D, A, E, C, F, G, B, or at least get the top N objects with the highest score.

My set size is about 50 million objects across 10 million sets. The training size set (number of pre-classified objects) can vary from 1 to a few thousand. The objects are pretty well connected - the biggest "connected subgraph" contains 90% of all objects.

• Do you have any probabilistic model in mind, for when two objects are in the same group? Otherwise it is hard to come up with anything other than simple heuristics, that you can come up with on your own. – Yuval Filmus Mar 24 '17 at 13:50
• Let $X$ be the set of objects. Write $c_0(x)$ for what we know of the color of an object $x\in X$, $r$ for red, $u$ for grey/undefined, $g$ for green. Write $K$ for the set of objects for which the color is known. Given a probability on the set of colorings $c:X\to \{r,g\}$, you want to compute $$P(c(x)=g|\forall x \in K, c(x)=c_0(x))=\frac{P(c(x)=g\land \forall x \in K, c(x)=c_0(x))}{P(\forall x \in K, c(x)=c_0(x))}=\frac{\sum\limits_{\substack{c:X\to \{r,g\}\\c(x)=g\\ \forall x \in K, c(x)=c_0(x)}}P(c)}{\sum\limits_{\substack{c:X\to \{r,g\}\\ \forall x \in K, c(x)=c_0(x)}}P(c)}$$ – xavierm02 Mar 24 '17 at 16:41
• So we need to know $P$, or to know enough about the dataset to pick it for you. So far, all you've told is that at equal cardinal, a set closer to being unicolor is more likely, and that adding an object of the majority color makes the set more likely. – xavierm02 Mar 24 '17 at 16:48
• @xavierm02 Thanks, and that's a bit over my head right now - I have almost no experience with this field. While I try to decipher your comment, can I clarify the question with more examples or otherwise? – Vladimir Panteleev Mar 24 '17 at 18:20
• Here's a simpler question : "I have 100 balls that are either green or red, I know how many balls there are and the color of some of the balls, how can I guess the colors of the other balls?" Now, if you know that you have 49 green balls and 50 red, then maybe the probability (between $0$ and $1$) of the last one being green is $0.4$. But if you know that there is an even number of green balls, then it has to be green, so it's $1$. Similarly, you could know that there are as many green balls as red balls, which in this case would also imply that the last one it green. – xavierm02 Mar 24 '17 at 18:29

One powerful and general approach is to write a probabilistic model that describes how colors are chosen, then apply maximum-likelihood estimation. The probabilistic model provides an expression for $p(x)$, where $x=(x_1,\dots,x_n)$ and $x_i$ is a random variable that describes the color of the $i$th object. You are given an observation for some of the $x_i$'s, namely, the color of the pre-classified objects, and want to infer the color of the rest. This can be done by finding a vector $x$ that maximizes the value of $p(x)$, subject to the requirement that it be consistent with the observed colors. You then apply some mathematical optimization routine to find $x$ that maximizes $p(x)$, subject to the constraint that $x$ is consistent with the observations.

This requires that you supply a model for how colors are generated. Only you can provide that, since that depends on the specifics of your application domain and the random process underlying your observations.

One possible approach is to model this as a Markov random field. Build an undirected graph where the vertices are the objects; add an edge $(u,v)$ between two objects $u$ and $v$ if $u,v$ are in the same cluster. Then the Markov random field assumption says that $p(x)$ is proportional to

$$\prod_{(u,v) \in E} q(x_u,x_v),$$

where $q(\cdot,\cdot)$ is some function $q:\{\text{red},\text{green}\}^2 \to [0,1]$. For instance, you might take $q(c,d) = 0.99$ if $c=d$ and $q(c,d)=0.01$ if $c\ne d$. That defines a Markov random field. There are algorithms for maximum-likelihood inference for Markov random fields. (In particular, as a starting optimization, you can decompose the graph into connected components and solve the problem separately for each connected component.)

Another possible model would be a hierarchical model, where we first pick a color at random for each cluster, then randomly pick a color for each object based on the color(s) of the cluster(s) it is contained in. Suppose there are $m$ clusters, and let $w=(w_1,\dots,w_n)$ where $w_i$ is a random variable describing the color of the $i$th cluster. We might imagine that the $w_i$ are independently uniformly distributed. Then, we might imagine that we pick a color $x_j$ for object $j$ based on the values of $w_i$ for each cluster $i$ that contains object $j$. In particular, we might imagine that the conditional probability distribution $p(x|w)$ is proportional to

$$\prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i),$$

where we define $p(x_j|w_i) = 0.99$ for $x_j=w_i$ and $p(x_j|w_i)=0.01$ if $x_j \ne w_i$ (say). Using the fact that $p(x,w)=p(x|w) \cdot p(w)$ and that $w$ is iid uniform, we obtain that $p(x,w)$ is proportional to

$$2^{-m} \prod_{j=1}^n \prod_{i \text{ s.t. } j \in i} p(x_j|w_i).$$

We can then try to find $x,w$ that maximizes $p(x,w)$, subject to the constraint that $x$ be compatible with the observations (the pre-classified objects). This could be done by mathematical optimization. Again, as an optimization, you can decompose the problem into independent subproblems through a connected component decomposition (consider two objects in the same component if they are members of the same cluster).

It is also possible to obtain confidence scores through "marginalization": if you can compute $p(x_i|y)$ where $y$ denotes the observed colors of the pre-classified objects, then this serves as a confidence score for the inferred color of object $i$.

There are other models that might be appropriate. We can't tell you which one is most suitable for your application domain, but once you choose one, you can work out how to apply the maximum-likelihood maximization principle to it.

• Thank you for the detailed answer! I will spend some time studying Markov random fields. – Vladimir Panteleev Mar 25 '17 at 5:18