OpenRaiser/Intern-Atlas huggingface dataset:
On the Parameterized Complexity of the Acyclic Matching Problem
Venue: arXiv cs.CC 2022
Year: 2022

A matching is a set of edges in a graph with no common endpoint. A matching M is called acyclic if the induced subgraph on the endpoints of the edges in M is acyclic. Given a graph G and an integer k, Acyclic Matching Problem seeks for an acyclic matching of size k in G. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter k. On the other hand, the problem is fixed parameter tractable with respect to the parameters tw and (k, c4), where tw and c4 are the treewidth and the number of cycles with length 4 of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter k for the line graphs and every proper minor-closed class of graphs (including planar graphs).
String Diagram Rewrite Theory III: Confluence with and without Frobenius
Venue: arXiv cs.LO 2022
Year: 2022

In this paper we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorically as double-pushout rewriting with interfaces (DPOI) on (labelled) hypergraphs. For standard DPO rewriting without interfaces, confluence for terminating rewrite systems is, in general, undecidable. Nevertheless, we show here that confluence for DPOI, and hence string diagram rewriting, is decidable. We apply this result to give effective procedures for deciding local confluence of symmetric monoidal theories with and without Frobenius structure by critical pair analysis. For the latter, we introduce the new notion of path joinability for critical pairs, which enables finitely many joins of a critical pair to be lifted to an arbitrary context in spite of the strong non-local constraints placed on rewriting in a generic symmetric monoidal theory.
Minimizing Quantum Renyi Divergences via Mirror Descent with Polyak Step Size
Venue: arXiv cs.IT 2022
Year: 2022

Quantum information quantities play a substantial role in characterizing operational quantities in various quantum information-theoretic problems. We consider numerical computation of four quantum information quantities: Petz-Augustin information, sandwiched Augustin information, conditional sandwiched Renyi entropy and sandwiched Renyi information. To compute these quantities requires minimizing some order-$α$ quantum Renyi divergences over the set of quantum states. Whereas the optimization problems are obviously convex, they violate standard bounded gradient/Hessian conditions in literature, so existing convex optimization methods and their convergence guarantees do not directly apply. In this paper, we propose a new class of convex optimization methods called mirror descent with the Polyak step size. We prove their convergence under a weak condition, showing that they provably converge for minimizing quantum Renyi divergences. Numerical experiment results show that entropic mirror descent with the Polyak step size converges fast in minimizing quantum Renyi divergences.
Discovering the Unknown Knowns: Turning Implicit Knowledge in the Dataset into Explicit Training Examples for Visual Question Answering
Venue: arXiv cs.CV 2022
Year: 2022

Visual question answering (VQA) is challenging not only because the model has to handle multi-modal information, but also because it is just so hard to collect sufficient training examples -- there are too many questions one can ask about an image. As a result, a VQA model trained solely on human-annotated examples could easily over-fit specific question styles or image contents that are being asked, leaving the model largely ignorant about the sheer diversity of questions. Existing methods address this issue primarily by introducing an auxiliary task such as visual grounding, cycle consistency, or debiasing. In this paper, we take a drastically different approach. We found that many of the "unknowns" to the learned VQA model are indeed "known" in the dataset implicitly. For instance, questions asking about the same object in different images are likely paraphrases; the number of detected or annotated objects in an image already provides the answer to the "how many" question, even if the question has not been annotated for that image. Building upon these insights, we present a simple data augmentation pipeline SimpleAug to turn this "known" knowledge into training examples for VQA. We show that these augmented examples can notably improve the learned VQA models' performance, not only on the VQA-CP dataset with language prior shifts but also on the VQA v2 dataset without such shifts. Our method further opens up the door to leverage weakly-labeled or unlabeled images in a principled way to enhance VQA models. Our code and data are publicly available at https://github.com/heendung/simpleAUG.
Adaptive Constrained Kinematic Control using Partial or Complete Task-Space Measurements
Venue: arXiv cs.RO 2022
Year: 2022

Recent advancements in constrained kinematic control make it an attractive strategy for controlling robots with arbitrary geometry in challenging tasks. Most current works assume that the robot kinematic model is precise enough for the task at hand. However, with increasing demands and safety requirements in robotic applications, there is a need for a controller that compensates online for kinematic inaccuracies. We propose an adaptive constrained kinematic control strategy based on quadratic programming, which uses partial or complete task-space measurements to compensate online for calibration errors. Our method is validated in experiments that show increased accuracy and safety compared to a state-of-the-art kinematic control strategy.
Locality in online, dynamic, sequential, and distributed graph algorithms
Venue: arXiv cs.DS 2022
Year: 2022

In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node we get to see its radius-T neighborhood before choosing the output. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, its sequential counterpart SLOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models, with LOCAL being the weakest and online-LOCAL the strongest model. In general, all models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all models are roughly equivalent: the locality of any LCL problem falls in the same broad class - $O(\log^* n)$, $Θ(\log n)$, or $n^{Θ(1)}$ - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in general bipartite graphs. We provide an online-LOCAL algorithm with locality $O(\log n)$ for the $3$-coloring problem in bipartite graphs - this is a problem with locality $Ω(n^{1/2})$ in the LOCAL model and $Ω(n^{1/10})$ in the SLOCAL model.
An MRC Framework for Semantic Role Labeling
Venue: arXiv cs.CL 2022
Year: 2022

Semantic Role Labeling (SRL) aims at recognizing the predicate-argument structure of a sentence and can be decomposed into two subtasks: predicate disambiguation and argument labeling. Prior work deals with these two tasks independently, which ignores the semantic connection between the two tasks. In this paper, we propose to use the machine reading comprehension (MRC) framework to bridge this gap. We formalize predicate disambiguation as multiple-choice machine reading comprehension, where the descriptions of candidate senses of a given predicate are used as options to select the correct sense. The chosen predicate sense is then used to determine the semantic roles for that predicate, and these semantic roles are used to construct the query for another MRC model for argument labeling. In this way, we are able to leverage both the predicate semantics and the semantic role semantics for argument labeling. We also propose to select a subset of all the possible semantic roles for computational efficiency. Experiments show that the proposed framework achieves state-of-the-art or comparable results to previous work. Code is available at \url{https://github.com/ShannonAI/MRC-SRL}.
IGNNITION: Bridging the Gap Between Graph Neural Networks and Networking Systems
Venue: arXiv cs.LG 2022
Year: 2022

Recent years have seen the vast potential of Graph Neural Networks (GNN) in many fields where data is structured as graphs (e.g., chemistry, recommender systems). In particular, GNNs are becoming increasingly popular in the field of networking, as graphs are intrinsically present at many levels (e.g., topology, routing). The main novelty of GNNs is their ability to generalize to other networks unseen during training, which is an essential feature for developing practical Machine Learning (ML) solutions for networking. However, implementing a functional GNN prototype is currently a cumbersome task that requires strong skills in neural network programming. This poses an important barrier to network engineers that often do not have the necessary ML expertise. In this article, we present IGNNITION, a novel open-source framework that enables fast prototyping of GNNs for networking systems. IGNNITION is based on an intuitive high-level abstraction that hides the complexity behind GNNs, while still offering great flexibility to build custom GNN architectures. To showcase the versatility and performance of this framework, we implement two state-of-the-art GNN models applied to different networking use cases. Our results show that the GNN models produced by IGNNITION are equivalent in terms of accuracy and performance to their native implementations in TensorFlow.
Linear block and convolutional MDS codes to required rate, distance and type
Venue: arXiv cs.IT 2022
Year: 2022

Algebraic methods for the design of series of maximum distance separable (MDS) linear block and convolutional codes to required specifications and types are presented. Algorithms are given to design codes to required rate and required error-correcting capability and required types. Infinite series of block codes with rate approaching a given rational $R$ with $0<R<1$ and relative distance over length approaching $(1-R)$ are designed. These can be designed over fields of given characteristic $p$ or over fields of prime order and can be specified to be of a particular type such as (i) dual-containing under Euclidean inner product, (ii) dual-containing under Hermitian inner product, (iii) quantum error-correcting, (iv) linear complementary dual (LCD). Convolutional codes to required rate and distance and infinite series of convolutional codes with rate approaching a given rational $R$ and distance over length approaching $2(1-R)$ are designed. The designs are algebraic and properties, including distances, are shown algebraically. Algebraic explicit efficient decoding methods are referenced.
Improving Zero-shot Cross-lingual Transfer between Closely Related Languages by injecting Character-level Noise
Venue: arXiv cs.CL 2022
Year: 2022

Cross-lingual transfer between a high-resource language and its dialects or closely related language varieties should be facilitated by their similarity. However, current approaches that operate in the embedding space do not take surface similarity into account. This work presents a simple yet effective strategy to imrove cross-lingual transfer between closely related varieties. We propose to augment the data of the high-resource source language with character-level noise to make the model more robust towards spelling variations. Our strategy shows consistent improvements over several languages and tasks: Zero-shot transfer of POS tagging and topic identification between language varieties from the Finnic, West and North Germanic, and Western Romance language branches. Our work provides evidence for the usefulness of simple surface-level noise in improving transfer between language varieties.
Robust Contrastive Active Learning with Feature-guided Query Strategies
Venue: arXiv cs.LG 2022
Year: 2022

We introduce supervised contrastive active learning (SCAL) and propose efficient query strategies in active learning based on the feature similarity (featuresim) and principal component analysis based feature-reconstruction error (fre) to select informative data samples with diverse feature representations. We demonstrate our proposed method achieves state-of-the-art accuracy, model calibration and reduces sampling bias in an active learning setup for balanced and imbalanced datasets on image classification tasks. We also evaluate robustness of model to distributional shift derived from different query strategies in active learning setting. Using extensive experiments, we show that our proposed approach outperforms high performing compute-intensive methods by a big margin resulting in 9.9% lower mean corruption error, 7.2% lower expected calibration error under dataset shift and 8.9% higher AUROC for out-of-distribution detection.
Elastic Tracker: A Spatio-temporal Trajectory Planner Flexible Aerial Tracking
Venue: arXiv cs.RO 2022
Year: 2022

This paper proposes Elastic Tracker, a flexible trajectory planning framework that can deal with challenging tracking tasks with guaranteed safety and visibility. Firstly, an object detection and intension-free motion prediction method is designed. Then an occlusion-aware path finding method is proposed to provide a proper topology. A smart safe flight corridor generation strategy is designed with the guiding path. An analytical occlusion cost is evaluated. Finally, an effective trajectory optimization approach enables to generate a spatio-temporal optimal trajectory within the resultant flight corridor. Particular formulations are designed to guarantee both safety and visibility, with all the above requirements optimized jointly. The experimental results show that our method works more robustly but with less computation than the existing methods, even in some challenging tracking tasks.
Low-Resource Named Entity Recognition Based on Multi-hop Dependency Trigger
Venue: arXiv cs.CL 2022
Year: 2022

This paper presents a simple and effective approach in low-resource named entity recognition (NER) based on multi-hop dependency trigger. Dependency trigger refer to salient nodes relative to a entity in the dependency graph of a context sentence. Our main observation is that there often exists trigger which play an important role to recognize the location and type of entity in sentence. Previous research has used manual labelling of trigger. Our main contribution is to propose use a syntactic parser to automatically annotate trigger. Experiments on two English datasets (CONLL 2003 and BC5CDR) show that the proposed method is comparable to the previous trigger-based NER model.
Progressive Hard-case Mining across Pyramid Levels for Object Detection
Venue: arXiv cs.CV 2022
Year: 2022

In object detection, multi-level prediction (e.g., FPN) and reweighting skills (e.g., focal loss) have drastically improved one-stage detector performance. However, the synergy between these two techniques is not fully explored in a unified framework. We find that, during training, the one-stage detector's optimization is not only restricted to the static hard-case mining loss (gradient drift) but also suffered from the diverse positive samples' proportions split by different pyramid levels (level discrepancy). Under this concern, we propose Hierarchical Progressive Focus (HPF) consisting of two key designs: 1) progressive focus, a more flexible hard-case mining setting calculated adaptive to the convergence progress, 2) hierarchical sampling, automatically generating a set of progressive focus for level-specific target optimization. Based on focal loss with ATSS-R50, our approach achieves 40.5 AP, surpassing the state-of-the-art QFL (Quality Focal Loss, 39.9 AP) and VFL (Varifocal Loss, 40.1 AP). Our best model achieves 55.1 AP on COCO test-dev, obtaining excellent results with only a typical training setting. Moreover, as a plug-and-play scheme, HPF can cooperate well with recent advances, providing a stable performance improvement on nine mainstream detectors.
Take a deep breath. Benefits of neuroplasticity practices for software developers and computer workers in a family of experiments
Venue: arXiv cs.SE 2022
Year: 2022

Context. Computer workers in general, and software developers specifically, are under a high amount of stress due to continuous deadlines and, often, over-commitment. Objective. This study investigates the effects of a neuroplasticity practice, a specific breathing practice, on the attention awareness, well-being, perceived productivity, and self-efficacy of computer workers. Method. We created a questionnaire mainly from existing, validated scales as entry and exit survey for data points for comparison before and after the intervention. The intervention was a 12-week program with a weekly live session that included a talk on a well-being topic and a facilitated group breathing session. During the intervention period, we solicited one daily journal note and one weekly well-being rating. We replicated the intervention in a similarly structured 8-week program. The data was analyzed using a Bayesian multi-level model for the quantitative part and thematic analysis for the qualitative part. Results. The intervention showed improvements in participants' experienced inner states despite an ongoing pandemic and intense outer circumstances for most. Over the course of the study, we found an improvement in the participants' ratings of how often they found themselves in good spirits as well as in a calm and relaxed state. We also aggregate a large number of deep inner reflections and growth processes that may not have surfaced for the participants without deliberate engagement in such a program. Conclusion. The data indicates usefulness and effectiveness of an intervention for computer workers in terms of increasing well-being and resilience. Everyone needs a way to deliberately relax, unplug, and recover. Breathing practice is a simple way to do so, and the results call for establishing a larger body of work to make this common practice.
Assisting the Human Fact-Checkers: Detecting All Previously Fact-Checked Claims in a Document
Venue: arXiv cs.CL 2022
Year: 2022

Given the recent proliferation of false claims online, there has been a lot of manual fact-checking effort. As this is very time-consuming, human fact-checkers can benefit from tools that can support them and make them more efficient. Here, we focus on building a system that could provide such support. Given an input document, it aims to detect all sentences that contain a claim that can be verified by some previously fact-checked claims (from a given database). The output is a re-ranked list of the document sentences, so that those that can be verified are ranked as high as possible, together with corresponding evidence. Unlike previous work, which has looked into claim retrieval, here we take a document-level perspective. We create a new manually annotated dataset for this task, and we propose suitable evaluation measures. We further experiment with a learning-to-rank approach, achieving sizable performance gains over several strong baselines. Our analysis demonstrates the importance of modeling text similarity and stance, while also taking into account the veracity of the retrieved previously fact-checked claims. We believe that this research would be of interest to fact-checkers, journalists, media, and regulatory authorities.
MPC-Friendly Commitments for Publicly Verifiable Covert Security
Venue: arXiv cs.CR 2022
Year: 2022

We address the problem of efficiently verifying a commitment in a two-party computation. This addresses the scenario where a party P1 commits to a value $x$ to be used in a subsequent secure computation with another party P2 that wants to receive assurance that P1 did not cheat, i.e. that $x$ was indeed the value inputted into the secure computation. Our constructions operate in the publicly verifiable covert (PVC) security model, which is a relaxation of the malicious model of MPC appropriate in settings where P1 faces a reputational harm if caught cheating. We introduce the notion of PVC commitment scheme and indexed hash functions to build commitments schemes tailored to the PVC framework, and propose constructions for both arithmetic and Boolean circuits that result in very efficient circuits. From a practical standpoint, our constructions for Boolean circuits are $60\times$ faster to evaluate securely, and use $36\times$ less communication than baseline methods based on hashing. Moreover, we show that our constructions are tight in terms of required non-linear operations, by proving lower bounds on the nonlinear gate count of commitment verification circuits. Finally, we present a technique to amplify the security properties our constructions that allows to efficiently recover malicious guarantees with statistical security.
Discovering Useful Compact Sets of Sequential Rules in a Long Sequence
Venue: arXiv cs.LG 2022
Year: 2022

We are interested in understanding the underlying generation process for long sequences of symbolic events. To do so, we propose COSSU, an algorithm to mine small and meaningful sets of sequential rules. The rules are selected using an MDL-inspired criterion that favors compactness and relies on a novel rule-based encoding scheme for sequences. Our evaluation shows that COSSU can successfully retrieve relevant sets of closed sequential rules from a long sequence. Such rules constitute an interpretable model that exhibits competitive accuracy for the tasks of next-element prediction and classification.
METEOR:A Dense, Heterogeneous, and Unstructured Traffic Dataset With Rare Behaviors
Venue: arXiv cs.CV 2022
Year: 2022

We present a new traffic dataset, METEOR, which captures traffic patterns and multi-agent driving behaviors in unstructured scenarios. METEOR consists of more than 1000 one-minute videos, over 2 million annotated frames with bounding boxes and GPS trajectories for 16 unique agent categories, and more than 13 million bounding boxes for traffic agents. METEOR is a dataset for rare and interesting, multi-agent driving behaviors that are grouped into traffic violations, atypical interactions, and diverse scenarios. Every video in METEOR is tagged using a diverse range of factors corresponding to weather, time of the day, road conditions, and traffic density. We use METEOR to benchmark perception methods for object detection and multi-agent behavior prediction. Our key finding is that state-of-the-art models for object detection and behavior prediction, which otherwise succeed on existing datasets such as Waymo, fail on the METEOR dataset. METEOR marks the first step towards the development of more sophisticated perception models for dense, heterogeneous, and unstructured scenarios.