**بسم الله الرحمن الرحیم **
#توضیح مختصر
سالانه میلیاردها دلار برای تبلیغات در فضای وب هزینه می شود.در موتور های جستجو، پس از این که کاربر درخواست (query)خود را وارد می کند، تبلیغات هدفمند(Targeted ads)علاوه بر پاسخ به درخواست در صفحه کاربر نمایش داده می شوند.
پیش بینی تبلیغات به شیوه (Clicked Through Rate) از مسائل یادگیری ماشین در ابعاد بسیار گسترده است که بر روی میلیاردها دلار صنعت تبلیغات آنلاین متمرکز شده است. چند مورد مطالعاتی که نتیجه بسیاری از آزمایشات آنلاین از الگوریتم های یادگیری است را در اینجا مورد بررسی قرار خواهیم داد.
سعی داریم بعد از این بررسی و توضیح مفصل این پروژه در بخش مقدمه به چند چالش که در پیاده سازی این الگوریتم در جهان واقعیت رخ می دهد بپردازیم؛چالش هایی که در نگاه نخست بیرون از مبحث یادگیری ماشین به نظر می رسد.این چالش ها و بررسی های حقیقی پروژه ما را در بهینه سازی حفظ حافظه، بهبود مصور سازی و کشف نیازهای نخست این الگوریتم و همچنین به تایید احتمال های به کار گرفته شده(کالیبراسیون)کمک خواهند کرد.
در نهایت ما در مسیری قرار خواهیم گرفت و از بسیاری از احتمالات و روش هایی که در ابتدا به نظر می رسیدند که در این پروژه سودمند بوده اما ما را از مقصد دور کرده فاصله می گیریم.
تفاوتی که در بررسی و پیمایش این پروژه با پروژه های دیگر به چشم می خورد تقابل نگاه سنتی به یادگیری ماشین و پیاده سازی آن در یک سیستم پیچیده پویا خواهد بود.[1]
----------
# کلمات کلیدی:
تبلیغ، پیش بینی، الگوریتم، CTR، یادگیری ماشین،کوئری، فیلترینگ،کاربر، کوانتیزه کردن،فضای وب، کلیک، مدل، بیشینه آنتروپی
----------
# مقدمه
تبلیغات آنلاین یک صنعت هزاران میلیونی دلاری را با موفقیت برای یادگیری ماشین به ارمغان آورده است.همه تبلیغاتی که براساس جستجو و مرتبط با آن ظاهر می شوند، تبلیغات محتوامحور، تبلیغات مصور و تمام تعلقات و تبلیغات در زمان واقعی وابسته به توانایی یادگیری مدل ها برای پیش بینی دقیق، سریع و مطمئن روش Clicked Through Rate هستند.
در این پروژه سعی داریم تا با رجوع وبررسی دقیق مورد مطالعاتی که براساس یک سری آرمایشات دقیق و بررسی شده با استفاده از موتور جستجوی گوگل برای پیش بینی CTR تبلیغات به کار گرفته شده اند به پروژه وارد شویم.
شکل 1 یک نمونه مثال را برای موتور جستجوی گوگل بررسی می کند.
البته باید بدانیم که این تبلیغ دقیقا یک نماینده کامل برای تبلیغات مرتبط با کوئری نیست اما در همین حد کافی است که کاربر بر روی آن کلیک نماید تا با یک رای مشخص شود این تبلیغ مرتبط با کوئری می باشد یا نه.
کاربران همیشه دوست دارند تبلیغات مرتبط با کوئری مخصوصی که جستجو می کنند بیابند.برای دقیق تر شدن در موضوع اجازه بدهید که نحوه ایجاد یک مدل برای پیش بینی تبلیغات مرتبط ارائه دهیم.
هنگامی که کاربر با جستجو یک کوئری q را انجام می دهد، یک مجموعه اولیه از تبلیغات کاندیدا که با کوئری q بر اساس کلمات کلیدی انتخاب شده مبلغ مرتبط هستند مشخص می شوند.
یک مکانیسم در این جا وجود دارد که مشخص می کند اگر قرار بر نمایش این تبلیغات برای کاربر باشد با چه ترتیبی نشان داده شوند و همچنین چه قیمتی برای هر کلیک بر روی تبلیغ محاسبه شود.همچنین علاوه بر موارد مذکور که توسط ناشر تبلیغات مشخص می شود یک مورد به عنوان ورودی برای هر تبلیغ(Advertisement) مشخص می شود که یک تابع P که احتمال کلیک شدن این تبلیغ در صورت نمایش داده شدن را نشان می دهد می باشد.
تمام این ویژگی ها در سیستم کاربر وابسته است به منبع انتشار تبلیغ، محتوای کوئری و فراداده هایی (metadata)که در پایگاه داده موارد مرتبط با تبلیغ موجود می باشد.
داده ها بر اساس این پیش بینی هایی که برای تحلیل سیستم تا به اینجا انجام دادیم می بایست به اصطلاح خلوت (Sparse)شوند.
بنابراین لازم است این پیش بینی ها روزانه میلیون ها بار تولید شوند و مدل هر بار بر اساس کلیک یا عدم کلیک آپدیت شود.
این بدین معناست که این نرخ از داده ها یک مجموعه بسیار عظیمی را تشکیل می دهند.در این آزمایش تولید داده بر اساس سرویس جریانی صورت می گیرد.[2]
البته برای نزدیک تر شدن این احتمال به پدیده قطعی و حتمی بهتر است یک سری از بکگراندهای کاربر برای مثال سن و جنسیت کاربر در نظر گرفته شود تا مدلی که قرار است برای تبلیغ ارائه شود جامع تر و دقیق تر باشد.
تصویری که در پایین این توضیحات خواهد آمد به سادگی تمامی مواردی را که تا این جا بررسی کردیم نشان خواهد داد.
----------
# کارهای مرتبط
جستجوهایی که توسط مبلغان حمایت می شود به طور قابل ملاحظه ای مورد توجه هم صنایع و هم مراکز تحقیقاتی دانشگاهی در دهه اخیر می باشد.برای هدف قرار دادن کاربران موتورهای جستجو به وسیله تبلیغات کارآمد،جستجوهای تبلیغاتی نیازمند حل بسیاری از مسائل مهم هستند از جمله:
1. تطابق کوئری و تبلیغ یا تبلیغاتی که مرتبط با آن باید ظاهر شوند.
2. پیش بینی کلیک برای رتبه بندی تبلیغ
3. عملیات فیلترینگ و فضاسازی برای تبلیغات کاندید
4. و تعیین قیمت برای نمایش نهایی تبلیغات
به عنوان هسته جستجوهای تبلیغاتی،پیش بینی کلیک از یادگیری ماشین استفاده می کند مانند بیشینه آنتروپی که از ویژگی ها و متغیرهای زیادی مانند کاربر، کوئری و تبلیغ بهره می برد.
استفاده از تحلیلگرهای معنایی و حتی لغوی برای برپایی ارتباط بین کوئری و تبلیغ در این قسمت می گنجد.
در کنار این ویژگی های متنی و معنایی(محتوایی)، ویژگی بازخورد کلیک ها بر اساس رویه و تاریخچه اطلاعات کلیک می تواند این پروژه را تا مرز بهبود تابع احتمال پیشبینی کلیک بر روی تبلیغ پیش ببرد.
مطالعات اخیر نیز رتبه بندی تبلیغات را در جستجوهای تبلیغی بهبود بخشیده و رفتار کاربر هم مورد بررسی قرار گرفته و **هدف حتی دستیابی به پیش بینی عمل کاربر بعد از کلیک بر روی تبلیغ است به جای بهبود پیش بینی کلیک **
این بخش را با یک مثال کوچک به پایان می بریم.(استفاده از مدل بیشینه آنتروپی)
برای فرموله کردن این روابط، تمامی اطلاعات مبنی بر کلیک و یا عدم کلیک بر روی تبلیغات کاندید مرتبط با کوئری جمع آوری می شود به طوری که هر نمونه شامل یک زوج کوئری و تبلیغ مرتبط با آن است.یک مجموعه از نمونه های کوئری-تبلیغ را در نظر بگیرید.
که در آن تابع f تمامی ابعاد زوج کوئری-تبلیغ و c عضو مجموعه دو عضوی زیر می باشد:
که 1- بیانگر این است که بر این تبلیغ کلیک نشده و 1+ بیانگر کلیک بر این تبلیغ می باشد.
با توصیف q به عنوان کوئری و a به عنوان تبلیغ برای بدست آوردن و محاسبه تابع احتمال داریم که:
مدل بیشینه آنتروپی به دلیل قدرت در ترکیب فرم های متفاوت داده های محتوایی در این جا به خوبی ظاهر شده و کار فرموله کردن تابع احتمال را برای زوج کوئری-تبلیغ را انجام میدهد.داریم که :
در آن f تابعی که از یکی از ویژگی های زوج کوئری-تبلیغ و w یک وزن مجتمع است.با فرض D به عنوان بیشینه مدل آنتروپی در می یابیم که w در این مدل وظیفه بیشینه سازی به صورت نمایی احتمال را بر عهده دارد.
----------
# آزمایش ها
برای شروع تست ها و اجرای کدها باید یک سری رفتارهای پیش بینی شده را در نظر گرفت.
یکی از بارزترین این رفتارها، اسکن فعالیت های چشمی انسان در طول مدت زمان یک جستجو و برای یک صفحه نتایج جستجو می باشد که این اسکن به ما کمک می کند تا در چه نقاطی تبلیغات نقش موثرتری ایفا می کنند.
تصویر بالا به خوبی این مطلب را تداعی می کند که در نقاط سمت بالا و راست که که قسمت مقابل نتایج می باشد بهترین قسمت برای تبلیغات خواهد بود.
رفتار دیگری که مد نظر می باشد که از روانشناسی کاربرانی که به جستجو پرداختند به دست آمده است این است هر چقدر که از نتایج اولیه فاصله می گیریم احتمال این که به تبلیغ توجه شود کاهش می یابد.
نکته بعدی این که همیشه انتظار می رود که مخاطب و یا کاربر بر روی یک سری تبلیغات مرتبط توجه بیشتری دارد به این معنی که تبلیغاتی که در یک موضوع قرار می گیرند CTR بیشتری را به خود اختصاص می دهد.
بنابر آزمایش های انجام شده click feedback انتظار می رود به انحراف کشیده شود و این موضوع برای الگوریتم یادگیری ماشین یک مشکل محسوب می شود.در این آزمایش ویژگی ها به یک فرمت گزارش تبدیل می شوند و توسط الگوریتم K-means clustering، عملیات کواتیزاسیون انجام می شود که تابع زیر مبین این مطلب خواهد بود:
در این فرمول Vi مربوط به مقدار ویژگی بعد از تبدیل لگاریتمی، Uj نیز سنتروید با هسته خوشه Cj می باشد.
هر خوشه از ویژگی ها یک سگمنت کوانتیزه را بیان می کند.ما یک سری ویژگی باینری شاخص را برای هر سگمنت در نظر می گیریم و این شاخص های باینری را به عنوان ورودی مدل بیشینه آنتروپی می دانیم.
برای ایجاد یک مدل ارتباطی بین ویژگی ها،ویژگی اتصال(conjunction) را ایحاد کرده تا تمامی زوج شاخص های باینری را متصل کند.
ما ویژگی هایی را بر اساس دامنه دانش سگمنت های متصل بیان می کنیم.
ویژگی هابعد از کوانتیزه شدن و اضافه کردن اتصالات به صورت نمایی رشد می کنند.برای محدود کردن این رشد، ویژگی های باینری و اتصالاتشان را از بین می بریم.
بعد از کوانتیزه کردن،اضافه کردن اتصالات و انتخاب، ویژگی ها به عنوان ورودی برای مدل بیشینه آنتروپی کلیک در نظر گرفته می شوند.
نمودار بالا نحوه توزیع مشاهدات کاربر-تبلیغ را نمایان می سازد و نمودار پایین clicked through rate کاربر-تبلیغ را.
----------
# روش های پیاده سازی
بعد از توضیحات مقدماتی و بسط یک سری از روش ها در فاز قبل در این قسمت در نظر داریم که برای یک نمونه آماری کوچک تئوری های ذکر شده را به مرحله پیاده سازی برسانیم.
کدهایی که در این فاز بررسی کردیم[3] [4] به مبحث یادگیری ماشین نیز پرداخته اند ولی در بین این کد ها، چند کد به عنوان نمونه انتخاب شده اند که به توضیح مختصری در مورد آن ها می پردازیم.
در ابتدا چند فایل به عنوان ساختاری مشابه پایگاه داده با زبان برنامه نویسی پایتون در نظر می گیریم.
این فایل ها که متن و محتوای جستجوی کاربر را در خود ذخیره می کنند در مرحله بعدی باید با فایلی که تمامی برچسب ها و عنوان عکس ها در خود ذخیره دارد مقایسه شود.
قسمتی از کدی که تمامی عنوان ها و برچسب های عکس ها را در خود جای داده است مشاهده می کنیم.
import os
import codecs
def readfile(filename):
result = {}
ifile = open(filename)
ad_list = ifile.readlines()
for a in ad_list:
tmp = a.strip('\r\n').split(',')
result[tmp[2]]=tmp[0]
return result
if __name__ == '__main__':
id_map = readfile('../data/ad.txt')
ofile = codecs.open('../data/label.txt','w','utf-8')
os.chdir('../data/classified')
import codecs
import string
import numpy
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
def get_label_map():
result = {}
infile = codecs.open('../data/label.txt','r','utf-8')
label_list = infile.readlines()
for l in label_list:
tmp = l.strip('\r\n').split(' ')
if result.has_key(int(tmp[1]))==0:
result[int(tmp[1])]=tmp[2]
return result
def get_train_data():
infile1 = codecs.open('../data/word_train.txt','r','utf-8')
infile2 = codecs.open('../data/word_test.txt','r','utf-8')
X_train = []
y_train = []
X_test = []
train_id = []
test_id = []
----------
# بررسی نتیجه ها
نتیجه ها را در سه عنوان اصلی بررسی خواهیم کرد:
1. ویژگی های ابزارها
2. ارزیابی بعد از مقداردهی اولیه
3. بررسی تبلیغات با نرخ مشاهده بالا
1. ویژگی های ابزارها
سوالی که در تمام این مدت برای استفاده از ابزارهای گوناگون برای پیاده سازی پیش می آید این است که چگونه استفاده از این ابزار خاص باقی متغیرها را ثابت در نظر می گیرد.در این بررسی با استفاده از روش KL-divergence، تمامی مجموعه های مرتبط با CTR های مربوط را محدود نگه می داریم.با استفاده از این روش 12 درصد به بهره وری سیستم کمک می شود. از آن جایی که مدل از logistic regression پیروی می کند می توان به سادگی پی برد که کدام ویژگی از بالاترین وزن یا پایین ترین وزن برخوردار است که همگی در جدول پایین مشخص شده اند.باید توجه داشت که وزن یک ویژگی لزوما به اهمیت آن وابستگی ندارد به خاطر این که این ویژگی ها مستقل نیستند و به هم وابسته هستند. برای مثال ویژگی termLength که تعداد کاراکترهای یک ترم را مشخص می کند به طور قطع وابسته به دیگر ویژگی ها می باشد. اگر یک ویژگی مهم برای مثال میانگین تعداد کاراکترهای یک کلمه را مشخص کند بنابراین این مدل یک وزن مثبت برای termLength در نظر خواهد گرفت.
2.ارزیابی بعد از مقداردهی اولیه
مدلی که در این پژوهش بررسی شده است قادر خواهد بود CTR تبلیغ را با دقت خاصی محاسبه کند.یک سوالی که ممکن است پرسیده شود که بعد از بررسی چه مقدار تبلیغ می توان به نتیجه مطمئن و صحیحی از CTR دست پیدا کرد؟
باید در نظر گرفت که CTR پیش بینی شده و CTR مشاهده شده را می توان با یک تکنیک خاص به هم مرتبط ساخت:
که در آن p بهترین برآورد از CTR تبلیغ می باشد و CTR قبلی از این مدل را در نظر دارد clicks مشخص کننده تعداد کلیک هایی هست که برروی تبلیغ انجام شده است و views تعداد بارهایی است که مشاهده شده است. a نیز مجموعه تمام ترم های قبلی که تعداد یکسانی مشاهده شده اند .
3.بررسی تبلیغات با نرخ مشاهده بالا
با بررسی 100 نمونه تبلیغات هوشمند که احتمال کلیک برروی آن ها بسیار بالا در نظر گرفته شده بود نتایجی بدست آمد که به تحلیل آن ها می پردازیم.
در بسیاری از سیستم ها که هدف کلی آن ها تبلیغ است تا ارائه اطلاعات، CTR با دقت بالا یک نقش حیاتی را ایفا می کند که در جدول پایین نتایج به خوبی قابل مشاهده خواهد بود.
# کارهای آینده
مسیرهای مطمئن زیادی برای پیمودن این روش وجود دارد.یکی از این مسیرها، توسعه و بسط ویژگی های مبتنی بر کاربر است که در این مقاله به اختصار در مورد یک روش بحث کردیم.
مسیر دوم بهره گیری از اطلاعات حساب کاربری کاربران(account session_based) است.تمامی فعالیت ها و تصمیمات مانند فرموله کردن کوئری ها،زمان بارگزاری صفحات بعد از کلیک بر تبلیغ هدف و همچنین ترتیب و تعداد کلیک هایی که دراین مسیر رخ می دهد همه و همه مبسوط و منتج از مدل های کلیکی شخصی می باشد[5].
یک ناحیه دیگر از تبلیغ گروه سازی کاربران بر اساس معیارهای مختلف است که کاربرانی که سلیقه های کلیکی شبیه تری دارند در یک گروه قرار بگیرند تا پیش بینی کلیک بر روی تبلیغات کاندید افزایش یابد.
# مراجع
[1]Ad Click Prediction: a View from the Trenches by H. Brendan McMahan, Gar y Holt, D. Sculley, Michael Young,Dietmar Ebner, Julian Grady, Lan Nie, Todd Phillips, Eugene Davydov,Daniel Golovin, Sharat Chikker ur, Dan Liu, Mar tin Wattenberg,Ar nar Mar Hrafnkelsson, Tom Boulos, Jeremy Kubica at Google, Inc.
[2] CTR Predictions and Literature References ,CSE599s, Spring 2014, Online Learning,Lecture 20 - 6/5/2014
[3]https://github.com/MLWave/kaggle-criteo
[4]https://github.com/ivanliu1989/AVAZU-CTR-Prediction
[5]Personaliz ed Click Prediction in Sponsored Search by Haibin Cheng,Erick Cant
+ http://stats.stackexchange.com/questions/105264/data-preparation-and-machine-algo-for-ad-click-prediction
+ https://leve.rs/blog/google-ad-click-prediction-humans/
+ http://mlwave.com/predicting-click-through-rates-with-online-machine-learning/