Синтаксическая однозначность при представлении знаний в логике первого порядка тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Пономарёв, Денис Константинович

• Пономарёв, Денис Константинович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Пономарёв, Денис Константинович

Введение

Глава 1. Пример разработки прикладных логических теорий

1,1 Постановка задачи.

12 Предназначение разрабоинноп юории.

13 Проблема формальней о иредсшв к'ння.

1,1 Структура теории.

1о Обсуждение предгтавичшой теории. l.G Программная реализация.

1,7 Обзор близких pa6oi.

1 8 Резулыаш

Глава 2, Проблема синтаксической однозначности и разложимости

2 1 Непрерывная шлборка информации . . . . 31 2 2 Посшнонка проб юмы ра5ло/Кимо(л и . . U)

2 3 Пршюшмые теории.

2 1 Разложимые теории . . . "Л

2 5 Резулыаш . . .G

Глава 3. Практические вопросы разложимости GG

3 1 Конечно аксиоматизируемые теории . . G

3 2 Приведение к преднкаым.

3 3 Скудемонское обогащение.

3 1 Ре платы

Введение диссертации (часть автореферата) на тему «Синтаксическая однозначность при представлении знаний в логике первого порядка»

В настоящее время существуй значительный ишерес к метола'i и средствам декларативного представления знаний, коюрый. в частности, связан с недавно обученной концепцией "Semantic Web" [lj-[l] и широко раснрос1раненным понятием формальной онюлопш [5]-[7j. Рсчулыаюм )юю являек'я разрабош! и применение новых компьютерных языков для формальною представления знаний [G2, G3], а мк-же сисп'М по,1держки логическою вывода. Каждый и з новых языков cooiBeu iB)ei некоюрому иодмножес1ву лотки первою порядка, однако исходя из практики специалисты начгши осознавать необходимость использования данной лотки целиком для работы с теми задачами, коюрые (чали аыуальны в последнее время. Среди них можно выделил» поиск в объемных слабо струмурированных хранилищах информации и пн им рацию кчероюнных источников данных.

В рамках данных задач декларашвные описания применякнся как 1ерминоло1ические базы знаний, в коюрыч описаны 1ермины вмесче с заданной для них аксиомашческой еемашикой. Декларашвные iep-\1Иноло1 ические базы знаний обычно нриняю рассмаipnnaiь с двух ючек зрения: как i рафы свя зносш юрминов и как наборы ло1 ических упзерждении IIjjii лом широко используемся ионяше связи юрминов по вхождению в одно (или близкие в определенной мефике) высказывания.

Связи между 1ерминами в задаче поиска даю1 возможное п> переформулировать (усилить/ослабить) запрос в зависимости oi рез)лыа-Ш13 ею исполнения [8]. Аналошчно лому в задаче imiei рации связи влинкл на точность иоароешюю отображения меж,1у двумя описаниями данных [9, 10J При лом аксиомы, заданные в декдарашвном описании, непосредственно определяют пш связей между терминами [11, 12]. Для решения копире:ной задачи moi^t применяйся различные cipaieimi. использующие разные пшы связей в зависимости от ситуации.

В данной работе декларативные описания знаний расематривают-ся как (элементарные) теории в лошке первого порядка. Естественно, данное рассмотрение не являемся орипшальным и оно не может бып> 1аковым в принципе, начиная с юю времени, как был введен формальный amiapai дошки.

С ючки зрения связей терминов по вхождению для заданной юории можно рассматривать различные компоненты свя зности на множестве cniHaiypubix символов, используемых в записи иредчожешш теории. Есюспзенным образом возникае1 вопрос: являю1ся ли компоненты связносш одинаковыми для двух лошчески эквивалентных leopini 13 одной и юй же cniiiaiype? В целом, ответ является отрицательным и причина лому - сишаксическая cyib нашею подхода. На практике это означает, что могут сущеснзовать два множества предложений, которые семантически эквивалентны, но синтаксически представ юны по-разному. Возможно ли привести теорию (аксиомы теории) к такому виду, по коюро.му однозначно определяю юя комноиешы связнос in сш шнуры юории? Данный вопрос нредставлне! расширенную постановку проблемы разложимое! и, коюрая была сформулирована в 2003 юду в связи с изучением формальных ошолошй (см. исходную формулировку в [13] и поепшовку в главе 1 8). Суп» проблемы заключайся в юм, как определи хь, иредаавима ли произвольная заданная тория в .юшке первою порядка в виде объединения двух (или более) ieopiii'i, имеющих непересекающиеся сшншуры.

Вопрос разложимое:и имее! важное значение для формализации знаний, поскольку разложимосп» означает возможность разбить формальное описание инюресующей нредмепюй облает на част, каждая из коюрых используе1 свой оиельный алфавш. При построении формальною описания некоюрой предмешой облас!П часю оказы-вае1ся, чю данные, полученные oi экснерюв (или, например, извлеченные авюмашчсски из ickciob), иредсчавляю! собой некоюрый набор фактов, которые необходимо структурировать, чтобы получить и i них адекватную формальную модель. В частности, можег бьпь интересно, существуют ли част знания, которые независимы друг oi дру1а Эю в ЮЧНОС1И cooiBeiciB)er вопросу разложимое!и. если рассматривать с})0]).малыю0 онисанио предмешой облапи как ло[ ическую !ео])ию (скажем, в некоюром иодмножечлве лошки первою порядка) [35. 56. 61].

В данной рабою решена проблема разложимости для произвольных элемешарных теорий. Кроме тою, доказана однозначность разло/ко-ния сш ши)ры и самой хеории (с lo'inocibio до формул чисюю равенства) в случае ею существования. Таким образом, настоящая рабоы )С1анавливае1 связь мел\,1у подходом к paccMoipennio сшпаксической связанное!!! 1ермшюв с точки зрения !рафов и с ючки зрения формул Л01 ики.

Цель работы

- исследование возможности декомпозиции (разложения) формальных описаний 15 логике первою порядка на компоненты с непересекающимися алфавшами;

- изучение вопроса синтаксической однозначности при использовании элементарных теорий в логике первою порядка как средства формальною представления знаний.

В результаю рабош шпором 61.1л сформулирован кршерий разло-жимосш, доказана одношачносчь разложения ieopim на нерапожи-мые комнонешы с точноаыо до формул чисюю равенства, показано приведение ieopim к иному виду, но коюрому одношачно определяется ее разложение.

Методы исследования: меюды лошческою upoi раммирования и дедук питых систем, аппарат математической логики и теории моделей.

Научная новизна

Резулыаш. полученные в рабою, являкнея новыми и cooibcicib\-Ю1 тенденции времени в част связанных с ними информационных задач. В частосш. до насюящей рабохы исследования по решению проблемы разложимости в теории с дизъюнктными сш натурами не вс!речались в публикациях. Не было показано ранее, чю 1Сория в лотке первою порядка определив! компоиешы связносчи cinnaiypbi однозначным образом. Также не была исследована взаимосвязь лих вопросов с современными иосьшовками задач информационною поиска и liniei рации nciочников данных.

Практическая ценность

Полученные резулыаш имечог ценное!ь для задач поиска и ише-I рации данШ)1Х с использованием декларативных баз знаний, декомпозиции логических программ, распределенною исполнения логических операции, таких как проверка на непротиворечивость, над декларашв-ными базами знаний большою обьема. Кроме юю, фак!ы. показанные в работе, представляют интерес в связи с исследованием проб ими рышттпоипи в лотке и философии.

Апробация работы

Резульгаш работы докладывались в рамках следующих научных вс!реч: Iiiformatik-2006 - немецкой конференции по информашке (i Дрезден, Германия), русско-немецком симпозиуме по биоинформашке в 2005 io,iy (i. Билефельд, Германия), семинаре СОМО (i. Дармппадк

Германии, 2005 г.), международной конференции по биоинформатике BGRS'200G (Новосибирск, 200G ь), конференции "Техно.юпш Майкрософт в информатике и иро1раммировании"(Новосибирк, 200G юд). Ме/кдународной Научной Студенческой Конференции в 20031оду (Новосибирск). а также на семинарах в Институте систем информатики СО РАН. Пнсшiyie математики СО РАН, Институте цито юпш и тенет ики СО РАН.

По Юме диссертации опубликовано 10 печатых работ.

Структура и объем работы

Диссертационная работ состоит из введения, треч глав и списка литературы. Объем диссертации - 89 страниц. Список литературы содержит 63 наименования. Работ включает 8 рисунков.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Пономарёв, Денис Константинович

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Исследовано применение декларативных описаний в дотике нерво-ю порядка для задач поиска информации и интсчрации исючников данных Разработана и реализована протраммно лотическая теория в области биоипформашки для анализа экспериментальных данных по экспрессии генов и фенотипическим аномалиям модельното организма Arabidopsis thaliana (L.).

2. В связи с использованием связей терминов в декларативных описаниях исследована возможность декомпозиции (разложения) формальных описаний тз .юшке первою порядка на компоненты с непересекающимися алфавитами. Сформулирован критерий разложимости.

3. Исследован вопрос синтаксической однозначности при описании знаний как ieopiiii в .км ике первою порядка. Доказана однозначное it, ра з-ложения геории на неразложимые компоненты с точностью до формул чистою равенства. Показано приведение теории к такому виду, по которому однозначно определяется ее разложение.

Заключение

В рамках соЕзременныч тенденций использования декларативных баз знаний для задач поиска и иннчрации информации автором в данной работе исследована проблема разложимоеiи (иементарных) кюрий дошки первою порядка.

Свойство разложимости cooiBeiciByei юму, чю исходную leopnio можно предемвить в виде обьединения двух (или более) теории. имеющих н(Ч1ересекаюшиеся сш натуры.

В облает формализации знаний вопрос разложимое!и интересен с ир<1ктической точки зрения, поскольку разложимость означаем возможность разбип» (формальное описание интересующей предметной облает на част, каждая из коюрых используем свой оiдельный ;u-(})авш. При носIроении формальною описания некоюрой предмешой облает часю оказываемся, чю данные, полученные oi жеперюв (или извлеченные авюмашчески), И1)едс1авляюг собой некоюрый набор факюв, которые необходимо с-1рукiурироиа 1 ь, чюбы получить из них адеквашую c|)op\uun>nyio модель. В часшосш, можем бы и, шперее-но. сущее 1вукн ли час ш знания, коюрые независимы др>ч oi друта Эю в ючносш cooiBeiciByei вопросу разложимоеш, если рассматривай, формальное описание предмешой облает как лотческио ieo-рию (скажем, в некотором фратмеше лотки первою порядка). Разложимосп, важна и для выполнения лснических операций над обьем-ными декларашвными базами знаний, в часшосш, для проверки их непротиворечивое ш. Если теория может бып, разбита в неско п,ко ча-cieii. имеющие различные сш шпуры, ю )ш част возможно подвер1nyib проверке на непро1иворечивое1ь по отдельности. Эю также дает возможность распределенною выполнения данной операции. Можно привести и дручие П1)имеры приложении данного вопроса. Пдеолош-чески все они исходяi из юю просюю факта, чю в любой сфере 'знаний декомпозиция всегда означает упрощение.

Важным является не только вопрос, является ли теория разложимой, но и ю, однозначно ли разложение, если оно существует.

В настоящее время в ряде информационных задач, связанных с тер-минолоптческими базами знаний, широко используется понятие связи терминов но вхождению в одно (или близкие с определенной метрикой) высказывания. Декларативные 1ерминоло1 ические базы знаний обычно принято рассматривать с двух точек зрения: как 1рафы связности терминов и как наборы лотических утверждений. В связи с этим в работе рассмотрена проблема синтаксической однозначности при описании знаний в ло1 икс первою порядка Однозначность является важной. поскольку в ло1 неэквивалентные утверждения мотут различаться сшпаксически. В общем случае два (семантически) эквивалентных описания Moiyr отвечать разным компонентам связности терминов, что делает на первый взгляд невозможным использование связности по вхождению в высказывания. Автором в данной работе доказано, чю разложение теории на неразложимые компоненты веема однозначно Однозначность разложения соответствует однозначности в синтаксической записи утверждений с точки зрения вхождения сигнатурных элементов. Кроме тою, показано приведение теории к такому втщу. по которому однозначно определяется это разложение. Таким образом, настоящая работа устанавливает связь между подходом к рассмотрению связности юрминов с точки зрения 1рафов и с точки зрения формул л 01 и к тт.

Список литературы диссертационного исследования кандидат физико-математических наук Пономарёв, Денис Константинович, 2006 год

1. Вегпогь-Lce Т., Hendler J., Lassila О. 'Ihe Semantic Web. // Scientific American, Maj, 2001.

2. G. Jasper R., Uschold М. A framework for understanding and classify mg ontolog\ applications // Proc IJCAI99 Workshop on Ontologies and Problem-Solving Methocls(KRRo), Stockholm, Sweden, August 1999

3. Guarino N. Гопиа! Ontologj and Information Sj stems Proc TOIS 9S. Trento, Italv, June. 199S P 3-13

4. Stuckenschmidt H., Giunchiglia F., van Ilarmelen F. Querj processing in ontolog\-based peer-to-peer Ь) stems // Ontologies for Agents Iheon and Experience-) Birkhauser, 2003.

5. Ralini E., Bernstein P. A sur\e> of approaches to automatic schema matching // 1 he YLDB Journal 2001 - \ 10(1).

6. Melnik S., Molina-Garcia H., Rahm E. Similarity flooding. A versatile graph matching <iIqorithm and its application to schema matching. // Proc International Conference on Data engineering (ICDE) 2002.

7. Maedche A., Staab S. Measuring similarity between ontologies // Proc EK WV'2002 P. 251-263.

8. Eu/enat J., Valtchev P. An integrative proximity measure for ontology alignment // Proc. ISWC-2003

9. Palchunov D. GABEK for Ontology Generation // GABEK Contributions to Knowledge Organization Wien LIT-pubhshing Company, 2003 - Vol. 2.

10. The Computable Plant project http //www computableplant org]

11. Omelianchuk N.A. et al. AGNS A database on expression of Arabulopsis genes // Bioinformaticb of Genome Regulation and Structure. I'roc. / BGRS'2001. .Novosibirsk, 2001 - Berlin, 200G - Volume 2 - P. 433-112

12. Karp P.D. An ontology for biological function based on molecular interactions // Bioinformatics 2000. X 16 P 260-285.17| Barcl J.В., Rliee S.Y. Ontologies in biology, design, applications and future challenges // Nat. Rev. Genet 2001. -No- P. 213-222

13. Bodenreider O. et al. Biomedical ontologies // Proc. Pacific Symposium on Bioconiputing 2003 - P. 76-78

14. McGuinness D. L., van Harmelen F. OWL Web Ontology Language Oyerview. // W3C Recommendation, <http://www.w3org/FR/owI-features

15. Patel-Schneider P.F., Hayes P., Ilorrocks I. OWL Web Ontology Language: Semantics and Abstract Syntax // W3C Recommendation chttp.//wvvvv.w3 org/1 R/owl-seniantics/>

16. Bander F., Calavnnese D., McGuiness D., Nardi D., Patel-Schneider P.1.e Description Logic Handbook Cambridge Universitv Pre^s, 2003

17. Клещев А.С., Артемьева И.Л. Математические моими онююшй иред-мегныч обллсюй. Член, II. Компоненты молели. // Научно-и'чническая информация 2001 - X 3 - С. 19-28

18. Клещев А.С., Артемьева И.Л. Необоыщенные системы лен ичеекпч соотношений // Научно-техническая информация 2000 - X 7 - 8 - .V" 7 С 18-28, .V» 8 С. 8-18

19. Garland F.M., McIIale N.A. LOP1. a gene involved ш аччш transport and vascular patterning ш Arabidopsis // Development. 1990 - X 122(G) - P 1S11-1819

20. Hermann G.T., Rosenberg G. Developmental Systems and language-. Amsterdam: Xorth-IIolIand Publishing Co , 19752(5. Лидл P., Ппльц Г. Примадная абстрактная плибра. Пер с англ. / Пот рел ЛИ Шенрина Ккатеринбур1. 1Ьд-ио Урал \н-та, 1996 г

21. Rosen R. Some further comments oil the DXA-protem coding problem. Bull Math Bioph\s 1959 - X 21 - P 289-297.

22. Rosen R. Foundations of Mathematical Biologv. Xev, York, Academic Press, 1972, 1973 - Vol. Mil

23. K. Krohn, R. Langer, J. Rhodes. Algebraic principle-, for the anah-ь of a biochemical ьу stem // I Comput. Syst. Sci -1976 Xl-P 119-136

24. TAIR Ihe Arabulopsis Information Resource, http //www arabidop-as org]

25. РОС Plant Ontology Consortium http.//\\\v\v.plantontolog\ org]

26. Vincent P. et al The Plant Ontology Consortium and plant ontologies Comparative and functional genomics. 2002 - X 3(2) - P 137-112.

27. Jaiswal P. et al. Plant ontology (PO): a controlled vocabulary of plant structures and growth stages // Comparative and functional genomics. 2006 - X 6(7-8) -P 388-397.

28. Aitken S. Formalizing concepts of species, ье\ and development stage ш cinatomical ontologies 11 Bioinformatics 2005 - N 21 - P. 2773-2779.

29. Smith D. et al. On the application of formal principle-, to life science data, a case stud} in the gene ontologv // Database Integration in the Life Sceienc.es -Springer Yerlag, 2004 P. 79-91

30. Smith B. et al. Relations in biomedical ontologies // Genome Hiologv 200") - X G chttp //genomebiologv com/2005/6/5/R 1G>

31. Smith 13. Mereotopologv • Л tlieorj of parts and boundaries // Data and Know ledge Engineering 199G - X 20 - P. 287-303

32. Fu G., Jones C., Abdelmoty A. Ontology-based bpatial querv expansion m information retrieval // Proc OTM Conferences 200") Vol 2

33. Muller H., Kenny E., Sternberg P. Textpresso. An ontologv-based information retrieval and extraction system for biological literature / PI.oS Biologv Journal- 2001 -X 2(11).

34. Chang K.-C., Garcia-Molina II. Approximate query mapping' Ac counting for translation closeness //1he VLDB Journal 2001 - X 10 - P. 155-181.

35. Castnno S., Ferrara A., Montanelli S., Pngani E., Rossi G. Ontologv-addre^sable contents in P2P networks. // Proc. 1st Workshop on Semantics in Peer-to-Peer and Grid Computing 2003.

36. Arumugam M., Sheth A., Arpinar I.B. Towards peer-to-peer semantic web. A distributed environment for sharing semantic knowledge on the web // Proc International World Wide Web Conference 2002 (WWW2002), Honolulu, Hawaii. USA, 2002.

37. Castano S., Ferrara A. Knowledge representation and transformation m ontologv-Ьач>(1 data integration. // Proc. ПС У Workshop oil Knowlidge Transformation for the Semantic Web, Lyon, Trance, July 2002 P 51-59

38. Madliavan J., Bernstein P.A., Domingos P., Halevy A.Y. Representing and reasoning about mappings between domain models // Proc. Eighteenth National Conference on Artificial Intelligence (АААГ2002), Edmonton, Canada- 2002 P. 80-8G.

39. Maedche A., Motik В., Stojanovic L. Managing multiple and distributed ontologies on the Semantic Web // The VLDB Journal 2003 - \ 12 - P. 2SG-302

40. Calvanasea D., De Giacomo G., Lenzerini M. Description logics for information integration / / Computational Logic: I ogic Programming and Beyond- Springer Yerlag, 2001 P. 11-60

41. Bergamabchi S., Cabtano S., Vincini M. Sem.intic integration of seini-structurcd and structured data sources // SIGMOD Records 1999 - X 28(1)

42. Кейслер Г, Чэн Ч.Ч. Ieopnn мошлеи \1.: Мир, 1977.

43. Otto М. An interpolation theorem // Bulletin of Svmbohc Logic 2000 X G.

44. Пальчунов Д.Е. Алгебраическое описании смысла высказываний естесюен-uoio языка // Впчислше и.иые системы / Модели коишпшиыч проще с on -Новосибирск, 1997 Нып 158 - С. 127-118.

45. Пальчунов Д.Е. Синтаксическая бниосгь пред ю/кеиий языка первою порядка // Вычислительные системы / Измерение и модели копштивиых процессов Новосибирск, 1998 - Bun 1G2 - С. 58-80

46. Шёнфплд Дж. Манпшическан лошка М.: Наука, 1975.

47. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

48. Ponomaryov D. Semantic Web Ьаысъ ш logical consideration. // Lecture Note-, ш Informatics- Proc / Inforinatik-2()0G, Dresden, 200G Bonn, 2000 - Volume 2 - P 337-311

49. Mironova V.V., Poplavbky A.S., Ponomaryov D.K., Omelianchuk

50. N.A. Ontolog} of Arabidopsis Genenet Supplemental Database(AGNS) Cro-s references to TAIR ontologv. // Proc. Bioinformatics of Genome Regulation and Structure (BGRS'2006), Novosibirsk 2000 - P 209-212.

51. GO. Ponomarjov D. Lattice semantics for incremental data e\traction from declarative knowledge bases. Новосибирск, 200G - 13 cip. - (Ilpenp CO РАН Ин-тспси'м информашки; N131).

52. Пономарев Д.К. Залача разложимой» э ie\ieniapnn\ теорий и проб leva мшшмимшш in аксиом. // 1см коиферсниии-конмрса "Течпо ioi ии

53. Microsoft u информатике и профаммироваиии", Новосибирск, 22-21 феир.ин, 2006. С. 213-215

54. Пономарев Д.К. Применение языков описании оитодопш дщ построении \\е1)-ориен1нропанны\ информационных систем. // Вестник Новосибирскою Гос Ун-та / Информационные темютопш Новосибирск, 2001 - Г 1, Впи 1 - С. 5-20.

55. Пономарев Д.К. Применение Web-стандарго» описания метаданных д 1я представ п'нии предметных областей. // Tes. XLI Междуиароmoil ILi\мноп Студенческой Конференции (МНСК), Новосибирск, 11-17 апреля 2003 С 39-Ю.