di ·0 commenti

In questo blog post cercheremo di capire come le chiamate di Inotify arrivano a livello kernel, passando per la libreria di interfaccia del sistema (libc).

Se effettuiamo strace del nostro programma vediamo le chiamate effettuate dal nostro processo.

Strace e’ un comando che registra le syscall fatte dal nostro processo in user space verso il kernel in kernel space, ci ritorna come output la system call, i parametri che passiamo il valore di ritorno. Lo eseguiamo sul programma che abbiamo creato nel precedente articolo http://www.spaghettiml.com/2019/02/01/come-funziona-inotify-parte-1/

Compiliamo il programma ed eseguiamo quindi strace:

gcc inotify_example.c && strace ./a.out 

Ora, a noi interessa capire come venga chiamata la funzione: inotify_add_watch

...
inotify_add_watch(3, "/home/joxer/code", IN_ACCESS|IN_MODIFY|IN_ATTRIB|IN_CLOSE_WRITE|IN_CLOSE_NOWRITE|IN_OPEN|IN_MOVED_FROM|IN_MOVED_TO|IN_CREATE|IN_DELETE|IN_DELETE_SELF|IN_MOVE_SELF) = 1
...

Questa e’ la system call che viene chiamata quando nel nostro codice effettuiamo inotify_add_watch( inotifyFd, bufPtr, IN_ALL_EVENTS );
Si vede qui, come la costante IN_ALL_EVENTS venga espansa e 3 indichi il file descriptor sul quale stiamo agendo.

Ora, dove possiamo trovare questa system call? Ci basta cercare nel source code del kernel Linux e troviamo il file inotify_user.c che la contiene
https://github.com/torvalds/linux/blob/master/fs/notify/inotify/inotify_user.c#L696

In un successivo articolo trattero’ del corpo della funzione, per ora mi limitero’ a illustrare come viene effettuata la chiamata dallo user space in kernel space.

Ora, come viene invocata una system call da libc nel kernel?
Questo dipende dall’architettura e da come vengono passati i parametri al kernel

Sia su sistemi x86 che su sistemi x86_64, Linux effettua una system call chiamando l’interrupt 0x80, ovvero usando l’istruzioneint $0x80
Sui sistemi x86_64 e’ disponibile, ed e’ definita come predefinita, l’istruzione syscall, al posto dell’interrupt 0x80.
I parametri vengono passati settando i registri nel seguente modo:

I valori associati a ogni system call, cioe’ il valore che dobbiamo mettere nel registro eax per chiamare le syscall vengono generati nel file arch/x86/include/generated/uapi/asm/unistd_32.h o usr/include/asm/unistd_32.h

Se vogliamo chiamare la system call dallo user space, il metodo e’ usare <sys/syscall.h> con la funzione long syscall(long number, …)
Questa funzione effettua le seguenti azioni:

  • Copia gli argomenti e setta il numero della system call nei registri del processore dove il kernel si aspetta di trovarli
  • Viene effettuata la trap in kernel mode, si passa in kernel mode e ora e’ il kernel ad avere il comando ed effettuare il codice
  • Se la system call ritorna un errore, viene settato errno e la cpu torna in user mode

Libc effettua del wrapping attorno le system call del kernel o le chiama direttamente. Ulteriori informazioni su questo si possono trovare alla pagina: https://sourceware.org/glibc/wiki/SyscallWrappers

Se visualizziamo il codice assembly per il nostro eseguibile possiamo vedere come viene chiamata la nostra funzione inotify_add_watch:

 gcc -g file.c
 objdump -d -S a.out

Qui possiamo vedere le seguenti linee:

int wd = inotify_add_watch( inotifyFd, bufPtr, IN_ALL_EVENTS );
a02: 48 8b 8d 20 f5 ff ff mov -0xae0(%rbp),%rcx
a09: 8b 85 04 f5 ff ff mov -0xafc(%rbp),%eax
a0f: ba ff 0f 00 00 mov $0xfff,%edx
a14: 48 89 ce mov %rcx,%rsi
a17: 89 c7 mov %eax,%edi
a19: e8 62 fd ff ff callq 780 <inotify_add_watch@plt>
a1e: 89 85 08 f5 ff ff mov %eax,-0xaf8(%rbp)

Quindi vediamo la riga: callq 780 <inotify_add_watch@plt> che chiama la funzione

0000000000000780 <inotify_add_watch@plt>:
780: ff 25 42 18 20 00 jmpq *0x201842(%rip) # 201fc8 <inotify_add_watch@GLIBC_2.4>
786: 68 07 00 00 00 pushq $0x7
78b: e9 70 ff ff ff jmpq 700 <.plt>

Si vede una jmpq alla riga 780 verso la funzione di glibc linkata dal mio programma. Questa e’ scritta come un riferimento a @plt

PLT e’ la Procedure Linkage Table, una tabella inclusa nel nostro eseguibile contenente gli indirizzi delle funzioni la quale risoluzione non e’ conosciuta in tempo di linking ed e’ lasciata come compito per il dynamic linker quando il programma viene eseguito.

GOT e’ la Global Offsets Table, ed e’ usata in modo simile per risolvere gli indirizzi. Tuttavia la GOT contiene una tabella fissa di questi indirizzi all’interno dell’eseguibile, in questo modo la PLT e’ dinamica ogni volta che si esegue il processo, invece la GOT e’ statica e il nostro programma conosce sempre in quale punto possono essere trovati i riferimenti alle funzioni. La GOT viene aggiornata in tempo di esecuzione del processo da parte del linker.
Usiamo il comando readelf sul nostro eseguibile, la flag –relocs mostra la sezione relocations del nostro eseguibile.

$ readelf –relocs a.out

Relocation section '.rela.plt' at offset 0x608 contains 9 entries:
   Offset          Info           Type           Sym. Value    Sym. Name + Addend
 000000201f90  000200000007 R_X86_64_JUMP_SLO 0000000000000000 puts@GLIBC_2.2.5 + 0
 000000201f98  000300000007 R_X86_64_JUMP_SLO 0000000000000000 pathconf@GLIBC_2.2.5 + 0
 000000201fa0  000400000007 R_X86_64_JUMP_SLO 0000000000000000 printf@GLIBC_2.2.5 + 0
 000000201fa8  000500000007 R_X86_64_JUMP_SLO 0000000000000000 getcwd@GLIBC_2.2.5 + 0
 000000201fb0  000600000007 R_X86_64_JUMP_SLO 0000000000000000 read@GLIBC_2.2.5 + 0
 000000201fb8  000900000007 R_X86_64_JUMP_SLO 0000000000000000 inotify_init@GLIBC_2.4 + 0
 000000201fc0  000a00000007 R_X86_64_JUMP_SLO 0000000000000000 malloc@GLIBC_2.2.5 + 0
 000000201fc8  000b00000007 R_X86_64_JUMP_SLO 0000000000000000 inotify_add_watch@GLIBC_2.4 + 0
 000000201fd0  000c00000007 R_X86_64_JUMP_SLO 0000000000000000 exit@GLIBC_2.2.5 + 0

In grassetto possiamo vedere l’offset della nostra funzione. I campi del comando readelf –relocs sono i seguenti:

  • Offset: e’ l’offset che il nostro simbolo avra’
  • Info: Ci indica l’indice del simbolo nella symbol table
  • Type: Ci indica il simbolo secondo la ABI (Application binary interface)
  • Sym value: e’ il padding che dobbiamo aggiungere per il symbol resolution
  • Sym name and addend: indica il nome del simbolo piu’ il padding

Se vogliamo vedere la sezione GOT del nostro eseguibile possiamo eseguire il comando che ci da’ il dump della sezione .got: objdump -j .got -s a.out

a.out: file format elf64-x86-64

Contents of section .got:
201f78 881d2000 00000000 00000000 00000000 .. ………….
201f88 00000000 00000000 16070000 00000000 …………….
201f98 26070000 00000000 36070000 00000000 &…….6…….
201fa8 46070000 00000000 56070000 00000000 F…….V…….
201fb8 66070000 00000000 76070000 00000000 f…….v…….
201fc8 86070000 00000000 96070000 00000000 …………….
201fd8 00000000 00000000 00000000 00000000 …………….
201fe8 00000000 00000000 00000000 00000000 …………….
201ff8 00000000 00000000 ……..

ed eseguendo il comando objdump -R a.out, otteniamo i relocation records della nostra GOT quando il programma viene lanciato.

a.out: file format elf64-x86-64

DYNAMIC RELOCATION RECORDS
OFFSET TYPE VALUE
0000000000201d78 R_X86_64_RELATIVE ABS+0x00000000000008b0
0000000000201d80 R_X86_64_RELATIVE ABS+0x0000000000000870
0000000000202008 R_X86_64_RELATIVE ABS+0x0000000000202008
0000000000201fd8 R_X86_64_GLOB_DAT _ITM_deregisterTMCloneTable
0000000000201fe0 R_X86_64_GLOB_DAT libc_start_main@GLIBC_2.2.5 0000000000201fe8 R_X86_64_GLOB_DAT __gmon_start
0000000000201ff0 R_X86_64_GLOB_DAT _ITM_registerTMCloneTable
0000000000201ff8 R_X86_64_GLOB_DAT __cxa_finalize@GLIBC_2.2.5
0000000000201f90 R_X86_64_JUMP_SLOT puts@GLIBC_2.2.5
0000000000201f98 R_X86_64_JUMP_SLOT pathconf@GLIBC_2.2.5
0000000000201fa0 R_X86_64_JUMP_SLOT printf@GLIBC_2.2.5
0000000000201fa8 R_X86_64_JUMP_SLOT getcwd@GLIBC_2.2.5
0000000000201fb0 R_X86_64_JUMP_SLOT read@GLIBC_2.2.5
0000000000201fb8 R_X86_64_JUMP_SLOT inotify_init@GLIBC_2.4
0000000000201fc0 R_X86_64_JUMP_SLOT malloc@GLIBC_2.2.5
0000000000201fc8 R_X86_64_JUMP_SLOT inotify_add_watch@GLIBC_2.4
0000000000201fd0 R_X86_64_JUMP_SLOT exit@GLIBC_2.2.5

Vediamo come gli indirizzi presenti nell’offset sono esattamente quelli presenti quando vediamo il contenuto della sezione GOT. Inoltre, se vediamo la riga:

780: ff 25 42 18 20 00 jmpq *0x201842(%rip) # 201fc8 <inotify_add_watch@GLIBC_2.4>

Vediamo che il valore 201fc8 e’ quello dove, nella nostra GOT, troviamo il punto dove ci si aspetta di trovare l’indirizzo della funzione inotify_add_watch della libreria GLIBC.

Quindi i nostri programmi vengono linkati verso le funzioni esterne di glibc per poter chiamare la syscall.
Se lanciamo objdump per vedere il contenuto della nostra libc avremo il seguente output:

objdump -d -S /lib/x86_64-linux-gnu/libc.so.6 | grep inotify_add_watch -A 10

00000000001222d0 :
   1222d0:    b8 fe 00 00 00          mov    $0xfe,%eax
   1222d5:    0f 05                   syscall
   1222d7:    48 3d 01 f0 ff ff       cmp    $0xfffffffffffff001,%rax
   1222dd:    73 01                   jae    1222e0 
   1222df:    c3                      retq
   1222e0:    48 8b 0d 81 8b 2c 00    mov    0x2c8b81(%rip),%rcx        # 3eae68 
   1222e7:    f7 d8                   neg    %eax
   1222e9:    64 89 01                mov    %eax,%fs:(%rcx)
   1222ec:    48 83 c8 ff             or     $0xffffffffffffffff,%rax
   1222f0:    c3                      retq
   1222f1:    66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
   1222f8:    00 00 00
   1222fb:    0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)

Abbiamo quindi capito come i nostri programmi possono accedere al kernel space per poter eseguire le system call e come vengono linkati tramite il linker in tempo di esecuzione verso le funzioni che non sono ancora conosciute.
Nel prossimo articolo trattero’ il sorgente del kernel cercando di capire come funziona inotify e come vengono create veramente le system call dentro Linux.

di ·1 commento

Leggevo il libro The linux programming interface e finalmente mi sono interessato di come Inotify funzioni su Linux

Semplicemente Inotify e’ un sistema di notifiche per cambiamenti su filesystem per file e directory, come accesso, modifica e esecuzione. E’ stato sviluppato per sostituire dnotify, il vecchio sistema di notifiche su cambiamenti del filesystem. Inotify si basa sui file descriptor, vengono aperti quando si vuole interrogare il sistema di cambiamenti di un singolo file e vengono letti con la system call read()

Il flusso delle system call e’ il seguente:

  • Il nostro programma usa inotify_init() per creare una istanza di inotify
  • Quindi usiamo la chiamata inotify_add_watch() per aggiungere un elemento alla watchlist (la lista degli elementi che osserviamo) e dichiariamo gli eventi sui quali vogliamo ascoltare
  • Effettuiamo una read() sul file descriptor che abbiamo ottenuto nel passo precente. La chiamata read() non torna solo un dato, ma diversi eventi.
  • Quando la nostra applicazione termina, chiudiamo i file descriptor associati con inotify

Di seguito, ecco la struttura di un evento inotify e la spiegazione che ho seguito dal libro.

struct inotify_event {
  int wd; /* Watch descriptor on which event occurred */
  uint32_t mask; /* Bits describing event that occurred */
  uint32_t cookie; /* Cookie for related events (for rename()) */
  uint32_t len; /* Size of 'name' field */
  char name[]; /* Optional null-terminated filename */
 };


Questa struttura contiene tutti i dati rilevanti che ci aiutano a comprendere da dove questo evento venga. wd e’ il file descriptor sul quale siamo in osservazione, mask e’ una integer mask che ci aiuta a capire quale evento e’ avvenuto facendo una & bitwise con la costante dell’evento, cookie e’ un campo che viene usato per gli eventi che succedono con la syscall rename(), len indica la lunghezza del campo name, name e’ il campo che indica il nome del file sul quale l’evento e’ avvenuto.

Di seguito, allego un semplice programma che ho scritto che riceve una notifica ogni volta che un utente invoca un comando ls sulla directory corrente o sulla directory padre.

di ·0 commenti

Un problema molto divertente da risolvere è quello della Bandiera Olandese o in inglese Dutch National Flag Problem.

Il problema e’ stato postulato da Edsger Dijkstra, il famoso informatico per l’algoritmo sui grafi.

Questo problema si formula così: Abbiamo un array non ordinato formato da N valori numerici, che sono o 0 o 1 o 2. Il nostro compito è ordinarlo.
Quindi mi trovo in una situazione del genere:

[0,1,2,0,1,1,2,0,2,1,0,0,1,1,2,2]

Quale è il modo per ordinarli?

La risposta che per prima ci verrebbe in mente è usare un merge sort o un quick sort, per avere una complessita’ computazionale pari a n*log(n).
Addirittura modificando il quicksort si potrebbe ricavare un algoritmo molto molto veloce, in quanto si salterebbe la fase dopo la scelta del pivot (che ricadrebbe sempre su 1).

Tuttavia c’e’ un modo molto piu’ interessante di gestire il problema.

Possiamo pensare all’array come alle tre strisce di una bandiera (da cui il nome del problema), quindi abbiamo 3 tipi di valori che dobbiamo sistemare e sappiamo per certo che ci saranno 2 indici che ne decideranno il limite.
Il primo, che nominerò “basso“, indicherà quando i valori pari a 0 dentro l’array finiranno, Il secondo, che nominerò “alto“, invece si troverà dove i valori pari a 2 inizieranno.
Un terzo indice, che chiamerò “mobile“,  indica i valori pari a 1,  esso si sposterà dalla posizione 0 e man mano arriverà dove inizieranno quelli pari a 2.
Quando l’indice mobile sarà uguale all’indice alto avremo finito.

Iniziamo settando l’indice basso e l’indice mobile alla posizione 0, e l’indice alto alla fine dell’array.
Essi verranno incrementati o decrementati e usati come posizione per scambiare i valori dentro l’array a seconda dell’elemento corrente che viene esaminato.

Questo approccio ha una complessita’ computazionale pari a N, perche’ varia in funziona del numero di valori dentro l’array e la complessità relativa alla memoria occupata è pari a 1

Lascio sotto il codice scritto in python su github per mostrare questo approccio.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

dutchflag.ipynb

hosted with ❤ by GitHub

di ·0 commenti

In questo articolo presenterò dei libri che ho trovato ottimi per iniziare o migliorare nel mondo del machine learning. Come ben si sa non è facile iniziare in questo campo da 0 senza avere una conoscenza della matematica e in parte degli argomenti propri del settore, con questa lista spero di aiutarvi a iniziare in questo mondo. Partiamo con la lista!

Machine Learning for Hackers

★★★★★



Questo libro tratta le tematiche di machine learning con molta semplicità, prima viene esposta la teoria e poi viene corredato l’esempio con Python o R. Gli esempi sono semplici e molto bene commentati, non è difficile seguire l’ordine degli argomenti proposti dal libro. I capitoli che lo compongono si basano su argomenti sia teorici che pratici e si va dai problemi di classificazione a metodi di visualizzazione.
Il libro è molto basilare ed è adatto a un programmatore che inizialmente vuole approcciarsi a questo mondo e avere una infarinatura senza finire in pura teoria. Gli esempi sono corredati da codice su Github e vengono offerti alcuni spunti per sistemi in produzione che utilizzano questi algoritmi.

Hands-On Machine Learning With Scikit-Learn and Tensorflow: Concepts, Tools, and Techniques to Build Intelligent Systems

★★★★★



Questo libro è molto più pratico del precedente. Esso illustra gli algoritmi più importanti e copre sia la parte di machine learning classica, che di Deep learning. I modelli di machine learning trattati sono: Classificatori con Stocastic Gradient Descent, Regressione Semplice e regressione Logistica, Support Vector Machine, Decision Tree, Ensamble, Random Forest, Riduzione delle dimensionalità e infine reti neurali feed forward e recurrent utilizzando Tensorflow. Il libro usa Python come linguaggio di riferimento, è molto chiaro e semplice comprendendo tutti i punti che sono richiesti in un progetto vero e proprio come l’ottimizzazione dei modelli e la loro valutazione.
Il libro è più avanzato del precedente, espone gli algoritmi piu’ richiesti in questo campo e la loro applicazione. Lo consiglio per chi vuole avere una panoramica generale.

Pattern Recognition And Machine Learning

★★★★★



Questo libro è un vero classico del Machine Learning, all’interno è contenuta tutta la teoria matematica sottostante a ogni modello ed algoritmo più usato. L’approccio dell’autore è puramente probabilistico basato sulla teoria bayesiana.
Viene trattato il tutto partendo dalle basi: si inizia dalla teoria della probabilità, poi la teoria dell’informazione e la statistica per arrivare ai modelli lineari, alle reti neurali e ai metodi kernel. Purtroppo questo libro manca di applicazioni a livello di codice rimanendo di teoria, tuttavia è una base fondamentale per chiunque voglia approndire queste tematiche.
Il sito web del libro è disponibile a questo link: https://goo.gl/uFpD7i

Machine Learning: An Algorithmic Perspective, Second Edition

★★★★★



In questo volume vengono trattati elementi di machine learning e data mining dal punto di vista algoritmico e pratico. È molto più diretto del libro di Bishop e più complesso dei primi due in quanto tratta sì le formule matematiche nello specifico, ma non va a spiegarne ogni punto ed è secondo me molto utile per completare la conoscenza della teoria con gli algoritmi.
È un libro consigliato, la qualità dell’esposizione del libro rimane alta ed è per questo molto utile per integrare le conoscenze.

di ·0 commenti

In questo articolo spiegherò come fare una analisi basilare di un dataset da me creato e di come applicare il modello di Decision Tree con Python. Ho utilizzato Scikit e Pandas per la parte di analisi dati e dataframe, per la parte relativa ai grafici ho scoperto ultimamente questa libreria Seaborn che va a sostituire a matplotlib.

Il dataset che prendo in considerazione è stato costruito da me facendo un semplice scraping della pagina di ogni regione di Booking.com . Dopo avere effettuato lo scraping, fatto a mano dal sito, ho preso ogni singola città e ne ho categorizzato un tipo possibile di turismo.
Esso è costituito da: Nome città, regione, Hotel, Latitudine, Longitudine, tipo di turismo
Nella pratica considero tutte le regioni italiane e elenco le prime 25 città per numero di hotel. Il dataset è disponibile in fondo al blogpost.

L’analisi che farò sarà quella di creare dei Decision Tree sul dataset in base al tipo di turismo, usando più o meno diverse feature in tre casi differenti e vedendo quale dei tre casi funziona meglio. Infine userò le funzioni interne delle librerie di scikit per creare la grafica.
Ecco il gist contenente tutti procedimenti commentati passo passo.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

Decision Tree Example.ipynb

hosted with ❤ by GitHub

Ecco ora il dataset che ho usato per la mia analisi dei dati. Lo potete usare sotto licenza GPL v2

di ·0 commenti

I Decision Tree o Alberi Decisionali sono uno strumento di apprendimento supervisionato, essi risolvono principalmente tematiche di classificazione o regressione. Sono molto facili da interpretare e da applicare, non basandosi su un modello lineare sono capaci di apprendere anche associazioni non lineari. Funzionano sia su dati numerici che categorici.

I Decision Tree si categorizzano rispetto alla variabile in output come:

  • Categorical Decision Tree
  • Continuous Decision Tree

Nella figura seguente si vede un esempio di Decision Tree sul dataset di Iris.

  • Il nodo principale si chiama Root Node o Radice
  • Quando un nodo porta a una divisione in rami nei sottonodi l’operazione si chiama Splitting
  • Quando un nodo si divide in più sottonodi senza arrivare a quello finale, i sottonodi si chiamano Decision Node o Nodo di decisione
  • Una intera sezione dell’albero si chiama Branch o Ramo

Vantaggi dei Decision Tree

  • Sono facili da capire: Siccome essi offrono una rappresentazione grafica molto facile da interpretare, i Decision Tree sono anche interpretabili dalla gente non propria del campo informatico.
  • Utili nell’analisi del dataset: Siccome sono un algoritmo molto veloce e semplice da applicare, è utile applicarlo per vedere le relazioni fra le variabili

Svantaggi dei Decision Tree

  • Sono proni all’overfitting: È il problema più frequente con i Decision Tree, il metodo migliore per risolverlo è settare dei vincoli o fare Pruning dei rami

Divisione in rami

Il criterio secondo il quale l’algoritmo divide in più rami i vari nodi dell’albero è critico per la precisione deloritmo. Esso poi è differente nel caso si scelga un ambito di regressione o un ambito di classificazione. In base ai criteri disponibili abbiamo i seguenti approcci:

  • Gini Index (o indice Gini): L’indice Gini dice calcola se gli elementi considerati fanno parte della stessa popolazione. Se la popolazione è pura essi devono essere della stessa classe e la probabilità associata a questo evento è 1 (cioè non contiene elementi di classe diverse)
  • Chi-Square (o Chi quadrato): L’algoritmo Chi Square si preoccupa di trovare una significanza statistica fra i sotto nodi e il nodo padre. Questa la misuriamo sommando il quadrato delle differenze standardizzate fra i valori osservati e i valori che ci aspettiamo
  • Information Gain: L’algoritmo Information Gain si basa sul principio di entropia di un insieme di dati, e usa questo per calcolare la divisione in rami.
  • Riduzione della varianza: Questo algoritmo utilizza la formula della varianza per decidere il migliore modo per dividere i rami, minore è la varianza maggiore è la probabilità che quell’attributo venga usato per dividere i rami

Overfitting

Il problema principale dei Decision Tree è dovuto all’overfitting. Essi arriveranno a fare tante osservazioni, fino ad arrivare a fare una foglia per ogni osservazione e raggiungere quindi il 100% di precisione. Per ridurre questo problema ci sono i seguenti approcci:

  • Si settano dei vincoli sul numero massimo di foglie o sul numero massimo di nodi finali o sul numero massimo di attributi su cui creare nuove foglie. Allo stesso modo anche sul numero minimo di foglie e sul numero minimo di elementi su cui creare nuove foglie
  • Si fa il Pruning dei rami, cioè si eliminano i rami possibili, attraverso un approccio greedy. Nella pratica si sceglie la strada che attualmente sembra la migliore e si prosegue con quella finchè non se ne trovano di migliori

Quando usiamo un Decision Tree?

Dovremmo usare un Decision Tree quando c’è una relazione complessa fra i vari attributi che è difficile da spiegare, in questo modo l’approccio non lineare del Decision Tree batte l’approccio lineare della Regressione Lineare ad Esempio. Inoltre un Decision Tree è molto utile se dobbiamo spiegare come si effettua una classificazione ai non addetti ai lavori.

Nel prossimo articolo includerò degli esempi in Python con la libreria Scikit per mostrare una implementazione dei Decision Tree su un dataset di Regioni città e Attrazioni.

di ·0 commenti

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.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

Classification_SGD_Binary.ipynb

hosted with ❤ by GitHub

di ·0 commenti

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.

di ·0 commenti

Mining of Massive Datasets è un libro scritto da Jure Leskovec, Anand Rajaraman, Jeff 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

di ·0 commenti

In questo articolo spiegherò come creare degli oggetti Clusterizzati in Python usando la libreria SciPy.
SciPy mette a disposizione per noi un sacco di metodi per il Clustering, noi utilizzeremo quelli che abbiamo visto nell’articolo precedente.

Il seguente file IPython fa vedere perfettamente la procedura con un metodo di collegamento fra i cluster di tipo singolo basato sulla distanza euclidea.

Il file ha i commenti che indicano ogni singola operazione avvenuta.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

clustering.ipynb

hosted with ❤ by GitHub