# Learning if instances from a dataset are part of the same subset

I was wondering if there are some well-known machine learning methodologies for subset learning. In other words, to learn if two instances are part of the same subset or not (boolean label?).

One idea could be creating features vectors that are comprised of the two feature vector that we need to test, using both ordering of the feature vectors.

For example: I have two instances represented by 2 $D$-dimensional feature vectors, that are $\mathbf{x}_1$ and $\mathbf{x}_2$.

I could create two combined feature vectors as being

$$[\mathbf{x}_1,\mathbf{x}_2] \rightarrow t\\ [\mathbf{x}_2,\mathbf{x}_1] \rightarrow t$$

Where $t\in\{0,1\}$ is a boolean target variable/category to be learnt that is $1$ in case $\mathbf{x}_1$ and $\mathbf{x}_2$ belong to the same subset or $0$ otherwise.

Unfortunately with this method, the relationship between the features that are at the same position in $\mathbf{x}_1$ and $\mathbf{x}_2$ is not exploited, when it should because they represent the same measurement. To solve this I could add an additional set of feature, that is $\mathbf{x}_{1-2} = \mathbf{x}_1-\mathbf{x}_2$, but this is just an heuristic as there could be many more, whose use would defeat the very idea of generality, and learning, typical of machine learning methods.

Please notice that all possible subsets are not known in advance, so I cannot just use the subset index as label/category to be learnt.

This is my solution, but I bet that there might be even better ones. Any other idea, or pointers to literature?

# Clarification on domain of application

The instances are feature vectors extracted from parts of an object as represented in an image. Given two sets of pixels (connected components), I extract the two feature vectors and then I am using these to some classifier as belonging to the same object, or as not belonging to the same object.

It would be wrong to have an initial idea on why the parts are related: I want to avoid such heuristics, this is why I left the post initially generic and did not explain the domain of application. Please notice that my questions, being generic, applies also to other domains, such as, for example, human perception of two products of belonging to the same category, or not.

This latter case can be formalized in exactly the same way, and the hypothetical categories in which the products may belong are not the target of learning, but the fact that two products are perceived as "same kind" as opposed to "different kind".

# Example with bag-of-words documents

A simple example can be illustrated by considering document classification: magazine articles composed by binary feature vectors of word presence might be prompted in pair to a person that has to establish if they belong to the same group or not. A classifier, then, might use this information to discover that the word "electrolysis" is a strong predictor of belonging to the same group, while words like "happy", "the", "a" don't have any predictive power. Moreover, it can be learnt that words as "volcano" and "eruption" are predictors of belonging to the same group, even if the words are not both present in both articles (for example, the first contains "volcano" but not "eruption" and the opposite for the second article).

• In the question, what is your definition of "same subset"? In other words, are you looking for grouping similar feature into similar subsets or you care about order of positions as you state in the provided example? What would you think about clustering features (clustering features shall not be confused with clustering data samples)? – soufanom Mar 29 '15 at 2:59
• @soufanom the problem cannot be solved by clustering. Clustering uses distance of features as as criteria for the relatedness of instances, but this is an assumption that does not make sense to make in this case. Features may be very distant but the instances may be belonging to the same group. Moreover this is a supervised learning problem, which means that I can instruct a model about which instances are related. The very definition of same subset of instances (not features) is the target of the learning – fstab Mar 29 '15 at 9:41
• I slightly misunderstood the question but not sure, I fully understand the problem yet. It might help to explain more what instances are originally representing and why two instances that might have different feature values could be of the same class (in such case I agree clustering not to be expected to do good as you mentioned)? Do you want to group instances based on feature existence or feature values? It is not clear how instances are correlated if a distance measure is not indicative of similarity of these instance. – soufanom Mar 29 '15 at 15:42
• The instances are feature vectors extracted from parts of an object as represented in an image. Given two sets of pixels (connected components), I extract the two feature vectors and then I am using these to some classifier as belonging to the same object, or as not belonging to the same object. It would be wrong to have an initial idea on why the parts are related: I want to avoid such heuristics, this is why I left the post generic and did not explain the domain of application. – fstab Mar 29 '15 at 16:31
• @soufanom: I added an additional explanation in the post – fstab Mar 29 '15 at 16:41