35099614
On Learning Limiting Programs
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 trade-off results are obtained regarding learning power, number (possibly zero) of limits taken, program size constraints and information, and number of errors tolerated in final programs learned.
5851955
Vacillatory Learning of Nearly Minimal Size Grammars
In Gold's influential language learning paradigm a learning machine converges in the limit to one correct grammar. In an attempt to generalize Gold's paradigm, Case considered the question whether people might converge to vacillating between up to (some integer) n > 1 distinct, but equivalent, correct grammars. He showed that larger classes of languages can be algorithmically learned (in the limit) by converging to up to n + 1 rather than up to n correct grammars. He also argued that, for ''small'' n>1, it is plausible that people might sometimes converge to vacillating between up to n grammars. The insistence on small n was motivated by the consideration that, for ''large'' n, at least one of n grammars would be too large to fit in people's heads. Of course, even for Gold's n = 1 case, the single grammar converged to in the limit may be infeasibly large. An interesting complexity restriction to make, then, on the final grammar(s) converged to in the limit is that they all have small size. In this paper we study some of the trade-offs in learning power involved in making a well-defined version of this restriction. We show and exploit as a tool the desirable property that the learning power under our size-restricted criteria (for successful learning) is independent of the underlying acceptable programming systems. We characterize the power of our size-restricted criteria and use this characterization to prove that some classes of languages, which can be learned by converging in the limit to up to n + 1 nearly minimal size correct grammars, cannot be learned by converging to up to n unrestricted grammars even if these latter grammars are allowed to have a finite number of anomalies (i.e., mistakes) per grammar. We also show that there is no loss of learning power in demanding that the final grammars be nearly minimal size iff one is willing to tolerate an unbounded, finite number of anomalies in the final grammars and there is a constant bound on the number of different grammars converged to in the limit. Hence, if we allow an unbounded, finite number of anomalies in the final grammars and the number of different grammars converged to in the limit is unbounded but finite (or if there is a constant bound on the number of anomalies allowed in the final grammars), then there is a loss of learning power in requiring that the final grammars be nearly minimal size. These results do not always match what might be expected from the cases, previously examined by Freivalds, Kinber, and Chen, of learning nearly minimal size programs for functions.
145211
Computational Limits on Team Identification of Languages
A team of learning machines is a multiset of learning machines. A team is said to successfully identify a concept just in case each member of some nonempty subset, of predetermined size, of the team identifies the concept. Team identification of programs for computable functions from their graphs has been investigated by Smith. Pitt showed that this notion is essentially equivalent to function identification by a single probabilistic machine. The present paper introduces, motivates, and studies the more difficult subject of team identification of grammars for languages from positive data. It is shown that an analog of Pitt's result about equivalence of team function identification and probabilistic function identification does not hold for language identification, and the results in the present paper reveal a very complex structure for team language identification. It is also shown that for certain cases probabilistic language identification is strictly more powerful than team language identification. Proofs of many results in the present paper involve very sophisticated diagonalization arguments. Two very general tools are presented that yield proofs of new results from simple arithmetic manipulation of the parameters of known ones.
644359
Anomalous Learning Helps Succinctness
Abstract It is shown that allowing a bounded number of anomalies (mistakes) in the final programs learned by an algorithmic procedure can considerably “succinctify” those final programs. Naturally, only those contexts are investigated in which the presence of anomalies is not actually required for successful inference (learning). The contexts considered are certain infinite subclasses of the class of characteristic functions of finite sets. For each finite set D , these subclasses have a finite set containing D . This latter prevents the anomalies from wiping out all the information in the sets featured in these subclasses and shows the context to be fairly robust. Some of the results in the present paper are shown to be provably more constructive than others. The results of this paper can also be interpreted as facts about succinctness of coding finite sets, which facts have interesting consequences for learnability of decision procedures for finite sets.
39847140
Team Learning of Recursive Languages
A team of learning machines is a multiset of learning machines. A team is said to successfully learn a concept just in case each member of some nonempty subset, of predetermined size, of the team learns the concept. Team learning of languages turns out to be a suitable theoretical model for studying computational limits on multi-agent machine learning. Team learning of recursively enumerable languages has been extensively studied. However, it may be argued that from a practical point of view all languages of interest are recursive. 
 
This paper gives theoretical results about team learnability of recursive languages. These results are mainly about two issues: redundancy and aggregation. The issue of redundancy deals with the impact of increasing the size of a team and increasing the number of machines required to be successful. The issue of aggregation deals with conditions under which a team may be replaced by a single machine without any loss in learning ability. The learning scenarios considered are: (a) Identification in the limit of accepting grammars for recursive languages. (b) Identification in the limit of decision procedures for recursive languages. (c) Identification in the limit of accepting grammars for indexed families of recursive languages. (d) Identification in the limit of accepting grammars for indexed families with enumerable class of grammars for the family as the hypothesis space. Scenarios which can be modeled by team learning are also presented.
122230605
On the intrinsic complexity of learning recursive functions
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, both natural 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 easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally".
32884753
Expert Simulation For On-line Scheduling
In recent years, the automotive industry has realized the importance of speed of new products to market and has mounted efforts for improving it. The Expert System Scheduler (ESS) facilitates these efforts by enabling manufacturing plants to generate viable schedules under increasing constraints and demands for flexibility. The scheduler takes advantage of the Computer Integrated Manufacturing (CIM) environment by utilizing the real-time information from the factory for responsive scheduling. The Expert System Scheduler uses heuristics developed by an experiences factory scheduler. It uses simulation concepts and these heuristics to generate schedules. Forward and "backward" simulation are used at different stages of the schedule generation process. The system is used to control parts flow on the factory floor at one automated facility. This highly automated facility is a testbed for implementation of CIM concepts. The scheduler runs on a Texas Instruments (TI) Explorer II computer using software developed inhouse utilizing IntelliCorp's Knowledge Engineering Environment (KEE) shell and the LISP language. The scheduling computer is networked to the factory control computer, which actually controls the plant floor. The TI Explorer II acquires current plant floor information from the factory control system, generates a new schedule and sends it back within a short time. The configuration allows fast response to changes in requirements and plant floor conditions.
34370031
Simulation for emergency response: a framework for modeling and simulation for emergency response
A number of modeling and simulation tools have been developed and more are being developed for emergency response applications. The available simulation tools are meant mostly for standalone use. Addressing an emergency incident requires addressing multiple interdependent aspects of the situation. The simulation tools addressing different aspects of an emergency situation need to be integrated to provide the whole picture to planners, trainers, and responders. A framework is required to ensure that modeling and simulation tools can be systematically integrated together to address the overall response. This paper proposes a framework for integration of modeling, simulation, and visualization tools for emergency response. The development and implementation of the proposed framework will significantly improve the nation's capability in the emergency response area.
120386960
Evolutionary games with two timescales
We consider a two timescale model of learning by economic agents wherein active or 'ontogenetic' learning by individuals takes place on a fast scale and passive or 'phylogenetic' learning by society as a whole on a slow scale, each affecting the evolution of the other. The former is modelled by the Monte Carlo dynamics of physics, while the latter is modelled by the replicator dynamics of evolutionary biology. Various qualitative aspects of the dynamics are studied in some simple cases, both analytically and numerically, and its role as a useful modelling device is emphasized.
30649473
Joint Bidding in the Name-Your-Own-Price Channel: A Strategic Analysis
In this paper, we study the name-your-own-price (NYOP) channel. We examine theoretically and empirically whether asking consumers to place a joint bid for multiple items, rather than bid one item at a time as practiced today, can increase NYOP retailers' profits. Relatedly, we also examine whether allowing consumers to self-select whether to place a joint bid or itemwise bids increases retailers' profits and consumers' surplus. We construct a dynamic model that incorporates both demand uncertainty and supply uncertainty to address these issues. Our theoretical analysis identifies the conditions under which joint bidding can increase both NYOP retailers' profits and consumers' surplus. We find that some consumers might bid more for the very same items when they place joint bids. The increase in bid amount is related to the fact that joint bidding reduces the chance of mismatch between NYOP retailers' costs and consumer bids. We conducted a laboratory study to assess the descriptive validity of some of the model predictions, because there are no field data on joint bidding in the NYOP channel. The results of the study are directionally consistent with our theory.
15127807
Pricing of Information Products on Online Servers: Issues, Models, and Analysis
Online information servers that provide access to diverse databases where users can search for, browse through, and download the information they need have been rapidly increasing in number in the past few years. Online vendors have traditionally charged users for information on the based on the length of the time they were connected to the databases. With hardware and software advances, many online servers have recently started changing their pricing strategies to search-based and/or subscription-fee pricing. This paper examines the various issues involved in pricing these information products, and presents an economic approach to analyze conditions under which the various pricing schemes may prove optimal for the online servers. Our results show that the variation in consumer expertise and valuation of information affects the choice of a pricing strategy by the server. We present general conditions under which subscription-fee pricing is optimal even when consumer demand is inelastic. We also find that, given the cost structures characterizing the market, undifferentiated online servers can compete and coexist in the market each making positive profits. We show that in a competitive setting an increase in costs of online servers can sometimes benefit them by enabling them to differentiate themselves. Our results offer insights into the trends in pricing strategies and may provide an explanation as to why many servers may persist with connect-time strategies.