Document Open Access Logo

The Complexity of User Retention

Authors Eli Ben-Sasson , Eden Saig

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.12.pdf
  • Filesize: 0.51 MB
  • 30 pages

Document Identifiers

Author Details

Eli Ben-Sasson
  • Department of Computer Science, Technion, Haifa, Israel
Eden Saig
  • Department of Computer Science, Technion, Haifa, Israel

Funding

This work was supported by the Israeli Science Foundation under grant number 1501/14.

Cite As Get BibTex

Eli Ben-Sasson and Eden Saig. The Complexity of User Retention. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 12:1-12:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.12

Abstract

This paper studies families of distributions T that are amenable to retentive learning, meaning that an expert can retain users that seek to predict their future, assuming user attributes are sampled from T and exposed gradually over time. Limited attention span is the main problem experts face in our model. We make two contributions.
First, we formally define the notions of retentively learnable distributions and properties. Along the way, we define a retention complexity measure of distributions and a natural class of retentive scoring rules that model the way users evaluate experts they interact with. These rules are shown to be tightly connected to truth-eliciting "proper scoring rules" studied in Decision Theory since the 1950's [McCarthy, PNAS 1956].
Second, we take a first step towards relating retention complexity to other measures of significance in computational complexity. In particular, we show that linear properties (over the binary field) are retentively learnable, whereas random Low Density Parity Check (LDPC) codes have, with high probability, maximal retention complexity. Intriguingly, these results resemble known results from the field of property testing and suggest that deeper connections between retentive distributions and locally testable properties may exist.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • retentive learning
  • retention complexity
  • information elicitation
  • proper scoring rules

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  2. Amir Ban and Nati Linial. The dynamics of reputation systems. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, pages 91-100. ACM, 2011. Google Scholar
  3. Ayelet Ben-Sasson, Eli Ben-Sasson, Kayla Jacobs, and Eden Saig. Baby CROINC: An Online, Crowd-based, Expert-curated System for Monitoring Child Development. In Proceedings of the 11th EAI International Conference on Pervasive Computing Technologies for Healthcare, PervasiveHealth '17, pages 110-119, New York, NY, USA, 2017. ACM. URL: http://dx.doi.org/10.1145/3154862.3154887.
  4. Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova. Some 3CNF properties are hard to test. SIAM Journal on Computing, 35(1):1-21, 2005. Google Scholar
  5. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 73-83, 1990. URL: http://dx.doi.org/10.1145/100216.100225.
  6. Glenn W Brier. Verification of forecasts expressed in terms of probability. Monthly weather review, 78(1):1-3, 1950. Google Scholar
  7. Kam Tong Chan, Irwin King, and Man-Ching Yuen. Mathematical modeling of social games. In Computational Science and Engineering, 2009. CSE'09. International Conference on, volume 4, pages 1205-1210. IEEE, 2009. Google Scholar
  8. Alexander Philip Dawid and Monica Musio. Theory and applications of proper scoring rules. Metron, 72(2):169-183, 2014. Google Scholar
  9. Gideon Dror, Dan Pelleg, Oleg Rokhlenko, and Idan Szpektor. Churn prediction in new users of Yahoo! answers. In Proceedings of the 21st International Conference on World Wide Web, pages 829-834. ACM, 2012. Google Scholar
  10. Robert Gallager. Low-density parity-check codes. IRE Transactions on information theory, 8(1):21-28, 1962. Google Scholar
  11. Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378, 2007. Google Scholar
  12. Michael H. Goldhaber. The attention economy and the Net. First Monday, 2(4), 1997. URL: http://dx.doi.org/10.5210/fm.v2i4.519.
  13. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 45(4):653-750, 1998. Google Scholar
  14. Gradient Theorem. Gradient Theorem - Wikipedia, The Free Encyclopedia, 2017. [Online; accessed 08-September-2017]. URL: https://en.wikipedia.org/w/index.php?title=Gradient_theorem&oldid=781791224.
  15. Arlo D Hendrickson and Robert J Buehler. Proper scores for probability forecasters. The Annals of Mathematical Statistics, pages 1916-1921, 1971. Google Scholar
  16. Richard A Lanham. The economics of attention: Style and substance in the age of information. University of Chicago Press, 2006. Google Scholar
  17. John McCarthy. Measures of the value of information. Proceedings of the National Academy of Sciences, 42(9):654-655, 1956. Google Scholar
  18. George A Miller. The magical number seven, plus or minus two: some limits on our capacity for processing information. Psychological review, 63(2):81, 1956. Google Scholar
  19. Yehuda Pinchover and Jacob Rubinstein. An introduction to partial differential equations. Cambridge university press, 2005. Google Scholar
  20. Paul Resnick, Ko Kuwabara, Richard Zeckhauser, and Eric Friedman. Reputation systems. Communications of the ACM, 43(12):45-48, 2000. Google Scholar
  21. Paul Resnick and Richard Zeckhauser. Trust among strangers in Internet transactions: Empirical analysis of eBay’s reputation system. In The Economics of the Internet and E-commerce, pages 127-157. Emerald Group Publishing Limited, 2002. Google Scholar
  22. Ralph Tyrell Rockafellar. Convex analysis. Princeton university press, 2015. Google Scholar
  23. Leonard J Savage. Elicitation of personal probabilities and expectations. Journal of the American Statistical Association, 66(336):783-801, 1971. Google Scholar
  24. Endel Tulving and Fergus IM Craik. The Oxford handbook of memory. Oxford: Oxford University Press, 2000. Google Scholar
  25. Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134-1142, 1984. Google Scholar
  26. Chih-Ping Wei and I-Tang Chiu. Turning telecommunications call details to churn prediction: a data mining approach. Expert systems with applications, 23(2):103-112, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact