Механизм отображения структуры

В искусственном интеллекте и когнитивной науке механизм структурного отображения ( SME ) представляет собой программную реализацию алгоритма сопоставления аналогов, основанного на психологической теории Дедре Гентнера . В основе идеи Гентнера о структурном отображении лежит то, что аналогия — это отображение знаний из одной области (базы) в другую (цель). Механизм структурного отображения представляет собой компьютерное моделирование аналогий и сравнений сходства.

Теория полезна, потому что она игнорирует поверхностные особенности и находит совпадения между потенциально очень разными вещами, если они имеют одинаковую репрезентативную структуру. Например, МСП может определить, что ручка похожа на губку, поскольку обе они участвуют в выдаче жидкости, хотя делают это совершенно по-разному.

Теория структурного отображения

Теория структурного отображения основана на принципе систематичности, который гласит, что связанные знания предпочтительнее независимых фактов. Следовательно, механизм сопоставления структур должен игнорировать изолированные сопоставления источника и цели, если они не являются частью более крупной структуры. Согласно теории, МСП должно отображать объекты, связанные со знаниями, которые уже были картографированы.

Теория также требует, чтобы сопоставления выполнялись «один к одному» , что означает, что ни одна часть исходного описания не может быть сопоставлена ​​более чем с одним элементом целевого объекта, и никакая часть целевого описания не может быть сопоставлена ​​более чем с одной частью целевого объекта. источник. Теория также требует, чтобы, если совпадение отображает субъект на цель, аргументы субъекта и цели также должны быть сопоставлены. Если оба этих условия выполняются, отображение называется «структурно согласованным».

Концепции малого и среднего бизнеса

МСП отображает знания из источника в цель. SME называет каждое описание dgroup. Dgroups содержат список сущностей и предикатов . Сущности представляют объекты или концепции в описании, например, входной механизм или переключатель. Предикаты относятся к одному из трех типов и являются общим способом выражения знаний для малого и среднего бизнеса.

• Предикаты отношений содержат несколько аргументов, которые могут быть другими предикатами или сущностями. Пример отношения: (передавать (что от к)). Это отношение имеет функтор передачи и принимает три аргумента: что, откуда и куда.
• Предикаты атрибутов — это свойства сущности. Примером атрибута является (красная шестерня), что означает, что шестерня имеет атрибут красный.
• Предикаты функций отображают одну сущность в другую сущность или константу. Примером функции является ( источник энергии в джоулях объекта ), которая сопоставляет источник энергии с числовой величиной в джоулях.

Функции и атрибуты имеют разное значение, и, следовательно, SME обрабатывает их по-разному. Например, в наборе правил истинной аналогии SME атрибуты отличаются от функций, поскольку они не могут совпадать, если между ними нет соответствия более высокого порядка. Разница между атрибутами и функциями будет объяснена далее в примерах этого раздела.

Все предикаты имеют четыре параметра. У них есть (1) функтор, который идентифицирует их, и (2) тип, который может быть отношением, атрибутом или функцией. Два других параметра (3 и 4) предназначены для определения того, как обрабатывать аргументы в алгоритме SME . Если аргументы должны быть сопоставлены по порядку, коммутативный является ложным. Если предикат может принимать любое количество аргументов, N-арный является ложным. Пример определения предиката: (sme:defPredicate отношение набора поведения (предиката) :n-ary? t :commutative? t) Функтор предиката — «набор поведения», его тип — «отношение», а его n-арные и коммутативные параметры оба имеют значение true. Часть определения «(предикат)» указывает, что внутри экземпляра набора поведения будет один или несколько предикатов.

Детали алгоритма

Алгоритм состоит из нескольких шагов. Первым шагом алгоритма является создание набора гипотез соответствия между исходной и целевой dgroup. Гипотеза соответствия представляет собой возможное сопоставление между любой частью источника и цели. Это сопоставление контролируется набором правил сопоставления. Изменяя правила сопоставления, можно изменить тип рассуждений МСП. Например, один набор правил сопоставления может выполнять аналогию, называемую буквальным сходством, а другой — аналогию, называемую истинной аналогией. Эти правила — это не то место, где добавляется информация, зависящая от предметной области, а скорее то, где настраивается процесс аналогии в зависимости от типа когнитивной функции, которую пользователь пытается имитировать.

Для данного правила соответствия существует два типа правил, которые дополнительно определяют, как оно будет применяться: правила фильтрации и внутренние правила. Внутренние правила используют только аргументы выражений в гипотезах соответствия, которые идентифицируют правила фильтра. Это ограничение делает обработку более эффективной за счет ограничения количества гипотез генерируемых соответствия. В то же время это также помогает создать структурную согласованность, которая потребуется позже в алгоритме. Пример правила фильтра из набора правил истинной аналогии создает гипотезы соответствия между предикатами, имеющими одинаковый функтор. В наборе правил истинной аналогии есть внутреннее правило, которое перебирает аргументы любой гипотезы соответствия, создавая больше гипотез соответствия, если аргументы являются сущностями или функциями или если аргументы являются атрибутами и имеют один и тот же функтор.

Чтобы проиллюстрировать, как правила соответствия создают гипотезы соответствия, рассмотрим эти два предиката:

transmit torque inputgear secondgear (p1)

transmit signal switch div10 (p2)

Здесь мы используем истинную аналогию для типа рассуждения. Правило сопоставления фильтра генерирует совпадение между p1 и p2, поскольку они используют один и тот же функтор — передачу. Затем внутренние правила создают еще три гипотезы соответствия: крутящий момент для сигнала, входной механизм для переключения и второй механизм для div10. Внутренние правила создали эти гипотезы соответствия, поскольку все аргументы были сущностями.

Если бы аргументами были функции или атрибуты, а не сущности, предикаты были бы выражены как:

transmit torque (inputgear gear) (secondgear gear) (p3)

transmit signal (switch circuit) (div10 circuit) (p4)

Эти дополнительные предикаты создают функции или атрибуты inputgear, Secondgear, Switch и div10 в зависимости от значения, определенного во входном языковом файле. Представление также содержит дополнительные объекты для механизма и цепи.

В зависимости от типа входного устройства, второго устройства, переключателя и div10 их значения меняются. В качестве атрибутов каждый из них является свойством механизма или схемы. Например, у шестерни есть два атрибута: входная передача и вторая передача. Схема имеет два атрибута: переключатель и цепь. В качестве функций inputgear, Secondgear, Switch и div10 становятся величинами шестерни и цепи. В этом примере функции inputgear и Secondgear теперь сопоставляются с числовыми величинами «крутящий момент от входного устройства» и «крутящий момент от второго устройства». на 10 счетчиков».

МСП обрабатывает их по-разному. Он не позволяет сопоставлять атрибуты, если они не являются частью отношения более высокого порядка, но позволяет сопоставлять функции, даже если они не являются частью такого отношения. Это позволяет функциям сопоставляться, поскольку они косвенно ссылаются на сущности и, следовательно, их следует рассматривать как отношения, не включающие сущности. Однако, как показано в следующем разделе, правила intern присваивают меньшие веса совпадениям между функциями, чем совпадениям между отношениями.

Причина, по которой МСП не сопоставляет атрибуты, заключается в том, что они пытаются создать связанные знания на основе отношений и, таким образом, удовлетворить принципу систематичности. Например, если и часы, и автомобиль имеют атрибуты входного устройства, SME не пометит их как похожие. Если бы это было так, то совпадение между часами и автомобилем было бы основано на их внешнем виде, а не на отношениях между ними.

Когда дополнительные предикаты в p3 и p4 являются функциями, результаты сопоставления p3 и p4 аналогичны результатам p1 и p2, за исключением того, что имеется дополнительное соответствие между механизмом и схемой и значениями для гипотез соответствия между (входной механизм) и (цепь переключателя), а также (вторая передача) и (цепь div10) находятся ниже. В следующем разделе причина этого описывается более подробно.

Если inputgear, Secondgear, Switch и div10 являются атрибутами, а не объектами, SME не находит совпадений между какими-либо атрибутами. Он находит совпадения только между предикатами передачи, а также между крутящим моментом и сигналом. Кроме того, баллы структурной оценки для оставшихся двух совпадений снижаются. Чтобы обеспечить совпадение двух предикатов, необходимо заменить p3 на p5, как показано ниже.

transmit torque (inputgear gear) (div10 gear) (p5)

Поскольку набор правил истинной аналогии определяет, что атрибуты div10 одинаковы для p5 и p4, и поскольку оба атрибута div10 являются частью более высокого соответствия между крутящим моментом и сигналом, SME выполняет сопоставление между (div10 gear) и (div10 цепь) — что приводит к совпадению шестерни и цепи.

Участие в совпадении более высокого порядка является требованием только для атрибутов. Например, если (передача div10) и (схема div10) не являются частью совпадения более высокого порядка, SME не создает гипотезу соответствия между ними. Однако если div10 является функцией или отношением, SME создает совпадение.

Структурная оценка оценки

После того как гипотезы соответствия сформированы, МСП необходимо вычислить оценочную оценку для каждой гипотезы. SME делает это, используя набор правил сопоставления стажеров для расчета положительных и отрицательных доказательств для каждого совпадения. Множественные объемы свидетельств коррелируются с использованием правила Демпстера [Shafer, 1978], что приводит к положительным и отрицательным значениям убеждений от 0 до 1. Правила сопоставления присваивают разные значения совпадениям, включающим функции и отношения. Однако эти значения являются программируемыми, а некоторые значения по умолчанию, которые можно использовать для обеспечения соблюдения принципа систематичности, описаны в [Falkenhainer et al., 1989].

Эти правила:

1. Если источник и цель не являются функциями и имеют одинаковый порядок, соответствие получает +0,3 доказательства. Если ордера находятся в пределах 1 друг от друга, совпадение получает +0,2 доказательства и -0,05 доказательства.
2. Если источник и цель имеют один и тот же функтор, совпадение получает 0,2 доказательства, если источник является функцией, и 0,5, если источник является отношением.
3. Если аргументы совпадают, совпадение получает +0,4 доказательства. Аргументы могут совпадать, если все пары аргументов между источником и целью являются сущностями, если аргументы имеют одинаковые функторы или никогда не бывает случая, когда цель является сущностью, а источник — нет.
4. Если тип предиката совпадает, но элементы в предикате не совпадают, то совпадение получает доказательство -0,8.
5. Если исходное и целевое выражения являются частью совпадения более высокого порядка, добавьте 0,8 свидетельства для совпадения более высокого порядка.

В примере соответствия между p1 и p2 SME дает совпадению между отношениями передачи положительное значение доказательства 0,7900, а остальные получают значения 0,6320. Отношение передачи получает значение свидетельства 0,7900, поскольку оно получает свидетельство по правилам 1, 3 и 2. Остальные совпадения получают значение 0,6320, поскольку 0,8 свидетельства передачи распространяется на эти совпадения из-за правила 5.

Для предикатов p3 и p4 SME присваивает меньше свидетельств, поскольку аргументы отношений передачи являются функциями. Отношение передачи получает положительное свидетельство 0,65, поскольку правило 3 больше не добавляет свидетельств. Соответствие между (входным механизмом) и (схемой переключения) становится 0,7120. Это совпадение получает 0,4 свидетельства из-за правила 3 ​​и 0,52 свидетельства, распространяемого из отношения передачи из-за правила 5.

Когда предикаты в p3 и p4 являются атрибутами, правило 4 добавляет -0,8 свидетельства к совпадению передачи, потому что — хотя функторы отношения передачи совпадают — аргументы не имеют возможности совпадать и аргументы не являются функциями.

Подводя итог, можно сказать, что правила сопоставления стажеров вычисляют показатель структурной оценки для каждой гипотезы соответствия. Эти правила обеспечивают соблюдение принципа систематичности. Правило 5 предоставляет доказательства просачивания вниз для усиления совпадений, участвующих в отношениях более высокого порядка. Правила 1, 3 и 4 добавляют или исключают поддержку отношений, которые могут иметь совпадающие аргументы. Правило 2 добавляет поддержку случаев совпадения функторов. тем самым добавляя поддержку совпадений, которые подчеркивают отношения.

Правила также обеспечивают соблюдение различий между атрибутами, функциями и отношениями. Например, у них есть проверки, которые дают меньше доказательств для функций, чем для отношений. Атрибуты конкретно не рассматриваются в правилах внутреннего сопоставления, но правила фильтрации SME гарантируют, что они будут учитываться в этих правилах только в том случае, если они являются частью отношения более высокого порядка, а правило 2 гарантирует, что атрибуты будут совпадать только в том случае, если они имеют идентичные значения. функторы.

Создание Gmap

Остальная часть алгоритма SME участвует в создании максимально согласованных наборов гипотез соответствия. Эти наборы называются gmaps. МСП должно гарантировать, что любые создаваемые им gmaps являются структурно последовательными; другими словами, они взаимно однозначны, то есть ни один источник не сопоставляется с несколькими целевыми объектами, а ни один целевой объект не сопоставляется с несколькими источниками. Gmaps также должны иметь поддержку, а это означает, что если гипотеза соответствия присутствует в gmap, то так же есть и гипотеза соответствия, включающая исходные и целевые элементы.

Процесс создания gmap состоит из двух этапов. Во-первых, SME вычисляет информацию о каждой гипотезе соответствия, включая сопоставления сущностей, любые конфликты с другими гипотезами и другие гипотезы соответствия, с которыми она может быть структурно несовместима.

Затем МСП использует эту информацию для объединения гипотез соответствия — используя жадный алгоритм и оценку структурной оценки. Он объединяет гипотезы совпадения в максимально структурно последовательные связные графы гипотез совпадения. Затем он объединяет карты gmap, имеющие перекрывающуюся структуру, если они структурно согласованы. Наконец, он объединяет независимые gmap, сохраняя при этом структурную согласованность.

Сравнение источника с целевой группой dgroup может привести к созданию одной или нескольких карт gmap. Вес каждой карты gmap представляет собой сумму всех положительных значений доказательств для всех гипотез соответствия, включенных в gmap. Например, если источник, содержащий p1 и p6 ниже, сравнивается с целевым объектом, содержащим p2, SME сгенерирует две карты gmap. Обе карты имеют вес 2,9186.

Источник:

transmit torque inputgear secondgear (p1)

transmit torque secondgear thirdgear (p6)

Цель: transmit signal switch div10 (p2)

Это gmaps, полученные в результате сравнения источника, содержащего p1 и p6, и цели, содержащей p2.

Гмап №1:

(TORQUE SIGNAL)
(INPUTGEAR SWITCH)
(SECONDGEAR DIV10)
(*TRANSMIT-TORQUE-INPUTGEAR-SECONDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10)

Гмап №2 :

(TORQUE SIGNAL)
(SECONDGEAR SWITCH)
(THIRDGEAR DIV10)
(*TRANSMIT-TORQUE-SECONDGEAR-THIRDGEAR *TRANSMIT-SIGNAL-SWITCH-DIV10)

В gmaps отображаются пары совпадающих предикатов или сущностей. Например, в gmap № 1 объекты крутящего момента и сигнала совпадают, а поведения входной шестерни передачи крутящего момента второй передачи и переключателя сигнала передачи div10 совпадают. Gmap № 1 представляет собой объединение p1 и p2. Gmap № 2 представляет собой объединение p1 и p6. Хотя p2 совместим как с p1, так и с p6, ограничение сопоставления «один к одному» требует, чтобы оба сопоставления не могли находиться в одной и той же gmap. Таким образом, SME создает две независимые карты gmap. Кроме того, объединение двух gmaps вместе приведет к конфликту сопоставлений сущностей между Thirdgear и div10 с сопоставлением сущностей между SecondGear и div10.

Критика

Чалмерс, Френч и Хофштадтер [1992] критикуют МСП за то, что они полагаются на созданные вручную представления LISP в качестве входных данных. Они утверждают, что для создания таких представлений требуется слишком много человеческого творчества; информация исходит из структуры вводимых ресурсов, а не от малого и среднего бизнеса. Форбус и др. [1998] попытались опровергнуть эту критику. Моррисон и Дитрих [1995] попытались примирить две точки зрения. Терни [2008] представляет алгоритм, который не требует ввода LISP, но следует принципам теории структурного отображения. Терни [2008] заявляют, что их работа также не защищена от критики со стороны Чалмерса, Френча и Хофштадтера [1992].

В своей статье «Как обретают форму креативные идеи» Лиана Габора пишет: «Согласно отточенной теории творчества, творческая мысль работает не над индивидуально рассматриваемыми, дискретными, заранее определенными представлениями, а над контекстуально вызванной смесью предметов, которые существуют в состоянии потенциальности и не могут быть легко разделены. Это приводит к предсказание о том, что создание аналогий происходит не путем сопоставления соответствий между возможными источниками и целью, как предсказывает теория структурного отображения аналогии, а путем отсеивания несоответствий, тем самым сводя на нет потенциальность».

Дальнейшее чтение

• Статьи группы качественного рассуждения Северо-Западного университета
• Чалмерс, DJ, Френч, RM, и Хофштадтер, DR: 1992, Восприятие, представление и аналогия высокого уровня: критика методологии искусственного интеллекта . Журнал экспериментального и теоретического искусственного интеллекта , 4 (3), 185–211.
• Фалькенхайнер, Б: 2005, Реализация механизма структурного картирования. реализация малого и среднего бизнеса
• Фалькенхайнер Б., Форбус К. и Гентнер Д.: 1989, «Механизм отображения структур: алгоритм и примеры» . Искусственный интеллект, 20 (41): 1–63.
• Форбус К.Д., Гентнер Д., Маркман А.Б. и Фергюсон Р.В.: 1998, Аналогия просто выглядит как восприятие высокого уровня: почему общий подход к аналоговому картированию является правильным . Журнал экспериментального и теоретического искусственного интеллекта , 10 (2), 231–257.
• Френч, РМ: 2002. «Вычислительное моделирование создания аналогий» . Тенденции в когнитивных науках, 6 (5), 200–205.
• Гентнер, Д.: 1983, «Отображение структуры: теоретическая основа аналогии» , Cognitive Science 7 (2)
• Шафер, Дж .: 1978, Математическая теория доказательств , Издательство Принстонского университета, Принстон, Нью-Джерси. ISBN   0-691-08175-1 .
• Моррисон, Коннектикут, и Дитрих, Э.: 1995, Структурное картирование против восприятия высокого уровня: ошибочная борьба за объяснение аналогии . Труды семнадцатой ежегодной конференции Общества когнитивных наук, 678–682.
• Терни, П.Д.: 2008, Механизм отображения скрытых отношений: алгоритм и эксперименты , Журнал исследований искусственного интеллекта (JAIR), 33, 615–655.