论文部分内容阅读
时态推理(TR)包含时间概念的形式化并为知识时态方面的表示和推理提供工具。因此,一个时态推理框架应包括以下两方面:
1通过对原有语言增加一个时态维(用来表示知识的时态方面),进行时态扩展。
2一个时态推理系统。能提供对扩展语言所形成的断言进行推理的方法,该方法能判定扩展语言中任何时态逻辑断言的真值。
另外,任何形式化的时态推理系统都能提供在非时态断言和时态基准(reference)之间建立某种关联的方法。更直观的解释就是:我们可以将建立一个时态逻辑的过程看成是定义一种方法的过程,这种方法能在非时态断言和时态基准(reference)之间建立某种联系。
在研究时态信息表示与推理的过程中,出现了多种对时间的不同理解(即:不同的时间本体),这些理解的差异主要体现在时态基元、时间的结构、时态实体和时态约束类型四个方面。
一、时态基元
形式化的时态推理在非时态断言和时态基准(reference)之间建立了一种联系。时态基准是时态元素的集合,每个时态元素与一个或多个时间关系相关。时态基元也可以看成是时态元素,主要存在两类时态基元:时刻(或称为点)和时间段(或称为区间)。
早期的时间表示是用时刻进行描述的。后来的一些研究者主张使用时间段,认为时间段更贴近常识的时态概念。llen提出时间段(区间)是唯一的时态基元,反对以时间点(或时刻)作为时态基元。1983年,VnBenthem等将区间理论进行了形式化。区间代数的表达能力比点代数强,但是它所提供的推理方法却要比点代数的方法复杂。除此之外,有些问题仍然需要用像时间点这种极短的时间段来表示。
1982年,Vilin提出将时刻和时间段同时作为时态本体。llen和Hyes对llen的区间理论进行了改进,引入了STRT和END两个函数将时间段变成时间点的表示。然而,将时刻和时间段同时作为基元在任何时间模型中都会导致诸如分离时刻问题的语义问题。1985年,llen和Hyes引入了时间片刻(moment)的概念。时间片刻是一种特殊的时刻,它具有时间点的许多特性,但又不同于时间点,因为它可以区分出一个时刻的开始点和结束点。它是一种特殊的,短到不能再分解的时间段。
二、时间的结构
在确定了时间的本体基元后,就应给出本体的结构,即时间的结构。推理工作的复杂性很大程度上取决于时间的结构。时间的结构涉及到如下几个问题:时间是离散的还是连续的?时间是有界的还是无界的?时间是线性的、分支的、平行的还是循环的?
三、时态实体
在大多数有关时态推理的研究方法中,研究者加入了对命题时态出现(occurence)的分析,根据命题出现的不同模式将命题进行分类。这些不同的分类被称作时态实体。
主要的时态实体包括:事实和事件。事实是“在某段时间为真的事情”。一个事实是世界状态的一种静态表示,如“车是红色的”。而事件则是“发生的事情”,它通常表示世界的动态情况,如“开始作画”。时态区间是可能发生某个事件的“一段时间”。如果区间和区间B的起始、终止时间相同,则它们是同一区间。但对事件X和事件Y而言,即使它们的起始、终止时间完全相同,也不一定是同一事件。
Russell将变化定义为同一实体分别在时间t与在时间t'的命题之间的真假性差别。在情形演算中变化是全局定义的,即不仅考虑单一命题的变化,而且考虑从世界的一个完全描述到另一完全描述的变化。然而,在后来的大多数方法中,都将变化局部定义为一个或一组命题的真值变化。因果关系的表达是有关变化推理的一个主要问题,因为多数变化都是通过因果关系进行解释的。在时态逻辑方法中,多数用定义在时态实体上的因果谓词表达因果关系,不同谓词表达两个不同实体间的因果关系。
四、时态约束
确定了时态基元、时间的结构、时态实体后,还要确定时态关系的类型和时态表达式的形式。许多研究工作致力于定义约束更强的时态表达式、推理算法和一致性检验。根据表达式中所用约束的性质主要可分为两类方法:建立在定性时态关系上的定性时态方法和建立在时态关系上的定量时态方法。也有一些文献将两者结合起来。
定性关系llen的区间代数学建立在区间之间13种相互独立关系的基础上。llen将简单关系的向量作为关系的析取式。例如,向量(I1beforemeetsoverlpsI2),表示时间区间I1before(在…前),meets(相遇)或者overlps(部分相交)时间区间I2。这种方法能够表达出区间时态关系上的不确定性,也能表达出两个时态区间之间所有可能的时态关系。llen给出了一种多项式时间的约束传播算法,用来计算区间代数学中一组语句的闭包,这个过程很易于实现。
点代数与区间代数的定义方法相同,只是将其中的元素换为时间点。简单的点关系有before,equl,fter三种,关系向量由简单的点关系组成,例如(p1beforeequlp2)。其约束闭包可以通过多项式时间的算法来进行计算。
Mtuszec等提出的方法建立在关于区间端点的部分信息上。例如,XsbsY表示时态区间X在时态区间Y开始之前开始(即XstrtbeforestrtY)。基于邻域的概念,Freks用半区间概念将Mtuszec的方法泛化。这种泛化的时态知识表示能够根据有意义的概念进行有效、高层次的推理。Freks为其邻域基元引入了最优转换表,用来执行“粗”的推理。Freks的邻域关系代数学与约束的区间代数学有着紧密的联系。
定量关系当时态信息以日期或其它精确数字形式出现时,就是定量关系的最简单情形。此时,断言是绝对数值的时间戳,时间段可以直接以数字形式表达,易于计算。通过比较数值,用常量时间算法就可以有效地回答出事件发生的查询。
然而,许多问题不能或者很难获得精确、可用的数字信息,很难用定量关系进行描述。尽管有许多处理数字信息的技术,但还取决于信息的可用性和精确度。
定性和定量关系的结合为了解决不同精确度知识的可用性问题,将定性约束和定量约束结合在一个系统中。此方面的研究工作主要有两个分支:
松散结合的方法Kutz和Ldkin分别保留了定性和定量区间,通过“中间件”关系将二者连接起来。其推理过程如下:首先分别进行定性、定量的推理,然后在定性、定量信息之间传递信息,最后收敛得到一个全局解。
紧密结合的方法Meiri通过定义通用时态网将定性和定量两种约束紧密结合起来,推理的难处理问题通过古典的约束满足技术加以解决。Meiri认为,他建立的模型比Kutz和Ldkin模型的概念更加清晰,各种不同推理任务的结合更加紧密。
Khn和Gorry设计并实现了一个“时间专家”模块(module),用来对时态信息进行存储、检索和推理,用区间来表示模糊时间信息,并用表推演(tbulr)方法进行模糊推理。Sheng提出了一种建立在Zdeh和Zimmermnn模糊逻辑基础上的语言学方法,可以处理模糊时态量词及不确定事件。Dutt用一个严格不相交的区间集合来描述时间,此集合即为定义模糊事件的论域。Kim和Oh提出了一个进行事件间定性时态关系不精确表示的模型。上述的一些方法用模糊集理论对llen的定性时态关系进行推广,没有考虑定量信息。
Dubois和Prde将日期(连续、线性时间的可能分布)和区间(两个日期之间时间点的模糊集合)作为表达和处理时态元素的基元,提出了一个更加通用的模型。使用与Dubois和Prde模型相同的时态基元,Oin将模糊时间与模糊命题推理结合在一起,提出了一个用模糊时间进行表达和推理的模型。该模型可以对规则中的模糊时态定量、定性关系进行操作,但不能对数据集中的模糊时态约束进行表达。
1通过对原有语言增加一个时态维(用来表示知识的时态方面),进行时态扩展。
2一个时态推理系统。能提供对扩展语言所形成的断言进行推理的方法,该方法能判定扩展语言中任何时态逻辑断言的真值。
另外,任何形式化的时态推理系统都能提供在非时态断言和时态基准(reference)之间建立某种关联的方法。更直观的解释就是:我们可以将建立一个时态逻辑的过程看成是定义一种方法的过程,这种方法能在非时态断言和时态基准(reference)之间建立某种联系。
在研究时态信息表示与推理的过程中,出现了多种对时间的不同理解(即:不同的时间本体),这些理解的差异主要体现在时态基元、时间的结构、时态实体和时态约束类型四个方面。
一、时态基元
形式化的时态推理在非时态断言和时态基准(reference)之间建立了一种联系。时态基准是时态元素的集合,每个时态元素与一个或多个时间关系相关。时态基元也可以看成是时态元素,主要存在两类时态基元:时刻(或称为点)和时间段(或称为区间)。
早期的时间表示是用时刻进行描述的。后来的一些研究者主张使用时间段,认为时间段更贴近常识的时态概念。llen提出时间段(区间)是唯一的时态基元,反对以时间点(或时刻)作为时态基元。1983年,VnBenthem等将区间理论进行了形式化。区间代数的表达能力比点代数强,但是它所提供的推理方法却要比点代数的方法复杂。除此之外,有些问题仍然需要用像时间点这种极短的时间段来表示。
1982年,Vilin提出将时刻和时间段同时作为时态本体。llen和Hyes对llen的区间理论进行了改进,引入了STRT和END两个函数将时间段变成时间点的表示。然而,将时刻和时间段同时作为基元在任何时间模型中都会导致诸如分离时刻问题的语义问题。1985年,llen和Hyes引入了时间片刻(moment)的概念。时间片刻是一种特殊的时刻,它具有时间点的许多特性,但又不同于时间点,因为它可以区分出一个时刻的开始点和结束点。它是一种特殊的,短到不能再分解的时间段。
二、时间的结构
在确定了时间的本体基元后,就应给出本体的结构,即时间的结构。推理工作的复杂性很大程度上取决于时间的结构。时间的结构涉及到如下几个问题:时间是离散的还是连续的?时间是有界的还是无界的?时间是线性的、分支的、平行的还是循环的?
三、时态实体
在大多数有关时态推理的研究方法中,研究者加入了对命题时态出现(occurence)的分析,根据命题出现的不同模式将命题进行分类。这些不同的分类被称作时态实体。
主要的时态实体包括:事实和事件。事实是“在某段时间为真的事情”。一个事实是世界状态的一种静态表示,如“车是红色的”。而事件则是“发生的事情”,它通常表示世界的动态情况,如“开始作画”。时态区间是可能发生某个事件的“一段时间”。如果区间和区间B的起始、终止时间相同,则它们是同一区间。但对事件X和事件Y而言,即使它们的起始、终止时间完全相同,也不一定是同一事件。
Russell将变化定义为同一实体分别在时间t与在时间t'的命题之间的真假性差别。在情形演算中变化是全局定义的,即不仅考虑单一命题的变化,而且考虑从世界的一个完全描述到另一完全描述的变化。然而,在后来的大多数方法中,都将变化局部定义为一个或一组命题的真值变化。因果关系的表达是有关变化推理的一个主要问题,因为多数变化都是通过因果关系进行解释的。在时态逻辑方法中,多数用定义在时态实体上的因果谓词表达因果关系,不同谓词表达两个不同实体间的因果关系。
四、时态约束
确定了时态基元、时间的结构、时态实体后,还要确定时态关系的类型和时态表达式的形式。许多研究工作致力于定义约束更强的时态表达式、推理算法和一致性检验。根据表达式中所用约束的性质主要可分为两类方法:建立在定性时态关系上的定性时态方法和建立在时态关系上的定量时态方法。也有一些文献将两者结合起来。
定性关系llen的区间代数学建立在区间之间13种相互独立关系的基础上。llen将简单关系的向量作为关系的析取式。例如,向量(I1beforemeetsoverlpsI2),表示时间区间I1before(在…前),meets(相遇)或者overlps(部分相交)时间区间I2。这种方法能够表达出区间时态关系上的不确定性,也能表达出两个时态区间之间所有可能的时态关系。llen给出了一种多项式时间的约束传播算法,用来计算区间代数学中一组语句的闭包,这个过程很易于实现。
点代数与区间代数的定义方法相同,只是将其中的元素换为时间点。简单的点关系有before,equl,fter三种,关系向量由简单的点关系组成,例如(p1beforeequlp2)。其约束闭包可以通过多项式时间的算法来进行计算。
Mtuszec等提出的方法建立在关于区间端点的部分信息上。例如,XsbsY表示时态区间X在时态区间Y开始之前开始(即XstrtbeforestrtY)。基于邻域的概念,Freks用半区间概念将Mtuszec的方法泛化。这种泛化的时态知识表示能够根据有意义的概念进行有效、高层次的推理。Freks为其邻域基元引入了最优转换表,用来执行“粗”的推理。Freks的邻域关系代数学与约束的区间代数学有着紧密的联系。
定量关系当时态信息以日期或其它精确数字形式出现时,就是定量关系的最简单情形。此时,断言是绝对数值的时间戳,时间段可以直接以数字形式表达,易于计算。通过比较数值,用常量时间算法就可以有效地回答出事件发生的查询。
然而,许多问题不能或者很难获得精确、可用的数字信息,很难用定量关系进行描述。尽管有许多处理数字信息的技术,但还取决于信息的可用性和精确度。
定性和定量关系的结合为了解决不同精确度知识的可用性问题,将定性约束和定量约束结合在一个系统中。此方面的研究工作主要有两个分支:
松散结合的方法Kutz和Ldkin分别保留了定性和定量区间,通过“中间件”关系将二者连接起来。其推理过程如下:首先分别进行定性、定量的推理,然后在定性、定量信息之间传递信息,最后收敛得到一个全局解。
紧密结合的方法Meiri通过定义通用时态网将定性和定量两种约束紧密结合起来,推理的难处理问题通过古典的约束满足技术加以解决。Meiri认为,他建立的模型比Kutz和Ldkin模型的概念更加清晰,各种不同推理任务的结合更加紧密。
Khn和Gorry设计并实现了一个“时间专家”模块(module),用来对时态信息进行存储、检索和推理,用区间来表示模糊时间信息,并用表推演(tbulr)方法进行模糊推理。Sheng提出了一种建立在Zdeh和Zimmermnn模糊逻辑基础上的语言学方法,可以处理模糊时态量词及不确定事件。Dutt用一个严格不相交的区间集合来描述时间,此集合即为定义模糊事件的论域。Kim和Oh提出了一个进行事件间定性时态关系不精确表示的模型。上述的一些方法用模糊集理论对llen的定性时态关系进行推广,没有考虑定量信息。
Dubois和Prde将日期(连续、线性时间的可能分布)和区间(两个日期之间时间点的模糊集合)作为表达和处理时态元素的基元,提出了一个更加通用的模型。使用与Dubois和Prde模型相同的时态基元,Oin将模糊时间与模糊命题推理结合在一起,提出了一个用模糊时间进行表达和推理的模型。该模型可以对规则中的模糊时态定量、定性关系进行操作,但不能对数据集中的模糊时态约束进行表达。