OpenRaiser/Intern-Atlas huggingface dataset:
Fundamental Inequalities and Identities Involving Mutual and Directed Informations in Closed-Loop Systems
Venue: arXiv cs.IT 2013
Year: 2013

We present several novel identities and inequalities relating the mutual information and the directed information in systems with feedback. The internal blocks within such systems are restricted only to be causal mappings, but are allowed to be non-linear, stochastic and time varying. Moreover, the involved signals can be arbitrarily distributed. We bound the directed information between signals inside the feedback loop by the mutual information between signals inside and outside the feedback loop. This fundamental result has an interesting interpretation as a law of conservation of information flow. Building upon it, we derive several novel identities and inequalities, which allow us to prove some existing information inequalities under less restrictive assumptions. Finally, we establish new relationships between nested directed informations inside a feedback loop. This yields a new and general data-processing inequality for systems with feedback.
Delay Minimization in Varying-Bandwidth Direct Multicast with Side Information
Venue: arXiv cs.IT 2013
Year: 2013

We study the delay minimization in a direct multicast communication scheme where a base station wishes to transmit a set of original packets to a group of clients. Each of the clients already has in its cache a subset of the original packets, and requests for all the remaining packets. The base station communicates directly with the clients by broadcasting information to them. Assume that bandwidths vary between the station and different clients. We propose a method to minimize the total delay required for the base station to satisfy requests from all clients.
To Obtain or not to Obtain CSI in the Presence of Hybrid Adversary
Venue: arXiv cs.IT 2013
Year: 2013

We consider the wiretap channel model under the presence of a hybrid, half duplex adversary that is capable of either jamming or eavesdropping at a given time. We analyzed the achievable rates under a variety of scenarios involving different methods for obtaining transmitter CSI. Each method provides a different grade of information, not only to the transmitter on the main channel, but also to the adversary on all channels. Our analysis shows that main CSI is more valuable for the adversary than the jamming CSI in both delay-limited and ergodic scenarios. Similarly, in certain cases under the ergodic scenario, interestingly, no CSI may lead to higher achievable secrecy rates than with CSI.
ω-Petri nets
Venue: arXiv cs.LO 2013
Year: 2013

We introduce ω-Petri nets (ωPN), an extension of plain Petri nets with ω-labeled input and output arcs, that is well-suited to analyse parametric concurrent systems with dynamic thread creation. Most techniques (such as the Karp and Miller tree or the Rackoff technique) that have been proposed in the setting of plain Petri nets do not apply directly to ωPN because ωPN define transition systems that have infinite branching. This motivates a thorough analysis of the computational aspects of ωPN. We show that an ωPN can be turned into an plain Petri net that allows to recover the reachability set of the ωPN, but that does not preserve termination. This yields complexity bounds for the reachability, (place) boundedness and coverability problems on ωPN. We provide a practical algorithm to compute a coverability set of the ωPN and to decide termination by adapting the classical Karp and Miller tree construction. We also adapt the Rackoff technique to ωPN, to obtain the exact complexity of the termination problem. Finally, we consider the extension of ωPN with reset and transfer arcs, and show how this extension impacts the decidability and complexity of the aforementioned problems.
An Upper Bound on the Capacity of non-Binary Deletion Channels
Venue: arXiv cs.IT 2013
Year: 2013

We derive an upper bound on the capacity of non-binary deletion channels. Although binary deletion channels have received significant attention over the years, and many upper and lower bounds on their capacity have been derived, such studies for the non-binary case are largely missing. The state of the art is the following: as a trivial upper bound, capacity of an erasure channel with the same input alphabet as the deletion channel can be used, and as a lower bound the results by Diggavi and Grossglauser are available. In this paper, we derive the first non-trivial non-binary deletion channel capacity upper bound and reduce the gap with the existing achievable rates. To derive the results we first prove an inequality between the capacity of a 2K-ary deletion channel with deletion probability $d$, denoted by $C_{2K}(d)$, and the capacity of the binary deletion channel with the same deletion probability, $C_2(d)$, that is, $C_{2K}(d)\leq C_2(d)+(1-d)\log(K)$. Then by employing some existing upper bounds on the capacity of the binary deletion channel, we obtain upper bounds on the capacity of the 2K-ary deletion channel. We illustrate via examples the use of the new bounds and discuss their asymptotic behavior as $d \rightarrow 0$.
Simplifying the Configuration of 802.11 Wireless Networks with Effective SNR
Venue: arXiv cs.NI 2013
Year: 2013

Advances in the price, performance, and power consumption of Wi-Fi (IEEE 802.11) technology have led to the adoption of wireless functionality in diverse consumer electronics. These trends have enabled an exciting vision of rich wireless applications that combine the unique features of different devices for a better user experience. To meet the needs of these applications, a wireless network must be configured well to provide good performance at the physical layer. But because of wireless technology and usage trends, finding these configurations is an increasingly challenging problem. Wireless configuration objectives range from simply choosing the fastest way to encode data on a single wireless link to the global optimization of many interacting parameters over multiple sets of communicating devices. As more links are involved, as technology advances (e.g., the adoption of OFDM and MIMO techniques in Wi-Fi), and as devices are used in changing wireless channels, the size of the configuration space grows. Thus algorithms must find good operating points among a growing number of options. ... continued inside thesis.
Image registration with sparse approximations in parametric dictionaries
Venue: arXiv cs.CV 2013
Year: 2013

We examine in this paper the problem of image registration from the new perspective where images are given by sparse approximations in parametric dictionaries of geometric functions. We propose a registration algorithm that looks for an estimate of the global transformation between sparse images by examining the set of relative geometrical transformations between the respective features. We propose a theoretical analysis of our registration algorithm and we derive performance guarantees based on two novel important properties of redundant dictionaries, namely the robust linear independence and the transformation inconsistency. We propose several illustrations and insights about the importance of these dictionary properties and show that common properties such as coherence or restricted isometry property fail to provide sufficient information in registration problems. We finally show with illustrative experiments on simple visual objects and handwritten digits images that our algorithm outperforms baseline competitor methods in terms of transformation-invariant distance computation and classification.
Generalized Bregman Divergence and Gradient of Mutual Information for Vector Poisson Channels
Venue: arXiv cs.IT 2013
Year: 2013

We investigate connections between information-theoretic and estimation-theoretic quantities in vector Poisson channel models. In particular, we generalize the gradient of mutual information with respect to key system parameters from the scalar to the vector Poisson channel model. We also propose, as another contribution, a generalization of the classical Bregman divergence that offers a means to encapsulate under a unifying framework the gradient of mutual information results for scalar and vector Poisson and Gaussian channel models. The so-called generalized Bregman divergence is also shown to exhibit various properties akin to the properties of the classical version. The vector Poisson channel model is drawing considerable attention in view of its application in various domains: as an example, the availability of the gradient of mutual information can be used in conjunction with gradient descent methods to effect compressive-sensing projection designs in emerging X-ray and document classification applications.
An Application of Uncertain Reasoning to Requirements Engineering
Venue: arXiv cs.SE 2013
Year: 2013

This paper examines the use of Bayesian Networks to tackle one of the tougher problems in requirements engineering, translating user requirements into system requirements. The approach taken is to model domain knowledge as Bayesian Network fragments that are glued together to form a complete view of the domain specific system requirements. User requirements are introduced as evidence and the propagation of belief is used to determine what are the appropriate system requirements as indicated by user requirements. This concept has been demonstrated in the development of a system specification and the results are presented here.
Loglinear models for first-order probabilistic reasoning
Venue: arXiv cs.AI 2013
Year: 2013

Recent work on loglinear models in probabilistic constraint logic programming is applied to first-order probabilistic reasoning. Probabilities are defined directly on the proofs of atomic formulae, and by marginalisation on the atomic formulae themselves. We use Stochastic Logic Programs (SLPs) composed of labelled and unlabelled definite clauses to define the proof probabilities. We have a conservative extension of first-order reasoning, so that, for example, there is a one-one mapping between logical and random variables. We show how, in this framework, Inductive Logic Programming (ILP) can be used to induce the features of a loglinear model from data. We also compare the presented framework with other approaches to first-order probabilistic reasoning.
A New Model of Plan Recognition
Venue: arXiv cs.AI 2013
Year: 2013

We present a new abductive, probabilistic theory of plan recognition. This model differs from previous plan recognition theories in being centered around a model of plan execution: most previous methods have been based on plans as formal objects or on rules describing the recognition process. We show that our new model accounts for phenomena omitted from most previous plan recognition theories: notably the cumulative effect of a sequence of observations of partially-ordered, interleaved plans and the effect of context on plan adoption. The model also supports inferences about the evolution of plan execution in situations where another agent intervenes in plan execution. This facility provides support for using plan recognition to build systems that will intelligently assist a user.
Multi-objects association in perception of dynamical situation
Venue: arXiv cs.AI 2013
Year: 2013

In current perception systems applied to the rebuilding of the environment for intelligent vehicles, the part reserved to object association for the tracking is increasingly significant. This allows firstly to follow the objects temporal evolution and secondly to increase the reliability of environment perception. We propose in this communication the development of a multi-objects association algorithm with ambiguity removal entering into the design of such a dynamic perception system for intelligent vehicles. This algorithm uses the belief theory and data modelling with fuzzy mathematics in order to be able to handle inaccurate as well as uncertain information due to imperfect sensors. These theories also allow the fusion of numerical as well as symbolic data. We develop in this article the problem of matching between known and perceived objects. This makes it possible to update a dynamic environment map for a vehicle. The belief theory will enable us to quantify the belief in the association of each perceived object with each known object. Conflicts can appear in the case of object appearance or disappearance, or in the case of a confused situation or bad perception. These conflicts are removed or solved using an assignment algorithm, giving a solution called the " best " and so ensuring the tracking of some objects present in our environment.
A Hybrid Approach to Reasoning with Partially Elicited Preference Models
Venue: arXiv cs.AI 2013
Year: 2013

Classical Decision Theory provides a normative framework for representing and reasoning about complex preferences. Straightforward application of this theory to automate decision making is difficult due to high elicitation cost. In response to this problem, researchers have recently developed a number of qualitative, logic-oriented approaches for representing and reasoning about references. While effectively addressing some expressiveness issues, these logics have not proven powerful enough for building practical automated decision making systems. In this paper we present a hybrid approach to preference elicitation and decision making that is grounded in classical multi-attribute utility theory, but can make effective use of the expressive power of qualitative approaches. Specifically, assuming a partially specified multilinear utility function, we show how comparative statements about classes of decision alternatives can be used to further constrain the utility function and thus identify sup-optimal alternatives. This work demonstrates that quantitative and qualitative approaches can be synergistically integrated to provide effective and flexible decision support.
Estimating the Value of Computation in Flexible Information Refinement
Venue: arXiv cs.AI 2013
Year: 2013

We outline a method to estimate the value of computation for a flexible algorithm using empirical data. To determine a reasonable trade-off between cost and value, we build an empirical model of the value obtained through computation, and apply this model to estimate the value of computation for quite different problems. In particular, we investigate this trade-off for the problem of constructing policies for decision problems represented as influence diagrams. We show how two features of our anytime algorithm provide reasonable estimates of the value of computation in this domain.
Mini-Bucket Heuristics for Improved Search
Venue: arXiv cs.AI 2013
Year: 2013

The paper is a second in a series of two papers evaluating the power of a new scheme that generates search heuristics mechanically. The heuristics are extracted from an approximation scheme called mini-bucket elimination that was recently introduced. The first paper introduced the idea and evaluated it within Branch-and-Bound search. In the current paper the idea is further extended and evaluated within Best-First search. The resulting algorithms are compared on coding and medical diagnosis problems, using varying strength of the mini-bucket heuristics. Our results demonstrate an effective search scheme that permits controlled tradeoff between preprocessing (for heuristic generation) and search. Best-first search is shown to outperform Branch-and-Bound, when supplied with good heuristics, and sufficient memory space.
A Bayesian Network Classifier that Combines a Finite Mixture Model and a Naive Bayes Model
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we present a new Bayesian network model for classification that combines the naive-Bayes (NB) classifier and the finite-mixture (FM) classifier. The resulting classifier aims at relaxing the strong assumptions on which the two component models are based, in an attempt to improve on their classification performance, both in terms of accuracy and in terms of calibration of the estimated probabilities. The proposed classifier is obtained by superimposing a finite mixture model on the set of feature variables of a naive Bayes model. We present experimental results that compare the predictive performance on real datasets of the new classifier with the predictive performance of the NB classifier and the FM classifier.
Learning Bayesian Networks with Restricted Causal Interactions
Venue: arXiv cs.AI 2013
Year: 2013

A major problem for the learning of Bayesian networks (BNs) is the exponential number of parameters needed for conditional probability tables. Recent research reduces this complexity by modeling local structure in the probability tables. We examine the use of log-linear local models. While log-linear models in this context are not new (Whittaker, 1990; Buntine, 1991; Neal, 1992; Heckerman and Meek, 1997), for structure learning they are generally subsumed under a naive Bayes model. We describe an alternative interpretation, and use a Minimum Message Length (MML) (Wallace, 1987) metric for structure learning of networks exhibiting causal independence, which we term first-order networks (FONs). We also investigate local model selection on a node-by-node basis.
Efficient Value of Information Computation
Venue: arXiv cs.AI 2013
Year: 2013

One of the most useful sensitivity analysis techniques of decision analysis is the computation of value of information (or clairvoyance), the difference in value obtained by changing the decisions by which some of the uncertainties are observed. In this paper, some simple but powerful extensions to previous algorithms are introduced which allow an efficient value of information calculation on the rooted cluster tree (or strong junction tree) used to solve the original decision problem.
Multiplicative Factorization of Noisy-Max
Venue: arXiv cs.AI 2013
Year: 2013

The noisy-or and its generalization noisy-max have been utilized to reduce the complexity of knowledge acquisition. In this paper, we present a new representation of noisy-max that allows for efficient inference in general Bayesian networks. Empirical studies show that our method is capable of computing queries in well-known large medical networks, QMR-DT and CPCS, for which no previous exact inference method has been shown to perform well.
An Update Semantics for Defeasible Obligations
Venue: arXiv cs.AI 2013
Year: 2013

The deontic logic DUS is a Deontic Update Semantics for prescriptive obligations based on the update semantics of Veltman. In DUS the definition of logical validity of obligations is not based on static truth values but on dynamic action transitions. In this paper prescriptive defeasible obligations are formalized in update semantics and the diagnostic problem of defeasible deontic logic is discussed. Assume a defeasible obligation `normally A ought to be (done)' together withthe fact `A is not (done).' Is this an exception of the normality claim, or is it a violation of the obligation? In this paper we formalize the heuristic principle that it is a violation, unless there is a more specific overriding obligation. The underlying motivation from legal reasoning is that criminals should have as little opportunities as possible to excuse themselves by claiming that their behavior was exceptional rather than criminal.
Quantifying Opacity
Venue: arXiv cs.CR 2013
Year: 2013

Opacity is a general language-theoretic framework in which several security properties of a system can be expressed. Its parameters are a predicate, given as a subset of runs of the system, and an observation function, from the set of runs into a set of observables. The predicate describes secret information in the system and, in the possibilistic setting, it is opaque if its membership cannot be inferred from observation. In this paper, we propose several notions of quantitative opacity for probabilistic systems, where the predicate and the observation function are seen as random variables. Our aim is to measure (i) the probability of opacity leakage relative to these random variables and (ii) the level of uncertainty about membership of the predicate inferred from observation. We show how these measures extend possibilistic opacity, we give algorithms to compute them for regular secrets and observations, and we apply these computations on several classical examples. We finally partially investigate the non-deterministic setting.
Robust Face Recognition via Block Sparse Bayesian Learning
Venue: arXiv cs.CV 2013
Year: 2013

Face recognition (FR) is an important task in pattern recognition and computer vision. Sparse representation (SR) has been demonstrated to be a powerful framework for FR. In general, an SR algorithm treats each face in a training dataset as a basis function, and tries to find a sparse representation of a test face under these basis functions. The sparse representation coefficients then provide a recognition hint. Early SR algorithms are based on a basic sparse model. Recently, it has been found that algorithms based on a block sparse model can achieve better recognition rates. Based on this model, in this study we use block sparse Bayesian learning (BSBL) to find a sparse representation of a test face for recognition. BSBL is a recently proposed framework, which has many advantages over existing block-sparse-model based algorithms. Experimental results on the Extended Yale B, the AR and the CMU PIE face databases show that using BSBL can achieve better recognition rates and higher robustness than state-of-the-art algorithms in most cases.
PhishAri: Automatic Realtime Phishing Detection on Twitter
Venue: arXiv cs.SI 2013
Year: 2013

With the advent of online social media, phishers have started using social networks like Twitter, Facebook, and Foursquare to spread phishing scams. Twitter is an immensely popular micro-blogging network where people post short messages of 140 characters called tweets. It has over 100 million active users who post about 200 million tweets everyday. Phishers have started using Twitter as a medium to spread phishing because of this vast information dissemination. Further, it is difficult to detect phishing on Twitter unlike emails because of the quick spread of phishing links in the network, short size of the content, and use of URL obfuscation to shorten the URL. Our technique, PhishAri, detects phishing on Twitter in realtime. We use Twitter specific features along with URL features to detect whether a tweet posted with a URL is phishing or not. Some of the Twitter specific features we use are tweet content and its characteristics like length, hashtags, and mentions. Other Twitter features used are the characteristics of the Twitter user posting the tweet such as age of the account, number of tweets, and the follower-followee ratio. These Twitter specific features coupled with URL based features prove to be a strong mechanism to detect phishing tweets. We use machine learning classification techniques and detect phishing tweets with an accuracy of 92.52%. We have deployed our system for end-users by providing an easy to use Chrome browser extension which works in realtime and classifies a tweet as phishing or safe. We show that we are able to detect phishing tweets at zero hour with high accuracy which is much faster than public blacklists and as well as Twitter's own defense mechanism to detect malicious content. To the best of our knowledge, this is the first realtime, comprehensive and usable system to detect phishing on Twitter.
Not all paths lead to Rome: Analysing the network of sister cities
Venue: arXiv cs.SI 2013
Year: 2013

This work analyses the practice of sister city pairing. We investigate structural properties of the resulting city and country networks and present rankings of the most central nodes in these networks. We identify different country clusters and find that the practice of sister city pairing is not influenced by geographical proximity but results in highly assortative networks.