استخراج ویژگی‌های سطح پیوند از گراف‌ها برای مدل‌های یادگیری ماشین
1. مقدمه
خلاصه ای از اولین و دومین وبلاگ من از این مجموعه:
این ادامه مجموعه وبلاگ‌های من در شبکه‌های گراف و سومین مقاله از این مجموعه است. این مجموعه با یک مقاله مقدماتی آغاز شد که تعاریف اصلی گره‌ها، لبه‌ها، گراف‌های جهت‌دار و غیرجهت‌دار را برجسته می‌کرد و نمونه‌هایی از مدل‌سازی روابط گرافیکی را برای موارد استفاده مختلف ارائه می‌کرد. این مقاله بر چالش‌های مرتبط با پردازش شبکه‌های گراف در یادگیری ماشینی و یادگیری عمیق تأکید کرد که بر پیچیدگی در مقایسه با پردازش تصویر یا متن (نسبتاً ساده‌تر) تأکید کرد.
مقاله دوم به جزئیات استخراج ویژگی‌های سطح گره از گراف‌ها پرداخت تا بتوان این ویژگی‌ها را به یک مدل یادگیری ماشینی مانند: ماشین بردار پشتیبانی یا جنگل‌های تصادفی یا رگرسیون لجستیک وارد کرد. با انجام این کار، مدل یادگیری ماشین با ویژگی‌هایی غنی می‌شود که توپولوژی گراف را در کنار ویژگی‌های سطح ویژگی توصیف می‌کند. این با بحث مفصلی در مورد مفاهیم شامل: درجه گره، مرکزیت گره، ضریب خوشه‌بندی و گراف‌ها دنبال شد.
در حالی که درجه گره و معیارهای مختلف مرکزیت گره: مرکزیت ارزش ویژه، مرکزیت بین، مرکزیت نزدیکی ویژگی‌های مبتنی بر اهمیت هستند که می‌توانند در پیش‌بینی اهمیت یا تأثیرگذاری گره‌ها در یک گراف استفاده شوند، ویژگی‌های مبتنی بر ساختار مانند ضریب خوشه‌بندی و بردار شمارش گرافلت توپولوژی گره و همسایگی آن را می‌گیرد.
شکل 1: خلاصه مقاله 2 - مفهوم درجه گره - نشان دهنده تعداد لبه‌هایی است که یک گره به آنها متصل است.
شکل 2: خلاصه مقاله 2 - ضریب خوشه‌بندی
بررسی اجمالی این مقاله:
این مقاله در مورد وظایف پیش‌بینی سطح پیوند در یک گراف بحث می‌کند و ویژگی‌هایی را برای وظایف پیش‌بینی سطح پیوند توضیح می‌دهد که می‌توانند برای پیش‌بینی دقیق‌تر از ویژگی‌های سطح ویژگی، به مدل یادگیری ماشینی وارد شوند.
بخش 4 این مقاله در مورد ویژگی‌های مبتنی بر فاصله، ضرایب جاکارد و شاخص Adamic-Adar صحبت می‌کند که معیارهای همسایگی محلی بین یک جفت گره را تشکیل می‌دهند.
بخش‌های 2 و 3 بینشی از پیش‌بینی‌های سطح پیوند و فرمول‌بندی پیش‌بینی سطح پیوند در یک مدل یادگیری ماشین ارائه می‌کنند.
2. وظایف پیش‌بینی سطح پیوند: وظایف پیش‌بینی سطح پیوند چیست؟
وظایف پیش‌بینی سطح پیوند شامل پیش‌بینی پیوندهای جدید در شبکه بر اساس پیوندهای موجود در یک شبکه است. این بدان معناست که در طول استنتاج باید تمام جفت‌های گره‌ای را که به هم مرتبط نیستند، ارزیابی کنیم، آنها را بر اساس احتمال پیوند رتبه‌بندی کنیم و سپس جفت‌های گره “k” برتر را همانطور که توسط الگوریتم یادگیری ماشین پیش‌بینی شده است، قرار است در شبکه رخ دهد اعلام کنیم.
شکل 3: وظایف پیش‌بینی سطح پیوند
اکنون کلید - برای برآورده کردن نیاز فوق - طراحی ویژگی‌های یک جفت گره است. در این مرحله، می‌توان فکر کرد که چرا به وظایف سطح گره (که در مقاله قسمت 2 این سری بحث شد) برگردیم و ویژگی‌های جفت گره‌ها را بر اساس ویژگی‌های گره‌های مجزا به هم پیوند ندهیم و یک مدل یادگیری ماشینی را که بازنمایی ویژگی آموزش دهیم. با این حال، این خیلی سودمند نخواهد بود زیرا رابطه بین گره‌ها به این صورت شکل گرفته نمی‌شود.
شکل 4: چگونه ویژگی‌ها را بین یک جفت گره طراحی کنیم؟
3. تدوین وظایف پیش‌بینی لینک برای آموزش
2 راه وجود دارد که می‌توان وظایف پیش‌بینی پیوند را فرموله کرد:
۱) پیوندهای تصادفی از دست رفته در شبکه: یکی از راه‌ها حذف مجموعه‌ای تصادفی از پیوندها و سپس پیش‌بینی مجدد آنها با استفاده از الگوریتم یادگیری ماشین است. شکل 3 را در زیر ببینید.
۲) پیوندها در طول زمان: نوع دیگر فرمولاسیون جایی است که شما پیوندها را در طول زمان پیش‌بینی می‌کنید. که، اگر یک شبکه گراف مانند یک شبکه استنادی، شبکه اجتماعی یا یک شبکه همکاری داشته باشیم، می‌توانیم به گراف بین t0 و t0’ نگاه کنیم و سپس بر اساس یال‌ها و ساختار گراف تا t0 می‌توانیم خروجی داشته باشیم. یک لیست رتبه‌بندی شده “L”از پیوندهایی که در آینده بین زمان t1 و t1 رخ می‌دهد.
شکل 5: حذف تصادفی پیوندها از شبکه برای آموزش ML
این نوع فرمول برای شبکه‌هایی که در طول زمان تکامل می‌یابند خوب است، در حالی که فرمول‌بندی لینک‌هایی که به‌طور تصادفی از دست می‌روند (همانطور که در بالا توضیح داده شد) برای شبکه‌های استاتیک مانند شبکه پروتئین-پروتئین مفیدتر است.
بنابراین، اکنون با در نظر گرفتن دو فرمول بالا، اجازه دهید اکنون بر روی ارائه توضیحات ویژگی بین جفت گره‌های داده شده تمرکز کنیم.
روش پیش‌بینی لینک:
بنابراین، با توجه به روش، برای هر جفت گره (مثلا x و y)، ما یک امتیاز را محاسبه می‌کنیم - امتیاز با c_bar (x,y) نشان داده می‌شود. به عنوان مثال، همسایه‌های مشترک x و y چه چیزی می‌تواند باشد.
و سپس همه جفت‌ها (x, y) را بر اساس امتیازهای کاهشی c_bar(x,y) مرتب می‌کنیم و سپس جفت‌های “m” را به‌عنوان پیوندهای جدیدی که قرار است در ظاهر شوند پیش‌بینی کنیم. شبکه سپس می‌توانیم ضرر را بر اساس پیوندهایی که واقعاً ظاهر شده‌اند یا نه، محاسبه کنیم.
4. چگونه ویژگی‌هایی را برای پیش‌بینی لینک طراحی کنیم؟
ویژگی‌های سطح پیوند
اکنون می‌خواهیم 3 روش مختلف را در مورد چگونگی ویژگی یا نحوه ایجاد توصیفی از رابطه بین دو گره در یک شبکه مرور کنیم. قصد داریم در مورد:
· ویژگی‌های مبتنی بر فاصله
· ویژگی‌های همپوشانی محله‌های محلی
· ویژگی‌های همپوشانی همسایگی سراسری
شکل 6: طراحی ویژگی‌ها برای پیش‌بینی لینک.
هدف این است که از یک جفت گره معین، می‌خواهیم رابطه بین دو گره را توصیف کنیم تا از طریق رابطه بتوانیم پیش‌بینی کنیم که آیا پیوندی بین دو گره وجود دارد یا خیر.
4.1 ویژگی‌های مبتنی بر فاصله:
این ویژگی بسیار رایج و بسیار شهودی است. ما می‌توانیم در مورد کوتاه‌ترین فاصله مسیر بین دو گره فکر کنیم و آن را در مد مشخص کنیم. بنابراین، اگر گره‌های B و H را داشته باشیم و کوتاه‌ترین فاصله مسیر بین این دو گره 2 باشد یعنی SBH = 2 (Edge BD و Edge DH) همانطور که در شکل 7 زیر نشان داده شده است.
شکل 7: ویژگی مبتنی بر فاصله - کوتاه‌ترین طول مسیر بین گره‌های B و H = 2
به طور مشابه، فاصله بین B و E، A و B، B و G، B و F نیز برابر 2 است که در شکل 7 زیر نشان داده شده است.
شکل 8: ویژگی‌های مبتنی بر فاصله بین برخی از جفت گره‌های دیگر.
با این حال، نکته‌ای که باید به آن توجه کرد این است که کوتاه‌ترین فاصله بین دو گره، میزان همپوشانی همسایگی - قدرت اتصال را نشان نمی‌دهد.
به عنوان مثال، SBH = 2 و گره‌های B و H دارای دو گره مشترک D و C هستند در حالی که B و E و A و B دارای یک چنین گره هستند - همانطور که در شکل 7/شکل 8 در بالا مشاهده شده است.
بنابراین ارتباط بین B و H قویتر از ارتباط بین (B و E) و (A و B) است زیرا بین B و E و A و B فقط یک مسیر و بین B و H دو مسیر وجود دارد.
4.2 همپوشانی محله محلی: ضریب جاکارد
این ما را به مبحث بعدی هدایت می‌کند که «همپوشانی همسایگی محلی» است - که قدرت اتصال را نشان می‌دهد که تعداد همسایگان مشترک بین یک جفت گره را می‌شمارد، یعنی همپوشانی همسایگی محلی تعداد گره‌های مشترک بین دو گره v1 و v2 را نشان می‌دهد.
از نظر ریاضی، برای شمارش همسایگان مشترک بین دو گره v1 و v2، تقاطع گره‌های v1 و v2 را می‌گیریم، یعنی تقاطع دو مجموعه.
همسایه‌های مشترک: بنابراین، همسایه‌های مشترک بین یک جفت گره، گره‌های مشترک بین دو گره را می‌گیرد.
شبکه زیر را در نظر بگیرید:
شکل 9: شبکه مثالی برای محاسبه همسایگان مشترک بین گره A و گره B
همسایگان مشترک:
یک نسخه نرمال شده از این ضریب جاکاردی است که در آن ما تقاطع را می‌گیریم و آن را بر اندازه اجتماع تقسیم می‌کنیم که در زیر نشان داده شده است:
ضریب جاکارد:
معادله: بیان ضریب جاکارد
Union = Neighbors of A + Neighbors of B
بنابراین،
ضریب جاکارد برای جفت گره A و B:
معادله: محاسبه ضریب جاکارد برای جفت گره (A,B)
4.3 همپوشانی محله‌های محلی: شاخص Adamic Adar:
نوع دیگر معیار محله محلی «شاخص آدامیک آدار» است. این در عمل بسیار خوب عمل می‌کند و با نشان داده می‌شود:
معادله شاخص آدامیک آدار
همانطور که از طریق معادله (زیر) مشاهده می‌شود، مجموع تقاطع همسایه‌هایی است که دو گره مشترک دارند تقسیم بر گزارش درجه - یعنی با افزایش درجه گره، اهمیت کاهش می‌یابد.
این منطقی است - یعنی اگر دو گره داشته باشید که همسایه‌های مشترکی داشته باشند که درجه پایینی دارند، بهتر از داشتن افراد مشهور به عنوان مجموعه‌ای از همسایگان مشترک است. با این حال، انتخاب یک ویژگی مناسب نیز توسط مورد استفاده در نظر گرفته می‌شود.
مثال - برای همان شبکه شکل 9:
4.4 محدودیت همپوشانی همسایگان محلی:
مشکل همپوشانی همسایگان محلی eh این است که اگر دو گره یک گره مشترک نداشته باشند، متریک همیشه 0 برمی‌گرداند.
به عنوان مثال، اگر باید همپوشانی همسایگان محلی بین گره‌های A و E را همانطور که در شبکه زیر نشان داده شده است محاسبه کنیم:
شکل 10: همپوشانی همسایگی محلی جفت گره A و E = 0
همپوشانی محله محلی در این مورد همیشه به عنوان "0" تنظیم مجدد میرشود. با این حال، این گره‌ها ممکن است در آینده متصل شوند. برای رفع این مسئله، همپوشانی همسایگی جهانی را تعریف می‌کنیم که این مسئله را حل می‌کند - متریک در اینجا متریک کاتز است که تعداد مسیرهای تمام طول‌های بین یک جفت گره معین را همانطور که در زیر بخش زیر توضیح داده شده است، می‌شمارد.
4.5 محاسبه همپوشانی همسایگی سراسری: ضریب کاتز
در مرحله بعد، سوال این است که چگونه تعداد مسیرهای یک طول معین را بین 2 گره مختلف محاسبه کنیم - این می‌تواند به زیبایی با استفاده از توان‌های ماتریس مجاورت گراف محاسبه شود. یعنی: محاسبه تعداد مسیرهای بین دو گره به قدرت‌های محاسباتی ماتریس Graph Adjacency کاهش می‌یابد - یعنی ماتریس Graph Adjacency را گرفته و در خود ضرب می‌شود.
اثبات این موضوع در اینجا بحث نشده است.
با استفاده از شاخص کاتز، می‌توانیم تعداد مسیرها را با تمام طول‌ها بین یک جفت گره بشماریم. برای محاسبه تعداد مسیرهای بین 2 گره، از قدرت های ماتریس مجاورت استفاده می کنیم:
· Auv تعداد مسیرهای به طول 1 (همسایگی مستقیم) بین u و v را مشخص می‌کند.
· Auv^2 تعداد مسیرهای به طول 2 (همسایه همسایه) بین u و v را مشخص می‌کند.
· Auv^ l تعداد مسیرهای با طول l را مشخص می‌کند.
5. خلاصه - ویژگی‌های سطح لبه
بنابراین، برای ویژگی‌های مبتنی بر لبه 2 گره، موارد زیر را مورد بحث قرار داده‌ایم:
۱) ویژگی‌های مبتنی بر فاصله: این از کوتاه‌ترین مسیر بین گره‌ها استفاده می‌کند اما همپوشانی همسایگی را نشان نمی‌دهد.
۲) همپوشانی محله محلی: این از معیارهایی مانند ضریب جاکارد استفاده می‌کند که محاسبه می‌کند گره چند همسایه مشترک دارد.
۳) همپوشانی همسایگی جهانی: این شاخص کاتز است که مسیرهای تمام طول‌ها را بین یک جفت گره با استفاده از توان‌های ماتریس مجاورتی که در بالا توضیح داده شد محاسبه می‌کند.
استخراج ویژگی‌های سطح گره از شبکه‌های گراف برای مدل‌های یادگیری ماشین
۱. مقدمه
این ادامه مجموعه وبلاگ‌های من در شبکه‌های گراف و دومین وبلاگ از این مجموعه است. مقاله اول برخی از مفاهیم مقدماتی برجسته شامل آناتومی یک گراف مانند: گره‌ها، لبه‌ها و تعریف گراف‌های جهت‌دار و غیر جهت‌دار را پوشش داد. این مقاله همچنین به جزئیات نمایش عددی یک گراف/مفهومی از: ماتریس مجاورت، فهرست لبه، فهرست مجاورت پرداخت. شبکه‌های گراف جالبی مانند - گراف‌های دو طرفه و شبکه‌های تا شده نیز در مقاله اول این مجموعه مورد بحث قرار گرفتند. برخی از این موارد در شکل تلفیقی زیر نشان داده شده است:
شکل: مروری بر بحث‌های مقاله اول مجموعه
در این مقاله (دومین مجموعه من در شبکه‌های گراف)، اکنون به بررسی روش‌های سنتی یادگیری ماشین در گراف‌ها می‌پردازیم. به طور خاص، قصد داریم در مورد چگونگی استخراج ویژگی‌های ساختاری از یک گراف برای موارد مختلف استفاده از یادگیری ماشین مانند:
۱) موارد استفاده پیش‌بینی سطح گره.
۲) موارد استفاده پیش‌بینی سطح لبه – که جفت‌های گره را در نظر می‌گیرد و سعی می‌کند پیش‌بینی کند که آیا گره‌ها متصل هستند یا خیر.
۳) و سپس در مورد موارد استفاده از سطح گراف صحبت خواهیم کرد، جایی که می‌خواهیم کل گراف را پیش‌بینی کنیم.
ادامه مطلب ...
مقدمه‌ای بر شبکه‌های گراف
۱. گراف چیست و چرا گراف؟
گراف‌ها یک زبان عمومی برای توصیف و تجزیه و تحلیل موجودیت‌ها با روابط و تعاملات هستند. این بدان معنی است که به جای اینکه یک دامنه را به عنوان نقاط داده خاص در نظر بگیریم، می‌توانیم آن را از نظر شبکه‌ها و روابط بین موجودیت‌ها در نظر بگیریم. این بدان معنی است که یک گراف زمینه‌ای از رابطه بین موجودیت‌ها وجود دارد. ساختار گراف رابطه بین موجودیت‌ها را همانطور که در شکل زیر نشان داده شده است نشان می‌دهد.
شکل: گراف شبکه – موجودیت‌های مرتبط با یکدیگر مطابق با اتصالات
ادامه مطلب ...
یک رویکرد یادگیری لایه‌ای برای مقیاس‌گذاری در سیستم‌های دسته‌بند یادگیری برای مسائل بولی
محاسبات تکاملی (EC) اغلب دانش آموخته شده را به عنوان بازنشانی برای هر مسئله جدید مورد بررسی قرار می‌دهد. برعکس، انسان‌ها می‌توانند از مسائل در مقیاس کوچک درس بگیرند، این دانش را حفظ کنند (به‌علاوه عملکرد)، و سپس با موفقیت دوباره از آنها در مقیاس بزرگ‌تر و/یا مسائل مرتبط استفاده کنند. پیوند راه‌حل‌ها با مسائل از طریق یادگیری لایه‌ای به دست آمده است، جایی که یک آزمایشگر یک سری مسائل مرتبط ساده‌تر را برای حل یک کار پیچیده‌تر تنظیم می‌کند. کارهای اخیر بر روی سیستم‌های دسته‌بند یادگیری (LCS) نشان داده است که استفاده مجدد از دانش از طریق پذیرش قطعات کد، برنامه‌های درختی مانند GP، قابل قبول است. با این حال، استفاده مجدد تصادفی ناکارآمد است. بنابراین، سوال تحقیق این است که چگونه LCS می‌تواند یک چارچوب یادگیری لایه‌ای اتخاذ کند، به طوری که مسائل پیچیده‌تر را می‌توان به طور کارآمد حل کرد. یک LCS (به نام XCSCF*) توسعه یافته است تا شامل بدیهیات پایه مورد نیاز برای یادگیری، روش‌های تصفیه شده برای انتقال یادگیری و بازنویسی یادگیری به عنوان تجزیه به یک سری مسائل فرعی باشد. این مسائل فرعی را می‌توان به عنوان یک برنامه درسی توسط معلم تنظیم کرد، اما این بدان معنا نیست که یک عامل می‌تواند از آن درس بگیرد. به خصوص اگر فقط دانش بیش از حد برازش هر مسئله را به جای الگوها و توابع مقیاس پذیر زیربنایی استخراج کند. نتایج نشان می‌دهد که از یک جدول معمولی، که تنها با یک مفهوم مبهم از اینکه کدام مسائل فرعی ممکن است مرتبط باشند، XCSCF* منطق کلی پشت حوزه‌های آزمایش‌شده را به تصویر می‌کشد و بنابراین می‌تواند هر n-bit Multiplexer، n-bit Carry-one، n-bit Majority-on، و n-bit Even-parity را حل کند. این کار گامی را به سوی یادگیری مستمر نشان می‌دهد زیرا دانش آموخته شده به طور موثر در مسائل بعدی مورد استفاده مجدد قرار می‌گیرد.
روابط بین اعضا در الگوریتم تکاملی
در مطالعات الگوریتم‌های تکاملی، معمولاً روابط بین اعضا نادیده گرفته می‌شود. برخی از تلاش‌ها بر روابط بین زیر مجموعه‌های جمعیت متمرکز شده است. تمرکز ما بر بررسی روابط بین اعضا است، و می‌پرسیم در طول زمان چه اتفاقی برای ویژگی‌های ساختاری شبکه‌هایی می‌افتد که جمعیت‌های در حال تکامل را نشان می‌دهند. مطالعه شبکه‌ها به دلایل زیر مهم است:
(1) شبکه‌ها روابط بین اعضا را در نظر می‌گیرند (از طریق وجود لبه‌ها و طول آنها)،
(2) شبکه‌ها برای به تصویر کشیدن انواع دیگر روابط نیز مناسب‌تر هستند، مانند به عنوان پیوندهای اجدادی، و
(۳) شبکه‌ها مدل‌های مفیدی از روابطی را ارائه می‌دهند که گونه‌های بیولوژیکی به اشتراک می‌گذارند.
بازنمایی‌های شبکه‌ای از نمونه‌های شناخته شده الگوریتم‌های تکاملی، به‌عنوان مثال، الگوریتم‌های ژنتیک با کد واقعی، بهینه‌سازی ازدحام ذرات، و سیستم‌های دسته‌بند یادگیری را با استفاده از گره‌ها در شبکه برای بازنمایی اعضا در جمعیت، برای مسائل بهینه‌سازی معیاری که توسط بسیاری از محققان مورد مطالعه قرار گرفته است، اعمال می‌شود.
ادامه مطلب ...