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

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

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.