[機器學習] Paper digest (3) Computational rationality: A converging paradigm for intelligence in brains, minds, and machines

原文連結在這裡，一篇登在Science上的review。好久沒寫blog，發現中文整個退化到不行，連帶我原本就不好的英文，真的要變文盲了。

先來個風景照(芬蘭・坦佩雷)



這篇回顧了computational rationality在人工智慧，認知科學及神經科學上的發展。

先稍微整理一下所謂computational rationality：

首先，最終的desicion必須要有最大的expected utility，這樣的概念首先由von Neumann等人[1]提出，即所謂的MEU(maximize expected utility) principle。至於為什麼是expected utility呢？原因是因為我們所身處的世界充滿了不確定性(uncertainty)，也就是凡事皆機率的意思，因此需引入期望值(expected value)的概念。

通常現實世界所處理的問題都頗複雜或是大尺度的(large scale)，因此在計算expected utility時，就經常需要動用逼近(appriximation)等計算技巧。

而appriximation本身也是決策的一環，因為計算需花上可觀的時間及資源，而這也是computational rationality的核心。在最大化expected utility的同時也要將計算所可投注有限資源及時間納入考慮。

至於computational rationality的模型則是建立於：

1. Infernece under uncertainty.

2. The feasibility and implications of actions.

3. Bounded computation power.

4. Multilevel, or multireasoning.


人工智慧

IBM Watson參加電視益智節目時，基本上Watson的計算時間(時間內要作答)和計算能力是被限制的，因此Watson基本上並沒有辦法『想』或是『窮舉』出所謂『完美無誤』的答案，而是要在『有限的時間及資源』下『猜』出『近乎完美』或『正確機率較高』的答案。

當然AI領域還有其他例子，像是Google自動駕駛汽車或是，Microsoft的個人秘書。


認知科學

心理學家發現，人類並非所謂「直覺的統計學家」(intuitive statisticians)。很多時候，人類的決策和所謂的「最佳決策」往往天差地遠。

Computational rationality可以提供一個架構來解釋這種現象。當腦在缺乏足夠資源的情況下被迫要做出決定時，所謂充滿缺陷的決策就會出現，但這些看似非理性的決策很有可能是考量了當下的計算資源所做出最理性的決策(哇勒好玄)。

文中提到抽樣貝氏推論(approximating Bayesian inference by sampling)，可以作為一個例子。基本上，所抽的樣本越多，所得到關於後驗機率分配(posterior distrubution)的資訊就越正確，但在時間及計算能力的限制下，往往只能得到一小部分的樣本，因此讓決策產生偏誤，計算生物學界就有學者此利用抽樣演算法作為模擬神經迴路的行為[2](看到嚇了一跳，有一種這樣也可以的感覺)。

神經科學

Computational rationality可以解釋分別屬於腦中不同的核區(cortex)的兩個系統：model-based system和model-free system的分工。

一般認為，model-based system較依賴經驗，需要較長時間(速度較慢)，卻比model-free system來得有彈性。在剛開始的學習階段，因為model-free system所做出的決策往往較不精準，model-based system通常有較好的效果而被採用。但經過一定時間的學習，model-free system的決策也可以優化到一定程度，這時model-based system反而會被放棄採用。

然而，學界也證實了大腦再選取兩者時，計算的消耗也被考慮在內[3][4]。


未來發展

文末，作者提到computational rationality是一個很有潛力的架構，並且應可以應用在更多不同的領域。然而更進一步的理論架構，以及更多的證實，或甚至是辯論都是學界可以繼續努力的方向。

[1] Von Neumann, J., & Morgenstern, O. (2007). Theory of games and economic behavior. Princeton university press.

[2] Buesing, L., Bill, J., Nessler, B., & Maass, W. (2011). Neural dynamics as sampling: a model for stochastic computation in recurrent networks of spiking neurons. PLoS Comput Biol, 7(11), e1002211.

[3] Daw, N. D., Gershman, S. J., Seymour, B., Dayan, P., & Dolan, R. J. (2011). Model-based influences on humans' choices and striatal prediction errors.Neuron, 69(6), 1204-1215.

[4] Keramati, M., Dezfouli, A., & Piray, P. (2011). Speed/accuracy trade-off between the habitual and the goal-directed processes. PLoS Comput Biol, 7(5), e1002055.

[貝氏] Paper digest(2) Slice sampling

最近啃了大師級學者Neal發表在Annals of Statistics上的這篇原著，十多年前的東西了。殿堂級的期刊果然很難讓人親近啊，有夠多頁，光是讀完都很很令人吐血。

有別於Gibbs sampling和MH sampling, slice sampling屬於Auxiliary sampling的範疇，除了抽出posterior distribution的樣本,更額外抽出另一個輔助性的,domain不一樣的樣本，歐好像有點玄。

總之先來看抽樣步驟:
1)選擇一個 starting point $x_{0}$ 並注意$f(x_{0})$ 必須大於$0$ ，並產生一個 $Uniform\ distribution\ U(0,\ f(x_{0}))$，也就是圖上的綠線

2)由 $U(0,\ f(x_{0}))$ 抽出一個 auxiliary variable $y_{0}$並產生一集合 $X^{*} = \{x:\ f(x)\geq y\}$，也就是圖上的紅色實線。這個動作叫做切割，也就是slice

3)由上一步驟產生的集合 $X^{*}$ 中，均勻(uniformly)抽出下一個 $x_{1}$ ，也就是紅點對用回x軸的位置並回到步驟二

換句話說，擁有越高posterior density的樣本，在每次切割(slice)的時候就越有機會被抽到，如此一來抽樣的結果就會收斂到Posterior distribution

[無母] Kernel Density Estimation

很久以前就看過這個方法，但都沒有仔細研究過。

有許多方法可以用來估計機率分配，以前課本上教的就是先假設一個機率分配(常常是Normal)，然後用動差法(moment-method)或者是最大概似估計(most likelihood)把參數找到後帶入。

無母數的做法就比較不一樣，在操作的時候避免假設一個太硬性的框架，以期發現更多數據底層的結構，KDE (Kernel Density Estimation)就是其中之一。話說回來，其實Histogram就是一種無母數的機率分配估計方法，像是下圖：

其實就是在計算

$p_{x}=\frac{\#of \ x_{i}\ is\ in\ the\ same\ bin\ with x}{bin\ width}$

所使用的參數就是bin的寬度和起始值(如上圖就是0)。

KDE也是類似的概念，要回答的問題是，當某個$x$並未被觀察到的時候，究竟背後的機率是多少？KDE回答問題的方式，就是去看$x$相進的點出現的情形，如果出現的多，表示其實$x$出現的機率很高，只是剛好by chance沒有被觀察到而已，反之則$x$本身出現的機率就是低的。

所以，當$x$出現機率的估計值就是

$p(x)=\frac{1}{nh}\sum_{i}kernel\left (\frac{x-x_{i}}{h}  \right )$

$h$是所謂的帶寬，$kernel$一般而言是以零為中心對稱的函數，並且所有值域的積分必須是$1$，像是Gaussian function

$k(u)=\frac{1}{\sqrt{2\pi}}\exp(\frac{u^{2}}{2})$

以下是我用不同$h$就產生上圖(Hitogram)的資料做的擬和

可以看出$h$的選擇很重要，太大的帶寬會導致under-fitting，太小的則導致over-fitting。帶寬的選擇又是另外一個很大的題目了。

[貝氏] 煩死人的 Variational Bayes 初探

先說，搞懂這個東西的過程令人崩潰的程度大概是這樣

羽生結弦，日本天才花式滑冰選手
圖片來源http://abcnews.go.com/Sports/photos/tough-straight-face-midair-22463006/image-22525718

貝氏統計推論中，有些Posterior實在太複雜太難算，用sampling (如MCMC)抽一大堆貌似合理的樣本來進行參數推論是經常使用的替代方式。然而sampling也有既存的問題，比如說常常讓運算速度不夠快，或是完全來自隨機以致收斂性等表現難以掌握等等。總之，學界開始尋找其他逼近(approximation)的方法在某些場合下取代MCMC。

Variational Bayes算是最紅的，許多貝氏建模的文章都會提供相對應的演算細節。

大致上的概念是這樣的，我們感興趣的東西是$p\left ( \theta \right |x)$，並且

$p\left ( \theta \right |x) \propto p\left ( \theta \right )p\left ( x |\theta \right)$

找一個替代品$q\left(\theta\right)$，並且讓這個替代品和posterior很像很像，換句話說就是努力把

$KL\left [ q\left(\theta\right) , p\left( \theta \right | x)\right]$

變得很小很小(沒錯，Kullback-leibler divergence這個小壞壞又出現了)

然後，因為我們有好多個parameter要推論，mean field assumption會是一個把情況變得簡單的假設，也就是所有的參數都是獨立的。也就是

$q\left(\theta \right )=\prod_iq\left(\theta_i \right )$

把這個該變小的Kullback-leibler divergence寫開

$KL \left[q \left( \theta \right),p \left( \theta \right|x) \right] =\int q \left( \theta \right) \log \frac{q\left( \theta \right)}{p \left( \theta|x \right)}d\theta$

$=\int q \left( \theta \right) \log \frac{q\left( \theta \right)p \left(x \right)}{p \left( \theta,x \right)} d\theta$

$=\int q \left( \theta \right) \log \frac{q \left( \theta \right)}{p \left( \theta,x \right)} d \theta- \int q \left( \theta \right) \log p \left(x\right) d\theta$

$=\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta-\log p\left(x\right)$

由於對$\log p\left(x\right)$已經使不上力(和$\theta$無關)，所以接下來專心解決$\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta$，並解我們知道$\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta$和$KL\left [ q\left(\theta\right) , p\left( \theta \right | x)\right]$成正比，所以要盡量把他變小

接下來引入mean field assumption

$\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta =\int \prod_i q\left(\theta_i \right) \log \frac{\prod_i q\left(\theta_i \right)}{p\left(\theta,x\right)} d\theta$

$=\int \prod_i q\left(\theta_i \right) \left( \sum_i \log q\left(\theta_i \right) - \log p\left(\theta, x \right ) \right)$

$=\int q\left(\theta_j \right) \prod_{i\neq j} q\left(\theta_i \right) \left( \sum_i \log q\left(\theta_i \right) - \log p\left(\theta, x \right ) \right) d\theta$

$=\int q\left(\theta_j \right) \prod_{i\neq j} q\left(\theta_i \right) \left( \log q\left(\theta_j \right) - \log p\left(\theta, x \right ) \right) d\theta$ $- \int q\left(\theta_j \right) \prod_{i\neq j} q\left(\theta_i \right) \left( \sum_{i\neq j} \log q\left(\theta_i \right) \right) d\theta$

$= \int q\left(\theta_j \right) \left( \log q\left(\theta_j \right) - \int \prod_{i\neq j} q\left(\theta_i \right) \log p\left(\theta, x \right ) d\theta_{i\neq j} \right ) d\theta_j$$+c$

$= \int q\left(\theta_j \right) \left( \log q\left(\theta_j \right) - E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right) d\theta_j +c$

$= \int q\left(\theta_j \right) \log \frac{\log q\left(\theta_j \right)}{\exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right )} d\theta_j +c$

$=KL\left[ q\left(\theta_j \right), \exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right ) \right ] + c$


$KL\left[ q\left(\theta_j \right), \exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right ) \right ]$最小就是讓$\int q\left(\theta\right)\log\frac{q\left(\theta\right)}{p\left(\theta,x\right)} d\theta$最小，也就是讓$KL\left [ q\left(\theta\right) , p\left( \theta \right | x)\right]$最小，目標就完成啦!!!!!!! 哈哈哈哈~~~~~(已瘋)

而可以把$KL\left[ q\left(\theta_j \right), \exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right ) \right ]$變得最小的$q\left(\theta_j \right)$不就是$\exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right )$本人嗎?

真是可喜可賀!!!

因此Variational Bayes演算法就大功告成了

$q^{*}\left(\theta_j \right) = \frac{1}{Z} \exp \left( E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] \right )$

或者寫成

$\log q^{*}=E_{q \left( \theta_{i \neq j} \right )} \left[ \log(\theta, x)) \right ] - \log Z$

逐個迭代$q \left( \theta_{j} \right )$直到收斂為止

[SAS] 賽仕冷知識(1) missing value 也有大小之分!?

其實平常不太用SAS這個我認為會越寫越笨的東西

題外話，他們倆是關係企業嗎？

但是今天不小心發現了一個它的小秘密!!就是missing value不只一種，然後不同種之間還有大小之分太精細了RRRRRRRRRR~~~

一般來說在SAS裡missing value是用「.」表示，排序上會比有的數字小，所以如果執行 proc sort 程序後，missing value都會在最上面。

除了一般的missing value之外，還有其他種類的missing value。像是「.A」~「.Z」，或是「._」這類特殊的missing value。

根據 SAS的文件，在排序上 「._」是最小的，其次是一般的missing value「.」，再來是「.A」~「.Z」。當然，數字永遠比missing value大。

最後來驗證一下

首先製造一筆資料

data aa; 
input name $ score; 
cards; 
A 60 
B 67 
C . 
D ._ 
E .A 
F .Z
G -10
;

排序一下

proc sort data=aa; 
by score; 
run;

然後來看結果

proc print data = aa;
run;

參考資料
http://support.sas.com/documentation/cdl/en/lrcon/62955/HTML/default/viewer.htm#a000989180.htm#a001221306

[JAVA] Big Data(4) Hadoop Multiple Input

Multiple Input

在map-reduce時，若不同的資料來源要塞給不同的mapper，最後再一起塞進reducer運算，就需要使用Multiple Input 的功能。如下圖，有三個不同的資料來源，先分別進入不同的mapper，然後最後要進到同一個reducer。

首先要先import需要的的類別
org.apache.hadoop.mapreduce.lib.input.MultipleInputs

然後在主程式(main)中寫入下面這一行，告訴電腦你要把哪一筆資料送進哪一個Mapper class的map函數

MultipleInputs.addInputPath(Job名稱, 輸入資料的位址, 格式, Mapper class的名字);

接下來看一個簡單到近乎無腦的例子
假設手上有三筆資料，都包含學號、科目和成績，但是長相就是不太一樣，現在我們要計算各科的平均分數

第一筆

$HADOOP/hadoop fs -cat input_1 | head -3
WUJ-360100;math;56
WPY-802007;math;98
FKT-670008;science;67

第二筆

$HADOOP/hadoop fs -cat input_2 | head -3
{Number:FJB-004150, Subject:math, Score:96}
{Number:QDG-300700, Subject:chinese, Score:90}
{Number:JVY-030140, Subject:chinese, Score:71}

第三筆

$HADOOP/hadoop fs -cat input_3 | head -3
[Number=>ITM-501806; Subject=>science; Score=>82]
[Number=>QBE-003981; Subject=>math; Score=>85]
[Number=>EUJ-017009; Subject=>chinese; Score=>63]

以上三種長相的資料要分別送給三種不同的Mapper中處理，產生(subject, score)的pair然後統一送進一個Reducer做平均數的計算，所以要準備三種Mapper

public static class Map1 extends Mapper
{
      public void map(LongWritable key, Text value, Context con) 
        throws IOException, InterruptedException
      {
              // get the student number
              String stNum = value.toString().split(";")[1];

              // get score
              int score = Integer.parseInt(value.toString().split(";")[2]);
              con.write(new Text(stNum), new IntWritable(score));
      }
}
public static class Map2 extends Mapper
{
      public void map(LongWritable key, Text value, Context con) 
        throws IOException, InterruptedException
      {       
              // "shave" the input value
              String line = value.toString().replaceAll("}", "");

              if(line.contains(",")){
                      // get the student number
                      String stNum = line.split(",")[1].split(":")[1];

                      // get score
                      int score = Integer.parseInt(line.split(",")[2].split(":")[1]);
                      con.write(new Text(stNum), new IntWritable(score));
              }
      }
}
public static class Map3 extends Mapper
{
      public void map(LongWritable key, Text value, Context con) 
        throws IOException, InterruptedException
      {
              // "shave" the input value
              String line=value.toString().replaceAll("[]\\[]", "");


              if(line.contains(";")){
                // get the student number
                String stNum = line.split(";")[1].split("=>")[1];

                // get score
                int score = Integer.parseInt(line.split(";")[2].split("=>")[1]);
                con.write(new Text(stNum), new IntWritable(score));
              }
      }
}

Reducer其實就只需要一個就可以了

public static class Red extends Reducer
{
     public void reduce(Text stNum, Iterable scores, Context con)
      throws IOException , InterruptedException
      {
              int numerator = 0;
              int denominator = 0;
              for (IntWritable v : scores){
                  numerator += v.get();
                  denominator ++;
              }
              int avg = numerator/denominator;
              con.write(stNum, new IntWritable(avg));
      }
}

然後是比較麻煩的主程式

public static void main(String[] args) throws Exception
{
      Configuration conf=new Configuration();
      String[] files=new GenericOptionsParser(conf,args).getRemainingArgs();
      Path inPath1=new Path(files[0]);
      Path inPath2=new Path(files[1]);
      Path inPath3=new Path(files[2]);
      Path outPath=new Path(files[3]);
      FileSystem hdfs = outPath.getFileSystem(conf);
      if (hdfs.exists(outPath)){
        hdfs.delete(outPath, true);
      };

      Job exampleJob = new Job(conf,"example");
      exampleJob.setJarByClass(MpInputExp.class);
      exampleJob.setMapperClass(Map1.class);
      exampleJob.setMapperClass(Map2.class);
      exampleJob.setMapperClass(Map3.class);
      exampleJob.setReducerClass(Red.class);
      exampleJob.setOutputKeyClass(Text.class);
      exampleJob.setOutputValueClass(IntWritable.class);

      MultipleInputs.addInputPath(exampleJob, inPath1, TextInputFormat.class, Map1.class);
      MultipleInputs.addInputPath(exampleJob, inPath2, TextInputFormat.class, Map2.class);
      MultipleInputs.addInputPath(exampleJob, inPath3, TextInputFormat.class, Map3.class);
      
      FileOutputFormat.setOutputPath(exampleJob, outPath);
      System.exit(exampleJob.waitForCompletion(true) ? 0:1);
}

要注意MultipleInputs.addInputPath有沒有把Input和Mapper配對好

最後來看結果(打包部分省略，可以參考這裡)

$HADOOP/hadoop fs -getmerge output_exp output_exp
cat output_exp

science 68
chinese 70
math    68

送上所有JAVA code結束這惱人的一切

import java.io.IOException;
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.FileSystem;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.MultipleInputs;
import org.apache.hadoop.mapreduce.lib.input.TextInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
import org.apache.hadoop.util.GenericOptionsParser;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public class MpInputExp
{
  public static class Map1 extends Mapper
  {
        public void map(LongWritable key, Text value, Context con) 
          throws IOException, InterruptedException
        {
                // get the student number
                String stNum = value.toString().split(";")[1];

                // get score
                int score = Integer.parseInt(value.toString().split(";")[2]);
                con.write(new Text(stNum), new IntWritable(score));
        }
  }
  public static class Map2 extends Mapper
  {
        public void map(LongWritable key, Text value, Context con) 
          throws IOException, InterruptedException
        {       
                // "shave" the input value
                String line = value.toString().replaceAll("}", "");

                if(line.contains(",")){
                        // get the student number
                        String stNum = line.split(",")[1].split(":")[1];

                        // get score
                        int score = Integer.parseInt(line.split(",")[2].split(":")[1]);
                        con.write(new Text(stNum), new IntWritable(score));
                }
        }
  }
  public static class Map3 extends Mapper
  {
        public void map(LongWritable key, Text value, Context con) 
          throws IOException, InterruptedException
        {
                // "shave" the input value
                String line=value.toString().replaceAll("[]\\[]", "");


                if(line.contains(";")){
                  // get the student number
                  String stNum = line.split(";")[1].split("=>")[1];

                  // get score
                  int score = Integer.parseInt(line.split(";")[2].split("=>")[1]);
                  con.write(new Text(stNum), new IntWritable(score));
                }
        }
  }
  public static class Red extends Reducer
  {
       public void reduce(Text stNum, Iterable scores, Context con)
        throws IOException , InterruptedException
        {
                int numerator = 0;
                int denominator = 0;
                for (IntWritable v : scores){
                    numerator += v.get();
                    denominator ++;
                }
                int avg = numerator/denominator;
                con.write(stNum, new IntWritable(avg));
        }
   }
  public static void main(String[] args) throws Exception
  {
        Configuration conf=new Configuration();
        String[] files=new GenericOptionsParser(conf,args).getRemainingArgs();
        Path inPath1=new Path(files[0]);
        Path inPath2=new Path(files[1]);
        Path inPath3=new Path(files[2]);
        Path outPath=new Path(files[3]);
        FileSystem hdfs = outPath.getFileSystem(conf);
        if (hdfs.exists(outPath)){
          hdfs.delete(outPath, true);
        };

        Job exampleJob = new Job(conf,"example");
        exampleJob.setJarByClass(MpInputExp.class);
        exampleJob.setMapperClass(Map1.class);
        exampleJob.setMapperClass(Map2.class);
        exampleJob.setMapperClass(Map3.class);
        exampleJob.setReducerClass(Red.class);
        exampleJob.setOutputKeyClass(Text.class);
        exampleJob.setOutputValueClass(IntWritable.class);

        MultipleInputs.addInputPath(exampleJob, inPath1, TextInputFormat.class, Map1.class);
        MultipleInputs.addInputPath(exampleJob, inPath2, TextInputFormat.class, Map2.class);
        MultipleInputs.addInputPath(exampleJob, inPath3, TextInputFormat.class, Map2.class);
        
        FileOutputFormat.setOutputPath(exampleJob, outPath);
        System.exit(exampleJob.waitForCompletion(true) ? 0:1);
  }
}

[機器學習] 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}$的長度

作為評估排序表現的依據