{"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":"# Tryig to hack the LB\n","metadata":{}},{"cell_type":"markdown","source":"## Evaluation code published by Kaggle\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":{"iopub.status.busy":"2022-06-05T17:50:26.518634Z","iopub.execute_input":"2022-06-05T17:50:26.519544Z","iopub.status.idle":"2022-06-05T17:50:26.550144Z","shell.execute_reply.started":"2022-06-05T17:50:26.519384Z","shell.execute_reply":"2022-06-05T17:50:26.549305Z"},"trusted":true},"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":{"iopub.status.busy":"2022-06-05T17:50:26.552011Z","iopub.execute_input":"2022-06-05T17:50:26.552418Z","iopub.status.idle":"2022-06-05T17:50:26.557892Z","shell.execute_reply.started":"2022-06-05T17:50:26.552373Z","shell.execute_reply":"2022-06-05T17:50:26.557046Z"},"trusted":true},"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-06-05T17:50:26.559502Z","iopub.execute_input":"2022-06-05T17:50:26.55991Z","iopub.status.idle":"2022-06-05T17:50:26.572871Z","shell.execute_reply.started":"2022-06-05T17:50:26.559825Z","shell.execute_reply":"2022-06-05T17:50:26.572224Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## My code","metadata":{}},{"cell_type":"markdown","source":"We are going to read a little set of notebooks","metadata":{}},{"cell_type":"code","source":"import pandas as pd\nfrom pathlib import Path\n\ndef read_notebook(path):\n    return (\n        pd.read_json(\n            path,\n            dtype={'cell_type': 'category', 'source': 'str'})\n            .assign(id=path.stem)\n            .rename_axis('cell_id')\n    )\n\ndata_dir = Path('../input/AI4Code')\n\ndf_orders = pd.read_csv(data_dir / 'train_orders.csv',index_col='id',squeeze=True).str.split()\n\npaths_train = list((data_dir / 'train').glob('*.json'))\npaths_train = [x for x in paths_train][:10] # 10 notebooks is enough\nnotebooks_train = [ read_notebook(path) for path in paths_train]\ndf_notebooks = pd.concat(notebooks_train).set_index('id', append=True).swaplevel().sort_index(level='id', sort_remaining=False)","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:26.574416Z","iopub.execute_input":"2022-06-05T17:50:26.574801Z","iopub.status.idle":"2022-06-05T17:50:33.885148Z","shell.execute_reply.started":"2022-06-05T17:50:26.574759Z","shell.execute_reply":"2022-06-05T17:50:33.884203Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Checking the Kendall Tau metric with this set of notebooks","metadata":{}},{"cell_type":"code","source":"df_allcells = df_notebooks.reset_index('cell_id').groupby('id')['cell_id'].apply(list).to_frame().join(df_orders,how='inner')\nkendall_tau(df_allcells.cell_order, df_allcells.cell_id)","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:33.887459Z","iopub.execute_input":"2022-06-05T17:50:33.887951Z","iopub.status.idle":"2022-06-05T17:50:33.961608Z","shell.execute_reply.started":"2022-06-05T17:50:33.887907Z","shell.execute_reply":"2022-06-05T17:50:33.960697Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"That's ok. But, what happens if we filter and use only code cells? Remember that code cells are ordered.","metadata":{}},{"cell_type":"code","source":"df_code = df_notebooks.query('cell_type == \"code\"').reset_index('cell_id').groupby('id')['cell_id'].apply(list)\ndf_testbug = df_code.to_frame().join(df_orders,how='inner')\nkendall_tau(df_testbug.cell_order, df_testbug.cell_id)","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:33.963199Z","iopub.execute_input":"2022-06-05T17:50:33.963786Z","iopub.status.idle":"2022-06-05T17:50:34.00756Z","shell.execute_reply.started":"2022-06-05T17:50:33.963742Z","shell.execute_reply":"2022-06-05T17:50:34.006409Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Oops! kendall_tau function is not checking the length of ground_truth and predictions","metadata":{}},{"cell_type":"code","source":"def my_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        assert len(gt) == len(pred) # <-- CHECK length\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-06-05T17:50:34.010208Z","iopub.execute_input":"2022-06-05T17:50:34.010522Z","iopub.status.idle":"2022-06-05T17:50:34.017262Z","shell.execute_reply.started":"2022-06-05T17:50:34.01048Z","shell.execute_reply":"2022-06-05T17:50:34.016624Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"my_kendall_tau(df_allcells.cell_order, df_allcells.cell_id)","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.020384Z","iopub.execute_input":"2022-06-05T17:50:34.021013Z","iopub.status.idle":"2022-06-05T17:50:34.030887Z","shell.execute_reply.started":"2022-06-05T17:50:34.020968Z","shell.execute_reply":"2022-06-05T17:50:34.030218Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"try:\n    my_kendall_tau(df_testbug.cell_order, df_testbug.cell_id)\nexcept:\n    print(\"OK!\")\n","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.032081Z","iopub.execute_input":"2022-06-05T17:50:34.033337Z","iopub.status.idle":"2022-06-05T17:50:34.044206Z","shell.execute_reply.started":"2022-06-05T17:50:34.03329Z","shell.execute_reply":"2022-06-05T17:50:34.043281Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We check this issue against LB and the submission failed. See [this thread](https://www.kaggle.com/code/ryanholbrook/competition-metric-kendall-tau-correlation/comments#1810701)","metadata":{}},{"cell_type":"markdown","source":"But, what happes if we repeat the last code cell until end? Like this:","metadata":{}},{"cell_type":"code","source":"my_kendall_tau([['c1','c2','c3','m1','m2','m3']],[['c1','c2','c3','c3','c3','c3']])","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.045843Z","iopub.execute_input":"2022-06-05T17:50:34.046339Z","iopub.status.idle":"2022-06-05T17:50:34.055923Z","shell.execute_reply.started":"2022-06-05T17:50:34.046292Z","shell.execute_reply":"2022-06-05T17:50:34.054783Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"paths_test = list((data_dir / 'test').glob('*.json'))\nnotebooks_test = [ read_notebook(path) for path in paths_test]\ndf_notebooks = pd.concat(notebooks_test).set_index('id', append=True).swaplevel().sort_index(level='id', sort_remaining=False)\ndf_code = df_notebooks.query('cell_type == \"code\"').reset_index('cell_id').groupby('id')['cell_id'].apply(list).reset_index()\ndf_ncell = df_notebooks.groupby('id').source.count().rename('count').reset_index()\ndf_code['count'] = df_ncell['count']\ndf_code['cell_padded'] = df_code.apply(lambda r: r.cell_id + [r.cell_id[-1]] * (r['count'] - len(r.cell_id)), axis=1)\ndf_code['cell_order'] = df_code.cell_padded.apply(lambda x: \" \".join(x))","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.058338Z","iopub.execute_input":"2022-06-05T17:50:34.059323Z","iopub.status.idle":"2022-06-05T17:50:34.154205Z","shell.execute_reply.started":"2022-06-05T17:50:34.059277Z","shell.execute_reply":"2022-06-05T17:50:34.15354Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission = df_code[['id','cell_order']]\nsubmission","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.155764Z","iopub.execute_input":"2022-06-05T17:50:34.156305Z","iopub.status.idle":"2022-06-05T17:50:34.174142Z","shell.execute_reply.started":"2022-06-05T17:50:34.156259Z","shell.execute_reply":"2022-06-05T17:50:34.173241Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Submission **failed** again!!\n\nThe metric works fine in LB","metadata":{}},{"cell_type":"markdown","source":"uhmm!! after my last regular submission, I have the intuition that Kaggle is filtering perfect submission. I'm going to force a litle error in submission file.","metadata":{}},{"cell_type":"code","source":"df = df_notebooks.reset_index('cell_id').groupby('id')['cell_id'].apply(list).reset_index()\nsubmission.iloc[-1].cell_order = \" \".join(df.iloc[-1].cell_id)\nsubmission","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:55:51.245001Z","iopub.execute_input":"2022-06-05T17:55:51.245537Z","iopub.status.idle":"2022-06-05T17:55:51.262355Z","shell.execute_reply.started":"2022-06-05T17:55:51.245495Z","shell.execute_reply":"2022-06-05T17:55:51.261357Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"submission.to_csv(\"submission.csv\", index=False)","metadata":{"execution":{"iopub.status.busy":"2022-06-05T17:50:34.175477Z","iopub.execute_input":"2022-06-05T17:50:34.17585Z","iopub.status.idle":"2022-06-05T17:50:34.182377Z","shell.execute_reply.started":"2022-06-05T17:50:34.175818Z","shell.execute_reply":"2022-06-05T17:50:34.181598Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Submission **failed** again!!","metadata":{}}]}