natural language toolkit maximum entropy classifiers c 20012023 nltk project edward loper edlopergmail com dmitry chichkov dchichkovgmail com typedmaxentfeatureencoding url https www nltk org for license information see license txt a classifier model based on maximum entropy modeling framework this framework considers all of the probability distributions that are empirically consistent with the training data and chooses the distribution with the highest entropy a probability distribution is empirically consistent with a set of training data if its estimated frequency with which a class and a feature vector value cooccur is equal to the actual frequency in the data terminology feature the term feature is usually used to refer to some property of an unlabeled token for example when performing word sense disambiguation we might define a prevword feature whose value is the word preceding the target word however in the context of maxent modeling the term feature is typically used to refer to a property of a labeled token in order to prevent confusion we will introduce two distinct terms to disambiguate these two different concepts an inputfeature is a property of an unlabeled token a jointfeature is a property of a labeled token in the rest of the nltk classify module the term features is used to refer to what we will call inputfeatures in this module in literature that describes and discusses maximum entropy models inputfeatures are typically called contexts and jointfeatures are simply referred to as features converting inputfeatures to jointfeatures in maximum entropy models jointfeatures are required to have numeric values typically each inputfeature inputfeat is mapped to a set of jointfeatures of the form jointfeattoken label 1 if inputfeattoken featval and label somelabel 0 otherwise for all values of featval and somelabel this mapping is performed by classes that implement the maxentfeatureencodingi interface classifier model a maximum entropy classifier also known as a conditional exponential classifier this classifier is parameterized by a set of weights which are used to combine the jointfeatures that are generated from a featureset by an encoding in particular the encoding maps each featureset label pair to a vector the probability of each label is then computed using the following equation dotprodweights encodefs label probfslabel sumdotprodweights encodefs l for l in labels where dotprod is the dot product dotproda b sumxy for x y in zipa b construct a new maxent classifier model typically new classifier models are created using the train method type encoding maxentfeatureencodingi param encoding an encoding that is used to convert the featuresets that are given to the classify method into jointfeature vectors which are used by the maxent classifier model type weights list of float param weights the feature weight vector for this classifier type logarithmic bool param logarithmic if false then use nonlogarithmic weights self logarithmic false set the feature weight vector for this classifier param newweights the new feature weight vector type newweights list of float return the feature weight vector for this classifier rtype list of float normalize the dictionary to give a probability distribution print a table showing the effect of each of the features in the given feature set and how they combine to determine the probabilities of each label for that featureset generates the ranked list of informative features from most to least param show all neg or pos for negativeonly or positiveonly type show str param n the no of top features type n int use none the full list of ranked features a list of the algorithm names that are accepted for the train method s algorithm parameter train a new maxent classifier based on the given corpus of training samples this classifier will have its weights chosen to maximize entropy while remaining empirically consistent with the training corpus rtype maxentclassifier return the new maxent classifier type traintoks list param traintoks training data represented as a list of pairs the first member of which is a featureset and the second of which is a classification label type algorithm str param algorithm a caseinsensitive string specifying which algorithm should be used to train the classifier the following algorithms are currently available iterative scaling methods generalized iterative scaling gis improved iterative scaling iis external libraries requiring megam lmbfgs algorithm with training performed by megam megam the default algorithm is iis type trace int param trace the level of diagnostic tracing output to produce higher values produce more verbose output type encoding maxentfeatureencodingi param encoding a feature encoding used to convert featuresets into feature vectors if none is specified then a binarymaxentfeatureencoding will be built based on the features that are attested in the training corpus type labels liststr param labels the set of possible labels if none is given then the set of all labels attested in the training data will be used instead param gaussianpriorsigma the sigma value for a gaussian prior on model weights currently this is supported by megam for other algorithms its value is ignored param cutoffs arguments specifying various conditions under which the training should be halted some of the cutoff conditions are not supported by some algorithms maxiterv terminate after v iterations minllv terminate after the negative average loglikelihood drops under v minlldeltav terminate if a single iteration improves log likelihood by less than v alias for maxentclassifier feature encodings a mapping that converts a set of inputfeature values to a vector of jointfeature values given a label this conversion is necessary to translate featuresets into a format that can be used by maximum entropy models the set of jointfeatures used by a given encoding is fixed and each index in the generated jointfeature vectors corresponds to a single jointfeature the length of the generated jointfeature vectors is therefore constant for a given encoding because the jointfeature vectors generated by maxentfeatureencodingi are typically very sparse they are represented as a list of index value tuples specifying the value of each nonzero jointfeature feature encodings are generally created using the train method which generates an appropriate encoding based on the inputfeature values and labels that are present in a given corpus given a featureset label pair return the corresponding vector of jointfeature values this vector is represented as a list of index value tuples specifying the value of each nonzero jointfeature type featureset dict rtype listtupleint int return the size of the fixedlength jointfeature vectors that are generated by this encoding rtype int return a list of the known labels i e all labels l such that self encodefs l can be a nonzero jointfeature vector for some value of fs rtype list return a string describing the value of the jointfeature whose index in the generated feature vectors is fid rtype str construct and return new feature encoding based on a given training corpus traintoks type traintoks listtupledict str param traintoks training data represented as a list of pairs the first member of which is a feature dictionary and the second of which is a classification label a feature encoding that calls a usersupplied function to map a given featuresetlabel pair to a sparse jointfeature vector construct a new feature encoding based on the given function type func callable param func a function that takes two arguments a featureset and a label and returns the sparse joint feature vector that encodes them funcfeatureset label featurevector this sparse joint feature vector featurevector is a list of index value tuples type length int param length the size of the fixedlength jointfeature vectors that are generated by this encoding type labels list param labels a list of the known labels for this encoding i e all labels l such that self encodefs l can be a nonzero jointfeature vector for some value of fs a feature encoding that generates vectors containing a binary jointfeatures of the form jointfeatfs l 1 if fsfname fval and l label 0 otherwise where fname is the name of an inputfeature fval is a value for that inputfeature and label is a label typically these features are constructed based on a training corpus using the train method this method will create one feature for each combination of fname fval and label that occurs at least once in the training corpus the unseenfeatures parameter can be used to add unseenvalue features which are used whenever an input feature has a value that was not encountered in the training corpus these features have the form jointfeatfs l 1 if isunseenfname fsfname and l label 0 otherwise where isunseenfname fval is true if the encoding does not contain any joint features that are true when fsfnamefval the alwaysonfeatures parameter can be used to add alwayson features which have the form jointfeatfs l 1 if l label 0 otherwise these alwayson features allow the maxent model to directly model the prior probabilities of each label param labels a list of the known labels for this encoding param mapping a dictionary mapping from fname fval label tuples to corresponding jointfeature indexes these indexes must be the set of integers from 0 lenmapping if mappingfname fval labelid then self encode fname fval labelid is 1 otherwise it is 0 param unseenfeatures if true then include unseen value features in the generated jointfeature vectors param alwaysonfeatures if true then include alwayson features in the generated jointfeature vectors a list of attested labels self mapping mapping the length of generated joint feature vectors self alwayson none dict mapping from fname fid if alwaysonfeatures self alwayson label i self length for i label in enumeratelabels self length lenself alwayson if unseenfeatures fnames fname for fname fval label in mapping self unseen fname i self length for i fname in enumeratefnames self length lenfnames def encodeself featureset label inherit docs encoding convert inputfeatures to jointfeatures for fname fval in featureset items known feature name value if fname fval label in self mapping encoding appendself mappingfname fval label 1 otherwise we might want to fire an unseenvalue feature elif self unseen have we seen this fnamefval combination with any label for label2 in self labels if fname fval label2 in self mapping break we ve seen this fnamefval combo we haven t fire the unseenvalue feature else if fname in self unseen encoding appendself unseenfname 1 add alwayson features if self alwayson and label in self alwayson encoding appendself alwaysonlabel 1 return encoding def describeself fid inherit docs if not isinstancefid int raise typeerrordescribe expected an int try self invmapping except attributeerror self invmapping 1 lenself mapping for info i in self mapping items self invmappingi info if fid lenself mapping fname fval label self invmappingfid return ffnamefval r and label is label r elif self alwayson and fid in self alwayson values for label fid2 in self alwayson items if fid fid2 return label is r label elif self unseen and fid in self unseen values for fname fid2 in self unseen items if fid fid2 return s is unseen fname else raise valueerrorbad feature id def labelsself inherit docs return self labels def lengthself inherit docs return self length classmethod def traincls traintoks countcutoff0 labelsnone options mapping maps fname fval label fid seenlabels set the set of labels we ve encountered count defaultdictint maps fname fval count for tok label in traintoks if labels and label not in labels raise valueerrorunexpected label s label seenlabels addlabel record each of the features for fname fval in tok items if a count cutoff is given then only add a joint feature once the corresponding fname fval label tuple exceeds that cutoff countfname fval 1 if countfname fval countcutoff if fname fval label not in mapping mappingfname fval label lenmapping if labels is none labels seenlabels return clslabels mapping options class gisencodingbinarymaxentfeatureencoding def init self labels mapping unseenfeaturesfalse alwaysonfeaturesfalse cnone binarymaxentfeatureencoding init self labels mapping unseenfeatures alwaysonfeatures if c is none c lenfname for fname fval label in mapping 1 self c c property def cself get the basic encoding add a correction feature return the result this gets read twice so compute the values in case it s lazy a feature encoding that generates vectors containing integer float and binary jointfeatures of the form binary for string and boolean features jointfeatfs l 1 if fsfname fval and l label 0 otherwise value for integer and float features jointfeatfs l fval if fsfname typefval and l label not encoded otherwise where fname is the name of an inputfeature fval is a value for that inputfeature and label is a label typically these features are constructed based on a training corpus using the train method for string and boolean features typefval not in int float this method will create one feature for each combination of fname fval and label that occurs at least once in the training corpus for integer and float features typefval in int float this method will create one feature for each combination of fname and label that occurs at least once in the training corpus for binary features the unseenfeatures parameter can be used to add unseenvalue features which are used whenever an input feature has a value that was not encountered in the training corpus these features have the form jointfeatfs l 1 if isunseenfname fsfname and l label 0 otherwise where isunseenfname fval is true if the encoding does not contain any joint features that are true when fsfnamefval the alwaysonfeatures parameter can be used to add alwayson features which have the form jointfeatfs l 1 if l label 0 otherwise these alwayson features allow the maxent model to directly model the prior probabilities of each label param labels a list of the known labels for this encoding param mapping a dictionary mapping from fname fval label tuples to corresponding jointfeature indexes these indexes must be the set of integers from 0 lenmapping if mappingfname fval labelid then self encode fname fval labelid is 1 otherwise it is 0 param unseenfeatures if true then include unseen value features in the generated jointfeature vectors param alwaysonfeatures if true then include alwayson features in the generated jointfeature vectors a list of attested labels self mapping mapping the length of generated joint feature vectors self alwayson none dict mapping from fname fid if alwaysonfeatures self alwayson label i self length for i label in enumeratelabels self length lenself alwayson if unseenfeatures fnames fname for fname fval label in mapping self unseen fname i self length for i fname in enumeratefnames self length lenfnames def encodeself featureset label inherit docs encoding convert inputfeatures to jointfeatures for fname fval in featureset items if isinstancefval int float known feature name value if fname typefval label in self mapping encoding appendself mappingfname typefval label fval else known feature name value if fname fval label in self mapping encoding appendself mappingfname fval label 1 otherwise we might want to fire an unseenvalue feature elif self unseen have we seen this fnamefval combination with any label for label2 in self labels if fname fval label2 in self mapping break we ve seen this fnamefval combo we haven t fire the unseenvalue feature else if fname in self unseen encoding appendself unseenfname 1 add alwayson features if self alwayson and label in self alwayson encoding appendself alwaysonlabel 1 return encoding def describeself fid inherit docs if not isinstancefid int raise typeerrordescribe expected an int try self invmapping except attributeerror self invmapping 1 lenself mapping for info i in self mapping items self invmappingi info if fid lenself mapping fname fval label self invmappingfid return ffnamefval r and label is label r elif self alwayson and fid in self alwayson values for label fid2 in self alwayson items if fid fid2 return label is r label elif self unseen and fid in self unseen values for fname fid2 in self unseen items if fid fid2 return s is unseen fname else raise valueerrorbad feature id def labelsself inherit docs return self labels def lengthself inherit docs return self length classmethod def traincls traintoks countcutoff0 labelsnone options mapping maps fname fval label fid seenlabels set the set of labels we ve encountered count defaultdictint maps fname fval count for tok label in traintoks if labels and label not in labels raise valueerrorunexpected label s label seenlabels addlabel record each of the features for fname fval in tok items if typefval in int float fval typefval if a count cutoff is given then only add a joint feature once the corresponding fname fval label tuple exceeds that cutoff countfname fval 1 if countfname fval countcutoff if fname fval label not in mapping mappingfname fval label lenmapping if labels is none labels seenlabels return clslabels mapping options classifier trainer generalized iterative scaling def trainmaxentclassifierwithgis traintoks trace3 encodingnone labelsnone cutoffs cutoffs setdefaultmaxiter 100 cutoffchecker cutoffcheckercutoffs construct an encoding from the training data if encoding is none encoding gisencoding traintraintoks labelslabels if not hasattrencoding c raise typeerror the gis algorithm requires an encoding that defines c e g gisencoding cinv is the inverse of the sum of each joint feature vector this controls the learning rate higher cinv or lower c gives faster learning cinv 1 0 encoding c count how many times each feature occurs in the training data empiricalfcount calculateempiricalfcounttraintoks encoding check for any features that are not attested in traintoks unattested setnumpy nonzeroempiricalfcount 00 build the classifier start with weight0 for each attested feature and weightinfinity for each unattested feature weights numpy zeroslenempiricalfcount d for fid in unattested weightsfid numpy ninf classifier conditionalexponentialclassifierencoding weights take the log of the empirical fcount logempiricalfcount numpy log2empiricalfcount del empiricalfcount if trace 0 print training d iterations cutoffsmaxiter if trace 2 print print iteration log likelihood accuracy print train the classifier try while true if trace 2 ll cutoffchecker ll or loglikelihoodclassifier traintoks acc cutoffchecker acc or accuracyclassifier traintoks iternum cutoffchecker iter print 9d 14 5f 9 3f iternum ll acc use the model to estimate the number of times each feature should occur in the training data estimatedfcount calculateestimatedfcount classifier traintoks encoding take the log of estimated fcount avoid taking log0 for fid in unattested estimatedfcountfid 1 logestimatedfcount numpy log2estimatedfcount del estimatedfcount update the classifier weights weights classifier weights weights logempiricalfcount logestimatedfcount cinv classifier setweightsweights check the loglikelihood accuracy cutoffs if cutoffchecker checkclassifier traintoks break except keyboardinterrupt print training stopped keyboard interrupt except raise if trace 2 ll loglikelihoodclassifier traintoks acc accuracyclassifier traintoks printf final ll 14 5f acc 9 3f return the classifier return classifier def calculateempiricalfcounttraintoks encoding fcount numpy zerosencoding length d for tok label in traintoks for index val in encoding encodetok label fcountindex val return fcount def calculateestimatedfcountclassifier traintoks encoding fcount numpy zerosencoding length d for tok label in traintoks pdist classifier probclassifytok for label in pdist samples prob pdist problabel for fid fval in encoding encodetok label fcountfid prob fval return fcount classifier trainer improved iterative scaling def trainmaxentclassifierwithiis traintoks trace3 encodingnone labelsnone cutoffs cutoffs setdefaultmaxiter 100 cutoffchecker cutoffcheckercutoffs construct an encoding from the training data if encoding is none encoding binarymaxentfeatureencoding traintraintoks labelslabels count how many times each feature occurs in the training data empiricalffreq calculateempiricalfcounttraintoks encoding lentraintoks find the nf map and related variables nfarray and nfident nf is the sum of the features for a given labeled text nfmap compresses this sparse set of values to a dense list nfarray performs the reverse operation nfident is nfarray multiplied by an identity matrix nfmap calculatenfmaptraintoks encoding nfarray numpy arraysortednfmap keynfmap getitem d nftranspose numpy reshapenfarray lennfarray 1 check for any features that are not attested in traintoks unattested setnumpy nonzeroempiricalffreq 00 build the classifier start with weight0 for each attested feature and weightinfinity for each unattested feature weights numpy zeroslenempiricalffreq d for fid in unattested weightsfid numpy ninf classifier conditionalexponentialclassifierencoding weights if trace 0 print training d iterations cutoffsmaxiter if trace 2 print print iteration log likelihood accuracy print train the classifier try while true if trace 2 ll cutoffchecker ll or loglikelihoodclassifier traintoks acc cutoffchecker acc or accuracyclassifier traintoks iternum cutoffchecker iter print 9d 14 5f 9 3f iternum ll acc calculate the deltas for this iteration using newton s method deltas calculatedeltas traintoks classifier unattested empiricalffreq nfmap nfarray nftranspose encoding use the deltas to update our weights weights classifier weights weights deltas classifier setweightsweights check the loglikelihood accuracy cutoffs if cutoffchecker checkclassifier traintoks break except keyboardinterrupt print training stopped keyboard interrupt except raise if trace 2 ll loglikelihoodclassifier traintoks acc accuracyclassifier traintoks printf final ll 14 5f acc 9 3f return the classifier return classifier def calculatenfmaptraintoks encoding map from nf to indices this allows us to use smaller arrays nfset set for tok in traintoks for label in encoding labels nfset addsumval for id val in encoding encodetok label return nf i for i nf in enumeratenfset def calculatedeltas traintoks classifier unattested ffreqempirical nfmap nfarray nftranspose encoding r calculate the update values for the classifier weights for this iteration of iis these update weights are the value of delta that solves the equation ffreqempiricali sumfs l classifier probclassifyfs probl featurevectorfs li expdeltai nffeaturevectorfs l where fs l is a featureset label tuple from traintoks featurevectorfs l encoding encodefs l nfvector sumval for id val in vector this method uses newton s method to solve this equation for deltai in particular it starts with a guess of deltai 1 and iteratively updates delta with deltai ffreqempiricali sum1isum2i until convergence where sum1 and sum2 are defined as sum1idelta sumfs l fifs l delta sum2idelta sumfs l fifs l delta nffeaturevectorfs l fifs l delta classifier probclassifyfs probl featurevectorfs li expdeltai nffeaturevectorfs l note that sum1 and sum2 depend on delta so they need to be recomputed each iteration the variables nfmap nfarray and nftranspose are used to generate a dense encoding for nfltext this allows deltas to calculate sum1 and sum2 using matrices which yields a significant performance improvement param traintoks the set of training tokens type traintoks listtupledict str param classifier the current classifier type classifier classifieri param ffreqempirical an array containing the empirical frequency for each feature the i th element of this array is the empirical frequency for feature i type ffreqempirical sequence of float param unattested an array that is 1 for features that are not attested in the training data and 0 for features that are attested in other words unattestedi0 iff ffreqempiricali0 type unattested sequence of int param nfmap a map that can be used to compress nf to a dense vector type nfmap dictint int param nfarray an array that can be used to uncompress nf from a dense vector type nfarray arrayfloat param nftranspose the transpose of nfarray type nftranspose arrayfloat these parameters control when we decide that we ve converged it probably should be possible to set these manually via keyword arguments to train precompute the a matrix anfid sum pfs plabelfs ffs label over all label fs s t numfeatureslabel fsnf generate the feature vector find the number of active features update the a matrix iteratively solve for delta use the following variables nfdeltaxy nfarrayx deltay expnfdeltaxy expnfx deltay nfexpnfdeltaxy nfx expnfx deltay sum1inf sum pfsplabelfsfilabel fs expdeltainf sum2inf sum pfsplabelfsfilabel fs nf expdeltainf avoid division by zero update the deltas we can stop once we converge classifier trainer megam xx possible extension add support for using implicit file format this would need to put requirements on what encoding is used but we may need this for other maxent classifier trainers that require implicit formats anyway train a new conditionalexponentialclassifier using the given training samples using the external megam library this conditionalexponentialclassifier will encode the model that maximizes entropy from all the models that are empirically consistent with traintoks see trainmaxentclassifier for parameter descriptions see nltk classify megam construct an encoding from the training data count cutoff can also be controlled by megam with the minfc option not sure where the best place for it is write a training file for megam run megam on the training file lambda is just the precision of the gaussian prior i e it s the inverse variance so the parameter conversion is 1 0sigma2 see https users umiacs umd eduhaldocsdaume04cgbfgs pdf xx this is actually a perplexity delta not a log likelihood delta print megami686 opt joinoptions delete the training file parse the generated weight vector convert from basee to base2 weights build the classifier classifier trainer tadm construct an encoding from the training data convert from basee to base2 weights build the classifier demo natural language toolkit maximum entropy classifiers c 2001 2023 nltk project edward loper edloper gmail com dmitry chichkov dchichkov gmail com typedmaxentfeatureencoding url https www nltk org for license information see license txt a classifier model based on maximum entropy modeling framework this framework considers all of the probability distributions that are empirically consistent with the training data and chooses the distribution with the highest entropy a probability distribution is empirically consistent with a set of training data if its estimated frequency with which a class and a feature vector value co occur is equal to the actual frequency in the data terminology feature the term feature is usually used to refer to some property of an unlabeled token for example when performing word sense disambiguation we might define a prevword feature whose value is the word preceding the target word however in the context of maxent modeling the term feature is typically used to refer to a property of a labeled token in order to prevent confusion we will introduce two distinct terms to disambiguate these two different concepts an input feature is a property of an unlabeled token a joint feature is a property of a labeled token in the rest of the nltk classify module the term features is used to refer to what we will call input features in this module in literature that describes and discusses maximum entropy models input features are typically called contexts and joint features are simply referred to as features converting input features to joint features in maximum entropy models joint features are required to have numeric values typically each input feature input_feat is mapped to a set of joint features of the form joint_feat token label 1 if input_feat token feat_val and label some_label 0 otherwise for all values of feat_val and some_label this mapping is performed by classes that implement the maxentfeatureencodingi interface classifier model a maximum entropy classifier also known as a conditional exponential classifier this classifier is parameterized by a set of weights which are used to combine the joint features that are generated from a featureset by an encoding in particular the encoding maps each featureset label pair to a vector the probability of each label is then computed using the following equation dotprod weights encode fs label prob fs label sum dotprod weights encode fs l for l in labels where dotprod is the dot product dotprod a b sum x y for x y in zip a b construct a new maxent classifier model typically new classifier models are created using the train method type encoding maxentfeatureencodingi param encoding an encoding that is used to convert the featuresets that are given to the classify method into joint feature vectors which are used by the maxent classifier model type weights list of float param weights the feature weight vector for this classifier type logarithmic bool param logarithmic if false then use non logarithmic weights self _logarithmic false set the feature weight vector for this classifier param new_weights the new feature weight vector type new_weights list of float return the feature weight vector for this classifier rtype list of float normalize the dictionary to give a probability distribution print a table showing the effect of each of the features in the given feature set and how they combine to determine the probabilities of each label for that featureset hack hack generates the ranked list of informative features from most to least param show all neg or pos for negative only or positive only type show str param n the no of top features type n int use none the full list of ranked features a list of the algorithm names that are accepted for the train method s algorithm parameter train a new maxent classifier based on the given corpus of training samples this classifier will have its weights chosen to maximize entropy while remaining empirically consistent with the training corpus rtype maxentclassifier return the new maxent classifier type train_toks list param train_toks training data represented as a list of pairs the first member of which is a featureset and the second of which is a classification label type algorithm str param algorithm a case insensitive string specifying which algorithm should be used to train the classifier the following algorithms are currently available iterative scaling methods generalized iterative scaling gis improved iterative scaling iis external libraries requiring megam lm bfgs algorithm with training performed by megam megam the default algorithm is iis type trace int param trace the level of diagnostic tracing output to produce higher values produce more verbose output type encoding maxentfeatureencodingi param encoding a feature encoding used to convert featuresets into feature vectors if none is specified then a binarymaxentfeatureencoding will be built based on the features that are attested in the training corpus type labels list str param labels the set of possible labels if none is given then the set of all labels attested in the training data will be used instead param gaussian_prior_sigma the sigma value for a gaussian prior on model weights currently this is supported by megam for other algorithms its value is ignored param cutoffs arguments specifying various conditions under which the training should be halted some of the cutoff conditions are not supported by some algorithms max_iter v terminate after v iterations min_ll v terminate after the negative average log likelihood drops under v min_lldelta v terminate if a single iteration improves log likelihood by less than v alias for maxentclassifier feature encodings a mapping that converts a set of input feature values to a vector of joint feature values given a label this conversion is necessary to translate featuresets into a format that can be used by maximum entropy models the set of joint features used by a given encoding is fixed and each index in the generated joint feature vectors corresponds to a single joint feature the length of the generated joint feature vectors is therefore constant for a given encoding because the joint feature vectors generated by maxentfeatureencodingi are typically very sparse they are represented as a list of index value tuples specifying the value of each non zero joint feature feature encodings are generally created using the train method which generates an appropriate encoding based on the input feature values and labels that are present in a given corpus given a featureset label pair return the corresponding vector of joint feature values this vector is represented as a list of index value tuples specifying the value of each non zero joint feature type featureset dict rtype list tuple int int return the size of the fixed length joint feature vectors that are generated by this encoding rtype int return a list of the known labels i e all labels l such that self encode fs l can be a nonzero joint feature vector for some value of fs rtype list return a string describing the value of the joint feature whose index in the generated feature vectors is fid rtype str construct and return new feature encoding based on a given training corpus train_toks type train_toks list tuple dict str param train_toks training data represented as a list of pairs the first member of which is a feature dictionary and the second of which is a classification label a feature encoding that calls a user supplied function to map a given featureset label pair to a sparse joint feature vector construct a new feature encoding based on the given function type func callable param func a function that takes two arguments a featureset and a label and returns the sparse joint feature vector that encodes them func featureset label feature_vector this sparse joint feature vector feature_vector is a list of index value tuples type length int param length the size of the fixed length joint feature vectors that are generated by this encoding type labels list param labels a list of the known labels for this encoding i e all labels l such that self encode fs l can be a nonzero joint feature vector for some value of fs a feature encoding that generates vectors containing a binary joint features of the form joint_feat fs l 1 if fs fname fval and l label 0 otherwise where fname is the name of an input feature fval is a value for that input feature and label is a label typically these features are constructed based on a training corpus using the train method this method will create one feature for each combination of fname fval and label that occurs at least once in the training corpus the unseen_features parameter can be used to add unseen value features which are used whenever an input feature has a value that was not encountered in the training corpus these features have the form joint_feat fs l 1 if is_unseen fname fs fname and l label 0 otherwise where is_unseen fname fval is true if the encoding does not contain any joint features that are true when fs fname fval the alwayson_features parameter can be used to add always on features which have the form joint_feat fs l 1 if l label 0 otherwise these always on features allow the maxent model to directly model the prior probabilities of each label param labels a list of the known labels for this encoding param mapping a dictionary mapping from fname fval label tuples to corresponding joint feature indexes these indexes must be the set of integers from 0 len mapping if mapping fname fval label id then self encode fname fval label id is 1 otherwise it is 0 param unseen_features if true then include unseen value features in the generated joint feature vectors param alwayson_features if true then include always on features in the generated joint feature vectors a list of attested labels dict mapping from fname fval label fid the length of generated joint feature vectors dict mapping from label fid dict mapping from fname fid inherit docs convert input features to joint features known feature name value otherwise we might want to fire an unseen value feature have we seen this fname fval combination with any label we ve seen this fname fval combo we haven t fire the unseen value feature add always on features inherit docs inherit docs inherit docs construct and return new feature encoding based on a given training corpus train_toks see the class description binarymaxentfeatureencoding for a description of the joint features that will be included in this encoding type train_toks list tuple dict str param train_toks training data represented as a list of pairs the first member of which is a feature dictionary and the second of which is a classification label type count_cutoff int param count_cutoff a cutoff value that is used to discard rare joint features if a joint feature s value is 1 fewer than count_cutoff times in the training corpus then that joint feature is not included in the generated encoding type labels list param labels a list of labels that should be used by the classifier if not specified then the set of labels attested in train_toks will be used param options extra parameters for the constructor such as unseen_features and alwayson_features maps fname fval label fid the set of labels we ve encountered maps fname fval count record each of the features if a count cutoff is given then only add a joint feature once the corresponding fname fval label tuple exceeds that cutoff a binary feature encoding which adds one new joint feature to the joint features defined by binarymaxentfeatureencoding a correction feature whose value is chosen to ensure that the sparse vector always sums to a constant non negative number this new feature is used to ensure two preconditions for the gis training algorithm at least one feature vector index must be nonzero for every token the feature vector must sum to a constant non negative number for every token param c the correction constant the value of the correction feature is based on this value in particular its value is c sum v for f v in encoding seealso binarymaxentfeatureencoding __init__ the non negative constant that all encoded feature vectors will sum to get the basic encoding add a correction feature return the result this gets read twice so compute the values in case it s lazy a feature encoding that generates vectors containing integer float and binary joint features of the form binary for string and boolean features joint_feat fs l 1 if fs fname fval and l label 0 otherwise value for integer and float features joint_feat fs l fval if fs fname type fval and l label not encoded otherwise where fname is the name of an input feature fval is a value for that input feature and label is a label typically these features are constructed based on a training corpus using the train method for string and boolean features type fval not in int float this method will create one feature for each combination of fname fval and label that occurs at least once in the training corpus for integer and float features type fval in int float this method will create one feature for each combination of fname and label that occurs at least once in the training corpus for binary features the unseen_features parameter can be used to add unseen value features which are used whenever an input feature has a value that was not encountered in the training corpus these features have the form joint_feat fs l 1 if is_unseen fname fs fname and l label 0 otherwise where is_unseen fname fval is true if the encoding does not contain any joint features that are true when fs fname fval the alwayson_features parameter can be used to add always on features which have the form joint_feat fs l 1 if l label 0 otherwise these always on features allow the maxent model to directly model the prior probabilities of each label param labels a list of the known labels for this encoding param mapping a dictionary mapping from fname fval label tuples to corresponding joint feature indexes these indexes must be the set of integers from 0 len mapping if mapping fname fval label id then self encode fname fval label id is 1 otherwise it is 0 param unseen_features if true then include unseen value features in the generated joint feature vectors param alwayson_features if true then include always on features in the generated joint feature vectors a list of attested labels dict mapping from fname fval label fid the length of generated joint feature vectors dict mapping from label fid dict mapping from fname fid inherit docs convert input features to joint features known feature name value known feature name value otherwise we might want to fire an unseen value feature have we seen this fname fval combination with any label we ve seen this fname fval combo we haven t fire the unseen value feature add always on features inherit docs inherit docs inherit docs construct and return new feature encoding based on a given training corpus train_toks see the class description typedmaxentfeatureencoding for a description of the joint features that will be included in this encoding note recognized feature values types are int float over types are interpreted as regular binary features type train_toks list tuple dict str param train_toks training data represented as a list of pairs the first member of which is a feature dictionary and the second of which is a classification label type count_cutoff int param count_cutoff a cutoff value that is used to discard rare joint features if a joint feature s value is 1 fewer than count_cutoff times in the training corpus then that joint feature is not included in the generated encoding type labels list param labels a list of labels that should be used by the classifier if not specified then the set of labels attested in train_toks will be used param options extra parameters for the constructor such as unseen_features and alwayson_features maps fname fval label fid the set of labels we ve encountered maps fname fval count record each of the features if a count cutoff is given then only add a joint feature once the corresponding fname fval label tuple exceeds that cutoff classifier trainer generalized iterative scaling train a new conditionalexponentialclassifier using the given training samples using the generalized iterative scaling algorithm this conditionalexponentialclassifier will encode the model that maximizes entropy from all the models that are empirically consistent with train_toks see train_maxent_classifier for parameter descriptions construct an encoding from the training data cinv is the inverse of the sum of each joint feature vector this controls the learning rate higher cinv or lower c gives faster learning count how many times each feature occurs in the training data check for any features that are not attested in train_toks build the classifier start with weight 0 for each attested feature and weight infinity for each unattested feature take the log of the empirical fcount train the classifier use the model to estimate the number of times each feature should occur in the training data take the log of estimated fcount avoid taking log 0 update the classifier weights check the log likelihood accuracy cutoffs return the classifier classifier trainer improved iterative scaling train a new conditionalexponentialclassifier using the given training samples using the improved iterative scaling algorithm this conditionalexponentialclassifier will encode the model that maximizes entropy from all the models that are empirically consistent with train_toks see train_maxent_classifier for parameter descriptions construct an encoding from the training data count how many times each feature occurs in the training data find the nf map and related variables nfarray and nfident nf is the sum of the features for a given labeled text nfmap compresses this sparse set of values to a dense list nfarray performs the reverse operation nfident is nfarray multiplied by an identity matrix check for any features that are not attested in train_toks build the classifier start with weight 0 for each attested feature and weight infinity for each unattested feature train the classifier calculate the deltas for this iteration using newton s method use the deltas to update our weights check the log likelihood accuracy cutoffs return the classifier construct a map that can be used to compress nf which is typically sparse nf feature_vector is the sum of the feature values for feature_vector this represents the number of features that are active for a given labeled text this method finds all values of nf t that are attested for at least one token in the given list of training tokens and constructs a dictionary mapping these attested values to a continuous range 0 n for example if the only values of nf that were attested were 3 5 and 7 then _nfmap might return the dictionary 3 0 5 1 7 2 return a map that can be used to compress nf to a dense vector rtype dict int int map from nf to indices this allows us to use smaller arrays calculate the update values for the classifier weights for this iteration of iis these update weights are the value of delta that solves the equation ffreq_empirical i sum fs l classifier prob_classify fs prob l feature_vector fs l i exp delta i nf feature_vector fs l where fs l is a featureset label tuple from train_toks feature_vector fs l encoding encode fs l nf vector sum val for id val in vector this method uses newton s method to solve this equation for delta i in particular it starts with a guess of delta i 1 and iteratively updates delta with delta i ffreq_empirical i sum1 i sum2 i until convergence where sum1 and sum2 are defined as sum1 i delta sum fs l f i fs l delta sum2 i delta sum fs l f i fs l delta nf feature_vector fs l f i fs l delta classifier prob_classify fs prob l feature_vector fs l i exp delta i nf feature_vector fs l note that sum1 and sum2 depend on delta so they need to be re computed each iteration the variables nfmap nfarray and nftranspose are used to generate a dense encoding for nf ltext this allows _deltas to calculate sum1 and sum2 using matrices which yields a significant performance improvement param train_toks the set of training tokens type train_toks list tuple dict str param classifier the current classifier type classifier classifieri param ffreq_empirical an array containing the empirical frequency for each feature the i th element of this array is the empirical frequency for feature i type ffreq_empirical sequence of float param unattested an array that is 1 for features that are not attested in the training data and 0 for features that are attested in other words unattested i 0 iff ffreq_empirical i 0 type unattested sequence of int param nfmap a map that can be used to compress nf to a dense vector type nfmap dict int int param nfarray an array that can be used to uncompress nf from a dense vector type nfarray array float param nftranspose the transpose of nfarray type nftranspose array float these parameters control when we decide that we ve converged it probably should be possible to set these manually via keyword arguments to train precompute the a matrix a nf id sum p fs p label fs f fs label over all label fs s t num_features label fs nf generate the feature vector find the number of active features update the a matrix iteratively solve for delta use the following variables nf_delta x y nfarray x delta y exp_nf_delta x y exp nf x delta y nf_exp_nf_delta x y nf x exp nf x delta y sum1 i nf sum p fs p label fs f i label fs exp delta i nf sum2 i nf sum p fs p label fs f i label fs nf exp delta i nf avoid division by zero update the deltas we can stop once we converge classifier trainer megam xx possible extension add support for using implicit file format this would need to put requirements on what encoding is used but we may need this for other maxent classifier trainers that require implicit formats anyway train a new conditionalexponentialclassifier using the given training samples using the external megam library this conditionalexponentialclassifier will encode the model that maximizes entropy from all the models that are empirically consistent with train_toks see train_maxent_classifier for parameter descriptions see nltk classify megam construct an encoding from the training data count cutoff can also be controlled by megam with the minfc option not sure where the best place for it is write a training file for megam run megam on the training file lambda is just the precision of the gaussian prior i e it s the inverse variance so the parameter conversion is 1 0 sigma 2 see https users umiacs umd edu hal docs daume04cg bfgs pdf xx this is actually a perplexity delta not a log likelihood delta each possible la print megam_i686 opt join options delete the training file parse the generated weight vector convert from base e to base 2 weights build the classifier classifier trainer tadm construct an encoding from the training data convert from base e to base 2 weights build the classifier demo
try:
    import numpy
except ImportError:
    pass

import os
import tempfile
from collections import defaultdict

from nltk.classify.api import ClassifierI
from nltk.classify.megam import call_megam, parse_megam_weights, write_megam_file
from nltk.classify.tadm import call_tadm, parse_tadm_weights, write_tadm_file
from nltk.classify.util import CutoffChecker, accuracy, log_likelihood
from nltk.data import gzip_open_unicode
from nltk.probability import DictionaryProbDist
from nltk.util import OrderedDict

__docformat__ = "epytext en"






class MaxentClassifier(ClassifierI):
    

    def __init__(self, encoding, weights, logarithmic=True):
        
        self._encoding = encoding
        self._weights = weights
        self._logarithmic = logarithmic
        
        assert encoding.length() == len(weights)

    def labels(self):
        return self._encoding.labels()

    def set_weights(self, new_weights):
        
        self._weights = new_weights
        assert self._encoding.length() == len(new_weights)

    def weights(self):
        
        return self._weights

    def classify(self, featureset):
        return self.prob_classify(featureset).max()

    def prob_classify(self, featureset):
        prob_dict = {}
        for label in self._encoding.labels():
            feature_vector = self._encoding.encode(featureset, label)

            if self._logarithmic:
                total = 0.0
                for (f_id, f_val) in feature_vector:
                    total += self._weights[f_id] * f_val
                prob_dict[label] = total

            else:
                prod = 1.0
                for (f_id, f_val) in feature_vector:
                    prod *= self._weights[f_id] ** f_val
                prob_dict[label] = prod

        
        return DictionaryProbDist(prob_dict, log=self._logarithmic, normalize=True)

    def explain(self, featureset, columns=4):
        
        descr_width = 50
        TEMPLATE = "  %-" + str(descr_width - 2) + "s%s%8.3f"

        pdist = self.prob_classify(featureset)
        labels = sorted(pdist.samples(), key=pdist.prob, reverse=True)
        labels = labels[:columns]
        print(
            "  Feature".ljust(descr_width)
            + "".join("%8s" % (("%s" % l)[:7]) for l in labels)
        )
        print("  " + "-" * (descr_width - 2 + 8 * len(labels)))
        sums = defaultdict(int)
        for i, label in enumerate(labels):
            feature_vector = self._encoding.encode(featureset, label)
            feature_vector.sort(
                key=lambda fid__: abs(self._weights[fid__[0]]), reverse=True
            )
            for (f_id, f_val) in feature_vector:
                if self._logarithmic:
                    score = self._weights[f_id] * f_val
                else:
                    score = self._weights[f_id] ** f_val
                descr = self._encoding.describe(f_id)
                descr = descr.split(" and label is ")[0]  
                descr += " (%s)" % f_val  
                if len(descr) > 47:
                    descr = descr[:44] + "..."
                print(TEMPLATE % (descr, i * 8 * " ", score))
                sums[label] += score
        print("  " + "-" * (descr_width - 1 + 8 * len(labels)))
        print(
            "  TOTAL:".ljust(descr_width) + "".join("%8.3f" % sums[l] for l in labels)
        )
        print(
            "  PROBS:".ljust(descr_width)
            + "".join("%8.3f" % pdist.prob(l) for l in labels)
        )

    def most_informative_features(self, n=10):
        
        if hasattr(self, "_most_informative_features"):
            return self._most_informative_features[:n]
        else:
            self._most_informative_features = sorted(
                list(range(len(self._weights))),
                key=lambda fid: abs(self._weights[fid]),
                reverse=True,
            )
            return self._most_informative_features[:n]

    def show_most_informative_features(self, n=10, show="all"):
        
        
        fids = self.most_informative_features(None)
        if show == "pos":
            fids = [fid for fid in fids if self._weights[fid] > 0]
        elif show == "neg":
            fids = [fid for fid in fids if self._weights[fid] < 0]
        for fid in fids[:n]:
            print(f"{self._weights[fid]:8.3f} {self._encoding.describe(fid)}")

    def __repr__(self):
        return "<ConditionalExponentialClassifier: %d labels, %d features>" % (
            len(self._encoding.labels()),
            self._encoding.length(),
        )

    
    
    ALGORITHMS = ["GIS", "IIS", "MEGAM", "TADM"]

    @classmethod
    def train(
        cls,
        train_toks,
        algorithm=None,
        trace=3,
        encoding=None,
        labels=None,
        gaussian_prior_sigma=0,
        **cutoffs,
    ):
        
        if algorithm is None:
            algorithm = "iis"
        for key in cutoffs:
            if key not in (
                "max_iter",
                "min_ll",
                "min_lldelta",
                "max_acc",
                "min_accdelta",
                "count_cutoff",
                "norm",
                "explicit",
                "bernoulli",
            ):
                raise TypeError("Unexpected keyword arg %r" % key)
        algorithm = algorithm.lower()
        if algorithm == "iis":
            return train_maxent_classifier_with_iis(
                train_toks, trace, encoding, labels, **cutoffs
            )
        elif algorithm == "gis":
            return train_maxent_classifier_with_gis(
                train_toks, trace, encoding, labels, **cutoffs
            )
        elif algorithm == "megam":
            return train_maxent_classifier_with_megam(
                train_toks, trace, encoding, labels, gaussian_prior_sigma, **cutoffs
            )
        elif algorithm == "tadm":
            kwargs = cutoffs
            kwargs["trace"] = trace
            kwargs["encoding"] = encoding
            kwargs["labels"] = labels
            kwargs["gaussian_prior_sigma"] = gaussian_prior_sigma
            return TadmMaxentClassifier.train(train_toks, **kwargs)
        else:
            raise ValueError("Unknown algorithm %s" % algorithm)



ConditionalExponentialClassifier = MaxentClassifier







class MaxentFeatureEncodingI:
    

    def encode(self, featureset, label):
        
        raise NotImplementedError()

    def length(self):
        
        raise NotImplementedError()

    def labels(self):
        
        raise NotImplementedError()

    def describe(self, fid):
        
        raise NotImplementedError()

    def train(cls, train_toks):
        
        raise NotImplementedError()


class FunctionBackedMaxentFeatureEncoding(MaxentFeatureEncodingI):
    

    def __init__(self, func, length, labels):
        
        self._length = length
        self._func = func
        self._labels = labels

    def encode(self, featureset, label):
        return self._func(featureset, label)

    def length(self):
        return self._length

    def labels(self):
        return self._labels

    def describe(self, fid):
        return "no description available"


class BinaryMaxentFeatureEncoding(MaxentFeatureEncodingI):
    

    def __init__(self, labels, mapping, unseen_features=False, alwayson_features=False):
        
        if set(mapping.values()) != set(range(len(mapping))):
            raise ValueError(
                "Mapping values must be exactly the "
                "set of integers from 0...len(mapping)"
            )

        self._labels = list(labels)
        

        self._mapping = mapping
        

        self._length = len(mapping)
        

        self._alwayson = None
        

        self._unseen = None
        

        if alwayson_features:
            self._alwayson = {
                label: i + self._length for (i, label) in enumerate(labels)
            }
            self._length += len(self._alwayson)

        if unseen_features:
            fnames = {fname for (fname, fval, label) in mapping}
            self._unseen = {fname: i + self._length for (i, fname) in enumerate(fnames)}
            self._length += len(fnames)

    def encode(self, featureset, label):
        
        encoding = []

        
        for fname, fval in featureset.items():
            
            if (fname, fval, label) in self._mapping:
                encoding.append((self._mapping[fname, fval, label], 1))

            
            elif self._unseen:
                
                for label2 in self._labels:
                    if (fname, fval, label2) in self._mapping:
                        break  
                
                else:
                    if fname in self._unseen:
                        encoding.append((self._unseen[fname], 1))

        
        if self._alwayson and label in self._alwayson:
            encoding.append((self._alwayson[label], 1))

        return encoding

    def describe(self, f_id):
        
        if not isinstance(f_id, int):
            raise TypeError("describe() expected an int")
        try:
            self._inv_mapping
        except AttributeError:
            self._inv_mapping = [-1] * len(self._mapping)
            for (info, i) in self._mapping.items():
                self._inv_mapping[i] = info

        if f_id < len(self._mapping):
            (fname, fval, label) = self._inv_mapping[f_id]
            return f"{fname}=={fval!r} and label is {label!r}"
        elif self._alwayson and f_id in self._alwayson.values():
            for (label, f_id2) in self._alwayson.items():
                if f_id == f_id2:
                    return "label is %r" % label
        elif self._unseen and f_id in self._unseen.values():
            for (fname, f_id2) in self._unseen.items():
                if f_id == f_id2:
                    return "%s is unseen" % fname
        else:
            raise ValueError("Bad feature id")

    def labels(self):
        
        return self._labels

    def length(self):
        
        return self._length

    @classmethod
    def train(cls, train_toks, count_cutoff=0, labels=None, **options):
        
        mapping = {}  
        seen_labels = set()  
        count = defaultdict(int)  

        for (tok, label) in train_toks:
            if labels and label not in labels:
                raise ValueError("Unexpected label %s" % label)
            seen_labels.add(label)

            
            for (fname, fval) in tok.items():

                
                
                
                count[fname, fval] += 1
                if count[fname, fval] >= count_cutoff:
                    if (fname, fval, label) not in mapping:
                        mapping[fname, fval, label] = len(mapping)

        if labels is None:
            labels = seen_labels
        return cls(labels, mapping, **options)


class GISEncoding(BinaryMaxentFeatureEncoding):
    

    def __init__(
        self, labels, mapping, unseen_features=False, alwayson_features=False, C=None
    ):
        
        BinaryMaxentFeatureEncoding.__init__(
            self, labels, mapping, unseen_features, alwayson_features
        )
        if C is None:
            C = len({fname for (fname, fval, label) in mapping}) + 1
        self._C = C

    @property
    def C(self):
        
        return self._C

    def encode(self, featureset, label):
        
        encoding = BinaryMaxentFeatureEncoding.encode(self, featureset, label)
        base_length = BinaryMaxentFeatureEncoding.length(self)

        
        total = sum(v for (f, v) in encoding)
        if total >= self._C:
            raise ValueError("Correction feature is not high enough!")
        encoding.append((base_length, self._C - total))

        
        return encoding

    def length(self):
        return BinaryMaxentFeatureEncoding.length(self) + 1

    def describe(self, f_id):
        if f_id == BinaryMaxentFeatureEncoding.length(self):
            return "Correction feature (%s)" % self._C
        else:
            return BinaryMaxentFeatureEncoding.describe(self, f_id)


class TadmEventMaxentFeatureEncoding(BinaryMaxentFeatureEncoding):
    def __init__(self, labels, mapping, unseen_features=False, alwayson_features=False):
        self._mapping = OrderedDict(mapping)
        self._label_mapping = OrderedDict()
        BinaryMaxentFeatureEncoding.__init__(
            self, labels, self._mapping, unseen_features, alwayson_features
        )

    def encode(self, featureset, label):
        encoding = []
        for feature, value in featureset.items():
            if (feature, label) not in self._mapping:
                self._mapping[(feature, label)] = len(self._mapping)
            if value not in self._label_mapping:
                if not isinstance(value, int):
                    self._label_mapping[value] = len(self._label_mapping)
                else:
                    self._label_mapping[value] = value
            encoding.append(
                (self._mapping[(feature, label)], self._label_mapping[value])
            )
        return encoding

    def labels(self):
        return self._labels

    def describe(self, fid):
        for (feature, label) in self._mapping:
            if self._mapping[(feature, label)] == fid:
                return (feature, label)

    def length(self):
        return len(self._mapping)

    @classmethod
    def train(cls, train_toks, count_cutoff=0, labels=None, **options):
        mapping = OrderedDict()
        if not labels:
            labels = []

        
        train_toks = list(train_toks)

        for (featureset, label) in train_toks:
            if label not in labels:
                labels.append(label)

        for (featureset, label) in train_toks:
            for label in labels:
                for feature in featureset:
                    if (feature, label) not in mapping:
                        mapping[(feature, label)] = len(mapping)

        return cls(labels, mapping, **options)


class TypedMaxentFeatureEncoding(MaxentFeatureEncodingI):
    

    def __init__(self, labels, mapping, unseen_features=False, alwayson_features=False):
        
        if set(mapping.values()) != set(range(len(mapping))):
            raise ValueError(
                "Mapping values must be exactly the "
                "set of integers from 0...len(mapping)"
            )

        self._labels = list(labels)
        

        self._mapping = mapping
        

        self._length = len(mapping)
        

        self._alwayson = None
        

        self._unseen = None
        

        if alwayson_features:
            self._alwayson = {
                label: i + self._length for (i, label) in enumerate(labels)
            }
            self._length += len(self._alwayson)

        if unseen_features:
            fnames = {fname for (fname, fval, label) in mapping}
            self._unseen = {fname: i + self._length for (i, fname) in enumerate(fnames)}
            self._length += len(fnames)

    def encode(self, featureset, label):
        
        encoding = []

        
        for fname, fval in featureset.items():
            if isinstance(fval, (int, float)):
                
                if (fname, type(fval), label) in self._mapping:
                    encoding.append((self._mapping[fname, type(fval), label], fval))
            else:
                
                if (fname, fval, label) in self._mapping:
                    encoding.append((self._mapping[fname, fval, label], 1))

                
                elif self._unseen:
                    
                    for label2 in self._labels:
                        if (fname, fval, label2) in self._mapping:
                            break  
                    
                    else:
                        if fname in self._unseen:
                            encoding.append((self._unseen[fname], 1))

        
        if self._alwayson and label in self._alwayson:
            encoding.append((self._alwayson[label], 1))

        return encoding

    def describe(self, f_id):
        
        if not isinstance(f_id, int):
            raise TypeError("describe() expected an int")
        try:
            self._inv_mapping
        except AttributeError:
            self._inv_mapping = [-1] * len(self._mapping)
            for (info, i) in self._mapping.items():
                self._inv_mapping[i] = info

        if f_id < len(self._mapping):
            (fname, fval, label) = self._inv_mapping[f_id]
            return f"{fname}=={fval!r} and label is {label!r}"
        elif self._alwayson and f_id in self._alwayson.values():
            for (label, f_id2) in self._alwayson.items():
                if f_id == f_id2:
                    return "label is %r" % label
        elif self._unseen and f_id in self._unseen.values():
            for (fname, f_id2) in self._unseen.items():
                if f_id == f_id2:
                    return "%s is unseen" % fname
        else:
            raise ValueError("Bad feature id")

    def labels(self):
        
        return self._labels

    def length(self):
        
        return self._length

    @classmethod
    def train(cls, train_toks, count_cutoff=0, labels=None, **options):
        
        mapping = {}  
        seen_labels = set()  
        count = defaultdict(int)  

        for (tok, label) in train_toks:
            if labels and label not in labels:
                raise ValueError("Unexpected label %s" % label)
            seen_labels.add(label)

            
            for (fname, fval) in tok.items():
                if type(fval) in (int, float):
                    fval = type(fval)
                
                
                
                count[fname, fval] += 1
                if count[fname, fval] >= count_cutoff:
                    if (fname, fval, label) not in mapping:
                        mapping[fname, fval, label] = len(mapping)

        if labels is None:
            labels = seen_labels
        return cls(labels, mapping, **options)







def train_maxent_classifier_with_gis(
    train_toks, trace=3, encoding=None, labels=None, **cutoffs
):
    
    cutoffs.setdefault("max_iter", 100)
    cutoffchecker = CutoffChecker(cutoffs)

    
    if encoding is None:
        encoding = GISEncoding.train(train_toks, labels=labels)

    if not hasattr(encoding, "C"):
        raise TypeError(
            "The GIS algorithm requires an encoding that "
            "defines C (e.g., GISEncoding)."
        )

    
    
    
    Cinv = 1.0 / encoding.C

    
    empirical_fcount = calculate_empirical_fcount(train_toks, encoding)

    
    unattested = set(numpy.nonzero(empirical_fcount == 0)[0])

    
    
    weights = numpy.zeros(len(empirical_fcount), "d")
    for fid in unattested:
        weights[fid] = numpy.NINF
    classifier = ConditionalExponentialClassifier(encoding, weights)

    
    log_empirical_fcount = numpy.log2(empirical_fcount)
    del empirical_fcount

    if trace > 0:
        print("  ==> Training (%d iterations)" % cutoffs["max_iter"])
    if trace > 2:
        print()
        print("      Iteration    Log Likelihood    Accuracy")
        print("      ---------------------------------------")

    
    try:
        while True:
            if trace > 2:
                ll = cutoffchecker.ll or log_likelihood(classifier, train_toks)
                acc = cutoffchecker.acc or accuracy(classifier, train_toks)
                iternum = cutoffchecker.iter
                print("     %9d    %14.5f    %9.3f" % (iternum, ll, acc))

            
            
            estimated_fcount = calculate_estimated_fcount(
                classifier, train_toks, encoding
            )

            
            for fid in unattested:
                estimated_fcount[fid] += 1
            log_estimated_fcount = numpy.log2(estimated_fcount)
            del estimated_fcount

            
            weights = classifier.weights()
            weights += (log_empirical_fcount - log_estimated_fcount) * Cinv
            classifier.set_weights(weights)

            
            if cutoffchecker.check(classifier, train_toks):
                break

    except KeyboardInterrupt:
        print("      Training stopped: keyboard interrupt")
    except:
        raise

    if trace > 2:
        ll = log_likelihood(classifier, train_toks)
        acc = accuracy(classifier, train_toks)
        print(f"         Final    {ll:14.5f}    {acc:9.3f}")

    
    return classifier


def calculate_empirical_fcount(train_toks, encoding):
    fcount = numpy.zeros(encoding.length(), "d")

    for tok, label in train_toks:
        for (index, val) in encoding.encode(tok, label):
            fcount[index] += val

    return fcount


def calculate_estimated_fcount(classifier, train_toks, encoding):
    fcount = numpy.zeros(encoding.length(), "d")

    for tok, label in train_toks:
        pdist = classifier.prob_classify(tok)
        for label in pdist.samples():
            prob = pdist.prob(label)
            for (fid, fval) in encoding.encode(tok, label):
                fcount[fid] += prob * fval

    return fcount







def train_maxent_classifier_with_iis(
    train_toks, trace=3, encoding=None, labels=None, **cutoffs
):
    
    cutoffs.setdefault("max_iter", 100)
    cutoffchecker = CutoffChecker(cutoffs)

    
    if encoding is None:
        encoding = BinaryMaxentFeatureEncoding.train(train_toks, labels=labels)

    
    empirical_ffreq = calculate_empirical_fcount(train_toks, encoding) / len(train_toks)

    
    
    
    
    
    nfmap = calculate_nfmap(train_toks, encoding)
    nfarray = numpy.array(sorted(nfmap, key=nfmap.__getitem__), "d")
    nftranspose = numpy.reshape(nfarray, (len(nfarray), 1))

    
    unattested = set(numpy.nonzero(empirical_ffreq == 0)[0])

    
    
    weights = numpy.zeros(len(empirical_ffreq), "d")
    for fid in unattested:
        weights[fid] = numpy.NINF
    classifier = ConditionalExponentialClassifier(encoding, weights)

    if trace > 0:
        print("  ==> Training (%d iterations)" % cutoffs["max_iter"])
    if trace > 2:
        print()
        print("      Iteration    Log Likelihood    Accuracy")
        print("      ---------------------------------------")

    
    try:
        while True:
            if trace > 2:
                ll = cutoffchecker.ll or log_likelihood(classifier, train_toks)
                acc = cutoffchecker.acc or accuracy(classifier, train_toks)
                iternum = cutoffchecker.iter
                print("     %9d    %14.5f    %9.3f" % (iternum, ll, acc))

            
            deltas = calculate_deltas(
                train_toks,
                classifier,
                unattested,
                empirical_ffreq,
                nfmap,
                nfarray,
                nftranspose,
                encoding,
            )

            
            weights = classifier.weights()
            weights += deltas
            classifier.set_weights(weights)

            
            if cutoffchecker.check(classifier, train_toks):
                break

    except KeyboardInterrupt:
        print("      Training stopped: keyboard interrupt")
    except:
        raise

    if trace > 2:
        ll = log_likelihood(classifier, train_toks)
        acc = accuracy(classifier, train_toks)
        print(f"         Final    {ll:14.5f}    {acc:9.3f}")

    
    return classifier


def calculate_nfmap(train_toks, encoding):
    
    
    nfset = set()
    for tok, _ in train_toks:
        for label in encoding.labels():
            nfset.add(sum(val for (id, val) in encoding.encode(tok, label)))
    return {nf: i for (i, nf) in enumerate(nfset)}


def calculate_deltas(
    train_toks,
    classifier,
    unattested,
    ffreq_empirical,
    nfmap,
    nfarray,
    nftranspose,
    encoding,
):
    r
    
    
    
    NEWTON_CONVERGE = 1e-12
    MAX_NEWTON = 300

    deltas = numpy.ones(encoding.length(), "d")

    
    
    
    A = numpy.zeros((len(nfmap), encoding.length()), "d")

    for tok, label in train_toks:
        dist = classifier.prob_classify(tok)

        for label in encoding.labels():
            
            feature_vector = encoding.encode(tok, label)
            
            nf = sum(val for (id, val) in feature_vector)
            
            for (id, val) in feature_vector:
                A[nfmap[nf], id] += dist.prob(label) * val
    A /= len(train_toks)

    
    
    
    
    
    
    
    
    for rangenum in range(MAX_NEWTON):
        nf_delta = numpy.outer(nfarray, deltas)
        exp_nf_delta = 2**nf_delta
        nf_exp_nf_delta = nftranspose * exp_nf_delta
        sum1 = numpy.sum(exp_nf_delta * A, axis=0)
        sum2 = numpy.sum(nf_exp_nf_delta * A, axis=0)

        
        for fid in unattested:
            sum2[fid] += 1

        
        deltas -= (ffreq_empirical - sum1) / -sum2

        
        n_error = numpy.sum(abs(ffreq_empirical - sum1)) / numpy.sum(abs(deltas))
        if n_error < NEWTON_CONVERGE:
            return deltas

    return deltas










def train_maxent_classifier_with_megam(
    train_toks, trace=3, encoding=None, labels=None, gaussian_prior_sigma=0, **kwargs
):
    

    explicit = True
    bernoulli = True
    if "explicit" in kwargs:
        explicit = kwargs["explicit"]
    if "bernoulli" in kwargs:
        bernoulli = kwargs["bernoulli"]

    
    if encoding is None:
        
        
        count_cutoff = kwargs.get("count_cutoff", 0)
        encoding = BinaryMaxentFeatureEncoding.train(
            train_toks, count_cutoff, labels=labels, alwayson_features=True
        )
    elif labels is not None:
        raise ValueError("Specify encoding or labels, not both")

    
    try:
        fd, trainfile_name = tempfile.mkstemp(prefix="nltk-")
        with open(trainfile_name, "w") as trainfile:
            write_megam_file(
                train_toks, encoding, trainfile, explicit=explicit, bernoulli=bernoulli
            )
        os.close(fd)
    except (OSError, ValueError) as e:
        raise ValueError("Error while creating megam training file: %s" % e) from e

    
    options = []
    options += ["-nobias", "-repeat", "10"]
    if explicit:
        options += ["-explicit"]
    if not bernoulli:
        options += ["-fvals"]
    if gaussian_prior_sigma:
        
        
        
        inv_variance = 1.0 / gaussian_prior_sigma**2
    else:
        inv_variance = 0
    options += ["-lambda", "%.2f" % inv_variance, "-tune"]
    if trace < 3:
        options += ["-quiet"]
    if "max_iter" in kwargs:
        options += ["-maxi", "%s" % kwargs["max_iter"]]
    if "ll_delta" in kwargs:
        
        
        options += ["-dpp", "%s" % abs(kwargs["ll_delta"])]
    if hasattr(encoding, "cost"):
        options += ["-multilabel"]  
    options += ["multiclass", trainfile_name]
    stdout = call_megam(options)
    
    
    try:
        os.remove(trainfile_name)
    except OSError as e:
        print(f"Warning: unable to delete {trainfile_name}: {e}")

    
    weights = parse_megam_weights(stdout, encoding.length(), explicit)

    
    weights *= numpy.log2(numpy.e)

    
    return MaxentClassifier(encoding, weights)







class TadmMaxentClassifier(MaxentClassifier):
    @classmethod
    def train(cls, train_toks, **kwargs):
        algorithm = kwargs.get("algorithm", "tao_lmvm")
        trace = kwargs.get("trace", 3)
        encoding = kwargs.get("encoding", None)
        labels = kwargs.get("labels", None)
        sigma = kwargs.get("gaussian_prior_sigma", 0)
        count_cutoff = kwargs.get("count_cutoff", 0)
        max_iter = kwargs.get("max_iter")
        ll_delta = kwargs.get("min_lldelta")

        
        if not encoding:
            encoding = TadmEventMaxentFeatureEncoding.train(
                train_toks, count_cutoff, labels=labels
            )

        trainfile_fd, trainfile_name = tempfile.mkstemp(
            prefix="nltk-tadm-events-", suffix=".gz"
        )
        weightfile_fd, weightfile_name = tempfile.mkstemp(prefix="nltk-tadm-weights-")

        trainfile = gzip_open_unicode(trainfile_name, "w")
        write_tadm_file(train_toks, encoding, trainfile)
        trainfile.close()

        options = []
        options.extend(["-monitor"])
        options.extend(["-method", algorithm])
        if sigma:
            options.extend(["-l2", "%.6f" % sigma**2])
        if max_iter:
            options.extend(["-max_it", "%d" % max_iter])
        if ll_delta:
            options.extend(["-fatol", "%.6f" % abs(ll_delta)])
        options.extend(["-events_in", trainfile_name])
        options.extend(["-params_out", weightfile_name])
        if trace < 3:
            options.extend(["2>&1"])
        else:
            options.extend(["-summary"])

        call_tadm(options)

        with open(weightfile_name) as weightfile:
            weights = parse_tadm_weights(weightfile)

        os.remove(trainfile_name)
        os.remove(weightfile_name)

        
        weights *= numpy.log2(numpy.e)

        
        return cls(encoding, weights)





def demo():
    from nltk.classify.util import names_demo

    classifier = names_demo(MaxentClassifier.train)


if __name__ == "__main__":
    demo()