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 w^*:=argmin_wΣ_iL(x^{(i)},y^{(i)},w)+CR(w) $ L (x ^ {(i)}, y ^ {(i)}, w) $: Fonction de perte, $ R (w) $: Terme de normalisation Je pense que cela peut être représenté par. Le but de l'apprentissage en ligne est de «mettre à jour les poids de manière séquentielle chaque fois qu'une donnée est reçue». Les avantages suivants peuvent être obtenus car le poids est mis à jour séquentiellement et les données sont rejetées.

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

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. result.png

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

Comparaison des classificateurs en ligne
Comparaison des implémentations LDA
Comparaison des programmes d'adaptation
Comparaison de 4 types de frameworks Web Python
Comparaison d'Apex et de Lamvery
Comparaison de la vitesse de la perspective XML Python
Comparaison des outils de migration de base de données autonomes 2020
Comparaison des modules de conversion japonais en Python3
Comparaison de gem, bundler et pip, venv
comparaison de chaînes python / utiliser 'list' et 'in' au lieu de '==' et 'ou'
[EDA] Introduction de Sweetviz (comparaison avec + pandas-profiling)
Comparaison des solutions aux problèmes d'appariement de poids
Comparaison de l'héritage de classe et de la description du constructeur
Essayez la comparaison de vitesse de l'API BigQuery Storage
Astuces: Comparaison de la taille de trois valeurs
Comparaison des frameworks sans serveur Python-Zappa vs Chalice
Comparaison de la régularisation L1 et Leaky Relu
Comparaison de la vitesse de transposition de la matrice par Python
Comparaison de vitesse de murmurhash3, md5 et sha1