Hidden Markov Models

We present a general encoding of Hidden Markov models in ProbLog, with three examples. The only differences between the programs are their model and queries sections, all the background knowledge is the same.

The first example is our earlier weather example extended with whether an umbrella is taken or not based on the weather.

%%%%%%%%%% % model % - start(modelID,state) complete AD % - trans(modelID,time,fromState,toState) possibly incomplete AD per fromState % - emit(modelID,time,state,symbol) possibly incomplete AD per state %%%%%%%%%% % example 1: weather (with umbrella yes/no added) 0.5::start(weather,sun); 0.5::start(weather,rain). 0.6::trans(weather,T,sun,sun); 0.4::trans(weather,T,sun,rain). 0.2::trans(weather,T,rain,sun); 0.8::trans(weather,T,rain,rain). 0.9::emit(weather,T,sun,no); 0.1::emit(weather,T,sun,yes). 0.1::emit(weather,T,rain,no); 0.9::emit(weather,T,rain,yes). %%%%%%%%% % background: which state are we in at which time? % state(modelID,time,state) %%%%%%%%% state(A,0,S) :- start(A,S). state(A,T,S) :- T > 0, TT is T-1, state(A,TT,S2), trans(A,TT,S2,S). %%%%%%%%% % background: which symbol do we see at which time? % observe(modelID,time,symbol) %%%%%%%%% observe(A,T,S) :- state(A,T,State),emit(A,T,State,S). %%%%%%%%% % running the model to generate a sequence of labels % observe_sequence(modelID,list_of_symbols) %%%%%%%%% observe_sequence(TS,[First|List]) :- start(TS,State), emit(TS,0,State,First), ob_seq(TS,State,List,0). % stop ob_seq(_,_,[],_). % keep going: add H to output, go to next time and state ob_seq(TS,State,[H|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, emit(TS,TT,State2,H), ob_seq(TS,State2,Tail,TT). %%%%%%%%% % running the model to generate a sequence of states % state_sequence(modelID,list_of_states) %%%%%%%%% state_sequence(TS,[State|List]) :- start(TS,State), st_seq(TS,State,List,0). % stop st_seq(_,_,[],_). % keep going: add H to output, go to next time and state st_seq(TS,State,[State2|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, st_seq(TS,State2,Tail,TT). %%%%%%%%% % queries %%%%%%%%% query(observe_sequence(weather,L)) :- between(0,2,N),length(L,N). query(state_sequence(weather,L)) :- between(0,2,N),length(L,N). query(state(weather,T,_)) :- between(0,2,T). query(observe(weather,T,_)) :- between(0,2,T).

The second example emits strings over {a,b,c,d,e}.

%%%%%%%%%% % model % - start(modelID,state) complete AD % - trans(modelID,time,fromState,toState) possibly incomplete AD per fromState % - emit(modelID,time,state,symbol) possibly incomplete AD per state %%%%%%%%%% % example 2: ring of five letters, going left or right, emitting letters based on distance start(letters,a). 0.5::trans(letters,T,M,L); 0.5::trans(letters,T,M,R) :- nbs(_,L,M,R,_). nbs(a,b,c,d,e). nbs(b,c,d,e,a). nbs(c,d,e,a,b). nbs(d,e,a,b,c). nbs(e,a,b,c,d). 0.1::emit(letters,T,M,LL); 0.2::emit(letters,T,M,L); 0.4::emit(letters,T,M,M); 0.2::emit(letters,T,M,R); 0.1::emit(letters,T,M,RR) :- nbs(LL,L,M,R,RR). %%%%%%%%% % background: which state are we in at which time? % state(modelID,time,state) %%%%%%%%% state(A,0,S) :- start(A,S). state(A,T,S) :- T > 0, TT is T-1, state(A,TT,S2), trans(A,TT,S2,S). %%%%%%%%% % background: which symbol do we see at which time? % observe(modelID,time,symbol) %%%%%%%%% observe(A,T,S) :- state(A,T,State),emit(A,T,State,S). %%%%%%%%% % running the model to generate a sequence of labels % observe_sequence(modelID,list_of_symbols) %%%%%%%%% observe_sequence(TS,[First|List]) :- start(TS,State), emit(TS,0,State,First), ob_seq(TS,State,List,0). % stop ob_seq(_,_,[],_). % keep going: add H to output, go to next time and state ob_seq(TS,State,[H|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, emit(TS,TT,State2,H), ob_seq(TS,State2,Tail,TT). %%%%%%%%% % running the model to generate a sequence of states % state_sequence(modelID,list_of_states) %%%%%%%%% state_sequence(TS,[State|List]) :- start(TS,State), st_seq(TS,State,List,0). % stop st_seq(_,_,[],_). % keep going: add H to output, go to next time and state st_seq(TS,State,[State2|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, st_seq(TS,State2,Tail,TT). %%%%%%%%% % queries %%%%%%%%% query(observe_sequence(letters,L)) :- between(0,2,N),length(L,N). query(state_sequence(letters,L)) :- between(0,2,N),length(L,N). query(state(letters,T,_)) :- between(0,2,T). query(observe(letters,T,_)) :- between(0,2,T).

The third example is from Pfeffer et al, Lazy Factored Inference for Functional Probabilistic Programming, arxiv 2015. It has 15 states (with identifiers 0 to 14) with the following connection pattern. States 0 and 14 are sinks, and from any other state s, there are two outgoing transitions, one to s+1 with probability s/14, and the other one to s-1. Each state s emits true with probability s/14 and false else. They are interested in whether state 0 or 14 is reached first, given evidence on the first few truth values. As these are queries with infinite support, but ProbLog requires finite support at this point, we restrict queries to a fixed number of steps here.

%%%%%%%%%% % model % - start(modelID,state) complete AD % - trans(modelID,time,fromState,toState) possibly incomplete AD per fromState % - emit(modelID,time,state,symbol) possibly incomplete AD per state %%%%%%%%%% :- use_module(library(lists)). state(S) :- between(0,14,S). start(line,S) :- findall(X,state(X),L),select_uniform(init,L,S,_). % start distribution not mentionned in paper, assume uniform % state s emits 1 with s/14, and 0 else % i.e., right sink emits 1 and left sink emits 0 for sure P1::emit(line,T,S,1) ; P2::emit(line,T,S,0) :- P1 is S/14, P2 is 1-P1. % from intermediate state s, transition upwards with s/14, and downwards else P::trans(line,T,S,SL) ; PP::trans(line,T,S,SR) :- between(1,13,S), SL is S-1, SR is S+1, PP is S/14, P is 1-PP. trans(line,_,0,0). trans(line,_,14,14). %%%%%%%%% % background: which state are we in at which time? % state(modelID,time,state) %%%%%%%%% state(A,0,S) :- start(A,S). state(A,T,S) :- T > 0, TT is T-1, state(A,TT,S2), trans(A,TT,S2,S). %%%%%%%%% % background: which symbol do we see at which time? % observe(modelID,time,symbol) %%%%%%%%% observe(A,T,S) :- state(A,T,State),emit(A,T,State,S). %%%%%%%%% % running the model to generate a sequence of labels % observe_sequence(modelID,list_of_symbols) %%%%%%%%% observe_sequence(TS,[First|List]) :- start(TS,State), emit(TS,0,State,First), ob_seq(TS,State,List,0). % stop ob_seq(_,_,[],_). % keep going: add H to output, go to next time and state ob_seq(TS,State,[H|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, emit(TS,TT,State2,H), ob_seq(TS,State2,Tail,TT). %%%%%%%%% % running the model to generate a sequence of states % state_sequence(modelID,list_of_states) %%%%%%%%% state_sequence(TS,[State|List]) :- start(TS,State), st_seq(TS,State,List,0). % stop st_seq(_,_,[],_). % keep going: add H to output, go to next time and state st_seq(TS,State,[State2|Tail],Time) :- trans(TS,Time,State,State2), TT is Time+1, st_seq(TS,State2,Tail,TT). %%%%%%%%% % queries %%%%%%%%% evidence(observe(line,0,1)). evidence(observe(line,1,0)). evidence(observe(line,2,1)). query(state(line,T,0)) :- time(T). query(state(line,T,14)) :- time(T). time(6).

Basic Inference

Parameter learning

Sampling

MPE Inference

Decision-Theoretic ProbLog

Examples from tutorial slides

Various examples

Advanced concepts

Python recipes