Xin Yao

AAAI Conference 2026 Conference Paper

GeWu: A Culturally-Grounded Chinese Benchmark for Multi-Stage Social Bias Evaluation in Large Language Models

• Yi Lin
• Ziyi Zhou
• Jiashi Gao
• Xinwei Guo
• Jiaxin Zhang
• Haiyan Wu
• Xin Yao
• Xuetao Wei

With the rapid deployment of Chinese large language models (LLMs), culturally-grounded bias evaluation remains understudied due to the dominance of English benchmarks and simplistic Chinese scenarios. To address this, we propose GeWu, a comprehensive benchmark featuring a culturally-aware dataset of 60,192 questions spanning 14 social groups with fine-grained Chinese contexts, significantly exceeding existing resources in breadth and depth. Our two-stage evaluation first quantifies bias via multiple-choice questions using a novel probability-based scoring mechanism to sensitively capture bias tendencies, distilling high-bias scenarios into GeWu-1K. This refined subset then enables multi-turn dialogue evaluations for in-depth analysis under realistic conditions. Experiments reveal that GeWu effectively exposes social biases in state-of-the-art Chinese LLMs, with 13.93% of scenarios eliciting universal bias across all models. This highlights persistent challenges and provides actionable insights for bias mitigation in Chinese contexts.

JAIR Journal 2026 Journal Article

Procedural Fairness in Machine Learning

• Ziming Wang
• Changwu Huang
• Ke Tang
• Xin Yao

Fairness in machine learning (ML) has garnered significant attention. However, current research has mainly concentrated on the distributive fairness of ML models, with limited focus on another dimension of fairness, i.e., procedural fairness. In this paper, we first define the procedural fairness of ML models by drawing from the established understanding of procedural fairness in philosophy and psychology fields, and then give formal definitions of individual and group procedural fairness. Based on the proposed definition, we further propose a novel metric to evaluate the group procedural fairness of ML models, called GPFFAE, which utilizes a widely used explainable artificial intelligence technique, namely feature attribution explanation (FAE), to capture the decision process of ML models. We validate the effectiveness of GPFFAE on a synthetic dataset and eight real-world datasets. Our experimental studies have revealed the relationship between procedural and distributive fairness of ML models. After validating the proposed metric for assessing the procedural fairness of ML models, we then propose a method for identifying the features that lead to the procedural unfairness of the model and propose two methods to improve procedural fairness based on the identified unfair features. Our experimental results demonstrate that we can accurately identify the features that lead to procedural unfairness in the ML model, and both of our proposed methods can significantly improve procedural fairness while also improving distributive fairness, with a slight sacrifice on the model performance.

AAAI Conference 2026 Conference Paper

The Silent Amplifier: In-Context Examples Fuel Bias in Large Language Models

• Xinwei Guo
• Jiashi Gao
• Junlei Zhou
• Jiaxin Zhang
• Quanying Liu
• Haiyan Wu
• Xin Yao
• Xuetao Wei

In-context learning (ICL) has proven to be adept at adapting large language models (LLMs) to downstream tasks without parameter updates, based on a few demonstration examples. Prior work has found that the ICL performance is susceptible to the selection of examples in prompt and made efforts to stabilize it. However, existing example selection studies ignore the ethical risks behind the examples selected, such as gender and race bias. In this work, we conduct extensive experiments and discover that (1) example selection with high accuracy does not mean low bias; (2) example selection for ICL may amplify the biases of LLMs; (3) example selection contributes to spurious correlations of LLMs. Based on the above observations, we propose the Remind with Bias-aware Embedding (ReBE), which removes the spurious correlations through contrastive learning and obtains bias-aware embedding for LLMs based on prompt tuning. Finally, we demonstrate that ReBE effectively mitigates biases of LLMs without significantly compromising accuracy and is highly compatible with existing example selection methods.

AAAI Conference 2025 Conference Paper

Efficient Robustness Evaluation via Constraint Relaxation

• Chao Pan
• Yu Wu
• Ke Tang
• Qing Li
• Xin Yao

The study of enhancing model robustness against adversarial examples has become increasingly critical in the security of deep learning, leading to the development of numerous adversarial defense techniques. While these defense methods have shown promise in mitigating the impact of adversarial perturbations, evaluating their effectiveness remains a critical challenge. The recently introduced AutoAttack technique has been recognized as a standardized method for assessing model robustness. However, the computational demands of the AutoAttack method significantly limits its applicability, underscoring the urgent need for efficient evaluation techniques. To address this challenge, we propose a novel and efficient evaluation framework based on strategic constraint relaxation. Our key insight is that temporarily expanding the adversarial perturbation bounds during the attack process can help discover more effective adversarial examples. Based on this insight, we develop the Constraint Relaxation Attack (CR Attack) method, which systematically relaxes and resets perturbation constraints during optimization. Extensive experiments on 105 robust models show that CR Attack outperforms AutoAttack in both attack success rate and efficiency, reducing forward and backward propagation time by 38.3× and 15.9× respectively. Through comprehensive analysis, we validate that the constraint relaxation mechanism is crucial for the method's effectiveness.

JAIR Journal 2025 Journal Article

Solving Overlapping Coalition Structure Generation in Task-Based Settings

• Guofu Zhang
• Zhaopin Su
• Xiaoxiao Song
• Zixuan Gao
• Miqing Li
• Xin Yao

The overlapping coalition structure generation problem (OCSGP) is a challenging computational problem in multi-agent systems. It focuses on selecting possibly overlapping coalitions from a set of agents to maximize the social welfare of all coalitions while containing all agents. However, in practical applications, coalitions may be formed to selectively respond to tasks from a pool of potential tasks assigned to agents. Consequently, this study considers OCSGP in a task-based setting, where each agent has finite resources and can only respond to tasks of interest, and each coalition can only take on mutually disjoint subsets of tasks. Specifically, we first present a model of the task-based OCSGP and investigate its computational complexity. Our theoretical results demonstrate that this specific OCSGP remains intractable even under restrictive assumptions. Subsequently, we develop a generic evolutionary algorithm framework (EAF) to find an approximately optimal overlapping coalition structure (OCS) in time quartic polynomial in the size of the instance. Particularly, we devise a specific solution-repair based heuristic of cubic time complexity to generate a feasible OCS. Finally, we compare the proposed EAF with a task-oriented heuristic and a hybrid algorithm for OCSGP, and examine its applicability in the pursuit-evasion problem. The experimental results reveal that the proposed EAF exhibits superior performance in finding feasible OCSs and demonstrates flexible adaptability to problem size and resource status.

NeurIPS Conference 2025 Conference Paper

ToxicTextCLIP: Text-Based Poisoning and Backdoor Attacks on CLIP Pre-training

• Xin Yao
• Haiyang Zhao
• Yimin Chen
• Jiawei Guo
• Kecheng Huang
• Ming Zhao

The Contrastive Language-Image Pretraining (CLIP) model has significantly advanced vision-language modeling by aligning image-text pairs from large-scale web data through self-supervised contrastive learning. Yet, its reliance on uncurated Internet-sourced data exposes it to data poisoning and backdoor risks. While existing studies primarily investigate image-based attacks, the text modality, which is equally central to CLIP's training, remains underexplored. In this work, we introduce ToxicTextCLIP, a framework for generating high-quality adversarial texts that target CLIP during the pre-training phase. The framework addresses two key challenges: semantic misalignment caused by background inconsistency with the target class, and the scarcity of background-consistent texts. To this end, ToxicTextCLIP iteratively applies: 1) a background-aware selector that prioritizes texts with background content aligned to the target class, and 2) a background-driven augmenter that generates semantically coherent and diverse poisoned samples. Extensive experiments on classification and retrieval tasks show that ToxicTextCLIP achieves up to 95. 83\% poisoning success and 98. 68% backdoor Hit@1, while bypassing RoCLIP, CleanCLIP and SafeCLIP defenses. The source code can be accessed via https: //github. com/xinyaocse/ToxicTextCLIP/.

TAAS Journal 2024 Journal Article

A Roadmap of Explainable Artificial Intelligence: Explain to Whom, When, What and How?

• Ziming Wang
• Changwu Huang
• Xin Yao

Explainable artificial intelligence (XAI) has gained significant attention, especially in AI-powered autonomous and adaptive systems (AASs). However, a discernible disconnect exists among research efforts across different communities. The machine learning community often overlooks “explaining to whom,” while the human-computer interaction community has examined various stakeholders with diverse explanation needs without addressing which XAI methods meet these requirements. Currently, no clear guidance exists on which XAI methods suit which specific stakeholders and their distinct needs. This hinders the achievement of the goal of XAI: providing human users with understandable interpretations. To bridge this gap, this article presents a comprehensive XAI roadmap. Based on an extensive literature review, the roadmap summarizes different stakeholders, their explanation needs at different stages of the AI system lifecycle, the questions they may pose, and existing XAI methods. Then, by utilizing stakeholders’ inquiries as a conduit, the roadmap connects their needs to prevailing XAI methods, providing a guideline to assist researchers and practitioners to determine more easily which XAI methodologies can meet the specific needs of stakeholders in AASs. Finally, the roadmap discusses the limitations of existing XAI methods and outlines directions for future research.

AAAI Conference 2024 Conference Paper

Adversarial Initialization with Universal Adversarial Perturbation: A New Approach to Fast Adversarial Training

• Chao Pan
• Qing Li
• Xin Yao

Traditional adversarial training, while effective at improving machine learning model robustness, is computationally intensive. Fast Adversarial Training (FAT) addresses this by using a single-step attack to generate adversarial examples more efficiently. Nonetheless, FAT is susceptible to a phenomenon known as catastrophic overfitting, wherein the model's adversarial robustness abruptly collapses to zero during the training phase. To address this challenge, recent studies have suggested adopting adversarial initialization with Fast Gradient Sign Method Adversarial Training (FGSM-AT), which recycles adversarial perturbations from prior epochs by computing gradient momentum. However, our research has uncovered a flaw in this approach. Given that data augmentation is employed during the training phase, the samples in each epoch are not identical. Consequently, the method essentially yields not the adversarial perturbation of a singular sample, but rather the Universal Adversarial Perturbation (UAP) of a sample and its data augmentation. This insight has led us to explore the potential of using UAPs for adversarial initialization within the context of FGSM-AT. We have devised various strategies for adversarial initialization utilizing UAPs, including single, class-based, and feature-based UAPs. Experiments conducted on three distinct datasets demonstrate that our method achieves an improved trade-off among robustness, computational cost, and memory footprint. Code is available at https://github.com/fzjcdt/fgsm-uap.

NeurIPS Conference 2024 Conference Paper

Association of Objects May Engender Stereotypes: Mitigating Association-Engendered Stereotypes in Text-to-Image Generation

• Junlei Zhou
• Jiashi Gao
• Xiangyu Zhao
• Xin Yao
• Xuetao Wei

Text-to-Image (T2I) has witnessed significant advancements, demonstrating superior performance for various generative tasks. However, the presence of stereotypes in T2I introduces harmful biases that require urgent attention as the T2I technology becomes more prominent. Previous work for stereotype mitigation mainly concentrated on mitigating stereotypes engendered with individual objects within images, which failed to address stereotypes engendered by the association of multiple objects, referred to as Association-Engendered Stereotypes. For example, mentioning ''black people'' and ''houses'' separately in prompts may not exhibit stereotypes. Nevertheless, when these two objects are associated in prompts, the association of ''black people'' with ''poorer houses'' becomes more pronounced. To tackle this issue, we propose a novel framework, MAS, to Mitigate Association-engendered Stereotypes. This framework models the stereotype problem as a probability distribution alignment problem, aiming to align the stereotype probability distribution of the generated image with the stereotype-free distribution. The MAS framework primarily consists of the Prompt-Image-Stereotype CLIP ( PIS CLIP ) and Sensitive Transformer. The PIS CLIP learns the association between prompts, images, and stereotypes, which can establish the mapping of prompts to stereotypes. The Sensitive Transformer produces the sensitive constraints, which guide the stereotyped image distribution to align with the stereotype-free probability distribution. Moreover, recognizing that existing metrics are insufficient for accurately evaluating association-engendered stereotypes, we propose a novel metric, Stereotype-Distribution-Total-Variation ( SDTV ), to evaluate stereotypes in T2I. Comprehensive experiments demonstrate that our framework effectively mitigates association-engendered stereotypes.

AAAI Conference 2024 Conference Paper

Complementary Knowledge Distillation for Robust and Privacy-Preserving Model Serving in Vertical Federated Learning

• Dashan Gao
• Sheng Wan
• Lixin Fan
• Xin Yao
• Qiang Yang

Vertical Federated Learning (VFL) enables an active party with labeled data to enhance model performance (utility) by collaborating with multiple passive parties that possess auxiliary features corresponding to the same sample identifiers (IDs). Model serving in VFL is vital for real-world, delay-sensitive applications, and it faces two major challenges: 1) robustness against arbitrarily-aligned data and stragglers; and 2) privacy protection, ensuring minimal label leakage to passive parties. Existing methods fail to transfer knowledge among parties to improve robustness in a privacy-preserving way. In this paper, we introduce a privacy-preserving knowledge transfer framework, Complementary Knowledge Distillation (CKD), designed to enhance the robustness and privacy of multi-party VFL systems. Specifically, we formulate a Complementary Label Coding (CLC) objective to encode only complementary label information of the active party's local model for passive parties to learn. Then, CKD selectively transfers the CLC-encoded complementary knowledge 1) from the passive parties to the active party, and 2) among the passive parties themselves. Experimental results on four real-world datasets demonstrate that CKD outperforms existing approaches in terms of robustness against arbitrarily-aligned data, while also minimizing label privacy leakage.

NeurIPS Conference 2024 Conference Paper

Does Egalitarian Fairness Lead to Instability? The Fairness Bounds in Stable Federated Learning Under Altruistic Behaviors

• Jiashi Gao
• Ziwei Wang
• Xiangyu Zhao
• Xin Yao
• Xuetao Wei

Federated learning (FL) offers a machine learning paradigm that protects privacy, allowing multiple clients to collaboratively train a global model while only accessing their local data. Recent research in FL has increasingly focused on improving the uniformity of model performance across clients, a fairness principle known as egalitarian fairness. However, achieving egalitarian fairness in FL may sacrifice the model performance for data-rich clients to benefit those with less data. This trade-off raises concerns about the stability of FL, as data-rich clients may opt to leave the current coalition and join another that is more closely aligned with its expected high performance. In this context, our work rigorously addresses the critical concern: Does egalitarian fairness lead to instability? Drawing from game theory and social choice theory, we initially characterize fair FL systems as altruism coalition formation games (ACFGs) and reveal that the instability issues emerging from the pursuit of egalitarian fairness are significantly related to the clients’ altruism within the coalition and the configuration of the friends-relationship networks among the clients. Then, we theoretically propose the optimal egalitarian fairness bounds that an FL coalition can achieve while maintaining core stability under various types of altruistic behaviors. The theoretical contributions clarify the quantitative relationships between achievable egalitarian fairness and the disparities in the sizes of local datasets, disproving the misconception that egalitarian fairness inevitably leads to instability. Finally, we conduct experiments to evaluate the consistency of our theoretically derived egalitarian fairness bounds with the empirically achieved egalitarian fairness in fair FL settings.

JMLR Journal 2024 Journal Article

Generative Adversarial Ranking Nets

• Yinghua Yao
• Yuangang Pan
• Jing Li
• Ivor W. Tsang
• Xin Yao

We propose a new adversarial training framework -- generative adversarial ranking networks (GARNet) to learn from user preferences among a list of samples so as to generate data meeting user-specific criteria. Verbosely, GARNet consists of two modules: a ranker and a generator. The generator fools the ranker to raise generated samples to the top; while the ranker learns to rank generated samples at the bottom. Meanwhile, the ranker learns to rank samples regarding the interested property by training with preferences collected on real samples. The adversarial ranking game between the ranker and the generator enables an alignment between the generated data distribution and the user-preferred data distribution with theoretical guarantees and empirical verification. Specifically, we first prove that when training with full preferences on a discrete property, the learned distribution of GARNet rigorously coincides with the distribution specified by the given score vector based on user preferences. The theoretical results are then extended to partial preferences on a discrete property and further generalized to preferences on a continuous property. Meanwhile, numerous experiments show that GARNet can retrieve the distribution of user-desired data based on full/partial preferences in terms of various interested properties (i.e., discrete/continuous property, single/multiple properties). Code is available at https://github.com/EvaFlower/GARNet. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2024. ( edit, beta )

NeurIPS Conference 2024 Conference Paper

Unveiling the Bias Impact on Symmetric Moral Consistency of Large Language Models

• Ziyi Zhou
• Xinwei Guo
• Jiashi Gao
• Xiangyu Zhao
• Shiyao Zhang
• Xin Yao
• Xuetao Wei

Large Language Models (LLMs) have demonstrated remarkable capabilities, surpassing human experts in various benchmark tests and playing a vital role in various industry sectors. Despite their effectiveness, a notable drawback of LLMs is their inconsistent moral behavior, which raises ethical concerns. This work delves into symmetric moral consistency in large language models and demonstrates that modern LLMs lack sufficient consistency ability in moral scenarios. Our extensive investigation of twelve popular LLMs reveals that their assessed consistency scores are influenced by position bias and selection bias rather than their intrinsic abilities. We propose a new framework tSMC, which gauges the effects of these biases and effectively mitigates the bias impact based on the Kullback–Leibler divergence to pinpoint LLMs' mitigated Symmetric Moral Consistency. We find that the ability of LLMs to maintain consistency varies across different moral scenarios. Specifically, LLMs show more consistency in scenarios with clear moral answers compared to those where no choice is morally perfect. The average consistency score of 12 LLMs ranges from $60. 7\%$ in high-ambiguity moral scenarios to $84. 8\%$ in low-ambiguity moral scenarios.

JBHI Journal 2022 Journal Article

JAN: Joint Attention Networks for Automatic ICD Coding

• Yuzhou Wu
• Zhigang Chen
• Xin Yao
• Xuechen Chen
• Zeren Zhou
• Jinkai Xue

The International Classification of Diseases (ICD) code is a disease classification method formulated by the World Health Organization(WHO). ICD coding usually requires clinicians to manually allocate ICD codes to clinical documents, which is labor-intensive, expensive, and error-prone. Therefore, many methods have been introduced for automatic ICD coding. However, most of the methods have ignored or cannot combine two essential features well: long-tailed label distribution and label correlation. In this paper, we propose a novel end-to-end Joint Attention Network (JAN) to solve these two problems. JAN includes Document-based attention and Label-based attention to capture semantic information from clinical document text and label description, respectively, which helps solve the classification of dense and sparse data in long-tailed label distribution. Besides, an Adaptive fusion layer and CorNet block are presented to adaptively adjust the weight of these two attentions and exploit label co-occurrence relations, respectively. Experiments on the MIMIC-III and MIMIC-II datasets demonstrate that our proposed JAN outperformed previous state-of-art methods achieving Micro-F1 of 0. 553, Micro-AUC of 0. 989 and precision at top 8(P@8) of 0. 735. Finally, we also provide attention and label correlation visualization to verify the effectiveness of our model and improve the interpretation of our deep learning-based method.

AAAI Conference 2020 Conference Paper

On Performance Estimation in Automatic Algorithm Configuration

• Shengcai Liu
• Ke Tang
• Yunwei Lei
• Xin Yao

Over the last decade, research on automated parameter tuning, often referred to as automatic algorithm configuration (AAC), has made significant progress. Although the usefulness of such tools has been widely recognized in real world applications, the theoretical foundations of AAC are still very weak. This paper addresses this gap by studying the performance estimation problem in AAC. More specifically, this paper first proves the universal best performance estimator in a practical setting, and then establishes theoretical bounds on the estimation error, i. e. , the difference between the training performance and the true performance for a parameter con- figuration, considering finite and infinite configuration spaces respectively. These findings were verified in extensive experiments conducted on four algorithm configuration scenarios involving different problem domains. Moreover, insights for enhancing existing AAC methods are also identified.

AAAI Conference 2019 Conference Paper

Automatic Construction of Parallel Portfolios via Explicit Instance Grouping

• Shengcai Liu
• Ke Tang
• Xin Yao

Exploiting parallelism is becoming more and more important in designing efficient solvers for computationally hard problems. However, manually building parallel solvers typically requires considerable domain knowledge and plenty of human effort. As an alternative, automatic construction of parallel portfolios (ACPP) aims at automatically building effective parallel portfolios based on a given problem instance set and a given rich configuration space. One promising way to solve the ACPP problem is to explicitly group the instances into different subsets and promote a component solver to handle each of them. This paper investigates solving ACPP from this perspective, and especially studies how to obtain a good instance grouping. The experimental results on two widely studied problem domains, the boolean satisfiability problems (SAT) and the traveling salesman problems (TSP), showed that the parallel portfolios constructed by the proposed method could achieve consistently superior performances to the ones constructed by the state-of-the-art ACPP methods, and could even rival sophisticated hand-designed parallel solvers.

NeurIPS Conference 2019 Conference Paper

Explicit Planning for Efficient Exploration in Reinforcement Learning

• Liangpeng Zhang
• Ke Tang
• Xin Yao

Efficient exploration is crucial to achieving good performance in reinforcement learning. Existing systematic exploration strategies (R-MAX, MBIE, UCRL, etc. ), despite being promising theoretically, are essentially greedy strategies that follow some predefined heuristics. When the heuristics do not match the dynamics of Markov decision processes (MDPs) well, an excessive amount of time can be wasted in travelling through already-explored states, lowering the overall efficiency. We argue that explicit planning for exploration can help alleviate such a problem, and propose a Value Iteration for Exploration Cost (VIEC) algorithm which computes the optimal exploration scheme by solving an augmented MDP. We then present a detailed analysis of the exploration behaviour of some popular strategies, showing how these strategies can fail and spend O(n^2 md) or O(n^2 m + nmd) steps to collect sufficient data in some tower-shaped MDPs, while the optimal exploration scheme, which can be obtained by VIEC, only needs O(nmd), where n, m are the numbers of states and actions and d is the data demand. The analysis not only points out the weakness of existing heuristic-based strategies, but also suggests a remarkable potential in explicit planning for exploration.

TAAS Journal 2019 Journal Article

Finding the Largest Successful Coalition under the Strict Goal Preferences of Agents

• Zhaopin Su
• Guofu Zhang
• Feng Yue
• Jindong He
• Miqing Li
• Bin Li
• Xin Yao

Coalition formation has been a fundamental form of resource cooperation for achieving joint goals in multiagent systems. Most existing studies still focus on the traditional assumption that an agent has to contribute its resources to all the goals, even if the agent is not interested in the goal at all. In this article, a natural extension of the traditional coalitional resource games (CRGs) is studied from both theoretical and empirical perspectives, in which each agent has uncompromising, personalized preferences over goals. Specifically, a new CRGs model with agents’ strict preferences for goals is presented, in which an agent is willing to contribute its resources only to the goals that are in its own interest set. The computational complexity of the basic decision problems surrounding the successful coalition is reinvestigated. The results suggest that these problems in such a strict preference way are complex and intractable. To find the largest successful coalition for possible computation reduction or potential parallel processing, a flow-network–based exhaust algorithm, called FNetEA, is proposed to achieve the optimal solution. Then, to solve the problem more efficiently, a hybrid algorithm, named 2D-HA, is developed to find the approximately optimal solution on the basis of genetic algorithm, two-dimensional (2D) solution representation, and a heuristic for solution repairs. Through extensive experiments, the 2D-HA algorithm exhibits the prominent ability to provide reassurances that the optimal solution could be found within a reasonable period of time, even in a super-large-scale space.

AIJ Journal 2019 Journal Article

Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms

• Chao Qian
• Yang Yu
• Ke Tang
• Xin Yao
• Zhi-Hua Zhou

Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two decades, promising results on the running time analysis (one essential theoretical aspect) of EAs have been obtained, while most of them focused on isolated combinatorial optimization problems, which do not reflect the general-purpose nature of EAs. To provide a general theoretical explanation of the behavior of EAs, it is desirable to study their performance on general classes of combinatorial optimization problems. To the best of our knowledge, the only result towards this direction is the provably good approximation guarantees of EAs for the problem class of maximizing monotone submodular functions with matroid constraints. The aim of this work is to contribute to this line of research. Considering that many combinatorial optimization problems involve non-monotone or non-submodular objective functions, we study the general problem classes, maximizing submodular functions with/without a size constraint and maximizing monotone approximately submodular functions with a size constraint. We prove that a simple multi-objective EA called GSEMO-C can generally achieve good approximation guarantees in polynomial expected running time.

AAAI Conference 2018 Conference Paper

On Multiset Selection With Size Constraints

• Chao Qian
• Yibo Zhang
• Ke Tang
• Xin Yao

This paper considers the multiset selection problem with size constraints, which arises in many real-world applications such as budget allocation. Previous studies required the objective function f to be submodular, while we relax this assumption by introducing the notion of the submodularity ratios (denoted by αf and βf ). We propose an anytime randomized iterative approach POMS, which maximizes the given objective f and minimizes the multiset size simultaneously. We prove that POMS using a reasonable time achieves an approximation guarantee of max{1 − e−βf, (αf /2)(1 − e−αf )}. Particularly, when f is submdoular, this bound is at least as good as that of the previous greedy-style algorithms. In addition, we give lower bounds on the submodularity ratio for the objectives of budget allocation. Experimental results on budget allocation as well as a more complex application, namely, generalized influence maximization, exhibit the superior performance of the proposed approach.

NeurIPS Conference 2017 Conference Paper

Log-normality and Skewness of Estimated State/Action Values in Reinforcement Learning

• Liangpeng Zhang
• Ke Tang
• Xin Yao

Under/overestimation of state/action values are harmful for reinforcement learning agents. In this paper, we show that a state/action value estimated using the Bellman equation can be decomposed to a weighted sum of path-wise values that follow log-normal distributions. Since log-normal distributions are skewed, the distribution of estimated state/action values can also be skewed, leading to an imbalanced likelihood of under/overestimation. The degree of such imbalance can vary greatly among actions and policies within a single problem instance, making the agent prone to select actions/policies that have inferior expected return and higher likelihood of overestimation. We present a comprehensive analysis to such skewness, examine its factors and impacts through both theoretical and empirical results, and discuss the possible ways to reduce its undesirable effects.

IJCAI Conference 2016 Conference Paper

Dealing with Multiple Classes in Online Class Imbalance Learning

• Shuo Wang
• Leandro L. Minku
• Xin Yao

Online class imbalance learning deals with data streams having very skewed class distributions in a timely fashion. Although a few methods have been proposed to handle such problems, most of them focus on two-class cases. Multi-class imbalance imposes additional challenges in learning. This paper studies the combined challenges posed by multi-class imbalance and online learning, and aims at a more effective and adaptive solution. First, we introduce two resampling-based ensemble methods, called MOOB and MUOB, which can process multi-class data directly and strictly online with an adaptive sampling rate. Then, we look into the impact of multi-minority and multi-majority cases on MOOB and MUOB in comparison to other methods under stationary and dynamic scenarios. Both multi-minority and multi-majority make a negative impact. MOOB shows the best and most stable G-mean in most stationary and dynamic cases.

IJCAI Conference 2015 Conference Paper

Increasingly Cautious Optimism for Practical PAC-MDP Exploration

• Liangpeng Zhang
• Ke Tang
• Xin Yao

Exploration strategy is an essential part of learning agents in model-based Reinforcement Learning. R-MAX and V-MAX are PAC-MDP strategies proved to have polynomial sample complexity; yet, their exploration behavior tend to be overly cautious in practice. We propose the principle of Increasingly Cautious Optimism (ICO) to automatically cut off unnecessarily cautious exploration, and apply ICO to R-MAX and V-MAX, yielding two new strategies, namely Increasingly Cautious R-MAX (ICR) and Increasingly Cautious V-MAX (ICV). We prove that both ICR and ICV are PAC- MDP, and show that their improvement is guaranteed by a tighter sample complexity upper bound. Then, we demonstrate their significantly improved performance through empirical results.

IJCAI Conference 2015 Conference Paper

Model Metric Co-Learning for Time Series Classification

• Huanhuan Chen
• Fengzhen Tang
• Peter Tino
• Anthony G. Cohn
• Xin Yao

We present a novel model-metric co-learning (MMCL) methodology for sequence classification which learns in the model space – each data item (sequence) is represented by a predictive model from a carefully designed model class. MMCL learning encourages sequences from the same class to be represented by ‘close’ model representations, well separated from those for different classes. Existing approaches to the problem either fit a single model to all the data, or a (predominantly linear) model on each sequence. We introduce a novel hybrid approach spanning the two extremes. The model class we use is a special form of adaptive high-dimensional non-linear state space model with a highly constrained and simple dynamic part. The dynamic part is identical for all data items and acts as a temporal filter providing a rich pool of dynamic features that can be selectively extracted by individual (static) linear readout mappings representing the sequences. Alongside learning the dynamic part, we also learn the global metric in the model readout space. Experiments on synthetic and benchmark data sets confirm the effectiveness of the algorithm compared to a variety of alternative methods.

TAAS Journal 2015 Journal Article

Static, Dynamic, and Adaptive Heterogeneity in Distributed Smart Camera Networks

• Peter R. Lewis
• Lukas Esterle
• Arjun Chandra
• Bernhard Rinner
• Jim Torresen
• Xin Yao

We study heterogeneity among nodes in self-organizing smart camera networks, which use strategies based on social and economic knowledge to target communication activity efficiently. We compare homogeneous configurations, when cameras use the same strategy, with heterogeneous configurations, when cameras use different strategies. Our first contribution is to establish that static heterogeneity leads to new outcomes that are more efficient than those possible with homogeneity. Next, two forms of dynamic heterogeneity are investigated: nonadaptive mixed strategies and adaptive strategies, which learn online. Our second contribution is to show that mixed strategies offer Pareto efficiency consistently comparable with the most efficient static heterogeneous configurations. Since the particular configuration required for high Pareto efficiency in a scenario will not be known in advance, our third contribution is to show how decentralized online learning can lead to more efficient outcomes than the homogeneous case. In some cases, outcomes from online learning were more efficient than all other evaluated configuration types. Our fourth contribution is to show that online learning typically leads to outcomes more evenly spread over the objective space. Our results provide insight into the relationship between static, dynamic, and adaptive heterogeneity, suggesting that all have a key role in achieving efficient self-organization.

IJCAI Conference 2013 Conference Paper

On the Approximation Ability of Evolutionary Optimization with Application to Minimum Set Cover: Extended Abstract

• Yang Yu
• Xin Yao
• Zhi-Hua Zhou

Evolutionary algorithms (EAs) are a large family of heuristic optimization algorithms inspired by natural phenomena, and are often used in practice to obtain satisficing instead of optimal solutions. In this work, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the obtained solution is to an optimal solution. We study an EA framework named simple EA with isolated population (SEIP) that can be implemented as a single- or multi-objective EA. We present general approximation results of SEIP, and specifically on the minimum set cover problem, we find that SEIP achieves the currently bestachievable approximation ratio. Moreover, on an instance class of the k-set cover problem, we disclose how SEIP can overcome the difficulty that limits the greedy algorithm.

TCS Journal 2012 Journal Article

A large population size can be unhelpful in evolutionary algorithms

• Tianshi Chen
• Ke Tang
• Guoliang Chen
• Xin Yao

The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002) [8] showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems.

TCS Journal 2012 Journal Article

Editorial to the special issue on “Theoretical Foundations of Evolutionary Computation”

• Per Kristian Lehre
• Frank Neumann
• Jonathan E. Rowe
• Xin Yao

AIJ Journal 2012 Journal Article

On the approximation ability of evolutionary optimization with application to minimum set cover

• Yang Yu
• Xin Yao
• Zhi-Hua Zhou

Evolutionary algorithms (EAs) are heuristic algorithms inspired by natural evolution. They are often used to obtain satisficing solutions in practice. In this paper, we investigate a largely underexplored issue: the approximation performance of EAs in terms of how close the solution obtained is to an optimal solution. We study an EA framework named simple EA with isolated population (SEIP) that can be implemented as a single- or multi-objective EA. We analyze the approximation performance of SEIP using the partial ratio, which characterizes the approximation ratio that can be guaranteed. Specifically, we analyze SEIP using a set cover problem that is NP-hard. We find that in a simple configuration, SEIP efficiently achieves an H n -approximation ratio, the asymptotic lower bound, for the unbounded set cover problem. We also find that SEIP efficiently achieves an ( H k − k − 1 8 k 9 ) -approximation ratio, the currently best-achievable result, for the k-set cover problem. Moreover, for an instance class of the k-set cover problem, we disclose how SEIP, using either one-bit or bit-wise mutation, can overcome the difficulty that limits the greedy algorithm.

TCS Journal 2010 Journal Article

Choosing selection pressure for wide-gap problems

• Tianshi Chen
• Jun He
• Guoliang Chen
• Xin Yao

To exploit an evolutionary algorithm’s performance to the full extent, the selection scheme should be chosen carefully. Empirically, it is commonly acknowledged that low selection pressure can prevent an evolutionary algorithm from premature convergence, and is thereby more suitable for wide-gap problems. However, there are few theoretical time complexity studies that actually give the conditions under which a high or a low selection pressure is better. In this paper, we provide a rigorous time complexity analysis showing that low selection pressure is better for the wide-gap problems with two optima.

JAAMAS Journal 2009 Journal Article

Market-based control of computational systems: introduction to the special issue

• Enrico H. Gerding
• Peter McBurney
• Xin Yao

Abstract We introduce the Special Issue of the journal on the topic of Market-Based Control of Computational Systems. The special issue collects six peer-reviewed papers arising from an International Workshop on the topic held in Liverpool, UK, in September 2008.

JAAMAS Journal 2009 Journal Article

Resource allocation in decentralised computational systems: an evolutionary market-based approach

• Peter R. Lewis
• Paul Marrow
• Xin Yao

Abstract We present a novel market-based method, inspired by retail markets, for resource allocation in fully decentralised systems where agents are self-interested. Our market mechanism requires no coordinating node or complex negotiation. The stability of outcome allocations, those at equilibrium, is analysed and compared for three buyer behaviour models. In order to capture the interaction between self-interested agents, we propose the use of competitive coevolution. Our approach is both highly scalable and may be tuned to achieve specified outcome resource allocations. We demonstrate the behaviour of our approach in simulation, where evolutionary market agents act on behalf of service providing nodes to adaptively price their resources over time, in response to market conditions. We show that this leads the system to the predicted outcome resource allocation. Furthermore, the system remains stable in the presence of small changes in price, when buyers’ decision functions degrade gracefully.

AIJ Journal 2003 Journal Article

Towards an analytic framework for analysing the computation time of evolutionary algorithms

• Jun He
• Xin Yao

In spite of many applications of evolutionary algorithms in optimisation, theoretical results on the computation time and time complexity of evolutionary algorithms on different optimisation problems are relatively few. It is still unclear when an evolutionary algorithm is expected to solve an optimisation problem efficiently or otherwise. This paper gives a general analytic framework for analysing first hitting times of evolutionary algorithms. The framework is built on the absorbing Markov chain model of evolutionary algorithms. The first step towards a systematic comparative study among different EAs and their first hitting times has been made in the paper.

AIJ Journal 2002 Journal Article

Erratum to: Drift analysis and average time complexity of evolutionary algorithms

• Jun He
• Xin Yao

The proof of Theorem 6 in the paper by J. He and X. Yao [Artificial Intelligence 127 (1) (2001) 57–85] contains a mistake, although the theorem is correct [S. Droste et al. , Theoret. Comput. Sci. 276 (2002) 51–81]. This note gives a revised proof and theorem. It turns out that the revised theorem is more general than the original one given an evolutionary algorithm with mutation probability p m =1/(2n), using the same proof method as given by J. He and X. Yao [Artificial Intelligence 127 (1) (2001) 57–85].

AIJ Journal 2001 Journal Article

Drift analysis and average time complexity of evolutionary algorithms

• Jun He
• Xin Yao

The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including conditions under which an EA will take no more than polynomial time (in problem size) to solve a problem and conditions under which an EA will take at least exponential time (in problem size) to solve a problem. The paper first presents the general results, and then uses several problems as examples to illustrate how these general results can be applied to concrete problems in analyzing the average time complexity of EAs. While previous work only considered (1+1) EAs without any crossover, the EAs considered in this paper are fairly general, which use a finite population, crossover, mutation, and selection.