论文标题
在二进制分类器的Kolmogorov复杂性上
On the Kolmogorov Complexity of Binary Classifiers
论文作者
论文摘要
我们在与标记样品一致的二元分类器的预期最小kolmogorov复杂性上提供了紧密的上限和下限。预期的大小不超过目标概念的复杂性，加上标签的条件熵。
We provide tight upper and lower bounds on the expected minimum Kolmogorov complexity of binary classifiers that are consistent with labeled samples. The expected size is not more than complexity of the target concept plus the conditional entropy of the labels given the sample.
