Gold (1967) discovered a fundamental enumeration technique, the socalled identification-by-enumeration, a simple but powerful class of algorithms for learning from examples (inductive inference). We introduce a variety of more sophisticated (and more powerful) enumeration techniques and characterize their power. We conclude with the thesis that enumeration techniques are even universal in that each solvable learning problem in inductive inference can be solved by an adequate enumeration technique. This thesis is technically motivated and discussed.

Over a period of thirty years there have been many curriculum reforms in the Undergraduate Computer Science curriculum. The ACM/IEEE-CS task force is currently working on the Curriculum 2001. In this struggle to define and develop this dynamic field of computer science, we have the opportunity to identify the foundations and related concepts of mathematics we would like to see in the new CS curriculum and introduce these in CS1 and CS2. Many standard topics of discrete mathematics can encourage the use of mathematical thinking when taught along with the CS courses. The more complex foundations and other theoretical topics may be introduced later in the curriculum. This session will present some of the views and examples in this direction. Our goal is not to eliminate the need of discrete math but to integrate it into the basics of CS so that the student will experience mathematical reasoning in the early stages of the development of CS topics. Currently discrete math is taught as one of the early math requirements and many students do not see the relationship between the programming concepts and these mathematical concepts. An early blend of these ideas of will provide a richer experience to CS majors and the new topics can be learned more quickly if the underlying theoretical concepts are well understood. The programming languages of choice can be introduced in separate laboratory components taken parallel to CS1 and CS2.We hope that we all can agree that CS is not just programming and we have a new discipline that must develop its basic theory rather than depending on other disciplines to do it for us. Someday, the courses we know now as CS1 and CS2 maybe known as University Computing I and II as we now have in some of the other sciences.

The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion.For several types of learning recursive functions (learning in the limit, learning with a bounded number of mind changes, learning with anomalies), both generic complete classes are exhibited and necessary and sufficient conditions for completeness are derived.Informally, a class is complete iff both its topological structure is highly complex while its algorithmic structure is surprisingly easy.Counter-intuitively, some self-describing classes turn out to be complete.

In this paper, we reconsider the definition of procrastinating learning machines. In the original definition of Freivalds and Smith [FS93], constructive ordinals are used to bound mindchanges. We investigate possibility of using arbitrary linearly ordered sets to bound mindchanges in similar way. It turns out that using certain ordered sets it is possible to define inductive inference types different from the previously known ones. We investigate properties of the new inductive inference types and compare them to other types.

The functions of finite support have played a ubiquitous role in the study of inductive inference since its inception. In addition to providing a clear and simple example of a learnable class, the functions of finite support are employed in many proofs that distinguish various types and features of learning. Recent results show that this ostensibly simple class requires as much space to learn as any other learnable set and, furthermore, is as intrinsically difficult as any other learnable set. Since the class of functions of finite support sit at the top of two very different complexity hierarchies, this class is a candidate for being a canonical learning problem. We argue for this point in the paper and discuss the ramifications.

Proceedings of the Annual ACM Conference on Computational Learning Theory

We generalize the traditional concept of team learning.The success of an asymmetric team in learning some function depends upon the successes of participant machines by an arbitrary nondecreasing Boolean function.Asymmetric team types are ordered accordingly to their learning power by basic reductions.The problem to determine this order for an arbitrary pair of asymmetric teams is shown to be NP-hard.Basic reductions are independent of the properties of any particular definition of learning.Many learning types (e.g.EX, -learning with no more than n mindchanges) have additional team order relations which vary from case to case.We define a learning type PINFlN which allows only the basic reductions between its teams.The relation between asymmetric team learning and probabilistic learning is described by a zerosum matrix game.

Introduction The starting point for studies in inductive inference is the model of learning by example introduced by Gold [Gol67]. This is a simple model of learning algorithms that input examples of some function and produce programs that are intended to compute the function generating the examples. Learning takes place as the "correct " program must be produced after the learning algorithm has seen only finitely many examples. The functions used as input are typically (partial) recursive functions. Using traditional encoding techniques, this class of functions is rich enough to model a wide range of phenomena [AS83]. Researchers in inductive inference have used the basic model of Gold to study the effects of other parameters of the learning process such as errors tolerance, plurality of approaches, probability of success, learning via queries, etc. Herein we combine traditional studies of inductive inference and classical continuous mathematics to produce a study of learning

Most work in the field of inductive inference regards the learning machine to be a passive recipient of data. In a prior paper the passive approach was compared to an active form of learning where the machine is allowed to ask questions. In this paper we continue the study of machines that ask questions by comparing such machines to teams of passive machines. This yields, via work of Pitt and Smith, a comparison of active learning with probabilistic learning. Also considered are query inference machines that learn an approximation of what is desired. The approximation differs from the desired result in finitely many anomalous places.

People tend not to have perfect memories when it comes to learning, or to anything else for that matter.Most formal studies of learning, however, assume a perfect memory.Some approaches have restricted the number of items that could be retained.We introduce a This work was facilitated by an international

A class U of recursive functions is said to be finitely (a, b) learnable if and only if for any b tuple of pairwise distinct functions from U at least a of the b functions have been learned correctly from examples of their behavior after some finite amount of time. It is shown that this approach, called learning in parallel, is more powerful than nonparallel learning. Furthermore, it is shown that imposing the restriction (called parallel super learning) on parallel learning that the learning algorithm also identiy on which of the input functions it is successful is still more powerful than nonparallel learning, A necessary and sufficient condition is derived for (a, b) superlearning and (c, d) superlearning being the same power. Our new notion of parallel learning is compared with other, previously defined notions of learning in parallel. Finally, we synthesize our notion of learning in parallel with the concept of team learning and obtain some interesting trade-offs and comparisons.

The problem of generalizing from specific instances to descriptions of underlying concepts is represented abstractly as the problem of inductive inference. A similarly abstract rendition of the problem of classifying concepts from a collection into one of a finite set a categories is introduced. The mathematical representations of generalization and classification admit to rigorous comparisons. We show similarities as well as differences between the problems of generalization and classification. Some characterizations of an interesting, potentially practical, restriction of the classification problem are presented.

Article Free Access Share on Co-learning of total recursive functions Authors: Rūsiņš Freivalds Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga Latvia Department of Computer Science, University of Latvia, Raina bulvaris 29, LV-1459, Riga LatviaView Profile , Marek Karpinski Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 Germany Department of Computer Science, University of Bonn, Römerstrasse 164, D-5300, Bonn 1 GermanyView Profile , Carl H. Smith Department of Computer Science, University of Maryland, College Park, MD Department of Computer Science, University of Maryland, College Park, MDView Profile Authors Info & Claims COLT '94: Proceedings of the seventh annual conference on Computational learning theoryJuly 1994 Pages 190–197https://doi.org/10.1145/180139.181098Published:16 July 1994Publication History 8citation28DownloadsMetricsTotal Citations8Total Downloads28Last 12 Months12Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

constant, finite amount of memory, there are and T such that

A class U of recursive functions is said to be finitely (a,b) learnable if and only if for any b tuple of pairwise distinct functions from U at least a of the b functions have been learned correctly from examples of their behaviour after some finite amount of time. It is shown that this approach, called learning in parallel, is more powerful than non parallel learning. Furthermore, it is shown that imposing the restriction (called parallel super learning) on parallel learning that the learning algorithm also identify which of the input functions it is successful on is still more powerful than non parallel learning. A necessary and sufficient condition is derived for (a,b) superlearning and (c,d) superlearning being the same power. Our new notion of parallel learning is compared with other, previously defined notions of learning in parallel. Finally, we synthesis our notion of learning in parallel with the concept of team learning and obtain some interesting trade offs and comparisons. (orig.)

Article Free Access Share on On the role of procrastination for machine learning Authors: Rūsiņš Freivalds Institute of Mathematics and Computer Science, University of Latvia, Raina bulvaris 29, 226250, Riga, Latvia Institute of Mathematics and Computer Science, University of Latvia, Raina bulvaris 29, 226250, Riga, LatviaView Profile , Carl H. Smith Department of Computer Science and Institute for Advanced Computer Studies, The University of Maryland, College Park, MD Department of Computer Science and Institute for Advanced Computer Studies, The University of Maryland, College Park, MDView Profile Authors Info & Claims COLT '92: Proceedings of the fifth annual workshop on Computational learning theoryJuly 1992 Pages 363–376https://doi.org/10.1145/130385.130426Published:01 July 1992Publication History 1citation62DownloadsMetricsTotal Citations1Total Downloads62Last 12 Months51Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Generalization is a learning problem that has received considerable attention. The generalization problem is to take a finite sample of some concept and produce an algorithm that can produce all other (perhaps infinitely many) samples of the same concept. Inductive inference is the study of this problem in a most general framework [1]. The classification problem is to take a finite sample of some concept and decide which type of concept the sample is from. The choice of type is usually finite. If the mechanism performing the classification is limiting, e.g., it makes more and more conjectures as to a classification as time goes on, then the process can also be considered as a type of learning. Roughly, we will say that some suitable mechanism has learned an appropriate classification if its sequence of conjectures stabilizes at some point. In this paper we formalize, at a suitable level of abstraction, the classification problem and rigorously compare it to the generalization problem. Despite some obvious similarities, the two notions are shown to be distinct. The new formalism of classification is investigated further.

Traditional work in inductive inference has been to model a learner receiving data about a function f and trying to learn the function. The data is usually just the values f (0), f (1),…. The scenario is modeled so that the learner is also allowed to ask questions about the data (e.g., (∀ χ) [χ> 17 → f ( χ ) = 0]?). An important parameter is the language that the lerner may use to formulate queries. We show that for most languages a learner can learn more by asking questions than by passively receiving data. Mathematical tools used include the solution to Hilbert's tenth problem, the decidability of Presuburger arithmetic, and ω-automata.

Self‐knowledge is a concept that is present in several philosophies. In this article, we consider the issue of whether or not a learning algorithm can in some sense possess self‐knowledge. The question is answered affirmatively. Self‐learning inductive inference algorithms are taken to be those that learn programs for their own algorithms, in addition to other functions. La connaissance de soi est un concept qui se retrouve dans plusieurs philosophies. Dans cet article, les auteurs s'interrogent à savoir si un algorithme d' apprentissage peut dans une certaine mesure posséder la connaissance de soi. lis apportent une reponse positive a cette question. Les algorithmes d'inference inductive autodidactes sont ceux qui font l'apprentissage de programmes pour leurs propres algorithmes, en plus d' autres fonctions.

Properties for software complexity measures are discussed. It is shown that a collection of nine properties suggested by E.J. Weyuker is inadequate for determining the quality of a software complexity measure. (see ibid., vol.14, p.1357-65, 1988). A complexity measure which satisfies all nine of the properties, but which has absolutely no practical utility in measuring the complexity of a program is presented. It is concluded that satisfying all of the nine properties is a necessary, but not sufficient, condition for a good complexity measure.>

Intuitively, the more a machine knows the more it can learn. This intuition is formalized in a recursion theoretic framework. A formal definition of what it means for a machine to learn a finite sequence of recursive functions is presented. We prove that there are sets of sequences S, and a sequence 〈ƒ1, ƒ2, …, ƒn〉ϵ S such that in order to learn a program for ƒi a machine must necessarily know programs for ƒ1, …, ƒi−1. Also investigated is the simultaneous inference of programs for a finite set of recursive functions.

The power of various query languages is compared along two dimensions, namely the inherent power of the language and the number of alternations of quantizers. Learning by asking questions is compared to learning by passively reading data. It is found that the extent of what can be learned by queries is largely dependent on the language used by the inference mechanism to formulate questions to ask of its trainer. It is proved that inference machines that are allowed to ask first-order questions with plus and times can be used to solve the halting problem and therefore can learn all the recursive functions. Learning languages are also considered.>

Inductive inference, the automatic synthesis of programs, bears certain ostensible relationships with program testing. For inductive inference, one must take a finite sample of the desired input/output behavior of some program and produce (synthesize) an equivalent program. In the testing paradigm, one seeks a finite sample for a function such that any program (in a given set) which computes something other than the object function differs from the object function on the finite sample. In both cases, the finite sample embodies sufficient knowledge to isolate the desired program from all other possibilities. These relationships are investigated and general recursion theoretic properties of testable sets of functions are exposed.

Inductive reference machmes (IIMs) synthesize programs, given examples of their intended input-output behavior.Several different criteria for successful synthesis by llMs are defined.A given criterion is said to be more general than some other criterion if the class of sets which can be inferred by some IIM with respect to the given criterion is larger than the class of sets which can be referred by some IIM with respect to the other criterion A team of IIMs synthesizes programs for a set of functions if and only ff for each function m the set, at least one of the IIMs m the team successfully synthesizes the proper program.The trade-offs between the number of IIMs involved in the learnmg process and the generality of the criteria of success are examined Categories and Subject Descriptors: F.

The augmented data manipulator (ADM) [5] has been proposed as an interconnection scheme for microprocessors. In this note we show how the number of permutations achieved by the last stage of an n-node ADM may be derived from a Fibonacci series. This result was used in [1] to analyze the total number of permutations achieved by an entire ADM.

Inductive inference machines (IIMs) are algorithmic devices which accept as input the graph of a computable function, an ordered pair at a time, and which output a succession of programs each conjectured to compute the input function. IIMs synthesize programs given examples of their intended input-output behavior. Several different criterion for successful synthesis by IIMs are defined. A given criterion is said to be more general than some other criterion if the class of sets which can be inferred by some IIM with respect to the given criteria is larger than the class of sets which can be inferred by some IIM with respect to the other criterion. The tradeoffs between the number of IIMs involved in the learning process and the generality of the criteria of success are examined.

Article Free Access Share on Anomaly hierarchies of mechanized inductive inference Authors: John Case View Profile , Carl Smith View Profile Authors Info & Claims STOC '78: Proceedings of the tenth annual ACM symposium on Theory of computingMay 1978 Pages 314–319https://doi.org/10.1145/800133.804360Online:01 May 1978Publication History 15citation13DownloadsMetricsTotal Citations15Total Downloads13Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The discriminating content addressable memory (DCAM) is a modified content addressable memory (CAM). After the ``similar to'' search performed by the CAM, the modified memory searches in parallel for the highest value in a particular field across all words of the memory. Applications of DCAM can greatly speed up queue searches and scheduling processes in operating systems. Worst case DCAM query time for 1000 words is 2 μs. The number of extra gates required by a DCAM increases linearly with memory size.