OpenRaiser/Intern-Atlas huggingface dataset:
Counterfactual Probabilities: Computational Methods, Bounds and Applications
Venue: arXiv cs.AI 2013
Year: 2013

Evaluation of counterfactual queries (e.g., "If A were true, would C have been true?") is important to fault diagnosis, planning, and determination of liability. In this paper we present methods for computing the probabilities of such queries using the formulation proposed in [Balke and Pearl, 1994], where the antecedent of the query is interpreted as an external action that forces the proposition A to be true. When a prior probability is available on the causal mechanisms governing the domain, counterfactual probabilities can be evaluated precisely. However, when causal knowledge is specified as conditional probabilities on the observables, only bounds can computed. This paper develops techniques for evaluating these bounds, and demonstrates their use in two applications: (1) the determination of treatment efficacy from studies in which subjects may choose their own treatment, and (2) the determination of liability in product-safety litigation.
Approximation Algorithms for the Loop Cutset Problem
Venue: arXiv cs.AI 2013
Year: 2013

We show how to find a small loop curser in a Bayesian network. Finding such a loop cutset is the first step in the method of conditioning for inference. Our algorithm for finding a loop cutset, called MGA, finds a loop cutset which is guaranteed in the worst case to contain less than twice the number of variables contained in a minimum loop cutset. We test MGA on randomly generated graphs and find that the average ratio between the number of instances associated with the algorithms' output and the number of instances associated with a minimum solution is 1.22.
Localized Partial Evaluation of Belief Networks
Venue: arXiv cs.AI 2013
Year: 2013

Most algorithms for propagating evidence through belief networks have been exact and exhaustive: they produce an exact (point-valued) marginal probability for every node in the network. Often, however, an application will not need information about every n ode in the network nor will it need exact probabilities. We present the localized partial evaluation (LPE) propagation algorithm, which computes interval bounds on the marginal probability of a specified query node by examining a subset of the nodes in the entire network. Conceptually, LPE ignores parts of the network that are "too far away" from the queried node to have much impact on its value. LPE has the "anytime" property of being able to produce better solutions (tighter intervals) given more time to consider more of the network.
Some Properties of Joint Probability Distributions
Venue: arXiv cs.AI 2013
Year: 2013

Several Artificial Intelligence schemes for reasoning under uncertainty explore either explicitly or implicitly asymmetries among probabilities of various states of their uncertain domain models. Even though the correct working of these schemes is practically contingent upon the existence of a small number of probable states, no formal justification has been proposed of why this should be the case. This paper attempts to fill this apparent gap by studying asymmetries among probabilities of various states of uncertain models. By rewriting the joint probability distribution over a model's variables into a product of individual variables' prior and conditional probability distributions, and applying central limit theorem to this product, we can demonstrate that the probabilities of individual states of the model can be expected to be drawn from highly skewed, log-normal distributions. With sufficient asymmetry in individual prior and conditional probability distributions, a small fraction of states can be expected to cover a large portion of the total probability space with the remaining states having practically negligible probability. Theoretical discussion is supplemented by simulation results and an illustrative real-world example.
Penalty logic and its Link with Dempster-Shafer Theory
Venue: arXiv cs.AI 2013
Year: 2013

Penalty logic, introduced by Pinkas, associates to each formula of a knowledge base the price to pay if this formula is violated. Penalties may be used as a criterion for selecting preferred consistent subsets in an inconsistent knowledge base, thus inducing a non-monotonic inference relation. A precise formalization and the main properties of penalty logic and of its associated non-monotonic inference relation are given in the first part. We also show that penalty logic and Dempster-Shafer theory are related, especially in the infinitesimal case.
On Modal Logics for Qualitative Possibility in a Fuzzy Setting
Venue: arXiv cs.LO 2013
Year: 2013

Within the possibilistic approach to uncertainty modeling, the paper presents a modal logical system to reason about qualitative (comparative) statements of the possibility (and necessity) of fuzzy propositions. We relate this qualitative modal logic to the many--valued analogues MVS5 and MVKD45 of the well known modal logics of knowledge and belief S5 and KD45 respectively. Completeness results are obtained for such logics and therefore, they extend previous existing results for qualitative possibilistic logics in the classical non-fuzzy setting.
A Logic for Default Reasoning About Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

A logic is defined that allows to express information about statistical probabilities and about degrees of belief in specific propositions. By interpreting the two types of probabilities in one common probability space, the semantics given are well suited to model the influence of statistical information on the formation of subjective beliefs. Cross entropy minimization is a key element in these semantics, the use of which is justified by showing that the resulting logic exhibits some very reasonable properties.
Reduction of Computational Complexity in Bayesian Networks through Removal of Weak Dependencies
Venue: arXiv cs.AI 2013
Year: 2013

The paper presents a method for reducing the computational complexity of Bayesian networks through identification and removal of weak dependencies (removal of links from the (moralized) independence graph). The removal of a small number of links may reduce the computational complexity dramatically, since several fill-ins and moral links may be rendered superfluous by the removal. The method is described in terms of impact on the independence graph, the junction tree, and the potential functions associated with these. An empirical evaluation of the method using large real-world networks demonstrates the applicability of the method. Further, the method, which has been implemented in Hugin, complements the approximation method suggested by Jensen & Andersen (1990).
Induction of Selective Bayesian Classifiers
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we examine previous work on the naive Bayesian classifier and review its limitations, which include a sensitivity to correlated features. We respond to this problem by embedding the naive Bayesian induction scheme within an algorithm that c arries out a greedy search through the space of features. We hypothesize that this approach will improve asymptotic accuracy in domains that involve correlated features without reducing the rate of learning in ones that do not. We report experimental results on six natural domains, including comparisons with decision-tree induction, that support these hypotheses. In closing, we discuss other approaches to extending naive Bayesian classifiers and outline some directions for future research.
Incremental Dynamic Construction of Layered Polytree Networks
Venue: arXiv cs.AI 2013
Year: 2013

Certain classes of problems, including perceptual data understanding, robotics, discovery, and learning, can be represented as incremental, dynamically constructed belief networks. These automatically constructed networks can be dynamically extended and modified as evidence of new individuals becomes available. The main result of this paper is the incremental extension of the singly connected polytree network in such a way that the network retains its singly connected polytree structure after the changes. The algorithm is deterministic and is guaranteed to have a complexity of single node addition that is at most of order proportional to the number of nodes (or size) of the network. Additional speed-up can be achieved by maintaining the path information. Despite its incremental and dynamic nature, the algorithm can also be used for probabilistic inference in belief networks in a fashion similar to other exact inference algorithms.
Exceptional Subclasses in Qualitative Probability
Venue: arXiv cs.AI 2013
Year: 2013

System Z+ [Goldszmidt and Pearl, 1991, Goldszmidt, 1992] is a formalism for reasoning with normality defaults of the form "typically if phi then + (with strength cf)" where 6 is a positive integer. The system has a critical shortcoming in that it does not sanction inheritance across exceptional subclasses. In this paper we propose an extension to System Z+ that rectifies this shortcoming by extracting additional conditions between worlds from the defaults database. We show that the additional constraints do not change the notion of the consistency of a database. We also make comparisons with competing default reasoning systems.
Vandermonde-subspace Frequency Division Multiplexing for Two-Tiered Cognitive Radio Networks
Venue: arXiv cs.IT 2013
Year: 2013

Vandermonde-subspace frequency division multiplexing (VFDM) is an overlay spectrum sharing technique for cognitive radio. VFDM makes use of a precoder based on a Vandermonde structure to transmit information over a secondary system, while keeping an orthogonal frequency division multiplexing (OFDM)-based primary system interference-free. To do so, VFDM exploits frequency selectivity and the use of cyclic prefixes by the primary system. Herein, a global view of VFDM is presented, including also practical aspects such as linear receivers and the impact of channel estimation. We show that VFDM provides a spectral efficiency increase of up to 1 bps/Hz over cognitive radio systems based on unused band detection. We also present some key design parameters for its future implementation and a feasible channel estimation protocol. Finally we show that, even when some of the theoretical assumptions are relaxed, VFDM provides non-negligible rates while protecting the primary system.
Shortest Path versus Multi-Hub Routing in Networks with Uncertain Demand
Venue: arXiv cs.NI 2013
Year: 2013

We study a class of robust network design problems motivated by the need to scale core networks to meet increasingly dynamic capacity demands. Past work has focused on designing the network to support all hose matrices (all matrices not exceeding marginal bounds at the nodes). This model may be too conservative if additional information on traffic patterns is available. Another extreme is the fixed demand model, where one designs the network to support peak point-to-point demands. We introduce a capped hose model to explore a broader range of traffic matrices which includes the above two as special cases. It is known that optimal designs for the hose model are always determined by single-hub routing, and for the fixed- demand model are based on shortest-path routing. We shed light on the wider space of capped hose matrices in order to see which traffic models are more shortest path-like as opposed to hub-like. To address the space in between, we use hierarchical multi-hub routing templates, a generalization of hub and tree routing. In particular, we show that by adding peak capacities into the hose model, the single-hub tree-routing template is no longer cost-effective. This initiates the study of a class of robust network design (RND) problems restricted to these templates. Our empirical analysis is based on a heuristic for this new hierarchical RND problem. We also propose that it is possible to define a routing indicator that accounts for the strengths of the marginals and peak demands and use this information to choose the appropriate routing template. We benchmark our approach against other well-known routing templates, using representative carrier networks and a variety of different capped hose traffic demands, parameterized by the relative importance of their marginals as opposed to their point-to-point peak demands.
Sound localization using compressive sensing
Venue: arXiv cs.SD 2013
Year: 2013

In a sensor network with remote sensor devices, it is important to have a method that can accurately localize a sound event with a small amount of data transmitted from the sensors. In this paper, we propose a novel method for localization of a sound source using compressive sensing. Instead of sampling a large amount of data at the Nyquist sampling rate in time domain, the acoustic sensors take compressive measurements integrated in time. The compressive measurements can be used to accurately compute the location of a sound source.
Continuous-time Infinite Dynamic Topic Models
Venue: arXiv cs.IR 2013
Year: 2013

Topic models are probabilistic models for discovering topical themes in collections of documents. In real world applications, these models provide us with the means of organizing what would otherwise be unstructured collections. They can help us cluster a huge collection into different topics or find a subset of the collection that resembles the topical theme found in an article at hand. The first wave of topic models developed were able to discover the prevailing topics in a big collection of documents spanning a period of time. It was later realized that these time-invariant models were not capable of modeling 1) the time varying number of topics they discover and 2) the time changing structure of these topics. Few models were developed to address this two deficiencies. The online-hierarchical Dirichlet process models the documents with a time varying number of topics. It varies the structure of the topics over time as well. However, it relies on document order, not timestamps to evolve the model over time. The continuous-time dynamic topic model evolves topic structure in continuous-time. However, it uses a fixed number of topics over time. In this dissertation, I present a model, the continuous-time infinite dynamic topic model, that combines the advantages of these two models 1) the online-hierarchical Dirichlet process, and 2) the continuous-time dynamic topic model. More specifically, the model I present is a probabilistic topic model that does the following: 1) it changes the number of topics over continuous time, and 2) it changes the topic structure over continuous-time. I compared the model I developed with the two other models with different setting values. The results obtained were favorable to my model and showed the need for having a model that has a continuous-time varying number of topics and topic structure.
Adaptive Modulation (QPSK, QAM)
Venue: arXiv cs.OH 2013
Year: 2013

In this paper, introduced below are the concepts of digital modulation used in many communication systems today. Techniques described include quadrature phase shift keying (QPSK) and quadrature amplitude modulation (QAM) and how these techniques can be used to increase the capacity and speed of a wireless network. These modulation techniques are the basis of communications for systems like cable modems, DSL modems, CDMA, 3G, Wi-Fi* (IEEE 802.11) and WiMAX* (IEEE 802.16).
Source Separation using Regularized NMF with MMSE Estimates under GMM Priors with Online Learning for The Uncertainties
Venue: arXiv cs.LG 2013
Year: 2013

We propose a new method to enforce priors on the solution of the nonnegative matrix factorization (NMF). The proposed algorithm can be used for denoising or single-channel source separation (SCSS) applications. The NMF solution is guided to follow the Minimum Mean Square Error (MMSE) estimates under Gaussian mixture prior models (GMM) for the source signal. In SCSS applications, the spectra of the observed mixed signal are decomposed as a weighted linear combination of trained basis vectors for each source using NMF. In this work, the NMF decomposition weight matrices are treated as a distorted image by a distortion operator, which is learned directly from the observed signals. The MMSE estimate of the weights matrix under GMM prior and log-normal distribution for the distortion is then found to improve the NMF decomposition results. The MMSE estimate is embedded within the optimization objective to form a novel regularized NMF cost function. The corresponding update rules for the new objectives are derived in this paper. Experimental results show that, the proposed regularized NMF algorithm improves the source separation performance compared with using NMF without prior or with other prior models.
An $O^*(1.1939^n)$ time algorithm for minimum weighted dominating induced matching
Venue: arXiv cs.DS 2013
Year: 2013

Say that an edge of a graph $G$ dominates itself and every other edge adjacent to it. An edge dominating set of a graph $G=(V,E)$ is a subset of edges $E' \subseteq E$ which dominates all edges of $G$. In particular, if every edge of $G$ is dominated by exactly one edge of $E'$ then $E'$ is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighted dominating induced matching, if any, and counting the number of dominating induced matchings of a graph with weighted edges. We describe an exact algorithm for general graphs that runs in $O^*(1.1939^n)$ time and polynomial (linear) space. This improves over any existing exact algorithm for the problems in consideration.
A Cooperative MARC Scheme Using Analogue Network Coding to Achieve Second-Order Diversity
Venue: arXiv cs.IT 2013
Year: 2013

A multiple access relay channel (MARC) is considered in which an analogue-like network coding is implemented in the relay node. This analogue coding is a simple addition of the received signals at the relay node. Using "nulling detection" structure employed in V-BLAST receiver, we propose a detection scheme in the destination which is able to provide a diversity order of two for all users. We analytically evaluate the performance of our proposed scheme for the MARC with two users where tight upper bounds for both uncoded and Convolutionally coded transmission blocks are provided. We verify our analytical evaluations by simulations and compare the results with those of noncooperative transmission and Alamouti's scheme for the same power and rate transmission. Our results indicate that while our proposed scheme shows a comparable performance compared to the Alamouti's scheme, it substantially outperforms the non-cooperate transmission.
Label-dependent Feature Extraction in Social Networks for Node Classification
Venue: arXiv cs.SI 2013
Year: 2013

A new method of feature extraction in the social network for within-network classification is proposed in the paper. The method provides new features calculated by combination of both: network structure information and class labels assigned to nodes. The influence of various features on classification performance has also been studied. The experiments on real-world data have shown that features created owing to the proposed method can lead to significant improvement of classification accuracy.
AutoSynch: An Automatic-Signal Monitor Based on Predicate Tagging
Venue: arXiv cs.DC 2013
Year: 2013

Most programming languages use monitors with explicit signals for synchronization in shared-memory programs. Requiring program- mers to signal threads explicitly results in many concurrency bugs due to missed notifications, or notifications on wrong condition variables. In this paper, we describe an implementation of an au- tomatic signaling monitor in Java called AutoSynch that eliminates such concurrency bugs by removing the burden of signaling from the programmer. We show that the belief that automatic signaling monitors are prohibitively expensive is wrong. For most problems, programs based on AutoSynch are almost as fast as those based on explicit signaling. For some, AutoSynch is even faster than explicit signaling because it never uses signalAll, whereas the programmers end up using signalAll with the explicit signal mechanism. AutoSynch achieves efficiency in synchronization based on three novel ideas. We introduce an operation called globalization that enables the predicate evaluation in every thread, thereby reducing context switches during the execution of the program. Secondly, AutoSynch avoids signalAll by using a property called relay invari- ance that guarantees that whenever possible there is always at least one thread whose condition is true which has been signaled. Finally, AutoSynch uses a technique called predicate tagging to efficiently determine a thread that should be signaled. To evaluate the effi- ciency of AutoSynch, we have implemented many different well- known synchronization problems such as the producers/consumers problem, the readers/writers problems, and the dining philosophers problem. The results show that AutoSynch is almost as efficient as the explicit-signal monitor and even more efficient for some cases.
Structure-semantics interplay in complex networks and its effects on the predictability of similarity in texts
Venue: arXiv cs.CL 2013
Year: 2013

There are different ways to define similarity for grouping similar texts into clusters, as the concept of similarity may depend on the purpose of the task. For instance, in topic extraction similar texts mean those within the same semantic field, whereas in author recognition stylistic features should be considered. In this study, we introduce ways to classify texts employing concepts of complex networks, which may be able to capture syntactic, semantic and even pragmatic features. The interplay between the various metrics of the complex networks is analyzed with three applications, namely identification of machine translation (MT) systems, evaluation of quality of machine translated texts and authorship recognition. We shall show that topological features of the networks representing texts can enhance the ability to identify MT systems in particular cases. For evaluating the quality of MT texts, on the other hand, high correlation was obtained with methods capable of capturing the semantics. This was expected because the golden standards used are themselves based on word co-occurrence. Notwithstanding, the Katz similarity, which involves semantic and structure in the comparison of texts, achieved the highest correlation with the NIST measurement, indicating that in some cases the combination of both approaches can improve the ability to quantify quality in MT. In authorship recognition, again the topological features were relevant in some contexts, though for the books and authors analyzed good results were obtained with semantic features as well. Because hybrid approaches encompassing semantic and topological features have not been extensively used, we believe that the methodology proposed here may be useful to enhance text classification considerably, as it combines well-established strategies.
Audit Games
Venue: arXiv cs.GT 2013
Year: 2013

Effective enforcement of laws and policies requires expending resources to prevent and detect offenders, as well as appropriate punishment schemes to deter violators. In particular, enforcement of privacy laws and policies in modern organizations that hold large volumes of personal information (e.g., hospitals, banks, and Web services providers) relies heavily on internal audit mechanisms. We study economic considerations in the design of these mechanisms, focusing in particular on effective resource allocation and appropriate punishment schemes. We present an audit game model that is a natural generalization of a standard security game model for resource allocation with an additional punishment parameter. Computing the Stackelberg equilibrium for this game is challenging because it involves solving an optimization problem with non-convex quadratic constraints. We present an additive FPTAS that efficiently computes a solution that is arbitrarily close to the optimal solution.