ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ ОСНОВНЫЕ НАПРАВЛЕНИЯ И СОСТОЯНИЕ ИССЛЕДОВАНИЙ Г.С. ОСИПОВ gos@isa.ru. - презентация

1 ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ ОСНОВНЫЕ НАПРАВЛЕНИЯ И СОСТОЯНИЕ ИССЛЕДОВАНИЙ Г.С. ОСИПОВ

2 Topics 2010 ` * Propositional Logic Description logic & Ontologies Cooperation * Diagnosis & Discovery Argumentation& Dialogue Robotics & Autonomous Systems Направления 2012 Дескриптивные логики Онтологии Кооперация и координация Аргументация Восприятие и роботика

3 Coalitions & Teams Planning Uncertainty Bayesian Methods Preference Modelling * Clastering & Classification Агенты и обучение играм Планирование и составление расписаний Вероятностные подходы Предпочтения

4 REINFORCEMENT LEARNING NEGOTIATION & ALLOCATION MACHINE LEARNING -- KERNEL METHODS NATURAL LANGUAGE PROCESSING AUCTIONS & TRADING SYSTEMS Обучение с подкреплением Переговоры и координация Интеллектуальный анализ данных Естественный язык Пространственные и временные рассуждения Аукционы и доверие.

5 TRUST & RECOMMENDATION * BELIEF REVISION, UPDATE, AND MERGING * BELIEF-DESIRE- INTENTION ARCHITECTURES APPLICATIONS PROCESSES AND STOCHASTIC MODELS Ограничения, удовлетворимость и обучение. Мультидисциплинарн ые подходы Рассуждения и диагностика, основанные на моделях

6 * LOGICAL FOUNDATIONS OF KR SEARCH & HEURISTICS MACHINE LEARNING & DATA MINING CONSTRAINTS ACTION, TIME, AND CHANGE Автоматические рассуждения Поиск и эвристики Машинное обучение Удовлетворение ограничений Действия, изменения и причинность

7 FOUNDATIONS OF LOGICAL REASONING * NEURAL NETS ORIGINS OF LANGUAGE UNCERTAINTY IN AI Теория игр Компьютерный анализ социального выбора

8 * INFORMATION RETRIEVAL LOGICAL FOUNDATIONS OF MAS * LOGIC PROGRAMMING & ANSWER SET PROGRAMMING * Шрифтом красного цвета выделены направления, не представленные в работах 2012 года Немонотонные рассуждения Марковские процессы принятия решений

9 Направления 1996 года Абдукция, темпоральные и каузальные рассуждения Пересмотр убеждений и немонотонные рассуждения Рассуждения на основе прецедентов Рассуждения и программирование на основе ограничений Генетические алгоритмы и нейронные сети

10 Направления 1996 года Интеллектуальный интерфей пользователя Представление знаний Логическое программирование, доказательство теорем и поиск Машинное обучение и представление знаний Модельные, качественные и пространственные рассуждения

11 Направления 1996 года Многоагентные системы Обработка естественного языка Планирование, составление расписаний и рассуждения о действиях Рассуждения с неопределенностью Роботика и зрение

12 Приглашенные лекции на ECAI 2012 Том Митчел Обучение не заканчивается никогда Вольфганг Бибель Искусственный интеллект в исторической перспективе Эрик Сандеволл Ранняя история искусственного интеллекта в Европе. Вулфрэм Булгард Вероятностная техника навигации мобильных роботов

13 ОСНОВНЫЕ НАПРАВЛЕНИЯ Автоматические рассуждения1 ЛоКо- логика для проблемы конфигурации. Исследуется фрагмент логики первого порядка, приспособленный для описания проблемы конфигурации. Особенность - в том, что количество компонент, используемых в конфигурации явно неограниченно, однако, неявно это делают аксиомы. Вычисление конфигурации сводится к поиску модели. Предлагается язык, соответствующие алгоритмы и результаты о сложности.

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

15 Автоматические рассуждения 3 Интервальная темпоральная логика над конечным линейным порядком: полная картина. Интервальная темпоральная логика предоставляет естественный подход к временным рассуждениям об интервальных структурах над линейно- упорядоченной предметной областью. Рассматриваются фрагменты интервальной темпоральной логики Хальперна и Шоама, в которой разрешима проблема выполнимости.

16 Агенты и обучение играм1 Социальные законы – множество ограничений, накладываемых на поведение агентов в многоагентной системе для координации поведения агентов. В качестве моделей таковых рассматриваются структуры Крипке K =, где R S S, π: S 2, - множество пропозициональных переменных K - множество структур Крипке.

17 Агенты и обучение играм 2 Вводятся понятия: состояния, достижимого из s в смысле транзитивного и рефлексивного замыкания отношения R и пути над R как бесконечной последовательности состояний, удовлетворяющей требованию достижимости каждого очередного состояния из предыдущего

18 Агенты и обучение играм 3 Рассматривается логика ветвящегося времени, интерпретируемая в структурах Крипке. Вводится обычным образом понятие подструктуры Крипке и отношение бисимуляции двух структур. После всего этого социальным законом объявляется некоторое R

19 Агенты и обучение играм 4 Вводятся понятия состояния, достижимого из s в смысле транзитивного и рефлексивного замыкания отношения R и пути над R как бесконечной последовательности состояний, удовлетворяющей требованию достижимости каждого очередного состояния из предыдущего

20 Агенты и обучение играм 5 Исследуется проблема делегирования решений руководителем некоторой совокупности агентов. Руководитель преследует собственные интересы и имеет некоторые цели. Каждый из агентов, кому делегированы решения является независимым в своих предпочтениях.

21 Агенты и обучение играм 6 Проблема делегирования решений состоит в следующем: как делегировать решения таким образом, при котором, если все агенты, которым были делегированы решения, принимают решения рационально, цель руководителя будет достигнута в равновесном состоянии. Эта задача описана в формализме булевых игр. Исследована вычислительная сложность проблемы и некоторых смежных задач.

22 Агенты и обучение играм 7 Задача агрегирования правил в предметных областях, где количество таких правил комбинаторно растет. Предлагается эвристический подход для вычисления агрегатов таких правил.

23 Агенты и обучение играм 8 Большое число работ основано на теоретико-игровых подходах и посвящено поведению коллективов агентов. Предлагается подход к планированию кооперативного поведения многоагентных систем на основе идей частично-упорядоченного планирования и CSP.

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

25 Исполняемая логика Определяется язык для широкого класса диалоговых систем, выполняется сравнение систем в терминах их свойств. Системы диалоговой аргументации специфицируются посредством исполняемых логик с помощью логических правил. Диалоговые правила определяют как меняется состояние диалоговой системы при удалении \добавлении литералов (при переходе в новое состоянии).

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

27 Исполняемая логика α означает такое действие, которым агент вводит литерал α в свое очередное частное состояние Ө α означает такое действие, которым агент удаляет литерал α из своего очередного частного состояния П α означает такое действие, которым агент вводит литерал α в свое очередное общее состояние α означает такое действие, которым агент удаляет литерал α из своего очередного общего состояния.

28 Исполняемая логика Из единиц действий обычным образом конструируются формулы действий. Далее вводятся правила действий и основные правила действий вида: ΦΨ где Φ – формула в классическом смысле, а Ψ – формула действий.

29 Исполняемая логика Доказываются утверждения об эквивалентности такой системы машине с конечным числом состояний, весьма напоминающей конечный автомат: (States, Trans, Initial, Ends, Alphabet).

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

31 Аргументация Рассматривается проблема вынуждения (усиления) аргументов в многоагентных системах. Исследуется поведение агентов в много- агентном диалоге. Предлагаются новые стратегии поведения агентов, в основе которых лежит аргументация, основанная на предположениях. Устанавливается связь между аргументацией и кооперативным планированием.

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

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

34 Дескриптивные логики и базы знаний. Дескриптивные логики с атрибутами и типами даных. Рассматривается расширение одной из дескриптивных логик атрибутами (.А), которые связывают конкретные значения атрибута некоторого типа с объектом. Рассматривается семантика семейства таких логик.

35 Дескриптивные логики и базы знаний Рассматриваются дескриптивные логики знаний и базы действий. Для этого используется вариант логики DL-Lite, действия задаются в виде множества эффектов с условиями. Вводится так называемая база знаний и действий (KAB). КАВ снабжена TBOXом, являющимся, по - существу, вариантом дескриптивной логики DL- Lite, расширенным ядром языка OWL. Кроме того, КАВ содержит действия, меняющие состояние базы знаний, т.е. состояние АBOXа.

36 Дескриптивные логики и базы знаний Исследуется верификация темпоральных и динамических логик в варианте - исчисления первого порядка. Для некоторых даже достаточно простых КАВов такая верификация неразрешима. Тем не менее, можно построить классы КАВов, для которых верификация всё- таки разрешима; при этом они сводятся к моделям с конечным числом состояний.

37 Дескриптивные логики и базы знаний Исследуются задачи апдейтинга противоречивой базы знаний. Для этого определяется новая семантика семейства DL – Lite. База знаний с точки зрения ДЛ состоит из двух компонент: TBox и ABox, где TBox есть множество итенсиональных утверждений, ABox – множество экстенсиональных утверждений.

38 Дескриптивные логики и базы знаний Если TBox непротиворчив, а противоречия возникают при взаимодействии TBoxа и Aboxа; на самом деле это сводится к противоречивости Aboxа, следовательно, речь идет о пополнении Aboxа новыми данными, т.е., по существу о достраивании высказывания из базы знаний таким образом, чтобы высказывания из TBoxа выполнялись на данных Aboxа

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

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

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

42 Естественный язык Предлагается метод «семантического» выделения синонимов непосредственно из семантической сети, которая содержит результаты глубинного семантико-синтаксического анализа

43 Игры и обучение с подкреплением Эвристическое ускорение обучения с подкреплением. Исследовалась проблема ускорения обучения с помощью эвристик. Представлены новые теоретические результаты, касающиеся сходимости и верхнего предела оценки ошибок для класса алгоритмов, основанных на эвристиках. Расширен класс таких алгоритмов тремя новыми. Были проведены эмпирические исследования для традиционных задач управления, которые продемонстрировали, что использование эвристик значительно повышает производительность.

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

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

46 Интеллектуальный анализ данных Рассматривается задача извлечения процессов из данных. В основе лежит поиск зависимостей между работами, основанный на базовых знаниях и прецедентных ограничениях. Предлагается новый подход к уменьшению пространства поиска при извлечении атомарных объектов из баз данных. Подход основан на учёте симметрии данных

47 Интеллектуальный анализ данных Предлагается метод извлечния отношений из биомедицинских данных, таких как заболевания, лекарства, их функциональные эффекты и воздействия. В качестве источников такой информации рассматриваются Wikipedia, MEDCIN, MeSH и SNOMED. Это обнаружение основано на денотативной семантике (entity-level), которая использует свойствах индивидов. Например, аспирин обладает противовоспалительным действием, которое, в свою очередь, способствует лечению боли. Если в системе присутствуют знания о том, что головная боль есть некий тип боли, то можно извлечь пару (аспирин, головная боль) и пополнить ею отношение «лечение».

48 Планирование Рассматривается Марковский процесс с ограничениями на путь как механизм планирования в стохастической среде. Устанавливается связь такого похода с планированием в пространстве состояний. Исследуется реактивное планирование с так называемыми компактными представлениями – нечто вроде фреймов.

49 Планирование Решение задачи планирования часто содержит повторяющиеся подпоследовательности операторов. Такие подпоследовательности можно оформить в виде макросов. В некоторых случаях это дает экспоненциальное уменьшение пространства поиска. Планирование на уровне макросов эквивалентно автоматному планированию.

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

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

52 Планирование Предложен язык планирования OPL, который в противовес PDDL является предметно-зависимым объектно-ориентированным языком. Теоретико-игровой подход к распознаванию конкурирующих планов.

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

54 Пространственые и временные рассуждения Предлагается новый подход к пространственным и темпоральным рассуждениям. Он основан на классическом подходе – на методах удовлетворения качественных ограничений

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

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

57 ЗАКЛЮЧЕНИЕ Происходит трансформация предмета исследования от исследования индивидуального поведения интеллектуальных агентов к исследованию их «социального» поведения. Следующим шагом, видимо, должно явиться моделирование сознания, как продукта культурно- исторической среды. Появляются междисциплинарные связи внутри искусственного интеллекта, что со временем должно привести к формированию единых подходов. Доминирует концентрация усилий на моделировании когнитивных функций versus моделирование когнитивных структур.