Learning Hidden Markov Models Using Conditional Samples

Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, Cyril Zhang
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2014-2066, 2023.

Abstract

This paper is concerned with the computational and statistical complexity of learning the Hidden Markov model (HMM). Although HMMs are some of the most widely used tools in sequential and time series modeling, they are cryptographically hard to learn in the standard setting where one has access to i.i.d. samples of observation sequences. In this paper, we depart from this setup and consider an \emph{interactive access model}, in which the algorithm can query for samples from the \emph{conditional distributions} of the HMMs. We show that interactive access to the HMM enables computationally efficient learning algorithms, thereby bypassing cryptographic hardness.Specifically, we obtain efficient algorithms for learning HMMs in two settings: \begin{enumerate} \item An easier setting where we have query access to the exact conditional probabilities. Here our algorithm runs in polynomial time and makes polynomially many queries to approximate any HMM in total variation distance. \item A harder setting where we can only obtain samples from the conditional distributions. Here the performance of the algorithm depends on a new parameter, called the fidelity of the HMM. We show that this captures cryptographically hard instances and all previously known positive results. \end{enumerate} We also show that these results extend to a broader class of distributions with latent low rank structure. Our algorithms can be viewed as generalizations and robustifications of Angluin’s $L^*$ algorithm for learning deterministic finite automata from membership queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-mahajan23a, title = {Learning Hidden Markov Models Using Conditional Samples}, author = {Mahajan, Gaurav and Kakade, Sham and Krishnamurthy, Akshay and Zhang, Cyril}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {2014--2066}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/mahajan23a/mahajan23a.pdf}, url = {https://proceedings.mlr.press/v195/mahajan23a.html}, abstract = {This paper is concerned with the computational and statistical complexity of learning the Hidden Markov model (HMM). Although HMMs are some of the most widely used tools in sequential and time series modeling, they are cryptographically hard to learn in the standard setting where one has access to i.i.d. samples of observation sequences. In this paper, we depart from this setup and consider an \emph{interactive access model}, in which the algorithm can query for samples from the \emph{conditional distributions} of the HMMs. We show that interactive access to the HMM enables computationally efficient learning algorithms, thereby bypassing cryptographic hardness.Specifically, we obtain efficient algorithms for learning HMMs in two settings: \begin{enumerate} \item An easier setting where we have query access to the exact conditional probabilities. Here our algorithm runs in polynomial time and makes polynomially many queries to approximate any HMM in total variation distance. \item A harder setting where we can only obtain samples from the conditional distributions. Here the performance of the algorithm depends on a new parameter, called the fidelity of the HMM. We show that this captures cryptographically hard instances and all previously known positive results. \end{enumerate} We also show that these results extend to a broader class of distributions with latent low rank structure. Our algorithms can be viewed as generalizations and robustifications of Angluin’s $L^*$ algorithm for learning deterministic finite automata from membership queries.} }
Endnote
%0 Conference Paper %T Learning Hidden Markov Models Using Conditional Samples %A Gaurav Mahajan %A Sham Kakade %A Akshay Krishnamurthy %A Cyril Zhang %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-mahajan23a %I PMLR %P 2014--2066 %U https://proceedings.mlr.press/v195/mahajan23a.html %V 195 %X This paper is concerned with the computational and statistical complexity of learning the Hidden Markov model (HMM). Although HMMs are some of the most widely used tools in sequential and time series modeling, they are cryptographically hard to learn in the standard setting where one has access to i.i.d. samples of observation sequences. In this paper, we depart from this setup and consider an \emph{interactive access model}, in which the algorithm can query for samples from the \emph{conditional distributions} of the HMMs. We show that interactive access to the HMM enables computationally efficient learning algorithms, thereby bypassing cryptographic hardness.Specifically, we obtain efficient algorithms for learning HMMs in two settings: \begin{enumerate} \item An easier setting where we have query access to the exact conditional probabilities. Here our algorithm runs in polynomial time and makes polynomially many queries to approximate any HMM in total variation distance. \item A harder setting where we can only obtain samples from the conditional distributions. Here the performance of the algorithm depends on a new parameter, called the fidelity of the HMM. We show that this captures cryptographically hard instances and all previously known positive results. \end{enumerate} We also show that these results extend to a broader class of distributions with latent low rank structure. Our algorithms can be viewed as generalizations and robustifications of Angluin’s $L^*$ algorithm for learning deterministic finite automata from membership queries.
APA
Mahajan, G., Kakade, S., Krishnamurthy, A. & Zhang, C.. (2023). Learning Hidden Markov Models Using Conditional Samples. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:2014-2066 Available from https://proceedings.mlr.press/v195/mahajan23a.html.

Related Material