General Purpose Solver (Универсальный решатель задач) Большая задача



Скачать 434.4 Kb.
страница1/2
Дата17.02.2017
Размер434.4 Kb.
Просмотров456
Скачиваний0
ТипЗадача
  1   2

Введение

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

Задачи, для которых уже существуют алгоритмы решения, не являются интеллектуальными.

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

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

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

История развития ИИ

1 направление – моделирование биологического прототипа: в 1950-е годы был создан перцептрон (PERCEPTRON) – самоорганизующийся автомат, реализующий сетчатку глаза.

2 – разработка методов, приемов, специализированных устройств и программ для ЭВМ, обеспечивающих решение сложных математических и логических задач, позволяющих автоматизировать отдельные интеллектуальные действия человека:


  • General Purpose Solver (Универсальный решатель задач)

Большая задача -> несколько подзадач -> их решение -> решение всех задач

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



  • Экспертные системы (Dendral) Для хим анализа в 3 этапа

  1. С помощью базы знаний составляется список исходных условий

  2. Список заполняется пользователем

  3. Система генерирует, проверяет, ранжирует и упорядочивает возможные решения, выдает их пользователям

  • Система MYCIN - диагностика инфекционных заболеваний крови. Вероятностные оценки решений 1…10. Система MYCIN могла объяснить ход решения. В дальнейшем система была расширена, что позволяло диагностировать не только заболевания крови.

  • Системы AM (automated mathematician) и Eurisco – спроектированы стенфордским университетом. Разработчики Eurisco попытались преодолеть недостатки AM и позволили генерировать новые правила случайным образом (но исходные данные переопределялись не всегда корректно)

Особенности знаний

  1. Внутренняя интерпретируемость

  2. Структурированность

  3. Связность

  4. Семантическая метрика

  5. Активность

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

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

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

Будем изучать следующие типы отношений:

1)Относительная структуризация -> иерархия информационных единиц

2)функциональные отношения -> процедурная информация(вычисление единицы информации через другие)

3)Каузальные отношения -> причинно-следственные связи

4)Семантические отношения -> все остальные связи

Модель представления знаний – семантическая сеть. Это граф, в вершинах которого находятся информационные единицы. Бывает 2 видов : иерархического типа и все остальные.

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

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

Если система обладает этими 5 особенностями, то это не БД а БЗ.

Модели представления знаний

Декларативная – нет описаний выполняемых действий. Вывод решений основан на процедурах поиска в пространстве состояний.

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

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

Высокая выразительная сила – можно смоделировать что угодно.

Полезны в случаях:

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

2) Вывод в условии ограниченности ресурсов – из-за ограниченности ресурсов, процессы вывода не могут завершиться и должны быть остановлены для получения результатов. Здесь правила определяют дальнейшие действия системы.



Способы описания знаний

1. Логические модели. В основе – формальная система, задаваемая четверкой вида M=

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

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

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

В – множество правил вывода. Применяя их к элементам А, можно получить новые синтаксически правильные совокупности, к которым снова можно применить правила вывода.

Так формируется множество выводимых в данной формальной системе совокупностей.

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

2. Сетевые модели

В зависимости от типов связи между ИС различают:



  • Классифицирующие сети (отношения структуризации)

  • Функциональные сети (функциональные отн.)

  • Сценарии (казуальные отн.)

Если в сетевой модели допускаются связи различного рода - это семантическая сеть.

H=

J – множество ИС

C1,C2….Cn – типы связей

r – связи между ИС (отображение)

3. Продукционные модели

Продукция – правила вывода



4. Фреймовая модель

(имя фрейма:

имя слота1 (значение слота1)

……………………


имя слотаN (значение слотаN))

Значение слота может быть ссылкой на другой слот или фрейм. Конкретизация фрейма – заполнение слотов (значение или имя).



Реализация моделей представления знаний

Реализация логических моделей основана на исчислении предикатов. Предикат – переменная высказывания, истинность и логичность которого зависит от значений его переменных.

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

Терм – всякая константа или переменная.

Квантор – 2 специальных символа  \forall и \exists.

Вхождение переменной в формулу может быть связанным и свободным.

P(x,y)→∀x P(x)

y – свободная переменная (не находится в области действия квантора).

Недостаток: слабая выразительная сила

1) Расширение и модификация логики предикатов



  • применение семантических ограничений в зависимости от особенностей предметной области.

  • использование логики предикатов 2-ого порядка

  • использование модальной логики (необходимость и возможность)

  • использование вероятностной логики (P(1) или P(0) высказывания)

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

2) Разработка глобальных механизмов представления.

Достоинства: синтаксис и интерпретация хорошо определены.



Сетевые модели

P-объект - объект, существующий в реальном мире.

М-объект – представление Р-объекта в базе знаний.

(Существует ли Р-объект, для которого не существует М-объекта? Запросто! Может быть и наоборот).

Способ интерпретации взаимосвязанных Р-объектов называется денотативной семантикой.

Способ интерпретации взаимосвязанных М-объектов называется коннотативной семантикой.

Р-объект по отношению к соответствующему в базе знаний М-объекту называется денотатом или референтом этого М-объекта, а М-объект по отношению к исходному Р-объекту – десигнат.

Терминальный объект – М-объект, который не может быть разложен на более простые объекты. Остальные М-объекты – производные.

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



СМ-фрейм задается в виде ассоциативного списка атрибутов

(имя_атрибута1 значение 1

…………………

имя_атрибутаN значение N)


Необходимо обеспечить уникальную идентификацию отдельных фреймов. Необходимо задать коннотативный смысл фреймов. Он задан, если перечень имен атрибутов постоянен и не совпадает с перечнем имен атрибутов фрейма другого вида. Т.о. целесообразно сопоставлять смысл фрейма с описанием его типа.
Статусы и логическая структура модели предметной области (МПОБ)
1) Замкнутая модель:

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



2) Открытая модель:

Фрейму, отсутствующему в БД присваивается неопределенный статус. Более того, могут использоваться фреймы с градацией истинности.


В МПОБ должны присутствовать специальные процедуры – ассимиляции. Смысл в том, что они соотносят синтаксически правильные фреймы с дедуктивным замыканием модели. Дедуктивное замыкание = дополнение модели всеми выводимыми из неё фактами.
Алгоритм:

Происходит пробное включение фрейма в модель; работа продолжается (в предположении, что ничего плохого не произойдёт). Если противоречие не возникает, то фрейм сохраняется. Иначе – происходит откат и исследуется другой вариант ассимиляции (если есть).

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



T – количество типов фреймов в МПОБ

aj – имя j-го атрибута фрейма Pi

DOM(Pi, aj) – множество допустимых значений атрибута aj фрейма Pi

Ni – число атрибутов фрейма Pi

Конкретизация схемы фрейма – факт.



Экстенсионал фрейма – множество всех фактов данного типа, зафиксированных в БЗ МПОБ.

Множество экстенсионалов образует супер экстенсионал, смысл которого в том, что для каждого состояния МПОБ выполняется следующее утверждение:

EXT(Pi) NEXT(Pi) // правый – супер экстенсионал

Интенсионал фрейма – функция INT(Pi), которая вырабатывает множество фактов

{Fj} NEXT



Таким образом, используя интенсионал, мы виртуализируем утверждения.



Дедуктивное замыкание модели происходит тогда, когда все факты представлены супер экстенсионалами.

Виртуальное утверждение – то, которое выводимо в данной предметной области.

Для фреймов, имеющих интенсиональное описание бессмысленно вводить в БЗ МПОБ конкретизирующие факты. Они либо не несут новой информации, либо противоречат модели.


Использование таксономических структур в сетевых моделях
Таксономическая структура – иерархия абстрактных понятий в виде дерева. При этом корень – наиболее общее понятие, всё что выше – более частные понятия.

При этом любое абстрактное понятие таксономии за исключением наиболее общего наследует все свойства непосредственно своего понятия – предка и добавляет к нему свое уточнение.

Отношения наследника SUP() и предка SUB()– транзитивны.

Достоинства и недостатки ТС:


  • (+): Организация фреймов в виде ТС существенно облегчает доступ к экстенсионалам соответствующих понятий, а также дедукцию при ответах на запросы системы.

Пример:



  • (+): Наличие ТС может служить основой для рассуждений по аналогии – выполнение индуктивных умозаключений. Чем дальше понятия находятся по иерархии ТС, тем меньше между ними общего.

  • (+): Удобство предположения о формально не заданных свойствах некоторых объектов.

  • (+): Когда пользователь взаимодействует с системой, ТС может помочь, давая подсказки и уточнения.

  • (-): Не существует единых принципов построения классифицирующих структур

  • (-): Вопрос о выделении подклассов решается для каждого уровня отдельно.

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

Продукционная модель

Продукционная модель, или модель, основанная на правилах, позволяет представить знания в  виде предложений типа: Если (условие), то (действие).

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

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

      В общем виде продукция может быть представлена выражением следующего вида:

       (i) ; Q ; P ; A => B ; N ,

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

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

А => В - основной элемент продукции, называемый ядром. (если «А» то «В»)

   Р - условие применения ядра продукции. Обычно Р представляется логическим выражениям. Если выражение Р – истина (1), то ядро продукции активизируется.

   N - описание постусловия продукции. Активизируется только в том случае, если ядро продукции реализовалось. Здесь описываются действия и процедуры, которые необходимо выполнить после реализации «В». Выполнение N может происходить не сразу после выполнения ядра продукции.

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

Продукционная модель – комбинация декларативного и процедурального описания. Декларативное – сетевая модель. Процедуральное – продукция.



Классификация ядер продукции

I – детерминированные ядра продукции (если А, то обязательно В)

II - недетерминированные ядра продукции (если А, то возможно В)

I.1 – однозначные (безальтернативные)

I.2 – многозначные (альтернативные)

II.1 – с вероятностной оценкой реализации ядра (если А, то с вероятностью р реализуется В)

II.2 – с лингвистической оценкой реализации ядра (если А, то с большой долей уверенности В)

II.3 – прогнозирующие ядра (если А, то с вероятностью р можно ожидать В)

I.2 делится:

1) С вероятностной оценкой веса - если А, то с вероятностью р=0.5 реализуется В1 , с вероятностью р=0.3 реализуется В2 , с вероятностью р=0.2 реализуется В3. Сумма всех рi должна быть равна 1.

2) С лингвистической оценкой веса – если А, то с большей долей уверенности В1 , с меньшей В2

3) Экспертная оценка веса – если А, то чаще В1 , реже В2



Управление системой продукции

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

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

Возможны два пути решения этой задачи:

1 - централизованное управление - управление  выполнения продукции решения  об актуализации принимаются  специальные системы управления.

2- децентрализованное управление - предполагает учет складывающейся  на этот момент ситуации.

Стратегии для выполнения системы продукции:

1.Принцип  «стопки книг»

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

2.Принцип  «наиболее длинного условия»

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

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

3.Принцип  метапродукций

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

4.Принцип  «классной доски»

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

5.Принцип приоритетного выбора

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

6. Управление по именам.

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



Пример:

а)

б)

в)

г)

Введем формальную грамматику:

(а)=>(б)

(в)=>(б)


(а)=>(г)

После (б) ничего, после (а) => (б), (г). Фронт готовых продукций сузится.



Базовые понятия нейронных сетей

Сети бывают:

Программного исполнения И Аппаратного исполнения

(программная эмуляция) (плата)

Рассматриваем только программного исполнения.



Общие черты: в основе – искусственный нейрон



– входы

– синапсы, характеризующиеся весом.

S состояние нейрона

Yвыход (функция состояния)

Вес синапса – аналог электропроводимости реального синапса.

F – активационная функция, может быть разной.

Наиболее распространены:



  1. Функция единичного скачка



  1. Линейный порог (гистерезис)



  1. Гиперболический тангенс



  1. Сигмоид



α = 0 – горизонтальная линия 0,5

α → ∞ стремится к единичному скачку с Т=0

– легко дифференцируется на всей оси абцисс.

Усиливает слабые сигналы лучше, чем сильные.

Один нейрон не решает задачи. Но из можно объединить в слой, а несколько слоев – в большую сеть.

Однослойный перцептрон из 3-х нейронов:





Y = F (X * W) – в матричном виде.

Число слоев ограничено ресурсами компьютера / платы.

Обучение нейронной сети – процесс нахождения оптимальных значений весовых коэффициентов.

Два метода обучения: с участием и без него.



  1. Есть некий набор тестовых значений Х и эталонных значений У. Сравниваем реальный Y с эталонным, производим корректировку сигналов с учетом разницы (Y – Yэт.)

  2. Весовые коэффициенты меняются на основе входных сигналов и значений синапсов на текущей итерации.

Алгоритмы обучения: детерминистические и стохастические.

  1. Жесткая последовательность действий.

  2. Обучение на основе действия, подчиняющегося некоему случайному процессу.

Классификация нейронных сетей:

  • Бинарные (напр. единичный скачок)

  • Аналоговые (напр. сигмоид, гистерезис – значения в некотором диапазоне)



  • Синхронные – в каждый момент времени свое состояние меняет лишь один нейрон.

  • Асинхронные – состояния меняется сразу у группы нейронов.

Сети можно классифицировать по числу слоев.

Добавляем к



Если убрать F(S), получим

F(S) дает нелинейность исполнения.

–дополнительная нелинейность.

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

Например,

Разработчики решили, что порог – дополнительный вход нейрона, значение которого всего 1, а вес подгоняется.



Если выходные значения >= 0, применять tanh нежелательно.

Большинство нейронных сетей решают задачу классификации.



– прямая делит пространство объектов (решений) на части. Но это не всегда возможно.

Например, решить задачу XOR одним нейроном невозможно (проблема исключающего или). Необходимо минимум 2 слоя.





Алгоритм обучения с учителем

Функция, которая не может быть решена однослойной сетью, называется линейно неразделимой.

Алгоритм обучения сети из одного слоя.

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

Этап 1. Инициализация элементов весовой матрицы небольшими случайными значениями

Этап 2. Подать на входы один из входных векторов, которые сеть должна научиться различать, и вычислить ее выход ,

Этап 3. Если выход получили правильный, переходим к пункту 4.

Иначе – вычисляем разницу

Необходимо скорректировать веса:

t – текущая итерация обучения



– коэффициент скорости обучения (0…1)



Этап 4. Цикл с этапом 2, пока сеть не перестает ошибаться.

Правило: На втором шаге на разных итерациях поочередно в случайном порядке предъявляются все возможные входные вектора.

Алгоритм обратного распространения

Если в многослойной нейронной сети каждый нейрон произвольного слоя связан со всеми аксонами нейронов предыдущего слоя (в случае первого слоя – со всеми входами) – такие нейронные сети называются полносвязными.



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

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

  • Распространение сигналов ошибки от выходов нейронной сети к её входам в направлении, обратном прямому распространению сигналов в обычных режимах работы.



- целевая функция, которую требуется минимизировать.

- реальное выходное состояние нейрона j слоя N (выходного) на её вход образа p

- идеальное выходное состояние этого нейрона.

Суммирование происходит и по выходным нейронам и по образам.

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



– весовой коэффициент связи, соединяющей i-й нейрон слоя n-1 с j-ым нейроном слоя n.

- коэффициент скорости обучения (0…1)



– выход нейрона j

- взвешенная сумма входных сигналов нейрона j

Для гиперболического тангенса:



Алгоритм обратного распространения:

1.Подать образ на вход, рассчитать выход.

2.Рассчитать ẟ выходного слоя.



3.Рассчитать поправки весов.

4.Рекурсивно повторить для остальных слоев.

5.Если ошибка сети большая, то к шагу 1, иначе – конец.

На шаге 1 использовать разные образы.

Для повышения эффективности:



Более 2х внутренних слоев не нужно.



Сd - емкость(количество образов для распознавания).



Узкие места алгоритма:

1.Большие + и – значения весов сместят рабочую точку сигмоидов многих нейронов в область насыщения. Малые величины производных от функции ẟ приведут к остановке обучения.

2.Недостаток градиентного метода – не дает гарантии, что будет найден глобальный, а не локальный минимум целевой функции. Можно кратковременно увеличивать коэффициент обучения и следить за найденными минимумами. Если они одни и те же, то это глобальный минимум.

Программировать нейросети лучше с использованием ООП. Например, класс нейрон, класс сеть и т.д.

BP означает что речь идет о сетях с обратным распространением.

FF – прямопоточная нейронная сеть

Layer – слой нейронов

NetBP – целиком сеть

Нейронные сети обучения без учителя.

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




Поделитесь с Вашими друзьями:
  1   2


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал