anirudh9119
commented
8 years ago I have not read the paper, till now. I should read it today! And then may be if you have time, we could discuss about this ?
- - Anirudh
On Wed, Mar 23, 2016 at 12:14 PM, Bart van Merriënboer < notifications@github.com> wrote:
I was just reading Junyoung's paper http://arxiv.org/abs/1603.06147 on using a character-level decoder. Although it's nice to see it works, I think the results are slightly misleading because the paper only compares to BPE segmented NMT and SMT, and not to word-level NMT (which does better or comparably well http://www.emnlp2015.org/proceedings/WMT/pdf/WMT14.pdf).
It made me think about BPE though (as described for NMT in this paper http://arxiv.org/abs/1508.07909). To try and formalize my thoughts a little bit, some notation:
- Consider a dictionary of tokens, T = {t1, ..., tn}.
- Let |ti| denote the string length of this token (i.e. the number of characters in ti)
- Our input text is segmented using the minimum amount of tokens. (This is a problem in itself that requires e.g. dynamic programming I guess.)
- Let f(ti) denote the number of times ti is used in this segmentation (i.e. the frequency of the token).
- The following objectives are reasonable to optimize when constructing T:
- Minimize |T|, because it reduces the size of the softmax and number of embeddings to learn
- Minimize the number of segments, s = ∑i f(ti), because this simplifies the problem (shorter sequences, less non-linear)
- Maximize f(ti), because we want a large number of examples per token to learn
- Minimize the total string length of the dictionary, l = ∑i |ti|, because this minimizes the amount of redundancy in the dictionary
If we consider that avg(f(ti)) = s / |T|, it's clear that minimizing (i) also maximizes (iii). Intuitively, (iv) and (i) are also closely related (adding/removing a token in T can only increase/decrease l). We can also make crude approximations saying that n = ∑i f(ti)|ti| ≈ s / |T| * l ⇒ l ≈ n / s * |T|, where n is the length of the text.
However, it's clear that (ii) and (iii) are competing objectives. We kind of want to minimize globally, but maximize locally, so perhaps an objective like s + ∑i |f(ti) - s / |T||2 is what you really want as a final objective.
You can actually optimize (i), (iii) and (iv) by simply letting T be equal to the set of characters (more accurately, with characters that only appear in pairs, merged). Objective (ii) is the competing objective here that makes us want to have more and longer tokens.
Now, the way I understand BPE, the algorithm works like this:
- Construct a dictionary, T, of all characters appearing in your text.
- Segment your text W into characters, W = (w1, ..., wm) where wi ∈ T.
- Define the number of merge operations K.
- For k = 1, ..., K
- Count the number of occurrences as a subsequence in W for all pairs (ti, tj) ∈ T × T
- Replace the most frequent pair (ti, tj) with a new token, t', and add it to the dictionary (i.e. merge the two tokens).
- If the new counts, f(ti') and f(tj') are zero, remove ti and/or tj from T respectively.
This minimizes s, since each merge operation reduces s by f(t'). The fact that we set K as a hyperparameter is the only thing stopping BPE from greedily optimizing s at the expense of the other objectives, since:
- The new dictionary size |T ∪ t'| = |T| - 1 + [f(t') = f(ti)] + [f(t') = f(tj)] i.e. it can increase or decrease, but statistically speaking is more likely to increase, which hurts objective (i).
- The new counts are f(ti') = f(ti) - f(t') and f(tj') = f(tj) - f(t') i.e. they will always decrease, which hurts objective (iii).
- The new dictionary string length l' = l - |ti|[f(t') = f(ti)] - |tj|[f(t') = f(tj)] + |t'| i.e. it can increase or decrease, but is more likely to increase and hurt objective (iv).
This is getting a bit long, but I guess the question is: Is there an easy way of adapting BPE so that it more intelligently optimizes these multiple objectives? The main thing I think we would need is a form of pruning: If a merger of two tokens reduces the frequency of the constituents significantly enough, we want to remove these from the dictionary altogether.
— You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub https://github.com/bartvm/nmt/issues/64
aalmah
bartvm
JinseokNam
I was just reading Junyoung's paper on using a character-level decoder. Although it's nice to see it works, I think the results are slightly misleading because the paper only compares to BPE segmented NMT and SMT, and not to word-level NMT (which does better or comparably well).
It made me think about BPE though (as described for NMT in this paper). To try and formalize my thoughts a little bit, some notation:
If we consider that avg(f(ti)) = s / |T|, it's clear that minimizing (i) also maximizes (iii). Intuitively, (iv) and (i) are also closely related (adding/removing a token in T can only increase/decrease l). We can also make crude approximations saying that n = ∑i f(ti)|ti| ≈ s / |T| * l ⇒ l ≈ n / s * |T|, where n is the length of the text.
However, it's clear that (ii) and (iii) are competing objectives. We kind of want to minimize globally, but maximize locally, so perhaps an objective like s + ∑i |f(ti) - s / |T||2 is what you really want as a final objective.
You can actually optimize (i), (iii) and (iv) by simply letting T be equal to the set of characters (more accurately, with characters that only appear in pairs, merged). Objective (ii) is the competing objective here that makes us want to have more and longer tokens.
Now, the way I understand BPE, the algorithm works like this:
This minimizes s, since each merge operation reduces s by f(t'). The fact that we set K as a hyperparameter is the only thing stopping BPE from greedily optimizing s at the expense of the other objectives, since:
This is getting a bit long, but I guess the question is: Is there an easy way of adapting BPE so that it more intelligently optimizes these multiple objectives? The main thing I think we would need is a form of pruning: If a merger of two tokens reduces the frequency of the constituents significantly enough, we want to remove these from the dictionary altogether (or not perform the merger).