Patterns and probabilities : a study in algorithmic randomness and computable learning
Abstract/Contents
- Abstract
- This dissertation connects the theory of algorithmic randomness—a branch of computability theory—with the foundations of induction. Algorithmic randomness provides a mathematical analysis of the notion of a sequence displaying no effective regularities. In my dissertation, I investigate the role that algorithmic randomness plays in inductive learning when randomness is taken to be a property of sequences of observations (or data streams) and the learners are computationally limited. In the first chapter, I show that the algorithmically random data streams are exactly the ones that ensure that a computable Bayesian agent's beliefs will asymptotically converge to the truth. In the second chapter, I show that algorithmic randomness leads to Bayesian merging of opinions. When two computable Bayesian agents perform the same experiment, agreeing on which data streams are algorithmically random suffices to guarantee that they will eventually reach a consensus. In the third and final chapter, I study a learning-theoretic approach—in the spirit of formal learning theory—for modelling algorithmic randomness itself. My main finding is that, in this context, the algorithmically random data streams can be systematically shown to coincide with the ones from which no computable qualitative learning method can extrapolate any patterns.
Description
Type of resource | text |
---|---|
Form | electronic resource; remote; computer; online resource |
Extent | 1 online resource. |
Place | California |
Place | [Stanford, California] |
Publisher | [Stanford University] |
Copyright date | 2020; ©2020 |
Publication date | 2020; 2020 |
Issuance | monographic |
Language | English |
Creators/Contributors
Author | Zaffora Blando, Francesca |
---|---|
Degree supervisor | van Benthem, Johan |
Thesis advisor | van Benthem, Johan |
Thesis advisor | Briggs, R. A, 1982- |
Thesis advisor | Diaconis, Persi |
Thesis advisor | Icard, Thomas |
Thesis advisor | Skyrms, Brian |
Degree committee member | Briggs, R. A, 1982- |
Degree committee member | Diaconis, Persi |
Degree committee member | Icard, Thomas |
Degree committee member | Skyrms, Brian |
Associated with | Stanford University, Department of Philosophy. |
Subjects
Genre | Theses |
---|---|
Genre | Text |
Bibliographic information
Statement of responsibility | Francesca Zaffora Blando. |
---|---|
Note | Submitted to the Department of Philosophy. |
Thesis | Thesis Ph.D. Stanford University 2020. |
Location | electronic resource |
Access conditions
- Copyright
- © 2020 by Francesca Zaffora Blando
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...