{"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":"## [日本語版はversion 1です．](https://www.kaggle.com/code/yufuin/ai4code-linearity-of-kendall-s-tau-english?scriptVersionId=95794450 \"version 1\") This notebook has the Japanese version (version=1).  ","metadata":{}},{"cell_type":"markdown","source":"In [discussion: About loss function and better score](https://www.kaggle.com/competitions/AI4Code/discussion/325272), it is pointed out that the L1 loss could be effective for this task.  \nThis should be correct because of the property of Kendall's tau.\n# In this notebook, we'll see the linearity of Kendall's tau and the correctness to use the L1 loss to train the model.\n\nIn this competition, we use Kendall's tau as the competition metric.\nKendall's tau is to measure the ordinal association between two orderings.\nThe range of Kendall's tau is -1 to 1.\n\nLet's assume ordered elements that has the correct order relations between any pair of elements except one element.  \n**Then, (1 - Kendall's tau) is proportional to the deviation of the order of the misaligned element.**  \nSince (1 - Kendall's tau) is the value that represents how bad it is from the best score, we can call it the true loss of the task.\n\nThe assumption here is quite simillar to the setting of the competition; the task is to put the markdown cells on the correct positions while we have the correct orders for code cells.  \n**Thus, if we use a model that directly predicts the correct position of the given cells, the absolute difference between the label and the prediction (abs(correct_position - pred_position), i.e., the L1 loss, should represent the true loss of the task well.**","metadata":{}},{"cell_type":"markdown","source":"# Why (1 - Kendall's tau) is proportional to the deviation of the order\nThe definition of Kendall's tau is as follows:\n$$\n\\tau = \\frac{K-L}{\\left( \\substack{n \\\\ 2} \\right)} \\\\\nK = \\#\\{(i,j) ~|~ i,j \\in [1,n],~~ i < j,~~ O_i \\lessgtr O_j,~~ O'_i \\lessgtr O'_j \\} \\\\\nL = \\#\\{(i,j) ~|~ i,j \\in [1,n],~~ i < j,~~ \\neg(O_i \\lessgtr O_j,~~ O'_i \\lessgtr O'_j) \\}\n$$\n\nHere, $n$ is the number of the elements, $O_i$ and $O'_i$ are the orders of the reference and the prediction for i-th element, respectively.  \n$K$ and $L$ are the number of the correctly or incorrectly ordered pairs, respectively.\n\nNow, assume that we have the predicted orders that has the correct order relations between any two elements except one element (e.g., an ordered sequence \"a b d e <font color=\"red\">c</font> f g h\", while the correct order is the alphabetical).  \nThen, $L$ equals to the number of the elements whose positions are between the misaligned position and the correct position of the misaligned element (in the example, \"d\" and \"e\", thus 2). I.e., $L$ equals to the difference of the deviation of the order of the misaligned element.  \nAs well, $K$ decreases by the deviation of the order.\n\n**Thus, Kendall's tau decreases by 2 * the deviation / (nC2) from 1 (the maximum value). In other words, the true loss of the task is proportional to the deviation of the order of the misaligined element.**","metadata":{}},{"cell_type":"markdown","source":"# Example （supplementary material）\nFirst, let's define helper functions.","metadata":{}},{"cell_type":"code","source":"# scoring function\n# this is copied from https://www.kaggle.com/code/ryanholbrook/competition-metric-kendall-tau-correlation\nfrom bisect import bisect\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\n\ndef 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":{"execution":{"iopub.status.busy":"2022-05-16T21:46:24.290622Z","iopub.execute_input":"2022-05-16T21:46:24.290936Z","iopub.status.idle":"2022-05-16T21:46:24.300245Z","shell.execute_reply.started":"2022-05-16T21:46:24.290903Z","shell.execute_reply":"2022-05-16T21:46:24.299247Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"def task_loss(ground_truth, predictions):\n    return 1 - kendall_tau(ground_truth, predictions)","metadata":{"execution":{"iopub.status.busy":"2022-05-16T21:46:25.417247Z","iopub.execute_input":"2022-05-16T21:46:25.417578Z","iopub.status.idle":"2022-05-16T21:46:25.42201Z","shell.execute_reply.started":"2022-05-16T21:46:25.417543Z","shell.execute_reply":"2022-05-16T21:46:25.420829Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We'll refer the deviation of the order of the misaligned element as \"diff\".  \nFor example, if the element is mialigned to the 7th position while the correct position is 2nd, diff=abs(2-7)=5 (obvious!).","metadata":{}},{"cell_type":"code","source":"def get_diff(source_index, dest_index):\n    return abs(source_index - dest_index)\n\nprint(\"diff of 2 => 7 :\", get_diff(2,7))","metadata":{"execution":{"iopub.status.busy":"2022-05-16T21:47:50.381448Z","iopub.execute_input":"2022-05-16T21:47:50.381738Z","iopub.status.idle":"2022-05-16T21:47:50.388422Z","shell.execute_reply.started":"2022-05-16T21:47:50.381691Z","shell.execute_reply":"2022-05-16T21:47:50.387765Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Let's consider the ordered sequence whose correct ordering is alphabetical.\nNow we know the correct orders for all elements except for 'c', thus we need to predict the position of 'c'.","metadata":{}},{"cell_type":"code","source":"correct_sequence = [c for c in \"abcdefghij\"]\ncorrect_index = 2\n\nprint(\"correct sequence   :\", correct_sequence)\nprint(\"given base sequence:\", correct_sequence[:correct_index] + correct_sequence[correct_index+1:])\nprint(\"prediction target  :\", correct_sequence[correct_index])\nprint(\"correct index      :\", correct_index)\n","metadata":{"execution":{"iopub.status.busy":"2022-05-16T21:50:20.551521Z","iopub.execute_input":"2022-05-16T21:50:20.552605Z","iopub.status.idle":"2022-05-16T21:50:20.560451Z","shell.execute_reply.started":"2022-05-16T21:50:20.55254Z","shell.execute_reply":"2022-05-16T21:50:20.559891Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## If we predict the position of 'c' as 3rd, then the score will be as follows:","metadata":{}},{"cell_type":"code","source":"def replace(correct_sequence, source_index, dest_index):\n    out = list(correct_sequence)\n    value = out.pop(source_index)\n    out = out[:dest_index] + [value] + out[dest_index:]\n    return out\n\npred_index = 3\n\ndiff = get_diff(correct_index, pred_index)\nprediction_c_as_3rd = replace(correct_sequence, correct_index, pred_index)\n\nprint(\"pred index         :\", pred_index)\nprint(\"diff(:=abs(pred_index-correct_index))\")\nprint(\"                   :\", diff)\nprint(\"prediction_c_as_3rd:\", prediction_c_as_3rd)\nprint(\"kendall_tau        :\", kendall_tau([correct_sequence], [prediction_c_as_3rd]))\nprint(\"task_loss(:=1-tau) :\", task_loss([correct_sequence], [prediction_c_as_3rd]))\nprint(\"task_loss/diff     :\", task_loss([correct_sequence], [prediction_c_as_3rd])/diff)","metadata":{"execution":{"iopub.status.busy":"2022-05-16T21:51:59.121184Z","iopub.execute_input":"2022-05-16T21:51:59.121444Z","iopub.status.idle":"2022-05-16T21:51:59.132261Z","shell.execute_reply.started":"2022-05-16T21:51:59.121413Z","shell.execute_reply":"2022-05-16T21:51:59.131654Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## When predict as 4th:","metadata":{}},{"cell_type":"code","source":"pred_index = 4\n\ndiff = get_diff(correct_index, pred_index)\nprediction_c_as_4th = replace(correct_sequence, correct_index, pred_index)\n\nprint(\"pred index         :\", pred_index)\nprint(\"diff               :\", diff)\nprint(\"prediction_c_as_4th:\", prediction_c_as_4th)\nprint(\"kendall_tau        :\", kendall_tau([correct_sequence], [prediction_c_as_4th]))\nprint(\"task_loss(:=1-tau) :\", task_loss([correct_sequence], [prediction_c_as_4th]))\nprint(\"task_loss/diff     :\", task_loss([correct_sequence], [prediction_c_as_4th])/diff)","metadata":{"execution":{"iopub.status.busy":"2022-05-16T21:53:27.709172Z","iopub.execute_input":"2022-05-16T21:53:27.710179Z","iopub.status.idle":"2022-05-16T21:53:27.719251Z","shell.execute_reply.started":"2022-05-16T21:53:27.710122Z","shell.execute_reply":"2022-05-16T21:53:27.718752Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## As above, the losses per the deviations of the orders (task_loss/diff) are same!\nThe value is actually always same for any prediction.","metadata":{}},{"cell_type":"code","source":"import pandas as pd\nimport matplotlib.pyplot as plt\nimport seaborn as sns\n\nCORRECT_SEQUENCE = [c for c in \"abcdefghij\"]\nSOURCE_IDX = 2\n\ndef get_scores(source_idx):\n    dests = list()\n    scores = list()\n    losses = list()\n    losses_per_deviations = list()\n\n    for dest_idx in range(len(CORRECT_SEQUENCE)):\n        pred = replace(CORRECT_SEQUENCE, SOURCE_IDX, dest_idx)\n        score = kendall_tau([CORRECT_SEQUENCE], [pred])\n        loss = task_loss([CORRECT_SEQUENCE], [pred]) # or simply (1 - score)\n        loss_per_deviation = loss / max(1, get_diff(SOURCE_IDX, dest_idx)) # avoid deviding by 0\n\n        dests.append(dest_idx)\n        scores.append(score)\n        losses.append(loss)\n        losses_per_deviations.append(loss_per_deviation)\n    return pd.DataFrame({\"dest_idx\":dests, \"kendall's tau\":scores, \"loss\": losses, \"loss_per_deviation\": losses_per_deviations})\n\nig, (ax1, ax2, ax3) = plt.subplots(1, 3, figsize=(15, 5))\ndf = get_scores(SOURCE_IDX)\nsns.scatterplot(x=\"dest_idx\", y=\"loss\", data=df, ax=ax1)\nsns.scatterplot(x=\"dest_idx\", y=\"kendall's tau\", data=df, ax=ax2)\nsns.scatterplot(x=\"dest_idx\", y=\"loss_per_deviation\", data=df, ax=ax3)","metadata":{"execution":{"iopub.status.busy":"2022-05-16T22:15:16.950644Z","iopub.execute_input":"2022-05-16T22:15:16.951518Z","iopub.status.idle":"2022-05-16T22:15:17.506402Z","shell.execute_reply.started":"2022-05-16T22:15:16.951466Z","shell.execute_reply":"2022-05-16T22:15:17.505559Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## We confirmed the linearity of the true loss of the task (1 - Kendall's tau)\n(Again, here we assumed the orders of all elements except one are correct.)\n\n[The baseline notebook](https://www.kaggle.com/code/aerdem4/ai4code-pytorch-distilbert-baseline) predicts the normalized position of the markdown cells, the L1 loss should work well for the model.\n\n## As the first part of this notebook, the coefficient (loss_per_deviation) should equal to $2 ~/~ _n C_2$. Let's check it.","metadata":{}},{"cell_type":"code","source":"# the following value should matches \"loss/diff\" in the above example\ndef n_C_2(n):\n    return (n * (n-1))//2\n\nlen_sequence = len(correct_sequence)\ndecreasing_for_one_rank = 2 / n_C_2(len_sequence)\n\nprint(\"decreasing for one-rank-difference (should be loss/diff):\", decreasing_for_one_rank)","metadata":{"execution":{"iopub.status.busy":"2022-05-16T20:42:20.756183Z","iopub.execute_input":"2022-05-16T20:42:20.756604Z","iopub.status.idle":"2022-05-16T20:42:20.763325Z","shell.execute_reply.started":"2022-05-16T20:42:20.756563Z","shell.execute_reply":"2022-05-16T20:42:20.762397Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"This is it!","metadata":{}},{"cell_type":"markdown","source":"## If you find this helpful, please upvote💕💕💕\nThank you!","metadata":{}},{"cell_type":"code","source":"","metadata":{},"execution_count":null,"outputs":[]}]}