Теория тестового распознавания

Кудрявцев В.Б.
Андреев А.Е.
Гасанов Э.Э.

Теория тестового

распознавания

МОСКВА

ФИЗМАТЛИТ ®

УДК 519.71
ББК 22.18
К 88

Ку д р я в ц е в
В. Б.,
А н д р е е в
А. Е.,
Га с а н о в
Э. Э.
Теория
тестового
распознавания.
—
М.:
ФИЗМАТЛИТ,
2007.
—
320
с.
—
ISBN 978-5-9221-0872-0.

Описывается логический подход к распознаванию образов. Его основным
понятием выступает тест. Анализ совокупности тестов позволяет строить
функционалы, характеризующие образ и процедуры вычисления их значений.
Указываются качественные и метрические свойства тестов, функционалов и
процедур распознавания. Приводятся результаты решения конкретных задач.
Книга может быть рекомендована математикам, кибернетикам, информатикам и инженерам как научная монография и как новый технологический
аппарат, а также как учебное пособие для студентов и аспирантов, специализирующихся в области математической кибернетики, дискретной математики и
математической информатики.

Научное издание

КУДРЯВЦЕВ Валерий Борисович
АНДРЕЕВ Александр Егорович
ГАСАНОВ Эльяр Эльдарович

ТЕОРИЯ ТЕСТОВОГО РАСПОЗНАВАНИЯ

Редактор И.Л. Легостаева
Оригинал-макет: И.В. Шутов
Оформление переплета: Н.В. Гришина

Подписано в печать 02.08.07. Формат 6090/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 20. Уч.-изд. л. 25.4. Тираж 100 экз. Заказ №

Издательская фирма «Физико-математическая литература»
МАИК «Наука/Интерпериодика»
117997, Москва, ул. Профсоюзная, 90
E-mail: fizmat@maik.ru, fmlsale@maik.ru;
http://www.fml.ru

Отпечатано с готовых диапозитивов
в ОАО «Ивановская областная типография»
153008, г. Иваново, ул. Типографская, 6
E-mail: 091-018@adminet.ivanovo.ru

ISBN 978-5-9221-0872-0

ISBN 978-5-9221-0872-0

c⃝ ФИЗМАТЛИТ, 2007

c⃝ В. Б. Кудрявцев, А. Е. Андреев,
Э. Э. Гасанов, 2007

ОГЛАВЛЕНИЕ

Предисловие . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Часть I.
Тестовое распознавание

Г л а в а 1. Основные результаты . .. . . . . . . . . . . . . . . . . . . . . . .
14
1.1. Тесты для матриц с малым числом строк . .. . . . . . . . . .
14
1.2. Тесты для матриц с заданным графом сравнения. .. . . . .
19
1.3. Короткие тесты . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
1.4. Тесты для функций k-значной логики . .. . . . . . . . . . . . .
43
1.5. Тесты для классов Поста . .. . . . . . . . . . . . . . . .. . . . . . .
47

Часть II.
Качественные и метрические свойства
тестовых алгоритмов

Введение. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54

Г л а в а 2. Некоторые предварительные оценки . .. . . . . . . . . . . .
55
2.1. Оценки, связанные с числом сочетаний. .. . . . . . . . . . . .
55
2.2. Верхние оценки числа тестовых и тупиковых тестовых
таблиц . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .
61
2.3. Нижние оценки числа тестовых и тупиковых тестовых
таблиц . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
2.4. Оценки совместных вероятностей . .. . . . . . . . . . . . . . . .
88

Г л а в а 3. Асимптотика числа тупиковых тестов . .. . . . . . .. .. . . . 101
3.1. Случай «низких» таблиц. .. . . . . . . . . . . . . . . . . . . . . . . 103
3.2. Случай «высоких» таблиц. Математическое ожидание
числа тупиковых тестов. .. . . . . . . . . . .. . . . . . . . . . . . . . 116
3.3. Случай «высоких» таблиц. Асимптотика числа тупиковых тестов . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . 128

Оглавление

Г л а в а 4. Минимальная длина тупикового теста. .. . . . .. . . . . . . 136
4.1. Вспомогательные оценки. .. . . . . . . . . . . . . . . . . . . . . . . 137
4.2. Случай «низких» таблиц. .. . . . . . . . . . . . . . . . . . . . . . . 145
4.3. Случай «высоких» таблиц. .. . . . . . . . . . . . . . . . . . . . . . 160

Г л а в а 5. Алгоритмы построения тупиковых тестов . .. . . . . . . . 172
5.1. Связные локальные алгоритмы . .. . . . . . . . . . . . . .. . . . . 176
5.2. Минимизация сложности в классе связных локальных
схем алгоритмов . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.3. Асимптотическая эффективность Д-алгоритма . .. . . . . . 184

Часть III.
Т-алгоритмы распознавания,
использующие короткие тесты

Г л а в а 6. Основные понятия и результаты . .. . . . . . . . . . . . . . . 194

Г л а в а 7. Асимптотическое поведение весов признаков . .. . . . . . 205
7.1. Некоторые предварительные оценки . .. . . . . . . . . . . . . . 205
7.2. Оценки числа пар тестовых и тупиковых тестовых таблиц. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
7.3. Оценки числа f-тестовых пар таблиц . .. . . . . . .. . . . . . . 238
7.4. Асимптотика числа тупиковых тестов . .. . . . . . . . . . . . . 258
7.5. Вычисление весов признаков. .. . . . . . . . . . . . . . . . . . . . 271

Г л а в а 8. Устойчивость опорных множеств при искажениях таблиц. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
8.1. Модель появления ошибок в исходной таблице . .. . . . . . 280
8.2. Устойчивость множества коротких тестов . .. . . . .. . . . . . 281
8.3. Неустойчивость множества всех тупиковых тестов . .. . . 287
8.4. Неустойчивость множества «очень коротких» тестов . .. . 300

Г л а в а 9. Алгоритмы построения коротких тестов. .. . . . . . . . . . 303
9.1. Алгоритм Д1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
9.2. Алгоритм Д2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

Список литературы . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

Предисловие

В предлагаемой монографии излагаются научные результаты, полученные по сравнительно новому направлению в теории
распознавания образов, которое основывается на использовании
аппарата логических тестов.
Это направление возникло в середине прошлого столетия и
по праву связывается с именами С. В. Яблонского и И. А. Чегис,
которые в своих работах [67, 69] впервые ввели понятие теста и
выявили ряд его важных свойств, что в итоге позволило с успехом применить тестовый подход к решению задач распознавания
образов.
Многие задачи распознавания могут быть описаны с помощью следующей схемы. Имеется некоторый объект A, который
может находиться в каких-то состояниях qi, i ∈ {1, 2, ..., m}.
Последние
характеризуются параметрами-признаками xj, j ∈
∈ {1, 2, ..., n}. Известно, что некоторые наборы значений этих
признаков α = (a1, a2, ..., an) описывают состояние qi. Эти наборы
как строки составляют матрицу Ti. Совокупность T как матрица,
образованная подматрицами Ti, описывает все состояния объекта A. Для того чтобы понять, какое состояние описывает конкретный набор значений признаков, нужно проверить, в какую
подматрицу Ti он входит. Если он не содержится в них, то набор
не соответствует состояниям. Если входит в подматрицу Ti, то
в предположении, что подматрицы не пересекаются, этот набор
описывает состояние qi.
В реальной ситуации и признаки, и сами подматрицы Ti, как
правило, описываются не полностью, а потому решение вопроса
о том, какое состояние описывает данный набор, становится
нетривиальным. Этот вопрос и называют задачей распознавания.
Тем самым задачу распознавания можно сформулировать так:
даны матрица T ′ и ее подматрицы T ′
i, требуется указать оператор
ϕ, который по этим подматрицам и заданному набору признаков
вычисляет состояние объекта A, представленное предъявленным
набором. Ясно, что нахождение ϕ в общем случае требует различных допущений относительно свойств A.
К числу исторически первых таких допущений относятся
алгебраические, геометрические и вероятностные свойства A.
Каждое из них породило соответствующее направление в теории

Предисловие

распознавания. В них накоплен большой опыт, включающий как
перечень решенных и потенциально решаемых задач, так и методов их решения.
Особый класс составляют задачи, в которых характеризация
объекта A является опосредованной или абстрактной, без подходящей интерпретации.
Типичным примером такого объекта является техническое
устройство, характеризуемое некоторыми своими параметрамипризнаками. Это устройство может иметь неисправности — состояния, каждое из которых описывается соответствующей подматрицей Ti. Тогда, зная T, по текущему набору признаков
α = (a1, a2, ..., an), можно как отмечалось, решить задачу распознавания состояния q объекта A.
С. В. Яблонский и И. А. Чегис [67, 69] заметили, что вообще
говоря, такое распознавания можно осуществлять, не используя
всю матрицу T, а только ее часть. Ими было введено понятие
теста для T следующим образом.
Пусть σ — набор признаков, Ti,σ — часть таблицы Ti, образованная столбцами, соответствующими σ, а Tσ — все Ti,σ. Набор
σ образует тест для T, если Ti,σ и Ti′,σ не имеют общих строк
при i ̸= i′. Таким образом, тест σ уже сам может решать задачу
распознавания после анализа множества Tσ и набора ασ. Тест
выступает в роли эксперта, принимающего решение что части
набора α и по T.
С. В. Яблонский и И. А. Чегис предложили логическое решение задачи описания множества ℑ(T) всех тестов для T. Этот
подход нашел применение в технической диагностике.
Позже он был распространен и на другие объекты. В качестве
A были рассмотрены рудные образования и в предположении,
что T доступно лишь фрагментарно в виде T ′, а множество
тестов для T и T ′ видимо «мало» отличаются друг от друга.
Ю. И. Журавлев, Ф. П. Кренделев и А. Н. Дмитриев [34]
предложили оценивать роли признаков в решении задачи распознавания как долю вхождения их в ℑ(T). Эта величина pj
для признака xj, называемая информационным весом, позволила
им рассмотреть при специальной кодировке значений признаков
линейный функционал n
j=1 pjxj, ввести некоторые пороги di
для Ti и по значению n
j=1 pjxj и di определять близость набора
значений признаков α = (a1, a2, ..., an) к некоторой из матриц Ti.
На этом пути они предложили решение ряда задач по оценке
месторождений полезных ископаемых.

Предисловие
7

Позже В. И. Переяславский [50, 51] исследовал вопрос, когда линейный функционал n
j=1 pjxj доставляет верное решение
задачи распознавания.
Сюда примыкают рассмотрения А. Шайеба [68], посвященные выяснению возможностей линейных функционалов в решении задачи распознавания в общем случае.
Другое развитие идеи использования тестов было осуществлено В.Б.Кудрявцевым [36]. Как отмечалось, тест σ может выступать в качестве «эксперта» для определения по набору α
состояния q объекта A. В случае, когда σ ∈ ℑ (T ′), он по α
из T уже, вообще говоря, не решает задачи принадлежности α
некоторому Ti, поскольку ℑ (T ′) может не совпадать с ℑ (T).
Более того, он может отнести α к другой матрице Tj, или
вообще отказаться от принятия решения, когда ασ не входит ни
в одну из матриц T ′
i,σ. Таким образом, возникает необходимость
подвергнуть анализу набор α с помощью всего доступного нам
множества ℑ (T ′). Используя каждый тест σ из ℑ (T ′) для α, получаем вектор «голосов» χ (α) = (k1, ..., km, km+1), где ki (i ⩽ m)
— число остальных тестов, проголосовавших за принадлежность
Ti, km+1 — число, «воздержавшихся» голосов.
Можно считать, что в векторе χ координаты пронормированы, т. е. поделены на число тестов в ℑ (T ′). Тогда kl интерпретируем как меру выраженности свойства α принадлежать Tl при
l ⩽ m, а km+1 — не принадлежать T ′; здесь следует полагать,
что ℑ (T ′) и ℑ (T) отличаются достаточно «мало».
Функционал χ был успешно опробован в решении ряда прикладных задач, но вместе с тем обнаружились и определенные
трудности в его использовании. Главными из них являлись сложностные факторы и слабое согласование численных результатов
с реальностью для отдельных задач распознавания. Это привело
к необходимости отхода от голосования по всему множеству
тестов и к замене его специальными семействами. К их числу
относятся тупиковые, короткие, минимальные тесты и их ограничения.
Тупиковый тест представляет собой тест, у которого любое
собственное подмножество признаков не образует тест.
Короткий тест по числу признаков близок к логарифму числа
признаков в T.
Минимальный тест имеет наименьшее число признаков из
всех возможных.
Возникающие функционалы распознавания, соответствующие голосованию по этим семействам, обозначаем через χT T ,
χKT и χMT , а сами семейства называем основными.

Предисловие

Выяснились огромные преимущества функционала χKT в решении задач распознавания. С его помощью было решено большое число задач геологии, экономики, военного дела и других
областей.
Были, например, установлены новые месторождения нефти,
газа и олова в Сибири [29], оценены перспективы развития
конкретных экономических районов, проводился анализ текущей военно-политической ситуации, устанавливался диагноз заболевания и, соответственно, оптимальный режим лечения для
него [42].
Приблизительно в то же время идею голосования использовали Ю. И. Журавлев и его ученики при голосовании по подмножествам признаков, состоящих из заданного числа элементов.
В частности, они предложили оптимизацию выбора конкретного
значения r, при котором распознавание оказывается наилучшим [23].
Особая значимость функционалов χ, χT T , χKT и χMT , в решении задач распознавания, подтвержденная практикой, создала
предпосылки для разработки тестовой теории распознавания. Ее
создание предполагало решение следующих задач.
1. Получение оценок для числа основных видов тестов матрицы T, имеющей заданные параметры ее подматриц Ti.
2. Нахождение точных и приближенных алгоритмов построения основных семейств тестов.
3. Выяснение того, когда для T и T ′ заданные виды их основных семейств отличаются на заданную долю.
4. Решение обратной задачи для 3.
5. Выделение того семейства из основных, которое для T ′
лучше остальных решает задачу распознавания.
6. Нахождение быстрых алгоритмов вычисления функционалов распознавания для T, соответствующих основным семействам.
7. Выяснение роли отдельных признаков в решении задачи
распознавания и определение корреляции между ними для
T ′.
8. Решение задач 1–7 при заданном графе сравнения для T ′
i в
T ′ с соответствующим уточнением понятий видов тестов.
9. Решение задач 1–8 для почти всех матриц T ′.
В решении задач 1 и 2 в случае, когда в T ′ каждая подматрица T ′
i состояла из одной строки, первые результаты получили
В. А. Слепян [60] и В. Н. Носков [43, 44], оценивших сверху и
снизу число тестов и тупиковых тестов в таких матрицах.

Предисловие
9

Затем в предложении, что в T признаков много больше,
чем строк, Е. В. Дюковой [21] была разработана специальная
комбинаторная техника, с помощью которой ею были найдены
асимптотики тестов и тупиковых тестов для почти всех таблиц
T ′ с заданными соотношениями параметров ее размерностей; эта
техника ей позволила синтезировать оптимальные детерминированные и стохастические алгоритмы построения тестов и тупиковых тестов, а также решить задачу поведения весов признаков и
значений их корреляций. Таким образом, Е. В. Дюковой удалось
частично решить задачи 1, 2, 6, 7, 9.
Работа Е. В. Дюковой была важной по своему значению в
создании теории тестового распознавания.
Продвижения Е. В. Дюковой затем были развиты и существенно усилены А. Е. Андреевым [5]. Им была разработана
новая специальная техника, позволившая:
• найти асимптотические поведения для числа тестов для
произвольных размерностных характеристик матриц;
• построить соответствующие оптимальные алгоритмы детерминированного и стохастического типа для нахождения
указанных тестов;
• частично решить задачу 4, указав возможные доопределения матриц T ′
i таким образом, чтобы множества ℑ (T ′) и
ℑ (T) совпадали;
• найти длины минимальных тестов и их число;
• выявить веса признаков и корреляции между ними;
• распространить результаты в решении задач 1, 2, 6, 7 на
случай произвольного графа сравнимости в таблице T для
почти всех таблиц.
Таким образом, А. Е. Андрееву удалось решив в определенной мере задачи 1, 2, 3, 6, 7, 8 и 9, кардинально расширить
базу знаний в теории тестов. В то же время из его результатов и частично из результатов Е. В. Дюковой вытекало, что
эффективность распознавания процедур, основанных на тестах,
существенно зависит от вида семейств тестов из основных, по
которым идет распознавание.
Этому вопросу были посвящены исследования А. А. Кибкало
[27]. Оказалось, что в качестве оптимального множества «голосующих» тестов следует выбирать так называемые «короткие»
тесты. Если таблица T имеет m строк, то под коротким тестом для T ′ понимается величина «близкая» к ln m − ln ln m,
А. А. Кибкало для случая, когда T ′ состоит из двух подматриц,

Предисловие

установлено, что:
• вес признака по тупиковым тестам уменьшается с увеличением доли различаемых строк из T ′
1 и T ′
2;
• вес признака по тестам не зависит от доли различаемых
строк из T ′
1 и T ′
2 и почти всегда равен 1/2;
• вес признака по коротким тестам растет с увеличением
доли различаемых строк из T ′
1 и T ′
2;
• вес признака, различающего больше половины пар строк
по тестам, длина которых близка к минимальной, почти
всегда равен единице;
Таким образом, содержательно становится ясным преимущество коротких тестов и «очень» коротких тестов, т. е. близких к
минимальным тестам перед остальными в выявлении признаков,
лучше других отличающих подматрицы T ′
1 и T ′
2. Он существенно
продвинулся в решении задачи 7.
Далее была изучена ситуация, близкая к задачам 3 и 5.
А. А. Кибкало установил, что в случае, когда в матрице T ′

возможны искажения: множество почти всех тупиковых тестов
перестает быть таковым после искажения:
• множество очень коротких тестов почти полностью меняется;
• множество коротких тестов практически не меняется.
Он же построил асимптотически оптимальный алгоритм перечисления коротких тестов, т. е. решил для рассматриваемого
случая задачи 2 и 9.
Все задачи 1–9 в общем случае относятся к числу переборных и потому возникающие для них алгоритмы при больших
размерах матриц T ′ мало применимы. Возникает необходимость
перехода к более простым, но менее точным алгоритмам их
решения.
Исторически первый приближенный алгоритм решения задач
6 и 7 был предложен В. Е. Кузнецовым [38]. Этот алгоритм типа
Монте-Карло использовался в процедурах решения практических
задач распознавания. Затем возникли приближенные алгоритмы
для этих задач у Е. В. Дюковой, А. Е. Андреева и А. А. Кибкало.
Позже М. В. Носовым [49] был предложен алгоритм вычисления χ, основанный на экспоненциально сложном анализе
множества T ′ с последующим полиномиальным по сложности
вычислении χ по набору α.
Восстанавливая хронологию, необходимо подчеркнуть, что
первые задачи, которые удалось решить Ю. И. Журавлеву и его

Предисловие
11

коллегам, имели матрицу T ′ с числом строк и столбцов соответственно до 20.
Работа В. Е. Кузнецова позволила решать подобные задачи с
уже до ста строк и столбцов в T ′.
Е. В. Дюкова расширила класс таких матриц до имеющих 200
столбцов и 50 строк.
А. Е. Андреев распространил эти возможности до матриц
размерами в 200 строк и 200 столбцов.
А. А. Кибкало смог использовать уже матрицы размерами 500
строк и 500 столбцов.
Современные компьютеры позволяют еще на порядок и более
увеличить размеры реально обрабатываемых матриц.
В рассмотренной ситуации в общем случае не предполагалось, что имеется некоторая связь между подматрицами T ′
i матрицы T ′. Специальный случай возникает при допущении такой
связи. Здесь следует выделить рассмотрение такой модели.
Пусть A является техническим устройством с r входами и одним выходом. На входы Q поступают значения a из
Ek = {0, 1, ..., k − 1}, а на выходе снимается значение f (a1, ..., ar)
— некоторой функции k-значной логики. Считается, что на входах могут возникать ошибки определенного типа γ, меняющие
набор (a1, ..., ar) на (a′
1, ..., a′
r). Тогда в общем случае на подаваемом наборе (a1, ..., ar) значение f меняется. Требуется указать
некоторое число наборов, вычисляя f на которых, можно установить, была ли ошибка на входах A.
Эти наборы образуют тест и обычно требуется, чтобы он имел
наименьшее число элементов. Далее допускается, что функция
f может быть любой от фиксированного числа r переменных и
ставится вопрос о том, каково минимально достаточное число
Lk(r, γ), такое что для любых из указанных функций f и ошибки типа γ найдется тест из Lk(r, γ) элементов, который по f
определяет, была ли на входах A, реализующего f, допущена
ошибка γ.
Отметим здесь две группы основных результатов. Первую составляют результаты Г. Р. Погосяна [54], который установил поведение Lk(r, γ) для γ, соответствующим коротким замыканиям,
слипаниям, инверсиям и др. Ранее в этом направлении интересные продвижения были получены В. Н. Носковым [46]. Вторую
составляют результаты О. А. Долотовой [16], которая для тех
же типов ошибок нашла поведение функции для LC
2 (r, γ), аналогичной функции L2(r, γ), но соотнесенной с заданным классом
Поста C функций алгебры логики. К этим группам результатов
примыкают подобные рассмотрения для почти всех функций.

Предисловие

В целом же тестирование технических устройств привлекает большое число исследователей, которыми накоплен большой
опыт, заслуживающий отдельного обсуждения. Упомянем здесь
лишь итоговые изложения в [66].
Все излагаемые в книге результаты выполнены на механикоматематическом факультете МГУ им. М. В. Ломоносова в научной школе кафедры математической теории интеллектуальных
систем. Они докладывались на научных форумах в стране и за
рубежом, библиография приведена в конце книги.
Книга может быть полезна для специалистов по распознаванию образов, для исследований и учебного процесса в этой
области.
Авторы выражают свою признательность коллегам по кафедре математической теории интеллектуальных систем, интерес
которых к тематике книги стимулировал ее создание, а также Е. С. Быченковой, Ю. Г. Гераськиной, Г. А. Майлыбаевой,
Е. Н. Остроуховой, А. П. Соколову, Е. Е. Титовой, Т. Д. Уваровой
и А. А. Хариной, помогавшим авторам в ее оформлении.
Авторы благодарны Российскому фонду фундаментальных
исследований за финансовую поддержку издания этой книги
(грант РФФИ № 07-01-07034-д).