haji_thesis/Thesis/chap1.tex

% !TEX encoding = UTF-8 Unicode
\chapter{مقدمه}\label{Chap:Chap1}

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

امروزه با گسترش اینترنت، شاهد تاثیرگذاری آن بر اکثر جنبه‌های زندگی بشری، از جمله اقتصاد هستیم. یکی از نمود‌های این تاثیرگذاری، ظهور تبلیغات آنلاین در مقابل گونه‌های سنتیِ آن است. مقرون به صرفه بودن، در دسترس بودن در مقیاس جهانی و قابلیت گرفتن بازخورد مستقیم از کاربران مورد نظر از جمله برتری‌های قابل توجه تبلیغات آنلاین است.

تبلیغات آنلاین، به شیوه‌های متنوعی انجام می‌شود.\cite{choi2020online} تعدادی از گونه‌های این نوع تبلیغات، وبسایت‌ها، \trans{شبکه‌های اجتماعی}{Social Networks}، \trans{تبلیغات کلمه کلیدی}{Keyword Advertising}، \trans{بهینه‌سازی موتور‌های جستجو}{SEO} و \trans{تبلیغات نمایشی}{Display Advertising} هستند.

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

\section{معرفی انواع معاملات در تبلیغات نمایشی}
از آنجا که درآمد بسیاری از صاحبان صفحات وب، تنها از تبلیغات نمایشی انجام شده در وب‌سایت‌هایشان حاصل می‌شود، انتخاب نحوه‌ی قرارداد با \trans{تبلیغ کننده}{Advertisier}‌ها اهمیت زیادی برای آن‌ها دارد.\cite{yuan2014survey} در این بخش به طور مختصر انواع قرارداد‌های رایج بین تبلیغات کننده‌ها و صاحبان صفحات وب را توضیح می‌دهیم.


\begin{itemize}
\item \textbf{قرارداد‌های مستقیم}


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


در بقیه‌ی روش‌ها، که جزء شاخه‌ی برنامه‌ریزی شده طبقه بندی می‌شوند، با رعایت کردن یک استاندارد مشترک، میزان هزینه و زحمت مورد نیاز کاهش یافته و فرآیند سریعتر انجام می‌شود. معاملات برنامه‌ریزی شده به دو دسته‌ی \trans{معاملات تضمین شده}{Guaranteed Deals} و \trans{مزایده‌ی بلادرنگ}{Realtime Bidding (RTB)} تقسیم می‌شوند.
\begin{itemize}
\item \textbf{قرارداد‌های تضمین شده}

در این دسته از قرارداد‌ها، هزینه و تعداد بنر‌هایی که باید به کاربران نشان داده شوند، از پیش تعیین می‌شود. نکته‌ی حائز اهمیت در این دسته از قرارداد‌ها، اضافه شدن سیستم‌هایی است که به صورت اتوماتیک بخش‌های قابل توجهی از فرآیند نمایش تبلیغ را انجام داده و با حذف دخالت انسانی، هزینه‌ها و زحمات کار را به شدت کاهش می‌دهند. دو دسته‌ی مهم از این قرارداد‌ها، دسته‌ی \trans{قرارداد‌های تضمین شده‌ی اتوماتیک}{Automated Guaranteed Deals} و \trans{قرارداد‌های تضمین شده‌ی برنامه‌ریزی شده}{Programmatic Guaranteed Deals} نامیده می‌شوند.
\begin{itemize}
\item \textbf{قرارداد‌های تضمین شده‌ی اتوماتیک}

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

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

\end{itemize}
\item \textbf{مزایده‌ی بلادرنگ}

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

در \trans{مزایده‌های بلادرنگ آزاد}{Open Realtime Auction}، هربار که یک کاربر به یکی از صفحات دارای کادر مناسب برای تبلیغ وارد می‌شود، همه‌ی تبلیغ کنندگان می‌توانند یک قیمت برای نمایش تبلیغ خود به کاربر، پیشنهاد دهند و تبلیغ دارای بالاترین پیشنهاد قیمت، به کاربر نمایش داده می‌شود. امروزه این نوع معامله به دلیل هزینه‌ی پایین برای تبلیغ کنندگان و درآمد بالا برای صاحبان صفحات وب، میزان قابل توجهی از تبلیغات کنندگان و صاحبان صفحات وب در سراسر جهان را به خود جذب کرده است.
\item \textbf{مزایده‌ی بلادرنگ خصوصی}

در \trans{مزایده‌های بلادرنگ خصوصی}{Private Realtime Auction}، تبلیغات کنندگان باید قبل از شروع فرآیند تبلیغ وارد قرارداد شده و با قبول شرایط اولیه‌ای که صاحب صفحات وب پیشنهاد می‌کند، وارد فرآیند مزایده شود.
\end{itemize}
\end{itemize}
\end{itemize}
در این پایان نامه، بر نوع مزایده‌های بلادرنگ آزاد تمرکز خواهیم داشت و جزئیات و چالش‌های مربوط به آن را بررسی خواهیم کرد.
\section{اجزا و نحوه‌ی اجرای مزایده‌های بلادرنگ}
در عمل، برای انجام مزایده‌های بلادرنگ، به اجزا و نقش‌های متنوعی نیاز است.\cite{yuan2014survey} در این بخش اصطلاحات استفاده شده در مزایده‌های بلادرنگ و همچنین اجزا و نقش‌های آن را تعریف کرده و توضیح می‌دهیم.
\subsection{کاربر}
تعریف کاربر در مزایده‌های بلادرنگ، با تعریفی که در بخش قبل ذکر شد، تفاوت چندانی ندارد. تنها فرق جزئی در این نکته است که اینجا، تمرکز بیشتر روی مرورگری است که کاربر استفاده می‌کند و اعمالی که در این بخش به کاربر نسبت می‌دهیم، عملا توسط مرورگر کاربر انجام می‌شود و خود کاربر اطلاعی از انجام آن‌ها ندارد.
\subsection{ناشر}
در ادبیات مزایده‌های بلادرنگ، \trans{ناشر}{Publisher} به وب‌سایتی اشاره می‌کند که در آن امکان انجام تبلیغات وجود دارد و لذا [بخشی از] درآمد این وب‌سایت از تبلیغات است. از ملزومات اجرای فرآیند مزایده‌های بلادرنگ، وجود اسکریپت‌های مربوط به سکوی سمت تامین در این صفحه است.
\subsection{سکوی سمت تامین}
\trans{سکوی سمت تامین}{Supply Side Platform}
به بخشی از زیرساخت اطلاق می‌شود که با تعدادی ناشر قرارداد بسته و از طریق تعدادی اسکریپت که در سایت ناشر‌ها تعبیه کرده است، اجرای فرآیند مزایده را ممکن می‌سازد.

این اسکریپت‌ها، برخی اطلاعات از جمله سوابق مرور کاربر در همه‌ی وب‌سایت‌هایی که این اسکریپت در آن‌ها وجود دارد را به سکوی سمت تامین ارسال کرده و در هنگام نیاز به نمایش تبلیغ، اطلاعاتی از جمله موقعیت جغرافیایی، نحوه‌ی اتصال به وب‌سایت (موبایل، تبلت یا کامپیوتر) و حتی نحوه‌ی ورود به وب‌سایت (موتور جستجو، ایمیل تبلیغاتی، لینک توصیه شده از طرف کاربر دیگر و ...) را به این سکو ارسال می‌کند؛ لذا سکوی سمت تامین اطلاعات جامعی از این کاربر در اختیار داشته و بر اساس این اطلاعات، تبلیغات مناسب را در اختیار کاربر قرار دهد.
\subsection{سکوی سمت نیاز}
\trans{سکوی سمت نیاز}{Demand Side Platform}
به بخشی از زیرساخت اطلاق می‌شود که با تعدادی تبلیغ کننده (بازاریاب) ارتباط داشته و عملا شرکت‌کننده‌های اصلی مزایده، آن‌ها هستند. سکو‌های سمت نیاز برای هر \trans{موقعیت قابل تبلیغ}{Impression} وارد مزایده شده و قیمت پیشنهادی خود را برای انجام تبلیغ ارائه می‌کنند.

\subsection{تبلیغ کننده}
تبلیغ کننده (\trans{بازاریاب}{Marketer}) در بخش قبلی به صورت کامل تعریف شده است. آن‌ها برای انجام تبلیغ و بازاریابی کالا یا خدماتی که ارائه می‌دهند، دست به تبلیغ زده و بودجه‌ی قابل توجهی را روانه‌ی زیرساخت‌های تبلیغاتی می‌کنند. بازاریاب‌ها با سکو‌های سمت نیاز قرارداد بسته و تبلیغات خود را به آن‌ها ارائه کرده و به ازای تعداد کلیک کاربران روی تبلیغاتشان، به آن‌ها پرداخت می‌کنند. به عنوان مثال، سکوی سمت نیاز در قراردادی تضمین می‌کند تعداد 1000 کلیک بر روی بنر تبلیغاتی یکی از تبلیغ کننده‌ها تامین کرده و در قبال آن، هزینه‌ای دریافت کند.
\subsection{اجرای فرآیند مزایده‌های بلادرنگ}
فرآیند مزایده‌ی بلادرنگ، از کاربر شروع می‌شود. زمانی که کاربر وارد صفحه‌ای متعلق به یک ناشر می‌شود، مرورگر کاربر یک درخواست برای نمایش وب‌سایت ناشر ارسال می‌کند(1).
وب‌سایت ناشر،‌ صفحه‌ی \trans{اچ‌تی‌ام‌ال}{HTML} خود را برای کاربر ارسال کرده و همزمان لینک مربوط به اسکریپت سکوی سمت تامین را در اختیار کاربر می‌گذارد(2).
کاربر برای بارگیری صفحه‌ی اچ‌تی‌ام‌ال دریافتی، سراغ تک‌تک منابع رفته و هرکدام را بارگیری می‌کند. برای نمایش اطلاعاتی که در کادر تبلیغ وجود دارد،‌ کاربر یک درخواست \trans{اچ‌تی‌تی‌پی}{HTTP} به سکوی سمت تامین ارسال می‌کند(3).
در این مرحله، سکوی سمت تامین وارد عمل شده و موقعیت قابل تبلیغ و اطلاعات کاربر را از قبیل سابقه‌ی کاربر، مشخصات و سابقه‌ی سایت ناشر و اطلاعات مربوط به ابعاد کادر تبلیغ به تمامی سکو‌های سمت نیاز در دسترس ارسال می‌کند(4).
هر سکوی سمت نیاز با در نظر گرفتن تبلیغِ خود، با استفاده از روش‌های مختلف (که نمونه‌های آن در فصل 2 توضیح داده می‌شود) یک قیمت به عنوان هزینه‌ی پیشنهادی نمایش تبلیغ ارائه می‌دهد. پیشنهادی که بیشترین قیمت را پیشنهاد داده باشد، برنده‌ی مزایده می‌شود. پیشنهاد برنده با خط‌چین نمایش داده شده است(5).
پس از دریافت هزینه‌های پیشنهادی سکو‌های سمت نیاز، سکو‌های سمت تامین بالاترین قیمت را انتخاب کرده و لینک سکوی سمت نیاز برنده را به کاربر ارسال می‌کند(6).
کاربر با کسب اطلاع از آدرس مشخصات سکوی سمت نیاز برنده، برای اطلاع از محل نهایی بنر تبلیغ انتخاب شده، به آن آدرس رجوع می‌کند(7).
سکوی سمت نیاز برنده به درخواست کاربر پاسخ داده و آدرس بنر (که در سرور متعلق به بازاریاب است) را برای کاربر ارسال می‌کند(8).
کاربر به آدرس بنر رجوع می‌کند(9).
سرور بازاریاب بنر تبلیغ را به کاربر ارسال می‌کند(10).
مراحل اجرای این فرآیند در شکل \ref{fig:rtb-process} قابل ملاحظه است.

نکته‌ی قابل توجه در فرآیند مزایده‌ی بلادرنگ، تفاوت نوع قرارداد‌های بسته شده بین سکو‌های سمت نیاز با تبلیغ کننده‌ها و سکو‌های سمت تامین با ناشران است. سکو‌های سمت تامین به ازای \textbf{نمایش} هر تبلیغ به ناشران مبلغی پرداخت می‌کنند؛ اما سکو‌های سمت تامین به ازای هر \textbf{کلیک انجام شده} روی بنر‌های تبلیغ کننده‌ها، مبلغی از آن‌ها دریافت می‌کنند؛ بنابراین برای تضمین سود‌دهی این سیستم، باید تبلیغاتی برای نمایش به کاربران انتخاب شوند که احتمال کلیک شدن روی آن‌ها قابل توجه باشد؛ پس تخمین این احتمال که به \trans{نرخ کلیک}{Click Through Rate} معروف است، به یک مساله‌ی محوری در این فرآیند تبدیل می‌شود.\cite{qin2019revenue}

لازم به ذکر است در برخی قرارداد‌های دیگر، نوع قرارداد بین سکو‌های سمت تامین و تبلیغ کنندگان، به جای تضمین تعداد کلیک انجام شده، تضمین تعداد خرید انجام شده از طریق بنر مربوطه است؛ پس به جای تخمین نرخ کلیک، احتمال انجام خرید از طریق تبلیغ نمایش داده شده تخمین زده می‌شود که به \trans{نرخ تبدیل}{Convertion Rate} معروف است. در عمل می‌توان نرخ تبدیل را ضریبی از نرخ کلیک در نظر گرفت که به دلیل تنک بودن، کار کردن با آن چالش بیشتری دارد. در این پژوهش به دلیل محدودیت در مجموعه‌های داده‌ی انتخاب شده، تنها از نرخ کلیک استفاده می‌کنیم.
\begin{figure}
	\center
	\includegraphics[width=0.9\textwidth]{images/RTB_Process}
	\caption{
فرآیند مزایده‌ی بلادرنگ
	}
	\label{fig:rtb-process}
\end{figure}
%==================================================================
\section{چالش‌ها}
در تخمین نرخ کلیک و نرخ تبدیل، چالش‌هایی وجود دارند که کار پژوهش در این موضوع را دچار مشکل می‌کنند. در این بخش به اختصار در مورد این چالش‌ها بحث می‌کنیم.
\begin{itemize}
\item \trans{چالش عدم توازن شدید کلاس‌ها}{High class imbalance challenge}

هنگام دسته‌بندی دودویی در مساله‌ای که داده‌ها به صورت نامتوازن هستند، با چالش جدی عدم توازن کلاس‌ها روبرو هستیم.\cite{reference/ml/LingS17} در تبلیغات نمایشی، در بیشتر موارد کاربر روی تبلیغ کلیک نمی‌کند و یا پس از کلیک، بازدید کاربر از صفحه‌ی مقصد به خرید (تبدیل) منتهی نمی‌شود و این شرایط باعث می‌شود این مساله نیز جزء مسائل مواجه با چالش عدم توازن شدید کلاس‌ها باشد.
\item \trans{چالش ابعاد بالا}{High dimentionality challenge}

به دلیل وجود تعداد ابعاد ورودی بسیار بالا، رویارویی با این مساله با الگوریتم‌های ساده‌ی یادگیری ممکن نیست. این مشکل با نام دیگر \trans{نفرین ابعاد}{Curse of dimentionality} نیز معروف است. نفرین ابعاد باعث می‌شود تعداد پارامتر‌های مدل بیشتر شده و در نتیجه فرآیند یادگیری آن دچار مشکلات متنوعی شود.\cite{pires2019high}
\item \trans{چالش شروع سرد}{Cold start challenge}

وقتی یک تبلیغ جدید برای نمایش اضافه می‌شود، سکو‌های سمت نیاز هیچ اطلاعاتی در مورد آن و کاربر‌هایی که احتمالا به آن تبلیغ علاقه نشان دهند، ندارند؛ لذا تعداد زیادی از موقعیت‌های قابل تبلیغ و در نتیجه میزان قابل توجهی هزینه صرف شناسایی تبلیغ جدید می‌شود. از طرفی، کاربر جدیدی که شروع به بازدید از صفحات مربوط به ناشرین می‌کند، از طرف سکو‌های سمت تامین مورد نظر شناخته شده نیست؛ پس وقت و هزینه‌ی زیادی صرف شناختن سلایق این کاربر جدید می‌شود. این مشکل در ادبیات \trans{سیستم‌های پیشنهاد دهنده}{Recommender systems} به نام شروع سرد معروف است.\cite{journals/eswa/LikaKH14, DBLP:journals/corr/abs-1004-3732}

\item چالش سرعت آموزش

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

\end{itemize}
\section{هدف پژوهش}

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

\section{پرسش‌های اساسی پژوهش}

برای رسیدن به هدف کلی این پژوهش که ارائه‌ی یک راهکار جدید برای تخمین نرخ کلیک است، باید مشخص شود که \textbf{چه راهکاری برای مواجهه با چالش‌های موجود، مناسب بوده و می‌تواند با وجود همه‌ی این چالش‌ها تخمین قابل قبولی از نرخ کلیک ارائه دهد؟} بنابراین، پرسش‌های زیر پیش‌رویمان خواهد بود:
\begin{enumerate}
\item روش‌های موجود برای تخمین نرخ کلیک در تبلیغات نمایشی، کدامند؟
\item هریک از چالش‌های مهم تخمین نرخ کلیک، چه تاثیری بر عملکرد روش‌ها می‌گذارند؟
\item روش مناسبی که با این چالش‌ها رویارو شود، باید چه ویژگی‌هایی داشته باشد؟
\end{enumerate}

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