OpenRaiser/Intern-Atlas huggingface dataset:
Explaining Deep Neural Networks
Venue: arXiv cs.CL 2021
Year: 2021

Deep neural networks are becoming more and more popular due to their revolutionary success in diverse areas, such as computer vision, natural language processing, and speech recognition. However, the decision-making processes of these models are generally not interpretable to users. In various domains, such as healthcare, finance, or law, it is critical to know the reasons behind a decision made by an artificial intelligence system. Therefore, several directions for explaining neural models have recently been explored. In this thesis, I investigate two major directions for explaining deep neural networks. The first direction consists of feature-based post-hoc explanatory methods, that is, methods that aim to explain an already trained and fixed model (post-hoc), and that provide explanations in terms of input features, such as tokens for text and superpixels for images (feature-based). The second direction consists of self-explanatory neural models that generate natural language explanations, that is, models that have a built-in module that generates explanations for the predictions of the model.
Reverse Operation based Data Augmentation for Solving Math Word Problems
Venue: arXiv cs.CL 2021
Year: 2021

Automatically solving math word problems is a critical task in the field of natural language processing. Recent models have reached their performance bottleneck and require more high-quality data for training. We propose a novel data augmentation method that reverses the mathematical logic of math word problems to produce new high-quality math problems and introduce new knowledge points that can benefit learning the mathematical reasoning logic. We apply the augmented data on two SOTA math word problem solving models and compare our results with a strong data augmentation baseline. Experimental results show the effectiveness of our approach. We release our code and data at https://github.com/yiyunya/RODA.
A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
Venue: arXiv cs.LG 2021
Year: 2021

Incorporating a so-called "momentum" dynamic in gradient descent methods is widely used in neural net training as it has been broadly observed that, at least empirically, it often leads to significantly faster convergence. At the same time, there are very few theoretical guarantees in the literature to explain this apparent acceleration effect. Even for the classical strongly convex quadratic problems, several existing results only show Polyak's momentum has an accelerated linear rate asymptotically. In this paper, we first revisit the quadratic problems and show a non-asymptotic accelerated linear rate of Polyak's momentum. Then, we provably show that Polyak's momentum achieves acceleration for training a one-layer wide ReLU network and a deep linear network, which are perhaps the two most popular canonical models for studying optimization and deep learning in the literature. Prior work Du at al. 2019 and Wu et al. 2019 showed that using vanilla gradient descent, and with an use of over-parameterization, the error decays as $(1- Θ(\frac{1}{ κ'}))^t$ after $t$ iterations, where $κ'$ is the condition number of a Gram Matrix. Our result shows that with the appropriate choice of parameters Polyak's momentum has a rate of $(1-Θ(\frac{1}{\sqrt{κ'}}))^t$. For the deep linear network, prior work Hu et al. 2020 showed that vanilla gradient descent has a rate of $(1-Θ(\frac{1}κ))^t$, where $κ$ is the condition number of a data matrix. Our result shows an acceleration rate $(1- Θ(\frac{1}{\sqrtκ}))^t$ is achievable by Polyak's momentum. All the results in this work are obtained from a modular analysis, which can be of independent interest. This work establishes that momentum does indeed speed up neural net training.
Optimal Neural Program Synthesis from Multimodal Specifications
Venue: arXiv cs.CL 2021
Year: 2021

Multimodal program synthesis, which leverages different types of user input to synthesize a desired program, is an attractive way to scale program synthesis to challenging settings; however, it requires integrating noisy signals from the user, like natural language, with hard constraints on the program's behavior. This paper proposes an optimal neural synthesis approach where the goal is to find a program that satisfies user-provided constraints while also maximizing the program's score with respect to a neural model. Specifically, we focus on multimodal synthesis tasks in which the user intent is expressed using a combination of natural language (NL) and input-output examples. At the core of our method is a top-down recurrent neural model that places distributions over abstract syntax trees conditioned on the NL input. This model not only allows for efficient search over the space of syntactically valid programs, but it allows us to leverage automated program analysis techniques for pruning the search space based on infeasibility of partial programs with respect to the user's constraints. The experimental results on a multimodal synthesis dataset (StructuredRegex) show that our method substantially outperforms prior state-of-the-art techniques in terms of accuracy and efficiency, and finds model-optimal programs more frequently.
Revisiting Batch Normalization for Training Low-latency Deep Spiking Neural Networks from Scratch
Venue: arXiv cs.CV 2021
Year: 2021

Spiking Neural Networks (SNNs) have recently emerged as an alternative to deep learning owing to sparse, asynchronous and binary event (or spike) driven processing, that can yield huge energy efficiency benefits on neuromorphic hardware. However, training high-accuracy and low-latency SNNs from scratch suffers from non-differentiable nature of a spiking neuron. To address this training issue in SNNs, we revisit batch normalization and propose a temporal Batch Normalization Through Time (BNTT) technique. Most prior SNN works till now have disregarded batch normalization deeming it ineffective for training temporal SNNs. Different from previous works, our proposed BNTT decouples the parameters in a BNTT layer along the time axis to capture the temporal dynamics of spikes. The temporally evolving learnable parameters in BNTT allow a neuron to control its spike rate through different time-steps, enabling low-latency and low-energy training from scratch. We conduct experiments on CIFAR-10, CIFAR-100, Tiny-ImageNet and event-driven DVS-CIFAR10 datasets. BNTT allows us to train deep SNN architectures from scratch, for the first time, on complex datasets with just few 25-30 time-steps. We also propose an early exit algorithm using the distribution of parameters in BNTT to reduce the latency at inference, that further improves the energy-efficiency.
Joint Scene and Object Tracking for Cost-Effective Augmented Reality Assisted Patient Positioning in Radiation Therapy
Venue: arXiv cs.CV 2021
Year: 2021

BACKGROUND AND OBJECTIVE: The research done in the field of Augmented Reality (AR) for patient positioning in radiation therapy is scarce. We propose an efficient and cost-effective algorithm for tracking the scene and the patient to interactively assist the patient's positioning process by providing visual feedback to the operator. Up to our knowledge, this is the first framework that can be employed for mobile interactive AR to guide patient positioning. METHODS: We propose a point cloud processing method that combined with a fiducial marker-mapper algorithm and the generalized ICP algorithm tracks the patient and the camera precisely and efficiently only using the CPU unit. The alignment between the 3D reference model and body marker map is calculated employing an efficient body reconstruction algorithm. RESULTS: Our quantitative evaluation shows that the proposed method achieves a translational and rotational error of 4.17 mm/0.82 deg at 9 fps. Furthermore, the qualitative results demonstrate the usefulness of our algorithm in patient positioning on different human subjects. CONCLUSION: Since our algorithm achieves a relatively high frame rate and accuracy employing a regular laptop (without the usage of a dedicated GPU), it is a very cost-effective AR-based patient positioning method. It also opens the way for other researchers by introducing a framework that could be improved upon for better mobile interactive AR patient positioning solutions in the future.
BalaGAN: Image Translation Between Imbalanced Domains via Cross-Modal Transfer
Venue: arXiv cs.CV 2021
Year: 2021

State-of-the-art image-to-image translation methods tend to struggle in an imbalanced domain setting, where one image domain lacks richness and diversity. We introduce a new unsupervised translation network, BalaGAN, specifically designed to tackle the domain imbalance problem. We leverage the latent modalities of the richer domain to turn the image-to-image translation problem, between two imbalanced domains, into a balanced, multi-class, and conditional translation problem, more resembling the style transfer setting. Specifically, we analyze the source domain and learn a decomposition of it into a set of latent modes or classes, without any supervision. This leaves us with a multitude of balanced cross-domain translation tasks, between all pairs of classes, including the target domain. During inference, the trained network takes as input a source image, as well as a reference or style image from one of the modes as a condition, and produces an image which resembles the source on the pixel-wise level, but shares the same mode as the reference. We show that employing modalities within the dataset improves the quality of the translated images, and that BalaGAN outperforms strong baselines of both unconditioned and style-transfer-based image-to-image translation methods, in terms of image quality and diversity.
Exploring the Interchangeability of CNN Embedding Spaces
Venue: arXiv cs.CV 2021
Year: 2021

CNN feature spaces can be linearly mapped and consequently are often interchangeable. This equivalence holds across variations in architectures, training datasets, and network tasks. Specifically, we mapped between 10 image-classification CNNs and between 4 facial-recognition CNNs. When image embeddings generated by one CNN are transformed into embeddings corresponding to the feature space of a second CNN trained on the same task, their respective image classification or face verification performance is largely preserved. For CNNs trained to the same classes and sharing a common backend-logit (soft-max) architecture, a linear-mapping may always be calculated directly from the backend layer weights. However, the case of a closed-set analysis with perfect knowledge of classifiers is limiting. Therefore, empirical methods of estimating mappings are presented for both the closed-set image classification task and the open-set task of face recognition. The results presented expose the essentially interchangeable nature of CNNs embeddings for two important and common recognition tasks. The implications are far-reaching, suggesting an underlying commonality between representations learned by networks designed and trained for a common task. One practical implication is that face embeddings from some commonly used CNNs can be compared using these mappings.
A Query-Efficient Quantum Algorithm for Maximum Matching on General Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We design quantum algorithms for maximum matching. Working in the query model, in both adjacency matrix and adjacency list settings, we improve on the best known algorithms for general graphs, matching previously obtained results for bipartite graphs. In particular, for a graph with $n$ nodes and $m$ edges, our algorithm makes $O(n^{7/4})$ queries in the matrix model and $O(n^{3/4}(m+n)^{1/2})$ queries in the list model. Our approach combines Gabow's classical maximum matching algorithm [Gabow, Fundamenta Informaticae, '17] with the guessing tree method of Beigi and Taghavi [Beigi and Taghavi, Quantum, '20].
Automotive Radar Data Acquisition using Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

The growing urban complexity demands an efficient algorithm to acquire and process various sensor information from autonomous vehicles. In this paper, we introduce an algorithm to utilize object detection results from the image to adaptively sample and acquire radar data using Compressed Sensing (CS). This novel algorithm is motivated by the hypothesis that with a limited sampling budget, allocating more sampling budget to areas with the object as opposed to a uniform sampling ultimately improves relevant object detection performance. We improve detection performance by dynamically allocating a lower sampling rate to objects such as buses than pedestrians leading to better reconstruction than baseline across areas with objects of interest. We automate the sampling rate allocation using linear programming and show significant time savings while reducing the radar block size by a factor of 2. We also analyze a Binary Permuted Diagonal measurement matrix for radar acquisition which is hardware-efficient and show its performance is similar to Gaussian and Binary Permuted Block Diagonal matrix. Our experiments on the Oxford radar dataset show an effective reconstruction of objects of interest with 10% sampling rate. Finally, we develop a transformer-based 2D object detection network using the NuScenes radar and image data.
A Note on Exponential-Time Algorithms for Linearwidth
Venue: arXiv cs.DS 2021
Year: 2021

In this note, we give an algorithm that computes the linearwidth of input $n$-vertex graphs in time $O^*(2^n)$, which improves a trivial $O^*(2^m)$-time algorithm, where $n$ and $m$ the number of vertices and edges, respectively.
Publication Patterns' Changes due to the COVID-19 Pandemic: A longitudinal and short-term scientometric analysis
Venue: arXiv cs.DL 2021
Year: 2021

In recent months the COVID-19 (also known as SARS-CoV-2 and Coronavirus) pandemic has spread throughout the world. In parallel, extensive scholarly research regarding various aspects of the pandemic has been published. In this work, we analyse the changes in biomedical publishing patterns due to the pandemic. We study the changes in the volume of publications in both peer reviewed journals and preprint servers, average time to acceptance of papers submitted to biomedical journals, international (co-)authorship of these papers (expressed by diversity and volume), and the possible association between journal metrics and said changes. We study these possible changes using two approaches: a short-term analysis through which changes during the first six months of the outbreak are examined for both COVID-19 related papers and non-COVID-19 related papers; and a longitudinal approach through which changes are examined in comparison to the previous four years. Our results show that the pandemic has so far had a tremendous effect on all examined accounts of scholarly publications: A sharp increase in publication volume has been witnessed and it can be almost entirely attributed to the pandemic; a significantly faster mean time to acceptance for COVID-19 papers is apparent, and it has (partially) come at the expense of non-COVID-19 papers; and a significant reduction in international collaboration for COVID-19 papers has also been identified. As the pandemic continues to spread, these changes may cause a slow down in research in non-COVID-19 biomedical fields and bring about a lower rate of international collaboration.
Efficient computation of contrastive explanations
Venue: arXiv cs.LG 2021
Year: 2021

With the increasing deployment of machine learning systems in practice, transparency and explainability have become serious issues. Contrastive explanations are considered to be useful and intuitive, in particular when it comes to explaining decisions to lay people, since they mimic the way in which humans explain. Yet, so far, comparably little research has addressed computationally feasible technologies, which allow guarantees on uniqueness and optimality of the explanation and which enable an easy incorporation of additional constraints. Here, we will focus on specific types of models rather than black-box technologies. We study the relation of contrastive and counterfactual explanations and propose mathematical formalizations as well as a 2-phase algorithm for efficiently computing (plausible) pertinent positives of many standard machine learning models.
Representation learning from videos in-the-wild: An object-centric approach
Venue: arXiv cs.CV 2021
Year: 2021

We propose a method to learn image representations from uncurated videos. We combine a supervised loss from off-the-shelf object detectors and self-supervised losses which naturally arise from the video-shot-frame-object hierarchy present in each video. We report competitive results on 19 transfer learning tasks of the Visual Task Adaptation Benchmark (VTAB), and on 8 out-of-distribution-generalization tasks, and discuss the benefits and shortcomings of the proposed approach. In particular, it improves over the baseline on all 18/19 few-shot learning tasks and 8/8 out-of-distribution generalization tasks. Finally, we perform several ablation studies and analyze the impact of the pretrained object detector on the performance across this suite of tasks.
On Euclidean Steiner $(1+ε)$-Spanners
Venue: arXiv cs.CG 2021
Year: 2021

Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+\varepsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $\varepsilon>0$ for constant $d\in \mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+\varepsilon)$-spanner. They gave upper bounds of $\tilde{O}(\varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $d\geq 3$, and $\tilde{O}(\varepsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $d\geq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\logΔ)$ in the plane, where $Δ\in Ω(\sqrt{n})$ is the \emph{spread} of $S$, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+\varepsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Ω(\varepsilon^{-d/2})$ for the lightness and $Ω(\varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $d\geq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\log n)$ for $n$ points in Euclidean plane.
Validating UTF-8 In Less Than One Instruction Per Byte
Venue: arXiv cs.DB 2021
Year: 2021

The majority of text is stored in UTF-8, which must be validated on ingestion. We present the lookup algorithm, which outperforms UTF-8 validation routines used in many libraries and languages by more than 10 times using commonly available SIMD instructions. To ensure reproducibility, our work is freely available as open source software.
Structured Logconcave Sampling with a Restricted Gaussian Oracle
Venue: arXiv cs.DS 2021
Year: 2021

We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization, which bootstraps samplers for regularized densities to improve dependences on problem conditioning. A key ingredient in our framework is the notion of a "restricted Gaussian oracle" (RGO) for $g: \mathbb{R}^d \rightarrow \mathbb{R}$, which is a sampler for distributions whose negative log-likelihood sums a quadratic and $g$. By combining our reduction framework with our new samplers, we obtain the following bounds for sampling structured distributions to total variation distance $ε$. For composite densities $\exp(-f(x) - g(x))$, where $f$ has condition number $κ$ and convex (but possibly non-smooth) $g$ admits an RGO, we obtain a mixing time of $O(κd \log^3\frac{κd}ε)$, matching the state-of-the-art non-composite bound; no composite samplers with better mixing than general-purpose logconcave samplers were previously known. For logconcave finite sums $\exp(-F(x))$, where $F(x) = \frac{1}{n}\sum_{i \in [n]} f_i(x)$ has condition number $κ$, we give a sampler querying $\widetilde{O}(n + κ\max(d, \sqrt{nd}))$ gradient oracles to $\{f_i\}_{i \in [n]}$; no high-accuracy samplers with nontrivial gradient query complexity were previously known. For densities with condition number $κ$, we give an algorithm obtaining mixing time $O(κd \log^2\frac{κd}ε)$, improving the prior state-of-the-art by a logarithmic factor with a significantly simpler analysis; we also show a zeroth-order algorithm attains the same query complexity.
Visual Object Recognition in Indoor Environments Using Topologically Persistent Features
Venue: arXiv cs.CV 2021
Year: 2021

Object recognition in unseen indoor environments remains a challenging problem for visual perception of mobile robots. In this letter, we propose the use of topologically persistent features, which rely on the objects' shape information, to address this challenge. In particular, we extract two kinds of features, namely, sparse persistence image (PI) and amplitude, by applying persistent homology to multi-directional height function-based filtrations of the cubical complexes representing the object segmentation maps. The features are then used to train a fully connected network for recognition. For performance evaluation, in addition to a widely used shape dataset and a benchmark indoor scenes dataset, we collect a new dataset, comprising scene images from two different environments, namely, a living room and a mock warehouse. The scenes are captured using varying camera poses under different illumination conditions and include up to five different objects from a given set of fourteen objects. On the benchmark indoor scenes dataset, sparse PI features show better recognition performance in unseen environments than the features learned using the widely used ResNetV2-56 and EfficientNet-B4 models. Further, they provide slightly higher recall and accuracy values than Faster R-CNN, an end-to-end object detection method, and its state-of-the-art variant, Domain Adaptive Faster R-CNN. The performance of our methods also remains relatively unchanged from the training environment (living room) to the unseen environment (mock warehouse) in the new dataset. In contrast, the performance of the object detection methods drops substantially. We also implement the proposed method on a real-world robot to demonstrate its usefulness.
A Survey of Deep Meta-Learning
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks can achieve great successes when presented with large data sets and sufficient computational resources. However, their ability to learn new concepts quickly is limited. Meta-learning is one approach to address this issue, by enabling the network to learn how to learn. The field of Deep Meta-Learning advances at great speed, but lacks a unified, in-depth overview of current techniques. With this work, we aim to bridge this gap. After providing the reader with a theoretical foundation, we investigate and summarize key methods, which are categorized into i)~metric-, ii)~model-, and iii)~optimization-based techniques. In addition, we identify the main open challenges, such as performance evaluations on heterogeneous benchmarks, and reduction of the computational costs of meta-learning.