Analysis of Learning from Positive and Unlabeled Data

本文从基本的分类损失出发,推导了PU的分类问题其实就是Cost-sensitive classification的形式,同时,通过实验证明了如果使用凸函数作为loss function,例如hinge loss会导致错误的分类边界(有bias),因此需要使用例如ramp loss之类的凹函数。同时,论文还对先验$\pi$存在偏差的情况进行了讨论,说明了如果样本中大部分都是正样本,那么就算先验差距比较大,但对总体的分类效果没有太大影响。最后对分类边界进行讨论,证明了使用PU进行分类的误差小于监督学习误差的$2\sqrt{2}$倍。

#基本概念和定义

  1. Ordinary classification
    • Bayes optimal classifier的目标是最小化misclassification rate,这在Introduction to Statistical Machine Learning By Masashi Sugiyama 书里有定义,直观理解就是最小化期望错分率:
    • $R(f) = \pi R_1 (f) + (1 - \pi) R_{-1}(f)$
    • 这里的$R_1$表示false negative rate,也就是分错正类的概率,乘以先验正类的概率$\pi$
    • $R_{-1}$表示false positive rate,也就是分错负类的概率,乘以先验负类的概率$1-\pi$
    • 这样,对分错样本的概率分别乘以其先验概率,就是其错分概率的期望。
  2. Cost-sensitive classification
    • 如果对于某种错误我们的敏感程度不一样,那么就乘以不同的权重,重新定义为:
    • $R(f) = \pi c_1 R_1(f) + (1-\pi) c_{-1}R_{-1}(f)$
    • 这里用$c_1$和$c_{-1}$分别表示对两种错分的代价
  3. PU classification
    • 定义在未标记数据集$X$ 中的分布:

      • $P_X = \pi P_1 + (1-\pi) P_{-1}$

      • 注意,这里的$P_X$可以理解为样本的分布:

        $$P(x) = P(y=1)P(x|y=1) + P(y=-1)P(x|y=-1)$$

      • 也就是说,$P_1 = P(x|y = 1), P_{-1} = P(x|y=-1)$

      • 论文认为两个数据集的分布不同:

        • 对于positive sample:$x \sim P(x|y=1)$
        • 对于unlabel sample:$x\sim P_X$
    • 对于PU问题,我们没有办法直接得到负类的信息,因此我们想要把目标函数中的$R_{-1}(f)$去掉。定义$R_X(f)$表示在$P_X$分布下预测为正类的风险risk:

      $$\begin{equation}\begin{split}R_X(f) &= P_X(f(X = 1)) \&= \pi P_1(f(X) = 1) + (1-\pi) P_{-1}(f(X) = 1) \&= \pi(1-R_1(f)) + (1-\pi) R_{-1}(f) \end{split}\end{equation}$$

    • 这样,我们就可以将$R_{-1}$替换为$R_X(f)$:

      $$\begin{equation}\begin{split}R(f) &= \pi R_1(f) + (1-\pi)R_{-1}(f) \&= \pi R_1(f) - \pi(1-R_1(f)) + R_X(f) \&= 2\pi R_1(f) + R_X(f) - \pi \end{split}\end{equation}$$

    • 我们可以定义$\eta \sim \frac{n}{n + n'}$是$P_1$与$P_X$的占比,也就是在我们正类数据集样本数占所有样本数的比例,因此可进一步写成:

      • $R(f) = c_1\eta R_1(f) + c_X(1-\eta)R_X(f)- \pi$
      • 其中$c_1 = \frac{2\pi}{\eta},c_X = \frac{1}{1-\eta}$
    • 这样,我们就把PU分类问题转换为了Cost-sensitive classification问题。通过设置不同的阈值并最小化分类错误率,就可以使用SVM等分类器进行训练。

#Necessity of non-convex loss functions

论文认为,如果在PU分类问题中使用常见的凸函数作为loss function,可能导致结果有biased,因此需要选择非凸函数。

  1. Loss functions in ordinary classification
    • 在分类器上定义一个符号函数:$sign (g(x)) = f(x)$
    • 使用01损失,仿照之前的期望错分率定义损失函数:
      • $J_{0-1}(g) = \pi E_1[l_{0-1}(g(X))] + (1-\pi )E_{-1}[l_{0-1}(-g(X))] $
      • $l_{0-1}$在大于0的时候取0,小于0时取1
    • 由于01损失在实际中很难优化,因此用ramp loss代替:
      • $l_R(z) = \frac{1}{2}\max(0,\min(2,1-z))$
    • 而为了保证凸性,因此一般使用hinge loss
      • $l_H(z) = \frac{1}{2}\max(1-z,0)$
    • 可以发现,ramp loss 在大于1时没有损失,在-1到1之间为线性损失,而大于1以后损失恒定为1
    • hinge loss在小于1时也依然为线性损失(在SVM中使用)
  2. Ramp loss function in PU classification
    • ramp loss带入之前定义的PU目标函数中,同时根据ramp loss的特殊性质:$l_R(-z) +l_R(z) = 1$,我们可以得到
    • $J_{PU-R} (g) = \pi E_1[l_R(g(X))] + (1-\pi)E_{-1}[l_R(-g(X))]$
    • 这个形式和最初的分类损失相同,也就是说,它们会有相同的分类边界
  3. Hinge loss function in PU classification
    • 如果用hinge loss,同样的道理我们可以得到:
      • pu3
    • 除了最初分类损失的项,还有另外的一项惩罚
    • 作者认为,这个惩罚会导致分类边界的改变,及时$g(X)$很好的区分了数据,由于惩罚项的存在,目标函数可能并不会是最小值
  4. 论文做了一个简单的实验,说明了如果使用hinge loss,那么在先验$\pi$增大的情况下,阈值增大的非常快,也就是说,会将所有的样本都标记为正样本(阈值为1),因此false positive概率为1。这样会导致总的分类错误率为$1-\pi$:
  5. 因此,作者用实验和公式说明了,光光最小化分类错误率不够(因为当$\pi$很大时,会将所有类标记为正类以获得最小的损失$1- \pi$,因此需要使用ramp loss对其进行惩罚

#Effect of inaccurate class-prior estimation

现实中有很多方法来估计先验$\pi$,但如果估计值离实际值很大(有偏),那么会对我们的PU问题造成什么样的影响?

  1. Ordinary classification
    • 考虑普通分类的情形。我们的目标函数时最小化$R(f,\pi) = \pi R_1(f) + (1-\pi) R_{-1}(f)$
    • 注意,这是一个凹函数。
    • 如果我们的先验为$\hat{\pi}$,最小化后得到的分类器为$\hat{f}$,这时候固定$\hat{f}$,真实的先验为$\pi$,可以发现当靠近$\hat{\pi}$时两个risk 的差距最小,随着$\pi$的变化而逐渐增大:
  2. PU classification
    • 通过变量替换,我们同时定义当前的先验为$\hat{\pi}$,真实的先验为$\pi$,可以得到risk为:
      • $R(f) = (2\hat{\pi} - \pi) R_1(f) + (1-\pi)R_{-1}(f) + \pi - \hat{\pi}$
    • 可以发现,如果 $\hat{\pi } \le \frac{1}{2}\pi$ 时,该分类就完全失效了(risk 的符号改变)
    • 将其进行归一化,定义effective class prior为:
    • pu7
    • 观察图片可以发现,当真实的$\pi$很大,那么估计的先验就算相差大一点,影响也不大(顶部较为平缓),这与现实相符。例如,如果我们在异常检测中,正类远远大于负类,那么估计的阈值稍微小优点,也不会对risk造成太大的改变。
    • 同样,如果真实的正类并不多,那么对正类的估计如果不准的话,会对结果造成较大改变。

#Generalization error bounds for PU classification

待完成。。。

#Reference

  1. Analysis of Learning from Positive and Unlabeled Data
  2. Introduction to Statistical Machine Learning By Masashi Sugiyama
  3. Why are the popular loss functions convex?
Load Comments?