science-review.ru
В связи с глобальной информатизацией общества информация (хотя этот термин и не имеет четкого определения) ныне обладает собственной ценностью, иногда существенно превышающей ценность материальных объектов. Быстрый релевантный поиск дает возможность не только приобретать новые знания, но и обогащаться материально. Поэтому поисковые системы (поисковики) информации в интернете представлены в изобилии [1, 2]. Как правило, в них используется разновидность поиска по ключевым словам, что связано с недостаточной развитостью в настоящее время семантического анализа и автоматического логического вывода, позволяющих получать следствия из полученных данных. Последний механизм может как сократить множество выдаваемых статей, полученных только по ключевым словам, так и ускорить поиск необходимой информации.
Основная сложность поиска необходимой информации в большом объеме данных состоит в том, что, как правило, при поиске определенного объекта имеется еще большая совокупность объектов, которые отличаются от искомого «немного», «чуть-чуть», «самую малость» и пр. Поэтому с содержательной точки зрения они отличаются мало, и человеку с его образным мышлением трудно подобрать существенные признаки, выделяющие нужный ему объект. В таком случае должна существовать подсказывающая система, указывающая те признаки, которые в данной предметной области представляются наиболее существенными. Тем самым человеку предоставляется возможность не вспоминать необходимый признак, что сопряжено с определенными ресурсными затратами, а выбирать из представленного набора. Однако такая система подсказок предполагает значительную проработку предметной области, так как иначе подсказки будут носить нерелевантный характер.
Основными типами запросов на поиск информации служат запрос на нахождение конкретного объекта, существование которого не вызывает сомнения, и объекта, обладающего определенными свойствами, наличие которого в информационной системе под вопросом. Например, такими объектами могут быть вычислительное устройство определенной конструкции, для которого указываются его конструктивные особенности, или авторского свидетельства на интересующую тему, в котором дается описание устройства с неточно заданными параметрами. Если в первом случае имеется гарантия, что такое устройство имеется и при достаточном терпении мы его найдем, то вторая ситуация характеризуется неопределенностью, устройство может не присутствовать в информационной системе. В качестве примера также можно упомянуть построение объекта, обладающего определенными свойствами, когда известно, какие составные элементы привносят то или иное свойство. Вопросам семантики посвящено очень много работ, с основополагающими идеями можно ознакомиться в [3, 4].
В этой работе предпринята попытка, используя оригинальный формализм, построить теорию вопросно-ответных систем, которая базируется на семантике предметной области. Эта семантика выражается в терминах совместимости / несовместимости, что представляется достаточно универсальным механизмом для описания предметных областей и построения систем поиска информации по семантическим признакам. В настоящей работе не затрагиваются вопросы нечеткого описания объектов, которые подразумевают градации присутствия признаков наподобие: присутствует всегда, присутствует иногда, встречается редко и т.п. Этот вопрос будет поднят в следующих публикациях.
Содержательное описание предметной области
Под предметной областью будем понимать пару OR = (Elements, Objects), где Elements есть конечное множество базисных элементов, а Objects – совокупность объектов, которые суть подмножества множества базисных элементов, т.е. Objects ⊆ 2Elements. Один базисный элемент может входить в несколько объектов в качестве составной части. Если два базисных элемента одновременно не принадлежат никакому объекту, то они называются несовместимыми, в противном случае – совместимыми. Содержательно несовместимость базисных элементов может интерпретироваться по-разному: это может быть несовместимость двух признаков при описании понятий, двух химических элементов при попытке создать новое соединение или двух разных команд в одном управляющем устройстве и т.п. Например, две команды ускорение и торможение, выполняемые одновременно, несовместимы. Два химических элемента, вступающие в реакцию, несовместимы при попытке создать устойчивое соединение, в которое они входят. Два признака молока – кислое и парное – также несовместимые. Два пользователя распределенной информационной системы несовместимы, если они не имеют доступа к одинаковой информации. Более подробно семантика предметной области, основанная на несовместимости, описана в [5].
Тем самым на множестве Elements задано бинарное коммутативное отношение Ort ⊆ Elements×Elements – описывающее отношение несовместимости.
Базисные элементы можно представлять обладающими определенными значениями ряда элементарных признаков. Признаки суть элементы конечного алфавита, значения каждого признака также принадлежат конечному множеству. Поэтому базисный элемент можно мыслить как вектор, каждый компонент которого указывает на наличие / отсутствие определенного признака. Тем самым признак однозначно соответствует компоненту вектора, разным компонентам соответствуют разные признаки и наоборот. Значения признаков, в свою очередь, бывают совместимыми и несовместимыми. Разные значения одного признака – несовместимы, они не встречаются в описании одного элемента. Это вполне естественно, так как в предметной области желательно максимально разделять базисные элементы, используя один признак. Предполагаем, что признаки, участвующие в описании базисных элементов, независимые, поэтому значения разных признаков совместимые.
В данном случае используется некоторая условность, так как несовместимые значения признаков при описании одной предметной области могут быть совместными при описании другой предметной области. Но такая условность оправдана тем, что мы априорно фиксируем последнюю. Таким образом, исследование предметной области сводится к изучению базисных элементов, с определенным на них отношением совместимости / несовместимости.
Построим по множеству Elements и отношению Ort граф GOrt несовместимости: его узлы суть элементы множества Elements, и два узла b1, b2 смежные тогда и только тогда, когда выполняется отношение Ort(b1, b2). Мы несколько усилим понятие объектов ПО: множество Objects – совокупность объектов, которые суть максимальные подмножества базисных элементов, то есть к условию Objects ⊆ 2Elements добавляется требование, чтобы каждый объект нельзя было расширить за счет добавления какого-либо элемента из Elements. Такое усиление объяснимо с содержательной точки зрения, если подмножество множества Elements расширяется, то такой объект можно считать лишь промежуточным, не несущей всей информацией. С другой стороны, совокупность максимальных подмножеств является полной характеристикой предметной области в терминах отношения несовместимости.
Введенное определение предметной области будем называть содержательным, так как отношение несовместимости может носить неформальный характер и определяться, исходя из содержательных соображений. Сейчас мы не рассматриваем разновидности определения понятия несовместимости. Так несовместимость может быть: всегда, в большинстве случаев, как правило, иногда, редко и т.п. Мы вводим предикат Ort, чтобы сделать изложение достаточно прозрачным.
Нетрудно увидеть, что каждому объекту B ∈ Objects в графе GOrt соответствует максимальный пустой подграф GB и наоборот, каждому максимальному пустому подграфу графа GOrt соответствует единственный объект из Objects. Таким образом, мы можем говорить не об объектах предметной области, а о пустых подграфах графа GOrt.
Логическая семантика предметной области
Введем понятие логической матрицы, строки которых соответствуют переменным, а столбцы – дизъюнктам или конъюнктам в зависимости от того, представляет матрица КНФ или ДНФ логической функции. Элементы логической матрицы суть 0, 1, _ (обозначая соответственно отрицательную литеру, положительную или отсутствие ее). Поэтому каждый столбец матрицы с n строками можно рассматривать как интервал в единичном n-мерном кубе En, а произвольная совокупность M* столбцов определяет интервал I* ⊆ En, который есть пересечение интервалов, определяемых этой совокупностью. Будем называть этот интервал I* определяемым подматрицей M*. Это пересечение может быть как пустым, так и не пустым, что определяется видом M*.
В [5] показано, что по графу GOrt строится логическая матрица с n строками и m столбцами, где m = |Elements|, и столбцы которой помечены разными элементами множества Elements, которая обладает следующими свойствами.
1. Два разных столбца b1 и b2 помечены интервалами σ1 и σ2 единичного n-мерного куба, пересечение которых σ1 ∩ σ2 пусто тогда и только тогда, когда Ort(b1, b2). Будем называть такие столбцы матрицы – ортогональными.
2. Каждый пустой подграф G0 ⊆ GOrt, G0 = {b1, b2, …, bq} определяет подматрицу M(b1, b2, …, bq) такую, что определяемый ею интервал n-мерного единичного куба не пуст. Для непустых графов определяемые ими интервалы пусты.
Отметим, что при разных способах построения матрицы по графу GOrt количество строк может варьироваться, тем самым по-разному определяются интервалы единичного куба, соответствующие столбцам матрицы.
Получаем, что семантика несовместимости элементов предметной области формально описывается в логических терминах, и отношению несовместимости однозначно соответствует отношение ортогональности столбцов матрицы или пустоты пересечения интервалов.
Фильтрация столбцов логической матрицы
Введем операцию умножения × векторов одинаковой длины в базисе 0, 1, _.
1. Значения 0 и 1 назовем ортогональными.
2. Если векторы в одном компоненте содержат ортогональные элементы (т.е. векторы ортогональные), то их произведение пусто.
3. В противном случае осуществляется покомпонентное умножение, на основе следующих базисных операций: 1×1 = 1×_ = _×1 = 1, 0×0 = 0×_ = _×0 = 0, _×_.
Так как векторы в базисе 0, 1, _ определяют интервалы единичного куба, то очевидно, что операция умножения векторов однозначно определяет пересечение соответствующих интервалов.
Пусть M есть логическая матрица с n строками и m столбцами, столбцы поименованы b1, b2, …., bm, и каждый из них определяет интервал I(b1), I(b2), …., I(bm) единичного n-мерного куба En. Введем операцию фильтрация матрицы M произвольным вектором b длины n. Ее результатом Ф(M, b) является матрица, которая получается из M заменой каждого ее столбца bi на произведение b×bi, i = 1, 2, …, m. Пустые произведения в результирующую матрицу Ф(M, b) не включаются. Легко обобщить операцию фильтрации на множество b = {b1. b2, …, bq} фильтрующих векторов: Ф(M, b) = Ф(…Ф(Ф(M, b1), b2, …, bq).
Построение объекта предметной области по заданным характеристикам
Пусть из информационной системы надо выделить объект, обладающий заданными характеристиками, причем практически невозможно перечислить в точности все его свойства в силу того, что они составляют представительное множество и не всегда можно указать их все сразу. Однако в процессе уточнения в диалоге с вопросно-ответной системой такая задача вполне решаема и в конечном итоге удается получить искомый объект. Для определенности будем считать, что на начальном этапе имеется перечисление некоторого подмножества свойств, которые позволяют выделять подмножество объектов, обладающих этими свойствами, и задача вопросно-ответной системы состоит в том, чтобы подсказать, какие еще свойства необходимо указать, чтобы получить искомый ответ.
Сформулируем задачу в терминах предметной области, для которой задано отношение Ort на множестве элементов. Содержательно ее элементами могут трактоваться как конкретные сущности, так и признаки, позволяющие однозначно идентифицировать искомый объект. Тем самым для элементов предметной области задана содержательная семантика. Рассматриваемая предметная область характеризуется графом совместимости GOrt, по которому в соответствии с описанной выше процедурой строится логическая матрица M. Теперь задача поиска искомого объекта состоит в построении максимального пустого подграфа, узлы которого суть элементы предметной области, имеющие содержательную интерпретацию и удовлетворяющие содержательным критериям принадлежности искомому объекту.
Полагаем, что исходно пользователь знает некоторые свойства искомого объекта. Пусть им соответствуют элементы из Elements, образующие множество b = {b1, b2, …, bq}, в соответствии с которым вычисляется матрица Ф(M, b). В графе GOrt элементы b1, b2, …, bq выделяют пустой подграф, в общем случае он не максимальный, так как искомый объект еще не построен, и может расширяться разными способами. Однако, такое расширение происходит только за счет элементов, которым соответствуют столбцы матрицы Ф(M, b).
Поэтому задача поиска состоит в том, чтобы путем поставленных вопросно-ответной системой вопросов построить максимальный пустой подграф, который и описывает искомый объект. То есть обладает содержательными характеристиками, соответствующими элементам предметной области, которые суть узлы пустого графа. Поэтому диалог пользователя и вопросно-ответной системы сводится к формулировке последних вопросов, на которые пользователь отвечает ДА/НЕТ. Вопросы касаются включения в описание искомого объекта тех элементов или признаков, которые представлены столбцами в матрице Ф(M, b). Поэтому вопросно-ответная система может задать любой из таких вопросов. Выбор признака, по которому задается вопрос о включении его в искомый объект, может происходить в соответствии с определенной стратегий, однако здесь мы не останавливаемся на ее представлении. Считаем, что априорно все признаки, представленные матрицей Ф(M, b), равноправны и вопрос может касаться любого из них.
Тем самым поиск искомого объекта в заданной предметной области состоит в последовательном включении новых элементов и фильтрации матрицы с учетом вхождения этих элементов в объект.
Построение объекта с определенными свойствами
Рассмотрим еще одну задачу, которая также успешно решается в рамках вопросно-ответной системы, базирующейся на представлении предметной области в виде множества элементов и отношения ортогональности. Пусть имеется несколько свойств, образующих множество S = {S1, S2, …, Sr}, которыми должен обладать конструируемый объект. Каждое свойство Si достигается включением в объект хотя бы одного элемента из определенного множество bi, i = 1, 2, …, r. Как и прежде, обозначим множество всех элементов через Elements, на котором задано отношение несовместимости Ort. Напомним, что пара несовместимых элементов не может входить в один объект, они взаимоисключающие. Соответственно, имеется граф GOrt и соответствующая ему логическая матрица M.
Построим по паре (S, Elements) двудольный граф GSE, одна его доля состоит из свойств S1, S2, …, Sr, а вторая – из элементов множества Elements. Узлы Si и bj смежные в точности в том случае, если bj ∈ Si , i = 1, 2, …, r, j = 1, 2, …, m. Тогда искомый объект будет существовать в случае, если в графе GSE существует двудольный подграф, включающий все узлы множества S и некоторое множество узлов E*, E* ⊆ Elements, обладающих следующим свойством: для каждого i = 1, 2, …, r, пересечение Si ∩ E* не пустое. Тем самым можно констатировать, что искомый объект обладает свойствами S и конструктивно состоит из элементов E*. Описание объекта в виде совокупности E* элементов предполагает, что множество E* выделяет в графе GOrt пустой подграф, узлами которого служат элементы E*.