'''
Algorithm: Follow the regularized leader - proximal

LB score : 0.668

Reference:
        http://www.eecs.tufts.edu/~dsculley/papers/ad-click-prediction.pdf

This code is based on tinrtgu famous beat the benchmark with less than 1MB of memory.
In short,
this is an adaptive-learning-rate sparse logistic-regression with
efficient L1-L2-regularization

https://www.kaggle.com/c/criteo-display-ad-challenge/discussion/10322

And adapted for the competition from
https://github.com/swapniel99/criteo

How to run in your terminal?

First save the file, example: FTRL_microsoft.py

With python3:
	python3 FTRL_microsoft.py

	To run with python3 you may need to install Python wrapper for MurmurHash (MurmurHash3) with:

	sudo pip install mmh3

With pypy:
	You can run the code with pypy as it will give you a huge speed-up (0nly took 5 minuties). To use the script
	with pypy on Ubuntu, first type

	sudo apt-get install pypy

	Then you need to get pure python MurmurHash3 implementation to run with pypy from the
	follwoing link and then put the file to current directory

	https://raw.githubusercontent.com/wc-duck/pymmh3/master/pymmh3.py

Then use the pypy interpreter to run the script

pypy FTRL_microsoft.py
'''

from datetime import datetime
from csv import DictReader
from math import exp, log, sqrt


# try to run pure python MurmurHash3 implementation with pypy
# download pure pymmh3 from https://raw.githubusercontent.com/wc-duck/pymmh3/master/pymmh3.py

#from pymmh3 import hash # uncomment this line if you run this code with pypy, and comment the next import

# ... otherwise try with a fast c-implementation to run with python3...
from mmh3 import hash # comment this line if you run this code with pypy, and uncomment the previous import


# dataset parameters #################################################################
train = '../input/train.csv'  # path to training file
test = '../input/test.csv'  # path to testing file
submission = 'submission.csv'  # path of to be outputted submission file


epoch = 1         # learn training data for N passes
logbatch = 10000  # batch log info after every N rows

# feature related parameters
signed = True  # Use signed hash? Set to False for to reduce number of hash calls
interaction = False  # whether to enable poly2 feature interactions
D = 2 ** 24    # number of weights use for learning

# model related parameters
lambda1 = 0.001  # L1 regularization, larger value means more regularized
lambda2 = 0.001  # L2 regularization, larger value means more regularized

if interaction:
    alpha = .04  # learning rate for sgd optimization
else:
    alpha = .1  # learning rate for sgd optimization
adapt = 1.  # Use adagrad, sets it as power of adaptive factor. >1 will amplify adaptive measure and vice versa
fudge = .4997  # Fudge factor (ratio of positive class)

# function definitions #######################################################

# A. Bounded logloss
# INPUT:
#     p: our prediction
#     y: real answer
# OUTPUT
#     logarithmic loss of p given y
def logloss(p, y):
    p = max(min(p, 1. - 10e-17), 10e-17)  # The bounds
    return -log(p) if y == 1. else -log(1. - p)


# B. Apply hash trick of the original csv row
# for simplicity, we treat both integer and categorical features as categorical
# INPUT:
#     csv_row: a csv dictionary, ex: {'Lable': '1', 'I1': '357', 'I2': '', ...}
#     D: the max index that we can hash to
# OUTPUT:
#     x: a list of indices that its value is 1
def get_x(csv_row, D):
    fullind = []
    for key, value in csv_row.items():
        s = key + '=' + value.lower()
        fullind.append(hash(s) % D)  # one-hot encode everything with hash trick

    if interaction == True:
        indlist2 = []
        for i in range(len(fullind)):
            for j in range(i + 1, len(fullind)):
                indlist2.append(fullind[i] ^ fullind[j])  # Creating interactions using XOR
        fullind = fullind + indlist2

    x = {}
    x[0] = 1  # 0 is the index of the bias term
    for index in fullind:
        if (index not in x):
            x[index] = 0
        if signed:
            x[index] += (1 if (hash(str(index)) % 2) == 1 else -1)  # Disable for speed
        else:
            x[index] += 1

    return x  # x contains indices of features that have a value as number of occurences


# C. Get probability estimation on x
# INPUT:
#     x: features
#     w: weights
# OUTPUT:
#     probability of p(y = 1 | x; w)
def get_p(x, w):
    wTx = 0.
    for i, xi in x.items():
        wTx += w[i] * xi  # w[i] * x[i]
    return 1. / (1. + exp(-max(min(wTx, 50.), -50.)))  # bounded sigmoid


# D. Update given model
# INPUT:
#     w: weights
#     n: a counter that counts the number of times we encounter a feature
#        this is used for adaptive learning rate
#     x: feature
#     p: prediction of our model
#     y: answer
# OUTPUT:
#     w: updated model
#     n: updated count
def update_w(w, g, x, p, y):
    for i, xi in x.items():
        # alpha / (sqrt(g) + 1) is the adaptive learning rate heuristic
        # (p - y) * x[i] is the current gradient
        # note that in our case, if i in x then x[i] = 1
        delreg = (lambda1 * ((-1.) if w[i] < 0. else 1.) + lambda2 * w[i]) if i != 0 else 0.
        delta = (p - y) * xi + delreg
        if adapt > 0:
            g[i] += delta ** 2
        w[i] -= delta * alpha / (sqrt(g[i]) ** adapt)  # Minimising log loss
    return w, g


# training and testing #######################################################

# initialize our model
w = [0.] * D  # weights
g = [fudge] * D  # sum of historical gradients

# start training a logistic regression model using on pass sgd
for e in range(epoch):
    loss = 0.
    lossb = 0.
    for t, row in enumerate(DictReader(open(train))):
        y = 1. if row['HasDetections'] == '1' else 0.

        del row['HasDetections']  # can't let the model peek the answer
        del row['MachineIdentifier']  # can't let the model peek the answer
        del row['Census_FirmwareVersionIdentifier'] 
        del row['Census_OEMModelIdentifier'] 
        del row['CityIdentifier']

        # main training procedure
        # step 1, get the hashed features
        x = get_x(row, D)
        # step 2, get prediction
        p = get_p(x, w)

        # for progress validation, useless for learning our model
        lossx = logloss(p, y)
        loss += lossx
        lossb += lossx
        if t % logbatch == 0 and t > 1:
            print('%s\tepoch-> %d\tencountered: %d\tcurrent whole logloss: %f\tcurrent batch logloss: %f' % (
            datetime.now(), e+1, t, loss / t, lossb / logbatch))
            lossb = 0.

        # step 3, update model with answer
        w, g = update_w(w, g, x, p, y)

# testing (build kaggle's submission file)
with open(submission, 'w') as outfile:
    outfile.write('MachineIdentifier,HasDetections\n')
    for t, row in enumerate(DictReader(open(test))):
        MachineIdentifier = row['MachineIdentifier']
        del row['MachineIdentifier']
        del row['Census_FirmwareVersionIdentifier'] 
        del row['Census_OEMModelIdentifier'] 
        del row['CityIdentifier']
        x = get_x(row, D)
        p = get_p(x, w)
        outfile.write('%s,%s\n' % (MachineIdentifier, str(p)))
        if t % logbatch == 0 and t > 1:
            print('%s\ttest rows encountered: %d' % (
                datetime.now(), t))
