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

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

По состоянию на 1990 год его использовали более 40 проектов [Falkenhainer, 2005]. Р.М. Френч сказал, что теория структурных отображений «несомненно, самая влиятельная работа на сегодняшний день в области моделирования построения аналогий» [2002].[нужна цитата ]

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

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

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

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

Концепции в МСП

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

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

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

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

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

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

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

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

передача крутящего момента на входе второй шестерни (p1)

переключатель сигнала передачи div10 (p2)

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

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

передача крутящего момента (первичная шестерня) (вторая шестерня) (p3)

сигнал передачи (схема переключения) (схема div10) (p4)

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

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

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

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

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

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

передача крутящего момента (входная шестерня) (шестерня div10) (p5)

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

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

Балл структурной оценки

После того, как гипотезы совпадения сгенерированы, 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. МСП должно гарантировать, что любые создаваемые им пробелы структурно согласованы; Другими словами, они взаимно однозначны - так что ни один источник не отображается на несколько целей и ни одна цель не отображается на несколько источников. У gmap также должна быть поддержка, а это означает, что если в gmap есть гипотеза совпадения, то также и гипотеза совпадения, которая включает исходный и целевой элементы.

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

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

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

Источник:

передача крутящего момента на входе второй шестерни (p1)

передать крутящий момент второй шестерне третьей передаче (p6)

Цель:переключатель сигнала передачи div10 (p2)

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

Gmap №1:

(МОМЕНТНЫЙ СИГНАЛ) (ПЕРЕКЛЮЧАТЕЛЬ ВХОДНОГО ПЕРЕДАЧИ) (ВТОРИЧНЫЙ ПЕРЕКЛЮЧАТЕЛЬ DIV10) (* ПЕРЕДАЧА-МОМЕНТ-ВХОД-ВТОРИЧНОЕ УСТРОЙСТВО * ПЕРЕДАЧА-СИГНАЛ-ПЕРЕКЛЮЧАТЕЛЬ-DIV10)

Gmap №2:

(МОМЕНТНЫЙ СИГНАЛ) (ПЕРЕКЛЮЧАТЕЛЬ ВТОРОЙ ШЕСТЕРНИ) (ТРЕТЬЕ ЗУБЧАТОЕ КОЛЕСО DIV10) (* ПЕРЕДАЧА-МОМЕНТ-ВТОРОЕ ЗНАЧЕНИЕ-ТРЕТЬЕ ПЕРЕДАЧА * ПЕРЕКЛЮЧАТЕЛЬ-СИГНАЛ-РАЗДЕЛ10)

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

Критика

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

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

Рекомендации

  1. ^ «Структурное отображение: вычислительная модель аналогии и подобия». Северо-Западный университет. Получено 2012-01-16.
  2. ^ Брайан Фалькенхайнер; Кеннет Д. Форбус; Дедре Джентнер (1989). «Механизм отображения структуры: алгоритм и примеры» (PDF). Искусственный интеллект. 41: 1–63. CiteSeerX  10.1.1.26.6432. Дои:10.1016/0004-3702(89)90077-5. Получено 2012-01-16.
  3. ^ Габора, Лиана (2015). «Как творческие идеи обретают форму». arXiv:1501.04406 [q-bio.NC ].

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