Krzywe wypełniające w rozwiązywaniu wielowymiarowych problemów decyzyjnych

• Autorzy: Skubalska-Rafajłowicz E.

Warianty tytułu

EN

Space-filling curves in decision problems

• Języki publikacji: PL

Abstrakty

PL

W monografii przedstawiono metodykę konstruowania i badania algorytmów decyzyjnych, która jest nowym podejściem do problemów przetwarzania i podejmowania decyzji na podstawie wielowymiarowych obserwacji. Polega ona na transformacji danych do postaci jednowymiarowej za pomocą quasi-odwrotności dobrze dobranej krzywej wypełniającej, a następnie na rozwiązaniu jednowymiarowego problemu decyzyjnego. W efekcie transformacji uzyskuje się redukcję wymiaru problemu i jego znaczącą kompresję, bez utraty istotnych informacji przestrzennych zawartych w danych wielowymiarowych. Prowadzi to do możliwości konstruowania szybkich algorytmów podejmowania decyzji, które mogą działać na bieżąco, na podstawie aktualnie uzyskiwanych obserwacji. Podejście to rozwija kierunki badań prowadzone obecnie w automatyce, polegające na projektowaniu elastycznych systemów, łączących konwencjonalne techniki z różnorodnymi metodami uczenia, które wykorzystują zgromadzone obserwacje pomiarowe i pozwalają na korygowanie pracy systemu. Opracowano układy równań funkcyjnych i rekurencyjne metody wyznaczania odwzorowań quasi-odwrotnych do wielowymiarowych krzywych typu Peano, Hilberta i Sierpińskiego. Wykazano, że transformacje te zachowują istotne informacje statystyczne zawarte w wielowymiarowych danych. Wyprowadzono teoretyczną zależność między wymiarami fraktalnymi danych przed i po transformacji. Udowodniono, że badana klasa krzywych wypełniających zachowuje ryzyko Bayesa dla dowolnego rozkładu obserwacji o ograniczonym nośniku. Zdefiniowano nową klasę krzywych wypełniających, które zachowują zadaną miarę probabilistyczną i wykorzystano ją w problemach kwantyzacji. Zbadano asymptotyczną wartość dystorsji wektorowych kwantyzatorów otrzymanych poprzez redukcję wymiaru obserwacji. Zdefiniowano też pojęcie powierzchni wypełniającej oraz odpowiednie odwzorowanie quasi-odwrotne oraz zbadano ich podstawowe własności. Wprowadzono pojęcie multi-karty, która jest uogólnieniem tradycyjnej karty kontrolnej i pozwala oceniać stan wielowymiarowego procesu na podstawie przekształconych, skalarnych obserwacji, zbadano też jej własności. Otrzymane rezultaty teoretyczne zastosowano w odniesieniu do wielowymiarowych problemów decyzyjnych, dotyczących rozpoznawania i monitorowania stanu procesu, diagnostyki i problemów statystycznego wykrywania zmian w procesie oraz problemów kwantyzacji. Zaowocowało to powstaniem szczegółowych metod, spełniających nałożone wymagania teoretyczne. W wielu przypadkach zaproponowano także proste obliczeniowo algorytmy heurystyczne. Podstawową cechą wszystkich opracowanych metod jest mała złożoność obliczeniowa procesu podejmowania decyzji.

EN

In the monograph, a methodology of constructing and validating decision algorithms is proposed. This methodology forms a new approach to the problems of multidimensional decision making. The main idea is to transform each multivariate observation to univariate one, using a quasi-inverse of a carefully chosen space-filling curve as a transformation. Then, the decision problem is solved for univariate data. The advantages of using such transformations lie in the dimensionality reduction and in data compression without loosing the information associated with the spatial structure of multivariate observations. These advantages allow us to construct fast decision algorithms, which can be easily implemented as on-line methods. The methodology proposed is contained in the stream of research which explores novel strategies for control of complex industrial processes. These strategies are directed towards the design of flexible control systems, which combine model--based classical techniques with a variety of learning based methods. The learning is based on past observations, which are used for a control system adaptation and enhancement. Important prerequisites for developing the decision making methodology are criteria for selecting space-filling curves and algorithms for calculating their quasi--inverses as quickly as possible. In the monograph, a method of forming functional equations for space-filling curves and their quasi-inverses is developed for the Peano, the Hilbert and the Sierpinski curves. It is also proved that these functional equations can be solved by backward recursions, providing exact values of the curves on dense sets in a finite number of iterations. It is also shown that the space-filling based transformations retain essential statistical information, which is important in decision-making. In particular, it is proved that the Bayes risk is invariant under these transformations for every distribution which has a bounded support. Also a fractal dimension, scaled by the dimension of the data, occurs to be invariant. A new class of curves which retain a prescribed probability measure is defined and used for solving vector quantization problems. In particular, an asymptotic distortion error of quantizers is investigated using the dimension error techniques. The notion of the space-filling curves is generalized also in another direction, namely, space-filling surfaces and their quasi-inverses are denned and investigated. The above theoretical results form foundations for deriving new classes of decision-making algorithms, which are applicable in a variety of control system tasks. In particular, the notion of a multi-chart is introduced, together with a new method of detecting system faults. In addition to new fast algorithms of vector quantization and pattern recognition, also their asymptotics is investigated, providing a theoretical foundations for their use in monitoring and diagnosis of a system state. In some cases simple heuristic algorithms, having solid support in the simulations, are also discussed. The important feature of all the decision algorithms, resulting from the methods considered in the monograph, is their low computational complexity.

Słowa kluczowe

PL

krzywe wypełniające; redukcja wymiaru; problemy decyzyjne; rozpoznawanie; sterowanie jakością

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Monografie
• Rocznik: 2001
• Tom: Vol. 104, nr 28
• Strony: 234--234
• Opis fizyczny: s., bibliogr.208 poz.

Twórcy

autor

Skubalska-Rafajłowicz E.

• Instytut Cybernetyki Technicznej Politechniki Wrocławskiej, ul. Janiszewskiego 11/17, 50-372 Wrocław.