Persian Paper

‫بازيابي كارآ و موثر اطلعات وب از طريق دستاوردهاي‬ ‫يادگيري ماشين‪ :‬طراحي و تكامل روشهاي يادگيري تقويتي‬ ‫در كاوش متمركز‬ ‫حميدرضا مطهري نژاد‬ ‫احمد عبداله زاده بارفروش‬ ‫‪[email protected]‬‬ ‫‪[email protected]‬‬

‫دانشكده مهندسي كامپيوتر و فناوري اطلعات‬ ‫دانشگاه صنعتي اميركبير (پلي تكنيك تهران)‬ ‫چكيده‬ ‫در اين مقاله‪ ،‬دستاوردهاي موتور جستجوي ‪ Cora‬بعنوان كاوشگر متمركزي كه از يادگيري تقويتي براي‬ ‫كاوش كارآي وب استفاده مي كند‪ ،‬توسعه داده شده است‪ .‬مهمترين دستاورد اين پروژه‪ ،‬بهبود روش هاي كاوش‬ ‫‪ Cora‬با توسعه و ارائه روشهاي جديد براي محاسبه مقدار ‪ Q‬در كاوشگر بر پايه يادگيري تقويتي است‪ .‬كاوشگرهاي‬ ‫پيشنهاد شده در اين پروژه صفحات هدف را سريعتر مييابند و نسبت به كاوشگرهاي موجود (‪ ،‍Cora‬كاوشگر‬ ‫متمركزي كه پاداشهاي آينده را مدل نميكند و نيز كاوشگر اول‪-‬سطح) به پاداشهاي بيشتري در طي كاوش دست‬ ‫مييابند‪ .‬در اين پروژه براي يادگيري متن در خلل كاوش متمركز وب براي اولين بار از دستهبندي كننده ماشينهاي‬ ‫بردار پشتيبان (‪ )SVMs‬استفاده شده است‪ .‬در نيمه اول كاوش‪ ،‬كاوشگرهاي يادگيري تقويتي بر پايه ‪SVMs‬‬ ‫نسبت به كاوشگرهاي يادگيري تقويتي بر پايه ‪ NB‬بسيار بهتر عمل مي كنند و صفحات هدف را سريع تر مي يابند‪.‬‬ ‫بستر آزمايش استفاده شده براي ارزيابي كاوشگرهاي پيشنهادي و روش هاي موجود‪ ،‬چهار پايگاه وب بخش هاي‬ ‫علوم كامپيوتر چهار دانشگاه بوده كه از وب كپي و بصورت خارج از خط در دسترس قرار گرفتهاند‪.‬‬

‫‪ 1‬مقدمه‬ ‫تعداد صفحات‪ ،‬سرويس دهندهها و حوزه های وب (مثلً ‪ )www.cisco.com‬با سرعت بسيار زيادی در حال‬ ‫افزايش است‪ .‬بزرگترين موتورهاي جستجو‪ ،‬كارهاي وسيعي براي توسعه دستاوردهايشان انجام داده‌اند؛ اما رشد وب‬ ‫فراتر از افزايش قدرت موتورهاي جستجو بوده است ]‪.[1‬تعداد پرس‌وجوهايي كه موتورهاي جستجو بايد پاسخ دهند‬ ‫نيز به صورت تصاعدي افزايش يافته است]‪ .[2‬كاوشگرهاي وب كه ‪ Robot، Spider‬و ‪ Worm‬هم ناميده‬ ‫مي‌شوند‪ ،‬داراي قدمتي به اندازه خود وب هستند ]‪.[3‬كلمه "كاوشگر" از آنجايي به اين برنامه اطلق ميشود كه‬ ‫تمامي پيوندهاي درون يك صفحه را براي ارجاعات بعدي استخراج مي‌كند‪ .‬كاوشگر وب همه منظوره تلش مي كند‬ ‫تا هر چقدر مي‌تواند صفحات بيشتري را از مجموعه‌اي از پايگاه هاي وب جمع‌آوري كند‪ .‬يك كاوشگر متمركز به‬ ‫جاي جمع آوري و شاخص بندي تمام اسناد وب‪ ،‬براي پاسخگويي به تمامي پرس و جوهاي آينده‪ ،‬موضوع محدوده‬ ‫كاوش خود را تحليل مي كند تا پيوندهايي را بيابد كه بيشترين ربط را به موضوع كاوش داشته باشند و از نواحي‬ ‫نامربوط وب احتراز كند‪ .‬استفاده از اين روش منجر به صرفه جويي قابل توجه در سخت افزار‪ ،‬نرمافزار و منابع شبكه‬ ‫ميشود و به ميزان پوشش باليي بر روي اسناد مرتبط موجود در وب دست مييابد‪ .‬يادگيري تقويتي ]‪4‬و ‪ [5‬يكي از‬ ‫شاخه‌هاي يادگيري نيمه‪-‬نظارتي است و هدف آن يادگيري از طريق محاوره مستقيم با يك محيط پويا و استفاده از‬ ‫چهارچوب تنبيه و تشويق براي يادگيري است‪ .‬استفاده از يادگيري تقويتي بهبود مناسبي را در كارآيي كاوشگر‬ ‫نسبت به كاوشگر اول‪-‬سطح و كاوشگر متمركز موجود از خود نشان داده است ]‪6‬و ‪ .[7‬در اين مقاله روشهاي موجود‬ ‫كاوش وب با استفاده از يادگيري تقويتي توسعه هاي داده شده است‪ .‬توسعه هاي اعمال شده در اين كاوشگرها‬ ‫بهبود عملكرد اين كاوشگرها نسبت به كاوشگرهاي قبلي را نشان مي دهد‪.‬‬ ‫‪1‬‬

‫در بخش ‪ 2‬اين مقاله يادگيري تقويتي معرفي شده و چگونگي نگاشت كاوش وب به اين يادگيري تشريح شده‬ ‫است‪ .‬بخش ‪ 3‬طراحي و پياده سازي كاوشگر يادگيري تقويتي را ارائه مي دهد‪ .‬بخش ‪ 4‬نتيجه آزمايشات انجام شده‬ ‫را بيان كرده و بخش ‪ 5‬نتيجه گيري كلي و پيشنهادات آينده را ارائه مي دهد‪.‬‬

‫‪ 2‬كاوش وب به عنوان يك مساله يادگيري تقويتي‬ ‫يادگيري تقويتي ]‪ [4‬روشي براي حل مسائل با استفاده از يادگيري از سعي و خطا در يك محيط پويا است‪.‬‬ ‫عامل يادگيري تقويتي‪ ،‬ياد ميگيرد كه در هر موقعيت چه كاري انجام دهد يعني يك نگاشت از موقعيتها به اعمال‬ ‫بدست آورد‪ .‬در يادگيري تقويتي‪ ،‬به عامل يادگير گفته نمي‌شود كه عمل درست در هر موقعيت كدام است‬ ‫(يادگيري از نوع با نظارت نيست)؛ بلكه بعد از انجام يك عمل در يك موقعيت‪ ،‬عمل انجام شده ارزيابي شده و به عامل‬ ‫گفته مي‌شود عمل انجام شده چقدر خوب و يا بد بوده است (پاداش و يا جزا داده ميشود) و عامل ياد ميگيرد كه در‬ ‫موقعيتهاي مشابه اين كار را انجام دهد و يا از آن احتراز كند‪ .‬در بسياري از كاربردهاي واقعي‪ ،‬ممكن است عمل‬ ‫انتخاب شده نه تنها بر پاداش دريافت شده آني بلكه بر پاداشهاي آينده نيز تاثير بگذارد‪ .‬از طرف ديگر‪ ،‬ممكن است‬ ‫عملي داراي سود آني نباشد و در قدمهاي زماني بعدي به پاداشهاي قابل توجهي منجر شود‪ .‬يكي از نقاط قوت‬ ‫يادگيري تقويتي اين است كه راه حلي براي اندازه‌گيري كارآيي اعمالي ارائه مي‌دهد كه داراي سود آني نيستند؛ اما‬ ‫در آينده منجر به سود و منفعت مي‌شوند‪ .‬عامل يادگيري تقويتي اين پاداش با تاخير را با يادگيري يك نگاشت از هر‬ ‫عمل ممكن به يك مقدار اسكالر انجام مي‌دهد‪ .‬اين مقدار اسكالر‪ ،‬مجموع پاداشهاي آينده هر عمل با يك "ضريب‬ ‫فراموشي" براي هر پاداش در طول زمان است‪ .‬ضريب فراموشي باعث مي‌شود تا پاداشهاي دريافت شده بعدي (در‬ ‫آينده دورتر) نسبت به پاداشهاي فعلي داراي ارزش كمتري باشند‪ .‬عامل يادگيري تقويتي سعي ميكند‪ ،‬بهينه عمل‬ ‫كند؛ يعني طوري عمل كند كه در طول زمان بيشترين مقدار پاداش را دريافت كند‪ .‬دو خصوصيت مهم يادگيري‬ ‫تقويتي كه آن را براي كار كاوش وب به عنوان يك راه حل مناسب مطرح مي سازد‪ ،‬يادگيري از محيط به روش سعي‬ ‫و خطا و توانايي در نظر گرفتن پاداشهاي تاخيري ميباشند‪.‬‬ ‫در اين بخش‪ ،‬يك نگاشت از مفاهيم موجود در كاوش وب به چارچوب يادگيري تقويتي انجام ميدهيم تا بتوان‬ ‫اين يادگيري را به مساله اعمال كرد‪ .‬در كار كاوش وب‪ ،‬اسناد هدف كه از كاوش يك ابرپيوند حاصل ميشوند‪،‬‬ ‫"پاداشهاي آني" بوده و اسناد هدفي كه ميتوان با پيمايش يك ابرپيوند در سطوح پايين‌تر يافت‪" ،‬پاداشهاي آينده"‬ ‫آن ابرپيوند هستند‪" .‬عمل"‪ ،‬تعقيب (پيمايش) يك ابرپيوند خاص است‪ .‬تعداد اعمال در اختيار‪ ،‬پويا و بزرگ است و‬ ‫بستگي به اين دارد كه تاكنون چه اسنادي كاوش شده است‪" .‬حالت" شامل‬ ‫‪ -1‬مجموعه اسناد هدفي است كه بايد كاوش شوند‪.‬‬ ‫‪ -2‬مجموعه‌ پيوندهايي كه يافته شده‌اند‪ .‬حالت فقط شامل موقعيت جاري كاوشگر (آخرين صفحه ملقات شده)‬ ‫نيست؛ زيرا كاوشگر مي‌تواند هر ابرپيوند يافته شده تاكنون را در قدم بعدي بپيمايد‪.‬‬ ‫خصوصيت كليدي كاوش متمركز كه يادگيري تقويتي را بعنوان يك چهارچوب مناسب براي آن مطرح مي‌سازد‪،‬‬ ‫اين است كه محيط‪ ،‬موقعيتهايي با پاداش مؤخر را ارائه مي‌دهد (صفحات غير مرتبط به موضوعي كه در چند قدم‬ ‫بعدي به تعداد زيادي صفحات مرتبط منجر مي شوند؛ مثل صفحه يك بخش علوم كامپيوتر كه در چند قدم بعد در‬ ‫صفحه شخصي كاربران تعدادي مقاله را ميتوان يافت)‪ .‬حال مي‌خواهيم بدانيم چگونه يادگيري تقويتي را به كاوش‬ ‫وب اعمال كنيم‪ .‬در اين حوزه‪ ،‬فضاي حالت بسيار بزرگ است و تعداد اعمال در اختيار هم بسيار زياد است (تعداد‬ ‫ابرپيوندهاي يافته شده تا كنون)‪ .‬در كاوشگر يادگيري تقويتي ‪ Cora‬چند فرض در نظر گرفته شده تا به سادگي و‬ ‫تعميم مساله كمك كند‪:‬‬ ‫‪ )1‬فرض ميشود "حالت" مستقل از اينست كه كدام اسناد هدف تابحال ديده ‌شده‌اند‪.‬‬

‫‪2‬‬

‫‪ )2‬فرض ميشود ميزان مربوط بودن اعمال (ابرپيوندها) به موضوع (هدف) مي‌تواند با كلمات "در همسايگي" ابرپيوند‬ ‫متناظر با هر عمل مشخص شود‪.‬‬ ‫با فرض اول‪ ،‬يك تعميم در فضاي حالت انجام مي‌گيرد و تمامي حالت به يک حالت تبديل مي شود‪ .‬با فرض‬ ‫دوم مي‌توان بين ابرپيوندها تعميم انجام داد و آنها را بوسيله متن اطرافشان با هم مقايسه كرد‪ .‬با اين فرض‌ها‪ ،‬براي‬ ‫يادگيري انجام يك كاوش مؤثر و كارآ دو زير مساله باقي مي‌ماند‪ )1( :‬بدست آوردن داده‌هاي آموزشي و زوجهاي‬ ‫"مجموعه‌ كلمات‪/‬مقدار ‪ Q‬متناظر" از داده هاي آموزشي (‪ )2‬يادگيري يك نگاشت با استفاده از داده‌هاي آموزشي‪.‬‬ ‫چندين راه براي جمعآوري دادههاي آموزشي وجود دارند‪.‬‬ ‫در كاوش وب‪ ،‬هدف‪ ،‬يادگيري ميزان پاداش مورد انتظار در آينده از تعقيب هر ابرپيوند است‪ .‬با استفاده از يادگيري‬ ‫تقويتي در سادهترين حالت‪ ،‬ميتوان يك نگاشت از متن در همسايگي يك ابرپيوند را به تعداد (با ضريب فراموشي)‬ ‫صفحات مرتبط مورد انتظار در آينده ياد گرفت‪ .‬صفحات مرتبط مورد انتظار‪ ،‬صفحاتي هستند كه از تعقيب همان‬ ‫ابرپيوند در مراحل بعدي حاصل مي‌شوند‪ .‬نگاشت از متن به يك مقدار اسكالر با تبديل اين مساله رگرسيون به يك‬ ‫مساله دسته‌بندي ]‪ [ 9‬انجام مي‌شود‪ .‬متن يك ابرپيوند و متن همسايه آن بوسيله يك دسته‌بندي كننده كه در فاز‬ ‫آموزش يادگرفته است‪ ،‬دسته‌بندي شده و احتمال مربوط بودن آن به هركدام از دسته‌هاي آموزشي بدست مي‌آيد‪.‬‬ ‫مقدار اسكالر نسبت داده شده به اين ابرپيوند‪ ،‬به مجموع وزني مقادير احتمال ربط ابرپيوند به اين دسته‌ها تعريف‬ ‫ميشود‪.‬‬

‫‪ 3‬طراحي و پياده سازي كاوشگر يادگيري تقويتي‬ ‫اگرچه عامل ميتواند از تجربيات بصورت برخط ياد بگيرد‪ ،‬در پيادهسازي اين سيستم‪ ،‬عامل يادگير بصورت‬ ‫خارج از خط با استفاده از يك مجموعه داده از قبل كاوش شده آموزش داده شده است‪ .‬براي اين دادههاي آموزشي‪،‬‬ ‫تابع انتقال حالت (‪ )T‬و تابع پاداش (‪ )R‬مشخص هستند‪ .‬با اين اطلعات ميتوان زوجهاي "مجموعه كلمات‪/‬مقدار ‪Q‬‬

‫متناظر" را بدست آورد و از آنها براي تخمين تابع‪ Q -‬بخش كاوش نشدهاي از وب استفاده كرد‪.‬‬ ‫همانطور كه اشاره شد‪ ،‬مقدار‪ Q-‬يك ابرپيوند با استفاده از برنامه سازي پويا برابر مجموع پاداشها با يك ضريب‬ ‫كاهنده (فراموشي) براي هر پاداش است كه عامل با تعقيب خط مشي بهينه پس از تعقيب ابرپيوند و در خلل‬ ‫پيمايش فضاي ابرپيوندها دريافت داشته است‪ .‬وقتي كه در تعقيب هر ابرپيوند‪ ،‬تعداد پاداشها زياد باشد‪ ،‬هدف‬ ‫محاسبه توالي بهينه بطور مستقيم است و مقدار‪ Q-‬به مجموع پاداشها در خلل توالي با يك ضريب كاهنده در هر‬ ‫قدم تعريف ميشود‪ .‬براي محاسبه مستقيم توالي بهينه‪ ،‬انباره ابرپيوندهاي حاصل از كاوش تمام صفحات ملقات شده‬ ‫توالي‪ ،‬نگهداري شده و پيمايش به صورت آزمند‪ ،‬به سمت ابرپيوند با بيشترين پاداش تخميني (و يا نزديكترين‬ ‫پاداش به انباره) انجام ميگيرد‪ .‬در ابتدا‪ ،‬انباره حاوي ابرپيوندهايي است كه مقدار‪ Q-‬آنها تاكنون محاسبه گرديده‬ ‫است‪ .‬انتخاب از ميان ابرپيوندهاي انباره اين حقيقت را روشن ميسازد كه كاوشگر مجبور نيست ابرپيوند بعدي‬ ‫ملقات شونده را از ميان ابرپيوندهاي صفحه جاري انتخاب كند؛ بلكه ميتواند هر ابرپيوند تاكنون شناخته شدهاي را‬ ‫انتخاب كند‪ .‬ابرپيوندهاي درون انباره فقط ابرپيوندهايي هستندكه از طريق ابرپيوند آغازي قابل دستيابي باشند‪.‬‬ ‫در ادامه‪ ،‬جريان كار كاوشگر يادگيري تقويتي‪ ،‬در دو فاز يادگيري و آزمايش بررسي شده است‪ .‬فاز يادگيري‪،‬‬ ‫به صورت "خارج از خط" انجام مي‌گيرد‪ .‬يعني سيستم از يك مجموعه اسناد وب كه قبلً از آن كپي شده‌اند‪ ،‬آموزش‬ ‫داده شده است‪ .‬در فاز آزمايش‪ ،‬اسناد از وب كپي شده و يك مقدار ‪ Q‬براي هر ابرپيوند جديد بر اساس ميزان پاداش‬ ‫آينده تخمين زده ميشود‪ ،‬پيوندها بر اساس تخمين مقدار پاداششان كاوش مي‌شوند‪ .‬كاوشگر سعي مي‌كند اسناد‬ ‫هدف را با كاوش كمترين تعداد ابرپيوند بيابد و از كاوش نواحي غير مرتبط وب احتراز كند‪ .‬در دو زيربخش زير‬ ‫فازهاي يادگيري و آزمايش به طور مشروح بيان شده‌اند‪.‬‬

‫‪ 3-1‬فاز يادگيري‬ ‫‪3‬‬

‫در فاز يادگيري‪ ،‬مجموعه داده‌هاي آموزش به سيستم ارائه مي‌شود‪ .‬سيستم‪ ،‬متن در همسايگي ابرپيوندها و‬ ‫متن خود ابرمتن را بكار گرفته و يك نگاشت از اين مجموعه كلمات به مقادير‪ Q-‬بدست مي‌آورد‪ .‬سپس اين مجموعه‬ ‫را به عنوان داده‌هاي آموزشي يك دسته‌بندي كننده بيز ساده بكار مي‌برد‪.‬‬ ‫بستر آزمايش اين سيستم‪ ،‬پايگاههاي وب بخشهاي علوم كامپيوتر چهار دانشگاه آمريكا و موضوع مورد تمركز‬ ‫فايلهاي مقالت تحقيقي علوم كامپيوتر با پسوندهاي ‪ PS, .PS.GZ, .PS.Z.‬بوده است‪ .‬در سيستم پياده سازي شده‪،‬‬ ‫يك الگوريتم براي شناسايي مقالت توسعه داده شده است كه با دقت بيش از ‪ %95‬صفحات هدف (مقالت) را از‬ ‫غيرهدف تمايز مي‌دهد‪ .‬اين الگوريتم‪ ،‬در هر فايل به دنبال بخشهاي چكيده و مراجع جستجو مي‌كند‪.‬‬ ‫فاز يادگيري شامل دو مرحله زير است‪ )1( :‬پردازش داده‌هاي آموزشي و بدست آوردن مقادير ‪ Q‬هر ابر پيوند (‬ ‫‪ )2‬استفاده از مقادير ‪ Q‬هر پيوند و متن همسايگي آن براي يادگيري يك تعميم از اين مساله رگرسيون‪.‬‬ ‫‪ 3-1-1‬پردازش داده‌هاي آموزشي و بدست آوردن مقادير ‪ Q‬هر ابرپيوند‬ ‫در هركدام از بسترهاي آزمايش مجموعه‌اي از داده‌هاي آموزشي وجود دارد و عامل به صورت "خارج از خط"‬ ‫آموزش ميبيند‪ .‬از ديدگاه يادگيري تقويتي‪ ،‬براي اين مجموعه آموزشي‪ ،‬تابع انتقال حالت ‪( T‬از هر صفحه با انتخاب‬ ‫يک عمل خاص به چه صفحه ديگري خواهيم رفت) و تابع پاداش ‪( R‬تعداد پاداشهاي قابل دستيابي از هر ابرپيوند)‬ ‫را داريم و هدف يادگيري تابع ‪ Q‬با محاسبات خارج از خط است‪ .‬مقدار ‪ Q‬يك ابرپيوند به مجموعه كاهش يافته‬ ‫پاداشهاي دريافت شده با استفاده از خط مشي بهينه تعريف مي‌شود‪.‬‬ ‫‪ 3-1-2‬نگاشت متن به مقادير‪Q-‬‬

‫براي بدست آوردن مقادير اسكالر ‪ Q‬از روي متن در همسايگي پيوندها‪ ،‬اين مساله رگرسيون به يك مساله‬ ‫دسته‌بندي ]‪ [9‬تبديل مي‌شود‪ .‬براي اين منظور از دسته‌بندي كننده هاي بيزساده و ماشينهاي بردار پشتيبان‬ ‫استفاده مي‌شود‪ .‬در بخش بعد اين دو دسته بندي كننده معرفي شده اند‪.‬‬ ‫ابتدا در مجموعه داده‌هاي آموزشي مقادير ‪ Q‬بدست آمده براي پيوندها (مجموع كاهشي پاداشهاي آينده) به‬ ‫چندين دسته گسسته مي‌شود‪ .‬سپس‪ ،‬متن در همسايگي هر ابرپيوند در دسته متناظر با مقدار ‪ Q‬آن ابرپيوند قرار‬ ‫مي‌گيرد و در نهايت اين دسته‌ها به عنوان داده‌هاي آموزشي دسته‌بندي كننده ها بكار مي‌روند‪ .‬متن همسايگي ‌‬ ‫مي‌تواند به صورتهاي مختلف انتخاب شود‪ .‬سه فرم متفاوتي كه در اين سيستم مورد استفاده قرار گرفته‌اند‪ ،‬عبارتند‬ ‫از‪ )1( :‬تمام متن صفحه‌اي كه ابرپيوند در آن قرار دارد‪ )2( .‬متن اطراف پيوند (جلو و بعد از آن) و متن خود ابر‬ ‫پيوند‪ )3( .‬متن ابرپيوند‪ ،‬عنوان صفحه و عناوين ديگر داخل صفحه‪ ،‬سرآيند صفحه‪ .‬شكل ‪ 1‬كد مجازي نگاشت متن‬ ‫به مقادير ‪ Q‬را در فاز يادگيري نشان مي‌دهد‪.‬‬ ‫‪ 3-1-3‬دسته بندي كننده هاي متن‬ ‫در يادگيري نظارتي ]‪ [10‬كه "دستهبندي" و يادگيري با معلم هم گفته ميشود‪ ،‬عامل يادگير با استفاده از يك‬ ‫سري از دادههاي آموزشي ياد ميگيرد‪ .‬در واقع‪ ،‬اجزاي يك سيستم يادگيري نظارتي شامل عامل يادگير‪ ،‬مجموعه‬ ‫دادههاي آموزشي و دادههاي آزمايشي (دادههاي برچسبدار و غير برچسبدار) و تعداد مشخصي دسته ميباشد‪ .‬در‬ ‫كاربرد دستهبندي متن‪ ،‬هر سند به عنوان يك داده آموزشي در نظر گرفته ميشود‪ .‬هر دسته در اين كاربرد‪ ،‬حاوي‬ ‫اسناد مربوط به يك موضوع خاص است‪ .‬تعداد دستههاي آموزشي بر اساس تنوع موضوعي تعيين ميگردد‪ .‬اين تعداد‬ ‫توسط كاربري كه دادههاي آموزشي را فراهم ميكند‪ ،‬مشخص ميشود‪ .‬برچسب دادههاي آموزشي‪ ،‬شماره و يا نام‬ ‫دسته و يا دستههايي ميباشد كه هر داده آموزشي به آن دسته و يا دستهها تعلق دارد‪ .‬عامل يادگير در فاز آموزشي‬ ‫با استفاده از دادههاي آموزشي (دادههاي برچسبدار)‪ ،‬آموزش داده شده و يك تعميم از هر دسته ياد ميگيرد كه عامل‬ ‫را قادر به شناسايي اسناد مربوط به هر دسته ميكند‪ .‬در فاز آزمايش‪ ،‬عامل يادگير ‪-‬كه دستهبندي كننده هم ناميده‬ ‫‪4‬‬

‫ميشود‪ -‬اسناد متني را كه در فاز آموزشي نديده است و متعلق به يكي از دستههاي آموزشي ميباشند‪ ،‬دريافت كرده‬ ‫و احتمال تعلق اين سند را به هر كدام از دستههاي آموزشي بدست ميآورد‪ .‬دستهبندي براي هر سند‪ ،‬به معني‬ ‫انتخاب دسته با بالترين احتمال تعلق سند به آن دسته ميباشد‪.‬‬ ‫‪Distance:‬‬ ‫)‪Calculates Q values as gamma ^ (distance to the nearest reward‬‬ ‫‪Three:‬‬ ‫‪Calculate Q values for three classes - immediate, future, none.‬‬ ‫‪Score = 1 for immediate, gamma for future, zero for none.‬‬ ‫‪Four:‬‬ ‫‪Calculates Q values for four classes - immediate, one-step, two-step, none.‬‬ ‫‪Score = 1 for immediate, gamma for one-step, gamma^2 for two-steps, zero for none‬‬ ‫‪Five:‬‬ ‫‪Calculates Q values for four classes - immediate, one-step, two-step, three-step, none.‬‬ ‫‪Score = 1 for immediate, gamma for one-step, gamma^2 for two-steps, gamma^3 for‬‬ ‫‪three-steps, zero for none.‬‬ ‫‪Papers:‬‬ ‫‪Calculates Q values as number of papers available from link.‬‬ ‫‪Future:‬‬ ‫)‪Calculates Q values as future reward, Num(reward) * (gamma ^ distance‬‬ ‫‪Immediate:‬‬ ‫‪If the link is a paper its Q value is 1 else 0.‬‬ ‫‪Cutoff:‬‬ ‫‪Calculates according to path, if value < $cutoff, gives value of 0.‬‬ ‫‪Number of traversed links‬‬ ‫فاز ‪leads‬‬ ‫در ‪to‬‬ ‫‪increase‬‬ ‫‪gamma‬‬ ‫يادگيري‬ ‫‪exponent‬به‪in‬مقادير ‪Q‬‬ ‫مجازي‪of‬نگاشت متن‬ ‫شكل ‪ -1‬كد‬

‫‪ 3-1-3-1‬دسته بندي كننده بيز ساده (‪)Naïve Bayes‬‬ ‫در اين مدل يادگيري فرض مي‌شود كه داده‌هاي متني از يك مدل پارامتري توليد مي‌شوند و از داده‌هاي‬ ‫آموزشي براي برآورد (تخمين) اين پارامترها استفاده مي‌شود ]‪8‬و ‪11‬و ‪ .[12‬در فاز آزمايش براي هر سند جديد با‬ ‫بكارگيري مقدار پارامترها ‪ -‬كه در فاز آموزش يادگرفته شده ‪ -‬و با استفاده از قانون بيز اين احتمال محاسبه ميشود‬ ‫كه اين سند بوسيله هر يك از دستههاي آموزشي توليد شده باشد (متعلق به آن دسته باشد)‪ .‬دسته‌بندي‪ ،‬انتخاب‬ ‫بالترين اين احتمالها براي كلمات اين سند است‪.‬‬ ‫‪ 3-1-3-1‬دسته بندي كننده ماشينهاي بردار پشتيبان‬ ‫ماشينهاي بردار پشتيبان بر پايه اصل حداقل سازي خطاي ساختاري از نظريههاي يادگيري آماري (محاسباتي)‬ ‫توسعه يافتهاند‪ .‬اين دسته بندي كننده از خود كارآيي بسيار بهتري را نسبت به روشهاي ديگر در دسته بندي متن‬ ‫از خود نشان داده است‪ .‬يكي از فاكتورهاي مهم در يادگيري متن اين است كه‪ ،‬يادگيرنده (دستهبنديكننده) قابليت‬ ‫تعميم مناسب با استفاده از تعداد معدودي داده آموزشي را داشته باشد‪ .‬در اغلب كاربردهاي واقعي و مخصوصاً در‬ ‫فضاي وب تعداد دادههاي آموزشي كافي و يا زيادي براي يادگيرنده وجود ندارند و يا فراهم نمودن آن زمانبر و‬ ‫مشكل است‪ .‬روش ماشينهاي بردار پشتيبان ‪Transductive (TSVMS) ]14‬و ‪15‬و ‪ [ 16‬يك نوع خاص از‬ ‫ماشينهاي بردار پشتيبان است كه هدفش يادگيري از تعداد معدودي داده آموزشي است و در فضاي دستهبندي‬ ‫متن نسبت به الگوريتم معمول ماشينهاي بردار پشتيبان به كارآيي بهتري دست يافته است ]‪ TSVMs .[14‬از‬ ‫دستاورد استنتاج ‪ Transductive‬به جاي استقراء (‪ )Induction‬استفاده ميكند‪ .‬در استقرا‪ ،‬يادگيرنده سعي ميكند‬ ‫تا به طريقه استقراء يك تابع تصميم را نتيجه بگيرد كه داراي نرخ خطاي پاييني در تمامي توزيعهاي مثالها (بعنوان‬ ‫داده آموزشي و آزمايشي) براي يك يادگيري خاص باشد‪ .‬اغلب‪ ،‬اين دستاورد به طور غير ضروري پيچيده است‪ .‬در‬

‫‪5‬‬

‫بسياري از موقعيتها ما به يك تابع تصميم خاص توجه نميكنيم اما ميخواهيم يك مجموعه از مثالها (مجموعه‬ ‫آموزشي) را با كمترين خطاي ممكن دستهبندي كنيم‪ .‬اين مساله‪ ،‬هدف استنتاج ‪ Transductive‬است‪ .‬مباحث‬ ‫تئوري و آزمايشات عملي ‪ [Joachims ]13‬نشان ميدهد كه ماشينهاي بردار پشتيبان براي دستهبندي متن بسيار‬ ‫مناسب هستند و كارآيي آنها از روشهاي متداول دسته‌بندي متن به طور چشمگيري بهتر است و همچنين داراي‬ ‫پايداري بيشتري است‪ .‬روش ‪ TSVMs‬اغلب خواص ماشينهاي بردار پشتيبان را به ارث مي‌برد‪ ،‬بنابراين همين‬ ‫شواهد به ‪ TSVMs‬هم اعمال ميشود‪.‬‬ ‫‪ TSVMs‬از چه نظر از ماشينهاي بردار پشتيبان بهتر است؟ در تحقيقات در بازيابي اطلعات داريم كه كلمات‬ ‫زبان طبيعي به ميزان بسيار زيادي در يك زمينه بطور همزمان با هم در يك سند رخ ميدهند ]‪ .[14‬به نظر مي‌رسد‬ ‫بعضي از كلمات با هم‪ ،‬در اسناد از يك نوع رخ مي‌دهند‪ .‬يك مطالعه تجربي در ]‪ [15‬نيز اين مشاهده را نشان مي‌دهد‪.‬‬ ‫بسياري از دستاوردهاي بازيابي اطلعات سعي مي‌كنند تا اين ساختارهاي متن را استخراج كنند ]‪ .[14‬روش‬ ‫‪ TSVMs‬اطلعات مربوط به رخداد همزمان كلمات را به عنوان دانش اوليه در مورد مساله مورد يادگيري‪ ،‬استخراج‬ ‫مي‌كند‪.‬‬

‫‪ 3-2‬فاز آزمايش‬ ‫در فاز آزمايش‪ ،‬عامل يادگيري تقويتي‪ ،‬پيوندهاي ملقات نشده مجموعه آزمايش را بر اساس مقدار تخمين‬ ‫تابع‪ Q-‬در يك صف اولويت قرار مي‌دهد‪ .‬اين تابع‪ Q-‬براي هر ابرپيوند‪ ،‬متن اطراف پيوند را به يك مقدار اسكالر از‬ ‫پاداشهاي مؤخر آينده تخمين مي‌زند‪ .‬پاداشهاي آينده آنهايي هستند كه از تعقيب آن ابرپيوند در قدم‌هاي بعدي‬ ‫بدست مي‌آيند‪.‬‬ ‫هنگامي كه يك سند از وب كپي شود‪ ،‬بررسي مي‌شود كه آيا اين سند مرتبط به موضوع و يا از نوع خواسته‬ ‫شده است و يا خير(سند هدف)‪ .‬در صورتي كه يك سند هدف باشد‪ ،‬در انباره اسناد ذخيره مي‌شود تا بعداً بر روي آن‬ ‫پردازش و سپس شاخص‌بندي شود‪ .‬اگر سند‪ ،‬صفحه هدف نبوده و يك صفحه ‪ HTML‬باشد‪ ،‬پيوندهاي آن استخراج‬ ‫شده و هر كدام از ابرپيوندها‪ ،‬بر اساس مقدار ‪ Q‬متناظر رتبه‌بندي شده و در صف اولويت كاوش قرار مي‌گيرد‪.‬‬ ‫استراتژيهاي متفاوتي براي كاوش بكار مي‌روند كه بر اساس هركدام مقدار ‪ Q‬متفاوتي به يك پيوند نسبت داده‬ ‫مي‌شود‪.‬‬ ‫در هر يك از بسترهاي آزمايش‪ ،‬بخشي از داده‌ها بعنوان مجموعه‌هاي آموزشي و بخشي ديگر به عنوان داده‌هاي‬ ‫آزمايش بكار گرفته شده‌اند‪ .‬در بستر آزمايش بخشهاي علوم كامپيوتر دانشگاهها و موضوع مورد تمركز مقالت‬ ‫تحقيقي علوم كامپيوتر از بين ‪ 4‬دانشگاه‪ ،‬هر دفعه سه بخش علوم كامپيوتر به عنوان مجموعه آموزشي و ديگري به‬ ‫عنوان پايگاه داده مورد آزمايش بكار گرفته شده‌اند‪.‬‬

‫‪ 4‬آزمايشات انجام شده‬ ‫در اين بخش‪ ،‬نتايج پياده سازي و ارزيابي كاوشگرهاي يادگيري تقويتي ارائه شده است‪ .‬كاوشگرهاي يادگيري‬ ‫تقويتي پيادهسازي شده در مقابل همديگر و روشهاي كاوش "اول سطح" وب و كاوشگرهاي متمركز قبلي ارزيابي‬ ‫شدهاند‪.‬‬ ‫نتايج پياده سازي نشان داده است كه استفاده از دسته بندي كننده ماشينهاي بردار پشتيبان در مقايسبه باد‬ ‫دسته بندي كننده بيز ساده (‪ )NB‬كه ‪ Cora‬از آن استفاده كرده است‪ ،‬منجر به بهبود كارآيي كاوشگرها در مراحل‬ ‫اوليه كاوش از نظر سرعت يافتن صفحات هدف و تعداد آنها دارد (شكل ‪.)2‬‬

‫‪6‬‬

‫شكل ‪ -2‬استفاده از دسته بندي كننده ‪ SVMs‬در مقايسه با ‪ NB‬كه ‪ Cora‬از آن استفاده كرده است منجر به بهبود‬ ‫مي شود‪.‬‬ ‫همچنين مقايسه ميزان پاداش كسب شده توسط كاوشگرهاي يادگيري تقويتي در خلل كاوش نشان مي دهد‬ ‫كه در نيمه اول كاوش روشهايي كه از دسته بندي كننده ‪ SVMs‬استفاده مي كنند به كارآيي بهتري دست مي يابند‬ ‫ولي در طول كل كاوش روشهاي با دسته بندي كننده ‪ NB‬عملكرد بهتري دارند (جدول ‪.)1‬‬ ‫جدول ‪ -1‬ده روش برتر كاوش در نيمه كاوش و در طي تمام كاوش‬ ‫‪Method 50%‬‬ ‫‪svm_n_4_cut_g0.3 88.481055‬‬ ‫‪nb_n_4_cut_g0.3‬‬ ‫‪88.36996‬‬ ‫‪svm_n_5_cut_g0.5 87.5699675‬‬ ‫‪svm_r_5_cut_g0.5 87.3709975‬‬ ‫‪svm_r_5_five0.5‬‬ ‫‪87.259045‬‬ ‫‪svm_r_3_parl0.3‬‬ ‫‪87.02282‬‬ ‫‪nb_n_3_cut_g0.5‬‬ ‫‪86.977685‬‬ ‫‪nb_r_4_four0.5‬‬ ‫‪86.6833625‬‬ ‫‪svm_r_4_cut_g0.5 86.627875‬‬ ‫‪nb_r_4_dist0.5‬‬ ‫‪86.6086575‬‬

‫‪Method 100%‬‬ ‫‪nb_n_4_cut_g0.3 81.8159675‬‬ ‫‪nb_r_3_cut_g0.5 78.3353625‬‬ ‫‪nb_r_3_parl0.1‬‬ ‫‪78.04647‬‬ ‫‪nb_r_4_dist0.5‬‬ ‫‪77.9688725‬‬ ‫‪nb_r_3_parl0.3‬‬ ‫‪77.94723‬‬ ‫‪nb_r_4_dist0.3‬‬ ‫‪77.87946‬‬ ‫‪nb_n_3_cut_g0.5 77.3640475‬‬ ‫‪nb_r_3_dist0.3‬‬ ‫‪77.3528025‬‬ ‫‪nb_r_3_cut_g0.3 77.25757‬‬ ‫‪nb_r_3_cut_g0.1 77.2251675‬‬

‫‪ 5‬نتيجه گيري و تحقيقات آينده‬ ‫به طور كلي‪ ،‬با توجه به نمودارها و جداول حاصل از نتايج پيادهسازي‪ ،‬نتايج زير قابل استخراج هستند‪:‬‬ ‫•كاوشگرهاي متمركز يادگيري تقويتي داراي كارآيي بهتري نسبت به كاوشگرهاي متمركزي‬ ‫كه پاداشهاي آينده را مدل نميكنند و نيز كاوشگر "اول‪-‬سطح" ‪ -‬روش معمول مورد‬ ‫استفاده در موتورهاي جستجوي همه منظوره‪ -‬هستند‪ .‬مخصوصاً اين كاوشگرها مسير خود‬ ‫را به سمت صفحات هدف بسيار سريع مييابند و در نزديكي آن باقي مي مانند‪ .‬بسياري از‬ ‫كاوشگرهاي يادگيري تقويتي ‪-‬بويژه آنهايي كه از دستهبندي كننده ماشينهاي بردار‬ ‫پشتيبان استفاده ميكنند‪ -‬نشان دادند كه اولين صفحه هدف را در سومين و يا چهارمين‬ ‫ابرپيوند تعقيب شده از پايگاه وب مييابند؛ در حاليكه روش كاوش اول سطح در سيصدمين‬ ‫ابرپيوند به آن رسيده و اين عدد براي كاوشگر متمركزي كه پاداشهاي آينده را مدل نمي‪-‬‬ ‫كند‪ ،‬بين ‪ 30‬تا ‪ 50‬تغيير ميكند‪.‬‬

‫‪7‬‬

‫•ميانگينگيري بر روي نتايج حاصل از كاوشگرهاي يادگيري تقويتي كه از دستهبندي كننده‬ ‫ماشينهاي بردار پشتيبان استفاده ميكنند‪ ،‬نشان ميدهد كه اين كاوشگرها نسبت به‬ ‫كاوشگرهاي يادگيري تقويتي كه از دستهبندي كننده بيز ساده استفاده ميكنند‪ ،‬در نيمه‬ ‫اول كاوش (‪ 50‬درصد اول) كارآيي بسيار بهتري دارند‪ .‬اگرچه‪ ،‬بعضي از روشهايي كه دسته‪-‬‬ ‫بندي كننده ماشينهاي بردار پشتيبان استفاده ميكنند‪ ،‬در تمام طول كاوش (‪ 100‬درصد‬ ‫كاوش) از خود كارآيي بهتري نشان دادهاند‪.‬‬ ‫•ميانگينگيري بر روي روشهاي كاوش متفاوت يادگيري تقويتي نشان داد كه پارامترهاي‬ ‫مختلف با مقادير زير در اين كاوشگرها به كارآيي بهتري دست مييابند (نتايج براي تمام‬ ‫طول كاوش ‪ 100-‬درصد آن‪ -‬ارائه شدهاند)‪:‬‬ ‫‪‬مقدار گاما‪:‬‬

‫‪1/0‬‬

‫‪‬تعداد دستهها‪:‬‬

‫‪ 3‬دسته‬

‫‪‬متن درهمسايگي‪:‬‬

‫•كاوشگرهاي‬

‫دستهبندي‬

‫با‬

‫كننده‬

‫‪ :SVMs‬متن مرتبط‬ ‫•كاوشگرهاي با دستهبندي كننده ‪:NB‬‬ ‫متن نزديك‬ ‫‪‬بهترين روش كاوش‪( nb_n_4_cut_g0.3 :‬كاوشگري كه از‬ ‫دستهبندي كننده بيز ساده‪ ،‬متن نزديك‪ ،‬تعداد دستهها ‪،4‬‬ ‫روش پايه كاوش برش مقدار و مقدار گاماي ‪ 3/0‬استفاده مي‪-‬‬ ‫كند)‬ ‫•استفاده از روش مكاشفهاي در كاوش (تحليل آماري ابرمتنهايي كه به صفحات هدف منجر‬ ‫ميشوند و استفاده از كلمات با احتمال رخداد بال در طي كاوش) منجر به بهبود كارآيي‬ ‫كاوش و مخصوصاً منجر به يافتن سريعتر صفحات هدف در اوايل كاوش ميباشد‪.‬‬ ‫آزمايشات انجام شده نشان دادكه استفاده از روش تغيير خط مشي (قسمتي از كاوش با يك روش و قسمت ديگر با‬ ‫روش ديگر) منجر به بهبود كارآيي كاوشگرهاي ميشود‪ .‬اين تغيير خط مشي چنان صورت ميگيرد كه هر روش‬ ‫كاوش در قسمتي بكار گرفته شود كه از خود كارآيي بهتري نشان ميدهد‪.‬‬ ‫از آنجاييكه در بستر آزمايش دانشگاهها‪ ،‬تعداد صفحات هدف زياد بوده و اين صفحات هدف داراي توزيع‬ ‫مشخصي بر روي پايگاه وب نميباشند‪ .‬در بستر آزمايش شركتها (مجموعه اي از پايگاه هاي وب چند شركت)‪ ،‬فقط‬ ‫يك صفحه هدف تعريف شده (صفحه مديران شركت) و اين بستر قادر به نشان دادن بهتر رفتار هوشمند كاوشگر‬ ‫يادگيري تقويتي ميباشد‪ .‬اين امر به اين دليل است كه كاوشگر يادگيري تقويتي در اين بستر بايد مسير خود به‬ ‫سمت هدف را يافته و به صورت بهينهاي آن را بپيمايد‪ .‬طبق پيشبينيهاي انجام شده‪ ،‬اين آزمايشات قادر به نشان‬ ‫دادن كارآيي بهتر كاوشگرهاي يادگيري تقويتي كه از دستهبندي كننده ‪ SVMs‬استفاده ميكنند‪ ،‬در حوزههايي‬ ‫است كه رفتار هوشمندانه كاوشگر بيشتر مد نظر است‪ .‬مطالعه رفتار كاوشگر در اين بستر آزمايش بعنوان يكي از‬ ‫زمينههاي تحقيقاتي آينده معرفي ميشود‪.‬‬

‫‪ 6‬مراجع‬ ‫‪[1] Lawrence S. and Giles C.L., Accessiblity of Information on the Web, Nature 400:107-109, July 8, 1999.‬‬ ‫‪[2] Page L. and Brin S., The anatomy of a large-scale hypertext web search engine, In the proceeding of the‬‬ ‫‪seventh International World Wide Web Conference, 1998.‬‬ ‫‪[3] The Web Robots Pages.‬‬

‫‪8‬‬

http://info.webcrawler.com/mak/projects/robots/robots.html. [4] Kaelbling L. P., Littman M. L., and Moore A. W., Reinforcement learning: A survey, Journal of Artificial Inteligence Research, pp. 237-285, May 1996. [5] Sutton R. S., Barto A. G., Reinformcement Learning: An Introduction, MIT Press, Cambridge, MA, 1998. [6] McCallum A. K., Nigam K., Rennie J. and Seymore K., Automating the construction of internet portals with machine learning, In Information Retrieval, 1999. [7] Rennie J. and McCallum A., Using reinforcement learning to spider the web efficiently, In Proceedings International Conference on Machine Learning (ICML), 1999. [8] McCallum A. and Nigam K., Rennie J. and Seymore K., Building domain-specific search engines with machine learninig techniques, In AAAI-99 Spring Symposium on Intelligent Agents in Cyberspace, 1999. [9] Torgo L. and Gama J., Regression using classification algorithms, Intelligent Data Analysis, 1(4), 1997. [10] Chakrabarti S., Data mining for hypertext: A tutorial survey, SIGKDD Explorations: Newsletter of the Special Interest Group (SIG) on Knowledge Discovery & Data Mining, ACM 1(2), pages 1-11, 2000. [11] Chakrabarti S., Dom B., Agrawal R., and Raghvan P., Using taxonomy, discrimination, and signatures to navigate in text databases, IN VLDB, Athtens, Greece, Sept. 1997. [12] Chakrabarti S., Dom B., Agrawal R. and P. Raghvan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, VLDB Journal, Aug. 1998 [13] Joachims T., Text Categorization with Support Vector Machines: Learning with Many Relevant Features, Proceedings of the European Conference on Machine Learning (ECML), Springer, 1998. [14] Joachims T., Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the International Conference on Machine Learning (ICML), 1999. [15] Joachims T., A Statistical Learning Model of Text Classification with Support Vector Machines, Proceedings of the Conference on Research and Development in Information Retrieval (SIGIR), ACM, 2001. [16] Joachims T., Learning to Classify Text using Support Vector Machines, Dissertation, Kluwer, 2002.

9