Analogical proportions II

類比比例 II

https://arxiv.org/abs/2405.13461

摘要
類比推理是指識(shí)別兩個(gè)看似遙遠(yuǎn)的對(duì)象或情境之間的相似性，這是一種基本的人類能力，廣泛應(yīng)用于常識(shí)推理、學(xué)習(xí)和創(chuàng)造力中。許多研究者認(rèn)為它是人類智能和人工智能的核心組成部分。類比比例（analogical proportions）是形如“a 之于 b 猶如 c 之于 d”的表達(dá)式，是類比推理的核心。作者最近在泛代數(shù)（universal algebra）的一般框架下引入了一個(gè)抽象的代數(shù)類比比例理論。本文的目的在于進(jìn)一步發(fā)展這一框架下的數(shù)學(xué)理論，其動(dòng)機(jī)來自于該理論已經(jīng)在人工智能中的邏輯程序合成方面得到了成功應(yīng)用。

1. 引言

類比推理是一種識(shí)別兩個(gè)表面上看似遙遠(yuǎn)的對(duì)象或情境之間相似性的能力，這是人類的一項(xiàng)基本認(rèn)知能力，例如用于常識(shí)推理、學(xué)習(xí)和創(chuàng)造性思維。許多研究者認(rèn)為這種能力是人類與人工智能核心機(jī)制的重要組成部分（參見例如 Gentner, Holyoak, & Kokinov, 2001；Gentner, 2012；Gust, Krumnack, Kühnberger, & Schwering, 2008；Hofstadter & Sander, 2013；Krieger, 2003；Pólya, 1954）。著名的類比推理模型包括 Gentner (1983) 提出的結(jié)構(gòu)映射理論（SMT）及其在結(jié)構(gòu)映射引擎中的實(shí)現(xiàn)（Falkenhainer, Forbus, & Gentner, 1989），以及 Hofstadter 和 Mitchell (1995) 的 Copycat 算法。使用二階邏輯形式化的類似于 SMT 的模型還有啟發(fā)驅(qū)動(dòng)理論投影（heuristic-driven theory projection）（Gust, Kühnberger, & Schmid, 2006）。Winston (1980) 是一篇展示類比在學(xué)習(xí)中應(yīng)用的經(jīng)典論文。Baaz (2005) 利用 Gentzen 序列演算對(duì)法律中的類比推理進(jìn)行了形式化。關(guān)于類比推理的簡短且略顯過時(shí)的介紹，讀者可參考 Prade 和 Richard (2014)；關(guān)于類比推理模型的歷史回顧，可參見 Hall (1989)。

類比比例是類比推理的核心，其形式為：“a 之于 b 猶如 c 之于 d”，記作 a : b :: c : d。類比比例的正式模型直到最近才開始出現(xiàn)，最著名的是 Lepage (2001, 2003) 在語言學(xué)背景下的公理化方法，Miclet 和 Prade (2009) 在布爾兩值邏輯下的邏輯方法（參見 Prade & Richard, 2013, 2018），以及 Stroppa & Yvon (2006) 和 Gust 等人 (2006) 的代數(shù)方法。Barbot、Miclet 和 Prade (2019) 使用類比比例來形式化概念之間的類比關(guān)系。有關(guān)類比比例在人工智能中的應(yīng)用概述，請(qǐng)參見 Prade 和 Richard (2021)（另見 Correa、Prade 和 Richard, 2012）。

作者最近在泛代數(shù)（universal algebra）的通用框架下提出了一種抽象的代數(shù)類比比例理論（Anti?, 2022）。該理論本質(zhì)上是基于解釋的（justification-based），因此屬于新興的可解釋人工智能（Explainable AI）領(lǐng)域（參見 Héder, 2023）。本文旨在通過進(jìn)一步發(fā)展該框架下的數(shù)學(xué)理論，為類比推理的數(shù)學(xué)基礎(chǔ)做出貢獻(xiàn)。這一研究的動(dòng)因之一是該理論已成功應(yīng)用于自動(dòng)編程與人工智能中的邏輯程序合成（Anti?, 2023c）；另一個(gè)原因是它能夠在一個(gè)統(tǒng)一的框架中捕捉 Klein (1982) 和 Miclet & Prade (2009) 分別提出的兩種布爾比例建模方式（Anti?, 2024）。關(guān)于該框架在單一運(yùn)算代數(shù)（monounary algebras）中的分析，請(qǐng)參見 Anti? (2023b)。

具體而言，在 §3 中我們首先觀察到：一組解釋（justifications）構(gòu)成主濾子（principal filter），這促使我們采用一種特殊的符號(hào)表示方式。接著我們引入一些術(shù)語，使得 Anti? (2022) 中的唯一性引理（Uniqueness Lemma）和函數(shù)比例定理（Functional Proportion Theorem）——這些是該框架的基本支柱——更易于理解。

在 §4 中，我們證明了一個(gè)同態(tài)定理（Homomorphism Theorem），作為 Anti? (2022) 中第一同構(gòu)定理的推廣，表明箭頭比例（arrow proportions）——即形如 a → b : · c → d 的表達(dá)式（讀作“a 轉(zhuǎn)變?yōu)?b 正如 c 轉(zhuǎn)變?yōu)?d”，見 §2）——與同態(tài)保持一致。

在 §5 中，我們開始研究該框架中對(duì)解釋形式進(jìn)行語法限制的片段。特別是，在 §5.1–5.2 中我們展示了即使在最簡單的單線性片段（monolinear fragment）中——即只允許最多一個(gè)變量出現(xiàn)一次的解釋——也能捕捉差分比例和幾何比例。這意味著 Stroppa 和 Yvon (2006) 所提出的算術(shù)比例概念實(shí)際上等價(jià)于我們框架中的單線性算術(shù)比例，因此過于局限，不能被視為算術(shù)比例的標(biāo)準(zhǔn)定義。此外，在 §5.3 中我們研究了單詞之間的單線性比例。

單詞之間的類比比例在計(jì)算語言學(xué)和自然語言處理中已有應(yīng)用，并被多位學(xué)者在該背景下研究過（例如 Hofstadter & Mitchell, 1995；Lepage, 2001, 2003；Lim, Prade, & Richard, 2021；Stroppa & Yvon, 2006）。因此在 §6 中，我們研究單詞比例，并在定理 43 和例 44 中說明：在單詞域中解釋我們的框架，可以嚴(yán)格地推廣 Stroppa 和 Yvon (2006) 中常用的單詞比例概念。這一點(diǎn)尤其有趣，因?yàn)槲覀兊目蚣懿⒎菍ｉT為單詞域設(shè)計(jì)。

樹結(jié)構(gòu)常用于計(jì)算語言學(xué)和自然語言處理中，用來表示復(fù)雜詞語和句子的內(nèi)部結(jié)構(gòu)，也用于一階謂詞中語言實(shí)體語義的表示（例如參見 Stroppa & Yvon, 2006 的 §2.2）。因此在 §7 中我們研究樹之間的比例，并證明經(jīng)典語法反合一（anti-unification）技術(shù)（Reynolds, 1970；Plotkin, 1970；Huet, 1976）可以通過簡單的語法檢查來計(jì)算樹比例（定理 51）。

受上述觀察啟發(fā)，在 §8 中我們進(jìn)一步指出：作者最近在泛代數(shù)框架下提出的代數(shù)反合一（algebraic anti-unification）理論（Anti?, 2023a）與類比比例存在聯(lián)系，并通過示例 54 進(jìn)行說明。需要指出的是，其他學(xué)者此前也在不同框架中注意到類比比例與反合一之間的關(guān)聯(lián)：Krumnack 等人 (2007) 研究了受限高階反合一與類比生成的關(guān)系；Weller 和 Schmid (2007) 則利用反合一通過正則樹文法來計(jì)算類比比例。

最后，在 §9 中我們展示了在有限代數(shù)中如何使用樹自動(dòng)機(jī)（tree automata）來計(jì)算類比比例，并提供了若干最重要計(jì)算任務(wù)的算法。

2. 預(yù)備知識(shí)

本節(jié)回顧了 Anti? (2022) 中提出的類比比例的抽象代數(shù)框架。我們假設(shè)讀者已熟悉泛代數(shù)的基本概念，相關(guān)內(nèi)容可參見 Burris 和 Sankappanavar (2000, 第II章)。

3. 解釋（Justifications）

在本節(jié)中，我們觀察到：解釋的集合是主濾子（principal filters） ，這一發(fā)現(xiàn)將促使我們改變符號(hào)表示方式，用 ↑ 取代 Jus，從而在語法上更恰當(dāng)?shù)乇磉_(dá)其與“泛化”之間的緊密聯(lián)系。

回想一下，在一個(gè)預(yù)序集 (P,≤)上，一個(gè) 濾子（filter）F 是 P的一個(gè)子集，滿足以下條件：

1. F 非空

   （即 F=? ）；

2. F 是向下有向的（downward directed）

   ，即對(duì)任意 a,b∈F ，存在某個(gè) c∈F ，使得 c≤a 且 c≤b ；

3. F 是上集（upper set），或稱向上閉合

   ，即對(duì)任意 a∈F 和 b∈P ，如果 a≤b ，則 b∈F 。

包含某個(gè)元素 a的最小濾子 稱為由 a生成的主濾子（principal filter） ，而 a被稱為主元素（principal element）——它定義為：

6. 單詞比例（Word Proportions）

在第 §5.3 節(jié)中，我們研究了單線性片段 中的單詞比例，其中解釋（justifications）最多包含一個(gè)變量的一次出現(xiàn)。本節(jié)則在完整的框架 下研究單詞比例。

具體而言，在定理 43 和例 44 中我們證明：我們的框架嚴(yán)格地涵蓋了 Stroppa 和 Yvon (2006) 所提出的單詞比例概念。

在本節(jié)中，我們將在字代數(shù)（word algebra） (A?, ·, A?) 中進(jìn)行討論，其中 · 表示連接運(yùn)算 （通常省略不寫），而 A 是一個(gè)非空有限字母表 。為方便閱讀，我們?cè)跀⑹鲋谐３Ｊ÷詫?duì)字代數(shù)的顯式引用。

記號(hào) 37 ：在其他章節(jié)中，我們使用粗體字母 表示元素序列 。
而在本節(jié)中，我們將使用粗體字母 表示單詞 （即字母的序列），并使用向量符號(hào) 來表示單詞的序列 。

7. 樹的比例（Tree Proportions）

在本節(jié)中，我們?cè)?strong>自由項(xiàng)代數(shù) TL,X中研究樹之間的類比比例，稱為樹比例 （tree proportions）（參見 §2）。

以下是一個(gè)簡單的觀察結(jié)果，突出了樹結(jié)構(gòu)設(shè)置的一個(gè)特殊性質(zhì)：

事實(shí) 45 ：
在項(xiàng)代數(shù)中，每個(gè)項(xiàng)函數(shù)都是單射的 ，因此每一個(gè)解釋（justification）都是一個(gè)特征解釋 （characteristic justification）。

8. 反合一（Anti-unification）

在上一節(jié)中，我們看到經(jīng)典的語法反合一 （syntactic anti-unification）可以用于計(jì)算樹比例 。受這一結(jié)果的啟發(fā)，我們?cè)诒竟?jié)中開始研究類比比例與反合一之間的相互關(guān)系 ，且不僅限于自由項(xiàng)代數(shù)的范圍。

為此，我們需要一個(gè)將反合一從項(xiàng)推廣到任意代數(shù)的概念。這一概念最近由作者提出（Anti?, 2023a），下面我們簡要回顧該理論的核心思想：

10. 結(jié)論

本文旨在擴(kuò)展作者最近在泛代數(shù)（universal algebra）框架下提出的類比比例的抽象代數(shù)理論 的數(shù)學(xué)基礎(chǔ)。

接下來，我們將討論一些可能的未來研究方向。

第 §5 節(jié)引入了 (k, ?)-片段（fragments） ，并在 §5.1 – §5.3 中研究了在數(shù)字和單詞 背景下的單線性 (1, 1)-片段 。而對(duì)于集合結(jié)構(gòu) 來說，單線性片段更具挑戰(zhàn)性，因?yàn)椴⒓c交集運(yùn)算是高度非單射的。

下一步是研究線性片段 (∞, 1) —— 即由最多出現(xiàn)一次的任意多個(gè)變量構(gòu)成的解釋——針對(duì)數(shù)字、單詞和集合進(jìn)行研究。從理論角度來看，分析不同此類片段之間的關(guān)系是非常有趣的，因?yàn)槲覀兛赡軙?huì)得到一個(gè)具有遞增表達(dá)能力的 (k, ?)-層次結(jié)構(gòu) 。

在 §6 中，我們對(duì)單詞比例 進(jìn)行了初步的部分結(jié)果研究，并在定理 43 中證明：一種重要的單詞比例概念被我們的框架所涵蓋。然而，要像定理 30 在單線性片段中那樣，對(duì)整個(gè)單詞比例關(guān)系進(jìn)行完整刻畫 ，仍然是一個(gè)具有挑戰(zhàn)性的、且在實(shí)踐中意義重大的開放問題。

無限樹自然地出現(xiàn)在程序設(shè)計(jì)語言的研究中（參見例如 Courcelle, 1983）。因此，將 §7 中的概念和結(jié)果推廣到無限樹之間的樹比例 是一個(gè)有趣的方向。

第 §9 節(jié)中關(guān)于有限代數(shù)中的類比比例的算法，局限于k-片段 ，即解釋中最多包含 k 個(gè)不同變量，因而變量數(shù)量是有界的。這種限制對(duì)于應(yīng)用樹自動(dòng)機(jī)理論 的技術(shù)是必要的。

將這些算法推廣至解釋中變量數(shù)量無界 的完整框架，是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。更進(jìn)一步，一個(gè)更具挑戰(zhàn)性的課題是尋找適用于超越有限代數(shù) 的類比比例計(jì)算算法，尤其重要的是在諸如自動(dòng)結(jié)構(gòu) （automatic structures）這類可有限表示的代數(shù) （如 Blumensath & Gr?del, 2000, 2004）中的算法設(shè)計(jì)。

原文鏈接：https://arxiv.org/abs/2405.13461