SergeyBPshenichnikov Mar 23 2021 at 00:38

Как преобразовать текст в алгебру

10 min

4.5K

Search engines *Semantics *Algorithms *Natural Language Processing *

Авторы статьи: к.ф.-м.н. С.Б. Пшеничников, к.ф.-м.н. А.С. Вальков

Алгебра и язык (письменность) являются двумя разными инструментами познания. Если их объединить, то можно рассчитывать на появление новых методов машинного понимания. Определить смысл (понять) – это вычислить как часть соотносится с целым. Современные поисковые алгоритмы уже имеют задачей распознавание смысла, а тензорные процессоры Google выполняют матричные умножения (свертки), необходимые для алгебраического подхода. При этом в семантическом анализе используются в основном статистические методы. В алгебре выглядело бы странным использование статистики при поиске, например, признаков делимости чисел. Использование алгебраического аппарата полезно также для интерпретации результатов вычислений при распознавании смысла текста.

Под текстом понимается последовательность знаков произвольной природы. Например, естественные языки, нотные тексты, генетические последовательности биополимеров, коды (кодовые таблицы как отношения знаков). В нотных текстах, записанных на нотоносце из одной линейки (нотоносец-«нитка»), знаками являются ноты, ключи, знаки аллитерации, указания громкости и темпа. В генетических текстах знаками-словами являются триплеты. Знаковые системы вкуса и обоняния пока существуют только как естественные (как образцы, вроде зоопарка). Для осязания существует рельефно-точечный тактильный код-шрифт Брайля. Хабом знаковых систем является семиотика [1], состоящая из трех тегов: семантики, синтактики и прагматики.

Пример языкового текста:

Множество – это объект, являющийся множеством объектов. Полином – это множество объектов-мономов, являющихся множеством объектов-сомножителей. (1)

Чтобы превратить текст в математический объект нужно его правильно координатизировать. Текст примера можно лемматизировать (если для задачи важны морфологические формы, лемматизация необязательна) – привести к нормальной форме: для существительных — это именительный падеж, единственное число; для прилагательных — именительный падеж, единственное число, мужской род; для глаголов, причастий, деепричастий — глагол в инфинитиве несовершенного вида:

(множество)_1,1 (это)_2,2 (объект)_3,3 (являться)_4,4 (множество)_5,1 (объект)_6,3("точка")_7,7 (полином)_8,8 (это)_9,2 (множество)_10,1 (объект)_11,3 (моном)_12,12 (являться)_13,4 (множество)_14,1 (объект)_15,3 (сомножитель)_16,16 ("точка")_17,7 (2)

В (2) правильная координатизация применена. Каждое слово (знак) текста приобретает два индекса, которые и есть координаты слова. Первая координата – это уникальный номер слова в тексте. Со второй координатой слова немного сложнее. Она совпадает с первой координатой, если это слово впервые встречается в тексте. Например, это первые четыре слова (2). Пятое слово «множество» уже было в тексте – это (множество)_1,1. На пятом месте (первая координата) текста это слово повторяется. Оно впервые встретилось на первом месте текста. Затем повторяется на пятом. Поэтому в (2) это слово-знак находится с индексами-координатами 5,1: (множество)_5,1. Таким образом, вторая координата – это номер впервые встретившегося слова в тексте. Все слова, которые впервые встретились в тексте, имеют одинаковые координаты. При этом первая координата уникальна, а вторая может повторяться. В (2) пятое и шестое слово (по первой координате) уже имеются в тексте под номерами 1 и 3. Поэтому слов (...)_5,5, (...)_6,6 в тексте нет. Есть индексированные слова (множество)_5,1 и (объект)_6,3.

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

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

(множество)_1,1 (это)_2,2 (объект)_3,3 (являться)_4,4 ("точка")_7,7 (полином)_8,8 (моном)_12,12 (сомножитель)_16,16 (3)

При координатизации (1) → (2) основными признаками слов стали индексы, а не то, что внутри круглых скобок (...)_i,j. Например, для бинарного кода Морзе латинские буквы являются знаковыми последовательностями. Словарем является последовательность двух знаков-символов ·– («точка» и «тире»), совпадающие с буквами A и N. Порядок знаков в словаре несущественен. Остальные 24 латинские буквы являются кодовыми текстами. Единый текст (с помощью конкатенации) строится из всех букв (как фрагментов текста):

$A\rightarrow (\cdot)_{1,1}(-)_{2,2}, B\rightarrow (-)_{3,2}(\cdot)_{4,1}(\cdot)_{5,1}(\cdot)_{6,1}, C\rightarrow (-)_{7,2}(\cdot)_{8,1}(-)_{9,2}(\cdot)_{10,1}, \ldots$

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

Замечательно, что такие знаки существуют. Это матричные единицы. Матричные единицы E_i,j(имеют два индекса) – это квадратные матрицы, в которых единица находится на пересечении i строки и j столбца, остальные элементы матрицы равны нулю. Например, при размерности n=2:

$E_{1,2} = \left\| {\begin{array}{*{20}{c}} 0&1 \\ 0&0 \end{array}} \right\|, E_{2,1} = \left\| {\begin{array}{*{20}{c}} 0&0 \\ 1&0 \end{array}} \right\|, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(4)$ $E_{1,1} = {E_{1,2}}{E_{2,1}} = \left\| {\begin{array}{*{20}{c}} 1&0 \\ 0&0 \end{array}} \right\|,\;\;{E_{2,2}} = {E_{2,1}}{E_{1,2}} = \left\| {\begin{array}{*{20}{c}} 0&0 \\ 0&1 \end{array}} \right\|,$

где E_1,2, E_2,1 и E_1,1, E_2,2 простые и составные матричные единицы (по аналогии с целыми числами). Произведение матричных единиц отлично от нуля (нулевой матрицы), если внутренние индексы произведения совпадают. Например, E_1,1E_2,1=0, E_2,1E_1,2=E_2,2. Матричные единицы в дальнейшем будут рассматриваться как некоммутативные обобщения целых чисел. Левые и правые делители таких чисел могут различаться, а также имеются делители нуля. Но многие понятия модулярной арифметики [2] остаются справедливыми.

Обычному тексту (2) соответствует матричный текст P (сумма матричных единиц):

$\begin{gathered} P = {E_{1,1}} + {E_{2,2}} + {E_{3,3}} + {E_{4,4}} + {E_{5,1}} + {E_{6,3}} + {E_{7,7}} + {E_{8,8}} + {E_{9,2}} + \\ + {E_{10,1}} + {E_{11,3}} + {E_{12,12}} + {E_{13,4}} + {E_{14,1}} + {E_{15,3}} + {E_{16,16}} + {E_{17,7}} \\ \end{gathered} \;\;\;\;\;\;(5)$

Индексы (координаты) в (2) и (5) поэлементно совпадают, но P - математический объект (квадратная матрица). Разделитель (пробел) слов в (2) превращается в операцию сложения матриц. Исходный текст (2) восстанавливается по индексам из (5) «забыванием» алгебраических свойств (превращением операции сложения в разделитель-пробел) и обратным использованием кодовой таблицы «координата-слово».

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

Матричный словарь, соответствующий (3) имеет вид:

$D_R = E_{1,1} + {E_{2,2}} + {E_{3,3}} + {E_{4,4}} + {E_{7,7}} + {E_{8,8}} + {E_{12,12}} + {E_{16,16}} \;\;\;\;\;\;\;(6)$

Матричный словарь D_R – это матричный текст P с исключенными повторами. Размерность матриц P и D_R i_max×i_max, где i_max – номер последнего слова (знака) в тексте. В каждой строке матриц P и D_R имеется не более одной единицы, остальные элементы равны нулю. Это свойство является следствием уникальности первого индекса. В матрице D_R соответствующие словам текста единицы находятся на её главной диагонали. Остальные элементы диагонали и матрицы равны нулю.

Для матричных текстов выполняются соотношения:

$P{D_R} = P,\;\;{D_R}P = {D_R},\;\;{P^2} = P,\;\;D_R^2 = {D_R},$

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

Делимое, делитель и частное определяются для любых фрагментов матричного текста F₁, F₂, …,F_k почти также, как для целых чисел. Элемент F_i (делимый) делится на элемент F_j (делитель), если существует элемент F_ij (частное) такой, что F_i=F_ijF_j. В отличие от целых чисел частное располагается слева от делителя. Частное может не являться фрагментом текста.

Фрагмент текста в предельном случае может быть матричной единицей (матричным словом). По (4) матричные единицы сами могут быть простыми и составными. Из n² матричных единиц 2(n-1) являются простыми, остальные (n² – 2n – 2) – составные (произведения простых).

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

Правый идеал матричного текста –это всевозможные номера слов в D_R (вторых координат), которые можно разместить на заданных номерах слов в тексте (первых координат).

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

Понятие делимости матричных текстов обобщается на делимость идеалов матричных текстов. Свойства делимости матричных фрагментов текста имеют место при делении идеалов. Понятия НОД и НОК также обобщаются на случай идеалов матричных текстов.

Сравнения целых чисел также обобщаются на случай матричных текстов. Фрагменты матричных текстов F₁, F₂, …,F_k сравнимы по модулю (мере) F_m фрагмента , если остатки от деления F₁, F₂, …,F_k на F_m кратны.

Если остатки кратны, то они имеют одинаковые словари. Поэтому фрагменты сравнимы по модулю заданного фрагмента, если остатки от деления фрагментов на заданный фрагмент имеют одинаковые словари. Сравнимость текстов по модулю некоторого текста можно интерпретировать следующим образом. Пусть имеется корпус английского языка. Выбираются шесть книг, наиболее соответствующие шести базовым сюжетам Шекспира. Матричный текст этих шести книг является фрагментом F_m. Тогда остальные книги корпуса, имеющие кратные остатки от деления их матричных текстов на F_m, сравнимы по F_m. Это означает, что можно сделать каталог книг для тех, кого интересуют не только шекспировские сюжеты. Причем кратность остатков является классифицирующим признаком для этого каталога. Классов вычетов в этом примере шесть. Взяв только три книги, например, можно весь корпус английского языка сравнить только по трем сюжетам из шести. Если человек имеет десять любимых книг или авторов, можно классифицировать корпус языка по признакам отличия от этого топтена.

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

Цель преобразований матричных текстов – алгебраически обоснованная фрагментация P со значительным уменьшением числа используемых фрагментов по сравнению с комбинаторной оценкой, которая называется алгебраической структуризацией текста.

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

Перечисленные структурные признаки – соответствующие части (фрагменты) текста. Для полиномиального представления матричного текста некоторые такие части – это соответствующие некоммутативные базисы Грёбнера-Ширшова. Коммутативный базис Грёбнера-Ширшова заданного набора многочленов - это такой многочлен, что при делении любого многочлена из этого набора на этот базис получается нулевой остаток. Если многочлены некоммутативны (составляющие их мономы не перестановочные по умножению), то аналог этого базиса называется некоммутативным.

Алгебраическая структуризация текста примера (5) выглядит следующим образом:

$F_1(P) = E_{1,1} + E_{2,2} + E_{3,3} + E_{4,4} + E_{5,1} + {E_{6,3}} + {E_{7,7}}$ $F_2 = E_{8,8} + {E_{9,2}} + {E_{10,1}} + {E_{11,3}} + {E_{12,12}} + {E_{13,4}} + {E_{14,1}} + {E_{15,3}} + {E_{16,16}} + E_{17,7}$ $F_2 = \left( E_{9,2} + E_{10,5} + E_{11,6} + E_{13,4} + E_{14,5} + E_{15,6} + E_{17,7} \right)F_1+ \\ +E_{8,8}+E_{12,12}+E_{16,16}$ $P=F_1+ \left(E_{9,2} + E_{10,5} + E_{11,6} + E_{13,4} + E_{14,5} + E_{15,6} + E_{17,7}\right)F_1 + \\ +E_{8,8} + E_{12,12} + E_{16,16}$ $P=\left(E + E_{9,2} + E_{10,5} + E_{11,6} + E_{13,4} + E_{14,5} + E_{15,6} + E_{17,7}\right)\times \\ \times \left( E_{1,1} + E_{2,2} + E_{3,3} + E_{4,4} + E_{5,1} + E_{6,3} + E_{7,7} + E_{8,8} + E_{12,12} + E_{16,16} \right),$ $P=\left(E + E_{9,2} + E_{10,5} + E_{11,6} + E_{13,4} + E_{14,5} + E_{15,6} + E_{17,7}\right) \left( D_R + E_{5,1} + E_{6,3} \right), \;\;\;\;\;\;\;(7)$

где E – единичная матрица. Используя свойства матричных единиц, исходный матричный текст в аддитивной форме (5) преобразован в мультипликативную форму (7). Сомножитель (D_R+E_5,1+E_6,3) является некоммутативным аналогом базиса Грёбнера-Ширшова для коммутативных многочленов. Бриллиантовая лемма Ширшова выполняется – в сомножителе (D_R+E_5,1+E_6,3) имеются зацепления (повторения) справа по второму индексу, но они разрешимы (имеют общие делители).

При преобразовании (редукции) (7) произошло преобразовании словаря текста:

$D_R \rightarrow \left( E_{5,1} +E_{6,3} +E \right) D_R,\;\;\;\;\;\;\;\;\;\;\; (8)$

В новом словаре (базисе идеала) появились слова E_5,1 и E_6,3. Это те же слова E_1,1 знаки («множество») и E_3,3 («объект»), но находящиеся на пятом и шестом местах текста. Слова как знаки те же, но смысл повторяющихся слов в тексте меняется. Слова определяются контекстами. Слова близки, если их контексты содержат хотя бы одно общее слово. Контексты тем более близки, чем больше общих слов из соответствующего словаря (общих вторых индексов) они содержат.

В естественных языках множественность контекстов слова является причиной неоднозначности понимания смысла слов. Смысл по Фреге – это соответствующая часть значений знака (слова). Значения слова – это все его контексты (свойства). Например, пусть знак – это слово «объект». Все его значения в тексте: множество, элемент множества, моном и сомножитель. Это означает, что слово-знак «объект» обозначает четыре омонима. Смысл – это часть значений, например, только «моном».

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

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

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

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

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

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

Предисловие, введение, заключение, аннотация, реферат - это заголовки, дополненные элементами базиса меньшей частотности, и вычетами, вошедшими в базис (как в алгоритме Бухбергера). Для текста примера вычет – это остаток E_8,8+E_12,12+E_16,16 в (7) или в исходном виде – (полином)_8,8... (моном)_12,12...(сомножитель)_16,16 – остаток от разложения F₂ по F₁. Именно этими элементами базиса (вычетами) отличаются контексты биграмм «множество объект» «объект множество».

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

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

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

Более строгое и общее описание алгебры текста изложено в [3].

Литература

Tags:

Hubs: