Recommender systems are crucial components of most commercial websites to keep users satisfied and to increase revenue. Thus, a lot of effort is made to improve recommendation accuracy. But when is the best possible performance of the recommender reached? The magic barrier, refers to some unknown level of prediction accuracy a recommender system can attain. The magic barrier reveals whether there is still room for improving prediction accuracy or indicates that further improvement is meaningless. In this work, we present a mathematical characterization of the magic barrier based on the assumption that user ratings are afflicted with inconsistencies - noise. In a case study with a commercial movie recommender, we investigate the inconsistencies of the user ratings and estimate the magic barrier in order to assess the actual quality of the recommender system.
DSPy a system for AI to Write Prompts and Do Fine Tuning
Β
Users and Noise: The Magic Barrier of Recommender Systems
1. Users and Noise: The Magic Barrier of Recommender Systems
Alan Said, Brijnesh J. Jain, Sascha Narr, Till Plumbaum
Competence Center Information Retrieval & Machine Learning
@alansaid, @saschanarr, @matip
2. Outline
βΊ The Magic Barrier
βΊ Empirical Risk Minimization
βΊ Deriving the Magic Barrier
βΊ User Study
βΊ Conclusion
20 July 2012 The Magic Barrier 2
4. The Magic Barrier
βΊ No magic involved....
βΊ Coined by Herlocker et al. in 2004
ο§ β...an algorithm cannot be more accurate than the variance in
a userβs ratings for the same item.β
ο§ The maximum level of prediction that a recommender
algorithm can attain.
βΊ What does this mean?
20 July 2012 The Magic Barrier 4
6. The Magic Barrier
βΊ Even a βperfectβ recommender should not reach RMSE = 0 or
Precision @ N = 1
βΊ Why?
ο§ People are inconsistent and noisy in their ratings
ο§ βperfectβ accuracy is not perfect
βΊ So?
ο§ Knowing the highest possible level of accuracy, we can stop
optimizing our algorithms at βperfectβ (before overfitting)
20 July 2012 The Magic Barrier 6
7. The Magic Barrier
So β how do we find the magic barrier?
We employ the Empirical Risk Minimization principle and a
statistical model for user inconsistencies
20 July 2012 The Magic Barrier 7
8. The Magic Barrier β User Inconsistencies
Assumption:
ο§ If a user were to re-rate all previously rated items, keeping in
mind the inconsistency, the ratings would differ, i.e.
π π’π = π π’π + π π’π
ο§ where
ο π π’π is the expected rating, and
ο π π’π the rating error (has zero mean)
20 July 2012 The Magic Barrier 8
9. Empirical Risk Minimization
βΊ β¦ is a principle in statistical learning theory which defines a
family of learning algorithms and is used to give theoretical
bounds on the performance of learning
algorithms.[Wikipedia]
20 July 2012 The Magic Barrier 9
10. Empirical Risk Minimization
βΊ We formulate our risk function as
ο§ π π = π’,π,π π π’, π, π π π’, π β π 2 The prediction error
The probability of user u rating item i with score r
βΊ Keeping the assumption in mind, we formulate the risk for a
true, unknown, rating function as the sum of the noise
variance, i.e.
ο§ π πβ = π’,π π π’, π π π π’π
ο§ where π π π’π is the noise variance
20 July 2012 The Magic Barrier 10
11. Deriving the Magic Barrier
βΊ We want to express the risk function in terms of a magic barrier
for RMSE β we take the root of the risk function
ο§ β¬ π°Γβ = π’,π π π’, π π π π’π
ο§ RMSE=0 iff π π’π = 0 over all ratings users and items
βΊ In terms of RMSE we can express this as
ο§ πΈ π πππΈ π = β¬ π°Γβ + πΈ π > β¬ π°Γβ
ο§ where πΈ π is the error
20 July 2012 The Magic Barrier 11
12. Estimating the Magic Barrier
1. For each user-item pair in our population
a) Sample ratings on a regular basis, i.e. re-ratings
b) Estimate the expected value of ratings
π
1
π π’π = π π‘ π’π
π
π‘=1
c. Estimate the rating variance
π
1 2
π π’π 2
=
π
π π’π β ππ‘ π’π
π‘=1
2. Estimate the magic barrier by taking the average
1
β¬= π π’π 2
π³
π’π βπ³
20 July 2012 The Magic Barrier 12
14. A User Study
βΊ We teamed up with moviepilot.de
ο§ Germanyβs largest online movie recommendation community
ο§ Ratings scale 1-10 stars (Netflix: 1-5 stars)
βΊ Created a re-rating UI
ο§ Users were asked to re-rate at least 20 movies
ο§ 1 new rating (so-called opinions) per movie
ο§ Collected data:
ο§ 306 users
ο§ 6,299 new opinions
ο§ 2,329 movies
20 July 2012 The Magic Barrier 14
15. A User Study
User study moviepilot
20 July 2012 The Magic Barrier 15
16. A User Study
~4 ratings steps Room for improvement
~1 rating steps
Predictions vs Ratings above Ratings below
Ratings userβs average userβs average
Overall Opinions above Opinions below
Magic Barrier userβs average userβs average
20 July 2012 The Magic Barrier 16
17. Conclusion
βΊ We created a mathematical characterization of the magic
barrier
βΊ We performed a user study on a commercial movie
recommendation website and estimated its magic barrier
βΊ We concluded the commercial recommender engine still has
room for improvement
βΊ No magic
20 July 2012 The Magic Barrier 17
18. More?
βΊ Estimating the Magic Barrier of Recommender Systems: A User Study
ο§ SIGIR 2012
βΊ Magic Barrier explained
ο§ http://irml.dailab.de
βΊ Movie rating and explanation user study
ο§ http://j.mp/ratingexplain
βΊ Recommender Systems Wiki
ο§ www.recsyswiki.com
βΊ Recommender Systems Challenge
ο§ www.recsyschallenge.com
20 July 2012 The Magic Barrier 18
19. Questions?
βΊ Thank You for Listening!
20 July 2012 The Magic Barrier 19