acl acl2010 acl2010-7 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthew Skala ; Victoria Krakovna ; Janos Kramar ; Gerald Penn
Abstract: Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques.
Reference: text
sentIndex sentText sentNum sentScore
1 {vkrakovna , Abstract Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. [sent-5, score-0.815]
2 We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. [sent-7, score-1.128]
3 A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. [sent-9, score-0.229]
4 An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques. [sent-10, score-0.473]
5 1 Introduction The use of bit vectors is almost as old as HPSG parsing itself. [sent-11, score-0.344]
6 , 1989) as a method for computing the unification of two types without table lookup, bit vectors have been attractive because of three speed advantages: • • The classical bit vector encoding uses bitwise TAhNeD c tasos iccaalcl builatt vee type uncnoifdiicnagtio uns. [sent-13, score-1.047]
7 That is exponential time in the worst case; most bit vector methods avoid explicitly computing it. [sent-16, score-0.364]
8 c s 2o0c1ia0ti Aosnso focria Ctio nm fpourta Ctoiomnpault Laitniognuaislt Licisn,g puaigsetisc 1s512–1521, the observation that counting the number of one bits in an integer is implemented in the basic instruction sets of many CPUs. [sent-39, score-0.442]
9 The question then arises whether smaller codes would be obtained by relaxing zero preservation so that any resulting vector with at most λ bits is interpreted as failure, with λ ≥ 1. [sent-40, score-0.534]
10 Penn (2002) generalized join-preserving encodings of partial orders to the case where more than one code can be used to represent the same object, but the focus there was on codes arising from successful unifications; there was still only one representative for failure. [sent-41, score-0.321]
11 We note at the outset that we are not using Bloom filters as such, but rather a derandomized encoding scheme that shares with Bloom filters the essential insight that λ can be greater than zero without adverse consequences for the required algebraic properties of the encoding. [sent-43, score-0.349]
12 un Wde or join tof v u, v ∈ X, eif th one exists, eaansdt u up v fbooru nthde greatest flo uw,ver ∈ ∈ bo Xu,n idf or meet. [sent-48, score-0.222]
13 Iofrd weer rneeleadtio an s aencodn g pfoarrt iiatsl join operation. [sent-51, score-0.222]
14 W foer are especially interested in a class of partial orders called meet semilattices, in which every pair of elements has a unique meet. [sent-52, score-0.372]
15 In a meet semilattice, the join of two elements is unique when it exists at all, and there is a unique globally least element ⊥ (“bottom”). [sent-53, score-0.598]
16 A successor of an element u ∈ X is an element v u ∈ Xes ssourch o fth aant u v v atn ud ∈th Xere i iss a no w ∈ Xnt wvi 6=th w u, w v, uan vd u v w v v, i. [sent-54, score-0.322]
17 A meet irreducible element is an element u ∈ X such that for any v, w ∈ X, itf i u = v eum w tth uen ∈ u = v or u = w. [sent-60, score-0.39]
18 2 Bit-vector encoding Intuitively, taking thejoin oftwo types in a type hierarchy is like taking the intersection of two sets. [sent-66, score-0.384]
19 Types often represent sets of possible values, and the type represented by the join really does represent the intersection of the sets that formed the input. [sent-67, score-0.401]
20 So it seems natural to embed a partial order of types hX, vi into a partial order (in fact, a lattice) otyfp seests h hY, ? [sent-68, score-0.271]
21 Tt ohfen s join g ti sZ simply set hinet seurpseecrtsieotn r e∩la. [sent-71, score-0.222]
22 th Terh a join exists, can be naturally defined by g(f(u) , f(v)) = 0 if and only if f(u) ∩ f(v) = ∅. [sent-73, score-0.222]
23 They set Z to be the set of all meet irreducible elements in X; and f(u) = {v ∈ Z|v w u}, that is, the imne Xet ;ir arenddu fci(bule) e=lem {ven ∈ts greater th u}an, or equal htoe u. [sent-77, score-0.296]
24 If Z is chosen to be the maximal elements of X instead, then join preservation is lost but the embedding still preserves order, success, and failure. [sent-79, score-0.6]
25 We construct shorter bit vectors by modifying the definition of g, so that the minimality results 1513 no longer apply. [sent-85, score-0.344]
26 Consider a meet semilattice containing only the bottom element ⊥ and n maximal elements all incomparable mtoe enatc ⊥h oatnhder n. [sent-89, score-0.603]
27 We would thus be spending n bits to represent a choice among n + 1alterna- tives, which should fit into a logarithmic number of bits. [sent-91, score-0.339]
28 With the traditional bit vector construction, each of the maximal elements consumes its own bit, even though those bits are highly correlated. [sent-93, score-0.893]
29 There, it is desired to store a large array of bits subject to two considerations. [sent-95, score-0.431]
30 The solution proposed by Bloom and widely used in the decades since is to map the entries in the large bit array pseudorandomly (by means of a hash function) into the entries of a small bit array. [sent-98, score-0.73]
31 To store a one bit we find its hashed location and store it there. [sent-99, score-0.472]
32 If we query a bit for which the answer should be zero but it happens to have the same hashed location as another query with the answer one, then we return a one and that is one of our tolerated errors. [sent-100, score-0.58]
33 To reduce the error rate we can elaborate the construction further: with some fixed k, we use k hash functions to map each bit in the large array to several locations in the small one. [sent-101, score-0.433]
34 There will be many collisions ofindividual hashed locations, as shown; but the chances are good that when we query a bit we did not intend to store in the filter, at least one of its hashed locations will still be empty, and so the query will 1? [sent-105, score-0.69]
35 In general, the hashed array can be much smaller than the original unhashed array (Bloom, 1970). [sent-108, score-0.231]
36 Classical Bloom filtering applied to the sparse vectors of the embedding would create some percentage of incorrect join results, which would then have to be handled by other techniques. [sent-109, score-0.364]
37 2 Modified failure detection In the traditional bit vector construction, types map to sets, join is computed by intersection of sets, and the empty set corresponds to failure (where no join exists). [sent-112, score-1.129]
38 In the traditional construction, to preserve joins we must assign one bit to each of the meet-irreducible elements {d, e, f,g, h, i,j,k, l, m}, for a total of teelenm m beintst. [sent-117, score-0.581]
39 As a more general example, consider the very simple meet semilattice consisting of just a least element ⊥ with n maximal elements incomparabelleem mtoe neta c⊥h owtihtehr. [sent-120, score-0.55]
40 his in b bits by choosing the smallest b such that ? [sent-122, score-0.385]
41 Both their technique and ours are at a disadvantage when applied to large trees; in particular, if the bottom of the partial order has successors which are not joinable with each other, then those will be assigned large sets with little overlap, and bits in the vectors will tend to be wasted. [sent-132, score-0.83]
42 To find the join of two types in the same module, we find the intersection of their encodings and check whether it is of size greater than λ. [sent-140, score-0.451]
43 For the remaining cases, where at least one of the types lacks a module, we observe that the module bottoms and non-module types form a tree, and the join can be computed in that tree. [sent-142, score-0.421]
44 If x is a type in the module whose bottom is y, and z has no module, then x t z = y t z unless y t z = y imn wdhuliceh, case x tt z = x; so uitn only y re tma zin =s t oy compute joins xw tithi zn =the x ;tre seo. [sent-143, score-0.265]
45 3 Set programming Ideally, we would like to have an efficient algorithm for finding the best possible encoding of any given meet semilattice. [sent-146, score-0.515]
46 The encoding can be represented as a collection of sets of integers (representing bit indices that contain ones), and an optimal encoding is the collection of sets whose over- all union is smallest subject to the constraint that the collection forms an encoding at all. [sent-147, score-1.172]
47 The reduction of partial order representation to set programming is clear: we create a set variable for every type, force the maximal types’ sets to contain at least 1elements, and then use subset to enforce that every type is a superset of all its successors (preserving order and success). [sent-159, score-0.685]
48 Gtiv xen a constraint satisfaction problem like this one, we can ask two questions: is there a feasible solution, assigning values to the variables so all constraints are satisfied; and if so what is the optimal solution, producing the best value of the objective while remaining feasible? [sent-163, score-0.302]
49 Ongoing research on set programming has produced a variety of software tools for solving these problems. [sent-167, score-0.236]
50 However, at first blush our instances are much too large for readily-available set programming tools. [sent-168, score-0.247]
51 1 Simplifying the instances First of all, we only use minimum cardinality constraints |Si | ≥ ri for maximal types; and every ri ≥ tλs 1. [sent-173, score-0.329]
52 | G≥iv ren a feasible bit assignment for a ma≥xim λa +l type wiviethn more stihbalen ri te alessmiegnnmts einn tit fso set Si, we can always remove elements until it has exactly ri elements, without violating the other constraints. [sent-174, score-0.576]
53 Now, let a choke-vertex in the partial order hX, vi be an element u ∈ X such that for every v, w ∈ Xn e wlemheerent v uis ∈ a successor aotf w a envdu v v, we ∈ha Xve u v w. [sent-180, score-0.349]
54 Choke-vertices are important because the optimal bit assignment for elements after a chokevertex u is almost independent of the bit assign- ment elsewhere in the partial order. [sent-185, score-0.85]
55 Removing the redundant constraints means there are no constraints between elements after u and elements before, or incomparable with, u. [sent-186, score-0.426]
56 As a result, we can solve a smaller instance consisting of u and everything after it, to find the minimal number of bits ru for representing u. [sent-188, score-0.339]
57 Then we solve the rest of the problem with a constraint |Su | = ru, excluding arollb partial iothrde ar ceolenmsteranintst ta |fSter| u, an rd then combine the two solutions with any arbitrary bijection between the set elements assigned to u in each solution. [sent-189, score-0.284]
58 2 Splitting into components If we cut the partial order at every choke-vertex, we reduce the huge and impractical encoding problem to a collection of smaller ones. [sent-192, score-0.312]
59 The cutting expresses the original partial order as a tree of components, each of which corresponds to a set programming instance. [sent-193, score-0.29]
60 We can find an optimal encoding for the entire partial order by optimally encoding the components, starting with the leaves of that tree and working our way back to the root. [sent-195, score-0.598]
61 The division into components creates a collection of set programming instances with a wide range of sizes and difficulty; we examine each instance and choose appropriate techniques for each one. [sent-196, score-0.247]
62 These include when λ = 0 regardless of the structure of the component; when the component consists of a bottom and zero, one, or two nonjoinable successors; and when there is one element (a top) greater than all other elements in the component. [sent-199, score-0.272]
63 Definition 2 A unary leaf (UL) is an element x in a partial order hX, vi such that x is maximal and x pisa trhtiea successor of exactly one oxt ihser m ealxeimmeanlt a. [sent-214, score-0.419]
64 Furthermore, ULs occur frequently in the partial orders we consider in practice; and by increasing the number of sets in an instance, they have a disproportionate effect on the difficulty of solv- ing the set programming problem. [sent-217, score-0.366]
65 We therefore implement a special solution process for instances containing ULs: we remove them all, solve the resulting instance, and then add them back one at a time while attempting to increase the overall number of elements as little as possible. [sent-218, score-0.233]
66 In practical experiments, the solver generally either produces an optimal or very nearly optimal solution within a time limit on the order of ten minutes; or fails to produce a feasible solution at all, even with a much longer limit. [sent-220, score-0.477]
67 n consists of finding the smallest b such that is at least k; that is the number of bits for th? [sent-224, score-0.417]
68 To add a UL x as the successor of an element y without increasing the total number of bits, we must find a choice of λ + 1of the bits already assigned to y, sharing at most λ bits with any of y’s other successors. [sent-232, score-0.891]
69 Our algorithm counts the subsets already covered, and compares that with the number of choices of λ + 1 bits from the bits assigned to y. [sent-235, score-0.678]
70 If enough choices remain, we use them; otherwise, we add bits until there are enough choices. [sent-236, score-0.339]
71 4 Solving For instances with a small number of sets and relatively large number of elements in the sets, we use an exponential variable solver. [sent-238, score-0.296]
72 This encodes the set programming problem into integer programming. [sent-239, score-0.256]
73 The constraints translate into simple inequalities on sums of the variables; and the system of constraints can be solved with standard integer programming techniques. [sent-247, score-0.388]
74 After solving the integer programming problem we can then assign elements arbitrarily 1517 to the appropriate combinations of sets. [sent-248, score-0.425]
75 The wide domains of the variables may be advantageous for some integer programming solvers as well. [sent-251, score-0.483]
76 However, it creates an integer programming problem of size exponential in the number of sets. [sent-252, score-0.293]
77 For more general set programming instances, we feed the instance directly into a solver designed for such problems. [sent-254, score-0.359]
78 We used the ECLiPSe logic programming system (Cisco Systems, 2008), which offers several set programming solvers as libraries, and settled on the ic sets library. [sent-255, score-0.645]
79 This is a straightforward set programming solver based on containment bounds. [sent-256, score-0.359]
80 We extended the solver by adding a lightweight not-subset constraint, and customized heuristics for variable and value selection designed to guide the solver to a feasible solution as soon as possible. [sent-257, score-0.487]
81 We choose variables near the top of the instance first, and prefer to assign values that share exactly λ bits with existing assigned values. [sent-258, score-0.384]
82 We also do limited symmetry breaking, in that whenever we assign a bit not shared with any current assignment, the choice of bit is arbitrary so we assume it must be the lowestindex bit. [sent-259, score-0.554]
83 The present work is primarily on the benefits of nonzero λ, and so a detailed study of general set programming techniques would be inappropriate; but we made informal tests of several other set-programming solvers. [sent-261, score-0.26]
84 We had hoped that a solver using containment-lexicographic hybrid bounds as described by Sadler and Gervet (Sadler and Gervet, 2008) would offer good performance, and chose the ECLiPSe framework partly to gain access to its ic hybrid sets implementation of such bounds. [sent-262, score-0.284]
85 We also evaluated the Cardinal solver included in ECLiPSe, which offers stronger propagation of cardinality information; it lacked other needed features and seemed no more efficient than ic sets. [sent-265, score-0.27]
86 Solvers with available source code were preferred for ease of customization, and free solvers were preferred for economy, but a license for ILOG CPLEX (IBM, 2008) was available and we tried using it with the natural encoding of sets as vectors of binary variables. [sent-267, score-0.5]
87 An instance with n sets of up to b bits, dense with pairwise constraints like subset and maximum intersection, requires Θ(n2b) variables when encoded into integer programming in the natural way. [sent-270, score-0.405]
88 As a result, the ECLiPSe solver can process much larger instances than CPLEX without exhausting memory. [sent-274, score-0.224]
89 In particular, the apparent superiority of λ = 0 for the synsem_min module should not be taken as indicating that no higher λ could be better: rather, that module includes a very difficult set programming instance on which the solver failed and fell back to GAK. [sent-287, score-0.549]
90 For the even larger modules, nonzero λ proved helpful despite solver failures, because of the bits saved by UL removal. [sent-288, score-0.576]
91 for the modules where the solver is failing anyway. [sent-291, score-0.257]
92 One important lesson seems to be that further work on set programming solvers would be bene- ficial: any future more capable set programming solver could be applied to the unsolved instances and would be expected to save more bits. [sent-292, score-0.788]
93 Table 3 and Figure 3 show the performance of the join query with various encodings. [sent-293, score-0.273]
94 As well as testing the non-modular ERG encoding for different values of λ, we tested the modularized encoding with λ = 0 for all modules (to show the effect of modularization alone) and with λ chosen per-module to give the shortest vectors. [sent-295, score-0.637]
95 The same implementation sufficed for all these tests, by means of putting all types in one module for the non-modular bit vectors or no types in any module for the pure lookup table. [sent-297, score-0.688]
96 The non-modular encoding with λ = 0 is the basic encoding of A ¨ıt-Kaci et al. [sent-302, score-0.426]
97 ture, using a technique first published by Weg- ner (1960), requires time increasing with the number of nonzero bits it counts; and a similar effect would appear on a word-by-word basis even if we used a constant-time per-word count. [sent-308, score-0.447]
98 In our experiments, λ = 9 gave the fastest joins for the non-modular encoding of the ERG. [sent-310, score-0.343]
99 5 Conclusion We have described a generalization of conventional bit vector concept lattice encoding techniques to the case where all vectors with λ or fewer one bits represent failure; traditional encodings are the case λ = 0. [sent-315, score-1.145]
100 A good encoding requires a kind of perfect hash, the design of which maps naturally to constraint programming over sets of integers. [sent-317, score-0.503]
wordName wordTfidf (topN-words)
[('bits', 0.339), ('bit', 0.277), ('bloom', 0.228), ('join', 0.222), ('encoding', 0.213), ('programming', 0.191), ('solvers', 0.182), ('successors', 0.174), ('solver', 0.168), ('eclipse', 0.139), ('erg', 0.136), ('encodings', 0.13), ('elements', 0.124), ('gak', 0.121), ('hashed', 0.121), ('si', 0.116), ('failure', 0.113), ('meet', 0.111), ('element', 0.109), ('uls', 0.106), ('sj', 0.106), ('successor', 0.104), ('partial', 0.099), ('module', 0.095), ('cplex', 0.091), ('joins', 0.091), ('modules', 0.089), ('modularization', 0.087), ('ul', 0.084), ('lookup', 0.082), ('embedding', 0.075), ('optimal', 0.073), ('maximal', 0.07), ('nonzero', 0.069), ('semilattice', 0.069), ('hash', 0.068), ('vectors', 0.067), ('constraints', 0.066), ('integer', 0.065), ('intersection', 0.063), ('preserves', 0.062), ('constraint', 0.061), ('irreducible', 0.061), ('cardinality', 0.059), ('feasible', 0.057), ('hx', 0.057), ('preserve', 0.056), ('instances', 0.056), ('array', 0.055), ('codes', 0.054), ('solution', 0.053), ('sx', 0.052), ('unification', 0.052), ('sadler', 0.052), ('query', 0.051), ('sk', 0.051), ('vector', 0.05), ('preservation', 0.047), ('filters', 0.046), ('smallest', 0.046), ('incomparable', 0.046), ('variables', 0.045), ('solving', 0.045), ('zero', 0.044), ('ic', 0.043), ('variable', 0.041), ('type', 0.04), ('hpsg', 0.04), ('fastest', 0.039), ('ri', 0.039), ('technique', 0.039), ('bottom', 0.039), ('removal', 0.039), ('orders', 0.038), ('sets', 0.038), ('exponential', 0.037), ('vi', 0.037), ('store', 0.037), ('types', 0.036), ('return', 0.036), ('lattice', 0.036), ('bounds', 0.035), ('bitwise', 0.035), ('carlsson', 0.035), ('clp', 0.035), ('cnfsat', 0.035), ('gervet', 0.035), ('ilog', 0.035), ('joinable', 0.035), ('modularized', 0.035), ('mtoe', 0.035), ('precomputation', 0.035), ('semilattices', 0.035), ('timeout', 0.035), ('stores', 0.034), ('construction', 0.033), ('traditional', 0.033), ('gerald', 0.033), ('least', 0.032), ('hierarchy', 0.032)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999994 7 acl-2010-A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices
Author: Matthew Skala ; Victoria Krakovna ; Janos Kramar ; Gerald Penn
Abstract: Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques.
2 0.081446446 29 acl-2010-An Exact A* Method for Deciphering Letter-Substitution Ciphers
Author: Eric Corlett ; Gerald Penn
Abstract: Letter-substitution ciphers encode a document from a known or hypothesized language into an unknown writing system or an unknown encoding of a known writing system. It is a problem that can occur in a number of practical applications, such as in the problem of determining the encodings of electronic documents in which the language is known, but the encoding standard is not. It has also been used in relation to OCR applications. In this paper, we introduce an exact method for deciphering messages using a generalization of the Viterbi algorithm. We test this model on a set of ciphers developed from various web sites, and find that our algorithm has the potential to be a viable, practical method for efficiently solving decipherment prob- lems.
3 0.079760268 183 acl-2010-Online Generation of Locality Sensitive Hash Signatures
Author: Benjamin Van Durme ; Ashwin Lall
Abstract: Motivated by the recent interest in streaming algorithms for processing large text collections, we revisit the work of Ravichandran et al. (2005) on using the Locality Sensitive Hash (LSH) method of Charikar (2002) to enable fast, approximate comparisons of vector cosine similarity. For the common case of feature updates being additive over a data stream, we show that LSH signatures can be maintained online, without additional approximation error, and with lower memory requirements than when using the standard offline technique.
4 0.073815808 93 acl-2010-Dynamic Programming for Linear-Time Incremental Parsing
Author: Liang Huang ; Kenji Sagae
Abstract: Incremental parsing techniques such as shift-reduce have gained popularity thanks to their efficiency, but there remains a major problem: the search is greedy and only explores a tiny fraction of the whole space (even with beam search) as opposed to dynamic programming. We show that, surprisingly, dynamic programming is in fact possible for many shift-reduce parsers, by merging “equivalent” stacks based on feature values. Empirically, our algorithm yields up to a five-fold speedup over a state-of-the-art shift-reduce depen- dency parser with no loss in accuracy. Better search also leads to better learning, and our final parser outperforms all previously reported dependency parsers for English and Chinese, yet is much faster.
5 0.062435683 14 acl-2010-A Risk Minimization Framework for Extractive Speech Summarization
Author: Shih-Hsiang Lin ; Berlin Chen
Abstract: In this paper, we formulate extractive summarization as a risk minimization problem and propose a unified probabilistic framework that naturally combines supervised and unsupervised summarization models to inherit their individual merits as well as to overcome their inherent limitations. In addition, the introduction of various loss functions also provides the summarization framework with a flexible but systematic way to render the redundancy and coherence relationships among sentences and between sentences and the whole document, respectively. Experiments on speech summarization show that the methods deduced from our framework are very competitive with existing summarization approaches. 1
6 0.061123502 171 acl-2010-Metadata-Aware Measures for Answer Summarization in Community Question Answering
7 0.059261337 130 acl-2010-Hard Constraints for Grammatical Function Labelling
8 0.057817794 70 acl-2010-Contextualizing Semantic Representations Using Syntactically Enriched Vector Models
9 0.055900995 166 acl-2010-Learning Word-Class Lattices for Definition and Hypernym Extraction
10 0.051572863 128 acl-2010-Grammar Prototyping and Testing with the LinGO Grammar Matrix Customization System
11 0.048796892 184 acl-2010-Open-Domain Semantic Role Labeling by Modeling Word Spans
12 0.048491303 66 acl-2010-Compositional Matrix-Space Models of Language
13 0.048323374 255 acl-2010-Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization
14 0.047808833 133 acl-2010-Hierarchical Search for Word Alignment
15 0.04565401 172 acl-2010-Minimized Models and Grammar-Informed Initialization for Supertagging with Highly Ambiguous Lexicons
16 0.04538881 217 acl-2010-String Extension Learning
17 0.045175888 65 acl-2010-Complexity Metrics in an Incremental Right-Corner Parser
18 0.044665199 211 acl-2010-Simple, Accurate Parsing with an All-Fragments Grammar
19 0.044535458 226 acl-2010-The Human Language Project: Building a Universal Corpus of the World's Languages
20 0.043909695 245 acl-2010-Understanding the Semantic Structure of Noun Phrase Queries
topicId topicWeight
[(0, -0.151), (1, 0.004), (2, -0.013), (3, -0.036), (4, -0.006), (5, -0.053), (6, 0.038), (7, -0.01), (8, 0.035), (9, -0.017), (10, -0.062), (11, 0.029), (12, -0.008), (13, -0.037), (14, -0.074), (15, 0.018), (16, -0.01), (17, 0.024), (18, -0.046), (19, 0.067), (20, 0.03), (21, 0.017), (22, 0.015), (23, -0.055), (24, 0.054), (25, 0.002), (26, -0.03), (27, -0.016), (28, 0.001), (29, 0.009), (30, -0.017), (31, -0.005), (32, -0.053), (33, -0.007), (34, -0.03), (35, 0.044), (36, -0.074), (37, -0.058), (38, -0.014), (39, -0.02), (40, -0.001), (41, -0.026), (42, 0.101), (43, 0.02), (44, 0.029), (45, 0.003), (46, -0.098), (47, 0.062), (48, 0.059), (49, 0.072)]
simIndex simValue paperId paperTitle
same-paper 1 0.9422307 7 acl-2010-A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices
Author: Matthew Skala ; Victoria Krakovna ; Janos Kramar ; Gerald Penn
Abstract: Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques.
2 0.59742165 98 acl-2010-Efficient Staggered Decoding for Sequence Labeling
Author: Nobuhiro Kaji ; Yasuhiro Fujiwara ; Naoki Yoshinaga ; Masaru Kitsuregawa
Abstract: The Viterbi algorithm is the conventional decoding algorithm most widely adopted for sequence labeling. Viterbi decoding is, however, prohibitively slow when the label set is large, because its time complexity is quadratic in the number of labels. This paper proposes an exact decoding algorithm that overcomes this problem. A novel property of our algorithm is that it efficiently reduces the labels to be decoded, while still allowing us to check the optimality of the solution. Experiments on three tasks (POS tagging, joint POS tagging and chunking, and supertagging) show that the new algorithm is several orders of magnitude faster than the basic Viterbi and a state-of-the-art algo- rithm, CARPEDIEM (Esposito and Radicioni, 2009).
3 0.58123034 183 acl-2010-Online Generation of Locality Sensitive Hash Signatures
Author: Benjamin Van Durme ; Ashwin Lall
Abstract: Motivated by the recent interest in streaming algorithms for processing large text collections, we revisit the work of Ravichandran et al. (2005) on using the Locality Sensitive Hash (LSH) method of Charikar (2002) to enable fast, approximate comparisons of vector cosine similarity. For the common case of feature updates being additive over a data stream, we show that LSH signatures can be maintained online, without additional approximation error, and with lower memory requirements than when using the standard offline technique.
4 0.5754149 186 acl-2010-Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
Author: Benoit Sagot ; Giorgio Satta
Abstract: Linear Context-Free Rewriting Systems (LCFRSs) are a grammar formalism capable of modeling discontinuous phrases. Many parsing applications use LCFRSs where the fan-out (a measure of the discontinuity of phrases) does not exceed 2. We present an efficient algorithm for optimal reduction of the length of production right-hand side in LCFRSs with fan-out at most 2. This results in asymptotical running time improvement for known parsing algorithms for this class.
5 0.56289792 29 acl-2010-An Exact A* Method for Deciphering Letter-Substitution Ciphers
Author: Eric Corlett ; Gerald Penn
Abstract: Letter-substitution ciphers encode a document from a known or hypothesized language into an unknown writing system or an unknown encoding of a known writing system. It is a problem that can occur in a number of practical applications, such as in the problem of determining the encodings of electronic documents in which the language is known, but the encoding standard is not. It has also been used in relation to OCR applications. In this paper, we introduce an exact method for deciphering messages using a generalization of the Viterbi algorithm. We test this model on a set of ciphers developed from various web sites, and find that our algorithm has the potential to be a viable, practical method for efficiently solving decipherment prob- lems.
6 0.54417241 64 acl-2010-Complexity Assumptions in Ontology Verbalisation
7 0.51748788 255 acl-2010-Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization
8 0.49111283 130 acl-2010-Hard Constraints for Grammatical Function Labelling
9 0.48867658 235 acl-2010-Tools for Multilingual Grammar-Based Translation on the Web
10 0.48255923 196 acl-2010-Plot Induction and Evolutionary Search for Story Generation
11 0.48033628 66 acl-2010-Compositional Matrix-Space Models of Language
12 0.47903812 224 acl-2010-Talking NPCs in a Virtual Game World
13 0.4759447 61 acl-2010-Combining Data and Mathematical Models of Language Change
14 0.4661054 182 acl-2010-On the Computational Complexity of Dominance Links in Grammatical Formalisms
15 0.46295643 139 acl-2010-Identifying Generic Noun Phrases
16 0.45822367 166 acl-2010-Learning Word-Class Lattices for Definition and Hypernym Extraction
17 0.45024812 211 acl-2010-Simple, Accurate Parsing with an All-Fragments Grammar
18 0.44877112 128 acl-2010-Grammar Prototyping and Testing with the LinGO Grammar Matrix Customization System
19 0.44331062 65 acl-2010-Complexity Metrics in an Incremental Right-Corner Parser
20 0.43793994 43 acl-2010-Automatically Generating Term Frequency Induced Taxonomies
topicId topicWeight
[(14, 0.016), (25, 0.044), (39, 0.421), (42, 0.012), (44, 0.014), (59, 0.095), (73, 0.035), (78, 0.031), (80, 0.014), (83, 0.062), (84, 0.034), (98, 0.108)]
simIndex simValue paperId paperTitle
same-paper 1 0.85554898 7 acl-2010-A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices
Author: Matthew Skala ; Victoria Krakovna ; Janos Kramar ; Gerald Penn
Abstract: Constructing an encoding of a concept lattice using short bit vectors allows for efficient computation of join operations on the lattice. Join is the central operation any unification-based parser must support. We extend the traditional bit vector encoding, which represents join failure using the zero vector, to count any vector with less than a fixed number of one bits as failure. This allows non-joinable elements to share bits, resulting in a smaller vector size. A constraint solver is used to construct the encoding, and a variety of techniques are employed to find near-optimal solutions and handle timeouts. An evaluation is provided comparing the extended representation of failure with traditional bit vector techniques.
2 0.81142759 2 acl-2010-"Was It Good? It Was Provocative." Learning the Meaning of Scalar Adjectives
Author: Marie-Catherine de Marneffe ; Christopher D. Manning ; Christopher Potts
Abstract: Texts and dialogues often express information indirectly. For instance, speakers’ answers to yes/no questions do not always straightforwardly convey a ‘yes’ or ‘no’ answer. The intended reply is clear in some cases (Was it good? It was great!) but uncertain in others (Was it acceptable? It was unprecedented.). In this paper, we present methods for interpreting the answers to questions like these which involve scalar modifiers. We show how to ground scalar modifier meaning based on data collected from the Web. We learn scales between modifiers and infer the extent to which a given answer conveys ‘yes’ or ‘no’ . To evaluate the methods, we collected examples of question–answer pairs involving scalar modifiers from CNN transcripts and the Dialog Act corpus and use response distributions from Mechanical Turk workers to assess the degree to which each answer conveys ‘yes’ or ‘no’ . Our experimental results closely match the Turkers’ response data, demonstrating that meanings can be learned from Web data and that such meanings can drive pragmatic inference.
3 0.76068705 180 acl-2010-On Jointly Recognizing and Aligning Bilingual Named Entities
Author: Yufeng Chen ; Chengqing Zong ; Keh-Yih Su
Abstract: We observe that (1) how a given named entity (NE) is translated (i.e., either semantically or phonetically) depends greatly on its associated entity type, and (2) entities within an aligned pair should share the same type. Also, (3) those initially detected NEs are anchors, whose information should be used to give certainty scores when selecting candidates. From this basis, an integrated model is thus proposed in this paper to jointly identify and align bilingual named entities between Chinese and English. It adopts a new mapping type ratio feature (which is the proportion of NE internal tokens that are semantically translated), enforces an entity type consistency constraint, and utilizes additional monolingual candidate certainty factors (based on those NE anchors). The experi- ments show that this novel approach has substantially raised the type-sensitive F-score of identified NE-pairs from 68.4% to 81.7% (42.1% F-score imperfection reduction) in our Chinese-English NE alignment task.
4 0.74465322 57 acl-2010-Bucking the Trend: Large-Scale Cost-Focused Active Learning for Statistical Machine Translation
Author: Michael Bloodgood ; Chris Callison-Burch
Abstract: We explore how to improve machine translation systems by adding more translation data in situations where we already have substantial resources. The main challenge is how to buck the trend of diminishing returns that is commonly encountered. We present an active learning-style data solicitation algorithm to meet this challenge. We test it, gathering annotations via Amazon Mechanical Turk, and find that we get an order of magnitude increase in performance rates of improvement.
5 0.44632345 65 acl-2010-Complexity Metrics in an Incremental Right-Corner Parser
Author: Stephen Wu ; Asaf Bachrach ; Carlos Cardenas ; William Schuler
Abstract: Hierarchical HMM (HHMM) parsers make promising cognitive models: while they use a bounded model of working memory and pursue incremental hypotheses in parallel, they still achieve parsing accuracies competitive with chart-based techniques. This paper aims to validate that a right-corner HHMM parser is also able to produce complexity metrics, which quantify a reader’s incremental difficulty in understanding a sentence. Besides defining standard metrics in the HHMM framework, a new metric, embedding difference, is also proposed, which tests the hypothesis that HHMM store elements represents syntactic working memory. Results show that HHMM surprisal outperforms all other evaluated metrics in predicting reading times, and that embedding difference makes a significant, independent contribution.
6 0.44224918 29 acl-2010-An Exact A* Method for Deciphering Letter-Substitution Ciphers
7 0.43653858 130 acl-2010-Hard Constraints for Grammatical Function Labelling
8 0.41664803 172 acl-2010-Minimized Models and Grammar-Informed Initialization for Supertagging with Highly Ambiguous Lexicons
9 0.41245791 93 acl-2010-Dynamic Programming for Linear-Time Incremental Parsing
10 0.41149813 39 acl-2010-Automatic Generation of Story Highlights
11 0.40906072 200 acl-2010-Profiting from Mark-Up: Hyper-Text Annotations for Guided Parsing
12 0.4071717 113 acl-2010-Extraction and Approximation of Numerical Attributes from the Web
13 0.40683669 115 acl-2010-Filtering Syntactic Constraints for Statistical Machine Translation
14 0.40586001 254 acl-2010-Using Speech to Reply to SMS Messages While Driving: An In-Car Simulator User Study
15 0.40489262 226 acl-2010-The Human Language Project: Building a Universal Corpus of the World's Languages
16 0.4041068 95 acl-2010-Efficient Inference through Cascades of Weighted Tree Transducers
17 0.40386018 194 acl-2010-Phrase-Based Statistical Language Generation Using Graphical Models and Active Learning
18 0.40310818 199 acl-2010-Preferences versus Adaptation during Referring Expression Generation
19 0.40222496 35 acl-2010-Automated Planning for Situated Natural Language Generation
20 0.40189803 76 acl-2010-Creating Robust Supervised Classifiers via Web-Scale N-Gram Data