Buchumschlag

Поиск аналогов с помощью распределенных представлений

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

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2005
Hauptverfasser: Рачковский, Д.А., Мисуно, И.С., Слипченко, С.В., Соколов, А.М.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут програмних систем НАН України 2005
Schlagworte:
Інформаційні системи
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/1369
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Поиск аналогов с помощью распределенных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 1. — С. 39–50. — Бібліогр.: 34 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859627345580654592
author Рачковский, Д.А.
Мисуно, И.С.
Слипченко, С.В.
Соколов, А.М.
author_facet Рачковский, Д.А.
Мисуно, И.С.
Слипченко, С.В.
Соколов, А.М.
citation_txt Поиск аналогов с помощью распределенных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 1. — С. 39–50. — Бібліогр.: 34 назв. — рос.
collection DSpace DC
description Рассматриваются модели первой стадии рассуждений по аналогии: поиск в памяти аналога некоторой ситуации. Ситуации и аналоги иерархически структурированы и могут включать отношения высших порядков, что усложняет поиск при использовании традиционных подходов. Приводятся схемы распределенного представления аналогов в виде многомерных бинарных векторов. Показано, что степень сходства ситуаций можно оценить по величине скалярного произведения представляющих их векторов. Это создает основу для моделирования процессов поиска аналогов людьми и для более эффективного поиска в базах знаний. Розглядаються моделі першої стадії міркувань за аналогією: пошук у пам’яті аналогів деякої ситуації. Ситуації та аналоги ієрархічно структуровані і можуть включати відношення вищих порядків, що ускладнює пошук за умов використання традиційних підходів. Наводяться схеми розподіленого представлення аналогів у вигляді багатовимірних бінарних векторів. Показано, що ступінь схожості ситуацій можна відобразити за допомогою величини скалярного добутку векторів, які їх представляють. Це створює підґрунтя для моделювання процесів пошуку аналогів людьми та для більш ефективного пошуку у базах знань. Models of the first stage in analogical reasoning, analogical access, are considered. Schemes for distributed representations of hierarchically structured episodes as multidimensional binary vectors are presented. Such schemes reflect similarity of analogical episodes by the scalar product of vectors representing them. This simplifies searching for the most similar analogs and allows modeling of preferences demonstrated by humans in analogical access tasks.
first_indexed 2025-11-29T12:03:50Z
format Article
fulltext Інформаційні системи © Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко, А.М. Соколов, 2005 ISSN 1727-4907. Проблеми програмування. 2005. № 1 39 УДК 004.82 + 004.838.3 Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко, А.М. Соколов ПОИСК АНАЛОГОВ С ПОМОЩЬЮ РАСПРЕДЕЛЕННЫХ ПРЕДСТАВЛЕНИЙ Рассматриваются модели первой стадии рассуждений по аналогии: поиск в памяти аналога некоторой ситуации. Ситуации и аналоги иерархически структурированы и могут включать отношения высших порядков, что услож- няет поиск при использовании традиционных подходов. Приводятся схемы распределенного представления аналогов в виде многомерных бинарных векторов. Показано, что степень сходства ситуаций можно оценить по ве- личине скалярного произведения представляющих их векторов. Это создает основу для моделирования процессов поиска аналогов людьми и для более эффективного поиска в базах знаний. Введение Рассуждения по аналогии — это процесс восприятия общности отношений, существующих в ситуа- циях (предметных областях, эпи- зодах), которые могут выглядеть непохожими при поверхностном рассмотрении [1–3]. Известным примером использования в науке является аналогия с солнечной системой, которую применил Ре- зерфорд при создании планетарной модели атома. Рассуждения по аналогии являются одним из важ- нейших процессов в разумной дея- тельности людей, а их моделиро- вание представляет собой одну из самых интересных задач искусст- венного интеллекта [1, 4–6]. Рассуждения по аналогии предполагают оперирование слож- ной структурированной информаци- ей. В подходах [1–3, 7, 8] и других аналоги являются структу- рированными высказываниями, со- держащими компоненты разного уровня сложности — признаки, объекты, отношения разного по- рядка, подструктуры и т.д. (рис. 1). Аналоги сравнивают по "по- верхностному сходству", основан- ному на наличии общих элементов СЛЕДСТВИЕ И ВРАЩАТЬСЯ-ВОКРУГ РАЗНИЦА-В-МАССЕ ПРИТЯГИВАЕТ СОЛНЦЕ ПЛАНЕТА СОЛНЦЕ ПЛАНЕТА ПЛАНЕТА СОЛНЦЕ СОЛНЦЕ ЖЕЛТЫЙ СЛЕДСТВИЕ КИСЛОРОДНАЯ-АТМОСФЕРА ОБИТАЕМАЯ СОЛНЕЧНАЯ СИСТЕМА ПЛАНЕТА ПЛАНЕТА РАЗНИЦА-В-МАССЕ ПРИТЯГИВАЕТ ЯДРО ЭЛЕКТРОН ЯДРО ЭЛЕКТРОН АТОМ ВРАЩАТЬСЯ-ВОКРУГ ЯДРО ЭЛЕКТРОН Рис. 1. Графическое представление аналогии Резерфорда "солнечная система — атом" Інформаційні системи 40 [1, 9], или по "семантическому сходству" этих элементов [2, 10], основанному на их некоторой априорной семантической близости (например, принадлежности к од- ному таксономическому классу). Однако не менее важно структур- ное сходство, которое определя- ется тем, как элементы аналогов группируются друг относительно друга. Структурное сходство ос- новано на понятии "структурной согласованности" [3, 11] или "изоморфизма" [2, 10]. Эти обна- руженные психологами ограничения на структурное сходство, которые демонстрируют люди при сравнении эпизодов, предполагают взаимно однозначное соответствие (не бо- лее одного элемента в одном ана- логе соответствует некоторому элементу в другом) и параллель- ную связность (соответствующие отношения должны иметь соответ- ствующие аргументы). Насколько жесткие эти ограничения, по- прежнему является открытым во- просом [2, 7, 10]. В рассуждениях по аналогии первыми тремя стадиями обычно считают [1, 2, 9–11] поиск ана- логов, установление соответствия между ними и вывод по аналогии. Поиск (извлечение из памяти, распознавание или доступ — analogical access) — процесс об- наружения в памяти наиболее под- ходящего аналога ко входному. Установление соответствия (ото- бражение — analogical mapping) — процесс обнаружения соответствий между компонентами двух анало- гов. Вывод по аналогии — процесс переноса знаний от одного анало- га к другому. Все эти стадии требуют обработки структуриро- ванной информации, содержащейся в представлении аналогов. Реализация и эффективность операций над структурированной информацией (таких, как оценка сходства, сравнение, нахождение соответствующих элементов, об- ход, и др.) существенно зависит от используемой схемы ее пред- ставления. До недавнего времени представление и обработка струк- тур осуществлялись только в рам- ках символьных или локальных представлений. Естественно, что именно они использованы в наибо- лее значимых вычислительных мо- делях рассуждений по аналогии — например, ARCS-ACME [9–11], см. также ссылки в [12]. Из-за ограничений исполь- зуемых методов представления ин- формации в этих моделях затруд- нены представление и учет семантического сходства компо- нентов, а применяемые алгоритмы требуют значительных затрат вы- числительных ресурсов. Кроме то- го, имеются проблемы с объясне- нием возможности реализации таких моделей в нейронных сетях мозга, в то время как использо- вание принципов и методов, на которых базируется поиск анало- гов в нейробиологических струк- турах мозга человека, может по- зволить создать модели рассуждений по аналогии, прибли- жающиеся по свойствам к рассуж- дениям людей. Необходимость расширения семантического базиса представ- ления аналогов, масштабирования подходов на случаи, когда имеет- ся большое количество потенци- альных аналогов, и повышения степени нейробиологической реле- вантности моделей привела к по- пыткам использования в моделях аналогии распределенного пред- ставления информации (например, LISA [2], Drama [8], STAR2). Од- нако их использование носило не- последовательный характер как из-за недостатков использованных схем для представления информа- ции о структуре, так и из-за не- достаточной проработанности под- ходов. В связи с этим перспективными для моделирования рассуждений по аналогии являются Інформаційні системи 41 появившиеся недавно новые типы распределенных представлений (HRR [13], BSC [6], АПНС [14]). В данной статье рассматри- вается подход к представлению структурированной информации с помощью специального типа рас- пределенных представлений — мно- гомерных разреженных бинарных векторов. Такие схемы разрабаты- ваются в рамках архитектуры ас- социативно-проективных нейронных сетей (АПНС). Они позволяют представить эпизоды-аналоги (или другие сложные структурированные описания) в виде "кодвекторов", величина корреляции которых, из- меряемая скалярным произведени- ем, отражает степень сходства эпизодов, оцениваемую психолога- ми в экспериментах с людьми. Это позволяет упростить поиск анало- гов и открывает возможности пре- одоления других недостатков тра- диционных подходов к моделированию рассуждений по аналогии. 1. Традиционные модели поиска аналогов Большинство моделей поиска аналогов основано на символьном или локальном представлении ин- формации [15, 16]. В них каждый новый элемент или их комбинация требуют выделения нового "узла" ("вершины" или "нейрона" в нейро- сетевых локальных представлени- ях) или ячейки памяти (в тради- ционных компьютерных символьных представлениях). Представление иерархических структур, каковыми являются аналоги — в общем слу- чае, направленные ациклические графы (например, [17]), — стро- ится с помощью семантических се- тей или их символьных вариантов. Узлы более высокого иерархиче- ского уровня, соответствующие более сложным структурам, со- единены с узлами более низких иерархических уровней, представ- ляющими их подструктуры разной сложности, вплоть до неразложи- мых элементов нижнего уровня (рис. 2). Такие "растущие" сети локальных элементов разрабатыва- ются рядом исследователей, напри- мер [5, 18, 19]. Для оценки сходства струк- Аналог 1 Аналог 2 Рис. 2. Локальное представление аналогов. Аналоги являются иерар- хическими структурами. Определение сходства требует вычислительно сложного сопоставления их элементов. Стрелками обозначены наилуч- шие соответствия между элементами аналогов, а пунктирными линиями — некоторые другие возможные кандидаты на соответствия. Линиями без стрелок показаны отношения «часть-целое» между элементами раз- ных уровней Інформаційні системи 42 турированной информации иногда привлекают подходы, использующие понятие частичного изоморфизма ([20–22] и др.). Его выявление для графов является сложной за- дачей. Однако изоморфизм не учи- тывает сходство самих элементов и не отражает особенностей оцен- ки сходства, обнаруженных психо- логами в рассуждениях по анало- гии у людей [2, 23]. В других существующих моде- лях поиска аналогов такие осо- бенности учитывают. Используемые для этого методы включают по- строение и эволюцию (стабилиза- цию) нейроподобных сетей, удов- летворяющих ограничениям (constraint-satisfaction networks), которые находят наи- лучшее соответствие между эле- ментами аналогов ([8], см. также ссылки в [12]), либо символьную обработку виртуальных сетей, представляющих эти соответствия [11], или использование "отобра- жающих связей" между "динамиче- скими связками" [16], представ- ленными одновременной активацией узлов в локальной сети (см. рис. 2). Однако, несмотря на на- лагаемые ограничения, оценка сходства структур остается очень "дорогой" в вычислительном отно- шении процедурой. Существуют различные точки зрения об относительной роли по- верхностного и структурного сходства в доступе к аналогам в памяти. Хотя структурное сходст- во при поиске аналогов считается менее важным, чем в отображении, модели, которые принимают во внимание только поверхностное сходство, считаются неадекват- ными [2, 3, 9, 10]. Таким образом, модели поиска аналогов, разработанные на базе локальных и символьных представ- лений, в общем случае требуют сложного сравнения входного (це- левого) аналога с (базовыми) аналогами в долговременной памя- ти. При этом каждое сравнение включает вычислительно дорогую стадию нахождения соответствия подструктур. Так как предполага- ется, что в памяти может хра- ниться много эпизодов, процесс поиска аналогов может быть недо- пустимо долгим и следует исполь- зовать способы ограничения ко- личества кандидатов на сравнение. Одним из таких спо- собов является общая стратегия введения двухступенчатого поиска аналогов в памяти, используемая в MAC/FAC [9] и ARCS [10]. На первой стадии для выбора кандидатов используется вычисли- тельно несложный процесс, осно- ванный только на наличии иден- тичных объектов или признаков. Выбираются кандидаты, которые имеют ряд общих с входным анало- гом элементарных объектов без учета их структуры и отношений. Вторая стадия требует нахо- ждения детального сходства с учетом структуры и выполнения сложных вычислений, чтобы оце- нить все аспекты сходства между входным эпизодом и кандидатами. Хотя двухступенчатая схема обна- ружения наилучшего соответствия и обеспечивает экономию вы- числений, эта экономия недоста- точна. Кроме того, на первой стадии есть риск пропустить по- тенциально лучшего кандидата. 2. Распределенное представление и обработка структур в АПНС В полностью распределенных представлениях [15, 24] любой объект представлен как кодвек- тор, каждый элемент которого можно рассматривать как соответ- ствующий состоянию некоторого "нейрона". Для похожих объектов естественно использовать корре- лированные кодвекторы и оцени- вать их сходство скалярным про- Інформаційні системи 43 изведением. Однако ранее предпо- лагалось, что иерархические структуры нельзя представить распределенным образом из-за “катастрофы суперпозиции” — по- тери информации о размещениях объектов в структурах [16]. В ряде распределенных схем, таких, как АПНС [14, 16], HRR [24], BSC [25], для решения этой проблемы были предложены проце- дуры связывания (аналог скобок в символьных представлениях [16, 26]). В этих схемах оказалось возможным создавать распределен- ные представления иерархических структур с помощью кодвекторов одинаковой размерности. На сходство кодвекторов, кодирующих эти структуры, влияют как набор компонентов, так и от- ношения между ними. Cходные по набору и группировке компонентов структуры дают сходные кодвекто- ры [16, 26]. Поэтому, в отличие от традиционных методов, нет необходимости явно определять соответствие между элементами (подструктурами) двух структур, чтобы оценить их полное сходст- во. Достаточно найти перекрытие их кодвекторов. Другое достоин- ство — это то, что сходство эле- ментарных компонентов может быть не типа "все или ничего", а гра- дуальным. Кратко рассмотрим разраба- тываемую нами в рамках архитек- туры ассоциативно-проективных нейронных сетей (АПНС) схему распределенного представления и обработки иерархически структу- рированной информации. Более де- тальное обсуждение и сравнение с другими схемами распределенного представления структур приведено в [14, 16]. Применению этой схе- мы для моделирования поиска ана- логий посвящен раздел 3. 2.1. Ассоциативно- проективные нейронные сети. В АПНС объекты (информационные единицы) любого уровня иерархии, элементарные или составные, представлены длинными кодвекто- рами одинаковой размерности. Кодвекторы — это двоичные и раз- реженные (с малой долей единиц p=M/N) векторы, например, с N=100,000 элементов, представляю- щих нейроны, и M=1,000 единиц, представляющих активные нейроны. Асимметричное нормированное пе- рекрытие единиц кодвекторов мо- жет быть измерено как доля сов- падающих единиц O(X,Y) = |X∧Y|/|X|, где |X| — количество единиц в кодвекторе X. Векторы конструируют таким образом, чтобы величина их пере- крытия отражала степень сходства объектов. Непохожие объекты представляют независимыми псев- дослучайными векторами, что для разреженного случая дает малое перекрытие p2, а похожие объекты — кодвекторами с большей величи- ной перекрытия единиц, чем слу- чайное. Для иерархических структур формирование кодвекторов осуще- ствляется следующим образом. Обычно элементы структур некото- рого уровня иерархии являются совокупностями небольшого коли- чества (под)структур — компонен- тов этих сложных структур с ни- жележащих уровней. Кодвекторы более сложных структур строятся из множества кодвекторов их ком- понентов. Поскольку каждый ком- понент может быть сложной со- ставной (под)структурой, можно представлять структуры произ- вольной сложности. Чтобы сохра- нить информацию о группировании компонентов, в АПНС используется связывание их кодвекторов с по- мощью контекстно-зависимого про- реживания (context-dependent thinning, CDT [16, 26]). Одна из версий CDT описана ниже (обсуж- дение различных версий и реали- заций CDT приведено в [16]). Інформаційні системи 44 2.2. Процедура контекстно- зависимого прореживания. Возьмем побитовую дизъюнкцию S (S = 2, ..., 5) псевдослучайных кодвекторов Xs компонентов, которые должны быть связаны: Z = S s 1= ∨Xs. (1) Сформируем прореженный код- вектор Z как 〈Z〉= K k 1= ∨ (Z ∧ Z ~ (k)) = Z ∧ K k 1= ∨Z ~ (k). (2) Здесь Z ~ (k) — это Z с пере- ставленными элементами. Каждая k-я перестановка должна быть фиксированной, уникальной и не- зависимой. Случайные перестанов- ки были бы идеальным вариантом, однако и перестановки цикличе- ским сдвигом со случайным коли- чеством сдвигов достаточно удоб- ны в приложениях. Число K дизъюнктивно наложенных векторов с переставленными элементами вы- бирается так, чтобы количество единиц в Z было приблизительно таким, как требуется — обычно, сравнимым с плотностью кодвекто- ров компонентов Xs. Возможно много "конфигура- ций" прореживания (путем дизъ- юнкции различных перестановок Z). Обозначим разные конфигура- ции прореживания разными метками (например, 1, 2, 5, u) как верх- ний индекс левой угловой скобки (например, 1 〈Z〉, 2〈Z〉, 5〈Z〉, u〈Z〉). Прореженные кодвекторы по- хожих наборов компонентов похожи друг на друга: 〈A∨B∨C〉 похож на 〈A∨B∨D〉. Прореженные кодвекторы похожи на каждый из кодвекторов компонентов: 〈A∨B∨C〉 похож на A. Однако представление (подмноже- ство единиц) A в 〈A∨B∨C〉 отлича- ется от подмножества единиц A в 〈A∨B∨D〉. 2.3. Иерархическая память. В АПНС, все кодвекторы всех уровней иерархии хранятся в ие- рархической памяти [14]: соот- ветствующие объектам одного уровня — в одном массиве, а раз- ных уровней — в разных массивах памяти. Например, A, B, C, D и другие кодвекторы одной сложно- сти хранятся на одном уровне, тогда как 〈A∨B∨C〉, 〈A∨B∨D〉 и т.д. — в массиве памяти более высоко- го уровня. Память на каждом уровне должна выполнить поиск самого близкого кодвектора ко входному. Заметим, что на раз- ных иерархических уровнях ис- пользуются различные конфигура- ции прореживания, а конфигурация прореживания, "закрепленная" за некоторым массивом памяти, по- стоянна. Такое устройство памяти по- зволяет выполнить обход уровней иерархии представлений, исполь- зуя сходство кодвекторов, сле- дующим образом. Пусть имеется кодвектор некоторого иерархиче- ского уровня — назовем его "про- бом". По пробу можно найти похо- жий кодвектор в массиве того же уровня иерархии (например, 〈A∨B∨C〉 по 〈A∨B∨D〉). Можно также найти компоненты проба ("декоди- ровать проб") путем его подачи в массивы более низкого уровня и выбора кодвекторов компонентов, имеющих максимальное перекрытие с пробом (например, A, B, C по 〈A∨B∨C〉). В свою очередь, они могут быть декодированы через компоненты более низкого уровня (если таковые есть) и т.д. Можно также найти более сложные код- векторы, которые содержат проб в качестве своих компонентов, пу- тем поиска сходных с пробом код- векторов на верхних уровнях па- мяти (например, 〈A∨B∨C〉 по A). Если бы кодвекторы разной уровни сложности находились в одном массиве памяти, нельзя было бы Інформаційні системи 45 определить только по их сходству с пробом, найден ли кодвектор супермножества или подмножества. Каждый из массивов может быть нейросетевой автоассоциа- тивной памятью, например, опи- санного в [27, 28] типа. Однако сейчас функционирование такого массива памяти моделируется пу- тем запоминания его кодвекторов в виде списка и выполнения пол- ного поиска на самое близкое со- ответствие путем вычисления пе- рекрытия проба со всеми кодвекторами массива. Обсудим, как рассмотренные операции и процедуры могут ис- пользоваться для представления иерархических реляционных струк- тур, какими являются аналоги- эпизоды. 2.4. Представление иерархи- ческих реляционных структур. Рассмотрим две схемы представле- ния реляционных структур в АПНС [16]. Они соответствуют двум из- вестным схемам представления предикатов в символьных представ- лениях: «роль – заполнитель» и «предикат – аргументы». В каче- стве примеров возьмем эпизоды или ситуации, которые применяют- ся при моделировании рассуждений по аналогии (в других системах терминологии их называют сужде- ниями, высказываниями, предика- тами и др.). 2.4.1. Схема "роль – запол- нитель". Рассмотрим иерархический эпизод "Спот укусил Джейн, за- ставив Джейн бежать от Спота" (Spot bit Jane, causing Jane to flee from Spot). Используя пред- ставления АПНС типа "роль – за- полнитель" (role-filler), код- вектор эпизода может быть представлен как в [14]: P = 4〈3〈cause_antc ∨ P(bite)〉 ∨ ∨ 3〈cause_cnsq ∨ P(flee)〉〉, (3) где P(bite) = 2〈1〈bite_agt ∨ spot〉 ∨ ∨ 1〈bite_obj ∨ jane〉〉, (4) P(flee) = 2〈1〈flee_agt ∨ jane〉 ∨ ∨ 2〈flee_obj ∨ spot〉〉. (5) Здесь кодвекторы ролей и заполнителей связаны с помощью процедуры CDT, например 1 〈bite_agt ∨ spot〉, 1 〈bite_obj ∨ jane〉, где bite_agt соответствует "роль первого мес- та в отношении укусил" (агент) и bite_obj соответствует "роль вто- рого места в отношении укусил" (объект). 1 〈…〉 обозначает проре- живание с использованием опреде- ленной конфигурации прорежива- ния, помеченной "1", как описано в разд. 2.2. Кодвекторы распреде- лены по массивам памяти различ- ных уровней, соответствующих уровням иерархии закодированных ими компонентов (табл. 1), и метка прореживания соответствует номеру уровня. Аналогично P1(flee) = 1〈P_structure(jane-spot) ∨ ∨ P_components(flee,jane,spot)〉, (6) и весь эпизод в целом будет за- кодирован так: P1 = 2〈cause ∨ P1(bite) ∨ P1(flee) ∨ ∨ P1(bite)>>antc ∨ P1(flee)>>cnsq〉. (7) 2.4.2. Позиционная схема. Один из известных методов пред- ставления места объекта в после- довательности состоит в том, чтобы отвести для каждого места отдельное подмножество ресурсов. Такой метод ведет к росту раз- мерности кодвекторов. Чтобы сох- ранить ее фиксированной, предло- жено кодировать различные позиции объекта (циклическим) сдвигом или другой обратимой пе- рестановкой его кодвектора. Інформаційні системи 46 В нашем примере это может быть реализовано как spot>>agent, jane>>object. Здесь X >> n обознача- ет X, пермутированный или сдви- нутый для кодирования n-й пози- ции в последовательности. Этот тип представления порядка может быть соотнесен с известным сим- вольным представлением "символ- аргумент-аргумент" (или "преди- кат-аргументы" — predicate-argu- ments). Кодвектор рассматривае- мого эпизода, согласно этой схеме представления, будет сле- дующим: P1(bite) =1 〈P_structure(spot-jane) ∨ ∨ P_components(bite,spot,jane)〉, (8) где P_structure(spot-jane) = spot>>agent ∨ ∨ jane>>object, (9) P_components(bite,spot,jane) = bite ∨ ∨ spot ∨ jane. (10) Аналогично P1(flee) = 1〈P_structure(jane-spot) ∨ ∨ P_components(flee,jane,spot)〉, (11) и кодвектор эпизода в целом бу- дет выглядеть так: P1 = 2〈cause ∨ P1(bite) ∨ P1(flee) ∨ ∨ P1(bite)>>antc ∨ P1(flee)>>cnsq〉. (12) Табл. 2 показывает распре- деление кодвекторов по массивам памяти разных уровней иерархии. Рассмотрим, как подобного рода представления используются при моделировании процессов поиска аналогов. Таблица 1. Пример организации памяти эпизода для схемы "роль – заполнитель" Уровень иерархии Кодвекторы компонентов аналогов Конфигурация прореживания Уровень#4 Probe = 4〈 Antc ∨ Cnsq 〉 4 〈 〉 Antc = 3〈 cause_antc ∨ Bite 〉 3 〈 〉 Уровень#3 Cnsq = 3〈 cause_cnsq ∨ Flee 〉 Bite = 2〈1〈bite_agt ∨ spot 〉∨ 1〈bite_obj ∨ jane〉〉 2 〈 〉 Уровень#2 Flee = 2〈1〈flee_agt ∨ jane〉 ∨ 1〈flee_obj ∨ spot〉〉 bite_a = 1〈bite_agt ∨ spot〉 bite_o = 1〈bite_obj ∨ jane〉 1 〈 〉 Уровень#1 flee_a = 1〈flee_agt ∨ jane〉 flee_o = 1〈flee_obj ∨ spot〉 Уровень#0 spot = dog ∨ id_spot jane = human ∨ id_jane human dog cat mouse id_jane id_john id_fred id_felix id_fido id_spot id_rover id_mort Нижний уровень bite_agt bite_obj flee_agt flee_obj cause_antc cause_cnsq Інформаційні системи 47 3. Поиск аналогов с помощью представлений АПНС Как указывалось выше, в распределенных представлениях, учитывающих структуру, набор компонентов и их группирование должны влиять на сходство код- векторов так, что похожие струк- туры получат похожие кодвекторы. Двухступенчатое сравнение, при- меняемое в традиционных моделях доступа (разд. 1), в этом случае не нужно. Задача состоит в том, чтобы создать такие кодвекторы эпизодов-аналогов, величины сходства которых отражают сте- пень сходства эпизодов, выявлен- ную психологами в результате экспериментов с людьми. В результате поиск наиболее близкого аналога в памяти с по- мощью учитывающих структуру рас- пределенных представлений может осуществляться путем нахождения кодвектора, наиболее похожего на входной, в долговременной памя- ти, где хранятся кодвекторы всех эпизодов. 3.1. Представление эпизо- дов-аналогов с различным типом сходства. Чтобы проиллюстриро- вать поиск аналогов в АПНС, ис- пользуем эпизоды из [13, 10]. Участвуют следующие персонажи или объекты: собаки (Фидо, Спот, Ровер), люди (Джейн, Джон, Фред), кот (Феликс), мышь (Морт). Отношения: кусать, бе- жать, быть причиной. Назовем пробным эпизод, к которому надо найти ближайший аналог в памяти. Используем в качестве пробного эпизод P, который уже встречался ранее: "Spot bit Jane, causing Jane flee from Spot" (разд. 2.4). Эпизоды, хранящиеся в па- мяти, имеют те же самые отноше- ния, что и пробный, но различные типы сходства с ним — главным образом, согласно классификации Джентнер [1] (см. также [9]). Основными типами сходства являются структурное (сходство отношений) и поверхностное (сходство объектов). Эпизод с буквальным сходством (literal similarity, LS) имеет как струк- турное, так и поверхностное сходство с пробным: "Фидо укусил Джона, заставив Джона убежать от Фидо" ("Fido bit John, causing John to flee from Fido"). Эпизод с поверхностными признаками (surface features, SF) имеет по- верхностное, но не структурное сходство с пробным: "Джон убежал от Фидо, заставив Фидо укусить Джона" ("John fled from Fido, causing Fido to bite John"). Таблица 2. Пример организация памяти эпизода для "позиционной" схемы Уровень иерархии Кодвекторы компонентов аналогов Конфигурация прореживания Уровень#2 P = 2〈cause ∨ BITE ∨ FLEE ∨ BITE>>cause_antc ∨ FLEE>>cause_cnsq〉 2 〈 〉 BITE = 1〈bite ∨ spot ∨ jane ∨ spot>>agent ∨ jane>>object〉 Уровень#1 FLEE = 1〈flee ∨ spot ∨ jane ∨ jane>>agent ∨ spot>>object〉 1 〈 〉 Уровень#0 spot = dog ∨ id_spot jane = human ∨ id_jane human dog cat mouse id_jane id_john id_fred id_felix id_fido id_spot id_rover id_mort Нижний уровень bite flee cause Інформаційні системи 48 Эпизод перекрестного отображения (сross-mapped, CM) имеет струк- турное и поверхностное сходство с пробным, но типы соответствую- щих объектов переставлены: "Фред укусил Ровера, заставив Ровера убежать от Фреда" ("Fred bit Rover, causing Rover to flee from Fred"). Эпизод с анало- гичным сходством (analogy, AN) имеет структурное, но не поверхностное сходство: "Морт укусил Феликса, заставив Феликса убежать от Мор- та" ("Mort fled from Felix, causing Felix to bite Mort"). Эпизоды с отношениями первого порядка (first order relations only, FOR) не имеют ни структур- ного, ни поверхностного сходст- ва, а только общие предикаты: "Морт убежал от Феликса, заста- вив Феликса укусить Морта" ("Mort fled from Felix, causing Felix to bite Mort") (табл. 3). Чтобы сформировать АПНС- представления эпизодов, необхо- димо закодировать объекты и от- ношения, используя кодвекторы основного уровня. Под кодвекто- рами основного уровня понимаем независимо сгенерированные код- векторы самого нижнего композиционного уровня (см. табл. 1, 2). В их качестве используем случайные бинарные векторы с N=100,000, M=1,000. Все отношения и роли счита- ем непохожими и представляем кодвекторами основного уровня, например bite_agt, bite_obj, flee_agt и т.д. Кодвекторы объектов (или экземпляров некоторого типа) сформированы как дизъюнктивная суперпозиция кодвекторов двух видов атрибутов: типа (human, dog, cat, mouse) и идентификатора или имени (id_john, id_fido, и т.д.). Например, объекты Джон и Морт представляем соответственно как john = 〈human ∨ id_john〉, mort = 〈mouse ∨ id_mort〉. Таким образом имитиру- ется разная степень сходства объектов. 3.2. Эксперименты по поиску аналогов. Данные экспериментов [9, 29, 30] по поиску аналогов людьми свидетельствуют о том, что сходство объектов более важ- но, чем сходство структур. В терминах рассмотренных выше раз- ных типов сходства аналогов это означает, что аналоги типа LS, CM, SF находятся людьми легче, чем аналоги со сходством типа AN и FOR. Среди группы эпизодов со сходством объектов эпизод LS на- ходят легче, чем CM и SF. На ос- нове анализа данных разных авто- ров в [13] приводится следующий порядок извлечения людьми анало- гов из долговременной памяти: LS > CM ≥ SF >AN ≥ FOR. Таблица 3. Эпизоды-аналоги с различными типами сходства с пробным эпизодом Тип сходства Эпизод Пробный эпизод P Спот укусил Джейн ⇒ Джейн убежала от Спота Буквальное сходство LS Фидо укусил Джона ⇒ Джон убежал от Фидо Поверхностные призна- ки SF Джон убежал от Фидо ⇒ Фидо укусил Джона Перекрестная аналогия CM Фред укусил Ровера ⇒ Ровер убежал от Фреда Аналогия AN Морт укусил Феликса ⇒ Феликс убежал от Морта Отношения 1-го поряд- убежал Інформаційні системи 49 Для создания кодвекторов эпизодов использовалась как схе- ма "роль – заполнитель" (разд. 2.4.1), так и позиционная схема (разд. 2.4.1). Для схемы "роль – заполнитель" кодвекторы уровня 1 и более высоких уровней прорежи- вались до 2M. Эта "глубина про- реживания" была выбрана опытным путем, чтобы получить величины сходств между кодвекторами проба и каждого эпизода, представлен- ные в столбце «role-filler» табл. 4. Для позиционной схемы код- векторы уровней 1 и 2 прорежива- лись до 4M. Величины сходства для этой глубины прореживания даны в столбце «positional» табл. 4. Величины сходства для другого типа распределенных представлений (HRR из [13] даны в первом столбце. Результаты ус- реднены по 100 реализациям слу- чайных кодвекторов нижнего уров- ня. Порядок величин сходства для обоих рассмотренных типов представлений АПНС тот же, что и для схемы HRR [13]. Это также соответствует порядку экспери- ментальных результатов, получен- ному для людей [9, 29, 30] и ре- зультатам моделирования, приводимого для MAC/FAC [9] и ARCS [10], где использовались другие эпизоды, но с тем же ти- пом сходства. Выводы При исследовании многих предметных областей существенной является структура объектов и их описаний. Это подтверждается как данными исследований психологов, изучающих сложные когнитивные процессы, такие, как процессы рассуждения по аналогии, так и работами исследователей, зани- мающихся исследованием свойств разного рода сложноструктуриро- ванных объектов [31], от химиче- ских соединений [32] до военно- политических кризисов [33]. По- этому сходство описаний таких объектов должно учитывать сход- ство как компонентов ("семанти- ческое сходство"), так и отноше- ний, существующих между ними ("структурное сходство"). Как показано в данной статье и в ра- ботах других исследователей, мо- гут быть созданы распределенные представления структур, которые несут непосредственную инфор- мацию о наборе структурных ком- понентов различных иерархических Таблица 4. Величины сходства между кодвекторами, представляющими проб и эпизоды в памяти Величина сход- ства HRRs АПНС АПНС Тип сходст- ва Эпизод role- fille r role- fille r posi- tiona l P Спот укусил Джейн ⇒ Джейн убежала от Спот 1.00 1.00 1.00 LS Фидо укусил Джона ⇒ Джон убежал от Фидо 0.71 0.42 0.40 SF Джон убежал от Фидо ⇒ Фидо укусил Джона 0.47 0.38 0.24 CM Фред укусил Ровера ⇒ Ровер убежал от Фреда 0.47 0.38 0.30 AN Морт укусил Феликса ⇒ Феликс убежал от Морт 0.42 0.26 0.14 Інформаційні системи 50 уровней и об их структурной ор- ганизации. В отличие от локальных или символьных представлений такие распределенные представления обеспечивают более адекватный учет семантического содержания, гибкость и способность справить- ся с зашумленной и неожиданной входной информацией. Они позво- ляют естественно представлять и вычислять меру градуального сходства, более надежны и нейро- биологически релевантны. Такие представления позволяют строить "на лету", без предварительного обучения, кодвекторы одинаковой размерности для иерархических структур разной сложности и оце- нивать их сходство скалярным произведением. АПНС являются примером ар- хитектуры, объединяющей подходы и технологии, развитые в области искусственного интеллекта, на нейросетевой основе. Их исполь- зование может рассматриваться как комбинация символьной и об- разной обработки информации. Ал- горитмы допускают массивно- параллельную реализацию и позво- ляют использовать эффективные версии распределенной ассоциа- тивной памяти. Поиск аналогов с помощью АПНС демонстрирует способность полностью распределенного подхо- да (без локальных или символьных подсистем) работать со сложно- структурированными данными. Пер- спективы дальнейших исследований состоят в использовании данного подхода при решении задач искус- ственного интеллекта и информа- тики, таких как представление и поиск информации в базах знаний [33, 34]. На его основе может моделироваться познавательная деятельность людей, в частности, рассуждения по аналогии [1, 4, 5]. Авторы выражают благодар- ность за обсуждения Л.М. Касат- киной и анонимному рецензенту за ценные замечания и комментарии. 1. Gentner D. Structure-mapping: A theoretical framework for analogy // Cognitive Science. — 1983. — № 7. — P. 155 — 170. 2. Hummel J.E., Holyoak K.J. Distributed representations of structure: A theory of analogical access and mapping // Psychological Review. — 1997. — 104, № 3. — P. 427 — 466. 3. Gentner, D. and Markman, A.B. Analogy-Based Reasoning // Arbib M.A. //.Handbook of brain theory and neural networks. — Cambridge, MA: MIT Press, 1995. — P. 91–93. 4. Амосов Н.М. Моделирование мышления и психики. — Киев: Наук. думка, 1965. — 304 с. 5. Гладун В.П. Партнерство с компьюте- ром: Человеко-машинные целеустрем- ленные системы. — Port-Royal, 2000. — 128 с. 6. Kanerva P. Dual role of analogy in the design of a cognitive computer / Holyoak K., Gentner D., Kokinov B. //Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences. Sofia, Bulgaria: New Bulgarian University, 1998. — P. 164– 170. 7. Gentner D., Markman A.B. Structure Mapping in Analogy and Similarity // American Psychologist. — 1997. — 52, № 1. — P. 45–56. 8. Eliasmith C., Thagard P. Integrating Structure and Meaning: A Distributed Model of Analogical Mapping // Cognitive Science. — 2001. — 2, № 25. — P. 245–286. 9. Forbus K.D., Gentner D., Law K. MAC/FAC: A model of similarity- based retrieval. // Ibid. — 1995. — 19, № 2. — P. 141–205. 10. Analog Retrieval by Constraint Sat- isfaction / P. Thagard, K. Holyoak, G. Nelson, D. Gochfeld // Artificial Intelligence. — 1990. — № 46. — P. 259–310. 11. Falkenhainer B., Forbus K., Gentner D. The Structure-Mapping Engine: Algorithm and Examples // Artificial Intelligence. — 1989. — № 41. — P. 1–63. 12. Rachkovskij D.A. Some approaches to analogical mapping with structure sensitive distributed representations // J. of Experimental and Theoretical Інформаційні системи 51 Artificial Intelligence. — 2004. — 16, № 3. — P. 125–145. 13. Plate T. Analogical Retrieval and Processing with Distributed Vector Representations // Expert Systems: The Intern. J. of Knowledge Engineering and Neural Networks. — 2000. — № 17(1). — P. 29–40. 14. Rachkovskij D.A. Representation and Processing of Structures with Binary Sparse Distributed Codes // IEEE Transactions on Knowledge and Data Engineering. — 2001. — 2, № 13. — P. 261–276. 15. Thorpe, S. Localized Versus Distributed Representations / Arbib M. // The Handbook of Brain Theory and Neural Networks. — Cambridge, MA: MIT Press, 2003. — P. 643–646. 16. Rachkovskij D.A., Kussul E.M. Binding and Normalization of Binary Sparse Distributed Representations by Context-Dependent Thinning // Neural Computation. — 2001. — 2, № 13. — P. 411–452. 17. Frasconi P., Gori M., Sperduti A. A general framework for adaptive processing of data structures. // IEEE Transactions on Neural Networks. — 1998. — 9, № 5. — P. 768–786. 18. Quillian M. Semantic memory // Minsky M. Semantic information processing. — Cambridge, Mass.: MIT Press, 1968. — P. 227–270. 19. M-network as possible basis for construction of heuristic models / N. Amosov, E. Basilevsky, A. Kasatkin, L. Kasatkina, A. Luk, E. Kussul, S. Talayev // Cybernetica. — 1972. — № 3. — P. 169–186. 20. Rangarajan A., Mjolsness E. Lagrangian Relaxation Network for Graph Matching // IEEE Transactions on Neural Networks. — 1996. — № 7(6). — P. 4629–4634. 21. Jain B.J., Wysotski F. A Novel Neural Network Approach to Solve Exact and Inexact Graph Isomorphism Problems. // Proccedings ICANN/ICONIP 2003. — Istambul, Turkey: 2003. — P. 299–306. 22. Finch A.M., Wilson R.C., Hancock E.R. Symbolic Graph Matching with the EM Algorithm // Pattern Recognition. — 1998. — 31, — P. 1777–1790. 23. Markman A.B., Gentner D. Structure mapping in the comparison process // American Journal of Psychology. — 2000. — 113, № 4. — P. 501–538. 24. Plate T. Holographic Reduced Representation: Distributed Representation for Cognitive Structures. — Chicago: Center for the Study of Language and Information, 2003. — 250 p. 25. Kanerva P. Binary Spatter-Coding of Ordered K-tuples // Intern. Conf. on Artificial Neural Networks ICANN'96. — Bochum, Germany: Berlin: Springer, 1996. — P. 869– 873. 26. Rachkovskij D.A., Kussul E.M. Binding and Normalization of Binary Sparse Distributed Representations by Context-Dependent Thinning // Neural Computation. — 13, №2 — P. 411–452. 27. Willshaw D.J., Buneman O.P., Longuet-Higgins H.C. Non- holographic associative memory // Nature. — 1969. — № 222. — P. 960–962. 28. Frolov A.A., Rachkovskij D.A., Husek D. On Information Characteristics of Willshaw-Like Auto-Associative Memory // Neural Network World. — 2002. — №2, — P. 141–157. 29. Ross B.H. Distinguishing types of superficial similarities: Different effects on the access and use of earlier examples — 1989. — 15, № 3. — P. 456–468. 30. Wharton C.M., Holyoak K.J., Downing P.E., Lange T.E., Wickens T.D., Melz E.R. Below the surface: Analogical similarity and retrieval competition in reminding — 1994. — 26, № 1. — P. 64–101. 31. Вывод гипотез о составе и свойствах объектов на основе аналогии / В.П. Гладун, В.Ю. Величко, Н.Н. Киселе- ва, Н.М. Москалькова // Искусствен- ный интеллект — 2000, №1. — С. 44– 52. 32. Величко В.Ю., Москалькова Н.М. Ис- пользование программного комплекса "Аналогия" для формирования гипотез о свойствах составных объектов // Пробл. программирования. — 2002. — №1–2. — С. 445–452. 33. The DARPA High-Performance Knowledge Bases Project / P. Cohen, R. Schrag, E. Jones, A. Pease, A. Lin, B. Starr, D. Gunning, M. Burke // AI Magazine. — 1998. — 19, № 4. — P. 25–49. 34. Forbus K.D. Exploring Analogy in the Large // Gentner D., Holyoak K., Kokinov B. //Analogy: Perspectives from Cognitive Science. — Cambridge, MA: The MIT Press, 2000. — P. 23–58. Інформаційні системи 52 Получено 24.11.04 Об авторах Рачковский Дмитрий Андреевич, канд. техн. наук, ст. науч. сотр. Мисуно Иван Семенович, вед. инж.-программист Слипченко Сергей Витальевич, вед. инж.-программист Соколов Артем Михайлович, мл. науч. сотр. Место работы авторов: Международный научно-учебной центр ин- формационных технологий и систем НАН Украины и МОН Украины просп. Акад. Глушкова, 40, Киев, Ук- раина Тел. 266 4119 E-mail: dar@infrm.kiev.ua qdamage@longbow.kiev.ua slipchenko_serg@ukr.net sokolov@ukr.net
id nasplib_isofts_kiev_ua-123456789-1369
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1727-4907
language Russian
last_indexed 2025-11-29T12:03:50Z
publishDate 2005
publisher Інститут програмних систем НАН України
record_format dspace
spelling Рачковский, Д.А.
Мисуно, И.С.
Слипченко, С.В.
Соколов, А.М.
2008-07-28T18:51:45Z
2008-07-28T18:51:45Z
2005
Поиск аналогов с помощью распределенных представлений / Д.А. Рачковский, И.С. Мисуно, С.В. Слипченко, А.М. Соколов // Проблеми програмування. — 2005. — N 1. — С. 39–50. — Бібліогр.: 34 назв. — рос.
1727-4907
https://nasplib.isofts.kiev.ua/handle/123456789/1369
004.82 + 004.838.3
Рассматриваются модели первой стадии рассуждений по аналогии: поиск в памяти аналога некоторой ситуации. Ситуации и аналоги иерархически структурированы и могут включать отношения высших порядков, что усложняет поиск при использовании традиционных подходов. Приводятся схемы распределенного представления аналогов в виде многомерных бинарных векторов. Показано, что степень сходства ситуаций можно оценить по величине скалярного произведения представляющих их векторов. Это создает основу для моделирования процессов поиска аналогов людьми и для более эффективного поиска в базах знаний.
Розглядаються моделі першої стадії міркувань за аналогією: пошук у пам’яті аналогів деякої ситуації. Ситуації та аналоги ієрархічно структуровані і можуть включати відношення вищих порядків, що ускладнює пошук за умов використання традиційних підходів. Наводяться схеми розподіленого представлення аналогів у вигляді багатовимірних бінарних векторів. Показано, що ступінь схожості ситуацій можна відобразити за допомогою величини скалярного добутку векторів, які їх представляють. Це створює підґрунтя для моделювання процесів пошуку аналогів людьми та для більш ефективного пошуку у базах знань.
Models of the first stage in analogical reasoning, analogical access, are considered. Schemes for distributed representations of hierarchically structured episodes as multidimensional binary vectors are presented. Such schemes reflect similarity of analogical episodes by the scalar product of vectors representing them. This simplifies searching for the most similar analogs and allows modeling of preferences demonstrated by humans in analogical access tasks.
ru
Інститут програмних систем НАН України
Інформаційні системи
Поиск аналогов с помощью распределенных представлений
Пошук аналогів за допомогою розподілених представлень
Analogical Access with Distributed Representations
Article
published earlier
spellingShingle Поиск аналогов с помощью распределенных представлений
Рачковский, Д.А.
Мисуно, И.С.
Слипченко, С.В.
Соколов, А.М.
Інформаційні системи
title Поиск аналогов с помощью распределенных представлений
title_alt Пошук аналогів за допомогою розподілених представлень
Analogical Access with Distributed Representations
title_full Поиск аналогов с помощью распределенных представлений
title_fullStr Поиск аналогов с помощью распределенных представлений
title_full_unstemmed Поиск аналогов с помощью распределенных представлений
title_short Поиск аналогов с помощью распределенных представлений
title_sort поиск аналогов с помощью распределенных представлений
topic Інформаційні системи
topic_facet Інформаційні системи
url https://nasplib.isofts.kiev.ua/handle/123456789/1369
work_keys_str_mv AT račkovskiida poiskanalogovspomoŝʹûraspredelennyhpredstavlenii
AT misunois poiskanalogovspomoŝʹûraspredelennyhpredstavlenii
AT slipčenkosv poiskanalogovspomoŝʹûraspredelennyhpredstavlenii
AT sokolovam poiskanalogovspomoŝʹûraspredelennyhpredstavlenii
AT račkovskiida pošukanalogívzadopomogoûrozpodílenihpredstavlenʹ
AT misunois pošukanalogívzadopomogoûrozpodílenihpredstavlenʹ
AT slipčenkosv pošukanalogívzadopomogoûrozpodílenihpredstavlenʹ
AT sokolovam pošukanalogívzadopomogoûrozpodílenihpredstavlenʹ
AT račkovskiida analogicalaccesswithdistributedrepresentations
AT misunois analogicalaccesswithdistributedrepresentations
AT slipčenkosv analogicalaccesswithdistributedrepresentations
AT sokolovam analogicalaccesswithdistributedrepresentations

Ähnliche Einträge