OpenRaiser/Intern-Atlas huggingface dataset:
On the numerical rank of radial basis function kernels in high dimension
Venue: arXiv cs.NA 2018
Year: 2018

Low-rank approximations are popular methods to reduce the high computational cost of algorithms involving large-scale kernel matrices. The success of low-rank methods hinges on the matrix rank of the kernel matrix, and in practice, these methods are effective even for high-dimensional datasets. Their practical success motivates our analysis of the function rank, an upper bound of the matrix rank. In this paper, we consider radial basis functions (RBF), approximate the RBF kernel with a low-rank representation that is a finite sum of separate products and provide explicit upper bounds on the function rank and the $L_\infty$ error for such approximations. Our three main results are as follows. First, for a fixed precision, the function rank of RBFs, in the worst case, grows polynomially with the data dimension. Second, precise error bounds for the low-rank approximations in the $L_\infty$ norm are derived in terms of the function smoothness and the domain diameters. Finally, a group pattern in the magnitude of singular values for RBF kernel matrices is observed and analyzed, and is explained by a grouping of the expansion terms in the kernel's low-rank representation. Empirical results verify the theoretical results.
Tree-Residue Vertex-Breaking: a new tool for proving hardness
Venue: arXiv cs.CC 2018
Year: 2018

In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of whose vertices are marked "breakable," is it possible to convert $G$ into a tree via a sequence of "vertex-breaking" operations (replacing a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the $k$ incident edges)? We characterize the computational complexity of TRVB with any combination of the following additional constraints: $G$ must be planar, $G$ must be a simple graph, the degree of every breakable vertex must belong to an allowed list $B$, and the degree of every unbreakable vertex must belong to an allowed list $U$. The two results which we expect to be most generally applicable are that (1) TRVB is polynomially solvable when breakable vertices are restricted to have degree at most $3$; and (2) for any $k \ge 4$, TRVB is NP-complete when the given multigraph is restricted to be planar and to consist entirely of degree-$k$ breakable vertices. To demonstrate the use of TRVB, we give a simple proof of the known result that Hamiltonicity in max-degree-$3$ square grid graphs is NP-hard. We also demonstrate a connection between TRVB and the Hypergraph Spanning Tree problem. This connection allows us to show that the Hypergraph Spanning Tree problem in $k$-uniform $2$-regular hypergraphs is NP-complete for any $k \ge 4$, even when the incidence graph of the hypergraph is planar.
When Can We Answer Queries Using Result-Bounded Data Interfaces?
Venue: arXiv cs.DB 2018
Year: 2018

We consider answering queries where the underlying data is available only over limited interfaces which provide lookup access to the tuples matching a given binding, but possibly restricting the number of output tuples returned. Interfaces imposing such "result bounds" are common in accessing data via the web. Given a query over a set of relations as well as some integrity constraints that relate the queried relations to the data sources, we examine the problem of deciding if the query is answerable over the interfaces; that is, whether there exists a plan that returns all answers to the query, assuming the source data satisfies the integrity constraints. The first component of our analysis of answerability is a reduction to a query containment problem with constraints. The second component is a set of "schema simplification" theorems capturing limitations on how interfaces with result bounds can be useful to obtain complete answers to queries. These results also help to show decidability for the containment problem that captures answerability, for many classes of constraints. The final component in our analysis of answerability is a "linearization" method, showing that query containment with certain guarded dependencies -- including those that emerge from answerability problems -- can be reduced to query containment for a well-behaved class of linear dependencies. Putting these components together, we get a detailed picture of how to check answerability over result-bounded services.
FReLU: Flexible Rectified Linear Units for Improving Convolutional Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Rectified linear unit (ReLU) is a widely used activation function for deep convolutional neural networks. However, because of the zero-hard rectification, ReLU networks miss the benefits from negative values. In this paper, we propose a novel activation function called \emph{flexible rectified linear unit (FReLU)} to further explore the effects of negative values. By redesigning the rectified point of ReLU as a learnable parameter, FReLU expands the states of the activation output. When the network is successfully trained, FReLU tends to converge to a negative value, which improves the expressiveness and thus the performance. Furthermore, FReLU is designed to be simple and effective without exponential functions to maintain low cost computation. For being able to easily used in various network architectures, FReLU does not rely on strict assumptions by self-adaption. We evaluate FReLU on three standard image classification datasets, including CIFAR-10, CIFAR-100, and ImageNet. Experimental results show that the proposed method achieves fast convergence and higher performances on both plain and residual networks.
Revenue Loss in Shrinking Markets
Venue: arXiv cs.GT 2018
Year: 2018

We analyze the revenue loss due to market shrinkage. Specifically, consider a simple market with one item for sale and $n$ bidders whose values are drawn from some joint distribution. Suppose that the market shrinks as a single bidder retires from the market. Suppose furthermore that the value of this retiring bidder is fixed and always strictly smaller than the values of the other players. We show that even this slight decrease in competition might cause a significant fall of a multiplicative factor of $\frac{1}{e+1}\approx0.268$ in the revenue that can be obtained by a dominant strategy ex-post individually rational mechanism. In particular, our results imply a solution to an open question that was posed by Dobzinski, Fu, and Kleinberg [STOC'11].
Is my attack tree correct? Extended version
Venue: arXiv cs.CR 2018
Year: 2018

Attack trees are a popular way to represent and evaluate potential security threats on systems or infrastructures. The goal of this work is to provide a framework allowing to express and check whether an attack tree is consistent with the analyzed system. We model real systems using transition systems and introduce attack trees with formally specified node labels. We formulate the correctness properties of an attack tree with respect to a system and study the complexity of the corresponding decision problems. The proposed framework can be used in practice to assist security experts in manual creation of attack trees and enhance development of tools for automated generation of attack trees.
VoxCeleb: a large-scale speaker identification dataset
Venue: arXiv cs.SD 2018
Year: 2018

Most existing datasets for speaker identification contain samples obtained under quite constrained conditions, and are usually hand-annotated, hence limited in size. The goal of this paper is to generate a large scale text-independent speaker identification dataset collected 'in the wild'. We make two contributions. First, we propose a fully automated pipeline based on computer vision techniques to create the dataset from open-source media. Our pipeline involves obtaining videos from YouTube; performing active speaker verification using a two-stream synchronization Convolutional Neural Network (CNN), and confirming the identity of the speaker using CNN based facial recognition. We use this pipeline to curate VoxCeleb which contains hundreds of thousands of 'real world' utterances for over 1,000 celebrities. Our second contribution is to apply and compare various state of the art speaker identification techniques on our dataset to establish baseline performance. We show that a CNN based architecture obtains the best performance for both identification and verification.
Preserving Differential Privacy in Convolutional Deep Belief Networks
Venue: arXiv cs.LG 2018
Year: 2018

The remarkable development of deep learning in medicine and healthcare domain presents obvious privacy issues, when deep neural networks are built on users' personal and highly sensitive data, e.g., clinical records, user profiles, biomedical images, etc. However, only a few scientific studies on preserving privacy in deep learning have been conducted. In this paper, we focus on developing a private convolutional deep belief network (pCDBN), which essentially is a convolutional deep belief network (CDBN) under differential privacy. Our main idea of enforcing epsilon-differential privacy is to leverage the functional mechanism to perturb the energy-based objective functions of traditional CDBNs, rather than their results. One key contribution of this work is that we propose the use of Chebyshev expansion to derive the approximate polynomial representation of objective functions. Our theoretical analysis shows that we can further derive the sensitivity and error bounds of the approximate polynomial representation. As a result, preserving differential privacy in CDBNs is feasible. We applied our model in a health social network, i.e., YesiWell data, and in a handwriting digit dataset, i.e., MNIST data, for human behavior prediction, human behavior classification, and handwriting digit recognition tasks. Theoretical analysis and rigorous experimental evaluations show that the pCDBN is highly effective. It significantly outperforms existing solutions.
Iterative Sequential Action Control for Stable, Model-Based Control of Nonlinear Systems
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents iterative Sequential Action Control (iSAC), a receding horizon approach for control of nonlinear systems. The iSAC method has a closed-form open-loop solution, which is iteratively updated between time steps by introducing constant control values applied for short duration. Application of a contractive constraint on the cost is shown to lead to closed-loop asymptotic stability under mild assumptions. The effect of asymptotically decaying disturbances on system trajectories is also examined. To demonstrate the applicability of iSAC to a variety of systems and conditions, we employ five different systems, including a 13-dimensional quaternion-based quadrotor. Each system is tested in different scenarios, ranging from feasible and infeasible trajectory tracking, to setpoint stabilization, with or without the presence of external disturbances. Finally, limitations of this work are discussed.
Identifying Patch Correctness in Test-Based Program Repair
Venue: arXiv cs.SE 2018
Year: 2018

Test-based automatic program repair has attracted a lot of attention in recent years. However, the test suites in practice are often too weak to guarantee correctness and existing approaches often generate a large number of incorrect patches. To reduce the number of incorrect patches generated, we propose a novel approach that heuristically determines the correctness of the generated patches. The core idea is to exploit the behavior similarity of test case executions. The passing tests on original and patched programs are likely to behave similarly while the failing tests on original and patched programs are likely to behave differently. Also, if two tests exhibit similar runtime behavior, the two tests are likely to have the same test results. Based on these observations, we generate new test inputs to enhance the test suites and use their behavior similarity to determine patch correctness. Our approach is evaluated on a dataset consisting of 139 patches generated from existing program repair systems including jGenProg, Nopol, jKali, ACS and HDRepair. Our approach successfully prevented 56.3\% of the incorrect patches to be generated, without blocking any correct patches.
A Datamining Approach to the Short Title Catalogue Flanders: the Case of Early Modern Quiring Practices
Venue: arXiv cs.DL 2018
Year: 2018

This paper contains a data mining approach to the Short Title Catalogue Flanders (http://www.stcv.be/), which aims to record all books printed in Flanders up to 1801 (24.850 editions, per 31/08/2018). More specifically, it aims to analyse the Early Modern practice of 'quiring' gatherings in handpress book production
Real-time Distracted Driver Posture Classification
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we present a new dataset for "distracted driver" posture estimation. In addition, we propose a novel system that achieves 95.98% driving posture estimation classification accuracy. The system consists of a genetically-weighted ensemble of Convolutional Neural Networks (CNNs). We show that a weighted ensemble of classifiers using a genetic algorithm yields in better classification confidence. We also study the effect of different visual elements (i.e. hands and face) in distraction detection and classification by means of face and hand localizations. Finally, we present a thinned version of our ensemble that could achieve a 94.29% classification accuracy and operate in a realtime environment.
Filter Bank Multicarrier in Massive MIMO: Analysis and Channel Equalization
Venue: arXiv cs.IT 2018
Year: 2018

We perform an asymptotic study of the performance of filter bank multicarrier (FBMC) in the context of massive multi-input multi-output (MIMO). We show that the effects of channel distortions, i.e., intersymbol interference and intercarrier interference, do not vanish as the base station (BS) array size increases. As a result, the signal-to-interference-plus-noise ratio (SINR) cannot grow unboundedly by increasing the number of BS antennas, and is upper bounded by a certain deterministic value. We show that this phenomenon is a result of the correlation between the multi-antenna combining tap values and the channel impulse responses between the mobile terminals and the BS antennas. To resolve this problem, we introduce an efficient equalization method that removes this correlation, enabling us to achieve arbitrarily large SINR values by increasing the number of BS antennas. We perform a thorough analysis of the proposed system and find analytical expressions for both equalizer coefficients and the respective SINR.
Interpretability via Model Extraction
Venue: arXiv cs.LG 2018
Year: 2018

The ability to interpret machine learning models has become increasingly important now that machine learning is used to inform consequential decisions. We propose an approach called model extraction for interpreting complex, blackbox models. Our approach approximates the complex model using a much more interpretable model; as long as the approximation quality is good, then statistical properties of the complex model are reflected in the interpretable model. We show how model extraction can be used to understand and debug random forests and neural nets trained on several datasets from the UCI Machine Learning Repository, as well as control policies learned for several classical reinforcement learning problems.
Failing to Learn: Autonomously Identifying Perception Failures for Self-driving Cars
Venue: arXiv cs.CV 2018
Year: 2018

One of the major open challenges in self-driving cars is the ability to detect cars and pedestrians to safely navigate in the world. Deep learning-based object detector approaches have enabled great advances in using camera imagery to detect and classify objects. But for a safety critical application, such as autonomous driving, the error rates of the current state of the art are still too high to enable safe operation. Moreover, the characterization of object detector performance is primarily limited to testing on prerecorded datasets. Errors that occur on novel data go undetected without additional human labels. In this letter, we propose an automated method to identify mistakes made by object detectors without ground truth labels. We show that inconsistencies in the object detector output between a pair of similar images can be used as hypotheses for false negatives (e.g., missed detections) and using a novel set of features for each hypothesis, an off-the-shelf binary classifier can be used to find valid errors. In particular, we study two distinct cues - temporal and stereo inconsistencies - using data that are readily available on most autonomous vehicles. Our method can be used with any camera-based object detector and we illustrate the technique on several sets of real world data. We show that a state-of-the-art detector, tracker, and our classifier trained only on synthetic data can identify valid errors on KITTI tracking dataset with an average precision of 0.94. We also release a new tracking dataset with 104 sequences totaling 80,655 labeled pairs of stereo images along with ground truth disparity from a game engine to facilitate further research. The dataset and code are available at https://fcav.engin.umich.edu/research/failing-to-learn
On Binary Matroid Minors and Applications to Data Storage over Small Fields
Venue: arXiv cs.IT 2018
Year: 2018

Locally repairable codes for distributed storage systems have gained a lot of interest recently, and various constructions can be found in the literature. However, most of the constructions result in either large field sizes and hence too high computational complexity for practical implementation, or in low rates translating into waste of the available storage space. In this paper we address this issue by developing theory towards code existence and design over a given field. This is done via exploiting recently established connections between linear locally repairable codes and matroids, and using matroid-theoretic characterisations of linearity over small fields. In particular, nonexistence can be shown by finding certain forbidden uniform minors within the lattice of cyclic flats. It is shown that the lattice of cyclic flats of binary matroids have additional structure that significantly restricts the possible locality properties of $\mathbb{F}_{2}$-linear storage codes. Moreover, a collection of criteria for detecting uniform minors from the lattice of cyclic flats of a given matroid is given, which is interesting in its own right.
Deep neural network initialization with decision trees
Venue: arXiv cs.LG 2018
Year: 2018

In this work a novel, automated process for constructing and initializing deep feed-forward neural networks based on decision trees is presented. The proposed algorithm maps a collection of decision trees trained on the data into a collection of initialized neural networks, with the structures of the networks determined by the structures of the trees. The tree-informed initialization acts as a warm-start to the neural network training process, resulting in efficiently trained, accurate networks. These models, referred to as "deep jointly-informed neural networks" (DJINN), demonstrate high predictive performance for a variety of regression and classification datasets, and display comparable performance to Bayesian hyper-parameter optimization at a lower computational cost. By combining the user-friendly features of decision tree models with the flexibility and scalability of deep neural networks, DJINN is an attractive algorithm for training predictive models on a wide range of complex datasets.
Maintaining cooperation in complex social dilemmas using deep reinforcement learning
Venue: arXiv cs.AI 2018
Year: 2018

Social dilemmas are situations where individuals face a temptation to increase their payoffs at a cost to total welfare. Building artificially intelligent agents that achieve good outcomes in these situations is important because many real world interactions include a tension between selfish interests and the welfare of others. We show how to modify modern reinforcement learning methods to construct agents that act in ways that are simple to understand, nice (begin by cooperating), provokable (try to avoid being exploited), and forgiving (try to return to mutual cooperation). We show both theoretically and experimentally that such agents can maintain cooperation in Markov social dilemmas. Our construction does not require training methods beyond a modification of self-play, thus if an environment is such that good strategies can be constructed in the zero-sum case (eg. Atari) then we can construct agents that solve social dilemmas in this environment.
Circular-shift Linear Network Coding
Venue: arXiv cs.IT 2018
Year: 2018

We study a class of linear network coding (LNC) schemes, called circular-shift LNC, whose encoding operations consist of only circular-shifts and bit-wise additions (XOR). Formulated as a special vector linear code over GF($2$), an $L$-dimensional circular-shift linear code of degree $δ$ restricts its local encoding kernels to be the summation of at most $δ$ cyclic permutation matrices of size $L$. We show that on a general network, for a certain block length $L$, every scalar linear solution over GF($2^{L-1}$) can induce an $L$-dimensional circular-shift linear solution with 1-bit redundancy per-edge transmission. Consequently, specific to a multicast network, such a circular-shift linear solution of an arbitrary degree $δ$ can be efficiently constructed, which has an interesting complexity tradeoff between encoding and decoding with different choices of $δ$. By further proving that circular-shift LNC is insufficient to achieve the exact capacity of certain multicast networks, we show the optimality of the efficiently constructed circular-shift linear solution in the sense that its 1-bit redundancy is inevitable. Finally, both theoretical and numerical analysis imply that with increasing $L$, a randomly constructed circular-shift linear code has linear solvability behavior comparable to a randomly constructed permutation-based linear code, but has shorter overheads.
Adaptive Correlation Filters with Long-Term and Short-Term Memory for Object Tracking
Venue: arXiv cs.CV 2018
Year: 2018

Object tracking is challenging as target objects often undergo drastic appearance changes over time. Recently, adaptive correlation filters have been successfully applied to object tracking. However, tracking algorithms relying on highly adaptive correlation filters are prone to drift due to noisy updates. Moreover, as these algorithms do not maintain long-term memory of target appearance, they cannot recover from tracking failures caused by heavy occlusion or target disappearance in the camera view. In this paper, we propose to learn multiple adaptive correlation filters with both long-term and short-term memory of target appearance for robust object tracking. First, we learn a kernelized correlation filter with an aggressive learning rate for locating target objects precisely. We take into account the appropriate size of surrounding context and the feature representations. Second, we learn a correlation filter over a feature pyramid centered at the estimated target position for predicting scale changes. Third, we learn a complementary correlation filter with a conservative learning rate to maintain long-term memory of target appearance. We use the output responses of this long-term filter to determine if tracking failure occurs. In the case of tracking failures, we apply an incrementally learned detector to recover the target position in a sliding window fashion. Extensive experimental results on large-scale benchmark datasets demonstrate that the proposed algorithm performs favorably against the state-of-the-art methods in terms of efficiency, accuracy, and robustness.