Proceedings 2002

ВЫЧИСЛИТЕЛЬНАЯ МОДЕЛЬ ДЛЯ ГЕНЕРАЦИИ АЛГОРИТМОВ ПОСТРОЕНИЯ ХОРОШИХ КЛАССИФИКАЦИОННЫХ ТЕСТОВ И ЕЁ СВЯЗЬ С МОДЕЛИРОВАНИЕМ ПРАВДОПОДОБНЫХ РАССУЖДЕНИЙ

 

 

К. А. Найденова

Военно-медицинская академия

naidenova@mail.spbnit.ru

 

 

Ключевые слова: классификация, диагностика, правдоподобные рассуждения, индуктивный вывод правил по примерам, алгебраическая решётка, когнитивное моделирование

 

В работе даётся определение хорошего диагностического теста как элемента алгебраической решетки с двойственной структурой. Поиск хороших диагностических тестов сводится к построению цепочек двойственных элементов алгебраической структуры. Показывается, что основные операции построения цепочек элементов могут быть интерпретированы как правила правдоподобных рассуждений – генерализация, специализация (уточнение описаний, совмещение значений), диагностика, поиск существенных примеров и существенных значений.

 

 

1. Структура данных и определение хорошего теста

 

В основе алгоритмов поиска хороших диагностических тестов лежит следующая структура данных.

 

Таблица 1. Структура данных

 

S/T	A1	A2	...	Aj	...	Am
1
…
N

 

Здесь S = {1, 2,…, N} – множество индексов примеров, T = {A₁, A₂, …, A_j, …A_m} – множество имён атрибутов (значений атрибутов). Каждый пример есть совокупность значений из множества Т и отображается соответствующей строкой таблицы. При поиске закономерностей в виде функциональных зависимостей между атрибутами примеры будут представлять собой совокупности имён атрибутов, в задачах поиска правил в виде импликативных зависимостей между значениями атрибутов примеры будут представлять собой совокупности значений атрибутов. В нашем подходе поиск этих двух видов зависимостей в данных есть задача поиска хороших диагностических тестов, - ни структура данных, ни алгоритмы не меняются с изменением вида закономерностей. Поэтому далее нам будет удобно называть множество Т множеством значений и примеры рассматривать как совокупности элементов этого множества.

В алгоритмах построения хороших диагностических тестов нами эффективно используются отношение G на S´T и два отображения S®T, T®S. Пусть s Í S, t Í T. Обозначим каждый пример через t_i, i = 1,…, N, t_i Í T, и определим отображения в удобной для описания алгоритмов форме S®T: t(s) = {пересечение всех t_i: t_i Í T, i Î s} и T®S: s(t) = {i: i Î S, t Í t_i}.

Пара введенных нами отображений в математике известна как соответствие Галуа [1-4]. Соответствия Галуа лежат в основе определения концепта и концептуального анализа, Рудольфа Вилле [5]. Соответствия Галуа также используются в системе извлечения знаний CHARADE [6].

Операторы t(s), s(t) обладают следующими свойствами [7]:

 

s₁ Í s₂ Þ t(s2) Í t(s1) для s₁, s₂ Í S

t₁ Í t₂ Þ s(t2) Í s(t1) для t₁, t₂ Í T

s Í s(t(s)) & t(s) = t(s(t(s))) для s Í S

t Í t(s(t)) & s(t) = s(t(s(t))) для t Í T

t(Ès_j) = Ç t(s_j) для s_j Í S; s(È t_j) = Ç s(t_j) для t_j Í T.

 

Введём два следующих оператора генерализации:

 

generalization_of(t) = t¢ = t(s(t)); generalization_of(s) = s¢ = s(t(s)).

 

Расширение набора s индексом j* ещё одного примера ведет к обобщению примеров и получению более общего признака примеров:

 

(s È j*) Ê s влечёт t(s È j*) Í t(s).

 

Расширение набора t атрибутов (значений атрибутов) ещё одним атрибутом (ещё одним значением) ведет к некоторому уточнению примеров и уменьшению множества примеров:

 

(t È A) Ê t влечёт s(t È A) Í s.

 

При генерализации набора s, то есть последовательности отображений (s È j*) ® t(s È j*) ® s'(t) получим, что t(s È j*) Í t(s), s'(t) Ê (s È j*), то есть s(t(s È j*)) Ê (s È j*). Содержательно этот оператор генерализации определяет все множество примеров, обладающих признаком t(s È j*).

При генерализации набора t, то есть последовательности отображений (t È A) ® s(t È A) ® t'(s), получим, что s(t È A) Í s(t), t'(s) Ê (t È A), t'(s(t È A)) Ê (t È A). Содержательно этот оператор генерализации строит максимальный общий признак для примеров, индексы которых составляют множество s(t È A). При этом может оказаться, что (t È A) не является тестом, а t'(s(t È A)) является тестом для данного класса примеров.

Диагностический тест определяется нами как двойственный объект, то есть тест есть пара (SL,TA), SL Í S, TA Í T, SL = s(TA) и TA = t(SL). Это означает, что задача поиска тестов - двойственная задача. Её нужно формулировать одновременно как в терминах подмножеств множества S, так и в терминах подмножеств множества T.

Пусть задана таблица примеров R, а R(k) и S(k) - множество примеров и множество индексов примеров k-го класса соответственно, FM = R\R(k) - примеры, принадлежащие классам, отличным от k-ого. Далее будем считать, что Т есть множество значений, каждое из которых появляется хотя бы в одном примере таблицы R. Дадим определение диагностического теста для примеров класса k.

Определение 1. Совокупность значений t, t Í T, s(t) ¹ Æ является диагностическим тестом для множества R(k) примеров класса k, если и только если выполняется условие, что t Ë t*, "t*, t* Î FM или (эквивалентное условие) s(t) Í S(k).

Дадим теперь определение хорошего диагностического теста:

Определение 2. Совокупность значений t, t Í T является хорошим диагностическим тестом для множества R(k) примеров класса k, если и только если выполняется условие, что s(t) Í S(k) и одновременно не существует такого набора значений t*, t* Í T для которого удовлетворяется условие s(t ) Í s(t*) Í S(k).

Определение 3. Пусть S = {s₁, ..., s_m} семейство подмножеств множества NT. S является системой Спернера (Sperner system) [8], если оно удовлетворяет следующим отношениям:

 

1. s_i Í NT for i = 1, ..., m,
2. s_i Ë s_j и s_j Ë s_i для всех i, j, i ¹ j, i, j = 1, ..., m.

 

Найти все хорошие максимальные тесты (ХМТ) для класса k значит построить такое семейство подмножеств s₁, s₂,…, s_n множества S, что

1) s_j Í S(k), "j = 1,...,n;

2) подмножества семейства попарно не вложимы друг в друга, то есть образуют семейство Спернера;

3) каждое s_j – максимальное множество в том смысле, что прибавление к нему любого индекса i примера t_i, такого, что i Ï s_j, i Î S приводит к тому, что (s_j È i) Ë S(k) (иными словами, t(s È i) не является тестом для примеров класса k, то есть найдётся такой пример t*, t*Î FM, что t Í t*).

Пусть Т - набор значений. Найти все ХМТ для примеров класса k означает найти семейство подмножеств t₁, t₂,..., t_n множества Т, такое, что

1) t_j Ë t, "t Î FM, "j = 1,...,n, в то же время для всех t_i  s(t_j ) не пустое множество и не существует такого набора индексов s*, что выполняется s(t_j ) Í s* Í s(k);

2) подмножества семейства попарно не вложимы друг в друга, то есть образуют семейство Спернера;

3) каждое t_j - максимальное множество в том смысле, что прибавление к нему любого значения A, такого, что A Ï t_j, A Î T приводит к тому, что s(t_j È A) Ì s(t_j).

Найти все хорошие безизбыточные тесты (ХБТ) для примеров класса k означает найти семейство подмножеств t₁, t₂,..., t_n множества Т, такое, что

1) t_j Ë t, "t Î FM, "j = 1,...,n, в то же время для всех t_i  s(t_j ) не пустое множество и не существует такого набора индексов s*, что выполняется s(t_j ) Í s* Í s(k);

2) подмножества семейства попарно не вложимы друг в друга, то есть образуют семейство Спернера;

3) каждое t_j - минимальное множество в том смысле, что удаление из него любого значения A приводит к тому, что полученный набор значений перестаёт быть тестом для примеров класса k.

 

 

2. Структура двойственных объектов

 

Пусть MUT есть множество всех двойственных объектов, то есть множество всех пар (s, t), s Í S, t Í T, s = s(t) и t = t(s). Это множество частично-упорядочено по отношению £: (s, t) £ (s*, t*) тогда и только тогда, когда s Í s* и t Ê t*.

Можно показать, что множество Y = (MUT, È, Ç) есть алгебраическая решетка, где операции È, Ç определяются следующим образом

(s*, t*) È (s, t) = ((s* È s), (t* Ç t)),

(s*, t*) Ç (s, t) = ((s* Ç s), (t* È t))

для любых пар (s*, t*), (s, t) Î MUT.

 

Единицей и нулём в решетке являются соответственно (S, Æ) и (Æ, T).

Построение диагностических тестов для заданных разбиений множества примеров на классы требует умения найти для любого элемента (s*, t*) Î MUT все ближайшие к нему по отношению £ элементы в решетке, то есть все такие (s, t), что (s*, t*) £ (s, t) и не существует такого элемента (s**, t**), что (s*, t*) £ (s**, t**) £ (s, t), или все такие (s, t), что (s*, t*) ³ (s, t) и не существует такого элемента (s**, t**), что (s*, t*) ³ (s**, t**) ³ (s, t).

В основе образования цепочек упорядоченных по отношению £ элементов решетки Y = (MUT, È, Ç), обладающих требуемыми свойствами, лежит построение упорядоченных по отношению включения цепочек вида:

 

1) s₀ Í … Í s_i Í s_i+1 Í …Í s_m (t₀ Ê t₁  Ê … Ê t_i Ê t_i+1 Ê … Ê t_m)

2) t₀ Í … Í t_i Í t_i+1 Í …Í t_m (s₀ Ê s₁  Ê … Ê s_i  Ê s_i+1 Ê …Ê s_m).

 

Процесс образования цепочек вида 1 будем называть восходящим процессом порождения элементов решетки. Процесс образования цепочек вида 2 будем называть нисходящим процессом порождения элементов решетки. Будем называть двунаправленным процессом такой процесс образования элементов решетки, в котором попеременно используются цепочки 1) или 2).

Если ведущим процессом образования тестов является цепочка элементов 1, то каждому элементу s_i цепочки будет соответствовать элемент t(s_i), являющийся тестом для класса k, вплоть до последнего элемента цепочки s_m, которому соответствует ХМТ t(s_m) и любому расширению которого s_m+1 соответствует элемент t(s_m+1), не являющийся тестом для класса k:

 

3) s₀ Í s₁ Í … Í s_i Í s_i+1 Í …Í s_m

4) t(s₀) Ê t(s₁) Ê … Ê t(s_i)  Ê t(s_i+1)Ê …Ê t(s_m).

 

Если ведущим процессом образования тестов является цепочка элементов 2, то каждому элементу t_i цепочки будет соответствовать элемент s(t_i):

 

5) t₀ Í t₁ Í … Í t_i Í t_i+1 Í …Í t_m

6) s(t₀) Ê s(t₁) Ê … Ê s(t_i)  Ê s(t_i+1)Ê …Ê s(t_m).

 

При этом элементы t_i  соответствуют не тестам вплоть до получения последнего элемента t_m, являющегося либо максимальным, либо безизбыточным (минимальным) хорошим тестом для класса k (что определяется алгоритмом построения тестов).

Ведущими процессами при образовании тестов могут быть также нисходящий s₀ Ê … Ê s_i   Ê s_i+1 Ê …Ê s_m и восходящий t₀ Ê … Ê t_i Ê t_i+1 Ê … Ê t_m процессы порождения элементов решётки с соответствующими им цепочками элементов t(s₀) Í … Í t(s_i) Í t(s_i+1) Í …Í t(s_m) и s(t₀) Í … Í s(t_i) Í s(t_i+1) Í …Í s(t_m) соответственно.

При построении всех ХМТ(ХБТ) необходимо для элемента некоторой цепочки уметь находить все его возможные непосредственно следующие (непосредственно предшествующие) по отношению включения элементы, обладающие требуемыми в алгоритме свойствами.

 

 

3. Операции построения цепочек двойственных элементов

 

Рассмотрим следующие операции.

1. Операция расширения набора s_i, такого, что t(s_i) является тестом для рассматриваемого класса примеров, с получением всех его наднаборов s_i+1 мощности на единицу большей, чем мощность набора s_i. Эта операция используется для нахождения максимальных хороших тестов, поэтому нам необходимо выполнить необходимое (хотя и не достаточное) условие того, чтобы вновь полученный набора s_i+1соответствовал тесту для рассматриваемого класса примеров: все поднаборы набора s_i+1 должны соответствовать тестам для рассматриваемого класса примеров. Кроме того операция расширения не должна повторять уже построенных ранее наборов, образованных при расширении наборов, отличных от s_i, такой же или меньшей мощности.

Содержательно операция расширения набора s означает получение большего по мощности подмножества примеров, обладающего общим признаком, отличающим примеры только одного класса k. Поэтому эту операцию будем называть правилом генерализации или обобщения примеров.

2. Операция расширения набора значений t_i, такого, который не является тестом для рассматриваемого класса примеров, с образованием всех наборов t_i+1, которые были бы тестами для рассматриваемого класса примеров. Содержательно рассмотренная нами операция соответствует диагностическому правилу, позволяющему перейти от признака с очень большой степенью генерализации, присущему примерам разных классов, к признаку, который охватывает примеры только одного какого-нибудь класса. При этом значение, которое используется для расширения первоначального набора - не теста, мы будем называть существенным значением, поэтому диагностическая операция есть также операция поиска существенных значений.

 

 

 

 

 

 

 

 

 

 

 

 

3. Операция сужения набора s_i, для которого t(s_i) не является тестом для рассматриваемой классификации, с образованием его поднаборов s_i-1 на единицу меньшей мощности, для которых t(s_i-1) являются тестами для рассматриваемой классификации.

По аналогии с существенным значением можно ввести понятие существенного примера. Пусть s – некоторый набор индексов примеров, принадлежащих одному и тому же классу заданного разбиения примеров на классы. Пусть также t(s) не является тестом для этого класса примеров. Среди примеров, индексы которых принадлежат s, назовём существенным такой пример, пусть с индексом j*, при удалении индекса которого из набора s отображение t(s\j*) окажется тестом для искомого класса примеров.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Эту операцию назовём операцией поиска существенных примеров.

Рассмотрим реализацию операции 1.

Введем следуюшие обозначения: STGOOD = {s: t(s) есть ХМТ для k}; функция to_be_test(t)::= if (" F')(F' Î FM) t Ë F' then true else false.

Пусть S(test) - частично-упорядоченное по отношению включения множество, содержащее все уже построенные к определённому моменту времени наборы s = {i₁, i₂, ..., i_q}, q = 1,2, ..., ns, удовлетворяющие условию, что t(s) является тестом, где ns - число примеров класса k (число индексов во множестве S(k)).

Построим правило расширения элементов множества S(test), с помощью которого конструируются наборы индексов {i₁, i₂, ..., i_(q+1)} из наборов индексов {i₁, i₂ ..., i_q}, для любого q, q = 1, 2, ..., ns - 1.

Пусть s Î S(test). Образуем множество V = {È s', sÍ s', s'Î {S (test) È STGOOD}}. Это множество есть объединение всех наборов, содержащих s, таким образом, s содержится в пересечении этих наборов. Ясно, что если мы хотим построить новый набор, не содержащийся ни в одном из уже имеющихся наборов, соответствующих тестам, то мы должны использовать для расширения такие индексы, которые не встречаются вместе с набором s во множестве V. Тогда множество индексов - кандидатов для расширения s есть множество L = not(s) \V, где not(s) = ns\s.

Индекс j*ÎL можно использовать для расширения s, если для любого i из s пара {i, j*} соответствует тесту, но тогда s должно содержаться в объединении всех наборов, которые содержат j*, за исключением только наборов из 2-х элементов, соответствующих хорошим тестам (эти двойки не имеют расширений). Таким образом, должно выполнятся условие: {Q(j*) содержит s}, где Q(j*) ={Ès': j*Î s', s'Î{S(test)ÈSTGOOD/{j*, j}}}.

Таким образом, множество Select(s) индексов-кандидатов для расширения s: Select(s)={i, iÎL: Q(i) содержит (включает ) s}.

Можно использовать другой способ образования множества Select(s) индексов-кандидатов для расширения наборов s, если запоминать такие двухэлементные наборы s, по мере их образования, для которых to_be_ test(t(s)) = false. Пусть множество ZQ хранит такие двухэлементные запрещённые наборы s. Изменим соответственно множество select(s):

 

select(s) = {i, iÎ L: ("j)(j Î s), {i,j}Ï{STGOOD or ZQ}},

где ZQ = {{i,j}: to_ be_ test (t({i,j})) = false}.

 

Этот способ расширения наборов s порождает и использует правила запрета.

Запрет или частный случай импликации a, b, c ® false (никогда, ложь). Это правило налагает запрет на совместное появление фактов или значений, перечисленных в левой части правила. Правило запрета может быть преобразовано в несколько импликаций a, b ® not c,  a, c ® not b, b, c ® not a.

Рассмотрим диагностическую операцию или операцию нахождения существенных значений.

Пусть s(t_i) = {i_s1, ... i_ss}, и t_s1, ... t_ss  - соответствующие примеры с индексами из s. Ясно, что t_{i =} t(s_i ) содержится в каждом из t_s1, ... t_ss. Обозначим через U все значения, которые встречаются вместе с набором значений t_i в примерах t_s1, ... t_ss. Обозначим все примеры множества FM, содержащие набор значений t_i через G и через UG обозначим все значения, которые встречаются в примерах множества Gвместе с набором значений t_i. Тогда множество существенных значений это те значения, которые принадлежат множеству U, но не принадлежат множеству UG. Таким образом множество существенных значений E = U\UG, и искомые наборы {t_i+1} мы получим следующим образом: {t_i+1: t_i È А, А Î E}. Искомые наборы s_i+1 образуются следующим образом{s_i+1: s(t_i+1)}.

Если множество существенных значений окажется пустым, то надо к рассматриваемому набору t(s_i ) прибавить значения (по одному) из множества U\ t(s_i ) и затем повторить для каждого из полученных расширений поиск существенных значений.

Диагностическая операция позволяет осуществлять индуктивный вывод по примерам диагностических правил.

Диагностические правила: x, d ® a, x, b ® c. Эти правила необходимы, когда доказано существование х и необходимо определить, имеет место a или b. Более строго, диагностические правила подразумевают, что если x, d, то имеет место a, и не может быть никогда c, то есть: x, d, с ® false и аналогично, если имеет место x, b, то имеет место c и не может быть никогда  а, то есть, x, b, а ® false.

Дадим пример рассмотренных операций.

Пример операции генерализации (таблица 2).

Пусть множество STGOOD содержит элемент s₁ = {2,3,5}, соответствующий хорошему максимальному тесту для второго класса. Пусть множество расширяемых наборов S(test) = {{3,4}, {4,6}, {3,5},{2,5},{3,6}}. Расширим набор s = {3,4}. Для расширения возможны индексы примеров 2, 5, 6. Однако только для одного индекса 6 выполняется условие, что объединение всех наборов s из S(test) и STGOOD, содержащих этот индекс, содержит также и будущее расширение {3,4,6}. Этот набор нельзя расширить и он соответствует хорошему тесту – «карий».

 

Таблица 2. Множество примеров с заданным на нём разбиением на классы

 

T	Рост	Цвет волос	Цвет глаз	Класс
1	Низкий	Светлый	Голубой	1
2	Низкий	Коричневый	Голубой	2
3	Высокий	Коричневый	Карий	2
4	Высокий	Светлый	Карий	2
5	Высокий	Коричневый	Голубой	2
6	Низкий	Светлый	Карий	2
7	Высокий	Рыжий	Голубой	1
8	Высокий	Светлый	Голубой	1

Пример диагностической операции (таблица 2).

Пусть имеется набор s = {1,2,5, 7,8}, который соответствует значению «голубой», не являющемуся тестом. Расширим это значение такими значениями, которые встречаются одновременно с ним в примерах первого класса и не встречаются в примерах второго класса и наоборот.

Тогда для первого класса имеем множество значений {«низкий», «светлый», «высокий», «рыжий»}, а для второго {«низкий», «коричневый», «высокий»}. Значения «низкий» и «высокий» исключаем из рассмотрения, так как они встречаются в примерах обоих классов. Для первого класса имеем два теста {«голубой», «рыжий»} и {«голубой», «светлый»}, а для второго класса один тест {«голубой», «коричневый»}. Применим операцию генерализации к этим тестам. Им соответствуют наборы индексов {7},{1,8} и {2,5}. Для первого класса наборы нельзя расширить, и потому найденные тесты являются хорошими. Набор {2,5} для второго класса можно расширить с получением набора индексов{2,3,5}, который соответствует хорошему тесту из одного значения – «коричневый».

Проиллюстрируем также как удаление существенного примера приводит к получению диагностического теста для заданного класса примеров. Рассмотрим множество (1,7,8) индексов примеров 1-ого класса (Таблица 2). Пересечение примеров 1,7,8, равное набору значений «голубой», не является тестом для 1-ого класса. Удаление из рассмотрения примера 7 приводит к тому, что пересечение оставшихся примеров 1, 8, равное набору значений «светлый», «голубой», является тестом для примеров первого класса. Таким образом, пример 7 оказался существенным примером во множестве примеров 1,7,8.

Как при добавлении существенных значений, так и при удалении существенных примеров результат может не дать сразу хорошего теста. Тогда для нахождения хороших тестов необходимо осуществлять основной - восходящий или нисходящий процесс порождения элементов решётки s(t₀) Í … Í s(t_i) Í s(t_i+1) Í …Í s(t_m). В общем случае также можно говорить не о единственном существенном значении (примере), а о подмножестве существенных значений (примеров).

Все возможные способы перехода от одного элемента какой-либо из цепочек 1), 2), 3), 4), 5), 6) к другому соответствуют некоторым правилам рассуждения и определённым способам управления значениями и примерами, без которых не может быть реализовано никакое рассуждение.

Нисходящий процесс порождения цепочек вида t₀ Í t₁ Í … Í t_i Í t_i+1 Í …Í t_m  и соответствующей цепочки s(t₀) Ê s(t₁) Ê … Ê s(t_i)  Ê s(t_i+1)Ê …Ê s(t_m) является двойственным по отношению к уже рассмотренному восходящему процессу построения цепочки вида s₀ Í s₁ Í … Í s_i Í s_i+1 Í …Í s_m ( t(s₀) Ê t(s₁) Ê … Ê t(s_i)  Ê t(s_i+1)Ê …Ê t(s_m)).

Нисходящий процесс используется для построения безизбыточных (минимальных) хороших тестов для заданного класса примеров. Основная операция этого процесса состоит в расширении набора значений t_i  с получением всех его наднаборов t_i+1 на единицу большей мощности. Набор t_i+1 возможно построить, если множество расширяемых наборов -не тестов содержит все его поднаборы на единицу меньшей мощности. Если набор значений t_i+1 оказывается тестом, то это безизбыточный тест, который запоминается в списке тестов, если s(t_i+1) Ë s(t) для "t, tÎ {множество уже построенных минимальных тестов}.

Нисходящий процесс также может использоваться при доопределении в процессе вывода не полностью определённых описаний объектов, ситуаций, таким образом, чтобы эти доопределения были логически непротиворечивы, то есть не содержали внутри себя запрещённых совокупностей значений.

Нисходящий процесс содержательно означает получение описаний классов примеров все более и более подробных, менее генерализованных, до тех пор, пока не будет получено описание (набор значений), которое присуще только примерам заданного класса.

В силу двойственности нисходящего и восходящего процессов, если имеется алгоритм реализации одного из них, то для другого процесса может быть построен алгоритм его реализации двойственным образом.

Мы не рассматривали в этой статье способы декомпозиции алгоритмов поиска хороших тестов на подзадачи и способы сокращения числа образуемых наборов. Рассмотрение этих способов ещё в большей степени сближает процесс вывода всех хороших тестов для заданного класса примеров с естественными правдоподобными рассуждениями.

 

 

Литература

 

1.Оре О. Теория графов. М.: Наука, 1980. С. 325.

2. Everett, J. Closure Operators and Galois Theory in Lattices. // Trans. Amer. Math. Soc. 1944. Vol. 55, No 1. P. 514-525.
3. Ore, O. Galois Connexions. // Trans. Amer. Math. Soc. 1944. Vol. 55, No 1. P. 493-513.
4. J. Riguet. Relations binaires, fermetures, correspondences de Galois. // Bull. Soc. Math. France. 1948. Vol. 76, No 3. P. 114-155.
5. Wille R. Restructuring Lattice Theory: an Approach Based on Hierarchies of Concept // Ordered Sets. Dordrecht-Boston: Reidel, 1982. P. 37-91.
6. Ganascia, J.-G. L’àme – machine. Les enjeux de l’intelligence artificielle. Paris: Editions du Seuil, 1990. P. 280.
7. Биркгоф Г. Теория структур. М.: ИЛ, 1954. С. 532.
8. Sperner E. Eine satz uber untermengen einer endlichen menge // Mat. Z. 1928. Vol. 27, No 11. P. 3-54.

 

 

 

Computational model for generating good classification test construction as a model of commonsense reasoning

Xenia Alexandrovna Naidenova

 

 

Key words: classification, diagnostics, commonsense reasoning, inductive inference of rules from examples, algebraic lattice, cognitive modeling

 

The definition of good diagnostic test is given as an element of algebraic lattice with dual structure. Inferring good diagnostic tests is reduced to constructing chains of dual elements of lattice. It is shown that the main operations of generating lattice elements can be interpreted as the rules of commonsense reasoning (generalization, specification, diagnostics, searching essential values and essential examples).