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

Материал из MachineLearning.

(Различия между версиями)

Sidious (Обсуждение | вклад)
(Новая: <p>Главная идея векторной модели семантики (vector space model, VSM) – это представление каждого документа колле...)
К следующему изменению →

Версия 09:33, 21 марта 2011

Главная идея векторной модели семантики (vector space model, VSM) – это представление каждого документа коллекции в качестве точки в многомерном пространстве (вектора в векторном пространстве). Близко лежащие друг к другу точки соответствуют семантически схожим документам. В поисковых системах эта идея реализуется следующим образом. Запрос пользователя рассматривается в качестве вектора (как псевдодокумент). Затем, документы сортируются в порядке возрастания расстояния до псевдодокумента и выдаются пользователю.

Векторная модель основана на гипотезе о статистической семантике (statistical semantics hypothesis): статистические зависимости употребления слов человеком могут быть использованы для нахождения заложенного в них смысла.

Содержание

1 Сходство документов: матрица термин-документ
2 Сходство слов: матрица слово-контекст
3 Сходство отношений: матрица пара-модель
4 Сходство
5 Другие векторные модели
6 Лингвистическая обработка для векторной модели
7 Математическая обработка для векторной модели
8 Литература

Сходство документов: матрица термин-документ

При наличии большой коллекции документов и, следовательно, большого числа соответствующих им векторов удобно сгруппировать последние в матрицу. Каждая её строка определяет отдельный термин, а каждый столбец соответствуют некоторому документу.

Пусть имеется документ, который содержит некоторое множество терминов $\{a, a, b, c, c, c\}$ (их порядок в наборе не важен). Тогда ему соответствует вектор ${\b x} = (2, 1, 3)$ , где первый элемент соответствует числу вхождений в документ термина $a$ , второй – $b$ , третий – $c$ .

Информационный поиск с использованием матрицы термин-документ (term–document matrix) основывается на следующей гипотезе: оценивание релевантности документа запросу можно производить путем представления документа и запроса в виде набора слов (bag of words). Иными словами, по частоте вхождения слов в документ мы можем судить о его релевантности запросу.

Пусть ${\b X}$ – матрица термин-документ. Предположим, что коллекция состоит из $n$ документов и $m$ уникальных терминов. Матрица ${\b X}$ будет иметь $m$ строк и $n$ столбцов. Обозначим через $w_i$ – $i$ -ый термин в словаре, $d_j$ – $j$ -ый документ в коллекции. Тогда каждый элемент $x_{ij}$ матрицы ${\b X}$ – это количество вхождений термина $w_i$ в документ $d_j$ .

Как правило, большинство значений элементов матрицы ${\b X}$ равны 0 (матрица является разреженной). Это связано с тем, что документы содержит лишь малую долю терминов из всего словаря.

Сходство слов: матрица слово-контекст

Матрица термин-документ используется для нахождения сходства среди отдельных документов. Иногда задача может заключаться в рассмотрении близости тех или иных слов в рамках не всего документа, а каких-либо его частей. Матрица слово-контекст (word–context matrix) отражает частоту вхождения терминов в некоторую фразу, предложение, параграф или главу.

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

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

Сходство отношений: матрица пара-модель

В матрице пара-модель (pair–pattern matrix) каждая строка описывает определенную пару слов (такие как каменщик: камень или столяр: дерево), а каждый столбец соответствует модели, определяющей отношение между парами слов (например, $X$ работает с $Y$ ).

Важное место здесь занимает расширенная гипотеза распределения, согласно которой, отношения, происходящие вместе со схожими парами слов, стремятся иметь близкий смысл. Например, отношение « $X$ решил (что?) $Y$ » и « $Y$ решена (кем?) $X$ » имеет тенденцию употребляться со схожими парами $X: Y$ . В связи с этим, можно предположить, что приведенные отношения имеют схожий смысл.

Согласно гипотезе о скрытых связях, пары слов, которые встречаются в похожих моделях, стремятся иметь близкую семантическую зависимость [1]. Близость векторов-строк матрицы пара-модель определяет степень сходства отношений между словами.

Сходство

Матрицы пара-модель пригодны для измерения сходства семантических отношений между парами слов. В этом случае речь идет о реляционном сходстве (relational similarity). С другой стороны, матрицы слово-контекст используют для измерения атрибутивного сходства (attributional similarity).

Сходство атрибутов между двумя словами $a$ и $b$ , $sim_a(a, b)\in \mathbb{R}$ , зависит от степени соответствия свойств $a$ и $b$ . Чем больше соответствие, тем выше атрибутивное сходство. Реляционное сходство между двумя парами слов $a:b$ и $c:d$ , $sim_r(a: b, c: d)$ , зависит от степени соответствия между отношениями $a: b$ и $c: d$ . Чем она выше, тем сильнее реляционное сходство.

Рассмотрим пример. Между словами собака и волк имеется сравнительно высокая степень атрибутивного сходства, в то время между парами слов собака:лай и кот:мяуканье существует реляционное сходство.

Другие векторные модели

Традиционные векторные модели получили своё дальнейшее развитие. Например, можно составить матрицу тройка-модель, устанавливающую зависимость между отношениями тройки слов (а не пары, как в матрице пара-модель).

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

Лингвистическая обработка для векторной модели

Допустим, имеется большая коллекция текстов на естественном языке. Прежде, чем сформировать матрицы термин-документ, слово-контекст или пара-модель, необходимо провести некоторую предобработку текста. Можно выделить три класса предобработки текста. Во-первых, нам необходимо его разметить. Это связано в первую очередь с тем, что мы должны решить, что может составлять термины и как их извлечь из «сырого» текста. Во-вторых, текст нуждается в нормализации: приведении различных слов к некоторой начальной форме (например, слова деревья, деревом, деревьями необходимо нормализовать в дерево). И, в-третьих, текст необходимо комментировать (annotate). Данная процедура подразумевает создание для каждого слова метки, указывающей на принадлежность его к определенной части речи.

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

Разметка текста

Разметка текста кажется на первый взгляд довольно простой задачей. В действительности это не всегда так.

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

Нормализация текста

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

Во-первых, необходимо привести все символы к единому регистру. Однако делать это следует с осторожностью, так как иногда изменение регистра может изменить и смысл слова. Для примера можно рассмотреть аббревиатуру РАН. Если все символы написаны в верхнем регистре, то слово обозначает Российскую Академию Наук. В нижнем регистре получается слово ран (родительный падеж от раны). Из примера видно, что при неудачной смене регистра может изменить и смысл слова.

С морфологической точки зрения, одно и то же слово может принимать различные формы. Например, глаголы в русском языке могут изменяться по временам и числам (а в прошедшем времени ещё и по родам). Стемминг (стемматизация) – процесс поиска слова во всех его морфологических формах с последующим выделением основы (или корня). Благодаря тому, что в английском языке аффиксы сравнительно просты и постоянны, алгоритмы стемминга, основанные на эвристике, работают довольно хорошо.

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

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

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

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

Комментирование

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

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

Особенно актуально комментирование для языков, где основным способом словообразования является конверсия. Например, в английском язык из существительного fly (полет) таким образом получается глагол fly (лететь). Написание этих слов совпадает, однако они могут нести разный смысл. Результат информационного поиска только по глаголу будет иметь более высокую точность, однако в некоторых документах и существительное способно нести в себе требуемый смысл, но система не сможет их найти, вследствие чего полнота поиска падает.

Большую пользу для информационного поиска приносит результат комментирования запросов с синтаксической и семантической информацией. Синтаксическое комментирование включает сегментацию запросов и разметку частей речи. Это используется для устранения неоднозначности в сокращениях и поиск ассоциаций среди ключевых слов.

Комментирование также полезно для измерения семантической схожести слов и понятий (для моделей, основанных на матрице слово-контекст). В работе [2] представлен алгоритм, который обнаруживает близкий смысл слов путем кластеризации векторов-строк матрицы слово-контекст.

Математическая обработка для векторной модели

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

Построение частотной матрицы

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

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

Взвешивание элементов

Идея заключается в том, что чем неожиданнее является событие, тем больший интерес оно представляет. Самый популярный способ взвешивания для модели термин-документ – это tf-idf (term frequency - inverse document frequency). Согласно этому подходу, термин имеет большой вес, если он в некотором документе встречается часто, а в других – редко. Рассчитывается вес по следующей формуле:

$w_{ki}=\frac{(1 + log(N_{ik})\cdot log(\frac{|D|}{N_k}))}{\sqrt{\sum_{s\ne k}(log(N_{is})+1)^2}}$

где $N_{ik}$ – количество появлений $k$ -ого термина в $i$ -ом документе, $N_k$ – количество появлений $k$ -ого термина во всех документах, $|D|$ – количество документов в коллекции.

Альтернативный способ присваивания весов – это метод PMI (Pointwise Mutual Information), который хорошо работает как для матриц слово-контекст, так и для термин-документ. Positive PMI – это один вариантов PMI, в котором все отрицательные веса заменяются нулем. Метод PPMI при этом подходит и для матриц пара-модель.

Пусть ${\b F}$ – это матрица частот слово-контекст с $n_r$ – строками и $n_c$ – строками. $i$ -ая строка в ${\b F}$ – это вектор ${\b f}_{i:}$ , соответствующий слову $w_i$ , и $j$ -ый столбец той же матрицы – вектор ${\b f}_{:j}$ , определяемый контекстом $c_j$ . Матрица ${\b X}$ – это результат работы метода PPMI c матрицей ${\b F}$ . Заметим, что $dim({\b X}) = dim({\b F})$ . Расчет элементов $x_{ij}$ результирующей матрицы происходит следующим образом:

$p_{kl}=\frac{f_{kl}}{\sum_{i=1}^{n_r}\sum_{j=1}^{n_c}f_{ij}}$ ,

$p_{k*}=\frac{\sum_{j=1}^{n_c}f_{kj}}{\sum_{i=1}^{n_r}\sum_{j=1}^{n_c}f_{ij}}$ ,

$p_{*l}=\frac{\sum_{i=1}^{n_r}f_{il}}{\sum_{i=1}^{n_r}\sum_{j=1}^{n_c}f_{ij}}$ ,

$pmi_{ij}=log(\frac{p_{ij}}{p_{i*}p_{*j}})$ ,

$x_{ij} =\begin{cases} pmi_{ij} & \mbox{ } \mbox{ pmi_{ij} > 0}\\ 0, & \mbox{ } \mbox{ otherwise }\\ \end{cases}$

В данном случае $p_{ij}$ – это ожидаемая вероятность того, что слово $w_i$ окажется в контексте $c_j$ , $p_{i*}$ – ожидаемая вероятность слова $w_i$ , и $p_{*j}$ – вероятность появления контекста $c_j$ . Если $w_i$ и $c_j$ статистически независимы, то $p_{i*}p_{*j} = p_{ij}$ , и тогда $pmi_{ij}$ обратится в ноль. С другой стороны, если между конкретным контекстом и словом есть сильная семантическая связь, то следует ожидать, что вероятность $p_{ij}$ будет выше, чем $p_{i*}p_{*j}$ и в этом случае коэффициент $pmi_{ij}$ примет положительное значение. Это следует из приведенной выше гипотезы распределения. Если некоторое слово $w_i$ совершенно не связано с контекстом $c_j$ , то $pmi_{ij}$ окажется отрицательным. В методе PPMI представляющие интерес семантические связи отражаются высоким значением элемента $x_{ij}$ , иначе же получается нулевое значение.

Самый известный недостаток метода PMI в том, что он склонен давать высокие веса нечастым событиям. При этом если некоторое слово встречается только в определенном контексте, то $p_{i*} = p_{*j} = p_{ij}$ . Легко проверить, что с уменьшением вероятности появления слова $w_i$ значение $pmi_{ij}$ возрастает. Одно из решений данной проблемы заключается в введении некоторого штрафующего коэффициента:

$\theta_{ij} = \frac{f_{ij}}{f_{ij}+1}\cdot \frac{min(\sum_{k=1}^{n_r}f_{kj},\sum_{k=1}^{n_c}f_{ik})}{min(\sum_{k=1}^{n_r}f_{kj},\sum_{k=1}^{n_c}f_{ik})+1}$ ,

$newpmi_{ij} = \theta_{ij} \cdot pmi_{ij}$ .

Сглаживание матрицы

Самым простым способом улучшения выполнения информационного поиска является ограничение числа векторных компонент. Отбираются только слова, которые в наибольшей степени встречаются в контексте. Следует отметить, что перед применением этого способа необходимо очистить текст от стоп-слов, которые несут в себе мало полезной информации.

Нахождение сходства между парами всех векторов – это вычислительно сложная задача. Поэтому оставляют наиболее значимые факторы.

Рассмотрим способ, основанный на сингулярном разложении, который позволяет представить ${\b X}$ в виде произведения матриц ${\b U \Sigma V}^T$ . Пусть $r = rank{\b X}$ и ${\b \Sigma}_k$ (где $k < r$ ) – диагональная матрица, сформированная из первых $k$ сингулярных чисел, ${\b U}_k$ и ${\b V}_k$ – матрицы, созданные из соответствующих столбцов ${\b U}$ и ${\b V}$ . Тогда ${\b U}_k{\b \Sigma}_k{{\b V}_{k}}^T$ – матрица ранга $k$ , которая лучшим образом аппроксимирует оригинальную матрицу ${\b X}$ . Это означает, что для матрицы $\hat{{\b X}} = {\b U}_k{\b \Sigma}_k{{\b V}_{k}}^T$ минимизируется выражение $||\hat{{\b X}}-{{\b X}}||_F$ , где $||\cdot||_F$ – норма Фробениуса.

Данный метод может быть использован для поиска скрытого смысла. Предположим, что ${\b X}$ – это матрица слово-контекст. $\hat{{\b X}}$ - это линейное отображение между словами и контекстами меньшего ранга, чем ${\b X}$ . При понижении ранга матрицы $(k < r)$ остаются только самые «сильные» соответствия.

Подобное преобразование также приводит к снижению уровня шума, степени разреженности матрицы ${\b X}$ .

Сравнивание векторов

Самый популярный способ измерения схожести двух векторов матрицы частот – это нахождения косинуса угла между ними. Пусть ${\b x}$ и ${\b y}$ – два вектора размерности $n$ .

Другой способ сравнения основан на нахождении расстояния между векторами. Тогда схожесть векторов равна:

$sim({\b x}, {\b y}) = 1/dist({\b x}, {\b y})$ .

Иногда схожесть находят и по такой формуле:

$sim({\b x}, {\b y}) = 1-dist({\b x}, {\b y})$ .

Идея заключает в том, что чем больше расстояние между векторами, тем меньше они похожи друг на друга. Часто в качестве $dist({\b x}, {\b y})$ используют либо Евклидово расстояние, либо расстояние Манхэттена.

Машинное обучение

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

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

Помимо обучения с учителем и обучения без учителя векторная модель может быть так же использована и для задач, решаемых методом частичного обучения [3, 4].

Литература

Turney, P. D. (2008). The latent relation mapping engine: Algorithm and experiments. Journal of Artificial Intelligence Research, 33, 615–655.
Pantel, P., & Lin, D. (2002). Discovering word senses from text. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 613–619, Edmonton, Canada.
Ando, R. K., & Zhang, T. (2005). A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research, 6, 1817–1853.
Collobert, R., & Weston, J. (2008). A unified architecture for natural language processing: Deep neural networks with multitask learning. In Proceedings of the 25th International Conference on Machine Learning (ICML-08), pp. 160–167.
Turney, P.D., and Pantel, P. (2010), From frequency to meaning: Vector space models of semantics, Journal of Artificial Intelligence Research (JAIR), 37, 141-188.
Барсенгян, А.А., Анализ данных и процессов. – 3-е изд., перераб. и доп. – СПб.: БХВ-Петербург, 2009. – 512 с.: ил.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%B0%D1%8F_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D1%8C»

Категория: Обработка и анализ текстов