OpenRaiser/Intern-Atlas huggingface dataset:
Transitivity of Subtyping for Intersection Types
Venue: arXiv cs.PL 2020
Year: 2020

The subtyping rules for intersection types traditionally employ a transitivity rule (Barendregt et al. 1983), which means that subtyping does not satisfy the subformula property, making it more difficult to use in filter models for compiler verification. Laurent develops a sequent-style subtyping system, without transitivity, and proves transitivity via a sequence of six lemmas that culminate in cut-elimination (2018). This article develops a subtyping system in regular style that omits transitivity and provides a direct proof of transitivity, significantly reducing the length of the proof, exchanging the six lemmas for just one. Inspired by Laurent's system, the rule for function types is essentially the $β$-soundness property. The new system satisfies the "subformula conjunction property": every type occurring in the derivation of $A <: B$ is a subformula of $A$ or $B$, or an intersection of such subformulas. The article proves that the new subtyping system is equivalent to that of Barendregt, Coppo, and Dezani-Ciancaglini.
Penalty Bidding Mechanisms for Allocating Resources and Overcoming Present Bias
Venue: arXiv cs.GT 2020
Year: 2020

From skipped exercise classes to last-minute cancellation of dentist appointments, underutilization of reserved resources abounds. Likely reasons include uncertainty about the future, further exacerbated by present bias. In this paper, we unite resource allocation and commitment devices through the design of contingent payment mechanisms, and propose the two-bid penalty-bidding mechanism. This extends an earlier mechanism proposed by Ma et al. (2019), assigning the resources based on willingness to accept a no-show penalty, while also allowing each participant to increase her own penalty in order to counter present bias. We establish a simple dominant strategy equilibrium, regardless of an agent's level of present bias or degree of "sophistication". Via simulations, we show that the proposed mechanism substantially improves utilization and achieves higher welfare and better equity in comparison with mechanisms used in practice and mechanisms that optimize welfare in the absence of present bias.
Task-based Solutions to Embedded Index Coding
Venue: arXiv cs.IT 2020
Year: 2020

In the index coding problem a sender holds a message $x \in \{0,1\}^n$ and wishes to broadcast information to $n$ receivers in a way that enables the $i$th receiver to retrieve the $i$th bit $x_i$. Every receiver has prior side information comprising a subset of the bits of $x$, and the goal is to minimize the length of the information sent via the broadcast channel. Porter and Wootters have recently introduced the model of embedded index coding, where the receivers also play the role of the sender and the goal is to minimize the total length of their broadcast information. An embedded index code is said to be task-based if every receiver retrieves its bit based only on the information provided by one of the receivers. This paper studies the effect of the task-based restriction on linear embedded index coding. It is shown that for certain side information maps there exists a linear embedded index code of length quadratically smaller than that of any task-based embedded index code. The result attains, up to a multiplicative constant, the largest possible gap between the two quantities. The proof is by an explicit construction and the analysis involves spectral techniques.
Tight Polynomial Worst-Case Bounds for Loop Programs
Venue: arXiv cs.LO 2020
Year: 2020

In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple programming language - representing non-deterministic imperative programs with bounded loops, and arithmetics limited to addition and multiplication - it is possible to decide precisely whether a program has certain growth-rate properties, in particular whether a computed value, or the program's running time, has a polynomial growth rate. A natural and intriguing problem was to move from answering the decision problem to giving a quantitative result, namely, a tight polynomial upper bound. This paper shows how to obtain asymptotically-tight, multivariate, disjunctive polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found. A pleasant surprise is that the algorithm is quite simple; but it relies on some subtle reasoning. An important ingredient in the proof is the forest factorization theorem, a strong structural result on homomorphisms into a finite monoid.
RUBi: Reducing Unimodal Biases in Visual Question Answering
Venue: arXiv cs.CV 2020
Year: 2020

Visual Question Answering (VQA) is the task of answering questions about an image. Some VQA models often exploit unimodal biases to provide the correct answer without using the image information. As a result, they suffer from a huge drop in performance when evaluated on data outside their training set distribution. This critical issue makes them unsuitable for real-world settings. We propose RUBi, a new learning strategy to reduce biases in any VQA model. It reduces the importance of the most biased examples, i.e. examples that can be correctly classified without looking at the image. It implicitly forces the VQA model to use the two input modalities instead of relying on statistical regularities between the question and the answer. We leverage a question-only model that captures the language biases by identifying when these unwanted regularities are used. It prevents the base VQA model from learning them by influencing its predictions. This leads to dynamically adjusting the loss in order to compensate for biases. We validate our contributions by surpassing the current state-of-the-art results on VQA-CP v2. This dataset is specifically designed to assess the robustness of VQA models when exposed to different question biases at test time than what was seen during training. Our code is available: github.com/cdancette/rubi.bootstrap.pytorch
Neural Transfer Learning for Cry-based Diagnosis of Perinatal Asphyxia
Venue: arXiv cs.LG 2020
Year: 2020

Despite continuing medical advances, the rate of newborn morbidity and mortality globally remains high, with over 6 million casualties every year. The prediction of pathologies affecting newborns based on their cry is thus of significant clinical interest, as it would facilitate the development of accessible, low-cost diagnostic tools\cut{ based on wearables and smartphones}. However, the inadequacy of clinically annotated datasets of infant cries limits progress on this task. This study explores a neural transfer learning approach to developing accurate and robust models for identifying infants that have suffered from perinatal asphyxia. In particular, we explore the hypothesis that representations learned from adult speech could inform and improve performance of models developed on infant speech. Our experiments show that models based on such representation transfer are resilient to different types and degrees of noise, as well as to signal loss in time and frequency domains.
Perceptual Generative Autoencoders
Venue: arXiv cs.LG 2020
Year: 2020

Modern generative models are usually designed to match target distributions directly in the data space, where the intrinsic dimension of data can be much lower than the ambient dimension. We argue that this discrepancy may contribute to the difficulties in training generative models. We therefore propose to map both the generated and target distributions to a latent space using the encoder of a standard autoencoder, and train the generator (or decoder) to match the target distribution in the latent space. Specifically, we enforce the consistency in both the data space and the latent space with theoretically justified data and latent reconstruction losses. The resulting generative model, which we call a perceptual generative autoencoder (PGA), is then trained with a maximum likelihood or variational autoencoder (VAE) objective. With maximum likelihood, PGAs generalize the idea of reversible generative models to unrestricted neural network architectures and arbitrary number of latent dimensions. When combined with VAEs, PGAs substantially improve over the baseline VAEs in terms of sample quality. Compared to other autoencoder-based generative models using simple priors, PGAs achieve state-of-the-art FID scores on CIFAR-10 and CelebA.
Improving performance of deep learning models with axiomatic attribution priors and expected gradients
Venue: arXiv cs.LG 2020
Year: 2020

Recent research has demonstrated that feature attribution methods for deep networks can themselves be incorporated into training; these attribution priors optimize for a model whose attributions have certain desirable properties -- most frequently, that particular features are important or unimportant. These attribution priors are often based on attribution methods that are not guaranteed to satisfy desirable interpretability axioms, such as completeness and implementation invariance. Here, we introduce attribution priors to optimize for higher-level properties of explanations, such as smoothness and sparsity, enabled by a fast new attribution method formulation called expected gradients that satisfies many important interpretability axioms. This improves model performance on many real-world tasks where previous attribution priors fail. Our experiments show that the gains from combining higher-level attribution priors with expected gradients attributions are consistent across image, gene expression, and health care data sets. We believe this work motivates and provides the necessary tools to support the widespread adoption of axiomatic attribution priors in many areas of applied machine learning. The implementations and our results have been made freely available to academic communities.
Model-based annotation of coreference
Venue: arXiv cs.CL 2020
Year: 2020

Humans do not make inferences over texts, but over models of what texts are about. When annotators are asked to annotate coreferent spans of text, it is therefore a somewhat unnatural task. This paper presents an alternative in which we preprocess documents, linking entities to a knowledge base, and turn the coreference annotation task -- in our case limited to pronouns -- into an annotation task where annotators are asked to assign pronouns to entities. Model-based annotation is shown to lead to faster annotation and higher inter-annotator agreement, and we argue that it also opens up for an alternative approach to coreference resolution. We present two new coreference benchmark datasets, for English Wikipedia and English teacher-student dialogues, and evaluate state-of-the-art coreference resolvers on them.
The Difficulty of Training Sparse Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

We investigate the difficulties of training sparse neural networks and make new observations about optimization dynamics and the energy landscape within the sparse regime. Recent work of \citep{Gale2019, Liu2018} has shown that sparse ResNet-50 architectures trained on ImageNet-2012 dataset converge to solutions that are significantly worse than those found by pruning. We show that, despite the failure of optimizers, there is a linear path with a monotonically decreasing objective from the initialization to the "good" solution. Additionally, our attempts to find a decreasing objective path from "bad" solutions to the "good" ones in the sparse subspace fail. However, if we allow the path to traverse the dense subspace, then we consistently find a path between two solutions. These findings suggest traversing extra dimensions may be needed to escape stationary points found in the sparse subspace.
Reconfigurable Interaction for MAS Modelling
Venue: arXiv cs.LO 2020
Year: 2020

We propose a formalism to model and reason about multi-agent systems. We allow agents to interact and communicate in different modes so that they can pursue joint tasks; agents may dynamically synchronize, exchange data, adapt their behaviour, and reconfigure their communication interfaces. The formalism defines a local behaviour based on shared variables and a global one based on message passing. We extend LTL to be able to reason explicitly about the intentions of the different agents and their interaction protocols. We also study the complexity of satisfiability and model-checking of this extension.
The induced subgraph K_2_,_3 in a non-Hamiltonian graphs
Venue: arXiv cs.DM 2020
Year: 2020

A graph $\textit{G}$ is a tuple $(\textit{V}, \textit{E})$, where $\textit{V}$ is the vertex set, $\textit{E}$ is the edge set. A reduced graph is a graph of deleting non-Hamiltonian edges and smoothing out the redundant vertices of degree 2 on an edge except for leaving only one vertex of degree 2. We denote by I a set of cycles only jointed by inside vertices. |I| is the number of sets I in a graph. We use a norm graph to denote a reduced graph of |I|=1. $\textit{g}$ is a subgraph obtained by deleting all removable cycles from a basis of a norm graph. In this paper, we show that a norm graph $\textit{G}$ is non-Hamiltonian, if and only if, $\textit{g}$ and K_2_,_3 are homeomorphic.
The Complexity of Helly-$B_{1}$ EPG Graph Recognition
Venue: arXiv cs.DM 2020
Year: 2020

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph $G$ is a graph that admits a representation where its vertices correspond to paths in a grid $Q$, such that two vertices of $G$ are adjacent if and only if their corresponding paths in $Q$ have a common edge. If the paths in the representation have at most $k$ bends, we say that it is a $B_k$-EPG representation. A collection $C$ of sets satisfies the Helly property when every sub-collection of $C$ that is pairwise intersecting has at least one common element. In this paper, we show that given a graph $G$ and an integer $k$, the problem of determining whether $G$ admits a $B_k$-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomial function of $|V(G)|$. Moreover, we show that the problem of recognizing Helly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs.
Aerial Base Stations Deployment in 6G Cellular Networks using Tethered Drones: The Mobility and Endurance Trade-off
Venue: arXiv cs.NI 2020
Year: 2020

Airborne base stations (carried by drones) have a great potential to enhance coverage and capacity of cellular networks. Multiple scenarios and use cases will highly benefit from such technology such as (i) offloading terrestrial base stations (BSs) in dense and urban areas, and (ii) providing coverage for rural areas. However, one of the main challenges facing the deployment of airborne BSs is the limited available energy at the drone, which limits the flight time. In fact, most of the currently used unmanned aerial vehicles (UAVs) can only operate for one hour maximum. This limits the performance of the UAV-enabled cellular network due to the need to frequently visit the ground station to recharge, leaving the UAV's coverage area temporarily out of service. In this article, we propose a new UAV-enabled cellular network setup based on tethered UAVs (TUAVs). In the proposed setup, the TUAV is connected to a ground station (GS) through a tether, which provides the TUAV with both energy and data. This enables a flight that can stay for days. We describe in detail the components of the proposed system. Furthermore, we enlist the main advantages of a TUAV-enabled cellular network compared to typical untethered UAVs. Next, we discuss the potential applications and use cases for TUAVs. Finally, we discuss the challenges, design considerations, and future research directions to realize the proposed setup.
InsectUp: Crowdsourcing Insect Observations to Assess Demographic Shifts and Improve Classification
Venue: arXiv cs.CV 2020
Year: 2020

Insects play such a crucial role in ecosystems that a shift in demography of just a few species can have devastating consequences at environmental, social and economic levels. Despite this, evaluation of insect demography is strongly limited by the difficulty of collecting census data at sufficient scale. We propose a method to gather and leverage observations from bystanders, hikers, and entomology enthusiasts in order to provide researchers with data that could significantly help anticipate and identify environmental threats. Finally, we show that there is indeed interest on both sides for such collaboration.
A Concise Model for Multi-Criteria Chinese Word Segmentation with Transformer Encoder
Venue: arXiv cs.CL 2020
Year: 2020

Multi-criteria Chinese word segmentation (MCCWS) aims to exploit the relations among the multiple heterogeneous segmentation criteria and further improve the performance of each single criterion. Previous work usually regards MCCWS as different tasks, which are learned together under the multi-task learning framework. In this paper, we propose a concise but effective unified model for MCCWS, which is fully-shared for all the criteria. By leveraging the powerful ability of the Transformer encoder, the proposed unified model can segment Chinese text according to a unique criterion-token indicating the output criterion. Besides, the proposed unified model can segment both simplified and traditional Chinese and has an excellent transfer capability. Experiments on eight datasets with different criteria show that our model outperforms our single-criterion baseline model and other multi-criteria models. Source codes of this paper are available on Github https://github.com/acphile/MCCWS.
Are you really looking at me? A Feature-Extraction Framework for Estimating Interpersonal Eye Gaze from Conventional Video
Venue: arXiv cs.CV 2020
Year: 2020

Despite a revolution in the pervasiveness of video cameras in our daily lives, one of the most meaningful forms of nonverbal affective communication, interpersonal eye gaze, i.e. eye gaze relative to a conversation partner, is not available from common video. We introduce the Interpersonal-Calibrating Eye-gaze Encoder (ICE), which automatically extracts interpersonal gaze from video recordings without specialized hardware and without prior knowledge of participant locations. Leveraging the intuition that individuals spend a large portion of a conversation looking at each other enables the ICE dynamic clustering algorithm to extract interpersonal gaze. We validate ICE in both video chat using an objective metric with an infrared gaze tracker (F1=0.846, N=8), as well as in face-to-face communication with expert-rated evaluations of eye contact (r= 0.37, N=170). We then use ICE to analyze behavior in two different, yet important affective communication domains: interrogation-based deception detection, and communication skill assessment in speed dating. We find that honest witnesses break interpersonal gaze contact and look down more often than deceptive witnesses when answering questions (p=0.004, d=0.79). In predicting expert communication skill ratings in speed dating videos, we demonstrate that interpersonal gaze alone has more predictive power than facial expressions.
A 1d convolutional network for leaf and time series classification
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, a 1d convolutional neural network is designed for classification tasks of plant leaves. This network based classifier is analyzed in two directions. In the forward direction, the proposed network can be used in two ways: a classifier and an automatic feature extractor. As a classifier, it takes the simple centroid contour distance curve as the single feature and achieves comparable performance with state-of-art methods that usually require multiple extracted features. As a feature extractor, it produces nearly linear separable features, hence can be used together with other classifiers such as support vector machines to provide better performance. The proposed network adopts simple 1d input and is generally applicable for other tasks such as classifying one dimensional time series in an end-to-end fashion without changes. Experiments on some benchmark datasets show this architecture can provide classification accuracies that are comparable or higher than some existing methods. In the backward direction, methods like gradient-weighted class activation mapping and maximum activation map of neurons in the classification layer with respect to inputs are performed to help investigate and further validate that hidden signatures helping trigger the trained classifier's specific decisions can be human interpretable. Code for the paper is available at https://github.com/dykuang/Leaf_Project.
Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting
Venue: arXiv cs.LG 2020
Year: 2020

Time series forecasting is an important problem across many domains, including predictions of solar plant energy output, electricity consumption, and traffic jam situation. In this paper, we propose to tackle such forecasting problem with Transformer [1]. Although impressed by its performance in our preliminary study, we found its two major weaknesses: (1) locality-agnostics: the point-wise dot-product self-attention in canonical Transformer architecture is insensitive to local context, which can make the model prone to anomalies in time series; (2) memory bottleneck: space complexity of canonical Transformer grows quadratically with sequence length $L$, making directly modeling long time series infeasible. In order to solve these two issues, we first propose convolutional self-attention by producing queries and keys with causal convolution so that local context can be better incorporated into attention mechanism. Then, we propose LogSparse Transformer with only $O(L(\log L)^{2})$ memory cost, improving forecasting accuracy for time series with fine granularity and strong long-term dependencies under constrained memory budget. Our experiments on both synthetic data and real-world datasets show that it compares favorably to the state-of-the-art.
Proof of Witness Presence: Blockchain Consensus for Augmented Democracy in Smart Cities
Venue: arXiv cs.CY 2020
Year: 2020

Smart Cities evolve into complex and pervasive urban environments with a citizens' mandate to meet sustainable development goals. Repositioning democratic values of citizens' choices in these complex ecosystems has turned out to be imperative in an era of social media filter bubbles, fake news and opportunities for manipulating electoral results with such means. This paper introduces a new paradigm of augmented democracy that promises actively engaging citizens in a more informed decision-making augmented into public urban space. The proposed concept is inspired by a digital revive of the Ancient Agora of Athens, an arena of public discourse, a Polis where citizens assemble to actively deliberate and collectively decide about public matters. The core contribution of the proposed paradigm is the concept of proving witness presence: making decision-making subject of providing secure evidence and testifying for choices made in the physical space. This paper shows how the challenge of proving witness presence can be tackled with blockchain consensus to empower citizens' trust and overcome security vulnerabilities of GPS localization. Moreover, a novel platform for collective decision-making and crowd-sensing in urban space is introduced: Smart Agora. It is shown how real-time collective measurements over citizens' choices can be made in a fully decentralized and privacy-preserving way. Witness presence is tested by deploying a decentralized system for crowd-sensing the sustainable use of transport means. Furthermore, witness presence of cycling risk is validated using official accident data from public authorities, which are compared against wisdom of the crowd. The paramount role of dynamic consensus, self-governance and ethically aligned artificial intelligence in the augmented democracy paradigm is outlined.