文章目录
- 引入
- 1 定义及评价指标
-
- 1.1 定义
-
- 1.1.1 学习框架
引入
论文地址：http://palm.seu.edu.cn/zhangml/files/TKDE’13.pdf
主要内容：
1）多标签定义及评价指标；
2）具体分析八种代表算法；
3）总结部分学习设置。
1 定义及评价指标
1.1 定义
符号表:
| 符号 | 含义 |
|---|---|
| X \mathcal{X} X | 实例空间 R d \mathbb{R}^d Rd (或者 Z d \mathbb{Z}^d Zd) |
| Y \mathcal{Y} Y | 标签空间 { y 1 , y 2 , ⋯ , y q } \{ y_1, y_2, \cdots, y_q \} { y1,y2,⋯,yq} |
| x \boldsymbol{x} x | 特征向量 ( x 1 , x 2 , ⋯ , x d ) ⊤ ( x ∈ X ) (x_1, x_2, \cdots, x_d)^\top (\boldsymbol{x} \in \mathcal{X}) (x1,x2,⋯,xd)⊤(x∈X) |
| Y Y Y | x \boldsymbol{x} x标签集 ( Y ∈ Y Y \in \mathcal{Y} Y∈Y) |
| Y ˉ \bar{Y} Yˉ | Y Y Y在 Y \mathcal{Y} Y的补集 |
| D \mathcal{D} D | 多标签训练集 { ( x i , Y i ) ∣ 1 < i ≤ m } \{ (\boldsymbol{x}_i, Y_i) \mid1 < i \leq m\} { (xi,Yi)∣1<i≤m} |
| S \mathcal{S} S | 多标签测试集 { ( x i , Y i ) ∣ 1 < i ≤ p } \{ (\boldsymbol{x}_i, Y_i) \mid1 < i \leq p\} { (xi,Yi)∣1<i≤p} |
| h ( ⋅ ) h (\cdot) h(⋅) | 多标签分类器 h : X → 2 Y h: \mathcal{X} \rightarrow 2^\mathcal{Y} h:X→2Y， h ( x ) h (\boldsymbol{x}) h(x)返回 x \boldsymbol{x} x标签的可能集合 |
| f ( ⋅ , ⋅ ) f (\cdot, \cdot) f(⋅,⋅) | 实值函数 f : X × Y → R f: \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R} f:X×Y→R， f ( x , y ) f (\boldsymbol{x}, y) f(x,y)返回 x \boldsymbol{x} x正确标签的置信度 |
| r a n k f ( ⋅ , ⋅ ) rank_f (\cdot, \cdot) rankf(⋅,⋅) | r a n k f ( x , y ) rank_f (\boldsymbol{x}, y) rankf(x,y)返回基于降序 f ( x , ⋅ ) f (\boldsymbol{x}, \cdot) f(x,⋅)的 y y y在 Y \mathcal{Y} Y上的秩 |
| t ( ⋅ ) t (\cdot) t(⋅) | 阈值函数 t : X → R t : \mathcal{X} \rightarrow \mathbb{R} t:X→R，其中 h ( x ) = { y ∣ f ( x , y ) > t ( x ) , y ∈ Y } h (\boldsymbol{x}) = \{ y \mid f (\boldsymbol{x}, y) > t (\boldsymbol{x}), y \in \mathcal{Y} \} h(x)={ y∣f(x,y)>t(x),y∈Y} |
| ∣ ⋅ ∣ \mid \cdot \mid ∣⋅∣ | A \mathcal{A} A返回集合 A \mathcal{A} A的候选 |
| ⋅ \llbracket \cdot\rrbracket [[⋅]] | 如果predicate π \pi π成立，返回 1 1 1否则 0 0 0 |
| ϕ ( ⋅ , ⋅ ) \phi (\cdot, \cdot) ϕ(⋅,⋅) | 如果 y ∈ Y y \in Y y∈Y， ϕ ( Y , y ) \phi (Y, y) ϕ(Y,y)返回 1 1 1；否则 − 1 -1 −1 |
| D j \mathcal{D}_j Dj | 二类训练集 { ( x i , ϕ ( Y i , y j ) ) ∣ 1 ≤ i ≤ m } \{ (\boldsymbol{x}_i, \phi (Y_i, y_j)) \mid 1 \leq i \leq m \} { (xi,ϕ(Yi,yj))∣1≤i≤m} |
| ψ ( ⋅ , ⋅ , ⋅ ) \psi (\cdot, \cdot, \cdot) ψ(⋅,⋅,⋅) | 如果 y j ∈ Y y_j \in Y yj∈Y且 y k ∉ Y y_k \notin Y yk∈/Y， ψ ( Y , y j , y k ) \psi (Y, y_j, y_k) ψ(Y,yj,yk)返回 1 1 1； y j ∉ Y y_j \notin Y yj∈/Y且 y k ∈ Y y_k \in Y yk∈Y返回 − 1 -1 −1 |
| D j k D_{jk} Djk | 二类训练集 { ( x , ψ ( Y i , y j , y k ) ) ∣ ϕ ( Y i , y j ) ≠ ϕ ( Y i , y k ) , 1 ≤ i ≤ m } \{ (\boldsymbol{x}, \psi (Y_i, y_j, y_k)) \mid \phi (Y_i, y_j) \neq \phi (Y_i, y_k), 1 \leq i \leq m \} { (x,ψ(Yi,yj,yk))∣ϕ(Yi,yj)=ϕ(Yi,yk),1≤i≤m} |
| σ Y ( ⋅ ) \sigma_{\mathcal{Y}} (\cdot) σY(⋅) | 单射函数 σ Y : 2 Y → N \sigma_\mathcal{Y}: 2^\mathcal{Y} \rightarrow \mathbb{N} σY:2Y→N ( σ Y − 1 \sigma_\mathcal{Y}^{-1} σY−1是相应的逆函数) |
| D Y † \mathcal{D}_{\mathcal{Y}}^{\dagger} DY† | 多类单标签训练集 { ( x i ) , σ Y ( Y i ) ∣ 1 ≤ i ≤ m } \{ (\boldsymbol{x}_i), \sigma_\mathcal{Y} (Y_i) \mid 1 \leq i \leq m \} { (xi),σY(Yi)∣1≤i≤m} |
| B \mathcal{B} B | 二类学习算法 [ F B ( m , d ) \mathcal{F}_\mathcal{B} (m ,d) FB(m,d)用于训练； F B ′ ( d ) \mathcal{F}_\mathcal{B}' (d) FB′(d)用于测试] |
| M \mathcal{M} M | 多类学习算法 [ F M ( m , d , q ) \mathcal{F}_\mathcal{M} (m ,d, q) FM(m,d,q)用于训练； F M ′ ( d , q ) \mathcal{F}_\mathcal{M}' (d, q) FM′(d,q)用于测试] |
1.1.1 学习框架
令 X \mathcal{X} X表示实例空间， Y \mathcal{Y} Y表示标签空间。多标签的任务为从训练集 D \mathcal{D} D习得一个映射 h : X → 2 Y h: \mathcal{X} \rightarrow 2^\mathcal{Y} h:X→2Y。对于任意未知标签的实例 x \boldsymbol{x} x， h ( ⋅ ) h (\cdot) h(⋅)能够为其预测标签 h ( x ) ⊆ Y h (\boldsymbol{x}) \subseteq \mathcal{Y} h(x)⊆Y。
为了描述多标签数据集的特征，可以使用以下几个指标：
1）标签基数 (label cardinality)：每个样本平均标签数，即
L C a r d ( D ) = 1 m ∑ i = 1 m = ∣ Y i ∣ 。 LCard (\mathcal{D}) = \frac{1}{m} \sum_{i = 1}^m = | Y_i |。 LCard(D)=m1i=1∑m=∣Yi∣。 2）标签密度 (label density)：通过标签空间中可能的标签数量来标准化标签基数，即
L D i v ( D ) = 1 Y ⋅ L C a r d ( D ) 。 LDiv (\mathcal{D}) = \frac{1}{\mathcal{Y}} \cdot LCard (\mathcal{D})。 LDiv(D)=Y1⋅LCard(D)。 3）标签多样性 (label diversity)：数据集中不同标签集的数量，即
L D i v ( D ) = ∣ { Y ∣ ∃ x : ( x , Y ) ∈ D } ∣ . LDiv (\mathcal{D}) = | \{ Y | \exists \boldsymbol{x}: (\boldsymbol{x}, Y) \in \mathcal{D} \} |. LDiv(D)=∣{ Y∣∃x:(x,Y)∈D}∣.标签多样性也能被标准化为：
P L D i v ( D ) = 1 D ⋅ L D i v ( D ) . PLDiv (\mathcal{D}) = \frac{1}{\mathcal{D}} \cdot LDiv (\mathcal{D}). PLDiv(D)=D1⋅LDiv(D). 普适情况下，多标签模型返回一个实值函数 f : X × Y → R f: \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R} f:X×Y→R，其中 f ( x , y ) f (\boldsymbol{x}, y) f(x,y)称为 y y y是 x \boldsymbol{x} x可能标签的置信度 (confidence)。特别的，给定一个多标签样本 ( x , Y ) (\boldsymbol{x}, Y) (x,Y)， f ( ⋅ , ⋅ ) f (\cdot, \cdot) f(⋅,⋅)对于相关标签 y ′ ∈ Y y' \in Y y′∈Y应该输出更大值；不相关标签 y ′ ′ ∉ Y y'' \notin Y y′′∈/Y则反之，即：
f ( x , y ′ ) > f ( x , y ′ ′ ) . f (\boldsymbol{x}, y') > f (\boldsymbol{x}, y''). f(x,y′)>f(x,y′′).
