7521284
On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms
A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones. An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible compared to the original coordinator. Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable. We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory.
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.
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.
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.
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".
9214465
Performance prediction tools for parallel discrete-event simulation
We have developed a set of performance prediction tools which help to estimate the achievable speedups from parallelizing a sequential simulation. The tools focus on two important factors in the actual speedup of a parallel simulation program: the simulation protocol used; and the inherent parallelism in the simulation model. The first two tools are a performance/parallelism analyzer for a conservative, asynchronous simulation protocol, and a similar analyzer for a conservative, synchronous (super-step) protocol. Each analyzer allows us to study how the speedup of a model changes with increasing number of processors, when a specific protocol is used. The third tool-a critical path analyzer-gives on ideal upper bound to the model's speedup. This paper gives an overview of the prediction tools, and reports the predictions from applying the tools to a discrete-event wafer fabrication simulation model. The predictions are close to speedups from actual parallel implementations. These tools help us to set realistic expectations of the speedup from a parallel simulation program, and to focus our work on issues which are more likely to yield performance improvement.
18211780
Supply chain opportunities: panel session: opportunities for simulation in supply chain management
It has become a matter of survival that many companies improve their supply chain efficiency. This presents an opportunity for simulation. However, there are many challenges that must be overcome for simulation to be a contributor to play an effective role. Four contributors discuss the opportunities that they see for simulation to play a meaningful role in the area of supply chain management.
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.
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.
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.