{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Evaluation #\n\nWe can compute the Kendall tau correlation between the predicted cell orders and the ground truth cell orders by counting how many swaps of adjacent cells are needed to sort the predicted order into the ground truth order.\n\nA pair \\\\(i, j\\\\) of indices is called an **inversion** within a numeric sequence \\\\(A\\\\) when \\\\(i < j\\\\) but \\\\(A[i] > A[j]\\\\). An inversion indicates that a pair of numbers in the sequence is *out of order*. The number of swaps needed to correctly sort the predictions turns out to be equivalent to the number of inversions in its ranking of the cells relative to the ground-truth ranking.\n\nThe following cell shows an intuitive, but rather slow (\\\\(O(n^2)\\\\)) way to count inversions in a list of ranks.","metadata":{}},{"cell_type":"code","source":"def count_inversions_slowly(ranks):\n    inversions = 0\n    size = len(ranks)\n    for i in range(size):\n        for j in range(i+1, size):\n            if ranks[i] > ranks[j]:\n                total += 1\n    return total","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"This implementation is much faster, though theoretically also \\\\(O(n^2)\\\\). (You might enjoy reviewing other inversion counting algorithms from [this StackOverflow post](https://stackoverflow.com/a/47845960).)","metadata":{}},{"cell_type":"code","source":"from bisect import bisect\n\n\n# Actually O(N^2), but fast in practice for our data\ndef count_inversions(a):\n    inversions = 0\n    sorted_so_far = []\n    for i, u in enumerate(a):  # O(N)\n        j = bisect(sorted_so_far, u)  # O(log N)\n        inversions += i - j\n        sorted_so_far.insert(j, u)  # O(N)\n    return inversions","metadata":{},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"To compute the Kendall tau correlation, we sum up the inversions across all predictions and also the worst-case number of inversions across all predictions, and apply the following formula:\n\\\\[K = 1 - 4 \\frac{\\sum_i S_{i}}{\\sum_i n_i(n_i - 1)}\\\\]\nwhere \\\\(S_i\\\\) is the number of inversions in the predicted ranks and \\\\(n_i\\\\) is the number of cells for notebook \\\\(i\\\\).","metadata":{}},{"cell_type":"code","source":"def kendall_tau(ground_truth, predictions):\n    total_inversions = 0  # total inversions in predicted ranks across all instances\n    total_2max = 0  # maximum possible inversions across all instances\n    for gt, pred in zip(ground_truth, predictions):\n        ranks = [gt.index(x) for x in pred]  # rank predicted order in terms of ground truth\n        total_inversions += count_inversions(ranks)\n        n = len(gt)\n        total_2max += n * (n - 1)\n    return 1 - 4 * total_inversions / total_2max","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-05-10T16:06:40.36077Z","iopub.execute_input":"2022-05-10T16:06:40.361342Z","iopub.status.idle":"2022-05-10T16:06:40.391879Z","shell.execute_reply.started":"2022-05-10T16:06:40.361248Z","shell.execute_reply":"2022-05-10T16:06:40.391064Z"},"trusted":true},"execution_count":null,"outputs":[]}]}