Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети Л.Ю. Жилякова ПИ ЮФУ, г. Ростов-на-Дону zhilyakov@aaanet.ru Тверь, КИИ-2010. - презентация

1 Реализация рекурсивных запросов в динамической ассоциативной ресурсной сети Л.Ю. Жилякова ПИ ЮФУ, г. Ростов-на-Дону Тверь, КИИ-2010

2 Ассоциативная ресурсная сеть Ассоциативная ресурсная сеть представляет собой динамическую модель памяти, основанную на неоднородной ресурсной сети. Вершины сети соответствуют сущностям предметной области, ребра ассоциативным связям между ними. Способ хранения информации в ассоциативной сети таков, что наиболее часто используемые данные оказываются и наиболее доступными. Чем данные используются реже, тем труднее их найти. Обеспечение быстрого доступа к часто используемым данным реализуется благодаря двум свойствам сети.

3 Способ хранения информации в ассоциативной сети таков, что наиболее часто используемые данные оказываются и наиболее доступными. Чем данные используются реже, тем труднее их найти. Способ хранения информации в ассоциативной сети таков, что наиболее часто используемые данные оказываются и наиболее доступными. Чем данные используются реже, тем труднее их найти. АВСD E FGHIJ Обеспечение быстрого доступа к часто используемым данным реализуется благодаря двум свойствам сети.

4 I. ЯРКОСТЬ Каждая вершина обладает яркостью: доступность вершины тем выше, чем больше ее яркость, – тем эта вершина «виднее» при поиске. СВОЙСТВА СЕТИ

5 11 Каждая дуга сети, имеет свою проводимость, которая отвечает за способность передавать яркость от одной вершины к другой. Проводимость соответствует силе ассоциативной связи между сущностями: чем сильнее связь, тем выше проводимость. Каждая дуга сети, имеет свою проводимость, которая отвечает за способность передавать яркость от одной вершины к другой. Проводимость соответствует силе ассоциативной связи между сущностями: чем сильнее связь, тем выше проводимость. II. ПРОПУСКНАЯ СПОСОБНОСТЬ (ПРОВОДИМОСТЬ)

6 Ресурсная сеть Ресурсной сетью называется двусторонний граф с петлями, вершинам которого приписаны неотрицательные числа, называемые ресурсами, а рёбра способны доставлять ресурс от одной вершины к другим. Каждому ребру графа приписано неотрицательное число, называемое проводимостью, и характеризующее максимальное количество ресурса, передаваемое по нему за один такт времени. Ресурсной сетью называется двусторонний граф с петлями, вершинам которого приписаны неотрицательные числа, называемые ресурсами, а рёбра способны доставлять ресурс от одной вершины к другим. Каждому ребру графа приписано неотрицательное число, называемое проводимостью, и характеризующее максимальное количество ресурса, передаваемое по нему за один такт времени. В качестве математического аппарата для такой модели используется ресурсная сеть.

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

8 Ресурс вершины отвечает за яркость соответствующего ей понятия. Чем он больше, тем понятие ярче, тем оно доступнее в памяти. Яркость попадает в вершины, участвующие в запросе, и передается по рёбрам от вершины к вершине. При перетекании яркости высвечиваются вершины, ассоциированные с данными. Ресурс вершины отвечает за яркость соответствующего ей понятия. Чем он больше, тем понятие ярче, тем оно доступнее в памяти. Яркость попадает в вершины, участвующие в запросе, и передается по рёбрам от вершины к вершине. При перетекании яркости высвечиваются вершины, ассоциированные с данными. Распространение яркости

9 Ресурс вершины q i Правила распространения яркости (правило 1) i

10 Ресурс вершины q i Правила распространения яркости (правило 2)

11 В каждый такт времени происходит перераспределение ресурса между вершинами. Процесс завершается, когда ресурс в вершинах достигает постоянного предельного значения или асимптотически сходится к нему. Это условие равносильно тому, что в каждой двусторонней паре навстречу друг другу начинает течь равное (или почти равное) количество ресурса. В каждый такт времени происходит перераспределение ресурса между вершинами. Процесс завершается, когда ресурс в вершинах достигает постоянного предельного значения или асимптотически сходится к нему. Это условие равносильно тому, что в каждой двусторонней паре навстречу друг другу начинает течь равное (или почти равное) количество ресурса. Распространение яркости

12 Изменение топологии сети Особенностью предложенной модели является динамическое изменение ее топологии всякий раз после того, как происходит обращение к сети с очередным запросом. Если во время выполнения запроса ребро участвовало в перераспределении ресурса, оно увеличит свою проводимость.

13 Пока в сеть не поступает запросов, она находится в неактивном состоянии. В сети вводится время двух типов: 1) медленное время ; 2) быстрое время t. Один такт медленного времени соответствует выполнению одного запроса. Медленное время отвечает за изменение проводимостей ребер и создание новых ребер. За один такт у каждого ребра происходит не более одного изменения проводимости. Быстрое время включается во время исполнения запроса. Оно отвечает за распределение ресурса по вершинам. Медленное и быстрое время

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

15 Проводимость петли увеличивается на заданный «квант проводимости» всякий раз, когда вершина связывается с новой вершиной, или упоминается при любом изменении структуры. Проводимость связи увеличивается всякий раз, когда две соответствующие вершины упоминаются вместе. Изменение проводимостей r ii = r ii + 0 r jj = r jj + 0 r ij = r ij + 0 r ji = r ji + 0 Сеть обязательно заполняется с самого начала. На нулевом шаге она пуста.

16 Пример построения сети Вот дом, Который построил Джек. Дом Джек Дом, который построил Джек

17 А это пшеница, Которая в темном чулане хранится В доме, Который построил Джек. Пример построения сети Дом Джек Дом, который построил Джек ПшеницаЧулан

18 Пример построения сети Дом Джек Дом, который построил Джек ПшеницаЧулан А это веселая птица-синица, Которая часто ворует пшеницу, Которая в темном чулане хранится В доме, Который построил Джек. Синица

19 Пример построения сети Дом Джек Дом, который построил Джек ПшеницаЧулан Синица Вот кот, Который пугает и ловит синицу, Которая часто ворует пшеницу, Которая в темном чулане хранится В доме, Который построил Джек. Кот

20 Вот два петуха, Которые будят того пастуха, Который бранится с коровницей строгою, Которая доит корову безрогую, Лягнувшую старого пса без хвоста, Который за шиворот треплет кота, Который пугает и ловит синицу, Которая часто ворует пшеницу, Которая в темном чулане хранится В доме, Который построил Джек. Готовый фрагмент сети Дом, который построил Джек

21 Восстановление образа по его части

22 Управление движением яркости Запрос к ассоциативной сети входное множество вершин и количество яркости, которое им приписывается. В больших сетях яркость может растекаться от каждой вершины неограниченно во все стороны. Чтобы локализовать область поиска и управлять движением «пятна яркости» в сети, используются рекурсивные запросы.

23 Под рекурсивным запросом будем понимать многократный запрос, входное множество вершин которого изменяется в зависимости от выходного множества на предыдущем шаге по одному из наперед заданных правил. Алгоритм выполнения одного шага рекурсии 1. В начальное множество вершин поступает яркость; 2. Яркость начинает распространяться в соответствии с правилами 1-2 ресурсной сети t R тактов быстрого времени t. (Величина t R задана заранее.); 3. По окончании распределения из вершин, имеющих яркость, выбирается новое начальное множество. И процесс повторяется. Реализация рекурсивных запросов

24 Виды запросов 1. Добавление к входному множеству одной или нескольких вершин из выходного множества предыдущего шага рекурсии Этот тип изменений соответствует ситуации, когда самый ожидаемый (вероятный) ответ на поставленный запрос является удовлетворительным, но его нужно расширить и/или уточнить. l – мощность выходного множества, l* – мощность пересечения входного и выходного множества.

25 2. Удаление одной или нескольких вершин из входного множества предыдущего запроса 2. a) Удаляются вершины из пересечения множеств вопрос-ответ, т.е. входного и выходного множеств предыдущего запроса.. Такие изменения предназначены для отсекания самого очевидного ответа и поиска других, менее очевидных. То есть, чтобы получить заведомо «нетривиальный» ответ, сначала нужно узнать ответ тривиальный, и только затем его отсечь.

26 2. Удаление одной или нескольких вершин из входного множества предыдущего запроса 2. b) Удаляются вершины из предыдущего входного множества, которых не оказалось в множестве выходном.. Эти изменения производятся, если нужно создать длинные ассоциативные цепочки, – создать движение яркости сквозь сеть. Чем меньше вершин из предыдущего входного множества перейдет в следующее, тем быстрее будет передвигаться «пятно яркости» по сети, охватывая каждый раз новые участки. m – мощность входного множества.

27 Комбинируя все возможные сочетания добавления и удаления вершин, получим. различных множеств, каждое из которых претендует на то, чтобы быть входным множеством запроса на следующем шаге рекурсии.

28 Операции над графами 1. Оператор T(G) – транзитивное замыкание графа G. Действует он следующим образом: для любого графа G T(G) – такой граф, что для любых двух вершин верно: если есть путь любой длины из вершины v i в вершину v j, то есть и двусторонняя пара, связывающая эти вершины. G InOut (i) = T(G In (i) G Out (i)). Множество его вершин – это по-прежнему вершины графа G In (i) G Out (i). Проводимость каждого вновь созданного ребра рассчитывается как среднее геометрическое проводимостей ребер, составляющих цепочку. 2. Оператор А – добавление вершин. Запись: (G 1, G 2 ) означает, что из графа G 2 в граф G 1 будет добавлено k вершин с номерами j 1, …, j k вместе со всеми ребрами, соединяющими эти вершины с вершинами G 1..

29 Операции над графами 3. Оператор Е (удаление вершин) применяется к одному графу. Запись: (G) означает, что из графа G будет удалено h вершин с номерами j 1 ', …, j h ' вместе с их инцидентными ребрами. Тогда на шаге i + 1 удаление из графа G In (i) вершин с номерами j 1 ', …, j h ', где h m (m – мощность множества вершин G In (i)), запишется в следующем виде:. G In (i +1) = (G In (i)).

30 Операции над графами Будем считать, что сначала к графу G In (i) применяется оператор Е, а затем к результату – оператор А. Операторы не коммутируют, порядок их применения важен. Таким образом, на шаге i + 1 входной граф запроса находится по следующей рекуррентной формуле: G In (i +1) = ( (G In (i))).. Непосредственно из этой формулы вытекает, что каждый новый входной подграф однозначно определяется входным и выходным подграфами на предыдущем шаге и парой последовательностей натуральных чисел переменной длины: ({j 1 ', …, j h '}; { j 1, …, j k }).

31 Заключение Топология изменяется автоматически таким образом, что наиболее востребованная информация оказывается наиболее доступной. Ассоциативность сети заключается не только в адресации по содержанию, но и в структуре взаимосвязей моделируемой предметной области, в которой близость понятий определяется не только и не столько семантикой, сколько самим функционированием сети, т.е. пользовательскими запросами и ответами на них. Управление движением ресурса сквозь сеть осуществляется как самой топологией сети, которая направляет ресурс по ребрам с большей проводимостью, так и рекурсивным заданием нового входного множества и продолжением поиска в заданном направлении. Топология изменяется автоматически таким образом, что наиболее востребованная информация оказывается наиболее доступной. Ассоциативность сети заключается не только в адресации по содержанию, но и в структуре взаимосвязей моделируемой предметной области, в которой близость понятий определяется не только и не столько семантикой, сколько самим функционированием сети, т.е. пользовательскими запросами и ответами на них. Управление движением ресурса сквозь сеть осуществляется как самой топологией сети, которая направляет ресурс по ребрам с большей проводимостью, так и рекурсивным заданием нового входного множества и продолжением поиска в заданном направлении.

32 Спасибо за внимание