OpenRaiser/Intern-Atlas huggingface dataset:
Unified Attentional Generative Adversarial Network for Brain Tumor Segmentation From Multimodal Unpaired Images
Venue: arXiv cs.CV 2019
Year: 2019

In medical applications, the same anatomical structures may be observed in multiple modalities despite the different image characteristics. Currently, most deep models for multimodal segmentation rely on paired registered images. However, multimodal paired registered images are difficult to obtain in many cases. Therefore, developing a model that can segment the target objects from different modalities with unpaired images is significant for many clinical applications. In this work, we propose a novel two-stream translation and segmentation unified attentional generative adversarial network (UAGAN), which can perform any-to-any image modality translation and segment the target objects simultaneously in the case where two or more modalities are available. The translation stream is used to capture modality-invariant features of the target anatomical structures. In addition, to focus on segmentation-related features, we add attentional blocks to extract valuable features from the translation stream. Experiments on three-modality brain tumor segmentation indicate that UAGAN outperforms the existing methods in most cases.
Towards Explainable Music Emotion Recognition: The Route via Mid-level Features
Venue: arXiv cs.SD 2019
Year: 2019

Emotional aspects play an important part in our interaction with music. However, modelling these aspects in MIR systems have been notoriously challenging since emotion is an inherently abstract and subjective experience, thus making it difficult to quantify or predict in the first place, and to make sense of the predictions in the next. In an attempt to create a model that can give a musically meaningful and intuitive explanation for its predictions, we propose a VGG-style deep neural network that learns to predict emotional characteristics of a musical piece together with (and based on) human-interpretable, mid-level perceptual features. We compare this to predicting emotion directly with an identical network that does not take into account the mid-level features and observe that the loss in predictive performance of going through the mid-level features is surprisingly low, on average. The design of our network allows us to visualize the effects of perceptual features on individual emotion predictions, and we argue that the small loss in performance in going through the mid-level features is justified by the gain in explainability of the predictions.
Recommending Related Tables
Venue: arXiv cs.IR 2019
Year: 2019

Tables are an extremely powerful visual and interactive tool for structuring and manipulating data, making spreadsheet programs one of the most popular computer applications. In this paper we introduce and address the task of recommending related tables: given an input table, identifying and returning a ranked list of relevant tables. One of the many possible application scenarios for this task is to provide users of a spreadsheet program proactively with recommendations for related structured content on the Web. At its core, the related table recommendation task boils down to computing the similarity between a pair of tables. We develop a theoretically sound framework for performing table matching. Our approach hinges on the idea of representing table elements in multiple semantic spaces, and then combining element-level similarities using a discriminative learning model. Using a purpose-built test collection from Wikipedia tables, we demonstrate that the proposed approach delivers state-of-the-art performance.
FortuneTeller: Predicting Microarchitectural Attacks via Unsupervised Deep Learning
Venue: arXiv cs.CR 2019
Year: 2019

The growing security threat of microarchitectural attacks underlines the importance of robust security sensors and detection mechanisms at the hardware level. While there are studies on runtime detection of cache attacks, a generic model to consider the broad range of existing and future attacks is missing. Unfortunately, previous approaches only consider either a single attack variant, e.g. Prime+Probe, or specific victim applications such as cryptographic implementations. Furthermore, the state-of-the art anomaly detection methods are based on coarse-grained statistical models, which are not successful to detect anomalies in a large-scale real world systems. Thanks to the memory capability of advanced Recurrent Neural Networks (RNNs) algorithms, both short and long term dependencies can be learned more accurately. Therefore, we propose FortuneTeller, which for the first time leverages the superiority of RNNs to learn complex execution patterns and detects unseen microarchitectural attacks in real world systems. FortuneTeller models benign workload pattern from a microarchitectural standpoint in an unsupervised fashion, and then, it predicts how upcoming benign executions are supposed to behave. Potential attacks and malicious behaviors will be detected automatically, when there is a discrepancy between the predicted execution pattern and the runtime observation. We implement FortuneTeller based on the available hardware performance counters on Intel processors and it is trained with 10 million samples obtained from benign applications. For the first time, the latest attacks such as Meltdown, Spectre, Rowhammer and Zombieload are detected with one trained model and without observing these attacks during the training. We show that FortuneTeller achieves F-score of 0.9970.
Incorporating Query Term Independence Assumption for Efficient Retrieval and Ranking using Deep Neural Networks
Venue: arXiv cs.IR 2019
Year: 2019

Classical information retrieval (IR) methods, such as query likelihood and BM25, score documents independently w.r.t. each query term, and then accumulate the scores. Assuming query term independence allows precomputing term-document scores using these models---which can be combined with specialized data structures, such as inverted index, for efficient retrieval. Deep neural IR models, in contrast, compare the whole query to the document and are, therefore, typically employed only for late stage re-ranking. We incorporate query term independence assumption into three state-of-the-art neural IR models: BERT, Duet, and CKNRM---and evaluate their performance on a passage ranking task. Surprisingly, we observe no significant loss in result quality for Duet and CKNRM---and a small degradation in the case of BERT. However, by operating on each query term independently, these otherwise computationally intensive models become amenable to offline precomputation---dramatically reducing the cost of query evaluations employing state-of-the-art neural ranking models. This strategy makes it practical to use deep models for retrieval from large collections---and not restrict their usage to late stage re-ranking.
Modeling and Simulation of the Quadrtor Delivery System
Venue: arXiv cs.RO 2019
Year: 2019

Unmanned Aerial Vehicle (UAV) quadrotor is a UAV with four rotors. The quadrotor control is a difficult task because the four-wheel system is inefficient. The purpose of this paper is to provide specifications and implement a separate quad system that integrates data from the camera and IMU (Inertial Measurement Unit) to allow high -resolution optical transmission. In this paper, a separate quad system was proposed. The system specification is specified. The system application introduced the SolidWorks design of the system, the mathematical modeling of the pickup and delivery (PDP) problem. The simulation results using MATLB for model implementation and the simultaneous localization and mapp ing (SLAM) were presented using the Extended Kalman (EKF-SLAM) filter algorithm used to make the system independent. Experimental results were introduced to use the candy edge detection algorithm.
LocationSpark: In-memory Distributed Spatial Query Processing and Optimization
Venue: arXiv cs.DB 2019
Year: 2019

Due to the ubiquity of spatial data applications and the large amounts of spatial data that these applications generate and process, there is a pressing need for scalable spatial query processing. In this paper, we present new techniques for spatial query processing and optimization in an in-memory and distributed setup to address scalability. More specifically, we introduce new techniques for handling query skew, which is common in practice, and optimize communication costs accordingly. We propose a distributed query scheduler that use a new cost model to optimize the cost of spatial query processing. The scheduler generates query execution plans that minimize the effect of query skew. The query scheduler employs new spatial indexing techniques based on bitmap filters to forward queries to the appropriate local nodes. Each local computation node is responsible for optimizing and selecting its best local query execution plan based on the indexes and the nature of the spatial queries in that node. All the proposed spatial query processing and optimization techniques are prototyped inside Spark, a distributed memory-based computation system. The experimental study is based on real datasets and demonstrates that distributed spatial query processing can be enhanced by up to an order of magnitude over existing in-memory and distributed spatial systems.
Expressive power of tensor-network factorizations for probabilistic modeling, with applications from hidden Markov models to quantum machine learning
Venue: arXiv cs.LG 2019
Year: 2019

Tensor-network techniques have enjoyed outstanding success in physics, and have recently attracted attention in machine learning, both as a tool for the formulation of new learning algorithms and for enhancing the mathematical understanding of existing methods. Inspired by these developments, and the natural correspondence between tensor networks and probabilistic graphical models, we provide a rigorous analysis of the expressive power of various tensor-network factorizations of discrete multivariate probability distributions. These factorizations include non-negative tensor-trains/MPS, which are in correspondence with hidden Markov models, and Born machines, which are naturally related to local quantum circuits. When used to model probability distributions, they exhibit tractable likelihoods and admit efficient learning algorithms. Interestingly, we prove that there exist probability distributions for which there are unbounded separations between the resource requirements of some of these tensor-network factorizations. Particularly surprising is the fact that using complex instead of real tensors can lead to an arbitrarily large reduction in the number of parameters of the network. Additionally, we introduce locally purified states (LPS), a new factorization inspired by techniques for the simulation of quantum systems, with provably better expressive power than all other representations considered. The ramifications of this result are explored through numerical experiments. Our findings imply that LPS should be considered over hidden Markov models, and furthermore provide guidelines for the design of local quantum circuits for probabilistic modeling.
Asymptotic Bayes risk for Gaussian mixture in a semi-supervised setting
Venue: arXiv cs.LG 2019
Year: 2019

Semi-supervised learning (SSL) uses unlabeled data for training and has been shown to greatly improve performance when compared to a supervised approach on the labeled data available. This claim depends both on the amount of labeled data available and on the algorithm used. In this paper, we compute analytically the gap between the best fully-supervised approach using only labeled data and the best semi-supervised approach using both labeled and unlabeled data. We quantify the best possible increase in performance obtained thanks to the unlabeled data, i.e. we compute the accuracy increase due to the information contained in the unlabeled data. Our work deals with a simple high-dimensional Gaussian mixture model for the data in a Bayesian setting. Our rigorous analysis builds on recent theoretical breakthroughs in high-dimensional inference and a large body of mathematical tools from statistical physics initially developed for spin glasses.
Faster Deterministic Distributed Coloring Through Recursive List Coloring
Venue: arXiv cs.DS 2019
Year: 2019

We provide novel deterministic distributed vertex coloring algorithms. As our main result, we give a deterministic distributed algorithm to compute a $(Δ+1)$-coloring of an $n$-node graph with maximum degree $Δ$ in $2^{O(\sqrt{\logΔ})}\cdot\log n$ rounds. This improves on the best previously known time complexity for a large range of values of $Δ$. For graphs with arboricity $a$, we obtain a deterministic distributed algorithm to compute a $(2+o(1))a$-coloring in time $2^{O(\sqrt{\log a})}\cdot\log^2 n$. Further, for graphs with bounded neighborhood independence, we show that a $(Δ+1)$-coloring can be computed more efficiently in time $2^{O(\sqrt{\logΔ})} + O(\log^* n)$. This in particular implies that also a $(2Δ-1)$-edge coloring can be computed deterministically in $2^{O(\sqrt{\logΔ})} + O(\log^* n)$ rounds, which improves the best known time bound for small values of $Δ$. All results even hold for the list coloring variants of the problems. As a consequence, we also obtain an improved deterministic $2^{O(\sqrt{\logΔ})}\cdot\log^3 n$-round algorithm for $Δ$-coloring non-complete graphs with maximum degree $Δ\geq 3$. Most of our algorithms only require messages of $O(\log n)$ bits (including the $(Δ+1)$-vertex coloring algorithms). Our main technical contribution is a recursive deterministic distributed list coloring algorithm to solve list coloring problems with lists of size $Δ^{1+o(1)}$. Given some list coloring problem and an orientation of the edges, we show how to recursively divide the global color space into smaller subspaces, assign one of the subspaces to each node of the graph, and compute a new edge orientation such that for each node, the list size to out-degree ratio degrades at most by a constant factor on each recursion level.
Graph Policy Gradients for Large Scale Robot Control
Venue: arXiv cs.RO 2019
Year: 2019

In this paper, we consider the problem of learning policies to control a large number of homogeneous robots. To this end, we propose a new algorithm we call Graph Policy Gradients (GPG) that exploits the underlying graph symmetry among the robots. The curse of dimensionality one encounters when working with a large number of robots is mitigated by employing a graph convolutional neural (GCN) network to parametrize policies for the robots. The GCN reduces the dimensionality of the problem by learning filters that aggregate information among robots locally, similar to how a convolutional neural network is able to learn local features in an image. Through experiments on formation flying, we show that our proposed method is able to scale better than existing reinforcement methods that employ fully connected networks. More importantly, we show that by using our locally learned filters we are able to zero-shot transfer policies trained on just three robots to over hundred robots.
Differences in Online Course Usage and IP Geolocation Bias by Local Economic Profile
Venue: arXiv cs.CY 2019
Year: 2019

Although Massive Online Open Courses (MOOCs) have the promise to make rigorous higher education accessible to everyone, prior research has shown that registrants tend to come from backgrounds of higher socioeconomic status. In this work, I study geographically granular economic patterns in registration for HarvardX and MITx courses, and in the accuracy of identifying users' locations from their IP addresses. Using ZIP Codes identified by the MaxMind IP geolocation database, I find that per-capita registration rates correlate with economic prosperity and population density. Comparing these ZIP Codes with user-provided mailing addresses, I find evidence of bias in MaxMind geolocation: it makes greater errors, both geographically and economically, for users from more economically distressed areas; it disproportionately geolocates users to prosperous areas; and it underestimates the regressive pattern in MOOC registration. Similar economic biases may affect IP geolocation in other academic, commercial, and legal contexts.
Diverse Agents for Ad-Hoc Cooperation in Hanabi
Venue: arXiv cs.AI 2019
Year: 2019

In complex scenarios where a model of other actors is necessary to predict and interpret their actions, it is often desirable that the model works well with a wide variety of previously unknown actors. Hanabi is a card game that brings the problem of modeling other players to the forefront, but there is no agreement on how to best generate a pool of agents to use as partners in ad-hoc cooperation evaluation. This paper proposes Quality Diversity algorithms as a promising class of algorithms to generate populations for this purpose and shows an initial implementation of an agent generator based on this idea. We also discuss what metrics can be used to compare such generators, and how the proposed generator could be leveraged to help build adaptive agents for the game.
Unexplainability and Incomprehensibility of Artificial Intelligence
Venue: arXiv cs.CY 2019
Year: 2019

Explainability and comprehensibility of AI are important requirements for intelligent systems deployed in real-world domains. Users want and frequently need to understand how decisions impacting them are made. Similarly it is important to understand how an intelligent system functions for safety and security reasons. In this paper, we describe two complementary impossibility results (Unexplainability and Incomprehensibility), essentially showing that advanced AIs would not be able to accurately explain some of their decisions and for the decisions they could explain people would not understand some of those explanations.
Multi-Scale Vector Quantization with Reconstruction Trees
Venue: arXiv cs.LG 2019
Year: 2019

We propose and study a multi-scale approach to vector quantization. We develop an algorithm, dubbed reconstruction trees, inspired by decision trees. Here the objective is parsimonious reconstruction of unsupervised data, rather than classification. Contrasted to more standard vector quantization methods, such as K-means, the proposed approach leverages a family of given partitions, to quickly explore the data in a coarse to fine-- multi-scale-- fashion. Our main technical contribution is an analysis of the expected distortion achieved by the proposed algorithm, when the data are assumed to be sampled from a fixed unknown distribution. In this context, we derive both asymptotic and finite sample results under suitable regularity assumptions on the distribution. As a special case, we consider the setting where the data generating distribution is supported on a compact Riemannian sub-manifold. Tools from differential geometry and concentration of measure are useful in our analysis.
Ultra Lightweight Multiple-time Digital Signature for the Internet of Things Devices
Venue: arXiv cs.CR 2019
Year: 2019

Digital signatures are basic cryptographic tools to provide authentication and integrity in the emerging ubiquitous systems in which resource-constrained devices are expected to operate securely and efficiently. However, existing digital signatures might not be fully practical for such resource-constrained devices (e.g., medical implants) that have energy limitations. Some other computationally efficient alternatives (e.g., one-time/multiple-time signatures) may introduce high memory and/or communication overhead due to large private key and signature sizes. In this paper, our contributions are two-fold: First, we develop a new lightweight multiple-time digital signature scheme called Signer Efficient Multiple-time Elliptic Curve Signature (SEMECS), which is suitable for resource-constrained embedded devices. SEMECS achieves optimal signature and private key sizes for an EC-based signature without requiring any EC operation (e.g., EC scalar multiplication or addition) at the signer. We prove SEMECS is secure (in random oracle model) with a tight security reduction. Second, we fully implemented SEMECS on 8-bit AVR microprocessor with a comprehensive energy consumption analysis and comparison. Our experiments confirm up to 19x less battery-consumption for SEMECS as compared to its fastest (full-time) counterpart, SchnorrQ, while offering significant performance advantages over its multiple-time counterparts in various fronts. We open-source our implementation for public testing and adoption.
A Comparative Evaluation of Animation and Small Multiples for Trend Visualization on Mobile Phones
Venue: arXiv cs.HC 2019
Year: 2019

We compare the efficacy of animated and small multiples variants of scatterplots on mobile phones for comparing trends in multivariate datasets. Visualization is increasingly prevalent in mobile applications and mobile-first websites, yet there is little prior visualization research dedicated to small displays. In this paper, we build upon previous experimental research carried out on larger displays that assessed animated and non-animated variants of scatterplots. Incorporating similar experimental stimuli and tasks, we conducted an experiment where 96 crowdworker participants performed nine trend comparison tasks using their mobile phones. We found that those using a small multiples design consistently completed tasks in less time, albeit with slightly less confidence than those using an animated design. The accuracy results were more task-dependent, and we further interpret our results according to the characteristics of the individual tasks, with a specific focus on the trajectories of target and distractor data items in each task. We identify cases that appear to favor either animation or small multiples, providing new questions for further experimental research and implications for visualization design on mobile devices. Lastly, we provide a reflection on our evaluation methodology.
Near-optimal Repair of Reed-Solomon Codes with Low Sub-packetization
Venue: arXiv cs.DS 2019
Year: 2019

Minimum storage regenerating (MSR) codes are MDS codes which allow for recovery of any single erased symbol with optimal repair bandwidth, based on the smallest possible fraction of the contents downloaded from each of the other symbols. Recently, certain Reed-Solomon codes were constructed which are MSR. However, the sub-packetization of these codes is exponentially large, growing like $n^{Ω(n)}$ in the constant-rate regime. In this work, we study the relaxed notion of $ε$-MSR codes, which incur a factor of $(1+ε)$ higher than the optimal repair bandwidth, in the context of Reed-Solomon codes. We give constructions of constant-rate $ε$-MSR Reed-Solomon codes with polynomial sub-packetization of $n^{O(1/ε)}$ and thereby giving an explicit tradeoff between the repair bandwidth and sub-packetization.
Planning for target retrieval using a robotic manipulator in cluttered and occluded environments
Venue: arXiv cs.RO 2019
Year: 2019

This paper presents planning algorithms for a robotic manipulator with a fixed base in order to grasp a target object in cluttered environments. We consider a configuration of objects in a confined space with a high density so no collision-free path to the target exists. The robot must relocate some objects to retrieve the target while avoiding collisions. For fast completion of the retrieval task, the robot needs to compute a plan optimizing an appropriate objective value directly related to the execution time of the relocation plan. We propose planning algorithms that aim to minimize the number of objects to be relocated. Our objective value is appropriate for the object retrieval task because grasping and releasing objects often dominate the total running time. In addition to the algorithm working in fully known and static environments, we propose algorithms that can deal with uncertain and dynamic situations incurred by occluded views. The proposed algorithms are shown to be complete and run in polynomial time. Our methods reduce the total running time significantly compared to a baseline method (e.g., 25.1% of reduction in a known static environment with 10 objects