Problem 637209 · hard · Level 06 Heuristics & Optimization

Predict the Robot's Next Move

Markov chain · higher-order Markov model · smoothing · held-out log-likelihood · model selection

A warehouse robot logs every action it takes as one letter ("a" for approach, "b" for grab, and so on). Its controller is a black box, but the engineers suspect that each action depends on the last few actions. They want a model that gives, for any recent history, a probability for every possible next action, so they can flag surprising behaviour.

Write train_predictor(train, alphabet). train is a long string of actions and alphabet a string of all possible actions. Return a function predict(history) that takes a string of the most recent actions (the last 6, or fewer at the very start) and returns a dict with one entry per letter of alphabet: the probability that it is the next action. Every probability must be positive and they must add up to 1.

Each test calls sequence_trial(train_predictor, case) from the setup. It trains your predictor on the training sequence of test case (3000 to 6000 actions), then walks through 4000 new actions of the same robot and reports the average natural log of the probability your predictor gave to the action that came next ("loglik", higher is better). You can look at a training sequence with action_log(case), and call sequence_trial yourself with Run.

Examples

Input:  sequence_trial(train_predictor, 1)
Output: for example {"loglik": -0.93, "plain": -1.346, "true": -0.839, "symbols": 4000}
Explanation: predicting from the last action alone scores -1.346 per action; the
robot's real controller would score -0.839.

How this problem is scored

  • Baseline: the next action predicted from the last action only, with probabilities (count(a -> s) + 1) / (count(a -> anything) + len(alphabet)) from the training sequence (a plain Markov chain with add-one smoothing). Its score is "plain". You pass a test when your "loglik" is at least as high.
  • Best known: the score of the robot's true controller ("true").
  • Score: 100 * (loglik - plain) / (true - plain), from 0 at the baseline to 100 at (or above) the true controller.

Constraints

  • 3 to 6 possible actions, 3000 to 6000 training actions
  • predict is called 4000 times per test; keep it fast (look up precomputed counts) and do not use the clock

Goals

  • Estimate next-symbol probabilities from a long sequence by counting
  • Decide how much history to condition on, trading bias against variance
  • Keep every probability positive with smoothing, and judge the model on unseen data
Starting Python…