OpenRaiser/Intern-Atlas huggingface dataset:
Probabilistic Evaluation of Candidates and Symptom Clustering for Multidisorder Diagnosis
Venue: arXiv cs.AI 2013
Year: 2013

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.
Refinement and Coarsening of Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

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.
Computing Probability Intervals Under Independency Constraints
Venue: arXiv cs.AI 2013
Year: 2013

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.
Default Reasoning and the Transferable Belief Model
Venue: arXiv cs.AI 2013
Year: 2013

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.
Fourier-Reflexive Partitions and MacWilliams Identities for Additive Codes
Venue: arXiv cs.IT 2013
Year: 2013

A partition of a finite abelian group gives rise to a dual partition on the character group via the Fourier transform. Properties of the dual partitions are investigated and a convenient test is given for the case that the bidual partition coincides the primal partition. Such partitions permit MacWilliams identities for the partition enumerators of additive codes. It is shown that dualization commutes with taking products and symmetrized products of partitions on cartesian powers of the given group. After translating the results to Frobenius rings, which are identified with their character module, the approach is applied to partitions that arise from poset structures.
Fourier sparsity, spectral norm, and the Log-rank conjecture
Venue: arXiv cs.CC 2013
Year: 2013

We study Boolean functions with sparse Fourier coefficients or small spectral norm, and show their applications to the Log-rank Conjecture for XOR functions f(x\oplus y) --- a fairly large class of functions including well studied ones such as Equality and Hamming Distance. The rank of the communication matrix M_f for such functions is exactly the Fourier sparsity of f. Let d be the F2-degree of f and D^CC(f) stand for the deterministic communication complexity for f(x\oplus y). We show that 1. D^CC(f) = O(2^{d^2/2} log^{d-2} ||\hat f||_1). In particular, the Log-rank conjecture holds for XOR functions with constant F2-degree. 2. D^CC(f) = O(d ||\hat f||_1) = O(\sqrt{rank(M_f)}\logrank(M_f)). We obtain our results through a degree-reduction protocol based on a variant of polynomial rank, and actually conjecture that its communication cost is already \log^{O(1)}rank(M_f). The above bounds also hold for the parity decision tree complexity of f, a measure that is no less than the communication complexity (up to a factor of 2). Along the way we also show several structural results about Boolean functions with small F2-degree or small spectral norm, which could be of independent interest. For functions f with constant F2-degree: 1) f can be written as the summation of quasi-polynomially many indicator functions of subspaces with \pm-signs, improving the previous doubly exponential upper bound by Green and Sanders; 2) being sparse in Fourier domain is polynomially equivalent to having a small parity decision tree complexity; 3) f depends only on polylog||\hat f||_1 linear functions of input variables. For functions f with small spectral norm: 1) there is an affine subspace with co-dimension O(||\hat f||_1) on which f is a constant; 2) there is a parity decision tree with depth O(||\hat f||_1 log ||\hat f||_0).
On the structure of the class NP
Venue: arXiv cs.CC 2013
Year: 2013

A new class UF of problems is introduced, strictly included in the class NP, which arises in the analysis of the time verifying the intermediate results of computations. The implications of the introduction of this class are considered. First of all, we prove that $P\not= NP$ and establish that it needs to consider the problem "P vs UF" instead the problem "P vs NP". Also, we determine the set-theoretical of properties of a one-way functions that used in cryptology.
Domain Specific Language for Geometric Relations between Rigid Bodies targeted to robotic applications
Venue: arXiv cs.RO 2013
Year: 2013

This paper presents a DSL for geometric relations between rigid bodies such as relative position, orientation, pose, linear velocity, angular velocity, and twist. The DSL is the formal model of the recently proposed semantics for the standardization of geometric relations between rigid bodies, referred to as `geometric semantics'. This semantics explicitly states the coordinate-invariant properties and operations, and, more importantly, all the choices that are made in coordinate representations of these geometric relations. This results in a set of concrete suggestions for standardizing terminology and notation, allowing programmers to write fully unambiguous software interfaces, including automatic checks for semantic correctness of all geometric operations on rigid-body coordinate representations. The DSL is implemented in two different ways: an external DSL in Xcore and an internal DSL in Prolog. Besides defining a grammar and operations, the DSL also implements constraints. In the Xcore model, the Object Constraint Language language is used, while in the Prolog model, the constraint are natively modelled in Prolog. This paper discusses the implemented DSL and the tools developed on top of this DSL. In particular an editor, checking the semantic constraints and providing semantic meaningful errors during editing is proposed.
Integration of spatio-temporal contrast sensitivity with a multi-slice channelized Hotelling observer
Venue: arXiv cs.CV 2013
Year: 2013

Barten's model of spatio-temporal contrast sensitivity function of human visual system is embedded in a multi-slice channelized Hotelling observer. This is done by 3D filtering of the stack of images with the spatio-temporal contrast sensitivity function and feeding the result (i.e., the perceived image stack) to the multi-slice channelized Hotelling observer. The proposed procedure of considering spatio-temporal contrast sensitivity function is generic in the sense that it can be used with observers other than multi-slice channelized Hotelling observer. Detection performance of the new observer in digital breast tomosynthesis is measured in a variety of browsing speeds, at two spatial sampling rates, using computer simulations. Our results show a peak in detection performance in mid browsing speeds. We compare our results to those of a human observer study reported earlier (I. Diaz et al. SPIE MI 2011). The effects of display luminance, contrast and spatial sampling rate, with and without considering foveal vision, are also studied. Reported simulations are conducted with real digital breast tomosynthesis image stacks, as well as stacks from an anthropomorphic software breast phantom (P. Bakic et al. Med Phys. 2011). Lesion cases are simulated by inserting single micro-calcifications or masses. Limitations of our methods and ways to improve them are discussed.
Interference Alignment with Diversity for the $2 \times 2$ $X$ Network with four antennas
Venue: arXiv cs.IT 2013
Year: 2013

A transmission scheme based on the Alamouti code, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was recently proposed for the $2 \times 2$ $X$ Network (i.e., two-transmitter (Tx) two-receiver (Rx) $X$ Network) with two antennas at each node. This scheme was claimed to achieve a sum degrees of freedom (DoF) of $\frac{8}{3}$ and also a diversity gain of two when fixed finite constellations are employed at each Tx. Furthermore, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of $\frac{8}{3}$. In this paper, we extend the LJJ scheme to the $2 \times 2$ $X$ Network with four antennas at each node. The proposed scheme also assumes only local channel knowledge at each Tx. We prove that the proposed scheme achieves the maximum possible sum DoF of $\frac{16}{3}$. In addition, we also prove that, using any fixed finite constellation with appropriate rotation at each Tx, the proposed scheme achieves a diversity gain of at least four.
Temporal Reasoning with Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

In this paper we explore representations of temporal knowledge based upon the formalism of Causal Probabilistic Networks (CPNs). Two different ?continuous-time? representations are proposed. In the first, the CPN includes variables representing ?event-occurrence times?, possibly on different time scales, and variables representing the ?state? of the system at these times. In the second, the CPN describes the influences between random variables with values in () representing dates, i.e. time-points associated with the occurrence of relevant events. However, structuring a system of inter-related dates as a network where all links commit to a single specific notion of cause and effect is in general far from trivial and leads to severe difficulties. We claim that we should recognize explicitly different kinds of relation between dates, such as ?cause?, ?inhibition?, ?competition?, etc., and propose a method whereby these relations are coherently embedded in a CPN using additional auxiliary nodes corresponding to "instrumental" variables. Also discussed, though not covered in detail, is the topic concerning how the quantitative specifications to be inserted in a temporal CPN can be learned from specific data.
Automated Reasoning Using Possibilistic Logic: Semantics, Belief Revision and Variable Certainty Weights
Venue: arXiv cs.AI 2013
Year: 2013

In this paper an approach to automated deduction under uncertainty,based on possibilistic logic, is proposed ; for that purpose we deal with clauses weighted by a degree which is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the refutation method can be generalized. Besides the lower bounds are allowed to be functions of variables involved in the clause, which gives hypothetical reasoning capabilities. The relation between our approach and the idea of minimizing abnormality is briefly discussed. In case where only lower bounds of necessity measures are involved, a semantics is proposed, in which the completeness of the extended resolution principle is proved. Moreover deduction from a partially inconsistent knowledge base can be managed in this approach and displays some form of non-monotonicity.
How Much More Probable is "Much More Probable"? Verbal Expressions for Probability Updates
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian inference systems should be able to explain their reasoning to users, translating from numerical to natural language. Previous empirical work has investigated the correspondence between absolute probabilities and linguistic phrases. This study extends that work to the correspondence between changes in probabilities (updates) and relative probability phrases, such as "much more likely" or "a little less likely." Subjects selected such phrases to best describe numerical probability updates. We examined three hypotheses about the correspondence, and found the most descriptively accurate of these three to be that each such phrase corresponds to a fixed difference in probability (rather than fixed ratio of probabilities or of odds). The empirically derived phrase selection function uses eight phrases and achieved a 72% accuracy in correspondence with the subjects' actual usage.
Shootout-89: A Comparative Evaluation of Knowledge-based Systems that Forecast Severe Weather
Venue: arXiv cs.AI 2013
Year: 2013

During the summer of 1989, the Forecast Systems Laboratory of the National Oceanic and Atmospheric Administration sponsored an evaluation of artificial intelligence-based systems that forecast severe convective storms. The evaluation experiment, called Shootout-89, took place in Boulder, and focussed on storms over the northeastern Colorado foothills and plains (Moninger, et al., 1990). Six systems participated in Shootout-89. These included traditional expert systems, an analogy-based system, and a system developed using methods from the cognitive science/judgment analysis tradition. Each day of the exercise, the systems generated 2 to 9 hour forecasts of the probabilities of occurrence of: non significant weather, significant weather, and severe weather, in each of four regions in northeastern Colorado. A verification coordinator working at the Denver Weather Service Forecast Office gathered ground-truth data from a network of observers. Systems were evaluated on the basis of several measures of forecast skill, and on other metrics such as timeliness, ease of learning, and ease of use. Systems were generally easy to operate, however the various systems required substantially different levels of meteorological expertise on the part of their users--reflecting the various operational environments for which the systems had been designed. Systems varied in their statistical behavior, but on this difficult forecast problem, the systems generally showed a skill approximately equal to that of persistence forecasts and climatological (historical frequency) forecasts. The two systems that appeared best able to discriminate significant from non significant weather events were traditional expert systems. Both of these systems required the operator to make relatively sophisticated meteorological judgments. We are unable, based on only one summer's worth of data, to determine the extent to which the greater skill of the two systems was due to the content of their knowledge bases, or to the subjective judgments of the operator. A follow-on experiment, Shootout-91, is currently being planned. Interested potential participants are encouraged to contact the author at the address above.
Evidence Absorption and Propagation through Evidence Reversals
Venue: arXiv cs.AI 2013
Year: 2013

The arc reversal/node reduction approach to probabilistic inference is extended to include the case of instantiated evidence by an operation called "evidence reversal." This not only provides a technique for computing posterior joint distributions on general belief networks, but also provides insight into the methods of Pearl [1986b] and Lauritzen and Spiegelhalter [1988]. Although it is well understood that the latter two algorithms are closely related, in fact all three algorithms are identical whenever the belief network is a forest.
Can Uncertainty Management be Realized in a Finite Totally Ordered Probability Algebra?
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, the feasibility of using finite totally ordered probability models under Alelinnas's Theory of Probabilistic Logic [Aleliunas, 1988] is investigated. The general form of the probability algebra of these models is derived and the number of possible algebras with given size is deduced. Based on this analysis, we discuss problems of denominator-indifference and ambiguity-generation that arise in reasoning by cases and abductive reasoning. An example is given that illustrates how these problems arise. The investigation shows that a finite probability model may be of very limited usage.
Large-Treewidth Graph Decompositions and Applications
Venue: arXiv cs.DS 2013
Year: 2013

Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph $G$ into node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs $h$, and the desired lower bound $r$ on the treewidth of each subgraph. The theorems assert that, given a graph $G$ with treewidth $k$, a decomposition with parameters $h,r$ is feasible whenever $hr^2 \le k/\polylog(k)$, or $h^3r \le k/\polylog(k)$ holds. We then show a framework for using these theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster algorithms for a class of fixed-parameter tractable problems.
Interference-Aware Resource Control in Multi-Antenna Cognitive Ad Hoc Networks with Heterogeneous Delay Constraints
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we consider a multi-antenna cognitive ad hoc network (CAHNet) with heterogeneous delay requirements. To fulfill the interference and delay constraints simultaneously, we propose to perform adaptive zero-forcing beamforming (ZFBF) at cognitive transmitters according to interference channel state information (CSI). To assist the CAHNet to obtain the interference CSI, we use a win-win inter-network cooperation strategy, namely quantized interference CSI feedback from the primary network to CAHNet through a feedback link, under the condition that the CAHNet pays a proper price for it. Considering the scarcity of feedback and power resources, we focus on the minimization of the overall resource cost subject to both interference and delay constraints. To solve the problem, we derive a joint feedback and power control algorithm amongst multiple links of CAHNet. Finally, simulation results validate the effectiveness of the proposed algorithm.
Simulated Car Racing Championship: Competition Software Manual
Venue: arXiv cs.AI 2013
Year: 2013

This manual describes the competition software for the Simulated Car Racing Championship, an international competition held at major conferences in the field of Evolutionary Computation and in the field of Computational Intelligence and Games. It provides an overview of the architecture, the instructions to install the software and to run the simple drivers provided in the package, the description of the sensors and the actuators.
Network Coding for Energy-Efficient Distributed Storage System in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

A network coding-based scheme is proposed to improve the energy efficiency of distributed storage systems in WSNs (wireless sensor networks), which mainly focuses on two problems: firstly, consideration is given to effective distributed storage technology in WSNs; secondly, we address how to repair the data in failed storage nodes with less resource. For the first problem, we propose a method to obtain a sparse generator matrix to construct network codes, and this sparse generator matrix is proven to be the sparsest. Benefiting from the sparse generator matrix, the energy consumption required to implement distributed storage is reduced. For the second problem, we designed a network coding-based iterative repair method, which adequately utilizes the idea of re-encoding at intermediate nodes from network coding theory. Benefiting from the re-encoding, the energy consumption required by data repair is significantly reduced. Moreover, we provide an explicit lower bound of field size required by this scheme, which implies that this scheme can work over a very small field and the required computation overhead of coding is very low. The simulation result verifies that by using our scheme, the total energy consumption required to implement distributed storage system in WSNs can be reduced on the one hand, and on the other hand, this method can also balance energy consumption of the networks.
Harmonic analysis and a bentness-like notion in certain finite Abelian groups over some finite fields
Venue: arXiv cs.CR 2013
Year: 2013

It is well-known that degree two finite field extensions can be equipped with a Hermitian-like structure similar to the extension of the complex field over the reals. In this contribution, using this structure, we develop a modular character theory and the appropriate Fourier transform for some particular kind of finite Abelian groups. Moreover we introduce the notion of bent functions for finite field valued functions rather than usual complex-valued functions, and we study several of their properties. In particular we prove that this bentness notion is a consequence of that of Logachev, Salnikov and Yashchenko, introduced in "Bent functions on a finite Abelian group" (1997). In addition this new bentness notion is also generalized to a vectorial setting.