PML Exercise 5 Solutions

Exercise 5.1 [Reject option in classifiers]

In many classification problems one has the option either of assigning $x$ to class $j$ or, if you are too uncertain, of choosing the reject option. If the cost for rejects is less than the cost of falsely classifying the object, it may be the optimal action. Let $\alpha_i$ mean you choose action $i$, for $i = 1 : C +1$, where $C$ is the number of classes and $C + 1$ is the reject action. Let $Y = j$ be the true (but unknown) state of nature. Define the loss function as follows

$$\lambda(\alpha_i|Y = j) = \begin{cases} 0 & \text{if } i = j \text{ and } i, j \in \{1, \dots, C\} \\ \lambda_r & \text{if } i = C + 1 \\ \lambda_s & \text{otherwise} \end{cases}$$

In other words, you incur 0 loss if you correctly classify, you incur $\lambda_r loss$ (cost) if you choose the reject option, and you incur $\lambda_s$ loss (cost) if you make a substitution error (misclassification).

• a. Show that the minimum risk is obtained if we decide $Y = j$ if $p(Y = j|x) \ge p(Y = k|x)$ for all $k$ (i.e., $j$ is the most probable class) and if $p(Y = j|x) \ge 1 - \frac{\lambda_r}{\lambda_s}$; otherwise we decide to reject.
• b. Describe qualitatively what happens as $\lambda_r/\lambda_s$ is increased from 0 to 1 (i.e., the relative cost of rejection increases).

解答：

• a. 易知 $p(Y = j|x) \ge p(Y = k|x)$，拒绝时期望损失 $\lambda_r$，选择 $j$ 类别期望损失 $(1-p(Y=j\mid x))\times \lambda_s+p(Y=j\mid x)\times 0$，当选择 $j$ 类别期望损失小于拒绝时则接受，即 $p(Y=j\mid x)\geq 1-\frac{\lambda_r}{\lambda_s}$。
• b. 当 $\frac{\lambda_r}{\lambda_s}$ 从 0 到 1 增加时，即拒绝的相对成本变高，则更有可能选择 $j$ 类别。

Exercise 5.2 [Newsvendor problem †]

Consider the following classic problem in decision theory / economics. Suppose you are trying to decide how much quantity $Q$ of some product (e.g., newspapers) to buy to maximize your profits. The optimal amount will depend on how much demand $D$ you think there is for your product, as well as its cost to you $C$ and its selling price $P$. Suppose $D$ is unknown but has pdf $f(D)$ and cdf $F(D)$. We can evaluate the expected profit by considering two cases: if $D > Q$, then we sell all $Q$ items, and make profit $\pi = (P - C)Q$; but if $D < Q$, we only sell $D$ items, at profit $(P - C)D$, but have wasted $C(Q - D)$ on the unsold items. So the expected profit if we buy quantity $Q$ is

$$E\pi(Q) = \int_Q^\infty (P - C)Qf(D)dD + \int_0^Q (P - C)Df(D)dD - \int_0^Q C(Q - D)f(D)dD$$

Simplify this expression, and then take derivatives wrt $Q$ to show that the optimal quantity $Q^*$ (which maximizes the expected profit) satisfies

$$F(Q^*) = \frac{P - C}{P}$$

解答： 对利润等式展开

$$\begin{aligned} \mathbb{E}[\pi(Q)]&=(P-C)Q\int_{Q}^{\infty}f(D)\mathrm{d}D+(P-C)\int_{0}^{Q}Df(D)\mathrm{d}D-C\int_{0}^Q (Q-D)f(D)\mathrm{d}D\\ &=(P-C)Q(F(\infty)-F(Q))+(P-C)\int_{0}^{Q}Df(D)\mathrm{d}D-C\int_{0}^Q(Q-D)f(D)\mathrm{d}D \end{aligned}$$

对其求导数（注意最后一项得展开求导？变上限积分求导定理被积函数里面，绝对不能含有求导的自变量）

$$\begin{aligned} \frac{\mathrm{d}\mathbb{E}[\pi(Q)]}{\mathrm{d}Q}&=(P-C)(1-F(Q))-(P-C)Qf(Q)+(P-C)Qf(Q)-C[\int_{0}^Qf(D)\mathrm{d}D+Qf(Q)-Qf(Q)]\\ &=(P-C)(1-F(Q))-C[F(Q)-F(0)]\\ &=0\\ \Rightarrow & F(Q^*)=\frac{P-C}{P} \end{aligned}$$

Exercise 5.3 [Bayes factors and ROC curves †]

Let $B = p(D|H_1)/p(D|H_0)$ be the Bayes factor in favor of model 1. Suppose we plot two ROC curves, one computed by thresholding $B$, and the other computed by thresholding $p(H_1|D)$. Will they be the same or different? Explain why.

解答： 在分类问题中，ROC 曲线的形状仅取决于样本得分的相对排序（Ranking），而不取决于得分的绝对数值。 因为 $\frac{p(H_1|D)}{p(H_0|D)} = \frac{p(H_1)}{p(H_0)} \cdot \frac{p(D|H_1)}{p(D|H_0)}$，令 $O=\frac{p(H_1)}{p(H_0)}$，又有 $p(H_0|D) = 1 - p(H_1|D)$，得到

$$\frac{p(H_1|D)}{1 - p(H_1|D)} = O \cdot B \Rightarrow p(H_1|D) = \frac{O \cdot B}{1 + O \cdot B}$$

因为先验概率 $p(H_1)$ 和 $p(H_0)$ 都是固定的正数，所以先验优势 $O > 0$。对于任意的贝叶斯因子 $B \ge 0$，这是一个严格单调递增的函数。这意味着对于任意两个样本数据 $D_i$ 和 $D_j$，如果 $B(D_i) > B(D_j)$，那么绝对可以保证 $p(H_1|D_i) > p(H_1|D_j)$。

对于贝叶斯因子上的任意一个阈值 $\tau_B$，在后验概率上都必定存在一个与之完全等价的阈值 $\tau_p = \frac{O \cdot \tau_B}{1 + O \cdot \tau_B}$。在这两个对应的阈值下，分类器做出的正负类划分完全一样，计算出的 TPR 和 FPR 也就完全一样，因此画出来的 ROC 曲线完全相同。

Exercise 5.4 [Posterior median is optimal estimate under L1 loss]

Prove that the posterior median is the optimal estimate under L1 loss.

解答： L1 损失为 $\lvert \theta - \theta^* \rvert$，后验中位数 $\hat{\theta}$ 即满足 $p(\hat{\theta} \leq \theta\mid D) =\frac{1}{2}$，计算其期望损失

$$\begin{aligned} \mathcal{L}(\hat{\theta})&=\int \lvert \theta-\hat{\theta}\rvert p(\theta\mid D)\mathrm{d}\theta\\ &= \int_{-\infty}^{\hat{\theta}} (\hat{\theta} - \theta) p(\theta|D) \mathrm{d}\theta + \int_{\hat{\theta}}^{\infty} (\theta - \hat{\theta}) p(\theta|D) \mathrm{d}\theta \end{aligned}$$

对 $\hat{\theta}$ 进行求导

$$\begin{aligned} \frac{\mathrm{d}\mathcal{L}(\hat{\theta})}{\mathrm{d}\hat{\theta}}&=(\hat{\theta}-\hat{\theta})p(\hat{\theta}\mid D)+\int_{-\infty}^{\hat{\theta}}\frac{\partial (\hat{\theta} - \theta) p(\theta|D)}{\partial \hat{\theta}}\mathrm{d}\theta-(\hat{\theta} - \hat{\theta}) p(\hat{\theta}|D)+\int_{\hat{\theta}}^{\infty}\frac{\partial (\theta - \hat\theta) p(\theta|D)}{\partial \hat{\theta}}\mathrm{d}\theta\\ &= \int_{-\infty}^{\hat{\theta}} p(\theta|D) \mathrm{d}\theta - \int_{\hat{\theta}}^{\infty} p(\theta|D) \mathrm{d}\theta = 0 \Rightarrow P(\theta \le \hat{\theta} \mid D) = \frac{1}{2} \end{aligned}$$

⚠️ 完善： 注意莱布尼茨积分法则的完整形式

$$\frac{\mathrm d}{\mathrm dx}\int_{a(x)}^{b(x)} f(x,t)\,\mathrm dt = \int_{a(x)}^{b(x)} \frac{\partial f}{\partial x}(x,t)\,\mathrm dt + f\bigl(x,b(x)\bigr)b'(x) - f\bigl(x,a(x)\bigr)a'(x)$$