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

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

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

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

ДАНО:

множество X рассматриваемых систем;

a b c множество отношений порядка на X.

,, МНОЖЕСТВО РЕШЕНИИ:

* * X = { x X |( y X )( y x x y )}, s * где - объединенный порядок предпочтения на X, определенный для всех х, уХ следующим образом:

* a x y тогда и только тогда, когда x y, a c и x y, и x y, и...

В процессе решения задачи реконструкции необходимы три набора процедур:

1) процедуры порождения всех нужных реконструктивных гипотез;

2) процедуры оценки и сравнения порожденных реконструктивных гипотез с точки зрения целей задачи реконструкции;

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

На рисунке Г.25 показано, каким образом эти три набора процедур объединяются в единый процесс решения. Ядром процесса является порождение всех подходящих реконструктивных гипотез. Удобно это делать, порождая соответствующие структуры, которые затем интерпретируются как реконструктивные гипотезы для заданной обобщенной системы. Интерпретация эта сводится к установлению соответствия между переменными обобщенной системы и целыми числами, которыми идентифицированы узлы структур, а также к вычислению, если нужно, проекций обобщенной функции поведения. Порожденные структуры можно разными способами сократить, что уменьшает время вычислений и их цену, а также, возможно, и по другим соображениям. Например, можно выбрать подмножество соответствующих G-, С- или L-структур или ограничиться рассмотрением только тех уровней уточнения (классов l-эквивалентности), для которых потеря информации не превышает некоторого заданного пользователем значения. Таким образом, процесс порождения реконструктивных гипотез может быть ограничен либо набором рассматриваемых структур, либо ограничениями на способ порождения.

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

Как уже говорилось выше, порождение структур также может быть организовано на нескольких уровнях вычислений. Так, например, RСпроцедура может быть использована на глобальном уровне для работы с классами r-эквивалентности G-структур. Модифицированная RG-процедура, в которой на шаге 3 вместо |k S | 2 используется условие |kS| > 2, которое затем на локальном уровне для порождения непосредственных уточнений некоторых важных классов r-эквивалентности, определенных на глобальном уровне.

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

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

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

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

Пример Г.19. Рассмотрим возможностную систему с поведением, определенную на данных, полученных путем наблюдения за четырьмя переменными, характеризующими работу вычислительного комплекса. Целью является нахождение условий, при которых загрузка ЦП (центрального процессора) оказывается высокой. Наблюдаемые значения переменных представляют загрузку ЦП и трех каналов, скажем каналов Kl, К2 и КЗ.

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

Для определения на этих данных системы с поведением исследователь решил использовать возможностную методологию без памяти. Из 16 возможных состояний переменных в действительности наблюдались только 6.

Поскольку эти состояния наблюдались примерно с одинаковыми частотами, исследователь решил, что функция поведения должна только отличать далее наблюдаемое и ненаблюдаемое состояния. Таким образом, он объявил, что единственно возможными состояниями являются наблюдаемые ранее состояния. Эти состояния имеют возможность, равную 1, остальные состояния (т. е. которые не наблюдались) Ч равную 0. Полученная функция поведения f приведена в таблице Г.13. Она дает исследователю понимание важной вещи: при некоторых изменениях в организации работы компьютера загрузка ЦП может поддерживаться по высоким уровням, если три канала загружены одним из следующих способов:

K1 К2 КЗ н в н в н н н в в Для подтверждения этой идеи исследователь решил изучить реконструктивные свойства обобщенной функции поведения f. Его интересовали только реконструктивные гипотезы без потери информации.

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

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

Чтобы определить, может ли f вообще быть реконструирована по каким-либо проекциям, полезно сначала рассмотреть реконструктивные гипотезы, основанные на использовании С-структур. С помощью RС-процедуры мы получаем шесть реконструктивных гипотез на первом уровне уточнения. Их схемы и соответствующие графы изображены на рисунке Г.26,а. Каждая гипотеза помечена номером в левом верхнем углу соответствующей клетки, а ее несмещенные реконструкции f h (hN6) приведены в таблице Г.13. Гипотезы 1, 4 и 6 в точности реконструируют f и являются перспективными кандидатами на включение в множество решений. Каждая из оставшихся гипотез дает по четыре некорректных состояния обобщенной системы. Они также имеют следующее информационное расстояние, вычисленное по формуле (Г.42):

(log210 - log26)/log216 = (3.32 - 2.58)/4 = 0.185.

Несмещенные реконструкции вычисляются, разумеется, с помощью возможностного варианта процедуры соединения. Для реконструктивной гипотезы 1 она показана на рисунке Г.27. Связями на диаграмме показаны те состояния отдельных трехмерных проекций, возможности которых равны 1. Результатом процедуры соединения, которая выполняется только один раз, являются все четверки из Н и В, которые лежат на путях на диаграмме, ЦП 1 ЦП КЦП КККК2 ККК2 КD(f, f 1) = D(f, f 2) = 0.К4 ЦП КЦП Ка) К2 ЦП К2 КК2 ККD(f, f 2) = D(f, f 4) = б) Рисунок Г.26 - Рассматриваемые в примере Г.19 реконструктивные гипотезы К2 КD( f, f 10 ) = 0.соединяющих левые и правые узлы.

При изучении трех удачных реконструктивных гипотез, изображенных на рисунке Г.26,а, видно, что все они содержат подсистему, основанную на переменных ЦП, К1 и К2. На рисунке Г.26,а эта подсистема изображена заштрихованным прямоугольником.

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

Как следует из таблицы Г.13, их несмещенные реконструкции равны. Происходит это из-за того, что двумерные проекции не содержат никакой информации. Данная рекон-струкция не являРисунок Г.27 - Иллюстрация к ется безупречной: вместо шести репроцедуре соединения реконстконструируется восемь состояний, а их руктивной гипотезы 1, изображенрасстояния равны 0,105. Это согласно ной на рисунке Г.условиям задачи является неприемлемым.

Рассматривать укрупнения этих трех удачных реконструктивных гипотез нет необходимости, поскольку они явно хуже: по определению, они являются менее уточненными, а их расстояния не могут быть меньше расстояний успешных гипотез (то есть не могут быть меньше 0). Следует, однако, рассмотреть укрупнения неудачных гипотез 2, 3 и 5 (смотри рисунок Г.26,а). Воспользовавшись рисунком Г.18, на котором изображена соответствующая решетка G-структур, можно установить, что рассматриваемые структуры - это G-структуры, принадлежащие классу изоморфизма GГ.

Таблица Г.13 - Возможностные функции поведения для обобщенной системы и некоторых несмещенных реконструкций из примера Г.ЦП К1 К2 К3 f f1=f4=f6 f2 f3 f5 f7=f8=f9 fН Н Н Н 1 1 1 1 1 1 Н Н Н в 1 1 1 1 0 1 Н Н в Н 0 0 1 0 0 0 Н Н в в 0 0 1 1 1 0 Н в Н Н 0 0 0 1 0 0 Н в Н в 0 0 0 0 1 0 Н в в Н 0 0 0 0 0 1 Н в в в 1 1 1 1 1 1 в Н Н Н 0 0 1 1 1 0 в Н Н в 0 0 1 0 1 0 в Н в Н 1 1 1 1 1 1 в Н в в 1 1 1 1 1 1 в в Н Н 1 1 1 1 1 1 в в Н в 0 0 0 0 0 1 в в в Н 0 0 0 0 1 0 в в в в 0 0 А 1 0 0 Из каждой подсистемы, изображенной на рисунке Г.26,а, за исключением успешных подсистем, представленных переменными ЦП, К1 и К(на рисунке они заштрихованы), выбираются две подсистемы с двумя переменными. Однако мы знаем, что эти пары подсистем являются неподходящими и что подсистемы из двух переменных информации не добавляют. Следовательно, реконструктивные гипотезы из класса изоморфизма G4 могут быть отброшены без вычисления несмещенных реконструкций и расстояний.

Остается только рассмотреть реконструктивные гипотезы, основанные на G-структурах из класса изоморфизма G3. Поскольку подсистемы, представленные переменными ЦП, К1 и К2, снова должны быть исключены из рассмотрения, то остается только одна гипотеза. Она показана на рисунке Г.26,а, а ее функция поведения f 10 приведена в таблице Г.13. Мы видим, что и эта гипотеза не подходит: ее расстояние равно 0.105, и, следовательно, она должна быть отвергнута.

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

Таким образом, можно" прийти к заключению, что множество решений состоит из изображенных на рисунке Г.26,а реконструктивных гипотез 1, 4 и 6.

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

Пример Г.20. Пример основан на данных по использованию противозачаточных средств до замужества (смотри Г.13). Состояния следующих двоичных переменных были определены на группе из 414 студенток старших курсов университета:

v1 - отношение к внебрачным связям (0 - всегда отрицательное, 1 - не всегда отрицательное);

v2 - обращение в университетскую клинику для предотвращения беременности (0 - да, 1 - нет);

v3 - девственность (0 - да, 1 - нет).

Частоты N(c) отдельных состояний и соответствующая вероятностная функция поведения f приведены в таблице Г.14а.

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