不可知学习

从计算复杂度角度看，判别式模型与生成式模型的两类任务（不可知学习与多精度）是等价的。

正则性引理可以给出一种高效的预言机归约，将不可区分任务（多精度）归约到区分任务（不可知学习）。

不可知学习不假设数据可由目标概念完美标记，而是允许噪声，目标是找到一个假设，使其错误率与假设类中最优成员的错误率相当（至多相差一个常数）。

不可知学习通常被认为是计算困难的，即使对于简单的假设类（如半空间），在一般分布下也没有已知的高效算法。