OpenRaiser/Intern-Atlas huggingface dataset:
Mitigating Evasion Attacks to Deep Neural Networks via Region-based Classification
Venue: arXiv cs.CR 2019
Year: 2019

Deep neural networks (DNNs) have transformed several artificial intelligence research areas including computer vision, speech recognition, and natural language processing. However, recent studies demonstrated that DNNs are vulnerable to adversarial manipulations at testing time. Specifically, suppose we have a testing example, whose label can be correctly predicted by a DNN classifier. An attacker can add a small carefully crafted noise to the testing example such that the DNN classifier predicts an incorrect label, where the crafted testing example is called adversarial example. Such attacks are called evasion attacks. Evasion attacks are one of the biggest challenges for deploying DNNs in safety and security critical applications such as self-driving cars. In this work, we develop new methods to defend against evasion attacks. Our key observation is that adversarial examples are close to the classification boundary. Therefore, we propose region-based classification to be robust to adversarial examples. For a benign/adversarial testing example, we ensemble information in a hypercube centered at the example to predict its label. In contrast, traditional classifiers are point-based classification, i.e., given a testing example, the classifier predicts its label based on the testing example alone. Our evaluation results on MNIST and CIFAR-10 datasets demonstrate that our region-based classification can significantly mitigate evasion attacks without sacrificing classification accuracy on benign examples. Specifically, our region-based classification achieves the same classification accuracy on testing benign examples as point-based classification, but our region-based classification is significantly more robust than point-based classification to various evasion attacks.
Widths of regular and context-free languages
Venue: arXiv cs.FL 2019
Year: 2019

Given a partially-ordered finite alphabet $Σ$ and a language $L\subseteq Σ^*$, how large can an antichain in $L$ be (where $L$ is given the lexicographic ordering)? More precisely, since $L$ will in general be infinite, we should ask about the rate of growth of maximum antichains consisting of words of length $n$. This fundamental property of partial orders is known as the width, and in a companion work we show that the problem of computing the information leakage permitted by a deterministic interactive system modeled as a finite-state transducer can be reduced to the problem of computing the width of a certain regular language. In this paper, we show that if $L$ is regular then there is a dichotomy between polynomial and exponential antichain growth. We give a polynomial-time algorithm to distinguish the two cases, and to compute the order of polynomial growth, with the language specified as an NFA. For context-free languages we show that there is a similar dichotomy, but now the problem of distinguishing the two cases is undecidable. Finally, we generalise the lexicographic order to tree languages, and show that for regular tree languages there is a trichotomy between polynomial, exponential and doubly exponential antichain growth.
Stochastic Nonconvex Optimization with Large Minibatches
Venue: arXiv cs.LG 2019
Year: 2019

We study stochastic optimization of nonconvex loss functions, which are typical objectives for training neural networks. We propose stochastic approximation algorithms which optimize a series of regularized, nonlinearized losses on large minibatches of samples, using only first-order gradient information. Our algorithms provably converge to an approximate critical point of the expected objective with faster rates than minibatch stochastic gradient descent, and facilitate better parallelization by allowing larger minibatches.
Signature Verification Approach using Fusion of Hybrid Texture Features
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, a writer-dependent signature verification method is proposed. Two different types of texture features, namely Wavelet and Local Quantized Patterns (LQP) features, are employed to extract two kinds of transform and statistical based information from signature images. For each writer two separate one-class support vector machines (SVMs) corresponding to each set of LQP and Wavelet features are trained to obtain two different authenticity scores for a given signature. Finally, a score level classifier fusion method is used to integrate the scores obtained from the two one-class SVMs to achieve the verification score. In the proposed method only genuine signatures are used to train the one-class SVMs. The proposed signature verification method has been tested using four different publicly available datasets and the results demonstrate the generality of the proposed method. The proposed system outperforms other existing systems in the literature.
Local Directional Relation Pattern for Unconstrained and Robust Face Retrieval
Venue: arXiv cs.CV 2019
Year: 2019

Face recognition is still a very demanding area of research. This problem becomes more challenging in unconstrained environment and in the presence of several variations like pose, illumination, expression, etc. Local descriptors are widely used for this task. The most of the existing local descriptors consider only few immediate local neighbors and not able to utilize the wider local information to make the descriptor more discriminative. The wider local information based descriptors mainly suffer due to the increased dimensionality. In this paper, this problem is solved by encoding the relationship among directional neighbors in an efficient manner. The relationship between the center pixel and the encoded directional neighbors is utilized further to form the proposed local directional relation pattern (LDRP). The descriptor is inherently uniform illumination invariant. The multi-scale mechanism is also adapted to further boost the discriminative ability of the descriptor. The proposed descriptor is evaluated under the image retrieval framework over face databases. Very challenging databases like PaSC, LFW, PubFig, ESSEX, FERET, AT&T, and FaceScrub are used to test the discriminative ability and robustness of LDRP descriptor. Results are also compared with the recent state-of-the-art face descriptors such as LBP, LTP, LDP, LDN, LVP, DCP, LDGP and LGHP. Very promising performance is observed using the proposed descriptor over very appealing face databases as compared to the existing face descriptors. The proposed LDRP descriptor also outperforms the pre-trained ImageNet CNN models over large-scale FaceScrub face dataset. Moreover, it also outperforms the deep learning based DLib face descriptor in many scenarios.
Mathematical foundations of matrix syntax
Venue: arXiv cs.CL 2019
Year: 2019

Matrix syntax is a formal model of syntactic relations in language. The purpose of this paper is to explain its mathematical foundations, for an audience with some formal background. We make an axiomatic presentation, motivating each axiom on linguistic and practical grounds. The resulting mathematical structure resembles some aspects of quantum mechanics. Matrix syntax allows us to describe a number of language phenomena that are otherwise very difficult to explain, such as linguistic chains, and is arguably a more economical theory of language than most of the theories proposed in the context of the minimalist program in linguistics. In particular, sentences are naturally modelled as vectors in a Hilbert space with a tensor product structure, built from 2x2 matrices belonging to some specific group.
Continuous-Time Relationship Prediction in Dynamic Heterogeneous Information Networks
Venue: arXiv cs.SI 2019
Year: 2019

Online social networks, World Wide Web, media and technological networks, and other types of so-called information networks are ubiquitous nowadays. These information networks are inherently heterogeneous and dynamic. They are heterogeneous as they consist of multi-typed objects and relations, and they are dynamic as they are constantly evolving over time. One of the challenging issues in such heterogeneous and dynamic environments is to forecast those relationships in the network that will appear in the future. In this paper, we try to solve the problem of continuous-time relationship prediction in dynamic and heterogeneous information networks. This implies predicting the time it takes for a relationship to appear in the future, given its features that have been extracted by considering both heterogeneity and temporal dynamics of the underlying network. To this end, we first introduce a feature extraction framework that combines the power of meta-path-based modeling and recurrent neural networks to effectively extract features suitable for relationship prediction regarding heterogeneity and dynamicity of the networks. Next, we propose a supervised non-parametric approach, called Non-Parametric Generalized Linear Model (NP-GLM), which infers the hidden underlying probability distribution of the relationship building time given its features. We then present a learning algorithm to train NP-GLM and an inference method to answer time-related queries. Extensive experiments conducted on synthetic data and three real-world datasets, namely Delicious, MovieLens, and DBLP, demonstrate the effectiveness of NP-GLM in solving continuous-time relationship prediction problem vis-a-vis competitive baselines
DisSent: Sentence Representation Learning from Explicit Discourse Relations
Venue: arXiv cs.CL 2019
Year: 2019

Learning effective representations of sentences is one of the core missions of natural language understanding. Existing models either train on a vast amount of text, or require costly, manually curated sentence relation datasets. We show that with dependency parsing and rule-based rubrics, we can curate a high quality sentence relation task by leveraging explicit discourse relations. We show that our curated dataset provides an excellent signal for learning vector representations of sentence meaning, representing relations that can only be determined when the meanings of two sentences are combined. We demonstrate that the automatically curated corpus allows a bidirectional LSTM sentence encoder to yield high quality sentence embeddings and can serve as a supervised fine-tuning dataset for larger models such as BERT. Our fixed sentence embeddings achieve high performance on a variety of transfer tasks, including SentEval, and we achieve state-of-the-art results on Penn Discourse Treebank's implicit relation prediction task.
DeepRank: A New Deep Architecture for Relevance Ranking in Information Retrieval
Venue: arXiv cs.IR 2019
Year: 2019

This paper concerns a deep learning approach to relevance ranking in information retrieval (IR). Existing deep IR models such as DSSM and CDSSM directly apply neural networks to generate ranking scores, without explicit understandings of the relevance. According to the human judgement process, a relevance label is generated by the following three steps: 1) relevant locations are detected, 2) local relevances are determined, 3) local relevances are aggregated to output the relevance label. In this paper we propose a new deep learning architecture, namely DeepRank, to simulate the above human judgment process. Firstly, a detection strategy is designed to extract the relevant contexts. Then, a measure network is applied to determine the local relevances by utilizing a convolutional neural network (CNN) or two-dimensional gated recurrent units (2D-GRU). Finally, an aggregation network with sequential integration and term gating mechanism is used to produce a global relevance score. DeepRank well captures important IR characteristics, including exact/semantic matching signals, proximity heuristics, query term importance, and diverse relevance requirement. Experiments on both benchmark LETOR dataset and a large scale clickthrough data show that DeepRank can significantly outperform learning to ranking methods, and existing deep learning methods.
Aligning Script Events with Narrative Texts
Venue: arXiv cs.CL 2019
Year: 2019

Script knowledge plays a central role in text understanding and is relevant for a variety of downstream tasks. In this paper, we consider two recent datasets which provide a rich and general representation of script events in terms of paraphrase sets. We introduce the task of mapping event mentions in narrative texts to such script event types, and present a model for this task that exploits rich linguistic representations as well as information on temporal ordering. The results of our experiments demonstrate that this complex task is indeed feasible.
Isointense Infant Brain Segmentation with a Hyper-dense Connected Convolutional Neural Network
Venue: arXiv cs.CV 2019
Year: 2019

Neonatal brain segmentation in magnetic resonance (MR) is a challenging problem due to poor image quality and low contrast between white and gray matter regions. Most existing approaches for this problem are based on multi-atlas label fusion strategies, which are time-consuming and sensitive to registration errors. As alternative to these methods, we propose a hyper-densely connected 3D convolutional neural network that employs MR-T1 and T2 images as input, which are processed independently in two separated paths. An important difference with previous densely connected networks is the use of direct connections between layers from the same and different paths. Adopting such dense connectivity helps the learning process by including deep supervision and improving gradient flow. We evaluated our approach on data from the MICCAI Grand Challenge on 6-month infant Brain MRI Segmentation (iSEG), obtaining very competitive results. Among 21 teams, our approach ranked first or second in most metrics, translating into a state-of-the-art performance.
Measuring Information Leakage in Website Fingerprinting Attacks and Defenses
Venue: arXiv cs.CR 2019
Year: 2019

Tor provides low-latency anonymous and uncensored network access against a local or network adversary. Due to the design choice to minimize traffic overhead (and increase the pool of potential users) Tor allows some information about the client's connections to leak. Attacks using (features extracted from) this information to infer the website a user visits are called Website Fingerprinting (WF) attacks. We develop a methodology and tools to measure the amount of leaked information about a website. We apply this tool to a comprehensive set of features extracted from a large set of websites and WF defense mechanisms, allowing us to make more fine-grained observations about WF attacks and defenses.
Efficient Neighbor-Finding on Space-Filling Curves
Venue: arXiv cs.CG 2019
Year: 2019

Space-filling curves (SFC, also known as FASS-curves) are a useful tool in scientific computing and other areas of computer science to sequentialize multidimensional grids in a cache-efficient and parallelization-friendly way for storage in an array. Many algorithms, for example grid-based numerical PDE solvers, have to access all neighbor cells of each grid cell during a grid traversal. While the array indices of neighbors can be stored in a cell, they still have to be computed for initialization or when the grid is adaptively refined. A fast neighbor-finding algorithm can thus significantly improve the runtime of computations on multidimensional grids. In this thesis, we show how neighbors on many regular grids ordered by space-filling curves can be found in an average-case time complexity of $O(1)$. In general, this assumes that the local orientation (i.e. a variable of a describing grammar) of the SFC inside the grid cell is known in advance, which can be efficiently realized during traversals. Supported SFCs include Hilbert, Peano and Sierpinski curves in arbitrary dimensions. We assume that integer arithmetic operations can be performed in $O(1)$, i.e. independent of the size of the integer. We do not deal with the case of adaptively refined grids here. However, it appears that a generalization of the algorithm to suitable adaptive grids is possible. To formulate the neighbor-finding algorithm and prove its correctness and runtime properties, a modeling framework is introduced. This framework extends the idea of vertex-labeling to a description using grammars and matrices. With the sfcpp library, we provide a C++ implementation to render SFCs generated by such models and automatically compute all lookup tables needed for the neighbor-finding algorithm. Furthermore, optimized neighbor-finding implementations for various SFCs are included for which we provide runtime measurements.
Relaxation-Based Coarsening for Multilevel Hypergraph Partitioning
Venue: arXiv cs.DM 2019
Year: 2019

Multilevel partitioning methods that are inspired by principles of multiscaling are the most powerful practical hypergraph partitioning solvers. Hypergraph partitioning has many applications in disciplines ranging from scientific computing to data science. In this paper we introduce the concept of algebraic distance on hypergraphs and demonstrate its use as an algorithmic component in the coarsening stage of multilevel hypergraph partitioning solvers. The algebraic distance is a vertex distance measure that extends hyperedge weights for capturing the local connectivity of vertices which is critical for hypergraph coarsening schemes. The practical effectiveness of the proposed measure and corresponding coarsening scheme is demonstrated through extensive computational experiments on a diverse set of problems. Finally, we propose a benchmark of hypergraph partitioning problems to compare the quality of other solvers.
Nonsmooth optimal value and policy functions in mechanical systems subject to unilateral constraints
Venue: arXiv cs.RO 2019
Year: 2019

State-of-the-art approaches to optimal control use smooth approximations of value and policy functions and gradient-based algorithms for improving approximator parameters. Unfortunately, we show that value and policy functions that arise in optimal control of mechanical systems subject to unilateral constraints -- i.e. the contact-rich dynamics of robot locomotion and manipulation -- are generally nonsmooth due to the underlying dynamics exhibiting discontinuous or piecewise-differentiable trajectory outcomes. Simple mechanical systems are used to illustrate this result and the implications for optimal control of contact-rich robot dynamics.
A Learning-to-Infer Method for Real-Time Power Grid Multi-Line Outage Identification
Venue: arXiv cs.LG 2019
Year: 2019

Identifying a potentially large number of simultaneous line outages in power transmission networks in real time is a computationally hard problem. This is because the number of hypotheses grows exponentially with the network size. A new "Learning-to-Infer" method is developed for efficient inference of every line status in the network. Optimizing the line outage detector is transformed to and solved as a discriminative learning problem based on Monte Carlo samples generated with power flow simulations. A major advantage of the developed Learning-to-Infer method is that the labeled data used for training can be generated in an arbitrarily large amount rapidly and at very little cost. As a result, the power of offline training is fully exploited to learn very complex classifiers for effective real-time multi-line outage identification. The proposed methods are evaluated in the IEEE 30, 118 and 300 bus systems. Excellent performance in identifying multi-line outages in real time is achieved with a reasonably small amount of data.
Probabilistic Pursuits on Graphs
Venue: arXiv cs.DM 2019
Year: 2019

We consider discrete dynamical systems of "ant-like" agents engaged in a sequence of pursuits on a graph environment. The agents emerge one by one at equal time intervals from a source vertex $s$ and pursue each other by greedily attempting to close the distance to their immediate predecessor, the agent that emerged just before them from $s$, until they arrive at the destination point $t$. Such pursuits have been investigated before in the continuous setting and in discrete time when the underlying environment is a regular grid. In both these settings the agents' walks provably converge to a shortest path from $s$ to $t$. Furthermore, assuming a certain natural probability distribution over the move choices of the agents on the grid (in case there are multiple shortest paths between an agent and its predecessor), the walks converge to the uniform distribution over all shortest paths from $s$ to $t$. We study the evolution of agent walks over a general finite graph environment $G$. Our model is a natural generalization of the pursuit rule proposed for the case of the grid. The main results are as follows. We show that "convergence" to the shortest paths in the sense of previous work extends to all pseudo-modular graphs (i.e. graphs in which every three pairwise intersecting disks have a nonempty intersection), and also to environments obtained by taking graph products, generalizing previous results in two different ways. We show that convergence to the shortest paths is also obtained by chordal graphs, and discuss some further positive and negative results for planar graphs. In the most general case, convergence to the shortest paths is not guaranteed, and the agents may get stuck on sets of recurrent, non-optimal walks from $s$ to $t$. However, we show that the limiting distributions of the agents' walks will always be uniform distributions over some set of walks of equal length.
Decentralized Control of Uncertain Multi-Agent Systems with Connectivity Maintenance and Collision Avoidance
Venue: arXiv cs.SY 2019
Year: 2019

This paper addresses the problem of navigation control of a general class of uncertain nonlinear multi-agent systems in a bounded workspace of $\mathbb{R}^n$ with static obstacles. In particular, we propose a decentralized control protocol such that each agent reaches a predefined position at the workspace, while using only local information based on a limited sensing radius. The proposed scheme guarantees that the initially connected agents remain always connected. In addition, by introducing certain distance constraints, we guarantee inter-agent collision avoidance, as well as, collision avoidance with the obstacles and the boundary of the workspace. The proposed controllers employ a class of Decentralized Nonlinear Model Predictive Controllers (DNMPC) under the presence of disturbances and uncertainties. Finally, simulation results verify the validity of the proposed framework.