Explanation-Based Learning: An Alternative View

In the last issue of this journal Mitchell, Keller, and Kedar-Cabelli presented a unifying framework for the explanation-based approach to machine learning. While it works well for a number of systems, the framework does not adequately capture certain aspects of the systems under development by the explanation-based learning group at Illinois. The primary inadequacies arise in the treatment of concept operationality, organization of knowledge into schemata, and learning from observation. This paper outlines six specific problems with the previously proposed framework and presents an alternative generalization method to perform explanation-based learning of new concepts.     

Machine Learning for User Modeling

At first blush, user modeling appears to be a prime candidate for straightforward application of standard machine learning techniques. Observations of the user's behavior can provide training examples that a machine learning system can use to form a model designed to predict future actions. However, user modeling poses a number of challenges for machine learning that have hindered its application in user modeling, including: the need for large data sets; the need for labeled data; concept drift; and computational complexity. This paper examines each of these issues and reviews approaches to resolving them.     

Space-bounded simulation of multitape turing machines

A new proof of a theorem of Hopcroft, Paul, and Valiant is presented: Every deterministic multitape Turing machine of time complexityT(n) can be simulated by a deterministic Turing machine of space complexityT(n)/logT(n). The proof includes an overlap argument.Supported by National Science Foundation Grant No. MCS-78-04343.Supported by National Science Foundation Grant No. MCS-77-19754 and the Fannie and John Hertz Foundation.     

Learning via finitely many queries

This work introduces a new query inference model that can access data and communicate with the teacher by asking finitely many Boolean queries in a language L. In this model the parameters of interest are the number of queries used and the expressive power of L. We study how the learning power varies with these parameters. Results suggest that this model may help studying query inference in a resource bounded environment.AMS subject classification 68Q05, 68Q32, 68T05, 03D10, 03D80     

机器学习图像分类程序的蜕变测试框架

机器学习在计算机视觉、语音识别和自然语言处理等实际应用中已经取得了显著的成功。图像分类作为计算机视觉的一个主要分支。不久的将来,许多的图像分类程序会以机器学习的方式呈现。然而,由于机器学习图像分类程序的测试面临着测试预言难题,这使得在测试的过程中将需要大量的人力及物力。为了缓解测试预言难题,使用了蜕变测试技术。为了规范测试流程、提高测试效率,提出了一种适用于机器学习图像分类程序的蜕变测试框架。并且通过测试基于SVM和VGGNet图像分类程序,验证了该测试框架的合理性和有效性。     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

Reversibility in space-bounded computation

In this paper, we investigate how computing power of a space-bounded Turing machine (TM) is affected by reversibility and determinism. We show an irreversible deterministic TM (IDTM), and a reversible non-deterministic TM (RNTM) can be simulated by a reversible and deterministic TM (RDTM) that uses exactly the same numbers of storage tape symbols and storage tape squares. Thus, an RDTM has relatively high capability in spite of the constraints of reversibility and determinism. Here, we also discuss a space-bounded symmetric TM.     

Learning from a Population of Hypotheses

We introduce a new formal model in which a learning algorithm must combine a collection of potentially poor but statistically independent hypothesis functions in order to approximate an unknown target function arbitrarily well. Our motivation includes the question of how to make optimal use of multiple independent runs of a mediocre learning algorithm, as well as settings in which the many hypotheses are obtained by a distributed population of identical learning agents.     

Multi-Instance Learning from Supervised View

In multi-instance learning, the training set comprises labeled bags that are composed of unlabeled instances, and the task is to predict the labels of unseen bags. This paper studies multi-instance learning from the view of supervised learning. First, by analyzing some representative learning algorithms, this paper shows that multi-instance learners can be derived from supervised learners by shifting their focuses from the discrimination on the instances to the discrimination on the bags. Second, considering that ensemble learning paradigms can effectively enhance supervised learners, this paper proposes to build multi-instance ensembles to solve multi-instance problems. Experiments on a real-world benchmark test show that ensemble learning paradigms can significantly enhance multi-instance learners.     

Learning Changing Concepts by Exploiting the Structure of Change

This paper examines learning problems in which the target function is allowed to change. The learner sees a sequence of random examples, labelled according to a sequence of functions, and must provide an accurate estimate of the target function sequence. We consider a variety of restrictions on how the target function is allowed to change, including infrequent but arbitrary changes, sequences that correspond to slow walks on a graph whose nodes are functions, and changes that are small on average, as measured by the probability of disagreements between consecutive functions. We first study estimation, in which the learner sees a batch of examples and is then required to give an accurate estimate of the function sequence. Our results provide bounds on the sample complexity and allowable drift rate for these problems. We also study prediction, in which the learner must produce online a hypothesis after each labelled example and the average misclassification probability over this hypothesis sequence should be small. Using a deterministic analysis in a general metric space setting, we provide a technique for constructing a successful prediction algorithm, given a successful estimation algorithm. This leads to sample complexity and drift rate bounds for the prediction of changing concepts.     

一种概念学习分类方法的探讨

为了解决数据分类效率问题,引入了并行概念学习的方法,针对二叉树分类法的“累积误差”问题,提出了一种并行概念的描述语言.在此基础上,设计了基于二叉树的多类SVM并行分类系统.通过对系统性能的分析表明,在样本空间庞大、样本涉及属性广的数据分类时,该系统具有很好的分类效果.     

A note on alternating one-pebble Turing machines with sublogarithmic space

Inoue et al. [A. Inoue, A. Ito, K. Inoue, T. Okazaki, Some properties of one-pebble Turing machines with sublogarithmic space, Theoret. Comput. Sci. 341 (2005) 138-149] conjectured that the language {ww|w∈⁺{a,b}} is not accepted by any alternating one-pebble Turing machine with sublogarithmic space. In this paper we disprove the conjecture by showing that there exists an alternating one-pebble Turing machine accepting the language in loglogn space.     

机器学习与网络信息处理

机器学习在网络信息处理中占有重要地位。GHunt是一个采用多项机器学习技术的网络信息智能获取与处理系统。首先,这一系统支持分布式的网络信息并行搜索与内容过滤;其次,采用机器学习技术,包括文本分类、聚类,文本概念抽取,从概念层次理解文本信息;再次,基于概念语义空间有效地统一文本信息管理;最后提供高效的基于概念语义的文本信息检索,以及个性化的专题组织与信息推送服务。文中着重阐述了系统中所用到的机器学习技术。     

逼近于BPP和PP的概率复杂性语言类的多项式有界线路复杂性研究

本文通过图灵机多项式"?"输出有界和多项式错误输出有界概念的引入,研究了逼近于BPP和PP的一些概率复杂性语言类的多项式有界线路复杂性。     

The Turing way to parameterized complexity

We propose a general proof technique based on the Turing machine halting problem that allows us to establish membership results for the classes W[1], W[2], and W[P]. Using this technique, we prove that Perfect Code belongs to W[1], Steiner Tree belongs to W[2], and α-Balanced Separator, Maximal Irredundant Set, and Bounded DFA Intersection belong to W[P].     

Learning Translation Templates from Bilingual Translation Examples

A mechanism for learning lexical correspondences between two languages from sets of translated sentence pairs is presented. These lexical level correspondences are learned using analogical reasoning between two translation examples. Given two translation examples, the similar parts of the sentences in the source language must correspond to the similar parts of the sentences in the target language. Similarly, the different parts must correspond to the respective parts in the translated sentences. The correspondences between similarities and between differences are learned in the form of translation templates. A translation template is a generalized translation exemplar pair where some components are generalized by replacing them with variables in both sentences and establishing bindings between these variables. The learned translation templates are obtained by replacing differences or similarities by variables. This approach has been implemented and tested on a set of sample training datasets and produced promising results for further investigation.     

Instance-Based Learning Algorithms

Storing and using specific instances improves the performance of several supervised learning algorithms. These include algorithms that learn decision trees, classification rules, and distributed networks. However, no investigation has analyzed algorithms that use only specific instances to solve incremental learning tasks. In this paper, we describe a framework and methodology, called instance-based learning, that generates classification predictions using only specific instances. Instance-based learning algorithms do not maintain a set of abstractions derived from specific instances. This approach extends the nearest neighbor algorithm, which has large storage requirements. We describe how storage requirements can be significantly reduced with, at most, minor sacrifices in learning rate and classification accuracy. While the storage-reducing algorithm performs well on several real-world databases, its performance degrades rapidly with the level of attribute noise in training instances. Therefore, we extended it with a significance test to distinguish noisy instances. This extended algorithm's performance degrades gracefully with increasing noise levels and compares favorably with a noise-tolerant decision tree algorithm.     

Hierarchies of recursive computations†

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.     

面向不同结构化程度数据源的本体学习方法研究

本体研究已成为计算机领域的一个研究热点,而本体学习又是本体研究的热点问题之一。文章根据数据源的结构化程度,将数据源分为结构化、非结构化和半结构化数据源,分别研究了如何从这三种不同程度结构化的数据源中学习本体,探讨了后续研究工作的本体学习方法以及研究目标,并论述了目前研究存在的不足及对未来的展望。     

A Necessary Condition for Learning from Positive Examples

We present a simple combinatorial criterion for determining concept classes that cannot be learned in the sense of Valiant from a polynomial number of positive-only examples. The criterion is applied to several types of Boolean formulae in conjunctive and disjunctive normal form, to the majority function, to graphs with large connected components, and to a neural network with a single threshold unit. All are shown to be nonlearnable from positive-only examples.