OpenRaiser/Intern-Atlas huggingface dataset:
Acyclic and Cyclic Reversing Computations in Petri Nets
Venue: arXiv cs.CL 2022
Year: 2022

Reversible computations constitute an unconventional form of computing where any sequence of performed operations can be undone by executing in reverse order at any point during a computation. It has been attracting increasing attention as it provides opportunities for low-power computation, being at the same time essential or eligible in various applications. In recent work, we have proposed a structural way of translating Reversing Petri Nets (RPNs) - a type of Petri nets that embeds reversible computation, to bounded Coloured Petri Nets (CPNs) - an extension of traditional Petri Nets, where tokens carry data values. Three reversing semantics are possible in RPNs: backtracking (reversing of the lately executed action), causal reversing (action can be reversed only when all its effects have been undone) and out of causal reversing (any previously performed action can be reversed). In this paper, we extend the RPN to CPN translation with formal proofs of correctness. Moreover, the possibility of introduction of cycles to RPNs is discussed. We analyze which type of cycles could be allowed in RPNs to ensure consistency with the current semantics. It emerged that the most interesting case related to cycles in RPNs occurs in causal semantics, where various interpretations of dependency result in different net's behaviour during reversing. Three definitions of dependence are presented and discussed.
Ordered Attention for Coherent Visual Storytelling
Venue: arXiv cs.CV 2022
Year: 2022

We address the problem of visual storytelling, i.e., generating a story for a given sequence of images. While each sentence of the story should describe a corresponding image, a coherent story also needs to be consistent and relate to both future and past images. To achieve this we develop ordered image attention (OIA). OIA models interactions between the sentence-corresponding image and important regions in other images of the sequence. To highlight the important objects, a message-passing-like algorithm collects representations of those objects in an order-aware manner. To generate the story's sentences, we then highlight important image attention vectors with an Image-Sentence Attention (ISA). Further, to alleviate common linguistic mistakes like repetitiveness, we introduce an adaptive prior. The obtained results improve the METEOR score on the VIST dataset by 1%. In addition, an extensive human study verifies coherency improvements and shows that OIA and ISA generated stories are more focused, shareable, and image-grounded.
O2NA: An Object-Oriented Non-Autoregressive Approach for Controllable Video Captioning
Venue: arXiv cs.CL 2022
Year: 2022

Video captioning combines video understanding and language generation. Different from image captioning that describes a static image with details of almost every object, video captioning usually considers a sequence of frames and biases towards focused objects, e.g., the objects that stay in focus regardless of the changing background. Therefore, detecting and properly accommodating focused objects is critical in video captioning. To enforce the description of focused objects and achieve controllable video captioning, we propose an Object-Oriented Non-Autoregressive approach (O2NA), which performs caption generation in three steps: 1) identify the focused objects and predict their locations in the target caption; 2) generate the related attribute words and relation words of these focused objects to form a draft caption; and 3) combine video information to refine the draft caption to a fluent final caption. Since the focused objects are generated and located ahead of other words, it is difficult to apply the word-by-word autoregressive generation process; instead, we adopt a non-autoregressive approach. The experiments on two benchmark datasets, i.e., MSR-VTT and MSVD, demonstrate the effectiveness of O2NA, which achieves results competitive with the state-of-the-arts but with both higher diversity and higher inference speed.
Criticality Metrics for Automated Driving: A Review and Suitability Analysis of the State of the Art
Venue: arXiv cs.RO 2022
Year: 2022

The large-scale deployment of automated vehicles on public roads has the potential to vastly change the transportation modalities of today's society. Although this pursuit has been initiated decades ago, there still exist open challenges in reliably ensuring that such vehicles operate safely in open contexts. While functional safety is a well-established concept, the question of measuring the behavioral safety of a vehicle remains subject to research. One way to both objectively and computationally analyze traffic conflicts is the development and utilization of so-called criticality metrics. Contemporary approaches have leveraged the potential of criticality metrics in various applications related to automated driving, e.g. for computationally assessing the dynamic risk or filtering large data sets to build scenario catalogs. As a prerequisite to systematically choose adequate criticality metrics for such applications, we extensively review the state of the art of criticality metrics, their properties, and their applications in the context of automated driving. Based on this review, we propose a suitability analysis as a methodical tool to be used by practitioners. Both the proposed method and the state of the art review can then be harnessed to select well-suited measurement tools that cover an application's requirements, as demonstrated by an exemplary execution of the analysis. Ultimately, efficient, valid, and reliable measurements of an automated vehicle's safety performance are a key requirement for demonstrating its trustworthiness.
Aspis: Robust Detection for Distributed Learning
Venue: arXiv cs.LG 2022
Year: 2022

State-of-the-art machine learning models are routinely trained on large-scale distributed clusters. Crucially, such systems can be compromised when some of the computing devices exhibit abnormal (Byzantine) behavior and return arbitrary results to the parameter server (PS). This behavior may be attributed to a plethora of reasons, including system failures and orchestrated attacks. Existing work suggests robust aggregation and/or computational redundancy to alleviate the effect of distorted gradients. However, most of these schemes are ineffective when an adversary knows the task assignment and can choose the attacked workers judiciously to induce maximal damage. Our proposed method Aspis assigns gradient computations to worker nodes using a subset-based assignment which allows for multiple consistency checks on the behavior of a worker node. Examination of the calculated gradients and post-processing (clique-finding in an appropriately constructed graph) by the central node allows for efficient detection and subsequent exclusion of adversaries from the training process. We prove the Byzantine resilience and detection guarantees of Aspis under weak and strong attacks and extensively evaluate the system on various large-scale training scenarios. The principal metric for our experiments is the test accuracy, for which we demonstrate a significant improvement of about 30% compared to many state-of-the-art approaches on the CIFAR-10 dataset. The corresponding reduction of the fraction of corrupted gradients ranges from 16% to 99%.
Automatic Rail Component Detection Based on AttnConv-Net
Venue: arXiv cs.CV 2022
Year: 2022

The automatic detection of major rail components using railway images is beneficial to ensure the rail transport safety. In this paper, we propose an attention-powered deep convolutional network (AttnConv-net) to detect multiple rail components including the rail, clips, and bolts. The proposed method consists of a deep convolutional neural network (DCNN) as the backbone, cascading attention blocks (CAB), and two feed forward networks (FFN). Two types of positional embedding are applied to enrich information in latent features extracted from the backbone. Based on processed latent features, the CAB aims to learn the local context of rail components including their categories and component boundaries. Final categories and bounding boxes are generated via two FFN implemented in parallel. To enhance the detection of small components, various data augmentation methods are employed in the training process. The effectiveness of the proposed AttnConv-net is validated with one real dataset and another synthesized dataset. Compared with classic convolutional neural network based methods, our proposed method simplifies the detection pipeline by eliminating the need of prior- and post-processing, which offers a new speed-quality solution to enable faster and more accurate image-based rail component detections
Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach
Venue: arXiv cs.LG 2022
Year: 2022

One of the challenges for multi-agent reinforcement learning (MARL) is designing efficient learning algorithms for a large system in which each agent has only limited or partial information of the entire system. While exciting progress has been made to analyze decentralized MARL with the network of agents for social networks and team video games, little is known theoretically for decentralized MARL with the network of states for modeling self-driving vehicles, ride-sharing, and data and traffic routing. This paper proposes a framework of localized training and decentralized execution to study MARL with network of states. Localized training means that agents only need to collect local information in their neighboring states during the training phase; decentralized execution implies that agents can execute afterwards the learned decentralized policies, which depend only on agents' current states. The theoretical analysis consists of three key components: the first is the reformulation of the MARL system as a networked Markov decision process with teams of agents, enabling updating the associated team Q-function in a localized fashion; the second is the Bellman equation for the value function and the appropriate Q-function on the probability measure space; and the third is the exponential decay property of the team Q-function, facilitating its approximation with efficient sample efficiency and controllable error. The theoretical analysis paves the way for a new algorithm LTDE-Neural-AC, where the actor-critic approach with over-parameterized neural networks is proposed. The convergence and sample complexity is established and shown to be scalable with respect to the sizes of both agents and states. To the best of our knowledge, this is the first neural network based MARL algorithm with network structure and provably convergence guarantee.
WSDesc: Weakly Supervised 3D Local Descriptor Learning for Point Cloud Registration
Venue: arXiv cs.CV 2022
Year: 2022

In this work, we present a novel method called WSDesc to learn 3D local descriptors in a weakly supervised manner for robust point cloud registration. Our work builds upon recent 3D CNN-based descriptor extractors, which leverage a voxel-based representation to parameterize local geometry of 3D points. Instead of using a predefined fixed-size local support in voxelization, we propose to learn the optimal support in a data-driven manner. To this end, we design a novel differentiable voxelization layer that can back-propagate the gradient to the support size optimization. To train the extracted descriptors, we propose a novel registration loss based on the deviation from rigidity of 3D transformations, and the loss is weakly supervised by the prior knowledge that the input point clouds have partial overlap, without requiring ground-truth alignment information. Through extensive experiments, we show that our learned descriptors yield superior performance on existing geometric registration benchmarks.
Lower Bounds for Shared-Memory Leader Election under Bounded Write Contention
Venue: arXiv cs.DC 2022
Year: 2022

This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for randomized obstruction-free algorithms. The approach extends to lower bounds for randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case contention incurred by a processor in an execution.
On Measures of Biases and Harms in NLP
Venue: arXiv cs.CL 2022
Year: 2022

Recent studies show that Natural Language Processing (NLP) technologies propagate societal biases about demographic groups associated with attributes such as gender, race, and nationality. To create interventions and mitigate these biases and associated harms, it is vital to be able to detect and measure such biases. While existing works propose bias evaluation and mitigation methods for various tasks, there remains a need to cohesively understand the biases and the specific harms they measure, and how different measures compare with each other. To address this gap, this work presents a practical framework of harms and a series of questions that practitioners can answer to guide the development of bias measures. As a validation of our framework and documentation questions, we also present several case studies of how existing bias measures in NLP -- both intrinsic measures of bias in representations and extrinsic measures of bias of downstream applications -- can be aligned with different harms and how our proposed documentation questions facilitates more holistic understanding of what bias measures are measuring.
Jointly Attacking Graph Neural Network and its Explanations
Venue: arXiv cs.LG 2022
Year: 2022

Graph Neural Networks (GNNs) have boosted the performance for many graph-related tasks. Despite the great success, recent studies have shown that GNNs are highly vulnerable to adversarial attacks, where adversaries can mislead the GNNs' prediction by modifying graphs. On the other hand, the explanation of GNNs (GNNExplainer) provides a better understanding of a trained GNN model by generating a small subgraph and features that are most influential for its prediction. In this paper, we first perform empirical studies to validate that GNNExplainer can act as an inspection tool and have the potential to detect the adversarial perturbations for graphs. This finding motivates us to further initiate a new problem investigation: Whether a graph neural network and its explanations can be jointly attacked by modifying graphs with malicious desires? It is challenging to answer this question since the goals of adversarial attacks and bypassing the GNNExplainer essentially contradict each other. In this work, we give a confirmative answer to this question by proposing a novel attack framework (GEAttack), which can attack both a GNN model and its explanations by simultaneously exploiting their vulnerabilities. Extensive experiments on two explainers (GNNExplainer and PGExplainer) under various real-world datasets demonstrate the effectiveness of the proposed method.
A Tool for Organizing Key Characteristics of Virtual, Augmented, and Mixed Reality for Human-Robot Interaction Systems: Synthesizing VAM-HRI Trends and Takeaways
Venue: arXiv cs.RO 2022
Year: 2022

Frameworks have begun to emerge to categorize Virtual, Augmented, and Mixed Reality (VAM) technologies that provide immersive, intuitive interfaces to facilitate Human-Robot Interaction. These frameworks, however, fail to capture key characteristics of the growing subfield of VAM-HRI and can be difficult to consistently apply due to continuous scales. This work builds upon these prior frameworks through the creation of a Tool for Organizing Key Characteristics of VAM-HRI Systems (TOKCS). TOKCS discretizes the continuous scales used within prior works for more consistent classification and adds additional characteristics related to a robot's internal model, anchor locations, manipulability, and the system's software and hardware. To showcase the tool's capability, TOKCS is applied to the ten papers from the fourth VAM-HRI workshop and examined for key trends and takeaways. These trends highlight the expressive capability of TOKCS while also helping frame newer trends and future work recommendations for VAM-HRI research.
Clio: A Hardware-Software Co-Designed Disaggregated Memory System
Venue: arXiv cs.DC 2022
Year: 2022

Memory disaggregation has attracted great attention recently because of its benefits in efficient memory utilization and ease of management. So far, memory disaggregation research has all taken one of two approaches: building/emulating memory nodes using regular servers or building them using raw memory devices with no processing power. The former incurs higher monetary cost and faces tail latency and scalability limitations, while the latter introduces performance, security, and management problems. Server-based memory nodes and memory nodes with no processing power are two extreme approaches. We seek a sweet spot in the middle by proposing a hardware-based memory disaggregation solution that has the right amount of processing power at memory nodes. Furthermore, we take a clean-slate approach by starting from the requirements of memory disaggregation and designing a memory-disaggregation-native system. We built Clio, a disaggregated memory system that virtualizes, protects, and manages disaggregated memory at hardware-based memory nodes. The Clio hardware includes a new virtual memory system, a customized network system, and a framework for computation offloading. In building Clio, we not only co-design OS functionalities, hardware architecture, and the network system, but also co-design compute nodes and memory nodes. Our FPGA prototype of Clio demonstrates that each memory node can achieve 100 Gbps throughput and an end-to-end latency of 2.5 us at median and 3.2us at the 99th percentile. Clio also scales much better and has orders of magnitude lower tail latency than RDMA. It has 1.1x to 3.4x energy saving compared to CPU-based and SmartNIC-based disaggregated memory systems and is 2.7x faster than software-based SmartNIC solutions.
Context-Aware Mixup for Domain Adaptive Semantic Segmentation
Venue: arXiv cs.CV 2022
Year: 2022

Unsupervised domain adaptation (UDA) aims to adapt a model of the labeled source domain to an unlabeled target domain. Existing UDA-based semantic segmentation approaches always reduce the domain shifts in pixel level, feature level, and output level. However, almost all of them largely neglect the contextual dependency, which is generally shared across different domains, leading to less-desired performance. In this paper, we propose a novel Context-Aware Mixup (CAMix) framework for domain adaptive semantic segmentation, which exploits this important clue of context-dependency as explicit prior knowledge in a fully end-to-end trainable manner for enhancing the adaptability toward the target domain. Firstly, we present a contextual mask generation strategy by leveraging the accumulated spatial distributions and prior contextual relationships. The generated contextual mask is critical in this work and will guide the context-aware domain mixup on three different levels. Besides, provided the context knowledge, we introduce a significance-reweighted consistency loss to penalize the inconsistency between the mixed student prediction and the mixed teacher prediction, which alleviates the negative transfer of the adaptation, e.g., early performance degradation. Extensive experiments and analysis demonstrate the effectiveness of our method against the state-of-the-art approaches on widely-used UDA benchmarks.
Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space
Venue: arXiv cs.GT 2022
Year: 2022

We investigate the Euclidean $d$-Dimensional Stable Roommates problem, which asks whether a given set~$V$ of $d \cdot n$ points from the 2-dimensional Euclidean space can be partitioned into $n$ disjoint (unordered) subsets $Π=\{V_1,\ldots,V_{n}\}$ with $|V_i|=d$ for each $V_i\in Π$ such that $Π$ is stable. Here, stability means that no point subset $W\subseteq V$ is blocking $Π$ and $W$ is said to be blocking $Π$ if $|W|= d$ such that $\sum_{w'\in W}δ(w,w') < \sum_{v\in Π(w)}δ(w,v)$ holds for each point $w\in W$, where $Π(w)$ denotes the subset $V_i\in Π$ which contains $w$ and $δ(a,b)$ denotes the Euclidean distance between points $a$ and $b$. Complementing the existing known polynomial-time result for $d=2$, we show that such polynomial-time algorithms cannot exist for any fixed number $d \ge 3$ unless P=NP. Our result for $d=3$ answers a decade-long open question in the theory of Stable Matching and Hedonic Games [17, 1, 9, 25, 20].
On the Power of Differentiable Learning versus PAC and SQ Learning
Venue: arXiv cs.LG 2022
Year: 2022

We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms. We show that SGD and GD can always simulate learning with statistical queries (SQ), but their ability to go beyond that depends on the precision $ρ$ of the gradient calculations relative to the minibatch size $b$ (for SGD) and sample size $m$ (for GD). With fine enough precision relative to minibatch size, namely when $b ρ$ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for $b=1$. Similarly, with fine enough precision relative to the sample size $m$, GD can also simulate any sample-based learning algorithm based on $m$ samples. In particular, with polynomially many bits of precision (i.e. when $ρ$ is exponentially small), SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when $b ρ^2$ is large enough, the power of SGD is equivalent to that of SQ learning.
GANmapper: geographical data translation
Venue: arXiv cs.CV 2022
Year: 2022

We present a new method to create spatial data using a generative adversarial network (GAN). Our contribution uses coarse and widely available geospatial data to create maps of less available features at the finer scale in the built environment, bypassing their traditional acquisition techniques (e.g. satellite imagery or land surveying). In the work, we employ land use data and road networks as input to generate building footprints and conduct experiments in 9 cities around the world. The method, which we implement in a tool we release openly, enables the translation of one geospatial dataset to another with high fidelity and morphological accuracy. It may be especially useful in locations missing detailed and high-resolution data and those that are mapped with uncertain or heterogeneous quality, such as much of OpenStreetMap. The quality of the results is influenced by the urban form and scale. In most cases, the experiments suggest promising performance as the method tends to truthfully indicate the locations, amount, and shape of buildings. The work has the potential to support several applications, such as energy, climate, and urban morphology studies in areas previously lacking required data or inpainting geospatial data in regions with incomplete data.