Skip to content

Commit 408904d

Browse files
yzhangcsyzhangcs
committed
Descriptions for semiring & discribution class
1 parent 8a80b43 commit 408904d

File tree

9 files changed

+178
-13
lines changed

9 files changed

+178
-13
lines changed

‎docs/source/refs.bib

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -256,4 +256,64 @@ @inproceedings{stern-etal-2017-minimal
256256
publisher = {Association for Computational Linguistics},
257257
url = {https://aclanthology.org/P17-1076},
258258
pages = {818--827}
259+
}
260+
261+
@inproceedings{eisner-2016-inside,
262+
title = {Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)},
263+
author = {Eisner, Jason},
264+
booktitle = {Proceedings of WS},
265+
year = {2016},
266+
url = {https://www.aclweb.org/anthology/W16-5901},
267+
address = {Austin, TX},
268+
publisher = {Association for Computational Linguistics},
269+
pages = {1--17}
270+
}
271+
272+
@article{goodman-1999-semiring,
273+
title = {Semiring Parsing},
274+
author = {Goodman, Joshua},
275+
journal = {Computational Linguistics},
276+
year = {1999},
277+
url = {https://aclanthology.org/J99-4004},
278+
pages = {573--606}
279+
}
280+
281+
@inproceedings{li-eisner-2009-first,
282+
title = {First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests},
283+
author = {Li, Zhifei and
284+
Eisner, Jason},
285+
booktitle = {Proceedings of EMNLP},
286+
year = {2009},
287+
address = {Singapore},
288+
publisher = {Association for Computational Linguistics},
289+
url = {https://aclanthology.org/D09-1005},
290+
pages = {40--51}
291+
}
292+
293+
@inproceedings{hwa-2000-sample,
294+
title = {Sample Selection for Statistical Grammar Induction},
295+
author = {Hwa, Rebecca},
296+
booktitle = {Proceedings of ACL},
297+
year = {2000},
298+
address = {Hong Kong, China},
299+
publisher = {Association for Computational Linguistics},
300+
url = {https://aclanthology.org/W00-1306},
301+
doi = {10.3115/1117794.1117800},
302+
pages = {45--52}
303+
}
304+
305+
@inproceedings{kim-etal-2019-unsupervised,
306+
title = {Unsupervised Recurrent Neural Network Grammars},
307+
author = {Kim, Yoon and
308+
Rush, Alexander and
309+
Yu, Lei and
310+
Kuncoro, Adhiguna and
311+
Dyer, Chris and
312+
Melis, G{\'a}bor},
313+
booktitle = {Proceedings of NAACL},
314+
year = {2019},
315+
address = {Minneapolis, Minnesota},
316+
publisher = {Association for Computational Linguistics},
317+
url = {https://aclanthology.org/N19-1114},
318+
pages = {1105--1117}
259319
}

‎docs/source/structs/dist.rst

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
Distribution
2+
================================================================
3+
4+
.. currentmodule:: supar.structs.dist
5+
6+
StructuredDistribution
7+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
8+
.. autoclass:: StructuredDistribution
9+
:members:

‎docs/source/structs/index.rst

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,8 @@ Structs
66
.. toctree::
77
:maxdepth: 2
88

9+
dist
10+
semiring
911
tree
1012
linearchain
1113
vi

‎docs/source/structs/semiring.rst

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
Semirings
2+
================================================================
3+
4+
.. currentmodule:: supar.structs.semiring
5+
6+
Semiring
7+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
8+
.. autoclass:: Semiring
9+
:members:
10+
11+
LogSemiring
12+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
13+
.. autoclass:: LogSemiring
14+
:members:
15+
16+
MaxSemiring
17+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
18+
.. autoclass:: MaxSemiring
19+
:members:
20+
21+
KMaxSemiring
22+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
23+
.. autoclass:: KMaxSemiring
24+
:members:
25+
26+
EntropySemiring
27+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
28+
.. autoclass:: EntropySemiring
29+
:members:
30+
31+
CrossEntropySemiring
32+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
33+
.. autoclass:: CrossEntropySemiring
34+
:members:
35+
36+
KLDivergenceSemiring
37+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
38+
.. autoclass:: KLDivergenceSemiring
39+
:members:

‎supar/structs/__init__.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
# -*- coding: utf-8 -*-
22

3-
from .distribution import StructuredDistribution
3+
from .dist import StructuredDistribution
44
from .linearchain import LinearChainCRF
55
from .tree import ConstituencyCRF, Dependency2oCRF, DependencyCRF, MatrixTree
66
from .vi import (ConstituencyLBP, ConstituencyMFVI, DependencyLBP,

‎supar/structs/distribution.py renamed to ‎supar/structs/dist.py

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,14 @@
1010

1111

1212
class StructuredDistribution(Distribution):
13+
r"""
14+
Base class for structured distribution :math:`p(y)` :cite:`eisner-2016-inside,goodman-1999-semiring,li-eisner-2009-first`.
15+
16+
Args:
17+
scores (torch.Tensor):
18+
Log potentials, also for high-order cases.
19+
20+
"""
1321

1422
def __init__(self, scores, **kwargs):
1523
self.scores = scores.requires_grad_() if isinstance(scores, torch.Tensor) else [s.requires_grad_() for s in scores]
@@ -20,41 +28,77 @@ def __repr__(self):
2028

2129
@lazy_property
2230
def log_partition(self):
31+
r"""
32+
Compute the log partition function.
33+
"""
2334
return self.forward(LogSemiring)
2435

2536
@lazy_property
2637
def marginals(self):
38+
r"""
39+
Compute marginals of the distribution :math:`p(y)`.
40+
"""
2741
return self.backward(self.log_partition.sum())
2842

2943
@lazy_property
3044
def max(self):
45+
r"""
46+
Compute the max score of distribution :math:`p(y)`.
47+
"""
3148
return self.forward(MaxSemiring)
3249

3350
@lazy_property
3451
def argmax(self):
52+
r"""
53+
Compute :math:`\arg\max_y p(y)` of distribution :math:`p(y)`.
54+
"""
3555
raise NotImplementedError
3656

3757
@lazy_property
3858
def mode(self):
3959
return self.argmax
4060

4161
def kmax(self, k):
62+
r"""
63+
Compute the k-max of distribution :math:`p(y)`.
64+
"""
4265
return self.forward(KMaxSemiring(k))
4366

4467
def topk(self, k):
68+
r"""
69+
Compute the k-argmax of distribution :math:`p(y)`.
70+
"""
4571
raise NotImplementedError
4672

4773
@lazy_property
4874
def entropy(self):
75+
r"""
76+
Compute entropy :math:`H[p]` of distribution :math:`p(y)`.
77+
"""
4978
return self.forward(EntropySemiring)
5079

5180
def cross_entropy(self, other):
81+
r"""
82+
Compute cross-entropy :math:`H[p,q]` of self and another distribution.
83+
84+
Args:
85+
other (~supar.structs.dist.StructuredDistribution): Comparison distribution.
86+
"""
5287
return (self + other).forward(CrossEntropySemiring)
5388

5489
def kl(self, other):
90+
r"""
91+
Compute KL-divergence :math:`KL[p \parallel q]=H[p,q]-H[p]` of self and another distribution.
92+
93+
Args:
94+
other (~supar.structs.dist.StructuredDistribution): Comparison distribution.
95+
"""
5596
return (self + other).forward(KLDivergenceSemiring)
5697

5798
def log_prob(self, value, **kwargs):
99+
"""
100+
Computes log probability over values :math:`p(y)`.
101+
"""
58102
return self.score(value, **kwargs) - self.log_partition
59103

60104
def score(self, value):

‎supar/structs/linearchain.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
# -*- coding: utf-8 -*-
22

33
import torch
4-
from torch.distributions.utils import lazy_property
5-
from supar.structs.distribution import StructuredDistribution
4+
from supar.structs.dist import StructuredDistribution
65
from supar.structs.semiring import LogSemiring
6+
from torch.distributions.utils import lazy_property
77

88

99
class LinearChainCRF(StructuredDistribution):

‎supar/structs/semiring.py

Lines changed: 20 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -8,10 +8,12 @@
88

99
class Semiring(object):
1010
r"""
11-
A semiring is defined by a tuple `<K, +, ×, 0, 1>` :cite:`goodman-1999-semiring`.
12-
`K` is a set of values;
13-
`+` is commutative, associative and has an identity element `0`;
14-
`×` is associative, has an identity element `1` and distributes over `+`.
11+
Base semiring class :cite:`goodman-1999-semiring`.
12+
13+
A semiring is defined by a tuple :math:`<K, \oplus, \otimes, \mathbf{0}, \mathbf{1}>`.
14+
:math:`K` is a set of values;
15+
:math:`\oplus` is commutative, associative and has an identity element `0`;
16+
:math:`\otimes` is associative, has an identity element `1` and distributes over `+`.
1517
"""
1618

1719
zero = 0
@@ -80,7 +82,7 @@ def unconvert(cls, x):
8082

8183
class LogSemiring(Semiring):
8284
r"""
83-
Log-space semiring: `<logsumexp, +, -inf, 0>`.
85+
Log-space semiring :math:`<\mathrm{logsumexp}, +, -\infty, 0>`.
8486
"""
8587

8688
zero = MIN
@@ -101,7 +103,7 @@ def prod(cls, x, dim=-1):
101103

102104
class MaxSemiring(LogSemiring):
103105
r"""
104-
Max semiring `<max, +, -inf, 0>`.
106+
Max semiring :math:`<\mathrm{max}, +, -\infty, 0>`.
105107
"""
106108

107109
@classmethod
@@ -111,7 +113,7 @@ def sum(cls, x, dim=-1):
111113

112114
def KMaxSemiring(k):
113115
r"""
114-
k-max semiring `<kmax, +, [-inf, -inf, ...], [0, -inf, ...]>`.
116+
k-max semiring :math:`<\mathrm{kmax}, +, [-\infty, -\infty, \dots], [0, -\infty, \dots]>`.
115117
"""
116118

117119
class KMaxSemiring(LogSemiring):
@@ -139,7 +141,9 @@ def one_(cls, x):
139141

140142
class EntropySemiring(LogSemiring):
141143
"""
142-
Entropy expectation semiring: `<logsumexp, +, -inf, 0>` :cite:`li-eisner-2009-first`.
144+
Entropy expectation semiring: :math:`<\oplus, +, [-\infty, 0], [0, 0]>`,
145+
where :math:`\oplus` computes the log-values and the running distributional entropy :math:`H[p]`
146+
:cite:`li-eisner-2009-first,hwa-2000-sample,kim-etal-2019-unsupervised`.
143147
"""
144148

145149
@classmethod
@@ -174,7 +178,9 @@ def one_(cls, x):
174178

175179
class CrossEntropySemiring(LogSemiring):
176180
"""
177-
Cross entropy expectation semiring: `<logsumexp, +, -inf, 0>` :cite:`li-eisner-2009-first`.
181+
Cross Entropy expectation semiring: :math:`<\oplus, +, [-\infty, -\infty, 0], [0, 0, 0]>`,
182+
where :math:`\oplus` computes the log-values and the running distributional cross entropy :math:`H[p,q]`
183+
of the two distributions :cite:`li-eisner-2009-first`.
178184
"""
179185

180186
@classmethod
@@ -208,6 +214,11 @@ def one_(cls, x):
208214

209215

210216
class KLDivergenceSemiring(LogSemiring):
217+
"""
218+
KL divergence expectation semiring: :math:`<\oplus, +, [-\infty, -\infty, 0], [0, 0, 0]>`,
219+
where :math:`\oplus` computes the log-values and the running distributional KL divergence :math:`KL[p \parallel q]`
220+
of the two distributions :cite:`li-eisner-2009-first`.
221+
"""
211222
"""
212223
KL divergence expectation semiring: `<logsumexp, +, -inf, 0>` :cite:`li-eisner-2009-first`.
213224
"""

‎supar/structs/tree.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
import torch
44
import torch.nn as nn
5-
from supar.structs.distribution import StructuredDistribution
5+
from supar.structs.dist import StructuredDistribution
66
from supar.structs.semiring import LogSemiring
77
from supar.utils.alg import mst
88
from supar.utils.fn import stripe

0 commit comments

Comments
 (0)