Although consistent learning is sufficient for PAC-learning, it has not been found what strategy makes learning more efficient, especially on the sample complexity, i.e., the number of examples required. For the first step towards this problem, classes that have consistent learning algorithms with one-sided error are considered. A combinatorial quantity called maximal particle sets is introduced, and an upper bound of the sample complexity of consistent learning with one-sided error is obtained in terms of maximal particle sets. For the class of n-dimensional axis-parallel rectangles, one of those classes that are consistently learnable with one-sided error, the cardinality of the maximal particle set is estimated and O(d/ε1/ε log 1/δ) upper bound of the learning algorithm for the class is obtained. This bound improves the bounds due to Blumer et al. and meets the lower bound within a constant factor.

Various authors have proposed probabilistic extensions of Valiant's PAC (Probably Approximately Correct) learning model in which the target to be learned is a (conditional) probability distribution. In this paper, we improve upon the best known upper bounds on the sample complexity of the parameter estimation part of the learning problem for distributions and stochastic rules over a finite domain with respect to the Kullback-Leibler divergence (KL-devergence). In particular, we improve the upper bound of order O(1/ε²) due to Abe, Takeuchi, and Warmuth to a bound of order O(1/ε). In obtaining our results, we made use of the properties of a specific estimator (slightly modified maximum likelihood estimator) with respect to the KL-divergence, while previously known upper bounds were obtained using the uniform convergence technique.

This paper considers properties of language classes with finite elasticity in the viewpoint of set theoretic operations. Finite elasticity was introduced by Wright as a sufficient condition for language classes to be inferable from positive data, and as a property preserved by (not usual) union operation to generate a class of unions of languages. We show that the family of language classes with finite elasticity is closed under not only union but also various operations for language classes such as intersection, concatenation and so on, except complement operation. As a framework defining languages, we introduce restricted elementary formal systems (EFS's for short), called max length-bounded by which any context-sensitive language is definable. We define various operations for EFS's corresponding to usual language operations and also for EFS classes, and investigate closure properties of the family G_e of max length-bounded EFS classes that define classes of languages with finite elasticity. Furthermore, we present theorems characterizing a max length-bounded EFS class in the family G_e, and that for the language class to be inferable from positive data, provided the class is closed under subset operation. From the former, it follows that for any n, a language class definable by max length-bounded EFS's with at most n axioms has finite elasticity. This means that G_e is sufficiently large.

In this paper we investigate the learnability of relations in Inductive Logic Programming, by using equality theories as background knowledge. We assume that a hypothesis and an observation are respectively a definite program and a set of ground literals. The targets of our learning algorithm are relations. By using equality theories as background knowledge we introduce tree structure into definite programs. The structure enable us to narrow the search space of hypothesis. We give pairs of a hypothesis language and a knowledge language in order to discuss the learnability of relations from the view point of inductive inference and PAC learning.

This paper concerns the issue of learning strategies for problem solvers from trace data. Many works on Explanation Based Learning have proposed methods for speeding up a given problem solver (or a Prolog program) by optimizing it on some subspace of problem instances with high probability of occurrences. However, in the current paper, we discuss the issue of identifying a target strategy exactly from trace data. Learning criterion used in this paper is the identification in the limit proposed by Gold. Further, we use the tree pattern language to represent preconditions of operators, and propose a class of strategies, called decision list strategies. One of the interesting features of our learning algorithm is the coupled use of state and operator sequence information of traces. Theoretically, we show that the proposed algorithm identifies some subclass of decision list strategies in the limit with the conjectures updated in polynomial time. Further, an experimental result on N-puzzle domain is presented.

Computational approaches to concept formation often share a top-down, incremental, hill-climbing classification, and differ from each other in the concept representation and quality criteria. Each of them captures part of the rich variety of conceptual knowledge and many are well suited only when the object-attribute distribution is not sparse. Formal concept analysis is a set-theoretic model that mathematically formulates the human understanding of concepts, and investigates the algebraic structure, Galois lattice, of possible concepts in a given domain. Adopting the idea of representing concepts by mutual closed sets of objects and attributes as well as the Galois lattice structure for concepts from formal concept analysis, we propose an approach to concept formation and develop OSHAM, a method that forms concept hierarchies with high utility score, clear semantics and effective even with sparse object-attribute distributions. In this paper we describe OSHAM, and in an attempt to show its performance we present experimental studies on a number of data sets from the machine learning literature.

This paper discusses some problems in Molecular Biology for which learning paradigms are strongly desired. We also present a framework of knowledge discovery by PAC-learning paradigm together with its theory and practice developed in our work for discovery from amino acid sequences.

Most traditional directory systems use tree structure. This structure has revealed some problems, especially in a large system domain like distributed networking environment. These problems are severe constraints on object naming, no support to automatic sharing, and single name space. We proposed a new directory structure called MSD (Multi-Space Directory) to solve these problems. MSD exhibits several outstanding characteristics over tree directory, such as supporting both hierarchical and orthogonal classifications, supporting both vertical and horizontal automatic sharings, providing multiple working environment, and providing a better mechanism for protection and consistency. This paper first analyzed the problems of tree directory and new requirements for directory systems, then describes the structure of MSD in detail and shows its merits over tree directory.

Program transformation is a kind of optimization techniques for logic programs, which aims at transforming equally a program into an other form by exploiting some properties or information of the program, so as to make the program cheaper to evaluate. In this paper, a new kind of property of logic programs, called reducibility, is exploited in program transformation. A recursive predicate is reducible if the values of some variables in the recursive predicate are independent to the remainder part and can be detached from the predicate after finite times of expansions. After being proved that the semantic notion of reducibility can be replaced by the syntactic notion of disconnectivity of a R-graph, which is a kind of graph model to represent the behavior of formula expansions, an efficient testing and factoring algorithm is proposed. The paper also extends some existed results on compiled formulas of linear sirups, and compares with some related work.

Motion estimation is a major part of the video coding, which traces the motion of moving objects in video sequences. Among various motion estimation algorithms, the Hierarchical Block-Matching Algorithm (HBMA) that is a multilayered motion estimation algorithm is attractive in motion-compensated interpolation when accurate motion estimation is required. However, parallel processing of HBMA is necessary since the high computational complexity of HBMA prevents it from operating in real-time. Further, the repeated updates of vectors naturally lead to pipelined processing. In this paper, we present a pipelined architecture for HBMA. We investigate the data dependency of HBMA and the requirements of the pipeline to operate synchronously. Each pipeline stage of the proposed architecture consists of a systolic array for the block-matching algorithm, a bilinear interpolator, and a latch mechanism. The latch mechanism mainly resolves the data dependency and arranges the data flow in a synchronous way. The proposed architecture achieves nearly linear speedup without additional hardware cost over a non-pipelined one. It requires the clock of 2.70 ns to process a large size of frame (e.q. HDTV) in real-time, which is about to be available under the current VLSI technology.

In this paper we describe a technique for deriving non-systematic t-Symmetric Error Correcting/All Unidirectional Error Detecting (t-SyEC/AUED) codes. The method developed here is suitable for binary as well as non-binary codes. We have used spectral techniques to derive these codes. These codes are shown to be of asymptotically optimal order for constant weight semidistance codes.