Национальной академии наук республики казахстан
жүктеу/скачать 6 Mb. Pdf көрінісі
|
| ISSN 1991-3494 ҚАЗАҚСТАН РЕСПУБЛИКАСЫ ҰЛТТЫҚ ҒЫЛЫМ АКАДЕМИЯСЫНЫҢ Х А Б А Р Ш Ы С Ы ВЕСТНИК НАЦИОНАЛЬНОЙ АКАДЕМИИ НАУК РЕСПУБЛИКИ КАЗАХСТАН THE BULLETIN OF THE NATIONAL ACADEMY OF SCIENCES OF THE REPUBLIC OF KAZAKHSTAN 1944 ЖЫЛДАН ШЫҒА БАСТАҒАН ИЗДАЕТСЯ С 1944 ГОДА PUBLISHED SINCE 1944 АЛМАТЫ ҚЫРКҮЙЕК АЛМАТЫ 2014 СЕНТЯБРЬ ALMATY SEPTEMBER Вестник Национальной академии наук Республики Казахстан 2 Б а с р е д а к т о р ҚР ҰҒА академигi М. Ж. Жұрынов Р е д а к ц и я а л қ а с ы: ҚР ҰҒА-ның академиктерi: Н. Ә. Айтқожина, К. М. Байпақов, И. О. Байтулин, Р. И. Берсiмбаев, Е. Е. Ерғожин, Н. П. Иванов, С. А. Қасқабасов, З. М. Молдахметов, Н. К. Надиров, Ә. Н. Нысанбаев, С. С. Сатыбалдин, С. Н. Харин, Ү. Ш. Шоманов, Е. М. Шайхутдiнов, РҒА-ның академигi Е. П. Велихов (Ресей), РҒА-ның академигi Н. П. Лаверов (Ресей), Украина ҰҒА-ның академигi В. В. Гончарук (Украина), ҚР ҰҒА-ның корреспондент мүшесі, химия ғылымдарының докторы, проф. Қ. С. Құлажанов, академик М. Алиев (Әзірбайжан), академик Ф. Гашимзаде (Әзірбайжан), академик В. Рудик (Молдова), академик И. Тодераш (Молдова), академик С. Москаленко (Молдова), мүше-корреспондент Ф. Лупашку (Молдова), академик М. М. Якубова (Тәжікстан), академик А. С. Сагиян (Армения), академик Р. Т. Джрбашян (Армения) Г л а в н ы й р е д а к т о р академик НАН РК М. Ж. Журинов Р е д а к ц и о н н а я к о л л е г и я: академики НАН РК: Н. А. Айтхожина, К. М. Байпаков, И. О. Байтулин, Р. И. Берсимбаев, Е. Е. Ергожин, Н. П. Иванов, С. А. Каскабасов, З. М. Мулдахметов, Н. К. Надиров, А. Н. Нысанбаев, С. С. Сатубалдин, С. Н. Харин, У. Ч. Чоманов, Е. М. Шайхутдинов, академик РАН Е. П. Велихов (Россия), академик РАН Н. П. Лаверов (Россия), академик НАН Украины В. В. Гончарук (Украина), член- корреспондент НАН РК, доктор химических наук, профессор К. С. Кулажанов, академик М. Алиев (Азер- байджан), академик Ф. Гашимзаде (Азербайджан), академик В. Рудик (Молдова), академик И. Тодераш (Молдова), академик С. Москаленко (Молдова), член-корреспондент Ф. Лупашку (Молдова) , академик М. М. Якубова (Таджикистан), академик А. С. Сагиян (Армения), академик Р. Т. Джрбашян (Армения) E d i t o r - i n - c h i e f academician of NAS of the RK M. Zh. Zhurinov E d i t o r i a l s t a f f : academicians of NAS of the RK: N. A. Aitkhozhina, K. M. Baipakov, I. O. Baitullin, R. I. Bersimbayev, E. E. Ergozhin, N. P. Ivanov, S. A. Kaskabasov, Z. M. Muldakhmetov, N. K. Nadirov, A. N. Nisanbaev, S. S. Satubaldin, S. N. Kharin, U. Ch. Chomanov, E. M. Shaikhutdinov, academician of the RAS E. P. Velikhov (Russia), academician of the RAS N. P. Laverov (Russia), academician of the NAS of Ukraine V. V. Goncharuk (Ukraine), corresponding member of the NAS of RK, doctor of chemical sciences, professor K. S. Kulazhanov, academician М. Аliyev (Аzerbaijan), academician F. Gashimzade (Аzerbaijan), academician V. Rudik (Моldova), academician I. Toderash (Моldova), academician S. Moskalenko (Моldova), corresponding member F. Lupashku (Моldova), academician М. М. Yakubova (Таdjikistan), academician А. S. Sagiyan (Аrmeniya), academician R. Т. Dzhirbashiyan (Аrmeniya) «Вестник Национальной академии наук Республики Казахстан» I SSN 1991-3494 Собственник: РОО «Национальная академия наук Республики Казахстан» (г. Алматы) Свидетельство о постановке на учет периодического печатного издания в Комитете информации и архивов Министерства культуры и информации Республики Казахстан №5551-Ж, выданное 01.06.2006 г. Периодичность: 6 раз в год Тираж: 2000 экземпляров Адрес редакции: 050010, г. Алматы, ул. Шевченко, 28, ком. 218-220, тел. 272-13-19, 272-13-18. www: nauka-nanrk.kz, bulletin-science.kz Адрес типографии: ИП «Аруна», г. Алматы, ул. Муратбаева, 75 © Национальная академия наук Республики Казахстан, 2014 ISSN 1991-3494 № 5. 2014 3 Научные статьи BULLETIN OF NATIONAL ACADEMY OF SCIENCES OF THE REPUBLIC OF KAZAKHSTAN ISSN 1991-3494 Volume 5, Number 5(2014), 5 – 10 UDC 519.68; 681.513.7; 316.472.45; 007.51/.52 COMPUTER-ORIENTED METHODS OF DEFINITION OF DEGREE OF SIMILARITY OF SENTENCES IN A NATURAL LANGUAGE T.V. Batura 1 , F.A. Murzin 1 , A.A. Perfiliev 1 , B.S. Baizhanov 2 , M.V. Nemchenko 2 tatiana.v.batura@gmail.com, murzin@iis.nsk.su, a_perfilev@mail.ru, baizhanov@hotmail.com, nemchenko.imim@mail.ru 1 A.P. Ershov Institute of Informatics Systems, Russian Academy of Sciences, Siberian Branch 2 Institute of Mathematics, Informatics and Mechanics, Committee of Science of the Ministry of Education and Science of the Republic of Kazakhstan Key words: Information Retrieval System, Link Grammar Parser, syntactic analysis, semantics, relevance Abstract. The basic considered problem consists in constructing algorithms, which getting into a text structure can deduce an adequate estimation of relevance of the text to the search inquiry. It is important, that the given estimation would be based on a context of search inquiry and would not be limited only by keywords, their similarity or frequency. Authors offered to use semantic-syntactical relations between words obtained on output of the Link Grammar Parser program system. In article, two algorithms of calculation of degree of similarity of sentences in a natural language are described. The second of them uses the approach based on the mathematical logic. Methods are partially implemented in the iNetSearch information retrieval system. УДК 519.68; 681.513.7; 316.472.45; 007.51/.52 МАШИННО-ОРИЕНТИРОВАННЫЕ МЕТОДЫ ОПРЕДЕЛЕНИЯ СТЕПЕНИ БЛИЗОСТИ ПРЕДЛОЖЕНИЙ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ Т.В. Батура 1 , Ф.А. Мурзин 1 , А.А. Перфильев 1 , Б.С. Байжанов 2 , М.В. Немченко 2 tatiana.v.batura@gmail.com, murzin@iis.nsk.su, a_perfilev@mail.ru, baizhanov@hotmail.com, nemchenko.imim@mail.ru 1 Институт систем информатики им. А.П. Ершова СО РАН 2 Институт математики, информатики и механики КН МОН Респ. Казахстан Ключевые слова: информационно-поисковая система, Link Grammar Parser, синтаксический анализ, семантика, релевантность Аннотация. Основная рассматриваемая задача состоит в построении алгоритмов, которые, проникая в структуру текста, могут вывести адекватную оценку релевантности текста поисковому запросу. Важно, чтобы данная оценка была основана на контексте поискового запроса и не ограничивалась только ключевыми словами, их близостью или частотой. Авторами было предложено использовать семантико- синтаксические отношения между словами предложения, получаемые на выходе программной системы Link Вестник Национальной академии наук Республики Казахстан 4 Grammar Parser. В статье описаны два алгоритма вычисления степени близости предложений на естественном языке. Второй из них использует подход, основанный на математической логике. Методы частично реализованы в информационно-поисковой системе iNetSearch. Работа выполнена при поддержке гранта 2581/ГФ3 МОН РК 1. Введение В условиях стремительного роста объемов информационных ресурсов возникает необходимость повышения качества поиска информации. Многие исследователи, например [1, 2], склоняются к необходимости проведения глубокого семантического анализа текстов для создания их семантических образов, на основе которых можно проводить тонкое ранжирование документов. Этот подход, несомненно, наиболее разумный, однако требует тщательной и долгой работы над созданием соответствующих теорий и подходящих инструментов для автоматической обработки текстов [3]. В частности, может потребоваться детальное описание различных областей знаний. Поэтому имеет смысл также поиск частичных решений. Основная задача состоит в построении алгоритмов, которые, проникая в структуру текста, могут вывести адекватную оценку релевантности текста поисковому запросу. Важно, чтобы данная оценка была основана на контексте поискового запроса и не ограничивалась только ключевыми словами, их близостью или частотой. В процессе решения поставленных задач авторами было предложено использовать семантико- синтаксические отношения между словами предложения, получаемые на выходе программной системы Link Grammar Parser [4,5]. Предложен способ (базовый алгоритм) вычисления степени совпадения естественно-языковых конструкций. Отметим, что в данный момент исследования полностью ориентированы на англоязычные источники. На основе вышеупомянутых идей была реализована информационно-поисковая система (ИПС) iNetSearch [6,7]. Проведенное тестирование системы iNetSearch показало эффективность предложенного алгоритма в решении задач поиска информации. Далее были предложены методы, которые обобщают подход, используемый в базовом алгоритме. Более точно, базовый алгоритм учитывает только так называемые инвариантные коннекторы, не принимая во внимание более сложную логику. Во втором случае применяются более тонкие методы. При сопоставлении двух предложений, точнее, при анализе их на близость осуществляется проверка ряда логических свойств. Примеры такого рода свойств: инвариантность коннектора, замена коннектора на дизъюнкцию других, расщепление коннектора на два коннектора, расщепление коннектора на два коннектора с инверсией и др. В настоящее время выделено 19 различных схем. Некоторые из них имеют несколько вариантов. Однако можно высказать предположение, что дальнейшее развитие предложенного метода весьма затруднительно и не приведет к существенным улучшениям имеющихся результатов. Одной из причин является то, что на данном этапе возможности анализатора Link Grammar Parser почти полностью исчерпаны. Несмотря на то, что Link Grammar Parser обладает рядом преимуществ (высокая скорость работы, частичный охват семантики), он вынуждает оставаться на уровне синтаксиса с небольшим охватом семантики. Поэтому, чтобы получить существенное продвижение, необходимо перейти на более высокий уровень, к инженерии знаний. 2. Метапоисковая система iNetSearch Система iNetSearch находится на стороне пользователя и требует подключения к сети Интернет. iNetSearch использует результаты запросов к существующим поисковым системам. Например, для тестирования использовался поисковый сервис Нигма.РФ (URL: http://www.nigma.ru), т.к. он переправляет запрос другим поисковым системам, тем самым, увеличивая возможный круг поиска. Реализованная система iNetSearch фильтрует результаты запросов. Предложения на естественном языке, получаемые из результатов запросов (например, краткие сниппеты, которые выдал сервис Нигма.РФ), транслируются в синтаксические диаграммы системы Link Grammar Parser. Транслятор дополнительно проводит лемматизацию слов, приписывание метаинформации словам. Добавление синтаксических связей между словами, типизацию этих ISSN 1991-3494 № 5. 2014 5 связей. Link Grammar Parser также осуществляет приписывание зависимостей между придаточными предложениями. Это дает достаточно большой объем информации о предложении. Самое главное, что анализатор генерирует диаграммы синтаксического разбора, которые отображают синтаксические взаимосвязи между словами. Основная задача состоит в том, чтобы оценить соответствие текста поисковому запросу. Делается это следующим образом. Имеются диаграмма синтаксического разбора для запроса и для конкретного предложения из текста. В базовом алгоритме предполагается, что если эти диаграммы похожи по лексике и по структуре связей, то мы признаем, что предложения (и в целом текст) релевантны запросу. В случае, когда учитываются перефразирования, обобщенный алгоритм на основе логического подхода принимает более изощренный вид, но в принципе идея та же. 3. Программная система Link Grammar Parser Link Grammar Parser – это синтаксический анализатор английского языка, разработанный в 1990-е гг. в университете Корнеги-Мелона, базирующийся на некоторой теории. Отметим, что данная теория, вообще говоря, отличается от классической теории синтаксиса. Получив предложение, система приписывает к нему синтаксическую структуру, которая состоит из множества помеченных связей (коннекторов), соединяющих пары слов. Подробное описание системы можно найти в [4,5] Link Grammar Parser имеет словари, включающие около 60000 словарных форм. Он позволяет анализировать большое число синтаксических конструкций, включая многочисленные редкие выражения и идиомы. Анализатор довольно устойчив; может пропустить часть предложения, непонятную ему, и определить структуру оставшейся части предложения. Он способен делать разумные предположения о синтаксической категории неизвестных ему слов (т. е. слов, которые отсутствуют в словарях) из контекста и написания. У анализатора есть данные об именах собственных, о числовых выражениях и разнообразных знаках препинания. Правила соединения слов описаны в наборе словарей. Для каждого слова в словаре записывается, какими коннекторами оно может быть связано с другими словами предложения. Коннектор состоит из имени типа связи, в которую может вступать рассматриваемая единица анализа. Например, пометка S соответствует связи между субъектом и предикатом, О – между объектом и предикатом. Только основных, наиболее важных связей, имеется более ста. Для обозначения направления связи справа к коннектору присоединяется знак "+", слева – знак "–". Левонаправленный и правонаправленный коннекторы одного типа (см. Рис.1) образуют связь (link). Рис. 1. Пример синтаксического разбора предложения Получаемые диаграммы, по сути, являются аналогом так называемых деревьев подчинения предложений. В деревьях подчинения от главного слова в предложении можно задать вопрос к второстепенному. Таким образом, слова выстраиваются в древовидную структуру. Синтаксический анализатор может выдать две или более схемы разбора одного и того же предложения. Это явление называется синтаксической синонимией. Главной причиной, по которой анализатор называют семантической системой, можно считать уникальный по полноте набор связей (около 100 основных, причем некоторые из них имеют 3-4 варианта). В некоторых случаях тщательная работа над разными контекстами привела авторов системы к переходу к почти семантическим классификациям, построенным исключительно на синтаксических принципах. Так, выделяются следующие классы английских наречий: ситуационные наречия, которые относятся ко всему предложению в целом (clausal adverb); наречия времени (time adverbs); вводные наречия, которые стоят в начале предложения и отделены запятой (openers); наречия, модифицирующие прилагательные и т.д. Из достоинств системы нужно отметить, что организация самой процедуры нахождения вариантов синтаксического представления очень эффективна. Построение идет не сверху вниз (top- Вестник Национальной академии наук Республики Казахстан 6 down) и не снизу вверх (bottom-up), а все гипотезы отношений рассматриваются параллельно: сначала строятся все возможные связи по словарным формулам, а потом выделяются возможные подмножества этих связей. Это, конечно, приводит к алгоритмической непрозрачности системы, поскольку очень трудно проследить за всеми отношениями сразу. Во-вторых, не к линейной зависимости скорости алгоритма от количества слов, а к экспоненциальной, поскольку множество всех вариантов синтаксических структур на предложении из N слов в худшем случае равномощно множеству всех остовных деревьев полного графа с N вершинами. Последняя особенность алгоритма заставляет разработчиков использовать таймер, для того чтобы вовремя останавливать процедуру, которая работает слишком долго. Однако все эти недостатки с лихвой компенсируются лингвистической прозрачностью системы, в которой с одинаковой легкостью прописываются валентности слова, причем порядок сбора валентностей внутри алгоритма принципиально не задается – связи строятся как бы параллельно, что полностью соответствует нашей языковой интуиции. Отметим также отрицательные моменты. 1. Практическое тестирование системы показывает, что при анализе сложных предложений, длина которых превышает 25-30 слов, возможен комбинаторный взрыв, и результатом работы анализатора становится «панический» граф, как правило, случайный вариант синтаксической структуры, с лингвистической точки зрения неадекватной. 2. Применение описанных выше идей затруднено для флективных языков типа русского, ввиду значительно возрастающего объема словарей, которые возникают в силу морфологической развитости флективных языков. Каждая морфологическая форма должна описываться отдельной формулой, где нижний индекс входящего в нее коннектора должен будет обеспечивать процедуру согласования. Это приводит к усложнению набора коннекторов и к увеличению их количества. Для агглюнативных языков (например, тюркских) система станет еще более сложной. 4. Базовый алгоритм отождествления 4.1. Краткое описание алгоритма Предполагаем, что мы работаем с деревьями, полученными в результате синтаксического анализа, проведенного системой Link Grammar Parser. Дальше производится «обобщение» таких деревьев. На этом этапе происходит нормализация словоформ. Могут быть произведены некоторые дополнительные преобразования предложений. Например, обратный порядок слов заменяется на прямой. Сложные формы глаголов «обрезаются» до простых форм. Глаголы могут переводиться в одну нормализованную форму в настоящем времени в простом виде. Сложные комбинации предлогов объединяются или даже удаляются. В результате получается «остов дерева», в котором удалены различные речеобразовательные конструкции. Такие деревья проходят процесс сравнения между собой (Рис.2). А именно, при определении релевантности текста запросу пользователя запрос сравнивается с предложениями в тексте. Сначала производится сравнение лексики. Перед сличением слов, слова проходят простые фильтры на словоформу. В действительности, было бы нецелесообразно считать глагол и существительное одинаковым словом, но мы этим пренебрегаем. Само сличение слов производится достаточно просто. Проверяются гипотезы на соответствие двух слов по набору правил, если все правила проверены, и соответствие не выявлено, то слова считаются далекими по смыслу. Набор правил представляет собой условия, при которых всё-таки можно считать слова близкими. Это такие правила как непосредственное равенство слов, совпадение с точностью до окончания, синонимическая близость слов, наличие отношения гипоним-гипероним, слова с трансмутациями и прочие возможные не очень сложные варианты близости между словами. ISSN 1991-3494 № 5. 2014 7 Рис.2: Пример сопоставления двух деревьев 4.2. Дополнительные возможности системы iNetSearch Режим нечеткого поиска позволяет системе находить документы, которые содержат слова, похожие по написанию на слова запроса. Например, слова с опечатками: вкрапления отдельных букв, пропуски букв, перестановки рядом стоящих букв, замена символа на неправильный, перепутанная раскладка клавиатуры, некоторые просторечные выражения, сокращения, транслитерации и пр. Режим нечеткого поиска, настраиваемый в системе, также позволяет анализировать слова, написанные похожими символами из других языков и специальными символами, что обычно используется хакерами и спамерами для маскировки слов. 4.3. Сравнение связей Далее предположим, что даны два предложения n x x x , , 1 , m y y y , , 1 , т.е. предложения рассматриваем, как вектор с компонентами из слов. Считаем, что произведен их разбор с помощью системы Link Grammar Parser. Рассмотрим множество всех таких пар 2 1 , i i , 2 1 , j j , что слова 2 1 , i i x x и слова 2 1 , j j y y соединены коннекторами одного и того же типа. При этом слова 1 1 , j i y x и слова 2 2 , j i y x близки в соответствии с тем или иным критерием. Например, их нормализованные формы одинаковые, они являются синонимами, слова похожие по написанию и т.д. Здесь возможна некоторая вариабельность алгоритма. Можно также игнорировать служебные слова: артикли, союзы, предлоги, междометия и др. Допустим теперь, что I – множество пар, упомянутых выше и принимаемых во внимание, и пусть его мощность n I | | . Далее пусть 2 1 , n n – количество коннекторов, получающихся в результате анализа предложений y x, соответственно. В качестве меры похожести двух предложений можно ввести ) , max( / ) , ( 2 1 0 n n n y x или ) /( 2 ) , ( 2 1 1 n n n y x . В следующем разделе предложенный подход будет существенно обобщен. Окажется, что базовый алгоритм учитывает только так называемые инвариантные коннекторы, не принимая во внимание более сложную логику. Таким образом, описанный выше метод позволяет ввести определенные меры близости между предложениями. Эти меры учитывают, как лексику, так и синтаксические отношения между словами. Минимальный вариант, дававший достаточно хорошие результаты, когда учитывались всего 8 связей: C, CC, S, SI, SF, SFI, SX, SXI. Вестник Национальной академии наук Республики Казахстан 8 Таблица 1 – Перечень наиболее важных связей системы Link Grammar Parser Связь Описание C соединяет подчинительный союз, глагол или прилагательное с подлежащим подчиненного предложения CC используется для соединения сочинительных союзов S соединяет подлежащее, выраженное существительным с глаголом SI соединяет подлежащее с глаголом в предложениях с инверсией главных членов предложения SF соединяет подлежащее, выраженное "it" или "there", с глаголом SFI соединяет подлежащее, выраженное "it" или "there", с глаголом вопросительном предложении с инверсией главных членов предложения SX используется для соединения местоимения "I" с глаголами "was" и "am" SXI используется для соединения местоимения "I" с глаголами "was" и "am" в случаях перестановки подлежащего и сказуемого Были выделены 6 связей, учет которых мог существенно испортить ситуацию. Поэтому их целесообразно опускать. Всего в большей или меньшей мере анализу подверглись 45 связей. 5. Логические методы отождествления Как и раньше считаем, что L – множество слов некоторого естественного языка. Для любого слова L x обозначим ) (x Norm его нормализованную форму. Запись ) , ( y x Syn обозначает, что y x, – синонимы. Возникают два вида эквивалентностей: 1) ) , ( 2 1 2 1 2 1 x x Syn x x x x , 2) ) ( ) ( 2 1 2 1 x Norm x Norm x x . Предложение рассматриваем, как вектор с компонентами из слов n x x x , , 1 . Функция Norm может быть естественно распространена на предложения ) ( , ), ( ) ( 1 n x Norm x Norm x Norm . Текст n x x T , , 1 есть последовательность предложений. Пусть запись ) , ( | j i x x P x обозначает, что в схеме разбора предложения n x x x , , 1 посредством анализатора Link Grammar Parser имеется коннектор типа P , идущий от слова i x к слову j x . Знак | означает, что фактически мы имеем дело с моделью. Основным множеством модели является множество пар } , , , , 1 { 1 n x n x . Так как одно и то же слово может входить в предложение два и более раз, то это приводит к необходимости рассмотрения именно пар, а не отдельных слов. Ввиду сказанного выше, корректным является даже обозначение | x , где – формула, например, исчисления предикатов первого порядка. Фактически x одновременно является обозначением и для вектора, и для модели. Предположим, что даны два предложения n x x x , , 1 , m y y y , , 1 . Интерес представляют функции f такие, что } , , 1 { ) ( }, , , 1 { ) ( m f range n f dom с дополнительными свойствами типа: j i y x j i f ) ( , j i y x j i f ) ( и другие подобные. При сопоставлении двух предложений, точнее, при анализе их на близость осуществляется проверка ряда логических свойств. Например, пусть 2 2 1 1 ) ( , ) ( j i f j i f . Теперь приведены примеры такого рода свойств. Инвариантность коннектора жүктеу/скачать 6 Mb. Достарыңызбен бөлісу:
|