论文标题
两相多重分类可实现的错误指数
Achievable Error Exponents for Two-Phase Multiple Classification
论文作者
论文摘要
我们重新访问了古特曼（Tit 1989）的$ M $ - 元分类，该分类的任务是确定是否生成测试顺序，其分布是否与$ M $培训序列之一相同。我们的主要结果是两阶段测试，其理论分析及其最佳保证。具体而言，我们的两阶段测试是顺序测试的特殊情况，只有两个决策时间点：测试的第一阶段是带有拒绝选项的固定长度测试，仅当我们测试的第二阶段而我们的测试的第二阶段决定\ emph {not}允许拒绝选项时，我们的测试的第二个阶段才会进行。为了为我们的测试提供理论保证，我们使用类型方法得出可实现的误差指数，并使用HSU，Li和Wang（ITW，2022）最近提出的技术来得出最佳顺序测试的相反结果。在分析上和数值上，我们表明我们的两个相测试可以使用正确选择测试参数的最佳顺序测试的性能。特别是，与最佳顺序测试一样，我们的测试不需要最终的拒绝选项来实现最佳误差指数区域，而最佳的固定长度测试需要拒绝选项才能实现同一区域。最后，当$ m = 2 $和$ m $ - $ - ARY假设测试时，我们将结果专注于二进制分类，当训练序列的长度和测试序列的比例趋于无穷大，以便可以完美估计生成分布。
We revisit $M$-ary classification of Gutman (TIT 1989), where one is tasked to determine whether a testing sequence is generated with the same distribution as one of the $M$ training sequences or not. Our main result is a two-phase test, its theoretical analysis and its optimality guarantee. Specifically, our two-phase test is a special case of a sequential test with only two decision time points: the first phase of our test is a fixed-length test with a reject option, the second-phase of our test proceeds only if a reject option is decided in the first phase and the second phase of our test does \emph{not} allow a reject option. To provide theoretical guarantee for our test, we derive achievable error exponents using the method of types and derive a converse result for the optimal sequential test using the techniques recently proposed by Hsu, Li and Wang (ITW, 2022) for binary classification. Analytically and numerically, we show that our two phase test achieves the performance of an optimal sequential test with proper choice of test parameters. In particular, similarly as the optimal sequential test, our test does not need a final reject option to achieve the optimal error exponent region while an optimal fixed-length test needs a reject option to achieve the same region. Finally, we specialize our results to binary classification when $M=2$ and to $M$-ary hypothesis testing when the ratio of the lengths of training sequences and testing sequences tends to infinity so that generating distributions can be estimated perfectly.
