Learning from the environment based on percepts and actions

Abstract

This thesis is a study of from the environment. As machine learning moves from toy environments towards the real world, the problem of learning autonomously from environments whose structure is not completely defined a priori becomes ever more critical. Three of the major challenges are: (1) how to integrate various high level AI techniques such as exploration, problem solving, learning, and experimentation with low level perceptions and actions so that learning can be accomplished through interactions with the environment; (2) how to acquire knowledge of the environment and to learn from mistakes autonomously, permitting incorrect information to be identified and corrected; (3) how to create features in such a way that knowledge acquisition is not limited by the initial concept description language provided by the designers of a system. The thesis defines learning from the environment as inferring the laws of the environment that enable the learner to solve problems. The inputs to the learning are goals to be achieved, percepts and actions sensed and effected by the learner, and constructors for organizing the percepts and the actions. The output is a set of prediction rules that correlate actions and percepts for achieving the given goals. The thesis develops a framework called scLIVE that unifies problem solving with rule induction. It creates rules by noticing the changes in the environment when actions are taken during exploration. It uses a learning method called complementary discrimination to learn both disjunctive and conjunctive rules incrementally and unbiasedly from feedback and experiments. Furthermore, it constructs new terms to describe newly discovered hidden features in the environment that are beyond the scope of the initial perception description language. Theoretically, if the environment is a $n$ state finite deterministic automaton and each of the learner's $m$ actions has a known inverse, then the learning method can learn with accuracy 1 $-$ $\epsilon$ and confidence 1 $-$ $\xi$ the correct model of the environment within $O(n\sp2m{1\over\epsilon}$log${1\over\xi}$) steps. Empirically, in comparison with existing learning systems, this approach has shown the advantages of creating problem spaces by interacting with environments, eliminating the bias posed by the initial concept hierarchy, and constructing vocabulary through actions. The generality of this approach is illustrated by experiments conducted in various domains, including child learning, puzzle solving, robot simulation and scientific discovery.