Інформаційний пошук
Інформаці́йний по́шук (ІП) (англ. Information retrieval) — наука про пошук неструктурованої документальної інформації. Особливо це відноситься до пошуку інформації в документах, пошук самих документів, добуття метаданих з документів, пошуку тексту, зображень, відео та звуку у локальних реляційних базах даних, у гіпертекстових базах даних таких, як Інтернет та локальні інтранет. Інформаційний пошук — велика міждисциплінарна область науки, яка стоїть на перетині когнітивної психології, інформатики, інформаційного дизайну, лінгвістики, семіотики, бібліотечної справи, та статистики. Вперше виділив як міждисциплінарну галузь відомий угорський дослідник Золтон Жулен у 1989 році .
Автоматичні системи інформаційного пошуку використовують для зменшення так званого «інформаційного перевантаження». Багато університетів та публічних бібліотек використовують системи ІП для полегшення доступу до книжок, журналів та інших документів. Найвідомішим прикладом систем ІП можна назвати пошукові системи в Інтернеті.
Об'єктом інформаційного пошуку є текстова інформація, зображення, аудіо, відео інформація.
Проблематика
З інформаційним пошуком змикаються проблеми:
- розсилки інформації (information routing);
- сортування інформації (information filtering);
- упорядкування (класифікація) інформації (information categorization);
- відбір інформації (information extraction).
Для інформаційного пошуку розробляють:
- алгоритми інформаційного пошуку (retrieval algorithms);
- підходи інформаційного пошуку(retrieval approaches);
- стратегії інформаційного пошуку (retrieval strategies).
Для його здійснення створюють:
- методи інформаційного пошуку (retrieval utilities);
- засоби інформаційного пошуку (information retrieval systems);
- комп'ютерні пошукові програми (search engines).
До проблем інформаційного пошуку належать питання:
- представлення даних, інформації, знань (data, information, knowledge);
- представлення інформації в сучасних інформаційних сховищах (representation of information);
- багатомовний інформаційний пошук (cross-language information retrieval);
- одночасний інформаційний пошук (parallel information retrieval);
- розподілений інформаційний пошук (distributed information retrieval);
- суспільний інформаційний пошук (social information retrieval)
Напрям інформаційний пошук відносять до проблем:
- застосовної (прикладної) лінгвістики (applied linguistics);
- обробки природної мови (natural language processing);
Завдання
Завданням інформаційного пошуку є знаходження відповідних (до пошукового запиту) інформаційних об'єктів, або документів серед доступного для пошуку матеріалу.
Завдання для інформаційного пошуку задається у вигляді інформаційного запиту (query), який може містити слова, фрази чи речення або комбінацію їх. Переважна більшість пошукових систем орієнтована на роботу з пошуковими термінами — словами або словосполученнями, які пошукова система розпізнає як одне ціле.
Для здійснення інформаційного пошуку потрібно мати збірку інформаційних об'єктів (бібліотека, комп'ютерні файли) і систему (алгоритм або програму) яка здійснює пошук. Для здійснення інформаційного пошуку користувач (людина або інформаційна система) формує інформаційний запит (information query). Результатом пошукової роботи є список документів який укладається згідно з певним принципом. Такий список називають впорядкованим (ranked list, ranked results).
Пошукова система переглядає всі доступні інформаційні одиниці (документи) зі збірки і відбирає документи відповідні до інформаційного запиту. Оскільки реальні пошукові системи знаходять не всі відповідні документи, говорять про точність пошукових систем (system accuracy). Результатом роботи пошукової системи є список відібраних документів (retrieved documents list), серед яких є відповідні до запиту документи (relevant documents). Для ідеальної пошукової системи список відібраних документів та відповідних документів повинні збігатися. В реальних пошукових системах в списках відібраних документів знаходяться і невідповідні до запиту документи. Тому говорять про ефективність пошукових систем.
Ефективність
Ефективність пошукових систем оцінюється двома параметрами: пошукова відповідність (precision) та пошукова якість (recall).
Пошукова відповідність визначає частку відповідних документів серед відібраних на запит. Пошукова відповідність визначає якість отриманого результату інформаційного пошуку. Пошукова якість визначає частку отриманих системою відповідних до запиту документів серед загального числа відповідних до запиту документів у збірці. Загальне число відповідних до запиту документів завжди є невідомим і може бути встановлене лише при повному перегляді збірки людиною.
Крім того роботу пошукових систем оцінюють швидкодією — часом, за який отримують список відповідних до запиту документів.
Інформаційний пошук — велика міждисциплінарна область науки, яка стоїть на перетині когнітивної психології, інформатики, інформаційного дизайну, лінгвістики, семіотики, бібліотечної справи, та статистики.
Автоматичні системи інформаційного пошуку використовують для зменшення так званого «інформаційного перевантаження». Багато університетів та публічних бібліотек використовують системи ІП для полегшення доступу до книжок, журналів та інших документів. Найвідомішим прикладом систем ІП можна назвати пошукові системи в Інтернеті.
Стратегії інформаційного пошуку
Стратегії інформаційного пошуку визначають ступінь подібності документів, що розглядаються, до пошукового запиту. Ступінь подібності визначається згідно з робочою гіпотезою: чим частіше пошуковий термін зустрічається в документі, тим «відповіднішим» є цей документ до пошукового запиту.
Стратегії інформаційного пошуку розробляються не тільки для визначення відповідності, але і для вирішення проблем, які пов'язані з неоднозначністю мови — один і той самий термін може позначати різні концепти (ключ в механіці означає зовсім не те, що в шифруванні), один і той же концепт може позначатись різними термінами (обласний центр Львівської області має назву Львів і Місто Лева).
Стратегія інформаційного пошуку це алгоритм, який, переглядаючи набір документів (Д1, …, Дn), встановлює їх відповідність до пошукового запиту (ПЗ). Оскільки пошуковий термін зустрічається в документах різну кількість раз, можна говорити про різну ступінь відповідності до пошукового запиту. Цей алгоритм обчислює коефіцієнт відповідності (similarity coefficient) (КВ) для кожного документу КВ(ПЗ, Дi), де 1 ≤ i ≤ n.
Існують такі стратегії інформаційного пошуку:
- з використанням векторно-просторового представлення (vector space model);
- пошук імовірності появи пошукового терміна в документі (probabilistic retrieval);
- з побудовою мовної моделі для кожного документа (language models);
- з побудовою мережі припущень, яка використовується для встановлення відповідності документу до пошукового запиту (inference network);
- з Булевим індексуванням, коли кожному пошуковому терміну присвоюється своя «вага», що потім враховується при побудові впорядкованих списків документів (Boolean indexing);
- з використанням не проявленого семантичного індексування (latent semantic indexing);
- з побудовою нейромереж (neural networks);
- з використанням продуктивних алгоритмів, коли початковий пошуковий запит «еволюційно» видозмінюється (genetic algorithms);
- з використанням нечітких множин, коли документу ставиться у відповідність нечітка множина (fuzzy set retrieval).
Інформаційний пошук за допомогою векторно-просторового представлення
Пошуковий запит та документи представляються у вигляді просторових векторів Пошукова система відбирає документи, просторові вектори яких подібні до просторового вектора пошукового запиту.
В основі векторно-просторового представлення документу лежить припущення, що зміст документу передається словами, що в ньому знаходяться. Просторово-векторне представлення будується для пошукового запиту і для кожного документу. Просторово-векторне представлення документу — це вектор у n-мірному просторі. N-мірний простір це простір, кожний вимір якого відповідає пошуковому терміну. Координати кінця вектора чисельно визначаються тим, скільки разів пошуковий термін зустрічається в документі. Тобто кожний компонент вектора відповідає числу появи відповідного терміну в документі.
Пошукова система обчислює коефіцієнт відповідності (КВ) просторово векторного представлення документу до просторово-векторного представлення пошукового запиту. Фактично пошукова система обчислює кут між цими векторами. Найвідповіднішими є документи, просторово-векторне представлення яких спрямоване туди ж куди і в представлення пошукового запиту[1].
Імовірнісний пошук
Коефіцієнт відповідності документа пошуковому запитові визначається на основі імовірності того, що документ є відповідним пошуковому запитові. Присутність чи відсутність пошукового терміну в документі використовується для визначення імовірності того, що документ відповідає інформаційному запитові.
Визначення імовірності базується на попередніх статистичних даних, про те, наскільки імовірно, що документ який містить пошуковий термін A, відповідатиме пошуковому запитові, що містить термін A. Припускаючи, що пошукові терміни в пошуковому запиті є незалежні, можна обчислювати таку імовірність для кожного пошукового терміну з пошукового запиту. Загальна імовірність відповідності документу обчислюється як добуток ймовірностей відповідності для кожного терміну.
Незалежність пошукових термінів в пошуковому запиті рідко спостерігається в дійсності, тому обчислення сумарної відповідності значно ускладнюється, що збільшує час інформаційного пошуку. Крім того, необхідно мати попередні дані про входження термінів у відповідні до запиту документи а також і у невідповідні до запиту документи[2].
Пошук з використанням мовних моделей
Мовні моделі використовуються для передбачення появи того чи іншого слова у тексті.
В інформаційному пошуку використовуються статистичні мовні моделі для передбачення чи з'явиться потрібне слово (пошуковий термін) в документі.
Для кожного документу зі збірки обчислюється імовірність появи в документі пошукових термінів. Згідно з цим документом упорядковуються у пошуковому списку. Ще один підхід пропонує побудову імовірнісної моделі пошуковго запиту. Тобто будується імовірнісна модель появи тих чи інших пошукових термінів у запиті Далі будується імовірнісна модель запиту як сукупності незалежних подій, де кожна подія — це поява того чи іншого терміну у пошуковому запиті. В цій моделі ми можемо врахувати навіть імовірності непояви певних термінів[3].
Алгоритми прийняття рішень
Алгоритми прийняття рішень використовуються для визначення імовірності того, що документ буде відповідним до пошукового запиту. Застосовуються для доповнення до ймовірного пошуку, щоб отримати додаткові докази того, що документ може відповідати пошуковому запиту. Метод засновано на використанні відомих залежностей для побудови невідомих. Це дозволяє кардинально знизити обсяг обчислень, які потрібно виконати задля визначення ймовірності події[4].
Розширений булевий пошук
Звичайний Булевий пошук не має нічого спільного зі ступенем відповідності документу до пошукового запиту, і, відповідно, з упорядкуванням документів згідно з цією відповідністю. Документи або задовільняють інформаційний запит, або ні. Ті документи, що задовільняють булевий запит попадають у список по черзі. Ідея розширеного Булевого пошуку полягає у створенні можливостей для визначення ступеня відповідності документів пошуковому запитові. Це досягається з допомогою присвоєння ваги пошуковим термінам. Вага термінів враховується при побудові списку відповідності документів до інформаційного запиту.[5]
Пошук з прихованим семантичним індексуванням
Поява термінів в документі представляється за допомогою матриці термін-документ. Матриця приводиться за допомогою розкладу за виродженими матрицями для того, щоб відділити «шум», так, що два семантично спільні документи розташовані поруч в багатомірному просторі[6].
Пошук з використанням нейромереж
Вузли нейронної мережі «активуються» пошуковим запитом. Сила кожного зв'язку нейронної мережі передається документу і використовується для обчислення коефіцієнта відповідності документа до пошуковго запиту. Для цього зв'язкам присвоюється вага згідно з наперед визначеною відповідністю чи невідповідністю документів[7].
Пошук з використанням алгоритмів розвитку
Шляхом еволюції можна змінити початковий пошуковий запит. Початковий запит використовується з рівноправними термінами, або з термінами, що мають різну вагу. Згенерований пошуковий запит залишається, якщо він охоплює відомі відпоівдні до початкового запиту документи, якщо ж ні — відкидається[8].
Пошук з використанням нечітких множин
Документ перетворюється в нечітку множину (це множина, що містить не тільки сам елемент але і число, що показує ступінь приналежності елемента до множини). Далі для кожного документу з проведеного попередньо Булевого пошуку додається інформація отримана з операцій об'єднання, перетину, комплементарності нечітких множин, яка говорить про ступінь відповідності кожного документу до пошукового запиту. Ступінь відповідності використовується як коефіцієнт відповідності.
Вимоги до результатів пошуку
Результати інформаційного пошуку повинні відповідати таким вимогам:
- релевантність (від англ. Relevant) — стосується результатів роботи пошукової системи і експертної системи; ступінь відповідності запиту і знайденого, тобто доречність результату. Одне з найбільш близьких поняттю «релевантності» — «адекватність», тобто оцінка ступеня відповідності, практичної та соціальної застосовності результату варіантів вирішення завдання.
- пертінентність (від англ. Pertinent) — співвідношення обсягу корисної інформації до загального обсягу отриманої інформації.
Примітки
- G. Salton, A. Wong, and C. S. Yang (1975), A vector space model for automatic indexing «Communications of the ACM», vol. 18, nr. 11, pages 613—620. «(The article in which the vector space model was first presented)»
- Maron, M. E., & Kuhns, J. L. (1960). On relevance, probabilistic indexing and information retrieval. Journal of the ACM, 7(3), 216—244.
- Ponte, Jay M., and Croft, W. Bruce. A language modeling approach to information retrieval. In Proc. SIGIR, 1998.- pp. 275—281. ACM Press.
- Greiff Warren R., Croft B., Turtle H. PIC matrices: a computationally tractable class of probabilistic query operators. ACM Transactions on Information Systems (TOIS) Volume 17 , Issue 4 (October 1999) p. 367—405
- Fox Edward A., Salton G., Wu H. Extended Boolean information retrieval. Commun. of the ACM, Volume 26 , Issue 11 (November 1983) р. 1022—1036
- Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer, Richard Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science (1990)
- Kwok K. L. A neural network for probabilistic information retrieval. ACM SIGIR Forum, Volume 23 , (червень 1989)
- Hsinchun Chen Machine learning for information retrieval: Neural networks, symbolic learning, and genetic algorithms. Journal of the American Society for Information Science. Volume 46 Issue 3, ст. 194—216
Література
- F. Crestani and G. Pasi. Soft Information Retrieval: Applications of Fuzzy Set Theory and Neural Networks. in «Neuro-fuzzy Techniques for Intelligent Information Systems», N.Kasabov and Robert Kozma Editors, Physica-Verlag, Springer-Verlag Group , 287—313, 1999.
- Ланде Д. В., Снарский А. А., Безсуднов И. В. Интернетика: Навигация в сложных сетях: модели и алгоритмы. — M.: Либроком (Editorial URSS), 2009. — 264 с. ISBN 978-5-397-00497-8.
- Schütze, Hinrich; Christopher D. Manning; Raghavan, Prabhakar (2008). Introduction to information retrieval. Cambridge, UK: Cambridge University Press. ISBN 0-521-86571-9.