bluuebunny/crossref_metadata_2025 huggingface dataset:
Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flows
Authors: Hoang Nu , Duong Bao , Nguyen Thin
Published: October 2024

Post-nonlinear (PNL) causal models stand out as a versatile and adaptable framework for modeling intricate causal relationships. However, accurately capturing the invertibility constraint required in PNL models remains challenging in existing studies. To address this problem, we introduce CAF-PoNo (Causal discovery via Normalizing Flows for Post-Nonlinear models), harnessing the power of the normalizing flows architecture to enforce the crucial invertibility constraint in PNL models. Through normalizing flows, our method precisely reconstructs the hidden noise, which plays a vital role in cause-effect identification through statistical independence testing. Furthermore, the proposed approach exhibits remarkable extensibility, as it can be seamlessly expanded to facilitate multivariate causal discovery via causal order identification, empowering us to efficiently unravel complex causal relationships. Extensive experimental evaluations on both simulated and real datasets consistently demonstrate that the proposed method outperforms several state-of-the-art approaches in both bivariate and multivariate causal discovery tasks.
Deep Mapper: Efficient Visualization of Plausible Conformational Pathways
Authors: Oulhaj Ziyad , Ishii Yoshiyuki , Ohga Kento , Yamazaki Kimihiro , Wada Mutsuyo , Umeda Yuhei , Katoh Takashi , Wada Yuichiro , Kurihara Hiroaki
Published: October 2024

Acquiring plausible pathways on high-dimensional structural distributions is beneficial in several domains. For example, in the drug discovery field, a protein conformational pathway, i.e. a highly probable sequence of protein structural changes, is useful to analyze interactions between the protein and the ligands, helping to create new drugs. Recently, a state-of-the-art method in drug discovery was presented, which efficiently computes protein pathways using latent variables obtained from an isometric auto-encoding of the space of 3D density maps associated to protein conformations. However, our preliminary experiments show that there is room to significantly reduce the computing time. In this study, we use the Mapper algorithm, which is a Topological Data Analysis method, and present a novel variant to extract plausible conformational pathways from the isometric latent space with comparatively short running time. The extracted pathways are visualized as paths on the resulting Mapper graph. The methodological novelties are described as follows: firstly, the filter function of the Mapper algorithm is optimized so as to extract the pathways via minimization of an energy loss defined on the Mapper graph itself, while filter functions taken in the classical Mapper algorithm are fixed beforehand. The optimization is with respect to parameters of a deep neural network in the filter. Secondly, the clustering method, which defines the vertices and edges of the Mapper graph, of our algorithm is designed by incorporating domain prior knowledge to assist the extraction. In our numerical experiments, based on an isometric latent space built on the common 50S-ribosomal dataset, the resulting Mapper graph successfully includes all the well-recognized plausible pathways. Moreover, our running time is much shorter than the above state-of-the-art counterpart.
Reasonable Gradients for Online Training Algorithms in Spiking Neural Networks
Authors: Xue Lang , Liu HanWen , Wang Jing , Qu Hong
Published: October 2024

Spiking neural networks (SNNs) have the potential to simulate sparse and spatio-temporal dynamics observed in biological neurons, making them promising for achieving energy-efficient artificial general intelligence. While backpropagation through time (BPTT) ensures reliable precision for training SNNs, it is hampered by high computation and storage complexity and does not conform to the instantaneous learning mechanism in brains. On the contrary, online training algorithms, which are biologically interpretable, offer low latency and memory efficiency, and are well-suited for on-chip learning applications. However, recent research exhibit a deficiency in the scientific comprehension of online gradients, which leads to certain limitations. To address this issue, we conduct an in-depth analysis of the calculation deviation in chain derivations induced by weight update and find two pivotal factors that affect the accuracy of online gradients: completeness and timeliness. To further enhance the performance of online training leveraging these findings, we propose spatio-temporal online learning (STOL), which substantially ameliorates the accuracy of the online gradients and demonstrates superior computation and memory efficiency. Our experiments on CIFAR-10, CIFAR-100, ImageNet, CIFAR10-DVS, and DVS128-Gesture datasets demonstrate that our method achieves state-of-the-art performance across most of these tasks. Besides, it shows a great improvement compared with existing online training algorithms.
Prompt-Based Data Augmentation Using Contrastive Learning Under Scarcity of Annotated Data
Authors: Ul Haq Muhammad Uzair , Rigoni Davide , Sperduti Alessandro
Published: October 2024

Named Entity Recognition is a crucial task in Natural Language Processing (NLP) which aims to identify the entities in text. Given an adequate amount of annotated data, Large Language Models (LLMs) have been shown to be effective in this task when fine-tuned. However, the performance of LLMs is severely affected when annotated datasets are limited. To alleviate this problem, adding synthetic data via Data Augmentation (DA) techniques is a viable approach. Even so, DA for token-level tasks suffers from two main limitations: (i) token-label misalignment problem; and (ii) quality of generated synthetic data. In this paper, we propose a novel prompt-based DA approach using contrastive learning. The proposed method can generate high-quality synthetic data while preserving the token-label correspondences. Experimental results demonstrate that the proposed approach, when compared against multiple baselines on well-known Named Entity Recognition (NER) datasets, achieves State-of-the-Art performance.
Augmented Prediction of a True Class for Positive Unlabeled Data Under Selection Bias
Authors: Mielniczuk Jan , Wawrzeńczyk Adam
Published: October 2024

We introduce a new observational setting for Positive Unlabeled (PU) data where the observations at prediction time are also labeled. This occurs commonly in practice – we argue that the additional information is important for prediction, and call this task “augmented PU prediction”. We allow for labeling to be feature dependent. In such scenario, Bayes classifier and its risk is established and compared with a risk of a classifier which for unlabeled data is based only on predictors. We introduce several variants of the empirical Bayes rule in such scenario and investigate their performance. We put a special focus on dangers (and ease) of applying classical classification rule in the augmented PU scenario – due to no preexisting studies, an unaware researcher is prone to skewing the obtained predictions. We conclude that the variant based on recently proposed variational autoencoder designed for PU scenario works on par or better than other considered variants and yields advantage over feature-only based methods in terms of accuracy for unlabeled samples.
Learning in Multi-Objective Public Goods Games with Non-Linear Utilities
Authors: Orzan Nicole , Acar Erman , Grossi Davide , Mannion Patrick , Rădulescu Roxana
Published: October 2024

Addressing the question of how to achieve optimal decision-making under risk and uncertainty is crucial for enhancing the capabilities of artificial agents that collaborate with or support humans. In this work, we address this question in the context of Public Goods Games. We study learning in a novel multi-objective version of the Public Goods Game where agents have different risk preferences, by means of multi-objective reinforcement learning. We introduce a parametric non-linear utility function to model risk preferences at the level of individual agents, over the collective and individual reward components of the game. We study the interplay between such preference modelling and environmental uncertainty on the incentive alignment level in the game. We demonstrate how different combinations of individual preferences and environmental uncertainty sustain the emergence of cooperative patterns in non-cooperative environments (i.e., where competitive strategies are dominant), while others sustain competitive patterns in cooperative environments (i.e., where cooperative strategies are dominant).
DeCoRTAD: Diffusion Based Conditional Representation Learning for Online Trajectory Anomaly Detection
Authors: Wang Chen , Erfani Sarah , Alpcan Tansu , Leckie Christopher
Published: October 2024

Online trajectory anomaly detection has become a critical task in many real-world applications. However, most existing works assume anomalies are significantly different from normal patterns or require knowing the destinations in advance. In this work, we focus on the problem of detecting anomalous subtrajectories in an online manner without knowing their destinations. This task presents a significant challenge as anomalous subtrajectories may largely overlap with normal trajectories, and we only have limited information on an ongoing trajectory during online detection. To overcome the limitations of current methods, we propose a novel diffusion-based conditional representation learning for online trajectory anomaly detection (DeCoRTAD), that aims to detect anomalies at the representation level, thereby improving computational efficiency. Our framework integrates a diffusion model with two encoders: one for capturing current information and another for encoding historical context. By conditioning the current encoder on the history encoder, we leverage past information as prior knowledge to achieve a more meaningful and compact latent space representation. Our method excels in capturing the normal representation in highly diverse trajectory data, therefore achieving great performance in online detection of fine-grained anomalies. Our experiments show that DeCoRTAD can achieve outstanding online anomaly detection performance in F1 score with an average improvement of 9.31%, and a maximum improvement of 22% over comparable baselines.
Mask-Encoded Sparsification: Mitigating Biased Gradients in Communication-Efficient Split Learning
Authors: Zhou Wenxuan , Qu Zhihao , Lyu Shen-Huan , Cai Miao , Ye Baoliu
Published: October 2024

This paper introduces a novel framework designed to achieve a high compression ratio in Split Learning (SL) scenarios where resource-constrained devices are involved in large-scale model training. Our investigations demonstrate that compressing feature maps within SL leads to biased gradients that can negatively impact the convergence rates and diminish the generalization capabilities of the resulting models. Our theoretical analysis provides insights into how compression errors critically hinder SL performance, which previous methodologies underestimate. To address these challenges, we employ a narrow bit-width encoded mask to compensate for the sparsification error without increasing the order of time complexity. Supported by rigorous theoretical analysis, our framework significantly reduces compression errors and accelerates the convergence. Extensive experiments also verify that our method outperforms existing solutions regarding training efficiency and communication complexity. Our code can be found at https://github.com/BinaryMus/MaskSparsification.
A Meta-Learning Approach for Multi-Objective Reinforcement Learning in Sustainable Home Energy Management
Authors: Lu Junlin , Mannion Patrick , Mason Karl
Published: October 2024

Effective residential appliance scheduling is crucial for sustainable living. While multi-objective reinforcement learning (MORL) has proven effective in balancing user preferences in appliance scheduling, traditional MORL struggles with limited data in non-stationary residential settings characterized by renewable generation variations. Significant context shifts in the environment can invalidate previously learned policies. To address this, we extend state-of-the-art MORL algorithms with the meta-learning paradigm, enabling rapid, few-shot adaptation to shifting contexts. Additionally, we employ an auto-encoder (AE)-based unsupervised method to detect shifts in environmental context. We have also developed a residential energy environment to evaluate our method using real-world data from London residential settings. This study not only assesses the application of MORL in residential appliance scheduling but also underscores the effectiveness of meta-learning in energy management. Our top-performing method significantly surpasses the best baseline, while the trained model saves 3.28% on electricity bills, a 2.74% increase in user comfort, and a 5.9% improvement in expected utility. Additionally, it reduces the sparsity of solutions by 62.44%. Remarkably, these gains were accomplished using 96.71% less training data and 61.1% fewer training steps.
Cascade Memory for Unsupervised Anomaly Detection
Authors: Li Jiahao , Chen Yiqiang , Xing Yunbing , Gu Yang , Lan Xiangyuan
Published: October 2024

Unsupervised anomaly detection is to detect previously unseen rare samples without any prior knowledge about them. With the emergence of deep learning, many methods employ normal data reconstruction to train detection models, which is expected to yield relatively large errors when reconstructing anomalies. However, recent studies find that anomalies can be overgeneralized, resulting in reconstruction errors as small as normal samples. In this paper, we examine the anomaly overgeneralization problem and propose global semantic information learning. Normal and anomalous samples may share the same local feature such as textures, edges, and corners, but have separability at the global semantic level. To address this, we propose a novel cascade memory architecture designed to capture global semantic information in the latent space and introduce a configurable sparsification and random forgetting mechanism. Our proposed method achieves state-of-the-art experimental results on different public benchmarks, without the introduction of any additional auxiliary loss terms. The code is available at https://github.com/LiJiahao-Alex/Cascade-Memory.
Federated Learning with Hybrid Knowledge Distillations on Long-Tailed Heterogeneous Client Data
Authors: Liu Senbin , Zhang Yuanting , Zhang Kunhua , Wang Yi
Published: October 2024

Federated learning (FL) has a great potential in large-scale machine learning applications by training a global model over distributed client data. However, FL deployed in real-world applications often incur collaboration bias and unstable convergence with inconsistent local predictions, resulting in poor modelling performance on heterogeneous and long-tailed client data distributions. In this paper, we reconsider heterogeneous FL in a two-stage learning paradigm where representation learning and classifier re-training are separated to incorporate different sampling schemes. This allows us to deal with the dilemma of obtaining more generalizable features and fine tuning a biased classifier building on client model aggregations. Specifically, we propose a novel hybrid knowledge distillation scheme, called FedHyb, to facilitate the two-stage learning. From the view of knowledge transfer, we show that FedHyb enables several desirable properties in the global feature space and optimization with fine-tuning, thus achieving better test accuracy and convergence speed, especially with a higher level of data heterogeneity and an increasing number of distributed clients. FedHyb does not require any information exchange between clients preventing privacy leakage, and is more robust under poisoning attacks comparing with other FL methods designed on heterogeneous data.
Natural Mitigation of Catastrophic Interference: Continual Learning in Power-Law Learning Environments
Authors: Atith Gandhi  , Shah Raj Sanjay , Vijay Marupudi  , Varma Sashank
Published: October 2024

Neural networks often suffer from catastrophic interference (CI): performance on previously learned tasks drops off significantly when learning a new task. This contrasts strongly with humans, who can continually learn new tasks without appreciably forgetting previous tasks. Prior work has explored various techniques for mitigating CI and promoting continual learning such as regularization, rehearsal, generative replay, and context-specific components. This paper takes a different approach, one guided by cognitive science research showing that in naturalistic environments, the probability of encountering a task decreases as a power-law of the time since it was last performed. We argue that techniques for mitigating CI should be compared against the intrinsic mitigation in simulated naturalistic learning environments. Thus, we evaluate the extent of the natural mitigation of CI when training models in power-law environments, similar to those humans face. Our results show that natural rehearsal environments are better at mitigating CI than existing methods, calling for the need for better evaluation processes. The benefits of this environment include simplicity, rehearsal that is agnostic to both tasks and models, and the lack of a need for extra neural circuitry. In addition, we explore popular mitigation techniques in power-law environments to create new baselines for continual learning research.
MCAHNN: Multi-Channel EEG Emotion Recognition Using Attention Mechanism Based on Householder Reflection
Authors: Liu Qinglong , Jiang Wenhao , Ding Shihang , Wang Kaixuan , Bo Hongjian , Xu Cong , Ma Lin , Li Haifeng
Published: October 2024

Emotions are integral to human cognition, exerting a profound influence on physiological responses, cognitive processes, and decision-making capabilities. Electroencephalography (EEG)-based emotion classification provides a significant methodological approach for the exploration of emotional states. Despite its potential, most current methodologies face challenges in delineating the representational patterns across different brain regions and in effectively classifying emotions from EEG signals. In response, a novel model for emotion recognition is proposed in this paper, which utilizes a multi-channel attention mechanism, designated as MCAHNN. This model incorporates Householder Reflection to enhance the attention mechanism, facilitating the extraction of inter-channel EEG features and simulating inter-regional brain dynamics. Furthermore, 1D convolution is employed to analyze intra-channel relationships. The proposed model has been evaluated on the publicly available DEAP dataset and further tested on the SEED dataset. Experimental results confirm that the MCAHNN model achieves state-of-the-art performance, demonstrating its effectiveness in classifying emotions within multi-center datasets.Code is publicly available at https://github.com/Oreoreoreor/MCAHNN.
Navigating Trade-offs: Policy Summarization for Multi-Objective Reinforcement Learning
Authors: Osika Zuzanna , Zatarain-Salazar Jazmin , Oliehoek Frans A. , Murukannaiah Pradeep K.
Published: October 2024

Multi-objective reinforcement learning (MORL) is used to solve problems involving multiple objectives. An MORL agent must make decisions based on the diverse signals provided by distinct reward functions. Training an MORL agent yields a set of solutions (policies), each presenting distinct trade-offs among the objectives (expected returns). MORL enhances explainability by enabling fine-grained comparisons of policies in the solution set based on their trade-offs as opposed to having a single policy. However, the solution set is typically large and multi-dimensional, where each policy (e.g., a neural network) is represented by its objective values. We propose an approach for clustering the solution set generated by MORL. By considering both policy behavior and objective values, our clustering method can reveal the relationship between policy behaviors and regions in the objective space. This approach can enable decision makers (DMs) to identify overarching trends and insights in the solution set rather than examining each policy individually. We tested our method in four multi-objective environments and found it outperformed traditional k-medoids clustering. Additionally, we include a case study that demonstrates its real-world application.
GraphFSA: A Finite State Automaton Framework for Algorithmic Learning on Graphs
Authors: Grötschla Florian , Mathys Joël , Raun Christoffer , Wattenhofer Roger
Published: October 2024

Many graph algorithms can be viewed as sets of rules that are iteratively applied, with the number of iterations dependent on the size and complexity of the input graph. Existing machine learning architectures often struggle to represent these algorithmic decisions as discrete state transitions. Therefore, we propose a novel framework: GraphFSA (Graph Finite State Automaton). GraphFSA is designed to learn a finite state automaton that runs on each node of a given graph. We test GraphFSA on cellular automata problems, showcasing its abilities in a straightforward algorithmic setting. For a comprehensive empirical evaluation of our framework, we create a diverse range of synthetic problems. As our main application, we then focus on learning more elaborate graph algorithms. Our findings suggest that GraphFSA exhibits strong generalization and extrapolation abilities, presenting an alternative approach to represent these algorithms.
VMFTransformer: An Angle-Preserving and Auto-Scaling Machine for Multi-Horizon Probabilistic Forecasting
Authors: Zhou Yunyi , Gao Ruohan , Zheng Xinping , Huang Yuchen , Chu Zhixuan
Published: October 2024

As deep learning develops, the major research methodologies of time series forecasting can be divided into two categories, i.e., iterative and direct methods. In the iterative methods, since a small amount of error is produced at each time step, the recursive structure can potentially lead to large error accumulations over longer forecasting horizons. Although the direct methods can avoid this puzzle involved in the iterative methods, they face abuse of conditional independence among time points. This impractical assumption can also lead to biased models. To solve these challenges, we propose a direct approach for multi-horizon probabilistic forecasting, which can effectively characterize the dependence across future horizons. Specifically, we consider the multi-horizon target as a random vector. The direction of the vector embodies the temporal dependence, and the length of the vector measures the overall scale across each horizon. Therefore, we respectively apply the von Mises-Fisher (VMF) distribution and the truncated normal distribution to characterize the target vector’s angle and magnitude in our model. Extensive results demonstrate the superiority of our framework over eight state-of-the-art methods.
Diversifying the Mixture-of-Experts Representation for Language Models with Orthogonal Optimizer
Authors: Liu Boan , Ding Liang , Shen Li , Peng Keqin , Cao Yu , Cheng Dazhao , Tao Dacheng
Published: October 2024

The Mixture of Experts (MoE) has emerged as a highly successful technique in deep learning, based on the principle of divide-and-conquer to maximize model capacity without significant additional computational cost. Even in the era of large-scale language models (LLMs), MoE continues to play a crucial role, as some researchers have indicated that GPT-4 adopts the MoE structure to ensure diverse inference results. However, MoE is susceptible to performance degeneracy, particularly evident in the issues of imbalance and homogeneous representation among experts. While previous studies have extensively addressed the problem of imbalance, the challenge of homogeneous representation remains unresolved. In this study, we shed light on the homogeneous representation problem, wherein experts in the MoE fail to specialize and lack diversity, leading to frustratingly high similarities in their representations (up to 99% in a well-performed MoE model). This problem restricts the expressive power of the MoE and, we argue, contradicts its original intention. To tackle this issue, we propose a straightforward yet highly effective solution: OMoE, an orthogonal expert optimizer. Additionally, we introduce an alternating training strategy that encourages each expert to update in a direction orthogonal to the subspace spanned by other experts. Our algorithm facilitates MoE training in two key ways: firstly, it explicitly enhances representation diversity, and secondly, it implicitly fosters interaction between experts during orthogonal weights computation. Through extensive experiments, we demonstrate that our proposed optimization algorithm significantly improves the performance of fine-tuning the MoE model on the GLUE benchmark, SuperGLUE benchmark, question-answering task, and name entity recognition tasks.
RETRO-LI: Small-Scale Retrieval Augmented Generation Supporting Noisy Similarity Searches and Domain Shift Generalization
Authors: Rashiti Gentiana , Karunaratne Geethan , Sachan Mrinmaya , Sebastian Abu , Rahimi Abbas
Published: October 2024

The retrieval augmented generation (RAG) system such as RETRO has been shown to improve language modeling capabilities and reduce toxicity and hallucinations by retrieving from a database of non-parametric memory containing trillions of entries. We introduce RETRO-LI that shows retrieval can also help using a small scale database, but it demands more accurate and better neighbors when searching in a smaller hence sparser non-parametric memory. This can be met by using a proper semantic similarity search. We further propose adding a regularization to the non-parametric memory for the first time: it significantly reduces perplexity when the neighbor search operations are noisy during inference, and it improves generalization when a domain shift occurs. We also show that the RETRO-LI’s non-parametric memory can potentially be implemented on analog in-memory computing hardware, exhibiting O(1) search time while causing noise in retrieving neighbors, with minimal (<1%) performance loss. Our code is available at: https://github.com/IBM/Retrieval-Enhanced-Transformer-Little
Taylor Expansion in Neural Networks: How Higher Orders Yield Better Predictions
Authors: Zwerschke Pavel , Weyrauch Arvid , Götz Markus , Debus Charlotte
Published: October 2024

Deep learning has become a popular tool for solving complex problems in a variety of domains. Transformers and the attention mechanism have contributed a lot to this success. We hypothesize that the enhanced predictive capabilities of the attention mechanism can be attributed to higher-order terms in the input. Expanding on this idea and taking inspiration from Taylor Series approximation, we introduce “Taylor layers” as higher order polynomial layers for universal function approximation. We evaluate Taylor layers of second and third order on the task of time series forecasting, comparing them to classical linear layers as well as the attention mechanism. Our results on two commonly used datasets demonstrate that higher expansion orders can improve prediction accuracy given the same amount of trainable model weights. Interpreting higher-order terms as a form of token mixing, we further show that second order (quadratic) Taylor layers can efficiently replace canonical dot-product attention, increasing prediction accuracy while reducing computational requirements.
High-Dimensional Causal Bayesian Optimization
Authors: Wu Yupeng , Wang Weiye , Zhang Yangwenhui , Li Mingjia , Liu Yuanhao , Qian Hong , Zhou Aimin
Published: October 2024

Causal global optimization (CGO) aims to complete optimization tasks through causal inference. In the high-dimensional CGO problems, traditional causal Bayesian optimization (CBO) methods struggle with the curse of dimensionality attributed to the number of variables in the causal graph, and scale inconsistency among Gaussian Process (GP) models. These issues limit the application of CBO in domains requiring optimization over large causal graphs. To address these limitations, this paper proposes a high-dimensional causal Bayesian optimization (HCBO) algorithm. To address the curse of dimensionality, HCBO introduces a submodularity indicator for variable subsets through the concept of causal intrinsic dimensionality (CID). It then uses the submodular optimization algorithm to find approximations of CID within polynomial sample complexity. Theoretically, we disclose a sufficient condition for CID’s existence. To address the issue of scale inconsistency among GP models, HCBO introduces a scale-normalized scoring function, ensuring stable identification of the optimal GP model corresponding to CID for intervention. Extensive experiments are conducted on high-dimensional synthetic and real-world tasks, i.e., coral ecology and health. The existence of CID is verified across the datasets of all tasks. HCBO achieves state-of-the-art performance in CGO problems and can handle causal graphs at a scale 10 times larger than that manageable by previous CBO methods.
Reset It and Forget It: Relearning Last-Layer Weights Improves Continual and Transfer Learning
Authors: Frati Lapo , Traft Neil , Clune Jeff , Cheney Nick
Published: October 2024

This work identifies a simple pre-training mechanism that leads to representations exhibiting better continual and transfer learning. This mechanism—the repeated resetting of weights in the last layer, which we nickname “zapping”—was originally designed for a meta-continual-learning procedure, yet we show it is surprisingly applicable in many settings beyond both meta-learning and continual learning. In our experiments, we wish to transfer a pre-trained image classifier to a new set of classes, in few shots. We show that our zapping procedure results in improved transfer accuracy and/or more rapid adaptation in both standard fine-tuning and continual learning settings, while being simple to implement and computationally efficient. In many cases, we achieve performance on par with state of the art meta-learning without needing the expensive higher-order gradients by using a combination of zapping and sequential learning. An intuitive explanation for the effectiveness of this zapping procedure is that representations trained with repeated zapping learn features that are capable of rapidly adapting to newly initialized classifiers. Such an approach may be considered a computationally cheaper type of, or alternative to, meta-learning rapidly adaptable features with higher-order gradients. This adds to recent work on the usefulness of resetting neural network parameters during training, and invites further investigation of this mechanism.
NeurCAM: Interpretable Neural Clustering via Additive Models
Authors: Upadhya Nakul , Cohen Eldan
Published: October 2024

Interpretable clustering algorithms aim to group similar data points while explaining the obtained groups to support knowledge discovery and pattern recognition tasks. While most approaches to interpretable clustering construct clusters using decision trees, the interpretability of trees often deteriorates on complex problems where large trees are required. In this work, we introduce the Neural Clustering Additive Model (NeurCAM), a novel approach to the interpretable clustering problem that leverages neural generalized additive models to provide fuzzy cluster membership with additive explanations of the obtained clusters. To promote sparsity in our model’s explanations, we introduce selection gates that explicitly limit the number of features and pairwise interactions leveraged. Additionally, we demonstrate the capacity of our model to perform text clustering that considers the contextual representation of the texts while providing explanations for the obtained clusters based on uni- or bi-word terms. Extensive experiments show that NeurCAM achieves performance comparable to black-box methods on tabular datasets while remaining interpretable. Additionally, our approach significantly outperforms other interpretable clustering approaches when clustering on text data.
An Axiomatic Perspective on Anomaly Detection
Authors: Wyke Chester , Urner Ruth
Published: October 2024

A major challenge for both theoretical treatment and practical application of unsupervised learning tasks such as clustering, anomaly detection or generative modeling, is the inherent lack of quantifiable objectives. Choosing methods and evaluating outcomes is then often a matter of ad-hoc heuristics or personal taste. Anomaly detection is often employed as a preprocessing step to other learning tasks, and unsound decisions for this task may thus have long reaching consequences. In this work, we propose an axiomatic framework for analyzing behaviours of anomaly detection methods. We propose a basic set of desirable properties (or axioms) for distance-based anomaly detection methods and identify dependencies and (in-)consistencies between subsets of these. We then demonstrate the benefits of this axiomatic perspective on behaviors of anomaly detection methods by illustrating empirically how some commonly employed algorithms violate, perhaps unexpectedly, a basic desirable property.
Is Contrasting All You Need? Contrastive Learning for the Detection and Attribution of AI-generated Text
Authors: La Cava Lucio , Costa Davide , Tagarelli Andrea
Published: October 2024

The significant progress in the development of Large Language Models has contributed to blurring the distinction between human and AI-generated text. The increasing pervasiveness of AI-generated text and the difficulty in detecting it poses new challenges for our society. In this paper, we tackle the problem of detecting and attributing AI-generated text by proposing WhosAI, a triplet-network contrastive learning framework designed to predict whether a given input text has been generated by humans or AI and to unveil the authorship of the text. Unlike most existing approaches, our proposed framework is conceived to learn semantic similarity representations from multiple generators at once, thus equally handling both detection and attribution tasks. Furthermore, WhosAI is model-agnostic and scalable to the release of new AI text-generation models by incorporating their generated instances into the embedding space learned by our framework. Experimental results on the TuringBench benchmark of 200K news articles show that our proposed framework achieves outstanding results in both the Turing Test and Authorship Attribution tasks, outperforming all the methods listed in the TuringBench benchmark leaderboards.
Rejection in Abstract Argumentation: Harder Than Acceptance?
Authors: Fichte Johannes K. , Hecher Markus , Mahmood Yasir , Meier Arne
Published: October 2024

Abstract argumentation is a popular toolkit for modeling, evaluating, and comparing arguments. Relationships between arguments are specified in argumentation frameworks (AFs), and conditions are placed on sets (extensions) of arguments that allow AFs to be evaluated. For more expressiveness, AFs are augmented with acceptance conditions on directly interacting arguments or a constraint on the admissible sets of arguments, resulting in dialectic frameworks or constrained argumentation frameworks. In this paper, we consider flexible conditions for rejecting an argument from an extension, which we call rejection conditions (RCs). On the technical level, we associate each argument with a specific logic program. We analyze the resulting complexity, including the structural parameter treewidth. Rejection AFs are highly expressive, giving rise to natural problems on higher levels of the polynomial hierarchy.
Escape Sensing Games: Detection-vs-Evasion in Security Applications
Authors: Boehmer Niclas , Han Minbiao , Xu Haifeng , Tambe Milind
Published: October 2024

Traditional game-theoretic research for security applications primarily focuses on the allocation of external protection resources to defend targets. This work puts forward the study of a new class of games centered around strategically arranging targets to protect them against a constrained adversary, with motivations from varied domains such as peacekeeping resource transit and cybersecurity. Specifically, we introduce Escape Sensing Games (ESGs). In ESGs, a blue player manages the order in which targets pass through a channel, while her opponent tries to capture the targets using a set of sensors that need some time to recharge after each activation. We present a thorough computational study of ESGs. Among others, we show that it is NP-hard to compute best responses and equilibria. Nevertheless, we propose a variety of effective (heuristic) algorithms whose quality we demonstrate in extensive computational experiments.
Characterising Serialisation Equivalence for Abstract Argumentation
Authors: Bengel Lars , Sander Julian , Thimm Matthias
Published: October 2024

We introduce the notion of serialisation equivalence, which provides a notion of equivalence that takes the underlying dialectical structure of extensions in an argumentation framework into account. Under this notion, two argumentation frameworks are considered equivalent if they possess not only the same extensions wrt. some semantics but also the same serialisation sequences. A serialisation sequence is a decomposition of an extension into a series of minimal acceptable sets and essentially offers insight into the order in which arguments need to brought forward to resolve the conflicts and to justify a particular position in the argumentation framework. We analyse serialisation equivalence in detail and show that it is generally more strict than standard equivalence and less strict than strong equivalence. Furthermore, we provide a full analysis of the computational complexity of deciding serialisation equivalence.
On Connected Strongly-Proportional Cake-Cutting
Authors: Jankó Zsuzsanna , Joó Attila , Segal-Halevi Erel , Yuen Sheung Man
Published: October 2024

We investigate the problem of fairly dividing a divisible heterogeneous resource, also known as a cake, among a set of agents who may have different entitlements. We characterize the existence of a connected strongly-proportional allocation—one in which every agent receives a contiguous piece worth strictly more than their proportional share. The characterization is supplemented with an algorithm that determines its existence using O(n·2n) queries. We devise a simpler characterization for agents with strictly positive valuations and with equal entitlements, and present an algorithm to determine the existence of such an allocation using O(n2) queries. We provide matching lower bounds in the number of queries for both algorithms. When a connected strongly-proportional allocation exists, we show that it can also be computed using a similar number of queries. The full version is available at https://arxiv.org/abs/2312.15326.
Learning and Optimizing with an SSB Representation of Intransitive Preferences on Sets
Authors: Gilbert Hugo , Ouaguenouni Mohamed , Spanjaard Olivier
Published: October 2024

We propose a Skew-Symmetric Bilinear (SSB) model to represent intransitive preferences on subsets of a ground set of items. More precisely, the SSB model accounts for preference intensities between pairs of subsets. We provide a procedure to learn the parameters of the SSB model from a set of known pairwise preferences between subsets, managing to find a sparse model, and as simple as possible in terms of the degree of interaction between items. The SSB model can be viewed as a concise representation of a weighted tournament on subsets. We study the complexity of determining the winners according to various tournament rules. Numerical tests on synthetic and real-world data are carried out.
The Complexity of Manipulation of k-Coalitional Games on Graphs
Authors: Barr Hodaya , Trabelsi Yohai , Kraus Sarit , Roditty Liam , Hazon Noam
Published: October 2024

In many settings, there is an organizer who would like to divide a set of agents into k coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such k-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.
Selfishly Cancelling Debts Can Reduce Systemic Risk
Authors: Tong Jinyun , De Keijzer Bart , Ventre Carmine
Published: October 2024

The exposure of banks to systemic risk in financial networks usually requires large bailouts of taxpayer money with long-lasting and damaging societal consequences. We examine whether the banking network can reduce systemic risk from within by selfishly cancelling the debts of banks in distress. This operation can in principle reduce losses and prevent default cascades. We define an abstract model to simulate the ensuing strategic game on randomly generated financial networks, where each systemically important bank independently decides how likely it is to cancel some debts of insolvent banks. We compute the equilibrium of the induced empirical game with the empirical game-theoretic analysis and analyse its efficiency by measuring the price of anarchy. Our results show that selfish debt cancellation can reduce systemic risk when adopting the equilibrium strategy profile. However, our results also indicate that the efficiency of the equilibrium can be low and relatively few banks cancel debts at equilibrium, and we explain the reason for this through analysis of the banks’ incentives and game dynamics.
Compromises in Dialogical Argumentation: Aggregated Policies for Biparty Decision Theory
Authors: Donadello Ivan , Lirio de Souza Renan , Hunter Anthony , Dragoni Mauro
Published: October 2024

Automated persuasion systems (APS) are conversational agents that exchange arguments and counterarguments with users during dialogues to persuade them to believe in something. Such systems use strategies (or policies) to carefully select a sequence of arguments that are tailored to the user’s needs and will likely have a positive outcome, that is, changing the user’s belief in a certain argument. Biparty Decision Theory (BDT) is a framework that uses game theory to formalize a dialogue between an APS and a user, that is, an exchange of (counter) arguments during each turn of the APS or the user. During the APS turn, the BDT policy selects the best argument to maximize only the utility for the APS and neglects the utility of that argument for the user. This is a reasonable choice in games, but in a persuasive dialogue, it can result in arguments that have a high utility for the APS but a modest utility for the user. There the user may be less likely to be persuaded. This is crucial in settings where there are no arguments with good utilities for both the APS and the user and a compromise has to be found. To this extent, we define a new family of policies for BDT, called aggregated policies, that consider, during the decisions of the APS, an aggregation of the APS and user’s utilities. Such an aggregation considers both the APS and the user’s needs leading toward a sequence of arguments representing the best trade-off of utilities. We evaluate the approach using both a new synthetic dataset and a published dataset of utilities for dialogical argumentation. The results show the aggregated policies find better compromise arguments w.r.t. the classical policy of BDT.
Worst- and Average-Case Robustness of Stable Matchings: (Counting) Complexity and Experiments
Authors: Boehmer Kimon , Boehmer Niclas
Published: October 2024

Focusing on the bipartite Stable Marriage problem, we investigate different robustness measures related to stable matchings. We analyze the computational complexity of computing them and analyze their behavior in extensive experiments on synthetic instances. For instance, we examine whether a stable matching is guaranteed to remain stable if a given number of adversarial swaps in the agent’s preferences are performed and the probability of stability when applying swaps uniformly at random. Our results reveal that stable matchings in our synthetic data are highly unrobust to adversarial swaps, whereas the average-case view presents a more nuanced and informative picture.
Optimal Diffusion Auctions
Authors: Zhang Yao , Zheng Shanshan , Zhao Dengji
Published: October 2024

Diffusion auction design is a new trend in mechanism design for which the main goal is to incentivize existing buyers to invite new buyers, who are their neighbors on a social network, to join an auction even though they are competitors. With more buyers, a diffusion auction will be able to give a more efficient allocation and receive higher revenue. Existing studies have proposed many interesting diffusion auctions to attract more buyers, but the seller’s revenue is not optimized. Hence, in this study, we investigate what optimal revenue the seller can achieve by attracting more buyers. Different from the traditional setting, the revenue that can be achieved in a diffusion auction highly relies on the structure of the network. Hence, we focus on optimal auctions with given classes of underlying networks. We propose a class of mechanisms, where for any given structure, an optimal diffusion mechanism can be found. We point out that it implies an idea of “reserve structure”. Moreover, we show that an optimal mechanism that handles all structures does not exist. Therefore, we also propose mechanisms that have bounded approximations of the optimal revenue in all structures.
Approximate Mechanism Design for Facility Location with Multiple Objectives
Authors: Walsh Toby
Published: October 2024

We identify strategy proof mechanisms for facility location that simultaneously approximate well both the maximum distance from the nearest facility and the minimum utility of any agent. Somewhat surprisingly, while the deterministic MEDIAN and the randomized ENDORAV mechanisms perform optimally with respect to approximating the maximum distance, neither perform optimally with respect to approximating the minimum utility. With deterministic mechanisms for locating a single facility, we prove that the MIDORNEAREST mechanism is optimal with respect to approximating both the maximum distance and the minimum utility. By comparison, the MEDIAN mechanism has an unbounded approximation ratio for approximating the minimum utility. With randomized mechanisms for locating a single facility, we construct the first mechanism that is optimal with respect to approximating the minimum utility. For deterministic and randomized mechanisms locating two or more facilities, we identify strategy proof mechanisms that are within a constant factor of optimal with respect to both objectives.