Model syntaktycznego rozpoznawania wzorców zniekształconych oparty na gramatykach ciągowych klasy Dpll(k)

mgr Tomasz Peszek

Promotor: dr hab. Janusz Jurek
Dyscyplina: Informatyka


Rozprawa doktorska pt. ”Model syntaktycznego rozpoznawania wzorców zniekształconych oparty na gramatykach ciągowych klasy DPLL(k)” jest pracą z dziedziny syntaktycznego rozpoznawania wzorców. Praca składa się z części teoretycznej (rozdziały: Wstęp, Założenia modelu rozmytego, Model formalny automatu FDPLLA(k)) oraz części implementacyjno-doświadczalnej (rozdziały: Implementacja, Aplikacja modelu). Pracę zamyka rozdział podsumowujący oraz trzy dodatki zawierające najważniejsze definicje z teorii języków bezkontekstowych, programowanych oraz założenia uogólnienia konstrukcji automatu FDPLL(k).

We wstępie do rozprawy doktorskiej zreferowany został kontekst badań. Zgodnie z przeprowadzonym badaniem literatury przedmiotu, określono główne kierunki badań w dziedzinie syntaktycznego rozpoznawania wzorców oraz podano najważniejsze otwarte problemy wraz z powołaniem ich częściowych rozwiązań. W ramach przedstawionego kontekstu zdefiniowano problem, którego rozwiązaniem miało być przedmiotem badań własnych oraz sformułowano tezę rozprawy:

„Model syntaktycznego rozpoznawania wzorców oparty o automat klasy FDPLLA(k) może być wykorzystany do rozpoznania wzorców rozmytych/zniekształconych.”

Rozdział drugi poświęcono rozszerzeniu pojęć potrzebnych dla rozbudowy klasycznego modelu syntaktycznego rozpoznawania wzorców, w kierunku analizy wzorców zniekształconych i/lub rozmytych. Zdefiniowano pojęcia: prymitywu rozmytego, składowej prymitywu rozmytego, elementu prymitywu rozmytego, wymiaru prymitywu rozmytego oraz pojęcia słowa rozmytego, rozwiązania słowa rozmytego, długości słowa rozmytego. Równocześnie rozszerzono pojęcie wyniku analizy syntaktycznej słowa rozmytego jako nadanie odpowiedniej kwalifikacji każdemu jego rozwiązaniu.

W rozdziale 3 zdefiniowano w sposób formalny automat FDPLLA(k) (Fuzzy Dynamically Programmed, Model FDPLLA(k) oparto na gramatykach klasy DPLL(k) ze względu na ich dużą siłę dyskryminacyjną oraz zdefiniowane, wielomianowe algorytmy analizy syntaktycznej, inferencji gramatyki oraz konstrukcji parsera. Automat klasy FDPLLA(k) zdefiniowano jako zespół trzech współpracujących ze sobą automatów TDA (Task Dispatcher Automaton), PPA (Parser Pool Automaton) oraz PSA (Process Saver Automaton) wykorzystujących do działania określone struktury danych: taśmę wejściową IT (przechowującą analizowane słowo rozmyte), pamięć procesów MEM (przechowującą dane aktualnie prowadzonych procesów analizy syntaktycznej), taśma PST (przechowująca dane o statusie każdego parsera-elementu puli PPA oraz dane zadań wywodu zleconych do wykonania). Każdy z automatów składowych otrzymał odpowiednie przeznaczenie - automat TDA miał przydzielać kolejne zadania wywodu, automat PPA oraz parsery DPLL(k) wchodzące w jego skład miały realizować przydzielone zadania wywodu, a automat PSA miał zapisywać wyniki zakończonych zadań wywodu w pamięci MEM. Każdy z automatów składowych został zdefiniowany formalnie (definicja automatu, definicja konfiguracji, funkcja przejścia). W konsekwencji zdefiniowano także automat FDPLLA(k). Na podstawie zdefiniowanego modelu formalnego oszacowano złożoność działania automatu – zarówno złożoność czasową jak i pamięciową. W rozdziale sformułowano także serię uwag o możliwości użycia automatu FDPLLA(k) w równoległym modelu obliczeń. Rozdział został zakończony porównaniem cech syntaktycznego modelu rozpoznawania wzorców rozmytych/zniekształconych z dotychczasowymi metodami rozwiązywania tego problemu (gramatyki z korekcją błędów, gramatyki stochastyczne). Wykazano istotne zalety nowego modelu.

W rozdziale 4 opisano implementacji aplikacji realizującej zdefiniowany model automatu FDPLLA(k) oraz przeprowadzono testy z użyciem wybranych języków kontekstowych (języki kształtów). Analizowane słowa poddawano losowym niewielkim zniekształceniom. Testy potwierdziły poprawność działania, efektywność obliczeniową oraz odporność modelu na zniekształcenia analizowanych wzorców. W rozdziale zawarto także opis wszystkich klas oraz struktur danych systemu.

W rozdziale piątym przedstawione zostało przykładowe zastosowanie modelu syntaktycznego rozpoznawania wzorców opartego na gramatykach klasy DPLL(k) oraz automatach klasy FDPLLA(k). Stworzony model automatu FDPLLA(k) został wykorzystany do konstrukcji systemu wspomagającego tworzenie 24-godzinnych prognoz zapotrzebowania na energię. Systemy tej klasy mają zastosowanie w firmach dystrybucyjnych działających w Krajowym Systemie Elektroenergetycznym (KSE).

Dzięki życzliwości Tauron Polska Energia S.A. oddział w Gliwicach możliwe było zweryfikowanie modelu prognostycznego, wykorzystującego automat FDPLLA(k), na rzeczywistych danych. Weryfikacja ta umożliwiła porównanie i ocenę skuteczności nowego modelu w kontekście aktualnie stosowanych metod prognozowania. W ostatniej sekcji przedstawione zostały wybrane statystyki działania systemu, wykorzystującego model automatu FDPLLA(k), ilustrujące efektywność działania oraz dokładność generowanej prognozy.

Rozdziale 6 zawiera podsumowanie wszystkich uzyskanych wyników i odniesienie ich do przedstawionego sposobu wykazania tezy. W dodatkach A i B, zawarto kompendium podstawowych pojęć z dziedziny syntaktycznego rozpoznawania wzorców i języków formalnych. Przedstawiono tam dokładne definicje najczęściej używanych w pracy doktorskiej terminów. W dodatku C zebrano szereg uwag dotyczących konstrukcji automatu FDPLLA(k) dla wyższych k.

Pełna wersja autoreferatu T.Peszek_autoreferat.pdf

Recenzja prof. dr hab. inż. Marka Skomorowskiego: recenzja_m.skomorowski.pdf
Recenzja prof. dr hab. inż. Marka Kurzyńskiego: recenzja_m.kurzynski.pdf

- J. Jurek, T. Peszek, 2005, On the use of syntactic pattern recognition methods, neural networks and fuzzy systems for short-term electrical load forecasting. Advances in Soft Computing 851-858, Springer-Verlag, Berlin Heidelberg, Germany (2005).

- T. Peszek, 2006, Neuro–Fuzzy Prediction Systems in Energetics. Schedae Informaticae, Wydawnictwo Uniwersytetu Jagiellońskiego . 15, 73-94, (2006).

- J. Jurek, T. Peszek, 2014, Model of syntactic recognition of distorted string patterns with the help of GDPLL(k)-based automata. Advances in Intelligent and Soft Computing 226, 101-110.

- M. Flasiński, J. Jurek, T. Peszek, 2014, Parallel Processing Model for Syntactic Pattern Recognition-Based Electrical Load Forecast. Lecture Notes in Computer Science 8384, 338-347, Springer-Verlag, Berlin Heidelberg, Germany (2014).

- M. Flasiński, J. Jurek, T. Peszek, 2016, Analysis of Fuzzy String Patterns with the Help of Syntactic Pattern Recognition. Advances in Intelligent Systems and Computing 400 (2016), 115-126, Springer International Publishing Switzerland.

- M. Flasiński, J. Jurek, T. Peszek, 2016, Application of syntactic pattern recognition methods for electrical load forecasting. Advances in Intelligent Systems and Computing 403 (2016), Springer International Publishing Switzerland, w druku.

- M. Flasiński, J. Jurek, T. Peszek, 2016, Fuzzy Transducers as a Tool for Translating Noisy Data in Electrical Load Forecast System, Lecture Notes in Computer Science (2016), Springer-Verlag, Berlin-Heidelberg, Germany, w druku.