English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм

Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

Решение проблемы оптимального синтеза информационных графов для базовых задач поиска информации

Гасанов Э.Э.
Кафедра математической теории интеллектуальных систем, механико-математический факультет МГУ им М.В.Ломоносова

 

0. Построена новая общая модель хранения и поиска информации, называемая информационно-графовой, частными случаями которой являются известные базовые примеры такого рода. Изучены основные свойства этой модели и решена проблема оптимального синтеза информационных графов для широкого класса задач поиска, включающего базовые примеры. Более полная версия излагаемых результатов содержится в [1].

1. Пусть $X$ – множество запросов с заданным на нем вероятностным пространством $\langle X,\sigma ,{\bf P}\rangle $, где $\sigma$ – алгебра подмножеств множества $X$, ${\bf P}$ – вероятностная мера на $\sigma$; $Y$ – множество записей (объектов поиска); $\rho$ – бинарное отношение на $X\times Y$, называемое отношением поиска; пятерку $S=\langle X,Y,\rho, \sigma,{\bf P}\rangle$ будем называть типом; тройку $I=\langle X,V,\rho\rangle$, где $V$ – некоторое конечное подмножество множества $Y$, будем называть задачей информационного поиска (ЗИП) типа $S$, и будем считать, что ЗИП $I=\langle X,V,\rho\rangle$ содержательно состоит в перечислении для произвольно взятого запроса $x\in X$ всех тех и только тех записей $y\in V$, таких что $x \rho y $; $O(y,\rho )=\{x\in X:x\rho y\}$; если $I=\langle X,V,\rho\rangle$, то $ R(I) = \sum_{y\in V} {\bf P}(O(y,\rho))$; если $f: X\rightarrow \{0,1\}$, то $N_f =\{x\in X:f(x)=1\}$; $F$ – множество символов одноместных предикатов, определенных на множестве $X$; $G$ – множество символов одноместных переключателей, определенных на множестве $X$, под переключателями будем понимать функции, областью значений которых являются конечные подмножества натурального ряда; пару ${\cal F}=\langle F,G\rangle $ назовем базовым множеством;

Понятие информационного графа (ИГ) над базовым множеством ${\cal F}=\langle F,G\rangle $, определяется следующим образом. Берется конечная многополюсная ориентированная сеть. В ней выбирается некоторый полюс, который называется корнем. Остальные полюса называются листьями и им приписываются записи из $Y$, причем разным листьям могут быть приписаны одинаковые записи. Некоторые вершины сети (в том числе это могут быть и полюса) называются переключательными и им приписываются переключатели из $G$. Ребра, исходящие из каждой из переключательных вершин, нумеруются начиная с 1 и называются переключательными ребрами. Ребра, не являющиеся переключательными, называются предикатными и им приписываются предикаты из множества $F$. Таким образом нагруженную многополюсную ориентированную сеть называем ИГ над базовым множеством ${\cal F}=\langle F,G\rangle $.

Функционирование ИГ определяется следующим образом. Скажем, что: предикатное ребро проводит запрос $x\in X$, если предикат, приписанный этому ребру, принимает значение 1 на запросе $x$; переключательное ребро, которому приписан номер $n$, проводит запрос $x\in X$, если переключатель, приписанный началу этого ребра, принимает значение $n$ на запросе $x$; ориентированная цепочка ребер проводит запрос $x\in X$, если каждое ребро цепочки проводит запрос $x$; запрос $x\in X$ проходит в вершину $\beta$ ИГ, если существует ориентированная цепочка, ведущая из корня в вершину $\beta$, которая проводит запрос $x$; запись $y$, приписанная листу $\alpha$, попадает в ответ ИГ на запрос $x\in X$, если запрос $x$ проходит в лист $\alpha$. Ответом ИГ $U$ на запрос $x$ назовем множество записей, попавших в ответ ИГ на запрос $x$, и обозначим его ${\cal J}_U(x)$. Эту функцию ${\cal J}_U(x)$ будем считать результатом функционирования ИГ $U$.

Пусть нам дана ЗИП $I=\langle X,V,\rho\rangle$. Скажем, что ИГ $U$ разрешает ЗИП $I=\langle X,V,\rho\rangle$, если $ {\cal J}_U(x) = \{ y\in V: x\rho y \}.$

Введем понятие сложности ИГ. Пусть $\beta$ – некоторая вершина ИГ. Предикат, определенный на множестве запросов, который принимает значение 1 на запросе $x$, если запрос проходит в вершину $\beta$, и 0 – в противном случае, назовем функцией фильтра вершины $\beta$ и обозначим $\varphi_\beta(x)$.

Сложностью ИГ $U$ на запросе $x\in X$ назовем число $ T(U,x)= \sum_{\beta \in {\cal P}} \varphi_\beta (x)+ \sum_{\beta \in {\cal R} \setminus {\cal P}} \psi_\beta \cdot \varphi_\beta (x),$ где ${\cal R}$ – множество вершин ИГ $U$, ${\cal P}$ – множество переключательных вершин ИГ $U$, $\psi_\beta$ – количество ребер, исходящих из вершины $\beta$.

Скажем, что базовое множество ${\cal F}$ измеримое, если каждая функция из ${\cal F}$ – измеримая (относительно алгебры $\sigma$). Далее всюду будем предполагать, что базовое множество измеримое. В этом случае для любого ИГ $U$ над ${\cal F}$ функция $T(U,x)$ как функция от $x$ измерима.

Сложностью ИГ $U$ назовем математическое ожидание величины $T(U,x)$, то есть число Сложностью задачи $I$ при базовом множестве ${\cal F}$ назовем число $T(I,{\cal F})=\inf \{T(U):U\in{\cal U}(I,{\cal F}) \},$ где ${\cal U}(I,{\cal F})$ – множество всех ИГ над базовым множеством ${\cal F}$, разрешающих ЗИП $I$.

2. Задача поиска идентичных объектов состоит в поиске в множестве объекта, идентичного объекту-запросу, и формально принадлежит типу $ {S_{id}}=\langle [0,1], [0,1], = ,\sigma,{\bf P} \rangle$. Задачи о близости состоят в поиске в линейно-упорядоченном множестве объекта, ближайшего к объекту-запросу, и принадлежат типу: $ {S_{ne}}=\langle [0,1], [0,1],{\rho_{ne}},\sigma,{\bf P} \rangle,$ где ${\rho_{ne}}$ задается на $[0,1]\times V$ и определяется соотношением $ x{\rho_{ne}}y \Longleftrightarrow (y\in V)\& (x\leq y)\& (\neg (\exists y')((y'\in V)\& (x\leq y')\& (y'< y))).$ Справедлива теорема [2].

Теорема 1   Пусть $I$ – ЗИП типа ${S_{id}}$ или типа ${S_{ne}}$, ${\cal F}$ – базовое множество, содержащее арифметические операции и операции сравнения. Тогда $ 1<T(I,{\cal F})<2$.

Задача включающего поиска принадлежит следующему типу:
$ S_b=\langle B^n, B^n,{\succeq},\sigma,{\bf P}\rangle,$ где $B^n$ – единичный $n$-мерный куб, ${\succeq}$ – отношение частичного порядка на $B^n$ "не меньше по-компонентно", ${\bf P}$ – равномерная вероятностная мера на $B^n$. Справедлива теорема [3].

Теорема 2   Пусть базовое множество имеет вид ${\cal F}=\langle F,\emptyset\rangle$, где $F\subseteq {\cal M}^n$ и ${\cal K}^n\subseteq F$, и ${\cal M}^n$ – множество монотонных булевых функций, а ${\cal K}^n$ – множество элементарных монотонных конъюнкций. Тогда для любой ЗИП $I$ типа $S_b$ $T(I,{\cal F})\geq 2 R(I)$ и существуют такие ЗИП $I$ типа $S_b$, что при $n \rightarrow \infty$ $T(I,{\cal F})= 2 R(I) (1 +\bar{o}(1)).$

Задача о доминировании состоит в поиске в конечном подмножестве $n$-мерного пространства всех тех точек, которые не больше по каждой из компонент чем запрос, являющийся в данном случае точкой $n$-мерного пространства. Пусть ${X_n}={[0,1]}^n$. Отношение поиска ${\rho_1}$ определено на ${X_n}\times {X_n}$ и задается следующим соотношением: $ (x_1,x_2,\ldots ,x_n){\rho_1}(y_1,y_2,\ldots ,y_n) \Longleftrightarrow y_i \leq x_i,\ i=\overline{1,n}. $ Тогда тип ${S_d}= \langle {X_n},{X_n},{\rho_1},\sigma,{\bf P}\rangle$ назовем типом задачи о доминировании. Задача интервального поиска состоит в поиске в конечном подмножестве $n$-мерного пространства всех тех точек, которые попадают в $n$-мерный параллелепипед-запрос. Пусть ${X_{in}}=\{ \tilde{x}=(u_1,v_1,\ldots ,u_n,v_n): 0\leq u_i \leq v_i \leq 1,\ i=\overline{1,n}\}$. Отношение поиска ${\rho_2}$ определено на ${X_{in}}\times {X_n}$ и задается следующим соотношением: $ (u_1,v_1,\ldots ,u_n,v_n){\rho_2}(y_1,\ldots ,y_n) \Longleftrightarrow u_i\leq y_i \leq v_i,\ i=\overline{1,n}. $ Тогда тип ${S_{in}}= \langle {X_{in}},{X_n},{\rho_2},\sigma,{\bf P}\rangle$ назовем типом интервального поиска. Справедлива следующая теорема [2,4].

Теорема 3   Пусть $I_1$ – ЗИП типа ${S_d}$, $I_2$ – ЗИП типа ${S_{in}}$, ${\cal F}$ – базовое множество, содержащее арифметические операции и операции сравнения. Тогда $0 < T(I_1,{\cal F})-R(I_1)\leq 2\,n-1,$ $ 0 < T(I_2,{\cal F})-R(I_2)\leq 4\,n+1. $

Литература

1
Гасанов  Э. Э. Информационно-графовая модель хранения и поиска данных. Интеллектуальные системы (1998) 3,  3-4, 163-192.

2
Гасанов  Э. Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8,  3, 119-134.

3
Гасанов  Э. Э. Нижняя оценка сложности информационных сетей для одного отношения частичного порядка. Дискретная математика (1996) 8,  4, 108-122.

4
Гасанов  Э. Э. Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска. Изд. центр РГГУ, Москва, 1997.
1
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 98-01-00130)

ДАН (2000) 374, N 4.

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru