The Experts below are selected from a list of 89634 Experts worldwide ranked by ideXlab platform

Sebastien Roch - One of the best experts on this subject based on the ideXlab platform.

  • Learning nonsingular phylogenies and Hidden Markov Models
    The Annals of Applied Probability, 2006
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise, a well-known learning problem conjectured to be computationally hard. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

  • learning nonsingular phylogenies and Hidden Markov Models
    Symposium on the Theory of Computing, 2005
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper, we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

  • STOC - Learning nonsingular phylogenies and Hidden Markov Models
    Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, 2005
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper, we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

Bart De Moor - One of the best experts on this subject based on the ideXlab platform.

  • Equivalence of state representations for Hidden Markov Models
    Systems & Control Letters, 2008
    Co-Authors: Bart Vanluyten, Jan C. Willems, Bart De Moor
    Abstract:

    In this paper we consider the following problem for Hidden Markov Models: given a minimal Hidden Markov model, derive conditions for another Hidden Markov model to be equivalent and give a description of the complete set of equivalent Models. A distinction is made between quasi- and positive Hidden Markov Models and between Mealy and Moore Hidden Markov Models. We derive a condition for two positive Mealy Models to be equivalent and give a description of the complete set of Mealy Models that are equivalent to a given Mealy model. We show that under certain conditions minimal quasi-Moore Models are unique up to a permutation of the states. We derive a condition for two positive Moore Models to be equivalent and give a description of the complete set of Moore Models equivalent to a given Moore model. Finally, we compare the results for Hidden Markov Models and linear Gaussian systems.

  • Equivalence of state representations for Hidden Markov Models
    2007 European Control Conference (ECC), 2007
    Co-Authors: Bart Vanluyten, Jan C. Willems, Katrien De Cock, Bart De Moor
    Abstract:

    In this paper we consider the following problem for (quasi) Hidden Markov Models: given a minimal (quasi) Hidden Markov model, what can be said about the set of all equivalent (quasi) Hidden Markov Models of the same order. A distinction is made between Mealy and Moore type of Hidden Markov Models. A complete solution is presented for the quasi HMM case. For quasi Mealy Models, there exists already a description of the set of equivalent Models. In this paper, we prove that for minimal quasi Moore Models, the set of equivalent Models consists of only one element (up to a permutation of the states). Finally, we present some initial results for the positive HMM case and show a motivating simulation example.

  • CDC - A new approach for the identification of Hidden Markov Models
    2007 46th IEEE Conference on Decision and Control, 2007
    Co-Authors: Bart Vanluyten, Jan C. Willems, Bart De Moor
    Abstract:

    In this paper, we consider the approximate identification problem for Hidden Markov Models, i.e. given a finite- valued output string generated by an unknown Hidden Markov model, find an approximation of the underlying model. We propose a two-step procedure for the approximate identification problem. In the first step the underlying state sequence corresponding to the output sequence is estimated directly from the output data. In the second step the system matrices are calculated from the obtained state sequence and the given output sequence. In a simulation example the performance of our proposed method is compared with the performance of the classical Baum-Welch approach for identification of Hidden Markov Models.

Elchanan Mossel - One of the best experts on this subject based on the ideXlab platform.

  • Learning nonsingular phylogenies and Hidden Markov Models
    The Annals of Applied Probability, 2006
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise, a well-known learning problem conjectured to be computationally hard. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

  • learning nonsingular phylogenies and Hidden Markov Models
    Symposium on the Theory of Computing, 2005
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper, we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

  • STOC - Learning nonsingular phylogenies and Hidden Markov Models
    Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, 2005
    Co-Authors: Elchanan Mossel, Sebastien Roch
    Abstract:

    In this paper, we study the problem of learning phylogenies and Hidden Markov Models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning Hidden Markov Models without the nonsingularity condition is at least as hard as learning parity with noise. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and Hidden Markov Models.

Bart Vanluyten - One of the best experts on this subject based on the ideXlab platform.

  • Equivalence of state representations for Hidden Markov Models
    Systems & Control Letters, 2008
    Co-Authors: Bart Vanluyten, Jan C. Willems, Bart De Moor
    Abstract:

    In this paper we consider the following problem for Hidden Markov Models: given a minimal Hidden Markov model, derive conditions for another Hidden Markov model to be equivalent and give a description of the complete set of equivalent Models. A distinction is made between quasi- and positive Hidden Markov Models and between Mealy and Moore Hidden Markov Models. We derive a condition for two positive Mealy Models to be equivalent and give a description of the complete set of Mealy Models that are equivalent to a given Mealy model. We show that under certain conditions minimal quasi-Moore Models are unique up to a permutation of the states. We derive a condition for two positive Moore Models to be equivalent and give a description of the complete set of Moore Models equivalent to a given Moore model. Finally, we compare the results for Hidden Markov Models and linear Gaussian systems.

  • Equivalence of state representations for Hidden Markov Models
    2007 European Control Conference (ECC), 2007
    Co-Authors: Bart Vanluyten, Jan C. Willems, Katrien De Cock, Bart De Moor
    Abstract:

    In this paper we consider the following problem for (quasi) Hidden Markov Models: given a minimal (quasi) Hidden Markov model, what can be said about the set of all equivalent (quasi) Hidden Markov Models of the same order. A distinction is made between Mealy and Moore type of Hidden Markov Models. A complete solution is presented for the quasi HMM case. For quasi Mealy Models, there exists already a description of the set of equivalent Models. In this paper, we prove that for minimal quasi Moore Models, the set of equivalent Models consists of only one element (up to a permutation of the states). Finally, we present some initial results for the positive HMM case and show a motivating simulation example.

  • CDC - A new approach for the identification of Hidden Markov Models
    2007 46th IEEE Conference on Decision and Control, 2007
    Co-Authors: Bart Vanluyten, Jan C. Willems, Bart De Moor
    Abstract:

    In this paper, we consider the approximate identification problem for Hidden Markov Models, i.e. given a finite- valued output string generated by an unknown Hidden Markov model, find an approximation of the underlying model. We propose a two-step procedure for the approximate identification problem. In the first step the underlying state sequence corresponding to the output sequence is estimated directly from the output data. In the second step the system matrices are calculated from the obtained state sequence and the given output sequence. In a simulation example the performance of our proposed method is compared with the performance of the classical Baum-Welch approach for identification of Hidden Markov Models.

Cheng-der Fuh - One of the best experts on this subject based on the ideXlab platform.

  • asymptotic bayesian theory of quickest change detection for Hidden Markov Models
    IEEE Transactions on Information Theory, 2019
    Co-Authors: Cheng-der Fuh, Alexander G. Tartakovsky
    Abstract:

    In the 1960s, Shiryaev developed a Bayesian theory of change-point detection in the i.i.d. case, which was generalized in the early 2000s by Tartakovsky and Veeravalli and recently by Tartakovsky (2017) for general stochastic Models assuming a certain stability of the log-likelihood ratio process. Hidden Markov Models represent a wide class of stochastic processes in a variety of applications. In this paper, we investigate the performance of the Bayesian Shiryaev change-point detection rule for Hidden Markov Models. We propose a set of regularity conditions under which the Shiryaev procedure is first-order asymptotically optimal in a Bayesian context, minimizing moments of the detection delay up to certain order asymptotically as the probability of false alarm goes to zero. The developed theory for Hidden Markov Models is based on Markov chain representation for the likelihood ratio and r -quick convergence for Markov random walks. In addition, applying Markov nonlinear renewal theory, we present a high-order asymptotic approximation for the expected delay to detection and a first-order asymptotic approximation for the probability of false alarm of the Shiryaev detection rule. We also study asymptotic properties of another popular change detection rule, the Shiryaev–Roberts rule, and provide some interesting examples.

  • Asymptotic Bayesian Theory of Quickest Change Detection for Hidden Markov Models
    arXiv: Statistics Theory, 2016
    Co-Authors: Cheng-der Fuh, Alexander G. Tartakovsky
    Abstract:

    In the 1960s, Shiryaev developed a Bayesian theory of change-point detection in the i.i.d. case, which was generalized in the beginning of the 2000s by Tartakovsky and Veeravalli for general stochastic Models assuming a certain stability of the log-likelihood ratio process. Hidden Markov Models represent a wide class of stochastic processes that are very useful in a variety of applications. In this paper, we investigate the performance of the Bayesian Shiryaev change-point detection rule for Hidden Markov Models. We propose a set of regularity conditions under which the Shiryaev procedure is first-order asymptotically optimal in a Bayesian context, minimizing moments of the detection delay up to certain order asymptotically as the probability of false alarm goes to zero. The developed theory for Hidden Markov Models is based on Markov chain representation for the likelihood ratio and r-quick convergence for Markov random walks. In addition, applying Markov nonlinear renewal theory, we present a high-order asymptotic approximation for the expected delay to detection of the Shiryaev detection rule. Asymptotic properties of another popular change detection rule, the Shiryaev{Roberts rule, is studied as well. Some interesting examples are given for illustration.

  • SPRT and CUSUM in Hidden Markov Models
    The Annals of Statistics, 2003
    Co-Authors: Cheng-der Fuh
    Abstract:

    In this paper, we study the problems of sequential probability ratio tests for parameterized Hidden Markov Models. We investigate in some detail the performance of the tests and derive corrected Brownian approximations for error probabilities and expected sample sizes. Asymptotic optimality of the sequential probability ratio test for testing simple hypotheses based on Hidden Markov chain data is established. Next, we consider the cumulative sum (CUSUM) procedure for change point detection in this model. Based on the renewal property of the stopping rule, CUSUM can be regarded as a repeated one-sided sequential probability ratio test. Asymptotic optimality of the CUSUM procedure is proved in the sense of Lorden (1971). Motivated by the sequential analysis in Hidden Markov Models, Wald's likelihood ratio identity and Wald's equation for products of Markov random matrices are also given. We apply these results to several types of Hidden Markov Models: i.i.d. Hidden Markov Models, switch Gaussian regression and switch Gaussian autoregression, which are commonly used in digital communications, speech recognition, bioinformatics and economics.