OpenRaiser/Intern-Atlas huggingface dataset:
A Reinforcement-Learning Approach to Proactive Caching in Wireless Networks
Venue: arXiv cs.SY 2017
Year: 2017

We consider a mobile user accessing contents in a dynamic environment, where new contents are generated over time (by the user's contacts), and remain relevant to the user for random lifetimes. The user, equipped with a finite-capacity cache memory, randomly accesses the system, and requests all the relevant contents at the time of access. The system incurs an energy cost associated with the number of contents downloaded and the channel quality at that time. Assuming causal knowledge of the channel quality, the content profile, and the user-access behavior, we model the proactive caching problem as a Markov decision process with the goal of minimizing the long-term average energy cost. We first prove the optimality of a threshold-based proactive caching scheme, which dynamically caches or removes appropriate contents from the memory, prior to being requested by the user, depending on the channel state. The optimal threshold values depend on the system state, and hence, are computationally intractable. Therefore, we propose parametric representations for the threshold values, and use reinforcement-learning algorithms to find near-optimal parametrizations. We demonstrate through simulations that the proposed schemes significantly outperform classical reactive downloading, and perform very close to a genie-aided lower bound.
A Collection of Lower Bounds for Online Matching on the Line
Venue: arXiv cs.DS 2017
Year: 2017

In the online matching on the line problem, the task is to match a set of requests $R$ online to a given set of servers $S$. The distance metric between any two points in $R\,\cup\, S$ is a line metric and the objective for the online algorithm is to minimize the sum of distances between matched server-request pairs. This problem is well-studied and - despite recent improvements - there is still a large gap between the best known lower and upper bounds: The best known deterministic algorithm for the problem is $O(\log^2n)$-competitive, while the best known deterministic lower bound is $9.001$. The lower and upper bounds for randomized algorithms are $4.5$ and $O(\log n)$ respectively. We prove that any deterministic online algorithm which in each round: $(i)$ bases the matching decision only on information local to the current request, and $(ii)$ is symmetric (in the sense that the decision corresponding to the mirror image of some instance $I$ is the mirror image of the decision corresponding to instance $I$), must be $Ω(\log n)$-competitive. We then extend the result by showing that it also holds when relaxing the symmetry property so that the algorithm might prefer one side over the other, but only up to some degree. This proves a barrier of $Ω(\log n)$ on the competitive ratio for a large class of "natural" algorithms. This class includes all deterministic online algorithms found in the literature so far. Furthermore, we show that our result can be extended to randomized algorithms that locally induce a symmetric distribution over the chosen servers. The $Ω(\log n)$-barrier on the competitive ratio holds for this class of algorithms as well.
Real-time 3D Reconstruction on Construction Site using Visual SLAM and UAV
Venue: arXiv cs.RO 2017
Year: 2017

3D reconstruction can be used as a platform to monitor the performance of activities on construction site, such as construction progress monitoring, structure inspection and post-disaster rescue. Comparing to other sensors, RGB image has the advantages of low-cost, texture rich and easy to implement that has been used as the primary method for 3D reconstruction in construction industry. However, the image-based 3D reconstruction always requires extended time to acquire and/or to process the image data, which limits its application on time critical projects. Recent progress in Visual Simultaneous Localization and Mapping (SLAM) make it possible to reconstruct a 3D map of construction site in real-time. Integrated with Unmanned Aerial Vehicle (UAV), the obstacles areas that are inaccessible for the ground equipment can also be sensed. Despite these advantages of visual SLAM and UAV, until now, such technique has not been fully investigated on construction site. Therefore, the objective of this research is to present a pilot study of using visual SLAM and UAV for real-time construction site reconstruction. The system architecture and the experimental setup are introduced, and the preliminary results and the potential applications using Visual SLAM and UAV on construction site are discussed.
Distributed Massive MIMO Channel Estimation and Channel Database Assistance
Venue: arXiv cs.IT 2017
Year: 2017

Due to the low per-antenna SNR and high signaling overhead, channel estimation is a major bottleneck in Massive MIMO systems. Spatial constraints can improve estimation performance by exploiting sparsity. Solutions exist for far field - beam domain channel estimation based on angle of arrival estimation. However, there is no equivalent solution for near field and distributed MIMO spatial channel estimation. We present a solution- source domain channel estimation- that is based on source location estimation. We extend this to employ a "Channel Database" incorporating information about the physical scattering environment into channel estimation. We present methods for generation, storage and usage of the Channel Database to assist localization and communication.
On Wasserstein Reinforcement Learning and the Fokker-Planck equation
Venue: arXiv cs.LG 2017
Year: 2017

Policy gradients methods often achieve better performance when the change in policy is limited to a small Kullback-Leibler divergence. We derive policy gradients where the change in policy is limited to a small Wasserstein distance (or trust region). This is done in the discrete and continuous multi-armed bandit settings with entropy regularisation. We show that in the small steps limit with respect to the Wasserstein distance $W_2$, policy dynamics are governed by the Fokker-Planck (heat) equation, following the Jordan-Kinderlehrer-Otto result. This means that policies undergo diffusion and advection, concentrating near actions with high reward. This helps elucidate the nature of convergence in the probability matching setup, and provides justification for empirical practices such as Gaussian policy priors and additive gradient noise.
Discovery of Shifting Patterns in Sequence Classification
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we investigate the multi-variate sequence classification problem from a multi-instance learning perspective. Real-world sequential data commonly show discriminative patterns only at specific time periods. For instance, we can identify a cropland during its growing season, but it looks similar to a barren land after harvest or before planting. Besides, even within the same class, the discriminative patterns can appear in different periods of sequential data. Due to such property, these discriminative patterns are also referred to as shifting patterns. The shifting patterns in sequential data severely degrade the performance of traditional classification methods without sufficient training data. We propose a novel sequence classification method by automatically mining shifting patterns from multi-variate sequence. The method employs a multi-instance learning approach to detect shifting patterns while also modeling temporal relationships within each multi-instance bag by an LSTM model to further improve the classification performance. We extensively evaluate our method on two real-world applications - cropland mapping and affective state recognition. The experiments demonstrate the superiority of our proposed method in sequence classification performance and in detecting discriminative shifting patterns.
Attentive Memory Networks: Efficient Machine Reading for Conversational Search
Venue: arXiv cs.CL 2017
Year: 2017

Recent advances in conversational systems have changed the search paradigm. Traditionally, a user poses a query to a search engine that returns an answer based on its index, possibly leveraging external knowledge bases and conditioning the response on earlier interactions in the search session. In a natural conversation, there is an additional source of information to take into account: utterances produced earlier in a conversation can also be referred to and a conversational IR system has to keep track of information conveyed by the user during the conversation, even if it is implicit. We argue that the process of building a representation of the conversation can be framed as a machine reading task, where an automated system is presented with a number of statements about which it should answer questions. The questions should be answered solely by referring to the statements provided, without consulting external knowledge. The time is right for the information retrieval community to embrace this task, both as a stand-alone task and integrated in a broader conversational search setting. In this paper, we focus on machine reading as a stand-alone task and present the Attentive Memory Network (AMN), an end-to-end trainable machine reading algorithm. Its key contribution is in efficiency, achieved by having an hierarchical input encoder, iterating over the input only once. Speed is an important requirement in the setting of conversational search, as gaps between conversational turns have a detrimental effect on naturalness. On 20 datasets commonly used for evaluating machine reading algorithms we show that the AMN achieves performance comparable to the state-of-the-art models, while using considerably fewer computations.
Fusing Multifaceted Transaction Data for User Modeling and Demographic Prediction
Venue: arXiv cs.SI 2017
Year: 2017

Inferring user characteristics such as demographic attributes is of the utmost importance in many user-centric applications. Demographic data is an enabler of personalization, identity security, and other applications. Despite that, this data is sensitive and often hard to obtain. Previous work has shown that purchase history can be used for multi-task prediction of many demographic fields such as gender and marital status. Here we present an embedding based method to integrate multifaceted sequences of transaction data, together with auxiliary relational tables, for better user modeling and demographic prediction.
Further limitations of the known approaches for matrix multiplication
Venue: arXiv cs.CC 2017
Year: 2017

We consider the techniques behind the current best algorithms for matrix multiplication. Our results are threefold. (1) We provide a unifying framework, showing that all known matrix multiplication running times since 1986 can be achieved from a single very natural tensor - the structural tensor $T_q$ of addition modulo an integer $q$. (2) We show that if one applies a generalization of the known techniques (arbitrary zeroing out of tensor powers to obtain independent matrix products in order to use the asymptotic sum inequality of Schönhage) to an arbitrary monomial degeneration of $T_q$, then there is an explicit lower bound, depending on $q$, on the bound on the matrix multiplication exponent $ω$ that one can achieve. We also show upper bounds on the value $α$ that one can achieve, where $α$ is such that $n\times n^α\times n$ matrix multiplication can be computed in $n^{2+o(1)}$ time. (3) We show that our lower bound on $ω$ approaches $2$ as $q$ goes to infinity. This suggests a promising approach to improving the bound on $ω$: for variable $q$, find a monomial degeneration of $T_q$ which, using the known techniques, produces an upper bound on $ω$ as a function of $q$. Then, take $q$ to infinity. It is not ruled out, and hence possible, that one can obtain $ω=2$ in this way.
Blind High Dynamic Range Quality estimation by disentangling perceptual and noise features in images
Venue: arXiv cs.MM 2017
Year: 2017

Assessing the visual quality of High Dynamic Range (HDR) images is an unexplored and an interesting research topic that has become relevant with the current boom in HDR technology. We propose a new convolutional neural network based model for No reference image quality assessment(NR-IQA) on HDR data. This model predicts the amount and location of noise, perceptual influence of image pixels on the noise, and the perceived quality, of a distorted image without any reference image. The proposed model extracts numerical values corresponding to the noise present in any given distorted image, and the perceptual effects exhibited by a human eye when presented with the same. These two measures are extracted separately yet sequentially and combined in a mixing function to compute the quality of the distorted image perceived by a human eye. Our training process derives the the component that computes perceptual effects from a real world image quality dataset, rather than using results of psycovisual experiments. With the proposed model, we demonstrate state of the art performance for HDR NR-IQA and our results show performance similar to HDR Full Reference Image Quality Assessment algorithms (FR-IQA).
Learning Sight from Sound: Ambient Sound Provides Supervision for Visual Learning
Venue: arXiv cs.CV 2017
Year: 2017

The sound of crashing waves, the roar of fast-moving cars -- sound conveys important information about the objects in our surroundings. In this work, we show that ambient sounds can be used as a supervisory signal for learning visual models. To demonstrate this, we train a convolutional neural network to predict a statistical summary of the sound associated with a video frame. We show that, through this process, the network learns a representation that conveys information about objects and scenes. We evaluate this representation on several recognition tasks, finding that its performance is comparable to that of other state-of-the-art unsupervised learning methods. Finally, we show through visualizations that the network learns units that are selective to objects that are often associated with characteristic sounds. This paper extends an earlier conference paper, Owens et al. 2016, with additional experiments and discussion.
Hierarchical and Interpretable Skill Acquisition in Multi-task Reinforcement Learning
Venue: arXiv cs.AI 2017
Year: 2017

Learning policies for complex tasks that require multiple different skills is a major challenge in reinforcement learning (RL). It is also a requirement for its deployment in real-world scenarios. This paper proposes a novel framework for efficient multi-task reinforcement learning. Our framework trains agents to employ hierarchical policies that decide when to use a previously learned policy and when to learn a new skill. This enables agents to continually acquire new skills during different stages of training. Each learned task corresponds to a human language description. Because agents can only access previously learned skills through these descriptions, the agent can always provide a human-interpretable description of its choices. In order to help the agent learn the complex temporal dependencies necessary for the hierarchical policy, we provide it with a stochastic temporal grammar that modulates when to rely on previously learned skills and when to execute new skills. We validate our approach on Minecraft games designed to explicitly test the ability to reuse previously learned skills while simultaneously learning new skills.
A Flexible Approach to Automated RNN Architecture Generation
Venue: arXiv cs.CL 2017
Year: 2017

The process of designing neural architectures requires expert knowledge and extensive trial and error. While automated architecture search may simplify these requirements, the recurrent neural network (RNN) architectures generated by existing methods are limited in both flexibility and components. We propose a domain-specific language (DSL) for use in automated architecture search which can produce novel RNNs of arbitrary depth and width. The DSL is flexible enough to define standard architectures such as the Gated Recurrent Unit and Long Short Term Memory and allows the introduction of non-standard RNN components such as trigonometric curves and layer normalization. Using two different candidate generation techniques, random search with a ranking function and reinforcement learning, we explore the novel architectures produced by the RNN DSL for language modeling and machine translation domains. The resulting architectures do not follow human intuition yet perform well on their targeted tasks, suggesting the space of usable RNN architectures is far larger than previously assumed.
Lost in Time: Temporal Analytics for Long-Term Video Surveillance
Venue: arXiv cs.CV 2017
Year: 2017

Video surveillance is a well researched area of study with substantial work done in the aspects of object detection, tracking and behavior analysis. With the abundance of video data captured over a long period of time, we can understand patterns in human behavior and scene dynamics through data-driven temporal analytics. In this work, we propose two schemes to perform descriptive and predictive analytics on long-term video surveillance data. We generate heatmap and footmap visualizations to describe spatially pooled trajectory patterns with respect to time and location. We also present two approaches for anomaly prediction at the day-level granularity: a trajectory-based statistical approach, and a time-series based approach. Experimentation with one year data from a single camera demonstrates the ability to uncover interesting insights about the scene and to predict anomalies reasonably well.
CameraTransform: a Scientific Python Package for Perspective Camera Corrections
Venue: arXiv cs.MS 2017
Year: 2017

Scientific applications often require an exact reconstruction of object positions and distances from digital images. Therefore, the images need to be corrected for perspective distortions. We present \textit{CameraTransform}, a python package that performs a perspective image correction whereby the height, tilt/roll angle and heading of the camera can be automatically obtained from the images if additional information such as GPS coordinates or object sizes are provided. We present examples of images of penguin colonies that are recorded with stationary cameras and from a helicopter.
Accurate 3D Reconstruction of Dynamic Scenes from Monocular Image Sequences with Severe Occlusions
Venue: arXiv cs.CV 2017
Year: 2017

The paper introduces an accurate solution to dense orthographic Non-Rigid Structure from Motion (NRSfM) in scenarios with severe occlusions or, likewise, inaccurate correspondences. We integrate a shape prior term into variational optimisation framework. It allows to penalize irregularities of the time-varying structure on the per-pixel level if correspondence quality indicator such as an occlusion tensor is available. We make a realistic assumption that several non-occluded views of the scene are sufficient to estimate an initial shape prior, though the entire observed scene may exhibit non-rigid deformations. Experiments on synthetic and real image data show that the proposed framework significantly outperforms state of the art methods for correspondence establishment in combination with the state of the art NRSfM methods. Together with the profound insights into optimisation methods, implementation details for heterogeneous platforms are provided.
An Ensemble Model with Ranking for Social Dialogue
Venue: arXiv cs.CL 2017
Year: 2017

Open-domain social dialogue is one of the long-standing goals of Artificial Intelligence. This year, the Amazon Alexa Prize challenge was announced for the first time, where real customers get to rate systems developed by leading universities worldwide. The aim of the challenge is to converse "coherently and engagingly with humans on popular topics for 20 minutes". We describe our Alexa Prize system (called 'Alana') consisting of an ensemble of bots, combining rule-based and machine learning systems, and using a contextual ranking mechanism to choose a system response. The ranker was trained on real user feedback received during the competition, where we address the problem of how to train on the noisy and sparse feedback obtained during the competition.
Improving Generalization Performance by Switching from Adam to SGD
Venue: arXiv cs.LG 2017
Year: 2017

Despite superior training outcomes, adaptive optimization methods such as Adam, Adagrad or RMSprop have been found to generalize poorly compared to Stochastic gradient descent (SGD). These methods tend to perform well in the initial portion of training but are outperformed by SGD at later stages of training. We investigate a hybrid strategy that begins training with an adaptive method and switches to SGD when appropriate. Concretely, we propose SWATS, a simple strategy which switches from Adam to SGD when a triggering condition is satisfied. The condition we propose relates to the projection of Adam steps on the gradient subspace. By design, the monitoring process for this condition adds very little overhead and does not increase the number of hyperparameters in the optimizer. We report experiments on several standard benchmarks such as: ResNet, SENet, DenseNet and PyramidNet for the CIFAR-10 and CIFAR-100 data sets, ResNet on the tiny-ImageNet data set and language modeling with recurrent networks on the PTB and WT2 data sets. The results show that our strategy is capable of closing the generalization gap between SGD and Adam on a majority of the tasks.
PKC-PC: A Variant of the McEliece Public Key Cryptosystem based on Polar Codes
Venue: arXiv cs.CR 2017
Year: 2017

Polar codes are novel and efficient error correcting codes with low encoding and decoding complexities. These codes have a channel dependent generator matrix which is determined by the code dimension, code length and transmission channel parameters. This paper studies a variant of the McEliece public key cryptosystem based on polar codes, called "PKC-PC". Due to the fact that the structure of polar codes' generator matrix depends on the parameters of channel, we used an efficient approach to conceal their generator matrix. Then, by the help of the characteristics of polar codes and also introducing an efficient approach, we reduced the public and private key sizes of the PKC-PC and increased its information rate compared to the McEliece cryptosystem. It was shown that polar codes are able to yield an increased security level against conventional attacks and possible vulnerabilities on the code-based public key cryptosystems. Moreover, it is indicated that the security of the PKC-PC is reduced to solve NP-complete problems. Compared to other post-quantum public key schemes, we believe that the PKC-PC is a promising candidate for NIST post-quantum crypto standardization.