3 ms·
If two movies disagree on the ordering, it is not necessarily the case that one of them is doing it "wrong". (Author here.) Indeed! This is about trying to dis
by sigil 5y ago
If two movies disagree on the ordering, it is not necessarily the case that one of them is doing it "wrong".
(Author here.) Indeed! This is about trying to discover emergent conventions, so we can give first-time filmmakers a good starting point.
Or you could do it quadratically by making a matrix of A-follows-B frequencies and then summing up all pairs of entries in your list (normalizing by the length of the list). The latter takes more of the graph structure into account.
This is what PageRank (Experiment 3) does!
The last thing is that the article seems to take NP-hardness too seriously. Sure, if you really had to consider every possible permutation, it would take too long. But there's way more than enough structure in the problem to take advantage of.
I ask this question in a footnote [0] -- is this permutation space amenable to gradient descent? Don't know the answer! If someone knows this area well I'm all ears.
[0] https://endcrawl.com/credits-ordering/#fn:permutation-search https://endcrawl.com/credits-ordering/#fn:permutation-search
- JohnKemeny 5y agoHey, great article, great topic! You missed one very interesting angle for the problem (speaking of games), namely Voting theory, which is an important part of game theory! In voting theory, there is a concept called Kemeny ranking (Kemeny–Young method), which I believe is exactly what you are looking for. It is of course an NP-hard problem, but that shouldn't scare you away. In a voting setting, each movie would "vote" for a ranking of, say, the electric unit; i.e., the gaffer comes before the other people. When you have many movies, you have many votes that you want to combine in order to rank all the candidates, while minimizing inconsistencies. A seminal paper was published in the journal of the ACM, Aggregating inconsistent information: Ranking and clustering by Ailon, Charikar, and Newman. An important insight is that your directed graph is actually what we call a tournament; for every two vertices a and b, there is an edge either from a to b, or from b to a. In that case, you want to solve a well known and widely studied problem, namely Feedback Arc Set in Tournaments (FAST). Check out the paper in ISAAC by Karpinski and Schudy, Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament (it's on arxiv).
- sigil 5y agoAmazing — didn’t realize minimum feedback arc set had a low exponent solution in this case. Your comment made my day, thank you!