Outline
Main question today:給定一個(gè)部分節(jié)點(diǎn)有標(biāo)簽的網(wǎng)絡(luò)骨坑,如何為網(wǎng)絡(luò)中的剩余節(jié)點(diǎn)分配標(biāo)簽?
Collective classification:為網(wǎng)絡(luò)中所有節(jié)點(diǎn)分配標(biāo)簽的思想,直覺上是利用網(wǎng)絡(luò)中存在的關(guān)聯(lián)(Correlations)。本次課程將討論以下三類方法:
- Relation Classification
- Iterative Classification
- Belief Propagation
有三種類型的依賴將導(dǎo)致關(guān)聯(lián):
- Homophily(Individual Characteristics -> Social Connections): 個(gè)體與相似的其他個(gè)體交往和聯(lián)系的趨勢妆毕。這種相似性可以體現(xiàn)在年齡、性別贮尖、組織角色等多種屬性上笛粘。例如:喜歡相同音樂類型的人更可能建立社交聯(lián)系(在音樂會(huì)上見面,在音樂論壇上互動(dòng)等)
- Infuence (Social Connections -> Individual Characteristics): 社會(huì)關(guān)聯(lián)將影響到個(gè)人特性湿硝。
- Confounding (Environment -> Individual Characteristics; Environment -> Social Connections)
Classification with Network Data
Problem:給定一個(gè)圖和少數(shù)帶有標(biāo)簽的節(jié)點(diǎn)薪前,如何利用網(wǎng)絡(luò)中觀察到的關(guān)聯(lián)幫助預(yù)測其它節(jié)點(diǎn)的標(biāo)簽?
Motivation:相似的節(jié)點(diǎn)往往離得很近或直接相連关斜。
- Guilt-by-association:如果我與一個(gè)帶有標(biāo)簽X的節(jié)點(diǎn)相連示括,我的標(biāo)簽很有可能也是X。
- 網(wǎng)絡(luò)中對象O的類別標(biāo)簽可能取決于:O的特性蚤吹、O鄰居的標(biāo)簽例诀、O鄰居的特性。
Fomulation:令表示一個(gè)
個(gè)節(jié)點(diǎn)上的
的帶權(quán)鄰接矩陣裁着。令
表示標(biāo)簽向量繁涂,其中1表示正類節(jié)點(diǎn),-1表示負(fù)類節(jié)點(diǎn)二驰,0表示無標(biāo)簽節(jié)點(diǎn)扔罪。目標(biāo)是預(yù)測哪些無標(biāo)簽節(jié)點(diǎn)可能是正類的。
Collective Classification
Markov Assumption: 節(jié)點(diǎn)的標(biāo)簽
取決于其鄰居
的標(biāo)簽
Collective Classification涉及三個(gè)步驟:
- Local Classifier: (bootstrap step)分配初始標(biāo)簽桶雀。根據(jù)節(jié)點(diǎn)屬性或特性預(yù)測標(biāo)準(zhǔn)矿酵,這是一個(gè)標(biāo)準(zhǔn)的分類任務(wù)唬复,不涉及網(wǎng)絡(luò)信息。
- Relational Classifier: 捕捉節(jié)點(diǎn)之間的相關(guān)性全肮。學(xué)習(xí)一個(gè)基于鄰居標(biāo)簽屬性對各節(jié)點(diǎn)進(jìn)行分類的分類器敞咧,這里用到了網(wǎng)絡(luò)的信息。
- Collective Inference:通過網(wǎng)絡(luò)傳播相關(guān)性辜腺。將relational classification迭代的用于每個(gè)節(jié)點(diǎn)休建,直到相鄰標(biāo)簽之間的非一致性最小化。網(wǎng)絡(luò)的結(jié)構(gòu)將嚴(yán)重影響最終的預(yù)測結(jié)果评疗。
注意:如今所介紹的所有分類方法都是Approximate Inference测砂,Exact Inference對于任意網(wǎng)絡(luò)而言都是一個(gè)NP-hard問題,只有當(dāng)網(wǎng)絡(luò)滿足特定條件時(shí)百匆,才可以進(jìn)行Exact Inference砌些。此外接下來介紹的所有算法都是迭代算法。
Probabilistic Relational Classifier
Basic Idea:類別的可能性是其鄰居類別可能性的加權(quán)平均加匈。對于有標(biāo)簽節(jié)點(diǎn)存璃,使用groud-truth的
標(biāo)簽進(jìn)行初始化;對于無標(biāo)簽節(jié)點(diǎn)矩动,對
進(jìn)行統(tǒng)一初始化有巧。以任意順序更新節(jié)點(diǎn),直到收斂或達(dá)到最大次數(shù)悲没。
對每個(gè)節(jié)點(diǎn)和標(biāo)簽
重復(fù)進(jìn)行如下計(jì)算(其中
表示節(jié)點(diǎn)i的鄰居數(shù)篮迎,
表示從
到
的邊的權(quán)重):
該方法的困難在于無法保證收斂以及模型無法用到節(jié)點(diǎn)的特征信息。
Iterative classification
Main idea:克服Relational Classifier未使用節(jié)點(diǎn)屬性的缺點(diǎn)示姿,基于節(jié)點(diǎn)的屬性和鄰居節(jié)點(diǎn)
的標(biāo)簽對節(jié)點(diǎn)
進(jìn)行分類甜橱。為每個(gè)節(jié)點(diǎn)
創(chuàng)建一個(gè)平面向量
,然后使用
訓(xùn)練一個(gè)分類器栈戳;每個(gè)節(jié)點(diǎn)具有不同數(shù)量的鄰居岂傲,因此可以使用以下方法進(jìn)行匯總(aggregate):計(jì)數(shù)(有多少鄰居節(jié)點(diǎn)擁有某種特性)、模式子檀、比例镊掖、均值、存在等褂痰。
Basic architechture:
- Bootstrap phase:將每個(gè)節(jié)點(diǎn)
轉(zhuǎn)換為平面向量
亩进,使用local classifier
,如SVM缩歪、kNN計(jì)算
的最佳值归薛;
- Iteration phase:對每個(gè)節(jié)點(diǎn)
重復(fù)以下過程:根據(jù)迭代結(jié)果更新節(jié)點(diǎn)向量
,重新計(jì)算
,迭代該過程直到類標(biāo)簽穩(wěn)定或達(dá)到最大迭代次數(shù)主籍。
Belief Propagation
Belief Propagation是一種用于回答圖形模型中的條件概率查詢的動(dòng)態(tài)編程方法习贫,鄰居變量在其迭代過程中彼此傳遞信息,在達(dá)成共識(shí)后千元,將計(jì)算最終的belief苫昌。
Message Passing
Task: 計(jì)算圖中的節(jié)點(diǎn)數(shù)
Condition: 每一個(gè)節(jié)點(diǎn)只能與鄰居節(jié)點(diǎn)傳遞信息
Solution: 每一個(gè)節(jié)點(diǎn)接收其鄰居節(jié)點(diǎn)傳遞的信息,更新自己的信息然后繼續(xù)傳遞
注意:在一個(gè)有環(huán)圖中該過程無法正確運(yùn)作幸海。
Loopy BP algorithm
What message will i send to j蜡歹?取決于i從它的鄰居k接收到的信息,每一個(gè)鄰居將會(huì)傳遞給i對i狀態(tài)的belief信息涕烧。
Notion:
- Label-label potential matrix
: 節(jié)點(diǎn)和其鄰居之間的依賴關(guān)系。
等于給定節(jié)點(diǎn)
處于狀態(tài)
下的鄰居節(jié)點(diǎn)
汗洒,其狀態(tài)為
的可能性议纯。
- Prior belief
: 節(jié)點(diǎn)
處于狀態(tài)
下的概率
。
-
表示
對
處于狀態(tài)
的估計(jì)溢谤。
-
是所有的狀態(tài)集合瞻凤。
Process:
- 初始化所有的消息為1;
- 對每個(gè)結(jié)點(diǎn)重復(fù)如下操作:
- 收斂后世杀,令
表示
處于狀態(tài)
的belief阀参,其計(jì)算如下:
Advantages:
- 很容易進(jìn)行編程和并行計(jì)算
- 容易泛化到其它圖模型
Challenges:
不能保證收斂,尤其是在有很多閉環(huán)的情況下