Sequence graphs realizations and ambiguity in language models
Several popular language models represent local contexts in an input text as bags of words. Such representations are naturally encoded by a sequence graph whose vertices are the distinct words occurring in x, with edges representing the (ordered) co-occurrence of two words within a sliding window of size w. However, this compressed representation is not generally bijective, and may introduce some degree of ambiguity. Some sequence graphs may admit several realizations as a sequence, while others may not admit any realization. In this paper, we study the realizability and ambiguity of sequence graphs from a combinatorial and computational point of view. We consider the existence and enumeration of realizations of a sequence graph under multiple settings: window size w, presence/absence of graph orientation, and presence/absence of weights (multiplicities). When w = 2, we provide polynomial time algorithms for realizability and enumeration in all cases except the undirected/weighted setting, where we show the #P-hardness of enumeration. For a window of size at least 3, we prove hardness of all variants, even when w is considered as a constant, with the notable exception of the undirected/unweighted case for which we propose an XP algorithms for both (realizability and enumeration) problems, tight due to a corresponding W[1]-hardness result. We conclude with an integer program formulation to solve the realizability problem, and with dynamic programming to solve the enumeration problem. This work leaves open the membership to NP for both problems, a non-trivial question due to the existence of minimum realizations having exponential size on the instance encoding.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal investment in ambiguous financial markets with learning
We consider the classical multi-asset Merton investment problem under drift uncertainty, i.e. the asset price dynamics are given by geometric Brownian motions with constant but unknown drift coefficients. The investor as…
TNT-NLG, System 1: Using a statistical NLG to massively augment crowd-sourced data for neural generation
Ever since the successful application of sequence to sequence learning for neural machine translation systems (Sutskever et al., 2014), interest has surged in its applicability towards language generation in other proble…
Data-to-Text GenerationMachine TranslationSentenceText Generation+1Learning Minimally Rigid Graphs with High Realization Counts
For minimally rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations). Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory, but…
Learning Semantic Script Knowledge with Event Embeddings
Induction of common sense knowledge about prototypical sequences of events has recently received much attention. Instead of inducing this knowledge in the form of graphs, as in much of the previous work, in our method, d…
Common Sense ReasoningGenerating High-Quality Surface Realizations Using Data Augmentation and Factored Sequence Models
This work presents a new state of the art in reconstruction of surface realizations from obfuscated text. We identify the lack of sufficient training data as the major obstacle to training high-performing models, and sol…
Data Augmentation