Dominating in Recommender Systems

A recommender dominates another when it is at least as good on every metric considered and strictly better on at least one. This is Pareto dominance, which is used to compare options on several objectives at once. The term here has nothing to do with dominating sets in graph theory.

The definition

In the Wikipedia article on multi-objective optimization, for objectives that are minimized, a solution \(x_1\) dominates \(x_2\) if \(f_i(x_1) \le f_i(x_2)\) for every objective \(i\) and \(f_j(x_1) < f_j(x_2)\) for at least one \(j\). A solution is Pareto optimal, or non-dominated, if no other solution dominates it, and the Pareto front is the set of Pareto optimal outcomes. For metrics where higher is better, such as NDCG, the inequalities are reversed.

A worked example

The numbers are hypothetical. Four models are scored on NDCG@10, item coverage, and intra-list diversity, higher being better.

A dominates B, because it is at least as good on all three and better on all three. A and C each dominate D. A and C do not dominate each other: C is better on coverage and diversity, and A is better on NDCG. The Pareto front is {A, C}. B and D can be dropped, since a model on the front beats each of them on every metric.

Choosing on the front

The front shrinks the set of candidates, but it does not choose among them. The same article notes that, without additional subjective preference information, there may be many Pareto optimal solutions, all of which are considered equally good. Picking between A and C needs a preference, such as a minimum acceptable NDCG or the value placed on coverage and diversity.

Conditions for a fair claim

• Every model is scored on the same users, candidates, and time period.
• Metrics where lower is better are negated or reversed before the comparison.
• Small differences are estimates. A difference of 0.01 in NDCG that lies within evaluation uncertainty does not establish dominance; see Confidence Intervals.
• The conclusion depends on which metrics are included. Adding one can turn a dominating model into a non-dominating one, so the metric list should be chosen before the comparison.

Dominance gets harder to achieve as metrics are added, because a model must be at least as good on all of them, so many comparisons end with a front and not a single winner. Related entries: NDCG and Intra-List Diversity (ILD).

References:

• Wikipedia, Multi-objective optimization