Диссертация (1137218), страница 4

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

Текст из файла (страница 4)

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

раздел1.4.3) уровням, причем на семантическом уровне рассматриваются впервую очередь дискурсивные связи. Важно отметить, что модельвключает в себя не только полное, но и приближенное (такназываемая проекция, подробнее см. 2.5.1), более эффективное свычислительной точки зрения представление текстового абзаца, атакже ассоциативную и коммутативную операция вычислениясходства между текстовыми абзацами (подробнее см. раздел 2.4).Именно эти особенности модели и обусловливают её новизну посравнению с уже существующими моделями (подробнее см. раздел1.4.4) и позволяют применять её в прикладных задачах.Помимо модели текстового абзаца в диссертации такжепредлагается новая модель тождественных денотатов (подробнее см.раздел 4), формально описывающая представление и обработкуодного из типов дискурсивных связей, существующих внутритекстового абзаца.1.2 Анализ формальных понятий и решетки замкнутых описанийОднойизактивноприменяемыхвисследованииматематических теорий является анализ формальных понятий [26] иего расширение ‒ решетки замкнутых описаний.

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

Решетка одновременно является и весьма удобныммоделью представления знаний, допускающим различные уровнидетализации, и весьма проработанным и развитым средством дляработы с данными.Эти свойства делают решетки весьма привлекательными в планеприменения к задачам обработки текста, поскольку уже существуют иизвестны самые разные способы и модели, позволяющие построитьформальное описание текста на синтаксическом и семантическомуровне.1.2.1 Частично упорядоченные множества и решеткиНиже приведены основные определения из теории решеток [1],широко используемой как в теоретических, так и в прикладныхобластях дискретной математики, в частности, в анализе формальныхпонятий [26].Определение 1.1. Бинарное отношениемножествеSна некоторомназывается отношением (нестрогого) частичногопорядка, если для s, t, u  S :1.

≤ (рефлексивность);2. Если ≤ и ≤ , то = (антисимметричность);3. Если ≤ и ≤ , то ≤ (транзитивность).Множество S с определённым на нем отношением частичногопорядка ≤ (частично упорядоченное множество) обозначается  S ,   .20Если ≤ , то говорят, что элемент меньше, чем , или равен ему.Если для не существует , такого что ≤ , то называютмаксимальным элементом (относительно ≤).

Если ≤ и s  t , топишут < и говорят, что строго меньше, чем .Определение1.2. S ,   частично упорядоченноеПустьмножество. Элемент ∈ называется соседом снизу элемента ∈ ,если < и v  S : l  v  u . В этом случае называется соседомсверху (обозначается ⪯ ). Направленный граф отношения ⪯называется графом покрытия.Графически конечное частично упорядоченное множество  S ,  может быть представлено с помощью диаграммы частичного порядка[1]. Элементы изображаются в виде точек. Если ⪯ , то размещается«над»(вертикальнаякоординатабольшевертикальной координаты ), и две точки соединяются линией.Определение1.3.Верхнейграньюподмножествавупорядоченном множестве называется элемент ∈ , такой что ≥ для всех ∈ .Точнаяверхняяграньнаименьшейверхнейграньюмножестваили(называемаясупремумом)такжемножества(обозначается sup) есть верхняя грань такая, что ≤ 1 для любойверхней грани 1 подмножества .Двойственным образом (с заменой ≥ на ≤) определяется понятиеточной (наибольшей) нижней грани или инфимума inf.Определение 1.4.

Бинарная операция ⊓: × → называетсяполурешёточной, если для некоторого ∈ и любых , , ∈ :1. ⊓ = (идемпотентность);212. ⊓ = ⊓ (коммутативность);3. ( ⊓ ) ⊓ = ⊓ ( ⊓ ) (ассоциативность);4. ⊓ = .Для = {1, . . . , } ⊆ и ∈ N мы пишем ⊓X вместо x1 ⊓ . . .⊓ x .Если X = {x}, то ⊓X = x.Определение 1.5. Множество с определённой на немполурешёточной операцией ⊓ называется полурешёткой (, ⊓).Полурешёточная операция ⊓ задает два частичных порядка ⊑ и⊒ на (, ∈ ): ⊑ ⇔ ⊓ = и ⊒ ⇔ ⊓ = .Тогда множество с определённой на нем полурешёточнойоперацией (,⊓) будем называть нижней полурешёткой (относительночастичного порядка ⊑) и верхней полурешёткой (относительночастичного порядка ⊒).Определение 1.6.

Пусть (,⊓) — полурешётка. Множество ⊆ называется системой замыканий [26] или семейством Мура [1](относительно ⊓), если ∀, ∈ : ⊓ ∈ .Очевидно, что система замыканий (относительно ⊓) сопределённой на ней операцией, ∧: × → и ∧ = ⊓ ,образует полурешётку.Определение1.7.Упорядоченноемножество(,≤)сопределёнными на нем полурешёточными операциями ∧ и ∨называется решёткой, если (,∧) и (,∨) являются, соответственно,нижней и верхней полурешётками (относительно ≤).Операции ∧ и ∨ называют операциями взятия точной нижней иверхней грани в решётке или инфимума и супремума, соответственно.22Определение1.8.Подрешёткойрешёткиназываетсяподмножество ⊂ такое, что если ∈ , ∈ , то ∧ ∈ и ∨ ∈ .Полурешёточные операции ∧ и ∨ удовлетворяют в решёткахследующему условию: ∧ ( ∨ ) = ∨ ( ∧ ) = (поглощение).Из любой конечной полурешётки можно получить решёткудобавлениемодного(максимальногоилиминимальноговзависимости от типа полурешетки) элемента.Решётка называется полной, если у каждого подмножества егоэлементов есть супремум и инфимум (всякая конечная решёткаявляется полной).Определение1.9.Пусть(,≤)и(,≤)—частичноупорядоченные множества.

Пара отображений : ↦ и : ↦ называется соответствием Галуа между частично упорядоченнымимножествами (,≤) и (,≤ ), если для любых ∈ и ∈ :1. 1 ≤ 2 ⇒ (2) ≤ (1);2. 1 ≤ 2 ⇒ (2) ≤ (1);3. ≤ (())4. ≤ (()).1.2.2 Анализ формальных понятийАнализ формальных понятий (АФП) [26] - это прикладная ветвьтеории решеток [1]. Основные сущности АФП были формальноописаны Рудольфом Вилле в 1982 году. С точки зрения анализаданных, методы, основанные на анализе формальных понятий,относятсякметодамбикластеризации(объектно-признаковойкластеризации). В АФП рассматриваются не кластеры объектов,23оторванных от исходного описания, а группы объектов и признаков,сильно связанных друг с другом.Определение 1.10. Формальный контекст K есть тройка(G, M , I ) , где G - множество, называемое множеством объектов,M-множество,называемоемножествомпризнаков,I  G  M - бинарное отношение.Отношение I интерпретируется следующим образом: для g  G,m  M gIm выполнено тогда и только тогда, когда объект g обладаетпризнаком m.Определение 1.11.

Для формального контекста K  (G, M , I ) ипроизвольных A  G, B  M определена пара отображений:A  m  M | g Im g  A , B   g  G | g Im m  B .Эти отображения задают соответствие Галуа между частичноупорядоченными множествами (2G , ) и (2M , ) , а операторы ()являются операторами замыкания на G и M. Иными словами, дляпроизвольного A  GA Mилиимеютместоследующиесоотношения [26]:1. A  A (экстенсивность),2. A  A (идемпотентность),3. если A  C , то A  C (изотонность).Определениеконтекста1.12.K  (G, M , I )Формальноеестьпарапонятие(A,B),гдеформальногоA  G, B  M ,A  B, B  A. Множество A называется объёмом, а B - содержаниемпонятия (A,B).24Для двух формальных понятий (A,B) и (C,D) некоторогоконтекста(A,B)называетсяподпонятием(C,D),еслиAC(эквивалентно D  B ).

В этом случае (C,D) является надпонятием(A,B).Множество формальных понятий контекста K, упорядоченныхпо вложению объемов (содержаний), образует решетку формальныхпонятий  ( K ) .1.2.3 Решетки замкнутых описанийАФП преобразует формальный контекст, представленный какбинарное отношение, в решетку формальных понятий, но во многихслучаях исследуемые «объекты» могут иметь более сложноеописание, чем множество некоторых наперед заданных признаков.Например,исследуямножествообъектов,возможнолиихисследовать без выделения специальных бинарных признаков?Узорные структуры (pattern structures) дают ответ на этот вопрос,являясь расширением АФП для работы со сложными данными [90],такимикакданные,описываемыечисленнымизначениями,множествами последовательностей или графов.Определение 1.13.

Узорная структура – это тройка (G, (D,⊓), δ),гдеG–множествообъектов,(D,⊓)–полнаяполурешеткавсевозможных описаний, а δ: G → D – функция, которая сопоставляеткаждому объекту из множества G его описание из D.Полурешеточная операция ⊓ соответствует операции сходствамежду двумя описаниями.1.2.4 Проекции решеток замкнутых описанийПоскольку размер решетки узорных понятий может бытьсущественным, а сама решеточная операция – асимптотически25сложной (например, для построения узорной структуры на графахнеобходимо вычислять изоморфизм подграфов), построение решеткиузорныхпонятийможетзаниматьсущественноевремя.Дляуменьшения этого времени были введены проекции узорных структур[90].

Характеристики

Список файлов диссертации