Un modo molto semplice di implementare lo Stochastic Gradient Descent nei nostri script è quello di usare l’implementazione di Scikit. La classe SGDClassifier implementa un classificatore che utilizza lo Stochastic Gradient Descent per  classificare valori. Il mio script in python applica questo classificatore sul MNIST database, un dataset contente dei numeri scritti a mano e utilizzati come dataset d’esempio nei problemi di classificazione.

Ho utilizzato questo semplice script inoltre per gareggiare su Kaggle alla competizione https://www.kaggle.com/c/digit-recognizer, dove si chiede di scrivere un classificatore di cifre e fare il submit del punteggio.

Il libro che sto attualmente seguendo e che mi ha permesso di scrivere questo codice è:Hands-On Machine Learning With Scikit-Learn and Tensorflow: Concepts, Tools, and Techniques to Build Intelligent Systems

Questo libro offre una buona introduzione pratica agli algoritmi di machine learning, approfondisce via via nei capitoli tematiche sempre più complesse rimanendo ancorati al codice pur avendo una piccola disgressione matematica.

 

 

 

Di seguito l’esempio del mio Notebook Jupyter dove viene implementato questo approccio.

Il Gradient Descent o Discesa del Gradiente è uno dei più popolari algoritmi di ottimizzazione.

La discesa del gradiente è un algoritmo molto usato nelle reti neurali in quanto è alla base dell’algoritmo di backpropagation, attualmente sono tantissime le librerie che implementano questo algoritmo.

L’idea del Gradiente Descent è quello di minimizzare una funzione obiettivo  J(θ) formata da N parametri  θ, aggiornando il valore dei parametri in base alla differenza con il gradiente negativo di  J(θ) rispetto al parametro considerato. L’aggiornamento del parametro viene aggiornato poi passo passo, secondo un dato valore η, chiamato learning rate.

In parole povere, scendiamo una funzioneJ(θ) passo passo, finchè questa non ci porta verso un valore di massimo o di minimo e noi ci fermiamo a questo.

I modi con cui questo algoritmo si può eseguire sono:

  • Batch Gradient Descent
  • Stochastic Gradient Descent
  • Mini Batch Gradient Descent

Batch Gradient Descent

La Batch Gradient Descent (BGD), o Discesa del Gradiente a Batch, computa la discesa del gradiente per la funzione costo su tutto il Training set:

Dove θ è la funzione costo per l’intero Training set. Con questo metodo dobbiamo calcolare la discesa del gradiente una sola volta, siccome usiamo tutto il nostro Training Set, tuttavia essa può essere molto lenta se il dataset è grande e impossibile da fare se il dataset non entra in memoria.

 

Stochastic Gradient Descent

Lo Stochastic Gradient Descent (SGD), o Discesa del Gradiente Stocastica, computa la discesa del gradiente per ogni elemento del Training set e aggiorna il suo valore volta per volta.

A differenza del Batch Gradient Descent, cioè la discesa del gradiente utilizzando una quantità di dati molto alta, questa tecnica utilizza un solo valore per volta:

Dove θ è la funzione costo per l’intero Training set.

 

Mini Batch Gradient Descent

La Mini Batch Gradiente Descente (MBGD), o Discesa del Gradiente a MiniBatch, è una via di mezzo fra la SGD e la BGD in quanto effettua degli aggiornamenti ai parametri della funzione con dei minibatch, e non con l’intero dataset o con valori singoli, e in questo modo porta a una più veloce convergenza .

 

Questi algoritmi per trovare l’ottimo delle funzioni sono disponibili nella libreria Python Scikit, nel prossimo articolo implementerò un classificatore che utilizza il metodo SGD per classificare delle cifre scritte a mano.

Mining of Massive Datasets è un libro scritto da Jure LeskovecAnand RajaramanJeff Ullman basato sul corso di studi tenuto a Stanford riguardante il Data Mining.

Ogni lezione è poi corredata sul web da dei video presenti su Youtube che spiegano le tematiche dei capitoli, la qualità del corso è molto alta e sono facili da seguire.

Capitoli del libro

Il libro è diviso nei seguenti Capitoli:

  • Data Mining: Il capitolo è una introduzione al libro, parla degli aspetti dei Big Data, del perchè si fa data mining, delle sfide e dei problemi.
  • Map-Reduce and the new Software Stack: Questo capitolo parla di Map-Reduce, del perchè è stato inventato questo approccio, quanto si riesce ad essere più performanti, del perchè è stato inventato in Google e dei problemi che va a risolvere. Si parla inoltre dei sistemi Opensource che implementano MapReduce fra cui Hadoop.
  • Finding Similar Items: Questo capitolo parla di come misurare i dati, cioè di come decidere delle distanze fra i dati e permettere di capire quanto due dati generici possano essere uguali. Tratta delle distanze classiche fra numeri e stringhe e dell’hashing per trovare i dati similin.
  • Mining Data Streams: Questo capitolo tratta degli Stream e come fare Sampling, contare elementi distinti, applicare il Bloom Filter, stimare i Momenti, stimare il numero di elementi in una finestra temporale.
  • Link Analysis: Questo capitolo parla di PageRank, dell’implementazione e il modello su cui si basa, il rischio di avere attacchi spam che possano deviare il risultato di PageRank delle pagine e i metodi per evitare questo tipo di attacchi.
  • Frequent Itemsets: Questo capitolo parla degli insiemi di oggetti frequenti e delle regole di associazione, spiega inoltre l’algoritmo A-Priori e l’algoritmo PCY con ulteriori spunti.
  • Clustering: Questo capitolo tratta il clustering, sia gerarchico che non, esplorando gli algoritmi KMeans, BFR, Cure
  • Advertising on the Web: Questo capitolo tratta del problema della pubblicità sul web, cioè come fare linking fra annunci e oggetti e migliore offerta sulla pubblicità in quel momento.
  • Recommendation Systems: Questo capitolo parla dei sistemi di raccomandazione esponendo quale è il problema della raccomandazione e come si tenta di risolverlo tramite un approccio semantico basato sui tag o tramite un approccio sulle relazioni fra gli oggetti basato sull’algebra lineare
  • Mining Social Network Graphs: Questo capitolo parla delle connessioni nei social network e nelle community applicando algoritmi e rappresentazioni.
  • Dimensionality Reduction: Questo capitolo parla della riduzione delle dimensioni in un dataset e di come applicare la decomposizione SVD e la decomposizione CUR al nostro dataset.
  • Large-Scale Machine Learning: Questo capitolo spiega i concetti di Training Set, Test Set, allenamento in batch o online, e algoritmi classici di machine learning come il Perceptron, le reti neurali e il Nearest-Neighbor

Perchè dovrei leggerlo?

Questo libro esplora le basi del data mining e del machine learning, fornendo le nozioni per argomento via via più complessi. E’ di per sé un libro teorico universitario, non si troverà codice, ma solo pseudo codice e ottime spiegazioni. Il libro inoltre non si perde in teoria inutile, ma va dritto al punto fornendo però il contesto adatto. Ogni algoritmo trattato nel libro può essere poi trovato implementato facilmente online da altri programmatori.

Link

Il corso video si può trovare su youtube:
https://www.youtube.com/channel/UC_Oao2FYkLAUlUVkBfze4jg/videos 

Il libro e le slide invece sono disponibili gratuitamente qui nella versione 2:
http://www.mmds.org/

Nel caso vogliate acquistare invece il libro è possibile comprarlo su amazon al link:

Mining of Massive Datasets

La Filter Bubble (o camera di Eco) di Facebook è la bolla di informazioni che gli algoritmi usati da Facebook decidono di farci vedere. Gli algoritmi di Facebook si basano sull’idea che noi utenti dobbiamo rimanere ingaggiati dalle informazioni basate sui nostri gusti mostrandoci post di pagine e amici, ma il risultato è diverso, vedremo informazioni basate sì sui nostri gusti, sui nostri amici e sulle pagine che seguiamo, ma ignorando le cose e le idee che non fanno parte della nostra sfera.
Inoltre non sapendo come funziona perfettamente l’algoritmo di Facebook per mostrare i contenuti, ma conoscendo quello che i tecnici decidono di dirci possiamo sapere in base a cosa è organizzato in modo approssimativo.

Questa immagine mostra come Facebook decide di farci vedere i post nel News Feed sotto forma di equazione.

La è l’interesse che ha l’utente corrente per il creatore del post.
La P è la performance del post con gli altri utenti
La C è le performance dei post passati dell’utente rispetto gli altri utenti.
La T è il tipo di post che l’utente corrente preferisce
La R è quanto sia nuovo il post.

Unendo questi fattori riusciamo a capire approsimativamente come viene formata la Filter Bubble in cui ci troviamo. Il problema poi aumenta quando pensiamo che non siamo il 100% del nostro tempo su Facebook, ma solo in alcuni momenti della giornata, in cui quindi escono solamente alcuni tipi di argomenti anzichè nuovi e opposti ai nostri gusti.

In tutto questo Facebook tratta le pagine in modo non uguale. Le pagine Facebook vogliono ingaggiare nuovi utenti, tuttavia esse non verranno tratte tutte allo stesso modo, l’utente vede le “Top Stories” di Facebook, cosicchè se una pagina vuole mostrare i propri post sopra gli altri è obbligata a pagare in pubblicità e da tutto questo Facebook ne trae profitto.

Il progetto https://facebook.tracking.exposed si propone di studiare questo fenomeno e di collezionare i dati della propria timeline di Facebook tramite una estensione, di salvarli e analizzarli dopo in locale.
La visione del progetto è di aumentare la trasparenza dietro gli algoritmi di personalizzazione cosicché gli utenti possano avere piu’ coscienza rispetto le proprie scelte e ha come obiettivo di aiutare i ricercatori a capire come gli attuali meccanismi di filtro funzionino e come gli algoritmi di personalizzazione debbano essere modificati per evitare effetti sociali pericolosi.

fbe

L’estensione del progetto è la sonda che viene installata nel nostro browser e invia i dati al backend del sito. L’estensione prende solo i dati pubblici e non i dati privati, il backend fa parsing dei dati ed essi ci vengono mostrati poi a noi in formato csv o in formato metadato estratto.

Un esempio del dato estratto è questo:

Schermata del 2017-09-13 20-25-10

Questi dati e metadati sono disponibili sia come API sia come CSV sia consultabili via interfaccia Web. Il progetto è completamente opensource e disponibile su github.

I nostri dati quindi possono essere estratti ed elaborati localmente per la nostra ricerca o per il nostro divertimento. Ho installato l’estensione su Chrome e ho seguito il semplice tutorial per attivarla, ho aspettato quindi qualche giorno per raccogliere i dati.
Ho scaricato il file CSV della mia Timeline di Facebook nei giorni scorsi e l’ho analizzato per vedere quanti amici hanno messo il partecipo a un evento ed è stato mostrato sulla mia Timeline di Facebook.

Quello che voglio dimostrare è che il mio grafico potrebbe dimostrare che durante la settimana, in prossimità del weekend il numero di notizie relative a gente che partecipa a eventi aumenta.

Non resta altro che collezionare altri dati e cercare di capire se questa ipotesi è vera.