English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

The problem of modeling complicated data sequences, such as DNA or speech, often arises in practice. Most of the algorithms select a hypothesis from within a model class assuming that the observed sequence is the direct output of the underlying generation process. In this paper we consider the case when the output passes through a memoryless noisy channel before observation. In particular, we show that in the class of Markov chains with variable memory length, learning is affected by factors, which, despite being super-polynomial, are still small in some practical cases. Markov models with variable memory length, or probabilistic finite suffix automata, were introduced in learning theory by Ron, Singer and Tishby who also described a polynomial time learning algorithm [11, 12]. We present a modification of the algorithm which uses a noise-corrupted sample and has knowledge of the noise structure. The same algorithm is still viable if the noise is not known exactly but a good estimation is available. Finally, some experimental results are presented for removing noise from corrupted English text, and to measure how the performance of the learning algorithm is affected by the size of the noisy sample and the noise rate. t~esearch supported in part by the National Science Foundation, grant CCR-9213881. Permission to make digital/hard copies of all oi pall of this material [br personal or classroom use is granted without l~e provided that the copies are not made or distributed lbr profit or commercial advantage, the copyright notice, the title of the publication and ils date appear, and notice is given tha! copyright is by permission of the ACM. Inc. To copy otherwise, to republish, to pos! on servers or to redistribute lo lists, requires specific permission and/or fee COLT 97 Nashville, Tennesee, USA Copyright 1997 ACM 0-89791-891-6/97/7.. $3.50 1 I n t r o d u c t i o n Modeling complex data sequences is one of the main problems in many research areas. Examples can be taken from computational biology [4, 6] (DNA or protein sequences), from natural language processing or speech recognition [9] (phoneme or letter sequences), etc. Most of the model building methods assume that noiseless training data are available. A natural approach is, however, to consider the observed data sequence as being the output of a string generation process corrupted by some noise. The knowledge of the noise structure may allow one to estimate the parameters for the underlying "clean" string generation model using a sample of noisy strings. The string generation process is often assumed to have only a finite memory, that is, the generation of the next symbol of the sequence depends on a fixed finite number of previous symbols and state transitions. Such models include Hidden Markov Models [9], FSM sources in data compression [10], and Markov chains with variable memory length [12]. In this paper we consider the case when the output of a Markov chain with variable memory length is passed through a memoryless noisy channel before observation. Among others, Lugosi [8] considered learning front noisy data and showed that consistent learning is possible in case of the binary symmetric channel even if the noise rate is not known. In particular, he proved that the use of a nearest neighbor or a histogram classification method is consistent, that is, the error rate converges to its minimal value (Bayes' error). Markov models with variable memory length, otherwise known as probabilistic finite suffix automata, were introduced in learning theory by Ron, Singer and Tishby who also described a polynomial time learning algorithm [11, 12]. Similar models have been studied in information theory as well '10, 13. 14, 15]. Other models in the learning theory literature include Hidden Markov Models [9] and probabilistic finite automata. They both have severe theoretical drawbacks. Abe and Warmuth [1]

Learning Markov chains with variable memory length from noisy output