Collaborative Research: Information Theory of the Rare Event Regime

本研究涉及改进文本文档自动处理方法的开发。该研究特别关注两个特定的文本处理问题：无损、数据压缩和分类。无损数据压缩有助于减少大型文本文档的存储和传输需求。这也是通过密码学安全发送文本的重要步骤。分类经常出现在网络搜索问题和取证中，其目标是确定匿名文档的作者。该方法是通过使用信息论中的一种新的渐近制度来对这些问题提出新的见解，该制度比经典模型更准确地模拟真实文本源。具体地说，研究人员考虑了一个数据集和源字母表的大小相当大的制度。可以证明，大多数经典信息理论技术在这种“罕见事件”制度下失败了。尽管如此，可以开发出适合这种制度的新技术，从而产生新的算法和见解。

This research involves the development of improved methods forautomatic processing of text documents. The research focusesin particular on two specific text-handling problems: losslessdata compression and classification. Lossless data compressionis useful for reducing storage and transmission requirementsfor large text documents. It is also an important step insending text securely via cryptography. Classification arisesfrequently in web search problems and also in forensics, wherethe goal is to determine the authorship of an anonymous document.The approach is to draw new insights into these problems byusing a novel asymptotic regime in information theory, whichmore accurately models real text sources than classicalmodels do. Specfically, the investigators consider a regime in which the size of the data set and the source alphabet are comparably large. It can be shown that most classical information theory techniquesfail in this "rare-events" regime. Nonetheless, new techniques can be developed that are tailored to this regime that yield new algorithms and insights.