Comparaison des classificateurs en ligne
Motivation
Comme je l'ai écrit la dernière fois, aucune donnée n'est stockée dans l'entreprise. Cependant, on a supposé que les données seraient énormes si les journaux étaient correctement acquis à l'avenir. Par conséquent, compte tenu de la quantité de calcul (temps / espace), j'ai décidé qu'il était préférable d'utiliser l'algorithme d'apprentissage en ligne. (J'écris une histoire en supposant le post précédent. C'est dommage à bien des égards ... orz) Je n'ai pas utilisé correctement un classificateur en ligne auparavant, j'ai donc essayé plusieurs classificateurs pour l'évaluation des performances (bien qu'il y a longtemps ...).
Présentation du classificateur en ligne
Les classificateurs linéaires sont pour la plupart
- Économie de mémoire
- Facile à réapprendre
Pour un aperçu, reportez-vous à Apprentissage en ligne (Supports de cours de l'Université de Tokyo?). pense.
Il existe différents types de classificateurs en ligne, tels que les algorithmes résistants au bruit et à convergence rapide, la normalisation automatique et l'ajustement automatique des paramètres. Cette fois, j'ai comparé Exact Soft Confidence-Weight Learning (SCW), Stochastic Gradient Descent (SGD) avec ajustement automatique des paramètres, SGD avec normalisation automatique et Naive Bayes (NB).
Les références
- No More Pesky Learning Rates, Schaul+, ‘13[pdf]
- Normalized online learning, Ross+, '13[pdf]
- Exact Soft Confidence-Weighted Learning, Wang, ICML‘12[pdf]
- Matériel de cours de l'Université du Maryland (?) [Pdf] ← Bons matériaux pour confirmer la différenciation partielle de la perte de log je pense
Code de référence
Voici le code que j'ai créé. Une certaine ingéniosité est que (1) le hachage simple des caractéristiques est possible, et (2) seules les composantes diagonales de la matrice de covariance sont enregistrées dans SCW.
SGD avec réglage automatique des paramètres
python
# coding: utf-8
import numpy as np
import math
class SgdTrainWithAutoLR(object):
def __init__(self, fname, feat_dim, loss_type):
self.fname = fname # input file name
self.weight = None # features weight
self.feat_dim = 2**feat_dim # max size of feature vector
self.bitmask = 2**feat_dim - 1 # mapping dimension
self.loss_type = loss_type # type of loss function
self.lambd = None # regularization
self.gamma = None # learning rate
self.x = np.zeros(self.feat_dim)
self.t = 1 # update times
self.gradbar = np.zeros(self.feat_dim)
self.grad2bar = np.zeros(self.feat_dim)
self.tau = np.ones(self.feat_dim)*5
self.gbar = np.zeros(self.feat_dim)
self.vbar = np.zeros(self.feat_dim)
self.hbar = np.zeros(self.feat_dim)
self.epsilon = 10**(-9)
self.loss_weight = 10 #Paramètres de réglage du taux de déséquilibre
self.update_t = 1
def train(self,gamma,lambd):
self.gamma = gamma
self.lambd = lambd
self.initialize()
with open(self.fname,'r') as trainf:
for line in trainf:
y = line.strip().split(' ')[0]
self.features = self.get_features(line.strip().split(' ')[1:])
y = int(-1) if int(y)<=0 else int(1) # posi=1, nega=-Quand dire 1
#Prédiction numérique
pred = self.predict(self.weight,self.features)
grad = y*self.calc_dloss(y*pred)*self.features
self.gradbar = grad
self.grad2bar = grad**2
# update weight
self.update(pred,y)
self.t += 1
print self.weight
print self.t
return self.weight
def initialize(self):
self.weight = np.zeros(self.feat_dim)
def get_features(self,data):
features = np.zeros(self.feat_dim)
for kv in data:
k, v = kv.strip().split(':')
features[int(k)&self.bitmask] += float(v)
return features
def predict(self,w,features): #margin
return np.dot(w,features)
def calc_loss(self,m): # m=py=wxy
if self.loss_type == 'hinge':
return max(0,1-m)
elif self.loss_type == 'log':
if m<=-700: m=-700
return math.log(1+math.exp(-m))
# gradient of loss function
def calc_dloss(self,m): # m=py=wxy
if self.loss_type == 'hinge':
res = -1.0 if (1-m)>0 else 0.0 #perte si la perte ne dépasse pas 0=0.Autrement-Par différenciation de m-Devenir 1
return res
elif self.loss_type == 'log':
if m < 0.0:
return float(-1.0) / (math.exp(m) + 1.0) # yx-e^(-m)/(1+e^(-m))*yx
else:
ez = float( math.exp(-m) )
return -ez / (ez + 1.0) # -yx+1/(1+e^(-m))*yx
def update(self, pred, y):
m = y*pred
self.gbar *= (1 - self.tau**(-1))
self.gbar += self.tau**(-1)*self.gradbar
self.vbar *= (1 - self.tau**(-1))
self.vbar += self.tau**(-1)*self.grad2bar + self.epsilon
self.hbar *= (1 - self.tau**(-1))
self.hbar += self.tau**(-1)*2*self.grad2bar + self.epsilon #
tmp = self.gbar**2/self.vbar
# update memory size
self.tau = (1-tmp)*self.tau+1 + self.epsilon
# update learning rate
eta = tmp/self.hbar
# update weight
self.update_weight(y, m, eta)
def update_weight(self,y,m,eta):
loss = self.calc_loss(m)
if loss>0.0: #Dans le cas de pa
delta = self.calc_dloss(m)*self.features
self.weight -= eta*y*delta
self.update_t += 1
def save_model(self,ofname,w):
with open(ofname,'w') as f:
#Ecrire le type de la fonction de perte
f.write(self.loss_type+'\n')
#Écrire le poids
weight = [str(x).encode('utf-8') for x in w]
f.write(' '.join(weight)+'\n')
#Écriture de la dimension de la quantité de caractéristiques
f.write(str(self.feat_dim).encode('utf-8'))
SGD avec normalisation automatique
python
# coding: utf-8
import numpy as np
import math
class SgdTrainWithAutoNormarize(object):
def __init__(self, fname, feat_dim, loss_type):
self.fname = fname # input file name
self.weight = None # features weight
self.feat_dim = 2**feat_dim # max size of feature vector
self.bitmask = 2**feat_dim - 1 # mapping dimension
self.loss_type = loss_type # type of loss function
self.eta = 10.0 # learning rate
self.features = None
self.G = np.zeros(self.feat_dim, dtype=np.float64)
self.t = 1 # update times
self.epsilon = 10**(-9)
self.maxfeature = np.zeros(self.feat_dim, dtype=np.float64)
self.N = 0
def train(self,gamma,lambd):
self.gamma = gamma
self.lambd = lambd
self.initialize()
with open(self.fname,'r') as trainf:
for line in trainf:
y = line.strip().split(' ')[0]
self.features = self.get_features(line.strip().split(' ')[1:])
y = int(-1) if int(y)<=0 else int(1) # posi=1, nega=-Quand dire 1
#Prédiction numérique
pred = self.predict(self.weight,self.features)
#normalisation du poids
self.NAG(y,y*pred)
self.t += 1
print self.weight
return self.weight
def initialize(self):
self.weight = np.zeros(self.feat_dim,dtype=np.float64)
def get_features(self,data):
features = np.zeros(self.feat_dim,dtype=np.float64)
for kv in data:
k, v = kv.strip().split(':')
features[int(k)&self.bitmask] += float(v)
return features
def NG(self,y,m):
"""normalisation du poids"""
idx = np.where( (np.abs(self.features)-self.maxfeature)>0 )
#Ajuster le poids
self.weight[idx] *= self.maxfeature[idx]**2/(np.abs(self.features[idx])+self.epsilon)**2
#mettre à jour la valeur maximale
self.maxfeature[idx] = np.abs( self.features[idx] )
#Mettre à jour le coefficient
self.N += sum(self.features**2/(self.maxfeature+self.epsilon)**2)
#mise à jour du poids
loss = self.calc_loss(m)
if loss>0.0:
grad = y*self.calc_dloss(m)*self.features
self.weight -= self.eta*self.t/self.N*1/(self.maxfeature+self.epsilon)**2*grad
def NAG(self,y,m):
"""normalisation du poids"""
idx = np.where( (np.abs(self.features)-self.maxfeature)>0 )
#Ajuster le poids
self.weight[idx] *= self.maxfeature[idx]/(np.abs(self.features[idx])+self.epsilon)
#mettre à jour la valeur maximale
self.maxfeature[idx] = np.abs( self.features[idx] )
#Mettre à jour le coefficient
self.N += sum(self.features**2/(self.maxfeature+self.epsilon)**2)
#Calcul du gradient de poids
grad = y*self.calc_dloss(m)*self.features
self.G += grad**2
self.weight -= self.eta*math.sqrt(self.t/self.N)* \
1/(self.maxfeature+self.epsilon)/np.sqrt(self.G+self.epsilon)*grad
def predict(self,w,features):
ez = np.dot(w,features)
#return 1/(1+math.exp(-ez)) #Ne pas appliquer à la fonction logistique
return ez
def calc_loss(self,m): # m=py=wxy
if self.loss_type == 'hinge':
return max(0,1-m)
elif self.loss_type == 'log':
if m<=-700: m=-700
return math.log(1+math.exp(-m))
# gradient of loss function
def calc_dloss(self,m): # m=py=wxy
if self.loss_type == 'hinge':
res = -1.0 if (1-m)>0 else 0.0 #perte si la perte ne dépasse pas 0=0.Autrement-Par différenciation de m-Devenir 1
return res
elif self.loss_type == 'log':
if m < 0.0:
return float(-1.0) / (math.exp(m) + 1.0) # yx-e^(-m)/(1+e^(-m))*yx
else:
ez = float( math.exp(-m) )
return -ez / (ez + 1.0) # -yx+1/(1+e^(-m))*yx
def update_weight(self,y,m):
"""Mettre à jour le poids après la normalisation
"""
loss = self.calc_loss(m)
if loss>0.0:
grad = y*self.calc_dloss(m)*self.features
self.weight -= self.eta*self.t/self.N*1/(self.maxfeature+self.epsilon)**2*grad
def save_model(self,ofname,w):
with open(ofname,'w') as f:
#Ecrire le type de la fonction de perte
f.write(self.loss_type+'\n')
#Écrire le poids
weight = [str(x).encode('utf-8') for x in w]
f.write(' '.join(weight)+'\n')
#Écriture de la dimension de la quantité de caractéristiques
f.write(str(self.feat_dim).encode('utf-8'))
SCW
python
# coding: utf-8
import numpy as np
import math
from scipy.stats import norm
class ScwTrain(object):
def __init__(self, fname, feat_dim, loss_type, eta, C):
self.fname = fname # input file name
self.feat_dim = 2**feat_dim # max size of feature vector
self.bitmask = 2**feat_dim - 1 # mapping dimension
self.loss_type = loss_type # type of loss function
self.lambd = None # regularization
self.gamma = None # learning rate
self.t = 1 # update times
self.features = np.zeros(self.feat_dim,dtype=np.float64)
self.mean_weight = np.zeros(self.feat_dim,dtype=np.float64)
self.sigma_weight = np.ones(self.feat_dim,dtype=np.float64)
self.alpha = 0
self.beta = 0
self.sai = None
self.pusai = None
self.u = None
self.v = None
self.eta = eta
self.phai = norm.ppf(eta)
self.C = C
def train(self):
with open(self.fname,'r') as trainf:
ex_num = 0
count_y = [0.0, 0.0]
for line in trainf:
y = line.strip().split(' ')[0]
features = line.strip().split(' ')[1:]
y = int(-1) if int(y)<=0 else int(1)
#Prédiction de y
pred = self.predict(self.mean_weight,features)
#calcul de vt
vt = self.calc_v()
ex_num += 1
if self.calc_loss(y)>0:
# update weight
self.update_param(y,y*pred,vt)
if y==-1: count_y[0] += 1
else: count_y[1] += 1
print self.mean_weight
print "data num=", ex_num
print "update time=", self.t
print "count_y=", count_y
return self.mean_weight
def initialize(self):
w_init = np.zeros(self.feat_dim, dtype=np.float64)
return w_init
def update_param(self,y,m,v):
nt = v+float(0.5)/self.C
gmt = self.phai*math.sqrt( (self.phai*m*v)**2+4.0*nt*v*(nt+v*self.phai**2) )
self.alpha = max( 0.0 , (-(2.0*m*nt+self.phai**2*m*v)+gmt)/(2.0*(nt**2+nt*v*self.phai**2)) )
u = 0.25*( -self.alpha*v*self.phai+((self.alpha*v*self.phai)**2 + 4.0*v)**0.5 )**2
self.beta = self.alpha*self.phai/(u**0.5 + v*self.alpha*self.phai)
self.mean_weight += self.alpha*y*self.sigma_weight*self.features
self.sigma_weight -= self.beta*(self.sigma_weight*self.features)**2
self.t += 1
def predict(self,w,features):
val = 0.0
self.features = np.zeros(self.feat_dim,dtype=np.float64)
if w != None:
for feature in features:
k,v = feature.strip().split(':')
val += w[int(k) & self.bitmask] * float(v)
self.features[int(k) & self.bitmask] += float(v)
return val
def calc_v(self):
return np.dot(self.sigma_weight, self.features**2)
def calc_loss(self,y): # m=py=wxy
"""Fonction de perte"""
res = self.phai * math.sqrt( np.dot(self.sigma_weight, self.features**2) ) \
- y * np.dot(self.features, self.mean_weight) #sigma ne stocke que les composants diagonaux
return res
def save_model(self,ofname,w):
with open(ofname,'w') as f:
f.write(self.loss_type+'\n')
weight = [str(x).encode('utf-8') for x in w]
f.write(' '.join(weight)+'\n')
f.write(str(self.feat_dim).encode('utf-8'))
Naive Bayes
Naive Bayes est simple, donc je l'écris en une seule formation et test
python
# coding: utf-8
import numpy as np
import math
class NB(object):
def __init__(self, fname, feat_dim):
self.fname = fname # input file name
self.feat_dim = 2**feat_dim # max size of feature vector
self.bitmask = 2**feat_dim - 1 # mapping dimension
self.t = 1 # update times
self.t_select = 1 # times of?@select sample
self.epsilon = 10**(-9)
self.N=0.0 #Nombre total de cas
self.Ny = np.zeros(2, dtype=np.float64) # y=-1, y=1 titulaire (nombre total)
self.Nxy = np.zeros((2,2**feat_dim), dtype=np.float64) #Somme du nombre d'occurrences de la combinaison des vecteurs y et x
self.propy = None
self.propxy = None
def train(self):
with open(self.fname,'r') as trainf:
for line in trainf:
y = line.strip().split(' ')[0]
self.features = self.get_features(line.strip().split(' ')[1:])
#y = int(-1) if int(y)<=0 else int(1)
y = int(-1) if int(y)<=1 else int(1) # posi=1, nega=-Quand dire 1
#Comptez le nombre de cas
self.N += 1
#Comptez le nombre de y
self.incliment_y(y)
#Compter le nombre de combinaisons de x et y
self.incliment_xy(y)
#Calcul de la valeur de probabilité utilisée pour la prédiction
self.propy = np.log(self.pred_y()+self.epsilon)
self.propxy = np.log(self.pred_xy()+self.epsilon)
for i in xrange(len(self.propy)):
print self.propxy[i]
def test(self, ifname):
with open(ifname,'r') as testf:
ans = np.zeros(4,dtype=np.int64)
for line in testf:
y = line.strip().split(' ')[0]
features = self.get_features(line.strip().split(' ')[1:])
y = int(-1) if int(y)<=0 else int(1)
res = self.test_pred(features)
#Calcul du tableau des résultats
ans = self.get_ans(ans, y, res)
print ans
def get_features(self,data):
features = np.zeros(self.feat_dim)
for kv in data:
k, v = kv.strip().split(':')
features[int(k)&self.bitmask] += float(v)
return features
def incliment_y(self,y):
if y==-1: self.Ny[0] += 1.0
else: self.Ny[1] += 1.0
def incliment_xy(self,y):
if y==-1:
self.Nxy[0] += (self.features!=0)*1.0
else:
self.Nxy[1] += (self.features!=0)*1.0
def test_pred(self,features):
res = np.zeros(2,dtype=np.float64)
for i in xrange(len(self.Ny)):
res[i] = self.propy[i] \
+ sum( self.propxy[i]*((features!=0)*1.0) )
if res[0]>res[1]:
return -1
else:
return 1
def predict(self):
res = np.zeros(2,dtype=np.float64)
predy = np.log(self.pred_y()) #Calcul de la valeur de probabilité de y
predx = np.log(self.predxy()) #Calcul de la valeur de probabilité conditionnelle x de y
res = np.zeros(2,dtype=np.float64)
for i in xrange(len(self.Ny)):
res[i] = predy[i]+sum(predx[i])
if res[0]>res[1]:
return -1
else:
return 1
def pred_y(self):
return self.Ny/self.N
def pred_xy(self):
res = np.zeros((2,self.feat_dim),dtype=np.float64)
for i in xrange(len(self.Ny)):
if self.Ny[i]==0.0:
res[i] = 0.0
else:
res[i] = self.Nxy[i]/self.Ny[i]
return res
def get_ans(self,ans,y,res):
if y==1 and res==1: #Vrai positif
ans[0] += 1
elif y==1 and res==-1: #Faux négatif
ans[1] += 1
elif y==-1 and res==1: #faux positif
ans[2] += 1
else: #Vrai négatif
ans[3] += 1
return ans
if __name__=='__main__':
trfname = 'training data file name'
tefname = 'test data file name'
bf = BF(trfname, 6)
bf.train()
bf.test(tefname)
Résultat expérimental
Les données utilisées dans l'expérience étaient a9a et covtype.binary dans Libsvm dataset.
a9a est une donnée binaire, et covtype est une donnée avec une différence d'échelle de 6000 fois.
Lors de la saisie d'une quantité continue dans NB, une valeur de 1 ou plus était simplement quantifiée comme 1.
De plus, comme covtype.binary ne possède pas d'ensemble de test, 400 000 données ont été échantillonnées et utilisées comme données d'apprentissage.
Les hyper paramètres ne sont pas ajustés en particulier. De plus, je n'ai pas répété.
Les résultats sont les suivants.
Résumé
Il s'avère que la normalisation est importante lors de l'utilisation de données avec des échelles complètement différentes pour chaque variable. En outre, vous pouvez voir que SCW semble converger avec un petit nombre d'échantillons. De plus, comme les résultats de l'apprentissage en ligne varient en fonction de l'ordre d'entrée des données, nous avons mélangé les données et mené des expériences. Je n'ai expérimenté qu'avec SCW et SGD avec normalisation automatique. En conséquence, la SGD a fluctué jusqu'à 3%, mais la précision était relativement stable. D'autre part, SCW fluctue jusqu'à 15%, et si vous léchez les données une seule fois, il semble être relativement sensible à l'ordre des données. Soit dit en passant, ce domaine a également été mentionné dans CROSS 2014 (Matériel sur l'apprentissage automatique de la première moitié de CROSS).
À propos, la normalisation, le lasso, la crête, etc. de SGD sont tous implémentés dans Vowpal Wabbit, nous vous recommandons donc d'utiliser Vowpal Wabbit. La vitesse de calcul est également explosive.
Si vous avez des erreurs, veuillez nous en informer.
Recommended Posts