OpenRaiser/Intern-Atlas huggingface dataset:
Mixing Metaphors: Actors as Channels and Channels as Actors (Extended Version)
Venue: arXiv cs.PL 2017
Year: 2017

Channel- and actor-based programming languages are both used in practice, but the two are often confused. Languages such as Go provide anonymous processes which communicate using buffers or rendezvous points---known as channels---while languages such as Erlang provide addressable processes---known as actors---each with a single incoming message queue. The lack of a common representation makes it difficult to reason about translations that exist in the folklore. We define a calculus $λ_{\textrm{ch}}$ for typed asynchronous channels, and a calculus $λ_{\textrm{act}}$ for typed actors. We define translations from $λ_{\textrm{act}}$ into $λ_{\textrm{ch}}$ and $λ_{\textrm{ch}}$ into $λ_{\textrm{act}}$ and prove that both are type- and semantics-preserving. We show that our approach accounts for synchronisation and selective receive in actor systems and discuss future extensions to support guarded choice and behavioural types.
Tracking Words in Chinese Poetry of Tang and Song Dynasties with the China Biographical Database
Venue: arXiv cs.CL 2017
Year: 2017

Large-scale comparisons between the poetry of Tang and Song dynasties shed light on how words, collocations, and expressions were used and shared among the poets. That some words were used only in the Tang poetry and some only in the Song poetry could lead to interesting research in linguistics. That the most frequent colors are different in the Tang and Song poetry provides a trace of the changing social circumstances in the dynasties. Results of the current work link to research topics of lexicography, semantics, and social transitions. We discuss our findings and present our algorithms for efficient comparisons among the poems, which are crucial for completing billion times of comparisons within acceptable time.
Nazr-CNN: Fine-Grained Classification of UAV Imagery for Damage Assessment
Venue: arXiv cs.CV 2017
Year: 2017

We propose Nazr-CNN1, a deep learning pipeline for object detection and fine-grained classification in images acquired from Unmanned Aerial Vehicles (UAVs) for damage assessment and monitoring. Nazr-CNN consists of two components. The function of the first component is to localize objects (e.g. houses or infrastructure) in an image by carrying out a pixel-level classification. In the second component, a hidden layer of a Convolutional Neural Network (CNN) is used to encode Fisher Vectors (FV) of the segments generated from the first component in order to help discriminate between different levels of damage. To showcase our approach we use data from UAVs that were deployed to assess the level of damage in the aftermath of a devastating cyclone that hit the island of Vanuatu in 2015. The collected images were labeled by a crowdsourcing effort and the labeling categories consisted of fine-grained levels of damage to built structures. Since our data set is relatively small, a pre- trained network for pixel-level classification and FV encoding was used. Nazr-CNN attains promising results both for object detection and damage assessment suggesting that the integrated pipeline is robust in the face of small data sets and labeling errors by annotators. While the focus of Nazr-CNN is on assessment of UAV images in a post-disaster scenario, our solution is general and can be applied in many diverse settings. We show one such case of transfer learning to assess the level of damage in aerial images collected after a typhoon in Philippines.
On Storage Allocation in Cache-Enabled Interference Channels with Mixed CSIT
Venue: arXiv cs.IT 2017
Year: 2017

Recently, it has been shown that in a cache-enabled interference channel, the storage at the transmit and receive sides are of equal value in terms of Degrees of Freedom (DoF). This is derived by assuming full Channel State Information at the Transmitter (CSIT). In this paper, we consider a more practical scenario, where a training/feedback phase should exist for obtaining CSIT, during which instantaneous channel state is not known to the transmitters. This results in a combination of delayed and current CSIT availability, called mixed CSIT. In this setup, we derive DoF of a cache-enabled interference channel with mixed CSIT, which depends on the memory available at transmit and receive sides as well as the training/feedback phase duration. In contrast to the case of having full CSIT, we prove that, in our setup, the storage at the receive side is more valuable than the one at the transmit side. This is due to the fact that cooperation opportunities granted by transmitters' caches are strongly based on instantaneous CSIT availability. However, multi-casting opportunities provided by receivers' caches are robust to such imperfection.
Multiple Right-Hand Side Techniques in Semi-Explicit Time Integration Methods for Transient Eddy Current Problems
Venue: arXiv cs.CE 2017
Year: 2017

The spatially discretized magnetic vector potential formulation of magnetoquasistatic field problems is transformed from an infinitely stiff differential algebraic equation system into a finitely stiff ordinary differential equation (ODE) system by application of a generalized Schur complement for nonconducting parts. The ODE can be integrated in time using explicit time integration schemes, e.g. the explicit Euler method. This requires the repeated evaluation of a pseudo-inverse of the discrete curl-curl matrix in nonconducting material by the preconditioned conjugate gradient (PCG) method which forms a multiple right-hand side problem. The subspace projection extrapolation method and proper orthogonal decomposition are compared for the computation of suitable start vectors in each time step for the PCG method which reduce the number of iterations and the overall computational costs.
Fine-Grained Complexity and Conditional Hardness for Sparse Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We consider the fine-grained complexity of sparse graph problems that currently have $\tilde{O}(mn)$ time algorithms, where m is the number of edges and n is the number of vertices in the input graph. This class includes several important path problems on both directed and undirected graphs, including APSP, MWC (minimum weight cycle), and Eccentricities, which is the problem of computing, for each vertex in the graph, the length of a longest shortest path starting at that vertex. We introduce the notion of a sparse reduction which preserves the sparsity of graphs, and we present near linear-time sparse reductions between various pairs of graph problems in the $\tilde{O}(mn)$ class. Surprisingly, very few of the known nontrivial reductions between problems in the $\tilde{O}(mn)$ class are sparse reductions. In the directed case, our results give a partial order on a large collection of problems in the $\tilde{O}(mn)$ class (along with some equivalences). In the undirected case we give two nontrivial sparse reductions: from MWC to APSP, and from unweighted ANSC (all nodes shortest cycles) to APSP. The latter reduction also gives an improved algorithm for ANSC (for dense graphs). We propose the MWC Conjecture, a new conditional hardness conjecture that the weight of a minimum weight cycle in a directed graph cannot be computed in time polynomially smaller than mn. Our sparse reductions for directed path problems in the $\tilde{O}(mn)$ class establish that several problems in this class, including 2-SiSP (second simple shortest path), Radius, and Eccentricities, are MWCC hard. We also identify Eccentricities as a key problem in the $\tilde{O}(mn)$ class which is simultaneously MWCC-hard, SETH-hard and k-DSH-hard, where SETH is the Strong Exponential Time Hypothesis, and k-DSH is the hypothesis that a dominating set of size k cannot be computed in time polynomially smaller than n^k.
A Deep Learning Approach for Joint Video Frame and Reward Prediction in Atari Games
Venue: arXiv cs.AI 2017
Year: 2017

Reinforcement learning is concerned with identifying reward-maximizing behaviour policies in environments that are initially unknown. State-of-the-art reinforcement learning approaches, such as deep Q-networks, are model-free and learn to act effectively across a wide range of environments such as Atari games, but require huge amounts of data. Model-based techniques are more data-efficient, but need to acquire explicit knowledge about the environment. In this paper, we take a step towards using model-based techniques in environments with a high-dimensional visual state space by demonstrating that it is possible to learn system dynamics and the reward structure jointly. Our contribution is to extend a recently developed deep neural network for video frame prediction in Atari games to enable reward prediction as well. To this end, we phrase a joint optimization problem for minimizing both video frame and reward reconstruction loss, and adapt network parameters accordingly. Empirical evaluations on five Atari games demonstrate accurate cumulative reward prediction of up to 200 frames. We consider these results as opening up important directions for model-based reinforcement learning in complex, initially unknown environments.
Exploiting Web Images for Dataset Construction: A Domain Robust Approach
Venue: arXiv cs.CV 2017
Year: 2017

Labelled image datasets have played a critical role in high-level image understanding. However, the process of manual labelling is both time-consuming and labor intensive. To reduce the cost of manual labelling, there has been increased research interest in automatically constructing image datasets by exploiting web images. Datasets constructed by existing methods tend to have a weak domain adaptation ability, which is known as the "dataset bias problem". To address this issue, we present a novel image dataset construction framework that can be generalized well to unseen target domains. Specifically, the given queries are first expanded by searching the Google Books Ngrams Corpus to obtain a rich semantic description, from which the visually non-salient and less relevant expansions are filtered out. By treating each selected expansion as a "bag" and the retrieved images as "instances", image selection can be formulated as a multi-instance learning problem with constrained positive bags. We propose to solve the employed problems by the cutting-plane and concave-convex procedure (CCCP) algorithm. By using this approach, images from different distributions can be kept while noisy images are filtered out. To verify the effectiveness of our proposed approach, we build an image dataset with 20 categories. Extensive experiments on image classification, cross-dataset generalization, diversity comparison and object detection demonstrate the domain robustness of our dataset.
Comparing entropy rates on finite and infinite rooted trees
Venue: arXiv cs.IT 2017
Year: 2017

We consider stochastic processes with (or without) memory whose evolution is encoded by a finite or infinite rooted tree. The main goal is to compare the entropy rates of a given base process and a second one, to be considered as a perturbation of the former. The processes are described by probability measures on the boundary of the given tree, and by corresponding forward transition probabilities at the inner nodes. The comparison is in terms of Kullback-Leibler divergence. We elaborate and extend ideas and results of Böcherer and Amjad. Our extensions involve length functions on the edges of the tree as well as nodes with countably many successors. In particular, in the last part, we consider trees with infinite geodesic rays and random perturbations of a given process.
Cryptanalysis of an Identity-Based Authenticated Key Exchange Protocol
Venue: arXiv cs.CR 2017
Year: 2017

Authenticated Key Exchange (AKE) protocols represent an important cryptographic mechanism that enables several parties to communicate securely over an open network. Elashry, Mu and Susilo proposed in 2015 an Identity Based Authenticated Key Exchange (IBAKE) protocol where different parties establish secure communication by means of their public identities. The authors also introduced a new security notion for IBAKE protocols called resiliency, that is, if a shared secret between a group of parties is compromised or leaked, they can generate another completely new shared secret without the need to set up a new key exchange session. They then proved that their IBAKE protocol satisfies this security notion. We analyze the security of their protocol and prove that it has a major security flaw which renders it insecure against an impersonation attack. We also disprove the resiliency property of their scheme by proposing an attack where an adversary can compute any share secret key if just one secret bit is leaked.
Tracking Control of Fully-actuated Mechanical port-Hamiltonian Systems using Sliding Manifolds and Contraction
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a novel trajectory tracking controller for fully-actuated mechanical port-Hamiltonian (pH) systems, which is based on recent advances in contraction-based control theory. Our proposed controller renders a desired sliding manifold (where the reference trajectory lies) attractive by making the corresponding error system partially contracting. Finally, we present numerical simulation results where a SCARA robot is commanded by our proposed tracking control law.
A Robust Force Control Approach for Underwater Vehicle Manipulator Systems
Venue: arXiv cs.RO 2017
Year: 2017

In various interaction tasks using Underwater Vehicle Manipulator Systems (UVMSs) (e.g. sampling of the sea organisms, underwater welding), important factors such as: i) uncertainties and complexity of UVMS dynamic model ii) external disturbances (e.g. sea currents and waves) iii) imperfection and noises of measuring sensors iv) steady state performance as well as v) inferior overshoot of interaction force error, should be addressed during the force control design. Motivated by the above factors, this paper presents a model-free control protocol for force controlling of an Underwater Vehicle Manipulator System which is in contact with a compliant environment, without incorporating any knowledge of the UVMS's dynamic model, exogenous disturbances and sensor's noise model. Moreover, the transient and steady state response as well as reduction of overshooting force error are solely determined by certain designer-specified performance functions and are fully decoupled by the UVMS's dynamic model, the control gain selection, as well as the initial conditions. Finally, a simulation study clarifies the proposed method and verifies its efficiency.
Sampling Random Spanning Trees Faster than Matrix Multiplication
Venue: arXiv cs.DS 2017
Year: 2017

We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in $\tilde{O}(n^{4/3}m^{1/2}+n^{2})$ time (The $\tilde{O}(\cdot)$ notation hides $\operatorname{polylog}(n)$ factors). The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, $O(n^ω)$. For the special case of unweighted graphs, this improves upon the best previously known running time of $\tilde{O}(\min\{n^ω,m\sqrt{n},m^{4/3}\})$ for $m \gg n^{5/3}$ (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute $ε$-approximate effective resistances for a set $S$ of vertex pairs via approximate Schur complements in $\tilde{O}(m+(n + |S|)ε^{-2})$ time, without using the Johnson-Lindenstrauss lemma which requires $\tilde{O}( \min\{(m + |S|)ε^{-2}, m+nε^{-4} +|S|ε^{-2}\})$ time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.
Scene Labeling using Gated Recurrent Units with Explicit Long Range Conditioning
Venue: arXiv cs.CV 2017
Year: 2017

Recurrent neural network (RNN), as a powerful contextual dependency modeling framework, has been widely applied to scene labeling problems. However, this work shows that directly applying traditional RNN architectures, which unfolds a 2D lattice grid into a sequence, is not sufficient to model structure dependencies in images due to the "impact vanishing" problem. First, we give an empirical analysis about the "impact vanishing" problem. Then, a new RNN unit named Recurrent Neural Network with explicit long range conditioning (RNN-ELC) is designed to alleviate this problem. A novel neural network architecture is built for scene labeling tasks where one of the variants of the new RNN unit, Gated Recurrent Unit with Explicit Long-range Conditioning (GRU-ELC), is used to model multi scale contextual dependencies in images. We validate the use of GRU-ELC units with state-of-the-art performance on three standard scene labeling datasets. Comprehensive experiments demonstrate that the new GRU-ELC unit benefits scene labeling problem a lot as it can encode longer contextual dependencies in images more effectively than traditional RNN units.
Sparse Phase Retrieval via Truncated Amplitude Flow
Venue: arXiv cs.IT 2017
Year: 2017

This paper develops a novel algorithm, termed \emph{SPARse Truncated Amplitude flow} (SPARTA), to reconstruct a sparse signal from a small number of magnitude-only measurements. It deals with what is also known as sparse phase retrieval (PR), which is \emph{NP-hard} in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitude-based nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically well-justified rule, and subsequently, a sparse orthogonality-promoting initialization is obtained via power iterations restricted on the support; and, in the second stage, the initialization is successively refined by means of hard thresholding based gradient-type iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any $n$-dimensional $k$-sparse ($k\ll n$) signal $\bm{x}$ with minimum (in modulus) nonzero entries on the order of $(1/\sqrt{k})\|\bm{x}\|_2$, SPARTA recovers the signal exactly (up to a global unimodular constant) from about $k^2\log n$ random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of $k^2n\log n$ with total runtime proportional to the time required to read the data, which improves upon the state-of-the-art by at least a factor of $k$. Finally, SPARTA is robust against additive noise of bounded support. Extensive numerical tests corroborate markedly improved recovery performance and speedups of SPARTA relative to existing alternatives.
A Tight Rate Bound and a Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
Venue: arXiv cs.IT 2017
Year: 2017

An $[n,k]$ code $\mathcal{C}$ is said to be locally recoverable in the presence of a single erasure, and with locality parameter $r$, if each of the $n$ code symbols of $\mathcal{C}$ can be recovered by accessing at most $r$ other code symbols. An $[n,k]$ code is said to be a locally recoverable code with sequential recovery from $t$ erasures, if for any set of $s \leq t$ erasures, there is an $s$-step sequential recovery process, in which at each step, a single erased symbol is recovered by accessing at most $r$ other code symbols. This is equivalent to the requirement that for any set of $s \leq t$ erasures, the dual code contain a codeword whose support contains the coordinate of precisely one of the $s$ erased symbols. In this paper, a tight upper bound on the rate of such a code, for any value of number of erasures $t$ and any value $r \geq 3$, of the locality parameter is derived. This bound proves an earlier conjecture due to Song, Cai and Yuen. While the bound is valid irrespective of the field over which the code is defined, a matching construction of {\em binary} codes that are rate-optimal is also provided, again for any value of $t$ and any value $r\geq3$.
Multi-hop Communication in the Uplink for LPWANs
Venue: arXiv cs.NI 2017
Year: 2017

Low-Power Wide Area Networks (LPWANs) have arisen as a promising communication technology for supporting Internet of Things (IoT) services due to their low power operation, wide coverage range, low cost and scalability. However, most LPWAN solutions like SIGFOX or LoRaWAN rely on star topology networks, where stations (STAs) transmit directly to the gateway (GW), which often leads to rapid battery depletion in STAs located far from it. In this work, we analyze the impact on LPWANs energy consumption of multi-hop communication in the uplink, allowing STAs to transmit data packets in lower power levels and higher data rates to closer parent STAs, reducing their energy consumption consequently. To that aim, we introduce the Distance-Ring Exponential Stations Generator (DRESG) framework, designed to evaluate the performance of the so-called optimal-hop routing model, which establishes optimal routing connections in terms of energy efficiency, aiming to balance the consumption among all the STAs in the network. Results show that enabling such multi-hop connections entails higher network lifetimes, reducing significantly the bottleneck consumption in LPWANs with up to thousands of STAs. These results lead to foresee multi-hop communication in the uplink as a promising routing alternative for extending the lifetime of LPWAN deployments.
Measuring Impact of Adaptive and Cooperative Adaptive Cruise Control on Throughput of Signalized Intersections
Venue: arXiv cs.SY 2017
Year: 2017

To properly assess the impact of (cooperative) adaptive cruise control ACC (CACC), one has to model vehicle dynamics. First of all, one has to choose the car following model, as it determines the vehicle flow as vehicles accelerate from standstill or decelerate because of the obstacle ahead. The other factor significantly affecting the intersection throughput is the maximal vehicle acceleration rate. In this paper, we analyze three car following behaviors: Gipps model, Improved Intelligent Driver Model (IIDM) and Helly model. Gipps model exhibits rather aggressive acceleration behavior. If used for the intersection throughput estimation, this model would lead to overly optimistic results. Helly model is convenient to analyze due to its linear nature, but its deceleration behavior in the presence of obstacles ahead is unrealistically abrupt. Showing the most realistic acceleration and deceleration behavior of the three models, IIDM is suited for ACC/CACC impact evaluation better than the other two. We discuss the influence of the maximal vehicle acceleration rate and presence of different portions of ACC/CACC vehicles on intersection throughput in the context of the three car following models. The analysis is done for two cases: (1) free road downstream of the intersection; and (2) red light at some distance downstream of the intersection. Finally, we introduce the platoon model and evaluate ACC and CACC with platooning in terms of travel time ad network throughput using SUMO simulation of the 4-mile stretch of Colorado Boulevard / Huntington Drive arterial with 13 signalized intersections in Arcadia, Southern California.