haji_thesis/Thesis/chap3.tex

% !TEX encoding = UTF-8 Unicode
\chapter{روش پیشنهادی}\label{Chap:Chap3}

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

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

\section{تعبیه‌ی ویژگی‌ها}
از آن‌جا که استفاده از بردار‌های تعبیه شده، امری ضروری برای بهره‌گیری از ویژگی‌های دسته‌ای موجود در مجموعه‌های داده‌ی پیش‌بینی نرخ کلیک به شمار می‌رود، طراحی مدل پیشنهادی را از همین بخش آغاز می‌نماییم.

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

می‌توانیم استفاده از بردار‌های هم‌بعد را به این صورت تعبیر کنیم که در این مدل‌ها، برای هر فیلد یک فضای $k$ بعدی در نظر گرفته شده و تمامی ویژگی‌ها (حالت‌ها)ی این فیلد، به عنوان نقاطی در این فضای $k$ بعدی جای می‌گیرند. به عنوان مثال، در صورتی که فیلد $F_{a}$ دارای 3 حالت مختلف و فیلد $F_{b}$ دارای 1000 حالت مختلف باشند، در فضای تعبیه‌ی فیلد اول ($E_{a}$) سه نقطه (یا سه بردار $k$ بعدی) و همچنین در فضای تعبیه‌ی فیلد دوم ($E_{b}$) هزار نقطه (یا بردار $k$ بعدی) حضور خواهند داشت؛ پس جایگیری نقاط در فضای $E_{b}$ نسبت به جایگیری نقاط در فضای $E_{a}$ شرایط فشرده‌تری دارد.

با ملاحظه‌ی نکته‌ی فوق، این سوال به وجود می‌آید که \textbf{آیا تعبیه‌ی ویژگی‌های همه‌ی فیلد‌ها در فضای دارای ابعاد یکسان (که همه‌ی روش‌های پیشین در انجام آن اتفاق دارند)، بهترین تصمیم ممکن است؟} برای پاسخ به این سوال، می‌توانیم از دو روش مختلف استفاده کنیم. روش اول، استفاده از نگرش مرسوم در \trans{نظریه‌ی اطلاعات}{Information Theory} برای اندازه‌گیری اطلاعات موجود در این بردار‌ها و روش دوم، بررسی شهودی این مساله، با توجه به مفاهیم مرسوم در ادبیات یادگیری ماشین و \trans{یادگیری ژرف}{Deep Learning} است.

\subsection{بررسی ابعاد بردار‌های تعبیه به کمک نظریه‌ی اطلاعات}
در نظریه‌ی اطلاعات\cite{ShannonWeaver49}،  \trans{آنتروپی}{Entropy} یک ویژگی دسته‌ای (فیلد)، به صورت زیر محاسبه می‌شود:
\begin{latin}
\begin{equation}
H(F) = - \sum_{i = 1}^{|F|}{p_{i}log_{2}(p_{i})}\label{entropy_source}
\end{equation}
\end{latin}

که در آن $|F|$ تعداد دسته‌ها و $p_{i}$ احتمال وقوع حالت $i$‌ام این ویژگی هستند.

در صورتی که این ویژگی دسته‌ای را در فضای $k$ بعدی تعبیه کنیم و هر‌یک از عناصر موجود در بردار‌های تعبیه، دارای $s$ بیت باشند، می‌توانیم آنتروپی بردار تعبیه‌شده را محاسبه کنیم:
\begin{latin}
\begin{equation}
H(E) = - \sum_{i = 1}^{2^{ks}}{p_{i}log_{2}(p_{i})}\label{entropy_embedding}
\end{equation}
\end{latin}
که در آن $p_{i}$ احتمال یک بودن بیت $i$ام این بردار است.

با مقایسه‌ی دو رابطه‌ی \ref{entropy_source} و \ref{entropy_embedding} می‌توانیم میزان اطلاعات موجود در آن فیلد را، با میزان اطلاعات قابل بیان توسط بردار تعبیه شده مقایسه کنیم.

در پژوهش \cite{Naumov_embedding_dim} با فرض هم احتمال بودن توزیع حالت‌های ویژگی دسته‌ای و همچنین هم احتمال بودن توزیع بیت‌های بردار تعبیه شده، مقایسه‌ی فوق را انجام داده و در نتیجه به رابطه‌ی زیر رسیدند:
\begin{latin}
\begin{equation}
log_{2}(|F|) = k . s
\end{equation}
\end{latin}

می‌توان این رابطه را به این صورت تعبیر کرد که برای تناسب اطلاعات موجود در ویژگی دسته‌ای و بردار تعبیه شده‌ی مربوطه، باید بعد تخصیص داده شده به آن بردار با لگاریتم کاردینالیتی مجموعه‌ی حالات مختلف انتخاب آن متناسب باشد؛ پس فیلدی که کاردینالیتی بالاتری داشته باشد، باید در فضای دارای ابعاد بیشتر تعبیه شود.

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

با وجود این فرض‌های اشتباه و فرض ساده‌کننده‌ی توزیع یکنواخت، این روابط تنها با افزودن چند ضریب قابل اصلاح است. فرض می‌کنیم اطلاعات مشترک بین متغیر هدف و هر‌یک از فیلد‌ها، به صورت ضریب ثابتی ($\mu$) از اطلاعات موجود در آن فیلد باشد. همچنین، فرض می‌کنیم هر چند ($\delta$) بردار تعبیه، به دلیل شباهت مفهوم مربوطه، در محل یکسانی از فضای تعبیه جا بگیرند.
\begin{latin}
	\begin{equation}
I(y, F_{i}) = H(F_{i}) \times \mu = log_{2}(\frac{|F_{i}|}{\delta}) \times \mu \label{prop_mutual}
\end{equation}
\end{latin}

همچنین فرض می‌کنیم برای مطلوب بودن فضای تعبیه، انتظار می‌رود تنها از کسر ثابتی ($\kappa$) از ظرفیت بیت‌های موجود در بردار تعبیه استفاده شود.
\begin{latin}
	\begin{equation}
H(E) = k . s . \kappa \label{prop_entropy}
\end{equation}
\end{latin}
حال با برابر قرار دادن روابط \ref{prop_mutual} و \ref{prop_entropy}، به این رابطه می‌رسیم:
\begin{latin}
\begin{equation}
k = log_{2}(\frac{|F_{i}|}{\delta}) \times \frac{\mu}{s \times \kappa}
\end{equation}
\end{latin}
که می‌توان آن را به صورت زیر هم نوشت:
\begin{latin}
\begin{equation}
k = \omega . \ln(|F_{i}|) + \epsilon
\end{equation}
\end{latin}
که در آن، با معرفی پارامتر‌های $\omega$ و $\epsilon$ همه‌ی ضرایب ثابت را یک جا جمع می‌کنیم. حال از طریق رابطه‌ی فوق، می‌توانیم ابعاد مناسب برای تعبیه‌ی هر فیلد را محاسبه کنیم.

\subsection{بررسی ابعاد بردار‌های تعبیه به کمک مفاهیم شهودی یادگیری ماشین و یادگیری ژرف}
در بخش قبل، به کمک مفاهیم نظریه‌ی اطلاعات، رابطه‌ای برای تخصیص مناسب بعد به فیلد‌ها ارائه کنیم. در این بخش، با بهره‌گیری از شهود و همچنین برخی از مفاهیم مورد استفاده در ادبیات یادگیری ماشین و یادگیری ژرف، نسبت به توجیه، نقد و اصلاح رابطه‌ی ارائه شده اقدام می‌کنیم.

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

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

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

از مثال بالا، می‌توانیم این مفهوم را برداشت کنیم که برای دسترسی به بهترین عملکرد ممکن، چگالی نقاط در فضای تعبیه باید مقدار معینی داشته باشد. برای درک بهتر این مفهوم، می‌توانیم تعریف فیزیکی چگالی را در نظر گرفته و سعی کنیم رابطه‌ای برای بعد تعبیه به دست آوریم.

از آن‌جا که تعریف فیزیکی چگالی، از تقسیم تعداد ذرات به حجم محاسبه می‌شود، ولی فضای تعبیه حجم بی‌نهایت دارد، مجبوریم این تعریف را تا حدودی تغییر دهیم. اعمال تکنیک‌های تنظیم بر پارامتر‌های تعبیه، باعث محدود شدن محل هندسی بردار‌های تعبیه شده می‌شوند و لذا می‌توانیم فرض کنیم همه‌ی پارامتر‌های تعبیه، در بازه‌ی $(-\frac{L}{2}, \frac{L}{2})$ محدود خواهند بود؛ پس اگر بعد تعبیه را $k$ و تعداد نقاطی که در این فضا تعبیه می‌شوند را $n$ در نظر بگیریم، می‌توانیم چگالی متوسط این نقاط را محاسبه کنیم:
\begin{latin}
\begin{equation}
density(E) = \frac{n}{L^{k}}
\end{equation}
\end{latin}

حال اگر در یک مدل که بیش از یک ویژگی دسته‌ای ورودی دارد، مقدار چگالی را برای فضای تعبیه‌ی همه‌ی فیلد‌ها یکسان در نظر بگیریم:
\begin{latin}
\begin{equation}
\frac{|F_{i}|}{L^{k_{i}}} = \frac{|F_{j}|}{L^{k_{j}}} = c.t.e.
\end{equation}
\end{latin}

با لگاریتم گرفتن از رابطه‌ی فوق می‌توانیم:

\begin{latin}
\begin{equation}
\ln(|F_{i}|) - k_{i} \ln(L) = \ln(|F_{j}|) - k_{j} \ln(L) = c
\end{equation}
\end{latin}
که در آن $c$ یک عدد ثابت بوده و خواهیم داشت:
\begin{latin}
\begin{equation}
\forall i: k_{i} = \frac{\ln(|F_{i}|) - c}{ln(L)}
\end{equation}
\end{latin}
با تغییر دادن پارامتر‌ها، می‌توان این رابطه را به شکل زیر در آورد:
\begin{latin}
\begin{equation}
\forall i: k_{i} = \omega \times \ln(|F_{i}|) + \epsilon
\end{equation}
\end{latin}
که رابطه‌ی اخیر، کاملا بر رابطه‌ی به دست آمده به کمک مفاهیم نظریه‌ی اطلاعات مطابقت دارد.

رابطه‌ی به دست آمده، نسبت به کاردینالیتی فیلد، صعودی است. به این معنا که فیلد دارای دسته‌های بیشتر، لزوما در فضای دارای بعد‌های بالاتر تعبیه خواهد شد؛ پس در صورتی که مدلی از این رابطه برای تخصیص پارامتر‌های تعبیه به فیلد‌های ورودی استفاده کند، همیشه تعداد پارامتر‌های بیشتری به فیلد‌هایی که کاردینالیتی بالاتر دارند در نظر می‌گیرد. اگر بخواهیم یک مثال افراطی از این مساله را مطرح کنیم، می‌توانیم فیلد‌های \trans{شناسه}{ID} را در نظر بگیریم. فیلد شناسه، به ویژگی‌هایی گفته می‌شود که در هر رکورد از مجموعه‌ی داده، یک مقدار متفاوت به خود گرفته و لذا هرگز در مجموعه‌ی داده تکرار نمی‌شوند. هر چند چنین ویژگی‌هایی از نظر نظریه‌ی اطلاعات، دارای آنتروپی و اطلاعات زیادی هستند، اما واضح است که به دلیل عدم تکرار (یا تکرار بسیار کم) آن‌ها در مجموعه‌ی داده، یادگیری از آن‌ها را غیر ممکن ساخته و لذا تخصیص پارامتر‌های زیاد به این ویژگی‌ها، باعث هدر رفتن قدرت محاسباتی و همچنین افزایش خطر بیش‌برازش می‌شود.

برای اصلاح این مشکل، می‌توانیم رابطه‌ی فوق را به شکل زیر تغییر دهیم:
\begin{latin}
\begin{equation}
\forall i: k_{i} = \omega \times \ln(|F_{i}|) \times \frac{|Dataset| - |F_{i}|}{|Dataset|} + \epsilon
\end{equation}
\end{latin}
که در آن $|Dataset|$ تعداد رکورد‌های موجود در مجموعه‌ی داده است. همان‌طور که مشخص است، کسر $\frac{|Dataset| - |F_{i}|}{|Dataset|}$ در صورتی که $|F_{i}|$ نسبت به تعداد رکورد‌های مجموعه‌ی داده، مقدار کمی داشته باشد، تقریبا برابر یک بوده و تاثیر چندانی روی نتیجه‌ی رابطه نمی‌گذارد؛ اما در صورتی که $|F_{i}|$ نسبت به $|Dataset|$ قابل مقایسه باشد، این کسر میزان کمتر از یک به خود گرفته و لذا بعد تعبیه را برای این ویژگی‌ها کاهش می‌دهد. به عبارت دیگر، برای ویژگی‌هایی که تعداد تکرار موجودیت‌های آن‌ها در مجموعه‌ی داده کم باشد، بعد تعبیه را کمی کاهش می‌دهیم. در حالت افراطی ویژگی‌های شناسه، که در آن‌ها $|F_{i}|$ تقریبا با $|Dataset|$ برابر است، میزان این کسر تقریبا برابر صفر شده و لذا بعد تعبیه برای این ویژگی‌ها به حداقل کاهش می‌یابد.

با توجه به نکات مطرح شده، در این پژوهش بعد تعبیه‌ی هر‌یک از ویژگی‌های دسته‌ای، از رابطه‌ی نهایی زیر محاسبه خواهد شد:
\begin{latin}
\begin{equation}
\forall_{1 \le i \le f}: Dim(F_{i}) = \omega \times \ln(|F_{i}|) \times \frac{|Dataset| - |F_{i}|}{|Dataset|} + \epsilon
\end{equation}
\end{latin}
که در آن، $f$ تعداد فیلد‌های ورودی است. همچنین، پارامتر‌های مربوط به تعبیه‌ی فیلد‌های مدل را به صورت زیر تعریف می‌کنیم:

\begin{latin}
\begin{equation}
\forall_{1 \le i \le f}:\mathbf{E}_{i} \in \mathbb{R}^{|F_{i}|\times Dim(|F_{i}|)}
\end{equation}
\end{latin}
حال اگر $x_{i}$ اندیس ویژگی فعال در فیلد $i$ام باشد، بردار‌های تعبیه شده‌ی مدل به این صورت تعریف می‌شوند:
\begin{latin}
\begin{equation}
\forall_{1 \le i \le f}:e_{i} = \mathbf{E}_{i}^{x_{i}} \in \mathbb{R}^{Dim(|F_{i}|)}
\end{equation}
\end{latin}

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

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

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

\subsection{نگاشت خطی بردار‌های تعبیه به فضای هم‌بعد}
در پژوهش \cite{Ginart_MixedDimEmb}، یک روش ساده برای مقابله با این مشکل معرفی شده است. می‌دانیم ضرب ماتریسی بردار‌های یک فضای $k_{in}$ بعدی، در یک ماتریس با ابعاد $k_{in} \times k_{out}$، یک نگاشت خطی بین فضای $k_{in}$ بعدی گفته شده و یک فضای $k_{out}$ بعدی جدید است. یعنی اگر $n$ بردار از فضای اول را در سطر‌های ماتریس $X$ قرار دهیم و همچنین ماتریس $W_{k_{in} \times k_{out}}$ را از سمت راست در $X$ ضرب کنیم، حاصل این عمل نگاشت این بردار‌ها در یک فضای جدید $k_{out}$ بعدی خواهد بود:
\begin{latin}
\begin{equation}
Y_{n \times k_{out}} = X_{n \times k_{in}} W_{k_{in} \times k_{out}}
\end{equation}
\end{latin}
در صورتی که $k_{in} < k_{out}$ باشد، نقاط در فضای $Y$ تنها به یک زیرفضا (منیفولد) از این فضای $k_{out}$ بعدی محدود شده و از تمام پیچیدگی موجود در این فضا استفاده نخواهد شد. همچنین در صورتی که $k_{in} > k_{out}$ باشد، نقاط در فضای $Y$ به صورت فشرده‌تری حضور داشته و می‌توان گفت میزانی از اطلاعات نهفته در این نقاط، از دست خواهد رفت.

در پژوهش فوق، پیشنهاد شده است که پس از ایجاد بردار‌های تعبیه در فضا‌های با ابعاد مختلف، با استفاده از تعدادی تبدیل ماتریسی خطی، همه‌ی این فضا‌ها را به فضای $k$ بعدی مشترک نگاشت کنیم؛ سپس مقادیر تعامل را مانند ماشین‌های فاکتورگیری، به کمک عملگر ضرب داخلی محاسبه کنیم. چون ابعاد ماتریس‌های گفته شده و در نتیجه تعداد پارامتر‌های آن‌ها در مقایسه با تعداد پارامتر‌های جدول‌های تعبیه ناچیز خواهد بود، لذا به سادگی می‌توانیم این پارامتر‌ها را به کمک روش‌های گرادیان کاهشی بیاموزیم.

\subsection{محاسبه‌ی تعامل به کمک شبکه‌ی عصبی}
در پژوهش \cite{he2017neural} که در ادبیات سیستم‌های پیشنهاد دهنده انجام شده است، برای محاسبه‌ی تعامل بین دو ویژگی کاربر و کالا، که به مساله‌ی \trans{فیلتر کردن مشترک}{Collaborative Filtering} معروف است، از ایده‌ی متفاوتی استفاده شده است. لازم به ذکر است این پژوهش، چندین روش مختلف و ترکیب آن‌ها را معرفی کرده است، در صورتی که در این پژوهش، تنها به یکی از این روش‌ها رجوع کرده و از ایده‌ی موجود در آن بهره می‌جوییم.

برای محاسبه‌ی تعامل بین دو بردار تعبیه شده، لزومی بر استفاده از عملگر ضرب داخلی وجود ندارد، بلکه می‌توان از یک \trans{شبکه‌ی عصبی چند لایه}{Multi Layer Perceptron} بهره جست. مهمترین ویژگی شبکه‌های عصبی چند لایه، توانایی تخمین همه‌ی توابع است. یعنی در صورتی که یک شبکه‌ی عصبی چند لایه، به تعداد کافی نورون داشته باشد و همچنین با مقدار کافی داده آموزش داده شود، می‌تواند روابط موجود بین این داده‌ها را با میزان خطای \trans{دلخواه}{Arbitrary} فرا گرفته و تخمین بزند؛ لذا به شبکه‌های عصبی چند لایه، \trans{تخمین زننده‌ی سراسری}{Global Approximator} نیز گفته می‌شود.

در پژوهش فوق، پس از تعبیه‌ی دو ویژگی موجود در مجموعه‌ی داده، بردار‌های تعبیه شده را به هم چسبانده و سپس از یک شبکه‌ی عصبی چند لایه برای محاسبه‌ی تعامل استفاده می‌شود. به دلیل سادگی و تطبیق پذیری شبکه‌های عصبی چند‌لایه، در این پژوهش نیز از این شبکه‌ها برای محاسبه‌ی تعامل بین ویژگی‌ها بهره خواهیم جست.
\subsection{تعامل‌های چند‌بعدی به جای تعامل‌های چند‌گانه}
یکی از مزایای ماشین‌های فاکتورگیری، سادگی پیاده‌سازی تعامل‌های چند‌گانه است. تعامل‌های چند‌گانه، به محاسبه‌ی مفهوم تعامل بیشتر از دو ویژگی به صورت همزمان اشاره می‌کند. در ماشین‌های فاکتورگیری، به دلیل محاسبه‌ی تعامل به صورت ضرب داخلی، به سادگی می‌توان عمل محاسبه‌ی تعامل را به بیش از دو ویژگی تعمیم داد. به عنوان مثال، رابطه‌ی زیر تعامل میان سه ویژگی در یک ماشین فاکتورگیری (مرتبه سوم) را نشان می‌دهد:
\begin{latin}
\begin{equation}
I_{i, j, l} = \sum_{m = 1}^{k} e_{i_{m}}e_{j_{m}}e_{l_{m}}
\end{equation}
\end{latin}
که در آن $k$ بعد تعبیه‌ی مشترک همه‌ی فیلد‌ها است. به این ترتیب، ماشین‌های فاکتورگیری ساده و بسیاری از مشتقات آن، به سادگی قابلیت محاسبه‌ی تعامل چند‌گانه را دارا هستند. تعامل چند‌گانه قابلیت مدل‌سازی را افزایش داده و البته خطر بیش‌برازش را افزایش می‌دهد.

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

ایده‌ای که برای رویارویی با این مشکل در این پژوهش معرفی می‌کنیم، استفاده از تعامل‌های چند‌بعدی است. همه‌ی روش‌های پیشین به دلیل محدودیت‌های ساختاری، مفهوم تعامل را به یک مفهوم تک بعدی که رابطه‌ی آن با احتمال کلیک خطی است، تقلیل داده‌اند. این در حالی است که می‌توانیم مفهوم تعامل را به صورت زیر تعریف کرده و تعمیم دهیم:
\begin{definition}
تعامل بین دو فیلد، بردار نهفته‌ای است که تمامی اطلاعاتی که در زوج مرتب آن دو فیلد وجود دارد و برای تخمین نرخ کلیک مورد نیاز است را به صورت فشرده نمایش می‌دهد.
\end{definition}
تعریف فوق دو تفاوت عمده با تعریف تعامل در خانواده‌ی ماشین‌های فاکتورگیری دارد:
\begin{enumerate}
\item \textbf{چند‌بعدی بودن}

تعامل بین دو فیلد می‌تواند به جای تک بعدی بودن، چند بعدی باشد و در نتیجه رفتاری مانند بردار‌های نهان در شبکه‌های عصبی داشته باشد. به این معنی که فضای چند‌بعدی ایجاد شده توسط تعامل بین دو فیلد، می‌تواند حاوی اطلاعاتی باشد که بخش‌های دیگر مدل، آن را به صورت یک ویژگی سطح بالا دریافت کرده و لذا قادر به استخراج میزان بیشتری اطلاعات از این بردار نهان چند‌بعدی خواهند بود.
\item \textbf{رابطه‌ی غیر خطی}

در ماشین‌های فاکتورگیری، فرض شده است که مجموع همه‌ی تعامل بین فیلد‌های مختلف، با افزوده شدن به جملات خطی رگرسیون، به صورت مستقیم احتمال کلیک را تخمین می‌زنند. این در حالی است که با در نظر گرفتن مفهوم تعامل به عنوان ویژگی‌های نهان در یک مدل ژرف، می‌توان روابط پیچیده‌تری نسبت به رابطه‌ی خطی بین تعامل بین فیلد‌ها و احتمال کلیک کشف نمود؛ پس لزومی ندارد که از رابطه‌ی بین احتمال کلیک و تعامل‌های بین ویژگی‌ها را به یک رابطه‌ی خطی تقلیل دهیم.
\end{enumerate}
با در نظر گرفتن تفاوت‌های گفته شده، می‌توان ساختار پیشنهادی را ارائه کرد، ولی پیش از معرفی نهایی ساختار پیشنهادی، پرسشی که ممکن است در این مرحله به ذهن برسد را مطرح کرده و پاسخ می‌دهیم.
\begin{itemize}
\item \textbf{پرسش}

چرا به جای تعامل چند‌بعدی، با افزایش تعداد لایه‌ها در شبکه‌های تعامل، از تعامل تک بعدی استفاده نکنیم؟ این گونه به نظر می‌رسد که در صورتی که تعداد لایه‌های شبکه‌های تعامل را افزایش دهیم، مدل می‌تواند تعامل‌های چند‌بعدی گفته شده را در یکی از لایه‌های نهان داخل همین شبکه‌های تعامل فرا گرفته و سپس با استخراج اطلاعات مفید آن، تعامل را به صورت تک بعدی به بخش‌های دیگر مدل انتقال دهد؛ در نتیجه معرفی تعامل چند‌بعدی به نظر بی‌دلیل می‌رسد.
\item \textbf{پاسخ}

با توجه به تعریف بالا برای مفهوم تعامل، این مفهوم مربوط به اطلاعات مشترکی است که بین ویژگی‌های دو فیلد وجود دارند؛ پس در نظر گرفتن \trans{تنگنا}{Bottleneck}ی تک بعدی، باعث محدودیت شده و ممکن است این اطلاعات مشترک برای عبور از این تنگنا فیلتر شده و بخش مهمی از این اطلاعات از دست برود.

دلیل دیگر استفاده از تعامل‌های چند‌بعدی، به اشکالی که قبلا معرفی کردیم یعنی عدم مقیاس پذیری مدل پیشنهادی در صورت استفاده از تعامل‌های چندگانه باز می‌گردد. در صورتی که اطلاعات مهمی در تعامل سه فیلد یا بیشتر وجود داشته باشد، در تعامل‌های تک بعدی این اطلاعات در تنگنای فوق حذف شده و مدل قادر به استخراج اطلاعات مربوط به تعامل چند‌گانه نخواهد بود. این در حالی است که اگر اجازه دهیم بردار‌های تعامل، چند بعدی باشند، مدل می‌تواند از کنار هم قرار دادن تعامل‌های دوگانه، تعامل‌های مرتبه‌ی بالاتر را به صورت \trans{ضمنی}{Implicit} محاسبه کرده و از آن برای پیش‌بینی نرخ کلیک بهره ببرد. عملا با در نظر گرفتن تعامل‌های چند‌بعدی، نیاز به استفاده از تعامل‌های چندگانه حذف شده و لذا مقیاس پذیری مدل افزایش می‌یابد.
\end{itemize}
با استدلال‌های گفته شده، روش محاسبه‌ی بردار‌های تعامل بین فیلد‌های ورودی تکمیل شده و لذا در این بخش، با اشاره به برخی جزئیات، این بخش مهم از روش پیشنهادی را جمع بندی می‌کنیم.

در بخش قبل بردار‌های تعبیه شده‌ی مدل را تعریف کردیم. اگر در مجموعه‌ی داده، $f$ فیلد داشته باشیم، بردار‌های تعبیه‌ی فیلد‌ها را با
$\{e_{1}, e_{2}, \dots, e_{f}\}$
نمایش می‌دهیم. چون تعامل بین ویژگی‌های هر دو فیلد محاسبه می‌شود، نیاز به $\frac{f(f - 1)}{2}$ شبکه‌ی عصبی تعامل خواهیم داشت. برای سادگی نامگذاری، این شبکه‌ها را به صورت زیر نامگذاری می‌کنیم:
\begin{latin}
\begin{equation}
\forall_{1 \le i < j \le f},  InteractionNet_{i, j} : \RR^{Dim(|F_{i}|) + Dim(|F_{j}|)} \rightarrow \RR^{Dim_{Int}}
\end{equation}
\end{latin}


شبکه‌ی $InteractionNet_{i, j}$ چند‌لایه بوده و تعداد نورون‌های هر لایه، به صورت خطی کاهش می‌یابد تا از $Dim(|F_{i}|) + Dim(|F_{j}|)$ بعد به $Dim_{Int}$ بعد برسد. تعداد لایه‌های همه‌ی این شبکه‌ها برابر $Depth_{Interaction}$ است. در فصل بعد با انجام آزمایش‌هایی، تعداد لایه‌ها و همچنین بعد بردار‌های تعامل مناسب را به دست خواهیم آورد.

تابع فعال‌ساز همه‌ی لایه‌های این شبکه‌ها (بجز لایه‌ی آخر) را \trans{واحد خطی یکسو کننده‌ی نشت کننده}{LeakyReLU}\cite{maas2013leakyrelu} در نظر می‌گیریم. دلیل استفاده از این تابع، انتقال بهتر گرادیان به لایه‌های پایین‌تر است. در لایه‌ی آخر این شبکه‌ها، برای استفاده‌ در بخش‌های دیگر مدل، از هیچ تابع فعال‌سازی استفاده نمی‌کنیم. در این پژوهش مقادیر بردار‌های تعامل را به شکل زیر نامگذاری و محاسبه می‌کنیم:
\begin{latin}
\begin{equation}
\forall_{1 \le i < j \le f},  I_{i, j} = InteractionNet_{i, j}(e_{i}: e_{j})
\end{equation}
\end{latin}

\section{استفاده از بردار‌های تعبیه و تعامل برای تخمین نرخ کلیک}
در بخش‌های قبل، شیوه‌ی تعبیه‌ی ویژگی‌ها و همچنین نحوه‌ی محاسبه‌ی تعامل بین بردار‌های تعبیه شده در روش پیشنهادی را معرفی کردیم. در این قسمت تنها بخش باقی مانده‌ی مدل را معرفی می‌کنیم. این بخش \trans{شبکه‌ی سر}{Head Network} نام دارد و مسئول استفاده از همه‌ی ویژگی‌هایی که تا اینجا تعریف کردیم و پیش‌بینی نرخ کلیک به کمک این ویژگی‌ها است.

در تعدادی از پژوهش‌های پیشین که از مدل‌های ژرف استفاده کرده‌اند، برای محاسبه‌ی نرخ کلیک از دو دسته ویژگی مهم استفاده می‌شود:
\begin{enumerate}
\item \textbf{ویژگی‌های مرتبه پایین}

ویژگی‌های مرتبه پایین در مدل‌های ژرف مبتنی بر ماشین فاکتورگیری، شامل جمله‌ی بایاس، جملات خطی و همچنین تعامل‌های مرتبه دوم است. همانطور که مشخص است، این ویژگی‌ها نقش اساسی در شکل دهی به تابع تصمیم‌گیری مدل‌ها دارند. این ویژگی‌ها به دلیل سادگی در محاسبه و همچنین نقش ساده و مشخص در پیش‌بینی نرخ کلیک، به سادگی نیز آموزش یافته و به همین دلیل با تعداد داده‌های کم نیز قابل یادگیری هستند.
\item \textbf{ویژگی‌های مرتبه بالا}
با گسترش روش‌های ژرف، محققین متوجه توانایی بالای این روش‌ها برای استخراج \trans{ویژگی‌های نهان}{Latent Features} و استفاده از آن‌ها یا استفاده از سایر ویژگی‌های مرتبه بالا شدند. مدل‌های ژرف، در صورتی که داده‌های کافی در اختیار داشته باشند، قادر خواهند بود ویژگی‌های نهان مفیدی ساخته و آن‌ها را برای محاسبه‌ی متغیر هدف به کار ببرند؛ در نتیجه بسیاری از پژوهش‌های پیشین برای پیش‌بینی نرخ کلیک، از این مزیت بهره جسته‌اند.

ویژگی‌های مرتبه بالا در مدل‌های پیش‌بینی نرخ کلیک، شامل تعامل‌های مرتبه بالا بین بردار‌های تعبیه و همچنین ویژگی‌های نهان که در برخی پژوهش‌ها به آن‌ها \trans{تعامل‌های ضمنی}{Implicit Interactions} نیز گفته می‌شود، هستند. استدلال این نامگذاری، این نکته است که مقادیر تعامل‌، به صورت \trans{صریح}{Explicit} فرموله‌بندی و محاسبه می‌شوند. در حالی که مدل‌های ژرف، می‌توانند ویژگی‌های نهانی محاسبه‌کنند که عملا تفاوتی با مقادیر تعامل بین ویژگی‌ها ندارند، اما فرموله بندی صریحی برای آن‌ها وجود ندارد؛ در نتیجه مدل‌های ژرف بر حسب نیاز، این ویژگی‌ها را استخراج کرده و از آن‌ها استفاده می‌کنند؛ لذا می‌توان این ویژگی‌ها را نسخه‌ی غیر صریح یا ضمنی (و همچنین پیچیده‌تر) مفهوم تعامل در نظر گرفت.

ویژگی‌های مرتبه بالا برای یادگیری، به داده‌های بیشتری نیاز داشته و شامل اطلاعات بیشتری هستند؛ اما آموزش آن‌ها علاوه بر محاسبات بیشتر، نیاز به طراحی دقیق‌تر و چالش‌های مختلف، به مراقبت ویژه در مقابل خطر بیش‌برازش نیاز دارند. 
\end{enumerate}
همانطور که گفته شد، در بسیاری از پژوهش‌های ژرف پیشین، از هر دو دسته‌ی این ویژگی‌ها استفاده می‌شود. دسته‌ی اول، شکل کلی تابع تصمیم‌گیری را ترسیم کرده و دسته‌ی دوم، به مدل کمک می‌کنند که این تابع را به طرز دقیق‌تری شکل داده و انعطاف کافی برای مدل‌سازی را به آن بیافزاید.

در این پژوهش نیز، از همین شیوه بهره جسته و از دو دسته ویژگی مختلف برای استفاده‌ی شبکه‌ی سر استفاده می‌کنیم. انتظار داریم این عمل هم در شرایط شروع سرد و هم در مقابل مشکل بیش‌برازش باعث بهبود کلی عملکرد مدل شود؛ پس ورودی شبکه‌ی سر، شامل دو بخش است:
\begin{itemize}
\item \textbf{بردار‌های تعبیه}

شبکه‌ی سر، برای پیش‌بینی نرخ کلیک، نیاز به ویژگی‌های مرتبه پایین دارد. به دلیل عدم استفاده از جملات رگرسیون خطی، تنها ویژگی‌های مرتبه پایینی که در اختیار داریم، خود بردار‌های تعبیه است؛ بنابراین همه‌ی بردار‌های تعبیه را به هم چسبانده و به عنوان ورودی اول شبکه‌ی سر استفاده می‌کنیم.
\item \textbf{بردار‌های تعامل}

همچنین، شبکه‌ی سر برای استخراج ویژگی‌های نهان و تخمین دقیق مرز تصمیم‌گیری، نیاز به ویژگی‌های مرتبه بالا دارد. برای تامین این ویژگی‌های مرتبه‌ی بالا، همه‌ی بردار‌های تعامل که توسط شبکه‌های تعامل محاسبه شده‌اند را به هم چسبانده و به عنوان ورودی دوم شبکه‌ی سر استفاده می‌کنیم.
\end{itemize}

شبکه‌ی سر، یک شبکه‌ی عصبی چند لایه است که بجز لایه‌ی آخر، تعداد نورون‌های همه‌ی لایه‌های آن ثابت بوده و در آن از واحد‌های خطی یکسو‌کننده‌ی نشت کننده به عنوان تابع فعال‌ساز استفاده می‌کنیم. تعداد لایه‌های این شبکه را با $Depth_{HeadNet}$ و تعداد نورون‌های هر لایه را با $Width_{HeadNet}$ نشان می‌دهیم. لایه‌ی آخر این شبکه برای محاسبه‌ی احتمال کلیک، دارای تنها یک نورون بوده و از تابع فعال‌ساز سیگموید برای آن استفاده می‌کنیم.

\begin{latin}
\begin{equation}
\hat{y} = HeadNet(e_{1}: e_{2}:\dots:e_{f}:I_{1, 2}:I_{1, 3}:\dots:I_{f-1, f})
\end{equation}
\end{latin}

چون مساله‌ی پیش‌بینی احتمال کلیک، جزو مسائل دسته‌بندی دو کلاسه است، پس می‌توانیم مدل پیشنهادی را با تابع هزینه‌ی خطای لگاریتمی آموزش دهیم. خطای لگاریتمی از طریق رابطه‌ی زیر محاسبه می‌شود:
\begin{latin}
\begin{equation}
LogLoss(y, \hat{y}) = - y \log(\hat{y}) - (1 - y)\log(1 - \hat{y})
\end{equation}
\end{latin}
همانطور که از رابطه‌ی خطای لگاریتمی مشخص است، این تابع برای نمونه‌های دو دسته، وزن یکسان در نظر می‌گیرد؛ اما در نظر گرفتن وزن یکسان برای هر دو دسته، در شرایطی که عدم توازن بین دسته‌ها وجود دارد، می‌تواند باعث شود مرز تصمیم گیری به سمت \trans{دسته‌ی اقلیت}{Minority Class} حرکت کرده و در نتیجه عملکرد مدل را برای نمونه‌های این دسته تضعیف کند. برای مقابله با این مشکل، روش‌های متعددی ارائه شده است. در این پژوهش، از وزن‌دهی تابع خطا استفاده می‌کنیم. وزن‌دهی تابع خطا به این صورت است که خطای نمونه‌های کلاس اکثریت را در یک ضریب کوچک و خطای نمونه‌های دسته‌ی اقلیت را در یک ضریب بیشتر ضرب می‌کنیم؛ در نتیجه میزان تاثیر دو کلاس بر تابع خطا یکسان شده و در نتیجه مشکل عدم توازن بین کلاس‌ها تا حدود زیادی حل می‌شود. خطای لگاریتمی در صورتی که از وزن دهی استفاده کنیم، به شکل زیر در می‌آید:
\begin{latin}
\begin{equation}
LogLoss(y, \hat{y}) = - y \log(\hat{y}) W_{Click} - (1 - y)\log(1 - \hat{y}) (1 - W_{Click})
\end{equation}
\end{latin}
که در آن $W_{Click}$ نسبت تعداد نمونه‌های کلیک نشده در کل مجموعه‌ی داده است.

تمامی قسمت‌های روش پیشنهادی، مشتق پذیر هستند. پس می‌توانیم همه‌ی این قسمت‌ها را \trans{سر تا سر}{End To End} با روش‌های \trans{گرادیان کاهشی دسته‌ای}{Mini-Batch Gradient Descent} آموزش دهیم. برای انجام این کار، از روش \trans{آدام}{ADAptive Moment estimation} استفاده می‌کنیم.

\section{جمع‌بندی روش پیشنهادی}
در جدول \ref{tbl:ideas} با جمع‌بندی ایده‌های استفاده شده در روش پیشنهادی و مزایای آن‌ها در مقابل چالش‌های مساله و همچنین معایب یا چالش‌های احتمالی هر کدام، این فصل را به پایان می‌بریم.

\begin{table}[!ht]
	\caption{خلاصه‌ی ایده‌های استفاده شده در روش پیشنهادی}
	\label{tbl:ideas}
	%\begin{latin}
	\scriptsize
\begin{center}
\begin{tabular}{|c|c|c|c|}
	\hline
	تکنیک مورد استفاده &
	چالش مورد نظر &
	مزایا در مقابل این چالش &
	معایب و محدودیت‌ها \\ \hline
	\multirow{4}{*}{تعبیه در ابعاد متفاوت} &
	ابعاد بالا &
	\begin{tabular}[c]{@{}c@{}}کاهش پارامتر‌های غیر ضروری\\ و جلوگیری از خطر بیش‌برازش\end{tabular} &
	\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}استفاده از عملگر‌های معمول برای\\ محاسبه‌ی تعامل امکان پذیر نیست\end{tabular}} \\ \cline{2-3}
	&
	شروع سرد &
	افزایش سرعت یادگیری به کمک تعبیه‌ی موثر &
	\\ \cline{2-4} 
	&
	سرعت آموزش &
	پارامتر‌های کمتر و افزایش سرعت آموزش &
	\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}نیاز به مشخص کردن رابطه‌ای\\ برای ابعاد بردار‌های تعبیه‌ی هر فیلد\end{tabular}} \\ \cline{2-3}
	&
	سرعت اجرا &
	محاسبات کمتر و افزایش سرعت پیش‌بینی &
	\\ \hline
	\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}محاسبه‌ی تعامل به کمک\\ شبکه‌های عصبی چند لایه\end{tabular}} &
	مدل‌سازی بهتر &
	استخراج تعامل‌ها با پیچیدگی بیشتر &
	افزایش جزئی خطر بیش‌برازش \\ \cline{2-4} 
	&
	شروع سرد &
	\begin{tabular}[c]{@{}c@{}}بهره گیری از فضای چگال بردار‌های\\ تعبیه برای محاسبه‌ی تعامل\end{tabular} &
	\multirow{2}{*}{لزوم استفاده از تنظیم} \\ \cline{2-3}
	&
	سرعت اجرا &
	\begin{tabular}[c]{@{}c@{}}وجود پیاده‌سازی‌های سریع\\ برای شبکه‌های عصبی چند لایه\end{tabular} &
	\\ \hline
	\multirow{2}{*}{تعامل‌های چند بعدی} &
	مدل‌سازی بهتر &
	وجود اطلاعات بیشتر در بردار‌های تعامل &
	\multirow{2}{*}{افزایش جزئی خطر بیش‌برازش} \\ \cline{2-3}
	&
	مدل‌سازی بهتر &
	عدم نیاز به تعامل‌های چند‌گانه &
	\\ \hline
	\multirow{3}{*}{\begin{tabular}[c]{@{}c@{}}ترکیب بردار‌های\\ تعبیه و تعامل\end{tabular}} &
	مدل‌سازی بهتر &
	\begin{tabular}[c]{@{}c@{}}وجود اطلاعات مفید در ویژگی‌های\\ مرتبه پایین و مرتبه بالا\end{tabular} &
	\multirow{3}{*}{افزایش جزئی خطر بیش‌برازش} \\ \cline{2-3}
	&
	شروع سرد &
	\begin{tabular}[c]{@{}c@{}}حضور ویژگی‌های مرتبه پایین در صورت\\ عدم حضور ویژگی‌های مرتبه بالا\end{tabular} &
	\\ \cline{2-3}
	&
	سرعت آموزش &
	رسیدن گرادیان از مسیر‌های متعدد به بردار‌های تعبیه &
	\\ \hline
	وزن دهی تابع خطا &
	عدم توازن بین دسته‌ها &
	جلوگیری از بایاس شدن مدل به سمت دسته‌ی اکثریت &
	کاهش جزئی سرعت همگرایی \\ \hline
\end{tabular}
\end{center}
\end{table}