SCM: новая вероятностная модель поведения пользователей интернет-поиска
Ключевые слова:
модели поведения пользователя, графические вероятностные модели, expectation propagationАннотация
Модели поведения пользователей -- одно из основных направлений исследований в области улучшения интернет-поиска; такие модели обычно основаны на графических вероятностных моделях и обучаются из логов пользовательских действий (click logs). В работе вводится новая модель поведения пользователей -- SCM (session click model, клик-модель сессии). Мы показываем, что новая модель проще для вывода, но в практических приложениях даёт результаты лучше, чем существующие модели.Литература
Bishop C. M. Pattern Recognition and Machine Learning. Springer, 2006
Burges C. J., Shaked T., Renshaw E., Lazier A., Deeds M., Hamilton N., Hullender G. Learning to rank using gradient descent // Proceedings of the 22 International Conference on Machine Learning. 2005. P. 89
Burges C. J. C. From RankNet to LambdaRank to LambdaMART : An Overview: Tech. rep.: Microsoft Research, 2010
Burges C. J. C., Svore K. M., Bennett P. N., Pastusiak A., Wu Q. Learning to Rank Using an Ensemble of Lambda-Gradient Models // Journal of Machine Learning Research. 2011. Vol. 14. P. 25-35
Chapelle O., Zhang Y. A dynamic Bayesian network click model for web search ranking // Proceedings of the 18th International Conference on World Wide Web. 2009. P. 1-10
Craswell N., Zoeter O., Taylor M., Ramsey B. An experimental comparison of click position-bias models // Proceedings of the 1st ACM International Conference on Web Search and Data Mining. 2008. P. 87-94
Donmez P., Svore K. M., Burges C. J. C. On the local optimality of LambdaRank // Proceedings of the 32nd Annual ACM SIGIR Conference. ACM, 2009. P. 460-467
Dupret G., Liao C. A model to estimate intrinsic document relevance from the clickthrough logs of a web search engine // Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. 2010. P. 181-190
Dupret G., Piwowarski B. A user browsing model to predict search engine click data from past observations // Proceedings of the 31st Annual ACM SIGIR Conference. 2008. P. 331-338
Freund Y., Iyer R., Schapire R. E., Singer Y. An efficient boosting algorithm for combining preferences // Journal of Machine Learning Research. 2005. Vol. 4. P. 933-969
Frey B. J. Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models // Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence. Acapulco, Mexico: Morgan Kaufmann Publishers Inc., 2003. P. 257-264
Friedman J. Greedy function approximation: a gradient boosting machine // Annals of Statistics. 2001. Vol. 29. P. 1180
Guo F., Liu C., Kannan A., Minka T., Taylor M., Wan Y., Faloutsos C. Click chain model in web search // Proceedings of the 18th International Conference on World Wide Web. 2009. P. 11-20
Hastie T., Tibshirani R., Friedman J. Elements of Statistical Learning. Springer, New York, 2008
Joachims T., Granka L. A., Pang B., Hembrooke H., Gay G. Accurately Interpreting Clickthrough Data as Implicit Feedback // Proceedings of the 28th Annual ACM SIGIR Conference. 2005. P. 154-161
Kschischang F. R., Frey B. J., Loeliger H.-A. Factor Graphs and the Sum-Product Algorithm // IEEE Transactions on Information Theory. 2001. Vol. 47, N. 2. P. 498-519
Ling C. X., Huang J., Zhang H. AUC: a Statistically Consistent and more Discriminating Measure than Accuracy // Proceedings of the International Joint Conference on Articial Intelligence 2003. 2003. P. 519-526
MacKay D. J. Information Theory, Inference and Learning Algorithms.
Minka T. Expectation Propagation for approximate Bayesian inference // Proceedings of the 17th Conference on Uncertainty in Articial Intelligence / Ed. by J. S. Breese, D. Koller. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2001. P. 362-369
Minka T. A family of algorithms for approximate Bayesian inference: Ph.D. thesis / Massachusetts Institute of Technology. 2001
Minka T., Winn J., Guiver J., Knowles D. Infer.NET 2.4. 2010. Microsoft Research Cambridge. Http://research.microsoft.com/infernet
Pearl J. Probabilistic reasoning using graphs // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Springer- Verlag, 1987. P. 201-202
Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. NY etc.: Morgan Kaufmann, 1994
Prince S. Computer Vision: Models, Learning, and Inference. Cambridge University Press, 2012
Richardson M., Dominowska E., Ragno R. Predicting clicks: estimating the click-through rate for new ads // Proceedings of the 16th International Conference on World Wide Web. 2009. P. 521-530
Zhang Y., Chen W., Wang D., Yang Q. User-click modeling for understanding and predicting search-behavior // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, 2011. P. 1388-1396
Заболотский В. П., Юсупов Р. М. Основные проблемы устойчивости перехода к информационному обществу/Труды СПИИРА002. Т. 1, № 1. С.13-26
Николенко С. И., Тулупьев А. Л. Самообучающиеся системы. М.: МЦНМО, 2009. 288 с.
Сироткин А. В. Байесовские сети доверия: дерево сочленений и его вероятностная семантка // Труды СПИРАН. 2006. Т. 1, № 3. С. 228-239
Сироткин А. В. Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовсих сетяхТруды СПИИРАН. 2006. Т. 1, № 3. С. 228-239
Сироткин А. В., Тулупьев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмв // Труды СПИИРАН.2007. № 5 С. 100-111
Тулупьев А. Л., Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант// Известия высших учебных заведений: Приборостроение.2006. № 11. С. 35-39
Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход . СПб.: Наука, 2006. 608 с.
Тулупьев А. Л., Николенко С. И., Сироткин А. В. Синтез апостериорных оценок при поступлении свидетельств с неопределенностью в интегрированную систему знаний о неточных вероятностях// Известия высших учебных заведений: Приборостроение. 2006.№ 11.С. 39-44
Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Известия высших учебных заведений: Приборостроение. 2006.№ 7С.20-26
Тулупьев А. Л., Сироткин А. В., Николенко С. И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах . СПб.: Из-во С.-Петербургского ун-та, 2009. 400 с.
Яндекс Поиск в интернете: что и как ищут пользователи. Информационный бюллетень <<Яндекс>>, http://download.yandex.ru/company/yandex_search_autumn_2008_ru.pdf. 2008
Яндекс Конкурс <<Интернет--математика>>. http://imat-relpred.yandex.ru/. 2011
Burges C. J., Shaked T., Renshaw E., Lazier A., Deeds M., Hamilton N., Hullender G. Learning to rank using gradient descent // Proceedings of the 22 International Conference on Machine Learning. 2005. P. 89
Burges C. J. C. From RankNet to LambdaRank to LambdaMART : An Overview: Tech. rep.: Microsoft Research, 2010
Burges C. J. C., Svore K. M., Bennett P. N., Pastusiak A., Wu Q. Learning to Rank Using an Ensemble of Lambda-Gradient Models // Journal of Machine Learning Research. 2011. Vol. 14. P. 25-35
Chapelle O., Zhang Y. A dynamic Bayesian network click model for web search ranking // Proceedings of the 18th International Conference on World Wide Web. 2009. P. 1-10
Craswell N., Zoeter O., Taylor M., Ramsey B. An experimental comparison of click position-bias models // Proceedings of the 1st ACM International Conference on Web Search and Data Mining. 2008. P. 87-94
Donmez P., Svore K. M., Burges C. J. C. On the local optimality of LambdaRank // Proceedings of the 32nd Annual ACM SIGIR Conference. ACM, 2009. P. 460-467
Dupret G., Liao C. A model to estimate intrinsic document relevance from the clickthrough logs of a web search engine // Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. 2010. P. 181-190
Dupret G., Piwowarski B. A user browsing model to predict search engine click data from past observations // Proceedings of the 31st Annual ACM SIGIR Conference. 2008. P. 331-338
Freund Y., Iyer R., Schapire R. E., Singer Y. An efficient boosting algorithm for combining preferences // Journal of Machine Learning Research. 2005. Vol. 4. P. 933-969
Frey B. J. Extending Factor Graphs so as to Unify Directed and Undirected Graphical Models // Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence. Acapulco, Mexico: Morgan Kaufmann Publishers Inc., 2003. P. 257-264
Friedman J. Greedy function approximation: a gradient boosting machine // Annals of Statistics. 2001. Vol. 29. P. 1180
Guo F., Liu C., Kannan A., Minka T., Taylor M., Wan Y., Faloutsos C. Click chain model in web search // Proceedings of the 18th International Conference on World Wide Web. 2009. P. 11-20
Hastie T., Tibshirani R., Friedman J. Elements of Statistical Learning. Springer, New York, 2008
Joachims T., Granka L. A., Pang B., Hembrooke H., Gay G. Accurately Interpreting Clickthrough Data as Implicit Feedback // Proceedings of the 28th Annual ACM SIGIR Conference. 2005. P. 154-161
Kschischang F. R., Frey B. J., Loeliger H.-A. Factor Graphs and the Sum-Product Algorithm // IEEE Transactions on Information Theory. 2001. Vol. 47, N. 2. P. 498-519
Ling C. X., Huang J., Zhang H. AUC: a Statistically Consistent and more Discriminating Measure than Accuracy // Proceedings of the International Joint Conference on Articial Intelligence 2003. 2003. P. 519-526
MacKay D. J. Information Theory, Inference and Learning Algorithms.
Minka T. Expectation Propagation for approximate Bayesian inference // Proceedings of the 17th Conference on Uncertainty in Articial Intelligence / Ed. by J. S. Breese, D. Koller. San Francisco, CA: Morgan Kaufmann Publishers Inc., 2001. P. 362-369
Minka T. A family of algorithms for approximate Bayesian inference: Ph.D. thesis / Massachusetts Institute of Technology. 2001
Minka T., Winn J., Guiver J., Knowles D. Infer.NET 2.4. 2010. Microsoft Research Cambridge. Http://research.microsoft.com/infernet
Pearl J. Probabilistic reasoning using graphs // Uncertainty in Knowledge-Based Systems / Ed. by B. Bouchon, R. R. Yager. Springer- Verlag, 1987. P. 201-202
Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. NY etc.: Morgan Kaufmann, 1994
Prince S. Computer Vision: Models, Learning, and Inference. Cambridge University Press, 2012
Richardson M., Dominowska E., Ragno R. Predicting clicks: estimating the click-through rate for new ads // Proceedings of the 16th International Conference on World Wide Web. 2009. P. 521-530
Zhang Y., Chen W., Wang D., Yang Q. User-click modeling for understanding and predicting search-behavior // Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, USA, 2011. P. 1388-1396
Заболотский В. П., Юсупов Р. М. Основные проблемы устойчивости перехода к информационному обществу/Труды СПИИРА002. Т. 1, № 1. С.13-26
Николенко С. И., Тулупьев А. Л. Самообучающиеся системы. М.: МЦНМО, 2009. 288 с.
Сироткин А. В. Байесовские сети доверия: дерево сочленений и его вероятностная семантка // Труды СПИРАН. 2006. Т. 1, № 3. С. 228-239
Сироткин А. В. Вычислительная сложность алгоритмов локального апостериорного вывода в алгебраических байесовсих сетяхТруды СПИИРАН. 2006. Т. 1, № 3. С. 228-239
Сироткин А. В., Тулупьев А. Л. Локальный априорный вывод в алгебраических байесовских сетях: комплекс основных алгоритмв // Труды СПИИРАН.2007. № 5 С. 100-111
Тулупьев А. Л., Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант// Известия высших учебных заведений: Приборостроение.2006. № 11. С. 35-39
Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход . СПб.: Наука, 2006. 608 с.
Тулупьев А. Л., Николенко С. И., Сироткин А. В. Синтез апостериорных оценок при поступлении свидетельств с неопределенностью в интегрированную систему знаний о неточных вероятностях// Известия высших учебных заведений: Приборостроение. 2006.№ 11.С. 39-44
Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Известия высших учебных заведений: Приборостроение. 2006.№ 7С.20-26
Тулупьев А. Л., Сироткин А. В., Николенко С. И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах . СПб.: Из-во С.-Петербургского ун-та, 2009. 400 с.
Яндекс Поиск в интернете: что и как ищут пользователи. Информационный бюллетень <<Яндекс>>, http://download.yandex.ru/company/yandex_search_autumn_2008_ru.pdf. 2008
Яндекс Конкурс <<Интернет--математика>>. http://imat-relpred.yandex.ru/. 2011
Опубликован
2012-03-01
Как цитировать
Николенко, С. И., & Фишков, А. А. (2012). SCM: новая вероятностная модель поведения пользователей интернет-поиска. Труды СПИИРАН, 1(20), 72-100. https://doi.org/10.15622/sp.20.4
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
