-
Notifications
You must be signed in to change notification settings - Fork 2.8k
/
maxent.py
1569 lines (1291 loc) · 57.9 KB
/
maxent.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
# Natural Language Toolkit: Maximum Entropy Classifiers
#
# Copyright (C) 2001-2023 NLTK Project
# Author: 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.
"""
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"
######################################################################
# { Classifier Model
######################################################################
class MaxentClassifier(ClassifierI):
"""
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))
"""
def __init__(self, encoding, weights, logarithmic=True):
"""
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._encoding = encoding
self._weights = weights
self._logarithmic = logarithmic
# self._logarithmic = False
assert encoding.length() == len(weights)
def labels(self):
return self._encoding.labels()
def set_weights(self, new_weights):
"""
Set the feature weight vector for this classifier.
:param new_weights: The new feature weight vector.
:type new_weights: list of float
"""
self._weights = new_weights
assert self._encoding.length() == len(new_weights)
def weights(self):
"""
:return: The feature weight vector for this classifier.
:rtype: list of float
"""
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
# Normalize the dictionary to give a probability distribution
return DictionaryProbDist(prob_dict, log=self._logarithmic, normalize=True)
def explain(self, featureset, columns=4):
"""
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.
"""
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] # hack
descr += " (%s)" % f_val # hack
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):
"""
Generates the ranked list of informative features from most to least.
"""
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"):
"""
: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.
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(),
)
#: A list of the algorithm names that are accepted for the
#: ``train()`` method's ``algorithm`` parameter.
ALGORITHMS = ["GIS", "IIS", "MEGAM", "TADM"]
@classmethod
def train(
cls,
train_toks,
algorithm=None,
trace=3,
encoding=None,
labels=None,
gaussian_prior_sigma=0,
**cutoffs,
):
"""
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``.
"""
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)
#: Alias for MaxentClassifier.
ConditionalExponentialClassifier = MaxentClassifier
######################################################################
# { Feature Encodings
######################################################################
class MaxentFeatureEncodingI:
"""
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.
"""
def encode(self, featureset, label):
"""
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))
"""
raise NotImplementedError()
def length(self):
"""
:return: The size of the fixed-length joint-feature vectors
that are generated by this encoding.
:rtype: int
"""
raise NotImplementedError()
def labels(self):
"""
: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
"""
raise NotImplementedError()
def describe(self, fid):
"""
:return: A string describing the value of the joint-feature
whose index in the generated feature vectors is ``fid``.
:rtype: str
"""
raise NotImplementedError()
def train(cls, train_toks):
"""
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.
"""
raise NotImplementedError()
class FunctionBackedMaxentFeatureEncoding(MaxentFeatureEncodingI):
"""
A feature encoding that calls a user-supplied function to map a
given featureset/label pair to a sparse joint-feature vector.
"""
def __init__(self, func, length, labels):
"""
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``.
"""
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):
"""
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.
"""
def __init__(self, labels, mapping, unseen_features=False, alwayson_features=False):
"""
: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.
"""
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)
"""A list of attested labels."""
self._mapping = mapping
"""dict mapping from (fname,fval,label) -> fid"""
self._length = len(mapping)
"""The length of generated joint feature vectors."""
self._alwayson = None
"""dict mapping from label -> fid"""
self._unseen = None
"""dict mapping from fname -> fid"""
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):
# Inherit docs.
encoding = []
# Convert input-features to joint-features:
for fname, fval in featureset.items():
# Known feature name & value:
if (fname, fval, label) in self._mapping:
encoding.append((self._mapping[fname, fval, label], 1))
# Otherwise, we might want to fire an "unseen-value feature".
elif self._unseen:
# Have we seen this fname/fval combination with any label?
for label2 in self._labels:
if (fname, fval, label2) in self._mapping:
break # we've seen this fname/fval combo
# We haven't -- fire the unseen-value feature
else:
if fname in self._unseen:
encoding.append((self._unseen[fname], 1))
# Add always-on features:
if self._alwayson and label in self._alwayson:
encoding.append((self._alwayson[label], 1))
return encoding
def describe(self, f_id):
# Inherit docs.
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):
# Inherit docs.
return self._labels
def length(self):
# Inherit docs.
return self._length
@classmethod
def train(cls, train_toks, count_cutoff=0, labels=None, **options):
"""
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``.
"""
mapping = {} # maps (fname, fval, label) -> fid
seen_labels = set() # The set of labels we've encountered
count = defaultdict(int) # maps (fname, fval) -> count
for tok, label in train_toks:
if labels and label not in labels:
raise ValueError("Unexpected label %s" % label)
seen_labels.add(label)
# 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.
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):
"""
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.
"""
def __init__(
self, labels, mapping, unseen_features=False, alwayson_features=False, C=None
):
"""
: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__``
"""
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):
"""The non-negative constant that all encoded feature vectors
will sum to."""
return self._C
def encode(self, featureset, label):
# Get the basic encoding.
encoding = BinaryMaxentFeatureEncoding.encode(self, featureset, label)
base_length = BinaryMaxentFeatureEncoding.length(self)
# Add a correction feature.
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 the result
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 = []
# This gets read twice, so compute the values in case it's lazy.
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):
"""
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.
"""
def __init__(self, labels, mapping, unseen_features=False, alwayson_features=False):
"""
: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.
"""
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)
"""A list of attested labels."""
self._mapping = mapping
"""dict mapping from (fname,fval,label) -> fid"""
self._length = len(mapping)
"""The length of generated joint feature vectors."""
self._alwayson = None
"""dict mapping from label -> fid"""
self._unseen = None
"""dict mapping from fname -> fid"""
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):
# Inherit docs.
encoding = []
# Convert input-features to joint-features:
for fname, fval in featureset.items():
if isinstance(fval, (int, float)):
# Known feature name & value:
if (fname, type(fval), label) in self._mapping:
encoding.append((self._mapping[fname, type(fval), label], fval))
else:
# Known feature name & value:
if (fname, fval, label) in self._mapping:
encoding.append((self._mapping[fname, fval, label], 1))
# Otherwise, we might want to fire an "unseen-value feature".
elif self._unseen:
# Have we seen this fname/fval combination with any label?
for label2 in self._labels:
if (fname, fval, label2) in self._mapping:
break # we've seen this fname/fval combo
# We haven't -- fire the unseen-value feature
else:
if fname in self._unseen:
encoding.append((self._unseen[fname], 1))
# Add always-on features:
if self._alwayson and label in self._alwayson:
encoding.append((self._alwayson[label], 1))
return encoding
def describe(self, f_id):
# Inherit docs.
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):
# Inherit docs.
return self._labels
def length(self):
# Inherit docs.
return self._length
@classmethod
def train(cls, train_toks, count_cutoff=0, labels=None, **options):
"""
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``.
"""
mapping = {} # maps (fname, fval, label) -> fid
seen_labels = set() # The set of labels we've encountered
count = defaultdict(int) # maps (fname, fval) -> count