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

Размещено на http://www.allbest.ru/

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

А.Е. Янковская

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

Введение

Рассматриваемая в настоящей статье задача возникает при оптимизации принятия решений в интеллектуальных системах, ориентированных на применение в разных проблемных и междисциплинарных областях. Далее будем рассматривать интеллектуальные системы, основанные на тестовых методах распознавания образов. Поскольку процедура принятия решений является довольно сложной, то её разбивают на последовательно выполняющиеся этапы [Янковская, 2001a]. В публикации [Янковская, 2001a] предложено 9 этапов, основными из которых являются следующие:

1. Анализ данных и знаний на непротиворечивость и репрезентативность.

2. Выявление различного рода закономерностей.

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

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

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

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

Одним из самых важных и трудоёмких этапов является 3-й этап - выбор оптимального подмножества тестов, используемых при принятии решений. Основные критерии выбора были сформулированы в [Янковская, 2009a], а алгоритмы выбора изложены в статьях [Янковская, 2009b], [Yankovskaya et al., 2007], [Колесникова и др., 2009].

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

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

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

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

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

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

Основные понятия и определения

Введём используемые далее основные понятия и определения [Янковская, 2001a], [Янковская, 2000].

Данные и знания представляются в матричном виде [Янковская, 2000]: матрица описаний (Q) объектов обучающей выборки в пространстве размерности m k-значных характеристических признаков (если значение признака не существенно, то символ "-" используется для указания его значения) и целочисленная матрица различения (R), задающая разбиение объектов, сопоставленных строкам матрицы Q, на классы эквивалентности.

Строки матрицы R сопоставляются одноименным строкам матрицы Q, столбцы - классификационным признакам. Элемент матрицы R, задает принадлежность данного объекта одному из выделенных классов при соответствующем механизме классификации.

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

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

Описание исследуемого (предъявляемого к распознаванию) объекта задается совокупностью значения признаков, число которых, как правило, существенно меньше числа характеристических признаков. При логико-вероятностном и логико-комбинаторно-вероятностном распознавании [Yankovskaya, 2001b] используются бинарные признаки, причём значения части из них могут быть либо неизвестны, либо заданы с некоторой степенью уверенности (вероятностью), либо в некотором диапазоне (парой вероятностей).

Рамки статьи не позволяют представить предложенную и используемую автором расширенную матричную модель представления данных и знаний [Янковская, 2001a]. Отметим, что матричная модель базируется на понятиях и конструкциях теории дискретных автоматов, применяемых при проектировании дискретных управляющих устройств, и при одном механизме классификации совпадает с представлением данных и знаний, традиционно используемых в задачах распознавания образов.

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

ДТ называется минимальным, если содержит минимальное количество признаков. ДТ называется безызбыточным (тупиковым [Журавлёв и др., 1990]), если содержит безызбыточное количество признаков.

Безызбыточный безусловный диагностический тест (ББДТ) характеризуется одновременным предъявлением всех входящих в него признаков исследуемого объекта при принятии решений.

Понятие закономерности в данных и знаниях как подмножеств признаков с определенными свойствами приведено в публикациях [Янковская, 2001a], [Янковская, 2000]. К числу закономерностей относятся константные, устойчивые, неинформативные, альтернативные, зависимые, несущественные, обязательные (входящие во все ББДТ), псевдообязательные (не являющиеся обязательными, но входящие во все ББДТ, участвующие в принятии решений), минимальные и все безызбыточные логические тесты (диагностические) и ряд других закономерностей, указанных в статье [Янковская, 2000], а также ДТ, устойчивые к числу t ошибок измерения значения признака (признаков) [Янковская, 2009c], сигнальные признаки 1-го рода.

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

Введём понятие вектор-функции различения размерности m, используемое в дальнейшем при анализе данных и знаний на непротиворечивость и при выявлении закономерностей:

,

где , - значения признака zj для объектов a, b соответственно из разных образов (классов при фиксированном механизме классификации).

Если один из признаков или оба признака принимают значение "-", будем считать, что результат операции равен 0. Это обусловлено тем, что при построении на основе вектор-функции различений безызбыточной матрицы импликаций (U'), задающей различимость объектов из разных образов (классов при фиксированном механизме классификации) строки, сопоставленные таким вектор-функциям различения, будут исключены. Построение матрицы U' осуществляется путём исключения из матрицы U поглощающих строк [Янковская, 2001a] в процессе её построения.

В дальнейшем i-ю строку матрицы U, построенную по вектор-функции f(a,b) будем обозначать через U'i(a,b).

U'i(a,b) = f(a,b).

При отсутствии необходимости указывать конкретные объекты будем их опускать при построении строк матриц Ui, U'i.

Критерии, предъявляемые к принимаемым решениям

Перечислим основные требования, предъявляемые к принимаемым решениям, сформулированные в виде критериев:

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

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

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

4. Общее число сигнальных признаков 1-го рода по всем правилам принятия решений должно быть минимальным.

5. Общее число подмножеств сигнальных признаков 1-го рода по всем правилам принятия решений должно быть минимальным.

6. Признаки, включённые во все правила принятия решений (ППР), должны иметь максимальный суммарный вес по разделяющей способности признаков [Янковская, 2000].

7. Признаки, включённые во все ППР, должны иметь максимальный суммарный вес (информационный вес [Журавлёв и др., 1990]).

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

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

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

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

Обозначим через Ш(U') - количество ненулевых элементов в строке U'. Сформулируем необходимое и достаточное, а также достаточное условия непротиворечивости данных и знаний при числе t ошибок измерения (занесения) значения характеристических признаков и устойчивости ДТ к числу t ошибок измерения (занесения) характеристических признаков.

Теорема 1. Для обеспечения непротиворечивости данных и знаний и принятия решения, устойчивого к числу t ошибок измерения (занесения) характеристических признаков, в матрице Q для каждой пары объектов из разных классов при фиксированном механизме классификации необходимо и достаточно обеспечение условия

Ш(Ui) ? h (h = t + 2)

для любой строки Ui матрицы U.

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

Следствие 1. Замена в утверждении теоремы 1 анализа каждой пары объектов из разных классов при фиксированном механизме классификации на анализ каждой пары объектов из разных образов (образ - образ, объект - образ, объект - объект) не нарушает её достаточности при построении матрицы импликаций на основе образов.

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

Теорема 2. Для обеспечения непротиворечивости данных и знаний и принятия решения, устойчивого к числу t ошибок измерения (занесения) l-го характеристического признака zl в матрице Q для каждой пары объектов из разных классов при фиксированном механизме классификации необходимо и достаточно обеспечение условия

Ш(Uli) ? h (h = t + 2)

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

Доказательство. Поскольку построение отказоустойчивых (минимальных, безызбыточных, оптимальных) ДТ осуществляется на основе поиска столбцовых h-кратных (кратчайших, безызбыточных, оптимальных) покрытий матрицы U, а следовательно, и матрицы U', то при построении покрытий с учётом отказоустойчивости тестов по l-ой переменной необходимо и достаточно, чтобы построенный тест содержал не менее h характеристических признаков, включающий l-й признак. Следовательно, необходимо и достаточно, чтобы только строки матрицы Ul, имевшие ненулевое значение l-го признака, содержали не менее h элементов, имеющих ненулевое значение. Остальные же строки матрицы Ul должны иметь не менее одного ненулевого элемента. В противном случае очевидна противоречивость данных и знаний и невозможно построить ДТ, устойчивые к t ошибкам измерения (занесения) значения l-го признака. Так как принятие решений осуществляется на основе ДТ, то невозможно обеспечить отказоустойчивость к t ошибкам измерения l-го признака, что и требовалось доказать.

Аналогично следствию 1, сформулируем следствие 2, обозначив через U матрицу импликаций, построенную на основе анализа пар образов.

Следствие 2. Замена в утверждении теоремы 2 анализа каждой пары объектов из разных классов при фиксированном механизме классификации на анализ каждой пары объектов из разных образов (образ - образ, объект - образ, объект - объект) не нарушает её достаточности при построении матрицы импликаций на основе образов.

Доказательство следствий не представляет сложности.

Алгоритм выявления закономерностей за исключением построения отказоустойчивых тестов описан в публикации [Янковская, 2000].

Алгоритм построения отказоустойчивых ДТ сводится к поиску кратчайших (безызбыточных, оптимальных) h-кратных столбцовых покрытий матрицы U'. Алгоритм поиска кратчайших h-кратных столбцовых покрытий для двоичных матриц приведён в [Агибалов, 1966].

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

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

Выбор оптимального подмножества ДТ (ББДТ и смешанных ДТ, основанных на оптимальном сочетании безусловных и условных составляющих [Yankovskaya, 1996a]), используемых при принятии субоптимальных решений относится к наиболее важному и трудоёмкому этапу.

Все вышеперечисленные 9 критериев к принятию субоптимальных решений переформулируются (трансформируются) в критерии выбора оптимального подмножества ДТ. Отметим, что критерии 2-9 трансформируются в критерии, соответственно 1-8, представленные в статье [Янковская, 2009a]. В данном исследовании 1-й критерий принятия субоптимальных решений (все ББДТ должны быть устойчивы к числу t ошибок измерения значений всех признаков либо l-го признака) обеспечивается на 1-м, 2-м этапах, перечисленных во введении, а именно, при анализе данных и знаний на непротиворечивость и выявлении различного рода закономерностей.

Выбор оптимального подмножества ДТ осуществляется на основе трёх алгоритмов (логико-комбинаторный алгоритм [Янковская и др., 2009b], алгоритм на основе метода анализа иерархий [Колесникова и др., 2009] и генетический алгоритм [Yankovskaya et al., 2007]), обеспечивающих выполнение этих критериев и сравнительного анализа результатов, полученных по трём алгоритмам. При этом используется упомянутая во введении конвергенция наук и научных направлений в рамках тестового распознавания образов (вес на основе разделяющей способности признаков и на основе информационного веса).

Принятие решений осуществляется на основе одного из подходов: логико-комбинаторный [Янковская, 2001a], логико-вероятностный [Янковская, 2001a] и логико-комбинаторно-вероятностный [Yankovskaya, 2001b] либо их сочетания.

Требование устойчивости к числу t ошибок измерения значений всех признаков либо конкретного признака при принятии решений приводит к изменению процедуры ортогонализации булевых функций, если матрица Q является булевой [Yankovskaya, 1996b]. Что касается изменений, при принятии решения связанных с целочисленной матрицей Q, то предстоят дальнейшие исследования, так же как и при принятии на множестве способов распознавания и подходов. При принятии решения на 5-м этапе используется конвергенция всех перечисленных во введении наук.

Заключение

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

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

Благодарности. Работа выполнена при финансовой поддержке РФФИ (проект № 10-01-00462-а).