The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
컨텍스트 트리 모델은 기호의 발생 확률이 유한한 과거 시퀀스로부터 결정된다는 특성을 가지며 iid 또는 Markov 소스를 포함하는 더 넓은 클래스의 소스입니다. 본 논문에서는 간격마다 변화하는 컨텍스트 트리 모델을 갖춘 비정상 소스를 제안합니다. 이 소스에 대한 Bayes 코드는 컨텍스트 트리 모델 및 변경 지점의 사후 확률에 가중치를 부여해야 하므로 계산 복잡성은 일반적으로 기하급수적으로 증가합니다. 따라서 문제는 어떻게 계산 복잡도를 줄이는가 하는 것입니다. 본 논문에서는 컨텍스트 트리 모델과 변화점의 사전 확률 분포에 대한 특별한 클래스를 제안하고, 기존의 두 베이즈 코딩 알고리즘을 결합하여 효율적인 베이즈 코딩 알고리즘을 개발한다. 알고리즘은 본 논문에서 제안한 소스의 베이즈 위험 함수를 최소화하며, 제안하는 알고리즘의 계산 복잡도는 다항식 차수이다. 실험을 통해 제안된 알고리즘의 동작과 성능을 조사한다.
Koshi SHIMADA
Waseda University
Shota SAITO
Gunma University
Toshiyasu MATSUSHIMA
Waseda University
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.
부
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
부
@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},}
부
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 -