OpenRaiser/Intern-Atlas huggingface dataset:
Bayesian Persuasion with State-Dependent Quadratic Cost Measures
Venue: arXiv cs.GT 2020
Year: 2020

We address Bayesian persuasion between a sender and a receiver with state-dependent quadratic cost measures for general classes of distributions. The receiver seeks to make mean-square-error estimate of a state based on a signal sent by the sender while the sender signals strategically in order to control the receiver's estimate in a certain way. Such a scheme could model, e.g., deception and privacy, problems in multi-agent systems. Existing solution concepts are not viable since here the receiver has continuous action space. We show that for finite state spaces, optimal signaling strategies can be computed through an equivalent linear optimization problem over the cone of completely positive matrices. We then establish its strong duality to a copositive program. To exemplify the effectiveness of this equivalence result, we adopt sequential polyhedral approximation of completely-positive cones and analyze its performance numerically. We also quantify the approximation error for a quantized version of a continuous distribution and show that a semi-definite program relaxation of the equivalent problem could be a benchmark lower bound for the sender's cost for large state spaces.
Automatic detection of rare pathologies in fundus photographs using few-shot learning
Venue: arXiv cs.CV 2020
Year: 2020

In the last decades, large datasets of fundus photographs have been collected in diabetic retinopathy (DR) screening networks. Through deep learning, these datasets were used to train automatic detectors for DR and a few other frequent pathologies, with the goal to automate screening. One challenge limits the adoption of such systems so far: automatic detectors ignore rare conditions that ophthalmologists currently detect, such as papilledema or anterior ischemic optic neuropathy. The reason is that standard deep learning requires too many examples of these conditions. However, this limitation can be addressed with few-shot learning, a machine learning paradigm where a classifier has to generalize to a new category not seen in training, given only a few examples of this category. This paper presents a new few-shot learning framework that extends convolutional neural networks (CNNs), trained for frequent conditions, with an unsupervised probabilistic model for rare condition detection. It is based on the observation that CNNs often perceive photographs containing the same anomalies as similar, even though these CNNs were trained to detect unrelated conditions. This observation was based on the t-SNE visualization tool, which we decided to incorporate in our probabilistic model. Experiments on a dataset of 164,660 screening examinations from the OPHDIAT screening network show that 37 conditions, out of 41, can be detected with an area under the ROC curve (AUC) greater than 0.8 (average AUC: 0.938). In particular, this framework significantly outperforms other frameworks for detecting rare conditions, including multitask learning, transfer learning and Siamese networks, another few-shot learning solution. We expect these richer predictions to trigger the adoption of automated eye pathology screening, which will revolutionize clinical practice in ophthalmology.
Progressive Perception-Oriented Network for Single Image Super-Resolution
Venue: arXiv cs.CV 2020
Year: 2020

Recently, it has been demonstrated that deep neural networks can significantly improve the performance of single image super-resolution (SISR). Numerous studies have concentrated on raising the quantitative quality of super-resolved (SR) images. However, these methods that target PSNR maximization usually produce blurred images at large upscaling factor. The introduction of generative adversarial networks (GANs) can mitigate this issue and show impressive results with synthetic high-frequency textures. Nevertheless, these GAN-based approaches always have a tendency to add fake textures and even artifacts to make the SR image of visually higher-resolution. In this paper, we propose a novel perceptual image super-resolution method that progressively generates visually high-quality results by constructing a stage-wise network. Specifically, the first phase concentrates on minimizing pixel-wise error, and the second stage utilizes the features extracted by the previous stage to pursue results with better structural retention. The final stage employs fine structure features distilled by the second phase to produce more realistic results. In this way, we can maintain the pixel, and structural level information in the perceptual image as much as possible. It is useful to note that the proposed method can build three types of images in a feed-forward process. Also, we explore a new generator that adopts multi-scale hierarchical features fusion. Extensive experiments on benchmark datasets show that our approach is superior to the state-of-the-art methods. Code is available at https://github.com/Zheng222/PPON.
Mend The Learning Approach, Not the Data: Insights for Ranking E-Commerce Products
Venue: arXiv cs.IR 2020
Year: 2020

Improved search quality enhances users' satisfaction, which directly impacts sales growth of an E-Commerce (E-Com) platform. Traditional Learning to Rank (LTR) algorithms require relevance judgments on products. In E-Com, getting such judgments poses an immense challenge. In the literature, it is proposed to employ user feedback (such as clicks, add-to-basket (AtB) clicks and orders) to generate relevance judgments. It is done in two steps: first, query-product pair data are aggregated from the logs and then order rate etc are calculated for each pair in the logs. In this paper, we advocate counterfactual risk minimization (CRM) approach which circumvents the need of relevance judgements, data aggregation and is better suited for learning from logged data, i.e. contextual bandit feedback. Due to unavailability of public E-Com LTR dataset, we provide \textit{Mercateo dataset} from our platform. It contains more than 10 million AtB click logs and 1 million order logs from a catalogue of about 3.5 million products associated with 3060 queries. To the best of our knowledge, this is the first work which examines effectiveness of CRM approach in learning ranking model from real-world logged data. Our empirical evaluation shows that our CRM approach learns effectively from logged data and beats a strong baseline ranker ($λ$-MART) by a huge margin. Our method outperforms full-information loss (e.g. cross-entropy) on various deep neural network models. These findings demonstrate that by adopting CRM approach, E-Com platforms can get better product search quality compared to full-information approach. The code and dataset can be accessed at: https://github.com/ecom-research/CRM-LTR.
SpanBERT: Improving Pre-training by Representing and Predicting Spans
Venue: arXiv cs.CL 2020
Year: 2020

We present SpanBERT, a pre-training method that is designed to better represent and predict spans of text. Our approach extends BERT by (1) masking contiguous random spans, rather than random tokens, and (2) training the span boundary representations to predict the entire content of the masked span, without relying on the individual token representations within it. SpanBERT consistently outperforms BERT and our better-tuned baselines, with substantial gains on span selection tasks such as question answering and coreference resolution. In particular, with the same training data and model size as BERT-large, our single model obtains 94.6% and 88.7% F1 on SQuAD 1.1 and 2.0, respectively. We also achieve a new state of the art on the OntoNotes coreference resolution task (79.6\% F1), strong performance on the TACRED relation extraction benchmark, and even show gains on GLUE.
A Fine-Grained Spectral Perspective on Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Are neural networks biased toward simple functions? Does depth always help learn more complex features? Is training the last layer of a network as good as training all layers? How to set the range for learning rate tuning? These questions seem unrelated at face value, but in this work we give all of them a common treatment from the spectral perspective. We will study the spectra of the *Conjugate Kernel, CK,* (also called the *Neural Network-Gaussian Process Kernel*), and the *Neural Tangent Kernel, NTK*. Roughly, the CK and the NTK tell us respectively "what a network looks like at initialization" and "what a network looks like during and after training." Their spectra then encode valuable information about the initial distribution and the training and generalization properties of neural networks. By analyzing the eigenvalues, we lend novel insights into the questions put forth at the beginning, and we verify these insights by extensive experiments of neural networks. We derive fast algorithms for computing the spectra of CK and NTK when the data is uniformly distributed over the boolean cube, and show this spectra is the same in high dimensions when data is drawn from isotropic Gaussian or uniformly over the sphere. Code replicating our results is available at github.com/thegregyang/NNspectra.
ART: Abstraction Refinement-Guided Training for Provably Correct Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Artificial Neural Networks (ANNs) have demonstrated remarkable utility in various challenging machine learning applications. While formally verified properties of their behaviors are highly desired, they have proven notoriously difficult to derive and enforce. Existing approaches typically formulate this problem as a post facto analysis process. In this paper, we present a novel learning framework that ensures such formal guarantees are enforced by construction. Our technique enables training provably correct networks with respect to a broad class of safety properties, a capability that goes well-beyond existing approaches, without compromising much accuracy. Our key insight is that we can integrate an optimization-based abstraction refinement loop into the learning process and operate over dynamically constructed partitions of the input space that considers accuracy and safety objectives synergistically. The refinement procedure iteratively splits the input space from which training data is drawn, guided by the efficacy with which such partitions enable safety verification. We have implemented our approach in a tool (ART) and applied it to enforce general safety properties on unmanned aviator collision avoidance system ACAS Xu dataset and the Collision Detection dataset. Importantly, we empirically demonstrate that realizing safety does not come at the price of much accuracy. Our methodology demonstrates that an abstraction refinement methodology provides a meaningful pathway for building both accurate and correct machine learning networks.
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we provide a $\tilde{O}(m\sqrt{n})$ time algorithm that computes a $3$-multiplicative approximation of the girth of a $n$-node $m$-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$. Additionally, for any integer $k \ge 1$, we provide a deterministic algorithm for a $O(k\log\log n)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Combining the techniques from these two results gives us an algorithm for a $O(k\log k)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs. The previous fastest algorithms for these problems either ran in All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$, or were due Pachocki et al. (PRSTV18) which provided a randomized algorithm that for any integer $k \ge 1$ in time $\tilde{O}(m^{1+1/k})$ computed with high probability a $O(k\log n)$ multiplicative approximation of the girth. Our first algorithm constitutes the first sub-APSP-time algorithm for approximating the girth to constant accuracy, our second removes the need for randomness and improves the approximation factor in Pachocki et al. (PRSTV18), and our third is the first time versus quality trade-off for obtaining constant approximations.
Protecting Spatiotemporal Event Privacy in Continuous Location-Based Services
Venue: arXiv cs.DB 2020
Year: 2020

Location privacy-preserving mechanisms (LPPMs) have been extensively studied for protecting users' location privacy by releasing a perturbed location to third parties such as location-based service providers. However, when a user's perturbed locations are released continuously, existing LPPMs may not protect the sensitive information about the user's spatiotemporal activities, such as "visited hospital in the last week" or "regularly commuting between Address 1 and Address 2" (it is easy to infer that Addresses 1 and 2 may be home and office), which we call it \textit{spatiotemporal event}. In this paper, we first formally define {spatiotemporal event} as Boolean expressions between location and time predicates, and then we define $ ε$-\textit{spatiotemporal event privacy} by extending the notion of differential privacy. Second, to understand how much spatiotemporal event privacy that existing LPPMs can provide, we design computationally efficient algorithms to quantify the privacy leakage of state-of-the-art LPPMs when an adversary has prior knowledge of the user's initial probability over possible locations. It turns out that the existing LPPMs cannot adequately protect spatiotemporal event privacy. Third, we propose a framework, PriSTE, to transform an existing LPPM into one protecting spatiotemporal event privacy against adversaries with \textit{any} prior knowledge. Our experiments on real-life and synthetic data verified that the proposed method is effective and efficient.
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Venue: arXiv cs.DS 2020
Year: 2020

We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated $2^{O(\sqrt{\log n})}$-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]---which had been called the most outstanding problem in the area. The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that $$\mathsf{P}\textit{-}\mathsf{RLOCAL} = \mathsf{P}\textit{-}\mathsf{LOCAL}.$$ That is, for any problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including $(Δ+1)$-coloring, maximal independent set, and Lovász Local Lemma, as well as massively parallel algorithms for $(Δ+1)$-coloring.
Info Intervention
Venue: arXiv cs.AI 2020
Year: 2020

Causal diagrams based on do intervention are useful tools to formalize, process and understand causal relationship among variables. However, the do intervention has controversial interpretation of causal questions for non-manipulable variables, and it also lacks the power to check the conditions related to counterfactual variables. This paper introduces a new info intervention to tackle these two problems, and provides causal diagrams for communication and theoretical focus based on this info intervention. Our info intervention intervenes the input/output information of causal mechanisms, while the do intervention intervenes the causal mechanisms. Consequently, the causality is viewed as information transfer in the info intervention framework. As an extension, the generalized info intervention is also proposed and studied in this paper.
Power Error Locating Pairs
Venue: arXiv cs.IT 2020
Year: 2020

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed--Solomon or algebraic geometry codes, the algorithm is a reformulation of the so--called {\em power decoding} algorithm. Asymptotically, it corrects errors up to Sudan's radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan's and Kötter's approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.
Fairness-Efficiency Tradeoffs in Dynamic Fair Division
Venue: arXiv cs.GT 2020
Year: 2020

We investigate the tradeoffs between fairness and efficiency when allocating indivisible items over time. Suppose T items arrive over time and must be allocated upon arrival, immediately and irrevocably, to one of n agents. Agent i assigns a value v_{it} in [0,1] to the t-th item to arrive and has an additive valuation function. If the values are chosen by an adaptive adversary it is known that the algorithm that minimizes maximum pairwise envy simply allocates each item uniformly at random; the maximum pairwise envy is then sublinear in T. If the values are independently and identically drawn from an adversarially chosen distribution D, it is also known that, under some mild conditions on D, allocating to the agent with the highest value -- a Pareto efficient allocation -- is envy-free with high probability. In this paper we study fairness-efficiency tradeoffs in this setting and provide matching upper and lower bounds under a spectrum of progressively stronger adversaries. On one hand we show that, even against a non-adaptive adversary, there is no algorithm with sublinear maximum pairwise envy that Pareto dominates the simple algorithm that allocates each item uniformly at random. On the other hand, under a slightly weaker adversary regime where item values are drawn from a known distribution and are independent with respect to time, i.e. v_{it} is independent of v_{it'} but possibly correlated with v_{i't}, optimal (in isolation) efficiency is compatible with optimal (in isolation) fairness. That is, we give an algorithm that is Pareto efficient ex-post and is simultaneously optimal with respect to fairness: for each pair of agents i and j, either i envies j by at most one item (a prominent fairness notion), or $i$ does not envy j with high probability. En route, we prove a structural result about allocations of divisible items that might be of independent interest.
FAKIR: An algorithm for revealing the anatomy and pose of statues from raw point sets
Venue: arXiv cs.GR 2020
Year: 2020

3D acquisition of archaeological artefacts has become an essential part of cultural heritage research for preservation or restoration purpose. Statues, in particular, have been at the center of many projects. In this paper, we introduce a way to improve the understanding of acquired statues representing real or imaginary creatures by registering a simple and pliable articulated model to the raw point set data. Our approach performs a Forward And bacKward Iterative Registration (FAKIR) which proceeds joint by joint, needing only a few iterations to converge. We are thus able to detect the pose and elementary anatomy of sculptures, with possibly non realistic body proportions. By adapting our simple skeleton, our method can work on animals and imaginary creatures.
A Benchmark on Tricks for Large-scale Image Retrieval
Venue: arXiv cs.CV 2020
Year: 2020

Many studies have been performed on metric learning, which has become a key ingredient in top-performing methods of instance-level image retrieval. Meanwhile, less attention has been paid to pre-processing and post-processing tricks that can significantly boost performance. Furthermore, we found that most previous studies used small scale datasets to simplify processing. Because the behavior of a feature representation in a deep learning model depends on both domain and data, it is important to understand how model behave in large-scale environments when a proper combination of retrieval tricks is used. In this paper, we extensively analyze the effect of well-known pre-processing, post-processing tricks, and their combination for large-scale image retrieval. We found that proper use of these tricks can significantly improve model performance without necessitating complex architecture or introducing loss, as confirmed by achieving a competitive result on the Google Landmark Retrieval Challenge 2019.
CAiRE: An Empathetic Neural Chatbot
Venue: arXiv cs.CL 2020
Year: 2020

In this paper, we present an end-to-end empathetic conversation agent CAiRE. Our system adapts TransferTransfo (Wolf et al., 2019) learning approach that fine-tunes a large-scale pre-trained language model with multi-task objectives: response language modeling, response prediction and dialogue emotion detection. We evaluate our model on the recently proposed empathetic-dialogues dataset (Rashkin et al., 2019), the experiment results show that CAiRE achieves state-of-the-art performance on dialogue emotion detection and empathetic response generation.
Specular- and Diffuse-reflection-based Face Spoofing Detection for Mobile Devices
Venue: arXiv cs.CV 2020
Year: 2020

In light of the rising demand for biometric-authentication systems, preventing face spoofing attacks is a critical issue for the safe deployment of face recognition systems. Here, we propose an efficient face presentation attack detection (PAD) algorithm that requires minimal hardware and only a small database, making it suitable for resource-constrained devices such as mobile phones. Utilizing one monocular visible light camera, the proposed algorithm takes two facial photos, one taken with a flash, the other without a flash. The proposed $SpecDiff$ descriptor is constructed by leveraging two types of reflection: (i) specular reflections from the iris region that have a specific intensity distribution depending on liveness, and (ii) diffuse reflections from the entire face region that represents the 3D structure of a subject's face. Classifiers trained with $SpecDiff$ descriptor outperforms other flash-based PAD algorithms on both an in-house database and on publicly available NUAA, Replay-Attack, and SiW databases. Moreover, the proposed algorithm achieves statistically significantly better accuracy to that of an end-to-end, deep neural network classifier, while being approximately six-times faster execution speed. The code is publicly available at https://github.com/Akinori-F-Ebihara/SpecDiff-spoofing-detector.