0

Искусственный интеллект и логическое программирование

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Клыгина Е. В.

Текст научной работы на тему «Логическое программирование и искусственный интеллект»

СЕКЦИЯ: ИНФОРМАТИКА И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ И ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ

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

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

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

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

Основы логического программирования изучаются в рамках курса «Интеллектуальные информационные системы» в институте математики, физики и информатики Тамбовского государственного университета им. Г.Р. Державина.

1. Адалгенко А.Н.. Кучуков А.М. Логическое программирование и Visual Prolog. СПб.: БХВ – Петербург, 2003. 992 с.

2. Марселлус Д. Программирование экспертных систем на Турбо Прологе. М.: Финансы и статистика, 1994. 256 с.

ТЕХНОЛОГИЯ ОБУЧЕНИЯ И КОНТРОЛЯ ЗНАНИЙ С ИСПОЛЬЗОВАНИЕМ ТЕСТОВОВОЙ ОБОЛОЧКИ «TESTIC»

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

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

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

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

В основе логического вывода лежит математическое понятие «формальная система (ФС)». ФС — это совокупность абстрактных объектов, связанных между собой определенными правилами. Вспомним определение. Формальная система F задана, если определена четверка:
F = (Al, Sn, Ax, Ru)
Al – алфавит – конечное множество символов;
Sn – синтаксис – процедура построения правильно построенных формул ФС;
Ax – аксиомы – совокупность правильных формул, заданных изначально;
Ru – правила вывода – конечное множество правил, позволяющих получать новые формулы из других формул ФС.
Всякая программа на языке ПРОЛОГ является ФС, которых в одной программе может быть несколько. В ПРОЛОГе важную роль играет понятие унификации, позволяющее более широко применять правила ФС за счет подстановки параметров. Хорошим примером ФС в программе является синтаксический анализатор на языке ПРОЛОГ().
ФС можно применить для порождения новых утверждений (прямой вывод) или для доказательства правильности утверждений (обратный вывод). В ПРОЛОГе можно реализовать оба варианта вывода, хотя обратный вывод реализуется непосредственно, поскольку заложен в структуру языка.
Язык логического программирования дает много интересных возможностей для решения интеллектуальных задач, т.е. требующих логического вывода для получения решения. Как правило, возможности языка по созданию различных типов прикладных систем демонстрируются на достаточно простых примерах, предназначенных больше для демонстрации парадигмы логического программирования, в учебных целях.
Для создания практически полезных прикладных систем требуется ряд свойств, отсутствующих в системе ПРОЛОГ, но которые можно в нее добавить.
На всякий случай, вспомним, что вычисление в логическом программировании состоит в поиске логического вывода. Этим термином именуют дерево, корнем которого является доказываемое утверждение, а остальные вершины содержат утверждения, связанные между собой логическим следованием. При этом терминальные вершины (листья) дерева должны быть исходными данными – утверждениями, сформулированными в условии задачи.
Построение дерева логического вывода состоит в поиске взаимосвязанных цепочек утверждений от листьев к вершине среди множества всех возможных путей от вершины к листьям. Это множество называют пространством поиска задачи.
Поиск может быть прямой – от данных к искомому и обратный – от искомого к данным. В первом подходе из условий задачи вычисляют то, что можно – новые утверждения, увеличивая тем самым количество известного о задаче.
Во втором подходе строятся гипотезы – строится последовательность, точнее дерево, гипотез, которое должна привести к известным данным.
Поскольку ПРОЛОГ основан на обратном выводе, сначала рассмотрим обратный вывод.
Для иллюстрации проблем, возникающих при построении неигрушечных экспертных систем, используем в качестве предметной области планиметрию, точнее говоря, ее небольшую часть, связанную с решением треугольников.
Рассмотрим конкретную задачу.
В равнобедренном треугольнике проведена высота из вершины, расположенной между равными сторонами. В образовавшемся внутреннем треугольнике снова проведена высота, затем в новом треугольнике еще высота, и т.д. всего – 10 высот. Известны длина основания треугольника AC и боковой стороны BC. Нужно решить любой треугольник, образованный проведенными высотами.
Представление основных объектов может быть таким:

  • seg(A,B) – отрезок с концевыми точками A и B;
  • tri(A,B,C) – треугольник с вершинами А, В, С;
  • length(seg(A,B),L) – длина отрезка;
  • equal(tri(A,B,C),tri(X,Y,Z)) – равенство треугольников.
Читайте также:  Долгое завершение работы windows 7 на ноутбуке

Для простоты изложения рассмотрим вычисление второй высоты треугольника – DE. Запишем условия задачи средствами языка ПРОЛОГ:

s(1,exist(d,tri(a,b,c))).
s(2,height(seg(b,d),tri(a,b,c))).
s(3,height(seg(d,e),tri(b,c,d))).
s(4,height(seg(f,e),tri(b,e,d))).
s(5,height(seg(f,g),tri(f,e,d))).
s(6,height(seg(h,g),tri(f,g,e))).
s(7,height(seg(h,i),tri(g,h,e))).
s(8,height(seg(i,k),tri(h,i,e))).
s(9,height(seg(k,l),tri(i,k,e))).
s(10,height(seg(l,m),tri(l,k,e))).
s(11,height(seg(m,n),tri(m,l,e))).
s(12,equal(seg(a,b),seg(b,c))).
s(13,length(seg(a,b),10)).
s(14,length(seg(a,c),16)).
s(15,length(seg(d,e),x)).

Для обеспечения нумерации условий задачи предикаты записаны в дополнительных скобках в виде s(N,P).
Последняя строка в исходных данных задачи определяет цель – утверждение, которое необходимо доказать. В нашем случае цель length(seg(d,e),x) содержит переменную х, что позволяет – вычислить значение длины отрезка DE.
Одна из основных трудностей в применении ПРОЛОГа для реализации коммерческих систем – возникновение зацикливания программы в процессе вычислений. Причиной этого может быть не ошибка в программе, а рекурсивность свойств объектов предметной области и, соответственно – рекурсивность правил логического вывода.
Например, в правилах логического вывода для решения треугольников неизбежно происходит обращение к аналогичным правилам.
Пример 1, Вычисление длины отрезка в треугольнике.

Вычисление длины стороны треугольника через высоту и площадь:
length(seg(A,C),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(B,D),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.

Вычисление длины высоты треугольника через основание и площадь:
length(seg(B,D),L):-
height(seg(B,D),tri(A,B,C)),
length(seg(A,C),L1),
area(tri(A,B,C),S1),
L is (2*S1)/L1.

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

  1. (78) hypot(tri(d,b,c),seg(b,c)) [79]
  2. (45) exist_rect(tri(d,b,c),seg(d,b)) [2]
  3. (46) length(seg(d,c),8) [14,47]
  4. (66) length(seg(b,c),10) [13,12]
  5. (77) pif_length([seg(d,b),6],[[seg(d,c),8],[seg(b,c),10]]) [78]
  6. (47) median(tri(a,b,c),seg(b,d)) [2,48]
  7. (333) rectangle(tri(c,d,b),_2F28) [2]
  8. (334) catets(tri(c,d,b),[seg(b,d),seg(d,c)]) [78]
  9. (44) length(seg(d,b),6) [77,66,46,45]
  10. (46) length(seg(d,c),8) [14,47]
  11. (332) area(tri(c,d,b),24) [46,44,334,333]
  12. (66) length(seg(b,c),10) [13,12]
  13. (331) length(seg(d,e),4.8) [66,332,3]

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

Как можно видеть из рисунка, все терминальные вершины дерева – утверждения из исходных данных.
Приведем текстовую интерпретацию полученного решения.
1)Для вычисления длины отрезка seg(d,e) (331) использовано правило: если искомый отрезок является высотой в треугольнике, то его длина равна площади треугольника деленной на основание и умноженной на два. Аргументы для этого правила получены из целей с номерами 66,332,3,
Площадь треугольника cdb равна 24 – цель 332. Длина основания bc равна 10 – цель 66. Искомая длина равна 2*(24/10) = 4.8. Отрезок de является высотой треугольника cdb – цель 3 (исходные данные).
2)Длина отрезка bc (66) вычислена из правила – если искомый отрезок равен другому отрезку с известной длиной, то искомая длина равна длина равного отрезка.
В нашем случае искомый отрезок bc равен отрезку ab – это задано в исходных данных – цель 12, длина отрезка ab задана в утверждении 13.
3) Площадь треугольника cdb (332) вычисляется по правилу для прямоугольных треугольников по длинам катетов, аргументы заданы целями 46,44, 333, 334.
Прямоугольность треугольника cdb (333) следует из того, что отрезок bd является высотой в треугольнике abc (2). Отсюда следует определение отрезков, которые являются катетами в этом треугольнике – bd и dc (334). Далее следует вычисление длин катетов (44) и (46).
4)Длина катета db (44) вычисляется через прямоугольный треугольник bdc из целей с номерами 77,66,46,45.
Цель 77 – применение теоремы Пифагора для вычисления отрезка db. Цель 66 – вычисление длины отрезка bc. Цель 46 – длина отрезка dc. Цель 45- наличие прямоугольного треугольника dbс с искомым отрезком db.
5)Длина катета dc (46) вычисляется из целей 14, 47 по правилу отрезка при медиане треугольника. Цель 14 задана в исходных данных – длина отрезка ac, на который опущена медиана bd (47). Применяется правило – высота в равнобедренном треугольнике, опущенная на его основание, является медианой.

Поскольку в приведенном примере данные получены в результате применения конкретной логической программы, можно предположить, что объем поиска составил 334 цели, из которых 13 составили необходимое решение задачи.
Для более сложного случая, например для вычисления десятой высоты в нашем треугольнике – отрезка LM, объем поиска составил 1667 целей, а в процессе поиска вывода было получено 138 утверждений, из которых далеко не все вошли в искомое решение. Незначительный объем поиска связан с тем, что было использовано всего четыре правила для вычисления длины отрезка.
Мы рассмотрели упрощенный пример для иллюстрации основных аспектов решения задач, требующих логического вывода. Если же попытаться описать все теоремы планиметрии для вычисления длины отрезка – подобие и равенство треугольников, тригонометрические функции, составные отрезки, объем необходимых вычислений возрастает на порядки и здесь понадобится иметь дополнительные возможности, чтобы справиться со всеми возникающими сложностями.
Для того, чтобы решать достаточно объемные интеллектуальные задачи недостаточно обычного языка ПРОЛОГ, поскольку в нем отсутствует ряд свойств, без которых сложно построить практически полезную программу. Эти усовершенствования системы языка ПРОЛОГ можно разделить на две группы – управление поиском вывода (логические) и технологические.
Необходимы следующие усовершенствования управления поиском:

  • защита от зацикливания;
  • сохранение созданного вывода;
  • возможность работать с большими объемами правил;
  • сохранение трассы поиска вывода в пространстве состояний предметной области для отладки;
  • управление объемом вычислений для защиты от излишних неэффективных поисков при наличии ошибки или отсутствии решения;
  • построение объяснения полученного решения.
    Технологические усовершенствования:
  • интеграция с процедурными языками программирования;
  • интеграция со средствами операционной системы;
  • эффективность кода;
  • возможность создания автономных программ.
    Большинство современных систем языка ПРОЛОГ имеют компилятор и другие средства, которые обеспечивают возможность создания прикладных программ, применимых без интерпретатора языка ПРОЛОГ, совместно с программами на других языках программирования или автономно.
    Для получения усовершенствований поиска необходимо в каждое правило ПРОЛОГа в прикладной программе вставить дополнительные проверки и, соответственно, дополнительные аргументы.
    Чтобы не делать это вручную, можно использовать специальные инструментальные системы. Научно-производственная фирма «Semantics Research» разработала такую систему под названием Exxlog, которую можно скачать бесплатно на сайте компании(exxlog.ru).
Читайте также:  Вход в интернет альф

Заключение

Мы рассмотрели основные аспекты построения формальной системы в виде программы для решения логических задач. ФС решает задачи путем полного перебора вариантов.
Если приведенным здесь способом описать правила для всех необходимых теорем планиметрии, пространство поиска будет неподъемным для среднего компьютера, а может быть и суперкомпьютера. Однако мы хорошо знаем, что толковый школьник решит почти любую решаемую задачу за приемлемое время, не выполняя слишком большого перебора.
Как он это делает? За счет анализа и планирования решения, намечая самые перспективные подходы и не рассматривая заведомо бесполезные. Знания, которыми он воспользуется для планирования решения, не являются геометрическими теоремами – это и есть те знания, которые называют экспертными – знания о методах поиска решения, которые обычно эксперт получает в процессе обучения и вырабатывает самостоятельно, в процессе приобретения опыта.
Вывод – одна ФС не является экспертной системой. Для ЭС нужно объединить несколько ФС. В дальнейшем рассмотрим более подробно, как это сделать.

— Я всё обдумал, — сказал Альберт. — Работая, я всю ночь думал и думал. И я сделал робота-юриста.
— Робота-юриста?
— Да, робота с большим объемом памяти, чем у остальных, и мощным решающим устройством, которое руководствуется законами формальной логики. Ведь право основано на логике, не так ли?
— Наверно, — ответил Ли. — Во всяком случае, должно основываться.

«Сделай сам», Клиффорд Саймак.

Мы уже упоминали о трёх основных направления в современном программировании: алгоритмическом, статистическом и логическом. Наиболее важную роль играет алгоритмическое программирование. Это примерно 99% процентов всех существующих программ, включая веб-сайты, операционные системы, текстовые редакторы и компьютерные игры. Статистическое направление позволяет решать некоторые специфические задачи, которые невозможно было решить алгоритмически. Оно сейчас бурно развивается: нейронные сети, bigdata, machinelearning– это всё разные названия примерно одного и того же. Логическое направление тоже успешно используется для определенного круга задач, но по причине отсутствия ярких успехов за последние годы интерес широкой общественности (в том числе, и юридической) к нему явно снизился. Тем не менее, на наш взгляд, если право и удастся связать с программированием, то, прежде всего, посредством логики (совпадение?).

Одним из первых применением логического подхода к искусственному интеллекту стали шахматные (а также шашечные и т. п.) программы. Разберем на примере шахмат просто, потому что это удачный пример по сути и про шахматы все знают.

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

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

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

Кажется слишком сложно, но на самом деле все с этим сталкивались в том или ином виде. Например, в шахматах:

  1. Формальный язык. Подойдёт обычная шахматная нотация, где фигуры обозначаются по первой букве, а их положение на доске – буквенно-числовыми координатами. Например, «Крb3» означает, что король находится на вертикали bи горизонтали 3.
  2. Правила построения легальных выражений напрямую следуют из шахматных правил: два короля не могут стоять рядом, не может быть шаха обоим королям, пешка не может находиться на крайней горизонтали и т. д. Всё это при желании можно сформулировать в терминах шахматной нотации. Например, понятно, что позиция «Белые: Крf1 Черные: Крf3» – легальная, а «Белые: Крf1 Черные: Крf2» – нет.
  3. Правилам перехода из одной легальной позиции в другую, собственно, и посвящены правила шахмат: слон ходит по диагонали, а конь – буквой «гэ». Чтобы переписать их в терминах шахматной нотации, надо изрядно постараться, особенно с учетом таких неприятностей как рокировка и взятие на проходе… Но поверьте, что любой программист (да и просто любой желающий) с такой задачей рано или поздно справится.
  4. С начальной ситуацией всё понятно, а конечная ситуация – это мат. Для него есть четкие критерии, которые также можно формализовать.
  5. Аналитическая машина. Здесь нет ничего принципиально сложного. Если вы успешно справились с пунктами 2 и 3, то можете смело звать любого программиста, даже абсолютно не играющего в шахматы, который реализует перебор всех (переходов до) легальных позиций (а на самом деле уже текстов!), и ваша первая шахматная программа готова. Поздравляем! Чудес от неё не ждите, но задачи «мат в 3 хода» она будет щёлкать как орешки.
Читайте также:  Доставка авито в каких городах работает

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

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

Теперь давайте посмотрим, как этот подход работает на примере алгебры.

  1. Формальный язык нам изобретать не надо. В отличии от шахмат, нас всех ему научили против нашей воли ещё в школе.
  2. Правила написания легальных выражений тоже понятны: количество открывающихся скобок должно быть равно количеству закрывающихся и т. д.
  3. Правила перехода от одного легального выражения к другому тоже всем до боли знакомы: «от перестановки слагаемых сумма не меняется» и т. д. Либо можно сразу писать в терминах формально языка: a+b=b+a, aa=a2 , a(b+c)=ab+ac,a+a=2a и т. п.
  4. В качестве начального выражения возьмем, к примеру, (x+1) 2 , а описание конечного выражения зависит от того, какую задачу мы хотим решить. Если «раскрыть скобки», то в конечном выражении не должно быть скобок.
  5. Снова зовем программиста, чтобы он немного подкорректировал аналитическую машину из предыдущего примера, и наш простейший алгебраический калькулятор готов. За доли секунды он продемонстрирует то, чему школьники учатся месяцами: (x+1) 2 =(x+1)(x+1)=(x+1)x+(x+1)=xx+x+x+1=x2+2x+1

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

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

  1. Формальный язык. Его пока нет. И непонятно, кто и как сможет его составить. Всю свою историю юристы пытаются уйти от естественного языка со всеми его противоречиями и неоднозначностями. В итоге получился язык достаточно занудный, чтобы быть непонятен простому обывателю, и недостаточно формальный, чтобы быть понятным машине.
  2. Правила написания легальных выражений. Здесь будет что-то вроде «судья не может быть одновременно потерпевшим», нельзя обжаловать решение суда до его оглашения и т. д. Мы это сможем сформулировать на любом языке: хоть человеческом, хоть формальном.
  3. Правила перехода от одного легального выражения к другому. Это обычные законы логики. Прямо по Аристотелю: «Если все люди смертны и Сократ – человек, то Сократ смертен».
  4. Начальное выражение – это, например, материалы дела, записанные на формальном языке. Конечное выражение тогда – судебное решение.
  5. Аналитическая машина. Она будет мало отличаться от аналитической машины для шахмат, компьютерной алгебры и других подобных задач.

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

Надо отметить, что математическая нотация принесла огромную пользу ещё задолго до появления компьютеров: громоздкие многословные записи существенно упростились, произошла унификация языка и понятий, логические переходы стали легко проверяемы, а техника проведения расчетов до того упростилась, что сейчас её умудрятся объяснять в начальной школе. Смеем предположить, что развитие и формализация юридического языка должна привести примерно к тем же последствиям, что и в математике: логические переходы станут более понятными и схематичными, а значит и доступными для проверки, количество грубых ошибок резко уменьшится, и где-нибудь через полвека будущие второклашки между уроками арифметики и английской грамматики начнут постигать основы юридической техники наряду с ОБЖ или иными уроками, где затрагиваются социальные нормы. А потом к ним и компьютерные программы подтянутся…

Почему сейчас такое невозможно, надеюсь, никому объяснять не надо.

В заключение добавим, что, на наш взгляд, до появления формального юридического языка и искусственного интеллекта на его основе невозможно всерьез говорить о практическом применении блокчейн-технологии и смарт-контрактах. Потому что не видно никакого другого способа запрограммировать хотя бы простейшие юридические понятия. Или кто-то в самом деле верит, что искусственный интеллект должен помогать юристу вынюхивать пресловутый «дух права»?

admin

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *