Archive

Archive for the ‘信息论’ Category

通信的语法,语义和语用层次:一封推荐信

2012/11/22 留下评论

以前在研究“语义信息论”(Semantic Information Theory)的时候,涉及到通信的三个层次:技术的,语义的和效果的。这个层次划分是(Weaver 1949)说的。香农的传统信息论只涉及技术这个层面。

从语言学的角度,这三个层次可以大致对应于语言的语法Syntax、语义Semantics和语用Pragmatics三个层次

今天在看《语言本能》(The Language Instinct)这本书,里面举了个很有意思的例子,可以做这三个层次的范例

一封推荐信:

亲爱的平克教授:

我非常高兴能向你推荐厄文×史密斯先生。史密斯先生是一个模范学生。他衣着整齐,而且非常守时。我认识史密斯先生已经三年了,我觉得他在各方面都是最合作的人。他的太太很迷人。

真诚的约翰×琼斯教授

语法层面:用某种NLP工具,比如Stanford parser,可以分析句子结构。比如这样的语法树

(ROOT
  (IP
    (IP
      (NP
        (NP (NR 史密斯))
        (NP (NN 先生)))
      (VP (VC 是)
        (NP
          (QP (CD 一)
            (CLP (M 个)))
          (NP (NN 模范) (NN 学生)))))
    (PU 。)
    (IP
      (NP (PN 他))
      (VP
        (VP
          (ADVP (AD 衣着))
          (VP (VA 整齐)))
        (PU ,)
        (CC 而且)
        (VP
          (ADVP (AD 非常))
          (VP (VA 守时)))))
    (PU 。)))

语义层面:基于背景知识,我们知道史密斯先生是个男人,他已婚,他至少已经三岁了(呵呵)。所谓的语义信息论,就是不仅局限于句子本身出现的符号(如“先生”),而是把它们与未出现的符号(如”男人”)也关联起来,通过出现的符号来推导出未出现的符号的一些信息。

语用层面:琼斯教授在使坏,在说史密斯的坏话,虽然一个负面的词都没有用。因为推荐信理论上是要讲被推荐人的专业素养,琼斯教授只说了一堆不相干的话。在这个特定的通信实例里,其实有一个“封闭世界假设”:如果推荐人没有说到专业素养,那说明这个专业素养是不值得提的。这种语用的信息,是基于信源和信宿共用的背景知识(如文化)和一些约定的规范(如推荐信的内容)。一些特定的场合,语用应该也是可以数学描述或近似的。留待以后有空来捣捣浆糊。

语义通信和传统通信的基本区别

2011/11/07 留下评论

引自我正在写的一篇文章:

A semantic information source or destination has a background knowledge base and is able to infer implicit facts from explicitly given facts. The key difference from the classical information theory is that in our semantic information theory, messages are expressions which can be true or false. We are interested in studying how often a message is true and how its truthhood can be preserved in communication; on the other hand, classical information theory studies how often a message appears and how precise its lexical form can be restored in communication.

分类:语义网, 信息论

TF-IDF之极简化信息论分析

2011/06/15 留下评论

昨天看到有人说,TF-IDF本质上是Kullback–Leibler divergence。参《如何确定网页和查询的相关性》by 吴军

问了一个搞IR的教授这个说法的出处。他说,似乎很明显,但搞不清楚谁第一个说的。

我试着做一个最简化的推导。这里用的TF-IDF是最简单的一种定义,实际用的,要比这复杂。

问题描述:一个查询q=(w1, w2…),一个文档d=(w1, w2….),其中w是单词,q和d都是bag of words。所有文档的集合是D=(d1, d2, …) 要求对所有文档,针对与q的相关性进行排序。

词频 TF(w,d) = w在d中出现的次数  / d中所有单词的个数

逆文档频率 IDF(w) = 所有文档的数量 / 包含w的文档的数量

单词w对文档d的相关度: TF*IDF(w,d) = TF(w,d)*IDF(w)

查询q对文档d的相关度,是它里面所有单词对d相关度的总和,Σw TF*IDF(w,d)。

对两个概率分布P和R,其KL-divergence,或者说相对熵, KL(P||R) = ΣxP(x) log(P(x)/R(x))

如果直接套,查询q对文档d的K-L divergence是

KL(Q||D) = ΣqP(q) log(P(q)/P(d))

这个不好算,什么叫q出现的概率和d出现的概率?

我们假设相关度具有可加性,我们只看一个单词w对一个文档的相关性,而不是一个查询q。

KL(W||D) = ΣP(w) log(P(w)/P(w|d))

其中P(w)是w在文档d中出现的概率【概率空间是单词】,P(w|d)是d中出现w的概率【概率空间是文档】。

KL(W||D) = ΣP(w) logP(w) -ΣP(w) log P(w|d))

第一项可排序无关,可略去。第二项,就和TF-IDF形似了。

【有待进一步思考】

参考 Robertson, S. (2004). Understanding inverse document frequency: on theoretical arguments for IDF. Journal of Documentation60(5), 503-520.

分类:信息论

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

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/28 1条评论

这两者之间其实有很近的关系

一个量子比特(qubit)是多个纯态(pure state)的叠加。例如|s>= 0.707 |0> + 0.707 |1> 就是说 |s>以概率0.707*0.707=0.5为|0>,以概率0.5为|0> 。也就是,如果进行100次测量,那近似 50次得到|0>。

在语义信息论中,一个消息,也即是一个逻辑的表达式,代表多个模型。每个模型有自己出现的概率。例如,假如模型的集合是一个一个的人,其中20%是小孩,20%是老人。那消息“小孩或老人”的逻辑概率是40%,其中一半的可能是小孩,另一半是老人。

也就是,单个模型对应量子信息论中的基态。可写为

|小孩或老人> = 0.707 |小孩> + 0.707 |老人>

注意,在经典信息论中,如果{0,1}的分布概率是{0.5,0.5}这个信源没有冗余,(香农)熵是1比特。在量子信息论中,如果{|0>,|1>}的分布概率是{0.5,0.5},它的(冯诺伊曼)熵要比1比特小,因为在所有的可能输出中(现在有无穷多种), 0.707 |0> + 0.707 |1>出现的概率最大。

由于语义信息论中,一个消息可能对应多个不同的模型,这本身包含了语义歧义性(semantic ambiguity)。所以,语义信源的平均语义熵,必然的小于信源的模型熵(model entropy,也即是把模型本身当作消息时,计算的经典香农熵)。也就是,平均语义熵对应于冯诺伊曼熵。这个熵小于模型熵,但是可能大于或者小于信源的语法熵。这提供了语义压缩的可能。

注意,Bennett & Shor 1998说(我的翻译):

若经典数据由于数字位的不等频率或数字位间的相关,是冗余的,可以利用某些技术如Huffman编码压缩。量子数据具有以上两种冗余,但还有第三种方式:若数据流中的状态是非正交的(例如 一水平和45度 对角光子的随机流),作为物理态不能完全区分。这样的数据流不能用经典方法压缩,因为发送站在试图读数据时可能会产生干扰。然而 在对输入的n个状态的数据块进行幺正变换后,量子编码可以(无须对状态有任何了解)将其所包含的信息压缩到较少的量子比特,在接收端通过相反的变换可以几乎完全重建原始信号。

利用量子纠缠进行量子压缩,对应于利用语义模糊进行语义压缩。

Reference

参: Seminar on Quantum Compression. Ofer Shayevitz

中文资料参: 量子信息讲座(中国科学院量子信息重点实验室)

我以前翻译的量子信息论文章(1999):
http://www.cs.iastate.edu/~baojie/acad/past/past.htm#quantum
原文是 Charles H. Bennett, Peter W. Shor: Quantum Information Theory. IEEE Transactions on Information Theory 44(6): 2724-2742 (1998)

分类:思路, 信息论

数据压缩方法

2011/05/21 留下评论

数据压缩data compression),或者称为信源编码,对利用数据中的冗余(redundancy),来实现减少数据集大小的方法。

(1)统计冗余

传统的信息论的方法,是利用统计冗余(statistical redundancy)。何谓统计冗余?一般的说法是符号出现的概率不相等。为什么这样就叫冗余呢?因为一个各符号出现概率相等的信源(也即看起来完全随机)是最简洁的,也是我们对它没有任何知识的信源——这对应于物理中的能量均分原理。如果概率不相等,那我们对这个信源有一定的(统计)知识,就可以用来变换这个信源到另一个更接近完全随机信源的的信源,从而实现压缩。

大体有这样一些方法

定长块编码(Fixed-length block codes)。如果令X是一个信号源,X随机独立重复n次,那得到的n长序列,有很多可能。不过根据大数定理,其中只有很少一部分是典型的,也就是说,其他的序列,概率极小,统计上可以忽略。所以,我们只需要对这部分典型序列做编码。而且这些典型序列的出现概率都是近乎相等的。这个特性也就是著名的渐进等分原理(AEP)。香农信源编码定理利用这个原理,证明,用定长块编码,我们可以用nH(X)码长实现对X的n长序列的任意小错误率的编码。这种编码,只有理论价值,没有工程价值。

符号编码(symbol codes)做一个从原符号集到编码集的映射,并保证可以唯一解码。典型的是一些变长(variable-length)前缀码(prefix codes),如霍夫曼(Huffman)编码。基本原理是经常出现的符号给以短码。这也是利用统计冗余。

流编码(stream codes)不依赖一个事先定义的一一对应编码,而通过读输入数据流,动态构造编码。算术码arithmetic codes)把每个字符串映射到[0,1)上的一个区间,区间的长度就是这个字符串的概率;收发端都知道这个概率分布。Lempel-Ziv编码记住已经见过的字符串,构造一个字典,这样下次遇到同样的字符串,只要给出它在字典中的位置即可。

(2)统计语义冗余 (statistical semantic redundancy )

目前主要是用在数据库领域。这是利用有结构的数据中存在的统计依赖关系来压缩。

SPARTAN是利用决策树,去除关系数据表中的某些列(column)——因为这些列现在可以通过决策树恢复。

ItCompress是一种聚类的方法,对表中的行(row),指定一些行为代表,其他行只记录和代表行之间的差别。fascicles算法类似。

一般的,机器学习就是一个信息压缩的过程。现在有很多本体学习的算法(例:DL-Learner),都可以看作信息压缩算法。

统计语义依赖可以表达一般的统计依赖(贝叶斯依赖)不能表达的关系,例如使用量词: P(C(x)|\exists R(x,a))=0.7

(3)演绎语义冗余(deductive semantic redundancy)

给定一个逻辑知识库,如果数据集的一部分可以通过其他部分经逻辑演绎获得,那这部分数据属于语义冗余,可以除去。对RDF和OWL,都有冗余检测算法。

不过彻底的冗余除去是计算代价很高的过程。可能通过一些启发式算法来估计某些数据是冗余数据的可能行,以提高可扩展性。

分类:信息论

语义通信这篇文章被录用了

2011/05/05 2 条评论

不是什么好会议,一个IEEE的workshop。不过这个题目从开始到现在,一年多了,这是第一篇文章,也算是稍有收获。只所以花这么久,第一是因为要学习的东西太多——信息论我已经很多年没有涉猎了。第二是不停地犯错误,曾经在算法信息论(algorithmic information theory)这个分支上晃悠了半年之久,最后发现对工程没有什么价值。现在这个文章,也还是很抽象的,没有说工程的事——不过香农的文章不也没有说吗?关键是下一步(如果我还做这个项目的话),如果指导编码?比如,如何更好的设计ontology来表达要表达的知识而只用最少的长度?

文章主要说了两个事

  • 什么是通信中的语义?怎么衡量这个语义?文中用的是模型论(model theory)+概率逻辑(probabilistic logic)
  • 语义对编码有什么意义?包括信源编码也就是数据压缩,和信道编码,也就是可靠性编码(和噪声对抗)。
下面这个框图,是Weaver最先提出的,我做了一点增删。等过段时间,再把全文和slides(BTW, 这个词的中文到底该怎么说?)放出来。

分类:信息论