path: root/ml/dlib/dlib/svm/ranking_tools.h

// Copyright (C) 2012  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_RANKING_ToOLS_Hh_
#define DLIB_RANKING_ToOLS_Hh_

#include "ranking_tools_abstract.h"

#include "../algs.h"
#include "../matrix.h"
#include <vector>
#include <utility>
#include <algorithm>
#include "sparse_vector.h"
#include "../statistics.h"

namespace dlib
{

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    struct ranking_pair
    {
        ranking_pair() {}

        ranking_pair(
            const std::vector<T>& r, 
            const std::vector<T>& nr
        ) :
            relevant(r), nonrelevant(nr) 
        {}

        std::vector<T> relevant;
        std::vector<T> nonrelevant;
    };

    template <
        typename T
        >
    void serialize (
        const ranking_pair<T>& item,
        std::ostream& out
    )
    {
        int version = 1;
        serialize(version, out);
        serialize(item.relevant, out);
        serialize(item.nonrelevant, out);
    }


    template <
        typename T
        >
    void deserialize (
        ranking_pair<T>& item,
        std::istream& in 
    )
    {
        int version = 0;
        deserialize(version, in);
        if (version != 1)
            throw dlib::serialization_error("Wrong version found while deserializing dlib::ranking_pair");

        deserialize(item.relevant, in);
        deserialize(item.nonrelevant, in);
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    typename disable_if<is_matrix<T>,bool>::type is_ranking_problem (
        const std::vector<ranking_pair<T> >& samples
    )
    {
        if (samples.size() == 0)
            return false;


        for (unsigned long i = 0; i < samples.size(); ++i)
        {
            if (samples[i].relevant.size() == 0)
                return false;
            if (samples[i].nonrelevant.size() == 0)
                return false;
        }

        return true;
    }

    template <
        typename T
        >
    typename enable_if<is_matrix<T>,bool>::type is_ranking_problem (
        const std::vector<ranking_pair<T> >& samples
    )
    {
        if (samples.size() == 0)
            return false;


        for (unsigned long i = 0; i < samples.size(); ++i)
        {
            if (samples[i].relevant.size() == 0)
                return false;
            if (samples[i].nonrelevant.size() == 0)
                return false;
        }

        // If these are dense vectors then they must all have the same dimensionality.
        const long dims = max_index_plus_one(samples[0].relevant);
        for (unsigned long i = 0; i < samples.size(); ++i)
        {
            for (unsigned long j = 0; j < samples[i].relevant.size(); ++j)
            {
                if (is_vector(samples[i].relevant[j]) == false)
                    return false;

                if (samples[i].relevant[j].size() != dims)
                    return false;
            }
            for (unsigned long j = 0; j < samples[i].nonrelevant.size(); ++j)
            {
                if (is_vector(samples[i].nonrelevant[j]) == false)
                    return false;

                if (samples[i].nonrelevant[j].size() != dims)
                    return false;
            }
        }

        return true;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename T
        >
    unsigned long max_index_plus_one (
        const ranking_pair<T>& item
    )
    {
        return std::max(max_index_plus_one(item.relevant), max_index_plus_one(item.nonrelevant));
    }

    template <
        typename T
        >
    unsigned long max_index_plus_one (
        const std::vector<ranking_pair<T> >& samples
    )
    {
        unsigned long dims = 0;
        for (unsigned long i = 0; i < samples.size(); ++i)
        {
            dims = std::max(dims, max_index_plus_one(samples[i]));
        }
        return dims;
    }

// ----------------------------------------------------------------------------------------

    template <typename T>
    void count_ranking_inversions (
        const std::vector<T>& x,
        const std::vector<T>& y,
        std::vector<unsigned long>& x_count,
        std::vector<unsigned long>& y_count
    )
    {
        x_count.assign(x.size(),0);
        y_count.assign(y.size(),0);

        if (x.size() == 0 || y.size() == 0)
            return;

        std::vector<std::pair<T,unsigned long> > xsort(x.size());
        std::vector<std::pair<T,unsigned long> > ysort(y.size());
        for (unsigned long i = 0; i < x.size(); ++i)
            xsort[i] = std::make_pair(x[i], i);
        for (unsigned long j = 0; j < y.size(); ++j)
            ysort[j] = std::make_pair(y[j], j);

        std::sort(xsort.begin(), xsort.end());
        std::sort(ysort.begin(), ysort.end());


        unsigned long i, j;

        // Do the counting for the x values.
        for (i = 0, j = 0; i < x_count.size(); ++i)
        {
            // Skip past y values that are in the correct order with respect to xsort[i].
            while (j < ysort.size() && ysort[j].first < xsort[i].first) 
                ++j;

            x_count[xsort[i].second] = ysort.size() - j;
        }


        // Now do the counting for the y values.
        for (i = 0, j = 0; j < y_count.size(); ++j)
        {
            // Skip past x values that are in the incorrect order with respect to ysort[j].
            while (i < xsort.size() && !(ysort[j].first < xsort[i].first)) 
                ++i;

            y_count[ysort[j].second] = i;
        }
    }

// ----------------------------------------------------------------------------------------

    namespace impl
    {
        inline bool compare_first_reverse_second (
            const std::pair<double,bool>& a,
            const std::pair<double,bool>& b
        )
        {
            if (a.first < b.first)
                return true;
            else if (a.first > b.first)
                return false;
            else if (a.second && !b.second)
                return true;
            else
                return false;
        }
    }

    template <
        typename ranking_function,
        typename T
        >
    matrix<double,1,2> test_ranking_function (
        const ranking_function& funct,
        const std::vector<ranking_pair<T> >& samples
    )
    {
        // make sure requires clause is not broken
        DLIB_ASSERT(is_ranking_problem(samples),
            "\t double test_ranking_function()"
            << "\n\t invalid inputs were given to this function"
            << "\n\t samples.size(): " << samples.size() 
            << "\n\t is_ranking_problem(samples): " << is_ranking_problem(samples)
            );

        unsigned long total_pairs = 0;
        unsigned long total_wrong = 0;

        std::vector<double> rel_scores;
        std::vector<double> nonrel_scores;
        std::vector<unsigned long> rel_counts;
        std::vector<unsigned long> nonrel_counts;

        running_stats<double> rs;
        std::vector<std::pair<double,bool> > total_scores;
        std::vector<bool> total_ranking;

        for (unsigned long i = 0; i < samples.size(); ++i)
        {
            rel_scores.resize(samples[i].relevant.size());
            nonrel_scores.resize(samples[i].nonrelevant.size());
            total_scores.clear();

            for (unsigned long k = 0; k < rel_scores.size(); ++k)
            {
                rel_scores[k] = funct(samples[i].relevant[k]);
                total_scores.push_back(std::make_pair(rel_scores[k], true));
            }

            for (unsigned long k = 0; k < nonrel_scores.size(); ++k)
            {
                nonrel_scores[k] = funct(samples[i].nonrelevant[k]);
                total_scores.push_back(std::make_pair(nonrel_scores[k], false));
            }

            // Now compute the average precision for this sample.  We need to sort the
            // results and the back them into total_ranking.  Note that we sort them so
            // that, if you get a block of ranking values that are all equal, the elements
            // marked as true will come last.  This prevents a ranking from outputting a
            // constant value for everything and still getting a good MAP score.
            std::sort(total_scores.rbegin(), total_scores.rend(), impl::compare_first_reverse_second);
            total_ranking.clear();
            for (unsigned long i = 0; i < total_scores.size(); ++i)
                total_ranking.push_back(total_scores[i].second);
            rs.add(average_precision(total_ranking));


            count_ranking_inversions(rel_scores, nonrel_scores, rel_counts, nonrel_counts);

            total_pairs += rel_scores.size()*nonrel_scores.size();

            // Note that we don't need to look at nonrel_counts since it is redundant with
            // the information in rel_counts in this case.
            total_wrong += sum(mat(rel_counts));
        }

        const double rank_swaps = static_cast<double>(total_pairs - total_wrong) / total_pairs;
        const double mean_average_precision = rs.mean();
        matrix<double,1,2> res;
        res = rank_swaps, mean_average_precision;
        return res;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename ranking_function,
        typename T
        >
    matrix<double,1,2> test_ranking_function (
        const ranking_function& funct,
        const ranking_pair<T>& sample
    )
    {
        return test_ranking_function(funct, std::vector<ranking_pair<T> >(1,sample));
    }

// ----------------------------------------------------------------------------------------

    template <
        typename trainer_type,
        typename T
        >
    matrix<double,1,2> cross_validate_ranking_trainer (
        const trainer_type& trainer,
        const std::vector<ranking_pair<T> >& samples,
        const long folds
    )
    {
        // make sure requires clause is not broken
        DLIB_ASSERT(is_ranking_problem(samples) &&
                    1 < folds && folds <= static_cast<long>(samples.size()),
            "\t double cross_validate_ranking_trainer()"
            << "\n\t invalid inputs were given to this function"
            << "\n\t samples.size(): " << samples.size() 
            << "\n\t folds:  " << folds 
            << "\n\t is_ranking_problem(samples): " << is_ranking_problem(samples)
            );


        const long num_in_test  = samples.size()/folds;
        const long num_in_train = samples.size() - num_in_test;


        std::vector<ranking_pair<T> > samples_test, samples_train;


        long next_test_idx = 0;

        unsigned long total_pairs = 0;
        unsigned long total_wrong = 0;

        std::vector<double> rel_scores;
        std::vector<double> nonrel_scores;
        std::vector<unsigned long> rel_counts;
        std::vector<unsigned long> nonrel_counts;

        running_stats<double> rs;
        std::vector<std::pair<double,bool> > total_scores;
        std::vector<bool> total_ranking;

        for (long i = 0; i < folds; ++i)
        {
            samples_test.clear();
            samples_train.clear();

            // load up the test samples
            for (long cnt = 0; cnt < num_in_test; ++cnt)
            {
                samples_test.push_back(samples[next_test_idx]);
                next_test_idx = (next_test_idx + 1)%samples.size();
            }

            // load up the training samples
            long next = next_test_idx;
            for (long cnt = 0; cnt < num_in_train; ++cnt)
            {
                samples_train.push_back(samples[next]);
                next = (next + 1)%samples.size();
            }


            const typename trainer_type::trained_function_type& df = trainer.train(samples_train);

            // check how good df is on the test data
            for (unsigned long i = 0; i < samples_test.size(); ++i)
            {
                rel_scores.resize(samples_test[i].relevant.size());
                nonrel_scores.resize(samples_test[i].nonrelevant.size());

                total_scores.clear();

                for (unsigned long k = 0; k < rel_scores.size(); ++k)
                {
                    rel_scores[k] = df(samples_test[i].relevant[k]);
                    total_scores.push_back(std::make_pair(rel_scores[k], true));
                }

                for (unsigned long k = 0; k < nonrel_scores.size(); ++k)
                {
                    nonrel_scores[k] = df(samples_test[i].nonrelevant[k]);
                    total_scores.push_back(std::make_pair(nonrel_scores[k], false));
                }

                // Now compute the average precision for this sample.  We need to sort the
                // results and the back them into total_ranking.  Note that we sort them so
                // that, if you get a block of ranking values that are all equal, the elements
                // marked as true will come last.  This prevents a ranking from outputting a
                // constant value for everything and still getting a good MAP score.
                std::sort(total_scores.rbegin(), total_scores.rend(), impl::compare_first_reverse_second);
                total_ranking.clear();
                for (unsigned long i = 0; i < total_scores.size(); ++i)
                    total_ranking.push_back(total_scores[i].second);
                rs.add(average_precision(total_ranking));


                count_ranking_inversions(rel_scores, nonrel_scores, rel_counts, nonrel_counts);

                total_pairs += rel_scores.size()*nonrel_scores.size();

                // Note that we don't need to look at nonrel_counts since it is redundant with
                // the information in rel_counts in this case.
                total_wrong += sum(mat(rel_counts));
            }

        } // for (long i = 0; i < folds; ++i)

        const double rank_swaps = static_cast<double>(total_pairs - total_wrong) / total_pairs;
        const double mean_average_precision = rs.mean();
        matrix<double,1,2> res;
        res = rank_swaps, mean_average_precision;
        return res;
    }

// ----------------------------------------------------------------------------------------

}

#endif // DLIB_RANKING_ToOLS_Hh_