先附上原文位址
這篇文章提出一個機器學習方法在資訊不充足的情況下做出決策
所謂資訊不足指的是，我們所收集到的資料是未經排序的，但是我們要給的決策建議是卻是排序的。舉例而言，收集到的資料只有某些人的某些特質和他們各自看了哪些電影(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}$的長度
作為評估排序表現的依據
