Hidden probabilistic one-counter automata
Başlık çevirisi mevcut değil.
- Tez No: 717927
- Danışmanlar: DR. DOMİNİK WOJTCZAK
- Tez Türü: Doktora
- Konular: İstatistik, Statistics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Unıversıty Of Lıverpool
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Özet yok.
Özet (Çeviri)
This thesis furthers the ongoing study of devising faster algorithms for the learning problem of infinite-state systems. We examine the Hidden Probabilistic One-Counter Machine (HP1CA) model, a natural extension of both Probabilistic One-Counter Automata (P1CA) and Hidden Markov Model (HMM) in this thesis. HP1CAs allow for the quadratic time complexity of learning the parameters of the model based on observational data. This gives them a big advantage over other infinite-state systems, e.g., probabilistic pushdown automata for which the same task requires cubic time. An HP1CA is a P1CA where both the control states and the counter values are hidden, but the output sequence is not (note that there is no input sequence). Such a model has a non-negative counter whose value can change by at most one during a transition. The probability of a transition depends only on the current control state and whether the counter value is zero or not. The probability of a given output symbol depends on the current control state, but not on the value of the counter. A sequence of transitions is valid only if it starts and ends in a special initial control state and final control state, respectively, with the counter value equal zero. After introducing the model, we adapt Baum-Welch algorithm, which is a special case of Expectation-Maximization algorithm used in unsupervised learning in HMM, to update the parameters of an HP1CA. Furthermore, we also adopted two dynamic programming algorithms which are called Forward algorithm and Backward algorithm, respectively to our new model. Our adapted algorithms have worst-case quadratic time complexity as compared to linear time for HMM. At the same time, its complexity is linear if the maximum value of the counter is assumed to be bounded by a constant (as it is commonly in practice). After that, we look at other possible HP1CA models that differ depending on the semantic of what a valid transition sequence is. This can depend on the the initial and final terminal state condition as follows. First, an HP1CA can either start in (1) a fixed control state with counter zero or (2) have multiple initial control states, and some fixed probability distribution specifies the likelihood of starting in a given control state (with a counter value zero). Second, an HP1CA may be required to end with with (A) a unique i Mehmet Kurucan Hidden Probabilistic One-Counter Automata final control state with counter value zero, (B) a unique final control state with arbitrary counter value, (C) multiple final control states with zero counter value. This gives rise to six possible semantics, and only (1-A) semantic studied by us earlier. We adapt the learning and dynamic programming algorithms to the remaining five models. In the end, we demonstrate that our HP1CA model lead to better accuracy and lower fit error of observation sequences of as compared to HMMs through an implementation.
Benzer Tezler
- Hybridization of probabilistic graphical models and metaheuristics for handling dynamism and uncertainty
Değişimin ve belirsizliğin ele alınması için olasılıksal çizgesel biçelerin ve sezgi-üstlerinin melezleştirilmesi
GÖNÜL ULUDAĞ
- Probabilistic graphical models for brain computer interfaces
Probabilistic graphical models for brain computer interfaces
JAİME FERNANDO DELGADO SAA
- Bist 30 hisse senedi endeksinin kısa dönem öngörüsü: Saklı Markov Modeli uygulaması
Short-term forecast of bist30 stock index: Application of Hidden Markov Model
ALİ SİNANOĞLU
- Zeki sınıflandırma ve kümeleme yöntemlerinin tıbbi tanı ve tedavide kullanımı
The usage of intelligent classification and clustering methods in medical diagnosis and treatment
UĞUR ERKİN KOCAMAZ
- An application on combining of cryptography and steganography for improving security
An application on combining of cryptography and steganography for ımproving security
SARHAD BAEZ HASAN HASAN
