natural language toolkit tnt tagger c 20012023 nltk project sam huston sjh900gmail com url https www nltk org for license information see license txt implementation of tnt a statisical part of speech tagger by thorsten brants https aclanthology orga001031 pdf tnt statistical pos tagger important notes does not automatically deal with unseen words it is possible to provide an untrained pos tagger to create tags for unknown words see init function should be used with sentencedelimited input due to the nature of this tagger it works best when trained over sentence delimited input however it still produces good results if the training data and testing data are separated on all punctuation eg input for training is expected to be a list of sentences where each sentence is a list of word tag tuples input for tag function is a single sentence input for tagdata function is a list of sentences output is of a similar form function provided to process text that is unsegmented please see basicsentchop tnt uses a second order markov model to produce tags for a sequence of input specifically argmax projptiti1 ti2pwiti ptt1 tt ie the maximum projection of a set of probabilities the set of possible tags for a given word is derived from the training data it is the set of all tags that exact word has been assigned to speed up and get more precision we can use log addition to instead multiplication specifically argmax sigmalogptiti1 ti2logpwiti logptt1tt the probability of a tag for a given word is the linear interpolation of 3 markov models a zeroorder firstorder and a second order model pti ti1 ti2 l1pti l2pti ti1 l3pti ti1 ti2 a beam search is used to limit the memory usage of the algorithm the degree of the beam can be changed using n in the initialization n represents the maximum number of possible solutions to maintain while tagging it is possible to differentiate the tags which are assigned to capitalized words however this does not result in a significant gain in the accuracy of the results construct a tnt statistical tagger tagger must be trained before being used to tag input param unk instance of a pos tagger conforms to taggeri type unk taggeri param trained indication that the pos tagger is trained or not type trained bool param n beam search degree see above type n int param c capitalization flag type c bool initializer creates frequency distributions to be used for tagging lx values represent the portion of the tribiuni taggers to be used to calculate the probability n value is the number of possible solutions to maintain while tagging a good value for this is 1000 c is a boolean value which specifies to use or not use the capitalization of the word as additional information for tagging note using capitalization may not increase the accuracy of the tagger statistical tools ignore or delete me uses a set of tagged data to train the tagger if an unknown word tagger is specified it is trained on the same data param data list of lists of word tag tuples type data tuplestr ensure that local c flag is initialized before use if capitalization is requested and the word begins with a capital set local flag c to true set local flag c to false for the next word compute lambda values from the trained frequency distributions creates lambda values based upon training data note no need to explicitly reference c it is contained within the tag variable tag tag c for each tag trigram t1 t2 t3 depending on the maximum value of ft1 t2 t31 ft1 t21 ft2 t31 ft21 ft31 n1 increment l3 l2 or l1 by ft1 t2 t3 issues resolutions if 2 values are equal increment both lambda values by ft1 t2 t3 2 temporary lambda variables for each t1 t2 in system for each t3 given t1 t2 in system note tag actually represents tag c however no effect within this function if there has only been 1 occurrence of this tag in the data then ignore this trigram safediv provides a safe floating point division it returns 1 if the denominator is 0 if c1 is the maximum value if c2 is the maximum value if c3 is the maximum value if c3 and c2 are equal and larger than c1 if c1 and c2 are equal and larger than c3 this might be a dumb thing to do not sure yet otherwise there might be a problem eg all values 0 lambda normalisation ensures that l1l2l3 1 safe floating point division function does not allow division by 0 returns 1 if the denominator is 0 tags each sentence in a list of sentences param data list of list of words type data string return list of list of word tag tuples invokes tagsent function for each sentence compiles the results into a list of tagged sentences each tagged sentence is a list of word tag tuples tags a single sentence param data list of words type data string return word tag calls recursive function tagword to produce a list of tags associates the sequence of returned tags with the correct words in the input sequence returns a list of word tag tuples unpack and discard the c flags param sent list of words remaining in the sentence type sent word param currentstates list of possible tag combinations for the sentence so far and the log probability associated with each tag combination type currentstates tag logprob tags the first word in the sentence and recursively tags the reminder of sentence uses formula specified above to calculate the probability of a particular tag if this word marks the end of the sentence return the most probable tag otherwise there are more words to be tagged if the capitalisation is requested initialise the flag for this word if word is known compute the set of possible tags and their associated log probabilities compute the result of appending each tag to this history otherwise a new word set of possible tags is unknown since a set of possible tags and the probability of each specific tag can not be returned from most classifiers specify that any unknown words are tagged with certainty if no unknown word tagger has been specified then use the tag unk otherwise apply the unknown word tagger now have computed a set of possible newstates sort states by log prob set is now ordered greatest to least log probability del everything after n threshold this is the beam search cut compute the tags for the rest of the sentence return the best list of tags for the sentence helper function basic sentence tokenizer basic method for tokenizing input into sentences for this tagger param data list of tokens words or word tag tuples type data str or tuplestr str param raw boolean flag marking the input data as a list of words or a list of tagged words type raw bool return list of sentences sentences are a list of tokens tokens are the same as the input function takes a list of tokens and separates the tokens into lists where each list represents a sentence fragment this function can separate both tagged and raw sequences into basic sentences sentence markers are the set of this is a simple method which enhances the performance of the tnt tagger better sentence tokenization will further enhance the results printi1 tacc tpkn i1 sacc tpkn i1 tacc i1 sacc natural language toolkit tnt tagger c 2001 2023 nltk project sam huston sjh900 gmail com url https www nltk org for license information see license txt implementation of tnt a statisical part of speech tagger by thorsten brants https aclanthology org a00 1031 pdf tnt statistical pos tagger important notes does not automatically deal with unseen words it is possible to provide an untrained pos tagger to create tags for unknown words see __init__ function should be used with sentence delimited input due to the nature of this tagger it works best when trained over sentence delimited input however it still produces good results if the training data and testing data are separated on all punctuation eg input for training is expected to be a list of sentences where each sentence is a list of word tag tuples input for tag function is a single sentence input for tagdata function is a list of sentences output is of a similar form function provided to process text that is unsegmented please see basic_sent_chop tnt uses a second order markov model to produce tags for a sequence of input specifically argmax proj p t_i t_i 1 t_i 2 p w_i t_i p t_t 1 t_t ie the maximum projection of a set of probabilities the set of possible tags for a given word is derived from the training data it is the set of all tags that exact word has been assigned to speed up and get more precision we can use log addition to instead multiplication specifically argmax sigma log p t_i t_i 1 t_i 2 log p w_i t_i log p t_t 1 t_t the probability of a tag for a given word is the linear interpolation of 3 markov models a zero order first order and a second order model p t_i t_i 1 t_i 2 l1 p t_i l2 p t_i t_i 1 l3 p t_i t_i 1 t_i 2 a beam search is used to limit the memory usage of the algorithm the degree of the beam can be changed using n in the initialization n represents the maximum number of possible solutions to maintain while tagging it is possible to differentiate the tags which are assigned to capitalized words however this does not result in a significant gain in the accuracy of the results construct a tnt statistical tagger tagger must be trained before being used to tag input param unk instance of a pos tagger conforms to taggeri type unk taggeri param trained indication that the pos tagger is trained or not type trained bool param n beam search degree see above type n int param c capitalization flag type c bool initializer creates frequency distributions to be used for tagging _lx values represent the portion of the tri bi uni taggers to be used to calculate the probability n value is the number of possible solutions to maintain while tagging a good value for this is 1000 c is a boolean value which specifies to use or not use the capitalization of the word as additional information for tagging note using capitalization may not increase the accuracy of the tagger statistical tools ignore or delete me uses a set of tagged data to train the tagger if an unknown word tagger is specified it is trained on the same data param data list of lists of word tag tuples type data tuple str ensure that local c flag is initialized before use if capitalization is requested and the word begins with a capital set local flag c to true set local flag c to false for the next word compute lambda values from the trained frequency distributions creates lambda values based upon training data note no need to explicitly reference c it is contained within the tag variable tag tag c for each tag trigram t1 t2 t3 depending on the maximum value of f t1 t2 t3 1 f t1 t2 1 f t2 t3 1 f t2 1 f t3 1 n 1 increment l3 l2 or l1 by f t1 t2 t3 issues resolutions if 2 values are equal increment both lambda values by f t1 t2 t3 2 temporary lambda variables for each t1 t2 in system for each t3 given t1 t2 in system note tag actually represents tag c however no effect within this function if there has only been 1 occurrence of this tag in the data then ignore this trigram safe_div provides a safe floating point division it returns 1 if the denominator is 0 if c1 is the maximum value if c2 is the maximum value if c3 is the maximum value if c3 and c2 are equal and larger than c1 if c1 and c2 are equal and larger than c3 this might be a dumb thing to do not sure yet otherwise there might be a problem eg all values 0 lambda normalisation ensures that l1 l2 l3 1 safe floating point division function does not allow division by 0 returns 1 if the denominator is 0 tags each sentence in a list of sentences param data list of list of words type data string return list of list of word tag tuples invokes tag sent function for each sentence compiles the results into a list of tagged sentences each tagged sentence is a list of word tag tuples tags a single sentence param data list of words type data string return word tag calls recursive function _tagword to produce a list of tags associates the sequence of returned tags with the correct words in the input sequence returns a list of word tag tuples unpack and discard the c flags param sent list of words remaining in the sentence type sent word param current_states list of possible tag combinations for the sentence so far and the log probability associated with each tag combination type current_states tag logprob tags the first word in the sentence and recursively tags the reminder of sentence uses formula specified above to calculate the probability of a particular tag if this word marks the end of the sentence return the most probable tag otherwise there are more words to be tagged if the capitalisation is requested initialise the flag for this word if word is known compute the set of possible tags and their associated log probabilities compute the result of appending each tag to this history otherwise a new word set of possible tags is unknown since a set of possible tags and the probability of each specific tag can not be returned from most classifiers specify that any unknown words are tagged with certainty if no unknown word tagger has been specified then use the tag unk otherwise apply the unknown word tagger now have computed a set of possible new_states sort states by log prob set is now ordered greatest to least log probability del everything after n threshold this is the beam search cut compute the tags for the rest of the sentence return the best list of tags for the sentence helper function basic sentence tokenizer basic method for tokenizing input into sentences for this tagger param data list of tokens words or word tag tuples type data str or tuple str str param raw boolean flag marking the input data as a list of words or a list of tagged words type raw bool return list of sentences sentences are a list of tokens tokens are the same as the input function takes a list of tokens and separates the tokens into lists where each list represents a sentence fragment this function can separate both tagged and raw sequences into basic sentences sentence markers are the set of this is a simple method which enhances the performance of the tnt tagger better sentence tokenization will further enhance the results print i 1 tacc tp_kn i 1 sacc tp_kn i 1 tacc i 1 sacc
from math import log
from operator import itemgetter

from nltk.probability import ConditionalFreqDist, FreqDist
from nltk.tag.api import TaggerI


class TnT(TaggerI):
    

    def __init__(self, unk=None, Trained=False, N=1000, C=False):
        

        self._uni = FreqDist()
        self._bi = ConditionalFreqDist()
        self._tri = ConditionalFreqDist()
        self._wd = ConditionalFreqDist()
        self._eos = ConditionalFreqDist()
        self._l1 = 0.0
        self._l2 = 0.0
        self._l3 = 0.0
        self._N = N
        self._C = C
        self._T = Trained

        self._unk = unk

        
        self.unknown = 0
        self.known = 0

    def train(self, data):
        

        
        C = False

        if self._unk is not None and self._T == False:
            self._unk.train(data)

        for sent in data:
            history = [("BOS", False), ("BOS", False)]
            for w, t in sent:

                
                
                
                if self._C and w[0].isupper():
                    C = True

                self._wd[w][t] += 1
                self._uni[(t, C)] += 1
                self._bi[history[1]][(t, C)] += 1
                self._tri[tuple(history)][(t, C)] += 1

                history.append((t, C))
                history.pop(0)

                
                C = False

            self._eos[t]["EOS"] += 1

        
        self._compute_lambda()

    def _compute_lambda(self):
        

        
        tl1 = 0.0
        tl2 = 0.0
        tl3 = 0.0

        
        for history in self._tri.conditions():
            (h1, h2) = history

            
            
            
            for tag in self._tri[history].keys():

                
                
                if self._uni[tag] == 1:
                    continue

                
                
                c3 = self._safe_div(
                    (self._tri[history][tag] - 1), (self._tri[history].N() - 1)
                )
                c2 = self._safe_div((self._bi[h2][tag] - 1), (self._bi[h2].N() - 1))
                c1 = self._safe_div((self._uni[tag] - 1), (self._uni.N() - 1))

                
                if (c1 > c3) and (c1 > c2):
                    tl1 += self._tri[history][tag]

                
                elif (c2 > c3) and (c2 > c1):
                    tl2 += self._tri[history][tag]

                
                elif (c3 > c2) and (c3 > c1):
                    tl3 += self._tri[history][tag]

                
                elif (c3 == c2) and (c3 > c1):
                    tl2 += self._tri[history][tag] / 2.0
                    tl3 += self._tri[history][tag] / 2.0

                
                
                elif (c2 == c1) and (c1 > c3):
                    tl1 += self._tri[history][tag] / 2.0
                    tl2 += self._tri[history][tag] / 2.0

                
                
                else:
                    pass

        
        
        self._l1 = tl1 / (tl1 + tl2 + tl3)
        self._l2 = tl2 / (tl1 + tl2 + tl3)
        self._l3 = tl3 / (tl1 + tl2 + tl3)

    def _safe_div(self, v1, v2):
        
        if v2 == 0:
            return -1
        else:
            return v1 / v2

    def tagdata(self, data):
        
        res = []
        for sent in data:
            res1 = self.tag(sent)
            res.append(res1)
        return res

    def tag(self, data):
        

        current_state = [(["BOS", "BOS"], 0.0)]

        sent = list(data)

        tags = self._tagword(sent, current_state)

        res = []
        for i in range(len(sent)):
            
            (t, C) = tags[i + 2]
            res.append((sent[i], t))

        return res

    def _tagword(self, sent, current_states):
        

        
        
        if sent == []:
            (h, logp) = current_states[0]
            return h

        
        word = sent[0]
        sent = sent[1:]
        new_states = []

        
        
        C = False
        if self._C and word[0].isupper():
            C = True

        
        
        
        if word in self._wd:
            self.known += 1

            for (history, curr_sent_logprob) in current_states:
                logprobs = []

                for t in self._wd[word].keys():
                    tC = (t, C)
                    p_uni = self._uni.freq(tC)
                    p_bi = self._bi[history[-1]].freq(tC)
                    p_tri = self._tri[tuple(history[-2:])].freq(tC)
                    p_wd = self._wd[word][t] / self._uni[tC]
                    p = self._l1 * p_uni + self._l2 * p_bi + self._l3 * p_tri
                    p2 = log(p, 2) + log(p_wd, 2)

                    
                    new_states.append((history + [tC], curr_sent_logprob + p2))

        
        else:
            self.unknown += 1

            
            
            
            
            p = 1

            
            
            if self._unk is None:
                tag = ("Unk", C)

            
            else:
                [(_w, t)] = list(self._unk.tag([word]))
                tag = (t, C)

            for (history, logprob) in current_states:
                history.append(tag)

            new_states = current_states

        

        
        
        new_states.sort(reverse=True, key=itemgetter(1))

        
        
        if len(new_states) > self._N:
            new_states = new_states[: self._N]

        
        
        return self._tagword(sent, new_states)







def basic_sent_chop(data, raw=True):
    

    new_data = []
    curr_sent = []
    sent_mark = [",", ".", "?", "!"]

    if raw:
        for word in data:
            if word in sent_mark:
                curr_sent.append(word)
                new_data.append(curr_sent)
                curr_sent = []
            else:
                curr_sent.append(word)

    else:
        for (word, tag) in data:
            if word in sent_mark:
                curr_sent.append((word, tag))
                new_data.append(curr_sent)
                curr_sent = []
            else:
                curr_sent.append((word, tag))
    return new_data


def demo():
    from nltk.corpus import brown

    sents = list(brown.tagged_sents())
    test = list(brown.sents())

    tagger = TnT()
    tagger.train(sents[200:1000])

    tagged_data = tagger.tagdata(test[100:120])

    for j in range(len(tagged_data)):
        s = tagged_data[j]
        t = sents[j + 100]
        for i in range(len(s)):
            print(s[i], "--", t[i])
        print()


def demo2():
    from nltk.corpus import treebank

    d = list(treebank.tagged_sents())

    t = TnT(N=1000, C=False)
    s = TnT(N=1000, C=True)
    t.train(d[(11) * 100 :])
    s.train(d[(11) * 100 :])

    for i in range(10):
        tacc = t.accuracy(d[i * 100 : ((i + 1) * 100)])
        tp_un = t.unknown / (t.known + t.unknown)
        tp_kn = t.known / (t.known + t.unknown)
        t.unknown = 0
        t.known = 0

        print("Capitalization off:")
        print("Accuracy:", tacc)
        print("Percentage known:", tp_kn)
        print("Percentage unknown:", tp_un)
        print("Accuracy over known words:", (tacc / tp_kn))

        sacc = s.accuracy(d[i * 100 : ((i + 1) * 100)])
        sp_un = s.unknown / (s.known + s.unknown)
        sp_kn = s.known / (s.known + s.unknown)
        s.unknown = 0
        s.known = 0

        print("Capitalization on:")
        print("Accuracy:", sacc)
        print("Percentage known:", sp_kn)
        print("Percentage unknown:", sp_un)
        print("Accuracy over known words:", (sacc / sp_kn))


def demo3():
    from nltk.corpus import brown, treebank

    d = list(treebank.tagged_sents())
    e = list(brown.tagged_sents())

    d = d[:1000]
    e = e[:1000]

    d10 = int(len(d) * 0.1)
    e10 = int(len(e) * 0.1)

    tknacc = 0
    sknacc = 0
    tallacc = 0
    sallacc = 0
    tknown = 0
    sknown = 0

    for i in range(10):

        t = TnT(N=1000, C=False)
        s = TnT(N=1000, C=False)

        dtest = d[(i * d10) : ((i + 1) * d10)]
        etest = e[(i * e10) : ((i + 1) * e10)]

        dtrain = d[: (i * d10)] + d[((i + 1) * d10) :]
        etrain = e[: (i * e10)] + e[((i + 1) * e10) :]

        t.train(dtrain)
        s.train(etrain)

        tacc = t.accuracy(dtest)
        tp_un = t.unknown / (t.known + t.unknown)
        tp_kn = t.known / (t.known + t.unknown)
        tknown += tp_kn
        t.unknown = 0
        t.known = 0

        sacc = s.accuracy(etest)
        sp_un = s.unknown / (s.known + s.unknown)
        sp_kn = s.known / (s.known + s.unknown)
        sknown += sp_kn
        s.unknown = 0
        s.known = 0

        tknacc += tacc / tp_kn
        sknacc += sacc / tp_kn
        tallacc += tacc
        sallacc += sacc

        

    print("brown: acc over words known:", 10 * tknacc)
    print("     : overall accuracy:", 10 * tallacc)
    print("     : words known:", 10 * tknown)
    print("treebank: acc over words known:", 10 * sknacc)
    print("        : overall accuracy:", 10 * sallacc)
    print("        : words known:", 10 * sknown)