Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T10:15:44.606Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic Decision Theory

Published online by Cambridge University Press:  27 July 2009

J. Robin B. Cockett ,
Jalel Zrida  and
J. Douglas Birdwell
J. Robin B. Cockett
Affiliation:
Department of Computer ScienceThe University of Tennessee Knoxville, Tennessee 37996-1301
Jalel Zrida
Affiliation:
Department of Electrical and Computer EngineeringThe University of Tennessee Knoxville, Tennessee 37996-2100
J. Douglas Birdwell
Affiliation:
Department of Electrical and Computer EngineeringThe University of Tennessee Knoxville, Tennessee 37996-2100
Get access Rights & Permissions [Opens in a new window]

Abstract

The manipulations and basic results of stochastic decision theory are introduced. The manipulations of idempotence, transposition, and repetition, introduced for deterministic decision trees, can be used to manipulate stochastic trees. However, there are two major differences. First, in order to obtain a complete set of manipulations it is necessary to introduce an additional rule called indifference. Second, these identities must be treated as rules of inference. Not all the rules can be soundly applied in both directions; in particular, idempotence is a one-way rule.

A manipulation of a stochastic decision tree not only alters the structure of the tree, but also the probability distributions associated with the tree. This allows probability calculation to be viewed as structural manipulation. In particular, a retrieval corresponds to a conditional probability calculation. The algorithm for doing this calculation has, therefore, many applications. For example, the solution to the classical state-estimation problem and the retrieval of information from probabilistic or uncertain knowledge bases may both be viewed as an application of this algorithm.

The main result of this paper is that these manipulations are complete and sound. In order to prove this result, it is necessary to have a semantic setting for these theories. The setting chosen is the category of description spaces which is a generalization of the category of bounded measure spaces with maps which do not increase measure. The proof of this result exploits the retrieval properties of stochastic terms and its relationship to conditional probability calculations in the models.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 1 , January 1989 , pp. 13 - 54
Copyright
Copyright © Cambridge University Press 1989

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adámek, J. (1983). Theory of mathematical structures. Prague, Czechoslovakia: Reidel.Google Scholar
Arbib, M.A. & Manes, E.G. (1975). Arrows, structures, and functors: The categorical imperative. New York: Academic Press.Google Scholar
Barr, A. & Feigenbaum, E.A. (1981). The handbook of artificial intelligence, Vol. 1. Stanford, California: HeurisTech Press.Google Scholar
Barr, A. & Wells, C. (1985). Toposes, triples, and theories. New York: Springer-Verlag.CrossRefGoogle Scholar
Bloom, S.L. & Tindell, R. (1983). Varieties of if … then … else … SIAM Journal on Computing 12(4): 677–707.CrossRefGoogle Scholar
Bucur, I. & Deleanu, A. (1968). Introduction to the theory of categories and functors. London: Wiley & Sons.Google Scholar
Cockett, J.R.B. (1987). Discrete decision theory: manipulations. Theoretical Computer Science 54: 215–236.CrossRefGoogle Scholar
Cockett, J.R.B. (1987). Optimizing decision expressions. Fundamenta Informaticae X: 93–114.CrossRefGoogle Scholar
Cockett, J.R.B. (1987). Discrete decision theory: completeness. Technical Report, CS−87−69, Department of Computer Science, University of Tennessee at Knoxville, TN, 01 (To appear in revised form in Theoretical Computer Science).Google Scholar
Dattatreya, G.R. & Kanal, L.N. (1986). Adaptive pattern recognition and random costs and its application to decision trees. IEEE Transactions on Systems, Man, and Cybernetics SMC-16(2): 208–218.Google Scholar
Doberkat, E.E. (1981). Stochastic automata: stability, nondeterminism, and prediction. New York: Springer-Verlag.CrossRefGoogle Scholar
Goldblatt, R. (1984). Topoi: the categorical analysis of logic. Study in logic and the foundations of mathematics, Barwise, J. et al. (eds.), Vol. 98. New York: North-Holland.Google Scholar
Grätzer, G. (1978). General lattice theory. New York: Academic Press.CrossRefGoogle Scholar
Grätzer, G. (1979). Universal algebra. New York: Springer-Verlag.CrossRefGoogle Scholar
Guessarian, I. & Meseguer, J. (1987). Onthe axiomatization of “if-then-else”. SIAM Journal an Computing 16(2): 332–357.CrossRefGoogle Scholar
Johnstone, P.T. (1977). Topos theory. London: Academic Press.Google Scholar
Kalman, R.E., Falb, P.L., & Arbib, M.A. (1969). Topics in mathematical system theory. New York: McGraw-Hill.Google Scholar
Kolman, B. & Busby, R.C. (1984). Discrete mathematical structures for computer science. New Jersey: Prentice-Hall.Google Scholar
Lorenz, A.A. (1974). Stochastic automata. Constructive theory. New York and Toronto: Wiley & Sons.Google Scholar
Mac, Lane S. (1971). Categories for working mathematicians. New York: Springer-Verlag.Google Scholar
Manes, E.G. (1976). Algebraic theories. Vol. 26 of GTM. New York: Springer-Verlag.CrossRefGoogle Scholar
Mitchell, B. (1965). Theory of categories. New York: Academic Press.Google Scholar
Moret, B.M.E., Thomason, M.G. & Gonzalez, R.C. (1980). The activity of a variable and its relation to decision trees. ACM Transactions on Programming Languages and Systems (4): 580–595.CrossRefGoogle Scholar
Moret, B.M.E. (1980). The representation of discrete functions by decision trees: aspects of complexity and problems of testing. Ph.D. Dissertation, The University of Tennessee at Knoxville, Department of Electrical Engineering, Knoxville.Google Scholar
Moret, B.M.E. (1982). Decision trees and diagrams. Computing Surveys 14(4): 593–623.CrossRefGoogle Scholar
Nilsson, N.J. (1986). Probabilistic logic. Artificial Intelligence 28: 71–87.CrossRefGoogle Scholar
Papoulis, A. (1965). Probability, random variables, and stochastic processes. New York: McGraw-Hill.Google Scholar
Paz, A. (1971). Introduction to probabilistic automata. New York: Academic Press.Google Scholar
Pearl, J. (1986). Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29: 241–288.CrossRefGoogle Scholar
Peebles, P.Z. Jr, (1980). Probability, random variables, and random signal principles. New York: McGraw-Hill.Google Scholar
Rudin, W. (1966). Real and complex analysis. New York: McGraw-Hill.Google Scholar
Simon, J.C. (1976). Computer oriented learning processes. The Netherlands: Noordhoff, Leyden.CrossRefGoogle Scholar
Zrida, J., Birdwell, J.D. & Cockett, J.R.B. (1987). Uncertain knowledge representation via stochastic decision trees. Proceedings of the Scientific Symposium MARI 87, Cognitiva 87/Electronic Image Electronique, La Villette, Paris, France, pp. 111–116.Google Scholar
Zrida, J., Birdwell, J.D. & Cockett, J.R.B. (1987). State estimation for static systems defined by stochastic decision trees. Proceedings of the 19th Southeastern Symposium on System Theory, Clemson, South Carolina, pp. 487–491.Google Scholar
Zrida, J., Birdwell, J.D. & Cockett, J.R.B. (1986). State estimation in finite stochastic decision trees. Colloquia Proceedings of the International Symposium on Methodologies for Intelligent Systems, Knoxville, TN, pp. 35–49.Google Scholar