# Inferring locations from groupings of items

Let's say I have a large series of three-item bundles, like so:

   item1 item2 item3
1     F     C     H
2     H     F     D
3     D     C     R
4     S     B     X
5     M     Q     F
6     J     X     U
7     O     T     G
8     W     U     F
9     Y     B     S
10     V     G     A
n   ...   ...   ...


Where I know the following:

1. The items each have a unidimensional "location" characteristic, and are all arrayed somewhere between 0 and 1.

2. The bundles were each chosen such that the constituent items come from disparate parts of this 0-1 range. Not necessarily maximally distinct (although that might be a useful optimand), but such that the bundle-chooser would not select three items all from the same part of the 0-1 range if another item is available to the chooser. (So, a bundle-chooser would typically prefer (0.2, 0.25, 0.8) > (0.2, 0.25, 0.5), and (0.1, 0.3, 0.8) > (0.2, 0.2, 0.8)).

I would like to infer, given this 0-1 constraint, and the entire collection of bundles, the most likely "locations" for each item (A-Z, in this case).

Does this type of model have a name? How should I go about fitting this model? Is there an R package I could use to help me find a solution?

• How many items, how many observations do you have? I haven't seen such a problem but what about just defining a loss function? for instance, you add negative distances, or inverse distances between items in the bundle, and the item locations will be your free parameters. – Ott Toomet Oct 31 '17 at 14:15
• Hundreds of thousands of observations, and several thousand items. I have attempted to do just that -- define a loss function and optim() my way to a solution -- but the process was taking far too long to converge. It is possible that a much more efficient refactoring of my loss function exists, but I hoped that others had dealt with similar problems, hence this question. – rapidadverbssuck Oct 31 '17 at 14:43
• So, the bundle-chooser cannot select an "inferior" bundle, or is less likely to do so? When it chooses, can it choose among the full set of options, or is only a subset of the items available to choose from? – user2089357 Oct 31 '17 at 16:21
• The bundle-chooser can select inferior bundles, or else they would always select the items located at c(0, 0.5, 1). They are more likely to select disparate bundles than concentrated bundles. Let's assume for now that at any given time, some but not all items are available to choose from, but that the selection varies over time, and we do not have any data on what's available. – rapidadverbssuck Oct 31 '17 at 16:51
• What about imaging these are electrons in 1D cage, repelling each other with a force proportional to the inverse of the distance? This setup should have a solution, possibly multiple solutions. Care to show what did you do with optim()? – Ott Toomet Nov 1 '17 at 4:45

I assume (0.2, 0.25, 0.8) = (0.8, 0.25, 0.2) and (0.5, 0.25, 0.8) = (0.8, 0.5, 0.25), because I could not comment and ask it.

1. In the example you have provided, I would sum the ocurrances of each case. It will become some kind of a "rating" measure of distance. E.g. from bundle 1, I count F~C=1 C~H=1 F~H=1. Adding bundle 2 (H~F=1 F~D=1 H~D=1), it becomes F~C=1 C~H=1 F~H=2 F~D=1 H~D=1.
2. In the end you can put the 2 items (letters) with maximum distance between them at 0 and 1 respectively.
3. Then you can continue by adding the rest of the elements between them by choosing locations in proportion to the distances you already have.

An alternative automated approach would be to divide the sum of all distances by the same (described above) distance between each two items and use it as attaction value between them. Then you can construct a graph and use an "energy" algorithm to re-position the nodes (vertices/items).

I don't know a name for this model. I think what you want can be found as some kind of maximum likelihood estimate. Assuming the letters don't change location, you'd use 26 parameters, representing the location of each letter. Then you will have to think of the likelihood of seeing the "bundle" F - G - H for example. This likelihood can be a formula based on the three letters. Let's say the likelihood is

h - g ~ Normal(.5, .5) and g - f ~ Normal(.5, .5)

This way, parameters can switch, but the model would, based on only this particular likelihood, put H before G and G before F. There is something weird where it doesn't like them too far apart, but let's forget about that for simplicity right now.

This likelihood should ideally be informed by how the bundle-choser works.

Then you use some package that can find a Maximum Likelihood estimate. Maybe you can use stan to code the model, with the added benefit that Bayesian confidence intervals are around the corner. Or, if that works for your likelihood (it does in the simple case above) you can create a design matrix a bit like below,

a  b  c d .. z
-1 0  1 0 .. 0
1 -1  0 0 .. 0


and even fit it with r::lm. In this system, you'd use two lines per observation.

The important point is that you will have to specify the balance between putting observations farther apart, or maybe switching labels, and all that can be done by specifying a likelihood. Then you optimize for the 26 parameters.

EDIT Okay I didn't read your question too well, since you are already talking about a loss function, which is pretty much what's described here. If you have ~100K observations, specifying it as a linear model with 26 parameters, I think you can still fit such a thing. If you even need all those samples.