pwc-archive/papers-with-abstracts huggingface dataset:
Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
Authors: Benjamin Doerr
Date: 2020-04-13 00:00:00
Tasks: Heuristic Search

We argue that proven exponential upper bounds on runtimes, an established area in classic algorithms, are interesting also in heuristic search and we prove several such results. We show that any of the algorithms randomized local search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary algorithm can optimize any pseudo-Boolean weakly monotonic function under a large set of noise assumptions in a runtime that is at most exponential in the problem dimension~$n$. This drastically extends a previous such result, limited to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise with noise probability at most $1/2$, and at the same time simplifies its proof. With the same general argument, among others, we also derive a sub-exponential upper bound for the runtime of the $(1,\lambda)$ evolutionary algorithm on the OneMax problem when the offspring population size $\lambda$ is logarithmic, but below the efficiency threshold. To show that our approach can also deal with non-trivial parent population sizes, we prove an exponential upper bound for the runtime of the mutation-based version of the simple genetic algorithm on the OneMax benchmark, matching a known exponential lower bound.
A Comparison of Deep Learning Convolution Neural Networks for Liver Segmentation in Radial Turbo Spin Echo Images
Authors: Lavanya Umapathy, Mahesh Bharath Keerthivasan, Jean-Phillipe Galons, Wyatt Unger, Diego Martin, Maria I Altbach, Ali Bilgin
Date: 2020-04-13 00:00:00
Tasks: Liver Segmentation, Segmentation

Motion-robust 2D Radial Turbo Spin Echo (RADTSE) pulse sequence can provide a high-resolution composite image, T2-weighted images at multiple echo times (TEs), and a quantitative T2 map, all from a single k-space acquisition. In this work, we use a deep-learning convolutional neural network (CNN) for the segmentation of liver in abdominal RADTSE images. A modified UNET architecture with generalized dice loss objective function was implemented. Three 2D CNNs were trained, one for each image type obtained from the RADTSE sequence. On evaluating the performance of the CNNs on the validation set, we found that CNNs trained on TE images or the T2 maps had higher average dice scores than the composite images. This, in turn, implies that the information regarding T2 variation in tissues aids in improving the segmentation performance.
Complaint-driven Training Data Debugging for Query 2.0
Authors: Weiyuan Wu, Lampros Flokas, Eugene Wu, Jiannan Wang
Date: 2020-04-12 00:00:00

As the need for machine learning (ML) increases rapidly across all industry sectors, there is a significant interest among commercial database providers to support "Query 2.0", which integrates model inference into SQL queries. Debugging Query 2.0 is very challenging since an unexpected query result may be caused by the bugs in training data (e.g., wrong labels, corrupted features). In response, we propose Rain, a complaint-driven training data debugging system. Rain allows users to specify complaints over the query's intermediate or final output, and aims to return a minimum set of training examples so that if they were removed, the complaints would be resolved. To the best of our knowledge, we are the first to study this problem. A naive solution requires retraining an exponential number of ML models. We propose two novel heuristic approaches based on influence functions which both require linear retraining steps. We provide an in-depth analytical and empirical analysis of the two approaches and conduct extensive experiments to evaluate their effectiveness using four real-world datasets. Results show that Rain achieves the highest recall@k among all the baselines while still returns results interactively.
Principal Neighbourhood Aggregation for Graph Nets
Authors: Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, Petar Veličković
Date: 2020-04-12 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: Graph Classification, Graph Regression, Molecular Property Prediction, Node Classification

Graph Neural Networks (GNNs) have been shown to be effective models for different predictive tasks on graph-structured data. Recent work on their expressive power has focused on isomorphism tasks and countable feature spaces. We extend this theoretical framework to include continuous features - which occur regularly in real-world input domains and within the hidden layers of GNNs - and we demonstrate the requirement for multiple aggregation functions in this context. Accordingly, we propose Principal Neighbourhood Aggregation (PNA), a novel architecture combining multiple aggregators with degree-scalers (which generalize the sum aggregator). Finally, we compare the capacity of different models to capture and exploit the graph structure via a novel benchmark containing multiple tasks taken from classical graph theory, alongside existing benchmarks from real-world domains, all of which demonstrate the strength of our model. With this work, we hope to steer some of the GNN research towards new aggregation methods which we believe are essential in the search for powerful and robust models.
Towards an Effective and Efficient Deep Learning Model for COVID-19 Patterns Detection in X-ray Images
Authors: Eduardo Luz, Pedro Lopes Silva, Rodrigo Silva, Ludmila Silva, Gladston Moreira, David Menotti
Date: 2020-04-12 00:00:00

Confronting the pandemic of COVID-19, is nowadays one of the most prominent challenges of the human species. A key factor in slowing down the virus propagation is the rapid diagnosis and isolation of infected patients. The standard method for COVID-19 identification, the Reverse transcription polymerase chain reaction method, is time-consuming and in short supply due to the pandemic. Thus, researchers have been looking for alternative screening methods and deep learning applied to chest X-rays of patients has been showing promising results. Despite their success, the computational cost of these methods remains high, which imposes difficulties to their accessibility and availability. Thus, the main goal of this work is to propose an accurate yet efficient method in terms of memory and processing time for the problem of COVID-19 screening in chest X-rays. Methods: To achieve the defined objective we exploit and extend the EfficientNet family of deep artificial neural networks which are known for their high accuracy and low footprints in other applications. We also exploit the underlying taxonomy of the problem with a hierarchical classifier. A dataset of 13,569 X-ray images divided into healthy, non-COVID-19 pneumonia, and COVID-19 patients is used to train the proposed approaches and other 5 competing architectures. Finally, 231 images of the three classes were used to assess the quality of the methods. Results: The results show that the proposed approach was able to produce a high-quality model, with an overall accuracy of 93.9%, COVID-19, sensitivity of 96.8% and positive prediction of 100%, while having from 5 to 30 times fewer parameters than other than the other tested architectures. Larger and more heterogeneous databases are still needed for validation before claiming that deep learning can assist physicians in the task of detecting COVID-19 in X-ray images.
Large-scale Real-time Personalized Similar Product Recommendations
Authors: Zhi Liu, Yan Huang, Jing Gao, Li Chen, Dong Li
Date: 2020-04-12 00:00:00
Tasks: Collaborative Filtering, Product Recommendation

Similar product recommendation is one of the most common scenes in e-commerce. Many recommendation algorithms such as item-to-item Collaborative Filtering are working on measuring item similarities. In this paper, we introduce our real-time personalized algorithm to model product similarity and real-time user interests. We also introduce several other baseline algorithms including an image-similarity-based method, item-to-item collaborative filtering, and item2vec, and compare them on our large-scale real-world e-commerce dataset. The algorithms which achieve good offline results are also tested on the online e-commerce website. Our personalized method achieves a 10% improvement on the add-cart number in the real-world e-commerce scenario.
Learning Spatial Relationships between Samples of Patent Image Shapes
Authors: Juan Castorena, Manish Bhattarai, Diane Oyen
Date: 2020-04-12 00:00:00
Tasks: General Classification, Image Generation, Retrieval

Binary image based classification and retrieval of documents of an intellectual nature is a very challenging problem. Variations in the binary image generation mechanisms which are subject to the document artisan designer including drawing style, view-point, inclusion of multiple image components are plausible causes for increasing the complexity of the problem. In this work, we propose a method suitable to binary images which bridges some of the successes of deep learning (DL) to alleviate the problems introduced by the aforementioned variations. The method consists on extracting the shape of interest from the binary image and applying a non-Euclidean geometric neural-net architecture to learn the local and global spatial relationships of the shape. Empirical results show that our method is in some sense invariant to the image generation mechanism variations and achieves results outperforming existing methods in a patent image dataset benchmark.
VGCN-BERT: Augmenting BERT with Graph Embedding for Text Classification
Authors: Zhibin Lu, Pan Du, Jian-Yun Nie
Date: 2020-04-12 00:00:00
Tasks: Classification, General Classification, Graph Embedding, Sentence, text-classification, Text Classification

Much progress has been made recently on text classification with methods based on neural networks. In particular, models using attention mechanism such as BERT have shown to have the capability of capturing the contextual information within a sentence or document. However, their ability of capturing the global information about the vocabulary of a language is more limited. This latter is the strength of Graph Convolutional Networks (GCN). In this paper, we propose VGCN-BERT model which combines the capability of BERT with a Vocabulary Graph Convolutional Network (VGCN). Local information and global information interact through different layers of BERT, allowing them to influence mutually and to build together a final representation for classification. In our experiments on several text classification datasets, our approach outperforms BERT and GCN alone, and achieve higher effectiveness than that reported in previous studies.
Visual Grounding Methods for VQA are Working for the Wrong Reasons!
Authors: Robik Shrestha, Kushal Kafle, Christopher Kanan
Date: 2020-04-12 00:00:00
Proceeding: ACL 2020 6
Tasks: Question Answering, Visual Grounding, Visual Question Answering, Visual Question Answering (VQA)

Existing Visual Question Answering (VQA) methods tend to exploit dataset biases and spurious statistical correlations, instead of producing right answers for the right reasons. To address this issue, recent bias mitigation methods for VQA propose to incorporate visual cues (e.g., human attention maps) to better ground the VQA models, showcasing impressive gains. However, we show that the performance improvements are not a result of improved visual grounding, but a regularization effect which prevents over-fitting to linguistic priors. For instance, we find that it is not actually necessary to provide proper, human-based cues; random, insensible cues also result in similar improvements. Based on this observation, we propose a simpler regularization scheme that does not require any external annotations and yet achieves near state-of-the-art performance on VQA-CPv2.
DarkneTZ: Towards Model Privacy at the Edge using Trusted Execution Environments
Authors: Fan Mo, Ali Shahin Shamsabadi, Kleomenis Katevas, Soteris Demetriou, Ilias Leontiadis, Andrea Cavallaro, Hamed Haddadi
Date: 2020-04-12 00:00:00
Tasks: CPU, image-classification, Image Classification

We present DarkneTZ, a framework that uses an edge device's Trusted Execution Environment (TEE) in conjunction with model partitioning to limit the attack surface against Deep Neural Networks (DNNs). Increasingly, edge devices (smartphones and consumer IoT devices) are equipped with pre-trained DNNs for a variety of applications. This trend comes with privacy risks as models can leak information about their training data through effective membership inference attacks (MIAs). We evaluate the performance of DarkneTZ, including CPU execution time, memory usage, and accurate power consumption, using two small and six large image classification models. Due to the limited memory of the edge device's TEE, we partition model layers into more sensitive layers (to be executed inside the device TEE), and a set of layers to be executed in the untrusted part of the operating system. Our results show that even if a single layer is hidden, we can provide reliable model privacy and defend against state of the art MIAs, with only 3% performance overhead. When fully utilizing the TEE, DarkneTZ provides model protections with up to 10% overhead.
Y-net: Biomedical Image Segmentation and Clustering
Authors: Sharmin Pathan, Anant Tripathi
Date: 2020-04-12 00:00:00
Tasks: Clustering, Deep Clustering, Image Segmentation, Medical Image Analysis, Segmentation, Semantic Segmentation, Survival Prediction

We propose a deep clustering architecture alongside image segmentation for medical image analysis. The main idea is based on unsupervised learning to cluster images on severity of the disease in the subject's sample, and this image is then segmented to highlight and outline regions of interest. We start with training an autoencoder on the images for segmentation. The encoder part from the autoencoder branches out to a clustering node and segmentation node. Deep clustering using Kmeans clustering is performed at the clustering branch and a lightweight model is used for segmentation. Each of the branches use extracted features from the autoencoder. We demonstrate our results on ISIC 2018 Skin Lesion Analysis Towards Melanoma Detection and Cityscapes datasets for segmentation and clustering. The proposed architecture beats UNet and DeepLab results on the two datasets, and has less than half the number of parameters. We use the deep clustering branch for clustering images into four clusters. Our approach can be applied to work with high complexity datasets of medical imaging for analyzing survival prediction for severe diseases or customizing treatment based on how far the disease has propagated. Clustering patients can help understand how binning should be done on real valued features to reduce feature sparsity and improve accuracy on classification tasks. The proposed architecture can provide an early diagnosis and reduce human intervention on labeling as it can become quite costly as the datasets grow larger. The main idea is to propose a one shot approach to segmentation with deep clustering.
SFE-GACN: A Novel Unknown Attack Detection Method Using Intra Categories Generation in Embedding Space
Authors: Ao Liu, Yunpeng Wang, Tao Li
Date: 2020-04-12 00:00:00
Tasks: Data Augmentation, Generative Adversarial Network, Intrusion Detection

In the encrypted network traffic intrusion detection, deep learning based schemes have attracted lots of attention. However, in real-world scenarios, data is often insufficient (few-shot), which leads to various deviations between the models prediction and the ground truth. Consequently, downstream tasks such as unknown attack detection based on few-shot will be limited by insufficient data. In this paper, we propose a novel unknown attack detection method based on Intra Categories Generation in Embedding Space, namely SFE-GACN, which might be the solution of few-shot problem. Concretely, we first proposed Session Feature Embedding (SFE) to summarize the context of sessions (session is the basic granularity of network traffic), bring the insufficient data to the pre-trained embedding space. In this way, we achieve the goal of preliminary information extension in the few-shot case. Second, we further propose the Generative Adversarial Cooperative Network (GACN), which improves the conventional Generative Adversarial Network by supervising the generated sample to avoid falling into similar categories, and thus enables samples to generate intra categories. Our proposed SFE-GACN can accurately generate session samples in the case of few-shot, and ensure the difference between categories during data augmentation. The detection results show that, compared to the state-of-the-art method, the average TPR is 8.38% higher, and the average FPR is 12.77% lower. In addition, we evaluated the graphics generation capabilities of GACN on the graphics dataset, the result shows our proposed GACN can be popularized for generating easy-confused multi-categories graphics.
Measuring spatial uniformity with the hypersphere chord length distribution
Authors: Panagiotis Sidiropoulos
Date: 2020-04-12 00:00:00

Data uniformity is a concept associated with several semantic data characteristics such as lack of features, correlation and sample bias. This article introduces a novel measure to assess data uniformity and detect uniform pointsets on high-dimensional Euclidean spaces. Spatial uniformity measure builds upon the isomorphism between hyperspherical chords and L2-normalised data Euclidean distances, which is implied by the fact that, in Euclidean spaces, L2-normalised data can be geometrically defined as points on a hypersphere. The imposed connection between the distance distribution of uniformly selected points and the hyperspherical chord length distribution is employed to quantify uniformity. More specifically,, the closed-form expression of hypersphere chord length distribution is revisited extended, before examining a few qualitative and quantitative characteristics of this distribution that can be rather straightforwardly linked to data uniformity. The experimental section includes validation in four distinct setups, thus substantiating the potential of the new uniformity measure on practical data-science applications.
Active Sampling for Pairwise Comparisons via Approximate Message Passing and Information Gain Maximization
Authors: Aliaksei Mikhailiuk, Clifford Wilmot, Maria Perez-Ortiz, Dingcheng Yue, Rafal Mantiuk
Date: 2020-04-12 00:00:00
Tasks: GPU, Video Quality Assessment

Pairwise comparison data arise in many domains with subjective assessment experiments, for example in image and video quality assessment. In these experiments observers are asked to express a preference between two conditions. However, many pairwise comparison protocols require a large number of comparisons to infer accurate scores, which may be unfeasible when each comparison is time-consuming (e.g. videos) or expensive (e.g. medical imaging). This motivates the use of an active sampling algorithm that chooses only the most informative pairs for comparison. In this paper we propose ASAP, an active sampling algorithm based on approximate message passing and expected information gain maximization. Unlike most existing methods, which rely on partial updates of the posterior distribution, we are able to perform full updates and therefore much improve the accuracy of the inferred scores. The algorithm relies on three techniques for reducing computational cost: inference based on approximate message passing, selective evaluations of the information gain, and selecting pairs in a batch that forms a minimum spanning tree of the inverse of information gain. We demonstrate, with real and synthetic data, that ASAP offers the highest accuracy of inferred scores compared to the existing methods. We also provide an open-source GPU implementation of ASAP for large-scale experiments.
XtremeDistil: Multi-stage Distillation for Massive Multilingual Models
Authors: Subhabrata Mukherjee, Ahmed Awadallah
Date: 2020-04-12 00:00:00
Proceeding: ACL 2020 6
Tasks: Knowledge Distillation, named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER

Deep and large pre-trained language models are the state-of-the-art for various natural language processing tasks. However, the huge size of these models could be a deterrent to use them in practice. Some recent and concurrent works use knowledge distillation to compress these huge models into shallow ones. In this work we study knowledge distillation with a focus on multi-lingual Named Entity Recognition (NER). In particular, we study several distillation strategies and propose a stage-wise optimization scheme leveraging teacher internal representations that is agnostic of teacher architecture and show that it outperforms strategies employed in prior works. Additionally, we investigate the role of several factors like the amount of unlabeled data, annotation resources, model architecture and inference latency to name a few. We show that our approach leads to massive compression of MBERT-like teacher models by upto 35x in terms of parameters and 51x in terms of latency for batch inference while retaining 95% of its F1-score for NER over 41 languages.
Low-Resolution Overhead Thermal Tripwire for Occupancy Estimation
Authors: Mertcan Cokbas, Prakash Ishwar, Janusz Konrad
Date: 2020-04-12 00:00:00

Smart buildings use occupancy sensing for various tasks ranging from energy-efficient HVAC and lighting to space-utilization analysis and emergency response. We propose a people counting system which uses a low-resolution thermal sensor. Unlike previous people-counting systems based on thermal sensors, we use an overhead tripwire configuration at entryways to detect and track transient entries or exits. We develop two distinct people counting algorithms for this configuration. To evaluate our algorithms, we have collected and labeled a low-resolution thermal video dataset using the proposed system. The dataset, the first of its kind, is public and available for download. We also propose new evaluation metrics that are more suitable for systems that are subject to drift and jitter.
PatchAttack: A Black-box Texture-based Attack with Reinforcement Learning
Authors: Chenglin Yang, Adam Kortylewski, Cihang Xie, Yinzhi Cao, Alan Yuille
Date: 2020-04-12 00:00:00
Proceeding: ECCV 2020 8
Tasks: Adversarial Defense, Clustering, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Patch-based attacks introduce a perceptible but localized change to the input that induces misclassification. A limitation of current patch-based black-box attacks is that they perform poorly for targeted attacks, and even for the less challenging non-targeted scenarios, they require a large number of queries. Our proposed PatchAttack is query efficient and can break models for both targeted and non-targeted attacks. PatchAttack induces misclassifications by superimposing small textured patches on the input image. We parametrize the appearance of these patches by a dictionary of class-specific textures. This texture dictionary is learned by clustering Gram matrices of feature activations from a VGG backbone. PatchAttack optimizes the position and texture parameters of each patch using reinforcement learning. Our experiments show that PatchAttack achieves > 99% success rate on ImageNet for a wide range of architectures, while only manipulating 3% of the image for non-targeted attacks and 10% on average for targeted attacks. Furthermore, we show that PatchAttack circumvents state-of-the-art adversarial defense methods successfully.