OpenRaiser/Intern-Atlas huggingface dataset:
Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding
Venue: arXiv cs.MA 2022
Year: 2022

In the Multi-Agent Path Finding (MAPF) problem, a set of agents moving on a graph must reach their own respective destinations without inter-agent collisions. In practical MAPF applications such as navigation in automated warehouses, where occasionally there are hundreds or more agents, MAPF must be solved iteratively online on a lifelong basis. Such scenarios rule out simple adaptations of offline compute-intensive optimal approaches; and scalable sub-optimal algorithms are hence appealing for such settings. Ideal algorithms are scalable, applicable to iterative scenarios, and output plausible solutions in predictable computation time. For the aforementioned purpose, this study presents Priority Inheritance with Backtracking (PIBT), a novel sub-optimal algorithm to solve MAPF iteratively. PIBT relies on an adaptive prioritization scheme to focus on the adjacent movements of multiple agents; hence it can be applied to several domains. We prove that, regardless of their number, all agents are guaranteed to reach their destination within finite time when the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle (e.g., biconnected). Experimental results covering various scenarios, including a demonstration with real robots, reveal the benefits of the proposed method. Even with hundreds of agents, PIBT yields acceptable solutions almost immediately and can solve large instances that other established MAPF methods cannot. In addition, PIBT outperforms an existing approach on an iterative scenario of conveying packages in an automated warehouse in both runtime and solution quality.
The number of languages with maximum state complexity
Venue: arXiv cs.FL 2022
Year: 2022

Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to determine the number of maximum-complexity languages. Here we give a formula for this number. We also generalize their work from languages to functions on finite sets.
Star-Transformer
Venue: arXiv cs.CL 2022
Year: 2022

Although Transformer has achieved great successes on many NLP tasks, its heavy structure with fully-connected attention connections leads to dependencies on large training data. In this paper, we present Star-Transformer, a lightweight alternative by careful sparsification. To reduce model complexity, we replace the fully-connected structure with a star-shaped topology, in which every two non-adjacent nodes are connected through a shared relay node. Thus, complexity is reduced from quadratic to linear, while preserving capacity to capture both local composition and long-range dependency. The experiments on four tasks (22 datasets) show that Star-Transformer achieved significant improvements against the standard Transformer for the modestly sized datasets.
Unsupervised Part Mining for Fine-grained Image Classification
Venue: arXiv cs.CV 2022
Year: 2022

Fine-grained image classification remains challenging due to the large intra-class variance and small inter-class variance. Since the subtle visual differences are only in local regions of discriminative parts among subcategories, part localization is a key issue for fine-grained image classification. Most existing approaches localize object or parts in an image with object or part annotations, which are expensive and labor-consuming. To tackle this issue, we propose a fully unsupervised part mining (UPM) approach to localize the discriminative parts without even image-level annotations, which largely improves the fine-grained classification performance. We first utilize pattern mining techniques to discover frequent patterns, i.e., co-occurrence highlighted regions, in the feature maps extracted from a pre-trained convolutional neural network (CNN) model. Inspired by the fact that these relevant meaningful patterns typically hold appearance and spatial consistency, we then cluster the mined regions to obtain the cluster centers and the discriminative parts surrounding the cluster centers are generated. Importantly, any annotations and sophisticated training procedures are not used in our proposed part localization approach. Finally, a multi-stream classification network is built for aggregating the original, object-level and part-level features simultaneously. Compared with other state-of-the-art approaches, our UPM approach achieves the competitive performance.
Inference of Human's Observation Strategy for Monitoring Robot's Behavior based on a Game-Theoretic Model of Trust
Venue: arXiv cs.AI 2022
Year: 2022

We consider scenarios where a worker robot, who may be unaware of the human's exact expectations, may have the incentive to deviate from a preferred plan (e.g. safe but costly) when a human supervisor is not monitoring it. On the other hand, continuous monitoring of the robot's behavior is often difficult for humans because it costs them valuable resources (e.g., time, cognitive overload, etc.). Thus, to optimize the cost of monitoring while ensuring the robots follow the {\em safe} behavior and to assist the human to deal with the possible unsafe robots, we model this problem in a game-theoretic framework of trust. In settings where the human does not initially trust the robot, pure-strategy Nash Equilibrium provides a useful policy for the human. Unfortunately, we show the formulated game often lacks a pure strategy Nash equilibrium. Thus, we define the concept of a trust boundary over the mixed strategy space of the human and show that it helps to discover optimal monitoring strategies. We conduct humans subject studies that demonstrate (1) the need for coming up with optimal monitoring strategies, and (2) the benefits of using strategies suggested by our approach.
Synthesizing Invariant Clusters for Polynomial Programs by Semidefinite Programming
Venue: arXiv cs.SY 2022
Year: 2022

In this paper, we present a novel approach to synthesize invariant clusters for polynomial programs. An invariant cluster is a set of program invariants that share a common structure, which could, for example, be used to save the needs for repeatedly synthesizing new invariants when the specifications and programs are evolving. To that end, we search for sets of parameters $R_k$ w.r.t. a parameterized multivariate polynomial $I(a, x)$ (i.e. a template) such that $I(a, x) \leq 0$ is a valid program invariant for all $a \in R_k$. Instead of using time-consuming symbolic routines such as quantifier eliminations, we show that such sets of parameters can be synthesized using a hierarchy of semidefinite programming (SDP). Moreover, we show that, under some standard non-degenerate assumptions, almost all possible valid parameters can be included in the synthesized sets. Such kind of completeness result has previously only been provided by symbolic approaches. Further extensions such as using semialgebraic and general algebraic templates (instead of polynomial ones) and allowing non-polynomial continuous functions in programs are also discussed.
Wiretap Secret Key Capacity of Tree-PIN
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problem of multiterminal secret key agreement (SKA) in wiretapped source model where terminals have access to samples of correlated random variables from a publicly known joint probability distribution. The adversary has access to a side information variable, that is correlated with terminals' variables. We focus on a special type of terminal variables in this model, known as Tree-PIN, where the relation between variables of the terminals can be represented by a tree. The study of Tree-PIN source model is of practical importance as it can be realized in wireless network environments. We derive the wiretap secret key capacity of Tree-PIN with independent leakage, and give lower and upper bounds on the maximum achievable secret key length in finite-length regime. We then prove an upper bound and a lower bound for the wiretap secret key capacity of a wiretapped PIN and give two conditions for which these bounds are tight. We also extend our main result to two other related models and prove their corresponding capacities. At the end, we argue how our analysis suggests that public interaction is required for achieving the multiterminal WSK capacity.
Epistemological and Bibliometric Analysis of Ethics and Shared Responsibility Health Policy and IoT Systems
Venue: arXiv cs.OH 2022
Year: 2022

The focus in this paper is placed on shared responsibility and ethics in health policy, specific to Internet of Things (IoT) devices in healthcare systems. The article assesses how the introduction of IoT brings risks to the security of medical systems. The justification for this research emerges from the opportunities emerging from digital technologies for medical services, but also creating a range of new cyber risks in the shared healthcare infrastructure. Such concerns are often not visible to individual departments in an integrated healthcare system. In addition, many healthcare organisations do not possess cyber skills and are faced with barriers to the adoption of smart manufacturing technologies, e.g., cost. These barriers trigger ethical concerns related to responsibility of cyber risks in shared healthcare systems.
ImageGCN: Multi-Relational Image Graph Convolutional Networks for Disease Identification with Chest X-rays
Venue: arXiv cs.CV 2022
Year: 2022

Image representation is a fundamental task in computer vision. However, most of the existing approaches for image representation ignore the relations between images and consider each input image independently. Intuitively, relations between images can help to understand the images and maintain model consistency over related images, leading to better explainability. In this paper, we consider modeling the image-level relations to generate more informative image representations, and propose ImageGCN, an end-to-end graph convolutional network framework for inductive multi-relational image modeling. We apply ImageGCN to chest X-ray images where rich relational information is available for disease identification. Unlike previous image representation models, ImageGCN learns the representation of an image using both its original pixel features and its relationship with other images. Besides learning informative representations for images, ImageGCN can also be used for object detection in a weakly supervised manner. The experimental results on 3 open-source x-ray datasets, ChestX-ray14, CheXpert and MIMIC-CXR demonstrate that ImageGCN can outperform respective baselines in both disease identification and localization tasks and can achieve comparable and often better results than the state-of-the-art methods.
On the Equivalence of Automatic and Symbolic Differentiation
Venue: arXiv cs.SC 2022
Year: 2022

We show that reverse mode automatic differentiation and symbolic differentiation are equivalent in the sense that they both perform the same operations when computing derivatives. This is in stark contrast to the common claim that they are substantially different. The difference is often illustrated by claiming that symbolic differentiation suffers from "expression swell" whereas automatic differentiation does not. Here, we show that this statement is not true. "Expression swell" refers to the phenomenon of a much larger representation of the derivative as opposed to the representation of the original function.
Unsupervised Deep Epipolar Flow for Stationary or Dynamic Scenes
Venue: arXiv cs.CV 2022
Year: 2022

Unsupervised deep learning for optical flow computation has achieved promising results. Most existing deep-net based methods rely on image brightness consistency and local smoothness constraint to train the networks. Their performance degrades at regions where repetitive textures or occlusions occur. In this paper, we propose Deep Epipolar Flow, an unsupervised optical flow method which incorporates global geometric constraints into network learning. In particular, we investigate multiple ways of enforcing the epipolar constraint in flow estimation. To alleviate a "chicken-and-egg" type of problem encountered in dynamic scenes where multiple motions may be present, we propose a low-rank constraint as well as a union-of-subspaces constraint for training. Experimental results on various benchmarking datasets show that our method achieves competitive performance compared with supervised methods and outperforms state-of-the-art unsupervised deep-learning methods.
Almost-Smooth Histograms and Sliding-Window Graph Algorithms
Venue: arXiv cs.DS 2022
Year: 2022

We study algorithms for the sliding-window model, an important variant of the data-stream model, in which the goal is to compute some function of a fixed-length suffix of the stream. We extend the smooth-histogram framework of Braverman and Ostrovsky (FOCS 2007) to almost-smooth functions, which includes all subadditive functions. Specifically, we show that if a subadditive function can be $(1+ε)$-approximated in the insertion-only streaming model, then it can be $(2+ε)$-approximated also in the sliding-window model with space complexity larger by factor $O(ε^{-1}\log w)$, where $w$ is the window size. We demonstrate how our framework yields new approximation algorithms with relatively little effort for a variety of problems that do not admit the smooth-histogram technique. For example, in the frequency-vector model, a symmetric norm is subadditive and thus we obtain a sliding-window $(2+ε)$-approximation algorithm for it. Another example is for streaming matrices, where we derive a new sliding-window $(\sqrt{2}+ε)$-approximation algorithm for Schatten $4$-norm. We then consider graph streams and show that many graph problems are subadditive, including maximum submodular matching, minimum vertex-cover, and maximum $k$-cover, thereby deriving sliding-window $O(1)$-approximation algorithms for them almost for free (using known insertion-only algorithms). Finally, we design for every $d\in (1,2]$ an artificial function, based on the maximum-matching size, whose almost-smoothness parameter is exactly $d$.
Tight Approximation Bounds for Maximum Multi-Coverage
Venue: arXiv cs.DS 2022
Year: 2022

In the classic maximum coverage problem, we are given subsets $T_1, \dots, T_m$ of a universe $[n]$ along with an integer $k$ and the objective is to find a subset $S \subseteq [m]$ of size $k$ that maximizes $C(S) := |\cup_{i \in S} T_i|$. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of $(1-e^{-1})$ and there is a matching inapproximability result. We note that in the maximum coverage problem if an element $e \in [n]$ is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element $e$ as many times as it is covered, then we obtain a linear objective function, $C^{(\infty)}(S) = \sum_{i \in S} |T_i|$, which can be easily maximized under a cardinality constraint. We study the maximum $\ell$-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to $\ell$ times but no more; hence, we consider maximizing the function $C^{(\ell)}(S) = \sum_{e \in [n]} \min\{\ell, |\{i \in S : e \in T_i\}| \}$, subject to the constraint $|S| \leq k$. Note that the case of $\ell = 1$ corresponds to the standard maximum coverage setting and $\ell = \infty$ gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of $1 - \frac{\ell^{\ell}e^{-\ell}}{\ell!}$ for the $\ell$-multi-coverage problem. In particular, when $\ell = 2$, this factor is $1-2e^{-2} \approx 0.73$ and as $\ell$ grows the approximation ratio behaves as $1 - \frac{1}{\sqrt{2π\ell}}$. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.
Remove-Win: a Design Framework for Conflict-free Replicated Data Types
Venue: arXiv cs.DC 2022
Year: 2022

Distributed storage systems employ replication to improve performance and reliability. To provide low latency data access, replicas are often required to accept updates without coordination with each other, and the updates are then propagated asynchronously. This brings the critical challenge of conflict resolution among concurrent updates. Conflict-free Replicated Data Type (CRDT) is a principled approach to addressing this challenge. However, existing CRDT designs are tricky, and hard to be generalized to other data types. A design framework is in great need to guide the systematic design of new CRDTs. To address this challenge, we propose RWF -- the Remove-Win design Framework for CRDTs. RWF leverages the simple but powerful remove-win strategy to resolve conflicting updates, and provides generic design for a variety of data container types. Two exemplar implementations following RWF are given over the Redis data type store, which demonstrate the effectiveness of RWF. Performance measurements of our implementations further show the efficiency of CRDT designs following RWF.
Analyzing Code Comments to Boost Program Comprehension
Venue: arXiv cs.SE 2022
Year: 2022

We are trying to find source code comments that help programmers understand a nontrivial part of source code. One of such examples would be explaining to assign a zero as a way to "clear" a buffer. Such comments are invaluable to programmers and identifying them correctly would be of great help. Toward this goal, we developed a method to discover explanatory code comments in a source code. We first propose eleven distinct categories of code comments. We then developed a decision-tree based classifier that can identify explanatory comments with 60% precision and 80% recall. We analyzed 2,000 GitHub projects that are written in two languages: Java and Python. This task is novel in that it focuses on a microscopic comment ("local comment") within a method or function, in contrast to the prior efforts that focused on API- or method-level comments. We also investigated how different category of comments is used in different projects. Our key finding is that there are two dominant types of comments: preconditional and postconditional. Our findings also suggest that many English code comments have a certain grammatical structure that are consistent across different projects.
External Memory Planar Point Location with Fast Updates
Venue: arXiv cs.DS 2022
Year: 2022

We study dynamic planar point location in the External Memory Model or Disk Access Model (DAM). Previous work in this model achieves polylog query and polylog amortized update time. We present a data structure with $O( \log_B^2 N)$ query time and $O(\frac{1}{ B^{1-ε}} \log_B N)$ amortized update time, where $N$ is the number of segments, $B$ the block size and $ε$ is a small positive constant, under the assumption that all faces have constant size. This is a $B^{1-ε}$ factor faster for updates than the fastest previous structure, and brings the cost of insertion and deletion down to subconstant amortized time for reasonable choices of $N$ and $B$. Our structure solves the problem of vertical ray-shooting queries among a dynamic set of interior-disjoint line segments; this is well-known to solve dynamic planar point location for a connected subdivision of the plane with faces of constant size.
The complexity of MinRank
Venue: arXiv cs.SC 2022
Year: 2022

In this note, we leverage some of our results from arXiv:1706.06319 to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our main theorem recovers and extends previous results by Faugère, Safey El Din, Spaenlehauer (arXiv:1112.4411).
Leader Stochastic Gradient Descent for Distributed Training of Deep Learning Models: Extension
Venue: arXiv cs.LG 2022
Year: 2022

We consider distributed optimization under communication constraints for training deep learning models. We propose a new algorithm, whose parameter updates rely on two forces: a regular gradient step, and a corrective direction dictated by the currently best-performing worker (leader). Our method differs from the parameter-averaging scheme EASGD in a number of ways: (i) our objective formulation does not change the location of stationary points compared to the original optimization problem; (ii) we avoid convergence decelerations caused by pulling local workers descending to different local minima to each other (i.e. to the average of their parameters); (iii) our update by design breaks the curse of symmetry (the phenomenon of being trapped in poorly generalizing sub-optimal solutions in symmetric non-convex landscapes); and (iv) our approach is more communication efficient since it broadcasts only parameters of the leader rather than all workers. We provide theoretical analysis of the batch version of the proposed algorithm, which we call Leader Gradient Descent (LGD), and its stochastic variant (LSGD). Finally, we implement an asynchronous version of our algorithm and extend it to the multi-leader setting, where we form groups of workers, each represented by its own local leader (the best performer in a group), and update each worker with a corrective direction comprised of two attractive forces: one to the local, and one to the global leader (the best performer among all workers). The multi-leader setting is well-aligned with current hardware architecture, where local workers forming a group lie within a single computational node and different groups correspond to different nodes. For training convolutional neural networks, we empirically demonstrate that our approach compares favorably to state-of-the-art baselines. This work is a gentle extension of [2].
Regular resolution for CNFs with almost bounded one-sided treewidth
Venue: arXiv cs.CC 2022
Year: 2022

We introduce a one-sided incidence tree decomposition of a CNF $φ$. This is a tree decomposition of the incidence graph of $φ$ where the underlying tree is rooted and the set of bags containing each clause induces a directed path in the tree. The one-sided treewidth is the smallest width of a one-sided incidence tree decomposition. We consider a class of unsatisfiable CNF $φ$ that can be turned into one of one sided treewidth at most $k$ by removal of at most $p$ clauses. We show that the size of regular resolution for this class of CNFs is FPT parameterized by $k$ and $p$. The results contributes to understanding the complexity of resolution for CNFs of bounded incidence treewidth, an open problem well known in the areas of proof complexity and knowledge compilation. In particular, the result significantly generalizes all the restricted classes of CNFs of bounded incidence treewidth that are known to admit an FPT sized resolution. The proof includes an auxiliary result and several new notions that may be of an independent interest.
Private Identity Testing for High-Dimensional Distributions
Venue: arXiv cs.DS 2022
Year: 2022

In this work we present novel differentially private identity (goodness-of-fit) testers for natural and widely studied classes of multivariate product distributions: Gaussians in $\mathbb{R}^d$ with known covariance and product distributions over $\{\pm 1\}^{d}$. Our testers have improved sample complexity compared to those derived from previous techniques, and are the first testers whose sample complexity matches the order-optimal minimax sample complexity of $O(d^{1/2}/α^2)$ in many parameter regimes. We construct two types of testers, exhibiting tradeoffs between sample complexity and computational complexity. Finally, we provide a two-way reduction between testing a subclass of multivariate product distributions and testing univariate distributions, and thereby obtain upper and lower bounds for testing this subclass of product distributions.