Autodidactic learning and reasoning

The formal study of intelligence has largely focused on learning and reasoning, the processes by which knowledge is, respectively, acquired and applied. This dissertation investigates how the two processes may be undertaken together in an autodidactic, or self-taught, manner. The thesis put forward is that the development of such a unified framework rests on the principled understanding of a third process, that of sensing. Sensing is formalized in this dissertation as the process by which some underlying reality completely specifying a state of affairs is mapped to an appearance explicitly offering only partial information. Learning is employed to discover the structure of the reality, and reasoning is employed to recover as much of the missing information as possible. Emphasis is placed on the tractability of learning and reasoning, and on the existence of formal guarantees on the accuracy of the information recovered, making only minimal assumptions on the nature of information loss during the sensing phase. An investigation of the conditions under which the task of information recovery is feasible is undertaken. It is shown that it suffices, and is optimal in some precisely defined sense, to induce rules that are simply consistent with the observed appearances. For environments with structure expressible via monotone rules, learning consistently from partial appearances reduces to learning from complete appearances, allowing for known positive results to be lifted to the case of autodidactic learning. On the negative side, there exist environments where partial appearances compromise learnability. The contribution of chaining rules--induced or externally provided ones--for information recovery is then examined, and is shown to be that of increasing the combined predictive soundness and completeness. This result provides apparently the first formal separation between multi-layered and single-layered reasoning in this context. It is further established that the learning and reasoning processes cannot be completely decoupled in the autodidactic setting. Instead, an approach that interleaves the two processes is introduced, which proceeds by learning the rules to be employed for multi-layered reasoning in an iterative manner, one layer at a time. This approach of employing interim reasoning, or reasoning while learning, is shown to suffice and to be a universal approach for the induction of knowledge that is to be reasoned with. The design and implementation of a system for automatically acquiring and manipulating knowledge is finally considered. Semantic information extracted from a natural language text corpus is interpreted, following the theory, as partial information about the real world. It is argued that rules induced from such information capture some commonsense knowledge. This knowledge is subsequently employed to recover information that is not explicitly stated in the corpus. Experiments were performed on a massive scale, and serious computational challenges had to be addressed to ensure scalability. The experimental setting was designed with the novel goal of detecting whether commonsense knowledge has been extracted. The experimental results presented suggest that this goal has been achieved to a measurable degree.