Systems and methods for unsupervised autoregressive text compression

1. A method for unsupervised text compression, the method comprising:

receiving an input sentence having a plurality of tokens;

assigning a score to each token in the plurality of tokens based on a pretrained bidirectional language model;

determining a directed acyclic graph representation having a plurality of nodes based on assigned scores, at least one node representing a candidate intermediate sentence after deleting one or more tokens from the input sentence;

progressively searching for a next deletion on the directed acyclic graph representation via progressive lookahead greedy search;

determining a deletion path comprising an ordered collection of intermediate sentences, at least one intermediate sentence along the deletion path represents a shorter version of a previous intermediate sentence, from the progressive lookahead greedy search, wherein each node on the deletion path in the directed acyclic graph points to a candidate intermediate sentence after deleting one or more tokens from the input sentence at the respective node; and

generating a compressed sentence following the deletion path that progressively deletes tokens from the input sentence.

2. The method of claim 1 , wherein assigning the respective average perplexity score based on the respective candidate intermediate sentence comprises:

determining a first set of tokens present in the respective candidate intermediate sentence;

determining a second set of tokens that have been deleted from the input sentence to result in the respective candidate intermediate sentence; and

calculating the respective average perplexity score based on a sum of logarithms of scores corresponding to the first set of tokens and scores corresponding to the second set of tokens.

3. The method of claim 1 , wherein determining the directed acyclic graph representation comprises:

designating a root node of the directed acyclic graph representing the input sentence;

designating a first lower level of nodes that are directly connected to the root node to a first set of candidate intermediate sentences, respectively, each candidate intermediate sentence from the first set being obtained after deleting the one or more tokens from the input sentence; and

for each outgoing edge connecting from the root node to one of the first lower level of nodes, assigning a respective average perplexity score based on a respective candidate intermediate sentence.

4. The method of claim 3 , wherein progressively searching for the next deletion on the directed acyclic graph representation via progressive lookahead greedy search comprises:

determining a first node from the first lower level corresponding to a first next candidate intermediate sentence having a first minimum average perplexity score among the first set of candidate intermediate sentences the next deletion; and

adding the first node to the deletion path.

5. The method of claim 4 , further comprising:

designating a second lower level of nodes that are directly connected to the first node to a second set of candidate intermediate sentences, respectively, each candidate intermediate sentence from the second set being obtained after further deleting one or more tokens from the first next candidate intermediate sentence;

determining a second node from the second lower level corresponding to a second next candidate intermediate sentence having a second minimum average perplexity score among the second set of candidate intermediate sentences the next deletion; and

adding the second node to the deletion path.

6. The method of claim 1 , wherein progressively searching for a next deletion on the directed acyclic graph representation via progressive lookahead greedy search comprises:

setting a first deletion length; and

determining the directed acyclic graph representation having the plurality of nodes corresponding to candidate intermediate sentences based on the first deletion length;

determining whether at least one candidate intermediate sentence from the directed acyclic graph representation corresponds to a score that satisfies a predetermined threshold condition; and

in response to determining that no candidate intermediate sentence from the directed acyclic graph representation has the score satisfying the predetermined threshold condition, re-setting the first deletion length to a second deletion length that is greater than the first deletion length.

7. The method of claim 6 , wherein the predetermined threshold condition includes: a ratio between a first average perplexity score corresponding to a next probing step and a second average perplexity score corresponding to a current probing step is greater than a pre-determined threshold.

8. The method of claim 7 , further comprising:

applying a parameter relating to the length of the current sentence to the first average perplexity score while evaluating the predetermined threshold condition.

9. The method of claim 8 , further comprising:

tuning the parameter to control an extent of deletion rate of the deletion path.

10. A system for unsupervised text compression, the system comprising:

a memory containing machine readable medium storing machine executable code; and

one or more processors coupled to the memory and configurable to execute the machine executable code to cause the one or more processors to:

receive an input sentence having a plurality of tokens;

assign a score to each token in the plurality of tokens based on a pretrained bidirectional language model;

determine a directed acyclic graph representation having a plurality of nodes based on assigned scores, at least one node representing a candidate intermediate sentence after deleting one or more tokens from the input sentence;

progressively search for a next deletion on the directed acyclic graph representation via progressive lookahead greedy search;

determine a deletion path comprising an ordered collection of intermediate sentences, at least one intermediate sentence along the deletion path represents a shorter version of a previous intermediate sentence, from the progressive lookahead greedy search, wherein each node on the deletion path in the directed acyclic graph points to a candidate intermediate sentence after deleting one or more tokens from the input sentence at the respective node; and

generate a compressed sentence following the deletion path that progressively deletes tokens from the input sentence.

11. The system of claim 10 , wherein the machine executable code further causes the one or more processors to assign the respective average perplexity score based on the respective candidate intermediate sentence by:

determining a first set of tokens present in the respective candidate intermediate sentence;

determining a second set of tokens that have been deleted from the input sentence to result in the respective candidate intermediate sentence; and

calculating the respective average perplexity score based on a sum of logarithms of scores corresponding to the first set of tokens and scores corresponding to the second set of tokens.

12. The system of claim 10 , wherein the machine executable code further causes the one or more processors to:

designate a root node of the directed acyclic graph representing the input sentence;

designate a first lower level of nodes that are directly connected to the root node to a first set of candidate intermediate sentences, respectively, each candidate intermediate sentence from the first set being obtained after deleting the one or more tokens from the input sentence; and

for each outgoing edge connecting from the root node to one of the first lower level of nodes, assign a respective average perplexity score based on a respective candidate intermediate sentence.

13. The system of claim 12 , wherein the machine executable code further causes the one or more processors to progressively searching for the next deletion on the directed acyclic graph representation via progressive lookahead greedy search by:

determining a first node from the first lower level corresponding to a first next candidate intermediate sentence having a first minimum average perplexity score among the first set of candidate intermediate sentences the next deletion; and

adding the first node to the deletion path.

14. The system of claim 13 , wherein the machine executable code further causes the one or more processors to:

designate a second lower level of nodes that are directly connected to the first node to a second set of candidate intermediate sentences, respectively, each candidate intermediate sentence from the second set being obtained after further deleting one or more tokens from the first next candidate intermediate sentence;

determine a second node from the second lower level corresponding to a second next candidate intermediate sentence having a second minimum average perplexity score among the second set of candidate intermediate sentences the next deletion; and

add the second node to the deletion path.

15. The system of claim 10 , wherein the machine executable code further causes the one or more processors to progressively search for a next deletion on the directed acyclic graph representation via progressive lookahead greedy search by:

setting a first deletion length; and

determining the directed graph representation having the plurality of nodes corresponding to candidate intermediate sentences based on the first deletion length;

determining whether at least one candidate intermediate sentence from the directed acyclic graph representation corresponds to a score that satisfies a predetermined threshold condition; and

in response to determining that no candidate intermediate sentence from the directed acyclic graph representation has the score satisfying the predetermined threshold condition, re-setting the first deletion length to a second deletion length that is greater than the first deletion length.

16. The system of claim 15 , wherein the predetermined threshold condition includes: a ratio between a first average perplexity score corresponding to a next probing step and a second average perplexity score corresponding to a current probing step is greater than a pre-determined threshold.

17. The system of claim 16 , wherein the machine executable code further causes the one or more processors to:

apply a parameter relating to the length of the current sentence to the first average perplexity score while evaluating the predetermined threshold condition.

18. The system of claim 17 , wherein the machine executable code further causes the one or more processors to:

tune the parameter to control an extent of deletion rate of the deletion path.