@Article{RS93b, author = { Ronald L. Rivest and Robert H. Sloan }, title = { On choosing between experimenting and thinking when learning }, journal = { Information and Computation }, issn = { 0890-5401 }, OPTyear = { 1993 }, OPTmonth = { September }, date = { 1993-09 }, volume = { 106 }, number = { 1 }, pages = { 1--25 }, doi = { 10.1006/inco.1993.1047 }, url = { http://www.sciencedirect.com/science/article/pii/S0890540183710473 }, abstract = { We introduce a model of inductive inference, or learning, that extends the conventional Bayesian approach by explicitly considering the computational cost of formulating predictions to be tested. We view the learner as a scientist who must divide her time between doing experiments and deducing predictions from promising theories, and we wish to know how she can do so most effectively. We explore several approaches based on the cost of making a prediction relative to the cost of performing an experiment. The resulting strategies share many qualitative characteristics with ``real'' science. This model is significant for the following reasons: \begin{itemize} \item It allows us to study how a scientist might go about acquiring knowledge in a world where (as in real life) both performing experiments and making predictions from theories require time and effort. \item It lays the foundation for a rigorous machine-implementable notion of ``subjective probability.'' Good (1959, Science \textbf{129}, 443--447) argues persuasively that subjective probability is at the heart of probability theory. Previous treatments of subjective probability do not handle the complication that the learner's subjective probabilities may change as the result of pure thinking; our model captures this and other effects in a realistic manner. In addition, we begin to answer the question of how to trade off \emph{thinking} versus \emph{doing}---a question that is fundamental for computers that must exist in the world and learn from their experience. \end{itemize} }, }