OpenRaiser/Intern-Atlas huggingface dataset:
Dependent Pearl: Normalization by realizability
Venue: arXiv cs.PL 2020
Year: 2020

For those of us who generally live in the world of syntax, semantic proof techniques such as reducibility, realizability or logical relations seem somewhat magical despite -- or perhaps due to -- their seemingly unreasonable effectiveness. Why do they work? At which point in the proof is "the real work" done? Hoping to build a programming intuition of these proofs, we implement a normalization argument for the simply-typed lambda-calculus with sums: instead of a proof, it is described as a program in a dependently-typed meta-language. The semantic technique we set out to study is Krivine's classical realizability, which amounts to a proof-relevant presentation of reducibility arguments -- unary logical relations. Reducibility assigns a predicate to each type, realizability assigns a set of realizers, which are abstract machines that extend lambda-terms with a first-class notion of contexts. Normalization is a direct consequence of an adequacy theorem or "fundamental lemma", which states that any well-typed term translates to a realizer of its type. We show that the adequacy theorem, when written as a dependent program, corresponds to an evaluation procedure. In particular, a weak normalization proof precisely computes a series of reduction from the input term to a normal form. Interestingly, the choices that we make when we define the reducibility predicates -- truth and falsity witnesses for each connective -- determine the evaluation order of the proof, with each datatype constructor behaving in a lazy or strict fashion. While most of the ideas in this presentation are folklore among specialists, our dependently-typed functional program provides an accessible presentation to a wider audience. In particular, our work provides a gentle introduction to abstract machine calculi which have recently been used as an effective research vehicle.
DGSAN: Discrete Generative Self-Adversarial Network
Venue: arXiv cs.LG 2020
Year: 2020

Although GAN-based methods have received many achievements in the last few years, they have not been entirelysuccessful in generating discrete data. The most crucial challenge of these methods is the difficulty of passing the gradientfrom the discriminator to the generator when the generator outputs are discrete. Despite the fact that several attemptshave been made to alleviate this problem, none of the existing GAN-based methods have improved the performance oftext generation compared with the maximum likelihood approach in terms of both the quality and the diversity. In thispaper, we proposed a new framework for generating discrete data by an adversarial approach in which there is no need topass the gradient to the generator. The proposed method has an iterative manner in which each new generator is definedbased on the last discriminator. It leverages the discreteness of data and the last discriminator to model the real datadistribution implicitly. Moreover, the method is supported with theoretical guarantees, and experimental results generallyshow the superiority of the proposed DGSAN method compared to the other popular or recent methods in generatingdiscrete sequential data.
Propagate-Selector: Detecting Supporting Sentences for Question Answering via Graph Neural Networks
Venue: arXiv cs.CL 2020
Year: 2020

In this study, we propose a novel graph neural network called propagate-selector (PS), which propagates information over sentences to understand information that cannot be inferred when considering sentences in isolation. First, we design a graph structure in which each node represents an individual sentence, and some pairs of nodes are selectively connected based on the text structure. Then, we develop an iterative attentive aggregation and a skip-combine method in which a node interacts with its neighborhood nodes to accumulate the necessary information. To evaluate the performance of the proposed approaches, we conduct experiments with the standard HotpotQA dataset. The empirical results demonstrate the superiority of our proposed approach, which obtains the best performances, compared to the widely used answer-selection models that do not consider the intersentential relationship.
Planning Beyond the Sensing Horizon Using a Learned Context
Venue: arXiv cs.RO 2020
Year: 2020

Last-mile delivery systems commonly propose the use of autonomous robotic vehicles to increase scalability and efficiency. The economic inefficiency of collecting accurate prior maps for navigation motivates the use of planning algorithms that operate in unmapped environments. However, these algorithms typically waste time exploring regions that are unlikely to contain the delivery destination. Context is key information about structured environments that could guide exploration toward the unknown goal location, but the abstract idea is difficult to quantify for use in a planning algorithm. Some approaches specifically consider contextual relationships between objects, but would perform poorly in object-sparse environments like outdoors. Recent deep learning-based approaches consider context too generally, making training/transferability difficult. Therefore, this work proposes a novel formulation of utilizing context for planning as an image-to-image translation problem, which is shown to extract terrain context from semantic gridmaps, into a metric that an exploration-based planner can use. The proposed framework has the benefit of training on a static dataset instead of requiring a time-consuming simulator. Across 42 test houses with layouts from satellite images, the trained algorithm enables a robot to reach its goal 189\% faster than with a context-unaware planner, and within 63\% of the optimal path computed with a prior map. The proposed algorithm is also implemented on a vehicle with a forward-facing camera in a high-fidelity, Unreal simulation of neighborhood houses.
Improvability Through Semi-Supervised Learning: A Survey of Theoretical Results
Venue: arXiv cs.LG 2020
Year: 2020

Semi-supervised learning is a setting in which one has labeled and unlabeled data available. In this survey we explore different types of theoretical results when one uses unlabeled data in classification and regression tasks. Most methods that use unlabeled data rely on certain assumptions about the data distribution. When those assumptions are not met in reality, including unlabeled data may actually decrease performance. Studying such methods, it therefore is particularly important to have an understanding of the underlying theory. In this review we gather results about the possible gains one can achieve when using semi-supervised learning as well as results about the limits of such methods. More precisely, this review collects the answers to the following questions: What are, in terms of improving supervised methods, the limits of semi-supervised learning? What are the assumptions of different methods? What can we achieve if the assumptions are true? Finally, we also discuss the biggest bottleneck of semi-supervised learning, namely the assumptions they make.
Kindly Bent to Free Us
Venue: arXiv cs.PL 2020
Year: 2020

Systems programming often requires the manipulation of resources like file handles, network connections, or dynamically allocated memory. Programmers need to follow certain protocols to handle these resources correctly. Violating these protocols causes bugs ranging from type mismatches over data races to use-after-free errors and memory leaks. These bugs often lead to security vulnerabilities. While statically typed programming languages guarantee type soundness and memory safety by design, most of them do not address issues arising from improper handling of resources. An important step towards handling resources is the adoption of linear and affine types that enforce single-threaded resource usage. However, the few languages supporting such types require heavy type annotations. We present Affe, an extension of ML that manages linearity and affinity properties using kinds and constrained types. In addition Affe supports the exclusive and shared borrowing of affine resources, inspired by features of Rust. Moreover, Affe retains the defining features of the ML family: it is an impure, strict, functional expression language with complete principal type inference and type abstraction. Affe does not require any linearity annotations in expressions and supports common functional programming idioms.
Variationally Inferred Sampling Through a Refined Bound for Probabilistic Programs
Venue: arXiv cs.LG 2020
Year: 2020

A framework to boost the efficiency of Bayesian inference in probabilistic programs is introduced by embedding a sampler inside a variational posterior approximation. We call it the refined variational approximation. Its strength lies both in ease of implementation and automatically tuning of the sampler parameters to speed up mixing time using automatic differentiation. Several strategies to approximate \emph{evidence lower bound} (ELBO) computation are introduced. Experimental evidence of its efficient performance is shown solving an influence diagram in a high-dimensional space using a conditional variational autoencoder (cVAE) as a deep Bayes classifier; an unconditional VAE on density estimation tasks; and state-space models for time-series data.
Partial Sums on the Ultra-Wide Word RAM
Venue: arXiv cs.DS 2020
Year: 2020

We consider the classic partial sums problem on the ultra-wide word RAM model of computation. This model extends the classic $w$-bit word RAM model with special ultrawords of length $w^2$ bits that support standard arithmetic and boolean operation and scattered memory access operations that can access $w$ (non-contiguous) locations in memory. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a new in-place data structure for the partial sum problem that only stores a constant number of ultraword in addition to the input and supports operations in doubly logarithmic time. This matches the best known time bounds for the problem (among polynomial space data structures) while improving the space from superlinear to a constant number of ultrawords. Our results are based on a simple and elegant in-place word RAM data structure, known as the Fenwick tree. Our main technical contribution is a new efficient parallel ultra-wide word RAM implementation of the Fenwick tree, which is likely of independent interest.
CASIA-SURF: A Large-scale Multi-modal Benchmark for Face Anti-spoofing
Venue: arXiv cs.CV 2020
Year: 2020

Face anti-spoofing is essential to prevent face recognition systems from a security breach. Much of the progresses have been made by the availability of face anti-spoofing benchmark datasets in recent years. However, existing face anti-spoofing benchmarks have limited number of subjects ($\le\negmedspace170$) and modalities ($\leq\negmedspace2$), which hinder the further development of the academic community. To facilitate face anti-spoofing research, we introduce a large-scale multi-modal dataset, namely CASIA-SURF, which is the largest publicly available dataset for face anti-spoofing in terms of both subjects and modalities. Specifically, it consists of $1,000$ subjects with $21,000$ videos and each sample has $3$ modalities (i.e., RGB, Depth and IR). We also provide comprehensive evaluation metrics, diverse evaluation protocols, training/validation/testing subsets and a measurement tool, developing a new benchmark for face anti-spoofing. Moreover, we present a novel multi-modal multi-scale fusion method as a strong baseline, which performs feature re-weighting to select the more informative channel features while suppressing the less useful ones for each modality across different scales. Extensive experiments have been conducted on the proposed dataset to verify its significance and generalization capability. The dataset is available at https://sites.google.com/qq.com/face-anti-spoofing/welcome/challengecvpr2019?authuser=0
How Good is Artificial Intelligence at Automatically Answering Consumer Questions Related to Alzheimer's Disease?
Venue: arXiv cs.IR 2020
Year: 2020

Alzheimer's Disease (AD) is the most common type of dementia, comprising 60-80% of cases. There were an estimated 5.8 million Americans living with Alzheimer's dementia in 2019, and this number will almost double every 20 years. The total lifetime cost of care for someone with dementia is estimated to be $350,174 in 2018, 70% of which is associated with family-provided care. Most family caregivers face emotional, financial and physical difficulties. As a medium to relieve this burden, online communities in social media websites such as Twitter, Reddit, and Yahoo! Answers provide potential venues for caregivers to search relevant questions and answers, or post questions and seek answers from other members. However, there are often a limited number of relevant questions and responses to search from, and posted questions are rarely answered immediately. Due to recent advancement in Artificial Intelligence (AI), particularly Natural Language Processing (NLP), we propose to utilize AI to automatically generate answers to AD-related consumer questions posted by caregivers and evaluate how good AI is at answering those questions. To the best of our knowledge, this is the first study in the literature applying and evaluating AI models designed to automatically answer consumer questions related to AD.
SGX-LKL: Securing the Host OS Interface for Trusted Execution
Venue: arXiv cs.OS 2020
Year: 2020

Hardware support for trusted execution in modern CPUs enables tenants to shield their data processing workloads in otherwise untrusted cloud environments. Runtime systems for the trusted execution must rely on an interface to the untrusted host OS to use external resources such as storage, network, and other functions. Attackers may exploit this interface to leak data or corrupt the computation. We describe SGX-LKL, a system for running Linux binaries inside of Intel SGX enclaves that only exposes a minimal, protected and oblivious host interface: the interface is (i) minimal because SGX-LKL uses a complete library OS inside the enclave, including file system and network stacks, which requires a host interface with only 7 calls; (ii) protected because SGX-LKL transparently encrypts and integrity-protects all data passed via low-level I/O operations; and (iii) oblivious because SGX-LKL performs host operations independently of the application workload. For oblivious disk I/O, SGX-LKL uses an encrypted ext4 file system with shuffled disk blocks. We show that SGX-LKL protects TensorFlow training with a 21% overhead.
InferPy: Probabilistic Modeling with Deep Neural Networks Made Easy
Venue: arXiv cs.LG 2020
Year: 2020

InferPy is a Python package for probabilistic modeling with deep neural networks. It defines a user-friendly API that trades-off model complexity with ease of use, unlike other libraries whose focus is on dealing with very general probabilistic models at the cost of having a more complex API. In particular, this package allows to define, learn and evaluate general hierarchical probabilistic models containing deep neural networks in a compact and simple way. InferPy is built on top of Tensorflow Probability and Keras.
Kinematic Single Vehicle Trajectory Prediction Baselines and Applications with the NGSIM Dataset
Venue: arXiv cs.RO 2020
Year: 2020

In the recent vehicle trajectory prediction literature, the most common baselines are briefly introduced without the necessary information to reproduce it. In this article we produce reproducible vehicle prediction results from simple models. For that purpose, the process is explicit, and the code is available. Those baseline models are a constant velocity model and a single-vehicle prediction model. They are applied on the NGSIM US-101 and I-80 datasets using only relative positions. Thus, the process can be reproduced with any database containing tracking of vehicle positions. The evaluation reports Root Mean Squared Error (RMSE), Final Displacement Error (FDE), Negative Log-Likelihood (NLL), and Miss Rate (MR). The NLL estimation needs a careful definition because several formulations that differ from the mathematical definition are used in other works. This article is meant to be used along with the published code to establish baselines for further work. An extension is proposed to replace the constant velocity assumption with a learned model using a recurrent neural network. This brings good improvements in accuracy and uncertainty estimation and opens possibilities for both complex and interpretable models.
Graph Convolutional Networks for Road Networks
Venue: arXiv cs.LG 2020
Year: 2020

Machine learning techniques for road networks hold the potential to facilitate many important transportation applications. Graph Convolutional Networks (GCNs) are neural networks that are capable of leveraging the structure of a road network by utilizing information of, e.g., adjacent road segments. While state-of-the-art GCNs target node classification tasks in social, citation, and biological networks, machine learning tasks in road networks differ substantially from such tasks. In road networks, prediction tasks concern edges representing road segments, and many tasks involve regression. In addition, road networks differ substantially from the networks assumed in the GCN literature in terms of the attribute information available and the network characteristics. Many implicit assumptions of GCNs do therefore not apply. We introduce the notion of Relational Fusion Network (RFN), a novel type of GCN designed specifically for machine learning on road networks. In particular, we propose methods that outperform state-of-the-art GCNs on both a road segment regression task and a road segment classification task by 32-40% and 21-24%, respectively. In addition, we provide experimental evidence of the short-comings of state-of-the-art GCNs in the context of road networks: unlike our method, they cannot effectively leverage the road network structure for road segment classification and fail to outperform a regular multi-layer perceptron.
Equivalences between triangle and range query problems
Venue: arXiv cs.CC 2020
Year: 2020

We define a natural class of range query problems, and prove that all problems within this class have the same time complexity (up to polylogarithmic factors). The equivalence is very general, and even applies to online algorithms. This allows us to obtain new improved algorithms for all of the problems in the class. We then focus on the special case of the problems when the queries are offline and the number of queries is linear. We show that our range query problems are runtime-equivalent (up to polylogarithmic factors) to counting for each edge $e$ in an $m$-edge graph the number of triangles through $e$. This natural triangle problem can be solved using the best known triangle counting algorithm, running in $O(m^{2ω/(ω+1)}) \leq O(m^{1.41})$ time. Moreover, if $ω=2$, the $O(m^{2ω/(ω+1)})$ running time is known to be tight (within $m^{o(1)}$ factors) under the 3SUM Hypothesis. In this case, our equivalence settles the complexity of the range query problems. Our problems constitute the first equivalence class with this peculiar running time bound. To better understand the complexity of these problems, we also provide a deeper insight into the family of triangle problems, in particular showing black-box reductions between triangle listing and per-edge triangle detection and counting. As a byproduct of our reductions, we obtain a simple triangle listing algorithm matching the state-of-the-art for all regimes of the number of triangles. We also give some not necessarily tight, but still surprising reductions from variants of matrix products, such as the $(\min,\max)$-product.
Two-layer Coded Channel Access with Collision Resolution: Design and Analysis
Venue: arXiv cs.IT 2020
Year: 2020

We propose a two-layer coding architecture for communication of multiple users over a shared slotted medium enabling joint collision resolution and decoding. Each user first encodes its information bits with an outer code for reliability, and then transmits these coded bits with possible repetitions over transmission time slots of the access channel. The transmission patterns are dictated by the inner collision-resolution code and collisions with other users' transmissions may occur. We analyze two types of codes for the outer layer: long-blocklength LDPC codes, and short-blocklength algebraic codes. With LDPC codes, a density evolution analysis enables joint optimization of both outer and inner code parameters for maximum throughput. With algebraic codes, we invoke a similar analysis by approximating their average erasure correcting capability while assuming a large number of active transmitters. The proposed low-complexity schemes operate at a significantly smaller gap to capacity than the state of the art. Our schemes apply both to a multiple access scenario where number of users within a frame is known a priori, and to a random access scenario where that number is known only to the decoder. In the latter case, we optimize an outage probability due to the variability in user activity.
EnGN: A High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks
Venue: arXiv cs.DC 2020
Year: 2020

Graph neural networks (GNNs) emerge as a powerful approach to process non-euclidean data structures and have been proved powerful in various application domains such as social networks and e-commerce. While such graph data maintained in real-world systems can be extremely large and sparse, thus employing GNNs to deal with them requires substantial computational and memory overhead, which induces considerable energy and resource cost on CPUs and GPUs. In this work, we present a specialized accelerator architecture, EnGN, to enable high-throughput and energy-efficient processing of large-scale GNNs. The proposed EnGN is designed to accelerate the three key stages of GNN propagation, which is abstracted as common computing patterns shared by typical GNNs. To support the key stages simultaneously, we propose the ring-edge-reduce(RER) dataflow that tames the poor locality of sparsely-and-randomly connected vertices, and the RER PE-array to practice RER dataflow. In addition, we utilize a graph tiling strategy to fit large graphs into EnGN and make good use of the hierarchical on-chip buffers through adaptive computation reordering and tile scheduling. Overall, EnGN achieves performance speedup by 1802.9X, 19.75X, and 2.97X and energy efficiency by 1326.35X, 304.43X, and 6.2X on average compared to CPU, GPU, and a state-of-the-art GCN accelerator HyGCN, respectively.
Imbalance Problems in Object Detection: A Review
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we present a comprehensive review of the imbalance problems in object detection. To analyze the problems in a systematic manner, we introduce a problem-based taxonomy. Following this taxonomy, we discuss each problem in depth and present a unifying yet critical perspective on the solutions in the literature. In addition, we identify major open issues regarding the existing imbalance problems as well as imbalance problems that have not been discussed before. Moreover, in order to keep our review up to date, we provide an accompanying webpage which catalogs papers addressing imbalance problems, according to our problem-based taxonomy. Researchers can track newer studies on this webpage available at: https://github.com/kemaloksuz/ObjectDetectionImbalance .