[PYTHON] Vergleich von Online-Klassifikatoren
Motivation
Wie ich letztes Mal schrieb, werden keine Daten in der Firma gespeichert. Es wurde jedoch davon ausgegangen, dass die Daten enorm wären, wenn die Protokolle in Zukunft ordnungsgemäß erfasst würden. In Anbetracht des Umfangs der (Zeit / Raum-) Berechnung entschied ich mich daher, den Online-Lernalgorithmus am besten zu verwenden. (Ich schreibe eine Geschichte unter der Annahme des vorherigen Beitrags. Es ist in vielerlei Hinsicht eine Schande ... orz) Ich habe Online-Klassifikatoren noch nicht richtig verwendet, daher habe ich mehrere Klassifikatoren zur Leistungsbewertung ausprobiert (obwohl dies schon lange her ist ...).
Online-Klassifikatorübersicht
Der lineare Klassifikator ist ungefähr
- Speicherplatz sparen
- Leicht neu zu lernen
Eine Übersicht finden Sie unter Online-Lernen (Vorlesungsunterlagen der Universität Tokio?). Überlegen.
Es gibt verschiedene Arten von Online-Klassifizierern, z. B. rauschresistente und schnell konvergierende Algorithmen, automatische Normalisierung und automatische Parameteranpassung. Dieses Mal verglich ich Exact Soft Confidence-Weight Learning (SCW), Stochastic Gradient Descent (SGD) mit automatischer Parameteranpassung, SGD mit automatischer Normalisierung und Naive Bayes (NB).
Verweise
- No More Pesky Learning Rates, Schaul+, ‘13[pdf]
- Normalized online learning, Ross+, '13[pdf]
- Exact Soft Confidence-Weighted Learning, Wang, ICML‘12[pdf]
- Vorlesungsunterlagen der Maryland University (?) [Pdf] ← Gute Materialien zur Bestätigung der teilweisen Differenzierung des Protokollverlusts Ich denke
Referenzcode
Unten ist der Code, den ich erstellt habe. Ein gewisser Einfallsreichtum besteht darin, dass (1) einfaches Feature-Hashing möglich ist und (2) nur die diagonalen Komponenten der Kovarianzmatrix in SCW gespeichert werden.
SGD mit automatischer Parametereinstellung
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 #Parameter zum Einstellen der Ungleichgewichtsrate
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=-Wann soll man sagen 1
#Numerische Vorhersage
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 #Verlust, wenn der Verlust 0 nicht überschreitet=0.Andernfalls-Durch Differenzierung von m-Werden Sie 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: #Im Fall von 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:
#Schreiben des Typs der Verlustfunktion
f.write(self.loss_type+'\n')
#Schreiben Sie Gewicht
weight = [str(x).encode('utf-8') for x in w]
f.write(' '.join(weight)+'\n')
#Schreiben der Dimension der Feature-Menge
f.write(str(self.feat_dim).encode('utf-8'))
SGD mit automatischer Normalisierung
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=-Wann soll man sagen 1
#Numerische Vorhersage
pred = self.predict(self.weight,self.features)
#Normalisierung des Gewichts
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):
"""Normalisierung des Gewichts"""
idx = np.where( (np.abs(self.features)-self.maxfeature)>0 )
#Gewicht anpassen
self.weight[idx] *= self.maxfeature[idx]**2/(np.abs(self.features[idx])+self.epsilon)**2
#Maximalwert aktualisieren
self.maxfeature[idx] = np.abs( self.features[idx] )
#Aktualisieren Sie den Koeffizienten
self.N += sum(self.features**2/(self.maxfeature+self.epsilon)**2)
#Gewichtsaktualisierung
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):
"""Normalisierung des Gewichts"""
idx = np.where( (np.abs(self.features)-self.maxfeature)>0 )
#Gewicht anpassen
self.weight[idx] *= self.maxfeature[idx]/(np.abs(self.features[idx])+self.epsilon)
#Maximalwert aktualisieren
self.maxfeature[idx] = np.abs( self.features[idx] )
#Aktualisieren Sie den Koeffizienten
self.N += sum(self.features**2/(self.maxfeature+self.epsilon)**2)
#Berechnung des Gewichtsgradienten
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)) #Nicht auf die Logistikfunktion anwenden
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 #Verlust, wenn der Verlust 0 nicht überschreitet=0.Andernfalls-Durch Differenzierung von m-Werden Sie 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):
"""Aktualisieren Sie das Gewicht nach der Normalisierung
"""
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:
#Schreiben des Typs der Verlustfunktion
f.write(self.loss_type+'\n')
#Schreiben Sie Gewicht
weight = [str(x).encode('utf-8') for x in w]
f.write(' '.join(weight)+'\n')
#Schreiben der Dimension der Feature-Menge
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)
#Vorhersage von y
pred = self.predict(self.mean_weight,features)
#Berechnung von 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
"""Verlustfunktion"""
res = self.phai * math.sqrt( np.dot(self.sigma_weight, self.features**2) ) \
- y * np.dot(self.features, self.mean_weight) #Sigma speichert nur diagonale Komponenten
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 ist einfach, also schreibe ich es in einem Training und teste w
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 #Gesamtzahl der Fälle
self.Ny = np.zeros(2, dtype=np.float64) # y=-1, y=1 Inhaber (Gesamtzahl)
self.Nxy = np.zeros((2,2**feat_dim), dtype=np.float64) #Summe der Anzahl der Vorkommen der Kombination von y- und x-Vektoren
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=-Wann soll man sagen 1
#Zählen Sie die Anzahl der Fälle
self.N += 1
#Zähle die Anzahl von y
self.incliment_y(y)
#Zählen der Anzahl der Kombinationen von x und y
self.incliment_xy(y)
#Berechnung des zur Vorhersage verwendeten Wahrscheinlichkeitswertes
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)
#Berechnung der Ergebnistabelle
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()) #Berechnung des Wahrscheinlichkeitswertes von y
predx = np.log(self.predxy()) #Berechnung des bedingten x-Wahrscheinlichkeitswertes von 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: #Richtig positiv
ans[0] += 1
elif y==1 and res==-1: #Falsch negativ
ans[1] += 1
elif y==-1 and res==1: #falsch positiv
ans[2] += 1
else: #Richtig negativ
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)
Versuchsergebnis
Die im Experiment verwendeten Daten waren a9a und covtype.binary in Libsvm-Datensatz.
a9a sind Binärdaten und covtype sind Daten mit einem 6.000-fachen Skalendifferenz.
Bei der Eingabe einer kontinuierlichen Größe in NB wurde ein Wert von 1 oder mehr einfach als 1 quantisiert.
Da covtype.binary keinen Testsatz hat, wurden 400.000 Daten abgetastet und als Trainingsdaten verwendet.
Hyperparameter werden insbesondere nicht angepasst. Außerdem habe ich nicht iteriert.
Die Ergebnisse sind wie folgt.
Zusammenfassung
Es stellt sich heraus, dass die Normalisierung wichtig ist, wenn Daten mit völlig unterschiedlichen Maßstäben für jede Variable verwendet werden. Sie können auch sehen, dass SCW mit einer kleinen Anzahl von Stichproben zu konvergieren scheint. Da die Ergebnisse des Online-Lernens in Abhängigkeit von der Reihenfolge der Dateneingabe variieren, haben wir die Daten gemischt und Experimente durchgeführt. Ich habe nur mit SCW und SGD mit automatischer Normalisierung experimentiert. Infolgedessen schwankte die SGD um bis zu 3%, die Genauigkeit war jedoch relativ stabil. Auf der anderen Seite schwankt SCW um bis zu 15%, und wenn Sie die Daten nur einmal lecken, scheint es relativ empfindlich auf die Reihenfolge der Daten zu reagieren. Dieser Bereich wurde übrigens auch in CROSS 2014 erwähnt (CROSS-Material für das erste Halbjahr).
Übrigens sind SGDs Normalisierung, Lasso, Ridge usw. alle in Vowpal Wabbit implementiert, daher empfehlen wir die Verwendung von Vowpal Wabbit. Die Berechnungsgeschwindigkeit ist ebenfalls explosiv.
Wenn Sie Fehler haben, lassen Sie es uns bitte wissen.
Recommended Posts