Xiaojin Zhu

AAAI Conference 2024 Conference Paper

Data Poisoning to Fake a Nash Equilibria for Markov Games

• Young Wu
• Jeremy McMahan
• Xiaojin Zhu
• Qiaomin Xie

We characterize offline data poisoning attacks on Multi-Agent Reinforcement Learning (MARL), where an attacker may change a data set in an attempt to install a (potentially fictitious) unique Markov-perfect Nash equilibrium for a two-player zero-sum Markov game. We propose the unique Nash set, namely the set of games, specified by their Q functions, with a specific joint policy being the unique Nash equilibrium. The unique Nash set is central to poisoning attacks because the attack is successful if and only if data poisoning pushes all plausible games inside it. The unique Nash set generalizes the reward polytope commonly used in inverse reinforcement learning to MARL. For zero-sum Markov games, both the inverse Nash set and the set of plausible games induced by data are polytopes in the Q function space. We exhibit a linear program to efficiently compute the optimal poisoning attack. Our work sheds light on the structure of data poisoning attacks on offline MARL, a necessary step before one can design more robust MARL algorithms.

AAAI Conference 2024 Conference Paper

Exact Policy Recovery in Offline RL with Both Heavy-Tailed Rewards and Data Corruption

• Yiding Chen
• Xuezhou Zhang
• Qiaomin Xie
• Xiaojin Zhu

We study offline reinforcement learning (RL) with heavy-tailed reward distribution and data corruption: (i) Moving beyond subGaussian reward distribution, we allow the rewards to have infinite variances; (ii) We allow corruptions where an attacker can arbitrarily modify a small fraction of the rewards and transitions in the dataset. We first derive a sufficient optimality condition for generalized Pessimistic Value Iteration (PEVI), which allows various estimators with proper confidence bounds and can be applied to multiple learning settings. In order to handle the data corruption and heavy-tailed reward setting, we prove that the trimmed-mean estimation achieves the minimax optimal error rate for robust mean estimation under heavy-tailed distributions. In the PEVI algorithm, we plug in the trimmed mean estimation and the confidence bound to solve the robust offline RL problem. Standard analysis reveals that data corruption induces a bias term in the suboptimality gap, which gives the false impression that any data corruption prevents optimal policy learning. By using the optimality condition for the generalized PEVI, we show that as long as the bias term is less than the ``action gap'', the policy returned by PEVI achieves the optimal value given sufficient data.

AAAI Conference 2024 Conference Paper

Optimal Attack and Defense for Reinforcement Learning

• Jeremy McMahan
• Young Wu
• Xiaojin Zhu
• Qiaomin Xie

To ensure the usefulness of Reinforcement Learning (RL) in real systems, it is crucial to ensure they are robust to noise and adversarial attacks. In adversarial RL, an external attacker has the power to manipulate the victim agent's interaction with the environment. We study the full class of online manipulation attacks, which include (i) state attacks, (ii) observation attacks (which are a generalization of perceived-state attacks), (iii) action attacks, and (iv) reward attacks. We show the attacker's problem of designing a stealthy attack that maximizes its own expected reward, which often corresponds to minimizing the victim's value, is captured by a Markov Decision Process (MDP) that we call a meta-MDP since it is not the true environment but a higher level environment induced by the attacked interaction. We show that the attacker can derive optimal attacks by planning in polynomial time or learning with polynomial sample complexity using standard RL techniques. We argue that the optimal defense policy for the victim can be computed as the solution to a stochastic Stackelberg game, which can be further simplified into a partially-observable turn-based stochastic game (POTBSG). Neither the attacker nor the victim would benefit from deviating from their respective optimal policies, thus such solutions are truly robust. Although the defense problem is NP-hard, we show that optimal Markovian defenses can be computed (learned) in polynomial time (sample complexity) in many scenarios.

AAAI Conference 2023 Conference Paper

Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learning

• Young Wu
• Jeremy McMahan
• Xiaojin Zhu
• Qiaomin Xie

In offline multi-agent reinforcement learning (MARL), agents estimate policies from a given dataset. We study reward-poisoning attacks in this setting where an exogenous attacker modifies the rewards in the dataset before the agents see the dataset. The attacker wants to guide each agent into a nefarious target policy while minimizing the Lp norm of the reward modification. Unlike attacks on single-agent RL, we show that the attacker can install the target policy as a Markov Perfect Dominant Strategy Equilibrium (MPDSE), which rational agents are guaranteed to follow. This attack can be significantly cheaper than separate single-agent attacks. We show that the attack works on various MARL agents including uncertainty-aware learners, and we exhibit linear programs to efficiently solve the attack problem. We also study the relationship between the structure of the datasets and the minimal attack cost. Our work paves the way for studying defense in offline MARL.

IJCAI Conference 2022 Conference Paper

Game Redesign in No-regret Game Playing

• Yuzhe Ma
• Young Wu
• Xiaojin Zhu

We study the game redesign problem in which an external designer has the ability to change the payoff function in each round, but incurs a design cost for deviating from the original game. The players apply no-regret learning algorithms to repeatedly play the changed games with limited feedback. The goals of the designer are to (i) incentivize players to take a specific target action profile frequently; (ii) incur small cumulative design cost. We present game redesign algorithms with the guarantee that the target action profile is played in T-o(T) rounds while incurring only o(T) cumulative design cost. Simulations on four classic games confirm the ef- fectiveness of our proposed redesign algorithms.

JMLR Journal 2021 Journal Article

Policy Teaching in Reinforcement Learning via Environment Poisoning Attacks

• Amin Rakhsha
• Goran Radanovic
• Rati Devidze
• Xiaojin Zhu
• Adish Singla

We study a security threat to reinforcement learning where an attacker poisons the learning environment to force the agent into executing a target policy chosen by the attacker. As a victim, we consider RL agents whose objective is to find a policy that maximizes reward in infinite-horizon problem settings. The attacker can manipulate the rewards and the transition dynamics in the learning environment at training-time, and is interested in doing so in a stealthy manner. We propose an optimization framework for finding an optimal stealthy attack for different measures of attack cost. We provide lower/upper bounds on the attack cost, and instantiate our attacks in two settings: (i) an offline setting where the agent is doing planning in the poisoned environment, and (ii) an online setting where the agent is learning a policy with poisoned feedback. Our results show that the attacker can easily succeed in teaching any target policy to the victim under mild conditions and highlight a significant security threat to reinforcement learning agents in practice. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2021. ( edit, beta )

AAAI Conference 2021 Conference Paper

Sequential Attacks on Kalman Filter-based Forward Collision Warning Systems

• Yuzhe Ma
• Jon A Sharp
• Ruizhe Wang
• Earlence Fernandes
• Xiaojin Zhu

Kalman Filter (KF) is widely used in various domains to perform sequential learning or variable estimation. In the context of autonomous vehicles, KF constitutes the core component of many Advanced Driver Assistance Systems (ADAS), such as Forward Collision Warning (FCW). It tracks the states (distance, velocity etc.) of relevant traffic objects based on sensor measurements. The tracking output of KF is often fed into downstream logic to produce alerts, which will then be used by human drivers to make driving decisions in near-collision scenarios. In this paper, we study adversarial attacks on KF as part of the more complex machine-human hybrid system of Forward Collision Warning. Our attack goal is to negatively affect human braking decisions by causing KF to output incorrect state estimations that lead to false or delayed alerts. We accomplish this by sequentially manipulating measurements fed into the KF, and propose a novel Model Predictive Control (MPC) approach to compute the optimal manipulation. Via experiments conducted in a simulated driving environment, we show that the attacker is able to successfully change FCW alert signals through planned manipulation over measurements prior to the desired target time. These results demonstrate that our attack can stealthily mislead a distracted human driver and cause vehicle collisions.

AAAI Conference 2021 Conference Paper

The Sample Complexity of Teaching by Reinforcement on Q-Learning

• Xuezhou Zhang
• Shubham Bharti
• Yuzhe Ma
• Adish Singla
• Xiaojin Zhu

We study the sample complexity of teaching, termed as “teaching dimension” (TDim) in the literature, for the teachingby-reinforcement paradigm, where the teacher guides the student through rewards. This is distinct from the teachingby-demonstration paradigm motivated by robotics applications, where the teacher teaches by providing demonstrations of state/action trajectories. The teaching-by-reinforcement paradigm applies to a wider range of real-world settings where a demonstration is inconvenient, but has not been studied systematically. In this paper, we focus on a specific family of reinforcement learning algorithms, Q-learning, and characterize the TDim under different teachers with varying control power over the environment, and present matching optimal teaching algorithms. Our TDim results provide the minimum number of samples needed for reinforcement learning, and we discuss their connections to standard PAC-style RL sample complexity and teaching-by-demonstration sample complexity results. Our teaching algorithms have the potential to speed up RL agent learning in applications where a helpful teacher is available.

AAAI Conference 2020 Conference Paper

Optimal Attack against Autoregressive Models by Manipulating the Environment

• Yiding Chen
• Xiaojin Zhu

We describe an optimal adversarial attack formulation against autoregressive time series forecast using Linear Quadratic Regulator (LQR). In this threat model, the environment evolves according to a dynamical system; an autoregressive model observes the current environment state and predicts its future values; an attacker has the ability to modify the environment state in order to manipulate future autoregressive forecasts. The attacker’s goal is to force autoregressive forecasts into tracking a target trajectory while minimizing its attack expenditure. In the white-box setting where the attacker knows the environment and forecast models, we present the optimal attack using LQR for linear models, and Model Predictive Control (MPC) for nonlinear models. In the black-box setting, we combine system identification and MPC. Experiments demonstrate the effectiveness of our attacks.

IJCAI Conference 2019 Conference Paper

Data Poisoning against Differentially-Private Learners: Attacks and Defenses

• Yuzhe Ma
• Xiaojin Zhu
• Justin Hsu

Data poisoning attacks aim to manipulate the model produced by a learning algorithm by adversarially modifying the training set. We consider differential privacy as a defensive measure against this type of attack. We show that private learners are resistant to data poisoning attacks when the adversary is only able to poison a small number of items. However, this protection degrades as the adversary is allowed to poison more data. We emprically evaluate this protection by designing attack algorithms targeting objective and output perturbation learners, two standard approaches to differentially-private machine learning. Experiments show that our methods are effective when the attacker is allowed to poison sufficiently many training items.

AAAI Conference 2018 Conference Paper

Training Set Debugging Using Trusted Items

• Xuezhou Zhang
• Xiaojin Zhu
• Stephen Wright

Training set bugs are flaws in the data that adversely affect machine learning. The training set is usually too large for manual inspection, but one may have the resources to verify a few trusted items. The set of trusted items may not by itself be adequate for learning, so we propose an algorithm that uses these items to identify bugs in the training set and thus improves learning. Specifically, our approach seeks the smallest set of changes to the training set labels such that the model learned from this corrected training set predicts labels of the trusted items correctly. We flag the items whose labels are changed as potential bugs, whose labels can be checked for veracity by human experts. To find the bugs in this way is a challenging combinatorial bilevel optimization problem, but it can be relaxed into a continuous optimization problem. Experiments on toy and real data demonstrate that our approach can identify training set bugs effectively and suggest appropriate changes to the labels. Our algorithm is a step toward trustworthy machine learning.

AAAI Conference 2017 Conference Paper

Explicit Defense Actions Against Test-Set Attacks

• Scott Alfeld
• Xiaojin Zhu
• Paul Barford

Automated learning and decision making systems in publicfacing applications are vulnerable to malicious attacks. Examples of such systems include spam detectors, credit card fraud detectors, and network intrusion detection systems. These systems are at further risk of attack when money is directly involved, such as market forecasters or decision systems used in determining insurance or loan rates. In this paper, we consider the setting where a predictor Bob has a fixed model, and an unknown attacker Alice aims to perturb (or poison) future test instances so as to alter Bob’s prediction to her benefit. We focus specifically on Bob’s optimal defense actions to limit Alice’s effectiveness. We define a general framework for determining Bob’s optimal defense action against Alice’s worst-case attack. We then demonstrate our framework by considering linear predictors, where we provide tractable methods of determining the optimal defense action. Using these methods, we perform an empirical investigation of optimal defense actions for a particular class of linear models — autoregressive forecasters — and find that for ten real world futures markets, the optimal defense action reduces the Bob’s loss by between 78 and 97%.

IJCAI Conference 2017 Conference Paper

No Learner Left Behind: On the Complexity of Teaching Multiple Learners Simultaneously

• Xiaojin Zhu
• Ji Liu
• Manuel Lopes

We present a theoretical study of algorithmic teaching in the setting where the teacher must use the same training set to teach multiple learners. This problem is a theoretical abstraction of the real-world classroom setting in which the teacher delivers the same lecture to academically diverse students. We define a minimax teaching criterion to guarantee the performance of the worst learner in the class. We prove that the teaching dimension increases with class diversity in general. For the classes of conjugate Bayesian learners and linear regression learners, respectively, we exhibit corresponding minimax teaching set. We then propose a method to enhance teaching by partitioning the class into sections. We present cases where the optimal partition minimizes overall teaching dimension while maintaining the guarantee on all learners. Interestingly, we show personalized education (one learner per section) is not necessarily the optimal partition. Our results generalize algorithmic teaching to multiple learners and offer insight on how to teach large classes.

AAAI Conference 2016 Conference Paper

Data Poisoning Attacks against Autoregressive Models

• Scott Alfeld
• Xiaojin Zhu
• Paul Barford

Forecasting models play a key role in money-making ventures in many different markets. Such models are often trained on data from various sources, some of which may be untrustworthy. An actor in a given market may be incentivised to drive predictions in a certain direction to their own benefit. Prior analyses of intelligent adversaries in a machinelearning context have focused on regression and classification. In this paper we address the non-iid setting of time series forecasting. We consider a forecaster, Bob, using a fixed, known model and a recursive forecasting method. An adversary, Alice, aims to pull Bob’s forecasts toward her desired target series, and may exercise limited influence on the initial values fed into Bob’s model. We consider the class of linear autoregressive models, and a flexible framework of encoding Alice’s desires and constraints. We describe a method of calculating Alice’s optimal attack that is computationally tractable, and empirically demonstrate its effectiveness compared to random and greedy baselines on synthetic and realworld time series data. We conclude by discussing defensive strategies in the face of Alice-like adversaries.

IJCAI Conference 2016 Conference Paper

Stochastic Multiresolution Persistent Homology Kernel

• Xiaojin Zhu
• Ara Vartanian
• Manish Bansal
• Duy Nguyen
• Luke Brandl

We introduce a new topological feature representation for point cloud objects. Specifically, we construct a Stochastic Multiresolution Persistent Homology (SMURPH) kernel which represents an object's persistent homology at different resolutions. Under the SMURPH kernel two objects are similar if they have similar number and sizes of "holes" at these resolutions. Our multiresolution kernel can capture both global topology and fine-grained topological texture in the data. Importantly, on large point clouds the SMURPH kernel is more computationally tractable compared to existing topological data analysis methods. We demonstrate SMURPH's potential for clustering and classification on several applications, including eye disease classification and human activity recognition.

JMLR Journal 2016 Journal Article

The Teaching Dimension of Linear Learners

• Ji Liu
• Xiaojin Zhu

Teaching dimension is a learning theoretic quantity that specifies the minimum training set size to teach a target model to a learner. Previous studies on teaching dimension focused on version-space learners which maintain all hypotheses consistent with the training data, and cannot be applied to modern machine learners which select a specific hypothesis via optimization. This paper presents the first known teaching dimension for ridge regression, support vector machines, and logistic regression. We also exhibit optimal training sets that match these teaching dimensions. Our approach generalizes to other linear learners. [abs] [ pdf ][ bib ] &copy JMLR 2016. ( edit, beta )

AAAI Conference 2015 Conference Paper

Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education

• Xiaojin Zhu

AAAI Conference 2015 Conference Paper

Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners

• Shike Mei
• Xiaojin Zhu

We investigate a problem at the intersection of machine learning and security: training-set attacks on machine learners. In such attacks an attacker contaminates the training data so that a specific learning algorithm would produce a model profitable to the attacker. Understanding training-set attacks is important as more intelligent agents (e. g. spam filters and robots) are equipped with learning capability and can potentially be hacked via data they receive from the environment. This paper identifies the optimal training-set attack on a broad family of machine learners. First we show that optimal training-set attack can be formulated as a bilevel optimization problem. Then we show that for machine learners with certain Karush-Kuhn-Tucker conditions we can solve the bilevel problem efficiently using gradient methods on an implicit function. As examples, we demonstrate optimal training-set attacks on Support Vector Machines, logistic regression, and linear regression with extensive experiments. Finally, we discuss potential defenses against such attacks.

IJCAI Conference 2013 Conference Paper

Persistent Homology: An Introduction and a New Text Representation for Natural Language Processing

• Xiaojin Zhu

Persistent homology is a mathematical tool from topological data analysis. It performs multi-scale analysis on a set of points and identifies clusters, holes, and voids therein. These latter topological structures complement standard feature representations, making persistent homology an attractive feature extractor for artificial intelligence. Research on persistent homology for AI is in its infancy, and is currently hindered by two issues: the lack of an accessible introduction to AI researchers, and the paucity of applications. In response, the first part of this paper presents a tutorial on persistent homology specifically aimed at a broader audience without sacrificing mathematical rigor. The second part contains one of the first applications of persistent homology to natural language processing. Specifically, our Similarity Filtration with Time Skeleton (SIFTS) algorithm identifies holes that can be interpreted as semantic “tie-backs” in a text document, providing a new document structure representation. We illustrate our algorithm on documents ranging from nursery rhymes to novels, and on a corpus with child and adolescent writings.

IJCAI Conference 2013 Conference Paper

Socioscope: Spatio-Temporal Signal Recovery from Social Media (Extended Abstract)

• Jun-Ming Xu
• Aniruddha Bhargava
• Robert Nowak
• Xiaojin Zhu

Counting the number of social media posts on a target phenomenon has become a popular method to monitor a spatiotemporal signal. However, such counting is plagued by biased, missing, or scarce data. We address these issues by formulating signal recovery as a Poisson point process estimation problem. We explicitly incorporate human population bias, time delays and spatial distortions, and spatiotemporal regularization into the model to address the data quality issues. Our model produces qualitatively convincing results in a case study on wildlife roadkill monitoring.

TIST Journal 2012 Journal Article

Metric Learning for Estimating Psychological Similarities

• Jun-Ming Xu
• Xiaojin Zhu
• Timothy T. Rogers

An important problem in cognitive psychology is to quantify the perceived similarities between stimuli. Previous work attempted to address this problem with multidimensional scaling (MDS) and its variants. However, there are several shortcomings of the MDS approaches. We propose Yada, a novel general metric-learning procedure based on two-alternative forced-choice behavioral experiments. Our method learns forward and backward nonlinear mappings between an objective space in which the stimuli are defined by the standard feature vector representation and a subjective space in which the distance between a pair of stimuli corresponds to their perceived similarity. We conduct experiments on both synthetic and real human behavioral datasets to assess the effectiveness of Yada. The results show that Yada outperforms several standard embedding and metric-learning algorithms, both in terms of likelihood and recovery error.

IJCAI Conference 2011 Conference Paper

A Framework for Incorporating General Domain Knowledge into Latent Dirichlet Allocation Using First-Order Logic

• David Andrzejewski
• Xiaojin Zhu
• Mark Craven
• Benjamin Recht

Topic models have been used successfully for a variety of problems, often in the form of application-specific extensions of the basic Latent Dirichlet Allocation (LDA) model. Because deriving these new models in order to encode domain knowledge can be difficult and time-consuming, we propose the Fold·all model, which allows the user to specify general domain knowledge in First-Order Logic (FOL). However, combining topic modeling with FOL can result in inference problems beyond the capabilities of existing techniques. We have therefore developed a scalable inference technique using stochastic gradient descent which may also be useful to the Markov Logic Network (MLN) research community. Experiments demonstrate the expresive power of Fold·all, as well as the scalability of our proposed inference method.

AAAI Conference 2011 Conference Paper

Co-Training as a Human Collaboration Policy

• Xiaojin Zhu
• Bryan Gibson
• Timothy Rogers

AAAI Conference 2011 Conference Paper

OASIS: Online Active Semi-Supervised Learning

• Andrew Goldberg
• Xiaojin Zhu
• Alex Furger
• Jun-Ming Xu

We consider a learning setting of importance to large scale machine learning: potentially unlimited data arrives sequentially, but only a small fraction of it is labeled. The learner cannot store the data; it should learn from both labeled and unlabeled data, and it may also request labels for some of the unlabeled items. This setting is frequently encountered in real-world applications and has the characteristics of online, semi-supervised, and active learning. Yet previous learning models fail to consider these characteristics jointly. We present OASIS, a Bayesian model for this learning setting. The main contributions of the model include the novel integration of a semi-supervised likelihood function, a sequential Monte Carlo scheme for efficient online Bayesian updating, and a posterior-reduction criterion for active learning. Encouraging results on both synthetic and real-world optical character recognition data demonstrate the synergy of these characteristics in OASIS.

AAAI Conference 2008 Conference Paper

Online Learning in Monkeys

• Xiaojin Zhu
• Shelley Prudom

IJCAI Conference 2007 Conference Paper

• Jurgen Van Gael
• Xiaojin Zhu

The crosslingual link detection problem calls for identifying news articles in multiple languages that report on the same news event. This paper presents a novel approach based on constrained clustering. We discuss a general way for constrained clustering using a recent, graph-based clustering framework called correlation clustering. We introduce a correlation clustering implementation that features linear program chunking to allow processing larger datasets. We show how to apply the correlation clustering algorithm to the crosslingual link detection problem and present experimental results that show correlation clustering improves upon the hierarchical clustering approaches commonly used in link detection, and, hierarchical clustering approaches that take constraints into account.

AAAI Conference 2007 Conference Paper

A Text-to-Picture Synthesis System for Augmenting Communication

• Xiaojin Zhu
• Mohamed Eldawy

We present a novel Text-to-Picture system that synthesizes a picture from general, unrestricted natural language text. The process is analogous to Text-to-Speech synthesis, but with pictorial output that conveys the gist of the text. Our system integrates multiple AI components, including natural language processing, computer vision, computer graphics, and machine learning. We present an integration framework that combines these components by first identifying informative and ‘picturable’ text units, then searching for the most likely image parts conditioned on the text, and finally optimizing the picture layout conditioned on both the text and image parts. The effectiveness of our system is assessed in two user studies using children’s books and news articles. Experiments show that the synthesized pictures convey as much information about children’s stories as the original artists’ illustrations, and much more information about news articles than their original photos alone. These results suggest that Text-to-Picture synthesis has great potential in augmenting human-computer and human-human communication modalities, with applications in education and health care, among others.

AAAI Conference 2007 Conference Paper

Humans Perform Semi-Supervised Classification Too

• Xiaojin Zhu
• Ruichen Qian

We explore the connections between machine learning and human learning in one form of semi-supervised classification. 22 human subjects completed a novel 2class categorization task in which they were first taught to categorize a single labeled example from each category, and subsequently were asked to categorize, without feedback, a large set of additional items. Stimuli were visually complex and unrecognizable shapes. The unlabeled examples were sampled from a bimodal distribution with modes appearing either to the left (leftshift condition) or right (right-shift condition) of the two labeled examples. Results showed that, although initial decision boundaries were near the middle of the two labeled examples, after exposure to the unlabeled examples, they shifted in different directions in the two groups. In this respect, the human behavior conformed well to the predictions of a Gaussian mixture model for semi-supervised learning. The human behavior differed from model predictions in other interesting respects, suggesting some fruitful avenues for future inquiry.

AAAI Conference 2007 Conference Paper

Kernel Regression with Order Preferences

• Xiaojin Zhu

We propose a novel kernel regression algorithm which takes into account order preferences on unlabeled data. Such preferences have the form that point x1 has a larger target value than that of x2, although the target values for x1, x2 are unknown. The order preferences can be viewed as side information or a form of weak labels, and our algorithm can be related to semi-supervised learning. Learning consists of formulating the order preferences as additional regularization in a risk minimization framework. We define a linear program to effectively solve the optimization problem. Experiments on benchmark datasets, sentiment analysis, and housing price problems show that the proposed algorithm outperforms standard regression, even when the order preferences are noisy.