半環(huán)誘導(dǎo)賦值代數(shù)的輪廓解

許格妮, 李永明, 張 云

(1.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安 710062; 2.西安財(cái)經(jīng)學(xué)院 統(tǒng)計(jì)學(xué)院, 西安 710100)

半環(huán)誘導(dǎo)賦值代數(shù)的輪廓解

許格妮1,2, 李永明1, 張 云2

(1.陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安 710062; 2.西安財(cái)經(jīng)學(xué)院 統(tǒng)計(jì)學(xué)院, 西安 710100)

先對(duì)全序半環(huán)誘導(dǎo)的賦值代數(shù)的輪廓解性質(zhì)進(jìn)行研究, 再在全序半環(huán)誘導(dǎo)的賦值代數(shù)中引入保輪廓解的概念, 并借助輪廓解的性質(zhì), 對(duì)轉(zhuǎn)移函數(shù)f保全序半環(huán)誘導(dǎo)的賦值代數(shù)的輪廓解問題進(jìn)行研究.結(jié)果表明, 若轉(zhuǎn)移函數(shù)f是一個(gè)半環(huán)同態(tài), 則f是保輪廓解的.

賦值代數(shù); 半環(huán); 輪廓解; 轉(zhuǎn)移函數(shù)

0 引 言

賦值代數(shù)是從人工智能領(lǐng)域中包括約束系統(tǒng)、信任函數(shù)系統(tǒng)、數(shù)據(jù)庫理論等抽象出來的用于描述信息處理方式的一種特殊代數(shù)結(jié)構(gòu)模型, Kohlas[1]對(duì)其進(jìn)行了明確、完整的表達(dá).在一個(gè)賦值代數(shù)系統(tǒng)中, 系統(tǒng)通過對(duì)變量的賦值表達(dá)知識(shí)和信息, 并通過聯(lián)合運(yùn)算對(duì)信息進(jìn)行合成, 通過投影運(yùn)算得到在指定變量集上的相關(guān)信息, 從而完成信息的提取.賦值代數(shù)是非確定情形下知識(shí)表示和推理的重要工具.

局部計(jì)算是賦值代數(shù)的一個(gè)核心內(nèi)容, 目前已有很多研究結(jié)果[2-6].在半環(huán)所誘導(dǎo)的賦值代數(shù)中, 投影運(yùn)算可轉(zhuǎn)化為求和運(yùn)算.特別地, 在全序半環(huán)誘導(dǎo)的賦值代數(shù)中, 求和運(yùn)算即為求最大值運(yùn)算.因此, 對(duì)于全序半環(huán)賦值φ∈Φ, 當(dāng)投影到空集時(shí), 滿足等式φ(x)=φ↓?(◇)的x即為使得φ取最大值的輪廓,φ↓?(◇)即為該賦值的最大值.基于此, 文獻(xiàn)[3]在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中提出了輪廓解的概念, 并給出了尋求輪廓解的一種算法; 文獻(xiàn)[7-8]對(duì)輪廓解的性質(zhì)進(jìn)行了初步探討.本文在此基礎(chǔ)上對(duì)輪廓解的一些性質(zhì)及其與擴(kuò)展解之間的關(guān)系進(jìn)行進(jìn)一步研究, 并對(duì)輪廓解的求法提出一種新思想： 當(dāng)直接尋求一個(gè)賦值的輪廓解存在困難時(shí), 可以將其轉(zhuǎn)移到新系統(tǒng)的一個(gè)賦值上, 通過求解新賦值的輪廓解獲得原問題的信息, 從而給出了在全序半環(huán)誘導(dǎo)的賦值代數(shù)中轉(zhuǎn)移函數(shù)保輪廓解的判別方法.

1 預(yù)備知識(shí)

一般可通過對(duì)變量賦值傳達(dá)知識(shí)或信息, 本文將該賦值用φ,ψ…表示, 用Φ,Ψ…表示由這些賦值構(gòu)成的集合.

定義1[1]設(shè)(Φ,D)是一個(gè)具有如下3種運(yùn)算的二元組, 其中(D,∨,∧)是一個(gè)格：

1) 論域運(yùn)算：Φ→D;φ→d(φ);

2) 聯(lián)合運(yùn)算：Φ×Φ→Φ; (φ,ψ)→φ?ψ;

3) 投影運(yùn)算：Φ×D→Φ; (φ,T)→φ↓T.

若系統(tǒng)(Φ,D)滿足如下公理, 則稱其為一個(gè)帶標(biāo)記的賦值代數(shù)：

1) 半群律：Φ關(guān)于聯(lián)合運(yùn)算滿足交換律與結(jié)合律, 且有單位元;

2) 論域律： 若?φ,ψ∈Φ, 則有d(φ?ψ)=d(φ)∨d(ψ);

3) 邊緣化律： ?φ∈Φ,T∈D, 若T≤d(φ), 則有d(φ↓T)=T;

4) 傳遞律： 若?φ∈Φ,T≤S≤d(φ), 則(φ↓S)↓T=φ↓T;

5) 聯(lián)合律： ?φ,ψ∈Φ, 若d(φ)=S,d(ψ)=T, 則有(φ?ψ)↓S=φ?ψ↓S∧T;

6) 單位元律： ?S,T∈D, 有eS?eT=eS∨T.

例1設(shè)A是一組屬性集, 對(duì)任意一個(gè)屬性α∈A, 用非空集Uα表示α可能的取值.設(shè)x∈A, 若?α∈x, 有f(α)∈Uα, 則稱定義域?yàn)閤的函數(shù)f是一個(gè)x元組.符號(hào)Ex表示所有x元組構(gòu)成的集合.若R?Ex, 則稱R為x上的一個(gè)關(guān)系,x稱為這個(gè)關(guān)系的域, 記d(R)=x.

1) 對(duì)于x,y上的兩個(gè)關(guān)系R,S, 它們的聯(lián)合定義域是x∪y上的關(guān)系, 滿足：

R??S={f:f∈Ex∪y,f[x]∈R,f[y]∈S},

其中f[x]表示x元組f在x上的投影.

2) 對(duì)于x上的一個(gè)關(guān)系R, 若y?x, 則定義關(guān)系R在y上的投影為πy(R)={f[y]:f∈R}.

給定一個(gè)屬性集A, 記R為由該屬性集子集上所有關(guān)系構(gòu)成的集合, 則由文獻(xiàn)[1]知, 系統(tǒng)(R,A)在上述定義的標(biāo)記運(yùn)算、聯(lián)合運(yùn)算及投影運(yùn)算下構(gòu)成一個(gè)賦值代數(shù).

定義2[2]設(shè)非空集合L上有兩個(gè)二元運(yùn)算+,×, 且元素0,1∈L, 若下列條件成立, 則稱(L,+,×,0,1)是一個(gè)半環(huán):

1) 加法和乘法均滿足交換律和結(jié)合律；

2) 乘法在加法上滿足分配律；

3) ?a∈L, 有a+0=a,a×0=0, 0稱為L的零元；

4) ?a∈L, 有a×1=a, 1稱為單位元.

在半環(huán)L上定義關(guān)系：a≤b?a+b=b, 由文獻(xiàn)[2]知, 若在L上定義的該序關(guān)系是全序, 則?a,a′,b,b′∈L, 有:

1)a+b=max{a,b};

2) 若a≤b,a′≤b′, 則a+a′≤b+b′,a×a′≤b×b′.

令D=P(r), 在(Φ,D)上定義如下運(yùn)算：

1) 聯(lián)合運(yùn)算： ?φ∈ΦS,ψ∈ΦT及x∈ΩS∪T, 定義φ?ψ(x)=φ(x↓S)ψ(x↓T);

文獻(xiàn)[2]已證明： 該系統(tǒng)在上述運(yùn)算下構(gòu)成一個(gè)賦值代數(shù), 稱其為由半環(huán)L誘導(dǎo)的賦值代數(shù).

2 半環(huán)誘導(dǎo)賦值代數(shù)輪廓解的性質(zhì)

在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中,φ↓?(◇)=max{φ(x):x∈Ωd(φ)}, 則滿足φ(x)=φ↓?(◇)的x即為φ取最大值的輪廓, 而對(duì)應(yīng)的φ(x)即為φ的最大值.為考察一個(gè)賦值φ對(duì)應(yīng)的這樣解的情況, 文獻(xiàn)[3]在全序半環(huán)所誘導(dǎo)的賦值代數(shù)中引入了輪廓解與擴(kuò)展解的概念, 并對(duì)其性質(zhì)進(jìn)行了研究.本文在這些工作的基礎(chǔ)上對(duì)全序半環(huán)所誘導(dǎo)賦值代數(shù)輪廓解的性質(zhì)及其與擴(kuò)展解的關(guān)系進(jìn)行進(jìn)一步研究.

定義3[3]設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 對(duì)于φ∈ΦS, 如果x∈ΩS滿足φ↓?(◇)=φ(x), 則稱x為φ的一個(gè)輪廓解,φ的全體輪廓解之集記為Cφ.

例2設(shè)L=({0,1,a,b},∨,∧,0,1)是四元鏈格, 其中0

φ:ΩS→L, (0,0)→1, (0,1)→1, (1,0)→a, (1,1)→b,

則Cφ={(0,0),(0,1)}.

注1特別地, 若S∩T=?時(shí), 則有(x1,x2)∈Cφ?ψ.

定理1的逆命題未必成立, 如：

推論1設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 取φ∈Φ且φ=φ1?φ2?…?φn, 其中d(φi)=Si,i=1,2,…,n, 且當(dāng)i≠j時(shí),Si∩Sj=?.如果xi∈Cφi, 則(x1,x2,…,xn)∈Cφ.

注2上述結(jié)論表明： 若φ=φ1?φ2?…?φn, 通過尋求賦值φi的輪廓解并不能完全得到φ的輪廓解, 但提供了尋求賦值輪廓解的一種方法.

即c∈Cφ↓S-T.

定理2的逆命題未必成立, 如：

定理3[4]設(shè)(Φ,D)是由全序半環(huán)所誘導(dǎo)的賦值代數(shù), 若d(φ)=S,d(ψ)=T, 且S∩T?U?S∪T, 則有(φ?ψ)↓U=φ↓S∩U?ψ↓T∩U.

φ(x↓U∩S,c1)×ψ(x↓U∩T,c2)=φ↓U∩S(x↓U∩S)×ψ↓U∩T(x↓U∩S),

因此有

3 半環(huán)誘導(dǎo)賦值代數(shù)的保輪廓解

定義5設(shè)f:L→L′是兩個(gè)全序半環(huán)間的一個(gè)映射, (Φ,D)與(Ψ,D)分別為半環(huán)L,L′誘導(dǎo)所得的賦值代數(shù), 對(duì)于Φ中的任一賦值φ:Ωs→L, 有復(fù)合映射fφ:Ωs→L′, 顯然fφ∈Ψ.因此, 稱映射f為Φ的轉(zhuǎn)移映射.

定義6設(shè)f:L→L′是兩個(gè)全序半環(huán)間的一個(gè)映射, (Φ,D)是由半環(huán)L誘導(dǎo)的賦值代數(shù), 如果f滿足?φ∈Φ, 有Cφ?Cfφ, 則稱f是保輪廓解的.

定義7[5]設(shè)f是兩個(gè)半環(huán)(L,+,×,0,1)與(L′,+,×,0,1)間的一個(gè)映射, 若f滿足:

1)f(0)=0,f(1)=1;

2)f(a+b)=f(a)+f(b);

3)f(a×b)=f(a)×f(b).

則稱f是一個(gè)半環(huán)同態(tài).

引理1設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個(gè)全序半環(huán)L,L′間的一個(gè)映射, 即f:L→L′, 且有f(0)=0,f(1)=1, 若對(duì)任意的正整數(shù)m,n, 有

則f是一個(gè)半環(huán)同態(tài), 其中?uij,vij∈L,i=1,2,…,n;j=1,2,…,m.

證明: 若式(1)成立, 則f是單調(diào)的.事實(shí)上, 在式(1)中, 令m=n=1即可得.

下證?a,b∈L, 有f(a)+f(b)=f(a+b).由f單調(diào)可得,f(a)+f(b)≤f(a+b).假設(shè)f(a)+f(b)

再證f(ab)=f(a)(b).假設(shè)f(ab)≠f(a)f(b), 則有f(a)f(b)

綜上可知,f是一個(gè)半環(huán)同態(tài).

定理5設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個(gè)全序半環(huán)L,L′間的一個(gè)映射, 且有f(0)=0,f(1)=1, 若式(1)成立, 則f是保輪廓解的.

由引理1知,f是一個(gè)半環(huán)同態(tài), 因此有

因此有

定理5給出了轉(zhuǎn)移函數(shù)f保輪廓解的一個(gè)判別條件, 但有時(shí)驗(yàn)證式(1)是否成立較麻煩, 下面給出定理5的另一種表示形式.

引理2設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個(gè)全序半環(huán)S,S′間的一個(gè)映射, 即f:L→L′, 且有f(0)=0,f(1)=1, 則f是一個(gè)半環(huán)同態(tài)當(dāng)且僅當(dāng)式(1)成立.

證明: 由引理1知, 僅證必要性即可.若f是一個(gè)半環(huán)同態(tài), 則f是單調(diào)的.事實(shí)上, ?a,b∈S, 若a≤b, 則有f(a)+f(b)=f(a+b)=f(b), 因此f(a)≤f(b).

由f是一個(gè)半環(huán)同態(tài)可得

因此, 式(1)成立.

綜上, 可得：

定理6設(shè)(Φ,D)是由全序半環(huán)L所誘導(dǎo)的賦值代數(shù),f是兩個(gè)全序半環(huán)L,L′間的一個(gè)映射, 且有f(0)=0,f(1)=1, 若f是一個(gè)半環(huán)同態(tài), 則f保輪廓解.

當(dāng)直接尋求某個(gè)賦值φ的輪廓解存在困難時(shí), 可借助定理6, 通過一個(gè)半環(huán)同態(tài)映射f將其轉(zhuǎn)移到一個(gè)結(jié)構(gòu)較簡單的、新的賦值代數(shù)系統(tǒng)中, 通過給出fφ的輪廓解解決原問題.

例5近期某類動(dòng)物有一種疾病, 醫(yī)務(wù)專家對(duì)此不能確診, 但憑借多年醫(yī)學(xué)經(jīng)驗(yàn)一致認(rèn)為服用三唑核苷、氧氟沙星、阿奇霉素或胸腺素這4種藥有助于該疾病的好轉(zhuǎn).多名醫(yī)務(wù)專家對(duì)該類動(dòng)物按不同組合服用這幾種藥物給出評(píng)價(jià), 結(jié)果列于表1, 其中:x1,x2,x3,x4依次表示上述4種藥物, 若服用藥物xi, 則取xi=1, 否則取xi=0(i=1,2,3,4);φ表示是否服用各藥物與醫(yī)務(wù)專家給出分值之間的對(duì)應(yīng)關(guān)系.求最佳服用方案.

表1 藥物服用情況分值結(jié)果Table 1 Score results about taking medicine

上述問題求最佳方案實(shí)際上是找φ的輪廓解, 為了找出φ的輪廓解, 需要在所有φ(x1,x2,x3,x4)中搜索出使φ取最大值的輪廓.當(dāng)φ取值較多時(shí), 用逐一搜索法找出其輪廓解顯然較麻煩, 但借助定理6可縮小搜索范圍, 從而減少了運(yùn)算量.

假設(shè)L1={[0,100],∨,∧,0,100}, 則上述φ可視為由全序半環(huán)L1所誘導(dǎo)的賦值代數(shù)(Φ,D)中的一個(gè)賦值, 其中Φ={f:ΩT→L1},T={x1,x2,x3,x4},D=P({x1,x2,x3,x4})是{x1,x2,x3,x4}的冪集.令L2={{0,a,b,1},∨,∧,0,1}, 其中0

表2 復(fù)合映射fφTable 2 Composite mapping fφ

由表2知Cα·φ={(0110),(1100),(0111)}, 則由定理6, 只需在Cα·φ中搜尋φ的輪廓解即可：φ(0110)=90,φ(1100)=90,φ(0111)=95, 因此Cφ={0111}, 即服用氧氟沙星、阿奇霉素和胸腺素為最佳方案.

[1]Kohlas J.Information Algebras: Generic Structures for Inference [M].London: Springer-Verlag, 2003.

[2]Kohlas J, Wilson N.Semiring Induced Valuation Algebras: Exact and Approximate Local Computation Algorithms [J].Artif Intell, 2008, 172(11): 1360-1399.

[3]Pouly M.A Generic Framework for Local Computation [D].Fribourg, Switzerland: University of Fribourg, 2008.

[4]韓邦合.賦值代數(shù)分裂算法與隱性半環(huán)賦值研究 [D].西安： 陜西師范大學(xué), 2011.(HAN Banghe.The Splitting Algorithm of Valuation Algebra and Implicit Valuation over a Semiring [D].Xi’an: Shaanxi Normal University, 2011.)

[5]LI Sanjiang, YING Mingsheng.Soft Constraint Abstraction Based on Semiring Homomorphism [J].Theoretical Computer Science, 2008, 403(2/3): 192-201.

[6]GUAN Xuechong, LI Yongming.On a Condition for Semirings to Induce Compact Information Algebras [J].Electronic Notes in Theoretical Computer Science, 2014, 301: 39-48.

[7]Kohlas J.Lecture Notes on the Algebraic Theory of Information [R/OL].2010-11-24.http://diuf.unifr.ch/drupal/tns/sites/diuf.unifr.ch.drupal.tns/files/file/kohlas/main.pdf.

[8]管雪沖.賦值代數(shù)中若干問題的研究 [D].西安: 陜西師范大學(xué), 2011.(GUAN Xuechong.The Study of Some Questions about Valuation Algebra [D].Xi’an: Shaanxi Normal University, 2011.)

SolutionConfigurationofSemiringValuationAlgebra

XU Geni1,2, LI Yongming1, ZHANG Yun2
(1.CollegeofMathematicsandInformationScience,ShaanxiNormalUniversity,Xi’an710062,China;
2.CollegeofStatistics,Xi’anUniversityofFinanceandEconomics,Xi’an710100,China)

The properties of the solution configuration of valuation algebra over a totally ordered semiring were discussed.Furthermore, the concept of preserving the solution configuration of valuation algebra over a totally ordered semiring was given.With the help of the properties of the solution configuration, the question of the transfer functionfpreserving solution configuration was studied.It is concluded that the transfer functionfpreserves solution configuration iffis a semiring homomorphism.

valuation algebra; semiring; solution configuration; transfer function

2014-03-12.

許格妮(1978—), 女, 漢族, 博士研究生, 講師, 從事計(jì)算智能、信息代數(shù)與不確定推理的研究, E-mail: geniwork@163.com.通信作者： 李永明(1966—), 男, 漢族, 博士, 教授, 博士生導(dǎo)師, 從事計(jì)算智能、量子邏輯和量子計(jì)算的研究, E-mail: liyongm@snnu.edu.cn.

國家自然科學(xué)基金(批準(zhǔn)號(hào): 11271237; 61228305)和西安財(cái)經(jīng)學(xué)院科研基金(批準(zhǔn)號(hào): 12JD04).

O141

A

1671-5489(2014)06-1119-06

10.13413/j.cnki.jdxblxb.2014.06.03

趙立芹)