脑图

代码实现

'''DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSEVersion 2, December 2004Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSETERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION0. You just DO WHAT THE FUCK YOU WANT TO.
'''from datetime import datetime
from csv import DictReader
from math import exp, log, sqrt# TL; DR, the main training process starts on line: 250,
# you may want to start reading the code from there##############################################################################
# parameters #################################################################
############################################################################### A, paths
# path to training file
train = '/Users/avazu/avazu-ctr-prediction/train'               
# path to testing file
test = '/Users/avazu/avazu-ctr-prediction/test'
# path of to be outputted submission file
submission = '/Users/avazu/avazu-ctr-prediction/sampleSubmission_myself'  # B, model
alpha = .1  # learning rate
beta = 1.   # smoothing parameter for adaptive learning rate
L1 = 1.     # L1 regularization, larger value means more regularized
L2 = 1.     # L2 regularization, larger value means more regularized# C, feature/hash trick
D = 2 ** 20             # Hash分桶的数量 number of weights to use
interaction = False     # whether to enable poly2 feature interactions# D, training/validation
epoch = 1       # learn training data for N passes
holdafter = 22   # data after date N (exclusive) are used as validation
holdout = None  # use every N training instance for holdout validation##############################################################################
# class, function, generator definitions #####################################
############################################################################### ftrl实现逻辑
class ftrl_proximal(object):''' Our main algorithm: Follow the regularized leader - proximalIn short,this is an adaptive-learning-rate sparse logistic-regression withefficient L1-L2-regularizationReference:http://www.eecs.tufts.edu/~dsculley/papers/ad-click-prediction.pdf'''def __init__(self, alpha, beta, L1, L2, D, interaction):# parametersself.alpha = alphaself.beta = betaself.L1 = L1self.L2 = L2# feature related parametersself.D = Dself.interaction = interaction# model# n: squared sum of past gradients# z: weights# w: lazy weightsself.n = [0.] * Dself.z = [0.] * Dself.w = {}def _indices(self, x):''' A helper generator that yields the indices in xThe purpose of this generator is to make the followingcode a bit cleaner when doing feature interaction.'''# first yield index of the bias termyield 0# then yield the normal indicesfor index in x:yield index# now yield interactions (if applicable)if self.interaction:D = self.DL = len(x)x = sorted(x)for i in range(L):for j in range(i+1, L):# one-hot encode interactions with hash trickyield abs(hash(str(x[i]) + '_' + str(x[j]))) % Ddef predict(self, x):''' Get probability estimation on xINPUT:x: featuresOUTPUT:probability of p(y = 1 | x; w)'''# parametersalpha = self.alphabeta = self.betaL1 = self.L1L2 = self.L2# modeln = self.nz = self.zw = {}# wTx is the inner product of w and xwTx = 0.for i in self._indices(x):sign = -1. if z[i] < 0 else 1.  # get sign of z[i]# build w on the fly using z and n, hence the name - lazy weights# we are doing this at prediction instead of update time is because# this allows us for not storing the complete wif sign * z[i] <= L1:# w[i] vanishes due to L1 regularizationw[i] = 0.else:# apply prediction time L1, L2 regularization to z and get ww[i] = (sign * L1 - z[i]) / ((beta + sqrt(n[i])) / alpha + L2)wTx += w[i]# cache the current w for update stageself.w = w# bounded sigmoid function, this is the probability estimation# 做SIGMOD函数return 1. / (1. + exp(-max(min(wTx, 35.), -35.)))#反向传导计算def update(self, x, p, y):''' Update model using x, p, yINPUT:x: feature, a list of indicesp: click probability prediction of our modely: answerMODIFIES:self.n: increase by squared gradientself.z: weights'''# parameteralpha = self.alpha# modeln = self.nz = self.zw = self.w# gradient under loglossg = p - y# update z and nfor i in self._indices(x):sigma = (sqrt(n[i] + g * g) - sqrt(n[i])) / alphaz[i] += g - sigma * w[i]n[i] += g * gdef logloss(p, y):''' FUNCTION: Bounded loglossINPUT:p: our predictiony: real answerOUTPUT:logarithmic loss of p given y'''p = max(min(p, 1. - 10e-15), 10e-15)return -log(p) if y == 1. else -log(1. - p)def data(path, D):''' GENERATOR: Apply hash-trick to the original csv rowand for simplicity, we one-hot-encode everythingINPUT:path: path to training or testing fileD: the max index that we can hash toYIELDS:ID: id of the instance, mainly uselessx: a list of hashed and one-hot-encoded 'indices'we only need the index since all values are either 0 or 1y: y = 1 if we have a click, else we have y = 0'''for t, row in enumerate(DictReader(open(path))):# process idID = row['id']del row['id']# process clicksy = 0.if 'click' in row:if row['click'] == '1':y = 1.del row['click']# extract datedate = int(row['hour'][4:6])# turn hour really into hour, it was originally YYMMDDHHrow['hour'] = row['hour'][6:]# build xx = []for key in row:value = row[key]# one-hot encode everything with hash trickindex = abs(hash(key + '_' + value)) % Dx.append(index)yield t, date, ID, x, y##############################################################################
# start training #############################################################
##############################################################################start = datetime.now()# initialize ourselves a learner
learner = ftrl_proximal(alpha, beta, L1, L2, D, interaction)# start training
for e in range(epoch):loss = 0.count = 0for t, date, ID, x, y in data(train, D):  # data is a generator#    t: just a instance counter# date: you know what this is#   ID: id provided in original data#    x: features#    y: label (click)# step 1, get prediction from learnerp = learner.predict(x)if (holdafter and date > holdafter) or (holdout and t % holdout == 0):# step 2-1, calculate validation loss#           we do not train with the validation data so that our#           validation loss is an accurate estimation## holdafter: train instances from day 1 to day N#            validate with instances from day N + 1 and after## holdout: validate with every N instance, train with othersloss += logloss(p, y)count += 1else:# step 2-2, update learner with label (click) informationlearner.update(x, p, y)print('Epoch %d finished, validation logloss: %f, elapsed time: %s' % (e, loss/count, str(datetime.now() - start)))##############################################################################
# start testing, and build Kaggle's submission file ##########################
##############################################################################with open(submission, 'w') as outfile:outfile.write('id,click\n')for t, date, ID, x, y in data(test, D):p = learner.predict(x)outfile.write('%s,%s\n' % (ID, str(p)))