虽然被发配出来开题报告估计是不用写了,不过之前的论文还是要看的,顺便回顾一下用的经典算法,推推式子。

其实,crowdsourcing或者multi-source truth finder这个方向使用的方法还是挺广的,首先使用的以概率图模型为主,各种大神在自己的数据集上用新的生成模型灌水,剩下的各种方法也不少,比如用的NMF或者概率矩阵分解来做矩阵填充的,更有甚者用张量分解来求隐变量的。还有一派就是用Minmax Entropy来解释的,求解方法自然就是拉格朗日乘子法。老规矩,先放大神的链接

对偶函数

对于一个常见的优化问题

\[ \begin{align} &\operatorname{minimize}& & f_0(x) \\ &\operatorname{subject\;to}& &f_i(x) \leq 0, \quad i = 1,\dots,m \\ & & &h_i(x) = 0, \quad i = 1,\dots,p \end{align} \]

称为约束最优化问题。然后引入广义拉格朗日函数generalized Lagrange function

\[ L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \]

其中\(\lambda \geq 0\)\(\nu\)称为拉格朗日乘子Lagrange multiplier vectors或者叫对偶变量dual variables。那对偶这个名字从什么地方来的呢?

对偶函数

定义对偶函数如下

\[ g(\lambda,\nu) = \inf_{x\in\mathcal{D}} L(x,\lambda,\nu) = \inf_{x\in\mathcal{D}} \left ( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right ) \]

即对偶函数是以对偶变量为自变量的函数,这个函数是拉格朗日函数的下届。仔细看一下这个式子,取\(f^*\)为原问题的最优解,由于\(\lambda \geq 0\)所以显然应该有\(g(\lambda, \nu) \leq f^*\)。此外,还有一个重要的结论是,不论原函数是不是凸的,其对偶函数总是凹的。这个又和另外两个结论有关,一个问题如果能表示成一族仿射函数的逐点上确界,则其一定是一个凸的,如果一个问题能表示成一族仿射函数的逐点下确界,则其一定是一个凹的。具体可以看Convex optimization

对偶问题

之前已经提过,由于\(\lambda \geq 0\)的存在,导致\(g(\lambda, \nu) \leq f^*\)成立,既然已经知道了对偶函数是原函数最优解\(f^*\)的下界估计,就可以用转化原问题了。

\[ \begin{align} &\operatorname{maximize}& & g(\lambda,\nu) \\ &\operatorname{subject\;to}& &\lambda \succeq 0 \end{align} \]

这个就是原问题的对偶问题。由于对偶问题一定是凸的,所以,这个问题总是一个凸优化问题。

但是这样就引来另一个问题,等号是不是能取到。

弱对偶性

\(g^*\)表示对偶问题的最优解,对于在原问题\(f(x)\)上的任意一个可行解\(\hat(x)\)则由于\(\lambda \geq 0\)所以

\[ \sum_{i=1}^m \lambda_i f_i(\hat{x}) + \sum_{i=1}^p \nu_i h_i(\hat{x}) \leq 0 \]

\[\begin{split} g(\lambda,\nu) = \inf_{x\in\mathcal{D}} L(x,\lambda,\nu) \leq L(\hat{x},\lambda,\nu) \leq f^* \end{split}\]

\(g^* \leq f^*\)

这称为弱对偶性,即对偶问题的最优解不大于原问题的最优解。

强对偶性

当原问题和对偶问题的最优解相等,即\(f^* == g^*\)的时候,称其为满足强对偶性。

Slater's Theorem提供了一个强对偶的充分条件:

若存在一点\(x \in relint \ D(D的相对内点集)\)满足 \(f_i(x) < 0, i = 1,...,m, \ \ Ax = b\)成立,且原问题是凸优化问题时,则强对偶性成立。

不过这个条件并不是常用来计算的条件。

松弛互补

这个结论也很直观,而且在SVM的推导中都能注意到,假设已经有强对偶成立。同时最优解分别为\(x^*\)\((\lambda^*, \nu^*)\)。则

\[ \begin{split} f_0(x^\ast) = & g(\lambda^\ast,\nu^\ast) \\ = & \inf_{x} \left( f_0(x) + \sum_{i=1}^m \lambda_i^\ast f_i(x) + \sum_{i=1}^p \nu_i^\ast h_i(x) \right) \\ \leq & f_0(x^\ast) + \sum_{i=1}^m \lambda_i^\ast f_i(x^\ast) + \sum_{i=1}^p \nu_i^\ast h_i(x^\ast) \\ \leq & f_0(x^\ast) \end{split} \]

因此,中间所有的不等号都可以取到等号。所以其中的项,$_{i=1}^m _if_i(x) \(应该为0,这就意味着,当\)_i\(不为0的时候,\)f_i(x^)\(应该为0,而\)f_i(x*)\(不为0的时候,\)_i^*$应该为0。这就称之为互补松弛条件。

KKT条件

KKT条件为

\[ \begin{split} f_i(x^\ast) \leq & 0, \quad i=1,\dots,m \\ h_i(x^\ast) = & 0, \quad i=1,\dots,p \\ \lambda_i^\ast \geq & 0, \quad i=1,\dots,m \\ \lambda_i^\ast f_i(x^\ast) = & 0, \quad i=1,\dots,m \\ \nabla f_0(x^\ast)+\sum_{i=1}^m \lambda_i^\ast\nabla f_i(x^\ast)+\sum_{i=1}^p \nu_i^\ast\nabla h_i(x^\ast) = & 0 \end{split} \]

假设所有函数\(f_0,...,f_m\)以及\(h_1,...,h_p\)都是一阶可微的,并且其定义域为开集。则KKT条件为取得强对偶的充分必要条件。

这一结论其实也挺直观的,前面三个式子都是约束条件,第四个是之前提到了互补松弛条件,而最后一项,说明了\(\nabla f_0\)应该是\(\nabla f_i\)\(\nabla h_i\)的线性组合,也是由于在每个算子和\(x\)方向上的梯度都优化到了0,所以,应该是最优的。

Minimax Entropy in Crowdsourcing

这篇是2012年NIPS上的论文,之后他们有继续提出了Conditional Entropy等方法。

CrowdSourcing本质上,很大一部分在估计题目的难度,用户在不同题目上的正确率以及正确答案。

上图中,\(z_{ij}\)为第\(i\)个人为第\(j\)个题给的标签,而\(\pi_{ij}\)则是给这个标签的概率,由于概率应该为1则,\(\sum_k \pi_{ijk} = 1\)。论文中提出一个观点,即每个人的判断概率\(\pi_{ij}\)应该服从最大熵原则。传统的majority voting方法假设每个题的做对的概率应该是一致的即难的题做对的少,简单的题作对的多,并用\(\sum_i z_{ijk}\)来模拟\(\sum_i \pi_{ijk}\),而Dawid and Skene's method任务,每个人在不同分类上的错误应该是有规律的,即每个人在把某一类型错判为另一类型的概率应该是有规律的,并用\(\sum_j y_{jl}z_{ijk}\)来模拟\(\sum_k y_{jl}\pi_{ijk}\)。同时,考虑这两点,然后用最大熵原则。得到

进一步,由于我们关系的是真实标签\(y_{jl}\),所以,我们应该选择能使最大熵最小的那个值,原文中用的词是peaky,即选择\(y\)使得\(\pi\)的波动范围最小,这个有点像频率学派的minmax risk

所以目标函数加个最小化的目标,然后约束项应该还有对于\(\sum_l y_{jl} = 1\)的约束。得到,

考虑到,这样形式并不好解,同时带有\(min\)\(max\),要先去掉一个,假设,已知真实的分布\(\pi^*_{ijk}\)这样为了接近极大熵的分布,只要加一个\(\sum_ i\pi_{ijk} = \sum_i \pi_{ijk}^*\)就行了,然后同时也应该有\(\sum_j y_{jl}\pi_{ijk} = \sum_j y_{jl} \pi_{ijk}^*\)

然后,用拉格朗日乘子法可得拉格朗日函数为

\[\begin{split} L = - & \sum_{i = 1}^m \sum_{j = 1}^n \sum_{k - 1}^c\pi_{ijk}\ln\pi_{ijk} \\ & + \sum_i^m \sum_j^n \lambda_{ij}(\sum_k^c \pi_{ijk} - 1) \\ & + \sum_j^n \sum_k^c \tau_{jk} \sum_i^m (\pi_{ijk} - \pi_{ijk}^*) \\ & + \sum_i^m \sum_k^c \sum_l^c \sigma _{ikl} \sum_j y_{jl} (\pi_{ijk} - \pi_{ijk}^*) \end{split}\]

然后根据KKT条件,求偏导然后令其等于0。最终可以解得

\[ \pi_{ijk} = \frac{exp \sum_{l=1}^c y_{jl}(\tau_{jk} + \sigma_{ikl})}{\sum_{s = 1}^c exp \sum_{l = 1}^c y_{jl}(\tau_{js} + \sigma_{isl})} \]

然后,像EM算法一样,每次分别迭代\(\tau_{jk}\)\(\sigma_{ijl}\)然后在更新隐变量\(y_{jl}\)就行了。

当然,这里直接要求用户的判断分布\(\pi_{ijk}\)\(z_{ijk}\)完全吻合太过强硬了,可以加入一些松弛因子即不要求完全相等将\(\sum_i \pi_{ijk} = \sum_i z_{ijk}\)改成\(\sum_i (\pi_{ijk} - z_{ijk}) = \epsilon_{jk}\),然后将\(-\sum_j \sum_c \epsilon^2_{jk}/ 2\alpha_j\)正则项加入目标函数,这也是中常用的套路,防止过拟合。

话说这周事情好烦,弄得我现在连式子都懒得打了。




X