بسم الله الرحمن الرحیم
۱. توضیح مختصر
سالانه میلیاردها دلار برای تبلیغات در فضای وب هزینه می شود.در موتور های جستجو، پس از این که کاربر درخواست (query)خود را وارد می کند، تبلیغات هدفمند(Targeted ads)علاوه بر پاسخ به درخواست در صفحه کاربر نمایش داده می شوند.
پیش بینی تبلیغات به شیوه (Clicked Through Rate) از مسائل یادگیری ماشین در ابعاد بسیار گسترده است که بر روی میلیاردها دلار صنعت تبلیغات آنلاین متمرکز شده است. چند مورد مطالعاتی که نتیجه بسیاری از آزمایشات آنلاین از الگوریتم های یادگیری است را در اینجا مورد بررسی قرار خواهیم داد.
سعی داریم بعد از این بررسی و توضیح مفصل این پروژه در بخش مقدمه به چند چالش که در پیاده سازی این الگوریتم در جهان واقعیت رخ می دهد بپردازیم؛چالش هایی که در نگاه نخست بیرون از مبحث یادگیری ماشین به نظر می رسد.این چالش ها و بررسی های حقیقی پروژه ما را در بهینه سازی حفظ حافظه، بهبود مصور سازی و کشف نیازهای نخست این الگوریتم و همچنین به تایید احتمال های به کار گرفته شده(کالیبراسیون)کمک خواهند کرد.
در نهایت ما در مسیری قرار خواهیم گرفت و از بسیاری از احتمالات و روش هایی که در ابتدا به نظر می رسیدند که در این پروژه سودمند بوده اما ما را از مقصد دور کرده فاصله می گیریم.
تفاوتی که در بررسی و پیمایش این پروژه با پروژه های دیگر به چشم می خورد تقابل نگاه سنتی به یادگیری ماشین و پیاده سازی آن در یک سیستم پیچیده پویا خواهد بود.[1]
۲. کلمات کلیدی:
تبلیغ، پیش بینی، الگوریتم، CTR، یادگیری ماشین،کوئری، فیلترینگ،کاربر، کوانتیزه کردن،فضای وب، کلیک، مدل، بیشینه آنتروپی
۳. مقدمه
تبلیغات آنلاین یک صنعت هزاران میلیونی دلاری را با موفقیت برای یادگیری ماشین به ارمغان آورده است.همه تبلیغاتی که براساس جستجو و مرتبط با آن ظاهر می شوند، تبلیغات محتوامحور، تبلیغات مصور و تمام تعلقات و تبلیغات در زمان واقعی وابسته به توانایی یادگیری مدل ها برای پیش بینی دقیق، سریع و مطمئن روش Clicked Through Rate هستند.
در این پروژه سعی داریم تا با رجوع وبررسی دقیق مورد مطالعاتی که براساس یک سری آرمایشات دقیق و بررسی شده با استفاده از موتور جستجوی گوگل برای پیش بینی CTR تبلیغات به کار گرفته شده اند به پروژه وارد شویم.
شکل 1 یک نمونه مثال را برای موتور جستجوی گوگل بررسی می کند.
البته باید بدانیم که این تبلیغ دقیقا یک نماینده کامل برای تبلیغات مرتبط با کوئری نیست اما در همین حد کافی است که کاربر بر روی آن کلیک نماید تا با یک رای مشخص شود این تبلیغ مرتبط با کوئری می باشد یا نه.
کاربران همیشه دوست دارند تبلیغات مرتبط با کوئری مخصوصی که جستجو می کنند بیابند.برای دقیق تر شدن در موضوع اجازه بدهید که نحوه ایجاد یک مدل برای پیش بینی تبلیغات مرتبط ارائه دهیم.
هنگامی که کاربر با جستجو یک کوئری q را انجام می دهد، یک مجموعه اولیه از تبلیغات کاندیدا که با کوئری q بر اساس کلمات کلیدی انتخاب شده مبلغ مرتبط هستند مشخص می شوند.
یک مکانیسم در این جا وجود دارد که مشخص می کند اگر قرار بر نمایش این تبلیغات برای کاربر باشد با چه ترتیبی نشان داده شوند و همچنین چه قیمتی برای هر کلیک بر روی تبلیغ محاسبه شود.همچنین علاوه بر موارد مذکور که توسط ناشر تبلیغات مشخص می شود یک مورد به عنوان ورودی برای هر تبلیغ(Advertisement) مشخص می شود که یک تابع P که احتمال کلیک شدن این تبلیغ در صورت نمایش داده شدن را نشان می دهد می باشد.
تمام این ویژگی ها در سیستم کاربر وابسته است به منبع انتشار تبلیغ، محتوای کوئری و فراداده هایی (metadata)که در پایگاه داده موارد مرتبط با تبلیغ موجود می باشد.
داده ها بر اساس این پیش بینی هایی که برای تحلیل سیستم تا به اینجا انجام دادیم می بایست به اصطلاح خلوت (Sparse)شوند.
بنابراین لازم است این پیش بینی ها روزانه میلیون ها بار تولید شوند و مدل هر بار بر اساس کلیک یا عدم کلیک آپدیت شود.
این بدین معناست که این نرخ از داده ها یک مجموعه بسیار عظیمی را تشکیل می دهند.در این آزمایش تولید داده بر اساس سرویس جریانی صورت می گیرد.[2]
البته برای نزدیک تر شدن این احتمال به پدیده قطعی و حتمی بهتر است یک سری از بکگراندهای کاربر برای مثال سن و جنسیت کاربر در نظر گرفته شود تا مدلی که قرار است برای تبلیغ ارائه شود جامع تر و دقیق تر باشد.
تصویری که در پایین این توضیحات خواهد آمد به سادگی تمامی مواردی را که تا این جا بررسی کردیم نشان خواهد داد.
۴. کارهای مرتبط
جستجوهایی که توسط مبلغان حمایت می شود به طور قابل ملاحظه ای مورد توجه هم صنایع و هم مراکز تحقیقاتی دانشگاهی در دهه اخیر می باشد.برای هدف قرار دادن کاربران موتورهای جستجو به وسیله تبلیغات کارآمد،جستجوهای تبلیغاتی نیازمند حل بسیاری از مسائل مهم هستند از جمله:
تطابق کوئری و تبلیغ یا تبلیغاتی که مرتبط با آن باید ظاهر شوند.
پیش بینی کلیک برای رتبه بندی تبلیغ
عملیات فیلترینگ و فضاسازی برای تبلیغات کاندید
و تعیین قیمت برای نمایش نهایی تبلیغات
به عنوان هسته جستجوهای تبلیغاتی،پیش بینی کلیک از یادگیری ماشین استفاده می کند مانند بیشینه آنتروپی که از ویژگی ها و متغیرهای زیادی مانند کاربر، کوئری و تبلیغ بهره می برد.
استفاده از تحلیلگرهای معنایی و حتی لغوی برای برپایی ارتباط بین کوئری و تبلیغ در این قسمت می گنجد.
در کنار این ویژگی های متنی و معنایی(محتوایی)، ویژگی بازخورد کلیک ها بر اساس رویه و تاریخچه اطلاعات کلیک می تواند این پروژه را تا مرز بهبود تابع احتمال پیشبینی کلیک بر روی تبلیغ پیش ببرد.
مطالعات اخیر نیز رتبه بندی تبلیغات را در جستجوهای تبلیغی بهبود بخشیده و رفتار کاربر هم مورد بررسی قرار گرفته و هدف حتی دستیابی به پیش بینی عمل کاربر بعد از کلیک بر روی تبلیغ است به جای بهبود پیش بینی کلیک
این بخش را با یک مثال کوچک به پایان می بریم.(استفاده از مدل بیشینه آنتروپی)
برای فرموله کردن این روابط، تمامی اطلاعات مبنی بر کلیک و یا عدم کلیک بر روی تبلیغات کاندید مرتبط با کوئری جمع آوری می شود به طوری که هر نمونه شامل یک زوج کوئری و تبلیغ مرتبط با آن است.یک مجموعه از نمونه های کوئری-تبلیغ را در نظر بگیرید.
که در آن تابع f تمامی ابعاد زوج کوئری-تبلیغ و c عضو مجموعه دو عضوی زیر می باشد:
که 1- بیانگر این است که بر این تبلیغ کلیک نشده و 1+ بیانگر کلیک بر این تبلیغ می باشد.
با توصیف q به عنوان کوئری و a به عنوان تبلیغ برای بدست آوردن و محاسبه تابع احتمال داریم که:
مدل بیشینه آنتروپی به دلیل قدرت در ترکیب فرم های متفاوت داده های محتوایی در این جا به خوبی ظاهر شده و کار فرموله کردن تابع احتمال را برای زوج کوئری-تبلیغ را انجام میدهد.داریم که :
در آن f تابعی که از یکی از ویژگی های زوج کوئری-تبلیغ و w یک وزن مجتمع است.با فرض D به عنوان بیشینه مدل آنتروپی در می یابیم که w در این مدل وظیفه بیشینه سازی به صورت نمایی احتمال را بر عهده دارد.
۵. آزمایش ها
بنابر آزمایش های انجام شده click feedback انتظار می رود به انحراف کشیده شود و این موضوع برای الگوریتم یادگیری ماشین یک مشکل محسوب می شود.در این آزمایش ویژگی ها به یک فرمت گزارش تبدیل می شوند و توسط الگوریتم K-means clustering، عملیات کواتیزاسیون انجام می شود که تابع زیر مبین این مطلب خواهد بود:
در این فرمول Vi مربوط به مقدار ویژگی بعد از تبدیل لگاریتمی، Uj نیز سنتروید با هسته خوشه Cj می باشد.
هر خوشه از ویژگی ها یک سگمنت کوانتیزه را بیان می کند.ما یک سری ویژگی باینری شاخص را برای هر سگمنت در نظر می گیریم و این شاخص های باینری را به عنوان ورودی مدل بیشینه آنتروپی می دانیم.
برای ایجاد یک مدل ارتباطی بین ویژگی ها،ویژگی اتصال(conjunction) را ایحاد کرده تا تمامی زوج شاخص های باینری را متصل کند.
ما ویژگی هایی را بر اساس دامنه دانش سگمنت های متصل بیان می کنیم.
ویژگی هابعد از کوانتیزه شدن و اضافه کردن اتصالات به صورت نمایی رشد می کنند.برای محدود کردن این رشد، ویژگی های باینری و اتصالاتشان را از بین می بریم.
بعد از کوانتیزه کردن،اضافه کردن اتصالات و انتخاب، ویژگی ها به عنوان ورودی برای مدل بیشینه آنتروپی کلیک در نظر گرفته می شوند.
نمودار بالا نحوه توزیع مشاهدات کاربر-تبلیغ را نمایان می سازد و نمودار پایین clicked through rate کاربر-تبلیغ را.
۶. کارهای آینده
مسیرهای مطمئن زیادی برای پیمودن این روش وجود دارد.یکی از این مسیرها، توسعه و بسط ویژگی های مبتنی بر کاربر است که در این مقاله به اختصار در مورد یک روش بحث کردیم.
مسیر دوم بهره گیری از اطلاعات حساب کاربری کاربران(account session_based) است.تمامی فعالیت ها و تصمیمات مانند فرموله کردن کوئری ها،زمان بارگزاری صفحات بعد از کلیک بر تبلیغ هدف و همچنین ترتیب و تعداد کلیک هایی که دراین مسیر رخ می دهد همه و همه مبسوط و منتج از مدل های کلیکی شخصی می باشد[3].
یک ناحیه دیگر از تبلیغ گروه سازی کاربران بر اساس معیارهای مختلف است که کاربرانی که سلیقه های کلیکی شبیه تری دارند در یک گروه قرار بگیرند تا پیش بینی کلیک بر روی تبلیغات کاندید افزایش یابد.
۷. مراجع
[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]Personaliz ed Click Prediction in Sponsored Search by Haibin Cheng,Erick Cant