رفتن به نوشته‌ها

تعبیه گراف در فضای غیراقلیدسی

به نظرم یکی از موضوعات خوب برای پایان‌نامه تعبیه گراف (Graph embedding) است. در کنفرانس NIPS پارسال (۲۰۱۷) یه مقاله بسیار جذاب در ارتباط با تعبیه گراف توسط فیسبوک ارائه شد که دید جدیدی ارائه میداد.

ایده تعبیه گراف (Graph embedding) دقیقا شبیه ورد۲وک است ولی در حوزه علوم شبکه (Network science).

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

دیپ‌واک (deep walk) که با دانش من، اولین مقاله در این زمینه بوده است، هر گره در گراف رو به بردارهایی به طول ثابت تبدیل می‌کند (مثل ورد۲وک که هر کلمه را به برداری به طول ثابت تبدیل میکرد).

 

به طور دقیق‌تر، مقاله دیپ‌واک (deepwalk) یه رندوم واک (Random Walk) روی شبکه میزند و یک سری توالی از نودهای گراف تولید میکند. مثلا از گره شماره ۲۳ شروع میکند و توالی به طول ۵ تولید میکند مثل زیر:

۲۳->۳۳-> ۶۳->۳۰->۱۵

که در توالی بالا مثلا میگه، از نود ۲۳ احتمالا میریم نود ۳۳ بعدش از نود ۳۳ میریم نود ۶۳ و …

این کار رو به ازای تمام گره‌های گراف انجام میدهد تا مجموعه‌ای از توالی‌های متوالی به ازای هر گره بدست آورد.

۲۳->۳۳-> ۶۳->۳۰->۱۵

۱۹->۸->۳۲->۹۰->۳۰->۳۹

۱->۲->۳->۶

سپس این توالی‌ها را به الگوریتم ورد۲وک میدهد و به ازای هر گره یک بردار به دست می‌آورد (در ورد۲وک به ازای هر کلمه یک بردار به دست می‌آرویم در اینجا به ازای هر گره در گراف یک بردار به دست می‌آوریم).  بعد از این بردارها به عنوان بردارهای ویژگی (feature) استفاده میکند و دسته‌بندی‌کننده‌ای (classifier) را آموزش میدهد و سپس به ارزیابی میپردازد. ارزیابی مقاله Deepwalk را روی Multilabel classification انجام داده‌اند و حدس میزنه که فلان گره در شبکه جز کدام کلاس قرار می‌گیرد. در مثال مقاله،‌ از گراف blogCatalog استفاده شده است. در blogCatalog به ازای هر گره در گراف یک سری کلاس مشخص شده است. مثلا نود x در کلاسهای c1  و c2 قرار میگیرد (این کلاس‌ها نوع محتوای اون بلاگ رو مشخص میکنند، مثلا بلاگ فرهنگی، سیاسی، اجتماعی، ورزشی یا …)

شکل بالا، ابتدا گره‌های گراف توسط الگوریتم دیپ‌واک به بردارهای به طول ۱۲۸ نگاشت شدند و سپس توسط الگوریتم TSNE در فضای دو بعدی نمایش داده شده‌اند.

در کارهای قبلی که گراف رو به بردارهای نهفته (vector embedding) تبدیل میکردند مثل دیپ واک (deep walk) یا نود۲وک (node2vec) اغلب به مساله Graph embedding به صورت اقلیدسی فکر میکردند. یعنی چی؟ یعنی معیاری که برای شباهت بین دوتا گره تعریف میشد به صورت خطی بود. یا به طور دقیق‌تر برای اینکه بگن دوتا گره شبیه به هم هستن از روابطی استفاده میکردند که در هندسه اقلیدسی تعریف شده است. هندسی اقلیدسی اون چیزی هست که ما از دبیرستان بهمون یاد دادن و هندسه غیراقلیدسی اون چیزی که در دبیرستان بهمون یاد ندادن :). اون چیزی که ما از دبیرستان یاد داریم این بود که برای اندازه‌گیری فاصله دو نقطه در فضا بیاییم از فرمول زیر استفاده کنیم:

ولی در هندسه غیراقلیدسی (هایبربولیک) فواصل به نحوه دیگری تعریف میشوند که توضیح‌ دقیق‌اش فراتر از این پست است ولی به طور خلاصه میشه گفت از فرمول زیر استفاده میکنند:

 

هندسی غیراقلیدسی خواص بسیار جالبی دارد و این امکان رو به ما میدهد تا ساختارهای سلسله مراتبی (hierarchical structure) رو در بردارهایی با طول بسیار کمتر ذخیره کنیم. چیزی که در هندسه اقلیدسی به دشواری قابل دسترسی است. مثلا در هندسه اقلیدسی برای اینکه یک گراف با branching factor (نرخ رشد گراف بر حس شاخه‌ها) L رو ذخیره کنیم، فضایی که لازم داریم طور نمایی رشد میکند. ولی وقتی همین گراف در فضای غیراقلیدسی میره میشه آن را در فضای خطی (polynomial) ذخیره کرد.

بردارهایی که در فضای اقلیدسی فضای بسیاری میگیرن (مثلا ۴۰۰-۵۰۰ بعد میشن) در فضای غیراقلیدسی در بردارهایی به طول ۱۰-۵ میتونید به همون کیفیت و اندازه برسید. حتی یک مقاله وجود دارد که میگه شما میتونید یک درخت رو در فضای غیراقلیدسی به بردارهایی به طول ۲ ذخیره کنید و در عین حال تمام خاصیت‌های اون رو حفظ کنید (به شرطی که بتونید مقدار دقیق اون بردارها را به دست بیارید). مقاله Pioncare embedding دقیقا از همین ایده کمک گرفته و آمده گراف‌ها رو در فضای غیراقلیدسی به بردارهایی به طول ثابت تبدیل کرده است.

از طرفی یک خاصیت جالب دیگری که فضای غیراقلیدسی وجود دارد این است که ساختار سلسله مراتبی رو ذاتن در داخل خودشون دارند (در مقاله‌ای در ۲۰۱۰ اشاره کردند که شبکه‌های پیچیده ذاتا ساختاری سلسله مراتبی دارند). اینکه بخوایید در فضای اقلیدسی طوری بردارهاتون رو آموزش بدید که ساختار سلسله مراتبی رو بفهند (مثل عبارت زیر) خیلی سخت است.

Gauss->Mathematician->Scientist->Person->Organism->Physical entity-> entity

پس این دوتا ویژگی یعنی وجود ساختار سلسله مراتبی و اشغال فضای کمتر نسبت به فضای اقلیدسی هدف مقاله بالا بود است.

ایده‌های جالبی در این مقاله بالا استفاده شده است که برای کسایی که در حوزه گراف کار میکنند بسیار پیشنهاد میشود و من به طور خلاصه به چندتا از آنها اشاره میکنم:

  • چون در فضای غیراقلیدسی کار کرده است نمیتواند مانند کارهای قبلی (دیپ واک و نود۲وک) از Stochastic Gradient Decent استفاده کند و بخاطر همین از نسخه‌ای متفاوت از SGD به نام Reimannian SGD استفاده کرده است.
  • چون در فضای غیراقلیدسی کار کرده است توانسته است طول بردارها را به شدت کاهش دهد (حدود ۲۰۰۰٪) و در عین حال بسیاری از خواص ساختاری را حفظ کند.
  • بردارهای به دست آمده خاصیت جالبی دارند. گره‌هایی که در مرکز فضا قرار دارند بیشتر خاصیت کلی (general) دارند ولی گره‌هایی که در لبه فضا قرار گرفته‌اند خاصیت جزیی دارند (specific). یعنی همان خاصیت سلسله مراتبی را میتوان در بردارها دید.

  • برای آموزش مدل از تکنیک Negative sampling استفاده کرده‌اند و به ازای هر نمونه مثبت (positive) از ده نمونه منفی (negative) نمونه برداری کرده‌اند.
  • در ارزیابی که انجام داده‌اند، مدل پیشنهادی با برداری به طول ۵ توانسته است به دقت بیشتری نسبت به برداری به طول ۲۰۰ در فضای اقلیدسی دست پیدا کند.

پی‌نوشت: پیاده‌سازی مدل بالا روی gensim وجود دارد و میتونید به راحتی تست‌اش کنید. فعلا در حوزه پردازش زبان (یا به طور کلی downstream task) عملی نیست چون در حین آموزش شبکه بقیه شبکه‌اتون با معیارهای اقلیدسی آموزش میبینن ولی این بردارها با استفاده از فضای اقلیدسی آموزش میبینند که احتمالا خوب کار نمیکنه. ولی یکی از کارهای آتی این مقاله این است که در حوزه NLP این ایده استفاده شود.

منتشر شده در آموزشمتفرقهیادگیری ماشین

اولین باشید که نظر می دهید

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *