Леонид Соломонович Файнзильберг
Предложено решающее правило, позволяющее оценивать состояние объекта в условиях противоречивой информации, полученной от группы независимых экспертов (алгоритмов). Для использования правила достаточно иметь информацию об априорных вероятностях классов и условных вероятностях ошибок экспертов. Описана архитектура системы, в которой наряду с формированием коллективного решения обеспечивается уточнение вероятностных характеристик, фигурирующих в решающем правиле.
Введение.
В различных областях приложения (техника, экономика, медицина и т.п.) профессиональная деятельность человека связана с принятием решений, которые сводятся к выбору оптимального варианта из множества альтернатив [1,2]. Для повышения эффективности принимаемых решений часто используется информация, полученная от группы экспертов [3-5]. В этом случае возникает необходимость формирования коллективного решения на основе “интеграции” частных решений членов группы. Типичным примером подобного коллектива является медицинский консилиум, принимающий окончательное решение на основании учета частных решений отдельных специалистов [6]. Идея коллективного решения получила также известность не только для группы людей, но и для совокупности формальных алгоритмов [7-19].
Известны различные подходы к интеграции частных решений. В одних случаях предлагается использовать метод голосования (majority vote method) [9,10] или ранжирования (label ranking method) [11, 12]. В других – использовать схемы, основанные на усреднении или линейной комбинации апостериорных вероятностей, которые оцениваются отдельными классификаторами [13,14], либо использовать алгоритмы нечетких правил (fuzzy rules) [15]. Развиваются также подходы, основанные на выделении в пространстве наблюдений локальных областей, в каждой из которых только один из частных классификаторов “компетентен” принимать решение [16,17].
Все эти работы имеют несомненный теоретический интерес и позволяют обосновать выбор той или иной схемы интеграции, если частные решения принимаются на основе формальных правил. В то же время довольно часто на практике эксперты принимают свои решения неформально, полагаясь на свой предшествующий опыт и интуицию.
Разумеется, в этих практически важных случаях также требуется обоснованный подход к интеграции частных решений экспертов. Например, какое окончательное решение должно быть принято, если в результате независимого обследования часть специалистов (экспертов) признала пациента здоровым, а другая часть – больным?
Можно привести и другие не менее актуальные примеры необходимости принятия коллективных решений в условиях ограниченной априорной информации о том, каким образом эксперты принимают свои частные решения.
В настоящей статье развивается один из возможных подходов к решению таких задач, предложенный в [18].
Постановка задачи.
Пусть некоторый объект Z может находиться в одном из М возможных состояний (классов) V1 ,...,VM с известными априорными вероятностями P(V1), ..., P(VM), . Ясно, что если не располагать какой либо дополнительной информацией, то состояние Z всегда следует относить к классу, имеющему наибольшую априорную вероятность. В этом случае величина
P0 =1- max{P(V1),...,P(VM)}, (1)
определяет минимальную вероятность ошибочной классификации.
Предположим теперь, что имеется N экспертов (алгоритмов) A1,…, AN, которые независимо один от другого принимают решения δj о состоянии Z в виде индикаторных функций
δi = k, если Ai решает в пользу Vk, i =1,…,N, k = 1,…, M. (2)
Будем характеризовать “квалификации” экспертов условными вероятностями ошибочных решений P(A1/Vk),...,P(AN/Vk), (k=1,…,M), которые считаются известными для всех N экспертов на основании предыдущего опыта. При этом, естественно допустить, что
P(Ai/Vk) < P0 для всех i = 1,…, N, k=1,…, M (3)
Ставится задача на основе имеющейся априорной информации по частным решениям независимых экспертов сформировать коллективное решение D =D(δ1, …, δN) о принадлежности Z к одному из M возможных классов (рис. 1).
Модель коллективного решения. Легко видно, что в общем случае число возможных комбинаций частных решений равно , причем только в M случаях эти решения будут согласованными (когда все эксперты принимают решения в пользу одного класса), а в остальных случаях решения противоречивы.
Пусть в результате обследования объекта получена некоторая комбинация S частных решений δ1, …, δN в форме (2). Обозначим Im - множества номеров экспертов, принявших решение в пользу m-го класса (m = 1,…,M). Очевидно, что Ii Ij = для любых i, j = 1,...,M и I1 ... IM ={1,...,N}.
Для минимизации средней вероятности ошибки коллективного решения D =D(δ1, …, δN) на множестве возможных комбинаций частных решений будем для каждой фиксированной комбинации принимать окончательное решение в пользу того из классов, который имеет наибольшую апостериорную вероятность:
(4)
где
.
По определению условная вероятность P(S / Vm) есть ни что иное как вероятность того, что в ситуации, когда имеет место класс Vm , эксперты, номера которых принадлежат множеству Im, приняли правильные решения, а остальные ошиблись. Поскольку мы предполагаем, что решения экспертов независимы, то по формуле произведения вероятностей
. (5)
На основании условия (4) с учетом (5) заключаем, что в ситуации окончательное (коллективное) решение следует принимать согласно правилу
. (6)
Для иллюстрации принятия коллективного решения по правилу (6) рассмотрим модельный пример.
Модельный пример.
Пусть некоторый объект может находиться в одном из трех классов, образующих полную группу случайных событий с априорными вероятностями P(V1) = 0.7, P(V2)=0.08 и P(V3) = 0.22. Состояние объекта оценивается 5 независимыми экспертами. Вероятности ошибок экспертов и возможная комбинация принятых ими частных решений представлены в таблице 1.
Таблица 1.
| Эксперт | Вероятности ошибок | Частные решения |
||
P(Ai /V1) |
P(Ai /V2) | P(Ai /V3) | i | |
| A1 | 0,04 | 0,01 | 0,03 | 1 = 1 |
| A2 | 0,01 | 0,03 | 0,02 | 2 = 3 |
| A3 | 0,03 | 0,05 | 0,01 | 3 = 2 |
| A4 | 0,02 | 0,02 | 0,06 | 4 = 2 |
| A5 | 0,01 | 0,05 | 0,04 | 5 = 3 |
Легко видно, что в данном случае частные решения экспертов противоречивы, причем І1={1}, І2={3,4}, І3={2,5}. Для принятия коллективного решения вычислим следующие величины
= 4,03·10-8,
= 1,12·10-6,
= 3,73·10-6.
Поскольку третья из найденных величин максимальна, то, на основании правила (6), принимаем окончательное решение в пользу класса V3.
Частный случай коллективного решения. Рассмотрим одну из типичных задач медицинской диагностики. Требуется отнести обследуемого пациента Z к одному из двух классов: V1 – болен, V2 – здоров на основании результатов двум диагностических тестов A1, A2. При этом будем считать известными априорные вероятности P(V1), P(V2), а эффективность каждого теста, как это принято в медицинской диагностике [19], характеризовать двумя показателями: чувствительностью Qi = 1- P(Ai /V1), где вероятность P(Ai /V1) ошибочного отнесения больного пациента к здоровому и специфичностью Wi = 1- P(Ai /V2), где вероятность P(Ai /V2) ошибочного отнесения здорового пациента к больному.
Ясно, что в результате тестирования возможны четыре комбинации частных решений:
S11: δ1 = 1, δ2 = 1;
S12: δ1 = 1, δ2 = 2;
S21: δ1 = 2, δ2 = 1;
S22: δ1 = 2, δ2 = 2.
Легко видно, что в ситуациях S12 и S21 частные решения противоречивы. Для принятия коллективного решения воспользуемся правилом (6). При этом в ситуации S12, когда A1 признал Z больным, а A2 - здоровым, окончательный диагноз следует ставить согласно схеме:
(7)
где λ = P(V2)/P(V1) – отношение априорных вероятностей здоровых и больных пациентов.
В ситуации же S21, когда A1 признал Z здоровым, а A2 – больным, окончательный диагноз следует ставить согласно схеме:
(8)
Заметим, что для принятия коллективного решения по правилам (6) –(8) требуется весьма ограниченная априорная информация, которая может быть получена на основании предыдущего опыта. При этом совершенно не требуется
В то же время мы сделали одно важное допущение о том, что решения экспертов независимы, которое, естественно, должно быть обоснованно. На практике достаточно веским обоснованием такого допущения может служить знания о том, что частные решения принимаются по статистически независимым данным.
Оценка вероятностных характеристик. Вполне понятно, что при решении практических задач точные значения вероятностных характеристик, фигурирующих в правилах (6)-(8), чаще всего неизвестны. Однако при достаточном объеме наблюдений вероятности P(Vk) и P(Ai / Vk) могут быть оценены соответствующими частотами:
(9)
(10)
где Gk – число появлений k-го класса (k = 1,…M) в выборке из G наблюдений, а Eki – число ошибочных решений i-го эксперта (i = 1,…, N) при анализе ситуаций, когда объект Z принадлежит k-му классу.
Рассмотрим схему оценки частот (9),(10), которая удобна для практического применения и может быть положена в основу системы поддержки принятия коллективного решения. Предположим, что для каждого из G наблюдений известна точная принадлежность Z к одному из возможных классов, выраженная в виде указаний “учителя” y[1], y[2], … , y[G], где y[n]. Запишем частоту появления k-го класса, оцененную согласно (9), в виде
(11)
где
Поскольку правую часть (11) можно выразить в виде суммы двух слагаемых
,
в первом из которых фигурирует оценка частоты появления k-го класса, вычисленная по G-1 наблюдениям, то после очевидных преобразований получим
. (12)
Для оценки вероятностей ошибок экспертов рассмотрим последовательность yk[1], yk[2], … , yk[Gk] указаний учителя, которые удовлетворяют условию yk[n] = k. Легко видно, что величина Eki , фигурирующая в правой части (11), может быть записана в виде суммы
,
где - штрафная функция, выраженная в форме
Тогда, оценка вероятности ошибки i-го эксперта при появлении k-го класса также может быть найдена по рекуррентной формуле
. (13)
Из выражений (12),(13) видно, что при неограниченном росте числа наблюдений величина поправки стремится к нулю, что, естественно, согласуется с предельной теоремой Бернулли [20] о сходимости по вероятности частоты случайного события к его вероятности.
На основе предложенного подхода легко может быть реализована система поддержки принятия коллективных решений, архитектура которой показана на рис. 2.
Блок формирования коллективного решения реализует решающее правило (6) на основании вводимых в систему частных решений 1,…, N группы независимых экспертов A1,…, AN . При этом в правиле (6) используются текущие значения оценок вероятностных характеристик P(Vk) и P(Ai/Vk), (i=1,…,N, k=1,…,M), которые хранятся в базе данных (БД) системы. В БД фиксируются также соответствующие классам V1,…,VM объемы наблюдений G1,…,GM в выборке G = G1 + … + GM, по которой были оценены указанные вероятностные характеристики.
Если после принятия коллективного решения по правилу (6) появляется возможность проверить истинное состояние объекта исследования, то такая дополнительная информация вводится в систему в виде указания “учителя” y[n] и используется для коррекции текущих значений оценок P(Vk) и P(Ai/Vk), (i=1,…,N, k=1,…,M) с помощью рекуррентных формул (12) и (13).
Такая архитектура системы, совмещающая коллективное решающее правило с возможностью его периодической коррекции, может быть рекомендован в различных областях приложения. Покажем это на примере задачи медицинской диагностики.
Известно, что для диагностики заболеваний сердечно-сосудистой системы в кардиологической практике используется электрокардиография, эхокардиография, реография и многие другие неинвазивные (косвенные) методы обследования. При этом хорошо известно, что достоверность таких методов существенно ниже, чем прямого метода – коронарографии. Однако совершенно очевидно, что метод коронарографии не может быть рекомендован для массовых обследований пациента, поскольку он является достаточно дорогим, а самое главное - небезопасным для пациента.
В то же время, на основе предлагаемого подхода можно объединить различные неинвазивные методы диагностики, используя коллективное решающее правило (6), и тем самым повысить эффективность принимаемых решений. Если же по медицинским показаниям некоторым из обследованных пациентов все же будет проводиться коронарография, то ее результаты непременно следует использовать в качестве указаний “учителя”. Тем самым будет обеспечиваться постоянное повышение достоверности диагностики в процессе эксплуатации системы.
Заключение.
Согласно правилу (6) для принятия обоснованного коллективного решения о текущем состоянии объекта исследования достаточно располагать лишь информацией об априорных вероятностях P(Vk) классов и условных вероятностях P(Ai/Vk) ошибок частных решений независимых экспертов. Важно отметить, что при решении практических задач правило (6) может быть использовано не только для интеграции решений группы людей, но и для совокупности различных алгоритмов.
Для улучшения эффективности системы поддержки принятия решений предложено помимо реализации в ней самого решающего правила (6) обеспечить возможность постоянного улучшения вероятностных характеристик, фигурирующих в этом правиле, на основе рекуррентных процедур (12) и (13).
Рассмотренный подход нашел практическое применение при построении коллективного решающего правила для диагностики кардиологических патологий у больных с неизмененной ЭКГ на основе интеграции решений совокупности алгоритмов интерпретации карт плотностей тока в плоскости сердца [21].
Список литературы
1. Ларичев О.И. Наука и искусство принятия решений. – М: Наука, 1979. – 200 с.
2. Макаров И.М. Теория выбора и принятия решений. – М.: Наука,1987. – 350 с.
3. Макеев С.П., Шахнов И.Ф. Упорядочение альтернатив на основе расплывчатых оценок: Сообщения по прикладной математике.– М.: ВЦАН СССР, 1989. – 42 с.
4. Миркин Б.Г. Проблема группового выбора. – М.: Наука, 1974. – 256 с.
5. Мулен Э. Кооперативное принятие решений: аксиомы и модели. – М: Мир, 1991.–464 с.
6. Васильев В.И. Распознающие системы (справочник).-К.Наукова думка.-1983.- 422 с.
7. Барабаш Ю.Л. Коллективные статистические решения при распознавании. – М.: Радио и связь, 1983.–224 с.
8. 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.
9. Pranke J., Mandler E. A Comparison of Two Approaches for Combining the Votes of Cooperating Classifiers//Proceedings 11-th IAPR International Conference on Pattern Recognition,1992.- V. 2.- P. 611-614.
10. Kimura F., Shridhar M Handwritten numerical recognition based on multiple algorithms// Pattern Recognition, 1991.- V. 24.- No. 10.- P. 969-983.
11. Ho T.K., Hull J.J., Srihari S.N. Decision combination in multiple classifier systems//IEEE Transactions on Pattern Analysis and Machine Intelligence,1994.- V.16.- No. 1, 1994, P. 66-75.
12. Bagui S.C., Pal N.R. A multistage generalization of the rank nearest neighbor classification rule// Pattern Recognition Letters, 1995.- V. 16.- No. 6.- P. 601- 614.
13. Hashem S., Schmeiser B. Improving model accuracy using optimal linear combinations of trained neural networks// IEEE Transactions on Neural Networks,1995.- V.6.- No. 3.- P. 792-794.
14. Xu L., Krzyzak A., Suen C.Y. Methods of combining multiple classifiers and their applications to handwriting recognition// IEEE Trans. SMC,1992.- V. 22.- No. 3.- P. 418-435.
15. 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.
16. РастригинЛ.А., Эренштейн Р.Х. Коллектив алгоритмов для обобщения алгоритмов решения задач.- Известия АН СССР.Техническая кибернетики, 1978, № 2, с.116-119.
17. Woods K.S., Bowyer K., Kergelmeyer W.P. Combination of multiple classifiers using local accuracy estimates// jProc. of the IEEE Computer Vision and Pattern Recognition Conf. (CVPR’96), San Francisco, Ca, USA.- 1996. - P. 391-396.
18. Файнзильберг Л.С. Байесова схема принятия коллективных решений в условиях противоречий // Проблемы управления и информатики.- 2002.- № 3.- С. 112-122. (http://www.sciteclibrary.ru/rus/catalog/pages/5656.html)
19. Власов В.В. Эффективность диагностических исследований. - М.: Медицина, 1988.-256 с.
20. Вентцель Е.С. Теория вероятностей. - М.: Наука, 1969. – 576 с.
21. Possibilities of Magnetocardiography in Coronary Artery Disease Detection in Patient with Normal or Unspecifically Changes ECG / I.Chaikovsky, F.Steinberg, B.Heiler, V.Sosnitsky, N.Budnic, L.Fainzilberg // Proceeding of the 3-th International Congress on Coronary Artery Disease (Lyon, France, October 2-5, 2000), 2000.- P. 415-422.