{"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":"A co-visitation matrix is essentially an \"analog\" approximation to matrix factorization. But matrix factorization has a lot of advantages as compared to co-visitation matrices. First of all, it can make better use of data -- it operates on the notion of similarity between categories. This is the jump from unigram/bigram/trigram models to word2vec in NLP.\n\nNow train a matrix factorization model and replace the co-visitation matrices with it. To streamline the work, we will use data in `parquet` format.","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19"}},{"cell_type":"markdown","source":"# Data Preprocessing","metadata":{}},{"cell_type":"code","source":"!pip install polars\n\nimport polars as pl\n\ntrain = pl.read_parquet('../input/otto-full-optimized-memory-footprint/train.parquet')\ntest = pl.read_parquet('../input/otto-full-optimized-memory-footprint/test.parquet')","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:03:53.154538Z","iopub.execute_input":"2023-01-05T05:03:53.155012Z","iopub.status.idle":"2023-01-05T05:04:21.854898Z","shell.execute_reply.started":"2023-01-05T05:03:53.154917Z","shell.execute_reply":"2023-01-05T05:04:21.853847Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We need to create `aid-aid` pairs to train our matrix factorization model.\n\nLet's us grab the pairs both from the train and test set.","metadata":{}},{"cell_type":"code","source":"%%time\n\ntrain_pairs = (pl.concat([train, test])\n    .groupby('session').agg([\n        pl.col('aid'),\n        pl.col('aid').shift(-1).alias('aid_next')\n    ])\n    .explode(['aid', 'aid_next'])\n    .drop_nulls()\n)[['aid', 'aid_next']]","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:21.856478Z","iopub.execute_input":"2023-01-05T05:04:21.857371Z","iopub.status.idle":"2023-01-05T05:04:56.031127Z","shell.execute_reply.started":"2023-01-05T05:04:21.857331Z","shell.execute_reply":"2023-01-05T05:04:56.030067Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"train_pairs.shape[0] / 1_000_000","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:56.034052Z","iopub.execute_input":"2023-01-05T05:04:56.034409Z","iopub.status.idle":"2023-01-05T05:04:56.043006Z","shell.execute_reply.started":"2023-01-05T05:04:56.034377Z","shell.execute_reply":"2023-01-05T05:04:56.042207Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"That is 209 million pairs created in 40 seconds without running out of RAM.","metadata":{}},{"cell_type":"code","source":"train_pairs.head()","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:56.045272Z","iopub.execute_input":"2023-01-05T05:04:56.045597Z","iopub.status.idle":"2023-01-05T05:04:56.061404Z","shell.execute_reply.started":"2023-01-05T05:04:56.045568Z","shell.execute_reply":"2023-01-05T05:04:56.060107Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's see what is the cardinality of our aids -- we will need this to create the embedding layer.","metadata":{}},{"cell_type":"code","source":"cardinality_aids = max(train_pairs['aid'].max(), train_pairs['aid_next'].max())\ncardinality_aids","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:56.062986Z","iopub.execute_input":"2023-01-05T05:04:56.063455Z","iopub.status.idle":"2023-01-05T05:04:56.227390Z","shell.execute_reply.started":"2023-01-05T05:04:56.063421Z","shell.execute_reply":"2023-01-05T05:04:56.226302Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We will have up to `1855602` -- our matrix factorization model will be able to handle this.\n\nLet's construct a `PyTorch` dataset and `dataloader`.","metadata":{}},{"cell_type":"code","source":"import torch\nfrom torch import nn\nfrom torch.utils.data import Dataset, DataLoader\n\nclass ClicksDataset(Dataset):\n    def __init__(self, pairs):\n        self.aid1 = pairs['aid'].to_numpy()\n        self.aid2 = pairs['aid_next'].to_numpy()\n    def __getitem__(self, idx):\n        aid1 = self.aid1[idx]\n        aid2 = self.aid2[idx]\n        return [aid1, aid2]\n    def __len__(self):\n        return len(self.aid1)\n\ntrain_ds = ClicksDataset(train_pairs[:-10_000_000])\nvalid_ds = ClicksDataset(train_pairs[10_000_000:])","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:56.228947Z","iopub.execute_input":"2023-01-05T05:04:56.229320Z","iopub.status.idle":"2023-01-05T05:04:58.230342Z","shell.execute_reply.started":"2023-01-05T05:04:56.229288Z","shell.execute_reply":"2023-01-05T05:04:58.229088Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"However, the Pytorch dataloader takes a lot of time to load data. The reason this is taking so long is that indexing into the the arrays and collating results into batches is very computationally expensive.\n\nThanks to other kagglers' work, we will use a brand new [Merlin Dataloader](https://github.com/NVIDIA-Merlin/dataloader). But, alas, Kaggle gives only 13 GB of RAM on a kernel with a GPU, and that wouldn't allow us to process our dataset. Now we will try how far we can go with CPU only.","metadata":{}},{"cell_type":"code","source":"!pip install merlin-dataloader==0.0.2","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:04:58.242267Z","iopub.execute_input":"2023-01-05T05:04:58.242717Z","iopub.status.idle":"2023-01-05T05:06:36.174048Z","shell.execute_reply.started":"2023-01-05T05:04:58.242672Z","shell.execute_reply":"2023-01-05T05:06:36.172586Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from merlin.loader.torch import Loader ","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:36.175889Z","iopub.execute_input":"2023-01-05T05:06:36.176631Z","iopub.status.idle":"2023-01-05T05:06:37.796593Z","shell.execute_reply.started":"2023-01-05T05:06:36.176591Z","shell.execute_reply":"2023-01-05T05:06:37.795469Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We can read data directly from the disk.\n\nWrite our datasets to disk.","metadata":{}},{"cell_type":"code","source":"train_pairs[:-10_000_000].to_pandas().to_parquet('train_pairs.parquet')\ntrain_pairs[-10_000_000:].to_pandas().to_parquet('valid_pairs.parquet')","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:37.800877Z","iopub.execute_input":"2023-01-05T05:06:37.801216Z","iopub.status.idle":"2023-01-05T05:06:47.478988Z","shell.execute_reply.started":"2023-01-05T05:06:37.801187Z","shell.execute_reply":"2023-01-05T05:06:47.477960Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from merlin.loader.torch import Loader \nfrom merlin.io import Dataset\n\ntrain_ds = Dataset('train_pairs.parquet')\ntrain_dl_merlin = Loader(train_ds, 65536, True)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:47.480393Z","iopub.execute_input":"2023-01-05T05:06:47.480881Z","iopub.status.idle":"2023-01-05T05:06:49.165121Z","shell.execute_reply.started":"2023-01-05T05:06:47.480851Z","shell.execute_reply":"2023-01-05T05:06:49.164246Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"class MatrixFactorization(nn.Module):\n    def __init__(self, n_aids, n_factors):\n        super().__init__()\n        self.aid_factors = nn.Embedding(n_aids, n_factors, sparse=True)\n        \n    def forward(self, aid1, aid2):\n        aid1 = self.aid_factors(aid1)\n        aid2 = self.aid_factors(aid2)\n        \n        return (aid1 * aid2).sum(dim=1)\n    \nclass AverageMeter(object):\n    \"\"\"Computes and stores the average and current value\"\"\"\n    def __init__(self, name, fmt=':f'):\n        self.name = name\n        self.fmt = fmt\n        self.reset()\n\n    def reset(self):\n        self.val = 0\n        self.avg = 0\n        self.sum = 0\n        self.count = 0\n\n    def update(self, val, n=1):\n        self.val = val\n        self.sum += val * n\n        self.count += n\n        self.avg = self.sum / self.count\n\n    def __str__(self):\n        fmtstr = '{name} {val' + self.fmt + '} ({avg' + self.fmt + '})'\n        return fmtstr.format(**self.__dict__)\n\nvalid_ds = Dataset('valid_pairs.parquet')\nvalid_dl_merlin = Loader(valid_ds, 65536, True)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:49.166382Z","iopub.execute_input":"2023-01-05T05:06:49.167298Z","iopub.status.idle":"2023-01-05T05:06:49.391509Z","shell.execute_reply.started":"2023-01-05T05:06:49.167262Z","shell.execute_reply":"2023-01-05T05:06:49.390665Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from torch.optim import SparseAdam\n\nnum_epochs=3\nlr=0.08\n\nmodel = MatrixFactorization(cardinality_aids+1, 32)\noptimizer = SparseAdam(model.parameters(), lr=lr)\ncriterion = nn.BCEWithLogitsLoss()","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:49.392602Z","iopub.execute_input":"2023-01-05T05:06:49.393698Z","iopub.status.idle":"2023-01-05T05:06:50.148493Z","shell.execute_reply.started":"2023-01-05T05:06:49.393663Z","shell.execute_reply":"2023-01-05T05:06:50.147116Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\nfor epoch in range(num_epochs):\n    for batch, _ in train_dl_merlin:\n        model.train()\n        losses = AverageMeter('Loss', ':.4e')\n            \n        aid1, aid2 = batch['aid'], batch['aid_next']\n        output_pos = model(aid1, aid2)\n        output_neg = model(aid1, aid2[torch.randperm(aid2.shape[0])])\n        \n        output = torch.cat([output_pos, output_neg])\n        targets = torch.cat([torch.ones_like(output_pos), torch.zeros_like(output_pos)])\n        loss = criterion(output, targets)\n        losses.update(loss.item())\n        \n        optimizer.zero_grad()\n        loss.backward()\n        optimizer.step()\n        \n    model.eval()\n    \n    with torch.no_grad():\n        accuracy = AverageMeter('accuracy')\n        for batch, _ in valid_dl_merlin:\n            aid1, aid2 = batch['aid'], batch['aid_next']\n            output_pos = model(aid1, aid2)\n            output_neg = model(aid1, aid2[torch.randperm(aid2.shape[0])])\n            accuracy_batch = torch.cat([output_pos.sigmoid() > 0.5, output_neg.sigmoid() < 0.5]).float().mean()\n            accuracy.update(accuracy_batch, aid1.shape[0])\n            \n    print(f'{epoch+1:02d}: * TrainLoss {losses.avg:.3f}  * Accuracy {accuracy.avg:.3f}')","metadata":{"execution":{"iopub.status.busy":"2023-01-05T05:06:50.153732Z","iopub.execute_input":"2023-01-05T05:06:50.154348Z","iopub.status.idle":"2023-01-05T06:33:36.798618Z","shell.execute_reply.started":"2023-01-05T05:06:50.154279Z","shell.execute_reply":"2023-01-05T06:33:36.797089Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Grab the embeddings to get vector representation matrix!","metadata":{}},{"cell_type":"code","source":"embeddings = model.aid_factors.weight.detach().numpy()","metadata":{"execution":{"iopub.status.busy":"2023-01-05T06:33:36.801858Z","iopub.execute_input":"2023-01-05T06:33:36.802835Z","iopub.status.idle":"2023-01-05T06:33:36.810011Z","shell.execute_reply.started":"2023-01-05T06:33:36.802783Z","shell.execute_reply":"2023-01-05T06:33:36.809157Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"And construct create the index for approximate nearest neighbor search.","metadata":{}},{"cell_type":"code","source":"%%time\n\nfrom annoy import AnnoyIndex\n\nindex = AnnoyIndex(32, 'euclidean')\nfor i, v in enumerate(embeddings):\n    index.add_item(i, v)\n    \nindex.build(10)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T06:33:36.811421Z","iopub.execute_input":"2023-01-05T06:33:36.812444Z","iopub.status.idle":"2023-01-05T06:33:59.790344Z","shell.execute_reply.started":"2023-01-05T06:33:36.812351Z","shell.execute_reply":"2023-01-05T06:33:59.789170Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Now for any `aid`, we can find its nearest neighbor!","metadata":{}},{"cell_type":"code","source":"index.get_nns_by_item(123, 10)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T06:33:59.791806Z","iopub.execute_input":"2023-01-05T06:33:59.792201Z","iopub.status.idle":"2023-01-05T06:33:59.799942Z","shell.execute_reply.started":"2023-01-05T06:33:59.792167Z","shell.execute_reply":"2023-01-05T06:33:59.798616Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Create a submission now!","metadata":{}},{"cell_type":"code","source":"import pandas as pd\nimport numpy as np\n\nfrom collections import defaultdict\n\nsample_sub = pd.read_csv('../input/otto-recommender-system//sample_submission.csv')\n\nsession_types = ['clicks', 'carts', 'orders']\ntest_session_AIDs = test.to_pandas().reset_index(drop=True).groupby('session')['aid'].apply(list)\ntest_session_types = test.to_pandas().reset_index(drop=True).groupby('session')['type'].apply(list)\n\nlabels = []\n\ntype_weight_multipliers = {0: 0.5, 1: 9, 2: 0.5}\nfor AIDs, types in zip(test_session_AIDs, test_session_types):\n    if len(AIDs) >= 20:\n        # if we have enough aids (over equals 20) we don't need to look for candidates! we just use the old logic\n        weights=np.logspace(0.1,1,len(AIDs),base=2, endpoint=True)-1\n        aids_temp=defaultdict(lambda: 0)\n        for aid,w,t in zip(AIDs,weights,types): \n            aids_temp[aid]+= w * type_weight_multipliers[t]\n            \n        sorted_aids=[k for k, v in sorted(aids_temp.items(), key=lambda item: -item[1])]\n        labels.append(sorted_aids[:20])\n    else:\n        # here we don't have 20 aids to output -- we will use approximate nearest neighbor search and our embeddings\n        # to generate candidates!\n        AIDs = list(dict.fromkeys(AIDs[::-1]))\n        \n        # let's grab the most recent aid\n        most_recent_aid = AIDs[0]\n        \n        # and look for some neighbors of the most recent aid\n        # just like what we have done in item2vec\n        nns = index.get_nns_by_item(most_recent_aid, 21)[1:]\n                        \n        labels.append((AIDs+nns)[:20])","metadata":{"execution":{"iopub.status.busy":"2023-01-05T06:33:59.801907Z","iopub.execute_input":"2023-01-05T06:33:59.802630Z","iopub.status.idle":"2023-01-05T06:37:25.673960Z","shell.execute_reply.started":"2023-01-05T06:33:59.802597Z","shell.execute_reply":"2023-01-05T06:37:25.672951Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Pull it all together and write to a file,","metadata":{}},{"cell_type":"code","source":"labels_as_strings = [' '.join([str(l) for l in lls]) for lls in labels]\n\npredictions = pd.DataFrame(data={'session_type': test_session_AIDs.index, 'labels': labels_as_strings})\n\nprediction_dfs = []\n\nfor st in session_types:\n    modified_predictions = predictions.copy()\n    modified_predictions.session_type = modified_predictions.session_type.astype('str') + f'_{st}'\n    prediction_dfs.append(modified_predictions)\n\nsubmission = pd.concat(prediction_dfs).reset_index(drop=True)\nsubmission.to_csv('submission.csv', index=False)","metadata":{"execution":{"iopub.status.busy":"2023-01-05T06:37:25.675292Z","iopub.execute_input":"2023-01-05T06:37:25.675617Z","iopub.status.idle":"2023-01-05T06:38:01.491686Z","shell.execute_reply.started":"2023-01-05T06:37:25.675587Z","shell.execute_reply":"2023-01-05T06:38:01.490518Z"},"trusted":true},"execution_count":null,"outputs":[]}]}