Or you can also skip step 2, if you initialize alpha and beta to be something simple and reasonable, like
(unreciprocated probability of edge from #i to #j) alpha = e^[ j-i ]
(reciprocated probability of edge between #i and #j) beta = e^[ (j-i)^2 ]
(I might have alpha and beta backwards from how they are in the paper?)
Before I was saying that alpha and beta should be modeled as polynomials, but it probably makes more sense to model (log alpha) and (log beta) as polynomials, as the equations above do. That makes it more like logistic regression, which I think is supposed to work well in the social sciences?
On Sun, Oct 7, 2012 at 12:35 PM, Eric Purdy epurdy@uchicago.edu wrote:
So, I'm still a bit too busy to just reimplement their code, but here's a sketch of roughly how I would do it. Maybe someone else will feel like writing this code? It sounds like we could probably use it to write a publishable paper, if that's a motivation.
The easiest would be to do this in python with networkx.
- Write code to separate the edges into training and test sets.
Basically, independently label each edge "test" with probability 10% and "training" with probability 90%. Then make a new graph that doesn't have any of the test edges. This is the graph that you will run EM on.
Get a ranking that has the minimum number of rank violations.
Write code to infer alpha and beta from a set of rankings. This is
basically just a least squares problem, if you take my advice and use polynomials to represent alpha and beta. You will probably want to have some sort of penalty for having large coefficients in your polynomial. A common way is to put a prior on the polynomial a_0 + a_1 x + ... + a_k x^k. A sensible prior would be a_1^2 + ... + a_k^2. Note that you probably want to let a_0 be whatever it wants.
- Write code to sample from the set of all rankings, assuming that
alpha and beta are the correct distributions. This is the thing that can probably be done quickly if you do some clever algorithms. Basically, you generate a ranking of the first k nodes, then you extend it to a ranking of the first (k+1) nodes by inserting node #(k+1) somewhere in between two other nodes in the ranking.
- Write code that does EM iterations. This is just going back and
forth between steps 3 and 4. In step 4, generate a bunch of random rankings, and then use all of them when you go back to step 3. Save all of the rankings, like Mike says.
- Write code that evaluates your proposed ranking by looking at the
invisible test edges. See how the quality of the ranking changes over each EM iteration.
On Sun, Oct 7, 2012 at 12:16 PM, Michael Bishop michaelbish@gmail.com wrote:
So with all due respect to the author, its annoying that the only ranking output the program saves is the final ranking. What I've started doing is telling it to run with 0 iterations which outputs the minimum violations ranking. Then I change the output filename, and run it again with a flag which allows you to specify a seed.
This way I'll be able to compare the minimum violations rankings to the expectation maximization algorithm which typically takes 4-8 iterations to converge. But given the computational requirements, it would seem to make sense to default to save every single ranking along the way in case you ever want to look at it later.
On Sun, Oct 7, 2012 at 10:33 AM, Eric Purdy epurdy@uchicago.edu wrote:
Let me also raise a substantive issue. Within groups there is more agreement about what is status-worthy than between groups. While I think the idea that there exists a status ranking across all the students in a school has enough truth to it to merit the work being done on it, this approach is also obscuring the large differences in what earns you status in different contexts. A focus on the causes and consequences of status differences (status as defined in this paper) inevitably ignores the importance of groups. Of course, there are ways of trying to address the existence of groups that complement the work done here, and maybe its not even as hard as I'm making it out to be, but you always have to draw the line somewhere, and at that point you start waving your hands. I guess I'm just saying we have to do our best to be honest with ourselves and our audience about the many things that might be important but we don't know for sure because we can't fit them in our model.
You can model people playing different status games at the same time. Like, say for simplicity that there are two games in high school, being smart and being cool. Then we could try to figure out which game each player is playing (or how much they're playing both) based on that. It would make the overfitting problems much worse, but it's not super-hard to formulate such a model.
Also, you could probably get some sort of independent check of such models by giving people surveys that try to determine what strategy people think they are following. Like, "how cool do you think you are, relative to your friends", "how do you decide whether you want to be friends with a new acquaintance", etc.
-- -Eric
-- -Eric