Convex Formulation for Learning

作者: zealscott | 来源:发表于2019-04-03 13:45 被阅读0次

Convex Formulation for Learning
project Abeona #2
Convex Optimization 2 -- Convex
Convex Optimization 3 -- Convex
Convex Relaxation, Convex Conjug
About conditional 0-3
16. Recommender Systems
pose graph formulation
Debiasing：Formulation & Summariz
Convex Set and Convex Function凸集

Unbiased PU learning.

该论文在之前PU learning中使用非凸函数作为loss的基础上，对正类样本和未标记样本使用不同的凸函数loss，从而将其转为凸优化问题。结果表明，该loss（double hinge loss）与非凸loss（ramp）精度几乎一致，但大大减少了计算量。

Introdution

Background

论文首先强调了PU问题的重要性，举了几个例子：

Automatic face tagging
- 用户对自己的画像标记为正类，其余都是未标记数据，需要正确识别用户的照片
Inlier-based outlier detection
- 需要在只有inliers和未标记数据中识别outliers，这种方法比完全无监督学习的效果要好
Class is too diverse
- 如果要识别的数据集中类别太多，也就是one-vs-rest classification
Negative-class dataset shift
- 由于训练数据和测试数据采集的实践差异导致负类样本的概率分布发生了变化，那么如果使用PU learning，可以减少重新标记的代价

Method

作者简单回顾了之前PU learning的常见做法：

直接在正类样本和未标记样本中训练一个分类器。但很显然这样的效果非常差，因为未标记样本中包含两类数据。
根据先验 $\pi$ 使用一个loss function来权衡每个样本的权重，目标是使得loss function最小化。但这样做的结果是会产生bias。
使用满足 $l(z) + l(-z) = 1$ 条件的loss function可以消除这种bias，但对于ramp loss，是非凸函数，导致在优化过程中可能求导局部解。

因此，本文提出了一种新的凸函数的loss function，也就是double hinge loss，不仅能够消除bias，同时也能保证凸性。关键点在于对未标记数据和正类数据使用不同的loss function。

Non-convex PU classification

作者回顾了在 Analysis of Learning from Positive and Unlabeled Data 这篇文章中的方法。

首先，根据two-simple的假设，我们可以认为正类样本和未标记样本是在两个数据集上分别进行采样得到的：
- $x_i \sim p(x|y = 1) \quad x^{'}_i \sim p(x)$
- 对于未标记样本来说，边际概率可以表示为： $p(x) = \pi p(x|y=1) + (1-\pi ) p(x|y=-1)$
- 目标是训练一个分类器 $g(x)$
最佳的分类器是最小化01损失：
- $J_{0-1}(g) = \pi E_1[l_{0-1}(g(X))] + (1-\pi )E_{-1}[l_{0-1}(-g(X))] $
- 其中loss function为 $l_{0-1}(z) = \frac{1}{2}sign(z) + \frac{1}{2}$
但由于我们的数据集没有负类样本，因此没有办法估计 $E_{-1}$ ，所以可以将其转换为：
- $J_{0-1}(g) = 2 \pi E_1[l_{0-1}(g(X))] + E_{X}[l_{0-1}(-g(X))] -\pi$
- 其中 $E_X$ 是在 $p(x)$ 上的期望： $E_X[l_{0-1}(-g(X))] = \pi E_1[l_{0-1}(-g(X))] + (1-\pi)E_{-1}[l_{0-1}(-g(X))]$
- 但是，对01损失函数进行优化是非常困难的，因为其梯度在除了0以外的地方都为0
因此，直觉的使用hinge loss作为替代，但是我们发现会多出来一个惩罚项，这样会导致估计的bias。而如果使用 $l(z) + l(-z) = 1$ 这样的loss function，就不会有bias（使用凹函数ramp loss）

Convex PU classifiction

由于 $l_{0-1}(-g(X)) = 1 - l_{0-1}(g(X))$ ，可以将损失函数改写为：
- $J_{0-1}(g) = \pi E_1[l_{0-1}(g(X)) - l_{0-1}(-g(X))] + E_{X}[l_{0-1}(-g(X))]$
我们用另外的损失函数 $l(z)$ 代替，则可以得到：
- $J(g) = \pi E_1[\hat{l}(g(X))] + E_X[l(-g(X))]$
- 注意到，在正类样本上我们的损失是composite loss： $\hat{l}(z) = l(z) - l(-z)$
- 在正类样本上使用composite loss，在未标记样本上使用普通的损失
因此，最关键的就是 $\hat{l}(z)$ 是不是凸函数，论文做了以下的证明：
- If the composite loss $\hat{l}(z)$ is convex, it is linear.
  - 为了简便，论文取了最简单的线性关系： $\hat{l}(z) = -z$
  - 因此，损失函数变为： $J(g) = \pi E_1[-g(X)] + E_X[l(-g(X))]$
  - 作者证明该损失函数表明learning with label noise实际上就是PU learning的特例
- 实际中，我们用linear-inparameter mode来进行分类：
  - $g(x) = \alpha^T\phi(x) + b$
  - 其中 $\phi(x) = [\phi_1(x),....,\phi_m(x)]^T$ ，也就是作用在所有样本上的基函数（作者建议使用高斯核）
基于composite loss是线性的假设，用均值代替期望，可以将loss function改写为：
- $\hat{J}(\alpha,b) = -\frac{\pi}{n}\sum\limits_{i=1}^n \alpha^T\phi(x_i) - \pi b + \frac{1}{n^{'}} \sum\limits_{j=1}^{n^{'}}l(-\alpha^T\phi(x_j^{'})-b) + \frac{\lambda}{2} \alpha^T \alpha$
- 最后一项做正则项
根据观察我们发现，在原来的损失函数中： $J(g) = \pi E_1[-g(X)] + E_X[l(-g(X))]$ ，这两项始终为正数；然而在我们的经验风险函数中，由于正则项的存在，前两项可能变为可能为负数，论文说在实际中需要限制这两项始终非负（这导致了后面nnPU的出现）

Convex loss functions for PU classiﬁcation

可以发现，我们最终的目标函数就只需要指定 $l$ 就完成了，本节作者讨论了多种可能的凸函数作为loss。

Squared loss
- 论文使用了作为loss，可以将目标函数变为：
  - $J_S(g) = \frac{1}{4}\int g(x)^2p(x)dx -\frac{1}{2}\int g(x) [2\pi p_1(x) - p(x)]dx +C$
- 同时，很巧妙的定义了在给定的条件下，分类为1和分类为0的概率的差：
  - $r(x) = p(y=1|x) - p(y=-1|x) = [2\pi p(x|y=1) - p(x)] / p(x)$
  - 积分后可以是不相关的常数，带入目标函数并化简可以得到（太赞了！）：
  - $\frac{1}{4}\int (g(x) - \frac{2\pi p_1(x) - p(x)}{p(x)})^2 p(x)dx$
- 论文说这个目标函数的好处是可以直接从理论分析得到数值解，如果我们省略linear-inparameter mode中的常数：
  - $\hat{J}_S(\alpha) = \frac{1}{4n^{'}} \alpha^T\Phi^T_U \Phi_U\alpha + \frac{1}{2n^{'}}1^T\Phi_U \alpha - \frac{\pi}{n}1^T\Phi_P \alpha + \frac{\lambda}{2}\alpha^T \alpha$
  - 对这个二次型函数求导即可得到 $\alpha$ 的数值解（牛啊。。）
- 但这个loss函数并不好，原因在于 $l_S(z) = \frac{1}{4}(z-1)^2$ 当 $z$ 大于1时这个loss会增大，而对于二分类来说，如果大于1说明能正确识别。
logistic loss
- 定义Logistic loss为，因此带入目标函数为：
  - $J_{LL}(g) = -\pi E_1[g(X)] + E_X[\log(1+\exp(g(X)))]$
- 有 $\log(1+\exp(-z)) = -\log \frac{1}{1+e^{-z}} = -z + \log(1+\exp(z))$ ，带入原始的分类损失中，可以得到其和目标函数是一样的，因此可以用于PU classification
- 最终经验风险函数可以表示为：
  - $\hat{J}_{LL} (\alpha,b) = -\frac{\pi}{n}\sum\limits_{i=1}^n \alpha^T \phi(x_i) - \pi b + \frac{\lambda}{2} \alpha^T\alpha + \frac{1}{n^{'}}\sum\limits_{j=1}^{n^{'}} l_{LL}(-\alpha^T\phi(x^{'}_j) - b)$
Double hinge losses
- 由于hinge loss并不是凸函数，因此不满足我们的定理（ $\hat{l}$ 表示线性的）
- 论文构造了Double hinge losses使得满足凸函数的性质：
- $l_{DH}(z) = \max(-z,\max (0,\frac{1}{2} - \frac{1}{2}z))$
- 因此经验风险函数可以写为：
  - $\hat{J}_{LL} (\alpha,b) = -\frac{\pi}{n}\sum\limits_{i=1}^n \alpha^T \phi(x_i) - \pi b + \frac{\lambda}{2} \alpha^T\alpha + \frac{1}{n^{'}}\sum\limits_{j=1}^{n^{'}} l_{DH}(-\alpha^T\phi(x^{'}_j) - b)$

Theoretical Analysis

待看。。。

Experiments

三组对比实验在MNIST数据集上进行实验，将0作为正类，其余作为负类，同时假设先验已知：

Hinge损失（会有bias）
Logistic 和 Double hinge loss
Ramp （非凸优化）

实验结果说明，提出的凸优化结果与非凸优化效果相当，但减少了计算量。

Convex Formulation for Learning
Unbiased PU learning. 该论文在之前PU learning中使用非凸函数作为loss的基础上，...
project Abeona #2
Scanner: character-by-character formulation:recognizing "...
Convex Optimization 2 -- Convex
Outline affine and convex sets some important examples op...
Convex Optimization 3 -- Convex
Outline basic properties and examples operations that pre...
Convex Relaxation, Convex Conjug
了解机器学习的人应该都知道，在优化非凸函数的时候，希望用一个凸函数来代替这个非凸函数，以获取凸函数在优化过程中良好...
About conditional 0-3
Zero Conditional Formulation If/When + Present simple + P...
16. Recommender Systems
Recommender Systems Problem formulation Content-based rec...
pose graph formulation
Debiasing：Formulation & Summariz
Formulation： Bias的类型其实有很多，其中有的是非常明确的，而有的问题并非well defined。...
Convex Set and Convex Function凸集
Welcome To My Blog Rockafeller说:"优化问题的分水岭不是线性和非线性,而是凸性和非...