6
$\begingroup$

Basically wondering best practices for input modeling and ML algorithm type(s) for inputs that essentially model samples that are a bag/set of "sub-objects", so order does not matter. Think of the kind of 2D input vector that would normally go into an RNN, but in this case the order of the 2nd-degree vectors in the input vector should not affect output.

Trying to model a classification problem where there are some number of records R1,...,Rn each with a uniform set of features f1,...,fm in a bag/set that should evaluate the same regardless of the order that the items R1,...,Rn are observed/pulled from the bag. All of the records are related to / interact with each other, but they may also affect the output individually (in terms of relations, think of a simple transitive closure graph with self loops).


Eg. say records R are personnel profiles, Ri.fj are features about each person Ri, and the output y is whether some group R1,...,Rn would make a "good" team. A team may not be "good" because either a single person Ri is just bad or there would be some bad interactions between two are more members.


My question is, is there some common design pattern for dealing with this (relatively new to machine learning)? I was either going to represent this kind of input as

1) a single big vector of features where a single sample is of the form

[R1.f1,...,R1.fm,...,Ri.f1,...,Ri.fm,...,Rn.f1,...,Rn.fm]

and feed into something like a simple DNN or DRF (accounting for the fact that order of each set of features does not really matter by creating all permutations of that row as extra samples to train on (treating each [Ri.f1, ..., Ri.fm] subrow as a element for permutation)). Maybe ordering the "subvectors" by alpha order based on feature Ri.f1 for all input vectors and having that just be the way data was always feed to the algorithm would be better than generating artificial permutations?

Or 2) break them up into groups, so a single sample looks like like

[[R1.f1,...,R1.fm],...,[Ri.f1,...,Ri.fm],...,[Rn.f1,...,Rn.fm]]

and feed into an RNN (the problem here seeming to be that it is not order agnostic; perhaps a CNN would work well here?). Again, is there some common design pattern for dealing with this? Any advice would be appreciated.

---------- Updates

** Adding this extra info in response to some comments discussion: In the "teams" example, they may be of arbitrary size, but can be simplified by only accounting for the first x members. My actual use case is more like looking at line items on a receipt and trying to predict a single outcome associated with that receipt.

$\endgroup$
4
  • $\begingroup$ Are the size of teams fixed, or of arbitrary size? $\endgroup$
    – kbrose
    May 16, 2018 at 23:14
  • $\begingroup$ @kbrose In the "teams" example, they may be of arbitrary size, but can be simplified by only accounting for the first x members. My actual use case is more like looking at line items on a receipt and trying to predict a single outcome associated with that receipt. $\endgroup$ May 17, 2018 at 1:06
  • $\begingroup$ Interesting. RNNs would probably work but give special meaning to the order of the items. I’m curious to see if there are answers with models that handle arbitrary length inputs and are order agnostic $\endgroup$
    – kbrose
    May 17, 2018 at 12:50
  • 1
    $\begingroup$ arxiv.org/abs/1703.06114 may be a good resource (“Deep Sets” from NIPS 2017) $\endgroup$
    – kbrose
    May 17, 2018 at 12:52

4 Answers 4

1
$\begingroup$

Especially if the teams were of fixed size, then one could use just about any model and teach them about the invariance to order by feeding them training data consisting of permutations of all inputs in all possible orders (plus having some overall team information like number of members, mean/variance/other things about each feature etc.). That may feel a bit inefficient and you need to be careful to e.g. do cross-validation splits before doing this data augmentation.

For many models this ignores that (if I understand correctly) items/team members share features that in a way mean the same thing for each one of them. If you put that information into the separate variables, it gets treated like it has nothing to do with each other. With neural networks, there's the option of using a common encoder to produce identical representations in a new feature space. That could be one tempting approach (in combination with the data augmentation above), but still does not deal well with the variable number of items.

One potential model architecture that combines all of the above (and does not need permuting of the items) would be a transformer neural network (of language model fame), which actually had to originally be modified with positional encodings to reflect that text is not just a bag of words but rather have a distinct order (positions for each word in the text).

$\endgroup$
0
$\begingroup$

The usual supervised classification approach is to create a rectangle of numbers, one row per thing to be classified, one column per feature, and engineer features to communicate information about the problem domain to the model, information that should in some way be predictive of the target labels.

When you have structural information as you’ve described here, you come up with ways to represent that structure for the model. If the graphs have a root, then you could have a feature for depth from that root, or more generally distance from some other kind of related node. For example, levels below (or above) VP, or distance from first ancestor having 200 or more nodes in its subgraph (just to name a couple of examples). You can create features about the graph structure, such as “has self loop” and “degree of node” (or indegree and outdegree if directed). You can create features about the neighborhood, such as total number of nodes within distance 3, or the average of some attribute among all immediate neighbors. You can create features about nodes related by feature, such as what fraction of all records have the same value for f2, or the median value of f4 among all records having the same f5 as this record.

There are challenges with cross-validation when all records are somehow related. Usually, you end up having to introduce an arbitrary partition in the graph structure, and need to decide how to handle records that had edges crossing the partition boundary (keep the nodes and drop those edges? Or also drop the nodes?) http://www.unofficialgoogledatascience.com/2018/01/designing-ab-tests-in-collaboration.html discusses some related issues in the context of A/B testing, and there are many other references out there, including Social Network Data Analysis (Springer, 2011) and “Graphs in machine learning: an introduction” (http://arxiv.org/abs/1506.06962)

$\endgroup$
0
$\begingroup$

An answer to your question goes under the heading of categorical feature encoding.

For example, if a feature represents ten counties in a country, the order of the labels identifying the counties would not matter. Then, using numbers to encode the labels may serve to only confuse the classifier.

To encode grouping information one can use so called hot encoding, which sometimes may not be adequate as it requires adding as many binary features as there are categories, 10 in this case.

There are a number of encoding tricks which mostly associate grouped points with the response variable. For example, you may calculate means of the response for each category/group. However, one must take care not to commit the crime of data snooping, which is what statisticians call "using data twice", both in training and test data sets. A way to avoid data snooping is to do encoding separately for training and data sets.

$\endgroup$
0
$\begingroup$

This is "multiple instance learning"; the wikipedia page has a good introduction.

Your examples sound like they don't conform to the standard assumption, so you'll need some "metadata-based" algorithm. At the simplest, you engineer metadata features from the bags and fit a traditional model to the result. More complex algorithms try to automatically find good metadata definitions; neural networks seem like a natural candidate for that, but I'm not familiar enough to give approaches. Still, armed with the search phrase "multi-instance", you can find e.g. https://arxiv.org/abs/2202.11132

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.