OpenRaiser/Intern-Atlas huggingface dataset:
Answer Set Programming for Stream Reasoning
Venue: arXiv cs.AI 2013
Year: 2013

The advance of Internet and Sensor technology has brought about new challenges evoked by the emergence of continuous data streams. Beyond rapid data processing, application areas like ambient assisted living, robotics, or dynamic scheduling involve complex reasoning tasks. We address such scenarios and elaborate upon approaches to knowledge-intense stream reasoning, based on Answer Set Programming (ASP). While traditional ASP methods are devised for singular problem solving, we develop new techniques to formulate and process problems dealing with emerging as well as expiring data in a seamless way.
Coupled Neural Associative Memories
Venue: arXiv cs.NE 2013
Year: 2013

We propose a novel architecture to design a neural associative memory that is capable of learning a large number of patterns and recalling them later in presence of noise. It is based on dividing the neurons into local clusters and parallel plains, very similar to the architecture of the visual cortex of macaque brain. The common features of our proposed architecture with those of spatially-coupled codes enable us to show that the performance of such networks in eliminating noise is drastically better than the previous approaches while maintaining the ability of learning an exponentially large number of patterns. Previous work either failed in providing good performance during the recall phase or in offering large pattern retrieval (storage) capacities. We also present computational experiments that lend additional support to the theoretical analysis.
Transmission Schemes for Gaussian Interference Channels with Transmitter Processing Energy
Venue: arXiv cs.IT 2013
Year: 2013

This work considers communication over Gaussian interference channels with processing energy cost, which explicitly takes into account the energy expended for processing when transmitters are on. In the presence of processing energy cost, transmitting all the time as in the conventional no-cost case is no longer optimal. For a two-user Gaussian interference channel with processing energy cost, assuming that the on-off states of transmitters are not utilized for signaling, several transmission schemes with varying complexities are proposed and their sum rates are compared with an interference-free upper bound. Moreover, the very strong interference regime, under which interference does not incur any rate penalty, is identified and shown to be larger than the case of no processing energy cost for certain scenarios of interest. Also, extensions to a three-user cascade Gaussian Z interference channel with processing energy cost are provided, where scheduling of user transmissions based on the channel set-up is investigated.
Formal Verification of Nonlinear Inequalities with Taylor Interval Approximations
Venue: arXiv cs.LO 2013
Year: 2013

We present a formal tool for verification of multivariate nonlinear inequalities. Our verification method is based on interval arithmetic with Taylor approximations. Our tool is implemented in the HOL Light proof assistant and it is capable to verify multivariate nonlinear polynomial and non-polynomial inequalities on rectangular domains. One of the main features of our work is an efficient implementation of the verification procedure which can prove non-trivial high-dimensional inequalities in several seconds. We developed the verification tool as a part of the Flyspeck project (a formal proof of the Kepler conjecture). The Flyspeck project includes about 1000 nonlinear inequalities. We successfully tested our method on more than 100 Flyspeck inequalities and estimated that the formal verification procedure is about 3000 times slower than an informal verification method implemented in C++. We also describe future work and prospective optimizations for our method.
Generalized Secure Transmission Protocol for Flexible Load-Balance Control with Cooperative Relays in Two-Hop Wireless Networks
Venue: arXiv cs.CR 2013
Year: 2013

This work considers secure transmission protocol for flexible load-balance control in two-hop relay wireless networks without the information of both eavesdropper channels and locations. The available secure transmission protocols via relay cooperation in physical layer secrecy framework cannot provide a flexible load-balance control, which may significantly limit their application scopes. This paper extends the conventional works and proposes a general transmission protocol with considering load-balance control, in which the relay is randomly selected from the first $k$ preferable assistant relays located in the circle area with the radius $r$ and the center at the middle between source and destination (2HR-($r,k$) for short). This protocol covers the available works as special cases, like ones with the optimal relay selection ($r=\infty$, $k=1$) and with the random relay selection ($r=\infty$, $k = n$ i.e. the number of system nodes) in the case of equal path-loss, ones with relay selected from relay selection region ($r \in (0, \infty), k = 1$) in the case of distance-dependent path-loss. The theoretic analysis is further provided to determine the maximum number of eavesdroppers one network can tolerate to ensure a desired performance in terms of the secrecy outage probability and transmission outage probability. The analysis results also show the proposed protocol can balance load distributed among the relays by a proper setting of $r$ and $k$ under the premise of specified secure and reliable requirements.
Image Registration for Stability Testing of MEMS
Venue: arXiv cs.CV 2013
Year: 2013

Image registration, or alignment of two or more images covering the same scenes or objects, is of great interest in many disciplines such as remote sensing, medical imaging, astronomy, and computer vision. In this paper, we introduce a new application of image registration algorithms. We demonstrate how through a wavelet based image registration algorithm, engineers can evaluate stability of Micro-Electro-Mechanical Systems (MEMS). In particular, we applied image registration algorithms to assess alignment stability of the MicroShutters Subsystem (MSS) of the Near Infrared Spectrograph (NIRSpec) instrument of the James Webb Space Telescope (JWST). This work introduces a new methodology for evaluating stability of MEMS devices to engineers as well as a new application of image registration algorithms to computer scientists.
On Pairwise Spanners
Venue: arXiv cs.DS 2013
Year: 2013

Given an undirected $n$-node unweighted graph $G = (V, E)$, a spanner with stretch function $f(\cdot)$ is a subgraph $H\subseteq G$ such that, if two nodes are at distance $d$ in $G$, then they are at distance at most $f(d)$ in $H$. Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the $u$-$v$ distance only for pairs $(u,v)$ in a given set $\cP \subseteq V\times V$. Such $\cP$-spanners were studied before [Coppersmith,Elkin'05] only in the special case that $f(\cdot)$ is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same $\cP$) and of the best known spanners (with the same $f(\cdot)$). In more detail, for arbitrary $\cP$, we show that there exists a $\mathcal{P}$-spanner of size $O(n(|\cP|\log n)^{1/4})$ with $f(d)=d+4\log n$. Alternatively, for any $\eps>0$, there exists a $\cP$-spanner of size $O(n|\cP|^{1/4}\sqrt{\frac{\log n}{\eps}})$ with $f(d)=(1+\eps)d+4$. We also consider the relevant special case that there is a critical set of nodes $S\subseteq V$, and we wish to approximate either the distances within nodes in $S$ or from nodes in $S$ to any other node. We show that there exists an $(S\times S)$-spanner of size $O(n\sqrt{|S|})$ with $f(d)=d+2$, and an $(S\times V)$-spanner of size $O(n\sqrt{|S|\log n})$ with $f(d)=d+2\log n$. All the mentioned pairwise spanners can be constructed in polynomial time.
Importance of Symbol Equity in Coded Modulation for Power Line Communications
Venue: arXiv cs.IT 2013
Year: 2013

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications system. In this paper, we extend this coded modulation scheme based on permutation codes to general codes and introduce an additional new parameter that more precisely captures a code's performance against permanent narrowband noise. As a result, we define a new class of codes, namely, equitable symbol weight codes, which are optimal with respect to this measure.
AViTExt: Automatic Video Text Extraction, A new Approach for video content indexing Application
Venue: arXiv cs.MM 2013
Year: 2013

In this paper, we propose a spatial temporal video-text detection technique which proceed in two principal steps:potential text region detection and a filtering process. In the first step we divide dynamically each pair of consecutive video frames into sub block in order to detect change. A significant difference between homologous blocks implies the appearance of an important object which may be a text region. The temporal redundancy is then used to filter these regions and forms an effective text region. The experimentation driven on a variety of video sequences shows the effectiveness of our approach by obtaining a 89,39% as precision rate and 90,19 as recall.
Estimation from Relative Measurements in Mobile Networks with Markovian Switching Topology: Clock Skew and Offset Estimation for Time Synchronization
Venue: arXiv cs.SY 2013
Year: 2013

We analyze a distributed algorithm for estimation of scalar parameters belonging to nodes in a mobile network from noisy relative measurements. The motivation comes from the problem of clock skew and offset estimation for the purpose of time synchronization. The time variation of the network was modeled as a Markov chain. The estimates are shown to be mean square convergent under fairly weak assumptions on the Markov chain, as long as the union of the graphs is connected. Expressions for the asymptotic mean and correlation are also provided. The Markovian switching topology model of mobile networks is justified for certain node mobility models through empirically estimated conditional entropy measures.
Wyner's Common Information: Generalizations and A New Lossy Source Coding Interpretation
Venue: arXiv cs.IT 2013
Year: 2013

Wyner's common information was originally defined for a pair of dependent discrete random variables. Its significance is largely reflected in, hence also confined to, several existing interpretations in various source coding problems. This paper attempts to both generalize its definition and to expand its practical significance by providing a new operational interpretation. The generalization is two-folded: the number of dependent variables can be arbitrary, so are the alphabet of those random variables. New properties are determined for the generalized Wyner's common information of N dependent variables. More importantly, a lossy source coding interpretation of Wyner's common information is developed using the Gray-Wyner network. In particular, it is established that the common information equals to the smallest common message rate when the total rate is arbitrarily close to the rate distortion function with joint decoding. A surprising observation is that such equality holds independent of the values of distortion constraints as long as the distortions are within some distortion region. Examples about the computation of common information are given, including that of a pair of dependent Gaussian random variables.
Instrumentality Tests Revisited
Venue: arXiv cs.AI 2013
Year: 2013

An instrument is a random variable thatallows the identification of parameters inlinear models when the error terms arenot uncorrelated.It is a popular method used in economicsand the social sciences that reduces theproblem of identification to the problemof finding the appropriate instruments.Few years ago, Pearl introduced a necessarytest for instruments that allows the researcher to discard those candidatesthat fail the test.In this paper, we make a detailed study of Pearl's test and the general model forinstruments. The results of this studyinclude a novel interpretation of Pearl'stest, a general theory of instrumentaltests, and an affirmative answer to aprevious conjecture. We also presentnew instrumentality tests for the casesof discrete and continuous variables.
Linearity Properties of Bayes Nets with Binary Variables
Venue: arXiv cs.AI 2013
Year: 2013

It is "well known" that in linear models: (1) testable constraints on the marginal distribution of observed variables distinguish certain cases in which an unobserved cause jointly influences several observed variables; (2) the technique of "instrumental variables" sometimes permits an estimation of the influence of one variable on another even when the association between the variables may be confounded by unobserved common causes; (3) the association (or conditional probability distribution of one variable given another) of two variables connected by a path or trek can be computed directly from the parameter values associated with each edge in the path or trek; (4) the association of two variables produced by multiple treks can be computed from the parameters associated with each trek; and (5) the independence of two variables conditional on a third implies the corresponding independence of the sums of the variables over all units conditional on the sums over all units of each of the original conditioning variables.These properties are exploited in search procedures. It is also known that properties (2)-(5) do not hold for all Bayes nets with binary variables. We show that (1) holds for all Bayes nets with binary variables and (5) holds for all singly trek-connected Bayes nets of that kind. We further show that all five properties hold for Bayes nets with any DAG and binary variables parameterized with noisy-or and noisy-and gates.
Learning the Dimensionality of Hidden Variables
Venue: arXiv cs.LG 2013
Year: 2013

A serious problem in learning probabilistic models is the presence of hidden variables. These variables are not observed, yet interact with several of the observed variables. Detecting hidden variables poses two problems: determining the relations to other variables in the model and determining the number of states of the hidden variable. In this paper, we address the latter problem in the context of Bayesian networks. We describe an approach that utilizes a score-based agglomerative state-clustering. As we show, this approach allows us to efficiently evaluate models with a range of cardinalities for the hidden variable. We show how to extend this procedure to deal with multiple interacting hidden variables. We demonstrate the effectiveness of this approach by evaluating it on synthetic and real-life data. We show that our approach learns models with hidden variables that generalize better and have better structure than previous approaches.
Estimating Well-Performing Bayesian Networks using Bernoulli Mixtures
Venue: arXiv cs.LG 2013
Year: 2013

A novel method for estimating Bayesian network (BN) parameters from data is presented which provides improved performance on test data. Previous research has shown the value of representing conditional probability distributions (CPDs) via neural networks(Neal 1992), noisy-OR gates (Neal 1992, Diez 1993)and decision trees (Friedman and Goldszmidt 1996).The Bernoulli mixture network (BMN) explicitly represents the CPDs of discrete BN nodes as mixtures of local distributions,each having a different set of parents.This increases the space of possible structures which can be considered,enabling the CPDs to have finer-grained dependencies.The resulting estimation procedure induces a modelthat is better able to emulate the underlying interactions occurring in the data than conventional conditional Bernoulli network models.The results for artificially generated data indicate that overfitting is best reduced by restricting the complexity of candidate mixture substructures local to each node. Furthermore, mixtures of very simple substructures can perform almost as well as more complex ones.The BMN is also applied to data collected from an online adventure game with an application to keyhole plan recognition. The results show that the BMN-based model brings a dramatic improvement in performance over a conventional BN model.
On characterizing Inclusion of Bayesian Networks
Venue: arXiv cs.AI 2013
Year: 2013

Every directed acyclic graph (DAG) over a finite non-empty set of variables (= nodes) N induces an independence model over N, which is a list of conditional independence statements over N.The inclusion problem is how to characterize (in graphical terms) whether all independence statements in the model induced by a DAG K are in the model induced by a second DAG L. Meek (1997) conjectured that this inclusion holds iff there exists a sequence of DAGs from L to K such that only certain 'legal' arrow reversal and 'legal' arrow adding operations are performed to get the next DAG in the sequence.In this paper we give several characterizations of inclusion of DAG models and verify Meek's conjecture in the case that the DAGs K and L differ in at most one adjacency. As a warming up a rigorous proof of well-known graphical characterizations of equivalence of DAGs, which is a highly related problem, is given.
The Factored Frontier Algorithm for Approximate Inference in DBNs
Venue: arXiv cs.AI 2013
Year: 2013

The Factored Frontier (FF) algorithm is a simple approximate inferencealgorithm for Dynamic Bayesian Networks (DBNs). It is very similar tothe fully factorized version of the Boyen-Koller (BK) algorithm, butinstead of doing an exact update at every step followed bymarginalisation (projection), it always works with factoreddistributions. Hence it can be applied to models for which the exactupdate step is intractable. We show that FF is equivalent to (oneiteration of) loopy belief propagation (LBP) on the original DBN, andthat BK is equivalent (to one iteration of) LBP on a DBN where wecluster some of the nodes. We then show empirically that byiterating, LBP can improve on the accuracy of both FF and BK. Wecompare these algorithms on two real-world DBNs: the first is a modelof a water treatment plant, and the second is a coupled HMM, used tomodel freeway traffic.
Approximating MAP using Local Search
Venue: arXiv cs.AI 2013
Year: 2013

MAP is the problem of finding a most probable instantiation of a set of variables in a Bayesian network, given evidence. Unlike computing marginals, posteriors, and MPE (a special case of MAP), the time and space complexity of MAP is not only exponential in the network treewidth, but also in a larger parameter known as the "constrained" treewidth. In practice, this means that computing MAP can be orders of magnitude more expensive than computingposteriors or MPE. Thus, practitioners generally avoid MAP computations, resorting instead to approximating them by the most likely value for each MAP variableseparately, or by MPE.We present a method for approximating MAP using local search. This method has space complexity which is exponential onlyin the treewidth, as is the complexity of each search step. We investigate the effectiveness of different local searchmethods and several initialization strategies and compare them to otherapproximation schemes.Experimental results show that local search provides a much more accurate approximation of MAP, while requiring few search steps.Practically, this means that the complexity of local search is often exponential only in treewidth as opposed to the constrained treewidth, making approximating MAP as efficient as other computations.
Sufficiency, Separability and Temporal Probabilistic Models
Venue: arXiv cs.AI 2013
Year: 2013

Suppose we are given the conditional probability of one variable given some other variables.Normally the full joint distribution over the conditioning variablesis required to determine the probability of the conditioned variable.Under what circumstances are the marginal distributions over the conditioning variables sufficient to determine the probability ofthe conditioned variable?Sufficiency in this sense is equivalent to additive separability ofthe conditional probability distribution.Such separability structure is natural and can be exploited forefficient inference.Separability has a natural generalization to conditional separability.Separability provides a precise notion of weaklyinteracting subsystems in temporal probabilistic models.Given a system that is decomposed into separable subsystems, exactmarginal probabilities over subsystems at future points in time can becomputed by propagating marginal subsystem probabilities, rather thancomplete system joint probabilities.Thus, separability can make exact prediction tractable.However, observations can break separability,so exact monitoring of dynamic systems remains hard.
Probabilistic Models for Unified Collaborative and Content-Based Recommendation in Sparse-Data Environments
Venue: arXiv cs.IR 2013
Year: 2013

Recommender systems leverage product and community information to target products to consumers. Researchers have developed collaborative recommenders, content-based recommenders, and (largely ad-hoc) hybrid systems. We propose a unified probabilistic framework for merging collaborative and content-based recommendations. We extend Hofmann's [1999] aspect model to incorporate three-way co-occurrence data among users, items, and item content. The relative influence of collaboration data versus content data is not imposed as an exogenous parameter, but rather emerges naturally from the given data sources. Global probabilistic models coupled with standard Expectation Maximization (EM) learning algorithms tend to drastically overfit in sparse-data situations, as is typical in recommendation applications. We show that secondary content information can often be used to overcome sparsity. Experiments on data from the ResearchIndex library of Computer Science publications show that appropriate mixture models incorporating secondary data produce significantly better quality recommenders than k-nearest neighbors (k-NN). Global probabilistic models also allow more general inferences than local methods like k-NN.
A Tractable POMDP for a Class of Sequencing Problems
Venue: arXiv cs.AI 2013
Year: 2013

We consider a partially observable Markov decision problem (POMDP) that models a class of sequencing problems. Although POMDPs are typically intractable, our formulation admits tractable solution. Instead of maintaining a value function over a high-dimensional set of belief states, we reduce the state space to one of smaller dimension, in which grid-based dynamic programming techniques are effective. We develop an error bound for the resulting approximation, and discuss an application of the model to a problem in targeted advertising.