OpenRaiser/Intern-Atlas huggingface dataset:
Assessment, Criticism and Improvement of Imprecise Subjective Probabilities for a Medical Expert System
Venue: arXiv cs.AI 2013
Year: 2013

Three paediatric cardiologists assessed nearly 1000 imprecise subjective conditional probabilities for a simple belief network representing congenital heart disease, and the quality of the assessments has been measured using prospective data on 200 babies. Quality has been assessed by a Brier scoring rule, which decomposes into terms measuring lack of discrimination and reliability. The results are displayed for each of 27 diseases and 24 questions, and generally the assessments are reliable although there was a tendency for the probabilities to be too extreme. The imprecision allows the judgements to be converted to implicit samples, and by combining with the observed data the probabilities naturally adapt with experience. This appears to be a practical procedure even for reasonably large expert systems.
Automated Construction of Sparse Bayesian Networks from Unstructured Probabilistic Models and Domain Information
Venue: arXiv cs.AI 2013
Year: 2013

An algorithm for automated construction of a sparse Bayesian network given an unstructured probabilistic model and causal domain information from an expert has been developed and implemented. The goal is to obtain a network that explicitly reveals as much information regarding conditional independence as possible. The network is built incrementally adding one node at a time. The expert's information and a greedy heuristic that tries to keep the number of arcs added at each step to a minimum are used to guide the search for the next node to add. The probabilistic model is a predicate that can answer queries about independencies in the domain. In practice the model can be implemented in various ways. For example, the model could be a statistical independence test operating on empirical data or a deductive prover operating on a set of independence statements about the domain.
Comparing Expert Systems Built Using Different Uncertain Inference Systems
Venue: arXiv cs.AI 2013
Year: 2013

This study compares the inherent intuitiveness or usability of the most prominent methods for managing uncertainty in expert systems, including those of EMYCIN, PROSPECTOR, Dempster-Shafer theory, fuzzy set theory, simplified probability theory (assuming marginal independence), and linear regression using probability estimates. Participants in the study gained experience in a simple, hypothetical problem domain through a series of learning trials. They were then randomly assigned to develop an expert system using one of the six Uncertain Inference Systems (UISs) listed above. Performance of the resulting systems was then compared. The results indicate that the systems based on the PROSPECTOR and EMYCIN models were significantly less accurate for certain types of problems compared to systems based on the other UISs. Possible reasons for these differences are discussed.
A general theory of equilibrium behavior
Venue: arXiv cs.GT 2013
Year: 2013

Economists were content with the concept of the Nash equilibrium as game theory's solution concept until Daskalakis, Goldberg, and Papadimitriou showed that finding a Nash equilibrium is most likely a computationally hard problem, a result that set off a deep scientific crisis. Motivated, in part, by their result, in this paper, we propose a general theory of equilibrium behavior in vector fields (and, therefore, also noncooperative games). Our line of discourse is to show that these universal in nature mathematical objects are endowed with significant structure, which we probe to unearth atypical, previously unidentified, equilibrium behavior.
Some Hierarchies of QCB_0-Spaces
Venue: arXiv cs.LO 2013
Year: 2013

We define and study hierarchies of topological spaces induced by the classical Borel and Luzin hierarchies of sets. Our hierarchies are divided into two classes: hierarchies of countably based spaces induced by their embeddings into the domain Pω, and hierarchies of spaces (not necessarily countably based) induced by their admissible representations. We concentrate on the non-collapse property of the hierarchies and on the relationships between hierarchies in the two classes.
Research on Potential Semantic Web Service Discovery Mechanisms
Venue: arXiv cs.SE 2013
Year: 2013

The field of Web services is an important paradigm in distributed application development. Currently, many businesses are seeking to convert their applications into web services because of its ability to promote inter-operability among applications. As a number of web services increase, the process of discovering appropriate web services for consumption from user's perspective gains importance. In this paper, we present a study of potential ways of discovering web services and issues related to each of them. In addition, we discuss ontology concepts and related technologies, which incorporate semantic meaning and hence give domain knowledge about a web service to improve the discovery mechanism. The paper also presents an overview of related research work, identifying metrics useful in filtering web service search mechanisms.
Verification of Artifact-Centric Systems: Decidability and Modeling Issues
Venue: arXiv cs.SE 2013
Year: 2013

Artifact-centric business processes have recently emerged as an approach in which processes are centred around the evolution of business entities, called artifacts, giving equal importance to control-flow and data. The recent Guard-State-Milestone (GSM) approach provides means for specifying business artifacts lifecycles in a declarative manner, using constructs that match how executive-level stakeholders think about their business. However, it turns out that formal verification of GSM is undecidable even for very simple propositional temporal properties. We attack this challenging problem by translating GSM into a well-studied formal framework. We exploit this translation to isolate an interesting class of state-bounded GSM models for which verification of sophisticated temporal properties is decidable. We then introduce some guidelines to turn an arbitrary GSM model into a state-bounded, verifiable model.
Locality Optimization for Data Parallel Programs
Venue: arXiv cs.PL 2013
Year: 2013

Productivity languages such as NumPy and Matlab make it much easier to implement data-intensive numerical algorithms. However, these languages can be intolerably slow for programs that don't map well to their built-in primitives. In this paper, we discuss locality optimizations for our system Parakeet, a just-in-time compiler and runtime system for an array-oriented subset of Python. Parakeet dynamically compiles whole user functions to high performance multi-threaded native code. Parakeet makes extensive use of the classic data parallel operators Map, Reduce, and Scan. We introduce a new set of data parallel operators,TiledMap, TiledReduce, and TiledScan, that break up their computations into local pieces of bounded size so as better to make use of small fast memories. We introduce a novel tiling transformation to generate tiled operators automatically. Applying this transformation once tiles the program for cache, and applying it again enables tiling for registers. The sizes for cache tiles are left unspecified until runtime, when an autotuning search is performed. Finally, we evaluate our optimizations on benchmarks and show significant speedups on programs that exhibit data locality.
Potential Networks, Contagious Communities, and Understanding Social Network Structure
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we study how the network of agents adopting a particular technology relates to the structure of the underlying network over which the technology adoption spreads. We develop a model and show that the network of agents adopting a particular technology may have characteristics that differ significantly from the social network of agents over which the technology spreads. For example, the network induced by a cascade may have a heavy-tailed degree distribution even if the original network does not. This provides evidence that online social networks created by technology adoption over an underlying social network may look fundamentally different from social networks and indicates that using data from many online social networks may mislead us if we try to use it to directly infer the structure of social networks. Our results provide an alternate explanation for certain properties repeatedly observed in data sets, for example: heavy-tailed degree distribution, network densification, shrinking diameter, and network community profile. These properties could be caused by a sort of `sampling bias' rather than by attributes of the underlying social structure. By generating networks using cascades over traditional network models that do not themselves contain these properties, we can nevertheless reliably produce networks that contain all these properties. An opportunity for interesting future research is developing new methods that correctly infer underlying network structure from data about a network that is generated via a cascade spread over the underlying network.
Optimal Discrete Uniform Generation from Coin Flips, and Applications
Venue: arXiv cs.DS 2013
Year: 2013

This article introduces an algorithm to draw random discrete uniform variables within a given range of size n from a source of random bits. The algorithm aims to be simple to implement and optimal both with regards to the amount of random bits consumed, and from a computational perspective---allowing for faster and more efficient Monte-Carlo simulations in computational physics and biology. I also provide a detailed analysis of the number of bits that are spent per variate, and offer some extensions and applications, in particular to the optimal random generation of permutations.
A probabilistic algorithm to compute the real dimension of a semi-algebraic set
Venue: arXiv cs.SC 2013
Year: 2013

Let $\RR$ be a real closed field (e.g. the field of real numbers) and $\mathscr{S} \subset \RR^n$ be a semi-algebraic set defined as the set of points in $\RR^n$ satisfying a system of $s$ equalities and inequalities of multivariate polynomials in $n$ variables, of degree at most $D$, with coefficients in an ordered ring $\ZZ$ contained in $\RR$. We consider the problem of computing the {\em real dimension}, $d$, of $\mathscr{S}$. The real dimension is the first topological invariant of interest; it measures the number of degrees of freedom available to move in the set. Thus, computing the real dimension is one of the most important and fundamental problems in computational real algebraic geometry. The problem is ${\rm NP}_{\mathbb{R}}$-complete in the Blum-Shub-Smale model of computation. The current algorithms (probabilistic or deterministic) for computing the real dimension have complexity $(s \, D)^{O(d(n-d))}$, that becomes $(s \, D)^{O(n^2)}$ in the worst-case. The existence of a probabilistic or deterministic algorithm for computing the real dimension with single exponential complexity with a factor better than ${O(n^2)}$ in the exponent in the worst-case, is a longstanding open problem. We provide a positive answer to this problem by introducing a probabilistic algorithm for computing the real dimension of a semi-algebraic set with complexity $(s\, D)^{O(n)}$.
Generalized Reduced-Rank Decompositions Using Switching and Adaptive Algorithms for Space-Time Adaptive Processing
Venue: arXiv cs.IT 2013
Year: 2013

This work presents generalized low-rank signal decompositions with the aid of switching techniques and adaptive algorithms, which do not require eigen-decompositions, for space-time adaptive processing. A generalized scheme is proposed to compute low-rank signal decompositions by imposing suitable constraints on the filtering and by performing iterations between the computed subspace and the low-rank filter. An alternating optimization strategy based on recursive least squares algorithms is presented along with switching and iterations to cost-effectively compute the bases of the decomposition and the low-rank filter. An application to space-time interference suppression in DS-CDMA systems is considered. Simulations show that the proposed scheme and algorithms obtain significant gains in performance over previously reported low-rank schemes.
Interference Suppression and Group-Based Power Adjustment via Alternating Optimization for DS-CDMA Networks with Multihop Relaying
Venue: arXiv cs.IT 2013
Year: 2013

This work presents joint interference suppression and power allocation algorithms for DS-CDMA networks with multiple hops and decode-and-forward (DF) protocols. A scheme for joint allocation of power levels across the relays subject to group-based power constraints and the design of linear receivers for interference suppression is proposed. A constrained minimum mean-squared error (MMSE) design for the receive filters and the power allocation vectors is devised along with an MMSE channel estimator. In order to solve the proposed optimization efficiently, a method to form an effective group of users and an alternating optimization strategy are devised with recursive alternating least squares (RALS) algorithms for estimating the parameters of the receiver, the power allocation and the channels. Simulations show that the proposed algorithms obtain significant gains in capacity and performance over existing schemes.
A Probabilistic Algorithm for Reducing Broadcast Redundancy in Ad Hoc Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

In a wired network, a packet can be transmitted to a specified destination only, no broadcasting required. But in ad hoc wireless network a packet transmitted by a node can reach all neighbors due to broadcasting. This broadcasting introduces unnecessary retransmissions of same message. Therefore, the total number of transmissions (forward nodes) is generally used as the cost criterion for broadcasting. The problem of finding the minimum number of forward nodes is NP-complete. In this paper, the goal is to reduce the number of forward nodes which will reduce redundant transmission as a result. Thus some of approximation approaches are analyzed, especially dominant pruning and total dominant pruning which use 2-hop neighborhood information and a new approach: Probability based algorithm is proposed with a view to minimizing number of forward nodes. Simulation results of applying this algorithm shows performance improvements with compared to dominant pruning and total dominant pruning algorithms.
On sampling SCJ rearrangement scenarios
Venue: arXiv cs.CE 2013
Year: 2013

The Single Cut or Join (SCJ) operation on genomes, generalizing chromosome evolution by fusions and fissions, is the computationally simplest known model of genome rearrangement. While most genome rearrangement problems are already hard when comparing three genomes, it is possible to compute in polynomial time a most parsimonious SCJ scenario for an arbitrary number of genomes related by a binary phylogenetic tree. Here we consider the problems of sampling and counting the most parsimonious SCJ scenarios. We show that both the sampling and counting problems are easy for two genomes, and we relate SCJ scenarios to alternating permutations. However, for an arbitrary number of genomes related by a binary phylogenetic tree, the counting and sampling problems become hard. We prove that if a Fully Polynomial Randomized Approximation Scheme or a Fully Polynomial Almost Uniform Sampler exist for the most parsimonious SCJ scenario, then RP = NP. The proof has a wider scope than genome rearrangements: the same result holds for parsimonious evolutionary scenarios on any set of discrete characters.
Linear codes on posets with extension property
Venue: arXiv cs.IT 2013
Year: 2013

We investigate linear and additive codes in partially ordered Hamming-like spaces that satisfy the extension property, meaning that automorphisms of ideals extend to automorphisms of the poset. The codes are naturally described in terms of translation association schemes that originate from the groups of linear isometries of the space. We address questions of duality and invariants of codes, establishing a connection between the dual association scheme and the scheme defined on the dual poset (they are isomorphic if and only if the poset is self-dual). We further discuss invariants that play the role of weight enumerators of codes in the poset case. In the case of regular rooted trees such invariants are linked to the classical problem of tree isomorphism. We also study the question of whether these invariants are preserved under standard operations on posets such as the ordinal sum and the like.
Probability Distributions Over Possible Worlds
Venue: arXiv cs.AI 2013
Year: 2013

In Probabilistic Logic Nilsson uses the device of a probability distribution over a set of possible worlds to assign probabilities to the sentences of a logical language. In his paper Nilsson concentrated on inference and associated computational issues. This paper, on the other hand, examines the probabilistic semantics in more detail, particularly for the case of first-order languages, and attempts to explain some of the features and limitations of this form of probability logic. It is pointed out that the device of assigning probabilities to logical sentences has certain expressive limitations. In particular, statistical assertions are not easily expressed by such a device. This leads to certain difficulties with attempts to give probabilistic semantics to default reasoning using probabilities assigned to logical sentences.
Uncertainty Management for Fuzzy Decision Support Systems
Venue: arXiv cs.AI 2013
Year: 2013

A new approach for uncertainty management for fuzzy, rule based decision support systems is proposed: The domain expert's knowledge is expressed by a set of rules that frequently refer to vague and uncertain propositions. The certainty of propositions is represented using intervals [a, b] expressing that the proposition's probability is at least a and at most b. Methods and techniques for computing the overall certainty of fuzzy compound propositions that have been defined by using logical connectives 'and', 'or' and 'not' are introduced. Different inference schemas for applying fuzzy rules by using modus ponens are discussed. Different algorithms for combining evidence that has been received from different rules for the same proposition are provided. The relationship of the approach to other approaches is analyzed and its problems of knowledge acquisition and knowledge representation are discussed in some detail. The basic concepts of a rule-based programming language called PICASSO, for which the approach is a theoretical foundation, are outlined.
Probability as a Modal Operator
Venue: arXiv cs.AI 2013
Year: 2013

This paper argues for a modal view of probability. The syntax and semantics of one particularly strong probability logic are discussed and some examples of the use of the logic are provided. We show that it is both natural and useful to think of probability as a modal operator. Contrary to popular belief in AI, a probability ranging between 0 and 1 represents a continuum between impossibility and necessity, not between simple falsity and truth. The present work provides a clear semantics for quantification into the scope of the probability operator and for higher-order probabilities. Probability logic is a language for expressing both probabilistic and logical concepts.
Probabilistic and Non-Monotonic Inference
Venue: arXiv cs.AI 2013
Year: 2013

(l) I have enough evidence to render the sentence S probable. (la) So, relative to what I know, it is rational of me to believe S. (2) Now that I have more evidence, S may no longer be probable. (2a) So now, relative to what I know, it is not rational of me to believe S. These seem a perfectly ordinary, common sense, pair of situations. Generally and vaguely, I take them to embody what I shall call probabilistic inference. This form of inference is clearly non-monotonic. Relatively few people have taken this form of inference, based on high probability, to serve as a foundation for non-monotonic logic or for a logical or defeasible inference. There are exceptions: Jane Nutter [16] thinks that sometimes probability has something to do with non-monotonic reasoning. Judea Pearl [ 17] has recently been exploring the possibility. There are any number of people whom one might call probability enthusiasts who feel that probability provides all the answers by itself, with no need of help from logic. Cheeseman [1], Henrion [5] and others think it useful to look at a distribution of probabilities over a whole algebra of statements, to update that distribution in the light of new evidence, and to use the latest updated distribution of probability over the algebra as a basis for planning and decision making. A slightly weaker form of this approach is captured by Nilsson [15], where one assumes certain probabilities for certain statements, and infers the probabilities, or constraints on the probabilities of other statement. None of this corresponds to what I call probabilistic inference. All of the inference that is taking place, either in Bayesian updating, or in probabilistic logic, is strictly deductive. Deductive inference, particularly that concerned with the distribution of classical probabilities or chances, is of great importance. But this is not to say that there is no important role for what earlier logicians have called "ampliative" or "inductive" or "scientific" inference, in which the conclusion goes beyond the premises, asserts more than do the premises. This depends on what David Israel [6] has called "real rules of inference". It is characteristic of any such logic or inference procedure that it can go wrong: that statements accepted at one point may be rejected at a later point. Research underlying the results reported here has been partially supported by the Signals Warfare Center of the United States Army.
Maintenance in Probabilistic Knowledge-Based Systems
Venue: arXiv cs.AI 2013
Year: 2013

Recent developments using directed acyclical graphs (i.e., influence diagrams and Bayesian networks) for knowledge representation have lessened the problems of using probability in knowledge-based systems (KBS). Most current research involves the efficient propagation of new evidence, but little has been done concerning the maintenance of domain-specific knowledge, which includes the probabilistic information about the problem domain. By making use of conditional independencies represented in she graphs, however, probability assessments are required only for certain variables when the knowledge base is updated. The purpose of this study was to investigate, for those variables which require probability assessments, ways to reduce the amount of new knowledge required from the expert when updating probabilistic information in a probabilistic knowledge-based system. Three special cases (ignored outcome, split outcome, and assumed constraint outcome) were identified under which many of the original probabilities (those already in the knowledge-base) do not need to be reassessed when maintenance is required.
A Linear Approximation Method for Probabilistic Inference
Venue: arXiv cs.AI 2013
Year: 2013

An approximation method is presented for probabilistic inference with continuous random variables. These problems can arise in many practical problems, in particular where there are "second order" probabilities. The approximation, based on the Gaussian influence diagram, iterates over linear approximations to the inference problem.
Handling uncertainty in a system for text-symbol context analysis
Venue: arXiv cs.AI 2013
Year: 2013

In pattern analysis, information regarding an object can often be drawn from its surroundings. This paper presents a method for handling uncertainty when using context of symbols and texts for analyzing technical drawings. The method is based on Dempster-Shafer theory and possibility theory.