35535

Интеллектуальные информационные системы (ИИС)

Книга

Информатика, кибернетика и программирование

Автоматизация процесса информационного поиска основывается на формализации представления смыслового содержания информационного запроса и документов в виде соответственно поискового предписания ПП и поисковых образов документов ПОД. В процессе проведения информационного поиска в ДИПС определяется степень соответствия содержания документов и запроса пользователя путем сопоставления ПОД и ПП. Поэтому подсистема ввода и регистрации документов решает следующие основные задачи: создание электронных копий бумажных документов; подключение...

Русский

2013-09-16

2.29 MB

60 чел.

`

ВВЕДЕНИЕ

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

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

ИИС можно классифицировать по любому признаку. По целевому назначению они подразделяются:

  •  на консультирующие системы;
  •  информационно-поисковые системы;
  •  системы принятия решения;
  •  обучающие системы;
  •  системы тестирования;
  •  системы проектирования и т.д.

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

Все основные прогрессивные свойства ИИС объясняются особенностями ИИ. Ниже даются понятие и основы теории ИИ.

1. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ

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

  1.  сущности;
  2.  отношения между сущностями.

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

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

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

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

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

 Рассуждение по аналогии (Лейбниц).  “Вещь  так относится к вещи , как вещь  к вещи  ”.

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

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

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

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

2. МОДЕЛИ ЗНАНИЙ

 

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

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

Продукционная модель. Основана на правилах  продукции типа

Если условие , то заключение ,

где “Если “, “то “ – операторы; условие (анцедент) - посылка, утверждение, предшествующий, основание; заключение (консеквент) - действие, следствие, последующий, гипотеза.

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

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

Фреймовая модель. Фрейм (рамка) – это единица представления знаний, детали которой (объект, атрибут , значение ) могут быть изменены согласно текущей ситуации.

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

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

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

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

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

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

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

Для имитации нейронов (см. рисунок) каждый входной сигнал  

                    

     

                                                                      

 Искусственный нейрон

умножим на некоторый вес  и просуммируем: . Сумматор имеет один выход . Поскольку любой нейрон  общается с другими – -ми, то =, где  выходной сигнал  -го нейрона. Тогда = и ==. Сигнал  обрабатывается активационным блоком , который выдает . Функция  может быть любой: пороговой, сигнумом, сигмодальной, линейной и т. д.

Для пороговой  нейрон остается неактивным до тех пор, пока его  не достигнет порогового значения . Тогда

=    0, если ,

                1, если >.

Когда = 0, функция  называется сигнум-функцией:

    1,  >0,

=  0,  =0,

      -1, <0.

Сигмодальная (логистическая) сжимающая функция:

    ()=1/(1+).

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

Линейная функция:

  =,

где  - системный параметр (часто =1).

Линейно-пороговая функция:

= 0, ,

                   - , >.

Выбор  зависит от проекта нейронной сети.

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

  •  в определении числа и свойств слоев нейронов,
  •  определении связей внутри и между слоями,
  •  задании всех параметров, , ,….

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

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

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

=+( -),

где ,  - соответственно новая (после обучения) и старая (до обучения) весовые связи нейрона  второго слоя с нейронами  третьего слоя,  - желаемый или правильный выход нейрона  третьего слоя,  - реальный выход нейрона , 01. Если нейрон  посылает правильный выход во внешнюю среду, тогда весовые связи не меняют, и наоборот.

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

3. СЕМАНТИЧЕСКИЕ БАЗЫ ДАННЫХ ИИС

3.1. ОБЩИЕ ПОЛОЖЕНИЯ

Создание баз данных (БД) ИИС во многих моделях является сложным и неудобным для проектировщика процессом, если эти модели не содержат достаточных средств представления смысла данных. От указанного недостатка свободно семантическое моделирование, имеющее два уровня: концептуальное моделирование и моделирование собственно базы данных.

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

Базисным в теории БД является понятие «предметная область», содержащее определения объекта и предмета.

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

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

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

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

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

Вводя пространство состояний, можно рассматривать в нем определенные траектории, или последовательности состояний s0,s1,…,st, в которых находится ПО в моменты времени 0,1,…,t. Члены такой последовательности не могут быть совершенно произвольными, поскольку состояние st обычно связано с предшествующими состояниями. Поэтому ПО можно определить как класс последовательных состояний – траекторий. Совокупность всех общих свойств траекторий называется семантикой предметной области.

3.2. СРЕДСТВА ОПИСАНИЯ ПРЕДМЕТНОЙ ОБЛАСТИ

Средства описания ПО должны достаточно просто интерпретироваться людьми и одновременно быть точными, структурированными и обозримыми (конечными). Кроме того, они должны быть универсальны, чтобы описывать любые предметные области. Поэтому в теории БД говорят о концептуальном, или информационно-логическом, моделировании ПО. Дадим некоторые определения.

 Тип – это понятие, объединяющее все объекты данного вида. В отличие от объекта, существующего в конкретный момент в конкретном месте, тип не имеет пространственно-временной локализации. Типы обеспечивают объединение точек зрения различных пользователей в данной ПО. Тип не является множеством объектов. С объектом он находится не в отношении «часть-целое», а в отношении «абстрактное-конкретное». Каждый тип имеет уникальное имя, например «ПРЕПОДАВАТЕЛЬ». В каждом состоянии предметной области любой объект может иметь один или несколько типов.

Между типами существуют отношения. Отношение частичного порядка обозначается как IS-A: «Если тип Т1 IS-A Т2, то в любой момент времени t объект типа Т1 является объектом типа Т2». Если множество типов конечно, то его можно изобразить в виде ориентированного графа, вершины которого помечены именами типов, а дуги соединяют те вершины, которые находятся в отношении IS-A, см. рисунок.

 

Над типами можно совершать некоторые операции, например равенства, объединения или включения. Эти операции порождают новые типы, семантика которых определяется совместимостью или несовместимостью исходных типов. Весь арсенал операций позволяет представить достаточно сложные структуры предметной области, например: «ЧЕЛОВЕК = МУЖЧИНА ЖЕНЩИНА».

Имя – тип лингвистических объектов. С каждым типом Т связывается одноместный предикат Р(Т) на множестве объектов типа ИМЯ, который выделяет множество имен объектов типа Т.

Отношение INSTANCE-OF – показывает, что одни объекты являются множествами, состоящими из других объектов. Объект о называется простым, если множество объектов о1, для которых name1) INSTANCE-OF name(о), является пустым. В противном случае объект о называется составным. Необходимо заранее разделить объекты на составные и простые.

 Композиционный объект – множество элементов, связанных отношением, отличным от отношения принадлежности. Пример композиционного объекта – дата, состоящая из года, месяца и числа.

 Ограничение целостности. Исключает противоречия в концептуальных моделях. Например, недопустимость включения одного и того же студента о в две различные группы о1 и о2 может быть записана следующим образом:

 оТ, о1Т1, о2Т2, name(о)INSTANCE-OF name(о1),

 name(о) INSTANCE-OF name(о2) ,

   о12,

где утверждается, что включение в разные группы окажется фиктивным, т. к. в этом случае группы о1 и о2 должны быть одним и тем же объектом.

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

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

4. Алгоритмы обработки знаний методами ИИ

4.1. Формализованные правила

Обработка базы знаний (БЗ) методом "до первого успеха". Рассмотрим процедуру достижения некоторой обобщенной цели “установить факт” по методу  "до первого успеха":

  1.  Если факт принадлежит базе фактов (БФ), то “успех”. В противном случае п.2.
  2.  Выполнить цикл обработки базы правил (БП) – п.3.
  3.  Если БП пуста, то “неуспех”. В противном случае п.4.
  4.  Рассмотреть первое правило БП (ПБП) – п.4.1.

4.1. Если все факты условия из ПБП принадлежат БФ, то пп.4.2,

      4.3. Иначе – п.4.4.

  1.  Если результат действия из ПБП есть искомый факт, то

      “успех”. В противном случае пп.4.3 – 4.5.

4.3. Добавить результат действия из ПБП в БФ, если его там нет.

4.4. Определить БП=БП-ПБП.

4.5. Перейти к п.2.

Пример. Рассмотрим следующую  базу знаний:

БЗ:     БФ: A,C,D,E,G,H,K

 БП: 1. K,L,M     I

       2. I,L,J       Q

       3. C,D,E     B

       4. A,B         Q

       5. L,N,O,P Q

        6. C,H         R

        7. R,J,M      S

        8. F,H         B

          9. G            F,

где "," между фактами условных частей правил означает логическое перемножение, а "" - "следует"; любое правило читается как "изследует…".  Задание: установить факт Q. Последовательность решения (по пунктам алгоритма): п.1: QБФ п.2 п.3: БП (не пусто) п.4: ПБП=1БП (первое правило из БП) п.4.1: {L,M}БФ п.4.4: новая база правил БП1=БП -1БП (остаются правила 2,…,9) п.4.5 п.2 п.3: БП1 п.4: ПБП=2БП п.4.1: {I,L,J}БФ п.4.4: БП2=БП1 -2БП (правила 3,…,9) п.4.5   п.2 п.3: БП2   п.4: ПБП=3БП п.4.1: {C,D,E}БФ п.4.2: BQ  п.4.3: новая база фактов БФ1=БФ+B  п.4.4: БП3 = БП2 - 3БП   (правила  4,…,9)  п.4.5    п.2    п.3:  БП3     п.4:

ПБП=4БП п.4.1: {A,B}БФ1 п.4.2: "успех". Очевидно, что БП рассматривается не полностью и  программа не приводит к новым требованиям "установить факт".

Обработка БЗ с перебором всей БП. Алгоритм обработки поясним на примере предыдущей базы знаний с той же целью:

 1. Анализ БФ на предмет наличия Q: QБФ.

 2. Выбор правила 1БП.

 3. Анализ условной части 1БП: {L,M}БФ.

 4. Выбор правила 2БП.

 5. Анализ условной части 2БП: {I,L,J}БФ.

 6. Выбор правила 3БП.

 7. Анализ условной части 3БП: {C,D,E}БФ.

 8. БФ1=БФ+B.

 9. Выбор правила 4БП.

10. Анализ условной части 4БП: {A,B}БФ1.

11. БФ2=БФ1+Q.

12. Выбор правила 5БП.

13. Анализ условной части 5БП: {L,N,O,P}БФ2.

14. Выбор правила 6БП.

15. Анализ условной части 6БП: {C,H}БФ.

16. БФ3=БФ2+R.

17. Выбор правила 7БП.

18. Анализ условной части 7БП: {R,J,M}БФ3.

19. Выбор правила 8БП.

20. Анализ условной части 8БП: FБФ3.

21. Выбор правила 9БП.

22. Анализ условной части 9БП: GБФ.

23. БФ4=БФ3+F.

24. Анализ БФ3 на предмет наличия Q: "успех".

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

 Обработка БЗ с ветвлением (порождение подпроблем). Алгоритм поясним на примере прежней задачи. Для установления факта Q (цель) анализируем БФ и, поскольку  там нет Q, просматриваем правила и находим то действие, результат которого равен Q (2БП). Для установления факта Q требуется установить факты I, L, J (порождение подпроблем или ветвление). Факт Q называется отцом подпроблем I, L, J. Для установления факта I отыскиваем правило с результатом действия I (1БП). Факт K есть в БФ. Факты L, M отсутствуют в качестве результатов действий. Поэтому переходим к следующему правилу, содержащему результат действия Q (4БП). Факт A условной части 4БП есть в БФ. Факт B устанавливается после анализа 3БП , так как  в нем {C,D,E}БФ. Теперь легко устанавливается требуемый факт Q.

 Обработка БЗ с возвратом. Рассмотрим БЗ, состоящую из следующих строк фактов и правил:

С1: рабочий(михаил).

 С2: студент(иван).

 С3: отец(петр,иван).

 С4: отец (михаил,петр).

 С5: отец(иван,виктор).

 С6: отец(,) :- сын(,).

 С7: дед(,) :- отец(,),отец(,).

 С8: сын(михаил,юрий).,

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

  СЦ1=дед(,),рабочий().

Программа решает задачу: существуют ли такие  и , что  являются дедами  и при этом  - рабочие. Процедура поиска решения следующая.

1-й цикл. Разрешаются одна за другой две цели в СЦ1. Вначале отыскивается в БЗ пара для цели дед(,). Сопоставление цели дед(,) и С7 заканчивается успешно путем замены  на  и  на , после чего оба выражения   становятся   идентичными.   Это   делает   унификатор  УНИФ  =  

= (,). Далее преобразуется содержимое СЦ1 в СЦ2 заменой цели дед(,) посылкой (условной частью) из С7:

  СЦ2= отец(,),отец(,),рабочий().

Новый СЦ является резольвентой СЦ1 и С7.

2-й цикл. Первая цель в СЦ2, т.е. отец(,), сравнивается по очереди с С1-С8, и находится унификатор УНИФ=(петр,иван) для отец(,) и С3. Первая цель нового СЦ считается решенной и удаляется из СЦ. К оставшимся целям СЦ2 применяют тот же УНИФ:

  СЦ3=отец(иван,),рабочий(петр).

3-й цикл. Цель отец(иван,) можно сопоставить с С5 из С1-С8 через УНИФ=(виктор):

  СЦ4= рабочий(петр).

4-й цикл. Цель рабочий(петр) в СЦ4 не сопоставляется с С1-С8. Тупик. Осуществляется возврат с восстановлением ближайшего к СЦ4 стека СЦ3, достижение первой цели которого привело к тупику (обозначим  копию СЦ3  как СЦ3.1 - точка возврата ТВ):

  СЦ3.1=отец(иван,),рабочий(петр).

5-й цикл. Сопоставляется цель отец(иван,) в СЦ3.1 уже с С6 через УНИФ=(иван). Получаем новое состояние стека:

  СЦ3.2=сын(,иван),рабочий(петр).

6-й цикл. Цель сын(,иван) в СЦ3.2 не сопоставляется с С1-С8. Тупик. Возврат к ближайшему к СЦ3.2 стеку СЦ3.1:

  СЦ3.1.1= отец(иван,),рабочий(петр).

7-й цикл. Цель отец(иван,) не сопоставляется с другими С7-С8. Тупик. Возврат к ближайшему к СЦ3.1.1=СЦ3.1=СЦ3 стеку СЦ2:

  СЦ2.1= отец(,),отец(,),рабочий().

8-й цикл. Цель отец(,) в СЦ2.1 сопоставляется уже с С4 через УНИФ=(михаил,петр):

  СЦ2.2=отец(петр,),рабочий(михаил).

9-й цикл. Цель отец(петр,) в СЦ2.2 сопоставляется с С3 через УНИФ=(иван), что дает

  СЦ2.3= рабочий(михаил).

10-й цикл. Цель рабочий(михаил) в СЦ2.3 сопоставляется с С1. Стек становится пустым. Ответ: =михаил, =иван.

Прямая цепь рассуждений. Рассмотрим следующую базу правил:

  1.  Если процентные ставки =падают,

то уровень цен на бирже =растет.

  1.  Если процентные ставки =растут,

то уровень цен на бирже =падает.

  1.  Если валютный курс доллара =падает,

то процентные ставки =растут.

  1.  Если валютный курс доллара =растет,

то процентные ставки =падают.

 5.  Если процентные ставки федерального резерва =падают 

     и обращение федерального резерва =добавить,

     то = процентные ставки падают.

С целью формализации записи правил введем следующие переменные:

 INTEREST – изменение процентных ставок (рост или падение),

 DOLLAR валютный курс (падает, растет),

 FEDINT – процентные ставки федерального резерва (растут, падают),

 FEDMON – федеральный резерв (добавление или изъятие),

 STOK – уровень цен на бирже (растет, падает).

Получим такую базу правил:

  1.  Если INTEREST=падает,

то STOK=растет.

  1.  Если INTEREST=растет,

то STOK=падает.

  1.  Если DOLLAR=падает,

то INTEREST=растет.

  1.  Если DOLLAR=растет,

то INTEREST=падает.

  1.  Если FEDINT=падает

и FEDMON=добавить,

то INTEREST=падает.

Образуем следующие структуры:

- список различных переменных (в условиях правил) и их значений,

- очередь переменных,

- указатели на правило и номер условия.

Введем запрос: “Если добавить денег из федерального бюджета, как будет вести себя фондовая биржа?”. Алгоритм поиска решения методом “от причины к следствию” имеет следующий вид:

1. Определить начальное условие – причину. В нашем случае: FEDMON=добавить.

2. Занести переменную условия (FEDMON) в очередь переменных (очередь примет вид: 1. FEDMON), а ее значение (добавить) – в список переменных. Для рассматриваемого примера этот список содержит четыре переменных, из которых INTEREST и DOLLAR пока не могут иметь значения, так как меняют их в разных правилах, а FEDINT и FEDMON точно известны:

INTEREST=…

DOLLAR=…

FEDINT=падает

FEDMON=добавить.

3. Просмотреть список переменных из условных частей правил и найти ту переменную (FEDMON), которая стоит первой в очереди. Если переменная найдена, записать в указатели номер первого найденного правила (номер 5) и номер 1 условия. Если переменная не найдена - пункт 6 алгоритма.

4. Присвоить значения непроинициализированным переменным условной части найденного правила по списку переменных (FEDINT=падает) или запросить, если в списке переменных их значений нет. Проверить все условия правила (в правиле 5 два условия), отражая их номера в указателе (вначале указатель условия будет равен 1, затем 2), и в случае их истинности (у нас оба условия истинны) обратиться к части  “то” правила.

5. Присвоить в списке переменных значение (падает) переменной (INTEREST), входящей в часть “то” рассматриваемого правила, и поместить ее в конец очереди переменных (очередь: 1. FEDMON, 2. INTEREST). Пункты 3, 4, 5 повторить для других правил, в условных частях которых встречается та же переменная очереди (FEDMON, в нашем примере после 5 других правил нет).

  1.  Удалить переменную, стоящую в начале очереди (FEDMON).

7. Закончить процесс рассуждений, как только опустеет очередь. Если в очереди есть переменные (INTEREST), вернуться к шагу 3 алгоритма.

На шаге 3 для нашего примера переменная INTEREST встречается в правилах 1, 2. Но найденное на шаге 5 значение падает соответствует только правилу 1. Получим STOK=растет. Очередь переменных: 1. INTEREST, 2. STOK. Переменная INTEREST удаляется из очереди. Очередь: 1. STOK. Переменной STOK нет в условных частях правил, поэтому поиск завершен. Ответ: 1. Процентные ставки падают. 2. Уровень цен на бирже растет.

Обратная цепь рассуждений. Рассмотрим следующую базу правил:

Если DEGREE=нет, то POSITION=нет.

Если DEGREE=да, то QUALIFY=да.

Если DEGREE=да и DISCOVERY=да,

то POSITION=научный работник.

Если QUALIFY=да и GRADE<3.5 и EXPERIENCE>=2,

то POSITION=инженер по эксплуатации.

Если QUALIFY=да и EXPERIENCE<2,

то POSITION=нет.

Если QUALIFY=да и GRADE>=3.5,

то POSITION=инженер-конструктор,

где

 DEGREE – ученое звание (да, нет),

 DISCOVERY – открытие (да, нет),

 EXPERIENCE – стаж работы,

 GRADE – средний балл,

 POSITION – должность,

 QUALIFY – возможность принятия на работу.

Введем запрос: “Какую работу предложить данному посетителю, имеющему ученую степень, не сделавшему никакого открытия, со средним баллом 3 и стажем работы 4 года?”  Для ответа образуем структуры:

  •  упорядоченного списка переменных вывода (список логических выводов) с номером правила: 1. POSITION,  2. QUALIFY,  

3. POSITION,  4. POSITION,  5. POSITION,  6. POSITION;

  •  списка неповторяющихся переменных и их значений из условных частей правил (список переменных условия), не встречающихся в следствиях, с учетом запроса:

DEGREE=да,

DISCOVERY=нет,

    EXPERIENCE=4,

    GRADE=3;

  •  стека пар указателей номеров правил и условий.

Поиск ответа методом “от цели к фактам ”имеет следующий порядок.

1. Определить  неизвестную переменную логического вывода (здесь -переменная запроса POSITION).

2. В списке логических выводов искать первое вхождение этой переменной (1. POSITION). Если переменная найдена, в указатели ввести номер вхождения-правила (в нашем случае это 1) и установить номер условия  1. Если переменная не найдена, выдать “ответа нет”.

3. Присвоить значения всем переменным условий найденного правила, наращивая номера условий  (для нашего примера условие одно: известно, что DEGREE=да).

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

5. Если какая-либо переменная условий найденного правила входит в список переменных логического вывода (в рассматриваемом  примере такого нет), поместить в стек указателей номер  ближайшего правила, в логический вывод которого она входит, установить номер условия 1 и перейти к шагу 3.

6. Если из правила нельзя определить значение  переменной логического вывода (POSITION=?, так как в нашем примере правило 1 противоречиво), удалить соответствующий ему  элемент (номер правила 1) из стека указателей и   по списку переменных логического вывода продолжить поиск следующего  правила (3) с этой переменной логического вывода (POSITION).

7. Если новое правило (3) найдено, заполнить стек указателей новыми данными (номер правила 3, номер условия 1) и  перейти к шагу 3 (переменная первого условия правила 3: DEGREE=да, второго условия: DISCOVERY=нет). Правило 3 противоречиво. Из стека указателей удаляем номер этого правила. По списку переменных логических выводов переходим к правилу 4 и шагу 3. Переменная QUALIFY первого условия правила 4 входит в список переменных логических выводов. Добавляем в стек указателей пару “правило 2, условие 1”, сохраняя предыдущие данные - ”правило 4, условие 1”. Переходим к шагу 3: DEGREE=да, QUALIFY=да. Удаляем пару “правило 2, условие 1” из стека указателей, обрабатываем предыдущую пару  “правило 4, условие 1”: QUALIFY=да. Увеличиваем номер условия: “правило 4, условие 2”: GRADE=3, т.е GRADE <3.5. Следующее условие: EXPERIENCE=4, т.е. EXPERIENCE>=2.

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

9. Определить значение переменной из правила, расположенного в начале    стека    логических    выводов    (правило 4: POSITION=инженер по эксплуатации); правило 4 из стека удалить. Если среди переменных условий есть еще переменные логического вывода (в нашем примере их больше нет), увеличить значение номера условия и перейти к шагу 3. Если в условиях больше нет переменных логического вывода, сообщить окончательный ответ (POSITION=инженер по эксплуатации).

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

4.2. ЭВРИСТИЧЕСКИЕ  МЕТОДЫ  ПОИСКА  РЕШЕНИЙ

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

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

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

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

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

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

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

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

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

Основные отличия генетических алгоритмов следующие.

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

Во-вторых, для поиска генетический алгоритм использует несколько точек поискового пространства одновременно, а не переходит от точки к точке. Это позволяет преодолеть опасность попадания в локальный экстремум целевой функции, если она не является унимодальной (одноэкстремальной).

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

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

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

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

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

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

Критериями останова генетического алгоритма являются следующие события:

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

На рис. 4.1 дана блок-схема генетического алгоритма.

В основе оператора отбора лежит принцип «выживает сильнейший». Например, вероятность участия в процессе размножения может быть вычислена как

     =/,

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

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

Рассмотрим простейший оператор скрещивания следующих строк:

   X1X2…Xn;                 Y1Y2…Yn.

На первом этапе равновероятно выбирается натуральное число k от 1 до n-1. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки:

 X1X2…XkXk+1…Xn;  Y1Y2…YkYk+1…Yn.

На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с k+1 по n-ный. Так получаются две новых строки, которые наследуют частично свойства обоих родителей:

 X1X2…XkYk+1…Yn;  Y1Y2…YkXk+1…Xn.

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

    K=(1-P)N,

 

 

 

где Р – вероятность применения оператора скрещивания, N – размер популяции.

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

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

Рассмотрим следующий очевидный пример. Пусть имеется набор чисел от 0 до 31 и функция, определенная на этом наборе f(x)=x. Требуется найти максимальное значение функции 31.

В качестве фенотипа используем двоичное представление аргументов. Генотип – строка из 5 бит. Целевой функцией будет сама рассматриваемая функция, аргументом которой является число, чье двоичное представление использует алгоритм.

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

 На основе равномерного распределения создадим исходную популяцию – табл. 4.1.

                    Исходная популяция       Таблица 4.1

строки

Код

Значение целевой функции

Вероятность участия в процессе размножения

1

01011

11

11/43

2

10010

18

18/43

3

00010

2

2/43

4

01100

12

12/43

Пусть оператор отбора выбрал для производства потомков две пары строк (1,2) и (2,4). Работа оператора скрещивания иллюстрирована табл. 4.2   (разбиение на подстроки – независимое).

 Работа оператора скрещивания      Таблица 4.2

№ строки

Родители

Потомки

Значение целевой функции для потомков

1

0 1011

00010

2

2

1 0010

11011

27

3

100 10

10000

16

4

011 00

01110

14

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

     Работа оператора мутации     Таблица 4.3

строки

Код

Значение целевой функции

Исходная популяция

1

01011

11

2

10010

18

3

00010

2

4

01100

12

Порожденные потомки

5

00010

2

6

11011

27

7

10001

17

8

01110

14

Оператор редукции далее сократит популяцию до исходного числа особей, исключив из нее те, чье значение целевой функции минимально. Исключены будут строки 1, 3, 4 и 5. Получим табл. 4.4. Уже на этом шаге работы генетического алгоритма видны его положительные результаты. Если первоначально среднее значение целевой функции было 10.75, а ее минимальное значение составляло 2, то в первом же поколении среднее значение выросло до 19, а минимальное значение – до 14.

Работа оператора редукции            Таблица  4.4

№ строки

Код

Значение целевой функции

Вероятность участия в процессе размножения

1

10010

18

18/76

2

11011

27

27/76

3

10001

17

17/76

4

01110

14

14/76

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

проезда имеет вид:

0 4 6 2 9

4 0 3 2 9

6 3 0 5 9

2 2 5 0 8

9 9 9 8 0

Решение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов. Значение целевой функции будет равно стоимости всей поездки (одним из оптимальных решений является маршрут 514235 стоимостью 25). Оператор отбора аналогичен тому, который использовался в предыдущем примере.

В качестве оператора скрещивания выберем процедуру двухточечного скрещивания. Например, пусть есть две родительские перестановки: 12345 и 34521. Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая – между четвертым и пятым: 12345, 34521. На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва (452, 234) с потерей остальных чисел (вместо них поставим звездочки): *452*, *234*. На втором этапе –  звездочки заменяются числами из исходной родительской перестановки, начиная со второго числа фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в исходной перестановке 12345 начальным числом является 3. После его подстановки в  *452* на место первой звездочки получим 3452*, где уже есть числа 4, 5, стоящие после 3 в исходной последовательности 12345. Пропускаем их и переходим к началу исходной последовательности: число 1 можно использовать для обмена, так как его нет в новой перестановке 3452*. Получаем вместо исходной последовательности 12345 ряд 34521. Также из 34521 и *234* получаем последовательно: 5234* и 52341.

Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному закону. Вероятность мутации 0.01. Размер популяции выберем равным 4. Исходная популяция представлена в таблице 4.5 (f(x) учитывает проезд из последнего города в первый).

     Исходная популяция              Таблица 4.5

№ строки

Код

Значение целевой функции f(x)

Вероятность участия в процессе размножения

1

12345

29

32/122

2

21435

29

32/122

3

54312

32

29/122

4

43125

32

29/122

Пусть для скрещивания были выбраны следующие пары: 1,3 и 2,4. В результате были получены потомки, представленные в табл. 4.6.

     Работа оператора скрещивания      Таблица 4.6

№ строки

Родители

Потомки

Значение целевой функции для потомков

1

12345

54312

32

3

54312

12354

мутация 13254

28

2

21435

43125

32

4

43125

21435

29

 

Пусть для потомка 12354 сработал оператор мутации и обменялись местами числа 2 и 3. В данном случае строка 12354 изменилась и приняла значение 13254. Популяция первого поколения после отсечения худших особей в результате работы оператора редукции приняла вид, представленный в табл. 4.7.

    Работа оператора редукции             Таблица 4.7

строки

Код

Значение целевой функции

Вероятность участия в процессе размножения

1 (1)

12345

29

28/115

2 (2)

21435

29

28/115

3 (н)

13254

28

29/115

4 (н)

21435

29

28/111

Пусть для получения второго поколения были выбраны следующие пары строк: 1,4 и 2,3. И в результате были получены потомки, показанные в табл. 4.8.

     Работа оператора скрещивания      Таблица 4.8

№ строки

Родители

Потомки

Значение целевой функции для потомков

1

12345

21435

29

4

21435

12345

29

2

21435

13452

32

3

13254

21354

29

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

    Работа оператора редукции             Таблица 4.9

№ строки

Код

Значение целевой функции

Вероятность участия в процессе размножения

1 (1)

12345

29

28/111

2 (2)

21435

29

28/111

3 (3)

13254

28

29/111

4 (н)

21354

29

28/111

Таким образом, после двух итераций значение целевой функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30.5 на 28.75, а общее количество - с 122 на 111. Налицо улучшение популяции.

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

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

 F(Sym) = 1/(1+e-PSum),      Sum = xiwi ,

где n – количество входов нейрона;  xi – значение на i-м входе; wi – вес i-го входа; P- параметр функции активации, влияющей на ее крутизну (чем больше P, тем ближе сигмодальная функция приближается к пороговой).

Таким образом, векторы примеров будут иметь вид (х1, х2, х3, y1),  где xi 

– входные значения, а y1 – эталонное выходное значение.  

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

где k – количество примеров;– значение выхода нейронной сети для j-го примера; y1j- эталонное значение выхода нейронной сети для j-го примера.

Таким образом, целевая функция будет представлять собой максимальное для  набора примеров относительное отклонение от эталонного значения, выраженное в процентах. Чем меньше значение целевой функции, тем сеть лучше. Работу алгоритма можно остановить, если для одной из особей значение целевой функции будет равно, например, 0.1. Критерием останова может быть также число поколений. Для обучения нейронной сети размер популяции выбирается достаточно большим, например 100.

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

w11

w12

w13

P1

w21

w22

w23

P2

w31

w32

P3

Для элементов хромосомы – генов – введем ограничения, обусловленные природой нейросетей: -1  wij  1 и Pi  0.

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

 В качестве оператора мутации будем использовать случайное изменение значений весов и параметра функции активации для каждого нейрона на случайную величину. Вероятность мутации 0.01. Причем одновременно будет изменяться параметр функции только для одного нейрона, и для каждого нейрона будет изменяться один из входных весов. Какие конкретно веса и параметры будут меняться, определяется по равномерному закону. Например, мутация может быть следующей: значение P2 увеличивается на 0.1; значение w13 уменьшается на 0.05; w21 – уменьшается на 0.01; w31 – увеличивается на 0.05.

Исходная популяция будет формироваться на основе равномерного распределения для каждого элемента хромосомы.

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

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

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

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

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

5. ПРОБЛЕМА Распознавания образов

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

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

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

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

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

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

Примером задач распознавания является распознавание 26 символов латинского алфавита. В качестве датчика предполагается система, которая выполняет оцифровку каждого символа, находящегося в стандартном поле шаблона размером 57. Например, символ A может быть представлен рис. 5.1, а и б [11, с.199].

Проектируемая нейронная сеть должна точно распознавать 26 идеальных векторов, каждый из которых содержит 35 элементов, и с максимальной точностью воспроизводить зашумленные векторы. Соответственно на вход нейросети поступает вектор с 35 элементами; вектор выхода содержит 26 элементов, только один из которых равен 1, а остальные – 0. Таким образом, нейронная сеть имеет 35 входов и 26 нейронов в выходном слое. Для решения задачи достаточно выбрать двухслойную сеть с логарифмическими сигмодальными функциями активации в каждом слое. Структурная схема такой сети в обозначениях пакета МАТЛАБ показана на рис. 5.2.

                                                                                                                                                                                                                                                                                     

 

 

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

Шаблон для рассматриваемого символа A можно получить с помощью таких МАТЛАБ-операторов:

[alphabet, targets] = prprob;

i = 2;

ti = alphabet(:, i);

letter{i} = reshape(ti, 5, 7)’;

letter{i}

что дает:

 ans =

 0  0  1  0  0

 0  1  0  1  0

 0  1  0  1  0

 1  0  0  0  1

 1  1  1  1  1

 1  0  0  0  1

 1  0  0  0  1

Для инициализации сети вызывается М-файл prprob, который формирует массив векторов входа alphabet размера 3526 с шаблонами символов алфавита и массив целевых векторов targets:

[alphabet, targets] = prprob;

[R,Q] = size(alphabet);

[S2,Q] = size(targets);

 Двухслойная нейронная сеть создается с помощью команды newff:

S1 = 10;

net = newff (minmax (alphabet), [S1 S2], {‘logsig’ ‘logsig’}, ‘traingdx’);

net.LW{2,1} = net.LW{2,1}*0.01;

net.b{2} = net.b{2}*0.01;

 Структура сети вызывается оператором gensim(net) – рис.5.3.

 

Структура блока Neural Network показана на рис.5.4:

Структура блоков Lauer 1 и Lauer 2 представлена на рис. 5.5, 5.6.

 Первоначально сеть обучается в отсутствии шума с максимальным числом циклов обучения 5000 либо до достижения допустимой средней квадратичной погрешности, равной 0.1 (рис. 5.7):

 P = alphabet;

T = targets;

net.performFcn = ‘sse’;

net.trainParam.goal = 0.1;

net.trainParam.show = 20;

net.trainParam.epochs = 5000;

net.trainParam.mc = 0.95;

[net,tr] = train(net,P,T); % Рис.5.7

Обучение нейронной сети, малочувствительной к помехам, проведем с применением двух идеальных и двух зашумленных копий векторов алфавита. Целевые векторы состоят из четырех копий. Зашумленные векторы имеют шум со средним значением 0.1 и 0.2.  Это позволит сети правильно распознавать зашумленные символы и в то же время хорошо распознавать идеальные векторы.

При  обучении с шумом максимальное число циклов обучения сократим до 300, а допустимую погрешность увеличим до 0.6 (рис.5.8):

netn = net;

netn.trainParam.goal = 0.6;

netn.trainParam.epochs = 300;

T = [targets targets targets targets];

for pass = 1:10

P = [alphabet, alphabet, …

 (alphabet + randn(R,Q)*0.1), …

 (alphabet + randn(R,Q)*0.2)];

 [netn,tr] = train(netn,P,T);

end % Рис.5.8

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

 

 netn.trainParam.goal = 0.1; % Предельная среднеквадратичная погрешность

 netn.trainParam.epochs = 500; % Максимальное количество циклов обучения

 net.trainParam.show = 5; % Частота вывода результатов на экран

 [netn,tr] = train(netn,P,T);

 Эффективность нейронной сети будем оценивать следующим образом. Рассмотрим две структуры нейронной сети: сеть 1, обученную на идеальных последовательностях, и сеть 2, обученную на зашумленных последовательностях. Проверка функционирования производится на 100 векторах входа при различных уровнях шума.

Тестирование реализуем следующим образом. Шум со средним значением 0 и стандартным отклонением от 0 до 0.5 с шагом 0.05 добавляется к векторам входа. Для каждого уровня шума формируется 100  последовательностей для каждого символа и вычисляется выход сети. Выходной сигнал обрабатывается М-функцией compet с той целью, чтобы выбрать только один из 26 элементов вектора выхода. После этого оценивается количество ошибочных классификаций и вычисляется процент ошибки. Ниже приведен сценарий appcr1, который выполняет эти операции:

noise_range = 0: .05: .5;

max_test = 100;

network1 = [ ];

network2 = [ ];

T = targets;

% выполнить тест

for noiselevel = noise_range

errors1 = 0;

errors2 = 0;

for i=1:max_test

P = alphabet + randn(35,26)*noiselevel;

% Тест для сети 1

 A = sim(net,P);

AA = compet(A);

errors1 = errors1 + sum(sum(abs(AA-T)))/2;

% Тест для сети 2

 An = sim(netn,P);

AAn = compet(An);

errors2 = errors2 + sum(sum(abs(AAn-T)))/2;

echo off

end

% Средние значения ошибок (100 последовательностей из 26 векторов целей)

 network1 = [network1 errors1/26/100];

network2 = [network2 errors2/26/100];

end

 График погрешностей сети от уровня входного шума формируется так:

 plot(noise_range, network1*100, ‘- -‘, noise_range, network2*100);

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

6. АВТОМАТИЗИРОВАННОЕ  ФОРМИРОВАНИЕ  ЗНАНИЙ

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

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

Одна из форм индуктивного обучения предусматривает демонстрацию примеров двух типов – тех, которые соответствуют концепту «позитивные экземпляры», и тех, которые ему не соответствуют («негативные экземпляры»). Задача программы обучения – обеспечить выявление или конструкцию подходящего концепта, который включал бы все позитивные экземпляры и не включал ни одного негативного. Такой вид обучения называется обучением концептам. Рассмотрим набор исходных данных, представленный табл. 6.1 (последний столбец предстоит заполнить).

Предположим, программа обучается концепту «Немецкий автомобиль». Тогда позитивными экземплярами для этого концепта будут BMW 316 и VW Cabriolet (см. последний столбец), а остальные – негативными. Если же целевой концепт – “Американский автомобиль старой марки”, то позитивными экземплярами будут Thunderbird Raodster и Chevrolet Bel Air, а остальные – негативными.

     Обучающая выборка примеров       Таблица 6.1

Экземпляр

Страна-изготовитель

Размер

Старая модель

Позитивный/

негативный

Oldmobile Cutlass

США

Большой

Нет

Негативный

BMW 316

Германия

Малый

Нет

Позитивный

Thunderbird Raodster

США

Малый

Да

Негативный

VW Cabriolet

Германия

Малый

Нет

Позитивный

Rolls Rouce Corniche

Великобрита -ния

Большой

Да

Негативный

Chevrolet Bel Air

США

Малый

Да

Негативный

 

Необходимо предъявить программе и позитивные, и негативные экземпляры. В противном случае выводы, которые она сделает, будут далеки от требуемых. Так, в первой из рассмотренных задач и BMW 316 и VW Cabriolet являются малыми машинами, поэтому если программе не предъявить в качестве негативного экземпляра Chevrolet Bel Air, то она может сделать вывод (коль скоро мы предполагаем у нее умственные способности), что концепт “Немецкий автомобиль” совпадает с концептом “Малый автомобиль”. Аналогично, если во второй задаче не будет представлен негативный экземпляр Oldmobile Cutlass, то программа может посчитать концепт “Американский автомобиль старой марки” совпадающим с более общим концептом “Американский автомобиль”. Таким образом, с формальной точки зрения для любого множества данных обучающей выборки, в котором выделены и положительные, и отрицательные экземпляры, нужно специфицировать некоторый необходимый набор атрибутов, имеющий отношение к обучаемым концептам, и запись каждого экземпляра должна содержать все значения этих атрибутов.

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

Пусть, например, обучающая выборка имеет вид {Cadillac Seville, Oldsmobile Cutlass, Lincoln Continental}. При этом каждый экземпляр выборки имеет атрибуты «размер, уровень комфорта и расход топлива». Тогда в результате выполнения задачи обобщения дескрипторов программа сформирует описание, представляющее набор значений дескрипторов, характерный для данного класса объектов: {большой, комфортабельный, прожорливый}.

Отличие между двумя методиками состоит в следующем:

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

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

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

Здесь даны атрибуты «наблюдение, влажность, ветрено». Листья деревьев промаркированы классами П (например, позитивный концепт – выйти на прогулку), Н (например, негативный концепт – остаться дома). Дерево можно прямо транслировать в общее правило:

Если  наблюдение = облачно

  

  наблюдение = солнечно

  влажность = нормально

  

  наблюдение = дождливо

  ветрено = нет,

то   П.

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

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

 Обучающая выборка дерева решения      Таблица 6.2

Номер

Наблюдение

Температура

Влажность

Ветрено

Класс

1

Солнечно

Жарко

Высокая

Нет

Н

2

Солнечно

Жарко

Высокая

Да

Н

3

Облачно

Жарко

Высокая

Нет

П

4

Дождливо

Умеренно

Высокая

Нет

П

5

Дождливо

Холодно

Нормальная

Нет

П

6

Дождливо

Холодно

Нормальная

Да

Н

7

Облачно

Холодно

Нормальная

Да

П

8

Солнечно

Умеренно

Высокая

Нет

Н

9

Солнечно

Холодно

Нормальная

Нет

П

10

Дождливо

Умеренно

Нормальная

Нет

П

11

Солнечно

Умеренно

Нормальная

Да

П

12

Облачно

Умеренно

Высокая

Да

П

13

Облачно

Жарко

Нормальная

Нет

П

14

Дождливо

Умеренно

Высокая

Да

Н

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

Один из алгоритмов (поскольку рассматривается автоматизированное обучение при минимальном участии экспертов) формирования дерева решения по обучающей выборке использует последовательность тестовых процедур  к каждому объекту , с помощью которых множество  элементов выборки разделяется на подмножества {,,…,}, содержащие объекты только одного класса такие, что для значение () =  (рис.6.2).

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

7. ИНФОРМАЦИОННО-ПОИСКОВЫЕ СИСТЕМЫ

7.1. общие положения

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

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

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

В процессе проведения информационного поиска в ДИПС определяется степень соответствия содержания документов и запроса пользователя путем сопоставления ПОД и ПП. На основе такого сопоставления принимается решение о выдаче (признан релевантным) или невыдаче документа.

Решение о выдаче или невыдаче документа в ответ на запрос принимается на основе некоторого набора правил, по которому данной ДИПС определяется степень смысловой близости между ПОД и ПП. Такой набор правил называется критерием смыслового содержания (КСС). Очевидно, что КСС определяет формальную релевантность. Фактическую релевантность может определить только сам потребитель.

 

7.2. СТРУКТУРА ДИПС

В состав ДИПС, как правило, входят четыре основные подсистемы: ввода и регистрации, обработки, хранения и поиска – рис. 7.1.

 

 

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

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

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

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

Все ПОД сохраняются в индексе. Логически индекс представляет собой таблицу, строки которой соответствуют документам, а столбцы – информационным признакам, на основе которых строится ПОД. В ячейках таблицы могут храниться либо 1, либо 0 – в зависимости от наличия или отсутствия данного признака в данном документе. Чтобы не хранить все ее значения, часто используют свертку таблицы по строкам и столбцам. Такую форму хранения называют прямой или инверсной соответственно.

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

7.3. НЕДОСТАТКИ ЕСТЕСТВЕННОГО ЯЗЫКА

 

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

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

Во-вторых, ЕЯ обладает семантической неоднозначностью. Семантическая неоднозначность возникает в основном из-за синонимии (тождественность значений) и многозначности слов ЕЯ. Синонимами ЕЯ являются как отдельные слова, так и словосочетания.

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

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

7.4. ИНФОРМАЦИОННО-ПОИСКОВЫЕ ЯЗЫКИ

 

Трудности использования ЕЯ в качестве основного средства представления информации в ДИПС приводит к необходимости применения искусственных языковых средств.

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

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

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

Частный случай классификационного ИПЯ - рубрикатор, лексическими единицами которого являются названия тематических рубрик. В общем под рубрикатором понимают ориентированный граф, состоящий из независимых деревьев (тем). Листья деревьев называют рубриками – объектами, инкапсулирующими знания о конкретных фрагментах данной предметной области. Как правило, рубрикатор формируется экспертами на основе их знаний о предметной области с учетом информационных потребностей пользователей.

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

В отличие от классификационных ИПЯ в дескрипторных ИПЯ лексические единицы (ЛЕ) заранее не связаны никакими текстуальными отношениями. Сложные синтаксические конструкции создаются в таких языках путем объединения (координации) во время процедуры представления смыслового содержания документов. Готовых предложений или фраз в таких языках нет, поэтому отсутствуют ограничения на сложные понятия. Такие ИПЯ называют посткоординируемыми, поскольку координация между словами предложения возникает во время его записи.

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

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

7.5. ОБРАБОТКА ВХОДЯЩЕЙ ИНФОРМАЦИИ

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

При использовании в ДИПС ИПЯ без грамматики и без контроля по словарю говорят о полнотекстовом индексировании.

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

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

7.6. ЛИНГВИСТИЧЕСКИЙ АНАЛИЗ

Обычно под лингвистическим анализом понимают морфологический и синтаксический анализ.

Цель морфологического анализа состоит в получении основ (путем  отсечения окончаний) словоформ со значениями грамматических категорий (например, часть речи, род, число, падеж).

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

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

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

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

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

Любые средства синтаксического анализа состоят из двух частей: базы знаний о конкретном языке и собственно алгоритма синтаксического анализа. Источником грамматических знаний являются данные, полученные в результате морфологического анализа, а также различные таблицы, которые априорно заполнены стандартным образом и представляют собой результат эмпирической обработки текстов на ЕЯ человеком с целью выделения определенных закономерностей, необходимых для проведения синтаксического анализа. Основу таких таблиц составляют наборы валентностей – списки ЛЕ с указанием для каждой из них всех возможных вариантов связей с другими ЛЕ на ЕЯ (потенциальные связи).

7.7. АВТОМАТИЧЕСКОЕ ИНДЕКСИРОВАНИЕ

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

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

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

Основу методов автоматического индексирования составляет присваивание весовых коэффициентов терминам на основе статистических характеристик.

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

Пусть - число документов, в которых встречается термин . Тогда величина log(/) может служить индикатором того, является ли термин  дискриминатором документов .

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

    = log(/).

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

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

     =.

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

7.8. АВТОМАТИЧЕСКОЕ РУБРИЦИРОВАНИЕ

Различают два способа рубрицирования: основанное на знаниях и основанное на примерах.

7.8.1. РУБРИЦИРОВАНИЕ, ОСНОВАННОЕ НА ЗНАНИЯХ

 

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

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

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

  •  может ли данная группа слов-терминов быть включена в тезаурус;
  •  является ли данный термин дескриптором или синонимом другого дескриптора;
  •  как должны быть описаны отношения данного термина.

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

Тезаурус и базы данных имеют одну структуру и состоят из следующих частей:

1) дескрипторов (существительное или именная группа), которые соответствуют понятиям или конкретным объектам;

2) совокупности текстовых входов (по каждому дескриптору) или синонимов (существительные, прилагательные или группы существительных). Одно слово может быть синонимом различных дескрипторов. Устранение смысловой неоднозначности производится во время автоматической обработки документа;

3) отношения между дескрипторами внутри каждой базы данных (широкий или узкий термин, связанный термин и т.д.);

4) отношения между дескрипторами различных баз данных. В данном случае добавляется отношение «равенство термина», которое появляется, когда базы данных содержат дескрипторы, соответствующие одному объекту.

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

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

Существует два типа представления рубрик последовательностью опорных дескрипторов в виде булевских нормальных форм:

  •  дизъюнкция опорных дескрипторов – D1D2Dn;
  •  коньюнкция дизъюнкций опорных дескрипторов – (D11D12D1n)( Dm1Dm2Dmk).

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

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

Развитием данной технологии является описание рубрики на ЕЯ.

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

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

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

На втором этапе принимается решение о принадлежности текста к конкретной рубрике. Учитывают понятия, выделенные на первом этапе из текста с возможными весами. Решение принимается на основе правил рубрицирования, которые, так же как и определения понятий, формулируются экспертом заранее с использованием языка правил. Пример:

(if

test:    (or [australian-dollar-concept]

          (and [dollar-concept]

                  [australia-concept]

                  (not [us-dollar-concept])

 ……………………….

 …))

action: (assign australian-dollar-category))

 

Совокупность определений и правил рубрицирования составляет базу правил. Процесс рубрицирования по продукционным моделям может быть представлен рисунком  7.2.

7.8.2. РУБРИЦИРОВАНИЕ, ОСНОВАННОЕ НА ПРИМЕРАХ

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

Выделяют статистические и нейросетевые методы рубрицирования.

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

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

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

  = log,

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

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

    ,

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

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

К достоинством метода относятся:

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

Недостатком метода является относительно низкое качество рубрицирования.

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

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

7.9. ПОИСК  ТЕКСТОВОЙ  ИНФОРМАЦИИ

7.9.1. МОДЕЛИ  ПОИСКА ИНФОРМАЦИИ

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

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

Рассмотрим некоторые модели поиска информации.

Булева модель представляет документы с помощью набора терминов, присутствующих в индексе, каждый из которых рассматривается как булева переменная. При наличии термина в документе соответствующая переменная принимает значение True. Присваивание  терминам весовых  коэффициентов не допускается. Запросы формулируются как произвольные булевы выражения, связывающие термины с помощью стандартных логических операций OR или NOT. Мерой соответствия запроса документу служит значение статуса выборки RSV. В булевой модели RSV равно либо 1 (документ релевантен), если для данного документа вычисление выражения запроса дает True, либо 0 в противном случае.

Хотя такая модель позволяет пользователям вводить в запросы произвольные сложные выражения, эффективность поиска невелика. К тому же ранжировать результаты невозможно, так как все найденные документы имеют одинаковые RSV, а терминам нельзя присвоить весовые коэффициенты. Могут быть и ошибки. Например, запрос, содержащий десять терминов, связанных операцией AND, не обнаружит нужный документ, содержащий меньшее количество терминов. В указанном случае необходима обратная связь с пользователем.

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

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

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

7.9.2. МЕТОДЫ ОБРАТНОЙ СВЯЗИ С ПОЛЬЗОВАТЕЛЕМ

 

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

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

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

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

7.10. ОЦЕНКА КАЧЕСТВА ДИПС

Так как в ПОД и ПП отображается лишь основное смысловое содержание поступающих сообщений в сокращенном виде, любой реальной ДИПС присущи два вида ошибок:

  •  ошибки 1-го рода (пропуск цели) – невыдача потребителю фактически релевантных его запросу документов;
  •  ошибки 2-го рода (ложная тревога) – выдача потребителю

документов, которые не отвечают поставленному запросу.

Указанные ошибки обусловливают разбиение всего массива документов на 4 подмассива - выданных релевантных документов А числом a, выданных нерелевантных  документов В числом b, невыданных релевантных документов С числом с, невыданных нерелевантных документов D числом d. Последние значения определяют следующие показатели эффективности ДИПС.

  1.  Коэффициент полноты, характеризующий долю выданных релевантных документов,

p = a /(a+c).

  1.  Коэффициент точности, характеризующий долю выданных релевантных документов,

                                                             n = a/(a+b).

  1.  Коэффициент шума, характеризующий долю выданных нерелевантных документов,

e = b/(a+b) = 1- n.

  1.  Коэффициент осадка, характеризующий долю нерелевантных     документов,

q = b/(b+d).

  1.  Коэффициент специфичности, характеризующий долю невыданных нерелевантных документов,

k = d/(b+d).

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

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

8. ОНТОЛОГИИ

8.1. общие положения

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

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

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

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

Улучшение взаимодействия связывают со следующими мероприятиями.

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

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

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

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

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

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

8.2. Создание онтологий

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

1. Постановка задачи. На этом этапе изучается среда, для которой создается онтология, обдумывается, зачем нужна онтология, как и кем она будет использоваться.

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

3. Формирование вопросов. На этом этапе осуществляются обдумывание и формальное описание вопросов, на которые онтология должна давать ответы, выбирается программная среда для реализации онтологии.

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

 Система теплоснабжения. В качестве конкретного примера создания онтологий рассмотрим ИИС проектирования зданий (интеллектуальную САПР), решающую важную задачу повышения эффективности систем теплоснабжения зданий.

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

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

Можно выделить четыре группы аксиом онтологии теплоснабжения:

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

 Аксиомы идентификации. Полагаем, что здание в целом, включая систему теплоснабжения, имеет множество объектных переменных = =, включая все известные и неизвестные, исходные и промежуточные, оценочные и конструктивные. В реальном проектировании требуется находить и уточнять значения этих переменных, которые, как правило, должны попадать в определенный интервал. Интервалом в нашем случае назовем множество действительных чисел  таких, что , где ,  - границы интервала. Интервал значений переменной  обозначим как []=[,]. Множество интервалов значений переменных обозначим [] (- переменные из , включенные в ). Каждой переменной  сопоставим предикат параметр(,[]) истинный, когда переменная  лежит в интервале [,].

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

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

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

 Аксиомы вычислений. Следующий этап формирования онтологии – это формулировка аксиом вычислений, задающих правила вычисления отношений. Как уже отмечалось, каждое отношение = () связывает множество переменных из , которое используется для вычисления неизвестных значений переменных по значениям переменных . Разбиений множества  на подмножества  и  может быть достаточно много (). Каждому такому разбиению сопоставим оператор (,), =1,…,, по которому осуществляется вычисление неизвестных значений переменных. Введем предикат оператор((,[],,[])) оператор((,)), который истинен, если известны значения переменных множества оператора , и в результате вычисляются значения неизвестных переменных . Тогда множество аксиом вычислений отношения  для одного множества = выглядит следующим образом:

параметр([,])параметр([,]) оператор((,)) экземпляр(,,,[]), где =1,…,.

Интервальная арифметика лежит в основе вычисления формул. Операции сложения, вычитания, умножения и деления над двумя интервалами [,] и [,] имеют вид:

[,] + [,] = [+, +],

[,] - [,] = [-, -],

[,] * [,] = [min{, ,,}, max{, ,,}],

[,] / [,] = [min{/, /,/,/}, max{/, /,/,/}],

0[,].

 

Рассмотрим пример аксиом вычислений для отношения сложения, связывающего три переменные множества  = отношением сложения . Для отношения сложения возможны только три оператора:

а) вычисляющий по известным  и  неизвестную , б) вычисляющий по известным  и  неизвестную  и в) вычисляющий по известным  и  неизвестную . Аксиомы вычислений для отношения  будут определяться следующим образом:

(параметр([,])параметр([,])параметр([,]))([,]=

=[,]+[,]) экземпляр(,0, ,[,],[,],[,]),

(параметр([,])параметр([,])параметр([,]))([,]= =[,]-[,]) экземпляр(,0, ,[,],[,],[,]),

(параметр([,])параметр([,])параметр([,]))([,]=

=[,]-[,]) экземпляр(,0, ,[,],[,],[,]).

 

Аксиомы вычислений должны быть заданы для всех отношений.

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

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

Среди объектных переменных, описывающих здание, выделим те, которые мы можем изменять в процессе поиска их оптимального сочетания. Они образуют вектор переменных , конкретное значение которого !! будем называть решением. Решение представляет собой точку в пространстве значений. Будем полагать, что оптимальное решение принадлежит множеству Парето (решение * принадлежит множеству Парето, если это допустимое решение и для любого другого решения  *  из допустимой области значение хотя бы одного критерия хуже, чем для *). Множество Парето – это множество неулучшаемых решений, так как для любого из них нельзя найти другого допустимого решения, в котором один критерий бы улучшился, а остальные бы не ухудшались. Однако получение множества Парето недостаточно для решения практических задач. Необходимо применить дополнительные знания в конкретной постановке задачи для выбора единственного из множества Парето.

Возможны три типа постановок задачи оптимального поиска:

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

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

наихудшего критерия, минимизации суммы отклонений критериев от идеальных значений и интерактивной оптимизации. Не во всех методах легко выразить предпочтения проектировщика и не все методы дают в конечном итоге оптимальное по Парето решение. Сущность методов оптимизации наихудшего критерия состоит в следующем. Решается задача оптимального поиска по каждому критерию  отдельно, и определяются наилучшие !! max и наихудшие !!min его значения.

Далее для каждого критерия определяется множество его относительных     значений,    вычисляемых   по    формуле   !!отн  =   (!!  –

- !!min)/(!!max - !!min). Очевидно, что среди всех относительных значений данного критерия существует минимальное. Оптимальным считается решение !*!, имеющее максимальное относительное значение критерия среди всех минимальных относительных значений критериев в множестве всех допустимых решений.

 Частотное дискриминирование. В качестве второго примера рассмотрим задачу дискриминирования (сравнения) частот периодических последовательностей сигналов , с частотами следования соответственно, . Данная задача распадается на две подзадачи: как математически сравнить частоты , и каким образом осуществить техническую реализацию сравнения.

 Математическая трактовка. Если частоты , близки друг к другу, то очевидным традиционным решением первой подзадачи является вычитание частоты  одной последовательности из частоты  другой последовательности. Если частоты ,  кратны и необходимо определить отклонение от кратности, то данный прием не подходит. Не подходит указанный прием и в случае, если частоты ,  некратны и надо определить отклонение частот ,  от их некратности. Ясно, что следует связать частоты ,  с условиями задачи – заданными исходными (априорными) соотношениями между частотами , . Таким образом, возникает необходимость в формулировании аксиом идентификации групп (классов) частот ,  до определения их математической обработки (аксиомы вычисления результата сравнения , ).

Выделим три класса частот , : равные, кратные и минимально-некратные частоты. Классы частот определим при условии, когда результат сравнения ,  оказывается нулевым. Это условие оформим в следующем виде:

   / = /,                                                               (8.1)

где ,  - значения частот ,, соответствующих (8.1). Для указанных трех классов частот имеем:

1) равные частоты –

=  = 1;                                    (8.2)

2) кратные частоты –

= ,   = 1,                              (8.3)

где >1 – целое положительное число;

3) минимально-некратные частоты –

= 1+ ,                                    (8.4)

где >1.

Соотношение (8.1) показывает, что аксиома вычисления результата сравнения ,   должна быть представлена как

    =-,                                                                  (8.5)

где

    =+,                                                            (8.6)

- приведенная к  частота ;  - начальное значение частоты ;  - отклонение частоты  от. Аналогично для  можно записать

= +.                                                (8.7)

Приведенное значение  находится в соответствии с (8.1):

    =/,                                                                      (8.8)

где

= +.                                              (8.9)

В этом случае

=+-/ -/ = -/.      (8.10)

Математическая трактовка операции сравнения частот ,  завершена.

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

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

Рассмотрим вначале простейший случай, когда последовательность  содержит единственный повторяющийся на оси  элемент  : 

  () = …         … .

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

                 () = … (1)  (1) …,

                  () =  (1)  (1) …,

где (1) =  и не несет информации о знаке частотного отклонения, т.е. соответствует модульному частотному дискриминированию. Обозначим данный элемент - развертки () как ==, где знаки «+», «-» соответствуют указанным выше направлениям смещения точки Н. Расположим последовательность элементов  под исходной последовательностью ():

                 ()=…    … ,

                  ()=…        … ,                           (8.11)

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

Увеличим далее число возможных различных - элементов последовательности ():

    () = …  …  .                                      (8.12)

Движение вдоль развертки (8.12) позволяет сформировать базис  таких -элементов:

(1) =,    (1) =,   (2) =(2) =(2)= ,

(2) =(2) =(2) =,                                        (8.13)

где ,  - уникальные последовательности-элементов.

Расположив начало координат между соседними элементами , на основе  (8.13) можно образовать несколько групп -событий дискриминирования, соответствующих различным алгоритмам работы дискриминатора частот:

  1.=, =;   2.=, =, =;   3.=,

   =;   4.=, =;    5.= ,  =;

  6.=, =, =;  7.= , =

  =, =; 8.=,  =, =

  ;   9.=;  10.= ;  11.=;  12.=;

 13.=, =;  14.=, =,      (8.14)

где индекс  соответствует знакомодульному дискриминированию, определяющему знак и модуль частотного отклонения, а - знаковому дискриминированию, определяющему знак частотного отклонения. Используя последние выражения, сопоставим -развертку (8.12) с последовательностями событий по аналогии с (8.11), добавляя к букве  в () соответствующие индексы:

                   () =……,

               ()[1,5] =…         …;                                  (8.15)

                     () =……,

          ()[2,6,7,8] = …      …,

         ()[2,6,7,8] = …      …;                                (8.16)

                        () = …  …,

                        ()[3,13] =…       …;                       (8.17)  

                              () =…  …,

  ()[4,14] =…     …;                           (8.18)

                     () =……,

                    ()[9,11] =…                          …;                      (8.19)

                      () =……,

 ()[10,12] =…                          …,                      (8.20)

где () = () = (), () = () = (), а цифры в квадратных скобках при обозначениях () есть номера тех групп  -событий (8.14), которые использованы для формирования разверток (), (), ().

Анализ (8.17), (8.18) обнаруживает новые свойства дискриминатора частот. В частности,  (8.17), (8.18) соответствуют знакомодульному, а (8.19), (8.20) – модульному частотному дискриминированию. Как и для единичной мощности алфавита  элементов  (||=1), при ||=2 модульное частотное дискриминирование допустимо в неограниченном фазовом интервале  – (8.16), (8.19), (820). Однако знакомодульное дискриминирование в неограниченном фазовом интервале может быть только однонаправленным (однополярным) – (8.15), (8.18). Двуполярное знакомодульное дискриминирование ограничено по фазе – (8.15), (8.16).

Отметим, что  количество  элементов -развертки (величина  ),  проходимое  точкой  Н  в  одном   направлении    до образования  ближайшего  -события, зависит  от  формы  событий: наибольшее количество элементов равно двум – (8.19), (8.20).

Отметим также тот факт, что события знака и модуля при знако-модульном дискриминировании начинаются и заканчиваются в одних и тех же фазовых точках оси  - (8.16).

Увеличим далее мощность алфавита  до трех и рассмотрим  -развертку:

   () =…….                            (8.21)

В соответствии с (8.21) имеем такой базис -событий:

   (1) =, (1) =, (1) =, (2) =, (2) =

   =, (2) =, (2) =, (2) =,

   (2) =,  (3) =,  (3) =,

   (3) =,(3) =, (3) =,

   (3) =.                                                      (8.22)  

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

1. =, =;    2. =,

    =, =;     3. =

    =, = 

   , =.       (8.23)

По типу (8.15)-(8.20) для (8.21), (8.23) имеем:

   () =……,

     ()[1] =…                               …,

     ()[1] =…                               …;                             (8.24)

       () =……,

     ()[2] =…             …,

     ()[2] =…              …,

    ()[2] =…                                 …;                             (8.25)

      () =……,

  ()[3] =…            …,

     ()[3] =…             …,

     ()[3] =…                                ….                              (8.26)

Как видно из (8.24)-(8.26), трехбуквенный алфавит позволяет осуществить знакомодульное частотное дискриминирование в неограниченном интервале. Событие знака может начинаться по фазе раньше, чем событие модуля – (8.25), (8.26), а минимальное расстояние  при любом смещении точки Н может превышать размер пустого интервала (расстояние между элементами). Последнее допускает частотное дискриминирование любого вида при стянутых (соприкасающихся) -элементах. Интервал адекватной регистрации знака при  знаковом   дискриминировании, в отличие от предыдущего   случая ||=2, может быть неограничен – (8.24), (8.26).

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

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

  1.  =,   =

,  =  

;    2. =,

=;     3. = 

, = 

;    4. =

, =

, =

.                                                       (8.27)

Результаты дискриминирования по (8.27) имеют следующий вид:

    () =……,

  ()[1] =…                    …,

                   ()[1] = …                   …,

     ()[1] =…                                       …;           (8.28)

      () =……,

        ()[2] =…                                        …,

         ()[2] =…                                      …;              (8.29)

               () =……,

            ()[3] =…                    …,

                   ()[3] =…                     …;       (8.30)

 

     () =……,

             ()[4] =…                 …,

    ()[4] =…                 …,

   ()[4] =…                ….          (8.31)

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

 =.                    (8.32)

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

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

  1.   -элементы есть результат обработки промежуточных элементов .
  2.   -элементы есть результат непосредственного взаимодействия элементов последовательностей ,.

Некоторые из аксиом взаимодействия элементов , следующие:

  1.  =. 2. =. 3. =,

где , - номера элемента . Первая аксиома соответствует булевой алгебре, вторые две – алгебре событий (порядка записи элементов). Очевидно, что .

Возможные аксиомы вычисления  -элементов:

  1.  =. 2. =. 3. =,

где  «» – знак однозначного взаимного соответствия, а «» – стрелка Пирса.

Так как физические сигналы обычно являются одноэлементыми (например, последовательность одинаковых импульсов), то из реальных дискриминируемых последовательностей ,  необходимо сформировать элементы , . Это потребует пересчета результата анализа частот ,  к входным сигналам   , . Кроме того, в зависимости от назначения обработка элементов   должна обеспечивать ту или иную форму выходных сигналов дискриминатора. Таким образом, онтология частотного дискриминирования приводит к следующей блок-схеме дискриминатора  –  рис. 8.1,  где , , , , , , - алфавиты

 

 

элементов соответственно последовательностей , , , , , , ; - выходная последовательность; Б – блок, Ф – формирование, О – обработка, Л – линия.

 В качестве примера рассмотрим дискриминатор на основе знако-модульных событий. Для этого  сформируем из  в виде периодических последовательностей {,}= с частично пересекающимися синхронными элементами  , (операция осуществляется простой задержкой элементов  на время, меньшее длительности элемента; при этом  соответствует исходной, а  - задержанной последовательности ),  которые  представляют  первичный алфавит   =   ={, }.   Сигнал     посредством   операции переиндексации сформируем из = в виде простого сигнала,  представляющего  однобуквенный  первичный  алфавит  ={}. Далее с помощью логического умножения из алфавитов,   образуем вторичный алфавит = {,},  где =, =. Алфавит      зададим    следующим    образом:    = {,,}, = ( - инверсия ), =, =. Заключительный этап – обработка алфавита  - имеет целью формирование знакомодульных событий , , которые в итоге дают сигналы  и алфавит .

Формирование событий ,  ведется, например, в соответствии с аксиомой (8.26). В этом случае разделение выходных сигналов для и  может осуществляться пространственным путем (две линии – для  и ).

Изложенная онтология позволяет также осуществить синтез дискриминатора на любой элементной базе [7].

9. ИНТЕЛЛЕКТУАЛЬНЫЕ ИНТЕРНЕТ-ТЕХНОЛОГИИ

9.1. ЯЗЫКИ РАЗМЕТКИ ДОКУМЕНТОВ

Одним из таких языков является HTML – язык разметки документов с помощью специальных конструкций, называемых тегами. Эти конструкции берутся в угловые скобки. Различают теги «открытия», которые задаются ключевыми словами и допустимыми параметрами, и теги «закрытия» – ключевые слова с символом «/». Общая структура HTML-документа может быть представлена следующим форматом:

!DOCTYPE  HTML  PUBLIC  “-//W3C//DTD  HTML  4.0//EN”

“http://www.w3.org/TR/REC-html40/strict/dtd”

HTML

 HEAD

TITLEНаименование документа/TITLE

 META name=keywords  content=”Представление знаний,

       Мультиагентные системы

  /HEAD

BODY

  Собственно текст документа

/BODY

./HTML

Комментарий !DOCTYPE… фиксирует текущее состояние спецификации версии языка HTML. Кроме того, в HTML-документе выделяются две основные структурные единицы – «голова» документа (между тегами HEAD и /HEAD) и его «тело» (между тегами  BODY и /BODY).

Один из элементов головы документа – это заголовок – произвольный текст между тегами TITLE и /TITLE. Не менее, а может быть и более важным элементом головы документа является тег META name=keywords  content=”Представление знаний, Мультиагентные системы. В приведенном примере этот тег с помощью параметров name и content фиксирует значение первого атрибута как keywords, а второго – как ключевые слова Представление знаний и  Мультиагентные системы. Эти и некоторые другие теги типа META… ориентированы на аннотирование Интернет-документов и, кроме того, существенно облегчают задачу индексирования их, например, с помощью сетевых роботов.

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

Наиболее важными базовыми конструкциями языка HTML являются якоря. Синтаксически эти конструкции представлены тегами А и . с атрибутами NAME и HREF. Пример: A  NAME=”Меткатекст. (обеспечивает в пределах документа уникальное имя начала фрагмента). При этом текст, заключенный между тегами А и ., как правило, задает семантически значимое наименование заголовка.

Для ссылок на помеченные таким образом части Интернет-документа используют конструкции A HREF =”Меткатекст. или A HREF =”URL”текст.. Первая из них задает локальную ссылку на часть документа, начинающуюся с указанной метки. Вторая – глобальную ссылку на документ в сети, однозначно идентифицируемый с помощью URL. По существу, URL – это Интернет-адрес: имя домена, уточненное названием протокола, собственное имя документа, включая путь к нему в пределах данного домена. Пример URL: http://www.anywhere.ru/anywhat.html.

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

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

TABLE

 TR

 TD Столбец-1, строка-1 /TD

 TD Столбец-1, строка-2 /TD

 /TR

/TABLE

FORM  METHOD=”POST” …

 P

 

Можно ввести в поле одну строку:

 INPYT  NAME=”entry”

 /P

 P

 Для обработки результатов ввода:

 INPUT  TYPE=”submit”  VALUE=”Принять запрос

 /P

/FORM

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

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

Для семантической разметки Интернет-документов прежде всего пригодны теги типа TITLE, META… и A. Первый важен для фиксации семантики всего HTML-документа, так как текст, заключенный между тегами TITLE и /TITLE, чаще всего отражает его назначение и содержание. Теги типа META… вводят имена атрибутов, а ссылки и якоря фиксируют отношения между частями документа или документами. Теги A фиксируют факт наличия отношения между ссылкой и ее якорем.

Язык HTML имеет ряд недостаков, к которым в первую очередь относятся нерасширяемость и ограниченные средства спецификации семантической структуры документов.

Некоторые недостатки HTML сняты в языке XML. Отличительными свойствами XML являются стандарт на определение синтаксиса и единообразные средства введения в языки разметки новых тегов. Это позволяет конструировать новые языки маркировки Web-документов и обеспечивает возможность различным приложениям и программным агентам понимать и обрабатывать XML-документы.

Каждый XML-документ обладает определенной логикой и физической структурой. Физически это композиция элементов, называемых единицами, которые могут быть связаны взаимными ссылками. Логически документ состоит из деклараций, единиц, комментариев, собственно текстов и инструкций обработки, причем каждая конструкция XML маркируется специальными тегами явным образом. Все теги XML – парные, а конструкции могут быть вложены друг в друга, образуя правильно построенное дерево. Так, например, конструкция item Attribute 1=”Value 1”/item определяет единицу с именем item и списком пар атрибут-значение, который в нашем случае представлен единственным атрибутом с именем Attribute 1, имеющим значение ”Value 1”.

Пример XML-документа, описывающего домашнюю страницу исследователя Иванова:

?xml version=”1.0”?

Homepage>

<Name>Домашняя страница Иванова</Name>

<Person>

 <firstName>Ivan</firstName >

 <lastName>Ivanov</lastName >

 <marriedTo Homepage=”http://www.anywhere.ru>

      Mariya Ivanova</marriedTo>

 <employee Homepage=”http://www.ccas.ru>

      CCAS of Russia</employee>

 <publications>

  <book title=”First Book”/>

  <book title=”Second Book”/>

……………………………..

 </publications>

</Person>

</Homepage>

 Этот XML-документ пока не имеет «смысла», так как из него не следует, как интерпретируются единицы типа Person, publications, book и т. п. Для решения этого вопроса используется специальная спецификация определения типа документа DTD (document type definition). По сути дела, это грамматика языка разметки, в рамках которой определяются, какие элементы могут присутствовать в документе, какие атрибуты они имеют и как элементы соотносятся друг с другом. Такие спецификации тоже входят в стандарт XML .

     

9.2. ПРОГРАММНЫЕ  АГЕНТЫ

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

Интеллектуальные агенты должны обладать следующими свойствами:

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

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

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

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

Среди разнообразных типов агентов имеет смысл выделить интеллектуального агента по поиску и выбору онтологий – ONTO, использующего ссылочную онтологию (Reference Ontology) в качестве источника знаний. Его брокер (посредник, комиссионер) работает со ссылочной онтологией, а входной запрос строится как соответствующая HTML-форма. Результаты поиска онтологий, удовлетворяющих запросу, возвращаются пользователю также в виде HTML-формы.

9.3. информационный поиск  в среде интернет

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

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

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

Типичный цикл работы машины поиска состоит в следующем:

  •  найти новый документ;
  •  отметить документ как извлеченный;
  •  расшифровать ссылки;
  •  проиндексировать содержание документа.

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

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

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

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Марселус   Д.   Программирование    экспертных    систем   на   ТУРБО-ПРОЛОГЕ. М.: Финансы и статистика, 1994. 256 с.

2. Герман О.В. Введение в теорию экспертных систем и обработку знаний. Мн.: ДизайнПРО, 1995. 255 с.

3. Статические и динамические экспертные системы: Учеб. пособие / Э.В. Попов, И.Б. Фоминых, Е.Б. Кисель, М.Д. Шапот. М.: Финансы и статистика, 1996. 320 с.

4. Змитрович А.И. Интеллектуальные информационные системы.  Мн.: НТООО "Тетра-систем", 1997. 368 с.

5. Одиноков В.Ф. Позиционно-логические дискриминаторы сигналов. М.: Горизонт, 1999. 231 с.

6. Гаврилова Т.А. , Хорошевский В.Ф.  Базы знаний интеллектуальных систем.  СПб.: Питер, 2000. 384 с.

7. Корнеев В.В. и др. Базы данных. Интеллектуальная обработка информации.  М.: Нолидж, 2000. 352 с.  

8. Хомоненко А.Д., Цыганков В.М., Мальцев М.Г. Базы данных: Учебник для высших учебных заведений / Под ред. проф. А.Д. Хомоненко. СПб.: КОРОНА принт, 2000. 416 с.

9. Девятков В.В. Системы искусственного интеллекта: Учеб. пособие для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 352 с. (Сер. Информатика в техническом университете).

10. Джексон Питер. Введение в экспертные системы.: Пер. с англ.: Уч. пос. М.: Издательский дом «Вильямс», 2001. 621 с.

11. Медведев В.С., Потемкин В.Г. Нейронные сети. МАТЛАБ 6 / Под общ. ред. канд. техн. наук В.Г. Потемкина. М.: ДИАЛОГ-МИФИ, 2002. 496 с. (Пакеты прикладных программ; Кн. 4).

12. Представление знаний в информационных системах: Учеб. пособие / В.Ф. Одиноков. Рязань: РГРТА, 2002. 60 с.

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ………………………………………………………………………..3

1. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ…………………………………………..3

2. МОДЕЛИ ЗНАНИЙ……………………………………………………………4

3. СЕМАНТИЧЕСКИЕ БАЗЫ ДАННЫХ ИИС…………………………………8

3.1. ОБЩИЕ ПОЛОЖЕНИЯ………………………………………………………8

3.2. СРЕДСТВА ОПИСАНИЯ ПРЕДМЕТНОЙ ОБЛАСТИ………………………….9

4. АЛГОРИТМЫ ОБРАБОТКИ ЗНАНИЙ МЕТОДАМИ ИИ………………...10

4.1. ФОРМАЛИЗОВАННЫЕ ПРАВИЛА…………………………………………10

4.2. ЭВРИСТИЧЕСКИЕ МЕТОДЫ ПОИСКА РЕШЕНИЙ…………………………17

5. ПРОБЛЕМА РАСПОЗНАВАНИЯ ОБРАЗОВ………………………………26

6. АВТОМАТИЗИРОВАННОЕ ФОРМИРОВАНИЕ ЗНАНИЙ………………33

7. ИНФОРМАЦИОННО-ПОИСКОВЫЕ СИСТЕМЫ………………………...37

7.1. ОБЩИЕ ПОЛОЖЕНИЯ……………………………………………………..37

7.2. СТРУКТУРА ДИПС…………………………………………………………38

7.3. НЕДОСТАТКИ ЕСТЕСТВЕННОГО ЯЗЫКА…………………………………39

7.4. ИНФОРМАЦИОННО-ПОИСКОВЫЕ ЯЗЫКИ………………………………..40

7.5. ОБРАБОТКА ВХОДЯЩЕЙ ИНФОРМАЦИИ………………………………...41

7.6. ЛИНГВИСТИЧЕСКИЙ АНАЛИЗ……………………………………………41

7.7. АВТОМАТИЧЕСКОЕ ИНДЕКСИРОВАНИЕ…………………………………42

7.8. АВТОМАТИЧЕСКОЕ РУБРИЦИРОВАНИЕ…………………………………44

7.8.1. Рубрицирование, основанное на знаниях………………………...44

7.8.2. Рубрицирование, основанное на примерах………………………47

7.9. ПОИСК ТЕКСТОВОЙ ИНФОРМАЦИИ……………………………………...49

7.9.1. Модели поиска информации………………………………………49

7.9.2. Методы обратной связи с пользователем………………………...50

7.10. ОЦЕНКА КАЧЕСТВА ДИПС……………………………………………….50

8. ОНТОЛОГИИ…………………………………………………………………51

8.1. ОБЩИЕ ПОЛОЖЕНИЯ……………………………………………………...51

8.2. СОЗДАНИЕ ОНТОЛОГИЙ…………………………………………………..53

9. ИНТЕЛЛЕКТУАЛЬНЫЕ ИНТЕРНЕТ-ТЕХНОЛОГИИ……………………68

9.1. ЯЗЫКИ РАЗМЕТКИ ДОКУМЕНТОВ………………………………………...68

9.2. ПРОГРАММНЫЕ АГЕНТЫ…………………………………………………71

9.3. ИНФОРМАЦИОННЫЙ ПОИСК В СРЕДЕ ИНТЕРНЕТ……………………….72

БИБЛИОГРАФИЧЕСКИЙ СПИСОК…………………………………………..74

О д и н о к о в Валерий Федорович

Интеллектуальные информационные системы

Редактор Р.К. Мангутова

Корректор Н.А. Орлова

Лицензия № 020446.

Подписано в печать                   Формат бумаги 6084 1/16.

Бумага газетная.  Печать трафаретная.   Усл. печ. л. 4,75.    

Уч.-изд. л.  4,75. Тираж 25 экз. Заказ0ЗЗззззиииЗЗаказ93    Ц. 50

Рязанская государственная радиотехническая академия.

390005, Рязань, ул. Гагарина, 59/1.

Редакционно-издательский центр РГРТА.


 

А также другие работы, которые могут Вас заинтересовать

49482. Проект ОКС 7 на ГТС с УВС 766 KB
  При необходимости с целью оптимизации сети сигнализации, например, по эффективной нагрузке на звено или по задержке распространения, устанавливается приоритет маршрутов в списке допустимых, который позволяет при проектировании методом итераций изменять структуру сети путем исключения неэффективных звеньев или маршрутов из списка допустимых, включаемых в таблицу маршрутизации.