IEICE TRANSACTIONS on Fundamentals
An Efficient Bayes Coding Algorithm for Changing Context Tree Model
Summary :
The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.3 pp.448-457
- Publication Date
- 2024/03/01
- Publicized
- 2023/08/24
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2023TAP0017
- Type of Manuscript
- Special Section PAPER (Special Section on Information Theory and Its Applications)
- Category
- Source Coding and Data Compression
Authors
Koshi SHIMADA
Waseda University
Shota SAITO
Gunma University
Toshiyasu MATSUSHIMA
Waseda University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Koshi SHIMADA, Shota SAITO, Toshiyasu MATSUSHIMA, "An Efficient Bayes Coding Algorithm for Changing Context Tree Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E107-A, no. 3, pp. 448-457, March 2024, doi: 10.1587/transfun.2023TAP0017.
Abstract: The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023TAP0017/_p
Copy
@ARTICLE{e107-a_3_448,
author={Koshi SHIMADA, Shota SAITO, Toshiyasu MATSUSHIMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Bayes Coding Algorithm for Changing Context Tree Model},
year={2024},
volume={E107-A},
number={3},
pages={448-457},
abstract={The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.},
keywords={},
doi={10.1587/transfun.2023TAP0017},
ISSN={1745-1337},
month={March},}
Copy
TY - JOUR
TI - An Efficient Bayes Coding Algorithm for Changing Context Tree Model
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 448
EP - 457
AU - Koshi SHIMADA
AU - Shota SAITO
AU - Toshiyasu MATSUSHIMA
PY - 2024
DO - 10.1587/transfun.2023TAP0017
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 2024
AB - The context tree model has the property that the occurrence probability of symbols is determined from a finite past sequence and is a broader class of sources that includes i.i.d. or Markov sources. This paper proposes a non-stationary source with context tree models that change from interval to interval. The Bayes code for this source requires weighting of the posterior probabilities of the context tree models and change points, so the computational complexity of it usually increases to exponential order. Therefore, the challenge is how to reduce the computational complexity. In this paper, we propose a special class of prior probability distribution of context tree models and change points and develop an efficient Bayes coding algorithm by combining two existing Bayes coding algorithms. The algorithm minimizes the Bayes risk function of the proposed source in this paper, and the computational complexity of the proposed algorithm is polynomial order. We investigate the behavior and performance of the proposed algorithm by conducting experiments.
ER -
English
