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.

摘要（不超过4000个字符，含空格）隐马尔可夫模型（HMM）可以广泛应用于现实生活中，从交通模型到不同的生物和神经模型。这种与现实的契合增加了对精确有效的算法来解决滤波和平滑问题的需求。文献提供了不同的方法来计算基础模型的过滤和平滑分布，尽管当维度增加时会暴露出两个问题。首先，正如 Rebeschini、Van Handel 等人在论文中所阐述的那样。（局部粒子滤波器能否击败维数诅咒？，2015），粒子滤波器（一种估计过滤分布的众所周知的算法）受到维数诅咒的影响。其次，即使可以以近似形式计算感兴趣的数量，维度的增长也可能使计算成本变得不可行。正如 Rebeschini、Van Handel 等人详细解释的那样。（2015），可以通过开发具有无量纲误差的局部粒子滤波器来防止这个问题，这也具有计算成本更低的优点。研究的起点是 HMM，其中隐马尔可夫链是一个 n 0 和 1 的维序列。假设状态空间是 {0, 1} （n 次）的乘积空间，可以很容易地看出维度是 2 的 n 次方，这意味着维度灾难可能是一个问题。由于状态空间是有限的，因此在前向和后向步骤之后可以使用过滤和平滑分布。然而，这些操作涉及处理 2 到 n 行和 2 到 n 列的矩阵，从计算的角度来看，这些矩阵的成本太高。解决这个问题的一个可能的解决方法是引入一个错误来提高算法的速度。通过假设模型内部存在局部结构并考虑观测分布的特定因式分解，可以找到该近似值。首先，假设马尔可夫过程 X 在固定时间内承认局部结构，这意味着每个组件在某种程度上仅由一组邻居引起。第二个假设是固定时间内的过程 Y 是从允许非退化表示的分布 G 中得出的，这意味着存在分解的正观测密度 g。最后一个假设是初始测量的因式分解。这些假设允许将前向步骤重新定义为仅适用于尺寸减小且近似误差较低的矩阵。在确保相应的实现正常工作后，下一个目标是修改 EM 算法，使其包含模型所有参数（初始分布、转换核等）未知的情况。这个具体案例适用于交通模型。事实上，在道路网络的时间演化中，每条边都可以通过具有可以拥堵或不拥堵的值的组件来建模。当然，道路的这种状态是无法实现的，因此仅观察每条道路的汽车数量。在这种特定情况下，局部结构是一个合理的假设，因为道路中的交通仅受最近交通的影响。下一步将是使用来自现实世界的数据将该算法应用于该高速公路交通模型。作为研究的自然延续，研究该算法的泛化将会很有趣。因此，尝试将近似不仅应用于“理想”有限状态空间，而且应用于更一般的空间。如果可能的话，该方法可以适应广泛的应用。