PaperlayerView exact revision on arXiv

Source-linked AI summary

Fighting Fire with Fire: Using Antidote Data to Improve Polarization and Fairness of Recommender Systems

Bashir Rastegarpanah, Krishna P. Gummadi, Mark Crovella

arXiv:1812.01504v4cs.IRcs.LGstat.ML

TL;DR

Recommender systems can inherit undesirable properties from observed data, while existing ways to improve social outcomes may require changing inputs, algorithms, or outputs. This paper adds optimized antidote ratings to matrix-factorization systems and reports substantial improvements in polarization or fairness with a modest data budget.

  • Problem

    Existing ways to improve socially relevant recommendation measures may be difficult to adapt across measures and often require changing system inputs, algorithms, or outputs.

    Source: §1 · p. 1

  • Method

    The paper adds ratings from new users to an existing matrix-factorization recommender system, optimizing the added data for socially relevant recommendation properties.

    Source: §1 · p. 1

  • Results

    Typically 1% new users can produce roughly 50% improvement in polarization or fairness of recommendations.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Antidote data provide a flexible approach for improving recommender-system polarization or fairness without modifying the original inputs or algorithm.

    Source: §1 · p. 1, §7 · p. 9

    The framework assumes a differentiable antidote objective but does not assume convexity or guarantee a global optimum.

    Source: §4.1 · p. 4

Abstract

from arXiv · show

The increasing role of recommender systems in many aspects of society makes it essential to consider how such systems may impact social good. Various modifications to recommendation algorithms have been proposed to improve their performance for specific socially relevant measures. However, previous proposals are often not easily adapted to different measures, and they generally require the ability to modify either existing system inputs, the system's algorithm, or the system's outputs. As an alternative, in this paper we introduce the idea of improving the social desirability of recommender system outputs by adding more data to the input, an approach we view as providing `antidote' data to the system. We formalize the antidote data problem, and develop optimization-based solutions. We take as our model system the matrix factorization approach to recommendation, and we propose a set of measures to capture the polarization or fairness of recommendations. We then show how to generate antidote data for each measure, pointing out a number of computational efficiencies, and discuss the impact on overall system accuracy. Our experiments show that a modest budget for antidote data can lead to significant improvements in the polarization or fairness of recommendations.

1 INTRODUCTION

Because recommender outputs may carry unfairness or polarization from observed data, the paper explores improving recommendations by adding data rather than changing existing inputs. Its framework targets socially relevant properties, and the experiments report substantial improvements with a small antidote-data budget.

1 INTRODUCTION

  • Observed data may carry undesired properties, including unfair or unequal service and societal polarization.The introduction motivates the approach by noting that recommendations can inherit properties of the data used to learn them.Source: §1 · p. 1
  • Adding data can avoid modifying existing inputs or the algorithm, and a third party may supply it without access to either.The approach applies to properties expressible as differentiable functions of system ratings and/or predictions.Source: §1 · p. 1
  • The framework adds ratings from new users on existing items to improve a socially relevant property for the original users.The paper calls these additional ratings antidote data.Source: §1 · p. 1
  • Typically 1% new users can produce roughly 50% improvement in recommendation polarization or fairness.The paper reports these as typical antidote-data budget and improvement magnitudes.Source: §1 · pp. 1–2

2 RELATED WORK

The related work situates the paper among fairness approaches and concerns about recommender-driven polarization. It distinguishes antidote data from input transformation and algorithm modification, and adapts adversarial data-poisoning techniques toward social goals.

2 RELATED WORK

  • Prior recommender-system fairness work includes group-level measures based on prediction accuracy across user or item groupings [34].The related work also describes fairness as covering users receiving recommendations and items being recommended.Source: §2 · p. 2
  • The paper extends group-level fairness notions to individual-level fairness and allows fairness to be considered from either user or item perspectives.The discussion notes that recommender fairness can involve both sides of the recommendation process.Source: §2 · p. 2
  • The paper redirects adversarial methods used to poison training data toward generating antidote data for social good [26].The described inspiration includes prior data-poisoning attacks on factorization-based collaborative filtering [26].Source: §2 · p. 2
  • The proposed approach leaves original training data untouched and adds antidote data, unlike preprocessing that transforms data or in-processing that changes objectives or models.The paper also contrasts its fairness approach with in-processing methods that require modifying the recommendation algorithm.Source: §2 · p. 2
  • Polarization is measured as divergence of predicted ratings across users, consistent with prior metrics [13].The framework can target either reducing or, in some scenarios, increasing this polarization measure.Source: §2 · p. 2

3 OPTIMAL ANTIDOTE DATA PROBLEM

The optimal antidote problem seeks additional ratings that change matrix-factorization predictions so a chosen social objective is optimized. It formalizes the input data, factorization outputs, and the option to construct artificial users or items.

3 OPTIMAL ANTIDOTE DATA PROBLEM

  • Matrix factorization learns user and item latent vectors from observed ratings, estimates unknown ratings as U^T V, and uses an L2 regularizer to avoid overfitting.The factorization rank and regularization parameter are selected during validation and then held fixed.Source: §3 · pp. 2–3
  • The social objective R is defined over estimated ratings and may also depend on original ratings or user-group labels.The paper uses R(estimated ratings) as shorthand because antidote data affect the output estimates.Source: §3 · p. 3
  • The optimal antidote problem seeks an added rating matrix for a fixed budget that optimizes an objective after factorization is applied jointly to original and added data.The objective may need to be minimized or maximized, depending on the target.Source: §3 · p. 3
  • The framework can generate artificial items instead of artificial users by applying the problem to the transposed rating matrix.The formulation describes added antidote data as artificial users in its basic notation.Source: §3 · p. 3
  • Joint factorization of original and antidote ratings yields latent vectors for original users, antidote users, and items; the original users’ predictions determine the objective.The estimated ratings are formed from the original users’ and item latent vectors.Source: §3 · p. 3

4 COMPUTING ANTIDOTE DATA

The paper optimizes antidote ratings with projected gradient descent/ascent, then exploits matrix-factorization structure to reduce gradient computations.

4 COMPUTING ANTIDOTE DATA

  • The framework applies projected gradient descent/ascent to optimize antidote data for a socially relevant objective, with computational efficiencies tailored to the problem.The approach adapts data-poisoning optimization [26]; machine teaching offers a route to extend it beyond matrix factorization.Source: §4 · p. 3, §4.1 · p. 3

4.1 A Projected Gradient Descent Approach

  • Each iteration refits the model with the current antidote ratings, computes their utility gradient, updates the ratings, and projects them into feasible bounds.The procedure starts with antidote data sized to the given budget; here, projection truncates ratings to the system’s minimum and maximum feasible values.Source: §4.1 · pp. 3–4
  • The utility need only be differentiable; the framework seeks metric improvement, not a global optimum, and assumes no convexity.Algorithm 1 takes the learning algorithm as input in a white-box setting, though heuristics can require less system information.Source: §4.1 · p. 4

4.2 Efficient Computation of the Gradient Step

  • The gradient computation exploits factorization structure: KKT conditions approximate factor derivatives, while reusable terms reduce repeated computation.A term shared by derivatives for antidote ratings in the same item column can be precomputed each iteration and reused across antidote users.Source: §4.1 · p. 4, §4.2 · p. 5

5 SOCIAL OBJECTIVE FUNCTIONS

The section applies the antidote-data framework to polarization and fairness objectives, defining measures for both and examining how improving them relates to prediction accuracy.

5 SOCIAL OBJECTIVE FUNCTIONS

  • Polarization can reflect either excessive disagreement or undesirable homogeneity, while fairness means equal prediction accuracy across users or user groups.The section applies antidote data to these objectives.Source: §5 · p. 5

5.1 Polarization

  • The polarization metric is normalized pairwise distance between predicted user ratings, equivalently average item-wise variance or user disagreement.Both increasing and decreasing polarization are considered objectives.Source: §5.1 · p. 5, §5 · p. 5

5.2 Fairness

  • Individual unfairness is the variance of users’ mean squared estimation losses, and group unfairness is the variance of groups’ mean squared estimation losses; both objectives are minimized.User losses are computed over known ratings; group losses are computed over known ratings in each group.Source: §5.2 · p. 5

5.3 Accuracy vs. Social Welfare

  • Changing polarization in either direction generally decreases accuracy slightly, while reducing unfairness may increase or decrease accuracy.The unfairness metrics are zero when prediction error is zero.Source: §5.3 · pp. 5–6

6 EFFECTIVENESS

The experiments show that antidote data can change polarization and improve individual and group fairness, including on held-out ratings. The paper also tests computationally cheaper heuristics and examines accuracy and recommendation changes.

6.1 Polarization

  • A 2% budget reduces polarization by 50% in a polarized setting and increases it by 10% in a less polarized setting; the method outperforms baselines and random data.Random initialization is more effective for minimizing polarization, while identical-value initialization is more effective for maximizing it.Source: §6.1 · p. 6
  • With a 1% budget, minimization lowers Rpol from 0.55 to 0.29 while known-rating RMSE changes only from 0.80 to 0.83.For Patch Adams, extreme estimates become a unimodal distribution within the range of original ratings.Source: §6.1 · pp. 6–7, Figure 4 · p. 7
  • Adding 1% antidote data changes the top-recommended item for 84% of users, with recommendation-set changes remaining significant through k = 30.The reported change is measured using Jaccard similarity across users’ top-k recommendation sets.Source: Figure 4 · p. 7, §6.1 · p. 7

6.2 Heuristic Algorithms

  • The fairness heuristics exploit boundary-valued ratings and nearly identical rows: heuristic1 uses one gradient evaluation, while heuristic2 also avoids factorization-algorithm and hyperparameter access.Source: §6.2 · pp. 7–8

6.3 Fairness

  • In held-out ratings, a 2% heuristic1 budget lowers individual unfairness from 0.1087 to 0.0800, while 0.5% GD(random init) lowers group unfairness from 0.0088 to 0.0035.Source: Table 1 · p. 8, Table 2 · p. 8, §6.3 · p. 8

6 EFFECTIVENESS

  • The fairness experiments use 1,000 active users and 1,000 frequently rated movies, with about 36% of ratings known; polarization experiments use a random 1,000-user subset with 11% known.The fairness factorization uses rank 8 and λ = 1.Source: §6.1 · p. 6, §6.3 · p. 8

6.3 Fairness

  • All algorithms considerably improve fairness; most antidote-data benefits require only 1% additional users for individual fairness and 0.5% for group fairness, while identical-row heuristics deliver nearly all versus around half of Algorithm 1’s benefits.Source: §6.3 · p. 8
  • Antidote data lowers RMSE across genres and narrows cross-group variability; it also reduces per-user RMSE variation and outliers in training and test sets, sometimes improving overall accuracy.Genres with initially larger errors, including Documentary and Horror, show the largest RMSE improvements.Source: §6.3 · pp. 8–9

7 CONCLUSION

The conclusion presents antidote data as a flexible strategy for improving recommender-system polarization or fairness without changing original inputs or the algorithm.

7 CONCLUSION

  • Antidote data can efficiently improve recommender-system polarization or fairness properties.The paper concludes that the framework is a flexible and effective approach to addressing recommender-system social impacts.Source: §7 · p. 9
  • The strategy adds data without requiring changes to the original system input or algorithm.Source: §7 · p. 9
  • The framework applies its antidote-data strategy to a range of socially important objectives.Source: §7 · p. 9

A.1 Derivation of ∂V

The appendix derives a formula for the item factor at a local optimum, using a first-order approximation for infinitesimal changes to antidote ratings.

A.1 Derivation of ∂V

  • The derivation assumes the factorization algorithm finds a local optimum of objective E.Source: §A.1 · p. 9
  • At that optimum, the derivative of E with respect to v_j is set to zero to obtain a formula for v_j.Source: §A.1 · p. 9
  • The derivation treats an infinitesimal change in x̃_ij as producing only first-order corrections.Source: §A.1 · p. 9

A.2 Gradients of the objective functions

This appendix defines averages used in the objective-function gradients and introduces group labels for group-fairness calculations.

A.2 Gradients of the objective functions

  • μ_j denotes the average estimated rating for item j.Source: §A.2 · p. 9
  • μ_indv denotes the average of user losses.Source: §A.2 · p. 9
  • For group fairness, G maps each user/item pair to its group label, and μ_G denotes the average of group losses.Source: §A.2 · p. 9

B HEURISITC ALGORITHMS

The appendix presents heuristic algorithms for generating antidote data to improve individual and group fairness.

B HEURISITC ALGORITHMS

  • The section gives pseudocode for the section 6.2 heuristics that generate antidote data for individual and group fairness.Source: B HEURISITC ALGORITHMS · p. 9

B.1 heuristic1

The two heuristics construct antidote data by setting item ratings from gradient information and repeating the resulting user profile to meet a budget.

B.1 heuristic1

  • Heuristic 1 starts with one antidote user, sets each rating to Mmin or Mmax according to the sign of the objective gradient, then copies the profile α times.The rule selects Mmin when the derivative is positive and Mmax otherwise.Source: §B.1 · p. 9

B.2 heuristic2

  • Heuristic 2 reshapes the objective gradient, projects each item’s gradient using the original factor U, sets ratings to Mmin or Mmax by the resulting sign, then copies the profile α times.The procedure forms an n × d gradient matrix and computes an item-specific value d[j] before choosing each rating.Source: §B.2 · pp. 9–10
Loading 1812.01504v4…