Ограничение когнитивной сложности моделей

Григорьев А. В. Ограничение когнитивной сложности моделей // Прогрессивные технологии и системы машиностроения: Международный сб. научных трудов. — Донецк: ДонГТУ, 2000. — Вып. 10. — С. 49–58.

А. В. Григорьев

ДонГТУ, г. Донецк, Украина

Аннотация

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

Введение

Задача оценки и ограничения когнитивной сложности (КС) моделей имеет ряд известных решений [1,2,3,4,5]. К недостаткам этих работ можно отнести: 1) отсутствие унификации концептуальной модели предметной области (КМПО), положенной в основу представления моделей; 2) выражение КС моделей посредством корреляции с набором отдельных показателей структурной сложности моделей, без учета положений многочисленных теорий сложности моделей [6,7,8,9,10,11]; 3) отсутствие методов автоматического приведения моделей к форме, имеющей допустимый уровень КС. Для преодоления указанных недостатков автором предложено:

1) Унифицированная КМПО [12], ориентированная на многоуровневое представление моделей в САПР, обобщающая ряд известных КМПО;

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

3) Новая мера сложности моделей, являющаяся обобщением известных способов оценки сложности и разработанная в соответствии с особенностями предложенной унифицированной КМПО;

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

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

1) В процессе создания базы знаний о методике проектирования для некоторого класса сложных технических объектов, путем обучения на малом числе примеров (трубопроводов, микропроцессорных систем и т.п.). В этом случае в качестве примера рассматривается некоторый апробированный на практике технический проект (прототип). Прототип, как правило, задан на языке представления, свойственном данной предметной области (чертеж трубопровода, принципиальная схема). Используя адаптированный интерфейс ИО [13] модель из исходной формы представления преобразуется во внутренний формат оболочки. Форма представления модели в таком случае, как правило, предполагает первоначально одноуровневое “необозримое” описание. КС такой модели превышает возможные уровни восприятия человеком (чертеж фрагмента схемы трубопроводов теплоэлектростанции размером 1,5м*1м). Для обеспечения возможности контроля экспертом создаваемой базы знаний и ограничения КС процесса синтеза моделей все вводимые модели должны иметь “обозримое” представление. Следовательно, каждая модель должна быть преобразована к виду, имеющему доступный уровень КС.

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

3) При вводе пользователем модели-прототипа или модели-гипотезы в базу данных САПР либо путем прямого ввода в диалоговом (пакетном) режиме, либо путем редактирования ранее введенной модели.

1 Краткая характеристика метода построения меры КС

Работа является последней в серии статей, посвященных когнитивной сложности моделей. Ранее были разработаны: 1) методика тестирования пользователей САПР для определения шкалы абсолютной КС моделей и границ допустимой КС представления моделей [14]; 2) метод построения формальной меры для оценки когнитивной сложности моделей [15]. Метод построения формальной меры для оценки когнитивной сложности моделей кратко может быть охарактеризован так. Упорядочивание по сложности совокупности отношений, в пределах отдельно взятого формального описания прототипа, выполняется с помощью модифицированного метода диаграмм Хассе [8].

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

\[M = \{ M_i^m\} _{i = \overline {1,{\mathop{\rm Im}\nolimits} } }^{m = \overline {1,W} }.\]

Здесь: \(W\) - число уровней типов отношений, имеющих место в прототипе; \(m\) - номер уровня иерархии отношений; \(i\) – номер отношения в пределах уровня; \({\mathop{\rm Im}\nolimits} \) - число отношений на уровне. Общее число отношений в диаграмме обозначается как \(I\). Структурная сложность \({S_l}\) для объекта-прототипа \(P_l^{},l = \overline {1,Np} \) может быть вычислена по формуле:

\[{S_l} = S_1^W \quad для \quad \forall l:l = \overline {1,Np}.\]

Здесь: \(m = W\) - номер верхнего уровня иерархии отношений, \(i = 1\) – номер единственного отношения верхнего уровня; \(S_1^W\) - сложность прототипа, представленного как замкнутая среда. Сложность прототипа определяется по рекуррентному соотношению:

\[S_i^m = M_i^m*\sum\limits_{j = 1}^{K_i^{m - 1}} {S_j^{m - 1}}\quad , \quad i = \overline {1,I_i^m}.\]

Тут: \(i\) - номер узла \(m\)-го уровня; \(j\) - номер составляющего отношения в узле; \(K_i^{m - 1}\) - число отношений в узле. Всякий узел содержит структуру Nil. При этом для базового 1-го уровня (значений свойств) выполняется \(S_j^1 = 1;\forall j\). Пример состава отношений приведен на рис. 1. Построение меры КС проводится по следующей методике.

Пусть дано:

1) \(A = {{\{A_l\}} _{l = \overline {1,Np} }}\) - совокупность оценок абсолютной КС по шкале для ряда прототипов \({P_o} = {{ \{P_l\}} _{l = \overline {1,Np} }}\), полученные путем тестирования пользователей; данные оценки должны отражать сложность восприятия, проектирования и контроля моделирования моделей объектов;

2) Мера структурной сложности с неизвестными весовыми коэффициентами \(M_i^m\).

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

2 Общая постановка задачи ограничения КС моделей

Пусть дано:

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

• Свойство как совокупность значений \(Д_l=\{д_{li}\}_{i=1}^{N_д}\) , где: - \(д_{li}\) идентификаторы значений свойства \(Д_l\);
• Подблоки данного блока-прототипа \(Б_t \in Б=\{Б_t\}_t\) , где: \(Б_{jt}\)- идентификатор подблока \(Б_t\), входящего в среду; \(t\) - номер в составе множества блоков \(Б\), входящих в среду; \(Б_l\)- внутренняя граница блока прототипа;
• Принадлежность свойства \(Д_l\) границе \(Б_t^e\) блока \(Б_t\), заданное как отношение: \(V_{tl}=(Б_t^e,Д_l)\);
• Граница блока внешняя (внутренняя) как множество отношений принадлежности свойств подблоку \(Б_t\) среды \(S:Б_t^e=\{V_{tl}^e\}(Б_t^y=\{V_{tl}^y\}_l)\);
• Связь \({s_i}\), т.е. причинно-следственное отношение или отношение эквивалентности значений, определенное над парой отношений принадлежности свойств границам блоков: \({s_i} = ({V_{ik}},{V_{ip}})\);
• Среда S, т.е. множество причинно-следственная связей, определенных над множеством подблоков, входящих в среду: \(S =\{s_i\}_{i = \overline {1,N} }\).

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

2) Мера абсолютной КСП (АКСП), включающая:

• Собственно меру АКСП, определенную над множеством отношений;
• Интервал допустимой КСП \(Э_5 \leq КС_p \leq Э_2\) , где \(Э_5\) и \(Э_2\) - точная нижняя и точная верхняя грань предельно допустимой КСП для данной предметной области, выбранного языка описания и конкретного пользователя (группы пользователей);
• N - возможная степень превышения КСП U, обеспечивающая безошибочную работу оператора [4].

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

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

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

2) В случае, если после «действия 1» для оставшихся фрагментов модели нет известного решения, следует выполнить упрощение прототипа автоматически или с участием пользователя, ориентируясь на доступный уровень КС моделей.

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

3 Алгоритм решения задачи

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

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

Критерий близости блоков есть функция, производная от числа эквивалентных отношений различных уровней иерархии. Структура критерия определяется составом и весом отношений, определенных на этапе построения меры КС. В частности, состав эквивалентных отношений может характеризоваться количеством: \({K_s}\) - связей по свойствам; \({K_t}\) - имен в цепочке идентификации типа блока; \({K_d}\) - наименования и типов свойств; \({K_z}\) - значений свойств, заданных в порядке взаимного включения типов свойств (время, пространство, "обычные" свойства).

В этом случае критерий близости приобретет вид:

\[B = \sum\limits_{i = 1}^N {K_i^{}{*_{}}} W_i^{}\]

Тут: \(W_i^{}\) - известные веса когнитивной сложности различных типов отношений. Исходя из данного критерия, может формироваться множество оценок близости для блоков, имеющихся в среде. Блок, имеющий наибольшую по величине меру близости с «пополняемым» блоком, объединяется с ним в единый логический блок.

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

Описание алгоритма.

1) Проверка исходной схемы \(Р\) на предельно допустимую КС. Если условие \(Э_5 \leq КС_р \leq Э_2\) не выполняется, то переходим на пункт 2, иначе – на конец алгоритма, пункт 12.

2) Формирование пустого списка \(S_п\), предназначенного для внесения в него извлекаемых из тела прототипа \(P\) подблоков.

3) Формирование на базе \(S_п\) нового «пустого» блока-аккумулятора \(П\), имеющего пустой список свойств, составляющих внешнюю и внутреннюю его границу и внесение его в \(Б\).

5) Выбор из множества \(Б\) набора блоков \(\{Б_s\}\), такого, что верно

\[ \forall\, B_{s} \in B \setminus S_{z} \]

и выполняется условие максимальной близости \(Б_s\) со списком \(S_п\) по критерию

\[ K\!\left(B_{s} \cap S_{\Pi}\right) = \max_{B_{t}\in B}\, K\!\left(B_{t} \cap S_{\Pi}\right) \tag{1} \]

где: \(\overline \cap \) - операция определения общего подмножества отношений.

Если имеет место множество {Бs}, для которых выполняется (1), например на первом шаге алгоритма, когда список П пуст, то выполняется переход на пункт 6, иначе на пункт 8.

6) Выбор из множества \(\{Б_s\}\), для которых выполняется (1), блока \(Б_s\), для которого степень уменьшения КС блока \(Б\), получаемая за счет удаления блока Бs максимальная среди всех \(Б_i\), принадлежащих \(Б\), т.е.

\[ K\!\left(B \setminus B_{s}\right) = \max_{B_{t}\in B}\, K\!\left(B \setminus B_{t}\right) \]

где: \(\backslash\) - операция удаления общего подмножества отношений.

При этом:

• степень увеличения КС блока \(П\) за счет блока \(Б_s'\) максимальная среди всех \(Б_i\), принадлежащих \(Б\) ;
• критерий близости \(Б_s\) с блоком \(П\) имеет максимальный вес ;
• критерий близости \(Б_s\) со списком \(Б\) имеет максимальный вес .

6) Внесение блока \(Б_s\) в состав списка \(S_п\).

7) Формирование на базе \(S_п\) нового блока-аккумулятора \(П\), имеющего список свойств, составляющих внешнюю и внутреннюю его границу, и внесение его в \(Б\); при этом:

• формируется связи данного блока Бs с подблоками блока П;
• внутренняя и внешняя граница блока П пополняется свойствами, посредством которых блок Бs связан с внешней средой;

8) Изменение состава блоков и связей исходного прототипа \(Р\) с учетом удаления из его состава найденного блока Бs и включения связей с новым блоком \(П\);

9) Если \(S_z=P\) то новый блок \(П\) есть искомый и далее переход на конец алгоритма - пункт 12;

10) Оценка на КС нового блока \(П\): если условие \(Э_5 \leq КС_р \leq Э_2\) выполняется, то идти на выбор следующего вторичного блока - пункт 5, иначе - на пункт 11;

11) Т.к. выбранный нами новый подблок для \(П\) превысил необходимый уровень \((Э_5 \le КС_р)\), то выполняется:

• возврат на предыдущий вариант \(S_п\) и соответствующему ему виду \(Р\) и \(П\);
• внесение блока \(Б_s\) в список запрещенных блоков \(S_z\);
• переход а выбор следующего вторичного блока - пункт 5;

12) Формирование нового «пустого» блока \(П\), имеющего пустой список подблоков и свойств, составляющих внешнюю и внутреннюю его границу, и внесение его в \(Б\).

Выводы

Статья содержит описание метода приведения формального описания моделей к форме, соответствующей требуемым ограничениям на допустимую когнитивную сложность представления моделей. Предлагаемый метод может быть охарактеризован как направленный на решение модифицированной классической задачи о рюкзаке. Эффективность метода определяется повышением качества выполнения стандартных функций моделей, например таких: компактное и наглядное описание системы в целом, оценка правильности представления о системе, получение оценок состояния и механизмов функционирования системы и т.д. Среди мер оценки качества систем с базами знаний улучшают свои показатели такие меры: 1) Устойчивость базы знаний, т.к. количество правил в модуле знаний, связанном с данным блоком, косвенно ограничено "когнитивными" критериями, ограничивающими сложность прототипов; 2. Быстродействие системы представления и обработки знаний, например, при синтезе решений в диалогом режиме сложность вопросов, задаваемых пользователю об особенностях требуемого решения, соответствуют степени компетентности пользователя, что приводит к снижению среднего времени между ответами пользователя. Предлагаемый метод программно реализован средствами DELPHI и соответствующий модуль включен в состав инструментальной оболочки для построения интеллектуальных САПР. Апробация метода проводилась на примере формальных моделей принципиальных схем микропроцессорных систем.

Литература

1. Павлов В. В. Системы «человек—машина»: проблемы и синтез. — Киев: Высшая школа, Головное издательство, 1987. — 55 с.
2. Кочетенко Е. М. Построение и алгоритмы внутримашинной системы знаний о человеке-операторе в рамках концепции адаптивного компьютера // Сборник трудов первой междунар. науч.-практ. конф. по программированию «УкрПРОГ’98». — Киев, 1998. — С. 487–492.
3. Росс Д. Структурный анализ (SA): язык для передачи понимания // Требования и спецификации в разработке программ. — М.: Мир, 1984. — С. 240–284.
4. Шиян А. А. Типы людей и их взаимодействие с компьютером // Сборник трудов первой междунар. науч.-практ. конф. по программированию «УкрПРОГ’98». — Киев, 1998. — С. 482–486.
5. Балашов К. В. Когнитивная сложность систем взаимодействующих процессов // Сб. научн. трудов конф. по искусственному интеллекту «КИИ-94». — Рыбинск, 1994. — Т. 1. — С. 154–158.
6. Касти Дж. Большие системы: связность, сложность и катастрофы / пер. с англ. — М.: Мир, 1982.
7. Первозванский А. А., Гайцгори В. Г. Декомпозиция, агрегирование и приближённая оптимизация. — 1979. — 344 с.
8. Солодовников В. В., Тумаркин В. И. Теория сложности и проектирование систем управления. — М.: Наука, Гл. ред. физ.-мат. лит., 1990. — 186 с.
9. Норенков И. П. Разработка систем автоматизации проектирования. — М.: МГТУ им. Э. Н. Баумана, 1994. — 207 с.
10. Бургин М. С. Меры сложности в аксиоматической теории алгоритмов // Методы проектирования интеллектуальных прикладных программных систем. — Киев: ИК, 1992. — С. 60–67.
11. Коваль Л. В., Коваль Ю. В. Методы упорядочивания термов в задачах пополнения // Там же. — С. 67–78.
12. Григорьев А. В. О построении унифицированной концептуальной модели предметной области // Сб. трудов шестой междунар. конф. «Знания — диалог — решения». — Ялта, 1997. — Т. 1. — С. 427–434.
13. Григорьев А. В., Бондаренко А. В., Шойхеденко А. В. Интерфейс табличного процессора EXCEL и специализированной оболочки для синтеза интеллектуальных САПР и АСНИ // Информатика, кибернетика и вычислительная техника (ИКВТ-97): сб. трудов ДонГТУ. — Донецк: ДонГТУ, 1997. — Вып. 1. — С. 229–238.
14. Григорьев А. В. Методика тестирования для определения когнитивной сложности моделей различных предметных областей // Научные труды Донецкого государственного технического университета. Сер.: Информатика, кибернетика и вычислительная техника (ИКВТ-99). — Донецк: ДонГТУ, 1999. — Вып. 6. — С. 246–251.
15. Григорьев А. В. Оценка когнитивной сложности моделей // Научные труды Донецкого государственного технического университета. Сер.: Информатика, кибернетика и вычислительная техника (ИКВТ-99). — Донецк: ДонГТУ, 1999. — Вып. 6. — С. 252–259.
16. Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974. — 520 с.