Compression methods for approximate stochastic modelling

• Main Author: Onggadinata, Kelvin
• Other Authors: Gu Mile
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Science::Mathematics::Applied mathematics::Information theory; Science::Physics
• Online Access: https://hdl.handle.net/10356/139314
• Institution: Nanyang Technological University

Understanding of the natural world can be accounted to effective information processing. Natural processes, however, are often riddled with enormous amount of information and high non-linearity. A need to simplify these problems becomes paramount for practical purposes. Computational mechanics has come up with a successful model --- known as $\epsilon$-machine --- to carry out statistically accurate prediction while assuming minimal representation. Reducing statistical complexity --- a fundamental measure of memory one needs to save to operate the $\epsilon$-machine --- has been a subject of interest as it provides operational advantages. In this final year project, we explore the problem of optimal construction of approximate $\epsilon$-machine that prioritize minimal complexity at the expense of prediction power. Several approaches are proposed to achieve this, namely the brute-force method and the information bottleneck method. Although requiring preliminary assumption on the approximate $\epsilon$-machine's structures, the brute-force method is fairly effective in finding the minimal model under some constraint. A more robust method is the information bottleneck method, which uses principle of rate-distortion theory to find a set of optimal predictive states to represent the process. We propose the use of two information bottleneck variations, specifically the deterministic information bottleneck and agglomerative clustering, to construct optimal predictive states that are unifilar. Through artificial reconstruction, the predictive states' probability law can be be used to inspire its corresponding approximate $\epsilon$-machine. Combination of these two techniques --- the information bottleneck followed by brute-force method --- can be proven to be useful in the problem of optimal model compression.