A person repeatedly selects the two most similar items out of three. How to model/estimate a perceptual distance between the items? A person is given three items, say pictures of faces, and is asked to pick out which two of the three faces are the most similar. This is repeated a large number of times with different combinations of faces, where each face can occur in many combinations. Given this kind of data I would like to model/estimate the difference/similarity between the faces by assuming that each face could be placed in a 2D space (or 3d, 4d, etc.) where the distance between each face reflects the choices of the participant.
What would be a good (perhaps even standard) way of modelling/estimating this?
Any pointers towards models/papers and/or software packages are highly appreciated.
 A: A good approach to this kind of problem can be found in section 4 of the paper The Bayesian Image Retrieval System, PicHunter by Cox et al (2000).  The data is a set of integer outcomes $A_1, ..., A_N$ where $N$ is the number of trials.  In your case, there are 3 possible outcomes per trial.  I will let $A_i$ be the index of the face that was left out.  The idea is to postulate a generative model for the outcome given some model parameters, and then estimate the parameters by maximum-likelihood.  If we show faces $(X_1,X_2,X_3)$ and the participant says that $(X_2,X_3)$ are the most similar, then the outcome is $A=1$, with probability
$$
p(A = 1 ~|~ X_1, X_2, X_3) \propto \exp(-d(X_2,X_3)/\sigma)
$$
where $d(X_2,X_3)$ is the distance between faces 2 and 3, and $\sigma$ is a parameter for the amount of "noise" (i.e. how consistent the participants are).  Since you want an embedding in Euclidean space, your distance measure would be:
$$
d(x,y) = \sqrt{\sum_k (\theta_{xk} - \theta_{yk})^2}
$$
where $\theta_x$ is the (unknown) embedding of face $x$.  The parameters of this model are $\theta$ and $\sigma$, which you can estimate from data via maximum-likelihood.  The paper used gradient ascent to find the maximum.  
The model in the paper was slightly different since the paper used known attributes of the images to compute distance, rather than an unknown embedding.  To learn an embedding you would need a much larger dataset, in which each face was shown multiple times.
This basic model assumes that all trials are independent and all participants are the same.  A nice benefit of this approach is that you can easily embellish the model to include non-independence, participant effects, or other covariates.
A: Thought:
I think eigenfaces is a decent way to convert what can be million-dimensional spaces to a few tens of dimensions.
Premise:
So lets assume that you are using a decent eigenfaces tool, or one that:


*

*does preprocessing to align appropriate features

*handles colors in an appropriate way

*makes sure the pictures used are all the same size


This means you don't have "pictures" as much as you have vectors of length O(n=50) elements in size where the elements are weights for each eigen-face comprising the basis.
Analysis:
First I would create 150-element vectors (concatenation of weight) as inputs and 1-element vectors (elements of closest match) as outputs.  If element 1 and 2 were closest then the output value would be "12".  If elements 1 and 3 were closest then the output would be "13".  If elements 2 and 3 were closest then output would be "23".  Given that there are only 3 unique outputs, I could re-map them to case 1 for "12", case 2 for "13" and case 3 for "23.  
Second I would want to throw away as much meaningless data as possible.  This means that I would try to use something like random forests to determine which of the ~150 columns were not informative.  There is also a "random evil twin method" but I don't have it at my fingertips the way R gives me with random forests.  (If you know a good R library for this, I invite you to put it in the comments).
Third, in my personal experience, if you have decent sample sizes, and decent basis a random forest can usually drop you down to the ~30 variables of interest, even from as much as 15k columns.  This is where you have to consider what is the general form of the answer.
You could try a dozen breeds of transforms of these variables to map the reduced inputs to the outputs:


*

*you could train an RF of the reduced inputs and call it good.

*you could train a NN on the reduced inputs if you wanted better smooth interpolation and generalization than an RF

*you could use some sort of linear transformation on the inputs

*there are a few dozen other ML hammers to hit it with, but when you are a hammer every problem looks like a nail.


More thoughts:


*

*I would be curious about which of the eigenfaces the reduced set references.  I would just like to see that data and let it talk to me.

*I'm quite curious about your sample sizes and the nature of your variation.  If you are looking at 3 rows, then having 150 columns is not going to be too productive.  If you have a few thousand rows then you might be in great shape.  A few hundred rows and you might be average.  I would hope that you accounted for all sources of variation in terms of ethnicity, facial shape, and such.  

*Dont be afraid of looking through simple models first.  They can be good.  Their interpretation and applicability are easily evaluated.  Their execution can be tested and confirmed with substantially less effort then complex and highly sensitive methods.


UPDATE:
The "random evil twin" tool is "Boruta". (link)
