Kollektiv tasnif - Collective classification

Yilda tarmoq nazariyasi, jamoaviy tasnif - bir nechta ob'ektlar uchun yorliqlarni bir vaqtning o'zida bashorat qilish, bu erda har bir yorliq ob'ekt kuzatilganligi haqida ma'lumot yordamida bashorat qilinadi Xususiyatlari, qo'shnilarining kuzatilgan xususiyatlari va yorliqlari va qo'shnilarining kuzatilmagan yorliqlari.[1] Kollektiv tasniflash muammolari tasodifiy o'zgaruvchilarning tarmoqlari nuqtai nazaridan aniqlanadi, bu erda tarmoq tuzilishi tasodifiy o'zgaruvchilar o'rtasidagi bog'liqlikni aniqlaydi. Xulosa bir vaqtning o'zida bir nechta tasodifiy o'zgaruvchilarda, odatda taxminiy xulosani bajarish uchun tarmoqdagi tugunlar o'rtasida ma'lumotni tarqatish orqali amalga oshiriladi. Jamoa tasnifidan foydalanadigan yondashuvlardan foydalanish mumkin aloqador ma'lumotlar xulosa chiqarishda. Kollektiv tasniflashning misollariga a. Tarkibidagi shaxslarning atributlarini (masalan, jinsi, yoshi, siyosiy mansubligi) bashorat qilish kiradi ijtimoiy tarmoq, veb-sahifalarini tasniflash Butunjahon tarmog'i va ilmiy nashrlar to'plamidagi maqolaning tadqiqot sohasi haqida xulosa chiqarish.

Motivatsiya va fon

An'anaga ko'ra, mashinani o'rganishning asosiy yo'nalishi hal qilishdir tasnif muammolar. (Masalan, elektron pochta xabarlari to'plamini hisobga olgan holda, qaysi biri ekanligini aniqlashni xohlaymiz Spam, va bunday emas.) Ushbu vazifani bajarish uchun ko'plab mashina o'rganish modellari har bir narsani toifalarga ajratishga harakat qiladi mustaqil ravishda va sinf yorliqlarini alohida bashorat qilishga e'tibor qarating. Shu bilan birga, qiymatlari chiqarilishi kerak bo'lgan yorliqlar uchun bashoratning aniqligi, tegishli narsalar uchun to'g'ri sinf yorliqlarini bilish bilan yaxshilanishi mumkin. Masalan, agar unga bog'langan veb-sahifalarning mavzularini bilsak, uning mavzusini oldindan aytish osonroq. Xuddi shunday, ma'lum bir so'zning fe'l bo'lish ehtimoli ortadi, agar gapdagi oldingi so'z ot ekanligini bilsak; so'zdagi dastlabki bir nechta belgini bilish qolgan belgilarni aniqlashni ancha osonlashtirishi mumkin. Ko'pgina tadqiqotchilar har bir namunani alohida-alohida davolash o'rniga, qo'shma yoki jamoaviy usulda tasniflashga urinish usullarini taklif qilishdi; ushbu uslublar tasniflash aniqligida sezilarli yutuqlarni qo'lga kiritdi.[1][2]

Misol

Ijtimoiy tarmoqdagi foydalanuvchilarning siyosiy mansubligi haqida xulosa chiqarish vazifasini ko'rib chiqing, u erda ushbu bog'lanishlarning bir qismi kuzatiladi va qolgan qismi kuzatilmaydi. Har bir foydalanuvchi o'zlarining profil ma'lumotlari kabi mahalliy xususiyatlarga ega va ushbu ijtimoiy tarmoqda do'st bo'lgan foydalanuvchilar o'rtasida havolalar mavjud. Birgalikda foydalanuvchilarni tasniflamaydigan yondashuv tarmoqdagi har bir foydalanuvchini mustaqil ravishda ko'rib chiqadi va partiyalarga bog'liqligini aniqlash uchun ularning mahalliy xususiyatlaridan foydalanadi. Kollektiv tasnifni amalga oshiradigan yondashuv, do'st bo'lgan foydalanuvchilar o'xshash siyosiy qarashlarga ega bo'lib, keyinchalik ijtimoiy tarmoqning boy munosabatlar tizimidan foydalangan holda, kuzatilmagan barcha partiyalarni birlashtirishi mumkin deb taxmin qilishi mumkin.

Ta'rif

Ni ko'rib chiqing yarim nazorat ostida o'rganish tugun yorliqlari to'plamining bilimlari yordamida tarmoqdagi tugunlarga yorliqlarni berish muammosi. Xususan, bizga a bilan ifodalangan tarmoq berilgan grafik tugunlar to'plami bilan va chekka to'plami tugunlar o'rtasidagi munosabatlarni ifodalaydi. Har bir tugun atributlari bilan tavsiflanadi: xususiyat vektori va uning yorlig'i (yoki sinf) .

qo'shimcha ravishda ikkita tugun to'plamiga bo'linishi mumkin: , biz to'g'ri yorliq qiymatlarini biladigan tugunlar to'plami (kuzatilgan o'zgaruvchilar) va , yorliqlari haqida xulosa qilish kerak bo'lgan tugunlar. Kollektiv tasniflash vazifasi tugunlarni belgilashdir yorliq to'plamidan yorliq bilan .

Bunday sozlamalarda an'anaviy tasniflash algoritmlari ma'lumotlarning ba'zi taqsimotlardan (iid) mustaqil va bir xil tarzda olinganligini taxmin qiladi. Bu shuni anglatadiki, yorlig'i kuzatilmaydigan tugunlar uchun chiqarilgan yorliqlar bir-biridan mustaqil. Klassik tasnifni amalga oshirishda kishi bu taxminni amalga oshirmaydi. Buning o'rniga, tasnifini yoki yorlig'ini aniqlash uchun ishlatilishi mumkin bo'lgan uchta aniq korrelyatsiya turi mavjud :

  1. Yorlig'i o'rtasidagi o'zaro bog'liqlik va ning kuzatilgan atributlari . Xususiyat vektorlaridan foydalanadigan an'anaviy iid klassifikatorlari ushbu korrelyatsiyadan foydalanadigan yondashuvlarning namunasidir.
  2. Yorlig'i o'rtasidagi o'zaro bog'liqlik va atrofidagi tugunlarning kuzatilgan atributlari (shu jumladan kuzatilgan yorliqlari) .
  3. Yorlig'i o'rtasidagi o'zaro bog'liqlik va atrofidagi ob'ektlarning kuzatilmagan yorliqlari .

Kollektiv tasniflash yuqoridagi uchta turdagi ma'lumotlardan foydalangan holda o'zaro bog'liq ob'ektlar to'plamining birlashtirilgan tasnifini anglatadi.

Usullari

Kollektiv tasniflashda bir nechta mavjud yondashuvlar mavjud. Ikkita asosiy usul - takrorlanadigan usullar va ularga asoslangan usullar ehtimollik grafik modellari.[3]

Takrorlash usullari

Takrorlash usullari uchun umumiy g'oya - bu muvozanatga erishish uchun individual tugun prognozlarini takroriy birlashtirish va qayta ko'rib chiqish. Alohida tugunlar uchun bashoratlarni yangilash tezkor operatsiya bo'lganda, ushbu takroriy usullarning murakkabligi konvergentsiya uchun zarur bo'lgan takroriy soni bo'ladi. Garchi yaqinlashish va maqbullik har doim ham matematik jihatdan kafolatlanmasa-da, amalda bu yondashuvlar grafik tuzilishga va muammolarning murakkabligiga qarab, odatda tezda yaxshi echimga aylanadi. Ushbu bo'limda keltirilgan usullar ushbu takroriy yondashuvning vakili hisoblanadi.

Yorliqni ko'paytirish

Tarmoq tasnifidagi tabiiy taxmin shundan iboratki, qo'shni tugunlar bir xil yorliqqa ega bo'lishi mumkin (ya'ni, yuqumli kasallik[ajratish kerak ] yoki gomofil ). Tugun uchun bashorat qiluvchi yorlig'i ko'paytirish usulidan foydalanib, uning qo'shni yorliqlarining o'rtacha og'irligi hisoblanadi [4]

Takroriy tasniflash algoritmlari (ICA)

Yorliqning tarqalishi hayratlanarli darajada samarali bo'lishiga qaramay, ba'zida murakkab relyatsion dinamikani ushlab turmasligi mumkin. Murakkab yondashuvlar boy predikatorlardan foydalanishi mumkin, deylik, bizda klassifikator mavjud tugunni tasniflashga o'rgatilgan uning xususiyatlarini hisobga olgan holda va xususiyatlari va yorliqlar qo'shnilarining . Iteratsion tasnif har bir tugun uchun mahalliy tasniflagichdan foydalanadi, bu erda mavjud bashoratlar va tugunning qo'shnilari haqidagi asosiy haqiqat ma'lumotlari ishlatiladi va mahalliy prognozlar global echimga kelguncha takrorlanadi. Takroriy tasniflash "algoritmik asos" dir, chunki u bashorat qilishni tanlash uchun agnostikdir; bu uni jamoaviy tasniflash uchun juda ko'p qirrali vositaga aylantiradi.[5][6][7]

Grafik modellar bilan kollektiv tasnif

Kollektiv tasniflashning yana bir yondashuvi bu muammoni a bilan ifodalashdir grafik model va to'g'ri tasniflarga erishish uchun grafik modellashtirish yondashuvi uchun o'rganish va xulosa qilish usullaridan foydalaning. Grafik modellar qo'shma, ehtimoliy xulosalar chiqarish vositasi bo'lib, ularni jamoaviy tasniflash uchun ideal qiladi. Ular ehtimollik taqsimotining grafik tasviri bilan tavsiflanadi , unda tasodifiy o'zgaruvchilar grafadagi tugunlardir . Grafik modellarni asosiy grafik yo'naltirilganligi (masalan, Bayes tarmoqlari yoki mahalliy klassifikatorlar to'plamlari) yoki yo'naltirilmagan (masalan, Markov tasodifiy maydonlari (MRF)).

Gibbs namunalari

Gibbs namunasi - bu taqsimotni taxmin qilish uchun umumiy asos. Bu Monte Karlo Markov zanjiri algoritm, u taqsimotning joriy bahosidan iterativ ravishda namuna oladi, maqsadli (statsionar) taqsimotga yaqinlashadigan Markov zanjirini yaratadi. Gibbs Samplingning asosiy g'oyasi - bu eng yaxshi yorliq bahosi uchun namuna olishdir. tugunlari uchun barcha qiymatlarni hisobga olgan holda mahalliy klassifikator yordamida aniq sonli takrorlash uchun. Shundan so'ng, biz har biri uchun yorliqlarni namuna olamiz va yorliq tanlaganimiz soni bo'yicha hisoblash statistikasini olib boring tugun uchun . Bunday namunalarning oldindan belgilangan sonini yig'gandan so'ng, biz tugun uchun eng yaxshi yorliqli topshiriqni chiqaramiz maksimal marta berilgan yorliqni tanlash orqali namunalarni yig'ish paytida.[8][9]

Loopik e'tiqodni ko'paytirish

Ba'zi yo'naltirilmagan grafik modellar uchun xabarni uzatish orqali aniq xulosani samarali bajarish mumkin e'tiqodni targ'ib qilish algoritmlar.[10] Ushbu algoritmlar oddiy iterativ sxemaga amal qiladi: har bir o'zgaruvchi o'z qo'shnilarining marginal taqsimotlari haqidagi "e'tiqodlarini" o'tkazadi, so'ngra o'zlarining e'tiqodlarini yangilash uchun o'zlarining qiymati to'g'risida kiruvchi xabarlardan foydalanadi. Daraxt tuzilgan MRFlar uchun haqiqiy marginallarga yaqinlashish kafolatlanadi, ammo tsiklli MRFlar uchun kafolat berilmaydi.

Statistik relyatsion ta'lim (SRL) bilan bog'liq

Statistik relyatsion ta'lim ko'pincha jamoaviy tasniflash muammolarini hal qilish uchun ishlatiladi. Kollektiv tasniflash sharoitida turli xil SRL usullari qo'llanilgan. Ba'zi usullarga to'g'ridan-to'g'ri usullar kiradi, masalan, ehtimoliy munosabat modellari (PRM),[11] bog'lanish asosida tasniflash kabi birlashtirilgan shartli modellar,[12]kabi bilvosita usullar Markov mantiqiy tarmoqlari (MLN)[13] va Ehtimolli yumshoq mantiq (PSL).[14]

Ilovalar

Kollektiv tasnif munosabat tizimiga ega bo'lgan ko'plab sohalarda qo'llaniladi, masalan:

  • Ijtimoiy tarmoq tahlili, zararli foydalanuvchilarni aniqlash kabi tugunlarni tasniflash vazifalariga kollektiv yondashuvlar tugunlar o'rtasidagi munosabatlar haqida ma'lumotdan foydalanishlari mumkin.[15][16]
  • Korxona qarori, bu erda hujjatlar mualliflarini aniqlash uchun hammualliflik munosabatlaridan foydalanish mumkin.[17]
  • Nomi tan olingan, bu erda ba'zi yondashuvlar buni matnni ketma-ketligini belgilash muammosi sifatida ko'rib chiqadi va jumlaga har bir so'zning yorliqlarini birgalikda chiqaradi, odatda shartli tasodifiy maydon gapdagi qo'shni so'zlarning yorliqlari orasidagi bog'liqlikning chiziqli zanjirini modellashtiradi.[18]
  • Hujjatlarning tasnifi, masalan, hujjatlararo semantik o'xshashliklardan ma'lum hujjatlar bir sinfga tegishli ekanligi signallari sifatida birgalikda foydalanish mumkin.[19]
  • Hisoblash biologiyasi, qayerda grafik modellar kabi Markov tasodifiy maydonlari genlar kabi biologik mavjudotlar o'rtasidagi munosabatlarni birgalikda xulosa qilish uchun foydalaniladi.[20]
  • Kompyuterni ko'rish, masalan, bir vaqtning o'zida bir nechta ob'ektlarni tanib olish uchun jamoaviy tasniflash qo'llanilishi mumkin.[21]

Shuningdek qarang

Adabiyotlar

  1. ^ a b Sen, Prithviraj; Namata, Galiley; Bilgich, Mustafo; Getur, Lise; Galligher, Brayan; Eliassi-Rad, Tina (2008). "Tarmoq ma'lumotlarida jamoaviy tasniflash". AI jurnali. 29 (3): 93. doi:10.1609 / oblast.v29i3.2157. ISSN  0738-4602.
  2. ^ Kaydanovich, Tomash; Kazienko, Przemyslav (2018). "Kollektiv tasnif": 253–265. doi:10.1007/978-1-4939-7131-2_45. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
  3. ^ London, Ben; Getoor, Lise (2014). "Tarmoq ma'lumotlarining jamoaviy tasnifi". Ma'lumotlarni tasnifi: Algoritmlar va ilovalar. 29: 399--416.
  4. ^ Chju, Xiaojin. "Belgilangan va markirovka qilinmagan ma'lumotlardan yorliqni ko'paytirish bilan o'rganish". CiteSeerX  10.1.1.14.3864. Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
  5. ^ Nevill, Jennifer; Jensen, Devid (2000). Relyatsion ma'lumotlarda takroriy tasnif (PDF). AAAI (Relation Data) statistik modellarini o'rganish bo'yicha seminar (SRL). AAAI. p. 8.
  6. ^ Chakrabarti, Soumen; Dom, Bayron; Indik, Pyotr (1998). Gipermurojatlar yordamida kengaytirilgan gipermatnli toifalash. Ma'lumotlarni boshqarish bo'yicha 1998 yil ACM SIGMOD xalqaro konferentsiyasi materiallari. Hisoblash texnikasi assotsiatsiyasi (ACM). p. 307-318. doi:10.1145/276304.276332.
  7. ^ Jensen, Devid; Nevill, Jennifer; Gallager, Devid (2000). Nega jamoaviy xulosa relyatsion tasnifni yaxshilaydi. ACM SIGKDD xalqaro konferentsiyasi - bu bilimlarni kashf qilish va ma'lumotlarni qazib olish. Hisoblash texnikasi assotsiatsiyasi (ACM). p. 5. doi:10.1145/1014052.1014125.
  8. ^ Mackskassy, ​​Sofus; Provost, Foster (2007). "Tarmoq ma'lumotlarida tasniflash: asboblar to'plami va yagona o'zgaruvchan vaziyatni o'rganish" (PDF). Mashinalarni o'rganish bo'yicha jurnal: 935 - 983.
  9. ^ Geman, Styuart; Donald, Foster (1990). Stoxastik bo'shashish, Gibbsning tarqalishi va Bayesning rasmlarni tiklashi. Morgan Kaufmann Publishers Inc p. 452-472.
  10. ^ Yedidia, J.S .; Freeman, W.T .; Y. (yanvar 2003). "E'tiqodni targ'ib qilish va uni umumlashtirish to'g'risida tushuncha". Lakemeyerda, Gerxard; Nebel, Bernxard (tahr.). Yangi ming yillikda sun'iy aqlni o'rganish. Morgan Kaufmann. 239–236 betlar. ISBN  978-1-55860-811-5. Olingan 2009-03-30.
  11. ^ Getur, Lise; Fridman, Nir; Koller, Dafne; Taskar, Benjamin (2002). "Bog'lanish strukturasining ehtimollik modellarini o'rganish" (PDF). Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
  12. ^ Lu, Tsin; Getoor, Lise (2003). Havola asosida tasniflash (PDF). Mashinalarni o'rganish bo'yicha xalqaro konferentsiya (ICML).
  13. ^ Dominogs, Pedro; Richardson, Metyu (2006). "Markov mantiqiy tarmoqlari" (PDF). Iqtibos jurnali talab qiladi | jurnal = (Yordam bering)
  14. ^ Bax, Stiven; Broecheler, Mattias; Xuang, Bert; Getoor, Lise (2017). "Menteşada yo'qotish Markovning tasodifiy maydonlari va ehtimollik yumshoq mantig'i". Mashinalarni o'rganish bo'yicha jurnal. 18: 1–67.
  15. ^ Jaafor, Umar; Birregah, Babiga (2017-07-31). Ijtimoiy tarmoqlarda jamoaviy tasnif. Nyu-York, Nyu-York, AQSh: ACM. doi:10.1145/3110025.3110128. ISBN  978-1-4503-4993-2.
  16. ^ Faxrayi, Shobeir; Fulds, Jeyms; Shashanka, Madhusudana; Getoor, Lise (2015). Rivojlanayotgan ko'p munosabatli ijtimoiy tarmoqlarda kollektiv spammerlarni aniqlash. Nyu-York, Nyu-York, AQSh: ACM Press. doi:10.1145/2783258.2788606. ISBN  978-1-4503-3664-2.
  17. ^ Bxattacharya, Indrajit; Getoor, Lise (2007). "Relyatsion ma'lumotlarda kollektiv sub'ektni hal qilish". Ma'lumotlardan ma'lumotni kashf qilish bo'yicha ACM operatsiyalari. Hisoblash texnikasi assotsiatsiyasi (ACM). 1 (1): 5. doi:10.1145/1217299.1217304. hdl:1903/4241. ISSN  1556-4681.
  18. ^ Luo, Ling; Yang, Tsixao; Yang, Pei; Chjan, Yin; Vang, Ley; Lin, Xongfey; Vang, Jian (2017-11-24). Wren, Jonathan (tahr.) "Hujjatlar darajasida kimyoviy taniqli shaxsni tan olish uchun BiLSTM-CRF-ga asoslangan yondashuv". Bioinformatika. Oksford universiteti matbuoti (OUP). 34 (8): 1381–1388. doi:10.1093 / bioinformatika / btx761. ISSN  1367-4803.
  19. ^ Burford, Klint; Qush, Stiven; Bolduin, Timoti (2015). Yagona hujjataro semantik aloqalar bilan hujjatlarni jamoaviy tasniflash. Stroudsburg, Pensilvaniya, AQSh: Kompyuter lingvistikasi assotsiatsiyasi. doi:10.18653 / v1 / s15-1012.
  20. ^ Nikitnik M, Zupan B (2015). "Turli xil tarqatish ma'lumotlarini birlashtirib, genlar tarmog'ining xulosasi". Bioinformatika. 31 (12): i230-9. doi:10.1093 / bioinformatics / btv258. PMC  4542780. PMID  26072487.
  21. ^ Triebel, Rudolph; Mozos, Oskar Martines; Burgard, Volfram (2008). "Joylarni va ob'ektlarni 2D va 3D diapazonli ma'lumotlarda yorliqlash uchun kollektiv tasnif". Ma'lumotlarni tahlil qilish, mashinada o'rganish va qo'llanilishi. Berlin, Heidelberg: Springer Berlin Heidelberg. 293-300 betlar. doi:10.1007/978-3-540-78246-9_35. ISBN  978-3-540-78239-1. ISSN  1431-8814.