wolffd@0: function [Y, Loss] = separationOracleAUC(q, D, pos, neg, k)
wolffd@0: %
wolffd@0: %   [Y,Loss]  = separationOracleAUC(q, D, pos, neg, k)
wolffd@0: %
wolffd@0: %   q   = index of the query point
wolffd@0: %   D   = the current distance matrix
wolffd@0: %   pos = indices of relevant results for q
wolffd@0: %   neg = indices of irrelevant results for q
wolffd@0: %   k   = length of the list to consider (unused in AUC)
wolffd@0: %
wolffd@0: %   Y is a permutation 1:n corresponding to the maximally
wolffd@0: %   violated constraint
wolffd@0: %
wolffd@0: %   Loss is the loss for Y, in this case, 1-AUC(Y)
wolffd@0: 
wolffd@0: 
wolffd@0:     % First, sort the documents in descending order of W'Phi(q,x)
wolffd@0:     % Phi = - (X(q) - X(x)) * (X(q) - X(x))'
wolffd@0:     
wolffd@0:     % Sort the positive documents
wolffd@0:     ScorePos        = - D(pos,q);
wolffd@0:     [Vpos, Ipos]    = sort(full(ScorePos'), 'descend');
wolffd@0:     Ipos            = pos(Ipos);
wolffd@0:     
wolffd@0:     % Sort the negative documents
wolffd@0:     ScoreNeg        = - D(neg,q);
wolffd@0:     [Vneg, Ineg]    = sort(full(ScoreNeg'), 'descend');
wolffd@0:     Ineg            = neg(Ineg);
wolffd@0: 
wolffd@0: 
wolffd@0:     % How many pos and neg documents are we using here?
wolffd@0:     numPos  = length(pos);
wolffd@0:     numNeg  = length(neg);
wolffd@0:     n       = numPos + numNeg;
wolffd@0: 
wolffd@0: 
wolffd@0:     NegsBefore = sum(bsxfun(@lt, Vpos, Vneg' + 0.5),1);
wolffd@0: 
wolffd@0:     % Construct Y from NegsBefore
wolffd@0:     Y                           = nan * ones(n,1);
wolffd@0:     Y((1:numPos) + NegsBefore)  = Ipos;
wolffd@0:     Y(isnan(Y))                 = Ineg;
wolffd@0: 
wolffd@0:     % Compute AUC loss for this ranking
wolffd@0:     Loss = 1 - sum(NegsBefore) / (numPos * numNeg * 2);
wolffd@0: end
wolffd@0: