نیم‌نگاهی به یادگیری ماشین روی گراف

ماجرا چیست؟

یادگیری ماشین کارِش رو با پردازش اعداد و ارقام شروع کرد؛ بعد ما آدم‌های طمع‌کار راضیش کردیم که از ما متن هم قبول کنه (که در نتیجه علم پردازش زبان طبیعی یا NLP جانی تازه یافت)؛ بعد رفتیم سراغ تصویر و ویدیو (که بینایی ماشین رو متحول کرد).

اما داستان به اینجا ختم نشد. از عنوان نوشته می‌تونید حدس بزنید که گام بعدی چی بوده. بله، پردازش گراف!

البته همون‌طور که بینایی ماشین و پردازش متن پیش از ظهور یادگیری ماشین هم وجود داشتن، گراف‌ها هم دنیای بزرگ خودشونو داشتن و دارن. اما یادگیری ماشین می‌تونه این دنیا رو هم عوض کنه. در این نوشته نیم‌نگاهی به این ماجرا خواهیم داشت.

گاهی گراف یک موجود زنده است!
گاهی گراف یک موجود زنده است!

چند خط درباره گراف

گراف‌ها رو همه جا میشه دید، فقط کافیه بهشون توجه کنیم. هر کجا که چند تا موجودیت با هم ارتباط داشته باشن، یه گراف شکل می‌گیره. اگه این موجودیت‌ها آدم‌ها باشن و ارتباطشون دوستی در شبکه اجتماعی، گراف شبکه اجتماعی رو خواهیم داشت. اگه این موجودیت‌ها کامپیوتر باشن و ارتباطشون لینک‌های شبکه، گراف شبکه کامپیوتری پدید میاد. اگه موجودیت‌ها صفحات وب باشن و ارتباطشون لینک بین این‌ها، گراف وب ایجاد میشه (همون گرافی که گوگل رو پول‌دار کرد) و ...

یه نمونه خیلی ساده از گراف وب در شکل زیر رسم شده. این گراف نشون میده این صفحه‌ی ویرگول و لینکدین به همدیگه لینک دادن، و یه لینک یه طرفه هم از ویرگول به ویکی‌پدیا داده شده.

اما هر گرافی رو میشه با یه زبان ریاضی مشترک نمایش داد و تحلیل کرد. این زبان ریاضی مشترک، نظریه گراف نامیده میشه که موضوع بحث ما نیست. اما برای ادامه این نوشته، فقط کافیه که بدونیم یک گراف رو میشه با یک ماتریس به اسم ماتریس مجاورت نشون داد. این ماتریس مشخص میکنه که کدوم گره‌ها (موجودیت‌ها) در گراف به هم متصل هستن.

به بیان دیگه، ماتریس مجاورت همون گرافه که در قالب اعداد بیان شده و میتونه به عنوان ورودی به یک الگوریتم هوش مصنوعی داده بشه.

مثالی برای اهالی وب

اجازه بدین چند تا از کاربردهای گراف رو هم در قالب همون مثالِ گراف وب مطرح کنم.

یادآوری: در گراف وب هر صفحه اینترنتی میشه یک گره (node) و هر لینک بین دو صفحه میشه یک یال (edge).

  • کلاس‌بندی گره‌ها: اگه همون رویه‌ی معمول در یادگیری ماشین رو دنبال کنیم، میشه بر مبنای اطلاعات یک صفحه (متن و عکس) کلاس‌بندی رو انجام داد (مثلاً محتوای آموزشی داره یا نه). اما اگه با عینک گراف به مسئله نگاه کنیم، میشه بر اساس این که کدوم صفحه‌ها به این صفحه لینک دادن، یا این صفحه به کدوم صفحه‌ها لینک داده، خروجی بهتری گرفت. برای نمونه من در این نوشته چند بار به ویکی‌پدیا لینک دادم، که این اطلاعات میتونه در مسئله کلاس‌بندی گره استفاده بشه.
  • پیش‌بینی لینک: این که بین دو گره لینک وجود داره یا نه، بر اساس دانشی که از گره‌های مشابه به دست اومده، مسئله پیش‌بینی لینک رو تعریف می‌کنه. فرض کنید من یک صفحه جدید در بین میلیاردها صفحه وب ایجاد کردم. چقدر احتمال داره فلان سایت به من لینک بده، میشه یه نمونه از همین مسئله.
  • کلاس‌بندی گراف: در این کاربرد نسبت به دو کاربرد قبلی یکم zoom out می‌کنیم و تمام گراف (یا زیرگراف) رو به عنوان یک رکورد دیتا در نظر می‌گیریم. برای مثال بخشی از گراف وب رو جدا می‌کنیم و به مدل میدیم تا بهمون بگه این بخش از گراف ویژگی مورد نظر ما رو داره یا نه.

شکل زیر از اسلایدهای کورس آقای Jurij Leskovec از دانشگاه استنفورد برداشته شده که یک دوره عالی برای آشنایی با این حوزه است (لینک).

انواع مسائل یادگیری گراف (اسلایدهای کورس دانشگاه استنفورد)
انواع مسائل یادگیری گراف (اسلایدهای کورس دانشگاه استنفورد)

در تلاش برای درک فرزندان

دانش من از مبحث سیستم‌های پیچیده به کتاب محمدرضا شعبانعلی محدود میشه (لینک معرفی کتاب)، و در نتیجه قصد ندارم به این حوزه ورود کنم. اما دلم نمیاد که از اهمیت نظریه گراف در این جهان‌بینی جدید چیزی نگم. چند خط زیر از مقدمه‌ی فصل نانوشته‌ی شبکه‌ها و توپولوژی برداشته شده، که امیدواریم نویسنده فرصت کنه و این فصل رو هم بنویسه.

چند خط از کتاب مقدمه‌ای بر سیستم‌های پیچیده
چند خط از کتاب مقدمه‌ای بر سیستم‌های پیچیده


پس اگه به جملات کتاب استناد کنیم، یادگیری ماشین روی گراف راهی است برای شناخت عمیق‌تر فرزندان پیچیده‌ی ما، از ساختارهای مولکولی و پروتئینی گرفته تا اینترنت و شبکه‌های اجتماعی و زنجیره بلوکی و بی‌‌شمار پدیده جذاب دیگه، بر پایه داده‌هایی که ازشون استخراج کردیم.


و اما یادگیری گراف

گفتیم که گراف رو میشه با ماتریسی از اعداد نمایش داد. اما اکثر مقادیر این ماتریس صفره! چطور؟ گراف شبکه اجتماعی رو تصور کنید. هر کدوم از ما با بخش کوچکی از شبکه در ارتباط هستیم و در نتیجه تعداد یال‌های این شبکه نسبت به کل تعداد یال‌هایی که میشه رسم کرد، ناچیزه.

بنابراین یکی از مهم‌ترین کارهایی که یک مدل یادگیری ماشین برای پردازش گراف باید انجام بده، استخراج یک ماتریس فشرده‌تر از ماتریس مجاورت است که خودِ این فرآیند نیز طبق روال معمول در سایر حوزه‌ها (مثل NLP) بر مبنای داده‌های موجود انجام میشه. شکل زیر یه طرح کلی از این فرآیند رو نشون میده که بهش میگن Node Embedding یا نهفته‌سازی گره‌ها.

نهفته‌سازی گره‌ها (اسلایدهای کورس دانشگاه استنفورد)
نهفته‌سازی گره‌ها (اسلایدهای کورس دانشگاه استنفورد)


اگه علاقه‌مند به یادگیری این شاخه جذاب از علم هستین، کتاب زیر برای خودِ من خیلی آموزنده بود و مطالعه‌اش رو پیشنهاد می‌کنم. اگه منبع ارزشمند دیگه‌ای میشناسین، ممنون میشم در کامنت‌های این مطلب یا پست مربوطه در صفحه لینکدین من معرفی کنید.