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


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


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.

  • $\begingroup$ Are the size of teams fixed, or of arbitrary size? $\endgroup$ – kbrose May 16 '18 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$ – lampShadesDrifter May 17 '18 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 '18 at 12:50
  • 1
    $\begingroup$ arxiv.org/abs/1703.06114 may be a good resource (“Deep Sets” from NIPS 2017) $\endgroup$ – kbrose May 17 '18 at 12:52

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)


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.


Your Answer

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

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