【CS224W課程筆記】Message Parsing and Node Classification

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:令W表示一個(gè)n個(gè)節(jié)點(diǎn)上的n \times n的帶權(quán)鄰接矩陣裁着。令Y=\{-1, 0, 1\}^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)i的標(biāo)簽Y_i取決于其鄰居N_i的標(biāo)簽
P(Y_i|i) = P(Y_i|N_i)

Collective Classification涉及三個(gè)步驟:

  1. Local Classifier: (bootstrap step)分配初始標(biāo)簽桶雀。根據(jù)節(jié)點(diǎn)屬性或特性預(yù)測標(biāo)準(zhǔn)矿酵,這是一個(gè)標(biāo)準(zhǔn)的分類任務(wù)唬复,不涉及網(wǎng)絡(luò)信息。
  2. Relational Classifier: 捕捉節(jié)點(diǎn)之間的相關(guān)性全肮。學(xué)習(xí)一個(gè)基于鄰居標(biāo)簽屬性對各節(jié)點(diǎn)進(jìn)行分類的分類器敞咧,這里用到了網(wǎng)絡(luò)的信息。
  3. 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:Y_i類別的可能性是其鄰居類別可能性的加權(quán)平均加匈。對于有標(biāo)簽節(jié)點(diǎn)存璃,使用groud-truth的Y標(biāo)簽進(jìn)行初始化;對于無標(biāo)簽節(jié)點(diǎn)矩动,對Y進(jìn)行統(tǒng)一初始化有巧。以任意順序更新節(jié)點(diǎn),直到收斂或達(dá)到最大次數(shù)悲没。

對每個(gè)節(jié)點(diǎn)i和標(biāo)簽c重復(fù)進(jìn)行如下計(jì)算(其中N_i表示節(jié)點(diǎn)i的鄰居數(shù)篮迎,W(i,j)表示從ij的邊的權(quán)重):
P(Y_i = c) = \frac{1}{|N_i|} \sum_{(i,j)\in E} W(i,j)P(Y_j=c)

該方法的困難在于無法保證收斂以及模型無法用到節(jié)點(diǎn)的特征信息。

Iterative classification

Main idea:克服Relational Classifier未使用節(jié)點(diǎn)屬性的缺點(diǎn)示姿,基于節(jié)點(diǎn)i的屬性和鄰居節(jié)點(diǎn)N_i的標(biāo)簽對節(jié)點(diǎn)i進(jìn)行分類甜橱。為每個(gè)節(jié)點(diǎn)i創(chuàng)建一個(gè)平面向量a_i,然后使用a_i訓(xùn)練一個(gè)分類器栈戳;每個(gè)節(jié)點(diǎn)具有不同數(shù)量的鄰居岂傲,因此可以使用以下方法進(jìn)行匯總(aggregate):計(jì)數(shù)(有多少鄰居節(jié)點(diǎn)擁有某種特性)、模式子檀、比例镊掖、均值、存在等褂痰。

Basic architechture:

  1. Bootstrap phase:將每個(gè)節(jié)點(diǎn)i轉(zhuǎn)換為平面向量a_i亩进,使用local classifier f(a_i),如SVM缩歪、kNN計(jì)算Y_i的最佳值归薛;
  2. Iteration phase:對每個(gè)節(jié)點(diǎn)i重復(fù)以下過程:根據(jù)迭代結(jié)果更新節(jié)點(diǎn)向量a_i,重新計(jì)算f(a_i),迭代該過程直到類標(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ù)傳遞

Message Passing

注意:在一個(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 \psi: 節(jié)點(diǎn)和其鄰居之間的依賴關(guān)系。\psi(Y_i, Y_j)等于給定節(jié)點(diǎn)j處于狀態(tài)Y_i下的鄰居節(jié)點(diǎn)i汗洒,其狀態(tài)為y_j的可能性议纯。
  • Prior belief /phi: 節(jié)點(diǎn)i處于狀態(tài)Y_i下的概率\phi_i(Y_i)
  • m_{i \rightarrow j}(Y_j)表示ij處于狀態(tài)Y_j的估計(jì)溢谤。
  • \mathcal{L}是所有的狀態(tài)集合瞻凤。

Process:

  1. 初始化所有的消息為1;
  2. 對每個(gè)結(jié)點(diǎn)重復(fù)如下操作:
    m_{i \rightarrow j}(Y_j) = \alpha \sum_{Y_i \in \mathcal{L}} \psi(Y_i, Y_j) \phi_i(Y_i) \prod_{k \in \mathcal{N}_i \backslash j} m_{k \rightarrow i}(Y_i)
  3. 收斂后世杀,令b_i(Y_i)表示i處于狀態(tài)Y_i的belief阀参,其計(jì)算如下:
    b_i(Y_i) = \alpha \phi_i(Y_i) \prod_{j \in \mathcal{N}_i} m_{j \rightarrow i}(Y_i), \forall Y_i \in \mathcal{L}

Advantages:

  • 很容易進(jìn)行編程和并行計(jì)算
  • 容易泛化到其它圖模型

Challenges:
不能保證收斂,尤其是在有很多閉環(huán)的情況下

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末瞻坝,一起剝皮案震驚了整個(gè)濱河市蛛壳,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌所刀,老刑警劉巖衙荐,帶你破解...
    沈念sama閱讀 221,430評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異浮创,居然都是意外死亡忧吟,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,406評論 3 398
  • 文/潘曉璐 我一進(jìn)店門斩披,熙熙樓的掌柜王于貴愁眉苦臉地迎上來溜族,“玉大人,你說我怎么就攤上這事垦沉』褪悖” “怎么了?”我有些...
    開封第一講書人閱讀 167,834評論 0 360
  • 文/不壞的土叔 我叫張陵乡话,是天一觀的道長摧玫。 經(jīng)常有香客問我,道長,這世上最難降的妖魔是什么诬像? 我笑而不...
    開封第一講書人閱讀 59,543評論 1 296
  • 正文 為了忘掉前任屋群,我火速辦了婚禮,結(jié)果婚禮上坏挠,老公的妹妹穿的比我還像新娘芍躏。我一直安慰自己,他們只是感情好降狠,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,547評論 6 397
  • 文/花漫 我一把揭開白布对竣。 她就那樣靜靜地躺著,像睡著了一般榜配。 火紅的嫁衣襯著肌膚如雪否纬。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,196評論 1 308
  • 那天蛋褥,我揣著相機(jī)與錄音临燃,去河邊找鬼。 笑死烙心,一個(gè)胖子當(dāng)著我的面吹牛膜廊,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播淫茵,決...
    沈念sama閱讀 40,776評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼爪瓜,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了匙瘪?” 一聲冷哼從身側(cè)響起铆铆,我...
    開封第一講書人閱讀 39,671評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎丹喻,沒想到半個(gè)月后算灸,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,221評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡驻啤,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,303評論 3 340
  • 正文 我和宋清朗相戀三年菲驴,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片骑冗。...
    茶點(diǎn)故事閱讀 40,444評論 1 352
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡赊瞬,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出贼涩,到底是詐尸還是另有隱情巧涧,我是刑警寧澤,帶...
    沈念sama閱讀 36,134評論 5 350
  • 正文 年R本政府宣布遥倦,位于F島的核電站谤绳,受9級特大地震影響占锯,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜缩筛,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,810評論 3 333
  • 文/蒙蒙 一消略、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧瞎抛,春花似錦艺演、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,285評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至断凶,卻和暖如春伤提,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背认烁。 一陣腳步聲響...
    開封第一講書人閱讀 33,399評論 1 272
  • 我被黑心中介騙來泰國打工飘弧, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人砚著。 一個(gè)月前我還...
    沈念sama閱讀 48,837評論 3 376
  • 正文 我出身青樓,卻偏偏與公主長得像痴昧,于是被迫代替她去往敵國和親稽穆。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,455評論 2 359