Файл: Санктпетербургский.pdf

Системный анализ и принятие решений Макаров Л.М.
66 статистических свойств текстов позволяют формировать статистические портреты текстового материала. Исследования открытых текстов показывает, что в каждом тексте можно выделить ключевые слова, для которых установлены значения вероятности встречаемости в тексте.
Кластер текстовых документов можно определить как множество, представленное то- чечными элементами образов текстов. В свою очередь элементарный образ текста характеризу- ется некоторым набором ключевых слов, в общем случае m- грамм, с установленными значени- ями вероятностей вхождения в исходный текст.
Для некоторого произвольно выбранного текста укажем набор m – грамм из трех ключе- вых слов: а
1
, а
2
, а
3
. Причем, первые две m – граммы выделим произвольно, а третью такую, что она в сочетании с первыми двумя образует семантически связанное суждение. В качестве ил- люстративного примера рассмотрим ключевые слова: формула – вставка – функция, для кото- рых установлены значения вероятности: Р(а
1
)=0,01; Р(а
2
)=0,015; Р(а
2
/a
1
)=0,012. Воспользуемся известным понятием об условной вероятности. Тогда можно записать выражение для искомой вероятности наступления события:
Полученный результат свидетельствует о том, что произвольный выбор первых двух ключевых слов с малой долей вероятности позволяет сделать суждение о наличии описания функции в исследуемом тексте.
Если изменить исходные данные: Р(а
1
)= 0,1; Р(а
2
)= 0,15; Р(а
2
/a
1
)= 0,012, то имеем –
Р(А)=0,0138. В этом случае наблюдаемое повышение уровня вероятности обнаружения сужде- ния о наличии в тексте описания некоторой функции объясняется повышением значений веро- ятности обнаружения ключевых слов.
В самом общем случае, можно дать рекомендации, которые сводятся к тому, что ключе- вые слова должны выбираться из текста с высокими значениями вероятности обнаружения.
Использование таких слов в качестве основы построения суждений является необходимым условием.
Рассмотрение исходного текста в качестве массива слов, для которых могут быть найде- ны вероятностные показатели, позволяет сформировать фрагменты семантической сети поня- тий, столь необходимые при формировании образа текста. Синтезируя наборы ключевых слов, представляется возможным формировать смысловой образ текстового материала.
Расширяя понятия анализа текстовых массивов можно рассмотреть случай набора тек- стов, объединенных в корпус. Надо признать, что создание одинаковых по размеру корпусов
00003
,
0 012
,
0
*
01
,
0 015
,
0
*
01
,
0
)
/
(
*
)
(
)
(
*
)
(
)
(
1 2
1 2
1
=
−
=
−
=
a
a
P
a
P
a
P
a
P
A
P

Системный анализ и принятие решений Макаров Л.М.
67 текстов, близких по семантическим признакам, невозможно. Поскольку наборы текстов, вхо- дящих в корпус различаются своими размерами, конечные наборы также получаются различ- ными. Для работы с такими корпусами текстов требуется некоторая предварительная оценка суждений об адекватности корпусов и анализе входящих в них текстовых материалов.
Сформулированные представления позволяют рассмотреть задачу получения статисти- ческой оценки равнозначности суждений, сформированной на произвольно выбранном корпусе текстовых документов.
Положим, имеется 4 корпуса текстов, сформированных по единой тематике. Определим такой набор коллекцией. Полагаем, что первый корпус содержит R
1
=0,95 типичных материа- лов. По аналогии укажем значения типичных материалов в других корпусах: R
2
=0,97, R
3
=0,94,
R
4
=0,91. При этом размер каждого корпуса в коллекции различен и составляет Q
1
=0,28, Q
2
=0,31, Q
3
=0,24, Q
4
=0,17, соответственно.
Определим значение вероятности того, что в произвольно выбранном корпусе окажутся типичные материалы, отражающие существенные тематики избранной области знаний. Такую направленность проблемы выбора корпуса документов аргументируем наличием возможности иметь значительно больший набор корпусов, что, безусловно, потребует значительного време- ни анализа.
Представим исходные данные в виде:
P(A/A
1
)= R
1
P(A
1
)= Q
1
P(A/A
2
)= R
2
P(A
2
)= Q
2
P(A/A
3
)= R
3
P(A
3
)= Q
3
P(A/A
4
)= R
4
P(A
4
)= Q
4
Используя известное выражение для оценки вероятности выбора типичного документа из набора кластеров, можно записать:
Полученный результат характеризует математическое ожидание или вероятность выбор- ки типичного документа. Фактически это долевая средняя, показывающая среднюю долю ти- пичных документов в четырех корпусах. Высокое значение вероятности выборки типичного документа позволяет избрать стратегию случайного анализа ключевых слов одного из докумен- тов, входящих в четыре корпуса.
Полученный результат требуется уточнить. Необходимо установить минимальный раз-
95
,
0
)
/
(
)
(
)
/
(
)
(
)
/
(
)
(
)
/
(
)
P(A
P(A)
4 4
3 3
2 2
1 1
=
+
+
+
=
A
A
P
A
P
A
A
P
A
P
A
A
P
A
P
A
A
P

Системный анализ и принятие решений Макаров Л.М.
68
0,7
0,75
0,8
0,85
0,9
0,95
1
0,02
0,05
0,08
0,11
0,14
0,17
Размер корпуса R4 в коллекции
Зн
а
ч
е
н
и
е
в
е
р
о
я
тн
о
с
ти
д
о
с
то
в
е
р
н
о
й
о
ц
е
н
ки
мер одного из корпусов документов, при котором возможно обоснованное применение страте- гии случайного выбора. Используя известные наблюдения за экспертом в данной ситуации можно выдвинуть гипотезу о некотором минимальном размере корпуса, анализ которого он не станет проводить, оперируя понятиями малой достоверности получаемых суждений, на малом объеме данных.
Проведем исследования по схеме: Q
i
 Q min
, вычислим значение P(A) для разных зна- чений Q
i
. Полагая, что все корпуса коллекции равнозначны, выберем в качестве переменной параметр Q
4
(2% - 17%). Проведем расчет и представим результат на рисунке 4.4.
Полученный результат демонстрирует линейную зависимость, которая может быть по- лезна при выборе размеров корпусов текстов.
Рисунок 4.4 Оценка достоверности суждений при различных размерах корпуса R
4
Для уточнения полученных результатов проведем исследование изменения значений ве- роятности достоверной оценки от размера тематических документов в одном из корпусов. Ре- зультат проведенных расчетов представим на рисунке 4.5.

Системный анализ и принятие решений Макаров Л.М.
69
0,7
0,75
0,8
0,85
0,9
0,95
1
0,7
0,75
0,8
0,85
0,9
0,95
Объем тематических документов в корпусе R4
Зн
а
ч
е
н
и
е
в
е
р
о
я
тн
о
с
ти
д
о
с
то
в
е
р
н
о
й
о
ц
е
н
ки
Рисунок 4.5 Оценка достоверности суждений при различных объемах текстовых материалов в корпусе R
4
Полученные результаты позволяют говорить о равнозначности приоритетов подбора, как размера корпусов, так и количества текстовых документов входящих в каждый корпус. Не акцентируя внимание на той или другой оценке можно признать их равнозначность при форми- ровании коллекции. Эти формальные результаты соответствуют интуитивным устремлениям эксперта, который на основе своих представлений формирует коллекцию документов.
Представленные эскизные расчеты составляют основу построения многих тематических подборок документов, по которым проводится формирование суждений, как с целью установ- ления их подобия, так и извлечения дополнительной информации. Работа с коллекцией доку- ментов предполагает наличие процедур по формированию – подборке документов, каждый из которых может быть представлен разным объемом и отнесен к разному корпусу. Такие проце- дуры можно обнаружить при исполнении человеком творческой задачи анализа коллекции до- кументов.
4.5 Организация процедур бустинга
Простой алгоритм бустинга реализуется на основе статистического метода анализа тек- ста, применяемого к обучающим данным, где по результатам наблюдения за элементами текста определяется их частота. При работе с массивом документов – корпусом, исполняется процеду-

Системный анализ и принятие решений Макаров Л.М.
70 ра наблюдения за элементами корпуса (множества), а затем выполняется процедура вычисле- ния весовых коэффициентов для элементов корпуса. Укажем, что процедуры бустинга могут составлять основы различных обучающих методов, которые не поддерживают в явном виде ве- са или цены ошибок классификации. В этом случае случайное взятие подвыборок из выборок может применяться к обучающим данным на последовательных шагах итеративной процедуры повышения точности добычи знаний, где вероятность выбора наблюдения в подвыборке обрат- но пропорциональна точности прогноза для наблюдения на предыдущей итерации бустинга.
Процедуры извлечения знаний из текстового массива формируются на представлении о векторной модели текста, основу которой составляют статистические понятия о распределении элементов текста. Векторная модель текста сформировалась на классических принципах стати- стики позволявших создать образ текстового материала в виде векторов в пространстве призна- ков. Принимая это за основу можно указать, что любой текст может быть поставлен в соответ- ствие точке в многомерном пространстве признаков, каждая координата которой соответствует частоте одного из его слов. Если допустить, что сходные мысли выражаются сходными слова- ми, то можно предположить, что тексты сходной тематики будут соответствовать простран- ственно-близким векторам.
Очевидно, тематика обычно не зависит от длины текста, поэтому вектора нормируют, чтобы они также не зависели от длины. Для нормированных векторов в качестве меры про- странственной близости удобно использовать косинус угла между ними: эта величина легко рассчитывается скалярным произведением векторов.
Простейшим применением векторной модели текста является классификация: выявление принадлежности текста одной из нескольких классификационных категорий. Другое очевидное применение - полнотекстовый поиск, который широко используется в поисковых системах.
Идея полнотекстового поиска состоит в том, чтобы не просто находить ключевые слова в тексте, но учитывать их значение (семантическую составляющую) в тексте и предоставлять возможность ранжировать тексты по степени соответствия запросу. Векторная модель позволя- ет это сделать на основе предположения о том, что ключевое слово определяет тематику текста пропорционально частоте встречаемости. Это позволяет ранжировать текстовые документы в базе данных по степени релевантности запроса. Такая процедура осуществляется на основе скалярного произведения векторов, представляющих текст и запрос. Такой подход хорошо сра- батывает при необходимости найти тексты с тематикой, близкой к заданному тексту. Хотя ис- пользование его на коротких поисковых фразах приводит к менее впечатляющим результатам, это не мешает ему быть теоретической основой практически всех алгоритмов полнотекстового поиска.
Тексты, являющиеся искаженной копией друг друга, порождают крайне близкие векто-

Системный анализ и принятие решений Макаров Л.М.
71 ра. Это обстоятельство дает основание применять исключительно статистические методы сопо- ставления текстовых документов. Эта близость много выше, чем близость текстов сходной те- матики. Поэтому нахождение векторов, особенно близких к вектору, представляющему данный текст, может использоваться для поиска дубликатов текста.
В последнее время, в связи с особенным увлечением человечества проблемой копирайта, появился ряд алгоритмов, построенных на этой основе, например алгоритм Шинглов. Реализа- ция алгоритма подразумевает несколько этапов:
• канонизация текстов;
• разбиение текста на шинглы - элементы
• нахождение контрольных сумм текстов
• поиск одинаковых подпоследовательностей
В алгоритме шинглов реализовано сравнение контрольных сумм текстов. Как известно, контрольные суммы статических функций очень чувствительны к изменениям. Алгоритм вы- числения контрольной суммы — способ цифровой идентификации некоторой последователь- ности данных, который заключается в вычислении контрольного значения ее циклического из- быточного кода. Полагая, что любой текст можно представить в виде набора слов – последова- тельных элементов, постулируется возможность реализации процедуры вычисления контроль- ных значений циклического избыточного кода.
Алгоритм нахождения контрольных сумм текстов базируется на свойствах деления с остатком двоичных многочленов. Текущие значения являются остатком от деления многочле- на, соответствующего входным данным, на некий фиксированный порождающий многочлен.
Например, конечной последовательности битов взаимнооднозначно со- поставляется двоичный многочлен
, последовательность коэффициентов кото- рого представляет собой исходную последовательность. Например, последовательности битов
1011010 соответствует многочлен:
Алгоритм нахождения контрольных сумм можно отнести к процедуре хеширования - создания хеш функции. Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свертки, а их результаты называют хешем, хеш-кодом или

Системный анализ и принятие решений Макаров Л.М.
72 дайджестом сообщения. Сопоставление дайджест сообщений позволяет установить их подобие.
Для выявления скрытых связей элементов текстового массива часто используется вос- произведение визуального образа. Распределение текстов в пространстве признаков можно ви- зуализировать. При этом в пространстве признаков находится поверхность, оптимальная с точ- ки зрения информативности проекции на нее, и распределение векторов в пространстве пред- ставляется проекцией на эту поверхность. Такое представление называют «картой признаков»: плотность распределения векторов выражается яркостью или цветом соответствующих участ- ков карты. На визуальном поле хорошо заметно, что в распределении текстов существует некий порядок: существуют области, в которых тексты группируются вместе, и которые разделены участками с низкой плотностью распределения векторов. Исследование таких областей пока- зывает, что они соответствуют текстам сходной тематики, что позволяет использовать карту признаков для навигации по коллекции текстов.
Для организации навигации по коллекции текстов используются процедуры кластериза- ции. Так как различным областям распределения векторов можно поставить в соответствие различные темы, то на этой основе можно создать набор кластеров, который выявляет принад- лежность исходного текста к различным тематическим группам. Типичную процедуру класте- ризации текста и коллекции текстовых документов осуществляет модель нейронной сети Ко- хонена-Гроссберга. Это модель нейронной сети встречного распространения.
По своим возможностям сети встречного распространения превосходят возможности однослойных сетей. Во встречном распространении объединены два хорошо известных алго- ритма: самоорганизующаяся карта Кохонена и звезда Гроссберга. При этом появляются свой- ства, которых нет ни у одного из них в отдельности. Методы, которые, подобно встречному распространению, объединяют различные сетевые парадигмы как строительные блоки, могут привести к сетям, более близким по архитектуре к мозгу, чем любые другие однородные струк- туры. Похоже, что в естественном мозге именно каскадные соединения модулей различной специализации позволяют выполнять требуемые вычисления.
Сеть встречного распространения функционирует подобно «интеллектуальному агенту», способному к обобщению. В процессе настройки сети входные векторы ассоциируются с соот- ветствующими выходными векторами. Они могут быть двоичными, состоящими из нулей и единиц, или непрерывными. Когда сетьнастроена, приложение входного вектора приводит к требуемому выходному вектору. Обобщающая способность сети позволяет получать правиль- ный выход даже при приложении входного вектора, который является неполным или слегка искаженным (зашумленным). Таким образом, возможно, использовать данную сеть для распо- знавания образов, восстановления образов и усиления сигналов (рис. 4.6).

Системный анализ и принятие решений Макаров Л.М.
73
Рисунок 4.6 Структура сети обратного распространения
Нейроны слоя 0 (показанные кружками) служат лишь точками разветвления и не выпол- няют вычислений. Каждый нейрон слоя 0 соединен с каждым нейроном слоя 1 (называемого слоем Кохонена) отдельным весом Wij. Эти веса в целом рассматриваются как матрица весов
W. Аналогично, каждый нейрон в слое Кохонена (слое 1) соединен с каждым нейроном в слое
Гроссберга (слое 2) весом V ij. Эти веса образуют матрицу весов V.
Множество весов нейронов Кохонена связывает каждый нейрон с каждым входом. По- добно нейронам выход, именуемый NET каждого нейрона Кохонена является суммой взвешен- ных входов. Формально это записывается в виде: где
j
NET
— это выход J нейрона Кохонена,
Нейрон Кохонена с максимальным значением NET является «победителем». Его выход равен единице, у остальных он равен нулю.
Сеть Кохонена специальный тип нейронной сети, позволяющий производить кластери-
ij
i
i
x w
NET
1
j

=
=

Системный анализ и принятие решений Макаров Л.М.
74 зацию объектов. Сеть Кохонена состоит всего из двух слоев – входного и выходного (рис. 4.7).
Выходной слой часто называется «слой Кохонена». Каждый нейрон входного слоя связан со всеми нейронами выходного, а внутри слоев связей нет. На нейроны входного слоя подаются векторы признаков кластеризуемых текстов. Как и в обычной нейронной сети, входные нейро- ны не участвуют в процессе обучения и обработки данных, а просто распределяют входной сигнал по нейронам следующего слоя. Число входных нейронов равно размерности вектора признаков т.е. числу признаков исследуемого текста. Формально можно говорить о процедуре соотнесения некоторого входного объекта (документа) одному из кластеров, для которого до- бавление нового объекта не изменяет внутренней топологической целостности.
Количество выходных нейронов сети Кохонена равно числу кластеров, которое должно быть построено моделью, и каждый нейрон ассоциирован с определенным кластером. Выходы обрабатываются по принципу «победитель забирает все», т.е. нейрон с наибольшим значением выхода выдает единицу, а остальные обращаются в 0.
Рисунок 4.7 Схема нейронной сети Кохонена
Таким образом, в результате обработки предъявленного сети объекта, на выходе одного из нейронов формируется 1, а на выходе остальных – 0. После чего объект относится к класте- ру, ассоциированному с единичным нейроном. Нейронная сеть позволяет проводить формиро- вание кластерного пространства, как с «учителем» так и посредством процедур самонастройки.
Обучение сети Кохонена является самообучением, протекающим без учителя. Очень важно, что в процессе работы с такой сетью не возникает необходимости уточнять какой именно нейрон сети Кохонена будет активироваться для заданного входного вектора. Необходимо лишь гаран- тировать, чтобы в результате обучения разделялись несхожие входные векторы.
Слой Гроссберга функционирует аналогично. Выход NET является взвешенной суммой выходов k1, k2, ….., kn, слоя Кохонена, образующих вектор K. Вектор соединяющих весов, обозначенный через V, состоит из весов v1, v2, …..,vij . Тогда выход NET каждого нейрона
Гроссберга реализует процедуру: