Archive

Archive for the ‘笔记’ Category

URL, URN, URI, IRI

2012/01/14 1条评论

“网址”到底是什么?一般的理解是URL(Uniform resource locator

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

还有一个相关概念 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 IssuesDocument Naming (1991)

分类:笔记, 语义网, Web

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

2011/05/28 留下评论

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

(1)删去信道

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

信道容量的证明:以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) codesRaptor 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.

分类:笔记, 信息论

笔记:概率时空逻辑

2011/05/18 留下评论

参前文

【会议版】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)基本思路

2011/05/17 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 AdomaviciusAlexander 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 HeitmannConor HayesUsing Linked Data to build open, collaborative recommender systemsIn 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 recommendationJ. 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方法

2011/05/15 1条评论

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

2011/05/15 1条评论

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)背景

2011/05/14 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.