Low Rank Matrix Factorization

برداری کردن الگوریتم فیلتر کردن مشترک

راه دیگر نوشتن داده‌های جدول زیر

فیلم	آلیس (1)	باب (2)	کارول(3)	دیو(4)
Love at Last	5	5	0	0
Romance Forever	5	؟	؟	0
Cute Puppies of Love	؟	4	0	؟
Nonstop Car Chases	0	0	5	4
Sword Vs. Karate	0	0	5	0

به صورت ماتریسی است:

$$ Y = \begin{bmatrix} 5 & 5 & 0 & 0 \\5 & ? & ? & 0 \\? & 4 & 0 & ?\\0 & 0 & 5 & 4 \\0 & 0 & 5 & 0\end{bmatrix} $$

هر ستون مربوط به نمره‌های یک کاربر است که به فیلم‌های مختلف داده و هر سطر نمره‌های یک فیلم است که از کاربرهای مختلف دریافت کرده است.

در حقیقت هر عنصر ماتریس $$Y$$ همان $y^{(i,j)}$ ها هستند. یعنی نمره فیلم $$i$$ توسط کاربر $$j$$ . اگر نمره پیش‌بینی شده برای یک فیلم توسط الگوریتم با $(\theta^{(j)})^Tx^{(i)}$ داده شود، ماتریس $$Y$$ را می‌توان به شکل زیر نوشت:

$$ Y = \begin{bmatrix} (\theta^{(1)})^Tx^{(1)} & ... & (\theta^{(n_u)})^Tx^{(1)} \\ (\theta^{(1)})^Tx^{(2)} & ... & (\theta^{(n_u)})^Tx^{(2)} \\ \vdots & \vdots & \vdots \\ (\theta^{(1)})^Tx^{(n_m)} & ... & (\theta^{(n_u)})^Tx^{(n_m)} \end{bmatrix} $$

بنابراین می‌توان با تعریف دو ماتریس $$X$$ برای خصوصیت‌ها و $\Theta$ برای پارامترها به شکل زیر:

$$ X = \begin{bmatrix} (x^{(1)})^T\\ \vdots \\ (x^{(n_m)})^T \end{bmatrix} ,\quad \Theta = \begin{bmatrix} (\theta^{(1)})^T\\ \vdots \\ (\theta^{(n_u)})^T \end{bmatrix} $$

می‌توان ماتریس $$Y$$ را به صورت برداری $X\Theta^T$ محاسبه کرد.

اسم دیگر این الگوریتم Low Rank Matrix Factorization است. اگر با جبر خطی و اصطلاح نقصات مرتبه آشنا باشید، دلیل این نامگذاری به خاطر خاصیت Low Rank بودن ماتریس $X\Theta^T$ است. اگر هم خیلی با جبر خطی و این اصطلاح آشنایی ندارید، جای نگرانی نیست و هنوزم می‌توانید الگوریتم را بدون مشکل اجرا کنید.

پیدا کردن فیلم‌های مشابه

هدف دیگر ما پیدا کردن فیلم‌های مشابه و پیشنهاد دادن آن به کاربر است. تا اینجا برای هر محصول $$i$$ یک بردار از خصوصیت‌ها را یاد گرفته‌ایم $x^{(i)} \in \mathbb{R}^n$ . از قبل خصوصیت‌ها را برای محصولات نمی‌دانیم، ولی با اجرای الگوریتم می‌توانیم جنبه‌های مهم محصول را یاد بگیریم. مثلا خصوصیت‌های:

$$x_1 =$$ romance

$$x_2 =$$ action

$$x_3 =$$ comedy

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

حال می‌خواهیم به این سوال پاسخ دهیم که چگونه فیلم $$j$$ را که در ارتباط با فیلم $$i$$ است را پیدا کنیم؟

دلیل آنکه دنبال چنین مسئله‌ای می‌رویم، به این خاطر است که فرض کنید کاربری اخیرا فیلمی را خریداری کرده یا نگاه کرده است و شما می‌خواهید دیگر فیلم‌های خود را بر اساس آن به کاربر پیشنهاد دهید. برای این کار کافی است که برای فیلم $$i$$ و $$j$$ مقدار

$$ \lVert x^{(i)} - x^{(j)} \rVert $$

را محاسبه کنید. اگر این اختلاف کوچک باشد، می‌توان گفت فیلم $$j$$ مشابه فیلم $$i$$ است.

جزئیات اجرا - نرمال کردن میانگین

فرض کنید علاوه بر ۴ کاربری که تا الان مثال آنها را بررسی کرده‌ایم، کاربر پنجمی داریم که هیچ فیلمی را رتبه‌بندی نکرده است.

فیلم	آلیس (1)	باب (2)	کارول(3)	دیو(4)	ایو (5)
Love at Last	5	5	0	0	؟
Romance Forever	5	؟	؟	0	؟
Cute Puppies of Love	؟	4	0	؟	؟
Nonstop Car Chases	0	0	5	4	؟
Sword Vs. Karate	0	0	5	0	؟

در این حالت اگر الگوریتم را اجرا و تابع زیر را کمینه کنیم:

$$\begin{eqnarray} \min_{\substack{x^{(1)},...,x^{(n_m)} \\ \theta^{(1)},...,\theta^{(n_u)}}} &\frac{1}{2}& \sum_{(i,j):r(i,j)=1} \left((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\right)^2 \\ &+&\frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x^{(i)}_{k})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta^{(j)}_{k})^2 \end{eqnarray}$$

چون برای کاربر پنجم $$r(i,j) = 1$$ وجود ندارد، تنها جمله تاثیرگذار برای آن جمله آخر خواهد بود که با فرض داشتن دو خصوصیت، کمینه کردن آن به وضوح $\theta = \begin{bmatrix}0\\0\end{bmatrix}$ را برمی‌گرداند. با داشتن چنین خصوصیتی آنچه که برای کاربر پنجک پیش‌بینی خواهیم کرد برابر است با:

$$ (\theta^{(5)})^Tx^{(i)} = 0 $$

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

برای این کار ابتدا میانگین نمره‌هایی که به هر فیلم داده شده است را محاسبه و در ماتریس $\mu$ ذخیره می‌کنیم:

$$ \mu = \begin{bmatrix} 2.5\\2.5\\2\\2.25\\1.25 \end{bmatrix} $$

حال با کم کردن این ماتریس از ماتریس $$Y$$ ، ماتریس جدید $$Y$$ به صورت زیر خواهد بود:

$$ Y = \begin{bmatrix} 2.5 & 2.5 & -2.5 & -2.5 & ? \\2.5 & ? & ? & -2.5& ? \\? & 2 & -2 & ? & ?\\-2.25 & -2.25 & 2.75 & 1.75 & ?\\-1.25 & -1.25 & 3.75 & -1.25 & ?\end{bmatrix} $$

الان تمام فیلم‌ها در ماتریس جدید دارای نمره میانگین صفر هستند. حال فرض می‌کنیم که داده‌‌های اصلی ما همین ماتریس جدید $$Y$$ است. با این فرض برای پیش‌بینی نمره کاربر $$j$$ روی فیلم $$i$$ باید به صورت زیر عمل کنیم:

$$ (\theta^{(j)})^T(x^{(i)} + \mu_i) $$

برای کاربر پنجم خواهیم داشت:

$$ \theta^{(5)} = \begin{bmatrix} 0\\0\end{bmatrix}, \quad (\theta^{(5)})^T(x^{(i)}) + \mu_i $$

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

<< مبحث قبلی مبحث بعدی >>