逻辑推理 _人工智能

人工智能不确定性推理（1）不确定性不确定环境下的行动概率公理使用全概率分布进行推理独立性贝叶斯法则及其应用不确定性（Uncertainty）定义行动At=航班起飞前t分钟启程前往机场；问：At能不能及时使agent赶上飞机？–A180是一个可靠的行动，如果所选路线上没有交通事故、没有交通管制、汽车没有出故障、没有沙尘暴，等等，等等。–(A1440或许是个一定不会耽误飞机的计划，不过要在机场过夜)逻辑方法使得Agent在得到关于环境的足够多事实时，使得行动计划得到保证。但是，没有任何agent能够获得关于其环境的全部事实。FOL与不确定性FOL能够处理不确定性吗？医学专家系统：–pSymptom(p,Toothache)Disease(p,Cavity)?–引起牙痛的原因：牙洞？穷举–牙洞与牙痛有必然联系吗？失败的原因：–懒惰(laziness):failuretoenumerateexceptions,qualifications,etc.–无知(ignorance):lackofrelevantfacts,initialconditions,etc.不确定环境下的决策基本思想：–精确度和有效性的折中理性决策的含义–既依赖于各种目标的相对重要性，也依赖于这些目标将被实现的可能性（程度）。假设A180理性决策，这意味着在给定所处的环境信息下，它是所有可执行的规划中智能体的性能度量期望达到最大的那个。性能度量：及时赶上飞机、等待时间不长，…不确定环境下的决策例如：给出行动及其成功的概率如下:P(A25getsmethereontime|…)=0.04P(A90getsmethereontime|…)=0.70P(A120getsmethereontime|…)=0.95P(A1440getsmethereontime|…)=0.9999该选哪一个行动?–例如，取决于成功的几率以及等待时间的折中。–必须考虑效用理论（Utilitytheory）–决策论＝概率论＋效用论–Decisiontheory=probabilitytheory+utilitytheory不确定性不确定环境下的行动概率公理使用全概率分布进行推理独立性贝叶斯法则及其应用概率理论（Probabilitytheory）Agent的知识提供的最多是关于语句的信度（degreeofbelief）。概率论可以处理我们的惰性和无知。概率是宇宙的真实方面：它是物体的行为表现为特定方式的倾向，而不仅仅是对观察者信心的描述。概率与证据：–在评估语句的概率时，必须指出有关证据。–Agent获得新的信息后，其概率评估应该更新。–先验概率、后验概率先验概率与命题a相关的无条件概率，在没有任何其它信息存在的情况下，关于命题的信度，记为：P（a）。例如，用P（weather）表示天气的概率：–P（weather＝sunny）＝0.7–P（weather＝rain）＝0.2–P（weather＝cloudy）＝0.08–P（weather＝snow）＝0.02先验概率分布：–P（weather）＝0.7,0.2,0.08,0.02联合概率分布，全联合概率分布概率密度函数后验（条件）概率得到与命题a相关的变量的证据，先验概率失效，需要以后验概率替代，记为：P（a|b）例如：–P（cavity|toothache）＝0.7乘法规则：–P（ab）＝P（b|a）P（a）概率公理（Axiomsofprobability）对任意命题A,B:–0≤P(A)≤1–P(true)=1，P(false)=0–P(AB)=P(A)+P(B)-P(AB)Kolmogorov公理不确定性不确定环境下的行动概率公理使用全概率分布进行推理独立性贝叶斯法则及其应用联合概率分布联合概率分布（jointprobabilitydistribution）:–表中catch是指由于牙医的钢探针不洁而导致的牙龈感染对任何命题φ,其概率是所有原子证据事件概率的和：P(φ)=Σω:ω╞φP(ω)联合概率分布（枚举）Startwiththejointprobabilitydistribution:Foranypropositionφ,sumtheatomiceventswhereitistrue:P(φ)=Σω:ω╞φP(ω)P(toothache)=0.108+0.012+0.016+0.064=0.2Startwiththejointprobabilitydistribution,Canalsocomputeconditionalprobabilities:P(cavity|toothache)=P(cavitytoothache)P(toothache)=0.016+0.0640.108+0.012+0.016+0.064=0.4联合概率分布（枚举）归一化（Normalization）(Denominator)-1＝normalizationconstantαP(Cavity|toothache)=αP(Cavity,toothache)=α[P(Cavity,toothache,catch)+P(Cavity,toothache,catch)]=α[0.108,0.016+0.012,0.064]=α0.12,0.08=0.6,0.4Generalidea:computedistributiononqueryvariablebyfixingevidencevariablesandsummingoverhiddenvariables.不确定性不确定环境下的行动概率公理使用全概率分布进行推理独立性贝叶斯法则及其应用独立性（Independence）A与B独立，当且仅当P(A|B)=P(A)orP(B|A)=P(B)orP(A,B)=P(A)P(B)例如：P(Toothache,Catch,Cavity,Weather)=P(Toothache,Catch,Cavity)P(Weather)32entriesreducedto12(weatherhas4possiblevalues);fornindependentbiasedcoins,O(2n)→O(n)绝对独立很好但很少见，例如牙科中可能涉及几百相互关联的变量，这时候如何处理？条件独立（Conditionalindependence）已知有一个牙洞，钻具感染与牙疼的概率相互独立：钻具感染与牙痛在给定牙洞的情况下是条件独立的conditionallyindependentP(Toothache,Catch|Cavity)=P(Toothache|Cavity)P(Catch|Cavity)条件独立推导联合分布，将全联合分布分解成很多更小的分布:P(Toothache,Catch,Cavity)=P(Toothache,Catch|Cavity)P(Cavity)乘法法则=P(Toothache|Cavity)P(Catch|Cavity)P(Cavity)条件独立I.e.,2+2+1=5independentnumbers条件分布将联合分布的表示空间由指数级降到线性。条件概率是处理不确定信息的基础和最鲁棒的形式。不确定性不确定环境下的行动概率公理使用全概率分布进行推理独立性贝叶斯法则及其应用贝叶斯法则（Bayes’Rule）由乘法法则P(ab)=P(a|b)P(b)=P(b|a)P(a)Bayes'rule:P(a|b)=P(b|a)P(a)/P(b)一般形式：P(Y|X)=P(X|Y)P(Y)/P(X)=αP(X|Y)P(Y)例子：用于从病因（causal）中找到诊断（diagnostic）结论:–P(Cause|Effect)=P(Effect|Cause)P(Cause)/P(Effect)–E.g.,letMbemeningitis,Sbestiffneck:P(m|s)=P(s|m)P(m)/P(s)=0.8×0.0001/0.1=0.0008贝叶斯法则与条件独立P(Cavity|toothachecatch)=αP(toothachecatch|Cavity)P(Cavity)=αP(toothache|Cavity)P(catch|Cavity)P(Cavity)ThisisanexampleofanaïveBayes（朴素贝叶斯）model:P(Cause,Effect1,…,Effectn)=P(Cause)iP(Effecti|Cause)Totalnumberofparametersislinearinn贝叶斯网络1贝叶斯网络概述2贝叶斯网络的语义3贝叶斯网络中的精确推理4贝叶斯网络的近似推理概率公式()(|)()PXYPXYPY()()(|)PXYPXPYX11()()(|)()(|)nnPYPXPYXPXPYX条件概率公式乘法公式全概率公式边缘化与条件化联合概率分布边缘化（求和消元）P(toothache)=0.108+0.012+0.016+0.064=0.2条件化：()(,)zPYPYz()(|)()zPYPYzPz贝叶斯法则由乘法法则P(ab)=P(a|b)P(b)=P(b|a)P(a)Bayes'rule:P(a|b)=P(b|a)P(a)/P(b)一般形式：更通用版本（条件化）：(|,)(|)(|,)(|)PXYePYePYXePXe(|)()(|)(|)()()PXYPYPYXPXYPYPX1()()(|)niiiPXPYPXY贝叶斯网络的由来随机方法？–每个状态值取决于前面有限个状态，如Markov链。在现实生活中，很多事物相互的关系并不能用一条链来串起来；它们之间的关系可能是交叉的、错综复杂的。–如疾病的起因，故障的原因等。贝叶斯网络的由来全联合概率计算复杂性十分巨大；变量之间的独立性和条件独立性能大大减少为了定义全联合概率分布所需的概率数目。需要一种自然、有效的方式来根据不确定性知识推理——贝叶斯网络；贝叶斯网络的定义贝叶斯网络(Bayesiannetwork)是一个有向图，其中每个节点都标注了定量概率信息：一个随机变量集合组成网络节点，变量可以是离散的或者连续的；一个连接节点对的有向边或者箭头的集合，如果存在从节点X指向节点Y的有向边，则称X是Y的一个父节点；每个节点都存在一个条件概率分布P(Xi|Parent(Xi))，量化父节点对该节点的影响；图中不存在有向环(是有向无环图DAG)。简单例子表示前例中条件独立的拓扑网络:WeatherisindependentoftheothervariablesToothacheandCatchareconditionallyindependentgivenCavity贝叶斯网络的表示——防盗网BurglaryEarthquakeMaryCallsJohnCallsAlarm0.950.940.290.001tttfftffP(A)BE0.900.05tfP(J)A0.700.01tfP(M)A0.001P(B)0.002P(E)条件概率表每个节点旁的条件概率表(简称CPT)中的值对应一个条件事件的概率–如P(A)=0.94=P(A|Burglary∧Earthquake)；–条件事件是父节点取值的一个可能组合；–每行的概率之和应为1(表中只给出了为真的情况，为假的概率应为1-p)；–一个具有k个布尔父节点的布尔变量的条件概率表中有2k个独立的可指定的概率(注意概率值是独立的)；–没有父节点的节点的概率只有1行，为先验概率。0.700.01tfP(M)A贝叶斯网络的概率解释任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力，完全的枚举需要指数级的规模（相对于领域变量个数）；贝叶斯网络提供