Brian Ziebart

Overview

Research

Theory:

• Maximum Causal Entropy
  Conditional random fields can be viewed as maximizing the conditional entropy of predicted variables given provided variables. They provide state-of-the-art predictive accuracy in a number of tasks. What distribution is appropriate when provided variables are not availale up front, but sequentially revealed according to a known process instead? Our maximum causal entropy paper introduces an answer to this question. It was the best student paper runner-up at ICML 2010.
  Perspectives: ,
  Statistical Estimation Perspective of Maximum Causal Entropy
  
  Consider a joint distribution, P(Y,X). It can factor sequentially over time as a product of conditional probabilities,
  
  

  P(Y,X) = ∏_t P(Y_t,X_t|Y_1:t-1,X_1:t-1) = ∏_t P(Y_t|Y_1:t-1,X_1:t) ∏_t P(X_t|Y_1:t-1,X_1:t-1).

  
  These two products are each causally conditioned probabilities, denoted:
  
  

  P(Y^T||X^T) = ∏_t P(Y_t|Y_1:t-1,X_1:t)
  P(X^T||Y^T-1) = ∏_t P(X_t|Y_1:t-1,X_1:t-1).

  
  We are interested in estimating the first process, P̂(Y^T||X^T), given the second process, P(X^T||Y^T-1), and samples from the joint distribution, P̃(Y,X). The log-loss minimizer, min_P̂(y||x) -∑_y,x P(y,x) log P̂(y||x), employs a natural measure to try to minimize. Unfortunately, P(Y,X) is unknown and employing P̃(Y,X) as a substitute will often overfit to the available data. Statistics of the form E_P(Y,X)[F(y,x)] characterizing P(Y,X) may exist that are easier to estimate from P̃(Y,X). We will assume that (unknown) P(Y,X) is adversarially chosen but must: (1) factor according to the known P(X^T||Y^T-1); and (2) match a set of statistics with distribution P̃(Y,X). The objective of this optimization in this adversarial log-loss minimization setting (subject to constraints: ∀k, E_P(Y,X)[F(y,x)] = E_P̃(Y,X)[F(y,x)]) is:
  
  

  min_{P̂(Y^T||X^T)} max_P(Y^T||X^T) -∑ P(y,x) log P̂(y||x)
  = max_P(Y^T||X^T) min_{P̂(Y^T||X^T)} -∑ P(y,x) log P̂(y||x)
  = max_P(Y^T||X^T) -∑ P(y,x) log P(y||x)
  

  
  This last measure is the causal entropy, H(Y||X) = -∑ P(y,x) log P(y||x). Thus, robustly minimizing the log-loss of a predictor is equivalent to obtaining a probability distribution that maximizes the causal entropy.
  Decision Theoretic Perspective of Maximum Causal Entropy
  
  In a sequential decision making task, the optimal decision problem is to find the optimal action, a, to employ in each state, s. The optimal expected future values for states, V(s), and actions, Q(s,a), are specified by the Bellman equations:
  
  

  V(s) = max_a Q(s,a)
  Q(s,a) = Reward(s,a) + ∑_s' P(s'|s,a) V(s'),

  
  with optimal policy: π(s) = max_a Q(s,a).
  
  When maximizing the causal entropy, H(A||S), subject to constraints of the form E_P(A,S)[∑_t f(a_t,s_t)] = E_P(A,S)[∑_t f(a_t,s_t)], the resulting distribution is very similar to the Bellman-optimal solution. It has the following form:
  
  

  V(s) = softmax_a Q(s,a)
  Q(s,a) = Reward(s,a) + ∑_s' P(s'|s,a) V(s'),

  
  with reward function: Reward(s,a) = θ^T f_s,a. The softmax is a smooth interpolation of the max function, softmax_x f(x) = log ∑_x e^f(x). The corresponding policy is then stochastic and distributed as: π(a|s) = e^Q(s,a)-V(s).
  
  
  
• Behavior Imitation Learning
  Behaving like an observed actor given only a small amount of observed behavior is an important artificial intelligence task. My approach is to learn good predictive distributions of actor behavior. Maximum causal entropy provides the right log-loss guarantees when conditioned on a Markov decision process. It learns a feature-based reward function so that a probabilistic relaxation of optimal control matches statistics of observed behavior. When state transition dynamics are deterministic, this reduces to the distribution we employed in our paper, Maximum Entropy Inverse Reinforcement Learning, at AAAI 2008,
  
  
• Strategy Learning
  In multi-agent games, rationality is defined in terms of regret rather than maximal utility. How can predictive imitation learning techniques be extended to this setting? Our computational rationalization paper at ICML 2011, which won the best paper award, introduces such an extension that learns feature-based payoffs that rationalize observed strategies. Our maximum causal entropy correlated equilibria paper at AAMAS 2011 applies the principle of maximum causal entropy to Markov games with known payoffs to obtain robust predictions of rational behavior.
  
  
• Bayesian Network Structure Learning
  
  In structure learning, the edges of a Bayesian network relating variables are learned from data. we present polynomial inference algorithms (MAP structure estimation and Bayesian model averaging) for selectively conditioned forests (c) -- the combination of tree structures (a) and ordered variable sets (b), enabling generalized naïve Bayes classifier learning in our UAI 2007 paper on selectively conditioned forests.
  
  

Applications:

• Pedestrian Trajectory Forecasting
  We improve robots' movements around people by endowing them with capabilities like you and I have -- mental models of where people intend to go and how they intend to get there.
  [フレーム] [フレーム]
  Using these purposeful predictive models, robots can find better balances between efficiently accomplishing their tasks and hindering people moving in the same environment in our paper, Planning-based Pedestrian Prediction, at IROS 2009.
  
  
• Assistive Navigation Systems
  Existing personal navigation devices (PNDs) are largely oblivious - they "ride along" with drivers, but ignore everything about how the drivers actually drive: where they go and how they prefer to get there.
  [フレーム] [フレーム]
  We develop navigation technology that reasons about observed driving to learn the driver's preferences and predict their future paths (to warn about unanticipated hazards). We applied these learning techniques on GPS data gathered from Pittsburgh taxi drivers in our Ubicomp 2008 paper, Navigate Like a Cabbie. We conducted additional experiments on this dataset in our paper at AAAI 2008 and our paper at AISTATS 2009. We also investigated techniques for reusing previous plans from planning tasks with different cost function weights to improve planning speed on new planning tasks with previously unseen cost function weights in our paper, Fast Planning for Dynamic Preferences, at ICAPS 2008.
  
  
• Pervasive Computing Environments
  As an undergraduate, I developed distributed applications for a middleware-based meta-operating system. Our papers discuss composing applications, rapid development, and evaluation metrics. I became interested in how machine learning could be used to automatically configure these systems. My paper, Learning Automation Policies for Pervasive Computing Environments, from ICAC 2005 discusses the latter topic.

Publications

@inproceedings{ziebart2012probabilistic,
 author = {Brian D. Ziebart and Anind K. Dey and J. Andrew Bagnell},
 title = {Probabilistic Pointing Target Prediction via Inverse Optimal 
 Control},
 year = {2012},
 booktitle = {Proc. of the International Conference on Intelligent User 
 Interfaces} 
}

@inproceedings{ziebart2011process,
 author = {Brian D. Ziebart},
 title = {Factorized Decision Forecasting via Combining Value-based
 and Reward-based Estimation},
 year = {2011},
 booktitle = {Proc. of the Allerton Conference on Communications,
 Control and Computing}
}

@inproceedings{ziebart2011process,
 author = {Brian D. Ziebart},
 title = {Process-Conditioned Investing with Incomplete Information
 using Maximum Causal Entropy},
 year = {2011},
 booktitle = {Proc. of the International Workshop on Bayesian Inference and
 Maximum Entropy Methods in Science and Engineering}
}

@inproceedings{waugh2011computational,
 author = {Kevin Waugh and Brian D. Ziebart and J. Andrew Bagnell},
 title = {Computational Rationalization: The Inverse Equilibrium Problem},
 year = {2011},
 booktitle = {Proc. of the International Conference on Machine Learning} 
}

@inproceedings{ziebart2011maximum,
 author = {Brian D. Ziebart and J. Andrew Bagnell and Anind K. Dey},
 title = {Maximum Causal Entropy Correlated Equilibria for {M}arkov Games},
 year = {2011},
 booktitle = {Proc. of the International Conference on Autonomous Agents
 and Multiagent Systems}
}

@inproceedings{davidoff2011learning,
 author = {Scott Davidoff and Brian D. Ziebart and John Zimmerman and 
 Anind K. Dey},
 title = {Learning Patterns of Pick-ups and Drop-offs to Support Busy
 Family Coordination},
 year = {2011},
 booktitle = {Proc. of the SIG CHI Conference on Human Factors in Computing
 Systems} 
}

@phdthesis{ziebart2010modelingB},
 author = {Brian D. Ziebart},
 title = {Modeling Purposeful Adaptive Behavior with the Principle of
 Maximum Causal Entropy},
 year = {2010},
 month = {Dec},
 school = {Machine Learning Department, Carnegie Mellon University}
}

@inproceedings{ziebart2010modeling,
 author = {Brian D. Ziebart and J. Andrew Bagnell and Anind K. Dey},
 title = {Modeling Interaction via the Principle of Maximum Causal Entropy}, 
 year = {2010},
 booktitle = {Proc. of the International Conference on Machine Learning},
 pages = {1255--1262}
}

@inproceedings{bziebart2009planning,
 author = {Brian D. Ziebart and Nathan Ratliff and Garratt Gallagher and
 Christoph Mertz and Kevin Peterson and J. Andrew Bagnell and 
 Martial Hebert and Anind K. Dey and Siddhartha Srinivasa},
 title = {Planning-based Prediction for Pedestrians},
 year = {2009},
 booktitle = {Proc. of the International Conference on Intelligent Robotsi
 and Systems}
}

@inproceedings{ratliff2009inverse,
 author = {Nathan Ratliff and Brian Ziebart and Kevin Peterson and 
 J. Andrew Bagnell and Martial Hebert and Anind K. Dey and
 Siddhartha Srinivasa},
 title = {Inverse Optimal Heuristic Control for Imitation Learning},
 year = {2009},
 booktitle = {Proc. AISTATS},
 pages = {424--431}
}

@inproceedings{bziebart2008navigate,
 author = {Brian D. Ziebart and Andrew Maas 
 and J. Andrew Bagnell and Anind K. Dey},
 title = {Navigate Like a Cabbie: Probabilistic Reasoning from 
 Observed Context-Aware Behavior},
 year = {2008},
 booktitle = {Proc. Ubicomp},
 pages = {322--331}
}

@inproceedings{ziebart2008fast,
 author = {Brian D. Ziebart and J. Andrew Bagnell and Anind K. Dey},
 title = {Fast Planning for Dynamic Preferences},
 year = {2008},
 booktitle = {Proc. of International Conference on Auomated Planning
 and Scheduling},
 pages = {412--419}
}

@inproceedings{ziebart2008maximum,
 author = {Brian D. Ziebart and Andrew Maas 
 and J. Andrew Bagnell and Anind K. Dey},
 title = {Maximum Entropy Inverse Reinforcement Learning},
 year = {2008},
 booktitle = {Proc. AAAI},
 pages = {1433--1438}
}

@inproceedings{bziebart2007learning,
 author = {Brian D. Ziebart and Anind K. Dey and J. Andrew Bagnell},
 title = {Learning Selectively Conditioned Forest Structures with 
 Applications to DBNs and Classification},
 year = {2007},
 booktitle = {Proc. UAI},
 pages = {458--465}
}

@inproceedings{bziebart2005learning,
 author = {Brian D. Ziebart and Dan Roth and Roy H. Campbell and 
 Anind K. Dey},
 title = {Learning Automation Policies for Pervasive Computing Environments},
 year = {2005},
 booktitle = {Proc. of the International Conference on Autonomic Computing} 
}