AP算法存在的固有缺陷是它不能對包含很多子類的category進行建模，而在image categorization, face categorization, 多字體optical character recognition，手寫數(shù)字分類，每個category可能包含很多子類。
比如說，在自然場景類別可能包含很多主題，比如說，街景中可能包含一些主題，比如road，car，pedestrian，building等等。

在OCR和手寫數(shù)字分類問題中，代表letter或digit的類可能由多個子類組成，每個子類代表著不同的style或者字體。顯然，我們用一個代表點來統(tǒng)一表示這些子類是不合理的。
這篇論文提出了MEAP算法。每一個cluster都是自動決定exemplars和superexemplars的數(shù)目，每個數(shù)據點都自動分配給最接近的exemplar,而每個exemplar都分配給最接近的superexemplar。
superexemplar定義為代表一類cluster的所有exemplars中的最具代表性的那一個。

所以目標函數(shù)是 最大化數(shù)據點和代表點(exemplar)之間的相似度，以及exemplar和superexemplar之間的相似度。
直接求解這個問題是NP困難的。所以我們可以使用max-sum belief propagation，可以產生對初始化信息不敏感的算法。

AP算法復習

在之前的博客中已經有過具體的介紹，為了數(shù)學符號表示的一致性，這里用新的數(shù)學表達式再表示一次。

給定一個用戶定義的N個數(shù)據點的相似矩陣[sij]N×N，我們的目標是獲得一個labels的valid configurationc=[c1,c2,...,cN]，來優(yōu)化目標函數(shù)：

S(c)=∑i=1Nsici+∑k=1Nδk(c)
而 δk(c)是一個exemplar-consistency約束，就是說如果有數(shù)據點i選擇k作為代表點，也就是滿足 ci=k,那么k必須同時也是自己的代表點，也就是 ck=k
δk(c)={?∞,if?ck≠k?but???i:ci=k0,?otherwise

更新迭代的過程可以濃縮到下面幾行：

最后的類別向量c=[c1,...,cN]的計算方法為：

ci=arg?maxj[a(i,j)+r(i,j)]

MEAP

假設[sij]N×N是一個用戶定義的相似度矩陣，sij代表著數(shù)據點i和代表點j之間的相似度，[lij]N×N代表著代表點i和潛在的super-exemplar j之間的相似度。
我們的目標是最大化所有數(shù)據點和它們對應的代表點之間的相似度S1，同時最大化代表點和superexemplar之間的相似度S2。

模型

假設C是assignment 矩陣，非對角線元素代表數(shù)據點j是數(shù)據點i的代表點cij=1,也就是ψ1(i)=j, 對角線元素代表 cii∈{1,...,N} 代表著cii是代表點i的superexemplar。

S1=∑i=1N∑j=1Nsij?[cij≠0],S2=∑i=1Nlicii?[cii≠0]

其中[?]是Iverson notation，當true時，取值為1。

我們可以得到S1+S2=∑Ni=1∑Nj=1Sij(cij)。同時必須滿足下面3個約束:
1) 每個數(shù)據點i必須只能分配給一個代表點

2) 代表點一致性約束
如果數(shù)據點i選擇了數(shù)據點j作為代表點，那么數(shù)據點j本身必須是代表點。

3) superexemplar一致性約束
如果數(shù)據點i選擇了數(shù)據點k作為superexemplar, 那么k必須同時選擇自己作為superexemplar。

所以MEAP的目標是最大化下面的目標函數(shù)：

上圖描述的是一個多層的結構，S1評估的是within-subcluster 的compactness，高層的ψ2描述的是exemplar 和superexemplar之間的關系。
根據single-exemplar的理論，最大化within-cluster 相似度會自動最大化between-cluster separation.
從最大化margin clustering的角度，MEAP比AP要好，見下圖：

優(yōu)化

MEAP的因子圖如下圖：

多代表點的模型是單代表點的模型的普及，對其進行優(yōu)化是NP-hard的。因此，我們使用max-sum belief propagation，這是一個local-message-passing 算法，它會收斂到局部最大值。
（可以發(fā)現(xiàn)對角線的變量多連接了F的函數(shù)），也就是 superexemplar的一致性約束。

上圖中圓形表示的變量節(jié)點，方形表示的是函數(shù)節(jié)點。
從變量到函數(shù)，將與這個變量連接的函數(shù)的信息求和（除了接收信息的函數(shù)以外）。

從函數(shù)到變量，包括除該變量外所有函數(shù)變量的maximization。

其中X=ne(f)是函數(shù)f的參數(shù)集。（或者我們可以理解成與該函數(shù)節(jié)點連接的所有變量節(jié)點）
這里我們可以發(fā)現(xiàn)對角線和非對角線的變量節(jié)點很不同，所以我們對它們分開進行討論。

非對角線元素的Messages

左圖有5種messages，與cij連接，i≠j，如左下圖：

非對角線元素

對角線元素

求解過程

非對角線變量

對于非對角線結點，m=cij

我們來討論cjj，將這一項單獨寫出來,它的取值可以是１也可以是０
第一種情況:
如果是１，也就是m=1, 如果數(shù)據點i選擇j作為代表點，那么j必須是一個代表點，這時Ej(c1j,...,cij) 為0，而別的數(shù)據點i′可以選擇ｊ作為代表點也可以不選，也就是ci′j的值不定。
第二種情況:
m=0,也就是說ｉ沒有選ｊ作為代表點，我們再討論數(shù)據點ｊ的情況，如果數(shù)據點j本身是一個代表點，別的數(shù)據點i′要么選它作為數(shù)據點，要么不選，就如第一種情況的結論，但是如果ｊ本身不選自己，那么逆否命題成立我們可以推知，一定有cjj=0=>ci′j=0,　所以可以得到∑i′:i′≠iρi′j(0)

對于ηij,同樣是從函數(shù)結點到變量結點。

ηij(m)=μIi→cij(m)=maxcij′:j′≠j[Ii(ci1,...,ciN)+∑j′′:j′≠jβij′′(cij′′)]

第一種情況，cij=1,　由于唯一性約束，也就是它只能有一個代表點，那么β參數(shù)cij′必須是０。
第二種情況，如果是０，那么假設它的代表點是j′,再討論這個j′是不是ｉ本身，除去j′的代表點的所屬權都必須是０。
(我一開始有點疑惑，因為大前提已經是i≠j,后來我反應過來這只是對cij的討論，而公式中覆蓋的條件是全面的。)

對角線變量

對于對角線上的變量，如果它們本身是代表點，那么它們的取值為{1,...,N},　如果它們不是代表點，那么取值為０。

(1)
如果ｉ是代表點，也就是cii=m,m∈{1,...,N}那么別的數(shù)據點i′可以選擇它或者不選它。
此時Ei(c1i,...,cii=m,...,cNi)=0
(2)
如果ｉ本身不是代表點，那么ci′i=0

(1)
如果ｉ本身是一個代表點，也就是它選自己當代表點，所以它不能再選別人當代表點，由唯一性約束，那么別的cii′=0
(2)
如果ｉ不是代表點，假如它選了i’,那么它不能選別的數(shù)據點作為代表點，所以可得

maxi′:i′≠i[βii′(1)+∑i′′:i′′?{i,i′}βii′′(0)]

對于γ的討論比較復雜，
(1) 如果cii=k=i，也就是說一個代表點ｋ，選了自己作為自己的superexemplar.
(2) 如果cii≠k=i
可以推出ckk≠k, 也就是說數(shù)據點ｋ并沒有選自己作為superexemplar，那么別的數(shù)據點i′也不能選自己ｋ作為superexemplar。
(3) cii=k≠i
如果ｉ為代表點，選擇ｋ作為超級代表點(superexemplar)，同時k≠i，那么ｋ本身必須也是一個代表點同時選擇自己作為超級代表點,也就是ckk=k,而別的除了i和ｋ的數(shù)據點并沒有限制。
(4) cii≠k≠i
i沒有選擇ｋ作為超級代表點，我們可以對ｋ的情況進行討論，如果它本身不是超級代表點，也就是ckk≠k,
這一項單獨寫出來可以得到

如果ｋ本身是超級代表點，ckk=k,單獨寫出來是：

最后的結果是兩項的較大值。

Message summary與代碼解讀

S: similiarty matrix，n*n的矩陣
L: linkage matrix, n*n的矩陣
Rhoij : ρ~ij Rhoim: ρ~mi
Alphaij: α~ij (N*N) Alphai: α~ii(N*1)
Betaij : β~ij Betaim : β~mi
Etaij: η~ij(N*N) Etaii : η~ii(N*1)
Gammaik: γ~ik
Phiik : ?~ik

Rhoij=zeros(N,N); Rhoim=zeros(N,N); Alphaij=zeros(N,N); Alphai=zeros(N,1); Betaij=zeros(N,N); Betaim=zeros(N,N); Etaij=zeros(N,N); Etai=zeros(N,1); Gammaik=zeros(N,N); Phiik=zeros(N,N);

更新ρ

%% rhoOldRhoij=Rhoij;Rhoij=S+Etaij;Rhoij=(1-lambda)*Rhoij+lambda*OldRhoij; %rho_ijOldRhoim=Rhoim;Rhoim=repmat(diag(S)+Etai,[1,N])+L+Gammaik;Rhoim=(1-lambda)*Rhoim+lambda*OldRhoim;

更新α

OldAlphaij=Alphaij;OldAlphai=Alphai;Rp=max(Rhoij,0);for k=1:N, Rp(k,k)=max(Rhoim(k,:)); end;A=repmat(sum(Rp,1),[N,1])-Rp;dA=diag(A); Alphaij=min(A,0);for k=1:N, Alphai(k)=dA(k); end;Alphaij=(1-lambda)*Alphaij+lambda*OldAlphaij;Alphai=(1-lambda)*Alphai+lambda*OldAlphai;

更新β

Betaij=S+Alphaij;Betaim=repmat(diag(S)+Alphai,[1,N])+L+Gammaik;

更新η

B=Betaij; [Y,I]=max(B,[],2);
for i=1:N, B(i,I(i))=-inf; end;%最大值賦值為負無窮
[Y2,I2]=max(B,[],2);% Y2代表次大值
R=repmat(Y,[1,N]);

當j的位置剛好對應最大值時，由于j′≠j所以取次大值
這一步得到

for i=1:N,R(i,I(i))=Y2(i);R(i,i)=-inf; end;

接下來計算：

T=zeros(N,N);for i=1:N, T(i,:)=max(Betaim(i,:)); end;

接下來計算：

Etaij=-max(R,T);

接下來計算

T=Betaij;for i=1:N, T(i,i)=-inf; end;%除去i'不等于ｉ的情況Etai=-max(T,[],2);

更新γ

這一步計算

OldGammaik=Gammaik;RPhiik=max(Phiik,0); for k=1:N, RPhiik(k,k)=Phiik(k,k); end;Gammaik=repmat(sum(RPhiik,1),[N,1])-RPhiik;

對于對角線元素，通過上面的計算已經求出，也就是Gammaik的對角線,所不同的是對非對角線，還有一個min函數(shù)的截斷。所以先存儲對角線元素，隨后對矩陣進行min函數(shù)的截斷，再單獨賦值。

dGammaik=diag(Gammaik); Gammaik=min(Gammaik,0); for k=1:N, Gammaik(k,k)=dGammaik(k); end;Gammaik=(1-lambda)*Gammaik+lambda*OldGammaik;

更新?

計算

OldPhiik=Phiik;LG=L+Gammaik; [Y,I]=max(LG,[],2);for i=1:N, LG(i,I(i))=-inf; end; [Y2,I2]=max(LG,[],2);R=repmat(Y,[1,N]);for i=1:N, R(i,I(i))=Y2(i); end;

計算sii+α~ii+η~ii

SAE=repmat(diag(S)+Alphai+Etai,[1,N]);Phiik=L-max(R,-SAE);Phiik=(1-lambda)*Phiik+lambda*OldPhiik;

Assignment matrix

計算cij的所有輸入信息的和，隨后求解使得c^ij最大的值。

C=zeros(N,N);C(Alphaij+Rhoij>=0)=1;%非對角線[a,b]=max(Rhoim,[],2);for i=1:N, if a(i)+Alphai(i)>=0, C(i,i)=b(i); else C(i,i)=0; end; end;%對角線if isequal(OldC,C), stayiter=stayiter+1; else stayiter=1; OldC=C; end;if stayiter>convits% further check for validationexemplar_idx=zeros(N,1);validflag=1;for i=1:Na=find(C(i,:)~=0);if length(a)~=1, validflag=0; break; else exemplar_idx(i)=a(1); end; % points to exemplarsendif validflag==1a=find(diag(C)~=0);if length(a)<=1%只有一個代表點validflag=0;elsesuperexemplar_idx=zeros(length(a),2);superexemplar_idx(:,1)=a;superexemplar_idx(:,2)=diag(C(a,a));sa=unique(superexemplar_idx(:,2));if ~isequal(diag(C(sa,sa)),sa), validflag=0; end; % exemplars to super-exemplarsendendif validflag==0 % invalid results! continue iterating!stayiter=1; OldC=zeros(N,N);elsedisp(['iteration number ' num2str(iter)]);break;endend end

計算net similarity

T=diag(L);
netSim=sum(S(C~=0))+sum(T(diag(C)~=0));

總結

以上是生活随笔為你收集整理的Multi-Exemplar Affinity Propagation的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。