Решение логических задач распознавания

 

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

Пусть множество объектов подразделено на классы Ω₁ ..., Ω_m, а для описания объектов используются признаки А₁ ..., А_n.

Предположим, что все сведения априорного характера о классах объектов, выражающие, с одной стороны, связь между высказываниями Ω₁, ..., Ω_m и А₁, ..., А_n, с другой стороны, зависимости только между признаками А₁, ..., А_n или только между классами Ω₁, ..., Ω_m, представлены в форме булевых соотношений:

 

(6.31)

 

Предположим также, что наряду с (6.31) в результате проведения экспериментов установлены некоторые данные, касающиеся части признаков А_х1 ..., А_n, присущих объектам классов Ω₁, ..., Ω_m, и что эти данные выражены как булева функция G(A₁ ...,А_n)=1.

Прямая задача распознавания состоит в том, чтобы определить, какие выводы можно сделать относительно классов Ω₁, ..., Ω_m на основе общих сведений априорного характера (6.31) и апостериорной информации G(A₁..., А_n), т. е. требуется определить неизвестную функцию F(Ω₁, ..., Ω_m), удовлетворяющую уравнению

 

 

(6.32)

 

при ограничениях (6.31).

Задача, сопряженная с данной, заключается в том, чтобы установить, какие совокупности признаков А₁ ..., А_n должны иметь место, если известны некоторые сведения о классах (Ω₁, ..., Ω_m, т. е. требуется определить неизвестную функцию G₁(A₁, ..., А_n), удовлетворяющую уравнению

 

(6.33)

 

при заданной функции F₁ (Ω₁, ..., Ω_m) и связях (6.31).

Положим, в соотношениях (6.32) и (6.33) F(Ω₁, ..., Ω_m) =F₁(Ω₁, ..., Ω_m). Тогда, если G₁(A₁ ..., A_n)=G(A₁ ..., А_n), перемножив левые части (6.32) и (6.33), получим G×F+`G×`F=l или

 

(6.34)

 

иначе говоря, посылки G(A₁ ..., А_n) [или F₁ (Ω₁, ..., Ω_m)] и следствия F(Ω₁, ..., Ω_m) [или G₁(А₁, ..., А_n)] эквивалентны.

Другая задача — обратная задача распознавания — заключается в том, чтобы определить множество априори неизвестных посылок G(A₁ ..., А_n), из которых следуют некоторые данные выводы F((Ω₁, ..., Ω_m) при условии, что признаки А₁, ..., А_n и классы (Ω₁, ..., Ω_m связаны зависимостями (6.31).

Покажем, что решение этой задачи приводится к решению предыдущей задачи. Пусть F(Ω₁, ..., Ω_m) есть заданная функция, имшшканты которой требуется найти в виде функции G(A₁ ..., А_n). Перейдем от функции F(Ω₁, ..., Ω_m) к ее отрицанию F₁ =`F(Ω<sub>1</sub>, ..., Ω<sub>m</sub>) и с помощью (6.33) определим функцию G<sub>1</sub>(A<sub>1</sub> ..., А<sub>n</sub>), связанную с `F((Ω₁, ..., Ω_m) зависимостью `F(Ω₁, ..., Ω_m)®G₁(A₁ ..., А_n). Так как эта зависимость эквивалентна соотношению

 

(6.35)

 

то G(A₁ ..., A_n) = `G₁(A₁ ..., А_n) и является искомой функцией.

Если наряду с (6.35) справедливо соотношение F((Ω₁, ..., Ω_m®-G(A₁ ..., А_n), то F(Ω₁, ..., Ω_m) = G(A₁ ..., А_n), т. е. G(A₁ ..., А_n) представляет собой полный набор импликант функции F(Ω₁, ..., Ω_m), через сумму которых эта функция может быть выражена.

Методы решения прямой и обратной задач распознавания основываются на построении сокращенного базиса b_с[А₁ ..., А_n(Ω₁, ..., Ω_m], определяемого следующим образом. Соотношения (6.31) накладывают определенные ограничения на возможные комбинации значений истинности элементов А_и ..., А„; Q_b ..., Q_m, так что не все столбцы полного базиса b[А₁, ..., А_n; (Ω₁, ..., Ω_m] совместны с этими соотношениями. Если отбросить столбцы базиса b[А₁... А_n; (Ω₁, ..., Ω_m], противоречащие хотя бы одному из соотношений (6.31), то оставшиеся столбцы, по определению, образуют сокращенный в соответствии с данными связями базис. Сокращенный базис устанавливает соответствие между колонками базиса b_с[А₁ ..., А_n] и базиса b_c[(Ω₁, ..., Ω_m] и определяет тем самым возможные преобразования соотношений (6.31) к такому виду, для которого рассматриваемые задачи решаются либо в рамках уравнений (6.32) или (6.35), либо (6.34).

Рассмотрим конкретный пример.

Предположим, что при некоторых условиях, характеризуемых признаками А₁ А₂, А₃, в системе могут протекать процессы Ω_1, Ω₂, Ω₃, причем связи между Ω_1, Ω₂, Ω₃ и А₁ А₂ А₃ представлены соотношениями

 

(6.36)

 

Изображающие числа булевых функций, представленных соотношениями (6.36), относительно базиса b[А₁ А₂, А₃; Ω_1, Ω₂, Ω₃] соответственно равны 0101 0000 0000 0101 1010 0000 0000 1010 0101 0000 0000 0101 1010 0000 0000 1010 и 1001 1100 1001 1100 1001 1100 1001 1100 0110 0011 0110 0011 0110 0011 0110 0011.

Перемножив эти два изображающих числа, получим 0001 0000 0000 0100 1000 0000 0000 1000 0100 0000 0000 0001 0010 0000 0000 0010. Следовательно, соотношения (6.36) удовлетворяются только при таких комбинациях значений истинности элементов А_1, А₂, А₃, Ω_1, Ω₂, Ω₃, которые соответствуют 3, 13, 16, 28, 33, 47, 50 и 62-му столбцам базиса b[А₁ А₂, А₃; Ω_1, Ω₂, Ω₃]. Сохраняя перечисленные колонки и отбрасывая остальные, получим следующий сокращенный базис:

 

(6.37)

 

Разобьем базис (6.37) на два базиса: b_с[А₁ А₂, А₃] и b_c[Ω_1, Ω₂, Ω₃]. Тогда сокращенный базис b_c[Ω_1, Ω₂, Ω₃] будет совпадать с полным стандартным базисом b[Ω_1, Ω₂, Ω₃ ] и b_с[А₁ А₂, А₃] будет представлять собой полный нестандартный базис для элементов А₁, А₂, А₃. Пусть i и j обозначают порядковые номера столбцов стандартных базисов b[Ω_1, Ω₂, Ω₃ ] и b[А_1, А₂, А₃], соответственно.

Базис (6.37) устанавливает следующее взаимно однозначное соответствие между значениями i и j:

 

(6.38)

 

или при другом порядке расположения чисел:

 

(6.39)

 

Из (6.38) следует, что изображающие числа #A_l, #А₂ и #А₃ относительно базиса b[Ω_1, Ω₂, Ω₃] запишутся как

 

(6.40)

 

а перестановочная матрица ||R_ij|| будет иметь вид

 

(6.41)

 

Аналогично (6.39) показывает, что в базисе b[А₁ А₂, А₃]

 

(6.42)

 

а матрица ||R_ij|| перехода от переменных Ω_1, Ω₂, Ω₃ к переменным А_1, А₂, А₃ получается как транспонированная по отношению к матрице (6.41). Полученный результат означает, что исходные связи (6.36) полностью эквивалентны либо соотношениям (6.40), либо соотношениям (6.42).

Предположим, что протекающие в рассматриваемой системе процессы проявляют себя через совокупности признаков А₁, А₂, А₃, причем сведения о признаках A_j можно представить в виде булевой функции G(A_1, A₂, А₃), например

 

(6.43)

 

Какие выводы можно сделать относительно процессов Ω_1, Ω₂, Ω₃ на основании информации (6.43) и соотношений (6.36)? По (6.26)

 

 

и, следовательно,

 

(6.44)

 

т. е. либо протекает только один процесс Ω₃, либо можно утверждать, что процесс Ω₁ протекает, а относительно процессов Ω₂ и Ω₃ ничего сказать нельзя, либо, наконец, имеет место Ω_1, Ω₂, Ω₃. При таком не очень определенном выводе может потребоваться узнать, какие признаки из числа признаков А_1, А₂, А₃ должны быть обнаружены дополнительно, чтобы убедиться, что в системе протекает только процесс Ω₁ т. е. F(Ω_1, Ω₂, Ω₃) = Ω_1,×`Ω<sub>2</sub>,×`Ω₃. В соответствии с (6.22)

 

 

откуда

 

(6.45)

 

т. е. в группе наблюдений, где было установлено A₁×`A₂ требуется дополнительно обнаружить наличие признака A₃. утверждения (6.44) и (6.45) имеют смысл необходимых и достаточных условий, когда посылки и следствия полностью эквивалентны.

 

Глава 7 ЛОГИЧЕСКИЕ СИСТЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ

 

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

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