{"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":"# Introduction\n\nThis is a fun little baselining experiment, to get a feel for the competition and the Kendall-tau metric.\n\n+ We'll create a **very simple** random generative model of notebook ranks, perturbed in the fashion that they are presented to us in the training data.\n+ We'll then consider what happens when we take different **markdown cell merging strategies** in order to make our predictions. \n\n**We'll run 3 experiments:**\n\n1. Predict the orders unchanged from the cell orders we receive in the data.\n2. Randomly order the markdown cells and interleave amongst the ordered code cells.\n3. Correctly order the markdown cells and interleave amongst the ordered code cells.\n","metadata":{}},{"cell_type":"code","source":"import pickle\nimport numpy as np\nimport pandas as pd\nimport plotly.express as px\nfrom scipy import stats","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-28T21:07:21.135628Z","iopub.execute_input":"2022-05-28T21:07:21.136113Z","iopub.status.idle":"2022-05-28T21:07:23.384477Z","shell.execute_reply.started":"2022-05-28T21:07:21.136024Z","shell.execute_reply":"2022-05-28T21:07:23.383650Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# The Kendall-tau (KT) Metric\n\nFirst, a couple of definitions from the [organisers' notebook](https://www.kaggle.com/code/ryanholbrook/competition-metric-kendall-tau-correlation):\n\n+ The Kendall tau correlation is: $K = 1 - 4 \\frac{\\sum_i S_{i}}{\\sum_i n_i(n_i - 1)}$ where \\\\(S_i\\\\) is the number of inversions in the predicted ranks and \\\\(n_i\\\\) is the number of cells for notebook \\\\(i\\\\),\n\nand where:\n\n+ A pair \\\\(i, j\\\\) of indices is called an **inversion** within a numeric sequence \\\\(A\\\\) when \\\\(i < j\\\\) but \\\\(A[i] > A[j]\\\\). The number of swaps needed to correctly sort the predictions is equivalent to the number of inversions in its ranking of the cells relative to the ground-truth ranking.","metadata":{}},{"cell_type":"code","source":"from bisect import bisect\n\ndef count_inversions(a):\n    inversions = 0\n    sorted_so_far = []\n    for i, u in enumerate(a):\n        j = bisect(sorted_so_far, u)\n        inversions += i - j\n        sorted_so_far.insert(j, u)\n    return inversions\n\n\ndef kendall_tau(ground_truth, predictions):\n    total_inversions = 0 \n    total_2max = 0\n    for gt, pred in zip(ground_truth, predictions):\n        ranks = [gt.index(x) for x in pred]\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":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-28T21:07:26.492573Z","iopub.execute_input":"2022-05-28T21:07:26.492874Z","iopub.status.idle":"2022-05-28T21:07:26.501511Z","shell.execute_reply.started":"2022-05-28T21:07:26.492845Z","shell.execute_reply":"2022-05-28T21:07:26.500556Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Train Data Statistics\n\nI processed the training data earlier - it's a list consisting of the notebook ranks and their cell types, with 0 indicating code and 1 indicating markdown. Note - all notebooks have at least one markdown cell and at least one code cell.","metadata":{}},{"cell_type":"code","source":"with open('../input/ai4code-corpus-ranks/train_ranks.pkl', 'rb') as f:\n    train = pickle.load(f)","metadata":{"execution":{"iopub.status.busy":"2022-05-28T21:07:28.517408Z","iopub.execute_input":"2022-05-28T21:07:28.518012Z","iopub.status.idle":"2022-05-28T21:07:30.281162Z","shell.execute_reply.started":"2022-05-28T21:07:28.517949Z","shell.execute_reply":"2022-05-28T21:07:30.280197Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Here's an example \"notebook\":","metadata":{}},{"cell_type":"code","source":"print(\"The notebook's cell ranks are:\", train[2][0], sep=\"\\n\")\nprint(\"The notebook's cell types are:\", train[2][1], sep=\"\\n\")","metadata":{"execution":{"iopub.status.busy":"2022-05-28T21:07:30.282630Z","iopub.execute_input":"2022-05-28T21:07:30.282862Z","iopub.status.idle":"2022-05-28T21:07:30.288322Z","shell.execute_reply.started":"2022-05-28T21:07:30.282835Z","shell.execute_reply":"2022-05-28T21:07:30.287329Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"train_length_df = pd.DataFrame({\n    \"nb_lengths\":[len(l[0]) for l in train],\n    \"md_lengths\":[sum(l[1]) for l in train]\n})\n\npx.histogram(train_length_df, x=\"nb_lengths\", nbins=500,\n             title=\"Train data distribution of number of cells\",\n             color_discrete_sequence=['purple'],\n             template='plotly_white')","metadata":{"execution":{"iopub.status.busy":"2022-05-28T21:09:31.197278Z","iopub.execute_input":"2022-05-28T21:09:31.197618Z","iopub.status.idle":"2022-05-28T21:09:31.987474Z","shell.execute_reply.started":"2022-05-28T21:09:31.197587Z","shell.execute_reply":"2022-05-28T21:09:31.986425Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"px.histogram(train_length_df, x=\"md_lengths\", nbins=500,\n             title=\"Train data distribution of number of markdown cells\",\n             color_discrete_sequence=['purple'],\n             template='plotly_white')","metadata":{"execution":{"iopub.status.busy":"2022-05-28T21:09:35.852469Z","iopub.execute_input":"2022-05-28T21:09:35.852736Z","iopub.status.idle":"2022-05-28T21:09:36.756173Z","shell.execute_reply.started":"2022-05-28T21:09:35.852709Z","shell.execute_reply":"2022-05-28T21:09:36.755268Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"train_length_df['md_proportions'] = train_length_df['md_lengths']/ train_length_df['nb_lengths'] \n\npx.histogram(train_length_df, x=\"md_proportions\", nbins=500,\n             title=\"Train data distribution of proportion of markdown cells\",\n             color_discrete_sequence=['purple'],\n             template='plotly_white')","metadata":{"execution":{"iopub.status.busy":"2022-05-28T21:11:19.021914Z","iopub.execute_input":"2022-05-28T21:11:19.022209Z","iopub.status.idle":"2022-05-28T21:11:19.653606Z","shell.execute_reply.started":"2022-05-28T21:11:19.022173Z","shell.execute_reply":"2022-05-28T21:11:19.652632Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's pull out some simple summary statistics to use with our generative corpus:","metadata":{}},{"cell_type":"code","source":"train_ncell = train_length_df.nb_lengths.mean()\ntrain_ratio = (train_length_df.md_lengths / train_length_df.nb_lengths).mean()","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:27:00.818308Z","iopub.execute_input":"2022-05-21T20:27:00.818791Z","iopub.status.idle":"2022-05-21T20:27:00.827047Z","shell.execute_reply.started":"2022-05-21T20:27:00.818751Z","shell.execute_reply":"2022-05-21T20:27:00.825845Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Corpus Generating Model\n\nLet's define a simple corpus-generating model! We'll make it hierarchical to add a bit of spice. We'll try and use the train set sample statistics for the parameters of the model. As can be seen below, the generative model doesn't fit the shape of the train distribution well yet. We could try harder (and could even set up a nice Bayesian model with priors), but... maybe later!","metadata":{}},{"cell_type":"code","source":"rng = np.random.default_rng(seed=200522)","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:29:56.000244Z","iopub.execute_input":"2022-05-21T20:29:56.000624Z","iopub.status.idle":"2022-05-21T20:29:56.00692Z","shell.execute_reply.started":"2022-05-21T20:29:56.000584Z","shell.execute_reply":"2022-05-21T20:29:56.005817Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"First, we'll make a \"notebook\" generating function which outputs:\n\n+ the original cell ranks\n+ the perturbed cell ranks* \n+ a list of the code cells\n+ a list of the markdown cells\n\n\\*with code cells in the correct order, as we'd receive in the dataset","metadata":{}},{"cell_type":"code","source":"def generate_notebook(n_cells, n_markdown=None, default_frac=0.2):\n    original_nb = np.arange(n_cells)\n    if not n_markdown:\n        n_markdown = np.floor(n_cells * default_frac).astype('int')\n    markdown_cells = rng.choice(original_nb, n_markdown, replace=False)\n    code_cells = np.delete(original_nb, markdown_cells)\n    perturbed_nb = np.concatenate([code_cells, markdown_cells])\n    notebook = {\n        'original' :  list(original_nb),\n        'perturbed':  list(perturbed_nb),\n        'code'     :  list(code_cells),\n        'markdown' :  list(markdown_cells)\n    }\n    return notebook","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:29:56.988046Z","iopub.execute_input":"2022-05-21T20:29:56.988409Z","iopub.status.idle":"2022-05-21T20:29:56.99683Z","shell.execute_reply.started":"2022-05-21T20:29:56.988357Z","shell.execute_reply":"2022-05-21T20:29:56.995692Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now we can generate a corpus of notebooks with randomly generated lengths and markdown cell proportions:","metadata":{}},{"cell_type":"code","source":"def generate_corpus(n_docs, mu=30, prob_md=0.2):\n    original_corpus = []\n    perturbed_corpus = []\n    markdown_corpus = []\n    code_corpus = []\n    for i in range(n_docs):\n        mu_i = rng.poisson(mu) + 2\n        n_md = rng.binomial(mu_i, prob_md)\n        nb_i = generate_notebook(mu_i, n_md)\n        original_corpus.append(nb_i['original'])\n        perturbed_corpus.append(nb_i['perturbed'])\n        code_corpus.append(nb_i['code'])\n        markdown_corpus.append(nb_i['markdown'])\n    corpus = {'original' : original_corpus,\n              'perturbed': perturbed_corpus,\n              'code'     : code_corpus,\n              'markdown' : markdown_corpus}\n    return corpus","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:29:57.780525Z","iopub.execute_input":"2022-05-21T20:29:57.78153Z","iopub.status.idle":"2022-05-21T20:29:57.790656Z","shell.execute_reply.started":"2022-05-21T20:29:57.781476Z","shell.execute_reply":"2022-05-21T20:29:57.789489Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Here's a sample \"notebook\" of length 15 with ~20% markdown cells","metadata":{}},{"cell_type":"code","source":"sample_nb = generate_notebook(15)\nprint(sample_nb, sep='\\n')","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:29:59.058199Z","iopub.execute_input":"2022-05-21T20:29:59.058529Z","iopub.status.idle":"2022-05-21T20:29:59.067229Z","shell.execute_reply.started":"2022-05-21T20:29:59.058491Z","shell.execute_reply":"2022-05-21T20:29:59.065926Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now let's generate a nice big corpus:","metadata":{}},{"cell_type":"code","source":"corpus = generate_corpus(100000,\n                         mu = train_ncell,\n                         prob_md = train_ratio)","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:30:58.647879Z","iopub.execute_input":"2022-05-21T20:30:58.64818Z","iopub.status.idle":"2022-05-21T20:31:09.75736Z","shell.execute_reply.started":"2022-05-21T20:30:58.648148Z","shell.execute_reply":"2022-05-21T20:31:09.756463Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Experiments","metadata":{}},{"cell_type":"markdown","source":"## Summary of the generated corpus\n\nRight, so we've generated a corpus. First, let's take a look at the distribution of generated notebook lengths:","metadata":{}},{"cell_type":"code","source":"df = pd.DataFrame({\n    \"nb_lengths\":[len(l) for l in corpus['original']],\n    \"md_lengths\":[len(l) for l in corpus['markdown']]\n})\n\npx.histogram(df, x=\"nb_lengths\", nbins=50,\n             title=\"Sample distribution of notebook lengths for the generated corpus\")","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:31:12.619945Z","iopub.execute_input":"2022-05-21T20:31:12.620251Z","iopub.status.idle":"2022-05-21T20:31:13.218182Z","shell.execute_reply.started":"2022-05-21T20:31:12.620219Z","shell.execute_reply":"2022-05-21T20:31:13.21735Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"px.histogram(df, x=\"md_lengths\", nbins=50,\n             title=\"Sample distribution of markdown cell lengths for the generated corpus\")","metadata":{"execution":{"iopub.status.busy":"2022-05-21T20:30:26.891771Z","iopub.execute_input":"2022-05-21T20:30:26.892179Z","iopub.status.idle":"2022-05-21T20:30:27.346772Z","shell.execute_reply.started":"2022-05-21T20:30:26.892147Z","shell.execute_reply":"2022-05-21T20:30:27.345574Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Experiment 1 - What is the KT for a naive submission?\n\nFor this experiment we just predict the cell order as we find it. Our baseline for this corpus is **KT = 0.4490**.","metadata":{}},{"cell_type":"code","source":"def compute_kendall_stats(ground_truth, predictions):\n    kt_pt = []\n    for orig, pert in zip(ground_truth, predictions):\n        kt_pt.append(kendall_tau([orig], [pert]))\n    kt = kendall_tau(ground_truth, predictions)\n    return kt, kt_pt","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:41:10.630195Z","iopub.execute_input":"2022-05-21T20:41:10.632112Z","iopub.status.idle":"2022-05-21T20:41:10.642195Z","shell.execute_reply.started":"2022-05-21T20:41:10.632048Z","shell.execute_reply":"2022-05-21T20:41:10.640828Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"predictions1 = corpus['perturbed']\nkendall_stats_1 = compute_kendall_stats(corpus['original'], predictions1)\n\nprint(f\"Kendall-tau for the corpus is:\\t\",\n      f\"{kendall_stats_1[0]}\")\n#print(f\"{stats.describe(kendall_stats_1[1])}\")\n\ndf = pd.DataFrame({\"kendall_tau\": kendall_stats_1[1]})\npx.histogram(df, x=\"kendall_tau\", nbins=50,\n             title=\"Sample distribution of pointwise Kendall-tau for experiment 1\")","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:41:11.354696Z","iopub.execute_input":"2022-05-21T20:41:11.355067Z","iopub.status.idle":"2022-05-21T20:41:31.124439Z","shell.execute_reply.started":"2022-05-21T20:41:11.355034Z","shell.execute_reply":"2022-05-21T20:41:31.12319Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Experiment 2 - What happens to the KT if we randomly interleave the *unordered* markdown cells?","metadata":{}},{"cell_type":"markdown","source":"First we have to make our predictions - note, this strategy knows **nothing** about the actual contents of the cells, just what type they are! Even so, KT has jumped up to **0.5967**.","metadata":{}},{"cell_type":"code","source":"predictions2 = []\nfor i, nb in enumerate(corpus['original']):\n    code_positions = np.array(corpus['code'][i]) + 0.5\n    \n    md_positions = rng.choice(\n        np.arange(len(corpus['original'][i])+1),\n        len(corpus['markdown'][i]),\n        replace=False\n    )\n    nb_ranks = np.concatenate([code_positions, md_positions])\n    \n    pred = np.array(corpus['perturbed'][i])[nb_ranks.argsort()]\n    predictions2.append(pred)","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:41:39.871218Z","iopub.execute_input":"2022-05-21T20:41:39.871546Z","iopub.status.idle":"2022-05-21T20:41:44.856164Z","shell.execute_reply.started":"2022-05-21T20:41:39.871511Z","shell.execute_reply":"2022-05-21T20:41:44.854724Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"kendall_stats_2 = compute_kendall_stats(corpus['original'], predictions2)\n\nprint(f\"Kendall-tau for the corpus is:\\t\",\n      f\"{kendall_stats_2[0]}\")\n#print(f\"{stats.describe(kendall_stats_2[1])}\")\n\ndf = pd.DataFrame({\"kendall_tau\": kendall_stats_2[1]})\npx.histogram(df, x=\"kendall_tau\", nbins=50,\n             title=\"Sample distribution of pointwise Kendall-tau for experiment 2\")","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:41:44.85816Z","iopub.execute_input":"2022-05-21T20:41:44.858468Z","iopub.status.idle":"2022-05-21T20:42:06.022364Z","shell.execute_reply.started":"2022-05-21T20:41:44.858434Z","shell.execute_reply":"2022-05-21T20:42:06.020936Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Experiment 3 - What happens to KT if we randomly interleave *correctly* ordered markdown cells?\n\nWe'll have to do some work in order to correctly order the code cells - but look! It **really pays off** in this experiment! KT has rocketed up to **0.9205**.","metadata":{}},{"cell_type":"code","source":"predictions3 = []\nfor i, nb in enumerate(corpus['original']):\n    code_positions = np.array(corpus['code'][i]) + 0.5\n    \n    md_positions = rng.choice(\n        np.arange(len(corpus['original'][i])+1),\n        len(corpus['markdown'][i]),\n        replace=False\n    )\n    \n    nb_ranks = np.concatenate([code_positions, sorted(md_positions)])\n    \n    pred = np.concatenate([ corpus['code'][i], sorted(corpus['markdown'][i]) ])[nb_ranks.argsort()]\n    predictions3.append(pred)","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:42:14.447934Z","iopub.execute_input":"2022-05-21T20:42:14.448548Z","iopub.status.idle":"2022-05-21T20:42:21.138628Z","shell.execute_reply.started":"2022-05-21T20:42:14.448508Z","shell.execute_reply":"2022-05-21T20:42:21.137355Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"kendall_stats_3 = compute_kendall_stats(corpus['original'], predictions3)\n\nprint(f\"Kendall-tau for the corpus is:\\t\",\n      f\"{kendall_stats_3[0]}\")\n#print(f\"{stats.describe(kendall_stats_3[1])}\")\n\ndf = pd.DataFrame({\"kendall_tau\": kendall_stats_3[1]})\npx.histogram(df, x=\"kendall_tau\", nbins=70,\n             title=\"Sample distribution of pointwise Kendall-tau for experiment 3\")","metadata":{"_kg_hide-input":true,"execution":{"iopub.status.busy":"2022-05-21T20:42:21.140447Z","iopub.execute_input":"2022-05-21T20:42:21.14098Z","iopub.status.idle":"2022-05-21T20:42:42.089159Z","shell.execute_reply.started":"2022-05-21T20:42:21.140944Z","shell.execute_reply":"2022-05-21T20:42:42.087815Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Summary\n\n1. We've constructed a toy notebook-corpus-generating distribution. \n2. Using a corpus that we sampled from the distribution, we've run three experiments:\n    + Experiment 1: 'dummy prediction' predict the cell orders as they appear in the data. (**KT = 0.4490**)\n    + Experiment 2: randomly interleave the unordered markdown cells amongst the ordered code cells (**KT = 0.5967**)\n    + Experiment 3: randomly interleave the ordered markdown cells amongst the ordered code cells (**KT = 0.9205**)\n    \n**Hope this takes you somewhere interesting!**","metadata":{}}]}