OpenRaiser/Intern-Atlas huggingface dataset:
Local-Encoding-Preserving Secure Network Coding---Part I: Fixed Security Level
Venue: arXiv cs.IT 2018
Year: 2018

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this two-part paper, we consider the problem of secure network coding when the information rate and the security level can change over time. In the current paper (i.e., Part I of the two-part paper), we focus on the problem for a fixed security level and a flexible rate. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We present an efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We also develop a polynomial-time algorithm for efficient implementation of this approach. Furthermore, it is proved that the proposed approach incurs no penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. The result in this paper will be used as a building block for efficiently constructing a family of local-encoding-preserving SLNCs for all possible pairs of rate and security level, which will be discussed in the companion paper (i.e., Part II of the two-part paper).
Automatic Repair of Real Bugs in Java: A Large-Scale Experiment on the Defects4J Dataset
Venue: arXiv cs.SE 2018
Year: 2018

Defects4J is a large, peer-reviewed, structured dataset of real-world Java bugs. Each bug in Defects4J comes with a test suite and at least one failing test case that triggers the bug. In this paper, we report on an experiment to explore the effectiveness of automatic test-suite based repair on Defects4J. The result of our experiment shows that the considered state-of-the-art repair methods can generate patches for 47 out of 224 bugs. However, those patches are only test-suite adequate, which means that they pass the test suite and may potentially be incorrect beyond the test-suite satisfaction correctness criterion. We have manually analyzed 84 different patches to assess their real correctness. In total, 9 real Java bugs can be correctly repaired with test-suite based repair. This analysis shows that test-suite based repair suffers from under-specified bugs, for which trivial or incorrect patches still pass the test suite. With respect to practical applicability, it takes on average 14.8 minutes to find a patch. The experiment was done on a scientific grid, totaling 17.6 days of computation time. All the repair systems and experimental results are publicly available on Github in order to facilitate future research on automatic repair.
On the Number of Order Types in Integer Grids of Small Size
Venue: arXiv cs.CG 2018
Year: 2018

Let $\{p_1,\dots,p_n\}$ and $\{q_1,\dots,q_n\}$ be two sets of $n$ labeled points in general position in the plane. We say that these two point sets have the same order type if for every triple of indices $(i,j,k)$, $p_k$ is above the directed line from $p_i$ to $p_j$ if and only if $q_k$ is above the directed line from $q_i$ to $q_j$. In this paper we give the first non-trivial lower bounds on the number of different order types of $n$ points that can be realized in integer grids of polynomial
Towards continual learning in medical imaging
Venue: arXiv cs.CV 2018
Year: 2018

This work investigates continual learning of two segmentation tasks in brain MRI with neural networks. To explore in this context the capabilities of current methods for countering catastrophic forgetting of the first task when a new one is learned, we investigate elastic weight consolidation, a recently proposed method based on Fisher information, originally evaluated on reinforcement learning of Atari games. We use it to sequentially learn segmentation of normal brain structures and then segmentation of white matter lesions. Our findings show this recent method reduces catastrophic forgetting, while large room for improvement exists in these challenging settings for continual learning.
Variational Bayes Inference in Digital Receivers
Venue: arXiv cs.IT 2018
Year: 2018

The digital telecommunications receiver is an important context for inference methodology, the key objective being to minimize the expected loss function in recovering the transmitted information. For that criterion, the optimal decision is the Bayesian minimum-risk estimator. However, the computational load of the Bayesian estimator is often prohibitive and, hence, efficient computational schemes are required. The design of novel schemes, striking new balances between accuracy and computational load, is the primary concern of this thesis. Two popular techniques, one exact and one approximate, will be studied. The exact scheme is a recursive one, namely the generalized distributive law (GDL), whose purpose is to distribute all operators across the conditionally independent (CI) factors of the joint model, so as to reduce the total number of operators required. In a novel theorem derived in this thesis, GDL, if applicable, will be shown to guarantee such a reduction in all cases. An associated lemma also quantifies this reduction. For practical use, two novel algorithms, namely the no-longer-needed (NLN) algorithm and the generalized form of the Markovian Forward-Backward (FB) algorithm, recursively factorizes and computes the CI factors of an arbitrary model, respectively. The approximate scheme is an iterative one, namely the Variational Bayes (VB) approximation, whose purpose is to find the independent (i.e. zero-order Markov) model closest to the true joint model in the minimum Kullback-Leibler divergence (KLD) sense. Despite being computationally efficient, this naive mean field approximation confers only modest performance for highly correlated models. A novel approximation, namely Transformed Variational Bayes (TVB), will be designed in the thesis in order to relax the zero-order constraint in the VB approximation, further reducing the KLD of the optimal approximation.
Training Generative Adversarial Networks with Weights
Venue: arXiv cs.LG 2018
Year: 2018

The impressive success of Generative Adversarial Networks (GANs) is often overshadowed by the difficulties in their training. Despite the continuous efforts and improvements, there are still open issues regarding their convergence properties. In this paper, we propose a simple training variation where suitable weights are defined and assist the training of the Generator. We provide theoretical arguments why the proposed algorithm is better than the baseline training in the sense of speeding up the training process and of creating a stronger Generator. Performance results showed that the new algorithm is more accurate in both synthetic and image datasets resulting in improvements ranging between 5% and 50%.
Evaluating the Ability of LSTMs to Learn Context-Free Grammars
Venue: arXiv cs.CL 2018
Year: 2018

While long short-term memory (LSTM) neural net architectures are designed to capture sequence information, human language is generally composed of hierarchical structures. This raises the question as to whether LSTMs can learn hierarchical structures. We explore this question with a well-formed bracket prediction task using two types of brackets modeled by an LSTM. Demonstrating that such a system is learnable by an LSTM is the first step in demonstrating that the entire class of CFLs is also learnable. We observe that the model requires exponential memory in terms of the number of characters and embedded depth, where a sub-linear memory should suffice. Still, the model does more than memorize the training input. It learns how to distinguish between relevant and irrelevant information. On the other hand, we also observe that the model does not generalize well. We conclude that LSTMs do not learn the relevant underlying context-free rules, suggesting the good overall performance is attained rather by an efficient way of evaluating nuisance variables. LSTMs are a way to quickly reach good results for many natural language tasks, but to understand and generate natural language one has to investigate other concepts that can make more direct use of natural language's structural nature.
Understanding the Role of Data-Centric Social Context in Personalized Mobile Applications
Venue: arXiv cs.CY 2018
Year: 2018

Context-awareness in personalized mobile applications is a growing area of study. Social context is one of the most important sources of information in human-activity based applications. In this paper, we mainly focus on social relational context that represents the interpersonal relationship between individuals, and the role or influence of such context on users' diverse phone call activities in their real world life. Individuals different phone call activities such as making a phone call to a particular person or responding an incoming call may differ from person-to-person based on their interpersonal relationships such as family, friend, or colleague. However, it is very difficult to make the device understandable about such semantic relationships between individuals and the relevant context-aware applications. To address this issue, in this paper, we explore the data-centric social relational context that can play a significant role in building context-aware personalized mobile applications for various purposes in our real world life.
A Volumetric Convolutional Neural Network for Brain Tumor Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Brain cancer can be very fatal, but chances of survival increase through early detection and treatment. Doctors use Magnetic Resonance Imaging (MRI) to detect and locate tumors in the brain, and very carefully analyze scans to segment brain tumors. Manual segmentation is time consuming and tiring for doctors, and it can be difficult for them to notice extremely small abnormalities. Automated segmentations performed by computers offer quicker diagnoses, the ability to notice small details, and more accurate segmentations. Advances in deep learning and computer hardware have allowed for high-performing automated segmentation approaches. However, several problems persist in practice: increased training time, class imbalance, and low performance. In this paper, I propose applying V-Net, a volumetric, fully convolutional neural network, to segment brain tumors in MRI scans from the BraTS Challenges. With this approach, I achieve a whole tumor dice score of 0.89 and train the network in a short time while addressing class imbalance with the use of a dice loss layer. Then, I propose applying an existing technique to improve automated segmentation performance in practice.
Training Domain Specific Models for Energy-Efficient Object Detection
Venue: arXiv cs.CV 2018
Year: 2018

We propose an end-to-end framework for training domain specific models (DSMs) to obtain both high accuracy and computational efficiency for object detection tasks. DSMs are trained with distillation \cite{hinton2015distilling} and focus on achieving high accuracy at a limited domain (e.g. fixed view of an intersection). We argue that DSMs can capture essential features well even with a small model size, enabling higher accuracy and efficiency than traditional techniques. In addition, we improve the training efficiency by reducing the dataset size by culling easy to classify images from the training set. For the limited domain, we observed that compact DSMs significantly surpass the accuracy of COCO trained models of the same size. By training on a compact dataset, we show that with an accuracy drop of only 3.6\%, the training time can be reduced by 93\%. The codes are uploaded in https://github.com/kentaroy47/training-domain-specific-models.
Scalable Bottom-up Subspace Clustering using FP-Trees for High Dimensional Data
Venue: arXiv cs.LG 2018
Year: 2018

Subspace clustering aims to find groups of similar objects (clusters) that exist in lower dimensional subspaces from a high dimensional dataset. It has a wide range of applications, such as analysing high dimensional sensor data or DNA sequences. However, existing algorithms have limitations in finding clusters in non-disjoint subspaces and scaling to large data, which impinge their applicability in areas such as bioinformatics and the Internet of Things. We aim to address such limitations by proposing a subspace clustering algorithm using a bottom-up strategy. Our algorithm first searches for base clusters in low dimensional subspaces. It then forms clusters in higher-dimensional subspaces using these base clusters, which we formulate as a frequent pattern mining problem. This formulation enables efficient search for clusters in higher-dimensional subspaces, which is done using FP-trees. The proposed algorithm is evaluated against traditional bottom-up clustering algorithms and state-of-the-art subspace clustering algorithms. The experimental results show that the proposed algorithm produces clusters with high accuracy, and scales well to large volumes of data. We also demonstrate the algorithm's performance using real-life data, including ten genomic datasets and a car parking occupancy dataset.
Weighted Matchings via Unweighted Augmentations
Venue: arXiv cs.DS 2018
Year: 2018

We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the streaming model and in the massively parallel computation (MPC) model. In the context of streaming with random edge arrivals, our techniques yield a $(1/2+c)$-approximation algorithm thus breaking the natural barrier of $1/2$. For multi-pass streaming and the MPC model, we show that any algorithm computing a $(1-δ)$-approximate unweighted matching in bipartite graphs can be translated into an algorithm that computes a $(1-\varepsilon(δ))$-approximate maximum weighted matching. Furthermore, this translation incurs only a constant factor (that depends on $\varepsilon> 0$) overhead in the complexity. Instantiating this with the current best multi-pass streaming and MPC algorithms for unweighted matchings yields the following results for maximum weighted matchings: * A $(1-\varepsilon)$-approximation streaming algorithm that uses $O_\varepsilon(1)$ passes and $O_\varepsilon(n\, \text{poly} (\log n))$ memory. This is the first $(1-\varepsilon)$-approximation streaming algorithm for weighted matchings that uses a constant number of passes (only depending on $\varepsilon$). * A $(1 - \varepsilon)$-approximation algorithm in the MPC model that uses $O_\varepsilon(\log \log n)$ rounds, $O(m/n)$ machines per round, and $O_\varepsilon(n\, \text{poly}(\log n))$ memory per machine. This improves upon the previous best approximation guarantee of $(1/2-\varepsilon)$ for weighted graphs.
YASENN: Explaining Neural Networks via Partitioning Activation Sequences
Venue: arXiv cs.LG 2018
Year: 2018

We introduce a novel approach to feed-forward neural network interpretation based on partitioning the space of sequences of neuron activations. In line with this approach, we propose a model-specific interpretation method, called YASENN. Our method inherits many advantages of model-agnostic distillation, such as an ability to focus on the particular input region and to express an explanation in terms of features different from those observed by a neural network. Moreover, examination of distillation error makes the method applicable to the problems with low tolerance to interpretation mistakes. Technically, YASENN distills the network with an ensemble of layer-wise gradient boosting decision trees and encodes the sequences of neuron activations with leaf indices. The finite number of unique codes induces a partitioning of the input space. Each partition may be described in a variety of ways, including examination of an interpretable model (e.g. a logistic regression or a decision tree) trained to discriminate between objects of those partitions. Our experiments provide an intuition behind the method and demonstrate revealed artifacts in neural network decision making.
Median Binary-Connect Method and a Binary Convolutional Neural Nework for Word Recognition
Venue: arXiv cs.LG 2018
Year: 2018

We propose and study a new projection formula for training binary weight convolutional neural networks. The projection formula measures the error in approximating a full precision (32 bit) vector by a 1-bit vector in the l_1 norm instead of the standard l_2 norm. The l_1 projector is in closed analytical form and involves a median computation instead of an arithmatic average in the l_2 projector. Experiments on 10 keywords classification show that the l_1 (median) BinaryConnect (BC) method outperforms the regular BC, regardless of cold or warm start. The binary network trained by median BC and a recent blending technique reaches test accuracy 92.4%, which is 1.1% lower than the full-precision network accuracy 93.5%. On Android phone app, the trained binary network doubles the speed of full-precision network in spoken keywords recognition.
StkTokens: Enforcing Well-bracketed Control Flow and Stack Encapsulation using Linear Capabilities - Technical Report with Proofs and Details
Venue: arXiv cs.PL 2018
Year: 2018

We propose and study StkTokens: a new calling convention that provably enforces well-bracketed control flow and local state encapsulation on a capability machine. The calling convention is based on linear capabilities: a type of capabilities that are prevented from being duplicated by the hardware. In addition to designing and formalizing this new calling convention, we also contribute a new way to formalize and prove that it effectively enforces well-bracketed control flow and local state encapsulation using what we call a fully abstract overlay semantics. This document is a technical report accompanying a paper by the same title and authors, published at POPL 2019. It contains proofs and details that were omitted from the paper for space and presentation reasons.
Amalgamating Knowledge towards Comprehensive Classification
Venue: arXiv cs.CV 2018
Year: 2018

With the rapid development of deep learning, there have been an unprecedentedly large number of trained deep network models available online. Reusing such trained models can significantly reduce the cost of training the new models from scratch, if not infeasible at all as the annotations used for the training original networks are often unavailable to public. We propose in this paper to study a new model-reusing task, which we term as \emph{knowledge amalgamation}. Given multiple trained teacher networks, each of which specializes in a different classification problem, the goal of knowledge amalgamation is to learn a lightweight student model capable of handling the comprehensive classification. We assume no other annotations except the outputs from the teacher models are available, and thus focus on extracting and amalgamating knowledge from the multiple teachers. To this end, we propose a pilot two-step strategy to tackle the knowledge amalgamation task, by learning first the compact feature representations from teachers and then the network parameters in a layer-wise manner so as to build the student model. We apply this approach to four public datasets and obtain very encouraging results: even without any human annotation, the obtained student model is competent to handle the comprehensive classification task and in most cases outperforms the teachers in individual sub-tasks.
Deep Neural Networks for ECG-free Cardiac Phase and End-Diastolic Frame Detection on Coronary Angiographies
Venue: arXiv cs.CV 2018
Year: 2018

Invasive coronary angiography (ICA) is the gold standard in Coronary Artery Disease (CAD) imaging. Detection of the end-diastolic frame (EDF) and, in general, cardiac phase detection on each temporal frame of a coronary angiography acquisition is of significant importance for the anatomical and non-invasive functional assessment of CAD. This task is generally performed via manual frame selection or semi-automated selection based on simultaneously acquired ECG signals - thus introducing the requirement of simultaneous ECG recordings. We evaluate the performance of a purely image based workflow based on deep neural networks for fully automated cardiac phase and EDF detection on coronary angiographies. A first deep neural network (DNN), trained to detect coronary arteries, is employed to preselect a subset of frames in which coronary arteries are well visible. A second DNN predicts cardiac phase labels for each frame. Only in the training and evaluation phases for the second DNN, ECG signals are used to provide ground truth labels for each angiographic frame. The networks were trained on 17800 coronary angiographies from 3900 patients and evaluated on 27900 coronary angiographies from 6250 patients. No exclusion criteria related to patient state, previous interventions, or pathology were formulated. Cardiac phase detection had an accuracy of 97.6%, a sensitivity of 97.6% and a specificity of 97.5% on the evaluation set. EDF prediction had a precision of 97.4% and a recall of 96.9%. Several sub-group analyses were performed, indicating that the cardiac phase detection performance is largely independent from acquisition angles and the heart rate of the patient. The average execution time of cardiac phase detection for one angiographic series was on average less than five seconds on a standard workstation.
Construction and Quality Evaluation of Heterogeneous Hierarchical Topic Models
Venue: arXiv cs.IR 2018
Year: 2018

In our work, we propose to represent HTM as a set of flat models, or layers, and a set of topical hierarchies, or edges. We suggest several quality measures for edges of hierarchical models, resembling those proposed for flat models. We conduct an assessment experimentation and show strong correlation between the proposed measures and human judgement on topical edge quality. We also introduce heterogeneous algorithm to build hierarchical topic models for heterogeneous data sources. We show how making certain adjustments to learning process helps to retain original structure of customized models while allowing for slight coherent modifications for new documents. We evaluate this approach using the proposed measures and show that the proposed heterogeneous algorithm significantly outperforms the baseline concat approach. Finally, we implement our own ESE called Rysearch, which demonstrates the potential of ARTM approach for visualizing large heterogeneous document collections.
UWB/LiDAR Fusion For Cooperative Range-Only SLAM
Venue: arXiv cs.RO 2018
Year: 2018

We equip an ultra-wideband (UWB) node and a 2D LiDAR sensor a.k.a. 2D laser rangefinder on a mobile robot, and place UWB beacon nodes at unknown locations in an unknown environment. All UWB nodes can do ranging with each other thus forming a cooperative sensor network. We propose to fuse the peer-to-peer ranges measured between UWB nodes and laser scanning information, i.e. range measured between robot and nearby objects/obstacles, for simultaneous localization of the robot, all UWB beacons, and LiDAR mapping. The fusion is inspired by two facts: 1) LiDAR may improve UWB-only localization accuracy as it gives a more precise and comprehensive picture of the surrounding environment; 2) on the other hand, UWB ranging measurements may remove the error accumulated in the LiDAR-based SLAM algorithm. Our experiments demonstrate that UWB/LiDAR fusion enables drift-free SLAM in real-time based on ranging measurements only.