OpenRaiser/Intern-Atlas huggingface dataset:
Soft + Hardwired Attention: An LSTM Framework for Human Trajectory Prediction and Abnormal Event Detection
Venue: arXiv cs.CV 2017
Year: 2017

As humans we possess an intuitive ability for navigation which we master through years of practice; however existing approaches to model this trait for diverse tasks including monitoring pedestrian flow and detecting abnormal events have been limited by using a variety of hand-crafted features. Recent research in the area of deep-learning has demonstrated the power of learning features directly from the data; and related research in recurrent neural networks has shown exemplary results in sequence-to-sequence problems such as neural machine translation and neural image caption generation. Motivated by these approaches, we propose a novel method to predict the future motion of a pedestrian given a short history of their, and their neighbours, past behaviour. The novelty of the proposed method is the combined attention model which utilises both "soft attention" as well as "hard-wired" attention in order to map the trajectory information from the local neighbourhood to the future positions of the pedestrian of interest. We illustrate how a simple approximation of attention weights (i.e hard-wired) can be merged together with soft attention weights in order to make our model applicable for challenging real world scenarios with hundreds of neighbours. The navigational capability of the proposed method is tested on two challenging publicly available surveillance databases where our model outperforms the current-state-of-the-art methods. Additionally, we illustrate how the proposed architecture can be directly applied for the task of abnormal event detection without handcrafting the features.
A $\frac{3}{2}$-Approximation Algorithm for Tree Augmentation via Chvátal-Gomory Cuts
Venue: arXiv cs.DM 2017
Year: 2017

The weighted tree augmentation problem (WTAP) is a fundamental network design problem. We are given an undirected tree $G = (V,E)$, an additional set of edges $L$ called links and a cost vector $c \in \mathbb{R}^L_{\geq 1}$. The goal is to choose a minimum cost subset $S \subseteq L$ such that $G = (V, E \cup S)$ is $2$-edge-connected. In the unweighted case, that is, when we have $c_\ell = 1$ for all $\ell \in L$, the problem is called the tree augmentation problem (TAP). Both problems are known to be APX-hard, and the best known approximation factors are $2$ for WTAP by (Frederickson and JáJá, '81) and $\tfrac{3}{2}$ for TAP due to (Kortsarz and Nutov, TALG '16). In the case where all link costs are bounded by a constant $M$, (Adjiashvili, SODA '17) recently gave a $\approx 1.96418+\varepsilon$-approximation algorithm for WTAP under this assumption. This is the first approximation with a better guarantee than $2$ that does not require restrictions on the structure of the tree or the links. In this paper, we improve Adjiashvili's approximation to a $\frac{3}{2}+\varepsilon$-approximation for WTAP under the bounded cost assumption. We achieve this by introducing a strong LP that combines $\{0,\frac{1}{2}\}$-Chvátal-Gomory cuts for the standard LP for the problem with bundle constraints from Adjiashvili. We show that our LP can be solved efficiently and that it is exact for some instances that arise at the core of Adjiashvili's approach. This results in the improved guarantee of $\frac{3}{2}+\varepsilon$. For TAP, this is the best known LP-based result, and matches the bound of $\frac{3}{2}+\varepsilon$ achieved by the best SDP-based algorithm due to (Cheriyan and Gao, arXiv '15).
Embeddings of Schatten Norms with Applications to Data Streams
Venue: arXiv cs.DS 2017
Year: 2017

Given an $n \times d$ matrix $A$, its Schatten-$p$ norm, $p \geq 1$, is defined as $\|A\|_p = \left (\sum_{i=1}^{\textrm{rank}(A)}σ_i(A)^p \right )^{1/p}$, where $σ_i(A)$ is the $i$-th largest singular value of $A$. These norms have been studied in functional analysis in the context of non-commutative $\ell_p$-spaces, and recently in data stream and linear sketching models of computation. Basic questions on the relations between these norms, such as their embeddability, are still open. Specifically, given a set of matrices $A^1, \ldots, A^{\operatorname{poly}(nd)} \in \mathbb{R}^{n \times d}$, suppose we want to construct a linear map $L$ such that $L(A^i) \in \mathbb{R}^{n' \times d'}$ for each $i$, where $n' \leq n$ and $d' \leq d$, and further, $\|A^i\|_p \leq \|L(A^i)\|_q \leq D_{p,q} \|A^i\|_p$ for a given approximation factor $D_{p,q}$ and real number $q \geq 1$. Then how large do $n'$ and $d'$ need to be as a function of $D_{p,q}$? We nearly resolve this question for every $p, q \geq 1$, for the case where $L(A^i)$ can be expressed as $R \cdot A^i \cdot S$, where $R$ and $S$ are arbitrary matrices that are allowed to depend on $A^1, \ldots, A^t$, that is, $L(A^i)$ can be implemented by left and right matrix multiplication. Namely, for every $p, q \geq 1$, we provide nearly matching upper and lower bounds on the size of $n'$ and $d'$ as a function of $D_{p,q}$. Importantly, our upper bounds are {\it oblivious}, meaning that $R$ and $S$ do not depend on the $A^i$, while our lower bounds hold even if $R$ and $S$ depend on the $A^i$. As an application of our upper bounds, we answer a recent open question of Blasiok et al. about space-approximation trade-offs for the Schatten $1$-norm, showing in a data stream it is possible to estimate the Schatten-$1$ norm up to a factor of $D \geq 1$ using $\tilde{O}(\min(n,d)^2/D^4)$ space.
Robust Shape Registration using Fuzzy Correspondences
Venue: arXiv cs.CV 2017
Year: 2017

Shape registration is the process of aligning one 3D model to another. Most previous methods to align shapes with no known correspondences attempt to solve for both the transformation and correspondences iteratively. We present a shape registration approach that solves for the transformation using fuzzy correspondences to maximize the overlap between the given shape and the target shape. A coarse to fine approach with Levenberg-Marquardt method is used for optimization. Real and synthetic experiments show our approach is robust and outperforms other state of the art methods when point clouds are noisy, sparse, and have non-uniform density. Experiments show our method is more robust to initialization and can handle larger scale changes and rotation than other methods. We also show that the approach can be used for 2D-3D alignment via ray-point alignment.
Perceptual Compressive Sensing based on Contrast Sensitivity Function: Can we avoid non-visible redundancies acquisition?
Venue: arXiv cs.MM 2017
Year: 2017

In this paper, we propose a novel CS approach in which the acquisition of non-visible information is also avoided.
Locally Repairable Codes with Multiple $(r_{i}, δ_{i})$-Localities
Venue: arXiv cs.IT 2017
Year: 2017

In distributed storage systems, locally repairable codes (LRCs) are introduced to realize low disk I/O and repair cost. In order to tolerate multiple node failures, the LRCs with \emph{$(r, δ)$-locality} are further proposed. Since hot data is not uncommon in a distributed storage system, both Zeh \emph{et al.} and Kadhe \emph{et al.} focus on the LRCs with \emph{multiple localities or unequal localities} (ML-LRCs) recently, which said that the localities among the code symbols can be different. ML-LRCs are attractive and useful in reducing repair cost for hot data. In this paper, we generalize the ML-LRCs to the $(r,δ)$-locality case of multiple node failures, and define an LRC with multiple $(r_{i}, δ_{i})_{i\in [s]}$ localities ($s\ge 2$), where $r_{1}\leq r_{2}\leq\dots\leq r_{s}$ and $δ_{1}\geqδ_{2}\geq\dots\geqδ_{s}\geq2$. Such codes ensure that some hot data could be repaired more quickly and have better failure-tolerance in certain cases because of relatively smaller $r_{i}$ and larger $δ_{i}$. Then, we derive a Singleton-like upper bound on the minimum distance for the proposed LRCs by employing the regenerating-set technique. Finally, we obtain a class of explicit and structured constructions of optimal ML-LRCs, and further extend them to the cases of multiple $(r_{i}, δ)_{i\in [s]}$ localities.
Relay-Aided MIMO Cellular Networks Using Opposite Directional Interference Alignment
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we first propose interference alignment (IA) scheme for uplink transmission of multiple-input-mulitple-output (MIMO) cellular network with a help of relay which operates in halfduplex mode. The proposed scheme only requires global channel state information (CSI) knowledge at relay and no transmitter beamforming and time extension is required at user equipment (UE), which differs from the conventional IA schemes for cellular network. We derive the feasibility condition of the proposed scheme for the general network configuration and analyze the degrees-of-freedom (DoF) performance of the proposed IA scheme. Extension of proposed scheme for downlink and full-duplex network are further described in this paper. It is also shown that the same advantage as the uplink case can be obtained for downlink case through relay induced interfering multiple access channel (IMAC) and interfering broadcast channel (IBC) duality. Furthermore, full-duplex network is shown to have same advantages with half-duplex cases.
Blocking Self-avoiding Walks Stops Cyber-epidemics: A Scalable GPU-based Approach
Venue: arXiv cs.SI 2017
Year: 2017

Cyber-epidemics, the widespread of fake news or propaganda through social media, can cause devastating economic and political consequences. A common countermeasure against cyber-epidemics is to disable a small subset of suspected social connections or accounts to effectively contain the epidemics. An example is the recent shutdown of 125,000 ISIS-related Twitter accounts. Despite many proposed methods to identify such subset, none are scalable enough to provide high-quality solutions in nowadays billion-size networks. To this end, we investigate the Spread Interdiction problems that seek most effective links (or nodes) for removal under the well-known Linear Threshold model. We propose novel CPU-GPU methods that scale to networks with billions of edges, yet, possess rigorous theoretical guarantee on the solution quality. At the core of our methods is an $O(1)$-space out-of-core algorithm to generate a new type of random walks, called Hitting Self-avoiding Walks (HSAWs). Such a low memory requirement enables handling of big networks and, more importantly, hiding latency via scheduling of millions of threads on GPUs. Comprehensive experiments on real-world networks show that our algorithms provides much higher quality solutions and are several order of magnitude faster than the state-of-the art. Comparing to the (single-core) CPU counterpart, our GPU implementations achieve significant speedup factors up to 177x on a single GPU and 338x on a GPU pair.
Hemingway: Modeling Distributed Optimization Algorithms
Venue: arXiv cs.DC 2017
Year: 2017

Distributed optimization algorithms are widely used in many industrial machine learning applications. However choosing the appropriate algorithm and cluster size is often difficult for users as the performance and convergence rate of optimization algorithms vary with the size of the cluster. In this paper we make the case for an ML-optimizer that can select the appropriate algorithm and cluster size to use for a given problem. To do this we propose building two models: one that captures the system level characteristics of how computation, communication change as we increase cluster sizes and another that captures how convergence rates change with cluster sizes. We present preliminary results from our prototype implementation called Hemingway and discuss some of the challenges involved in developing such a system.
I Ate This: A Photo-based Food Journaling System with Expert Feedback
Venue: arXiv cs.HC 2017
Year: 2017

What we eat is one of the most frequent and important health decisions we make in daily life, yet it remains notoriously difficult to capture and understand. Effective food journaling is thus a grand challenge in personal health informatics. In this paper we describe a system for food journaling called I Ate This, which is inspired by the Remote Food Photography Method (RFPM). I Ate This is simple: you use a smartphone app to take a photo and give a very basic description of any food or beverage you are about to consume. Later, a qualified dietitian will evaluate your photo, giving you feedback on how you did and where you can improve. The aim of I Ate This is to provide a convenient, visual and reliable way to help users learn from their eating habits and nudge them towards better choices each and every day. Ultimately, this incremental approach can lead to long-term behaviour change. Our goal is to bring RFPM to a wider audience, through APIs that can be incorporated into other apps.
Latent Variable Dialogue Models and their Diversity
Venue: arXiv cs.CL 2017
Year: 2017

We present a dialogue generation model that directly captures the variability in possible responses to a given input, which reduces the `boring output' issue of deterministic dialogue models. Experiments show that our model generates more diverse outputs than baseline models, and also generates more consistently acceptable output than sampling from a deterministic encoder-decoder model.
Generating Adversarial Malware Examples for Black-Box Attacks Based on GAN
Venue: arXiv cs.LG 2017
Year: 2017

Machine learning has been used to detect new malware in recent years, while malware authors have strong motivation to attack such algorithms. Malware authors usually have no access to the detailed structures and parameters of the machine learning models used by malware detection systems, and therefore they can only perform black-box attacks. This paper proposes a generative adversarial network (GAN) based algorithm named MalGAN to generate adversarial malware examples, which are able to bypass black-box machine learning based detection models. MalGAN uses a substitute detector to fit the black-box malware detection system. A generative network is trained to minimize the generated adversarial examples' malicious probabilities predicted by the substitute detector. The superiority of MalGAN over traditional gradient based adversarial example generation algorithms is that MalGAN is able to decrease the detection rate to nearly zero and make the retraining based defensive method against adversarial examples hard to work.
CLS: New Problems and Completeness
Venue: arXiv cs.CC 2017
Year: 2017

The complexity class CLS was introduced by Daskalakis and Papadimitriou with the goal of capturing the complexity of some well-known problems in PPAD$~\cap~$PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. No complete problem was known for CLS, and in previous work, the problems ContractionMap, i.e., the problem of finding an approximate fixpoint of a contraction map, and PLCP, i.e., the problem of solving a P-matrix Linear Complementarity Problem, were identified as prime candidates. First, we present a new CLS-complete problem MetaMetricContractionMap, which is closely related to the ContractionMap. Second, we introduce EndOfPotentialLine, which captures aspects of PPAD and PLS directly via a monotonic directed path, and show that EndOfPotentialLine is in CLS via a two-way reduction to EndOfMeteredLine. The latter was defined to keep track of how far a vertex is on the PPAD path via a restricted potential function. Third, we reduce PLCP to EndOfPotentialLine, thus making EndOfPotentialLine and EndOfMeteredLine at least as likely to be hard for CLS as PLCP. This last result leverages the monotonic structure of Lemke paths for PLCP problems, making EndOfPotentialLine a likely candidate to capture the exact complexity of PLCP; we note that the structure of Lemke-Howson paths for finding a Nash equilibrium in a two-player game very directly motivated the definition of the complexity class PPAD, which eventually ended up capturing this problem's complexity exactly.
Joint Transmission with Dummy Symbols for Dynamic TDD in Ultra-Dense Deployments
Venue: arXiv cs.IT 2017
Year: 2017

Dynamic time-division duplexing (TDD) is considered a promising solution to deal with fast-varying traffic often found in ultra-densely deployed networks. At the same time, it generates more interference which may degrade the performance of some user equipment (UE). When base station (BS) utilization is low, some BSs may not have an UE to serve. Rather than going into sleep mode, the idle BSs can help nearby UEs using joint transmission. To deal with BS-to-BS interference, we propose using joint transmission with dummy symbols where uplink BSs serving uplink UEs participate in the precoding. Since BSs are not aware of the uplink symbols beforehand, any symbols with zero power can be transmitted instead to null the BS-to-BS interference. Numerical results show significant performance gains for uplink and downlink at low and medium utilization. By varying the number of participating uplink BSs in the precoding, we also show that it is possible to successfully trade performance in the two directions.
Parallel needed reduction for pure interaction nets
Venue: arXiv cs.LO 2017
Year: 2017

Reducing interaction nets without any specific strategy benefits from constant time per step. On the other hand, a canonical reduction step for weak reduction to interface normal form is linear by depth of terms. In this paper, we refine the weak interaction calculus to reveal the actual cost of its reduction. As a result, we obtain a notion of needed reduction that can be implemented in constant time per step without allowing any free ports and without sacrificing parallelism.
An Attention-Based Deep Net for Learning to Rank
Venue: arXiv cs.LG 2017
Year: 2017

In information retrieval, learning to rank constructs a machine-based ranking model which given a query, sorts the search results by their degree of relevance or importance to the query. Neural networks have been successfully applied to this problem, and in this paper, we propose an attention-based deep neural network which better incorporates different embeddings of the queries and search results with an attention-based mechanism. This model also applies a decoder mechanism to learn the ranks of the search results in a listwise fashion. The embeddings are trained with convolutional neural networks or the word2vec model. We demonstrate the performance of this model with image retrieval and text querying data sets.
DEEProtect: Enabling Inference-based Access Control on Mobile Sensing Applications
Venue: arXiv cs.CR 2017
Year: 2017

Personal sensory data is used by context-aware mobile applications to provide utility. However, the same data can also be used by an adversary to make sensitive inferences about a user thereby violating her privacy. We present DEEProtect, a framework that enables a novel form of inference control, in which mobile apps with access to sensor data are limited (provably) in their ability to make inferences about user's sensitive data and behavior. DEEProtect adopts a two-layered privacy strategy. First, it leverages novel autoencoder techniques to perform data minimization and limits the amount of information being shared; the learning network is used to derive a compact representation of sensor data consisting only of features relevant to authorized utility-providing inferences. Second, DEEProtect obfuscates the previously learnt features, thereby providing an additional layer of protection against sensitive inferences. Our framework supports both conventional as well as a novel relaxed notion of local differential privacy that enhances utility. Through theoretical analysis and extensive experiments using real-world datasets, we demonstrate that when compared to existing approaches DEEProtect provides provable privacy guarantees with up to 8x improvement in utility. Finally, DEEProtect shares obfuscated but raw sensor data reconstructed from the perturbed features, thus requiring no changes to the existing app interfaces.
Reinforcement Learning Based Argument Component Detection
Venue: arXiv cs.CL 2017
Year: 2017

Argument component detection (ACD) is an important sub-task in argumentation mining. ACD aims at detecting and classifying different argument components in natural language texts. Historical annotations (HAs) are important features the human annotators consider when they manually perform the ACD task. However, HAs are largely ignored by existing automatic ACD techniques. Reinforcement learning (RL) has proven to be an effective method for using HAs in some natural language processing tasks. In this work, we propose a RL-based ACD technique, and evaluate its performance on two well-annotated corpora. Results suggest that, in terms of classification accuracy, HAs-augmented RL outperforms plain RL by at most 17.85%, and outperforms the state-of-the-art supervised learning algorithm by at most 11.94%.
Player Skill Decomposition in Multiplayer Online Battle Arenas
Venue: arXiv cs.SI 2017
Year: 2017

Successful analysis of player skills in video games has important impacts on the process of enhancing player experience without undermining their continuous skill development. Moreover, player skill analysis becomes more intriguing in team-based video games because such form of study can help discover useful factors in effective team formation. In this paper, we consider the problem of skill decomposition in MOBA (MultiPlayer Online Battle Arena) games, with the goal to understand what player skill factors are essential for the outcome of a game match. To understand the construct of MOBA player skills, we utilize various skill-based predictive models to decompose player skills into interpretative parts, the impact of which are assessed in statistical terms. We apply this analysis approach on two widely known MOBAs, namely League of Legends (LoL) and Defense of the Ancients 2 (DOTA2). The finding is that base skills of in-game avatars, base skills of players, and players' champion-specific skills are three prominent skill components influencing LoL's match outcomes, while those of DOTA2 are mainly impacted by in-game avatars' base skills but not much by the other two.
Compressive Channel Estimation and Multi-user Detection in C-RAN
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers the channel estimation (CE) and multi-user detection (MUD) problems in cloud radio access network (C-RAN). Assuming that active users are sparse in the network, we solve CE and MUD problems with compressed sensing (CS) technology to greatly reduce the long identification pilot overhead. A mixed L{2,1}-regularization functional for extended sparse group-sparsity recovery is proposed to exploit the inherently sparse property existing both in user activities and remote radio heads (RRHs) that active users are attached to. Empirical and theoretical guidelines are provided to help choosing tuning parameters which have critical effect on the performance of the penalty functional. To speed up the processing procedure, based on alternating direction method of multipliers and variable splitting strategy, an efficient algorithm is formulated which is guaranteed to be convergent. Numerical results are provided to illustrate the effectiveness of the proposed functional and efficient algorithm.