Search

Abstract: Given an edge-weighted transportation network G and a list of transportation requests L, the Stacker Crane Problem is to find a minimum-cost tour for a server along the edges of G that serves all requests. The server has capacity one, and starts and stops at the same vertex. In this paper, we consider the case that the transportation network G is a tree, and that the requests are chosen randomly according to a certain class of probability distributions. We show that a polynomial time algorithm by Frederickson and Guan [J. Algorithms 15 (1993) 29–60], which guarantees a 4/3-approximation in the worst case, on almost all inputs finds a minimum-cost tour, along with a certificate of the optimality of its output. [Copyright &y& Elsevier]

Abstract: This paper is devoted to the estimation of stochastic context-free grammars (SCFGs) and their use as language models. Classical estimation algorithms, together with new ones that consider a certain subset of derivations in the estimation process, are presented in a unified framework. This set of derivations is chosen according to both structural and statistical criteria. The estimated SCFGs have been used in a new hybrid language model to combine both a word-based n-gram, which is used to capture the local relations between words, and a category-based SCFG together with a word distribution into categories, which is defined to represent the long-term relations between these categories. We describe methods for learning these stochastic models for complex tasks, and we present an algorithm for computing the word transition probability using this hybrid language model. Finally, experiments on the UPenn Treebank corpus show significant improvements in the test set perplexity with regard to the classical word trigram models. [Copyright &y& Elsevier]

In many cases Bayes' theorem is an appropriate algorithm for the aggregation of probabilistic evidence. As with other statistical procedures, there are restrictions that must be taken into account. In the present paper we shall comment on several approaches that have been devoted to one of these restrictions; the incorporation of uncertainty about the true state of a datum. A datum is a variable which can be partitioned into equivalence classes. These classes represent the possible data states which will be also called events. In Bayes' theorem an event is an item of information which will be used for revising the opinion about the relative likelihood of hypotheses. In any specific situation only one of the possible events will be the true event. An event may come from a source whose reporting or observational accuracy is not perfect. An example may illustrate the issue. A medical doctor wants to come to a diagnosis. To achieve this he considers several data. One datum might be the result of a medical test, which has three possible states: positive, negative, inconclusive. If the doctor reports the state of the datum to be positive, he may be wrong by whatever reasons. That is, the report of an event must not necessarily coincide with the actual or true event of the datum under consideration. This kind of uncertainty about the true event in any specific situation is a characteristic of the source. In most cases it will reduce the diagnostic impact of an event. Whenever the report of an event and the true event coincide imperfectly, measures of source inaccuracy must be incorporated into Bayes' theorem. The task can be considered as two stage probabilistic induction. The first step is induction from the reported to the actual event, the second is induction from the actual event to the creditation of hypotheses. This is the reason why Gettys and Willke (1969) speak about "cascaded inference." [ABSTRACT FROM AUTHOR]

This paper discusses the application of Bayes's theorem to those cases where the true state of the world is not known with certainty. An algorithm is proposed that relaxes the requirement of Bayes's theorem that the true data state be known with certainty by postulating a true but unobservable elementary event, ω, which gives rise to posterior probabilities which reflect the uncertainty of the data. A derivation is presented for the calculation of Bayesian posterior probabilities which uses as its input these probabilities, rather than the true event, o, which is assumed to be unavailable. Suggestions are made as to the application of this modification of Bayes's theorem to cascaded inference processes. [ABSTRACT FROM AUTHOR]