Probably Approximately Precision and Recall Learning
summary
Introduces a learning model where each training point is a user plus one liked item, shows that only positive samples make unbiased precision estimates impossible, and proves that maximum likelihood selection yields provably high precision and recall in the realizable case with sample size scaling with log degrees and standard generalization bounds. For the agnostic case the paper proves an unavoidable multiplicative tradeoff — a constant gap of about 5 versus a theoretical lower bound near 1.05 — so joint optimality is impossible.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 1:05Personal anecdotes
- 3:39PAC learning fundamentals
- 7:55Precision and recall
- 11:50User-item interactions
- 17:11Realizable setting
- 24:13Agnostic setting
- 26:20Multi-objective learning
- 29:15Evaluation nuances
- 31:01Closing and Q&A
related talks
33mTradeoffs in Large Scale Learning: Statistical Accuracy vs. Numerical Precision
17mData privacy and reliable learning
25mConfidence-Based Active Learning
29mEfficient Minimax Optimal Strategies for Universal Prediction
01h 07mDoes generalization imply accuracy on the line? A new look at robust generalization
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals
01h 21mMulticalibration: Towards Fair Decision Making
59mTesting Assumptions of Learning Algorithms