Mercurial > hg > camir-aes2014
comparison toolboxes/distance_learning/mlr/separationOracle/separationOracleKNN.m @ 0:e9a9cd732c1e tip
first hg version after svn
author | wolffd |
---|---|
date | Tue, 10 Feb 2015 15:05:51 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:e9a9cd732c1e |
---|---|
1 function [Y, Loss] = separationOracleKNN(q, D, pos, neg, k) | |
2 % | |
3 % [Y,Loss] = separationOracleKNN(q, D, pos, neg, k) | |
4 % | |
5 % q = index of the query point | |
6 % D = the current distance matrix | |
7 % pos = indices of relevant results for q | |
8 % neg = indices of irrelevant results for q | |
9 % k = length of the list to consider | |
10 % | |
11 % Y is a permutation 1:n corresponding to the maximally | |
12 % violated constraint | |
13 % | |
14 % Loss is the loss for Y, in this case, 1-Prec@k(Y) | |
15 | |
16 | |
17 % First, sort the documents in descending order of W'Phi(q,x) | |
18 % Phi = - (X(q) - X(x)) * (X(q) - X(x))' | |
19 | |
20 % Sort the positive documents | |
21 ScorePos = - D(pos,q); | |
22 [Vpos, Ipos] = sort(full(ScorePos'), 'descend'); | |
23 Ipos = pos(Ipos); | |
24 | |
25 % Sort the negative documents | |
26 ScoreNeg = - D(neg,q); | |
27 [Vneg, Ineg] = sort(full(ScoreNeg'), 'descend'); | |
28 Ineg = neg(Ineg); | |
29 | |
30 % Now, solve the DP for the interleaving | |
31 | |
32 numPos = length(pos); | |
33 numNeg = length(neg); | |
34 n = numPos + numNeg; | |
35 | |
36 cVpos = cumsum(Vpos); | |
37 cVneg = cumsum(Vneg); | |
38 | |
39 | |
40 % If we don't have enough positive (or negative) examples, scale k down | |
41 k = min([k, numPos, numNeg]); | |
42 | |
43 % Algorithm: | |
44 % For each precision score in 0, 1/k, 2/k, ... 1 | |
45 % Calculate maximum discriminant score for that precision level | |
46 KNN = (0:(1/k):1)' > 0.5; | |
47 Discriminant = zeros(k+1, 1); | |
48 NegsBefore = zeros(numPos,k+1); | |
49 | |
50 % For 0 precision, all positives go after the first k negatives | |
51 | |
52 NegsBefore(:,1) = k + binarysearch(Vpos, Vneg(k+1:end)); | |
53 Discriminant(1) = Vpos * (numNeg - 2 * NegsBefore(:,1)) + numPos * cVneg(end) ... | |
54 - 2 * sum(cVneg(NegsBefore((NegsBefore(:,1) > 0),1))); | |
55 | |
56 | |
57 | |
58 % For precision (a-1)/k, swap the (a-1)'th positive doc | |
59 % into the top (k-a) negative docs | |
60 | |
61 for a = 2:(k+1) | |
62 NegsBefore(:,a) = NegsBefore(:,a-1); | |
63 | |
64 % We have a-1 positives, and k - (a-1) negatives | |
65 NegsBefore(a-1, a) = binarysearch(Vpos(a-1), Vneg(1:(k-a+1))); | |
66 | |
67 % There were NegsBefore(a-1,a-1) negatives before (a-1) | |
68 % Now there are NegsBefore(a,a-1) | |
69 | |
70 Discriminant(a) = Discriminant(a-1) ... | |
71 + 2 * (NegsBefore(a-1,a-1) - NegsBefore(a-1,a)) * Vpos(a-1); | |
72 | |
73 if NegsBefore(a-1,a-1) > 0 | |
74 Discriminant(a) = Discriminant(a) + 2 * cVneg(NegsBefore(a-1,a-1)); | |
75 end | |
76 if NegsBefore(a-1,a) > 0 | |
77 Discriminant(a) = Discriminant(a) - 2 * cVneg(NegsBefore(a-1,a)); | |
78 end | |
79 end | |
80 | |
81 % Normalize discriminant scores | |
82 Discriminant = Discriminant / (numPos * numNeg); | |
83 [s, x] = max(Discriminant - KNN); | |
84 | |
85 % Now we know that there are x-1 relevant docs in the max ranking | |
86 % Construct Y from NegsBefore(x,:) | |
87 | |
88 Y = nan * ones(n,1); | |
89 Y((1:numPos)' + NegsBefore(:,x)) = Ipos; | |
90 if sum(isnan(Y)) ~= length(Ineg) | |
91 keyboard; | |
92 end | |
93 Y(isnan(Y)) = Ineg; | |
94 | |
95 % Compute loss for this list | |
96 Loss = 1 - KNN(x); | |
97 end | |
98 |