{ "cells": [ { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "67197eb8-2065-8df7-7948-2c44fa2c325c" }, "outputs": [], "source": [ "# This Python 3 environment comes with many helpful analytics libraries installed\n", "# It is defined by the kaggle/python docker image: https://github.com/kaggle/docker-python\n", "# For example, here's several helpful packages to load in \n", "\n", "import numpy as np # linear algebra\n", "import csv\n", "import pandas as pd\n", "from datetime import datetime\n", "from csv import DictReader\n", "from math import exp, log, sqrt" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "e20b4c0a-ce04-a07e-dac6-725357cfdb9a" }, "outputs": [], "source": [ "train = pd.read_csv('../input/clicks_train.csv')\n", "test = pd.read_csv('../input/clicks_test.csv')" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "eb0c591f-fa5d-5c0c-506b-9a0e7f1c727f" }, "outputs": [], "source": [ "train.head()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "551c0baa-7f59-a3d6-2ff2-8b8cb1bf4977" }, "outputs": [], "source": [ "test.head()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "2ff3bfe9-f4d7-d4d9-d386-aedd339beb36" }, "outputs": [], "source": [ "##############################################################################\n", "# start training #############################################################\n", "##############################################################################\n", "\n", "start = datetime.now()\n", "\n", "# initialize ourselves a learner\n", "#learner = ftrl_proximal(alpha, beta, L1, L2, D, interaction)\n", "\n", "print(\"Content..\")\n", "with open( \"../input/promoted_content.csv\") as infile:\n", "\tprcont = csv.reader(infile)\n", "\t#prcont_header = (prcont.next())[1:]\n", "\tprcont_header = next(prcont)[1:]\n", "\tprcont_dict = {}\n", "\tfor ind,row in enumerate(prcont): # enumerate()\u7528\u4e8e\u904d\u5386\u5e8f\u5217\u4e2d\u7684\u5143\u7d20\u548c\u4e0b\u6807\uff0cind\u4e0b\u6807\uff0crow\u5143\u7d20\n", "\t\tprcont_dict[int(row[0])] = row[1:]\n", "\t\tif ind%100000 == 0:\n", "\t\t\tprint('ind', ind)\n", "\t\tif ind==10000:\n", "\t\t\tbreak\n", "\tprint('len(prcont_dict)', len(prcont_dict))\n", "print(prcont_header)\n", "print(row)\n", "print(prcont_dict)\n", "print(prcont)\n", "del prcont\n", "print('********')" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "8d4ff1e8-fe21-8620-a789-8ee519281a60" }, "outputs": [], "source": [ "'''\n", "f = csv.reader(open( \"../input/promoted_content.csv\"))\n", "next(f)\n", "c = 0\n", "a = 0\n", "d = {}\n", "\n", "for line in f:\n", " print(line)\n", " c += 1\n", " if c == 3:\n", " break\n", "\n", "for ind, row in enumerate(f):\n", " #print('row', row)\n", " d[row[0]] = row[1:]\n", " a += 1\n", " if a == 10:\n", " break\n", " \n", "print('d', d)\n", "'''" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "94e26735-8dac-58a0-f35c-0658f2d2bebe" }, "outputs": [], "source": [ "print(\"Events..\")\n", "with open( \"../input/events.csv\") as infile:\n", "\tevents = csv.reader(infile)\n", "\t#events.next()\n", "\tnext(events)\n", "\tevent_header = ['uuid', 'document_id', 'platform', 'geo_location', 'loc_country', 'loc_state', 'loc_dma']\n", "\tevent_dict = {}\n", "\tfor ind,row in enumerate(events):\n", "\t\ttlist = row[1:3] + row[4:6]\n", "\t\tloc = row[5].split('>')\n", "\t\tif len(loc) == 3:\n", "\t\t\ttlist.extend(loc[:])\n", "\t\telif len(loc) == 2:\n", "\t\t\ttlist.extend( loc[:]+[''])\n", "\t\telif len(loc) == 1:\n", "\t\t\ttlist.extend( loc[:]+['',''])\n", "\t\telse:\n", "\t\t\ttlist.append(['','',''])\t\n", "\t\tevent_dict[int(row[0])] = tlist[:] \n", "\t\tif ind%100000 == 0:\n", "\t\t\tprint(\"Events : \", ind)\n", "\t\tif ind==10000:\n", "\t\t\tbreak\n", "\tprint(len(event_dict))\n", "del events" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "0a6433b6-ce04-563b-0e36-256ac907968f" }, "outputs": [], "source": [ "leak_uuid_dict = {}" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "d9ea1d0c-466b-e25f-311b-1388c68c2af8" }, "outputs": [], "source": [ "# B, model\n", "alpha = .1 # learning rate\n", "beta = 0. # smoothing parameter for adaptive learning rate\n", "L1 = 0. # L1 regularization, larger value means more regularized\n", "L2 = 0. # L2 regularization, larger value means more regularized\n", "\n", "# C, feature/hash trick\n", "D = 2 ** 20 # number of weights to use\n", "interaction = False # whether to enable poly2 feature interactions\n", "\n", "# D, training/validation\n", "epoch = 1 # learn training data for N passes\n", "holdafter = None # data after date N (exclusive) are used as validation\n", "holdout = None # use every N training instance for holdout validation\n", "\n", "\n", "##############################################################################\n", "# class, function, generator definitions #####################################\n", "##############################################################################\n", "\n", "class ftrl_proximal(object):\n", " ''' Our main algorithm: Follow the regularized leader - proximal\n", "\n", " In short,\n", " this is an adaptive-learning-rate sparse logistic-regression with\n", " efficient L1-L2-regularization\n", "\n", " Reference:\n", " http://www.eecs.tufts.edu/~dsculley/papers/ad-click-prediction.pdf\n", " '''\n", "\n", " def __init__(self, alpha, beta, L1, L2, D, interaction):\n", " # parameters\n", " self.alpha = alpha\n", " self.beta = beta\n", " self.L1 = L1\n", " self.L2 = L2\n", "\n", " # feature related parameters\n", " self.D = D\n", " self.interaction = interaction\n", "\n", " # model\n", " # n: squared sum of past gradients\n", " # z: weights\n", " # w: lazy weights\n", " self.n = [0.] * D\n", " self.z = [0.] * D\n", " self.w = {}\n", "\n", " def _indices(self, x):\n", " ''' A helper generator that yields the indices in x\n", "\n", " The purpose of this generator is to make the following\n", " code a bit cleaner when doing feature interaction.\n", " '''\n", "\n", " # first yield index of the bias term\n", " yield 0\n", "\n", " # then yield the normal indices\n", " for index in x:\n", " yield index\n", "\n", " # now yield interactions (if applicable)\n", " if self.interaction:\n", " D = self.D\n", " L = len(x)\n", "\n", " x = sorted(x)\n", " for i in xrange(L):\n", " for j in xrange(i+1, L):\n", " # one-hot encode interactions with hash trick\n", " yield abs(hash(str(x[i]) + '_' + str(x[j]))) % D\n", "\n", " def predict(self, x):\n", " ''' Get probability estimation on x\n", "\n", " INPUT:\n", " x: features\n", "\n", " OUTPUT:\n", " probability of p(y = 1 | x; w)\n", " '''\n", "\n", " # parameters\n", " alpha = self.alpha\n", " beta = self.beta\n", " L1 = self.L1\n", " L2 = self.L2\n", "\n", " # model\n", " n = self.n\n", " z = self.z\n", " w = {}\n", "\n", " # wTx is the inner product of w and x\n", " wTx = 0.\n", " for i in self._indices(x):\n", " sign = -1. if z[i] < 0 else 1. # get sign of z[i]\n", "\n", " # build w on the fly using z and n, hence the name - lazy weights\n", " # we are doing this at prediction instead of update time is because\n", " # this allows us for not storing the complete w\n", " if sign * z[i] <= L1:\n", " # w[i] vanishes due to L1 regularization\n", " w[i] = 0.\n", " else:\n", " # apply prediction time L1, L2 regularization to z and get w\n", " w[i] = (sign * L1 - z[i]) / ((beta + sqrt(n[i])) / alpha + L2)\n", "\n", " wTx += w[i]\n", "\n", " # cache the current w for update stage\n", " self.w = w\n", "\n", " # bounded sigmoid function, this is the probability estimation\n", " return 1. / (1. + exp(-max(min(wTx, 35.), -35.)))\n", "\n", " def update(self, x, p, y):\n", " ''' Update model using x, p, y\n", "\n", " INPUT:\n", " x: feature, a list of indices\n", " p: click probability prediction of our model\n", " y: answer\n", "\n", " MODIFIES:\n", " self.n: increase by squared gradient\n", " self.z: weights\n", " '''\n", "\n", " # parameter\n", " alpha = self.alpha\n", "\n", " # model\n", " n = self.n\n", " z = self.z\n", " w = self.w\n", "\n", " # gradient under logloss\n", " g = p - y\n", "\n", " # update z and n\n", " for i in self._indices(x):\n", " sigma = (sqrt(n[i] + g * g) - sqrt(n[i])) / alpha\n", " z[i] += g - sigma * w[i]\n", " n[i] += g * g" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "5a013208-05d7-97f1-d5d5-90cc8a657973" }, "outputs": [], "source": [ "def logloss(p, y):\n", " ''' FUNCTION: Bounded logloss\n", "\n", " INPUT:\n", " p: our prediction\n", " y: real answer\n", "\n", " OUTPUT:\n", " logarithmic loss of p given y\n", " '''\n", "\n", " p = max(min(p, 1. - 10e-15), 10e-15)\n", " return -log(p) if y == 1. else -log(1. - p)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "bbd35ead-924b-bfc4-ea6a-77769e007785" }, "outputs": [], "source": [ "def data(path, D):\n", " ''' GENERATOR: Apply hash-trick to the original csv row\n", " and for simplicity, we one-hot-encode everything\n", "\n", " INPUT:\n", " path: path to training or testing file\n", " D: the max index that we can hash to\n", "\n", " YIELDS:\n", " ID: id of the instance, mainly useless\n", " x: a list of hashed and one-hot-encoded 'indices'\n", " we only need the index since all values are either 0 or 1\n", " y: y = 1 if we have a click, else we have y = 0\n", " '''\n", "\n", " for t, row in enumerate(DictReader(open(path))):\n", " # process id\n", " disp_id = int(row['display_id'])\n", " ad_id = int(row['ad_id'])\n", " \n", " #print('disp_id', disp_id)\n", " #print('ad_id', ad_id)\n", " \n", " # process clicks\n", " y = 0.\n", " if 'clicked' in row:\n", " if row['clicked'] == '1':\n", " y = 1.\n", " del row['clicked']\n", "\n", " x = []\n", " for key in row:\n", " x.append(abs(hash(key + '_' + row[key])) % D)\n", "\n", " row = prcont_dict.get(ad_id, [])\t\t\n", " # build x\n", " ad_doc_id = -1\n", " for ind, val in enumerate(row):\n", " if ind==0:\n", " ad_doc_id = int(val)\n", " x.append(abs(hash(prcont_header[ind] + '_' + val)) % D)\n", "\n", " row = event_dict.get(disp_id, [])\n", " ## build x\n", " disp_doc_id = -1\n", " for ind, val in enumerate(row):\n", " if ind==0:\n", " uuid_val = val\n", " if ind==1:\n", " disp_doc_id = int(val)\n", " x.append(abs(hash(event_header[ind] + '_' + val)) % D)\n", "\n", " if (ad_doc_id in leak_uuid_dict) and (uuid_val in leak_uuid_dict[ad_doc_id]):\n", " x.append(abs(hash('leakage_row_found_1'))%D)\n", " else:\n", " x.append(abs(hash('leakage_row_not_found'))%D)\n", " \n", " yield t, disp_id, ad_id, x, y" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "5416e13e-bded-6f11-7d1b-ccb1f82f0753" }, "outputs": [], "source": [ "# initialize ourselves a learner\n", "learner = ftrl_proximal(alpha, beta, L1, L2, D, interaction)\n", "\n", "# start training\n", "for e in range(epoch):\n", " loss = 0.\n", " count = 0\n", " date = 0\n", "\n", " for t, disp_id, ad_id, x, y in data('../input/clicks_train.csv', D): # data is a generator\n", " # t: just a instance counter\n", " # date: you know what this is\n", " # ID: id provided in original data\n", " # x: features\n", " # y: label (click)\n", "\n", " # step 1, get prediction from learner\n", " p = learner.predict(x)\n", "\n", " if (holdafter and date > holdafter) or (holdout and t % holdout == 0):\n", " # step 2-1, calculate validation loss\n", " # we do not train with the validation data so that our\n", " # validation loss is an accurate estimation\n", " #\n", " # holdafter: train instances from day 1 to day N\n", " # validate with instances from day N + 1 and after\n", " #\n", " # holdout: validate with every N instance, train with others\n", " loss += logloss(p, y)\n", " count += 1\n", " else:\n", " # step 2-2, update learner with label (click) information\n", " learner.update(x, p, y)\n", "\n", " if t%1000000 == 0:\n", " print(\"Processed : \", t, datetime.now())\n", " if t == 100000: \n", " break\n", " " ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "cc13a305-a660-7e56-2395-029a41fe7e33" }, "outputs": [], "source": [ "\n", "##############################################################################\n", "# start testing, and build Kaggle's submission file ##########################\n", "##############################################################################\n", "\n", "with open(submission, 'w') as outfile:\n", " outfile.write('display_id,ad_id,clicked\\n')\n", " for t, disp_id, ad_id, x, y in data(test, D):\n", " p = learner.predict(x)\n", " outfile.write('%s,%s,%s\\n' % (disp_id, ad_id, str(p)))\n", " if t%1000000 == 0:\n", " print(\"Processed : \", t, datetime.now())\n", " if t ==100000:\n", " break" ] } ], "metadata": { "_change_revision": 0, "_is_fork": false, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }