TY - JOUR

T1 - State splitting and merging in probabilistic finite state automata for signal representation and analysis

AU - Mukherjee, Kushal

AU - Ray, Asok

N1 - Funding Information:
This work has been supported in part by the U.S. Army Research Laboratory and the U.S. Army Research Office under Grant nos. W911NF-07-1-0376 and W911NF-13-1-0461, and by the U.S. Air Force Office of Scientific Research (AFOSR) under Grant no. FA9550-12-1-0270 . Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agencies.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2014/11

Y1 - 2014/11

N2 - Probabilistic finite state automata (PFSA) are often constructed from symbol strings that, in turn, are generated by partitioning time series of sensor signals. This paper focuses on a special class of PFSA, which captures finite history of the symbol strings; these PFSA, called D-Markov machines, have a simple algebraic structure and are computationally efficient to construct and implement. The procedure of PFSA construction is based on (i) state splitting that generates symbol blocks of different lengths based on their information contents; and (ii) state merging that assimilates histories by combining two or more symbol blocks without any significant loss of the embedded information. A metric on the probability distribution of symbol blocks is introduced for trade-off between loss of information (e.g., entropy rate) and the number of PFSA states. The underlying algorithms have been validated with three test examples. While the first and second examples elucidate the key concepts and the pertinent numerical steps, the third example presents the results of analysis of time series data, generated from laboratory experimentation, for detection of fatigue crack damage in a polycrystalline alloy.

AB - Probabilistic finite state automata (PFSA) are often constructed from symbol strings that, in turn, are generated by partitioning time series of sensor signals. This paper focuses on a special class of PFSA, which captures finite history of the symbol strings; these PFSA, called D-Markov machines, have a simple algebraic structure and are computationally efficient to construct and implement. The procedure of PFSA construction is based on (i) state splitting that generates symbol blocks of different lengths based on their information contents; and (ii) state merging that assimilates histories by combining two or more symbol blocks without any significant loss of the embedded information. A metric on the probability distribution of symbol blocks is introduced for trade-off between loss of information (e.g., entropy rate) and the number of PFSA states. The underlying algorithms have been validated with three test examples. While the first and second examples elucidate the key concepts and the pertinent numerical steps, the third example presents the results of analysis of time series data, generated from laboratory experimentation, for detection of fatigue crack damage in a polycrystalline alloy.

UR - http://www.scopus.com/inward/record.url?scp=84899660625&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899660625&partnerID=8YFLogxK

U2 - 10.1016/j.sigpro.2014.03.045

DO - 10.1016/j.sigpro.2014.03.045

M3 - Article

AN - SCOPUS:84899660625

SN - 0165-1684

VL - 104

SP - 105

EP - 119

JO - Signal Processing

JF - Signal Processing

ER -