Векторна модель

Векторна модель (англ. vector space model) — в інформаційному пошуку алгебраїчне представлення колекції документів векторами одного спільного для всієї колекції векторного простору.

Векторна модель є основою для вирішення багатьох завдань інформаційного пошуку, таких як: пошук документа за запитом, класифікація документів, кластеризація документів.

Визначення

Документ у векторній моделі розглядається як невпорядкована множина термів. Термами в інформаційному пошуку називають слова, з яких складається текст, а також такі елементи тексту, як, наприклад, 2010, II-5 або Тянь-Шань.

Різними способами можна визначити вагу терма в документі — «важливість» слова для ідентифікації цього тексту. Наприклад, можна просто підрахувати кількість вживань терма в документі, так звану частоту терма, — чим частіше слово зустрічається в документі, тим більша у нього буде вага. Якщо терм не зустрічається в документі, то його вага в цьому документі дорівнює нулю.

Всі терми, які трапляються в документах оброблюваної колекції, можна впорядкувати. Якщо тепер для деякого документа виписати по порядку ваги всіх термів, включаючи ті, яких немає в цьому документі, вийде вектор, який і буде представленням цього документа у векторному просторі. Розмірність цього вектора, як і розмірність простору, дорівнює кількості різних термів у всій колекції, і є однаковою для всіх документів.

Більш формально

$d_{j}=(w_{1,j},w_{2,j},\dotsc ,w_{t,j})$

$q=(w_{1,q},w_{2,q},\dotsc ,w_{n,q})$

де d_j — векторне уявлення j-го документа, w_ij — вага i-го терма в j-му документі, n — загальна кількість різних термів у всіх документах колекції.

Маючи таке подання для всіх документів, можна, наприклад, знаходити відстань між точками простору і тим самим вирішувати задачу подоби документів — чим ближче розташовані точки, тим більше схожі відповідні документи. У разі пошуку документа за запитом, запит теж представляється як вектор того ж простору — і можна обчислювати відповідність документів запиту.

Застосування

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

$\cos {\theta }={\frac {\mathbf {d_{2}} \cdot \mathbf {q} }{\left\|\mathbf {d_{2}} \right\|\left\|\mathbf {q} \right\|}}$

Де $\mathbf {d_{2}} \cdot \mathbf {q}$ — перетин (тобто скалярний добуток) документу та вектори запиту, $\left\|\mathbf {d_{2}} \right\|$ — нормаль вектора d₂, к — нормаль вектора q. Нормаль вектора обчислюється наступною формулою:

$\left\|\mathbf {q} \right\|={\sqrt {\sum _{i=1}^{n}q_{i}^{2}}}$

Оскільки всі вектори, що розглядуються цією моделлю поелементно невід'ємні, нульовий косинус означає, що запит і вектор документа ортогональні і не збігаються (тобто в документі, що розглядають, не існує терму запит). Подивіться статтю косинусний коефіцієнт для отримання додаткової інформації.

Міра TF-IDF

У класичній векторній моделі, запропонованій Салтоном, Вонгом та Янгом, певні для слова міри в векторах документа — це продукти локальних та глобальних параметрів. Модель, відома як tf-idf модель. Маса вектора для документу d:

$\mathbf {v} _{d}=[w_{1,d},w_{2,d},\ldots ,w_{N,d}]^{T}$, де

$w_{t,d}=\mathrm {tf} _{t,d}\cdot \log {\frac {|D|}{|\{d'\in D\,|\,t\in d'\}|}}$

та

• $\mathrm {tf} _{t,d}$ це частота терміну терму t у документі d (локальний параметр)
• $\log {\frac {|D|}{|\{d'\in D\,|\,t\in d'\}|}}$ це зворотна частота документу(глобальний параметр). $|D|$ — це загальна кількість документів у наборі документів; $|\{d'\in D\,|\,t\in d'\}|$ — це кількість документів, що містять терм t.

З використанням косинусу, подібність між документом d_j та запитом q можна обчислити так:

$\mathrm {sim} (d_{j},q)={\frac {\mathbf {d_{j}} \cdot \mathbf {q} }{\left\|\mathbf {d_{j}} \right\|\left\|\mathbf {q} \right\|}}={\frac {\sum _{i=1}^{N}w_{i,j}w_{i,q}}{{\sqrt {\sum _{i=1}^{N}w_{i,j}^{2}}}{\sqrt {\sum _{i=1}^{N}w_{i,q}^{2}}}}}$

Переваги

Векторна модель має наступні переваги над моделлю Standard Boolean:

1. Проста модель, заснована на лінійній алгебрі
2. Міра терміну не двійкова(бінарна)
3. Дозволяє обчислювати нескінчену кількість подібностей між запитами та документами
4. Дозволяє оцінювати документи згідно з їхньою можливою релевантністю
5. Дозволяє часткові збіги

Обмеження

Векторна модель має наступні обмеження:

1. Великі документи погано представлені, тому що вони мають недостатньо змінних подібності(маленький скалярний добуток та велика розмірність)
2. Ключові слова у пошуку повинні точно відповідати термінам документа; підрядки терма можуть привести до «похибки першого роду»
3. Семантична чутливість; документи зі схожим контекстом, але різним словником термів не пов'язані, видаючи у результаті «похибку другого роду»
4. Порядок, у якому терми з'являються у документі, втрачається у векторному зображенні
5. Теоретично передбачається, що терми статистично незалежні
6. Вимірювання інтуїтивне, та не дуже формальне

Хоча багато з цих складностей можна подолати за допомогою інтеграції різних інструментів, включаючи математичні методи, такі як сингулярний розклад матриці та лексичні бази даних, такі як WordNet.

Моделі, засновані на векторній моделі та доповнюють її

Моделі, що засновані на векторній моделі та ті, що її доповнюють:

• Узагальнена векторна модель
• Латентно-семантичний аналіз
• Дискримінація термів
• Класифікація Роше
• Випадкове індексування

Програми, що реалізовують векторну модель

Наступні пакети програм можуть зацікавити бажаючих поекспериментувати з векторною моделлю та реалізувати пошукові служби, засновані на них.

Безкоштовні загальнодоступні програми

• Apache Lucene. Apache Lucene — високо-продуктивна бібліотека для повнотекстного пошуку, повністю написана на Java.
• Gensim — платформа Python+NumPy для векторного моделювання. Вона містить поетапні алгоритми для Tf-idf, латентно-семантичного індексування, рандомних проектувань та латентного розміщення Дирихле.
• Weka. Weka — популярний пакет збору даних для Java, що включає моделі WordVectors та Bag of words.

Література

• Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze An Introduction to Information Retrieval [Архівовано 9 грудня 2012 у Wayback Machine.] Draft. Online edition. Cambridge University Press. — 2009. — 544 pp.
• Daniel Jurafsky, James H. MartinSpeech and Language Processing. An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Second Edition. Pearson Education International. — 2009. — 1024 pp.
• 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. (Article in which a vector space model was presented)
• David Dubin (2004), The Most Influential Paper Gerard Salton Never Wrote (Explains the history of the Vector Space Model and the non-existence of a frequently cited publication)
• Description of the vector space model
• Description of the classic vector space model by Dr E. Garcia [Архівовано 12 серпня 2006 у Wayback Machine.]
• Relationship of vector space search to the «k-Nearest Neighbor» search [Архівовано 5 березня 2016 у Wayback Machine.]

Посилання

• Apache Lucene — програмна реалізація інформаційного пошуку, заснована на векторній моделі.