Spectral bandits for smooth graph functions with applications in recommender systems

ملخص تقني: خوارزميات "المناديب الطيفية" (Spectral Bandits) للدوال السلسة على الرسوم البيانية

صياغة المشكلة
تتناول هذه الورقة مشكلة "المندوب متعدد الأذرع" (multi-armed bandit) حيث تقابل الأذرع عقد الرسم البياني المعروف $G=(V, E)$، ويتم تحديد العائد المتوقع لسحب ذراع ما من خلال دالة سلسة معرفة على الرسم البياني. في هذا الإطار، يُفترض أن دالة المكافأة $f$ هي توليفة خطية من المتجهات الذاتية لـ "لابلاسيان الرسم البياني" $L$. وتحديداً، إذا احتوت المصفوفة $Q$ على المتجهات الذاتية لـ $L$ كأعمدة، فإن مكافأة العقدة $v$ هي $f_\alpha(v) = \langle x_v, \alpha^* \rangle$، حيث $x_v$ هو الصف رقم $v$ من المصفوفة $Q$ و $\alpha^*$ هو متجه أوزان غير معروف.

ينشأ التحدي الجوهري عندما يكون عدد العقد $N$ (وبالتالي أبعاد فضاء الميزات $D=N$) كبيراً جداً، بحيث قد يتجاوز أفق الزمن $T$ لعملية التعلم ($T < N$). إن خوارزميات "المندوب الخطي" القياسية، التي يرتفع تعقيدها عادةً مع البعد المحيط $D$ أو عدد الأذرع $K$، ستؤدي أداءً سيئاً في هذا النطاق. وتفترض الورقة أن الدالة الحقيقية "سلسة"، مما يعني أن المعاملات $\alpha^*$ المرتبطة بالمتجهات الذاتية ذات القيم الذاتية الكبيرة تكون صغيرة، بينما تكون المعاملات المرتبطة بالقيم الذاتية الصغيرة أكبر.

المنهجية
يقترح المؤلفون خوارزميتين تستفيدان من الخصائص الطيفية للرسم البياني لتحقيق حدود ندم (regret bounds) تتناسب مع "البعد الفعال" $d$ بدلاً من البعد الكامل $N$.

1. البعد الفعال ($d$): تقدم الورقة تعريفاً رسمياً للبعد الفعال $d$ بناءً على نمو القيم الذاتية لـ "لابلاسيان المنتظم" $\Lambda = \Lambda_L + \lambda I$. ويُعرف $d$ بأنه أكبر عدد صحيح يحقق $(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$. يلتقط هذا المقياس عدد الأبعاد "ذات الصلة" في المشكلة، وهو ما يكون عادةً أصغر بكثير من $N$ في الرسوم البيانية الواقعية.

2. خوارزمية SpectralUCB: هي نسخة معدلة من خوارزمية LinUCB. تستخدم مقدراً للمربعات الصغرى المنتظمة لـ $\alpha^*$ باستخدام القاعدة الطيفية. والأهم من ذلك، أنها تبني حدود الثقة للمكافآت المتوقعة باستخدام البعد الفعال $d$ بدلاً من البعد المحيط $D$. تختار الخوارزمية العقدة التي تعظم الحد الأعلى للثقة: $\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$، حيث تعتمد $c_t$ على $d$.

3. خوارزمية Spectral Thompson Sampling (SpectralTS): تستخدم هذه الخوارزمية نهجاً بايزياً. فهي تحافظ على توزيع خلفي (posterior distribution) لـ $\alpha^*$، يتم نمذجته كتوزيع غاوسي $N(\hat{\alpha}_t, v^2 V_t^{-1})$. تم ضبط مصفوفة التباين القبلي (prior covariance) لتكون "لابلاسيان المنتظم" $\Lambda$، مما يعزز الافتراض بأن الدوال السلسة (مكونات القيم الذاتية المنخفضة) هي الأكثر احتمالاً. في كل خطوة، يتم سحب عينة $\tilde{\alpha}$ من التوزيع الخلفي، ويتم اختيار العقدة التي تعظم $x_v^T \tilde{\alpha}$.

المساهمات الرئيسية والنتائج النظرية

• إطار عمل مبتكر: يعد هذا أول عمل يصيغ رسمياً مشاكل "المندوب" حيث تكون العوائد دوالاً سلسة على رسم بياني، مما يربط بين تعلم المانيفولد (manifold learning)/التعلم شبه الموجه وبين التعلم عبر الإنترنت.
• حدود الندم: تثبت الورقة أن كلاً من SpectralUCB و SpectralTS يحققان حدود ندم تراكمي تتناسب مع البعد الفعال $d$:
  • SpectralUCB: $O(d\sqrt{T \ln T})$.
  • SpectralTS: $O(d\sqrt{T \ln N})$.
    تعتبر هذه الحدود هامة لأن $d$ غالباً ما يكون أصغر بكثير من $N$، مما يسمح للخوارزميات بالعمل جيداً حتى عندما يكون $T < N$.
• الكفاءة الحسابية: يسلط المؤلفون الضوء على ميزة حسابية لـ SpectralTS. فبينما تتطلب SpectralUCB حساب حدود الثقة لجميع الأذرع $N$ (مما يؤدي إلى تعقيد $O(N^3)$ لكل خطوة في أسوأ الحالات حيث $D=N$)، تتطلب SpectralTS فقط أخذ عينة من متجه المعلمات وإيجاد القيمة القصوى، وهو ما يمكن القيام به بكفاءة أكبر ($O(N^2)$ لكل خطوة).

النتائج التجريبية
قيم المؤلفون الخوارزميات باستخدام مجموعات بيانات اصطناعية وواقعية:

• البيانات الاصطناعية: استخدام رسوم باراباسي-ألبرت (Barabási-Albert) حيث $N=250$ وكانت دالة المكافأة الحقيقية عبارة عن توليفة خطية من أول 3 متجهات ذاتية أكثر سلاسة. في نطاق $T < N$، تفوقت كل من SpectralUCB و SpectralTS بشكل ملحوظ على نظائرهما الخطية (LinUCB و LinearTS) من حيث الندم التراكمي. كما أظهرت SpectralTS وقتاً حسابياً أسرع.
• البيانات الواقعية: أجريت تجارب على مجموعة بيانات MovieLens (حيث $N=2019$ من الأفلام)، مع نمذجة تفضيلات المستخدم كدالة سلسة على رسم بياني للتشابه تم بناؤه من تقييمات الأفلام. جاءت النتائج مطابقة للنتائج الاصطناعية: حققت الخوارزميات الطيفية ندماً تراكمياً أقل من النماذج الخطية الأساسية. تشير الورقة إلى أنه يمكن تعلم مقدر جيد لتفضيلات المستخدم لآلاف العناصر من خلال عشرات التقييمات للعقد فقط.

الأهمية والادعاءات
تدعي الورقة أنه من خلال استغلال سلاسة الدوال على الرسوم البيانية عبر التفكيك الطيفي، يمكن حل مشكلات التعلم عبر الإنترنت التي تحتوي على عدد كبير من الأذرع دون أن يتناسب الندم سوءاً مع عدد العقد. إن تقديم "البعد الفعال" $d$ يسمح للخوارزميات بالتكيف مع التعقيد الجوهري لبنية الرسم البياني. ينبع العمل من تطبيقات في التوصيات القائمة على المحتوى والإعلانات المستهدفة في الشبكات الاجتماعية، حيث تميل اهتمامات المستخدم أو تفضيلاته إلى التغير بسلاسة عبر العقد المتصلة. ويؤكد المؤلفون أن نهجهم وثيق الصلة بالسيناريوهات التي يكون فيها عدد التفاعلات المتاحة ($T$) صغيراً مقارنة بعدد العناصر المتاحة ($N$).