OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic Recourse with Missing Values
Venue: arXiv cs.LG 2024
Year: 2024

This paper proposes a new framework of algorithmic recourse (AR) that works even in the presence of missing values. AR aims to provide a recourse action for altering the undesired prediction result given by a classifier. Existing AR methods assume that we can access complete information on the features of an input instance. However, we often encounter missing values in a given instance (e.g., due to privacy concerns), and previous studies have not discussed such a practical situation. In this paper, we first empirically and theoretically show the risk that a naive approach with a single imputation technique fails to obtain good actions regarding their validity, cost, and features to be changed. To alleviate this risk, we formulate the task of obtaining a valid and low-cost action for a given incomplete instance by incorporating the idea of multiple imputation. Then, we provide some theoretical analyses of our task and propose a practical solution based on mixed-integer linear optimization. Experimental results demonstrated the efficacy of our method in the presence of missing values compared to the baselines.
ChatGPT Evaluation on Sentence Level Relations: A Focus on Temporal, Causal, and Discourse Relations
Venue: arXiv cs.CL 2024
Year: 2024

This paper aims to quantitatively evaluate the performance of ChatGPT, an interactive large language model, on inter-sentential relations such as temporal relations, causal relations, and discourse relations. Given ChatGPT's promising performance across various tasks, we proceed to carry out thorough evaluations on the whole test sets of 11 datasets, including temporal and causal relations, PDTB2.0-based, and dialogue-based discourse relations. To ensure the reliability of our findings, we employ three tailored prompt templates for each task, including the zero-shot prompt template, zero-shot prompt engineering (PE) template, and in-context learning (ICL) prompt template, to establish the initial baseline scores for all popular sentence-pair relation classification tasks for the first time. Through our study, we discover that ChatGPT exhibits exceptional proficiency in detecting and reasoning about causal relations, albeit it may not possess the same level of expertise in identifying the temporal order between two events. While it is capable of identifying the majority of discourse relations with existing explicit discourse connectives, the implicit discourse relation remains a formidable challenge. Concurrently, ChatGPT demonstrates subpar performance in the dialogue discourse parsing task that requires structural understanding in a dialogue before being aware of the discourse relation.
Kullback-Leibler Maillard Sampling for Multi-armed Bandits with Bounded Rewards
Venue: arXiv cs.LG 2024
Year: 2024

We study $K$-armed bandit problems where the reward distributions of the arms are all supported on the $[0,1]$ interval. It has been a challenge to design regret-efficient randomized exploration algorithms in this setting. Maillard sampling \cite{maillard13apprentissage}, an attractive alternative to Thompson sampling, has recently been shown to achieve competitive regret guarantees in the sub-Gaussian reward setting \cite{bian2022maillard} while maintaining closed-form action probabilities, which is useful for offline policy evaluation. In this work, we propose the Kullback-Leibler Maillard Sampling (KL-MS) algorithm, a natural extension of Maillard sampling for achieving KL-style gap-dependent regret bound. We show that KL-MS enjoys the asymptotic optimality when the rewards are Bernoulli and has a worst-case regret bound of the form $O(\sqrt{μ^*(1-μ^*) K T \ln K} + K \ln T)$, where $μ^*$ is the expected reward of the optimal arm, and $T$ is the time horizon length.
Using Large Language Models to Generate JUnit Tests: An Empirical Study
Venue: arXiv cs.SE 2024
Year: 2024

A code generation model generates code by taking a prompt from a code comment, existing code, or a combination of both. Although code generation models (e.g., GitHub Copilot) are increasingly being adopted in practice, it is unclear whether they can successfully be used for unit test generation without fine-tuning for a strongly typed language like Java. To fill this gap, we investigated how well three models (Codex, GPT-3.5-Turbo, and StarCoder) can generate unit tests. We used two benchmarks (HumanEval and Evosuite SF110) to investigate the effect of context generation on the unit test generation process. We evaluated the models based on compilation rates, test correctness, test coverage, and test smells. We found that the Codex model achieved above 80% coverage for the HumanEval dataset, but no model had more than 2% coverage for the EvoSuite SF110 benchmark. The generated tests also suffered from test smells, such as Duplicated Asserts and Empty Tests.
Learning Self-Prior for Mesh Inpainting Using Self-Supervised Graph Convolutional Networks
Venue: arXiv cs.CV 2024
Year: 2024

In this paper, we present a self-prior-based mesh inpainting framework that requires only an incomplete mesh as input, without the need for any training datasets. Additionally, our method maintains the polygonal mesh format throughout the inpainting process without converting the shape format to an intermediate one, such as a voxel grid, a point cloud, or an implicit function, which are typically considered easier for deep neural networks to process. To achieve this goal, we introduce two graph convolutional networks (GCNs): single-resolution GCN (SGCN) and multi-resolution GCN (MGCN), both trained in a self-supervised manner. Our approach refines a watertight mesh obtained from the initial hole filling to generate a complete output mesh. Specifically, we train the GCNs to deform an oversmoothed version of the input mesh into the expected complete shape. The deformation is described by vertex displacements, and the GCNs are supervised to obtain accurate displacements at vertices in real holes. To this end, we specify several connected regions of the mesh as fake holes, thereby generating meshes with various sets of fake holes. The correct displacements of vertices are known in these fake holes, thus enabling training GCNs with loss functions that assess the accuracy of vertex displacements. We demonstrate that our method outperforms traditional dataset-independent approaches and exhibits greater robustness compared with other deep-learning-based methods for shapes that infrequently appear in shape datasets. Our code and test data are available at https://github.com/astaka-pe/SeMIGCN.
Strategic Resource Selection with Homophilic Agents
Venue: arXiv cs.GT 2024
Year: 2024

The strategic selection of resources by selfish agents is a classic research direction, with Resource Selection Games and Congestion Games as prominent examples. In these games, agents select available resources and their utility then depends on the number of agents using the same resources. This implies that there is no distinction between the agents, i.e., they are anonymous. We depart from this very general setting by proposing Resource Selection Games with heterogeneous agents that strive for joint resource usage with similar agents. So, instead of the number of other users of a given resource, our model considers agents with different types and the decisive feature is the fraction of same-type agents among the users. More precisely, similarly to Schelling Games, there is a tolerance threshold $τ\in [0,1]$ which specifies the agents' desired minimum fraction of same-type agents on a resource. Agents strive to select resources where at least a $τ$-fraction of those resources' users have the same type as themselves. For $τ=1$, our model generalizes Hedonic Diversity Games with a peak at $1$. For our general model, we consider the existence and quality of equilibria and the complexity of maximizing social welfare. Additionally, we consider a bounded rationality model, where agents can only estimate the utility of a resource, since they only know the fraction of same-type agents on a given resource, but not the exact numbers. Thus, they cannot know the impact a strategy change would have on a target resource. Interestingly, we show that this type of bounded rationality yields favorable game-theoretic properties and specific equilibria closely approximate equilibria of the full knowledge setting.
Key-Locked Rank One Editing for Text-to-Image Personalization
Venue: arXiv cs.CV 2024
Year: 2024

Text-to-image models (T2I) offer a new level of flexibility by allowing users to guide the creative process through natural language. However, personalizing these models to align with user-provided visual concepts remains a challenging problem. The task of T2I personalization poses multiple hard challenges, such as maintaining high visual fidelity while allowing creative control, combining multiple personalized concepts in a single image, and keeping a small model size. We present Perfusion, a T2I personalization method that addresses these challenges using dynamic rank-1 updates to the underlying T2I model. Perfusion avoids overfitting by introducing a new mechanism that "locks" new concepts' cross-attention Keys to their superordinate category. Additionally, we develop a gated rank-1 approach that enables us to control the influence of a learned concept during inference time and to combine multiple concepts. This allows runtime-efficient balancing of visual-fidelity and textual-alignment with a single 100KB trained model, which is five orders of magnitude smaller than the current state of the art. Moreover, it can span different operating points across the Pareto front without additional training. Finally, we show that Perfusion outperforms strong baselines in both qualitative and quantitative terms. Importantly, key-locking leads to novel results compared to traditional approaches, allowing to portray personalized object interactions in unprecedented ways, even in one-shot settings.
Autonomous search of real-life environments combining dynamical system-based path planning and unsupervised learning
Venue: arXiv cs.RO 2024
Year: 2024

In recent years, advancements have been made towards the goal of using chaotic coverage path planners for autonomous search and traversal of spaces with limited environmental cues. However, the state of this field is still in its infancy as there has been little experimental work done. The existing experimental works have not developed robust methods to satisfactorily address the immediate set of problems a chaotic coverage path planner needs to overcome in order to scan realistic environments within reasonable coverage times. These immediate problems are as follows: (1) an obstacle avoidance technique that reduces halts or disruptions in continuous chaotic trajectories, (2) a means to spread chaotic trajectories across the environment (especially crucial for large and/or complex-shaped environments) that need to be covered, and (3) a real-time coverage calculation technique that is accurate and independent of cell size. This study addresses these problems by developing a novel applied framework for real-world applications of chaotic coverage path planners while providing techniques for effective obstacle avoidance, chaotic trajectory dispersal, and accurate real-time coverage calculation. These algorithms were created within the ROS framework and make up a newly developed chaotic path planning application. The performance of this application was comparable to that of a conventional optimal path planner. The performance tests were carried out in environments of various sizes, shapes, and obstacle densities, both in real-life and Gazebo simulations.
Where We Have Arrived in Proving the Emergence of Sparse Symbolic Concepts in AI Models
Venue: arXiv cs.LG 2024
Year: 2024

This study aims to prove the emergence of symbolic concepts (or more precisely, sparse primitive inference patterns) in well-trained deep neural networks (DNNs). Specifically, we prove the following three conditions for the emergence. (i) The high-order derivatives of the network output with respect to the input variables are all zero. (ii) The DNN can be used on occluded samples and when the input sample is less occluded, the DNN will yield higher confidence. (iii) The confidence of the DNN does not significantly degrade on occluded samples. These conditions are quite common, and we prove that under these conditions, the DNN will only encode a relatively small number of sparse interactions between input variables. Moreover, we can consider such interactions as symbolic primitive inference patterns encoded by a DNN, because we show that inference scores of the DNN on an exponentially large number of randomly masked samples can always be well mimicked by numerical effects of just a few interactions.
MaskSearch: Querying Image Masks at Scale
Venue: arXiv cs.DB 2024
Year: 2024

Machine learning tasks over image databases often generate masks that annotate image content (e.g., saliency maps, segmentation maps, depth maps) and enable a variety of applications (e.g., determine if a model is learning spurious correlations or if an image was maliciously modified to mislead a model). While queries that retrieve examples based on mask properties are valuable to practitioners, existing systems do not support them efficiently. In this paper, we formalize the problem and propose MaskSearch, a system that focuses on accelerating queries over databases of image masks while guaranteeing the correctness of query results. MaskSearch leverages a novel indexing technique and an efficient filter-verification query execution framework. Experiments with our prototype show that MaskSearch, using indexes approximately 5% of the compressed data size, accelerates individual queries by up to two orders of magnitude and consistently outperforms existing methods on various multi-query workloads that simulate dataset exploration and analysis processes.
Personalized Abstractive Summarization by Tri-agent Generation Pipeline
Venue: arXiv cs.CL 2024
Year: 2024

Tailoring outputs from large language models, like ChatGPT, to implicit user preferences remains a challenge despite their impressive generative capabilities. In this paper, we propose a tri-agent generation pipeline comprising a generator, an instructor, and an editor to enhance output personalization. The generator produces an initial output, the instructor automatically generates editing instructions based on user preferences, and the editor refines the output to align with those preferences. The inference-only large language model (ChatGPT) serves as both the generator and editor, with a smaller model acting as the instructor to guide output generation. We train the instructor using editor-steered reinforcement learning, leveraging feedback from a large-scale editor model to optimize instruction generation. Experimental results on two abstractive summarization datasets demonstrate the effectiveness of our approach in generating outputs that better meet user expectations. Code is available at \url{https://github.com/Wendy-Xiao/chatgpt_editing_summ}
A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate Functions
Venue: arXiv cs.IT 2024
Year: 2024

The Blahut-Arimoto (BA) algorithm has played a fundamental role in the numerical computation of rate-distortion (RD) functions. This algorithm possesses a desirable monotonic convergence property by alternatively minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a novel modification of the BA algorithm, wherein the multiplier is updated through a one-dimensional root-finding step using a monotonic univariate function, efficiently implemented by Newton's method in each iteration. Consequently, the modified algorithm directly computes the RD function for a given target distortion, without exploring the entire RD curve as in the original BA algorithm. Moreover, this modification presents a versatile framework, applicable to a wide range of problems, including the computation of distortion-rate (DR) functions. Theoretical analysis shows that the outputs of the modified algorithms still converge to the solutions of the RD and DR functions with rate $O(1/n)$, where $n$ is the number of iterations. Additionally, these algorithms provide $\varepsilon$-approximation solutions with $O\left(\frac{MN\log N}{\varepsilon}(1+\log |\log \varepsilon|)\right)$ arithmetic operations, where $M,N$ are the sizes of source and reproduced alphabets respectively. Numerical experiments demonstrate that the modified algorithms exhibit significant acceleration compared with the original BA algorithms and showcase commendable performance across classical source distributions such as discretized Gaussian, Laplacian and uniform sources.
A QoS-Aware Uplink Spectrum and Power Allocation with Link Adaptation for Vehicular Communications in 5G networks
Venue: arXiv cs.NI 2024
Year: 2024

In this work, we have proposed link adaptation-based joint spectrum and power allocation algorithms for the uplink communication in 5G Cellular Vehicle-to-Everything (C-V2X) systems. In C-V2X, vehicle-to-vehicle (V2V) users share radio resources with vehicle-to-infrastructure (V2I) users. Existing works primarily focus on the optimal pairing of V2V and V2I users, assuming that each V2I user needs a single resource block (RB) while minimizing interference through power allocation. In contrast, in this work, we have considered that the number of RBs needed by the users is a function of their channel condition and Quality of Service (QoS) - a method called link adaptation. It effectively compensates for the frequent channel quality fluctuations at the high frequencies of 5G communication.5G uses a multi-numerology frame structure to support diverse QoS requirements, which has also been considered in this work. The first algorithm proposed in this article greedily allocates RBs to V2I users using link adaptation. It then uses the Hungarian algorithm to pair V2V with V2I users while minimizing interference through power allocation. The second proposed method groups RBs into resource chunks (RCs) and uses the Hungarian algorithm twice - first to allocate RCs to V2I users and then to pair V2I users with V2V users. Extensive simulations reveal that link adaptation increases the number of satisfied V2I users and their sum rate while also improving the QoS of V2I and V2V users, making it indispensable for 5G C-V2X systems.
Explainable Reinforcement Learning via a Causal World Model
Venue: arXiv cs.LG 2024
Year: 2024

Generating explanations for reinforcement learning (RL) is challenging as actions may produce long-term effects on the future. In this paper, we develop a novel framework for explainable RL by learning a causal world model without prior knowledge of the causal structure of the environment. The model captures the influence of actions, allowing us to interpret the long-term effects of actions through causal chains, which present how actions influence environmental variables and finally lead to rewards. Different from most explanatory models which suffer from low accuracy, our model remains accurate while improving explainability, making it applicable in model-based learning. As a result, we demonstrate that our causal model can serve as the bridge between explainability and learning.
Closure and Decision Properties for Higher-Dimensional Automata
Venue: arXiv cs.FL 2024
Year: 2024

We report some further developments regarding the language theory of higher-dimensional automata (HDAs). Regular languages of HDAs are sets of finite interval partially ordered multisets (pomsets) with interfaces. We show a pumping lemma which allows us to expose a class of non-regular languages. Concerning decision and closure properties, we show that inclusion of regular languages is decidable (hence is emptiness), and that intersections of regular languages are again regular. On the other hand, complements of regular languages are not always regular. We introduce a width-bounded complement and show that width-bounded complements of regular languages are again regular. We also study determinism and ambiguity. We show that it is decidable whether a regular language is accepted by a deterministic HDA and that there exists regular languages with unbounded ambiguity. Finally, we characterize one-letter deterministic languages in terms of utlimately periodic functions.
Incentivising the federation: gradient-based metrics for data selection and valuation in private decentralised training
Venue: arXiv cs.LG 2024
Year: 2024

Obtaining high-quality data for collaborative training of machine learning models can be a challenging task due to A) regulatory concerns and B) a lack of data owner incentives to participate. The first issue can be addressed through the combination of distributed machine learning techniques (e.g. federated learning) and privacy enhancing technologies (PET), such as the differentially private (DP) model training. The second challenge can be addressed by rewarding the participants for giving access to data which is beneficial to the training model, which is of particular importance in federated settings, where the data is unevenly distributed. However, DP noise can adversely affect the underrepresented and the atypical (yet often informative) data samples, making it difficult to assess their usefulness. In this work, we investigate how to leverage gradient information to permit the participants of private training settings to select the data most beneficial for the jointly trained model. We assess two such methods, namely variance of gradients (VoG) and the privacy loss-input susceptibility score (PLIS). We show that these techniques can provide the federated clients with tools for principled data selection even in stricter privacy settings.
Confidence-Based Skill Reproduction Through Perturbation Analysis
Venue: arXiv cs.RO 2024
Year: 2024

Several methods exist for teaching robots, with one of the most prominent being Learning from Demonstration (LfD). Many LfD representations can be formulated as constrained optimization problems. We propose a novel convex formulation of the LfD problem represented as elastic maps, which models reproductions as a series of connected springs. Relying on the properties of strong duality and perturbation analysis of the constrained optimization problem, we create a confidence metric. Our method allows the demonstrated skill to be reproduced with varying confidence level yielding different levels of smoothness and flexibility. Our confidence-based method provides reproductions of the skill that perform better for a given set of constraints. By analyzing the constraints, our method can also remove unnecessary constraints. We validate our approach using several simulated and real-world experiments using a Jaco2 7DOF manipulator arm.
Phase Transitions of the Price-of-Anarchy Function in Multi-Commodity Routing Games
Venue: arXiv cs.GT 2024
Year: 2024

We consider the behavior of the price of anarchy and equilibrium flows in nonatomic multi-commodity routing games as a function of the traffic demand. We analyze their smoothness with a special attention to specific values of the demand at which the support of the Wardrop equilibrium exhibits a phase transition with an abrupt change in the set of optimal routes. Typically, when such a phase transition occurs, the price of anarchy function has a breakpoint, \ie is not differentiable. We prove that, if the demand varies proportionally across all commodities, then, at a breakpoint, the largest left or right derivatives of the price of anarchy and of the social cost at equilibrium, are associated with the smaller equilibrium support. This proves -- under the assumption of proportional demand -- a conjecture of O'Hare et al. (2016), who observed this behavior in simulations. We also provide counterexamples showing that this monotonicity of the one-sided derivatives may fail when the demand does not vary proportionally, even if it moves along a straight line not passing through the origin.