When Collaborative Filtering is not Collaborative: Unfairness of PCA for Recommendations

Authors

David Liu, Jackie Baek, Tina Eliassi‐Rad

Type: Article

Publication Date: 2025-06-23

Citations: 0

DOI: https://doi.org/10.1145/3715275.3732190

Ask PDF

Topics

Locations

arXiv (Cornell University)
View PDF

Ask a Question About This Paper

Summary

This paper delves into the critical issue of fairness in dimensionality reduction methods, specifically focusing on Principal Component Analysis (PCA) within recommender systems. It argues that while PCA is a fundamental technique for collaborative filtering, its inherent mechanisms can introduce significant “unfairness” at the item level, leading to suboptimal recommendations, especially for niche or highly popular content.

The core insight is the identification of two underlying popularity-driven mechanisms that cause this unfairness:

Underserving Less Popular Items: Less popular items often rely on the trailing principal components for accurate representation. Since PCA’s low-rank approximation inherently discards these components, unpopular items are poorly represented, leading to fewer or lower-quality recommendations for them. This means users with niche tastes might not find relevant content.
Specialization of Popular Items: For highly popular items, the leading PCA components tend to specialize in capturing information about individual popular items rather than their collaborative similarities with other items. This breaks the “collaborative” aspect that is central to good recommendations, as the system struggles to infer preferences for popular items based on a user’s interaction with other items. This can lead to popular items being recommended in a non-collaborative, almost siloed, manner.

To address these issues, the paper proposes a novel algorithm called Item-Weighted PCA (IWPCA). The key innovations of IWPCA are:

Weighted Objective: IWPCA introduces a flexible weighting scheme that up-weights less popular items in its objective function. This encourages the model to retain more information about these items, counteracting the first unfairness mechanism. The weighting is controlled by a parameter y (e.g., popularity^y), allowing for flexible interpolation.
Convex Formulation with Hard Rank Constraint: Unlike many previous weighted dimensionality reduction techniques that often lead to non-convex optimization problems or struggle to enforce strict rank constraints, IWPCA is formulated as a convex Semi-Definite Program (SDP). This guarantees a globally optimal solution and explicitly maintains the low-rank structure crucial for efficiency and interpretability in recommendations. The algorithm is shown to be solvable in polynomial time.
Theoretical Unification: The paper provides a significant theoretical contribution by demonstrating that both standard PCA (referred to as Vanilla PCA) and Normalized PCA (a common baseline that normalizes item vectors before PCA) are specific instances of IWPCA under certain conditions (y=0 for Vanilla PCA and y=-2 for Normalized PCA in specific matrix structures). This positions IWPCA as a generalized framework that can interpolate between these existing methods, balancing their respective strengths and weaknesses.

Main Prior Ingredients:

The work builds upon established foundations in:

Principal Component Analysis (PCA): Leveraging its mathematical framework for dimensionality reduction, singular value decomposition, and low-rank approximation.
Collaborative Filtering and Recommender Systems: Applying PCA within the context of user-item preference matrices and the goal of predicting user interest for unseen items.
Algorithmic Fairness: While prior work on fair PCA primarily focused on user-level fairness (e.g., balancing errors across demographic groups or obscuring sensitive attributes), this paper shifts the focus to item-level fairness and the internal mechanisms of the algorithm itself, rather than external fairness constraints.
Weighted Matrix Factorization/Dimensionality Reduction: Drawing on the concept of weighting elements in matrix decomposition, but innovating by ensuring convexity and a hard rank constraint, which were often challenges in prior weighted methods.
Popularity Bias in Recommender Systems: Addressing the well-known phenomenon of popular items being over-recommended, but tackling it at the level of the item’s representation within the model, rather than just post-processing recommendation lists or handling missing data.
Convex Optimization and Semi-Definite Programming (SDP): Utilizing the power of SDP to formulate a complex objective in a solvable manner, ensuring optimality guarantees.

Empirical evaluations on real-world datasets demonstrate that IWPCA effectively mitigates the identified unfairness mechanisms, leading to reduced specialization and increased collaboration among items, while simultaneously producing superior recommendation quality compared to PCA baselines. This work offers a deeper, mechanistic understanding of fairness issues in fundamental ML algorithms and provides a principled, effective solution.

When Collaborative Filtering is not Collaborative: Unfairness of PCA for Recommendations

2023-01-01

David Liu , Jackie Baek , Tina Eliassi‐Rad

We study the fairness of dimensionality reduction methods for recommendations. We focus on the established method of principal component analysis (PCA), which identifies latent components and produces a low-rank approximation … We study the fairness of dimensionality reduction methods for recommendations. We focus on the established method of principal component analysis (PCA), which identifies latent components and produces a low-rank approximation via the leading components while discarding the trailing components. Prior works have defined notions of "fair PCA"; however, these definitions do not answer the following question: what makes PCA unfair? We identify two underlying mechanisms of PCA that induce unfairness at the item level. The first negatively impacts less popular items, due to the fact that less popular items rely on trailing latent components to recover their values. The second negatively impacts the highly popular items, since the leading PCA components specialize in individual popular items instead of capturing similarities between items. To address these issues, we develop a polynomial-time algorithm, Item-Weighted PCA, a modification of PCA that uses item-specific weights in the objective. On a stylized class of matrices, we prove that Item-Weighted PCA using a specific set of weights minimizes a popularity-normalized error metric. Our evaluations on real-world datasets show that Item-Weighted PCA not only improves overall recommendation quality by up to $0.1$ item-level AUC-ROC but also improves on both popular and less popular items.

View PDF Chat

Collaborative filtering with privacy via factor analysis

2002-08-11

John Canny

Collaborative filtering (CF) is valuable in e-commerce, and for direct recommendations for music, movies, news etc. But today's systems have several disadvantages, including privacy risks. As we move toward ubiquitous … Collaborative filtering (CF) is valuable in e-commerce, and for direct recommendations for music, movies, news etc. But today's systems have several disadvantages, including privacy risks. As we move toward ubiquitous computing, there is a great potential for individuals to share all kinds of information about places and things to do, see and buy, but the privacy risks are severe. In this paper we describe a new method for collaborative filtering which protects the privacy of individual data. The method is based on a probabilistic factor analysis model. Privacy protection is provided by a peer-to-peer protocol which is described elsewhere, but outlined in this paper. The factor analysis approach handles missing data without requiring default values for them. We give several experiments that suggest that this is most accurate method for CF to date. The new algorithm has other advantages in speed and storage over previous algorithms. Finally, we suggest applications of the approach to other kinds of statistical analyses of survey or questionaire data.

View PDF Chat

"You Might Also Like:" Privacy Risks of Collaborative Filtering

2011-05-01

Joseph A. Calandrino , Ann Kilzer , Arvind Narayanan +2 more

Many commercial websites use recommender systems to help customers locate products and content. Modern recommenders are based on collaborative filtering: they use patterns learned from users' behavior to make recommendations, … Many commercial websites use recommender systems to help customers locate products and content. Modern recommenders are based on collaborative filtering: they use patterns learned from users' behavior to make recommendations, usually in the form of related-items lists. The scale and complexity of these systems, along with the fact that their outputs reveal only relationships between items (as opposed to information about users), may suggest that they pose no meaningful privacy risk. In this paper, we develop algorithms which take a moderate amount of auxiliary information about a customer and infer this customer's transactions from temporal changes in the public outputs of a recommender system. Our inference attacks are passive and can be carried out by any Internet user. We evaluate their feasibility using public data from popular websites Hunch, Last. fm, Library Thing, and Amazon.

View PDF Chat

Empirical Analysis of Predictive Algorithms for Collaborative Filtering

2013-01-01

John S. Breese , David Heckerman , Carl Kadie

Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed … Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity calculations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list. Experiments were run for datasets associated with 3 application areas, 4 experimental protocols, and the 2 evaluation metrics for the various algorithms. Results indicate that for a wide range of conditions, Bayesian networks with decision trees at each node and correlation methods outperform Bayesian-clustering and vector-similarity methods. Between correlation and Bayesian networks, the preferred method depends on the nature of the dataset, nature of the application (ranked versus one-by-one presentation), and the availability of votes with which to make predictions. Other considerations include the size of database, speed of predictions, and learning time.

Empirical Analysis of Predictive Algorithms for Collaborative Filtering

2013-01-30

John S. Breese , David Heckerman , Carl Kadie

Collaborative filtering with privacy

2005-08-25

John Canny

Server-based collaborative filtering systems have been very successful in e-commerce and in direct recommendation applications. In future, they have many potential applications in ubiquitous computing settings. But today's schemes have … Server-based collaborative filtering systems have been very successful in e-commerce and in direct recommendation applications. In future, they have many potential applications in ubiquitous computing settings. But today's schemes have problems such as loss of privacy, favoring retail monopolies, and with hampering diffusion of innovations. We propose an alternative model in which users control all of their log data. We describe an algorithm whereby a community of users can compute a public "aggregate" of their data that does not expose individual users' data. The aggregate allows personalized recommendations to be computed by members of the community, or by outsiders. The numerical algorithm is fast, robust and accurate. Our method reduces the collaborative filtering task to an iterative calculation of the aggregate requiring only addition of vectors of user data. Then we use homomorphic encryption to allow sums of encrypted vectors to be computed and decrypted without exposing individual data. We give verification schemes for all parties in the computation. Our system can be implemented with untrusted servers, or with additional infrastructure, as a fully peer-to-peer (P2P) system.

View PDF Chat

Alleviating the Sparsity Problem of Collaborative Filtering Using Trust Inferences

2005-01-01

Manos Papagelis , Dimitris Plexousakis , Themistoklis Kutsuras

Algorithms are not neutral: Bias in collaborative filtering

2021-01-01

Catherine Stinson

Discussions of algorithmic bias tend to focus on examples where either the data or the people building the algorithms are biased. This gives the impression that clean data and good … Discussions of algorithmic bias tend to focus on examples where either the data or the people building the algorithms are biased. This gives the impression that clean data and good intentions could eliminate bias. The neutrality of the algorithms themselves is defended by prominent Artificial Intelligence researchers. However, algorithms are not neutral. In addition to biased data and biased algorithm makers, AI algorithms themselves can be biased. This is illustrated with the example of collaborative filtering, which is known to suffer from popularity, and homogenizing biases. Iterative information filtering algorithms in general create a selection bias in the course of learning from user responses to documents that the algorithm recommended. These are not merely biases in the statistical sense; these statistical biases can cause discriminatory outcomes. Data points on the margins of distributions of human data tend to correspond to marginalized people. Popularity and homogenizing biases have the effect of further marginalizing the already marginal. This source of bias warrants serious attention given the ubiquity of algorithmic decision-making.

Data Sparsity Issues in the Collaborative Filtering Framework

2006-01-01

Miha Grćar , Dunja Mladenić , Blaž Fortuna +1 more

Collaborative Filtering: A Machine Learning Perspective

2004-01-01

Benjamin M. Marlin

A Theoretical Analysis of Two-Stage Recommendation for Cold-Start Collaborative Filtering

2016-01-01

Xiaoxue Zhao , Jun Wang

In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a … In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a limited number of resources (users or items) that can be allocated and related to them. The solution requires a trade-off between exploitation and exploration as with the limited recommendation opportunities, we need to, on one hand, allocate the most relevant resources right away, but, on the other hand, it is also necessary to allocate resources that are useful for learning the target's properties in order to recommend more relevant ones in the future. In this paper, we study a simple two-stage recommendation combining a sequential and a batch solution together. We first model the problem with the partially observable Markov decision process (POMDP) and provide an exact solution. Then, through an in-depth analysis over the POMDP value iteration solution, we identify that an exact solution can be abstracted as selecting resources that are not only highly relevant to the target according to the initial-stage information, but also highly correlated, either positively or negatively, with other potential resources for the next stage. With this finding, we propose an approximate solution to ease the intractability of the exact solution. Our initial results on synthetic data and the Movie Lens 100K dataset confirm the performance gains of our theoretical development and analysis.

View PDF Chat

A Theoretical Analysis of Two-Stage Recommendation for Cold-Start Collaborative Filtering

2015-09-22

Xiaoxue Zhao , Jun Wang

In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a … In this paper, we present a theoretical framework for tackling the cold-start collaborative filtering problem, where unknown targets (items or users) keep coming to the system, and there is a limited number of resources (users or items) that can be allocated and related to them. The solution requires a trade-off between exploitation and exploration since with the limited recommendation opportunities, we need to, on one hand, allocate the most relevant resources right away, but, on the other hand, it is also necessary to allocate resources that are useful for learning the target's properties in order to recommend more relevant ones in the future. In this paper, we study a simple two-stage recommendation combining a sequential and a batch solution together. We first model the problem with the partially observable Markov decision process (POMDP) and provide its exact solution. Then, through an in-depth analysis over the POMDP value iteration solution, we identify that an exact solution can be abstracted as selecting resources that are not only highly relevant to the target according to the initial-stage information, but also highly correlated, either positively or negatively, with other potential resources for the next stage. With this finding, we propose an approximate solution to ease the intractability of the exact solution. Our initial results on synthetic data and the MovieLens 100K dataset confirm our theoretical development and analysis.

View PDF Chat

Advances in Collaborative Filtering

2021-11-22

Yehuda Koren , Steffen Rendle , Robert Bell

Advances in Collaborative Filtering

2015-01-01

Yehuda Koren , Robert Bell

Advances in Collaborative Filtering

2010-10-05

Yehuda Koren , Robert Bell

Beyond Parity: Fairness Objectives for Collaborative Filtering

2017-01-01

Sirui Yao , Bert Huang

We study fairness in collaborative-filtering recommender systems, which are sensitive to discrimination that exists in historical data. Biased data can lead collaborative-filtering methods to make unfair predictions for users from … We study fairness in collaborative-filtering recommender systems, which are sensitive to discrimination that exists in historical data. Biased data can lead collaborative-filtering methods to make unfair predictions for users from minority groups. We identify the insufficiency of existing fairness metrics and propose four new metrics that address different forms of unfairness. These fairness metrics can be optimized by adding fairness terms to the learning objective. Experiments on synthetic and real data show that our new metrics can better measure fairness than the baseline, and that the fairness objectives effectively help reduce unfairness.

Explaining the Performance of Collaborative Filtering Methods with Optimal Data Characteristics

2023-03-11

Samin Poudel , Marwan Bikdash

The performance of a Collaborative Filtering (CF) method is based on the properties of a User-Item Rating Matrix (URM). And the properties or Rating Data Characteristics (RDC) of a URM … The performance of a Collaborative Filtering (CF) method is based on the properties of a User-Item Rating Matrix (URM). And the properties or Rating Data Characteristics (RDC) of a URM are constantly changing. Recent studies significantly explained the variation in the performances of CF methods resulted due to the change in URM using six or more RDC. Here, we found that the significant proportion of variation in the performances of different CF techniques can be accounted to two RDC only. The two RDC are the number of ratings per user or Information per User (IpU) and the number of ratings per item or Information per Item (IpI). And the performances of CF algorithms are quadratic to IpU (or IpI) for a square URM. The findings of this study are based on seven well-established CF methods and three popular public recommender datasets: 1M MovieLens, 25M MovieLens, and Yahoo! Music Rating datasets.

View PDF Chat

Rethinking Neural vs. Matrix-Factorization Collaborative Filtering: the Theoretical Perspectives

2021-01-01

Da Xu , Chuanwei Ruan , Evren Körpeoğlu +2 more

The recent work by Rendle et al. (2020), based on empirical observations, argues that matrix-factorization collaborative filtering (MCF) compares favorably to neural collaborative filtering (NCF), and conjectures the dot product's … The recent work by Rendle et al. (2020), based on empirical observations, argues that matrix-factorization collaborative filtering (MCF) compares favorably to neural collaborative filtering (NCF), and conjectures the dot product's superiority over the feed-forward neural network as similarity function. In this paper, we address the comparison rigorously by answering the following questions: 1. what is the limiting expressivity of each model; 2. under the practical gradient descent, to which solution does each optimization path converge; 3. how would the models generalize under the inductive and transductive learning setting. Our results highlight the similar expressivity for the overparameterized NCF and MCF as kernelized predictors, and reveal the relation between their optimization paths. We further show their different generalization behaviors, where MCF and NCF experience specific tradeoff and comparison in the transductive and inductive collaborative filtering setting. Lastly, by showing a novel generalization result, we reveal the critical role of correcting exposure bias for model evaluation in the inductive setting. Our results explain some of the previously observed conflicts, and we provide synthetic and real-data experiments to shed further insights to this topic.

View PDF Chat

The trade-off between data minimization and fairness in collaborative filtering

2024-09-20

Nasim Sonboli , S.J. Li , Mehdi Elahi +1 more

General Data Protection Regulations (GDPR) aim to safeguard individuals' personal information from harm. While full compliance is mandatory in the European Union and the California Privacy Rights Act (CPRA), it … General Data Protection Regulations (GDPR) aim to safeguard individuals' personal information from harm. While full compliance is mandatory in the European Union and the California Privacy Rights Act (CPRA), it is not in other places. GDPR requires simultaneous compliance with all the principles such as fairness, accuracy, and data minimization. However, it overlooks the potential contradictions within its principles. This matter gets even more complex when compliance is required from decision-making systems. Therefore, it is essential to investigate the feasibility of simultaneously achieving the goals of GDPR and machine learning, and the potential tradeoffs that might be forced upon us. This paper studies the relationship between the principles of data minimization and fairness in recommender systems. We operationalize data minimization via active learning (AL) because, unlike many other methods, it can preserve a high accuracy while allowing for strategic data collection, hence minimizing the amount of data collection. We have implemented several active learning strategies (personalized and non-personalized) and conducted a comparative analysis focusing on accuracy and fairness on two publicly available datasets. The results demonstrate that different AL strategies may have different impacts on the accuracy of recommender systems with nearly all strategies negatively impacting fairness. There has been no to very limited work on the trade-off between data minimization and fairness, the pros and cons of active learning methods as tools for implementing data minimization, and the potential impacts of AL on fairness. By exploring these critical aspects, we offer valuable insights for developing recommender systems that are GDPR compliant.

View PDF Chat

Understanding and Improving Adversarial Collaborative Filtering for Robust Recommendation

2024-10-30

Kaike Zhang , Qi Cao , Yunfan Wu +3 more

Adversarial Collaborative Filtering (ACF), which typically applies adversarial perturbations at user and item embeddings through adversarial training, is widely recognized as an effective strategy for enhancing the robustness of Collaborative … Adversarial Collaborative Filtering (ACF), which typically applies adversarial perturbations at user and item embeddings through adversarial training, is widely recognized as an effective strategy for enhancing the robustness of Collaborative Filtering (CF) recommender systems against poisoning attacks. Besides, numerous studies have empirically shown that ACF can also improve recommendation performance compared to traditional CF. Despite these empirical successes, the theoretical understanding of ACF's effectiveness in terms of both performance and robustness remains unclear. To bridge this gap, in this paper, we first theoretically show that ACF can achieve a lower recommendation error compared to traditional CF with the same training epochs in both clean and poisoned data contexts. Furthermore, by establishing bounds for reductions in recommendation error during ACF's optimization process, we find that applying personalized magnitudes of perturbation for different users based on their embedding scales can further improve ACF's effectiveness. Building on these theoretical understandings, we propose Personalized Magnitude Adversarial Collaborative Filtering (PamaCF). Extensive experiments demonstrate that PamaCF effectively defends against various types of poisoning attacks while significantly enhancing recommendation performance.

View PDF Chat

A multi-criteria collaborative filtering recommender system for the tourism domain using Expectation Maximization (EM) and PCA–ANFIS

2015-08-20

Mehrbakhsh Nilashi , Othman Ibrahim , Norafida Ithnin +1 more

The Rotation of Eigenvectors by a Perturbation. III

1970-03-01

Chandler Davis , W. Kahan

When a Hermitian linear operator is slightly perturbed, by how much can its invariant subspaces change? Given some approximations to a cluster of neighboring eigenvalues and to the corresponding eigenvectors … When a Hermitian linear operator is slightly perturbed, by how much can its invariant subspaces change? Given some approximations to a cluster of neighboring eigenvalues and to the corresponding eigenvectors of a real symmetric matrix, and given an estimate for the gap that separates the cluster from all other eigenvalues, how much can the subspace spanned by the eigenvectors differ from the subspace spanned by our approximations? These questions are closely related; both are investigated here. The difference between the two subspaces is characterized in terms of certain angles through which one subspace must be rotated in order most directly to reach the other. These angles unify the treatment of natural geometric, operator-theoretic and error-analytic questions concerning those subspaces. Sharp bounds upon trigonometric functions of these angles are obtained from the gap and from bounds upon either the perturbation (1st question) or a computable residual (2nd question). An example is included.

Collaborative filtering based on iterative principal component analysis

2005-01-14

Dong‐Hyun Kim , Bong‐Jin Yum

Multiplying matrices faster than coppersmith-winograd

2012-05-19

Virginia Vassilevska Williams

We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction. Using this approach we obtain a new improved bound on the matrix … We develop an automated approach for designing matrix multiplication algorithms based on constructions similar to the Coppersmith-Winograd construction. Using this approach we obtain a new improved bound on the matrix multiplication exponent ω<2.3727.

View PDF Chat

Item-based collaborative filtering recommendation algorithms

2001-04-01

Badrul Sarwar , George Karypis , Joseph A. Konstan +1 more

Article Share on Item-based collaborative filtering recommendation algorithms Authors: Badrul Sarwar GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN GroupLens Research … Article Share on Item-based collaborative filtering recommendation algorithms Authors: Badrul Sarwar GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MNView Profile , George Karypis GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MNView Profile , Joseph Konstan GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MNView Profile , John Riedl GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN GroupLens Research Group/Army HPC Research Center, Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MNView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001 Pages 285–295https://doi.org/10.1145/371920.372071Online:01 April 2001Publication History 4,816citation29,749DownloadsMetricsTotal Citations4,816Total Downloads29,749Last 12 Months2,414Last 6 weeks183 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

View PDF Chat

Item popularity and recommendation accuracy

2011-10-23

Harald Steck

Recommendations from the long tail of the popularity distribution of items are generally considered to be particularly valuable. On the other hand, recommendation accuracy tends to decrease towards the long … Recommendations from the long tail of the popularity distribution of items are generally considered to be particularly valuable. On the other hand, recommendation accuracy tends to decrease towards the long tail. In this paper, we quantitatively examine this trade-off between item popularity and recommendation accuracy. To this end, we assume that there is a selection bias towards popular items in the available data. This allows us to define a new accuracy measure that can be gradually tuned towards the long tail. We show that, under this assumption, this measure has the desirable property of providing nearly unbiased estimates concerning recommendation accuracy. In turn, this also motivates a refinement for training collaborative-filtering approaches. In various experiments with real-world data, including a user study, empirical evidence suggests that only a small, if any, bias of the recommendations towards less popular items is appreciated by users.

Analysis of a complex of statistical variables into principal components.

1933-09-01

H. Hotelling

A useful variant of the Davis–Kahan theorem for statisticians

2015-04-28

Yi Yu , Tengyao Wang , Richard J. Samworth

Journal Article A useful variant of the Davis–Kahan theorem for statisticians Get access Y. Yu, Y. Yu Statistical Laboratory, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, U.K., [email protected]@[email protected] Search … Journal Article A useful variant of the Davis–Kahan theorem for statisticians Get access Y. Yu, Y. Yu Statistical Laboratory, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, U.K., [email protected]@[email protected] Search for other works by this author on: Oxford Academic Google Scholar T. Wang, T. Wang Statistical Laboratory, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, U.K., [email protected]@[email protected] Search for other works by this author on: Oxford Academic Google Scholar R. J. Samworth R. J. Samworth Statistical Laboratory, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, U.K., [email protected]@[email protected] Search for other works by this author on: Oxford Academic Google Scholar Biometrika, Volume 102, Issue 2, June 2015, Pages 315–323, https://doi.org/10.1093/biomet/asv008 Published: 28 April 2014 Article history Published: 28 April 2014 Received: 01 May 2014 Revision received: 01 February 2015

View PDF Chat

Collaborative Filtering for Implicit Feedback Datasets

2008-12-01

Yifan Hu , Yehuda Koren , Chris Volinsky

A common task of recommender systems is to improve customer experience through personalized recommendations based on prior implicit feedback. These systems passively track different sorts of user behavior, such as … A common task of recommender systems is to improve customer experience through personalized recommendations based on prior implicit feedback. These systems passively track different sorts of user behavior, such as purchase history, watching habits and browsing activity, in order to model user preferences. Unlike the much more extensively researched explicit feedback, we do not have any direct input from the users regarding their preferences. In particular, we lack substantial evidence on which products consumer dislike. In this work we identify unique properties of implicit feedback datasets. We propose treating the data as indication of positive and negative preference associated with vastly varying confidence levels. This leads to a factor model which is especially tailored for implicit feedback recommenders. We also suggest a scalable optimization procedure, which scales linearly with the data size. The algorithm is used successfully within a recommender system for television shows. It compares favorably with well tuned implementations of other known methods. In addition, we offer a novel way to give explanations to recommendations given by this factor model.

None

2001-01-01

Ken Goldberg , Thomas Roeder , Dhruv Gupta +1 more

Smallest singular value of a random rectangular matrix

2009-06-29

Mark Rudelson , Roman Vershynin

Abstract We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and … Abstract We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and identically distributed sub‐Gaussian entries, the smallest singular value of A is at least of the order √ N − √ n − 1 with high probability. A sharp estimate on the probability is also obtained. © 2009 Wiley Periodicals, Inc.

View PDF Chat

The MovieLens Datasets

2015-12-22

F. Maxwell Harper , Joseph A. Konstan

The MovieLens datasets are widely used in education, research, and industry. They are downloaded hundreds of thousands of times each year, reflecting their use in popular press programming books, traditional … The MovieLens datasets are widely used in education, research, and industry. They are downloaded hundreds of thousands of times each year, reflecting their use in popular press programming books, traditional and online courses, and software. These datasets are a product of member activity in the MovieLens movie recommendation system, an active research platform that has hosted many experiments since its launch in 1997. This article documents the history of MovieLens and the MovieLens datasets. We include a discussion of lessons learned from running a long-standing, live research platform from the perspective of a research organization. We document best practices and limitations of using the MovieLens datasets in new research.

LIII. On lines and planes of closest fit to systems of points in space

1901-11-01

Karl Pearson

(1901). LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science: Vol. 2, No. 11, … (1901). LIII. On lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science: Vol. 2, No. 11, pp. 559-572.

View PDF Chat

Controlling Popularity Bias in Learning-to-Rank Recommendation

2017-08-24

Himan Abdollahpouri , Robin Burke , Bamshad Mobasher

Many recommendation algorithms suffer from popularity bias in their output: popular items are recommended frequently and less popular ones rarely, if at all. However, less popular, long-tail items are precisely … Many recommendation algorithms suffer from popularity bias in their output: popular items are recommended frequently and less popular ones rarely, if at all. However, less popular, long-tail items are precisely those that are often desirable recommendations. In this paper, we introduce a flexible regularization-based framework to enhance the long-tail coverage of recommendation lists in a learning-to-rank algorithm. We show that regularization provides a tunable mechanism for controlling the trade-off between accuracy and coverage. Moreover, the experimental results using two data sets show that it is possible to improve coverage of long tail items without substantial loss of ranking performance.

Convex Formulations for Fair Principal Component Analysis

2019-07-17

Matt Olfat , Anil Aswani

Though there is a growing literature on fairness for supervised learning, incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of principal component … Though there is a growing literature on fairness for supervised learning, incorporating fairness into unsupervised learning has been less well-studied. This paper studies fairness in the context of principal component analysis (PCA). We first define fairness for dimensionality reduction, and our definition can be interpreted as saying a reduction is fair if information about a protected class (e.g., race or gender) cannot be inferred from the dimensionality-reduced data points. Next, we develop convex optimization formulations that can improve the fairness (with respect to our definition) of PCA and kernel PCA. These formulations are semidefinite programs, and we demonstrate their effectiveness using several datasets. We conclude by showing how our approach can be used to perform a fair (with respect to age) clustering of health data that may be used to set health insurance rates.

View PDF Chat

LightGCN

2020-07-25

Xiangnan He , Kuan Deng , Xiang Wang +3 more

Graph Convolution Network (GCN) has become new state-of-the-art for collaborative filtering. Nevertheless, the reasons of its effectiveness for recommendation are not well understood. Existing work that adapts GCN to recommendation … Graph Convolution Network (GCN) has become new state-of-the-art for collaborative filtering. Nevertheless, the reasons of its effectiveness for recommendation are not well understood. Existing work that adapts GCN to recommendation lacks thorough ablation analyses on GCN, which is originally designed for graph classification tasks and equipped with many neural network operations. However, we empirically find that the two most common designs in GCNs -- feature transformation and nonlinear activation -- contribute little to the performance of collaborative filtering. Even worse, including them adds to the difficulty of training and degrades recommendation performance.

Principal Component Analysis with Noisy and/or Missing Data

2012-09-01

S. Bailey

We present a method for performing Principal Component Analysis (PCA) on noisy datasets with missing values. Estimates of the measurement error are used to weight the input data such that … We present a method for performing Principal Component Analysis (PCA) on noisy datasets with missing values. Estimates of the measurement error are used to weight the input data such that compared to classic PCA, the resulting eigenvectors are more sensitive to the true underlying signal variations rather than being pulled by heteroskedastic measurement noise. Missing data is simply the limiting case of weight=0. The underlying algorithm is a noise weighted Expectation Maximization (EM) PCA, which has additional benefits of implementation speed and flexibility for smoothing eigenvectors to reduce the noise contribution. We present applications of this method on simulated data and QSO spectra from the Sloan Digital Sky Survey.

View PDF Chat

Popularity-Opportunity Bias in Collaborative Filtering

2021-03-06

Ziwei Zhu , Yun He , Xing Zhao +3 more

This paper connects equal opportunity to popularity bias in implicit recommenders to introduce the problem of popularity-opportunity bias. That is, conditioned on user preferences that a user likes both items, … This paper connects equal opportunity to popularity bias in implicit recommenders to introduce the problem of popularity-opportunity bias. That is, conditioned on user preferences that a user likes both items, the more popular item is more likely to be recommended (or ranked higher) to the user than the less popular one. This type of bias is harmful, exerting negative effects on the engagement of both users and item providers. Thus, we conduct a three-part study: (i) By a comprehensive empirical study, we identify the existence of the popularity-opportunity bias in fundamental matrix factorization models on four datasets; (ii) coupled with this empirical study, our theoretical study shows that matrix factorization models inherently produce the bias; and (iii) we demonstrate the potential of alleviating this bias by both in-processing and post-processing algorithms. Extensive experiments on four datasets show the effective debiasing performance of these proposed methods compared with baselines designed for conventional popularity bias.

A Faster Interior Point Method for Semidefinite Programming

2020-11-01

Haotian Jiang , Tarun Kathuria , Yin Tat Lee +2 more

Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents … Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size n ×n and m constraints in time Õ(√n(mn 2 +m ω +n ω )log(1/ε)), \end{equation*} where ω is the exponent of matrix multiplication and ε is the relative accuracy. In the predominant case of m ≥ n, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method [JLSW20]. Our algorithm's runtime can be naturally interpreted as follows: O(√nlog(1/ε)) is the number of iterations needed for our interior point method, mn 2 is the input size, and m ω +n ω is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.

View PDF Chat

Popularity Bias in Dynamic Recommendation

2021-08-12

Ziwei Zhu , Yun He , Xing Zhao +1 more

Popularity bias is a long-standing challenge in recommender systems: popular items are overly recommended at the expense of less popular items that users may be interested in being under-recommended. Such … Popularity bias is a long-standing challenge in recommender systems: popular items are overly recommended at the expense of less popular items that users may be interested in being under-recommended. Such a bias exerts detrimental impact on both users and item providers, and many efforts have been dedicated to studying and solving such a bias. However, most existing works situate the popularity bias in a static setting, where the bias is analyzed only for a single round of recommendation with logged data. These works fail to take account of the dynamic nature of real-world recommendation process, leaving several important research questions unanswered: how does the popularity bias evolve in a dynamic scenario? what are the impacts of unique factors in a dynamic recommendation process on the bias? and how to debias in this long-term dynamic process? In this work, we investigate the popularity bias in dynamic recommendation and aim to tackle these research gaps. Concretely, we conduct an empirical study by simulation experiments to analyze popularity bias in the dynamic scenario and propose a dynamic debiasing strategy and a novel False Positive Correction method utilizing false positive signals to debias, which show effective performance in extensive experiments.

Fast and Efficient MMD-Based Fair PCA via Optimization over Stiefel Manifold

2022-06-28

Jung-Hyun Lee , Gwangsu Kim , Mahbod Olfat +2 more

This paper defines fair principal component analysis (PCA) as minimizing the maximum mean discrepancy (MMD) between the dimensionality-reduced conditional distributions of different protected classes. The incorporation of MMD naturally leads … This paper defines fair principal component analysis (PCA) as minimizing the maximum mean discrepancy (MMD) between the dimensionality-reduced conditional distributions of different protected classes. The incorporation of MMD naturally leads to an exact and tractable mathematical formulation of fairness with good statistical properties. We formulate the problem of fair PCA subject to MMD constraints as a non-convex optimization over the Stiefel manifold and solve it using the Riemannian Exact Penalty Method with Smoothing (REPMS). Importantly, we provide a local optimality guarantee and explicitly show the theoretical effect of each hyperparameter in practical settings, extending previous results. Experimental comparisons based on synthetic and UCI datasets show that our approach outperforms prior work in explained variance, fairness, and runtime.

View PDF Chat

Efficient fair principal component analysis

2022-01-06

Mohammad Mahdi Kamani , Farzin Haddadpour , Rana Forsati +1 more

View PDF Chat

Second workshop on information heterogeneity and fusion in recommender systems (HetRec2011)

2011-10-23

Iván Cantador , Peter Brusilovsky , Tsvi Kuflik

No abstract available. No abstract available.

View PDF Chat

A novel approach for Fair Principal Component Analysis based on eigendecomposition

2022-01-01

Guilherme Dean Pelegrina , Leonardo Tomazeli Duarte

Principal component analysis (PCA), a ubiquitous dimensionality reduction technique in signal processing, searches for a projection matrix that minimizes the mean squared error between the reduced dataset and the original … Principal component analysis (PCA), a ubiquitous dimensionality reduction technique in signal processing, searches for a projection matrix that minimizes the mean squared error between the reduced dataset and the original one. Since classical PCA is not tailored to address concerns related to fairness, its application to actual problems may lead to disparity in the reconstruction errors of different groups (e.g., men and women, whites and blacks, etc.), with potentially harmful consequences such as the introduction of bias towards sensitive groups. Although several fair versions of PCA have been proposed recently, there still remains a fundamental gap in the search for algorithms that are simple enough to be deployed in real systems. To address this, we propose a novel PCA algorithm which tackles fairness issues by means of a simple strategy comprising a one-dimensional search which exploits the closed-form solution of PCA. As attested by numerical experiments, the proposal can significantly improve fairness with a very small loss in the overall reconstruction error and without resorting to complex optimization schemes. Moreover, our findings are consistent in several real situations as well as in scenarios with both unbalanced and balanced datasets.

Cluster Anchor Regularization to Alleviate Popularity Bias in Recommender Systems

2024-05-12

Bo Chang , Changping Meng , He Ma +7 more

Recommender systems are essential for finding personalized content for users on online platforms. These systems are often trained on historical user interaction data, which collects user feedback on system recommendations. … Recommender systems are essential for finding personalized content for users on online platforms. These systems are often trained on historical user interaction data, which collects user feedback on system recommendations. This creates a feedback loop leading to popularity bias; popular content is over-represented in the data, better learned, and thus recommended even more. Less popular content struggles to reach its potential audiences. Popularity bias limits the diversity of content that users are exposed to, and makes it harder for new creators to gain traction. Existing methods to alleviate popularity bias tend to trade off the performance of popular items. In this work, we propose a new method for alleviating popularity bias in recommender systems, called the cluster anchor regularization, which partitions the large item corpus into hierarchical clusters, and then leverages the cluster information of each item to facilitate transfer learning from head items to tail items. Our results demonstrate the effectiveness of the proposed method with offline analyses and live experiments on a large-scale industrial recommendation platform, where it significantly increases tail recommendation without hurting the overall user experience.

View PDF Chat

Large Language Models Portray Socially Subordinate Groups as More Homogeneous, Consistent with a Bias Observed in Humans

2024-06-03

Messi Ho Jun Lee , Jacob Montgomery , Calvin K. Lai

Large language models (LLMs) are becoming pervasive in everyday life, yet their propensity to reproduce biases inherited from training data remains a pressing concern. Prior investigations into bias in LLMs … Large language models (LLMs) are becoming pervasive in everyday life, yet their propensity to reproduce biases inherited from training data remains a pressing concern. Prior investigations into bias in LLMs have focused on the association of social groups with stereotypical attributes. However, this is only one form of human bias such systems may reproduce. We investigate a new form of bias in LLMs that resembles a social psychological phenomenon where socially subordinate groups are perceived as more homogeneous than socially dominant groups. We had ChatGPT, a state-of-the-art LLM, generate texts about intersectional group identities and compared those texts on measures of homogeneity. We consistently found that ChatGPT portrayed African, Asian, and Hispanic Americans as more homogeneous than White Americans, indicating that the model described racial minority groups with a narrower range of human experience. ChatGPT also portrayed women as more homogeneous than men, but these differences were small. Finally, we found that the effect of gender differed across racial/ethnic groups such that the effect of gender was consistent within African and Hispanic Americans but not within Asian and White Americans. We argue that the tendency of LLMs to describe groups as less diverse risks perpetuating stereotypes and discriminatory behavior.

View PDF Chat

A survey on popularity bias in recommender systems

2024-07-01

Anastasiia Klimashevskaia , Dietmar Jannach , Mehdi Elahi +1 more

Abstract Recommender systems help people find relevant content in a personalized way. One main promise of such systems is that they are able to increase the visibility of items in … Abstract Recommender systems help people find relevant content in a personalized way. One main promise of such systems is that they are able to increase the visibility of items in the long tail , i.e., the lesser-known items in a catalogue. Existing research, however, suggests that in many situations today’s recommendation algorithms instead exhibit a popularity bias , meaning that they often focus on rather popular items in their recommendations. Such a bias may not only lead to the limited value of the recommendations for consumers and providers in the short run, but it may also cause undesired reinforcement effects over time. In this paper, we discuss the potential reasons for popularity bias and review existing approaches to detect, quantify and mitigate popularity bias in recommender systems. Our survey, therefore, includes both an overview of the computational metrics used in the literature as well as a review of the main technical approaches to reduce the bias. Furthermore, we critically discuss today’s literature, where we observe that the research is almost entirely based on computational experiments and on certain assumptions regarding the practical effects of including long-tail items in the recommendations.

View PDF Chat

Large language models that replace human participants can harmfully misportray and flatten identity groups

2025-02-17

Angelina Wang , Jamie Morgenstern , John P. Dickerson