Her er modellen bag Version2's emneords-gætteri

Forudsætningerne er helt hen i vejret, men algoritmen fungerer alligevel. Her gennemgår vi modellen Naive Bayes, der har mange år på bagen.

Som vi så i forrige artikel, hvor vi skabte en algoritme, der kan finde emneord for en Version2-historie, er det ikke nødvendigvis så svært at bruge kunstig intelligens og maskinlæring.

Læs også: Java-algoritme gætter Version2's emneord med en træfsikkerhed på 98 pct.

Vi gennemgår her modellen bag algoritmen, men hvis man ikke lige er i humør til at få genopfrisket gymnasiematematikken fra 2.g på B-niveau, som det hed da jeg var ung, er man lovligt undskyldt.

Gennemgangen bygger på et kursus, jeg i sin tid fulgte, og et simpelt gennemregnet eksempel fra kurset kan ses på video. En dybere forklaring kan ses her. Professor Dan Jurafsky fra Stanford University, som er underviseren på videoerne, har også lagt et kapitel fra en kommende lærebog om emnet på nettet. Algoritmen stammer i øvrigt helt tilbage fra 1960’erne.

Bayes i navnet henfører til den engelske matematiker fra 1700-tallet, der opfandt hvad vi på dansk kalder betinget sandsynlighed.

I gymnasiet lærte vi en sætning, som kan bruges til at skabe en model til at gætte på emneord. Den ser sådan ud:

P(emneord|artikel) = P(emneord) * P(artikel|emneord) / P(artikel)

Det siger, at sandsynligheden for at en kendt artikel har et givet emneord, kan udregnes som sandsynligheden for emneordet, ganget med sandsynligheden for, at en artikel har et kendt emneord, delt med sandsynligheden for artiklen.

Det kan lyde noget vidtløftigt, men vi bryder de enkelte dele ned og ender med formlen i forrige artikel. Den sidste faktor, 1/P(artikel), får vi heldigvis ikke brug for - det skyldes en teknikalitet, som vi vender tilbage til.

P(emneord) udregnes som en såkaldt klassisk sandsynlighed, som kvotienten antal artikler med emneordet / antal artikler i alt. Den kvotient finder vi, ligesom resten af tallene, ved at tælle i vores træningssæt.

Tilbage står faktoren P(artikel|emneord). Hvis vi kender emneordet, hvad er så chancen for, at en given artikel er udstyret med dette emneord?

For at komme videre med det spørgsmål, må vi foretage to forsimplinger. Vi antager, at en artikel kan betragtes som en pose ord, hvor rækkefølge og struktur er ligegyldig. Dernæst antager vi, at chancen for, at et ord optræder i en artikel, er uafhængig af et andet ord i samme artikel. Det er disse to antagelser, der er ‘naive’, i navnet Naive Bayes.

Begge antagelser passer nemlig ikke rigtig med virkeligheden, men algoritmen fungerer meget godt alligevel, så pyt med det. Nu kan vi komme videre med vores udtryk fra før.

P(emne|artikel) = P(emne) * P(ord1, ord2, ord3…|emne) / P(artikel)
  = P(emne) * P(ord1|emne) * P(ord2|emne) * P(ord3|emne) * ...  / P(artikel)

(Gymnasiematematikken fortæller os: Da ordene er indbyrdes uafhængige, kan sandsynligheden udregnes ved at gange deres enkelte sandsynligheder.)

Vores problem består nu i at bestemme sandsynligheden for et ord, givet et emne. Lad os sige, at ordet er ‘hospital’, og emnet er ‘sundheds-it.’ Det bestemmer vi også som en klassisk sandsynlighed, ‘antal gunstige delt med antal mulige:’

P('hospital'|'sundheds-it') = antal 'hospital' i sundheds-it-klassen / antal ord i sundheds-it-klassen

Ordet, der ikke fandtes

Det var jo ikke så svært. Men vi har dog et sidste problem: For hvad hvis der optræder et ord i vores testartikel, som vi ikke stødte på i træningssættet?

Vi kunne sige, at denne sandsynlighed er 0, men da det samlede resultat består i at gange alle sandsynlighederne, ender vi med resultatet 0, som vi ikke rigtig kan bruge til noget. Vi giver derfor det ukendte ord sandsynligheden, som hvis vi havde truffet det én enkelt gang i træningssættet, ved at lægge 1 til i tælleren.

P(ord|'sundheds-it') = (hyppighed(ord) + 1) / antal ord i sundheds-it-klassen

Men vi må også lægge noget til i nævneren, for ellers passer pengene ikke. For hvert ord i alle artikler lægger vi nu 1 til i nævneren. Det tal er en anden måde at sige ‘antal unikke ord i alle artikler’ på. Så ser vores formel sådan ud:
P(ord|'sundheds-it') = (hyppighed(ord) + 1) / (antalOrdISundhedsItKlassen + antalUnikkeOrdIAlleArtikler)

Tricket kaldes for 'laplace smoothing' i jargonen. Nu er det ikke rigtigt sandsynligheder, vi snakker om længere. I stedet kalder man det, som tidligere nævnt, et estimat, betegnet P med en hat over, eller Phat.

Nu skriver vi den samlede formel op:

Phat('sundheds-it'|artikel) = P('sundheds-it') * Produktet af ( Phat(ord|'sundheds-it') ) / P(artikel) )

hvor Produktet ovenfor gennemløber alle ord i testartiklen.

Vi betragter nu, som tidligere nævnt, alle de artikler, der ikke har emneordet sundheds-it, som én samlet klasse. Så estimatet for den klasse ser sådan ud:

Phat('ikke-sundheds-it'|artikel) = P('ikke-sundheds-it') * Produktet af ( P(ord|'ikke-sundheds-it') ) /  P(artikel)

Vi beregner nu begge udtryk, og den, der har størst Phat-værdi, har vundet. Da faktoren 1/P(artikel) indgår i begge udtryk og har samme værdi, kan vi bare smide den væk. Den ændrer ikke på, om den ene Phat er større end den anden.

Nu ser problemet sådan ud:

Find den klasse, der giver det største tal i formlen:

Phat(klasse|artikel) = P(klasse) * Produktet af ( Phat(ord|klasse)  )

hvor klasse er 'sundheds-it' eller 'ikke-sundheds-it', og ord gennemløber alle ord i artiklen.

Vi tager nu logaritmen på begge sider af lighedstegnet. Det gør vi for at undgå at gange en masse små tal, der ofte bare ender med at give nul, når vi regner på CPU’en, og fordi det er hurtigere at plusse end at gange. Logaritme-funktionen er støt stigende, så den klasse, der giver højst Phat, giver også højst log(Phat).

Puha - det var en ordentlig omgang, men nu er vi næsten i land. Logaritmen laver vores produkt om til en sum, og nu ser det sådan ud:

log Phat(klasse|artikel) = log(P(klasse)) + Summen af ( log(Phat(ord|klasse)) )

hvor ord gennemløber alle ordene i testartiklen.

Lad os beregne de enkelte led til højre for lighedstegnet:

P(klasse) = antal artikler med klassen / antal artikler i alt

Hvis der er 20 artikler i træningssættet om sundheds-it og 1000 artikler i alt, er P('sundheds-it') = 20 / 1000. Det kaldes for ‘maximum likelihood’, hvor forhåbningen er, at den sande sandsynlighed ligger tæt på frekvensen, målt ud fra træningssættet, hvis blot antallet af artikler i træningssættet er stort nok.

Nu er der kun et led tilbage, der skal beregnes, nemlig Summen af ( log(Phat(ord|klasse)) ).

Indmaden beregner vi med vores formel fra før, ved at bruge vores hyppighedstabel:

Phat(ord|'sundheds-it') = (hyppighed(ord) + 1) / (antalOrdISundhedsItKlassen + antalUnikkeOrdIAlleArtikler)

Nu har vi rigtige tal af kød og blod, eller cifre, på alle elementerne i formlen, og så er det bare at kode og teste, for at se om det virkelig også virker - og er det overhovedet praktisk anvendeligt til vores brugsscenarie?

Det hele kan lyde lidt grovkornet, men målt på træfsikkerhed, eller ‘accuracy’, som det kaldes, kan algoritmen, som vi så i forrige artikel, komme helt op på 98% med visse emneord i vores eksempel.

Men accuracy er ikke alt, som vi skal se i en kommende artikel, hvor vi tuner vores algoritme til at give bedre praktiske resultater. (Og der kommer ikke mere matematik, på spejderære.) Bliv på kanalen.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (2)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Carsten Frigaard

Jeg har gentaget forsøget i Python og SciKit. Der er lidt forskel i vores processering af tekst og min Naive Bayes er ikke helt så god som Java versionen.

Jeg får en confusion matrix som:

  [[285   0]  
   [  9   3]]

og diverse kvalitestsmål som

  precision=1.0, recall=0.25, accuracy=0.97, F1=0.4

Men, interessant for SciKit, er det nu også muligt at gennemsøge en hel række forskellige Machine Learning algoritmer. Med et par liner Python kode søges der nedenfor i ni forskellige ML-algoritmer:

classifiers = [  
    GaussianNB(),  
    KNeighborsClassifier(3),  
    SVC(kernel="linear", C=0.025),  
    SVC(gamma=2, C=1),  
    GaussianProcessClassifier(1.0 * RBF(1.0)),  
    DecisionTreeClassifier(max_depth=5),  
    RandomForestClassifier(max_depth=5),  
    MLPClassifier(alpha=1),  
    AdaBoostClassifier()]  
   
for clf, name in zip(classifiers, names):  
    print(f"Trying model '{name}'...")  
    clf.fit(X_train_tfidf, y_train1)  
   
    ptrain = clf.predict(X_train_tfidf)  
    ptest = clf.predict(X_test_tfidf)

...og jeg får at 'Nearest Neighbor' og 'AdaBoost' performer bedst mht.
accuracy, selvom det er tæt løb blandt modellerne.

Trying model 'Nearest Neighbor'...  
  Results for test  
    found categories=8, expected categories=12  
    total=[289   8],  precision=1.0,  recall=0.667,  accuracy=0.987,  F1=0.8  
    confusion matrix=  
      [[285   0]  
       [  4   8]]  
   
Trying model 'AdaBoost'...  
  Results for test  
    found categories=8, expected categories=12  
    total=[289   8],  precision=1.0,  recall=0.667,  accuracy=0.987,  F1=0.8  
    confusion matrix=  
      [[285   0]  
       [  4   8]]

Bemærk at ingen hyperparametre i modellerne er blevet tunet, og at man via
SciKit nemt kan sætte en global søgning op her. Herudover kan man nemt udvide
Naive Bayes til at dække alle ord, ikke bare 'sundheds-it'. Der vil i begge
dele være tale om at tweake et par parametre samt skrive et par one-liners
python code.

Og koden? Well, i mangel på et GIT-repository kommer den her:

import numpy as np  
import matplotlib.pyplot as plt  
   
import os  
import codecs   
import re  
   
def mk_dat(dir):  
    files = os.listdir(dir)  
    m = []  
    alltxt = []  
    for file in files:  
        if file[-1]!='~':  
            t=""  
            filename=dir + "/" + file  
            with codecs.open(filename,encoding='8859') as f:  
                t = f.read()  
            t = t.replace("\r","")  
            s = t.split("\n")  
   
            assert(len(s)==3)  
            assert(s[2]=="")     # ends in a newline!  
            assert(len(s[0])>1)  # somewhat abitrary limit  
            assert(len(s[1])>1)  # somewhat abitrary limit  
            assert(len(s[0])<80) # somewhat abitrary limit  
   
            k = s[0].strip()        
            v = s[1]  
            assert('  ' not in k)  
            assert('\n' not in alltxt)  
            assert('\r' not in alltxt)  
   
            m.append(k)         
            alltxt.append(v)                  
    return m, alltxt  
   
DBG=0  
   
if DBG==1:  
    root='Dummy/'  
else:  
    root='Ing/'  
   
traincats,traintxt = mk_dat(root + "traeningssaet")  
testcats,testtxt = mk_dat(root + "testsaet")  
print(f"train: len(traincats)={len(traincats)}, len(traintxt)={len(traintxt)}")  
print(f"test:  len(testcats) ={len(testcats)}, len(testtxt) ={len(testtxt)}")  
   
assert(len(traincats)==len(traintxt))  
assert(len(testcats)==len(testtxt))  
assert(len(traincats)==2673 or DBG)  
assert(len(testcats)==297 or DBG)  
   
def mk_cats(cattxt,c,inv_c,n,dbg=False):      
    y = []  
    for k in cattxt:  
        t = []  
        #print(f"{k} -> {len(train[k])}")  
        s = k.split(' ')  
        for i in s:  
            assert(' ' not in i)  
            if not(i in c):  
                if dbg:  
                    print(f"found cat='{i}' as index {n}")  
                c[i]=n  
                assert(not(n in inv_c))  
                inv_c[n]=i  
                n = n + 1  
            t.append(c[i])  
        y.append(t)  
    return c,n,y,inv_c  
   
c = {}  
inv_c = {}  
# test contains on extra 'certificering' category  
c['certificering']=0  
inv_c[0]='certificering'  
n=int(1)  
   
c,n,y_train,inv_c = mk_cats(traincats,c,inv_c,n)  
c,m,y_test,inv_c = mk_cats(testcats,c,inv_c,n,True)   
assert(n==m)  
   
print(f'categories={len(c)}')  
if DBG:  
    print(f"  DBG: {c}")  
    print(f"  DBG: {inv_c}")  
   
assert(len(y_train)==len(traincats))  
assert(len(y_test)==len(testcats))  
assert(inv_c[0]=='certificering')  
assert(inv_c[1]=='cpu')  
assert(inv_c[2]=='sikkerhed')  
assert((len(inv_c)>=168 and inv_c[168]=='sla') or (DBG and inv_c[3]=='sla'))  
assert(c['certificering']==0)  
assert(c['cpu']==1);  
assert(c['sikkerhed']==2);  
assert(c['sla']==168 or (DBG and c['sla']==3));      
assert(len(c)==169 or (DBG and len(c)==4))  
   
def mk_singlecat(y_train,cat):  
    y = []  
    n = c[cat];  
   
    for i in y_train:  
        f=False  
        for j in i:  
            if j==n:  
                f=True  
        if f:  
            y.append(1)  
        else:  
            y.append(0)  
    return y  
   
currcat='sundheds-it'  
print(f"current single category='{currcat}' maps to category index {c[currcat]}")  
y_train1 = mk_singlecat(y_train,currcat)  
y_test1 = mk_singlecat(y_test,currcat)  
   
print(f"  '{currcat}' has {sum(y_train1)} train- and {sum(y_test1)} test-entries")  
   
assert(len(y_train1)==len(y_train))  
assert(len(y_test1)==len(y_test))  
assert(len(y_train1)==len(traincats))  
assert(len(y_test1)==len(testcats))  
   
from sklearn.feature_extraction.text import CountVectorizer  
from sklearn.feature_extraction.text import TfidfTransformer  
   
count_vect = CountVectorizer() #CountVectorizer(analyzer='word', binary=False, decode_error='strict',dtype='numpy.int64', encoding='utf-8', input='content', lowercase=True, max_df=1.0, max_features=None, min_df=1,ngram_range=(1, 1), preprocessor=None, stop_words=None, strip_accents=None, token_pattern='(?u)\\b\\w\\w+\\b', tokenizer=None, vocabulary=None)  
   
X_train = count_vect.fit_transform(traintxt).todense()  
assert(len(y_train1)==X_train.shape[0])  
   
X_test = count_vect.transform(testtxt).todense()  
assert(len(y_test1)==X_test.shape[0])  
   
print(f"lookup a single word: 'ifølge' => {count_vect.vocabulary_['ifølge']}\n")  
   
tfidf_transformer = TfidfTransformer()  
X_train_tfidf = tfidf_transformer.fit_transform(X_train).todense()  
X_test_tfidf  = tfidf_transformer.transform(X_test).todense()  
   
print(traintxt[0])  
print("\n")  
   
inv_X  = count_vect.inverse_transform(X_train)  
print(inv_X[0])  
print("\n")  
   
print(X_train_tfidf.shape)  
print(X_test_tfidf.shape)  
   
assert(X_train_tfidf.shape==X_train.shape)  
assert(X_test_tfidf.shape ==X_test.shape)  
assert(X_train_tfidf.shape[0]==len(traintxt))  
assert(X_test_tfidf.shape[0] ==len(testtxt))  
   
from skmultilearn.problem_transform import BinaryRelevance # pip install scikit-multilearn  
from sklearn.naive_bayes import GaussianNB  
from sklearn.ensemble import RandomForestClassifier  
from sklearn.tree import DecisionTreeRegressor  
from sklearn.svm import SVC  
from sklearn.metrics import confusion_matrix  
from sklearn import metrics  
   
#clf = BinaryRelevance(GaussianNB(),require_dense=[True,False])  
#clf = RandomForestClassifier()  
#clf = DecisionTreeRegressor()  
clf = GaussianNB()  
   
clf.fit(X_train_tfidf, y_train1)  
   
print("DONE")  
   
from sklearn.metrics import accuracy_score, f1_score, precision_score, recall_score, classification_report, confusion_matrix  
   
print("some dummy test data...")  
T = count_vect.transform(['hello world','cpu','sdf sdf hello','text','teraflops fremtiden at','at teraflops','ifølge']).todense()  
p = clf.predict(T)  
print(p)  
print(T)  
print("\n")  
   
ptrain = clf.predict(X_train_tfidf)  
ptest = clf.predict(X_test_tfidf)  
   
def ShowResult(y, p, label, plotcfm=False):  
    print(f"  Results for {label}")  
    print(f"    found categories={sum(p)}, expected categories={sum(y)}")  
   
    # Thus in binary classification, the count of true negatives is  
    #:math:`C_{0,0}`, false negatives is :math:`C_{1,0}`, true positives is  
    #:math:`C_{1,1}` and false positives is :math:`C_{0,1}`.  
    # cfm = [[TN(0,0) FP(0,1)]  
    #        [FN(1,0) TP(1,1)]]  
    cfm = metrics.confusion_matrix(y, p)  
   
    if plotcfm:  
        imshow(cfm)  
        f = figure()  
   
    to = sum(cfm)  
    pr = metrics.precision_score(y, p)  # tp / (tp + fp)  
    rc = metrics.recall_score(y, p)  # tp / (tp + fn)  
    ac = np.trace(cfm) / cfm.sum()  # (TP+TN)/(TP+TN+FP+FN)  
    F1 = metrics.f1_score(y, p)  # F1 = 2 * (precision * recall) / (precision + recall)  
   
    r=3   
    print(f"    total={to},  precision={round(pr,r)},  recall={round(rc,r)},  accuracy={round(ac,r)},  F1={round(F1,r)}")   
    print("    confusion matrix=")  
    print("      "+re.sub('\n', '\n      ', np.array_str(cfm)))   
   
    return F1  
   
   
# In[11]:  
   
   
#from matplotlib.colors import ListedColormap  
#from sklearn.model_selection import train_test_split  
#from sklearn.preprocessing import StandardScaler  
#from sklearn.datasets import make_moons, make_circles, make_classification  
from sklearn.neural_network import MLPClassifier  
from sklearn.neighbors import KNeighborsClassifier  
from sklearn.svm import SVC  
from sklearn.gaussian_process import GaussianProcessClassifier  
from sklearn.gaussian_process.kernels import RBF  
from sklearn.tree import DecisionTreeClassifier  
from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier  
from sklearn.naive_bayes import GaussianNB  
   
names = [  
    "Naive Bayes",  
    "Nearest Neighbors",   
    "Linear SVM",   
    "RBF SVM",   
    "Gaussian Process",  
    "Decision Tree",   
    "Random Forest",   
    "Neural Net",   
    "AdaBoost"  
    ]  
   
classifiers = [  
    GaussianNB(),  
    KNeighborsClassi  
    fier(3),  
    SVC(kernel="linear", C=0.025),  
    SVC(gamma=2, C=1),  
    GaussianProcessClassifier(1.0 * RBF(1.0)),  
    DecisionTreeClassifier(max_depth=5),  
    RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1),  
    MLPClassifier(alpha=1),  
    AdaBoostClassifier()]  
   
for clf,name in zip(classifiers,names):  
    print(f"Trying model '{name}'...")  
    clf.fit(X_train_tfidf, y_train1)  
   
    ptrain = clf.predict(X_train_tfidf)  
    ptest = clf.predict(X_test_tfidf)  
   
    ShowResult(y_train1,ptrain,"train")  
    ShowResult(y_test1,ptest,"test")
  • 3
  • 0
Log ind eller Opret konto for at kommentere