Переход от систем данных

Лекция 12

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

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

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

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

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

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

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

Рекомендуемые материалы

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

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

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

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 Содержательные подмаски

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

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

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

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

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

.(4.36)

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

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

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

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

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

Люди также интересуются этой лекцией: 3. Управление ЧС.

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

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

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

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

К.Р. № 12

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