Maintaining State: Optimisations
Using the techniques of Chap. 3 one can build a working spoken dialogue system for some limited real-world situations. There are still, however, significant computational difficulties when dealing with large state spaces. In particular, the Loopy Belief P
- PDF / 239,940 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 15 Downloads / 233 Views
Maintaining State: Optimisations
Using the techniques of Chap. 3 one can build a working spoken dialogue system for some limited real-world situations. There are still, however, significant computational difficulties when dealing with large state spaces. In particular, the Loopy Belief Propagation algorithm does not scale well when individual nodes have very large numbers of values. This chapter will discuss methods for improving the tractability of the standard algorithm. The essential idea of these methods is that the values in a node will be joined into groups which are all given the same belief. This will constitute an approximation of the true marginal but will result in significantly less computation because the beliefs for a given group need only be calculated once. Throughout this chapter, the focus will be on updating the approximation for a given factor. For the sake of clarity, the notation denoting the factor under consideration will be removed during this chapter. Hence the cavity distribution is denoted q \ , the factor is f and the approximating function is fˆ. The majority of Algorithm 1 will stay the same. There is still an iteration through factors and cavity distributions will be computed as before. What changes is the computation of the factor approximations. Figure 4.1 shows a portion of a factor graph as an example factor to be updated. Only the variables connected to the factor are considered, since they are the only ones which will have any effect (See Sect. 3.5). The variables are X = (X 1 , X 2 , . . . , X m ), variable values are x = (x1 , x2 , . . . , xm ), factor approximations are fˆ(xi ) and cavity distributions are q \ (xi ).
4.1 Expectation Propagation If the values are to be grouped together, it is not necessarily obvious how the Loopy Belief Propagation algorithm should be altered to incorporate this. The LBP algorithm was defined by matching marginal distributions between an approximation and a target. When the values are grouped together, which of the marginals should be matched? B. Thomson, Statistical Methods for Spoken Dialogue Management, Springer Theses, DOI: 10.1007/978-1-4471-4923-1_4, © Springer-Verlag London 2013
45
46
4 Maintaining State: Optimisations
Fig. 4.1 A portion of a factor graph
X2
X1 Xm
X3 …
An alternative to simply matching marginals must be found to decide this issue. In the more general situation of arbitrary approximations, one would like to replace exact matching with minimizing a distance function. The distance to be minimized will be between two probability distributions and as such it is called a divergence measure. An appropriate divergence measure is given by the Expectation Propagation algorithm (EP) (Minka 2001). The distance measure chosen in EP is the KL-divergence, which is defined for two functions p(x) and q(x) to be, K L( p||q) =
p(x) log x
p(x) dx. q(x)
(4.1)
Note that the KL-divergence, as with many divergence-measures, is not the same if the order of the functions is swapped (it is not symmetric). Using this measure, the
Data Loading...
