Ranking movies with discrete differential forms

Redirect to:

• Differential forms#Social choice: ratings and comparisons

This is related to the Netflix prize (awarded in 2010):

• Given: Part of the database of customers: data about him/her + preferences, in terms of stars given to each movie.
• Guess: The rest of the ratings/preferences/rankings/suggestions.

We will address a related issue.

Suppose all we have is rankings for each customer: for each pair of movies one indicates which one he prefers and by how much, $A > B$ etc.

The goal is to rank all movies: $$A_1 > A_2 > A_3 > ...$$

Since these are relative/pairwise/local rankings, there may be problems: $A > B > C > A$. This may occur for each customer and then more when we tally the preferences over the whole population.

So from local ranking we want to construct a global ranking, which may be impossible!

Let's build a model to sort this out.

• Each movie is a vertex and people's preferences are arrows with "weights" between vertices.

Now a person is a combination of his preferences, so it's a discrete $1$-form.

Note: This time the forms (the preferences) is not on a regular grid, but a general graph.

Next, the sum of all people's preferences is still a $1$-form, as in a vector space.

Observe that this form corresponds to a flow: the liquid flows from worse to better movies. It can also be understood as a vector field:

The goal is to extract the global ranking, which is a scalar function, that corresponds to this vector field.

There may be problems: circular flows/cycles. They are the ones that make global rankings impossible.

Note: a related problem occurs with elections via Arrow's Impossibility Theorem.

What to do?

Answer: remove the "cycles".

In other words, throw out some votes (yes, it's harsh).

In the smooth domain, all is clear. If we had a gradient vector field (aka conservative vector field), $V=\nabla h$, then all we need is to maximize this function, $h$. If it's not gradient, we make it so! As much as possible. (Similar for discrete forms.)

Have: a $1$-form $\varphi $.

Want: a $0$-form $f$ such that $\varphi = df$. Then maximize $f$.

So this does work if this vector field is conservative. How do we make it so?

We can't but there is the Hodge decomposition: any form is $$\varphi = df + \partial \omega + \xi,$$ where we think of $\partial \omega + \xi$ as "trash".

Here $\partial$ is the codifferential, $\xi$ is harmonic. Then $f$ is the solution, the (best possible) global ranking.