智能代理 Agent

定义

For each possible percept sequence, a rational agent should select an action that is expected to maximise the performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

一个代理应该拥有：

  • 用来感知来自环境中的信息的Sensors 传感器
  • 与环境进行交互的Actuators 执行器
  • 指出应该怎么做的Agent function 代理函数

一个代理怎样才能变得智能？

  • 我们需要告诉代理什么是合理的，也就是说，它需要一个performance measure 性能度量
  • 这个代理存储一个percept sequence 感知序列（有关环境状态的信息）
  • 代理可能有一些prior knowledge of the environment 关于环境的先验知识
  • 具有代理可以执行的well-defined actions 定义良好的操作

任务环境规范 Task Environment Specification

任务环境的性质（或维度）：

  • Observability (full, partial)
  • Deterministic or Stochastic
  • Episodic or Sequential
  • Static or Dynamic
  • Discrete or Continuous
  • Single or Multiple agents

用于搜索的代理

Problem formalisation 问题形式化

  1. Determine the relevant problem-solving knowledge

  2. Find a suitable state representation

  3. Define the initial state and the goal state(s)

  4. Define a transition model (also called successor function, or operators)

路线查找算法

  1. 广度优先搜索 Breadth-First-Search (BFS)
  2. 深度优先搜索 Depth-First-Search (DFS)

如何评价查找算法的性能？

  • Completeness

Will the algorithm find a solution if one exists?

  • Optimality

Will the algorithm find the solution with the lowest path cost?

  • Time Complexity

How long does it take the algorithm to find a solution?

  • Space Complexity

How much memory is needed to perform the search?

时间和空间的复杂度与搜索树中的节点数量成正比。空间的复杂性也会受到所使用的特定搜索策略的影响。

在人工智能问题中，复杂性可能难以衡量，因为我们可能从一开始就不知道确切的搜索树布局。如何得到一个大体的估计值？

Branching factor b (number of children per node)

Tree depth d (expected number of levels in the tree)

$b^d$ = number of nodes at depth d

搜索树最深处的节点数是节点总数的下界。对于许多应用场景，这个值足以决定一个特定的搜索策略是否是寻找解决方案的可行选择。该值乘以算法处理单个节点所需的时间就是这个算法大体的时间复杂度。该值乘以单个节点的存储需求，从而得到空间复杂度的估计值。

  1. 一致代价搜索 Uniform-Cost Search (UCS)

始终展开最浅的路径，即具有最低（总体）路径成本的后继路径。UCS是否比BFS更有效在很大程度上取决于路径成本分布。当所有路径成本相等时，UCS的行为与BFS相似。

  1. 深度受限搜索 Depth-Limited Search (DLS)

DFS的一种变体，限制了探索的深度。这可以防止算法运行无限的路径。然而，这也引入了一个额外的不完整性来源。

  1. 迭代深化搜索 Iterative Deepening Search (IDS)

迭代深化搜索（IDS）提供了一种解决深度限制搜索的正确限制的方法。通过迭代深化搜索，我们首先应用一个最小的深度限制（例如，1）。如果没有成功，我们将深度限制增加1，然后重复搜索，直到找到解决方案。底层的搜索技术仍然是DFS，因此不需要太大内存，因为它只在当前探索的级别上存储路径和节点。IDS可以说是最好的、通用的搜索策略，因为它提供了深度优先搜索的低内存成本，以及广度优先搜索的最优性和完整性。

Search Strategy Complete? Optimal? Time Complexity Space Complexity
BFS YES YES $O(b^d)$ $O(b^d)$
UCS YES YES $O(b^{\frac{OPTCOST} {MINCOST}})$ $O(b^{\frac{OPTCOST} {MINCOST}})$
DFS NO NO $O(b^d)$ $O(b*d)$
DLS NO NO $O(b^L)$ $O(b*L)$
IDS YES YES $O(b^d)$ $O(b*d)$

Abstract data types (ADT)

等同于数据结构

  • (FIFO) Queue 先进先出 队列
  • (LIFO) Stack 后进先出 栈

启发式与知情搜索策略 Heuristics & Informed Search Strategies

启发式

利用有关问题的知识来支持，一种解决问题的有效方法。

Greedy Best-First Search

Not Optimal Not complete

A*

使用一个同时包含路径代价和启发式代价的计算函数。

$f(n)=g(n)+h(n)$

g(n) : accumulated path cost

h(n) : estimated distance to goal

Conditions for Optimality

  • Admissibility

    A heuristic h(n) is admissible if h(n) ≤ h*(n), where h*(n) is the true cost to reach the goal state from n, i.e. the heuristic is optimistic such that it never overestimates the actual cost to reach the goal state along the current path through n.

  • Consistency

    A heuristic h(n) is consistent if for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost n → n’ plus the estimated cost of reaching the goal from n’.

总结：

  • Complete for finite spaces & positive path cost

  • Optimal: will always expand the currently best path

  • Optimally efficient

    (There is no other search algorithm that is guaranteed to expand fewer nodes and still find an optimal solution)

  • Space and time complexity depend on the heuristic chosen but can still be high in worst case, similar to BFS: $b^d$

优化A*算法：

Lowest Evaluation Result First: g(n) + h(n)

ADT：Priority Queue 优先队列

Hanoi 汉诺塔问题

Game Playing

特点：

  • 确定性的

    状态转换规则

  • 零和博弈

    一个玩家的胜利也就代表另一个玩家的失败。可能出现平局。

  • 完美信息

    所有玩家都可以访问关于游戏状态的所有可用信息，包括历史移动。

Task Environment

  • Initial state

  • Players

  • Transition Model (Actions + Results)

  • Terminal test (Goal test)

  • Utility-based evaluation function (What is the pay-off or outcome of each prospective move?)

Minimax Algorithm 极小化极大算法

假设我们是参与博弈的一方。我们用静态估计函数$f(p)$来估计博弈双方的态势：

有利于我方的态势：$f(p) \gt 0$
有利于敌方的态势：$f(p) \lt 0$
双方均衡的态势：$f(p) = 0$
显然，我方希望$f(p)$ 最大化，敌方希望$f(p)$ 最小化。因此称我方为Max方，敌方为Min方

在Max方的角度，因为是我们自己做决策，我们可以选择任意一种方案，所以我们只需选择收益最大的方案，也就是说每种方案之间是“或”的关系。

而对于Min方而言，因为是敌方做决策，我们无法控制敌方选择哪种策略，假设敌方足够聪明，我们应该假设敌方选择对他最有利的方案，也就是对我们最不利的方案、使我们收益最小的方案，所以对他而言每种方案之间是“与”的关系。

Alpha-Beta Pruning $\alpha \beta$剪枝

α-β剪枝是一种优化方法，在博弈树生成的过程中同时计算各节点的估计值及倒推值，通过对估值的上下限进行估计，减去没有用的分支，减少搜索范围，提高效率。

α-β剪枝的基本思想：

“或”节点（Max方）：取当前子节点中效用值的极大值为该节点效用值的下界，称为α（α≥该极大值），只有当下一个节点的值大于α才会被选择

“与”节点（Min方）：取当前子节点中效用值的极小值为该节点效用值的上界，称为β（β≤该极小值），只有当下一个节点的值小于α才会被选择

核心思想是：如果存在一个比某一分支更好的走法，那么就不考察这一分支。

Negamax / Negamax alpha beta algorithms 负极大值算法

负极大值算法是极小化极大算法的一个变体，其基本原理是基于下面的公式：

$max(a,b)=-min(-a,-b)$

即在几个节点中选择得分最小的节点相当于将这些节点的得分乘以-1然后取得分最大的节点。这样Negamax算法就将每一步递归过程都统一了起来，每一次递归都选取最大值。Negamax适用于只有两个玩家的零和游戏。

自动推理

认识论 Epistemology

Explicit knowledge 显式知识

Implicit knowledge 隐式知识

Tacit knowledge 意会知识

知识从哪里来？

通过从感官刺激中学习获得：经验主义

通过推理获得：理性主义

归纳，假设，演绎推理

正向推理 Forward-Reasoning

逻辑含义称为规则，它存储在规则库中。我们使用一个前向链式过程来递归地生成结论。根据最初建立的事实，我们检查下一步可以使用哪些规则，也就是说，哪些规则现有事实满足它们的所有条件。然后，我们添加相关的结论并重复操作，直到无法得出新的结论。

所发现的任何事实都决定了下一个规则的选择。因此，正向推理也被称为数据驱动的方法。

反向推理 Backward-Reasoning

在另一种方法中，我们从希望得出的结论开始反向推理，看看它是否可以根据一个已知的事实是合理的。在逆向推理中，我们从假设作为目标开始，看看是否有任何前因（数据）支持对目标的结论。因此，逆向推理也被称为目标驱动的方法。

逻辑与知识表示

命题逻辑

在命题逻辑（propositional logic）中，原子公式（atomic formula）是命题（proposition）。原子公式是用来构造语句（sentence）的构成要素。在任意逻辑中，语句被视作一种特殊类型的公式，这两个术语之间不作区别。在命题逻辑中，每一个语句要么正确（true），要么错误（false），两者必居其一。真值（truth value) 1 或 0 被指派给相应的语句。在上面的例子中，我们可以把真值 1 指派给公式 A，真值 0 指派给公式 B。如果我们字面地理解公式 C，那么其真值是有争议的。也许，允许真值介于 1 和 0 之间更合理。我们可以把 0.75 指派给洛芙，如果洛芙比75%的美国女性更高。模糊逻辑（fuzzy logic）允许这样的真值存在，但是我们研究的经典逻辑不允许。

实际上，命题的内容与命题逻辑无关。我们约定，从此以后，原子公式仅用大写字母A、B、C……表示（可能带有下标），而不涉及命题实际上在说什么。我们并不关心这些公式内容的准确性（veracity）。命题逻辑并不研究事实，而是研究不同命题的真值的关系。

命题逻辑的语言主要包括“非（not）”“与（and）”“或（or）”“蕴含（implies）”和“当且仅当（if and only if）”。我们用以下符号分别表示命题逻辑中的词语： ¬ ∧ ∨ ⟹ ⟺ 。就像语言间的翻译一样，这样的对应并不是完全准确恰当的。这些符号表示的意义是准确的、不变的；而自然语言的词义往往取决于上下文。比如 ∧ 常会被解释为and。在命题逻辑中， A∧B 和 B∨A 的意义总是完全相同的。

一阶逻辑

不像命题逻辑只处理简单的陈述命题，一阶逻辑还额外包含了断言和量化。

关系与分类

知识的联想主义理论通过其与其他事物的关系来定义某一事物的意义。

不同的关系可以描述不同的属性或行为。

结构化表示比句子语言更灵活，对人类来说更容易理解和推理。

简单的语义网可能会很混乱，但仍然可能允许某种程度的推理。

在语义网络的思想之上，可以建立更专业的知识表示。例如，有框架、脚本和概念图。

本体和语义web

本体在Web上的应用导致了语义Web的诞生，其目的是解决Web上信息共享时的语义问题。1999年，Web的创始人伯纳斯－李(Tim Berners-Lee)首次提出了“语义Web”（Semantic Web）的概念。2001年2月，W3C正式成立“Semantic Web Activity”来指导和推动语义Web的研究和发展，语义Web的地位得以正式确立。

语义Web提供了一个通用的框架，允许跨越不同应用程序、企业和团体的边界共享和重用数据。语义Web是W3C领导下的协作项目，有大量研究人员和业界伙伴参与。语义Web以资源描述框架（RDF）为基础。RDF以XML作为语法、URI作为命名机制，将各种不同的应用集成在一起，对Web上的数据所进行的一种抽象表示。语义Web所指的“语义”是“机器可处理的”语义，而不是自然语言语义和人的推理等计算机所不能够处理的信息。

知识管理是一种对知识的组织和再组织，以及对人的显性和隐性知识进行管理，通过对知识的获取、组织、分发、应用，实现知识共享和知识创新，提高组织的创新能力、反应能力、生产率以及技术技能，增加核心竞争力。在今天激烈竞争的环境中，知识管理有助于企业整合自身知识，实现知识流程化、企业化；使企业能够快速有效地对外界进行响应，提高单位时间内创造的价值；扩大知识利用的程度与范围，增强创新能力和商务智能；打破原有管理等级边界，拓展组织发展的空间。

本体是语义Web的基础，本体可以有效地进行知识表达，知识查询，或不同领域知识的语义消解。本体还可以支持更丰富的服务发现、匹配和组合，提高自动化程度。本体知识管理（ontology-based knowledge management）可实现语义级知识服务，提高知识利用的深度。

本体知识管理还可以支持对隐性知识进行推理，方便异构知识服务之间实现互操作，方便融入领域专家知识及经验知识结构化等。本体知识管理一般要求满足以下基本功能：①支持本体多种表示语言和存储形式，具有本体导航功能；②支持本体的基本操作如本体学习、本体映射、本体合并等；③提供本体版本管理功能，支持本体的可扩展性和一致性。

知识本体是领域概念及概念之间关系的规范化描述，这种描述是规范的、明确的、形式化的，可共享的。“明确”意味着所采用概念的类型和它们应用的约束实行明确的定义。“形式化” 指知识本体是计算机可读的(即能被计算机处理)；“共享”反映知识本体应捕捉该领域中一致公认的知识，反映的是相关领域中公认的概念集，即知识本体针对的是团体而非个体的共识。知识本体的目标是捕获相关领域的知识,提供对该领域知识的共同理解,确定该领域内共同认可的词汇,并从不同层次的形式化模式上给出这些词汇和词汇间相互关系的明确定义。

模糊集&模糊逻辑

在逻辑中，模糊逻辑是多值逻辑的一种形式，其中变量的真值可以是0到1之间的任何实数。它用于处理部分真值的概念，其中真值可能介于完全真值之间并且完全错误。相比之下，在布尔逻辑中，变量的真值可能只是整数值0或1。

经典逻辑只允许结论为真或假。然而，也有一些具有可变答案的命题，例如在要求一群人识别颜色时可能会发现。在这种情况下，真理是从不精确或部分知识进行推理的结果，其中抽样答案被映射到频谱上。

两个真实度的和概率的范围0到1之间，并因此可能看起来在xxx相似，但模糊逻辑使用真实度为的数学模型的模糊性，而概率是一个数学模型无知。

应用真值：基本应用程序可能表征连续变量的各种子范围。例如，防抱死制动器的温度测量可能有几个单独的隶属函数，定义正确控制制动器所需的特定温度范围。每个函数将相同的温度值映射到0到1范围内的真值。然后可以使用这些真值来确定应如何控制制动器。模糊集理论提供了一种表示不确定性的方法。

语言变量：在模糊逻辑应用中，经常使用非数字值来促进规则和事实的表达。诸如年龄之类的语言变量可以接受诸如年轻及其反义词old之类的值。由于自然语言并不总是包含足够的价值术语来表达模糊的价值尺度，因此通常的做法是用形容词或副词来修饰语言价值。例如，我们可以使用对冲而不是和有点来构造额外的值而不是旧或有点年轻。

贝叶斯规则

条件概率：$P(A|B)$

熵：$\sum_i^n{p_i*log_2(\frac{1}{p_i})}$

Pi是第i个选择的概率。熵随备选方案的数量和归属概率的均匀性而增加。

当使用熵作为不确定性的度量时，我们可以评估当一些事情发生并更新当前分布时我们获得了多少信息（即，我们获得了新的信息）。不确定性的减少意味着知识的增加。

给定证据E和一些结论C：

$P(C|E)=\frac{P(C)*P(E|C)}{P(E)}$

P(C)和P (E)被称为prior probabilities 先验概率。P（E|C）是likelihood 似然。P（C|E）被称为posterior probability 后验概率。

条件概率遵循链式法则。

贝叶斯网络

马尔科夫链