Файл: Методыискусственногоинтеллекта.pdf

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

22
Введение
Работы в области когнитивного моделирования включают иссле- дование церебральных механизмов распространения и обработки ин- формации в процессе реализации когнитивных функций, механизмов категоризации, именования (действий, объектов), механизмов целеоб- разования и поведения, возникновения и развития когнитивных кон- фликтов.
8. Нечеткие модели и мягкие вычисления. Это направление пред- ставлено нечеткими схемами вывода, «вывода по аналогии», взглядом на теорию нечетких мер с вероятностных позиций, нечеткими пред- ставлениями, аналитическими моделями для описания геометрических объектов, алгоритмами эволюционного моделирования с динамически- ми параметрами, такими, как время жизни и размер популяции, ме- тодами решения оптимизационных задач с использованием технологий генетического поиска, гомеостатических и синергетических принципов и элементов самоорганизации.
9. Разработка инструментальных средств. Это обширная сфера деятельности, ставящая перед собой задачи:
а) создания программных средств приобретения знаний для автома- тизированного переноса знаний и компетентности в базы знаний.
При этом в качестве источников могут выступать не только
«прямые» их носители — эксперты различных областей, но и текстовые материалы — от учебников до протоколов, а также, ра- зумеется, базы данных (имплицитные источники знаний). Верба-
лизация, т. е. перевод таких источников в эксплицитную форму,
составляет содержание методов обнаружения знаний в данных,
в том числе различных методов обучения по примерам (включая предобработку больших массивов данных для дальнейшего ана- лиза);
б) реализации программных средств поддержки баз знаний;
в) реализации программных средств автоматизации рассуждений;
г) реализации программных средств поддержки проектирования ин- теллектуальных систем. Набор таких средств обычно содержит редактор текстов, редактор понятий, редактор концептуальных моделей, библиотеку моделей, систему приобретения знаний от экспертов, средства обучения по примерам и ряд других модулей.

Г л а в а 1
МЕТОДЫ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ
Введение
В этой главе рассматриваются основные методы представления зна- ний в интеллектуальных системах: системы правил, семантические се- ти и системы фреймов. Достаточно подробно описаны системы правил,
неоднородные семантические сети и отношения в них. В последнем параграфе главы описаны основы дескриптивной логики, возникшей относительно недавно и играющей роль логической основы некоторых методов представления знаний. При изложении основных способов представления знаний активно применяется язык исчисления предика- тов первого порядка, атомарные формулы которого использованы для описания составных частей конструкций, используемых для представ- ления знаний.
Поэтому прежде чем переходить собственно к методам представ- ления знаний, уделим некоторое внимание исчислению предикатов первого порядка и одной из его интерпретаций.
1.1. Формальные языки и формальные системы
Существуют работы, где язык исчисления предикатов рассматри- вается как язык представления знаний, однако это не главное его назначение и мы будем использовать его, главным образом, в качестве средства описания элементов конструкций других языков, более ори- ентированных на представление знаний.
Опишем вначале основные конструкции языка исчисления предика- тов первого порядка и их интерпретацию в духе работ [5, 6].
1.1.1. Язык исчисления предикатов первого порядка. Основ- ные конструкции языка L — языка исчисления предикатов первого порядка — называются формулами. Введем вначале алфавит языка L.
Алфавит включает:
1. Счетное множество букв x, y, ..., z, которое будем называть мно- жеством символов для обозначения переменных языка.

24
Гл. 1. Методы представления знаний
2. Счетное множество букв a, b, ..., c, которое будем называть мно- жеством символов для обозначения констант языка.
3. Счетное множество прописных букв P , Q, ... для обозначения предикатных символов языка.
4. Счетное множество строчных букв f, g, ... для обозначения функ- циональных символов.
5. Символы для логических связок → (влечет), ¬ (не).
6. Символ для квантора ∀ (для любого).
7. ( , ) — скобки.
Предикатные буквы P , Q, ... и функциональные буквы f, g, ... могут быть n-местными или, как еще говорят, n-арными. Иначе говоря,
с каждым предикатным или функциональным символом будем связы- вать некоторое натуральное число, равное числу его аргументов.
Определим теперь понятие формулы или правильно построенного выражения языка исчисления предикатов первого порядка.
Формулы языка определяются индуктивным образом. Начнем с определения терма языка:
1. Символ для обозначения переменной есть терм.
2. Символ для обозначения константы есть терм.
3. Если t
1
, t
2
, ... , t m
, ..., t n
— термы, а f и g — функциональные символы арности m и n соответственно, то f(t
1
, t
2
, ..., t m
) и g(t
1
, t
2
, ... , t n
) также термы.
4. Если t
1
, t
2
, ..., t m
, ... , t n
— термы, а P и Q — предикатные символы арности m и n соотвественно, то P (t
1
, t
2
, ..., t m
) и
Q(t
1
, t
2
, ... , t n
) — атомарные формулы.
5. Атомарная формула есть формула.
6. Если A, B — формулы, то A → B, ¬A, ¬B — формулы.
7. Если A — формула, то ∀xA — формула.
8. Всякое слово в алфавите языка является формулой тогда и только тогда, когда это можно показать с помощью конечного числа применений пп. 1–7.
Таким образом, мы завершили одно из возможных определений языка исчисления предикатов первого порядка. Существуют и другие определения, однако язык, определенный нами, является полным, т. е.
в нем выразимо все то, что выразимо в языках (исчисления предикатов первого порядка), определенных любым иным способом.
Можно, например, определить логические связки ∧, ∨ (читается и
и или), выразив их через связки → и ¬:
1. A ∧ B = ¬(A → ¬B),
2. A ∨ B = ¬A → B.

1.1. Формальные языки и формальные системы
25
Квантор существования ∃ (существует) также выражается через квантор всеобщности и отрицание:
∃ xA(x) = ¬∀x¬A(x).
Разумеется, ∧, ∨ и ∃ с тем же успехом можно было бы вклю- чить в язык в качестве трех дополнительных символов. Есть, однако,
некоторые преимущества в том, чтобы сохранить список символов как можно более коротким. Например, индуктивные определения и дока- зательства по индукции оказываются в этом случае короче.
В дальнейшем нам придется использовать понятия свободного
и связанного вхождения переменной в формулу. Вхождение перемен- ной x в формулу A называется связанным, если эта переменная сле- дует за кванторами существования или общности, предшествующими формуле A и находится в области их действия. В противном случае вхождение переменной называется свободным. Если в формуле A от- сутствуют свободно входящие в нее переменные (т. е. либо все перемен- ные связаны, либо отсутствуют), то формула называется замкнутой
формулой или предложением. Атомарную замкнутую формулу будем называть фактом. В том случае, если язык состоит только лишь из предложений, то он называется пропозициональным языком, а бук- вы A, B, ..., входящие в формулы этого языка — пропозициональными переменными.
1.1.2. Элементы исчисления предикатов первого порядка. Рас- смотрим вкратце основные понятия исчисления предикатов первого порядка.
Введем вначале аксиомы исчисления предикатов:
1. A → (B → A).
2. (A → (B → C)) → ((A → B) → (A → C)).
3. (¬A → ¬B) → (B → A).
Однако исчисление предикатов первого порядка не исчерпывается приведенными выше тремя аксиомами и правилами вывода. Смысл кванторов устанавливается еще двумя аксиомами и одним правилом вывода.
4. Аксиома генерализации: (∀x)((A → B) → (A → (∀x)B)), где x не является свободной переменной в A;
5. Аксиома спецификации: ∀tA(t) → A(x), где t — терм, а x не содержится в t в качестве свободной переменной.
Правила вывода:
1. Правило отделения: если выводимо A и выводимо A → B, то выводимо B.

26
Гл. 1. Методы представления знаний
2. Правило подстановки: в любую аксиому на место любой про- позициональной переменной можно подставить любое предложе- ние, предварительно переименовав пропозициональные перемен- ные подставляемого предложения так, чтобы они не совпадали с пропозициональными переменными аксиомы.
Если в аксиомах 1–3 все переменные являются пропозициональны- ми, то такое исчисление называется пропозициональным исчислением
или исчислением высказываний.
Рассмотрим пример вывода в исчислении высказываний. Возьмем,
например, три закона логики, сформулированные Аристотелем и на- зываемые постулатами Аристотеля. В языке исчисления высказываний они записываются следующим образом.
Пусть P — пропозициональная переменная исчисления высказыва- ний:
Постулат 1. P → P .
Постулат 2. P ∨ ¬P .
Постулат 3. ¬(P ∧ ¬P ).
Первый из постулатов Аристотеля — это так называемый закон тождества; второй — закон исключенного третьего и третий — закон противоречия.
Докажем один из постулатов, например P → P .
Используем аксиому 1 и правило подстановки (вместо B подставим
P → P : получим A → ((P → P ) → A)).
Из аксиомы 2: (A → ((P → P ) → C)) → ((A → (P → P )) → (A →
→ C)).
Вместо A, C подставим P :
(P → ((P → P ) → P ))
|
{z
}
X
→ ((P → (P → P )) → (P → P ))
|
{z
}
Y
Применим правило отделения: та часть последней формулы, которая обозначена через X, является аксиомой, т. е. выводима, тогда, в силу правила отделения, выводима формула, обозначенная через Y .
Теперь применим правило отделения к Y :
(P → (P → P ))
|
{z
}
X
′
→ (P → P )
| {z }
Y
′
и, рассуждая таким же образом, получим, что Y
′
выводима. Таким образом, закон тождества Аристотеля является теоремой исчисле- ния высказываний. Действуя таким же образом, можно доказать, что второй и третий постулаты Аристотеля также являются теоремами
исчисления высказываний.

1.1. Формальные языки и формальные системы
27 3. Правило обобщения: если выводимо A, то выводимо ∀xA, где x — свободная переменная в A.
Аксиомы 1–5 исчисления предикатов первого порядка (или матема- тической логики первого порядка) называются логическими аксиома- ми, они описывают логические законы, справедливые всегда, незави- симо от предметной области. Если же к аксиомам 1–5 добавить еще и аксиомы, опсывающие некоторую предметную область, например,
арифметику или теорию групп, то получим формальную теорию —
формальную арифметику или формальную теорию групп, соответствен- но. При этом, разумеется, в алфавит языка следует ввести спецаль- ные функциональные символы, такие как сложение в арифметике или умножение в теории групп.
Словосочетание «первый порядок» относится исключительно к тому обстоятельству, что кванторы ∀ и ∃ действуют на некотором мно- жестве U. Логика второго порядка разрешает одному из кванторов действовать на подмножествах множества U и на функциях из сте- пеней U в U. Логика третьего порядка может использовать кванто- ры по множествам функций и т. д. Уже из этих разъяснений видно,
что в логиках более высоких порядков (как говорят, более сильных логиках) используются и некоторые нелогические понятия, такие как множество.
Некоторым обобщением понятия исчисления является понятие фор- мальной системы.
1.1.3. Формальные системы. Будем полагать, что если заданы некоторый алфавит, множество формул, множества аксиом и правил вывода, то тем самым задана некоторая формальная система. Иначе говоря, формальная система F представляет собой совокупность сле- дующих объектов:
F = hT , P , A, Пi,
T — счетное множество символов и операций над ними; P — мно- жество правил грамматики, применение которых к символам из T
позволяет строить правильно построенные формулы; A — множество аксиом; П — множество правил вывода.
Если среди аксиом имеются нелогические аксиомы (аксиомы, опи- сывающие некоторую предметную область), то формальная система называется формальной теорией.
Выводом (или доказательством) в формальной системе называ- ется конечная последовательность правильно построенных формул
A
1
, A
2
, ..., A
n
, таких что каждая из формул последовательности либо является аксиомой, либо получена из предыдущих формул последо- вательности с использованием аксиом и правил вывода. Формула A
n