OpenRaiser/Intern-Atlas huggingface dataset:
Deep Generative Dual Memory Network for Continual Learning
Venue: arXiv cs.LG 2018
Year: 2018

Despite advances in deep learning, neural networks can only learn multiple tasks when trained on them jointly. When tasks arrive sequentially, they lose performance on previously learnt tasks. This phenomenon called catastrophic forgetting is a fundamental challenge to overcome before neural networks can learn continually from incoming data. In this work, we derive inspiration from human memory to develop an architecture capable of learning continuously from sequentially incoming tasks, while averting catastrophic forgetting. Specifically, our contributions are: (i) a dual memory architecture emulating the complementary learning systems (hippocampus and the neocortex) in the human brain, (ii) memory consolidation via generative replay of past experiences, (iii) demonstrating advantages of generative replay and dual memories via experiments, and (iv) improved performance retention on challenging tasks even for low capacity models. Our architecture displays many characteristics of the mammalian memory and provides insights on the connection between sleep and learning.
Inducing Regular Grammars Using Recurrent Neural Networks
Venue: arXiv cs.CL 2018
Year: 2018

Grammar induction is the task of learning a grammar from a set of examples. Recently, neural networks have been shown to be powerful learning machines that can identify patterns in streams of data. In this work we investigate their effectiveness in inducing a regular grammar from data, without any assumptions about the grammar. We train a recurrent neural network to distinguish between strings that are in or outside a regular language, and utilize an algorithm for extracting the learned finite-state automaton. We apply this method to several regular languages and find unexpected results regarding the connections between the network's states that may be regarded as evidence for generalization.
Learning to diagnose from scratch by exploiting dependencies among labels
Venue: arXiv cs.CV 2018
Year: 2018

The field of medical diagnostics contains a wealth of challenges which closely resemble classical machine learning problems; practical constraints, however, complicate the translation of these endpoints naively into classical architectures. Many tasks in radiology, for example, are largely problems of multi-label classification wherein medical images are interpreted to indicate multiple present or suspected pathologies. Clinical settings drive the necessity for high accuracy simultaneously across a multitude of pathological outcomes and greatly limit the utility of tools which consider only a subset. This issue is exacerbated by a general scarcity of training data and maximizes the need to extract clinically relevant features from available samples -- ideally without the use of pre-trained models which may carry forward undesirable biases from tangentially related tasks. We present and evaluate a partial solution to these constraints in using LSTMs to leverage interdependencies among target labels in predicting 14 pathologic patterns from chest x-rays and establish state of the art results on the largest publicly available chest x-ray dataset from the NIH without pre-training. Furthermore, we propose and discuss alternative evaluation metrics and their relevance in clinical practice.
SGDLibrary: A MATLAB library for stochastic gradient descent algorithms
Venue: arXiv cs.MS 2018
Year: 2018

We consider the problem of finding the minimizer of a function $f: \mathbb{R}^d \rightarrow \mathbb{R}$ of the finite-sum form $\min f(w) = 1/n\sum_{i}^n f_i(w)$. This problem has been studied intensively in recent years in the field of machine learning (ML). One promising approach for large-scale data is to use a stochastic optimization algorithm to solve the problem. SGDLibrary is a readable, flexible and extensible pure-MATLAB library of a collection of stochastic optimization algorithms. The purpose of the library is to provide researchers and implementers a comprehensive evaluation environment for the use of these algorithms on various ML problems.
Rate-Splitting Multiple Access for Downlink Communication Systems: Bridging, Generalizing and Outperforming SDMA and NOMA
Venue: arXiv cs.IT 2018
Year: 2018

Space-Division Multiple Access (SDMA) utilizes linear precoding to separate users in the spatial domain and relies on fully treating any residual multi-user interference as noise. Non-Orthogonal Multiple Access (NOMA) uses linearly precoded superposition coding with successive interference cancellation (SIC) and relies on user grouping and ordering to enforce some users to fully decode and cancel interference created by other users. In this paper, we argue that to efficiently cope with the high throughput, heterogeneity of Quality-of-Service (QoS), and massive connectivity requirements of future multi-antenna wireless networks, multiple access design needs to depart from SDMA and NOMA. We develop a novel multiple access framework, called Rate-Splitting Multiple Access (RSMA). RSMA is a more general and powerful multiple access for downlink multi-antenna systems that contains SDMA and NOMA as special cases. RSMA relies on linearly precoded rate-splitting with SIC to decode part of the interference and treat the remaining part of the interference as noise. This capability of RSMA to partially decode interference and partially treat interference as noise enables to softly bridge the two extremes of fully decoding interference and treating interference as noise, and provide room for rate and QoS enhancements, and complexity reduction. The three multiple access schemes are compared and extensive numerical results show that RSMA provides a smooth transition between SDMA and NOMA and outperforms them both in a wide range of network loads (underloaded and overloaded regimes) and user deployments (with a diversity of channel directions, channel strengths and qualities of Channel State Information at the Transmitter). Moreover, RSMA provides rate and QoS enhancements over NOMA at a lower computational complexity for the transmit scheduler and the receivers (number of SIC layers).
Approximation Algorithms for $\ell_0$-Low Rank Approximation
Venue: arXiv cs.DS 2018
Year: 2018

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matrix $A$, to output a rank-$k$ matrix $A'$ for which $\|A'-A\|_0$ is minimized. Here, for a matrix $B$, $\|B\|_0$ denotes the number of its non-zero entries. This NP-hard variant of low rank approximation is natural for problems with no underlying metric, and its goal is to minimize the number of disagreeing data positions. We provide approximation algorithms which significantly improve the running time and approximation factor of previous work. For $k > 1$, we show how to find, in poly$(mn)$ time for every $k$, a rank $O(k \log(n/k))$ matrix $A'$ for which $\|A'-A\|_0 \leq O(k^2 \log(n/k)) \mathrm{OPT}$. To the best of our knowledge, this is the first algorithm with provable guarantees for the $\ell_0$-Low Rank Approximation Problem for $k > 1$, even for bicriteria algorithms. For the well-studied case when $k = 1$, we give a $(2+ε)$-approximation in {\it sublinear time}, which is impossible for other variants of low rank approximation such as for the Frobenius norm. We strengthen this for the well-studied case of binary matrices to obtain a $(1+O(ψ))$-approximation in sublinear time, where $ψ= \mathrm{OPT}/\lVert A\rVert_0$. For small $ψ$, our approximation factor is $1+o(1)$.
Algorithmic learning of probability distributions from random data in the limit
Venue: arXiv cs.LG 2018
Year: 2018

We study the problem of identifying a probability distribution for some given randomly sampled data in the limit, in the context of algorithmic learning theory as proposed recently by Vinanyi and Chater. We show that there exists a computable partial learner for the computable probability measures, while by Bienvenu, Monin and Shen it is known that there is no computable learner for the computable probability measures. Our main result is the characterization of the oracles that compute explanatory learners for the computable (continuous) probability measures as the high oracles. This provides an analogue of a well-known result of Adleman and Blum in the context of learning computable probability distributions. We also discuss related learning notions such as behaviorally correct learning and orther variations of explanatory learning, in the context of learning probability distributions from data.
Reshaping Cellular Networks for the Sky: Major Factors and Feasibility
Venue: arXiv cs.NI 2018
Year: 2018

This paper studies the feasibility of supporting drone operations using existent cellular infrastructure. We propose an analytical framework that includes the effects of base station (BS) height and antenna radiation pattern, drone antenna directivity and various propagation environments. With this framework, we derive an exact expression for the coverage probability of ground and drone users through a practical cell association strategy. Our results show that a carefully designed network can control the radiated interference that is received by the drones, and therefore guarantees a satisfactory quality of service. Moreover, as the network density grows the increasing level of interference can be partially managed by lowering the drone flying altitude. However, even at optimal conditions the drone coverage performance converges to zero considerably fast, suggesting that ultra-dense networks might be poor candidates for serving aerial users.
Manipulation Strategies for the Rank Maximal Matching Problem
Venue: arXiv cs.DS 2018
Year: 2018

We consider manipulation strategies for the rank-maximal matching problem. In the rank-maximal matching problem we are given a bipartite graph $G = (A \cup P, E)$ such that $A$ denotes a set of applicants and $P$ a set of posts. Each applicant $a \in A$ has a preference list over the set of his neighbours in $G$, possibly involving ties. Preference lists are represented by ranks on the edges - an edge $(a,p)$ has rank $i$, denoted as $rank(a,p)=i$, if post $p$ belongs to one of $a$'s $i$-th choices. A rank-maximal matching is one in which the maximum number of applicants is matched to their rank one posts and subject to this condition, the maximum number of applicants is matched to their rank two posts, and so on. A rank-maximal matching can be computed in $O(\min(c \sqrt{n},n) m)$ time, where $n$ denotes the number of applicants, $m$ the number of edges and $c$ the maximum rank of an edge in an optimal solution. A central authority matches applicants to posts. It does so using one of the rank-maximal matchings. Since there may be more than one rank- maximal matching of $G$, we assume that the central authority chooses any one of them randomly. Let $a_1$ be a manipulative applicant, who knows the preference lists of all the other applicants and wants to falsify his preference list so that he has a chance of getting better posts than if he were truthful. In the first problem addressed in this paper the manipulative applicant $a_1$ wants to ensure that he is never matched to any post worse than the most preferred among those of rank greater than one and obtainable when he is truthful. In the second problem the manipulator wants to construct such a preference list that the worst post he can become matched to by the central authority is best possible or in other words, $a_1$ wants to minimize the maximal rank of a post he can become matched to.
Scheduling Monotone Moldable Jobs in Linear Time
Venue: arXiv cs.DS 2018
Year: 2018

A moldable job is a job that can be executed on an arbitrary number of processors, and whose processing time depends on the number of processors allotted to it. A moldable job is monotone if its work doesn't decrease for an increasing number of allotted processors. We consider the problem of scheduling monotone moldable jobs to minimize the makespan. We argue that for certain compact input encodings a polynomial algorithm has a running time polynomial in n and log(m), where n is the number of jobs and m is the number of machines. We describe how monotony of jobs can be used to counteract the increased problem complexity that arises from compact encodings, and give tight bounds on the approximability of the problem with compact encoding: it is NP-hard to solve optimally, but admits a PTAS. The main focus of this work are efficient approximation algorithms. We describe different techniques to exploit the monotony of the jobs for better running times, and present a (3/2+ε)-approximate algorithm whose running time is polynomial in log(m) and 1/ε, and only linear in the number n of jobs.
Interpretable and Pedagogical Examples
Venue: arXiv cs.AI 2018
Year: 2018

Teachers intentionally pick the most informative examples to show their students. However, if the teacher and student are neural networks, the examples that the teacher network learns to give, although effective at teaching the student, are typically uninterpretable. We show that training the student and teacher iteratively, rather than jointly, can produce interpretable teaching strategies. We evaluate interpretability by (1) measuring the similarity of the teacher's emergent strategies to intuitive strategies in each domain and (2) conducting human experiments to evaluate how effective the teacher's strategies are at teaching humans. We show that the teacher network learns to select or generate interpretable, pedagogical examples to teach rule-based, probabilistic, boolean, and hierarchical concepts.
The Complexity of Finding Small Separators in Temporal Graphs
Venue: arXiv cs.DS 2018
Year: 2018

Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.
Ω-Net (Omega-Net): Fully Automatic, Multi-View Cardiac MR Detection, Orientation, and Segmentation with Deep Neural Networks
Venue: arXiv cs.CV 2018
Year: 2018

Pixelwise segmentation of the left ventricular (LV) myocardium and the four cardiac chambers in 2-D steady state free precession (SSFP) cine sequences is an essential preprocessing step for a wide range of analyses. Variability in contrast, appearance, orientation, and placement of the heart between patients, clinical views, scanners, and protocols makes fully automatic semantic segmentation a notoriously difficult problem. Here, we present $Ω$-Net (Omega-Net): a novel convolutional neural network (CNN) architecture for simultaneous localization, transformation into a canonical orientation, and semantic segmentation. First, an initial segmentation is performed on the input image, second, the features learned during this initial segmentation are used to predict the parameters needed to transform the input image into a canonical orientation, and third, a final segmentation is performed on the transformed image. In this work, $Ω$-Nets of varying depths were trained to detect five foreground classes in any of three clinical views (short axis, SA, four-chamber, 4C, two-chamber, 2C), without prior knowledge of the view being segmented. The architecture was trained on a cohort of patients with hypertrophic cardiomyopathy and healthy control subjects. Network performance as measured by weighted foreground intersection-over-union (IoU) was substantially improved in the best-performing $Ω$- Net compared with U-Net segmentation without localization or orientation. In addition, Ω-Net was retrained from scratch on the 2017 MICCAI ACDC dataset, and achieves state-of-the-art results on the LV and RV bloodpools, and performed slightly worse in segmentation of the LV myocardium. We conclude this architecture represents a substantive advancement over prior approaches, with implications for biomedical image segmentation more generally.
A Fast Successive Over-Relaxation Algorithm for Force-Directed Network Graph Drawing
Venue: arXiv cs.CG 2018
Year: 2018

Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing large- scale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.
A Tight Approximation for Fully Dynamic Bin Packing without Bundling
Venue: arXiv cs.DS 2018
Year: 2018

We consider a variant of the classical Bin Packing Problem, called Fully Dynamic Bin Packing. In this variant, items of a size in $(0,1]$ must be packed in bins of unit size. In each time step, an item either arrives or departs from the packing. An algorithm for this problem must maintain a feasible packing while only repacking a bounded number of items in each time step. We develop an algorithm which repacks only a constant number of items per time step and, unlike previous work, does not rely on bundling of small items which allowed those solutions to move an unbounded number of small items as one. Our algorithm has an asymptotic approximation ratio of roughly $1.3871$ which is complemented by a lower bound of Balogh et al., resulting in a tight approximation ratio for this problem. As a direct corollary, we also close the gap to the lower bound of the Relaxed Online Bin Packing Problem in which only insertions of items occur.
ReBNet: Residual Binarized Neural Network
Venue: arXiv cs.LG 2018
Year: 2018

This paper proposes ReBNet, an end-to-end framework for training reconfigurable binary neural networks on software and developing efficient accelerators for execution on FPGA. Binary neural networks offer an intriguing opportunity for deploying large-scale deep learning models on resource-constrained devices. Binarization reduces the memory footprint and replaces the power-hungry matrix-multiplication with light-weight XnorPopcount operations. However, binary networks suffer from a degraded accuracy compared to their fixed-point counterparts. We show that the state-of-the-art methods for optimizing binary networks accuracy, significantly increase the implementation cost and complexity. To compensate for the degraded accuracy while adhering to the simplicity of binary networks, we devise the first reconfigurable scheme that can adjust the classification accuracy based on the application. Our proposition improves the classification accuracy by representing features with multiple levels of residual binarization. Unlike previous methods, our approach does not exacerbate the area cost of the hardware accelerator. Instead, it provides a tradeoff between throughput and accuracy while the area overhead of multi-level binarization is negligible.
RF Wireless Power Transfer: Regreening Future Networks
Venue: arXiv cs.IT 2018
Year: 2018

Green radio communication is an emerging topic since the overall footprint of information and communication technology (ICT) services is predicted to triple between 2007 and 2020. Given this research line, energy harvesting (EH) and wireless power transfer (WPT) networks can be evaluated as promising approaches. In this paper, an overview of recent trends for future green networks on the platforms of EH and WPT is provided. By rethinking the application of radio frequency (RF)-WPT, a new concept, namely green RF-WTP, is introduced. Accordingly, opening challenges and promising combinations among current technologies, such as small-cell, millimeter (mm)-wave, and Internet of Things (IoT) networks, are discussed in details to seek solutions for the question with how to re-green the future networks?
Differentially Private ANOVA Testing
Venue: arXiv cs.CR 2018
Year: 2018

Modern society generates an incredible amount of data about individuals, and releasing summary statistics about this data in a manner that provably protects individual privacy would offer a valuable resource for researchers in many fields. We present the first algorithm for analysis of variance (ANOVA) that preserves differential privacy, allowing this important statistical test to be conducted (and the results released) on databases of sensitive information. In addition to our private algorithm for the F test statistic, we show a rigorous way to compute p-values that accounts for the added noise needed to preserve privacy. Finally, we present experimental results quantifying the statistical power of this differentially private version of the test, finding that a sample of several thousand observations is frequently enough to detect variation between groups. The differentially private ANOVA algorithm is a promising approach for releasing a common test statistic that is valuable in fields in the sciences and social sciences.
Transaction Fraud Detection Using GRU-centered Sandwich-structured Model
Venue: arXiv cs.CR 2018
Year: 2018

Rapid growth of modern technologies such as internet and mobile computing are bringing dramatically increased e-commerce payments, as well as the explosion in transaction fraud. Meanwhile, fraudsters are continually refining their tricks, making rule-based fraud detection systems difficult to handle the ever-changing fraud patterns. Many data mining and artificial intelligence methods have been proposed for identifying small anomalies in large transaction data sets, increasing detecting efficiency to some extent. Nevertheless, there is always a contradiction that most methods are irrelevant to transaction sequence, yet sequence-related methods usually cannot learn information at single-transaction level well. In this paper, a new "within->between->within" sandwich-structured sequence learning architecture has been proposed by stacking an ensemble method, a deep sequential learning method and another top-layer ensemble classifier in proper order. Moreover, attention mechanism has also been introduced in to further improve performance. Models in this structure have been manifested to be very efficient in scenarios like fraud detection, where the information sequence is made up of vectors with complex interconnected features.