И.А. Бессмертный «Системный анализ, управление и обработка информации (технические науки)»
Преимущества: Компактное представление знаний Простота кодирования для ввода в ЭВМ Широкое применение (юридические документы, инструкции,…) Простота восприятия Недостатки: Экспоненциальная сложность поиска на дереве решений Неизбежное накопление противоречий по мере роста базы знаний Существующие решения: ТРИЗ Экспертные системы Semantic Web 2
Цель: Разработка принципов построения и концептуальной модели интеллектуального агента для систем искусственного интеллекта (ИИ) на основе продукционной модели знаний. Задачи: Выбор метрик и оценка объемов знаний в формализованных источниках на основе теории информации. Исследование и разработка методов ускорения логического вывода в продукционных системах. Исследование компетентностного подхода к ИИ с реализацией механизма навыков. Разработка концептуальной модели интеллектуального агента, реализующего в себе компетентностную модель ИИ и управление контекстом. Разработка средств визуализации знаний и интерфейса человек-машина для взаимодействия пользователя с интеллектуальными агентами и представления результатов работы агентов. 3
Требования к оценке: Объективность. Оценка не должна зависеть от субъекта оценивания или автора метода оценки. Воспроизводимость. Оценка не должна зависеть от конкретной аппаратной или программной реализации искусственного интеллекта. Универсальность. Оценка должна быть применимой как к естественному, так и искусственному интеллекту. Количественный характер. Оценка должна выражаться в абсолютных величинах. 4
Энтропия Информация АЛФАВИТНЫЙ ПОДХОД Английский алфавит: 26 букв -> I = 4.7 бит Немецкий алфавит : 31 буква -> I = 4.95 бит I (speed) = 23.5 бит I (Geschwindigkeit) = 74.3 бит ! СЛОВАРНЫЙ ПОДХОД Слово – минимальная лексическая единица (атом) Энтропия Информация w – слово, D – словарь Целиком зависит от словаря 5
СЛОВАРНО-КОНТЕКСТНЫЙ ПОДХОД Пусть понятие E i определено на множестве E i+1 = {E i }, имеющем мощность n i. Тогда При объединении уровней Контекста Информативность фактов: S – множество субъектов, O – множество объектов, P – множество предикатов в данном контексте 6 … E i+1 ={ E i } E i ={ E i-1 } …
ПРИМЕР Онтология Пицца I(Pizza) = 2,32+1,59+3, ,17+4,52+8,3 4= 24,26 бит. 7 hasCountry I = 0 I = 2,32 hasSpiciness I=3,17 I=8,34I=4,52 I=3,32 I=1 AKO hasTopping AKO hasBase AKO Pizza PizzaBase (2) TypeOfTopping (9) PizzaTopping KindOfTopping (36) TypedPizza (10) NamedPizza (23) I = 1,59 Country (5) Spiciness (3)
ПРИМЕР I(db Car ) = I(T Car )+ +I(T Engine )+ +I(T Body )+ +I(T Transmission ) + +I(T Brand )+ +I(T Fuel )+ +I(T TransType )+ +I(T Counry ) = 244 бит 8 I=6,64 Таблица Engine (I=170,24) EngineID (16) EngineFuelID Displacement (100) I=3,0 Таблица Transmission (I=21,0) TransmissionID (3) TransTypeID TransSpeedsNum (8) Таблица Brand (I=24,85) BrandID (4) BrandName CountryID Таблица Car (I=21,18) ModelName (10) BodyID EngineID BrandID TransmissionID Таблица Body (I=1,59) BodyID (3) BodyName I=1,59 Таблица Country (I=3,17) CountryID (5) CountryName I=3,17 EngineFuel (I=1,0) FuelID (2) EngineFuelName I=1,0 Таблица TransType (I=1) TranstypeID (2) TransTypeName I=1,0
ВЫВОДЫ 1. Информативность понятий невозможно оценить вне контекста – информационной среды, которая должна быть одинаковой для всех участников обмена информацией, в противном случае одни и те же факты могут быть интерпретированы по-разному. 3. Определение контекста является неотъемлемой частью любого коммуникативного акта, как между людьми, так и между компьютерами. Установление контекста позволяет обходиться короткими сообщениями, одинаково понятными отправителю и получателю. 5. В рамках любого контекста устанавливается словарь понятий, одинаковый для всех участников обмена информацией, и появляется возможность вычислить информативность всех понятий. 6. Минимальной единицей знаний является факт, составленный из понятий, как молекула из атомов. Информативность фактов, как и информативность понятий, может определяться только в рамках определенного контекста. 7. Предложенные методы позволяют подвергать предметную область декомпозиции и вычислять информативность баз знаний на разных уровнях контекста, а также оценивать количество информации в базах данных, что может быть полезным для контроля оптимальности структуры в ходе проектирования баз данных и знаний. 9
Индексация и предварительный отбор фактов Факт f(s,p,o). Нумерованный факт fn(i,s,p,o). Индекс: где w – место терма t в атоме (в качестве субъекта, предиката или объекта ), [i tw ] – список номеров фактов, имеющих терм t в роли w, w=(s;p;o). Релевантные факты для c j условия правила: 10
Применение операций реляционной алгебры Пусть в результате отбора фактов для условий правила c(s 1,p 1,o 1 ), c(s 2,p 2,o 2 ),..., c(s k,p k,o k ), получены множества кортежей T = {{t i }}, t i =(x i1,x i2 ), или t i =(x i1 ) Вместо интерпретации правил: пересечение X Y (INTERSECT) вычитание X - Y (DIFFERENCE) объединение X U Y (UNION) соединение (INNER JOIN) проекция дополнение (NOT) фильтрация (WHERE) 11 x 11 x 12 x 21 x 22...x i1...x k1 x k2 SELECT F_1.Object AS Uncle, F.Object AS Nephew FROM F INNER JOIN F AS F_1 ON F.Subject=F_1.Subject WHERE (((F.Predicate)="is_parent") AND ((F_1.Predicate)="has_brother"));
Быстрые реляционные операции в среде Prolog 12 ОперацияОператор в СУБД Встроенный предикат в Visual Prolog Сложность встроенного предиката Сложность быстрого предиката Пересечение X Y INTERSECT list::intersection n x n y /2 n x + n y Разность X - Y MINUSlist::differencen x n y /2n x + n y Объединение XUY =(X-Y)+ (Y-X)+(XY) UNIONlist::unionn x n y /2n x + n y СоединениеJOINотсутствуетnxnynxny n x + n y + d x + d y
Агентный подход к поиску решений и роевой интеллект Ср.число переходов до достижения цели b – коэффициент ветвления, d – глубина поиска Число развертываемых вершин для сети NxN - при поиске сначала в ширину V b = b d /2 - при случайных блужданиях Один агент – множество попыток случайного поиска на заданную глубину без цели. Много агентов – множество поездок с заданными целями с возможостью составлять маршрут из готовых фрагментов 13
Выводы: 1. Индексация фактов дает ускорение поиска решений в больших базах знаний, но сохраняется экспоненциальная сложность вывода. 2. Применение операций реляционной алгебры над множествами кортежей переменных обеспечивает квадратичный рост сложности вывода. 3. Применение реляционных операций над отсортированными списками позволяет говорить о линейной сложности вывода в пределах одного правила. 4. Мультиагентный подход в сочетании с роевым интеллектом позволяет эффективно решать задачи, имеющие экспоненциальную сложность. Качество решения – функция времени. 14
15 ПроектЗнанияУменияНавыкиУспешность Игровые программыПравила игрыЭвристические алгоритмы, альфа- бета отсечения Базы дебютов, партий лучших гроссмейстеров (шахматы) Да Экспертные системыФакты, полученные от пользователя в диалоге Машина вывода продукционной системы Правила, реализующие связи внешних проявлений с гипотезами Да Нейронные сетиОбучающие выборкиАлгоритмы обученияОбученные сетиДа Логические агентыДанные от сенсоровАлгоритмы поведения НетДа Оптическое распознавание символов Словари, грамматикиАлгоритмы обученияТиповые образы символов, шаблоны предложений Да Распознавание речиСловари фонем, слов, грамматики Алгоритмы распознавания слов Типовые сочетания слов Распознавание отдельных слов Машинный переводСловари, грамматикиАлгоритмы переводаНетНа уровне отдельных фраз Интеллектуальные системы Обширные базы фактов и правил Машина вывода с алгоритмами ускорения НетНа уровне отдельных задач
16 Знания Узкий контекст Широкий контекст Логические агенты Нейронные сети Интеллектуальные системы Экспертные системы Машинный перевод Распознавание текстов Распознавание речи Игровые программы Semantic Web Навыки
17 % Без прецедентов move(1). move(2). move(3). % правило хорошего хода good_move( X, M ) :- move(M), X – M = 1. good_move( X,M ) :- move(M), X1 is X-M, not(good_move(X1,_)). % С прецедентами move(1). move(2). move(3). good_move( X, M ) :- precedent(X,M),!. good_move( X, M ) :- move(M), X – M = 1. good_move( X,M ) :- move(M), X1 is X-M, not(good_move(X1,_)), assert(precedent(X,M)). Для N=23: Исходное дерево - 20 тыс.узлов, с применением прецедентов – 57 узлов
18 1. Актуальность прецедентов проверяется при каждом обращении к ним Ср.время извлечения прецедента с проверкой его актуальности t 1 = ½ τ |P| + ½ τm|F| = ½ τ(|P| + m|F|), 2. При каждом изменении первичных фактов зависящие от них прецеденты удаляются Ср.время извлечения прецедента t 2 = ½ τ|P|, Ср.время удаления всех зависимых от удаляемого факта прецедентов t d = τ|P|. τ – время извлечения одного факта, F – множество первичных фактов, P – множество прецедентов, m – среднее число первичных фактов, использованных при выводе прецедента
Компетентностный подход позволяет устранить экспоненциальную сложность логического вывода в продукционных системах ПРОБЛЕМЫ проблема актуальности прецедентов; проблема размещения и администрирования прецедентов; проблема противоречивости фактов. 19
а) b) c) 20 База знаний База прецедентов Агент База знаний База прецедентов Агент База знаний База прецедентов Агент Сервер прецедентов База знаний База прецедентов База знаний База прецедентов База знаний Агент Вариант а)Вариант b)Вариант c) Преимущества Децентрализация базы прецедентов Авторы документов могут контролировать состав прецедентов Персональный агент для каждого пользователя Совпадение контекста пользователя с базой прецедентов Широкая доступность Повторное использование прецедентов Возможность оптимизации состава базы знаний Возможность коммерциализации Недостатки Множество прецедентов не коррелирует с множеством запросов Необходимость локального размещения всех фактов предметной области Зависимость от авторов Длительное обучение агента Большие затраты на администрировани Многократное дублирование прецедентов Не учитывается контекст пользователя Отчуждение от авторов документов Необходимость капиталовлоений
где N – число фактов в базе знаний, τ – среднее время доступа к одному факту, A– число атрибутов или классов, релевантных условию запроса, i=(1,n), δ i – число допустимых значений атрибута, C – число экземпляров класса. 21 Поиск и извлечение документов Поиск и извлечение фактов Документы Пользова тель или агент Факты Контекст запроса Запрос Результат D E C B A Контекст домена Контекст запроса Контекст домена Контекст запроса = контекст домена Контекст запроса Контекст домена Контекст запроса x y y x y y x x x x A C D B E
22
Первичные факты E = {e} - события, Вторичные факты S = {s} – состояния Правило: r: ({s t-1 }, {e t }) s t Требование вычислимости: s i =φ(e i, s i-1 ). 23 Множество состояний в момент i S i = {s i } Множество правил R ={r} Событие e i+1 Множество состояний в момент i+1 S i+1 = {s i+1 } Множество правил R ={r} Событие e i+2 Множество состояний в момент i+2 S i+2 = {s i+2 }
Декомпозиция состояний а) s i =φ(e i, s i-1, s i-2 ). Граф состояний: б) s i =φ(e i, s i-1 ). 24 б)б) a) e33e33 e3e3 e2e2 e2e2 S 32 S2S2 S 12 S 11 S 31 e3e3 e2e2 e2e2 S 32 S 21 S 12 S 11 S 31 S 22 singledivorcedmarried widowed
25 XXY ternary(X, canMarry, Y, Certainty, [X, canMarry, Y, Cty, Cond1,[NOT|Cond2]):- ternary(X, oppositeSex, Y, Cty1, Cond1), Cty1>=0, ternary(X, closeRelative,Y,Cty2, Cond2), Cty2=
26 1.Антропоморфная модель интеллектуального агента для больших баз знаний является актуальной и технически реализуемой. 2.В продукционной модели знаний отсутствует компонент «навыки». При этом большую часть времени в поведении человека превалируют интеллектуальные навыки, а не логическое мышление. 3.Вывод на основе прецедентов является аналогом интеллектуальных навыков человека и позволяет снизить сложность поиска до полиномиальной. 4.Процесс создания и сопровождения базы прецедентов может управляться запросами, расписаниями или событиями. Последний способ является наиболее простым в реализации, но предъявляет повышенные требования к онтологической организации знаний, используемой всеми участниками создания и использования ресурсов, на которых размещаются базы знаний. 5.В допущении открытого мира база фактов должна строиться в пространстве «состояния – события». Текущее состояние любого объекта может быть вычислено путем обработки всех событий, произошедших после известного предыдущего состояния.
Задачи: Графический язык запросов к базе знаний Отображение сложных предметных областей Объяснение результатов найденных решений 27
Графический язык запросов vs. SPARQL SELECT ?S ?University WHERE {?S ISA спецсовет. ?S has_spec ?S at ?University. ?University in С.Петербург} 28
Графический язык запросов 29
30
Графический язык запросов 31
IF ?x has_child ?y AND ?x has_child ?z AND ?y differs ?z THEN ?y is_sibling ?z IF ?x is_sibling ?y AND ?x has_sex male THEN ?x is_brother ?y 32 Nikita is_sibling Andrey BECAUSE Sergey1913 has_child Nikita AND Segrey1913 has_child Andrey AND Nikita differs Andrey Nikita is_sibling Andrey BECAUSE Sergey1913 has_child Nikita AND Segrey1913 has_child Andrey AND Nikita differs Andrey
33 IF ?x has_spouse ?y AND ?x has_child ?z AND NOT ?y has_child ?z THEN ?y is_step-parent ?z. IF ?x has_spouse ?y AND ?x has_child ?z AND ?a has_child ?z AND ?a differs ?x AND ?a differs ?y THEN ?y is_step-parent ?z. IF ?x has_spouse ?y AND ?x has_child ?z AND ?a has_child ?z AND ?a differs ?x AND ?a differs ?y THEN ?y is_step-parent ?z. Julia is_step-parent Egor BECAUSE Julia NOT has_child Egor AND Andrey has_spouse Julia AND Andrey has_child Egor. Julia is_step-parent Egor BECAUSE Julia NOT has_child Egor AND Andrey has_spouse Julia AND Andrey has_child Egor.
34 t(A). pic(file1.bmp). f(A,…,B). f(A,…,C). f(C,…,D). file1.txt t(C). pic(file2.bmp). f(C,…,E). f(C,…,F). f(F,…,G). File2.txt t(D). pic(file3.bmp). f(D,…,H). f(D,…,C). f(H,…,A). File3.txt e(C,file2.txt ). e(D,file3.txt). e(G,file4.txt). e(C,file2.txt). e(A,file1.txt).
35 1.В отличие от баз данных, в которых результаты обработки запросов представлены множествами однородных кортежей, доступ к базам знаний порождает разнообразные факты, связанные между собой. Вследствие этого визуализация знаний является важной составной частью интеллектуальных систем на основе баз знаний. Семантический граф являются привлекательной формой отображения знаний. 2.Отображение семантического графа даже небольшой предметной области на двумерное пространство является проблематичным вследствие большого числа связей между объектами. Для восприятия фактов человеком необходимы специальные методы, позволяющие согласовать визуализацию знаний с возможностями человека. 3. Контекстный подход, как универсальный способ организации обмена информацией, позволяет решить проблему визуализации даже больших предметных областей. Управление контекстом в процессе визуализации знаний позволяет отображать на экране только информацию, необходимую для передачи семантики сообщения.
1. К оценке количества информации в базах данных и знаний применен контекстный подход, позволивший вычислять информативность понятий и фактов методами теории информации, а также подвергать эту задачу декомпозиции на разных уровнях обобщения. 2. Разработан метод индексации и предварительного отбора фактов для применения в правилах логического вывода, позволяющий сокращать размерность поиска на дереве решений, в т.ч. для базы фактов, подверженной изменениям. 3. К логическому выводу применены теоретико-множественные операции, на основе которых задача поиска решений в продукционной модели знаний может быть перенесена в среду реляционных СУБД. 4. Разработаны методы быстрого логического вывода в среде программирования Prolog, основанные на реляционных операциях над отсортированными кортежами переменных, входящих в условия правил. 36
6. Исследован многоагентный подход с методами роевого интеллекта к информационному поиску, продемонстрировавшими эффективность простейших алгоритмов поведения агентов для нахождения решений. 7. К анализу систем ИИ применен компетентностный антропоморфный подход с применением механизма интеллектуальных навыков, позволяющий устранить экспоненциальный рост сложности задачи логического вывода. 8. Разработана модель знаний в пространстве состояния – события, объединяющая первичные факты, заносимые в базу явным образом, и вторичные факты, выводимые из правил. 9. Разработана концептуальная модель интеллектуального агента в продукционных системах с применением моделирования на основе прецедентов, позволяющего устранить экспоненциальную сложность поиска решений в базах знаний. 10. Разработаны методы визуализации знаний для взаимодействия с интеллектуальным агентом и интерпретации результатов работы агента с использованием механизма управления контекстом. 37
СПАСИБО ЗА ВНИМАНИЕ! 38