Kolektivní klasifikace - Collective classification

v teorie sítí, kolektivní klasifikace je simultánní predikce štítků pro více objektů, kde každý štítek je predikován pomocí informací o pozorovaném objektu funkce, pozorované vlastnosti a štítky jeho sousedů a nepozorované štítky jeho sousedů.^[1] Problémy kolektivní klasifikace jsou definovány z hlediska sítí náhodných proměnných, kde struktura sítě určuje vztah mezi náhodnými proměnnými. Odvození se provádí na více náhodných proměnných současně, obvykle šířením informací mezi uzly v síti za účelem provedení přibližné inference. Lze využít přístupy, které používají kolektivní klasifikaci relační informace při provádění závěru. Mezi příklady kolektivní klasifikace patří předpovídání atributů (např. Pohlaví, věk, politická příslušnost) jednotlivců v a sociální síť, klasifikace webových stránek v Celosvětová Síť a odvození oblasti výzkumu příspěvku v datovém souboru vědecké publikace.

Motivace a pozadí

Hlavním zaměřením strojového učení je tradičně řešení klasifikace problémy. (Například vzhledem ke sbírce e-mailů chceme zjistit, které z nich jsou spam, a které nejsou.) Mnoho modelů strojového učení pro provádění tohoto úkolu se pokusí kategorizovat každou položku nezávisle a zaměřit se na samostatné předpovídání štítků tříd. Přesnost predikce štítků, jejichž hodnoty musí být odvozeny, lze však zlepšit znalostmi správných štítků tříd pro související položky. Například je jednodušší předvídat téma webové stránky, pokud známe témata webových stránek, které na ni odkazují. Podobně se zvyšuje šance, že určité slovo bude slovesem, pokud víme, že předchozí slovo ve větě je podstatným jménem; znalost prvních několika znaků ve slově může mnohem snáze identifikovat zbývající znaky. Mnoho vědců navrhlo techniky, které se pokoušejí klasifikovat vzorky společným nebo kolektivním způsobem, místo aby s každým vzorkem zacházely izolovaně; tyto techniky umožnily významné zvýšení přesnosti klasifikace.^[1][2]

Příklad

Zvažte úkol odvodit politickou příslušnost uživatelů v sociální síti, kde je pozorována určitá část těchto vztahů a zbytek je nepozorován. Každý uživatel má místní funkce, například informace o svém profilu, a existují odkazy mezi uživateli, kteří jsou přáteli v této sociální síti. Přístup, který kolektivně neklasifikuje uživatele, bude každého uživatele v síti zvažovat samostatně a k odvození přidružení stran použije své místní funkce. Přístup, který provádí kolektivní klasifikaci, by mohl předpokládat, že uživatelé, kteří jsou přáteli, mají tendenci mít podobné politické názory, a pak by mohli společně odvodit všechny nepozorované stranické vztahy při využití bohaté relační struktury sociální sítě.

Definice

Zvažte částečně pod dohledem problém přiřazení štítků uzlům v síti pomocí znalosti podmnožiny štítků uzlů. Konkrétně nám je dána síť představovaná a graf ${ displaystyle G}$ se sadou uzlů ${ displaystyle V}$ a sadu hran ${ displaystyle E}$ představující vztahy mezi uzly. Každý uzel ${ displaystyle v_ {i} ve V}$ je popsán jeho atributy: vektorem funkce ${ displaystyle x_ {i} v X}$ a jeho štítek (nebo třída) ${ displaystyle y_ {i} v Y}$.

${ displaystyle V}$ lze dále rozdělit na dvě sady uzlů: ${ displaystyle L}$, množina uzlů, pro které známe správné hodnoty návěští (sledované proměnné), a ${ displaystyle U}$, uzly, jejichž popisky musí být odvozeny. Úkolem kolektivní klasifikace je označení uzlů ${ displaystyle U}$ se štítkem ze sady štítků ${ displaystyle L = {L_ {1}, cdots L_ {q} }}$.

V takovém nastavení tradiční klasifikační algoritmy předpokládají, že data jsou čerpána nezávisle a identicky z nějaké distribuce (iid). To znamená, že popisky odvozené pro uzly, jejichž popisek není pozorován, jsou na sobě nezávislé. Při provádění kolektivní klasifikace nelze tento předpoklad učinit. Místo toho existují tři odlišné typy korelací, které lze použít k určení klasifikace nebo označení ${ displaystyle v}$:

1. Korelace mezi štítkem ${ displaystyle v}$ a sledované atributy ${ displaystyle v}$. Tradiční iid klasifikátory, které využívají vektory funkcí, jsou příkladem přístupů, které používají tuto korelaci.
2. Korelace mezi štítkem ${ displaystyle v}$ a pozorované atributy (včetně pozorovaných štítků) uzlů v sousedství ${ displaystyle v}$.
3. Korelace mezi štítkem ${ displaystyle v}$ a nepozorované štítky objektů v sousedství ${ displaystyle v}$.

Kolektivní klasifikace označuje kombinovanou klasifikaci sady vzájemně propojených objektů pomocí tří výše uvedených typů informací.

Metody

Existuje několik existujících přístupů ke kolektivní klasifikaci. Dvěma hlavními metodami jsou iterační metody a metody založené na pravděpodobnostní grafické modely.^[3]

Iterační metody

Obecnou myšlenkou iterativních metod je iterativně kombinovat a revidovat předpovědi jednotlivých uzlů tak, aby bylo dosaženo rovnováhy. Když je aktualizace předpovědí pro jednotlivé uzly rychlá operace, složitost těchto iteračních metod bude počet iterací potřebných pro konvergenci. Ačkoli konvergence a optimalita nejsou vždy matematicky zaručeny, v praxi se tyto přístupy obvykle rychle sblíží k dobrému řešení, v závislosti na struktuře grafu a složitosti problému. Metody uvedené v této části jsou reprezentativní pro tento iterativní přístup.

Šíření štítku

Přirozeným předpokladem v klasifikaci sítě je, že sousední uzly pravděpodobně budou mít stejný štítek (tj. nákaza^{[nutná disambiguation ]} nebo homofilně ). Prediktor pro uzel ${ displaystyle V_ {i}}$ pomocí metody šíření štítků je vážený průměr sousedních štítků ${ displaystyle Y_ {N_ {i}}}$^[4]

Iterativní klasifikační algoritmy (ICA)

Zatímco šíření štítků je překvapivě efektivní, někdy nemusí zachytit složitou relační dynamiku. Sofistikovanější přístupy mohou používat bohatší prediktory. Předpokládejme, že máme klasifikátor ${ displaystyle h}$ který byl vyškolen pro klasifikaci uzlu ${ displaystyle v_ {i}}$ vzhledem k jeho vlastnostem ${ displaystyle X_ {i}}$ a funkce ${ displaystyle X_ {N_ {i}}}$ a štítky ${ displaystyle Y_ {N_ {i}}}$ jejích sousedů ${ displaystyle N_ {i}}$. Iterativní klasifikace platí používá místní klasifikátor pro každý uzel, který používá informace o aktuálních předpovědích a základní pravdivé informace o sousedech uzlu, a iteruje, dokud se místní předpovědi nespojí s globálním řešením. Iterativní klasifikace je „algoritmický rámec“ v tom, že je agnostický vůči volbě prediktoru; to z něj dělá velmi univerzální nástroj pro kolektivní klasifikaci.^[5][6][7]

Kolektivní klasifikace s grafickými modely

Dalším přístupem ke kolektivní klasifikaci je představit problém s a grafický model a používat techniky učení a odvození pro přístup grafického modelování k dosažení správné klasifikace. Grafické modely jsou nástroje pro společnou pravděpodobnostní inferenci, díky čemuž jsou ideální pro kolektivní klasifikaci. Vyznačují se grafickým znázorněním rozdělení pravděpodobnosti ${ displaystyle P}$, ve kterém jsou náhodné proměnné uzly v grafu ${ displaystyle G}$. Grafické modely lze obecně rozdělit podle toho, zda je směrován podkladový graf (např. Bayesovské sítě nebo sbírky místních klasifikátorů) nebo neorientované (např. Markovova náhodná pole (MRF)).

Gibbsův odběr vzorků

Gibbsův výběr je obecný rámec pro aproximaci distribuce. Je to Markovský řetězec Monte Carlo Algoritmus v tom, že iterativně vzorkuje z aktuálního odhadu distribuce a vytváří Markovův řetězec, který konverguje k cílové (stacionární) distribuci. Základní myšlenkou pro Gibbs Sampling je vzorkování pro nejlepší odhad štítku pro ${ displaystyle y_ {i}}$ dané všechny hodnoty pro uzly v ${ displaystyle N_ {i}}$ pomocí lokálního klasifikátoru ${ displaystyle f}$ pro pevný počet iterací. Poté pro každý z nich vzorkujeme štítky ${ displaystyle y_ {i} v Y}$ a udržovat statistické údaje o počtu opakování vzorkování štítku ${ displaystyle l}$ pro uzel ${ displaystyle y_ {i}}$. Po shromáždění předdefinovaného počtu takových vzorků vydáme nejlepší přiřazení štítku pro uzel ${ displaystyle y_ {i}}$ výběrem štítku, kterému byl přiřazen maximální počet opakování ${ displaystyle y_ {i}}$ při odběru vzorků.^[8][9]

Loopy šíření víry

U určitých neorientovaných grafických modelů je možné efektivně provádět přesný závěr prostřednictvím předávání zpráv nebo šíření víry algoritmy.^[10] Tyto algoritmy se řídí jednoduchým iteračním vzorem: každá proměnná předává své „přesvědčení“ o okrajových distribucích svých sousedů a poté používá příchozí zprávy o své vlastní hodnotě k aktualizaci svých přesvědčení. Konvergence ke skutečným okrajům je zaručena pro stromově strukturované MRF, ale není zaručena pro MRF s cykly.

Statistické relační učení (SRL)

Statistické relační učení se často používá k řešení problémů kolektivní klasifikace. Pro nastavení kolektivní klasifikace byla použita řada metod SRL. Některé z metod zahrnují přímé metody, jako jsou pravděpodobnostní relační modely (PRM),^[11] spojené podmíněné modely, jako je klasifikace založená na odkazech,^[12]a nepřímé metody jako Markovovy logické sítě (MLN)^[13] a Pravděpodobná měkká logika (PSL).^[14]

Aplikace

Kolektivní klasifikace se používá v mnoha doménách, které vykazují relační strukturu, například:

• Analýza sociálních sítí, kde kolektivní přístupy k úkolům klasifikace uzlů, jako je detekce uživatelů se zlými úmysly, mohou využívat informace o vztazích mezi uzly.^[15][16]
• Rozlišení entity, kde lze k identifikaci autorů příspěvků využít spoluautorských vztahů.^[17]
• Rozpoznání pojmenované entity, kde to některé přístupy považují za problém označení textové sekvence a společně odvozují popisky každého slova ve větě, obvykle pomocí podmíněné náhodné pole který modeluje lineární řetězec závislostí mezi popisky sousedních slov ve větě.^[18]
• Klasifikace dokumentu kde lze například společně použít sémantické podobnosti mezi dokumenty jako signály, že určité dokumenty patří do stejné třídy.^[19]
• Výpočetní biologie, kde grafické modely jako Markovova náhodná pole se používají ke společnému odvození vztahů mezi biologickými entitami, jako jsou geny.^[20]
• Počítačové vidění, kde lze například použít kolektivní klasifikaci pro současné rozpoznávání více objektů.^[21]

Viz také

• Strojové učení
• Klasifikace
• Podobnost (síťová věda)
• Graf (diskrétní matematika)
• Statistické relační učení
• Bayesian Networks
• Markovovo náhodné pole

Reference