OpenRaiser/Intern-Atlas huggingface dataset:
Unified and Dynamic Graph for Temporal Character Grouping in Long Videos
Venue: arXiv cs.CV 2024
Year: 2024

Video temporal character grouping locates appearing moments of major characters within a video according to their identities. To this end, recent works have evolved from unsupervised clustering to graph-based supervised clustering. However, graph methods are built upon the premise of fixed affinity graphs, bringing many inexact connections. Besides, they extract multi-modal features with kinds of models, which are unfriendly to deployment. In this paper, we present a unified and dynamic graph (UniDG) framework for temporal character grouping. This is accomplished firstly by a unified representation network that learns representations of multiple modalities within the same space and still preserves the modality's uniqueness simultaneously. Secondly, we present a dynamic graph clustering where the neighbors of different quantities are dynamically constructed for each node via a cyclic matching strategy, leading to a more reliable affinity graph. Thirdly, a progressive association method is introduced to exploit spatial and temporal contexts among different modalities, allowing multi-modal clustering results to be well fused. As current datasets only provide pre-extracted features, we evaluate our UniDG method on a collected dataset named MTCG, which contains each character's appearing clips of face and body and speaking voice tracks. We also evaluate our key components on existing clustering and retrieval datasets to verify the generalization ability. Experimental results manifest that our method can achieve promising results and outperform several state-of-the-art approaches.
An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
Venue: arXiv cs.DS 2024
Year: 2024

An induced subgraph is called an induced matching if each vertex is a degree-1 vertex in the subgraph. The \textsc{Almost Induced Matching} problem asks whether we can delete at most $k$ vertices from the input graph such that the remaining graph is an induced matching. This paper studies parameterized algorithms for this problem by taking the size $k$ of the deletion set as the parameter. First, we prove a $6k$-vertex kernel for this problem, improving the previous result of $7k$. Second, we give an $O^*(1.6765^k)$-time and polynomial-space algorithm, improving the previous running-time bound of $O^*(1.7485^k)$.
Multidepot Capacitated Vehicle Routing with Improved Approximation Guarantees
Venue: arXiv cs.DS 2024
Year: 2024

The Multidepot Capacitated Vehicle Routing Problem (MCVRP) is a well-known variant of the classic Capacitated Vehicle Routing Problem (CVRP), where we need to route capacitated vehicles located in multiple depots to serve customers' demand such that each vehicle must return to the depot it starts, and the total traveling distance is minimized. There are three variants of MCVRP according to the property of the demand: unit-demand, splittable and unsplittable. We study approximation algorithms for $k$-MCVRP in metric graphs, where $k$ is the capacity of each vehicle. The best-known approximation ratios for the three versions are $4-Θ(1/k)$, $4-Θ(1/k)$, and $4$, respectively. We give a $(4-1/1500)$-approximation algorithm for unit-demand and splittable $k$-MCVRP, and a $(4-1/50000)$-approximation algorithm for unsplittable $k$-MCVRP. When $k$ is a fixed integer, we give a $(3+\ln2-\max\{Θ(1/\sqrt{k}),1/9000\})$-approximation algorithm for the splittable and unit-demand cases, and a $(3+\ln2-Θ(1/\sqrt{k}))$-approximation algorithm for the unsplittable case.
Can GitHub Issues Help in App Review Classifications?
Venue: arXiv cs.SE 2024
Year: 2024

App reviews reflect various user requirements that can aid in planning maintenance tasks. Recently, proposed approaches for automatically classifying user reviews rely on machine learning algorithms. A previous study demonstrated that models trained on existing labeled datasets exhibit poor performance when predicting new ones. Therefore, a comprehensive labeled dataset is essential to train a more precise model. In this paper, we propose a novel approach that assists in augmenting labeled datasets by utilizing information extracted from an additional source, GitHub issues, that contains valuable information about user requirements. First, we identify issues concerning review intentions (bug reports, feature requests, and others) by examining the issue labels. Then, we analyze issue bodies and define 19 language patterns for extracting targeted information. Finally, we augment the manually labeled review dataset with a subset of processed issues through the Within-App, Within-Context, and Between-App Analysis methods. We conducted several experiments to evaluate the proposed approach. Our results demonstrate that using labeled issues for data augmentation can improve the F1-score to 6.3 in bug reports and 7.2 in feature requests. Furthermore, we identify an effective range of 0.3 to 0.7 for the auxiliary volume, which provides better performance improvements.
Entropy-Based Strategies for Multi-Bracket Pools
Venue: arXiv cs.GT 2024
Year: 2024

Much work in the parimutuel betting literature has discussed estimating event outcome probabilities or developing optimal wagering strategies, particularly for horse race betting. Some betting pools, however, involve betting not just on a single event, but on a tuple of events. For example, pick six betting in horse racing, March Madness bracket challenges, and predicting a randomly drawn bitstring each involve making a series of individual forecasts. Although traditional optimal wagering strategies work well when the size of the tuple is very small (e.g., betting on the winner of a horse race), they are intractable for more general betting pools in higher dimensions (e.g., March Madness bracket challenges). Hence we pose the multi-brackets problem: supposing we wish to predict a tuple of events and that we know the true probabilities of each potential outcome of each event, what is the best way to tractably generate a set of $n$ predicted tuples? The most general version of this problem is extremely difficult, so we begin with a simpler setting. In particular, we generate $n$ independent predicted tuples according to a distribution having optimal entropy. This entropy-based approach is tractable, scalable, and performs well.
Geometrically Modulable Gait Design for Quadrupeds
Venue: arXiv cs.RO 2024
Year: 2024

Miniature-legged robots are constrained by their onboard computation and control, thus motivating the need for simple, first-principles-based geometric models that connect \emph{periodic actuation or gaits} (a universal robot control paradigm) to the induced average locomotion. In this paper, we develop a \emph{modulable two-beat gait design framework} for sprawled planar quadrupedal systems under the no-slip using tools from geometric mechanics. We reduce standard two-beat gaits into unique subgaits in mutually exclusive shape subspaces. Subgaits are characterized by a locomotive stance phase when limbs are in ground contact and a non-locomotive, instantaneous swing phase where the limbs are reset without contact. During the stance phase, the contacting limbs form a four-bar mechanism. To analyze the ensuing locomotion, we develop the following tools: (a) a vector field to generate nonslip actuation, (b) the kinematics of a four-bar mechanism as a local connection, and (c) stratified panels that combine the kinematics and constrained actuation to encode the net change in the system's position generated by a stance-swing subgait cycle. Decoupled subgaits are then designed independently using flows on the shape-change basis and are combined with appropriate phasing to produce a two-beat gait. Further, we introduce ``scaling" and ``sliding" control inputs to continuously modulate the global trajectories of the quadrupedal system in gait time through which we demonstrate cycle-average speed, direction, and steering control using the control inputs. Thus, this framework has the potential to create uncomplicated open-loop gait plans or gain schedules for robots with limited resources, bringing them closer to achieving autonomous control.
Mobile Foundation Model as Firmware
Venue: arXiv cs.AI 2024
Year: 2024

In today's landscape, smartphones have evolved into hubs for hosting a multitude of deep learning models aimed at local execution. A key realization driving this work is the notable fragmentation among these models, characterized by varied architectures, operators, and implementations. This fragmentation imposes a significant burden on the comprehensive optimization of hardware, system settings, and algorithms. Buoyed by the recent strides in large foundation models, this work introduces a pioneering paradigm for mobile AI: a collaborative management approach between the mobile OS and hardware, overseeing a foundational model capable of serving a broad spectrum of mobile AI tasks, if not all. This foundational model resides within the NPU and remains impervious to app or OS revisions, akin to firmware. Concurrently, each app contributes a concise, offline fine-tuned "adapter" tailored to distinct downstream tasks. From this concept emerges a concrete instantiation known as \sys. It amalgamates a curated selection of publicly available Large Language Models (LLMs) and facilitates dynamic data flow. This concept's viability is substantiated through the creation of an exhaustive benchmark encompassing 38 mobile AI tasks spanning 50 datasets, including domains such as Computer Vision (CV), Natural Language Processing (NLP), audio, sensing, and multimodal inputs. Spanning this benchmark, \sys unveils its impressive performance. It attains accuracy parity in 85\% of tasks, demonstrates improved scalability in terms of storage and memory, and offers satisfactory inference speed on Commercial Off-The-Shelf (COTS) mobile devices fortified with NPU support. This stands in stark contrast to task-specific models tailored for individual applications.
GADePo: Graph-Assisted Declarative Pooling Transformers for Document-Level Relation Extraction
Venue: arXiv cs.CL 2024
Year: 2024

Document-level relation extraction typically relies on text-based encoders and hand-coded pooling heuristics to aggregate information learned by the encoder. In this paper, we leverage the intrinsic graph processing capabilities of the Transformer model and propose replacing hand-coded pooling methods with new tokens in the input, which are designed to aggregate information via explicit graph relations in the computation of attention weights. We introduce a joint text-graph Transformer model and a graph-assisted declarative pooling (GADePo) specification of the input, which provides explicit and high-level instructions for information aggregation. GADePo allows the pooling process to be guided by domain-specific knowledge or desired outcomes but still learned by the Transformer, leading to more flexible and customisable pooling strategies. We evaluate our method across diverse datasets and models and show that our approach yields promising results that are consistently better than those achieved by the hand-coded pooling functions.
Composition in Differential Privacy for General Granularity Notions (Long Version)
Venue: arXiv cs.CR 2024
Year: 2024

The composition theorems of differential privacy (DP) allow data curators to combine different algorithms to obtain a new algorithm that continues to satisfy DP. However, new granularity notions (i.e., neighborhood definitions), data domains, and composition settings have appeared in the literature that the classical composition theorems do not cover. For instance, the original parallel composition theorem does not translate well to general granularity notions. This complicates the opportunity of composing DP mechanisms in new settings and obtaining accurate estimates of the incurred privacy loss after composition. To overcome these limitations, we study the composability of DP in a general framework and for any kind of data domain or neighborhood definition. We give a general composition theorem in both independent and adaptive versions and we provide analogous composition results for approximate, zero-concentrated, and Gaussian DP. Besides, we study the hypothesis needed to obtain the best composition bounds. Our theorems cover both parallel and sequential composition settings. Importantly, they also cover every setting in between, allowing us to compute the final privacy loss of a composition with greatly improved accuracy.
Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
Venue: arXiv cs.DS 2024
Year: 2024

We present an algorithm for min-cost flow in graphs with $n$ vertices and $m$ edges, given a tree decomposition of width $τ$ and size $S$, and polynomially bounded, integral edge capacities and costs, running in $\widetilde{O}(m\sqrtτ + S)$ time. This improves upon the previous fastest algorithm in this setting achieved by the bounded-treewidth linear program solver by [Dong-Lee-Ye,21] and [Gu-Song,22], which runs in $\widetilde{O}(m τ^{(ω+1)/2})$ time, where $ω\approx 2.37$ is the matrix multiplication exponent. Our approach leverages recent advances in structured linear program solvers and robust interior point methods (IPM). For general graphs where treewidth is trivially bounded by $n$, the algorithm runs in $\widetilde{O}(m \sqrt n)$ time, which is the best-known result without using the Lee-Sidford barrier or $\ell_1$ IPM, demonstrating the surprising power of robust interior point methods. As a corollary, we obtain a $\widetilde{O}(\operatorname{tw}^3 \cdot m)$ time algorithm to compute a tree decomposition of width $O(\operatorname{tw}\cdot \log(n))$, given a graph with $m$ edges.
Improving Generalization in Reinforcement Learning Training Regimes for Social Robot Navigation
Venue: arXiv cs.RO 2024
Year: 2024

In order for autonomous mobile robots to navigate in human spaces, they must abide by our social norms. Reinforcement learning (RL) has emerged as an effective method to train sequential decision-making policies that are able to respect these norms. However, a large portion of existing work in the field conducts both RL training and testing in simplistic environments. This limits the generalization potential of these models to unseen environments, and the meaningfulness of their reported results. We propose a method to improve the generalization performance of RL social navigation methods using curriculum learning. By employing multiple environment types and by modeling pedestrians using multiple dynamics models, we are able to progressively diversify and escalate difficulty in training. Our results show that the use of curriculum learning in training can be used to achieve better generalization performance than previous training methods. We also show that results presented in many existing state-of-the-art RL social navigation works do not evaluate their methods outside of their training environments, and thus do not reflect their policies' failure to adequately generalize to out-of-distribution scenarios. In response, we validate our training approach on larger and more crowded testing environments than those used in training, allowing for more meaningful measurements of model performance.
Uncovering the Hidden Cost of Model Compression
Venue: arXiv cs.LG 2024
Year: 2024

In an age dominated by resource-intensive foundation models, the ability to efficiently adapt to downstream tasks is crucial. Visual Prompting (VP), drawing inspiration from the prompting techniques employed in Large Language Models (LLMs), has emerged as a pivotal method for transfer learning in the realm of computer vision. As the importance of efficiency continues to rise, research into model compression has become indispensable in alleviating the computational burdens associated with training and deploying over-parameterized neural networks. A primary objective in model compression is to develop sparse and/or quantized models capable of matching or even surpassing the performance of their over-parameterized, full-precision counterparts. Although previous studies have explored the effects of model compression on transfer learning, its impact on visual prompting-based transfer remains unclear. This study aims to bridge this gap, shedding light on the fact that model compression detrimentally impacts the performance of visual prompting-based transfer, particularly evident in scenarios with low data volume. Furthermore, our findings underscore the adverse influence of sparsity on the calibration of downstream visual-prompted models. However, intriguingly, we also illustrate that such negative effects on calibration are not present when models are compressed via quantization. This empirical investigation underscores the need for a nuanced understanding beyond mere accuracy in sparse and quantized settings, thereby paving the way for further exploration in Visual Prompting techniques tailored for sparse and quantized models.
Probabilistic Dataset Reconstruction from Interpretable Models
Venue: arXiv cs.AI 2024
Year: 2024

Interpretability is often pointed out as a key requirement for trustworthy machine learning. However, learning and releasing models that are inherently interpretable leaks information regarding the underlying training data. As such disclosure may directly conflict with privacy, a precise quantification of the privacy impact of such breach is a fundamental problem. For instance, previous work have shown that the structure of a decision tree can be leveraged to build a probabilistic reconstruction of its training dataset, with the uncertainty of the reconstruction being a relevant metric for the information leak. In this paper, we propose of a novel framework generalizing these probabilistic reconstructions in the sense that it can handle other forms of interpretable models and more generic types of knowledge. In addition, we demonstrate that under realistic assumptions regarding the interpretable models' structure, the uncertainty of the reconstruction can be computed efficiently. Finally, we illustrate the applicability of our approach on both decision trees and rule lists, by comparing the theoretical information leak associated to either exact or heuristic learning algorithms. Our results suggest that optimal interpretable models are often more compact and leak less information regarding their training data than greedily-built ones, for a given accuracy level.
Lifelike Agility and Play in Quadrupedal Robots using Reinforcement Learning and Generative Pre-trained Models
Venue: arXiv cs.RO 2024
Year: 2024

Knowledge from animals and humans inspires robotic innovations. Numerous efforts have been made to achieve agile locomotion in quadrupedal robots through classical controllers or reinforcement learning approaches. These methods usually rely on physical models or handcrafted rewards to accurately describe the specific system, rather than on a generalized understanding like animals do. Here we propose a hierarchical framework to construct primitive-, environmental- and strategic-level knowledge that are all pre-trainable, reusable and enrichable for legged robots. The primitive module summarizes knowledge from animal motion data, where, inspired by large pre-trained models in language and image understanding, we introduce deep generative models to produce motor control signals stimulating legged robots to act like real animals. Then, we shape various traversing capabilities at a higher level to align with the environment by reusing the primitive module. Finally, a strategic module is trained focusing on complex downstream tasks by reusing the knowledge from previous levels. We apply the trained hierarchical controllers to the MAX robot, a quadrupedal robot developed in-house, to mimic animals, traverse complex obstacles and play in a designed challenging multi-agent chase tag game, where lifelike agility and strategy emerge in the robots.
The Anatomy of Conspirators: Unveiling Traits using a Comprehensive Twitter Dataset
Venue: arXiv cs.SI 2024
Year: 2024

The discourse around conspiracy theories is currently thriving amidst the rampant misinformation in online environments. Research in this field has been focused on detecting conspiracy theories on social media, often relying on limited datasets. In this study, we present a novel methodology for constructing a Twitter dataset that encompasses accounts engaged in conspiracy-related activities throughout the year 2022. Our approach centers on data collection that is independent of specific conspiracy theories and information operations. Additionally, our dataset includes a control group comprising randomly selected users who can be fairly compared to the individuals involved in conspiracy activities. This comprehensive collection effort yielded a total of 15K accounts and 37M tweets extracted from their timelines. We conduct a comparative analysis of the two groups across three dimensions: topics, profiles, and behavioral characteristics. The results indicate that conspiracy and control users exhibit similarity in terms of their profile metadata characteristics. However, they diverge significantly in terms of behavior and activity, particularly regarding the discussed topics, the terminology used, and their stance on trending subjects. In addition, we find no significant disparity in the presence of bot users between the two groups. Finally, we develop a classifier to identify conspiracy users using features borrowed from bot, troll and linguistic literature. The results demonstrate a high accuracy level (with an F1 score of 0.94), enabling us to uncover the most discriminating features associated with conspiracy-related accounts.
Rotation Augmented Distillation for Exemplar-Free Class Incremental Learning with Detailed Analysis
Venue: arXiv cs.CV 2024
Year: 2024

Class incremental learning (CIL) aims to recognize both the old and new classes along the increment tasks. Deep neural networks in CIL suffer from catastrophic forgetting and some approaches rely on saving exemplars from previous tasks, known as the exemplar-based setting, to alleviate this problem. On the contrary, this paper focuses on the Exemplar-Free setting with no old class sample preserved. Balancing the plasticity and stability in deep feature learning with only supervision from new classes is more challenging. Most existing Exemplar-Free CIL methods report the overall performance only and lack further analysis. In this work, different methods are examined with complementary metrics in greater detail. Moreover, we propose a simple CIL method, Rotation Augmented Distillation (RAD), which achieves one of the top-tier performances under the Exemplar-Free setting. Detailed analysis shows our RAD benefits from the superior balance between plasticity and stability. Finally, more challenging exemplar-free settings with fewer initial classes are undertaken for further demonstrations and comparisons among the state-of-the-art methods.