样本量估计

2019-12-16 本文已影响0人热爱生活的大川

ERM

真实损失
定义 $D$ 为总体分布， $f$ 为真实标签函数， $h$ 为标签函数，也叫模型或分类器。
$L_{D,f}(h)$ 为在总体分布和真实标签函数分别为D和f时h所对应的误差，也叫做真实损失。其公式为
$\begin{align} L_{D,f}(h) &= P_{x \sim D}[f(h(x) \neq f(x)] \\ &= D(\{x \in D:h(x) \neq f(x)\}) \\ \end{align}$
经验损失
抽取 $m$ 个独立同分布样本，组成一个m-tuples的样本组 $S_x$ ，将 $S_x$ 的集合定义为样本集 $S$ 。
以[m]表示数据集{1,2,...,m}， $L_S$ 表示形式上的经验损失函数。
则有如下经验损失的定义公式
$L_S(h)=\frac{\|\{i \in [m]: h(x_i)\neq y_i \} \|}{m}$
当 $L_S \to 0$ 时，可训练得到模型 $h_S$ 。
过拟合
定义 $\epsilon$ 为误差精度，过拟合是指经验损失可训练而真实损失超过了误差精度，表达式为
$L_{D,f}(h_S)>\epsilon$
为消除过拟合，我们主要手段是限制合理模型范围。
经验风险最小化(ERM)
定义模型的有限假设类 $\mathscr{H}$ ，则令
$h_S=\arg\min_{h \in \mathscr{H} }L_S(h)$

置信度

误导集
定义模型的有限假设类 $\mathscr{H}$ ，则无效的模型集合为
$\mathscr{H}_B = \{ h \in \mathscr{H}:L_{D,f}(h)>\epsilon \}$
定义 $S_x$ 表示样本集 $S$ 中的一个样本组，则样本组的误导集可表示为
$M=\{S_x \in S: \exists h \in \mathscr{H}_B , L_S(h) \to 0 \}$
置信度
定义 $_\delta$ 为抽取到无效样本组的概率， $1-\delta$ 为置信度。其定义式为
$\delta = D^m(\{ S_x \in S:L_{D,f}(h_S)>\epsilon \})$
如下推导
$\begin{align} \delta &\le D^m(M) \\ & \le \sum_{h \in \mathscr{H}_B}D^m(\{S_x \in S: L_S(h) \to 0 \}) \\ & = \sum_{h \in \mathscr{H}_B}\prod_{i=1}^{m}D(\{ x_i:h(x_i)=y_i=f(x_i) \}) \\ & \le \sum_{h \in \mathscr{H}_B}\prod_{i=1}^{m}(1-\epsilon) \\ & = \| \mathscr{H}_B \| (1-\epsilon)^m \\ & \le \| \mathscr{H} \| e^{-\epsilon m} \end{align}$
得到
$\delta \leq \| \mathscr{H} \| e^{-\epsilon m}$
样本量
$m \ge \frac{\ln(\| \mathscr{H} \|/\delta)}{\epsilon}$

举例：性别估计是个二分类，假设使用1000个0-1特征，则 $\| \mathscr{H} \|=2^{1000}$ ，根据经验 $\delta=0.001$ ，希望的精度 $\epsilon=0.1$ ，则样本量 $m \ge 10100\ln(2)$

设模型参数数量为N，参数取值范围为R，则
$\begin{align} m & \ge \frac{\ln(\| \mathscr{H} \|/\delta)}{\epsilon} \\ & = \frac{N\ln(R)- \ln(\delta)}{\epsilon} \end{align}$
可见样本数量应与参数数量N成正比例关系。

样本量估计

ERM

置信度

猜你喜欢

热点阅读