TT-Entails Python代码实现

TT-Entails Python代码实现

• 0 前言
• 1 算法目标
• 2 算法总体思路
• 3 构建KB与 α \alpha α
• • （1）class LogicalExpression
  • （2）function toRPN
  • （3）function RPN2Tree
• 4 枚举真值表
• • 4.1 伪代码
  • 4.2 思路解释
  • • 4.2.1 总体思路
    • 4.2.2 模块解释
    • 4.2.3 各模块代码实现
• 5 测试

0 前言

• 最近选修了人工智能课程，在Knowledge and Reasoning这一章中，感觉TT-Entails这个算法不是很好理解，搞了半天总算弄得比较明白了，趁机用Python试着自己实现了一下，完整代码已经上传GitHub。
• 另外，这个PPT讲得非常清楚，跟着他的思路也会比较容易理解。
• 如果只想知道算法思路，可以直接跳转到“4 枚举真值表”
• 非专业人士，难免有所疏漏，还请大佬批评指正 😄

1 算法目标

• 输入：Knowledge Base(KB) 和 α \alpha α（目标结论）。KB和 α \alpha α都遵从BNF语法规则
• 输出：KB是否蕴含 α \alpha α
• KB， α \alpha α的严格定义不展开了。蕴含（entailment）的大致意思是使KB为真的model一定使 α \alpha α为真，即 K B ′ + α KB'+\alpha KB′+α
• 一句话：能否从已有的知识储备（KB，包括已知的规则和观察结果）推断出目标结论（ α \alpha α）

2 算法总体思路

1. 读取KB与 α \alpha α
2. 提取其中的所有变量
3. 通过枚举构造真值表（TT就表示Truth Table）
4. 寻找反例（存在某一种真值组合使KB为真而 α \alpha α为假，则为假）

3 构建KB与 α \alpha α

为了方便输入，从txt中读入KB和 α \alpha α，每一行为一句BNF语句，每个句子包括若干tokens，其两两之间用空格（tab）隔开。
token包括两类：connective和symbol。symbol即变量，connective是逻辑运算符，包括左括号，右括号，and（合取），or（析取），not（取反），iff（双向蕴含），if（蕴含），优先级（数字越大，优先级越高）定义如下表。

Operator	Priority
()	5
not	4
and	3
or	2
iff	1
if	1

def buildSentences(file: str) -> LogicalExpression:
    h_node = LogicalExpression("and")
    lines = readLinesFromTxt(file)
    for line in lines:
        tokens = line2Tokens(line)
        var = toRPN(tokens)
        result = RPN2Tree(var)
        h_node.appendChild(result)
    return h_node

几个比较容易理解的部分：

• readLinesFromTxt - 从txt中读取所有行 -> list
• line2Tokens - 以空格为分隔符提取一行内的tokens

这里有几个重要的类和函数：

（1）class LogicalExpression

我们用“树”来描述这样一个表达式，因为树能很好地表达这些语句的结构与层级特点。

类LogicalExpression是树（或者说树的节点），定义如下：

class LogicalExpression(object):
    def __init__(self, content: str) -> None:
        super(LogicalExpression, self).__init__()
        if content in PRIORITY_DICT:
            self.connective = content
            self.symbol = None
        else:
            self.symbol = content
            self.connective = None
        self.children: List[LogicalExpression] = []
        self.parent: LogicalExpression = None

    def appendChild(self, child) -> None:
        child: LogicalExpression = child
        self.children.append(child)
        child.parent = self

• 每个节点包括了symbol和connective，二者是互斥的，即一个节点只能为逻辑变量（叶子节点）或逻辑运算符（中间节点），一个有值时另一个为None。
• 由此可以将一个句子（文件中的一行）表达为一棵树，例如B12 iff (P12 or P22 or P13)可以表示为
  
  实际上，经过后续处理，这棵树应该长成如下的样子：
  
  二者是逻辑等价的，所以不影响分析。
• PRIORITY_DICT

PRIORITY_DICT = {
    "#"  : 0,
    "("  : 1,
    "if" : 2,
    "iff": 2,
    "or" : 3,
    "and": 4,
    "not": 5,
    ")"  : 6
}

（2）function toRPN

用逆波兰式（RPN）改写语句，具体算法见链接，主要是为了方便处理式子。

for token in tokens:
    if token in PRIORITY_DICT:  # it is an operator
        if token == "(":
            # push 
            op.append(token)
        elif token == ")":
            # pop till (
            while op[-1] != "(":
                var.append(op.pop(-1))
            op.pop(-1)  # pop "("
        elif PRIORITY_DICT[token] > PRIORITY_DICT[op[-1]]:
            # push
            op.append(token)
        else:
            # pop till smaller than token
            while PRIORITY_DICT[op[-1]] >= PRIORITY_DICT[token]:
                var.append(op.pop(-1))
            op.append(token)
    else:
        var.append(token)

（3）function RPN2Tree

现在将这一串串token连成一棵棵树，这时候使用RPN的优越性就体现出来，因为优先级的问题已经自动解决了。

在这一问题中，“运算”变为了节点的连接，不同的逻辑运算符有不同的连接方法，例如“not”只有一个子节点，而“and”，“or”等都有两个。

def RPN2Tree(var: list) -> LogicalExpression:
    def theOperation(op_node: LogicalExpression, children: List[LogicalExpression]) -> LogicalExpression:
        assert op_node.symbol is None
        assert op_node.connective is not None
        for child in children:
            op_node.appendChild(child)
        return op_node
    var = [LogicalExpression(node) for node in var]
    result: list[LogicalExpression] = []
    for node in var:
        if node.symbol is not None:  # a leaf node
            # push
            result.append(node)
        else:                        # an operator
            # do "the operation"
            if node.connective == "not":
                result.append(theOperation(node, [result.pop(-1)]))
            else:
                result.append(theOperation(node, [result.pop(-1), result.pop(-1)]))
    return result[0]

至此我们已经完成了一个语句到一棵树的构建。最后将KB中所有的句子用一个“and”相连，“and”作为一个hyper-node就可以代表整个KB。 α \alpha α和KB是完全一样的。

4 枚举真值表

整个算法的核心就在于，通过穷尽真值表的每一行，寻找是否存在entail的反例。

4.1 伪代码

Boolean TT-Entails?(LogicalExpression KB, LogicalExpression alpha)
	List symbols1 = ExtractSymbols(KB);
	List symbols2 = ExtractSymbols(alpha);
	List symbols = concatenate(symbols1, symbols2);
	return TT-Check-All(KB, alpha, symbols, [])

Boolean TT-Check-All(LogicalExpression KB, LogicalExpression alpha, List symbols, Map model)
	if Empty?(symbols):
		if PL-True?(KB, model) then return PL-True?(alpha, model)
		else return true
	else:
		P = First(symbols);
		rest = Rest(symbols);
		return TT-Check-All(KB, alpha, rest, Extend(P, true, model)) and 
   			   TT-Check-All(KB, alpha, rest, Extend(P, false, model))

直接看伪代码真不好理解，太多函数不清楚是什么含义，而且递归容易让大脑堆栈溢出，先厘清一下代码思路。

4.2 思路解释 4.2.1 总体思路

1. TT-Entail只是一个壳子，代码的主体部分在TT-Check-All，TT-Entail只是将KB和α中的所有symbol提取出来，连接成一个列表（集合，更准确地讲），这个列表就是我们的逻辑变量域。

2. 将这些变量分别赋True和False，由此可以推断出整句话的真值，进而推断出KB和α的真值，就构成了整张真值表。

3. 在所有这些情况中，如果存在某种逻辑变量的真值组合使得KB为真时，α为假，则说明找到了反例，KB不蕴含α。

举个例子，假设KB为B11 iff (P12 or P21)只有这一句话，α为P12 or P21

则symbols为[B11, P12, P21]可以构建真值表：

B11	P12	P21	KB	α
F	F	F	T	F
F	F	T	F	T
F	T	F	F	F
F	T	T	F	T
T	F	F	F	F
T	F	T	T	T
T	T	F	T	T
T	T	T	T	T

注意第一行，当KB为True时，α为False，因此这个例子中KB不蕴含α，也即不能从KB推断出α（直观上也很好理解）。

4.2.2 模块解释

1. ExtractSymbols 上文已经解释了，是将symbols从语句中提取出来。
2. model以及Extend
   model可以理解为一个字典，实际上就是真值表中的一行，键为逻辑变量，值为True or False。
   Extend就是将一个逻辑变量赋值为真或假，更新到model中。
3. PL-True
   判断一个句子是否为真，其内部也是递归实现的，主要分为以下两个步骤：
   1. 判断是否为叶子节点（symbol不是None），若是，根据model可以直接返回它的真值，这也是递归出口。
   2. 检测是什么逻辑运算，针对不同运算的逻辑要求，往下递归一层。
4. TT-Check-All的递归
   TT-Check-All的递归也分为两步：
   1. 判断是否所有逻辑变量都已经被赋值，判断的方法是查看symbols是否为空，这是因为，每当一个变量被赋值，它就会从symbols中被d出。若是，则可以判断KB和α的真值，根据4.2.1的3返回真假。
   2. 若否，说明还有变量未被赋值。此时需要向下递归一层，在新的一层中，model被更新。每个变量都有True和False两种赋值选择，又因为我们只要找到反例，整个算法就返回假，因此用and相连。
      

4.2.3 各模块代码实现

def extractSymbols(sentence: LogicalExpression) -> List[str]:
    result = []
    if sentence.symbol is not None:
        if sentence.symbol not in result:
            result.append(sentence.symbol)
    else:
        for child in sentence.children:
            result.extend(extractSymbols(child))
    return result

def extendModel(symbol: str, boolean: bool, model: dict) -> dict:
    model[symbol] = boolean
    return model

def PL_True(sentence: LogicalExpression, model: dict) -> bool:
    if sentence.symbol is not None:
        return model[sentence.symbol]
    elif sentence.connective == "and":
        for child in sentence.children:
            if not PL_True(child, model):
                return False
        return True
    elif sentence.connective == "or":
        for child in sentence.children:
            if PL_True(child, model):
                return True
        return False
    elif sentence.connective == "not":
        return not PL_True(sentence.children[0], model)
    elif sentence.connective == "if":
        left = sentence.children[0]
        right = sentence.children[1]
        if PL_True(left, model) and not PL_True(right, model):
            return False
        else:
            return True
    elif sentence.connective == "iff":
        left = sentence.children[0]
        right = sentence.children[1]
        if PL_True(left, model) == PL_True(right, model):
            return True
        else:
            return False
    else:
        raise NameError ("Invalid connective!")

def TT_CheckAll(KB: LogicalExpression, alpha: LogicalExpression, symbols: List[str], model: dict) -> bool:
    if symbols == []:
        if PL_True(KB, model):
            return PL_True(alpha, model)
        else:
            return True
    else:
        p = symbols.pop()
        return (TT_CheckAll(KB, alpha, symbols, extendModel(p, True, model)) 
                and 
                TT_CheckAll(KB, alpha, symbols, extendModel(p, False, model))
        )

5 测试

KB.txt

not P11
B11 iff (P12 or P21)
B21 iff (P11 or P22 or P31)
not B11
B21

alpha.txt

P31 or P22

结果

True

(The Wumpus World)