# How to handle machine learning inputs that should be considered as set of vectors, but whoes interpretation is order invariant (order agnostic set)

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.

** 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.

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