URL, URN, URI, IRI

“网址”到底是什么？一般的理解是URL（Uniform resource locator）

在RDF/OWL1/OWL2中却使用了不同的概念

• RDF和OWL 1使用了URI （Uniform resource identifier，也就是最初的语义网层次蛋糕的第一层）
• OWL 2使用了IRI（Internationalized Resource Identifier）

还有一个相关概念 URN（Uniform Resource Name）。他们有什么区别？

简述如下：

URL是这样的形式：

scheme://domain:port/path?query_string#fragment_id

如本页的编辑页面是  https://blog.baojie.org:80/wp-admin/post-new.php?post_type=post#

URI是URL的扩展，形式是：

<scheme name> : <hierarchical part> [ ? <query> ] [ # <fragment> ]

例：
foo://username:password@example.com:8042/over/there/index.dtb?type=animal&name=narwhal#nose
Wikipedia上列有官方和非官方的URI scheme，如about, ed2k, doi, skype，都是。

URI不一定指向一个网址

URN是一种URI，形式如 urn:isbn:0451450523（书号），urn:mpeg:mpeg7:schema:2001（MPEG-7标准）。URN使我们可以描述一个资源而不必关系它的具体存档地址。

IRI是URI的扩展：URI只能用ASCII，而IRI可以用Universal Character Set (USC), Unicode——比如中文。

所以RDF和OWL里的资源，都不只是用“网址”来命名的。理论上，每个人都可以自己定义一个scheme来唯一确定自己的资源，不一定要放在网上，比如对我的冰箱，我可以命名为

urn:baojie-bengbu-iowa:冰箱:2012

更多关于URL/URI/IRI的请看W3C官方网页：Naming and Addressing: URIs, URLs, …

另参Tim Berners-Lee的Design Issues，Document Naming （1991）

从挖地雷到分布式文件存储(删去编码)

erasure channel一般翻译为删去信道或消去信道，Erasure code一般翻译为删去编码或者存疑编码。

（1）删去信道

删去信道是会以一定概率丢失比特或者信包packet的信道。例如二进删去信道Binary erasure channel。输入信号符号是{0,1}，输出符号是{0,1,e}，e代表信号丢失。对下图BEC，信道容量是1-p_e。

信道容量的证明：以1-p的概率，传一次就成功。如不成功，再传一次成功，概率为p(1-p)，也就是用2次。这样，要以极小出错概率传输，需要传

(1-p)+p(1-p)2+p^2(1-p)*3+….

这个无穷级数收敛于1/(1-p)。也就是说，在单位时间里，可以传输1-p个比特。

(2) 里德-所罗门码（Reed–Solomon (RS) codes）

“Polynomial Codes over Certain Finite Fields.” (Reed & Solomon 1960)

原理见Wikipedia: erasure code Example: Err-mail (k=2)

基本原理是对信号做过采样：“编码过程首先在多个点上对这些多项式求冗余，然后将其传输或者存储。对多项式的这种超出必要值得采样使得多项式超定（过限定）。当接收器正确的收到足够的点后，它就可以恢复原来的多项式，即使接收到的多项式上有很多点被噪声干扰失真。” （Wikipedia中文）

“RS码的两种定义方式有着非常大的区别，而它们的等价关系并不是显而易见的。在第一种定义中，码字是多项式的值，而在第二种定义中，码字是多项式的系数。另外，第一种定义要求多项式具有特定的比较小的幂次，而在第二种定义中，多项式需要有特定的根。这两种定义的等价性可以通过有限域上的离散傅立叶变换来证明。”（Wikipedia中文）【注意，傅立叶变换是一种线性变换】

联想：这种多项式分解，似乎可以类比为傅立叶分解。如果根据某种准则（和语义相关）使个多项式系数重要性不同，则有可能实现有损语义压缩。一般的，我们认为高阶项系数相对不重要。

（3）低密度奇偶检查码 low-density parity-check (LDPC) code 

汉明码（Hamming Code）的检查码和原比特位的每一位都相关。比如(7,4)码，3位检查码中每一位和4位数据码的每一位相关。如果只和一小部分相关，就是LDPC。

（4）喷泉码 Fountain code

对k个原始数据码，喷泉编码器会产生无数多编码序列，只要其中>=k个序列被接收，就可以恢复原始数据。这有很多用处，比如分布式文件存储：把文件分为很多小块，只要收集的足够多的任意小块，就可以恢复原始文件。

具体的例子包括：Luby transform (LT) codes，Raptor codes (线性时间) and Online codes。参考Mackay书第50章。

Online编码图示如下，其他喷泉码类似：

LT码其实非常简单：

1. 假设原始数据有K个包，编码后的数据有N个包。实践中证明，N比K大5%就够了
2. 取一个随机整数d。随机取原始包中d个包。把这d个包做XOR（异或），得到一个新的包。注意，这里的随机是伪随机，也就是解码器和编码器都知道这个“随机”序列。
3. 做第2步N次。

解码过程类似挖地雷游戏，进行约束推理。

有些角上的方块，标记只有一个“1”（周围只有一个地雷），那可以肯定确定那个角是地雷。由此第次推理，可以发现越来越多的地雷。但是有些情况，有无地雷都可能，那就是不能唯一解码了。又有时，一个“1”都没有，那连解码都没法开始了。

关键在如何选择d的分布，使在极大的概率下，解码可以开始，而且可以确定性地恢复所有的原始包。

参考：喷泉编码（百度百科）

（5) 结论

（Mackay, p596）：The best solution to the communication problem is: combine a simple, pseudo-random code with message-passing decoder.

笔记：概率时空逻辑

参前文

• 从概率时态逻辑到概率域态逻辑（Probabilistic Context Logic）
• 笔记：加注(Annotated) RDF (3) Dekhtyar 2001
• 笔记：加注(Annotated) RDF (4) Dekhtyar 2001续
• 笔记：加注(Annotated) RDF (5) APT Logic

【会议版】Austin Parker, Guillaume Infantes, V. S. Subrahmanian, John Grant: An AGM-Based Belief Revision Mechanism for Probabilistic Spatio-Temporal Logics. AAAI 2008: 511-516 [bibtex]

【期刊版】John Grant, Francesco Parisi, Austin Parker, V. S. Subrahmanian: An AGM-style belief revision mechanism for probabilistic spatio-temporal logics. Artif. Intell. 174(1): 72-104 (2010)[bibtex]<

本文可以看成概率域态逻辑（probabilistic context logic, PCL）的一种特例。

【待补充】

关于Probabilistic Logic's consistency，在First-order probabilistic logic里就有不少讨论。大意是，不同的逻辑公式可以被指定不同的概率值，比如p(A)=0.2, P(B)=0.1，那0<P(A^B)<0.2, 0.1<P(A v B)<0.3。如果P(a^b) =0.5，那这个theory就不consistent。

【待续】

语义网与推荐（2）基本思路

续《语义网与推荐（1）乱拳打死老师傅》

看了几篇和语义技术在推荐系统中的应用。总的感觉是不靠谱。我的感觉是工业界对这些想法现在还没有多少兴趣。假如前提是有linked data和ontology，那这个代价非常高，而且数据的质量很成问题，不是说DBPedia的数据拿来就能用的。就算能用，速度也是大问题，SPARQL的速度还不能做到实时响应。

Recommender大体分为

• content-based
• collaborative or social
• knowledge-based
• trust-based

从机器学习的角度，推荐是一个分类或者聚类的过程；从信息检索的角度，推荐是一个发现对象和对象之间相关度的过程。逻辑推理在这里面基本没有什么作用。如果有，也大概就是分类树。

我很痛恨有些文章，因为用到RDF就说自己是语义网的应用。那还不如说，因为你的本体是存成文件的，所以你的系统是文件系统的应用。

下面是几篇我看的文章

E. Peis; J. M. Morales-del-Castillo; J. A. Delgado-López. Analysis of the state of the topic [en linea]. “Hipertext.net”, num. 6, 2008. <http://www.hipertext.net&gt; [bibtex] 【语义推荐的一个简要综述】

Gediminas Adomavicius, Alexander Tuzhilin: Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions. IEEE Trans. Knowl. Data Eng. 17(6): 734-749 (2005) [bibtex] 【这个是推荐系统的一般综述；这两个人写了很多推荐系统的文章，见link】

Houda OUFAIDA, Omar NOUA. Exploiting Semantic Web Technologies for Recommender Systems. A Multi ViewRecommendation Engine .2009【一般般】

Alexandre Passant: dbrec – Music Recommendations Using DBpedia. International Semantic Web Conference (2) 2010: 209-224 [bibtex][ppt] 【用且只用linked data，发现对象之间的相似度。其中lessons一节值得看看】

Alexandre Passant, and Yves Raimond. Combining Social Music and Semantic Web for Music-related Recommender Systems. SDoW 2008 [bibtex][ppt]

Benjamin Heitmann, Conor Hayes. Using Linked Data to build open, collaborative recommender systems. In Proceedings of the AAAI Spring Symposium ”Linked Data Meets Artificial Intelligence” 2010

Òscar Celma, Xavier Serra: FOAFing the music: Bridging the semantic gap in music recommendation. J. Web Sem. 6(4): 250-256 (2008) [bibtex]【比较早的一个工作；这个人是专门做推荐的，文章很多】

Loizou, A. and Dasmahapatra, S. (2006) Recommender Systems for the Semantic Web. In:ECAI 2006 Recommender Systems Workshop, Aug 28th – Sep 1st 2006, Trento, Italy.

Jennifer Golbeck. Social Recommender Systems on the Semantic Web 【PPT】【Jen还有很多Trust-based recommendation工作，容后看】

笔记：描述逻辑的云计算(4)Aslani方法

Mina Aslani, Volker Haarslev: Towards Parallel Classifcation of TBoxes. Description Logics 2008 [bibtex] 【sound but not complete，略过】

Mina Aslani, Volker Haarslev: TBox Classification in Parallel: Design and First Evaluation. Description Logics 2010 [bibtex] 【ECAI文章的workshop版，也可略过】

Mina Aslani, Volker Haarslev: Parallel TBox Classification in Description Logics – First Experimental Results.  ECAI 2010: 485-490 [bibtex]

这篇文章是reasoner level并行，而不是proof level并行。在对一个TBox做分类（classification）时，如果有n个概念，就有n(n+1)/2个子类关系测试。本文分析如何将这些测试分给多个独立的线程（thread）。在内存使用上，基于global tree（全局树）。

本文提到所谓的ParTree (parallel tree)方法，就是每个线程构造一个本地树，最后将这些本地树组合成一个全局树。P-DL推理算法，就是一种proof-level, ParTree的方法。

由于本文不涉及树图算法本身的并行化，参考意义不大。

笔记：描述逻辑的云计算(3)Liebig 2007

Thorsten Liebig, Felix Müller: Parallelizing Tableaux-Based Description Logic Reasoning. OTM Workshops (2) 2007: 1135-1144 [bibtex]

This paper describes our approach for concurrent computation of the nondeterministic choices inherent to the standard tableau procedure.

Thorsten Liebig, Andreas Steigmiller and Olaf Noppens. Scalability via Parallelization of OWL Reasoning In Workshop on NeFoRS: New Forms of Reasoning for the Semantic Web: Scalable & Dynamic 2010

So far the design is tailored to a SMP (symmetric multi processor) architecture, where all processing cores have access to one main memory.

2007文目标逻辑是SHN，2010文目标是SHIQ（也就是增加inverse property and qualified number restriction）

主要利用树图算法中的不确定选择，例如disjunction rule或者at-most number restriction rule。这些选择会导致不同的ABox被产生。这些ABox被放在一个优先级队列（priority queue）里。初始ABox的优先级为0，n级ABox产生的ABox级别为n+1。

所谓ABox，其实就是Tableau。

本文没有具体讨论backtracking。如果一个ABox被发现inconsistent，是不是可以简单回到它的“父”ABox?

【构架】偷2010文图

【深入讨论】

所谓并行，就是要在尽可能减少通信代价的前提下，把操作分布到不同的处理器上去。在树图算法中，有几类很明显的可并行处理

• 不确定选择（nondeterministic choices），例：A v B(x) -> A(x)或B(x)
• 不同分支（branch）例：∃R.C ^ ∃R.D (x)  -> R(x,y), C(y)和R(x,z), D(z)，则y和z两个分支可以分别处理。这一点在没有inverse property的时候成立。

有几类很明显的不适合并行处理

• 远程计数（remote counting），例如A(x)在节点1，R(x,y)在节点2，R(x,z)在节点3，要问 =2R (x)是否成立，需要做两次远程查询。
• 如果TBox本身是分布在不同节点上，而且需要远程连接时(remote join)

【分类】

一般做并行推理，大体是要么做数据的分布（distributed data），在树图算法里就是TBox的分布（ABox一定是分布的）；要么做计算的分布（distributed computation），在triple-store里就是推理规则的分布，在树图算法里就是树图扩展的分布。如果TBox较小，可以由各节点共享TBox以减少通信代价。

模块化本体算法，将TBox分布，并改造语义以保证局域化（可以减少通信代价）。如果着眼于直接减少通信代价，可能有其他的DL子集，并不需要局域语义。

Liebig说，分布式推理有reasoner level的和proof level的。他的工作是proof level的。我的P-DL推理也是proof level的。DDL的推理是reasoner level的。

Reasoner level的实现比较容易，但是不能最充分的利用并行特性。

笔记：描述逻辑的云计算(1)背景

Description Logic in the Cloud 这是很扯蛋的说法

或者说描述逻辑的并行计算（Parallel Computing with Description Logic），主要是指查询和推理两种任务。

对于RDFS或者OWL-RL的某个子集，利用MapReduce或者其他基于集群的（cluster-based）的计算，工作不少。不过一般都是基于规则(rule-based)的推理，不保证推理的完备性(completeness)。很多只支持非常有限的推理，比如BBN的SHARD工作。

模块化本体（modular ontology）语言，如Distributed Description Logics, E-Connections and Package-based Description Logics，基于非经典局域语义(Local Model Semantics)，可做分布式推理。但是局域语义的复杂性，使它们不适合现在的工程应用。

所以这个系列，主要是在普通全局语义下，探讨完备的推理算法。其中包括对Tableau Algorithm (树图算法)的并行化的一些讨论。

下面附对Rule-based并行推理的一个简短比较（摘自我自己的一个报告）。这些工作，主要是parallel triple-store，而不是parallel reasoner。

———————————

Distributed RDF Reasoning

Most existing work on distributed RDF reasoning relies on parallelization of rule-based reasoning or partition of data on a cluster.

WebPIE (Web-scale Parallel Inference Engine) by Urbani et al [7, 6] performs rule-based forward reasoning based on the MapReduce programming model. It is implemented using the Hadoop framework.  They have shown inference on a triple set of 100 billion triples and in 1.35 hours on 64 nodes against 10 billion triples. This system does not support querying.

SAOR (by Hogan et al.) [1] computes the closure of an RDF graph using two passes over the data on a single machine. A fragment of the OWL Horst semantics is implemented to allow more efficient materialization and to prevent “ontology hijacking”.

In MaRVIN [10, 4], Kotoulas, Oren and others have presented a technique based on data-partitioning in a peer-to-peer network. A load-balanced auto-partitioning approach was used without upfront partitioning costs.

In Williams, Weaver et al [5], straightforward parallel RDFS reasoning on a cluster is presented. This approach replicates all schema triples to all processing nodes and distributes instance triples randomly. Each node calculates the closure of its partition using a conventional reasoner and the results are merged. To ensure that there are no dependencies between partitions, triples extending the RDFS schema are ignored. This approach does not support complete RDFS reasoning.

Newman et al. [2] decompose and merge RDF molecules using MapReduce and Hadoop. They perform SPARQL queries on the data but performance is reported over a dataset of limited size (70,000 triples).

Husain et al. [8] report results for SPARQL querying using MapReduce for datasets up to 1.1 billion triples.

References

1. A. Hogan, A. Harth, and A. Polleres. Scalable authoritative OWL reasoning for the web. International Journal on Semantic Web and Information Systems, 5(2), 2009.
2. A. Newman, Y. Li, and J. Hunter. Scalable semantics the silver lining of cloud computing. In Proceedings of the 4th IEEE International Conference on eScience. 2008.
3. Adjiman, P., Chatalic, P., Goasdou, F., Rousset, M.-C., and Simon, L. (2006). Distributed Reasoning in a Peer-to-Peer Setting: Application to the Semantic Web . Journal of Artificial Intelligence Research, 25:269,314.
4. E. Oren, S. Kotoulas, G. Anadiotis, R. Siebes, et al. Marvin: Distributed reasoning over large-scale semantic web data. J. Web Sem., 7(4):305-316, 2009.
5. G. Williams, J. Weaver, M. Atre, J. A. Hendler. Scalable Reduction of Large Datasets to Interesting Subsets, In Web Semantics: Science, Services and Agents on the World Wide Web, , 2010
6. J. Urbani, S. Kotoulas, E. Oren, F. van Harmelen, Scalable Distributed Reasoning Using MapReduce, in: Proceedings of the 8th International Semantic Web Conference, 2009.
7. J. Urbani, S. Kotoulas, J. Maassen, F. van Harmelen, H. Bal, OWL reasoning with WebPIE: calculating the closure of 100 billion triples, in: Proceedings of the 7th Extended Semantic Web Conference, 2010.
8. M. F. Husain, P. Doshi, L. Khan, and B. Thuraisingham. Storage and retrieval of large rdf graph using hadoop and mapreduce. In M. G. Jaatun, G. Zhao, and C. Rong, (eds.) Cloud Computing, vol. 5931, chap. 72, pp. 680-686. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
9. R. Soma and V. Prasanna. Parallel inferencing for OWL knowledge bases. In International Conference on Parallel Processing, pp. 75{82. 2008.
10. S. Kotoulas, E. Oren, and F. van Harmelen. Mind the data skew: Distributed inferencing by speeddating in elastic regions. In Proceedings of the WWW. 2010.

笔记：域态逻辑的语义（3）QLC 1996

Buvac, S. (1996). Quantificational logic of context. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI).

概述：本文扩展PLC（Propositional Logic of Context）到一阶逻辑。Context本身也可以作为一阶逻辑的对象。

Context语义上是一组真值赋值。每个QLC的model，把每个context上对应一组一阶结构（first-order structures）。也就是普通一阶模型会属于一个或多个context。

ist(c, f) is true, iff f is true in all first-order structures of c. 这都和PLC一样。

语法：一阶语言分为两个sort（类）: context sort and discourse sort。公式包括普通一阶公式加上ist(k,w) 其中k是context sort上的term（可能是变量），w是公式。

语义：解释interpretation定义在两个集合上：C(ontext)和D(iscourse)。QLC的模型将每个C上的元素映射到一阶结构的集合，并要求：

• 所有的context的一阶结构有同样的domain（分别对C和D）
• C和D互斥
• C上所有的元素都有对应结构的集合（可能为空）
• 常数在所有的解释里都对应到 同样的对象。

模型上有些条件约束，最关键是的关于ist的这条：M |= ist(k,w)[q] if for all B\in models of k[q], B |= k:w[q]，其中q是变量赋值。

由此可定义proof theory。

笔记：域态逻辑的语义（1）PLC 1993

参前：域态逻辑的模型论，为什么要用模型论语义

McCarthy的初始文章：

• A LOGICAL AI APPROACH TO CONTEXT [最简单介绍]
• Notes on Formalizing Context [IJCAI93简介]
• Formalizing Context (Expanded Notes)  [97比较详细的发展]

以上文章都没有正式的语义。

Buvac和Mason的形式化:

Propositional Logic of Context [AAAI 1993]

语法: 命题逻辑加上ist(c, f) – c是context，f是公式

ist ([c1,c2],f) := ist(c1, ist(c2, f))

另外，有些命题proposition可能只在某些context中有意义。所以，对每个context，有一个相关的词汇vocabulary。只有这些词汇才会被做语义解释。

语义：一个模型model是一个从context序列到真值赋值集合（partial truth assignment）的映射。对命题逻辑，真值赋值就是一个命题的集合（set of propositions）. 例

<c1,c2> -> {A},{B}
<c3> ->{B},{A,B}
<c1,c2,c3> -> {A, B}

换句话说，每个context序列是所有普通model的集合的子集。比如，如果有n个model，那有2^n种可能的context序列（等价类）。

一个公式在一个context序列中真，仅当它在这个序列中每个模型中都为真。

由于vocabulary只在某些context序列中被解释，所以这个语义其实是三值的：true, false, meaningless。

再换句话说，这个语义是把所有可能的模型分成若干子集（可能有交叉）。在讨论公式的validity时，不讨论所有的模型，而只是某些子集（context sequences）。

该语义中有一系列公理，如ist(c1, f1) ^ ist (c1, f2) -> ist (c1, f1 ^ f2) 等。文中提出了一组Inference Rules，并证明了其完备性completeness

【评价：该语义中真正的域，是所谓的context sequence。真值相对于context sequence存在。这样有利于做进入域和退出域的推理（enter/leave context）。如果把context sequence都给以名字，那就可以退化成只有原子域（atomic context, or named context）的逻辑。所以意大利学派，说，这个法子的表法力没有他们的Local Model Semantics高。换句话说，本文里，唯一的从原子域构造复杂域的方法是串联。这个语义里，context本身没有其他的组合方法。】

笔记：加注(Annotated) RDF (7) Guha 2004

Ramanathan V. Guha, Rob McCool, Richard Fikes: Contexts for the Semantic Web. International Semantic Web Conference 2004: 32-46

Guha是Context建模的先驱。这个文章，无非是McCarthy和Guha的博士论文工作在语义网上的自然应用。我感兴趣的，是第六节Model Theory。

在一般的RDF语义中， IS是一个从URI到IR v IP 的映射（我把它称为“释名函数”）。Guha的语义里，IS是一个从URIxURI到IR v IP 的映射，第一个URI是资源（class, property等），第二个URI是context. 最关键的语义条件是这一条：

If E is a ground triple (s p o) in the context c then I(E,c) = true if c, s, p and o are in V, IS(p,c) is in IP and < IS(s, c), IS(o, c) > is in IEXT(IS(p,c)). Otherwise I(E,c)= false.

注意，IEXT（外延函数）并不是contextual的，上面的条件中，和普通RDF语义唯一的区别是IS（释名函数）。

在不同的context中，一个URI可以映射到不同的资源上，所以可以对应到不同的外延上。

这里Guha没有具体说context本身之间是不是可以有关系，比如context的层次关系，如果< IS(c1, u), IS(c2, u) > is in IEXT(IS(narrower,u)) then IS(x,c1)(如果存在)= IS(x,c2)。或可定义contex上的一阶关系

笔记：加注(Annotated) RDF (6) Sahoo 2010

S.S. Sahoo, O. Bodenreider, P. Hitzler, A. Sheth, K., Thirunarayan, “Provenance Context Entity (PaCE): Scalable provenance tracking for scientific RDF data.”,in the 22nd International Conference on Scientific and Statistical Database Management (SSDBM) 2010

讲RDF的Context（或者annotation）建模的文章虽多（几十篇总是有的），涉及语义的很少。这一篇，定了“源谱域实体”Provenance Context Entity (PaCE) [注：provenance=源谱, context=域]。

语法：Provenance当然是很重要的一种context。本文中，provenance用provenir来建模，本身就是一个RDF/OWL文档。[Provenir是Sahoo自己提出来的。关于不同的源谱模型的比较，参Li Ding和我的这篇文章 (IPAW2010)]

语义：是对RDF语义的一个扩展。大意是如果两个triple有某种共同的源谱，那它们其他的源谱可能也是也是共同的。具体来说，if pc (s1, p1, o1) = pc (s2, p2, o2), then (s1 p v) = (s2 p v) 其中pc是triple的源谱域，p是一个源谱property（比如createdBy）,v是一个值（比如“张三”）。

【评价】我认为这语义只适用于一些特定的场合，或者可用于启发式推理。但是，很难扩展到一般的情况，而且不适合做基于模型论的逻辑推理。当然，工程上可能需要这种简单的框架。

笔记：加注(Annotated) RDF (5) APT Logic

Paulo Shakarian, Austin Parker, Gerardo I. Simari, V. S. Subrahmanian: Annotated probabilistic temporal logic. ACM Trans. Comput. Log. 12(2): 14 (2011)

参从概率时态逻辑到概率域态逻辑（Probabilistic Context Logic）。今天重读此文。另参前篇笔记：加注(Annotated) RDF (3) Dekhtyar 2001及续。

和前述各篇不同的是，APT Logic中的概率不简单视为标注（annotation），而是有possible world semantics。一个线程是一个状态变化的流（时间到模型model的映射），所有可能的线程构成概率空间，概率分布定义在线程上。 文章的核心贡献是频率函数frequency function，在线程内部可以做概率推理。

频率函数用来建模说：F为真正好t时间单位后，G为真的频率。在一个线程T里，F会出现很多次，G也出现很多次。这个频率，记为fr(T,F,G,t)。所谓点(pointed)频率函数定义为

Existential Frequency Function说，F为真后t时间单位内，G为真的频率。公式略。

APT Rule: 其中I(Th)是线程Th的概率，fr(Th, F,G,Δt)是线程内频率。两者相乘，是G在F后Δt时间为真的频率的数学期望。

【评价】我认为频率函数没有定义的必要。如果系统的“状态”（model）是遍历的，那在任一个时刻x做采样，看F为真的概率，然后过t时刻做第二次采样，看G为真的概率，就可以得到P(G_x+t|F_x)。这个文章引入频率函数，我并不认为增加了表达力，反而搞得很复杂。

笔记：加注(Annotated) RDF (4) Dekhtyar 2001续

Alex Dekhtyar, Robert B. Ross, V. S. Subrahmanian: Probabilistic temporal databases, I: algebra. ACM Trans. Database Syst. 26(1): 41-95 (2001)

【续笔记：加注(Annotated) RDF (3) Dekhtyar 2001】

概率分布函数：在时间域（在本文中是calendar）上，每个时间点的概率值。注意，本文只讨论离散的分布函数。

常见的分布函数：

• 均匀（uniform）分布，例如“下雨”这件事，按星期一到星期日算，差不多是均匀分布。
• 几何（geometric）分布，p_i = p (1-p)ⁱ
• 二项（bionominal）分布 p_i = C(n,i) pⁱ (1-p)^n-i
• 几何（geometric）分布 p_i =  e^-λ λⁱ / i!

如果已知e1和e2的概率，那e1∧e2的概率是多少？有conjunctive和disjunctive两种策略。具体看section 2.4 and 2.5

时态概率关系（TP-Relations）

TP-tuple

语义：从 TP-tuple（数据域x时间域）->概率[0,1]的映射。

满足关系：（概率值的分配满足区间要求和分布函数）【注意，这个语义不涉及概率本身的语义，和probabilistic logic of Nilsson不同】

解释的例子：

改写概率时态元组（TP-tuple）为普通关系元组

下略

【总结】本文并未涉及概率本身的语义: 没有把概率和模型的分布结合起来。我不是很喜欢这类作品，给人以不必要的复杂之感。一个好的逻辑，语义应该是很清楚的。因为没有概率本身的语义，所以要设计比较复杂的概率组合算法。后面设计的algebra，参考意义不大。

笔记：加注(Annotated) RDF (3) Dekhtyar 2001

Alex Dekhtyar, Robert B. Ross, V. S. Subrahmanian: Probabilistic temporal databases, I: algebra. ACM Trans. Database Syst. 26(1): 41-95 (2001)

正文44页，共67页。

背景：这个似乎和Annotated RDF无关。不过，temporal information是一种最常见的annotation，而在tuple上的工作，自然也可以用在triple上。Alexander Dekhtyar是Subrahmanian 2000年毕业的PhD。后面的APT (Annotated Probabilistic Temporal) Logic [Shakarian 2011]看似是这个工作的扩展

基本建模对象：Data tuple d is in relation R at some point of time in the interval [ti, tj ] with probability between p1 and p2. 例：

• Package p will arrive in Albany at some time between 9am and 5pm on Nov. 8 with probability 50–60%
• Rain is expected to begin sometime between 2pm and 12 midnight on Nov. 8 with probability 5–20%
• IBM stockwill reach $300 per share some time during the time
  interval Nov 1-10 with probability 90-100%

时间的模型：文中Fig 1 普通数据库，时态数据库和概率时态数据库的区别

• Time Unit: 比如天 day={1,2,…,31}
• Linear hierarchy of time units: 比如 day < month < year
• Time point: 是一个tuple，每个分量来自hierarchy中的一层，例如(2011 May 7 Sat 18 28)
• Calendar: 规定了time point的合法性，比如(2011 Feb 31)是不合法的

Temporal constraint: 基本的约束是形如day >= 5 或者 (2011 May 1 ~ 2011 May 7) 【注，原文要求(t1 ~ t2)里t1晚于t2，反直觉】。复杂的约束由基本约束通过 与∧ 或∨ 非¬ 构造。例 (year=1996 ∧ month < 4)

【待续】

笔记：加注(Annotated) RDF (2) Udrea 2010

Octavian Udrea, Diego Reforgiato Recupero, V. S. Subrahmanian: Annotated RDF. ACM Trans. Comput. Log. 11(2): (2010) 【本文的会议版在ESWC2006】

这个文章里，annotation也是一种偏序结构。也提到有不确定性uncertainty（模糊fuzzy？）, 时态temporal and 源谱provenance等几种应用。

aRDF = annotated RDF

历史：Annotated logic [Kifer ans Subramanian 1992] （要求标注是一个半格semilattice）[Leach and Lu 1996] [Fitting 1991]

语法：每个property属于某个偏序关系。一个aRDF triple是(s, p:a, o)。例如(Jie memberOf:[2001,2008], IowaStateUniversity)。画成图，就是每条边上多出来个annotation：例如（文中Fig 1(a)）

语义：一个aRDF解释（interpretation）是一个从资源到标注的映射。I满足(s p:a o) 如果 a≤ I(s p o).

一个aRDF系统(theory)是可能inconsistent的(Straccia 2010就不会）– 大概是偏序关系弱于格关系的缘故。不过我不认为这在工程上有什么影响。

后面和查询及实验相关的细节略过。（他们的实验说能处理10million triples）

【评价】本文和Straccia 2010方法完全类似。区别在于S文标注在triple上，U文标注在property上。S文要求标注为格，U问要求为偏序。两者的语义，都是从triple映射到标注，再做标注的“大小”比较。这一点应做扩展，从大小比较变成entailment的关系。这就变成了有完整表法力的域态逻辑（contextual logic）。

笔记：加注(Annotated) RDF (1) Straccia 2010

Umberto Straccia, Nuno Lopes, Gergely Lukacsy and Axel Polleres. A General Framework for Representing and Reasoning with Annotated Semantic Web Data. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10).
Abstract . Bibitem . Paper . Slides

读这系列的文章，是为了扩展做Contextual RDF。

RDF的Annotation: (s, p, o) : t  — t可以是时间（time），置信度（trust），源谱（provenance）

形形色色的Annotated RDF, contextual RDF, temporal RDF，无非是要描述

1. context域上的关系，有人称为meta-knowledge。比如时间。比如域的分类(hierarchy)
2. context上的知识转移。传统的（McCarthy式）说法是shifting。也就是，真值如何在context间转移。如 (a sc b): [1,3] and (b sc c): [2,4]推理出 (a sc c) : [2,3] – sc = rdfs:subClassOf

[Straccia 2010]中，annotation可以组成一个Lattice（格）——如果忘了格是什么，通俗的说，一个格里部分元素间可以比大小（偏序关系），而且任意多个元素都有一个共同的上界和一个共同的下界。

语义：标准的RDF语义，略，这里只提和annotation有关的变化。标注（annotation）有一个annotation domain。一个annotated interpretation对每个class，指定一个annotation。也就是一个函数ΔR ->L，其中ΔR是所有资源（resource）的集合，L是所有标注的集合。对property，类似，ΔR x ΔR ->L。

令I是从ΔR 到ΔR 到的“释名”函数（就是把RDF里的名字资源映射到其他资源）。IA(.)是从资源到标注的函数，那(s,p,o):v 的语义是 IA[I(p)] (I(s),I(o)) ≥ v，这里≥代表偏序关系。注意，IA[I(p)]本身是一个函数。通俗来说，就是p在一个情况下包含(s,o)，而这个情况比v一般（general, wider, broader）。

在格上，最大下界inf的作用类似于全称量词（universal quantifier）；最小上界sup的作用类似于存在量词（existential quantifier）。具体语义条件看文中Table 2。【注：这也类似连续信号的逻辑中，用min和max做量词。在普通逻辑中，我们隐含假设T>F,所以 T^F=F, 也即 inf(T,F)=F, min(T,F)=F】【又注：在多值逻辑里，比如4-valued paraconsistent logic, 或者LP的良基语义well-founded semantics，都有这种类似的真值结构和变量词为比大小的办法】

关键：和经典逻辑比，在经典逻辑里，只有两个标注值，0或者1。所有的资源，要么属于一个class，要么不属于（L={0,1}）。在Annotated RDF里，有多种“属于”的形式。

疑问：它这种定义，一个资源只能有一个标注类型。更一般的，应该是映射mapping而不是函数function。另外，用格代数限制很大。不过，因为其简单，推理才可能用Table 3 里的区区几条规则来表示。

应用1：模糊（Fuzzy）RDF。L=[0,1]（0到1的实数）≤是实数上的大小关系，x是实数上的乘法。我们有(a sp b):0.8, (b sp c):0.7 -> (a sp c):0.56 【注：注意和概率RDF的区别——不具有模型论语义。】

应用2：时态（Temporal）RDF。L={所有的时段集}。一个时段集（set of temporal interval）是若干个时段，每个时段如[t1, t2]，其中t1,t2是整数（含无穷大和无穷小）。≤是时间轴上的子集关系。

多种标注的综合：(CountryXXX  type Dangerous) : <[1975, 1983], 0.8, 0.6>
Time x Fuzzy x Trust

最终评价：本文其实很简单，思路很清晰。Annotation（标注）定义为一种代数结构（格）。这使annotation域的表达力弱，同时也推理简单。代数结构不需要一种模型论语义，反而适合工程的应用。

后续阅读：Nuno Lopes, Axel Polleres, Umberto Straccia, and Antoine Zimmermann. AnQL: SPARQLing up annotated RDFS. In Proceedings of the 9th International Semantic Web Conference (ISWC 2010), Shanghai, China, November 2010. Springer 【对本文加注RDF的一个查询语言】

笔记：AURA

David Gunning, Vinay K. Chaudhri et al. Project Halo Update – Progress Toward Digital Aristotle. 33-58. AI Magazine, Volume 31,  Number 3, Fall 2010

【下载】http://www.cs.utexas.edu/users/pclark/papers/AURA-AIMag.pdf
【项目主页】http://www.ai.sri.com/project/aura
【参考】语义网的公司（5）Vulcan: Project Halo，笔记: Inquire for iPad （平板上的教科书）

为了和沃森系统比较，又看了SRI的AURA系统。他们主页上有很多文章，其实看上面这一篇就够了。没时间，做一个很简略的笔记

【目的】特定领域的Q/A：本科入门水平的生物、化学、物理教科书。目前实现的系统可以算是“考试机器人”，能回答选择题。终极目标是HaloBook，一种新形式的电子教科书。

【构架】偷论文里的图

【知识表现】把课本和考试题都用逻辑公式来表示（由两组人分别搞）。用到了DL和LP。用到一个通用知识库Component Libaray (CLIB)。也用到语义网的数据。

为什么不象Watson用NLP做自动分析（automatic reading）？作者称1）语言理解难；2）不认为教科书（专业知识）可以用NLP自动建模；3）公式和图表很难NLP

【受控自然语言】考题的形式化用Controlled English – CPL (Computer-processable language)

【推理】 问题回答是用逻辑推理，推理机是Knowledge Machine（UT Austin）。但是也有非逻辑的，启发式推理（heuristic and plausible）。

推理过程给出了Explanation（解释）。和Provenance工作相关。

公式推理那一块，是不是可以重用Wolfgram Alpha？Siri是用的。

【界面】逻辑公式用概念图（concept map）来表示，内部表示大概是Lisp。也用SMW的Halo Extension做界面。

评价：我认为，全图形化的输入界面才是王道，并加以各种提示工具，如faceted brower, autocompletion, drag and draw, zoom in and out。核心在用人机交互帮助思考和联想。目标应放在0培训。

【正确率】在2002年的Halo Pilot系统，能达到30%-50%正确率。对生物和物理，专家建的系统能答对70%参考书上的问题，和40%书外的问题。化学差些。

【成本】但是他们这种方法成本很高。每个做课本形式化的“专家”要训练20小时；做考题形式化的训练4小时。形式化的课本：生物44页，化学67页，物理78页。专家（SRI自己的科学家）在生物上做了600小时的标注，平均每页13.6小时。在美国企业里，这种级别的雇员至少要8万美元每年,按250个工作日，每小时40美元。也就是这44页要（不算开始的训练时间）2.4万美元，每页545美元。

一本教科书至少200页（美国的教科书500页以上的很正常），那要10万美元以上才能形式化，要花一个专家一整年的时间。沃森系统有2亿页数据，照AURA这么做要1000亿美元。

专家做120小时的标注和非专家（本科生）做300小时的标注效果类似（回答书外的问题60%正确率）。非专家做120小时标注正确率只有21%。

【疑问】1）是否可以扩展（generalize）到其他问题域？2）是否能处理大量数据（scale）？3）怀疑受控自然语言的有效性——当然，可以用图形化的用户界面来弥补。4）如何更好利用外部数据如linked data? 5）如何多种方法综合使用，比如用NLP做种子知识生成？参考沃森。6）如何降低综合成本？

【和沃森的一些区别】

• 沃森是做开放问题域，AURA做特定问题域。
• 沃森主要基于概率，AURA主要基于逻辑
• 沃森做答案的发现，AURA做选择题（答案的校验）——这一点难度的差别，犹如NP和P。
• 沃森对答案有置信度，AURA没有。
• 对所有问题，沃森的正确率是65%，AURA是75%。当然，这两个数字没有可比性。
• 沃森的核心是算法，跨领域性好，添加新的数据成本应该比较低（可能和Web数据的增长同步）；AURA需要人工做知识提取，很难scale。
• 沃森有可能处理实时数据，AURA看起来不可能。
• 如果用沃森来回答AURA的问题，会有什么样的结果？未必好，但是不试一下怎么知道？

【团队】

David Gunning【PI, Vulcan】
Vinay K. Chaudhri 【SRI这边的PI，主要直接领导人】
Peter Clark 【Boeing】
Ken Barker【UTAustin这边的头，主打逻辑推理】
Shaw-Yi Chaw 【IBM的，他在沃森组里】
Mark Greaves 【Halo的总头】
Benjamin Grosof 【SILK的头，规则推理这一块】
Alice Leung 【BBN这边做实验的。她也在NS-CTA里做实验这一块】
David McDonald 【语言学linguistics】
Sunil Mishra, 【SRI，大概是开发工作】
John Pacheco 【SRI，大概是开发工作】
Bruce Porter
Aaron Spaulding,
Dan Tecuci,
Jing Tien 【界面】

不在本文列名的SRI人员还有

• Dinesh, Nikhil
• Overholtzer, Adam
• Pacheco, John
• Spaulding, Aaron
• Wessel, Michael A.
• Wilkins, David E

笔记：DeepQA (IBM沃森)（4）结果与心得

David A. Ferrucci et al,Building Watson: An Overview of the DeepQA Project. AI Magazine 31(3): 59-79 (2010).

==结果==

偷论文里的一张图

==工作方式==

所有人在一个大屋war room，以方便交流。逐步进步。【唔，how about 中国的团队？】

==作者心得==

Q/A三要素：precision, confidence, and speed

systems-level approach：综合运用多种方法。这可能是对一般AI问题都有意义的。

快速实验，高性能计算平台的重要性。

==我的其他心得==

面向终端用户的系统，需要做自然语言理解。语义网的团队，需要招这种人才。加深了对Twine, PowerSet, Siri等的理解。但我觉得在选择应用方面，还是以容错性较高的领域比较好。

自然语言理解并不需要做逻辑的建模。不需要做强的逻辑推理，可以综合运用一些简单的推理。这可以避免Twine的问题（scalability）

结构化知识，起辅助的作用，我很想知道到底有助于提高几个百分点？

沃森成功的关键之一是对置信度的计算。你要是单看对所有问题的正确率，那只有65%的样子，好像不是很惊人。但是如果不但知道答案，还知道答案有多可靠，把那些不确定的过滤掉，这很有用。知之为知之，不知为不知。知不知亦为知亦。

按这个思路，应该可以针对某些特定领域做更优的Q/A。

笔记：DeepQA (IBM沃森)（3）答案之生成

David A. Ferrucci et al,Building Watson: An Overview of the DeepQA Project. AI Magazine 31(3): 59-79 (2010).

==假设生成==

Hypothesis generation takes the results of question analysis and produces candidate answers by searching the system’s sources and extracting answer-sized snippets from the search results

这一步是要收集尽可能多的假设： the system generates the correct answer as a candidate answer for 85 percent of the questions somewhere within the top 250 ranked candidates

综合运用多种搜索方法，Indri, Lucene, SPARQL。triple store的作用主要是对线索里提到的名词或者关系做查找。

找到文献后，要做Candidate Answer Generation：取出和问题相关的字句，准备答案

==软过滤==

Soft Filtering。得到的假设（候选答案很多），要先用一些简单的算法“软”过滤一下，比如算“韩寒”是一个“省”的概率有多大。后面还有另一层过滤，用比较昂贵的方法。过滤后大概剩下100个假设。

==找证据==

对每个假设，要看看有没有充分的证据支持。一个方法是把假设代进问题本身，再去搜索，看能不能搜到。

然后对每个证据打分。有很多不同的打分算法，多于50个。这里有许多推理，比如时态关系，空间关系，还有证据来源的可信度。

==合并和排序==

The goal of final ranking and merging is to evaluate the hundreds of hypotheses based on potentially hundreds of thousands of scores to identify
the single best-supported hypothesis given the evidence and to estimate its confidence — the likelihood it is correct.

很多假设（候选答案）是等价的，要先合并之。

用一个机器学习方法做基于证据的排序。

==其他==

硬件（并行），抢答策略（博弈论）略。

技术讨论完。

笔记：DeepQA (IBM沃森)（2）问题之分析

David A. Ferrucci et al,Building Watson: An Overview of the DeepQA Project. AI Magazine 31(3): 59-79 (2010).

==DeepQA方式==

一句话总结：a massively parallel probabilistic evidence-based architecture

多种方法的集成：we use more than 100 different techniques for analyzing natural language, identifying sources, finding and generating hypotheses, finding and scoring evidence, and merging and ranking hypotheses.

四项基本原则：massive parallelism, many experts, pervasive confidence estimation, and integration of shallow and deep knowledge.

==指标==

第一要能答尽可能多的问题Percentage Attempted

第二要能答对precision

因为知识有限，答的多，有些没有把握的也答，就更容易出错。把两者做坐标画一个曲线，是一个下降的线。目标就是把这个线提高。沃森的各个版本渐次做到这一点（Fig 9）

人类参赛者一般回到20%-60%问题，正确率70%-100%。特别牛X的回答50%-80%，正确率80%-100%。

所以系统设计，要计算对答案的置信度，如果太低，就不答。

==基准==

设计沃森前，团队用现成的Q/A系统跑了跑 Jeopardy。 PIQUANT对5%的问题有47%的正确率，总的正确率是13%。OpenEphyra答对了45%——利用Web搜索。

更有趣的是，他们比较了纯文本搜索（text search）和结构化数据（structured data）查询。文本搜索的曲线是上升的，但很快稳定在30%，表示文本搜索可以覆盖更多的问题，但是比较盲目（不知道答案是否“好”）。结构化查询对某些已知类型问题有效，但对这之外的，比搜索还差。

==分析问题==

Q/A的第一步是分析问题Q(uestion)。

每个问题有一个类（category），比如历史、科学、政治，这是已知的。

问题可以分解为子问题，子问题可以是并列的关系，或者嵌套的关系。这需要对问题句子做自然语言结构分析。

每个问题有一个关键词被称为“domain”（域），比如“这个皇帝死于北京的那年一共有三个不同国号的皇帝在北京登基”的域就是“皇帝”。域也称lexical answer type (LAT)。分布很分散，2万个问题就有2500个LAT。因为LAT太多，针对每个域做特别的建模就不可行了。

问题还要做关系检测（Relation Detection），也就是动词，比如“和北京相邻的省”中关系是“相邻”。