OpenRaiser/Intern-Atlas huggingface dataset:
The (1+$λ$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
Venue: arXiv cs.NE 2018
Year: 2018

We propose a new way to self-adjust the mutation rate in population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+λ)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+λ)$ EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(nλ/\logλ+n\log n)$. This time is asymptotically smaller than the optimization time of the classic $(1+λ)$ EA. Previous work shows that this performance is best-possible among all $λ$-parallel mutation-based unbiased black-box algorithms. This result shows that the new way of adjusting the mutation rate can find optimal dynamic parameter values on the fly. Since our adjustment mechanism is simpler than the ones previously used for adjusting the mutation rate and does not have parameters itself, we are optimistic that it will find other applications.
Mitigating Interference in Content Delivery Networks by Spatial Signal Alignment: The Approach of Shot-Noise Ratio
Venue: arXiv cs.IT 2018
Year: 2018

Multimedia content especially videos is expected to dominate data traffic in next-generation mobile networks. Caching popular content at the network edge has emerged to be a solution for low-latency content delivery. Compared with the traditional wireless communication, content delivery has a key characteristic that many signals coexisting in the air carry identical popular content. They, however, can interfere with each other at a receiver if their modulation-and-coding (MAC) schemes are adapted to individual channels following the classic approach. To address this issue, we present a novel idea of content adaptive MAC (CAMAC) where adapting MAC schemes to content ensures that all signals carry identical content are encoded using an identical MAC scheme, achieving spatial MAC alignment. Consequently, interference can be harnessed as signals, to improve the reliability of wireless delivery. In the remaining part of the paper, we focus on quantifying the gain CAMAC can bring to a content-delivery network using a stochastic-geometry model. Specifically, content helpers are distributed as a Poisson point process, each of which transmits a file from a content database based on a given popularity distribution. It is discovered that the successful content-delivery probability is closely related to the distribution of the ratio of two independent shot noise processes, named a shot-noise ratio. The distribution itself is an open mathematical problem that we tackle in this work. Using stable-distribution theory and tools from stochastic geometry, the distribution function is derived in closed form. Extending the result in the context of content-delivery networks with CAMAC yields the content-delivery probability in different closed forms. In addition, the gain in the probability due to CAMAC is shown to grow with the level of skewness in the content popularity distribution.
DualGAN: Unsupervised Dual Learning for Image-to-Image Translation
Venue: arXiv cs.CV 2018
Year: 2018

Conditional Generative Adversarial Networks (GANs) for cross-domain image-to-image translation have made much progress recently. Depending on the task complexity, thousands to millions of labeled image pairs are needed to train a conditional GAN. However, human labeling is expensive, even impractical, and large quantities of data may not always be available. Inspired by dual learning from natural language translation, we develop a novel dual-GAN mechanism, which enables image translators to be trained from two sets of unlabeled images from two domains. In our architecture, the primal GAN learns to translate images from domain U to those in domain V, while the dual GAN learns to invert the task. The closed loop made by the primal and dual tasks allows images from either domain to be translated and then reconstructed. Hence a loss function that accounts for the reconstruction error of images can be used to train the translators. Experiments on multiple image translation tasks with unlabeled data show considerable performance gain of DualGAN over a single GAN. For some tasks, DualGAN can even achieve comparable or slightly better results than conditional GAN trained on fully labeled data.
Learning Two-Branch Neural Networks for Image-Text Matching Tasks
Venue: arXiv cs.CV 2018
Year: 2018

Image-language matching tasks have recently attracted a lot of attention in the computer vision field. These tasks include image-sentence matching, i.e., given an image query, retrieving relevant sentences and vice versa, and region-phrase matching or visual grounding, i.e., matching a phrase to relevant regions. This paper investigates two-branch neural networks for learning the similarity between these two data modalities. We propose two network structures that produce different output representations. The first one, referred to as an embedding network, learns an explicit shared latent embedding space with a maximum-margin ranking loss and novel neighborhood constraints. Compared to standard triplet sampling, we perform improved neighborhood sampling that takes neighborhood information into consideration while constructing mini-batches. The second network structure, referred to as a similarity network, fuses the two branches via element-wise product and is trained with regression loss to directly predict a similarity score. Extensive experiments show that our networks achieve high accuracies for phrase localization on the Flickr30K Entities dataset and for bi-directional image-sentence retrieval on Flickr30K and MSCOCO datasets.
CASP Solutions for Planning in Hybrid Domains
Venue: arXiv cs.AI 2018
Year: 2018

CASP is an extension of ASP that allows for numerical constraints to be added in the rules. PDDL+ is an extension of the PDDL standard language of automated planning for modeling mixed discrete-continuous dynamics. In this paper, we present CASP solutions for dealing with PDDL+ problems, i.e., encoding from PDDL+ to CASP, and extensions to the algorithm of the EZCSP CASP solver in order to solve CASP programs arising from PDDL+ domains. An experimental analysis, performed on well-known linear and non-linear variants of PDDL+ domains, involving various configurations of the EZCSP solver, other CASP solvers, and PDDL+ planners, shows the viability of our solution.
On Plane Constrained Bounded-Degree Spanners
Venue: arXiv cs.CG 2018
Year: 2018

Let $P$ be a finite set of points in the plane and $S$ a set of non-crossing line segments with endpoints in $P$. The visibility graph of $P$ with respect to $S$, denoted $Vis(P,S)$, has vertex set $P$ and an edge for each pair of vertices $u,v$ in $P$ for which no line segment of $S$ properly intersects $uv$. We show that the constrained half-$θ_6$-graph (which is identical to the constrained Delaunay graph whose empty visible region is an equilateral triangle) is a plane 2-spanner of $Vis(P,S)$. We then show how to construct a plane 6-spanner of $Vis(P,S)$ with maximum degree $6+c$, where $c$ is the maximum number of segments of $S$ incident to a vertex.
Gbps User Rates Using mmWave Relayed Backhaul with High Gain Antennas
Venue: arXiv cs.IT 2018
Year: 2018

Delivering Gbps high user rate over long distances (around 1 km) is challenging, and the abundant spectrum available in millimeter wave band cannot solve the challenge by its own due to the severe path loss and other limitations. Since it is economically challenging to deploy wired backhaul every few hundred meters, relays (e.g., wireless access points) have been proposed to extend the coverage of a base station which has wired connection to the core network. These relays, deployed every few hundred meters, serve the users in their vicinity and are backhauled to the base station through wireless connections. In this work, the wireless relayed backhaul design has been formulated as a topology-bandwidth-power joint optimization problem, and the influence of path loss, angular spread, array size, and RF power limitation on the user rate has been evaluated. It has been shown that for a linear network deployed along the street at 28 GHz, when high joint directional gain (50 dBi) is available, 1 Gbps user rate within cell range of 1 km can be delivered using 1.5 GHz of bandwidth (using single polarization antennas). The user rates drop precipitously when joint directional gain is reduced, or when the path loss is much more severe. When the number of RF chains is limited, the benefit of larger arrays will eventually be surpassed by the increased channel estimation penalty as the effective beamforming gain saturates owing to the channel angular spread.
An Empirical Analysis of Traceability in the Monero Blockchain
Venue: arXiv cs.CR 2018
Year: 2018

Monero is a privacy-centric cryptocurrency that allows users to obscure their transactions by including chaff coins, called "mixins," along with the actual coins they spend. In this paper, we empirically evaluate two weaknesses in Monero's mixin sampling strategy. First, about 62% of transaction inputs with one or more mixins are vulnerable to "chain-reaction" analysis -- that is, the real input can be deduced by elimination. Second, Monero mixins are sampled in such a way that they can be easily distinguished from the real coins by their age distribution; in short, the real input is usually the "newest" input. We estimate that this heuristic can be used to guess the real input with 80% accuracy over all transactions with 1 or more mixins. Next, we turn to the Monero ecosystem and study the importance of mining pools and the former anonymous marketplace AlphaBay on the transaction volume. We find that after removing mining pool activity, there remains a large amount of potentially privacy-sensitive transactions that are affected by these weaknesses. We propose and evaluate two countermeasures that can improve the privacy of future transactions.
Maximal Unbordered Factors of Random Strings
Venue: arXiv cs.DS 2018
Year: 2018

A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border other than itself. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length $n$ from a fixed non-unary alphabet uniformly at random, then the expected maximum length of its unbordered factors is $n - O(1)$. We confirm this conjecture by proving that the expected value is, in fact, ${n - Θ(σ^{-1})}$, where $σ$ is the size of the alphabet. This immediately implies that we can find such a maximal unbordered factor in linear time on average. However, we go further and show that the optimum average-case running time is in $Ω(\sqrt{n}) \cap O (\sqrt{n \log_σn})$ due to analogous bounds by Czumaj and Gąsieniec [CPM 2000] for the problem of computing the shortest period of a uniformly random string.
Does robustness imply tractability? A lower bound for planted clique in the semi-random model
Venue: arXiv cs.CC 2018
Year: 2018

We consider a robust analog of the planted clique problem. In this analog, a set $S$ of vertices is chosen and all edges in $S$ are included; then, edges between $S$ and the rest of the graph are included with probability $\frac{1}{2}$, while edges not touching $S$ are allowed to vary arbitrarily. For this semi-random model, we show that the information-theoretic threshold for recovery is $\tildeΘ(\sqrt{n})$, in sharp contrast to the classical information-theoretic threshold of $Θ(\log(n))$. This matches the conjectured computational threshold for the classical planted clique problem, and thus raises the intriguing possibility that, once we require robustness, there is no computational-statistical gap for planted clique. Our lower bound involves establishing a result regarding the KL divergence of a family of perturbed Bernoulli distributions, which may be of independent interest.
A Large Self-Annotated Corpus for Sarcasm
Venue: arXiv cs.CL 2018
Year: 2018

We introduce the Self-Annotated Reddit Corpus (SARC), a large corpus for sarcasm research and for training and evaluating systems for sarcasm detection. The corpus has 1.3 million sarcastic statements -- 10 times more than any previous dataset -- and many times more instances of non-sarcastic statements, allowing for learning in both balanced and unbalanced label regimes. Each statement is furthermore self-annotated -- sarcasm is labeled by the author, not an independent annotator -- and provided with user, topic, and conversation context. We evaluate the corpus for accuracy, construct benchmarks for sarcasm detection, and evaluate baseline methods.
Extension of Technology Acceptance Model by using System Usability Scale to assess behavioral intention to use e-learning
Venue: arXiv cs.HC 2018
Year: 2018

This study examines the acceptance of technology and behavioral intention to use learning management systems (LMS). In specific, the aim of this research is to examine whether students ultimately accept and use educational learning systems such as e-class and the impact of behavioral intention on their decision to use them. An extended version of technology acceptance model has been proposed and used by employing the System Usability Scale to measure perceived ease of use. 345 university students participated in the study and the data analysis was based on partial least squares method. The results were confirmed in most of the research hypotheses. In particular, social norm, system access and self-efficacy significantly affect behavioral intention to use. As a result, it is suggested that e-learning developers and stakeholders should focus on these factors to increase acceptance and effectiveness of learning management systems.
Hazard Analysis and Risk Assessment for an Automated Unmanned Protective Vehicle
Venue: arXiv cs.RO 2018
Year: 2018

For future application of automated vehicles in public traffic, ensuring functional safety is essential. In this context, a hazard analysis and risk assessment is an important input for designing functionally vehicle automation systems. In this contribution, we present a detailed hazard analysis and risk assessment (HARA) according to the ISO 26262 standard for a specific Level 4 application, namely an unmanned protective vehicle operated without human supervision for motorway hard shoulder roadworks.
Equivalence Between Policy Gradients and Soft Q-Learning
Venue: arXiv cs.LG 2018
Year: 2018

Two of the leading approaches for model-free reinforcement learning are policy gradient methods and $Q$-learning methods. $Q$-learning methods can be effective and sample-efficient when they work, however, it is not well-understood why they work, since empirically, the $Q$-values they estimate are very inaccurate. A partial explanation may be that $Q$-learning methods are secretly implementing policy gradient updates: we show that there is a precise equivalence between $Q$-learning and policy gradient methods in the setting of entropy-regularized reinforcement learning, that "soft" (entropy-regularized) $Q$-learning is exactly equivalent to a policy gradient method. We also point out a connection between $Q$-learning methods and natural policy gradient methods. Experimentally, we explore the entropy-regularized versions of $Q$-learning and policy gradients, and we find them to perform as well as (or slightly better than) the standard variants on the Atari benchmark. We also show that the equivalence holds in practical settings by constructing a $Q$-learning method that closely matches the learning dynamics of A3C without using a target network or $ε$-greedy exploration schedule.
The Ising Partition Function: Zeros and Deterministic Approximation
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters $β$ (the interaction) and $λ$ (the external field), except for the case $\vertλ\vert=1$ (the "zero-field" case). A randomized algorithm (FPRAS) for all graphs, and all $β,λ$, has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the "decay of correlations" property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.
Low-Dimensional Spatial Embedding Method for Shape Uncertainty Quantification in Acoustic Scattering
Venue: arXiv cs.CE 2018
Year: 2018

This paper introduces a novel boundary integral approach of shape uncertainty quantification for the Helmholtz scattering problem in the framework of the so-called parametric method. The key idea is to construct an integration grid whose associated weight function encompasses the irregularities and nonsmoothness imposed by the random boundary. Thus, the solution can be evaluated accurately with relatively low number of grid points. The integration grid is obtained by employing a low-dimensional spatial embedding using the coarea formula. The proposed method can handle large variation as well as non-smoothness of the random boundary. For the ease of presentation the theory is restricted to star-shaped obstacles in low-dimensional setting. Higher spatial and parametric dimensional cases are discussed, though, not extensively explored in the current study.
Multi-View Dynamic Facial Action Unit Detection
Venue: arXiv cs.CV 2018
Year: 2018

We propose a novel convolutional neural network approach to address the fine-grained recognition problem of multi-view dynamic facial action unit detection. We leverage recent gains in large-scale object recognition by formulating the task of predicting the presence or absence of a specific action unit in a still image of a human face as holistic classification. We then explore the design space of our approach by considering both shared and independent representations for separate action units, and also different CNN architectures for combining color and motion information. We then move to the novel setup of the FERA 2017 Challenge, in which we propose a multi-view extension of our approach that operates by first predicting the viewpoint from which the video was taken, and then evaluating an ensemble of action unit detectors that were trained for that specific viewpoint. Our approach is holistic, efficient, and modular, since new action units can be easily included in the overall system. Our approach significantly outperforms the baseline of the FERA 2017 Challenge, with an absolute improvement of 14% on the F1-metric. Additionally, it compares favorably against the winner of the FERA 2017 challenge. Code source is available at https://github.com/BCV-Uniandes/AUNets.
Uplink performance of multi-antenna cellular networks with co-operative base stations and user-centric clustering
Venue: arXiv cs.IT 2018
Year: 2018

We consider a user-centric co-operative cellular network, where base stations (BSs) close to a mobile co-operate to detect its signal using a (joint) linear minimum-mean-square-error receiver. The BSs are at arbitrary positions and mobiles are modeled as a planar Poisson Point Process (PPP). Combining stochastic geometry and infinite-random-matrix theory, we derive a simple expression for the spectral efficiency of this complex system as the number of antennas grows large. This framework is applied to BS locations from PPPs and hexagonal grids, and are validated through Monte Carlo simulations. The results reveal the influence of tangible system parameters such as mobile and base-station densities, number of antennas per BS, and number of co-operating BSs on achievable spectral efficiencies. Among other insights, we find that for a given BS density and a constraint on the total number of co-operating antennas, all co-operating antennas should be located at a single BS. On the other hand, in our asymptotic regime, for the same number of co-operating antennas, if the network is limited by the area density of antennas, then the number of co-operating BSs should be increased with fewer antennas per BS.
How compatible are our discourse annotations? Insights from mapping RST-DT and PDTB annotations
Venue: arXiv cs.CL 2018
Year: 2018

Discourse-annotated corpora are an important resource for the community, but they are often annotated according to different frameworks. This makes comparison of the annotations difficult, thereby also preventing researchers from searching the corpora in a unified way, or using all annotated data jointly to train computational systems. Several theoretical proposals have recently been made for mapping the relational labels of different frameworks to each other, but these proposals have so far not been validated against existing annotations. The two largest discourse relation annotated resources, the Penn Discourse Treebank and the Rhetorical Structure Theory Discourse Treebank, have however been annotated on the same text, allowing for a direct comparison of the annotation layers. We propose a method for automatically aligning the discourse segments, and then evaluate existing mapping proposals by comparing the empirically observed against the proposed mappings. Our analysis highlights the influence of segmentation on subsequent discourse relation labeling, and shows that while agreement between frameworks is reasonable for explicit relations, agreement on implicit relations is low. We identify several sources of systematic discrepancies between the two annotation schemes and discuss consequences of these discrepancies for future annotation and for the training of automatic discourse relation labellers.
Scalable Twin Neural Networks for Classification of Unbalanced Data
Venue: arXiv cs.LG 2018
Year: 2018

Twin Support Vector Machines (TWSVMs) have emerged an efficient alternative to Support Vector Machines (SVM) for learning from imbalanced datasets. The TWSVM learns two non-parallel classifying hyperplanes by solving a couple of smaller sized problems. However, it is unsuitable for large datasets, as it involves matrix operations. In this paper, we discuss a Twin Neural Network (Twin NN) architecture for learning from large unbalanced datasets. The Twin NN also learns an optimal feature map, allowing for better discrimination between classes. We also present an extension of this network architecture for multiclass datasets. Results presented in the paper demonstrate that the Twin NN generalizes well and scales well on large unbalanced datasets.