10 марта 2016г.
1. Введение.
Проанализировав прекрасный обзор К.В.Воронцова [2], начнѐм с критики общих слабых мест в работах цитируемых им авторов.
Прежде всего, в теоретических построениях все без исключения авторы рассматривают универсальный словарь W. Судя по контексту, им должен быть единый для всех общий словарь. Однако, когда дело доходит до вычислений, фактически используются разные словари. Отсюда напрашивается включение в состав моделей возможности выбирать словарь.
Ещѐ важнее отказ от универсальности рассматриваемых словарей. Он позволит создавать и использовать разнообразные словари специального назначения.
Наиболее уязвимым местом в работах цитируемых Воронцовым авторов является понятие темы. Внятное еѐ определение вообще отсутствует. Вместо него говорится о совместном «неслучайно частом»(!) употреблении каких-либо слов в составе документов общей тематики. Значит, такая тема – не объект, а обстоятельство.
С теоретико-множественной точки зрения темы объявляются элементарными. Это сразу же исключает возможность пересечения тематики (в частности, вхождения «узких» тем в состав «широких»). Надо признать, что несовместность (непересекаемость) тем создаѐт массу преимуществ (прежде всего, возможность суммирования по множеству тем). Тем не менее, минусов из-за такого ограничения гораздо больше.
Каждое вхождение слова в состав документа почему-то связывается только с одной темой. Эта гипотеза представляется нам серьѐзнейшей натяжкой. Косвенным еѐ следствием служит тот факт, что после добавления новых документов к ранее рассмотренному множеству могут весьма сильно измениться как список выявленных тем, так и привязка слов к темам.
Наконец, почти утрачена связь темы с относящимися к ней словами. Она выражается лишь в изменении условных вероятностей появления слов в документах. При этом даже не утверждается (хотя и явно подразумевается), что речь идѐт именно об изменении в сторону увеличения.
Все перечисленные недостатки преодолеваются, если связать с каждой темой словарь «специфических» именно для неѐ слов. Разумеется, возникает проблема составления подходящих словарей, чему и посвящена эта работа.
Оказывается, тематические словари должны обладать свойством замкнутости в смысле Галуа [3]. Так как нужная конструкция Галуа нигде не изложена по-русски с требуемой детальностью, то ей посвящен следующий параграф.
2. Замыкания и двойственность Галуа.
Пусть U – некий универсум объектов (элементов), а V – (двойственный ему) универсум признаков (свойств) этих объектов. Отношение двойственности между U и V устанавливает булева функция В(u,v), принимающая значение «ИСТИНА», если элемент u∈U обладает свойством v∈V, и значение «ЛОЖЬ» в противном случае.
Для любого элемента u∈U обозначим через Г(u) множество всех свойств этого элемента: Г(u) ={v∈V :
В(u,v)=«ИСТИНА»}.
Для любого множества X⊂U определим двойственное ему множество Г(Х)=∩{Г(х) : х∈Х} . Оно состоит из всех общих свойств всех элементов из множества Х.
Легко заметить, что с чисто формальной точки зрения ситуация абсолютно симметрична. Поэтому для любого свойства v∈V можно ввести множество Г(v) ={u∈U : В(u,v)=«ИСТИНА»} всех объектов, обладающих свойством v. А для любого множества Y⊂V можно ввести двойственное ему множество Г(Y)=∩{Г(y) : y∈Y} всех объектов, обладающих всеми свойствами из Y. Повторять это замечание мы больше не будем, но считаем по умолчанию, что все сделанные ниже утверждения об элементах зеркально дублируются для свойств (и наоборот).
Рассмотрим теперь Г(Г(Х)). Так как Г(Х) – множество всех общих свойств всех элементов из Х, то любой элемент х∈Х обладает всеми свойствами из Г(Х). Поэтому X⊂Г(Г(Х)). Легко понять, что равенства здесь может не быть. Нельзя исключать возможность, что всеми теми же самыми свойствами обладает ещѐ и какой-либо элемент, не принадлежащий Х.
«Чудо» состоит в том, что верна теорема Галуа: Г(Г(Г(Х)))=Г(Х) . Этот факт побуждает ввести понятие замыкания Галуа С(Х)=Г(Г(Х)). Если С(Х)=Х, то Х называется замкнутым (по Галуа).
Для замкнутых множеств соответствие Галуа Г превращается в «чистую» двойственность: если Y=Г(Х), то Х=Г(Y) (и наоборот). При этом все множества вида Г(Y) заведомо замкнуты.
Многочисленные реализации описанной конструкции фактически присутствуют во всех без исключения математических дисциплинах. Прежде всего, замыканиями Галуа являются все операции замыкания (в алгебре, топологии, функциональном анализе и пр.) и разнообразные оболочки (линейная, аффинная, коническая, выпуклая и др.). При подходящем выборе U и V частными случаями двойственности Галуа становятся арифметические операции 1/x и −х, полярное соответствие, ортогональное дополнение, разнообразные сопряжения и т.д.
Ещѐ важнее роль замыканий и двойственности Галуа в естественных и гуманитарных науках. Любая
«правильно построенная» классификация должна базироваться на замкнутых по Галуа множествах объектов и двойственных им множествах свойств.
Например, обнаружив новое для себя растение, ботаник сравнивает его с уже изученными. Если удаѐтся выделить характеристические признаки и установить их совпадение с каким-либо образцом, то растение относится к одному с ним биологическому виду. В противном случае определяется признак, значение которого (в сочетании с признаками всех более высоких уровней) принципиально отличается от ранее известных, что позволяет говорить об уникальности.
3. Тематическая модель в классической (двоичной) логике.
В качестве объектов здесь и ниже будут рассматриваться слова. На данном этапе ещѐ нет необходимости глубоко вдаваться в семантику этого понятия и делать стандартные оговорки о возможности нескольких разных форм одного и того же слова и их распознавании. Ограничимся замечанием, что слово считается элементарным (различимым и неделимым) объектом.
Словарѐм мы будем называть любое множество слов. Как уже сказано, К.В. Воронцов и цитируемые им авторы фиксируют универсальный словарь W и не рассматривают иных словарей. Однако именно варьирование словарей позволяет более адекватно формулировать нужные понятия. Подчеркивая это различие, будем обозначать словари буквой l, сохранив W за универсальным словарѐм. Заглавную L используем для произвольного множества словарей.
Документом d называется любая упорядоченная последовательность слов (возможно, с повторениями).
Заглавную D используем для любого множества документов.
Каждому документу d можно поставить в соответствие «его» словарь l(d) , состоящий в точности из всех слов, встречающихся в документе d (без повторов и без учѐта их порядка в тексте этого документа). Аналогично, для множества документов D через L(D) обозначим множество словарей l(d), отвечающих всем d∈D , а через l(D) – их объединение.
Ясно, что эта операция необратима: разным документам может соответствовать один и тот же словарь. Тем не менее, любой словарь l можно превратить в документ, как угодно зафиксировав порядок слов в нѐм. Если с этой целью выбрана какая-либо стандартная процедура (например, лексикографический порядок), то обозначим через d(l) возникающий таким способом документ. Легко понять, что l(d(l))=l .
Через D(l) обозначим множество всех документов, которые можно составить из слов словаря l . Заметим, что D(l) бесконечно для любого непустого словаря l , так как даже единственное слово можно повторить в пределах одного текста сколько угодно раз. Все рассмотренные множества в предшествующей части этого параграфа, по умолчанию, были конечными.
Если нужно избавиться от бесконечности, то сделать это легко. Достаточно ввести ограничение на длину документов.
Темой множества документов D назовѐм Т=D(l(D)) − множество всех документов, которые можно составить из слов, встречающихся в документах из множества D. Ясно, что D⊂Т, но равенства здесь нет, так как D(l(D)) бесконечно, а D, как правило, конечно.
Если взять множество D={d} , состоящее из единственного документа d, то можно говорить о теме Т(d) конкретного документа d. А если взять d=d(l) , то появляется возможность говорить о теме Т(l) словаря l.
Словарь темы l(Т)= l(D(l(D))) = l(D) . Ясно, что l(Т(l)) = l .
Словарным ядром k(Т)=k(D) темы Т=D(l(D)) и определяющего еѐ множества документов D назовѐм
∩l(d). Пересечение здесь берѐтся по всем документам d∈D .
Заметим, что k(Т) может оказаться даже пустым. Гораздо чаще, ядро будет состоять только из «мусорных» слов – общеупотребительных и служебных. Ясно, что с практической точки зрения такая тема «бессодержательна». Важнее собрать в k(Т) специальные термины нужной тематики. С чисто формальной точки зрения достичь этого несложно: достаточно заранее включить в состав D нужный терминологический словарь. Беда лишь в том, что как раз составление терминологического словаря k(Т) в некоторых случаях является главной целью исследования. А когда он уже составлен, нет резона исключать из него термины, по каким-либо причинам использованные не во всех документах множества D.
Достоинством и одновременно недостатком этого подхода является слишком широкая универсальность понимания темы и еѐ ядра. Их можно связать с любым документом, словарѐм или множеством документов, предварительно даже не заботясь об их содержании и смысловых связях между словами в составе словаря или различными документами.
Тем не менее, даже в рамках этого подхода можно привести немало содержательных примеров. Прежде всего, словари различных естественных языков позволяют расклассифицировать любое множество документов по использованным в них языкам. С другой стороны, словарь терминов из узкой предметной области, написание которых не различается в большинстве европейских языков, позволяет выделить тексты нужного содержания вне зависимости от их языка. Удачно составленный словарь языка конкретного автора, позволит эффективно выделять из огромной массы документов его последователей (учеников, подражателей и плагиаторов).
4. Вероятностная модель
«Жѐсткий» классический подход беспристрастно фиксирует вхождение слов в состав документов, но «не отличает» чисто случайные вхождения от вполне закономерных (обусловленных содержанием темы). К.В. Воронцов справедливо заметил, что выделение «содержательных» тем должно основываться на «неслучайно»(!) повышенной встречаемости в текстах этой темы специфических для неѐ терминов.
Обозначим вслед за ним через n(w,d) количество вхождений (повторений) слова w∈W в документе d∈D ,
а n(d) = Σ n(w,d) − длину (количество слов) документа d (с учѐтом повторений). Так как n(w,d)=0 для слов w, которых нет в документе d , то суммирование достаточно вести только по w∈l(d) , а не по всему универсальному словарю W (как это делает К.В. Воронцов).
Частота слова w в документе d определяется как р^(w,d) = n(w,d)/n(d).
Легко вычисляемые частоты р^ служат оценками для вероятностей р.
Их несколько. Начнѐм с фиксации документа d и темы Т. В документе d выделим (предположительно,
«относящийся к теме») фрагмент f⊂d . В принципе, фрагментом может быть любое подмножество (наследующее из документа порядок слов и их повторения), но на практике оно будет состоять из небольшого числа связных (во всех смыслах) кусков. Для фрагмента f и темы Т введѐм вероятность p(f,T) их «связи».
Обозначим через q(f,d)=n(f)/n(d) долю фрагмента f в составе документа d. В идеале фрагмент f нужно выбирать так, чтобы достигался максимум произведения q(f,d)∙ p(f,T) , который мы обозначим через P(d,T) .
Так как весь документ d можно рассматривать в качестве собственного фрагмента, причѐм q(d,d)=1, то всегда P(d,T)≥ p(d,T) .
Появление того или иного слова w в выбранном документе d разумно считать пуассоновским потоком событий. Интенсивность i(w,d) этого потока может возрасти в случае, когда документ d связан с темой Т, для которой w∈k(Т) или хотя бы w∈l(Т) . Ясно, что изменение интенсивности может выражаться различными формулами («законами»). Даже не пытаясь объять необъятного, постараемся выделить наиболее простые модели их связи.
Для этого трансформируем одну из основных гипотез Воронцова и его предшественников к виду i(w,f)= i(w,Т)∙i(Т,f), где через i(w,Т) обозначена интенсивность появления данного слова w в среднестатистическом «эталоне» текста на тему Т, а через i(Т,f) обозначена интенсивность появления в выбранном фрагментe f
документa d не важно какого слова, лишь бы относящегося к теме Т.
Выделенная формула фактически относится к многим разным моделям в зависимости от того, подразумевается ли «отношение к теме» как w∈k(Т) или w∈l(Т) , либо задаѐтся пороговым значением вероятности р(w,Т) . Все соответствующие вероятности выражаются через интенсивности по закону Пуассона.
Заметим, что для вероятностей аналогичная формула произведения неверна (но она сохранится как приближѐнная, поскольку интенсивности близки к нулю).
Напомним, что интенсивность в законе Пуассона имеет смысл средней частоты. Обратная к ней величина в нашем контексте – это среднее расстояние между двумя вхождениями одного и того же слова. Поэтому в первом приближении (если проигнорировать дисперсные отклонения от средних значений) частоты в модельных текстах совпадут с вероятностями.
5. Нечѐткая модель.
К числу уязвимых мест в работах К.В. Воронцова и цитируемых им авторов относится также попытка соединить «жѐсткую» модель с частотным анализом. Из-за этого многие формулировки потеряли внятность, а внешне эффектные результаты расчѐтов остались без вменяемого объяснения, что же именно вычислялось на самом деле. Наконец, оценку (замену) вероятностей частотами нельзя признать корректной в случае слишком малого числа экспериментов, тогда как для проведения длинной серии экспериментов не хватает ни исходных данных, ни мощности компьютеров. Освободиться от названных недостатков и преодолеть возникшие проблемы позволяет язык теории нечѐтких (fuzzy) множеств.
Вместо словаря темы l(Т) или его ядра k(Т) теперь будет введена нечѐткая функция принадлежности r(w,T) слова w к теме T. Для некоторых слов она может быть представлена точным значением вероятности р(w,Т) ; в частности, если w∈k(Т) в прежнем смысле, то р(w,Т)=1 . В иных случаях точное значение р(w,T) заменяется вероятностным распределением, либо распределением на множестве распределений и т.д., вплоть до чисто словесной оценки r(w,T) .
Аналогично, нечѐткими функциями заменяются все рассмотренные в предыдущем параграфе вероятности и интенсивности. Подобная замена в ином контексте обстоятельно реализована С.В. Прокопчиной [4].
Может показаться, что это приведѐт к ещѐ большему нагромождению сложных вычислений. Тем не менее,
«лингвистический» подход оказывается более перспективным и результативным при проведении экспертных оценок.
6. Примеры из биоинформатики.
Зафиксируем три натуральных числа p
Подчеркнѐм, что (в отличие от стандартного прочтения текстов) слова внутри документа и документы внутри темы могут перекрываться. Например, если p=2, q=3, а r=4 , то тема АВВА состоит из документов АВВ и ВВА, первый из них состоит из слов АВ и ВВ, а второй – из слов ВВ и ВА.
Словарь темы АВВА состоит из трѐх слов АВ, ВА и ВВ, а словарное ядро – только из одного слова ВВ. Темы ААВА и АВАА имеют совпадающие словари, но различные ядра. Различаются они и как множества документов.
Если алфавит состоит только из двух символов, то из них можно составить 22=4 слова (АА, АВ, ВА и ВВ),
23=8 документов и 24=16 тем.
Документ ААА состоит из двух вхождений слова АА, а ВВВ – из двух вхождений слова ВВ. Остальные 6 из 8 документов состоят из двух разных слов. Сходная ситуация и с темами: АААА и ВВВВ состоят только из одного документа (повторы документа в составе темы на теоретико-множественном уровне не играют никакой роли), а остальные 14 тем – из двух разных документов.
Если вхождения документов в состав темы объявить равновероятными, то можно найти вероятности появления слов. Разумеется, они окажутся равными m/3 , где m – число повторов слова в теме; 0≤m≤3 .
При небольших q=3 и r=4 модель Пуассона «не работает». Но если q/p и r/q весьма велики, то появление слов в документе становится пуассоновским потоком, а вероятности удобнее заменить интенсивностями.
Аналогичные модели (но с огромными q и r) возникают в задачах расшифровки генетического кода [1]. В роли темы там выступает молекула ДНК, рассматриваемая как (неизвестная) последовательность аминокислот, играющих роль символов алфавита. Приборные исследования не могут сразу обозреть всю молекулу длины r и сканируют лишь существенно более короткие еѐ фрагменты длины q . Они играют здесь роль документов.
Конечная цель – «склеить» из фрагментов всю молекулу. Прежде всего, для этого необходимо, чтобы имеющийся набор фрагментов полностью еѐ перекрывал. Другое требование – наличие существенных перекрытий на концах соседних фрагментов. Здесь важно заметить, что заранее неизвестно, какие именно фрагменты являются соседними. Чтобы выявить их, нужно для каждой пары фрагментов проверить, нет ли сравнительно длинных совпадающих кусков на их противоположных концах.
Ясно, что если длина р этих совпадающих кусков (они будут играть роль слов) относительно невелика, то совпадение, скорее всего, было чисто случайным. Но если взять р огромным и искать совпадения путѐм перебора вариантов, то для этого не хватит мощности современных компьютеров.
Компромиссное решение состоит в постепенном наращивании р. На первом этапе его берут небольшим: максимально возможным при условии, что перебор вариантов должен сравнительно быстро завершиться. Если совпадений окажется не слишком много, то каждое из них анализируется, сколь далеко его можно продолжить.
Уже на этом этапе учѐт частот идѐт на пользу. Одиночные совпадения, скорее всего, бесперспективны. В лучшем случае, они выявляют слишком короткий общий участок на концах, не позволяющий сделать далеко идущих выводов. Напротив, скопление коротких совпадений на относительно длинных участках часто указывает на их тождественность.
Другая задача – сравнение двух ДНК на предмет выявления степени их «родства». Так как здесь уже не ставится вопрос о полном их совпадении, то вероятностные и лингвистические (нечѐткие) оценки выходят на первый план.
7. Замыкание классов Тузова.
Работа В.А. Тузова [5] идейно очень близка к подходу Галуа. Основу его классификации слов русского языка составляет иерархическая система специальным образом отобранных их свойств. Однако, точь-в-точь как и все цитируемые Воронцовым авторы, Тузов стремился получить классы без пересечений. Это вынудило его использовать последовательности свойств, в которых недопустимы изменение порядка и произвольные замены одних свойств другими.
Отказ от этих ограничений позволяет получить близкую по смыслу классификацию. Классы Тузова будут играть в ней роль «узких» тем. Но при этом становится возможным их объединение в более широкие темы. Важно, что такие темы окажутся замкнутыми в смысле Галуа, а двойственность поставит им в соответствие замкнутые множества свойств.
Невозможно спросить у покойного автора, намеренно ли он отказался подчинить построенную им классификацию требованиям замкнутости Галуа. Остаѐтся лишь разобраться, почему классы Тузова прекрасно «работают» в отсутствие столь важного условия.
Одна из причин – дискретность. Если запретить появление новых слов, то словарь конечен. А в дискретной топологии на конечном множестве замкнутыми являются все без исключения его подмножества. Благодаря чему требование замкнутости фактически оказалось выполненным, даже не будучи специально продекларированным.
Однако, реальность всѐ же сложнее. Дело даже не в систематическом возникновении новых слов и новых смыслов у «старых» слов. Огромная масса слов вообще не зафиксирована в словарях. Например, там отсутствуют порядковые числительные, отвечающие даже большинству двузначных чисел, не говоря о многозначных (в порядке исключения в словари включены лишь слова, чреватые частыми ошибками).
Значит, в противоположность всем уже опубликованным версиям, «полный словарь» какого-либо естественного языка представляет собой не дискретное (конечное) множество, а континуальную среду, в которой можно выделять (фиксировать) отдельные слова. Подходящей аналогией служат примеры из геометрии. После реформы еѐ школьного курса академиком А.Н.Колмогоровым плоскость и пространство определяются как множества точек с нужными свойствами. Тогда как традиционный подход (от Евклида до Римана) рассматривал их как протяжѐнности, внутри которых можно выбирать точки и строить из них какие-то фигуры.
Дело вовсе не в том, что теоретико-множественный подход появился на две тысячи с лишним лет после Евклида. Большинство базовых вопросов теории множеств не только не ставились тогда, но при корректной трактовке вообще не имеют однозначного ответа.
Например, после случившейся в начале ХХ века полемики между Гильбертом и Пуанкаре принято представлять евклидову плоскость в декартовой модели, допуская в качестве значений координат любые вещественные числа. Но если точно следовать древнегреческой традиции, опиравшейся на построения циркулем и линейкой, то значениями координат могут быть только квадратичные иррациональности. Значит, в современном понимании мощность множества всех точек евклидовой плоскости равна континууму, тогда как у самого Евклида плоскость фактически была счѐтным множеством точек.
Вернѐмся к классам Тузова. «Протяжѐнность» («размытость») словарей естественных языков приводит к тому, что классы Тузова смогут потерять замкнутость. Если такое случится по мере развития русского языка, то конструкция Тузова утратит свою корректность. Залогом незначительности этого риска служит слишком медленный темп изменений в языке.
При построении классификации важно не терять смысла, что и ради чего делается. Хорошим примером служит такое свойство как цвет (окрас) животных. В одних случаях он является основным классифицирующим признаком биологического вида. В других лишь выделяет породы в рамках одного и того же вида. В третьих вообще не играет никакой роли.
Аналогично, после появления (фиксации в словаре) каждого нового слова нужно будет попытаться найти его место в уже построенной классификации. Чаще всего, оно найдѐтся. В противном случае нужно понять, что именно мешает отнести слово к тому или иному «близкому» классу. Когда принципиальное различие будет выявлено и чѐтко сформулировано, оно и станет недостающим новым свойством.
Список литературы
1. Александров А.В., Казаков С.В., Мельников С.В., Сергушичев А.А., Федотов П.В., Царев Ф.Н., Шалыто А.А. Параллельный алгоритм de novo сборки генома с использованием технологии MapReduce / Сборник трудов международной суперкомпьютерной конференции "Научный сервис в сети Интернет: поиск новых решений" и конференции молодых ученых "Теория и практика параллельного программирования". М.: МГУ. 2012, с. 679-682.
2. Воронцов К.В. Вероятностное тематическое моделирование. Курс лекций ВМК МГУ. – http://www.machinelearning.ru/wiki/images/2/22/Voron-2013-ptm.pdf .
3. Галуа Э. Сочинения / Пер. с французского Н.Н. Мейнмана, под редакцией и с примечаниями Н.Г. Чеботарева. - М.-Л.: ОНТИ, 1936. - 342 с.
4. Прокопчина С.В. Байесовские интеллектуальные технологии для аудита и управления сложными объектами в условиях значительной неопределѐнности // В сб. докладов Первой междунар. конф. ЮНИ- ИНТЕЛ 2010 «СЕЛИГЕР», 25–29 июня 2010, с. 81-85.
5. Тузов В.А. Компьютерная семантика русского языка // Издательство СПбГУ, 2004.
