OpenRaiser/Intern-Atlas huggingface dataset:
BitTrain: Sparse Bitmap Compression for Memory-Efficient Training on the Edge
Venue: arXiv cs.LG 2021
Year: 2021

Training on the Edge enables neural networks to learn continuously from new data after deployment on memory-constrained edge devices. Previous work is mostly concerned with reducing the number of model parameters which is only beneficial for inference. However, memory footprint from activations is the main bottleneck for training on the edge. Existing incremental training methods fine-tune the last few layers sacrificing accuracy gains from re-training the whole model. In this work, we investigate the memory footprint of training deep learning models, and use our observations to propose BitTrain. In BitTrain, we exploit activation sparsity and propose a novel bitmap compression technique that reduces the memory footprint during training. We save the activations in our proposed bitmap compression format during the forward pass of the training, and restore them during the backward pass for the optimizer computations. The proposed method can be integrated seamlessly in the computation graph of modern deep learning frameworks. Our implementation is safe by construction, and has no negative impact on the accuracy of model training. Experimental results show up to 34% reduction in the memory footprint at a sparsity level of 50%. Further pruning during training results in more than 70% sparsity, which can lead to up to 56% reduction in memory footprint. BitTrain advances the efforts towards bringing more machine learning capabilities to edge devices. Our source code is available at https://github.com/scale-lab/BitTrain.
EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
Venue: arXiv cs.DS 2021
Year: 2021

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for \textsc{Maximum Clique} on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time $2^{\tilde{O}(n^{2/3})}$ for \textsc{Maximum Clique} on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for \textsc{Max Clique} on disk and unit ball graphs. \textsc{Max Clique} on unit ball graphs is equivalent to finding, given a collection of points in $\mathbb R^3$, a maximum subset of points with diameter at most some fixed value. In stark contrast, \textsc{Maximum Clique} on ball graphs and unit $4$-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation which cannot be attained even in time $2^{n^{1-\varepsilon}}$, unless the Exponential Time Hypothesis fails.
Dense Hierarchical Retrieval for Open-Domain Question Answering
Venue: arXiv cs.IR 2021
Year: 2021

Dense neural text retrieval has achieved promising results on open-domain Question Answering (QA), where latent representations of questions and passages are exploited for maximum inner product search in the retrieval process. However, current dense retrievers require splitting documents into short passages that usually contain local, partial, and sometimes biased context, and highly depend on the splitting process. As a consequence, it may yield inaccurate and misleading hidden representations, thus deteriorating the final retrieval result. In this work, we propose Dense Hierarchical Retrieval (DHR), a hierarchical framework that can generate accurate dense representations of passages by utilizing both macroscopic semantics in the document and microscopic semantics specific to each passage. Specifically, a document-level retriever first identifies relevant documents, among which relevant passages are then retrieved by a passage-level retriever. The ranking of the retrieved passages will be further calibrated by examining the document-level relevance. In addition, hierarchical title structure and two negative sampling strategies (i.e., In-Doc and In-Sec negatives) are investigated. We apply DHR to large-scale open-domain QA datasets. DHR significantly outperforms the original dense passage retriever and helps an end-to-end QA system outperform the strong baselines on multiple open-domain QA benchmarks.
GalilAI: Out-of-Task Distribution Detection using Causal Active Experimentation for Safe Transfer RL
Venue: arXiv cs.LG 2021
Year: 2021

Out-of-distribution (OOD) detection is a well-studied topic in supervised learning. Extending the successes in supervised learning methods to the reinforcement learning (RL) setting, however, is difficult due to the data generating process - RL agents actively query their environment for data, and the data are a function of the policy followed by the agent. An agent could thus neglect a shift in the environment if its policy did not lead it to explore the aspect of the environment that shifted. Therefore, to achieve safe and robust generalization in RL, there exists an unmet need for OOD detection through active experimentation. Here, we attempt to bridge this lacuna by first defining a causal framework for OOD scenarios or environments encountered by RL agents in the wild. Then, we propose a novel task: that of Out-of-Task Distribution (OOTD) detection. We introduce an RL agent that actively experiments in a test environment and subsequently concludes whether it is OOTD or not. We name our method GalilAI, in honor of Galileo Galilei, as it discovers, among other causal processes, that gravitational acceleration is independent of the mass of a body. Finally, we propose a simple probabilistic neural network baseline for comparison, which extends extant Model-Based RL. We find that GalilAI outperforms the baseline significantly. See visualizations of our method https://galil-ai.github.io/
PEDENet: Image Anomaly Localization via Patch Embedding and Density Estimation
Venue: arXiv cs.CV 2021
Year: 2021

A neural network targeting at unsupervised image anomaly localization, called the PEDENet, is proposed in this work. PEDENet contains a patch embedding (PE) network, a density estimation (DE) network, and an auxiliary network called the location prediction (LP) network. The PE network takes local image patches as input and performs dimension reduction to get low-dimensional patch embeddings via a deep encoder structure. Being inspired by the Gaussian Mixture Model (GMM), the DE network takes those patch embeddings and then predicts the cluster membership of an embedded patch. The sum of membership probabilities is used as a loss term to guide the learning process. The LP network is a Multi-layer Perception (MLP), which takes embeddings from two neighboring patches as input and predicts their relative location. The performance of the proposed PEDENet is evaluated extensively and benchmarked with that of state-of-the-art methods.
Computing Lewis Weights to High Precision
Venue: arXiv cs.DS 2021
Year: 2021

We present an algorithm for computing approximate $\ell_p$ Lewis weights to high precision. Given a full-rank $\mathbf{A} \in \mathbb{R}^{m \times n}$ with $m \geq n$ and a scalar $p>2$, our algorithm computes $ε$-approximate $\ell_p$ Lewis weights of $\mathbf{A}$ in $\widetilde{O}_p(\log(1/ε))$ iterations; the cost of each iteration is linear in the input size plus the cost of computing the leverage scores of $\mathbf{D}\mathbf{A}$ for diagonal $\mathbf{D} \in \mathbb{R}^{m \times m}$. Prior to our work, such a computational complexity was known only for $p \in (0, 4)$ [CohenPeng2015], and combined with this result, our work yields the first polylogarithmic-depth polynomial-work algorithm for the problem of computing $\ell_p$ Lewis weights to high precision for all constant $p > 0$. An important consequence of this result is also the first polylogarithmic-depth polynomial-work algorithm for computing a nearly optimal self-concordant barrier for a polytope.
Novel View Synthesis from a Single Image via Unsupervised learning
Venue: arXiv cs.CV 2021
Year: 2021

View synthesis aims to generate novel views from one or more given source views. Although existing methods have achieved promising performance, they usually require paired views of different poses to learn a pixel transformation. This paper proposes an unsupervised network to learn such a pixel transformation from a single source viewpoint. In particular, the network consists of a token transformation module (TTM) that facilities the transformation of the features extracted from a source viewpoint image into an intrinsic representation with respect to a pre-defined reference pose and a view generation module (VGM) that synthesizes an arbitrary view from the representation. The learned transformation allows us to synthesize a novel view from any single source viewpoint image of unknown pose. Experiments on the widely used view synthesis datasets have demonstrated that the proposed network is able to produce comparable results to the state-of-the-art methods despite the fact that learning is unsupervised and only a single source viewpoint image is required for generating a novel view. The code will be available soon.
Training Integrable Parameterizations of Deep Neural Networks in the Infinite-Width Limit
Venue: arXiv cs.LG 2021
Year: 2021

To theoretically understand the behavior of trained deep neural networks, it is necessary to study the dynamics induced by gradient methods from a random initialization. However, the nonlinear and compositional structure of these models make these dynamics difficult to analyze. To overcome these challenges, large-width asymptotics have recently emerged as a fruitful viewpoint and led to practical insights on real-world deep networks. For two-layer neural networks, it has been understood via these asymptotics that the nature of the trained model radically changes depending on the scale of the initial random weights, ranging from a kernel regime (for large initial variance) to a feature learning regime (for small initial variance). For deeper networks more regimes are possible, and in this paper we study in detail a specific choice of ''small'' initialization corresponding to "mean-field" limits of neural networks, which we call integrable parameterizations (IPs). First, we show that under standard i.i.d. zero-mean initialization, integrable parameterizations of neural networks with more than four layers start at a stationary point in the infinite-width limit and no learning occurs. We then propose various methods to avoid this trivial behavior and analyze in detail the resulting dynamics. In particular, one of these methods consists in using large initial learning rates, and we show that it is equivalent to a modification of the recently proposed maximal update parameterization $μ$P. We confirm our results with numerical experiments on image classification tasks, which additionally show a strong difference in behavior between various choices of activation functions that is not yet captured by theory.
Path-Enhanced Multi-Relational Question Answering with Knowledge Graph Embeddings
Venue: arXiv cs.CL 2021
Year: 2021

The multi-relational Knowledge Base Question Answering (KBQA) system performs multi-hop reasoning over the knowledge graph (KG) to achieve the answer. Recent approaches attempt to introduce the knowledge graph embedding (KGE) technique to handle the KG incompleteness but only consider the triple facts and neglect the significant semantic correlation between paths and multi-relational questions. In this paper, we propose a Path and Knowledge Embedding-Enhanced multi-relational Question Answering model (PKEEQA), which leverages multi-hop paths between entities in the KG to evaluate the ambipolar correlation between a path embedding and a multi-relational question embedding via a customizable path representation mechanism, benefiting for achieving more accurate answers from the perspective of both the triple facts and the extra paths. Experimental results illustrate that PKEEQA improves KBQA models' performance for multi-relational question answering with explainability to some extent derived from paths.
Bayesian Optimal Experimental Design for Simulator Models of Cognition
Venue: arXiv cs.LG 2021
Year: 2021

Bayesian optimal experimental design (BOED) is a methodology to identify experiments that are expected to yield informative data. Recent work in cognitive science considered BOED for computational models of human behavior with tractable and known likelihood functions. However, tractability often comes at the cost of realism; simulator models that can capture the richness of human behavior are often intractable. In this work, we combine recent advances in BOED and approximate inference for intractable models, using machine-learning methods to find optimal experimental designs, approximate sufficient summary statistics and amortized posterior distributions. Our simulation experiments on multi-armed bandit tasks show that our method results in improved model discrimination and parameter estimation, as compared to experimental designs commonly used in the literature.
Scale-Aware Dynamic Network for Continuous-Scale Super-Resolution
Venue: arXiv cs.CV 2021
Year: 2021

Single-image super-resolution (SR) with fixed and discrete scale factors has achieved great progress due to the development of deep learning technology. However, the continuous-scale SR, which aims to use a single model to process arbitrary (integer or non-integer) scale factors, is still a challenging task. The existing SR models generally adopt static convolution to extract features, and thus unable to effectively perceive the change of scale factor, resulting in limited generalization performance on multi-scale SR tasks. Moreover, the existing continuous-scale upsampling modules do not make full use of multi-scale features and face problems such as checkerboard artifacts in the SR results and high computational complexity. To address the above problems, we propose a scale-aware dynamic network (SADN) for continuous-scale SR. First, we propose a scale-aware dynamic convolutional (SAD-Conv) layer for the feature learning of multiple SR tasks with various scales. The SAD-Conv layer can adaptively adjust the attention weights of multiple convolution kernels based on the scale factor, which enhances the expressive power of the model with a negligible extra computational cost. Second, we devise a continuous-scale upsampling module (CSUM) with the multi-bilinear local implicit function (MBLIF) for any-scale upsampling. The CSUM constructs multiple feature spaces with gradually increasing scales to approximate the continuous feature representation of an image, and then the MBLIF makes full use of multi-scale features to map arbitrary coordinates to RGB values in high-resolution space. We evaluate our SADN using various benchmarks. The experimental results show that the CSUM can replace the previous fixed-scale upsampling layers and obtain a continuous-scale SR network while maintaining performance. Our SADN uses much fewer parameters and outperforms the state-of-the-art SR methods.
Multi-target tracking for video surveillance using deep affinity network: a brief review
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning models are known to function like the human brain. Due to their functional mechanism, they are frequently utilized to accomplish tasks that require human intelligence. Multi-target tracking (MTT) for video surveillance is one of the important and challenging tasks, which has attracted the researcher's attention due to its potential applications in various domains. Multi-target tracking tasks require locating the objects individually in each frame, which remains a huge challenge as there are immediate changes in appearances and extreme occlusions of objects. In addition to that, the Multitarget tracking framework requires multiple tasks to perform i.e. target detection, estimating trajectory, associations between frame, and re-identification. Various methods have been suggested, and some assumptions are made to constrain the problem in the context of a particular problem. In this paper, the state-of-the-art MTT models, which leverage from deep learning representational power are reviewed.
Shortest Beer Path Queries in Outerplanar Graphs
Venue: arXiv cs.DS 2021
Year: 2021

A \emph{beer graph} is an undirected graph $G$, in which each edge has a positive weight and some vertices have a beer store. A \emph{beer path} between two vertices $u$ and $v$ in $G$ is any path in $G$ between $u$ and $v$ that visits at least one beer store. We show that any outerplanar beer graph $G$ with $n$ vertices can be preprocessed in $O(n)$ time into a data structure of size $O(n)$, such that for any two query vertices $u$ and $v$, (i) the weight of the shortest beer path between $u$ and $v$ can be reported in $O(α(n))$ time (where $α(n)$ is the inverse Ackermann function), and (ii) the shortest beer path between $u$ and $v$ can be reported in $O(L)$ time, where $L$ is the number of vertices on this path. Both results are optimal, even when $G$ is a beer tree (i.e., a beer graph whose underlying graph is a tree).
Generational Frameshifts in Technology: Computer Science and Neurosurgery, The VR Use Case
Venue: arXiv cs.HC 2021
Year: 2021

We are at a unique moment in history where there is a confluence of technologies which will synergistically come together to transform the practice of neurosurgery. These technological transformations will be all-encompassing, including improved tools and methods for intraoperative performance of neurosurgery, scalable solutions for asynchronous neurosurgical training and simulation, as well as broad aggregation of operative data allowing fundamental changes in quality assessment, billing, outcome measures, and dissemination of surgical best practices. The ability to perform surgery more safely and more efficiently while capturing the operative details and parsing each component of the operation will open an entirely new epoch advancing our field and all surgical specialties. The digitization of all components within the operating room will allow us to leverage the various fields within computer and computational science to obtain new insights that will improve care and delivery of the highest quality neurosurgery regardless of location. The democratization of neurosurgery is at hand and will be driven by our development, extraction, and adoption of these tools of the modern world. Virtual reality provides a good example of how consumer-facing technologies are finding a clear role in industry and medicine and serves as a notable example of the confluence of various computer science technologies creating a novel paradigm for scaling human ability and interactions. The authors describe the technology ecosystem that has come and highlight a myriad of computational and data sciences that will be necessary to enable the operating room of the near future.
Media Modulation in Molecular Communications
Venue: arXiv cs.ET 2021
Year: 2021

In conventional molecular communication (MC) systems, the signaling molecules used for information transmission are stored, released, and then replenished by a transmitter (TX). However, the replenishment of signaling molecules at the TX is challenging in practice. Furthermore, in most envisioned MC applications, e.g., in the medical field, it is not desirable to insert the TX into the MC system, as this might impair natural biological processes. In this paper, we propose the concept of media modulation based MC where the TX is placed outside the channel and utilizes signaling molecules already existing inside the system. We consider signaling molecules that can be in different states which can be switched by external stimuli. Hence, in media modulation based MC, for information transmission, the TX stimulates the signaling molecules to encode information into their state. In particular, we elaborate media modulation for the group of photochromic molecules, which undergo light-induced reversible transformations, and study the usage of these molecules for information transmission in a three-dimensional duct system. We develop a statistical model for the received signal which depends on the distribution of the signaling molecules in the system, the reliability of the state control mechanism, and the randomness of molecule propagation. Furthermore, we analyze the performance of media modulation based MC in terms of the bit error rate (BER). We show that media modulation enables reliable information transmission, which renders a TX inside the channel unnecessary.
Comparing Machine Learning-Centered Approaches for Forecasting Language Patterns During Frustration in Early Childhood
Venue: arXiv cs.CL 2021
Year: 2021

When faced with self-regulation challenges, children have been known the use their language to inhibit their emotions and behaviors. Yet, to date, there has been a critical lack of evidence regarding what patterns in their speech children use during these moments of frustration. In this paper, eXtreme Gradient Boosting, Random Forest, Long Short-Term Memory Recurrent Neural Networks, and Elastic Net Regression, have all been used to forecast these language patterns in children. Based on the results of a comparative analysis between these methods, the study reveals that when dealing with high-dimensional and dense data, with very irregular and abnormal distributions, as is the case with self-regulation patterns in children, decision tree-based algorithms are able to outperform traditional regression and neural network methods in their shortcomings.
Learning to Communicate with Reinforcement Learning for an Adaptive Traffic Control System
Venue: arXiv cs.LG 2021
Year: 2021

Recent work in multi-agent reinforcement learning has investigated inter agent communication which is learned simultaneously with the action policy in order to improve the team reward. In this paper, we investigate independent Q-learning (IQL) without communication and differentiable inter-agent learning (DIAL) with learned communication on an adaptive traffic control system (ATCS). In real world ATCS, it is impossible to present the full state of the environment to every agent so in our simulation, the individual agents will only have a limited observation of the full state of the environment. The ATCS will be simulated using the Simulation of Urban MObility (SUMO) traffic simulator in which two connected intersections are simulated. Every intersection is controlled by an agent which has the ability to change the direction of the traffic flow. Our results show that a DIAL agent outperforms an independent Q-learner on both training time and on maximum achieved reward as it is able to share relevant information with the other agents.