OpenRaiser/Intern-Atlas huggingface dataset:
A Decade Survey of Content Based Image Retrieval using Deep Learning
Venue: arXiv cs.CV 2021
Year: 2021

The content based image retrieval aims to find the similar images from a large scale dataset against a query image. Generally, the similarity between the representative features of the query image and dataset images is used to rank the images for retrieval. In early days, various hand designed feature descriptors have been investigated based on the visual cues such as color, texture, shape, etc. that represent the images. However, the deep learning has emerged as a dominating alternative of hand-designed feature engineering from a decade. It learns the features automatically from the data. This paper presents a comprehensive survey of deep learning based developments in the past decade for content based image retrieval. The categorization of existing state-of-the-art methods from different perspectives is also performed for greater understanding of the progress. The taxonomy used in this survey covers different supervision, different networks, different descriptor type and different retrieval type. A performance analysis is also performed using the state-of-the-art methods. The insights are also presented for the benefit of the researchers to observe the progress and to make the best choices. The survey presented in this paper will help in further research progress in image retrieval using deep learning.
Learning and Using Abstractions for Robot Planning
Venue: arXiv cs.RO 2021
Year: 2021

Robot motion planning involves computing a sequence of valid robot configurations that take the robot from its initial state to a goal state. Solving a motion planning problem optimally using analytical methods is proven to be PSPACE-Hard. Sampling-based approaches have tried to approximate the optimal solution efficiently. Generally, sampling-based planners use uniform samplers to cover the entire state space. In this paper, we propose a deep-learning-based framework that identifies robot configurations in the environment that are important to solve the given motion planning problem. These states are used to bias the sampling distribution in order to reduce the planning time. Our approach works with a unified network and generates domain-dependent network parameters based on the environment and the robot. We evaluate our approach with Learn and Link planner in three different settings. Results show significant improvement in motion planning times when compared with current sampling-based motion planners.
Dynamic Feature Pyramid Networks for Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Feature pyramid network (FPN) is a critical component in modern object detection frameworks. The performance gain in most of the existing FPN variants is mainly attributed to the increase of computational burden. An attempt to enhance the FPN is enriching the spatial information by expanding the receptive fields, which is promising to largely improve the detection accuracy. In this paper, we first investigate how expanding the receptive fields affect the accuracy and computational costs of FPN. We explore a baseline model called inception FPN in which each lateral connection contains convolution filters with different kernel sizes. Moreover, we point out that not all objects need such a complicated calculation and propose a new dynamic FPN (DyFPN). The output features of DyFPN will be calculated by using the adaptively selected branch according to a dynamic gating operation. Therefore, the proposed method can provide a more efficient dynamic inference for achieving a better trade-off between accuracy and computational cost. Extensive experiments conducted on MS-COCO benchmark demonstrate that the proposed DyFPN significantly improves performance with the optimal allocation of computation resources. For instance, replacing inception FPN with DyFPN reduces about 40% of its FLOPs while maintaining similar high performance.
Local Routing in a Tree Metric 1-Spanner
Venue: arXiv cs.CG 2021
Year: 2021

Solomon and Elkin constructed a shortcutting scheme for weighted trees which results in a 1-spanner for the tree metric induced by the input tree. The spanner has logarithmic lightness, logarithmic diameter, a linear number of edges and bounded degree (provided the input tree has bounded degree). This spanner has been applied in a series of papers devoted to designing bounded degree, low-diameter, low-weight $(1+ε)$-spanners in Euclidean and doubling metrics. In this paper, we present a simple local routing algorithm for this tree metric spanner. The algorithm has a routing ratio of 1, is guaranteed to terminate after $O(\log n)$ hops and requires $O(Δ\log n)$ bits of storage per vertex where $Δ$ is the maximum degree of the tree on which the spanner is constructed. This local routing algorithm can be adapted to a local routing algorithm for a doubling metric spanner which makes use of the shortcutting scheme.
Intelligence and Learning in O-RAN for Data-driven NextG Cellular Networks
Venue: arXiv cs.NI 2021
Year: 2021

Next Generation (NextG) cellular networks will be natively cloud-based and built upon programmable, virtualized, and disaggregated architectures. The separation of control functions from the hardware fabric and the introduction of standardized control interfaces will enable the definition of custom closed-control loops, which will ultimately enable embedded intelligence and real-time analytics, thus effectively realizing the vision of autonomous and self-optimizing networks. This article explores the disaggregated network architecture proposed by the O-RAN Alliance as a key enabler of NextG networks. Within this architectural context, we discuss the potential, the challenges, and the limitations of data-driven optimization approaches to network control over different timescales. We also present the first large-scale integration of O-RAN-compliant software components with an open-source full-stack softwarized cellular network. Experiments conducted on Colosseum, the world's largest wireless network emulator, demonstrate closed-loop integration of real-time analytics and control through deep reinforcement learning agents. We also show the feasibility of Radio Access Network (RAN) control through xApps running on the near real-time RAN Intelligent Controller, to optimize the scheduling policies of co-existing network slices, leveraging the O-RAN open interfaces to collect data at the edge of the network.
Eudoxus: Characterizing and Accelerating Localization in Autonomous Machines
Venue: arXiv cs.AR 2021
Year: 2021

We develop and commercialize autonomous machines, such as logistic robots and self-driving cars, around the globe. A critical challenge to our -- and any -- autonomous machine is accurate and efficient localization under resource constraints, which has fueled specialized localization accelerators recently. Prior acceleration efforts are point solutions in that they each specialize for a specific localization algorithm. In real-world commercial deployments, however, autonomous machines routinely operate under different environments and no single localization algorithm fits all the environments. Simply stacking together point solutions not only leads to cost and power budget overrun, but also results in an overly complicated software stack. This paper demonstrates our new software-hardware co-designed framework for autonomous machine localization, which adapts to different operating scenarios by fusing fundamental algorithmic primitives. Through characterizing the software framework, we identify ideal acceleration candidates that contribute significantly to the end-to-end latency and/or latency variation. We show how to co-design a hardware accelerator to systematically exploit the parallelisms, locality, and common building blocks inherent in the localization framework. We build, deploy, and evaluate an FPGA prototype on our next-generation self-driving cars. To demonstrate the flexibility of our framework, we also instantiate another FPGA prototype targeting drones, which represent mobile autonomous machines. We achieve about 2x speedup and 4x energy reduction compared to widely-deployed, optimized implementations on general-purpose platforms.
Prototype-based Incremental Few-Shot Semantic Segmentation
Venue: arXiv cs.CV 2021
Year: 2021

Semantic segmentation models have two fundamental weaknesses: i) they require large training sets with costly pixel-level annotations, and ii) they have a static output space, constrained to the classes of the training set. Toward addressing both problems, we introduce a new task, Incremental Few-Shot Segmentation (iFSS). The goal of iFSS is to extend a pretrained segmentation model with new classes from few annotated images and without access to old training data. To overcome the limitations of existing models iniFSS, we propose Prototype-based Incremental Few-Shot Segmentation (PIFS) that couples prototype learning and knowledge distillation. PIFS exploits prototypes to initialize the classifiers of new classes, fine-tuning the network to refine its features representation. We design a prototype-based distillation loss on the scores of both old and new class prototypes to avoid overfitting and forgetting, and batch-renormalization to cope with non-i.i.d.few-shot data. We create an extensive benchmark for iFSS showing that PIFS outperforms several few-shot and incremental learning methods in all scenarios.
Cycloidal Trajectory Realization on Staircase based on Neural Network Temporal Quantized Lagrange Dynamics (NNTQLD) with Ant Colony Optimization for a 9-Link Bipedal Robot
Venue: arXiv cs.RO 2021
Year: 2021

In this paper, a novel optimal technique for joint angles trajectory tracking control with energy optimization for a biped robot with toe foot is proposed. For the task of climbing stairs by a 9-link biped model, a cycloid trajectory for swing phase is proposed in such a way that the cycloid variables depend on the staircase dimensions. Zero Moment Point(ZMP) criteria is taken for satisfying stability constraint. This paper mainly can be divided into 3 steps: 1) Planning stable cycloid trajectory for initial step and subsequent step for climbing upstairs and Inverse Kinematics using an unsupervised artificial neural network with knot shifting procedure for jerk minimization. 2) Modeling Dynamics for Toe foot biped model using Lagrange Dynamics along with contact modeling using spring-damper system followed by developing Neural Network Temporal Quantized Lagrange Dynamics which takes inverse kinematics output from neural network as its inputs. 3) Using Ant Colony Optimization to tune PD (Proportional Derivative) controller parameters and torso angle with the objective to minimize joint space trajectory errors and total energy consumed. Three cases with variable staircase dimensions have been taken and a brief comparison is done to verify the effectiveness of our proposed work Generated patterns have been simulated in MATLAB .
Saying No is An Art: Contextualized Fallback Responses for Unanswerable Dialogue Queries
Venue: arXiv cs.CL 2021
Year: 2021

Despite end-to-end neural systems making significant progress in the last decade for task-oriented as well as chit-chat based dialogue systems, most dialogue systems rely on hybrid approaches which use a combination of rule-based, retrieval and generative approaches for generating a set of ranked responses. Such dialogue systems need to rely on a fallback mechanism to respond to out-of-domain or novel user queries which are not answerable within the scope of the dialog system. While, dialog systems today rely on static and unnatural responses like "I don't know the answer to that question" or "I'm not sure about that", we design a neural approach which generates responses which are contextually aware with the user query as well as say no to the user. Such customized responses provide paraphrasing ability and contextualization as well as improve the interaction with the user and reduce dialogue monotonicity. Our simple approach makes use of rules over dependency parses and a text-to-text transformer fine-tuned on synthetic data of question-response pairs generating highly relevant, grammatical as well as diverse questions. We perform automatic and manual evaluations to demonstrate the efficacy of the system.
Robustly Learning Mixtures of $k$ Arbitrary Gaussians
Venue: arXiv cs.DS 2021
Year: 2021

We give a polynomial-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $\mathbb{R}^d$, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. This resolves the main open problem in several previous works on algorithmic robust statistics, which addressed the special cases of robustly estimating (a) a single Gaussian, (b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of two Gaussians. Our main tools are an efficient \emph{partial clustering} algorithm that relies on the sum-of-squares method, and a novel \emph{tensor decomposition} algorithm that allows errors in both Frobenius norm and low-rank terms.
Steady-State Planning in Expected Reward Multichain MDPs
Venue: arXiv cs.AI 2021
Year: 2021

The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some well-defined logic. While many such logics have been proposed with varying degrees of expressiveness and complexity in their capacity to capture desirable agent behavior, their value is limited when deriving decision-making policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steady-state behavior of an agent, which captures the proportion of time an agent spends in each state as it interacts for an indefinite period of time with its environment. This is sometimes called the average or expected behavior of the agent and the associated planning problem is faced with significant challenges unless strong restrictions are imposed on the underlying model in terms of the connectivity of its graph structure. In this paper, we explore this steady-state planning problem that consists of deriving a decision-making policy for an agent such that constraints on its steady-state behavior are satisfied. A linear programming solution for the general case of multichain Markov Decision Processes (MDPs) is proposed and we prove that optimal solutions to the proposed programs yield stationary policies with rigorous guarantees of behavior.
Saturated $k$-Plane Drawings with Few Edges
Venue: arXiv cs.CG 2021
Year: 2021

A drawing of a graph is $k$-plane if no edge is crossed more than $k$ times. In this paper we study saturated $k$-plane drawings with few edges. This are $k$-plane drawings in which no edge can be added without violating $k$-planarity. For every number of vertices $n>k+1$, we present a tight construction with $\frac{n-1}{k+1}$ edges for the case in which the edges can self-intersect. If we restrict the drawings to be $\ell$-simple we show that the number of edges in saturated $k$-plane drawings must be higher. We present constructions with few edges for different values of $k$ and $\ell$. Finally, we investigate saturated straight-line $k$-plane drawings.
Concept-based model explanations for Electronic Health Records
Venue: arXiv cs.LG 2021
Year: 2021

Recurrent Neural Networks (RNNs) are often used for sequential modeling of adverse outcomes in electronic health records (EHRs) due to their ability to encode past clinical states. These deep, recurrent architectures have displayed increased performance compared to other modeling approaches in a number of tasks, fueling the interest in deploying deep models in clinical settings. One of the key elements in ensuring safe model deployment and building user trust is model explainability. Testing with Concept Activation Vectors (TCAV) has recently been introduced as a way of providing human-understandable explanations by comparing high-level concepts to the network's gradients. While the technique has shown promising results in real-world imaging applications, it has not been applied to structured temporal inputs. To enable an application of TCAV to sequential predictions in the EHR, we propose an extension of the method to time series data. We evaluate the proposed approach on an open EHR benchmark from the intensive care unit, as well as synthetic data where we are able to better isolate individual effects.
Tight Chang's-lemma-type bounds for Boolean functions
Venue: arXiv cs.CC 2021
Year: 2021

Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each positive threshold $t$, Chang's lemma provides a lower bound on $wt(f):=\Pr[f(x)=-1]$ in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least $1/t$. We examine the tightness of Chang's lemma w.r.t. the following three natural settings of the threshold: - the Fourier sparsity of $f$, denoted $k(f)$, - the Fourier max-supp-entropy of $f$, denoted $k'(f)$, defined to be $\max \{1/|\hat{f}(S)| : \hat{f}(S) \neq 0\}$, - the Fourier max-rank-entropy of $f$, denoted $k''(f)$, defined to be the minimum $t$ such that characters whose Fourier coefficients are at least $1/t$ in absolute value span a space of dimension $r(f)$. We prove new lower bounds on $wt(f)$ in terms of these measures. One of our lower bounds subsumes and refines the previously best known upper bound on $r(f)$ in terms of $k(f)$ by Sanyal (ToC, 2019). Another lower bound is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of the absolute values of the level-$1$ Fourier coefficients. We also show that Chang's lemma for the these choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions (which are modifications of the Addressing function) witnessing their tightness. Finally we construct Boolean functions $f$ for which - our lower bounds asymptotically match $wt(f)$, and - for any choice of the threshold $t$, the lower bound obtained from Chang's lemma is asymptotically smaller than $wt(f)$.
Near-Optimal Algorithms for Point-Line Covering Problems
Venue: arXiv cs.CG 2021
Year: 2021

We study fundamental point-line covering problems in computational geometry, in which the input is a set $S$ of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least $λ$ points from $S$, for a given integer parameter $λ\geq 2$; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which -- the latter -- asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of $k$ lines that cover the points of $S$, for a given parameter $k \in \mathbb{N}$. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.'s algorithm [Computational Geometry 1996], for a wide range of the parameter $λ$. We derive lower-bound results showing that, for $λ=Ω(\sqrt{n \log n})$, the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model. For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.
Deep Learning for Medical Anomaly Detection -- A Survey
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning-based medical anomaly detection is an important problem that has been extensively studied. Numerous approaches have been proposed across various medical application domains and we observe several similarities across these distinct applications. Despite this comparability, we observe a lack of structured organisation of these diverse research applications such that their advantages and limitations can be studied. The principal aim of this survey is to provide a thorough theoretical analysis of popular deep learning techniques in medical anomaly detection. In particular, we contribute a coherent and systematic review of state-of-the-art techniques, comparing and contrasting their architectural differences as well as training algorithms. Furthermore, we provide a comprehensive overview of deep model interpretation strategies that can be used to interpret model decisions. In addition, we outline the key limitations of existing deep medical anomaly detection techniques and propose key research directions for further investigation.
Spread Mechanism and Influence Measurement of Online Rumors in China During the COVID-19 Pandemic
Venue: arXiv cs.SI 2021
Year: 2021

In early 2020, the Corona Virus Disease 2019 (COVID-19) pandemic swept the world.In China, COVID-19 has caused severe consequences. Moreover, online rumors during the COVID-19 pandemic increased people's panic about public health and social stability. At present, understanding and curbing the spread of online rumors is an urgent task. Therefore, we analyzed the rumor spreading mechanism and propose a method to quantify a rumors' influence by the speed of new insiders. The search frequency of the rumor is used as an observation variable of new insiders. The peak coefficient and the attenuation coefficient are calculated for the search frequency, which conforms to the exponential distribution. We designed several rumor features and used the above two coefficients as predictable labels. A 5-fold cross-validation experiment using the mean square error (MSE) as the loss function showed that the decision tree was suitable for predicting the peak coefficient, and the linear regression model was ideal for predicting the attenuation coefficient. Our feature analysis showed that precursor features were the most important for the outbreak coefficient, while location information and rumor entity information were the most important for the attenuation coefficient. Meanwhile, features that were conducive to the outbreak were usually harmful to the continued spread of rumors. At the same time, anxiety was a crucial rumor causing factor. Finally, we discuss how to use deep learning technology to reduce the forecast loss by using the Bidirectional Encoder Representations from Transformers (BERT) model.