亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        n-元圈圖模型迭代比例擬合算法中的最優(yōu)分劃

        2015-06-12 12:03:36孫聚波徐平峰
        關(guān)鍵詞:分劃高維復(fù)雜度

        孫聚波, 徐平峰

        (長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院,吉林 長春 130012)

        0 引 言

        近年來,針對分類數(shù)據(jù)的特殊統(tǒng)計方法的應(yīng)用日益廣泛,這個現(xiàn)象一定程度上反映了過去幾十年分類數(shù)據(jù)分析方法的發(fā)展。其中,用列聯(lián)表對分類數(shù)據(jù)進行統(tǒng)計分析是一種常用、直觀的方法[1]。

        一般來說,觀測數(shù)據(jù)按兩個或多個屬性分類時所列出的頻數(shù)表即為列聯(lián)表。文中令V表示由分類變量構(gòu)成的集合。對任意的分類變量γ∈V,Xγ表示γ對應(yīng)的有限的水平集。表中的一個格子表示集合XV中的一個點x=(xγ)γ∈V,這里XV=×γ∈VXγ。假設(shè)把n次觀測數(shù)據(jù)按V進行分類,令計數(shù)

        n(x)=落入格子x的觀測頻數(shù)

        p(x)=一個個體落入格子x的概率

        在高維列聯(lián)表中,飽和模型的參數(shù)個數(shù)一般大于樣本個數(shù),不僅統(tǒng)計上無法處理,計算上也不可行。但事實上,很多高維數(shù)據(jù)都具有某種特殊結(jié)構(gòu),并且結(jié)構(gòu)是稀疏的,通??梢杂脠D模型表示。

        1 圖模型及極大似然估計

        1.1 圖模型

        圖模型是圖論、概率論、統(tǒng)計學(xué)等學(xué)科的交叉領(lǐng)域[2-3]。在圖模型中,隨機變量由圖的頂點表示,隨機變量之間有直接關(guān)聯(lián),對應(yīng)的頂點間用邊相連,這樣構(gòu)成一個圖G(V,E),這里V表示頂點集,E表示邊集。相對于圖G滿足馬爾科夫性的概率分布族,即為圖模型,記作P(G)。如此建立的圖模型清晰地表示了條件獨立關(guān)系,從而建立圖與概率分布的對應(yīng)關(guān)系,利用圖的語言表示概率統(tǒng)計相關(guān)問題,并依據(jù)圖論的理論和算法幫助進行概率統(tǒng)計推斷,降低推斷的復(fù)雜度。目前,圖模型被廣泛地應(yīng)用于生物信息學(xué)、統(tǒng)計物理、圖像處理、信息檢索、機器學(xué)習(xí)等各個領(lǐng)域[4]。

        在圖G中,子集c?V,如果c中任意兩個頂點都是相鄰的,則稱子集c是完全的。如果一個完全子集是最大的(相對于包含運算而言),則稱它為一個團。我們用K(G)表示一個圖的所有團構(gòu)成的集合。

        1.2 極大似然估計的IPS算法

        利用圖模型分析高維數(shù)據(jù),求解參數(shù)的極大似然估計是一個非常重要的方面。設(shè)x1,x2,…,xn為來自多項圖模型P(G)的獨立同分布樣本,對于每個x∈XV,x被觀測到的次數(shù)為n(x)。對于團c∈K(G),xc∈Xc=×γ∈cXγ的觀測數(shù)為。于是,似然函數(shù)為

        似然方程為

        對所有的xc∈Xc,c∈K(G)。

        為求解上述似然方程,Deming[5]等給出了迭代比例擬合(IPS)算法,他們先引入一個邊緣調(diào)整算子Ac,對于任意p(xV),任意c∈K(G),令

        其中j=(tmodk)+1。取p(0)∈P(G),則概率p的極大似然估計為

        收斂性的證明見文獻[3]。

        1.3 基于團分劃改進的IPS算法(IPSP算法)

        在圖模型中,IPS算法的復(fù)雜度隨變量個數(shù)的增加呈指數(shù)型增加,求解似然方程的速度變得非常慢。過去十幾年,諸多學(xué)者做了大量工作以降低IPS算法的復(fù)雜度[6-10]。對于多項圖模型,文獻[10]利用團分劃的策略實現(xiàn)局部計算和共享計算,從而改進了IPS算法,給出了基于團分劃改進的IPS算法,即IPSP算法。它先找K(G)的一個分劃W={K1,K2,…,Km},使得K(G)=,且對;對i=1,2,…,m,令Ui=∪c∈Kic,計算,對c∈Ki,進行局部調(diào)整pUi=AcpUi;利用調(diào)整后的邊緣分布pUi恢復(fù)聯(lián)合分布p(xV),詳見文獻[10]。

        在IPSP算法中,給定分劃W,將所有的團都調(diào)整一次,共需加法次;需乘法次;需除法次。其中算法的復(fù)雜程度主要體現(xiàn)在乘法上,常用乘法次數(shù)來度量算法的復(fù)雜度。

        2 n-元圈圖模型的最優(yōu)分劃

        在IPSP算法中,分劃策略影響算法的復(fù)雜度。如何選擇最優(yōu)分劃是一個組合優(yōu)化問題,對于一般的圖模型問題比較復(fù)雜,可采用模擬退火等方法進行求解。下面對于具有特殊結(jié)構(gòu)的n-元圈圖模型給出了最優(yōu)分劃策略,如圖1所示。

        圖1 n-元圈圖模型

        在上面的n-元圈圖G=(V,E)中,頂點集V={1,2,…,n},邊 集E={(1,2),(2,3),…,(n-1,n),(n,1)},每個頂點表示隨機變量Xi,Xi為離散的,且所有Xi的取值個數(shù)相同。其中,團為:ci={i,i+1},i=1,2,…,n-1,cn={n,1},團集K(G)={ci|i=1,2,…,n}。團集的分劃為:W={K1,K2,…,Km},使得,且對i。分劃W的復(fù)雜度函數(shù)為:

        定理1 令W為連續(xù)分劃,|Ki|=ki,n≥6,隨機變量Xi取值個數(shù)皆為定數(shù)a(a≥2),對應(yīng)的復(fù)雜度函數(shù)為:

        證明 由Jensen不等式,有

        我們構(gòu)造函數(shù):

        m≥3時,若下面不等式組成立

        則m≥3時,f關(guān)于m單調(diào)增。下述即證明m≥3時,該不等式組成立。

        我們構(gòu)造函數(shù):

        n為偶數(shù)時,連續(xù)二等分劃復(fù)雜度為:

        解不等式

        整理得:

        易求得對任意n≥6,a≥2,都有上式成立,則對任意分劃W都有

        g(W)≥f(a,n,3)≥n·an/2+1+2·an

        n為奇數(shù)時,連續(xù)二等分劃復(fù)雜度為:

        解不等式

        整理得

        構(gòu)造函數(shù)

        解不等式組

        將t(2,n)≥0整理為:

        求得n≥7,滿足該不等式。

        成立。

        綜上,無論n為偶數(shù)還是奇數(shù),對任意n≥6,a≥2,任意連續(xù)分劃中二等連續(xù)分劃最優(yōu)。

        3 結(jié) 語

        給出并證明了隨機變量的取值個數(shù)相等時,n-元圈圖模型中IPSP算法的最優(yōu)分劃為連續(xù)二等分劃。那么若隨機變量的取值不一定相同時,其最優(yōu)分劃是否仍為連續(xù)二等分劃,對于結(jié)構(gòu)一般的圖模型,IPSP算法的最優(yōu)分劃是否也為連續(xù)二等分劃呢,這都是尚未解決的問題。作者旨在拋磚引玉,以待更多人關(guān)注和研究。

        [1] Agresti A.屬性數(shù)據(jù)分析引論[M].張淑梅,王睿,曾莉,譯.2版.北京:高等教育出版社,2008.

        [2] 王曉飛.圖模型的結(jié)構(gòu)、分解和可壓縮性[D].長春:東北師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,2010.

        [3] Lauritzen S L.Lectures on Contingency Tables[EB/OL].(2002-05-28)[2015-03-20].http://www.stats.ox.ac.uk/~steffen/papers/cont.pdf.

        [4] Wainwright M J,Jordan M I.Graphical models,exponential families,and variational inference[J].Foundations and Trends in Machine Learning,2008,1(1/2):1-305.

        [5] Deming W E,Stephan F F.On a least squares adjustment of a sampled frequency table when the expected marginal totals are known[J].The Annals of Mathematical Statistics,1940,11(4):427-444.

        [6] Jirousek R,Preucil S.On the effective implementation of the iterative proportional fitting procedure[J].Computational Statistics and Data Analysis,1995,19(2):177-189.

        [7] Badsberg J H,Malvestuto F M.An implementation of the iterative proportional fitting procedure by propagation trees[J].Computational Statistics and Data Analysis,2001,37(3):297-322.

        [8] Teh Y W,Welling M.On Improving the efficiency of the Iterative proportional fitting procedure[J].In Proceedings of the Ninth International Conference on Artificial Intelligence and Statistics,Key West,F(xiàn)L,2003,34(6):231-240.

        [9] Xu P F,Guo J H,Tang M L.A localized implementation of the iterative proportional scaling procedure for Gaussian graphical models[J].Journal of Computational and Graphical Statistics,2015,24(1):205-229.

        [10] Xu P F,Sun J,Shan N.Local computations of the iterative proportional scaling procedure for hierarchical models[J].Submitted to Computational Statistics Data Analysis,2015,16(2):195-199.

        猜你喜歡
        分劃高維復(fù)雜度
        R1上莫朗測度關(guān)于幾何平均誤差的最優(yōu)Vornoi分劃
        一種低復(fù)雜度的慣性/GNSS矢量深組合方法
        一種改進的GP-CLIQUE自適應(yīng)高維子空間聚類算法
        基于加權(quán)自學(xué)習(xí)散列的高維數(shù)據(jù)最近鄰查詢算法
        求圖上廣探樹的時間復(fù)雜度
        巧用分劃板測望遠鏡的放大率
        某雷達導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進
        非絕對型Henstock 積分與Riemann-Stieltjes 積分之關(guān)系
        一般非齊次非線性擴散方程的等價變換和高維不變子空間
        出口技術(shù)復(fù)雜度研究回顧與評述
        国产麻豆精品一区二区三区v视界| 日本免费三片在线播放| 91久久国产香蕉熟女线看 | 91久久精品一二三区色| 日韩精品一区二区在线天天狠天| 欧美人与动牲交a精品| 99国产超薄丝袜足j在线观看| 久久99热精品免费观看麻豆| 穿着白丝啪啪的av网站| 欧洲熟妇色 欧美| 99热最新在线观看| 久久综合这里只有精品| av在线观看一区二区三区| 丰满人妻熟妇乱又伦精品软件| 男女一级毛片免费视频看| av免费在线观看网站大全| 中文字幕av久久亚洲精品| 无码人妻一区二区三区在线视频| chinese国产在线视频| 最新日本久久中文字幕| 无码人妻久久一区二区三区蜜桃| 初尝黑人巨砲波多野结衣| 久久久99久久久国产自输拍| 美女视频在线观看网址大全| а天堂中文最新一区二区三区| 国内精品大秀视频日韩精品| 黑人一区二区三区高清视频| 亚洲综合精品中文字幕| 中文国产日韩欧美二视频| 阿v视频在线| 亚州中文热码在线视频| 国产伦精品一区二区三区妓女| 亚洲欧美日韩激情在线观看| 亚洲高清av一区二区| 老太婆性杂交视频| 国产成人av 综合 亚洲| 国产成人精品人人做人人爽| 亚洲一区二区三区99| 国产精品综合一区二区三区| 亚洲VA欧美VA国产VA综合| 精品人妻av一区二区三区四区|