title: Increased mode instability thresholds of fiber amplifiers by gain saturation

abstract: We show by numerical modeling that saturation of the population inversion reduces the stimulated thermal Rayleigh gain relative to the laser gain in large mode area fiber amplifiers. We show how to exploit this effect to raise mode instability thresholds by a substantial factor. We also demonstrate that when suppression of stimulated Brillouin scattering and the population saturation effect are both taken into account, counter-pumped amplifiers have higher mode instability thresholds than co-pumped amplifiers for fully Yb$^{3+}$ doped cores, and confined doping can further raise the thresholds.


title: Lepton flavor mixing in the Wolfenstein scheme

abstract: We mimic the Wolfenstein scheme of quark flavor mixing to describe neutrino oscillations in the standard model. We identify the parameter $\lambda$ with the experimentally measured value of the mixing element responsible for atmospheric neutrino oscillations. The matrix elements responsible for solar neutrino oscillations and the Chooz angle are taken to be proportional to $\lambda^2$ and $\lambda^3$, respectively. Using present world average data on neutrinos, we derive bounds on the other parameters $A$, $\rho$, and $\eta$, of the new scheme.


title: An Improved LR-aided K-Best Algorithm for MIMO Detection

abstract: Recently, lattice reduction (LR) technique has caught great attention for multi-input multi-output (MIMO) receiver because of its low complexity and high performance. However, when the number of antennas is large, LR-aided linear detectors and successive interference cancellation (SIC) detectors still exhibit considerable performance gap to the optimal maximum likelihood detector (MLD). To enhance the performance of the LR-aided detectors, the LR-aided K-best algorithm was developed at the cost of the extra complexity on the order $\mathcal{O}(N_t^2 K + N_t K^2)$, where $N_t$ is the number of transmit antennas and $K$ is the number of candidates. In this paper, we develop an LR-aided K-best algorithm with lower complexity by exploiting a priority queue. With the aid of the priority queue, our analysis shows that the complexity of the LR-aided K-best algorithm can be further reduced to $\mathcal{O}(N_t^2 K + N_t K {\rm log}_2(K))$. The low complexity of the proposed LR-aided K-best algorithm allows us to perform the algorithm for large MIMO systems (e.g., 50x50 MIMO systems) with large candidate sizes. Simulations show that as the number of antennas increases, the error performance approaches that of AWGN channel.


title: Collective allocation of science funding: from funding agencies to scientific agency

abstract: Public agencies like the U.S. National Science Foundation (NSF) and the National Institutes of Health (NIH) award tens of billions of dollars in annual science funding. How can this money be distributed as efficiently as possible to best promote scientific innovation and productivity? The present system relies primarily on peer review of project proposals. In 2010 alone, NSF convened more than 15,000 scientists to review 55,542 proposals. Although considered the scientific gold standard, peer review requires significant overhead costs, and may be subject to biases, inconsistencies, and oversights. We investigate a class of funding models in which all participants receive an equal portion of yearly funding, but are then required to anonymously donate a fraction of their funding to peers. The funding thus flows from one participant to the next, each acting as if he or she were a funding agency themselves. Here we show through a simulation conducted over large-scale citation data (37M articles, 770M citations) that such a distributed system for science may yield funding patterns similar to existing NIH and NSF distributions, but may do so at much lower overhead while exhibiting a range of other desirable features. Self-correcting mechanisms in scientific peer evaluation can yield an efficient and fair distribution of funding. The proposed model can be applied in many situations in which top-down or bottom-up allocation of public resources is either impractical or undesirable, e.g. public investments, distribution chains, and shared resource management.


title: Nanometer scale quantum thermometry in a living cell

abstract: Sensitive probing of temperature variations on nanometer scales represents an outstanding challenge in many areas of modern science and technology. In particular, a thermometer capable of sub-degree temperature resolution as well as integration within a living system could provide a powerful new tool for many areas of biological research, including temperature-induced control of gene expression and cell-selective treatment of disease. Here, we demonstrate a new approach to nanoscale thermometry that utilizes coherent manipulation of the electronic spin associated with nitrogen-vacancy (NV) color centers in diamond. We show the ability to detect temperature variations down to 1.8 mK (sensitivity of 9 mK/sqrt(Hz)) in an ultra-pure bulk diamond sample. Using NV centers in diamond nanocrystals (nanodiamonds), we directly measure the local thermal environment at length scales down to 200 nm. Finally, by introducing both nanodiamonds and gold nanoparticles into a single human embryonic fibroblast, we demonstrate temperature-gradient control and mapping at the sub-cellular level, enabling unique potential applications in life sciences.


title: The C0 general density theorem for geodesic flows

abstract: Given a closed Riemannian manifold, we prove the C0-general density theorem for continuous geodesic flows. More precisely, that there exists a residual (in the C0-sense) subset of the continuous geodesic flows such that, in that residual subset, the geodesic flow exhibits dense closed orbits.


title: Differential operators on non-commutative algebras

abstract: There is a relatively well-known description of the algebra of (higher order) left differential operators on commutative algebras. This note gives a construction of similar flavor for algebras of differential operators on not necessarily commutative algebras.


title: Alternating knots, planar graphs and q-series

abstract: Recent advances in Quantum Topology assign $q$-series to knots in at least three different ways. The $q$-series are given by generalized Nahm sums (i.e., special $q$-hypergeometric sums) and have unknown modular and asymptotic properties. We give an efficient method to compute those $q$-series that come from planar graphs (i.e., reduced Tait graphs of alternating links) and compute several terms of those series for all graphs with at most 8 edges drawing several conclusions. In addition, we give a graph-theory proof of a theorem of Dasbach-Lin which identifies the coefficient of $q^k$ in those series for $k=0,1,2$ in terms of polynomials on the number of vertices, edges and triangles of the graph. Updated tables of data.


title: Massively Parallel RNA Chemical Mapping with a Reduced Bias MAP-seq Protocol

abstract: Chemical mapping methods probe RNA structure by revealing and leveraging correlations of a nucleotide's structural accessibility or flexibility with its reactivity to various chemical probes. Pioneering work by Lucks and colleagues has expanded this method to probe hundreds of molecules at once on an Illumina sequencing platform, obviating the use of slab gels or capillary electrophoresis on one molecule at a time. Here, we describe optimizations to this method from our lab, resulting in the MAP-seq protocol (Multiplexed Accessibility Probing read out through sequencing), version 1.0. The protocol permits the quantitative probing of thousands of RNAs at once, by several chemical modification reagents, on the time scale of a day using a table-top Illumina machine. This method and a software package MAPseeker (http://simtk.org/home/map_seeker) address several potential sources of bias, by eliminating PCR steps, improving ligation efficiencies of ssDNA adapters, and avoiding problematic heuristics in prior algorithms. We hope that the step-by-step description of MAP-seq 1.0 will help other RNA mapping laboratories to transition from electrophoretic to next-generation sequencing methods and to further reduce the turnaround time and any remaining biases of the protocol.


title: A New Theorem on N-th Order Differential Equation with Retarded Argument

abstract: In this work, using the well-known mean-value theorem (Lagrange's theorem) we obtain an inequality for n-th order differential equations with retarded argument. If the retarded argument vanishes then the inequality turns to an inequality for n-th order ordinary differential equations which plays a vital role in the proof of existence theorem for n-th order ordinary differential equations.


title: Kolmogorov's strong law of large numbers in game-theoretic probability: Reality's side

abstract: The game-theoretic version of Kolmogorov's strong law of large numbers says that Skeptic has a strategy forcing the statement of the law in a game of prediction involving Reality, Forecaster, and Skeptic. This note describes a simple matching strategy for Reality.


title: The core of games on ordered structures and graphs

abstract: In cooperative games, the core is the most popular solution concept, and its properties are well known. In the classical setting of cooperative games, it is generally assumed that all coalitions can form, i.e., they are all feasible. In many situations, this assumption is too strong and one has to deal with some unfeasible coalitions. Defining a game on a subcollection of the power set of the set of players has many implications on the mathematical structure of the core, depending on the precise structure of the subcollection of feasible coalitions. Many authors have contributed to this topic, and we give a unified view of these different results.


title: Pure spinors, intrinsic torsion and curvature in odd dimensions

abstract: We study the geometric properties of a $(2m+1)$-dimensional complex manifold $\mathcal{M}$ admitting a holomorphic reduction of the frame bundle to the structure group $P \subset \mathrm{Spin}(2m+1,\mathbb{C})$, the stabiliser of the line spanned by a pure spinor at a point. Geometrically, $\mathcal{M}$ is endowed with a holomorphic metric $g$, a holomorphic volume form, a spin structure compatible with $g$, and a holomorphic pure spinor field $\xi$ up to scale. The defining property of $\xi$ is that it determines an almost null structure, i.e.\ an $m$-plane distribution $\mathcal{N}_\xi$ along which $g$ is totally degenerate. We develop a spinor calculus, by means of which we encode the geometric properties of $\mathcal{N}_\xi$ and of its rank-$(m+1)$ orthogonal complement $\mathcal{N}_\xi^\perp$ corresponding to the algebraic properties of the intrinsic torsion of the $P$-structure. This is the failure of the Levi-Civita connection $\nabla$ of $g$ to be compatible with the $P$-structure. In a similar way, we examine the algebraic properties of the curvature of $\nabla$. Applications to spinorial differential equations are given. Notably, we relate the integrability properties of $\mathcal{N}_\xi$ and $\mathcal{N}_\xi^\perp$ to the existence of solutions of odd-dimensional versions of the zero-rest-mass field equation. We give necessary and sufficient conditions for the almost null structure associated to a pure conformal Killing spinor to be integrable. Finally, we conjecture a Goldberg--Sachs-type theorem on the existence of a certain class of almost null structures when $(\mathcal{M},g)$ has prescribed curvature. We discuss applications of this work to the study of real pseudo-Riemannian manifolds.


title: Softly Constrained Films

abstract: The shape of materials is often subject to a number of geometric constraints that limit the size of the system or fix the structure of its boundary. In soft and biological materials, however, these constraints are not always hard, but are due to other physical mechanisms that affect the overall force balance. A capillary film spanning a flexible piece of wire or a cell anchored to a compliant substrate by mean of adhesive contacts are examples of these softly constrained systems in the macroscopic and microscopic world. In this article I review some of the important mathematical and physical developments that contributed to our understanding of shape formation in softly constrained films and their recent application to the mechanics of adherent cells.


title: Loops and spurs: The angular power spectrum of the Galactic synchrotron background

abstract: We present a new model of the diffuse Galactic synchrotron radiation, concentrating on its angular anisotropies. While previous studies have focussed on either the variation of the emissivity on large (kpc) scales, or on fluctuations due to MHD turbulence in the interstellar medium, we unify these approaches to match the angular power spectrum. We note that the usual turbulence cascade calculation ignores spatial correlations at the injection scale due to compression of the interstellar medium by old supernova remnants -- the 'radio loops', only four of which are visible by eye in radio maps. This new component naturally provides the otherwise missing power on intermediate and small scales in the all-sky map at 408 MHz. Our model can enable more reliable subtraction of the synchrotron foreground for studies of CMB anisotropies (both in temperature and polarisation) or searches for dark matter annihilation. We conclude with some remarks on the relevance to modelling of the polarised foreground.


title: Covariant Renormalizable Modified and Massive Gravity Theories on (Non) Commutative Tangent Lorentz Bundles

abstract: The fundamental field equations in modified gravity (including general relativity; massive and bimetric theories; Ho\vrava-Lifshits, HL; Einstein--Finsler gravity extensions etc) posses an important decoupling property with respect to nonholonomic frames with 2 (or 3) +2+2+... spacetime decompositions. This allows us to construct exact solutions with generic off--diagonal metrics depending on all spacetime coordinates via generating and integration functions containing (un-) broken symmetry parameters. Such nonholonomic configurations/ models have a nice ultraviolet behavior and seem to be ghost free and (super) renormalizable in a sense of covariant and/or massive modifications of HL gravity. The apparent noncommutativity and breaking of Lorentz invariance by quantum effects can be encoded into fibers of noncommutative tangent Lorentz bundles for corresponding "partner" anisotropically induced theories. We show how the constructions can be extended to include conjectured covariant reonormalizable models with massive graviton fields and effective Einstein fields with (non)commutative variables.


title: Off-Diagonal Ekpyrotic Scenarios and Equivalence of Modified, Massive and/or Einstein Gravity

abstract: Using our anholonomic frame deformation method, we show how generic off-diagonal cosmological solutions depending, in general, on all spacetime coordinates and undergoing a phase of ultra-slow contraction can be constructed in massive gravity. In this paper, there are found and studied new classes of locally anisotropic and (in) homogeneous cosmological metrics with open and closed spatial geometries. The late time acceleration is present due to effective cosmological terms induced by nonlinear off-diagonal interactions and graviton mass. The off-diagonal cosmological metrics and related St\" uckelberg fields are constructed in explicit form up to nonholonomic frame transforms of the Friedmann-Lama\^itre-Robertson-Walker (FLRW) coordinates. We show that the solutions include matter, graviton mass and other effective sources modelling nonlinear gravitational and matter fields interactions in modified and/or massive gravity, with polarization of physical constants and deformations of metrics, which may explain certain dark energy and dark matter effects. There are stated and analyzed the conditions when such configurations mimic interesting solutions in general relativity and modifications and recast the general Painlev\'e--ullstrand and FLRW metrics. Finally, we elaborate on a reconstruction procedure for a subclass of off-diagonal cosmological solutions which describe cyclic and ekpyrotic universes, with an emphasis on open issues and observable signatures.


title: Exploiting Functional Dependencies in Qualitative Probabilistic Reasoning

abstract: Functional dependencies restrict the potential interactions among variables connected in a probabilistic network. This restriction can be exploited in qualitative probabilistic reasoning by introducing deterministic variables and modifying the inference rules to produce stronger conclusions in the presence of functional relations. I describe how to accomplish these modifications in qualitative probabilistic networks by exhibiting the update procedures for graphical transformations involving probabilistic and deterministic variables and combinations. A simple example demonstrates that the augmented scheme can reduce qualitative ambiguity that would arise without the special treatment of functional dependency. Analysis of qualitative synergy reveals that new higher-order relations are required to reason effectively about synergistic interactions among deterministic variables.


title: Qualitative Propagation and Scenario-based Explanation of Probabilistic Reasoning

abstract: Comprehensible explanations of probabilistic reasoning are a prerequisite for wider acceptance of Bayesian methods in expert systems and decision support systems. A study of human reasoning under uncertainty suggests two different strategies for explaining probabilistic reasoning: The first, qualitative belief propagation, traces the qualitative effect of evidence through a belief network from one variable to the next. This propagation algorithm is an alternative to the graph reduction algorithms of Wellman (1988) for inference in qualitative probabilistic networks. It is based on a qualitative analysis of intercausal reasoning, which is a generalization of Pearl's "explaining away", and an alternative to Wellman's definition of qualitative synergy. The other, Scenario-based reasoning, involves the generation of alternative causal "stories" accounting for the evidence. Comparing a few of the most probable scenarios provides an approximate way to explain the results of probabilistic reasoning. Both schemes employ causal as well as probabilistic knowledge. Probabilities may be presented as phrases and/or numbers. Users can control the style, abstraction and completeness of explanations.


title: Managing Uncertainty in Rule Based Cognitive Models

abstract: An experiment replicated and extended recent findings on psychologically realistic ways of modeling propagation of uncertainty in rule based reasoning. Within a single production rule, the antecedent evidence can be summarized by taking the maximum of disjunctively connected antecedents and the minimum of conjunctively connected antecedents. The maximum certainty factor attached to each of the rule's conclusions can be sealed down by multiplication with this summarized antecedent certainty. Heckerman's modified certainty factor technique can be used to combine certainties for common conclusions across production rules.


title: Context-Dependent Similarity

abstract: Attribute weighting and differential weighting, two major mechanisms for computing context-dependent similarity or dissimilarity measures are studied and compared. A dissimilarity measure based on subset size in the context is proposed and its metrization and application are given. It is also shown that while all attribute weighting dissimilarity measures are metrics differential weighting dissimilarity measures are usually non-metric.


title: Similarity Networks for the Construction of Multiple-Faults Belief Networks

abstract: A similarity network is a tool for constructing belief networks for the diagnosis of a single fault. In this paper, we examine modifications to the similarity-network representation that facilitate the construction of belief networks for the diagnosis of multiple coexisting faults.


title: Integrating Probabilistic, Taxonomic and Causal Knowledge in Abductive Diagnosis

abstract: We propose an abductive diagnosis theory that integrates probabilistic, causal and taxonomic knowledge. Probabilistic knowledge allows us to select the most likely explanation; causal knowledge allows us to make reasonable independence assumptions; taxonomic knowledge allows causation to be modeled at different levels of detail, and allows observations be described in different levels of precision. Unlike most other approaches where a causal explanation is a hypothesis that one or more causative events occurred, we define an explanation of a set of observations to be an occurrence of a chain of causation events. These causation events constitute a scenario where all the observations are true. We show that the probabilities of the scenarios can be computed from the conditional probabilities of the causation events. Abductive reasoning is inherently complex even if only modest expressive power is allowed. However, our abduction algorithm is exponential only in the number of observations to be explained, and is polynomial in the size of the knowledge base. This contrasts with many other abduction procedures that are exponential in the size of the knowledge base.


title: What is an Optimal Diagnosis?

abstract: Within diagnostic reasoning there have been a number of proposed definitions of a diagnosis, and thus of the most likely diagnosis, including most probable posterior hypothesis, most probable interpretation, most probable covering hypothesis, etc. Most of these approaches assume that the most likely diagnosis must be computed, and that a definition of what should be computed can be made a priori, independent of what the diagnosis is used for. We argue that the diagnostic problem, as currently posed, is incomplete: it does not consider how the diagnosis is to be used, or the utility associated with the treatment of the abnormalities. In this paper we analyze several well-known definitions of diagnosis, showing that the different definitions of the most likely diagnosis have different qualitative meanings, even given the same input data. We argue that the most appropriate definition of (optimal) diagnosis needs to take into account the utility of outcomes and what the diagnosis is used for.


title: Kutato: An Entropy-Driven System for Construction of Probabilistic Expert Systems from Databases

abstract: Kutato is a system that takes as input a database of cases and produces a belief network that captures many of the dependence relations represented by those data. This system incorporates a module for determining the entropy of a belief network and a module for constructing belief networks based on entropy calculations. Kutato constructs an initial belief network in which all variables in the database are assumed to be marginally independent. The entropy of this belief network is calculated, and that arc is added that minimizes the entropy of the resulting belief network. Conditional probabilities for an arc are obtained directly from the database. This process continues until an entropy-based threshold is reached. We have tested the system by generating databases from networks using the probabilistic logic-sampling method, and then using those databases as input to Kutato. The system consistently reproduces the original belief networks with high fidelity.


title: Ideal Reformulation of Belief Networks

abstract: The intelligent reformulation or restructuring of a belief network can greatly increase the efficiency of inference. However, time expended for reformulation is not available for performing inference. Thus, under time pressure, there is a tradeoff between the time dedicated to reformulating the network and the time applied to the implementation of a solution. We investigate this partition of resources into time applied to reformulation and time used for inference. We shall describe first general principles for computing the ideal partition of resources under uncertainty. These principles have applicability to a wide variety of problems that can be divided into interdependent phases of problem solving. After, we shall present results of our empirical study of the problem of determining the ideal amount of time to devote to searching for clusters in belief networks. In this work, we acquired and made use of probability distributions that characterize (1) the performance of alternative heuristic search methods for reformulating a network instance into a set of cliques, and (2) the time for executing inference procedures on various belief networks. Given a preference model describing the value of a solution as a function of the delay required for its computation, the system selects an ideal time to devote to reformulation.


title: Computationally-Optimal Real-Resource Strategies

abstract: This paper focuses on managing the cost of deliberation before action. In many problems, the overall quality of the solution reflects costs incurred and resources consumed in deliberation as well as the cost and benefit of execution, when both the resource consumption in deliberation phase, and the costs in deliberation and execution are uncertain and may be described by probability distribution functions. A feasible (in terms of resource consumption) strategy that minimizes the expected total cost is termed computationally-optimal. For a situation with several independent, uninterruptible methods to solve the problem, we develop a pseudopolynomial-time algorithm to construct generate-and-test computationally optimal strategy. We show this strategy-construction problem to be NP-complete, and apply Bellman's Optimality Principle to solve it efficiently.


title: Problem Formulation as the Reduction of a Decision Model

abstract: In this paper, we extend the QMRDT probabilistic model for the domain of internal medicine to include decisions about treatments. In addition, we describe how we can use the comprehensive decision model to construct a simpler decision model for a specific patient. In so doing, we transform the task of problem formulation to that of narrowing of a larger problem.


title: Dynamic Construction of Belief Networks

abstract: We describe a method for incrementally constructing belief networks. We have developed a network-construction language similar to a forward-chaining language using data dependencies, but with additional features for specifying distributions. Using this language, we can define parameterized classes of probabilistic models. These parameterized models make it possible to apply probabilistic reasoning to problems for which it is impractical to have a single large static model.


title: A New Algorithm for Finding MAP Assignments to Belief Networks

abstract: We present a new algorithm for finding maximum a-posterior) (MAP) assignments of values to belief networks. The belief network is compiled into a network consisting only of nodes with boolean (i.e. only 0 or 1) conditional probabilities. The MAP assignment is then found using a best-first search on the resulting network. We argue that, as one would anticipate, the algorithm is exponential for the general case, but only linear in the size of the network for poly trees.


title: Reducing Uncertainty in Navigation and Exploration

abstract: A significant problem in designing mobile robot control systems involves coping with the uncertainty that arises in moving about in an unknown or partially unknown environment and relying on noisy or ambiguous sensor data to acquire knowledge about that environment. We describe a control system that chooses what activity to engage in next on the basis of expectations about how the information re- turned as a result of a given activity will improve 2 its knowledge about the spatial layout of its environment. Certain of the higher-level components of the control system are specified in terms of probabilistic decision models whose output is used to mediate the behavior of lower-level control components responsible for movement and sensing.


title: Ergo: A Graphical Environment for Constructing Bayesian

abstract: We describe an environment that considerably simplifies the process of generating Bayesian belief networks. The system has been implemented on readily available, inexpensive hardware, and provides clarity and high performance. We present an introduction to Bayesian belief networks, discuss algorithms for inference with these networks, and delineate the classes of problems that can be solved with this paradigm. We then describe the hardware and software that constitute the system, and illustrate Ergo's use with several example


title: Decision Making with Interval Influence Diagrams

abstract: In previous work (Fertig and Breese, 1989; Fertig and Breese, 1990) we defined a mechanism for performing probabilistic reasoning in influence diagrams using interval rather than point-valued probabilities. In this paper we extend these procedures to incorporate decision nodes and interval-valued value functions in the diagram. We derive the procedures for chance node removal (calculating expected value) and decision node removal (optimization) in influence diagrams where lower bounds on probabilities are stored at each chance node and interval bounds are stored on the value function associated with the diagram's value node. The output of the algorithm are a set of admissible alternatives for each decision variable and a set of bounds on expected value based on the imprecision in the input. The procedure can be viewed as an approximation to a full e-dimensional sensitivity analysis where n are the number of imprecise probability distributions in the input. We show the transformations are optimal and sound. The performance of the algorithm on an influence diagrams is investigated and compared to an exact algorithm.


title: A Randomized Approximation Algorithm of Logic Sampling

abstract: In recent years, researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build models of expert opinion. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of exact probabilistic inference on belief networks almost certainly requires exponential computation in the worst ease [3]. We have previously described a randomized approximation scheme, called BN-RAS, for computation on belief networks [ 1, 2, 4]. We gave precise analytic bounds on the convergence of BN-RAS and showed how to trade running time for accuracy in the evaluation of posterior marginal probabilities. We now extend our previous results and demonstrate the generality of our framework by applying similar mathematical techniques to the analysis of convergence for logic sampling [7], an alternative simulation algorithm for probabilistic inference.


title: Occupancy Grids: A Stochastic Spatial Representation for Active Robot Perception

abstract: In this paper we provide an overview of a new framework for robot perception, real-world modelling, and navigation that uses a stochastic tesselated representation of spatial information called the Occupancy Grid. The Occupancy Grid is a multi-dimensional random field model that maintains probabilistic estimates of the occupancy state of each cell in a spatial lattice. Bayesian estimation mechanisms employing stochastic sensor models allow incremental updating of the Occupancy Grid using multi-view, multi-sensor data, composition of multiple maps, decision-making, and incorporation of robot and sensor position uncertainty. We present the underlying stochastic formulation of the Occupancy Grid framework, and discuss its application to a variety of robotic tusks. These include range-based mapping, multi-sensor integration, path-planning and obstacle avoidance, handling of robot position uncertainty, incorporation of pre-compiled maps, recovery of geometric representations, and other related problems. The experimental results show that the Occupancy Grid approach generates dense world models, is robust under sensor uncertainty and errors, and allows explicit handling of uncertainty. It supports the development of robust and agile sensor interpretation methods, incremental discovery procedures, and composition of information from multiple sources. Furthermore, the results illustrate that robotic tasks can be addressed through operations performed di- rectly on the Occupancy Grid, and that these operations have strong parallels to operations performed in the image processing domain.


title: Time, Chance, and Action

abstract: To operate intelligently in the world, an agent must reason about its actions. The consequences of an action are a function of both the state of the world and the action itself. Many aspects of the world are inherently stochastic, so a representation for reasoning about actions must be able to express chances of world states as well as indeterminacy in the effects of actions and other events. This paper presents a propositional temporal probability logic for representing and reasoning about actions. The logic can represent the probability that facts hold and events occur at various times. It can represent the probability that actions and other events affect the future. It can represent concurrent actions and conditions that hold or change during execution of an action. The model of probability relates probabilities over time. The logical language integrates both modal and probabilistic constructs and can thus represent and distinguish between possibility, probability, and truth. Several examples illustrating the use of the logic are given.


title: A Dynamic Approach to Probabilistic Inference

abstract: In this paper we present a framework for dynamically constructing Bayesian networks. We introduce the notion of a background knowledge base of schemata, which is a collection of parameterized conditional probability statements. These schemata explicitly separate the general knowledge of properties an individual may have from the specific knowledge of particular individuals that may have these properties. Knowledge of individuals can be combined with this background knowledge to create Bayesian networks, which can then be used in any propagation scheme. We discuss the theory and assumptions necessary for the implementation of dynamic Bayesian networks, and indicate where our approach may be useful.


title: Approximations in Bayesian Belief Universe for Knowledge Based Systems

abstract: When expert systems based on causal probabilistic networks (CPNs) reach a certain size and complexity, the "combinatorial explosion monster" tends to be present. We propose an approximation scheme that identifies rarely occurring cases and excludes these from being processed as ordinary cases in a CPN-based expert system. Depending on the topology and the probability distributions of the CPN, the numbers (representing probabilities of state combinations) in the underlying numerical representation can become very small. Annihilating these numbers and utilizing the resulting sparseness through data structuring techniques often results in several orders of magnitude of improvement in the consumption of computer resources. Bounds on the errors introduced into a CPN-based expert system through approximations are established. Finally, reports on empirical studies of applying the approximation scheme to a real-world CPN are given.


title: Robust Inference Policies

abstract: A series of monte carlo studies were performed to assess the extent to which different inference procedures robustly output reasonable belief values in the context of increasing levels of judgmental imprecision. It was found that, when compared to an equal-weights linear model, the Bayesian procedures are more likely to deduce strong support for a hypothesis. But, the Bayesian procedures are also more likely to strongly support the wrong hypothesis. Bayesian techniques are more powerful, but are also more error prone.


title: Minimum Error Tree Decomposition

abstract: This paper describes a generalization of previous methods for constructing tree-structured belief network with hidden variables. The major new feature of the described method is the ability to produce a tree decomposition even when there are errors in the correlation data among the input variables. This is an important extension of existing methods since the correlational coefficients usually cannot be measured with precision. The technique involves using a greedy search algorithm that locally minimizes an error function.


title: A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints

abstract: A method of calculating probability values from a system of marginal constraints is presented. Previous systems for finding the probability of a single attribute have either made an independence assumption concerning the evidence or have required, in the worst case, time exponential in the number of attributes of the system. In this paper a closed form solution to the probability of an attribute given the evidence is found. The closed form solution, however does not enforce the (non-linear) constraint that all terms in the underlying distribution be positive. The equation requires O(r^3) steps to evaluate, where r is the number of independent marginal constraints describing the system at the time of evaluation. Furthermore, a marginal constraint may be exchanged with a new constraint, and a new solution calculated in O(r^2) steps. This method is appropriate for calculating probabilities in a real time expert system


title: Computation of Variances in Causal Networks

abstract: The causal (belief) network is a well-known graphical structure for representing independencies in a joint probability distribution. The exact methods and the approximation methods, which perform probabilistic inference in causal networks, often treat the conditional probabilities which are stored in the network as certain values. However, if one takes either a subjectivistic or a limiting frequency approach to probability, one can never be certain of probability values. An algorithm for probabilistic inference should not only be capable of reporting the inferred probabilities; it should also be capable of reporting the uncertainty in these probabilities relative to the uncertainty in the probabilities which are stored in the network. In section 2 of this paper a method is given for determining the prior variances of the probabilities of all the nodes. Section 3 contains an approximation method for determining the variances in inferred probabilities.


title: A Sensitivity Analysis of Pathfinder

abstract: Knowledge elicitation is one of the major bottlenecks in expert system design. Systems based on Bayes nets require two types of information--network structure and parameters (or probabilities). Both must be elicited from the domain expert. In general, parameters have greater opacity than structure, and more time is spent in their refinement than in any other phase of elicitation. Thus, it is important to determine the point of diminishing returns, beyond which further refinements will promise little (if any) improvement. Sensitivity analyses address precisely this issue--the sensitivity of a model to the precision of its parameters. In this paper, we report the results of a sensitivity analysis of Pathfinder, a Bayes net based system for diagnosing pathologies of the lymph system. This analysis is intended to shed some light on the relative importance of structure and parameters to system performance, as well as the sensitivity of a system based on a Bayes net to noise in its assessed parameters.


title: IDEAL: A Software Package for Analysis of Influence Diagrams

abstract: IDEAL (Influence Diagram Evaluation and Analysis in Lisp) is a software environment for creation and evaluation of belief networks and influence diagrams. IDEAL is primarily a research tool and provides an implementation of many of the latest developments in belief network and influence diagram evaluation in a unified framework. This paper describes IDEAL and some lessons learned during its development.


title: On the Equivalence of Causal Models

abstract: Scientists often use directed acyclic graphs (days) to model the qualitative structure of causal theories, allowing the parameters to be estimated from observational data. Two causal models are equivalent if there is no experiment which could distinguish one from the other. A canonical representation for causal models is presented which yields an efficient graphical criterion for deciding equivalence, and provides a theoretical basis for extracting causal structures from empirical data. This representation is then extended to the more general case of an embedded causal model, that is, a dag in which only a subset of the variables are observable. The canonical representation presented here yields an efficient algorithm for determining when two embedded causal models reflect the same dependency information. This algorithm leads to a model theoretic definition of causation in terms of statistical dependencies.


title: Application of Confidence Intervals to the Autonomous Acquisition of High-level Spatial Knowledge

abstract: Objects in the world usually appear in context, participating in spatial relationships and interactions that are predictable and expected. Knowledge of these contexts can be used in the task of using a mobile camera to search for a specified object in a room. We call this the object search task. This paper is concerned with representing this knowledge in a manner facilitating its application to object search while at the same time lending itself to autonomous learning by a robot. The ability for the robot to learn such knowledge without supervision is crucial due to the vast number of possible relationships that can exist for any given set of objects. Moreover, since a robot will not have an infinite amount of time to learn, it must be able to determine an order in which to look for possible relationships so as to maximize the rate at which new knowledge is gained. In effect, there must be a "focus of interest" operator that allows the robot to choose which examples are likely to convey the most new information and should be examined first. This paper demonstrates how a representation based on statistical confidence intervals allows the construction of a system that achieves the above goals. An algorithm, based on the Highest Impact First heuristic, is presented as a means for providing a "focus of interest" with which to control the learning process, and examples are given.


title: Directed Reduction Algorithms and Decomposable Graphs

abstract: In recent years, there have been intense research efforts to develop efficient methods for probabilistic inference in probabilistic influence diagrams or belief networks. Many people have concluded that the best methods are those based on undirected graph structures, and that those methods are inherently superior to those based on node reduction operations on the influence diagram. We show here that these two approaches are essentially the same, since they are explicitly or implicity building and operating on the same underlying graphical structures. In this paper we examine those graphical structures and show how this insight can lead to an improved class of directed reduction methods.


title: Optimal Decomposition of Belief Networks

abstract: In this paper, optimum decomposition of belief networks is discussed. Some methods of decomposition are examined and a new method - the method of Minimum Total Number of States (MTNS) - is proposed. The problem of optimum belief network decomposition under our framework, as under all the other frameworks, is shown to be NP-hard. According to the computational complexity analysis, an algorithm of belief network decomposition is proposed in (Wee, 1990a) based on simulated annealing.


title: Pruning Bayesian Networks for Efficient Computation

abstract: This paper analyzes the circumstances under which Bayesian networks can be pruned in order to reduce computational complexity without altering the computation for variables of interest. Given a problem instance which consists of a query and evidence for a set of nodes in the network, it is possible to delete portions of the network which do not participate in the computation for the query. Savings in computational complexity can be large when the original network is not singly connected. Results analogous to those described in this paper have been derived before [Geiger, Verma, and Pearl 89, Shachter 88] but the implications for reducing complexity of the computations in Bayesian networks have not been stated explicitly. We show how a preprocessing step can be used to prune a Bayesian network prior to using standard algorithms to solve a given problem instance. We also show how our results can be used in a parallel distributed implementation in order to achieve greater savings. We define a computationally equivalent subgraph of a Bayesian network. The algorithm developed in [Geiger, Verma, and Pearl 89] is modified to construct the subgraphs described in this paper with O(e) complexity, where e is the number of edges in the Bayesian network. Finally, we define a minimal computationally equivalent subgraph and prove that the subgraphs described are minimal.


title: On Heuristics for Finding Loop Cutsets in Multiply-Connected Belief Networks

abstract: We introduce a new heuristic algorithm for the problem of finding minimum size loop cutsets in multiply connected belief networks. We compare this algorithm to that proposed in [Suemmondt and Cooper, 1988]. We provide lower bounds on the performance of these algorithms with respect to one another and with respect to optimal. We demonstrate that no heuristic algorithm for this problem cam be guaranteed to produce loop cutsets within a constant difference from optimal. We discuss experimental results based on randomly generated networks, and discuss future work and open questions.


title: A Combination of Cutset Conditioning with Clique-Tree Propagation in the Pathfinder System

abstract: Cutset conditioning and clique-tree propagation are two popular methods for performing exact probabilistic inference in Bayesian belief networks. Cutset conditioning is based on decomposition of a subset of network nodes, whereas clique-tree propagation depends on aggregation of nodes. We describe a means to combine cutset conditioning and clique- tree propagation in an approach called aggregation after decomposition (AD). We discuss the application of the AD method in the Pathfinder system, a medical expert system that offers assistance with diagnosis in hematopathology.


title: Possibility as Similarity: the Semantics of Fuzzy Logic

abstract: This paper addresses fundamental issues on the nature of the concepts and structures of fuzzy logic, focusing, in particular, on the conceptual and functional differences that exist between probabilistic and possibilistic approaches. A semantic model provides the basic framework to define possibilistic structures and concepts by means of a function that quantifies proximity, closeness, or resemblance between pairs of possible worlds. The resulting model is a natural extension, based on multiple conceivability relations, of the modal logic concepts of necessity and possibility. By contrast, chance-oriented probabilistic concepts and structures rely on measures of set extension that quantify the proportion of possible worlds where a proposition is true. Resemblance between possible worlds is quantified by a generalized similarity relation: a function that assigns a number between O and 1 to every pair of possible worlds. Using this similarity relation, which is a form of numerical complement of a classic metric or distance, it is possible to define and interpret the major constructs and methods of fuzzy logic: conditional and unconditioned possibility and necessity distributions and the generalized modus ponens of Zadeh.


title: Integrating Case-Based and Rule-Based Reasoning: the Possibilistic Connection

abstract: Rule based reasoning (RBR) and case based reasoning (CBR) have emerged as two important and complementary reasoning methodologies in artificial intelligence (Al). For problem solving in complex, real world situations, it is useful to integrate RBR and CBR. This paper presents an approach to achieve a compact and seamless integration of RBR and CBR within the base architecture of rules. The paper focuses on the possibilistic nature of the approximate reasoning methodology common to both CBR and RBR. In CBR, the concept of similarity is casted as the complement of the distance between cases. In RBR the transitivity of similarity is the basis for the approximate deductions based on the generalized modus ponens. It is shown that the integration of CBR and RBR is possible without altering the inference engine of RBR. This integration is illustrated in the financial domain of mergers and acquisitions. These ideas have been implemented in a prototype system called MARS.


title: Credibility Discounting in the Theory of Approximate Reasoning

abstract: We are concerned with the problem of introducing credibility type information into reasoning systems. The concept of credibility allows us to discount information provided by agents. An important characteristic of this kind of procedure is that a complete lack of credibility rather than resulting in the negation of the information provided results in the nullification of the information provided. We suggest a representational scheme for credibility qualification in the theory of approximate reasoning. We discuss the concept of relative credibility. By this idea we mean to indicate situations in which the credibility of a piece of evidence is determined by its compatibility with higher priority evidence. This situation leads to structures very much in the spirit of nonmonotonic reasoning.


title: Updating with Belief Functions, Ordinal Conditioning Functions and Possibility Measures

abstract: This paper discusses how a measure of uncertainty representing a state of knowledge can be updated when a new information, which may be pervaded with uncertainty, becomes available. This problem is considered in various framework, namely: Shafer's evidence theory, Zadeh's possibility theory, Spohn's theory of epistemic states. In the two first cases, analogues of Jeffrey's rule of conditioning are introduced and discussed. The relations between Spohn's model and possibility theory are emphasized and Spohn's updating rule is contrasted with the Jeffrey-like rule of conditioning in possibility theory. Recent results by Shenoy on the combination of ordinal conditional functions are reinterpreted in the language of possibility theory. It is shown that Shenoy's combination rule has a well-known possibilistic counterpart.


title: A New Approach to Updating Beliefs

abstract: We define a new notion of conditional belief, which plays the same role for Dempster-Shafer belief functions as conditional probability does for probability functions. Our definition is different from the standard definition given by Dempster, and avoids many of the well-known problems of that definition. Just as the conditional probability Pr (lB) is a probability function which is the result of conditioning on B being true, so too our conditional belief function Bel (lB) is a belief function which is the result of conditioning on B being true. We define the conditional belief as the lower envelope (that is, the inf) of a family of conditional probability functions, and provide a closed form expression for it. An alternate way of understanding our definition of conditional belief is provided by considering ideas from an earlier paper [Fagin and Halpern, 1989], where we connect belief functions with inner measures. In particular, we show here how to extend the definition of conditional probability to non measurable sets, in order to get notions of inner and outer conditional probabilities, which can be viewed as best approximations to the true conditional probability, given our lack of information. Our definition of conditional belief turns out to be an exact analogue of our definition of inner conditional probability.


title: The Transferable Belief Model and Other Interpretations of Dempster-Shafer's Model

abstract: Dempster-Shafer's model aims at quantifying degrees of belief But there are so many interpretations of Dempster-Shafer's theory in the literature that it seems useful to present the various contenders in order to clarify their respective positions. We shall successively consider the classical probability model, the upper and lower probabilities model, Dempster's model, the transferable belief model, the evidentiary value model, the provability or necessity model. None of these models has received the qualification of Dempster-Shafer. In fact the transferable belief model is our interpretation not of Dempster's work but of Shafer's work as presented in his book (Shafer 1976, Smets 1988). It is a ?purified' form of Dempster-Shafer's model in which any connection with probability concept has been deleted. Any model for belief has at least two components: one static that describes our state of belief, the other dynamic that explains how to update our belief given new pieces of information. We insist on the fact that both components must be considered in order to study these models. Too many authors restrict themselves to the static component and conclude that Dempster-Shafer theory is the same as some other theory. But once the dynamic component is considered, these conclusions break down. Any comparison based only on the static component is too restricted. The dynamic component must also be considered as the originality of the models based on belief functions lies in its dynamic component.


title: Valuation-Based Systems for Discrete Optimization

abstract: This paper describes valuation-based systems for representing and solving discrete optimization problems. In valuation-based systems, we represent information in an optimization problem using variables, sample spaces of variables, a set of values, and functions that map sample spaces of sets of variables to the set of values. The functions, called valuations, represent the factors of an objective function. Solving the optimization problem involves using two operations called combination and marginalization. Combination tells us how to combine the factors of the joint objective function. Marginalization is either maximization or minimization. Solving an optimization problem can be simply described as finding the marginal of the joint objective function for the empty set. We state some simple axioms that combination and marginalization need to satisfy to enable us to solve an optimization problem using local computation. For optimization problems, the solution method of valuation-based systems reduces to non-serial dynamic programming. Thus our solution method for VBS can be regarded as an abstract description of dynamic programming. And our axioms can be viewed as conditions that permit the use of dynamic programming.


title: Computational Aspects of the Mobius Transform

abstract: In this paper we associate with every (directed) graph G a transformation called the Mobius transformation of the graph G. The Mobius transformation of the graph (O) is of major significance for Dempster-Shafer theory of evidence. However, because it is computationally very heavy, the Mobius transformation together with Dempster's rule of combination is a major obstacle to the use of Dempster-Shafer theory for handling uncertainty in expert systems. The major contribution of this paper is the discovery of the 'fast Mobius transformations' of (O). These 'fast Mobius transformations' are the fastest algorithms for computing the Mobius transformation of (O). As an easy but useful application, we provide, via the commonality function, an algorithm for computing Dempster's rule of combination which is much faster than the usual one.


title: Using Dempster-Shafer Theory in Knowledge Representation

abstract: In this paper, we suggest marrying Dempster-Shafer (DS) theory with Knowledge Representation (KR). Born out of this marriage is the definition of "Dempster-Shafer Belief Bases", abstract data types representing uncertain knowledge that use DS theory for representing strength of belief about our knowledge, and the linguistic structures of an arbitrary KR system for representing the knowledge itself. A formal result guarantees that both the properties of the given KR system and of DS theory are preserved. The general model is exemplified by defining DS Belief Bases where First Order Logic and (an extension of) KRYPTON are used as KR systems. The implementation problem is also touched upon.


title: A Hierarchical Approach to Designing Approximate Reasoning-Based Controllers for Dynamic Physical Systems

abstract: This paper presents a new technique for the design of approximate reasoning based controllers for dynamic physical systems with interacting goals. In this approach, goals are achieved based on a hierarchy defined by a control knowledge base and remain highly interactive during the execution of the control task. The approach has been implemented in a rule-based computer program which is used in conjunction with a prototype hardware system to solve the cart-pole balancing problem in real-time. It provides a complementary approach to the conventional analytical control methodology, and is of substantial use where a precise mathematical model of the process being controlled is not available.


title: Evidence Combination and Reasoning and Its Application to Real-World Problem-Solving

abstract: In this paper a new mathematical procedure is presented for combining different pieces of evidence which are represented in the interval form to reflect our knowledge about the truth of a hypothesis. Evidences may be correlated to each other (dependent evidences) or conflicting in supports (conflicting evidences). First, assuming independent evidences, we propose a methodology to construct combination rules which obey a set of essential properties. The method is based on a geometric model. We compare results obtained from Dempster-Shafer's rule and the proposed combination rules with both conflicting and non-conflicting data and show that the values generated by proposed combining rules are in tune with our intuition in both cases. Secondly, in the case that evidences are known to be dependent, we consider extensions of the rules derived for handling conflicting evidence. The performance of proposed rules are shown by different examples. The results show that the proposed rules reasonably make decision under dependent evidences


title: On Some Equivalence Relations between Incidence Calculus and Dempster-Shafer Theory of Evidence

abstract: Incidence Calculus and Dempster-Shafer Theory of Evidence are both theories to describe agents' degrees of belief in propositions, thus being appropriate to represent uncertainty in reasoning systems. This paper presents a straightforward equivalence proof between some special cases of these theories.


title: Using Belief Functions for Uncertainty Management and Knowledge Acquisition: An Expert Application

abstract: This paper describes recent work on an ongoing project in medical diagnosis at the University of Guelph. A domain on which experts are not very good at pinpointing a single disease outcome is explored. On-line medical data is available over a relatively short period of time. Belief Functions (Dempster-Shafer theory) are first extracted from data and then modified with expert opinions. Several methods for doing this are compared and results show that one formulation statistically outperforms the others, including a method suggested by Shafer. Expert opinions and statistically derived information about dependencies among symptoms are also compared. The benefits of using uncertainty management techniques as methods for knowledge acquisition from data are discussed.


title: An Architecture for Probabilistic Concept-Based Information Retrieval

abstract: While concept-based methods for information retrieval can provide improved performance over more conventional techniques, they require large amounts of effort to acquire the concepts and their qualitative and quantitative relationships. This paper discusses an architecture for probabilistic concept-based information retrieval which addresses the knowledge acquisition problem. The architecture makes use of the probabilistic networks technology for representing and reasoning about concepts and includes a knowledge acquisition component which partially automates the construction of concept knowledge bases from data. We describe two experiments that apply the architecture to the task of retrieving documents about terrorism from a set of documents from the Reuters news service. The experiments provide positive evidence that the architecture design is feasible and that there are advantages to concept-based methods.


title: Amplitude-Based Approach to Evidence Accumulation

abstract: We point out the need to use probability amplitudes rather than probabilities to model evidence accumulation in decision processes involving real physical sensors. Optical information processing systems are given as typical examples of systems that naturally gather evidence in this manner. We derive a new, amplitude-based generalization of the Hough transform technique used for object recognition in machine vision. We argue that one should use complex Hough accumulators and square their magnitudes to get a proper probabilistic interpretation of the likelihood that an object is present. Finally, we suggest that probability amplitudes may have natural applications in connectionist models, as well as in formulating knowledge-based reasoning problems.


title: A Probabilistic Reasoning Environment

abstract: A framework is presented for a computational theory of probabilistic argument. The Probabilistic Reasoning Environment encodes knowledge at three levels. At the deepest level are a set of schemata encoding the system's domain knowledge. This knowledge is used to build a set of second-level arguments, which are structured for efficient recapture of the knowledge used to construct them. Finally, at the top level is a Bayesian network constructed from the arguments. The system is designed to facilitate not just propagation of beliefs and assimilation of evidence, but also the dynamic process of constructing a belief network, evaluating its adequacy, and revising it when necessary.


title: On Non-monotonic Conditional Reasoning

abstract: This note is concerned with a formal analysis of the problem of non-monotonic reasoning in intelligent systems, especially when the uncertainty is taken into account in a quantitative way. A firm connection between logic and probability is established by introducing conditioning notions by means of formal structures that do not rely on quantitative measures. The associated conditional logic, compatible with conditional probability evaluations, is non-monotonic relative to additional evidence. Computational aspects of conditional probability logic are mentioned. The importance of this development lies on its role to provide a conceptual basis for various forms of evidence combination and on its significance to unify multi-valued and non-monotonic logics


title: Decisions with Limited Observations over a Finite Product Space: the Klir Effect

abstract: Probability estimation by maximum entropy reconstruction of an initial relative frequency estimate from its projection onto a hypergraph model of the approximate conditional independence relations exhibited by it is investigated. The results of this study suggest that use of this estimation technique may improve the quality of decisions that must be made on the basis of limited observations over a decomposable finite product space.


title: Fine-Grained Decision-Theoretic Search Control

abstract: Decision-theoretic control of search has previously used as its basic unit. of computation the generation and evaluation of a complete set of successors. Although this simplifies analysis, it results in some lost opportunities for pruning and satisficing. This paper therefore extends the analysis of the value of computation to cover individual successor evaluations. The analytic techniques used may prove useful for control of reasoning in more general settings. A formula is developed for the expected value of a node, k of whose n successors have been evaluated. This formula is used to estimate the value of expanding further successors, using a general formula for the value of a computation in game-playing developed in earlier work. We exhibit an improved version of the MGSS* algorithm, giving empirical results for the game of Othello.


title: Rules, Belief Functions and Default Logic

abstract: This paper describes a natural framework for rules, based on belief functions, which includes a repre- sentation of numerical rules, default rules and rules allowing and rules not allowing contraposition. In particular it justifies the use of the Dempster-Shafer Theory for representing a particular class of rules, Belief calculated being a lower probability given certain independence assumptions on an underlying space. It shows how a belief function framework can be generalised to other logics, including a general Monte-Carlo algorithm for calculating belief, and how a version of Reiter's Default Logic can be seen as a limiting case of a belief function formalism.


title: Combination of Evidence Using the Principle of Minimum Information Gain

abstract: One of the most important aspects in any treatment of uncertain information is the rule of combination for updating the degrees of uncertainty. The theory of belief functions uses the Dempster rule to combine two belief functions defined by independent bodies of evidence. However, with limited dependency information about the accumulated belief the Dempster rule may lead to unsatisfactory results. The present study suggests a method to determine the accumulated belief based on the premise that the information gain from the combination process should be minimum. This method provides a mechanism that is equivalent to the Bayes rule when all the conditional probabilities are available and to the Dempster rule when the normalization constant is equal to one. The proposed principle of minimum information gain is shown to be equivalent to the maximum entropy formalism, a special case of the principle of minimum cross-entropy. The application of this principle results in a monotonic increase in belief with accumulation of consistent evidence. The suggested approach may provide a more reasonable criterion for identifying conflicts among various bodies of evidence.


title: Probabilistic Evaluation of Candidates and Symptom Clustering for Multidisorder Diagnosis

abstract: This paper derives a formula for computing the conditional probability of a set of candidates, where a candidate is a set of disorders that explain a given set of positive findings. Such candidate sets are produced by a recent method for multidisorder diagnosis called symptom clustering. A symptom clustering represents a set of candidates compactly as a cartesian product of differential diagnoses. By evaluating the probability of a candidate set, then, a large set of candidates can be validated or pruned simultaneously. The probability of a candidate set is then specialized to obtain the probability of a single candidate. Unlike earlier results, the equation derived here allows the specification of positive, negative, and unknown symptoms and does not make assumptions about disorders not in the candidate.


title: Extending Term Subsumption systems for Uncertainty Management

abstract: A major difficulty in developing and maintaining very large knowledge bases originates from the variety of forms in which knowledge is made available to the KB builder. The objective of this research is to bring together two complementary knowledge representation schemes: term subsumption languages, which represent and reason about defining characteristics of concepts, and proximate reasoning models, which deal with uncertain knowledge and data in expert systems. Previous works in this area have primarily focused on probabilistic inheritance. In this paper, we address two other important issues regarding the integration of term subsumption-based systems and approximate reasoning models. First, we outline a general architecture that specifies the interactions between the deductive reasoner of a term subsumption system and an approximate reasoner. Second, we generalize the semantics of terminological language so that terminological knowledge can be used to make plausible inferences. The architecture, combined with the generalized semantics, forms the foundation of a synergistic tight integration of term subsumption systems and approximate reasoning models.


title: Refinement and Coarsening of Bayesian Networks

abstract: In almost all situation assessment problems, it is useful to dynamically contract and expand the states under consideration as assessment proceeds. Contraction is most often used to combine similar events or low probability events together in order to reduce computation. Expansion is most often used to make distinctions of interest which have significant probability in order to improve the quality of the assessment. Although other uncertainty calculi, notably Dempster-Shafer [Shafer, 1976], have addressed these operations, there has not yet been any approach of refining and coarsening state spaces for the Bayesian Network technology. This paper presents two operations for refining and coarsening the state space in Bayesian Networks. We also discuss their practical implications for knowledge acquisition.


title: Second Order Probabilities for Uncertain and Conflicting Evidence

abstract: In this paper the elicitation of probabilities from human experts is considered as a measurement process, which may be disturbed by random 'measurement noise'. Using Bayesian concepts a second order probability distribution is derived reflecting the uncertainty of the input probabilities. The algorithm is based on an approximate sample representation of the basic probabilities. This sample is continuously modified by a stochastic simulation procedure, the Metropolis algorithm, such that the sequence of successive samples corresponds to the desired posterior distribution. The procedure is able to combine inconsistent probabilities according to their reliability and is applicable to general inference networks with arbitrary structure. Dempster-Shafer probability mass functions may be included using specific measurement distributions. The properties of the approach are demonstrated by numerical experiments.


title: Computing Probability Intervals Under Independency Constraints

abstract: Many AI researchers argue that probability theory is only capable of dealing with uncertainty in situations where a full specification of a joint probability distribution is available, and conclude that it is not suitable for application in knowledge-based systems. Probability intervals, however, constitute a means for expressing incompleteness of information. We present a method for computing such probability intervals for probabilities of interest from a partial specification of a joint probability distribution. Our method improves on earlier approaches by allowing for independency relationships between statistical variables to be exploited.


title: An Empirical Analysis of Likelihood-Weighting Simulation on a Large, Multiply-Connected Belief Network

abstract: We analyzed the convergence properties of likelihood- weighting algorithms on a two-level, multiply connected, belief-network representation of the QMR knowledge base of internal medicine. Specifically, on two difficult diagnostic cases, we examined the effects of Markov blanket scoring, importance sampling, demonstrating that the Markov blanket scoring and self-importance sampling significantly improve the convergence of the simulation on our model.


title: Towards a Normative Theory of Scientific Evidence

abstract: A scientific reasoning system makes decisions using objective evidence in the form of independent experimental trials, propositional axioms, and constraints on the probabilities of events. As a first step towards this goal, we propose a system that derives probability intervals from objective evidence in those forms. Our reasoning system can manage uncertainty about data and rules in a rule based expert system. We expect that our system will be particularly applicable to diagnosis and analysis in domains with a wealth of experimental evidence such as medicine. We discuss limitations of this solution and propose future directions for this research. This work can be considered a generalization of Nilsson's "probabilistic logic" [Nil86] to intervals and experimental observations.


title: A Model for Non-Monotonic Reasoning Using Dempster's Rule

abstract: Considerable attention has been given to the problem of non-monotonic reasoning in a belief function framework. Earlier work (M. Ginsberg) proposed solutions introducing meta-rules which recognized conditional independencies in a probabilistic sense. More recently an e-calculus formulation of default reasoning (J. Pearl) shows that the application of Dempster's rule to a non-monotonic situation produces erroneous results. This paper presents a new belief function interpretation of the problem which combines the rules in a way which is more compatible with probabilistic results and respects conditions of independence necessary for the application of Dempster's combination rule. A new general framework for combining conflicting evidence is also proposed in which the normalization factor becomes modified. This produces more intuitively acceptable results.


title: Default Reasoning and the Transferable Belief Model

abstract: Inappropriate use of Dempster's rule of combination has led some authors to reject the Dempster-Shafer model, arguing that it leads to supposedly unacceptable conclusions when defaults are involved. A most classic example is about the penguin Tweety. This paper will successively present: the origin of the miss-management of the Tweety example; two types of default; the correct solution for both types based on the transferable belief model (our interpretation of the Dempster-Shafer model (Shafer 1976, Smets 1988)); Except when explicitly stated, all belief functions used in this paper are simple support functions, i.e. belief functions for which only one proposition (the focus) of the frame of discernment receives a positive basic belief mass with the remaining mass being given to the tautology. Each belief function will be described by its focus and the weight of the focus (e.g. m(A)=.9). Computation of the basic belief masses are always performed by vacuously extending each belief function to the product space built from all variables involved, combining them on that space by Dempster's rule of combination, and projecting the result to the space corresponding to each individual variable.


title: Separable and transitive graphoids

abstract: We examine three probabilistic formulations of the sentence a and b are totally unrelated with respect to a given set of variables U. First, two variables a and b are totally independent if they are independent given any value of any subset of the variables in U. Second, two variables are totally uncoupled if U can be partitioned into two marginally independent sets containing a and b respectively. Third, two variables are totally disconnected if the corresponding nodes are disconnected in every belief network representation. We explore the relationship between these three formulations of unrelatedness and explain their relevance to the process of acquiring probabilistic knowledge from human experts.


title: Analysis in HUGIN of Data Conflict

abstract: After a brief introduction to causal probabilistic networks and the HUGIN approach, the problem of conflicting data is discussed. A measure of conflict is defined, and it is used in the medical diagnostic system MUNIN. Finally, it is discussed how to distinguish between conflicting data and a rare case.


title: Evaporation phenomena in f(T) gravity

abstract: We formulate evaporation phenomena in a generic model of generalized teleparallel gravity in Weitzenbock spacetime with diagonal and non-diagonal tetrads basis. We also perform the perturbation analysis around the constant torsion scalar solution named Nariai spacetime which is an exact solution of field equations as the limiting case of the Schwarzschild-de Sitter and in the limit where two back hole and their cosmological horizons coincide. By a carefully analysis of the horizon perturbation equation, we show that (anti)evaporation can not happen if we use a diagonal tetrad basis. This result implies that a typical black hole in any generic form of generalized teleparallel gravity is frozen in its initial state if we use the diagonal tetrads. But in the case of non-diagonal tetrads the analysis is completely different. By a suitable non trivial non-diagonal tetrad basis we investigate the linear stability of the model under perturbations of the metric and torsion simultaneously. We observe that in spite of the diagonal case, both evaporation and anti evaporation can happen. The phenomena depend on the initial phase of the horizon perturbation. In the first mode when we restrict ourselves to the first lower modes the (anti)evaporation happens. So, in non-diagonal case the physical phenomena is reasonable. This is an important advantage of using non-diagonal tetrads instead of the diagonal ones. We also see that this is an universal feature, completely independent from the form of the model.


title: Free algebras, amalgamation, and a theorem of Vaught for many valued logics

abstract: We investigate atomicity of free algebras and various forms of amalgamation for BL and MV algebras, and also Heyting algebras, though the latter algebras may not be linearly ordered, so strictly speaking their corresponding intuitionistic logic does not belong to many valued logic. Generalizing results of Comer proved in the classical first order case; working out a sheaf duality on the Zarski topology defined on the prime spectrum of such algebras, we infer several definability theorems, and obtain a representation theorem for theories as continuous sections of Sheaves. We also prove an omitting types theorem for fuzzy logic, and formulate and prove several of its consequences (in classical model theory) adapted to our case; that has to do with existence and uniqueness of prime and atomic models.


title: On some open problems in Algebraic logic

abstract: Several open problems in algebraic logic are solved.


title: Protoplanetary disk evolution and stellar parameters of T Tauri binaries in Chamaeleon I

abstract: This study aims to determine the impact of stellar binary companions on the lifetime and evolution of circumstellar disks in the Chamaeleon I (Cha I) star-forming region by measuring the frequency and strength of accretion and circumstellar dust signatures around the individual components of T Tauri binary stars. We used high-angular resolution adaptive optics JHKL'-band photometry and 1.5-2.5mu spectroscopy of 19 visual binary and 7 triple stars in Cha I - including one newly discovered tertiary component - with separations between ~25 and ~1000au. The data allowed us to infer stellar component masses and ages and, from the detection of near-infrared excess emission and the strength of Brackett-gamma emission, the presence of ongoing accretion and hot circumstellar dust of the individual stellar component of each binary. Of all the stellar components in close binaries with separations of 25-100au, 10(+15-5)% show signs of accretion. This is less than half of the accretor fraction found in wider binaries, which itself appears significantly reduced (~44%) compared with previous measurements of single stars in Cha I. Hot dust was found around 50(+30-15)% of the target components, a value that is indistinguishable from that of Cha I single stars. Only the closest binaries (<25au) were inferred to have a significantly reduced fraction (<~25%) of components that harbor hot dust. Accretors were exclusively found in binary systems with unequal component masses M_secondary/M_primary < 0.8, implying that the detected accelerated disk dispersal is a function of mass-ratio. This agrees with the finding that only one accreting secondary star was found, which is also the weakest accretor in the sample. The results imply that disk dispersal is more accelerated the stronger the dynamical disk truncation, i.e., the smaller the inferred radius of the disk. (abridged)


title: Determining Triple Gauge Boson Couplings from Higgs Data

abstract: In the framework of effective Lagrangians with the SU(2)_L x U(1)_Y symmetry linearly realized, modifications of the couplings of the Higgs field to the electroweak gauge bosons are related to anomalous triple gauge couplings (TGCs). Here, we show that the analysis of the latest Higgs boson production data at the LHC and Tevatron give rise to strong bounds on TGCs that are complementary to those from direct TGC analysis. We present the constraints on TGCs obtained by combining all available data on direct TGC studies and on Higgs production analysis. Note added: The analysis has been updated with all the public data available as November 2013. Updates of this analysis are provided at http://hep.if.usp.br/Higgs


title: The role of relativistic jets in the heaviest and most active supermassive black holes at high redshift

abstract: In powerful radio-quiet active galactic nuclei (AGN), black holes heavier than one billion solar masses form at a redshift ~1.5-2. Supermassive black holes in jetted radio-loud AGN seems to form earlier, at a redshift close to 4. The ratio of active radio-loud to radio-quiet AGN hosting heavy black holes is therefore a rather a strong function of redshift. We report on some recent evidence supporting this conclusion, gathered from the Burst Alert Telescope (BAT, onboard Swift) and by the Large Area Telescope (LAT, onboard Fermi). We suggest that the more frequent occurrence of relativistic jets in the most massive black holes at high redshifts, compared to later times, could be due to the average black hole spin being greater in the distant past, or else to the jet helping a fast accretion rate (or some combination of the two scenarios). We emphasize that the large total accretion efficiency of rapidly spinning black holes inhibits a fast growth, unless a large fraction of the available gravitational energy of the accreted mass is not converted into radiation, but used to form and maintain a powerful jet.


title: The VMC survey VII. Reddening map of the 30 Doradus field and the structure of the cold interstellar medium

abstract: Context: The details of how galaxies have evolved are imprinted in their star formation history, chemical enrichment and morpho-kinematic structure. Parameters behind these can be measured by combining photometric techniques with modelling. However, there are uncertainties from the ambiguity of colour and magnitude and the effects of interstellar reddening. Aims: In this paper we present a detailed reddening map of the central 30 Doradus region of the Large Magellanic Cloud; for community use and to test the methods used. The reddening, a measurement of dust extinction, acts as a tracer of the interstellar medium (ISM). Methods: Near infrared photometry of red clump stars are used to measure reddening as extinction is the main cause of their colour and magnitude variance. The star formation history is used to convert colour to reddening values which are subsequently converted to visual extinction. Results: Presented is a dust map for the 30 Doradus field. This map samples a region of 1x1.5 deg, containing ~1.5x10^5 red clump stars which probe reddening up to AV=6 mag. We compare our map with maps from the literature, including optical extinction maps and radio, mid- and far-infrared maps of atomic hydrogen and dust emission. Through estimation of column density we locate molecular clouds. Conclusions: This new reddening map shows correlation with equivalent maps in the literature, validating the method of red clump star selection. We make our reddening map available for community use. In terms of ISM the red clump stars appear to be more affected by the cooler dust measured by 70 micron emission because there is stronger correlation between increasing emission and extinction due to red clump stars not being located near hot stars that would heat the dust. The transition from atomic hydrogen to molecular hydrogen occurs between densities of NH=4x10^21 to 6x10^21 cm^-2.


title: The star formation rate and stellar mass limits for submillimetre galaxies implied by recent interferometric observations

abstract: Explaining the observed number counts of submillimetre (submm) galaxies (SMGs) has been a longstanding challenge for theoretical models. Surprisingly, recent observations have suggested that the brightest SMGs are almost exclusively multiple fainter sources blended into a single source in the single-dish surveys. This result is in contrast with the predictions of our previously presented theoretical model, which includes some effects of blending. In this Letter, we consider the implications of an upper limit on the submm flux density for the demographics of the SMG population. Using a relation amongst submm flux, star formation rate (SFR), and dust mass (M_d) from our previous work, we infer the maximum SFR for a range of flux density limits. For M_d = 2 x 10^9 (5 x 10^8) M_sun, the SFR limit that corresponds to an 870-{\mu}m flux density (S_870) limit in the range 9 - 12.5 mJy is in the range ~630 - 1400 (3600 - 7700) M_sun/yr. The SFR limit implies a correspondingly sharp, redshift-dependent cutoff in the stellar mass (M_star) function, the value of which we predict using the S_870-M_star relation predicted by our model. The M_star limit decreases with increasing redshift: for an S_870 limit of 9 - 12.5 mJy, the M_star limit ranges from ~4 - 7 x 10^12 M_sun at z ~ 1 to ~3 - 5 x 10^11 M_sun at z ~ 6. We discuss the few interferometrically detected SMGs that may be brighter than the proposed cutoff. Although such objects are certainly interesting, inferences based on such objects may not apply to most SMGs.


title: Duality and Decay of Macroscopic F-Strings

abstract: We study the decay of fundamental string loops of arbitrary size L/min(n,m)>>\sqrt{\alpha'}, labelled by (n,m;\lambda_n,\bar{\lambda}_m), where n,m correspond to left- and right-mover harmonics and \lambda_n,\bar{\lambda}_m to polarisation tensors, and find that a description in terms of the recent coherent vertex operator construction of Hindmarsh and Skliros is computationally very efficient. We primarily show that the decay rates and mass shifts of vertex operators (n,m;\lambda_n,\bar{\lambda}_m) and their "duals" (n,m;\lambda_n,\bar{\lambda}_m^*) are equal to leading order in the string coupling, implying for instance that decay rates of epicycloids equal those of hypocycloids. We then compute the power and decay rates associated to massless IR radiation for the trajectory (1,1;\lambda_1,\bar{\lambda}_1), and find that it is precisely reproduced by the low energy effective theory of Dabholkar and Harvey. Guided by this correspondence, we conjecture the result for arbitrary trajectories (n,m;\lambda_n,\bar{\lambda}_m) and discover a curious relation between gravitational and axion plus dilaton radiation. It is now possible to start exploring string evolution in regimes where a low energy effective description is less useful, such as in the vicinity of cusps.


title: Rotating Black Droplet

abstract: We construct the gravitational dual, in the Unruh state, of the "jammed" phase of a CFT at strong coupling and infinite N on a fixed five-dimensional rotating Myers-Perry black hole with equal angular momenta. When the angular momenta are all zero, the solution corresponds to the five-dimensional generalization of the solution first studied by Figueras, Lucietti, and Wiseman. In the extremal limit, when the angular momenta of the Myers-Perry black hole are maximum, the Unruh, Boulware and Hartle-Hawking states degenerate. We give a detailed analysis of the corresponding holographic stress energy tensor for all values of the angular momenta, finding it to be regular at the horizon in all cases. We compare our results with existent literature on thermal states of free field theories on black hole backgrounds.


title: On the Possibility of Habitable Moons in the System of HD 23079: Results from Orbital Stability Studies

abstract: The aim of our study is to investigate the possibility of habitable moons orbiting the giant planet HD 23079b, a Jupiter-mass planet, which follows a low-eccentricity orbit in the outer region of HD 23079's habitable zone. We show that HD 23079b is able to host habitable moons in prograde and retrograde orbits, as expected, noting that the outer stability limit for retrograde orbits is increased by nearly 90% compared to that of prograde orbits, a result consistent with previous generalized studies. For the targeted parameter space it was found that the outer stability limit for habitable moons varies between 0.05236 and 0.06955 AU (prograde orbits) and between 0.1023 and 0.1190 AU (retrograde orbits) depending on the orbital parameters of the Jupiter-type planet if a minimum mass is assumed. These intervals correspond to 0.306 and 0.345 (prograde orbits) and 0.583 and 0.611 (retrograde orbits) of the planet's Hill radius. Larger stability limits are obtained if an increased value for the planetary mass m_p is considered; they are consistent with the theoretically deduced relationship of m_p^{1/3}. Finally, we compare our results to the statistical formulae of Domingos et al. (2006) [MNRAS 373, 1227], indicating both concurrence and limitations.


title: Localization protected quantum order

abstract: Closed quantum systems with quenched randomness exhibit many-body localized regimes wherein they do not equilibrate even though prepared with macroscopic amounts of energy above their ground states. We show that such localized systems can order in that individual many-body eigenstates can break symmetries or display topological order in the infinite volume limit. Indeed, isolated localized quantum systems can order even at energy densities where the corresponding thermally equilibrated system is disordered, i.e.: localization protects order. In addition, localized systems can move between ordered and disordered localized phases via non-thermodynamic transitions in the properties of the many-body eigenstates. We give evidence that such transitions may proceed via localized critical points. We note that localization provides protection against decoherence that may allow experimental manipulation of macroscopic quantum states. We also identify a `spectral transition' involving a sharp change in the spectral statistics of the many-body Hamiltonian.

categories: cond-mat.stat-mech cond-mat.dis-nn cond-mat.mes-hall cond-mat.quant-gas cond-mat.str-el


title: Dark Matter Detection in Focus Point Supersymmetry

abstract: We determine the prospects for direct and indirect detection of thermal relic neutralinos in supersymmetric theories with multi-TeV squarks and sleptons. We consider the concrete example of the focus point region of minimal supergravity, but our results are generically valid for all models with decoupled scalars and mixed Bino-Higgsino or Higgsino-like dark matter. We determine the parameter space consistent with a 125 GeV Higgs boson including 3-loop corrections in the calculation of the Higgs mass. These corrections increase m_h by 1-3 GeV, lowering the preferred scalar mass scale and decreasing the fine-tuning measure in these scenarios. We then systematically examine prospects for dark matter direct and indirect detection. Direct detection constraints do not exclude these models, especially for \mu < 0. At the same time, the scenario generically predicts spin-independent signals just beyond current bounds. We also consider indirect detection with neutrinos, gamma rays, anti-protons, and anti-deuterons. Current IceCube neutrino constraints are competitive with direct detection, implying bright prospects for complementary searches with both direct and indirect detection.


title: Gravito-Electromagnetic Perturbations of Kerr-Newman Black Holes: Stability and Isospectrality in the Slow-Rotation Limit

abstract: The most general stationary black-hole solution of Einstein-Maxwell theory in vacuum is the Kerr-Newman metric, specified by three parameters: mass M, spin J and charge Q. Within classical general relativity, the most important and challenging open problem in black-hole perturbation theory is the study of gravitational and electromagnetic fields in the Kerr-Newman geometry, because of the indissoluble coupling of the perturbation functions. Here we circumvent this long-standing problem by working in the slow-rotation limit. We compute the quasinormal modes up to linear order in J for any value of Q and provide the first, fully-consistent stability analysis of the Kerr-Newman metric. For scalar perturbations the quasinormal modes can be computed exactly, and we demonstrate that the method is accurate within 3% for spins J/Jmax<~0.5, where Jmax is the maximum allowed spin for any value of Q. Quite remarkably, we find numerical evidence that the axial and polar sectors of the gravito-electromagnetic perturbations are isospectral to linear order in the spin. The extension of our results to nonasymptotically flat space-times could be useful in the context of gauge/gravity dualities and string theory.


title: Towards a Renormalization Group Approach to Density Functional Theory - General Formalism and Case Studies -

abstract: We discuss a two-point particle irreducible (2PPI) approach to many-body physics which relies on a renormalization group (RG) flow equation for the associated effective action. In particular, the general structure and properties of this RG flow equation are analyzed in detail. Moreover, we discuss how our 2PPI RG approach relates to Density Functional Theory and argue that it can in principle be used to study ground-state properties of non-relativistic many-body systems from microscopic interactions, such as (heavy) nuclei. For illustration purposes, we use our formalism to compute the ground-state properties of two toy models.


title: CFTs in rotating black hole backgrounds

abstract: We use AdS/CFT to construct the gravitational dual of a 5D CFT in the background of a non-extremal rotating black hole. Our boundary conditions are such that the vacuum state of the dual CFT corresponds to the Unruh state. We extract the expectation value of the stress tensor of the dual CFT using holographic renormalisation and show that it is stationary and regular on both the future and the past event horizons. The energy density of the CFT is found to be negative everywhere in our domain and we argue that this can be understood as a vacuum polarisation effect. We construct the solutions by numerically solving the elliptic Einstein--DeTurck equation for stationary Lorentzian spacetimes with Killing horizons.


title: Comparative investigation of the freezing phenomena for quantum correlations under nondissipative decoherence

abstract: We show that the phenomenon of frozen discord, exhibited by specific classes of two-qubit states under local nondissipative decoherent evolutions, is a common feature of all known bona fide measures of general quantum correlations. All those measures, despite inducing typically inequivalent orderings on the set of nonclassically correlated states, return a constant value in the considered settings. Every communication protocol which relies on quantum correlations as resource will run with a performance completely unaffected by noise in the specified dynamical conditions. We provide a geometric interpretation of this

categories: quant-ph cond-mat.stat-mech math-ph math.MP physics.optics


title: Waves and distributions connected to systems of interacting populations

abstract: We discuss two cases that can be connected to the dynamics of interacting populations: (I.) density waves for the case or negligible random fluctuations of the populations densities, and (II.) probability distributions connected to the model equations for of spatially averaged populations densities for the case of significant random fluctuations of the independent quantity that can be associated with the population density. For the case (I.) we consider model equations containing polynomial nonlinearities. Such nonlinearities can arise as a consequence of interaction among the populations (for the case of large population densities) or as a result of a Taylor series expansion (for the case of small density of interacting populations). In the both cases we can apply the modified method of simplest equation to obtain exact traveling-wave solutions connected to migration of population members. Such solutions are obtained for systems consisting of 1 or 3 populations respectively. For the case (II.) we discuss model equations of the Fokker-Planck kind for the evolution of the statistical distributions of population densities. We derive several stationary distributions for the population density and calculate the expected exit time connected to the extinction of the studied population.