Manuscript ID : 202006218179 Visit : 12683 Page: 45 - 70

Article Type: Original Research

Learning to Rank for the Persian Web Using the Layered Genetic Programming

Subject Areas : General

1 - University of Tehran

Received: 2020-03-05 Accepted : 2020-03-05 Published : 2020-06-21

Keywords: Learning to Rank, Layered Genetic Programming, Click-through Features, Persian Web Content, dotIR dataset.,

Abstract :

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.

References:

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.

Full-Text:

فصلنامة علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال دهم، شمارههای 37 و 38، پاییز و زمستان 1397

صص: 45- 70

$E:\E Drive\logo\iicta Logo0.JPG$

یادگیری رتبه‏بندی محتوای فارسی وب بر مبنای برنامه‏نویسی ژنتیک چند لایه

امیر حسین کیهانی پور

استادیار، گروه مهندسی کامپیوتر، دانشکده مهندسی، پردیس فارابی، دانشگاه تهران

تاریخ دریافت:15/12/1398 تاریخ پذیرش: 21/03/1399

چكيده

یادگیری رتبه‏بندی، یک رویکرد نو ظهور به منظور رفع چالش‏های موجود و بهبود عملکرد جویشگرهای وب، بسیار امید بخش و کارآمد است. در عین حال عدم توجه جدی به سوابق تعاملات کاربران با جویشگر طی فرآیند جستجو و ارزیابی نتایج بدست آمده، یکی از معضلات جدی آن بشمار می‏رود. در عین حال حجم بسیار زیاد ویژگی‏های مورد نیاز از اسناد و پرس‏وجوهای کاربران نیز کاربردی بودن این رویکرد را در شرایط واقعی با ابهام مواجه ساخته است. استفاده از مدل اطلاعات کلیک از گذر داده‏ها و تولید ویژگی‏های کلیک از گذر داده، راهکار نوینی است که بر مبنای آن و با بکارگیری مدل برنامه‏نویسی ژنتیک چند لایه، مدل رتبه‏بندی مناسبی تحت عنوان MGP-Rank برای بازیابی اطلاعات انگلیسی وب، عرضه شده است. در این پژوهش این، با عنایت به ویژگی‏های خاص زبان فارسی، از طریق ارائه سناریوهای مناسب برای ایجاد ویژگی‏های کلیک از گذر داده این الگوریتم، این الگوریتم بومی‏سازی شده است. نتایج حاصل از ارزیابی عملکرد این الگوریتم در حوزه زبان فارسی با استفاده از مجموعه داده dotIR، حاکی از توانمندی قابل ملاحظه آن نسبت به روش‏های مرجع رتبه‏بندی اطلاعات است. این بهبود عملکرد، بخصوص در بخش ابتدایی فهرست نتایج جستجو که غالباً بیشتر مورد مراجعه کاربران است، قابل توجه است.

واژههای كليدي: یادگیری رتبه‏بندی، مدل برنامه‏نویسی ژنتیک چند لایه، ویژگی‏های کلیک از گذر داده، محتوای فارسی وب، مجموعه داده dotIR

1- مقدمه

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

جویشگرها، پیشینه قابل توجهی دارد، ولی در سال‏های اخیر با کاربرد گسترده‌تر این سامانه‌ها توسط کاربران، حجم قابل

نویسندۀ عهدهدار مکاتبات: امیر حسین کیهانی پور keyhanipour@ut.ac.ir

توجهی از اطلاعات مربوط به سوابق تعاملات کاربران با این سامانه‌ها، گردآوری شده است و این امر، امکان استفاده از الگوریتم‌های يادگيري ماشيني را براي ايجاد مدل‌هاي رتبـه‌بندي کارآمـد، فـراهـم نمـوده اسـت. بطور مشـخـص،

یادگیری رتبه‏بندی، به مجموعه روش‏های یادگیری ماشینی اطلاق می‏شود كه در عمليات رتبه‌بندي، به انجام يادگيري و تشخیص مدل مناسب جهت رتبه‌بندی اطلاعات، مي‌پردازند [28]. یادگیری رتبه‌بندی، كاربردهاي متعددي در زمینه بازيابي اطلاعات¹، پردازش زبان طبيعي² و نیز داده‌كاوي³ دارد. در تحقیقات انجام شده در این خصوص، به این نکته توجه شده است که کاربران جویشگرها که بطور مستقیم با این سامانه‌ها درگیر هستند، قادر به ارایه بهترین قضاوت‌ها در مورد کیفیت عملکرد این سامانه‌ها می‌باشند. با این‌ وجود، عدم تمایل اکثریت کاربران به ارایه قضاوت صریح از عملکرد جویشگرهای مورد استفاده، طراحان این سامانه‌ها را بر آن داشته است تا از سوابق تعاملات کاربران طی جستجوهای بعمل آمده، که اصطلاحاً «اطلاعات کلیک از گذر داده⁴»، نامیده می‌شود، به منظور بررسی و بهبود عملکرد این سامانه‌ها بهره گیرند [21]. مطالعات انجام شده، نشان می‌دهد که استفاده از اطلاعات کلیک از گذر داده، می‌تواند منجر به بهبود عملکرد جویشگرهای وب،
شود [30] و [22] و [31]. علیرغم این موضوع، فقدان اطلاعات کلیک از گذر داده در اغلب مجموعه‌های داده محک موجود در زمینه یادگیری رتبه‌بندی، موجب شده است تا اکثر الگوریتم‌های ارایه شده در این حوزه، از این اطلاعات ارزشمند، بی‌بهره باشند. در عین حال، استفاده اغلب روش‌های موجود از تعداد زیادی از ویژگی‌های اسناد و پرس‌وجوها، کاربرد آنها را در شرایط واقعی، دشوار می‌سازد.

در ادامه این نوشتار، ابتدا به مرور تحقیقات مرتبط پرداخته خواهد شد و بصورت تحلیلی، ضرورت انجام این پژوهش، مطرح خواهد شد. پس از آن، معرفی الگوریتم‏
MGP-Rank صورت خواهد گرفت و نحوه عملکرد آن بیان خواهد شد. سپس نتایج حاصل از ارزیابی عملکرد الگوریتم یادگیری رتبه‏بندی MGP-Rank در مقایسه با روش‏های رتبه‏بندی مرجع، بر اساس شاخص‏های ارزیابی فرآیند بازیابی اطلاعات، بصورت تحلیل مورد قیاس قرار خواهد گرفت. بخش پایانی این نوشتار نیز به جمع‏بندی این پژوهش و نیز معرفی حوزه‏های تحقیقاتی آتی، اختصاص یافته است.

2- مرور تحقیقات مرتبط

با توجه به نقش محوري رتبه‌بندي نتایج حاصل از جستجو در جویشگرهای وب، در سالهای گذشته تحقيقات گسترده‏ای در این در اين زمينه صورت پذيرفته است. بصورت ویژه طی سالیان اخير، موضوع يادگيري رتبه‌بندي، به عنوان يک روش نوين براي انجام رتبه‌بندي با استفاده از تکنيک‌هاي يادگيري ماشيني، مطرح شده است و در واقع، يادگيري رتبه‌بندي، به ‌صورت ترکيبي از يادگيري ماشيني، بازيابي اطلاعات و نیز پردازش زبان طبيعي قابل توصيف است. بطور کلي، دو تعريف عمده براي مفهوم يادگيري رتبه‌بندي، ارائه شده است. در نگرش کلان، يادگيري رتبه‌بندي به هر نوع کاربرد تکنيک‌هاي يادگيري ماشيني در مساله رتبه‌بندي، اطلاق مي‌شود. در مقابل و در يک نگرش جزيي‌تر، يادگيري رتبه‌بندي به آن دسته از روش‌هاي يادگيري ماشيني اشاره دارد که براي ايجاد مدل‌هاي رتبه‌بندي در مسايل «ايجاد رتبه‌بندي⁵» و «تجميع رتبه‌بندي⁶»، مورد استفاده قرار مي‌گيرند. در [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)

بر این اساس، يک الگوريتم يادگيري به منظور توليد مدل رتبه‌بندي، استفاده مي‌شود، به نحوي که اين مدل، قادر باشد با توجه به تابع زيان¹ مورد استفاده، ميزان مرتبط بودن اسناد به پرس‌وجوها را با دقت بالا و حتي‌المقدور مشابه قضاوت‌هاي انساني، پيش‌بيني نمايد. در خلال فاز آزمون و با دريافت يک پرس‌وجوي جديد، مدل توليد شده طي فاز آموزش، روي مجموعه اسناد مورد نظر، اِعمال مي‌شود تا فهرست رتبه‌بندي شده از آن اسناد، ايجاد شود. بر اساس اين رويکرد، روش‌هاي يادگيري رتبه‌بندي را مي‌توان به روش‌هاي نقطه‌اي²، روش‌هاي جفتي³ و نيز روش‌هاي مبتني بر فهرست⁴، دسته‌بندي نمود. هر دسته از اين روش‌ها، فرآيند يادگيري رتبه‌بندي را به اَشکال مختلف، مدل‌سازي مي‌کنند. به ‌عبارت ديگر، هر کدام از اين انواع روش‌ها، تعاريف متفاوتي از فضاهاي ورودي و خروجي بيان مي‌کنند يا ممکن است از فرضيه‌هاي متفاوتي استفاده کنند و نيز توابع زيان متفاوتي را بکار گيرند.

بطور کلی، روش‌هاي نقطه‌اي، وابستگي بين اسناد را در نظر نمي‌گيرند و بنابراين موقعيت يک سند در ليست مرتب نهايي، در محاسبات، لحاظ نمي‌شود. فضاي ورودي در روش‌هاي جفتي، زوج‌هاي اسناد مي‌باشد که به‌صورت بردارهاي ويژگي‌ها، نمايش داده مي‌شوند. فضاي خروجي نيز شامل اولويت‌ بين این زوج‌های اسناد است که دامنه مقادير آن از مجموعه مي‌باشد. در برخی از روش‏های ارائه شده در این دسته، رتبه‏بندی به مساله رگرسيون، تقليل مي‌يابد
[10] و [15] و [45]. یک رویکرد دیگر، مدل‏سازی مساله رتبه‏بندی بصورت یک مساله رده‏بندی است. در تحقيقات مختلف، امکان استفاده از مدل رده‌بندي براي مساله رتبه‌بندي در حوزه بازيابي اطلاعات، بررسی شده است که از جمله آنها مي‌توان به [33] و [44] و [27]. اشاره نمود. در این پژوهش‏ها، ایده تبدیل رتبه‏بندی به مساله رده‌بندي دودويي مطرح شده است. در تحقیقات دیگری نظیر [25] و [3]. بکارگیری رده‌بندي چند کلاسه براي حل مساله رتبه‌بندي، پیشنهاد شده است. بکارگیری مدل رگرسيون ترتيبي، در دسته سوم روش‏های نقطه‏ای، دنبال شده است که به عنوان نمونه مي‌توان به [8] و [9] اشاره نمود. با توجه به اينکه اغلب شاخص‌هاي ارزيابي در حوزه بازيابي اطلاعات مبتني بر موقعيت اسناد و در سطح پرس‌وجوها محاسبه مي‌شوند، روش‌هاي نقطه‌اي در شرایط واقعی، دچار محدوديت‌هاي جدي هستند.

فضاي فرضيه در روش‌هاي جفتي یادگیری رتبه‌بندی، شامل توابع دو متغيره‌اي است که يک جفت سند را به عنوان ورودي، دريافت مي‌کنند و ترتيب نسبي آن دو را در قالب خروجي، ارائه مي‌دهند. ضمناً تابع زيان مورد استفاده در روش‌هاي جفتي، صرفاً ترتيب نسبي بين زوج‌هاي اسناد را در نظر مي‌گيرد. در نتيجه، موقعيت نهايي اسناد در فهرست مرتب نهايي، به سختي قابل استحصال خواهد بود. از جمله ایده‏های مطرح شده در روش‏های جفتی رتبه بندی یادگیری، می‏توان به استفاده از شبکه‌هاي عصبي مصنوعی [38] و [16] و [52] و [24]. استفاده از مدل ماشین بردار پشتیبان⁵ [21] و [17]. و نيز بکارگیری الگوریتم‏های يادگيري ماشيني [4] و [51] و [11] و [20] و [29]. اشاره نمود. ذکر این نکته در خصوص روش‌هاي جفتي، ضرورت دارد که با توجه به اينکه اغلب شاخص‌هاي ارزيابي در حوزه بازيابي اطلاعات، در سطح پرس‌وجوها و بر مبناي موقعيت نهايي اسناد در فهرست مرتب‌شده عمل مي‌کنند، فاصله قابل توجهی، بين مدل عملکرد روش‌هاي جفتي و رتبه‌بندي مطلوب در مقوله بازيابي اطلاعات، مشاهده مي‌شود.

فضاي ورودي در روش‌هاي مبتني بر فهرست، شامل مجموعه اسناد متناظر با پرس‌وجوي داده شده است. فضاي خروجي نیز عبارتست از فهرست مرتب‌شده اسناد يا به تعبير ديگر، جايگشتي از مجموعه اسناد داده شده است. این دسته از الگوریتم‏های یادگیری رتبه‏بندی را بر اساس نوع تابع زیان مورد استفاده، به دو دسته، تقسیم نمود. دسته نخست، روش‏های بهینه‏سازی مستقیم⁶ نامیده می‏شوند و شامل روش‏های رتبه‏بندی هستند که توابع زیان آنها، ارتباط مستقیمی با شاخص‏های استاندارد ارزیابی در حوزه بازیابی اطلاعات دارد [40] و [50] و [46] و [54] و [5] و [36] و [7] و [49]. در برخی دیگر از روش‏های اخیر، از رویکرد یادگیری عمیق⁷ برای تخمین شاخص‏های ارزیابی استفاده شده است [1] و [37] و [34] و [39]. همچنین ایده استفاده از قابلیت‏های الگوریتم ژنتیک، به منظور بهینه‌سازی شاخص‌های ارزیابی، در برخی تحقیقات مورد توجه بوده است که از جمله آنها می‌توان به این موارد اشاره کرد: [13] و [41] و [14] و [48] و [23]. در مقابل، در دسته دوم روش‏های فهرستی، الگوریتم‏های رتبه‏بندی قرار می‏گیرند که در آنها توابع زیان مورد استفاده، ارتباط مستقیمی با شاخص‏های استاندارد ارزیابی جستجو، ندارد. از جمله اين روش‌ها مي‌توان به [4] و [43] و [34] و [53] و [44] اشاره نمود.

علیرغم مطالعات گسترده صورت گرفته در حوزه یادگیری رتبه‏بندی، این حوزه تحقیقاتی، با نواقص و محدودیت‌های جدی، همراه است. از مهم‌ترین این معضلات، عدم استفاده از اطلاعات مربوط به سوابق رفتارهای کاربران در حین انجام جستجوها، در فرآیندهای بازیابی و رتبه‌بندی نتایج است. در واقع، عدم اقبال کاربران برای ارایه بازخورد صریح از نحوه عملکرد جویشگر مورد استفاده، محققان را بر آن داشته است تا با پردازش سوابق رفتار کاربران، بازخورد ضمنی رفتار آنها را استخراج کنند. بنا بر نتایج تحقیقات انجام شده، اطلاعات حاصل از پردازش سوابق تعاملات و رفتارهای کاربران، که اصطلاحاً اطلاعات کلیک از گذر داده، نامیده می‌شود، بسیار ارزشمند بوده و بکارگیری آنها می‌تواند منجر به بهبود کیفیت فرآیند بازیابی اطلاعات، به میزان قابل توجهی شود
[22] و [30] و [31]. فقدان این قبیل اطلاعات، در اغلب مجموعه‌های داده محک⁸ موجود در زمینه یادگیری رتبه‌بندی، باعث گردیده است تا اغلب روش‌های یادگیری رتبه‌بندی موجود، امکان استفاده از این قبیل اطلاعات را نداشته باشند که این امر، یکی از معضلات و محدودیت‌های اصلی پیش‌روی حوزه یادگیری رتبه‌بندی، بشمار می‌رود. در عین حال، عرضه انبوهی از ویژگی‏های مرتبط با پرس‌وجوها و نتایج و بکارگیری آنها در الگوریتم‌های موجود، کاربری آنها را در شرایط واقعی، دشوار می‌سازد. علت این امر آن است که در شرایط واقعی، تهیه داده‌های مربوط به این تعداد زیاد از ویژگی‏ها، فرآیندی دشوار و وقت‌گیر می‌باشد. بر این اساس و با الهام از پایه مفهوم «اطلاعات کلیک از گذر داده»، ایده جدیدی در سال‏های اخیر مطرح شده است که در آن، به تولید مجموعه‏ای از ویژگی‏های ثانویه بر پایه ویژگی‏های پایه مجموعه داده محک مورد استفاده پرداخته می‏شود. این مجموعه را اصطلاحاً «ویژگی‏های کلیک از گذر داده» می‏نامند. در [23]، با اِعمال مدل برنامه‏نویسی ژنتیک چند لایه روی ویژگی‏های کلیک از گذر داده، الگوریتم جدیدی موسوم به MGP-Rank ارائه شده است که عملکرد قابل توجهی در رتبه‏بندی اطلاعات انگلیسی وب داشته است. توفیق این الگوریتم، الهام بخش این پژوهش بوده است تا با تطبیق ساختار این الگوریتم بر اساس ویژگی‏های زبان فارسی، الگوریتم رتبه‏بندی قدرتمندی برای دادگان فارسی وب، حاصل شود.

3- معرفی روش پیشنهادی

این بخش به معرفی و بیان نحوه عملکرد الگوریتم‏ MGP-Rank اختصاص یافته است و جزئیات گام‏های اجرای این الگوریتم،‏ مورد بحث و بررسی قرار گرفته است.

3-1-کلیات الگوریتم MGP-Rank

الگوریتم MGP-Rank با استفاده از مدل برنامه‌نویسی ژنتیک چند لایه، روی ویژگی‌های کلیک از گذر داده، عمل می‌کند[23]. در این الگوریتم، ویژگی‌های کلیک از گذر داده، در یک چارچوب مدل برنامه‌نویسی ژنتیک چند لایه و چند جمعیتی، بکار گرفته می‌شوند تا بر اساس برخی شاخص‌های بازیابی اطلاعات، بهترین توابع رتبه‌بندی ممکن، شناسایی شوند. مهم‌ترین مزیت مدل برنامه‌نویسی ژنتیک چند لایه، قابلیت جستجوی سریع‌تر و فراگیرتر آن نسبت به مدل برنامه‌نویسی ژنتیک معمول است. بر این اساس، الگوريتم MGP-Rank، از اين جهت با روش‌هاي مشابه، متفاوت است كه در آن، از مفهوم اطلاعات كليك از گذر داده [21] به منظور توليد ويژگي‌هاي كليك از گذر داده، استفاده شده است. فرآيند توليد ويژگي‌هاي كليك از گذر داده، در هر دو حالت وجود يا عدم وجود اطلاعات مرتبط با كليك از گذر داده در مجموعه داده محك مورد استفاده، امكان‌پذير است. سپس از اين ويژگي‌ها در قالب معماري LAGEP [26]، به منظور يافتن توابع رتبه‌بندي مناسب، استفاده مي‌شود كه تركيبي از ويژگي‌هاي مرتبط با محتواي اسناد، ويژگي‌هاي ساختاري صفحات وب و نيز ويژگي‌هاي مرتبط با نحوه جستجوي كاربران، خواهد بود. در تعيين توابع برتر، از شاخص‌هاي ارزيابي مرتبط با مقوله بازيابي اطلاعات نظير دقت⁹، صحت¹⁰، فراخواني¹¹، F-measure و نيز خاص بودن¹² به عنوان توابع سازگاري، مورد استفاده قرار گرفته است [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: بازنمایی تابع بصورت درخت دودویی

هر جمعیت با استفاده از سه عملگر ژنتیکی اصلی، یعنی ادغام¹³، جهش¹⁴ و بازتولید¹⁵، تکامل می‌یابند. نرخ بکارگیری عملگرهای سه‌گانه ادغام، جهش و بازتولید، به ترتیب برابر با ، و می‌باشد. در بکارگیری عملگر جهش، نخست بصورت تصادفی، گره‌ای از ساختار دودویی فرد مورد نظر به عنوان نقطه جهش¹⁶ در نظر گرفته می‌شود و با گره دیگری که از مجموعه متناظر یعنی ، ویا ، که بصورت تصادفی انتخاب شده است، جایگزین می‌شود. در واقع، هدف عملگر جهش، اجتناب از بهینه‌های محلی است، زیرا با بکارگیری این عملگر، افراد جدیدی حاصل می‌شوند که ممکن است تا بحال در جمعیت‌های مورد مطالعه، مشاهده نشده باشند. به همین ترتیب، در عملگر ادغام نیز زیردرخت‌هایی از دو فرد که بصورت تصادفی انتخاب شده‌اند، با یکدیگر جایگزین می‌شوند و در نتیجه آن، دو فرد جدید، حاصل می‌شوند. نهایتاً در عملگر بازتولید، قاعده طبیعی بقای قوی‌ترین و مناسب‌ترین افراد، مدل‌سازی می‌شود و بهترین فرد هر نسل از جمعیت، عیناً در نسل بعدی نیز فرصت حضور، خواهد یافت. با توجه به اینکه عملگر جهش، تنوع افراد یک جمعیت را کنترل می‌کند، بدیهی است که نرخ بکارگیری آن () طی فرآیند تکامل یک جمعیت، بصورت مناسبی تنظیم شود. در LAGEP، این فرآیند از طریق روش تنظیم تطبیقی نرخ جهش (AMRT‏¹⁷) صورت می‌پذیرد که جزییات آن در [26] ذکر شده است. بطور خلاصه، در هر نسل از جمعیت، روش AMRT ، اقدام به ارزیابی میزان سازگاری افراد آن جمعیت می‌کند. چنانچه مقادیر میزان سازگاری افراد، یکسان باشد، مقدار افزایش می‌یابد و در غیر این‌صورت، نرخ جهش، برابر با مقدار اولیه آن، خواهد بود. علاوه بر آن، با توجه به اینکه: می‌باشد، افزایش ، به معنی کاهش است. در تحقیق انجام شده، مشخص شده است که استفاده از این تکنیک، منجر به بهبود عملکرد LAGEP خواهد شد [26]. ضمناً بایستی خاطر نشان کرد که برای انتخاب افراد جهت اِعمال عملگرهای ادغام و جهش، می‌توان از روش‌های انتخاب مختلف نظیر انتخاب تصادفی¹⁸ یا انتخاب از طریق مسابقه استفاده نمود¹⁹. در روش انتخاب از طریق مسابقه، ابتدا افرادی از جمعیت هدف به تعداد مشخصی که اصطلاحاً اندازه مسابقه²⁰ نامیده می‌شود، بصورت تصادفی، انتخاب می‌شوند و سپس بر اساس میزان سازگاری آنها، یک یا دو نفر آنها از به ترتیب، جهت عملگرهای جهش یا ادغام، برگزیده می‌شوند.

در معماری معرفی شده برای 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، از شاخص‌هاي مرجع در ارزیابی رتبه‏بندی یعنی ، ، و ، استفاده شده است.

· دقت²¹ در نقطه k (): اگر قضاوت انسانيِ اسناد، به‌صورت دودويي در اختيار باشد، مثلاً برچسب اسناد مرتبط، يک و برچسب اسناد نامرتبط، صفر باشد، در این صورت، به‌صورت زير تعريف مي‌شود [32]:

که تابع شاخص است و به برچسب سند قرار گرفته در موقعيت ليست مرتب نتايج، ، اشاره مي‌کند.

· متوسط ميانگين دقت²² (): بر اساس تعريف ارائه شده از دقت در موقعيت ، میانگین دقت²³ () عبارتست از:

(1)

که در آن، تعداد کل اسناد متناظر پرس‌وجوي است و تعداد زير مجموعه‌اي از اين اسناد است که میزان مرتبط بودن آنها برابر با يک باشد. مقدار ميانگين روي همه پرس‌وجوهاي آزمون، متوسط ميانگين دقت () ناميده مي‌شود [32].

· بهره انباشته کاهشی هنجار شده²⁴ (NDCG) در نقطه (): این شاخص بر پایه میانگین‏گیری از شاخص بهره انباشته کاهشي²⁵ ()، محاسبه می‏شود. شاخص بهره انباشته کاهشي () مي‌تواند قضاوت‌هاي ميزان مرتبط بودن را که به‌صورت طبقه‌بندي‌هاي مرتب چندگانه ارائه شده باشند، در ارزیابی مورد استفاده قرار دهد؛ ضمن آنکه در تعريف آن، يک ضريب کاهشي بر اساس موقعيت اسناد، در نظر گرفته شده است [18] و 9[32]. برای بیان این موضوع به زبان رياضي، فرض کنيد که ليست مرتبي از نتايج نظير به ازاي پرس‌وجوي وجود داشته باشد؛ در اين صورت، مقدار شاخص در موقعيت به‌صورت زير تعريف مي‌شود:

(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

شایان توجه است که در همه این سناریوها، ابتدا خصوصیات پایه داده محک dotIR، به روش Min-Max، هنجارسازی شده‌اند و سپس روش هموار سازی موسوم به Dirichlet prior [32]، روی آنها اِعمال شده است.

ویژگی‌های کلیک از گذر داده بدست آمده، در فرآیند تولید جمعیت، به عنوان مجموعه متغیرها، ، مورد استفاده قرار می‌گیرند. هر فرد مانند بصورت یک درخت دودویی نمایش داده می‌شود. در شکل شماره شش، دو فرد نمونه به همراه نتایج حاصل از اِعمال عملگرهای ترکیب و جهش، به تصویر کشیده شده است. در این مثال، متغیرهای CF1، CF2، CF3، CF4 و CF5، به ترتیب نماینده ویژگی‌های کلیک از گذر داده ، ، ، و می‌باشند.

شناسه سناریو	روش محاسبه
IR-DF1
IR-DF2
IR-DF3
IR-DF4
IR-DF5
IR-DF6
IR-DF7

شکل 6: نمونه افراد جمعیت ژنتیکی و نتایج اِعمال عملگرهای ژنتیک روی آنها

ب- بازنمایی عبارت شماره دو بصورت درخت دودویی:	الف- بازنمایی عبارت شماره یک بصورت درخت دودویی:

ج- بازنمایی نتایج عملگر ترکیب بصورت درخت دودویی
د- بازنمایی نتیجه اِعمال عملگر جهش روی عبارت شماره یک بصورت درخت دودویی

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
درصد رشد¹	50

[1] Grow Percentage

چارچوب LAGEP مورد استفاده در این تحقیق، از سه لایه مجزا تشکیل یافته است که جزییات آنها در جدول شماره پنج آمده است. هر لایه، شامل تعدادی جمعیت است که در مقداردهی اولیه آنها از روش رشد¹، استفاده شده است. در این روش، درخت‌های متناظر با افراد عضو جمعیت‌ها، طی یک فرآیند بازگشتی، ایجاد می‌شوند، به نحوی ‌که عمق درخت حاصله، از مقدار متغیر «عمق درخت»، بیشتر نباشد و حجم درخت نسبت به درخت کامل با همان عمق، از مقدار متغیر «درصد رشد»، تجاوز نکند. جمعیت‌های حاصل از این فرآیند، توسط عملگرهای ژنتیکی با نرخ بکارگیری مشخص شده در جدول شماره چهار، تکامل می‌یابند. سپس از هر جمعیت، فردی با بیشترین میزان تابع برازش، برای بقا در نسل بعد، باقی خواهد ماند. این فرآیند در هر جمعیت تا رسیدن به تعداد مشخصی از نسل‌ها، ادامه پیدا می‌کند.

[1] Grow Method

جدول5: مشخصات لایه‌های چارچوب LAGEP مورد استفاده

مشخصات لایه	لایه شماره یک	لایه شماره دو	لایه شماره سه
تعداد جمعیت‌ها	1	2	3
تعداد افراد هر جمعیت	100	100	10
تعداد نسل‌ها	50	10	10
اندازه مسابقه	5	7	1
تعداد افراد باقی مانده از یک جمعیت در نسل بعدی	1	1	1
عمق درخت	4	6	4

هر فرد از یک جمعیت را می‌توان بصورت یک رده‌بندی کننده، در نظر گرفت و کارآیی آن در فرآیند رده‌بندی را توسط یک ماتریس ابهام¹ با چهار مقدار: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) / (TP + TN + FP + FN)
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 @1	NDCG @2	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 @1	NDCG @2	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.

Share To

Article Url

Learning to Rank for the Persian Web Using the Layered Genetic Programming

Rimag

Links

Related Centers

Technical Support

Official pages