Hamoon
Hamoon
خواندن ۵ دقیقه·۲ سال پیش

Information Retrieval System(recommendation system)




در این پست می‌خوایم خیلی کلی این سرویس رو بررسی کنیم.توییتر رو به جرات میشه اصلی‌ترین مرکز مکالمات امروز در جهان قلمداد کرد. این یعنی این پلتفرم به راحتی می‌تونه با نمایش یا عدم نمایش بعضی توییت‌ها به برخی افراد، جریان اطلاعات، اخبار، نگرانی‌ها، بحث‌ها و حتی کامیونیتی‌ها رو در جهتی که می‌خواد هدایت کنه و تاثیر جدی بر روی افکار و سلائق عمومی و اجتماعی بذاره. در چنین شرایطی، شفافیت (Transparency) و توضیح‌پذیری (Explainability) اهمیت پیدا می‌کنند به‌طوری‌که هرلحظه می‌تونن تمام اعتبار پلتفرم رو از بین ببرن. دقیقا به همین دلیل هم هست که توییتر تصمیم به اوپن‌سورس کردن #سامانه‌_بازیابی_اطلاعات (Information Retrieval System) خود یا همون ریکامندر سیستمش گرفته.این سیستم در واقع اصلی‌ترین بخش الگوریتمی توییتر است و بقیه‌ی بخش‌های پلتفرم عمدتا تمرکز بر چالش‌های مهندسی مثل Availability و Scalability دارند نه الگوریتمی.زمانی که اپلیکیشن توییتر رو باز می‌کنید، یک تب اصلی (For You) داره که تا حدی صفحه‌ی Home اپلیکیشن به حساب میاد و توییت‌هایی رو در قالب یک تایم‌لاین به شما نشون می‌ده. نیمی از این توییت‌ها معمولا از افرادی اند که شما فالو نمی‌کنید و حتی نمیشناسید اما جالب اینجاست که کم پیش میاد توییت کسی که همیشه فالو می‌کنید رو نبینید یا توییت‌هایی رو ببینید که براتون جالب نباشه و بخواید که اپ رو ببندید. این هنر سامانه بازیابی اطلاعات یا همون ریکامندر توییتره.هر بار که این صفحه رو تا انتها اسکرول می‌کنید، یک درخواست از اپ شما به سرویس Home Mixer روی سرور توییتر زده می‌شود (روزانه حدود ۵ میلیارد درخواست) و به صورت میانگین، حدود ۱/۵ ثانیه بعد، در پاسخ، لیستی ترکیب (Mix) شده از توییت‌های جدید، تبلیغات، پیشنهاد برای فالو کردن افراد و … را دریافت می‌کنید. اما این سیستم چطور می‌تواند ازبین میلیاردها توییت!!!! (روزانه تقریبا ۵۰۰ میلیون توییت)، یک تعداد کم از توییت‌های مناسب رو برای شما بازیابی کند؟! اگر قرار است اندازه‌ی ورودی یک الگوریتم فیلتر‌سازی انقدر بزرگ باشد، طبیعتا نباید قادر باشیم از الگوریتم‌های قدرتمند با پیچیدگی زمانی (Time Complexity) زیاد استفاده کنیم.همه‌ی ریکامندر سیستم‌ها (ازجمله توییتر) برای غلبه بر این مشکل، فرایند بازیابی رو به ۲ یا ۳ مرحله (stage) می‌شکنند. در فاز اول که بهش candidate generation و یا candidate sourcing و یا retrieval گفته می‌شه، یک الگوریتم فیلترسازی بسیار بسیار ساده (با پیچیدگی زمانی کم) از بین میلیاردها آیتم، در حد چندهزارتا که می‌توان به سادگی مطمئن شد کاندیدای مناسب و غیر پرتی اند را فیلتر می‌کند. این کاندیدها در مرحله دوم (Ranking) به یک الگوریتم بسیار پیچیده و سنگین داده می‌شوند و چون در حد چندهزار آیتم اند به راحتی و با سرعت رتبه‌بندی می‌شوند. توییتر هر بار ۱۵۰۰ آیتم کاندید را از بین ۳ منبع (source) اطلاعاتی، بازیابی و کاندید می‌کند (از هر منبع ۵۰۰ آیتم به عنوان کاندید بازیابی می‌شود). این سه منبع اطلاعاتی عبارتند از:




۱. فضای Embedding: در الگوریتم‌های یادگیری ماشین، سعی بر این است که همه کانسپت‌ها (کاربرها، توییت‌ها، کامیونیتی‌ها و …) رو با بردارهای متراکم عددی به نام embedding vector بازنمایی کنیم بطوریکه کاربران شبیه به هم بردارهای شبیه به هم، توییت‌های شبیه به هم بردارهایی شبیه به هم و همینطور کاربر علاقه مند به یک توییت‌ هم برداری شبیه به بردار آن توییت داشته باشد. توییتر ۲ فضای embedding جداگانه به نام‌های SimClusters و TwHIN دارد. در فضای SimClusters با استفاده از روش Matrix Factorization بردارهای embedding با مرکزیت افراد influencer مثل خواننده ها و … خوشه بندی می‌شوند (۱۴۵ هزار خوشه که هر ۳ هفته یک بار آپدیت می شوند)۵۰۰ توییت که بردار embedding مشابه با بردار کاربر دارند، از این منبع استخراج می‌شوند.




۲. منبع Social Graph: توییت‌های مربوط به افرادی که شما فالو نمی‌کنید ولی فالورهای شما یا افراد شبیه به شما فالو می‌کنند یا با آن تعامل (لایک، ریتوییت و …) دارند. لازم به ذکر است دیتای رابطه‌ی فالو کردن افراد، در یک گراف جهت‌دار به‌نام Follow graph نگه‌داری میشود که گره‌های آن، نمایانگر کاربران و یال‌های آن نمایانگر فالوها اند.



۳. منبع In Network: توییت‌های مربوط به افرادی که شما فالو می‌کنید و به‌صورت مستمر با توییت‌های آن‌ها در تعامل هستید. این منبع از یک مدل ساده دیگر به نام RealGraph که بر روی Follow graph سوارشده و احتمال تعامل دونفر را پیش‌بینی می‌کند، به همراه یک مدل logistic regression برای ranking استفاده می‌کند.

  • برای اطلاعات بیشتر در مورد مدل RealGraph به مقاله زیر رجوع کنید:https://www.ueo-workshop.com/wp-content/uploads/2014/04/sig-alternate.pdf

از هر کدام از این منابع به کمک الگوریتم بسیار ساده‌ی Logistic Regression تعداد ۵۰۰ کاندید (در مجموع ۱۵۰۰ توییت) انتخاب شده و وارد فاز ranking می‌شوند.در فاز ranking به کمک یک شبکه عصبی عمیق و پیچیده با حدود ۴۸ میلیون پارامتر و هزاران فیچر ورودی، که به صورت continuous آموزش می‌بیند (سرویس Heavy Ranker)، تعداد ۱۰ امتیاز مجزا (multi-task learning) برای engagement های مختلف (لایک، ریپلای، ریتوییت و …) محاسبه شده و توییت‌ها بر اساس این score ها رتبه‌بندی می‌شوند.معمولا ریکامندر سیستم‌ها به جز فازهای candidate sourcing و ranking یک فاز سوم هم دارند که با روش‌های شهودی، هیوریستیک و سنتی‌تر (غیر هوشمند) ملاحضات کسب و کار رو اعمال می‌کنن مثلا وزن آیتم‌های اسپانسر رو بیشتر می‌کنیم یا آیتم‌هایی که کاربر قبلا دیده رو حذف می‌کنن و …توییتر هم در فاز سوم (که بهش Heuristics & Filters میگه) توییت‌هایی که قبلا دیده شده یا توییت افراد mute یا بلاک شده را حذف می‌کند (Visibility Filtering)، توییت‌هایی که مربوط به افرادی اند که بیش از ۲ درجه جدایی با شما در follow graph دارند، حذف می‌شوند (Social Proof)، امتیاز توییت‌هایی که با فیدبک منفی شما روبرو شده اند کم می‌شود (Feedback-based Fatigue)، مطمئن می‌شود که نیمی از توییت‌ها مربوط به افراد In Network و نیمی مربوط به افراد Out of Network باشند (Content Balance)، مطمئن می‌شود که فید شما با توییت‌های یک شخص خاص پر نشده باشد (Author Diversity) و …

اطلاعات بیشتر:https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm

کدها:https://github.com/twitter/the-algorithmhttps://github.com/twitter/the-algorithm-ml

Social Proofشبکه عصبیکسب و کاریادگیری ماشینinformation retrieval system
شاید از این پست‌ها خوشتان بیاید