pwc-archive/papers-with-abstracts huggingface dataset:
Streaming Complexity of SVMs
Authors: Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff
Date: 2020-07-07 00:00:00

We study the space complexity of solving the bias-regularized SVM problem in the streaming model. This is a classic supervised learning problem that has drawn lots of attention, including for developing fast algorithms for solving the problem approximately. One of the most widely used algorithms for approximately optimizing the SVM objective is Stochastic Gradient Descent (SGD), which requires only $O(\frac{1}{\lambda\epsilon})$ random samples, and which immediately yields a streaming algorithm that uses $O(\frac{d}{\lambda\epsilon})$ space. For related problems, better streaming algorithms are only known for smooth functions, unlike the SVM objective that we focus on in this work. We initiate an investigation of the space complexity for both finding an approximate optimum of this objective, and for the related ``point estimation'' problem of sketching the data set to evaluate the function value $F_\lambda$ on any query $(\theta, b)$. We show that, for both problems, for dimensions $d=1,2$, one can obtain streaming algorithms with space polynomially smaller than $\frac{1}{\lambda\epsilon}$, which is the complexity of SGD for strongly convex functions like the bias-regularized SVM, and which is known to be tight in general, even for $d=1$. We also prove polynomial lower bounds for both point estimation and optimization. In particular, for point estimation we obtain a tight bound of $\Theta(1/\sqrt{\epsilon})$ for $d=1$ and a nearly tight lower bound of $\widetilde{\Omega}(d/{\epsilon}^2)$ for $d = \Omega( \log(1/\epsilon))$. Finally, for optimization, we prove a $\Omega(1/\sqrt{\epsilon})$ lower bound for $d = \Omega( \log(1/\epsilon))$, and show similar bounds when $d$ is constant.
Scribble-based Domain Adaptation via Co-segmentation
Authors: Reuben Dorent, Samuel Joutard, Jonathan Shapey, Sotirios Bisdas, Neil Kitchen, Robert Bradford, Shakeel Saeed, Marc Modat, Sebastien Ourselin, Tom Vercauteren
Date: 2020-07-07 00:00:00
Tasks: Domain Adaptation, Image Segmentation, Medical Image Segmentation, Segmentation, Semantic Segmentation

Although deep convolutional networks have reached state-of-the-art performance in many medical image segmentation tasks, they have typically demonstrated poor generalisation capability. To be able to generalise from one domain (e.g. one imaging modality) to another, domain adaptation has to be performed. While supervised methods may lead to good performance, they require to fully annotate additional data which may not be an option in practice. In contrast, unsupervised methods don't need additional annotations but are usually unstable and hard to train. In this work, we propose a novel weakly-supervised method. Instead of requiring detailed but time-consuming annotations, scribbles on the target domain are used to perform domain adaptation. This paper introduces a new formulation of domain adaptation based on structured learning and co-segmentation. Our method is easy to train, thanks to the introduction of a regularised loss. The framework is validated on Vestibular Schwannoma segmentation (T1 to T2 scans). Our proposed method outperforms unsupervised approaches and achieves comparable performance to a fully-supervised approach.
Strong Generalization and Efficiency in Neural Programs
Authors: Yujia Li, Felix Gimeno, Pushmeet Kohli, Oriol Vinyals
Date: 2020-07-07 00:00:00
Tasks: Program induction

We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes, achieving strong generalization. Moreover, by using reinforcement learning, we optimize for program efficiency metrics, and discover new algorithms that surpass the teacher used in imitation. With this, our approach can learn to outperform custom-written solutions for a variety of problems, as we tested it on sorting, searching in ordered lists and the NP-complete 0/1 knapsack problem, which sets a notable milestone in the field of Neural Program Induction. As highlights, our learned model can perform sorting perfectly on any input data size we tested on, with $O(n log n)$ complexity, whilst outperforming hand-coded algorithms, including quick sort, in number of operations even for list sizes far beyond those seen during training.
What Gives the Answer Away? Question Answering Bias Analysis on Video QA Datasets
Authors: Jianing Yang, Yuying Zhu, Yongxin Wang, Ruitao Yi, Amir Zadeh, Louis-Philippe Morency
Date: 2020-07-07 00:00:00
Tasks: Multiple-choice, Question Answering, Video Question Answering

Question answering biases in video QA datasets can mislead multimodal model to overfit to QA artifacts and jeopardize the model's ability to generalize. Understanding how strong these QA biases are and where they come from helps the community measure progress more accurately and provide researchers insights to debug their models. In this paper, we analyze QA biases in popular video question answering datasets and discover pretrained language models can answer 37-48% questions correctly without using any multimodal context information, far exceeding the 20% random guess baseline for 5-choose-1 multiple-choice questions. Our ablation study shows biases can come from annotators and type of questions. Specifically, annotators that have been seen during training are better predicted by the model and reasoning, abstract questions incur more biases than factual, direct questions. We also show empirically that using annotator-non-overlapping train-test splits can reduce QA biases for video QA datasets.
Can GAN Generated Morphs Threaten Face Recognition Systems Equally as Landmark Based Morphs? -- Vulnerability and Detection
Authors: Sushma Venkatesh, Haoyu Zhang, Raghavendra Ramachandra, Kiran Raja, Naser Damer, Christoph Busch
Date: 2020-07-07 00:00:00
Tasks: Face Recognition, Generative Adversarial Network

The primary objective of face morphing is to combine face images of different data subjects (e.g. a malicious actor and an accomplice) to generate a face image that can be equally verified for both contributing data subjects. In this paper, we propose a new framework for generating face morphs using a newer Generative Adversarial Network (GAN) - StyleGAN. In contrast to earlier works, we generate realistic morphs of both high-quality and high resolution of 1024$\times$1024 pixels. With the newly created morphing dataset of 2500 morphed face images, we pose a critical question in this work. \textit{(i) Can GAN generated morphs threaten Face Recognition Systems (FRS) equally as Landmark based morphs?} Seeking an answer, we benchmark the vulnerability of a Commercial-Off-The-Shelf FRS (COTS) and a deep learning-based FRS (ArcFace). This work also benchmarks the detection approaches for both GAN generated morphs against the landmark based morphs using established Morphing Attack Detection (MAD) schemes.
GraphOpt: Learning Optimization Models of Graph Formation
Authors: Rakshit Trivedi, Jiachen Yang, Hongyuan Zha
Date: 2020-07-07 00:00:00
Proceeding: ICML 2020 1
Tasks: Decision Making, Link Prediction, Sequential Decision Making

Formation mechanisms are fundamental to the study of complex networks, but learning them from observations is challenging. In real-world domains, one often has access only to the final constructed graph, instead of the full construction process, and observed graphs exhibit complex structural properties. In this work, we propose GraphOpt, an end-to-end framework that jointly learns an implicit model of graph structure formation and discovers an underlying optimization mechanism in the form of a latent objective function. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm. Further, it employs a novel continuous latent action space that aids scalability. Empirically, we demonstrate that GraphOpt discovers a latent objective transferable across graphs with different characteristics. GraphOpt also learns a robust stochastic policy that achieves competitive link prediction performance without being explicitly trained on this task and further enables construction of graphs with properties similar to those of the observed graph.
Asymptotic behaviour of learning rates in Armijo's condition
Authors: Tuyen Trung Truong, Tuan Hang Nguyen
Date: 2020-07-07 00:00:00

Fix a constant $0<\alpha <1$. For a $C^1$ function $f:\mathbb{R}^k\rightarrow \mathbb{R}$, a point $x$ and a positive number $\delta >0$, we say that Armijo's condition is satisfied if $f(x-\delta \nabla f(x))-f(x)\leq -\alpha \delta ||\nabla f(x)||^2$. It is a basis for the well known Backtracking Gradient Descent (Backtracking GD) algorithm. Consider a sequence $\{x_n\}$ defined by $x_{n+1}=x_n-\delta _n\nabla f(x_n)$, for positive numbers $\delta _n$ for which Armijo's condition is satisfied. We show that if $\{x_n\}$ converges to a non-degenerate critical point, then $\{\delta _n\}$ must be bounded. Moreover this boundedness can be quantified in terms of the norms of the Hessian $\nabla ^2f$ and its inverse at the limit point. This complements the first author's results on Unbounded Backtracking GD, and shows that in case of convergence to a non-degenerate critical point the behaviour of Unbounded Backtracking GD is not too different from that of usual Backtracking GD. On the other hand, in case of convergence to a degenerate critical point the behaviours can be very much different. We run some experiments to illustrate that both scenrios can really happen. In another part of the paper, we argue that Backtracking GD has the correct unit (according to a definition by Zeiler in his Adadelta's paper). The main point is that since learning rate in Backtracking GD is bound by Armijo's condition, it is not unitless.
Backdoor attacks and defenses in feature-partitioned collaborative learning
Authors: Yang Liu, Zhihao Yi, Tianjian Chen
Date: 2020-07-07 00:00:00
Tasks: Federated Learning

Since there are multiple parties in collaborative learning, malicious parties might manipulate the learning process for their own purposes through backdoor attacks. However, most of existing works only consider the federated learning scenario where data are partitioned by samples. The feature-partitioned learning can be another important scenario since in many real world applications, features are often distributed across different parties. Attacks and defenses in such scenario are especially challenging when the attackers have no labels and the defenders are not able to access the data and model parameters of other participants. In this paper, we show that even parties with no access to labels can successfully inject backdoor attacks, achieving high accuracy on both main and backdoor tasks. Next, we introduce several defense techniques, demonstrating that the backdoor can be successfully blocked by a combination of these techniques without hurting main task accuracy. To the best of our knowledge, this is the first systematical study to deal with backdoor attacks in the feature-partitioned collaborative learning framework.
Monitoring Browsing Behavior of Customers in Retail Stores via RFID Imaging
Authors: Kamran Ali, Alex X. Liu, Eugene Chai, Karthik Sundaresan
Date: 2020-07-07 00:00:00

In this paper, we propose to use commercial off-the-shelf (COTS) monostatic RFID devices (i.e. which use a single antenna at a time for both transmitting and receiving RFID signals to and from the tags) to monitor browsing activity of customers in front of display items in places such as retail stores. To this end, we propose TagSee, a multi-person imaging system based on monostatic RFID imaging. TagSee is based on the insight that when customers are browsing the items on a shelf, they stand between the tags deployed along the boundaries of the shelf and the reader, which changes the multi-paths that the RFID signals travel along, and both the RSS and phase values of the RFID signals that the reader receives change. Based on these variations observed by the reader, TagSee constructs a coarse grained image of the customers. Afterwards, TagSee identifies the items that are being browsed by the customers by analyzing the constructed images. The key novelty of this paper is on achieving browsing behavior monitoring of multiple customers in front of display items by constructing coarse grained images via robust, analytical model-driven deep learning based, RFID imaging. To achieve this, we first mathematically formulate the problem of imaging humans using monostatic RFID devices and derive an approximate analytical imaging model that correlates the variations caused by human obstructions in the RFID signals. Based on this model, we then develop a deep learning framework to robustly image customers with high accuracy. We implement TagSee scheme using a Impinj Speedway R420 reader and SMARTRAC DogBone RFID tags. TagSee can achieve a TPR of more than ~90% and a FPR of less than ~10% in multi-person scenarios using training data from just 3-4 users.
An Emergency Medical Services Clinical Audit System driven by Named Entity Recognition from Deep Learning
Authors: Wang Han, Wesley Yeung, Angeline Tung, Joey Tay Ai Meng, Davin Ryanputera, Feng Mengling, Shalini Arulanadam
Date: 2020-07-07 00:00:00
Tasks: named-entity-recognition, Named Entity Recognition, Named Entity Recognition (NER), NER

Clinical performance audits are routinely performed in Emergency Medical Services (EMS) to ensure adherence to treatment protocols, to identify individual areas of weakness for remediation, and to discover systemic deficiencies to guide the development of the training syllabus. At present, these audits are performed by manual chart review which is time-consuming and laborious. In this paper, we present an automatic audit system based on both the structured and unstructured ambulance case records and clinical notes with a deep neural network-based named entities recognition model. The dataset used in this study contained 58,898 unlabelled ambulance incidents encountered by the Singapore Civil Defence Force from 1st April 2019 to 30th June 2019. A weakly-supervised training approach was adopted to label the sentences. Later on, we trained three different models to perform the NER task. All three models achieve F1 scores of around 0.981 under entity type matching evaluation and around 0.976 under strict evaluation, while the BiLSTM-CRF model is 1~2 orders of magnitude lighter and faster than our BERT-based models. Overall, our approach yielded a named entity recognition model that could reliably identify clinical entities from unstructured paramedic free-text reports. Our proposed system may improve the efficiency of clinical performance audits and can also help with EMS database research.
Instance Segmentation for Whole Slide Imaging: End-to-End or Detect-Then-Segment
Authors: Aadarsh Jha, Haichun Yang, Ruining Deng, Meghan E. Kapp, Agnes B. Fogo, Yuankai Huo
Date: 2020-07-07 00:00:00
Tasks: Instance Segmentation, Segmentation, Semantic Segmentation

Automatic instance segmentation of glomeruli within kidney Whole Slide Imaging (WSI) is essential for clinical research in renal pathology. In computer vision, the end-to-end instance segmentation methods (e.g., Mask-RCNN) have shown their advantages relative to detect-then-segment approaches by performing complementary detection and segmentation tasks simultaneously. As a result, the end-to-end Mask-RCNN approach has been the de facto standard method in recent glomerular segmentation studies, where downsampling and patch-based techniques are used to properly evaluate the high resolution images from WSI (e.g., >10,000x10,000 pixels on 40x). However, in high resolution WSI, a single glomerulus itself can be more than 1,000x1,000 pixels in original resolution which yields significant information loss when the corresponding features maps are downsampled via the Mask-RCNN pipeline. In this paper, we assess if the end-to-end instance segmentation framework is optimal for high-resolution WSI objects by comparing Mask-RCNN with our proposed detect-then-segment framework. Beyond such a comparison, we also comprehensively evaluate the performance of our detect-then-segment pipeline through: 1) two of the most prevalent segmentation backbones (U-Net and DeepLab_v3); 2) six different image resolutions (from 512x512 to 28x28); and 3) two different color spaces (RGB and LAB). Our detect-then-segment pipeline, with the DeepLab_v3 segmentation framework operating on previously detected glomeruli of 512x512 resolution, achieved a 0.953 dice similarity coefficient (DSC), compared with a 0.902 DSC from the end-to-end Mask-RCNN pipeline. Further, we found that neither RGB nor LAB color spaces yield better performance when compared against each other in the context of a detect-then-segment framework. Detect-then-segment pipeline achieved better segmentation performance compared with End-to-end method.
Adaptive Cascade Submodular Maximization
Authors: Shaojie Tang, Jing Yuan
Date: 2020-07-07 00:00:00

In this paper, we propose and study the cascade submodular maximization problem under the adaptive setting. The input of our problem is a set of items, each item is in a particular state (i.e., the marginal contribution of an item) which is drawn from a known probability distribution. However, we can not know its actual state before selecting it. As compared with existing studies on stochastic submodular maximization, one unique setting of our problem is that each item is associated with a continuation probability which represents the probability that one is allowed to continue to select the next item after selecting the current one. Intuitively, this term captures the externality of selecting one item to all its subsequent items in terms of the opportunity of being selected. Therefore, the actual set of items that can be selected by a policy depends on the specific ordering it adopts to select items, this makes our problem fundamentally different from classical submodular set optimization problems. Our objective is to identify the best sequence of selecting items so as to maximize the expected utility of the selected items. We propose a class of stochastic utility functions, \emph{adaptive cascade submodular functions}, and show that the objective functions in many practical application domains satisfy adaptive cascade submodularity. Then we develop a $0.12$ approximation algorithm to the adaptive cascade submodular maximization problem.
STADB: A Self-Thresholding Attention Guided ADB Network for Person Re-identification
Authors: Bo Jiang, Sheng Wang, Xiao Wang, Aihua Zheng
Date: 2020-07-07 00:00:00
Tasks: Person Re-Identification

Recently, Batch DropBlock network (BDB) has demonstrated its effectiveness on person image representation and re-identification task via feature erasing. However, BDB drops the features \textbf{randomly} which may lead to sub-optimal results. In this paper, we propose a novel Self-Thresholding attention guided Adaptive DropBlock network (STADB) for person re-ID which can \textbf{adaptively} erase the most discriminative regions. Specifically, STADB first obtains an attention map by channel-wise pooling and returns a drop mask by thresholding the attention map. Then, the input features and self-thresholding attention guided drop mask are multiplied to generate the dropped feature maps. In addition, STADB utilizes the spatial and channel attention to learn a better feature map and iteratively trains the feature dropping module for person re-ID. Experiments on several benchmark datasets demonstrate that the proposed STADB outperforms many other related methods for person re-ID. The source code of this paper is released at: \textcolor{red}{\url{https://github.com/wangxiao5791509/STADB_ReID}}.
Expressiveness of SETAFs and Support-Free ADFs under 3-valued Semantics
Authors: Wolfgang Dvořák, Atefeh Keshavarzi Zafarghandi, Stefan Woltran
Date: 2020-07-07 00:00:00
Tasks: Relation

Generalizing the attack structure in argumentation frameworks (AFs) has been studied in different ways. Most prominently, the binary attack relation of Dung frameworks has been extended to the notion of collective attacks. The resulting formalism is often termed SETAFs. Another approach is provided via abstract dialectical frameworks (ADFs), where acceptance conditions specify the relation between arguments; restricting these conditions naturally allows for so-called support-free ADFs. The aim of the paper is to shed light on the relation between these two different approaches. To this end, we investigate and compare the expressiveness of SETAFs and support-free ADFs under the lens of 3-valued semantics. Our results show that it is only the presence of unsatisfiable acceptance conditions in support-free ADFs that discriminate the two approaches.
Using Semantic Web Services for AI-Based Research in Industry 4.0
Authors: Lukas Malburg, Patrick Klein, Ralph Bergmann
Date: 2020-07-07 00:00:00
Tasks: Management

The transition to Industry 4.0 requires smart manufacturing systems that are easily configurable and provide a high level of flexibility during manufacturing in order to achieve mass customization or to support cloud manufacturing. To realize this, Cyber-Physical Systems (CPSs) combined with Artificial Intelligence (AI) methods find their way into manufacturing shop floors. For using AI methods in the context of Industry 4.0, semantic web services are indispensable to provide a reasonable abstraction of the underlying manufacturing capabilities. In this paper, we present semantic web services for AI-based research in Industry 4.0. Therefore, we developed more than 300 semantic web services for a physical simulation factory based on Web Ontology Language for Web Services (OWL-S) and Web Service Modeling Ontology (WSMO) and linked them to an already existing domain ontology for intelligent manufacturing control. Suitable for the requirements of CPS environments, our pre- and postconditions are verified in near real-time by invoking other semantic web services in contrast to complex reasoning within the knowledge base. Finally, we evaluate our implementation by executing a cyber-physical workflow composed of semantic web services using a workflow management system.
HKR For Handwritten Kazakh & Russian Database
Authors: Daniyar Nurseitov, Kairat Bostanbekov, Daniyar Kurmankhojayev, Anel Alimova, Abdelrahman Abdallah
Date: 2020-07-07 00:00:00
Tasks: Handwriting Recognition

In this paper, we present a new Russian and Kazakh database (with about 95% of Russian and 5% of Kazakh words/sentences respectively) for offline handwriting recognition. A few pre-processing and segmentation procedures have been developed together with the database. The database is written in Cyrillic and shares the same 33 characters. Besides these characters, the Kazakh alphabet also contains 9 additional specific characters. This dataset is a collection of forms. The sources of all the forms in the datasets were generated by \LaTeX which subsequently was filled out by persons with their handwriting. The database consists of more than 1400 filled forms. There are approximately 63000 sentences, more than 715699 symbols produced by approximately 200 different writers. It can serve researchers in the field of handwriting recognition tasks by using deep and machine learning.