Рисунок 9 - Пример класса эквивалентности
В соответствии с рисунком 9, на корпусе CHILDES, например, образуется класс эквивалентности, представляющий собой имена людей.
Еще один пример выделения класса эквивалентности на основе корпуса газетных статей приведен на рисунке 10.
Рисунок 10 – Пример класса эквивалентности
Каждый вновь полученный класс эквивалентности сохраняется в глобальном массиве как объект, имеющий следующую структуру:
E: make object!
[
name: "" ; имя класса эквивалентности
nodes: [] ; узлы, которые в него входят
]
3.5 Образование новых узлов графаПроцесс выделения структур в исходном тексте носит итеративный характер. В соответствии с рисунком 11, на каждой итерации новый узел образуется на основе уже существующих.
Рисунок 11 - Создание нового узла P
Полученный с помощью алгоритма MEX значимый шаблон с возможно входящим в него классом эквивалентности сворачивается в новый узел и добавляется к уже существующему графу составляющих. При этом происходит перераспределение информации о соседях как вновь образованного узла, так и бывших самостоятельных узлов, входящих в этот новый узел.
Рисунок 12 - Графическое изображение узла и его ближайших соседей
На рисунке 12 изображен пример одного из полученных в результате работы алгоритма ADIOS узлов. Синими кружками отмечен сам узел, зелеными ромбами – класс эквивалентности. Этот узел имеет вложенную структуру, так как включает в себя еще один узел с его классом эквивалентности.
Ниже приведены некоторые результаты, полученные при тестировании алгоритма на небольших фрагментах текстов:
один из текстов Национального корпуса русского литературного языка (1400 слов – 843 уникальных): найдено 163 класса эквивалентности и 45 значимых шаблонов текст из корпуса CHILDES (2020 слов – 27 уникальных): найдено 13 классов эквивалентности и 4 значимых шаблона 3.6 Отрисовка построенного графа составляющихДля визуализации построенных структур (графа составляющих, полученных новых узлов) используется несколько инструментов:
написанная на языке REBOL программа, имеющая достаточно ограниченный набор возможностей; также написанная на языке REBOL программа, представляющая собой усовершенствованный вариант предыдущей; специальный редактор графов yEd, позволяющий использовать специальный язык разметки для отображения графа; 3.6.1 Первая реализация программы отрисовки графаВ соответствии с рисунком 13, при рисовании графа решено было изображать текущий узел, двух его ближайших соседей (предок и потомок), а также указывать стрелочками связи.
Рисунок 13 - Графическое изображение узла и его ближайших соседей
Для отображения на экране данной структуры необходимо было создать набор типа «стрелка» (Arrow):
Arrows: make object!
[
text1: "" ; название узла начала стрелки
text2: "" ; название узла конца стрелки
id1: 321 ; идентификатор узла начала стрелки
id2: 432 ; идентификатор узла конца стрелки
params_block: [] ; описание отображения стрелок (для
lock)
]
и набор поверхностей, представляющих собой узлы графа.
В соответствии с рисунком 14, если узлов в графе слишком много, и они «наезжают» друг на друга при отрисовке, для лучшего рассмотрения их можно перетаскивать мышью.
Рисунок 14 – «Перетаскивание» нужных узлов графа
Для того чтобы посмотреть содержимое узла – потомка или предка текущего узла - была создана специальная функция, вызывающаяся при нажатии левой кнопки мыши, вызывающая перерисовку основного экрана для отображения нужного узла.
Рисунок 15 - Выделение цветом пути в графе
В соответствии с рисунком 15, черным цветом в графе отмечаются пути, связывающие между собой слова, принадлежащие к одному и тому же предложению.
В соответствии с рисунком 16, «перетаскиваемы вершины» выделяются специальным цветом.
Рисунок 16 - Выделение цветом «перетаскиваемого» узла
Очевидным недостатком рассмотренной выше версии программы отрисовки графа является невозможность увидеть общую картину (часть полного графа или весь граф целиком). Также невозможно получиться представление о том, как много путей имеет рассматриваемый граф. Поэтому было решено переписать данную программу, полностью изменив принципы отображения.
3.6.2 Усовершенствование программы отрисовки графаВ ранее написанную программу изображения графа были внесены существенные изменения, как со стороны интерфейса, так и со стороны графического представления.
Просмотр связей между вершинами графа может осуществляться в двух режимах:
- показать предков и потомков отдельно взятой вершины показать связи вершин в пределах одного предложения
Рисунок 17 - Интерфейс программы отрисовки графа составляющих
Для отображения на экране данной структуры необходимо было создать набор типа «стрелка» (Arc):
Arc: make object!
[
begin: none ;координаты начала и конца
end: none
]
и набор поверхностей, представляющих собой узлы графа.
На рисунке 17 слева видна панель навигации по отдельным вершинам графам, внизу – по предложениям. В центре расположена основная область для изображения фрагмента графа. Различные предложения показаны разными цветами. Узлы begin и end выделены синим, а узлы, принадлежащие к рассматриваемому предложению – красным.
3.6.3 Использование готового программного продукта для отрисовки графаКак уже было упомянуто выше, в качестве инструмента для графического представления полученных в результате работы алгоритма новых узлов был использован редактор графов yEd. Он позволяет создать текстовый файл специального формата, на основе которого программно будет создана визуализация пользовательского графа.
Редактор поддерживает несколько форматов описания структуры графа, одним из которых является GML (Graph Modeling Language).
Основными элементами файла GML являются:
graph – собственно описание самого графа, контейнер для всех остальных элементов; node – описание узла графа; для него можно задать уникальное имя или идентификатор, а также отображаемую метку узла; edge – ребро графа; задаются узлы начала и конца ребра, а также необязательная метка; служебные элементы LabelGraphics и graphics (имеют разные свойства для элементов node и edge), позволяющие задавать способы отображения узлов, меток и дуг (координаты, цвет, относительное позиционирование, размер и т. д.).Примером разметки GML может послужить следующий фрагмент кода:
graph
[
hierarchic 1
directed 1
defaultnodesize "labelsize"
defaultnodeinsetshorizontal 1
defaultnodeinsetsvertical 1
node
[
name "P*1"
label "P*1"
graphics
[
w 60
h 60
dropShadowColor "#112233"
dropShadowOffsetX 3
dropShadowOffsetY 1
fill "#61E276"
type "circle"
]
LabelGraphics
[
fontSize 16
type "text"
color "#000000"
]
]
node
[
name "E*4"
label "E*4"
graphics
[
w 60
h 60
dropShadowColor "#112233"
dropShadowOffsetX 3
dropShadowOffsetY 1
type "diamond"
]
LabelGraphics
[
fontSize 16
type "text"
color "#000000"
]
]
edge
[
source "P*1"
target "E*4"
]
]
Таким образом, на заключительной стадии работы алгоритма, когда иерархическая структура новых узлов уже построена, для каждого такого узла создается его описание в формате GML и сохраняется в текстовом файле с расширением «.gml». После этого все такие файлы могут быть просмотрены с помощью редактора yEd.
ЗаключениеВ результате работы над дипломом была создана программа, воспроизводящая алгоритм автоматического (неуправляемого, исключающего вмешательство человека) извлечения иерархически устроенных структур. Под такими структурами понимаются выявленные с помощью статистических вероятностных функций последовательности единиц исходного текста. Текст никак не размечается заранее, до начала запуска алгоритма. Таким образом, на входе алгоритм не имеет в своем распоряжении предварительных данных, которые могут каким-то образом повлиять на работу программы.
Получая и обрабатывая тексты, программа имитирует процесс обучения, выявляя грамматические закономерности, лежащие в основе текстовой конструкции. Подобное поведение может быть интересным в рассмотрении вопросов, связанных с исследованиями в области языка.
Список использованных источников Solan, Z., Horn, D., Ruppin, E., Edelman, S. Unsupervised Context Sensitive Language Acquisition from a Large Corpus // NIPS, 2003. Эфрос и геометрия беспорядка / // Гл. редакция физ.-мат. литературы. – M.: Издательство «Наука», 1982. – С.270. Dorogovtsev S. N., Mendes J. F.F. Evolution of Networks / S. N. Dorogovtsev, J. F.F Mendez // Oxford. – 2003. – C.271. Solan, Z., Horn, D., Ruppin, E., Edelman, S. Unsupervised language acquisition: syntax from plain corpus // NIPS, 2004. Solan Z., Edelman S. Automatic acquisition and efficient representation of syntactic structures / S. Thrun // Cambridge: MIT Press, 2003. Solan, Z., Horn, D., Ruppin, E., Edelman, S. Unsupervised learning of natural languages // Natl. Acad. Sci. – 2005. Solan, Z., Ruppin, E., Horn, D., Edelman, S., Automatic acquisition and efficient representation of syntactic structures // NIPS, 2002. Русские словари [Электронный ресурс] / Академия Наук СССР, Институт русского языка им. . - Электрон. дан. - Россия, 2003. - Режим доступа: http://slovari. donpac. ru/, свободный. - Загл. с экрана. Zach Solan. Unsupervised learning of natural languages [Текст] : дис. …doctor of philosophy : защищена May 2006 / Zach Solan. – 2006. – 121 с. – Библиогр.: с.110–120. Solan, Z., Horn, D., Ruppin, E., Edelman, S. Bridging computational, formal and psycholinguistic approaches to language // NIPS, 2003. Solan, Z., Horn, D., Ruppin, E., Edelman, S. Rich syntax from a raw corpus: unsupervised does it // NIPS, 2003. Solan, Z., Horn, D., Ruppin, E., Edelman, S. Unsupervised efficient learning and representation of language structure // NIPS, 2003.
Дипломная работа выполнена мною самостоятельно. Использованные в работе материалы из опубликованной научной, учебной литературы и Интернет имеют ссылки на них.
Отпечатано в ____ экземплярах.
Библиография 12 наименований.
Один экземпляр сдан на кафедру.
____________________ «____» _____________ 2007 г.
1 Под степенью вершины понимается общее число связей данной вершины с соседними вершинами.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
