автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Логико-вероятностные методы извлечения знаний из данных и компьютерное познание

На правах рукописи

Витяев Евгений Евгеньевич

ЛОГИКО-ВЕРОЯТНОСТНЫЕ МЕТОДЫ ИЗВЛЕЧЕНИЯ ЗНАНИЙ ИЗ ДАННЫХ И КОМПЬЮТЕРНОЕ ПОЗНАНИЕ

05.13.01 - Системный анализ, управление и обработка информации (в научных исследованиях) по физико-математическим наукам

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Новосибирск, 2006

Работа выполнена в Институте математики им. СЛ. Соболева СО РАН

Официальные оппоненты: чл.-корр РАН,

доктор физико-математических наук, профессор Федотов А.М.;

доктор технических наук, профессор Загоруйко Н.Г.;

доктор физико-математических наук Романьков В.А;

Ведущая организация: Новосибирский государственный университет,

Защита состоится 28 декабря 2006г. в 14.00 на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО «Омский государственный университет им. Ф.М. Достоевского» в библиотеке Омского филиала Института математики им. С. Л. Соболева СО РАН по адресу:

644099 Омск, ул. Певцова, 13

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского

Новосибирск

Автореферат разослан » 2006

Ученый секретарь

диссертационного совета,

кандидат физико-математических наук

А.М. Семенов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время в базах данных накоплено множество разнообразных данных. Все более актуальной является задача корректной обработки этих данных и извлечения знаний. Методами обработки («раскопки») данных и обнаружения знаний занимается интенсивно развиваемое направление Knowledge Discovery in Databases and Data Mining (KDD&DM), основанное на методах Machine Learning, Artificial Intelligence и Data Analysis. Однако до сих пор не проведен анализ этих методов с точки зрения их связи с процессом познания. Не ясно в какой степени извлекаемые знания помогают познавать исследуемую предметную область.

В диссертационной работе анализируется связь методов извлечения знаний с процессом познания. В результате анализа выясняются следующие ограничения существующих методов извлечения знаний, мешающих осуществлению процесса познания предметной области:

1. каждый метод ориентирован на работу с вполне определенными данными. Не определено в какой степени и полноте данный метод извлекает информацию из данных;

2. каждый метод явно или неявно обнаруживает только вполне определенный класс гипотез в данных.

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

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

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

Цель работы. Разработать теорию и метод компьютерного познания, позволяющие обнаруживать теории предметных областей и решать задачи полного извлечения знаний из данных.

Методы исследования. Основным методом исследования является использование теории измерений и логико-вероятностных методов в языке первого порядка. Теория измерений является единственной теорией, в которой достаточно полно и подробно проведен логический анализ величин, дано определение числовых представлений величин и их эмпирического содержания. В ней показано, что каждая величина является числовым представлением некоторой эмпирически заданной алгебраической структуры. В работе показано* что для достаточно полного представления эмпирической информации, содержащейся в данных, необходимо представить эти данные в виде многосортной эмпирической системы - алгебраической структуры, определенной в терминах интерпретируемых в понятиях предметной области эмпирических отношений и операций.

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

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

1. основанный на теории измерений и автоматизирующий основные этапы этого процесса;

2. логический путь познания.

Для осуществления первого пути познания в диссертации получены следующие новые результаты:

- разработана методика перевода данных в многосортные эмпирические системы с извлечением содержащейся в них интерпретируемой информации;

- разработан метод и система Discovery обнаружения систем аксиом на данных, представленных полученными многосортными эмпирическими сис-

, темами;

- доказана возможность обнаружения систем аксиом в условиях шумов некоторого типа;

- на примере физической структуры ранга (2,2) доказано соответствие между теорией измерений и теорией физических структур.

Получена серия результатов, открывающих путь логического процесса познания:

- даны определения закона, вероятностного закона и максимально специфического правила, позволяющие обнаруживать соответственно истинные, вероятностные и максимально специфические для предсказания высказывания;

- решена проблема статистической двусмысленности и непротиворечивости предсказаний;

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

Разработан реляционный подход к извлечению знаний из данных. Этот подход реализует логический процесс познания предметной области. Разработана система Discovery, обнаруживающая все перечисленные типы законов. Эта система успешно применялась для решения целого ряда практических задач.

Практическая ценность. Разработана программная система Discovery, которая была успешно применена для решения следующих задач: определение закона транзитивности (в психофизике); разработка диагностической системы рака груди (в медицине); прогнозирования курсов ценных бумаг (в финансах); анализ регуляторных районов генов (в биоинформатике).

Апробация работы: Основные результаты работы докладывались на следующих семинарах и конференциях: И-я Всесоюзная школа-семинар по "Программно-алгоритмическому обеспечению прикладного многомерного статистического анализа", Москва, 1983; Седьмая всесоюзная конференция по математической логике, Новосибирск, 1984; III-я Всесоюзная научно-практическая конференция "Применение многомерного статистического анализа в экономике и оценке качества продукции, Тарту, 1985; Всесоюзная конференция по прикладной логике, Новосибирск, 1985; Методы и программное обеспечение обработки информации и прикладного статистического анализа данных на ЭВМ, Минск, 1985; Проблемы совершенствования синтеза, тестирования, верификации и отладки программ, Рига, 1986; International workshop on Expert Systems and Pattern Recognition, 1987, Novosibirsk; IV Всесоюзная школа-семинар "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа", Москва, 1991; Симпозиум: Интеллектуальная поддержка деятельности в сложных предметных областях, Новосибирск, 1992;

Artificial Intelligence and Manufacturing Research planning Workshop, Albuquerque, New Mexico, US, 1996; Workshop Data Mining in Finance, New-York, US, 1998; Second International Conference on Bioinformatics of Genom Regulation and Structure, Novosibirsk, 2000; International Conference on Imaging

Science, Systems, and Technology, Las Vegas, US, 2002; Fifth International Conference on Forensic Statistics, Venice, Italy, 2002; Third International conference on bioinformatics of genome regulation and structure, Novosibirsk, 2002; Вероятностные идеи в науке и философии, Новосибирск, 2003; First International Moscow Conference on Computational Molecular Biology, Moscow, 2003; Seventh International Conference "Knowledge-based Intelligent Information and Engineering on Systems", Oxford, UK, 2003; Fourth international conference on bioinformatics of genome regulation and structure, Novosibirsk, 2004; 9th Asian Logic Conference, Novosibirsk, 2005; 36th EMPG European Mathematical Psychology Group Meeting, Padua, Italy, 2005; 1st International Workshop on Philosophies and Methodologies for Knowledge Discovery, Copengagen, Denmark, 2005; XIV-ой Международной конференции по нейрокибернетике, Ростов-на-Дону, 2005; Технологии Microsoft в информатике и программировании, Новосибирск, 2005; Вторая международная конференция по Когнитивной Науке, Санкт-Петербург, 2006.

Публикации. По теме диссертации опубликована 41 работа. Из них 1 монография в издательстве Kluwer, 6 глав в зарубежных монографиях, 22 статьи в рецензируемых журналах и 8 развернутых статей в трудах международных конференций. В совместных работах с проф. Борисом Ковалерчуком (Central Washington University, US) идея подхода, метод, программная система Discovery, и её применения к решению задач принадлежат автору диссертации. Приведенная в главе 5 методика восстановления монотонных Булевых функций принадлежит Борису Ковалерчуку.

Структура и объем работы. Диссертация состоит из введения, шести глав, списка литературы, содержащего 210 наименований. Объем диссертации 222 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

• Определении онтологии предметной области;

• Извлечении из числовых представлений величин множеств отношений и операций, определяющих смысл величин в соответствии с теорией измерений. Перевода данных в многосортные эмпирические системы, используя найденные множества отношений и операций;

• Определении систем аксиом в терминах полученных отношений и опера. ций, которым удовлетворяют рассматриваемые величины и законы;

• Нахождении числовых представлений величин и законов в теории измерений или в теории конструктивных моделей, используя обнаруженные системы аксиом;

• Интерпретации полученных числовых представлений величин и законов в системе понятий онтологии и получении системы величин, связанных между собой законами, как это имеет место в физике.

Анализ этого пути показывает, что есть ещё один путь познания - логический путь познания предметной области, в котором всю информацию из данных можно извлечь с помощью теории измерений и далее проводить извлечение знаний из данных на логическом уровне. Этот путь позволяет обнаруживать не только теории, но и извлекать знания в виде высказываний с оценками.

Далее анализируется логический путь познания. Показывается, что этот путь требует решения достаточно глубоких и нерешенных на настоящее время проблем:

• Знания логически противоречивы и не образуют теорию;

• Предсказание для знаний плохо определено - значения вероятностных оценок знаний резко падают в процессе логического вывода;

• Предсказания, получаемые из знаний, статистически двусмысленны.

Кратко описан предлагаемый в диссертации подход, основанный на семантическом вероятностном выводе, позволяющий решить эти проблемы и открывающий путь логического познания.

Решенные проблемы позволили авторам сформулировать реляционный подход к извлечению знаний, позволяющий достаточно полно извлекать знания из данных, а также решить задачу обнаружения эмпирической теории на данных. Показывается, что предложенный подход снимает ограничения с существующих в Machine Learning методов извлечения знаний. Описываются полученные в рамках подхода приложения в области финансового прогнозирования, медицины и биоинформатике.

Первая глава посвящена логическому анализу данных и законов.

Такой анализ необходим для понимания информационного содержания данных и понимания, что такое величины и законы.

Для этого вводятся основные понятия теории измерений и приведены основные проблемы: существования, единственности и адекватности числовых представлений. Приведем определение числового представления. Пусть некоторая величина определяется системой аксиом Т в сигнатуре О = <Ро,Р[,...,Рп,

pi.....Pm, c0,ci,c2,...), где Pj, i S n, - предикатные символы; pj, j £ m, - символы

операций; C[, 1 e 1, - символы констант (1 = 0 или I - начальная часть ряда на-

туральных чисел со = {0,1,2,...} или I = о); Р0 - равенство.

Величиной будем называть неприводимую (равенство является единственным отношением конгруэнтности) систему 3 = {А; Оз) сигнатуры Q, удовлетворяющую системе аксиом Т; где А — множество значений величины, £1з =

{Р3о,Р3ь...,Р3„, Р3......Р3т, с о, с с г,--.} — множество отношений, операций и

констант сигнатуры Q, интерпретируемых в понятиях предметной области. Числовой системой называется система 5R = (Rek, £2r) сигнатуры П, где Re -множество действительных чисел, к — размерность числового представления, Пя= {=,Р*,.....Р\ р9*!.....р^т, с\, с*„ с\...> - множество отношений, операций и констант, определенных на Rek. Числовым представлением величины 3 = (А; Дз) в числовой системе называется сильный гомоморфизм ц: А -» Rek, удовлетворяющий условиям:

1. P3i(a],...,ami) <=» РЯ|(р.а,,..., да™), i = 0,1.....п;

2. др3Да¡.....а^) = namj),j = l,...,m;

3. цс3] = С9®!, 1 6 I.

Далее формулируются проблемы существования, единственности и адекватности, решаемые в теории измерений.

Вводится понятие эмпирической аксиоматической теории1, которое, с одной стороны, позволяет определить эмпирические системы теории измерений, а, с другой стороны, определяет эмпирическое содержание данных. Эмпирической аксиоматической теорией является набор:

М = < Obsv , V, W, S), где Obsv - измерительная процедура, задающая интерпретацию символов словаря V. Ее применение к произвольному множеству объектов А = {ai,...,am} дает формальную конечную конструкцию prv, состоящую из символов объектов ai,...,am, символов словаря V и, возможно, других вспомогательных символов. Эту конструкцию будем называть протоколом наблюдения, проведенного в соответствии с инструкцией Obsv над множеством объектов А в словаре V;

prv - протокол наблюдения. Мы специально не будем конкретизировать вид этой формальной конструкции, так как в разных наблюдениях она может быть различной. Единственно, что всегда будет требоваться — это точное определение истинности высказываний в словаре V на prv;

V - {РЬ...,Р„,} - словарь (сигнатура) наблюдаемых терминов. Будем предполагать, что равенство "=" всегда содержится в V;

1 Гончаров С.С., Ершов Ю.Л., Самохвалов К.Ф. Введение в логику и методологию науки. М. Интерпракс, Институт математики СО РАН, Новосибирск, 1994.

W = {Qj,...,Qn2} - словарь (сигнатура) теоретических терминов. Отношения из W являются теоретическими конструктами, и идеализацией непосредственно наблюдаемых отношений Pi,...,P„i словаря V = {Р(,...,РП|}. Взаимосвязь отношений теоретического и эмпирического уровня должна осуществляться с помощью правил соответствия;

S = Sv U Sw U SVuVV - система аксиом в словаре VUW. Она включает аксиомы Sv в словаре V наблюдаемых терминов, аксиомы SVuW в объединенном словаре VUW и аксиомы в словаре теоретических терминов.

Понятие эмпирической системы М = (A; W), используемое в теории измерений, можно сформулировать в рамках эмпирических аксиоматических теорий следующим образом. Эмпирическая система является неприводимой моделью системы аксиом Sw. Смысл неприводимости состоит в том, что любые два объекта a,b е А различимы с помощью отношений из W.

Понятие эмпирической аксиоматической теории позволяет показать, как такие известные типы данных, как парные сравнения, множественные сравнения, матричное представление бинарных отношений, матрицы упорядочений, матрицы близости и матрицы объект-признак могут быть представлены в эмпирических аксиоматических теориях. Такое представление преследует следующие цели:

1. Показать, что эмпирические аксиоматические теории являются довольно общим способом представления данных;

2. Привести для каждого типа данных, используя их представление в эмпирических аксиоматических теориях, относящиеся к ним результаты теории измерений. Эти результаты включают в себя системы аксиом в языке первого порядка и теоремы представления и единственности, указывающие, какие числовые представления для данных систем аксиом существуют.

Проводится анализ законов. Анализируется представление законов в теории измерений. Используя результаты теории измерений показывается, что законы просты потому, что они обнаруживаются с одновременным формированием числовых представлений входящих в него величин, что не делает ни один из существующих методов анализа данных или Machine Learning. Для закона вида у = /(x,z) приводится модификация системы аксиом аддитивной соединительной структуры2, для которой доказывается, что если функция f принадлежит классу f 6 F, определенному системой аксиом, то верна теорема.

Теорема (модификация теоремы2). Для любой функции fe F существуют

2 Krantz DH, Luce RD, Suppes P, Tversky A. Foundations of Measurement V.l-3, Acad. Press, NY, London. 1971, 1989, 1990.

взаимно однозначные функции <рх, <рг и монотонная функция ф такие, что

<р/(х, г) = ф„(х) + фг(г) и любая другая функция /'(х', г') = ф/(фхх\ф22'), где ф - строго монотонная функция, фх, фг - взаимно однозначные функции, также принадлежит Б.

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

Устанавливается взаимосвязь между теорией измерений и теорией физических структур. Эта взаимосвязь отвечает сразу на несколько вопросов: во-первых, она дает путь решения вопроса о классификации всех возможных законов природы, который не решен в теории измерений, а, во-вторых, подтверждает положение о том, что обнаруживать законы можно только с одновременным формированием числовых представлений величин.

В теории измерений вопрос о классификации всех возможных законов природы не только не решен, но даже не поставлен. В теории физических структур этот вопрос решен, и получена классификация всех возможных законов. Эта классификация получена на основании принципа феноменологической симметрии. На примере физической структуры ранга (2,2) показана взаимосвязь системы аксиом аддитивной соединительной структуры и физической структуры ранга (2,2).

Для сопоставления теории измерений с теорией физических структур, кратко приводится основной результат теории физических структур о классификации возможных законов природы. Далее доказывается теорема о взаимосвязи физической структуры (2,2) и системы аксиом аддитивной соединительной структуры теории измерений.

Пусть даны два множества М,Ы и вещественная функция (измерительная процедура) а: МхЫ —> Ле, а(1,а) = а,а е 11е, ¡бМ,аеК

На множествах М и N задана физическая структура ранга (ш,п), если существует аналитическая функция Ф от ш»п переменных, определенная в области Е <г Иеш*п такая, что

VI],Ь.....1т,а,.....Оп ф(а,]о1, а;1о2,..., а:тап) = 0,1Ь12.....ь, 6 М, аьа,.....а„ е N.

Это требование является главным и называется принципом феноменологической симметрии. Этот принцип выражает равноправие объектов из М и N по отношению к функциональной зависимости.

Рассмотрим физическую структуру ранга (2,2). Для нее принцип феномено-

логической симметрии имеет вид

V i j,a,ß <p(ala,alß,aja,ajß) = О, где ij б М, a,ß б N. Доказано3, что существуют монотонные функции R,S и строго монотонная функция х такие, что

a1a=3C(R(aiao) + S(ai0a))> (1)

9(aia,aip,aja,aip) = (x)"'(aia) + (x)"'(ajp) - (z)''(aip) - (х)"'(^а) = О В диссертации доказано, что физическая структура ранга (2,2) может быть описана системой аксиом аддитивных соединительных структур теории измерений.

Модель <MxN; < ) называется аддитивной соединительной структурой2, если М * 0, N * 0, а ~ b <=> (а <, b) & (b ä а) и для любых ij,k,... 6 М, а,Ру,." е N вьшолнены следующие аксиомы: <, — слабый линейный порядок;

* э i(U) < (i,p) vja,«) 5; a,ß);

ö,a) ~ (i,ß)&(k,p) ~ Ü>y) => (k,a) ~ (i,y);

* (i,a) < (j,P) 2 (i,r) => 3 e(i,e) ~ (j,ß);

* Э ij,a((i,ct) + (j,a))-

Если 3i(i,a) + (i,ß) и определена ограниченная последовательность i|,i2>... 6 М, (ik,a) ä (j.r)» k = такая» что (ii.a) ~ (¡2,ß), (¡z,a) ~ (i3,ß), (ij,a) ~ (i4,ß), ...,

то она конечна.

Аксиомы, отмеченные звездочкой, сформулированы относительно элементов множества М, аналогичные аксиомы должны выполняться относительно элементов множества N. Числовые представления аддитивных соединительных структур определяет следующая.

Теорема2. Если модель (MxN; £ ) является аддитивной соединительной структурой, то существуют функции <р: М —> Re, \|/: N —> Re, удовлетворяющие, для любых ij 6 М; a,ß G N, соотношению

(i,a) < (j,ß) « Ф(0 + V(a) <; фО) + Y(ß). (2)

Если ф', у - другие функции, удовлетворяющие этой эквивалентности, то существуют е > 0, xi,x2 е Re такие, что ф' = еф + Х|, у = е\|/ + х2.

Пусть в модели (MxN; < ) отношение порядка задается соотношением (i,a)^a,ß)«a,a<ajp. (3)

Теорема 1. Пусть для модели <MxN; < ) выполнено соотношение (3) и на

3 Кулаков Ю.И. Математическая формулировка теории физических структур. -Сиб. Мат. Ж. 1971, т.ХИ, №5, с. 1142-1145.

множествах М^ задана физическая структура ранга (2,2). Тогда эта модель является аддитивной соединительной структурой и для функций Я, в из (1) существуют е > О, XI,х2 6 Ле такие, что Я(а(1,ао)) = £ф(0 + хь 8(а(10,а)) = Е\у(а) + х2 для функций <р, у из (3).

Далее конструируются алгебраическое, а также конструктивное числовое представление физической структуры ранга (2,2). Они дают возможность проанализировать, что представляет собой принцип феноменологической симметрии и каков его логико-алгебраический статус.

Полученное логико-алгебраическое представление закона ранга (2,2) не может быть отображено в действительные числа. Для этого строится более общее - конструктивное представление закона ранга (2,2). Оно дает альтернативный, по отношению к теории измерений, способ представления законов.

Рассмотрим модель (Мх>4; ~ ), М * 0, N ^ 0, удовлетворяющую следующим аксиомам.

Аксиома 1 ~ - отношение эквивалентности на МхЫ.

Аксиома 2 (¡,а)~(1,Р) » 0',«*) ~ (ЬР)>

(1,а)~0,«)<=>0,Р)~а.Р)-

Аксиома 3. Неограниченная разрешимость: для любых трех из четырех элементов У е М, а,р е N четвертый можно подобрать так, чтобы (¡,а) ~ (],р).

Аксиома 4. Для р|,р2,рз,яь42>4з е МхЫ/~ выполнено условие замыкания Том-сена: из р1«Ч2 = Рг*Я1 и р3^| = ргяз следует рз«я2 = Рг'Чз.

Лемма 1. Модель <Мх>1; ~ >, М * 0, N * 0, удовлетворяющая аксиомам 1,3 и условию Томсена, определяет абелеву группу.

Определение 1. Алгебраическим представлением законов ранга (2,2) будем называть модель (Мх>1; ~ ), удовлетворяющую аксиомам 1,3 и условию Томсена. Величинами будем называть абелевы группы (М/~; г ), •), (МхМ/~; • ) с изоморфными между собой операциями •. Закономерной связью между величинами будем называть операцию

Теорема 2. Модель (МхЫ; удовлетворяющую аксиомам 1,3, условию Томсена и конечно-порожденную относительно операции можно отобразить в прямую сумму бесконечных циклических групп целых чисел и примарных циклических групп вычетов целых чисел Ъ = "¿1®...®ХЛ® гр1|Ф...Ф 7?\ так, что величины, представленные абелевыми группами (М/~ ; • ), (Ы/— ; • ), (МхЫ/~ ; • ) будут изоморфны Ъ, а закономерная связь, представленная операцией перейдет в операцию сложения в Ъ и будут существовать изоморфизмы Ф: М/~ —» Ъ, у: N7—> Ъ, х- Мх1Ч/~ —> X, связанные соотношением

Х([1,а]) = Ф([1]) + у([а]), где «+» операция в X.

Эта теорема дает пример конструктивного представления закона.

Дано определение конструктивного, числового представления. В теории измерений нельзя получить числовые представления некоторых величин и законов в силу ограниченности самого понятия числового представления. Величины и законы, описываемые частичными порядками, толерантностями, решетками и т.д. не могут быть сильным гомоморфизмом отображены в поле вещественных чисел. Для числового представления таких величин и законов нами предложено использовать теорию конструктивных моделей4. Основываясь на этой теории нами введено понятие конструктивного числового представления. Значениями величин в этом случае являются натуральные, рациональные или другие эффективно вычислимые числа (например, коды).

Понятие конструктивного числового представления обобщает понятие числового представления таким образом, что числовое кодирование эмпирической системы заменяется на кодирование любыми числами — действительными, натуральными и рациональными. При этом должно быть выполнено условие, чтобы на полученных кодах были определены некоторые эффективно вычислимые функции (общерекурсивные функции), точно соответствующие эмпирическим отношениям и операциям.

При конструктивном представлении величин значения а 6 А величин 3 = (А; Пз> нумеруются (кодируются). Нумерацией4 множества А называется отображение V множества натуральных чисел со = {0,1,2,...} на А, V: ы А. Пару (3 ) будем называть конструктивным представлением величины 3 (конструктивной системой4), а нумерацию V - конструктивным числовым представлением (конструктивизацией4), если существует характеристические общерекурсивные функции Р\РЫ,.....Рм„ со значениями во множестве {0,1}, общерекурсивные функции ркь..-,рМт и натуральные числа сы0, снь с^,... такие, что

1. Р3;(угц,-, уа™) <=> (Р"(а,,...,а™) = 1), I = 0,1.....п;

2. р^Уаь...,уа„д) = ур^(аь...,ат)),] = 1,...,т;

3. с31 = 1 е I.

Конструктивное числовое представление V аналогично шкале, только вместо числовых отношений, операций и констант используются общерекурсивные функции и натуральные числа. Конструктивной числовой системой является система N = <ю;£2ы), = {РМ0,РМ„...,РМП, р",.....ркт, сы0, с\ с\...}. Из определения очевидна полная аналогия между числовым и конструктивным число-

4 Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. М. Наука, 1980.-415с.

вым представлениями. Далее дается аналогичная формулировка проблем существования, единственности и адекватности для конструктивных числовых представлений.

Установлена связь между числовым и конструктивным числовым представлениями. Показано, что если существует оба числовых представления, то существует также и конструктивное представление числового представления.

Приводится серия простых примеров конструктивных числовых представлений величин. Показано, что конструктивные числовые представления могут рассматриваться как измерительные процедуры для таких нестандартных измерений как тестирование, анкетирование, обследование и т.д. Примером конструктивного числового представления закона является конструктивное представление физической структуры ранга (2,2).

Рассматривается одна из наиболее распространенных шкал величин - шкала экстенсивных величин. Определена система аксиом для конструктивной процедуры шкалирования приборов, измеряющих экстенсивные величины. Доказано, что конструктивное числовое представление этой системы аксиом даёт конструктивное числовое представление рациональных делений шкал приборов этих величин. Таким образом, даже для традиционных числовых представлений величин показано, как для них можно получать конструктивные числовые представления, которые в некоторых случаях даже более естественны, чем традиционные.

Во второй главе разрабатывается процесс познания, основанный на теории измерений. Вводятся необходимые определения и теоретические построения, описывающие процесс обнаружения эмпирической теории в условиях шумов.

Обнаружено свойство эксперимента, гарантирующее универсальную аксиоматизируемость экспериментальной зависимости 8У. Таким свойством оказывается наследственность результатов эксперимента. Под экспериментальной зависимостью понимается совокупность всех формул в языке первого порядка в словаре V, истинных на любом результате наблюдения ргу = ОЬб(А). В данном случае протокол наблюдения ргу определяется как модель ргу = (В;У). Обозначим через РЯ множество всех конечных моделей, которые могут быть получены в качестве протоколов наблюдения измерительной процедурой ОЬву над всеми возможными множествами объектов А. Обозначим через Т абстрактный класс всех конечных моделей сигнатуры V. Нам нужно найти необходимое и достаточное условие универсальной аксиоматизируемости класса РЛ в классе Т. Будем предполагать, что нам известна функция ж: А —» В, В = {а1,...,ат}, взаимно однозначно ставящая в соответствие объектам А их символы в протоколе рг\

Опираясь на теорему Лося-Тарского5 можно определить достаточное условие универсальной аксиоматизируемости экспериментальной зависимости.

Теорема (Лось-Тарский5). Для того, чтобы подкласс PR класса Т был универсально аксиоматизируем в классе Т необходимо и достаточно, чтобы подкласс PR был локально замкнут в Т.

Определение 2. Будем говорить, что эксперимент удовлетворяет свойству наследственности, если выполнены следующие условия.

1. В процессе наблюдения не производится конструирования новых объектов, и поэтому протокол наблюдения имеет вид: prv = <n(A);V) = Obsv (А).

2. Для любого протокола рг = <jt(A);V> = Obsv (А) и любого подмножества В с А протокол рг = (rc(B);V) = Obsv (В), полученный на этом подмножестве, изоморфен подмодели <7t(B);V), я(В) с я(А) модели prv = (:t(A);V).

Из определения 2 следует наследственность класса PR в классе Т.

Теорема 3. Если эксперимент удовлетворяет свойству наследственности, то экспериментальная зависимость Sv универсально аксиоматизируема.

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

Определение 3. Методом обнаружения экспериментальной зависимости мы будем называть отображение

М: <SV, pr0v> Smv,

где Sv - совокупность универсальных формул, истинных на pr0v, представляющее собой априорную информацию для метода; Smv — совокупность универсальных формул в словаре, V обнаруживаемых методом на протоколе pr0v. Формулы из Smv не выводимы из Sv.

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

С = (А]&...&Ак => А0 ), где (4)

Aj = Pj (xi1,...,xJ„j)CJ j, j = 0,1,...,k, x0b...,x0n0, x1!.....x'„i ,-.., xki.....xknk - свободные

переменные; ............ - местности предикатных символов P0,Pi.....Рь символы

£о,£ь—,£к <= {0,1} - означают наличие (0) отсутствие (1) отрицания.

Далее анализируя правила (4) и доказывается следующая теорема.

Теорема 4. Правило С = (Ai&...&Ak => А0) логически следует (в исчислении высказываний) из любого правила вида: 1. An&...&Ajh =>-.Аю ,

5 Мальцев А.И. Алгебраические системы, М., Наука, 1970.

- 15-

где {A¡i,...,A¡h,A¡o} с {Аь...,Ак}, О ¿ h < к, т.е.

(Aü&.-.&Aih => —iA,o) i- —i(A|&...&Ait) у (Ai&...&Ak => A0);

у - доказуемость в исчислении высказываний.

2. (Aii&...&Aih => Ао),

где {Aib...Аь} с {Ai,...,Ak}, 0 á h < k, т.е.,

(A¡i&...&A¡h =5 Ао) у (Ai&...&Ak => Ао).

На основании этой теоремы вводится понятие закона для некоторой эмпирической системы М.

Определение 4. Законом на эмпирической системе М = <A,W) будем называть любое, истинное на М, правило С вида (4), для которого каждое из его подправил, определенных в п.п. 1,2 теоремы 4 не истинно на М.

Обозначим множество всех законов эмпирической системы М через PR(M).

Теорема 5. PR(M) н Th(M), где Th(M) - теория модели М.

Вводится понятие эксперимента на эмпирической системе. Понятие закона переопределяется для множества Ехр всех возможных результатов эксперимента. Определяется вероятность на множестве экспериментов и высказываний.

Понятие закона обобщается на вероятностный случай.

Определение 5. Вероятностным законом на Ехр в детерминированном случае будем называть правило С = (Ai&...&Ak => Ао) вида (4), удовлетворяющее условиям:

a) условная вероятность p.(Ao/At&...&Ak) правила определена (т.е. Ц.(А,&...&Ак) > 0) и n(Ao/Ai&...&Ak) =1;

b) условная вероятность |i(Ac/Ai&...&Ak) правила строго больше условных вероятностей каждого из его подправил.

Определение вероятностного закона в детерминированном случае вводится так, что бы понятие закона оставалось частным случаем этого определения, т.е. верна

Теорема 6. Для правила С = (А1&...&Ак => Ао) вида (4) следующие два условия эквивалентны:

1. правило С является законом на Ехр;

2. правило С является вероятностным законом в детерминированном случае.

Понятие вероятностного закона в детерминированном случае обобщается на

понятие вероятностного закона в общем случае. Такое обобщение получается удалением п. «а» из определения 5. Вводится общее определение закона и аргументируется, что, с точки зрения этого определения закона, данное обобщение корректно и сохраняет свойство быть законом.

Вводится понятие шума в эксперименте. Дается определение сохраняющего шума, при котором множество законов и вероятностных законов совпадают. Наличие такого шума в эксперименте не мешает обнаружению эмпирической теории.

Приводится пример сохраняющего двоичного шума и доказывается теорема о том, что наличие такого шума не изменяет множества законов.

Теорема 7. Множества вероятностных законов для экспериментов с двоичным шумом и экспериментов без шума совпадают.

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

Анализируется взаимоотношение знания и познания и рассматривается задача: обнаружить Логическую Эмпирическую Теорию (ЛЭТ), включающую знания.

Знания — это высказывания, имеющие некоторую степень вероятности, нечеткости, размытости или достоверности. Будем предполагать, что ЛЭТ содержит не только истинные знания, но и вероятностные.

Рассмотрение ЛЭТ, включающей знания сталкивается со следующими принципиальными и нерешенными проблемами:

1) Знания логически противоречивы и не образуют теорию;

2) Предсказание для знаний плохо определено — вероятностные оценки знаний резко падают в процессе логического вывода;

3) Предсказания, получаемые из знаний, статистически двусмысленны.

Эти проблемы известны и обсуждаются, например, в широко цитируемой работе6 L.De Raedt and K.Kersting. Probabilistic logic learning. В ней говорится, что «одними из центральных вопросов методов извлечения знаний и искусственного интеллекта является вероятностное логическое обучение, т.е. интеграция реляционных или логических представлений, вероятностного вывода и обучения».

Проблемы 1-3 являются следствием более глубокой проблемы:

4) В настоящее время нет адекватного синтеза логики и вероятности.

Этой проблеме в 2002 был посвящен workshop "Combining Probability and

Logic". В аннотации к workshop говорится "Artificial intelligence is one key discipline in which probability theory competes with other logics for application. It is becoming vitally important to evaluate and integrate systems that are based on very

6 Probabilistic Logic Learning, L. De Raedt, K. Kersting, in ACM-SIGKDD Explorations, special issue on Multi-Relational Data Mining, vol. 5:1, pp.31-48, July 2003.

different approaches to reasoning, and there is strong demand for theoretical understanding of the relationships between these approaches".

Однако настоящего синтеза логики и вероятности в этих работах не сделано.

Нам удалось разрешить проблемы 1-4 и осуществить синтез логики и вероятности для понятия предсказания путем определения семантического вероятностного вывода, который следует идее семантического подхода к программированию7, выдвинутого С.С.Гончаровым, Ю.Л.Ершовым, Д.И.Свириденко.

Идея семантического программирования состоит в том, чтобы процесс вычисления рассматривать как проверку истинности утверждений (включая возможное использование логического вывода) на некоторой модели (моделью могут бьггь данные, представленные некоторой многосортной системой; некоторая специальная модель теории или абстрактного типа данных и т.д.). При таком взгляде на процесс вычисления, процедуру логического вывода можно обобщить, рассматривая более разнообразные взаимоотношения высказываний и модели - рассмотреть процесс вычисления как, например, определение наиболее вероятных, подтвержденных или нечетких высказываний на модели. Такой обобщенный вывод будем называть семантическим.

Далее рассмотрены перечисленные выше проблемы 1-4 и дано их решение на основании семантического вероятностного вывода.

Рассмотрен индуктивно-статистический вывод (I-S вывод), традиционно используемый для получения предсказаний и определяется семантический вероятностный вывод.

Определение 6. Под семантическим вероятностным выводом (СВВ) некоторого сильнейшего для предсказания атома G вероятностного закона Сп (не являющееся подправилом некоторого другого вероятностного закона) мы понимаем последовательность вероятностных законов С| с Сг с ...с С„, такую, что: Q = (А1, =>G), i = l,2,...n, n > 1,

правило Ci является подправилом правила Cj+ь г|(См)>Л(С>), i= 1,2,...п-1,

Предложение 1. Для любого закона существует его СВВ-вывод.

Семантический вероятностный вывод позволяет решить проблему статистической двусмысленности' путем' определения Максимально'Специфических Правил.- ■ " • '' : ■'•• ' '

Определение 7. Максимально Специфическим Правилом MCTI(G) для вы-

7 S.S.Goncharov, Yu.L.Ershov, D.I.Sviridenko, Semantic programming // lOth World Congress Information Processing 86, Dublin, Oct.,1986. - Amsterdam, 1986, p. 1093-1100.

вода факта G будем называть сильнейший вероятностный закон (СВЗ) (имеющий максимальную оценку условной вероятности) среди всех СВЗ-законов, выводимых семантическим вероятностным выводом для факта G.

Множество всех MCn(G) обозначим через МСП.

Определяется требование максимальной специфичности и доказывается теорема:

Теорема 8. Любое МСП(С)-правило удовлетворяет требованию максимальной специфичности.

Следствие 1. Любой закон удовлетворяет требованию максимальной специфичности.

Доказывается, что введенное понятие максимально специфического правила решает проблему статистической двусмысленности.

Теорема 9.1-S вывод непротиворечив для любой теории J с МСП.

Таким образом в данной главе доказывается, что с помощью семантического вероятностного вывода можно вычислить:

- Все законы;

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

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

В результате, проблемы 1-4 решаются следующим образом:

1) Множество максимально специфических правил непротиворечиво. Таким образом, множество максимально специфических правил является непротиворечивой вероятностной теорией, включающей знания;

2) Максимально специфические правила решают проблему статистической двусмысленности.

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

Проводится логический анализ методов Machine Learning и KDD&DM. Показывается, что если методы не основаны на теории измерений, то для них возникает проблема адекватности — доказательство инвариантности метода относительно допустимых преобразований шкал. В противном случае метод может давать различные результаты в зависимости от того, в каких единицах измерения представлены данные. Вводится определение инвариантности метода относительно выбора числовых представлений для данных. Выделяется логическая составляющая данных. Показывается как для любого метода Machine Learning и KDD&DM можно получить его логический аналог, для которого нет проблемы инвариантности.

В результате проведенного анализа показывается как для каждого Machine Learning и KDD&DM можно выделить:

(1)тип данных, с которыми работает ИГО&ОМ-метод в виде многосортной эмпирической системы;

(2) онтологию метода в виде множества отношений и операций, в которых записаны данные и представлены гипотезы метода;

(3) тип знаний метода как класс правил, которые проверяет метод. Аргументируется, что в отличии от конкретного KDD&DM-MeTOfla разработанная в рамках реляционного подхода система Discovery не имеет ограничений ни в типе данных, ни в онтологии, ни в классе обнаруживаемых знаний.

Описывается разработанный реляционный подход к извлечению знаний и теорий, реализующий логический процесс познания.

В реляционном подходе к извлечению знаний следующим образом снимаются все ограничения с существующих ML, KDD&DM методов:

(1) ограничения с используемых типов данных за счет использования теории измерений и многосортных эмпирических систем;

(2) использование теории измерений позволяет извлекать всю информацию из данных, чего не делают другие методы;

(3) ограничения в использовании априорного знания путем представления априорного знания в логике первого порядка;

(4) ограничения с классов проверяемых гипотез за счет введения типа обнаруживаемых знаний Rule Туре в языке первого порядка;

(5) разработана система Discovery, которая обнаруживает все перечисленные ниже виды множеств:

(a) все законы на эмпирической системе;

(b) все максимально специфические правила;

(c) все правила с максимальной оценкой условной вероятности;

(6) база знаний, обнаруживаемая системой Discovery полна в двух смыслах: (i) в смысле полноты извлечения информации из данных за счет использования теории измерений; (ii) полноты обнаруживаемых множеств правил (а), (Ь),(с);

Кратко описывается программная система Discovery, реализующая семантический вероятностный вывод и реляционный подход к извлечению знаний, и определяется метод обнаружения вероятностных законов на данных.

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

разности в процентах между текущей ценой на момент закрытия биржи и ценой на пять дней вперед (предоставленную журналом Journal of Computational Intelligence in Finance). Ниже мы приведем типы найденных закономерностей и полученные статистические характеристики этих закономерностей, а также проценты ошибок первого и второго рода на контрольных данных.

Для применения реляционного подхода необходимо извлечь информацию из финансовых временных рядов с помощью набора отношений и операций.

С этой целью рассматриваются преобразования числовых данных в отношения. Для обучения использовался временной ряд TR = {аь ... .а^} с данными за десять лет 1985-1994 (2528 торговых дней) и контрольный временной ряд CT = {ai.....а«} с данными за два года 1995-1996 (506 торговых дней).

Пять последовательных дней использовались как объект рассмотрения а, =(а],а? ,аъ, ,а* ,а?), где а\ - j-й день пятидневого объекта а,. Мы также будем использовать другое обозначение

а, = (at,at+1,a(+2,at4.j,a14.4), где a{l_i)4,= а/, j = 1....5.

Фактически, индекс t указывает первый день пятидневого объекта.

День недели, обозначаемый как функция (а,), имеет пять значений: 1,2,3,4,5, где день недели (а,) = 1 указывает, что а, - понедельник, а день недели (а,) = 5 указывает, что а, - пятница. Мы не рассматриваем субботы, воскресенья и праздники, потому что фондовая биржа закрыта в эти дни.

Было определено также несколько множеств функций:

1. Первая разность:

A ij (ai) = {SPS00C(a/ ) - SPSOOCXdr,'))/SP500C(a', ), i < j, i, j = 1.....5.

Эта функция представляет собой разность между SP500C для i-тых и j-тых дней, нормализованных относительно SP500C для i-того дня.

2. Разность между двумя относительными разностями: A,jk(e,) = Ajk(«;) - Лц(л,>

3. Функция wd(а) отображающая пять календарных дней в числа. Формально, вектор-функция vid(b)—(di, ..„¿/^эквивалентна выражению

(день недели (b')=di) и (день недели (b2)=ds)&..,&(denb недели (bs)=ds), wd (а) = (1,2,3,4,5) означает, что а представляет собой пять последовательных дней недели с понедельника по пятницу.

4. Циклические перестановки к длины 5 объекта а. Используя перестановку к, мы можем преобразовать последовательности дней. Например,

7t (Mon, Tue, Wed, Thu, Fri) = (Tue, Wed, Thu, Fri, Mon) = (d^.dj.d^ds).

Таким образом, к - циклическая перестановка, которая изменяет множество

рассматриваемых дней недели

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

Определим общий вид отношений (без индексов), которые будут применяться для любых пятидневых объектов а и Ь: (Д(а) ^ А(Ь)У .

Примерами таких отношений являются любые из неравенств: (Д;/а) 5 Д,;(Ь))е, (Дцк(а) 5 Д,*(Ь)), ¡<^<к; = 1,..,5.

Следующие множества гипотез Н1-Н4 использовались для обнаружения вероятностных законов. Множество гипотез Н1 :

(\ус1(а) = \у<1(Ь) = (й,,...,с15)) & (Д(а) 5 Д(Ь))е1 => ((цель(а5) 5 цель(Ь5))'0; Множество гипотез Н2.

[\ус!(а) = \ус1(Ь) = (<!,,...А)] & [Д(а) 5 Д(Ь)]с,&[Д(а) 2 Д(Ъ)]'2 => [цель(а') ^ цель(Ь5)]'0;

Это множество гипотез имеет схожую интерпретацию. Единственное различие от гипотез Н1 в том, что теперь мы рассматриваем две разности в правилах.

Множество гипотез НЗ.

Оф) = ™с!(Ь) = <с11,...^5)]&[Д(а)2Д(Ь)]е1&[Д(а)£Д(Ь)]с2&[Д(а)й Д(Ь)]е3 => [цель(а') г цель(Ь5)]Е°. Множество гипотез Н4.

М(а) = wd(b) = (с11,...,а5>]&[Д(а) 5 Д(Ь)]"& ... &[(Д(а) * Д(Ь)]ек => [цель(а5) 5 цель(Ь5)]с0.

Эти гипотезы позволяют нам задавать гипотезы с более, чем тремя отношениями, включающими Д^к(а,).

Пример обнаруженного правила, сформулированного в финансовых терминах:

ЕСЛИ конец текущей пятидневки - понедельник, и есть некоторая другая пятидневка в истории 1984-1996 торгов, которая также заканчивалась в понедельник.

И относительная разность БР500С между вторником и четвергом для старых пяти дней не больше чем между вторником и четвергом для текущих пяти дней

И относительная разность БР500С между вторником и понедельником для старых пяти дней больше чем между вторником и понедельником для текущих пяти дней

И относительная разность между SP500C разностями для вторника, сре- (б) ды и для среды и четверга, для старых пяти дней не больше чем для аналогичных пар дней текущих пяти дней

И (мы опускаем лингвистическое описание (A24s(a) > Дг45(Ь)), которое является подобным предыдущему>

ТО значение целевого признака для понедельника текущих 5-ти дней должно быть не больше чем значение целевого признака для понедельника из пяти дней предыстории, то есть, мы предсказываем, что биржевая цена за пять дней вперед от текущего понедельника станет не больше чем эта же цена на пять дней вперед относительно понедельника в предыстории.

Рассматриваются Марковские цепи как примеры вероятностных законов в финансах. Марковские цепи, использующие условные вероятности как вероятности перехода, являются примерами методов, использующих гипотезы типа Н1-Н4.

Примером Марковской цепи является правило:

ЕСЛИ цена акции увеличилась вчера,

ТО цена акции увеличится сегодня с вероятностью 0.7.

Показано, как данный тип моделей может быть представлен гипотезами типа Н1-Н4.

Приводятся результаты обучения. Множества гипотез Н1-Н4 были протестированы системой "Discovery" на обучающем множестве TR = {ai,...,aIr} путем случайного выбора пар объектов a, b из TR. Результатом обучения являлось множество Law всех возможных вероятностных законов, найденных на TR. Для каждого из этих вероятностных законов была посчитана его условная вероятность на TR.

Чтобы проверить устойчивость закона при переходе к контролю, оценивалась его условная вероятность на контрольном множестве СТ. Мы не использовали эти условные вероятности, для определения предпочтения закона в процессе обучения.

Приведем пример законов с относительно высокими условными вероятностями на обучающем TR и контрольном множестве CT:

1. [wd(a) = wd(b) = <2,3,4,5Д>)&(Д,3(а)<;Дп(Ь)]&

[Д15(а)>Д15(Ь)] & [Д234(а) <: Д2з4(Ь)] & [Д245(а) > Л245(Ь)] (7)

=> цель(а5) s цель(Ь®). Для этого правила частота на обучении TR была равна 0.64, а на контроле CT 0.76. Этот закон сформулирован на финансовом языке в формуле (6).

В общей сложности было обнаружено 134 закона, позволяющие предсказывать целевое значение по индексу SP500C. Среднее значение условных вероятностей закономерностей на обучении равно 0.5813, а значение условных вероятностей закономерностей на контроле СТ равно 0.5759, Все условные вероятности оценивались как относительные частоты на TR и СТ, соответственно.

Эксперимент показал, что условная вероятность достаточно устойчива при переходе от обучающих к контрольным данным. Полученная разность равна 0.0054=0.5813-0.5759, т.е. 0.54 %.

Приводится оригинальный метод прогноза, основанный на обнаруженных вероятностных законах. Мы можем использовать множество обнаруженных законов Law для предсказания, только если нам известна правая часть (цель(а5)) или левая часть (цель(Ь5)) прогнозируемого неравенства

(цель(а5) s цель(Ь5))Е°, которая является заключением законов. Например, если цель(Ь5) = 45 и еО = 0 (мы предсказываем отрицание неравенства, то есть отношение > ), то мы можем предсказать, что цель(а5) > 45. Если мы берем оба объекта а и b из СТ, то прогноз невозможен, потому что оба целевых значения - неизвестны. Но если взять объект а из TR, а объект Ь из СТ, то можно предсказать нижнюю границу неизвестной величины целъ(Ь!), если еО = 1, и верхнюю границу, если еО = 0.

Целевое значение для объекта а из СТ предсказывается путем применения всех закономерностей из множества Law к двум множествам пар объектов {<a,b)|b е TR} и {<b,a)|b е TR}.

Для каждого правила, первое из этих множеств дает верхние границы Upl(a5) = {цель(Ь5)>, если еО = 1, и нижние границы Lowl(a5) = (target(b5)}, если еО = 0 для неизвестного значения цели(а5). Так же вторые из этих множеств {(b,a)|b е TR} дают нижние границы

Low2(as) = {targetib5)} если е0 = 1, и верхние границы Up2(a5) = {target(bs)}, если еО = 0 для неизвестного значения цели(а!). Таким образом, мы получаем множества верхних и нижних границ

Upl(a5), Up2(a5), Lowl(a5), Low2(as) для цели(а5) путем объединения границ для всех закономерностей. Рассмотренные закономерности дают прогноз для последнего дня пятидневого цикла, используя данные предыдущих дней.

Затем использовалась порядковая статистика с определенным доверительным уровнем для определения интервалов предсказаний - верхних и нижних границ. Проблема состояла в том, что множества границ Upl(a5), Up2(as),

Lowl(as), Low2(as) перекрываются и не могут прямо использоваться для прогноза интервалов в таком виде.

Мы вычислили р-квинтили (р = 0.55, 0.60, 0.65, 0.70, 0.75, 0.80, 0.85, 0.90) для верхних границ цели(а5) и (1-р) - квантили для нижних границ цели(а'). Для каждой величины р-квинтиля (р = 0.55, 0.60, 0.65, 0.70, 0.75, 0.80, 0.85, 0.90) мы получили верхнюю границу Upp(a5) и нижнюю границу Lowp(a5) для значения цели(а5), взятые, соответственно, из Upl(as)uUp2(as) и Low 1 (a5)uLow2(a!).

По умолчанию Lowp(as) =■ - » для больших значений р (например 0.80, 0.90, 0.95), если (1-р) - квантиль меньше, чем наименьшее значение нижней границы для цели(а5). Точно так же Upp(as) = +<» для больших значений р (например 0.80, 0.90, 0.95), если р-квинтиль больше, чем наибольшее значение соответствующей верхней границы.

Прогноз не делается, если нижняя граница Lowp(as) больше, чем верхняя граница Upp(a5). Это иногда имело место для небольшого р (например, 0.55, 0.60, 0.65). Также прогноз не может быть вычислен, если получен р-интервал -

Приводятся результаты эксперимента №1 прогнозирования для гипотез Н1-Н4. Мы оценивали качество прогноза для каждого р-квинтиля на всех объектах из СТ, используя шесть параметров: процент отказов, процент ошибок, процент правильных предсказаний, средняя длина р-интервалов для всех прогнозов (ML), средняя длина р-интервалов для всех правильных прогнозов (MLR) и ограниченный средний квадрат ошибки прогноза (bound forecast mean square error BF MSE), то есть средний квадрат разности между прогнозом и ближайшей границей р-интервала для прогнозов, которые находятся вне р-интервала.

В Таблица 1 приведены параметры прогноза для обучающегося множества СТ. Из таблицы видно, что с ростом р процент правильных предсказаний растет, а интервалы прогноза увеличиваются.

Таблица 1. Выполнение метрики для ряда регулярностей

p-value Rejections Errors Right Forecast ML MLR BF MSE

0.55 102 (23%) 268 (61%) 72 (16%) 0,54 1.21 2.01

0.60 17 (4%) 315(71%) 110(25%) 0.82 1.33 1.59

0.65 4 (0.9%) 279 (61%) 168 (38%) 1.24 1.57 1.75 ,

0.70 4 (0.9%) 215 (49%) 223 (50%) 1.76 2.01 1.99

0.75 3 (0.7%) 176 (40%) 263 (59%) 2.33 2.58 1.72 :

0.80 3 (0.7%) 125 (28%) 314(71%) 3.03 3.24 1.38

0.85 3 (0.7%) 71 (16%) 368 (83%) 3.94 4.09 1.22

0.90 10 (2.2%) 35 (7.9%) 397 (90%) 5.19 5.25 1.10

Анализируется качество предсказания для конкретной закономерности (7). Мы рассматривали различные р-квантили и нашли объекты, которые связаны со специфическим р-значением. Например, р = 0.55 дает нам 58 объектов и 28 из них предсказаны правильно (в относительно узком интервале прогноза), см. Таблица 2. Увеличение р позволило нам дойти до 100% правильности прогноза, но с более широким интервалом прогноза и меньшие числом объектов. Это означает, что для практического использования прогноза надо выбирать некоторый приемлемый уровень р.

Таблица 2. Качество прогноза для закономерности из примера 1.

p-value Right forecast ML MLR BFMSE

0.55 28 from 58 (48,3%) 2.806 0.269 2.640

0.60 36 from 62 (58.1%) 3.111 0.925 3.347

0.65 34 from 56 (60.7%) 3.471 1.386 2.146

0.70 30 from 46 (65.2%) 4.081 2.119 1.989

0.75 26 from 37 (70.3%) 5.059 3.172 0.604

0.80 24 from 29 (82.8%) 4.962 4.013 0.114

0.85 16 from 18(88.9%) 6.129 5.411 0.029

0.90 8 from 8 (100%) 6.221 6.221 0.000

Этот выбор зависит от индивидуальных целей инвестора, приемлемого уровня риска и ситуации. Поэтому выбор должен быть частью торговой стратегии, которая требует специального исследования.

Рассматриваются преимущества предсказания цели по конкретной закономерности типа Н1-Н4. Если мы эксплуатируем все 134 найденные закономерности, цель может быть предсказана фактически для всех объектов, но для некоторых из них интервал прогноза может быть очень большим и бесполезным. Используя конкретную закономерность, цель может быть предсказана только для вполне определенных объектов и намного точнее. Эти объекты отбираются проверкой условия С? закономерности (ЕСЛИ (3, ТО Т). Если утверждение О верно для этих объектов, то предсказание Т применяется.

Описывается эксперимент №2 по обнаружению структурных законов во временных рядах. Этот эксперимент использовал ежедневные данные БР500 в течение десяти лет на обучении (1984-1994) и ежедневные данные за четыре года (1995-1998) на контроле. Контрольные данные были разделены на два множества, (1995-1996) и (1997-1998). Примером структурной гипотезы является следующая:

ЕСЛИ индекс 8Р500С повысился с пятницы три недели назад к среде две

недели назад

И понизился со среды две недели назад к понедельнику текущей недели,

ТО индекс SP500C повысится в следующий понедельник.

Этот закон подтверждается на контрольных данных (1995-1996) в 78 % случаев.

Используя эти структурные законы, система Discovery получила ежегодный выигрыш 143.83 % для 1997-1998 годов и 126,69 % для 1995-1996 годов.

Приводится сравнение качества системы Discovery с другими методами. Пассивные стратегии не предполагают регулярную торговлю. Пассивные стратегии, такие как buy-and-hold и свободные от риска инвестиции с 3%-ым ростом прибыли, рассматриваются нами как точки отсчета.

Наряду с пассивными, мы опробовали различные активные торговые стратегии для моделирования торговой выгоды/потери. Методы сравнивались на тех же самых данных, что и в экспериментах 1,2.

Для сравнения использовался, в частности, адаптивный линейный прогноз, определяемый следующим образом: yj+] = у; + е, где yi+i является предсказанным курсом акций, е = у( - ум (i > 1) и у„ и ум - курсы акций в течение предыдущих дней. Эта стратегия дает приблизительно 120% ежегодной прибыли. Приводятся различные торговые стратегии. Использование торговых стратегий и их сравнение должно опираться на различные меры качества. Существуют различные меры качества стратегий. Одной из обсуждаемых мер является величина Sharpe Ratio.

Приводятся результаты сравнения- со стратегией buy-and-hold. Стратегия buy-and-hold означает купить п акций в первый торговый день и продать их в последний торговый день. По этой стратегии было куплено 48 акций за 55.6$ каждая (полные инвестиции 2668.7$) 3 января 1995 и проданы за 60.36$ 31 декабря 1996 с доходом в 228.44$ (8.56 % от начального капитала buy-and-hold).

Приводится сравнение (см. таблицу 3) стратегии buy-and-hold со стратегией, использующей обнаруженные структурные законы, описанные в §45.

Таблица 3. Сравнение со стратегией buy-and-hold за 1995-1996г.

Характеристики, .. , ,, х;<, Активная торго-i. вая стратегия ; п , i Buy-and-,, hold

Средние инвестиции за 1995-1996 994.53 2668.7

Общее число акций 48 48

Прибыли за 1995-1996 1059.87 228.44

Прибыль (% к полученному капиталу) 52.92% 7.88%

Прибыль (% к средним торговым инвестициям) 106.57%

Прибыль (% к начальным buy-and-hold инвести- Не применимо 8.56%

циям)

Активная торговая стратегия, основанная на обнаруженных закономерностях, дала прибыль 1059.87$ (для 48 акций) в отличие от 228.37$ в стратегии buy-and-hold для тех же самых 48 акций. Для упрощения анализа все налоги игнорируются.

Приводятся результаты сравнения с другими методами. Таблица 4 показывает, что система Discovery по проценту правильного прогноза превосходит другие методы.

Таблица 4. Качество прогноза полученного различными методами._

Метод % правильного прогноза SP500C

1995-1996 1997-1998* 1995-1998

Свободный от риска (3%) N/A N/A

Нейронная сеть (с препроцессингом) 68% 57 62.5%

Правила, извлеченные из NN (косвенная ä 68% < 57% S 62.5%

оценка)

Дерево решений (Sipina с С4.5) 67% 60% - 64%

Discovery 78% 85% 81.5%

Логика первого порядка (FOIL) 50.50% 45.40% 47.95%

Приводятся также результаты (см. таблицу 5) сравнения методов не по проценту ошибок, а с использованием стратегий игры. Наиболее интересно сравнение системы Discovery со стратегией Buy-and-HoId (В&Н). Стратегия В&Н немного выиграла у Discovery в 1995-1996гг. (30.39 % для В&Н и 26.69 % для Discovery, см.Таблица 5). С другой стороны, Discovery значительно выиграла у Buy-and-HoId за 1997-1998 (43.83 % для Discovery и 20.56 % для В&Н) Таблица 5. Сравнение различных стратегий игры за год для SP500._

Метод Годовая прибыль в торговой игре (% от начальных инвестиций)

1995-1996 1997-1998 Среднее 1995-1998

Adaptive Linear 21.9 18.28 20.09

Discovery 26.69 43.83 35.26

Buy-and-Hold 30.39 20.56 25.47

Risk-Free 3.05 3.05 3.05

Neural Network 18.94 16.07 17.5

Даются выводы из финансовых приложений. Реляционный подход к извлечению знаний в состоянии обнаруживать закономерности в таких сильно за-

шумленных данных как финансовые ряды, и прогнозировать такие сложные данные как курсы акций и индексов.

В пятой главе рассматриваются приложения реляционного подхода в медицине.

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

Традиционные Экспертные системы опираются на диагностические правила, извлеченные из эксперта. Системы, основанные на методах Machine Learning, опираются на обнаруженные диагностические правила. Эти два множества правил могут противоречить друг другу. Главная проблема - обнаружить достаточные, полные, и сопоставимые наборы правил, извлеченных из данных и из эксперта. Нами разработаны методы обнаружения полных наборов экспертных и обнаруживаемых на данных правил.

Эта цель приводит нас к экспоненциальной проблеме извлечения диагностических правил. Лобовой метод может потребовать задания тысяч вопросов эксперту. Например, для 11 бинарных диагностических признаков сгруппированных кальцинозов есть (211 = 2,048) комбинаций признаков, каждый из которых представляет новый случай. Лобовой метод потребовал бы опроса радиолога для каждой из этих 2.048 комбинаций. Мы разработали эффективный механизм для декомпозиции знаний на основе свойства монотонности для решения этой проблемы.

Рассматривается метод извлечения диагностических правил из эксперта, используя иерархический подход. Мы строим иерархию интерпретируемых признаков, начиная с обобщенного уровня до все менее обобщенного. Эта иерархия начинается с определения 11 медицинских бинарных признаков. Медик-эксперт определил, что первичные 11 бинарных признаков Wi, w2, w3, у у2> у3, У л, У 5. х3, Х4Х5 могут быть организованы в иерархию с добавлением двух новых обобщенных признаков Xi и х2, являющимися функциями соответственно признаков Wi, W2, w3 и у), у2, у3, у.), у5. Мы рассматриваем х2 как функцию v(yi, у2, Уз, У4, ys)> которая должна быть идентифицирована для диагностики рака и Xi как функцию v(wi,w2,w3).

Эксперт идентифицировал, что функции v и у должны быть общими для совместного решения двух связанных проблем:

(Р1) рекомендовать биопсию, определяемую неизвестной функцией ft; . (Р2) диагноз рака, определяемую неизвестной функцией f2 fi(Xl,X2,X3,X4,Xs) = fi(v(w,,w2,w3), У<У1,У2,Уз,У4,У5), Хз,Х4,Х5), i = 1,2.

Таким образом, задача состоит в определении функций fi, f2 путем опроса эксперта.

Рассматривается свойство монотонности, которое позволяет решить эту проблему. Приводится методика восстановления Булевой функции, удовлетворяющей условию монотонности.

Чтобы понять, как монотонность может быть использована в проблеме рака груди, рассмотрим оценку кальцинозов в маммограммах. Мы можем представить клинические случаи в терминах бинарных векторов с пятью обобщенными признаками: (х1,х2,хз,х4,х5). Рассмотрим два клинических случая, которые представлены двумя двоичными последовательностями: (10110) и (10100). Если радиолог правильно диагностировал набор (10100) как злокачественный, то, используя свойство монотонности он может также заключить, что клинический случай (10110) должен быть злокачественным. Это заключение основано на систематическом кодировании всех признаков "подозрительных на рак" как 1. Заметим, что в (10100) мы имели два показания для рака: х3= 1 (протоковая ориентация, имеющая значение 1; подозрительна на рак) и Xi = 1 (количество и объем кальцинозов со значением 1; указание на рак). Во втором случае мы имеем два наблюдения за рак, а также х4 = 1 (сравнение с предыдущими экспертизами, подозрительными на рак). Аналогично, если мы знаем, что (01010) не. подозрительно на рак, то и случай (00000) нельзя также считать подозрительным. Это верно, потому что во втором случае мы имеем меньше признаков, указывающих на наличие рака. Вышеупомянутые соображения — существо того, на чем основаны наши алгоритмы.

Опишем метод восстановления монотонных Булевых функций с минимальной последовательностью вопросов для эксперта. Эта последовательность основана на фундаментальной лемме Hansel, Минимальная последовательность вопросов означает, что мы достигаем минимума функции Шеннона, то есть минимальное количество вопросов обязано восстанавливать самую сложную монотонную Булеву функцию с п аргументами. Эта последовательность не написана заранее. Она зависит от предыдущих ответов эксперта, поэтому каждый последующий вопрос определен динамически. Далее приводится таблица экспертного опроса, позволяющая восстановить функции. Эта таблица была заполнена по ответам эксперта-радиолога Джеймса Русса.

Из таблицы следует, что всего 13 вопросов необходимы для восстановления каждой из функций f\ и f2 как функций отхь х2, х3, х4, х5, и 12 вопросов необходимы для восстановления как функций от у и у2, уз, у4, ys. Фактическое количество вопросов, которые были заданы около 40, включая и связанные функции (рак и биопсию), т.е. приблизительно 20 вопросов на функцию.

Приводятся результаты обнаружения диагностических правил на данных системой Discovery. Это исследование было выполнено с использованием расширенного набора признаков. Было добавлено два признака тип Le Gal и плотность паренхимы со следующими диагностическими классами: "злокачественный", "доброкачественный", "высокий риск злокачественного развития". Было обнаружено несколько десятков диагностических правил, которые были статистически значительны при уровнях F-критерия 0.01, 0.05, 0.1.

Правила были извлечены на данных, содержащих 156 случая (73 злокачественный, 77 доброкачественный, 2 очень подозрительны и 4 со смешанным диагнозом). В скользящем контроле наши правила диагностировали 134 случая и отказались диагностировать 22 случая. Общая точность диагноза - 86 %. Неправильные диагнозы были получены в 19 случаях, ошибка первого рода была равна 5.2 %, ошибка второго рода была 8.9 %. Некоторые из правил показаны в таблице 2. Эта таблица дает примеры обнаруженных правил вместе с их статистическими оценками.

Таблица 7. Примеры обнаруженных диагностических правил_

Диагностическое правило F-критерий Значение F- Точно-

критерия сть на

0.01 0.05 0.1 конт-

роле

[F NUMber of calcifications per cm2 is NUM 0.0029 + + +

between 10 and 20 AND VOLume > 5 VOL 0.0040 + + + 93.3%

cm3 THEN Malignant

IF TOTal # of calcifications >30 TOT 0.0229 - + +

AND VOLume > 5 cm3 AND DENSITY VOL 0.0124 - + + 100.0%

of calcifications is moderate DEN 0.0325 - + +

THEN Malignant

IF VARiation in shape of calcifications VAR 0.0044 + + +

is marked AND NUMber of calcifica- NUM 0.0039 + . + + 100.0%

tions is between 10 and 20 AND IR- IRR 0.0254 - + +

Regularity in shape of calcifications is

moderate THEN Malignant

IF variation in SIZE of calcifications is SIZE 0.0150 - + +

moderate AND Variation in SHAPE of SHAP 0.0114 - ■ + 92.86%

calcifications is mild AND IRRegularity E 0.0878 - - +

in shape of calcifications is mild IRR

THEN Benign

Была рассмотрена зависимость результатов от выбора уровня условной вероятности. Мы рассмотрели три уровня 0.7, 0.85 и 0.95. Более высокий уровень условной вероятности уменьшал количество правил и диагностированных пациентов, но увеличивал точность диагноза. Их результаты обозначим как ММБШ, ММГЖ2 и ММОЯЗ. Нами было обнаружено 44 статистически значимых диагностических правила при 0.05 уровне Р - критерия с условной вероятностью не меньше, чем 0.75 (ММОШ). Было обнаружено 30 правил с условной вероятностью не меньшей, чем 0.85 (ММОЯ2) и 18 правил с условной вероятностью не меньшей, чем 0.95 (ММОЯЗ). Самые надежные 30 правил дали точность 90%; 18 самых надежных правил, выполненных с точностью 96.6 %, дали только 3 ошибки второго рода.

Нейронная сеть ("Вгаттакег") дала 100% точность на обучении, но на скользящем контроле точность упала до 66 %. Слабые результаты - 76 % на контрольных обучающихся данных - были получены линейным дискрими-нантным анализом (программное обеспечение "БЮАМО"). Решающие деревья (программное обеспечение "Б1РША") дал точность 76%-82% на обучении. Этот результат хуже, чем результат метода ММЭЯ с намного более трудным испытанием скользящим контролем.

Приводятся правила, извлеченные из эксперта. Они получены путем разложения найденных Булевых функций.

Описывается процедура получения монотонной Булевой функции по таблице ответов эксперта. Получены функции для подпроблем биопсии и рака:

Г)(х) = х2х3у хгх^х^ч^х^^зухзхдухзухгхзух^ух},

Г2(Х) = Х2Хз\'Х]Х2Х4\/Х1Х2>^Х1ХзХ4\''Х1Хз\ОСзХ4УХэУХ2Х5\/Х1Х5\/Х4Х5.

Упрощение этой дизъюнктивной нормальной формы позволило нам исключить некоторые избыточные конъюнкции. Для второго уровня иерархии по ответам эксперта были построены функции:

XI = = \V2VW1W3 ,

х2 = У(УьУ2,Уз,У4,У5) = У1 ^У2^УзУ4У5-

Объединяя, получим функции, включающие все 11 признаков для подпроблем биопсии и рака:

fl(x)=(УгVУlVyзУ4У5)X4V(W2VWlWз)(У2VyIVyзУ4У5)v(W2VWlWз)X4VXзVX5

£(х) = Х)Х2\'Хз У(Х2\^Х 14^X4^X5 =

(^V2VW1WЗ)(У1VУ2VУЗУ4У5)VXЗV(У1VУ2VУЗУ4У5)V(W2VW1WЗVX4)X5

Используя эти формулы, было извлечено 16 правил для диагностического класса "подозрительный на злокачественное развитие" и 13 правил для класса "биопсия".

Приведено сравнение экспертных и извлеченных системой Discovery правил. Приведем комментарии эксперта относительно правил извлеченных системой Discovery:

ЕСЛИ общее количество калышнозов > 30 И объем > 5 см3,

И плотность кальпинозов умеренна,

ТО - Злокачественная.

F-критерий значим при уровне 0.05, точность диагноза на контроле - 100 %.

Комментарий радиолога: «Это правило обещающее, но я считаю это рискованным».

ЕСЛИ изменение в форме кальпинозов отмечено И количество кальпинозов - между 10 и 20 И неисправность в форме кальпинозов умеренна

ТО - Злокачественная.

F-критерий значим при уровне 0.05, точность диагноза на контроле - 100 %.

Комментарий радиолога: «Я доверял бы этому правилу».

ЕСЛИ изменение в размере кальпинозов умеренно И изменение в форме кальпинозов умеренно И неисправность в форме кальпинозов умеренна

ТО — доброкачественная.

F-критерий значим с уровнем 0.05, точность диагноза на контроле - 92.86 %.

Комментарий радиолога: «Я доверял бы этому правилу».

Обсуждаются результаты применения реляционного подхода к задаче диагностики рака груди. Исследование продемонстрировало, что можно извлечь из данных и эксперта совместное множество знаний для медицинской диагностической системы рака груди. Согласованная база знаний лишена противоречий между правилами, полученными системой Discovery, правилами, используемыми опытным радиологом, и базой данных патологически подтвержденных случаев.

В шестой главе приводятся приложения реляционного подхода в биоинформатике.

Рассматривается одна из сложнейших и нерешенных задач - задача анализа регуляторных районов ДНК. Задача состоит в обнаружении законов в контекстных характеристиках последовательностей ДНК, вовлеченных в регуляцию транскрипции. Цель — найти законы, устанавливающие взаимосвязь между нук-леотидными последовательностями и функциональным классом этих последовательностей.

Поиск законов выполнен осуществлялся системой Gene Discovery, являющей-

ся адаптацией системы Discovery к задачам анализа генетических последовательностей. Для построения моделей регуляторных районов использовались различные отношения и операции. Например, алгоритм использует:

(1) положение олигонуклеотидов относительно начала транскрипции;

(2) взаимное расположение олигонуклеотидов в модели;

(3) ориентацию олигонуклеотидов в двойной спирали ДНК.

Описывается система Gene Discovery как технология извлечения знаний из

ДНК.

Определяются комплексные сигналы как олигонуклеотидные паттерны, обнаруживаемые системой Gene Discovery. Комплексным сигналом называется группа олигонуклеотидных мотивов, дающих определенную модель относительного взаиморасположения в последовательностях промотора. Присутствие такого комплексного сигнала можно рассматривать как условие принадлежности-последовательности к классу промоторов. Например, мы считаем группу двух олигонуклеотидных мотивов (Si,S2) комплексным сигналом, определенным следующим образом:

(Si, S2) = (Позиция (Si) < Позиция (S2) ), где Si и S2 - олигонуклеотиды; Позиция (Si), Позиция (S2) — позиции олигонуклеотидов в последовательности относительно старта транскрипции. Таким образом, мы можем считать условие А) в закономерности как комплексный сигнал (Si,S2), и проверять гипотезу Ai => Ао на последовательности ДНК, содержащей S| и S2.

Более сложные комплексные сигналы и соответствующие правила прогноза получаются добавлением новых сигналов в условие правила

(Si,... S¡.|,S¡) = (Позиция^,) <... < Позиция^,.,) < Позиция^;)), ¡=1,2,....

Система "Gene Discovery" перебирает все варианты возможного удлинения правила (Si,... S¡.i,S¡) олигонуклеотидом S¡, чтобы усилить прогноз, i = 1,...N, N - число мотивов.

Обсуждается подготовка данных и предварительный отбор сигналов. Обучающая выборка, подающаяся на вход системе Gene Discovery, состоит из последовательностей промотеров, специфичных для рассматриваемой функциональной системы (класс 1) и случайных последовательностей (класс 2).

Мы продемонстрируем возможности подхода в решении двух задач:

(1)анализа и распознавания промоторов, используя олигонуклеотиды как сигналы;

(2) анализа и распознавания донорных сайтов связывания, используя отдельные нуклеотиды как сигналы.

Мы проанализировали последовательности промоторов эндокринной систе-

мы. Выборка содержала 40 последовательностей длиной по 120 Ьр (от-100 Ьр до +20 Ьр относительно старта транскрипции). Программа АРГО была использована для выбора олигонуклеотидов длины 8 Ьр в 15-буквенном коде IUP АС для нуклеотидов.

Анализируются найденные системой Gene Discoveiy комплексные сигналы. Следующие дополнительные условия использовались для отбора и интерпретации комплексных сигналов: (1) олигонуклеотиды в комплексном сигнале не перекрываются в последовательностях промоторов; (2) наблюдаемое число N промоторов, обладающих комплексным сигналом больше, чем ожидаемое число N*,N>N*.

Примеры обнаруженных комплексных контекстных сигналов для промоторов эндокринной системы представлены в Таблица б. Рассмотрим сигнал №3 CWGNRGCN < NGSYMTAM < MAGKSHCN. Ожидаемое случайное число N* для этого сигнала - 0.47 (то есть меньше 1). Но сигнал присутствует в 6 промоторах, что приблизительно в 13 раз больше чем ожидаемое число. Таблица 6. Комплексные сигналы в промотерах эндокринной системы._

№ Услов- Значе- Число про- Ожида-

Комплексные сигналы ная ние моторов, емое чис-

(закономерности)1 веро- кри- включаю- ло промо-

ят- терия щих сигнал торов

ность Фишера

1 CWGNRGCN<NGSYMTAM<CAGGRNCH 0.875 0.00054 4 0.24 (<1)

2 KGRSSAGR<CYCYNSCY<CWGSNYCH 1.0 0.00012 4 0.28 (<1)

3 CWGNRGCN<NGSYMTAM<MAGKSHCN 1.0 0.00009 6 0.47 (<1)

4 CWGNRGCN<NGSYMTAM<CMDGGNCH 0.846 0.00099 5 0.43 (<1)

5 CNKSAGNT<NCARGRNC<HNNKGCTG 1.0 0.01426 4 0.37 (<1)

6 RNWGGCCN<DGRGNRGG<TCMAGNMN 0.875 0.00118 4 0.4 (<1)

7 RGSNRGRG<NNGSTWTA<CNCNRKGC 1.0 0.02852 5 0.53 (<1)

8 NNGSTWTA<NMAGDGMC<CNCNRKGC 0.875 0.04755 5 0.53 (<1)

9 RGSNRGRG<NNGSTWTA< CMDGGNCH 1.0 0.03964 5 0.55 (<1)

10 RGSNRGRG < KGGNSAGD <ANCTSMNG 1.0 0.03964 4 0.45 (<1)

45 RGSNRGRG<NGSYMTAM<CNCNRKGC 1.0 0.03964 5 0.58 (<1)

Система Gene Discovery была применена также для анализа донорных сайтов связывания генов приматов. Отдельные нуклеотидные основания использовались как сигналы в последовательности. Выборка содержала 2343 участков, каждый из которых содержал позиции от -11 до +10 относительно объединения

интрона и экзона.-

Таблица 7 содержит примеры найденных сигналов. Комплексные сигналы представлены как подпоследовательности нуклеотидов. Знак < обозначает отношение между позициями соответствующих нуклеотидов.

Описывается процедура распознавания на основе комплексных сигналов. На первом шаге процедуры распознавания мы находим все комплексные сигналы, применимые к некоторой контрольной последовательности.

Таблица 7. Примеры комплексных сигналов для донорных сайтов сплайсинга

№ Комплексный сиг- Длина комп- Значение крите- Число участков,

нал (закономер- лексного рия Фишера содержащих сиг-

ность) сигнала нал

1 а<Ь 2 7.221685е-003 6011

2 а<д 2 4.549541е-002 7469

3 t<c<c<c<a 5 2.242927е-002 2467

4 с<а<с<а<ь<ь 6 1.886203е-002 770

5 с<с<а<с<а<а 6 2.004277е-002 726

6 Ь<с<с<а<с<а 6 1.602915е-002 902

7 д<с<с<а<с<а 6 1.644068е-002 880

8 д<с<а<с<а<д 6 2.211978е-002 696

9 а<с<а<с<а<1;^ 7 2.358411е-002 304

1918 с<д<с<а<с<а<а 7 2.196624е-002 331

Тогда может быть вычислена оценка Р(Б) последовательности как принадлежащая классу промоторов. Оценка последовательности может быть определена несколькими способами:

(1) T.log Р(Б), сумма логарифмов условных вероятностей комплексных сигналов, найденных в последовательности;

(2) сумма логарифмов вероятностей олигонуклеотидных сигналов, найденных в последовательности.

Базируясь на этих оценках последовательностей, мы разработали метод прогнозирования донорных сайтов связывания. Полученные ошибки первого и второго рода на контрольных данных были 4,4 % и 4,0 %, соответственно.

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

В диссертационной работе получены следующие основные результаты: 1. Получена серия результатов, позволяющая осуществлять процесс познания в соответствии с Теорией измерений: а) Разработана методика перевода данных в многосортные эмпирические

системы;

b) Разработан метод и система Discovery обнаружения систем аксиом на данных;

c) Доказана возможность обнаружения аксиом в условиях некоторого вида шумов;

d) На примере физической структуры ранга (2,2) доказано соответствие между теорией измерений и теорией физических структур

2. Получена серия результатов, позволяющая осуществлять логический процесс познания:

a) Дано определение закона, вероятностного закона и максимально специфического правила, позволяющие обнаруживать, соответственно, истинные, вероятностные и максимально специфические для предсказания высказывания;

b) Решена проблема статистической двусмысленности и непротиворечивости предсказания;

c) Разработан семантический вероятностный вывод, выводящий перечисленные выше высказывания и аппроксимирующий дедуктивный вывод;

Основные результаты диссертации опубликованы в работах:

1. Витяев Е.Е. Алгоритм эмпирического предсказания // Выч. сист., 61, Новосибирск, 1975, с. 28-36.

2. Витяев Е.Е. Метод обнаружения закономерностей и метод предсказания // Эмпирическое предсказание и распознавание образов (Выч. сист., 67), Новосибирск, 1976, с. 54-68.

3. Витяев Е.Е. Закономерности в языках эмпирических систем и законы классической физики // Эмпирическое предсказание и распознавание образов (Выч. сист., 79), Новосибирск, 1979, с. 45-56.

4. Витяев Е.Е. Обнаружение закономерностей, выраженных универсальными формулами // Эмпирическое предсказание и распознавание образов (Выч. сист., 79), Новосибирск, 1979, с. 57-59.

5. Витяев Е.Е. Числовое алгебраическое, и конструктивное представление одной физической структуры // Логиго-математические основы МОЗ (Выч. сист., 107), Новосибирск, 1985, с.40-51.

6. Витяев Е.Е., Москвитин A.A. Лада - программная система логического анализа данных // Методы анализа данных (Выч. сист. 111), Новосибирск, 1985, с.38-58.

7. Витяев Е.Е. Конструктивное числовое представление величин // Методы анализа данных (Выч. сист., 111), Новосибирск, 1985, с.23-32.

8. Витяев Е.Е., Подколодный Н.Л. От экспертных систем к системам, создающим теории предметных областей // Компьютерный анализ структуры, функ-

ции и эволюции генетических макромолекул, Новосибирск, 1989, с.264-282. 9. Витяев Е.Е. Логико-операциональный подход к анализу данных // Комплексный подход к анализу данных в социологии. Труды Института Социологических исследований АН, Москва, 1989, с. 113-122. 10.Обнаружение закономерностей (методология, метод, программная система SINTEZ). 1. Методология // Методологические проблемы науки (Выч. сист., 138), Новосибирск, 1991, с. 26-60

11.Витяев Е.Е. Семантический подход к созданию баз знаний. Семантический вероятностный вывод наилучших для предсказания Пролог-программ по вероятностной модели данных. // Логика и семантическое программирование (Выч. сист., 146), Новосибирск, 1992, с.19-49.

12.Витяев Е.Е., Москвитин А.А. Введение в теорию открытий. Программная система Discovery. // Логические методы в информатике (Выч. сист., 148), Новосибирск, 1993, с.117-163.

13.Витяев Е.Е., Логвиненко А.Д. Метод тестирования систем аксиом. // Теория вычислений и языки спецификаций. (Выч. сист. 152), Новосибирск, 1994, с.119-139.

14.Kovalerchuk, В., Triantaphyllou, Е., Vityaev, Е., Monotone.Boolean Function Learning Technique Integrated with User Interaction. Proc. of 12th International Conf. on Machine Learning, Workshop "Learning from Examples", Tahoe City, USA, 1995, pp. 41-48.

15.B.Kovalerchuk, E.Vityaev, James F.Ruiz Design of consistent system for radiologists to support breast cancer diagnosis. Joint Conference of Information Sciences, v.2, Elsevier Publishing Company, 1997, pp. 118-121.

16.Kovalerchuk, В., Vityaev E. Discovering Lawlike Regularities in Financial Time Series, Journal of Computational Intelligence in Finance, v.6, No.3, 1998 pp.12-26.

17.Витяев E.E., Логвиненко А.Д. Обнаружение законов на эмпирических системах и тестирование систем аксиом теории измерений. Социология: методология, методы, математические модели № 10, Научный журнал РАН, 1998, стр. 97-121.

18.В. Kovalerchuk, Е. Vityaev, J. Ruiz. Consistent knowledge discovery in medical diagnosis. IEEE Engineering in Medicine and Biology Magazine, July/August 2000, pp.26-37.

IMiovalerchuk В., Vityaev E. Data Mining in Finance: Advances in Relational and -—"Hybrid methods. Kluwer Academic Publishers, 2000, p.308.

20.Kovalerchuk, В., Vityaev E., Ruiz J.F., Consistent and Complete Data and "Expert" Mining in Medicine, In: Medical Data Mining and Knowledge Discovery, Springer, 2001, pp. 238-280.

итяев Е.Е., Орлов Ю.Л., Вишневский О.В., Беленок А.С., Колчанов Н.А. Компьютерная система "Gene Discovery" поиска закономерностей организации регуляторных последовательностей эукариот. Молекулярная биология, 2001,

т^, №6,952-961. ----

(^¿¿¡¿Вишневский О.В., Витяев Е.Е. Анализ и распознавание промоторов эритро-ид-специфичных генов на основе наборов вырожденных олигонуклеотидных последовательностей. Молекулярная биология, 2001, т.35, №6,979-986. /(¿4|Д"1оздняков М.А., Витяев Е.Е., Ананько Е.А., Игнатьева Е.В., Подколодная О.А., Подколодный Н.Л., Лаврюшев С.В., Колчанов Н.А. Сравнительный анализ методов распознавания потенциальных сайтов связывания транскрипционных сайтов связывания. Мол. Биол., 2001, т.35, №6, 961-969.

25.Evgenii Е. Vityaev, Yury L. Orlov, Oleg V. Vishnevsky, Mikhail A. Pozdnyakov, Nikolay A. Kolchanov. Computer system "Gene Discovery" for promoter structure analysis, In Silico Biol. 2 (2002) 257-262.

26.Vityaev E.E., OrlovYu.L., Vishnevsky O.V., Kovalerchuk B.Ya., Belenok A.S., Podkolodnii N.L., Kolchanov N.A. Knowledge Discovery for Gene Regulatory Regions Analysis, In: KES'2002. Eds. E.Damiani, R. Howlett, L.Jain, N. Ichalkaranje, IOS Press, Amsterdam, 2002, part 1, pp. 487-491.

27. Vityaev E.E., Orlov Yu.L., Pozdnyakov M.A., Vishnevsky O.V., Kolchanov N.A., Kovalerchuk B.K. Knowledge Discovery for Promoter Structure Analysis In: Proceedings of the International Conference on Imaging Science, Systems, and Technology Eds.: Hamid R. Arabnia, Las Vegas, USA, June 24-27, 2002, CSREA Press, v.l, 122-128

28.Vityaev E.E., Pozdnyakov M.A., Orlov Yu.L., Vishnevsky O.L., Podkolodny N.L., Kolchanov N.A. Gene Discovery Computer system for Analysis of Regulatory Regions // BGRS'2002, Novosibirsk, Russia, July 14-20, 2002, v3, ICG, Novosibirsk, 2002, pp. 257-259.

29.Nikolay A. Kolchanov, Mikhail A. Pozdnyakov, Yury L. Orlov, Oleg V. Vishnevsky, Nikolay L. Podkolodny, Eugenii E. Vityaev and Boris Kovalerchuk Computer System "Gene Discovery" for Promoter Structure Analysis In: Artificial Intelligence and Heuristic Methods in Bioinformatics, Eds: P. Frasconi and R. Shamir, IOS Press, 2003, pp.173-192.

30.Витяев E. E., Харламов E. Ю., Формализация понятия, предсказания // Вероятностные идеи в науке и философии, Новосибирск, 2003, стр. 79-82

31.Vityaev Е., Demenkov P., Empirical Theory Discovery, Probabilistic ideas in science and philosophy, Novosibirsk, 2003, pp.86-89.

32.Kovalerchuk, В., Vityaev, E., Detecting patterns of fraudulent behavior in forensic accounting, In: Proc. of the Seventh International Conference "Knowledge-based Intelligent Information and Engineering on Systems", Oxford, UK, Sept, 2003, part 1, pp. 502-509.

33. A. D. Logvinenko, W. Byth, E. E. Vityaev. In search of an elusive hard threshold: a test of observer's ability to order sub-threshold stimuli. Vision Research, v.44:3,

287-296,2004.

34.Boris Kovalerchuk, Evgenii Vityaev. Data mining in finance: From extremes to realism. Journal of Financial Transformation, vol 11 - August 2004, p. 81-89.

35.Evgenii Vityaev, Boris Kovalerchuk, Empirical Theories Discovery based on the Measurement Theory. Mind and Machine, v.14, #4, 551-573,2004

36.Evgenii Vityaev, Boris Kovalerchuk. Visual data mining with simultaneous rescaling. In: Visual and Spatial Analysis. Advances in Data Mining, Reasoning and Problem Solving. Springer 2004, pp. 371-385.

37.Evgenii Vityaev, Boris Kovalerchuk. Data Mining For Financial Applications. In: O. Maimon and L. Rokach (eds.), Data Mining and Knowledge Discovery Handbook: A Complete Guide for Practitioners and Researchers, Springer 2005, pp. 1203-1224.

38. Vityaev E. Probability and logic synthesis in the notion of prediction // The 9th Asian Logic Conference, Abstracts, NSU, Sobolev Institute of mathematics, 2005, 134-135.

39.Vityaev Evgenii, On the classification of all possible fundamental laws // 36th EMPG Europian Mathematical Psychology Group Meeting, program and abstracts, University of Padua, September 5-7,2005, pp72-73

40.E.Vityaev, B. Kovalerchuk, Relational Methodology for Data Mining and Knowledge Discovery II Sixteenth International Workshop on Database and Expert Systems Applications, 1st International Workshop on Philosophies and Methodologies for Knowledge discovery (22-26 Audust 2005, Copenhagen, Denmark), IEEE Computer Society, 2005, pp.725-729

41.E.E. Vityaev, T.I. Shipilov, M.A. Pozdnyakov, O.V. Vishnevsky, A.L., Proscura, Yu.L. Orlov, P. Arrigo Software for analysis of gene regulatory sequences by knowledge discovery methods. In: Bioinformatics of Genome Regulation and Structure II. (Eds. N.Kolchanov and R. Hofestaedt) Springer Science+Business Media, Inc. 2006, pp. 491-498.

42.Scientific Discovery website: http:/Avww.math.nsc.ru/AP/Sc)'entiflcDiscovery

Подписано в печать 08.11.2006. Формат 60x80 1/16. Усл. печ. л. 2.5. Уч.-изд. л. 2.5. Тираж 100 экз. Заказ № 121 Отпечатано в ООО «Омега Принт» пр. Лаврентьева, 6, 630090 Новосибирск

ВВЕДЕНИЕ

§1. Методология познания, вытекающая из Теории Измерений

§2. Процесс познания, основанный на Теории Измерений

§3. Логический путь познания предметной области

§4. Проблемы извлечения знаний и теорий

§5. Реляционный подход к извлечению знаний - реализация логического пути познания

§6. Применения реляционного подхода к извлечению знаний из данных в финансовом прогнозировании, медицине и биоинформатике

ГЛАВА 1. ЛОГИЧЕСКИЙ АНАЛИЗ ДАННЫХ И ЗАКОНОВ

§7. Основные понятия и проблемы теории измерений

§8. Эмпирические аксиоматические теории и Теория Измерений

§9. Представление известных типов данных в эмпирических аксиоматических теориях

§10. Критический анализ методов анализа данных

§11. Представление законов в Теории Измерений

§12. Теория Физических Структур

§13. Соотношение между физической структурой ранга (2,2) и аддитивной соединительной структурой

§14. Алгебраическое и конструктивное представления физической структуры ранга (2,2)

§15. Конструктивные числовые представления величии

§16. Взаимосвязь конструктивного и числового представлений

§17. Примеры конструктивных представлений величин

§18. Конструктивное числовое представление процедур шкалирования для экстенсивных величин

ГЛАВА 2. ПРОЦЕСС ПОЗНАНИЯ, ОСНОВАННЫЙ НА ТЕОРИИ ИЗМЕРЕНИЙ

§19. Универсальная аксиоматизируемость экспериментальной зависимости

§20. Общая формулировка метода обнаружения экспериментальной зависимости

§21. Что такое закон

§22. Понятие эксперимента. Определение закона на множестве всех возможных экспериментов

§23. События и вероятности событий

§24. Определение вероятностного закона на ТЧп ■ I щщ ~1

ГОСУДАРГ

Г ^ИБЛ

Ч АЧЗоХ'оЦ.

§25. Обобщение понятия вероятностного закона и эксперимента на случай данных с шумами

§26. Тестирование систем аксиом в условиях шумов

§27. Сохраняющий двоичный шум

ГЛАВА 3. ЛОГИЧЕСКИЙ ПУТЬ ПОЗНАНИЯ. ПРОБЛЕМА ПРЕДСКАЗАНИЯ

§28. Знание и познание

§29. Индуктивно-статистический вывод

§30. Семантический вероятностный вывод множеств законов L и LP

§31. Требование максимальной специфичности

§32. Решение проблемы статистической двусмысленности

ГЛАВА 4. РЕЛЯЦИОННЫЙ ПОДХОД К ИЗВЛЕЧЕНИЮ ЗНАНИЙ ИЗ ДАННЫХ

§1. Методология познания, вытекающая из Теории Измерений

В настоящее время интенсивно развивается направление Knowledge Discovery in Databases and Data Mining (KDD&DM), основанное на методах Machine Learning, Artificial Intelligence и Data Analysis. Давно назрела потребность проанализировать эти методы с точки зрения их связи с процессом познания. В результате анализа мы естественным образом придем к Компьютерному Познанию, основанному на Теории Измерений.

1. Аппроксимационный подход к решению задач анализа данных. В методах Machine Learning неизвестная зависимость аппроксимируется некоторым заданным априори классом функций, моделями, решающими правилами и т.д. В нейронных сетях это кусочно-линейные правила, в деревьях это логические решающие функции, в регрессионном анализе это линейная или нелинейная регрессия, в дискриминантном анализе - дискриминантная функция, в распознавании образов - решающее правило, методах классификации - форма кластеров. Какова в некотором смысле "истинная" зависимость - такой вопрос не ставится, и не может быть поставлен. Аппроксимируя неизвестную зависимость с требуемой степенью точности и надежности, методы Machine Learning решают, по существу, задачу предсказания. Найденная аппроксимация практически ничего не говорит об "истинной" зависимости.

Процесс аппроксимации начинается с переноса способов измерения из точных наук в другие области. Рассмотрим, например, такую физическую величину как температура. Шкалы температуры в нефизических областях, например, при измерении температуры тела больного в медицине, температуры почвы в сельском хозяйстве, температуры воздуха в духовке в кулинарии и т.д., должны быть разные, хотя измеряться они могут одним и тем же прибором - термометром. Далеко не всеми понимается тот факт, что шкала это не только риски делений на приборе, а это набор операций и отношений, которые имеет смысл производить с числовыми значениями величин с точки зрения рассматриваемой предметной области (точнее это те операции и отношения, которые интерпретируемы в системе понятий соответствующей предметной области). Можно возразить, что термометр не может измерять ничего кроме температуры. Он действительно во всех случаях измеряет физическую температуру. Но резонно спросить, а зачем, собственно, мы измеряем температуру'' Ведь не затем, чтобы согласно законам физики узнать, сколько в больном содержится тепла и сколько он в состоянии растопить льда, если его положить на лед, и не затем, чтобы определить среднюю кинетическую энергию молекул почвы или курицы в духовке Температура как и любой другой прибор нужны для получения выводов в системе понятий той предметной области, к которой он относится Для больного "Температурный фактор служит наиболее общим и универсальным регулятором скорости химических реакций и активности ферментов, с повышением температуры в известной мере ускоряются и обменные процессы" Для почв температура должна интерпретироваться в системе понятий физиологии растений и деятельности микроорганизмов и т д Следует понимать, что физическая величина температуры является косвенным измерением некоторой другой величины, интерпретируемой в системе понятий предметной области, которую мы именно и хотим измерить Физическая температура больного, например, есть косвенное измерение медицинской величины -уровня обмена веществ, температура почвы измеряет состояние биохимических процессов в растениях и микроорганизмах, температура воздуха в духовке измеряет течение процесса свертывания белка и т.д. Какие отношения и операции над числовыми значениями температуры имеют смысл для всех этих величин определяется уже этими интерпретациями Поэтому числовые значения величин нельзя автоматически переносить из одной области знаний в другую. После такого переноса необходимо заново определять шкалу Например, для температуры больного интерпретируемы выделенные значения 36 7, 42 и отношение линейного порядка <, поэтому это будет шкала порядка с выделенными значениями

Применение методов Machine Learning также является аппроксимационным. Перед обработкой данные, как правило, преобразуются к одному из известных видов - количественным или качественным. Если они преобразуются к количественным данным (т.е. с числами разрешается производить любые математические операции вне зависимости от их интерпретации), то в них вносится бессмысленная информация (проявляющаяся в том, что невозможно обоснованно проинтерпретировать полученные результаты). Если данные преобразуются в количественные за счет использования различного рода (числовых) моделей или дополнительных предположений, которые не полностью интерпретируемы, то это также приводит к невозможности обоснованно проинтерпретировать полученные результаты. Если данные преобразуются в дискретные, то это ведет к потере информации. Поэтому неизвестные зависимости не просто аппроксимируются задаваемыми видами зависимостей, но и сами данные часто искажаются, чтобы их обработка этими методами была возможна.

2. Построение «истинных» величин законов и моделей. Для того чтобы детальнее разобраться с такими понятиями как числовые значения величин, их интерпретируемость, осмысленность математических операций с величинами, "истинная" зависимость и т.д. необходимо обратиться к Теории Измерений [50-51, 143]. Теория Измерений основана на принципе: свойства определяются отношениями. Из теории измерений следует, что числовые значения величин и функциональные выражения для законов являются лишь удобным и математически хорошо разработанным способом числового кодирования элементов эмпирических систем. Число, например, 5 само по себе смысла не имеет, оно приобретает смысл лишь при его интерпретации в некоторой эмпирической системе, например, если мы говорим 5 метров, 5 баллов, 5 деталей и т.д. Интерпретация чисел, в частности, определяет какие математические действия с ними можно осмысленно проводить чтобы не получать бессмысленных результатов типа 1.5 дровосека, 1 м + 1 кг, и т.д. Эмпирическая система - это множество (идеализированных) объектов с заданными на нем множеством интерпретируемых в системе понятий отношений и операций, удовлетворяющих некоторой системе аксиом. Такой семантический уровень рассмотрения с необходимостью возникает из того факта, что интерпретировать человек может только качественно. Поэтому, интерпретируя количественные значения величин, модели, функции и т д. он интерпретирует их качественно - в системе понятий предметной области - и в качестве промежуточной стадии такой интерпретации - на семантическом уровне в (многосортной) эмпирической системе Семантический уровень возникает не только из-за требования интерпретируемости, но он и исторически является первичным и представляет собой целостное (модельное) представление той исходной операциональной деятельности над объектами, которая привела в свое время к возникновению чисел

В отличии от аппроксимационного подхода в Теории Измерений определяются в некотором смысле "истинные" величины и зависимости Числовые представления величин, получаемые в Теории Измерений, "истинны" в том смысле, что они интерпретируемы в системе понятий предметной области и являются лишь числовыми кодами значений величины соответствующей эмпирической системы Числовые представления законов в Теории Измерений являются "истинными" в том смысле, что они, во-первых, интерпретируемы в системе понятий данной предметной области и являются лишь числовыми кодами взаимосвязи величин эмпирической системы и, во-вторых, получаются одновременно с числовыми представлениями величин (единой процедурой шкалирования (см §11-§14) В [143] показано, что физические законы просты только потому, что они являются результатом одновременного шкалирования всех, входящих в зависимость величин, так чтобы взаимосвязь этих величин выражалась заданной (определяемой системой аксиом) простой функциональной зависимостью

Следующий вывод, который следует из Теории Измерений, состоит в том, что цель обнаружения «истинных» величин и законов совсем другая - познать предметную область Для достижения этой цели интерпретируемость данных и результатов обработки данных в системе понятий предметной области является необходимым условием получения полезного результата, вносящего вклад в теорию предметной области. Так как числа сами по себе смысла не имеют, то интерпретируемость данных и результатов счета означает их интерпретируемость на семантическом уровне в системе понятий предметной области без использования чисел. Поэтому для целей познания предметной области необходим способ представления данных, принятый в Теории Измерений - в виде (многосортных) эмпирических систем. Системы аксиом, которым удовлетворяют эти эмпирические системы, представляют собой логическую эмпирическую теорию предметной области. Системы аксиом как логические высказывания, очевидно, интерпретируемы в системе понятий предметной области. Поэтому обнаружение законов должно состоять в обнаружении систем аксиом в языке первого порядка на данных представленных (многосортными) эмпирическими системами. Таким образом, задача познания предметной области сводится к задаче усиления (в логическом смысле) логической эмпирической теории за счет обнаружения аксиом в логике первого порядка.

Числовые представления величин и функциональных зависимостей должны получаться из обнаруженных систем аксиом в результате применения Теории Измерений. Полученные шкалы величин и законы, связывающие величины, дают Количественную Теорию Предметной Области. Для физики этот переход продемонстрирован в [143]. Показано, как можно строить Количественную Теорию Предметной Области - систему величин, связанных между собой (фундаментальными) законами.

Таким образом, задача познания предметной области как она понимается в Теории Измерений разбивается на два этапа: сначала надо построить Логическую Эмпирическую Теорию, а затем, применяя Теорию Измерений, построить Количественную Теорию Предметной Области. Такое разбиение отражает естественный процесс перехода теории из качественного состояния, представленного онтологией и логической эмпирической теорией, в количественное. Теория Измерений и является теорией такого перехода. Для физики, например, этот процесс протекал достаточно долго. Процесс построения эмпирических теорий представлен на Рис. 1.

Выводы:

1) показано, что извлечение информации из данных путем определения отношений и операций позволяет обнаруживать достаточно интересные и сильные закономерности, позволяющие осуществлять эффективные предсказания. Полученные результаты показывают, что предсказание посредством найденных закономерностей, как правило, точнее предсказаний, сделанных другими методами;

2) онтологии, в настоящее время, включают в себя только систему понятий и априорные знания. Они не включают интерпретируемые отношения и операции, которые можно извлечь из данных и величин. Как показано в работе, в первом случае анализ величин и обнаружение законов в том смысле, как это понимается в теории измерений, невозможен. Поэтому онтологии должны включать в систему понятий множества интерпретируемых отношений и операций, которые определяют смысл и содержание величин;

3) дедуктивная математическая логика не подходит для осуществления предсказаний.

Как показано в работе, для получения высоковероятных и непротиворечивых предсказаний требуется другой процесс вывода, основанный на семантическом вероятностном выводе. Этот вывод разработан в рамках новой парадигмы в логике -предсказания не выводятся, а вычисляются Разработанные в работе понятия закона, вероятностного закона, максимально специфического правила и семантического вероятностного вывода позволяют осуществлять вычисления максимально вероятных и непротиворечивых предсказаний,

4) для осуществления процесса познания нужна разработка принципиально новых методов по сравнению с теми, которые существуют в настоящее время Некоторые из них предложены в работе (извлечение отношений и операций, обнаружение систем аксиом в языке первого порядка), другие намечены (конструктивные числовые представления величин, обнаружение функциональных зависимостей с одновременным формированием величин),

5) достаточно полное извлечение знаний из данных невозможно без явного определения скрытой в них логико-алгебраической структуры, определяющей смысл и интерпретацию величин Закономерности, обнаруженные в экспериментах, показывают, что в данных есть информация, невыразимая другими методами

1. Препринт // Научный совет по комплексной проблеме «Кибернетика»), 80 с

2. Белоусов В Д. Алгебраические сети и квазигруппы Кишенев, 1971,165 с

3. Витяев Е Е Метод обнаружения закономерностей и метод предсказания // Эмпирическоепредсказание и распознавание образов (Выч сист,вып67) Новосибирск, 1976, с 54-68.

4. Витяев Е Е Закономерности в языке эмпирических систем // Эмпирическое предсказаниеи распознавание образов (Выч сист , вып 76) Новосибирск, 1978, с 3-14

5. Витяев Е.Е. Обнаружение закономерностей, выраженных универсальными формулами // Эмпирическое предсказание и распознавание образов (Выч. сист., вып. 79). Новосибирск, 1979, с. 57-59.

6. Витяев Е.Е. Закономерности в языках эмпирических систем и законы классической физики // Эмпирическое предсказание и распознавание образов (Выч. сист., вып. 79). Новосибирск, 1979, с. 45-56.

7. Витяев Е.Е. Обнаружение функциональных зависимостей с одновременным формированием понятий // Вторая всесоюзная конференция по автоматизации поискового конструирования. Новосибирск, 1980, с. 171-172.

8. Витяев Е.Е. Анализ данных с применением языка эмпирических систем // Дисс. канд. тех. наук. Новосибирск, 1982.

9. Витяев Е.Е. Упрощение функциональных зависимостей за счет перешкалирования величин // 11-я Всесоюзная школа-семинар по "Программно-алгоритмическому обеспечению прикладного многомерного статистического анализа". М., 1983, с.260-262.

10. Витяев Е.Е. Числовое алгебраическое, и конструктивное представление одной физической структуры // Логиго-математические основы МОЗ (Выч. сист., вып. 107). Новосибирск, 1985, с.40-51.

11. Витяев Е.Е. Конструктивное числовое представление величин // Методы анализа данных (Выч. сист., вып. 111). Новосибирск, 1985, с.23-32.

12. Витяев Е.Е. Шкала экстенсивных величин как абстрактный тип данных // Всесоюзная конференция по прикладной логике (Тезисы докладов). Новосибирск, 1985, с.37-39.

13. Витяев Е.Е. Логико-операциональный подход к анализу данных // Комплексный подход к анализу данных в социологии. Тр. Института Социологических исследований АН. Москва, 1989, с. 113-122.

14. Витяев Е.Е. Обнаружение закономерностей (методология, метод, программная система

15. SINTEZ). 1. Методология // Методологические проблемы науки (Выч сист, 138), Новосибирск, 1991,с 26-60

16. Витяев Е Е Семантический подход к созданию баз знаний Семантический вероятностный вывод наилучших для предсказания ПРОЛОГ-программ по вероятностной модели данных // Логика и семантическое программирование (Выч сист , вып 146) Новосибирск, 1992, с 19-49

17. Витяев Е Е , Логвиненко А Д Метод тестирования систем аксиом // Теория вычислений и языки спецификаций (Выч системы, 152) Новосибирск, 1995, с 119-139.

18. Витяев Е Е , Москвитин А А. ЛАДА программная система логического анализа данных // Методы анализа данных (Выч сист вып 111) Новосибирск, 1985, с 38-58

19. Витяев Е Е , Орлов Ю Л , Вишневский О В , Беленок А С , Колчанов Н А Компьютерная система "Gene Discovery" для поиска закономерностей организации регуляторных последовательностей эукариот Молекулярная биология, 2001, т 35, №6, 952-961

20. Витяев Е Е , Подколодный Н Л. От экспертных систем к системам, создающим теории предметных областей // Компьютерный анализ структуры , функции и эволюции генетических макромолекул Новосибирск, 1989, с 264-282

21. Вишневский О В, Витяев Е Е Анализ и распознавание промоторов эритроид-специфичных генов на основе наборов вырожденных олигонуклеотидных последовательностей Молекулярная биология, 2001, т 35, №6,979-986

22. Всесоюзная конференция «Нечисловая статистика, экспертные оценки и смежные вопросы» (Тезисы докладов) М-Таллин, 1984,403с.

23. Гихман И И., Скороход А В , Ядренко М И Теория вероятностей и математическая статистика "Вища школа", Киев, 1079, с 408

24. Данные в языках программирования Абстракция и типология М , Мир, 1982, с 327

25. ДевидГ Метод парных сравнений -М Статистика, 1978 150с

26. Дробыщев Ю.П. Задачи и методы анализа данных // Математические вопросы анализа данных/ Под ред. Ю.П. Дробышева, Новосибирск, 1980, с. 6-14.

27. Ершов ЮЛ. Проблемы разрешимости и конструктивные модели. М.: Наука, 1980.-415с.

28. Загоруйко Н.Г., Самохвалов К.Ф., Свириденко Д.И. Логика эмпирических исследований. Новосибирск, 1978. 66с.

29. Каменский B.C. Модели и методы не метрического многомерного шкалирования (Обзор) // Автоматика и телемеханика, 1977, #8, с. 118-156.

30. Карнап Р. Философские основания физики. М.: Прогресс, 1971. 387с.

31. Кендал М., Стьюарт А. Статистические выводы и связи. М., Наука, 1973, с.899.

32. Кини P.JL, РАЙФА X. Принятие решений при многих критериях: предпочтения и замещения. М. Радио и связь, 1981,560с.

33. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М., Наука, 1982. 182с.

34. Козелецкий Ю. Психологическая теория принятия решений. М., Прогресс, 1979. 503с.

35. Кузьмин В.Б., Орлов А.И. О средних величинах, сравнение которых инвариантно относительно допустимых преобразований шкалы // Статистические методы анализа экспертных оценок, М., 1977, с.220-227.

36. Кулаков Ю.И. Элементы теории физических структур. Новосибирск, 1968,215с. (НГУ);

37. Кулаков Ю.И. Математическая формулировка теории физических структур. Сиб. Мат. Ж. 1971,т.Х11, №5, с.1142-1145.

38. Кулаков Ю.И. О теории физических структур. В кн.: Краевые задачи математической физики и смежные вопросы теории функций. Т5. JL, 1983, с.103-151 (Зап. Сем. ЛОМИ, т. 127).

39. Кулаков Ю.И. Новая формулировка теории физических структур // Методологические и технологические проблемы информационно-логических систем (Выч. систю, вып. 125). Новосибирск, 1988, с.3-32.

40. Куперштох В.Л., Миркин Б Г., Трофимов В А., Метод наименьших квадратов в анализе качественных признаков // Проблемы анализа дискретной информации. Новосибирск, 1976.

41. Лбов Г С., Котюков В.И , Манохин А Н. Об одном алгоритме распознавания в пространстве разнотипных признаков//Выч сист вып 55, Новосибирск, 1973, с. 108-110

42. Лихорадка // Малая Медицинская Энциклопедия, М , 13. Психологические измерения Под ред Л ДМешалкина -М Мир, 1967 120с

43. Мальцев А И Алгебраические системы, М , Наука, 1970

44. Машинные методы обнаружения закономерностей (Материалы Всесоюзного симпозиума 5-7 апреля 1976г) // Под ред Н Г Загоруйко, В Н Елкиной Новосибирск, 1976 167с

45. Мейен С.В , Шрейдер С А Методологические аспекты теории классификаций. Вопросы философии, 1976, №12.

46. Миркин Б Г Анализ качественных признаков М. Статистика, 1976 166с

47. Миркин Анализ качественных признаков и структур М Статистика, 1980 -316с

48. Михайличенко Г.Г. Решение функциональных уравнений в теории физических структур ДАН, т 206, N5,1972, с.1056-1058

49. Михиенко Е В , Витяев Е Е Моделирование работы функциональной системы, VI Всероссийская научно-техническая конференция «Нейроинформатика-2004». Сборник научных трудов. В 2-х частях Ч 2 , М.: МИФИ, 2004, 124-129

50. Нормативные и дескриптивные модели принятия решений (По материалам советско-американского семинара. М., Наука, 1981 -340с

51. ПфанцагльИ Теория измерений М,Мир, 1976 -248с

52. Психологические измерения//Под ред Л ДМешалкина -М Мир, 1967 120с

53. Орлов А.И. Допустимые средние в некоторых задачах экспертных оценок и агрегирования показателей качества // Многомерный статистический анализ в социально-экономических исследованиях. М., Наука, 1979. 293с.

54. Орлов А.И. Устойчивость в социально-экономических моделях. М., Наука, 1977. 182с.

55. Саганенко Г.И. Социологическая информация. JI., Наука, 1979. 142с.

56. Сатаров Г.А., Каменский B.C. Общий подход к анализу экспертных оценок методами не метрического многомерного шкалирования // Статистические методы анализа экспертных оценок. М., Наука, 1977, с.251-266.

57. Терехина А.Ю. Методы многомерного шкалирования и визуализации данных (Обзор). -Автоматика и телемеханика, 1973, #7, с.80-94.

58. Тюрин Ю.Н. Непараметрические методы статистики. М., Знание, 1978. - 64с.

59. Тюрин Ю.Н., Василевич А.П., Андрукевич П.Ф. Статистические методы ранжирования // Статистические методы анализа экспертных оценок, М., Наука, 1977, с.30-58.

60. Тюрин Ю.Н., Литвак Б.Г., Орлов А.И., Сатаров Г.А., Шмерлинг Д.С. Анализ нечисловой информации (препринт). М., 1981. - 80с.

61. Тюрин Ю.Н., Литвак Б.Г., Орлов А.И., Сатаров Г.А., Шмерлинг Д.С. Анализ нечисловой информации // Всесоюзная школа "Программно-алгоритмическое обеспечение прикладного многомерного статистического анализа", Ереван, 1979, с.231-243.

62. Фишберн П.С. Теория полезности для принятия решений. М., Наука, 1978. 352с.

63. Шмерлинг Д.С. О построении моделей парных и множественных сравнений со связями // Прикладной многомерный статистический анализ, М., 1978, с.164-189.

64. Шрейдер С.А. Систематика, типологии, классификация. В кн.: Теория и методология биологических классификаций, М., Наука, 1983.

65. Abu-Mostafa Learning from hints in neural networks. Journal of complexity 6 192-198,1990.

66. Artificial Intelligence in the Capital Markets, Eds R. Freedman, R. Klein, J. Lederman, Probus Publishing, 1995

67. Er.W Adams, The logic of conditionals // An application of probability to deductive logic // Synthese Library, v.86, 1975.

68. Akeroyd, F. M A practical example of Grue The British journal for the philosophy of science, 1991,42-535-39.

69. Anderson N H. Integration theory, functional measurement and the psychological law // Advances in psychophysics // Ed Geissler, Yu Zabrodin, Berlin, 1976, p 93-130

70. Anderson N H Algebraic Rules in Psyhological measurement Amer. Scientist, 1979 , v 67, p 555-563

71. K R Apt, Introduction to logic programming // Computer Science Department of Software Technology, Report CS-R874

72. Bergadano, F , Giordana, A , & Ponsero, S (1989) Deduction in top-down inductive learning Proceedings of the Sixth International Workshop on Machine Learning (pp. 23-25) Ithaca, NY Morgan Kaufmann

73. V N Babenko et al, Investigating extended regulatory regions of genomic DNA sequences, Bio-mformatics 15 (1999) 644-653

74. Babenko, V N, Kosarev, P S., Vishnevsky, O V , Levitsky, V G , Basin, V V. and Frolov, A S (1999) Investigating extended regulatory regions of genomic DNA sequences Bioinformatics, 15, 644-653.

75. Baxevanis, A D (2001) The Molecular Biology Database Collection an updated compilation of biological database resources Nucleic Acids Research, 29,1-10

76. BI-RADS., Breast Imaging Reporting and Data System, American College of Radiology, Reston, VA, 1998

77. Bird,, R.E.,Wallace, T.W., Yankaskas, B.C. Analysis of cancer missed at screening mammography, Radiology, v. 184, pp. 613-617,1992.

78. Bratko, I., Muggleton, S., Varvsek, A. Learning qualitative models of dynamic systems. In Inductive Logic Programming, S. Muggleton, Ed. Academic Press, London, 1992.

79. Bratko, I. Innovative design as learning from examples. In Proceedings of the International Conference on Design to Manufacture in Modern Industries, Bled, Slovenia, June 1993.

80. Bratko I, Muggleton S (1995): Applications of inductive logic programming. Communications of ACM 38 (11):65-70.

81. Breast Imaging Reporting and Data System, ACR, Reston, VA, 1998

82. Burhenne, H.J., Burhenne, L.W. , Goldberg, T.G. Hislop, A.J. Worth, P.M.Ribeck, L. Kan, Interval Breast cancer in screening mammography program of British Columbia: analysis and calcification. AJR,162,pp. 1067-1071, 1994.

83. Caldwell, R., An Overview of the INFFC: from Organization to Results, in: Nonlinear financial forecasting, Proc. of the first INFFC, Finance and Technology, 1997,pp.9-22.

84. Chart, D. 2000. Shulte and Goodman's Riddle. The British journal for the philosophy of science,5 1:147-149.

85. Chickering, D.M., Learning Bayesian networks in NP-complete. IN: D. Fisher and H-J. Lehz,editors, Learning from Data- Artificial intelligence and Statistics, Springer Verlag, 1996.

86. Clocksin W.F., Mellish C S. Programming m Prolog NY, 1981,280c.

87. T DandekarandK Sharma, Regulatory RNA, Springer Verlag, Heidelberg 1998

88. DanyIuk,A (1989) Finding new rules for incomplete theories-Explicit biases for induction with contextual information. Proceedings of the Sixth International Workshop on Machine Learning (pp 34-36) Ithaca, NY. Morgan Kaufmann

89. Dhar V, Stein R- Intelligent Decision Support Methods Prentice Hall, NJ, 1997

90. Dzeroski S (1996). Inductive Logic Programming and Knowledge Discovery in Databases In Advances in Knowledge Discovery and Data Mining, Eds U Fayad, G, Piatetsky-Shapiro, P Smyth, R. Uthurusamy AAAI Press, The MIT Press, pp 117-152

91. M N.Van Emden, Quantitative deduction and its fix-point theory // J Logic Programming, v.3, N 1,1986, p 37-53.

92. Fenstad, JI Representation of probabilities defined on first order languages // J N.Crossley, ed , Sets, Models and Recursion Theory Proceedings of the Summer School in Mathematical Logic and Tenth Logic Colloguium (1967) 156-172.

93. Fickett, J W and Hatzigeorgiou, A G (1997) Eukaryotic promoter recognition. Genome Res , 7. 861-878

94. M C Fitting, Logic Programming on a Topological Bilattices // Fundamenta Informática, vil, 1988, p 209-218

95. Flach, P , Giraud-Carner C , and Lloyd J W (1998) Strongly Typed Inductive Concept Learning In Proceedings of the Eighth International Conference on Inductive Logic Programming1.P'98), 185-194.

96. Flann, N., & Dietterich, T. (1989). A study of explanation based methods for inductive learning. Machine Learning, 4,187-226.

97. H.Gaifman, Concerning measure in first order calculi // Israel journal of Math, v.2, N1, 1964, p. 1-18.

98. S.S.Goncharov, Yu.L.Ershov, D.I.Sviridenko, Semantic programming // 10th World Congress Information Processing 86, Dublin, Oct.,1986. Amsterdam, 1986, p.1093-1100.

99. Goodrich, J.A., Cutler, G. and Tjian, R. (1996) Contacts in context: promoter specificity and macromolecular interactions in transcription. Cell, 84(6), 825-830.

100. Gumey J. Neural Networks at the crossroads: caution ahead, Radiology, v. 193, n. 1, pp. 27-28, 1994.

101. Thomas R. Gruber. Towards Principles for the Design of Ontology's Used for Knowledge Sharing// International Workshop on Formal Ontology. 1993. March, Padova, Italy.

102. T.Hailpcrin, Probability Logic // Notre Dame J. of Formal Logic, v.25, N3, 1984, p.198-212.

103. Halpem JY: An analysis of first-order logic of probability. Artificial Intelligence 46: 311-350, 1990.

104. Hansel, G. Sur le nombre des fonctions Boolenes monotones den variables, C.R. Acad. Sci. Paris (in French), 262(20): 1088-1090 (1966).

105. R.C. Hardison, Conserved non-coding sequences are reliable guides to regulatory elements, Trends Genet. 16 (2000) 369-372.

106. Hirsh, H. (1989). Combining empirical and analytical learning with version spaces.

107. Hempel, C. G.: 1968, 'Maximal Specificity and Lawlikeness in Probabilistic Explanation', Philosophy of Science 35, 116-33.

108. Hesse, M. 1969. Ramifications of "grue". The British journal for the philosophy of science, 20.13-15.

109. Holman E W Completely Nonmetnc Multidimensional scaling J. Math Psychol, 1978, V 18, N1, p 39-51.

110. Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-Complete Information Processing Letters 5(1)15-17

111. Hu Y -J. (2001) Biological Sequence Data Mining In De Raedt, L. and Siebes A (eds) PKDD 2001, LNAI 2168, Spnnger-Verlag Berlin Heidelberg, pp 228-240.

112. Jakobsen, IB , Saleeba, J A , Poidinger, M and Littlejohn, T.G (2001) TreeGeneBrowser phy-logenetic data mining of gene sequences from public databases Bioinformatics, 17, 535-540.

113. Katz, B (1989) Integrating learning in a neural network Proceedings of the Sixth international Workshop on Machine Learning (pp 69--71) Ithaca, NY Morgan Kaufmann

114. Keeney RL, Raiffa H. Decisions with Multiple Objectives, preferences and value Tradeoffs John Wiley & Sons, 1976

115. Kendall M G , Stuart A (1977) The advanced theory of statistics, 4th ed, v. 1 .Charles Griffin &1. Co LTD, London.

116. M.Kifer., V.S.Subrahmanian, Theory of Generalized Annotated Logic Programming and its Applications // Research Report, University of Maryland, USA, 1990.

117. King, R.D., Karwath, A., Clare, A. and Dehaspe, L. (2001) The utility of different representations of protein sequence for predicting functional class. Bioinformatics, 17,445-454.

118. Klingenhoff, A., Freeh, K., Quandt, K. and Werner, T. (1999) Functional promoter modules can be detected by formal models independent of overall nucleotide sequence similarity. Bioinformatics, 15(3), 180-186.

119. N.A. Kolchanov et al., Transcription Regulatory Regions Databases (TRRD): its status in 2002, Nucleic Acids Res. 30 (2002) 312-317.

120. D. Koller, A. Pfeffer Learning probabilities for noisy first-order rules, In: Proc. of the 15th Int. Joint Conf. on Artificial Intelligence, Nagoya, Japan, 1997

121. Koller, D., Pfeffer., A., Probabilistic frame-based systems. In Proc. AAAI, 1998

122. Kondrakhin, Y.V, Kel, A.E., Kolchanov, N.A., Romaschenko, A.G. and Milanesi, L. (1995) Eu-karyotic promoter recognition by binding sites for transcription factors. Comput Appl Biosci, 11, 477-488.

123. Kovalerchuk B (1975): On cyclical scales. Comp. Syst. 61:51-59, Novosibirsk, Institute of Mathematics, (in Russian).

124. Kovalerchuk, B. (1976), Coordinating methods for decision rules and training data in pattern recognition. Ph. D. Diss., Institute of Mathematics, USSR Academy of Science, Novosibirsk,146 p (in Russian).

125. Kovalerchuk, B , Ruiz J F , Vityaev E., Fisher S. Prototype Internet consultation system for radiologists Journal of Digital Imaging, vol 11, n 3, Suppl., 1998, pp.22-26

126. Kovalerchuk B, Vityaev E, Ruiz JF. (1997) Design of consistent system for radiologists to support breast cancer diagnosis. Joint Conf of Information Sciences, Duke University, NC, 2 118-121, 1997

127. Kovalerchuk, B , Vityaev, E , Ruiz, J (2000) Consistent Knowledge Discovery in Medical Diagnosis IEEE Engineering in Medicine and Biology Magazine Special issue "Medical Data Mining", July/August, 26-37.

128. Kovalerchuk, B , Vityaev, E , Ruiz, J F (2001) Consistent and Complete Data and "Expert" Mining in Medicine. In Medical Data Mining and Knowledge Discovery (Book chapter), Springer, 238-280

129. Kovalerchuk B, Vityaev E (1998) Discovering Lawlike Regularities in Financial Time Series Journal of Computational Intelligence in Finance 6 (3) 12-26

130. Kovalerchuk B., Vityaev E Data Mining in Finance Advances in Relational and Hybrid methods (Kluwer international series in engineering and computer science, SECS 547), Kluwer Academic Publishers, 2000, p 308

131. Kovalerchuk, B , Talianski V , Comparison of empirical and computed fuzzy values of conjunction, Fuzzy Sets and Systems, v. 46, pp 49-53,1992

132. Kovalerchuk, B , Tnantaphyllou, E, Despande, A , Vityaev, E 1996. "Interactive Learning of Monotone Boolean Function" Information Sciences, Vol 94, issue 1-4, pp 87-118.

133. Kovalerchuk, B., Triantaphyllou, E., Ruiz J., Clayton J.Fuzzy Logic in Computer-Aided Breast Cancer Diagnosis: Analysis of Lobulation, Artificial Intelligence in Medicine, No. 11, pp. 75-85, 1997.

134. Kovalerchuk B., Conner N., Ruiz J., Clayton J. Fuzzy logic for formalization of breast imaging lexicon and feature extraction. 4th Intern. Workshop on Digital Mammography, June 7-10,1998, University of Nijmegen, Netherlands, 1998.

135. Krantz DH, Luce RD, Suppes P, and Tversky A: Foundations of Measurement V.l-3, Acad. Press, NY, London. 1971,1989,1990.

136. Kretschmann, E., Fleischmann, W. and Apweiler, R. (2001) Automatic rule generation for protein annotation with the C4.5 data mining algorithm applied on SWISS-PROT Bioinformatics, 17, 920-926.

137. Kulakov Yu.I. The One Principal Underlying Classical Physics // Soviet Physics Doclagy, V.15, #7, Jan., 1971, 666-668.

138. Kutschera F. Von. 1973. Induction and empiricist model of knowledge. In: Logic, Methodology and Philosophy of Science IV, eds.: P.Suppes et al, North-Holland Pub.Co., pp.345-356.

139. Langley P., Zytkow J.M. Data-Driven Approaches to Empirical Discovery // Artificial Intelligence, v.40 (1989), N.l-3, p.283-312.

140. Lavrak, N., Dzeroski, S., Inductive Logic Programming: Techniques and Aapplications. Ellis Hodwood, 1994

141. Lebowitz, M. (1986). Integrated learning: Controlling explanation. Cognitive Science, 10.

142. A.D. Logvinenko, W.Byth, E.E.Vityaev We can order stimuli even when we are not able to see them: An evidence in favour of fuzzy sensory threshold, Perception and Psychophysics, 1997.

143. Matthew, A. 1971. Prediction and Predication. The British journal for the philosophy of science, 22:171-182.

144. M.Matthew, Huntbach An improved version of Shapiro's Model Inference system // Third International conference on Logic Programming (Lecture Notes in Computer Science v.225),p.l80-187.

145. Mikhailichenko G.G Phenomenological and Group Symmetry in the Geometry of two Sets (Theory of Physical Structures) // Soviet Math. Docl 32(2), 1985,371-374.

146. Mitchell (1997) Machine Learning, Prentice Hall.

147. Mitchell, T, Keller, R, & Kedar-Cabelli, S. (1986) Explanation based learning- A unifying view Machine Learning, 1,47—80.

148. Mooney, R, & Ourston, D (1989) Induction over the unexplained Integrated learning of concepts with both explainable and conventional aspects Proceedings of the Sixth International Workshop on Machine Learning (pp 5—7) Ithaca, NY Morgan Kaufmann

149. Muggleton S Bayesian inductive logic programming. In Proceedings of the Eleventh International Conference on Machine Learning W. Cohen and H Hirsh, Eds. (1994), pp 371-379

150. Muggleton S (1999) Scientific Knowledge Discovery Using Inductive Logic Programming, Communications of ACM, vol 42, N11, pp 43-46

151. Muggleton, S , & Buntine, W (1988). Machine invention of first-order predicates by inverting resolution Proceedings of the Fifth International Workshop on Machine Learning (pp 339— 352) Ann Arbor, MI. Morgan Kaufmann

152. Muggleton, S , King, RD and Sternberg, M JE (1992) Protein secondary structure prediction using logic. Prot Eng 5,7), 647-657

153. Mulhall, S 1989. No smoke without fire The meaning of grue. The Philosophical Quarterly, 39.166-89.

154. NarensL (1985), Abstract Measurement Theory, MIT Press, Cambridge

155. Ngo, L , Haddawy, P , Answering queries from context-sensitive probabilistic knowledge bases. Theoretical Computer Science, 1996

156. Nikolov, DB and Burley, SK (1997) RNA Polymerase II transcription initiation A structuralview. Proc. Natl. Acad. Sci. USA, 94, 15-22.

157. Nils J. Nillson, Probability logic // Artif. Intell., v.28, N1, 1986, p. 71-87.

158. Pazzani, M. (1989). Explanation based learning with weak domain theories. Proceedings of the Sixth International Workshop on Machine Learning (pp. 72— 74). Ithaca, NY: Morgan Kaufmann.

159. Pazzani, M. J. (1990). Creating a memory of causal relationships: An integration of empirical and explanation based learning methods. Hillsdale, NJ: Lawrence Erlbaum Associates.

160. Pazzani, M., Kibler, D. (1992). The utility of prior knowledge in inductive learning. Machine Learning, 9,54-97

161. Pazzani, M., (1997), Comprehensible Knowledge Discovery: Gaining Insight from Data. First Federal Data Mining Conference and Exposition, pp. 73-82. Washington, DC

162. Pazzani, M., Brunk, C. (1990), Detecting and correcting errors in rule-based expert systems: An integration of empirical and explanation based learning. Proceedings of the Workshop on Knowledge Acquisition for Knowledge Based System. Banff, Canada.

163. Pedersen, A.G., Baldi, P., Chauvin, Y. and Brunak, S. (1999) The biology of eukaryotic promoter prediction a review. Comput. Chem. 23,191-207.

164. Pzelecki M. The logic of empirical theories. London: Routledge Kogan Paul, 1969. - 109p.

165. K. Quandt et al., Matlnd and Matlnspector: new fast and versatile tools for detection of consensus matches in nucleotide sequence data, Nucleic Acids Res. 23 (1995) 4878-4884.

166. Quinlan, J. R. (1989). Learning relations: Comparison of a symbolic and a connectionist approach (Technical Report). Sydney, Australia: University of Sidney.

167. Quinlan, J. R. (1990). Learning logical definitions from relations. Machine Learning, 5,239-266.

168. Quinlan J.R.1993. C4.5:Programms for Machine Learning. San Mateo, CA; Morgan Kaufmann.

169. D.S. Prestridge, Computer software for eukaryotic promoter analysis. Methods Mol. Biol. 1302000) 265-295

170. Logic Learning, L. De Raedt, K. Kersting, in ACM-SIGKDD Explorations, special issue on Multi-Relational Data Mining, Vol. 5(1), pp. 31-48, July 2003.

171. Roberts F.S., Franke CH On the theory of Uniqueness in Measurement J Math Psychol, 1976, V.14, N3,p 211-218.

172. Russel S, Norvig P (1995) Artificial Intelligence A Modem Approach, Prentice Hall

173. Sarrett, W, Pazzani, M (1989) One-sided algorithms for integrating empirical and explanation based learning Proceedings of the Sixth International Workshop on Machine Learning (pp 26-28) Ithaca, NY Morgan Kaufmann

174. SCAR'96, Proceedings of the Symposium for Computer Applications in Radiology. Kilcoyne RF, Lear JL, Rowberg AH (eds)' Computer applications to assist radiology, Carlsbad, CA, Symposia Foundation, 1996

175. SCAR'98, Proceedings of the Symposium for Computer Applications in Radiology. Journal of Digital Imaging, vol. 11, n 3, Suppl, 1998

176. D S Scott, P Krauss, Assigning Probabilities to Logical Formulas // Aspects of Inductive Logic, (ed J Hintikka, P.Suppes), N Holland, 1966, pp 219-264

177. Scott, D., Suppes P , (1958), Foundation aspects of theories of measurement, Journal of Symbolic Logic, v.23, pp. 113-128

178. E Shapiro, Algorithmic Program Debugging // MIT Press, 1983, pp 204.

179. E Shapiro, Logic Programs witn Uncertainties- A Tool for Implementing Expert Systems // Proc IJCAI '83, Williams Kauffman, 1983, p 529-532

180. Shavlik, J, & Towell, G (1989) Combining explanation based learning and artificial neural networks Proceedings of the Sixth International Workshop on Machine Learning ,pp 90-93 Ithaca, NY' Morgan Kaufmann

181. Solovyev, V and Salamov, A (1997) The gene-finder computer tools for analysis of human andmodel organisms genome sequences. In Proceedings Fifth International Conference on Intelligent Systems for Molecular Biology ISMB-97,294-302.

182. Dhar V., Stein R. Intelligent decision support methods, Prentice Hall, NJ.1997

183. R.T.Ng, V.S.Subrahmanian, Probabilistic reasoning in Logic Programming // Proc. 5th Symposium on Methodologies for Intelligent Systems, Knoxville, North-Holland, 1990, pp. 9-16.

184. R.T.Ng, V.S.Subrahmanian, Annotation Variables and Formulas in Probabilistic Logic Programming // Technical report CS TR-2563, University of Maryland, 1990.

185. Suppes, P. (1970) A probabilistic Theory of Causality, North-Holland, Amsterdam.

186. Thijs, G., Lescot, M., Marchal, K., Rombauts, S., De Moor, B., Rouze, P. and Moreau Y. (2001) A higher-order background model improves the detection of promoter regulatory elements by Gibbs sampling. Bioinformatics, 17,1113-1122.

187. TIWDM, 1996. Third International Workshop on Digital Mammography, University of Chicago, Chicago, IL, Abstracts, June 9-12, 1996,

188. TIWDM, 1998,4th Intem. Workshop on Digital Mammography, June 7-10, 1998, University of Nijmegen, Netherlands, 1998,

189. E.E. Vityaev et al., Computer system "Gene Discovery" for promoter structure analysis, In Silico Biol. 2 (2002) 0024 http://www.bioinfo.de/isb/2002/02/0024/

190. Vityaev, E., Kovalerchuk, B., Empirical Theories Discovery based on the Measurement Theory. Mind and Machine, v.14, #4, 551-573,2004

191. Evgenii Vityaev, Boris Kovalerchuk. Data Mining For Financial Applications. In: O. Maimon and L. Rokach (eds.), Data Mining and Knowledge Discovery Handbook: A Complete Guide for

192. Practitioners and Researchers, Springer 2005, pp.1203-1224.

193. Ullman, J Principles of Database and Knowledge Base Systems Vol 1. Rockville, Mass: Computer Science Press

194. Elmore, J., Wells, M , Carol, M , Lee, H , Howard, D , Feinstein A Variability in radiologists' interpretation of mammograms, New England Journal of Medicine, v 331, n 22,pp 1493-1449, 1994

195. Christopher Welty , Nicola Guanno (2001) Supporting ontological analysis of taxonomic relationships, Data & Knowledge Engineering, v.39 n 1, p 51-74

196. T. Werner, Computer-assisted analysis of transcription control regions Matinspector and other programs, Methods Mol Biol 132 (2000) 337-349

197. T. Werner, Models for prediction and recognition of eukaryotic promoters, Mamm Genome 10 (1999)168-175.

198. Widmer, G (1990) Incremental knowledge intensive learning. A case study based on an extension to Bergadano & Giordana's integrated learning strategy (Technical Report) Austrian Research Institute for Artificial Intelligence

199. E. Wingender et al, The TRANSFAC system on gene expression regulation Nucleic Acids Res 29 (2001)281-3

200. Wingo, P.A., Tong,T, Bolden,S Cancer Statistics, Ca-A Cancer Journal for Clinicians, v 45, n l,pp 8-30, 1995

201. Zagoruiko N.G, Elkma VN Eds (1976), Machine Methods for Discovering Regularities Proceedings of MOZ'76, Novosibirsk (In Russian)

202. Zhang M Q Identification of human gene core-promoters in sihco Genome Res 8-319-326,1998