Оценка систем текстового поиска тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Кураленок, Игорь Евгеньевич

• Кураленок, Игорь Евгеньевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Кураленок, Игорь Евгеньевич

Введение

1 Анализ состояния области

1.1 Оценка систем информационного поиска.

1.2 Предмет оценки

1.2.1 Поисковая система.

1.2.2 Наборы данных.

1.3 Критерии.

1.3.1 Релевантность

1.4 Меры, используемые в оценке

1.4.1 Меры на уровне обработки.

1.4.2 Меры на уровне выхода.

1.4.3 Другие меры.

1.5 Инструменты измерения.

1.5.1 Теоретические подходы.

1.5.2 Реальные пользователи.

1.5.3 Экспертные оценки.

1.5.4 Косвенные оценки.

1.6 Методы оценки.

1.6.1 Процедура проведения оценки.

1.6.2 Анализ результатов

1.6.3 Методология.

Введение диссертации (часть автореферата) на тему «Оценка систем текстового поиска»

Актуальность проблемы поиска и обработки текстовой информации сегодня не вызывает сомнений. Ежедневно мы сталкиваемся с необходимостью ее эффективного решения на работе и дома. Многие сферы нашей деятельности зачастую тесно связаны с электронными технологиями, получившими за последние два десятка лет широкое распространение в нашей стране. Так, для того чтобы найти необходимую книгу или ноты не обязательно выходить из дома, а для того, чтобы узнать курс валют или акций идти на биржу. Большинство информации можно найти в общедоступных сетях (internet, fidonet, домашние сети (homenet) и т.п.), однако большинство этих сетей содержат информацию неупорядоченно, что приводит к необходимости ее поиска. Так как большинство информации представлено в тексте, наиболее часто встающей перед пользователем является задача полнотекстового поиска.

Текстовый поиск — одна из самых первых задач компьютерной эры. История исследований в этой области берет свое начало в 50-х годах, когда создавались первые поисковые системы (Н. Luhn, 1958 [29]). Наиболее масштабные же исследования в области информационного поиска относятся к 90 годам и продолжаются по сей день. Столь долгий период невостребованности исследований широким кругом пользователей (практически до конца 80-х) в первую очередь связан с тем, что большинство предлагаемых методов эффективны на больших объемах данных, которые не могут быть подвергнуты анализу по выделению структуры (поиск в структурированных данных — решенная задача), а такие данные были просто недоступны широкому пользователю из-за малой мощности существовавших вычислительных машин. В конце 80-х широкое распространение получили сетевые технологии, которые позволили распределить информацию по множеству машин, это и привело к расцвету текстового поиска.

Несмотря на богатую историю исследований полнотекстового поиска, широкое распространение получили лишь несколько наиболее простых технологий: простые векторные и вероятностные модели, что связано в первую очередь с простотой их реализации. Спрос на поисковые системы столь велик, что большинство реализаций написаны непрофессионалами в поиске, для которых фактор простоты реализации является определяющим. Но даже в том случае, когда работу выполняет человек, осведомленный о достижениях в этой области, он все равно скорее всего изберет один из проверенных и зарекомендовавших себя методов. Этот факт связан с первую очередь с тем, что зачастую методы, показывающие хорошие результаты на одних данных, оказываются много хуже тех же классических моделей на других данных. Эти две проблемы приводят к сегодняшней ситуации, когда 95% всех поисковых систем используют различные вариации векторных моделей, эффективность которых оставляет желать лучшего, что приводит к заслуженному недоверию пользователя к результатам поиска.

Если первая обозначенная причина ситуации вряд ли может быть как-либо исправлена средствами науки, то вторая напрямую связана с провалом методологий оценки, принятых в поиске. Несмотря на то, что область оценки имеет почти столь же богатую историю как и сама область поиска (точкой отсчета можно считать вторые Кренфилдские эксперименты 1963 г.), продвижения в этой области до 1992 г. минимальны, и лишь с появлением TREC (Text REtrival Conference) ситуация несколько изменилась. В 1998 г. выяснилось, что технологии хорошо зарекомендовавшие себя в TREC абсолютно не применимы в среде Internet, что показывает "эффективность" тестирования при переносе на другие данные. С тех пор в TREC были добавлены новые коллекции, в том числе Web и VLT, исследованы многие важные проблемы и задачи поиска (многоязыковый поиск, проблема переноса техники поиска на другие языки и т.п. см. п. 1), но принципиальных изменений в методологии так и не последовало.

Предлагаемое исследование — маленький шажок в сторону понимания эффектов искажения результатов тестирования при переносе на новые данные. В работе сделана попытка анализа поведения результатов оценки при изменении данных. Так же предложен оригинальный способ автоматического построения оценки системы поиска относительно результатов работы системы с известными характеристиками. Рассмотренный метод имеет значительный потенциал для применения в построении предварительной оценки, так как несравнимо менее требователен к ресурсам (прежде всего человеческим), чем все существующие подходы. Построение описанного метода было невозможно без теоретической поддержки. В работе приведена своя интерпретация понятия релевантности, основанная на вероятностной модели. Еще одной иллюстрацией адекватности предложенной модели релевантности стала эффективность предлагаемого метода построения мета-поисковой системы, основанного на этой модели.

Далее работа разделена на пять частей. Первая часть представляет собой анализ существующего состояния дел в области оценки текстового поиска[73]. Основной целью этой части является введение в проблематику и обзор принятой на сегодня методологии оценки. Отличительной чертой приведенного анализа является представление большой части известных аспектов оценки в едином каркасе.

Во второй части работы приведены основные теоретические выкладки. В этой части многие утверждения приводятся без доказательств (которые приведены отдельно в разделе экспериментов) с целью как можно более краткого и обозримого изложения. Несмотря на свой небольшой объем эта часть содержит большинство результатов работы.

Третья часть посвящена экспериментальным данным, использованным для подтверждения теоретических выкладок. В качестве тестовой базы приводимых экспериментов были использованы данные РОМИП'ОЗ (Российский семинар по Оценке Методов Информационного Поиска). Качество данных и способ их сбора — ключевая часть любого эксперимента, поэтому было решено подробно описать процедуру их построения. К тому же, в рамках работы над диссертацией автор имел возможность принять участие в работе семинара РОМИП (Российский по Оценке Методов Информационного Поиска) в качестве одного из его организаторов. И наряду с другими участниками организационного комитета создавал методологическую базу семинара. Этим фактом так же объясняется использование в работе данных, закрытых для широкого пользователя.

Четвертая часть работы представляет собой серию экспериментов, показывающих обоснованность утверждений второй части.

Последняя пятая часть посвящена выводам и возможным направлениям дальнейших исследований.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кураленок, Игорь Евгеньевич

Заключение

В приведенной работе были исследованы некоторые свойства результатов оценки систем текстового поиска. Данное исследование представляет собой первый шаг в области более широкого использования результатов тестирования. На основе предложенного подхода были получены следующие результаты:

• нашла свое подтверждение гипотеза о сходимости результатов тестирования при увеличении тестовой базы;

• исследована зависимость вероятности релевантности документа запросу от индекса ранжирования реальной поисковой системы;

• построена новая математическая модель представления релевантности;

• разработан метод автоматического построения характеристик поисковой системы относительно известной;

• разработан алгоритм построения мета-поисковой системы на основе предложенной теории.

Эти результаты показывают перспективность выбранного направления и примененного подхода к определению основных понятий поиска.

В работе результаты оценки рассматриваются как самостоятельные данные, что позволяет в значительной степени расширить область их применения. Подобное было бы невозможно без знания того, что в среднем эти результаты сходятся при увеличении тестового набора. Этот фундаментальный факт получил частичное подтверждение в изложенной выше работе, однако характер сходимости и ее зависимость от данных — тема дальнейших исследований.

Впервые результаты оценки были рассмотрены не только как характеристика оцениваемых систем, но и как характеристика тестовой коллекции. Такой подход дал возможность разработать новую модель релевантности, которая позволила с одной стороны оценивать системы друг относительно друга, с другой же, ранжировать результаты работы различных систем поиска.

В частности, одним из приложений выдвинутой модели стал метод автоматической оценки систем текстового поиска. Кроме своей практической ценности (а это по сути первый метод такого рода) результатом построения предложенного метода является и доказательство независимости отношения характеристик методов от тестовой базы. В нашем исследовании была использована лишь информация о распределении вероятности релевантности, полученная на небольшом наборе из 54 заданий. Далее эта информация была применена ко много большему множеству заданий (10000). Полученная в результате схожесть графиков (экспертного и полученного в результате работы предложенного алгоритма) не может быть случайной и говорит об общем для любых данных отношении поведения систем. Это, на первый взгляд, слишком сильное утверждение во многом следует из самой постановки задачи поиска. Как видно из п. 4.1 в среднем вероятность релевантности документа запросу убывает с увеличением индекса ответа. Задача любой системы поиска — сделать это убывание как можно более сильным, таким образом, с точки зрения вероятности релевантности, системы тем ближе друг другу, чем лучше они эту задачу решают. Эта близость и приводит к зависимости их характеристик.

Список литературы диссертационного исследования кандидат физико-математических наук Кураленок, Игорь Евгеньевич, 2004 год

1. Ricardo Baeza-Yates and Berthier Ribeiro-Neto. Modern 1.formation Retrieval. ACM Press, 1999.

2. P. Borlund and P. Ingwersen. Measures of relative relevance and ranked half-life: Performance indicators for interactive IR. In Proc of the SIGIR'98, pages 324-331, 1998.

3. T. Brooks. The semantic distance model of relevance assessment. In Proc. of the annual meeting of A SIS, pages 33-44, October 1998.

4. Peter Bruza and T. W. C. Huibers. Investigating aboutness axioms using information fields. In Proc. of the SIGIR'94, pages 112-121, 1994.

5. Peter Bruza and T. W. C. Huibers. A study of aboutness in information retrieval. Artificial Intelligence Review, 10(5-6):381-407, 1996.

6. Peter Bruza, Robert McArthur, and Simon Dennis. Interactive internet search: keyword, directory and query reformulation mechanisms compared. In Proc. of the SIGIR'OO, pages 280-287, 2000.

7. Peter Bruza and D. Song. Theoretical evaluation of IR models using symbolic means. In Proc. of the MFIR'01, 2001.

8. Chris Buckley and Ellen M. Voorhees. Evaluating evaluation measure stability. In Proc. of the SIGIR '00, pages 33-40, 2000.

9. R. Burgin. Variations in relevance judgments and the evaluation of retrieval performance. Information Processing and Management, 5(28):619—627, 1992.

10. C.W. Cleverdon. The effect of variations in relevance assessments in comparative experimental tests of index languages. Information Processing and Management, 5 (28) :619-627, 1970.

11. William G. Cochran. Sampling Techniques (second edition). John Wiley & Sons, Inc., New York — London, 1963.

12. William S. Cooper. On selecting a measure of retrieval effectiveness. In Karen Sparck Jones and Peter Willett, editors, Readings in Information Retrieval, pages 87-100. Morgan Kaufmann, 1997.

13. Gordon Cormack, Ondrej Lhotak, and Christopher Palmer. Estimating precision by random sampling. In Proc. of the SIGIR'99, pages 273 274, 1999.

14. Gordon V. Cormack, Christopher R. Palmer, and Charles L. A. Clarke. Efficient construction of large test collections. In Proc. of the SIGIR'98, pages 282-289, 1998.

15. Harman D. What we have learned, and not learned, from tree. In Proc. of the BCS IRSG'2000, pages 2-20, 2000.

16. Ron Dolin, J. Pierre, M. Butler, and R. Avedon. Practical evaluation of IR within automated classification systems. In Proc. of the CIKM'99, pages 322-329, 1999.

17. Steve Draper. Mizzaro's framework for relevance, August 1998. Available from http://staff.psy.gla.ac.uk/~steve/stefano.html.

18. Mark D. Dunlop. Time, relevance and interaction modelling for information retrieval. In Proc. of the SIGIR '97, pages 206-213, 1997.

19. S. Gabrielli and S. Mizzaro. Negotiating a multidimensional framework for relevance space. In Proc. of the MIRA '99, pages 1-15, 1999.

20. Howard Greisdorf. Relevance: An interdisciplinary and information science perspective. Informing Science, 3(2):67-72, 2000.

21. D. Harman. Overview of the first text retrieval conference. In Proc. of the TREC-1, 1992.

22. D. Harman. What we have learned, and not learned, from TREC. In Proc. of the BCS IRSG'2000, pages 2-20, 2000.

23. D. Hawking, E. Voorhees, N. Craswell, and P. Bailey. Overview of the trec-8 web track. In Proc. of the TREC-8, pages 131-150, 2000.

24. David Hawking, Nick Craswell, and Paul B. Thistlewaite. Overview of TREC-7 very large collection track. In Proc. of the TREC-1, pages 40-52, 1999.

25. David Hawking and Paul B. Thistlewaite. Overview of TREC-6 very large collection track. In Proc. of the TREC-6, 1998.

26. J. Hongyan, R. Barzilay, C. McKeown, and M. Elhadad. Summarization evaluation methods: Experiments and analysis. In Proc. of AAAI Spring Symposium on Intelligent Text Summarization, pages 60-68, 1998.

27. P. Ingwersen. Polyrepresentation of information needs and semantic entities. In Proc. of the SIGIR'94, pages 51-60, 1994.

28. Kalevro Jarvelin and Jaana Kekalainen. IR evaluation methods for retrieving highly relevant documents. In Proc. of the SIGIR'00, pages 41-48, July 2000.

29. K. Sparc Jones, editor. Infromation Retrieval Experiment. Butterworth, London, 1981.

30. Karen Sparck Jones. Reflections on TREC. Information Processing and Management, 31(3):291-314, 1995.

31. J. Klavans, K. McKeown, M. Kan, and S. Lee. Resources for the evaluation of summarization techniques. In Proc. of the Conference on Language Resources and Evaluation, May 1998.

32. Eric Lagergren and Paul Over. Comparing interactive information retrieval systems across sites: The TREC-6 interactive track matrix experiment. In Proc. of the SIGIR'98, pages 164-172, 1998.

33. M. Lesk and G. Salton. Relevance assessments and retrieval system evaluation. Information Processing and Management, 3(4):343-358, 1968.

34. D. Lewis. Evaluating and optimizing autonomous text classification systems. In Proc. of the SIGIR'95, pages 246-254, 1995.

35. D. Lewis. The trec-4 filtering track. In Proc. of the TREC-4, 1996.

36. D. Lewis. Reuters-21578 text categorization test collection, 1997.

37. D. Lewis and M. Ringuette. A comparison of two learning algorithms for text categorisation. In Proc. of the SDAIR-94, pages 81-93, 1994.

38. David D. Lewis, Robert E. Schapire, James P. Callan, and Ron Papka. Training algorithms for linear text classifiers. In Proc. of the SIGIR'96, pages 298-306, 1996.

39. Robert Losee. Comparing boolean and probabilistic information retrieval systems across queries and disciplines. JASIS, 48(2): 143-156, 1997.

40. Robert Losee. When information retrieval measures agree about the relative quality of document rankings. JASIS, 51(9):834-840, 2000.

41. S. Mizzaro. How many relevances in information retrieval? Interacting with Computers, 10:303-320, 1998.

42. Stefano Mizzaro. Relevance: The whole history. Journal of the American Society of Information Science, 48(9):810-832, 1997.

43. Douglas W. Oard. Evaluating interactive cross-language information retrieval: Document selection. In Proc. of the CLEF, pages 57-71, 2000.

44. Vijay Raghavan. What do you say after you say, "I work in IR"? Available from http://www.cacs.usl.edu/~raghavan.

45. Jane Reid. A task-oriented non-interactive evaluation methodology for information retrieval systems. Information Retrieval, 2(1):113—127, 2000.

46. C. Van Rijsbergen. Foundation of evaluation. Journal of Documentation, 4(30):365-373, 1974.

47. David Robins. Interactive information retrieval: Context and basic notions. Informing Science, 3(2):57-62, 2000.

48. Tefko Saracevic. Evaluation of evaluation in information retrieval. In Proc. of the SIGIR'95, pages 135-146, 1995.

49. Tefko Saracevic. Relevance reconsidered 1996. In Proc. of the CoLIS2, pages 201-218, 1996.

50. D.W. Song, K.F. Wong, P.D. Bruza, and C.H. Cheng. Towards functional benchmarking of information retrieval models. In Proc. of the FLAIRS '99, pages 389-393, 1999.

51. Pertti Vakkari. Cognition and changes of search terms and tactics during task performance: A longitudinal study. In Proc. of the R1AO'2000, pages 894-907, 2000.

52. Pertti Vakkari. Relevance and contributory information types of searched documents in task performance. In Proc. of the SIGIR'00, 2000.

53. C. J. van Rijsbergen. Information Retrieval 2nd ed. Butterworths, 1979.

54. Е. Voorhees. Variations in relevance judgments and the measuremennt of retrieval effectiveness. In Proc. of the SIGIR'98, pages 315-323, August 1998.

55. E. Voorhees and D. Harman. Overview of the eighth text retrieval conference. In Proc. of the TREC-8, 1999.

56. E. Voorhees and D. Harman. Overview of the ninth text retrieval conference. In Proc. of the TREC-9, 2001.

57. Ellen Voorhees. Evaluating by highly relevant documents. In Proc. of the SIGIR'01, pages 74-82, 2001.

58. Ellen Voorhees and Dawn Tice. Building a question answering test collection. In Proc. of the SIGIR'00, pages 200-207, 2000.

59. Wilbur J. W. The knowledge in multiple human relevance judgments. In TOIS, volume 2, pages 101 126, 1998.

60. Peter Wallis and James Thom. Relevance judgements for assessing recall. Information Processing and Management, 32(11):273—286, 1996.

61. R. Wiener, E. Pedersen, and A. Weigend. A neural network approach to topic spotting. In Proc. of the Symposium on Document Analysis and Information Retrieval, 1995.

62. John W. Wilbur. The knowledge in multiple human relevance judgments. TOIS, 16(2): 101-126, April 1998.

63. Mei-Mei Wu and Diane H. Sonnenwald. Reflection on information retrieval evaluation. In Proc. of the 1999 EBTI, ECAI, SEER & PNC Joint Meeting, 1999.

64. Y. Yang. Expert network: Effective and efficient learning from human decisions in text categorization and retrieval. In Proc. of the SIGIR'94, pages 13 22, 1994.

65. Y. Yang and J. Pederson. Feature selection in statistical learning of text categorization. In Proc. of the ICML'97, pages 412-420, 1997.

66. Yiming Yang. An evaluation of statistical approaches to text categorization. Information Retrieval, l(l-2):69—90, 1999.

67. J. Zobel. How reliable are large-scale information retrieval experiments? In Proc. of the SIGIR '98, pages 308-315, August 1998.

68. П. Джексон, editor. Введение в экспертные системы. Вильяме, 2001.

69. И. Е.Кураленок. Метод предварительной оценки эффективности семантических методов обработки текстовой информации. In Труды третьей всероссийской научной конференции "Электронные библиотеки", октябрь 2001.

70. Вейн Ламбле and Дон Симен. Распространение и внедрение: основополагающие процессы социальных изменений. In Руководство по информационно-консультационной службе: процессы и практика Thompson Educational Publishing, 1994.

71. И. Некрестьянов and Н. Пантелеева. Системы текстового поиска для Веб. Программирование (в печати), 2002.

72. Павлова Е. Некрестьянов И., "Кураленок И.". "РОМИП-2003: опыт организации". In Труды РОМИП-2003, под редакцией И.С.Некрестьянова, СПб, Россия, октябрь 2003.

73. Кураленок И. Е. Некрестьянов И. С. "Оценка систем текстового поиска". In Программирование, Москва, Россия, июнь 2002.

74. В. С. Мхитарян С. А. Айвазян. Прикладная статистика и основы эконометрики. Москва. Издательское объединение "Юнити", 1998.