Learning, Complexity, & Testing

点击翻译按钮获取中文摘要

Various aspects of machine learning have been under empirical investigation for quite some time. And, more recently, theoretical studies have become popular. This research contributes towards the goal of understanding how a computer can be programmed to learn by isolating features of incremental learning algorithms that theoretically enhance their learning potential. In addition to pursuing lines of research that have already been established with a firm base, investigations of other topics in machine learning are initiated; for example, investigating learning algorithms with a limited ability to remember observed data and other information. Inductive inference is in some sense the dual of program testing. For the inference problem, one must generalize from a finite set of examples to an entire function or concept. The testing problem requires the formulation of a finite test set that distinguishes a given function from all the others in a given class. The program testing problem is more difficult than the program equivalence problem, hence it is highly unsolvable. Consequently, practitioners are doomed to ad hoc techniques. However, it is possible to discuss testing strategies that give an indication of how confident we are that the program being tested is reliable. In another vein, the complexity of certain problems is studied. Some of the earlier work in recursive graph theory has now been applied to the complexity of NP-hard problems. This work is extended to problems in P. The complexity of Boolean functions is also investigated.