Optimal Rates of Teaching and Learning Under Uncertainty
Optimal Rates of Teaching and Learning Under Uncertainty
复制标题
不确定性下的最佳教学率
DOI：
--
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
J. Scarlett
中科院分区：
文献类型：
--
作者：
Yan Hao Ling;J. Scarlett
在本文中，我们考虑了最近提出的不确定性下的教学模型，其中教师接收对被二进制对称噪声破坏的单个比特的独立观察，并根据迄今为止观察到的比特通过另一个二进制对称通道顺序传输给学生。在给定数量的传输 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 后，学生输出未知位的估计，我们感兴趣的是随着 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 增加的错误概率的指数衰减率。我们提出了一种新颖的块结构教学策略，其中教师对每个块中收到的 1 的数量进行编码，并表明所得误差指数是二进制相对熵 <inline-formula> <tex-math notation="LaTeX">$Dleft({frac {1}{2}|max (p,q)}
ight)$ </tex-math></inline-formula>，其中 <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> 和 <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> 是噪声参数。这与基于数据处理不等式的简单逆结果相匹配，并解决了 [Jog and Loh, 2021] 和 [Huleihel <italic>et al.</italic>, 2019] 的两个猜想。此外，我们还表明，教师和学生所需的计算时间在 <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> 中呈线性关系。我们还研究了一种更通用的设置，其中二进制对称通道被通用二进制输入离散无记忆通道取代。我们提供了可实现性界限和逆界限，并表明两者在某些情况下一致，包括（i）当两个通道相同时，以及（ii）当学生-教师通道是二元对称通道时。更一般地说，我们给出了足够的条件，在该条件下我们的学习率对于块结构协议来说是最好的。
In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by binary symmetric noise, and sequentially transmits to a student through another binary symmetric channel based on the bits observed so far. After a given number <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> of transmissions, the student outputs an estimate of the unknown bit, and we are interested in the exponential decay rate of the error probability as <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> increases. We propose a novel block-structured teaching strategy in which the teacher encodes the number of 1s received in each block, and show that the resulting error exponent is the binary relative entropy <inline-formula> <tex-math notation="LaTeX">$Dleft({frac {1}{2}|max (p,q)}
ight)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$p$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> are the noise parameters. This matches a trivial converse result based on the data processing inequality, and settles two conjectures of [Jog and Loh, 2021] and [Huleihel <italic>et al.</italic>, 2019]. In addition, we show that the computation time required by the teacher and student is linear in <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>. We also study a more general setting in which the binary symmetric channels are replaced by general binary-input discrete memoryless channels. We provide an achievability bound and a converse bound, and show that the two coincide in certain cases, including (i) when the two channels are identical, and (ii) when the student-teacher channel is a binary symmetric channel. More generally, we give sufficient conditions under which our learning rate is the best possible for block-structured protocols.