Probabilistic Deterministic Infinite Automata

The Probabilistic Deterministic Infinite Automaton (PDIA) is a nonparametric model that defines a prior distribution over all probablistic deterministic finite automata (PDFA). Similar to a Hidden Markov Model, a PDFA sampled from the PDIA defines a prior probability over sequences. The key difference from Hidden Markov Models is that, conditioned on data, there is no uncertainty in the latent state sequence.

(define vocabulary '(chef omelet soup eat work bake))

(define top-level (DPmem 10.0 gensym))

(define symbol->state-distribution
  (mem (lambda (symbol) (DPmem 10.0 top-level))))

(define state/symbol->next-state
  (mem (lambda (state symbol) ((symbol->state-distribution symbol)))))

(define state->observation-model
  (mem (lambda (state) 
    (dirichlet (make-list (length vocabulary) 1.0)))))

(define (observation state) 
  (multinomial vocabulary (state->observation-model state)))

(define (sample-words last-state) 
  (if (flip 0.1) 
    '()
    (let ((word (observation last-state)))
      (pair word 
        (sample-words (state/symbol->next-state last-state word))))))

(sample-words 'start)