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.
35497745
On Aggregating Teams of Learning Machines
39763724
Branch and bound on the network model
Abstract Karp and Zhang developed a general randomized parallel algorithm for solving branch and bound problems. They showed that with high probability their algorithm attained optimal speedup within a constant factor (for p⩽ n/( log n) c , where p is the number of processors, n is the “size” of the problem, and c is a constant). Ranade later simplified the analysis and obtained a better processor bound. Karp and Zhang's algorithm works on models of computation where communication cost is constant. The present paper considers the Branch and Bound problem on networks where the communication cost is high. Suppose sending a message in a p processor network takes G = O ( log p) time and node expansion (defined below) takes unit time (other operations being free). Then a simple randomized algorithm is presented which is, asymptotically, nearly optimal for p = O (2 log c n ) , where c is any constant and n is the number of nodes in the input tree with cost no greater than the cost of the optimal leaf in the tree.
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.
18622476
Learning in the Presence of Partial Explanations
Abstract 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.
35698338
Generality's price: Inescapable deficiencies in machine-learned programs
Abstract This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of those optimal, learned programs are provably unalterably information deficient—in some cases, deficient as to safe, algorithmic extractability/provability of the fact that they are even approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, computably axiomatizable extensions of Peano Arithmetic.
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.
1156882
Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability
Abstract
In this paper, we present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.

18971661
Development of a high-level supply chain simulation model
This paper describes an effort that involved development of a simulation model for evaluating the business processes and inventory control parameters of a logistics and distribution supply chain. A generic simulation tool, rather than a supply chain simulator, was developed for meeting customized needs of the effort. The paper describes, the approaches used to model at the selected level of abstraction, the development of interfaces for data and experimentation and the development and delivery of animation for communicating the approach and results to the client.
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.
11952430
David vs. Goliath: An Analysis of Asymmetric Mixed-Strategy Games and Experimental Evidence
Mixed strategies are widely used to model strategic situations in diverse fields such as economics, marketing, political science, and biology. However, some of the implications of asymmetric mixed-strategy solutions are counterintuitive. We develop a stylized model of patent race to examine some of these implications. In our model two firms compete to develop a product and obtain a patent. However, one firm values the patent more because of its market advantages, such as brand reputation and distribution network. Contrary to some intuition, we find that the firm that values the patent less is likely to invest more aggressively in developing the product and will also win the patent more often. We argue that the reason for these counterintuitive results is inherent in the very concept of mixed strategy solution. In a laboratory test, we examine whether subjects' behavior conforms to the equilibrium predictions. We find that the aggregate behavior of our subjects is consistent with the game-theoretic predictions. With the help of the experience-weighted attraction (EWA) learning model proposed by Camerer and Ho (1999), we show that adaptive learning can account for the investment behavior of our subjects.We find that the EWA learning model tracks the investment decisions of our subjects well, whether we hold out trials or an entire group of subjects.