IJPAM: Volume 115, No. 3 (2017)

Title

INFERENCE AND LEARNING IN STOCHASTIC AUTOMATA

Authors

Karl-Heinz Zimmermann
Department of Electrical Engineering,
Computer Science, Mathematics
Hamburg University of Technology
21071, Hamburg, GERMANY

Abstract

Machine learning provides algorithms that can learn from data and make inferences or predictions on data. Stochastic automata are a class of input/output devices which can model components in machine learning scenarios. In this paper, we provide an inference algorithm for stochastic automata which is related to the Viterbi algorithm. Moreover, we specify a learning algorithm using the expectation-maximization technique and describe a more efficient implementation which is related to the Baum-Welch algorithm.

History

Received: July 14, 2017
Revised: June 3, 2017
Published: July 27, 2017

AMS Classification, Key Words

AMS Subject Classification: 68Q70, 68T05, 16Y60
Key Words and Phrases: stochastic automaton, tropical semiring, dynamic programming, inference, learning

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
P. D'Argenio, J.-P. Katoen, A theory of stochastic systems: Part I: stochastic automata, Information and Control, 203, No. 1 (2005), 1-38. https://dx.doi.org/10.1016/j.ic.2005.07.001

2
P. D'Argenio, J.-P. Katoen, A theory of stochastic systems: Part II: process algebra, Information and Control, 203, No. 1 (2005), 39-74. https://dx.doi.org/10.1016/j.ic.2005.07.002

3
D. Barber, Bayes Reasoning and Machine Learning, Cambridge Univ. Press, Cambridge (2012).

4
D. Blackwell, L. Breiman, A.J. Thomasian, The capacitites of certain channel classes under random coding, Annals of Mathematical Statistics, 31, No. 3 (1969), 558-567. https://dx.doi.org/10.1214/aoms/1177705783

5
V. Claus, Stochastische Automaten, Teubner, Stuttgart (1971).

6
J. von Neumann, Probabilistic logic and the synthesis of reliable organisms from unreliable components, in: Automata Studies, C. Shannon and J. McCarthy (eds), Annals of Mathematical Studies, 34, Princeton Univ. Press, Princeton, NJ (1956). https://dx.doi.org/10.1515/9781400882618-003

7
J. W. Carlyle, Reduced forms for stochastic sequential machines, Journal Mathematical Analysis and Applications, 7, No. 2 (1963), 167-165. https://dx.doi.org/10.1016/0022-247X(63)90045-3

8
L. Pachter, B. Sturmfels, Algebraic Statistics for Computational Biology, Cambridge Univ. Press, Cambridge (2005).

9
L. R. Rabiner, A tutorial on hidden Markov models and selected applications, Proceedings of the IEEE, 77, No. 2 (1989), 257-286. https://dx.doi.org/10.1109/5.18626

10
M. O. Rabin, Probabilistic automata, Information and Control, 6, No. 3 (1963), 230-245. https://dx.doi.org/10.1016/S0019-9958(63)90290-0

11
M. O. Rabin, D. Scott, Finite automata and their decision problems, IBM Journal Research Development, 3, No. 3 (1959), 114-125. https://dx.doi.org/10.1147/rd.32.0114

12
G. Ricciardi, R. Pieraccini, E. Bocchieri, Stochastic automata for language modeling, Computer Speech and Language, 10 (1996), 265-293. https://dx.doi.org/10.1006/csla.1996.0014

13
T. Koski, J. M. Noble, Bayesian Networks, Wiley, New York (2009).

14
L. Rabiner, B. H. Juang, Fundamentals of Speech Recognition, Prentice Hall, Englewood Cliffs, NJ (1993).

15
A. Salomaa, Theory of Automata, Pergamon Press, Oxford (1969).

16
C. E. Shannon, The mathematical theory of communication, Bell System Technical Journal, 5, No. 1 (1948), 379-423. https://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x

17
P. H. Starke, Stochastische Ereignisse und Wortmengen, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 12 (1966), 61-68. https://dx.doi.org/10.1002/malq.19660120108

18
M. Thathachar, Stochastic automata and learning systems, Sadhana, 15 (2009), 263-281. https://dx.doi.org/10.1007/BF02811325

19
A. J. Viterbi, Error bounds for convolutional codes and an asymptotic optimum decoding algorithm, IEEE Transactions on Information Theory, 13, No. 2 (1967) 260-269. https://dx.doi.org/10.1109/TIT.1967.1054010

20
K.-H. Zimmermann, Algebraic Statistics, TubDok, Hamburg, Germany (2016).

How to Cite?

DOI: 10.12732/ijpam.v115i3.15 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 115
Issue: 3
Pages: 621 - 639


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).