How local particle filters can be used to solve filtering and smoothing problems in Hidden Markov Models

如何使用局部粒子滤波器解决隐马尔可夫模型中的滤波和平滑问题

基本信息

批准号：
1961576
负责人：
金额：
--
依托单位：
University of Bristol
依托单位国家：
英国
项目类别：
Studentship
财政年份：
2017
资助国家：
英国
起止时间：
2017 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=studentship-1961576
关键词：
How local particle filters used

项目摘要

Abstract(no more than 4,000 characters inc spaces) Hidden Markov Models (HMM) can be applied widely in real life, from traffic models to different biological and neural models. This fitting with reality has increased the demand of precise and efficient algorithms to solve the filtering and the smoothing problems. The literature offers different methods to work out the filtering and the smoothing distribution of the underlying model, though when the dimension increases two problems are revealed. Firstly, as outspread in the paper by Rebeschini, Van Handel et al. (Can local particle filters beat the curse of dimensionality?, 2015), the particle filter (a well-know algorithm that estimates the filtering distribution) is affected by the curse of dimensionality. Secondly, even if the quantities of interest can be calculated in a close form the growth in the dimension could make the computational cost unfeasible. As explained in detail by Rebeschini, Van Handel et al. (2015), it is possible to prevent this problem by developing local particle filters with a dimension-free error, which has also the advantage of being computationally cheaper.The starting point of the research is the HMM where the hidden Markov chain is an n-dimensional sequence of 0's and 1's. Given that the state space is the product space of {0, 1} (n-times) , it can be easily recognized that the dimension is 2 to the power of n, meaning that the curse of dimensionality can be an issue. Since the state space is finite, the filtering and the smoothing distributions are available after forward and a backward step. However these operations involve handling matrices with 2 to the n rows and 2 to the n columns that are too expensive from a computational point of view. A possible work around to this is to introduce an error to increase the speed of the algorithm. This approximation can be found by assuming the existence of a local structure inside the model and considering a particular factorization of the observation distribution. The first thing is assuming that the Markov process X, for a fixed time, admits a local structure, meaning that each component is somehow caused by only a set of neighbors. The second assumption is that the process Y for a fixed time is drawn from a distribution G that admits a nondegenerative representation, meaning that exists a positive observation density g which factorizes. The last assumption is the factorization of the initial measure. These assumptions allow to redefine the forward step as working only on matrices with reduced dimension and with a low approximation error. Having ensured that the corresponding implementation works properly, the next aim will be to modify the EM algorithm to also include the cases in which all the parameters of the model (initial distribution, transition kernel, etc.) are unknown. This specific case has an application to traffic models. Indeed, in the temporal evolution of a network of roads each edge can be modeled by a component with a value that can be either congested or not congested. Of course this state of a road is not achievable, therefore only the number of cars for each road is observed. In this specific case the local structure is a reasonable assumption, because the traffic in a road is influenced only by the closest ones. The next step would be to apply the algorithm to this freeway traffic model, using data from the real world.As natural continuation of the research, it will be interesting to study generalization of this algorithm. So trying to apply the approximation not only to the "ideal" finite state space, but also to more general spaces. If that is possible, the method can be adapted to a huge range of applications.

摘要（不超过4,000个字符INC空间）隐藏的马尔可夫模型（HMM）可以在现实生活中广泛应用，从交通模型到不同的生物学和神经模型。这种与现实的融合增加了精确有效的算法的需求，以解决过滤和平滑问题。文献提供了不同的方法来计算过滤和基础模型的平滑分布，尽管当尺寸增加了两个问题时。首先，范·汉德尔（Van Handel）等人的论文中的论文中很广泛。（局部粒子过滤器可以击败维度的诅咒吗？，2015年），粒子滤波器（一种估计过滤分布的知识算法）受维度诅咒的影响。其次，即使可以以接近形式计算利益量，维度的增长也可能使计算成本不可行。如Rebeschini详细解释的，Van Handel等人。（2015年），可以通过开发没有尺寸误差的局部粒子过滤器来防止此问题，这也具有更便宜的计算。研究的起点是HMM，其中隐藏的Markov链是0和1的N维序列。鉴于状态空间是{0，1}（n-times）的产品空间，因此可以很容易地认识到，尺寸为N的功率为2，这意味着维度的诅咒可能是一个问题。由于状态空间是有限的，因此在向前和向后步骤后进行过滤和平滑分布。但是，这些操作涉及从计算的角度处理矩阵2到n行的矩阵，而n行2到n列的矩阵太昂贵。解决此问题的可能工作是引入错误以提高算法的速度。可以通过假设模型内的局部结构并考虑观察分布的特定分解来找到这种近似值。第一件事是假设Markov Process X在固定的时间内承认了局部结构，这意味着每个组件仅由一组邻居引起。第二个假设是，固定时间的过程y是从接受非平滑表示的分布g中得出的，这意味着存在分解的阳性观察密度g。最后一个假设是初始度量的分解。这些假设允许将远期步骤重新定义为仅在降低尺寸和低近似误差的矩阵上工作。确保相应的实现正常工作后，下一个目标是修改EM算法，以包括模型所有参数（初始分布，过渡内核等）的情况。该特定情况对流量模型有应用。实际上，在道路网络的时间演变中，每个边缘都可以由具有拥挤或不拥挤的价值的组成部分建模。当然，这种道路状态是无法实现的，因此只有观察到每条道路的汽车数量。在这种特定情况下，本地结构是一个合理的假设，因为道路上的交通仅受最亲密的影响。下一步是使用现实世界中的数据将算法应用于该高速公路交通模型。由于研究的自然延续，研究该算法的概括将很有趣。因此，尝试不仅将近似值应用于“理想”有限状态空间，还将近似值应用于更一般的空间。如果可能的话，该方法可以适应大量应用程序。