{"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 Basic Markov Decision Process for candidate choose\nMarkov Decision Process, a stochastic decision-making process that uses a mathematical framework to model the decision-making of a dynamic system. It is used in scenarios where the results are either random or controlled by a decision maker, which makes sequential decisions over time.\n\n### A MDP consists of the following elements:\n1. *T* is all decision times.\n2. *S* is a set of states, which is a set of all possible states of the system.\n3. *A* is set of actions\n4. *P* is set of Transition Probabilities\n5. *R* is a Reward FunctionA MDP consists of the following elements:\n\nIn this competition manner; \n*     S is candidate item set,\n*     A is set of actions those are {'clicks', 'carts', 'orders'}, \n*     P is the probability matrix which one of its value is the switching probability from an item to next item with a defined action. \n*     The reward process was not implemented because the goal was to find candidate item probabilities.","metadata":{}},{"cell_type":"code","source":"!pip install polars pyarrow --quiet","metadata":{"execution":{"iopub.status.busy":"2023-02-02T20:32:31.247573Z","iopub.execute_input":"2023-02-02T20:32:31.247926Z","iopub.status.idle":"2023-02-02T20:32:39.492053Z","shell.execute_reply.started":"2023-02-02T20:32:31.247897Z","shell.execute_reply":"2023-02-02T20:32:39.490993Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"from tqdm import tqdm\nimport numpy as np\nimport os\nimport sys\nimport builtins\nimport polars as pl\nimport pandas as pd\nimport time\nimport gc","metadata":{"tags":[],"execution":{"iopub.status.busy":"2023-02-02T20:32:39.493859Z","iopub.execute_input":"2023-02-02T20:32:39.494146Z","iopub.status.idle":"2023-02-02T20:32:40.721838Z","shell.execute_reply.started":"2023-02-02T20:32:39.494120Z","shell.execute_reply":"2023-02-02T20:32:40.720833Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Load CV Data","metadata":{}},{"cell_type":"code","source":"%%time\ntrain_df = pl.read_parquet('/kaggle/input/otto-train-and-test-data-for-local-validation/train.parquet')\ntest_df = pl.read_parquet('/kaggle/input/otto-train-and-test-data-for-local-validation/test.parquet')\nlabels_df = pl.read_parquet('/kaggle/input/otto-train-and-test-data-for-local-validation/test_labels.parquet')","metadata":{"tags":[],"execution":{"iopub.status.busy":"2023-02-02T20:32:40.722945Z","iopub.execute_input":"2023-02-02T20:32:40.723294Z","iopub.status.idle":"2023-02-02T20:32:50.625668Z","shell.execute_reply.started":"2023-02-02T20:32:40.723269Z","shell.execute_reply":"2023-02-02T20:32:50.624642Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Regulations","metadata":{}},{"cell_type":"code","source":"def add_aid_pos_reverse(df):\n    return df.select([\n        pl.col('*'),\n        pl.col('session').cumcount().reverse().over('session').alias('aid_pos_reverse')+1\n    ])\n\ndef add_r_score(df):\n    pos_alpha = 10\n    r_score = pl.Series(1 / (2**((df['aid_pos_reverse']-1)/pos_alpha)))\n    return df.with_columns(r_score.alias('r_score')).fill_nan(0)\n\ndef add_type_weighted_r_score(df):\n    tw = {0:.2, 1:.3, 2:.4}\n    tw_r_score = pl.Series(df['r_score'] * df['type'].apply(lambda x: tw[x]))\n    df = df.with_columns(tw_r_score.alias('tw_r_score'))\n    df = df.drop('r_score')\n    return df\n\ndef apply(df, pipeline):\n    for f in pipeline:\n        df = f(df)\n    return df\n\ndef transitions_shift(df):\n    df = df.with_columns([\n        pl.col(['aid']).shift(-1).over('session').prefix(\"next_\"),\n        pl.col(['type']).shift(-1).over('session').prefix(\"next_\"),\n        pl.col(['ts']).shift(-1).over('session').prefix(\"next_\")\n    ]).with_columns([\n        pl.col(\"next_aid\").fill_null(pl.col(\"aid\")),\n        pl.col(\"next_type\").fill_null(pl.col(\"type\")),\n        pl.col(\"next_ts\").fill_null(pl.col(\"ts\")+1)\n    ])\n    \n    time_diff = pl.Series(df['next_ts'] - df['ts']+1)\n\n    # time_alpha = 60 sec * 60 min * 12 hours\n    time_alpha = 60*60*12\n    \n    t_diff = 1/(2**((time_diff-1)/(time_alpha-1)))\n    \n    df = df.with_columns([\n        t_diff.alias('time_diff'),\n    ])    \n    \n    df = df.drop_nulls()\n    \n    return df\n\ndef eval_test_df(df):\n    df = df.drop('ts')\n    return df\n\npipeline = [\n    add_aid_pos_reverse, \n    add_r_score,\n    add_type_weighted_r_score\n]","metadata":{"execution":{"iopub.status.busy":"2023-02-02T20:42:33.366980Z","iopub.execute_input":"2023-02-02T20:42:33.367884Z","iopub.status.idle":"2023-02-02T20:42:33.383519Z","shell.execute_reply.started":"2023-02-02T20:42:33.367847Z","shell.execute_reply":"2023-02-02T20:42:33.382554Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n\ntransitions_df = pl.concat([\n    train_df,\n    test_df\n], how=\"vertical\")\n\nprint(\"transitions_df\")\ntransitions_df = apply(transitions_df, pipeline)\n\nprint(\"transitions_df shift\")\ntransitions_df = transitions_shift(transitions_df)\n\n\nprint(\"test_df_transitions\")\ntest_df_transitions = apply(eval_test_df(test_df), pipeline)\n\nprint(\"apply weights for aids in each session for initial states\")\ntest_df_transitions = test_df_transitions.join(transitions_df, how='left', \\\n                               left_on=['session','aid','aid_pos_reverse'], \\\n                               right_on=['session','aid','aid_pos_reverse']).fill_null(0)\nweight = pl.Series(test_df_transitions['tw_r_score']*test_df_transitions['time_diff'])\ntest_df_transitions = test_df_transitions.with_columns([weight.alias('weight')]) \n\ntest_df_transitions = test_df_transitions[['session','aid','type','weight']]\ntransitions_df = transitions_df[['aid','type','next_aid','next_type']]","metadata":{"execution":{"iopub.status.busy":"2023-02-02T20:42:40.332796Z","iopub.execute_input":"2023-02-02T20:42:40.333504Z","iopub.status.idle":"2023-02-02T20:45:27.098300Z","shell.execute_reply.started":"2023-02-02T20:42:40.333469Z","shell.execute_reply":"2023-02-02T20:45:27.097135Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Emission Probabilities","metadata":{}},{"cell_type":"code","source":"%%time\nprint(\"emission_probabilities\")\nemission_probabilities = transitions_df.groupby(['aid','type','next_type']).agg([\n    pl.col('next_aid').count().alias('count')\n])\n\nemission_probabilities = emission_probabilities.select([\n    pl.col('*'),\n    pl.col('count').sum().over(['aid']).alias('total_count')\n])\n\nep = emission_probabilities['count'] / emission_probabilities['total_count']\nemission_probabilities = emission_probabilities.with_columns(pl.Series(ep).alias('ep')).fill_nan(0)\nemission_probabilities = emission_probabilities.drop('count')\nemission_probabilities = emission_probabilities.drop('total_count') ","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:44:42.119485Z","iopub.execute_input":"2023-02-02T21:44:42.120369Z","iopub.status.idle":"2023-02-02T21:44:45.687673Z","shell.execute_reply.started":"2023-02-02T21:44:42.120325Z","shell.execute_reply":"2023-02-02T21:44:45.686407Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"emission_probabilities.filter(pl.col('aid')==11830)","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:45:27.825135Z","iopub.execute_input":"2023-02-02T21:45:27.826225Z","iopub.status.idle":"2023-02-02T21:45:27.882491Z","shell.execute_reply.started":"2023-02-02T21:45:27.826186Z","shell.execute_reply":"2023-02-02T21:45:27.881381Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Transition Probabilities","metadata":{}},{"cell_type":"code","source":"%%time\nprint(\"transitions\")\ntransitions = transitions_df.groupby(['aid','next_aid','type','next_type']).agg([\n    pl.col('next_aid').count().alias('count')\n])\n\ntransitions = transitions.select([\n    pl.col('*'),\n    pl.col('count').sum().over(['aid','type','next_type']).alias('total_count'),\n])\n\ntp = pl.Series((transitions['count'] / transitions['total_count']) )\n\ntransitions = transitions.with_columns(tp.alias('tp')).fill_nan(0)\n\ntransitions = transitions[['type','aid','next_type','next_aid','tp']]\n\n## trimming for optimization\nTOP_K = 100\ntransitions = transitions.sort('tp', reverse=True).groupby(['aid','type','next_type']).head(TOP_K)","metadata":{"tags":[],"execution":{"iopub.status.busy":"2023-02-02T21:00:14.083548Z","iopub.execute_input":"2023-02-02T21:00:14.084263Z","iopub.status.idle":"2023-02-02T21:00:39.687799Z","shell.execute_reply.started":"2023-02-02T21:00:14.084229Z","shell.execute_reply":"2023-02-02T21:00:39.686640Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"transitions.filter(pl.col('aid')==11830)","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:45:55.088509Z","iopub.execute_input":"2023-02-02T21:45:55.089671Z","iopub.status.idle":"2023-02-02T21:45:55.264206Z","shell.execute_reply.started":"2023-02-02T21:45:55.089633Z","shell.execute_reply":"2023-02-02T21:45:55.263182Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Agent Tours","metadata":{}},{"cell_type":"code","source":"def markov_decision_process(sessions):\n\n    top_k = 20\n    top_n = 50\n\n    # forward (1st tour)\n    ep = sessions.join(emission_probabilities, how='left', left_on=['aid','type'], right_on=['aid','type']).fill_null(0)\n    tp = ep.join(transitions, how='left', left_on=['aid','type','next_type'],\\\n                       right_on=['aid','type','next_type']).fill_null(0)\n    probabilities = tp.with_columns(pl.Series(tp['ep'] * tp['tp']).alias('prob_1'))\n    \n    candidates = probabilities[['session','next_aid','next_type','prob_1']] \n    candidates = candidates.rename({'next_aid':'aid','next_type':'type','prob_1':'score'})\n    candidates = candidates.groupby(['session','aid','type']).agg([\n            pl.col('score').sum().alias('score')\n        ])\n    candidates_first = candidates.sort('score', reverse=True).groupby(['session','type']).head(top_n)\n    candidates_next = candidates.sort('score', reverse=True).groupby(['session','type']).head(top_k)\n\n    # forward (2nd tour)\n    ep = candidates_next.join(emission_probabilities, how='left', left_on=['aid','type'], right_on=['aid','type']).fill_null(0)\n    tp = ep.join(transitions, how='left', left_on=['aid','type','next_type'],\\\n                       right_on=['aid','type','next_type']).fill_null(0)\n    probabilities = tp.with_columns(pl.Series(tp['score'] * tp['ep'] * tp['tp']).alias('prob_2'))\n    \n    candidates_second = probabilities[['session','next_aid','next_type','prob_2']] \n    candidates_second = candidates_second.rename({'next_aid':'aid','next_type':'type','prob_2':'score'})\n    candidates_second = candidates_second.groupby(['session','aid','type']).agg([\n            pl.col('score').sum().alias('score')\n        ])\n    candidates_second = candidates_second.sort('score', reverse=True).groupby(['session','type']).head(top_n)\n\n    # init recommends\n    ses_init_aids = sessions.rename({'weight':'score'})[['session','type','aid','score']]\n    \n    return pl.concat([\n        ses_init_aids,\n        candidates_first,\n        candidates_second\n    ], how=\"vertical\").groupby(['session','type','aid']).agg([\n        pl.col('score').sum().alias('score')\n    ]) ","metadata":{"tags":[],"execution":{"iopub.status.busy":"2023-02-02T21:09:43.415030Z","iopub.execute_input":"2023-02-02T21:09:43.415961Z","iopub.status.idle":"2023-02-02T21:09:43.433576Z","shell.execute_reply.started":"2023-02-02T21:09:43.415922Z","shell.execute_reply":"2023-02-02T21:09:43.432675Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Chunked df","metadata":{}},{"cell_type":"code","source":"%%time\nVER = 1\nCACHED = False\nCHUNK_COUNT = 80\n\ns = pl.Series(lag_test_df[\"session\"])\nsmin = s.min()\nsmax = s.max()\n\nif not CACHED:\n    chunk_size = (smax-smin)/CHUNK_COUNT\n    for c,x in enumerate(tqdm(range(smin, smax-1, round(chunk_size)))):\n        ses_end = min(x+round(chunk_size)-1,smax)\n        chunked_df = test_df_transitions.filter((pl.col(\"session\")>=x)&(pl.col(\"session\")<=ses_end))\n        probs = markov_decision_process(chunked_df)\n        probs.write_parquet(f\"/kaggle/working/probs_tr_ver_{VER}_{c}.parquet\")\n    prob_set = pl.read_parquet(f\"/kaggle/working/probs_tr_ver_{VER}_*\")\nelse:\n    prob_set = pl.read_parquet(f\"/kaggle/working/probs_tr_ver_{VER}_*\")","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:09:45.913300Z","iopub.execute_input":"2023-02-02T21:09:45.913731Z","iopub.status.idle":"2023-02-02T21:32:03.540069Z","shell.execute_reply.started":"2023-02-02T21:09:45.913699Z","shell.execute_reply":"2023-02-02T21:32:03.538911Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"# A coldstart session example with one click\nprob_set.filter(pl.col('session')==11098528)","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:46:44.548343Z","iopub.execute_input":"2023-02-02T21:46:44.548799Z","iopub.status.idle":"2023-02-02T21:46:44.865613Z","shell.execute_reply.started":"2023-02-02T21:46:44.548768Z","shell.execute_reply":"2023-02-02T21:46:44.864571Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## Evaluation","metadata":{}},{"cell_type":"code","source":"%%time\n\nprint(\"Weights for events\")\nscore_clicks = pl.Series( prob_set['score'] + ( 1 * prob_set['type'] * prob_set['score'] ) )\nscore_carts = pl.Series( prob_set['score'] + ( 3 * prob_set['type'] * prob_set['score'] ) )\nscore_orders = pl.Series( prob_set['score'] + ( 6 * prob_set['type'] * prob_set['score'] ) )\n \nprint(\"Separate scores for each event\")\nprob_set = prob_set.with_columns([\n    score_clicks.alias('score_clicks'),\n    score_carts.alias('score_carts'),\n    score_orders.alias('score_orders')\n])\n\nprint(\"Merge and sum scores for to prevent duplicate aids\")\nprob_set = prob_set.groupby(['session','aid']).agg([\n    pl.col('score_clicks').sum().alias('score_clicks'),\n    pl.col('score_carts').sum().alias('score_carts'),\n    pl.col('score_orders').sum().alias('score_orders')\n])","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:32:21.583108Z","iopub.execute_input":"2023-02-02T21:32:21.584101Z","iopub.status.idle":"2023-02-02T21:32:56.012084Z","shell.execute_reply.started":"2023-02-02T21:32:21.584064Z","shell.execute_reply":"2023-02-02T21:32:56.010919Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\nclick_predictions = prob_set.sort(['score_clicks'], reverse=True).groupby(['session']).agg([\n    pl.col('aid').limit(20)\n])\ncart_predictions = prob_set.sort(['score_carts'], reverse=True).groupby(['session']).agg([\n    pl.col('aid').limit(20)\n])\norder_predictions = prob_set.sort(['score_orders'], reverse=True).groupby(['session']).agg([\n    pl.col('aid').limit(20)\n])","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:33:03.196336Z","iopub.execute_input":"2023-02-02T21:33:03.196775Z","iopub.status.idle":"2023-02-02T21:34:07.033399Z","shell.execute_reply.started":"2023-02-02T21:33:03.196743Z","shell.execute_reply":"2023-02-02T21:34:07.032175Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"%%time\n#click preds\nclick_preds = click_predictions.to_pandas()\nclick_preds[\"session\"] = click_preds.session.apply(lambda x: str(x)+\"_clicks\")\nclick_preds.columns = [\"session_type\", \"labels\"]\n#cart preds\ncart_preds = cart_predictions.to_pandas()\ncart_preds[\"session\"] = cart_preds.session.apply(lambda x: str(x)+\"_carts\")\ncart_preds.columns = [\"session_type\", \"labels\"]\n#order preds\norder_preds = order_predictions.to_pandas()\norder_preds[\"session\"] = order_preds.session.apply(lambda x: str(x)+\"_orders\")\norder_preds.columns = [\"session_type\", \"labels\"]\n\nvalid_set = pd.concat([click_preds,cart_preds,order_preds],ignore_index=True).sort_values(\"session_type\")","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:34:49.876233Z","iopub.execute_input":"2023-02-02T21:34:49.877443Z","iopub.status.idle":"2023-02-02T21:35:08.131920Z","shell.execute_reply.started":"2023-02-02T21:34:49.877400Z","shell.execute_reply":"2023-02-02T21:35:08.130692Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"## CV Local Score Eval.","metadata":{}},{"cell_type":"code","source":"%%time\nprint('- - -')\n# Compute Recalls\nscore = 0\nweights = [0.10, 0.30, 0.60]\nlabels = ['clicks','carts','orders']\ntlab = labels_df.to_pandas()\nfor t in range(3):\n    sub = valid_set.loc[valid_set.session_type.str.contains(labels[t])].copy()\n    sub['session'] = sub.session_type.apply(lambda x: int(x.split('_')[0]))    \n    test_labels = tlab.loc[tlab['type']==labels[t]]\n    test_labels = test_labels.loc[test_labels['session'].isin(sub['session'])]\n    test_labels = test_labels.merge(sub, how='left', on=['session'])\n    test_labels['hits'] = test_labels.apply(lambda df: len(set(df.ground_truth).intersection(set(df.labels))), axis=1)\n    test_labels['gt_count'] = test_labels.ground_truth.str.len().clip(0,20)\n    recall = test_labels['hits'].sum() /test_labels['gt_count'].sum()\n    score += weights[t] * recall\n    print(labels[t] + ' recall = ' + str(recall))\nprint('- - -')\nprint('Overall Recall ='+str(score))\nprint('- - -')","metadata":{"execution":{"iopub.status.busy":"2023-02-02T21:35:16.047412Z","iopub.execute_input":"2023-02-02T21:35:16.047829Z","iopub.status.idle":"2023-02-02T21:37:03.370934Z","shell.execute_reply.started":"2023-02-02T21:35:16.047798Z","shell.execute_reply":"2023-02-02T21:37:03.370069Z"},"trusted":true},"execution_count":null,"outputs":[]}]}