یادگیری رتبه بندی محتوای فارسی وب بر مبنای برنامه نویسی ژنتیک چند لایه
محورهای موضوعی : عمومى
1 - -
کلید واژه: یادگیری رتبه بندی, مدل برنامه نویسی ژنتیک چند لایه, ویژگی های کلیک از گذر داده, محتوای فارسی وب, مجموعه داده dotIR,
چکیده مقاله :
یادگیری رتبهبندی، یک رویکرد نو ظهور به منظور رفع چالشهای موجود و بهبود عملکرد جویشگرهای وب، بسیار امید بخش و کارآمد است. در عین حال عدم توجه جدی به سوابق تعاملات کاربران با جویشگر طی فرآیند جستجو و ارزیابی نتایج بدست آمده، یکی از معضلات جدی آن بشمار میرود. در عین حال حجم بسیار زیاد ویژگیهای مورد نیاز از اسناد و پرسوجوهای کاربران نیز کاربردی بودن این رویکرد را در شرایط واقعی با ابهام مواجه ساخته است. استفاده از مدل اطلاعات کلیک از گذر دادهها و تولید ویژگیهای کلیک از گذر داده، راهکار نوینی است که بر مبنای آن و با بکارگیری مدل برنامهنویسی ژنتیک چند لایه، مدل رتبهبندی مناسبی تحت عنوان MGP-Rank برای بازیابی اطلاعات انگلیسی وب، عرضه شده است. در این پژوهش این، با عنایت به ویژگیهای خاص زبان فارسی، از طریق ارائه سناریوهای مناسب برای ایجاد ویژگیهای کلیک از گذر داده این الگوریتم، این الگوریتم بومیسازی شده است. نتایج حاصل از ارزیابی عملکرد این الگوریتم در حوزه زبان فارسی با استفاده از مجموعه داده dotIR، حاکی از توانمندی قابل ملاحظه آن نسبت به روشهای مرجع رتبهبندی اطلاعات است. این بهبود عملکرد، بخصوص در بخش ابتدایی فهرست نتایج جستجو که غالباً بیشتر مورد مراجعه کاربران است، قابل توجه است.
Learning to rank (L2R) has emerged as a promising approach in handling the existing challenges of Web search engines. However, there are major drawbacks with the present learning to rank techniques. Current L2R algorithms do not take into account to the search behavior of the users embedded in their search sessions’ logs. On the other hand, machine-learning as a data-intensive process requires a large volume of data about users’ queries as well as Web documents. This situation has made the usage of L2R techniques questionable in the real-world applications. Recently, by the use of the click-through data model and based on the generation of click-through features, a novel approach is proposed, named as MGP-Rank. Using the layered genetic-programming model, MGP-Rank has achieved noticeable performance on the ranking of the English Web content. In this study, with respect to the specific characteristics of the Persian language, some suitable scenarios are presented for the generation of the click-through features. In this way, a customized version of the MGP-Rank is proposed of the Persian Web retrieval. The evaluation results of this algorithm on the dotIR dataset, indicate its considerable improvement in comparison with major ranking methods. The improvement of the performance is particularly more noticeable in the top part of the search results lists, which are most frequently visited by the Web users.
1. Q. Ai, K. Bi, J. Guo, W.B. Croft Croft, “Learning a Deep Listwise Context Model for Ranking Refinement”, In Proceedings of the 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 135-144, 2018.
2. Q. Ai, X. Wang, S. Bruch, N. Golbandi, M. Bendersky, and M. Najork, “Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks”, In Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 85-92, 2019.
3. C.C. Alves, M.A. Gonçalves, D. Sousa, and T. Salles, “Generalized BROOF-L2R: A General Framework for Learning to Rank Based on Boosting and Random Forests”, In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 95-104, 2016.
4. Z. Cao, T. Qin, T.Y. Liu, M.F. Tsai, and H. Li, “Learning to rank: from pairwise approach to listwise approach”, In Proceedings of the 24th International Conference on Machine Learning, pp. 129-136, 2007.
5. S. Chakrabarti, R. Khanna, U. Sawant, and C. Bhattacharyya, “Structured learning for nonsmooth ranking losses”, In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 88-96, 2008.
6. O. Chapelle & Y. Chang, “Yahoo! Learning to Rank Challenge Overview”, Journal of Machine Learning Research, pp. 14, 1-24, 2011.
7. O. Chapelle & M. Wu, “Gradient descent optimization of smoothed information retrieval metrics”, Information Retrieval, Vol. 13, No. 3, pp. 216-235, 2010.
8. W. Chu & Z. Ghahramani, “Preference learning with Gaussian processes”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 137-144, 2005.
9. W. Chu & S.S. Keerthi, “New approaches to support vector ordinal regression”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 145-152, 2005.
10. D. Cossock & T. Zhang, “Subset ranking using regression”, In Proceedings of the 19th annual conference on Learning Theory, pp. 605-619, 2006.
11. F. Dammak, H. Kammoun, and A.B. Hamadou, “Improving pairwise learning to rank algorithms for document retrieval”, In of IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-8, 2017.
12. E. Darrudi, H.B. Hashemi, A. Aleahmad, A. Habibian, A. ZarehBidoki, A. Shakery, and M. Rahgozar, “A standard web test collection for IR domain”, Technical Reoprt, Iran Telecommunication Research Center, 2009.
13. W. Fan, M.D. Gordon, and P. Pathak, “Ranking function optimization for effective web search by genetic programming: an empirical study”, In Proceedings of the 37th Hawaii International Conference on System Sciences, pp. 1-8, 2004.
14. W. Fan, M.D. Gordon, and P. Pathak, “On linear mixture of expert approaches to information retrieval”, Decision Support System, Vol. 42, No. 2, pp. 975-987, 2006.
15. N. Fuhr, “Optimum polynomial retrieval functions based on the probability ranking principle”, ACM Transactions on Information Systems, 183-204, 1989.
16. J. Gao, H. Qi, X. Xia, and J.Y. Nie, “Linear discriminant model for information retrieval”, In Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 290-297, 2005.
17. Z. Hu, Y. Wang, Q. Peng, and H. Li, “Unbiased LambdaMART: An Unbiased Pairwise Learning-to-Rank Algorithm”, In Proceedings of the World Wide Web Conference, pp. 2830-2836, 2019.
18. K. Järvelin & J. Kekäläinen, “IR evaluation methods for retrieving highly relevant documents”, In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 41-48, 2000.
19. K. Järvelin & J. Kekäläinen, “Cumulated gain-based evaluation of IR techniques”, ACM Transactions on Information Systems, Vol. 20, No. 4, pp. 422-446, 2002.
20. X.B. Jin, G.G. Geng, G.S. Xie, and K. Huang, “Approximately optimizing NDCG using pair-wise loss”, Information Sciences, Vol. 453, pp. 50-65, 2018.
21. T. Joachims, “Optimizing search engines using clickthrough data”, In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 133-142, 2002.
22. T. Joachims, L.A. Granka, B. Pan, H.A. Hembrooke, and G .Gay, “Accurately Interpreting Clickthrough Data as Implicit Feedback”, In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 154-161, 2005.
23. A.H. Keyhanipour, B. Moshiri, F. Oroumchian, M. Rahgozar, and K. Badie, “Learning to rank: new approach with the layered multi-population genetic programming on click-through features”, Genetic Programming and Evolvable Machines, Vol. 17, pp. 203-230, 2016.
24. M. Köppel, A. Segner, M. Wagener, L. Pensel, A. Karwath, and S. Kramer, “Pairwise Learning to Rank by Neural Networks Revisited: Reconstruction, Theoretical Analysis and Practical Performance”, arXiv:1909.02768v1, 2019.
25. P. Li, Q. Wu, and C.J. Burges, “McRank: Learning to rank using multiple classification and gradient boosting”, Advances in Neural Information Processing Systems 20, pp. 845-852, 2008.
26. J.Y. Lin, H.R. Ke, B.C. Chien, and W.P. Yang, “Classifier design with feature selection and feature extraction using layered genetic programming”, Expert Systems with Applications, Vol. 34, 1384-1393, 2008.
27. Y. Lin, J. Wu, B. Xu, K. Xu, and H. Lin, “Learning to rank using multiple loss functions”, International Journal of Machine Learning and Cybernetics, Vol. 10, pp. 485-494, 2019.
28. T.Y. Liu, Learning to Rank for Information Retrieval, Berlin: Springer-Verlag, 2011.
29. H. Liu, Z. Wu, X. Zhang, “CPLR: Collaborative pairwise learning to rank for personalized recommendation, Knowledge-Based Systems”, Vol. 148, pp. 31-40, 2018.
30. C. Macdonald, I. Ounis, “Usefulness of Quality Click-through Data for Training”, In Proceedings of the 2009 workshop on Web Search Click Data, pp. 75-79, 2009.
31. C. Macdonald, R.L. Santos, I. Ounis, “On the Usefulness of Query Features for Learning to Rank”, In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 2559-2562, 2012.
32. C.D. Manning, P. Raghavan, and H. Schütze, An Introduction to Information Retrieval, Cambridge University Press, 2008.
33. R. Nallapati, “Discriminative models for information retrieval”, In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 64-71, 2004.
34. L. Pang, J. Xu, Q. Ai, Y. Lan, X. Cheng, and J. Wen, “SetRank: Learning a Permutation-Invariant Ranking Model for Information Retrieval”, arXiv:1912.05891v1, 2019.
35. T. Qin, T.Y. Liu, J. Xu, and H. Li, “LETOR: Benchmark dataset for research on learning to rank for information retrieval”, In Proceedings of the LR4IR 2007, in conjunction with SIGIR 2007, pp. 3-10, 2007.
36. T. Qin, T.Y. Liu, and H. Li, “A general approximation framework for direct optimization of information retrieval measures”, Information Retrieval, Vol. 13, No. 4, pp. 375-397, 2009.
37. R. Rahimi, A. Montazeralghaem, and J. Allan, “Listwise Neural Ranking Models”, In Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 101-104, 2019.
38. E. Renshaw, A. Lazier, C. Burges, T. Shaked, M. Deeds, N. Hamilton, and G. Hullender, “Learning to rank using gradient descent”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 89-96, 2005.
39. S. Tan, Z. Zhou, and P. Li, “Fast Item Ranking under Neural Network based Measures”, In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 591-599, 2020.
40. M. Taylor, J. Guiver, S. Robertson, and T. Minka, “Softrank: optimising non-smooth rank metrics”, In Proceedings of the 1st International Conference on Web Search and Web Data Mining, pp. 77-86, 2008.
41. A. Trotman, “Learning to rank”, Information Retrieval, Vol. 8, No. 3, pp. 359-381, 2005.
42. M.F. Tsai, T.Y. Liu, T. Qin, H.H. Chen, and W.Y. Ma, “Frank: a ranking method with fidelity loss”, In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 383-390, 2007.
43. M.N. Volkovs & R.S. Zemel, “Boltzrank: learning to maximize expected ranking gain”, In Proceedings of the 26th International Conference on Machine Learning, pp. 1089-1096, 2009.
44. J. Wang, L. Yu, W. Zhang, Y. Gong, Y. Xu, and B. Wang, “IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models”, In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 515-524, 2017.
45. T. Xia, S. Zhai, and S. Wang, “Analysis of Regression Tree Fitting Algorithms in Learning to Rank”, arXiv:1909.05965v1, 2019.
46. J. Xu, T.Y. Liu, M. Lu, H. Li, and W.Y. Ma, “Directly optimizing IR evaluation measures in learning to rank”, In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 107-114, 2008.
47. Q. Xu, M. Li, and M. Yu, “Learning to rank with relational graph and pointwise constraint for cross-modal retrieval”, Soft Computing, Vol. 23, pp. 9413-9427, 2019.
48. J.Y. Yeh, J.Y. Lin, H.R. Ke, and W.P. Yang, “Learning to Rank for Information Retrieval Using Genetic Programming”, In Proceedings of the SIGIR 2007 Workshop on Learning to Rank for Information Retrieval, pp. 1-8, 2007.
49. J.Y. Yeh, J.Y. Lin, H.R. Ke, and W.P. Yang, “Learning to Rank for Information Retrieval Using Layered Multi-Population Genetic Programming”, In Proceedings of the 2012 IEEE International Conference on Computational Intelligence and Cybernetics, pp. 45-49, 2012.
50. Y. Yue, T. Finley, F. Radlinski and T. Joachims, “A support vector method for optimizing average precision”, In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 271-278, 2007.
51. Z. Zheng, H. Zha, and G. Sun, “Query-level learning to rank using isotonic regression”, In Proceedings of the SIGIR 2008 Workshop on Learning to Rank for Information Retrieval, pp. 9-14, 2008.
52. W. Zhou, J. Li, Y. Zhou, M.H. Momen, “Bayesian pairwise learning to rank via one-class collaborative filtering”, Neurocomputing, Vol. 367, pp. 176-187, 2019.
53. X. Zhu & D. Klabjan, “Listwise Learning to Rank by Exploring Unique Ratings”, In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 798-806, 2020.
54. O. Zoeter, M. Taylor, E. Snelson, J. Guiver, N. Craswell, N., and M. Szummer, “A decision theoretic framework for ranking using implicit feedback”, In Proceedings of the SIGIR 2008 Workshop on Learning to Rank for Information Retrieval, pp. 24-31, 2008.
فصلنامة علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال دهم، شمارههای 37 و 38، پاییز و زمستان 1397 |
|
یادگیری رتبهبندی محتوای فارسی وب بر مبنای برنامهنویسی ژنتیک چند لایه
امیر حسین کیهانی پور
استادیار، گروه مهندسی کامپیوتر، دانشکده مهندسی، پردیس فارابی، دانشگاه تهران
تاریخ دریافت:15/12/1398 تاریخ پذیرش: 21/03/1399
چكيده
یادگیری رتبهبندی، یک رویکرد نو ظهور به منظور رفع چالشهای موجود و بهبود عملکرد جویشگرهای وب، بسیار امید بخش و کارآمد است. در عین حال عدم توجه جدی به سوابق تعاملات کاربران با جویشگر طی فرآیند جستجو و ارزیابی نتایج بدست آمده، یکی از معضلات جدی آن بشمار میرود. در عین حال حجم بسیار زیاد ویژگیهای مورد نیاز از اسناد و پرسوجوهای کاربران نیز کاربردی بودن این رویکرد را در شرایط واقعی با ابهام مواجه ساخته است. استفاده از مدل اطلاعات کلیک از گذر دادهها و تولید ویژگیهای کلیک از گذر داده، راهکار نوینی است که بر مبنای آن و با بکارگیری مدل برنامهنویسی ژنتیک چند لایه، مدل رتبهبندی مناسبی تحت عنوان MGP-Rank برای بازیابی اطلاعات انگلیسی وب، عرضه شده است. در این پژوهش این، با عنایت به ویژگیهای خاص زبان فارسی، از طریق ارائه سناریوهای مناسب برای ایجاد ویژگیهای کلیک از گذر داده این الگوریتم، این الگوریتم بومیسازی شده است. نتایج حاصل از ارزیابی عملکرد این الگوریتم در حوزه زبان فارسی با استفاده از مجموعه داده dotIR، حاکی از توانمندی قابل ملاحظه آن نسبت به روشهای مرجع رتبهبندی اطلاعات است. این بهبود عملکرد، بخصوص در بخش ابتدایی فهرست نتایج جستجو که غالباً بیشتر مورد مراجعه کاربران است، قابل توجه است.
واژههای كليدي: یادگیری رتبهبندی، مدل برنامهنویسی ژنتیک چند لایه، ویژگیهای کلیک از گذر داده، محتوای فارسی وب، مجموعه داده dotIR
1- مقدمه
استفاده گسترده کاربران محیط وب از جویشگرها به عنوان یکی از مهمترین و پرکاربردترین سامانههای موجود در این محیط، موجب گردیده است تا پژوهشهای زیادی به منظور تقویت و بهبود فرآیند جستجو و رتبهبندی اسناد مرتبط با پرسوجوهای کاربران، صورت گیرد. گرچه تحقیقات در زمینه انجام رتبهبندی مناسب نتایج جستجوهای کاربران
جویشگرها، پیشینه قابل توجهی دارد، ولی در سالهای اخیر با کاربرد گستردهتر این سامانهها توسط کاربران، حجم قابل
نویسندۀ عهدهدار مکاتبات: امیر حسین کیهانی پور keyhanipour@ut.ac.ir |
نویسندۀ عهدهدار مکاتبات: امیر حسین کیهانی پور keyhanipour@ut.ac.ir |
یادگیری رتبهبندی، به مجموعه روشهای یادگیری ماشینی اطلاق میشود كه در عمليات رتبهبندي، به انجام يادگيري و تشخیص مدل مناسب جهت رتبهبندی اطلاعات، ميپردازند [28]. یادگیری رتبهبندی، كاربردهاي متعددي در زمینه بازيابي اطلاعات1، پردازش زبان طبيعي2 و نیز دادهكاوي3 دارد. در تحقیقات انجام شده در این خصوص، به این نکته توجه شده است که کاربران جویشگرها که بطور مستقیم با این سامانهها درگیر هستند، قادر به ارایه بهترین قضاوتها در مورد کیفیت عملکرد این سامانهها میباشند. با این وجود، عدم تمایل اکثریت کاربران به ارایه قضاوت صریح از عملکرد جویشگرهای مورد استفاده، طراحان این سامانهها را بر آن داشته است تا از سوابق تعاملات کاربران طی جستجوهای بعمل آمده، که اصطلاحاً «اطلاعات کلیک از گذر داده4»، نامیده میشود، به منظور بررسی و بهبود عملکرد این سامانهها بهره گیرند [21]. مطالعات انجام شده، نشان میدهد که استفاده از اطلاعات کلیک از گذر داده، میتواند منجر به بهبود عملکرد جویشگرهای وب،
شود [30] و [22] و [31]. علیرغم این موضوع، فقدان اطلاعات کلیک از گذر داده در اغلب مجموعههای داده محک موجود در زمینه یادگیری رتبهبندی، موجب شده است تا اکثر الگوریتمهای ارایه شده در این حوزه، از این اطلاعات ارزشمند، بیبهره باشند. در عین حال، استفاده اغلب روشهای موجود از تعداد زیادی از ویژگیهای اسناد و پرسوجوها، کاربرد آنها را در شرایط واقعی، دشوار میسازد.
در ادامه این نوشتار، ابتدا به مرور تحقیقات مرتبط پرداخته خواهد شد و بصورت تحلیلی، ضرورت انجام این پژوهش، مطرح خواهد شد. پس از آن، معرفی الگوریتم
MGP-Rank صورت خواهد گرفت و نحوه عملکرد آن بیان خواهد شد. سپس نتایج حاصل از ارزیابی عملکرد الگوریتم یادگیری رتبهبندی MGP-Rank در مقایسه با روشهای رتبهبندی مرجع، بر اساس شاخصهای ارزیابی فرآیند بازیابی اطلاعات، بصورت تحلیل مورد قیاس قرار خواهد گرفت. بخش پایانی این نوشتار نیز به جمعبندی این پژوهش و نیز معرفی حوزههای تحقیقاتی آتی، اختصاص یافته است.
2- مرور تحقیقات مرتبط
با توجه به نقش محوري رتبهبندي نتایج حاصل از جستجو در جویشگرهای وب، در سالهای گذشته تحقيقات گستردهای در این در اين زمينه صورت پذيرفته است. بصورت ویژه طی سالیان اخير، موضوع يادگيري رتبهبندي، به عنوان يک روش نوين براي انجام رتبهبندي با استفاده از تکنيکهاي يادگيري ماشيني، مطرح شده است و در واقع، يادگيري رتبهبندي، به صورت ترکيبي از يادگيري ماشيني، بازيابي اطلاعات و نیز پردازش زبان طبيعي قابل توصيف است. بطور کلي، دو تعريف عمده براي مفهوم يادگيري رتبهبندي، ارائه شده است. در نگرش کلان، يادگيري رتبهبندي به هر نوع کاربرد تکنيکهاي يادگيري ماشيني در مساله رتبهبندي، اطلاق ميشود. در مقابل و در يک نگرش جزييتر، يادگيري رتبهبندي به آن دسته از روشهاي يادگيري ماشيني اشاره دارد که براي ايجاد مدلهاي رتبهبندي در مسايل «ايجاد رتبهبندي5» و «تجميع رتبهبندي6»، مورد استفاده قرار ميگيرند. در [28]، یک دستهبندی کلي از انواع روشهای مطرح در زمینه يادگيري رتبهبندي، در شکل شماره یک ارائه شده است.
در هر دو دسته تکنیکهای یادگیری رتبهبندی را میتوان جزء روشهای یادگیری ماشینی تحت نظارت، بشمار آورد. بر این اساس، دادگان پایه یادگیری مشتمل بر مجموعهای از اسناد و پرسوجوها و نیز قضاوتهای کاربران خبره در مورد با میزان مرتبط بودن این اسناد و پرسوجوها در اختیار است. تولید مدل بر اساس قضاوت کاربران در رابطه با میزان مرتبط بودن زوجهای اسناد - پرسوجوها صورت میگیرد. در روشهای ایجاد رتبهبندی، بر اساس مجموعه داده یادگیری، مدلی به منظور رتبهبندی نتایج حاصل از پرسوجوهای کاربران، تولید میشود. در مقابل، در روشهای تجمیع رتبهبندی، نتایج حاصل از رتبهبندی تعدادی از روشهای رتبهبندی پایه، جهت تولید یک مدلی تجمیعی، با یکدیگر ادغام میشوند. بصورت خلاصه، میتوان گفت در فرآيند «ايجاد رتبهبندي»، تهيه ليست مرتب، بر اساس ويژگيهاي درخواست و پيشنهادهاي ممکن، صورت ميگيرد، در حالي که در عمليات «تجميع رتبهبندي»، از رتبهبنديهاي اولیه صورت گرفته، استفاده ميشود. معمولاً هرگاه به مساله يادگيري رتبهبندي اشاره شود، منظور، ايجاد رتبهبندي بر اساس يادگيري تحت نظارت است [28]. الگوریتم ارایه شده در این پژوهش یعنی
MGP-Rank نیز از همین دسته روشهای یادگیری رتبهبندی، بشمار میرود.
[1] Information retrieval
[2] Natural Language Processing (NLP)
[3] Data mining
[4] Click-through data
[5] Rank Creation
[6] Rank Aggregation
|
شکل 1: طبقهبندي انواع روشهای يادگيري رتبهبندي (Liu 2011)
شمای کلي عملیات روشهاي يادگيري رتبهبندي، در شکل شماره دو نشان داده شده است. بر اساس اين ساختار، از آنجا يادگيري رتبهبندي، گونهاي از يادگيري تحت نظارت ميباشد، نیاز به مجموعه داده آموزشي دارد. فرآيند توليد مجموعه داده آموزشي، شباهت زيادي با ايجاد داده آموزشي براي ارزيابي دارد. يک مجموعه داده آموزشي، عموماً شامل موارد زير است:
· تعداد پرسوجوي آموزشي،
· مجموعه اسناد متناظر با آنها که به صورت بردار ويژگيها نمايش داده ميشوند (که در آن، برابر با تعداد اسناد متناظر پرس وجوي است)، و
· قضاوتهاي ميزان مرتبط بودن اسناد با پرسوجوها.
شکل 2: شماي کلي چارچوب روشهاي رتبهبندي مبتني بر يادگيري (Liu 2011)
بر این اساس، يک الگوريتم يادگيري به منظور توليد مدل رتبهبندي، استفاده ميشود، به نحوي که اين مدل، قادر باشد با توجه به تابع زيان1 مورد استفاده، ميزان مرتبط بودن اسناد به پرسوجوها را با دقت بالا و حتيالمقدور مشابه قضاوتهاي انساني، پيشبيني نمايد. در خلال فاز آزمون و با دريافت يک پرسوجوي جديد، مدل توليد شده طي فاز آموزش، روي مجموعه اسناد مورد نظر، اِعمال ميشود تا فهرست رتبهبندي شده از آن اسناد، ايجاد شود. بر اساس اين رويکرد، روشهاي يادگيري رتبهبندي را ميتوان به روشهاي نقطهاي2، روشهاي جفتي3 و نيز روشهاي مبتني بر فهرست4، دستهبندي نمود. هر دسته از اين روشها، فرآيند يادگيري رتبهبندي را به اَشکال مختلف، مدلسازي ميکنند. به عبارت ديگر، هر کدام از اين انواع روشها، تعاريف متفاوتي از فضاهاي ورودي و خروجي بيان ميکنند يا ممکن است از فرضيههاي متفاوتي استفاده کنند و نيز توابع زيان متفاوتي را بکار گيرند.
بطور کلی، روشهاي نقطهاي، وابستگي بين اسناد را در نظر نميگيرند و بنابراين موقعيت يک سند در ليست مرتب نهايي، در محاسبات، لحاظ نميشود. فضاي ورودي در روشهاي جفتي، زوجهاي اسناد ميباشد که بهصورت بردارهاي ويژگيها، نمايش داده ميشوند. فضاي خروجي نيز شامل اولويت بين این زوجهای اسناد است که دامنه مقادير آن از مجموعه ميباشد. در برخی از روشهای ارائه شده در این دسته، رتبهبندی به مساله رگرسيون، تقليل مييابد
[10] و [15] و [45]. یک رویکرد دیگر، مدلسازی مساله رتبهبندی بصورت یک مساله ردهبندی است. در تحقيقات مختلف، امکان استفاده از مدل ردهبندي براي مساله رتبهبندي در حوزه بازيابي اطلاعات، بررسی شده است که از جمله آنها ميتوان به [33] و [44] و [27]. اشاره نمود. در این پژوهشها، ایده تبدیل رتبهبندی به مساله ردهبندي دودويي مطرح شده است. در تحقیقات دیگری نظیر [25] و [3]. بکارگیری ردهبندي چند کلاسه براي حل مساله رتبهبندي، پیشنهاد شده است. بکارگیری مدل رگرسيون ترتيبي، در دسته سوم روشهای نقطهای، دنبال شده است که به عنوان نمونه ميتوان به [8] و [9] اشاره نمود. با توجه به اينکه اغلب شاخصهاي ارزيابي در حوزه بازيابي اطلاعات مبتني بر موقعيت اسناد و در سطح پرسوجوها محاسبه ميشوند، روشهاي نقطهاي در شرایط واقعی، دچار محدوديتهاي جدي هستند.
فضاي فرضيه در روشهاي جفتي یادگیری رتبهبندی، شامل توابع دو متغيرهاي است که يک جفت سند را به عنوان ورودي، دريافت ميکنند و ترتيب نسبي آن دو را در قالب خروجي، ارائه ميدهند. ضمناً تابع زيان مورد استفاده در روشهاي جفتي، صرفاً ترتيب نسبي بين زوجهاي اسناد را در نظر ميگيرد. در نتيجه، موقعيت نهايي اسناد در فهرست مرتب نهايي، به سختي قابل استحصال خواهد بود. از جمله ایدههای مطرح شده در روشهای جفتی رتبه بندی یادگیری، میتوان به استفاده از شبکههاي عصبي مصنوعی [38] و [16] و [52] و [24]. استفاده از مدل ماشین بردار پشتیبان5 [21] و [17]. و نيز بکارگیری الگوریتمهای يادگيري ماشيني [4] و [51] و [11] و [20] و [29]. اشاره نمود. ذکر این نکته در خصوص روشهاي جفتي، ضرورت دارد که با توجه به اينکه اغلب شاخصهاي ارزيابي در حوزه بازيابي اطلاعات، در سطح پرسوجوها و بر مبناي موقعيت نهايي اسناد در فهرست مرتبشده عمل ميکنند، فاصله قابل توجهی، بين مدل عملکرد روشهاي جفتي و رتبهبندي مطلوب در مقوله بازيابي اطلاعات، مشاهده ميشود.
فضاي ورودي در روشهاي مبتني بر فهرست، شامل مجموعه اسناد متناظر با پرسوجوي داده شده است. فضاي خروجي نیز عبارتست از فهرست مرتبشده اسناد يا به تعبير ديگر، جايگشتي از مجموعه اسناد داده شده است. این دسته از الگوریتمهای یادگیری رتبهبندی را بر اساس نوع تابع زیان مورد استفاده، به دو دسته، تقسیم نمود. دسته نخست، روشهای بهینهسازی مستقیم6 نامیده میشوند و شامل روشهای رتبهبندی هستند که توابع زیان آنها، ارتباط مستقیمی با شاخصهای استاندارد ارزیابی در حوزه بازیابی اطلاعات دارد [40] و [50] و [46] و [54] و [5] و [36] و [7] و [49]. در برخی دیگر از روشهای اخیر، از رویکرد یادگیری عمیق7 برای تخمین شاخصهای ارزیابی استفاده شده است [1] و [37] و [34] و [39]. همچنین ایده استفاده از قابلیتهای الگوریتم ژنتیک، به منظور بهینهسازی شاخصهای ارزیابی، در برخی تحقیقات مورد توجه بوده است که از جمله آنها میتوان به این موارد اشاره کرد: [13] و [41] و [14] و [48] و [23]. در مقابل، در دسته دوم روشهای فهرستی، الگوریتمهای رتبهبندی قرار میگیرند که در آنها توابع زیان مورد استفاده، ارتباط مستقیمی با شاخصهای استاندارد ارزیابی جستجو، ندارد. از جمله اين روشها ميتوان به [4] و [43] و [34] و [53] و [44] اشاره نمود.
علیرغم مطالعات گسترده صورت گرفته در حوزه یادگیری رتبهبندی، این حوزه تحقیقاتی، با نواقص و محدودیتهای جدی، همراه است. از مهمترین این معضلات، عدم استفاده از اطلاعات مربوط به سوابق رفتارهای کاربران در حین انجام جستجوها، در فرآیندهای بازیابی و رتبهبندی نتایج است. در واقع، عدم اقبال کاربران برای ارایه بازخورد صریح از نحوه عملکرد جویشگر مورد استفاده، محققان را بر آن داشته است تا با پردازش سوابق رفتار کاربران، بازخورد ضمنی رفتار آنها را استخراج کنند. بنا بر نتایج تحقیقات انجام شده، اطلاعات حاصل از پردازش سوابق تعاملات و رفتارهای کاربران، که اصطلاحاً اطلاعات کلیک از گذر داده، نامیده میشود، بسیار ارزشمند بوده و بکارگیری آنها میتواند منجر به بهبود کیفیت فرآیند بازیابی اطلاعات، به میزان قابل توجهی شود
[22] و [30] و [31]. فقدان این قبیل اطلاعات، در اغلب مجموعههای داده محک8 موجود در زمینه یادگیری رتبهبندی، باعث گردیده است تا اغلب روشهای یادگیری رتبهبندی موجود، امکان استفاده از این قبیل اطلاعات را نداشته باشند که این امر، یکی از معضلات و محدودیتهای اصلی پیشروی حوزه یادگیری رتبهبندی، بشمار میرود. در عین حال، عرضه انبوهی از ویژگیهای مرتبط با پرسوجوها و نتایج و بکارگیری آنها در الگوریتمهای موجود، کاربری آنها را در شرایط واقعی، دشوار میسازد. علت این امر آن است که در شرایط واقعی، تهیه دادههای مربوط به این تعداد زیاد از ویژگیها، فرآیندی دشوار و وقتگیر میباشد. بر این اساس و با الهام از پایه مفهوم «اطلاعات کلیک از گذر داده»، ایده جدیدی در سالهای اخیر مطرح شده است که در آن، به تولید مجموعهای از ویژگیهای ثانویه بر پایه ویژگیهای پایه مجموعه داده محک مورد استفاده پرداخته میشود. این مجموعه را اصطلاحاً «ویژگیهای کلیک از گذر داده» مینامند. در [23]، با اِعمال مدل برنامهنویسی ژنتیک چند لایه روی ویژگیهای کلیک از گذر داده، الگوریتم جدیدی موسوم به MGP-Rank ارائه شده است که عملکرد قابل توجهی در رتبهبندی اطلاعات انگلیسی وب داشته است. توفیق این الگوریتم، الهام بخش این پژوهش بوده است تا با تطبیق ساختار این الگوریتم بر اساس ویژگیهای زبان فارسی، الگوریتم رتبهبندی قدرتمندی برای دادگان فارسی وب، حاصل شود.
3- معرفی روش پیشنهادی
این بخش به معرفی و بیان نحوه عملکرد الگوریتم MGP-Rank اختصاص یافته است و جزئیات گامهای اجرای این الگوریتم، مورد بحث و بررسی قرار گرفته است.
3-1-کلیات الگوریتم MGP-Rank
الگوریتم MGP-Rank با استفاده از مدل برنامهنویسی ژنتیک چند لایه، روی ویژگیهای کلیک از گذر داده، عمل میکند[23]. در این الگوریتم، ویژگیهای کلیک از گذر داده، در یک چارچوب مدل برنامهنویسی ژنتیک چند لایه و چند جمعیتی، بکار گرفته میشوند تا بر اساس برخی شاخصهای بازیابی اطلاعات، بهترین توابع رتبهبندی ممکن، شناسایی شوند. مهمترین مزیت مدل برنامهنویسی ژنتیک چند لایه، قابلیت جستجوی سریعتر و فراگیرتر آن نسبت به مدل برنامهنویسی ژنتیک معمول است. بر این اساس، الگوريتم MGP-Rank، از اين جهت با روشهاي مشابه، متفاوت است كه در آن، از مفهوم اطلاعات كليك از گذر داده [21] به منظور توليد ويژگيهاي كليك از گذر داده، استفاده شده است. فرآيند توليد ويژگيهاي كليك از گذر داده، در هر دو حالت وجود يا عدم وجود اطلاعات مرتبط با كليك از گذر داده در مجموعه داده محك مورد استفاده، امكانپذير است. سپس از اين ويژگيها در قالب معماري LAGEP [26]، به منظور يافتن توابع رتبهبندي مناسب، استفاده ميشود كه تركيبي از ويژگيهاي مرتبط با محتواي اسناد، ويژگيهاي ساختاري صفحات وب و نيز ويژگيهاي مرتبط با نحوه جستجوي كاربران، خواهد بود. در تعيين توابع برتر، از شاخصهاي ارزيابي مرتبط با مقوله بازيابي اطلاعات نظير دقت9، صحت10، فراخواني11، F-measure و نيز خاص بودن12 به عنوان توابع سازگاري، مورد استفاده قرار گرفته است [32]. نتایج حاصل از آزمایشهای صورت گرفته، نشاندهنده کارآمدی روش ارایه شده در مقایسه با الگوریتمهای مطرح یادگیری رتبهبندی، بر اساس شاخصهای دقت و NDCG است. این بهبود بازیابی، عمدتاً در بخش بالایی فهرست نتایج جستجوها قابل توجه است که غالباً بیشتر توجه کاربران را به خود، معطوف میدارد. در عین حال، بهبود حاصل از الگوریتم ارایه شده، در شرایطی که داده محک اولیه، در برگیرنده اطلاعات کلیک از گذر داده کاربران باشد، بیشتر خواهد بود.
3-2- مراحل الگوریتم MGP-Rank
الگوریتم MGP-Rank، متشکل از دو مرحله است که در گام نخست آن، بر اساس مفهوم کلیک از گذر داده، از اطلاعات موجود در مجموعه داده محک اولیه، هشت ویژگی ثانویه تولید میشود که آنها را ویژگیهای کلیک از گذر داده مینامیم. برای این منظور، از تعدادی سناریوی متفاوت جهت تولید این ویژگیها، استفاده میشود. نکته جالب توجه در خصوص این فرآیند، آن است که این کار، حتی در غیاب اطلاعات کلیک از گذر داده در مجموعه داده محک اولیه نیز امکانپذیر میباشد. در ادامه و طی گام دوم، از این ویژگیهای ثانویه به منظور تولید توابع رتبهبندی، استفاده میشود که در ساختار مدل برنامهنویسی ژنتیک چند لایه موسوم به LAGEP [25]، بر اساس توابع سازگاری مرتبط با حوزه بازیابی اطلاعات، تکامل مییابند تا اینکه نهایتاً توابع رتبهبندی مطلوب، شناسایی شوند.
3-2-1- استخراج ویژگیهای کلیک از گذر داده
هر چند تحقيقات مختلف نشان دادهاند كه بکارگیری اطلاعات كليك از گذر داده در بهبود نتايج بازيابي، مفيد ميباشد
[22] و [30] و [31]، ولي اين قبيل اطلاعات در بسیاری از مجموعههاي داده ارائه شده براي مساله يادگيري رتبهبندي نظير مجموعه داده LETOR مربوط به مايكروسافت [35] و نیز مجموعه داده تهيه شده توسط شركت یاهو [6]، مورد استفاده قرار نگرفته است. از سوي ديگر، اين مجموعههاي داده، شامل تعداد زيادي از ويژگيها هستند و الگوريتمهاي مستخرج از اين آنها، بدليل بكارگيري اين حجم بالا از ويژگيها، در شرايط كاربري واقعي، چندان کارآمد نخواهند بود. با توجه به اين واقعيات، الگوريتم MGP-Rank در گام نخست و بر اساس مدل مفهومي اطلاعات كليك از گذر داده، اقدام به تهيه هشت ويژگي ثانويه از روي اطلاعات موجود در مجموعه داده محك اوليه داده شده، موسوم به ويژگيهاي كليك از گذر داده، ميكند. جزییات مفهومی این ویژگیها در ادامه این بخش، بیان شده است.
در فرآیند استخراج ویژگیهای کلیک از گذر داده، یک بازنمایی فشرده از مجموعه داده محک اولیه بر اساس مدل مفهومی کلیک از گذر داده ارایه میشود [23]. در واقع، مفهوم کلیک از گذر داده، بصورت یک سهتایی شامل پرسوجوی کاربر، فهرست نتایج و مجموعه کلیکهای کاربر، تعریف شده است [21]. با الهام از این مدل، در گام تبدیل، تعداد هشت ویژگی جدید موسوم به ویژگیهای کلیک از گذر داده، در سه گروه ، و ، بشرح زیر تعریف میشود:
جدول 1: ویژگیهای کلیک از گذر داده معرفی شده مبتنی بر مفهوم اطلاعات کلیک از گذر داده
|
در این دستهبندی، مجموعه ، شامل ویژگیهایی است که تا حدی، مرتبط با ماهیت پرسوجوی کاربر هستند. در این دسته، ویژگی ، به میزان تکرار واژگان پرسوجوی کاربر در بخشهای مختلف یک سندِ پاسخ، شامل: آدرس (URL)، عنوان و متن مرتبط میباشد. ویژگی ، به میزان مرتبط بودن سند با توجه به پرسوجوی کاربر، اشاره میکند که در محاسبه آن، ترکیبی از نتایج روشهای رتبهبندی وابسته به پرسوجوی کاربر از جمله روشهای مبتنی بر مدل فضای برداری و روشهای مدل زبانی، مورد استفاده قرار میگیرد. نهایتاً ویژگی ، معطوف به تعداد پاسخهای ارایه شده در قبال پرسوجوی مورد نظر میباشد.
به همین ترتیب، دسته ، شامل ویژگیهایی است که تاکید بیشتری بر مشخصات اسناد، بصورت مستقل از پرسوجوی مطرح شده از سوی کاربر دارند. در این دسته، ویژگی ، به رتبه مطلق یک سند صرفنظر از پرسوجوی کاربر، میپردازد که طبعاً اطلاعاتی نظیر در آن، نقش مهمی ایفا میکنند. ویژگی به طول یک سند اشاره دارد و ترکیبی از اطلاعات طول بخشهای مختلف یک سند از جمله URL، عنوان و متن آن را شامل میشود.
تمرکز عمده ویژگیهای دسته ، بر اطلاعات قابل حصول از یک زوج سند-پرسوجو، در رابطه با کلیکهای کاربران است. در این دسته، ویژگی ، به میزان خاص بودن اطلاعات یک سند، طی تراکنشهای کاربران در پرسوجوهای مختلف، اشاره میکند و قصد دارد تا به نوعی، به این نکته بپردازد که یک سند پاسخ، چقدر شامل موضوعات خاص است، بنحویکه در تعداد معدودی از پرسوجوها، به عنوان یک پاسخ بالقوه، مورد توجه کاربران واقع شده است. ویژگی نیز سعی در نشان دادن میزان جلب توجه کاربران و سامانههای بازیابی طی پرسوجوهای مختلف به یک سند خاص، دارد. در محاسبه این ویژگی، طبعاً اینکه یک سند، بعنوان اولین یا آخرین پاسخ بالقوه از سوی کاربر، کلیک شده است، حایز اهمیت میباشد. نهایتاً ویژگی ، به میزان پتانسیل سند مورد نظر برای دریافت کلیک کاربران طی پرسوجوهای مختلف، میپردازد.
نکته قابل توجه این است که ویژگیهای هشتگانه مندرج در جدول شماره یک را میتوان در هر دو صورتِ وجود یا عدم وجودِ اطلاعات صریح کلیک از گذر داده در مجموعه داده محک اولیه، محاسبه نمود. طبعاً روند محاسبه این ویژگیها، وابسته به مفهوم و ساختار ویژگیهای اصلی موجود در مجموعههای داده محک مختلف، متفاوت خواهد بود. بر این اساس، در بخش 3-4، سناریوهایی برای محاسبه این ویژگیها روی مجموعه داده فارسی dotIR پیشنهاد میشود.
3-2-2- بکارگیری چارچوب برنامهنویسی ژنتیک چند لایه
ویژگیهای کلیک از گذر داده حاصل از اجرای گام نخست الگوریتم MGP-Rank، به عنوان ورودی، جهت بکارگیری در چارچوب مدل برنامهنویسی ژنتیک چند لایه و چند جمعیتی موسوم به LAGEP، بکار گرفته میشوند [26]. در این ساختار، هر جمعیت، شامل تعدادی افراد است که در اینجا به عنوان توابع رتبهبندی بالقوه، مطرح میباشند. یک فرد این جمعیت مثلاً ، بصورت سهگانه
نمایش داده میشود که در آن، ، مجموعه متغیرها، ، مجموعه مقادیر ثابت و ، مجموعه عملگرهای ریاضی است. متغیرها، همان ویژگیهای موجود در دادههای آموزشی هستند. طی بخش بعدی، جزییات ساختار استفاده شده در آزمایشهای انجام شده، بیان خواهد شد. بر این اساس، یک جمعیت مانند که شامل فرد باشد را میتوان بصورت زیر تعریف نمود: . هر فرد عضو این جمعیتها را میتوان بصورت یک درخت دودویی نمایش داد که برگهای آن، یا متغیرها (ویژگیهای زوجهای سند-پرسوجو) و یا مقادیر ثابت هستند و گرههای میانی نیز عملگرهای ریاضی میباشند. به عنوان یک نمونه، در شکل شماره سه، بازنمایی فردی از جمعیت را که یک تابع رتبهبندی بصورت است، در قالب درخت دودویی، نمایش داده شده است.
شکل 3: بازنمایی تابع بصورت درخت دودویی
هر جمعیت با استفاده از سه عملگر ژنتیکی اصلی، یعنی ادغام13، جهش14 و بازتولید15، تکامل مییابند. نرخ بکارگیری عملگرهای سهگانه ادغام، جهش و بازتولید، به ترتیب برابر با ، و میباشد. در بکارگیری عملگر جهش، نخست بصورت تصادفی، گرهای از ساختار دودویی فرد مورد نظر به عنوان نقطه جهش16 در نظر گرفته میشود و با گره دیگری که از مجموعه متناظر یعنی ، ویا ، که بصورت تصادفی انتخاب شده است، جایگزین میشود. در واقع، هدف عملگر جهش، اجتناب از بهینههای محلی است، زیرا با بکارگیری این عملگر، افراد جدیدی حاصل میشوند که ممکن است تا بحال در جمعیتهای مورد مطالعه، مشاهده نشده باشند. به همین ترتیب، در عملگر ادغام نیز زیردرختهایی از دو فرد که بصورت تصادفی انتخاب شدهاند، با یکدیگر جایگزین میشوند و در نتیجه آن، دو فرد جدید، حاصل میشوند. نهایتاً در عملگر بازتولید، قاعده طبیعی بقای قویترین و مناسبترین افراد، مدلسازی میشود و بهترین فرد هر نسل از جمعیت، عیناً در نسل بعدی نیز فرصت حضور، خواهد یافت. با توجه به اینکه عملگر جهش، تنوع افراد یک جمعیت را کنترل میکند، بدیهی است که نرخ بکارگیری آن () طی فرآیند تکامل یک جمعیت، بصورت مناسبی تنظیم شود. در LAGEP، این فرآیند از طریق روش تنظیم تطبیقی نرخ جهش (AMRT17) صورت میپذیرد که جزییات آن در [26] ذکر شده است. بطور خلاصه، در هر نسل از جمعیت، روش AMRT ، اقدام به ارزیابی میزان سازگاری افراد آن جمعیت میکند. چنانچه مقادیر میزان سازگاری افراد، یکسان باشد، مقدار افزایش مییابد و در غیر اینصورت، نرخ جهش، برابر با مقدار اولیه آن، خواهد بود. علاوه بر آن، با توجه به اینکه: میباشد، افزایش ، به معنی کاهش است. در تحقیق انجام شده، مشخص شده است که استفاده از این تکنیک، منجر به بهبود عملکرد LAGEP خواهد شد [26]. ضمناً بایستی خاطر نشان کرد که برای انتخاب افراد جهت اِعمال عملگرهای ادغام و جهش، میتوان از روشهای انتخاب مختلف نظیر انتخاب تصادفی18 یا انتخاب از طریق مسابقه استفاده نمود19. در روش انتخاب از طریق مسابقه، ابتدا افرادی از جمعیت هدف به تعداد مشخصی که اصطلاحاً اندازه مسابقه20 نامیده میشود، بصورت تصادفی، انتخاب میشوند و سپس بر اساس میزان سازگاری آنها، یک یا دو نفر آنها از به ترتیب، جهت عملگرهای جهش یا ادغام، برگزیده میشوند.
در معماری معرفی شده برای LAGEP، جمعیتها در یک ساختار لایهای قرار میگیرند که هر لایه، شامل تعدادی جمعیت و مجموعه متغیرها و پارامترهای مختص به خود است. در واقع، هر لایه از مدل LAGEP، خود، یک مدل چند جمعیتی از مدل برنامهنویسی ژنتیک است که با استفاده از مجموعه داده آموزشی یکسانی، تکامل مییابند و بهترین افراد آنها در یک مجموعه قرار داده میشوند و بنا به مدل تشریح شده در [26]، با استفاده از آنها دادههای آموزشی برای لایه بعدی، تولید میشود. در هر لایه و طی تعدادی تکرار، جمعیتها تکامل پیدا میکنند و در رقابت افراد آنها با یکدیگر، تنها تعداد معدودی از بهترین آنها با توجه به میزان سازگاری، برای بقا در نسل بعد، باقی میمانند. تولید مجموعه متغیرهای لایههای بعدی نیز طی روش مشابهی، صورت میگیرد [26]. پس از اتمام فرآیند تکامل در همه لایهها، خروجی آخرین لایه، به عنوان خروجی نهایی فرآیند LAGEP، در نظر گرفته میشود. شکل شماره چهار، شمای کلی تکنیک برنامهنویسی چند لایه و چند جمعیتی را نشان میدهد.
شکل 4: شمای کلی تکنیک برنامهنویسی چند لایه و چند جمعیتی (Lin et al. 2008)
4- آزمایشهای صورت گرفته
در این بخش، ابتدا به معرفی داده محک dotIR میپردازیم و سپس، شاخصهای مورد استفاده در ارزیابی رتبهبندی بیان خواهند شد. ادامه این بخش، به ذکر سناریوهای استخراج ویژگیهای کلیک از گذر داده روی مجموعه داده محک dotIR، اختصاص یافته است. پس از آن، تنظیمات و پارامترهای آزمایشهای بعمل آمده، مطرح میشود و نهایتاً به طرح نتایج حاصل از آزمایشهای صورت گرفته و نیز تحلیل نتایج بدست آمده، خواهیم پرداخت.
4-1- معرفی داده محک مورد استفاده
در بررسي عملكرد الگوريتم MGP-Rank در محیط وب فارسی، از مجموعه داده dotIR استفاده شده است كه مشخصات و ساختار آن در ادامه، بيان شده است. مجموعه داده محك dotIR، تنها داده محك در دسترس براي بازيابي اطلاعات فارسي در محيط وب ميباشد. اين مجموعه داده، توسط دانشگاه تهران و با حمايت مركز تحقيقات مخابرات ايران، در سال 1388 ايجاد شده است. توليد اين مجموعه داده، بر اساس خزش صورت گرفته در دامنه .ir طي سال 1388 و دادههاي جمعآوري شده از حدود 8.5 ميليون سند در اين دامنه، انجام شده است [12]. اين مجموعه داده، شامل 50 پرسوجوي مختلف و هزار سند به ازاي هر يك از اين پرسوجوها است كه جمعاً پنجاه هزار زوج پرسوجو-سند را تشكيل ميدهند. به ازاي هر يك از زوجهای داده، 56 ويژگي مختلف استخراج شده است كه فهرست آنها در جدول پیوست شماره یک، آمده است. این ویژگیها در سه دسته کلی یعنی ویژگیهای مبتني بر محتوا، ویژگیهای مبتني بر پيوند و نیز ویژگیهای ترکیبی، ارائه شدهاند. ضمناً قضاوت انساني در مورد ميزان مرتبط بودن هر زوج پرسوجو-سند، در دو سطح مرتبط و نامرتبط، انجام شده است.
به منظور سهولت ارزيابي الگوريتمها، اين مجموعه داده به پنج چين مختلف، تقسيمبندی شده است. هر دسته، بشرح مندرج در جدول شماره دو، شامل يك بخش آموزش، يك بخش اعتبارسنجي و همچنين يك بخش آزمون ميباشد.
جدول 2: دستهبندي مجموعه داده dotIR به بخشهاي آموزش، اعتبارسنجی و آزمون
(Darrudi et al. 2009)
چين | داده آموزش | داده اعتبارسنجي | داده آزمون |
Fold1 | {S1,S2,S3} | S4 | S5 |
Fold2 | {S2,S3,S4} | S5 | S1 |
Fold3 | {S3,S4,S5} | S1 | S2 |
Fold4 | {S4,S5,S1} | S2 | S3 |
Fold5 | {S5,S1,S2} | S3 | S4 |
ساختار كلي اطلاعات موجود در اين داده محك، در شکل شماره پنج، نشان داده شده است.
Label qid:queryID 1:F1Value 2:F2Value 3:F3Value … 55:F55Value 56:F56Value #docid = docID |
شکل 5: ساختار داده محك dotIR
(Darrudi et al. 2009)
4-2- شاخصهای ارزیابی
به منظور ارزيابي عملكرد الگوريتم MGP-Rank، از شاخصهاي مرجع در ارزیابی رتبهبندی یعنی ، ، و ، استفاده شده است.
· دقت21 در نقطه k (): اگر قضاوت انسانيِ اسناد، بهصورت دودويي در اختيار باشد، مثلاً برچسب اسناد مرتبط، يک و برچسب اسناد نامرتبط، صفر باشد، در این صورت، بهصورت زير تعريف ميشود [32]:
(1) |
|
(2) |
|
(3) |
|
که در آن، رتبه يک سند است که عموماً بهصورت ميباشد و يک ضريب کاهشي بر اساس موقعيت است که غالباً بهصورت تعريف ميشود. با هنجار سازي مقادير با يک مقدار بيشينه (مثلاً ) شاخص بهره انباشته کاهشی هنجار شده () حاصل ميگردد که عبارتست از:
(4) |
|
بديهي است که دامنه مقادير ممکن براي شاخص ، بين صفر و يک قرار ميگيرد.
· میانگین بهره انباشته کاهشی هنجار شده (): با میانگینگیری مقادیر در موقعیتهای مختلف ، شاخص میانگین بهره انباشته کاهشی هنجار شده، محاسبه میشود [32].
4-3- سناریوهای استخراج ویژگیهای کلیک از گذر داده
برای تولید ویژگیهای کلیک از گذر داده در الگوریتم MGP-Rank، بر اساس سناریوهای مندرج در جدول شماره سه، عمل میشود و نتایج برترین سناریوها در ادامه، گزارش خواهد شد.
[1] Loss Function
[2] Pointwise
[3] Pairwise
[4] Listwise
[5] Support Vector Machine (SVM)
[6] Direct optimization
[7] Deep Learning
[8] Benchmark Dataset
[9] Precision
[10] Accuracy
[11] Recall
[12] Specificity
[13] Crossover
[14] Mutation
[15] Reproduction
[16] Mutation Point
[17] Adaptive Mutation Rate Tuning
[18] Random Selection
[19] Tournament Selection
[20] Tournament Size
[21] Precision
[22] Mean Average Precision
[23] Average Precision
[24] Normalized Discounted Cumulative Gain
[25] Discounted Cumulative Gain
جدول 3: سناریوهای تولید ویژگیهای کلیک از گذر داده روی داده محک dotIR
شناسه سناریو | روش محاسبه | ||||||||||||
IR-DF1 |
| ||||||||||||
IR-DF2 |
| ||||||||||||
IR-DF3 |
| ||||||||||||
IR-DF4 |
| ||||||||||||
IR-DF5 |
| ||||||||||||
IR-DF6 |
| ||||||||||||
IR-DF7 |
|
ب- بازنمایی عبارت شماره دو بصورت درخت دودویی:
|
الف- بازنمایی عبارت شماره یک بصورت درخت دودویی:
|
|
|
ج- بازنمایی نتایج عملگر ترکیب بصورت درخت دودویی | |
د- بازنمایی نتیجه اِعمال عملگر جهش روی عبارت شماره یک بصورت درخت دودویی |
4-4- تنظیمات و پارامترهای آزمایشها
در این قسمت، نتایج حاصل از بررسیهای انجام شده مطابق سناریوهای مندرج در بخش 3-4، روی مجموعه داده dotIR ارایه میشود. تمامی آزمایشها روی یک رایانه با پردازنده دو هستهای 2.0GHz، شامل 2MB کاشه و 3GB حافظه، صورت پذیرفته است. در ارزیابی عملکرد الگوریتم MGP-Rank از چارچوب LAGEP با تنظیمات مندرج درError! Reference source not found.شماره چهار، استفاده شده است.
جدول 4: مشخصات چارچوب LAGEP در مطالعه الگوریتم MGP-Rank
پارامتر | مقدار |
تعداد لایهها | 3 |
نرخ بکارگیری عملگرهای ژنتیک | ادغام: 0.95، جهش: 0.05 |
احتمال بکارگیری عملگرهای ریاضی | احتمال مساوی برای {+, −, /, ×, Sin(.), Cos(.), Ln(.) and Exp(.)} |
احتمال بکارگیری ضرایب عددی ثابت | احتمال مساوی برای {0, 0.1, 0.2,.., 0.9, 1, π, e(=2.71828), π/2} |
احتمال بکارگیری انواع گرهها | متغیرها: 0.075، مقادیر ثابت: 0.025، عملگر ریاضی: 0.9 |
درصد رشد1 | 50 |
[1] Grow Percentage
چارچوب LAGEP مورد استفاده در این تحقیق، از سه لایه مجزا تشکیل یافته است که جزییات آنها در جدول شماره پنج آمده است. هر لایه، شامل تعدادی جمعیت است که در مقداردهی اولیه آنها از روش رشد1، استفاده شده است. در این روش، درختهای متناظر با افراد عضو جمعیتها، طی یک فرآیند بازگشتی، ایجاد میشوند، به نحوی که عمق درخت حاصله، از مقدار متغیر «عمق درخت»، بیشتر نباشد و حجم درخت نسبت به درخت کامل با همان عمق، از مقدار متغیر «درصد رشد»، تجاوز نکند. جمعیتهای حاصل از این فرآیند، توسط عملگرهای ژنتیکی با نرخ بکارگیری مشخص شده در جدول شماره چهار، تکامل مییابند. سپس از هر جمعیت، فردی با بیشترین میزان تابع برازش، برای بقا در نسل بعد، باقی خواهد ماند. این فرآیند در هر جمعیت تا رسیدن به تعداد مشخصی از نسلها، ادامه پیدا میکند.
[1] Grow Method
جدول5: مشخصات لایههای چارچوب LAGEP مورد استفاده
مشخصات لایه | لایه شماره یک | لایه شماره دو | لایه شماره سه |
تعداد جمعیتها | 1 | 2 | 3 |
تعداد افراد هر جمعیت | 100 | 100 | 10 |
تعداد نسلها | 50 | 10 | 10 |
اندازه مسابقه | 5 | 7 | 1 |
تعداد افراد باقی مانده از یک جمعیت در نسل بعدی | 1 | 1 | 1 |
عمق درخت | 4 | 6 | 4 |
هر فرد از یک جمعیت را میتوان بصورت یک ردهبندی کننده، در نظر گرفت و کارآیی آن در فرآیند ردهبندی را توسط یک ماتریس ابهام1 با چهار مقدار:True Positive
(TP)، True Negative (TN)، False Positive (FP) و False Negative (FN)، مندرج در جدول شماره شش، بیان نمود. |
جدول 6: بیان کارآیی فرد I در ردهبندی بر اساس مقادیر TP، FP، FN و TNا
| نمونه مثبت | نمونه منفی |
پاسخ I مثبت است | TP | FP |
پاسخ I منفی است | FN | TN |
در آزمایشهای انجام شده، از پنج تابع برازش مختلف و مرتبط با حوزه بازیابی اطلاعات، به شرح مندرج در جدول شماره هفت، به منظور ارزیابی کیفیت افراد جمعیتها، استفاده شده است.
جدول7: توابع سازگاری استفاده شده جهت تعیین سازگاری افراد جمعیت ا
شناسه تابع برازش | تابع برازش | روش محاسبه |
FF1 | Accuracy | (TP + TN) / |
FF2 | Precision | TP / (TP + FP) |
FF3 | Recall | TP / (TP + FN) |
FF4 | F-measure | 2 TP / (TP + FP + FN) |
FF5 | Specificity | TN / (TN + FP) |
همه نتایج گزارش شده در قسمتهای آتی، بر اساس بازه اطمینان 95% حاصل شدهاند. این نتایج، بر اساس میانگینگیری از 150 بار تکرار هر نسخه از الگوریتم MGP-Rank روی مجموعه داده dotIR حاصل شده است. دلیل این کار، ماهیت تصادفی مدل برنامهنویسی تکاملی است که در نتیجه آن، ممکن است خروجی هر بار اجرای الگوریتم، با دفعات دیگر، تفاوت داشته باشد. تنظیمات مورد استفاده در بهترین نسخههای مورد مطالعه عملکرد الگوریتم MGP-Rank در زبان فارسی، در جدول شماره هشت ارایه شده است.
جدول 8: مشخصات نسخههای مختلف الگوریتم MGP-Rank جهت ارزیابی روی مجموعه داده dotIRا
شناسه ساختار | شناسه سناریو | شناسه تابع برازش |
MGP.IR1 | IR-DF7 | FF4 |
MGP.IR2 | IR-DF4 | FF4 |
MGP.IR3 | IR-DF7 | FF1 |
MGP.IR4 | IR-DF6 | FF1 |
4- نتایج بدست آمده
در جدول شماره نه، نتایج حاصل از بررسی کیفیت بازیابی الگوریتم MGP-Rank بر اساس شاخص دقت روی مجموعه داده dotIR، گزارش شده است. لازم به ذکر است که مقایسه عملکرد الگوریتم MGP-Rank با روشهای مرجع رتبهبندی بر اساس شاخص دقت، مطابق نتایج درج شده در جدول شماره ده، انجام میشود. به منظور تعیین مبنایی جهت مقایسه عملکرد الگوریتم MGP-Rank نسبت به دیگر روشهای مرجع رتبهبندی، در این پژوهش، عملکرد سه الگوریتم پایه رتبهبندی، روی مجموعه دادگان dotIR، مورد بررسی قرار گرفته است و نتایج بدست آمده بر اساس شاخص دقت، در جدول شماره ده، گزارش شده است.
[1] Confusion Matrix
جدول 9: نتایج حاصل از ارزیابی الگوریتم MGP-Rank بر اساس شاخص دقت روی مجموعه داده dotIR
شناسه ساختار | P@1 | P@2 | P@3 | P@4 | P@5 | P@6 | P@7 | P@8 | P@9 | P@10 | MAP |
MGP.IR1 | 0.68 | 0.61 | 0.5867 | 0.57 | 0.588 | 0.5867 | 0.58 | 0.5775 | 0.5667 | 0.56 | 0.441 |
MGP.IR2 | 0.68 | 0.66 | 0.6667 | 0.65 | 0.628 | 0.62 | 0.6029 | 0.605 | 0.6067 | 0.602 | 0.4408 |
MGP.IR3 | 0.66 | 0.62 | 0.6 | 0.605 | 0.64 | 0.64 | 0.6314 | 0.6375 | 0.6222 | 0.618 | 0.4545 |
MGP.IR4 | 0.64 | 0.61 | 0.6 | 0.615 | 0.64 | 0.6333 | 0.6343 | 0.635 | 0.62 | 0.616 | 0.454 |
جدول10: نتایج ارزیابی روشهای استاندارد رتبهبندی طبق شاخص دقت روی مجموعه داده dotIR
الگوریتم | P@1 | P@2 |
|
| P@3 | P@4 | P@5 | P@6 | P@7 | P@8 | P@9 | P@10 | MAP |
PageRank | 0.12 | 0.12 |
|
| 0.1133 | 0.115 | 0.112 | 0.1067 | 0.1029 | 0.1 | 0.1111 | 0.112 | 0.1229 |
TF-IDF of Whole Doc | 0.36 | 0.38 |
|
| 0.3867 | 0.38 | 0.364 | 0.35 | 0.3343 | 0.3275 | 0.32 | 0.316 | 0.2479 |
HITS authority | 0.4 | 0.42 |
|
| 0.42 | 0.44 | 0.464 | 0.47 | 0.4971 | 0.4975 | 0.5044 | 0.512 | 0.4319 |
هفت، نمایش داده شده است.
|
مقایسه تصویری اطلاعات جدول شماره نه با نتایج عملکرد روشهای مرجع مندرج در جدول شماره ده، در شکل شماره
شکل7: مقایسه عملکرد الگوریتم MGP-Rank در زبان فارسی با روشهای مرجع رتبهبندی طبق شاخص دقت
MAP، نمایش داده شده است.
|
در شکل شماره هشت نیز مقایسه الگوریتم MGP-Rank با روشهای مـرجع رتبهبنـدی در زبان فارسـی طبق شـاخـص
شکل 8: مقایسه الگوریتم MGP-Rank با روشهای مرجع رتبهبندی در زبان فارسی طبق شاخص MAP
به همین ترتیب، بررسی عملکرد الگوریتم MGP-Rank روی داده dotIR بر اساس شاخص NDCG نیز انجام شده است که نتایج بدست آمده در جدول شماره یازده، ارایه شده است. ضمن آنکه نتایج بدست آمده به ازای روشهای رتبهبندی مرجع روی دادگان dotIR بر اساس شاخص NDCG، در جدول شماره دوازده، گزارش شده است.
جدول 11: نتایج ارزیابی نسخههای الگوریتم MGP-Rank طبق شاخص NDCG روی مجموعه داده dotIR
NDCG | NDCG | NDCG @3 | NDCG @4 | NDCG @5 | NDCG @6 | NDCG @7 | NDCG @8 | NDCG @9 | NDCG @10 | Mean NDCG | |
MGP.IR1 | 0.68 | 0.61 | 0.5932 | 0.5815 | 0.591 | 0.5899 | 0.5858 | 0.5839 | 0.5773 | 0.5729 | 0.7051 |
MGP.IR2 | 0.66 | 0.62 | 0.6056 | 0.6079 | 0.6287 | 0.6298 | 0.6257 | 0.6296 | 0.6213 | 0.619 | 0.7184 |
MGP.IR3 | 0.68 | 0.66 | 0.6648 | 0.6544 | 0.6406 | 0.6347 | 0.6235 | 0.6233 | 0.6231 | 0.6195 | 0.7173 |
MGP.IR4 | 0.64 | 0.61 | 0.6028 | 0.6119 | 0.6274 | 0.6247 | 0.626 | 0.627 | 0.6189 | 0.6167 | 0.718 |
جدول 12: نتایج ارزیابی روشهای استاندارد رتبهبندی بر اساس شاخص NDCG روی مجموعه داده dotIR
الگوریتم | NDCG | NDCG | NDCG @3 | NDCG @4 | NDCG @5 | NDCG @6 | NDCG @7 | NDCG @8 | NDCG @9 | NDCG @10 | Mean NDCG |
PageRank | 0.12 | 0.12 | 0.1152 | 0.116 | 0.114 | 0.1107 | 0.1081 | 0.1061 | 0.1121 | 0.1126 | 0.3259 |
TF-IDF of Whole Doc | 0.36 | 0.38 | 0.384 | 0.381 | 0.3711 | 0.3621 | 0.352 | 0.3468 | 0.3413 | 0.3378 | 0.5137 |
HITS authority | 0.4 | 0.42 | 0.42 | 0.4328 | 0.4482 | 0.4532 | 0.4703 | 0.4725 | 0.478 | 0.4839 | 0.6861 |
مقایسه نتایج جدول فوق با عملکرد روشهای مرجع رتبهبندی در شکل شماره نه، انجام شده است که در آن از اطلاعات مربوط به روشهای مرجع مندرج در جدول شماره دوازده، استفاده شده است.
شکل 9: مقایسه عملکرد الگوریتم MGP-Rank در زبان فارسی با روشهای مرجع رتبهبندی طبق شاخص NDCG
در شکل شماره ده نیز مقایسه الگوریتم MGP-Rank با روشهای مرجع رتبهبندی در زبان فارسی طبق شاخص MeanNDCG، نمایش داده شده است.
شکل 10: مقایسه الگوریتم MGP-Rank با روشهای مرجع رتبهبندی در زبان فارسی طبق شاخص MeanNDCG
تحلیل نتایج
در این بخش، عملکرد الگوریتم یادگیری رتبهبندی MGP-Rank، در زبان فارسی، بر اساس شاخصهای ارزیابی چهارگانه P@n، MAP، NDCG@n و MeanNDCG، روی مجموعه داده محک dotIR مورد بررسی قرار گرفت. یافتههای حاصل از نتایج از این ارزیابیها، بطور خلاصه، بشرح زیر است:
· در شاخص دقت نقطهای (P@n)، عملکرد الگوریتم MGP-Rank، کاملاً برتر از روشهای روشهای مرجع رتبهبندی میباشد. به عنوان مثال، الگوریتم MGP-Rank، در شاخص P@1، بهبودی معادل 70% در مقایسه با برترین روش مرجع رتبهبندی، یعنی HITS authority داشته است. به همین ترتیب، در شاخص P@2، نیز افزایش دقتی به ترتیب معادل 70% نسبت به بهترین روش مرجع رتبهبندی، بدست آمده است.
· در شاخص متوسط میانگین دقت (MAP)، عملکرد الگوریتم MGP-Rank، از روشهای مرجع رتبهبندی بهتر بوده است. در این خصوص، الگوریتم فوق، افزایش دقتی معادل 2.05% نسبت به برترین روش مرجع یعنی HITS authority داشته است.
· در شاخص NDCG@n، نیز عملکرد الگوریتم MGP-Rank، به طرز چشمگیری بهتر از روشهای مرجع بوده است. به عنوان نمونه، به ازای شاخص NDCG@1، این الگوریتم، بهبود عملکردی معادل 65% نسبت به بهترین روش مرجع رتبهبندی، یعنی HITS authority، کسب نموده است.
· در شاخص MeanNDCG نیز روش مورد بحث، موفقتر از روشهای مرجع رتبهبندی ظاهر شدهاست. در این زمینه، الگوریتم MGP-Rank، حدود 4.71% نسبت به بهترین روش مرجع رتبهبندی، یعنی HITS authority، بهبود عملکرد نشان داده است.
یک نکته جالب توجه در بررسی عملکرد الگوریتم MGP-Rank روی مجموعه داده dotIR، این است که استفاده از شاخص متوسط میانگین دقت (MAP) در اولویتبندی ویژگیها برای ادغام آنها بکمک عملگرهای میانگینگیری مرتب وزندار، مناسبتر از دیگر شاخصها بوده است. همچنین بر اساس آمار فوق، میتوان به این نکته نیز اشاره نمود که الگوریتم یادگیری رتبهبندی MGP-Rank در زبان فارسی نیز همانند زبان انگلیسی، موفق بوده است. مساله شایان توجه دیگر این است که در زبان فارسی نیز بهترین عملکرد این الگوریتم، مربوط به بخش آغازین فهرست نتایج بوده است که همانطور که پیشتر نیز ذکر شد، بیشترین میزان توجه کاربران جویشگرهای وب را به خود، معطوف میسازد. این عملکرد مناسب الگوریتم MGP-Rank در زبان فارسی، با بکارگیری خصوصیاتی مشابهی همچون TF-IDF، BM25، PageRank، HITS، طول سند و نیز خصوصیات مرتبط با مدلهای زبانی، محقق شده است.
5- جمعبندی و پیشنهاد پژوهشهای بعدی
با توجه به نقش تعیین کننده جویشگرهای وب در دسترسی کاربران به اطلاعات و خدمات مورد نیاز، فرآیند رتبهبندی در این خصوص، بسیار تاثیر گذار است. با عنایت به کاربر- محور بودن فرآیند رتبهبندی نتایج جستجو، بکارگیری اطلاعات مربوط به سوابق رفتار کاربران جویشگرهای وب در حین جستجوی اطلاعات مورد نیاز که اصطلاحاً اطلاعات کلیک از گذر داده نامیده میشود، در بهبود عملکرد جویشگرها بسیار مفید میباشد. با این وجود، ارایه و در نتيجه، استفاده از اين قبيل اطلاعات، در اغلب مجموعههای داده محک موجود برای یادگیری رتبهبندی و به تبع آن، در اکثر روشهای مطرح شده در این زمینه، مغفول مانده است. همچنین، تعدد ویژگیهای ارایه شده در این مجموعههای داده، ضمن تحمیل هزینههای محاسباتی قابل توجه به روشهای رتبهبندی مطرح شده، کاربرد آنها را در شرایط واقعی، دشوار میکند.
به منظور پرداختن به این چالشها، در تحقيقات صورت گرفته، رويكرد نوينی برای حل مساله ایجاد یادگیری رتبهبندی، ارایه شده است [23] که طی آن، با نگاه مفهومی به اطلاعات کلیک از گذر داده [21]، از ویژگیهای موجود در مجموعههای داده محک مربوط به یادگیری رتبهبندی، تعداد معدودی ویژگیهای ثانویه موسوم به «ویژگیهای کلیک از گذر داده» تولید میشود. این ویژگیها دارای غنای اطلاعاتی مناسب، به منظور ایجاد روشهای رتبهبندی جدید، میباشند. در فرآیند تولید ویژگیهای کلیک از گذر داده، از مدل مفهومی اطلاعات کلیک از گذر داده، الگو برداری شده است. این ویژگیها که تعداد آنها، هشت عدد میباشد، در سه دسته ویژگیهای مرتبط با پرسوجوهای کاربران، ویژگیهای در رابطه با نتایج جستجوها و نیز ویژگیهای وابسته به الگوهای کلیک کاربران در حین بررسی نتایج، دستهبندی میشوند. در تحقیقات پیشین، به منظور محاسبه این ویژگیها از اطلاعات موجود در مجموعههای داده محک مورد استفاده، تعدادی سناریوی محاسبه، پیشنهاد و بررسی شده است که عمدتاً محدود به اطلاعات و محتوای انگلیسی وب بوده است. به منظور بکارگیری این ایده در زبان فارسی، در این پژوهش، با عنایت به ویژگیهای زبان فارسی، سناریوهای مناسبی برای تولید ویژگیهای کلیک از گذر داده، شناسایی شده است. سپس با بکارگیری نیز مدل برنامهنویسی ژنتیک چند لایه، روی ویژگیهای کلیک از گذر داده، از الگوریتم MGP-Rank، استفاده شده است [23]. بطور مشخص، در این الگوریتم، از قابلیت جستجوی فراگیر مدل برنامهنویسی ژنتیک چند لایه و چند جمعیتی، برای یافتن توابع رتبهبندی مناسب اسناد از طریق ادغام ویژگیهای کلیک از گذر داده، بهره گرفته میشود. با توجه به گزارش موفقیت قابل توجه این الگوریتم در رتبهبندی اطلاعات انگلیسی وب، در این مقاله تلاش شده است با پیشنهاد سناریوهای مناسب جهت استخراج ویژگیهای کلیک از گذر داده روی دادگان فارسی وب، توانمندی آن در زبان فارسی نیز بکار گرفته شود. ارزیابی عملکرد این الگوریتم در بازیابی اطلاعات فارسی وب، نشاندهنده افزایش دقت قابل توجه این الگوریتم، نسبت به الگوریتمهای پایه رتبهبندی میباشد. این بهبود عملکرد بخصوص در بخش آغازین فهرست نتایج جستجو که بیشتر مورد توجه کاربران است، قابل ملاحظهتر بوده است.
این پژوهش از جنبههای مختلفی قابل توسعه است. بصورت خاص، به منظور انجام تحقیقات جامعتر پیرامون MGP-Rank، ارایه یک مدل استاندارد و خودکار جهت تولید و سنجش عملکرد سناریوهای محاسبه ویژگیهای کلیک از گذر داده، بر اساس ساختار و مشخصات و نیز ویژگیهای عرضه شده در مجموعههای داده محک پایه مورد استفاده، حائز اهمیت است. در عین حال، بکارگیری روشهاي مختلف تركيب اطلاعات در سناريوهاي محاسبه ويژگيهاي مبتني بر اطلاعات كليك از گذر داده، میتواند منجر به افزایش توانمندی این الگوریتم گردد. همچنین با عنایت به این نکته که در فرآیند یادگیری رتبهبندی، تولید مدل رتبهبندی بر مبنای قضاوت کاربران، صورت میگیرد و این قضاوتهای میتواند همراه با ابهام و نایقینی باشد، لذا بررسي روشهاي مواجهه با نايقيني و ابهام ذاتي موجود در قضاوتهاي انساني، در راستای بهبود عملکرد این الگوریتمها، حائز اهمیت خواهد بود. علاوه بر آن، بكارگيري انواع ديگر توابع سازگاري مرتبط با حوزه بازيابي اطلاعات، بخصوص توابع مرتبط با شاخص NDCG، ميتواند جالب توجه باشد.
پیوستها
پیوست 1: فهرست ويژگيهاي موجود در مجموعه داده محك dotIR (Darrudi et al. 2009)
شناسه ويژگي | نام ويژگي | نوع ويژگي |
F1 | Term frequency (TF) of body | مبتني بر محتوا |
F2 | TF of anchor | |
F3 | TF of title | |
F4 | TF of URL | |
F5 | TF of whole document | |
F6 | Inverse document frequency (IDF) of body | |
F7 | IDF of anchor | |
F8 | IDF of title | |
F9 | IDF of URL | |
F10 | IDF of whole document | |
F11 | TF×IDF of body | |
F12 | TF×IDF of anchor | |
F13 | TF×IDF of title | |
F14 | TF×IDF of URL | |
F15 | TF×IDF of whole document | |
F16 | Document length (DL) of body | |
F17 | DL of anchor | |
F18 | DL of title | |
F19 | DL of URL | |
F20 | DL of whole document | |
F21 | BM25 of body | |
F22 | BM25 of anchor | |
F23 | BM25 of title | |
F24 | BM25 of URL | |
F25 | BM25 of whole document | |
F26 | LMIR.ABS of body | |
F27 | LMIR.ABS of anchor | |
F28 | LMIR.ABS of title | |
F29 | LMIR.ABS of URL | |
F30 | LMIR.ABS of whole document | |
F31 | LMIR.DIR of body | |
F32 | LMIR.DIR of anchor | |
F33 | LMIR.DIR of title | |
F34 | LMIR.DIR of URL | |
F35 | LMIR.DIR of whole document | |
F36 | LMIR.JM of body | |
F37 | LMIR.JM of anchor | |
F38 | LMIR.JM of title | |
F39 | LMIR.JM of URL | |
F40 | LMIR.JM of whole document | |
F41 | Sitemap based term propagation | تركيب محتوا و پيوند |
F42 | Sitemap based score propagation | |
F43 | Hyperlink base score propagation weighted in-link | |
F44 | Hyperlink base score propagation weighted out-link | |
F45 | Hyperlink base score propagation uniform out-link | |
F46 | Hyperlink base feature propagation weighted in-link | |
F47 | Hyperlink base feature propagation weighted out-link | |
F48 | Hyperlink base feature propagation uniform out-link | |
F49 | HITS authority | مبتني بر پيوند |
F50 | HITS hub | |
F51 | PageRank | |
F52 | In-link number | |
F53 | Out-link number | |
F54 | Number of slash in URL | |
F55 | Length of URL | |
F56 | Number of child page |
منابع
1. Q. Ai, K. Bi, J. Guo, W.B. Croft Croft, “Learning a Deep Listwise Context Model for Ranking Refinement”, In Proceedings of the 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, pp. 135-144, 2018.
2. Q. Ai, X. Wang, S. Bruch, N. Golbandi, M. Bendersky, and M. Najork, “Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks”, In Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 85-92, 2019.
3. C.C. Alves, M.A. Gonçalves, D. Sousa, and T. Salles, “Generalized BROOF-L2R: A General Framework for Learning to Rank Based on Boosting and Random Forests”, In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pp. 95-104, 2016.
4. Z. Cao, T. Qin, T.Y. Liu, M.F. Tsai, and H. Li, “Learning to rank: from pairwise approach to listwise approach”, In Proceedings of the 24th International Conference on Machine Learning, pp. 129-136, 2007.
5. S. Chakrabarti, R. Khanna, U. Sawant, and C. Bhattacharyya, “Structured learning for nonsmooth ranking losses”, In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 88-96, 2008.
6. O. Chapelle & Y. Chang, “Yahoo! Learning to Rank Challenge Overview”, Journal of Machine Learning Research, pp. 14, 1-24, 2011.
7. O. Chapelle & M. Wu, “Gradient descent optimization of smoothed information retrieval metrics”, Information Retrieval, Vol. 13, No. 3, pp. 216-235, 2010.
8. W. Chu & Z. Ghahramani, “Preference learning with Gaussian processes”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 137-144, 2005.
9. W. Chu & S.S. Keerthi, “New approaches to support vector ordinal regression”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 145-152, 2005.
10. D. Cossock & T. Zhang, “Subset ranking using regression”, In Proceedings of the 19th annual conference on Learning Theory, pp. 605-619, 2006.
11. F. Dammak, H. Kammoun, and A.B. Hamadou, “Improving pairwise learning to rank algorithms for document retrieval”, In of IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1-8, 2017.
12. E. Darrudi, H.B. Hashemi, A. Aleahmad, A. Habibian, A. ZarehBidoki, A. Shakery, and M. Rahgozar, “A standard web test collection for IR domain”, Technical Reoprt, Iran Telecommunication Research Center, 2009.
13. W. Fan, M.D. Gordon, and P. Pathak, “Ranking function optimization for effective web search by genetic programming: an empirical study”, In Proceedings of the 37th Hawaii International Conference on System Sciences, pp. 1-8, 2004.
14. W. Fan, M.D. Gordon, and P. Pathak, “On linear mixture of expert approaches to information retrieval”, Decision Support System, Vol. 42, No. 2, pp. 975-987, 2006.
15. N. Fuhr, “Optimum polynomial retrieval functions based on the probability ranking principle”, ACM Transactions on Information Systems, 183-204, 1989.
16. J. Gao, H. Qi, X. Xia, and J.Y. Nie, “Linear discriminant model for information retrieval”, In Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 290-297, 2005.
17. Z. Hu, Y. Wang, Q. Peng, and H. Li, “Unbiased LambdaMART: An Unbiased Pairwise Learning-to-Rank Algorithm”, In Proceedings of the World Wide Web Conference, pp. 2830-2836, 2019.
18. K. Järvelin & J. Kekäläinen, “IR evaluation methods for retrieving highly relevant documents”, In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 41-48, 2000.
19. K. Järvelin & J. Kekäläinen, “Cumulated gain-based evaluation of IR techniques”, ACM Transactions on Information Systems, Vol. 20, No. 4, pp. 422-446, 2002.
20. X.B. Jin, G.G. Geng, G.S. Xie, and K. Huang, “Approximately optimizing NDCG using pair-wise loss”, Information Sciences, Vol. 453, pp. 50-65, 2018.
21. T. Joachims, “Optimizing search engines using clickthrough data”, In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 133-142, 2002.
22. T. Joachims, L.A. Granka, B. Pan, H.A. Hembrooke, and G .Gay, “Accurately Interpreting Clickthrough Data as Implicit Feedback”, In Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 154-161, 2005.
23. A.H. Keyhanipour, B. Moshiri, F. Oroumchian, M. Rahgozar, and K. Badie, “Learning to rank: new approach with the layered multi-population genetic programming on click-through features”, Genetic Programming and Evolvable Machines, Vol. 17, pp. 203-230, 2016.
24. M. Köppel, A. Segner, M. Wagener, L. Pensel, A. Karwath, and S. Kramer, “Pairwise Learning to Rank by Neural Networks Revisited: Reconstruction, Theoretical Analysis and Practical Performance”, arXiv:1909.02768v1, 2019.
25. P. Li, Q. Wu, and C.J. Burges, “McRank: Learning to rank using multiple classification and gradient boosting”, Advances in Neural Information Processing Systems 20, pp. 845-852, 2008.
26. J.Y. Lin, H.R. Ke, B.C. Chien, and W.P. Yang, “Classifier design with feature selection and feature extraction using layered genetic programming”, Expert Systems with Applications, Vol. 34, 1384-1393, 2008.
27. Y. Lin, J. Wu, B. Xu, K. Xu, and H. Lin, “Learning to rank using multiple loss functions”, International Journal of Machine Learning and Cybernetics, Vol. 10, pp. 485-494, 2019.
28. T.Y. Liu, Learning to Rank for Information Retrieval, Berlin: Springer-Verlag, 2011.
29. H. Liu, Z. Wu, X. Zhang, “CPLR: Collaborative pairwise learning to rank for personalized recommendation, Knowledge-Based Systems”, Vol. 148, pp. 31-40, 2018.
30. C. Macdonald, I. Ounis, “Usefulness of Quality Click-through Data for Training”, In Proceedings of the 2009 workshop on Web Search Click Data, pp. 75-79, 2009.
31. C. Macdonald, R.L. Santos, I. Ounis, “On the Usefulness of Query Features for Learning to Rank”, In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 2559-2562, 2012.
32. C.D. Manning, P. Raghavan, and H. Schütze, An Introduction to Information Retrieval, Cambridge University Press, 2008.
33. R. Nallapati, “Discriminative models for information retrieval”, In Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 64-71, 2004.
34. L. Pang, J. Xu, Q. Ai, Y. Lan, X. Cheng, and J. Wen, “SetRank: Learning a Permutation-Invariant Ranking Model for Information Retrieval”, arXiv:1912.05891v1, 2019.
35. T. Qin, T.Y. Liu, J. Xu, and H. Li, “LETOR: Benchmark dataset for research on learning to rank for information retrieval”, In Proceedings of the LR4IR 2007, in conjunction with SIGIR 2007, pp. 3-10, 2007.
36. T. Qin, T.Y. Liu, and H. Li, “A general approximation framework for direct optimization of information retrieval measures”, Information Retrieval, Vol. 13, No. 4, pp. 375-397, 2009.
37. R. Rahimi, A. Montazeralghaem, and J. Allan, “Listwise Neural Ranking Models”, In Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval, pp. 101-104, 2019.
38. E. Renshaw, A. Lazier, C. Burges, T. Shaked, M. Deeds, N. Hamilton, and G. Hullender, “Learning to rank using gradient descent”, In Proceedings of the 22nd International Conference on Machine Learning, pp. 89-96, 2005.
39. S. Tan, Z. Zhou, and P. Li, “Fast Item Ranking under Neural Network based Measures”, In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 591-599, 2020.
40. M. Taylor, J. Guiver, S. Robertson, and T. Minka, “Softrank: optimising non-smooth rank metrics”, In Proceedings of the 1st International Conference on Web Search and Web Data Mining, pp. 77-86, 2008.
41. A. Trotman, “Learning to rank”, Information Retrieval, Vol. 8, No. 3, pp. 359-381, 2005.
42. M.F. Tsai, T.Y. Liu, T. Qin, H.H. Chen, and W.Y. Ma, “Frank: a ranking method with fidelity loss”, In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 383-390, 2007.
43. M.N. Volkovs & R.S. Zemel, “Boltzrank: learning to maximize expected ranking gain”, In Proceedings of the 26th International Conference on Machine Learning, pp. 1089-1096, 2009.
44. J. Wang, L. Yu, W. Zhang, Y. Gong, Y. Xu, and B. Wang, “IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models”, In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 515-524, 2017.
45. T. Xia, S. Zhai, and S. Wang, “Analysis of Regression Tree Fitting Algorithms in Learning to Rank”, arXiv:1909.05965v1, 2019.
46. J. Xu, T.Y. Liu, M. Lu, H. Li, and W.Y. Ma, “Directly optimizing IR evaluation measures in learning to rank”, In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 107-114, 2008.
47. Q. Xu, M. Li, and M. Yu, “Learning to rank with relational graph and pointwise constraint for cross-modal retrieval”, Soft Computing, Vol. 23, pp. 9413-9427, 2019.
48. J.Y. Yeh, J.Y. Lin, H.R. Ke, and W.P. Yang, “Learning to Rank for Information Retrieval Using Genetic Programming”, In Proceedings of the SIGIR 2007 Workshop on Learning to Rank for Information Retrieval, pp. 1-8, 2007.
49. J.Y. Yeh, J.Y. Lin, H.R. Ke, and W.P. Yang, “Learning to Rank for Information Retrieval Using Layered Multi-Population Genetic Programming”, In Proceedings of the 2012 IEEE International Conference on Computational Intelligence and Cybernetics, pp. 45-49, 2012.
50. Y. Yue, T. Finley, F. Radlinski and T. Joachims, “A support vector method for optimizing average precision”, In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 271-278, 2007.
51. Z. Zheng, H. Zha, and G. Sun, “Query-level learning to rank using isotonic regression”, In Proceedings of the SIGIR 2008 Workshop on Learning to Rank for Information Retrieval, pp. 9-14, 2008.
52. W. Zhou, J. Li, Y. Zhou, M.H. Momen, “Bayesian pairwise learning to rank via one-class collaborative filtering”, Neurocomputing, Vol. 367, pp. 176-187, 2019.
53. X. Zhu & D. Klabjan, “Listwise Learning to Rank by Exploring Unique Ratings”, In Proceedings of the 13th
International Conference on Web Search and Data Mining, pp. 798-806, 2020.
54. O. Zoeter, M. Taylor, E. Snelson, J. Guiver, N. Craswell, N., and M. Szummer, “A decision theoretic framework for ranking using implicit feedback”, In Proceedings of the SIGIR 2008 Workshop on Learning to Rank for Information Retrieval, pp. 24-31, 2008.
|
|