摘要
赋值代数是从软约束、关系数据库及信任函数等多个理论体系中抽象出来的一种应用于对非确定性信息进行局部计算的代数框架.最近的研究表明,赋值代数的很多重要的实例,包括约束系统,可能性位势,概率位势等都可以由一些特殊的半环诱导而得.本文主要围绕半环诱导的赋值代数中的优解问题、赋值代数的结构及相关结构之间的联系展开研究.在优解问题的研究中,给出了映射保投影问题的优解的条件.这为寻找合适的转移函数提供了依据.通过在赋值代数结构方面的讨论,得到了各种赋值代数之间、半环诱导的赋值代数与半环之间在结构上面的较完整的相互关系.通过带标记紧信息代数的举例,首次将软集引入到了赋值代数的研究对象之中.
文章的主要工作包括以下几个方面:
(1)半环诱导的赋值代数上的投影问题:赋值代数上的投影问题关注的是赋值集在局部区域上所得的相应信息.文中首先定义了投影问题之间的两个序关系:解序和问题序.分别探讨了序之间以及保序映射之间的关系.对于两个半环间的转移满射f,证明得到它保投影问题的解序的充分必要条件是它为一个半环同态.利用构造性的方法得到了映射保投影问题的优解的充分条件.研究了映射保投影问题的优解和它保解序之间的关系.证得如果一个变量集系统至少含有四个变量且其中有一个变量的框架含有多于两个元素,则满射f保投影问题的优解及半环的单位元和零元的充要条件为它保投影问题的解序且关于半环上的序是反保序的.
(2)全序半环诱导的赋值的解组合和解扩展:对于全序半环诱导的赋值,证得它的解组合之集在转移映射为保加法运算的单射时不发生改变.给出了投影问题的最佳接近值的表示.得到了在弱条件下成立的解扩展定理.
(3)赋值代数的同态:研究了半环诱导的赋值代数和半环在代数结构上的联系.证得了半环同构是赋值代数同构的充分条件.半环中的乘法半群的同构是赋值代数同构的必要条件.引入了具有不同域集格的赋值代数间的广义同态的概念.证明了赋值代数的广义同态基本定理.
(4)两类连续信息代数的性质与联系:分别给出了无标记信息代数和带标记信息代数的连续性和强连续性的概念,并研究了它们相互之间的关系.证得无标记信息代数和带标记信息代数关于连续性是相互对应的.定义了无标记信息代数间的连续函数的概念.证得无标记强连续信息代数的连续函数空间仍可构成一个强连续信息代数.
(5)紧信息代数的获取途径及相关范畴的性质:分别改进和新定义了带标记的紧信息代数和带标记的强紧信息代数的概念.验证表明两类信息代数在紧性和强紧性之间可以建立完全对应的关系.给出了两种获取无标记的强紧信息代数的方法:首先,若半环关于其上的反序是代数格,则该半环诱导的无标记信息代数是强紧信息代数;接着给出了从一般的无标记信息代数实现紧化得到一个紧信息代数的具体过程.证明了强紧信息代数和强连续信息代数分别与连续映射构成的范畴均是笛卡儿闭的.
(6)带标记紧信息代数的例子:在软集间引入了软信息序的概念.证明了同一个初始集上的软集族关于软信息序是一个完全分配格.同时,该软集族与标记运算、扩展交运算及投影运算构成一个带标记的信息代数.证得在同一个初始集上,属性集为有限集的软集族构成了一个带标记的强紧信息代数.
Valuation algebra is an algebraic structure for permitting local computation of non-deterministic information, which is abstracted from many theoretical for-malisms including soft constraints, relation databases, belief functions and so on. Recent research demonstrates that many important instances such as constraint sys-tem, possibility potential, and probability potential can be induced by some special semirings. In this paper, we mainly study the issue about the optimal solutions of projection problems in semiring-induced valuation algebras, the structures of valu-ation algebras and the relationship among them. In the study on optimal solutions of projection problems, we give the conditions of mappings preserving optimal so-lutions. These conclusions provide a basis for finding out some suitable transitive mappings. By the study on the structures of valuation algebras, we realize the re-lationship among valuation algebras with different structures and the relationship between semiring-induced valuation algebras and semirings. We present an example of labeled compact information algebra, and therefore take the set of all soft sets over a universal set as a research object of information algebras firstly.
The main contributions in this thesis are listed as follows:
(1) Projection problems on semiring-induced valuation algebras:Projection problems over valuation algebras focus on the corresponding information which is obtained in a local domain of valuations. Firstly, solution-order and problem-order on projection problems of semiring-induced valuation algebras are defined. The rela-tionship among orderings, and the relationship among mappings that preserve these orderings are discussed respectively. For a transitive surjective f between two semir-ings, it preserves the solution-order if and only if it is a semiring homomorphism. By using constructive methods, some sufficient conditions of mapping preserving optimal solutions of projection problems are given. The relationship between map-pings preserving the optimal solutions and its preserving the solution-order relation is studied. It is shown that if there exist at least four variables in a system and one of frames includes more than two elements, then a surjective f preserves the optimal solutions of projection problems and preserves the zero element, the unit element of semiring if and only if f is order-reflecting with respective to the order relation on semiring and preserves the solution-order of projection problems.
(2) Solution configurations and solution extensions of valuations:It is shown that, for a valuation induced by a totally ordered semiring, the set of its solution configurations will not be changed if the transitive mapping preserves the plus operation. The expression of the maximal value for projection problem is given. The theorem of solution extension of valuations under a weaker condition is presented.
(3) Homomorphism of valuation algebras:The relationship on algebraic struc-ture between semirings and semiring-induced valuation algebras is studied. It is shown that the isomorphism between semiring-induced valuation algebras is a nec-essary condition of the isomorphism between semirings, and also a necessary condi-tion of the isomorphism between multiplicative semigroups of semirings. A general valuation homomorphism based on different domains is defined, and the Homomor-phism Theorem of valuation algebra is proved.
(4) The properties of two types of continuous information algebras and the relationship between them:The continuity and strong continuity in information algebras are introduced respectively. By studying the relationship between domain-free information algebras and labeled information algebras, it is demonstrated that they do correspond to each other on continuity. A more general notion of con-tinuous function which is defined between two domain-free continuous information algebras is presented. It is shown that the set of all continuous functions between s-continuous information algebras forms a new s-continuous information algebra.
(5) The methods of obtaining compact information algebras and the properties of the related category:The definition of labeled strongly compact information alge-bra is given. It is shown that there exist complete correspondences between labeled information algebras and domain-free information algebras with respect to the com-pactness and strong compactness. Two methods of obtaining compact information algebras are presented. It is shown that a domain-free information algebra induced by a semiring is compact, if the semiring is an algebraic lattice with respect to the converse order relation. Next, an approach to realize the compactification of a gen-eral domain-free information algebra is offered. It is shown that the two categories of strong compact information algebras and strong continuous information algebras are Cartesian closed.
(6) An example of labeled compact information algebra:A new kind of order relation on fuzzy soft sets, called soft information order, is introduced. It is shown that the collection of all fuzzy soft sets (over a given soft universe), equipped with this new order, forms a completely distributive lattice. With the operations of la-beling, extended intersection and projection, it is also a labeled information algebra. It is declared that the set of all soft sets, which have finite parameters set, is formed a labeled strongly compact information algebra.
引文
[1]P.P. Shenoy. A valuation-based language for expert systems[J]. International Journal of Approximate Reasoning,1989,3:383-411.
[2]J. Kohlas, P.P. Shenoy. Computation in valuation algebras[M]. J. Kohlas, S. Moral.//D.V. Gabbay, P.Smets. Handbook of Defeasible Reasoning and Uncer-tainty Management Systems, vol.5:Algorithms for Uncertainty and Defeasible Reasoning. Dordrecht:Kluwer,2000:5-40.
[3]J. Kohlas. Information Algebras:Generic Structures for Inference[M]. London: Springer-Verlag,2003.
[4]R. Haenni. Ordered valuation algebras:A generic framework for approximating inference [J]. International Journal of Approximate Reasoning,2004,37:1-41.
[5]A-L. Jousselme, E. Bosse. Valuation networks for implementing fusion algo-rithms:An application to target identification[R]. Ottawa:Defence Research & Development Canada,2006.
[6]C. Schneuwly. Computing in Valuation Algebras[D]. Ph.D. thesis. Department of Informatics, University of Fribourg,2007.
[7]P.P. Shenoy. Valuation-Based Systems:A Framework for Managing Uncer-tainty in Expert Systems[M]//L. A. Zadeh, J. Kacprzyk. Fuzzy Logic for the Management of Uncertainty. New York:John Wiley & Sons,1992:83-104,
[8]P.P. Shenoy. Consistency in Valuation-Based Systems [J]. ORSA Journal on Computing,1994,6(3):281-291.
[9]J. Kohlas, N. Wilson. Lecture Notes on The Algebraic Theory of Information[EB/OL].2008-12-22.[2010-03-25]. http://diuf.unifr.ch/drupal/tns /sites/diuf.unifr.ch.drupal.tns/files/file/kohlas/main.pdf.
[10]J. Kohlas, N. Wilson. Semiring induced valuation algebras:Exact and ap-proximate local computation algorithms [J]. Artifical Intelligence,2008,172: 1360-1399.
[11]M. Pouly. A Generic Architecture for Local Computation[D]. Master Thesis. Department of Informatics, University of Fribourg,2004. http://marcpouly.ch /pdf/pouly04.pdf.
[12]M. Pouly. A Generic Framework for Local Computation[D]. Ph.D. Thesis. De-partment of Informatics, University of Fribourg,2008. http://marcpouly.ch /pdf/pouly08.pdf.
[13]J. Kohlas, R. Haenni, S. Moral. Propositional information systems[J]. Journal of Logic and Computation,1999,9(5):651-681.
[14]J. Langel. Local Computation with Models in Propositional Logic[D]. Ph.D. Thesis. Department of Informatics, University of Fribourg,2004. http://diuf.unifr.ch/diva/diplome05/html/pdf/jutta_langel.pdf.
[15]胡小建.基于赋值代数的BN概率推理的局部计算模型[J].中国科技大学学报,2005,35(6):805-814.
[16]管雪冲,李永明.半环诱导的赋值代数的解轮廓和解扩展[J].计算机工程与应用,2010,46(35):42-44.
[17]管雪冲,李永明.投影问题的序关系研究[J].陕西师范大学学报(自然科学版)2011,39(1):5-9.
[18]管雪冲,李永明On homomorphism of valuation algebras [J]. Communications in Mathematical Research,2011,27(1):181-192.
[19]管雪冲,李永明.连续信息代数[J].模糊系统与数学,2011,25(1):103-111.
[20]N. Lehmann, R. Haenni. Belief function propagation based on shenoy's fusion algorithm[C]. IPMU'00, Proceedings of the 8th international conference,2000: 1928-1931. http://www.iam.unibe.ch/haenni/Homepage/PAPERS/TR00-1.pdf.
[21]R. Haenni, N. Lehmann. Effcient hypertree construction[R]. Fribourg:Insti-tute of informatics, University of fribourg,1999. http://www.iam.unibe.ch/ haenni/Homepage/PAPERS/TR99-1.pdf
[22]F.V. Jensen, S.L. Lauritzen, K.G. Olesen. Bayesian updating in causal proba-bilistic networks by local computation [J]. Computational Statistics Quarterly, 1990,4:269-282.
[23]S.L. Lauritzen, F.V. Jensen. Local computation with valuations from a com-mutative semigroup[J]. Annals of Mathematics and Artificial Intelligence,1997, 21(1):51-69.
[24]S.L. Lauritzen, D.J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems [J]. Journal of the Royal Statistical Society:Series B,1998,50,157-224.
[25]N. Lehmann. Argumentation System and Belief Functions[D]. Ph.D. thesis. Department of Informatics, University of Fribourg,,2001.
[26]H. Fargier, N. Wilson. Local computation schemes with partially ordered pref-erences [M]//C. Sossai, G. Chemello. Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Lecture Notes in Computer Science,2009,5590: 34-45.
[27]H. Fargier, E. Rollon, N. Wilson. Enabling local computation for partially ordered preferences[J]. Constraints,2010,15:516-539.
[28]F. Pichon, T. Denoeux. A new singular property of the unnormalized Demp-ster's rule among uninorm-based combination rules[C]//L. Magdalena, M. Ojeda-Aciego, J.L. Verdegay. Proceedings of IPMU,2008:314-321.
[29]P.P. Shenoy. Binary join trees for computing marginals in the Shenoy-Shafer ar-chitecture [J]. International Journal of Approximate Reasoning,1997,17:239-263.
[30]G. Shafer. An axiomatic study of computation in hypertrees[R]. Work-ing Paper No.232, School of Business, University of Kansas, Lawrence. http://www.glennshafer.com/assets/downloads/hypertrees_91WP232.pdf.
[31]P.P. Shenoy, Glenn Shafer. Axioms for probability and belief-function propa-gation[M]//R.D. Shachter, T.S. Levitt, L.N. Kanal, J.F. Lemmer. Uncertainty in Artificial Intelligence 4. Amsterdam:North-Holland,1990:169-198.
[32]P.P. Shenoy. Using possibility theory in expert systems [J]. Fuzzy Sets and Sys-tems,1992,51(2):129-142.
[33]P.P. Shenoy. On Spohn's rule for revision of beliefs[J]. International Journal of Approximate Reasoning,1991,5(2):149-181.
[34]C. Eichenberger. Local computation with Gaussian potentials[R]. Fribourg:De-partment of Informatics, University of Fribourg,2006. http://www.irit.fr /LC/WIGSK06/Eichenberger_wigsk06.pdf.
[35]M. Pouly. Implementation of a generic architecture for local computation[C]// J. Kohlas, J. Mengin, N. Wilson. ECAI'04,16th European Conference on Ar-tificial Intelligence, Workshop 22 on "Local Computation for Logics and Un-certainty",2004:31-37.
[36]S. Bistarelli, U. Montanari, F. Rossi. Constraint solving over semirings[C]. Pro-ceedings of International Joint Conference of Artifical Intelligence 95. San Fran-cisco:Morgan Kaufmann,1995:624-630.
[37]S. Bistarelli, H. Fargier, U. Montanari, et al. Semiring-based CSPs and val-ued CSPs:Basic properties and comparison[M]//Michael Jampel. Over-Constrained Systems. Springer-Verlang, LNCS 1106,1996:111-150.
[38]S. Bistarelli, U. Montanari, F. Rossi. Semiring-based constraint satisfaction and optimization [J]. Journal of ACM,1997,44(2):201-236.
[39]S. Bistarelli, H. Fargier, U. Montanari, et al. Semiring-based CSPs and valued CSPs:Frameworks, properties, and comparison[J]. Constraints,1999,4(3): 199-240.
[40]S. Bistarelli, P. Codognet, F. Rossi. Abstracting soft constraints:Framework, properties, examples[J]. Artificial Intelligence,2002,139:175-211.
[41]S. Bistarelli. Semirings for Soft Constraint Solving and Programming[M]. Vol-ume 2962 of Lecture Notes in Computer Science. New York:Springer-Verlag, 2004.
[42]D. Maier. The Theory of Relational Databases[M]. London:Pitman,1983.
[43]J. Kohlas. Uncertain information:Random variables in graded semilattices[J]. International Journal of Approximate Reasoning,2007,46:17-34.
[44]G. Gierz, et al. Continuous Lattices and Domains:Encyclopedia of Mathemat-ics and its Applications[M]. Cambridge, Eng.:Cambridge University Press, 2003.
[45]郑崇友,樊磊,崔宏斌Frame与连续格(第二版).北京:首都师范大学出版社,2000.
[46]A. Jung. Cartesian Closed Categories of Domains[D]. Volume 66 of CWI Tracts, Centrum voor Wiskunde en Informatica, Amsterdam,1989.
[47]B.A. Davey, H.A. Priestley. Introduction to Latticees and Order[M]. Cam-bridge:Cambridge University Press,2002.
[48]S. Burris, H. P. Sankappanavar. A Course in Universal Algebra[M]. New York: Springer-Verlag,1981.
[49]G. Bergman. A Invitation to General Algebras and Constructions[M]. Berkeley: Henry Helson,1998.
[50]J.B. Nation. Notes on Lattice Theory[EB/OL].[2009-10-26]. http://www. math.hawaii.edu/jb/books.html.
[51]A.K. Mackworth. Constraint satisfaction[M]//S.C. Shapiro. Encyclopedia of Artificial Intelligence(second edition), New York:John Wiley & Sons Ltd., 1992:285-293.
[52]M. Wachter, R. Haenni, M. Pouly. Optimizing inference in bayesian networks and semiring valuation algebras[G]//A. Gelbukh, A.F. Kuri Morales. MICAI 2007, LNAI, Springer Heidelberg,2007,4827:236-247.
[53]B.R. Cobb, P.P. Shenoy. Inference in hybrid Bayesian networks with mixtures of truncated exponentials [J]. International Journal of Approximate Reasoning, 2006,41:257-286.
[54]T. Schmidt, P.P. Shenoy. Some improvements to the Shenoy-Shafer and Hugin architectures for computing marginals[J]. Artificial Intelligence,1998,102:323-333.
[55]R. Dechter. Bucket Elimination:A unifying framework for reasoning[J]. Arti-ficial Intelligence,1999,113:41-85.
[56]M. Pouly. Nenok 1.1 user guide[R]. Fribourg:Department of Informatics, Uni-versity of Fribourg,2006. http://marcpouly.ch/pdf/poulykohlas05.pdf.
[57]T. Walsh, F. Giunchiglia. A theory of abstraction [J]. Artificial Intelligence, 1992,56(2-3):323-390.
[58]R. Kaschek. A little theory of abstraction [C]. Proceedings of Modellierung. Lecture Notes in Computer Science. Berlin:Springer-Verlag,45,2004:75-92.
[59]S.J. Li, M. Ying. Soft constraint abstraction based on semiring homomor-phism[J]. Theoretical Computer Science,2008,403:192-201.
[60]M. Pouly, R. Haenni, M. Wachter. Compiling solution configurations in semir-ing valuation systems//A. Gelbukh, A.F. Kuri Morales. MICAI 2007, LNAI, Springer Heidelberg,2007,4827:248-259.
[61]U. Hebisch, H.J. Weinert. Semirings:algebraic theory and applications in com-puter science. Singapore:World Scientific Publishing,1993.
[62]熊金城.点集拓扑讲义(第二版)[M].北京:高等教育出版社,2005.
[63]J.L. Kelley. General Topology[M]. Volume 27 of Graduate Texts in Mathemat-ics. New York:Springer-Verlag,1975.
[64]M.A. Armstrong. Basic Topology[M]. Undergraduate Texts in Mathematics. New York:Springer-Verlag,1983.
[65]Y.M. Li, Z.H. Li. Free semilattices and strongly free semilattices generated by partially ordered sets[J]. Northeastern Mathematics Journal,1993,9(3):359-366.
[66]郭智莲,赵彬.自由Dcpo和自由并完备格的结构和性质[J].陕西师范大学学报(自然科学版),2005,33(4):11-14.
[67]M.B. Smyth. The largest Cartesian closed category of domains[J]. Theoretical Computer Science,1983,27:109-119.
[68]P. Taylor. An algebraic approach to stable domains[J]. Journal of Pure and Applied Algebra,1990,64:171-203.
[69]S. Mac Lane. Categories for the Working Mathematician[M]. New York: Springer-Verlag,1971.
[70]B.C. Pierce. Basic Category Theory for Computer Scientists[M]. Cambridge Mass.:The MIT Press,1991.
[71]D. Turi. Category Theory Lecture Notes[EB/OL]. [2009-09-26]. Laboratory for Foundations of Computer Science, University of Edinburgh. September 1996-December 2001. http://www.dcs.ed.ac.uk/home/dt/CT/categories.pdf.
[72]J. Adamek, G. Strecker, H. Herrlich. Abstract and Concrete Categories:The joy of cats[M]. New York:John Wiley and Sons,1990.
[73]Z. Pawlak. Rough sets[J]. Internaional Journal of Information and Computation Science,1982,11:341-356.
[74]L.A. Zadeh. Fuzzy sets[J]. Information Control,1965,8:338-353.
[75]李永明.模糊系统分析[M].北京:科学出版社,2005.
[76]D. Molodtsov. Soft set theory-First results [J]. Computers & Mathematics with Applications,1999,37:19-31.
[77]P.K. Maji, R. Biswas, A.R. Roy. Soft set theory [J]. Computers & Mathematics with Applications,2003,45:555-562.
[78]H. Aktas, N. Cagman. Soft sets and soft groups [J]. Information Science,2007, 177:2726-2735.
[79]Y.B. Jun, C.H. Park. Applications of soft sets in ideal theory of BCK/BCI-algebras[J]. Information Sciences,2008,178:2466-2475.
[80]F. Feng, Y.B. Jun, X.Z. Zhao. Soft semirings [J]. Computers & Mathematics with Applications,2008,56:2621-2628.
[81]D. Chen, E.C.C. Tsang, D.S. Yeung, X. Wang. The parametrization reduction of soft sets and its applications [J]. Computers & Mathematics with Applica-tions,2005,49:757-763.
[82]A.R. Roy, P.K. Maji. A fuzzy soft set theoretic approach to decision making problems [J]. Computers & Mathematics with Applications,2007,203:412-418.
[83]Z. Kong, L.Q. Gao, L.F. Wang. Comment on a fuzzy soft set theoretic approach to decision making problems [J]. Computers & Mathematics with Applications, 2009,223:540-542.
[84]F. Feng, Y. B. Jun, X.Y. Liu, L.F. Li. An adjustable approach to fuzzy soft set based decision making[J]. Journal of Computational and Applied Mathematics, 2010,234:10-20.
[85]M. Irfan Ali, F. Feng, X.Y. Liu, W.K. Min, M. Shabir. On some new operations in soft set theory [J]. Computers & Mathematics with Applications,2009,57: 1547-1553.
[86]C.F. Yang. A note on soft set theory [J]. Computers & Mathematics with Ap-plications,2008,56:1899-1900.
[87]L.S. Xu, X.X. Mao. Strongly continuous posets and the local Scott topology [J]. Journal of Mathematical Analysis and Applications.2008,345:816-824.
[88]管雪冲,王戈平.一类局部定向完备集及其范畴的性质[J].数学进展,2005,34(6):677-682.
[89]徐爱军,王戈平.代数的局部完备集范畴和FS-局部dcpo范畴的笛卡儿闭性[J].数学进展,2006,35(4):485-492.
[90]M.B. Smyth. Topology[M]//S. Abramsky, D. Gabbay, T.S.E. Maibaum. Hand-book of Logic in Computer Science. Oxford:Oxford Science Publications,1992: 642-761.
[91]A. Ghose, P. Harvey. Metric SCSPs:Partial Constraint Satisfaction via Semir-ing CSPs augmented with metrics[C]//Proceeding AI'02:Proceedings of the 15th Australian Joint Conference on Artificial Intelligence:Advances in Arti-ficial Intelligence. London:Springer-Verlag,2002:443-454.