OpenRaiser/Intern-Atlas huggingface dataset:
A domain agnostic measure for monitoring and evaluating GANs
Venue: arXiv cs.LG 2020
Year: 2020

Generative Adversarial Networks (GANs) have shown remarkable results in modeling complex distributions, but their evaluation remains an unsettled issue. Evaluations are essential for: (i) relative assessment of different models and (ii) monitoring the progress of a single model throughout training. The latter cannot be determined by simply inspecting the generator and discriminator loss curves as they behave non-intuitively. We leverage the notion of duality gap from game theory to propose a measure that addresses both (i) and (ii) at a low computational cost. Extensive experiments show the effectiveness of this measure to rank different GAN models and capture the typical GAN failure scenarios, including mode collapse and non-convergent behaviours. This evaluation metric also provides meaningful monitoring on the progression of the loss during training. It highly correlates with FID on natural image datasets, and with domain specific scores for text, sound and cosmology data where FID is not directly suitable. In particular, our proposed metric requires no labels or a pretrained classifier, making it domain agnostic.
On the Robustness of Information-Theoretic Privacy Measures and Mechanisms
Venue: arXiv cs.IT 2020
Year: 2020

Consider a data publishing setting for a dataset composed by both private and non-private features. The publisher uses an empirical distribution, estimated from $n$ i.i.d. samples, to design a privacy mechanism which is applied to new fresh samples afterward. In this paper, we study the discrepancy between the privacy-utility guarantees for the empirical distribution, used to design the privacy mechanism, and those for the true distribution, experienced by the privacy mechanism in practice. We first show that, for any privacy mechanism, these discrepancies vanish at speed $O(1/\sqrt{n})$ with high probability. These bounds follow from our main technical results regarding the Lipschitz continuity of the considered information leakage measures. Then we prove that the optimal privacy mechanisms for the empirical distribution approach the corresponding mechanisms for the true distribution as the sample size $n$ increases, thereby establishing the statistical consistency of the optimal privacy mechanisms. Finally, we introduce and study uniform privacy mechanisms which, by construction, provide privacy to all the distributions within a neighborhood of the estimated distribution and, thereby, guarantee privacy for the true distribution with high probability.
Boosting Search Performance Using Query Variations
Venue: arXiv cs.IR 2020
Year: 2020

Rank fusion is a powerful technique that allows multiple sources of information to be combined into a single result set. However, to date fusion has not been regarded as being cost-effective in cases where strict per-query efficiency guarantees are required, such as in web search. In this work we propose a novel solution to rank fusion by splitting the computation into two parts -- one phase that is carried out offline to generate pre-computed centroid answers for queries with broadly similar information needs, and then a second online phase that uses the corresponding topic centroid to compute a result page for each query. We explore efficiency improvements to classic fusion algorithms whose costs can be amortized as a pre-processing step, and can then be combined with re-ranking approaches to dramatically improve effectiveness in multi-stage retrieval systems with little efficiency overhead at query time. Experimental results using the ClueWeb12B collection and the UQV100 query variations demonstrate that centroid-based approaches allow improved retrieval effectiveness at little or no loss in query throughput or latency, and with reasonable pre-processing requirements. We additionally show that queries that do not match any of the pre-computed clusters can be accurately identified and efficiently processed in our proposed ranking pipeline.
Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
Venue: arXiv cs.LG 2020
Year: 2020

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with $k$ blocks of equal size. More precisely, we consider a random $d$-uniform hypergraph $H$ with $n$ vertices partitioned into $k$ clusters of size $s = n / k$. Hyperedges $e$ are added independently with probability $p$ if $e$ is contained within a single cluster and $q$ otherwise, where $0 \leq q < p \leq 1$. We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on $n, k, p, q$, and $d$. Our algorithm is based on the adjacency matrix of $H$, which is a symmetric $n \times n$ matrix whose $(u, v)$-th entry is the number of hyperedges containing both $u$ and $v$. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters $k=Θ(\sqrt{n})$.
Relational Long Short-Term Memory for Video Action Recognition
Venue: arXiv cs.CV 2020
Year: 2020

Spatial and temporal relationships, both short-range and long-range, between objects in videos, are key cues for recognizing actions. It is a challenging problem to model them jointly. In this paper, we first present a new variant of Long Short-Term Memory, namely Relational LSTM, to address the challenge of relation reasoning across space and time between objects. In our Relational LSTM module, we utilize a non-local operation similar in spirit to the recently proposed non-local network to substitute the fully connected operation in the vanilla LSTM. By doing this, our Relational LSTM is capable of capturing long and short-range spatio-temporal relations between objects in videos in a principled way. Then, we propose a two-branch neural architecture consisting of the Relational LSTM module as the non-local branch and a spatio-temporal pooling based local branch. The local branch is utilized for capturing local spatial appearance and/or short-term motion features. The two branches are concatenated to learn video-level features from snippet-level ones which are then used for classification. Experimental results on UCF-101 and HMDB-51 datasets show that our model achieves state-of-the-art results among LSTM-based methods, while obtaining comparable performance with other state-of-the-art methods (which use not directly comparable schema). Further, on the more complex large-scale Charades dataset, we obtain a large 3.2% gain over state-of-the-art methods, verifying the effectiveness of our method in complex understanding.
Revisiting Image-Language Networks for Open-ended Phrase Detection
Venue: arXiv cs.CV 2020
Year: 2020

Most existing work that grounds natural language phrases in images starts with the assumption that the phrase in question is relevant to the image. In this paper we address a more realistic version of the natural language grounding task where we must both identify whether the phrase is relevant to an image and localize the phrase. This can also be viewed as a generalization of object detection to an open-ended vocabulary, introducing elements of few- and zero-shot detection. We propose an approach for this task that extends Faster R-CNN to relate image regions and phrases. By carefully initializing the classification layers of our network using canonical correlation analysis (CCA), we encourage a solution that is more discerning when reasoning between similar phrases, resulting in over double the performance compared to a naive adaptation on three popular phrase grounding datasets, Flickr30K Entities, ReferIt Game, and Visual Genome, with test-time phrase vocabulary sizes of 5K, 32K, and 159K, respectively.
Handling polymorphic algebraic effects
Venue: arXiv cs.PL 2020
Year: 2020

Algebraic effects and handlers are a powerful abstraction mechanism to represent and implement control effects. In this work, we study their extension with parametric polymorphism that allows abstracting not only expressions but also effects and handlers. Although polymorphism makes it possible to reuse and reason about effect implementations more effectively, it has long been known that a naive combination of polymorphic effects and let-polymorphism breaks type safety. Although type safety can often be gained by restricting let-bound expressions---e.g., by adopting value restriction or weak polymorphism---we propose a complementary approach that restricts handlers instead of let-bound expressions. Our key observation is that, informally speaking, a handler is safe if resumptions from the handler do not interfere with each other. To formalize our idea, we define a call-by-value lambda calculus that supports let-polymorphism and polymorphic algebraic effects and handlers, design a type system that rejects interfering handlers, and prove type safety of our calculus.
A Practical Mode System for Recursive Definitions
Venue: arXiv cs.PL 2020
Year: 2020

In call-by-value languages, some mutually-recursive value definitions can be safely evaluated to build recursive functions or cyclic data structures, but some definitions (let rec x = x + 1) contain vicious circles and their evaluation fails at runtime. We propose a new static analysis to check the absence of such runtime failures. We present a set of declarative inference rules, prove its soundness with respect to the reference source-level semantics of Nordlander, Carlsson, and Gill (2008), and show that it can be (right-to-left) directed into an algorithmic check in a surprisingly simple way. Our implementation of this new check replaced the existing check used by the OCaml programming language, a fragile syntactic/grammatical criterion which let several subtle bugs slip through as the language kept evolving. We document some issues that arise when advanced features of a real-world functional language (exceptions in first-class modules, GADTs, etc.) interact with safety checking for recursive definitions.
Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians
Venue: arXiv cs.GT 2020
Year: 2020

We show that computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions $l_{e,i}(x) = a_{e,i} x + b_{e,i}$ is $\mathsf{PPAD}$-complete. To prove that the problem is contained in $\mathsf{PPAD}$, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix. Using the properties of this matrix give rise to a path following formulation for computing an equilibrium where states correspond to supports that are feasible for some demands. A closer investigation of the block Laplacian system further allows to orient the states giving rise to unique predecessor and successor states thus putting the problem into $\mathsf{PPAD}$. For the $\mathsf{PPAD}$-hardness, we reduce from computing an approximate equilibrium of a bimatrix win-lose game. As a byproduct of our reduction we further show that computing a multi-class Wardrop equilibrium with class dependent affine cost functions is $\mathsf{PPAD}$-complete as well. As another byproduct of our $\mathsf{PPAD}$-completeness proof, we obtain an algorithm that computes a continuum of equilibria parametrized by the players' flow demand. For player-specific costs, the algorithm runs in polynomial space. For games with player-independent costs, we obtain an algorithm computing all equilibria as a function of the flow demand that runs in time polynomial in the output.
Killing the Password and Preserving Privacy with Device-Centric and Attribute-based Authentication
Venue: arXiv cs.CR 2020
Year: 2020

Current authentication methods on the Web have serious weaknesses. First, services heavily rely on the traditional password paradigm, which diminishes the end-users' security and usability. Second, the lack of attribute-based authentication does not allow anonymity-preserving access to services. Third, users have multiple online accounts that often reflect distinct identity aspects. This makes proving combinations of identity attributes hard on the users. In this paper, we address these weaknesses by proposing a privacy-preserving architecture for device-centric and attribute-based authentication based on: 1) the seamless integration between usable/strong device-centric authentication methods and federated login solutions; 2) the separation of the concerns for Authorization, Authentication, Behavioral Authentication and Identification to facilitate incremental deployability, wide adoption and compliance with NIST assurance levels; and 3) a novel centralized component that allows end-users to perform identity profile and consent management, to prove combinations of fragmented identity aspects, and to perform account recovery in case of device loss. To the best of our knowledge, this is the first effort towards fusing the aforementioned techniques under an integrated architecture. This architecture effectively deems the password paradigm obsolete with minimal modification on the service provider's software stack.
Synetgy: Algorithm-hardware Co-design for ConvNet Accelerators on Embedded FPGAs
Venue: arXiv cs.CV 2020
Year: 2020

Using FPGAs to accelerate ConvNets has attracted significant attention in recent years. However, FPGA accelerator design has not leveraged the latest progress of ConvNets. As a result, the key application characteristics such as frames-per-second (FPS) are ignored in favor of simply counting GOPs, and results on accuracy, which is critical to application success, are often not even reported. In this work, we adopt an algorithm-hardware co-design approach to develop a ConvNet accelerator called Synetgy and a novel ConvNet model called DiracDeltaNet$^{\dagger}$. Both the accelerator and ConvNet are tailored to FPGA requirements. DiracDeltaNet, as the name suggests, is a ConvNet with only $1\times 1$ convolutions while spatial convolutions are replaced by more efficient shift operations. DiracDeltaNet achieves competitive accuracy on ImageNet (88.7\% top-5), but with 42$\times$ fewer parameters and 48$\times$ fewer OPs than VGG16. We further quantize DiracDeltaNet's weights to 4-bit and activations to 4-bits, with less than 1\% accuracy loss. These quantizations exploit well the nature of FPGA hardware. In short, DiracDeltaNet's small model size, low computational OP count, low precision and simplified operators allow us to co-design a highly customized computing unit for an FPGA. We implement the computing units for DiracDeltaNet on an Ultra96 SoC system through high-level synthesis. Our accelerator's final top-5 accuracy of 88.1\% on ImageNet, is higher than all the previously reported embedded FPGA accelerators. In addition, the accelerator reaches an inference speed of 66.3 FPS on the ImageNet classification task, surpassing prior works with similar accuracy by at least 11.6$\times$.
A Neural Network Study of Blasius Equation
Venue: arXiv cs.LG 2020
Year: 2020

In this work we applied a feed forward neural network to solve Blasius equation which is a third-order nonlinear differential equation. Blasius equation is a kind of boundary layer flow. We solved Blasius equation without reducing it into a system of first order equation. Numerical results are presented and a comparison according to some studies is made in the form of their results. Obtained results are found to be in good agreement with the given studies.
A Simple Non-i.i.d. Sampling Approach for Efficient Training and Better Generalization
Venue: arXiv cs.CV 2020
Year: 2020

While training on samples drawn from independent and identical distribution has been a de facto paradigm for optimizing image classification networks, humans learn new concepts in an easy-to-hard manner and on the selected examples progressively. Driven by this fact, we investigate the training paradigms where the samples are not drawn from independent and identical distribution. We propose a data sampling strategy, named Drop-and-Refresh (DaR), motivated by the learning behaviors of humans that selectively drop easy samples and refresh them only periodically. We show in our experiments that the proposed DaR strategy can maintain (and in many cases improve) the predictive accuracy even when the training cost is reduced by 15% on various datasets (CIFAR 10, CIFAR 100 and ImageNet) and with different backbone architectures (ResNets, DenseNets and MobileNets). Furthermore and perhaps more importantly, we find the ImageNet pre-trained models using our DaR sampling strategy achieves better transferability for the downstream tasks including object detection (+0.3 AP), instance segmentation (+0.3 AP), scene parsing (+0.5 mIoU) and human pose estimation (+0.6 AP). Our investigation encourages people to rethink the connections between the sampling strategy for training and the transferability of its learned features for pre-training ImageNet models.
Predicting Diabetes Disease Evolution Using Financial Records and Recurrent Neural Networks
Venue: arXiv cs.LG 2020
Year: 2020

Managing patients with chronic diseases is a major and growing healthcare challenge in several countries. A chronic condition, such as diabetes, is an illness that lasts a long time and does not go away, and often leads to the patient's health gradually getting worse. While recent works involve raw electronic health record (EHR) from hospitals, this work uses only financial records from health plan providers (medical claims) to predict diabetes disease evolution with a self-attentive recurrent neural network. The use of financial data is due to the possibility of being an interface to international standards, as the records standard encodes medical procedures. The main goal was to assess high risk diabetics, so we predict records related to diabetes acute complications such as amputations and debridements, revascularization and hemodialysis. Our work succeeds to anticipate complications between 60 to 240 days with an area under ROC curve ranging from 0.81 to 0.94. In this paper we describe the first half of a work-in-progress developed within a health plan provider with ROC curve ranging from 0.81 to 0.83. This assessment will give healthcare providers the chance to intervene earlier and head off hospitalizations. We are aiming to deliver personalized predictions and personalized recommendations to individual patients, with the goal of improving outcomes and reducing costs
On the Structure Theory of Partial Automaton Semigroups
Venue: arXiv cs.FL 2020
Year: 2020

We study automaton structures, i.e. groups, monoids and semigroups generated by an automaton, which, in this context, means a deterministic finite-state letter-to-letter transducer. Instead of considering only complete automata, we specifically investigate semigroups generated by partial automata. First, we show that the class of semigroups generated by partial automata coincides with the class of semigroups generated by complete automata if and only if the latter class is closed under removing a previously adjoined zero, which is an open problem in (complete) automaton semigroup theory stated by Cain. Then, we show that no semidirect product (and, thus, also no direct product) of an arbitrary semigroup with a (non-trivial) subsemigroup of the free monogenic semigroup is an automaton semigroup. Finally, we concentrate on inverse semigroups generated by invertible but partial automata, which we call automaton-inverse semigroups, and show that any inverse automaton semigroup can be generated by such an automaton (showing that automaton-inverse semigroups and inverse automaton semigroups coincide).
LSD$_2$ -- Joint Denoising and Deblurring of Short and Long Exposure Images with CNNs
Venue: arXiv cs.CV 2020
Year: 2020

The paper addresses the problem of acquiring high-quality photographs with handheld smartphone cameras in low-light imaging conditions. We propose an approach based on capturing pairs of short and long exposure images in rapid succession and fusing them into a single high-quality photograph. Unlike existing methods, we take advantage of both images simultaneously and perform a joint denoising and deblurring using a convolutional neural network. A novel approach is introduced to generate realistic short-long exposure image pairs. The method produces good images in extremely challenging conditions and outperforms existing denoising and deblurring methods. It also enables exposure fusion in the presence of motion blur.
MonoGRNet: A Geometric Reasoning Network for Monocular 3D Object Localization
Venue: arXiv cs.CV 2020
Year: 2020

Detecting and localizing objects in the real 3D space, which plays a crucial role in scene understanding, is particularly challenging given only a single RGB image due to the geometric information loss during imagery projection. We propose MonoGRNet for the amodal 3D object detection from a monocular RGB image via geometric reasoning in both the observed 2D projection and the unobserved depth dimension. MonoGRNet is a single, unified network composed of four task-specific subnetworks, responsible for 2D object detection, instance depth estimation (IDE), 3D localization and local corner regression. Unlike the pixel-level depth estimation that needs per-pixel annotations, we propose a novel IDE method that directly predicts the depth of the targeting 3D bounding box's center using sparse supervision. The 3D localization is further achieved by estimating the position in the horizontal and vertical dimensions. Finally, MonoGRNet is jointly learned by optimizing the locations and poses of the 3D bounding boxes in the global context. We demonstrate that MonoGRNet achieves state-of-the-art performance on challenging datasets.
Robust Cross-View Gait Recognition with Evidence: A Discriminant Gait GAN (DiGGAN) Approach
Venue: arXiv cs.CV 2020
Year: 2020

Gait as a biometric trait has attracted much attention in many security and privacy applications such as identity recognition and authentication, during the last few decades. Because of its nature as a long-distance biometric trait, gait can be easily collected and used to identify individuals non-intrusively through CCTV cameras. However, it is very difficult to develop robust automated gait recognition systems, since gait may be affected by many covariate factors such as clothing, walking speed, camera view angle etc. Out of them, large view angle changes has been deemed as the most challenging factor as it can alter the overall gait appearance substantially. Existing works on gait recognition are far from enough to provide satisfying performances because of such view changes. Furthermore, very few works have considered evidences -- the demonstrable information revealing the reliabilities of decisions, which are regarded as important demands in machine learning-based recognition/authentication applications. To address these issues, in this paper we propose a Discriminant Gait Generative Adversarial Network, namely DiGGAN, which can effectively extract view-invariant features for cross-view gait recognition; and more importantly, to transfer gait images to different views -- serving as evidences and showing how the decisions have been made. Quantitative experiments have been conducted on the two most popular cross-view gait datasets, the OU-MVLP and CASIA-B, where the proposed DiGGAN has outperformed state-of-the-art methods. Qualitative analysis has also been provided and demonstrates the proposed DiGGAN's capability in providing evidences.