A hálózatok sok mindent elárulnak nekünk. Az egyik érdekes jelenség, amelyet a hálózatok illusztrálnak, hogy a hasonló objektumok valószínűleg kapcsolatot alakítanak ki egymással. Ez valóban látható a közösségi hálózatunkon. Két személy, akiknek hasonló hobbijaik vannak, valószínűleg barátkozni fognak egymással. Ez a megfigyelés lehetővé teszi számunkra, hogy előre jelezzük a hobbit a közösségi hálózatunkban lévő baráti kapcsolatok alapján. Nyugodtan kijelenthetjük, hogy az a személy, akinek sok teniszező barátja van, valószínűleg teniszezni fog, nem igaz?
Ebben a sorozatban megismerheti a Címketerjesztés nevű gépi tanulási algoritmust. Ez az algoritmus matematikaibb módon hajtja végre a fenti előrejelzést. Ez a bejegyzés annak a sorozatnak az 1. része, amely bemutatja a címketerjesztés alapkoncepcióját. A 2. részben megpróbáljuk a címketerjesztést a NetworkX nevű Python könyvtár használatával, amely az egyik híres Python-könyvtár a hálózati adatok manipulálására.
Bevezetés a NetworkX segítségével történő címketerjesztésbe – 1. rész (ez a bejegyzés)
„Bevezetés a NetworkX-szel történő címketerjesztésbe – 2. rész”
Kezdjük a megoldandó probléma meghatározásával. Ezt a problémát csomópont-besorolásnak nevezik. Ebben a feladatban egy hálózatot kapunk, amely csomópontok halmazából és élek halmazából áll. A probléma fontos aspektusa az, hogy a csomópontok bizonyos részei megkapják a címkéket. Mutatjuk a kapott összetevőket:
Néhány csomópont (A, B, C és D) piros vagy kék színű, míg néhány (X és Y) nem. Tegyük fel, hogy a szín a címkét jelenti. Itt szeretnénk megjósolni a címkézetlen csomópontok (X és Y) színeit (címkéit). Ez az a probléma, amelyet a Label Propagation megoldhat.
Tehát hogyan tudjuk megoldani ezt a problémát? A Label Propagation megpróbálja megtalálni az optimális színezést, amely megfelel a következő két feltételnek:
Megkötés 1: A címkét kapott csomópont nem változtathatja meg a címkéjét.
2. megkötés: Egy pár összekapcsolt csomópontnak azonos címkével kell rendelkeznie.
A Constraint1 egyszerű. Csak annyit ír, hogy a kék az kék, a piros az piros. A megadott színek nem változhatnak a Label Propagation kimenetében. A Constraint2 ennek az algoritmusnak a magja. Ha egy csomópont egy másik, piros színű csomóponttal van kapcsolatban, az első csomópontnak is pirosnak kell lennie. Vegye figyelembe, hogy az első megkötés a „kell”, de a második megkötés a „kell”. Így meg fogjuk találni azt a színezést, amelyminimalizálja a Constraint2 megsértésének számát anélkül, hogy az 1. megkötés megsértése nélkül.
OK, keressük meg az optimális színezést a fenti példához. Mivel ez az első próbatételed, szánjunk időt a színezés minden esetének kipróbálására. Először is megpróbáljuk mindkét címkézetlen csomópontot kékre festeni (lásd alább).
Miután megfestettük az összes címkézetlen csomópontot, könnyű megszámolni a Constraint2 megsértésének számát. A fenti ábrán látható módon a jogsértések száma 3. Rendben, ez jó kiindulópontnak tűnik. Próbáljunk ki más festést.
Ezúttal X-et pirosra, Y-t kékre festettük. A szabálysértések száma ebben az esetben is 3. Az (A, X) és (B, X) csatlakozásokon észlelt szabálysértések megszűnnek, de az (X, C) és (X, Y) csatlakozásokon új szabálysértéseket vezetnek be. OK, próbáljuk meg a következő színezést.
Most mindkét címkézetlen csomópontot pirosra festettük a fenti ábrán látható módon. Hú, a jogsértések száma most 2. Az eredmény javult! Mielőtt arra következtetnénk, hogy ez az optimális megoldás, próbáljuk ki a színezés utolsó kombinációját.
Ahogy sejtheti, rosszabbul lettünk. Most 4 szabálysértésünk van.
OK, ennek eredményeként a harmadik próbálkozással (X = piros, Y = piros) érhető el az optimális színezés, ami pontosan a Label Propagation kimenete! Tényleg egyszerű, nem?
Ez a történet vége? - Várjon! Egy kérdés természetesen felmerül. Ki kell próbálnunk az összes kombinációt? Mi van, ha a címkézetlen csomópontok száma mondjuk egy millió? Nyilvánvalóan lehetetlen az összes lehetséges színezést kipróbálni. Hogyan juthatunk ilyenkor az optimális megoldáshoz? Sajnos bebizonyítható, hogy minden kombinációt ki kell próbálnunk, hogy megtaláljuk az optimális megoldást.
Ez azt jelenti, hogy a címkeszaporítás szemét? Határozottan nem. A Label Propagation közelítő megoldást kaphat, ami ésszerű, és a legtöbb esetben elég jó megoldás. Nézzük meg, hogyan kapjuk meg a közelítő megoldást.
A Label Propagation úgy véli, hogy a címkézett csomópontok 0 vagy 1 számot kapnak. A piros címkével jelölt csomópont 1-et, a kék címkével jelölt csomópont pedig 0-t. Tehát itt a szám a színt jelzi. Tegyük fel, hogy „pirosodás”. Más szavakkal, az 1-hez közeli szám a vöröshez közeli színt jelöli. Itt az a cél, hogy a 0-tól 1-ig tartó „optimális” számokat hozzárendeljük a címkézetlen csomópontokhoz. Ha egy címkézetlen csomóponthoz 1-hez közeli számot rendelünk (például 0,78), akkor azt pirosra kell színezni!
E számok megszerzéséhez a Label Propagation „terjeszti” a számokat csomópontról csomópontra az élek mentén. Ezért nevezik ezt az algoritmust Label Propagation. Lássuk, mit csinál a Label Propagation lépésről lépésre.
A fenti ábra a kezdeti állapotot szemlélteti. A címkézett csomópontok 0 vagy 1 számot kapnak. A címkézetlen csomópontok 0,5-öt kapnak, mert semmit sem tudunk a színükről. A Label Propagation a számokat az élek mentén terjeszti, és a címkézetlen csomópontokon lévő számokat úgy frissíti, hogy átveszi a terjesztett számok átlagát a szomszédoktól. A következő ábra azt mutatja, hogy mi történik egy lépés végrehajtása után.
Az X csomópont a 0,625-ös számot kapta, mivel az 1-et A-ból és B-ből, a 0-t C-ből, a 0,5-öt pedig Y-ből terjesztik. Az Y csomópont 0,5-öt kapott, mivel a 0 a C-ből, az 1-es a D-ből, a 0,5-ös az X-ből származik. OK, hajtsunk végre még egy lépést, és nézzük meg, mi történik.
Az X-en lévő szám nem változott, mert a szomszédjának számai ugyanazok az előző lépésben. Az Y-n lévő szám 0,5-ről 0,542-re nőtt, mivel az X-ről terjedő szám nőtt. A Label Propagation ezt a lépést újra és újra megismétli, és a címkézetlen csomópontok számai konvergálnak valamilyen fix ponthoz. Nézzük meg a végső kimenetet bizonyos számú iteráció után.
A fenti végeredményben mindkét címkézetlen csomóponthoz 0,5-nél nagyobb számok vannak hozzárendelve, ami azt jelenti, hogy inkább piros, mint kék. Ezért a Label Propagation arra a következtetésre jut, hogy a címkézetlen csomópontok címkéi egyaránt pirosak. Igazodik ahhoz az optimális eredményhez, amelyet korábban a brute force megoldással kaptunk!
A címkeszaporítás előnyei és hátrányai a következők:
Előnyök: ésszerű eredményt érhet el anélkül, hogy kipróbálná az összes színkombinációt, ami milliárdok vagy akár billiók is lehetnek, ha sok a címkézetlen csomópont.
Előnyök: meg tudjuk állapítani a címkézetlen csomópontok „vörösségét”. A fenti eredményben X pirosabb, mint Y. Ez azt jelzi, hogy ismerhetjük előrejelzésünk bizonyosságának fokát.
Előnyök: matematikailag bebizonyosodott, hogy a címketerjesztés lépései a címkézetlen csomópontokhoz rendelt kezdeti számoktól függetlenül konvergálnak (példánkban ez 0,5 volt). Gyakorlatilag fontos, mert nem akarunk olyan algoritmust használni, amely bizonyítottan nem áll le.
Hátrányok: A Label Propagation megoldása eltérhet az optimális megoldástól, mivel ez egy közelítő megoldás. De nem feltétlenül rossz. Néha a közelítő megoldás „gyakorlatilag jobb” lehet, mint az optimális.
Ez mind a címketerjesztés alapfogalma, amelyet meg kell tanulnia. Noha ebben a bejegyzésben nincs konvertálva, csak 2 helyett 3 vagy több címkével is foglalkozhatunk.Egy kis matematikai ismeretekre van szükség, hogy megtudja, miért tud ilyen szép módon ésszerű eredményt elérni. Hagyjuk a haladóbb cikkekre. Az érdeklődő olvasók beleugorhatnak az alább felsorolt hivatkozásokba. OK, a következő lépés a kódolás Python könyvtárral, a NetworkX-szel.
Referencia
„Félig felügyelt tanulás Gauss-mezők és harmonikus függvények használatával”: ez az a cikk, amely először javasolta az ebben a bejegyzésben tanulmányozott algoritmust.
„Bevezetés a félig felügyelt tanulásba”: ez a könyv a félig felügyelt tanulást magyarázza, amely a gépi tanulási algoritmusok egy kategóriája. A címkeszaporítás ebbe a kategóriába tartozik.
