OpenRaiser/Intern-Atlas huggingface dataset:
Indirect-adaptive Model Predictive Control for Linear Systems with Polytopic Uncertainty
Venue: arXiv cs.SY 2015
Year: 2015

We develop an indirect-adaptive model predictive control algorithm for uncertain linear systems subject to constraints. The system is modeled as a polytopic linear parameter varying system where the convex combination vector is constant but unknown. Robust constraint satisfaction is obtained by constraints enforcing a robust control invariant. The terminal cost and set are constructed from a parameter-dependent Lyapunov function and the associated control law. The proposed design ensures robust constraint satisfaction and recursive feasibility, is input-to-state stable with respect to the parameter estimation error and it only requires the online solution of quadratic programs.
An Automata Theoretic Approach to the Zero-One Law for Regular Languages: Algorithmic and Logical Aspects
Venue: arXiv cs.FL 2015
Year: 2015

A zero-one language L is a regular language whose asymptotic probability converges to either zero or one. In this case, we say that L obeys the zero-one law. We prove that a regular language obeys the zero-one law if and only if its syntactic monoid has a zero element, by means of Eilenberg's variety theoretic approach. Our proof gives an effective automata characterisation of the zero-one law for regular languages, and it leads to a linear time algorithm for testing whether a given regular language is zero-one. In addition, we discuss the logical aspects of the zero-one law for regular languages.
Noise-Robust ASR for the third 'CHiME' Challenge Exploiting Time-Frequency Masking based Multi-Channel Speech Enhancement and Recurrent Neural Network
Venue: arXiv cs.SD 2015
Year: 2015

In this paper, the Lingban entry to the third 'CHiME' speech separation and recognition challenge is presented. A time-frequency masking based speech enhancement front-end is proposed to suppress the environmental noise utilizing multi-channel coherence and spatial cues. The state-of-the-art speech recognition techniques, namely recurrent neural network based acoustic and language modeling, state space minimum Bayes risk based discriminative acoustic modeling, and i-vector based acoustic condition modeling, are carefully integrated into the speech recognition back-end. To further improve the system performance by fully exploiting the advantages of different technologies, the final recognition results are obtained by lattice combination and rescoring. Evaluations carried out on the official dataset prove the effectiveness of the proposed systems. Comparing with the best baseline result, the proposed system obtains consistent improvements with over 57% relative word error rate reduction on the real-data test set.
Frequency Distribution of Error Messages
Venue: arXiv cs.SE 2015
Year: 2015

Which programming error messages are the most common? We investigate this question, motivated by writing error explanations for novices. We consider large data sets in Python and Java that include both syntax and run-time errors. In both data sets, after grouping essentially identical messages, the error message frequencies empirically resemble Zipf-Mandelbrot distributions. We use a maximum-likelihood approach to fit the distribution parameters. This gives one possible way to contrast languages or compilers quantitatively.
Boosting Spatial Reuse via Multiple Paths Multi-Hop Scheduling for Directional mmWave WPANs
Venue: arXiv cs.NI 2015
Year: 2015

With huge unlicensed bandwidth available in most parts of the world, millimeter wave (mmWave) communications in the 60 GHz band has been considered as one of the most promising candidates to support multi-gigabit wireless services. Due to high propagation loss of mmWave channels, beamforming is likely to become adopted as an essential technique. Consequently, transmission in 60 GHz band is inherently directional. Directivity enables concurrent transmissions (spatial reuse), which can be fully exploited to improve network capacity. In this paper, we propose a multiple paths multi-hop scheduling scheme, termed MPMH, for mmWave wireless personal area networks, where the traffic across links of low channel quality is transmitted through multiple paths of multiple hops to unleash the potential of spatial reuse. We formulate the problem of multiple paths multi-hop scheduling as a mixed integer linear program (MILP), which is generally NP-hard. To enable the implementation of the multiple paths multi-hop transmission in practice, we propose a heuristic scheme including path selection, traffic distribution, and multiple paths multi-hop scheduling to efficiently solve the formulated problem. Finally, through extensive simulations, we demonstrate MPMH achieves near-optimal network performance in terms of transmission delay and throughput, and enhances the network performance significantly compared with existing protocols.
A new class of rank-metric codes and their list decoding beyond the unique decoding radius
Venue: arXiv cs.IT 2015
Year: 2015

Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. Although the list decodability of random rank-metric codes and limits to list decodability have been completely determined, little work on efficient list decoding rank-metric codes has been done. The only known efficient list decoding of rank-metric codes $\mC$ gives decoding radius up to the Singleton bound $1-R-\Ge$ with positive rate $R$ when $ρ(\mC)$ is extremely small, i.e., $Θ(\Ge^2)$ , where $ρ(\mC)$ denotes the ratio of the number of rows over the number of columns of $\mC$ \cite[STOC2013]{Guru2013}. It is commonly believed that list decoding of rank-metric codes $\mC$ with not small constant ratio $ρ(\mC)$ is hard. The main purpose of the present paper is to explicitly construct a class of rank-metric codes $\mC$ with not small constant ratio $ρ(\mC)$ and efficiently list decode these codes with decoding radius beyond $(1-R)/2$. Our key idea is to employ two-variable polynomials $f(x,y)$, where $f$ is linearized in variable $x$ and the variable $y$ is used to "fold" the code. In other words, rows are used to correct rank errors and columns are used to "fold" the code to enlarge decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace of dimension linear in the number $n$ of columns. This "periodic" structure allows us to pre-encoding the messages to prune down the list. More precisely, we use subspace design introduced in \cite[STOC2013]{Guru2013} to get a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced in \cite[STOC2012]{Guru2012} to obtain a randomized algorithm with a smaller constant list size.
Space Codes for MIMO Optical Wireless Communications: Error Performance Criterion and Code Construction
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider a multiple-input-multiple-output optical wireless communication (MIMO-OWC) system in the presence of log-normal fading. In this scenario, a general criterion for the design of full-diversity space code (FDSC) with the maximum likelihood (ML) detector is developed. This criterion reveals that in a high signal-to-noise ratio (SNR) regime, MIMO-OWC offers both large-scale diversity gain, governing the exponential decaying of the error curve, and small-scale diversity gain, producing traditional power-law decaying. Particularly for a two by two MIMO-OWC system with unipolar pulse amplitude modulation (PAM), a closed-form solution to the design problem of a linear FDSC optimizing both diversity gains is attained by taking advantage of the available properties on the successive terms of Farey sequences in number theory as well as by developing new properties on the disjoint intervals formed by the Farey sequence terms to attack the continuous and discrete variables mixed max-min design problem. In fact, this specific design not only proves that a repetition code (RC) is the optimal linear FDSC optimizing both the diversity gains, but also uncovers a significant difference between MIMO radio frequency (RF) communications and MIMO-OWC that space dimension alone is sufficient for a full large-scale diversity achievement. Computer simulations demonstrate that FDSC substantially outperforms uncoded spatial multiplexing with the same total optical power and spectral efficiency, and the latter provides only the small-scale diversity gain.
Design Aspects of Short Range Millimeter Wave Networks: A MAC Layer Perspective
Venue: arXiv cs.IT 2015
Year: 2015

Increased density of wireless devices, ever growing demands for extremely high data rate, and spectrum scarcity at microwave bands make the millimeter wave (mmWave) frequencies an important player in future wireless networks. However, mmWave communication systems exhibit severe attenuation, blockage, deafness, and may need microwave networks for coordination and fall-back support. To compensate for high attenuation, mmWave systems exploit highly directional operation, which in turn substantially reduces the interference footprint. The significant differences between mmWave networks and legacy communication technologies challenge the classical design approaches, especially at the medium access control (MAC) layer, which has received comparatively less attention than PHY and propagation issues in the literature so far. In this paper, the MAC layer design aspects of short range mmWave networks are discussed. In particular, we explain why current mmWave standards fail to fully exploit the potential advantages of short range mmWave technology, and argue for the necessity of new collision-aware hybrid resource allocation frameworks with on-demand control messages, the advantages of a collision notification message, and the potential of multihop communication to provide reliable mmWave connections.
A Review of Feature Selection Methods Based on Mutual Information
Venue: arXiv cs.LG 2015
Year: 2015

In this work we present a review of the state of the art of information theoretic feature selection methods. The concepts of feature relevance, redundance and complementarity (synergy) are clearly defined, as well as Markov blanket. The problem of optimal feature selection is defined. A unifying theoretical framework is described, which can retrofit successful heuristic criteria, indicating the approximations made by each method. A number of open problems in the field are presented.
Sentiment Uncertainty and Spam in Twitter Streams and Its Implications for General Purpose Realtime Sentiment Analysis
Venue: arXiv cs.CL 2015
Year: 2015

State of the art benchmarks for Twitter Sentiment Analysis do not consider the fact that for more than half of the tweets from the public stream a distinct sentiment cannot be chosen. This paper provides a new perspective on Twitter Sentiment Analysis by highlighting the necessity of explicitly incorporating uncertainty. Moreover, a dataset of high quality to evaluate solutions for this new problem is introduced and made publicly available.
Folding a Tree into a Map
Venue: arXiv cs.OS 2015
Year: 2015

Analysis of the retrieval architecture of the highly influential UNIX file system (\cite{Ritchie}\cite{multicsfs}) provides insight into design methods, constraints, and possible alternatives. The basic architecture can be understood in terms of function composition and recursion by anyone with some mathematical maturity. Expertise in operating system coding or in any specialized "formal method" is not required.
Online Stochastic Linear Optimization under One-bit Feedback
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we study a special bandit setting of online stochastic linear optimization, where only one-bit of information is revealed to the learner at each round. This problem has found many applications including online advertisement and online recommendation. We assume the binary feedback is a random variable generated from the logit model, and aim to minimize the regret defined by the unknown linear function. Although the existing method for generalized linear bandit can be applied to our problem, the high computational cost makes it impractical for real-world problems. To address this challenge, we develop an efficient online learning algorithm by exploiting particular structures of the observation model. Specifically, we adopt online Newton step to estimate the unknown parameter and derive a tight confidence region based on the exponential concavity of the logistic loss. Our analysis shows that the proposed algorithm achieves a regret bound of $O(d\sqrt{T})$, which matches the optimal result of stochastic linear bandits.
A vulnerability in Google AdSense: Automatic extraction of links to ads
Venue: arXiv cs.CY 2015
Year: 2015

On the basis of the XSS (Cross Site Scripting) and Web Crawler techniques it is possible to go through the barriers of the Google Adsense advertising system by obtaining the validated links of the ads published on a website. Such method involves obtaining the source code built for the Google java applet for publishing and handling ads and for the final link retrieval. Once the links of the ads have been obtained, you can use the user sessions visiting other websites to load such links, in the background, by a simple re-direction, through a hidden iframe, so that the IP addresses clicking are different in each case.
A Mathematical Theory for Clustering in Metric Spaces
Venue: arXiv cs.LG 2015
Year: 2015

Clustering is one of the most fundamental problems in data analysis and it has been studied extensively in the literature. Though many clustering algorithms have been proposed, clustering theories that justify the use of these clustering algorithms are still unsatisfactory. In particular, one of the fundamental challenges is to address the following question: What is a cluster in a set of data points? In this paper, we make an attempt to address such a question by considering a set of data points associated with a distance measure (metric). We first propose a new cohesion measure in terms of the distance measure. Using the cohesion measure, we define a cluster as a set of points that are cohesive to themselves. For such a definition, we show there are various equivalent statements that have intuitive explanations. We then consider the second question: How do we find clusters and good partitions of clusters under such a definition? For such a question, we propose a hierarchical agglomerative algorithm and a partitional algorithm. Unlike standard hierarchical agglomerative algorithms, our hierarchical agglomerative algorithm has a specific stopping criterion and it stops with a partition of clusters. Our partitional algorithm, called the K-sets algorithm in the paper, appears to be a new iterative algorithm. Unlike the Lloyd iteration that needs two-step minimization, our K-sets algorithm only takes one-step minimization. One of the most interesting findings of our paper is the duality result between a distance measure and a cohesion measure. Such a duality result leads to a dual K-sets algorithm for clustering a set of data points with a cohesion measure. The dual K-sets algorithm converges in the same way as a sequential version of the classical kernel K-means algorithm. The key difference is that a cohesion measure does not need to be positive semi-definite.
Delay Optimal Power Aware Opportunistic Scheduling with Mutual Information Accumulation
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers optimization of power and delay in a time-varying wireless link using rateless codes. The link serves a sequence of variable-length packets. Each packet is coded and transmitted over multiple slots. Channel conditions can change from slot to slot and are unknown to the transmitter. The amount of mutual information accumulated on each slot depends on the random channel realization and the power used. The goal is to minimize average service delay subject to an average power constraint. We formulate this problem as a frame-based stochastic optimization problem and solve it via an online algorithm. We show that the subproblem within each frame is a simple integer program which can be effectively solved using a dynamic program. The optimality of this online algorithm is proved using the frame-based Lyapunov drift analysis.
Power Divider
Venue: arXiv cs.SY 2015
Year: 2015

This paper derives analytical closed-form expressions that uncover the contributions of nodal active- and reactive-power injections to the active- and reactive-power flows on transmission lines in an AC electrical network. Paying due homage to current- and voltage-divider laws that are similar in spirit, we baptize these as the power divider laws. Derived from a circuit-theoretic examination of AC power-flow expressions, the constitution of the power divider laws reflects the topology and voltage profile of the network. We demonstrate the utility of the power divider laws to the analysis of power networks by highlighting applications to transmission-network allocation, transmission-loss allocation, and identifying feasible injections while respecting line active-power flow set points.
Cultural Barriers to Software Productivity Practices at Los Alamos
Venue: arXiv cs.SE 2015
Year: 2015

In recent years, code projects in the nuclear weapons program at Los Alamos National Laboratory (LANL) have given increased attention to modern software productivity practices. We found that some of the biggest barriers to adoption of new practices were not technical but cultural. This paper describes several of the cultural differences between the physics and computer science communities at LANL.
Analysis of A Splitting Approach for the Parallel Solution of Linear Systems on GPU Cards
Venue: arXiv cs.DC 2015
Year: 2015

We discuss an approach for solving sparse or dense banded linear systems ${\bf A} {\bf x} = {\bf b}$ on a Graphics Processing Unit (GPU) card. The matrix ${\bf A} \in {\mathbb{R}}^{N \times N}$ is possibly nonsymmetric and moderately large; i.e., $10000 \leq N \leq 500000$. The ${\it split\ and\ parallelize}$ (${\tt SaP}$) approach seeks to partition the matrix ${\bf A}$ into diagonal sub-blocks ${\bf A}_i$, $i=1,\ldots,P$, which are independently factored in parallel. The solution may choose to consider or to ignore the matrices that couple the diagonal sub-blocks ${\bf A}_i$. This approach, along with the Krylov subspace-based iterative method that it preconditions, are implemented in a solver called ${\tt SaP::GPU}$, which is compared in terms of efficiency with three commonly used sparse direct solvers: ${\tt PARDISO}$, ${\tt SuperLU}$, and ${\tt MUMPS}$. ${\tt SaP::GPU}$, which runs entirely on the GPU except several stages involved in preliminary row-column permutations, is robust and compares well in terms of efficiency with the aforementioned direct solvers. In a comparison against Intel's ${\tt MKL}$, ${\tt SaP::GPU}$ also fares well when used to solve dense banded systems that are close to being diagonally dominant. ${\tt SaP::GPU}$ is publicly available and distributed as open source under a permissive BSD3 license.
Continuous set packing and near-Boolean functions
Venue: arXiv cs.DM 2015
Year: 2015

Given a family of feasible subsets of a ground set, the packing problem is to find a largest subfamily of pairwise disjoint family members. Non-approximability renders heuristics attractive viable options, while efficient methods with worst-case guarantee are a key concern in computational complexity. This work proposes a novel near-Boolean optimization method relying on a polynomial multilinear form with variables ranging each in a high-dimensional unit simplex, rather than in the unit interval as usual. The variables are the elements of the ground set, and distribute each a unit membership over those feasible subsets where they are included. The given problem is thus translated into a continuous version where the objective is to maximize a function taking values on collections of points in a unit hypercube. Maximizers are shown to always include collections of hypercube disjoint vertices, i.e. partitions of the ground set, which constitute feasible solutions for the original discrete version of the problem. A gradient-based local search in the expanded continuous domain is designed. Approximations with polynomial multilinear form of bounded degree and near-Boolean games are also finally discussed.
Random-resistor-random-temperature Kirchhoff-law-Johnson-noise (RRRT-KLJN) key exchange
Venue: arXiv cs.ET 2015
Year: 2015

We introduce two new Kirchhoff-law-Johnson-noise (KLJN) secure key distribution schemes which are generalizations of the original KLJN scheme. The first of these, the Random-Resistor (RR-) KLJN scheme, uses random resistors with values chosen from a quasi-continuum set. It is well-known since the creation of the KLJN concept that such a system could work in cryptography, because Alice and Bob can calculate the unknown resistance value from measurements, but the RR-KLJN system has not been addressed in prior publications since it was considered impractical. The reason for discussing it now is the second scheme, the Random-Resistor-Random-Temperature (RRRT-) KLJN key exchange, inspired by a recent paper of Vadai, Mingesz and Gingl, wherein security was shown to be maintained at non-zero power flow. In the RRRT-KLJN secure key exchange scheme, both the resistances and their temperatures are continuum random variables. We prove that the security of the RRRT-KLJN scheme can prevail at non-zero power flow, and thus the physical law guaranteeing security is not the Second Law of Thermodynamics but the Fluctuation-Dissipation Theorem. Alice and Bob know their own resistances and temperatures and can calculate the resistance and temperature values at the other end of the communication channel from measured voltage, current and power-flow data in the wire. However, Eve cannot determine these values because, for her, there are four unknown quantities while she can set up only three equations. The RRRT-KLJN scheme has several advantages and makes all former attacks on the KLJN scheme invalid or incomplete.
Adaptive Agent-Based SCADA System
Venue: arXiv cs.SY 2015
Year: 2015

Modern supervisory control and data acquisition (SCADA) systems comprise variety of industrial equipment such as physical control processes, logical control systems, communication networks, computers, and communication protocols. They are concerned with control and supervision of production control processes. Modern SCADA networks contain highly distributed information, control, and location. Moreover, they contain large number of heterogeneous components situated in highly changing and uncertain environments. As a result, engineering modern SCADA is a challenging issue and conventional engineering approaches are no longer suitable for them because of their increasing complexity and highly distribution. In this research, Multi-Agent Systems (MAS) are used to enable building adaptive agent-based SCADA system by modeling system components as agents in the micro level and as organizations or societies of agents in the macro level. A prototype has been implemented and evaluated within a simulation environment for demonstrating the adaptive behavior of the system-to-be, which results in continuous improvement of system performance.
Building a Virtual HPC Cluster with Auto Scaling by the Docker
Venue: arXiv cs.DC 2015
Year: 2015

Solving the software dependency issue under the HPC environment has always been a difficult task for both computing system administrators and application scientists. This work would like to tackle the issue by introducing the modern container technology, the Docker, to be specific. By integrating the auto-scaling feature of service discovery with the light-weight virtualization tool, the Docker, the construction of a virtual cluster on top of physical cluster hardware is attempted. Thus, through the isolation of computing environment, a remedy of software dependency of HPC environment is possible.