OpenRaiser/Intern-Atlas huggingface dataset:
Safety-Aware Apprenticeship Learning
Venue: arXiv cs.AI 2018
Year: 2018

Apprenticeship learning (AL) is a kind of Learning from Demonstration techniques where the reward function of a Markov Decision Process (MDP) is unknown to the learning agent and the agent has to derive a good policy by observing an expert's demonstrations. In this paper, we study the problem of how to make AL algorithms inherently safe while still meeting its learning objective. We consider a setting where the unknown reward function is assumed to be a linear combination of a set of state features, and the safety property is specified in Probabilistic Computation Tree Logic (PCTL). By embedding probabilistic model checking inside AL, we propose a novel counterexample-guided approach that can ensure safety while retaining performance of the learnt policy. We demonstrate the effectiveness of our approach on several challenging AL scenarios where safety is essential.
The Refinement Calculus of Reactive Systems Toolset
Venue: arXiv cs.LO 2018
Year: 2018

We present the Refinement Calculus of Reactive Systems Toolset, an environment for compositional modeling and reasoning about reactive systems, built on top of Isabelle, Simulink, and Python.
Distributed estimation from relative measurements of heterogeneous and uncertain quality
Venue: arXiv cs.SY 2018
Year: 2018

This paper studies the problem of estimation from relative measurements in a graph, in which a vector indexed over the nodes has to be reconstructed from pairwise measurements of differences between its components associated to nodes connected by an edge. In order to model heterogeneity and uncertainty of the measurements, we assume them to be affected by additive noise distributed according to a Gaussian mixture. In this original setup, we formulate the problem of computing the Maximum-Likelihood (ML) estimates and we design two novel algorithms, based on Least Squares regression and Expectation-Maximization (EM). The first algorithm (LS- EM) is centralized and performs the estimation from relative measurements, the soft classification of the measurements, and the estimation of the noise parameters. The second algorithm (Distributed LS-EM) is distributed and performs estimation and soft classification of the measurements, but requires the knowledge of the noise parameters. We provide rigorous proofs of convergence of both algorithms and we present numerical experiments to evaluate and compare their performance with classical solutions. The experiments show the robustness of the proposed methods against different kinds of noise and, for the Distributed LS-EM, against errors in the knowledge of noise parameters.
Deep Transfer Learning for Error Decoding from Non-Invasive EEG
Venue: arXiv cs.LG 2018
Year: 2018

We recorded high-density EEG in a flanker task experiment (31 subjects) and an online BCI control paradigm (4 subjects). On these datasets, we evaluated the use of transfer learning for error decoding with deep convolutional neural networks (deep ConvNets). In comparison with a regularized linear discriminant analysis (rLDA) classifier, ConvNets were significantly better in both intra- and inter-subject decoding, achieving an average accuracy of 84.1 % within subject and 81.7 % on unknown subjects (flanker task). Neither method was, however, able to generalize reliably between paradigms. Visualization of features the ConvNets learned from the data showed plausible patterns of brain activity, revealing both similarities and differences between the different kinds of errors. Our findings indicate that deep learning techniques are useful to infer information about the correctness of action in BCI applications, particularly for the transfer of pre-trained classifiers to new recording sessions or subjects.
Automated cardiovascular magnetic resonance image analysis with fully convolutional networks
Venue: arXiv cs.CV 2018
Year: 2018

Cardiovascular magnetic resonance (CMR) imaging is a standard imaging modality for assessing cardiovascular diseases (CVDs), the leading cause of death globally. CMR enables accurate quantification of the cardiac chamber volume, ejection fraction and myocardial mass, providing information for diagnosis and monitoring of CVDs. However, for years, clinicians have been relying on manual approaches for CMR image analysis, which is time consuming and prone to subjective errors. It is a major clinical challenge to automatically derive quantitative and clinically relevant information from CMR images. Deep neural networks have shown a great potential in image pattern recognition and segmentation for a variety of tasks. Here we demonstrate an automated analysis method for CMR images, which is based on a fully convolutional network (FCN). The network is trained and evaluated on a large-scale dataset from the UK Biobank, consisting of 4,875 subjects with 93,500 pixelwise annotated images. The performance of the method has been evaluated using a number of technical metrics, including the Dice metric, mean contour distance and Hausdorff distance, as well as clinically relevant measures, including left ventricle (LV) end-diastolic volume (LVEDV) and end-systolic volume (LVESV), LV mass (LVM); right ventricle (RV) end-diastolic volume (RVEDV) and end-systolic volume (RVESV). By combining FCN with a large-scale annotated dataset, the proposed automated method achieves a high performance on par with human experts in segmenting the LV and RV on short-axis CMR images and the left atrium (LA) and right atrium (RA) on long-axis CMR images.
A unified framework for manifold landmarking
Venue: arXiv cs.LG 2018
Year: 2018

The success of semi-supervised manifold learning is highly dependent on the quality of the labeled samples. Active manifold learning aims to select and label representative landmarks on a manifold from a given set of samples to improve semi-supervised manifold learning. In this paper, we propose a novel active manifold learning method based on a unified framework of manifold landmarking. In particular, our method combines geometric manifold landmarking methods with algebraic ones. We achieve this by using the Gershgorin circle theorem to construct an upper bound on the learning error that depends on the landmarks and the manifold's alignment matrix in a way that captures both the geometric and algebraic criteria. We then attempt to select landmarks so as to minimize this bound by iteratively deleting the Gershgorin circles corresponding to the selected landmarks. We also analyze the complexity, scalability, and robustness of our method through simulations, and demonstrate its superiority compared to existing methods. Experiments in regression and classification further verify that our method performs better than its competitors.
Signed Network Modeling Based on Structural Balance Theory
Venue: arXiv cs.SI 2018
Year: 2018

The modeling of networks, specifically generative models, have been shown to provide a plethora of information about the underlying network structures, as well as many other benefits behind their construction. Recently there has been a considerable increase in interest for the better understanding and modeling of networks, but the vast majority of this work has been for unsigned networks. However, many networks can have positive and negative links(or signed networks), especially in online social media, and they inherently have properties not found in unsigned networks due to the added complexity. Specifically, the positive to negative link ratio and the distribution of signed triangles in the networks are properties that are unique to signed networks and would need to be explicitly modeled. This is because their underlying dynamics are not random, but controlled by social theories, such as Structural Balance Theory, which loosely states that users in social networks will prefer triadic relations that involve less tension. Therefore, we propose a model based on Structural Balance Theory and the unsigned Transitive Chung-Lu model for the modeling of signed networks. Our model introduces two parameters that are able to help maintain the positive link ratio and proportion of balanced triangles. Empirical experiments on three real-world signed networks demonstrate the importance of designing models specific to signed networks based on social theories to obtain better performance in maintaining signed network properties while generating synthetic networks.
Distributed Graph Clustering using Modularity and Map Equation
Venue: arXiv cs.DS 2018
Year: 2018

We study large-scale, distributed graph clustering. Given an undirected graph, our objective is to partition the nodes into disjoint sets called clusters. A cluster should contain many internal edges while being sparsely connected to other clusters. In the context of a social network, a cluster could be a group of friends. Modularity and map equation are established formalizations of this internally-dense-externally-sparse principle. We present two versions of a simple distributed algorithm to optimize both measures. They are based on Thrill, a distributed big data processing framework that implements an extended MapReduce model. The algorithms for the two measures, DSLM-Mod and DSLM-Map, differ only slightly. Adapting them for similar quality measures is straight-forward. We conduct an extensive experimental study on real-world graphs and on synthetic benchmark graphs with up to 68 billion edges. Our algorithms are fast while detecting clusterings similar to those detected by other sequential, parallel and distributed clustering algorithms. Compared to the distributed GossipMap algorithm, DSLM-Map needs less memory, is up to an order of magnitude faster and achieves better quality.
Protograph LDPC Codes with Block Thresholds: Extension to Degree-1 and Generalized Nodes
Venue: arXiv cs.IT 2018
Year: 2018

Protograph low-density-parity-check (LDPC) are considered to design near-capacity low-rate codes over the binary erasure channel (BEC) and binary additive white Gaussian noise (BIAWGN) channel. For protographs with degree-one variable nodes and doubly-generalized LDPC (DGLDPC) codes, conditions are derived to ensure equality of bit-error threshold and block-error threshold. Using this condition, low-rate codes with block-error threshold close to capacity are designed and shown to have better error rate performance than other existing codes.
Time-Division is Optimal for Covert Communication over Some Broadcast Channels
Venue: arXiv cs.IT 2018
Year: 2018

We consider a covert communication scenario where a transmitter wishes to communicate simultaneously to two legitimate receivers while ensuring that the communication is not detected by an adversary, the warden. The legitimate receivers and the adversary observe the transmission from the transmitter via a three-user discrete or Gaussian memoryless broadcast channel. We focus on the case where the "no-input" symbol is not redundant, i.e., the output distribution at the warden induced by the no-input symbol is not a mixture of the output distributions induced by other input symbols, so that the covert communication is governed by the square root law, i.e., at most $Θ(\sqrt{n})$ bits can be transmitted over $n$ channel uses. We show that for such a setting, a simple time-division strategy achieves the optimal throughputs for a non-trivial class of broadcast channels; this is not true for communicating over broadcast channels without the covert communication constraint. Our result implies that a code that uses two separate optimal point-to-point codes each designed for the constituent channels and each used for a fraction of the time is optimal in the sense that it achieves the best constants of the $\sqrt{n}$-scaling for the throughputs. Our proof strategy combines several elements in the network information theory literature, including concave envelope representations of the capacity regions of broadcast channels and El Gamal's outer bound for more capable broadcast channels.
How to Fool Radiologists with Generative Adversarial Networks? A Visual Turing Test for Lung Cancer Diagnosis
Venue: arXiv cs.CV 2018
Year: 2018

Discriminating lung nodules as malignant or benign is still an underlying challenge. To address this challenge, radiologists need computer aided diagnosis (CAD) systems which can assist in learning discriminative imaging features corresponding to malignant and benign nodules. However, learning highly discriminative imaging features is an open problem. In this paper, our aim is to learn the most discriminative features pertaining to lung nodules by using an adversarial learning methodology. Specifically, we propose to use unsupervised learning with Deep Convolutional-Generative Adversarial Networks (DC-GANs) to generate lung nodule samples realistically. We hypothesize that imaging features of lung nodules will be discriminative if it is hard to differentiate them (fake) from real (true) nodules. To test this hypothesis, we present Visual Turing tests to two radiologists in order to evaluate the quality of the generated (fake) nodules. Extensive comparisons are performed in discerning real, generated, benign, and malignant nodules. This experimental set up allows us to validate the overall quality of the generated nodules, which can then be used to (1) improve diagnostic decisions by mining highly discriminative imaging features, (2) train radiologists for educational purposes, and (3) generate realistic samples to train deep networks with big data.
Computing the Line Index of Balance Using Integer Programming Optimisation
Venue: arXiv cs.SI 2018
Year: 2018

An important measure of signed graphs is the line index of balance which has several applications in many fields. However, this graph-theoretic measure was underused for decades because of the inherent complexity in its computation which is closely related to solving NP-hard graph optimisation problems like MAXCUT. We develop new quadratic and linear programming models to compute the line index of balance exactly. Using the Gurobi integer programming optimisation solver, we evaluate the line index of balance on real-world and synthetic datasets. The synthetic data involves Erdős-Rényi graphs, Barabási-Albert graphs, and specially structured random graphs. We also use well known datasets from the sociology literature, such as signed graphs inferred from students' choice and rejection as well as datasets from the biology literature including gene regulatory networks. The results show that exact values of the line index of balance in relatively large signed graphs can be efficiently computed using our suggested optimisation models. We find that most real-world social networks and some biological networks have small line index of balance which indicates that they are close to balanced.
A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
Venue: arXiv cs.CG 2018
Year: 2018

This paper presents the first polynomial time algorithm to compute geodesics in a CAT(0) cubical complex in general dimension. The algorithm is a simple iterative method to update breakpoints of a path joining two points using Miller, Owen and Provan's algorithm (2015) as a subroutine. Our algorithm is applicable to any CAT(0) space in which geodesics between two close points can be computed, not limited to CAT(0) cubical complexes.
Convolutional neural networks on irregular domains based on approximate vertex-domain translations
Venue: arXiv cs.DM 2018
Year: 2018

We propose a generalization of convolutional neural networks (CNNs) to irregular domains, through the use of a translation operator on a graph structure. In regular settings such as images, convolutional layers are designed by translating a convolutional kernel over all pixels, thus enforcing translation equivariance. In the case of general graphs however, translation is not a well-defined operation, which makes shifting a convolutional kernel not straightforward. In this article, we introduce a methodology to allow the design of convolutional layers that are adapted to signals evolving on irregular topologies, even in the absence of a natural translation. Using the designed layers, we build a CNN that we train using the initial set of signals. Contrary to other approaches that aim at extending CNNs to irregular domains, we incorporate the classical settings of CNNs for 2D signals as a particular case of our approach. Designing convolutional layers in the vertex domain directly implies weight sharing, which in other approaches is generally estimated a posteriori using heuristics.
Uplink Performance Analysis in D2D-Enabled mmWave Cellular Networks with Clustered Users
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, an analytical framework is provided to analyze the uplink performance of device-to-device (D2D)-enabled millimeter wave (mmWave) cellular networks with clustered D2D user equipments (UEs). Locations of cellular UEs are modeled as a Poison Point Process (PPP), while locations of potential D2D UEs are modeled as a Poisson Cluster Process (PCP). Signal-to-interference-plus-noise ratio (SINR) outage probabilities are derived for both cellular and D2D links using tools from stochastic geometry. The distinguishing features of mmWave communications such as directional beamforming and having different path loss laws for line-of-sight (LOS) and non-line-of-sight (NLOS) links are incorporated into the outage analysis by employing a flexible mode selection scheme. Also, the effect of beamforming alignment errors on the outage probability is investigated to get insight on the performance in practical scenarios. Moreover, area spectral efficiency (ASE) of the entire network is determined for both underlay and overlay types of sharing. Optimal spectrum partition factor is determined for overlay sharing by considering the optimal weighted proportional fair spectrum partition.
One-shot and few-shot learning of word embeddings
Venue: arXiv cs.CL 2018
Year: 2018

Standard deep learning systems require thousands or millions of examples to learn a concept, and cannot integrate new concepts easily. By contrast, humans have an incredible ability to do one-shot or few-shot learning. For instance, from just hearing a word used in a sentence, humans can infer a great deal about it, by leveraging what the syntax and semantics of the surrounding words tells us. Here, we draw inspiration from this to highlight a simple technique by which deep recurrent networks can similarly exploit their prior knowledge to learn a useful representation for a new word from little data. This could make natural language processing systems much more flexible, by allowing them to learn continually from the new words they encounter.
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities
Venue: arXiv cs.IT 2018
Year: 2018

The explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. These codes can correct a small number of erasures by accessing only a small number of remaining coordinates. An $(n,r,h,a,q)$-LRC is a linear code over $\mathbb{F}_q$ of length $n$, whose codeword symbols are partitioned into $g=n/r$ local groups each of size $r$. It has $h$ global parity checks and each local group has $a$ local parity checks. Such an LRC is Maximally Recoverable (MR), if it corrects all erasure patterns which are information-theoretically correctable under the stipulated structure of local and global parity checks. We show the first non-trivial lower bounds on the field size required for MR LRCs. When $a,h$ are constant and the number of local groups $g \ge h$, while $r$ may grow with $n$, our lower bound simplifies to $q\ge Ω_{a,h}\left(n\cdot r^{\min\{a,h-2\}}\right).$ No superlinear (in $n$) lower bounds were known prior to this work for any setting of parameters. MR LRCs deployed in practice have a small number of global parities, typically $h=2,3$. We complement our lower bounds by giving constructions with small field size for $h\le 3$. For $h=2$, we give a linear field size construction. We also show a surprising application of elliptic curves and arithmetic progression free sets in the construction of MR LRCs.
Capturing the Future by Replaying the Past
Venue: arXiv cs.PL 2018
Year: 2018

Delimited continuations are the mother of all monads! So goes the slogan inspired by Filinski's 1994 paper, which showed that delimited continuations can implement any monadic effect, letting the programmer use an effect as easily as if it was built into the language. It's a shame that not many languages have delimited continuations. Luckily, exceptions and state are also the mother of all monads! In this Pearl, we show how to implement delimited continuations in terms of exceptions and state, a construction we call $\textit{thermometer continuations}$. While traditional implementations of delimited continuations require some way of "capturing" an intermediate state of the computation, the insight of thermometer continuations is to reach this intermediate state by replaying the entire computation from the start, guiding it using a recording it so that the same thing happens until the captured point. Along the way, we explain delimited continuations and monadic reflection, show how the Filinski construction lets thermometer continuations express any monadic effect, share an elegant special-case for nondeterminism, and discuss why our construction is not prevented by theoretical results that exceptions and state cannot macro-express continuations.
Toward predictive machine learning for active vision
Venue: arXiv cs.NE 2018
Year: 2018

We develop a comprehensive description of the active inference framework, as proposed by Friston (2010), under a machine-learning compliant perspective. Stemming from a biological inspiration and the auto-encoding principles, the sketch of a cognitive architecture is proposed that should provide ways to implement estimation-oriented control policies. Computer simulations illustrate the effectiveness of the approach through a foveated inspection of the input data. The pros and cons of the control policy are analyzed in detail, showing interesting promises in terms of processing compression. Though optimizing future posterior entropy over the actions set is shown enough to attain locally optimal action selection, offline calculation using class-specific saliency maps is shown better for it saves processing costs through saccades pathways pre-processing, with a negligible effect on the recognition/compression rates.
List-decodable zero-rate codes
Venue: arXiv cs.IT 2018
Year: 2018

We consider list-decoding in the zero-rate regime for two cases: the binary alphabet and the spherical codes in Euclidean space. Specifically, we study the maximal $τ\in [0,1]$ for which there exists an arrangement of $M$ balls of relative Hamming radius $τ$ in the binary hypercube (of arbitrary dimension) with the property that no point of the latter is covered by $L$ or more of them. As $M\to \infty$ the maximal $τ$ decreases to a well-known critical value $τ_L$. In this work, we prove several results on the rate of this convergence. For the binary case, we show that the rate is $Θ(M^{-1})$ when $L$ is even, thus extending the classical results of Plotkin and Levenshtein for $L=2$. For $L=3$ the rate is shown to be $Θ(M^{-\tfrac{2}{3}})$. For the similar question about spherical codes, we prove the rate is $Ω(M^{-1})$ and $O(M^{-\tfrac{2L}{L^2-L+2}})$.