文章目錄
- 引入
- 1 定義及評價指標
- 1.1 定義
- 1.1.1 學習框架
- 1.1.2 關鍵挑戰
- 1.1.3 閾值校驗
引入
??論文地址：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)=m1?i=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′′).??根據實值函式 f ( ? , ? ) f (\cdot, \cdot) f(?,?)可以得到多標簽分類器 h ( ? ) h (\cdot) h(?)：
h ( x ) = { y ∣ f ( x , y ) > t ( x ) , y ∈ Y } , h (\boldsymbol{x}) = \{ y | f (\boldsymbol{x}, y) > t (\boldsymbol{x}), y \in \mathcal{Y} \}, h(x)={y∣f(x,y)>t(x),y∈Y},其中 t : X → R t: \mathcal{X} \rightarrow \mathbb{R} t:X→R模擬一個閾值函式，以將標簽空間分為相關標簽集和不相關標簽集，
1.1.2 關鍵挑戰
??多標簽學習的關鍵挑戰在于巨大的輸出空間，即標簽集的數量會隨類標簽呈指數增長，例如，對于一個
20
20
20類的標簽空間，標簽集的可能數量將為
2
20
2^{20}
220，對此，必須利用標簽之間的相關性來進行學習，基于相關性順序 (order of correlations)，現有策略分為以下三類：
??1）First-order strategy：忽略其他標簽，進行label-by-label的處理，例如將多標簽問題分解為一系列獨立的二分類問題，該策略的突出優點為簡單高效，但不能保證獲取最優結果，
??2）Second-order strategy：考慮標簽對的相關性，例如相關標簽與不相關標簽，或者任意標簽對，
??3）High-order strategy：考慮標簽之間更高級別的關系，例如將其他標簽的影響強加給每一個標簽，
1.1.3 閾值校驗
??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/202596.html
標籤：其他
下一篇：微信公眾號采集方案