OpenRaiser/Intern-Atlas huggingface dataset:
UAV-Aided Offloading for Cellular Hotspot
Venue: arXiv cs.IT 2018
Year: 2018

In conventional terrestrial cellular networks, mobile terminals (MTs) at the cell edge often pose a performance bottleneck due to their long distances from the serving ground base station (GBS), especially in hotspot period when the GBS is heavily loaded. This paper proposes a new hybrid network architecture by leveraging the use of unmanned aerial vehicle (UAV) as an aerial mobile base station, which flies cyclically along the cell edge to offload data traffic for cell-edge MTs. We aim to maximize the minimum throughput of all MTs by jointly optimizing the UAV's trajectory, bandwidth allocation and user partitioning. We first consider orthogonal spectrum sharing between the UAV and GBS, and then extend to spectrum reuse where the total bandwidth is shared by both the GBS and UAV with their mutual interference effectively avoided. Numerical results show that the proposed hybrid network with optimized spectrum sharing and cyclical multiple access design significantly improves the spatial throughput over the conventional GBS-only network; while the spectrum reuse scheme provides further throughput gains at the cost of slightly higher complexity for interference control. Moreover, compared to the conventional small-cell offloading scheme, the proposed UAV offloading scheme is shown to outperform in terms of throughput, besides saving the infrastructure cost.
Learning Structured Text Representations
Venue: arXiv cs.CL 2018
Year: 2018

In this paper, we focus on learning structure-aware document representations from data without recourse to a discourse parser or additional annotations. Drawing inspiration from recent efforts to empower neural networks with a structural bias, we propose a model that can encode a document while automatically inducing rich structural dependencies. Specifically, we embed a differentiable non-projective parsing algorithm into a neural model and use attention mechanisms to incorporate the structural biases. Experimental evaluation across different tasks and datasets shows that the proposed model achieves state-of-the-art results on document modeling tasks while inducing intermediate structures which are both interpretable and meaningful.
Plan3D: Viewpoint and Trajectory Optimization for Aerial Multi-View Stereo Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a new method that efficiently computes a set of viewpoints and trajectories for high-quality 3D reconstructions in outdoor environments. Our goal is to automatically explore an unknown area, and obtain a complete 3D scan of a region of interest (e.g., a large building). Images from a commodity RGB camera, mounted on an autonomously navigated quadcopter, are fed into a multi-view stereo reconstruction pipeline that produces high-quality results but is computationally expensive. In this setting, the scanning result is constrained by the restricted flight time of quadcopters. To this end, we introduce a novel optimization strategy that respects these constraints by maximizing the information gain from sparsely-sampled view points while limiting the total travel distance of the quadcopter. At the core of our method lies a hierarchical volumetric representation that allows the algorithm to distinguish between unknown, free, and occupied space. Furthermore, our information gain based formulation leverages this representation to handle occlusions in an efficient manner. In addition to the surface geometry, we utilize the free-space information to avoid obstacles and determine collision-free flight paths. Our tool can be used to specify the region of interest and to plan trajectories. We demonstrate our method by obtaining a number of compelling 3D reconstructions, and provide a thorough quantitative evaluation showing improvement over previous state-of-the-art and regular patterns.
Multi-shot ASP solving with clingo
Venue: arXiv cs.AI 2018
Year: 2018

We introduce a new flexible paradigm of grounding and solving in Answer Set Programming (ASP), which we refer to as multi-shot ASP solving, and present its implementation in the ASP system clingo. Multi-shot ASP solving features grounding and solving processes that deal with continuously changing logic programs. In doing so, they remain operative and accommodate changes in a seamless way. For instance, such processes allow for advanced forms of search, as in optimization or theory solving, or interaction with an environment, as in robotics or query-answering. Common to them is that the problem specification evolves during the reasoning process, either because data or constraints are added, deleted, or replaced. This evolutionary aspect adds another dimension to ASP since it brings about state changing operations. We address this issue by providing an operational semantics that characterizes grounding and solving processes in multi-shot ASP solving. This characterization provides a semantic account of grounder and solver states along with the operations manipulating them. The operative nature of multi-shot solving avoids redundancies in relaunching grounder and solver programs and benefits from the solver's learning capacities. clingo accomplishes this by complementing ASP's declarative input language with control capacities. On the declarative side, a new directive allows for structuring logic programs into named and parameterizable subprograms. The grounding and integration of these subprograms into the solving process is completely modular and fully controllable from the procedural side. To this end, clingo offers a new application programming interface that is conveniently accessible via scripting languages.
Temporal anomaly detection: calibrating the surprise
Venue: arXiv cs.CR 2018
Year: 2018

We propose a hybrid approach to temporal anomaly detection in access data of users to databases --- or more generally, any kind of subject-object co-occurrence data. We consider a high-dimensional setting that also requires fast computation at test time. Our methodology identifies anomalies based on a single stationary model, instead of requiring a full temporal one, which would be prohibitive in this setting. We learn a low-rank stationary model from the training data, and then fit a regression model for predicting the expected likelihood score of normal access patterns in the future. The disparity between the predicted likelihood score and the observed one is used to assess the `surprise' at test time. This approach enables calibration of the anomaly score, so that time-varying normal behavior patterns are not considered anomalous. We provide a detailed description of the algorithm, including a convergence analysis, and report encouraging empirical results. One of the data sets that we tested, TDA, is new for the public domain. It consists of two months' worth of database access records from a live system. Our code is publicly available at https://github.com/eyalgut/TLR_anomaly_detection.git. The TDA data set is available at https://www.kaggle.com/eyalgut/binary-traffic-matrices.
HiNet: Hierarchical Classification with Neural Network
Venue: arXiv cs.LG 2018
Year: 2018

Traditionally, classifying large hierarchical labels with more than 10000 distinct traces can only be achieved with flatten labels. Although flatten labels is feasible, it misses the hierarchical information in the labels. Hierarchical models like HSVM by \cite{vural2004hierarchical} becomes impossible to train because of the sheer number of SVMs in the whole architecture. We developed a hierarchical architecture based on neural networks that is simple to train. Also, we derived an inference algorithm that can efficiently infer the MAP (maximum a posteriori) trace guaranteed by our theorems. Furthermore, the complexity of the model is only $O(n^2)$ compared to $O(n^h)$ in a flatten model, where $h$ is the height of the hierarchy.
Coded Caching Schemes with Reduced Subpacketization from Linear Block Codes
Venue: arXiv cs.IT 2018
Year: 2018

Coded caching is a technique that generalizes conventional caching and promises significant reductions in traffic over caching networks. However, the basic coded caching scheme requires that each file hosted in the server be partitioned into a large number (i.e., the subpacketization level) of non-overlapping subfiles. From a practical perspective, this is problematic as it means that prior schemes are only applicable when the size of the files is extremely large. In this work, we propose coded caching schemes based on combinatorial structures called resolvable designs. These structures can be obtained in a natural manner from linear block codes whose generator matrices possess certain rank properties. We obtain several schemes with subpacketization levels substantially lower than the basic scheme at the cost of an increased rate. Depending on the system parameters, our approach allows us to operate at various points on the subpacketization level vs. rate tradeoff.
Discovering Discrete Latent Topics with Neural Variational Inference
Venue: arXiv cs.CL 2018
Year: 2018

Topic models have been widely explored as probabilistic generative models of documents. Traditional inference methods have sought closed-form derivations for updating the models, however as the expressiveness of these models grows, so does the difficulty of performing fast and accurate inference over their parameters. This paper presents alternative neural approaches to topic modelling by providing parameterisable distributions over topics which permit training by backpropagation in the framework of neural variational inference. In addition, with the help of a stick-breaking construction, we propose a recurrent network that is able to discover a notionally unbounded number of topics, analogous to Bayesian non-parametric topic models. Experimental results on the MXM Song Lyrics, 20NewsGroups and Reuters News datasets demonstrate the effectiveness and efficiency of these neural topic models.
A context-aware e-bike system to reduce pollution inhalation while cycling
Venue: arXiv cs.SY 2018
Year: 2018

The effect of transport-related pollution on human health is fast becoming recognised as a major issue in cities worldwide. Cyclists, in particular, face great risks, as they typically are most exposed to tail-pipe emissions. Three avenues are being explored worldwide in the fight against urban pollution: (i) outright bans on polluting vehicles and embracing zero tailpipe emission vehicles; (ii) measuring air-quality as a means to better informing citizens of zones of higher pollution; and (iii) developing smart mobility devices that seek to minimize the effect of polluting devices on citizens as they transport goods and individuals in our cities. Following this latter direction, in this paper we present a new way to protect cyclists from the effect of urban pollution. Namely, by exploiting the actuation possibilities afforded by pedelecs or e-bikes (electric bikes), we design a cyber-physical system that mitigates the effect of urban pollution by indirectly controlling the breathing rate of cyclists in polluted areas. Results from a real device are presented to illustrate the efficacy of our system.
Model-Based Active Source Identification in Complex Environments
Venue: arXiv cs.RO 2018
Year: 2018

We consider the problem of Active Source Identification (ASI) in steady-state Advection-Diffusion (AD) transport systems. Unlike existing bio-inspired heuristic methods, we propose a model-based method that employs the AD-PDE to capture the transport phenomenon. Specifically, we formulate the Source Identification (SI) problem as a PDE-constrained optimization problem in function spaces. To obtain a tractable solution, we reduce the dimension of the concentration field using Proper Orthogonal Decomposition and approximate the unknown source field using nonlinear basis functions, drastically decreasing the number of unknowns. Moreover, to collect the concentration measurements, we control a robot sensor through a sequence of waypoints that maximize the smallest eigenvalue of the Fisher Information matrix of the unknown source parameters. Specifically, after every new measurement, a SI problem is solved to obtain a source estimate that is used to determine the next waypoint. We show that our algorithm can efficiently identify sources in complex AD systems and non-convex domains, in simulation and experimentally. This is the first time that PDEs are used for robotic SI in practice.
InfoVAE: Information Maximizing Variational Autoencoders
Venue: arXiv cs.LG 2018
Year: 2018

A key advance in learning generative models is the use of amortized inference distributions that are jointly trained with the models. We find that existing training objectives for variational autoencoders can lead to inaccurate amortized inference distributions and, in some cases, improving the objective provably degrades the inference quality. In addition, it has been observed that variational autoencoders tend to ignore the latent variables when combined with a decoding distribution that is too flexible. We again identify the cause in existing training criteria and propose a new class of objectives (InfoVAE) that mitigate these problems. We show that our model can significantly improve the quality of the variational posterior and can make effective use of the latent features regardless of the flexibility of the decoding distribution. Through extensive qualitative and quantitative analyses, we demonstrate that our models outperform competing approaches on multiple performance metrics.
A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem
Venue: arXiv cs.CC 2018
Year: 2018

For integers $n$ and $k$, the density Hales-Jewett number $c_{n,k}$ is defined as the maximal size of a subset of $[k]^n$ that contains no combinatorial line. We show that for $k \ge 3$ the density Hales-Jewett number $c_{n,k}$ is equal to the maximal size of a cylinder intersection in the problem $Part_{n,k}$ of testing whether $k$ subsets of $[n]$ form a partition. It follows that the communication complexity, in the Number On the Forehead (NOF) model, of $Part_{n,k}$, is equal to the minimal size of a partition of $[k]^n$ into subsets that do not contain a combinatorial line. Thus, the bound in \cite{chattopadhyay2007languages} on $Part_{n,k}$ using the Hales-Jewett theorem is in fact tight, and the density Hales-Jewett number can be thought of as a quantity in communication complexity. This gives a new angle to this well studied quantity. As a simple application we prove a lower bound on $c_{n,k}$, similar to the lower bound in \cite{polymath2010moser} which is roughly $c_{n,k}/k^n \ge \exp(-O(\log n)^{1/\lceil \log_2 k\rceil})$. This lower bound follows from a protocol for $Part_{n,k}$. It is interesting to better understand the communication complexity of $Part_{n,k}$ as this will also lead to the better understanding of the Hales-Jewett number. The main purpose of this note is to motivate this study.
A Deformable Interface for Human Touch Recognition using Stretchable Carbon Nanotube Dielectric Elastomer Sensors and Deep Neural Networks
Venue: arXiv cs.HC 2018
Year: 2018

User interfaces provide an interactive window between physical and virtual environments. A new concept in the field of human-computer interaction is a soft user interface; a compliant surface that facilitates touch interaction through deformation. Despite the potential of these interfaces, they currently lack a signal processing framework that can efficiently extract information from their deformation. Here we present OrbTouch, a device that uses statistical learning algorithms, based on convolutional neural networks, to map deformations from human touch to categorical labels (i.e., gestures) and touch location using stretchable capacitor signals as inputs. We demonstrate this approach by using the device to control the popular game Tetris. OrbTouch provides a modular, robust framework to interpret deformation in soft media, laying a foundation for new modes of human computer interaction through shape changing solids.
MirBot: A collaborative object recognition system for smartphones using convolutional neural networks
Venue: arXiv cs.CV 2018
Year: 2018

MirBot is a collaborative application for smartphones that allows users to perform object recognition. This app can be used to take a photograph of an object, select the region of interest and obtain the most likely class (dog, chair, etc.) by means of similarity search using features extracted from a convolutional neural network (CNN). The answers provided by the system can be validated by the user so as to improve the results for future queries. All the images are stored together with a series of metadata, thus enabling a multimodal incremental dataset labeled with synset identifiers from the WordNet ontology. This dataset grows continuously thanks to the users' feedback, and is publicly available for research. This work details the MirBot object recognition system, analyzes the statistics gathered after more than four years of usage, describes the image classification methodology, and performs an exhaustive evaluation using handcrafted features, convolutional neural codes and different transfer learning techniques. After comparing various models and transformation methods, the results show that the CNN features maintain the accuracy of MirBot constant over time, despite the increasing number of new classes. The app is freely available at the Apple and Google Play stores.
Privacy-Preserving Electronic Ticket Scheme with Attribute-based Credentials
Venue: arXiv cs.CR 2018
Year: 2018

Electronic tickets (e-tickets) are electronic versions of paper tickets, which enable users to access intended services and improve services' efficiency. However, privacy may be a concern of e-ticket users. In this paper, a privacy-preserving electronic ticket scheme with attribute-based credentials is proposed to protect users' privacy and facilitate ticketing based on a user's attributes. Our proposed scheme makes the following contributions: (1) users can buy different tickets from ticket sellers without releasing their exact attributes; (2) two tickets of the same user cannot be linked; (3) a ticket cannot be transferred to another user; (4) a ticket cannot be double spent; (5) the security of the proposed scheme is formally proven and reduced to well known (q-strong Diffie-Hellman) complexity assumption; (6) the scheme has been implemented and its performance empirically evaluated. To the best of our knowledge, our privacy-preserving attribute-based e-ticket scheme is the first one providing these five features. Application areas of our scheme include event or transport tickets where users must convince ticket sellers that their attributes (e.g. age, profession, location) satisfy the ticket price policies to buy discounted tickets. More generally, our scheme can be used in any system where access to services is only dependent on a user's attributes (or entitlements) but not their identities.
Dynamics over Signed Networks
Venue: arXiv cs.SI 2018
Year: 2018

A signed network is a network with each link associated with a positive or negative sign. Models for nodes interacting over such signed networks, where two different types of interactions take place along the positive and negative links, respectively, arise from various biological, social, political, and economic systems. As modifications to the conventional DeGroot dynamics for positive links, two basic types of negative interactions along negative links, namely the opposing rule and the repelling rule, have been proposed and studied in the literature. This paper reviews a few fundamental convergence results for such dynamics over deterministic or random signed networks under a unified algebraic-graphical method. We show that a systematic tool of studying node state evolution over signed networks can be obtained utilizing generalized Perron-Frobenius theory, graph theory, and elementary algebraic recursions.
Gradient descent GAN optimization is locally stable
Venue: arXiv cs.LG 2018
Year: 2018

Despite the growing prominence of generative adversarial networks (GANs), optimization in GANs is still a poorly understood topic. In this paper, we analyze the "gradient descent" form of GAN optimization i.e., the natural setting where we simultaneously take small gradient steps in both generator and discriminator parameters. We show that even though GAN optimization does not correspond to a convex-concave game (even for simple parameterizations), under proper conditions, equilibrium points of this optimization procedure are still \emph{locally asymptotically stable} for the traditional GAN formulation. On the other hand, we show that the recently proposed Wasserstein GAN can have non-convergent limit cycles near equilibrium. Motivated by this stability analysis, we propose an additional regularization term for gradient descent GAN updates, which \emph{is} able to guarantee local stability for both the WGAN and the traditional GAN, and also shows practical promise in speeding up convergence and addressing mode collapse.
Adversarially Regularized Autoencoders
Venue: arXiv cs.LG 2018
Year: 2018

Deep latent variable models, trained using variational autoencoders or generative adversarial networks, are now a key technique for representation learning of continuous structures. However, applying similar methods to discrete structures, such as text sequences or discretized images, has proven to be more challenging. In this work, we propose a flexible method for training deep latent variable models of discrete structures. Our approach is based on the recently-proposed Wasserstein autoencoder (WAE) which formalizes the adversarial autoencoder (AAE) as an optimal transport problem. We first extend this framework to model discrete sequences, and then further explore different learned priors targeting a controllable representation. This adversarially regularized autoencoder (ARAE) allows us to generate natural textual outputs as well as perform manipulations in the latent space to induce change in the output space. Finally we show that the latent representation can be trained to perform unaligned textual style transfer, giving improvements both in automatic/human evaluation compared to existing methods.
Proximal Backpropagation
Venue: arXiv cs.LG 2018
Year: 2018

We propose proximal backpropagation (ProxProp) as a novel algorithm that takes implicit instead of explicit gradient steps to update the network parameters during neural network training. Our algorithm is motivated by the step size limitation of explicit gradient descent, which poses an impediment for optimization. ProxProp is developed from a general point of view on the backpropagation algorithm, currently the most common technique to train neural networks via stochastic gradient descent and variants thereof. Specifically, we show that backpropagation of a prediction error is equivalent to sequential gradient descent steps on a quadratic penalty energy, which comprises the network activations as variables of the optimization. We further analyze theoretical properties of ProxProp and in particular prove that the algorithm yields a descent direction in parameter space and can therefore be combined with a wide variety of convergent algorithms. Finally, we devise an efficient numerical implementation that integrates well with popular deep learning frameworks. We conclude by demonstrating promising numerical results and show that ProxProp can be effectively combined with common first order optimizers such as Adam.