Errors and Correction in Cumulative Knowledge

Madhu Sudan 
Harvard University

Societal accumulation of knowledge is a complex, and arguably error-prone, process. The correctness of new units of knowledge depends not only on the correctness of the new reasoning, but also on the correctness of old units that the new one builds on. Left unchecked errors could completely ruin the validity of most of this knowledge – so there must some error-correcting going on. What are the error-corrections processes and how effective are they? In this talk, we present a simple probabilistic process that aims to model such accumulation of knowledge and study the persistence (or lack thereof) of errors.

Our model for the generation of new units of knowledge is based on the preferential attachment growth model, to which we additionally allow for injection of errors. Furthermore, the process includes checks aimed at catching these errors. We investigate when effects of errors persist forever in the system (with positive probability) and when they get rooted out completely by the checking process.

The two basic parameters associated with the checking process are the {\em probability} of conducting a check and the {\em depth} of the check. We show that errors are rooted out if checks are sufficiently frequent and sufficiently deep. In contrast, shallow or infrequent checks are insufficient to root out errors.

Based on the paper: “Is This Correct? Let’s Check!” with Omri Ben-Eliezer, Dan Mikulincer and Elchanan Mossel (all at MIT).