On the learnability and usage of acyclic probabilistic finite automata
type: Item
instance of: scholarly article
title: On the learnability and usage of acyclic probabilistic finite automata
zbMATH Open document ID: 0915.68124
author: Dana Ron
author: Yoram Singer
author: Naftali Tishby
published in: Journal of Computer and System Sciences
publication date: 1998-11-10T00:00:00Z
review text: The authors' main effort is to propose and analyze a distribution learning algorithm for certain acyclic probabilistic finite automata. Special attention is given to the modeling of short sequences that correspond to objects such as short DNA sequences, spoken words, or single handwritten letters. Specifically, they construct models for cursive handwritten letters (but no ideograms) and pronunciation models for spoken words. Formal results are given in the form of two theorems and several lemmas.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1220910
zbMATH Keywords: distribution learning algorithm
zbMATH Keywords: acyclic probabilistic finite automata
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
full work available at URL: jcss.1997.1555
OpenAlex ID: W3089948396
cites work: On the computational complexity of approximating distributions by probabilistic automata
cites work: Statistical Inference for Probabilistic Functions of Finite State Markov Chains
cites work: Efficient learning of typical finite automata from random walks
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: On the learnability of discrete distributions
cites work: Efficient noise-tolerant learning from statistical queries
cites work: Dynamical encoding of cursive handwriting
cites work: Q3214824
DOI: 10.1006/JCSS.1997.1555
Recommended article: Q3093192
Recommended article: Towards Feasible PAC-Learning of Probabilistic Deterministic Finite Automata
Recommended article: Algorithmic Learning Theory
Recommended article: Learning deterministic probabilistic automata from a model checking perspective
Recommended article: Learning Theory
Recommended article: Learning probabilistic automata: a study in state distinguishability
Recommended article: Learning probabilistic automata and Markov chains via queries
Recommended article: PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance
Recommended article: A Lower Bound for Learning Distributions Generated by Probabilistic Automata
description: scientific article; zbMATH DE number 1220910