�The Unreasonable Effectiveness of the Chaotic Tent Map in Engineering Applications

Nithin Nagaraj

Consciousness Studies Programme

National Institute of Advanced Studies (NIAS)

Bengaluru, India (Email: nithin@nias.res.in)

​

29^th September 2022 (Virtual)

The simplest 1D map that exhibits chaos?

2

Binary Map

(Bernoulli Shift Map)

Logistic Map

Tent Map

Tent Map

• Continuous, piecewise-linear
• Lebesgue measure preserving
• Chaotic (Lyapunov Exponent = ln2 > 0)
• Isomorphic to Bernoulli shift map (ergodic)
• Topologically conjugate to the Logistic map
• Positive topological entropy
• Easy to implement in hardware and software

3

Symbolic Dynamics of Tent Map

• Generating Markov partition: [0,0.5) and [0.5, 1) correspond to symbols ‘0’ (L) and ‘1’ (R).

​

• Symbolic sequences of Order 2:

​

‘00’, ‘01’, ‘11’, ‘10’

​

• Order 3:

​

‘000’, ‘001’, ‘011’, ‘010’, ‘110’, ‘111’, ‘101’, ‘100’

​

• Can you see a pattern?

​

• These form a Gray Code: adjacent codes differ in only one bit (Hamming distance = 1)

​

• Gray codes are used in error correction in digital comm., to address computer memory, mathematical puzzles (Towers of Hanoi), to prevent spurious output from electromechanical switches.

​

4

GLS: Generalized Luröth Series

• The Tent map belongs to a family of piecewise linear maps known as Generalized Luröth Series (GLS)
• Luröth’s paper in 1883, Cantor’s work in 1869

5

GLS: Generalized Luröth Series

• A GLS map with a Generating Markov Partition consisting of N intervals {a₁, a₂, …, a_N} of lengths {p₁, p₂, …, p_N} is shown here.

​

• In each interval a_i of length p_i, the line can have either a positive or negative slope of magnitude 1/p_i

6

Ref: Dajani, K., & Kraaikamp, C. (2002). Ergodic theory of numbers,

volume 29 of Carus Mathematical Monographs. Mathematical Association of America, Washington, DC.

Binary Map (binary expansion)

7

T₂(x) = 2x – [2x]

Lyapunov Exponent

= ln(2) > 0

[2x] is the integer part of (2x)

Decimal Map (decimal expansion)

8

Lyapunov Exponent

= ln(10) > 0

[10x] is the integer part of (10x)

Skew GLS Maps

9

Skew

Binary

Skew

Tent

λ= H

10

Lyapunov Exponent = Shannon Entropy

GLS maps are very special…

Aleksandr

Lyapunov

(1857-1918)

Claude Shannon

(1916-2001)

Father of Information Theory

Father of Modern Cryptography

Father of AI

bits/iteration

Applications of Tent Map/GLS in Engineering

Tent map and other GLS maps have found numerous engineering applications:

​

1. Lossless Data Compression: Nagaraj et al., 2009
2. Joint compression and error detection: Nagaraj, 2009, 2019
3. Chaos-based cryptography (perfect secrecy systems, one-time pad etc.): Nagaraj, 2012
4. Joint compression and encryption: Wong et al., 2010
5. Joint compression, error detection & encryption: Nagaraj et al., 2008
6. Chaos-based computing (implementing logic gates) Ditto et al., 2010
7. Dense storage, efficient search & retrieval: Sinha & Ditto, 1998; Miliotis et al., 2008
8. Chaotic signal multiplexing in the presence of noise: Nagaraj & Vaidya, 2009
9. Pseudorandom number generators: Palacios-Luengas et al., 2019
10. GLS neurons in brain-inspired machine learning yields state-of-the-art performance for classification tasks comparable to Machine Learning, Deep Learning algorithms in literature: Balakrishnan et al., 2019, 2021, 2022

​

​

11

Lossless Data Compression

12

An example

13

Message = “AABABBABAA”

GLS coding of “AABABBABAA”

14

Skew

Tent

Map

Iterate Backwards

15

AA

0.36

AB

Message = “AABABBABAA”

16

BAA

Message = “AABABBABAA”

GLS-Coding

• Treating the message as a symbolic sequence, we can find the initial value on the GLS (skew-tent map).

​

• Encode the initial value in binary. The initial value contains exactly the same information as the symbolic sequence. This is the compressed file.

​

• For decompression, start with the initial value and forward iterate.

17

GLS-Coding is Shannon Optimal

• Shannon entropy H(X) of the binary i.i.d source is the best possible lossless compression achievable!

​

• Asymptotically, GLS-coding achieves this Shannon limit and hence is optimal.

​

• Proof of this theorem can be found in:

Ref: Nithin Nagaraj, Prabhakar G. Vaidya, Kishor G. Bhat, Arithmetic coding as a non-linear dynamical system, Communications in Non-linear Science & Numerical Simulation (2009), doi:10.1016/j.cnsns.2007.12.001.

​

18

GLS-Coding – Arithmetic Coding

• GLS-coding is a generalization of Arithmetic Coding.
• Arithmetic Coding: Elias (1960s), Rissanen and Langdon (1979)
• Arithmetic Coding is used in international compression standards: JPEG2000, MPEG-4.

​

Ref: JJ Rissanen and GG Langdon, Arithmetic Coding, IBM Journal of Research and Development, vol. 23, no. 2, pp. 146-162. Mar. 1979.

19

GLS coding (Arithmetic Coding)

20

JPEG2000

​

Incorporating error detection in GLS-coding

21

Nagaraj, N. (2019). Using cantor sets for error detection. PeerJ Computer Science, 5, e171.

Machine Learning

22

1943: The Birth of the Artificial Neuron

23

Source: Wiki

Source: Haykin (1984)

Aritificial Neural Networks (ANN)

24

Image source: Wiki

Questioning the Core of today’s AI

25

Artificial Neuron

Biological Neuron

Chaos in the Brain

“Neuro-Chaos”^*

• Chaos – empirically found at all levels of hierarchy in the brain
• Single and coupled neurons
• Neuronal attractors in information processing, perception and memory
• Chaos – as a neuronal code

​

^*Korn, H., & Faure, P. (2003). Is there chaos in the brain? II. Experimental evidence and related models. Comptes Rendus Biologies, 326(9), pp. 787-840.

Neurochaos Learning (NL)�- incorporating chaos into Artificial Neural Networks

27

We propose NL with 2 novel architectures:

ChaosNet (2019)

ChaosFEX + ML (2020-2022)

​

28

ChaosNet: A Neural Net with Chaotic Neurons

29

Chaotic Neuron

Chaotic Neuron: GLS Map (SkewTent)

How does it work?

30

• Initial neural activity (q) = 0.34
• Stimulus = 0.92
• Discrimination Threshold (b) = 0.5
• A Chaotic Neural Trace is generated.

​

​

​

Stopping criteria: When neural trace is in the ε-neighbourhood of stimulus

(halting guaranteed by Topological Transitivity property of Chaos in GLS)

Extract features from Chaotic Neural Trace

31

• Extract the following features:
• Firing Time
• Firing Rate
• Energy of chaotic trajectory.
• Entropy of the symbolic sequence of the chaotic trajectory

​

Other statistical features of neural trace can also be used.

Chaotic neural trace features fed to a classifier

Two Flavors of NL:

1. ChaosNet: Simple classifier based on mean representation vectors and a cosine similarity measure
2. ChaosFEX + ML/DL: Pass Neurochaos features to ML or DL or your-favorite-classifier!

​

Currently tested on several datasets:

• Iris, Ionosphere, Wine, Bank Note Authentication

Haberman’s Survival, Breast Cancer Wisconsin

Statlog (Heart), Seeds, Free Spoken Digit Data, MNIST

SARS-CoV-2, Exoplanets, Intrusion detection,

Prey-Predator Datasets etc.

​

32

Accuracy:

73.89% to 98.33% with < 0.05% of data for training

33

Application of NL: COVID-19

SARS-CoV-2 genome classification using NL

• SARS-CoV-2 vs. SARS-CoV-1: We report an average macro F1-score > 0.99 with just one sample for training (averaged across 1000 independent random trials)

​

​

• Multi-class classification: SARS-CoV-2 vs. Other Coronaviruses

​

34

COVID-19

> 6.5 million deaths worldwide

The average sensitivity, specificity and accuracy for NL are 0.998, 0.999 and 0.998 respectively

Neurochaos Learning (NL) vs. ANN

35

Neurochaos Learning exhibits Stochastic Resonance

36

Research on NL by other groups

• Continual Learning / Stream Learning:

Laleh, Touraj, et al. "Chaotic Continual Learning." ICML 2020 Workshop LifelongML.

​

• Deep ChaosNet:

Chen, Huafeng, et al. "Deep ChaosNet for Action Recognition in Videos." Complexity 2021.

​

​

Please try out NL (available for free download and use)

ChaosFEX: https://github.com/pranaysy/ChaosFEX

ChaosFEX+SVM: https://github.com/HarikrishnanNB/genome_classification

SR in NL: https://github.com/HarikrishnanNB/stochastic_resonance_and_nl

​

Create your own NL

37

Conclusions

Unreasonable effectiveness of the Tent map and Generalized Luröth Series (GLS) in engineering applications due to:

• Chaos – dense periodic orbits, non-periodic universal orbits (topological transitivity), sensitive dependence on initial conditions (+^ve Lyapunov exponent), invariant distribution is uniform, ergodic, Lebesgue measure preserving, rich symbolic dynamics, non-linear extensions exhibit Robust Chaos, resistant to noise

​

• Easy to realize in hardware and low computational complexity in software applications

​

• Future: GLS maps in Machine Learning applications (inspired by ChaosNet/Neurochaos Learning)

38

Thanking my Collaborators & Funding Sources

• Prof. Prabhakar G Vaidya (late)
• Kishor G Bhat (St. Johns)
• Harikrishnan NB, Snehanshu Saha (BITS, Goa)
• Aditi Kathpalia (Czech Academy of Sciences)
• Pranay S Y (Cambridge Univ.)
• Deeksha Sethi (BMSIT&M)

​

​

​

39

Financial Support

• Tata Trusts
• DST-CSIR, DST-SATYAM, Govt. of India
• NIAS-CSP

​

Thank you!

References

[1] Kathleen T.. Alligood, Sauer, T., & Yorke, J. A. (2000). Chaos: an introduction to dynamical systems. New York: Springer.

[2] Dajani, K., & Kraaikamp, C. (2002). Ergodic theory of numbers, volume 29 of Carus Mathematical Monographs. Mathematical Association of America, Washington, DC, 1.

[3] Nagaraj, N., Vaidya, P. G., & Bhat, K. G. (2009). Arithmetic coding as a non-linear dynamical system. Communications in Nonlinear Science and Numerical Simulation, 14(4), 1013-1020.

[4] Balakrishnan, H. N., Kathpalia, A., Saha, S., & Nagaraj, N. (2019). ChaosNet: A chaos based artificial neural network architecture for classification. Chaos: An Interdisciplinary Journal of Nonlinear Science, 29(11), 113125.

[5] Harikrishnan, N. B., & Nagaraj, N. (2021). When noise meets chaos: Stochastic resonance in neurochaos learning. Neural Networks, 143, 425-435.

40

References…contd.

[6] Harikrishnan, N. B., Pranay, S. Y., & Nagaraj, N. (2022). Classification of SARS-CoV-2 viral genome sequences using Neurochaos Learning. Medical & Biological Engineering & Computing, 1-11.

[7] Sinha, S., & Ditto, W. L. (1998). Dynamics based computation. Physical Review Letters, 81(10), 2156.

[8] Ditto, W. L., Miliotis, A., Murali, K., Sinha, S., & Spano, M. L. (2010). Chaogates: Morphing logic gates that exploit dynamical patterns. Chaos: An Interdisciplinary Journal of Nonlinear Science, 20(3), 037107.

[9] Miliotis, A., Sinha, S., & Ditto, W. L. (2008). Exploiting nonlinear dynamics to store and process information. International Journal of Bifurcation and Chaos, 18(05), 1551-1559.

[10] Nagaraj, N., & Vaidya, P. G. (2009). Multiplexing of discrete chaotic signals in presence of noise. Chaos: An Interdisciplinary Journal of Nonlinear Science, 19(3), 033102.

​

41

References…contd.

[11] Nagaraj, N. (2019). Using cantor sets for error detection. PeerJ Computer Science, 5, e171.

[12] Nagaraj, N. (2012). One-Time Pad as a nonlinear dynamical system. Communications in Nonlinear Science and Numerical Simulation, 17(11), 4029-4036.

[13] Wong, K. W., Lin, Q., & Chen, J. (2010). Simultaneous arithmetic coding and encryption using chaotic maps. IEEE Transactions on Circuits and Systems II: Express Briefs, 57(2), 146-150.

[14] Palacios-Luengas, L., Pichardo-Méndez, J. L., Díaz-Méndez, J. A., Rodríguez-Santos, F., & Vázquez-Medina, R. (2019). PRNG based on skew tent map. Arabian Journal for Science and Engineering, 44(4), 3817-3830.

[15] Nithin Nagaraj, Novel applications of chaos theory to coding and cryptography, PhD Thesis, NIAS, 2008.

42

43

Thank You�Email: nithin@nias.res.in