AIMA

 

Fig	Page	Name (in book)	描述	Code
2	34 50	Environment 环境，又称为智能体所在的任务环境	有以下几个维度： 1.完全可观察和部分可观察 2.确定的和随机的 3.片段式的和连续式的 4.静态的与动态的 5.离散的与连续的 6.单智能体与多智能体	Environment
2.1	35 53	Agent 智能体＝体系结构+程序	这里的Agent指的是智能体程序	Agent
2.3	36	Table-Driven-Vacuum-Agent		TableDrivenVacuumAgent
2.7	47 53	Table-Driven-Agent 表驱动智能体	1.记录感知序列 2.已感知序列为索引 3.查询对应的行动决策 评价：只能对简单的环境进行处理，否则数量会大到无法处理	TableDrivenAgent
2.8	48 54	Reflex-Vacuum-Agent 反射智能体	根据设定好的“条件－行为规则”进行行动， 如：前方的车在刹车，那么我就要刹车	ReflexVacuumAgent
2.10	49 55	Simple-Reflex-Agent 简单反射智能体	1.根据当前感知判断当前状态 2.根据当前状态，查找适合的规则 3.根据规则，进行对应行动	SimpleReflexAgentProgram
2.12	51 57	Model-Based-Reflex-Agent	1.智能体根据之前状态、行动、当前感知和一个下个状态要依赖的模型来维护一个内部状态 2.根据当前状态，查找适合的规则 3.根据规则，进行对应行动 评价：对于部分可观察的环境来说，维护一个内部状态很重要（第3版的内容）	ModelBasedReflexAgentProgram
3	66 69	Problem 问题	五要素： 1.初始状态 2.后继函数 3.目标测试 4.路径耗散 5.转换模型[第3版新添]	Problem
3.1	67 68	Simple-Problem-Solving-Agent 简单问题处理智能体	1.形式化描述了目标和问题 2.搜索能解决该问题的行动序列 3.依次执行这些行动 4.这个过程完成之后，它形式化描述另一个目标并重复以上步骤 注意：智能体在执行序列的时候会忽略它的感知，它假设找到的解总是可行的	SimpleProblemSolvingAgent
3.2	68 70	Romania 罗马尼亚	罗马尼亚的道路信息，比如耗散	SimplifiedRoadMapOfPartOfRomania
3.7	77 76	Tree-Search 一般生成搜索树算法	1.用给定的元素创建一个队列 2.从队列中取出第一个节点 3.检查该节点是否能解决问题， 4.如果能解决，则回溯并返回求解路径 5.如果不能，则展开节点并加入到队列中 6.循环此过程直到队列为空	TreeSearch
3.7	77 85	Graph-Search 图搜索算法	1.根据问题的初始状态生成边界 2.从边界中选取一个叶子节点 3.判断该节点是否能解决问题 4.能，则返回解决方案 5.否则，加入到已遍历列表，展开此节点到边界，重新选取一个节点 6.循环此过程直到边界为空	GraphSearch
3.10	79	Node		Node
3	79	Queue		Queue
3.11	82 77	Breadth-First-Search 广度优先搜索	1.扩展根节点 2.扩展根节点的所有后继 3.扩展后继的后继 4.以此类推 评价：此算法最简单，但对内存需求太过庞大；当单步耗散相同的时候，此算法最优	BreadthFirstSearch
3.14	84 79	Uniform-Cost-Search 代价一致搜索	取代扩展深度最浅的节点，而是扩展路径消耗最低的节点	UniformCostSearch
3	85 79	Depth-first Search 深度优先搜索	总是扩展搜索树当前边缘中最深的节点	DepthFirstSearch
3.17	88 81	Depth-Limited-Search 深度有限搜索	深度为L的节点被当作没有后继的节点来对待	DepthLimitedSearch
3.18	89 81	Iterative-Deepening-Search 迭代深入深度优先搜索	不断增加深入限制直到找到目标节点	IterativeDeepeningSearch
3	90 83	Bidirectional search 双向搜索	同时运行两个搜索，其中一个从初始状态向前搜索，另一个从目标状态向后搜索，当它们在中间相遇时终止。 动机：pow(b, d/2) + pwd(b, d/2) 远小于 pow(b, d)	BidirectionalSearch
3	92 94	Best-First search 最佳优先搜索	一般是TreeSearch和GraphSearch算法的一个实例，它要扩展的节点是基于评价函数f(n)进行选择的。传统上，选择评价值最低的节点进行扩展，因为评价值度量了到目标的距离。	BestFirstSearch
3	92 95	Greedy best-First search 贪婪最佳优先搜索	试图扩展离目标节点最近的节点，建立在这样可能很快找到解的基础上。因些，它只用启发函数f(n)=h(n)来评价节点。	GreedyBestFirstSearch
3	93 96	A* search A星搜索	最小化总的估计解耗散。它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价。 f(n) = g(n)+h(n) 倘若h(n)从不会过高估计到达目标的耗散，那么此算法是最优的	AStarSearch
3.26	99 100	Recursive-Best-First-Search 递归最佳优先搜索	模仿标准的最佳优先搜索的递归算法，但是它只使用线性的存储空间。它的结构和递归深度优先搜索类似，但是它不沿着当前的不确定路径继续下去，而是记录从当前节点的祖先可得到的最佳可替换路径的f值。如果当前节点超过了这个限制，递归将回到替换的路径上。当递归回溯时，对回溯前的当前路径上的每个节点，RBFS用其了节点的最佳f值替换其f值。这样RBFS能记住被它遗忘的子树中的最佳叶节点的f值，并因此能够在以后某个时刻决定是否值得重新扩展该子树。	RecursiveBestFirstSearch
4.2	122 108	Hill-Climbing 爬山法	它是一个向值增加的方向持续移动的简单循环过程，它将会在到达一个“峰顶”时终止，相邻中没有比它更高的值。它不维护搜索树，因此当前节点的数据结构只需要记录当前状态和它的目标函数值。它不会前瞻与当前状态不直接相邻的那些状态的值。就像健忘的人在大雾中试图登顶珠穆朗玛峰一样。	HillClimbingSearch
4.5	126 109	Simulated-Annealing 模拟退火搜索	想象使不平表面上的一个乒乓球掉到最深的裂缝中的任务，如果我们只是让乒乓球在表面上滚动，那么它会停留在局部极小点，如果我们晃动平面，我们可以使乒乓球弹出局部极小点。技巧是晃动要足够大让乒乓球能人局部极小点弹出来，但又不能太大把它从全局最小点赶出来。 其解决办法就是：开始使劲摇晃（也就是先高温加热）然后慢慢降低摇晃的强度（也已经逐渐降温）。它用评价值变坏的梯度和温度来降低随机概率。	SimulatedAnnealingSearch
4.8	129 110	Genetic-Algorithm 遗传算法	它是随机剪枝搜索的一个变化形式，它不是通过修改单一状态而是通过把两个父状态结合来生成后继的。它与自然选择类似，这点和随机剪枝搜索是一样的。	GeneticAlgorithm
4.11	136 351	And-Or-Graph-Search 与或图算法	对极大极小值算法做了两个典型的修改。第一，MAX和MIN节点能够变成OR（或）和AND（与）节点。直观地，在每个到达的状态，规划只需要采取某个行动，但是需要处理它所采取的行动产生的每个结果。第二，算法需要返回一个条件规划，而不仅仅是一个单步移动。在或节点，规划只是被选中的行动，伴随着下一步会出现的任何情况。在与节点，规划是用来指定每个结果的子规划的if-then-else步骤嵌套序列；这些步骤中的测试是完全状态描述。	AndOrSearch
4	147	Online search problem		OnlineSearchProblem
4.21	150 116	Online-DFS-Agent 联机深度优先搜索体	它将它的环境地图存储在一个表里result[a,s]，记录了在状态s执行行动a得到的结果状态。只要从当前状态出发的某个行动还没有被探索过，智能体就要尝试这个行动。难题来自智能体尝试完一个状态的所有行动之后。在脱机尝试优先搜索中，状态很简单的被从队列中删除；而在联机搜索中，智能体不得不实际的回溯。在尝试优先搜索中，这意味着回溯到智能体进入当前状态前最近的那个状态。这要通过维护一个表来达到，该表列出每个状态的所有还没有回溯的前辈状态。如果智能体已经没有可回溯的状态了，那么它的搜索完成了。	OnlineDFSAgent
4.24	152 118	LRTA*-Agent 实时学习A星智能体	和ONLINE－DFS－AGENT一样，它用result表建造一个环境地图。它更新了刚刚离开的状态的耗散估计，然后根据当前的耗散估计选择“显然最佳的”移动。一个重要的细节是：在状态s从未尝试过后行动总被假设为能用最小可能耗散（也就是h(s)）直接达到目标。这种不确定条件下的乐观主义鼓励智能体探索新的、可能更有希望的路径。	LRTAStarAgent
5.3	166 146	Minimax-Decision 极小极大值算法	从当前状态计算极小极大决策。它使用了简单的递归算法，计算每个后继的极小极大值，直接实现定义公式。递归算法自上而下一直前进到树的叶节点，然后随着递归回溯通过树把极小极大值回传。 评价：它对博弈树执行了一个完整的深度优先探索，它必须检查的游戏状态的数目随着招数的数量指数级增长，对于真实的游戏它的开销完全不实用。	MinimaxSearch
5.7	170 149	Alpha-Beta-Search α-β剪枝	它剪裁掉那些不可能影响最后决策的分支，仍然可以返回和极小极大值算法同样的结果。 α＝到目前为止我们在路径上的任意选择点发现的MAX的最佳（即极大值）选择 β＝到目前为止我们在路径上的任意选择点发现的MIN的最佳（即极小值）选择 α-β搜索不断更新α和β值，并且当某个节点的值分别比目前的MAX的α或者MIN的β值更差的时候剪裁这个节点剩下的分支（即终止递归调用）。	AlphaBetaSearch
6	202 126	CSP 约束满足问题	由一个变量集合和一个约束集合定义的。每个变量都 有一个非空的可能值域。每个约束包括一些变量 的子集，并指定了这些子集的值之间允许进行的合并。问题的一个状态是由对一些或全部变量 的一个赋值定义的。一个不违反任何约束条件的赋值称作相容的或者合法的赋值。一个完全赋值的每个变量都参与的赋值，而CSP问题的解是满足所有约束的完全赋值。某些CSP问题还要求问题的解能使目标函数最大化。	CSP
6.1	204	Map CSP		MapCSP
6.3	209 132	AC-3 弧相容算法	弧是指约束图中的有向弧，如果对于一值域的每取值x,另一值域都有某个取值y能和x保持相容，那么这条弧是相容的。 弧相容检验不仅可以用作开始搜索过程之前的预处理，也可以在搜索过程中每次赋值后用作一个传播约束步骤（像前向检验一样）。（后一个算法有时也称为MAC，即保持弧相容）在每种情况下这个过程必须反复应用直到不再有矛盾。这是因为，任何时候从某个变量的传开中删除一个值以消除弧不相容，指向这个变量的弧都可能会产生新的弧不相容。   此算法用一个队列来记录需要检验不相容性的弧，每条弧依次从队列中删除并被检验；如果任何一个值域中的值需要被删除，那么每个指向这个值域的弧都必须重新插入队列中准备检验。	AC3Strategy
6.5	215 129	Backtracking-Search CSP问题的回溯搜索	以递归尝试优先搜索为模型，它考虑了CSP问题元素的可交换性，在搜索树的每个节点上只考虑单个变量 的可能赋值，当没有合法的值 可以赋给变量时就回溯。	BacktrackingStrategy
6.8	221 135	Min-Conflicts 最小冲突启发式算法	在为变量选择一个新值的时候，最明显的启发式是选择会造成与其它变量的冲突最小的值	MinConflictsStrategy
6.11	209	Tree-CSP-Solver		---
7	235 170	Knowledge Base 知识库	知识库是一个语句集合，这些语句在被称为知识表示语言的语言中表达，表示了关于世界的某些断言。	KnowledgeBase
7.1	236 170	KB-Agent 基于知识的智能体	基于知识的智能体感知信息作为输入并返回一个行动。智能体维护一个知识库，KB。该知识库在初始化时包括了一些背景知识。每次调用智能体程序，它做两件事件： 1.智能体TELL告诉知识库它感知的内容  2.它ASK询问知识库应该执行什么行动 在回复查询的过程中，可能要对关于世界的当前状态、可能行动序列的结果等等进行大量推理。一旦选择了某个行动，智能体用TELL记录它的选择并执行该行动。为了让知识库了解到该假定行动确实已经被执行，第二个TELL必不可少。	---
7.7	244 176	Propositional-Logic-Sentence 命题逻辑	由原子语句和逻辑连接符组成。以下是常用的5种连接符： 非、与、或、蕴涵（可以理解为：前项的结论是后期）、当且仅当（双向蕴含）	Sentence
7.10	248 180	TT-Entails 真值表枚举算法	执行对变量赋值有限空间的递归枚举	TTEntails
7	253	Convert-to-CNF		CNFTransformer
7.12	255 185	PL-Resolution 归结算法	首先把（KB与非α）转换为CNF，接着，对结果子句运用归结规则。每对包含互补文字的子句相归结产生一个新的子句，如果该新子句尚未出现过，则将它加入子句集中。此过程将持续下去，直到发生以下两件事情之一： 没有可以添加的新语句，这种情况下，α不蕴涵β 使用归结规则可以生成空子句，这种情况下α蕴涵β	PLResolution
7.15	258 187	PL-FC-Entails? 前向链接算法	Agenda记录了已知为真但还没有“处理”的符号。count表记录着每个蕴涵还有多少前提依然未知。只要待办事项表Agenda中的一个新符号p被处理，对于每个前提中出现p的蕴涵而言，它相应的计数值减去1.（如果KB已经建立了适当的索引，这可以在固定的时间内完成。）如果计数达到0，蕴涵的所有前提都已知，因此可以把它的结论添加到Agenda中。最后，我们需要记录哪些符号已经被处理过；一个推理符号无需添加到Agenda中，如果它先前已经被处理。这避免了冗余操作；它还能阻止发生可能由P蕴涵Q和QP这样的蕴涵引起的无限循环。	PLFCEntails
7.17	261 189	DPLL-Satisfiable?	做了如下优化： 1.及早终止 2.纯符号启发式 3.单元子句启发式	(method)-dpllSatisfiable(String)
7.18	263 190	WalkSAT	算法在每次迭代中选择一个未得到满足的子句并从该子句中选择一个符号对其进行翻转操作。它在两种方法随机选择一个来挑选要翻转的符号： 1.“最小冲突”步骤，最小化新状态下未满足语句的数量 2.“随机行走”步骤，随机挑选符号	WalkSAT
7.20	270	Hybrid-Wumpus-Agent		---
7.22	272 328	SATPlan 命题逻辑规划	规划问题被转换成一个CNF语句，在该语句中目标被断言在固定的时间步T是成立的，而且包含每个时间步一直到T的公理。如果可满足性算法找到一个模型，然后通过查看那些指代行动且在模型中赋值为真的命题符号来抽取规划。如果没有模型存在，那么把目标向后移动一步，重复这个过程。	---
9	323 227	Subst 置换	置换 SUBST(o,a)表示把置换o用于a的结果	SubstVisitor
9.1	328 230	Unify 合一	被提升的推理规则要求找到相关的置换，让不同的逻辑表示看起来是一样的。这个过程称为合一，也就所有一阶推理算法的一个关键部分。合一算法挑选两条语句并返回一个它们的合一者，如果存在的话：UNIFY(p,q)=o，这里SUBST(o,p)=SUBST(o,q)	Unifier
9.3	332 233	FOL-FC-Ask 前身链接算法	它从已知的事实开始，触发所有前提得到满足的规则，把结论添加到已知事实。重复该过程直到查询得到回答（假定只需要一个答案）或者没有新的事实加入。注意如果某个事实只是已知事实的重命名，那它就不是“新的”。	“”FOLFCAsk
9.3	332 237	FOL-BC-Ask 反向链接算法	它用只包含单个元素（即原始查询）的目标列表来调用，并返回满足查询的所有转换的集合。目标列表可以认为是一个等待处理的“栈”；如果有的栈内目标都可以得到满足，则当前的证明分支是成功的。算法选择列表中的第一个目标，在知识库中寻找正文字（或称为头）能与该目标合一的每个子句。每个这样的子句创建一个新的递归调用，在该递归过程中，子句的前提（或称为体）都被加入到目标栈内。记住事实就是只有头没有体的子句，因此当目标和某个已知事实合一时，不会有新的子目标添加到栈里，目标敢就得到了解决。	FOLBCAsk
9	345	CNF	命题逻辑的每个语句逻辑等价于文字析取式的合取式。以文字析取式的合取形式表达的语句被称为合取范式或者CNF。	CNFConverter
9	347	Resolution		FOLTFMResolution,  FOLOTTERLikeTheoremProver
9	354	Demodulation		Demodulation
9	354	Paramodulation		Paramodulation
9	345	Subsumption		SubsumptionElimination
10.9	383 324	Graphplan 规划图	它有两个主要步骤，它们在循环内交替。第一，它检查所有目标文字是否出现在当前阶段，而且它们中的任何一对文字之间没有互斥连接。如果的确如此，那么当前图中可能存在一个解，因此算法尝试抽取这个解。否则，它通过为当前阶段添加行动以及为下一个阶段添加状态文字来扩展该图。过程继续进行，直到一个解被找到或者它已经知道没有解存在。	---
11.5	409	Hierarchical-Search		---
11.8	414	Angelic-Search		---
13.1	484 376	DT-Agent 决策理论智能体	在一个抽象层次上，该智能体和第七章所描述的逻辑智能体是相同的。主要的区别在于，决策理该智能体关于当前状态的知识是不确定的；智能体的信度状态是对于世界的所有可能实际状态的一种概率表示。随着时间推移，智能体积累了更多的证据，它的信度状态也会发生变化。给定信度状态，智能体能够对行动的结果进行概率预测，进而选择期望效用最高的行动。	---
13	484	Probability-Model 概率模型		ProbabilityModel,  FiniteProbabilityModel
13	487	Probability-Distribution 概率分布		ProbabilityDistribution,  CategoricalDistribution
13	490	Full-Joint-Distribution 全联合分布		FullJointDistributionModel
14	510 396	Bayesian Network 贝叶斯网络	贝叶斯网络是一个有向图，其中每个节点都标注了定量概率信息。其完整的详细描述如下： 1.一个随机变量集组成网络节点。变量可以是离散的或者连续的。 2.一个连接节点的对的有向边或箭头集合。如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点。 3.每个节点Xi都有一个条件概率分布P（Xi|Parents(Xi)）,量化其父节点对该节点的影响。 4.图中不存在有向环（因此是一个有向无环图，或缩写为DAG）	BayesianNetwork
14.9	525 384	Enumeration-Ask 枚举全联合分布概率推理算法	令X为查询变更，令E为证据变更集合，e表示其观察值；并令Y为其余的未预测变量查询为P(X|e),可以对它求值：P(X|e)=aP(X,e)=a*Sum(P(X,e,y))，其中的求和针对所有可能的y(也就是对未难测变量Y的值的所有可能组合)。注意变量X，E以及Y一起构成了域中所有变量的完整信息，所以P(X,e,y)只不过是来自全联合分布概率的一个子集。它对所有X和Y的值进行循环以枚举当e固定时所有的原子事件，然后根据全联合分布的概率表将它们的概率加起来，最后对结果进行归一化。	EnumerationAsk
14.11	528 409	Elimination-Ask 变更消元算法	按照从右到左的次序计算公式的表达式。中间结果被保存下来，而对每个变量的求积只需要对依赖于这些变量的表达式部分进行就可以了。	EliminationAsk
14.13	531 411	Prior-Sample 直接采样算法	对于贝叶斯网络而言，最简单种类的随机采样过程是对没有与之关联的证据的网络事件进行采样。其思想是按照拓扑次序依次对每个变量进行采样。被采样变量值的概率分布依赖于父节点已得到的赋值。	PriorSample
14.14	533 412	Rejection-Sampling 拒绝采样算法	它是一类由一个易于采样的分布出发，为一个难以直接采样的分布产生样本的通用算法。在其最简单的形式中，它可以被用于计算条件概率，也就是：确定P(X|e). 首先，它根据网络指定的先验概率分布生成采样样本。然后，它拒绝所有与证据不匹配的样本。最后通过在剩余样本中对事件X＝x的出现频繁程序计数从而得到估计概率P（X＝x|e）	RejectionSampling
14.15	534 413	Likelihood-Weighting 似然加权算法	它只生成与证据e一致的事件，从而避免拒绝采样算法的低效率。它固定证据变量E的值，证据以外的其余变量X和Y进行采样。这保证了生成每个采样样本都与证据一致。然而，并非所有的事件的地位都相等。在对查询变量的分布进行计数之前，把根据证据得到的事件的似然作为每个事件的权值，这个权值通过每个证据变量在给定其父节点取值下的条件概率的乘积进行度量。直观地看，其中不太可能出现证据的事件应该给予较低的权值。	LikelihoodWeighting
	415	MCMC－Ask 马尔可夫链蒙特卡洛算法	和其它两种为每个事件都重新生成样本的采样算法不同，马尔可夫链蒙特卡洛算法总是通过对前一个事件进行随机改变而生成每个样本。因此可以认为网络处于为每一个变量指定了值的一个特定的当前状态。而下一个状态则通过对某个非证据变量Xi进行采样来产生，取决于Xi的马尔可夫覆盖中的变量当前值（单变量马尔可夫覆盖是由节点的父节点、子节点以及子节点的父节点组成的）。因此马尔可夫链蒙特卡洛算法可以被视为在状态空间中——所有可能的完整赋值的空间——的随机走动——每次改变一个变量，但保持证据变量的值固定不变。
14.16	537	GIBBS-Ask 吉布斯	关于Gibbs sampling， 首先看一下Wiki上的解释：Gibbs sampling or Gibbs sampler is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables. The purpose of such a sequence is to approximate the joint distribution, or to compute an integral(such as an expected value). 说到Gibbs Sampling 就不得不说markov chain了。 Markov chain 是一组事件的集合，在这个集合中，事件是一个接一个发生的，并且下一个事件的发生，只由当前发生的事件决定。用数学符号表示就是：  A={ a1,a2 … ai, ai+1,… at } P(ai+1| a1,a2,…ai) = P(ai+1| ai) 这里的ai不一定是一个数字，它有可能是一个向量，或者一个矩阵，例如我们比较感兴趣的问题里ai=（g, u, b）这里g表示基因的效应，u表示环境效应，b表示固定效应，假设我们研究的一个群体，g，u，b的联合分布用π（a）表示。事实上，我们研究QTL，就是要找到π（a），但是有时候π（a）并不是那么好找的，特别是我们要估计的a的参数的个数多于研究的个体数的时候。用一般的least square往往效果不是那么好。 解决方案： 用一种叫Markov chain Monte Carlo (MCMC)的方法产生Markov chain，产生的Markov chain{a1,a2 … ai, ai+1,… at }具有如下性质：当t 很大时，比如10000，那么at ~ π（a），这样的话如果我们产生一个markov chain：{a1,a2 … ai, ai+1,… a10000}，那么我们取后面9000个样本的平均   a_hat = (g_hat,u_hat,b_hat) = ∑ai / 9000 (i=1001,1002, … 10000) 这里g_hat, u_hat, b_hat 就是基因效应，环境效应，以及固定效应的估计值 MCMC有很多算法，其中比较流行的是Metropolis-Hastings Algorithm，Gibbs Sampling是Metropolis-Hastings Algorithm的一种特殊情况。MCMC算法的关键是两个函数： 1）    q（ai, ai+1），这个函数决定怎么基于ai得到ai+1 2）    α（ai, ai+1），这个函数决定得到的ai+1是否保留 目的是使得at的分布收敛于π（a） Gibbs Sampling的算法： 一般来说我们通常不知道π（a），但我们可以得到p（g | u , b）,p(u | g , b), p ( b | g, u )即三个变量的posterior distribution Step1: 给g, u, b 赋初始值：（g0,u0,b0） Step2: 利用p (g | u0, b0) 产生g1 Step3: 利用p (u | g1, b0) 产生u1 Step4: 利用p (b | g1, u1) 产生b1 Step5: 重复step2~step5 这样我们就可以得到一个markov chain {a1,a2 … ai, ai+1,… at} 这里的q（ai, ai+1）= p（g | u , b）* p(u | g , b)* p ( b | g, u ) From：link ============================================= 互动百科这么说的： 概率推理的通用方法，是Metropolis-Hastings算法的一个特例，因此也是Markov chain Monte Carlo算法的一种。 虽然它的通用性比较好，但导致了计算代价较高，所以在许多应用里，包括具有不完备信息的应用，都采用其它更为高效的方法。然而，理解这一方法有助于增进对统计推理问题的理解。 中心思想 由一个具有2个或更多变量的联合概率分布P(x1,x2,...,xn)，生成一个样本序列{y1,y2,...,ym}，用于逼近这一个联合分布，或计算一个积分（例如期望）。 适用于处理不完备信息，当联合分布不明确，而各个变量的条件分布已知的情况。 根据其他变量的当前值，依次对分布的每个变量生成一个实例。 随机过程 对一个随机过程，例如马尔可夫链过程，一般包括一个有限的状态集合 和 一个概率转移矩阵。假设这个过程各个各个状态都是可遍历的(ergodic)，即转移矩阵中的元素值都大于0。为此，我们可以选择任意状态为初始态 Q0，计算转化N次后可能到达的状态 Qn 的概率。当N取值足够大时，可以计算得到这一过程最有可能的终态。 假设有一个变量集合X={X1，X2，……，Xn}，P(X)为集合X的联合分布，0<P(X)<1。 我们将这些变量看做一个马尔科夫过程中的状态集，这一过程定义为：S=∏i=1~n	GibbsAsk
15.4	576 S8	Forward-Backward 前向－后向算法	线性时间算法的关键是记录对整个序列进行前向滤波的每步结果。然后我们从时刻t到时刻l运行后向递归过程，根据已经计算出来的后向消息b[k+1:t]和所存储的前向消息f[1:k]计算时刻t的平滑估计。	ForwardBackward,  HMMForwardBackward,  HMMForwardBackwardConstantSpace
15	578 S10	Hidden Markov Model 隐马尔可夫模型	它用单一离散随机变量描述过程状态的时序概率模型。该变量的可能取值就是世界的可能状态。其它的状态变更也可以加入到一个时序模型中，同时保持隐马尔可夫模型框架，不过只能通过将所有的状态变量组合成单个“大变量”的方式实现，其取值范围是全部单个状态变量取值构成的所有可能元组。这种受限的隐马尔可夫模型结构能够得到所有基本算法的一种简单而优雅的矩阵实现。它被用于语音识别。	HiddenMarkovModel
15.6	580 S12	Fixed-Lag-Smoothing 固定时间延迟平滑算法	它作为一种能够在给定新时间步的观察下输出新的平滑估计的联机算法而实现；首选它是前向－后向算法一种简单变形，使算法能够在常数空间内完成平滑，而与序列长度无关。其思想是，对任何特定时间片k的平滑都需要同时给出前向和后向消息，即f[1:k]和b[k+1:1]。 它在单一运行过程里同时向相同的方向传递f和b。 它首选执行标准的前向过程计算f[t:1]（抛弃所有的中间结果），然后对b和f同时执行后向过程，用它们来计算每一时间步的平滑估计。因为每个消息都只需要一份拷贝，存储需求就是不变的（即与序列长度t无关）。不过这个算法有一个显著的限制：它要求转移矩阵必须是可逆的，并且传感器模型没有零元素——也就是说，所有观察值在每个状态下都是可能的。 第二改进是固定延迟的联机平滑。首先，我们可以通过标准的滤波过程，即由f[1:t-d]计算f[1:t-d+1]。（15.14）这个公式提供了对B矩阵的增量更新，并进而允许我们计算新的后向消息b[t-d+2:t+1]。	FixedLagSmoothing
15	590 S18	Dynamic Bayesian Network 动态贝叶斯网络	总的来说，动态贝叶斯网络中的每个时间片都具有任意数量的状态变更Xt与变量Et。为了简化，我们将假设变更与有向边从一个时间片到另一个时间片是精确复制的，并且动态贝叶斯网络表示的是一个一阶马尔可夫过程，所以每个变量的父节点或者在该变量本身所在那个时间片中，或者在与之相邻的上一个时间片中。	DynamicBayesianNetwork
15.17	598 S23	Particle-Filtering 粒子滤波算法	首先，根据时刻0的先验分布P(X0)进行采样得到N个样本构成的总体。然后对每个时间步重复下面的更新循环： 1.对每个样本，通过转移模型P(X[t+1]|x[t]),在给定样本的当前状态值x[t]条件下，对下一个状态值x[t+1]进行采样使得每个样本前向传播。 2.对于每个样本，通过它赋予新证据的似然值P(e[t+1]|x[t+1])进行加权。 3.对总体样本进行重新采样以生成一个新的N样本总体。从当前的总体中选出每个新样本；某个样本被选中的概率与其权值成。新的样本未被赋权。	ParticleFiltering
16.9	632 S52	Information-Gathering-Agent 信息收集智能体		---
17	647 S61	Markov Decision Process 马尔可夫决策过程	对完全可观察的环境，使用马尔可夫链转移模型和累加回报的这种特定规格的延续式决策问题被称为马尔可夫决策过程。它由3个组成部分定义：初始状态S0，转移模型T(s,a,s')，回报函数：R(s)	MarkovDecisionProcess
17.4	653 S65	Value-Iteration 价值迭代	基本思想是计算出每一个状态的效用值，然后通过状态效用值来选出每个状态中的最优行动。该迭代算法，从任意的初始效用值开始，我们算出方程右边的值，再把它供稿到左边——从而根据它们的邻接状态的效用值来更新每个状态的效用值。如此重复直到达到一种均衡。最后的的效用值一定是贝尔曼方程组的解，实际上这也是唯一解。	ValueIteration
17.7	657 S68	Policy-Iteration 策略迭代	即使在效用函数估计得不是很准确的情况下也有可能得到最优策略。如果一个行动比其他行动明显要好，那么所涉及状态的效用的准确量值不需要太精确。策略迭代算法从某个初始策略π0开始，交替执行下面的两个步骤： 1.策略评价，给定策略πi，计算出Ui，即如果执行πi后每个状态的效用值。 2.策略改进，通过基于Ui的向前看一步的方法，计算新的MEU策略πi+1。 当策略改进步骤没有产生效用值的改变时，算法终止。这时的效用函数Ui是贝尔曼更新的不动点，也就是贝尔曼方程组的解，πi一这是最优策略。	PolicyIteration
17.9	663	POMDP-Value-Iteration		---
18.5	702 S95	Decision-Tree-Learning 决策树学习算法	该算法背后的基本思想是，首先测试最重要的属性。通过所谓“最重要的”，我们表达的含义是：使得某实例的分类与其他实例最不同的属性。这样我们希望能够通过较少数量的测试就能得到正确的分类，意味着树中所有的路径都很智短，而且整棵树规模比较小。	DecisionTreeLearner
18.8	710	Cross-Validation-Wrapper		---
18.11	717 S106	Decision-List-Learning	此算法属于贪婪算法，它重复寻找一个与训练集的某个子集完全一致的测试。一旦找到这样的测试，它就将该测试添加到正在构建的决策表中，并删除相应的实例。然后用剩余的实例构造决策表的其余部分。重复上述过程直到没有剩余的实例。	DecisionListLearner
18.24	734 S163	Back-Prop-Learning 多层网络中的反向传播学习算法	为了更新输入单元与隐单元之间的连接，我们定义一个类似于输出节点的误差项的量。这里就是需要我们进行误差反向传播的地方。主要思路是，隐节点j对它所连接的每个输出节点处的误差的某些部分要“承担责任”。这样，误差的值将根据隐节点和输出节点之间的强度进行划分，并且反向传播，为隐层提供误差的值。那么输入层与隐层之间的权值更新规则与输出层的更新规则几乎相同了。反向传播过程可以归纳如下：利用观测到的误差值，计算输出单元的误差值；从输出层开始，对网络中的每一层重复下面的步骤，直到到达最早的隐层：向前面的层反向传播误差值；更新两层之间的权值。	BackPropLearning
18.34	751 S102	AdaBoost 集体学习推进算法的一个变种	该算法对假设进行了合成。如果输入学习算法L是一弱学习算法——意味着L总会返回一个比随机猜测（即，对布尔分类而言是50%）要好一点、但在训练集上有加权错误的假设——那么该算法将回返一个对足够大的M能够对训练数据进行理想分类的假设。因此这个算法推进了原始的学习算法在训练数据上的准确度，无论原始假设空间的表达能力有多差，或者要学习的函数的复杂度有多高，上述结论都成立。	AdaBoostLearner
19.2	771 S114	Current-Best-Learning 当前最佳假设学习算法	该算法搜索一个一致性假设，并当无法找到一致的特殊化或一般化的时候回溯	---
19.3	773 S116	Version-Space-Learning 变形空间学习算法	算法找到V的一个子集，与examples保持一致	---
19.8	786 S125	Minimal-Consistent-Det 一个寻找最小一致决定的算法		---
19.12	793 S130	FOIL 自顶向下的归纳学习方法	用于根据实例学习一队霍恩子句的算法	---
21.2	834 S178	Passive-ADP-Agent 基于自适应动态规划的被动强化学习智能体	为了利用状态间的约束，智能体必须学习状态之间的联系。该一个自适应动态规划（ADP）智能体通过在运行中学习环境的转移模型来工作，并且运用动态规划方法求解相应的马尔可夫决策过程。对于一个被动学习智能体而言，这意味着把尝到的转移模型T(s,π(s),s')以及观察到的回报R(s)代入到贝尔曼方程中，计算状态的效用。	PassiveADPAgent
21.4	837 S179	Passive-TD-Agent 时序差分法学习效用估计的被动强化学习智能体	其基本思想是，首先定义当效用估计正确时局部成立的条件，然后，写出更新公式使估计值向理想的“均衡”方程靠近。	PassiveTDAgent
21.8	844 S184	Q-Learning-Agent 探索型Q学习智能体	它是一个主动的学习者，对每种情况下的每个行动的Q(a,s)值都进行学习。它使用与探索型ADP智能体相同的探索函数f，不过由于一个状态的Q值可以与其邻居的Q值直接关联，可以避免对转移模型进行学习。	QLearningAgent
22.1	871	HITS		---
23.5	894	CYK-Parse		---
25.9	982	Monte-Carlo-Localization		---