基于描述复杂性的信息检索理论与若干模型研究

论文摘要

我们在文中讨论了几种模型：基于kolmogorov complexity的NID(NCD)理论的几种模型(第二章、第三章)，图模型(第四章)，简单关联模型(第五章)，设计程序进行了实验验证，和经典的向量空间模型做了对比。并且从两个方面力图解决信息检索理论和经验上的ad hoc问题：从普遍理论导出检索模型，用普遍理论解释经验模型。此外，探讨了信息检索结果等价的形式化分析、向量空间模型假设的形式化分析及其前缀复杂性表示。 一，在NCD理论和模型方面做的工作主要有三：信息检索的NCD解释、NCD模型近似实现和试验、经验模型和NCD模型的比较和解释。 1：信息检索的NCD理论(第二章)。我们从算法信息(描述复杂性)的角度讨论了信息检索的NCD理论。NCD从理论方面给出了解决信息检索理论上一直存在的ad hoc问题的途径。由Kolmogorov complexity定义出来的NCD在理论上证明为一切有意义的距离中最优的。如果信息检索必须含有评分和排序，并且将相关度等同于评分函数所得到的评分，依照评分来排序文档，那么，理论上NCD应该是最优的检索模型。但是由于NCD不可计算，因此只提供了一个理论解释，而具体模型则需要我们用各种策略去近似NCD。 2：NCD模型近似实现和试验(第二章、第三章)。2a．NCD模型依照压缩算法的近似实现和试验(第二章)。 ●我们由NCD理论近似得出了两种基于压缩算法的模型。两个模型由NCD理论近似导出，不同于信息检索的模型(信息检索模型一直具有ad hoc问题)，并且是揭示了压缩和信息检索相关度之间的关系。就文本的结构算法信息进行了实验。实验的结果表明，压缩率越大，则检索效果越好。而对文本做编码，使得单词能够作为一个单位，或者编码长度一致，检索效果也有了提高。这表明，进一步改进压缩算法，提高压缩率，进而得到更高的检索效果；修改实现压缩算法的程序，使之真正以单词为单位进行压缩，从而得到更好的检索效果。 ●我们根据lz算法，设计了一个简单算法，真正以单词为单位进行压缩(把词作为不可压缩的码字)，编制程序进行了实验验证。实验结果表明，真正以单词为单位进行压缩，则检索性能大有提高，限于条件，简化算法没有达到lz算法最优压缩效果。

论文目录

• 关于学位论文使用授权的说明
• 摘要
• Abstract
• 第一章 信息检索概述
• 1.1 引言
• 1.2 四种基本的信息检索模型
• 1.2.1 基于集合论的模型
• 1.2.1.1 布尔模型
• 1.2.1.2 布尔模型的几种变体
• 1.2.1.3 MMM模型
• 1.2.1.4 Paice模型
• 1.2.1.5 P-norm模型
• 1.2.2 代数模型
• 1.2.2.1 向量空间模型
• 1.2.2.2 广义向量空间模型
• 1.2.2.3 潜在语义标引模型（latent semantics indexing model,LSI）
• 1.2.2.4 神经网络模型（Neural Network Model）
• 1.2.3 概率模型
• 1.2.3.1 贝叶斯网络（bayesian）
• 1.2.4 语言模型
• 1.2.4.1 一元语法模型
• 1.2.4.2 隐马尔科夫模型（HMM）
• 1.2.4.3 统计语言翻译模型
• 1.2.4.4 信息检索的语言模型和贝叶斯决策理论
• 1.3 检索模型评价与评测组织
• 1.3.1 模型评价
• 1.3.2 TREC简介
• 1.4 模型的基础理论研究以及理论研究上的ad hoc问题
• 1.5 各种模型的实现
• 1.5.1 一般信息检索系统的架构
• 1.5.2 几个信息检索软件简介
• 1.5.2.1 smart
• 1.5.2.2 lemur
• 第二章 信息检索的NID（NCD）距离与由此导出的模型
• 2.1 描述复杂性理论（Kolmogorov's complexity）
• 2.1.1 任意性或随机性与不可计算性或非递归性
• 2.1.2 描述复杂性（Kolmogorov's complexity）
• 2.1.3 准测度,描述概率和推理概率
• 2.1.4 描述复杂性（Kolmogorov's comptexity）和距离
• 2.2 描述复杂性（Kolmogorov's complexity）,归一化绝对距离和信息检索
• 2.2.1 归一化绝对距离
• 2.2.2 压缩概述,有损压缩,无损压缩与信息检索
• 2.2.2.1 通用压缩算法概述
• 2.2.2.2 非通用压缩-多媒体数据的压缩
• 2.2.2.3 压缩算法和技术目前和将来的发展
• 2.2.2.4 有损压缩,无损压缩和信息检索
• 2.3 信息检索的NCD模型
• 2.3.1 信息检索的NCD模型的实现
• 2.4 信息检索的NCD模型的zlib近似实现和实验
• 2.4.1 实验1
• 2.4.1.1 实验1的设定
• 2.4.1.2 实验1的结果
• 2.4.1.3 实验1的分析
• 2.4.2 实验2
• 2.4.2.1 实验2的设定
• 2.4.2.2 实验2的结果
• 2.4.2.3 实验2的分析
• 2.4.3 实验3
• 2.4.3.1 实验3的设定
• 2.4.3.2 实验3的结果
• 2.4.3.3 实验3的分析
• 2.4.4 实验4
• 2.4.4.1 实验4的设定
• 2.4.4.2 实验4的结果
• 2.4.4.3 实验4的分析
• 2.4.5 实验5
• 2.4.5.1 实验5的设定
• 2.4.5.2 实验5的结果
• 2.4.5.3 实验5的分析
• 2.4.6 实验6
• 2.4.6.1 实验6的设定
• 2.4.6.2 实验6的结果
• 2.4.6.3 实验6的分析
• 2.4.7 zlib试验分析
• 2.5 ncd的bzip近似模型与实验
• 2.5.1 bzip近似模型的压缩算法
• 2.5.2 实验7
• 2.5.2.1 实验7的设定
• 2.5.2.2 实验7的结果
• 2.5.2.3 实验7的分析
• 2.5.3 实验8
• 2.5.3.1 实验8的设定
• 2.5.3.2 实验8的结果
• 2.5.3.3 实验8的分析
• 2.5.4 实验9
• 2.5.4.1 实验9的设定
• 2.5.4.2 实验9的结果
• 2.5.4.3 实验9的分析
• 2.5.5 bzip试验分析
• 2.6 NCD模型一个简单的近似实现
• 2.6.1 实验10
• 2.6.1.1 实验10的设定
• 2.6.1.2 实验10的结果
• 2.6.1.3 实验10的分析
• 2.6.2 实验11
• 2.6.2.1 实验11的设定
• 2.6.2.2 实验11的结果
• 2.6.2.3 实验11的分析
• 2.7 结论与将来的工作
• 2.7.1 信息检索的NCD理论
• 2.7.2 NCD模型依照压缩算法的近似实现和试验
• 2.7.2.1 NCD模型依照LZ,BWT的近似实现和试验
• 2.7.2.2 NCD模型以单词为单位进行压缩的LZ简单实现和试验
• 2.7.3 信息检索NCD模型将来的进一步工作
• 第三章 信息检索的经验模型,NCD距离与NCD距离模型探讨
• 3.1 信息检索的形式定义与若干性质
• 3.1.1 信息检索的形式描述
• 3.2 向量空间模型与其他经验模型的比较,向量空间模型的假设
• 3.2.1 语言模型和向量空间模型的比较
• 3.2.2 向量空间模型的假设
• 3.2.3 一个典型的向量空间模型的表示函数与评分函数
• 3.3 归一化绝对距离在VSM两个假设之下导出的模型与实验验证
• 3.3.1 归一化绝对距离在向量空间模型的两个假设之下导出的模型
• 3.3.2 实验1
• 3.3.2.1 实验1的设定
• 3.3.2.2 实验1的结果
• 3.3.2.3 实验1的分析
• 3.3.3 实验2
• 3.3.3.1 实验2的设定
• 3.3.3.2 实验2的结果
• 3.3.3.3 实验2的分析
• 3.4 向量空间模型与归一化绝对距离的比较
• 3.4.1 向量空间模型与归一化绝对距离
• 3.5 结论和将来的工作
• 3.5.1 信息检索结果等价的形式化分析、向量空间模型假设的形式化分析及其前缀复杂性表示
• 3.5.2 NCD模型在VSM假设之下的近似实现和试验
• 3.5.3 NCD模型中近似取得词语的算法信息或前缀复杂度的方法
• 3.5.4 经验模型（VSM）和NCD模型的比较和解释
• 第四章 信息检索的文档图模型
• 4.1 文档图模型与相关的工作
• 4.1.1 文档图模型
• 4.1.2 我们的图模型和其他机构一些相关的工作
• 4.2 离散马尔可夫链、图模型、对阅读过程的建模（词之间,句子之间的连接关系）
• 4.3 图模型试验
• 4.3.1 实验1
• 4.3.1.1 实验1的设定
• 4.3.1.2 实验1的结果
• 4.3.1.3 实验1的分析
• 4.4 结论和将来的工作
• 第五章 关联模型：简化的实现和试验
• 5.1 简单关联模型
• 5.2 简单关联模型试验一
• 5.2.1 实验设定
• 5.2.2 实验结果
• 5.2.3 实验分析
• 5.3 简单关联模型试验二
• 5.3.1 实验设定
• 5.3.2 实验结果
• 5.3.3 实验分析
• 5.4 简单关联模型试验三：混合简单关联模型和向量空间模型
• 5.4.1 实验设定
• 5.4.2 实验结果
• 5.4.3 实验分析
• 5.5 混合实验对应的简单向量空间模型实验
• 5.5.1 实验设定
• 5.5.2 实验结果
• 5.5.3 实验分析
• 5.6 简单关联模型结论和将来进一步的工作
• 第六章 经典信息检索模型的相关实验
• 6.1 经典信息检索模型的软件实现
• 6.1.1 简单的经典模型检索
• 6.1.2 带反馈的经典模型检索
• 6.1.3 rerank检索
• 6.1.4 评测
• 6.2 信息检索的向量空间,okapi,lm模型的检索实验
• 6.2.1 实验1
• 6.2.1.1 实验1的设定
• 6.2.1.2 实验1的结果
• 6.2.2 实验2
• 6.2.2.1 实验2的设定
• 6.2.2.2 实验2的结果
• 6.2.3 实验3
• 6.2.3.1 实验3的设定
• 6.2.3.2 实验3的结果
• 6.3 反馈试验
• 6.3.1 实验4
• 6.3.1.1 实验4的设定
• 6.3.1.2 实验4的结果
• 6.3.2 实验5
• 6.3.2.1 实验5的设定
• 6.3.2.2 实验5的结果
• 6.4 信息检索模型的rerank实验
• 6.4.1 实验6
• 6.4.1.1 实验6的设定
• 6.4.1.2 实验6的结果
• 6.4.1.3 实验6的分析
• 6.4.2 实验7
• 6.4.2.1 实验7的设定
• 6.4.2.2 实验7的结果
• 6.4.3 实验8
• 6.4.3.1 实验8的设定
• 6.4.3.2 实验8的结果
• 第七章 结论
• 7.1 基于kolmogorov complexity的NCD模型,理论和经验模型的解释
• 7.1.1 信息检索的NCD理论
• 7.1.2 基于kolmogorov complexity的NCD模型的近似实现和试验
• 7.1.2.1 NCD模型依照压缩算法的近似实现和试验
• 7.1.2.2 NCD模型在VSM假设之下的近似实现和试验
• 7.1.3 VSM诸经验摸型和NCD模型的比较和解释
• 7.1.3.1 近似取得词语的算法信息或前缀复杂度的方法
• 7.1.3.2 经验模型（VSM）和NCD模型的比较和解释
• 7.2 信息检索结果等价,VSM假设的形式化分析和VSM假设的前缀复杂性表示
• 7.2.1 信息检索结果等价的形式化分析
• 7.2.2 向量空间模型假设的形式化分析和前缀复杂性表示
• 7.3 图模型
• 7.4 简单关联模型
• 参考文献
• 致谢
• 声明
• 附录A 相关数学概念,定理,公式和证明
• A.1 随机性和有效测试的有关概念和定理
• 个人简历、在学期间的研究成果及发表的论文