The performance of machine learning classification algorithms are evaluated
by estimating metrics, often from the confusion matrix, using training data and
cross-validation. However, these do not prove that the best possible
performance has been achieved. Fundamental limits to error rates can be
estimated using information distance measures. To this end, the confusion
matrix has been formulated to comply with the Chernoff-Stein Lemma. This links
the error rates to the Kullback-Leibler divergences between the probability
density functions describing the two classes. This leads to a key result that
relates Cohen's Kappa to the Resistor Average Distance which is the parallel
resistor combination of the two Kullback-Leibler divergences. The Resistor
Average Distance has units of bits and is estimated from the same training data
used by the classification algorithm, using kNN estimates of the
KullBack-Leibler divergences. The classification algorithm gives the confusion
matrix and Kappa. Theory and methods are discussed in detail and then applied
to Monte Carlo data and real datasets. Four very different real datasets -
Breast Cancer, Coronary Heart Disease, Bankruptcy, and Particle Identification
- are analysed, with both continuous and discrete values, and their
classification performance compared to the expected theoretical limit. In all
cases this analysis shows that the algorithms could not have performed any
better due to the underlying probability density functions for the two classes.
Important lessons are learnt on how to predict the performance of algorithms
for imbalanced data using training datasets that are approximately balanced.
Machine learning is very powerful but classification performance ultimately
depends on the quality of the data and the relevance of the variables to the
problem.

机器学习分类算法的性能通过评估混淆矩阵中的度量指标进行，但这并不能证明达到了最佳性能。通过使用信息距离测量，可以估计错误率的根本限制。混淆矩阵已经与 Chernoff-Stein 引理相结合，将错误率与描述两个类别的概率密度函数之间的 Kullback-Leibler 距离相关联。这导致了一个关键结果，将 Cohen's Kappa 与电阻器平均距离相关联，后者是两个 Kullback-Leibler 距离的并联电阻器组合。通过使用 kNN 估计 KullBack-Leibler 距离，从分类算法使用的相同训练数据对 Resistor Average Distance 进行估计，该距离以比特为单位。接下来，论文详细讨论了该理论和方法，并将其应用于蒙特卡洛数据和真实数据集。分析了四个非常不同的真实数据集 - 乳腺癌、冠心病、破产和粒子鉴别 - 其中包含连续值和离散值，并将它们的分类性能与预期的理论极限进行了比较。在所有情况下，这种分析表明由于两个类别的概率密度函数的底层特征，算法无法表现得更好。通过使用近似平衡的训练数据集来预测不平衡数据的算法性能，可以学到重要的教训。机器学习非常强大，但分类性能最终取决于数据的质量和变量与问题的相关性。

通过 Kullback-Leibler 散度与 Cohen's Kappa 相关联的分类性能限制

Limits to classification performance by relating Kullback-Leibler  divergence to Cohen's Kappa

The probability that a user will click a search result depends both on its
relevance and its position on the results page. The position based model
explains this behavior by ascribing to every item an attraction probability,
and to every position an examination probability. To be clicked, a result must
be both attractive and examined. The probabilities of an item-position pair
being clicked thus form the entries of a rank-$1$ matrix. We propose the
learning problem of a Bernoulli rank-$1$ bandit where at each step, the
learning agent chooses a pair of row and column arms, and receives the product
of their Bernoulli-distributed values as a reward. This is a special case of
the stochastic rank-$1$ bandit problem considered in recent work that proposed
an elimination based algorithm Rank1Elim, and showed that Rank1Elim's regret
scales linearly with the number of rows and columns on "benign" instances.
These are the instances where the minimum of the average row and column rewards
$\mu$ is bounded away from zero. The issue with Rank1Elim is that it fails to
be competitive with straightforward bandit strategies as $\mu \rightarrow 0$.
In this paper we propose Rank1ElimKL which simply replaces the (crude)
confidence intervals of Rank1Elim with confidence intervals based on
Kullback-Leibler (KL) divergences, and with the help of a novel result
concerning the scaling of KL divergences we prove that with this change, our
algorithm will be competitive no matter the value of $\mu$. Experiments with
synthetic data confirm that on benign instances the performance of Rank1ElimKL
is significantly better than that of even Rank1Elim, while experiments with
models derived from real data confirm that the improvements are significant
across the board, regardless of whether the data is benign or not.

该研究提出了基于位置的模型来解释用户点击搜索结果的概率，并提出了 Bernoulli rank-1 bandit 和 Rank1ElimKL 算法来解决排名问题。该算法在不同条件下的实验表现证实其较简单的对手策略更加优秀。

点击反馈的伯努利一级臂老虎机

Bernoulli Rank-$1$ Bandits for Click Feedback

We revisit lower bounds on the regret in the case of multi-armed bandit
problems. We obtain non-asymptotic, distribution-dependent bounds and provide
straightforward proofs based only on well-known properties of Kullback-Leibler
divergences. These bounds show in particular that in an initial phase the
regret grows almost linearly, and that the well-known logarithmic growth of the
regret only holds in a final phase. The proof techniques come to the essence of
the information-theoretic arguments used and they are deprived of all
unnecessary complications.

本文研究多臂老虎机问题的遗憾下界，并利用 Kullback-Leibler 分歧的已知特性证明了非相对论、分布依赖的限制。这些限制特别表明，在初始阶段遗憾几乎线性增长，并且在最后阶段仅出现知名的对数增长。证明技术突出了信息理论论证的本质，并去除了所有不必要的复杂性。