14981222
On a generalized notion of mistake bounds
This paper proposes the use of constructive ordinals as mistake bounds in the on-line learning model. This approach elegantly generalizes the applicability of the on-line mistake bound model to learnability analysis of very expressive concept classes like pattern languages, unions of pattern languages, elementary formal systems, and minimal models of logic programs. The main result in the paper shows that the topological property of effective finite bounded thickness is a sufficient condition for on-line learnability with a certain ordinal mistake bound. An interesting characterization of the on-line learning model is shown in terms of the identification in the limit framework. It is established that the classes of languages learnable in the on-line model with a mistake bound of α are exactly the same as the classes of languages learnable in the limit from both positive and negative data by a Popperian, consistent learner with a mind change bound of α. This result nicely builds a bridge between the two models. C © 2001 Academic Press
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.
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.
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.
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".
6477912
Stress testing a supply chain using simulation
Simulation provides the capability to evaluate performance of a system operating under current or proposed configurations, policies and procedures. It is very applicable to evaluation of strategic and operational level plans for supply chains. It is especially useful for exploring the viability of a supply chain before beginning production. This paper describes the use of simulation for determining the readiness of a supply chain designed by a small company for providing sub-systems to a defense contractor. The supply chain had to be stress tested at surge and mobilization volume levels to meet the requirements. Simulation provided the ideal methodology to identify and demonstrate the behavior of the supply chain under stress and evaluate strategies to meet the defined volumes. It was used to prove the readiness of the supply chain reducing perceived risks in using the virtual operation.
14852497
Towards standards for integrated gaming and simulation for incident management
Simulation and gaming can support decision making through all phases of incident management including prevention, preparedness, response, recovery and mitigation. A number of gaming and simulation tools have been developed for the purpose but they generally utilize proprietary or unique data interfaces and their own view of partitioning the application and solution space. This creates a large obstacle for wide use, and in particular, prevents the use of these tools in an integrated manner to address the application space. This paper explores the groundwork needed to build standards for integrated gaming and simulation tools for incident management. 
 
An architecture has been proposed to identify the required groups of simulation and gaming modules for incident management and define their scope in the solution space. A conceptual model is proposed for the data required for such simulations. Available data exchange standards are mapped to the conceptual data model. A concept prototype has been developed based on the architecture to demonstrate the value of integrated modeling and simulation and the architecture itself. A number of simulation and gaming modules have been utilized to model the major aspects of a hypothetical scenario. The exercise is used to identify the issues due to lack of data exchange standards.
10615305
Manufacturing sypply chain management: distributed supply chain simulation across enterprise boundaries
The effective practice of supply chain management (SCM) is crucial to improve corporations' competitive advantage. Many corporations have built simulation models to facilitate the application of simulation in designing, evaluating, and optimizing their supply chain. Traditionally, a supply chain involves only a single enterprise with multiple facilities and distribution centers. Hence, sharing of detailed simulation models is not a problem in this scenario. But in recent years, the scope of SCM has evolved to cross the enterprise boundaries. Applying simulation in designing, evaluating, and optimizing the supply chain becomes more difficult since the participating corporations might not be willing to share their simulation models with partners. In this paper, distributed simulation techniques are presented as an enabling technology that allows corporations to construct a cross enterprise simulation while hiding model details within the enterprise. This can be realized by either building the simulation on top of the Runtime Infrastructure of the High Level Architecture or building the simulation on top of a customized distributed discrete event simulation protocol. These alternative approaches are compared in terms of their performance and interoperability. The comparison of the performance is done through a benchmarking test of a semiconductor supply chain model.
7194511
A Concept Prototype for Integrated Gaming and Simulation for Incident Management
This paper describes a prototype that has been developed to demonstrate the concept of integrated gaming and simulation for incident management. An architecture for the purpose was developed and presented at the last conference. A hypothetical emergency incident scenario has been developed for demonstrating the applicability of integrated simulation and gaming. A number of simulation and gaming modules have been utilized to model the major aspects of the hypothetical scenario. The modules demonstrate the value of utilizing simulation for incident management applications. They can be used to highlight the value of simulation and gaming for training applications in particular. Two of the simulation modules have been integrated using a modified implementation of the high level architecture to give an idea of the advantages. Technical issues in integration are identified
5859647
Simulation in the next millennium
The paper looks into the future of simulation. The capabilities and features of simulation software of the future are hypothesized, focusing on the major aspects of their use. The features addressed include model building, visualization, output analysis and optimization, integration and the Internet. The discussion of simulation software in the future is closely related to the vision of future applications of simulation. Applications of simulation in the near term future are proposed using examples of advanced applications that are in conceptual stages at present. Applications of simulation in the long term future are also proposed, bordering on science fiction.