§ 62. Свойство монотонности

Чтобы понимать, как монотонность может быть использована в проблеме рака груди рассмотрим оценку кальцинозов в маммограмме. Используя данные выше определения, мы можем представить клинические случаи в терминах бинарных векторов с пятью обобщенными признаками: (x1, x2, x3, x4, x5). Затем рассмотрим два клинических случая, которые представлены двумя двоичными последовательностями: (10110) и (10100). Если радиолог правильно диагностировал набор (10100) как злокачественный, то, используя свойство монотонности, мы можем также заключить, что клинический случай (10110) должен также быть злокачественным.  

Это заключение основано на систематическом кодировании всех признаков «подозрительных на рак» как 1. Заметим, что в (10100) мы имели два показания для рака:

x3 = 1  (протоковая ориентация, имеющая значение 1; подозрительна на рак) и

x1 = 1  (количество и объем кальцинозов со значением 1; указание на рак).

Во втором клиническом случае мы имеем эти два наблюдения для рака и также x4 = 1 (сравнение с предыдущими экспертизами, подозрительными на рак). Аналогично, если мы знаем, что (01010) не подозрительно на рак, то и случай (00000) нельзя также считать подозрительным. Это верно, потому что во втором случае мы имеем меньше признаков, указывающих на наличие рака. Вышеупомянутые соображения – существо того, на чем основаны наши алгоритмы. Они могут скомбинировать логический анализ данных с монотонностью получить необходимое обобщение. Таким образом, можно избежать недостатком метода полного перебора.

Предполагается, что, если радиолог полагает, что случай является злокачественным, тогда он / она рекомендует биопсию. Более формально, эти две подпроблемы определены следующим образом.

Клиническая подпроблема лечения (P1) – один и только один из следующих двух результатов возможен:

1) «биопсия необходима»;

2) «биопсия не нужна».

Подпроблема диагноза (P2).

Так же как и выше, один и только один из двух следующих непересекающихся результатов возможен:

1) «подозрительный для злокачественного развития»;

2) «не подозрительный для злокачественного развития».

Наша цель состоит в том, чтобы извлечь способ которым должна оперировать система в случае двух дискриминантных Булевых функций f2 и f1:

―  функция f1 возвращает значение «истинна» (1), если решением является «биопсия необходима», и ложь (0) в противном случае; 

―  функция f2 возвращает значение «истинна» (1), если решением является «подозрительно на злокачественное развитие», и ложь (0) в противном случае.

Функция f1 связана с первой подпроблемой, в то время как вторая функция f2 связана со второй подпроблемой. Есть важное отношение между этими двумя подпроблемами P1  P2 и соответствующими им функциями f1(α), f2(α).  Проблемы вложены, т. е. если случай является подозрительным на рак (f2(α) = 1), то биопсию нужно рекомендовать (f1(α) = 1), поэтому f2(α) = 1 Þ f1(α) = 1. Также, если биопсия не рекомендуется (f1(α) = 0), то случай не является подозрительным на рак (f2(α) = 0), поэтому f1(α) = 0 Þ f2(α) = 0. Последние два утверждения эквивалентны f2(α) ³ f1(α) и f1(α) £ f2(α) для случая α. Пусть E+n, 1 – множество последовательностей α из En такие, что f1(α) = 1  (положительные случаи биопсии). Точно так же E+n, 2  – множество последовательностей α из En таких, что f2(α) = 1 (положительные случаи рака). Заметим, что связанное свойство формально означает, что E+n2 Í E+n1 (для всех случаев, подозрительных на рак, биопсию нужно рекомендовать) и f2(α) ³ f1(α) для всех α Î En.

Предыдущие две взаимосвязанные подпроблемы P1 и P2 могут быть сформулированы как проблема восстановления двух связанных монотонных Булевых функций f1 и f2.

Медику-эксперту представили идеи относительно монотонности и связанных функций как было определено выше, и ему понравилась идея использовать вложенные Булевы функции монотонности. Кроме того, диалог, который следовал, подтверждал законность этого предположения. Точно так же функция x2 = y(y1, y2, y3, y4, y5) для x2 («Форма и плотность кальциноза») была подтверждена как монотонная Булева функция.

Булева функция – компактное представление набора диагностических правил. Булева дискриминантная функция может быть представлена в форме множества ЕСЛИ–ТО-правил, но необязательно, чтобы эти правила означали дерево как в методе решающих деревьев. Булева функция может дать диагностическую дискриминантную функцию, которая не может быть получена методом решающих деревьев.

Например, подпроблема биопсии формулируется как

               f1(x) =  x2x4 Ú x1x2 Ú x1x4 Ú x3 Ú x5 .                    

Эта формула читается следующим образом:

ЕСЛИ (x2 И x4) ИЛИ (x1 И x2) ИЛИ (x1 И x4) ИЛИ (x3) ИЛИ (x5)

TО биопсия рекомендуется.

В медицинские термины это переводится так

ЕСЛИ (форма и плотность кальцинозов предполагает рак

            И сравнение с предыдущей экспертизой предполагат рак)

ИЛИ (количество, и объем, занятый кальцинозами предполагает рак

            И форму, и плотность кальцинозов предполагают рак)

ИЛИ (количество, и объем, занятый кальцинозами предлагает рак,

            И сравнение с предыдущей экспертизой предлагает рак)

ИЛИ (протоковая ориентация предлагает рак)

ИЛИ (связанные результаты исследования предлагают рак),

ТО  Биопсия рекомендуется.
Таким образом, основными шагами извлечения правил из медика-эксперта являются следующие:

―  разработать иерархию понятий и представить их как ряд монотонных Булевых функций;

―  восстановить каждую из этих функций с минимальной последовательностью вопросов эксперту;

―  объединить обнаруженные функции в полную диагностическую функцию;

―  представить полную функцию как традиционный набор простых диагностических правил вида: Если A и B и … F ТО Z.

Опишем шаг (2) – восстановления каждой монотонной Булевой функции с минимальной последовательностью вопросов для эксперта (рис. 21). Последний блок 2.5 предусматривает интервьюирование эксперта с минимальной динамической последовательностью вопросов. Эта последовательность основана на фундаментальной лемме Hansel [122 ;109]. Мы опускаем детальное описание определенных математических шагов. Они могут быть найдены в [Там же]. Общая идея дается на примере интерактивной процедуры в табл. 8. Минимальная последовательность вопросов означает, что мы достигаем минимума Шенноновской функции, т. е. минимальное количество вопросов обязано восстанавливать самую сложную Булевую функцию монотонности с n аргументами. Эта последовательность не написана заранее. Это зависит от предыдущих ответов эксперта, поэтому каждый последующий вопрос определен динамически. Табл. 8 иллюстрирует это. Столбцы 2, 3 и 4 представляют собой значения определенных выше функций f1, f2  и y. Мы опускаем восстановление функции n(w1, w2, w3),  потому что нужно немного вопросов для восстановления этой функции, но общая схема – та же самая, что и для функций f1, f2  и y и начинается с рассмотрения всех бинарных наборов троек (010), (110).

В таблице первый вопрос: «Представляет ли последовательность (01100) случай, требующий биопсии?» Здесь, x1 = 0 и (01100) = (x1, x2, x3, x4, x5). Если ответ «да» (1), то следующий вопрос будет о биопсии для случая (01010). Если ответ «нет» (0), то следующий вопрос будет о биопсии для (11100). Эта последовательность вопросов не случайна. Как было упомянуто выше, это выведено из леммы Hansel [Там же]. Все 32 возможных случая с пятью бинарными признаками (x1, x2, x3, x4, x5) представлены в столбце 1 табл. 8. Они сгруппированы, и группы называют цепями Hansel [Там же]. Последовательность цепей начинается с самой короткой цепи   *1 – (01100) и (11100). Эта цепь состоит из двух назначенных случаев, (01100) < (11100) для пяти двойных наборов признаков. Тогда наибольшая цепь *10 состоит из 6 назначенных случаев: (00000) < (00001) < (00011) < (00111) < (01111) < (11111). Аналогично случаи упорядочены как векторы в каждой цепи. 

Чтобы строить цепи, представленные в табл. 8 (с пятью измерениями, например x1, x2, x3, x4, x5 или y1, y2, y3, y4, y5), используется последовательный процесс. Сначала произведены все 1-мерные цепи (в E1), затем они используются, чтобы произвести цепи более высоких измерений до измерения пять. Каждый шаг порождения цепи состоит в использовании текущей i–размерной цепи и построения (i + 1)-размерной цепи. Поколение цепей для следующего измерения (i + 1) появляется в результате следующего процесса.

·                 Мы клонируем i–пространственную цепь, например, имея 1-мерную цепь (0) < (1) мы производим ее копию: (0) < (01).

·                 После этого мы наращиваем эти цепи, добавляющие второе измерение.

·                  

Таблица 8. Динамическая последовательность интервью с экспертом

 

Дело

f1

биопсия

f2

Рак

y Форма и плотность кальцинозов

Монотонное удлинение

Цепь

Дело

1® 1   

0® 0

1

2

3

4

5

6

7

8

(01100)

1*

1*

1*

1.2;6.3;7.3

7.1;8.1

Цепь 1

 1.1

(11100)

1

1

1

6.4;7.4

5.1;3.1

 1.2

(01010)

1*

0*

1*

2.2;6.3;8.3

6.1;8.1

Цепь 2

 2.1

(11010)

1

1*

1

6.4;8.4

3.1;6.1

 2.2

(11000)

1*

1*

1*

3.2

8.1;9.1

Цепь 3

 3.1

(11001)

1

1

1

7.4;8.4

8.2;9.2

 3.2

(10010)

1*

0*

1*

4.2;9.3

6.1;9.1

Цепь 4

 4.1

(10110)

1

1*

1

6.4;9.4

6.2;5.1

 4.2

(10100)

1*

1*

1*

5.2

7.1;9.1

Цепь 5

 5.1

(10101)

1

1

1

7.4;9.4

7.2;9.2

 5.2

(00010)

0*

0

0*

6.2;10.3

10.1

Цепь 6

 6.1

(00110)

1*

1*

0*

6.3;10.4

7.1

 6.2

(01110)

1

1

1

6.4;10.5

 

 6.3

(11110)

1

1

1

10.6

 

 6.4

(00100)

1*

1*

0*

7.2;10.4

10.1

Цепь 7

 7.1

(00101)

1

1

0*

7.3;10.4

10.2

 7.2

(01101)

1

1

1*

7.4;10.5

8.2;10.2

 7.3

(11101)

1

1

1

5.6

 

 7.4

(01000)

0*

0

1*

8.2

10.1

Цепь 8

 8.1

(01001)

1*

1*

1

8.3

10.2

 

 8.2

(01011)

1

1

1

8.4

10.3

 8.3

(11011)

1

1

1

10.6

9.3

 8.4

(10000)

0*

0

1*

9.2

10.1

Цепь 9

 9.1

(10001)

1*

1*

1

9.3

10.2

 9.2

(10011)

1

1

1

9.4

10.3

 9.3

(10111)

1

1

1

10.6

10.4

 9.4

(00000)

0

0

0

10.2

 

Цепь 10

 10.1

(00001)

1*

0*

0

10.3

 

 10.2

(00011)

1

1*

0

10.4

 

 10.3

(00111)

1

1

1

10.5

 

 10.4

(01111)

1

1

1

10.6

 

 10.5

(11111)

1

1

1

 

 

10.6

Вопросов

13

13

12

 

 

 

 

 

·                 Цепь 1 : (00) < (01).

·                 Цепь 2 : (10) < (11).

Здесь 0 добавлен слева от обоих случаев в цепи 1, и 1 добавлена к обоим случаям в цепи 2.

·                 Затем мы отделяем главный случай (11) от цепи 2 и добавляем его в качестве головы к цепи 1, создавая две 2-мерные цепи:

         Новая цепь 1 – (00) < (01) < (11) и

         Новая цепь 2 – (10). 

Этот процесс продолжается и останавливается в пятом измерении для áx1, x2, x3, x4, x5ñ и áy1, y2, y3, y4, y5ñ. Табл. 8 представляет результат этого процесса. Цепи пронумерованы от 1 до 10, каждый случай имеет свой номер в цепи. Например, 1.2 означает второй случай в первой цепи. Знак « * » в столбцах 2, 3 и 4 маркируют ответы, полученные от эксперта. Например, 1* для случая (01100) в столбце 3 означает, что эксперт ответил «да». Остающиеся ответы для той же самой цепи в столбце 3 автоматически получены, используя монотонность. Признак f1(01100) = 1 для случая 1.1  расширен для случаев 1.2, 6.3. и 7.3 таким путем. Аналогично вычисляются значения третьей монотонной Булевой функции ψ, используя таблицу 8. (Признаки в последовательности (10010) интерпретируются как y1, y2, y3, y4, y5 вместо x1, x2, x3, x4, x5 которые использовались для f1 и f2. Цепи Hansel те же самые, так как количество признаков то же самое).

В столбцах 5 и 6 выписаны случаи, расширяющие значения функций, без опроса эксперта. Столбец 5 предназначен для расширения значений функци с 1 до 1, столбец 6 для расширения значений с 0 до 0. Если эксперт дал противоположный ответ (f1(01100) = 0) по сравнению с представленным в табл. 8 для функции f1 и случая 1.1 (01100), то значения 0 могут быть расширены в столбце 2 для случаев 7.1 (00100) и 8.1 (01000). Эти случаи перечислены в столбце 6 для случая (01100). Тогда нет необходимости спрашивать эксперта о случаях 7.1 (00100) и 8.1 (01000). Монотонность обеспечивает ответ. Отрицательный ответ f1 (01100) = 0 не может быть расширен для f1 (11100). Эксперта надо спросить относительно f1 (11100). Если его / ее ответ отрицательный  f1(11100) = 0, то эти значения могут быть расширены для случаев 5.1. и 3.1, перечисленных в столбце 6 для случая 1.2. Полагаясь на монотонность, значение f1 для них также будет 0.

Общее количество случаев со знаком « * » в столбце 1 равно 13, для столбцов 3 и 4 они равны соответственно 13 и 12. Эти количества показывают, что 13 вопросов необходимы для восстановления каждой из функций f1 и f2 как функций от x1, x2, x3, x4, x5  и 12 вопросов необходимы для восстановления функции от y1, y2, y3, y4, y5. Это только 37.5 % из 32 возможных вопросов и 60 % от возможного максимума гарантируемого леммой Hansel.


Полное восстановление любой из функций f1 и f2 с 11 аргументами без оптимизации процесса интервью потребовало бы до 211 = 2048 вопросов к медику-эксперту. Заметим, что фактически все исследования по созданию автоматизированных диагностических систем по раку молочной железы получают диагностические правила, использующие значительно меньше чем 1000 случаев. Однако согласно лемме Hansel и согласно предположению о монотонности оптимальный (т. е. минимальный) диалог для восстановления монотонной Булевой функции потребовал бы максимум следующего количества вопросов:

Это новое значение является в 2.36 раза меньше, чем предыдущий верхний предел в 2048 вопросов. Однако даже этот верхний предел 924 может быть уменьшен. Иерархия уменьшает максимальное количество вопросов для восстановления монотонных Булевых функций с 11 бинарными переменными к 72 вопросам (недетерминированный опрос) и к 46 используя лемму Hansel. Фактическое количество вопросов, которые были заданы, около 40, включая и связанные функции (рак и биопсию) т. е. приблизительно 20 вопросов в функцию.