Математические модели текста

 

 

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

 

Колмогоров Андрей Николаевич (великий математик):

Математический метод всегда следует двум принципам:

  1. Обобщение (абстрагирование). Объекты изучения в математике — это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды.

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

Чтобы изучать с помощью математических методов лингвистические объекты (языки, тексты...) , необходимо:

  • выделить из объекта его свойства, которые представляются важными для изучения,

  • строго определить эти свойства.

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

 

 

 

Bag of words

 

Простейшая модель текста "мешок слов" (bag-of-words) представляет собой суммативное единство (не систему) составляющих текст слов.

Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова.

В модели текста "мешок слов" учитывается только количество вхождений конкретных слов в исходном тексте, при этом  игнорируются:

  • порядок слов в документе,

  • морфологические формы представления слов.

Модель текста "мешок слов" была предложена в 1975 году Дж. Солтоном, и в настоящее время является одной из самых распространённых в самых различных областях лингвистических исследований и сервисов, как правило, в качестве основы для более сложных, прежде всего "векторных моделей теста".

 

Мешок слов используется в "машинном обучении на основе текстов" в качестве одного из основных объектов изучения.

 

 

 

 

Bag of terms

 

Полезным обобщением формальной модели текста "мешок слов" (bag-of-words) может служить модель "мешок термов" (bag-of-terms).

Основной объект модели мешка термов — это терм, снабженное единственным атрибутом, частотой встречаемости в тексте.

Терм - символьное выражение объекта формальной модели (языка, системы)

Терм (формальное определение): символьное выражение: t(X1, X2, … , Xn), где t — имя терма, называемая функтор или «функциональная буква», а X1, X2, … , Xn — термы, структурированные или простейшие.

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

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

В модели  bag-of-terms, в качестве термов могут быть рассматриваемы любые символьные выражения текста, в том числе - знаки препинания.

 

 

 

Амфиболи́я

 

Пример амфиболии — фраза «Казнить нельзя помиловать», где смысл меняется на противоположный в зависимости от места паузы (определяемой на письме знаком запятой) после или перед словом «нельзя».

 

 

 

Частотная модель текста

 

Для каждого слова из набора модели "мешок слов" может указывается некоторый «вес».

Таким образом, модель текста представляет собой множество пар «слово — вес».

При этом веса могут присваиваться словам или основам слов.

Методы определения веса слов:

  • Бинарный метод (распространённое обозначение — BI, от binary). Определяется только наличие или отсутствие некоторых терминов в документе. Применяется для логического информационного поиска и автоматической рубрикации текстов методами нейросетевых классификаторов ART и SOM.

  • Количество вхождений (слов в документ). Предполагает несоразмерность оценки для текстов разной длины — больший вес будут получать более объемные тексты, так как в них больше слов;

  • Частота вхождения слова в документе (TF — term frequency). Частота вычисляется как отношение числа вхождения слова к общему количеству слов текста. При относительной простоте эта характеристика обеспечивает приемлемый результат для методов информационного поиска и классификации (предполагает несоразмерность оценки для текстов разной длины —  недооцениваются длинные документы, так как в них больше слов и средняя частота слов в тексте ниже).

  • Логарифм частоты вхождения слова (LOGTF). Вес входящего в текст документа определяется как 1+log(TF), где TF — частота термина. Использование логарифмической шкалы позволяет сделать модель более устойчивой к переоценке текстов разного объема.

  • Обратная частота документов (IDF — inverse document frequency). Параметр является инверсией частоты, с которой встречается термин в документах.

 

 

Вектор

 

Общее определение вектора: https://ru.wikipedia.org/wiki/Вектор_(математика)

 

Кортеж  — упорядоченный конечный набор длины n (где n∈N∪{0}), каждый из элементов которого fi принадлежит некоторому множеству F.

Элементы кортежа называются его компонентами, или координатами.

Элементы кортежа могут повторяться в нём любое число раз.

Многие математические объекты формально определяются как кортежи.

Точка в n-мерном пространстве действительных чисел определяется как кортеж длины n, составленный из элементов множества действительных чисел.

В некоторых языках программирования , кортеж — особый тип данных.
Кортеж является стандартным типом в платформе .NET.

 

Вектор —  кортеж однородных элементов (скаляров).

Совокупность векторов образует векторное пространство V над линейным пространством (полем) F.

Элементы V называются векторами, элементы F — скалярами.

 

В программировании, вектор, как правило, обозначается именем-идентификатором с квадратными скобками ( object[] ).

Перечень свойств вектора моделирует принятое в теории систем определение класса и состояния объекта.

Типы элементов вектора определяют класс объекта, а значения элементов — его состояние.

 

Векторное исчисление изучает:

  • свойства линейных операций с векторами (векторная алгебра): сложение, умножение векторов на число, различные произведения векторов — скалярное, псевдоскалярное, векторное, смешанное, двойное векторное и т. д.

  • геометрические свойства векторов и их совокупности (вектораная геометрия): коллинеарность, компланарность, свойства векторного базиса).

  • статические, стационарные и динамические векторные и скалярные поля (векторный анализ).

  • дифференциальные операторы (тензорный анализ) и др...

 

 

 

 

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

 

Векторная модель (vector space model) — представление текстов векторами из одного общего для всей коллекции текстов векторного пространства.

Векторная модель является основой решения задач информационного поиска:

  • поиск документа по запросу, 

  • классификация документов,

  • кластеризация документов и др...

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

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

Размерность этого вектора, как и размерность пространства, равна количеству различных термов во всей коллекции, и является одинаковой для всех текстов (документов) коллекции.

Формально:

dj = (w1j, w2j, …, wnj),

где dj — векторное представление j-го текста, wij — вес i-го терма в j-м документе, n — общее количество различных термов во всех документах коллекции.

 

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

В случае поиска документа по запросу, запрос тоже представляется как вектор того же пространства — и можно вычислять соответствие документов запросу.

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

 

 

 

Частотный словарь как векторная модель текста

 

 

Простейшей векторной моделью текста (vector space model) может служить построенный на основе модели "мешок слов" частотный словарь текста.

Частотный словарь может быть интерпретирован как простейшая векторная модель текста (элементы - кортежи из слов и параметра их частотности).

Частотный анализатор определяет для каждого слова vi из словарного пространства (системного словаря) V  его частоту вхождения  fi ≥ 0 в данный текст t=t1t2t3...tk.

Частотную характеристику f можно рассматривать как точку в пространстве признаков F, соответствующую тексту t.

Частотная характеристика это вектор  векторного пространства F.

Длина f=(f1,...fn) равна количеству слов в словаре V, каждая компонента fi это целое неотрицательное число:

Таким образом, на входе имеем текст t и словарь V, на выходе точку в пространстве признаков F.

 

Системный словарь V может быть задан "неявно" как совокупность всех слов моделируемого текста

 

 

 

Латентно-семантический анализ 

 

Модель "мешок слов" используется в латентно-семантическом анализе (ЛСА, LSA).

Латентно-семантический анализ (ЛСА, LSA) — метод обработки информации на естественном языке,  устанавливающий взаимосвязь между текстами (документами) и терминами в них встречающимися.

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

LSA запатентован в 1988г (Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum и Lynn Streeter).

LSA впервые применен для автоматического индексирования текстов, выявления семантической структуры текста и получения псевдодокументов.

LSA  для:

  • для поиска информации (индексация документов)  - области информационного поиска данный подход называют латентно-семантическим индексированием (ЛСИ).

  • классификации документов ,

  • представления баз знаний

  • построения построения когнитивных моделей (моделей понимания)

LSA представим (моделируем) трехслойной нейросетью:

  • множество слов (термов),

  • множество документов, соответствующих определенным ситуациям,

  • (латентный слой) множество узлов с различными весовыми коэффициентами, связывающих первый и второй слои.

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

Наиболее распространенный вариант LSA основан на использовании разложения диагональной матрицы по сингулярным значениям (SVD – Singular Value Decomposition). С помощью SVD-разложения любая матрица раскладывается во множество ортогональных матриц, линейная комбинация которых является достаточно точным приближением к исходной матриц

 

См: Латентно-семантический анализ: реализация (с картинкой)
http://habrahabr.ru/post/240209/
 

 

 

Подготовка к LSA

 

LSA обычно предваряется подготовительными операциями:

  • исключение стоп-символов (стоп-слов, стоп-термов).

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

  • исключение малочастотных термов (встречающихся в единственном экземпляре). Эта операция сильно упрощает математические вычисления.

 

 

Стоп-символы

 

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

Частотные стоп-слова русского языка:
 

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


Фильтруются также цифры, отдельные буквы и знаки препинания.

 

 

 

 

Нормализация

 

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

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

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

Нормализация текста не использует стемминг, поэтому она лишена недостатков потери релевантности из-за особенностей русского словоизменения.

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

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

 

См. "Томита парсер нормализация интерпретация в Яндексе"

 

 

 

Stemming

 

Стемминг — процесс нахождения основы слова для заданного исходного слова (является частью процесса нормализации текста).

Основа слова необязательно совпадает с морфологическим корнем слова.

В области компьютерных наук первая публикация по стеммингу датируется 1968 годом.

Стемминг применяется в поисковых системах для расширения поискового запроса пользователя.

Конкретный способ решения задачи поиска основы слов называется алгоритм стемминга, а конкретная реализация — стеммер.

Стемминг важен:

  • при небольшом наборе текстов

  • для русского языка (как флективного).

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

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

Для стемминга популярен алгоритм Портера:

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

Алгоритм состоит из пяти шагов. На каждом шаге отсекается словообразующий суффикс и оставшаяся часть проверяется на соответствие правилам (например, для русских слов основа должна содержать не менее одной гласной). Если полученное слово удовлетворяет правилам, происходит переход на следующий шаг. Если нет — алгоритм выбирает другой суффикс для отсечения. На первом шаге отсекается максимальный формообразующий суффикс, на втором — буква «и», на третьем — словообразующий суффикс, на четвертом — суффиксы превосходных форм, «ь» и одна из двух «н».

 

Популярен стеммер Mystem 2.0 (https://tech.yandex.ru/mystem/)

Стеммер (полезный ресурс с онлайновыми инструментами): http://www.solarix.ru/for_developers/api/stemmer.shtml

  • на странице познакомиться с материалами по стеммингу и осуществить стемминг фразы в точном соответствии с образцом (Должны быть Ваши ФИО!)

  • на странице познакомиться с лемматизацией  и осуществить лемматизацию фразы в точном соответствии с образцом (Должны быть Ваши ФИО!)

 

 

 

 

kmp