{"id":3403,"date":"2016-07-15T19:43:52","date_gmt":"2016-07-15T19:43:52","guid":{"rendered":"http:\/\/dalelane.co.uk\/blog\/?p=3403"},"modified":"2016-07-16T01:50:53","modified_gmt":"2016-07-16T01:50:53","slug":"normalised-discounted-cumulative-gain","status":"publish","type":"post","link":"https:\/\/dalelane.co.uk\/blog\/?p=3403","title":{"rendered":"Normalised Discounted Cumulative Gain"},"content":{"rendered":"

A ramble about accuracy compared with NDCG scores for evaluating effectiveness of information retrieval. It’s an introduction, so if you already know what they are, you can skip this.<\/strong><\/p>\n

A couple of weeks ago, we released a new tool<\/a> for training the IBM Watson Retrieve and Rank service<\/a> (a search service that uses machine learning to train it how to sort search results into the best order).<\/p>\n

This afternoon, I deployed a collection of small updates to the tool <\/a> and thought I’d make a few notes about what’s changed.<\/p>\n

Most of them are a bunch of incremental updates and minor bug fixes. <\/p>\n

<\/p>\n

For example, support for a wider range of Bluemix<\/a> environments, support for larger document cluster sizes, displaying the amount of disk space left in a cluster, and so on.<\/p>\n

One update in particular I thought was more interesting, and worth explaining.<\/p>\n

It’s something I’ve wanted to fix for a while, but didn’t get the time to before. I mentioned in my last post<\/a> that the tool represents a minimum viable product, and that there were lots of great ideas and many possible features that there wasn’t time to include. But two things in particular bugged me – two things that I wish I’d managed to get done in time for our initial release. And this is one of them.<\/p>\n

Evaluation<\/h2>\n

The tool needs to guide users through training the service. It also needs to evaluate how the training is going. This helps the tool decide how to drive the training next: the types of training task to give the user, the types of questions to focus on, and so on.<\/p>\n

It’s also something we explain to the user, so that they have a feel for how their training is going, and the impact that their work is having.<\/p>\n

We built this tool for someone who isn’t an expert in information retrieval or machine learning. That means we can’t show them a detailed dashboard with technical data. We can’t expect them to be able to interpret a learning curve. We decided to distill the results of the tests we run for them into a single figure. One metric that would represent a summarised view of the performance of the system they’ve trained.<\/p>\n

<\/p>\n

Accuracy<\/h2>\n

For the initial release, that metric was ‘accuracy@5’.<\/p>\n

That is to say, the percentage of the questions where the system returned a correct answer in one of the first five responses.<\/p>\n

I could argue that this is good because it’s easiest to understand for non-technical users. I could argue that typical use cases for search services like Retrieve and Rank will return a short list of answers, so if it’s returning something relevant in the first five answers then it’s doing a good job, making that a useful thing to measure. But really the biggest benefit was that it was very quick and easy to implement.<\/p>\n

The problems with accuracy<\/h3>\n

However, there’s a lot I don’t like about it.<\/p>\n

For example, imagine that for half the questions in the test, the service returns a list of answers like this:<\/p>\n

    \n
  1. A terrible answer\n<\/li>\n
  2. A truly awful answer\n<\/li>\n
  3. A ridiculous non-sensical answer\n<\/li>\n
  4. An unbelievably stupid answer\n<\/li>\n
  5. A partial but correct answer\n<\/li>\n
  6. …\n<\/li>\n<\/ol>\n

    The accuracy@5 score is 50%<\/strong>.
    \nHalf of the questions in the test met the requirement.<\/p>\n

    Now imagine you spend a few days diligently rating answers to questions. You do all the training tasks the tool prepares for you to continue training.<\/p>\n

    The test is run again. Imagine that for half the questions in the test, the service returns:<\/p>\n

      \n
    1. An amazing perfect answer\n<\/li>\n
    2. Another brilliant detailed answer\n<\/li>\n
    3. A fantastic answer\n<\/li>\n
    4. A very good answer\n<\/li>\n
    5. A partial, but still correct and relevant answer\n<\/li>\n
    6. …\n<\/li>\n<\/ol>\n

      The accuracy@5 score is 50%<\/strong>.
      \nHalf of the questions in the test met the requirement.<\/p>\n

      If that’s the only figure you look at, it looks like you haven’t achieved anything in all the training work you’ve done since the last test. It looks like you haven’t improved anything.<\/p>\n

      The metric fails to really describe the experience that someone would get from using the service, because it doesn’t differentiate between an answer that’s just okay and an answer that’s perfect.
      \nAnd it doesn’t differentiate between returning the answer at the top of the list, and returning an answer further down the list.
      \nAnd it doesn’t reflect the difference between easy questions and hard questions.
      \nAnd it doesn’t acknowledge questions where a correct answer isn’t even in any of your documents.
      \nAnd so on.<\/p>\n

      If the tool is only going to show a single metric, these sorts of issues are a problem. It’s not enough to let users know how their training is going. And this is what I mean by something that has bugged me.<\/p>\n

      Normalised Discounted Cumulative Gain<\/h2>\n

      Now that the tool is out, I had some time to try a variety of alternate approaches, and I’ve settled on using NDCG scores.<\/p>\n

      NDCG stands for Normalised Discounted Cumulative Gain<\/strong>, and addresses most of the problems I had with using accuracy scores.<\/p>\n

      The easiest way to explain it is to start at the end, and work backwards…<\/p>\n

      Gain<\/h3>\n

      You assign a value that represents the amount of gain you get from an answer that the system returns, based on how relevant it is. The more relevant, the more gain. And there’s no gain from an incorrect answer.<\/p>\n

      The tool is already guiding users to rate the answers they are shown as part of the training, so this maps to gain values very easily.<\/p>\n

      For example, I could say:<\/p>\n

        \n
      • perfect answers – gain of 3<\/strong>\n<\/li>\n
      • good answers – gain of 2<\/strong>\n<\/li>\n
      • answers that are at least in the right topic area – gain of 1<\/strong>\n<\/li>\n
      • incorrect answers – zero<\/strong> gain\n<\/li>\n<\/ul>\n

        There are different gain functions you can come up with, but this is what I’ve gone with for the tool, because it maps so neatly with the relevance labels we’re asking the users to collect already.<\/p>\n

        <\/p>\n

        This means we’re rewarding a system that returns perfect answers more than one that returns answers that are just okay.<\/p>\n

        Cumulative gain<\/h3>\n

        You add up the gain for the different answers that the system returns.<\/p>\n

        For example, if you’re interested in the first five answers that it returns to a question:<\/p>\n

          \n
        1. perfect answer\n<\/li>\n
        2. another perfect answer\n<\/li>\n
        3. a good answer\n<\/li>\n
        4. a good answer\n<\/li>\n
        5. an incorrect answer\n<\/li>\n<\/ol>\n

          The cumulative gain is
          \n3 + 3 + 2 + 2 + 0 = 10<\/strong><\/p>\n

          (For the tool, I’ve gone with the cumulative gain for the first ten answers to every question, but you get the idea).<\/p>\n

          This means we’re rewarding a system that returns a range of good answers more than one that returns a good answer together with a load of rubbish.<\/p>\n

          Discounted cumulative gain<\/h3>\n

          You discount the gain that an answer has, the further down the list it’s returned.<\/p>\n

          For example:<\/p>\n

            \n
          1. gain (answer in first place gets the full gain score)\n<\/li>\n
          2. gain \/ 2 (answer second in the list gets half of it’s gain score)\n<\/li>\n
          3. gain \/ 3 (answer third in the list gets a third of it’s gain score)\n<\/li>\n
          4. gain \/ 4 (answer fourth in the list gets a quarter of it’s gain score)\n<\/li>\n
          5. gain \/ 5 (answer fifth in the list gets a fifth of it’s gain score)\n<\/li>\n<\/ol>\n

            In other words, using the same example as before…<\/p>\n

              \n
            1. perfect answer\n<\/li>\n
            2. another perfect answer\n<\/li>\n
            3. a good answer\n<\/li>\n
            4. a good answer\n<\/li>\n
            5. an incorrect answer\n<\/li>\n<\/ol>\n

              The discounted cumulative gain (DCG) could be
              \n3 + (3 \/ 2) + (2 \/ 3) + (2 \/ 4) + (0 \/ 5) = 5.7<\/strong><\/p>\n

              There are different discounting functions you can use. The one I’ve described above is a little harsh. Halving the gain just because something is in 2nd place instead of 1st in a list of answers is probably too extreme a discount.<\/p>\n

              A more common function, and what I’ve gone with for the tool, is log2<\/sub><\/p>\n

                \n
              1. gain\n<\/li>\n
              2. gain \/ log2<\/sub> 2\n<\/li>\n
              3. gain \/ log2<\/sub> 3\n<\/li>\n
              4. gain \/ log2<\/sub> 4\n<\/li>\n
              5. gain \/ log2<\/sub> 5\n<\/li>\n<\/ol>\n

                e.g. The DCG would be
                \n3 + (3 \/ log2<\/sub> 2) + (2 \/ log2<\/sub> 3) + (2 \/ log2<\/sub> 4) + (0 \/ log2<\/sub> 5) = 8.3<\/strong><\/p>\n

                This means that we’re rewarding systems that return good answers higher in the list.<\/p>\n

                Normalised discounted cumulative gain<\/h3>\n

                You normalise the score compared with the best possible score.<\/p>\n

                There might not be a perfect answer in any of your documents to one question.
                \nAnother question might have loads of perfect answers in several documents.<\/p>\n

                It’s not really fair to compare their scores – it’s not necessarily as easy to find perfect answers to one question as it is to find perfect answers to another.<\/p>\n

                So instead, we normalise them, compared with the DCG you’d get for the best possible known answers in the perfect order.<\/p>\n

                For example, imagine a system with only five known possible answers returned:<\/p>\n

                  \n
                1. An incorrect answer (gain = 0)\n<\/li>\n
                2. A good answer (gain = 2)\n<\/li>\n
                3. A perfect answer (gain = 3)\n<\/li>\n
                4. A relevant answer (gain = 1)\n<\/li>\n
                5. A perfect answer (gain = 3)\n<\/li>\n<\/ol>\n

                  The DCG would be
                  \n0 + (2 \/ log2<\/sub> 2) + (3 \/ log2<\/sub> 3) + (1 \/ log2<\/sub> 4) + (3 \/ log2<\/sub> 5) = 5.7<\/strong><\/p>\n

                  The ideal DCG (iDCG) can be found by getting the score for:<\/p>\n

                    \n
                  1. A perfect answer (gain = 3)\n<\/li>\n
                  2. A perfect answer (gain = 3)\n<\/li>\n
                  3. A good answer (gain = 2)\n<\/li>\n
                  4. A relevant answer (gain = 1)\n<\/li>\n
                  5. An incorrect answer (gain = 0)\n<\/li>\n<\/ol>\n

                    The iDCG would be
                    \n3 + (3 \/ log2<\/sub> 2) + (2 \/ log2<\/sub> 3) + (1 \/ log2<\/sub> 4) + (0 \/ log2<\/sub> 5) = 7.8<\/strong><\/p>\n

                    The NDCG is DCG \/ iDCG<\/strong> and so would be
                    \n5.7 \/ 7.8 = 0.7<\/strong><\/p>\n

                    The final score is in a predictable range – from 0.0 to 1.0.<\/p>\n

                    0.0 for a system that performs terribly, to 1.0 for a system that returns the best possible answers in the best possible order (because DCG and iDCG will be the same, and DCG\/iDCG = 1)<\/p>\n

                    This means that we’re rewarding a system based on how it returns from what is actually possible.<\/p>\n

                    Explaining performance<\/h2>\n

                    Most of the users we’ve built the tool for won’t be aware of any of this. They won’t know what NDCG means or how the score was computed. And that’s fine. We’re showing them a single number and telling them that a bigger number means it’s doing better and a lower number is worse. <\/p>\n

                    (That said, we’ve put “NDCG” in the UI so some knowledgable users will have an idea what it means, and the curious users can always Google it to find out)<\/p>\n

                    Regardless, what we needed was to distill the performance of their trained system into a single metric. We needed one number that gives them a feel for how their training is going, factoring in the relevancy of the answers it’s returning and the order that they’re in. And of all the different metrics I’ve tried, I’m happiest with this one.<\/p>\n

                    <\/p>\n

                    With this afternoon’s updates, users who start training new rankers will see the performance of their ranker in NDCG scores.<\/p>\n","protected":false},"excerpt":{"rendered":"

                    A ramble about accuracy compared with NDCG scores for evaluating effectiveness of information retrieval. It’s an introduction, so if you already know what they are, you can skip this. A couple of weeks ago, we released a new tool for training the IBM Watson Retrieve and Rank service (a search service that uses machine learning […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,4],"tags":[569,505],"class_list":["post-3403","post","type-post","status-publish","format-standard","hentry","category-code","category-ibm","tag-ibm","tag-watson"],"_links":{"self":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/3403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3403"}],"version-history":[{"count":0,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=\/wp\/v2\/posts\/3403\/revisions"}],"wp:attachment":[{"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dalelane.co.uk\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}