OpenRaiser/Intern-Atlas huggingface dataset:
Computing the Unique Information
Venue: arXiv cs.IT 2018
Year: 2018

Given a pair of predictor variables and a response variable, how much information do the predictors have about the response, and how is this information distributed between unique, redundant, and synergistic components? Recent work has proposed to quantify the unique component of the decomposition as the minimum value of the conditional mutual information over a constrained set of information channels. We present an efficient iterative divergence minimization algorithm to solve this optimization problem with convergence guarantees and evaluate its performance against other techniques.
On self-dual negacirculant codes of index two and four
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study a special kind of factorization of $x^n+1$ over $\mathbb{F}_q, $ with $q$ a prime power $\equiv 3~({\rm mod}~4)$ when $n=2p,$ with $p\equiv 3~({\rm mod}~4)$ and $p$ is a prime. Given such a $q$ infinitely many such $p$'s exist that admit $q$ as a primitive root by the Artin conjecture in arithmetic progressions. This number theory conjecture is known to hold under GRH. We study the double (resp. four)-negacirculant codes over finite fields $\mathbb{F}_q, $ of co-index such $n$'s, including the exact enumeration of the self-dual subclass, and a modified Varshamov-Gilbert bound on the relative distance of the codes it contains.
On Encoding Temporal Evolution for Real-time Action Prediction
Venue: arXiv cs.CV 2018
Year: 2018

Anticipating future actions is a key component of intelligence, specifically when it applies to real-time systems, such as robots or autonomous cars. While recent works have addressed prediction of raw RGB pixel values, we focus on anticipating the motion evolution in future video frames. To this end, we construct dynamic images (DIs) by summarising moving pixels through a sequence of future frames. We train a convolutional LSTMs to predict the next DIs based on an unsupervised learning process, and then recognise the activity associated with the predicted DI. We demonstrate the effectiveness of our approach on 3 benchmark action datasets showing that despite running on videos with complex activities, our approach is able to anticipate the next human action with high accuracy and obtain better results than the state-of-the-art methods.
Private Information Retrieval from Transversal Designs
Venue: arXiv cs.IT 2018
Year: 2018

Private information retrieval (PIR) protocols allow a user to retrieve entries of a database without revealing the index of the desired item. Information-theoretical privacy can be achieved by the use of several servers and specific retrieval algorithms. Most of known PIR protocols focus on decreasing the number of bits exchanged between the client and the server(s) during the retrieval process. On another side, Fazeli et. al. introduced so-called PIR codes in order to reduce the storage overhead on the servers. However, only a few works address the issue of the computation complexity of the servers. In this paper, we show that a specific encoding of the database provides PIR protocols with reasonable communication complexity, low storage overhead and optimal computational complexity for the servers. This encoding is based on incidence matrices of transversal designs, from which a natural and efficient recovering algorithm is derived. We also present instances of our construction, making use of finite geometries and orthogonal arrays, and we finally give a generalisation of our main construction for resisting collusions of servers.
Multi-task Learning with Gradient Guided Policy Specialization
Venue: arXiv cs.RO 2018
Year: 2018

We present a method for efficient learning of control policies for multiple related robotic motor skills. Our approach consists of two stages, joint training and specialization training. During the joint training stage, a neural network policy is trained with minimal information to disambiguate the motor skills. This forces the policy to learn a common representation of the different tasks. Then, during the specialization training stage we selectively split the weights of the policy based on a per-weight metric that measures the disagreement among the multiple tasks. By splitting part of the control policy, it can be further trained to specialize to each task. To update the control policy during learning, we use Trust Region Policy Optimization with Generalized Advantage Function (TRPOGAE). We propose a modification to the gradient update stage of TRPO to better accommodate multi-task learning scenarios. We evaluate our approach on three continuous motor skill learning problems in simulation: 1) a locomotion task where three single legged robots with considerable difference in shape and size are trained to hop forward, 2) a manipulation task where three robot manipulators with different sizes and joint types are trained to reach different locations in 3D space, and 3) locomotion of a two-legged robot, whose range of motion of one leg is constrained in different ways. We compare our training method to three baselines. The first baseline uses only joint training for the policy, the second trains independent policies for each task, and the last randomly selects weights to split. We show that our approach learns more efficiently than each of the baseline methods.
Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems
Venue: arXiv cs.AI 2018
Year: 2018

Much research in artificial intelligence is concerned with the development of autonomous agents that can interact effectively with other agents. An important aspect of such agents is the ability to reason about the behaviours of other agents, by constructing models which make predictions about various properties of interest (such as actions, goals, beliefs) of the modelled agents. A variety of modelling approaches now exist which vary widely in their methodology and underlying assumptions, catering to the needs of the different sub-communities within which they were developed and reflecting the different practical uses for which they are intended. The purpose of the present article is to provide a comprehensive survey of the salient modelling methods which can be found in the literature. The article concludes with a discussion of open problems which may form the basis for fruitful future research.
Learning Context-Sensitive Convolutional Filters for Text Processing
Venue: arXiv cs.CL 2018
Year: 2018

Convolutional neural networks (CNNs) have recently emerged as a popular building block for natural language processing (NLP). Despite their success, most existing CNN models employed in NLP share the same learned (and static) set of filters for all input sentences. In this paper, we consider an approach of using a small meta network to learn context-sensitive convolutional filters for text processing. The role of meta network is to abstract the contextual information of a sentence or document into a set of input-aware filters. We further generalize this framework to model sentence pairs, where a bidirectional filter generation mechanism is introduced to encapsulate co-dependent sentence representations. In our benchmarks on four different tasks, including ontology classification, sentiment analysis, answer sentence selection, and paraphrase identification, our proposed model, a modified CNN with context-sensitive filters, consistently outperforms the standard CNN and attention-based CNN baselines. By visualizing the learned context-sensitive filters, we further validate and rationalize the effectiveness of proposed framework.
Multi-view Registration Based on Weighted Low Rank and Sparse Matrix Decomposition of Motions
Venue: arXiv cs.CV 2018
Year: 2018

Recently, the low rank and sparse (LRS) matrix decomposition has been introduced as an effective mean to solve the multi-view registration. It views each available relative motion as a block element to reconstruct one matrix so as to approximate the low rank matrix, where global motions can be recovered for multi-view registration. However, this approach is sensitive to the sparsity of the reconstructed matrix and it treats all block elements equally in spite of their varied reliability. Therefore, this paper proposes an effective approach for multi-view registration by the weighted LRS decomposition. Based on the anti-symmetry property of relative motions, it firstly proposes a completion strategy to reduce the sparsity of the reconstructed matrix. The reduced sparsity of reconstructed matrix can improve the robustness of LRS decomposition. Then, it proposes the weighted LRS decomposition, where each block element is assigned with one estimated weight to denote its reliability. By introducing the weight, more accurate registration results can be recovered from the estimated low rank matrix with good efficiency. Experimental results tested on public data sets illustrate the superiority of the proposed approach over the state-of-the-art approaches on robustness, accuracy, and efficiency.
Detection of Malicious and Low Throughput Data Exfiltration Over the DNS Protocol
Venue: arXiv cs.CR 2018
Year: 2018

In the presence of security countermeasures, a malware designed for data exfiltration must do so using a covert channel to achieve its goal. Among existing covert channels stands the domain name system (DNS) protocol. Although the detection of covert channels over the DNS has been thoroughly studied in the last decade, previous research dealt with a specific subclass of covert channels, namely DNS tunneling. While the importance of tunneling detection is not undermined, an entire class of low throughput DNS exfiltration malware remained overlooked. The goal of this study is to propose a method for detecting both tunneling and low-throughput data exfiltration over the DNS. Towards this end, we propose a solution composed of a supervised feature selection method, and an interchangeable, and adjustable anomaly detection model trained on legitimate traffic. In the first step, a one-class classifier is applied for detecting domain-specific traffic that does not conform with the normal behavior. Then, in the second step, in order to reduce the false positive rate resulting from the attempt to detect the low-throughput data exfiltration we apply a rule-based filter that filters data exchange over DNS used by legitimate services. Our solution was evaluated on a medium-scale recursive DNS server logs, and involved more than 75,000 legitimate uses and almost 2,000 attacks. Evaluation results shows that while DNS tunneling is covered with at least 99% recall rate and less than 0.01% false positive rate, the detection of low throughput exfiltration is more difficult. While not preventing it completely, our solution limits a malware attempting to avoid detection with at most a 1kb/h of payload under the limitations of the DNS syntax (equivalent to five credit cards details, or ten user credentials per hour) which reduces the effectiveness of the attack.
Uncertainty in Multi-Commodity Routing Networks: When does it help?
Venue: arXiv cs.GT 2018
Year: 2018

We study the equilibrium behavior in a multi-commodity selfish routing game with many types of uncertain users where each user over- or under-estimates their congestion costs by a multiplicative factor. Surprisingly, we find that uncertainties in different directions have qualitatively distinct impacts on equilibria. Namely, contrary to the usual notion that uncertainty increases inefficiencies, network congestion actually decreases when users over-estimate their costs. On the other hand, under-estimation of costs leads to increased congestion. We apply these results to urban transportation networks, where drivers have different estimates about the cost of congestion. In light of the dynamic pricing policies aimed at tackling congestion, our results indicate that users' perception of these prices can significantly impact the policy's efficacy, and "caution in the face of uncertainty" leads to favorable network conditions.
Multimodal Image Super-resolution via Joint Sparse Representations induced by Coupled Dictionaries
Venue: arXiv cs.CV 2018
Year: 2018

Real-world data processing problems often involve various image modalities associated with a certain scene, including RGB images, infrared images or multi-spectral images. The fact that different image modalities often share certain attributes, such as certain edges, textures and other structure primitives, represents an opportunity to enhance various image processing tasks. This paper proposes a new approach to construct a high-resolution (HR) version of a low-resolution (LR) image given another HR image modality as reference, based on joint sparse representations induced by coupled dictionaries. Our approach, which captures the similarities and disparities between different image modalities in a learned sparse feature domain in \emph{lieu} of the original image domain, consists of two phases. The coupled dictionary learning phase is used to learn a set of dictionaries that couple different image modalities in the sparse feature domain given a set of training data. In turn, the coupled super-resolution phase leverages such coupled dictionaries to construct a HR version of the LR target image given another related image modality. One of the merits of our sparsity-driven approach relates to the fact that it overcomes drawbacks such as the texture copying artifacts commonly resulting from inconsistency between the guidance and target images. Experiments on real multimodal images demonstrate that incorporating appropriate guidance information via joint sparse representation induced by coupled dictionary learning brings notable benefits in the super-resolution task with respect to the state-of-the-art. Of particular relevance, the proposed approach also demonstrates better robustness than competing deep-learning-based methods in the presence of noise.
Image similarity using Deep CNN and Curriculum Learning
Venue: arXiv cs.CV 2018
Year: 2018

Image similarity involves fetching similar looking images given a reference image. Our solution called SimNet, is a deep siamese network which is trained on pairs of positive and negative images using a novel online pair mining strategy inspired by Curriculum learning. We also created a multi-scale CNN, where the final image embedding is a joint representation of top as well as lower layer embedding's. We go on to show that this multi-scale siamese network is better at capturing fine grained image similarities than traditional CNN's.
Faster Interpolation Algorithms for Sparse Multivariate Polynomials Given by Straight-Line Programs\
Venue: arXiv cs.SC 2018
Year: 2018

In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let $f$ be an $n$-variate polynomial given by a straight-line program, which has a degree bound $D$ and a term bound $T$. Our deterministic algorithm is quadratic in $n,T$ and cubic in $\log D$ in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in $nT$ in the Soft-Oh sense. Since $nT$ is a factor of the size of $f$, our Monte Carlo algorithms are optimal in $n$ and $T$ in the Soft-Oh sense.
Exact Camera Location Recovery by Least Unsquared Deviations
Venue: arXiv cs.CV 2018
Year: 2018

We establish exact recovery for the Least Unsquared Deviations (LUD) algorithm of Ozyesil and Singer. More precisely, we show that for sufficiently many cameras with given corrupted pairwise directions, where both camera locations and pairwise directions are generated by a special probabilistic model, the LUD algorithm exactly recovers the camera locations with high probability. A similar exact recovery guarantee was established for the ShapeFit algorithm by Hand, Lee and Voroninski, but with typically less corruption.
PPLS/D: Parallel Pareto Local Search based on Decomposition
Venue: arXiv cs.DC 2018
Year: 2018

Pareto Local Search (PLS) is a basic building block in many metaheuristics for Multiobjective Combinatorial Optimization Problem (MCOP). In this paper, an enhanced PLS variant called Parallel Pareto Local Search based on Decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known Two Phase Pareto Local Search (2PPLS) in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective Unconstrained Binary Quadratic Programming problems (mUBQPs) and the multiobjective Traveling Salesman Problems (mTSPs) with at most four objectives. The experimental results show that, no matter whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.
Communication Complexity of Cake Cutting
Venue: arXiv cs.GT 2018
Year: 2018

We study classic cake-cutting problems, but in discrete models rather than using infinite-precision real values, specifically, focusing on their communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-logarithmic total communication), and "hard". Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.
X-View: Graph-Based Semantic Multi-View Localization
Venue: arXiv cs.RO 2018
Year: 2018

Global registration of multi-view robot data is a challenging task. Appearance-based global localization approaches often fail under drastic view-point changes, as representations have limited view-point invariance. This work is based on the idea that human-made environments contain rich semantics which can be used to disambiguate global localization. Here, we present X-View, a Multi-View Semantic Global Localization system. X-View leverages semantic graph descriptor matching for global localization, enabling localization under drastically different view-points. While the approach is general in terms of the semantic input data, we present and evaluate an implementation on visual data. We demonstrate the system in experiments on the publicly available SYNTHIA dataset, on a realistic urban dataset recorded with a simulator, and on real-world StreetView data. Our findings show that X-View is able to globally localize aerial-to-ground, and ground-to-ground robot data of drastically different view-points. Our approach achieves an accuracy of up to 85 % on global localizations in the multi-view case, while the benchmarked baseline appearance-based methods reach up to 75 %.
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-off Algorithms
Venue: arXiv cs.CG 2018
Year: 2018

We are given a read-only memory for input and a write-only stream for output. For a positive integer parameter s, an s-workspace algorithm is an algorithm using only $O(s)$ words of workspace in addition to the memory for input. In this paper, we present an $O(n^2/s)$-time $s$-workspace algorithm for subdividing a simple polygon into $O(\min\{n/s,s\})$ subpolygons of complexity $O(\max\{n/s,s\})$. As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately: (1) computing the shortest path between two points inside a simple $n$-gon, (2) computing the shortest path tree from a point inside a simple $n$-gon, (3) computing a triangulation of a simple $n$-gon. In addition, we improve the algorithm for the second problem even further.
Recovering sparse graphs
Venue: arXiv cs.DM 2018
Year: 2018

We construct a fixed parameter algorithm parameterized by d and k that takes as an input a graph G' obtained from a d-degenerate graph G by complementing on at most k arbitrary subsets of the vertex set of G and outputs a graph H such that G and H agree on all but f(d,k) vertices. Our work is motivated by the first order model checking in graph classes that are first order interpretable in classes of sparse graphs. We derive as a corollary that if G_0 is a graph class with bounded expansion, then the first order model checking is fixed parameter tractable in the class of all graphs that can obtained from a graph G from G_0 by complementing on at most k arbitrary subsets of the vertex set of G; this implies an earlier result that the first order model checking is fixed parameter tractable in graph classes interpretable in classes of graphs with bounded maximum degree.
Provably Minimally-Distorted Adversarial Examples
Venue: arXiv cs.LG 2018
Year: 2018

The ability to deploy neural networks in real-world, safety-critical systems is severely limited by the presence of adversarial examples: slightly perturbed inputs that are misclassified by the network. In recent years, several techniques have been proposed for increasing robustness to adversarial examples --- and yet most of these have been quickly shown to be vulnerable to future attacks. For example, over half of the defenses proposed by papers accepted at ICLR 2018 have already been broken. We propose to address this difficulty through formal verification techniques. We show how to construct provably minimally distorted adversarial examples: given an arbitrary neural network and input sample, we can construct adversarial examples which we prove are of minimal distortion. Using this approach, we demonstrate that one of the recent ICLR defense proposals, adversarial retraining, provably succeeds at increasing the distortion required to construct adversarial examples by a factor of 4.2.
Enabling Quality Control for Entity Resolution: A Human and Machine Cooperation Framework
Venue: arXiv cs.DB 2018
Year: 2018

Even though many machine algorithms have been proposed for entity resolution, it remains very challenging to find a solution with quality guarantees. In this paper, we propose a novel HUman and Machine cOoperation (HUMO) framework for entity resolution (ER), which divides an ER workload between the machine and the human. HUMO enables a mechanism for quality control that can flexibly enforce both precision and recall levels. We introduce the optimization problem of HUMO, minimizing human cost given a quality requirement, and then present three optimization approaches: a conservative baseline one purely based on the monotonicity assumption of precision, a more aggressive one based on sampling and a hybrid one that can take advantage of the strengths of both previous approaches. Finally, we demonstrate by extensive experiments on real and synthetic datasets that HUMO can achieve high-quality results with reasonable return on investment (ROI) in terms of human cost, and it performs considerably better than the state-of-the-art alternatives in quality control.