While it is commonly accepted that computability on a Turing machine in polynomial time represents a correct formalization of the notion of a feasibly computable function, there is no similar agreement on how to extend this notion on functionals , that is, what functionals should be considered feasible. One possible paradigm was introduced by Mehlhorn, who extended Cobham's definition of feasible functions to type 2 functionals. Subsequently, this class of functionals (with inessential changes of the definition) was studied by Townsend who calls this class POLY , and by Kapron and Cook who call the same class basic feasible functionals . Kapron and Cook gave an oracle Turing machine model characterisation of this class. In this article, we demonstrate that the class of basic feasible functionals has recursion theoretic properties which naturally generalise the corresponding properties of the class of feasible functions, thus giving further evidence that the notion of feasibility of functionals mentioned above is correctly chosen. We also improve the Kapron and Cook result on machine representation.Our proofs are based on essential applications of logic. We introduce a weak fragment of second order arithmetic with second order variables ranging over functions from N N which suitably characterises basic feasible functionals, and show that it is a useful tool for investigating the properties of basic feasible functionals. In particular, we provide an example how one can extract feasible programs from mathematical proofs that use nonfeasible functions.

Proceedings of the Annual ACM Conference on Computational Learning Theory

Article Free Access Share on Robust learning aided by context Authors: John Case Department of CIS, University of Delaware, Newark, DE Department of CIS, University of Delaware, Newark, DEView Profile , Sanjay Jain Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of Singapore Department of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of SingaporeView Profile , Matthias Ott Institut für Logik, Komplexität und Deduktionssysteme Universität Karlsruhe, 76128 Karlsruhe, Germany Institut für Logik, Komplexität und Deduktionssysteme Universität Karlsruhe, 76128 Karlsruhe, GermanyView Profile , Arun Sharma School of Computer Science and Engineering, University of New South Wales, Sydney 2052, Australia School of Computer Science and Engineering, University of New South Wales, Sydney 2052, AustraliaView Profile , Frank Stephan Mathematisches Institut, Universität Heidelberg, 69120 Heidelberg, Germany Mathematisches Institut, Universität Heidelberg, 69120 Heidelberg, GermanyView Profile Authors Info & Claims COLT' 98: Proceedings of the eleventh annual conference on Computational learning theoryJuly 1998 Pages 44–55https://doi.org/10.1145/279943.279952Published:24 July 1998Publication History 1citation230DownloadsMetricsTotal Citations1Total Downloads230Last 12 Months8Last 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

Speed of convergence in Gold's identification in the limit model can be measured by deriving bounds on the number of mind changes made by a learner before the onset of convergence. Two approaches to date are bounds given by constants (referred here as Type 1) and bounds expressed as constructive ordinals (referred as Type 2). The use of ordinals has recently been successfully employed to measure the mind change complexity of learning rich concept classes such as unions of pattern languages, elementary formal systems and logic programs. Motivated by these applications, the present work introduces two more general approaches to bounding mind changes. These are based on counting by going down in a linearly ordered set (Type 3) and on counting by going down in a partially ordered set (Type 4). In both cases the set must not contain infinite, descending, and computable sequences. These four types of mind changes yield a hierarchy and there are identifiable classes that cannot be learned wit...

Abstract Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of “intrinsic” complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification. The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages. Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open.

Most theoretical models of inductive inference make the idealized assumption that the data available to a learner is from a single and accurate source. The subject of inaccuracies in data emanating from a single source has been addressed by several authors. The present paper argues in favor of a more realistic learning model in which data emanates from multiple sources, some or all of which may be inaccurate. Three kinds of inaccuracies are considered: spurious data (modeled as noisy texts), missing data (modeled as incomplete texts), and a mixture of spurious and missing data (modeled as imperfect texts). Motivated by the above argument, the present paper introduces and theoretically analyzes a number of inference criteria in which a learning machine is fed data from multiple sources, some of which may be infected with inaccuracies. The learning situation modeled is the identification in the limit of programs from graphs of computable functions. The main parameters of the investigation are: the kind of inaccuracy, the total number of data sources, the number of faulty data sources which produce data within an acceptable bound, and the bound on the number of errors allowed in the final hypothesis learned by the machine. Sufficient conditions are determined under which, for the same kind of inaccuracy, for the same bound on the number of errors in the final hypothesis, and for the same bound on the number of inaccuracies, learning from multiple texts, some of which may be inaccurate, is equivalent to learning from a single inaccurate text. The general problem of determining when learning from multiple inaccurate texts is a restriction over learning from a single inaccurate text turns out to be combinatorially very complex. Significant partial results are provided for this problem. Several results are also provided about conditions under which the detrimental effects of multiple texts can be overcome by either allowing more errors in the final hypothesis or by reducing the number of inaccuracies in the texts. It is also shown that the usual hierarchies resulting from allowing extra errors in the final program (results in increased learning power) and allowing extra inaccuracies in the texts (results in decreased learning power) hold. Finally, it is demonstrated that in the context of learning from multiple inaccurate texts, spurious data is better than missing data, which in turn is better than a mixture of spurious and missing data.

Article Free Access Share on Elementary formal systems, intrinsic complexity, and procrastination Authors: Sanjay Jain Department of ISCS, National University of Singapore, Singapore 119260, Republic of Singapore Department of ISCS, National University of Singapore, Singapore 119260, Republic of SingaporeView Profile , Arun Sharma School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, Australia School of Computer Science and Engineering, The University of New South Wales, Sydney, NSW 2052, AustraliaView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 181–192https://doi.org/10.1145/238061.238093Published:01 January 1996Publication History 6citation230DownloadsMetricsTotal Citations6Total Downloads230Last 12 Months7Last 6 weeks4 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

Consider a scenario in which an algorithmic machine, M, is being fed the graph of a computable function ƒ. M is said to finitely identify ƒ just in case, after inspecting a finite portion of the graph of ƒ, it emits its first conjecture, which is a program for ƒ, and it never abandons this conjecture thereafter. A team of machines is a multiset of such machines. A team is said to be successful just in case each member of some nonempty subset, of predetermined size, of the team is successful, The ratio of the number of machines required to be successful to the size of the team is referred to as the success ratio of the team. The present paper investigates the finite identification of computable functions by teams of learning machines. The results presented complete the picture for teams with success ratio 12 and greater. It is shown that at success ratio 12, introducing redundancy in the team can result in increased learning power. In particular, it is established that larger collections of functions can be learned by employing teams of 4 machines and requiring at least 2 to be successful than by employing teams of 2 machines and requiring at least 1 to be successful. Surprisingly, it is also shown that introducing further redundancy at success ratio 12 does not yield any extra learning power. In particular, it is shown that the collections of functions that can be finitely identified by a team of 2m machines requiring at least m to be successful is the same as: the collections of functions that can be finitely identified by a team of 4 machines requiring at least 2 to be successful, if is even, and the collections of functions that can be identified by a team of 2 machines requiring at least 1 to be successful, if is odd.

A new investigation of the complexity of language identification is undertaken using the notion of reduction from recursion theory and complexity theory. The approach, referred to as the intrinsic complexity of language identification, employs notions of “weak” and “strong” reduction between learnable classes of languages. The intrinsic complexity of several classes are considered and the results agree with the intuitive difficulty of learning these classes. Several complete classes are shown for both the reductions and it is also established that the weak and strong reductions are distinct.

192-198

Machine learning of limit programs (i.e., programs allowed finitely many mind changes about their legitimate outputs) for computable functions is studied. Learning of iterated limit programs is also studied. To partially motivate these studies, it is shown that, in some cases, interesting global properties of computable functions can be proved from suitable (n+1)-iterated limit programs for them which can not be proved from any n-iterated limit programs for them. It is shown that learning power is increased when (n+1)-iterated limit programs rather than n-iterated limit programs are to be learned. Many tradeoff results are obtained regarding learning power, number (possibly zero) of limits taken, program size constraints, and number of errors tolerated in final programs learned.

The effect of a partial explanation as additional information in the learning process is investigated. A scientist performs experiments to gather experimental data about some phenomenon, and then tries to construct an explanation (or theory) for the phenomenon. A plausible model for the practice of science is an inductive inference machine (scientist) learning a program (explanation) from a graph (set of experiments) of a recursive function (phenomenon). It is argued that this model of science is not an adequate one, as scientists, in addition to performing experiments, make use of some approximate partial explanation based on the “state of the art” knowledge about that phenomenon. An attempt has been made to model this partial explanation as additional information in the scientific process. It is shown that the inference capability of machines is improved in the presence of such a partial explanation. The quality of this additional information is modeled using certain “density” notions. It is shown that additional information about a “better” quality partial explanation enhances the inference capability of learning machines as scientists more than a “not so good” partial explanation. Similar enhancements to inference of approximations, a more sophisticated model of science, are demonstrated. Inadequacies in Gold's paradigm of language learning are investigated. It is argued that Gold's model fails to incorporate certain additional information that children get from their environment. Children are sometimes told about some grammatical rule that enumerates elements of the language. It is argued that these rules are a kind of additional information. They enable children to see in advance elements that are yet to appear in their environments. Also, children are being given some information about what is not in the language. Sometimes, they are rebuked for making incorrect utterances, or are told of a rule that enumerates certain non-elements of the language. An attempt has been made to extend Gold's model to incorporate both the above types of additional information. It is shown that either type of additional information enhances the learning capability of formal language learning devices.