Agent Behavior Prediction and Its Generalization Analysis

Authors

  • Fei Tian University of Science and Technology of China
  • Haifang Li Chinese Academy of Sciences
  • Wei Chen Microsoft Research
  • Tao Qin Microsoft Research
  • Enhong Chen University of Science and Technology of China
  • Tie-Yan Liu Microsoft Research

DOI:

https://doi.org/10.1609/aaai.v28i1.8914

Keywords:

generalization analysis, agent behavior model prediction, Markov Chain in Random Environments, empirical risk minimization algorithm

Abstract

Machine learning algorithms have been applied to predict agent behaviors in real-world dynamic systems, such as advertiser behaviors in sponsored search and worker behaviors in crowdsourcing. Behavior data in these systems are generated by live agents: once systems change due to adoption of prediction models learnt from behavior data, agents will observe and respond to these changes by changing their own behaviors accordingly. Therefore, the evolving behavior data will not be identically and independently distributed, posing great challenges to theoretical analysis. To tackle this challenge, in this paper, we propose to use Markov Chain in Random Environments (MCRE) to describe the behavior data, and perform generalization analysis of machine learning algorithms on its basis. We propose a novel technique that transforms the original time-variant MCRE into a higher-dimensional time-homogeneous Markov chain, which is easier to deal with. We prove the convergence of the new Markov chain when time approaches infinity. Then we obtain a generalization bound for the machine learning algorithms on the behavior data generated by the new Markov chain. To the best of our knowledge, this is the first work that performs the generalization analysis on data generated by complex processes in real-world dynamic systems.

Downloads

Published

2014-06-21

How to Cite

Tian, F., Li, H., Chen, W., Qin, T., Chen, E., & Liu, T.-Y. (2014). Agent Behavior Prediction and Its Generalization Analysis. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8914

Issue

Section

Main Track: Machine Learning Applications