The Stochastic Context Tree (SCOT) is a useful tool for studying infinite random sequences generated by an m-Markov Chain (m-MC). It captures the phenomenon that the probability distribution of the next state sometimes depends on less than m of the preceding states. This allows compressing the information needed to describe an m-MC. The SCOT construction has been earlier used under various names: VLMC, VOMC, PST, CTW. In this paper we study the possibility of reducing the m-MC to a 1-MC on the leaves of the SCOT. Such context trees are called perfect-memory. We give various combinatorial characterizations of perfect-memory context trees and an efficient algorithm to find the minimal perfect-memory extension of a SCOT.
翻译：托盘背景树(SCOT)是研究由m-markov 链(m-MC)产生的无限随机序列的有用工具。 它捕捉到下一个状态的概率分布有时取决于低于先前状态的 mm 。 这样可以压缩描述一个 m-MC所需的信息。 SCOT 的构造先前曾以各种名称使用: VLMC、 VOMC、 PST、 CTW。 本文我们研究了将M- MC 在SCOT 叶叶上减少到1- MC 的可能性。 这种背景树被称为完美模擬。 我们对完美模拟背景树作了各种组合性描述,并采用了一种有效的算法,以找到一个SCOT 最小的完美模范扩展。
相关内容
- Today (iOS and OS X): widgets for the Today view of Notification Center
- Share (iOS and OS X): post content to web services or share content with others
- Actions (iOS and OS X): app extensions to view or manipulate inside another app
- Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
- Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
- Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
- Custom Keyboard (iOS): system-wide alternative keyboards
Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
微信扫码咨询专知VIP会员