OpenRaiser/Intern-Atlas huggingface dataset:
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Venue: arXiv cs.CC 2019
Year: 2019

Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within \approx 0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within \approx 0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (\approx 0.878 for Max-Cut, and \approx 0.940 for Max-2-Sat). The hardness obtained for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem.
Attending to Emotional Narratives
Venue: arXiv cs.LG 2019
Year: 2019

Attention mechanisms in deep neural networks have achieved excellent performance on sequence-prediction tasks. Here, we show that these recently-proposed attention-based mechanisms---in particular, the Transformer with its parallelizable self-attention layers, and the Memory Fusion Network with attention across modalities and time---also generalize well to multimodal time-series emotion recognition. Using a recently-introduced dataset of emotional autobiographical narratives, we adapt and apply these two attention mechanisms to predict emotional valence over time. Our models perform extremely well, in some cases reaching a performance comparable with human raters. We end with a discussion of the implications of attention mechanisms to affective computing.
Variational Inference MPC for Bayesian Model-based Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

In recent studies on model-based reinforcement learning (MBRL), incorporating uncertainty in forward dynamics is a state-of-the-art strategy to enhance learning performance, making MBRLs competitive to cutting-edge model free methods, especially in simulated robotics tasks. Probabilistic ensembles with trajectory sampling (PETS) is a leading type of MBRL, which employs Bayesian inference to dynamics modeling and model predictive control (MPC) with stochastic optimization via the cross entropy method (CEM). In this paper, we propose a novel extension to the uncertainty-aware MBRL. Our main contributions are twofold: Firstly, we introduce a variational inference MPC, which reformulates various stochastic methods, including CEM, in a Bayesian fashion. Secondly, we propose a novel instance of the framework, called probabilistic action ensembles with trajectory sampling (PaETS). As a result, our Bayesian MBRL can involve multimodal uncertainties both in dynamics and optimal trajectories. In comparison to PETS, our method consistently improves asymptotic performance on several challenging locomotion tasks.
Unified Optimal Analysis of the (Stochastic) Gradient Method
Venue: arXiv cs.LG 2019
Year: 2019

In this note we give a simple proof for the convergence of stochastic gradient (SGD) methods on $μ$-convex functions under a (milder than standard) $L$-smoothness assumption. We show that for carefully chosen stepsizes SGD converges after $T$ iterations as $O\left( LR^2 \exp \bigl[-\fracμ{4L}T\bigr] + \frac{σ^2}{μT} \right)$ where $σ^2$ measures the variance in the stochastic noise. For deterministic gradient descent (GD) and SGD in the interpolation setting we have $σ^2 =0$ and we recover the exponential convergence rate. The bound matches with the best known iteration complexity of GD and SGD, up to constants.
On the 3-D Placement of Airborne Base Stations Using Tethered UAVs
Venue: arXiv cs.IT 2019
Year: 2019

One of the main challenges slowing the deployment of airborne base stations (BSs) using unmanned aerial vehicles (UAVs) is the limited on-board energy and flight time. One potential solution to such problem, is to provide the UAV with power supply through a tether that connects the UAV to the ground. In this paper, we study the optimal placement of tethered UAVs (TUAVs) to minimize the average path-loss between the TUAV and a receiver located on the ground. Given that the tether has a maximum length, and the launching point of the TUAV (the starting point of the tether) is placed on a rooftop, the TUAV is only allowed to hover within a specific hovering region. Beside the maximum tether length, this hovering region also depends on the heights of the buildings surrounding the rooftop, which requires the inclination angle of the tether not to be below a given minimum value, in order to avoid tangling and ensure safety. We first formulate the optimization problem for such setup and provide some useful insights on its solution. Next, we derive upper and lower bounds for the optimal values of the tether length and inclination angle. We also propose a suboptimal closed-form solution for the tether length and its inclination angle that is based on maximizing the line-of-sight probability. Finally, we derive the probability distribution of the minimum inclination angle of the tether length. We show that its mean value varies depending on the environment from 10 degrees in suburban environments to 31 degrees in high rise urban environments. Our numerical results show that the derived upper and lower bounds on the optimal values of the tether length and inclination angle lead to tight suboptimal values of the average path-loss that are only 0-3 dBs above the minimum value.
BASN -- Learning Steganography with Binary Attention Mechanism
Venue: arXiv cs.CV 2019
Year: 2019

Secret information sharing through image carrier has aroused much research attention in recent years with images' growing domination on the Internet and mobile applications. However, with the booming trend of convolutional neural networks, image steganography is facing a more significant challenge from neural-network-automated tasks. To improve the security of image steganography and minimize task result distortion, models must maintain the feature maps generated by task-specific networks being irrelative to any hidden information embedded in the carrier. This paper introduces a binary attention mechanism into image steganography to help alleviate the security issue, and in the meanwhile, increase embedding payload capacity. The experimental results show that our method has the advantage of high payload capacity with little feature map distortion and still resist detection by state-of-the-art image steganalysis algorithms.
New Competitiveness Bounds for the Shared Memory Switch
Venue: arXiv cs.NI 2019
Year: 2019

We consider one of the simplest and best known buffer management architectures: the shared memory switch with multiple output queues and uniform packets. It was one of the first models studied by competitive analysis, with the Longest Queue Drop (LQD) buffer management policy shown to be at least $\sqrt{2}$- and at most $2$-competitive; a general lower bound of $4/3$ has been proven for all deterministic online algorithms. Closing the gap between $\sqrt{2}$ and $2$ has remained an open problem in competitive analysis for more than a decade, with only marginal success in reducing the upper bound of $2$. In this work, we first present a simplified proof for the $\sqrt{2}$ lower bound for LQD and then, using a reduction to the continuous case, improve the general lower bound for all deterministic online algorithms from $\frac 43$ to $\sqrt{2}$. Then, we proceed to improve the lower bound of $\sqrt{2}$ specifically for LQD, showing that LQD is at least $1.44546086$-competitive. We are able to prove the bound by presenting an explicit construction of the optimal clairvoyant algorithm which then allows for two different ways to prove lower bounds: by direct computer simulations and by proving lower bounds via linear programming. The linear programming approach yields a lower bound for LQD of $1.4427902$ (still larger than $\sqrt{2}$).
The Ad Types Problem
Venue: arXiv cs.GT 2019
Year: 2019

The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $θ$ to slot $j$ is $v_i\cdot α^θ_j$ where $v_i$ is an advertiser-specific value and each ad type $θ$ has a discount curve $α^{(θ)}_{1} \ge α^{(θ)}_{2} \ge ... \ge 0$ over the slots that is common for ads of type $θ$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + \log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + \log n))$, and apply reserve prices in $O(n^3(k + \log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $θ_i$, the next $G_{ij}$ slots cannot show an ad of type $θ_j$. We show that the problem is hard to approximate within $k^{1- ε}$ for any $ε> 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(k\cdot n^{2k + 1})$ time.
Sublinear data structures for short Fréchet queries
Venue: arXiv cs.CG 2019
Year: 2019

We study metric data structures for curves in doubling spaces, such as trajectories of moving objects in Euclidean $\mathbb{R}^d$, where the distance between two curves is measured using the discrete Fréchet distance. We design data structures in an \emph{asymmetric} setting where the input is a curve (or a set of $n$ curves) each of complexity $m$ and the queries are with curves of complexity $k\ll m$. We show that there exist approximate data structures that are independent of the input size $N = d \cdot n \cdot m$ and we study how to maintain them dynamically if the input is given in the stream. Concretely, we study two types of data structures: (i) distance oracles, where the task is to store a compressed version of the input curve, which can be used to answer queries for the distance of a query curve to the input curve, and (ii) nearest-neighbor data structures, where the task is to preprocess a set of input curves to answer queries for the input curve closest to the query curve. In both cases we are interested in approximation. For curves embedded in Euclidean $\mathbb{R}^d$ with constant $d$, our distance oracle uses space in $\mathcal{O}((k \log(ε^{-1}) ε^{-d})^k)$ ($ε$ is the precision parameter). The oracle performs $(1+ε)$-approximate queries in time in $\mathcal{O}(k^2)$ and is deterministic. We show how to maintain this distance oracle in the stream using polylogarithmic additional memory. In the stream, we can dynamically answer distance queries to the portion of the stream seen so far in $\mathcal{O}(k^4 \log^2 m)$ time. We apply our techniques to the second problem, approximate near neighbor (ANN) data structures, and achieve an exponential improvement in the dependency on the complexity of the input curves compared to the state of the art.
Shadow Accrual Maps: Efficient Accumulation of City-Scale Shadows Over Time
Venue: arXiv cs.GR 2019
Year: 2019

Large scale shadows from buildings in a city play an important role in determining the environmental quality of public spaces. They can be both beneficial, such as for pedestrians during summer, and detrimental, by impacting vegetation and by blocking direct sunlight. Determining the effects of shadows requires the accumulation of shadows over time across different periods in a year. In this paper, we propose a simple yet efficient class of approach that uses the properties of sun movement to track the changing position of shadows within a fixed time interval. We use this approach to extend two commonly used shadowing techniques, shadow maps and ray tracing, and demonstrate the efficiency of our approach. Our technique is used to develop an interactive visual analysis system, Shadow Profiler, targeted at city planners and architects that allows them to test the impact of shadows for different development scenarios. We validate the usefulness of this system through case studies set in Manhattan, a dense borough of New York City.
Partially Observable Planning and Learning for Systems with Non-Uniform Dynamics
Venue: arXiv cs.RO 2019
Year: 2019

We propose a neural network architecture, called TransNet, that combines planning and model learning for solving Partially Observable Markov Decision Processes (POMDPs) with non-uniform system dynamics. The past decade has seen a substantial advancement in solving POMDP problems. However, constructing a suitable POMDP model remains difficult. Recently, neural network architectures have been proposed to alleviate the difficulty in acquiring such models. Although the results are promising, existing architectures restrict the type of system dynamics that can be learned --that is, system dynamics must be the same in all parts of the state space. TransNet relaxes such a restriction. Key to this relaxation is a novel neural network module that classifies the state space into classes and then learns the system dynamics of the different classes. TransNet uses this module together with the overall architecture of QMDP-Net[1] to allow solving POMDPs that have more expressive dynamic models, while maintaining efficient data requirement. Its evaluation on typical benchmarks in robot navigation with initially unknown system and environment models indicates that TransNet substantially out-performs the quality of the generated policies and learning efficiency of the state-of-the-art method QMDP-Net.
Neural Input Search for Large Scale Recommendation Models
Venue: arXiv cs.LG 2019
Year: 2019

Recommendation problems with large numbers of discrete items, such as products, webpages, or videos, are ubiquitous in the technology industry. Deep neural networks are being increasingly used for these recommendation problems. These models use embeddings to represent discrete items as continuous vectors, and the vocabulary sizes and embedding dimensions, although heavily influence the model's accuracy, are often manually selected in a heuristical manner. We present Neural Input Search (NIS), a technique for learning the optimal vocabulary sizes and embedding dimensions for categorical features. The goal is to maximize prediction accuracy subject to a constraint on the total memory used by all embeddings. Moreover, we argue that the traditional Single-size Embedding (SE), which uses the same embedding dimension for all values of a feature, suffers from inefficient usage of model capacity and training data. We propose a novel type of embedding, namely Multi-size Embedding (ME), which allows the embedding dimension to vary for different values of the feature. During training we use reinforcement learning to find the optimal vocabulary size for each feature and embedding dimension for each value of the feature. In experiments on two common types of large scale recommendation problems, i.e. retrieval and ranking problems, NIS automatically found better vocabulary and embedding sizes that result in $6.8\%$ and $1.8\%$ relative improvements on Recall@1 and ROC-AUC over manually optimized ones.
User Detection Performance Analysis for Grant-Free Uplink Transmission in Large-Scale Antenna Systems
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, user detection performance of a grant-free uplink transmission in a large scale antenna system is analyzed, in which a general grant-free multiple access is considered as the system model and Zadoff-Chu sequence is used for the uplink pilot. The false alarm probabilities of various user detection schemes under the target detection probabilities are evaluated.
Exploiting user-frequency information for mining regionalisms from Social Media texts
Venue: arXiv cs.CL 2019
Year: 2019

The task of detecting regionalisms (expressions or words used in certain regions) has traditionally relied on the use of questionnaires and surveys, and has also heavily depended on the expertise and intuition of the surveyor. The irruption of Social Media and its microblogging services has produced an unprecedented wealth of content, mainly informal text generated by users, opening new opportunities for linguists to extend their studies of language variation. Previous work on automatic detection of regionalisms depended mostly on word frequencies. In this work, we present a novel metric based on Information Theory that incorporates user frequency. We tested this metric on a corpus of Argentinian Spanish tweets in two ways: via manual annotation of the relevance of the retrieved terms, and also as a feature selection method for geolocation of users. In either case, our metric outperformed other techniques based solely in word frequency, suggesting that measuring the amount of users that produce a word is informative. This tool has helped lexicographers discover several unregistered words of Argentinian Spanish, as well as different meanings assigned to registered words.
Simple Kinematic Feedback Enhances Autonomous Learning in Bio-Inspired Tendon-Driven Systems
Venue: arXiv cs.RO 2019
Year: 2019

Error feedback is known to improve performance by correcting control signals in response to perturbations. Here we show how adding simple error feedback can also accelerate and robustify autonomous learning in a tendon-driven robot. We implemented two versions of the General-to-Particular (G2P) autonomous learning algorithm to produce multiple movement tasks using a tendon-driven leg with two joints and three tendons: one with and one without kinematic feedback. As expected, feedback improved performance in simulation and hardware. However, we see these improvements even in the presence of sensory delays of up to 100 ms and when experiencing substantial contact collisions. Importantly, feedback accelerates learning and enhances G2P's continual refinement of the initial inverse map by providing the system with more relevant data to train on. This allows the system to perform well even after only 60 seconds of initial motor babbling.
Adding Common Randomness Can Remove the Secrecy Constraints in Communication Networks
Venue: arXiv cs.IT 2019
Year: 2019

In communication networks secrecy constraints usually incur an extra limit in capacity or generalized degrees-of-freedom (GDoF), in the sense that a penalty in capacity or GDoF is incurred due to the secrecy constraints. Over the past decades a significant amount of effort has been made by the researchers to understand the limits of secrecy constraints in communication networks. In this work, we focus on how to remove the secrecy constraints in communication networks, i.e., how to remove the GDoF penalty due to secrecy constraints. We begin with three basic settings: a two-user symmetric Gaussian interference channel with confidential messages, a symmetric Gaussian wiretap channel with a helper, and a two-user symmetric Gaussian multiple access wiretap channel. Interestingly, in this work we show that adding common randomness at the transmitters can totally remove the penalty in GDoF or GDoF region of the three settings considered here. The results reveal that adding common randomness at the transmitters is a powerful way to remove the secrecy constraints in communication networks in terms of GDoF performance. Common randomness can be generated offline. The role of the common randomness is to jam the information signal at the eavesdroppers, without causing too much interference at the legitimate receivers. To accomplish this role, a new method of Markov chain-based interference neutralization is proposed in the achievability schemes utilizing common randomness. From the practical point of view, we hope to use less common randomness to remove secrecy constraints in terms of GDoF performance. With this motivation, for most of the cases we characterize the minimal GDoF of common randomness to remove secrecy constraints, based on our derived converses and achievability.
Multi-Person tracking by multi-scale detection in Basketball scenarios
Venue: arXiv cs.CV 2019
Year: 2019

Tracking data is a powerful tool for basketball teams in order to extract advanced semantic information and statistics that might lead to a performance boost. However, multi-person tracking is a challenging task to solve in single-camera video sequences, given the frequent occlusions and cluttering that occur in a restricted scenario. In this paper, a novel multi-scale detection method is presented, which is later used to extract geometric and content features, resulting in a multi-person video tracking system. Having built a dataset from scratch together with its ground truth (more than 10k bounding boxes), standard metrics are evaluated, obtaining notable results both in terms of detection (F1-score) and tracking (MOTA). The presented system could be used as a source of data gathering in order to extract useful statistics and semantic analyses a posteriori.
Smoothed Analysis of Order Types
Venue: arXiv cs.CG 2019
Year: 2019

Consider an ordered point set $P = (p_1,\ldots,p_n)$, its order type (denoted by $χ_P$) is a map which assigns to every triple of points a value in $\{+,-,0\}$ based on whether the points are collinear(0), oriented clockwise(-) or counter-clockwise(+). An abstract order type is a map $χ: \left[\substack{n\\3}\right] \rightarrow \{+,-,0\}$ (where $\left[\substack{n\\3}\right]$ is the collection of all triples of a set of $n$ elements) that satisfies the following condition: for every set of five elements $S\subset [n]$ its induced order type $χ_{|S}$ is realizable by a point set. To be precise, a point set $P$ realizes an order type $χ$,if $χ_P(p_i,p_j,p_k) = χ(i,j,k)$, for all $i<j<k$. Planar point sets are among the most basic and natural geometric objects of study in Discrete and Computational Geometry. Properties of point sets are relevant in theory and practice alike. It is known, that deciding if an abstract order type is realizable is complete for the existential theory of the reals. Our results show that order type realizability is much easier for realistic instances than in the worst case. In particular, we can recognize instances in "expected \NP-time". This is one of the first $\exists\mathbb{R}$-complete problems analyzed under the lens of Smoothed Analysis.
Playing Go without Game Tree Search Using Convolutional Neural Networks
Venue: arXiv cs.AI 2019
Year: 2019

The game of Go has a long history in East Asian countries, but the field of Computer Go has yet to catch up to humans until the past couple of years. While the rules of Go are simple, the strategy and combinatorics of the game are immensely complex. Even within the past couple of years, new programs that rely on neural networks to evaluate board positions still explore many orders of magnitude more board positions per second than a professional can. We attempt to mimic human intuition in the game by creating a convolutional neural policy network which, without any sort of tree search, should play the game at or above the level of most humans. We introduce three structures and training methods that aim to create a strong Go player: non-rectangular convolutions, which will better learn the shapes on the board, supervised learning, training on a data set of 53,000 professional games, and reinforcement learning, training on games played between different versions of the network. Our network has already surpassed the skill level of intermediate amateurs simply using supervised learning. Further training and implementation of non-rectangular convolutions and reinforcement learning will likely increase this skill level much further.