OpenRaiser/Intern-Atlas huggingface dataset:
Scalable and Accurate Online Feature Selection for Big Data
Venue: arXiv cs.LG 2016
Year: 2016

Feature selection is important in many big data applications. Two critical challenges closely associate with big data. Firstly, in many big data applications, the dimensionality is extremely high, in millions, and keeps growing. Secondly, big data applications call for highly scalable feature selection algorithms in an online manner such that each feature can be processed in a sequential scan. We present SAOLA, a Scalable and Accurate OnLine Approach for feature selection in this paper. With a theoretical analysis on bounds of the pairwise correlations between features, SAOLA employs novel pairwise comparison techniques and maintain a parsimonious model over time in an online manner. Furthermore, to deal with upcoming features that arrive by groups, we extend the SAOLA algorithm, and then propose a new group-SAOLA algorithm for online group feature selection. The group-SAOLA algorithm can online maintain a set of feature groups that is sparse at the levels of both groups and individual features simultaneously. An empirical study using a series of benchmark real data sets shows that our two algorithms, SAOLA and group-SAOLA, are scalable on data sets of extremely high dimensionality, and have superior performance over the state-of-the-art feature selection methods.
On the roots and minimum rank distance of skew cyclic codes
Venue: arXiv cs.IT 2016
Year: 2016

Skew cyclic codes play the same role as cyclic codes in the theory of error-correcting codes for the rank metric. In this paper, we give descriptions of these codes by root spaces, cyclotomic spaces and idempotent generators. We prove that the lattice of skew cyclic codes is anti-isomorphic to the lattice of root spaces, study these two lattices and extend the rank-BCH bound on their minimum rank distance to rank-metric versions of the van Lint-Wilson's shift and Hartmann-Tzeng bounds. Finally, we study skew cyclic codes which are linear over the base field, proving that these codes include all Hamming-metric cyclic codes, giving then a new relation between these codes and rank-metric skew cyclic codes.
Decidability of regular language genus computation
Venue: arXiv cs.FL 2016
Year: 2016

The article continues the study of the genus of regular languages that the authors introduced in a 2012 paper. Generalizing a previous result, we produce a new family of regular languages on a two-letter alphabet having arbitrary high genus. Let $L$ be a regular language. In order to understand the genus $g(L)$ of $L$, we introduce the topological size of $|L|_{\rm{top}}$ to be the minimal size of all finite deterministic automata of genus $g(L)$ computing $L$. We show that the minimal finite deterministic automaton of a regular language can be arbitrary far away from a finite deterministic automaton realizing the minimal genus and computing the same language, both in terms of the difference of genera and in terms of the difference in size. In particular, we show that the topological size $|L|_{\rm{top}}$ can grow at least exponentially in size $|L|$. We conjecture however the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R.V. Book and A.K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles.
Neural Enquirer: Learning to Query Tables with Natural Language
Venue: arXiv cs.AI 2016
Year: 2016

We proposed Neural Enquirer as a neural network architecture to execute a natural language (NL) query on a knowledge-base (KB) for answers. Basically, Neural Enquirer finds the distributed representation of a query and then executes it on knowledge-base tables to obtain the answer as one of the values in the tables. Unlike similar efforts in end-to-end training of semantic parsers, Neural Enquirer is fully "neuralized": it not only gives distributional representation of the query and the knowledge-base, but also realizes the execution of compositional queries as a series of differentiable operations, with intermediate results (consisting of annotations of the tables at different levels) saved on multiple layers of memory. Neural Enquirer can be trained with gradient descent, with which not only the parameters of the controlling components and semantic parsing component, but also the embeddings of the tables and query words can be learned from scratch. The training can be done in an end-to-end fashion, but it can take stronger guidance, e.g., the step-by-step supervision for complicated queries, and benefit from it. Neural Enquirer is one step towards building neural network systems which seek to understand language by executing it on real-world. Our experiments show that Neural Enquirer can learn to execute fairly complicated NL queries on tables with rich structures.
New Lace and Arsenic: adventures in weak memory with a program logic
Venue: arXiv cs.LO 2016
Year: 2016

We describe a program logic for weak memory (also known as relaxed memory). The logic is based on Hoare logic within a thread, and rely/guarantee between threads. It is presented via examples, giving proofs of many weak-memory litmus tests. It extends to coherence but not yet to synchronised assignment (compare-and-swap, load-logical/store-conditional). It deals with conditionals and loops but not yet arrays or heap. The logic uses a version of Hoare logic within threads, and a version of rely/guarantee between threads, with five stability rules to handle various kinds of parallelism (external, internal, propagation-free and two kinds of in-flight parallelism). There are $\mathbb{B}$ and $\mathbb{U}$ modalities to regulate propagation, and temporal modalities $\mathsf{since}$, $\mathbb{S}\mathsf{ofar}$ and $\mathbb{O}\mathsf{uat}$ to deal with global coherence (SC per location). The logic is presented by example. Proofs and unproofs of about thirty weak-memory examples, including many litmus tests in various guises, are dealt with in detail. There is a proof of a version of the token ring. In version 2: The correspondence with Herding Cats has been clarified. The stability rules have been simplified: in particular the sat and x= x tests have been eliminated from external stability checks. The embedding is simplified and has a more transparent relation to the mechanisms of the logic. Definitions of U, Sofar and Ouat have been considerably altered. The description of modalities and the treatment of termination has been reworked. Many proofs are reconstructed. A comprehensive summary of the logic is an appendix.
A Prediction Study of Path Loss Models from 2-73.5 GHz in an Urban-Macro Environment
Venue: arXiv cs.IT 2016
Year: 2016

It is becoming clear that 5G wireless systems will encompass frequencies from around 500 MHz all the way to around 100 GHz. To adequately assess the performance of 5G systems in these different bands, path loss (PL) models will need to be developed across this wide frequency range. The PL models can roughly be broken into two categories, ones that have some anchor in physics, and ones that curve-match only over the data set without any physical anchor. In this paper we use both real-world measurements from 2 to 28 GHz and ray-tracing studies from 2 to 73.5 GHz, both in an urban-macro environment, to assess the prediction performance of the two PL modeling techniques. In other words, we look at how the two different PL modeling techniques perform when the PL model is applied to a prediction set which is different in distance, frequency, or environment from a measurement set where the parameters of the respective models are determined. We show that a PL model with a physical anchor point can be a better predictor of PL performance in the prediction sets while also providing a parameterization which is more stable over a substantial number of different measurement sets.
Distributed protocols for spanning tree construction and leader election
Venue: arXiv cs.DC 2016
Year: 2016

We present fast deterministic distributed protocols in synchronous networks for leader election and spanning tree construction. The protocols are designed under the assumption that nodes in a network have identifiers but the size of an identifier is unlimited. So time bounds of protocols depend on the sizes of identifiers. We present fast protocols running in time $O(D\log L+L)$, where $L$ is the size of the minimal identifier and $D$ is the diameter of a network.
Rates Achievable on a Fiber-Optical Split-Step Fourier Channel
Venue: arXiv cs.IT 2016
Year: 2016

A lower bound on the capacity of the split-step Fourier channel is derived. The channel under study is a concatenation of smaller segments, within which three operations are performed on the signal, namely, nonlinearity, linearity, and noise addition. Simulation results indicate that for a fixed number of segments, our lower bound saturates in the high-power regime and that the larger the number of segments is, the higher is the saturation point. We also obtain an alternative lower bound, which is less tight but has a simple closed-form expression. This bound allows us to conclude that the saturation point grows unbounded with the number of segments. Specifically, it grows as $c+(1/2)\log(K)$, where $K$ is the number of segments and $c$ is a constant. The connection between our channel model and the nonlinear Schrödinger equation is discussed.
Parallel and sequential reclaiming in multicore real-time global scheduling
Venue: arXiv cs.OS 2016
Year: 2016

When integrating hard, soft and non-real-time tasks in general purpose operating systems, it is necessary to provide temporal isolation so that the timing properties of one task do not depend on the behaviour of the others. However, strict budget enforcement can lead to inefficient use of the computational resources in the presence of tasks with variable workload. Many resource reclaiming algorithms have been proposed in the literature for single processor scheduling, but not enough work exists for global scheduling in multiprocessor systems. In this report, we propose two reclaiming algorithms for multiprocessor global scheduling and we prove their correctness.
Visualizing Deep Convolutional Neural Networks Using Natural Pre-Images
Venue: arXiv cs.CV 2016
Year: 2016

Image representations, from SIFT and bag of visual words to Convolutional Neural Networks (CNNs) are a crucial component of almost all computer vision systems. However, our understanding of them remains limited. In this paper we study several landmark representations, both shallow and deep, by a number of complementary visualization techniques. These visualizations are based on the concept of "natural pre-image", namely a natural-looking image whose representation has some notable property. We study in particular three such visualizations: inversion, in which the aim is to reconstruct an image from its representation, activation maximization, in which we search for patterns that maximally stimulate a representation component, and caricaturization, in which the visual patterns that a representation detects in an image are exaggerated. We pose these as a regularized energy-minimization framework and demonstrate its generality and effectiveness. In particular, we show that this method can invert representations such as HOG more accurately than recent alternatives while being applicable to CNNs too. Among our findings, we show that several layers in CNNs retain photographically accurate information about the image, with different degrees of geometric and photometric invariance.
Traffic Differentiation in Dense Collision-free WLANs using CSMA/ECA
Venue: arXiv cs.NI 2016
Year: 2016

The ability to perform traffic differentiation is a promising feature of the current Medium Access Control (MAC) in Wireless Local Area Networks (WLANs). The Enhanced Distributed Channel Access (EDCA) protocol for WLANs proposes up to four Access Categories (AC) that can be mapped to different traffic priorities. High priority ACs are allowed to transmit more often than low priority ACs, providing a way of prioritising delay sensitive traffic like voice calls or video streaming. Further, EDCA also considers the intricacies related to the management of multiple queues, virtual collisions and traffic differentiation. Nevertheless, EDCA falls short in efficiency when performing in dense WLAN scenarios. Its collision-prone contention mechanism degrades the overall throughput to the point of starving low priority ACs, and produce priority inversions at high number of contenders. Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA) is a compatible MAC protocol for WLANs which is also capable of providing traffic differentiation. Contrary to EDCA, CSMA/ECA uses a contention mechanism with a deterministic backoff technique which is capable of constructing collision-free schedules for many nodes with multiple active ACs, extending the network capacity without starving low priority ACs, as experienced in EDCA. This work analyses traffic differentiation with CSMA/ECA by describing the mechanisms used to construct collision-free schedules with multiple queues. Additionally, evaluates the performance under different traffic conditions and a growing number of contenders. (arXiv's abstract field is not large enough for the paper's abstract, please download the paper for the complete abstract.)
Applications of $α$-strongly regular distributions to Bayesian auctions
Venue: arXiv cs.GT 2016
Year: 2016

Two classes of distributions that are widely used in the analysis of Bayesian auctions are the Monotone Hazard Rate (MHR) and Regular distributions. They can both be characterized in terms of the rate of change of the associated virtual value functions: for MHR distributions the condition is that for values $v < v'$, $ϕ(v') - ϕ(v) \ge v' - v$, and for regular distributions, $ϕ(v') - ϕ(v) \ge 0$. Cole and Roughgarden introduced the interpolating class of $α$-Strongly Regular distributions ($α$-SR distributions for short), for which $ϕ(v') - ϕ(v) \ge α(v' - v)$, for $0 \le α\le 1$. In this paper, we investigate five distinct auction settings for which good expected revenue bounds are known when the bidders' valuations are given by MHR distributions. In every case, we show that these bounds degrade gracefully when extended to $α$-SR distributions. For four of these settings, the auction mechanism requires knowledge of these distribution(s) (in the other setting, the distributions are needed only to ensure good bounds on the expected revenue). In these cases we also investigate what happens when the distributions are known only approximately via samples, specifically how to modify the mechanisms so that they remain effective and how the expected revenue depends on the number of samples.
Relative Entropy in Biological Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper we review various information-theoretic characterizations of the approach to equilibrium in biological systems. The replicator equation, evolutionary game theory, Markov processes and chemical reaction networks all describe the dynamics of a population or probability distribution. Under suitable assumptions, the distribution will approach an equilibrium with the passage of time. Relative entropy - that is, the Kullback--Leibler divergence, or various generalizations of this - provides a quantitative measure of how far from equilibrium the system is. We explain various theorems that give conditions under which relative entropy is nonincreasing. In biochemical applications these results can be seen as versions of the Second Law of Thermodynamics, stating that free energy can never increase with the passage of time. In ecological applications, they make precise the notion that a population gains information from its environment as it approaches equilibrium.
Staircase Codes for Secret Sharing with Optimal Communication and Read Overheads
Venue: arXiv cs.IT 2016
Year: 2016

We study the communication efficient secret sharing (CESS) problem introduced by Huang, Langberg, Kliewer and Bruck. A classical threshold secret sharing scheme randomly encodes a secret into $n$ shares given to $n$ parties, such that any set of at least $t$, $t<n$, parties can reconstruct the secret, and any set of at most $z$, $z<t$, parties cannot obtain any information about the secret. Recently, Huang et al. characterized the achievable minimum communication overhead (CO) necessary for a legitimate user to decode the secret when contacting $d\geq t$ parties and presented explicit code constructions achieving minimum CO for $d=n$. The intuition behind the possible savings on CO is that the user is only interested in decoding the secret and does not have to decode the random keys involved in the encoding process. In this paper, we introduce a new class of linear CESS codes called Staircase Codes over any field $GF(q)$, for any prime power $q> n$. We describe two explicit constructions of Staircase codes that achieve minimum communication and read overheads respectively for a fixed $d$, and universally for all possible values of $d, t\leq d\leq n$.
Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games
Venue: arXiv cs.GT 2016
Year: 2016

We study the optimization problem faced by a perfectly informed principal in a Bayesian game, who reveals information to the players about the state of nature to obtain a desirable equilibrium. This signaling problem is the natural design question motivated by uncertainty in games and has attracted much recent attention. We present new hardness results for signaling problems in (a) Bayesian two-player zero-sum games, and (b) Bayesian network routing games. For Bayesian zero-sum games, when the principal seeks to maximize the equilibrium utility of a player, we show that it is NP-hard to obtain an additive FPTAS. Our hardness proof exploits duality and the equivalence of separation and optimization in a novel way. Further, we rule out an additive PTAS assuming planted clique hardness, which states that no polynomial time algorithm can recover a planted clique from an Erdős-Rényi random graph. Complementing these, we obtain a PTAS for a structured class of zero-sum games (where obtaining an FPTAS is still NP-hard) when the payoff matrices obey a Lipschitz condition. Previous results ruled out an FPTAS assuming planted-clique hardness, and a PTAS only for implicit games with quasi-polynomial-size strategy sets. For Bayesian network routing games, wherein the principal seeks to minimize the average latency of the Nash flow, we show that it is NP-hard to obtain a (multiplicative) $(4/3 - ε)$-approximation, even for linear latency functions. This is the optimal inapproximability result for linear latencies, since we show that full revelation achieves a $(4/3)$-approximation for linear latencies.
Current Injection Attack against the KLJN Secure Key Exchange
Venue: arXiv cs.CR 2016
Year: 2016

The Kirchhoff-law-Johnson-noise (KLJN) scheme is a statistical/physical secure key exchange system based on the laws of classical statistical physics to provide unconditional security. We used the LTSPICE industrial cable and circuit simulator to emulate one of the major active (invasive) attacks, the current injection attack, against the ideal and a practical KLJN system, respectively. We show that two security enhancement techniques, namely, the instantaneous voltage/current comparison method, and a simple privacy amplification scheme, independently and effectively eliminate the information leak and successfully preserve the system's unconditional security.
Secure Estimation based Kalman Filter for Cyber-Physical Systems against Adversarial Attacks
Venue: arXiv cs.SY 2016
Year: 2016

Cyber-physical systems are found in many applications such as power networks, manufacturing processes, and air and ground transportation systems. Maintaining security of these systems under cyber attacks is an important and challenging task, since these attacks can be erratic and thus difficult to model. Secure estimation problems study how to estimate the true system states when measurements are corrupted and/or control inputs are compromised by attackers. The authors in [1] proposed a secure estimation method when the set of attacked nodes (sensors, controllers) is fixed. In this paper, we extend these results to scenarios in which the set of attacked nodes can change over time. We formulate this secure estimation problem into the classical error correction problem [2] and we show that accurate decoding can be guaranteed under a certain condition. Furthermore, we propose a combined secure estimation method with our proposed secure estimator and the Kalman Filter for improved practical performance. Finally, we demonstrate the performance of our method through simulations of two scenarios where an unmanned aerial vehicle is under adversarial attack.
The Power of Depth for Feedforward Neural Networks
Venue: arXiv cs.LG 2016
Year: 2016

We show that there is a simple (approximately radial) function on $\reals^d$, expressible by a small 3-layer feedforward neural networks, which cannot be approximated by any 2-layer network, to more than a certain constant accuracy, unless its width is exponential in the dimension. The result holds for virtually all known activation functions, including rectified linear units, sigmoids and thresholds, and formally demonstrates that depth -- even if increased by 1 -- can be exponentially more valuable than width for standard feedforward neural networks. Moreover, compared to related results in the context of Boolean functions, our result requires fewer assumptions, and the proof techniques and construction are very different.
QoS Guaranteed Energy Minimization Over Two-Way Relaying Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this work, we consider a typical three-node, two-way relaying network (TWRN) over fading channels. The aim is to minimize the entire system energy usage for a TWRN in the long run, while satisfying the required average symmetric exchange rate between the two source nodes. To this end, the energy usage of the physical-layer network coding (PNC) or the superposition coding based digital network coding (SPC-DNC) is analyzed. The rule on selection of both strategies is then derived by comparison. Based on the observed rule, we then design a scheme by switching between PNC and SPC-DNC for each channel realization. The associated optimization problem, through PNC/DNC switching,as well as power allocation on the uplink and the downlink for each channel realization is formulated and solved via an iterative algorithm. It is demonstrated that this switching scheme outperforms the schemes solely employing PNC or SPC-DNC through both theoretical analysis and simulations.
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework
Venue: arXiv cs.LG 2016
Year: 2016

Despite the importance of sparsity in many large-scale applications, there are few methods for distributed optimization of sparsity-inducing objectives. In this paper, we present a communication-efficient framework for L1-regularized optimization in the distributed environment. By viewing classical objectives in a more general primal-dual setting, we develop a new class of methods that can be efficiently distributed and applied to common sparsity-inducing models, such as Lasso, sparse logistic regression, and elastic net-regularized problems. We provide theoretical convergence guarantees for our framework, and demonstrate its efficiency and flexibility with a thorough experimental comparison on Amazon EC2. Our proposed framework yields speedups of up to 50x as compared to current state-of-the-art methods for distributed L1-regularized optimization.