Леонид Соломонович Файнзильберг
Развиваетсяподход к построению схемы принятия коллективного решения в условияхпротиворечивой информации, полученной от независимых экспертов. Показано, чтотолько при равновероятных классах групповое решение должно совпадать с частнымрешением более квалифицированного эксперта. Предложены правила, обеспечивающиеминимизацию средней вероятности ошибки коллективного решения.
Введение.
Различныесферы профессиональной деятельности человека связаны с принятием решений,которые сводятся к выбору оптимального варианта поведения из множестваальтернатив [1,2]. Довольно часто такой выбор опирается на информацию, которуюлицо, принимающее решение, получает в виде рекомендаций от коллектива экспертов[3-7].
Целыйряд прикладных задач, например, задач медицинской и технической диагностики,также сводится к принятию решения: необходимо определить принадлежностьсостояния объекта исследования к одному из нескольких заранее определенныхклассов (диагнозов) [8]. В простейших случаях достаточно сделать выбор междудвумя возможными состояниями, например “болен” — “здоров”, “исправен — неисправен”. В других случаях число возможных диагнозов больше двух.
Прирешении таких задач используются методы распознавания образов, позволяющиеавтоматизировать процесс диагностики. С этой целью состояние объектаописывается совокупностью некоторых параметров (признаков) и строится алгоритмраспознавания, который после соответствующей настройки (обучения) обеспечиваетклассификацию текущего состояния объекта. Обычно эффективность таких системоценивается вероятностью ошибочной классификации.
Дляповышения эффективности систем распознавания в последнее время вниманиеспециалистов привлекают так называемые коллективные (комбинированные)классификаторы [9,10]. Их суть состоит в том, что окончательное решениепринимается на основе “интеграции” частных решений, которые принимают отдельныеклассификаторы.
Существуютразличные подходы к интеграции частных решений. В одних случаях предлагаетсяиспользовать метод голосования (majority vote method) [11,12] или ранжирования(label ranking method) [13, 14]. В других — использовать схемы, основанные наусреднении или линейной комбинации апостериорных вероятностей, которыеоцениваются отдельными классификаторами [15,16], либо использовать алгоритмынечетких правил (fuzzy rules) [17]. Предлагается также проводить независимоеобучение комбинированного классификатора, рассматривая частные решения какновые комплексные признаки [18,19]. Развиваются также подходы, основанные навыделении в пространстве наблюдений локальных областей, в каждой из которыхтолько один из частных классификаторов “компетентен” принимать решение [20].
Всеэти работы имеют несомненный теоретический интерес и, как показано в [21],позволяют обосновать выбор той или иной схемы интеграции, если известныалгоритмы принятия частных решений и характеристики признаков, которыеиспользуют отдельные классификаторы.
Вто же время на практике, как отмечено в [1], приходится принимать решения и втех случаях, когда рассматриваемая проблема слабо структурирована, аформализации поддаются лишь отдельные фрагменты общей постановки. Довольночасто эксперты при анализе ситуаций используют не количественные, акачественные признаки [22], а сами решения принимают на основе эвристическихалгоритмов либо просто полагаются на свой предшествующий опыт и интуицию.
Разумеетсяв этих практически важных случаях также требуется обоснованный подход кинтеграции частных решений экспертов. Например, какое окончательное решениедолжно быть принято, если в результате независимого обследования частьспециалистов (экспертов) признала пациента здоровым, а другая часть – больным?
Можнопривести и другие не менее актуальные примеры необходимости принятияколлективных решений в условиях противоречий при ограниченной априорнойинформации о частных решениях экспертов.
Внастоящей статье развивается один из возможных подходов к решению таких задач.
Постановка задачи.
Пустьнекоторый объект Z находится в одном из М возможных состояний (классов) V1,...,VM с известными априорными вероятностями P(V1),...,P(VM),/>. Ясно, что если нерасполагать какой либо дополнительной информацией, то состояние Z всегдаследует относить к классу, имеющему наибольшую априорную вероятность. В этомслучае величина
P0=1- max{P(V1),...,P(VM)}, (1)
определяетминимальную вероятность ошибочной классификации.
Предположимтеперь, что имеется N экспертов (алгоритмов) A1,…, AN, которые на основаниидополнительной информации независимо один от другого принимают решенияδi(Z) о состоянии объекта Z в виде индикаторных функций
δi(Z)= k, если Ai решает в пользу Vk, i =1,…,N, k = 1,..M. (2)
Будемхарактеризовать “квалификации” экспертов вероятностями P(Ai) ошибочной классификации,которые считаются известными для всех N экспертов на основании предыдущегоопыта. При этом, естественно, допустить, что эти вероятности удовлетворяютусловиям
P(Ai)
Ставитсязадача построения коллективного решающего правила, основанного на частныхрешениях экспертов, которое минимизирует среднюю вероятность ошибочнойклассификации.
Решающееправило 1.
Рассмотримвначале простейший случай, когда число экспертов N=2 и число возможных классовM=2. В этом случае возможны четыре комбинации частных решений экспертов:
S11:δ1(Z) = 1, δ2(Z) = 1;
S12: δ1(Z) = 1, δ2(Z) = 2;
S21: δ1(Z) = 2, δ2(Z) = 1;
S22:δ1(Z) = 2, δ2(Z) = 2.
Каквидно в ситуациях S12 и S21 решения экспертов противоречивы. Возникаетестественный вопрос: какое решение следует принимать, чтобы минимизироватьвероятность ошибочной классификации?
Напервый взгляд может показаться, что в условиях противоречий следует приниматьто решение, которое принял более “квалифицированный” эксперт. В то же времяоказывается, что в общем случае такой подход неправомерен.
Длятого, чтобы показать это, рассмотрим условные (апостериорные) вероятностиP(V1/S12 ) и P(V2/S12 ) классов в ситуации S12. При этом для минимизациисредней вероятности ошибочной классификации будем принимать окончательноерешение в пользу класса V1, если
/>P(V1 / S12 )> P(V2 / S12 ), (4)
ирешение в пользу V2 в противном случае.
Поформуле Байеса имеем
/>,
/>.
Очевидно,что неравенство (4) имеет место в том и только в том случае, когда
P(V1)P(S12 / V1) > P(V2)P(S12 / V2). (5)
Поопределению условная вероятность P(S12 / V1) есть ни что иное как вероятностьтого, что в ситуации, когда имеет место класс V1, эксперт A2 принял правильноерешение, а эксперт A1 ошибся. Поскольку мы предполагаем, что решения экспертовнезависимы, то по формуле произведения вероятностей
P(S12/V1)= [1-P(A1)]P(A2). (6)
Аналогичнымобразом
P(S12/V2) = P(A1)[1-P(A2)]. (7)
Неравенство(5) с учетом (6), (7), можно представить в виде:
P(V1)[1- P(A1) P(A2) > P(V2) P(A1) [1-P(A2)]. (8)
Из(8) вытекает, что в ситуации S12, когда решения экспертов противоречивы, объектZ следует относить к классу V1 в том и только том случае, когда
/>, (9)
гдеλ = P(V2)/P(V1) – отношение априорных вероятностей классов.
Еслиже выполняется соотношение
/>, (10)
тов ситуации S12 объект Z следует относить к классу V2
Дляиллюстрации на рис. 1 показаны границы областей решений, построенные дляситуации S12 согласно условиям (9), (10) при различных значениях λ.Область решения в пользу класса V1 расположена выше соответствующей границы, арешений в пользу класса V2 – ниже соответствующей границы.
/>
Рис.1. Области решений для ситуации S12
1:λ = 9; 2: λ = 4; 3: λ =2.33; 4: λ =1.5; 5: λ = 1; 6:λ = 0.67;
7:λ = 0.43; 8: λ = 0.25; 9: λ = 0.11.
Аналогичнымобразом легко показать, что в ситуации S21 решение в пользу класса V1 следуетпринимать в том случае, когда
/>, (11)
арешение в пользу класса V2, когда
/>. (12)
Заметим,что из (9)-(12) непосредственно следует, что только при равновероятных классах,когда λ =1, окончательное решение совпадает с решением того из экспертов,который имеет меньшую вероятность ошибки.
Востальных же случаях, когда λ />1, т.е./>окончательное решение определяетсяне только соотношением вероятностей ошибок экспертов, но и соотношениемаприорных вероятностей классов. При этом окончательное решение может несовпадать с решением более “квалифицированного” эксперта.
Посколькупримеры часто бывают более убедительными, чем формальные рассуждения, пояснимсказанное на модельном примере.
Модельныйпример.
ПустьP(V1)=0.3, P(V2)=0.7, а значит λ. = 2.33. Пусть далее известно, что первыйэксперт ошибается в 5% случаев, т.е. P(A1)=0.05, а второй — в 8% случаев, т.е.P(A2)=0.08. Предположим, что эксперт A1 отнес объект к классу V1, а эксперт A2- к классу V2, т.е. мы имеем ситуацию S12 противоречивых решений. Заметим, чтопервый эксперт более “квалифицированный”, так как P(A1)
Каквидно из рис. 1 точка с координатами P(A1)=0.05 и P(A2)=0.08, расположена нижеграницы, соответствующей λ. = 2.33. Следовательно объект должен бытьотнесен к классу V2, хотя более квалифицированный эксперт A1 принялпротивоположное решение.
Дляпроверки обоснованности решения в пользу класса V2 определим по формуле Байесаапостериорные вероятности классов в рассматриваемой ситуации S12 :
/>=/>(13)
и
/>=/>. (14)
Каквидим P(V1/S12)
Изменимв условиях примера соотношения априорных вероятностей классов, положив P(V1) =0.4, P(V2) = 0.6. В этом случае λ = 0.67 и, как видно из рис. 1, точка скоординатами P(A1)=0.05 и P(A2)=0.08 попадает уже в область решений в пользукласса V1. В самом деле
/>=/>
и
/>=/>,
т.е.P(V1/S12) > P(V2/S12). Значит в этом случае объект следует отнести к классуV2, что совпадает с решением более “квалифицированного” эксперта A1.
Итакмы показали, что при различных решениях двух независимых экспертов сфиксированными вероятностями ошибок окончательное решение изменяется сизменением λ.
Заметим,что рассматриваемая схема принятия решений основывается на знании весьмаограниченных вероятностных характеристик, которые при решении практическихзадач, в частности задач медицинской и технической диагностики, легко могутбыть получены на основании предыдущего опыта. При достаточном числе наблюденийвероятности P(Vk) и P(Ai) могут быть оценены соответствующими частотами:
/>
гдеGk – общее число появлений k-го класса (k=1,2) в выборке из G наблюдений, а Ei– общее число ошибок i-го эксперта (i =1,2) в этой же выборке.
Приэтом совершенно не требуется знать, на основании какой информации экспертыпринимают частные решения и как именно эксперты принимают эти решения –используя формальный или эвристический алгоритм, либо просто полагаясь на своюинтуицию.
Вто же время мы сделали одно важное допущение о том, что решения экспертовнезависимы, а вероятность ошибки каждого эксперта не зависит от класса, т.е.P(Ai)=P(Ai/V1)=P(Ai/V2). Естественно, что такое допущение должно бытьобосновано.
Длятого, чтобы продемонстрировать практическую возможность описанной схемы,рассмотрим один из возможных формальных алгоритмов принятия независимых решенийдвумя экспертами.
Предположим,что эксперт A1 классифицирует объект по бинарному признаку x1 (симптому),имеющему всего лишь две градации />и />, а эксперт A2 — по другомупризнаку x2, также имеющему две градации />и />. Будем считать, что дляминимизации вероятности ошибок оба эксперта используют правило максимумаапостериорных вероятностей, т. е. эксперт A1 принимает свое частное решение помаксимуму P(V1/x1) и P(V1/x1), а эксперт A2 — по максимуму P(V1/x2) и P(V1/x2).
Будемсчитать, что P(V1)=0.3, P(V2)=0.7, а также заданы условные распределениязначений признаков в классах V1 и V2, которые представлены в таблицах 1 и 2соответственно .
/>/>
Дляопределения вероятности ошибочных решений эксперта A1 найдем апостериорныевероятности классов при возможных значениях признака x1:
/>= />,
/>= />,
/>= />,
/>= />.
Поскольку/>и />, то эксперт A1классифицирует объект Z по признаку x1 следующим образом
δ1(Z)= />(15)
Легковидно, что />,а значит вероятность ошибки первого эксперта не зависит от класса, т.е.P(A1)=P(A1/V1)=P(A1/V2) =0.05.
Дляопределения вероятности ошибочных решений эксперта A2 найдем апостериорныевероятности классов при возможных значениях признака x2:
/>= />,
/>= />,
/>= />,
/>= />.
Поскольку/>, а />, то эксперт A2классифицирует объект Z по признаку x2 следующим образом
δ2(Z)= />(16)
Приэтом вероятность ошибки эксперта A2 составляет P(A2)=0.08, причем этавероятность также не зависит от класса, т.е. P(A2)= P(A2/V1) = P(A2/V2).
Каквидно из таблиц 1 и 2 признаки x1 и x2 статистически независимы в обоихклассах, поскольку для любых их значений справедливо соотношение p(x1,x2/Vk) =p(x1/Vk)p(x2/Vk) при k =1,2. Отсюда непосредственно следует, что решения(15),(16) экспертов будут независимыми.
Предположим,что в момент принятия решений признаки получили следующие значения />, а />. В этом случае,согласно (15), (16), δ1(Z) = 1 и δ2(Z) = 2, т.е. требуется принятьокончательное решение в условиях противоречивой ситуации S12. Посколькуаприорные вероятности классов и найденные вероятности ошибок экспертов имеюттакие же значения, как в первой части рассмотренного выше примера, то, согласнопредложенной схеме, окончательное решение следует принимать в пользу V2.
Покажем,что такое решение совпадает с оптимальным решением, основанным на результатахизмерения совокупности двух признаков по формальному правилу максимумуапостериорных вероятностей классов/>и />. По формуле Байеса определим этивероятности при />и />:
/>=/>(17)
и
/>=/>. (18)
Сравнение(13),(14) с (17),(18) позволяет заключить, что />для k =1,2. Нетрудно убедиться втом, что аналогичные равенства имеют место и при других возможных значенияхпризнаков.
Следовательно,если эксперты принимают независимые решения, причем P(Ai/V1)=P(Ai/V2) при i =1,2, то предлагаемая схема эквивалентна оптимальной, обеспечивающей минимумсредней вероятности ошибочной классификации по совокупности двух независимыхпризнаков в классах.
Вусловиях данного примера средняя вероятность ошибочных решений, принимаемых порезультатам классификации двух экспертов, составляет 0.0406. Заметим, что этавеличина меньше вероятности ошибки каждого из экспертов.
Решающееправило 2.
Предложеннуюсхему легко можно обобщить на случай, когда вероятности ошибок экспертовзависят от классов. Такое обобщение актуально для решения практических задач, вчастности, задач медицинской диагностики.
Пустьтребуется отнести обследуемого пациента Z к одному из двух классов: V1 – болен,V2 – здоров. При этом будем считать известными априорные вероятности P(V1),P(V2), и ставить окончательный диагноз на основании информации, полученной отдвух экспертов A1, A2, которые производят независимое обследование пациента поразличным методикам.
Будем,как это принято в медицинской практике [23], оценивать “квалификацию” каждогоиз экспертов двумя величинами: чувствительностью Qi = 1- P(Ai /V1), гдевероятность P(Ai /V1) ошибочного отнесения больного пациента к здоровому, испецифичностью Wi = 1- P(Ai /V2), где вероятность P(Ai /V2) ошибочногоотнесения здорового пациента к больному (В теории распознавания вероятностиP(Ai /V1) и P(Ai /V2) принято называть вероятностями ошибок первого и второгорода, или, что то же самое, вероятностями ошибок пропуска цели и ложнойтревоги [24].).
Тогдав ситуации S12, когда A1 признал Z больным, а A2 признал Z здоровым,окончательный диагноз следует ставить согласно схеме:
/>(19)
гдеλ = P(V2)/P(V1) – отношение априорных вероятностей здоровых и больныхпациентов.
Решающееправило 3.
Предположимтеперь, что N >2 экспертов проводят независимое обследования пациента Z, врезультате которых относят его к классу V1 (болен) или к классу V2 (здоров).Будем считать, что известны априорные вероятности P(V1) и P(V2),чувствительности Q1, …, QN и специфичности W1,…,WN каждого из экспертов.
Пустьв результате обследования получена комбинация S решений экспертов. Обозначим I1- множество номеров экспертов, которые приняли решение в пользу класса V1, т.е.признали Z больным, а I2 — множество номеров экспертов, которые признали пациентаздоровым. Очевидно, что I1 I2 =; I1 I2 ={1,...,N}.
Тогдав ситуации S будем считать, что Z болен, если
/>, (20)
иZ здоров, если
/>. (21)
Решающееправило 4.
Рассмотримтеперь общий случай, когда требуется отнести объект Z к одному из M > 2классов V1,..., VM. Будем полагать, что известны априорные вероятности классовP(V1),..., P(VM) и условные вероятности ошибочных решенийP(A1/Vk),...,P(AN/Vk), (k=1,…,M), принимаемых N независимыми экспертамиA1,...,AN.
Пустьв результате обследования Z получена комбинация S частных решений экспертов.Обозначим Im — множество номеров экспертов, принявших решение в пользу m-гокласса. Очевидно, что Ii Ij = ( i, j = 1,...,M ), I1 ... IM ={1,...,N}.
Вэтом случае окончательное решение в пользу m-го класса будем принимать только втом случае, когда
P(Vm/S)= />P(Vk/S).(22)
Поформуле Байеса условие (22) эквивалентно следующему:
P(Vm)P(S/Vm) = />P(Vk)P(S/Vk) ,
или,что то же самое,
P(Vm)P(S/Vm) > P(Vk)P(S/Vk), k=1,...,M, k m (23)
Посколькудля любых m, k =1,..., M решения экспертов независимы, то
/>
/>
Наосновании условия (23) с учетом последних соотношений заключаем, чтоокончательное решение принимается в пользу класса Vm, если
k=1,…, M, k m выполняется неравенство:
/>>/>. (24)
Заключение.
Встатье показано, что в условиях противоречивой информации от независимыхэкспертов правомерно принимать окончательное решение, совпадающее с решениемболее квалифицированного эксперта, только при равновероятных классах. В болееобщем случае для минимизации вероятности ошибочных классификаций следуетучитывать как вероятности ошибочных классификаций каждого из экспертов, так исоотношения априорных вероятностей классов.
Рассмотреныправила интеграции частных решений независимых экспертов, которые можно пользоватьсядаже в тех практически важных случаях, когда эксперты принимают свои решениянеформально, опираясь на опыт и интуицию.
Предложенныйподход нашел применение при построении комплексного решающего правила длядиагностики кардиологических патологий у больных с неизмененной ЭКГ порезультатам автоматического анализа карт плотностей тока в плоскости сердца[25].
Список литературы
1.Ларичев О.И. Наука и искусство принятия решений. – М: Наука, 1979. – 200 с.
2.Макаров И.М. Теория выбора и принятия решений. – М.: Наука,1987. – 350 с.
3.Выявление экспертных знаний/О.И. Ларичев, А.И. Мечитов, Е.М.Мошкович, Е. М.Фуремс .– М.: Наука, 1989.– 128 с.
4.Макеев С.П., Шахнов И.Ф. Упорядочение альтернатив на основе расплывчатыхоценок: Сообщения по прикладной математике.– М.: ВЦАН СССР, 1989. – 42 с.
6.Миркин Б.Г. Проблема группового выбора. – М.: Наука, 1974. – 256 с.
7.Мулен Э. Кооперативное принятие решений: аксиомы и модели. – М: Мир, 1991. –464 с.
8.Биргер И.А. Техническая диагностика. – М.: Машиностроение, 1978.- 240 с.
9.Барабаш Ю.Л. Коллективные статистические решения при распознавании. – М.: Радиои связь, 1983. – 224 с.
10. On combining classifiers/ J. Kittler, M. Hatef, R.P.W. Duin, J.Matas// IEEE Transactions on Pattern Analysis and Machine Intelligence.- 1998.-№ 20.- P. 226–239.
11. Pranke J., Mandler E. A Comparison of Two Approaches forCombining the Votes of Cooperating Classifiers//Proceedings 11-th IAPRInternational Conference on Pattern Recognition,1992.- V. 2.- P. 611-614.
12. Kimura F., Shridhar M Handwritten numerical recognition based onmultiple algorithms// Pattern Recognition, 1991.- V. 24.- No. 10.- P. 969-983.
13. Ho T.K., Hull J.J., Srihari S.N. Decision combination inmultiple classifier systems//IEEE Transactions on Pattern Analysis and MachineIntelligence,1994.- V.16.- No. 1, 1994, P. 66-75.
14. Bagui S.C., Pal N.R. A multistage generalization of the ranknearest neighbor classification rule// Pattern Recognition Letters, 1995.- V.16.- No. 6.- P. 801-614.
15. Hashem S., Schmeiser B. Improving model accuracy using optimallinear combinations of trained neural networks// IEEE Transactions on NeuralNetworks,1995.- V.6.- No. 3.- P. 792-794.
16. Xu L., Krzyzak A., Suen C.Y. Methods of combining multipleclassifiers and their applications to handwriting recognition// IEEE Trans.SMC,1992.- V. 22.- No. 3.- P. 418-435.
17. Cho S.B.,Kim J.H. Multiple network fusion using fuzzy logic//IEEE Transactions on Neural Networks.- 1995.- V. 6.- No. 2.- P. 497-501.
18. Krogh A., Vedelsby J. Neural network ensembles, crossvalidation, and active learning// Advances in neural information processingsystems, 1995.- MIT Press.- Cambridge MA.-278 P.
19. Wolpert D.H. Stacked generalization// Neural Networks,1992.- V.5.- No. 2.- P. 241-260.
20. Woods K.S., Bowyer K., Kergelmeyer W.P. Combination of multipleclassifiers using local accuracy estimates// Proc. of CVPR98,1996.- P. 391-396.
21.Hansen L.K., Salamon P. Neural network ensembles// IEEETransactions on Pattern Analysis and Machine Intelligence,1990.- V.12,No. 10.- P. 993- 1001.
22.Миркин Б.Г. Анализ качественных признаков и структур .- М.: Статистика,1980.-320 с.
23.Власов В.В. Эффективность диагностических исследований. — М.: Медицина,1988.-256 с.
24.Васильев В.И. Распознающие системы. -Киев: Наукова думка, 1983.- 422 с.
25. Possibilities of Magnetocardiography in Coronary Artery DiseaseDetection in Patient with Normal or Unspecifically Changes ECG/I.Chaikovsky,F.Steinberg, B.Heiler, V.Sosnitsky, N.Budnic, L.Fainzilberg//Proceeding of the3-th International Congress on Coronary Artery Disease (Lyon, France, October2-5, 2000), 2000.- P. 415-422.
Дляподготовки данной работы были использованы материалы с сайта www.sciteclibrary.ru