Motivated by the problem of the definition of a distance between two sequences of characters, we investigate the so-called learning process of a typical sequential data compression schemes. We focus on the problem of how a compression algorithm optimizes its features at the interface between two different sequences A and B while zipping the sequence A + B obtained by simply appending B after A. We show the existence of a scaling function (the "learning function") which rules the way in which the compression algorithm learns a sequence B after having compressed a sequence A. In particular it turns out that there exists a cross-over length for the sequence B, which depends on the relative entropy between A and B, below which the compression algorithm does not learn the sequence B (measuring in this way the cross-entropy between A and B) and above which it starts learning B, i.e. optimizing the compression using the specific features of B. We check the scaling on three main classes of systems: Bernoulli schemes, Markovian sequences and the symbolic dynamic generated by a nontrivial chaotic system (the Lozi map). As a last application of the method we present the results of a recognition experiment, namely recognize which dynamical systems produced a given time sequence. We finally point out the potentiality of these results for segmentation purposes, i.e. the identification of homogeneous sub-sequences in heterogeneous sequences (with applications in various fields from genetic to time-series analysis). (C) 2003 Elsevier Science B.V. All rights reserved.
Data compression and learning in time sequences analysis / A., Puglisi; Benedetto, Dario; Caglioti, Emanuele; Loreto, Vittorio; Vulpiani, Angelo. - In: PHYSICA D-NONLINEAR PHENOMENA. - ISSN 0167-2789. - 180:1-2(2003), pp. 92-107.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Data compression and learning in time sequences analysis|
|Data di pubblicazione:||2003|
|Citazione:||Data compression and learning in time sequences analysis / A., Puglisi; Benedetto, Dario; Caglioti, Emanuele; Loreto, Vittorio; Vulpiani, Angelo. - In: PHYSICA D-NONLINEAR PHENOMENA. - ISSN 0167-2789. - 180:1-2(2003), pp. 92-107.|
|Appartiene alla tipologia:||01a Articolo in rivista|