Ինչու է գրաֆների տեսությունն այդքան զիլ

Ի՞նչ է գրաֆը

Գիտության ցանկացած բնագավառի մասնագետի հարցրեք՝ թէ ինչպես է աշխատում իր հետազոտթյունների առարկան հանդիսացող համակարգը: Հավանաբար նա կառաջարկի դիտարկել իր մեջ արդեն իսկ գոյություն ունեցող ներքին կապեր ներառող որոշակի համակարգ: Դա կարող է լինել մարդու մարմինը, էկոհամակարգի սննդի շղթան, քիմիական ռեակցիան կամ աասարակությունն ամբողջությամբ: Առանց ուսումնասիրելու և հասկանալու էկոհամակարգի մեջ՝ կենդանիների, մոլեկուլների մեջ՝ ատոմների կամ օրգանիզմի մեջ բջիջների և հյուսվածքների, միմյանց միջև փոխազդեցությունները, դուք պարզապես կստանաք ինֆորմացիայի կույտ:

Մեքենայական ուսուցման ավանդական մոդելները հաճախ տվյալներ են քաղում հետևյալ կերպ. ցուցակներից կամ աղյուսակներից վերցվում են միավոր ինֆորմացիա և մշակում դրանք (այս գործընթացի մանրամասները կախված են օգտագործվող ալգորիթմից, ինչպես նաև մի քանի այլ պարամետրերից): Այսպես են արվում տարբեր կանխատեսումներ: Այնուահանդերձ, որոշ խնդիրներ լուծվում են ավելի արդյունավետ եղանակներով:

Գրաֆները տվյալների կառուցվածքներ են, որոնք ներկայացնում են դրանցում պարունակվող տվյալների ցանցերը կամ դրանց միջև փոխհարաբերությունները: Սովորաբար դրանք ներկայացված են որպես հանգույցներ կամ «գագաթներ» և գծեր կամ «կողեր»:

Նկար 1-ը ցույց է տալիս «չկողմնորոշված կամ չուղղորդված գրաֆի» օրինակ, որում տվյալները երկկողմանի կապ ունեն այլ տվյալների հետ: Այս գրաֆիկի յուրաքանչյուր հանգույց ներկայացնում է սոցիալական ցանցի օգտվող, որի բոլոր անդամները կապված են միմյանց հետ: Այս ձևով դուք կարող եք ներկայացնել սոցիալական կայքերը, ինչպես օրինակ՝ LinkedIn-ը, որտեղ, կապվելով որևէ մեկի հետ, դուք դառնում եք կապված նրա ցանցի օգտատերերի հետ: Կողմնորոշված (ուղղորդված) գրաֆի օրինակ է Twitter սոցիալական ցանցը, որի օգտվողները հետևում են միմյանց (և ոչ միշտ փոխադարձաբար):

Օգտատերերի նկարները, որոնք ասոցացնում են նրանց տվյալները, կոչվում են հանգույցներ կամ գագաթներ, իսկ դրանք միացնող գծերը՝ կողեր: Գագաթների միջև կապի ինտենսիվությունը փոխանցվում է գծերի միջոցով.

• կետագծերը ցույց են տալիս թույլ կապերը, ինչպես օրինակ «ամեն ինչ կամ ոչինչ», այսինքն՝ դու հետևում ես մեկին, թե՝ ոչ
• հոծ գծերն արտահայտում են «հավասարակշռված» հարաբերություններ, այսինքն՝ ներկայացնում են երկու օգտագործողների հարաբերություններում ներգրավվածության ավելի բարձր մակարդակ

Դուք, հավանաբար, հիմա նույնն եք զգում, ինչ ես, երբ առաջին անգամ ինֆորմատիկայի դասին ծանոթացա գրաֆների և գրաֆների տեսության հետ` ձանձրալի և ոչ այնքան պարզ: Բայց ես լավ լուր ունեմ. քննարկվող թեման հասկանալու համար անհրաժեշտ հիմնական տերմիններին ծանոթանալուց հետո մենք անցնում ենք ավելի հետաքրքիր հարցերի: Ի՞նչու են գրաֆներն այդքան կարևոր և ինչն է դրանց դարձնում այդքան հիանալի:

Եվ այսպես, ինչի՞ հետ մենք գործ ունենք

Գրաֆներն արդեն կիրառվում են ինֆորմատիկայի բնագավառում` բավականին հիանալի ծրագրեր ստեղծելու համար: Google Maps-ը, օրինակ, օգտագործում է գրաֆներ` վայրերի և դրանք միացնող փողոցների մասին տվյալները պահելու համար: Նույն հավելվածում ամենակարճ հեռավորության ալգորիթմները օգտագործվել են վերջնակետին հասնելու ամենակարճ ճանապարհը գտնելու համար:

Բայց սա դեռ ծաղիկներ են, հատապտուղները կլինեն այն ժամանակ, երբ մենք կսկսենք դիտարկել գրաֆների կիրառումը մեքենայական ուսուցման մեջ: Քանի որ գրաֆները ցույց են տալիս տվյալների կտորների միջև բազմակողմանի կապերը (ի տարբերություն տվյալների դասավորված ցուցակների կամ տենզորների, որոնք քիչ բան են ասում մեծությունների կամ օբյեկտների միջև փոխհարաբերությունների մասին), մենք կարող ենք դրանք օգտագործել բարդ վերլուծություններ կատարելու և դրանց հիման վրա կանխատեսումներ անելու համար:

Գրաֆների տեսություն & մեքենայական ուսուցում. ինչպե՞ս

Նախքան մեքենայական ուսուցման և գրաֆի տանդեմից օգտվելը, մենք պետք է ներկայացնենք մեր կապերը, որպեսզի համակարգիչը, իսկ հետո մեքենայի ուսուցման ալգորիթմը, հասկանա դրանք:

Սովորաբար գրաֆները կարող են ներկայացվել երեք հիմնական եղանակներից մեկով:

1. Հարևանության հարաբերություն/մատրիցա

Հարևանության մատրիցի իմաստը բացահայտված է իր իսկ անվան մեջ՝ տարբեր հանգույցների միջև կապերը կամ կողերը ներկայացված են մատրիցային բջիջների միջոցով: Առավել լավ պատկերացնելու համար ասվածը, դիտարկենք հետևյալ օրինակը.

Այս մատրիցան կօգնի գտնել երկու հանգույցների միջև կողը ըստ մատրիցայում նշումների հատման: Եվ ակնհայտ կարող ենք տեսնել, որ 1 հանգույցը ինքն իր հետ կապված չէ, բայց կապված է 2 հանգույցի հետ:

2. Կցության մատրից

Կցության մատրիցը (կողերի ցանկ) մեր ցանցը կամ գրաֆը ներկայացնելու հաշվարկային հարաբերակցությամբ ներկայացնելու եղանակ է: Դա կարող ենք դիտարկել ստորև բերված օրինակում.

3. Հարևանության ցուցակ

Հարևանության ցուցակները համատեղում են վերը նշված երկու մոտեցումները՝ ներկայացնելով հանգույցների ցուցակ, որոնք առնչվում են այն բոլոր հանգույցների ցանկին, որոնց դրանց անմիջականորեն կից են: Սա պարզաբանելու համար դիտարկենք օրինակ.

Վերոնշյալ երեք մոտեցումների միջոցով մենք կարող ենք հաղթահարել մեր կոդում գրաֆները հաշվարկային տեսքով ներկայացնելու դժվարությունները: Այնուամենայնիվ, գրաֆները մեքենայական ուսուցման մոդելների մեջ են ներդնելու համար դեռևս որոշ խնդիրներ կան: Ավանդաբար, խորը ուսուցման մոդելները լավ են մծակում տվյալներ, որոնք զբաղեցնում են որոշակի ֆիքսված ծավալ և միակողմանի են: Գրաֆները, անկախ նրանից, թե ինչպես ենք դրանք ներկայացնում, չեն զբաղեցնում հիշողության որոշակի ծավալ և անընդհատ չեն, ավելի շուտ յուրաքանչյուր հանգույց պարունակում է հղում այն ​​հանգույցներին, որոնց ուղղակիորեն հարակից է:

Այս մարտահրավերներին դիմակայելու իսկապես հրաշալի եղանակներ կան, որոնց ավելի խորը կանդրադառնանք հետագա հոդվածներում: Առայժմ, կառաջարկեմ մի քանի ռեսուրս՝ ինքնուրույն հետազոտելու համար, որտեղ բավականին հետաքրքիր վերլուծություններով ներկայացված են մեքենայական ուսուցման խնդիրները լուծելու նոր ուղիներ:

• Learn about Deep Learning on Graphs with Graph Convolutional Networks
• Learn about DeepWalk — a project finding another way to represent graphs for machine learning

Գրաֆների տեսություն և մեքենայական ուսուցում. ի՞նչ կարող ենք անել դրանց հետ

Վակուումի մեջ ոչինչ չկա, ամեն ինչից անկախ ոչինչ ևս: Տվյալների փոխկապակցված ցանցերի ըմբռնումը, որոնք կազմում են գրեթե բոլոր գիտական ոլորտների հիմքը, տալիս է շատ ու շատ հարցերի պատասխանելու հուզիչ ներուժ.

• Ի՞նչպես ավելի մանրամասն ուսումնասիրել մարդու ուղեղը:
• Ի՞նչպես կանխատեսել էկոհամակարգի վրա ինչ-որ խթանի կամ փոփոխության ազդեցության հետևանքները:
• Ինչպե՞ս որոշել, թե որ միացությունները առավել հավանական ելքով թույլ կտան արդյունավետ դեղամիջոց ստեղծել:

Վերջապես՝ ամենահետաքրքիրը. մեր սովորածի ամենալավ մասն այն է, որ մենք կարող ենք, և դա պարզապես տեսական հնարավորություն չէ, այլ այն, ինչ մենք անում ենք հենց հիմա: Գրաֆների տեսությունն օգտագործվում է հետևյալ ոլորտներում.

1. Ախտորոշիչ մոդելավորում (որոշակի վստահությամբ կանխատեսել՝ ունի արդյոք հիվանդը կոնկրետ ախտորոշում, թե՝ ոչ).
2. Օգնություն քաղցկեղով հիվանդների ախտորոշման և բուժման հարցում.
3. Դեղերի և դեղամիջոցների մշակում.
4. Էկոլոգիայի և էվոլյուցիայի տեսությունները համատեղելու ուղիների որոնում.

Ինչպե՞ս է աշխատում գրաֆների տեսությունը

Եկեք մի փոքր խորանանք գրաֆների տեսության կիրառման ոլորտներում: Որպես օրինակ վերցրեք ախտորոշիչ մոդելները: Մասնավորապես, ես առաջարկում եմ դիտարկել ուղեղի ցանցի վերլուծության օրինակ, որն օգտագործվում է հիվանդների մոտ իրական կամ պոտենցիալ շիզոֆրենիա բացահայտելու համար:

Գրաֆների օգնությամբ նյարդաբանները կարող են համադրել շիզոֆրենիայի ախտորոշման հետ կապված հիմնական բացահայտումներն ու արդյունքները: Ընդ որում, հաշվի է առնվում խանգարման առաջացման որոշ նշաններ.

• պակաս արդյունավետ լարային ցանցեր
• ավելի քիչ տեղային խմբավորում/կլաստերիզացիա
• ավելի քիչ հիերարխիկ կազմ

Այս մարկերների հիման վրա մենք կարող ենք պոտենցիալ գնահատել այս ցանցերը՝ օգտագործելով մեքենայական ուսուցման ալգորիթմ և կանխատեսել հավանականությունը, որ հիվանդը ունի կամ նրա մոտ զարգանալու է շիզոֆրենիա:

Առանց հասկանալու այդ ցանցերը, այս տեսակի ախտորոշումը դառնում է բոլորովին այլ նյարդաբանական վերլուծություն: Շիզոֆրենիայի հետազոտությունների խոստումնալից հայտնագործությունները խոստումնալից հետևանքներ ունեն խանգարման հայտնաբերման և բուժման համար` վաղ ախտորոշում և միջամտություն, որոնք դուրս են գալիս ախտանիշների պարզ գնահատման սահմաններից:

Սա ընդամենը մեկ օրինակ է, բայց այն ամբողջությամբ պատկերում է մեքենայական ուսուցման մեջ գրաֆների տեսության առավելությունները, քանի որ այն հատվում է այլ գիտությունների հետ, թույլ տալիս լուծել ամենատարբեր բնագավառներից տարատեսակ խնդիրներ:

Բանն այն է, որ մեր տվյալները հաճախ պարունակում են շատ ավելի շատ ինֆորմացիա, քան մենք կարող ենք պատկերացնել` ցուցակների, տվյալների շրջանակների կամ տենզորների տեսքով: Այո, մենք ունենք տվյալներ ուսումնասիրելու և դրանք այնպես ներկայացնելու եղանակներ, որ կարող ենք ենթադրել հարաբերությունները և նույնիսկ թույլ տալ, որ մեր ալգորիթմները կանխատեսեն դրանք: Բայց երբ մենք սովորում ենք այլ կերպ կապել մեր տվյալները, կարող ենք հասնել ավելիին:

Հասկանալով, թե ինչպես են իրերը փոխկապակցված միմյանց միջև, մենք դրանք ավելի լավ ենք հասկանում: Մենք կարող ենք ավելի համապարփակ կանխատեսումներ անել և պատասխանել շատ կարևոր արդյունքներով ավելի բարդ հարցերի` որոնք կարող են փոխել մեր կյանքը:

Սկզբնաղբյուր՝ Why Graph Theory Is Cooler than You Thought