nips nips2003 nips2003-75 nips2003-75-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Thomas L. Griffiths, Joshua B. Tenenbaum
Abstract: We explore the phenomena of subjective randomness as a case study in understanding how people discover structure embedded in noise. We present a rational account of randomness perception based on the statistical problem of model selection: given a stimulus, inferring whether the process that generated it was random or regular. Inspired by the mathematical definition of randomness given by Kolmogorov complexity, we characterize regularity in terms of a hierarchy of automata that augment a finite controller with different forms of memory. We find that the regularities detected in binary sequences depend upon presentation format, and that the kinds of automata that can identify these regularities are informative about the cognitive processes engaged by different formats. 1
[1] D. Kahneman and A. Tversky. Subjective probability: A judgment of representativeness. Cognitive Psychology, 3:430–454, 1972.
[2] T. L. Griffiths and J. B. Tenenbaum. Probability, algorithmic complexity and subjective randomness. In Proceedings of the 25th Annual Conference of the Cognitive Science Society, Hillsdale, NJ, 2003. Erlbaum.
[3] R. J. Solomonoff. A formal theory of inductive inference. Part I. Information and Control, 7:1–22, 1964.
[4] A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1–7, 1965.
[5] G. J. Chaitin. On the length of programs for computing finite binary sequences: statistical considerations. Journal of the ACM, 16:145–159, 1969.
[6] R. Falk and C. Konold. Making sense of randomness: Implicit encoding as a bias for judgment. Psychological Review, 104:301–318, 1997.
[7] N. Chomsky. Threee models for the description of language. IRE Transactions on Information Theory, 2:113–124, 1956.
[8] A. Cherubini, C. Citrini, S. C. Reghizzi, and D. Mandrioli. QRT FIFO automata, breadth-first grammars and their relations. Theoretical Comptuer Science, 85:171–203, 1991.
[9] S. Ginsburg, S. A. Greibach, and M. A. Harrison. Stack automata and compiling. Journal of the ACM, 14:172–201, 1967.
[10] A. V. Aho. Indexed grammars – an extension of context-free grammars. Journal of the ACM, 15:647–671, 1968.