2415

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

Конспект

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

Научные исследования позволяют выявлять и исследовать неявные качества и закономерности свойственные исследуемым объектам. К таким объектам, наиболее часто относятся определенные системы и процессы. Особый интерес для науки и прикладных задач представляет автоматизация научных исследований, то есть создание автоматизированных систем научных исследований (АСНИ).

Русский

2013-01-06

1.03 MB

77 чел.

АСНИ – конспект лекций

Лекция 1

Введение          2

Задачи научных исследований       2 

Систем и их типы         3 

1. Общие понятия и определения

Лекция 2

1.1 Объекты и системы объектов      4 

1.2 Базовые свойства        5 

1.3 Ограничения на выбор баз       5

1.4 Формальное определение системы      6

Лекция 3

1.5 Переменные и параметры       6

1.6 Обобщенные переменные и параметры. Формализация.   7 

Лекция 4

1.7 Каналы наблюдения        8

1.8 Нечеткие каналы наблюдения       9

Лекция 5

1.9 Методологические отличия       11

1.10 Методологические отличия на уровне переменных и параметров 13

2. Представляющие и исходные системы

Лекция 6

2.1 Формализация представляющих и исходных систем   14

2.2 Системы с входными и выходными переменными    16

Лекция 7

2.3 Вырожденные типы направленных систем     17

3. Системы данных

Лекция 8

3.1 Формализация систем данных       21

3.2 Системы данных с нечеткими каналами наблюдения   22

3.3 Представление данных        22

4. Порождающие системы

Лекция 9

4.1 Системы с поведением        23

4.2 Выборочные переменные и маски      24

4.3 Маски в случае полностью упорядоченных параметрических множеств 25

Лекция 10

4.4 Функции поведения. Порождающие и порождаемые переменные. 26

4.5 Особенности процедуры порождения данных    27

Лекция 11

4.6 Функции порождения для недетерминированных систем   30

4.7 Направленные системы с поведением      31

Лекция 12

4.8 Переход от систем данных, к системам с поведением   32

4.9 Особенности переходов, в зависимости от свойств параметрического множества         33

4.10 Особенности построения масок      34

4.11 Содержательные подмаски       34

Лекция 13

4.12 Меры нечеткости        35

4.13 Методы вычислений нечеткости      36

Лекция 14

4.14 Выбор подходящих систем с поведением     40

4.15 Упорядочение по сложности и нечеткости    41

Лекция 15

4.16 Системы с изменяющимися состояниями     45

Лекция 16

4.17 Взаимосвязь ST-систем и систем с поведением    49

Лекция 17

4.18 Виды порождающих систем       52

4.19 Упрощение порождающих систем      53

Лекция 18

Исследование и проектирование при помощи АСНИ     56


Лекция 1

Введение

Научные исследования позволяют выявлять и исследовать неявные качества и закономерности свойственные исследуемым объектам. К таким объектам, наиболее часто относятся определенные системы и процессы. Особый интерес для науки и прикладных задач представляет автоматизация научных исследований, то есть создание автоматизированных систем научных исследований (АСНИ).

В курсе будут рассмотрены общие принципы формализации произвольных систем, получения эмпирических данных в ходе моделирования, основы исследования систем. То есть принципы построения и применения АСНИ.

 

Задачи научных исследований

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

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

а) выделение задач, в которых рассматриваются определенные типы элементов систем;

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

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

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

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

Рис.1 Общая схема работы АСНИ

Систем и их типы

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

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

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

Рис.2 Иерархическая схема типов систем

К.Р. № 1

Охарактеризуйте общую схему работы АСНИ, и иерархические типы систем.

Лекция 2

1. Общие понятия и определения

1.1 Объекты и системы объектов

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

Согласно этому определению объекты могут быть как

а) материальными, так и

б) абстрактными.

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

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

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

Таким образом, система всегда рассматривается не как реальный объект, а как абстрагирование или отображение некоторых свойств объекта.

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

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

1.2 Базовые свойства

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

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

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

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

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

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

Базы трех основных типов — время, пространство, группа — можно комбинировать. Хотя в принципе возможны любые комбинации, особенно важны и распространены комбинации время — пространство и время — группа.

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

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

1.3 Ограничения на выбор баз

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

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

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

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

1.4 Формальное определение системы

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

Формально система

,(1.1)

где Nn={1, 2, …, n}, a Nm={1, 2, …, m} (буквой N с положительным целым индексом здесь всегда обозначается множество значений целых положительных чисел от 1 до значения этого индекса); через ai и Ai обозначены соответственно свойство и множество его проявлений; bj и Bj— база и множество ее проявлений, а О — система объекта.

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

К.Р. № 2

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

Выберите некоторую систему, и формализуйте ее.

Лекция 3

1.5 Переменные и параметры

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

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

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

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

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

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

1.6 Обобщенные переменные и параметры. Формализация.

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

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

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

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

 vi, Vi,  означающие соответственно обобщенную переменную, ее множество состояний и множество математических свойств, определенных для нее;

, , те же характеристики конкретной переменной, являющиеся конкретизацией переменной vi;

и  соответственно обобщенный параметр, его множество состояний и множество математических свойств, определенных на параметре wj;

и — те же характеристики конкретного параметра, полученные конкретизацией параметра wj.

АСНИ работает, в основном, только с обобщенными переменными и параметрами. Заданная обобщенная переменная vi, конкретизируется переменной  тогда и только тогда, когда функция

ei : Vi,(1.2)

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

εj :  Wj, (1.3)

существует и изоморфна относительно .

Каждый конкретный изоморфизм ei  (или  εj) задает конкретизацию vi с помощью (или соответственно wj с помощью).

Функции, обратные  ei и   εj, т. е.

e-1i : Vi ,(1.4)

ε-1 j :  ,(1.5)

задают абстрагирование соответственно и . ▲

К.Р. № 3

Для некоторой системы опишите конкретные и обобщенные переменные и параметры.

Лекция 4

1.7 Каналы наблюдения

Назовем каналом наблюдения понимаем любую операцию, вводящую конкретную переменную как отображение (или конкретизацию) свойства.

Канал наблюдения, с помощью которого свойство ai представляется переменной , реализуется функцией

Oi : Ai, (1.6)

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

Аналогичная функция, скажем

ωj : Bj , (1.7)

задает представление базы bj, параметром , она также должна быть гомоморфной относительно соответствующих свойств базы (например, времени) и множества 

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

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

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

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

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

Пример 1.1. Для иллюстрации введенных понятий положим, что ai — это установленный ежегодный доход налогоплательщика некоторой страны за последний год, как сообщается в его налоговой декларации за этот год. Тогда Ai — это всевозможные суммы денег от нуля до максимально представимой суммы, скажем до 100000.00 единиц. Это множество конечно, так как минимальная имеющая хождение денежная величина — 0.1 единицы. Мы понимаем также, что это множество полностью (линейно) упорядочено. Для вычисления подоходного налога достаточно рассматривать только диапазоны облагаемого налогом дохода, где каждому диапазону соответствует определенный процент дохода, который следует выплатить в качестве подоходного налога. Для упрощения будем этими диапазонами считать диапазоны 0—4999.99, 5000.00 — 9999.99, .... 90000.00 —94999.99, 95000.00—100000.00 и пусть множеством состояний , конкретной переменной , представляющей свойство ai , будет множество минимальных значений этих диапазонов. Содержательное представление ai с помощью можно ввести с помощью функции оi, которая для каждого диапазона любому значению из диапазона присваивает минимальное значение в этом диапазоне, например оi (52357) =50 000 или оi (796) =0. Очевидно, что функция  оi гомоморфна относительно полного упорядочения Ai, так как для любой пары

α, β  Ai,  если α β,  оi(α,)  оi (β) . Из методических соображений обобщенная переменная vi может быть для конкретной переменной определена с помощью абстрагирующей функции e-1i : Vi . Эта функция должна быть изоморфной относительно упорядочения на . Предположим, что нужно, чтобы множество Vi представляло собой набор значений целых чисел. Тогда e-1i  можно, вероятно, наиболее естественным образом, задать следующим уравнением:

                                              e-1i   (5000k)=k  (k=0,1,…, 19)    

Базой в этом примере является множество налогоплательщиков определенной категории, скажем множество жителей города Х. Данное множество не обладает никакими математическими свойствами. Таким образом,  ωj : Bj  может быть любой взаимно однозначной функцией, которая каждому налогоплательщику ставит в соответствие уникальный идентификатор. Методологически удобно абстрагирование ε-1j:Wj  представить в виде взаимно однозначной функции, ставящей в соответствие целым числам

из множества Nn, где n — число налогоплательщиков в этой группе.

1.8 Нечеткие каналы наблюдения

Остановимся более подробно на понятии канала наблюдения. До сих пор мы его определяли через функции оi и ωj , определенные соответственно в уравнениях (1.6) и (1.7). Эти функции предполагают разбиения множеств Ai и Bj на некоторые подмножества,  обозначим их соответственно  Aii и Bj/ωj. Элементы любого подмножества в этом разбиении эквивалентны в том смысле, что они не различаются с точки зрения введенной процедуры наблюдения. В таком разбиении каждое подмножество целиком представляет одно состояние переменной или одно значение параметра . Когда наблюдение свойства ai, проводится при некотором значении параметра, то наблюдаемое свойство получает определенное проявление (значение) из множества Ai. Это проявление является элементом одного и только одного подмножества Aii. Функция оi  присваивает его определенному состоянию переменной . Таким образом, предполагается, что любое наблюдение позволяет нам определить, к какому подмножеству Aii принадлежит данное проявление, даже если отдельное проявление и нельзя идентифицировать.

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

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

В результате появления возможности ошибок измерения с проявлениями возле границ между подмножествами A/оi связана определенная недостоверность наблюдения. Имеется два варианта интерпретации этой недостоверности. Здесь мы рассмотрим, и будем придерживаться одного из них.

Разбиение множества Ai задается функцией оi. Это то же самое разбиение Aii , что рассматривалось выше. Достоверно  неизвестно, к какому подмножеству Aii принадлежит заданный элемент Ai.. Эта недостоверность может быть задана функцией, сопоставляющей любой паре  (элемент Ai, подмножество Aii)  число  (обычно между 0 и 1 – некий аналог вероятности).

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

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

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

 : Ai Aii → [0, 1], (1.8)

Однако, поскольку каждое подмножество Aii однозначно представляется  (помечается) состоянием из множества (в соответствии с функцией оi), функциюможно задать в более удобном виде

 : Ai  → [0, 1], (1.9)

Определенная в уравнении (1.9) функцияхарактеризует наблюдения свойства ai в смысле их недостоверности. В этом смысле можно назвать нечетким каналом наблюдения. Во избежание недоразумений оi будем называть четким каналом наблюдения. ▲

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

                                                           

то задает четкую функцию из Ai в , идентичную оi .

При рассмотрении баз можно ввести функцию

: Bj    → [0, 1], (1.10)

подобную функции (1.9) и основанную на соотношении (1.7). Здесь (x, y) — степень достоверности того, что х принадлежит подмножеству Bj/ωj, который представлен значением у параметра . На практике, однако, эта функция не используется.

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

Пример 1.2. Пусть свойством ai является возраст человека из группы Bj. И пусть элементами Ai будут номера лет в диапазоне от 0 до 100. Положим, что . = {очень молодой, молодой, средних лет, старый, очень старый}, и пусть оi — это взаимно однозначная функция Aii  , определенная следующим

образом:

{0, 1, …, 14}        - очень молодой,

{15, 16, …, 29}    - молодой,

{30, 31, …, 49}    - средних лет,

{50, 51, …, 74}    - старый,

{75, 76, …, 100}  - очень старый.

При использовании четкого канала наблюдения очень плохо описываются люди, чей возраст близок к границам между блоками Aii. Например, 49-летний человек помечается как человек средних лет, а 50-летний, как старый. При использовании нечеткого канала оi, например такого, какой описан на рис. 1.1, приведен оказывается более подходящим, поскольку не дает таких резких скачков. Важно отметить, что нечеткий канал наблюдения дает не одно состояние для одного наблюдения, как четкий канал, а набор значений для всех . Так, например, при наблюдении 25-летнего человека через нечеткий канал будут получены следующие 5 значений:

(25, очень молодой) = 0.1

(25, молодой) = 0.97

(25, старый) = 0

(25, очень старый) = 0.

Рис. 1.1. Четкий и нечеткий каналы наблюдения для полностью упорядоченного признака «возраст человека»

К.Р. № 4

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

 

Лекция 5

1.9 Методологические отличия

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

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

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

Методологические отличия для переменных и параметров — это характеристики их множеств состояний и, соответственно, параметрических множеств. Если переменная (или параметр) представляет свойство (или базу), то эти свойства не могут быть произвольными.

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

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

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

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

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

∆ Формально частичная упорядоченность Q, например, множества Vi — это бинарное отношение

                                                                           Q  Vi  Vi ,(1.11)

удовлетворяющее следующим требованиям:

1. (x, x)  Q (рефлексивность);

2.  если (x, y)  Q и(y, x)  Q, то х = у (антисимметричность);

  1.  если  (x, y)  Q и (y, z)  Q , то ( x, z )  Q (транзитивность).

Если (x , y)  Q то х называется предшественником у, а упреемником х. Если (x , y)  Q и не существует, z  Q, такого, что ( x, z )  Q и (z, x)  Q, то х называется непосредственным предшественником у, а унепосредственным преемником х. В дополнение к требованиям рефлексивности, антисимметричности и транзитивности отношение линейной упорядоченности удовлетворяет следующему требованию связности: для всех х, y  Vi , если , то или (x, y)  Q или (y, x)  Q. ▲

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

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

∆ Для данного множества, скажем множества , расстояние определяется функцией вида

: R , (1.12)

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

(1)  (x, y) 0      (условие неотрицательности);

(2)  (x, y) = 0    тогда и только тогда, когда х = у  (условие нулевого расстояния, называемое также условием невырожденности);

(3)  (x, y) = (y, x)  (симметричность);

(4)  (x, y)  (x, y) +(y, z)   (неравенство треугольника).

Любая функция, удовлетворяющая условиям (1) - (4), называется метрическим расстоянием на множестве , а пара (, )  — метрическим пространством. Метрическое расстояние можно, разумеется, определить как на множестве состояний, так и на параметрическом множестве. ▲

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

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

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

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

1.10 Методологические отличия на уровне переменных и параметров

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

                                                             0 — упорядоченности нет

 Упорядоченность:                            1  — частичная упорядоченность

                                                             2 — линейная упорядоченность

 Расстояние:                                       0 — не определено

                                                             1 — определено

 Непрерывность:                                0 — дискретно

                                                             1 — непрерывно

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

(упорядоченность, расстояние, непрерывность),

в котором каждое свойство представляется его определенным значением (или его идентификатором). Так, например, триплет (2, 1, 0) описывает дискретную переменную с линейно упорядоченным множеством состояний, на котором определено метрическое расстояние.

Рис. 1.2. Решетки методологических типов переменных или параметров

Хотя данные три свойства в принципе определяют 12 возможных комбинаций, три из них (0, 0, 1), (0, 1, 0) и (0, 1, 1) смысла не имеют. В самом деле, если на множестве не определена упорядоченность, то на нем нельзя ни содержательно определить метрическое расстояние, ни рассматривать его как непрерывное. Таким образом, имеется девять осмысленных комбинаций. Будем называть эти комбинации методологическими типами переменных и параметров.

Они могут быть частично упорядочены с помощью отношения «быть методологически более определенным чем». На рис. 1.2,а это частичное упорядочение, образующее решетку,

представлено в виде диаграммы Хассе. Упрощенная решетка на рис. 1.2,б задает схему для свойств упорядоченности и расстояния, но без непрерывности.

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

,(1.13)

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

.(1.14)

Алгоритм формализации систем объекта

  1.  Определяются свойства ai и множества их проявлений Ai .
  2.  Определяются базы bj и множества их проявлений Bj .
  3.  Определяется система объекта , где Nn={1, 2, …, n}, a Nm={1, 2, …, m}.

К.Р. № 5

 Опишите две системы с различными методологическими отличиями.

Лекция 6

2. Представляющие и исходные системы

2.1 Формализация представляющих и исходных систем

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

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

Пусть и — это, соответственно конкретная и общая представляющая системы. Тогда

 (2.1)

  (2.2)

где соответствующие символы имеют тот же смысл, что и ранее.

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

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

определяется уравнением (1.6)   и должны быть гомоморфны относительно свойств и }, {(,,определяются уравнением  (1.7)  и должны быть гомоморфны относительно свойств и })  (2.3)

где все символы имеют тот же смысл, что и ранее.

Нечеткий полный канал наблюдения, скажем , можно получить, заменив из (1.6) на , определенное уравнением (1.9). Функции также можно было бы заменить на функции , заданные уравнением (1.10), однако такая замена, по определенным соображениям, здесь опущенным, схемой АСНИ не предусматривается.

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

определяются уравнением (1.2) и должны быть  изоморфны   относительно    свойств и }, определяются уравнением  (1.3)  и должны быть изоморфны относительно свойств ,(2.4)

Можно  рассмотреть    канал  наблюдения  из  системы  объекта непосредственно в общую представляющую систему. Однако этот канал можно получить из двух каналов, определяемых уравнением (2.3) и (2.4). Он состоит из триплетов

и ),(2.5)

где символ обозначает композицию. 

Теперь можно определить исходную систему, как пятерку

,(2.6)

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

Рис 2.1. Концептуальные элементы, используемые для определения исходной системы.

2.2 Системы с входными и выходными переменными

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

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

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

,(2.7)

такой, что если или, то это значит, что переменная является соответственно входной или выходной. Любой n-мерный вектор-строку

,(2.8)

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

Обозначим направленные аналоги нейтральных систем теми же символами, но с добавлением знака ^. Тогда

(2.9)

(2.10)                             (2.11)

где —направленные аналоги нейтральных систем . Направленная исходная система  определяется пятеркой

.  (2.12) ▲

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

К.Р. № 6

Опишите формально некоторые представляющую и исходную системы с входными и выходными переменными.

Лекция 7

2.3 Вырожденные типы направленных систем

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

Существует два типа вырожденных направленных систем.

1. Направленные системы без выходных переменных (рис. 2.2,б), т е. системы с . Эти системы методологически бесполезны. В самом деле, любая такая система имеет только входные переменные, которые по определению полностью задаются средой, и, следовательно, их свойства невозможно представить и исследовать внутри самой системы. Таким образом, в системе нечего описывать и изучать любое утверждение, которое можно сформулировать внутри системы, бессмысленно, так как оно содержит только условие, но не следствие. Следовательно, для п переменных имеется только осмысленных объявлений входа-выхода.

2. Направленные системы без входных переменных (рис. 2.2,в), т. е. системы с .Эти системы методологически интересны, поскольку для них можно сформулировать содержательные утверждения. Однако эти утверждения не могут быть условными, поскольку в таких системах нет входных переменных, на которых можно было бы сформулировать эти условия.

                        а)                                                                                   б)

                          в)                                                                             г)

Рис.2.2. Методологические отличия направленных и нейтральных исходных систем.

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

Отличия между нейтральными и направленными системами и между четкими и нечеткими каналами наблюдения — это еще два методологических отличия исходных систем. Любая исходная система является или нейтральной, или направленной, а каналы наблюдения ее переменных или все четкие, или все нечеткие, или разных типов. Таким образом, новые отличия дают 2х3=6 возможностей. Кроме того, в исходную систему могут входить переменные разных методологических типов. Обозначим общее число методологических отличий, определенных для уровня исходных систем, через #S. Тогда при вполне разумном предположении, что число параметров не превышает 9 , мы получим

, (2.13)

где .

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

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

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

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

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

Рис. 2.3, а.  Определение переменных для признаков .

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

Рис. 2.3, б.  Определение переменных для признаков .

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

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

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

Алгоритм формализации представляющих систем

  1.  Определяются vi, Vi, означающие соответственно обобщенную переменную, ее множество состояний и множество математических свойств, определенных для нее.
  2.  Определяются , , те же характеристики конкретной переменной, являющиеся конкретизацией переменной vi  .
  3.  Определяются и  соответственно обобщенный параметр, его множество состояний и множество математических свойств, определенных на параметре wj.
  4.  Определяются и — те же характеристики конкретного параметра, полученные конкретизацией параметра wj.
  5.  Определяются и —  соответственно конкретная и общая представляющая системы:  .

Для направленных систем, дополнительно

  1.  Определяется , если или, то это значит, что переменная является соответственно входной или выходной.
  2.  Направленные аналоги нейтральных систем: .

Алгоритм формализации исходных систем

  1.  Определяется канал наблюдения, с помощью которого свойство ai представляется переменной :    Oi : Ai.
  2.  Определяется представление базы bj, параметром :    ωj : Bj .
  3.  Определяется функция ei , конкретизирующая обобщенную переменную vi  , изоморфная относительно математических свойств :     ei : Vi. 
  4.  Определяется функция εj , конкретизирующая обобщенный параметр wj  , изоморфная относительно математических свойств:    εj :  Wj.
  5.  Определяется четкий полный канал наблюдения:  должны быть гомоморфны относительно свойств и }, {(,, должны быть гомоморфны относительно свойств и }).
  6.  Определяется каналом конкретизации абстрагирования: должны быть  изоморфны   относительно    свойств и }, должны быть изоморфны относительно свойств .
  7.  Определяется исходная система:  . Для направленных систем .

К.Р. № 7

 Приведите подробный пример вырожденной системы.

Лекция 8

3. Системы данных

3.1 Формализация систем данных

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

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

,(3.1)

.(3.2)

Тогда четкие данные представляются функцией

,(3.3)

Функция d любому значению полного параметра ставит в соответствие одно полное состояние переменных.

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

,(3.4)

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

,(3.5)

В данном случае функция d связана с системой S следующим образом: если наблюдение, описываемое с помощью

,(3.6)

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

,(3.7)

где .

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

Системы данных D и SD нейтральные. Превращение этих систем в их направленные аналоги и труда не представляет. Нужно только заменить на , а S на .Таким образом,

,(3.8)

,(3.9)

— это направленные системы данных без представления смысла данных и с последним соответственно.

3.2 Системы данных с нечеткими каналами наблюдения

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

,(3.10)

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

Формализуем  понятие нечетких данных. Пусть

.(3.11)

Тогда нечеткие данные представляются функцией

. (3.12)

Для любого значения полного параметра

,(3.13)

где .  

3.3 Представление данных

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

,(3.14)

элементами которой  являются состояния переменных , наблюденные при соответствующих значениях полного параметра w (рис. 3.1,а). Каждый столбец матрицы d задает полное состояние, наблюденное при данном w, а каждая строка — все наблюдения одной переменной на параметрическом множестве W. Если W линейно упорядочено, то и столбцы в матрице d должны быть упорядочены точно таким же образом. Если используются несколько параметров, то может оказаться удобнее использовать другие формы представления.

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

,(3.15)

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

. Массив представляет собой набор матриц (рис. 3.1,б), по одной для каждой переменной. Столбец в матрице переменной задает функцию , определяемую уравнением (3.10).

V

а)

б)

Рис. 3.1 Стандартные формы представления данных для дискретных переменных а) четкие данные б) нечеткие данные

К.Р. № 8

 Опишите формально некоторую систему данных с нечеткими каналами наблюдения.

Приведите пример представления данных.

Алгоритм формализации систем данных

  1.  Определяется функция , где , .
  2.  Определяется система данных .Система данных с семантикой . Направленные аналоги ,.

Для систем данных с нечеткими каналами наблюдения

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

2. Нечеткие данные представляются функцией , где .

Лекция 9

4. Порождающие системы

4.1 Системы с поведением

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

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

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

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

, (4.1)    

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

, (4.2)

где — целая константа (положительная, отрицательная или нуль). При   называется тождественным правилом сдвига.

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

4.2 Выборочные переменные и маски

Пусть задана обобщенная представляющая система I, определяемая уравнением (2.12). Обозначим через V множество переменных из I, а через R набор правил сдвига, рассматриваемых для этих переменных. Тогда множество переменных

,(4.3)

называемых выборочными переменными, может быть введено с помощью уравнений

,(4.4)

для некоторых переменных и правил сдвига ; обозначает состояние выборочной переменной при значении параметра w, а  — состояние переменной   при значении параметра , т. е. при значении, полученном для заданного w, при применении правила сдвига . Для полностью упорядоченного параметрического множества, правила сдвига которого имеют вид (4.2), уравнение (4.4) может быть переписано в более определенном виде

,(4.5)

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

, (4.6)

так, что всякой паре  соответствует одно уравнение из (4.4). Отношение М представляет схему соседства на параметрическом множестве, в терминах которого определены выборочные переменные. Эта схема обычно называется маской.

Для введения идентификаторов выборочных переменных k должна быть введена некая однозначная функция (кодирование).

, (4.7)

где — это количество элементов множества М.

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

,(4.8)

представляет собой полное множество состояний выборочных переменных.

4.3 Маски в случае полностью упорядоченных параметрических множеств

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

, (4.9)

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

Состояние d 

для M при t=7

=

=

2

=

=

0

k

=

=

3

=

=

2

=

=

1

=

=

1

Маска M

=

=

0

 

=

=

3

 

=

=

0

Справочник

=

=

2

-2

-1

0

1

i=1

1

2

2

3

4

3

5

6

7

4

8

9

5

10

                    в)                                                                                       а)

t=

1

2

3

4

5

6

7

8

9

Матрица данных d

0

0

1

2

2

2

0

1

1

3

2

2

1

2

3

3

2

0

0

0

0

1

1

1

0

0

0

0

0

1

2

3

0

0

1

2

2

2

2

0

1

2

2

2

1

Справочник

                       б)

Рис.4.1. Пояснение понятия маски для полностью упорядоченных параметрических множеств.

переменных из множества V, a столбцы — целыми константами , связанными с правилами сдвига вида (4.2). Элементы матрицы или пусты, или представляют собой идентификаторы k выборочных переменных, приписанные парам согласно (4.6); пустые элементы матрицы соответствуют элементам , не входящим в маску. В визуальном представлении становится ясно, почему используется термин «маска».

Часто бывает удобно разбить маску М на подмаски М„ каждая из которых связана с одной переменной и, из подобной системы. Формально

, (4.10)

 В визуальном (матричном) представлении подмаски  представляют собой строки. В любой маске один столбец соответствует тождественному правилу сдвига . Этот столбец имеет особое значение, поскольку связанные с ним выборочные переменные идентичны базовым переменным заданной представляющей системы. Будем этот столбец в масках называть справочником. Если маска помещена на матрицу данных таким образом, что справочник совпадает с определенным значением t, то маска выделит только некоторое подмножество элементов, а именно элементы, представляющие полное состояние выборочных переменных при данном значении t. Так, например, на рис. 4.1,б изображена маска (определенная на рис. 4.1,а), помещенная на матрицу данных d при t=7 (справочник маски совпадает с t=7). Полное состояние выборочных переменных для этого положения маски показано на рис. 4.1,в. Состояния справочника выборочных переменных в точности те же (для любого t), что и состояние базовых переменных соответственно . Остальные выборочные переменные представляют собой состояния из параметрического соседства в t. Для любой маски при любом t схема соседства сохраняется. Если t — время, то переменная будет представлять будущее (относительно рассматриваемого значения t) состояние переменной , а переменные и будут представлять, прошлые состояния переменной любая маска представляет определенную точку зрения, в соответствии с которой представляются ограничения на базовые переменные.

К.Р. № 9

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

Лекция 10

4.4 Функции поведения. Порождающие и порождаемые переменные.

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

,(4.11)

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

Функция  определяет встречающиеся состояния с, но не определяет значение параметра, при котором они имеют место. Таким образом, эта функция является параметрически инвариантной.

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

, (4.12)

где I — обобщенная представляющая система; М — маска, определенная на I; —функция поведения, определенная через М и I. Будем такую систему называть системой с поведением

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

1)   переменные, состояния которых порождаются из ограничения; назовем их порождаемыми переменными;

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

Для заданной системы с поведением одним из способов определения порожденных и порождающих переменных является определение для данной маски М двух подмасок и . Будем

, (4.13)

где

,(4.14)

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

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

(4.15)  

с помощью которых множества состояний и соответственно порождаемых и порождающих переменных задаются декартовыми произведениями

(4.16)

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

, (4.17)

где

,(4.18)

Назовем эту функцию порождающей функцией поведения.

Если маску М и функцию из (4.11) заменить соответственно на и функцию , то получится альтернативная система

. (4.19)

Будем называть такую систему порождающей системой с поведением.

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

а)  для некоторого значения задано состояние ; для  определения состояния при том же значении используется  функция ;

б)   значение t заменяется на новое и повторяется этап а).

4.5 Особенности процедуры порождения данных

1. На этапе а) неявно предполагается, что при заданном значении t состояние известно. Это состояние называется начальное условие. Однако после этого все полностью определяется самим процессом порождения, т. е. состояниями и g, связанными с предшествующим значением t. При этом предполагается, что значения t должны на этапе (б) изменяться в соответствии с порядком, заданным на множестве Т. Таким образом, значения t заменяются или на t+l, или на t-1. В первом варианте начальное условие должно быть определено для наименьшего возможного значения t, а во втором — для наибольшего возможного значения t.

2. Из необходимости порождения данных в одном из двух порядков следует, что существует только два содержательных разбиения маски М на и , каждое из которых соответствует одному из двух порядков порождения. Если данные порождаются в порядке возрастания (убывания) t, то содержит ровно по одному элементу каждой подмаски  , определенной в (4.10), элемент с наибольшим (наименьшим) значением ; остальные элементы М входят в . Таким образом, графически получается, что — это множество самых правых элементов М (правый край этой маски) или, наоборот, множество самых левых элементов М (левый край маски).

3. Предполагается, что для любого состояния имеется по крайней мере одно состояние , допустимое функцией [т.е. ] Если допускается только одно состояние, то для любого начального условия данные порождаются однозначно; такие системы называются детерминированными. Если допускается более чем одно состояние, то порождение данных проблематично, так как порождаемое состояние не всегда однозначно определено. Для таких систем выбирающие функции поведения не подходят. Более содержательно они описываются функциями поведения других типов, рассматриваемых ниже. Для детерминированных систем представление (4.17) порождающей функции поведения может быть заменено более простым

. (4.20)

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

В первом случае (рис. 4.2) порождаемые выборочные переменные— это переменные, соответствующие правому краю маски, т. е. ; остальные выборочные переменные являются порождающими. Порождение данных в матрице данных происходит слева направо. Пусть порождающая функция поведения , представленная в виде (4.20), определяется уравнениями

при , Множества состояний порождаемых   переменных определяются этими уравнениями, а множества состояний порождающих переменных — их положением в маске. Например, множество состояний порождаемой переменной — это 0, 1, 2, 3, так как уравнение для берется по модулю 4; порождающая переменная имеет то же множество состояний, что и s4, так как обе эти переменные определены через одну и ту же переменную представляющей системы   (т. е. ).

Справочник

Справочник

1

2

1

2

0

9

t=

1

2

3

4

5

6

t=

1

2

3

4

5

6

7

1

1

1

1

1

1

1

1

1

1

1

1

4

1

1

5

2

1

1

5

1

1

5

3

5

5

9

                                               а)                                                                             б)

0

0

t=

1

2

3

4

5

6

t=

1

2

3

4

5

6

7

8

0

2

1

1

1

1

1

0

4

0

0

1

1

1

1

1

1

2

0

4

5

1

1

5

2

1

1

5

2

0

4

4

4

1

1

6

0

1

1

5

0

5

4

6

9

4

5

9

4

4

Справочник

Справочник

                                     в)                                                                   г)

t=

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

1

1

1

0

0

1

0

1

0

0

1

0

0

0

0

0

1

1

1

2

0

1

0

3

0

0

1

0

0

2

2

1

1

5

2

0

4

2

5

0

5

5

6

2

5

0

3

3

1

1

5

0

5

4

0

3

7

3

3

4

7

3

5

1

1

5

9

4

4

9

2

7

2

2

3

6

2

4

0

0

Начальное условие

                                                                          д)

Рис. 4.2. Данные, порожденные в порядке возрастания значения параметра t (Пример 3.1).

Первой осмысленной позицией маски на матрице данных (позиция определяется положением справочника маски) является позиция t=3; позиции t=1 и t=2 смысла не имеют, так как состояния некоторых выборочных переменных для этих позиций не определены ( не входит в множество Т). Начальное условие состоит из шести элементов матрицы данных:  . Пусть, например, все эти элементы равны 1. Еще пять элементов    матрицы   данных — — не могут быть порождены, а могут быть заданы пользователем, но для порождения данных эти переменные не нужны. На рис. 4.2,а,б,в,г подробно показано порождение состояний соответственно для t = 3, 4, 5, 6; кружками обведены порожденные состояния. На рис. 4.2.д показано начальное условие и несколько больший фрагмент порожденной матрицы данных.

1

t=

94

95

96

97

98

99

t=

93

94

95

96

97

98

99

1

1

1

1

1

1

3

1

1

1

1

1

0

5

1

1

5

1

1

9

5

1

1

5

1

1

Справочник

Справочник

5

5

                                               а)                                                                             б)

0

t=

93

94

95

96

97

98

99

t=

93

94

95

96

97

98

99

2

1

1

1

1

0

1

1

1

1

4

3

1

1

1

2

3

1

1

1

1

3

3

5

1

1

4

3

3

5

1

1

10

6

0

6

1

1

1

6

0

5

1

1

Справочник

Справочник

4

9

5

10

4

9

5

                                        в)                                                                      г)                                                                                                                                                                                                                                            

t=

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

0

1

1

0

1

1

1

0

1

0

1

0

1

1

1

1

1

2

3

3

0

1

1

1

0

1

0

3

2

3

1

1

1

5

3

2

5

5

5

2

3

0

3

4

3

3

5

1

1

2

6

2

8

8

5

8

0

3

6

1

6

0

5

1

1

9

7

0

4

9

6

6

5

8

9

1

4

10

4

9

5

Начальное условие

Рис. 4.3.  Данные, порожденные в порядке убывания значения параметра t (Пример 3.1).

Начальное условие

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

при  k = 1, 3, 5, 8, 10. Порождение данных при t = 98, 97, 96, 95 подробно показано на рис.4.3,а, б, в и г. На рис. 4.3,д показано начальное условие и несколько больший фрагмент порожденной матрицы.

К.Р. № 10

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

Лекция 11

4.6 Функции порождения для недетерминированных систем

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

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

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

, (4.21)

При этом порождающая функция поведения имеет вид

 

,(4.22)

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

4.7 Направленные системы с поведением

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

1) выборочные переменные, определяемые средой, т. е. входные переменные [переменные , для которых ];

2)   остальные выборочные переменные, связанные с рассматриваемой маской.

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

, (4.23)

для которой справедливо, что

(4.24)

определяет маску направленной системы с поведением.

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

(4.25)

и будут определены следующие два множества состояний:

(4.26)

необходимые для направленных систем. Функция поведения направленных систем имеет вид

,(4.27)

где  — это условная вероятность и,   следовательно,    вместо    записи можно использовать стандартную форму . Теперь можно определить направленную систему    с    поведением    как тройку

.(4.28)

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

,(4.29)

где — это разбиение М.    Снова   определяются   кодирующие функции (4.15), но рассматривается   теперь   как разбиение . Множества и определяются формулами (4.16).

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

Теперь

,(4.30)

где — это условная    вероятность, и, следовательно, в соответствии с традицией ее можно записать в виде . Для детерминированных систем можно переписать в более удобном виде

,(4.31)

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

.(4.32)

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

К.Р. № 11

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

 

Лекция 12

4.8 Переход от систем данных к системам с поведением

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

1.  дана конкретная система х, определенного иерархического типа;

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

3. набор соответствующих требований Q относительно неких свойств систем из множества Y, причем одним из этих требований является требование, чтобы данная система х была аппроксимирована как можно точнее системой более высокого типа и требуется определить YQ — подмножество Y, такое, чтобы любая система из YQ удовлетворяла всем требованиям, определенным в наборе Q.

Набор требований Q может состоять из:

1)   подмножества множества Y, определенного АСНИ (как выбор по умолчанию);

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

3)   требование, чтобы степень неопределенности при порождении данных системой с поведением из подмножества YQ была как можно меньшей;

4)   требованием, чтобы система из подмножества YQ была как можно более простой;

5)  предпочтения требования 2 требованиям 3 и 4.

В этой общей формулировке требование 1 сводится к определению множества допустимых масок.

4.9 Особенности переходов, в зависимости от свойств параметрического множества

Если параметрическое множество не упорядочено, то понятие параметрического соседства не определено, и, следовательно, существует только одна осмысленная маска. Эта маска, определяемая тождественным правилом сдвига; она называется маской без памяти. Поскольку в этом случае имеется только одна приемлемая маска, задача оказывается довольно тривиальной [требования 3, 4 и 5 просто неприменимы]. Эта задача сводится к определению для заданных данных функции распределения вероятностей, удовлетворяющих требованию 2. Она решается полным перебором данных с помощью маски без памяти (в данном случае порядок выбора не важен) и определения для каждого состояния выборочных переменных с (в данном случае они совпадают с основными переменными) числа N(c) их появлений в данных. Числа N (с) для всех обычно называются частотами состояний с. Они используются для вычисления по некоторым правилам соответствующих функций вероятностей или возможностей.

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

.(4.33)

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

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

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

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

4.10 Особенности построения масок

Если рассматриваемая маска представляет собой один столбец (маска без памяти), то выборки по всем значениям параметра являются полными. Однако, если маска состоит из более чем одного столбца, то некоторые выборки в начале и конце параметрического множества (левый и правый края матрицы данных) окажутся неполными (см. рис. 4.2 и 4.3). Точнее, число неполных выборок для каждого края матрицы данных равно числу столбцов в маске минус 1. Число столбцов в маске М будем называть глубиной маски и обозначать . Тогда

,(4.34)

где операторы max и min применены ко всем целым . Так, например, для маски, определенной на рис. 4.1, , для масок без памяти .

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

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

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

,(4.35)

где .

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

4.11 Содержательные подмаски

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

(ml) в подмаску входит по крайней мере один элемент из каждой подмаски , определенной уравнением (4.10) (т. е. один элемент из каждой строки М-матрицы);

(m2) в подмаску должен быть включен по крайней мере один элемент с правилом сдвига (крайний правый элемент из М-маски).

Требование ml необходимо для покрытия заданной системы данных, т. е. для того, чтобы гарантировать, что любая базовая переменная из заданной системы данных была бы включена в любую из систем с поведением из ограниченного множества Yr. Требование m2 препятствует дублированию эквивалентных подмасок, т. е. подмасок, преобразуемых одна в другую только с помощью добавления константы к правилу сдвига  (сдвиг ряда в М-маске).

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

.(4.36)

Первый член выражения  (4.36)  задает число подмасок М, удовлетворяющих условию ml, а второй член — число    масок, нарушающих условие m2. В табл. 4.1 приведены значения при п, .

Таблица 4.1.  Число содержательных масок , вычисленное  по формуле (3.36)

 

n

1

2

3

4

5

6

7

8

9

10

1

1

2

4

8

16

32

64

128

256

512

2

1

8

40

176

736

3,008

12,160

48,896

196,096

785,408

3

1

26

316

3,032

26,416

220,256

4

1

80

2,320

48,224

872,896

5

1

242

16,564

742,568

6

1

728

116,920

7

1

2,186

821,356

8

1

6,560

9

1

19,682

10

1

59,048

 

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

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

1. фиксация   множества  порождаемых  выборочных  переменных;

2. фиксация числа выборочных переменных;

3. фиксация верхней границы числа выборочных переменных;

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

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

К.Р. № 12

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

Лекция 13

4.12 Меры нечеткости

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

,(4.37)

Она измеряет нечеткость в единицах, называемых битами.

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

Легко видеть, что

,(4.38)

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

,(4.39)

называется нормализованной энтропией; понятно, что

, (4.40)

В нашем случае множествами выходов являются множества а распределения вероятностей представляются функциями поведения , определяемыми соответственно формулами  (4.11),  (4.17), (4.27),  (4.30). Для упрощения записи опустим индексы В и GB, а также знак  ^ .   Таким образом,

,(4.41)

обозначают вероятности, определяемые соответственно формулами (4.11), (4.17), (4.27), (4.30); смысл любого из этих обозначений однозначно определяется заключенными в скобки аргументами. Кроме того, определим безусловные вероятности

, (4.42)

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

,(4.43)

,(4.44)

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

, (4.45)

Условные вероятности, характеризующие процесс порождения данных, связаны с основными (совместными) и безусловными вероятностями следующим образом:

;(4.46)

.(4.47)

Первая формула описывает эту связь для    нейтральных, а вторая — для направленных систем.

4.13 Методы вычислений нечеткости

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

. (4.48)

Это значение определяет степень недетерминированности данной нейтральной порождающей системы с поведением.

Для направленных систем порождающая нечеткость  вычисляется по формуле

,(4.49)

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

где    вероятности и  вычисляются по заданным вероятностям согласно формулам (4.45) и (4.47).

Формулы (4.48), (4.49) и (4.50) можно заменить другими, более удобными для вычисления. Например, уравнение (4.48) можно модифицировать следующим образом:

,(4.51)

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

(4.52)

Точно так же уравнения (3.49) и (3.50) можно заменить соответственно уравнениями

(4.53)

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

 ,(4.54)

Пример 4.2. На рис. 4.5,а показана    вероятностная    функция поведения для четырех выборочных переменных каждая с двумя состояниями — 0 и 1. Состояния с нулевой вероятностью в таблице не приводятся. Выборочные переменные определены через две базовые переменные с помощью маски, изображенной на рис. 3.7,а. Поскольку выборочные переменные суть сдвиги одной и той же базовой переменной, распределения вероятностей их состояний должны быть одинаковы; они и в самом деле одинаковы; оба имеют вероятности 0.7 и 0.3 соответственно для состояний 0 и 1. Аналогично переменные (сдвиги) имеют одинаковое распределение вероятностей: 0.6 и 0,4 соответственно для состояний 0 и 1. Следовательно, для данной маски приведенная функция распределения вероятностей является корректной функцией поведения.

Если данная система интерпретируется как нейтральная, ее порождающая нечеткость может быть вычислена по формуле (4.52). Для первого члена формулы мы имеем

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

Рис. 4.5 Вероятностная нейтральная система

Для другого порядка порождения (рис. 4.5,г) мы получим

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

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

Предположим теперь, что  интерпретируется  как входная переменная и что по функции поведения на рис. 4.5,а определена соответствующая направленная система. Теперь для вычисления порождающей нечеткости можно воспользоваться формулой (4.53). Нечеткость уже была вычислена раньше;зависит от порядка порождения. В любом случае множество Е представляется состояниями переменныхпредставляется или состояниями (в порядке возрастания параметра) или состояниями (в порядке убывания параметра). В первом случае нечеткостьсвязана с переменными

Во    втором    случае она    представляет    нечеткость  переменных:

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

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

Ситуация при порождении состояний слева направо, включая значения для каждого состояния е, показана на рис. 4.6,в.

Из формулы (4.53) получим

Другой порядок порождения изображен на рис.  4.8,г. Для него имеем

Рис. 4.6 Вероятностная направленная система

К.Р. № 13

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

Лекция 14

4.14 Выбор подходящих систем с поведением

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

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

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

(4.55)

так что

(4.56)

где а — некая агрегирующая функция, определяемая характером функции. Например,

(4.57)

где — распределение вероятностей.

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

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

Пример 4.3. Определим проекцию вероятностной функции поведения, приведенной на рис. 4.5,а  для . Применив формулу (4.57) для вероятностной функции, получим:

4.15 Упорядочение по сложности и нечеткости

Для заданной системы данных D и наибольшей допустимой маски М требование соответствия приводит к ограниченному множеству

(4.58)

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

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

Что касается меры сложности, то тут возможно много вариантов. Возьмем для примера простую, но содержательную меру, которую часто используют в АСНИ  — размер (мощность) маски.

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

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

(4.59)

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

Пример упорядоченности по сложности и упорядоченности подмасок для наибольшей допустимой маски М при n=3 и приведен на рис. 3.10. При этом предполагается, что данные порождаются слева направо. Все содержательные подмаски изображаются своими матрицами и помечены в левом верхнем углу своими идентификаторами i. По сложности они разбиты на четыре группы. Маски с одинаковой сложностью расположены на одном уровне. Например, маски с идентификаторами 2—7 образуют группу со сложностью 5, маски 8—19 — другую группу со сложностью 4 и т.д. С точки зрения упорядоченности по сложности любая маска некоторого уровня является непосредственным преемником любой маски ближайшего более высокого уровня и непосредственным предшественником любой маски ближайшего более низкого уровня. На рис. 4.7 стрелками показано упорядочение по подмаскам. Из этого примера видно, что упорядочение по сложности — это связное квазиупорядочение (рефлексивное и транзитивное отношение, определенное для любой пары систем).

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

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

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

(4.60)

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

,(4.61)

для некоторых . Следовательно, объединенное упорядочение — это общего вида квазиупорядочение (рефлексивное и транзитивное отношение) на .

Рис. 4.7 Содержательные маски для классифицированные согласно упорядоченности по сложности подмасок

Рис. 4.8

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

(а) более сложна и более детерминирована, чем или менее сложна и менее детерминирована, чем. Формально

(4.62)

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

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

Предположим сначала, что . Тогда имеется восемь содержательных масок, которые вместе с их упорядочением подмасок и указанием трех уровней сложности изображены на рис. 4.8,а. После выполнения исчерпывающей выборки для наибольшей приемлемой маски по определенной формуле, по частотам N(c) вычисляются вероятности , а порождающая нечеткость вычисляется или по формуле (4.48). Если для вычисления вероятностей используется формула (4.31), то порождающая нечеткость равна 1.11. Затем для остальных семи содержательных масок по формуле (4.57) определяются соответствующие проекции и вычисляются их порождающие нечеткости. Результаты этих вычислений показаны на рис. 4.8,б (в правом нижнем углу масок). На рис. 4.8,б также изображено упорядочение масок по нечеткости. В этом примере упорядочение является полным, поскольку значения нечеткости у всех разные. Объединенное упорядочение по сложности и нечеткости (3.60) изображено на рис. 4.8,в. Как мы видим, минимальными с точки зрения объединенного упорядочения являются маски

Рис. 4.9 Подходящие системы с поведением из примера 4.4

с идентификаторами  1, 2, 6. Следовательно,. Предположим теперь, что =3. Тогда согласно формуле (4.36) имеется 40 содержательных масок. После их обработки, аналогичной обработке для случая , мы получим пять подходящих систем с поведением, маски которых, значения сложности и порождающие нечеткости приведены на рис. 4.9,а. Оставшиеся 35 масок хуже с точки зрения их сложности, как и с точки зрения четкости, и, следовательно, их вовсе не нужно рассматривать. Рис. 4.9,а — это типичный пример ответа АСНИ. При соответствующих запросах могут также выдаваться различные дополнительные характеристики, множества решений, такие, как график зависимости нечеткости от сложности, изображенный на рис. 4.9,б.

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

К.Р. № 14

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

Лекция 15

4.16 Системы с изменяющимися состояниями

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

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

(1) к ST-системам неприменимо разделение выборочных переменных на порождаемые и порождающие, и

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

Для нейтральных систем аналогами функций поведения определяем формулами (4.11), (4.20), (4.17), являются следующие ST-функции:

(4.63)

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

, (4.64)

где —условная вероятность того, что при текущем состоянии с следующим состоянием будет состояние ;    будем    поэтому    использовать    общепринятую    запись :                      

 (4.65)

где, т. е. следующее состояние однозначно определяется текущимсостоянием с; функция специального вида (4.65) применима, разумеется, только к детерминированным системам. Будем  называть порождающими ST-функциями.

Аналогами нейтральных систем с поведением являются соответственно ST-система

,  (4.66)

и порождающая ST-система

 (4.67)

где I, M иимеют тот же смысл, что в системах с поведением.

Для заданных системы данных и маски ST-функция fST хорошо согласующаяся с системой данных и маской, может быть определена с помощью полной выборки данных аналогично тому, как это делалось для функции поведения fB. Единственное отличие состоит в том, что в результате выборки получаются частоты пар последовательных состояний, а не частоты N(c) отдельных состояний.

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

  (4.68)

и, следовательно,

 (4.69)

что и определяет равновесие переходов.

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

тогда и только тогда, когда,  (4.70)

если данные порождаются в порядке возрастания параметра, или

тогда и только тогда, когда,  (4.71)

если данные порождаются в обратном порядке.

Маски используются вместе для описания пар состояний.

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

для заданной маски М, если  и  и, то для всех целых, таких, что

Это значит, что маски в ST-системах не должны содержать «пробелы», подобные элементам на рис. 4.1. Маски, удовлетворяющие этому дополнительному требованию, будем называть компактными масками.

Для обоснования этого требования предположим, что маска М ST-системы некомпактна. Тогда существует по крайней мере одна пара элементов из маски М, скажем пара , , такая, что,

(4.72)

идля всех. Из (4.70) имеем

(4.73)

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

>,(4.74)

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

Рис. 4.10. Пример несогласованности или неполноты ST-систем с некомпактными масками

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

Иллюстрацией к доказательству того, что маски с «пробелами» недопустимы в ST-системах, служит рис. 4.10; компонент следующего состояния с' при значении параметра t+1 не может быть ни определен из состояния с в момент времени t (рис. 4.10,в), ни порожден с помощью ST-функции, так как уже порожден при значении параметра t—3 (рис. 4.10,а).

Удобно представлять ST-функции (4.63) и (4.64) в виде квадратных матриц, строки и столбцы которых связаны соответственно с с и. Элементами этих матриц являются значения соответственно или

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

Обычно в состав аппаратных мониторов входят счетчики, которые в процессе сбора данных или считают число происшедших событий (режим счета), или измеряют длительность событий (временной режим). Это значит, что обычно аппаратный монитор предоставляет исследователю не фактические данные, а обобщенные. Например, монитор определяет, что центральный процессор (ЦП) вычислительной системы был загружен в течение 43% времени наблюдения, что канал был занят в 15% всех наблюдений, но не дает фактической последовательности событий, которые бы можно было затем обрабатывать и анализировать.

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

Согласно концепции АСНИ все наблюдения должны быть зафиксированы, а затем обработаны любым подходящим способом. В данном примере по времени было сделано 409610 наблюдений для четырех переменных v1, v2, v3, v4. Каждая переменная имела два состояния 0 и 1, характеризующие состояние конкретного компонента аппаратного обеспечения: 0 означает, что компонент был неактивен во время наблюдения, а 1 — что активен. Переменная  описывает работу ЦП, а остальные три переменных — работу трех важных каналов связи системы. Для получения вероятностной ST-функции из этого огромного набора данных, превышающего 1,6 млн. бит, с помощью маски без памяти была сделана выборка для двух последовательных состояний. Это дало 15 состояний (см. табл. 4.2,а) и 11З переходов. Состояния 7—15 появляются очень редко: вероятность того, что система находится в одном из этих состояний 0.009. Если для упрощения ST-функции, объединить эти состояния в одно, что удобно для исследователя, получится матричное представление порождающей ST-функции, приведенное в табл. 4.2,б. Элементами матрицы являются условные вероятности . Обозначение ~0 используется для вероятностей, которыми можно пренебречь; через 0 обозначены переходы, которые вообще не наблюдались. В матрице подчеркнуты элементы, соответствующие переходу из состояния снова в это состояние. В табл. 4.2,б также приведен вектор-столбец значений функции поведения при той же маске (маска без памяти),

Таблица 4.2 ST-функция для исследования по оценке производительности вычислительной системы

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

,(4.75)

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

К.Р. № 15

 Опишите ST-функцию для системы с изменяющимися состояниями.

Лекция 16

4.17 Взаимосвязь ST-систем и систем с поведением

Любую ST-систему легко можно преобразовать в изоморфную систему с поведением. Чтобы показать, как это делается, возьмем произвольную ST-систему

(4.76)

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

Рассмотрим теперь систему с поведением

(4.77)

гдеопределяется через М следующим образом:

(4.78)

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

,(4.79)

где состояние состоит из с и порождаемой части, назовем ее. Таким образом, функция поведения эквивалентна ST-функции при однозначном соответствии

(4.80)

где тогда и только тогда, когда .

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

(4.79)

Можно аналогично тому, как это было показано для М+, показать, что система с поведением

,(4.80)

изоморфна ST-системе, определенной для той же представляющей системы I и маски М.

Соответствие между масками М,и масками М,показано соответственно на рис. 4.11а и б. На рисунке также показано однозначное соответствие и его аналог для маски и

Для заданной системы с поведением

(4.81)

Изоморфная ST-система  при той же представляющей системе I существует только тогда, когда М — компактная маска и для любой подмаски . Если эти условия выполнены, то понятно, что ST-система(4.82)

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

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

(4.83)

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

(4.84)

где — порождающие условные вероятности;

(4.85)

где.

Изменяющими состояния аналогами для направленных систем с поведением будут соответственно направленная ST-система

(4.86)

 и направленная порождающая ST-система

(4.87)

где и определяются так же, как и для систем с поведением.

Рис. 4.11. Изоморфизм между системами с поведением и ST-системами

Рис. 4.12. Трехмерный массив, представляющий направленную ST-систему

Функции (4.83) и (4.84) удобно представлять в виде массивов квадратных матриц (трехмерных массивов) по одной матрице для каждого условия . Удобны также диаграммы, подобные диаграммам для нейтральных ST-систем. Для направленных систем связи на диаграммах помечаются не только значениями соответствующей ST-функции, но и условиями . Функции (4.85) можно представлять в виде матриц, строки которых соответствуют состояниям е, столбцы — состояниям , а элементами являются соответствующие состояния . Эти функции представляются также в виде диаграмм, таблиц и в некоторых случаях с помощью алгебраических формул.

Пример 4.6. На рис. 4.12 приведена простая направленная ST-система (без интерпретации). Ее представляющая система состоит из входной переменной  и выходной переменной , каждая имеет два состояния 0 и 1. Маска системы М показана на рис. 4.12,а, а на рис. 4.12,б приведены соответствующие компоненты состояний, порожденные двумя ее последовательными положениями на матрице данных. На рис. 4.12,в и г показаны соответственно функции и в виде трехмерных массивов. В данном примере массив состоит из двух матриц.

К.Р. № 16

Приведите пример перехода от некоторой ST-системы к изоморфоной системе с поведением.

Лекция 17

4.18 Виды порождающих систем

системы с поведением

  1.  базовые-
  2.  уравнение (4.12)—нейтральные;
  3.  уравнение (4.28)—направленные;
  4.  порождающие:
  5.  уравнение (4.19)—нейтральные;
  6.  уравнение (4.32)—направленные;

ST-системы

  1.  базовые:
  2.  уравнение (4.66) —нейтральные,
  3.  уравнение (3.93)—направленные;
  4.  порождающие:
  5.  уравнение (4.86) — нейтральные;
  6.  уравнение (4.87)—направленные.

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

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

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

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

1. упорядоченность   параметрического  множества,  что  позволяет ввести важное понятие маски;

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

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

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

Отличиями, относящимися к порождающим системам, но не к системам данных и исходным системам, являются:

1. детерминированность и недетерминированность систем;

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

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

4.19 Упрощение порождающих систем

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

Существует два основных метода одновременного упрощения систем данных и соответствующих порождающих систем:

1) упрощение за счет исключения некоторых переменных из соответствующей подобной системы;

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

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

или как     (4.88)

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

,(4.89)

определенной уравнением (4.57).

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

(4.90)

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

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

Разрешающие формы, определенные на каком-то множестве состояний , могут быть упорядочены с помощью обычного отношения уточнения, определенного на разбиениях данного множества. Хорошо известно, что такое отношение уточнения является отношением частичного порядка и образует решетку. Для двух заданных разбиений, скажем X и У, определенных на одном и том же множестве, будем говорить, что X является уточненным разбиением Y тогда и только тогда, когда для любой группы х из X существует группа у из У, такая, что . Если X, уточняющее разбиение У, то У называется укрупненным разбиением X. Решетку разрешающих форм, определенных на множестве состояний , будем называть разрешающей решеткой и обозначать . Любая разрешающая решетка множества состояний может быть определена или в виде     

(4.91)

или в виде    

(4.92)

где и обозначают соответственно произведение и сумму разбиений.

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

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

 (4.93)

Ниже показано огромное число разрешающих форм даже для небольшого числа состояний:

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

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

(4.94)

Очевидно, что эта решетка для m состояний изоморфна булевской решетке для упорядочения подмножеств любого множества из m—1 элемента. В следующей таблице приводятся значения , вычисленные по формуле (3.94); в этом случае число разрешающих форм существенно меньше, чем в случае неупорядоченных множеств состояний:

Число содержательных упрощений снова равно

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

Рис. 4.13. Решетки разрешающих форм.

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

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

(4.95)

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

(4.96)

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

(4.97)

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

(4.98)

 

Требования, упрощающие порождающие системы:

1)   чтобы системы были как можно проще;

2)   чтобы степень порождающей нечеткости систем была как можно меньше.

Будем называть требование 1 требованием простоты, а требование 2 требованием четкости.

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

Алгоритмы формализации порождающих систем

Системы с поведением

  1.  Определяется правило сдвига (Если параметрическое множество полностью упорядочено ).
  2.  Определяются выборочные переменные , где . обозначает состояние выборочной переменной при значении параметра w, а  — состояние переменной   при значении параметра .
  3.  Определяется маска . Для введения выборочных переменных определяется функция .
  4.  Определяется функция поведения , где . , если состояние с имеет место быть, и в противном случае.
  5.  Определяется система с поведением .

Порождающие системы с поведением

  1.  Определяются подмаски и маски М. Порождаемая подмаска и порождающая подмаска . - маска порождения.
  2.  Для удобства определяются функции . Множества состояний и соответственно порождаемых и порождающих переменных
  3.  Определяется порождающая функция поведения .
  4.  Определяется порождающая система с поведением .

Для недетерминированных систем с поведением

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

Направленные системы с поведением

  1.  Определяются подмаски и маски  М. Пусть подмаска   определяет выборочные переменные, задаваемые средой, а подмаска   — остальные. - маска направленной системы с поведением.
  2.  Для удобства определяются функции. Также .
  3.  Определяется функция поведения .
  4.  Определяется направленная система с поведением .

Направленные порождающие системы с поведением

  1.  Порождающая маска для направленной системы с поведением . рассматривается как разбиение .
  2.  Определяется функция поведения .
  3.  Определяется направленная порождающая система с поведением .

Системы с изменяющимися состояниями

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

2. Определяются аналоги нейтральных систем с поведением, ST-система  , и порождающая ST-система . Где , и имеют тот же смысл, что в системах с поведением.

К.Р. № 17

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

Лекция 18

Исследование и проектирование при помощи АСНИ

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

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

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

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

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

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

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

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


 

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

81312. Поняття, види, зміст і форма виконавчого документа 28.75 KB
  Відповідно до цього Закону підлягають виконанню державною виконавчою службою такі виконавчі документи: виконавчі листи що видаються судами і накази господарських судів у тому числі на підставі рішень третейського суду та рішень Міжнародного комерційного арбітражного суду при Торговопромисловій палаті і Морської арбітражної комісії при Торговопромисловій палаті...
81313. Стадії виконавчого провадження. Відкриття виконавчого провадження 36.12 KB
  Відкриття виконавчого провадження. Процес виконавчого провадження завжди складається із послідовності дій державного виконавця від відкриття виконавчого провадження до його закінчення. Перша стадія виконавчого провадження.
81314. Органи і посадові особи, які здійснюють виконавче провадження 26.83 KB
  Примусове виконання рішень покладається на державну виконавчу службу яка входить до системи органів Міністерства юстиції України. Примусове виконання рішень здійснюють державні виконавці визначені Законом України Про державну виконавчу службу далі державні виконавці. За наявності обставин що ускладнюють виконання рішення або у разі виконання зведеного виконавчого провадження у встановленому Міністерством юстиції України порядку можуть утворюватися виконавчі групи до складу яких включаються державні виконавці одного або кількох органів...
81315. Підстави для відкриття виконавчого провадження. Вимоги до виконавчого документа 26.92 KB
  У заяві про відкриття виконавчого провадження стягувач вправі зазначити відомості що ідентифікують боржника чи можуть сприяти примусовому виконанню рішення рахунок боржника місце роботи чи отримання ним інших доходів місцезнаходження його майна тощо а також шляхи отримання ним коштів стягнутих з боржника. У заяві про відкриття виконавчого провадження щодо виконання рішення про майнове стягнення стягувач має право просити державного виконавця накласти арешт на майно та кошти боржника та оголосити заборону на його відчуження. У...
81316. Відводи державного виконавця, експерта, спеціаліста, перекладача, суб’єкта оціночної діяльності - суб’єкта господарювання 25.8 KB
  Державний виконавець, експерт, спеціаліст, оцінювач, перекладач не можуть брати участі у виконавчому провадженні і підлягають відводу, якщо вони є близькими родичами сторін, їх представників або інших осіб, які беруть участь у виконавчому провадженні, або заінтересовані в результаті виконання рішення, або є інші обставини, що викликають сумнів у їх неупередженості.
81317. Місце виконання судових рішень та рішень інших юрисдикційних органів (посадових осіб) 26.46 KB
  Виконавчі Виконавчі дії проводяться державним виконавцем відповідного органу державної виконавчої служби який розташований: за місцем проживання роботи боржника фізичної особи або за місцезнаходженням його майна; за місцезнаходженням постійно діючого керівного органу або майна боржника юридичної особи; за місцем здійснення певних дій які зобовязаний вчинити боржник за відповідним рішенням суду або іншого органу посадової особи. Право вибору місця виконання між кількома органами державної виконавчої служби які можуть учиняти...
81318. Строки пред’явлення виконавчих документів до виконання 26.66 KB
  Виконавчі документи можуть бути предявлені до виконання в такі строки: виконавчі листи та інші судові документи протягом трьох років; посвідчення комісій по трудових спорах протягом трьох місяців; постанови органів посадових осіб уповноважених розглядати справи про адміністративні правопорушення протягом трьох місяців; інші виконавчі документи протягом року якщо інше не встановлено законом. Строки встановлюються: для виконання рішень і вироків судів у частині майнових стягнень з наступного дня після набрання рішенням законної...
81319. Прийняття виконавчого документа до виконання. Строки здійснення виконавчого провадження 27.87 KB
  Строки здійснення виконавчого провадження. Державний виконавець зобовязаний прийняти до виконання виконавчий документ і відкрити виконавче провадження якщо не закінчився строк предявлення виконавчого документа до виконання і цей документ відповідає вимогам статті 18 Закону та предявлений до виконання до органу державної виконавчої служби за належним місцем виконання рішення. У разі помилкового надходження виконавчих документів не за територіальністю або підвідомчістю державний виконавець виносить постанову про відмову у відкритті...
81320. Підстави та порядок відмови у відкритті виконавчого провадження 25.99 KB
  Про відмову у відкритті виконавчого провадження державний виконавець виносить постанову протягом трьох робочих днів, а за рішенням, що підлягає негайному виконанню, - не пізніше наступного робочого дня з дня надходження виконавчого документа і не пізніше наступного дня надсилає її заявникові разом з виконавчим документом.