OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Strategies for Single/Multi-Target Jamming on MIMO Gaussian Channels
Venue: arXiv cs.IT 2014
Year: 2014

The problem of jamming on multiple-input multiple-output (MIMO) Gaussian channels is investigated in this paper. In the case of a single target legitimate signal, we show that the existing result based on the simplification of the system model by neglecting the jamming channel leads to losing important insights regarding the effect of jamming power and jamming channel on the jamming strategy. We find a closed-form optimal solution for the problem under a positive semi-definite (PSD) condition without considering simplifications in the model. If the condition is not satisfied and the optimal solution may not exist in closed-form, we find the optimal solution using a numerical method and also propose a suboptimal solution in closed-form as a close approximation of the optimal solution. Then, the possibility of extending the results to solve the problem of multi-target jamming is investigated for four scenarios, i.e., multiple access channel, broadcasting channel, multiple transceiver pairs with orthogonal transmissions, and multiple transceiver pairs with interference, respectively. It is shown that the proposed numerical method can be extended to all scenarios while the proposed closed-form solutions for jamming may be applied in the scenarios of the multiple access channel and multiple transceiver pairs with orthogonal transmissions. Simulation results verify the effectiveness of the proposed solutions.
Modeling Concept Combinations in a Quantum-theoretic Framework
Venue: arXiv cs.AI 2014
Year: 2014

We present modeling for conceptual combinations which uses the mathematical formalism of quantum theory. Our model faithfully describes a large amount of experimental data collected by different scholars on concept conjunctions and disjunctions. Furthermore, our approach sheds a new light on long standing drawbacks connected with vagueness, or fuzziness, of concepts, and puts forward a completely novel possible solution to the 'combination problem' in concept theory. Additionally, we introduce an explanation for the occurrence of quantum structures in the mechanisms and dynamics of concepts and, more generally, in cognitive and decision processes, according to which human thought is a well structured superposition of a 'logical thought' and a 'conceptual thought', and the latter usually prevails over the former, at variance with some widespread beliefs
Multipath Private Communication: An Information Theoretic Approach
Venue: arXiv cs.CR 2014
Year: 2014

Sending private messages over communication environments under surveillance is an important challenge in communication security and has attracted attentions of cryptographers through time. We believe that resources other than cryptographic keys can be used for communication privacy. We consider private message transmission (PMT) in an abstract multipath communication model between two communicants, Alice and Bob, in the presence of an eavesdropper, Eve. Alice and Bob have pre-shared keys and Eve is computationally unbounded. There are a total of $n$ paths and the three parties can have simultaneous access to at most $t_a$, $t_b$, and $t_e$ paths. The parties can switch their paths after every $λ$ bits of communication. We study perfect (P)-PMT versus asymptotically-perfect (AP)-PMT protocols. The former has zero tolerance of transmission error and leakage, whereas the latter allows for positive error and leakage that tend to zero as the message length increases. We derive the necessary and sufficient conditions under which P-PMT and AP-PMT are possible. We also introduce explicit P-PMT and AP-PMT constructions. Our results show AP-PMT protocols attain much higher information rates than P-PMT ones. Interestingly, AP-PMT is possible even in poorest condition where $t_a=t_b=1$ and $t_e=n-1$. It remains however an open question whether the derived rates can be improved by more sophisticated AP-PMT protocols. We study applications of our results to private communication over the real-life scenarios of multiple-frequency links and multiple-route networks. We show practical examples of such scenarios that can be abstracted by the multipath setting: Our results prove the possibility of keyless information-theoretic private message transmission at rates $17\%$ and $20\%$ for the two example scenarios, respectively. We discuss open problems and future work at the end.
An Experimental Evaluation of List Coloring Algorithms
Venue: arXiv cs.DS 2014
Year: 2014

The list coloring problem is a variant of vertex coloring where a vertex may be colored only a color from a prescribed set. Several applications of vertex coloring are more appropriately modelled as instances of list coloring and thus we argue that it is an important problem to consider. Regardless of the importance of list coloring, few published algorithms exist for it. In this paper we review the only two existing ones we could find and propose an exact branch and bound one. We conduct an experimental evaluation of the three algorithms.
Power Aware Wireless File Downloading: A Constrained Restless Bandit Approach
Venue: arXiv cs.PF 2014
Year: 2014

This paper treats power-aware throughput maximization in a multi-user file downloading system. Each user can receive a new file only after its previous file is finished. The file state processes for each user act as coupled Markov chains that form a generalized restless bandit system. First, an optimal algorithm is derived for the case of one user. The algorithm maximizes throughput subject to an average power constraint. Next, the one-user algorithm is extended to a low complexity heuristic for the multi-user problem. The heuristic uses a simple online index policy and its effectiveness is shown via simulation. For simple 3-user cases where the optimal solution can be computed offline, the heuristic is shown to be near-optimal for a wide range of parameters.
Constructing Reference Sets from Unstructured, Ungrammatical Text
Venue: arXiv cs.CL 2014
Year: 2014

Vast amounts of text on the Web are unstructured and ungrammatical, such as classified ads, auction listings, forum postings, etc. We call such text "posts." Despite their inconsistent structure and lack of grammar, posts are full of useful information. This paper presents work on semi-automatically building tables of relational information, called "reference sets," by analyzing such posts directly. Reference sets can be applied to a number of tasks such as ontology maintenance and information extraction. Our reference-set construction method starts with just a small amount of background knowledge, and constructs tuples representing the entities in the posts to form a reference set. We also describe an extension to this approach for the special case where even this small amount of background knowledge is impossible to discover and use. To evaluate the utility of the machine-constructed reference sets, we compare them to manually constructed reference sets in the context of reference-set-based information extraction. Our results show the reference sets constructed by our method outperform manually constructed reference sets. We also compare the reference-set-based extraction approach using the machine-constructed reference set to supervised extraction approaches using generic features. These results demonstrate that using machine-constructed reference sets outperforms the supervised methods, even though the supervised methods require training data.
Fast Set Bounds Propagation Using a BDD-SAT Hybrid
Venue: arXiv cs.AI 2014
Year: 2014

Binary Decision Diagram (BDD) based set bounds propagation is a powerful approach to solving set-constraint satisfaction problems. However, prior BDD based techniques in- cur the significant overhead of constructing and manipulating graphs during search. We present a set-constraint solver which combines BDD-based set-bounds propagators with the learning abilities of a modern SAT solver. Together with a number of improvements beyond the basic algorithm, this solver is highly competitive with existing propagation based set constraint solvers.
Intrusion Detection using Continuous Time Bayesian Networks
Venue: arXiv cs.AI 2014
Year: 2014

Intrusion detection systems (IDSs) fall into two high-level categories: network-based systems (NIDS) that monitor network behaviors, and host-based systems (HIDS) that monitor system calls. In this work, we present a general technique for both systems. We use anomaly detection, which identifies patterns not conforming to a historic norm. In both types of systems, the rates of change vary dramatically over time (due to burstiness) and over components (due to service difference). To efficiently model such systems, we use continuous time Bayesian networks (CTBNs) and avoid specifying a fixed update interval common to discrete-time models. We build generative models from the normal training data, and abnormal behaviors are flagged based on their likelihood under this norm. For NIDS, we construct a hierarchical CTBN model for the network packet traces and use Rao-Blackwellized particle filtering to learn the parameters. We illustrate the power of our method through experiments on detecting real worms and identifying hosts on two publicly available network traces, the MAWI dataset and the LBNL dataset. For HIDS, we develop a novel learning method to deal with the finite resolution of system log file time stamps, without losing the benefits of our continuous time model. We demonstrate the method by detecting intrusions in the DARPA 1998 BSM dataset.
Implicit Abstraction Heuristics
Venue: arXiv cs.AI 2014
Year: 2014

State-space search with explicit abstraction heuristics is at the state of the art of cost-optimal planning. These heuristics are inherently limited, nonetheless, because the size of the abstract space must be bounded by some, even if a very large, constant. Targeting this shortcoming, we introduce the notion of (additive) implicit abstractions, in which the planning task is abstracted by instances of tractable fragments of optimal planning. We then introduce a concrete setting of this framework, called fork-decomposition, that is based on two novel fragments of tractable cost-optimal planning. The induced admissible heuristics are then studied formally and empirically. This study testifies for the accuracy of the fork decomposition heuristics, yet our empirical evaluation also stresses the tradeoff between their accuracy and the runtime complexity of computing them. Indeed, some of the power of the explicit abstraction heuristics comes from precomputing the heuristic function offline and then determining h(s) for each evaluated state s by a very fast lookup in a database. By contrast, while fork-decomposition heuristics can be calculated in polynomial time, computing them is far from being fast. To address this problem, we show that the time-per-node complexity bottleneck of the fork-decomposition heuristics can be successfully overcome. We demonstrate that an equivalent of the explicit abstraction notion of a database exists for the fork-decomposition abstractions as well, despite their exponential-size abstract spaces. We then verify empirically that heuristic search with the databased" fork-decomposition heuristics favorably competes with the state of the art of cost-optimal planning.
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
Venue: arXiv cs.LO 2014
Year: 2014

We offer a new understanding of some aspects of practical SAT-solvers that are based on DPLL with unit-clause propagation, clause-learning, and restarts. We do so by analyzing a concrete algorithm which we claim is faithful to what practical solvers do. In particular, before making any new decision or restart, the solver repeatedly applies the unit-resolution rule until saturation, and leaves no component to the mercy of non-determinism except for some internal randomness. We prove the perhaps surprising fact that, although the solver is not explicitly designed for it, with high probability it ends up behaving as width-k resolution after no more than O(n^2k+2) conflicts and restarts, where n is the number of variables. In other words, width-k resolution can be thought of as O(n^2k+2) restarts of the unit-resolution rule with learning.
Scaling up Heuristic Planning with Relational Decision Trees
Venue: arXiv cs.AI 2014
Year: 2014

Current evaluation functions for heuristic planning are expensive to compute. In numerous planning problems these functions provide good guidance to the solution, so they are worth the expense. However, when evaluation functions are misguiding or when planning problems are large enough, lots of node evaluations must be computed, which severely limits the scalability of heuristic planners. In this paper, we present a novel solution for reducing node evaluations in heuristic planning based on machine learning. Particularly, we define the task of learning search control for heuristic planning as a relational classification task, and we use an off-the-shelf relational classification tool to address this learning task. Our relational classification task captures the preferred action to select in the different planning contexts of a specific planning domain. These planning contexts are defined by the set of helpful actions of the current state, the goals remaining to be achieved, and the static predicates of the planning task. This paper shows two methods for guiding the search of a heuristic planner with the learned classifiers. The first one consists of using the resulting classifier as an action policy. The second one consists of applying the classifier to generate lookahead states within a Best First Search algorithm. Experiments over a variety of domains reveal that our heuristic planner using the learned classifiers solves larger problems than state-of-the-art planners.
Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
Venue: arXiv cs.AI 2014
Year: 2014

The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results -- the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains -- we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish easy domains from hard ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.
Decidability and Undecidability Results for Propositional Schemata
Venue: arXiv cs.LO 2014
Year: 2014

We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions and iterated connectives ranging over intervals parameterized by arithmetic variables. The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.
Policy Invariance under Reward Transformations for General-Sum Stochastic Games
Venue: arXiv cs.GT 2014
Year: 2014

We extend the potential-based shaping method from Markov decision processes to multi-player general-sum stochastic games. We prove that the Nash equilibria in a stochastic game remains unchanged after potential-based shaping is applied to the environment. The property of policy invariance provides a possible way of speeding convergence when learning to play a stochastic game.
Centrality-as-Relevance: Support Sets and Similarity as Geometric Proximity
Venue: arXiv cs.IR 2014
Year: 2014

In automatic summarization, centrality-as-relevance means that the most important content of an information source, or a collection of information sources, corresponds to the most central passages, considering a representation where such notion makes sense (graph, spatial, etc.). We assess the main paradigms, and introduce a new centrality-based relevance model for automatic summarization that relies on the use of support sets to better estimate the relevant content. Geometric proximity is used to compute semantic relatedness. Centrality (relevance) is determined by considering the whole input source (and not only local information), and by taking into account the existence of minor topics or lateral subjects in the information sources to be summarized. The method consists in creating, for each passage of the input source, a support set consisting only of the most semantically related passages. Then, the determination of the most relevant content is achieved by selecting the passages that occur in the largest number of support sets. This model produces extractive summaries that are generic, and language- and domain-independent. Thorough automatic evaluation shows that the method achieves state-of-the-art performance, both in written text, and automatically transcribed speech summarization, including when compared to considerably more complex approaches.
Scheduling Bipartite Tournaments to Minimize Total Travel Distance
Venue: arXiv cs.AI 2014
Year: 2014

In many professional sports leagues, teams from opposing leagues/conferences compete against one another, playing inter-league games. This is an example of a bipartite tournament. In this paper, we consider the problem of reducing the total travel distance of bipartite tournaments, by analyzing inter-league scheduling from the perspective of discrete optimization. This research has natural applications to sports scheduling, especially for leagues such as the National Basketball Association (NBA) where teams must travel long distances across North America to play all their games, thus consuming much time, money, and greenhouse gas emissions. We introduce the Bipartite Traveling Tournament Problem (BTTP), the inter-league variant of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our theoretical results to the 12-team Nippon Professional Baseball (NPB) league in Japan, producing a provably-optimal schedule requiring 42950 kilometres of total team travel, a 16% reduction compared to the actual distance traveled by these teams during the 2010 NPB season. We also develop a nearly-optimal inter-league tournament for the 30-team NBA league, just 3.8% higher than the trivial theoretical lower bound.
Towards Autotuning of OpenMP Applications on Multicore Architectures
Venue: arXiv cs.DC 2014
Year: 2014

In this paper we describe an autotuning tool for optimization of OpenMP applications on highly multicore and multithreaded architectures. Our work was motivated by in-depth performance analysis of scientific applications and synthetic benchmarks on IBM Power 775 architecture. The tool provides an automatic code instrumentation of OpenMP parallel regions. Based on measurement of chosen hardware performance counters the tool decides on the number of parallel threads that should be used for execution of chosen code fragments.
Convex Optimization for Binary Classifier Aggregation in Multiclass Problems
Venue: arXiv cs.LG 2014
Year: 2014

Multiclass problems are often decomposed into multiple binary problems that are solved by individual binary classifiers whose results are integrated into a final answer. Various methods, including all-pairs (APs), one-versus-all (OVA), and error correcting output code (ECOC), have been studied, to decompose multiclass problems into binary problems. However, little study has been made to optimally aggregate binary problems to determine a final answer to the multiclass problem. In this paper we present a convex optimization method for an optimal aggregation of binary classifiers to estimate class membership probabilities in multiclass problems. We model the class membership probability as a softmax function which takes a conic combination of discrepancies induced by individual binary classifiers, as an input. With this model, we formulate the regularized maximum likelihood estimation as a convex optimization problem, which is solved by the primal-dual interior point method. Connections of our method to large margin classifiers are presented, showing that the large margin formulation can be considered as a limiting case of our convex formulation. Numerical experiments on synthetic and real-world data sets demonstrate that our method outperforms existing aggregation methods as well as direct methods, in terms of the classification accuracy and the quality of class membership probability estimates.
The Cognitive Compressive Sensing Problem
Venue: arXiv cs.IT 2014
Year: 2014

In the Cognitive Compressive Sensing (CCS) problem, a Cognitive Receiver (CR) seeks to optimize the reward obtained by sensing an underlying $N$ dimensional random vector, by collecting at most $K$ arbitrary projections of it. The $N$ components of the latent vector represent sub-channels states, that change dynamically from "busy" to "idle" and vice versa, as a Markov chain that is biased towards producing sparse vectors. To identify the optimal strategy we formulate the Multi-Armed Bandit Compressive Sensing (MAB-CS) problem, generalizing the popular Cognitive Spectrum Sensing model, in which the CR can sense $K$ out of the $N$ sub-channels, as well as the typical static setting of Compressive Sensing, in which the CR observes $K$ linear combinations of the $N$ dimensional sparse vector. The CR opportunistic choice of the sensing matrix should balance the desire of revealing the state of as many dimensions of the latent vector as possible, while not exceeding the limits beyond which the vector support is no longer uniquely identifiable.
Preserving the Basic Property of Stable Matching by Deleting a pair
Venue: arXiv cs.DS 2014
Year: 2014

This paper describes the transition of a male-pessimal matching set to optimal when it is a man-oriented approach by deleting a pair from matching set considering the score based approach. A descriptive explanation of the proposed algorithm both in a sequential and parallel manner is given. The comparison based theoretical analysis shows that the best case of the algorithm is lower bound of n3.