United States

In this paper, we augment online algorithms for the knapsack problem using the total weight information. The conventional optimal online algorithm achieves the $\ln (\frac{U}{L})+1$ competitive ratio where $L$ and $U$ are the upper and lower bounds of the value-to-weight ratio. However, it does not consider that decision makers can know the total weight information or obtain it through machine-learned predictions. To fill this gap, we first propose the Known Weight Algorithm (KWA) which uses the exact total weight information to achieve a competitive ratio of $\mathcal{W}(\frac{1}{e}\frac{U-L}{L})+1$, where $\mathcal{W}$ denotes the Lambert-W function. We prove that it is optimal and tight. After that, we extend KWA to the Predicted Weight Algorithm (PWA), a learning-augmented online algorithm that uses predicted total weight. We show the consistency and robustness of PWA, and prove that its competitive ratio degrades gracefully as the prediction error grows. Finally, we introduce the Limited Volume Algorithm (LWA), which achieves a better competitive ratio than $\ln \frac{U}{L}+1$ when the total weight is less than twice the capacity.

AAAI 2025

Augmenting Online Algorithms for Knapsack Problem with Total Weight Information

planning under uncertainty

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

AAMAS 2021

technical paper

We are pleased to announce the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25), which will be held in Philadelphia, Pennsylvania at the Pennsylvania Convention Center from February 25 to March 4, 2025.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

### [Invited Speakers](https://aaai.org/conference/aaai/aaai-25/aaai-25-invited-speakers/)

Register [here](https://aaai.org/conference/aaai/aaai-25/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-25 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.



Recent advancements in proactive dialogues have garnered significant attention, particularly for more complex objectives (e.g. emotion support and persuasion). Unlike traditional task-oriented dialogues, proactive dialogues demand advanced policy planning and adaptability, requiring rich scenarios and comprehensive policy repositories to develop such systems. However, existing approaches tend to rely on Large Language Models (LLMs) for user simulation and online learning, leading to biases that diverge from realistic scenarios and result in suboptimal efficiency. Moreover, these methods depend on manually defined, context-independent, coarse-grained policies, which not only incur high expert costs but also raise concerns regarding their completeness. In our work, we highlight the potential for automatically discovering policies directly from raw, real-world dialogue records. To this end, we introduce a novel dialogue policy planning framework, LDPP. It fully automates the process from mining policies in dialogue records to learning policy planning. Specifically, we employ a variant of the Variational Autoencoder to discover fine-grained policies represented as latent vectors. After automatically annotating the data with these latent policy labels, we propose an Offline Hierarchical Reinforcement Learning (RL) algorithm in the latent space to develop effective policy planning capabilities. Our experiments demonstrate that LDPP outperforms existing methods on two proactive scenarios, even surpassing ChatGPT with only a 1.8-billion-parameter LLM. Our codes are available at xxx.

Simulation-Free Hierarchical Latent Policy Planning for Proactive Dialogues

Image-goal navigation aims to steer an agent toward goal location specified by an image. Most prior methods tackle this task by learning a navigation policy, which extracts visual representation of goal and observation images, compares their similarity and predicts actions. However, if the agent is in different rooms or has large pose variation from the goal image, it is extremely challenging to identify their similarity, which may result in the agent wandering around. Intuitively, when humans carry out this task, they may first roughly compare the current observation with the goal image, having an approximate concept of whether they are in the same room. Inspired by this intuition, we try to imitate the human behaviour and propose a Room Expert Guided Image-Goal Navigation model (REGNav) to equip the agent with the ability of analyzing whether goal and observation images are taken in the same room. Specifically, we first pre-train a room expert with unsupervised learning technique on the self-collected unlabelled room images. The expert, composed of room style embedding network and room relation network, can extract the room style representation of image pairs and obtain their relationship about whether they belong to the same room. Two different fusion approaches are explored to efficiently guide the agent navigation with the room relation knowledge. As a result, our proposed REGNav can successfully navigate to the goal location in a more efficient way. Extensive experiments show that our REGNav surpasses prior state-of-the-art works on three popular benchmarks (e.g., Gibson, MP3D, and HM3D).

REGNav: Room Expert Guided Image-Goal Navigation

This paper studies continual learning (CL) of text classification tasks with a pre-trained language model (LM). In particular, it focuses on the class incremental learning (CIL) setting of CL. Many CIL methods have been proposed to leverage an LM via various types of fine-tuning or adaptation, but they are still prone to catastrophic forgetting (CF). This paper proposes a novel method, called Kernel Linear Discriminant Analysis (KLDA).  It only exploits the latent feature representations extracted from an LM for CIL. However, directly using LM features is sub-optimal. KLDA employs the Radial Basis Function (RBF) kernel to enhance the features from the LM to capture non-linear relationships in the features, resulting in improved accuracy. As the kernel matrix is impractical to build for CIL due to its huge size and the incremental learning nature of CIL, we approximate it using Random Fourier Features (RFF). When a new task arrives, KLDA computes the class mean of each class in the task and updates a shared covariance matrix for all classes learned so far based on the kernelized features. Linear Discriminant Analysis is employed for classification. Our experiments show that KLDA significantly outperforms existing methods. Remarkably, it achieves an accuracy level comparable to that of joint training all classes together, which is considered the upper bound for CIL performance, without using any replay data.

Continual Learning Using a Kernel-Based Method Over Foundation Models

Functional Magnetic Resonance Image (fMRI) is commonly employed to study human brain activity, since it offers insight into the relationship between functional fluctuations and human behavior. To enhance analysis and comprehension of brain activity, Graph Neural Networks (GNNs) have been widely applied to the analysis of functional connectivities (FC) derived from fMRI data, due to their ability to capture the synergistic interactions among brain regions. However, in the human brain, performing complex tasks typically involves the activation of certain \textit{pathways}, which could be represented as paths across graphs. As such, conventional GNNs struggle to learn from these pathways due to the long-range dependencies of multiple pathways. To address these challenges, we introduce a novel framework \textbf{BrainMAP} to learn multiple pathways in brain networks. BrainMAP leverages sequential models to identify long-range correlations among sequentialized brain regions and incorporates an aggregation module based on Mixture of Experts (MoE) to learn from multiple pathways. Our comprehensive experiments highlight BrainMAP's superior performance. Furthermore, our framework enables explanatory analyses of crucial brain regions involved in tasks.

BrainMAP: Learning Multiple Activation Pathways in Brain Networks

To understand a document with multiple events, event-event relation extraction (ERE) emerges as a crucial task, aiming to discern how natural events temporally or structurally associate with each other. To achieve this goal, our work addresses the problems of temporal event relation extraction (TRE) and subevent relation extraction (SRE). The latest methods for such problems have commonly built document-level event graphs for global reasoning across sentences. However, the edges between events are usually derived from external tools heuristically, which are not always reliable and may introduce noise. Moreover, they are not capable of preserving logical constraints among event relations, e.g., coreference constraint, symmetry constraint and conjunction constraint. These constraints guarantee coherence between different relation types, enabling the generation of a uniffed event evolution graph. In this work, we propose a novel method named LogicERE, which performs high-order event relation reasoning through modeling logic constraints. Speciffcally, different from conventional event graphs, we design a logic constraint induced graph (LCG) without any external tools. LCG involves event nodes where the interactions among them can model the coreference constraint, and event pairs nodes where the interactions among them can retain the symmetry constraint and transitivity constraint. Then we perform high-order reasoning on LCG with relational graph transformer to obtain enhanced event and event pair embeddings. Finally, we further incorporate logic constraint information via a joint logic learning module. Extensive experiments demonstrate the effectiveness of the proposed method with state-of-the-art performance on benchmark datasets.

Logic Induced High-Order Reasoning Network for Event-Event Relation Extraction

Large language models (LLMs) have revolutionized numerous fields of research, driving significant advancements in natural language processing, machine translation, and beyond. Although the extensive number of parameters contributes a lot to the great success, existing studies indicate that not all model parameters hold equal importance, which further leads to redundancy during the parameter update process. Recent works for reducing redundant parameter updates for LLMs either lack task-specific data information, may leading to suboptimal model performance, or discard transformer components or insignificant parameters, limiting the model's scalability across different tasks and potentially compromising the LLM structure. To address these issues and further enhance the performance of LLMs, we propose Gradient-Mask Tuning (GMT), a method that selectively updates parameters based on gradient information, which is specific to the target tasks. Specifically, after calculating gradients during back propagation, we measure their absolute values and mask those with small absolute values. Our empirical results in various training paradigms like SFT and DPO for various domains of tasks demonstrate that GMT not only preserves the original network structure but also enhances the potential performance of LLMs. Further analysis indicates that GMT exhibits insensitivity to mask ratio and possesses computational efficiency comparable to vanilla training approach.

Enhancing Large Language Model Performance with Gradient-Based Parameter Selection

Multi-view clustering (MVC) for remote sensing data is a critical and challenging task in Earth observation. Although recent advances in graph neural network (GNN)-based MVC have shown remarkable success, the most prevalent approaches have two major limitations: 1) heavily relying on a predefined yet fixed graph, which limits the performance of clustering because the large number of indistinguishable background samples contained in remote sensing data would introduce noise information and increase struct heterogeneity; 2) ignoring the effect of confusing samples on cluster structure compactness, which leads to fluffy cluster structure and decrease feature discriminability. To address these issues, we propose a Structure-Adaptive Multi-View Graph Clustering method named SAMVGC on remote sensing data which boosts the structure homogeneity and cluster compactness by adaptively learning the graph and cluster structures, respectively. Concretely, we use the geometric structure within the feature embedding space to refine adjacency matrices. The adjacency matrices are dynamically fused with the previous ones to improve the homogeneity and stability of structure information. Additionally, the samples are separated into two categories, including the central (intra-cluster center samples) and the confusing (inter-cluster boundary samples). On the basis, we deploy the contrastive learning paradigm on the central samples within views and the consistent learning paradigm on the confusing samples between views, improving the cluster compactness and consistency. Finally, we conduct extensive experiments on four benchmarks and achieve promising results, well demonstrating the effectiveness and superiority of the proposed method.

Structure-Adaptive Multi-View Graph Clustering for Remote Sensing Data

Backdoor attacks pose a significant threat during the model's training phase. Attackers craft pre-defined triggers to break deep neural networks, ensuring the model accurately classifies clean samples during inference yet erroneously classifies samples added with these triggers. Recent studies have shown that speaker recognition systems trained on large-scale data are susceptible to backdoor attacks. Existing attackers employ unnoticed ambient sounds as triggers. However, these sounds are not inherently part of the training samples themselves. In essence, triggers can be designed to maintain an intrinsic connection with the original speech to enhance stealthiness. Our paper presents a novel attack methodology named Speed Master, which undermines deep neural networks by manipulating the speed of speech samples. Specifically, we execute poison-only backdoor attacks using direct or tempo speed adjustment. In real-world scenarios, individuals have the autonomy to adjust their speaking rate, which can vary according to the context. Consequently, users typically perceive fluctuations in a speaker's speech rate as natural, making it unlikely to arouse suspicion. Furthermore, detecting such subtle adjustments becomes challenging for users without reference speech. Our comprehensive experiments demonstrate that Speed Master can achieve an ASR over 99% in the digital domain, with only a 0.6% poisoning rate. Additionally, we validate the feasibility of Speed Master in the real world and its resistance to typical defensive measures.

Speed Master: Quick or Slow Play to Attack Speaker Recognition

Involving collaborative information in Large Language Models (LLMs) is a promising technique for adapting LLMs for recommendation. Existing methods achieve this by fine-tuning LLM, aligning collaborative features with LLM's input space, and concatenating collaborative features with text tokens to form a unified sequence input. Although effective, in this work, we identify two limitations when adapting LLMs to recommendation tasks, which hinder the integration of general knowledge and collaborative information, resulting in sub-optimal recommendation performance. (1) Fine-tuning LLM with recommendation data can undermine its inherent world knowledge and fundamental competencies, which are crucial for interpreting and inferring recommendation text. (2) Incorporating collaborative features into textual prompts disrupts the semantics of the original prompts, preventing LLM from generating appropriate outputs. In this paper, we propose a new paradigm, CoRA (an acronym for Collaborative LoRA), with a collaborative weights generator. Rather than input space alignment, this method aligns collaborative information with LLM's parameter space, representing them as incremental weights to update LLM's output. This way, LLM perceives collaborative information without altering its general knowledge and text inference capabilities. 
For each user-item pair, we employ a collaborative filtering model to extract user and item embeddings, converting them into collaborative weights with low-rank properties through the collaborative weights generator. We then merge the collaborative weights into LLM's weights, enabling LLM to perceive the collaborative signals and generate personalized recommendations without fine-tuning or extra collaborative tokens in prompts. Extensive experiments confirm that CoRA effectively integrates collaborative information into LLM, enhancing recommendation performance.

CoRA: Collaborative Information Perception by Large Language Model’s Weights for Recommendation

The map of elections framework is a methodology for visualizing and analyzing election datasets. So far, the framework was restricted to elections that have equal numbers of candidates, equal numbers of voters, and where all the (ordinal) votes rank all the candidates. We extend it to the case of elections of different sizes, where the votes can be top-truncated. We use our results to present a visualization of a large fragment of the Preflib database.

Downloads

Next from AAAI 2025

Simulation-Free Hierarchical Latent Policy Planning for Proactive Dialogues

Similar lecture

Group Fairness for Knapsack Problems