книги / Математические методы принятия решений
..pdfв пространстве критериев —множество критериальных векторов
вЖк, которые одновременно удовлетворяют всем целям.
ВЦП используются две основные модели решения задач: архи медова модель и модель с приоритетами. В архимедовой модели точки — кандидаты в решение — генерируют путем определения тех точек из D, критериальные векторы которых являются ближайши ми в смысле взвешенной метрики пространства L\ к утопическому множеству в пространстве критериев. В модели с приоритетами генерируют решения, для которых критериальные векторы оказы ваются наиболее соответствующими в лексикографическом смысле точками утопического множества в пространстве критериев.
Пример. Рассмотрим задачу ЦП:
цель {с\х = z\}, |
z\ ^ t\, |
|
ЦеЛЬ {с^Х = 22}» |
*2 = Î2 , |
|
ц ел ь |
{сТ3х = 23}, |
23 е Щ, £$], |
при x e D . |
|
|
Архимедова модель этой задачи записывается следующим об |
||
разом: |
|
|
min{tuj"dj" + W2 d,2 + |
+ w * d f + w ^ d j } |
|
при целевых ограничениях |
|
|
c}x + dj" ^ t i , |
c^x — d£ + d j = t2> c}x + d j ^ £", |
|
clx — d f ^ t * , |
x e D , |
dj", d j, d j, df, d j ^ 0. |
Переменные w \, W2, WT, в целевой функции — положительные штраф ные весовые коэффициенты; каждая цель порождает одно целевое ограничение, кроме случая, когда задан диапазон значений целевой функции и возникают два целевых ограничения. В формулировке задачи используются переменные отклонений dj", d%, d j , ..., кото рые соответствуют нежелательным отклонениям.
Архимедова целевая функция представляет собой взвешенную сумму переменных нежелательных отклонений. Переменные w\, W2, и>з позволяют штрафовать нежелательные отклонения от цели с разной степенью жесткости. Целевые ограничения расширяют об ласть допустимых решений D, переводя ее в пространство большей
размерности и создавая таким образом архимедову область допу стимых решений для задачи ЦП.
Архимедовы задачи ЦП можно решать, используя обычные ме тоды линейного программирования. Но тогда мы можем получить только крайние точки допустимой области в пространстве решений для архимедовой задачи ЦП (т. е. крайние точки области D после ее усечения целевыми ограничениями). В процесссе решения могут быть получены следующие варианты:
1)крайние точки области D\
2)точки границы области D, не являющиеся крайними;
3)внутренние точки области D.
Если ЛПР предпочитает получить точку, не являющуюся край ней точкой допустимой области архимедовой задачи ЦП, то ее мож но получить, используя процедуры изменения целевых показате лей U.
Рассмотрим задачу ЦП с приоритетами. В приоритетном (лек сикографическом) ЦП цели группируются по приоритетам. Цели с высшим уровнем приоритета считаются «бесконечно важными» по сравнению с целями со следующим уровнем приоритета, т.е. если решение задачи получено при некотором уровне приоритета, то цели нижних уровней не учитываются в дальнейшем. Рассмот рим задачу ЦП с приоритетами вида
цель |
{с\х = z i}, |
P\(z\ ^ |
ti), |
цель |
{cjx = z2), |
P2(z2 ^ |
t2), |
цель {cjX = 23}, |
Рз(г3 = |
h) |
|
при х е D, в которой j = 1,2,3 указывают цели с уровнем приорите та j. Величины Pj служат и в качестве характеристик приоритетов, причем Pj » Pj+i (т.е. Pj много больше Pj+i).
Запишем задачу ЦП с приоритетами в следующей лексикогра фической форме:
lex m inldf, d j , (d+ + dj)}
при условиях
c}x — d ^ ^ t \ , c2x + d 2 ^ t 2,
c^ x |
d ^ -b d j 1 £3 » 2* ^ -P, |
d^ , d2 , d^ , rfj ^ 0. |
Решается данная задача с помощью методов линейного про граммирования, при этом последовательно рассматриваются задачи с наибольшим приоритетом. На первом этапе решаем задачу целе вого программирования с первым приоритетом:
min{dj'}
при условиях
с}х — d* ^ t i , x e D d + ^ 0.
Если в этой задаче есть альтернативные оптимумы (для небазис ных элементов есть соответствующее значение Cj —Zj = 0), то ре шаем задачу со вторым приоритетом, учитывая результаты, полу ченные на первом этапе:
m in{dj}
при условиях |
|
c [ x ^ t\ + (d+)om, clx + d ^ ^ t 2, x e D , |
d j $ s 0 . |
Здесь (di’)onT — оптимальное значение переменной |
d*, найденное |
на первом этапе. |
|
Если в задаче второго этапа есть альтернативные оптимумы, то решаем задачу третьего этапа с третьим приоритетом, учитывая результаты, полученные на первых двух этапах:
minfdj' + dj}
при условиях
С\Х ^ il |
+ (d f )опт> |
С2Х ^ ^2 |
(d2 )опт, |
с\х - d f |
+ d j = ti, |
x e D , |
d % , d j ^ 0, |
где (dj)onr — оптимальное значение d j, найденное на втором этапе. Любое решение задачи третьего этапа определяет лексикогра фический минимум в задаче ЦП с приоритетами. Однако решение задачи прекращается, как только на каком-то этапе будет получено единственное решение, т. е. цели нижних уровней могут и не по
влиять на решение.
Задачу ЦП с приоритетами можно решить в течение одного эта па при использовании лексикографического симплекс-метода.
Пример. Рассмотрим задачу ЦП:
цель |
{х2 = zi}, |
P\{z\ ^ |
5), |
цель |
{ - x i - х 2 = z2}, |
P 2(z2 ^ 4), |
|
цель |
{я3 = z3}, |
Р3(23 ^ |
3) |
при условиях х 2 ^ 2, хъ ^ 3, х\, х 2, х3 ^ 0. Данная задача преобразуется к виду
lex min {df, d j , dj}
при условиях-ограничениях
X 2 + d f ^ 5, - X \ - x2 + d^ ^ 4, æ3 + d^ ^ 3, x2 ^ 2 , x 2 < 3;
здесь все переменные положительные.
Введем дополнительные (слабые) переменные s i , ..., S5 и за полним симплекс-таблицу (табл. 5.19), из которой удалим столбцы базисных переменных; Cÿ —Z ÿ , i = 1, 2, 3, —строки относительных оценок целевой функции для каждого лексикографического уров ня Pj, j = 1, 2,3 (последние три строки симплекс-таблицы), в пу стых клетках —нули.
Таблица 5.19
Симплекс-таблица первого этапа
Базис |
|
Свободный член |
X\ |
ХЪ |
Si |
S2 |
S3 |
S4 |
|
d r |
|
|
3 |
|
|
- 1 |
|
|
- 1 |
6^2 |
|
|
6 |
- 1 |
|
|
- l |
|
|
d j |
|
|
3 |
|
1 |
|
|
- 1 |
|
Х\ |
|
|
2 |
|
|
|
|
|
1 |
S5 |
|
|
3 |
|
ш |
|
|
|
|
c \j ~ |
Z\j |
3 |
|
|
1 |
|
|
1 |
|
c 2j — z |
2j |
6 |
1 |
|
|
l |
|
- 1 |
|
C3j - |
z |
3j |
3 |
|
- 1 |
|
|
1 |
|
Анализируя строки щ — Zÿ, г = 1,2,3, видим, что перемен ную S4 можно было бы перевести в базисные переменные. Тогда целевая функция второго лексикографического уровня может быть
уменьшена, но при этом увеличится целевая функция первого лек сикографического уровня, чего допустить нельзя. Таким образом, точка (х\,Х2, х-}) = (0,2,0) минимизирует целевые функции первого и второго этапов. Поскольку существуют альтернативные оптимумы, переходим к третьему этапу.
Вводим в базис переменную х-$, так как в первой и второй строках Cij —Zij над элементом —1 нет положительных элементов. Получим новую симплекс-таблицу (табл. 5.20) и оптимальное реше ние (х\,Х2,хз) = (0,2, 3), которое и является лексикографическим минимумом для рассматриваемой задачи. В точке оптимального ре
шения для первой цели имеем |
= 3; для второй цели — d j = 6 ; |
|
для третьей цели |
= 0, т. е. цель достигнута. |
|
Таблица 5.20
Заключительная симплекс-таблица
Базис |
Свободный член |
XI |
Si |
S2 |
S3 |
S4 |
S5 |
с?1 |
3 |
|
- 1 |
|
|
- 1 |
|
|
6 |
- 1 |
|
- 1 |
|
1 |
|
d3- |
0 |
|
|
|
- 1 |
|
- 1 |
XI |
2 |
|
|
|
|
1 |
|
Хз |
3 |
|
|
|
|
|
1 |
р |
3 |
|
1 |
|
|
1 |
|
Рг |
6 |
1 |
|
1 |
|
- 1 |
|
Р |
0 |
|
|
|
1 |
|
1 |
Наилучшие результаты в решении задач ЦП получаются в ин терактивном режиме, когда решаются одновременно и архимедова задача, и задача с приоритетами.
Полезно бывает использовать прием масштабирования целевых ограничений — записать отклонения от целей в процентах, т. е. вве
сти вместо di выражение • сЦ. Если дополнительно миними
зировать новую переменную а и добавить условие, что отклоне ния di не будут превышать значения а, то такая процедура будет минимизировать максимальное отклонение. В этом случае число дополнительных ограничений равно числу переменных отклонения на рассматриваемом уровне приоритета.
ЧАСТЬ II
СТАТИСТИЧЕСКИЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЙ
Всякая наука есть предвидение.
Герберт Спенсер
Г л а в а 6
АНАЛИЗ МЕТОДОВ ПРИНЯТИЯ РЕШЕНИЙ И ПОСТАНОВКА ЗАДАЧИ УЧЕТА ПОГРЕШНОСТЕЙ ПРИЗНАКОВ
§6.1. Основные понятия и определения
Теория принятия решений и распознавания образов в послед ние годы приобретает все большее значение в различных областях знания (технике, экономике, медицине и др.) и проникает в обла сти управления, исследования операций, радиолокации и т. д. Число статей и книг, посвященных этим вопросам, значительно возросло.
Алгоритмы распознавания образов, рассматриваемые в ч. 2 на стоящей книги, по совокупности признаков различаются этапностью принятия решений, степенью и характером учета статистики признаков, помех, сигналов.
Различают алгоритмы одноэтапного и многоэтапного [14, 63, 65, 66, 80-85] принятия решений. Одноэтапное принятие решений предусматривает обязательное получение оценки принятия г-й ги потезы с приемлемой достоверностью. Многоэтапное принятие ре шений предусматривает отказ от выдачи решения на первом эта пе (первых этапах) до получения дополнительного набора инфор мативных признаков (последовательные алгоритмы Вальда), либо принятие приближенного решения до получения дополнительно го набора информативных признаков, либо обобщение предвари тельных решений, полученных в различные моменты времени или от различных источников.
По степени учета статистических закономерностей различают
лингвистические и статистические алгоритмы. По характеру уче та статистических закономерностей из статистических алгоритмов выделяют параметрические (байесовские и небайесовские), непа раметрические и нейрокомпьютерные алгоритмы.
Лингвистические алгоритмы [18, 62, 81, 84] не учитывают ста тистики признаков объектов. Вводимые признаки описывают объек ты качественно, часто двоичными цифрами 0, 1. Описание призна ков в терминах алгебры логики (языковое, кодовое, синтаксическое) служит при этом основой распознавания изучаемых явлений.
Байесовские параметрические алгоритмы, в отличие от пара метрических небайесовских, учитывают не только статистику по мех, флуктуаций сигналов и признаков, но и определенные гипо тезы об априорных вероятностях Р* различных элементов алфа вита классов [28, 80, 85]. Структуры алгоритмов и работающих по ним устройств обработки сигналов определяются по матема тическим моделям, описывающим изучаемые явления. Статистика признаков сигналов, негауссова в общем случае, устанавливается путем эксперимента, математического или физического моделиро вания. Введение этой статистики можно трактовать как обучение распознаванию, адаптацию к конкретным условиям распознавания. Непараметрические алгоритмы синтезируются эвристически без яв ного принятия предположений о конкретных статистических рас пределениях [28, 52, 59, 62, 80, 85]. Их можно рассматривать в ряде случаев как эвристическое упрощение параметрических байесов ских алгоритмов.
Нейрокомпьютерные алгоритмы отличаются своей заранее за данной универсальной структурой с большим числом неизвестных параметров, уточняемых в процессе адаптации (обучения) [60, 101, 107]. Возрастание вычислительных затрат как издержку универса лизации компенсируют ростом производительности вычислитель ных средств.
К решению задач распознавания объектов (образов) привлека ют также ряд математических теорий и методов, развитие которых связано с появлением экспертных систем [35, 74]: теорию нечетких множеств и теорию возможностей [29, 74, 82], теорию игр и другие математические методы [7, 8, 12, 60, 61].
В задачах распознавания образов и принятия решений важную роль играет тот факт, насколько строго учтены неопределенно сти исходных данных. Использование усредненных величин ведет к смещенным оценкам основных показателей, определяющих реше ние, и, как следствие, к неверным практическим выводам. Поэтому
здесь особое внимание уделено строгому учету погреш ностей из мерений вектора признаков объекта.
Традиционные статистические методы распознавания образов часто не учитываю т погреш ности измерений наблюдаемых значе
ний признаков, что приводит к следующему:
1) оценки функций условных плотностей распределения веро ятностей признаков образов (если даже вид плотностей известен априори), которые получаю т по результатам наблюдений, будут
смещ енными, а их интервальные оценки — неверными;
2) в процессе идентификации образов, имею щ их близкие зна чения координат векторов признаков, вследствие влияния погреш ностей на результаты наблюдений может быть принято неверное
решение;
3) в традиционны х методах принятия реш ений функции услов
ных плотностей распределения вероятностей признаков считаю т
в процедурах идентификации образов детерминированными (не учитываю тся их интервальные оценки), и по этой причине не рас сматриваю т имею щ ие место зоны неопределенности (нулевые зо ны) в принятии реш ений.
В отличие от традиционны х статистических методов распозна вания образов в настоящ ей книге рассматриваю тся методы, которые
позволяю т учесть погреш ности наблюдаемых значений координат векторов признаков объектов, получить несмещ енные точечные
и интервальны е оценки функций условных плотностей распреде ления вероятностей признаков, оценить «истинные» координаты вектора признаков, по которому ведется идентификация объектов, и вклю чить эти данны е в процедуру принятия решений.
В теории принятия реш ений используют методы математиче ской статистики, которыми проводят проверку гипотез, при этом вводят в рассмотрение реальные потери от возможной ош ибки при принятии гипотезы . У чет различных потерь для разных гипотез приводит к другим выводам, полученным методами теории приня тия реш ений, по сравнению с выводами, сделанными с помощ ью статистической проверки гипотез. Выбор менее вероятной гипоте зы может оказаться более предпочтительным, если потери в случае ош ибочности такого выбора окажутся меньш е потерь, вызванных ош ибочностью выбора более вероятной конкурирующей гипотезы.
Типичным примером такого случая является отбраковка изделий, выход из строя которых приводит к дорогостоящим последствиям. В этом случае более выгодно нести материальные потери на изго товление лишних изделий, чем допускать прием аварийно опасного изделия.
Вероятность ошибки, функция потерь, правила решений
В статистической теории решений, чтобы принять решение от носительно некоторых гипотез (состояний природы) toi и сог по ре зультатам наблюдений признаков х изучаемых явлений, необходимо каким-то образом получить апостериорное (на языке байесовских классификаторов) распределение P(tOj | х), j = 1,2. Если в после дующем окажется, что при наблюдении х вероятность P(a>i | х) бу дет больше P(CÛ2 | х), то следует все-таки выбрать решение, что состояние природы есть <0]. При этом совершается ошибка е, ве роятность которой есть
Пусть kj — потери вследствие принятия решения ы* при истин ном состоянии природы (истинной гипотезе) <0j. Ожидаемые поте ри называются риском, решение принимается по значению условно
го риска
3
R(a>i |х) = lijP(v>j |х), г = 1,2,..., s,
з=1
где s —число состояний природы (гипотез), х — наблюдаемые зна чения признаков, х е Х .
Если окажется, что \ х) < R(u>j \ х), то выбирается гипо теза <0j. Для случая двух состояний природы o>i и од последнее неравенство имеет вид
(hi - ill)P(cO, | X) > (i12 - /22>Р(“ 2 Iх).
Рассмотрим для примера случай двух состояний природы, ко гда апостериорная вероятность известна и определена как произ ведение условной плотности распределения вероятностей р(х | од) и априорной вероятности Р(од) (рис. 6.1).