Книги по разным темам Pages:     | 1 |   ...   | 34 | 35 | 36 | 37 | 38 |   ...   | 41 |

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

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

h h 1 / p ( f, f ) = [ f ( c ) - f ( c )|, (Г.39) | p cC где f, f h- соответственно функция поведения заданной системы и несмещенная реконструкция по гипотезе h, a p N - параметр функций расстояния.

При р = 1- это расстояние Хэмминга, при p = 2 - Евклида, при р = - верхняя граница расстояний.

Расстояния по Минковскому вычисляют по точечным разностям h | f ( c ) - f ( c )| распределение вероятностей или возможностей в соответствии с формулой (Г.39). Несмотря на то, что поточечное описание близости f и f h полезно для многих приложений, теоретически оно недостаточно хорошо обосновано.

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

Меру подобной потери информации будем называть информационным h расстоянием и обозначать D(f, f )- Для вероятностных систем она задается хорошо известной формулой 1 f ( c ) h D( f, f ) = f ( c )log, (Г.40) h log | C | cC f ( c ) где константа l/log2|C| Ч нормирующий коэффициент, обеспечивающий выполнение соотношения 0 D(f, f h) 1.

h Поскольку, если f (с) = 0, то f(с) = 0, вероятностное информационное расстояние определено всегда. Это, однако, не метрическое расстояние, так как оно асимметрично, более того, D(f h, f) может быть не определено для некоторых f и f h [когда f h(с) > 0 и f (c) = 0 для некоторого с С].

При применении вероятностного расстояния к порождающей системе с поведением уравнение (Г.40) приобретает следующий вид:

1 f ( g | g ) h D ( f, f ) = f ( g ) f ( g | g )log. (Г.41) G h log | G | gG gG f ( g | g ) Модификация уравнений (Г.40) и (Г.41) для направленных систем с поведением очевидна.

Для возможностных систем информационное расстояние рассчитывается по формуле h 1 | c( f,l ) h D( f, f ) = (Г.42) log c( f,l ), log2 | C | представляющей собой аналог вероятностного информационного расстояния (Г.40) для U - нечеткости.

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

Реконструктивная гипотеза для заданной обобщенной системы с поведением представляет собой набор ее подсистем. Если обобщенная система состоит из n переменных, то число ее подсистем, содержащих по крайней мере одну переменную равно 2n - 1, а общее число наборов таких подсистем, n содержащих не менее одной подсистемы, равно 22 -1 - 1. С ростом n это число| растет очень быстро. Однако без потери общности его можно существенно уменьшить, если рассматривать только неизбыточные; наборы подсистем (смотри раздел Г.3).

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

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

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

юбая реконструктивная гипотеза (равно как и любая обобщенная реконструктивная гипотеза) полностью описывается:

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

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

Для данного множества переменных, скажем множества S, множество структур, представляющих все реконструктивные гипотезы любой обобщенной системы, определенной на S, состоит из семейств подмножеств S, удовлетворяющих условиям неизбыточности и покрытия. Будем для удобства представлять все множества переменных одной мощности, скажем мощности n, общим множеством структур, скажем множеством Gn, определенным на множестве Nn положительных целых чисел. Формально для любого n N Gn = {Gi/Gi P( Nn ),Gi удовлетворяет условиям неизбыточности и покрытия}.

В этом формальном определении через Gi обозначены элементы Gn, являющиеся наиболее общими структурами, рассматриваемыми при решении задачи реконструкции (некие специальные типы этих структур будут введены ниже); индекс i идентифицирует структуры из Gn и обычно i N|G |. Мноn жество Gn тривиально интерпретируется на языке любого множества переменных S, такого, что |S| = n, заданием взаимно однозначного отображения переменных из S на целые из Nn. Будем для удобства структуры из множеств Gn называть G-структурами.

Из некоторых соображений удобно расширить множество Gn до множества G+n всех обобщенных реконструктивных гипотез. Формально для любого nN G+n={Gi|Gi P( Nn ),Gi удовлетворяет условию неизбыточности}.

Несмотря на то, что далее в этой главе основное внимание будет уделяться множествам Gn, все результаты относительно Gn могут быть легко обобщены и на множества G+n.

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

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

Определим сначала естественное упорядочение структур, называемое уточняющим упорядочением. Пусть даны две структуры Gi, Gj&n Будем называть Gi уточнением Gj (и, соответственно, Gj укрупнением Gi) тогда и только тогда, когда для любого x Gi существует y Gj, такое, что x y ; пусть Gi Gj означает, что Gi это уточнение Gj.

Рассмотрим две структуры Gi, Gj&n, такие, что Gi Gj. Тогда Gi называется непосредственным уточнением Gj (a Gj Ч непосредственным укрупнением Gi ) тогда и только тогда, когда не существует Gk&n, такого что Gi&n и Gk Gj. Для заданной структуры GiGn структурное соседство определяется как множество всех непосредственных уточнений и непосредственных укрупнений Gi в &п.

егко видеть, что отношение уточнения определяет частичное упорядочение. Более того, пара ( &п ) определяет решетку, что подтверждают следующие факты: 1) существует универсальная верхняя граница Ч множество (Nn}; 2) существует универсальная нижняя граница - множество {{x}| x Nn }; 3) для любой пары Gi, Gj&n наибольшим общим уточнением является неизбыточный эквивалент множества { x y | x Gi, y Gj }; 4) для любой пары Gi, Gj&n наименьшим общим укрупнением является неизбыточный эквивалент множества Gi Gj. Будем называть эти решетки решетками уточнения G-структур). (по одной для каждого n N ). Отметим, что уточняющее упорядочение применимо и к множествам G+n, что дает решетки (&+, ).

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

Одна такая процедура определяется следующим образом.

Уточняющая процедура для G-структур (или RG-процедура). Заданы Gструктуры Gi={kS|kNq}&n. Для определения всех их непосредственных уточнений 1) положить k = 0;

2) если k

k 3) если |kS| 2, то (Gi-{kS}) XR, где X={x|x S, |x| =|kS| - 1}; иначе перейти на шаг 2;

4) RQ, где Q Ч неизбыточный аналог R, записать Q в качестве непосредственного уточнения Gi, перейти на 2;

5) конец.

Обратите внимание на то, что условие |kS| 2 из шага 3 обеспечивает то, что порождаемые структуры будут удовлетворять условию покрытия;

замена этого условия на условие |kS| l позволяет работать с множествами &+ обобщенных реконструктивных гипотез. Шаг 4 обеспечивает выполп нение условия неизбыточности. Тот факт, что наименьшее возможное изменение делается на шаге 3, т. е. только один элемент Gi изменяется на непосредственно следующие меньшие элементы (подмножества), обспечивает то, что порождаемые структуры являются непосредственными уточнениями Gi.

2 Пример Г.17. Дано Gi= {1S= {1, 2, 3}, S={2, 3, 4}, S={1, 4}}.

Сразу видно, что для всех k N3|k S | 2, и, следовательно, RG-процедуры применимы к любому элементу. Таким образом, имеются три непосредственных уточнения Gi. Множество 1S заменяется на множества {1, 2}, {1, 3}, {2, 3}, однако третье множество является подмножеством и будет исключено на шаге 4; это даст следующее непосредственное уточнение:

{{1, 2}, {1, 3}, {2, 3, 4}, {1, 4}}.

Аналогичная замена 2S дает второе непосредственное уточнение:

{{1, 2, 3}, {2, 4}, {3, 4}, {1, 4}}.

Наконец, множество S заменяется на множества {1} и {4}, которые являются избыточными и будут исключены на шаге 4; отсюда имеем третье непосредственное уточнение:

{{1, 2, 3}, {2, 3, 4}}.

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

окальный уровень вычислений представлен уже описанной RGпроцедурой. Для определения глобального уровня вычислений определим функции rn : Gn Rn,n N, где R - множество симметричных и рефлексивных бинарных отношений, определенных на множестве Nn (они также называются отношениями сравнения, отношениями толерантности или неориентированными графами с циклами), a rn(Gi) Ч бинарное отношение, выполняемое для целых а и b (a, bNn) тогда и только тогда, когда и а, и b принадлежат по крайней мере одному из подмножеств Nn, входящих в Gi. Формально rn( Gi ) = {( a,b )|( x Gi )( a x и b x )}.

Будем элементы Rn называть графами. Однако мы должны помнить, что эти графы не ориентированы (симметричность) и содержат циклы (рефлексивность). Некоторые примеры функций классов r4 и r5 показаны на рисунке Г.15. При изображении этих графов опущены тривиальные циклы в узлах.

G1 G2 r4(G1)=r4(G2) Рисунок Г.15. Примеры функции rп Понятно, что функции rп сюръективны, а при n 3 прообразы могут состоять из более чем одного элемента. Поэтому они индуцируют следующее отношение эквивалентности на соответствующих множествах Gn Gr структур: Gi Gj тогда и только тогда, когда Gt, Gj Gn и rn(Gi) = rn(Gj) для некоторого n N. Если Gi = Gj, то мы говорим, что структуры Gi и Gj r-эквивалентны. Для обозначения классов эквивалентности, индуцируемых rп на &п, будем использовать стандартную запись &п/rп.

Для любого n Nn множество Rп и отношение подмножества (или, иначе, операции объединения и пересечения множеств) определяют булеву решетку. Очевидное взаимнооднозначное соответствие между &п/rп и Rп индуцирует изоморфную булеву решетку на множестве Gn/rn. Этот изоморфизм позволяет нам порождать классы эквивалентности на &п/rп с помощью соответствующих операций на графах из Rп. При этом, однако, желательно, чтобы любой класс эквивалентности из &п/rп был представлен некоей канонической структурой. С этой целью введем для любого n N следующие подмножества &n:

Pages:     | 1 |   ...   | 34 | 35 | 36 | 37 | 38 |   ...   | 41 |    Книги по разным темам