United States

Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results --  however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.

AAAI 2025

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces

evolutionary computation

The 9th Brazilian Conference on Intelligent Systems (BRACIS), the 16h Encontro Nacional de Inteligência Artificial e Computacional (ENIAC), and the 12th Concurso de Teses e Dissertações em Inteligência Artificial e Computacional (CTDIAC) was held from 20 to 23 October, 2020.

BRACIS originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence - SBIA (22 editions), and the Brazilian Symposium on Neural Networks - SBRN (13 editions). ENIAC is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. CTDIAC is a satellite event whose goals are to disseminate and award the best dissertations and theses (MSc and PhDs concluded in Brazilian universities from June 2018 to May 2020) in Artificial and Computational Intelligence areas.

In this year, the Symposium on Knowledge Discovery, Mining and Learning (KDMiLe) will be held in conjunction with BRACIS 2020. This sysposium aims at integrating researchers, practitioners, developers, students and users to present their research results, to discuss ideas, and to exchange techniques, tools, and practical experiences – related to the Data Mining and Machine Learning areas.

BRACIS 2020

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 literature uses language to build foundation models for audio. These Audio-Language Models (ALMs) are trained on a vast number of audio-text pairs and show remarkable performance in tasks including Text-to-Audio Retrieval, Captioning, and Question Answering. However, their ability to engage in more complex open-ended tasks, like Interactive Question-Answering, requires proficiency in logical reasoning-- a skill not yet benchmarked. We introduce the novel task of Audio Entailment to evaluate an ALM's deductive reasoning ability. This task assesses whether a text description (hypothesis) of audio content can be deduced from an audio recording (premise), with potential conclusions being entailment, neutral, or contradiction, depending on the sufficiency of the evidence. We create two datasets for this task with audio recordings sourced from two audio captioning datasets-AudioCaps and Clotho-and hypotheses generated using Large Language Models (LLMs). We benchmark state-of-the-art ALMs and find deficiencies in logical reasoning with both zero-shot and linear probe evaluations. Finally, we propose "caption-before-reason", an intermediate step of captioning that improves the Zero-Shot and linear-probe performance of ALMs by an absolute 6% and 3%, respectively.

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Personalized Federated Learning (PFL) is widely used in IoT applications to manage large-scale, non-iid client data while ensuring data privacy. However, the diverse edge devices owned by clients may impose varying degrees of resource constraints, leading to computation and communication bottlenecks for PFL. To tackle this challenge, Federated Dropout has emerged as a popular strategy, where only a subset of the global model, known as a sub-model, is trained on a client's device, thereby reducing computation and communication overheads. Nevertheless, the dropout-based model-pruning strategy may introduce bias, especially towards non-iid local data. This bias can result in performance degradation when biased sub-models absorb highly divergent parameters from other clients. In response, we propose federated learning with stochastic parameter update (FedSPU). Unlike dropout, which tailors the global model to small-size local sub-models, FedSPU maintains the full model architecture on each device but randomly freezes a certain percentage of neurons in the local model during training while updating the remaining neurons. This approach ensures that a portion of the local model remains personalized, thereby enhancing the model's robustness against biased parameters from other clients. Experimental results demonstrate that FedSPU outperforms federated dropout by an average of 7.57% in terms of accuracy. Furthermore, an introduced early stopping scheme leads to a significant reduction in training time by 24.8% to 70.4% while maintaining high accuracy.

FedSPU: Personalized Federated Learning for Resource-Constrained Devices with Stochastic Parameter Update

Generative models have gained significant attention in multivariate time series forecasting (MTS), particularly due to their ability to generate high-fidelity samples. Forecasting the probability distribution of multivariate time series is a challenging yet practical task. Although some recent attempts have been made to handle this task, two major challenges persist: 1) some existing generative methods underperform in high-dimensional multivariate time series forecasting, which is hard to scale to higher dimensions; 2) The inherent high-dimensional multivariate attributes constrain the forecasting lengths of existing generative models. In this paper, we point out that discrete token representations can model high-dimensional MTS with faster inference time, and forecast the target with the long-term trends of itself can extend the forecasting length with high accuracy. Motivated by this, we propose a vector quantized framework called \textbf{H}ierarchical \textbf{D}iscrete \textbf{T}ransformer (HDT) that models time series into discrete token representations with $\ell_2$ normalization enhanced vector quantized strategy, in which we transform the MTS forecasting into discrete tokens generation. To address the limitations of generative models in long-term forecasting, we propose a hierarchical discrete Transformer. This model captures the discrete long-term trend of the target at the low level and leverages this trend as a condition to generate the discrete representation of the target at the high level that introduces the features of target itself for extending the forecasting length in high-dimensional MTS. Extensive experiments on five popular MTS datasets verify the effectiveness of our proposed method. The source code will be released.

HDT: Hierarchical Discrete Transformer for Multivariate Time Series Forecasting

We consider a class of optimization problems defined by a system of linear equations with min and max operators. 
	This class of optimization problems has been studied under restrictive conditions, such as,
    (C1) the halting or stability condition;
    (C2) the non-negative coefficients condition;
    (C3) the sum upto $1$ condition; and
    (C4) the only min or only max operator condition.
	Several seminal results in the literature focus on special cases.
	For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4.
	However, the systematic computational complexity study of all the cases has not been explored, which we address in this work.
	Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is \textsc{NP}-complete, whereas with condition C1 only, the problem is in \textsc{UP} $\cap$ \textsc{coUP}.
	Finally, we establish the computational complexity of the decision problem of checking the respective conditions.

Linear Equations with Min and Max Operators: Computational Complexity

Self-learning of Large Language Models (LLMs) facilitates their advancement towards super-intelligence by training with self-synthesized experiences. However, a critical challenge is the amplification of hallucinations in generated data during iterative self-learning, underscoring the need for reliable data selection. To address this, we investigate the mechanism of Inner Knowledge Explicitation, which involves explicitly extracting the inner knowledge from memory of LLMs, to concurrently improves reasoning, and enables reliable self-learning data selection. This paper introduces a Self Knowledge Explicitation Learning (SKE-Learn) framework, which equips the LLMs with meta-skills to explicitly extract, verify and utilize inner knowledge for reasoning. By leveraging these meta-skills, SKE-Learn establishes a self-learning approach that ensures reliable selection of self-synthetic data. This approach enhances performance through iterative self-learning while mitigating the problem of hallucinations. Empirical results from six benchmarks demonstrate that Inner Knowledge Explicitation improves reasoning by serving as a more effective prompting method. Additionally, SKE-Learn, based on the verifiability of explicit knowledge, shows consistent performance improvements over multiple self-training iterations, with an average performance increase from 52.79% to 56.54% across all benchmarks. Furthermore, Inner Knowledge Explicitation provides explaination and intervention space during LLM's generation process. The code will be made available upon acceptance.

Empowering Self-Learning of LLMs: Inner Knowledge Explicitation as a Catalyst

Rap, a prominent genre of vocal performance, remains underexplored in vocal generation. General vocal synthesis depends on precise note and duration inputs, requiring users to have related musical knowledge, which limits flexibility. In contrast, rap typically features simpler melodies, with a core focus on a strong rhythmic sense that harmonizes with accompanying beats. In this paper, we propose Freestyler, the first system that generates rapping vocals directly from lyrics and accompaniment inputs. Freestyler utilizes language model-based token generation, followed by a conditional flow matching model to produce spectrograms and a neural vocoder to restore audio. It allows a 3-second prompt to enable zero-shot timbre control. Due to the scarcity of publicly available rap datasets, we collected a large volume of rap songs from the internet and designed a meticulous pipeline for data cleaning, processing, and filtering.

Drop the Beat! Freestyler for Accompaniment Conditioned Rapping Voice Generation

Fairness and efficiency have become the pillars of modern fair division research, but prior work on achieving both simultaneously is largely limited to the unconstrained setting. We study fair and efficient allocations of indivisible goods under additive valuations and various types of allocation feasibility constraints, and demonstrate the unreasonable effectiveness of the maximum Nash welfare (MNW) solution in this previously uncharted territory. 

Our main result is that MNW allocations are 1/2-envy-free up to one good (EF1) and Pareto optimal under the broad family of (arbitrary) matroid constraints. We extend these guarantees to complete MNW allocations for base-orderable matroid constraints, and to a family of non-matroidal constraints (which includes balancedness) using a novel "alternate worlds" technique. We establish tightness of our results by providing counterexamples for the satisfiability of certain stronger desiderata, but show an improved result for the special case of goods with copies (Gafni et al. 2023). Finally, we also establish novel best-of-both-worlds guarantees for goods with copies and balancedness.

Constrained Fair and Efficient Allocations

Prototype-based federated learning has emerged as a promising approach that shares lightweight prototypes to transfer knowledge among clients with data heterogeneity in a model-agnostic manner.
However, existing methods often collect prototypes directly from local models, which inevitably introduce inconsistencies into representation learning due to the biased data distributions and differing model architectures among clients.
In this paper, we identify that both statistical and model heterogeneity create a vicious cycle of representation inconsistency, classifier divergence, and skewed prototype alignment, which negatively impacts the performance of clients.
To break the vicious cycle, we propose a novel framework named Federated Learning via Semantic Anchors (FedSA) to decouple the generation of prototypes from local representation learning.
We introduce a novel perspective that uses simple yet effective semantic anchors serving as prototypes to guide local models in learning consistent representations.
By incorporating semantic anchors, we further propose anchor-based regularization with margin-enhanced contrastive learning and anchor-based classifier calibration to correct feature extractors and calibrate classifiers across clients, achieving intra-class compactness and inter-class separability of prototypes while ensuring consistent decision boundaries.
We then update the semantic anchors with these consistent and discriminative prototypes, which iteratively encourage clients to collaboratively learn a unified data representation with robust generalization.
Extensive experiments under both statistical and model heterogeneity settings show that FedSA significantly outperforms existing prototype-based FL methods on various classification tasks.

FedSA: A Unified Representation Learning via Semantic Anchors for Prototype-based Federated Learning

Communication has been widely employed to enhance multi-agent collaboration. Previous research has typically assumed delay-free communication, a strong assumption that is challenging to meet in practice. However, real-world agents suffer from channel delays, receiving  messages sent at different time points, termed Asynchronous Communication, leading to cognitive biases and breakdowns in collaboration. This paper first defines two communication delay settings in MARL and emphasizes their harm to collaboration. To handle the above delays, this paper proposes a novel framework, Communication Delay-Tolerant Multi-Agent Collaboration (CoDe). At first, CoDe learns an intent representation as messages through future action inference, reflecting the stable future behavioral trends of the agents. Then, CoDe devises a dual alignment mechanism of intent and timeliness to strengthen the fusion process of asynchronous messages. In this way, agents can extract the long-term intent of others, even from delayed messages, and selectively utilize the most recent messages that are relevant to their intent. Experimental results demonstrate that CoDe outperforms baseline algorithms in three MARL benchmarks without delay and exhibits robustness under fixed and time-varying delays.

CoDe: Communication Delay-Tolerant Multi-Agent Collaboration via Dual Alignment of Intent and Timeliness

The accelerated MRI reconstruction process presents a challenging ill-posed inverse problem due to the extensive under-sampling in k-space. Recently, Vision Transformers (ViTs) have become the mainstream for this task, demonstrating substantial performance improvements. However, there are still three significant issues remain unaddressed: (1) ViTs struggle to capture high-frequency components of images, limiting their ability to detect local textures and edge information, thereby impeding MRI restoration; (2) Previous methods calculate multi-head self-attention (MSA) among both related and unrelated tokens in content, introducing noise and significantly increasing computational burden; (3) The naive feed-forward network in ViTs cannot model the multi-scale information that is important for image restoration. In this paper, we propose FPS-Former, a powerful ViT-based framework, to address these issues from the perspectives of frequency modulation, spatial purification, and scale diversification. Specifically, to address issue (1), we introduce a frequency modulation attention module to enhance the self-attention map by adaptively re-calibrating the frequency information in a Laplacian pyramid. For issue (2), we customize a spatial purification attention module to capture interactions among closely related tokens, thereby reducing redundant or irrelevant feature representations. For issue (3), we propose an efficient feed-forward network based on a hybrid-scale fusion strategy that effectively models multi-scale information. We conduct extensive experiments on three public datasets for MRI reconstruction under various undersampling patterns. Comprehensive results demonstrate that our FPS-Former significantly outperforms state-of-the-art methods while requiring lower computational costs. Codes will be available.

Downloads

Next from AAAI 2025

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Similar lecture

A Reinforcement Learning Based Adaptive Mutation for Cartesian Genetic Programming Applied to the Design of Combinational Logic Circuits

.css-70qvj9{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}Downloads

Next from AAAI 2025

Audio Entailment: Assessing Deductive Reasoning for Audio Understanding

Similar lecture

A Reinforcement Learning Based Adaptive Mutation for Cartesian Genetic Programming Applied to the Design of Combinational Logic Circuits

Downloads