基本思想

GBRank 和 RankSVM 都是用来解决 LTR 问题的 pairwise 方法。利用 \Phi(q,d) 得出 query 和文档的特征向量，x1、x2分别是d1、d2的特征，取(x1, x2)为正样本，(x2, x1)为负样本，代入 SVM 模型中。

介绍

RankSVM 是在2002年提出的，之前工作关于LTR的工作貌似只有 Pointwise 相关的，比如 PRanking，这样的排序学习算法Work需要含有档位标注的训练样本，一般有以下几种获取方式：

1. 需要人工/专家标注
2. 诱导用户对展现的搜索结果进行反馈

这样就会存在会成本高、可持续性低、受标准者影响大等缺点。

而 RankSVM 只需要根据搜索引擎的点击日志构建 Pair 对即可，相对于先前的工作在算法的实用性上有了非常大的改善。

训练样本设计

对于 q 为一次 query，和文档集合 D = \{d_1, \dots,d_m\} ，算法按照相关性给出给出一个文档排序 r^* 。算法一般找不到最优的 r^* ，而是通过其排序顺序 r_{f(q)} 和最优值得差距来评估搜索排序函数 f 。

一般搜索引擎都会记录用户搜索后展现的结果以及用户的点击情况，这种日志成本较低，并且改造系统也较为方便，而RankSVM的训练样本就是从这种点击日志中进行提取。

由于用户点击的doc概率和排序的位置影响很大，虽然一般都是偏爱相关性较大的doc，但是如果这种doc排在很后面的话其实用户也几乎不会点，所以 RankSVM 就只考虑top级别的点击日志，一般为top 10

另外在构建训练数据时同一 query 下认为用户被点击 doc 相关性要高于没有被点击的 doc ，但是由于用户是从上往下浏览网页的，所以排在前面的 doc 被点击的概率会大于后面的 doc ，因此 RankSVM 使用的最终策略为:

Pair 构建策略：给定一组排序情况 (doc_1,doc_2,doc_3,\cdots) ，以及 C 记录了用户点击 doc 的情况，则有
doc_i{\overset{r^*}{<}} doc_j 对于所有pair对 1 \leq i ，同时 i \in C ， j \notin C

r^* 表示应有的优化排序，也就是被点击文档的相关性要大于排在该文档前面并且未被点击的文档，看上去很绕口，看个栗子：

假如某个用户搜索某个 query 得到首页10个doc，按顺序使用 doc_i 进行表示，如果该用户点击了 1,3,7 三个文档，则认为有:

doc_3 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_2 \\
doc_7 {\overset{r^*}{<}} doc_4 \\
doc_7 {\overset{r^*}{<}} doc_5 \\
doc_7 {\overset{r^*}{<}} doc_6

表示该 query 下 doc_3 的相关性要高于 doc_2 ，理应排在前面，而 doc7 的相关性也应该要高于 doc_{2，4，5，6} ，但是可以发现未见 doc_1 的相关性鉴定，这是由于 doc_1 已经是排在了第一位，本身位置点击概率就就是最高的，所以无法判断与其他文档相关性的高低，同理， doc_{8，9，10} 也未纳入相关性的排序中。

训练样本可以通过这样方式进行构建，但是遗憾的是并没有一种机器学习算法能直接使用这种数据进行训练学习-_-

搜索函数的理论框架

在上面的栗子中，我们希望用新算法完成 doc_{1，3，7} 排在top 3，那这样的文档的真实相关性高的将会排到前面，RankSVM 采用Kendall’s Tau （肯德尔等级相关系数）来统计实际排序与算法排序的度量，先看下面两个变量:

1. P 表示排序序列中保持一致性的 Pair 对数量，也就是真实相关性高的排在第的前面。
2. Q 表示排序序列中保持不一致的 Pair 对数量（逆序数），也就是由于算法的误差导致真实相关性低的排在了高的前面
3. 同时 P+Q=\binom{m}{2} ， m 表示序列中文档的数量，因为长度为 m 的序列可能组成的 Pair 对为 m 的2组合

则 \tau 的计算方式为:

\tau(r_a，r_b)=\frac{P-Q}{P+Q}=1-\frac{2Q}{\binom{m}{2}}

r_a 为真实排序， r_b 为算法排序

比如实际文档中的顺序为:

d_1{\overset{r^*}{<}}d_2{\overset{r^*}{<}}d_3{\overset{r^*}{<}}d_4{\overset{r^*}{<}}d_5

但是算法的排序顺序为:

d_3{\overset{\hat{r}}{<}}d_2{\overset{\hat{r}}{<}}d_1{\overset{\hat{r}}{<}}d_4{\overset{\hat{r}}{<}}d_5

因此可以发现算法排序中有3对 Pair 不一致了( \{d_2，d_3\} ， \{d_1，d_2\} ， \{d_1，d_3\} )，所以 Q=3 ， P=4+3+2+1-3 = 7 ，最终的 \tau(r，\hat{r})=\frac{7-3}{10}=4
\tau 的值越大，表示排序效果越接近真实，比如上面的 \tau(r，r)=\frac{10-0}{10}=1

还证明了由逆序数 Q 的一个式子为平均准确率指标的下界(具体证明看原文附录):

 AvgPrec(\hat{r}) \geq \frac{1}{R} \left[Q+\binom{R+1}{2}\right]^{-1} \left(\sum_{i=1}^{R} \sqrt{i}\right)^2

R 为排序出现的文档中与 query 相关文档数量（这个是[Mean Average Precision](http://kubicode.me/2016/02/15/Machine Learning/Learning-To-Rank-Base-Knowledge/#MAP)中的标注，与 Pair 对的样本稍微有点差别）
从这个角度也可以看到 \tau 来衡量排序效果好坏的合理性.

现在可以定义学习排序函数得问题，对于有 m 个文档的 D 集合上，有固定且未知分布的概率 P{r(q, r^*)} ，目标是学习到一个 f(q) ，其使得肯德尔系数 \tau 最大化。

\tau_{P}(\mathrm{f})=\int \tau\left(\mathrm{r}_{\mathrm{f}(\mathrm{q})}, \mathrm{r}^{*}\right) d \operatorname{Pr}\left(\mathrm{q}, \mathrm{r}^{*}\right)

以下算法采用经验风险最小化，假设现在有 n 个 q_i 作为训练样本，他们各自的目标排序为 r_i^* ，也就是:

(q_1,r_1^*),(q_2,r_2^*),(q_3,r_3^*),\cdots,(q_n，r_n^*)

给定一个大小为 n 且独立同分布的训练样本 S ，其中算法排序为 \hat{r}_i ，则排序算法的优化目标是将下列式子

\tau_{S}(\mathrm{f})=\frac{1}{n} \sum_{i=1}^{n} \tau\left(\mathrm{r}_{\mathrm{f}\left(\mathrm{q}_{i}\right)}, \mathrm{r}_{i}^{*}\right)

最大化。

RankSVM 排序

假设能找到一个排序算法 f 能使得上面的 \tau_s 得到最大化，对于一个指定的查询 q ，每个文档 d_i 使用特征向量映射方法 \Phi(q，d_i) ， \vec{w} 是通过学习调整的权重向量。 \Phi(q,d) 是映射到描述查询 q 和文档 d 之间的匹配的特征的映射，例如网页 title, h1, h2 标题共有的单词数，或者 d 的页面排名。

如果是直接使用线性排序方法:

\left(\mathrm{d}_{i}, \mathrm{~d}_{j}\right) \in \mathrm{f}_{\vec{w}}(\mathrm{q}) \Longleftrightarrow \vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{i}\right)>\vec{w} \Phi\left(\mathrm{q}, \mathrm{d}_{j}\right)

\vec{w} 表示权重向量，线性排序下，排序分数为权重 x 特征向量

上图表示一个二维的权重与特征图，在排序的顺序的就是特征在权重上的投影位置顺序，比如单从 W_1 维度进行观察可以看到的排序顺序为{1，2，3，4}，而如果按 W_2 维度则是{2，3，1，4}。

在这里，间隔被定义为当数据点投射到排序向量 w 时两个数据点之间的最近距离，如图 d_1,d_2 ：

为了最大化 \tau_s ，可以最小化 Q 来代替，也就是说对于线性的排序， Q=0 就是表示下面的等式全成立(也就是最大化)

\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j) \\
… \\
\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i)>\vec{w} \Phi(q,d_j)

不幸的是，优化这个是一个NP问题。
但我们可以让他们绝大多数都成立，SVM 在由于软间距最大时可以看到熟悉的身影，可以通过引入（非负）松弛变量 \xi_{i,j,k} 并按如下方式最小化上限 \sum\xi_{i,j,k} 来使用SVM技术来近似解。：

\begin{aligned}
&\min[\frac{1}{2} \vec{w} \cdot \vec{w} + C \sum \xi_{i，j，k}]
\\ \\
\text{s.t. }&\forall (d_i,d_j) \in r_1^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) + 1 - \xi_{i,j,1} \\
&\cdots \\
&\forall (d_i,d_j) \in r_n^* : \vec{w} \Phi(q,d_i) \geq \vec{w} \Phi(q,d_j) +1 - \xi_{i,j,n} \\
&\forall_i \forall_j \forall_k:\xi_{i,j,k} \geq 0
\end{aligned}

\xi 为松弛项， C 表示平衡项

因此优化该问题时可以将约束转为:

\vec{w} \Phi(q，d_i)-\vec{w} \Phi(q，d_j) \geq 1 - \xi_{i，j，1}

并且由于是线性排序，可以进一步精简为:

\vec{w} \left(\Phi(q，d_i)-\Phi(q，d_j)\right) \geq 1 - \xi_{i，j，1}

在 Pair 对中只可能 d_i 是否排在 d_j 前面是一个二值结果，所以我们可以将 d_i 排在 d_j 前面的 Pair 为正标签，否则为负标签:

y=\left\{
\begin{aligned}
+1 & \quad if \quad \vec{w} \Phi(q，d_i)>\vec{w} \Phi(q，d_j) \\
-1 & \quad otherwise\\
\end{aligned}
\right.

则最终可以将约束可以写成:

y_i \cdot \vec{w} \left(\Phi(q，d_i)-\Phi(q，d_j)\right) \geq 1 - \xi_{i，j，1}

其中传统的偏置项在 RankSVM 是不需要的，以为正好 Pair 相减时就消掉了

所以这样一个问题等价于 SVM 应用于成对向量差上的分类问题。完全将上面构建的样本转为一个分类问题，使用 SVM 的对偶形式进行求解，并且还可以使用核函数进行非线性的分类。 \vec{w} 对应了排序函数，可以对query-doc pair进行打分和排序。

所以 RankSVM 可以看做是一个回归问题，模型应用的时候，使用当前样本的预估值作为排序的依据。

但是样本的构造就发生了变化，每一条样本表示的是一个序关系。所以，损失函数变为（样本 x_i 排名好于 x_j ）

\begin{matrix} minimize &&\ \ \ \ \frac{1}{2}|w|^2+C\sum_{ij} \xi_{ij}\\s.t. && (wx_i+b) -(wx_j+b) \ge 1-\xi_{ij}\\ &&\xi_{ij}\ge 0 \end{matrix}

上式为了方便理解，没有进行化简，上式也可以依葫芦画瓢引入核函数。

RankSVM 可以看做是寻找一个超平面，使得点对 (x_i , x_j) 对平面的几何间隔差最大。

rsv(q，d_i)= \vec{w}^* \Phi(q，d_i) = \sum_l^n \alpha_{k,l}^*y_i(\Phi(q_k，d_l) \cdot \Phi(q，d_j))

上面是表示两个不同的 query 所表示的特征空间，不同的形状表示文档与对应 query 的相关性档位，三角形 x_1 表示相关性档位高，圆圈 x_2 表示相关性档位一般，叉叉 x_3 表示相关性档位差。
将这些样本转为 Pair 对之后可以有：

可以发现 x_1-x_3 和 x_1-x_2 为正样本，而 x_2-x_1 和 x_3-x_1 为负样本，因此可以形成对应的训练数据进行训练，其实这样形成的样本是对称的，因此在实际使用中一般只保留一侧即可。

总结

RankSVM 很好的解决原始训练样本构建难的问题，根据点击日志构建样本，既考虑了doc之间的顺序，又保证了可持续性，并且其 Pair 对的训练正好可以使用SVM进行求最优化，而SVM分类器已经是非常成熟并且广泛使用的一种机器学习算法。
因此 RankSVM 虽然在2002年就提出，但是至今在工业界还是广泛使用，但是现在的主要难点是样本 Pair 对的构建，针对不同的场景也不同的策略，不一定只是根据点击顺序，实际使用中还要考虑新样本数据。

参考

1. Joachims T. Optimizing search engines using clickthrough data[C], Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2002:133-142.

2. Learning to Rank for Information Retrieval and Natural Language Processing, Hang Li

3. 原始博文来源于 [RankSvm-基于点击数据的搜索排序算法](http://kubicode.me/2016/03/30/Machine Learning/RankSvm-Optimizing-Search-Engines-using-Clickthrough-Data/)，但他转述错了论文的某些细节部分，感觉像机翻，所以修正写好重发。

4. LTR中RankSVM算法的基本思路是什么？

5. RankSVM原理

一般的约束优化问题

约束优化问题常常可以化简为以下不等式，

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N

\end{aligned}

可以写成拉格朗日函数

L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x)

那么原问题可以等价于无约束形式：

\min_{x\in\mathbb{R}^p}\max_{\lambda,\eta}L(x,\lambda,\eta)\  \\s.t.\ \lambda_i\ge0

求偏导后， n_i(x) 会等于0。当未满足约束时， m_i(x) 0 ， \lambda_i 可以调整为最大值 \infin ， \max_{\lambda,\eta}L(x,\lambda,\eta)\ = \infin ；满足其约束时， m_i(x) \le 0 ， \max_{\lambda,\eta}L(x,\lambda,\eta) 为常数。取 min 显然过滤了不满足约束情况。

这个问题的对偶形式：

\max_{\lambda,\eta}\min_{x\in\mathbb{R}^p}L(x,\lambda,\eta)\ s.t.\ \lambda_i\ge0

对偶问题是关于 \lambda, \eta 的最大化问题。

\max_{\lambda_i,\eta_j}\min_{x}L(x,\lambda_i,\eta_j)\le\min_{x}\max_{\lambda_i,\eta_j}L(x,\lambda_i,\eta_j)

证明，理解为L的值域，值域里面的任何一个数，大于等于它的最小值，小于等于它的最大值

   \min\limits_{x}L\le L\le\max\limits_{\lambda,\eta}L \\  
  \Rightarrow \max\limits_{\lambda,\eta}\min\limits_{x}L\le L   , \min\limits_{x}\max\limits_{\lambda,\eta}L\ge L \\

对偶问题的解小于原问题，有两种情况：

1. 强对偶，能取等于号
2. 弱对偶，不能取等于号

几何解释

特别的，二次规划问题都满足 slater 条件。对于一个凸优化问题，有如下定理：

凸优化问题满足某些条件如 Slater 条件 \Rightarrow 它和其对偶问题满足强对偶关系。

注意是充分不必要条件。记问题的定义域为： \mathcal{D}=\mathrm{dom}f(x)\cap \mathrm{dom} m_i(x)\cap \mathrm{dom}n_j(x) 。 Slater 条件为：

\exist\hat{x}\in \mathrm{relint}\mathcal{D}\ \text{s.t. } \forall i=1,2,\cdots,M,m_i(x)\lt0 \\  \mathrm{relint} \text{ 表示相对内部（不包含边界的内部）。}\\

1. 对于大多数凸优化问题，Slater 条件成立。
2. 对于不满足条件的，可以松弛 Slater 条件，如果 M 个不等式约束中，有 K 个函数为仿射函数，那么只要其余的 (M – K) 个函数满足 Slater 条件即可。

KKT 条件

原问题及其拉格朗日函数为

\begin{aligned}

&\min_{x\in\mathbb{R^p}}f(x)\\
&s.t.\ m_i(x)\le0,i=1,2,\cdots,M\\
&\ \ \ \ \ \ \ \ n_j(x)=0,j=1,2,\cdots,N
\\
&L(x,\lambda,\eta)=f(x)+\sum\limits_{i=1}^M\lambda_im_i(x)+\sum\limits_{i=1}^N\eta_in_i(x) \\
&\text{令 } g(\lambda, \eta) = \min_{x} L(x,\lambda,\eta)
\end{aligned}

对偶问题有

\begin{aligned}
&\max_{\lambda, \eta} g(\lambda, \eta) \\
&\text{s.t. } \lambda_i\ge0
\end{aligned}

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件，KKT 条件 \Leftrightarrow 强对偶关系。关于原问题， p^* 是最优解， x^* 是最优解参数。关于对偶问题， d^* 是最优解， \lambda^*, \eta^* 是最优解参数。证明弱对偶性实际上就是证明 d^* \le p^* ，强对偶性是证明 d^* = p^* 。KKT 条件对最优解的条件为：

1. 可行域：

   \begin{aligned}
   m_i(x^*)\le0\\
   n_j(x^*)=0\\
   \lambda^*\ge0
   \end{aligned}

2. 互补松弛 \lambda^*m_i(x^*)=0,\forall m_i

   \begin{aligned}
   d^*&=\max_{\lambda,\eta}g(\lambda,\eta)=g(\lambda^*,\eta^*) \\
   &=\min_{x}L(x,\lambda^*,\eta^*) \\
   &\le L(x^*,\lambda^*,\eta^*) \\
   &=f(x^*)+\sum\limits_{i=1}^M\lambda^*m_i(x^*) \\
   &\le f(x^*)=p^*
   \end{aligned}

   为了满足相等，两个不等式必须成立，于是，对于第一个不等于号，需要有梯度为0条件，对于第二个不等于号需要满足互补松弛条件。

3. 梯度为0： \frac{\partial L(x,\lambda^*,\eta^*)}{\partial x}|_{x=x^*}=0

综述

SVM（support vector machine, 支持向量机），是一个二元分类模型，采用方法是高维空间下用超平面分割不同数据点，并使两类的之间的间隔最大化，SVM 的三大核心在于间隔、对偶、核技巧。

1. hard-margin SVM
2. soft-margin SVM
3. kernel Method

参考资料：

Doto, 统计学习方法|支持向量机(SVM)原理剖析及实现

《统计学习方法》李航

支持向量机通俗导论（理解SVM的三层境界）

硬间隔分类器 hard margin

最大化泛化能力，减少过拟合

\mathcal{D} = {\{(x_i, y_i)\}}_{i=1}^{N}, x_i \in \mathbb{R}^p, y_i \in \{ +1, -1\} ， y_i = 1 为正例， y_i=-1 为负例。超平面为

w^Tx+b = 0

一个分类正确的超平面要满足

y_i(w^Tx_i+b) > 0

让超平面在正确分类所有数据点的前提下，改变 w,b 的值，就获得了新的超平面，使得该超平面与所有数据点的距离之中的最小值，在其他所有能正确分类的超平面中是最大的。那么目标就是

\begin{aligned}
&\mathop{\max}_{w, b} margin(w, b)\\
&\text{s.t. } y_i(w^Tx_i + b) > 0\text{. }\forall{i = 1, 2, \dots,N}
\end{aligned}

距离函数为

\begin{aligned}
margin(w, b) = & \mathop{\min}_{i}distance(w, b, x_i)
\\ = & \mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b \mid
\end{aligned}

代入式子，常数 \frac{1}{\|w\|} 可以提出来，绝对值符号可以去掉，目标是

\begin{aligned}
\mathop{\max}_{w, b} margin(w, b)
 = & \mathop{\max}_{w, b} [\mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b\mid ]\\
 = & \mathop{\max}_{w, b}[\frac{1}{\|w\|}\mathop{\min}_{i}y_i(w^Tx_i + b) ]   \\
& \text{s.t. } y_i(w^Tx_i + b) > 0\text{. }
\end{aligned}

函数间隔和几何间隔 funtional margin & geometric margin

\mid w^Tx_i+b\mid 可以确定数据点与超平面的距离，从 w^Tx_i+b 和 y_i 的符号是否一致可以确定分类是否正确，于是自然就有了函数间隔的定义，来确定分类结果正确的置信度

\hat{\gamma_i} = y_i(w^Tx_i + b)

其最小值为

\hat{\gamma} = \mathop{\min}_{i}{\hat{\gamma_i}}

但这个定义有问题，例如 2x_1+4x_2+2 = 0 和 x_1+2x_2+1 = 0 是同一个平面，但函数间隔算出来是不同的。 w,b 成比例变化 \lambda 倍，超平面不会发生改变，最小函数间隔变成了 \lambda\hat{\gamma} ，所以要让同一个超平面的方程形式也是一致的。

函数间隔同除以超平面的法向量的 L_2 范数，就有了几何间隔的定义

\gamma_i = y_i(\frac{w^Tx_i}{\|w\|} + \frac{b}{\|w\|}) \\

最小值为

\gamma = \mathop{\min}_{i}{\gamma_i}

回顾高中数学说的点到平面距离公式（向量描述）

d = \frac{\mid w^Tx+b\mid}{\|w\|}

是不是有点像？其实几何间隔就是点到超平面的距离。回到 SVM 上，要最大化最小的几何间隔，其与最小函数间隔的数量关系

\gamma = \frac{\hat{\gamma}}{\|w\|} = \frac{y_i(w^Tx_i + b)}{\|w\|}

结合上式，目标就变成了

\begin{aligned}
&\mathop{\max}_{w,b}\gamma 
&\text{s.t. }\frac{y_i(w^Tx_i + b)}{\|w\|} \ge \gamma \\
\Rightarrow&\mathop{\max}_{w,b}\frac{\hat{\gamma}}{\|w\|} 
&\text{s.t. }y_i(w^Tx_i + b) \ge \hat{\gamma}
\end{aligned}

改变函数间隔，就是改变分子， w,b 会相应地改变。若更新使得 w_{i+1}=\lambda w_i, b_{i+1} = \lambda b_i, \lambda \neq 0 ，那超平面不会改变（可以验证），函数间隔变为 \lambda 倍，几何间隔不变。反之， w,b 不按同样的比例改变，超平面和几何间隔才会变。

换句话说，如果我们调整 w,b 使得函数间隔变为 \lambda 倍，并不会改变几何间隔。

函数间隔不为 0 ，放缩 w,b 使最小函数间隔 \hat{\gamma }= 1 ，令 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}}

\begin{aligned}
&y_j(\frac{w^T_ix_j}{\hat{\gamma}} + \frac{b_i}{\hat{\gamma}}) =\frac{\hat{\gamma}}{\hat{\gamma}}=  1 \\
\Rightarrow&y_j({w^T_{i+1}x_j} + b_{i+1}) = 1
\end{aligned}

没有改变平面本身和几何间隔，实际上，我们可以让最小函数间隔取任意值且 \hat{\gamma} \neq 0 ，都有 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}} ，我们最终求解出的SVM参数 w,b 仍然和目标的超平面参数是一致的，不会对不等式的约束和目标函数造成影响。取最简单的 \hat{\gamma} = 1 ，原问题就变成了

\begin{aligned}
&\mathop{\max}_{w,b}\frac{1}{\|w\|}\\
&\text{s.t. }\mathop{\min}_iy_i(w^Tx_i + b) = 1 \Leftrightarrow y_i(w^Tx_i + b) \ge 1
\end{aligned}

对偶问题 dual problem

最大值问题可以转换为最小值问题，刚才的目标函数可以化为

\begin{aligned}
&\mathop{\min}_{w,b} \frac{1}{2}\| w \| \\
&\text{s.t. }y_i(w^Tx_i + b) \ge1,\forall i=1,2,\dots,N
\end{aligned}

有这种形式，是因为凸优化问题一般都为求最小值，目标函数的常数不会造成什么影响， \frac{1}{2} 主要是为了后续计算。

为了消除约束条件，引入拉格朗日算子

\mathcal{L}(w, b, \alpha) = \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))

算子 \alpha = [\alpha_1, \alpha_2, \cdots, \alpha_N]^T,\alpha_i \ge 0,i=1,\cdots,N. ，令 \Delta_i = 1 - y_i(w^Tx_i + b) , \forall i= 1, \cdots, N.

其实就有

\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) =  \left \{
\begin{aligned}
&\frac{1}{2}\|w\| + \infty = +\infty , &\text{if }\Delta_i > 0 \\
&\frac{1}{2}\|w\| ,&\text{if }\Delta_i \le 0
\end{aligned}
\right.

\mathop{\max}\mathcal{L} 的最小值就等于刚才的目标函数，把约束归并到目标中，相当于丢弃了 \Delta_i >0 的解空间，目标变为

infty\mathop{\min}_{w,b}\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) = \mathop{\min}_{w,b}(+ \infty, \frac{1}{2}\|w\|) = \mathop{\min}\frac{1}{2}\|w\|

带 w,b 约束的原问题转化为无约束的

\begin{aligned}
&\mathop{\min}_{w,b} \mathop{\max}_\alpha \mathcal{L}(w, b, \alpha) \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

它的对偶问题是

\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha)  \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

如何理解这个问题？

\mathop{\min}\mathop{\max}f \ge \mathop{\max}\mathop{\min} f

举个栗子，宁为鸡头，不为凤尾。（or 瘦死的骆驼比马大） \mathop{\max}f 就是凤， \mathop{\min}f 就是鸡， \mathop{\max}\mathop{\min}f 就是鸡头， \mathop{\min}\mathop{\max}f 就是凤尾。

凸优化二次问题就满足强对偶关系，即等号也成立。

回到 SVM ，刚才的目标是

\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha)  \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

先求 \mathop{\min}_\alpha \mathcal{L} ，可以求偏导得到最优解

\begin{aligned}
\frac{\partial \mathcal{L}}{\partial b} 
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))) \\
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b)
\\
&= \frac{\partial}{\partial b}(-\sum_{i = 1}^{N} \alpha_i y_i  b) \\
&= -\sum_{i = 1}^{N} \alpha_i y_i
\end{aligned}

令 \frac{\partial \mathcal{L}}{\partial b} = 0 ，得 \sum_{i = 1}^{N} \alpha_i y_i = 0 ，将其代入 \mathcal{L} ，求关于 w 的偏导

\begin{aligned}
\frac{\partial \mathcal{L}}{\partial w} 
&= \frac{\partial}{\partial b}[ \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))] \\
&= \frac{\partial}{\partial b}[\frac{1}{2}w^Tw +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - 0] \\
&= w - \sum_{i = 1}^{N} \alpha_i y_i  x_i
\end{aligned}

令 \frac{\partial \mathcal{L}}{\partial w} = 0 ，得最优解参数 w* = \sum_{i = 1}^{N} \alpha_i y_i x_i 。结合之前公式，推出 \sum_{i = 1}^{N} \alpha_i y_i b = 0 （ b 不是向量），将其代入 \mathcal{L}

\begin{aligned}
\mathop{\min}_\alpha \mathcal{L}(w, b, \alpha) 
&= \frac{1}{2}\|w\| +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b 
\\
&=  \frac{1}{2}(\sum_{i = 1}^{N} \alpha_i y_i  x_i)^T (\sum_{j = 1}^{N} \alpha_j y_j  x_j) 
+ \sum_{i = 1}^{N} \alpha_i
- \sum_{i = 1}^{N} (\alpha_i y_i  x_i )^T(\sum_{j = 1}^{N} \alpha_j y_j  x_j)
\\
&= \frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j 
- \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j  + \sum_{i = 1}^{N} \alpha_i
\\
&= -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j + 
\sum_{i = 1}^{N} \alpha_i
\end{aligned}

进一步得到目标

\begin{aligned}
&\mathop{\max}_{w,b}[ -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j + \sum_{i = 1}^{N} \alpha_i] \\
&\text{s.t. } \alpha_i \ge 0, \text{且} \sum_{j = 1}^{N} \alpha_iy_i = 0, \forall i=1,2,\dots,N
\end{aligned}

KKT条件

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件：

\begin{aligned}
&\frac{\partial \mathcal{L}}{\partial w}=0,\frac{\partial \mathcal{L}}{\partial b}=0
\\&\alpha_k(1-y_k(w^Tx_k+b))=0\text{ (slackness complementary, 松弛互补条件)}\\
&\alpha_i\ge0\\
&1-y_i(w^Tx_i+b)\le 0
\end{aligned}

得出最优解参数为

w^* =\sum\limits_{i=1}^N\alpha_iy_ix_i \\

w^* 是训练集的线性组合， \alpha_i 其实只在支持向量上时才有值，其他地方是0。

对于参数 b 和( x_k 是支持向量)

\begin{aligned}

\exists k, 1-y_k(w^Tx_k+b) =0,
\text{s.t. }b^* 
=y_k-w^Tx_k 
=y_k-\sum\limits_{i=1}^N\lambda_iy_ix_i^Tx_k
\end{aligned}

发现其实 b^* 也是是训练集的线性组合。决策函数就出来了

f(x) = sign(w^* + b^*)

软间隔分类器 soft margin

soft: 允许一点点错误。保持泛化的能力，降低噪声对模型的影响。

Hard-margin 的 SVM 只对可分数据可解，如果不可分的情况，我们的基本想法是在损失函数中加入错误分类的可能性。错误分类的个数可以写成( \mathbb{I} 为指示函数)

loss =\sum\limits_{i=1}^N\mathbb{I}\{y_i(w^Tx_i+b)\lt1\}

这个样本点分类错误则输出0，正确则输出1，容忍一点错误。但这个函数不连续，可以将其改写为：

loss =\sum\limits_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}

求和符号中的式子又叫铰链函数 ( Hinge Function ) 。前面说的函数间隔 \hat{\gamma}_i = y_i(w^Tx_i+b) ，这个函数本质就是

H = \left \{
\begin{aligned}
&\hat{\gamma}_i , &\text{if } \hat{\gamma}_i < 1
\\
&0 , &\text{if } \hat{\gamma}_i \ge 1
\end{aligned}
\right.

我个人的理解是

某样本点 \hat{\gamma}_i 的意义  = \left\{
\begin{aligned}
  &\text{分类正确的置信度很高，}&\hat{\gamma}_i > 1 \\ 
 &\text{是支持向量，} &\hat{\gamma}_i = 1 \\
 &\text{噪声，} &0 < \hat{\gamma}_i < 1  \\
 &\text{分类错误的置信度，} &\hat{\gamma}_i < 0
\end{aligned}
\right.

将这个错误加入 Hard-margin SVM 中，于是：

\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}
\\
&\text{s.t. }y_i(w^Tx_i+b) \ge 1 ,i=1,2,\cdots,N
\end{aligned}

这个式子中，超参数 C 可以看作允许的错误水平，同时上式为了进一步消除 \max 符号，对数据集中的每一个观测，我们可以认为其大部分满足约束，但是其中部分违反约束，因此令 \xi_i=1-y_i(w^Tx_i+b) ，这部分约束变成 y_i(w^Tx+b)\ge1-\xi_i ， \xi_i 实际上是可以容忍错误的那部分间隔，进一步的化简：

\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum\limits_{i=1}^N\xi_i 
\\
&\text{s.t. }y_i(w^Tx_i+b)\ge 1- \xi_i, \xi_i \ge 0,i=1,2,\cdots,N
\end{aligned}

来源

Binary relevance for multi-label learning – Zhang, Li, Liu, Geng, 2018, [Frontiers of Computer Science]

传统的二元相关性方法

1、 二元相关性方法依赖概念的简洁。它是一个一阶方法，忽略了标签间的相关性，其计算复杂度与标签空间的大小呈线性关系。
2、 它是一种问题转换法。它可以将多标签问题转化为二元分类问题。
3、 它优化了宏平均（Macro-average）的多标签指标。
4、 它能轻易地适应缺失标签的训练集。

提升二元相关性方法的泛化能力的两个方法

1、开发标签间的相关关系。
2、研究标签内在属性，例如标签不平衡状态、标签间的相对重要性。

标签间相关关系开发

1、 假设随机标签相关的链结构，如分类器链算法。
2、 假设全序标签相关的堆栈结构，如堆栈式集成分类器算法。
3、 假设标签相关性剪枝的控制结构，LEAD算法。

链式结构

核心思想：分类器链是一种高阶算法，按照特定顺序排列分类器的顺序，将这一个分类器的结果 y^\ast 作为 x 的额外特征来训练，得到新的训练集。
一般的分类器链算法：
利用多标签训练集的m个训练数据\left(x,y_i\right)：

\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\}

按算法指定顺序\pi生成训练数据：

\mathcal{D}_{\pi\left(\mathcal{j}\right)}=\left\{\left(\left[\boldsymbol{x}^{i},y_{\pi\left(1\right)}^i,\ldots,y_{\pi\left(j-1\right)}^i\right],y_{\pi\left(j\right)}^i\right)\mid1\le i\le m\right\}

在 q 个分类中，按照特定顺序 \pi 训练分类器，对每个数据应用二元学习算法 \mathcal{B} ：

g_\pi\left(j\right):\mapsto\mathcal{B}\left(\mathcal{D}_\pi\left(j\right)\right)

例如，对于第 j\left(1\le j\le q\right) 个分类器，按照一定的顺序先由 \left(x,y_1\right) 训练出 y_1 的分类器，再利用\left(x,y_1,y_2\right) 训练 y_3 的分类器，以此类推，从\ \left(x,y_1,\ldots,y_n\right)得到最后的分类器。其中y_1,y_2,\ldots,y_q 的生成顺序\pi根据具体算法而定。g_{\pi\left(j\right)}同时决定了标签\lambda_j与其他标签的相关性。
输入一个未知向量x^\ast，按照顺序 \pi 应用分类器 g_j 算法将预测输出标签空间 \mathcal{Y} 内的 Y^\ast ，输出概率，最终得出所有的分类标签：

\eta_{\pi\left(1\right)}^{x^\ast}=sign\left[g_{\pi\left(1\right)}\left(x^\ast\right)\right]
\\
\eta_{\pi\left(j\right)}^{x^\ast}=sign\left[g_{\pi\left(j\right)}\left(\left[x^\ast,\eta_{\pi\left(1\right)}^{x^\ast},\ldots,\eta_{\pi\left(j-1\right)}^{x^\ast}\right]\right)\right]
\\
Y^\ast=\left\{\lambda_{\pi\left(j\right)}\mid\eta_{\pi\left(j\right)}^{x^\ast}=+1,1\le j\le q\right\}

还值得注意的是，先前分类器中发生的预测错误将沿着链结构传播到后续分类器，并且如果容易出错的分类标签碰巧放置在起始链接位置，则这些不良影响会变得更加明显。在训练阶段，我们用的是y真值，而在预测阶段，我们用的是分类器给出的值，纠正这种差异的办法是，统一都用分类器给出的值。从概率论的视角来说，分类器链通过条件概率预测结果：

p\left(y\mid x\right)=\prod_{j=1}^{q}{p\left(y_{\pi\left(j\right)}\mid x,y_{\pi\left(1\right)},\ldots,y_{\pi\left(j-1\right)}\right)}

堆栈结构

核心思想：堆叠式的分类器算法假设标签间皆存在相关关系，利用的是标签间的全序结构，集成所有基础分类器来得到标签关系。
堆叠式分类器算法：
利用训练集数据训练 j 个基础分类器 g_j，它是数据集在通过学习算法生成的映射：

\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\} \\
g_j:\mapsto\mathcal{B}\left(\mathcal{D}_{\left(\mathcal{j}\right)}\right)

利用训练集数据和基础分类器的结果 \mathcal{D}_j^M ，训练 j 个元分类器 \ g_j^M ：

\mathcal{D}_j^M=\left\{\left(\left[x^i,sign\left[g_2\left(x^i\right)\right],\ldots,sign\left[g_q\left(x^i\right)\right]\right],y_j^i\right)\mid1\le i\le m\right\}

利用 g_j^M 和 g_j 推导出结果标签集：

Y^\ast=\left\{\lambda_j\mid g_j^M\left(\tau^{x^\ast}\right)>0,1\le j\le q\right\}
\\
\text{where }\tau^{x^\ast}=\left[x^\ast,sign\left[g_1\left(x^\ast\right)\right],\ldots,sign\left[g_q\left(x^\ast\right)\right]\right]

评价：同样，与分类器链类似，训练阶段使用真值而预测阶段使用分类器预测值，会让输入空间造成差异。最好是统一训练和预测的y值。除了元分类器输出结果，还能汇总元分类器和基础分类器来输出预测结果。除了使用二元标签分配作为额外的堆叠功能外，还可以采用特定技术来生成量身定制的堆叠功能，如判别分析和规则学习。

贝叶斯网络

贝叶斯网络利用DAG表述条件概率模型。图中的节点代表随机变量，可以是可观察到的变量，或隐变量、未知参数等。认为有因果关系（或非条件独立）的变量或命题则用箭头来连接。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。总而言之，连接两个节点的箭头代表此两个随机变量是具有因果关系，或者非条件独立。假设节点E直接影响到节点H，即E→H，则用从E指向H的箭头建立结点E到结点H的有向弧(E,H)，权值(即连接强度)用条件概率P(H|E)来表示。把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。其主要用来描述随机变量之间的条件依赖，用圆圈表示随机变量(random variables)，用箭头表示条件依赖(conditional dependencies)。

对于任意的随机变量，其联合概率可由各自的局部条件概率分布相乘而得出：

p\left(y\mid x\right)=\prod_{j=1}^{q}{p\left(y_i\mid p a_j,x\right)}

恰好可以应用在开发标签间关系上。
导致图结构难以生成的原因：
1、 混合类型，x 是连续变量，标签 y 是离散变量。
2、 计算复杂度很高

LEAD算法

核心思想：估计特征的影响以简化贝叶斯网络的生成过程。
LEAD一般算法：
按照独立按每个标签训练各自的二元分类器 g_j 。
根据训练集 \mathcal{D}_\mathcal{j} 的每个 x 进行计算，对每个标签引入误差随机变量：

e_j=y_j-sign\left(g_j\left(x\right)\right)

使用现成的工具的贝叶斯学习算法，根据误差随机变量建立贝叶斯网络结构。

\mathcal{G}\gets\mathcal{L}\left(e_1,e_2,\ldots,e_q\right)

类似于之前两种结构的训练过程，按照网络结构得到每个标签的特定分类器组合，输入特征，训练二元模型：

\eta_{\pi^G\left(1\right)}^{x^\ast}=sign\left[g_{\pi^G\left(1\right)}^G\left(x^\ast\right)\right]
\\
\eta_{\pi^G\left(j\right)}^{x^\ast}=sign\left[g_{\pi^G\left(j\right)}^G\left(\left[x^\ast,\left\langle\eta_a^{x^\ast}\right\rangle_{y_a\in p a_nG_{\left(j\right)}}\right]\right)\right]
\\
g_j^\mathcal{G}:\mapsto\mathcal{B}\left(\mathcal{D}_\mathcal{j}^\mathcal{G}\right)

按照贝叶斯网络的图结构确定分类器排序，依次判断每个标签：

Y^\ast=\left\{\lambda_{\pi^G\left(j\right)}\mid\eta_{\pi^G\left(j\right)}^{x^\ast}=+1,1\le j\le q\right\}

标签间关系剪枝还有其他方法：
1、 基于树的贝叶斯网络，用作简化的DAG，通过修剪（最多）有一个父标签的标签来考虑二阶关系。
2、 通过为堆叠的元分类器，修剪基分类器的不相关输出，堆栈式结构的改造能满足受控的标签间相关关系开发。
3、带有易错预测的标签甚至可以从标签池中过滤掉，以进行相关关系开发。

标签内在属性开发的算法

关注训练集标签不平衡问题

标签空间中存在大量标签时，标签数量不平衡现象大量存在。不平衡指标为：

ImR_j=\frac{max\left(\left|\mathcal{D}_\mathcal{j}^+\right|,\left|\mathcal{D}_\mathcal{j}^-\right|\right)}{min\left(\left|\mathcal{D}_\mathcal{j}^+\right|,\left|\mathcal{D}_\mathcal{j}^-\right|\right)}

现有方法采用二元相关性算法作为学习过程的中间步骤，来解决标签不平衡问题，例如过采样、欠采样、阈值决策边界。然而它们忽略了利用标签间的相关性。

COCOA算法

交叉解耦聚集(cross-coupling aggregation)，高阶方法，利用标签相关性研究标签失衡问题。在训练阶段，成对标签耦合用以开发标签关系。在判别阶段，由类不平衡学习算法生成的聚集分类器，研究标签类不平衡。
一般算法描述：
对于每个标签j进行如下步骤：
按类不平衡的二元学习算法，训练常规的二元分类器 g_j^I 。

\mathcal{D}_\mathcal{j}=\{\left(x^i,y_j^i\right)\mid1\le i\le m\}
\\
g_j^I:\mapsto\mathcal{B}^I\left(\mathcal{D}_{\left(\mathcal{j}\right)}\right)

生成一个K标签随机子集 J_K\subset\mathcal{Y}\left\{\lambda_j\right\}

对于每个 \lambda_k\in J_K，每个成对标签，有三元训练集

\mathcal{D}^{\boldsymbol{tri}} = \{ \boldsymbol{x}^i ,  \psi^{\boldsymbol{tri}}(\boldsymbol{y}^i , \lambda_j, \lambda_k )) \mid  1 \le i \le m  \}
\\
\text{where }
\psi^{\boldsymbol{tri}}(\boldsymbol{y}^i , \lambda_j, \lambda_k ) = 
\left \{
\begin{aligned}
0, & \text{ if } y_j^i = -1 \text{ and } y_k^i = -1  \\
+1, & \text{ if } y_j^i = -1 \text{ and } y_k^i = +1  \\
+2, & \text{ if } y_j^i = +1 
\end{aligned}
\right .

\left(y_j^i,y_k^i\right)	+1, +1	+1, -1	-1, +1	-1, -1
	2	2	1	0

由此，训练类不平衡学习算法 g_{jk}^I:\gets\mathcal{M}^I\left(\mathcal{D}_{jk}^{tri}\right)
至此，训练结束，通过判别算法计算标签

Y^\ast=\left\{\lambda_j\mid f_j\left(x^\ast\right)>t_j,1\le j\le q\right\}
\\
\text{where }f_j\left(x^\ast\right)=g_j^I\left(x^\ast\right)+\sum_{\lambda_k\in J_K}{g_{jk}^I\left(x^\ast,+2\right)}

通过 K+1 个分类器判断是否是正类。阈值 t_j 可通过F度量判断和某些经验指标确定。
精确率是针对我们预测结果而言的，它表示的是预测为正的样本中有多少是真正的正样本。那么预测为正就有两种可能了，一种就是把正类预测为正类(TP)，另一种就是把负类预测为正类(FP)，也就是

P=\frac{TP}{TP+FP}

而召回率是针对我们原来的样本而言的，它表示的是样本中的正例有多少被预测正确了。那也有两种可能，一种是把原来的正类预测成正类(TP)，另一种就是把原来的正类预测为负类(FN)。

R=\frac{TP}{TP+FN}

在信息检索领域，精确率和召回率又被称为查准率和查全率，

查准率＝检索出的相关信息量 / 检索出的信息总量 \
查全率＝检索出的相关信息量 / 系统中的相关信息总量

F 度量为

F = \frac{2\times P\times R}{P+R}

关注标签相对重要性

以往的多标签方法都默认标签之间都有同等的重要性，然而，现实场景中相关性标签，重要性常常是不同的，而且不能从训练集中获得其信息。如下图，显示了一个多标签自然场景图像，其相关的标签重要性递减：天空 ? 水 ? 云 ? 建筑物 ? 行人。类似的情况也适用于其他类型的多标签对象，例如具有不同主题重要性的多类别文档，具有不同表达水平的多功能基因等。

也有一些利用辅助信息的算法，如每个标签的全序排序的定序尺度、相关标签的全排序、所有标签的重要性分布、对未标记实体查询标签的Oracle反馈。但在标准的多标签学习问题中，唯一可用的信息只有实体与标签的相关性。通过利用隐式的标签相对重要性，多标签学习的泛化能力可以进一步增强。

RELIAB算法

算法一般性描述：
第一阶段计算相对重要性 \mathcal{U}=\{\mu_{x_i}^{\lambda_i}|1\le i\le m,1\le j\le q\}
构建全连接图 G=\left(V,E\right) ，其中 V=\{x^i|1\le i\le m\}，为图构建相似度矩阵 W=\left[w_{ik}\right]_{m\times m}，其中i不等于k时，该标签与其他标签比较，通过高斯核函数计算相似

\forall_{i, k=1}^{m}: w_{i k}=\left\{\begin{array}{cl}
\exp \left(-\frac{\left\|x^{i}-x^{k}\right\|_{2}^{2}}{2 \sigma^{2}}\right), & \text { if } i \neq k \\
0, & \text { if } i=k
\end{array}\right.

得出标签传播矩阵

P=D^{-\frac{1}{2}}WD^{-\frac{1}{2}} \\
\text{ where  }D=diag\left[d_1,d_2,\ldots,d_m\right]\mathrm{\ with\ }d_i=\sum_{k=1}^{m}w_{ik}

初始化标签重要性矩阵 R=\left[r_{ij}\right]_{m\times q}

R^{\left(0\right)}=\Phi=\left[\phi_{ij}\right]_{m\times q}

迭代传播标签重要性矩阵

R^{\left(t\right)}=\alpha PR^{\left(t-1\right)}+\left(1-\alpha\right)\Phi

最终R收敛于 R^\ast，得出标签相对重要性

\forall1\le i\le m,\forall1\le j\le q:\mu_{x_i}^{\lambda_j}=\frac{r_{ij}^\ast}{\sum_{j=1}^{q}r_{ij}^\ast}

第二阶段，选择最大熵模型参数化多标签预测变量

f_j\left(x\right)=\frac{1}{Z\left(x\right)}\exp{\left(\theta_j^\top x\right)}\left(1\le j\le q\right)
\\
\mathrm{\ where\ }Z\left(x\right)=\sum_{j=1}^{q}exp\left(\theta_j^\top x\right)

最大化目标函数以得出参数

V\left(\Theta,\mathcal{U},\mathcal{D}\right)=V_{dis}\left(\Theta,\mathcal{U}\right)+\beta\cdot V_{emp}\left(\Theta,\mathcal{D}\right)

第一项的 V_{dis}\left(\Theta,\mathcal{U}\right) 评估预测模型的效果与相对标签重要性信息 \mathcal{U} 的拟合程度（如通过Kullback-Leibler散度），第二项评估预测模型 \Theta 在训练集 \mathcal{D}上的分类能力（如经验排序损失）。\beta 是平衡目标函数这两项的正则化参数。
最后，对任意新样本 x^\ast 输出结果标签 Y^\ast

Y^\ast=\{\lambda_j|f_j\left(x^\ast\right)>t\left(x^\ast\right),1\le j\le q\}