极限多标签学习之-PLT
《Probabilistic label trees for extreme multi-label classification》
主要贡献：提出了PLT.
文章目录
- 问题定义
- PLT model
- 一致性和遗憾界分析
- 在线PLT
问题定义
符号系统：
| Key notations | Meaning |
|---|---|
| X \mathcal{X} X | instance space |
| L = { 1 , … , m } \mathcal{L} = \{1, \dots, m\} L={1,…,m} | Label set |
| Y = { 0 , 1 } m \mathcal{Y} = \{0, 1\}^m Y={0,1}m | Label space |
| x ∈ X \mathbf{x} \in \mathcal{X} x∈X | an instance |
| y ∈ Y \mathbf{y} \in \mathcal{Y} y∈Y | a label corresponding to x \mathbf{x} x |
| L x ⊆ L \mathcal{L}_\mathbf{x} \subseteq \mathcal{L} Lx⊆L | relevant(positive) labels, otherwise irrelevant(positive) labels. y j = 1 ⇔ j ∈ L x y_j = 1 \Leftrightarrow j \in \mathcal{L}_\mathbf{x} yj=1⇔j∈Lx |
| R ( ⋅ ) R(\cdot) R(⋅) | The expected loss, or risk |
| P ( x , y ) \mathbf{P}(\mathbf{x},\mathbf{y}) P(x,y) | 观测 ( x , y ) (\mathbf{x},\mathbf{y}) (x,y)的概率分布, 假定每个观测独立采样 |
| ℓ ( y , y ^ ) \ell(\mathbf{y},\hat{\mathbf{y}}) ℓ(y,y^) | Loss |
| T T T | The tree |
| L T L_T LT | leaf set; l j ∈ L T l_j \in L_T lj∈LT对应 j ∈ L j \in \mathcal{L} j∈L |
| V T V_T VT | the set of all nodes |
| L v L_v Lv | 内节点 v v v的所有叶子 |
| L v ⊆ L \mathcal{L}_v \subseteq \mathcal{L} Lv⊆L | 内节点 v v v对应的所有叶子的标签集合 |
| ↑ ( v ) , ↓ ( v ) \uparrow(v), \downarrow(v) ↑(v),↓(v) | 父节点，直接孩子节点集合 |
| Path ( v ) \text{Path}(v) Path(v) | 从 v v v到根节点的路径 |
| len v \text{len}_v lenv | 路径长度 |
| deg v \text{deg}_v degv | 节点 v v v的度 |
本文作者的问题定义写的很好，读起来很通畅。先前也看了一些XC的文章，都没有将问题定义描述的很好（或者压根没有问题定义）。
极限多标签分类问题可定义为（类似于多标签分类问题的定义）：寻找一个分类器
h
(
x
)
=
(
h
1
(
x
)
,
…
,
h
m
(
x
)
)
∈
H
m
:
X
↦
R
m
\mathbf{h}(\mathbf{x}) = (h_1(\mathbf{x}),\dots,h_m(\mathbf{x})) \in \mathcal{H}^m:\mathcal{X}\mapsto \mathbb{R}^m
h(x)=(h1(x),…,hm(x))∈Hm:X↦Rm，使得期望损失极小：
R
ℓ
(
h
)
=
E
(
x
,
y
)
∼
P
(
x
,
y
)
(
ℓ
(
y
,
h
(
x
)
)
)
R_\ell(\mathbf{h}) = \mathbb{E}_{(\mathbf{x}, \mathbf{y}) \sim \mathbf{P}(\mathbf{x},\mathbf{y})}(\ell(\mathbf{y},\mathbf{h}(\mathbf{x})))
Rℓ(h)=E(x,y)∼P(x,y)(ℓ(y,h(x)))
一般地，
m
≥
1
0
5
,
∣
L
x
∣
≪
m
m\geq 10^5,|\mathcal{L}_\mathbf{x}| \ll m
m≥105,∣Lx∣≪m。那么在损失
ℓ
\ell
ℓ上的最优分类器为：
h
ℓ
∗
=
arg min
h
R
ℓ
(
h
)
\mathbf{h}_\ell^* = \argmin_{\mathbf{h}} R_\ell(\mathbf{h})
hℓ∗=hargminRℓ(h)
文中定义了一个分类器
h
\mathbf{h}
h针对损失
ℓ
\ell
ℓ的遗憾(regret)：
reg
ℓ
(
h
)
=
R
ℓ
(
h
)
−
R
ℓ
(
h
ℓ
∗
)
=
R
ℓ
(
h
)
−
R
ℓ
∗
\text{reg}_\ell(\mathbf{h}) = R_\ell(\mathbf{h}) - R_\ell(\mathbf{h}_\ell^*) = R_\ell(\mathbf{h}) - R_\ell^*
regℓ(h)=Rℓ(h)−Rℓ(hℓ∗)=Rℓ(h)−Rℓ∗
当然它越小越好。
令
η
j
=
P
(
y
j
=
1
∣
x
)
,
j
∈
L
\eta_j = P(y_j=1|\mathbf{x}), j\in \mathcal{L}
ηj=P(yj=1∣x),j∈L，希望
L
1
L_1
L1估计误差最小，其中
η
^
j
\hat{\eta}_j
η^j为
η
j
\eta_j
ηj的估计。
∣
η
j
−
η
^
j
∣
|\eta_j - \hat{\eta}_j|
∣ηj−η^j∣
令
ℓ
log
\ell_\text{log}
ℓlog为交叉熵损失，其在样本
x
\mathbf{x}
x上的条件风险（也就是期望损失）为：
E
y
ℓ
log
(
y
,
h
(
x
)
)
=
∑
j
=
1
m
R
log
(
h
j
(
x
)
∣
x
)
\mathbb{E}_\mathbf{y}\ell_{\text{log}}(\mathbf{y},\mathbf{h}(\mathbf{x})) = \sum_{j=1}^m R_\text{log}(h_j(\mathbf{x})|\mathbf{x})
Eyℓlog(y,h(x))=j=1∑mRlog(hj(x)∣x)
那么最优预测为
h
j
∗
(
x
)
=
arg min
h
R
log
(
h
j
(
x
)
∣
x
)
=
η
j
(
x
)
h_j^*(\mathbf{x}) = \argmin_\mathbf{h}R_\text{log}(h_j(\mathbf{x})|\mathbf{x}) = \eta_j(\mathbf{x})
hj∗(x)=hargminRlog(hj(x)∣x)=ηj(x)
当然，交叉熵损失函数实际上只对应一般的（文章中用了一个似乎比较地道的词：vanilla）1-vs-all方法。
而更加流行的评价指标就有
P
@
k
,
n
D
C
G
@
k
,
P
S
P
@
k
P@k,nDCG@k,PSP@k
P@k,nDCG@k,PSP@k等，也就是人们通常只关心top-k。
PLT model
PLT将原问题以一个树的形式分解为若干二元估计问题。
未完待续.