Incremental construction of Markov chains with dependence on non-temporal domains

Abstract

Zamansal bağımlılık, birçok gerçek dünya sisteminin ardışıklık içeren davranışını modellemek için kullanılan temel bir kavramdır. Markov zincirleri, belirtilen olasılık dağılımına dayalı olarak bu tür zamana bağlı davranışları modelleme yeteneğine sahip güçlü araçlardır. Markov zincirlerinin parametreleri, Oommen ve Rueda tarafından önerilen Olasılıksal Öğrenmeye dayalı Zayıf Tahmin (SLWE) yöntemi ile öğrenilebilir. Bu yöntem, temel olasılık dağılımının zamanla değiştiği, durağan olmayan ortamlarda etkili bir şekilde çalışır. Ancak bazı sistemler daha karmaşık bağımlılıklara sahip verilerin analizini gerektirir. Karmaşık örüntülerin tespiti, tanımlanması veya tanınması gibi karmaşık problemlerde, zamansal bağımlılığın yanı sıra, konumlara veya komşulara ilişkin bir bağımlılığın, yani uzaysal bağımlılığın, verinin analizine önemli ek bilgiler sağlama potansiyeli yüksektir. Yalnızca zamansal bağımlılığı göz önünde bulunduran Markov zincirleri, verilerden çıkarılabilen bağımlılık bilgilerinin uzaysal yönünden yararlanma konusunda yetersiz kalmaktadır. Bu çalışmada, uzaysal bağımlılığı literatürde tanımlanandan farklı bir şekilde ele alarak zamansal bağımlılığı kullanan Markov zincirlerini genişletiyor ve çift alanlı Markov zincirleri olan uzay-zamansal Markov zincirleri nin (STMC) matematiksel altyapılarını veriyoruz. Bu çalışmada ayrıca, SLWE yöntemi, ayrık zamanlı birinci dereceden homojen bir uzay-zamansal Markov zincirinin parametrelerini tahmin etmek için geliştirilmiş, hedef parametre tahminlerinin asimptotik davranışları incelenmiş ve ilgili teoremler verilmiştir. Önerilen yöntemin (i) sentetik verilerle gerçekleştirilen deneylerde, hedef parametreyi yalnızca zamansal veya uzaysal bağımlılığa dayanan Markov zincirlerinden daha etkili bir şekilde takip ettiği ve geleneksel tahmin yöntemlerinden daha iyi performans gösterdiği, (ii) gerçek dünya verisiyle gerçekleştirilen deneylerde, derin öğrenme yöntemleriyle karşılaştırıldığında, rekabetçi tahmin performansına sahip olduğu ve açık bir şekilde daha az karmaşık bir yöntem olduğu gösterilmiştir.

Temporal dependence (TD) is a fundamental concept exploited for modeling real world systems’ behavior of sequential nature. Markov chains (MCs) are powerful tools capable of modeling such time dependent behavior. The parameters of the MCs may be learned by an estimation method, Stochastic Learning Weak Estimator (SLWE) (Oommen and Rueda), which operates effectively in non-stationary environments, where the underlying probability distribution changes over time. In complex problems such as detection, identification or recognition of complex patterns, besides TD, a dependence regarding the positions or neighboring, i.e., spatial dependence (SD), is likely to provide a significant contribution to the analysis of relevant data. MCs that consider only TD remain insufficient in exploiting the spatial aspect of dependence information extractable from the data. In this study, we extend the MCs that utilize, besides TD, SD, and present the theoretical background for spatio-temporal MCs (STMCs) considering the spatial domain in a different manner from literature. Also, SLWE is extended to estimate the parameters of a discrete-time first-order homogeneous STMC and corresponding theorems regarding the asymptotic behavior of estimates are provided. We show that the proposed method (i) is able to track the target parameter more effectively than the MCs relying solely on temporal or spatial dependence, and outperforms the traditional estimation methods in synthetic experiments, (ii) has competitive forecasting performance, and is significantly less complex compared with Deep Learning (DL) methods in real-world experiments.