wolffd@0: function [Y, Loss] = separationOracleMRR(q, D, pos, neg, k)
wolffd@0: %
wolffd@0: %   [Y,Loss]  = separationOracleMRR(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 MRR)
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-MRR(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:     % Now, solve the DP for the interleaving
wolffd@0: 
wolffd@0:     numPos  = length(pos);
wolffd@0:     numNeg  = length(neg);
wolffd@0:     n       = numPos + numNeg;
wolffd@0: 
wolffd@0:     cVpos           = cumsum(Vpos);
wolffd@0:     cVneg           = cumsum(Vneg);
wolffd@0: 
wolffd@0: 
wolffd@0:     % Algorithm:
wolffd@0:     %   For each RR score in 1/1, 1/2, ..., 1/(numNeg+1)
wolffd@0:     %       Calculate maximum discriminant score for that precision level
wolffd@0:     MRR                     = ((1:(numNeg+1)).^-1)';
wolffd@0: 
wolffd@0:     
wolffd@0:     Discriminant            = zeros(numNeg+1, 1);
wolffd@0:     Discriminant(end)       = numPos * cVneg(end) - numNeg * cVpos(end);
wolffd@0:     
wolffd@0:     % For the rest of the positions, we're interleaving one more negative
wolffd@0:     % example into the 2nd-through-last positives
wolffd@0:     offsets                 = 1 + binarysearch(Vneg, Vpos(2:end));
wolffd@0:     
wolffd@0:     % How many of the remaining positives go before Vneg(a)?
wolffd@0:     NegsBefore              = -bsxfun(@ge, offsets, (1:length(Vpos))');
wolffd@0: 
wolffd@0:     % For the last position, all negatives come before all positives
wolffd@0:     NegsBefore(:,numNeg+1)  = numNeg;
wolffd@0: 
wolffd@0:     Discriminant(1:numNeg) = -2 * (offsets .* Vneg - cVpos(offsets));
wolffd@0:     Discriminant = sum(Discriminant) - cumsum(Discriminant) + Discriminant;
wolffd@0: 
wolffd@0: 
wolffd@0:     % Normalize discriminant scores
wolffd@0:     Discriminant    = Discriminant / (numPos * numNeg);
wolffd@0:     [s, x]          = max(Discriminant - MRR);
wolffd@0: 
wolffd@0:     % Now we know that there are x-1 relevant docs in the max ranking
wolffd@0:     % Construct Y from NegsBefore(x,:)
wolffd@0: 
wolffd@0:     Y = nan * ones(n,1);
wolffd@0:     Y((1:numPos)' + sum(NegsBefore(:,x:end),2)) = Ipos;
wolffd@0:     Y(isnan(Y))                     = Ineg;
wolffd@0: 
wolffd@0:     % Compute loss for this list
wolffd@0:     Loss        = 1 - MRR(x);
wolffd@0: end
wolffd@0: