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.
16978245
Learning with the Knowledge of an Upper Bound on Program Size
Abstract Two learning situations are considered: machine identification of programs from graphs of recursive functions (modeling inductive hypothesis formation) and machine identification of grammars from texts of recursively enumerable languages (modeling first language acquisition). Both these learning models are extended to account for situations in which a learning machine is provided additional information in the form of knowledge about an upper bound on the minimal size program (grammar) for the function (language) being identified. For a number of such extensions, it is shown that larger classes of functions (languages) can be algorithmically identified in the presence of upper bound information. Numerous interesting relationships are shown between different models of learning, number of anomalies allowed in the inferred program (grammar), and number of anomalies allowed in the upper bound information.
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.
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.
10962196
Absolute versus probabilistic classification in a logical setting
Suppose we are given a set W of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula @f. We then consider the classification problem of determining in the limit and almost always correctly whether a possible world M satisfies @f, from a complete enumeration of the possible data that are true in M. One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, with respect to some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set W^' of possible worlds of measure 1, without having to produce any claim in the limit on the truth of @f for the members of the complement of W^' in W. We compare these notions with absolute classification of W with respect to a formula that is almost always equivalent to @f in W, hence we investigate whether the set of possible worlds on which the classification is correct is definable. We mainly work with the probability distribution that corresponds to the standard measure on the Cantor space, but we also consider an alternative probability distribution proposed by Solomonoff and contrast it with the former. Finally, in the spirit of the kind of computations considered in Logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas.
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.
17397415
Analyzing the supply chain for a large logistics operation using simulation
This paper presents a case study of using simulation for analyzing the impact of proposed changes in the supply chain processes for a large logistics operation. The major changes explored include business process changes, and use of new supply chain software. The results of the analysis indicate that the changes in forecast accuracy provide much larger savings compared to process automation changes. A number of insights are drawn from the results of the analyses.
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.
1408878
Distributed simulation for interoperability testing along the supply chain
The need for interoperability of information systems among supply chain partners has been recognized. A number of standards have been or are being developed to ensure interoperability of applications used along the supply chain. An associated need for interoperability testing has emerged. There is a need to evaluate compliance of applications to standards across specific platforms. The standards themselves need to be evaluated for a comprehensive coverage of the application scope (validation testing). This paper reports on a distributed simulation based approach for supply chain interoperability testing. Simulations are used to represent real life organizations to serve as sources and consumers of dynamic data. The data can be encapsulated per the standard under consideration and exchanged with other organizations directly or through selected applications for testing. Error free performance of the simulated systems over time will provide confidence in the interoperability of applications and in the standards themselves.
6467955
Low degree metabolites explain essential reactions and enhance modularity in biological networks
BackgroundRecently there has been a lot of interest in identifying modules at the level of genetic and metabolic networks of organisms, as well as in identifying single genes and reactions that are essential for the organism. A goal of computational and systems biology is to go beyond identification towards an explanation of specific modules and essential genes and reactions in terms of specific structural or evolutionary constraints.ResultsIn the metabolic networks of Escherichia coli, Saccharomyces cerevisiae and Staphylococcus aureus, we identified metabolites with a low degree of connectivity, particularly those that are produced and/or consumed in just a single reaction. Using flux balance analysis (FBA) we also determined reactions essential for growth in these metabolic networks. We find that most reactions identified as essential in these networks turn out to be those involving the production or consumption of low degree metabolites. Applying graph theoretic methods to these metabolic networks, we identified connected clusters of these low degree metabolites. The genes involved in several operons in E. coli are correctly predicted as those of enzymes catalyzing the reactions of these clusters. Furthermore, we find that larger sized clusters are over-represented in the real network and are analogous to a 'network motif. Using FBA for the above mentioned three organisms we independently identified clusters of reactions whose fluxes are perfectly correlated. We find that the composition of the latter 'functional clusters' is also largely explained in terms of clusters of low degree metabolites in each of these organisms.ConclusionOur findings mean that most metabolic reactions that are essential can be tagged by one or more low degree metabolites. Those reactions are essential because they are the only ways of producing or consuming their respective tagged metabolites. Furthermore, reactions whose fluxes are strongly correlated can be thought of as 'glued together' by these low degree metabolites. The methods developed here could be used in predicting essential reactions and metabolic modules in other organisms from the list of metabolic reactions.
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.