OpenRaiser/Intern-Atlas huggingface dataset:
Evaluation of Dataflow through layers of Deep Neural Networks in Classification and Regression Problems
Venue: arXiv cs.CV 2019
Year: 2019

This paper introduces two straightforward, effective indices to evaluate the input data and the data flowing through layers of a feedforward deep neural network. For classification problems, the separation rate of target labels in the space of dataflow is explained as a key factor indicating the performance of designed layers in improving the generalization of the network. According to the explained concept, a shapeless distance-based evaluation index is proposed. Similarly, for regression problems, the smoothness rate of target outputs in the space of dataflow is explained as a key factor indicating the performance of designed layers in improving the generalization of the network. According to the explained smoothness concept, a shapeless distance-based smoothness index is proposed for regression problems. To consider more strictly concepts of separation and smoothness, their extended versions are introduced, and by interpreting a regression problem as a classification problem, it is shown that the separation and smoothness indices are related together. Through four case studies, the profits of using the introduced indices are shown. In the first case study, for classification and regression problems , the challenging of some known input datasets are compared respectively by the proposed separation and smoothness indices. In the second case study, the quality of dataflow is evaluated through layers of two pre-trained VGG 16 networks in classification of Cifar10 and Cifar100. In the third case study, it is shown that the correct classification rate and the separation index are almost equivalent through layers particularly while the serration index is increased. In the last case study, two multi-layer neural networks, which are designed for the prediction of Boston Housing price, are compared layer by layer by using the proposed smoothness index.
Active Learning of Dynamics for Data-Driven Control Using Koopman Operators
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents an active learning strategy for robotic systems that takes into account task information, enables fast learning, and allows control to be readily synthesized by taking advantage of the Koopman operator representation. We first motivate the use of representing nonlinear systems as linear Koopman operator systems by illustrating the improved model-based control performance with an actuated Van der Pol system. Information-theoretic methods are then applied to the Koopman operator formulation of dynamical systems where we derive a controller for active learning of robot dynamics. The active learning controller is shown to increase the rate of information about the Koopman operator. In addition, our active learning controller can readily incorporate policies built on the Koopman dynamics, enabling the benefits of fast active learning and improved control. Results using a quadcopter illustrate single-execution active learning and stabilization capabilities during free-fall. The results for active learning are extended for automating Koopman observables and we implement our method on real robotic systems.
Macro-action Multi-time scale Dynamic Programming for Energy Management in Buildings with Phase Change Materials
Venue: arXiv cs.LG 2019
Year: 2019

This paper focuses on energy management in buildings with phase change material (PCM), which is primarily used to improve thermal performance, but can also serve as an energy storage system. In this setting, optimal scheduling of an HVAC system is challenging because of the nonlinear and non-convex characteristics of the PCM, which makes solving the corresponding optimization problem using conventional optimization techniques impractical. Instead, we use dynamic programming (DP) to deal with the nonlinear nature of the PCM. To overcome DP's curse of dimensionality, this paper proposes a novel methodology to reduce the computational burden, while maintaining the quality of the solution. Specifically, the method incorporates approaches from sequential decision making in artificial intelligence, including macro actions and multi-time scale Markov decision processes, coupled with an underlying state-space approximation to reduce the state-space and action-space size. The performance of the method is demonstrated on an energy management problem for a typical residential building located in Sydney, Australia. The results demonstrate that the proposed method performs well with a computational speed-up of up to 12,900 times compared to the direct application of DP.
Compressed Sensing MRI via a Multi-scale Dilated Residual Convolution Network
Venue: arXiv cs.CV 2019
Year: 2019

Magnetic resonance imaging (MRI) reconstruction is an active inverse problem which can be addressed by conventional compressed sensing (CS) MRI algorithms that exploit the sparse nature of MRI in an iterative optimization-based manner. However, two main drawbacks of iterative optimization-based CSMRI methods are time-consuming and are limited in model capacity. Meanwhile, one main challenge for recent deep learning-based CSMRI is the trade-off between model performance and network size. To address the above issues, we develop a new multi-scale dilated network for MRI reconstruction with high speed and outstanding performance. Comparing to convolutional kernels with same receptive fields, dilated convolutions reduce network parameters with smaller kernels and expand receptive fields of kernels to obtain almost same information. To maintain the abundance of features, we present global and local residual learnings to extract more image edges and details. Then we utilize concatenation layers to fuse multi-scale features and residual learnings for better reconstruction. Compared with several non-deep and deep learning CSMRI algorithms, the proposed method yields better reconstruction accuracy and noticeable visual improvements. In addition, we perform the noisy setting to verify the model stability, and then extend the proposed model on a MRI super-resolution task.
The Tandem Duplication Distance is NP-hard
Venue: arXiv cs.DS 2019
Year: 2019

In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a genome segment and inserts it right after the segment - this can be represented as the string operation $AXB \Rightarrow AXXB$. For example, Tandem exon duplications have been found in many species such as human, fly or worm, and have been largely studied in computational biology. The Tandem Duplication (TD) distance problem we investigate in this paper is defined as follows: given two strings $S$ and $T$ over the same alphabet, compute the smallest sequence of tandem duplications required to convert $S$ to $T$. The natural question of whether the TD distance can be computed in polynomial time was posed in 2004 by Leupold et al. and had remained open, despite the fact that tandem duplications have received much attention ever since. In this paper, we prove that this problem is NP-hard. We further show that this hardness holds even if all characters of $S$ are distinct. This is known as the exemplar TD distance, which is of special relevance in bioinformatics. One of the tools we develop for the reduction is a new problem called the Cost-Effective Subgraph, for which we obtain W[1]-hardness results that might be of independent interest. We finally show that computing the exemplar TD distance between $S$ and $T$ is fixed-parameter tractable. Our results open the door to many other questions, and we conclude with several open problems.
A Combination of Temporal Sequence Learning and Data Description for Anomaly-based NIDS
Venue: arXiv cs.NI 2019
Year: 2019

Through continuous observation and modeling of normal behavior in networks, Anomaly-based Network Intrusion Detection System (A-NIDS) offers a way to find possible threats via deviation from the normal model. The analysis of network traffic based on the time series model has the advantage of exploiting the relationship between packages within network traffic and observing trends of behaviors over a period of time. It will generate new sequences with good features that support anomaly detection in network traffic and provide the ability to detect new attacks. Besides, an anomaly detection technique, which focuses on the normal data and aims to build a description of it, will be an effective technique for anomaly detection in imbalanced data. In this paper, we propose a combination model of Long Short Term Memory (LSTM) architecture for processing time series and a data description Support Vector Data Description (SVDD) for anomaly detection in A-NIDS to obtain the advantages of them. This model helps parameters in LSTM and SVDD are jointly trained with the joint optimization method. Our experimental results with KDD99 dataset show that the proposed combined model obtains high performance in intrusion detection, especially DoS and Probe attacks with 98.0% and 99.8%, respectively.
Sub-Goal Trees -- a Framework for Goal-Directed Trajectory Prediction and Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Many AI problems, in robotics and other domains, are goal-directed, essentially seeking a trajectory leading to some goal state. In such problems, the way we choose to represent a trajectory underlies algorithms for trajectory prediction and optimization. Interestingly, most all prior work in imitation and reinforcement learning builds on a sequential trajectory representation -- calculating the next state in the trajectory given its predecessors. We propose a different perspective: a goal-conditioned trajectory can be represented by first selecting an intermediate state between start and goal, partitioning the trajectory into two. Then, recursively, predicting intermediate points on each sub-segment, until a complete trajectory is obtained. We call this representation a sub-goal tree, and building on it, we develop new methods for trajectory prediction, learning, and optimization. We show that in a supervised learning setting, sub-goal trees better account for trajectory variability, and can predict trajectories exponentially faster at test time by leveraging a concurrent computation. Then, for optimization, we derive a new dynamic programming equation for sub-goal trees, and use it to develop new planning and reinforcement learning algorithms. These algorithms, which are not based on the standard Bellman equation, naturally account for hierarchical sub-goal structure in a task. Empirical results on motion planning domains show that the sub-goal tree framework significantly improves both accuracy and prediction time.
Uncovering Dominant Social Class in Neighborhoods through Building Footprints: A Case Study of Residential Zones in Massachusetts using Computer Vision
Venue: arXiv cs.CV 2019
Year: 2019

In urban theory, urban form is related to social and economic status. This paper explores to uncover zip-code level income through urban form by analyzing figure-ground map, a simple, prevailing and precise representation of urban form in the field of urban study. Deep learning in computer vision enables such representation maps to be studied at a large scale. We propose to train a DCNN model to identify and uncover the internal bridge between social class and urban form. Further, using hand-crafted informative visual features related with urban form properties (building size, building density, etc.), we apply a random forest classifier to interpret how morphological properties are related with social class.
Eye Contact Correction using Deep Neural Networks
Venue: arXiv cs.CV 2019
Year: 2019

In a typical video conferencing setup, it is hard to maintain eye contact during a call since it requires looking into the camera rather than the display. We propose an eye contact correction model that restores the eye contact regardless of the relative position of the camera and display. Unlike previous solutions, our model redirects the gaze from an arbitrary direction to the center without requiring a redirection angle or camera/display/user geometry as inputs. We use a deep convolutional neural network that inputs a monocular image and produces a vector field and a brightness map to correct the gaze. We train this model in a bi-directional way on a large set of synthetically generated photorealistic images with perfect labels. The learned model is a robust eye contact corrector which also predicts the input gaze implicitly at no additional cost. Our system is primarily designed to improve the quality of video conferencing experience. Therefore, we use a set of control mechanisms to prevent creepy results and to ensure a smooth and natural video conferencing experience. The entire eye contact correction system runs end-to-end in real-time on a commodity CPU and does not require any dedicated hardware, making our solution feasible for a variety of devices.
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
Venue: arXiv cs.LG 2019
Year: 2019

Modern neural network architectures often generalize well despite containing many more parameters than the size of the training dataset. This paper explores the generalization capabilities of neural networks trained via gradient descent. We develop a data-dependent optimization and generalization theory which leverages the low-rank structure of the Jacobian matrix associated with the network. Our results help demystify why training and generalization is easier on clean and structured datasets and harder on noisy and unstructured datasets as well as how the network size affects the evolution of the train and test errors during training. Specifically, we use a control knob to split the Jacobian spectum into "information" and "nuisance" spaces associated with the large and small singular values. We show that over the information space learning is fast and one can quickly train a model with zero training loss that can also generalize well. Over the nuisance space training is slower and early stopping can help with generalization at the expense of some bias. We also show that the overall generalization capability of the network is controlled by how well the label vector is aligned with the information space. A key feature of our results is that even constant width neural nets can provably generalize for sufficiently nice datasets. We conduct various numerical experiments on deep networks that corroborate our theoretical findings and demonstrate that: (i) the Jacobian of typical neural networks exhibit low-rank structure with a few large singular values and many small ones leading to a low-dimensional information space, (ii) over the information space learning is fast and most of the label vector falls on this space, and (iii) label noise falls on the nuisance space and impedes optimization/generalization.
Factorized Mutual Information Maximization
Venue: arXiv cs.IT 2019
Year: 2019

We investigate the sets of joint probability distributions that maximize the average multi-information over a collection of margins. These functionals serve as proxies for maximizing the multi-information of a set of variables or the mutual information of two subsets of variables, at a lower computation and estimation complexity. We describe the maximizers and their relations to the maximizers of the multi-information and the mutual information.
Cognitive Knowledge Graph Reasoning for One-shot Relational Learning
Venue: arXiv cs.LG 2019
Year: 2019

Inferring new facts from existing knowledge graphs (KG) with explainable reasoning processes is a significant problem and has received much attention recently. However, few studies have focused on relation types unseen in the original KG, given only one or a few instances for training. To bridge this gap, we propose CogKR for one-shot KG reasoning. The one-shot relational learning problem is tackled through two modules: the summary module summarizes the underlying relationship of the given instances, based on which the reasoning module infers the correct answers. Motivated by the dual process theory in cognitive science, in the reasoning module, a cognitive graph is built by iteratively coordinating retrieval (System 1, collecting relevant evidence intuitively) and reasoning (System 2, conducting relational reasoning over collected information). The structural information offered by the cognitive graph enables our model to aggregate pieces of evidence from multiple reasoning paths and explain the reasoning process graphically. Experiments show that CogKR substantially outperforms previous state-of-the-art models on one-shot KG reasoning benchmarks, with relative improvements of 24.3%-29.7% on MRR. The source code is available at https://github.com/THUDM/CogKR.
Scalable Community Detection over Geo-Social Network
Venue: arXiv cs.DB 2019
Year: 2019

We consider a community finding problem called Co-located Community Detection (CCD) over geo-social networks, which retrieves communities that satisfy both high structural tightness and spatial closeness constraints. To provide a solution that benefits from existing studies on community detection, we decouple the spatial constraint from graph structural constraint and propose a uniform CCD framework which gives users the freedom to choose customized measurements for social cohesiveness (e.g., $k$-core or $k$-truss). For the spatial closeness constraint, we apply the bounded radius spatial constraint and develop an exact algorithm together with effective pruning rules. To further improve the efficiency and make our framework scale to a very large scale of data, we propose a near-linear time approximation algorithm with a constant approximation ratio ($\sqrt{2}$). We conduct extensive experiments on both synthetic and real-world datasets to demonstrate the efficiency and effectiveness of our algorithms.
A Meta Approach to Defend Noisy Labels by the Manifold Regularizer PSDR
Venue: arXiv cs.LG 2019
Year: 2019

Noisy labels are ubiquitous in real-world datasets, which poses a challenge for robustly training deep neural networks (DNNs) since DNNs can easily overfit to the noisy labels. Most recent efforts have been devoted to defending noisy labels by discarding noisy samples from the training set or assigning weights to training samples, where the weight associated with a noisy sample is expected to be small. Thereby, these previous efforts result in a waste of samples, especially those assigned with small weights. The input $x$ is always useful regardless of whether its observed label $y$ is clean. To make full use of all samples, we introduce a manifold regularizer, named as Paired Softmax Divergence Regularization (PSDR), to penalize the Kullback-Leibler (KL) divergence between softmax outputs of similar inputs. In particular, similar inputs can be effectively generated by data augmentation. PSDR can be easily implemented on any type of DNNs to improve the robustness against noisy labels. As empirically demonstrated on benchmark datasets, our PSDR impressively improve state-of-the-art results by a significant margin.
MIMA: MAPPER-Induced Manifold Alignment for Semi-Supervised Fusion of Optical Image and Polarimetric SAR Data
Venue: arXiv cs.CV 2019
Year: 2019

Multi-modal data fusion has recently been shown promise in classification tasks in remote sensing. Optical data and radar data, two important yet intrinsically different data sources, are attracting more and more attention for potential data fusion. It is already widely known that, a machine learning based methodology often yields excellent performance. However, the methodology relies on a large training set, which is very expensive to achieve in remote sensing. The semi-supervised manifold alignment (SSMA), a multi-modal data fusion algorithm, has been designed to amplify the impact of an existing training set by linking labeled data to unlabeled data via unsupervised techniques. In this paper, we explore the potential of SSMA in fusing optical data and polarimetric SAR data, which are multi-sensory data sources. Furthermore, we propose a MAPPER-induced manifold alignment (MIMA) for semi-supervised fusion of multi-sensory data sources. Our proposed method unites SSMA with MAPPER, which is developed from the emerging topological data analysis (TDA) field. To our best knowledge, this is the first time that SSMA has been applied on fusing optical data and SAR data, and also the first time that TDA has been applied in remote sensing. The conventional SSMA derives a topological structure using k-nearest-neighbor (kNN), while MIMA employs MAPPER, which considers the field knowledge and derives a novel topological structure through the spectral clustering in a data-driven fashion. Experiment results on data fusion with respect to land cover land use classification and local climate zone classification suggest superior performance of MIMA.
A Security Case Study for Blockchain Games
Venue: arXiv cs.CR 2019
Year: 2019

Blockchain gaming is an emerging entertainment paradigm. However, blockchain games are still suffering from security issues, due to the immature blockchain technologies and its unsophisticated developers. In this work, we analyzed the blockchain game architecture and reveal the possible penetration methods of cracking. We scanned more than 600 commercial blockchain games to summarize a security overview from the perspective of the web server and smart contract, respectively. We also conducted three case studies for blockchain games to show detailed vulnerability detection.
A Turing Kernelization Dichotomy for Structural Parameterizations of $\mathcal{F}$-Minor-Free Deletion
Venue: arXiv cs.DS 2019
Year: 2019

For a fixed finite family of graphs $\mathcal{F}$, the $\mathcal{F}$-Minor-Free Deletion problem takes as input a graph $G$ and an integer $\ell$ and asks whether there exists a set $X \subseteq V(G)$ of size at most $\ell$ such that $G-X$ is $\mathcal{F}$-minor-free. For $\mathcal{F}=\{K_2\}$ and $\mathcal{F}=\{K_3\}$ this encodes Vertex Cover and Feedback Vertex Set respectively. When parameterized by the feedback vertex number of $G$ these two problems are known to admit a polynomial kernelization. Such a polynomial kernelization also exists for any $\mathcal{F}$ containing a planar graph but no forests. In this paper we show that $\mathcal{F}$-Minor-Free Deletion parameterized by the feedback vertex number is MK[2]-hard for $\mathcal{F} = \{P_3\}$. This rules out the existence of a polynomial kernel assuming $NP \subseteq coNP/poly$, and also gives evidence that the problem does not admit a polynomial Turing kernel. Our hardness result generalizes to any $\mathcal{F}$ not containing a $P_3$-subgraph-free graph, using as parameter the vertex-deletion distance to treewidth $mintw(\mathcal{F})$, where $mintw(\mathcal{F})$ denotes the minimum treewidth of the graphs in $\mathcal{F}$. For the other case, where $\mathcal{F}$ contains a $P_3$-subgraph-free graph, we present a polynomial Turing kernelization. Our results extend to $\mathcal{F}$-Subgraph-Free Deletion.