Search

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern π, are there finite sets T + and T − of strings such that the only pattern language containing all strings in T + and none of the strings in T − is the language generated by π? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension.

Re learning in the limit from positive data, a major concern is which classes of languages are learnable with respect to a given learning criterion. We are particularly interested herein in the reasons for a class of languages to be unlearnable. We consider two types of reasons. One type is called topological where it does not help if the learners are allowed to be uncomputable (an example of Gold's is that no class containing an infinite language and all its finite sub-languages is learnable - even by an uncomputable learner). Another reason is called computational (where the learners are required to be algorithmic). In particular, two learning criteria might allow for learning different classes of languages from one another - but with dependence on whether the unlearnability is of type topological or computational.In this paper we formalize the idea of two learning criteria separating topologically in learning power. This allows us to study more closely why two learning criteria separate in learning power. For a variety of learning criteria, concerning vacillatory, monotone, (several kinds of) iterative and feedback learning, we show that certain learning criteria separate topologically, and certain others, which are known to separate, are shown not to separate topologically. Showing that learning criteria do not separate topologically implies that any known separation must necessarily exploit algorithmicity of the learner.

This paper establishes an upper bound on the size of a concept class with given recursive teaching dimension (RTD, a teaching complexity parameter). The upper bound coincides with Sauer's well-known bound on classes with a fixed VC-dimension. Our result thus supports the recently emerging conjecture that the combinatorics of VC-dimension and those of teaching complexity are intrinsically interlinked. We further introduce and study RTD-maximum classes (whose size meets the upper bound) and RTD-maximal classes (whose RTD increases if a concept is added to them), showing similarities but also differences to the corresponding notions for VC-dimension. Another contribution is a set of new results on maximal classes of a given VC-dimension. Methodologically, our contribution is the successful application of algebraic techniques, which we use to obtain a purely algebraic characterization of teaching sets (sample sets that uniquely identify a concept in a given concept class) and to prove our analog of Sauer's bound for RTD. Such techniques have been used before to prove results relevant to computational learning theory, e.g., by Smolensky [13] , but are not standard in the field.

We analyze iterative learning in the limit from positive data with the additional information provided by a counter. The simplest type of counter provides the current iteration number (counting up from 0 to infinity), which is known to improve learning power over plain iterative learning. We introduce five other (weaker) counter types, for example only providing some unbounded and non-decreasing sequence of numbers. Analyzing these types allows one to understand which properties of a counter learning can benefit from. For the iterative setting, we completely characterize the relative power of the learning criteria corresponding to the counter types. In particular, for our types, the only properties improving learning power are unboundedness and strict monotonicity. Furthermore, we show that each of our types of counter improves learning power over weaker ones in some settings; to this end, we analyze transductive and non-U-shaped learning. Finally we show that, for iterative learning criteria with one of our types of counter, separations of learning criteria are necessarily witnessed by classes containing only infinite languages.

Given a prior probability distribution over a set of possible oracle functions, we define a number of queries to be useless for determining some property of the function if the probability that the function has the property is unchanged after the oracle responds to the queries. A familiar example is the parity of a uniformly random Boolean-valued function over $\{1,2,...,N\}$, for which $N-1$ classical queries are useless. We prove that if $2k$ classical queries are useless for some oracle problem, then $k$ quantum queries are also useless. For such problems, which include classical threshold secret sharing schemes, our result also gives a new way to obtain a lower bound on the quantum query complexity, even in cases where neither the function nor the property to be determined is Boolean.

We study learning in a modified EXACT model, where the oracles are corrupt and only few of the presented attributes are relevant. Both modifications were already studied in the literature [Dana Angluin, Mārtiņš Krikis, Learning with malicious membership queries and exceptions (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 56–57 [3]; Dana Angluin, Mārtiņš Krikis, Robert H. Sloan, György Turán, Malicious omissions and errors in answers to membership queries, Machine Learning 28 (1997) 211–255; Laurence Bisht, Nader H. Bshouty, Lawrance Khoury, Learning with errors in answers to membership queries (extracted abstract), in: FOCS ’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS’04, IEEE Computer Society, 2004, pp. 611–620; Nader H. Bshouty, Lisa Hellerstein, Attribute-efficient learning in query and mistake-bound models, J. Comput. System Sci. 56 (3) (1998) 310–319 [12]; Nick Littlestone, Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm, Machine Learning 2 (4) (1988) 285–318; Robert H. Sloan, Gyorgy Turan, Learning with queries but incomplete information (extended abstract), in: COLT ’94: Proceedings of the Seventh Annual Conference on Computational Learning Theory, ACM Press, 1994, pp. 237–245 [5]], and efficient solutions were found to most of their variants. Nonetheless, their reasonable combination is yet to be studied, and integrating the existing solutions either fails or works with a complexity that can be significantly improved. In this paper we prove the equivalence of EXACT learning attribute-efficiently with and without corrupt oracles. For each of the possible scenarios we describe a generic scheme that enables learning in these cases using modifications of the standard learning algorithms. We also generalize and improve previous non-attribute-efficient algorithms for learning with corrupt oracles.

We consider a variant of Gold’s learning paradigm where a learner receives as input n different languages (in the form of one text where all input languages are interleaved). Our goal is to explore the situation when a more “coarse” classification of input languages is possible, whereas more refined classification is not. More specifically, we answer the following question: under which conditions, a learner, being fed n different languages, can produce m grammars covering all input languages, but cannot produce k grammars covering input languages for any k>m. We also consider a variant of this task, where each of the output grammars may not cover more than r input languages. Our main results indicate that the major factor affecting classification capabilities is the difference n−m between the number n of input languages and the number m of output grammars. We also explore the relationship between classification capabilities for smaller and larger groups of input languages. For the variant of our model with the upper bound on the number of languages allowed to be represented by one output grammar, for classes consisting of disjoint languages, we found complete picture of relationship between classification capabilities for different parameters n (the number of input languages), m (number of output grammars), and r (bound on the number of languages represented by each output grammar). This picture includes a combinatorial characterization of classification capabilities for the parameters n,m,r of certain types.

Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts invariant under an operation satisfying a certain algebraic condition. We give a learning algorithm in the exact model with equivalence queries for such classes. This algorithm utilizes a novel encoding scheme, which we call a signature. The first author was supported by an NSERC Discovery Grant. The second and third authors were supported by grant TIC 2002-04470-C03 and the EU PASCAL Network of Excellence IST-2002-506778. The third author was also supported by the MEC under the program “Ramon y Cajal”, grant TIC 2002-04019-C03, and MODNET Marie Curie Research Training Network MRTN-CT-2004-512234.

We give an overview of the fastest known algorithms for learning various expressive classes of Boolean functions in the Probably Approximately Correct (PAC) learning model. In addition to surveying previously known results, we use existing techniques to give the first known subexponential-time algorithms for PAC learning two natural and expressive classes of Boolean functions: sparse polynomial threshold functions over the Boolean cube {0,1}n and sparse GF2 polynomials over {0,1}n.

A non-zero-approaching adaptive learning rate is proposed to guarantee the global convergence of Oja's principal component analysis (PCA) learning algorithm. Most of the existing adaptive learning rates for Oja's PCA learning algorithm are required to approach zero as the learning step increases. However, this is not practical in many applications due to the computational round-off limitations and tracking requirements. The proposed adaptive learning rate overcomes this shortcoming. The learning rate converges to a positive constant, thus it increases the evolution rate as the learning step increases. This is different from learning rates which approach zero which slow the convergence considerably and increasingly with time. Rigorous mathematical proofs for global convergence of Oja's algorithm with the proposed learning rate are given in detail via studying the convergence of an equivalent deterministic discrete time (DDT) system. Extensive simulations are carried out to illustrate and verify the theory derived. Simulation results show that this adaptive learning rate is more suitable for Oja's PCA algorithm to be used in an online learning situation.

Within the scope of inductive inference a recursion theoretic approach is used to model learning behaviour. The fundamental model considered is Gold's identification of recursive functions in the limit. Modifying the corresponding definition has proposed several inference classes, which have been compared regarding the capacities of the relevant learners. The present paper is concerned with a meta-version of this learning model. Given a description of a class of target functions, a uniform learner is supposed to develop a specific successful method for learning the represented class. The same modifications as in the elementary model are considered in the context of uniform learning, especially respecting identification capacities. It turns out that the former separations of inference classes are reflected on the meta-level, in particular finite classes of recursive functions—which constitute the most simple learning problems in the elementary model—are evidence of these separations.

An elementary formal system (EFS) is a logic program such as a Prolog program, for instance, that directly manipulates strings. Arikawa and his co-workers proposed elementary formal systems as a unifying framework for formal language learning.In the present paper, we introduce advanced elementary formal systems (AEFSs), i.e., elementary formal systems which allow for the use of a certain kind of negation, which is nonmonotonic, in essence, and which is conceptually close to negation as failure.We study the expressiveness of this approach by comparing certain AEFS definable language classes to the levels in the Chomsky hierarchy and to the language classes that are definable by EFSs that meet the same syntactical constraints.Moreover, we investigate the learnability of the corresponding AEFS definable language classes in two major learning paradigms, namely in Gold's model of learning in the limit and Valiant's model of probably approximately correct learning. In particular, we show which learnability results achieved for EFSs extend to AEFSs and which do not.

A long-standing goal in the realm of Machine Learning is to minimize sample-complexity, i.e. to reduce as much as possible the number of examples used in the course of learning. The Active Learning paradigm is one such method aimed at achieving this goal by transforming the learner from a passive participant in the information gathering process to an active one. Vaguely speaking, the learner tries to minimize the number of labeled instances used in the course of learning, relaying also on unlabelled instances in order to acquire the needed information whenever possible. The reasoning comes from many real-life problems where the teacher's activity is an expensive resource (e.g. text categorization, part of speech tagging). The Query By Committee (QBC) (Seung et al., Query by committee, Proceedings of the Fifth Workshop on Computational Learning theory, Morgan Kaufman, San Mateo, CA, 1992, pp. 287–294) is an Active Learning algorithm acting in the Bayesian model of concept learning, (Haussler et al., Mach. Learning 14 (1994) 83) i.e. it assumes that the concept to be learned is chosen according to some fixed and known distribution. Trying to apply the QBC algorithm for learning the class of linear separators, one faces the problem of implementing the mechanism of sampling hypotheses (the Gibbs oracle). The major problem is computational-complexity, since the straightforward Monte Carlo method takes exponential time. In this paper we address the problems involved in the implementation of such a mechanism. We show how to convert them to questions about sampling from convex bodies or approximating the volume of such bodies. Similar problems have recently been solved in the field of computational geometry based on random walks. These techniques enable us to device efficient implementations of the QBC algorithm. We also give few improvements and corrections to the QBC algorithm, the most important one is dropping the Bayes assumption when the concept classes possess a sort of symmetry property (which holds for linear separators). We draw attention to a useful geometric lemma which bounds the maximal radius of a ball contained in a convex body. Finally, this paper exhibits a connection between random walks and certain Machine Learning notions such as ε-net and support vector machines.

In this paper we introduce a general method of establishing tight linear inequalities between different types of predictive complexity. Predictive complexity is a generalisation of Kolmogorov complexity and it bounds the ability of an algorithm to predict elements of a sequence. Our method relies upon probabilistic considerations and allows us to describe explicitly the sets of coefficients which correspond to true inequalities. We apply this method to two particular types of predictive complexity, namely, logarithmic complexity, which coincides with a variant of Kolmogorov complexity, and square-loss complexity, which is interesting for applications.

Some basic issues in the statistical mechanics of learning from examples are reviewed. The approach of statistical physics is contrasted with the analysis of learning within the framework of mathematical statistics and the question of the algorithmic complexity of explicit learning prescriptions is addressed. Even in very simple learning scenarios, the typical properties of which can be analyzed in great quantitative detail by methods from statistical mechanics, the determination of a suitable hypothesis approximating the target rule may be an NP-complete problem. Some special learning setups are suggested as model systems for the comparison between the approaches of statistical mechanics and computer science to the theory of computationally hard problems.

A FIN-learning machine M receives successive values of the function f it is learning and at some moment outputs a conjecture which should be a correct index of f. FIN learning has two extensions: (1) If M flips fair coins and learns a function with certain probability p, we have FIN〈p〉-learning. (2) When n machines simultaneously try to learn the same function f and at least k of these machines output correct indices of f, we have learning by a [k,n]FIN team. Sometimes a team or a probabilistic learner can simulate another one, if their probabilities p1,p2 (or team success ratios k1/n1,k2/n2) are close enough (Daley et al., in: Valiant, Waranth (Eds.), Proc. 5th Annual Workshop on Computational Learning Theory, ACM Press, New York, 1992, pp. 203–217; Daley and Kalyanasundaram, Available from http://www.cs.pitt.edu/ ̃daley/fin/fin.html, 1996). On the other hand, there are cut-points r which make simulation of FIN〈p2〉 by FIN〈p1〉 impossible whenever p2⩽r

Process control problems can be modeled as closed recursive games. Learning strategies for such games is equivalent to the concept of learning infinite recursive branches for recursive trees. We use this branch learning model to measure the difficulty of learning and synthesizing process controllers. We also measure the difference between several process learning criteria, and their difference to controller synthesis. As measure we use the information content (i.e., the Turing degree) of the oracle which a machine needs to get the desired power. The investigated learning criteria are finite, EX -, BC -, weak BC - and on-line learning. Finite, EX - and BC -style learning are well known from inductive inference, while weak BC - and on-line learning came up with the new notion of branch (i.e., process) learning. For all considered criteria – including synthesis – we also solve the questions of their trivial degrees, their omniscient degrees and with some restrictions their inference degrees. While most of the results about finite, EX - and BC -style branch learning can be derived from inductive inference, new techniques had to be developed for on-line learning, weak BC -style learning and synthesis, and for the comparisons of all process learning criteria with the power of controller synthesis.

Testing plays an integral part in many areas of computer science. In relation to computational learning theory, testing can be viewed as an inverse process to learning. Testing algorithms create a set of examples for a given target concept that distinguish it from other concepts, while learning algorithms use a given set of examples to correctly infer an unknown concept. In this paper we develop a model for approximate testing of concepts, which relates to the PAC (probably almost correct) model of learning as well as other learning models. In approximate testing, a concept that passes the given tests is only required to be correct to within a given error tolerance rather than being exactly correct. We define what it means for a concept class to be approximately testable , and we investigate general properties of a concept class that make it testable or untestable. We define a new measure that is similar to the Vapnik-Chervonenkis dimension, called the testing dimension of a concept class, and show how it yields untestability results for certain concept classes. We also compare our testing model to several different learning models, and we discuss the topics of nonredundant test sets and generic test sets.

In this note, we consider the problem of learning approximately regular languages in the limit from positive data using the class of k-reversible languages. The class of k-reversible languages was introduced by Angluin (1982), and proved to be efficiently identifiable in the limit from positive data only. We show that Angluin's learning algorithm for the class of k-reversible languages can be readily adopted for the approximate identification of regular languages from positive data. Considering the negative result on the exact identifiability by Gold (1967), this approximation approach would be one of the best we could hope for learning the class of regular languages from positive data only.

This paper describes a topological theory of learning which characterizes learning as a homotopy (which is a function of the deformation of a space in time) from an original knowledge base to one augmented by learned knowledge. The knowledge representation, the algorithms and the theory are based on the cognitive theories of Jean Piaget, the psychological theories of Hebb, as well as the ethological theories of Merzenich and Kaas. The choice of topology as a descriptive and predictive theory was inspired by the neurological aspects of synaptic routing under learning, which preserves the original continuity of the routes. Topology was chosen as a basis for a theory of learning as it is the study of space invariants which preserve the structure and continuity of a space under “stretchings and deformations”. Topology also offers a theoretical description of learning which does not revert to second-order logic. It has been shown that learning can be characterized by second-order logic, but any algorithm based on it is NP-complete.

A model for a subject S learning its environment E could be described thus: S , placed in E , receives data about E , and simultaneously conjectures a sequence of hypotheses. S is said to learn E just in case the sequence of hypotheses conjectured by S stabilizes to a final hypothesis which correctly represents E . Computational learning theory provides a framework for studying problems of this nature when the subject is a machine. A natural abstraction for the notion of hypothesis is a computer program. The present paper, in the above framework of learning, presents arguments for the final hypothesis to be succinct , and introduces a plethora of formulations of such succinctness. A revelation of this study is that some of the “natural” notions of succinctness may be uninteresting because learning capability of machines under these seemingly natural constraints is dependent on the choice of programming system used to interpret hypotheses.

Inductive inference is a recursion-theoretic theory of learning, first developed by E. M. Gold (1967). This paper surveys developments in probabilistic inductive inference. We mainly focus on finite inference of recursive functions, since this simple paradigm has produced the most interesting (and most complex) results., 16 pages, to appear in Theoretical Computer Science

This paper characterizes the polynomial time learnability of TP k , the class of collections of at most k first-order terms. A collection in TPA k defines the union of the languages defined by each first-order terms in the set. Unfortunately, the class TP k not polynomial time learnable in most of learning frameworks under standard assumptions in computational complexity theory. To overcome this computational hardness, we relax the learning problem by allowing a learning algorithm to make membership queries. We present a polynomial time algorithm that exactly learns every concept in TP k using O(kn) equivalence and O(k2n · max{k, n}) membership queries, where n is the size of longest counterexample given so far. In the proof, we use a technique of replacing each restricted subset query by several membership queries under some condition on a set of function symbols. As corollaries, we obtain the polynomial time PAC-learnability and the polynomial time predictability of TP k when membership queries are available. We also show a lower bound Ω(kn) of the number of queries necessary to learn TP k using both types of queries. Further, we show that neither types of queries can be eliminated to achieve efficient learning of TP k . Finally, we apply our results in learning of a class of restricted logic programs, called unit clause programs.

This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i.e., learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished.The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning.The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relations of all models of learning with and without anomalies mentioned above is derived.

In any learnability setting, hypotheses are conjectured from some hypothesis space. Studied herein are the influence on learnability of the presence or absence of certain control structures in the hypothesis space. First presented are control structure characterizations of some rather specific but illustrative learnability results. The presence of these control structures is thereby shown essential to maintain full learning power. Then presented are the main theorems. Each of these non-trivially characterizes the invariance of a learning class over hypothesis space V and the presence of a particular projection control structure, called proj, in V as: V has suitable instances of all denotational control structures. In a sense, then, proj epitomizes the control structures whose presence need not help and whose absence need not hinder learning power.

Working in the framework of PAC-learning theory, we present special statistics for accomplishing in polynomial time proper learning of DNF boolean formulas having a fixed number of monomials. Our statistics turn out to be near sufficient for a large family of distribution laws – that we call butterfly distributions. We develop a theory of most powerful learning for analyzing the performance of learning algorithms, with particular reference to trade-offs between power and computational costs. Focusing attention on sample and time complexity, we prove that our algorithm works as efficiently as the best algorithms existing in the literature – while the latter only take care of subclasses of our family of distributions.

This paper provides a systematic study of incremental learning from noise-free and from noisy data. As usual, we distinguish between learning from positive data and learning from positive and negative data, synonymously called learning from text and learning from informant. Our study relies on the notion of noisy data introduced by Stephan.The basic scenario, named iterative learning, is as follows. In every learning stage, an algorithmic learner takes as input one element of an information sequence for some target concept and its previously made hypothesis and outputs a new hypothesis. The sequence of hypotheses has to converge to a hypothesis describing the target concept correctly.We study the following refinements of this basic scenario. Bounded example-memory inference generalizes iterative inference by allowing an iterative learner to additionally store an a priori bounded number of carefully chosen data elements, while feedback learning generalizes it by allowing the iterative learner to additionally ask whether or not a particular data element did already appear in the input data seen so far.For the case of learning from noise-free data, we show that, when both positive and negative data are available, restrictions on the accessibility of the input data do not limit the learning capabilities if and only if the relevant iterative learners are allowed to query the history of the learning process or to store at least one carefully selected data element. This insight nicely contrasts the fact that, in case only positive data are available, restrictions on the accessibility of the input data seriously affect the learning capabilities of all versions of incremental learners.For the case of learning from noisy data, we present characterizations of all kinds of incremental learning in terms being independent from learning theory. The relevant conditions are purely structural ones. Surprisingly, when learning from noisy text and noisy informant is concerned, even iterative learners are exactly as powerful as unconstrained learning devices.

The decomposition method is currently one of the major methods for solving the convex quadratic optimization problems being associated with Support Vector Machines (SVM-optimization). A key issue in this approach is the policy for working set selection. We would like to find policies that realize (as well as possible) three goals simultaneously: ''(fast) convergence to an optimal solution'', ''efficient procedures for working set selection'', and ''a high degree of generality'' (including typical variants of SVM-optimization as special cases). In this paper, we study a general policy for working set selection that has been proposed in [Nikolas List, Hans Ulrich Simon, A general convergence theorem for the decomposition method, in: Proceedings of the 17th Annual Conference on Computational Learning Theory, 2004, pp. 363-377] and further analyzed in [Nikolas List, Hans Ulrich Simon, General polynomial time decomposition algorithms, in: Proceedings of the 17th Annual Conference on Computational Learning Theory, 2005, pp. 308-322]. It is known that it efficiently approaches feasible solutions with minimum cost for any convex quadratic optimization problem. Here, we investigate its computational complexity when it is used for SVM-optimization. It turns out that, for a variable size of the working set, the general policy poses an NP-hard working set selection problem. But a slight variation of it (sharing the convergence properties with the original policy) can be solved in polynomial time. For working sets of fixed size 2, the situation is even better. In this case, the general policy coincides with the ''rate certifying pair approach'' (introduced by Hush and Scovel). We show that maximum rate certifying pairs can be found in linear time, which leads to a quite efficient decomposition method with a polynomial convergence rate for SVM-optimization.

The present paper investigates identification of indexed families L of recursively enumerable languages from good examples. We distinguish class-preserving learning from good examples (the good examples have to be generated with respect to a hypothesis space having the same range as L) and class-comprising learning from good examples (the good examples have to be selected with respect to a hypothesis space comprising the range of L). A learner is required to learn a target language on every finite superset of the good examples for it. If the learner's first and only conjecture is correct then the underlying learning model is referred to as finite identification from good examples and if the learner makes a finite number of incorrect conjectures before always outputting a correct one, the model is referred to as limit identification from good examples. In the context of class-preserving learning, it is shown that the learning power of finite and limit identification from good text examples coincide. When class comprising learning from good text examples is concerned, limit identification is strictly more powerful than finite learning. Furthermore, if learning from good informant examples is considered, limit identification is superior to finite identification in the class preserving as well as in the class-comprising case. Finally, we relate the models of learning from good examples to one another as well as to the standard learning models in the context of Gold-style language learning.

The present paper motivates the study of mind change complexity for learning minimal models of length-bounded logic programs. It establishes ordinal mind change complexity bounds for learnability of these classes both from positive facts and from positive and negative facts. Building on Angluin's notion of finite thickness and Wright's work on finite elasticity, Shinohara defined the property of bounded finite thickness to give a sufficient condition for learnability of indexed families of computable languages from positive data. This paper shows that an effective version of Shinohara's notion of bounded finite thickness gives sufficient conditions for learnability with ordinal mind change bound, both in the context of learnability from positive data and for learnability from complete (both positive and negative) data. Let ω be a notation for the first limit ordinal. Then, it is shown that if a language defining framework yields a uniformly decidable family of languages and has effective bounded finite thickness, then for each natural number m>0, the class of languages defined by formal systems of length ⩽m: •is identifiable in the limit from positive data with a mind change bound of ωm;•is identifiable in the limit from both positive and negative data with an ordinal mind change bound of ω×m. The above sufficient conditions are employed to give an ordinal mind change bound for learnability of minimal models of various classes of length-bounded Prolog programs, including Shapiro's linear programs, Arimura and Shinohara's depth-bounded linearly covering programs, and Krishna Rao's depth-bounded linearly moded programs. It is also noted that the bound for learning from positive data is tight for the example classes considered.

We present a multiple pass streaming algorithm for learning the density function of a mixture of k uniform distributions over rectangles in R^d, for any d>0. Our learning model is: samples drawn according to the mixture are placed in arbitrary order in a data stream that may only be accessed sequentially by an algorithm with a very limited random access memory space. Our algorithm makes 2@?+2 passes, for any @?>0, and requires memory at most O@?(@e^-^2^/^@?k^2d^4+(4k)^d), where @e is the tolerable error of the algorithm. This exhibits a strong memory-pass tradeoff in terms of @e: a few more passes significantly lower its memory requirements, thus trading one of the two most important resources in streaming computation for the other. Chang and Kannan first considered this problem for d=1,2. Our learning algorithm is especially appropriate for situations where massive data sets of samples are available, but computation with such large inputs requires very restricted models of computation.