we could use forwards-backwards algorithm for exact inference in this model (Sutton and McCallum, 2012).
forwards-backwards on a sequence containing T units costs where M is the number of relations in our relation set.