OpenRaiser/Intern-Atlas huggingface dataset:
Contextual Multi-armed Bandits for the Prevention of Spam in VoIP Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we argue that contextual multi-armed bandit algorithms could open avenues for designing self-learning security modules for computer networks and related tasks. The paper has two contributions: a conceptual one and an algorithmical one. The conceptual contribution is to formulate -- as an example -- the real-world problem of preventing SPIT (Spam in VoIP networks), which is currently not satisfyingly addressed by standard techniques, as a sequential learning problem, namely as a contextual multi-armed bandit. Our second contribution is to present CMABFAS, a new algorithm for general contextual multi-armed bandit learning that specifically targets domains with finite actions. We illustrate how CMABFAS could be used to design a fully self-learning SPIT filter that does not rely on feedback from the end-user (i.e., does not require labeled data) and report first simulation results.
Wikipedia Arborification and Stratified Explicit Semantic Analysis
Venue: arXiv cs.CL 2012
Year: 2012

[This is the translation of paper "Arborification de Wikipédia et analyse sémantique explicite stratifiée" submitted to TALN 2012.] We present an extension of the Explicit Semantic Analysis method by Gabrilovich and Markovitch. Using their semantic relatedness measure, we weight the Wikipedia categories graph. Then, we extract a minimal spanning tree, using Chu-Liu & Edmonds' algorithm. We define a notion of stratified tfidf where the stratas, for a given Wikipedia page and a given term, are the classical tfidf and categorical tfidfs of the term in the ancestor categories of the page (ancestors in the sense of the minimal spanning tree). Our method is based on this stratified tfidf, which adds extra weight to terms that "survive" when climbing up the category tree. We evaluate our method by a text classification on the WikiNews corpus: it increases precision by 18%. Finally, we provide hints for future research
An Information-Spectrum Approach to the Capacity Region of General Interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

This paper is concerned with general interference channels characterized by a sequence of transition (conditional) probabilities. We present a general formula for the capacity region of the interference channel with two pairs of users. The formula shows that the capacity region is the union of a family of rectangles, where each rectangle is determined by a pair of spectral inf-mutual information rates. Although the presented formula is usually difficult to compute, it provides us useful insights into the interference channels. For example, the formula suggests us that the simplest inner bounds (obtained by treating the interference as noise) could be improved by taking into account the structure of the interference processes. This is verified numerically by computing the mutual information rates for Gaussian interference channels with embedded convolutional codes.
Advanced Coarsening Schemes for Graph Partitioning
Venue: arXiv cs.DS 2012
Year: 2012

The graph partitioning problem is widely used and studied in many practical and theoretical applications. The multilevel strategies represent today one of the most effective and efficient generic frameworks for solving this problem on large-scale graphs. Most of the attention in designing the multilevel partitioning frameworks has been on the refinement phase. In this work we focus on the coarsening phase, which is responsible for creating structurally similar to the original but smaller graphs. We compare different matching- and AMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstrate computational results on several classes of graphs that emphasize the running time and quality advantages of different coarsenings.
Control Communication Complexity of Distributed Actions
Venue: arXiv cs.SY 2012
Year: 2012

Recent papers have treated {\em control communication complexity} in the context of information-based, multiple agent control systems including nonlinear systems of the type that have been studied in connection with quantum information processing. The present paper continues this line of investigation into a class of two-agent distributed control systems in which the agents cooperate in order to realize common goals that are determined via independent actions undertaken individually by the agents. A basic assumption is that the actions taken are unknown in advance to the other agent. These goals can be conveniently summarized in the form of a {\em target matrix}, whose entries are computed by the control system responding to the choices of inputs made by the two agents. We show how to realize such target matrices for a broad class of systems that possess an input-output mapping that is bilinear. One can classify control-communication strategies, known as {\em control protocols}, according to the amount of information sharing occurring between the two agents. Protocols that assume no information sharing on the inputs that each agent selects and protocols that allow sufficient information sharing for identifying the common goals are the two extreme cases. Control protocols will also be evaluated and compared in terms of cost functionals given by integrated quadratic functions of the control inputs. The minimal control cost of the two classes of control protocols are analyzed and compared. The difference in the control costs between the two classes reflects an inherent trade-off between communication complexity and control cost.
Feature Selection for Value Function Approximation Using Bayesian Model Selection
Venue: arXiv cs.AI 2012
Year: 2012

Feature selection in reinforcement learning (RL), i.e. choosing basis functions such that useful approximations of the unkown value function can be obtained, is one of the main challenges in scaling RL to real-world applications. Here we consider the Gaussian process based framework GPTD for approximate policy evaluation, and propose feature selection through marginal likelihood optimization of the associated hyperparameters. Our approach has two appealing benefits: (1) given just sample transitions, we can solve the policy evaluation problem fully automatically (without looking at the learning task, and, in theory, independent of the dimensionality of the state space), and (2) model selection allows us to consider more sophisticated kernels, which in turn enable us to identify relevant subspaces and eliminate irrelevant state variables such that we can achieve substantial computational savings and improved prediction performance.
Learning RoboCup-Keepaway with Kernels
Venue: arXiv cs.AI 2012
Year: 2012

We apply kernel-based methods to solve the difficult reinforcement learning problem of 3vs2 keepaway in RoboCup simulated soccer. Key challenges in keepaway are the high-dimensionality of the state space (rendering conventional discretization-based function approximation like tilecoding infeasible), the stochasticity due to noise and multiple learning agents needing to cooperate (meaning that the exact dynamics of the environment are unknown) and real-time learning (meaning that an efficient online implementation is required). We employ the general framework of approximate policy iteration with least-squares-based policy evaluation. As underlying function approximator we consider the family of regularization networks with subset of regressors approximation. The core of our proposed solution is an efficient recursive implementation with automatic supervised selection of relevant basis functions. Simulation results indicate that the behavior learned through our approach clearly outperforms the best results obtained earlier with tilecoding by Stone et al. (2005).
On the equivalence between Stein and de Bruijn identities
Venue: arXiv cs.IT 2012
Year: 2012

This paper focuses on proving the equivalence between Stein's identity and de Bruijn's identity. Given some conditions, we prove that Stein's identity is equivalent to de Bruijn's identity. In addition, some extensions of de Bruijn's identity are presented. For arbitrary but fixed input and noise distributions, there exist relations between the first derivative of the differential entropy and the posterior mean. Moreover, the second derivative of the differential entropy is related to the Fisher information for arbitrary input and noise distributions. Several applications are presented to support the usefulness of the developed results in this paper.
Moving Target Parameters Estimation in Non-Coherent MIMO Radar Systems
Venue: arXiv cs.IT 2012
Year: 2012

The problem of estimating the parameters of a moving target in multiple-input multiple-output (MIMO) radar is considered and a new approach for estimating the moving target parameters by making use of the phase information associated with each transmit-receive path is introduced. It is required for this technique that different receive antennas have the same time reference, but no synchronization of initial phases of the receive antennas is needed and, therefore, the estimation process is non-coherent. We model the target motion within a certain processing interval as a polynomial of general order. The first three coefficients of such a polynomial correspond to the initial location, velocity, and acceleration of the target, respectively. A new maximum likelihood (ML) technique for estimating the target motion coefficients is developed. It is shown that the considered ML problem can be interpreted as the classic "overdetermined" nonlinear least-squares problem. The proposed ML estimator requires multi-dimensional search over the unknown polynomial coefficients. The Cramér-Rao Bound (CRB) for the proposed parameter estimation problem is derived. The performance of the proposed estimator is validated by simulation results and is shown to achieve the CRB.
On Backhauling of Relay Enhanced Networks in LTE-Advanced
Venue: arXiv cs.NI 2012
Year: 2012

Relaying is considered a promising cost-efficient solution in 3GPP LTE-Advanced for coverage extension and throughput enhancement. The compact physical characteristics and low power requirements of the relay nodes offer more flexible deployment options than traditional macro evolved Node Bs. This paper provides an overview of general relaying concepts and presents the relay deployment within the LTE-Advanced framework. Furthermore, the impact of relay backhauling on envisioned relaying gains is discussed and the methods to improve the performance of the backhauling are included.
Randomization Using Quasigroups, Hadamard and Number Theoretic Transforms
Venue: arXiv cs.CR 2012
Year: 2012

This paper investigates the use of quasigroups, Hadamard transforms and Number Theoretic Transforms for use in sequence randomization. This can also be used to generate hash functions for sequence encryption.
Protocol Coding through Reordering of User Resources, Part I: Capacity Results
Venue: arXiv cs.IT 2012
Year: 2012

The vast existing wireless infrastructure features a variety of systems and standards. It is of significant practical value to introduce new features and devices without changing the physical layer/hardware infrastructure, but upgrade it only in software. A way to achieve it is to apply protocol coding: encode information in the actions taken by a certain (existing) communication protocol. In this work we investigate strategies for protocol coding via combinatorial ordering of the labelled user resources (packets, channels) in an existing, primary system. Such a protocol coding introduces a new secondary communication channel in the existing system, which has been considered in the prior work exclusively in a steganographic context. Instead, we focus on the use of secondary channel for reliable communication with newly introduced secondary devices, that are low-complexity versions of the primary devices, capable only to decode the robustly encoded header information in the primary signals. We introduce a suitable communication model, capable to capture the constraints that the primary system operation puts on protocol coding. We have derived the capacity of the secondary channel under arbitrary error models. The insights from the information-theoretic analysis are used in Part II of this work to design practical error-correcting mechanisms for secondary channels with protocol coding.
Topological Features of Online Social Networks
Venue: arXiv cs.SI 2012
Year: 2012

The importance of modeling and analyzing Social Networks is a consequence of the success of Online Social Networks during last years. Several models of networks have been proposed, reflecting the different characteristics of Social Networks. Some of them fit better to model specific phenomena, such as the growth and the evolution of the Social Networks; others are more appropriate to capture the topological characteristics of the networks. Because these networks show unique and different properties and features, in this work we describe and exploit several models in order to capture the structure of popular Online Social Networks, such as Arxiv, Facebook, Wikipedia and YouTube. Our experimentation aims at verifying the structural characteristics of these networks, in order to understand what model better depicts their structure, and to analyze the inner community structure, to illustrate how members of these Online Social Networks interact and group together into smaller communities.
Cryptographic Path Hardening: Hiding Vulnerabilities in Software through Cryptography
Venue: arXiv cs.SE 2012
Year: 2012

We propose a novel approach to improving software security called Cryptographic Path Hardening, which is aimed at hiding security vulnerabilities in software from attackers through the use of provably secure and obfuscated cryptographic devices to harden paths in programs. By "harden" we mean that certain error-checking if-conditionals in a given program P are replaced by equivalent" we mean that adversaries cannot use semi-automatic program analysis techniques to reason about the hardened program paths and thus cannot discover as-yet-unknown errors along those paths, except perhaps through black-box dictionary attacks or random testing (which we can never prevent). Other than these unpreventable attack methods, we can make program analysis aimed at error-finding "provably hard" for a resource-bounded attacker, in the same sense that cryptographic schemes are hard to break. Unlike security-through-obscurity, in Cryptographic Path Hardening we use provably-secure crypto devices to hide errors and our mathematical arguments of security are the same as the standard ones used in cryptography. One application of Cryptographic Path Hardening is that software patches or filters often reveal enough information to an attacker that they can be used to construct error-revealing inputs to exploit an unpatched version of the program. By "hardening" the patch we make it difficult for the attacker to analyze the patched program to construct error-revealing inputs, and thus prevent him from potentially constructing exploits.
Coalitional Games in Partition Form for Joint Spectrum Sensing and Access in Cognitive Radio Networks
Venue: arXiv cs.IT 2012
Year: 2012

Unlicensed secondary users (SUs) in cognitive radio networks are subject to an inherent tradeoff between spectrum sensing and spectrum access. Although each SU has an incentive to sense the primary user (PU) channels for locating spectrum holes, this exploration of the spectrum can come at the expense of a shorter transmission time, and, hence, a possibly smaller capacity for data transmission. This paper investigates the impact of this tradeoff on the cooperative strategies of a network of SUs that seek to cooperate in order to improve their view of the spectrum (sensing), reduce the possibility of interference among each other, and improve their transmission capacity (access). The problem is modeled as a coalitional game in partition form and an algorithm for coalition formation is proposed. Using the proposed algorithm, the SUs can make individual distributed decisions to join or leave a coalition while maximizing their utilities which capture the average time spent for sensing as well as the capacity achieved while accessing the spectrum. It is shown that, by using the proposed algorithm, the SUs can self-organize into a network partition composed of disjoint coalitions, with the members of each coalition cooperating to jointly optimize their sensing and access performance. Simulation results show the performance improvement that the proposed algorithm yields with respect to the non-cooperative case. The results also show how the algorithm allows the SUs to self-adapt to changes in the environment such as the change in the traffic of the PUs, or slow mobility.
Relational Semantics for Databases and Predicate Calculus
Venue: arXiv cs.DB 2012
Year: 2012

The relational data model requires a theory of relations in which tuples are not only many-sorted, but can also have indexes that are not necessarily numerical. In this paper we develop such a theory and define operations on relations that are adequate for database use. The operations are similar to those of Codd's relational algebra, but differ in being based on a mathematically adequate theory of relations. The semantics of predicate calculus, being oriented toward the concept of satisfiability, is not suitable for relational databases. We develop an alternative semantics that assigns relations as meaning to formulas with free variables. This semantics makes the classical predicate calculus suitable as a query language for relational databases.
A Resolution for Shared Memory Conflict in Multiprocessor System-on-a-Chip
Venue: arXiv cs.AR 2012
Year: 2012

Now days, manufacturers are focusing on increasing the concurrency in multiprocessor system-on-a-chip (MPSoC) architecture instead of increasing clock speed, for embedded systems. Traditionally lock-based synchronization is provided to support concurrency; as managing locks can be very difficult and error prone. Transactional memories and lock based systems have been extensively used to provide synchronization between multiple processors [1] in general-purpose systems. It has been shown that locks have numerous shortcomings over transactional memory in terms of power consumption, ease of programming and performance. In this paper, we propose a new semaphore scheme for synchronization in shared cache memory in an MPSoC. Moreover, we have evaluated and compared our scheme with locks and transactions in terms of energy consumption and cache miss rate using SimpleScalar functional simulator.
New Geometrical Spectra of Linear Codes with Applications to Performance Analysis
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, new enumerating functions for linear codes are defined, including the triangle enumerating function and the tetrahedron enumerating function, both of which can be computed using a trellis-based algorithm over polynomial rings. The computational complexity is dominated by the complexity of the trellis. In addition, we show that these new enumerating functions can be used to improve existing performance bounds on the maximum likelihood decoding.
Assessment of OGC Web Processing Services for REST principles
Venue: arXiv cs.SE 2012
Year: 2012

Recent distributed computing trends advocate the use of Representational State Transfer (REST) to alleviate the inherent complexity of the Web services standards in building service-oriented web applications. In this paper we focus on the particular case of geospatial services interfaced by the OGC Web Processing Service (WPS) specification in order to assess whether WPS-based geospatial services can be viewed from the architectural principles exposed in REST. Our concluding remarks suggest that the adoption of REST principles, to specially harness the built-in mechanisms of the HTTP application protocol, may be beneficial in scenarios where ad hoc composition of geoprocessing services are required, common for most non-expert users of geospatial information infrastructures.
Reducibility of joint relay positioning and flow optimization problem
Venue: arXiv cs.IT 2012
Year: 2012

This paper shows how to reduce the otherwise hard joint relay positioning and flow optimization problem into a sequence a two simpler decoupled problems. We consider a class of wireless multicast hypergraphs mainly characterized by their hyperarc rate functions, that are increasing and convex in power, and decreasing in distance between the transmit node and the farthest end node of the hyperarc. The set-up consists of a single multicast flow session involving a source, multiple destinations and a relay that can be positioned freely. The first problem formulates the relay positioning problem in a purely geometric sense, and once the optimal relay position is obtained the second problem addresses the flow optimization. Furthermore, we present simple and efficient algorithms to solve these problems.
A Reconstruction Error Formulation for Semi-Supervised Multi-task and Multi-view Learning
Venue: arXiv cs.LG 2012
Year: 2012

A significant challenge to make learning techniques more suitable for general purpose use is to move beyond i) complete supervision, ii) low dimensional data, iii) a single task and single view per instance. Solving these challenges allows working with "Big Data" problems that are typically high dimensional with multiple (but possibly incomplete) labelings and views. While other work has addressed each of these problems separately, in this paper we show how to address them together, namely semi-supervised dimension reduction for multi-task and multi-view learning (SSDR-MML), which performs optimization for dimension reduction and label inference in semi-supervised setting. The proposed framework is designed to handle both multi-task and multi-view learning settings, and can be easily adapted to many useful applications. Information obtained from all tasks and views is combined via reconstruction errors in a linear fashion that can be efficiently solved using an alternating optimization scheme. Our formulation has a number of advantages. We explicitly model the information combining mechanism as a data structure (a weight/nearest-neighbor matrix) which allows investigating fundamental questions in multi-task and multi-view learning. We address one such question by presenting a general measure to quantify the success of simultaneous learning of multiple tasks or from multiple views. We show that our SSDR-MML approach can outperform many state-of-the-art baseline methods and demonstrate the effectiveness of connecting dimension reduction and learning.
Improving feature selection algorithms using normalised feature histograms
Venue: arXiv cs.AI 2012
Year: 2012

The proposed feature selection method builds a histogram of the most stable features from random subsets of a training set and ranks the features based on a classifier based cross-validation. This approach reduces the instability of features obtained by conventional feature selection methods that occur with variation in training data and selection criteria. Classification results on four microarray and three image datasets using three major feature selection criteria and a naive Bayes classifier show considerable improvement over benchmark results.
π-Control: A Personal Cloud Control Centre
Venue: arXiv cs.DC 2012
Year: 2012

Consumption of online services and cloud computing offerings is on the rise, largely due to compelling advantages over traditional local applications. From a user perspective, these include zero-maintenance of software, the always-on nature of such services, mashups of different applications and the networking effect with other users. Associated disadvantages are known, but effective means and tools to limit their effect are not yet well-established and not yet generally available to service users. We propose (1) a user-centric model of cloud elements beyond the conventional <SPI>aaS layers, including activities across trust zones, and (2) a personal control console for all individual and collaborative user activities in the cloud.