arXiv:2410.21666cs.LGcs.IT2024-10NeurIPS被引 10

提出带瓶颈的最小熵耦合框架,提升压缩与检索的协同性能。

Minimum Entropy Coupling with Bottleneck

  • 引入瓶颈机制控制耦合中的随机性,优化压缩过程
  • 在马尔可夫编码游戏中,实现不同速率下的奖励与准确率平衡
  • 提供贪婪算法保证性能,适用于分布偏移场景

本文研究一种新型有损压缩框架,在对数损失下运行,适用于重建分布与源分布不一致的场景。该框架特别适用于需要联合压缩与检索的应用,以及因处理导致分布偏移的情况。通过引入瓶颈,所提方法扩展了经典最小熵耦合框架,实现对耦合中随机性的可控调节。我们揭示了最小熵耦合带瓶颈(MEC-B)可分解为两个优化问题:编码器的熵约束信息最大化(EBIM),和解码器的最小熵耦合(MEC)。通过分析,我们给出了EBIM的贪心算法并保证其性能,同时刻画了接近函数映射时的最优解结构,揭示了该问题的结构性复杂度。此外,我们在速率限制下的马尔可夫编码游戏(MCGs)中展示了MEC-B的实用性。这些游戏模拟了马尔可夫决策过程中发送方通过动作向接收方传输压缩消息的通信场景。实验结果展示了在不同压缩率下MDP奖励与接收端准确率之间的权衡,验证了该方法相比传统压缩基线的有效性。

原文摘要 · Abstract (English)

This paper investigates a novel lossy compression framework operating under logarithmic loss, designed to handle situations where the reconstruction distribution diverges from the source distribution. This framework is especially relevant for applications that require joint compression and retrieval, and in scenarios involving distributional shifts due to processing. We show that the proposed formulation extends the classical minimum entropy coupling framework by integrating a bottleneck, allowing for a controlled degree of stochasticity in the coupling. We explore the decomposition of the Minimum Entropy Coupling with Bottleneck (MEC-B) into two distinct optimization problems: Entropy-Bounded Information Maximization (EBIM) for the encoder, and Minimum Entropy Coupling (MEC) for the decoder. Through extensive analysis, we provide a greedy algorithm for EBIM with guaranteed performance, and characterize the optimal solution near functional mappings, yielding significant theoretical insights into the structural complexity of this problem. Furthermore, we illustrate the practical application of MEC-B through experiments in Markov Coding Games (MCGs) under rate limits. These games simulate a communication scenario within a Markov Decision Process, where an agent must transmit a compressed message from a sender to a receiver through its actions. Our experiments highlight the trade-offs between MDP rewards and receiver accuracy across various compression rates, showcasing the efficacy of our method compared to conventional compression baseline.

压缩马尔可夫信息论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。