Crea il tuo forum GRATIS su GlobalFreeForum.com.

Bayes for fun and profit

In questa sezione avverranno le discussioni sulla scienza e sulle arti. Si possono chiedere pareri e spiegazioni o postare i propri pensieri a riguardo di un argomento. Qui potete postare spiegazioni su un qualsiasi argomento: matematica, chimica, lingue etc...

Moderatori: Gruppo Admin, Gruppo Mod

Bayes for fun and profit

Messaggioda Flame_Alchemist » 06/08/2012 - 17:16

Information: the negative reciprocal value of probability
-- Claude Shannon


Per un progetto che sto portando avanti [0] ho avuto la necessità di scoprire in che lingua è stato scritto un documento, una cosa che noi diamo abbastanza per scontata, visto che per noi essere umani risulta abbastanza semplice, e anche google lo capisce facilmente, ma che in realtà non è così immediata.

Un giochetto casalingo che ogni tanto funziona consiste nel prendere due testi, piuttosto grandi, in due lingue differenti, comprimerli, annotare le dimensioni, prendere il testo di cui si vuole scoprire la lingua, comprimerlo assieme agli stessi file di prima e vedere nuovamente le dimensioni: il testo è scritto nella lingua corrispondente all'archivio variato meno.
Purtroppo questa tecnica non sempre funziona ed è un po' lenta, quindi si deve trovare un altro metodo.

Iniziamo: applicheremo un po' di semplice machine learning ad un insieme di dati. In particolare ci dedicheremo principalmente a Naive Bayes, utilizzando come dati dei trigrammi nelle varie lingue [1].

I trigrammi
I trigrammi sono semplicemente insiemi di 3 elementi. Noi consideriamo trigrammi formati da lettere, generati da parole in una certa lingua.
Per esempio, la frase "generare trigrammi" può dare luogo a questi trigrammi:
("gen", "ene", "ner", "era", "are", "re ", "e t", " tr", "tri", "rig", "igr", "gra", "ram", "amm", "mmi")

Ogni linguaggio ha delle frequenze di trigrammi piuttosto fisse, per questo al momento i trigrammi vengono considerati tra i metodi migliore per scoprire la lingua di un testo. Si potrebbero utilizzare anche i bigrammi, monogrammi o addirittura 4-grammi, ma hanno dei problemi che nei trigrammi sono molto meno importanti.

Il codice per generare i trigrammi è questo:
Codice: Seleziona tutto
def generate_trigrams(testo):
    for i, c in enumerate(testo[:-2]):
        yield ''.join((c, testo[i+1], testo[i+2]))


Formula di Bayes
Come al solito, prima di tutto un po' di teoria. La formula di Bayes viene usata nel campo delle probabilità condizionate, ovvero probabilità che accada un evento dato che è successo qualcos'altro. Per esempio, si potrebbe considerare la probabilità che la somma dei punteggi su due dadi sia 11 dato che uno dei due dadi mostra 6. Oppure, la probabilità che una email sia di spam sapendo che contiene la parola "casinò".

La formula di Bayes è una formula che si usa per "girare" una probabilità condizionata. Riprendendo l'esempio dello spam:
A. una mail è di spam il 50% delle volte (che si indica con P(spam))
B. il 56% delle email di spam contiene la parola "casinò" (indichiamo questa probabilità con P(casinò|spam))
C. "vincita" appare nel 29% dei casi, fra tutte le email (vale a dire, circa il 2% delle email non di spam contengono "casinò")
Posso calcolare la probabilità che una mail sia di spam, dato che contiene "casinò" (questa probabilità viene indicata con P(spam|casinò))

P(spam|casinò) = P(casinò|spam)*P(spam)/P(casinò)

Nel nostro caso si ottiene:

P(spam|casinò) = 0.56*0.5/0.29 = 0.97

Quindi, una mail che contiene "casinò" è di spam nel 97% dei casi e siamo ragionevolmente sicuri nel segnalarla come tale.
Comunque, nonostante sia la tecnica utilizzata di solito (e in prima battuta) dai principali filtri antispam, non è di questo che volevo parlare.

Noi, tramite i dati raccolti, sappiamo che il trigramma " di" è il più comune in italiano, e appare nel 1.4% dei testi italiani, subito dopo c'è "di " con 1.2%.
In inglese, invece, " di" appare nel 1.2%, mentre "di " addirittura nello 0.002% dei casi.
Quindi, se analizzando il nostro testo troviamo "di " possiamo ragionevolmente assumere che sia italiano.
Formalizzando un po':
P(" di"|italiano) = 0.014 (probabilità che il testo contenga " di" sapendo che è italiano)

P(italiano|"di ") = P("di "|italiano)*P(italiano)/P("di ")

In realtà i nostri testi non conterranno solo il trigramma " di", ma anche molti altri. Possiamo applicare il teorema di Bayes, considerando l'evento congiunto:

P(testo sia italiano | "di " and " di" and ... and "pro" and ...) =
= P("di " and " di" and ... and "pro" and ... | italiano) * P(italiano) / P("di " and " di" and ... and "pro" and ...)

Questo sarebbe il vero teorema di Bayes. Funziona bene, ma è troppo complicato. In particolare P("di " and " di" and ... and "pro" and ... | italiano) è difficile da calcolare (servono troppi dati).
Ora entrano in gioco le assunzioni "naive": i parametri sono indipendenti. Se siete statistici dal cuore debole, forse è meglio che vi fermiate.
E', in molti casi (tra cui questo) una assunzione molto forte. I trigrammi non sono per nulla indipendenti: se un trigramma è "cia", il trigramma successivo sarà quasi sicuramente "iao", invece noi abbiamo supposto che se il primo trigramma è "cia" quello dopo può essere "iao", "olo", "pie", insomma, uno qualunque.
Però la buona notizia è che possiamo sostituire tutti gli and con delle moltiplicazioni.

Una ulteriore buona notizia è che questo metodo serve il suo scopo molto bene ugualmente. L'abbiamo fatto diventare un pessimo stimatore (nel senso che le probabilità calcolate non saranno per niente veritiere), ma è un buon predittore (nel senso che comunque la classe con "probabilità" maggiore sarà quasi sempre giusta).

= P("di "|italiano)*P(" di"|italiano)*... * P("pro"|italiano) * ... * P(italiano) / (P("di ") * P(" di") * ... * P("pro") * ...)

Good news, everyone!: il denominatore non ci interessa. Siccome dobbiamo calcolare almeno due probabilità (P(testo sia italiano|...) e P(testo sia inglese|...)) e poi confrontarle e il denominatore è uguale, visto che è calcolato sul testo, possiamo semplicemente ignorarlo. E neanche P(italiano) ci interessa particolarmente. In generale il classificatore è migliore se si ha anche questa probabilità, ma possiamo farne a meno (assumiamo che sia fissa, pari a 1/N -- N è il numero di lingue che sto considerando --, e quindi non la inseriamo nel calcolo).

Ora invece una cattiva notizia: le probabilità sono molto piccole: si generano moltissimi errori di floating point e tutto il calcolo risulta spesso 0. O si passa ad una rappresentazione che permette di avere precisione molto più elevata o, più semplicemente, passiamo ai logaritmi.

La formula sopra, utilizzando la proprietà che permette di trasformare prodotti in somme, diventa (indico con T[k] i vari trigrammi):

log(P(T1|italiano)) + log(P(T2|italiano)) + ... log(P(T[k]|italiano)) = SOMMA(log(P(T[i]|italiano)) per 0 <= i < n)
Per ogni lingua, L, si calcola:
SOMMA(log(P(T[i]|L)) per 0 <= i < n)

(ho sistemato due errori nelle formule, grazie a Roland, che me li ha fatti notare)

Non tutti i linguaggi avranno tutti i trigrammi necessari, quindi la probabilità sarà 0, che quindi dà un risultato nullo. Per risolvere questo problema applichiamo quello che viene chiamato smoothing laplaciano: maggioriamo tutte le probabilità di un fattore dipendente dalla lunghezza del nostro vocabolario di trigrammi, così nessuna sarà mai zero. (sotto alcune condizioni un classificatore sottoposto a smoothing additivo è ottimale)

Inoltre applichiamo una piccola ottimizzazione che migliora sia le performance sia i risultati: consideriamo solo i trigrammi più frequenti, per esempio i primi 3000. E' inutile andare oltre perché le probabilità diventano molto più piccole (nell'ordine di 10^-5 o ancora minori) e potrebbero falsare i risultati, siccome spesso sono i risultati di testi specialisti, che non sono molto rappresentativi.

A questo punto possiamo calcolare ogni probabilità, e scegliamo la maggiore.

Codice: Seleziona tutto
import collections
import operator
import string
from math import log

def parse_file(name):
    f = open(name)
    x = {}
    c = 0
    i = 0
    for line in f:
        i = i + 1
        if i > 3000:
            break
        line = line.strip().split()
        #questo dataset usa < e > per indicare gli spazi nei trigrammi
        #quindi noi semplicemente li sostituiamo nuovamente
        line[1] = line[1].replace('<', ' ').replace('>', ' ')

        if len(line) == 2:
            x[line[1]] = int(line[0])
            c = c + int(line[0])
    for k in x:
        x[k] = float(x[k]+1)/(c+3000)
    return x

def generate_trigrams(testo):
    for i, c in enumerate(testo[:-2]):
        yield ''.join((c, testo[i+1], testo[i+2]))

def get_trigram_count(testo):
    d = collections.defaultdict(lambda: 0)
    #eliminiamo i caratteri non alfabetici
    testo = filter(lambda x: x in string.letters + ' ', testo)
    for i in generate_trigrams(testo):
        d[i] += 1
    total = sum(d.values())
    for k in d:
        d[k] = d[k]/float(total) #trasformiamo da conteggio in frequenza
    return d

def bayes(testo, langs):
    probs = {x: 0 for x in langs}
    for lang in langs:
        model = parse_file("langid/%s-3grams.txt"%lang)
        highest3000 = sorted(get_trigram_count(testo).iteritems(), key=operator.itemgetter(1), reverse=True)
        for k, v in highest3000:
            try:
                probs[lang] += log(model[k])
            except:
                #se il trigramma non esiste nel dizionario model
                #gli assegnamo probabilità 1/3000.0
                probs[lang] += log(1.0/3000)
    maxl, lang = probs[langs[0]], langs[0]
    for l in probs:
        if probs[l] > maxl:
            maxl = probs[l]
            lang = l
    return lang, maxl

testo = open('nome.txt', 'r').read()
print(bayes(testo, ['it', 'en', 'fr', 'nl']))


____
[0] Il progetto si chiama AsPy, è un manager di documenti personali, la cui caratteristica principale è che dovrà taggare automaticamente i documenti (e correggerli e permettere una ricerca nel testo completo, almeno per txt e pdf, più altre cosine di utilità). Siccome al momento è un progetto che posso stimare completo al 10/20%, e sapete cosa fare alle stime di un programmatore (*), dovrete aspettare un po' per avere nuove notizie.
(*) Di solito si peggiora di 2 e di un ordine di grandezza: 2 settimane --> 4 mesi. 50% --> 2.5%.

[1] Il corpo di testi utilizzato è qui: http://nltk.googlecode.com/svn/trunk/nl ... /index.xml (numero 28)
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda Roland » 19/12/2012 - 16:46

Ho potuto dare solo una lettura veloce.
Quando posso leggerò più attentamente per cercare di capire tutti i passaggi
anche se l'idea di base è abbastanza chiara ed interessante.

Perchè un confronto tra le frequenze delle lettere del testo e le frequenze note non è sufficiente a
decidere in modo sufficientemente sicuro la ingua del testo, ma sono necessari gruppi di tre lettere?

Seconda cosa, mi sfugge il passaggio da prodotti a somme...
log(P(T1|italiano)) + log(P(T2|italiano)) + ... log(P(T[k]|italiano)) = log(SOMMA(P(T[i]|italiano)) per 0 <= i < n)

non dovrebbe essere
log(P(T1|italiano)) + log(P(T2|italiano)) + ... log(P(T[k]|italiano)) = log(PRODUTTORIA(P(T[i]|italiano)) per 0 <= i < k)
?
L'informatica non riguarda i computer più di quanto l'astronomia riguardi i telescopi. (Edsger Wybe Dijkstra)
Avatar utente
Roland
Utente
Utente
 
Messaggi: 91
Iscritto il: 18/11/2007 - 22:04

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 19/12/2012 - 17:33

Essenzialmente si potrebbe fare (e si fa, molto probabilmente). Si dovrebbe applicare un test del chi quadrato, in prima approssimazione. Tika, in Apace, fa cosi' (o faceva, non so se abbiano cambiato).
I risultati, di norma, non sono tanto buoni per testi brevi. Una delle condizioni di utilizzo del test e' che le frequenze relative a tutti (o quasi, di solito la soglia e' il 20%) devono essere >= 5. Su un testo di 100/200 lettere puo' essere limitativo, nel senso che spesso non si hanno cosi' tanti caratteri. Sperimentalmente, invece, si e' verificato che un modello bayesiano permette di raggiungere affidabilita' del 93/95% anche con solo 50 caratteri.

EDIT
Si', solo che ho invertito somma e logaritmo, dovrebbe essere
SOMMA(log(P[i]|language))
Se fosse log(PRODOTTO(P[i]|language)), nonostante sia equivalente da un punto di vista formale, non ridurrebbe il problema degli 0 che annullano il calcolo.
Pero' direi che n e' giusto (indica il numero dei trigrammi considerati).

Ho visto che hai modificato il tuo post: considero i trigrammi perche' provando vari valori (monogrammi, bigrammi, ecc) i trigrammi sono quelli che hanno il miglior compromesso tra qualita' dei risultati e performance. Valori troppo piccoli rendono piu' suscettibile a falsi positivi, (per esempio italiano e inglese hanno frequenze di alcune lettere piuttosto simili), valori troppo grandi (5-gram, o piu'), invece, danno luogo a troppi dati da analizzare. La scelta vera da fare e' tra 3-gram e 4-gram, quindi: avevo un dataset di trigrammi, e ho usato quello.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda Roland » 19/12/2012 - 19:38

Ok, hai confermato i miei sospetti, sia per quanto riguarda la scelta algoritmica che per la formula.

Hai già fatto testing sull'algoritmo su casi limiti o particolari?
Sulle analissi delle frequenze delle singole lettere mi pare ci sia un libro scritto senza nemmeno una 'e'
oppure su testi tecnici che usano con una certa frequenza parole con trigrammi poco probabili (sempre che sia possibile).
L'informatica non riguarda i computer più di quanto l'astronomia riguardi i telescopi. (Edsger Wybe Dijkstra)
Avatar utente
Roland
Utente
Utente
 
Messaggi: 91
Iscritto il: 18/11/2007 - 22:04

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 20/12/2012 - 10:55

Hai già fatto testing sull'algoritmo su casi limiti o particolari?
Sulle analissi delle frequenze delle singole lettere mi pare ci sia un libro scritto senza nemmeno una 'e'
oppure su testi tecnici che usano con una certa frequenza parole con trigrammi poco probabili (sempre che sia possibile).

No, se devo essere sincero non l'ho provato in casi particolari. So che esistono testi "strani" che riducono le possibilita' di un'analisi delle frequenze sulle singole lettere, ma credo che i trigrammi siano molto piu' regolari.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda joker__ » 25/12/2012 - 23:18

Ciao Flame! Anch'io ho dato solo una lettura sommaria (cosa volete, è Natale ;) ) ma domani mattina lo leggo più attentamente. Solo mi è venuto in mente un programmino che avevo fatto, sempre in py, che a partire dalle frequenze con cui apparivano in un testo lettere e coppie di lettere (mi ero fermato alle coppie, e non come te ai trigrammi), mi generava tutte le combinazioni possibili. L'idea era quella di creare un bruteforcer che generasse parole "intelligenti" (mi dava fastidio quando jtr provava come prima password "aaaaaa" ;) ). Fatto sta che questo mio programmino ha "preso fuoco" assieme al mio vecchio hard disk, e da tempo volevo provare a riscriverlo. Pensavo, ora, che potrei farlo basandomi su quanto hai scritto tu. A naso, non sarebbero molte le modifiche. In tal caso ti faccio sapere^^
Comunque, grazie per la condivisione, e buon Natale a tutti!!
Avatar utente
joker__
Utente
Utente
 
Messaggi: 27
Iscritto il: 21/10/2012 - 23:12

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 26/12/2012 - 09:49

Ciao, buon natale anche a te.
Anche io avevo fatto qualcosa del genere. Detto in due parole, la mia idea era qualcosa tipo:
1) parti da n lettere scelte a caso in un testo, consecutive
2) cerca l'occorrenza (a partire da un punto scelto a caso) di quelle lettere
3) usa le n lettere dopo queste appena trovate come punto di partenza per l'iterazione successiva.

Poi ho scoperto che ne aveva parlato Shannon nel suo "a mathematical theory of communication" (io avevo trovato l'idea nel "programming pearls")
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda Al_Chiappone » 26/12/2012 - 13:08

Complimenti Flame_Alchemist, post così se ne vedono pochi ultimamente. L'ho letto con molto interesse.
Avatar utente
Al_Chiappone
Gold Member
Gold Member
 
Messaggi: 667
Iscritto il: 18/11/2007 - 11:25
Località: Rio de Janeiro - RJ - Brasile

Re: Bayes for fun and profit

Messaggioda joker__ » 06/01/2013 - 16:11

Flame_Alchemist ha scritto:Ciao, buon natale anche a te.

(Ri)eccomi Flame, scusa il delay.

Quanto hai scritto è davvero interessante e ben scritto: devi essere conoscitore e molto appassionato di statistica-calcolo probabilistico per scrivere così. L'assunzione che fai tu, ovvero che i diversi trigrammi siano in probabilità di frequenza indipendenti, si potrebbe risolvere con un modello Markoviano (HMM?), in cui lo stato (trigramma) futuro è ammesso in un range di stati, con una certa probabilità rispetto allo stato presente [1].
In effetti, però, l'assunzione non è così distante dalla realtà (in fondo sposti il problema: "le frequenze dei trigrammi in questo testo, a quale modello di lingua si adattano meglio?", il che, a livello pratico è abbastanza discriminante).

Flame_Alchemist ha scritto:Anche io avevo fatto qualcosa del genere. Detto in due parole, la mia idea era qualcosa tipo:
1) parti da n lettere scelte a caso in un testo, consecutive
2) cerca l'occorrenza (a partire da un punto scelto a caso) di quelle lettere
3) usa le n lettere dopo queste appena trovate come punto di partenza per l'iterazione successiva.

Poi ho scoperto che ne aveva parlato Shannon nel suo "a mathematical theory of communication" (io avevo trovato l'idea nel "programming pearls")

In verità non capisco perché partire da lettere scelte a caso nel testo. Il mio script essenzialmente lavorava così: metteva in un array ogni coppia di lettere presenti in un testo, e ordinava queste coppie in ordine decrescente rispetto alla frequenza con cui esse comparivano. Quindi tutte le lettere in un nuovo array, che ordinava allo stesso modo.
Ad esempio
Codice: Seleziona tutto
text="Sono tanto stanco"
c=couples(text)
l=letters(text)
print c
['ta','an','so',....]
print l
['o','n','t','a','s',...]


A questo punto cominciavo a produrre tutte le combinazioni possibili, a partire dalla prima lettera (la più frequente). Le combinazioni erano prodotte in questo modo: data la prima lettera, la completo man mano con le coppie di lettere che cominciano con essa. Quando sono esaurite le coppie di lettere che cominciano per essa, concateno le lettere, a partire dalla più frequente. Era un modo perché tutte le combinazioni (anche quelle più improbabili) fossero soddisfatte, ma solo dopo quelle più frequenti.
A quei tempi, quand'ho scritto questa cosa, non sapevo nulla di statistica.
Rispetto al tuo metodo mi accorgo inoltre di non aver considerato gli spazi: non è scontato che una sia molto frequente, ma mai come prima lettera di parola.

Però secondo me, se si dovesse scrivere uno script del genere, sarebbe utile basarsi sull'analisi di Bayes che hai fatto (Ripeto, come hai detto tu, l'approssimazione è più che sufficiente).
Ora, prova ad immaginare uno script che sia in grado di determinare non solo la lingua, ma anche il modo il cui scrive una persona, le parole che usa di più. Sarebbe interessante scoprire (sono certo che in parte è così), che il modo in cui scrive è una cosa che gli appartiene, e che le sue password stesse ne sono condizionate. Dico "immagina", ma io credo che uno script così fatto, abbia queste potenzialità.

[1] Se pensi che l'HMM non sia una buona soluzione, ti prego, dimmelo. E' una cosa che sto studiando per conto mio (ne ho parlato anche nel mio piccolo blog), e non vorrei mai capire o peggio diffondere idee sbagliate.

PS: codice ben scritto
Avatar utente
joker__
Utente
Utente
 
Messaggi: 27
Iscritto il: 21/10/2012 - 23:12

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 06/01/2013 - 23:04

Bayes e' un classificatore, mentre un modello Markoviano permette di modellare un processo, quindi rappresenta l'evoluzione di un sistema. (A dir la verita' si puo' effettuare una classificazione anche attraverso processi Markoviani, non so come funziona precisamente, ma credo si basi su funzioni di premio e una soglia, ed e' poco usata).
Io sto pensando piu' ad una markov chain che ad un HMM (non mi sembra ci siano dei layer nascosti).
La assunzione di indipendenza non puo' essere risolta in molti modi (per come la intendo io, e' probabile che abbia frainteso): si deve calcolare, sul testo, la probabilita' dell'evento complesso. Solo che questa cosa puo' essere lunga da fare. Il problema verrebbe risolto, ma semplicemente non vale la pena calcolare le probabilita' in modo esatto: si scopre che il classificatore naive funziona bene molto spesso (con dati reali), anche quando le assunzioni non sono perfettamente giustificate (Machine learning is easy!, qualcuno dice).

Una volta nota questa, e' inutile fare l'assunzione naive, infatti conosco in modo esatto la probabilita' dell'evento che nel primo post avevo etichettato come troppo complicato.
Inoltre, a questo punto, potrei anche creare un modello Markoviano.
In verità non capisco perché partire da lettere scelte a caso nel testo.

Effettivamente ai fini pratici non e' particolarmente utile.
Comunque, il mio metodo (e il tuo, che e' abbastanza simile), e' una specie di Markov Chain, solo che non si effettua il calcolo delle frequenze prima, ma si usa un testo come "seme".
E' anche il metodo che usano gli spammer per generare testi da mandare in giro.
Se sei interessato a questo argomento, potresti voler cercare un certo Mark V Shaney: era un bot che postava messaggi su usenet, generati tramite catene markoviane. Il suo codice e' liberamente disponibile (sono poche decine di righe). Inoltre, se sei un fan di EMacs (io vedo solo VIM, mi dispiace), esiste un plugin, che si chiama "dissociated press" (mi pare), che fa questa cosa.
Ora, prova ad immaginare uno script che sia in grado di determinare non solo la lingua, ma anche il modo il cui scrive una persona, le parole che usa di più

Ricordo un sito che, dato un testo, riusciva a trovarne l'autore, o trovava l'autore che scriveva in modo piu' simile al tuo. Purtroppo non mi ricordo il nome, nel frattempo ho trovato questo, che identifica il sesso in base al testo: http://www.hackerfactor.com/GenderGuesser.php. Se si deve suddividere in un numero elevato di classi pero', si necessitano di molti piu' dati.

Inoltre, inserisco qui sotto una nota storica, estratta dall'HACKMEM (Item 176, scritto da Gosper), che riguarda questo argomento.
The "banana phenomenon" was encountered when processing a character string by taking the last 3 letters typed out, searching for a random occourrence of that sequence in the text, taking the letter following that occourrence, typing it out, and iterating. This ensures that every 4-letter string output occurs in the original. The program typed BANANANANANANANANANA... We note an ambiguity in the phrase, "the Nth occurrence of". In one sense, there are five 00's in 0000000000; in another, there are nine. The editing program TECO finds five. Thus it finds only the first ANA in BANANA, and is thus obligated to type N next. By Murphy's Law, there is but one NAN, thus forcing A, and thus a loop. An option to find overlapped instances would be useful, altough it would require backing up N-1 characters before seeking the next N character string.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 09/01/2013 - 16:57

Un paio di link che potrebbero interessarvi, sull'argomento identificazione persone tramite stile di scrittura.
http://events.ccc.de/congress/2011/Fahr ... 81.en.html
http://www.scmagazine.com.au/News/32813 ... users.aspx
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21

Re: Bayes for fun and profit

Messaggioda mamo139 » 22/01/2013 - 00:19

Molto interessante. Approfondiro' sicuramente il discorso quando avro' un po' di tempo :)

Ho provato per divertimento il gender guesser e pare funzionare almeno nel mio caso... gli ho dato un documento formale in inglese che ho redatto e il verdetto e' maschio europeo :D

Genre: Formal
Female = 334
Male = 447
Difference = 113; 57.23%
Verdict: Weak MALE

Weak emphasis could indicate European.


Cosi per curiosita', qual'e' il vantaggio di riconoscere le lingue in questo modo piuttosto che con dei volcabolari?
Penso a software multifunzione che oltre a riconoscere il linguaggio offrono anche servizi tipo correzione ortografica e grammaticale... gia' che hanno in dotazione un vocabolario non fanno meglio ad utilizzarlo anche per l'identificazione della lingua?
Quali dei due sistemi ha pecentuali di successo maggiori?

Vi siete posti queste domande?
bw|Clan @ http://www.bravewarriors.eu/
http://mamo139.altervista.org
Avatar utente
mamo139
Gold Member
Gold Member
 
Messaggi: 1297
Iscritto il: 20/11/2006 - 16:41
Località: Bologna -> Londra

Re: Bayes for fun and profit

Messaggioda Flame_Alchemist » 22/01/2013 - 20:12

Probabilmente utilizzando un metodo basato su dizionario, si otterrebbero risultati piu' velocemente (finche' si hanno pochi linguaggi). Essenzialmente si dovrebbe fare un test Chi quadrato (o qualcosa di simile -- un confronto delle frequenze, insomma). Credo (e alcuni bug report di Apache Tika mi hanno dato conferma) che questo ultimo metodo sia meno affidabile per testi brevi (se ben ricordo, il test del chi quadro richiede che tutte le frequenze siano >= 5).

Gira voce che translate.google.com usi gli ngrammi, e in effetti funziona bene anche con testi brevissimi (poche parole), nonostante supporti diverse decine di lingue. Se usasse le parole probabilmente sarebbe limitato qualora dovrebbe distinguere tra spagnolo e portoghese (immagino che abbiano alcune parole simili), o se per esempio il testo contenesse alcuni errori di ortografia che fanno diventare parole italiane quasi straniere (mentre gli ngrammi sono piu' regolari). Del resto, queste sono speculazioni, magari sto prendendo del tutto un granchio.
To iterate is human, to recurse, divine. — L. P. Deutsch
I could be bound in a nutshell and count myself as a king of infinite space (Hamlet)
Non era proprio un genio – pensava che la figura che lui tracciava sul suo fianco nudo dopo il sesso fosse il numerale 8, per dare un'idea. — D. F. Wallace

N = 1 ==> P = NP [compscient]
Avatar utente
Flame_Alchemist
Gold Member
Gold Member
 
Messaggi: 861
Iscritto il: 14/08/2007 - 18:21


Torna a Il Pozzo della conoscenza

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite

cron