اپیزود‌های یادگیری

1.1.1       اپیزود‌های یادگیری

از آنجائیکه در محیط یک حالت هدف جذب کننده[1] در نظر گرفته میشود که با قرار گرفتن عامل درآن حرکت عامل متوقف میشود، عمل یادگیری بصورت اپیزودی انجام میشود. در هر اپیزود عامل در یک محل تصادفی قرار داده می‌شود و تا رسیدن به حالت جذبی به تغییر مقادیر Q ادامه میدهد.

اگر مقادیر اولیه Q  صفر در نظر گرفته شده باشند، در هر اپیزود فقط یکی از مقادیر که به مقدار نهائی نزدیکتر هستند تغییر کرده و بقیه صفر باقی میمانند. با افزایش تکرار اپیزود‌ها این مقادیر غیر صفر به سایر مقادیر جدول گسترش پیدا کرده و درنهایت به مقادیر بهینه همگرا خواهند شد.

1.2        آزمون کای

آزمون خی‌دو[2] یا آزمون کی دو یا خی دو یا مربع کای یا χ²  از آزمون‌های آماری و از نوع ناپارامتری است و برای ارزیابی همقوارگی متغیرهای اسمی‌به کار می‌رود:

رابطه 2-5

که در آن:

O : فراوانیهای مشاهده شده

E : فراوانیهای مورد انتظار

آزمون بدون توزیع است. فراوانی‌های مورد انتظار نباید در هیچ مقوله‌ای صفر باشد. مجموع مقوله‌هایی که مقدار مشاهدات مربوط به آنها کمتر از ۵ است، نباید بیش از ۲۰ درصد کل مقوله‌ها باشد. این آزمون تنها راه حل موجود برای آزمون همقوارگی در مورد متغیرهای مقیاس اسمی‌ با بیش از دو مقوله‌ است، بنابراین کاربرد بیشتری نسبت به آزمونهای دیگر دارد. این آزمون نسبت به حجم نمونه حساس است.[28]

1.3       معیار دقت [3] و معیار بازخوانی[4]

بازیابی اطلاعات[5]  به فناوری و دانش پیچیده‌ی جستجو و استخراج اطلاعات، داده‌ها، فراداده‌ها در انواع گوناگون منابع اطلاعاتی مثل بانک اسناد، مجموعه‌ای از تصاویر، و وب گفته می‌شود. با افزایش روز افزون حجم اطلاعات ذخیره شده در منابع قابل دسترس و گوناگون، فرایند بازیابی و استخراج اطلاعات اهمیت ویژه‌ای یافته است. اطلاعات مورد نظر ممکن است شامل هر نوع منبعی مانند متن، تصویر، صوت و ویدئو باشد[29]. بر خلاف پایگاه داده‌ها، اطلاعات ذخیره شده در منابع اطلاعاتی بزرگ مانند وب و زیرمجموعه‌های آن مانند شبکه‌های اجتماعی از ساختار مشخصی پیروی نمی‌کنند و عموماً دارای معانی تعریف شده و مشخصی نیستند. هدف بازیابی اطلاعات در چنین شرایطی، کمک به کاربر برای یافتن اطلاعات مورد نظر در انبوهی از اطلاعات ساختارنایافته است.

جستجوگرهای گوگل، یاهو و بینگ سه نمونه از پراستفاده‌ترین سیستم‌های بازیابی اطلاعات هستند که به کاربران برای بازیابی اطلاعات متنی، تصویری، ویدئویی و غیره کمک می‌کنند. «بازیابی اطلاعات» در برخی منابع فارسی به اشتباه به جای ذخیره و بازیابی داده‌ها که به معنای دانش شناخت رسانه‌های ذخیره‌سازی فیزیکی است، به کار رفته است.

1.3.1       معیارهای ارزیابی

معیار دقت: به حاصل تقسیم «تعداد مستندات بازیابی شده‌ی واقعاً مرتبط» بر «تعداد کل مستندات بازیابی شده» گفته می‌شود.[29]

معیار بازخوانی: به حاصل تقسیم «تعداد مستندات بازیابی شده‌ی مرتبط» بر «تعداد کل مستندات باربط مرتبطی که در مجموعه‌ی اطلاعاتی موجود بوده است» گفته می‌شود.[29]

 

شکل2‑12- معیار دقت و معیار بازخوانی [45]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2         فصل سوم

روش‌شناسی تحقیق

 

 

 

 

 

2.1       مقدمه

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

در بخش دوم پژوهش با توجه به اینکه تشخیص گرایش در زمان قابل قبول در بخش اول محقق شده است، طي يك  فاز آموزش قصد داريم پست‌هاي مربوطه را در اين وبلاگ‌ها بررسي كرده و پرگرایش‌ترین[6] عناوین را مشخص ‌كنيم و سپس در فاز آزمايش پرگرایش‌ترین عنوان در اين اجتماع را براي دوره‌هاي زماني بعدي پيش‌بيني كنيم. در این راه تاکید ما بر نحوه‌ی تاثیر الگوریتم بر حل مسئله ( و در عین حال مشاهده‌ی رفتار گروهی یک اجتماع در یک دوره‌ی زمانی کوتاه) است و اینکه دقت الگوریتم انتخاب شده به چه میزانی است و ‌در این پیش‌بینی به چه عواملی وابسته است. همچنین اینکه چگونه این الگوریتم یک مدل مناسب از انتخاب‌های فردی و تصمیمات جمعی ارائه می‌دهد و چطور می‌توان نگاشتی بین الگو‌های رفتاری کشف شده با تفسیر‌ها واقعی کشف کرد.

2.2       مدل  ارائه‌شده

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

همچنین از میان الگوریتم‌های مبتنی بر هوش جمعی الگوریتم،‌ PSO نتایج بهتری در خوشه‌بندی داده‌ها هم از نظر سرعت و هم از نظر دقت داشته [24] ، و هم‌چنین کیفیت راه‌حل و نرخ موفقیت PSO نسبت به دیگر الگوریتم‌های هوش مصنوعی نیز بالاتر بوده است [25] . البته در [25] ، PSO با کلونی مورچه[7] هم مقایسه شده و دقت و نرخ موفقیت بیشتری داشته اما سرعت آن کمی‌کمتر از کلونی مورچه بوده، این درحالی است که دقت کلونی مورچه بسیار کمتر PSO نشان داده شده است. (حدود 1/3  دقت PSO). با توجه به بررسی این نتایج و همچنین کمرنگ بودن تحقیقات با استفاده از الگوریتم PSO در این حوزه، در این پژوهش قصد داریم با استفاده از الگوریتم PSO به حل مسئله بپردازیم.

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

نمای منطقی[9] که به شرح الگوریتم و منطق اجرای قدم‌های مختلف فرآیند می‌پردازد و در آن مشخص می‌شود که ورودی‌های سیستم با چه روالی تبدیل به خروجی می‌شوند. در این نما به جزئیات اینکه داده‌ها از چه نوعی هستند و چگونه منتقل می‌شوند پرداخته نمی‌شود اما اینکه در هر مرحله از الگوریتم داده‌ها دارای چه ساختاری هستند و با چه روالی تحلیل می‌شوند بیان می‌شوند.

نمای داده[10] که در آن به معرفی مجموعه‌ی‌ داده‌های مورد استفاده، نحوه‌ی جمع‌آوری داده، روش قابل دسترس کردن[11] داده‌های برای الگوریتم، فهرست کردن داده‌های توصیف‌گر[12] پرداخته می‌شود. این نما برخلاف نمای منطقی به چگونگی انجام عملیات روی داده‌ها نمی‌پردازد و تنها به مدل کردن داده و جریان داده اکتفا می‌کند.

نمای سوم نمای مولفه‌ای[13] است که در آن مولفه‌های نرم افزاری و محل استقرار[14] آنها مشخص می‌شود. با توجه به اینکه مدل ارائه شده در این پژوهش روی سیستم‌های توزیع‌شده مستقر می‌شود، و اصولا این مدل تعیین گرایش در بلاگستان را با نگاه به سیستم‌های توزیع‌شده حل می‌کند، نگرانی‌هایی که پیرامون مقیاس‌پذیری در سیستم‌های توزیع‌شده وجود دارد با نمای مولفه‌ای واضح‌تر پاسخ داده می‌شود.

2.3       نمای منطقی

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

2.3.1       مسائل اساسی PSO

در فصل دوم با الگوریتم PSO و نحوه‌ی کارکرد آن آشنا شدید. در این الگوریتم برای آنکه ذرات[15] بتوانند همراه با Swarm به سمت نقطه‌ی بهینه حرکت کنند باید پیش از اجرای الگوریتم با یکدیگر از نظر مقدار داده‌ای هم‌تراز[16] شوند. این عمل در واقع در گام initialization  رخ می‌دهد.

قبل از این اشاره کردیم که اگرچه دقت الگوریتم PSO 3 برابر الگوریتم کلونی مورچه است اما کارایی آن کمتر است و یکی از مسائلی که باعث کاهش کارایی الگوریتم PSO می‌شود همین مسئله Initialization است [25].

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

شکل3‑1- محاسبه‌ی مقدار بهینه به طور مداوم

در چنین شرایطی (شکل 3-1) چون الگوریتم به تعداد بسیاز زیاد (و احتمالا برای حجم داده زیاد ) فراخوانی می‌شود، بسیار مهم است که گامهای الگوریتم چگونه طراحی شوند و در حد امکان کارهای تکراری حذف شده و گام‌های پیچیده‌ی الگوریتم که توان محاسباتی زیادی نیاز دارند حتی‌الامکان ساده شوند. در الگوریتم PSO  گامی‌که مربوط بهinitialize  کردن ذرات است بدون توجه به باقی گامهای الگوریتم هر بار برای همه‌ی داده‌ها اجرا می‌شود.

از طرفی یکسان کردن ذرات در ابتدای الگوریتم، نیازی اساسی برای ایجاد شرایط قابل پیش‌بینی در فضای حالت مسئله است. اساسا در الگوریتم PSO پارامترهای ثابت r1 و r2 که به شکل تصادفی باید انتخاب شوند برای حالتی تولید شده‌اند که در آن ذرات در گام اول initialize شده‌اند و پیدا کردن مجدد این پارامترها، برای تولید حالت بهینه، به ازای مقادیر مختلف ذرات بسیار پرهزینه است. بنابراین در حالت سنتی الگوریتم PSO، نمی‌توان بدون پرداخت هزینه‌ی زمانی و پردازشی زیاد گام initialize را حذف کرد.

اما اگر با دقت به الگوریتم PSO نگاه کنیم واضح است که مهم‌ترین تاثیر گام initialize هنگامی‌که است که قرار است fitness value برای آن محاسبه شود. در این مرحله اگر مقدار r1 و r2 بر اساس مقدار اولیه‌ی ذره محاسبه نشده باشد، جواب بهینه حاصل نخواهد شد و اگر بر اساس مقدار اولیه‌ی ذره باشد باید قبلا آنرا initialize  کرده باشیم.

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

اما در محیط بلاگستان که روزانه بالغ بر چند ده میلیون پُست وبلاگ در آن منتشر می‌شود[26] و نیاز است که گرایش کاربران به صورت بلادرنگ[17] تولید شود نگه‌داری اطلاعات همه ذرات بسیار هزینه‌بر است. فرض کنید اگر اطلاعات هر پست وبلاگ 1MB باشد[27] ، به کامپیوتری با 10TB حافظه اصلی نیاز است – فقط برای نگه‌داری این داده‌ها برای یک روز- به این معنی که استخراج گرایش مبتنی بر روزهای پیشین نیز نخواهد بود که عملیاتی بسیار پر هزینه است.

چنین حجمی‌از حافظه اصلی تنها توسط اشکال مختلف سیستم‌های توزیع‌شده قابل دسترسی است و هیچ MainBoard وجود ندارد که بتوان در آن 10TB حافظه اصلی قرار داد  و حتی اگر کامپیوتری با این حجم از حافظه اصلی وجود داشته باشد گذرگاه[18] مناسبی برای عبور دادن این حجم از داده به صورت آنی وجود ندارد. در اینجا نیاز به اجرای الگوریتم روی کامپیوترهایی با تعداد بیشتر و یک بستر پردازشی توزیع شده بیشتر نمایان می‌شود. بنابراین به بیش از یک ایستگاه کاری[19] و یا سرور[20]  برای پردازش این حجم از داده نیازمندیم که در این به هرکدام یک نود پردازشی می‌گوییم.

2.3.2       اصلاح PSO بر اساس مسئله

بنابراین نیاز است که اولا اطلاعات ذراتی که initialize  شده‌اند در جایی نگه‌داری شود تا در تکرارهای[21] بعدی الگوریتم مجددا محاسبه نشوند، ثانیا این عمل باید توسط تعدادی کامپیوتر انجام شود تا محدودیت‌های فیزیکی که در حال حاضر با آنها مواجه هستیم برطرف گردد. به تعبیر دیگر الگوریتم‌ باید به صورت توزیع شده اجرا شود. به همین منظور الگوریتم  سنتی  PSO که در شبه کد (1) آورده شد به صورت زیر بازنویسی می‌شود:

If there is new element in CAQ

For each new element
initialize particle
END

 

DO

For new particle (new post)
Calculate fitness value
If the fitness value is better than the best fitness value (pBest) in history
set current value as the new pBest
End

Send the particle with best fitness value to Aggregator

Choose the particle with the best fitness value of all the particles as the gBest
For each particle
Calculate particle velocity according equation (a)
Update particle position according equation (b)
End

End

  • (1.) شبه کد

v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[])    (a)

present[] = persent[] + v[]      (b)

در این شـبـه کد دو مفهـوم جـدیـد برای پاسـخ دادن به نیازهای مطرح شده معرفی شده‌اند: 1) CAQ  2) Aggregator . CAQ که مخفف Change Aware Queue است یک ساختار داده جدید است که وظیفه دارد داده‌های جدید را از داده‌های تکراری تشخیص دهد و اصول درج[22] و حذف[23] از آن بر مبنای ساختار داده‌ی صف است. یک CAQ  در واقع صفی از داده است که قابلیت تشخیص داده‌های جدید را دارد و الگوریتم PSO در گام   initializeاز طریق این ساختار داده ذراتی که به تازگی به فهرست اضافه شده‌اند را دریافت کرده و تنها آنها را initialize می‌کند تا در تکرار‌‌های مکرر الگوریتم ‌همه‌ی داده‌ها چندین بار Initialize نشوند. در ادامه در همین بخش بیشتر به جزئیات CAQ خواهیم پرداخت.

مفهوم دیگر یعنی Aggregator نقش هماهنگ کردن نتایج تولید شده در الگوریتم را دارد. شبه کد فهرست شده در فهرست کد (2) به صورت مستقل در کامپیوتر‌های مختلف اجرا می‌شود و هر کدام نتایج را برای Aggregator ارسال می‌کنند. یعنی هرکدام گرایش تولید شده براساس‌ داده‌های خود را محاسبه کرده و برای Aggregator ارسال می‌کنند. Aggregator نیز همان الگوریتم را روی داده‌های ورودی اعمال می‌کند تا محبوب‌ترین گرایش‌ها مشخص شوند. (شکل 3-2)

[1] absorbing state

[2] Chi-squared test

[3] Precision

[4] Recall

[5] Information Retrieval

[6] Trending

[7] Ant colony

[8] View

[9] Logical

[10] Data Flow View

[11] Data Availability

[12] Meta Data View

[13] Component View

[14] Deploy

[15] s‍Particle

[16] align

[17] real-time

[18] Bus

[19] Work station

[20] Server

[21] Iteration

[22] insert

[23] remove