Материал: Алгебра_кортежей

Б.А. Кулик, А.А. Зуенко, А.Я. Фридман

АЛГЕБРАИЧЕСКИЙ ПОДХОД К ИНТЕЛЛЕКТУАЛЬНОЙ ОБРАБОТКЕ ДАННЫХ И ЗНАНИЙ

Санкт-Петербург Издательство Политехнического университета

2010

УДК 004.657 К 90

Рецензенты:

Заместитель директора ИСА РАН, постоянный член Европейского комитета по искусственному интеллекту (ECCAI), доктор физико-математичсеских наук, профессор Г.С. Осипов

Ведущий научный сотрудник Санкт-Петербургского института информатики и автоматизации Российской академии наук В.А. Дюк

Кулик Б.А. Алгебраический подход к интеллектуальной обработке данных и знаний / Кулик Б.А., Зуенко А.А., Фридман А.Я.. – СПб.: Изд-во Политехн. ун-та, 2010. 235 c.

В книге представлен новый математический аппарат – алгебра кортежей (АК), которая относится к классу булевых алгебр и позволяет реализовать алгебраический подход к логическому анализу в системах искусственного интеллекта. В АК, в отличие от формальных систем, где основа – символьные конструкции, в качестве базового выбрано понятие “многоместное отношение” и предложены обобщения операций алгебры множеств для работы с отношениями, заданными в разных схемах. Это позволило расширить возможности существующих систем обработки данных и знаний, основанных на бинарных и реляционных отношениях. АК дает возможность унифицировать представление и анализ как данных, так и знаний, и, следовательно, решить проблему сопряжения баз данных и баз знаний в рамках одной программной системы. Алгоритмы обработки отношений, записанных в виде АК-объектов, хорошо поддаются распараллеливанию. Кроме того, разработаны дополнительные методы уменьшения трудоемкости, а в некоторых случаях – и вычислительной сложности интеллектуальных процедур. В алгебре кортежей, помимо известных методов логических исчислений, реализованы новые алгебраические методы проверки корректности следствия и поиска следствий из заданной системы аксиом. В ходе вывода учитывается внутренняя структура обрабатываемых знаний, что ускоряет решение стандартных задач логического анализа. Помимо логического вывода, АК служит для формализации широкого круга логических задач (абдуктивные и модифицируемые заключения, моделирование графов и семантических сетей, экспертных правил и т.д.).

Работа выполнена при поддержке грантов РФФИ (проекты 03-01-96142-р2003север_а, 09-07-00066), РГНФ (проект 09-02-43203а/С), проекта 2.3 Программы фундаментальных научных исследований ОНИТ РАН и проекта 4.3 "Интеллектуальные базы данных" Программы № 15 Президиума РАН.

Издание книги осуществлено за счет финансирования по проекту 4.3 "Интеллектуальные базы данных" Программы № 15 Президиума РАН.

Предисловие

Математика – это язык!

Дж.У.Гиббс

В основе современной логики лежит математическая система, которая имеет несколько названий: формальный подход, аксиоматический метод, символическая логика, теория формальных систем. Здесь мы будем использовать последнее название (сокращенно ТФС). Этот подход начал развиваться в начале XX века, когда были открыты парадоксы теории множеств. Большинство расценило эти открытия как кризис в основаниях математики. Тогда многие математики, логики и философы решили, что только ТФС может стать защитой от парадоксов и заодно – основой всей математики и логики.

Активность защитников ТФС, среди которых были многие всемирно известные математики и философы (Б. Рассел, Л. Витгенштейн, Д. Гильберт, Дж. Пеано и др.), оказалась столь сильной, что развивавшийся в то время подход к основаниям логики на основе алгебры множеств, булевой алгебры и теории отношений стал постепенно утрачивать свое влияние. В середине XX века своеобразным каноном для приверженцев ТФС стало многотомное математическое сочинение группы известных математиков, публиковавшихся под коллективным псевдонимом Н. Бурбаки [Бурбаки, 1965]. В соответствии с этим каноном из оснований математики должны были исчезнуть такие "неточные", "интуитивные" понятия, как числа, пространства, геометрические фигуры, множества и т.д. По замыслу авторов этих сочинений, в основаниях математики возможны только символы и последовательности символов (предложения), слабо связанные с основными понятиями прикладной математики и предложениями на естественном языке [Арнольд, 2002].

Оказалось, что с помощью ТФС можно изложить не только классическую логику (к ней относятся теория доказательств, математическая логика и отчасти силлогистика), но и многочисленные варианты неклассической логики (многозначная, модальная, паранепротиворечивая, немонотонная и т.д.). В дальнейшем новые логики посыпались как из рога изобилия, и мало кого смущали следующие обстоятельства:

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

3

парадоксы, потрясшие всю математику в первой четверти XX века, так и остались необъяснимой загадкой;

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

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

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

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

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

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

4