MAP@k вычисление

Средняя средняя точность, вычисленная при k (для топ-k элементов в ответе), согласно вики, мл метрики в kaggle, и этот ответ: Путаница в отношении (средней) средней точности должна быть вычислена как среднее средней точности при k, где среднее Точность при k вычисляется как:

Где: P(i) - точность при отсечении i в списке; rel(i) - это индикаторная функция, равная 1, если элемент с рангом i является релевантным документом, в противном случае ноль.

Делитель min(k, number of relevant documents) имеет значение максимально возможного количества релевантных записей в ответе.

Это понимание правильно?

Всегда ли MAP@k меньше MAP, вычисляемого для всего ранжированного списка?

Меня беспокоит то, что во многих работах MAP@k вычисляется не так.

Типично, что делитель не min(k, number of relevant documents), но количество относительных документов в топ-к. Этот подход даст более высокое значение MAP@k.


HashNet: глубокое обучение хешу через продолжение " (ICCV 2017)

Код: https://github.com/thuml/HashNet/blob/master/pytorch/src/test.py

    for i in range(query_num):
        label = validation_labels[i, :]
        label[label == 0] = -1
        idx = ids[:, i]
        imatch = np.sum(database_labels[idx[0:R], :] == label, axis=1) > 0
        relevant_num = np.sum(imatch)
        Lx = np.cumsum(imatch)
        Px = Lx.astype(float) / np.arange(1, R+1, 1)
        if relevant_num != 0:
            APx.append(np.sum(Px * imatch) / relevant_num)

куда relevant_num это не min(k, number of relevant documents), но количество соответствующих документов в результате, которое не совпадает с общим количеством относительных документов или k.

Я неправильно читаю код?


Глубокое визуально-семантическое квантование эффективного поиска изображений CVPR 2017

Код: https://github.com/caoyue10/cvpr17-dvsq/blob/master/util.py

def get_mAPs_by_feature(self, database, query):
    ips = np.dot(query.output, database.output.T)
    #norms = np.sqrt(np.dot(np.reshape(np.sum(query.output ** 2, 1), [query.n_samples, 1]), np.reshape(np.sum(database.output ** 2, 1), [1, database.n_samples])))
    #self.all_rel = ips / norms
    self.all_rel = ips
    ids = np.argsort(-self.all_rel, 1)
    APx = []
    query_labels = query.label
    database_labels = database.label
    print "#calc mAPs# calculating mAPs"
    bar = ProgressBar(total=self.all_rel.shape[0])
    for i in xrange(self.all_rel.shape[0]):
        label = query_labels[i, :]
        label[label == 0] = -1
        idx = ids[i, :]
        imatch = np.sum(database_labels[idx[0: self.R], :] == label, 1) > 0
        rel = np.sum(imatch)
        Lx = np.cumsum(imatch)
        Px = Lx.astype(float) / np.arange(1, self.R+1, 1)
        if rel != 0:
            APx.append(np.sum(Px * imatch) / rel)
        bar.move()
    print "mAPs: ", np.mean(np.array(APx))
    return np.mean(np.array(APx))

Где делитель rel, который вычисляется как np.sum(imatch), где imatch является двоичным вектором, который указывает, является ли запись релевантной или нет. Проблема в том, что это занимает только первое R: imatch = np.sum(database_labels[idx[0: self.R], :] == label, 1) > 0, Так np.sum(imatch) даст количество соответствующих записей в возвращенном списке размера R, но нет min(R, number of relevant entries), И обратите внимание, что значения R в работе используются меньше количества записей в БД.


Углубленное изучение двоичных хеш-кодов для быстрого поиска изображений (CVPR 2015)

Код: https://github.com/kevinlin311tw/caffe-cvprw15/blob/master/analysis/precision.m#L30-L55

    buffer_yes = zeros(K,1);
    buffer_total = zeros(K,1);
    total_relevant = 0;

    for j = 1:K
        retrieval_label = trn_label(y2(j));

        if (query_label==retrieval_label)
            buffer_yes(j,1) = 1;
            total_relevant = total_relevant + 1;
        end
        buffer_total(j,1) = 1;
    end

    % compute precision
    P = cumsum(buffer_yes) ./ Ns';

    if (sum(buffer_yes) == 0)
        AP(i) = 0;
    else
        AP(i) = sum(P.*buffer_yes) / sum(buffer_yes);
    end

Здесь делитель sum(buffer_yes) это число относительных документов в возвращенном списке размера k, а не min(k, number of relevant documents),


"Контролируемое изучение семантики, сохраняющей глубокое хеширование" (TPAMI 2017)

Код: https://github.com/kevinlin311tw/Caffe-DeepBinaryCode/blob/master/analysis/precision.m

Код такой же, как и в предыдущей статье.


Изучение компактных двоичных дескрипторов с неконтролируемыми глубокими нейронными сетями (CVPR 2016)

Тот же код: https://github.com/kevinlin311tw/cvpr16-deepbit/blob/master/analysis/precision.m#L32-L55



Я что-то пропустил? Правильно ли указан код в приведенных выше документах? Почему он не совпадает с https://github.com/benhamner/Metrics/blob/master/Python/ml_metrics/average_precision.py?


Обновить

Я нашел этот закрытый вопрос, ссылаясь на ту же проблему: https://github.com/thuml/HashNet/issues/2

Правильно ли следующее утверждение?

AP является метрикой рейтинга. Если 2 верхних поиска в ранжированном списке являются релевантными (и только 2 верхними), AP составляет 100%. Вы говорите о Recall, который в этом случае действительно составляет 0,2%.

Насколько я понимаю, если мы рассматриваем AP как область под кривой PR, утверждение выше не является правильным.


PS Я сомневался, стоит ли переходить на Cross Validated или Stackru. Если вы думаете, что лучше поместить его в Cross Validated, я не возражаю. Я рассуждал, что это не теоретический вопрос, а вопрос реализации со ссылкой на реальный код.

1 ответ

Решение

Вы совершенно правы и молодцы, что нашли это. Учитывая сходство кода, я предполагаю, что есть одна исходная ошибка, а затем статьи после статей копировали плохую реализацию, не рассматривая ее внимательно.

Выпускник "akturtle" тоже совершенно прав, я собирался привести тот же пример. Я не уверен, что "кунхэ" понял аргумент, конечно, вспомнить имеет значение при вычислении средней точности.

Да, ошибка должна надувать цифры. Я просто надеюсь, что рейтинговые списки достаточно длинные и что методы достаточно разумны, так что они достигают 100% отзыва в ранжированном списке, и в этом случае ошибка не повлияет на результаты.

К сожалению, рецензентам трудно это уловить, так как обычно никто не рецензирует код статьи. Стоит связаться с авторами, чтобы попытаться заставить их обновить код, обновить свои документы с правильными номерами или, по крайней мере, не продолжать повторять ошибку. в своих будущих работах. Если вы планируете написать статью, в которой сравниваются разные методы, вы можете указать на проблему и сообщить правильные цифры (а также, возможно, те, которые содержат ошибку, просто чтобы сделать яблоки для сравнения яблок).

Чтобы ответить на ваш дополнительный вопрос:

Всегда ли MAP@k меньше MAP, вычисляемого для всего ранжированного списка?

Не обязательно, MAP@k по существу вычисляет MAP, нормализуя для потенциального случая, когда вы не можете сделать что-либо лучше, если бы только k запросов. Например, рассмотрите возвращенный ранжированный список с релевантностями: 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 и предположите, что в общей сложности 6 соответствующих документов. MAP должен быть немного выше, чем 50%, в то время как MAP@3 = 100%, потому что вы не можете сделать ничего лучше, чем извлечь 1 1 1. Но это не связано с обнаруженной вами ошибкой, так как с их ошибкой MAP@k гарантируется быть по крайней мере таким же большим, как истинная карта @k.

Другие вопросы по тегам