[機器學習] Paper digest(1) On Multilabel Classification and Ranking with Bandit Feedback

這篇是在Journal of machine learning research上看到的
先附上原文位址

這篇文章提出一個機器學習方法在資訊不充足的情況下做出決策

所謂資訊不足指的是，我們所收集到的資料是未經排序的，但是我們要給的決策建議是卻是排序的。舉例而言，收集到的資料只有某些人的某些特質和他們各自看了哪些電影(partial feedback)，卻不知道這些人對這些電影的喜好程度，我們要如何給出一個排序過的推薦清單?

Loss function for partial information

這篇文章的作者發展的loss function：

$l_{a,c} \big(Y_{t}, \widehat{Y_{t}} \big) =a |Y_{t} \backslash \widehat{Y_{t}}|+\big(1-a\big) \sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big) $

其中$Y_{t}$是收集到的資料，$\widehat{Y_{t}}$是建議的決策，因此$Y_{t}$是沒有排序的，而$\widehat{Y_{t}}$是有排序的

$|Y_{t}, \widehat{Y_{t}}|$是指有多少$Y_{t}$裡的element沒有出現在$\widehat{Y_{t}}$裡面，概念上有點像是Hamming loss function；而$ \sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big)$則是考量了排序，$\widehat{Y_{t}}$中，沒有出現在$Y_{t}$的元素要是排得越前面，計分就越重

舉例來說，如果

$Y_{t}=\left \{ 1,3,8 \right \}$

$\widehat{Y_{t}} = \big(4,3,6\big)$

則

$|Y_{t}, \widehat{Y_{t}}| = 2$ ($Y_{t}$中的$1$, $3$不屬於$\widehat{Y_{t}}$)

$\sum_{i \in\widehat{Y_{t}} \setminus Y_{t}} c \big(j_{i}, |\widehat{Y_{t}}| \big) = 3/3 + 1/3$  ($4$ 和 $6$的權重分別為$3/3$和$1/3$)

Multilabel classification

利用線性模型

$P_{t}(y_{1,t}, y_{2,t}, ...y_{k,t})=P_{t}(y_{1,t}, y_{2,t}, ...y_{k,t}|x_{t})$

$P_{t}(y_{i,t}=1) = \frac{g(-u_{i}^{T})}{g(u_{i}^{T}) + g(-u_{i}^{T})}$

最佳化上述的loss function找最好的決策，上述的loss function也可以寫成

$a \sum_{i=1}^{K}y_{i,t}+\big(1-a\big) \sum_{i \in\widehat{Y_{t}}}\big( c (j_{i}, |\widehat{Y_{t}}| ) - \big(\frac{a}{1-a} + c (j_{i}, |\widehat{Y_{t}}| ) \big)y_{i,t}\big)$

由於$\sum_{i=1}^{K}y_{i,t}$和$\widehat{Y_{t}}$基本上是無關的，所以在計算中只要最佳化

$E\left [l_{a,c} \big(Y_{t}, \widehat{Y_{t}} \big)   \right ]=\big(1-a\big) \sum_{i \in\widehat{Y_{t}}}\big( c (j_{i}, |\widehat{Y_{t}}| ) - \big(\frac{a}{1-a} + c (j_{i}, |\widehat{Y_{t}}| ) \big)p_{i,t}\big)$

就可以了

Others

作者也提出了另一個loss function：

$l_{p-rank, t}(Y, f)=\sum_{i,j\in \widehat{Y}_{t}:y_{i} <  y_{j}}\big(\left \{f_{i}(x_{t} ) < f_{j}(x_{t} )  \right \} + \frac{1}{2}\left \{ f_{i}(x_{t} ) = f_{j}(x_{t} ) \right \} \big)+ S_{t}|Y_{t}\backslash \widehat{Y}_{t}|$

$f$是ranking function而$ \left \{... \right \}$是indicator function，$S_{t}$則是$\widehat{Y}_{t}$的長度

作為評估排序表現的依據