16015083
Learning languages in a union
In inductive inference, a machine is given words of a language (a recursively enumerable set in our setting) and the machine is said to identify the language if it correctly names the language. In this paper we study identifiability of classes of languages where the unions of up to a fixed number (n say) of languages from the class are provided as input. We distinguish between two different scenarios: in one scenario, the learner need only to name the language which results from the union; in the other, the learner must individually name the languages which make up the union (we say that the unioned language is discerningly identified). We define three kinds of identification criteria based on this and by the use of some classes of disjoint languages, demonstrate that the inferring power of each of these identification criterion decreases as we increase the number of languages allowed in the union, thus resulting in an infinite hierarchy for each identification criterion. That is, we show that for each n, there exists a class of disjoint languages where all unions of up to n languages from this class can be discerningly identified, but there is no learner which identifies every union of n+1 languages from this class. A comparison between the different identification criteria also yielded similar hierarchies. We give sufficient conditions for classes of languages where the unions can be discerningly identified, and characterize such discerning learnability for the indexed families. We then give naturally occurring classes of languages that witness some of the earlier hierarchical results. Finally, we present language classes which are complete with respect to weak reduction (in terms of intrinsic complexity) for our identification criteria.
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.
30890449
Prudence in Vacillatory Language Identification (Extended Abstract)
The present paper settles an open question about ‘prudent’ vacillatory identification of grammars from positive data only.
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.
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".
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.
195860327
Criticality of detailed modeling in semiconductor supply chain simulation
Supply chain management offers a large potential for organizations to reduce costs and improve customer service performance. Simulation of supply chains can help in these objectives by evaluating the impact of alternative inventory control policies. Supply chain simulation involves the modeling of multiple factories across the chain and can get quite complex. Analysts typically carry out such simulation at a coarse level of detail to keep the complexity and computing resources manageable. However, modeling at coarse levels may reduce the accuracy of outputs and affect the quality of decisions. In this paper, we report on a study to compare the quality of results at different levels of detail in a semiconductor supply chain simulation.
5203881
Components of an Incident Management Simulation and Gaming Framework and Related Developments
The nation's emergency responders need to work in a coordinated, well-planned manner to best mitigate the impact of an emergency incident. They need to be trained and ready to act in view of the increased security threat. The training has been traditionally provided using live eXercises at great eXpense. Simulation and gaming systems could provide a wider range of training at a much lower cost. Integrated gaming and simulation systems should be used for training decision makers and responders on the same scenarios, preparing them to work together as a team. A large number of simulation and gaming tools are needed to address the huge number of scenarios that can be of interest for incident management. An efficient approach will be to develop a library of interoperable component models that can be assembled together in different combinations to represent a range of scenarios. Standard specifications of the component models are needed to stimulate the development. The specifications should allow for alternate competing implementations. This paper presents a conceptual architecture that partitions the incident management simulation and gaming solution space into standard components. Recent literature is surveyed to identify related models and/or simulators where available for each defined component. The suggested components and the survey lay some preliminary groundwork in developing a holistic model of the incident response domain.
16256467
Implementations of dispatch rules in parallel manufacturing simulation
Most features in commercial simulation packages are often omitted in parallel simulation benchmarks, because they neither affect the overall correctness of the simulation protocol nor the benchmark's performance. In our work on parallel simulation of a wafer fabrication plant, we however find several features which complicate the implementation of the simulation protocol and affect the program performance. One such feature is the dispatch rules which a machine set uses to decide the priority of the waiting wafer lots. In a sequential simulation, the dispatch rule can be implemented in a straightforward fashion, because the whole system state is at the same simulation time, and the rule simply reads the state variables (of any machine, resources, etc.) In a parallel simulation, the dispatch rule computation may be complicated by the fact that different portions of the simulated system can be at different simulation times. This paper describes our study of the implementation of dispatch rules in parallel simulation. This is actually an instance of the little-studied problem of providing shared-state information in parallel simulation. We briefly survey previous related work. We then outline two different approaches for a dispatch rule to access the shared-state information and compare them in terms of their ease of implementation.
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.
201885623
Manufacturing supply chain applications: modeling computer assembly operations for supply chain integration
Factory operations have been modeled for years to understand the relationship between the different design and policy factors and the performance measures of interest. The increasing awareness of the need to manage factories as a link in the supply chain places a corresponding requirement for an enhanced approach for factory modeling. This paper describes the modeling of a computer assembly factory for supply chain integration by including aspects of inbound and outbound logistics and relevant business processes. Lessons are drawn based on the experience.