OpenRaiser/Intern-Atlas huggingface dataset:
Active Learning of Probabilistic Movement Primitives
Venue: arXiv cs.RO 2022
Year: 2022

A Probabilistic Movement Primitive (ProMP) defines a distribution over trajectories with an associated feedback policy. ProMPs are typically initialized from human demonstrations and achieve task generalization through probabilistic operations. However, there is currently no principled guidance in the literature to determine how many demonstrations a teacher should provide and what constitutes a "good" demonstration for promoting generalization. In this paper, we present an active learning approach to learning a library of ProMPs capable of task generalization over a given space. We utilize uncertainty sampling techniques to generate a task instance for which a teacher should provide a demonstration. The provided demonstration is incorporated into an existing ProMP if possible, or a new ProMP is created from the demonstration if it is determined that it is too dissimilar from existing demonstrations. We provide a qualitative comparison between common active learning metrics; motivated by this comparison we present a novel uncertainty sampling approach named Greatest Mahalanobis Distance. We perform grasping experiments on a real KUKA robot and show our novel active learning measure achieves better task generalization with fewer demonstrations than a random sampling over the space.
Efficient Isomorphism for $S_d$-graphs and $T$-graphs
Venue: arXiv cs.DS 2022
Year: 2022

An $H$-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph $H$, introduced by Biró, Hujter and Tuza (1992). An $H$-graph is proper if the representing subgraphs of $H$ can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for $S_d$-graphs and $T$-graphs, where $S_d$ is the star with $d$ rays and $T$ is an arbitrary fixed tree. Answering an open problem of Chaplick, Töpfer, Voborn\'ık and Zeman (2016), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of $S_d$-graphs when parameterized by~$d$, which involves the classical group-computing machinery by Furst, Hopcroft, and Luks (1980). We also show that the isomorphism problem of $S_d$-graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of $T$-graphs when parameterized by the size of $T$. Lastly, we contribute a simple FPT-time combinatorial algorithm for isomorphism testing in the special case of proper $S_d$- and $T$-graphs.
Towards Improving Christofides Algorithm on Fundamental Classes by Gluing Convex Combinations of Tours
Venue: arXiv cs.DS 2022
Year: 2022

We present a new approach for gluing tours over certain tight, 3-edge cuts. Gluing over 3-edge cuts has been used in algorithms for finding Hamilton cycles in special graph classes and in proving bounds for 2-edge-connected subgraph problem, but not much was known in this direction for gluing connected multigraphs. We apply this approach to the traveling salesman problem (TSP) in the case when the objective function of the subtour elimination relaxation is minimized by a $θ$-cyclic point: $x_e \in \{0,θ, 1-θ, 1\}$, where the support graph is subcubic and each vertex is incident to at least one edge with $x$-value 1. Such points are sufficient to resolve TSP in general. For these points, we construct a convex combination of tours in which we can reduce the usage of edges with $x$-value 1 from the $\frac{3}{2}$ of Christofides algorithm to $\frac{3}{2}-\fracθ{10}$ while keeping the usage of edges with fractional $x$-value the same as Christofides algorithm. A direct consequence of this result is for the Uniform Cover Problem for TSP: In the case when the objective function of the subtour elimination relaxation is minimized by a $\frac{2}{3}$-uniform point: $x_e \in \{0, \frac{2}{3}\}$, we give a $\frac{17}{12}$-approximation algorithm for TSP. For such points, this lands us halfway between the approximation ratios of $\frac{3}{2}$ of Christofides algorithm and $\frac{4}{3}$ implied by the famous "four-thirds conjecture".
Coresets for Clustering in Graphs of Bounded Treewidth
Venue: arXiv cs.DS 2022
Year: 2022

We initiate the study of coresets for clustering in graph metrics, i.e., the shortest-path metric of edge-weighted graphs. Such clustering problems are essential to data analysis and used for example in road networks and data visualization. A coreset is a compact summary of the data that approximately preserves the clustering objective for every possible center set, and it offers significant efficiency improvements in terms of running time, storage, and communication, including in streaming and distributed settings. Our main result is a near-linear time construction of a coreset for k-Median in a general graph $G$, with size $O_{ε, k}(\mathrm{tw}(G))$ where $\mathrm{tw}(G)$ is the treewidth of $G$, and we complement the construction with a nearly-tight size lower bound. The construction is based on the framework of Feldman and Langberg [STOC 2011], and our main technical contribution, as required by this framework, is a uniform bound of $O(\mathrm{tw}(G))$ on the shattering dimension under any point weights. We validate our coreset on real-world road networks, and our scalable algorithm constructs tiny coresets with high accuracy, which translates to a massive speedup of existing approximation algorithms such as local search for graph k-Median.
A Foundation for Proving Splay is Dynamically Optimal
Venue: arXiv cs.DS 2022
Year: 2022

Consider the task of performing a sequence of searches in a binary search tree. After each search, we allow an algorithm to arbitrarily restructure the tree. The cost of executing the task is the sum of the time spent searching and the time spent optimizing the searches with restructuring operations. Sleator and Tarjan introduced this notion in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments that move searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. We lay a foundation for proving the dynamic optimality conjecture. Central to our method is approximate monotonicity. Approximately monotone algorithms are those whose cost does not increase by more than a fixed multiple after removing searches from the sequence. As we shall see, Splay is dynamically optimal if and only if it is approximately monotone. This result extends to a weaker form of approximate monotonicity as well as insertion, deletion, and related algorithms. We prove that a lower bound on optimal execution cost is approximately monotone and outline how to adapt this proof from the lower bound to Splay, and how to overcome the remaining barriers to establishing dynamic optimality.
Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
Venue: arXiv cs.DS 2022
Year: 2022

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry D are solvable in time g(d,D)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,D)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.
Characterizing Attacks on Deep Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Recent studies show that Deep Reinforcement Learning (DRL) models are vulnerable to adversarial attacks, which attack DRL models by adding small perturbations to the observations. However, some attacks assume full availability of the victim model, and some require a huge amount of computation, making them less feasible for real world applications. In this work, we make further explorations of the vulnerabilities of DRL by studying other aspects of attacks on DRL using realistic and efficient attacks. First, we adapt and propose efficient black-box attacks when we do not have access to DRL model parameters. Second, to address the high computational demands of existing attacks, we introduce efficient online sequential attacks that exploit temporal consistency across consecutive steps. Third, we explore the possibility of an attacker perturbing other aspects in the DRL setting, such as the environment dynamics. Finally, to account for imperfections in how an attacker would inject perturbations in the physical world, we devise a method for generating a robust physical perturbations to be printed. The attack is evaluated on a real-world robot under various conditions. We conduct extensive experiments both in simulation such as Atari games, robotics and autonomous driving, and on real-world robotics, to compare the effectiveness of the proposed attacks with baseline approaches. To the best of our knowledge, we are the first to apply adversarial attacks on DRL systems to physical robots.
Visual Entropy and the Visualization of Uncertainty
Venue: arXiv cs.GR 2022
Year: 2022

Background: Even though data visualizations (and underlying data) almost always contain uncertainty, it remains complex to communicate and interpret uncertainty representations. Consequently, uncertainty visualizations for non-expert audiences are rare. Objective: our aim is to rigorously define and evaluate the novel use of visual entropy as a measure of shape that allows us to construct an ordered scale of glyphs for use in representing both uncertainty and value in 2D and 3D environments. Method: We use sample entropy as a numerical measure of visual entropy to construct a set of glyphs using R and Blender which vary in their complexity. Results: an exact binomial analysis of a pairwise comparison of the glyphs shows a majority of participants (n = 87) ordered each glyph as predicted by the visual entropy score with large effect size (Cohen's g > 0.25). We also evaluate whether the glyphs effectively represent uncertainty using a signal detection method in a search task. Participants (n = 15) were able to find glyphs representing uncertainty with high sensitivity and low error rates. Conclusion: visual entropy is a successful novel approach to representing ordered data and provides a channel that can allow the uncertainty of a measure to be presented alongside its mean value.
On the Robustness of Median Sampling in Noisy Evolutionary Optimization
Venue: arXiv cs.NE 2022
Year: 2022

Evolutionary algorithms (EAs) are a sort of nature-inspired metaheuristics, which have wide applications in various practical optimization problems. In these problems, objective evaluations are usually inaccurate, because noise is almost inevitable in real world, and it is a crucial issue to weaken the negative effect caused by noise. Sampling is a popular strategy, which evaluates the objective a couple of times, and employs the mean of these evaluation results as an estimate of the objective value. In this work, we introduce a novel sampling method, median sampling, into EAs, and illustrate its properties and usefulness theoretically by solving OneMax, the problem of maximizing the number of 1s in a bit string. Instead of the mean, median sampling employs the median of the evaluation results as an estimate. Through rigorous theoretical analysis on OneMax under the commonly used onebit noise, we show that median sampling reduces the expected runtime exponentially. Next, through two special noise models, we show that when the 2-quantile of the noisy fitness increases with the true fitness, median sampling can be better than mean sampling; otherwise, it may fail and mean sampling can be better. The results may guide us to employ median sampling properly in practical applications.
Theme-Aware Aesthetic Distribution Prediction With Full-Resolution Photographs
Venue: arXiv cs.CV 2022
Year: 2022

Aesthetic quality assessment (AQA) is a challenging task due to complex aesthetic factors. Currently, it is common to conduct AQA using deep neural networks that require fixed-size inputs. Existing methods mainly transform images by resizing, cropping, and padding or employ adaptive pooling to alternately capture the aesthetic features from fixed-size inputs. However, these transformations potentially damage aesthetic features. To address this issue, we propose a simple but effective method to accomplish full-resolution image AQA by combining image padding with region of image (RoM) pooling. Padding turns inputs into the same size. RoM pooling pools image features and discards extra padded features to eliminate the side effects of padding. In addition, the image aspect ratios are encoded and fused with visual features to remedy the shape information loss of RoM pooling. Furthermore, we observe that the same image may receive different aesthetic evaluations under different themes, which we call theme criterion bias. Hence, a theme-aware model that uses theme information to guide model predictions is proposed. Finally, we design an attention-based feature fusion module to effectively utilize both the shape and theme information. Extensive experiments prove the effectiveness of the proposed method over state-of-the-art methods.
Efficient Fair Division with Minimal Sharing
Venue: arXiv cs.GT 2022
Year: 2022

A collection of objects, some of which are good and some are bad, is to be divided fairly among agents with different tastes, modeled by additive utility functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then a fair division may not exist. What is the smallest number of objects that must be shared between two or more agents in order to attain a fair and efficient division? In this paper, fairness is understood as proportionality or envy-freeness, and efficiency, as fractional Pareto-optimality. We show that, for a generic instance of the problem (all instances except a zero-measure set of degenerate problems), a fair fractionally Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where agents' valuations are aligned for many objects.
Likelihood Contribution based Multi-scale Architecture for Generative Flows
Venue: arXiv cs.LG 2022
Year: 2022

Deep generative modeling using flows has gained popularity owing to the tractable exact log-likelihood estimation with efficient training and synthesis process. However, flow models suffer from the challenge of having high dimensional latent space, the same in dimension as the input space. An effective solution to the above challenge as proposed by Dinh et al. (2016) is a multi-scale architecture, which is based on iterative early factorization of a part of the total dimensions at regular intervals. Prior works on generative flow models involving a multi-scale architecture perform the dimension factorization based on static masking. We propose a novel multi-scale architecture that performs data-dependent factorization to decide which dimensions should pass through more flow layers. To facilitate the same, we introduce a heuristic based on the contribution of each dimension to the total log-likelihood which encodes the importance of the dimensions. Our proposed heuristic is readily obtained as part of the flow training process, enabling the versatile implementation of our likelihood contribution based multi-scale architecture for generic flow models. We present such implementations for several state-of-the-art flow models and demonstrate improvements in log-likelihood score and sampling quality on standard image benchmarks. We also conduct ablation studies to compare the proposed method with other options for dimension factorization.
Fully-automated patient-level malaria assessment on field-prepared thin blood film microscopy images, including Supplementary Information
Venue: arXiv cs.LG 2022
Year: 2022

Malaria is a life-threatening disease affecting millions. Microscopy-based assessment of thin blood films is a standard method to (i) determine malaria species and (ii) quantitate high-parasitemia infections. Full automation of malaria microscopy by machine learning (ML) is a challenging task because field-prepared slides vary widely in quality and presentation, and artifacts often heavily outnumber relatively rare parasites. In this work, we describe a complete, fully-automated framework for thin film malaria analysis that applies ML methods, including convolutional neural nets (CNNs), trained on a large and diverse dataset of field-prepared thin blood films. Quantitation and species identification results are close to sufficiently accurate for the concrete needs of drug resistance monitoring and clinical use-cases on field-prepared samples. We focus our methods and our performance metrics on the field use-case requirements. We discuss key issues and important metrics for the application of ML methods to malaria microscopy.
A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
Venue: arXiv cs.DS 2022
Year: 2022

Given an undirected, weighted graph, the minimum spanning tree (MST) is a tree that connects all of the vertices of the graph with minimum sum of edge weights. In real world applications, network designers often seek to quickly find a replacement edge for each edge in the MST. For example, when a traffic accident closes a road in a transportation network, or a line goes down in a communication network, the replacement edge may reconnect the MST at lowest cost. In the paper, we consider the case of finding the lowest cost replacement edge for each edge of the MST. A previous algorithm by Tarjan takes $O(m α(m, n))$ time and space, where $α(m, n)$ is the inverse Ackermann's function. Given the MST and sorted non-tree edges, our algorithm is the first practical algorithm that runs in $O(m+n)$ time and $O(m+n)$ space to find all replacement edges. Additionally, since the most vital edge is the tree edge whose removal causes the highest cost, our algorithm finds it in linear time.
Visualizing Image Content to Explain Novel Image Discovery
Venue: arXiv cs.LG 2022
Year: 2022

The initial analysis of any large data set can be divided into two phases: (1) the identification of common trends or patterns and (2) the identification of anomalies or outliers that deviate from those trends. We focus on the goal of detecting observations with novel content, which can alert us to artifacts in the data set or, potentially, the discovery of previously unknown phenomena. To aid in interpreting and diagnosing the novel aspect of these selected observations, we recommend the use of novelty detection methods that generate explanations. In the context of large image data sets, these explanations should highlight what aspect of a given image is new (color, shape, texture, content) in a human-comprehensible form. We propose DEMUD-VIS, the first method for providing visual explanations of novel image content by employing a convolutional neural network (CNN) to extract image features, a method that uses reconstruction error to detect novel content, and an up-convolutional network to convert CNN feature representations back into image space. We demonstrate this approach on diverse images from ImageNet, freshwater streams, and the surface of Mars.
Freezing, Bounded-Change and Convergent Cellular Automata
Venue: arXiv cs.DM 2022
Year: 2022

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-Kůrka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from convergent cellular automata in dimension~1, but also dimension~1 versus higher dimensions for freezing cellular automata. Another surprising dimension-sensitive result obtained is that nilpotency becomes decidable in dimension~ 1 for all the three classes, while it stays undecidable even for freezing cellular automata in higher dimension.
Large-scale Environmental Data Science with ExaGeoStatR
Venue: arXiv cs.DC 2022
Year: 2022

Parallel computing in Gaussian process calculations becomes necessary for avoiding computational and memory restrictions associated with large-scale environmental data science applications. The evaluation of the Gaussian log-likelihood function requires O(n^2) storage and O(n^3) operations where n is the number of geographical locations. Thus, computing the log-likelihood function with a large number of locations requires exploiting the power of existing parallel computing hardware systems, such as shared-memory, possibly equipped with GPUs, and distributed-memory systems, to solve this computational complexity. In this paper, we advocate the use of ExaGeoStatR, a package for exascale Geostatistics in R that supports a parallel computation of the exact maximum likelihood function on a wide variety of parallel architectures. Parallelization in ExaGeoStatR depends on breaking down the numerical linear algebra operations in the log-likelihood function into a set of tasks and rendering them for a task-based programming model. The package can be used directly through the R environment on parallel systems. Currently, ExaGeoStatR supports several maximum likelihood computation variants such as exact, Diagonal Super Tile (DST), Tile Low-Rank (TLR) approximations, and Mixed-Precision (MP). ExaGeoStatR also provides a tool to simulate large-scale synthetic datasets. These datasets can help to assess different implementations of the maximum log-likelihood approximation methods. Here, we demonstrate ExaGeoStatR by illustrating its implementation details, analyzing its performance on various parallel architectures, and assessing its accuracy using synthetic datasets with up to 250K observations. We provide a hands-on tutorial to analyze a sea surface temperature real dataset. The performance evaluation involves comparisons with the popular packages geoR and fields for exact likelihood evaluation.