Learning, Complexity, & Testing

机器学习的各个方面已经进行了很长一段时间的实证研究。 而且，最近，理论研究变得流行起来。 这项研究有助于理解计算机如何通过隔离增量学习算法的特征来学习，这些算法在理论上可以提高它们的学习潜力。 除了追求已经建立了坚实基础的研究之外，还开始了对机器学习中其他主题的研究;例如，研究记忆观察数据和其他信息的能力有限的学习算法。 归纳推理在某种意义上是程序测试的对偶。对于推理问题，必须从有限的例子集推广到整个函数或概念。 测试问题需要制定一个有限的测试集，区分一个给定的功能从所有其他在一个给定的类。 程序测试问题比程序等价问题更难，因此它是高度不可解的。因此，从业者注定会采用临时技术。然而，讨论测试策略是可能的，它给出了我们对被测试程序的可靠性有多大信心的指示。 另一方面，研究了某些问题的复杂性。 递归图论中的一些早期工作现在已经被应用于NP难问题的复杂性。 这一工作被扩展到P. 研究了布尔函数的复杂性。

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.