Learning probabilistic logic models from probabilistic examples

We revisit an application developed originally using abductive Inductive Logic Programming (ILP) for modeling inhibition in metabolic networks. The example data was derived from studies of the effects of toxins on rats using Nuclear Magnetic Resonance (NMR) time-trace analysis of their biofluids together with background knowledge representing a subset of the Kyoto Encyclopedia of Genes and Genomes (KEGG). We now apply two Probabilistic ILP (PILP) approaches—abductive Stochastic Logic Programs (SLPs) and PRogramming In Statistical modeling (PRISM) to the application. Both approaches support abductive learning and probability predictions. Abductive SLPs are a PILP framework that provides possible worlds semantics to SLPs through abduction. Instead of learning logic models from non-probabilistic examples as done in ILP, the PILP approach applied in this paper is based on a general technique for introducing probability labels within a standard scientific experimental setting involving control and treated data. Our results demonstrate that the PILP approach provides a way of learning probabilistic logic models from probabilistic examples, and the PILP models learned from probabilistic examples lead to a significant decrease in error accompanied by improved insight from the learned results compared with the PILP models learned from non-probabilistic examples.     

概率逻辑、不确定逻辑和模糊逻辑之比较

通过一个实例分析比较了概率逻辑、主观概率逻辑、不确定逻辑和模糊逻辑的思想方法。提出了自己的观点：基于数据统计的概率逻辑是最科学的。不确定逻辑比主观概率逻辑更科学。当具有不确定性的原子命题具有独立性时,不确定逻辑和模糊逻辑的观点是一致的。而对于处理带有不确定性的相关性命题,不确定逻辑比模糊逻辑更科学。但是模糊逻辑在建立推理理论方面见长。     

Borel型概率计量逻辑

视全体赋值之集为通常乘积拓扑空间,利用该空间上的Borel概率测度在二值命题逻辑中引入了公式的概率真度概念.该方法既克服了计量逻辑学要求赋值集上的概率测度必须为均匀概率测度的无穷可数乘积的局限,又弥补了概率逻辑学只讲局部而缺乏整体性的不足;证明了计量逻辑学中公式的真度、随机真度以及概率逻辑学中公式的概率等概念都可作为本文提出的概率真度的特例而纳入到统一的框架中,从而实现了计量逻辑学与概率逻辑学的融合与统一;证明了逻辑闭理论与赋值空间中的拓扑闭集是一一对应的以及概率真度函数与赋值空间上的Borel概率测度是一样多的等若干结论;本文的第4节给出了公式的概率真度的公理化定义,证明了公式集上满足Kolmogorov公理的任一[0,1]值函数均可由赋值空间上的某Borel概率测度按本文的方法所表出,从而建立了二值命题逻辑框架下的概率计量逻辑的理论体系.     

Learning hierarchical probabilistic logic programs

Machine Learning - Probabilistic logic programming (PLP) combines logic programs and probabilities. Due to its expressiveness and simplicity, it has been considered as a powerful tool for learning...     

Borel probabilistic and quantitative logic

The present paper introduces the notion of the probabilistic truth degree of a formula by means of Borel probability measures on the set of all valuations,endowed with the usual product topology,in classical two-valued propositional logic.This approach not only overcomes the limitations of quantitative logic,which require the probability measures on the set of all valuations to be the countably infinite product of uniform probability measures,but also remedies the drawback that probability logic behaves onl...     

Reasoning about probabilistic sequential programs in a probabilistic logic

We introduce a notion of strong monotonicity of probabilistic predicate transformers. This notion enables us to establish a normal form theorem for monotone probabilistic predicate transformers. Three other healthiness conditions, namely, conjunctivity, disjunctivity and continuity for probabilistic predicate transformers are also examined, and they are linked to strong monotonicity. A notion of probabilistic refinement index is proposed, and it provides us with a continuous strength spectrum of refinement relations which may be used to describe more flexible refinement between probabilistic programs. A notion of probabilistic correctness is introduced too. We give a probabilistic weakest-precondition, choice and game semantics to the contract language, and present a probabilistic generalization of the winning strategy theorem. Received: 16 April 2002 / 20 January 2003 RID="a" ID="a" This work was partly supported by the National Key Project for Fundamental Research of China (Grant No: 1998030905) and the National Foundation of Natural Sciences of China (Grant No: 60273003)     

基于纳米电路的概率逻辑

具有概率特性的逻辑学适合表示纳米器件的状态.本文介绍了该逻辑学和其在计算纳米级门电路的概率分布方面的应用.此应用是基于马尔可夫随机场的新特性:势团势能,初始节点的概率密度.我们利用初级门电路和判断电路证明了该方法的有效性.分析证明器件的概率分布主要依赖于系统结构和温度参数.     

A Petri net model for probabilistic logic

In this article we investigate the use of Petri nets for the representation of possible worlds in probabilistic logic. We propose a method to generate possible worlds based upon the reachability tree of the Petri net model. The number of columns in the matrix of possible worlds grows exponentially with the problem size. Nilsson [Proceedings of 1976 National Computer Conference and Readings in Artificial Intelligence, Morgan Kaufmann, Los Altos, CA, 1981, pp. 192-199] suggested a method to generate only those columns of the possible world matrix that are likely to be important for the solution. We provide Petri net models for the method suggested by Nilsson and show that they lead to intuitive and simple computational methods. © 1996 John Wiley & Sons, Inc.     

Lifted discriminative learning of probabilistic logic programs

Machine Learning - Probabilistic logic programming (PLP) provides a powerful tool for reasoning with uncertain relational models. However, learning probabilistic logic programs is expensive due to...     

N-tuple features for OCR revisited

N-tuple features for optical character recognition have received only scattered attention since the 1960s. Our main purpose is to show that advances in computer technology and computer science compel renewed interest. N-tuple features are useful for printed character classification because they indicate the presence or absence of a given rigid configuration of n black and white pixels in a pattern. Desirable n-tuples fit each pattern of a specified (positive) training set of characters in at least p different shift positions, and fail to fit each pattern of a specified (negative) training set by at least n-q pixels in each shift position. We prove that the problem of finding a distinguishing n-tuple is NP-complete, by examining a natural subproblem with binary strings called the missing configuration problem. The NP-completeness result notwithstanding, distinguishing n-tuples are found automatically in a few seconds on contemporary workstations. We exhibit a practical search algorithm for generating, from a small training set, a collection of n-tuples with low class-conditional correlation and with specified design parameters n, p, and q. The generator, which is available on the Internet, is empirically shown to be effective through a comparison with a benchmark generator. We show experimentally that the design parameters provide a useful tradeoff between distinguishing power and generation time, and also between the conditional probabilities for the positive and negative classes. We explore the feature probabilities obtainable for various dichotomies, and show that the design parameters control the feature probabilities     

On finite-state approximants for probabilistic computation tree logic

We generalize the familiar semantics for probabilistic computation tree logic from finite-state to infinite-state labelled Markov chains such that formulas are interpreted as measurable sets. Then we show how to synthesize finite-state abstractions which are sound for full probabilistic computation tree logic and in which measures are approximated by monotone set functions. This synthesis of sound finite-state approximants also applies to finite-state systems and is a probabilistic analogue of predicate abstraction. Sufficient and always realizable conditions are identified for obtaining optimal such abstractions for probabilistic propositional modal logic.     

Verifying concurrent probabilistic systems using probabilistic-epistemic logic specifications

In this paper, we address the problem of verifying probabilistic and epistemic properties in concurrent probabilistic systems expressed in PCTLK. PCTLK is an extension of the Probabilistic Computation Tree Logic (PCTL) augmented with Knowledge (K). In fact, PCTLK enjoys two epistemic modalities K_i for knowledge and \(Pr_{\triangledown b}K_{i}\) for probabilistic knowledge. The approach presented for verifying PCTLK specifications in such concurrent systems is based on a transformation technique. More precisely, we convert PCTLK model checking into the problem of model checking Probabilistic Branching Time Logic (PBTL), which enjoys path quantifiers in the range of adversaries. We then prove that model checking a formula of PCTLK in concurrent probabilistic programs is PSPACE-complete. Furthermore, we represent models associated with PCTLK logic symbolically with Multi-Terminal Binary Decision Diagrams (MTBDDs), which are supported by the probabilistic model checker PRISM. Finally, an application, namely the NetBill online shopping payment protocol, and an example about synchronization illustrated through the dining philosophers problem are implemented with the MTBDD engine of this model checker to verify probabilistic epistemic properties and evaluate the practical complexity of this verification.     

A new approach to hybrid probabilistic logic programs

This paper presents a novel revision of the framework of Hybrid Probabilistic Logic Programming, along with a complete semantics characterization, to enable the encoding of and reasoning about real-world applications. The language of Hybrid Probabilistic Logic Programs framework is extended to allow the use of non-monotonic negation, and two alternative semantical characterizations are defined: stable probabilistic model semantics and probabilistic well-founded semantics. These semantics generalize the stable model semantics and well-founded semantics of traditional normal logic programs, and they reduce to the semantics of Hybrid Probabilistic Logic programs for programs without negation. It is the first time that two different semantics for Hybrid Probabilistic Programs with non-monotonic negation as well as their relationships are described. This proposal provides the foundational grounds for developing computational methods for implementing the proposed semantics. Furthermore, it makes it clearer how to characterize non-monotonic negation in probabilistic logic programming frameworks for commonsense reasoning. An erratum to this article can be found at     

Probabilistic Belief Logic and Its Probabilistic Aumann Semantics

In this paper, we present a logic system for probabilistic belief named PBL,which expands the language of belief logic by introducing probabilistic belief. Furthermore, we give the probabilistic Aumann semantics of PBL. We also list some valid properties of belief and probabilistic belief, which form the deduction system of PBL. Finally, we prove the soundness and completeness of these properties with respect to probabilistic Aumann semantics.     

基于概率软逻辑的多层次识别和推理

随着全球老龄化人口增长,老年人的日常行为监管和护理也成为极具挑战性的社会问题。为了应对这种不断增长的社会需求,提出了一种由数据和知识共同驱动、使用概率软逻辑（Probabilistic Soft Logic）和多层次分析对老年人的日常活动进行建模的方法,来解决老年人护理中的活动识别问题。实验表明,该方法在活动识别和异常活动检测上,比隐马尔可夫模型能产生更高的精度,并且,该方法比非层次识别方法具有更快的响应速度。     

Representation and extraction of information by probabilistic logic

In general, a probabilistic knowledge base consists of a joint probability distribution on discrete random variables. Though it allows of easy computability and efficient propagation methods, its inherent knowledge is hardly accessible for the user. The concept introduced in this paper permits an interactive communication between man and machine by use of probabilistic logic: The user is able to convey all know-how available to the system, and conversely, knowledge embodied by the distribution is revealed in an understandable way. Uncertain rules constitute the link between commonsense and probabilistic knowledge representation. The concept developed in this paper is partly realized in the probabilistic expert system shell SPIRIT. An application of SPIRIT to a real life example is described in the appendix.     

Polytime model checking for timed probabilistic computation tree logic

We consider the model checking problem for Timed Probabilistic Computation Tree Logic (TPCTL) introduced by H.A. Hansson and D. Jonsson, and studied in a recent book by H.A. Hansson [Han94]. The semantics of TPCTL is defined in terms of probabilistic transition systems. It is shown in [Han94] that model checking for TPCTL has exponential time complexity, the latter being measured in terms of the size of formula, the size of transition system and the value of explicit time that appears in the formula. Besides that, [Han94] describes some polytime decidable classes, the proofs being rather voluminous. We show, by a short proof, that this model checking problem is polytime decidable in the general case. The proof is essentially based on results on the complexity of Markov decision processes. Received: 2 May 1996 / 5 January 1998