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

Обосновывается возможность вычислятьсемантическое расстояние как меру семантической схожести (основана толькона отношении порядка), которая является приближением при вычислениисемантической связности (определяется по совокупности всех семантическихотношений) и может заменять использование меры связности в актуальныхзадачах ВОС.В разделе 3.3 предлагается метод вычисления меры схожести для ФП Ci иCj решетки:Dc|B|spc(Ci , C j ) = − log(1 −)×,(8)pathc | Bi \ B | + | B j \ B | + | B |где ФП C=(A,B) – Наибольшее Общее Суперпонятие (НОСП) для формальныхпонятий Ci=(Ai,Bi) и Cj=(Aj,Bj), D( ⊥ ,C) – кратчайшее расстояние между ФП C и⊥ , Dc – кратчайшее расстояние между ФП C и , pathC = Dc+D( ⊥ ,C).В разделе 3.4 приводится алгоритм сегментации решетки для целейвыделения интерпретируемых классов (сортов).

Результатом работы алгоритмасегментации является набор классов ФП {L’}, также являющихся решетками.Классы максимальны по количеству элементов, количество элементов классовне задается перед началом работы алгоритма. Критерием выделения решеткиLi ∈ {L′} из первоначальной формальной решетки L является условие, чтокаждое ФП C ∈ Li более схоже с другими формальными понятиями из решетки11Li , чем с формальными понятиями из решеток L j ∈{L′} , что i≠j. Итоговыйалгоритм сегментации решетки описывается так:Шаг 0. Получить из размеченного корпуса текстов формальный контекст Kg;сгенерировать на его основе формальную решетку L;Шаг 1.

В массив LCS_Array записать все формальные понятия C ∈ L , чтоCp ;Шаг 2. Для каждого ФП Ci из LCS_Array, где i=1 до Ni (Ni – количествоэлементов массива LCS_Array);Шаг 2.1. Пусть Li – i-ый класс формальных понятий, тогда Li:= Ci ;Шаг 2.2. Для каждого ФП Cj, что Cj<Ci и Cj≠ ⊥ , где j=1 до Nj (Nj – количествоподпонятий ФП Ci);Шаг 2.2.1. Если для каждого C m ∈ L , что C j p C m , также выполняется Cm≤Ci, тоLi:= Li+Cj и пропустить Шаг 2.2.2 и Шаг 2.2.3, иначе отметить Cj как спорноеФП и выполнить Шаг 2.2.2 и Шаг 2.2.3;Шаг 2.2.2. Для спорного ФП Cj вычислить d1:=spc(Cj, Cm) и d2, равноемаксимальному из значений spc(Cj, Ch), где h – номер ФП, что выполняетсяC j p C h и C h ≤ Ci .Если d1=d2, то сравнить количество ( d 2′ ) ФП в области, где НОСП является ФПCi, и количество ( d1′ ) ФП в области, где НОСП является ФП C M p и C m ≤ C M ,и количество ФП максимально по сравнению с другими областями, к которымпринадлежит ФП Cm.

Если d 2′ ≥ d1′ , то выполнить Шаг 2.2.2.1, иначе выполнитьШаг 2.2.2.2.Если d2>d1, тоШаг 2.2.2.1. Вариант 1: для каждого из объектов a j из объемов ФП, меньшихлибо равных Cj, выполнить а) – г):а) добавить в формальный контекст Kg два объекта: a j _ Bi и a j _ BM , гдеCM=(AM,BM), C M p и C m ≤ C M ;б) добавить в формальный контекст Kg отношения a j _ Bi I g bq для каждогоbq ∈ B j такое, что также выполняется bq ∈ Br для каждого ФП Cr=(Ar,Br), чтоCr ≤ Ci и C j p C r , и отношения a j _ BM I g b p для каждого b p ∈ B j такое, что такжевыполняется b p ∈ Bm ;в) для каждого признака b jo ∈ B jo из подмножества признаков B jo ⊆ Bkсодержания формальных понятий Ck, таких, что C k = ( B ′jo , B ′jo′ ) и Ck≤Cj,выполнить:• добавить в формальный контекст Kg два признака b jo _ 1 и b jo _ 2 , если такиепризнаки не были добавлены на предыдущих итерациях данного Шага;• добавить в формальный контекст Kg отношения a j _ Bi I g b jo _ 1 и a j _ BM I g b jo _ 2 ,если такие признаки не были добавлены на предыдущих итерациях данногоШага;12• добавить в формальный контекст Kg отношения a t I g b jo _ 1 и a t I g b jo _ 2 для всехобъектов at из объема подпонятий ФП Ck, если они уже не содержатся вконтексте Kg;• отметить признак b jo и все отношения этого признака с объектами контекстаKg на удаление;г) отметить объект a j и все отношения этого объекта со всеми признакамиконтекста Kg на удаление.Удалить из формального контекста Kg все объекты и их признаки, а также всепризнаки и их отношения, помеченные на удаление.Шаг 2.2.2.1.

Вариант 2: для каждого признака b j ∈ B j , Cj=(Aj,Bj), для котороготакже выполняется b j ∈ Bm , удалить из формального контекста Kg отношение Igдля признака b j , что a j I g b j для всех объектов a j из объема ФП Cj(полное переформирование решетки L не требуется, возможно тольконеобходимо объединить ФП Cj с ФП Ch, если после удаления из контекстапризнаков выполняется Bj=Bh),иначе если d1>d2, тоШаг 2.2.2.2.

Вариант 1: Аналогично Шаг 2.2.2.1, Вариант 1.Шаг 2.2.2.2. Вариант 2: для каждого признака b j ∈ B j , Cj=(Aj,Bj), для котороготакже выполняется b j ∈ Br для каждого ФП Cr=(Ar,Br), что Cr ≤ Ci , выполнить:удалить из формального контекста Kg отношение Ig для признака b j , что a j I g b jдля всех объектов a j из объема ФП Cj;(полное переформирование решетки L не требуется, возможно, иногданеобходимо объединить ФП Cj с ФП Cm, если после удаления из контекстапризнаков выполняется Bj=Bm).Шаг 2.2.3.

Если на Шаге 2.2.2 для каждого C m ∈ L выполнялось только условиеd2>d1 и Вариант 2, то Li:= Li+Cj, иначе, если выполнялся Вариант 1 и условиеd2>d1 или d1>d2, то после переформирования первоначальной решетки найти вней ФП с объемом, в котором содержатся все объекты a j _ Bi , где a j ∈ A j иCj=(Aj,Bj) – спорное ФП первоначальной решетки.

Далее выполнять алгоритмпо переформированной решетке.Шаг 3. К множеству формальных понятий Li добавить наименьшее ФП ⊥ .Добавить решетку Li к итоговому множеству формальных решеток {L’}.В четвертой главе описываются методы поиска ответов в ВОС спомощью КОЛ. Анализируется представление в КОЛ лексики различныхтипов. Рассматривается метод снятия семантической омонимии слов в объемеформальных понятий.В разделе 4.2 описываются архитектура типовой ВОС и модули системы,в которых происходит обращение к лексическим знаниям. На Рисунке 3представлена диаграмма потоков данных типовой ВОС.13ЛексическиезнанияРасширение вопросаМножество (qi, wi)ключевых словвопроса с весамиРасширениевопросаЗапросИзвлечение параграфовпоисковой системойДеревосинтаксическихзависимостейвопросаСемантическийкласс вопросаОценка параграфовВопросАнализ вопросаФорма вопросаНабор параграфовс указаниемрелевантности(Pi,ri)Оценка параграфовОценкаНабор параграфовпараграфовс указаниемоценки(Pi,ei)Извлечение ответов из параграфовЛексическиезнанияПредварительныеответыУдаление избыточности в ответахОкончательныеответыУдалениеизбыточностив ответахЛексическиезнанияРисунок 3.

Диаграмма потоков данных типовой ВОС.В разделе 4.3 рассматриваются два подхода к классификации вопросов:классификация по форме ответов и семантическая классификация ответов.Семантическая классификация вопроса задает семантический класс, к которомудолжны принадлежать вопрос и набор ответов.

Чем выше детализациясемантических классов, тем более точно можно сравнить вопрос и ответ,поэтому использование специализированного, пополняемого в автоматическомрежиме и содержащего детальные семантические классы лексикона являетсяпреимуществом ВОС. Рассмотрено применение КОЛ при сопоставлениисемантического класса вопроса с извлеченными из поисковой системыпараграфами, которое учитывается ВОС при определении оценок параграфов.Семантический компонент в оценке параграфов вычисляется по формуле:⎧1, еслиC a = C q⎪⎪Spc L (C a , C q ), еслиC a < C q илиC a > C qSemType _ score = ⎨,min(Spc L (C a , C ), Spc L (C q , C )), если∃C ∈ Lv |⎪¬⎪CC&CC&Ch | Ck < C & Cq < Ck & Ca < Ck<<∃a⎩ qvvv14(9)где q – главное ключевое слово вопроса, a – ключевое слово ответа впараграфе, C q = (q ′′, q ′) , C a = (a ′′, a ′) , Lv – решетка КОЛ, Spc L (C x , C y ) – мерасхожести между ФП Cx и Cy, нормированная к максимальному значению мерысхожести для всех ФП решетки Lv, ФП С – НОСП ФП C q и C a .В разделе 4.4 исследуются свойства КОЛ.

Анализируется спецификапредставления в КОЛ собирательных и абстрактных существительных. Врешеткеформальных понятий собирательныесуществительныеисоответствующие им конкретные существительные не связаны отношениемпорядка. Показано, что для ВОС отсутствие отношения порядка позволяетиспользовать собирательные существительные при сопоставлении типа вопросаи ответа по формуле (9). Проверка объема покрытия абстрактныхсуществительных выполнена относительно спискасуществительных,обозначающих эмоции, из частотного словаря Шарова. Степень покрытия КОЛ,построенного на основе ГК, извлеченных из корпуса «Классика» библиотекиМошкова, составляет 94%.

Показано, что ФП, к объему которых принадлежатабстрактные существительные, образуют в КОЛ классы, которые возможновыделить с помощью алгоритма сегментации решетки.Для использования КОЛ в ВОС разработан метод снятия семантическойомонимии слов в объеме формальных понятий, который предполагает работуалгоритма сегментации по Варианту 1. Работа алгоритма сегментации поВарианту 2 позволяет получить наборы классов формальных понятий, при этомсуммарное количество ФП в этих классах будет меньше, чем в первоначальнойрешетке из-за удаления отношений между некоторыми объектами ипризнаками.В разделе 4.5 описываются дополнительные методы использования КОЛв ВОС: расширение ключевых слов вопроса, обработка собственных имен ввопросах и ответах, удаление избыточности в ответах.В пятой главе выполняется экспериментальная проверка моделиизвлечения знаний для ВОС.

Формулируются требования по полноте ирепрезентативности, предъявляемые к корпусу текстов, используемому дляпостроения на его основе КОЛ. Анализируются алгоритмы генерации решетки,выбирается наиболее эффективный для генерации КОЛ. Выполняется оценкаКОЛ.В разделе 5.2 показано, что распределение частоты встречаемости ГКсоответствует закону Ципфа по формуле (10) для достаточно больших текстоврусского языка.(10)log( F ) = c − k log( r ) ,vгде F – частота встречаемости слова, r – ранг слова в частотном распределении,c и k – константы, специфические для каждого ЕЯ.На Рисунке 4 представлен график распределения частот употребления ГК длятекста различного объема (текст №1 – 4 млн. слов, текст №2 – 8 млн.

слов,текст №3 – 16 млн. слов, текст №4 – 25 млн. слов, текст №5 – 34 млн. слов,текст №6 – 41 млн. слов, текст №7 – 50 млн. слов, текст №8 – 85 млн. слов).15Рисунок 4. Распределение частот употребления ГК для текста различногообъема.Согласно закону Ципфа, объем корпуса текстов для построения на егооснове КОЛ должен быть не менее 50 млн.