OpenRaiser/Intern-Atlas huggingface dataset:
Ideal Reformulation of Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

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.
Approximations in Bayesian Belief Universe for Knowledge Based Systems
Venue: arXiv cs.AI 2013
Year: 2013

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.
A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints
Venue: arXiv cs.AI 2013
Year: 2013

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
A Sensitivity Analysis of Pathfinder
Venue: arXiv cs.AI 2013
Year: 2013

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.
Application of Confidence Intervals to the Autonomous Acquisition of High-level Spatial Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

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.
Directed Reduction Algorithms and Decomposable Graphs
Venue: arXiv cs.AI 2013
Year: 2013

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.
Possibility as Similarity: the Semantics of Fuzzy Logic
Venue: arXiv cs.AI 2013
Year: 2013

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.
Computational Aspects of the Mobius Transform
Venue: arXiv cs.AI 2013
Year: 2013

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.
A Probabilistic Reasoning Environment
Venue: arXiv cs.AI 2013
Year: 2013

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.
Rules, Belief Functions and Default Logic
Venue: arXiv cs.AI 2013
Year: 2013

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.
Extending Term Subsumption systems for Uncertainty Management
Venue: arXiv cs.AI 2013
Year: 2013

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.
Second Order Probabilities for Uncertain and Conflicting Evidence
Venue: arXiv cs.AI 2013
Year: 2013

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.
Solving Linear Programming with Constraints Unknown
Venue: arXiv cs.DS 2013
Year: 2013

What is the value of input information in solving linear programming? The celebrated ellipsoid algorithm tells us that the full information of input constraints is not necessary; the algorithm works as long as there exists an oracle that, on a proposed candidate solution, returns a violation in the format of a separating hyperplane. Can linear programming still be efficiently solved if the returned violation is in other formats? We study this question in a trial-and-error framework: there is an oracle that, upon a proposed solution, returns the index of a violated constraint (with the content of the constraint still hidden). When more than one constraint is violated, two variants in the model are investigated. (1) The oracle returns the index of a "most violated" constraint, measured by the Euclidean distance of the proposed solution and the half-spaces defined by the constraints. In this case, the LP can be efficiently solved. (2) The oracle returns the index of an arbitrary (i.e., worst-case) violated constraint. In this case, we give an algorithm with running time exponential in the number of variables. We then show that the exponential dependence on n is unfortunately necessary even for the query complexity. These results put together shed light on the amount of information that one needs in order to solve a linear program efficiently. The proofs of the results employ a variety of geometric techniques, including McMullen's Upper Bound Theorem, the weighted spherical Voronoi diagram, and the furthest Voronoi diagram. In addition, we give an alternative proof to a conjecture of László Fejes Tóth on bounding the number of disconnected components formed by the union of m convex bodies in R^n. Our proof, inspired by the Gauss-Bonnet Theorem in global differential geometry, is independent of the known and reveals more clear insights into the problem and the bound.
A composition theorem for the Fourier Entropy-Influence conjecture
Venue: arXiv cs.CC 2013
Year: 2013

The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures of Boolean function complexity: it states that $H[f] \leq C Inf[f]$ holds for every Boolean function $f$, where $H[f]$ denotes the spectral entropy of $f$, $Inf[f]$ is its total influence, and $C > 0$ is a universal constant. Despite significant interest in the conjecture it has only been shown to hold for a few classes of Boolean functions. Our main result is a composition theorem for the FEI conjecture. We show that if $g_1,...,g_k$ are functions over disjoint sets of variables satisfying the conjecture, and if the Fourier transform of $F$ taken with respect to the product distribution with biases $E[g_1],...,E[g_k]$ satisfies the conjecture, then their composition $F(g_1(x^1),...,g_k(x^k))$ satisfies the conjecture. As an application we show that the FEI conjecture holds for read-once formulas over arbitrary gates of bounded arity, extending a recent result [OWZ11] which proved it for read-once decision trees. Our techniques also yield an explicit function with the largest known ratio of $C \geq 6.278$ between $H[f]$ and $Inf[f]$, improving on the previous lower bound of 4.615.
Improved approximation for 3-dimensional matching via bounded pathwidth local search
Venue: arXiv cs.DS 2013
Year: 2013

One of the most natural optimization problems is the k-Set Packing problem, where given a family of sets of size at most k one should select a maximum size subfamily of pairwise disjoint sets. A special case of 3-Set Packing is the well known 3-Dimensional Matching problem. Both problems belong to the Karp`s list of 21 NP-complete problems. The best known polynomial time approximation ratio for k-Set Packing is (k + eps)/2 and goes back to the work of Hurkens and Schrijver [SIDMA`89], which gives (1.5 + eps)-approximation for 3-Dimensional Matching. Those results are obtained by a simple local search algorithm, that uses constant size swaps. The main result of the paper is a new approach to local search for k-Set Packing where only a special type of swaps is considered, which we call swaps of bounded pathwidth. We show that for a fixed value of k one can search the space of r-size swaps of constant pathwidth in c^r poly(|F|) time. Moreover we present an analysis proving that a local search maximum with respect to O(log |F|)-size swaps of constant pathwidth yields a polynomial time (k + 1 + eps)/3-approximation algorithm, improving the best known approximation ratio for k-Set Packing. In particular we improve the approximation ratio for 3-Dimensional Matching from 3/2 + eps to 4/3 + eps.
How Hard is Counting Triangles in the Streaming Model
Venue: arXiv cs.DS 2013
Year: 2013

The problem of (approximately) counting the number of triangles in a graph is one of the basic problems in graph theory. In this paper we study the problem in the streaming model. We study the amount of memory required by a randomized algorithm to solve this problem. In case the algorithm is allowed one pass over the stream, we present a best possible lower bound of $Ω(m)$ for graphs $G$ with $m$ edges on $n$ vertices. If a constant number of passes is allowed, we show a lower bound of $Ω(m/T)$, $T$ the number of triangles. We match, in some sense, this lower bound with a 2-pass $O(m/T^{1/3})$-memory algorithm that solves the problem of distinguishing graphs with no triangles from graphs with at least $T$ triangles. We present a new graph parameter $ρ(G)$ -- the triangle density, and conjecture that the space complexity of the triangles problem is $Ω(m/ρ(G))$. We match this by a second algorithm that solves the distinguishing problem using $O(m/ρ(G))$-memory.
Bandwidth reduction in cognitive radio
Venue: arXiv cs.IT 2013
Year: 2013

Due to mushroom development of wireless devices cognitive radio is used to resolve the bandwidth utilization and sacristy problem. The crafty usage of bandwidth in cognitive radio based on error correcting codes is ensured to accomodate un authorized user. This study proposes a transmission model by which a finite sequence of binary cyclic codes constructed by a binary BCH code of length $n=2^{s}-1$, in which all codes have same error correction capability and code rate but sequentially increasing code lengths greater than $n$. Initially all these codes are carrying data of their corresponding primary users. A transmission pattern is planned in the sprit of interweave model deals the transmission parameters; modulation scheme, bandwidth and code rate. Whenever, any of the primary users having mod of transmission, the binary cyclic code, is not using its allocated bandwidth, the user having its data built by binary BCH code enter and exploit the free path as a secondary user. Eventually whenever the primary user with $W$ bandwidth having binary BCH code for its data transmission, change its status as a secondary user, it just requires the bandwidth less than $W$.
Decision Making "Biases" and Support for Assumption-Based Higher-Order Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Unaided human decision making appears to systematically violate consistency constraints imposed by normative theories; these biases in turn appear to justify the application of formal decision-analytic models. It is argued that both claims are wrong. In particular, we will argue that the "confirmation bias" is premised on an overly narrow view of how conflicting evidence is and ought to be handled. Effective decision aiding should focus on supporting the contral processes by means of which knowledge is extended into novel situations and in which assumptions are adopted, utilized, and revised. The Non- Monotonic Probabilist represents initial work toward such an aid.
Heuristic Search as Evidential Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

BPS, the Bayesian Problem Solver, applies probabilistic inference and decision-theoretic control to flexible, resource-constrained problem-solving. This paper focuses on the Bayesian inference mechanism in BPS, and contrasts it with those of traditional heuristic search techniques. By performing sound inference, BPS can outperform traditional techniques with significantly less computational effort. Empirical tests on the Eight Puzzle show that after only a few hundred node expansions, BPS makes better decisions than does the best existing algorithm after several million node expansions
The Compilation of Decision Models
Venue: arXiv cs.AI 2013
Year: 2013

We introduce and analyze the problem of the compilation of decision models from a decision-theoretic perspective. The techniques described allow us to evaluate various configurations of compiled knowledge given the nature of evidential relationships in a domain, the utilities associated with alternative actions, the costs of run-time delays, and the costs of memory. We describe procedures for selecting a subset of the total observations available to be incorporated into a compiled situation-action mapping, in the context of a binary decision with conditional independence of evidence. The methods allow us to incrementally select the best pieces of evidence to add to the set of compiled knowledge in an engineering setting. After presenting several approaches to compilation, we exercise one of the methods to provide insight into the relationship between the distribution over weights of evidence and the preferred degree of compilation.
Conditioning on Disjunctive Knowledge: Defaults and Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

Many writers have observed that default logics appear to contain the "lottery paradox" of probability theory. This arises when a default "proof by contradiction" lets us conclude that a typical X is not a Y where Y is an unusual subclass of X. We show that there is a similar problem with default "proof by cases" and construct a setting where we might draw a different conclusion knowing a disjunction than we would knowing any particular disjunct. Though Reiter's original formalism is capable of representing this distinction, other approaches are not. To represent and reason about this case, default logicians must specify how a "typical" individual is selected. The problem is closely related to Simpson's paradox of probability theory. If we accept a simple probabilistic account of defaults based on the notion that one proposition may favour or increase belief in another, the "multiple extension problem" for both conjunctive and disjunctive knowledge vanishes.
Strategies for Generating Micro Explanations for Bayesian Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian Belief Networks have been largely overlooked by Expert Systems practitioners on the grounds that they do not correspond to the human inference mechanism. In this paper, we introduce an explanation mechanism designed to generate intuitive yet probabilistically sound explanations of inferences drawn by a Bayesian Belief Network. In particular, our mechanism accounts for the results obtained due to changes in the causal and the evidential support of a node.
Decision under Uncertainty
Venue: arXiv cs.AI 2013
Year: 2013

We derive axiomatically the probability function that should be used to make decisions given any form of underlying uncertainty.