OpenRaiser/Intern-Atlas huggingface dataset:
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $1 - 1/e - ε$ approximation require $Ω(n)$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $1 - 1/e - ε$ approximation using $O(\ln{n} / ε^2)$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $O(n \mathrm{poly}(\log{n}, 1/ε))$.
White matter fiber analysis using kernel dictionary learning and sparsity priors
Venue: arXiv cs.CV 2018
Year: 2018

Diffusion magnetic resonance imaging, a non-invasive tool to infer white matter fiber connections, produces a large number of streamlines containing a wealth of information on structural connectivity. The size of these tractography outputs makes further analyses complex, creating a need for methods to group streamlines into meaningful bundles. In this work, we address this by proposing a set of kernel dictionary learning and sparsity priors based methods. Proposed frameworks include L-0 norm, group sparsity, as well as manifold regularization prior. The proposed methods allow streamlines to be assigned to more than one bundle, making it more robust to overlapping bundles and inter-subject variations. We evaluate the performance of our method on a labeled set and data from Human Connectome Project. Results highlight the ability of our method to group streamlines into plausible bundles and illustrate the impact of sparsity priors on the performance of the proposed methods.
Composable Unpaired Image to Image Translation
Venue: arXiv cs.LG 2018
Year: 2018

There has been remarkable recent work in unpaired image-to-image translation. However, they're restricted to translation on single pairs of distributions, with some exceptions. In this study, we extend one of these works to a scalable multidistribution translation mechanism. Our translation models not only converts from one distribution to another but can be stacked to create composite translation functions. We show that this composite property makes it possible to generate images with characteristics not seen in the training set. We also propose a decoupled training mechanism to train multiple distributions separately, which we show, generates better samples than isolated joint training. Further, we do a qualitative and quantitative analysis to assess the plausibility of the samples. The code is made available at https://github.com/lgraesser/im2im2im.
Analogue-digital systems and the modular decomposition of physical behaviour
Venue: arXiv cs.SY 2018
Year: 2018

We take a fresh look at analogue-digital systems focussing on their physical behaviour. We model a general analogue-digital system as a physical process controlled by an algorithm by viewing the physical process as physical oracle to the algorithm, generalising the notion of Turing. We develop a theoretical framework for the specification and analysis of such systems that combines five semantical notions: actual physical behaviour, measured behaviour, predicted behaviour, computed behaviour and exceptional behaviour. Next, we consider the more general and applicable situation of complex processes that exhibit several distinct modes of physical behaviour. Thus, for their design, a set of mathematical models may be needed, each model having its own domain of application and representing a particular mode of behaviour or operation of physical reality with its own physical oracle. The models may be of disparate kinds and, furthermore, not all physical modes may even have a reliable model. We address the questions: How do we specify algorithms and software that monitor or govern a complex physical situation with many physical modes? How do we specify a portfolio of modes, and the computational problem of transitioning from using one mode to another mode as physical behaviour changes? We propose a general definition of an analogue-digital system with modes, and show how any diverse set of modes, with or without models, can be bound together, and how the transitions between modes can be determined, by constructing a data type and mode selection functions. We illustrate the ideas of physical modes and our theory by reflecting on simple examples, including driverless racing cars.
Efficient Scheduling of Serial Iterative Decoding for Zigzag Decodable Fountain Codes
Venue: arXiv cs.IT 2018
Year: 2018

Fountain codes are erasure correcting codes realizing reliable communication systems for the multicast on the Internet. The zigzag decodable fountain (ZDF) code is one of generalization of the Raptor code, i.e, applying shift operation to generate the output packets. The ZDF code is decoded by a two-stage iterative decoding algorithm, which combines the packet-wise peeling algorithm and the bit-wise peeling algorithm. By the bit-wise peeling algorithm and shift operation, ZDF codes outperform Raptor codes under iterative decoding in terms of decoding erasure rate and overhead. However, the bit-wise peeling algorithm spends long decoding time. This paper proposes a fast bit-wise decoding algorithm for the ZDF codes. Simulation results show that the proposed algorithm drastically reduces the decoding time compared with the existing algorithm.
Community Structures, Interactions and Dynamics in London's Bicycle Sharing Network
Venue: arXiv cs.SI 2018
Year: 2018

Bikesharing schemes are transportation systems that not only provide an efficient mode of transportation in congested urban areas, but also improve last-mile connectivity with public transportation and local accessibility. Bikesharing schemes around the globe generate detailed trip data sets with spatial and temporal dimensions, which, with proper mining and analysis, reveal valuable information on urban mobility patterns. In this paper, we study the London bicycle sharing dataset to explore community structures. Using a novel clustering technique, we derive distinctive behavioural patterns and assess community interactions and spatio-temporal dynamics. The analyses reveal self-contained, interconnected and hybrid clusters that mimic London's physical structure. Exploring changes over time, we find geographically isolated and specialized communities to be relatively consistent, while the remaining system exhibits volatility, especially during and around peak commuting times. By increasing our understanding of the collective behaviour of the bikesharing users, this analysis supports policy appraisal, operational decision-making and motivates improvements in infrastructure design and management.
NELL2RDF: Reading the Web, and Publishing it as Linked Data
Venue: arXiv cs.DB 2018
Year: 2018

NELL is a system that continuously reads the Web to extract knowledge in form of entities and relations between them. It has been running since January 2010 and extracted over 50,000,000 candidate statements. NELL's generated data comprises all the candidate statements together with detailed information about how it was generated. This information includes how each component of the system contributed to the extraction of the statement, as well as when that happened and how confident the system is in the veracity of the statement. However, the data is only available in an ad hoc CSV format that makes it difficult to exploit out of the context of NELL. In order to make it more usable for other communities, we adopt Linked Data principles to publish a more standardized, self-describing dataset with rich provenance metadata.
Active Learning for Efficient Testing of Student Programs
Venue: arXiv cs.SE 2018
Year: 2018

In this work, we propose an automated method to identify semantic bugs in student programs, called ATAS, which builds upon the recent advances in both symbolic execution and active learning. Symbolic execution is a program analysis technique which can generate test cases through symbolic constraint solving. Our method makes use of a reference implementation of the task as its sole input. We compare our method with a symbolic execution-based baseline on 6 programming tasks retrieved from CodeForces comprising a total of 23K student submissions. We show an average improvement of over 2.5x over the baseline in terms of runtime (thus making it more suitable for online evaluation), without a significant degradation in evaluation accuracy.
An Extended Beta-Elliptic Model and Fuzzy Elementary Perceptual Codes for Online Multilingual Writer Identification using Deep Neural Network
Venue: arXiv cs.CV 2018
Year: 2018

Actually, the ability to identify the documents authors provides more chances for using these documents for various purposes. In this paper, we present a new effective biometric writer identification system from online handwriting. The system consists of the preprocessing and the segmentation of online handwriting into a sequence of Beta strokes in a first step. Then, from each stroke, we extract a set of static and dynamic features from new proposed model that we called Extended Beta-Elliptic model and from the Fuzzy Elementary Perceptual Codes. Next, all the segments which are composed of N consecutive strokes are categorized into groups and subgroups according to their position and their geometric characteristics. Finally, Deep Neural Network is used as classifier. Experimental results reveal that the proposed system achieves interesting results as compared to those of the existing writer identification systems on Latin and Arabic scripts.
The Effect of Extremist Violence on Hateful Speech Online
Venue: arXiv cs.SI 2018
Year: 2018

User-generated content online is shaped by many factors, including endogenous elements such as platform affordances and norms, as well as exogenous elements, in particular significant events. These impact what users say, how they say it, and when they say it. In this paper, we focus on quantifying the impact of violent events on various types of hate speech, from offensive and derogatory to intimidation and explicit calls for violence. We anchor this study in a series of attacks involving Arabs and Muslims as perpetrators or victims, occurring in Western countries, that have been covered extensively by news media. These attacks have fueled intense policy debates around immigration in various fora, including online media, which have been marred by racist prejudice and hateful speech. The focus of our research is to model the effect of the attacks on the volume and type of hateful speech on two social media platforms, Twitter and Reddit. Among other findings, we observe that extremist violence tends to lead to an increase in online hate speech, particularly on messages directly advocating violence. Our research has implications for the way in which hate speech online is monitored and suggests ways in which it could be fought.
And Now for Something Completely Different: Visual Novelty in an Online Network of Designers
Venue: arXiv cs.SI 2018
Year: 2018

Novelty is a key ingredient of innovation but quantifying it is difficult. This is especially true for visual work like graphic design. Using designs shared on an online social network of professional digital designers, we measure visual novelty using statistical learning methods to compare an images features with those of images that have been created before. We then relate social network position to the novelty of the designers images. We find that on this professional platform, users with dense local networks tend to produce more novel but generally less successful images, with important exceptions. Namely, users making novel images while embedded in cohesive local networks are more successful.
Convex Relaxations and Approximations of Chance-Constrained AC-OPF Problems
Venue: arXiv cs.SY 2018
Year: 2018

This paper deals with the impact of linear approximations for the unknown nonconvex confidence region of chance-constrained AC optimal power flow problems. Such approximations are required for the formulation of tractable chance constraints. In this context, we introduce the first formulation of a chance-constrained second-order cone (SOC) OPF. The proposed formulation provides convergence guarantees due to its convexity, while it demonstrates high computational efficiency. Combined with an AC feasibility recovery, it is able to identify better solutions than chance-constrained nonconvex AC-OPF formulations. To the best of our knowledge, this paper is the first to perform a rigorous analysis of the AC feasibility recovery procedures for robust SOC-OPF problems. We identify the issues that arise from the linear approximations, and by using a reformulation of the quadratic chance constraints, we introduce new parameters able to reshape the approximation of the confidence region. We demonstrate our method on the IEEE 118-bus system.
Classifying magnetic resonance image modalities with convolutional neural networks
Venue: arXiv cs.CV 2018
Year: 2018

Magnetic Resonance (MR) imaging allows the acquisition of images with different contrast properties depending on the acquisition protocol and the magnetic properties of tissues. Many MR brain image processing techniques, such as tissue segmentation, require multiple MR contrasts as inputs, and each contrast is treated differently. Thus it is advantageous to automate the identification of image contrasts for various purposes, such as facilitating image processing pipelines, and managing and maintaining large databases via content-based image retrieval (CBIR). Most automated CBIR techniques focus on a two-step process: extracting features from data and classifying the image based on these features. We present a novel 3D deep convolutional neural network (CNN)-based method for MR image contrast classification. The proposed CNN automatically identifies the MR contrast of an input brain image volume. Specifically, we explored three classification problems: (1) identify T1-weighted (T1-w), T2-weighted (T2-w), and fluid-attenuated inversion recovery (FLAIR) contrasts, (2) identify pre vs post-contrast T1, (3) identify pre vs post-contrast FLAIR. A total of 3418 image volumes acquired from multiple sites and multiple scanners were used. To evaluate each task, the proposed model was trained on 2137 images and tested on the remaining 1281 images. Results showed that image volumes were correctly classified with 97.57% accuracy.
An AI-driven Malfunction Detection Concept for NFV Instances in 5G
Venue: arXiv cs.NI 2018
Year: 2018

Efficient network management is one of the key challenges of the constantly growing and increasingly complex wide area networks (WAN). The paradigm shift towards virtualized (NFV) and software defined networks (SDN) in the next generation of mobile networks (5G), as well as the latest scientific insights in the field of Artificial Intelligence (AI) enable the transition from manually managed networks nowadays to fully autonomic and dynamic self-organized networks (SON). This helps to meet the KPIs and reduce at the same time operational costs (OPEX). In this paper, an AI driven concept is presented for the malfunction detection in NFV applications with the help of semi-supervised learning. For this purpose, a profile of the application under test is created. This profile then is used as a reference to detect abnormal behaviour. For example, if there is a bug in the updated version of the app, it is now possible to react autonomously and roll-back the NFV app to a previous version in order to avoid network outages.
Newtonian Action Advice: Integrating Human Verbal Instruction with Reinforcement Learning
Venue: arXiv cs.HC 2018
Year: 2018

A goal of Interactive Machine Learning (IML) is to enable people without specialized training to teach agents how to perform tasks. Many of the existing machine learning algorithms that learn from human instructions are evaluated using simulated feedback and focus on how quickly the agent learns. While this is valuable information, it ignores important aspects of the human-agent interaction such as frustration. In this paper, we present the Newtonian Action Advice agent, a new method of incorporating human verbal action advice with Reinforcement Learning (RL) in a way that improves the human-agent interaction. In addition to simulations, we validated the Newtonian Action Advice algorithm by conducting a human-subject experiment. The results show that Newtonian Action Advice can perform better than Policy Shaping, a state-of-the-art IML algorithm, both in terms of RL metrics like cumulative reward and human factors metrics like frustration.
Subcarrier-Interlaced FDD for Faster-than-TDD Channel Tracking in Massive MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Canonical Massive MIMO uses time division duplex (TDD) to exploit channel reciprocity within the coherence time, avoiding feedback of channel state information (CSI), as is required for precoding at the base station. We extend the idea of exploiting reciprocity to the coherence bandwidth, allocating subcarriers of a multicarrier (OFDM)-based system in an interlaced fashion to up- and downlink, respectively, referred to as (OFDM-)subcarrier interlaced FDD (IFDD). Exploiting this "two-dimensional" channel reciprocity within both time and frequency coherence does not require any CSI feedback and, even more so, offers faster-than-TDD channel tracking. To address imperfections of actual hardware, we conducted measurements, verifying the practical viability of IFDD. As it turns out, the scheme incurs similar transmit/receive isolation issues (self-interference) as well-known from the full-duplex (FDup) literature. As will be shown, such hardware challenges like self-interference or frequency offsets are not critical for massive MIMO operation, but can be neglected as the number of antennas grows large. Finally, we quantify how IFDD allows to track the channel variations much faster than TDD over a wide range of commonly used pilot symbol rates.
Chronos: A Unifying Optimization Framework for Speculative Execution of Deadline-critical MapReduce Jobs
Venue: arXiv cs.DC 2018
Year: 2018

Meeting desired application deadlines in cloud processing systems such as MapReduce is crucial as the nature of cloud applications is becoming increasingly mission-critical and deadline-sensitive. It has been shown that the execution times of MapReduce jobs are often adversely impacted by a few slow tasks, known as stragglers, which result in high latency and deadline violations. While a number of strategies have been developed in existing work to mitigate stragglers by launching speculative or clone task attempts, none of them provides a quantitative framework that optimizes the speculative execution for offering guaranteed Service Level Agreements (SLAs) to meet application deadlines. In this paper, we bring several speculative scheduling strategies together under a unifying optimization framework, called Chronos, which defines a new metric, Probability of Completion before Deadlines (PoCD), to measure the probability that MapReduce jobs meet their desired deadlines. We systematically analyze PoCD for popular strategies including Clone, Speculative-Restart, and Speculative-Resume, and quantify their PoCD in closed-form. The result illuminates an important tradeoff between PoCD and the cost of speculative execution, measured by the total (virtual) machine time required under different strategies. We propose an optimization problem to jointly optimize PoCD and execution cost in different strategies, and develop an algorithmic solution that is guaranteed to be optimal. Chronos is prototyped on Hadoop MapReduce and evaluated against three baseline strategies using both experiments and trace-driven simulations, achieving 50% net utility increase with up to 80% PoCD and 88% cost improvements.
Automatic Detection of Indoor and Outdoor Scenarios using NMEA Message Data from GPS Receivers
Venue: arXiv cs.OH 2018
Year: 2018

Detection of indoor and outdoor scenarios is an important resource for many types of activities such as multisensor navigation and location-based services. This research presents the use of NMEA data provided by GPS receivers to characterize different types of scenarios automatically. A set of static tests was performed to evaluate metrics such as number of satellites, positioning solution geometry and carrier-to-receiver noise-density ratio values to detect possible patterns to determine indoor and outdoor scenarios. Subsequently, validation tests are applied to verify that parameters obtained are adequate.
Learning a Deep Listwise Context Model for Ranking Refinement
Venue: arXiv cs.IR 2018
Year: 2018

Learning to rank has been intensively studied and widely applied in information retrieval. Typically, a global ranking function is learned from a set of labeled data, which can achieve good performance on average but may be suboptimal for individual queries by ignoring the fact that relevant documents for different queries may have different distributions in the feature space. Inspired by the idea of pseudo relevance feedback where top ranked documents, which we refer as the \textit{local ranking context}, can provide important information about the query's characteristics, we propose to use the inherent feature distributions of the top results to learn a Deep Listwise Context Model that helps us fine tune the initial ranked list. Specifically, we employ a recurrent neural network to sequentially encode the top results using their feature vectors, learn a local context model and use it to re-rank the top results. There are three merits with our model: (1) Our model can capture the local ranking context based on the complex interactions between top results using a deep neural network; (2) Our model can be built upon existing learning-to-rank methods by directly using their extracted feature vectors; (3) Our model is trained with an attention-based loss function, which is more effective and efficient than many existing listwise methods. Experimental results show that the proposed model can significantly improve the state-of-the-art learning to rank methods on benchmark retrieval corpora.
Segmentation of both Diseased and Healthy Skin from Clinical Photographs in a Primary Care Setting
Venue: arXiv cs.CV 2018
Year: 2018

This work presents the first segmentation study of both diseased and healthy skin in standard camera photographs from a clinical environment. Challenges arise from varied lighting conditions, skin types, backgrounds, and pathological states. For study, 400 clinical photographs (with skin segmentation masks) representing various pathological states of skin are retrospectively collected from a primary care network. 100 images are used for training and fine-tuning, and 300 are used for evaluation. This distribution between training and test partitions is chosen to reflect the difficulty in amassing large quantities of labeled data in this domain. A deep learning approach is used, and 3 public segmentation datasets of healthy skin are collected to study the potential benefits of pre-training. Two variants of U-Net are evaluated: U-Net and Dense Residual U-Net. We find that Dense Residual U-Nets have a 7.8% improvement in Jaccard, compared to classical U-Net architectures (0.55 vs. 0.51 Jaccard), for direct transfer, where fine-tuning data is not utilized. However, U-Net outperforms Dense Residual U-Net for both direct training (0.83 vs. 0.80) and fine-tuning (0.89 vs. 0.88). The stark performance improvement with fine-tuning compared to direct transfer and direct training emphasizes both the need for adequate representative data of diseased skin, and the utility of other publicly available data sources for this task.