OpenRaiser/Intern-Atlas huggingface dataset:
An Optimal Construction for the Barthelmann-Schwentick Normal Form on Classes of Structures of Bounded Degree
Venue: arXiv cs.LO 2018
Year: 2018

Building on the locality conditions for first-order logic by Hanf and Gaifman, Barthelmann and Schwentick showed in 1999 that every first-order formula is equivalent to a formula of the shape $\exists x_1 \dotsc \exists x_k \forall y\,ϕ$ where quantification in $ϕ$ is relativised to elements of distance $\leq r$ from $y$. Such a formula will be called Barthelmann-Schwentick normal form (BSNF) in the following. However, although the proof is effective, it leads to a non-elementary blow-up of the BSNF in terms of the size of the original formula. We show that, if equivalence on the class of all structures, or even only finite forests, is required, this non-elementary blow-up is indeed unavoidable. We then examine restricted classes of structures where more efficient algorithms are possible. In this direction, we show that on any class of structures of degree $\leq 2$, BSNF can be computed in 2-fold exponential time with respect to the size of the input formula. And for any class of structures of degree $\leq d$ for some $d\geq 3$, this is possible in 3-fold exponential time. For both cases, we provide matching lower bounds.
Burst ranking for blind multi-image deblurring
Venue: arXiv cs.CV 2018
Year: 2018

We propose a new incremental aggregation algorithm for multi-image deblurring with automatic image selection. The primary motivation is that current bursts deblurring methods do not handle well situations in which misalignment or out-of-context frames are present in the burst. These real-life situations result in poor reconstructions or manual selection of the images that will be used to deblur. Automatically selecting best frames within the burst to improve the base reconstruction is challenging because the amount of possible images fusions is equal to the power set cardinal. Here, we approach the multi-image deblurring problem as a two steps process. First, we successfully learn a comparison function to rank a burst of images using a deep convolutional neural network. Then, an incremental Fourier burst accumulation with a reconstruction degradation mechanism is applied fusing only less blurred images that are sufficient to maximize the reconstruction quality. Experiments with the proposed algorithm have shown superior results when compared to other similar approaches, outperforming other methods described in the literature in previously described situations. We validate our findings on several synthetic and real datasets.
Deep learning long-range information in undirected graphs with wave networks
Venue: arXiv cs.LG 2018
Year: 2018

Graph algorithms are key tools in many fields of science and technology. Some of these algorithms depend on propagating information between distant nodes in a graph. Recently, there have been a number of deep learning architectures proposed to learn on undirected graphs. However, most of these architectures aggregate information in the local neighborhood of a node, and therefore they may not be capable of efficiently propagating long-range information. To solve this problem we examine a recently proposed architecture, wave, which propagates information back and forth across an undirected graph in waves of nonlinear computation. We compare wave to graph convolution, an architecture based on local aggregation, and find that wave learns three different graph-based tasks with greater efficiency and accuracy. These three tasks include (1) labeling a path connecting two nodes in a graph, (2) solving a maze presented as an image, and (3) computing voltages in a circuit. These tasks range from trivial to very difficult, but wave can extrapolate from small training examples to much larger testing examples. These results show that wave may be able to efficiently solve a wide range of problems that require long-range information propagation across undirected graphs. An implementation of the wave network, and example code for the maze problem are included in the tflon deep learning toolkit (https://bitbucket.org/mkmatlock/tflon).
Automatic CNN-based detection of cardiac MR motion artefacts using k-space data augmentation and curriculum learning
Venue: arXiv cs.CV 2018
Year: 2018

Good quality of medical images is a prerequisite for the success of subsequent image analysis pipelines. Quality assessment of medical images is therefore an essential activity and for large population studies such as the UK Biobank (UKBB), manual identification of artefacts such as those caused by unanticipated motion is tedious and time-consuming. Therefore, there is an urgent need for automatic image quality assessment techniques. In this paper, we propose a method to automatically detect the presence of motion-related artefacts in cardiac magnetic resonance (CMR) cine images. We compare two deep learning architectures to classify poor quality CMR images: 1) 3D spatio-temporal Convolutional Neural Networks (3D-CNN), 2) Long-term Recurrent Convolutional Network (LRCN). Though in real clinical setup motion artefacts are common, high-quality imaging of UKBB, which comprises cross-sectional population data of volunteers who do not necessarily have health problems creates a highly imbalanced classification problem. Due to the high number of good quality images compared to the relatively low number of images with motion artefacts, we propose a novel data augmentation scheme based on synthetic artefact creation in k-space. We also investigate a learning approach using a predetermined curriculum based on synthetic artefact severity. We evaluate our pipeline on a subset of the UK Biobank data set consisting of 3510 CMR images. The LRCN architecture outperformed the 3D-CNN architecture and was able to detect 2D+time short axis images with motion artefacts in less than 1ms with high recall. We compare our approach to a range of state-of-the-art quality assessment methods. The novel data augmentation and curriculum learning approaches both improved classification performance achieving overall area under the ROC curve of 0.89.
Concepts of Architecture, Structure and System
Venue: arXiv cs.SE 2018
Year: 2018

The current ISO standards pertaining to the Concepts of System and Architecture express succinct definitions of these two key terms that lend themselves to practical application and can be understood through elementary mathematical foundations. The current work of the ISO/IEC Working Group 42 is seeking to refine and elaborate the existing standards. This position paper revisits the fundamental concepts underlying both of these key terms and offers an approach to: (i) refine and exemplify the term 'fundamental concepts' in the current ISO definition of Architecture, (ii) exploit existing standards for the term 'concept', and (iii) introduce a new concept, Architectural Structure, that can serve to unify the current terminology at a fundamental level. Precise elementary examples are used in to conceptualise the approach offered.
Three Mechanisms of Weight Decay Regularization
Venue: arXiv cs.LG 2018
Year: 2018

Weight decay is one of the standard tricks in the neural network toolbox, but the reasons for its regularization effect are poorly understood, and recent results have cast doubt on the traditional interpretation in terms of $L_2$ regularization. Literal weight decay has been shown to outperform $L_2$ regularization for optimizers for which they differ. We empirically investigate weight decay for three optimization algorithms (SGD, Adam, and K-FAC) and a variety of network architectures. We identify three distinct mechanisms by which weight decay exerts a regularization effect, depending on the particular optimization algorithm and architecture: (1) increasing the effective learning rate, (2) approximately regularizing the input-output Jacobian norm, and (3) reducing the effective damping coefficient for second-order optimization. Our results provide insight into how to improve the regularization of neural networks.
Sesquickselect: One and a half pivots for cache-efficient selection
Venue: arXiv cs.DS 2018
Year: 2018

Because of unmatched improvements in CPU performance, memory transfers have become a bottleneck of program execution. As discovered in recent years, this also affects sorting in internal memory. Since partitioning around several pivots reduces overall memory transfers, we have seen renewed interest in multiway Quicksort. Here, we analyze in how far multiway partitioning helps in Quickselect. We compute the expected number of comparisons and scanned elements (approximating memory transfers) for a generic class of (non-adaptive) multiway Quickselect and show that three or more pivots are not helpful, but two pivots are. Moreover, we consider "adaptive" variants which choose partitioning and pivot-selection methods in each recursive step from a finite set of alternatives depending on the current (relative) sought rank. We show that "Sesquickselect", a new Quickselect variant that uses either one or two pivots, makes better use of small samples w.r.t. memory transfers than other Quickselect variants.
Learning to Screen for Fast Softmax Inference on Large Vocabulary Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Neural language models have been widely used in various NLP tasks, including machine translation, next word prediction and conversational agents. However, it is challenging to deploy these models on mobile devices due to their slow prediction speed, where the bottleneck is to compute top candidates in the softmax layer. In this paper, we introduce a novel softmax layer approximation algorithm by exploiting the clustering structure of context vectors. Our algorithm uses a light-weight screening model to predict a much smaller set of candidate words based on the given context, and then conducts an exact softmax only within that subset. Training such a procedure end-to-end is challenging as traditional clustering methods are discrete and non-differentiable, and thus unable to be used with back-propagation in the training process. Using the Gumbel softmax, we are able to train the screening model end-to-end on the training set to exploit data distribution. The algorithm achieves an order of magnitude faster inference than the original softmax layer for predicting top-$k$ words in various tasks such as beam search in machine translation or next words prediction. For example, for machine translation task on German to English dataset with around 25K vocabulary, we can achieve 20.4 times speed up with 98.9\% precision@1 and 99.3\% precision@5 with the original softmax layer prediction, while state-of-the-art ~\citep{MSRprediction} only achieves 6.7x speedup with 98.7\% precision@1 and 98.1\% precision@5 for the same task.
Language Classes Associated With Automata Over Matrix Groups
Venue: arXiv cs.FL 2018
Year: 2018

We investigate the language classes recognized by group automata over matrix groups. For the case of $2 \times 2 $ matrices, we prove that the corresponding group automata for rational matrix groups are more powerful than the corresponding group automata for integer matrix groups. Finite automata over some special matrix groups, such as the discrete Heisenberg group and the Baumslag-Solitar group are also examined. We also introduce the notion of time complexity for group automata and demonstrate some separations among related classes. The case of linear-time bounds is examined in detail throughout our repertory of matrix group automata.
Concealing the identity of faces in oblique images with adaptive hopping Gaussian mixtures
Venue: arXiv cs.CV 2018
Year: 2018

Cameras mounted on Micro Aerial Vehicles (MAVs) are increasingly used for recreational photography. However, aerial photographs of public places often contain faces of bystanders thus leading to a perceived or actual violation of privacy. To address this issue, we propose to pseudo-randomly modify the appearance of face regions in the images using a privacy filter that prevents a human or a face recogniser from inferring the identities of people. The filter, which is applied only when the resolution is high enough for a face to be recognisable, adaptively distorts the face appearance as a function of its resolution. Moreover, the proposed filter locally changes its parameters to discourage attacks that use parameter estimation. The filter exploits both global adaptiveness to reduce distortion and local hopping of the parameters to make their estimation difficult for an attacker. In order to evaluate the efficiency of the proposed approach, we use a state-of-the-art face recognition algorithm and synthetically generated face data with 3D geometric image transformations that mimic faces captured from an MAV at different heights and pitch angles. Experimental results show that the proposed filter protects privacy while reducing distortion and exhibits resilience against attacks.
Design and Implementation of Ecological Adaptive Cruise Control for Autonomous Driving with Communication to Traffic Lights
Venue: arXiv cs.SY 2018
Year: 2018

This paper presents the design and implementation results of an ecological adaptive cruise controller (ECO-ACC) which exploits driving automation and connectivity. The controller avoids front collisions and traffic light violations, and is designed to reduce the energy consumption of connected automated vehicles by utilizing historical and real-time signal phase and timing data of traffic lights that adapt to the current traffic conditions. We propose an optimization-based generation of a reference velocity, and a velocity-tracking model predictive controller that avoids front collisions and violations. We present an experimental setup encompassing the real vehicle and controller in the loop, and an environment simulator in which the traffic flow and the traffic light patterns are calibrated on real-world data. We present and analyze simulation and experimental results, finding a significant potential for energy consumption reduction, even in the presence of traffic.
Incremental Learning for Semantic Segmentation of Large-Scale Remote Sensing Data
Venue: arXiv cs.LG 2018
Year: 2018

In spite of remarkable success of the convolutional neural networks on semantic segmentation, they suffer from catastrophic forgetting: a significant performance drop for the already learned classes when new classes are added on the data, having no annotations for the old classes. We propose an incremental learning methodology, enabling to learn segmenting new classes without hindering dense labeling abilities for the previous classes, although the entire previous data are not accessible. The key points of the proposed approach are adapting the network to learn new as well as old classes on the new training data, and allowing it to remember the previously learned information for the old classes. For adaptation, we keep a frozen copy of the previously trained network, which is used as a memory for the updated network in absence of annotations for the former classes. The updated network minimizes a loss function, which balances the discrepancy between outputs for the previous classes from the memory and updated networks, and the mis-classification rate between outputs for the new classes from the updated network and the new ground-truth. For remembering, we either regularly feed samples from the stored, little fraction of the previous data or use the memory network, depending on whether the new data are collected from completely different geographic areas or from the same city. Our experimental results prove that it is possible to add new classes to the network, while maintaining its performance for the previous classes, despite the whole previous training data are not available.
Unsupervised Meta-path Reduction on Heterogeneous Information Networks
Venue: arXiv cs.SI 2018
Year: 2018

Heterogeneous Information Network (HIN) has attracted much attention due to its wide applicability in a variety of data mining tasks, especially for tasks with multi-typed objects. A potentially large number of meta-paths can be extracted from the heterogeneous networks, providing abundant semantic knowledge. Though a variety of meta-paths can be defined, too many meta-paths are redundant. Reduction on the number of meta-paths can enhance the effectiveness since some redundant meta-paths provide interferential linkage to the task. Moreover, the reduced meta-paths can reflect the characteristic of the heterogeneous network. Previous endeavors try to reduce the number of meta-paths under the guidance of supervision information. Nevertheless, supervised information is expensive and may not always be available. In this paper, we propose a novel algorithm, SPMR (Semantic Preserving Meta-path Reduction), to reduce a set of pre-defined meta-paths in an unsupervised setting. The proposed method is able to evaluate a set of meta-paths to maximally preserve the semantics of original meta-paths after reduction. Experimental results show that SPMR can select a succinct subset of meta-paths which can achieve comparable or even better performance with fewer meta-paths.
Gated Transfer Network for Transfer Learning
Venue: arXiv cs.CV 2018
Year: 2018

Deep neural networks have led to a series of breakthroughs in computer vision given sufficient annotated training datasets. For novel tasks with limited labeled data, the prevalent approach is to transfer the knowledge learned in the pre-trained models to the new tasks by fine-tuning. Classic model fine-tuning utilizes the fact that well trained neural networks appear to learn cross domain features. These features are treated equally during transfer learning. In this paper, we explore the impact of feature selection in model fine-tuning by introducing a transfer module, which assigns weights to features extracted from pre-trained models. The proposed transfer module proves the importance of feature selection for transferring models from source to target domains. It is shown to significantly improve upon fine-tuning results with only marginal extra computational cost. We also incorporate an auxiliary classifier as an extra regularizer to avoid over-fitting. Finally, we build a Gated Transfer Network (GTN) based on our transfer module and achieve state-of-the-art results on six different tasks.
Forest Tree Detection and Segmentation using High Resolution Airborne LiDAR
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents an autonomous approach to tree detection and segmentation in high resolution airborne LiDAR that utilises state-of-the-art region-based CNN and 3D-CNN deep learning algorithms. If the number of training examples for a site is low, it is shown to be beneficial to transfer a segmentation network learnt from a different site with more training data and fine-tune it. The algorithm was validated using airborne laser scanning over two different commercial pine plantations. The results show that the proposed approach performs favourably in comparison to other methods for tree detection and segmentation.
Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similarities
Venue: arXiv cs.LG 2018
Year: 2018

Ensemble clustering has been a popular research topic in data mining and machine learning. Despite its significant progress in recent years, there are still two challenging issues in the current ensemble clustering research. First, most of the existing algorithms tend to investigate the ensemble information at the object-level, yet often lack the ability to explore the rich information at higher levels of granularity. Second, they mostly focus on the direct connections (e.g., direct intersection or pair-wise co-occurrence) in the multiple base clusterings, but generally neglect the multi-scale indirect relationship hidden in them. To address these two issues, this paper presents a novel ensemble clustering approach based on fast propagation of cluster-wise similarities via random walks. We first construct a cluster similarity graph with the base clusters treated as graph nodes and the cluster-wise Jaccard coefficient exploited to compute the initial edge weights. Upon the constructed graph, a transition probability matrix is defined, based on which the random walk process is conducted to propagate the graph structural information. Specifically, by investigating the propagating trajectories starting from different nodes, a new cluster-wise similarity matrix can be derived by considering the trajectory relationship. Then, the newly obtained cluster-wise similarity matrix is mapped from the cluster-level to the object-level to achieve an enhanced co-association (ECA) matrix, which is able to simultaneously capture the object-wise co-occurrence relationship as well as the multi-scale cluster-wise relationship in ensembles. Finally, two novel consensus functions are proposed to obtain the consensus clustering result. Extensive experiments on a variety of real-world datasets have demonstrated the effectiveness and efficiency of our approach.
Shorten Spatial-spectral RNN with Parallel-GRU for Hyperspectral Image Classification
Venue: arXiv cs.LG 2018
Year: 2018

Convolutional neural networks (CNNs) attained a good performance in hyperspectral sensing image (HSI) classification, but CNNs consider spectra as orderless vectors. Therefore, considering the spectra as sequences, recurrent neural networks (RNNs) have been applied in HSI classification, for RNNs is skilled at dealing with sequential data. However, for a long-sequence task, RNNs is difficult for training and not as effective as we expected. Besides, spatial contextual features are not considered in RNNs. In this study, we propose a Shorten Spatial-spectral RNN with Parallel-GRU (St-SS-pGRU) for HSI classification. A shorten RNN is more efficient and easier for training than band-by-band RNN. By combining converlusion layer, the St-SSpGRU model considers not only spectral but also spatial feature, which results in a better performance. An architecture named parallel-GRU is also proposed and applied in St-SS-pGRU. With this architecture, the model gets a better performance and is more robust.
Architectural exploration of heterogeneous memory systems
Venue: arXiv cs.AR 2018
Year: 2018

Heterogeneous systems appear as a viable design alternative for the dark silicon era. In this paradigm, a processor chip includes several different technological alternatives for implementing a certain logical block (e.g., core, on-chip memories) which cannot be used at the same time due to power constraints. The programmer and compiler are then responsible for selecting which of the alternatives should be used for maximizing performance and/or energy efficiency for a given application. This paper presents an initial approach for the exploration of different technological alternatives for the implementation of on-chip memories. It hinges on a linear programming-based model for theoretically comparing the performance offered by the available alternatives, namely SRAM and STT-RAM scratchpads or caches. Experimental results using a cycle-accurate simulation tool confirm that this is a viable model for implementation into production compilers.
DSKG: A Deep Sequential Model for Knowledge Graph Completion
Venue: arXiv cs.LG 2018
Year: 2018

Knowledge graph (KG) completion aims to fill the missing facts in a KG, where a fact is represented as a triple in the form of $(subject, relation, object)$. Current KG completion models compel two-thirds of a triple provided (e.g., $subject$ and $relation$) to predict the remaining one. In this paper, we propose a new model, which uses a KG-specific multi-layer recurrent neural network (RNN) to model triples in a KG as sequences. It outperformed several state-of-the-art KG completion models on the conventional entity prediction task for many evaluation metrics, based on two benchmark datasets and a more difficult dataset. Furthermore, our model is enabled by the sequential characteristic and thus capable of predicting the whole triples only given one entity. Our experiments demonstrated that our model achieved promising performance on this new triple prediction task.