Обробка числової і символьної інформації на основі розподілених представлень в задачах штучного інтелекту.

РАЗДЕЛ 2
РАЗРАБОТКА МЕТОДОВ ПОИСКА, ОТОБРАЖЕНИЯ И ВЫВОДА ПО АНАЛОГИИ НА ОСНОВЕ
РАСПРЕДЕЛЕННЫХ ПРЕДСТАВЛЕНИЙ
В данном разделе рассматриваются методы формирования бинарных распределенных
представлений отношений и сложно структурированной реляционной информации,
которая используется для представления знаний в базах знаний и применяется в
качестве аналогов в рассуждениях по аналогии. На основе распределенных
представлений разработаны методы поиска, отображения и вывода по аналогии.
Свойства разработанных представлений и методы исследованы как аналитически, так
и экспериментально на базах знаний.
Формирование представлений отношений
Для формирования бинарных распределенных представлений отношений используем
метод «роль-заполнитель» (см. п. 1.1.3), где отношению
R(O1, O2, ...) соответствует бинарный вектор
бR­1 Ъ O1с Ъ бR­2 Ъ O2с Ъ … Ъ бR­n Ъ Onс,
(2.34)
где R­1,…,R­n – векторы представления ролей; O1,…,On – векторы представления
объектов (заполнителей ролей).
Основные свойства этого метода, в частности, вопросы сохранения сходства
структур в виде сходства соответствующих бинарных представлений, рассмотрены в
работе [69]. В данном подразделе исследуется вопрос различимости векторных
представлений для различных структур, что является крайне важным при поиске
ближайших аналогов.
Пример формирования бинарных представлений для абстрактного отношения R,
объектов O­1 и O2 для высказываний R(O­1, O2) и R(O­2, O1), приведенный на рис.
2.1, иллюстрирует процесс формирования структурно зависимых векторных
представлений высказываний. Под высказыванием подразумевается реализация
отношения R для конкретных параметров. Черными точками показаны единичные
элементы, а белыми – единичные элементы вектора дизъюнкции вектора роли и
вектора объекта, удаленные в результате применения процедуры
контекстно-зависимого прореживания. В процессе формирования вектора
высказывания выполняется связывание векторов объектов O­1 и O­2 с векторами их
ролей, в результате формируются бинарные векторы соответствующие их ролям –
R­1(O­1) и R­2(O­2). Связывание выполняется процедурой контекстно-зависимого
прореживания (см. п. 1.1.2). Объекты и роли представлены бинарными многомерными
(N=50) разреженными (M=10) псевдослучайными векторами.
Рис. 2.7. Иллюстрация процесса формирования бинарных представлений отношений
R(O1, O2) и R(O2, O1) методом «роль-заполнитель»
Векторы отношений R(O­1, O2) и R(O­2, O1) имеют достаточно большое количество
общих единиц, благодаря чему сохраняется сходство отношений со сходными
объектами. Однако при этом множества единиц различны, что позволяет судить о
различиях в структуре отношений.
Оценим вероятность совпадения векторных представлений отношений R(O1, O2) и
R(O2, O1), полученных методом (2.1). Совпадение векторов этих отношений будет
означать, что бR1 Ъ O1с Ъ бR2 Ъ O2с є бR1 Ъ O2с Ъ бR2 Ъ O1с, где R1, R2 –
векторы ролей, а O1, O2 – векторы объектов. Эта вероятность меньше вероятности
равенства скалярного произведения векторов R1,2 и R2,1, соответствующих R(O1,
O2) и R(O2, O1), и скалярного произведения вектора R1,2 с самим собой.
Рассмотрим вектор перекрытия R1,2 и R2,1:
R1,2 Щ R2,1 = (бR1 Ъ O1с Ъ бR2 Ъ O2с) Щ (бR1 Ъ O2с Ъ бR2 Ъ O1с) =
= ([R1 Ъ O1][R1,k Ъ O1,k] Ъ [R2 Ъ O2][R2,k Ъ O2,k]) Щ
Щ ([R1 Ъ O2][R1,k Ъ O2,k] Ъ [R2 Ъ O1][R2,k Ъ O1,k]) =
= R1R1,k Ъ R2R2,k Ъ O1O1,k Ъ O2O2,k Ъ
Ъ R1O1,k(R2 Ъ O2,k) Ъ R2O2,k(R1 Ъ O1,k) Ъ
Ъ O1R1,k(R2,k Ъ O2) Ъ O2R2,k(R1,k Ъ O1),
(2.35)
где Ri,k = Ъk Rik, Oj,k = Ъk Ojk получены из Ъk[Ri Ъ Oj]k, где [Ri Ъ Oj]k – k-я
перестановка дизъюнкции Ri Ъ Oj (см. (1.4)), отсутствие знака между векторами
надо интерпретировать как Щ.
Заметим, что при вычислении математического ожидания скалярного произведения по
формуле (2.2) членами третьего порядка ДНФ (2.2) O1O2(R1,k Ъ R2,k) Ъ R1R2(O1,k
Ъ O2,k) Ъ (O1 Ъ O2) R1,kR2,k Ъ (R1 Ъ R2) O1,kO2,k можно пренебречь. Для малых
плотностей векторов объектов pO = 0,01 и векторов отношений pR = 0,02 вклад в
скалярное произведение максимального из них (O1 Ъ O2) R1,kR2,k не превышает
2ґ10-4.
Вектор R(O1, O2) получается следующим образом:
R1,2 = бR1 Ъ O1с Ъ бR2 Ъ O2с = R1R1,k Ъ R2R2,k Ъ O1O1,k Ъ O2O2,k
Ъ R1O1,k Ъ R2O2,k Ъ O1R1,kЪ O2R2,k.
(2.36)
Предполагая независимость всех векторов, (2.2) и (2.3) вычисляются как
R1,2 Щ R2,1 = R11 R1,k1 Ъ R21R2,k1 Ъ O11O1,k1 Ъ O21O2,k1 Ъ R12O1,k2(R22 Ъ
O2,k2) Ъ R23O2,k3(R13 Ъ O1,k3) Ъ O12R1,k2(R2,k2 Ъ O22) Ъ O23R2,k3(R1,k3 Ъ
O13);
R1,2 = R11R1,k1 Ъ R21R2,k1 Ъ O11O1,k1 Ъ O21O2,k1 Ъ R12O1,k2 Ъ R22O2,k2 Ъ
O1R1,k2Ъ O2R2,k2,
(2.37)
где Rih, Ri,kh, OjhOj,kh ­ – независимые случайные векторы.
Это предположение увеличит вероятность появления единицы в векторе R1,2 Щ R2,1:
поскольку для зависимых величин c положительной корреляцией P(a, b) > P(a)P(b),
то, положив P(a, b) = P(a)P(b), мы только увеличим
P(a Ъ b) = P(a) + P(b) - P(a, b). Векторные представления высказываний
различаются по значению скалярного произведения, т.е. высказывания различимы,
если (R1,2, R2,1) < (R1,2, R1,2). Обозначим вероятность того, что i-й элемент
вектора R1,2 равен 1 как P(R1,2). P(R1,2, R2,1) будет соответствовать
вероятности того, что i-е элементы векторов R1,2 и R2,1 одновременно равны 1,
т.е. вероятности 1 в векторе перекрытия. Соответственно, вероятность совпадения
единичных элементов векторов R1,2 Щ R2,1 и R1,2, следствием чего является
совпадение (R1,2, R2,1) и |R1,2|, равна
pсовпадения = Si=0,NСNi P(R1,2)i(1– P(R1,2))N-i P(R2,1 | R1,2)i =
= (1 – P(R1,2) + P(R1,2, R2,1))N.
(2.38)
В экспериментальном исследовании соответствующие вероятности P(R1,2, R2,1) и
P(R1,2) вычислялись алгоритмически по формулам (1.1): P(xX Ъ xY) = P(xX)