OpenRaiser/Intern-Atlas huggingface dataset:
On the Generation of Alternative Explanations with Implications for Belief Revision
Venue: arXiv cs.AI 2013
Year: 2013

In general, the best explanation for a given observation makes no promises on how good it is with respect to other alternative explanations. A major deficiency of message-passing schemes for belief revision in Bayesian networks is their inability to generate alternatives beyond the second best. In this paper, we present a general approach based on linear constraint systems that naturally generates alternative explanations in an orderly and highly efficient manner. This approach is then applied to cost-based abduction problems as well as belief revision in Bayesian net works.
Compressed Constraints in Probabilistic Logic and Their Revision
Venue: arXiv cs.AI 2013
Year: 2013

In probabilistic logic entailments, even moderate size problems can yield linear constraint systems with so many variables that exact methods are impractical. This difficulty can be remedied in many cases of interest by introducing a three valued logic (true, false, and "don't care"). The three-valued approach allows the construction of "compressed" constraint systems which have the same solution sets as their two-valued counterparts, but which may involve dramatically fewer variables. Techniques to calculate point estimates for the posterior probabilities of entailed sentences are discussed.
Effect of Receive Spatial Diversity on the Degrees of Freedom Region in Multi-Cell Random Beamforming
Venue: arXiv cs.IT 2013
Year: 2013

The random beamforming (RBF) scheme, jointly applied with multi-user diversity based scheduling, is able to achieve virtually interference-free downlink transmissions with only partial channel state information (CSI) available at the transmitter. However, the impact of receive spatial diversity on the rate performance of RBF is not fully characterized yet even in a single-cell setup. In this paper, we study a multi-cell multiple-input multiple-output (MIMO) broadcast system with RBF applied at each base station (BS) and either the minimum-mean-square-error (MMSE), matched filter (MF), or antenna selection (AS) based spatial receiver employed at each mobile terminal. We investigate the effect of different spatial diversity receivers on the achievable sum-rate of multi-cell RBF systems subject to both the intra- and inter-cell interferences. We first derive closed-form expressions for the distributions of the receiver signal-to-interference-plus-noise ratio (SINR) with different spatial diversity techniques, based on which we compare their rate performances at finite signal-to-noise ratios (SNRs). We then investigate the asymptotically high-SNR regime and for a tractable analysis assume that the number of users in each cell scales in a certain order with the per-cell SNR as SNR goes to infinity. Under this setup, we characterize the degrees of freedom (DoF) region for multi-cell RBF systems with different types of spatial receivers, which consists of all the achievable DoF tuples for the individual sum-rate of all the cells. The DoF region analysis provides a succinct characterization of the interplays among the receive spatial diversity, multiuser diversity, spatial multiplexing gain, inter-/intra-cell interferences, and BSs' collaborative transmission.
High Quality Requirement Engineering and Applying Priority Based Tools for QoS Standardization in Web Service Architecture
Venue: arXiv cs.SE 2013
Year: 2013

Even though there are more development to improving the Quality of Service and requirement engineering in web services yet there is a big scarcity for its related standardization in day to day progress leading to vast needs in its area. Also in web service environment it always has been a big challenge to raise the standard of Quality of Service in requirement engineering analysis.
Reinforcement Ranking
Venue: arXiv cs.IR 2013
Year: 2013

We introduce a new framework for web page ranking -- reinforcement ranking -- that improves the stability and accuracy of Page Rank while eliminating the need for computing the stationary distribution of random walks. Instead of relying on teleportation to ensure a well defined Markov chain, we develop a reverse-time reinforcement learning framework that determines web page authority based on the solution of a reverse Bellman equation. In particular, for a given reward function and surfing policy we recover a well defined authority score from a reverse-time perspective: looking back from a web page, what is the total incoming discounted reward brought by the surfer from the page's predecessors? This results in a novel form of reverse-time dynamic-programming/reinforcement-learning problem that achieves several advantages over Page Rank based methods: First, stochasticity, ergodicity, and irreducibility of the underlying Markov chain is no longer required for well-posedness. Second, the method is less sensitive to graph topology and more stable in the presence of dangling pages. Third, not only does the reverse Bellman iteration yield a more efficient power iteration, it allows for faster updating in the presence of graph changes. Finally, our experiments demonstrate improvements in ranking quality.
On Sparsity Inducing Regularization Methods for Machine Learning
Venue: arXiv cs.LG 2013
Year: 2013

During the past years there has been an explosion of interest in learning methods based on sparsity regularization. In this paper, we discuss a general class of such methods, in which the regularizer can be expressed as the composition of a convex function $ω$ with a linear function. This setting includes several methods such the group Lasso, the Fused Lasso, multi-task learning and many more. We present a general approach for solving regularization problems of this kind, under the assumption that the proximity operator of the function $ω$ is available. Furthermore, we comment on the application of this approach to support vector machines, a technique pioneered by the groundbreaking work of Vladimir Vapnik.
A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization
Venue: arXiv cs.SY 2013
Year: 2013

In this paper we consider a general problem set-up for a wide class of convex and robust distributed optimization problems in peer-to-peer networks. In this set-up convex constraint sets are distributed to the network processors who have to compute the optimizer of a linear cost function subject to the constraints. We propose a novel fully distributed algorithm, named cutting-plane consensus, to solve the problem, based on an outer polyhedral approximation of the constraint sets. Processors running the algorithm compute and exchange linear approximations of their locally feasible sets. Independently of the number of processors in the network, each processor stores only a small number of linear constraints, making the algorithm scalable to large networks. The cutting-plane consensus algorithm is presented and analyzed for the general framework. Specifically, we prove that all processors running the algorithm agree on an optimizer of the global problem, and that the algorithm is tolerant to node and link failures as long as network connectivity is preserved. Then, the cutting plane consensus algorithm is specified to three different classes of distributed optimization problems, namely (i) inequality constrained problems, (ii) robust optimization problems, and (iii) almost separable optimization problems with separable objective functions and coupling constraints. For each one of these problem classes we solve a concrete problem that can be expressed in that framework and present computational results. That is, we show how to solve: position estimation in wireless sensor networks, a distributed robust linear program and, a distributed microgrid control problem.
Model-Based Calibration of Filter Imperfections in the Random Demodulator for Compressive Sensing
Venue: arXiv cs.IT 2013
Year: 2013

The random demodulator is a recent compressive sensing architecture providing efficient sub-Nyquist sampling of sparse band-limited signals. The compressive sensing paradigm requires an accurate model of the analog front-end to enable correct signal reconstruction in the digital domain. In practice, hardware devices such as filters deviate from their desired design behavior due to component variations. Existing reconstruction algorithms are sensitive to such deviations, which fall into the more general category of measurement matrix perturbations. This paper proposes a model-based technique that aims to calibrate filter model mismatches to facilitate improved signal reconstruction quality. The mismatch is considered to be an additive error in the discretized impulse response. We identify the error by sampling a known calibrating signal, enabling least-squares estimation of the impulse response error. The error estimate and the known system model are used to calibrate the measurement matrix. Numerical analysis demonstrates the effectiveness of the calibration method even for highly deviating low-pass filter responses. The proposed method performance is also compared to a state of the art method based on discrete Fourier transform trigonometric interpolation.
Some notes on the abstraction operation for Multi-Terminal Binary Decision Diagrams
Venue: arXiv cs.LO 2013
Year: 2013

The starting point of this work are inaccurate statements found in the literature for Multi-terminal Binary Decision Diagrams (MTBDDs) regarding the well-definedness of the MTBDD abstraction operation. The statements try to relate an operation * on a set of terminal values M to the property that the abstraction over this operation does depend on the order of the abstracted variables. This paper gives a necessary and sufficient condition for the independence of the abstraction operation of the order of the abstracted variables in the case of an underlying monoid and it treats the more general setting of a magma.
EAST: Energy Efficient Adaptive Scheme for Transmission in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we propose Energy-efficient Adaptive Scheme for Transmission (EAST) in WSNs. EAST is IEEE 802.15.4 standard compliant. In this approach, open-loop is used for temperature-aware link quality estimation and compensation. Whereas, closed-loop feedback helps to divide network into three logical regions to minimize overhead of control packets on basis of Threshold transmitter power loss (RSSIloss) for each region and current number of neighbor nodes that help to adapt transmit power according to link quality changes due to temperature variation. Simulation results show that propose scheme; EAST effectively adapts transmission power to changing link quality with less control packets overhead and energy consumption compared to classical approach with single region in which maximum transmitter power assigned to compensate temperature variation.
Simulation of Fractional Brownian Surfaces via Spectral Synthesis on Manifolds
Venue: arXiv cs.CG 2013
Year: 2013

Using the spectral decomposition of the Laplace-Beltrami operator we simulate fractal surfaces as random series of eigenfunctions. This approach allows us to generate random fields over smooth manifolds of arbitrary dimension, generalizing previous work with fractional Brownian motion with multi-dimensional parameter. We give examples of surfaces with and without boundary and discuss implementation.
A Note on k-support Norm Regularized Risk Minimization
Venue: arXiv cs.LG 2013
Year: 2013

The k-support norm has been recently introduced to perform correlated sparsity regularization. Although Argyriou et al. only reported experiments using squared loss, here we apply it to several other commonly used settings resulting in novel machine learning algorithms with interesting and familiar limit cases. Source code for the algorithms described here is available.
Large-Scale Pattern Search Using Reduced-Space On-Disk Suffix Arrays
Venue: arXiv cs.DS 2013
Year: 2013

The suffix array is an efficient data structure for in-memory pattern search. Suffix arrays can also be used for external-memory pattern search, via two-level structures that use an internal index to identify the correct block of suffix pointers. In this paper we describe a new two-level suffix array-based index structure that requires significantly less disk space than previous approaches. Key to the saving is the use of disk blocks that are based on prefixes rather than the more usual uniform-sampling approach, allowing reductions between blocks and subparts of other blocks. We also describe a new in-memory structure based on a condensed BWT string, and show that it allows common patterns to be resolved without access to the text. Experiments using 64 GB of English web text and a laptop computer with just 4 GB of main memory demonstrate the speed and versatility of the new approach. For this data the index is around one- third the size of previous two-level mechanisms; and the memory footprint of as little as 1% of the text size means that queries can be processed more quickly than is possible with a compact FM-INDEX.
Density Controlled Divide-and-Rule Scheme for Energy Efficient Routing in Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Cluster based routing technique is most popular routing technique in Wireless Sensor Networks (WSNs). Due to varying need of WSN applications efficient energy utilization in routing protocols is still a potential area of research. In this research work we introduced a new energy efficient cluster based routing technique. In this technique we tried to overcome the problem of coverage hole and energy hole. In our technique we controlled these problems by introducing density controlled uniform distribution of nodes and fixing optimum number of Cluster Heads (CHs) in each round. Finally we verified our technique by experimental results of MATLAB simulations.
Optimal Power Allocation over Multiple Identical Gilbert-Elliott Channels
Venue: arXiv cs.IT 2013
Year: 2013

We study the fundamental problem of power allocation over multiple Gilbert-Elliott communication channels. In a communication system with time varying channel qualities, it is important to allocate the limited transmission power to channels that will be in good state. However, it is very challenging to do so because channel states are usually unknown when the power allocation decision is made. In this paper, we derive an optimal power allocation policy that can maximize the expected discounted number of bits transmitted over an infinite time span by allocating the transmission power only to those channels that are believed to be good in the coming time slot. We use the concept belief to represent the probability that a channel will be good and derive an optimal power allocation policy that establishes a mapping from the channel belief to an allocation decision. Specifically, we first model this problem as a partially observable Markov decision processes (POMDP), and analytically investigate the structure of the optimal policy. Then a simple threshold-based policy is derived for a three-channel communication system. By formulating and solving a linear programming formulation of this power allocation problem, we further verified the derived structure of the optimal policy.
Systematic Mapping Study On Security Threats in Cloud Computing
Venue: arXiv cs.CR 2013
Year: 2013

Today, Cloud Computing is rising strongly, presenting itself to the market by its main service models, known as IaaS, PaaS and SaaS, that offer advantages in operational investments by means of on-demand costs, where consumers pay by resources used. In face of this growth, security threats also rise, compromising the Confidentiality, Integrity and Availability of the services provided. Our work is a Systematic Mapping where we hope to present metrics about publications available in literature that deal with some of the seven security threats in Cloud Computing, based in the guide entitled "Top Threats to Cloud Computing" from the Cloud Security Alliance (CSA). In our research we identified the more explored threats, distributed the results between fifteen Security Domains and identified the types of solutions proposed for the threats. In face of those results, we highlight the publications that are concerned to fulfill some standard of compliance.
Proving the Pressing Game Conjecture on Linear Graphs
Venue: arXiv cs.DM 2013
Year: 2013

The pressing game on black-and-white graphs is the following: Given a graph $G(V,E)$ with its vertices colored with black and white, any black vertex $v$ can be pressed, which has the following effect: (a) all neighbors of $v$ change color, i.e. white neighbors become black and \emph{vice versa}, (b) all pairs of neighbors of $v$ change connectivity, i.e. connected pairs become unconnected, unconnected ones become connected, (c) and finally, $v$ becomes a separated white vertex. The aim of the game is to transform $G$ into an all white, empty graph. It is a known result that the all white empty graph is reachable in the pressing game if each component of $G$ contains at least one black vertex, and for a fixed graph, any successful transformation has the same number of pressed vertices. The pressing game conjecture is that any successful pressing path can be transformed into any other successful pressing path with small alterations. Here we prove the conjecture for linear graphs. The connection to genome rearrangement and sorting signed permutations with reversals is also discussed.
A practical system for improved efficiency in frequency division multiplexed wireless networks
Venue: arXiv cs.NI 2013
Year: 2013

Spectral efficiency is a key design issue for all wireless communication systems. Orthogonal frequency division multiplexing (OFDM) is a very well-known technique for efficient data transmission over many carriers overlapped in frequency. Recently, several papers have appeared which describe spectrally efficient variations of multi-carrier systems where the condition of orthogonality is dropped. Proposed techniques suffer from two weaknesses: Firstly, the complexity of generating the signal is increased. Secondly, the signal detection is computationally demanding. Known methods suffer either unusably high complexity or high error rates because of the inter-carrier interference. This work addresses both problems by proposing new transmitter and receiver arch itectures whose design is based on using the simplification that a rational Spectrally Efficient Frequency Division Multiplexing (SEFDM) system can be treated as a set of overlapped and interleaving OFDM systems. The efficacy of the proposed designs is shown through detailed simulation of sys tems with different signal types and carrier dimensions. The decoder is heuristic but in practice produces very good results which are close to the theoretical best performance in a variety of settings. The system is able to produce efficiency gains of up to 20% with negligible impact on the required signal to noise ratio.
Order-Preserving Suffix Trees and Their Algorithmic Applications
Venue: arXiv cs.DS 2013
Year: 2013

Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for consecutive substrings of the text that have the same "shape" as a given pattern. These results include a linear-time order-preserving pattern matching algorithm for polynomially-bounded alphabet and an extension of this result to pattern matching with multiple patterns. We make one step forward in the analysis and give an $O(\frac{n\log{n}}{\log\log{n}})$ time randomized algorithm constructing suffix trees in the order-preserving setting. We show a number of applications of order-preserving suffix trees to identify patterns and repetitions in time series.
Large scale citation matching using Apache Hadoop
Venue: arXiv cs.IR 2013
Year: 2013

During the process of citation matching links from bibliography entries to referenced publications are created. Such links are indicators of topical similarity between linked texts, are used in assessing the impact of the referenced document and improve navigation in the user interfaces of digital libraries. In this paper we present a citation matching method and show how to scale it up to handle great amounts of data using appropriate indexing and a MapReduce paradigm in the Hadoop environment.
The reduction of qualitative games
Venue: arXiv cs.GT 2013
Year: 2013

We extend the study of the iterated elimination of strictly dominated strategies (IESDS) from Nash strategic games to a class of qualitative games. Also in this case, the IESDS process leads us to a kind of 'rationalizable' result. We define several types of dominance relation and game reduction and establish conditions under which a unique and nonempty maximal reduction exists. We generalize, in this way, some results due to Dufwenberg and Stegeman (2002) and Apt (2007).
Unveiling Zeus
Venue: arXiv cs.CR 2013
Year: 2013

Malware family classification is an age old problem that many Anti-Virus (AV) companies have tackled. There are two common techniques used for classification, signature based and behavior based. Signature based classification uses a common sequence of bytes that appears in the binary code to identify and detect a family of malware. Behavior based classification uses artifacts created by malware during execution for identification. In this paper we report on a unique dataset we obtained from our operations and classified using several machine learning techniques using the behavior-based approach. Our main class of malware we are interested in classifying is the popular Zeus malware. For its classification we identify 65 features that are unique and robust for identifying malware families. We show that artifacts like file system, registry, and network features can be used to identify distinct malware families with high accuracy---in some cases as high as 95%.
Detecting Overlapping Temporal Community Structure in Time-Evolving Networks
Venue: arXiv cs.SI 2013
Year: 2013

We present a principled approach for detecting overlapping temporal community structure in dynamic networks. Our method is based on the following framework: find the overlapping temporal community structure that maximizes a quality function associated with each snapshot of the network subject to a temporal smoothness constraint. A novel quality function and a smoothness constraint are proposed to handle overlaps, and a new convex relaxation is used to solve the resulting combinatorial optimization problem. We provide theoretical guarantees as well as experimental results that reveal community structure in real and synthetic networks. Our main insight is that certain structures can be identified only when temporal correlation is considered and when communities are allowed to overlap. In general, discovering such overlapping temporal community structure can enhance our understanding of real-world complex networks by revealing the underlying stability behind their seemingly chaotic evolution.
Elementary Deduction Problem for Locally Stable Theories with Normal Forms
Venue: arXiv cs.LO 2013
Year: 2013

We present an algorithm to decide the intruder deduction problem (IDP) for a class of locally stable theories enriched with normal forms. Our result relies on a new and efficient algorithm to solve a restricted case of higher-order associative-commutative matching, obtained by combining the Distinct Occurrences of AC- matching algorithm and a standard algorithm to solve systems of linear Diophantine equations. A translation between natural deduction and sequent calculus allows us to use the same approach to decide the \emphelementary deduction problem for locally stable theories. As an application, we model the theory of blind signatures and derive an algorithm to decide IDP in this context, extending previous decidability results.