OpenRaiser/Intern-Atlas huggingface dataset:
Heterogeneous Sparse Matrix-Vector Multiplication via Compressed Sparse Row Format
Venue: arXiv cs.DC 2023
Year: 2023

Sparse matrix-vector multiplication (SpMV) is one of the most important kernels in high-performance computing (HPC), yet SpMV normally suffers from ill performance on many devices. Due to ill performance, SpMV normally requires special care to store and tune for a given device. Moreover, HPC is facing heterogeneous hardware containing multiple different compute units, e.g., many-core CPUs and GPUs. Therefore, an emerging goal has been to produce heterogeneous formats and methods that allow critical kernels, e.g., SpMV, to be executed on different devices with portable performance and minimal changes to format and method. This paper presents a heterogeneous format based on CSR, named CSR-k, that can be tuned quickly and outperforms the average performance of Intel MKL on Intel Xeon Platinum 8380 and AMD Epyc 7742 CPUs while still outperforming NVIDIA's cuSPARSE and Sandia National Laboratories' KokkosKernels on NVIDIA A100 and V100 for regular sparse matrices, i.e., sparse matrices where the number of nonzeros per row has a variance $\leq$ 10, such as those commonly generated from two and three-dimensional finite difference and element problems. In particular, CSR-k achieves this with reordering and by grouping rows into a hierarchical structure of super-rows and super-super-rows that are represented by just a few extra arrays of pointers. Due to its simplicity, a model can be tuned for a device and used to select super-row and super-super-rows sizes in constant time.
MetAug: Contrastive Learning via Meta Feature Augmentation
Venue: arXiv cs.CV 2023
Year: 2023

What matters for contrastive learning? We argue that contrastive learning heavily relies on informative features, or "hard" (positive or negative) features. Early works include more informative features by applying complex data augmentations and large batch size or memory bank, and recent works design elaborate sampling approaches to explore informative features. The key challenge toward exploring such features is that the source multi-view data is generated by applying random data augmentations, making it infeasible to always add useful information in the augmented data. Consequently, the informativeness of features learned from such augmented data is limited. In response, we propose to directly augment the features in latent space, thereby learning discriminative representations without a large amount of input data. We perform a meta learning technique to build the augmentation generator that updates its network parameters by considering the performance of the encoder. However, insufficient input data may lead the encoder to learn collapsed features and therefore malfunction the augmentation generator. A new margin-injected regularization is further added in the objective function to avoid the encoder learning a degenerate mapping. To contrast all features in one gradient back-propagation step, we adopt the proposed optimization-driven unified contrastive loss instead of the conventional contrastive loss. Empirically, our method achieves state-of-the-art results on several benchmark datasets.
Suspected Object Matters: Rethinking Model's Prediction for One-stage Visual Grounding
Venue: arXiv cs.CV 2023
Year: 2023

Recently, one-stage visual grounders attract high attention due to their comparable accuracy but significantly higher efficiency than two-stage grounders. However, inter-object relation modeling has not been well studied for one-stage grounders. Inter-object relationship modeling, though important, is not necessarily performed among all objects, as only part of them are related to the text query and may confuse the model. We call these objects suspected objects. However, exploring their relationships in the one-stage paradigm is non-trivial because: First, no object proposals are available as the basis on which to select suspected objects and perform relationship modeling. Second, suspected objects are more confusing than others, as they may share similar semantics, be entangled with certain relationships, etc, and thereby more easily mislead the model prediction. Toward this end, we propose a Suspected Object Transformation mechanism (SOT), which can be seamlessly integrated into existing CNN and Transformer-based one-stage visual grounders to encourage the target object selection among the suspected ones. Suspected objects are dynamically discovered from a learned activation map adapted to the model current discrimination ability during training. Afterward, on top of suspected objects, a Keyword-Aware Discrimination module (KAD) and an Exploration by Random Connection strategy (ERC) are concurrently proposed to help the model rethink its initial prediction. On the one hand, KAD leverages keywords contributing high to suspected object discrimination. On the other hand, ERC allows the model to seek the correct object instead of being trapped in a situation that always exploits the current false prediction. Extensive experiments demonstrate the effectiveness of our proposed method.
Learning Torque Control for Quadrupedal Locomotion
Venue: arXiv cs.RO 2023
Year: 2023

Reinforcement learning (RL) has become a promising approach to developing controllers for quadrupedal robots. Conventionally, an RL design for locomotion follows a position-based paradigm, wherein an RL policy outputs target joint positions at a low frequency that are then tracked by a high-frequency proportional-derivative (PD) controller to produce joint torques. In contrast, for the model-based control of quadrupedal locomotion, there has been a paradigm shift from position-based control to torque-based control. In light of the recent advances in model-based control, we explore an alternative to the position-based RL paradigm, by introducing a torque-based RL framework, where an RL policy directly predicts joint torques at a high frequency, thus circumventing the use of a PD controller. The proposed learning torque control framework is validated with extensive experiments, in which a quadruped is capable of traversing various terrain and resisting external disturbances while following user-specified commands. Furthermore, compared to learning position control, learning torque control demonstrates the potential to achieve a higher reward and is more robust to significant external disturbances. To our knowledge, this is the first sim-to-real attempt for end-to-end learning torque control of quadrupedal locomotion.
Parameter-Free Attentive Scoring for Speaker Verification
Venue: arXiv cs.SD 2023
Year: 2023

This paper presents a novel study of parameter-free attentive scoring for speaker verification. Parameter-free scoring provides the flexibility of comparing speaker representations without the need of an accompanying parametric scoring model. Inspired by the attention component in Transformer neural networks, we propose a variant of the scaled dot product attention mechanism to compare enrollment and test segment representations. In addition, this work explores the effect on performance of (i) different types of normalization, (ii) independent versus tied query/key estimation, (iii) varying the number of key-value pairs and (iv) pooling multiple enrollment utterance statistics. Experimental results for a 4 task average show that a simple parameter-free attentive scoring mechanism can improve the average EER by 10% over the best cosine similarity baseline.
Adaptive Information Bottleneck Guided Joint Source and Channel Coding for Image Transmission
Venue: arXiv cs.IT 2023
Year: 2023

Joint source and channel coding (JSCC) for image transmission has attracted increasing attention due to its robustness and high efficiency. However, the existing deep JSCC research mainly focuses on minimizing the distortion between the transmitted and received information under a fixed number of available channels. Therefore, the transmitted rate may be far more than its required minimum value. In this paper, an adaptive information bottleneck (IB) guided joint source and channel coding (AIB-JSCC) method is proposed for image transmission. The goal of AIB-JSCC is to reduce the transmission rate while improving the image reconstruction quality. In particular, a new IB objective for image transmission is proposed so as to minimize the distortion and the transmission rate. A mathematically tractable lower bound on the proposed objective is derived, and then, adopted as the loss function of AIB-JSCC. To trade off compression and reconstruction quality, an adaptive algorithm is proposed to adjust the hyperparameter of the proposed loss function dynamically according to the distortion during the training. Experimental results show that AIB-JSCC can significantly reduce the required amount of transmitted data and improve the reconstruction quality and downstream task accuracy.
Lowerbounds for Bisimulation by Partition Refinement
Venue: arXiv cs.LO 2023
Year: 2023

We provide time lower bounds for sequential and parallel algorithms deciding bisimulation on labeled transition systems that use partition refinement. For sequential algorithms this is $Ω((m \mkern1mu {+} \mkern1mu n ) \mkern-1mu \log \mkern-1mu n)$ and for parallel algorithms this is $Ω(n)$, where $n$ is the number of states and $m$ is the number of transitions. The lowerbounds are obtained by analysing families of deterministic transition systems, ultimately with two actions in the sequential case, and one action for parallel algorithms. For deterministic transition systems with one action, bisimilarity can be decided sequentially with fundamentally different techniques than partition refinement. In particular, Paige, Tarjan, and Bonic give a linear algorithm for this specific situation. We show, exploiting the concept of an oracle, that this approach is not of help to develop a faster generic algorithm for deciding bisimilarity. For parallel algorithms there is a similar situation where these techniques may be applied, too.
Characterizing Reddit Participation of Users Who Engage in the QAnon Conspiracy Theories
Venue: arXiv cs.SI 2023
Year: 2023

Widespread conspiracy theories may significantly impact our society. This paper focuses on the QAnon conspiracy theory, a consequential conspiracy theory that started on and disseminated successfully through social media. Our work characterizes how Reddit users who have participated in QAnon-focused subreddits engage in activities on the platform, especially outside their own communities. Using a large-scale Reddit moderation action against QAnon-related activities in 2018 as the source, we identified 13,000 users active in the early QAnon communities. We collected the 2.1 million submissions and 10.8 million comments posted by these users across all of Reddit from October 2016 to January 2021. The majority of these users were only active after the emergence of the QAnon Conspiracy theory and decreased in activity after Reddit's 2018 QAnon ban. A qualitative analysis of a sample of 915 subreddits where the "QAnon-enthusiastic" users were especially active shows that they participated in a diverse range of subreddits, often of unrelated topics to QAnon. However, most of the users' submissions were concentrated in subreddits that have sympathetic attitudes towards the conspiracy theory, characterized by discussions that were pro-Trump, or emphasized unconstricted behavior (often anti-establishment and anti-interventionist). Further study of a sample of 1,571 of these submissions indicates that most consist of links from low-quality sources, bringing potential harm to the broader Reddit community. These results point to the likelihood that the activities of early QAnon users on Reddit were dedicated and committed to the conspiracy, providing implications on both platform moderation design and future research.
Chains, Koch Chains, and Point Sets with many Triangulations
Venue: arXiv cs.CG 2023
Year: 2023

We introduce the abstract notion of a chain, which is a sequence of $n$ points in the plane, ordered by $x$-coordinates, so that the edge between any two consecutive points is unavoidable as far as triangulations are concerned. A general theory of the structural properties of chains is developed, alongside a general understanding of their number of triangulations. We also describe an intriguing new and concrete configuration, which we call the Koch chain due to its similarities to the Koch curve. A specific construction based on Koch chains is then shown to have $Ω(9.08^n)$ triangulations. This is a significant improvement over the previous and long-standing lower bound of $Ω(8.65^n)$ for the maximum number of triangulations of planar point sets.
Animatable Implicit Neural Representations for Creating Realistic Avatars from Videos
Venue: arXiv cs.CV 2023
Year: 2023

This paper addresses the challenge of reconstructing an animatable human model from a multi-view video. Some recent works have proposed to decompose a non-rigidly deforming scene into a canonical neural radiance field and a set of deformation fields that map observation-space points to the canonical space, thereby enabling them to learn the dynamic scene from images. However, they represent the deformation field as translational vector field or SE(3) field, which makes the optimization highly under-constrained. Moreover, these representations cannot be explicitly controlled by input motions. Instead, we introduce a pose-driven deformation field based on the linear blend skinning algorithm, which combines the blend weight field and the 3D human skeleton to produce observation-to-canonical correspondences. Since 3D human skeletons are more observable, they can regularize the learning of the deformation field. Moreover, the pose-driven deformation field can be controlled by input skeletal motions to generate new deformation fields to animate the canonical human model. Experiments show that our approach significantly outperforms recent human modeling methods. The code is available at https://zju3dv.github.io/animatable_nerf/.
FastKASSIM: A Fast Tree Kernel-Based Syntactic Similarity Metric
Venue: arXiv cs.CL 2023
Year: 2023

Syntax is a fundamental component of language, yet few metrics have been employed to capture syntactic similarity or coherence at the utterance- and document-level. The existing standard document-level syntactic similarity metric is computationally expensive and performs inconsistently when faced with syntactically dissimilar documents. To address these challenges, we present FastKASSIM, a metric for utterance- and document-level syntactic similarity which pairs and averages the most similar constituency parse trees between a pair of documents based on tree kernels. FastKASSIM is more robust to syntactic dissimilarities and runs up to to 5.32 times faster than its predecessor over documents in the r/ChangeMyView corpus. FastKASSIM's improvements allow us to examine hypotheses in two settings with large documents. We find that syntactically similar arguments on r/ChangeMyView tend to be more persuasive, and that syntax is predictive of authorship attribution in the Australian High Court Judgment corpus.
Mixed-Precision Neural Network Quantization via Learned Layer-wise Importance
Venue: arXiv cs.LG 2023
Year: 2023

The exponentially large discrete search space in mixed-precision quantization (MPQ) makes it hard to determine the optimal bit-width for each layer. Previous works usually resort to iterative search methods on the training set, which consume hundreds or even thousands of GPU-hours. In this study, we reveal that some unique learnable parameters in quantization, namely the scale factors in the quantizer, can serve as importance indicators of a layer, reflecting the contribution of that layer to the final accuracy at certain bit-widths. These importance indicators naturally perceive the numerical transformation during quantization-aware training, which can precisely provide quantization sensitivity metrics of layers. However, a deep network always contains hundreds of such indicators, and training them one by one would lead to an excessive time cost. To overcome this issue, we propose a joint training scheme that can obtain all indicators at once. It considerably speeds up the indicators training process by parallelizing the original sequential training processes. With these learned importance indicators, we formulate the MPQ search problem as a one-time integer linear programming (ILP) problem. That avoids the iterative search and significantly reduces search time without limiting the bit-width search space. For example, MPQ search on ResNet18 with our indicators takes only 0.06 s, which improves time efficiency exponentially compared to iterative search methods. Also, extensive experiments show our approach can achieve SOTA accuracy on ImageNet for far-ranging models with various constraints (e.g., BitOps, compress rate). Code is available on https://github.com/1hunters/LIMPQ.
Subgame-perfect Equilibria in Mean-payoff Games (journal version)
Venue: arXiv cs.GT 2023
Year: 2023

In this paper, we provide an effective characterization of all the subgame-perfect equilibria in infinite duration games played on finite graphs with mean-payoff objectives. To this end, we introduce the notion of requirement, and the notion of negotiation function. We establish that the plays that are supported by SPEs are exactly those that are consistent with a fixed point of the negotiation function. Finally, we use that characterization to prove that the SPE threshold problem, who status was left open in the literature, is decidable.
An Error-State Model Predictive Control on Connected Matrix Lie Groups for Legged Robot Control
Venue: arXiv cs.RO 2023
Year: 2023

This paper reports on a new error-state Model Predictive Control (MPC) approach to connected matrix Lie groups for robot control. The linearized tracking error dynamics and the linearized equations of motion are derived in the Lie algebra. Moreover, given an initial condition, the linearized tracking error dynamics and equations of motion are globally valid and evolve independently of the system trajectory. By exploiting the symmetry of the problem, the proposed approach shows faster convergence of rotation and position simultaneously than the state-of-the-art geometric variational MPC based on variational-based linearization. Numerical simulation on tracking control of a fully-actuated 3D rigid body dynamics confirms the benefits of the proposed approach compared to the baselines. Furthermore, the proposed MPC is also verified in pose control and locomotion experiments on a quadrupedal robot MIT Mini Cheetah.
Exploring Variational Graph Auto-Encoders for Extract Class Refactoring Recommendation
Venue: arXiv cs.SE 2023
Year: 2023

The code smell is a sign of design and development flaws in a software system that reduces the reusability and maintainability of the system. Refactoring is done as an ongoing practice to remove the code smell from the program code. Among different code smells, the God class or Blob is one of the most common code smells. A god class contains too many responsibilities, violating object-oriented programming design's low coupling and high cohesiveness principles. This paper proposes an automatic approach to extracting a God class into multiple smaller classes with more specific responsibilities. To do this, we first construct a graph of methods (as nodes) for the concerning god class. The edge between any two methods is determined by their structural similarity, and the feature for each method is initialized using different semantic representation methods. Then, the variational graph auto-encoder is used to learn a vector representation for each method. Finally, the learned vectors are used to cluster methods into different groups to be recommended as refactored classes. We assessed the proposed framework using three different class cohesion metrics on sixteen actual God Classes collected from two well-known open-source systems. We also conducted a comparative study of our approach with a similar existing approach and found that the proposed approach generated better results for almost all the God Classes used in the experiment.
Short and local transformations between ($Δ+1$)-colorings
Venue: arXiv cs.DM 2023
Year: 2023

Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring $σ$ to a target coloring $η$. Adding the constraint that each pair of consecutive colorings must differ on exactly one vertex, one asks: Is there a sequence of colorings from $σ$ to $η$? If yes, how short can it be? In this paper, we focus on $(Δ+1)$-colorings of graphs of maximum degree $Δ$. Feghali, Johnson and Paulusma proved that, if both colorings are non-frozen (i.e. we can change the color of a least one vertex), then a quadratic recoloring sequence always exists. We improve their result by proving that there actually exists a linear transformation (assuming that $Δ$ is a constant). In addition, we prove that the core of our algorithm can be performed locally. Informally, this means that after some preprocessing, the color changes that a given node has to perform only depend on the colors of the vertices in a constant size neighborhood. We make this precise by designing of an efficient recoloring algorithm in the LOCAL model of distributed computing.
EVA2.0: Investigating Open-Domain Chinese Dialogue Systems with Large-Scale Pre-Training
Venue: arXiv cs.CL 2023
Year: 2023

Large-scale pre-training has shown remarkable performance in building open-domain dialogue systems. However, previous works mainly focus on showing and evaluating the conversational performance of the released dialogue model, ignoring the discussion of some key factors towards a powerful human-like chatbot, especially in Chinese scenarios. In this paper, we conduct extensive experiments to investigate these under-explored factors, including data quality control, model architecture designs, training approaches, and decoding strategies. We propose EVA2.0, a large-scale pre-trained open-domain Chinese dialogue model with 2.8 billion parameters, and will make our models and codes publicly available. Automatic and human evaluations show that EVA2.0 significantly outperforms other open-source counterparts. We also discuss the limitations of this work by presenting some failure cases and pose some future research directions on large-scale Chinese open-domain dialogue systems.
The Sparse Grids Matlab kit -- a Matlab implementation of sparse grids for high-dimensional function approximation and uncertainty quantification
Venue: arXiv cs.MS 2023
Year: 2023

The Sparse Grids Matlab Kit provides a Matlab implementation of sparse grids, and can be used for approximating high-dimensional functions and, in particular, for surrogate-model-based uncertainty quantification. It is lightweight, high-level and easy to use, good for quick prototyping and teaching; however, it is equipped with some features that allow its use also in realistic applications. The goal of this paper is to provide an overview of the data structure and of the mathematical aspects forming the basis of the software, as well as comparing the current release of our package to similar available software.